Brief Overview of G-Ramp - Image Classification
Note:- Since G-Ramps platform is under development, you will find missing steps or missing parts of already mentioned steps. That is, you will find some arguments which are either not proved mathematically or not supported by experimentation. With time, there should be a lesser and lesser number of such arguments. If there are such arguments, then I should at least fix them temporarily by providing a good reference for each such argument.
Between any two adjacent steps, either it will be explicitly mention that there are missing steps between these two steps. Or there may not be such mention of missing steps. Similarly, there may or may not be explicit mention of missing parts of any already mentioned steps. Text in square brackets ‘[]’ is used to mention about missing steps or about missing parts of already mentioned steps.
A step title below starts with “LS” meaning logical step. Steps should be numbered like “LS#1 …”. But putting numbers during development creates difficult because it is not straightforward how to increment the numbers when steps are added in between. So, until a g-ramp is complete and contain all the steps, steps are not numbered.
Brief Overview
- Prerequisite
- Just curiosity to master AI algorithms and nothing else. We are assuming that anyone who is curious to master AI must be already good at school-level maths. This assumption is very weak and there are high chances of it being true.
- You do not even need to revise school-level maths. We will gonna cover it enough that you will revise it while going through a ramp.
- Main Problem
- We wanna let computer do image classification like a human.
- For simplicity, let’s scale down the problem where given an image of either a dog or a cat, a computer should be able to correctly classify the image and assign a label - dog or cat.
- [Explain why image classification via a computer?]
[steps leading to next and first solution of main problem which is hard coding]
- LS - Hard Coding
- One way to do image classification is to create a computer program where rules are hard coded.
- [About traditional Computer Vision]
- hand-coded features etc.
- Ref. Szeliski’s book
- LS - Introducing Machine Learning
- [Add an explanation how hard coding is difficult because there are exponentially large number of rules and one can not write each of them in a program. Hence, hard coded algorithm won’t do image classification accurately or it would be just too much laborious to create a correct algorithm. Explain that image classification is hard and motivate the need for better solution.]
- How humans learn to do image classification? By looking at many examples before they can accurately do image classification. Can we have a way where a computer learns by itself just like a human?
- [add explanation that we need to have a dataset for computer to learn]
- We can have a “dataset” of images where each image has a “label” representing the “class” of that image.
- [search for dataset for problem at our hand, i.e., for cat-dog image classification.]
- Now we need to think of whether we can create a “learning” algorithm which takes this dataset as input and outputs another algorithm which contain learned rules.
- [Explain that we need mathematics to build these two algorithms by taking help from this blog - AI - Mathematical Formulation of Intelligence. Conclusion should be that we need to use mathematics to do learning and to do action of “classification”. So, learning, and action (classification) algorithms are nothing but implementation of mathematics.]
- This mathematical formulation of intelligence is called “Machine Learning” or “ML” in short.
- And action algorithm is generally called “model” in machine learning because it models the real but unknown function of nature, in our case it is the human ability to classify things.
- And in ML, “learning” is also called “training”.
- [Explain how to think of coming up with these mathematical functions? Which include first representing dataset in mathematical terms. Then from there come to the conclusion that firstly one need to think of a structure of a model and then think of how to create a learning algorithm which can output appropriate model.]
- LS - Linear Model
- [explain how this is the first model which we should be thinking about]
- We know about plane equation in mathematics.
- What if there is a plane which separates the two classes.
- To find such plane, means, finding appropriate slopes and intercept of the plane.
- In ML terms, these slopes and intercept are called weights and biases. And for simplicity, we will be also calling biases as just weights.
- LS - Searching
- Weights are real numbers. And there are many weights.
- So, there are infinitely many possible values, weights can take.
- How to find appropriate weight values out of infinite possibilities?
- [explain that this is exactly what we mean by “learning”]
- So, now we are dealing with a search problem?
- We need some way to determine whether we have reached to the solution or the appropriate values while searching.
- Given the dataset, we can calculate “accuracy” corresponding to each set of weight values.
- [explain accuracy]
- So, we are searching for weight values which gives maximum accuracy which is 100%.
- That means, our search problem is nothing but an optimization problem. An optimization problem is a specific kind of search problem where we are looking for values which maximizes some score or minimizes some cost.
- [Explain that given this optimization problem, next obvious solution is brute force search.]
- LS - Efficient Searching
- [explain the difficulty or inefficiency of brute force search]
- [Since, real values are involved, conclude that we can think of optimization algorithms which uses continuous functions and finds its minima or maxima analytically i.e., by solving the equation. Which is exponentially much easier than brute force search.]
- We have learned about finding minima or maxima of a continuous function in the school.
- But we need a differentiable function.
- Accuracy is not differentiable.
- Differentiable meaning there exist tangent and hence its slope at every point.
- Accuracy function is a step function. It contain sharp corners. So, no tangent line exist at such corners and hence function is not differentiable.
- So, we need differentiable function.
- [come to the conclusion that we can use squared error function]
- [may be we can explain it like this: we can have a distance function which calculates distance between current prediction and given label. Because its minima lead us to our solution.]
- [also introduce the terms “cost” or “loss”]
- [Now talk about optimization by using this function, which involves checking for convexity, differentiation, and finding global minima. And also introduce the term “loss surface” while checking for convexity.]
- LS - Non-Linearity
- [explain problem with linear model by experimentation and by theoretically]
- Find non-linear model
- There are many ways a model can be non-linear.
- By analyzing, one should find what kind of non-linearity an image classification problem has.
- E.g. XOR like non-linearity.
- Image classification has very arbitrary non-linearity, very random. Classes are so intermingled between each other. Talked about it in this blog - Understanding Non-Linearity in Image Classification.
- Because class is determined by a particular wave like pattern and this pattern could appear anywhere, at any scale, which also leads to classes appearing next to each other and intermingled. Because only subtle differences between neighboring pixel values, a subtle wave pattern is the only differentiator between the classes. It is not about what pixels taking what values but it is only about particular differences between neighboring pixels.
- Such non-linearity is similar to simple XOR like non-linearity. [Or also similar to non-linearity in shifter problem in Boltzmann machine paper?]
- [now connect non-linearity to “features” or “representation”]
- Features or representation terms are used interchangeably.
- [Define high-level or abstract and low-level representation]
- [Explain how representation term came to use. From inspiration with brain and neuroscience?]
- [Explain representation from brain point of view by analyzing our own mental processing]
- When we see something e.g. a dog, we extract some abstract features of it unconsciously, its shape, height, color etc.
- Term “representation” is used because we are representing some information in a computer.
- Lowest level of representation is nothing but arrays of pixels.
- Low level features like pixel values contain lot of information which we do not need for the task of image classification. It contain information about the position, scale (wrt background), pose etc. of a dog or cat which actually does not differentiate between dog and cat.
- High level representation of a complex object like image is nothing but most compressed description of the object which is useful for a particular task like image classification. Compressed description can also mean discarding low level useless features (for the task) and only retaining abstract or high-level features which are useful for the task. Objects with same abstract features may have very different low level features e.g. pixel values.
- We just need those high-level representation which are useful for the task.
- [explain why we need to discard low-level features. One explanation is that high-level features makes the data linear so we can use linear model. But we can have one more explanation which should feel more natural. It could be like - it is a way to only attend to the information that is needed for the task.]
- LS - Non-Linear Model
- Now the problem is that how do we create a model that can deal with such non-linearity.
- [conclude that such model should be able to extract high-level representation]
- [Now come to conclusion that to extract high-level representation, we need to have hidden units with “activation function”.]
- Simplest activation function we can think of is a step or binary function.
- [Introduce the term “Neural Network” or “Artificial Neural Network” or “Multi Layer Perceptron” or in short “NN”, “ANN” or “MLP”. Also explain why “NN” and “activation function” as a name? inspiration from neuroscience.]
- [Explain that to make NN arbitrary non-linear, one have to make it multi-layer, i.e., add more number of hidden layers]
- [explain that we discovered “Universal Function Approximation” theorem]
- Apparently, pattern recognition is one of the early problems which motivated the development of neural network.
- [For reference, look for evolution of neural networks. Initially, NNs were tested on toy non-linear problems like XOR, shifter problem etc.]
- LS - Learning in NN
- [Follow the same procedure of training as we did for linear model]
- Use squared error function as a cost function.
[Steps about many attempts one can try like competitive learning, BM, RBM etc. for training NNs]
- LS - Credit Assignment Problem
- [Explain that cost function is not differentiable because of step activation function.]
- And hence there is this popular “Credit Assignment Problem”.
- [It looks like this problem is introduced in this ramp just for the sake of introducing it. We need to add more explanation such that we discover this problem by ourselves and not just introduce it anyhow because we want to introduce it.]
- We don’t know which weight (or which neuron) to blame for the error. Or which weight causes this error. If we know this, then we can change that weight such that we reduce the error.
- How to fix this problem? Obvious solution is to think of smooth activation function.
- [Introduce “Sigmoid” activation function and explain how we can think of choosing this activation function]
- Now cost function over NN with sigmoid activation function is differentiable.
- LS - Non-Convexity
- [Check for convexity]
- Turns out loss surface is not convex.
- So, there is no single minima. It means equation of zero gradient have multiple solution.
- Next obvious step is that we find these solutions.
- [Check for convexity]
- LS - Multivariate Differentiation
- [To find the zero gradient equation, we have to do multivariate differentiation]
- [explain all these concepts partial derivative, total derivative, gradient and jacobian]
- [To find the zero gradient equation, we have to do multivariate differentiation]
- LS - Gradient Descent
- [Explain that finding solution of zero gradient equation is impossible]
- [now come to conclusion that we have to do gradient based optimization i.e., gradient descent]
- [Explain that for gradient descent:]
- [we have to first initialize the weights]
- [then given the weight values, we have to use these values to calculate gradient]
- [algorithm used to calculate the gradient is called “back propagation”]
- [explain “learning rate”]
- [now explain training iterations and “epochs”]
[steps about stochastic gradient descent (SGD), validation set, testing set, evaluation metric (e.g. accuracy), overfitting, underfitting, bias, variance, data preprocessing (e.g. normalization) etc.]
- Note:- Put rest of the steps regarding improvement in training, model and cost function in “Advanced Classification Algorithm” ramp which will come after third ramp. Also deal with multi class classification problem in that ramp.
- Improvement in training of neural network
- There are problems in training “deep” networks via back propagation.
- problems are like NN getting stuck in bad local minima, gradient flow problem like vanishing and exploding gradient etc.
- [to fix it, think of using kernel based ML algorithms]
- [think of using layer-wise pre-training so that layers are better preconditioned before training end-to-end via backpropagation]
- There are problems in training “deep” networks via back propagation.
- Improvement in model
- [introduce convolution layer]
- [introduce better activation function like ReLU which can lead to better end-to-end training via backpropagation. (ref: representation learning paper by Bengio et al, 2013)]
- [introduce dropout layer]
- [introduce normalization layers like batch normalization, layer normalization etc.]
- [et cetera, et cetera…]
- Improvement in cost function
- [explain the problem with squared error]
- Does not give proper weight to misclassification errors which are not serious vs which are serious.
- [introduce binary cross entropy and cross entropy loss]
- [explain the problem with squared error]
- Improvement in training of neural network
- Take Away
- Mastered an image classification algorithm
- Which lead us to introduction and mastery of these topics
- Image classification problem
- Machine Learning
- Linear model
- Optimisation algorithm
- Square Loss
- Global optimisation
- sgd
- neural network
- representation
- universal function approximation
- etc.