Artificial neural networks find solution to problems by learning from a large number of examples. The procedure used to carry out the learning process in a neural network is called the training algorithm. The learning problem in neural networks is formulated in terms of the minimization of a cost function.

Quadratic Cost function (MSE - Mean Squared Error)

The Quadratic Cost function $C$, also known as the Mean Square Error (MSE), is defined as:

$$C(w,b) \equiv \frac{1}{2n} \sum_x \| y(x) - a \|^2 $$

Where $w$ denotes the collection of all weights in the neural network, $b$ represents all the biases, $n$ is the total number of training inputs, $a$ is the vector of outputs from the network when $x$ is input, and the sum is over all training inputs, $x$ .

Using a smooth cost function like the quadratic cost it turns out to be easy to figure out how to make small changes in the weights and biases so as to get an improvement in the cost.

The aim of training algorithm is to minimize the cost $C(w,b)$ as a function of the weights and biases, i.e., to find a set of weights and biases which make the cost as small as possible. Commonly, the algorithm known as gradient descent is used to do that.

Learning with gradient descent

Assuming $C$ is a function of two variables $v_1$ and $v_2$, as illustrated in the figure below, and we want to find where $C$ achieve its global minimum.

let's think about what happens when we move a small amount $\Delta v_1$ in the direction $v_1$, and a small amount $\Delta v_{21}$ in the direction $v_2$. Calculus tells us that $C$ changes as follows:

$$\Delta C \approx \frac{\partial C}{\partial v_1} \Delta v_1 + \frac{\partial C}{\partial v_2} \Delta v_2.$$

If we can find a way of choosing $\Delta v_1$ and $\Delta v_2$ so as to make $\Delta C$ negative, we should be able to find where $C$ achieve its global minimum.

Define $\Delta v$ to be the vector of changes. In 2D, it is:

$$\Delta v \equiv (\Delta v_1, \Delta v_2)^T $$

Where $T$ is the transpose operation.

Also, define the gradient of $C$ to be the vector of partial derivatives:

$$\nabla C \equiv \Big(\frac{\partial C}{\partial v_1}, \frac{\partial C}{\partial v_2}\Big)^T $$

Then, $\Delta C$ can be rewritten in terms of $\Delta v$ and $\nabla C$:

$$\Delta C \approx \nabla C \cdot \Delta v $$

If we choose:

$\Delta v = \eta \nabla C$(a)

Where $\eta$ is a small, positive parameter (known as the learning rate)

Then:

$$\Delta C \approx - \eta \nabla C \cdot \nabla C = - \eta \| \nabla C \|^2 $$

Because $\| \Delta C\|^2 \ge 0$, this guarantees that $\Delta C \le 0$, i.e., $C$ will always decrease, never increase, if we change $v$ according to the prescription above. So we will use equation (a) to compute a value for $\Delta v$, then the new value of $v$ is:

$$v \to v^{'} = v - \eta \nabla C $$

To make gradient descent work correctly, we need to choose the learning rate $\eta$ to be small enough. To use gradient descent to find the weights $w_k$ and biases $b_l$ which minimize the Quadratic cost, we have:

$$w_k \to w_k^{'} = w_k - \eta \frac{\partial C}{\partial w_k} $$

$$b_l \to b_l^{'} = b_l - \eta \frac{\partial C}{\partial b_l} $$

Then, the question is: How to compute the gradient of the cost function?

Backpropagation
Backpropagation is a fast algorithm to compute the gradient of cost function. It is known as the workhorse of learning in neural networks. It gives us detailed insights into how changing the weights and biases changes the overall behaviour of the network.

The Universal Approximation Theorem
The standard multilayer feed-forward network with a single hidden layer, which contains finite number of hidden neurons, is a universal approximator among continuous functions on compact subsets of $R_n$ , under mild assumptions on the activation function.
A neural network can compute any function!

Pros and Cons

Pros of ANN include:
Can be trained directly on data with hundreds or thousands input variables
Once trained, predictions are fast
Great for complex/abstract problems like image recognition
Can significantly out-perform other models when the conditions are right (lots of high quality labeled data).

Cons of ANN include:
Black box that not much can be gleaned from
Training is computationally expensive
Can suffer from “interference” in that new data cause it to forget some of what it learned on old data
Often abused in cases where simpler solutions like linear regression would be best

Clustering is a technique to find similar groups (i.e., clusters) in a data. Clustering is an unsupervised learning, as there are no prescribed labels in the data and no class values denoting a priori grouping of the data instance are given. K-means clustering is the most used clustering algorithm.

“K” in K-Means represents the number of clusters in which we want our data to divide into, i.e., K-means clustering will categorize data into k groups of similarity. It tries to improve the inter group similarity while keeping the groups as far as possible from each other. To calculate that similarity, the Euclidean distance is used as measurement.

K-Means can be applied to almost any branch of study. While the basic restriction for the implementation of K-means is: your data should be continuous in nature. It won’t work if data is categorical in nature.

K-means algorithm

K-means algorithm works as:

1. Randomly initialise k cluster centroids.

2. Categorize each data instance to its closest centroid, then update the centroid’s coordinates, which are the averages of the instances categorized in that mean so far.

3. Repeat step 2 until convergence and at the end, we have our clusters.

In pseudo code, the algorithm can be written as:

An example

In this example, we want to divide the points (plotted as circle in the figure below) into two groups using K-means. So, in this case, K=2.

To run this K-means algorithm, first we randomly initialize two points (plotted as the red and yellow triangles in the figure below) as two cluster centroids.

Next, we assign each point into the cluster closer to it. As illustrated below, we use different colours to present different clusters. And we call them the red cluster and the yellow cluster.

Now we calculate the average of the points in each cluster (i.e., the white triangle in the figure below).

And update the cluster centroids to the average locations.

Then, use the updated centroid positions, assign the data points to either red or yellow cluster, depending on which cluster centroid the point closer to. As shown below, two points changed their colour, i.e., cluster.

Again, we update the centroid location to the average position of the points in each cluster.

And re-assign the cluster to each point, two points changed their cluster in this iteration. Again we calculate the average position of the points in each cluster.

And move the centroids to the average position. Using the updated centroid location assign the cluster to the points, there is no change in the clusters: it is converged. And we have the 2 clusters.