Machine learning basics

tags: machine learning

• Machine learning basics
  • Linear regression with one variable
  • Linear regression with multiple variables
  • Logistic regression
    • Binary classification
    • Multiclass classification
  • Overfitting and regulization
  • Neural networks
    • Model representation
    • Forward propagation
    • Cost function
    • Back propagation

The material is from Andrew Ng's course: Machine Learning^[1]. Another excellent material is the book "Neutral networks and deep learning" written by Michael Nielsen^[2].

Linear regression with one variable

Training sample

$(x,y)$, where

$x$ is called the feature (input),

$y$ the target (output).

$(x^{(i)},y^{(i)})$–-the

$i^{th}$ instance of the training sample.

Hypothesis:

$h_{\theta }(x)={\theta }_0+{\theta }_{1}x$. Given a value of the feature, predict the value of the target.

What is the flow chart of the machine learning process?

Cost function: Measure the error between the prediction from the hypothesis and the target value from the training set. We denote it as

$J$. We can define many different versions of such measures. One of the most common choices is the so-called

$L_2$ norm, which is defined by the equation

$$J({\theta }_0,{\theta }_1)=\frac{1}{2m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)}{)}^2,$$
where

$m$ is the size of the training sample.

The goal of the machine leraning algorithm is to find the parameters,

${\theta }_0$ and

${\theta }_1$, such that the cost function

$J({\theta }_0,{\theta }_1)$ achieves the minimum value.

How do we find such combination of

$({\theta }_0,{\theta }_1)$?
Gradient descent (GD) method

Starting from an initial guess of

${\theta }_0$ and

${\theta }_1$, we update them as

$${\theta }_j\leftarrow {\theta }_j-\alpha \frac{\partial J}{\partial {\theta }_j},j=1,2,$$

where

$\alpha$ is referred to as learning rate.

When applying the GD method to the linear regression, we have

$$\begin{array}{rl}{\theta }_0& \leftarrow {\theta }_0-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)}),\\ {\theta }_1& \leftarrow {\theta }_1-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)})x^{(i)}.\end{array}$$

The aforementioned method is often referred to as the batch GD method since everytime it update the parameters using the information from all instances of the traning sample.

Linear regression with multiple variables

The model we consider now has more than one features,

$x_1,x_2,...,x_n$, yet still one target value,

$y$.

The hypothesis becomes

$$h_{\theta }(\mathit{x})={\mathit{\theta }}^{\text{T}}\cdot \mathit{x}={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2+...+{\theta }_n{x}_n.$$

where

$\mathit{x}$ is a column vector and

$\mathit{x}=(x_0,x_1,x_2,...,x_n{)}^{\text{T}}$ with

$x_0=1$ called zero feature.

The cost function becomes

$$J({\theta }_0,{\theta }_1,...,{\theta }_n)=\frac{1}{2m}\sum _{i=1}^m(h_{\theta }({\mathit{x}}^{(i)})-y^{(i)}{)}^2.$$

The corresponding updates of

${\theta }_0$,

${\theta }_1$,…,

${\theta }_n$ are

$$\begin{array}{rl}{\theta }_0& \leftarrow {\theta }_0-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }({\mathit{x}}^{(i)})-y^{(i)}),\\ {\theta }_1& \leftarrow {\theta }_1-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }({\mathit{x}}^{(i)})-y^{(i)})x_1^{(i)}.\\ {\theta }_2& \leftarrow {\theta }_2-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }({\mathit{x}}^{(i)})-y^{(i)})x_2^{(i)},\\ & ⋮\\ {\theta }_n& \leftarrow {\theta }_n-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }({\mathit{x}}^{(i)})-y^{(i)})x_n^{(i)}.\end{array}$$

It is desirable to have the features whose values are of the same magnitude or on a similar scale (for fast convergence of the learning algorithm). The way to do this is called feature scaling. Often we scale the value of the

$j^{th}$ feature as

$$x_j:=\frac{x_j-{\mu }_j}{{\sigma }_j},j=1,2,...,n,$$

where

${\mu }_j$ and

${\sigma }_j$ are the average and standard deviation of

$x_j$.

Logistic regression

We now move on to the classification problems, e.g., whether an email belongs to spam or not, in which the prediction has discrete values.

The logistic regression is one of the most common learning algorithms for classification problems.

Binary classification

The output of logistic regression is always in the range

$[0,1]$.

Logistic regression model:

$h_{\theta }(\mathit{x})\in [0,1]$

$$\begin{array}{rl}{h}_{\theta }(\mathit{x})& =g({\mathit{\theta }}^{\text{T}}\cdot \mathit{x}),\\ g(z)& =\frac{1}{1+e^{-z}},\end{array}$$

where

$g$ is called logistic/sigmoid function.

For a set of parameters

$\mathit{\theta }$ and input

$\mathit{x}$, the model estimates the probability at which the output equals one, i.e.,

$$h_{\theta }(\mathit{x})=P(y=1|\mathit{x},\mathit{\theta }).$$

Decision boundary:
The model predicts

$y=1$ for

$h_{\theta }(\mathit{x})\ge 0.5$ and

$y=0$ for

$h_{\theta }(\mathit{x})<0.5$. From the graph of the sigmoid function we have

$g(z=0)=0.5$,

$g(z>0)>0.5$, and

$g(z<0)<0.5$. Thus, we get that

$y=1$ when

${\mathit{\theta }}^{\text{T}}\cdot \mathit{x}\ge 0$ and

$y=0$ otherwise.

Here is an example:

$h_{\theta }(\mathit{x})=g(-3+x_1+x_2)$. It predict a cross when

$-3+x_1+x_2\ge 0$ and a circle otherwise.

Cost function:

To construct a convex cost function, we define

$$Cost(h_{\theta }(\mathit{x}),y)=\{\begin{array}{ll}-\log (h_{\theta }(\mathit{x}))& \text{if}y=1,\\ -\log (1-h_{\theta }(\mathit{x}))& \text{if}y=0.\end{array}$$

It means that when

$y=1$ and the prediction is also 1, then the cost is 0, when

$y=1$ but the prediction is 0, then the cost is

$\mathrm{\infty }$. Similar for the case when

$y=0$.

Then the cost function is

$$J(\mathit{\theta })=\frac{1}{m}\sum _{i=1}^{m}Cost(h_{\theta }({\mathit{x}}^{(i)}),y^{(i)}).$$

Note that

$y$ can only take the value to be either 0 or 1. We can rewrite

$Cost(h_{\theta }(\mathit{x}),y)$ as

$$Cost(h_{\theta }(\mathit{x}),y)=-y\log (h_{\theta }(\mathit{x}))-(1-y)\log (1-h_{\theta }(\mathit{x})).$$

And the cost function becomes

$$J(\mathit{\theta })=\frac{1}{m}\sum _{i=1}^m[-y^{(i)}\log (h_{\theta }({\mathit{x}}^{(i)}))-(1-y^{(i)})\log (1-h_{\theta }({\mathit{x}}^{(i)}))].$$

The above function is also called cross-entropy loss function^[3].

We update the parameters

$\mathit{\theta }$ as

$${\theta }_j\leftarrow {\theta }_j-\alpha \frac{\partial J(\mathit{\theta })}{\partial {\theta }_j}$$

where

$$\frac{\partial J(\mathit{\theta })}{\partial {\theta }_j}=\frac{1}{m}\sum _{i=1}^m[h_{\theta }({\mathit{x}}^{(i)})-y^{(i)}]x_j^{(i)},$$

for

$j=0,1,...,n$.

Multiclass classification

Training the three classifiers

$h_{\theta }^{(i)}(\mathit{x})$. For a given

$\mathit{x}$, choose

$i$ such that

$h_{\theta }^{(i)}(\mathit{x})=P(y=i|\mathit{x},\mathit{\theta })$ is maximum, i.e.,

$\underset{i}{max}{h}^{(i)}(\mathit{x})$.

Overfitting and regulization

Overfitting of the model to the data comes from the higher orders in the hypothesis

$h_{\theta }(\mathit{x})$.

To avoid overfitting, we can penalize the higher orders in the cost function, i.e., regularization.

Introduce a regularization parameter,

$\lambda$, which is a large number, in the cost function.

Regularized linear regression:

The regularized cost function

$$J(\mathit{\theta })=\frac{1}{2m}\sum _{i=1}^m((h_{\theta }({\mathit{x}}^{(i)})-y^{(i)}{)}^2+\lambda \sum _{i=1}^n{\theta }_j^2).$$

The learning algorithm

$$\begin{array}{rl}{\theta }_0& \leftarrow {\theta }_0-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }({\mathit{x}}^{(i)})-y^{(i)}),\\ {\theta }_j& \leftarrow {\theta }_j-\alpha \frac{1}{m}\sum _{i=1}^m((h_{\theta }({\mathit{x}}^{(i)})-y^{(i)})x_j^{(i)}+\frac{\lambda }{m}{\theta }_j),j=1,2,...,n.\end{array}$$

Regularized logistic regression:

The regularized cost function

$$J(\mathit{\theta })=\frac{1}{m}\sum _{i=1}^m[-y^{(i)}\log (h_{\theta }({\mathit{x}}^{(i)}))-(1-y^{(i)})\log (1-h_{\theta }({\mathit{x}}^{(i)}))]+\frac{\lambda }{2m}\sum _{i=1}^n{\theta }_j^2.$$

The learning algorithm has the same expression as that of the regularized linear regression.

Neural networks

When the model has too many features, i.e., the dimension of

$\mathit{x}$ is big, the computational complexity of the linear and logistic regressions becomes huge. This is the place where neural network comes to play a role.

First of all, we may ask why the neural networks are so powerful. The answer to this question lies in the fact that the neural network can approximate any function with any desirable satisfaction, which has been proven mathematically, that is,

Suppose we're given a [continuous] function

$f(x)$ which we'd like to compute to within some desired accuracy

$ϵ>0$. The guarantee is that by using enough hidden neurons we can always find a neural network whose output

$g(x)$ satisfies:

$$|g(x)-f(x)|<ϵ$$

for all input

$x$. In other words, the approximation will be good to within the desired accuracy for every possible input.
–- Michael Nielsen, Neural networks and deep learning^[4]

Model representation

Biological neurons:

Neural networks:
The neural networks consists of many layers of neurons, and each neutron (or activation units) takes some features as input and provides an output according to a learning model. Below is a sigmoid activation function, or a single neuron. In neural networks, the parameters are also referred to as weights.

For a neural network shown in the figure below, the first layer is called input layer, the last layer output layer, and the middle layer hidden layer. In each layer there is a bias unit.

Forward propagation

In order to represent the hypothesis of the neural networks, we introduce the following notations:

$a_i^{(j)}$: the

$i^{th}$ activation unit in the

$j^{th}$ layer;

${\mathrm{\Theta }}^{(j)}$: the matrix of weights controlling function mapping from layer

$j$ to layer

$j+1$; its size is

$s_{j+1}\times (s_j+1)$, where

$s_j$ and

$s_{j+1}$ are the number of units in the

$j^{th}$ and

$j^{th}+1$ layer, respectively.

In the above example,

$$\begin{array}{rl}{a}_1^{(2)}& =g({\mathrm{\Theta }}_{10}^{(1)}{x}_0+{\mathrm{\Theta }}_{11}^{(1)}{x}_1+{\mathrm{\Theta }}_{12}^{(1)}{x}_2+{\mathrm{\Theta }}_{13}^{(1)}{x}_3),\\ a_2^{(2)}& =g({\mathrm{\Theta }}_{20}^{(1)}{x}_0+{\mathrm{\Theta }}_{21}^{(1)}{x}_1+{\mathrm{\Theta }}_{22}^{(1)}{x}_2+{\mathrm{\Theta }}_{23}^{(1)}{x}_3),\\ a_3^{(2)}& =g({\mathrm{\Theta }}_{30}^{(1)}{x}_0+{\mathrm{\Theta }}_{31}^{(1)}{x}_1+{\mathrm{\Theta }}_{32}^{(1)}{x}_2+{\mathrm{\Theta }}_{33}^{(1)}{x}_3),\end{array}$$

and

$$h_{\mathrm{\Theta }}(\mathit{x})=g({\mathrm{\Theta }}_{10}^{(2)}{a}_0^{(2)}+{\mathrm{\Theta }}_{11}^{(2)})a_1^{(2)}+{\mathrm{\Theta }}_{12}^{(2)}{a}_2^{(2)}+{\mathrm{\Theta }}_{13}^{(2)}{a}_3^{(2)}).$$

We can vectorize the representation as follows. Let

$$\begin{array}{r}\mathit{x}=\left[\begin{array}{c}{x}_0\\ x_1\\ x_2\\ x_3\end{array}\right],{\mathit{z}}^{(2)}=\left[\begin{array}{c}{z}_1^{(2)}\\ z_2^{(2)}\\ z_3^{(2)}\end{array}\right],{\mathit{z}}^{(2)}={\mathrm{\Theta }}^{(1)}\mathit{x},{\mathit{a}}^{(2)}=g({\mathit{z}}^{(2)}),\end{array}$$

and let

$${\mathit{z}}^{(3)}={\mathrm{\Theta }}^{(2)}{\mathit{a}}^{(2)},h_{\mathrm{\Theta }}(\mathit{x})=a_1^{(3)}=g({\mathit{z}}^{(3)}).$$

The units

${\mathit{a}}^{(j)}$ in the hidden layers can be viewed as the newly evolved features from the origin features

$\mathit{x}$.

Cost function

The neural network can be divided into binary classification and multi-class classification.

In the neural network, the output could be a vector with dimension

$K$, that is,

$h_{\mathrm{\Theta }}(\mathit{x})\in {\mathbb{R}}^K$. We denote the

$k^{th}$ output as

$(h_{\mathrm{\Theta }}(\mathit{x}){)}_k$.

In analogy to the cost function of logistic regression, the cost function of neural network can be written as

$$\begin{array}{rl}J(\mathrm{\Theta })=& -\frac{1}{m}\sum _{i=1}^m\sum _{k=1}^K(y_k^{(i)}\log (h_{\mathrm{\Theta }}({\mathit{x}}^{(i)}){)}_k+(1-y_k^{(i)})\log (1-(h_{\mathrm{\Theta }}({\mathit{x}}^{(i)}){)}_k))\\ & +\frac{\lambda }{2m}\sum _{l=1}^{L-1}\sum _{i=1}^{s_l}\sum _{j=1}^{s_{l+1}}({\mathrm{\Theta }}_{ji}^{(l)}{)}^2.\end{array}$$

(Note

$m$ denotes the total number of training samples and

$K$ denotes the total number of classifiers.)

The cost function above is a summation of two parts: the first is a summation of the difference between the output of hypothesis and the real value from training sample for each class, and the second is a summation of the components of the matrix of weights for all layers except for the bias terms.

Back propagation

Understand from a simple case

Note: In this section the notations are different from that are adopted by Andrew Ng.

To help to understand what back propagation is, let us start with the simplest case where there is only one neuron in each layer and no regularization terms.

The following derivations are from the video tutorial by 3BLUE1BROWN^[5].

Another excellent material about back propagation algorithm can be found on this page^[6]

From the forward propagation we know that, given a training sample

$(x,y)$, the error between the output

$h_{\theta }(x)$ and the real value

$y$, or the cost function, is

$C(w_1,b_1,w_2,b_2,w_3,b_3)$, where

$w_i$ and

$b_i$ are, respectively, the weight and bias associated with the function mapping from layer

$i$ to layer

$i+1$. And we try to minimize the value of

$C$ by tuning the values of

$w_i$,

$b_i$ according to some algorithm we will discuss about next.

First of all, let us only consider the last two layers and see how the value of cost function,

$C_0$, is affected by the weight

$w^{(L)}$, bias

$b^{(L)}$, and the value of activation unit

$a^{(L-1)}$ from previous layer.

According to the chain rule, we have

$$\frac{\partial C_0}{\partial w^{(L)}}=\frac{\partial C_0}{\partial a^{(L)}}\frac{\partial a^{(L)}}{\partial z^{(L)}}\frac{\partial z^{(L)}}{\partial w^{(L)}}.$$

(We understand

$\partial C_0$ as the change in

$C_0$ due to a slight change of

$\partial w^{(L)}$ in

$w^{(L)}$.)

Since

$$\begin{array}{rl}\frac{\partial z^{(L)}}{\partial w^{(L)}}& =a^{(L-1)},\\ \frac{\partial a^{(L)}}{\partial z^{(L)}}& ={\sigma }^{\prime }\left(z^{(L)}\right),\end{array}$$

we have

$$\frac{\partial C_0}{\partial w^{(L)}}=a^{(L-1)}{\sigma }^{\prime }\left(z^{(L)}\right)\frac{\partial C_0}{\partial a^{(L)}}.$$

Similarly,

$$\begin{array}{rl}\frac{\partial C_0}{\partial b^{(L)}}& ={\sigma }^{\prime }\left(z^{(L)}\right)\frac{\partial C_0}{\partial a^{(L)}},\\ \text{color}red\frac{\partial C_0}{\partial a^{(L-1)}}& =w^{(L)}{\sigma }^{\prime }\left(z^{(L)}\right)\text{color}red\frac{\partial C_0}{\partial a^{(L)}}.\end{array}$$

Now we are ready to study the change of

$C_0$ due to the changes of weight

$w^{(L-1)}$, bias

$b^{(L-1)}$, and activation unit value

$a^{(L-2)}$, where the idea of back propagation comes in.

Again, by chain rule we have

$$\begin{array}{rl}\frac{\partial C_0}{\partial w^{(L-1)}}& =\text{color}red\frac{\partial C_0}{\partial a^{(L-1)}}\frac{\partial a^{(L-1)}}{\partial z^{(L-1)}}\frac{\partial z^{(L-1)}}{\partial w^{(L-1)}}\\ & =a^{(L-2)}{\sigma }^{\prime }\left(z^{(L-1)}\right)\text{color}red\frac{\partial C_0}{\partial a^{(L-1)}},\\ \frac{\partial C_0}{\partial b^{(L-1)}}& =\text{color}red\frac{\partial C_0}{\partial a^{(L-1)}}\frac{\partial a^{(L-1)}}{\partial z^{(L-1)}}\frac{\partial z^{(L-1)}}{\partial b^{(L-1)}}\\ & ={\sigma }^{\prime }\left(z^{(L-1)}\right)\text{color}red\frac{\partial C_0}{\partial a^{(L-1)}},\\ \text{color}red\frac{\partial C_0}{\partial a^{(L-2)}}& =\text{color}red\frac{\partial C_0}{\partial a^{(L-1)}}\frac{\partial a^{(L-1)}}{\partial z^{(L-1)}}\frac{\partial z^{(L-1)}}{\partial a^{(L-2)}}\\ & =w^{(L-1)}{\sigma }^{\prime }\left(z^{(L-1)}\right)\text{color}red\frac{\partial C_0}{\partial a^{(L-1)}}.\end{array}$$

We can move on until to find the derivatives of

$C_0$ with respect to the weight

$w^{(1)}$ and

$b^{(1)}$ controlling function mapping from the first layer to the second. With all the derivatives of

$C_0$ with respect to

$w_i$ and

$b_i$, we are able to update them using the gradient descent method to minimize

$C_0$.

That is,

$$\begin{array}{rl}{w}_i& \leftarrow w_i-\alpha \frac{\partial C_0}{\partial w_i},\\ b_i& \leftarrow b_i-\alpha \frac{\partial C_0}{\partial b_i}.\end{array}$$

The above derivation is for neural network with only one neuron in each layer and for only one training sample. For the neural network composed of multiple neurons in each layer and trained by a set of data, the expressions become complicated but the core idea remains the same.

Algorithm

Recall for a complicate neural network trained by a large data set, we need to minimize the cost function

$J(\mathrm{\Theta })$ which involves computing the derivative

$\partial J(\mathrm{\Theta })/\partial {\mathrm{\Theta }}_{ij}^{(l)}$. Once again we note

$l\in \{1,2,...,L-1\}$ is the layer number,

$i\in \{1,2,...,s_j\}$, and

$j\in \{1,2,...,s_{j+1}\}$, where

$s_j$ and

$s_{j+1}$ are the number of activation units in the

$j^{th}$ and

$j^{th}+1$ layer, respectively.

As an example, we consider a neural network with 4 layers shown in figure below. The error between the output of hypothesis and the real value in the last layer is

$${\delta }_j^{(4)}=a_j^{(4)}-y_j,\text{or}{\mathit{\delta }}^{(4)}={\mathit{a}}^{(4)}-\mathit{y}.$$

We denote the "error" of unit

$j$ in layer

$l$ as

${\delta }_j^{(l)}:=\frac{\partial J}{\partial z_j^{(l)}}$.

Then we can compute the "error" in the previous layers in a fashion of backward propagation. That is,

$$\begin{array}{rl}{\mathit{\delta }}^{(3)}& =({\mathrm{\Theta }}^{(3)}{)}^{\text{T}}{\mathit{\delta }}^{(4)}.\ast g^{\prime }({\mathit{z}}^{(3)}),\\ {\mathit{\delta }}^{(2)}& =({\mathrm{\Theta }}^{(2)}{)}^{\text{T}}{\mathit{\delta }}^{(2)}.\ast g^{\prime }({\mathit{z}}^{(2)})\end{array}$$

The symbol ".*" denotes the element-wise multiplication of matrices, also known as the Hadamard product^[7]. Recall

${\mathit{z}}^{(3)}={\mathrm{\Theta }}^{(2)}{\mathit{a}}^{(2)}$ and

${\mathit{z}}^{(2)}={\mathrm{\Theta }}^{(1)}{\mathit{a}}^{(1)}$.

It can be shown that

$g^{\prime }({\mathit{z}}^{(i)})={\mathit{a}}^{(i)}.\ast (\mathbf{1}-{\mathit{a}}^{(i)})$.

Proof

Recall that

$$g({\mathit{z}}^{(l)})=\frac{1}{1+e^{-{\mathit{z}}^{(l)}}}$$

By taking the derivative, we have

$$\begin{array}{rl}{g}^{\prime }({\mathit{z}}^{(l)})& =\frac{\partial g}{\partial {\mathit{z}}^{(l)}}\\ & =\frac{1}{1+e^{-{\mathit{z}}^{(l)}}}.\ast (1-\frac{1}{1+e^{-{\mathit{z}}^{(l)}}})\\ & =g({\mathit{z}}^{(l)}).\ast (1-g({\mathit{z}}^{(l)}))\\ & ={\mathit{a}}^{(l)}.\ast (1-{\mathit{a}}^{(l)}).\end{array}$$

It can be further shown that when ignoring regularization (

$\lambda =0$), we have

$$\frac{\partial J(\mathrm{\Theta })}{\partial {\mathrm{\Theta }}_{ij}^{(l)}}=a_j^{(l)}{\delta }_i^{(l+1)}.$$

The proof can be found on this page^[8] and this page^[9].

I repeated the proof procedure in this note^[10].

---

1. https://www.coursera.org/learn/machine-learning ↩︎

2. http://neuralnetworksanddeeplearning.com/chap2.html ↩︎

3. https://en.wikipedia.org/wiki/Cross_entropy ↩︎

4. http://neuralnetworksanddeeplearning.com/chap4.html ↩︎

5. https://www.youtube.com/watch?v=tIeHLnjs5U8 ↩︎

6. https://en.wikipedia.org/wiki/Hadamard_product_(matrices) ↩︎

7. https://mc.ai/a-beginners-guide-to-deriving-and-implementing-backpropagation/ ↩︎

8. https://blog.innovea.tech/https-medium-com-sebastien-attia-cheat-sheet-on-neural-networks-1-30735616584a ↩︎

9. https://stats.stackexchange.com/questions/94387/how-to-derive-errors-in-neural-network-with-the-backpropagation-algorithm ↩︎

10. https://hackmd.io/@wldeng/back-propagation ↩︎