Data Science Part 18: Kernel methods, support vector machines, deep learning

 

Recall the nearest neighbors formulation 

which Nk(X) is basically just the set of the K nearest neighbors, in which we want to take the average of. 

Here, the Nearest Neighbor estimator is bumpy. Another way to approach this is to assign greater confidence to nearer points and to taper away for distant points. We can formulate the function and approximate the corresponding Y value as follows: 

These nearest neighbors can be used for regression and predicting the Y values for certain points. 

The next topic to talk about is support vector machines (svms). The main idea of svms is to find  a hyperplane that best-separates two classes of data, as demonstrated by the diagram below: 

So how do we compute the perfectly separating "optimal" hyperplane?

Doing this.

We can also have slack variables with a small l1 norm. 

A note we can contrive is that perfectly separating hyperplane may exist in high dimensional space. We need to map ℝ^p to a higher dimensional space (kernels, splines, polynomials, etc.). As a result, we find a hyperplane with the best margin in transformed space.

The final topic that will be discussed here is Artificial Neural Networks (ANNs). They are algorithms inspired the by biological neuron networks in the brain. It is comprised of neurons and synapses in sequential layers. The neurons contain activation functions to change their internal states and produce output. Then the "synapses" will use backpropagation to update the weights. Data is traversed multiple times to improve learning. 

Deep Learning uses feature extractions to learn a model of the input-output data. These interacting layers can be used to extract features, corresponding to different layers of abstraction. Each successive layer uses the output of the previous layer, most of which are hidden. Extracted features can then be used for classification or simply feature detection. Multiple layers can be used to extract features corresponding to different layers of abstraction. Applications are image recognition, speech recognition, and advertising (recommendation systems).

Per Wikipedia, in deep learning, a convolutional neural network (CNN, or ConvNet) is a class of artificial neural network (ANN), most commonly applied to analyze visual imagery. 

The first step into these networks and convolution. The convolution layer applies a convolution operation to the input image.

The second step is called thresholding, where it applies ReLU (Rectified Linear Units) to introduce nonlinearity in the feature maps generated by the convolution layer which is linear at positive number and zero in negative number. It's defined as f(x) = max(0, x). Another function is called a hyperbolic function used to increase nonlinearity. 

Step 3 is pooling which downsamples the matrix/map by  selecting the most important features. The exact location of a feature is less important than its rough location relative to other features. An example is max pooling/average pooling/sum pooling, which selects the maximum/average/sum of all the elements of the area being pooled. It makes images less detailed and easier to process. 

Step 4 is classification. ANN has multiple hidden layers inside in which each layer connects strongly to each other. The arguments is the number of neurons.

The steps for a CNN are as follows: 

1. Divide the training set into smaller subsets then randomly select one of the sets. 

2. Forward propogation with convolution, thresholding, pooling, classification operations, get some probability values for each class. 

3. Back propagation to update filter weights and layer weights with the gradient descent method.

4. Repeat 1-2 for all batches. This is an epoch.

5. Do multiple epochs until training stabilizes. This is the final model.

Convolutional Neural networks are trained on GPUs to obtain a reasonable execution time. Here's an example of a CNN and the stuff it can identify/generate. We can accelerate these calculations through stochastic gradient descent. Compared to Gradient Descent, Stochastic Gradient Descent is much faster, and more suitable to large-scale datasets. Gradient descent computes the derivative and a step function. The derivative is computed based on the difference between expected and actual values.

But since the gradient it's not computed for the entire dataset, and only for one random point on each iteration, the updates have a higher variance.