Machine Learning - Basics

1. Introduction: Linear Classifier

1.1 Training Data

Training Data are data points, and usually their labels are given in advance

• We have $i$$i$ data points each in the form $x^{(i)}$$x^{(i)}$

• Each Data Point has a feature vector containing $d$$d$ features in the form $x_d^{(i)}$$x^{(i)}_{d}$

• Each Data Point is associated with label value in the form $y^{(i)}$$y^{(i)}$

Mathematically, Training Data with $n$$n$ data points ($D_n$$D_n$) is defined as the following

You can set Label Value $y^{(i)}$$y^{(i)}$ to whatever you favor, the above binary labeling method is just an arbitrary example.

Assume for each data point, there is only 2 features ( $d=2$$d=2$ ) , that is

We could visualize the provided training data, where we have

• 2 axes $x_1/x_2$$x_1/x_2$ to represent features

  TIP: $x_1/x_2$$x_1/x_2$ actually means $x_1^{(i)}/x_2^{(i)}$$x_1^{(i)}/x_2^{(i)}$

• colored "$+/-$$+/-$" signs to represent labeled values

 

 

 

1.2 Hypothesis

Hypothesis is the resulted model yielded after learning from the training data

Or we could also say it is a way to go from data to labels

For the "Hypothesis" here, we actually mean a way to label NEW data points, it is a function that takes in a couple of features, and then return a label...if we adopt the example above, then its hypothesis $h$$h$ should be

Of course, you can also pass the data points in training data into $h$$h$ to do testings...What I imply here is that $h(x^{(i)})$$h(x^{(i)})$ might not give the same value as $y^{(i)}$$y^{(i)}$!

Hypothesis Class $H$$H$ is the set of all hypotheses: $h\in H$$h \in H$

 

 

 

1.3 Basics

1.3.1 Hypothesis Class

An example of hypothesis class for linear classifier is

• $H$$H$: All hypotheses that label $+1$$+1$ on one side of a line and $-1$$-1$ on the other side

The following two lines both represent hypotheses with $H$$H$

• Data points in green shadow are predicted to be $+1$$+1$

• Data points in red shadow are predicted to be $-1$$-1$

TIP: The label of the two axes actually means $x_1^{(i)}$$x_1^{(i)}$ and $x_2^{(i)}$$x_2^{(i)}$

If we test both of them with the labeled data points in the training data, the hypothesis on the left is terribly awful...

 

 

1.3.2 Math :Vector Projection

This is essential for 1.3.3

The Dot Product of two vectors $a$$a$ and $b$$b$ is defined as below, where $\theta$$\theta$ is the angle between $a$$a$ and $b$$b$

The amount of projection of Vector $a$$a$ on Vector $b$$b$ in the graph below is denoted as Scalor $l$$l$

We could induce the formula for vector projection with

 

 

1.3.3 Math: Hyperplane

The "line", or the Linear Classifier Hyperplane could be represented using one single vector $\theta$$\theta$ in the Feature Space

Hyperplane is always 1-Dimension lower than the the space dimension (leave one dimension to do classification)

• The hyperplane in the 2-D feature space below is 1-D, which is a line

• The hyperplane in the 3-D feature space would be 2-D

• ... ...

Notation in the graph:

• $\theta ,x^{(i)}\in {\mathbb{R}}^d$$\theta, x^{(i)} \in \mathbb{R}^d$

  Vectors, $d=2$$d=2$ in the case above, but the theory applies to higher dimensions

• $b\in \mathbb{R}$$b\in \mathbb{R}$

  Scalor, the amount of $x^{(i)}$$x^{(i)}$ projected onto $\theta$$\theta$

The amount of this projection ($b$$b$) could be calculated using the equation in the graph: dot product of the two vectors, divided by the length of $\theta$$\theta$. We can also check the dimensions:

Just because $b$$b$ is a PROJECTION, we could see that the above equation gives exactly the SAME result for EVERY $x^{(i)}$$x^{(i)}$ on the red dotted line perpendicular to $\theta$$\theta$ in the graph below

[ !! WARNING !! ] For the convenience of discussion, we could consider the projection onto the opposite direction of $\theta$$\theta$, and denote the magnitude of this projection with $a$$a$

and therefore the signed distance is $-a$$-a$

The Hyperplane represented by the red dotted line could be expressed with the following equation

If we make $a\Vert \theta \Vert ={\theta }_0$$a\norm{\theta} = \theta_0$, then it would became:

 

 

1.3.4 Math: Point-to-Hyperplane Distance

Q: What is the Signed Distance from a Hyperplane to an arbitrary point $x^{\ast }$$x^*$ in 2-D space?

The purple distance in the graph is what we want, and what we need to do is just to subtract the distance between hyperplane and origin from the amount of projection of $x^{\ast }$$x^*$ onto $\theta$$\theta$

Tip: If the hyperplane is below the origin, as in the last picture of 1.3.3, then we need to change notation of $b$$b$ to $-a$$-a$, but they have the same equation (remember that $a$$a$ is the magnitude and $-a$$-a$ is the Signed Distance)

$$b=-a=\frac{-{\theta }_0}{\Vert \theta \Vert }$$

• When Hyperplane is above origin

  $$\begin{array}{rl}\frac{{\theta }^T{x}^{(i)}}{\Vert \theta \Vert }& =b\\ {\theta }^T{x}^{(i)}\underset{+{\theta }_0}{\underbrace{-b\Vert \theta \Vert }}& =0\\ -b\Vert \theta \Vert & ={\theta }_0\\ b& =\frac{-{\theta }_0}{\Vert \theta \Vert }\end{array}$$

• When Hyperplane is below origin

  $$\begin{array}{rl}\frac{{\theta }^T{x}^{(i)}}{\Vert \theta \Vert }& =-a\\ {\theta }^T{x}^{(i)}+\underset{{\theta }_0}{\underbrace{a\Vert \theta \Vert }}& =0\\ a\Vert \theta \Vert & ={\theta }_0\\ -a& =\frac{-{\theta }_0}{\Vert \theta \Vert }\end{array}$$

 

 

1.3.5 Definition of Linear Classifier

With the Hypothesis Class and "Line" Definition, we could derive the full definition of a hypothesis of Linear Classifier

where $\theta ,{\theta }_0$$\theta, \theta_0$ are parameters

 

 

 

1.4 Loss Evaluation

1.4.1 Loss Function $L(g,a)$$L(g, a)$

$L$$L$ determines the loss of data points, could be single, could be plural

$g=guess$$g = guess$ and $a=actual$$a = actual$

You can choose whatever rule is appropriate for your data points

• Ex. 0-1 Loss

  Very Classic, Very Common, Very Boring...

  $$\begin{array}{c}L(g,a)=\{\begin{array}{ll}0& \text{if }g=a\\ 1& else\end{array}\end{array}$$

• Ex. Asymmetric Loss

  The Loss value depends on the case of deviation between $g$$g$ and $a$$a$

  $$\begin{array}{c}L(g,a)=\{\begin{array}{ll}1& \text{if }g=1,a=-1\\ 100& \text{if }g=-1,a=1\\ 0& else\end{array}\end{array}$$

  For example, if the model is guessing whether the patient is sick, $-1$$-1$ indicates healthy and $1$$1$ indicates not

  • If you finds someone sick ( $g=1$$g=1$ ) but he's not ( $a=-1$$a=-1$ ), then he might just have to do some useless checkings, not a very seriously consequence, so the loss could just be small as $1$$1$

  • But if you find someone healthy ( $g=-1$$g=-1$ ) but he's not ( $a=1$$a=1$ ), then...Well, 100 is a very fair loss value

 

 

1.4.2 Training Error

Assume we have $n$$n$ data points in Training Data, then Training Error ${\mathrm{E}}_n(h)$$\Epsilon_n(h)$ is

• We prefer hypothesis $h_a$$h_a$ to $h_b$$h_b$ if ${\mathrm{E}}_n(h_a)<{\mathrm{E}}_n(h_b)$$\Epsilon_n(h_a) < \Epsilon_n(h_b)$

 

 

1.4.3 Test Error

Assume we have $n^{\prime }$$n'$ new data points for testing, then Test Error $\mathrm{E}(h)$$\Epsilon(h)$ is

Almost the same as Training Error, the difference is just the index

 

 

 

1.5 Random Linear Classifier

Clumsy, but not so clumsy. Here comes's the pseudo-code

Hyperparameter $k$$k$ is the times of iterations, or the number of sets of random parameters $(\theta ,{\theta }_0)$$(\theta, \theta_0)$ to generate

• Cons

  Not very efficient because parameter sets are generated at random, and you might have to test some very crazy hypotheses

• Pros

  In one round of training, you'll always get a better $h$$h$ returned as $k$$k$ increases

  I won't say that with multiple rounds of training...

  • First Training, $k=1$$k=1$

    You have chances (although extremely small) to hit the optimal parameter set in the only one iteration

  • Second Training, $k=2$$k=2$

    It's highly possible that you get two sets of insanely awful parameters...and get a huge loss

 

 

 

1.6 Perceptron

1.6.1 Algorithm

This algorithm is more organized with less randomness (I guess), pseudo-code here

Hyperparameter $\tau$$\tau$ is the times to iterate through all the $n$$n$ data points in the Training Data $D_n$$D_n$

The key component here is the evaluation & update in the nested for-loop, where $a$$a$ is actual label value, $g$$g$ is guess label value

• Evaluation

  $$\underset{a}{\underbrace{y^{(i)}}}\underset{g}{\underbrace{({\theta }^T{x}^{(i)}+{\theta }_0)}}\le 0$$

  The evaluation would be true when at the initial case, or when actual value does not corresponds to guess value

  Tip: $a,g\in \{+1,-1\}$$a, g \in \{+1, -1\}$, and $\theta ,{\theta }_0$$\theta, \theta_0$ are zero when initialized

  • Initial Case

    $$\begin{array}{rl}{y}^{(i)}({\theta }^T{x}^{(i)}+{\theta }_0)& =y^{(i)}([0,...,0{]}^T\cdot x^{(i)}+0)\\ & =y^{(i)}\cdot 0\\ & =0\end{array}$$

  • Actual $\ne$$\not=$ Guess

    $$\begin{array}{rl}{y}^{(i)}({\theta }^T{x}^{(i)}+{\theta }_0)& =(+1)\cdot (-1)\text{ or }(-1)\cdot (+1)\\ & =-1\end{array}$$

  When all the predictions made on the training data set are correct, that means

  $$y^{(i)}={\theta }^T{x}^{(i)}+{\theta }_0$$

  And then the evaluation becomes

  $$\begin{array}{rl}{y}^{(i)}({\theta }^T{x}^{(i)}+{\theta }_0)& =(+1)\cdot (+1)\text{ or }(-1)\cdot (-1)\\ & =1>0\end{array}$$

• Update

  We update the value of $\theta$$\theta$ and ${\theta }_0$$\theta_0$ when the guess label value of any data point does not equals to its actual label value

  $$\begin{array}{c}{\theta }_{neo}=\theta +y^{(i)}{x}^{(i)}\\ {\theta }_{0,neo}={\theta }_0+y^{(i)}\end{array}$$

  Then for the next data point, the evaluation equation would become

  $$\begin{array}{rl}{y}^{(i)}({\theta }_{neo}^T{x}^{(i)}+{\theta }_{0,neo})& =y^{(i)}[(\theta +y^{(i)}{x}^{(i)}{)}^T{x}^{(i)}+({\theta }_0+y^{(i)})]\\ & =y^{(i)}({\theta }^T{x}^{(i)}+{\theta }_0)+\underset{=1}{\underbrace{(y^{(i)}{)}^2}}(\underset{={\Vert x^{(i)}\Vert }^2}{\underbrace{x^{(i)T}{x}^{(i)}}}+1)\\ & =y^{(i)}({\theta }^T{x}^{(i)}+{\theta }_0)+({\Vert x^{(i)}\Vert }^2+1)\end{array}$$

  The evaluation formula with updated $\theta$$\theta$ and ${\theta }_0$$\theta_0$ is "original evaluation + a strictly positive term"

  $${\Vert x^{(i)}\Vert }^2\ge 0⟶{\Vert x^{(i)}\Vert }^2+1>0$$

  So this update is definitely trying to push the evaluation towards false, moving the parameters $\theta$$\theta$ and ${\theta }_0$$\theta_0$ to achieve a more correct classification

 

 

1.6.2 Linear Separability

A set of training data set $D_n$$D_n$ is Linearly Separable if there exists $\theta ,{\theta }_0$$\theta, \theta_0$ such that for $i\in \{1,2,...,n\}$$i\in\{1, 2,...,n\}$ it satifies any of the below

• $y^{(i)}({\theta }^T{x}^{(i)}+{\theta }_0)>0$$y^{(i)}(\theta^Tx^{(i)}+\theta_0) > 0$

• $h(x^{(i)};\theta ,{\theta }_0)=y^{(i)}$$h(x^{(i)}; \theta, \theta_0)=y^{(i)}$

• ${\mathrm{E}}_n(h)=0$$\Epsilon_n(h)=0$

Well, they are actually completely equivalent...

The data set in the picture below is definitely not linearly separable

 

 

1.6.3 Margin of Training Data

Margin of training data set $D_n$$D_n$ with respect to the hyperplane defined by $\theta ,{\theta }_0$$\theta, \theta_0$ is the minimum of the distances from $n$$n$ data points to the hyperplane

(Point-to-Hyperplane Distance - see 1.3.4)

This equation would be positive if and only if all data points are correctly predicted

if any data point is incorrectly classified, $y^{(i)}$$y^{(i)}$ and $\frac{{\theta }^T{x}^{(i)}+{\theta }_0}{\Vert \theta \Vert }$$\frac{\theta^Tx^{(i)}+\theta_0}{\norm{\theta}}$ will have different signs, and their product would be negative, therefore guarantees the $Margin$$Margin$ to be negative (the equation returns the minimum product)

 

 

1.6.4 Perceptron Convergence Theorem

Assume:

• Hypothesis Class $H$$H$: classifiers with hyperplanes passing through the origin (${\theta }_0=0$$\theta_0=0$)

  (way to achieve: see 1.6.5)

• There exists ${\theta }^{\ast }$$\theta^*$ and $\gamma >0$$\gamma > 0$ such that $y^{(i)}(\frac{{\theta }^{\ast T}{x}^{(i)}}{\Vert \theta \Vert })\ge \gamma$$y^{(i)}(\frac{\theta^{*T}x^{(i)}}{\norm{\theta}})\geq\gamma$ for $i\in \{1,2,...,n\}$$i\in\{1, 2, ..., n\}$

  we have a minimum value for Point-to-Hyperplane distance

• All data points have a magnitude bounded to some value $\Vert x^{(i)}\Vert \le R$$\norm{x^{(i)}} \leq R$ for $i\in \{1,2,...,n\}$$i\in\{1, 2, ..., n\}$

  we have a maximum range for data points

Conclusion:

• Then the perceptron algorithm would make at most $(\frac{R}{\gamma }{)}^2$$(\frac{R}{\gamma})^2$ updates to $\theta$$\theta$ and ${\theta }_0$$\theta_0$, then the Training Error of this Hypothesis would be 0

 

 

1.6.5 Classifier Offset

We could expand the Feature Space to "get rid of" the offset ${\theta }_0$$\theta_0$ in the hyperplane definition

• Hyperplane with Offset

  $\theta \in {\mathbb{R}}^d$$\theta \in \mathbb{R}^d$, $x^{(i)}\in {\mathbb{R}}^d$$x^{(i)}\in \mathbb{R}^d$

  $$x^{(i)}:{\theta }^T{x}^{(i)}+{\theta }_0=0$$

  Notice that ${\theta }_0={\theta }_0\times 1$$\theta_0=\theta_0 \times1$

• Hyperplane without Offset

  we could move ${\theta }_0$$\theta_0$ and 1 into the feature space of $\theta$$\theta$ and $x$$x$

  ${\theta }_{neo}\in {\mathbb{R}}^{d+1}$$\theta_{neo} \in \mathbb{R}^{d+1}$, $x_{neo}\in {\mathbb{R}}^{d+1}$$x_{neo} \in \mathbb{R}^{d+1}$

  • ${\theta }_{neo}=[{\theta }_1,{\theta }_2,...,{\theta }_d,{\theta }_0{]}^T$$\theta_{neo}=[\theta_1, \theta_2,...,\theta_d, \theta_0]^T$

  • $x_{neo}^{(i)}=[x_1^{(i)},x_2^{(i)},...,x_d^{(i)},1{]}^T$$x^{(i)}_{neo}=[x^{(i)}_{1}, x^{(i)}_{2}, ..., x^{(i)}_{d}, 1]^T$

  And it is exactly the same equation as the one with offset (we just hide it)

  $${\theta }_{neo}^T{x}_{neo}^{(i)}={\theta }^T{x}^{(i)}+{\theta }_0$$

  With the above modification, we have the new definition for Hyperplane as below

  $$x_{neo[1:d]}^{(i)}:{\theta }_{neo}^T{x}_{neo}^{(i)}=0$$

 

 

 

1.7 Algorithm Evaluation

1.7.1 Nonlinear Boundary

For data sets that are not linearly separable, we could use polynomial to create nonlinear boundaries to do classification

One way to implement these nonlinear boundaries is to use Taylor Expansion to approximate a smooth function, below is the table of term in the Taylor Polynomial when each data point has $d$$d$ features

Usually, a $k^{th}$$k^{th}$ order Taylor Polynomial could create a boundary for data separated into $k$$k$ groups like below

• $k=2$$k=2$ for the donut-shape example at the top

• $k=3$$k=3$ for the weird shape example at the bottom

As you see, classifiers of training data in 2D-space could be expressed as hyperplanes in 3D-space, this not only applies to nonlinear boundaries, but also linear boundaries

Mathematically speaking, this kind of boundsare just nonlinear in $x^{(i)}$$x^{(i)}$, but still linear in $\theta$$\theta$, with $x^{(i)}$$x^{(i)}$ in the equation

They are still linear classifiers!

• Classifier of Linear Boundary - Example on the top

  Hyperplane expressed by

  $$z={\theta }^T{x}^{(i)}+{\theta }_0$$

  where $x^{(i)}=[x_1^{(i)},x_2^{(i)}{]}^T$$x^{(i)} = [x^{(i)}_1, x^{(i)}_2]^T$

• Classifier of Nonlinear Boundary - Example at the bottom

  Hyperplane expressed by

  $$z={\theta }^T{\varphi }^{(i)}(x)+{\theta }_0$$

  where ${\varphi }^{(i)}(x)=[x_1^{(i)},x_2^{(i)},x_1^{(i)2},x_2^{(i)2},x_1^{(i)}{x}_2^{(i)}{]}^T$$\phi^{(i)}(x)=[x^{(i)}_1, x^{(i)}_2, x^{(i)2}_1, x^{(i)2}_2, x^{(i)}_1x^{(i)}_2]^T$

 

 

1.7.2 Overfitting

Actually we could apply those super-flexible functions (or nonlinear boundaries) in 1.7.1 to any data set, but there are some extreme cases where you don't want such superiority...

Training Error would be 0 with the boundary we develop above, but are you sure this is what you want?

This is Overfitting

I'm 99% sure you can't generalize this boundary to new data points in the tests...

 

 

1.7.3 Cross Validation

This is a way to prevent overfitting

1. Shuffle the training data $D_n$$D_n$, then divide it into $k$$k$ groups: $D_{n,1},D_{n,2},...,D_{n,k}$$D_{n,1}, D_{n,2}, ..., D_{n,k}$

   

2. Repeat the following steps $k$$k$ times

   1. Train your $h_i$$h_i$ on all groups of $D_n$$D_n$ except one group $D_{n,i}$$D_{n,i}$

      The orange section of $D_n$$D_n$

   2. Test $h_i$$h_i$ on the group left, compute Test Error $\mathrm{E}(h_i,D_{n,i})$$\Epsilon(h_i, D_{n,i})$

      The blue section of $D_n$$D_n$

    

3. Compute average Test Error $\frac{1}{k}\sum _{i=1}^k\mathrm{E}(h_i,D_{n,i})$$\frac{1}{k}\sum^{k}_{i=1}\Epsilon(h_i, D_{n,i})$

! [WARNING] ! Do please shuffle the order of your data set, unless you want to train your $h$$h$ on some very biased group of data like the one in the grey box from the graph below

Trust me, you don't want this...

 

 

 

 

 

2. Feature Encoding

The following is an example data table before encoding

 

 

 

2.1 Numerical Data

Order & Differences of data values Does Matter

In the example data given above, resting heart rate, age, family income are numerical data

Although age does looks categorical or ordinal, by definition above, it's still numerical

Usually we just leave numerical data as they are, but...

 

 

2.1.1 Level of Detail

Please be careful when pre-processing the data...

When people dealing with "vague" data like age in the table above, they might do something like rounding "40s" to "45"

DON'T DO THAT unless you are sure this rounding is needed and would definitly not negatively impact the result

• One suggested practice is to just use "4" for "40s"

Gentle Remainder Again: Don't Do Anything Unnecessary

 

 

2.1.2 Data Standardization

Sometimes we need to visualize the data...Do you know what's gonna happen if we plot resting heart rate versus family income in the table above with their linear classifier?

You could find a linear classifier that works properly, it just looks like hell...

Solution: Standardize the data!

For numerical data, the simplist way is what we did to an arbitrary normal distribution to make it a standard normal distribution. The $d^{th}$$d^{th}$ feature in the data could be standardized to $z_d^{(i)}$$z^{(i)}_d$ as below

where ${\mu }_d$$\mu_d$ and ${\sigma }_d$$\sigma_d$ are the mean and the standard deviation of all $d^{th}$$d^{th}$ features in data set

 

2.2 Categorical Data

Order of data values Does Not Matter

In the example data given above, pain?, job, medicines are categorical data

 

 

2.2.1 Boolean Encoding

A typical way to convert something like "Yes/No", "True/False", for example

pain? $\in \{\text{Yes},\text{No}\}\to \{+1,-1\}$$\in \{\text{Yes}, \text{No}\} \rightarrow \{+1, -1\}$

You can also use $\{1,0\}$$\{1, 0\}$ depending on your need

 

 

2.2.2 One-Hot Encoding

Converting "Single Choice" data. Turn each category into a unique "$0/1$$0/1$ Feature", the feature become 1 when we "select" it, otherwise that bit would always be 0

Example: job

We could turn 5 jobs into 5 features: $j_1,j_2,j_3,j_4,j_5$$j_1, j_2, j_3, j_4, j_5$ where $j_i\in \{0,1\}$$j_i \in \{0, 1\}$

xxxxxxxxxx
 
6
 
 
 
 
 
 
 
 
1
 
*job*   [j1 j2 j3 j4 j5]
 
 
 
2
 
nurse   [1, 0, 0, 0, 0]
 
 
 
3
 
admin   [0, 1, 0, 0, 0]
 
 
 
4
 
doctor  [0, 0, 1, 0, 0]
 
 
 
5
 
teacher [0, 0, 0, 1, 0]
 
 
 
6
 
worker  [0, 0, 0, 0, 1]
 
 
 
 
 
 
 

If you want to group nurse and doctor together saying that they have some features in common, then you can consider Factored Encoding (see 2.2.3)

 

 

2.2.3 Factored Encoding

Converting "Multiple Choices" data, rather than "Single Choice" data like the job we discussed above, for example

Example: medicine

It seems like we have 4 different medicine selection, but in fact, it is just combinations of 2 kinds of medicine, and therefore we only have to deal with 2 features

xxxxxxxxxx
 
5
 
 
 
 
 
 
 
 
1
 
*selection*         [m1 m2]
 
 
 
2
 
pain                [1, 0]
 
 
 
3
 
pain & beta blocker [1, 1]
 
 
 
4
 
beta blocker        [0, 1]
 
 
 
5
 
none                [0, 0]
 
 
 
 
 
 
 

 

 

 

2.3 Ordinal Data

Order of data values Does Matter but Differences Does Not

Converting "Scales" like "Levels of Pain", "Levels of Agreement"

No example on the data table above, but we could provide one like this

This kind of feature encoding method is called "Thermometer Code" or "Unary Code"

 

 

 

2.4 Processed Data Example

The encoded and standardized example data table

 

 

 

 

 

3. Regression

3.1 Gradient Descent

3.1.1 Gradient

Gradient tells us the direction to increase "height of function" (at the axis of dependent variable) the most Mathematically, it is a vector of partial derivatives with respect to each of the variables, the Gradient of $J$$J$ with respect to $\mathrm{\Theta }$$\Theta$ is

Where parameter $\mathrm{\Theta }=\{{\mathrm{\Theta }}_1,{\mathrm{\Theta }}_2,...,{\mathrm{\Theta }}_m\}\in {\mathbb{R}}^m$$\Theta = \{\Theta_1, \Theta_2, ..., \Theta_m\} \in \mathbb{R}^m$

In the picture above, graph of the function $f(\mathrm{\Theta })$$f(\Theta)$ with $\mathrm{\Theta }\in {\mathbb{R}}^2$$\Theta \in \mathbb{R}^2$ is on the left hand side; another contour graph with top view for this function is on the right hand side, where the green arrow denotes the direction of gradient at the red dot.

 

 

3.1.2 Convex Function

A Real-Valued Function is Convex if the line segment of any two distinct points on the graph of this function lies completely above or on this graph

Two sets of examples are presented below

When a function is convex, it is easier to minimize

 

 

3.1.3 (Batch) Gradient Descent

When saying "Gradient Descent", this is the version we talk about

We are actually interested in how to minimize (instead of maximize) the function since talking about Descent; in terms of the contour graph in 3.1.1, the red arrow denotes the desired direction

And by going down the contour lines step by step, we could (probabily) reach the minimum of the function, the "bottom of the valley". The picture below shows the simplest process of gradient descent

Here comes the pseudo-code

• Parameters Explanation

  • ${\mathrm{\Theta }}_{init}=$$\Theta_{init} =$ Initial "Position"

  • ${\mathrm{\Theta }}^{(t)}=$$\Theta^{(t)}=$ Parameters for $f(\mathrm{\Theta })$$f(\Theta)$ at $t^{th}$$t^{th}$ Step

  • $f(\mathrm{\Theta })=$$f(\Theta)=$ Convex Function

  • ${\mathbf{\nabla }}_{\mathrm{\Theta }}f(\mathrm{\Theta })=$$\grad_{\Theta} f(\Theta)=$ Gradient of $f(\mathrm{\Theta })$$f(\Theta)$ with respect to $\mathrm{\Theta }$$\Theta$ as a Function

  • $\eta =$$\eta=$ Step Size

• Stop Condition

  You could choose different stop_conditions for the while loop here

  • Maximum Number of Iteration $T$$T$

    Always a good choice

  • $|f({\mathrm{\Theta }}^{(t)})-f({\mathrm{\Theta }}^{(t-1)})|\ge ϵ$$\abs{f(\Theta^{(t)})-f(\Theta^{(t-1)})} \geq \epsilon$

    stop when step difference of function value is small enough

  • $|{\mathrm{\Theta }}^{(t)}-{\mathrm{\Theta }}^{(t-1)}|\ge ϵ$$\abs{\Theta^{(t)}-\Theta^{(t-1)}} \geq \epsilon$

    stop when you can hardly "improve" the parameter set for your convex function

  • $\Vert {\mathbf{\nabla }}_{\mathrm{\Theta }}f({\mathrm{\Theta }}^{(t)})\Vert \ge ϵ$$\norm{\grad_{\Theta} f(\Theta^{(t)})} \geq \epsilon$

    stop when gradient is small enough

• Performance Theorem

  Based on the pseudo-code in 3.1.3, if select any $ϵ>0$$\epsilon >0$, then

  • Assume

    • $\eta$$\eta$ is sufficiently small

    • $f(\mathrm{\Theta })$$f(\Theta)$ is sufficiently smooth an d convex

    • $f(\mathrm{\Theta })$$f(\Theta)$ has at least one global optimum

      I mean minimum here

  • Conclusion

    If the code runs long enough, Gradient Descent will return a value within $ϵ$$\epsilon$ of global optimum $\mathrm{\Theta }$$\Theta$

 

 

3.1.4 Stochastic Gradient Descent

Sort of a "Drunk" Gradient Descent

If you look at how gradients are updated in (Batch) Gradient Descent 3.2.5 & 3.3.5, you shall see that we sum the gradients of the whole training data set, then take the average

In Stochastic Gradient Descent, we randomly select one data point at a time, and just look at its gradient. This would be noisier, but since we don't have to do summations, iterations become cheaper

Here's the pseudo-code for it

About changes in parameters

• $\eta (t)$$\eta(t)$ would be smaller as $t$$t$ gets larger

• ${\mathrm{\nabla }}_{\mathrm{\Theta }}{f}_i({\mathrm{\Theta }}^{(t-1)})$$\nabla_{\Theta} f_i(\Theta^{(t-1)})$ is the gradient of a single data point

[Note] In practice, SGD uses a small collection of data points, not just one, called minibatch

 

 

 

3.2 Logistic Regression

Common linear classifiers could only divide linearly separable data, but it has no idea on the uncertainty of $y^{(i)}$$y^{(i)}$, or to be more specific, linearly unseparable data, where different labeled values $y^{(i)}$$y^{(i)}$ are mixed up in some regions

For example, at what temperature would you wear a coat?

• $x^{(i)}\in \mathbb{R}$$x^{(i)} \in \mathbb{R}$ with only one feature: Temperature

• $y^{(i)}\in \mathbb{R}$$y^{(i)} \in \mathbb{R}$ is the probability of wearing a coat

The graph on the left hand side shows that someone will wear a coat when temperature is under a definite value bound, and will not when above. But the real life experience is that there is a certain range of temperature in which you are uncertain about if you need a coat, just like the graph on the right hand side.

• Definitely need a coat when under 10C

• Be 70% sure that you need a coat at 13C, but in some very sunny days, you don't

• Be 30% sure that you do not need a coat at 17C, but in some very rainy days, you do need

• Definitely do not need a coat when above 20C

The shape of the graph on the right is a Sigmoid/Logistic Function, or Linear Logistic Classifier

 

 

3.2.1 Logistic Function

• Definition

  $$\sigma (z)=\frac{1}{1+e^{-z}}$$

  

• Shifting/Scaling

  Add a scaling constant $\theta$$\theta$ and shifting constant ${\theta }_0$$\theta_0$ to the variable of Logistic Function

  $$\sigma (\theta z+{\theta }_0)=\frac{1}{1+e^{-(\theta z+{\theta }_0)}}$$

  Suppose we replace $z$$z$ with a multi-feature vector $x^{(i)}\in {\mathbb{R}}^d$$x^{(i)}\in \mathbb{R}^{d}$, then we would find something familiar...

  $$\sigma ({\theta }^T{x}^{(i)}+{\theta }_0)=\frac{1}{1+e^{-({\theta }^T{x}^{(i)}+{\theta }_0)}}$$

  If $d=2$$d=2$, then the graph of the function above would be the following

  

Tip: Logistic Function $\sigma (z)\in (0,1)$$\sigma(z) \in (0, 1)$ and it is not a classifier

 

 

3.2.2 Prediction Threshold

How to make prediction decision from $\{+1,-1\}$$\{+1, -1\}$ with Logistic Function?

• Default Practice

  The output of Logistic Function is Probability, so...

  • $+1$$+1$ if $Probability>0.5$$Probability>0.5$

  • $-1$$-1$ if $Probability\le 0.5$$Probability\leq 0.5$

  The value $0.5$$0.5$ above is the Prediction Threshold

• Simplification

  $$\begin{array}{rl}Probability& >0.5\\ \sigma ({\theta }^T{x}^{(i)}+{\theta }_0)& >0.5\\ \frac{1}{1+e^{-({\theta }^T{x}^{(i)}+{\theta }_0)}}& >0.5\\ e^{-({\theta }^T{x}^{(i)}+{\theta }_0)}& <1\\ {\theta }^T{x}^{(i)}+{\theta }_0& >0\end{array}$$

  The last equation should be very familiar to you (see 1.3.5). We could see the default hypothesis for Logistic Function is exactly the same as that for Linear Classifier!

  $$\begin{array}{c}h(x)=sgn({\theta }^T{x}^{(i)}+{\theta }_0)=\{\begin{array}{ll}+1& \text{if }{\theta }^T{x}^{(i)}+{\theta }_0>0\\ -1& \text{if }{\theta }^T{x}^{(i)}+{\theta }_0\le 0\end{array}\end{array}$$

 

 

3.2.3 NLL Loss

The loss function we define here is negative-log-likelihood (NLL). To be honest this is not a "Loss" Function, but a function that would help us learn a Linear Logistic Classifier

We know the output of logistic function is in $(0,1)$$(0,1)$, which is a probability, in our case, it is the probability that a data point is labeled as "$+1$$+1$", or the probability that you need a coat

Assume each data point are completely independent, then we could find the probability that the whole training data is properly labeled by multiplying the probability that each data point is properly labeled

• The probability that a data point is labeded as "$+1$$+1$" is denoted as $g^{(i)}$$g^{(i)}$

  $$g^{(i)}=\sigma ({\theta }^T{x}^{(i)}+{\theta }_0)$$

• The probability that data point is properly labeled is denoted as $P(x^{(i)})$$P(x^{(i)})$

  • if $y^{(i)}=+1$$y^{(i)}=+1$, then $P(x^{(i)})=g^{(i)}$$P(x^{(i)})=g^{(i)}$

  • if $y^{(i)}\ne +1$$y^{(i)}\not=+1$, then $P(x^{(i)})=1-g^{(i)}$$P(x^{(i)})=1-g^{(i)}$

We could find the probability that the whole training data is properly labeled as the equation below

Explanation for why we need negative-log-likelihood

• Q: Why logarithm?

  A: Calculating products would have some effect on the precision of results on the computer, so we would like to convert our formula from product $\prod$$\prod$ to summation $\sum$$\sum$

• Q: Why negative?

  Our objective is to maximize the probability that the whole training data is properly labeled, but we prefer to minimize by taking the negative sign

The Loss of Data (not NLL Loss) in general is defined as below

Tip: Logarithm Properties

• ${\log }_b(xy)={\log }_b(x)+{\log }_b(y)$$\log_{b}(xy)=\log_{b}(x)+\log_{b}(y)$

• ${\log }_b(x^p)=p{\log }_b(x)$$\log_{b}(x^p)=p\log_{b}(x)$

NLL Loss in the equation above is defined by the following ($g$$g$ is guess value and $a$$a$ is actual value)

You can use logarithm of any base

Default base value $=e$$=e$

For convenience, if $y^{(i)}\in \{0,1\}$$y^{(i)} \in \{0, 1\}$, the NLL Loss function could be defined more rigorously as

We could reorganize $L(data)$$L(data)$ to the following objective $J_{lr}(\mathrm{\Theta })$$J_{lr}(\Theta)$ to minimize

$lr=$$lr=$ logistic regression

$\mathrm{\Theta }=$$\Theta=$ parameters

(a multi-class version is available in Machine Learning - NN Special Topics 2.)

 

 

3.2.4 Overfitting & Regularizer

First of all, $J_{lr}(\mathrm{\Theta })=J_{lr}(\theta ,{\theta }_0)$$J_{lr}(\Theta)=J_{lr}(\theta, \theta_0)$ is Differentiable & Convex

This is a claim, not an assumption

Assume we want to train a linear logistic classifier for the training data below

Run the pseudo-code in 3.1.3 with the NLL Loss function defined in 3.2.3

• Gradient_Descent $({\mathrm{\Theta }}_{init},\eta ,J_{lr}(\mathrm{\Theta }),\mathrm{\nabla }f(\mathrm{\Theta }),ϵ)$$(\Theta_{init}, \eta, J_{lr}(\Theta), \nabla f(\Theta), \epsilon)$

Then we need to ask: How far should we go?

• The whole idea of NLL Loss is to increase the probability of the whole data set

• We can increase this probability by making the graph $g^{(i)}$$g^{(i)}$ steeper (see 3.2.3)

• So ideally, we will always get the graph at Step 114514 in the graph below in the end

We can plot the objective function and see what's happening (assume ${\theta }_0=0$$\theta_0=0$)

Value of NLL Loss will go down as $\theta$$\theta$ increases all the time

Even after some value of $\theta$$\theta$ in the positive axis, despite that the graph of the function would look like a horizontal line, its value is still decreasing

But being overly certain is pointless, we don't need it.

The solution is to add a Regularizer / Penalty $R(\theta )=\lambda {\Vert \theta \Vert }^2$$R(\theta)=\lambda\norm{\theta}^{2}$ with $\lambda \ge 0$$\lambda \geq 0$ that penalizes being overly certain, while still keep the objective $J_{lr}$$J_{lr}$ differentiable & convex

$R(\theta )$$R(\theta)$ is a quadratic function...a quadratic function is always convex

You could see its effect as below

 

 

3.2.5 Gradient Descent for Logistic Regression

We could set up our Logistic Regression Learning Algorithm based on the pseudo-code of gradient descent in 3.1.3

• Gradients

  we need to update all the parameters ($\mathrm{\Theta }=[\theta ,{\theta }_0]$$\Theta=[\theta, \theta_0]$) with respective gradients

  Tips:

  1. Default logarithm base value $=e$$=e$

  2. $g^{(i)}=\sigma ({\theta }^T{x}^{(i)}+{\theta }_0)$$g^{(i)}=\sigma(\theta^Tx^{(i)}+\theta_0)$

  3. Derivatives

     $\frac{d}{dx}\ln \left(x\right)=\frac{1}{x}$$\frac{d}{dx}\ln(x)=\frac{1}{x}$

     $\frac{d}{dx}\sigma (x)=\sigma (x)(1-\sigma (x))$$\frac{d}{dx}\sigma(x)=\sigma(x)(1-\sigma(x))$

  • Gradient of $\theta$$\theta$

    $$\begin{array}{rl}{\mathbf{\nabla }}_{\theta }{J}_{lr}(\mathrm{\Theta })& =\frac{1}{n}\sum _{i=1}^n\frac{\partial L_{nll}}{\partial \theta }+\frac{\partial }{\partial \theta }(\lambda {\Vert \theta \Vert }^2)\\ & =\frac{1}{n}\sum _{i=1}^n-[y^{(i)}\frac{1}{g^{(i)}}\cdot \frac{\partial g^{(i)}}{\partial \theta }+(1-y^{(i)})\frac{1}{1-g^{(i)}}\cdot \frac{\partial (1-g^{(i)})}{\partial \theta }]+2\lambda \theta \\ & =\frac{1}{n}\sum _{i=1}^n-[\frac{y^{(i)}}{g^{(i)}}-\frac{1-y^{(i)}}{1-g^{(i)}}]\cdot \frac{\partial g^{(i)}}{\partial \theta }+2\lambda \theta \\ & =\frac{1}{n}\sum _{i=1}^n-\frac{y^{(i)}-y^{(i)}{g}^{(i)}-g^{(i)}+y^{(i)}{g}^{(i)}}{g^{(i)}(1-g^{(i)})}\cdot g^{(i)}(1-g^{(i)})\cdot \frac{\partial }{\partial \theta }({\theta }^T{x}^{(i)}+{\theta }_0)+2\lambda \theta \\ & =\frac{1}{n}\sum _{i=1}^n-(y^{(i)}-g^{(i)})\cdot x^{(i)}+2\lambda \theta \end{array}$$

    Reorganize the equation, then we have the following gradient equation

    $${\mathbf{\nabla }}_{\theta }{J}_{lr}(\mathrm{\Theta })=\frac{1}{n}\sum _{n=1}^n[\sigma ({\theta }^T{x}^{(i)}+{\theta }_0)-y^{(i)}]x^{(i)}+2\lambda \theta$$

  • Gradient of ${\theta }_0$$\theta_0$

    $$\begin{array}{rl}{\mathbf{\nabla }}_{{\theta }_0}{J}_{lr}(\mathrm{\Theta })& =\frac{1}{n}\sum _{i=1}^n\frac{\partial L_{nll}}{\partial {\theta }_0}+\frac{\partial }{\partial {\theta }_0}(\lambda {\Vert \theta \Vert }^2)\\ & =\frac{1}{n}\sum _{i=1}^n-[y^{(i)}\frac{1}{g^{(i)}}\cdot \frac{\partial g^{(i)}}{\partial {\theta }_0}+(1-y^{(i)})\frac{1}{1-g^{(i)}}\cdot \frac{\partial (1-g^{(i)})}{\partial {\theta }_0}]\\ & =\frac{1}{n}\sum _{i=1}^n-[\frac{y^{(i)}}{g^{(i)}}-\frac{1-y^{(i)}}{1-g^{(i)}}]\cdot \frac{\partial g^{(i)}}{\partial {\theta }_0}\\ & =\frac{1}{n}\sum _{i=1}^n-\frac{y^{(i)}-y^{(i)}{g}^{(i)}-g^{(i)}+y^{(i)}{g}^{(i)}}{g^{(i)}(1-g^{(i)})}\cdot g^{(i)}(1-g^{(i)})\cdot \frac{\partial }{\partial {\theta }_0}({\theta }^T{x}^{(i)}+{\theta }_0)\\ & =\frac{1}{n}\sum _{i=1}^n-(y^{(i)}-g^{(i)})\cdot 1\end{array}$$

    Reorganize the equation, then we have the following gradient equation

    $${\mathbf{\nabla }}_{{\theta }_0}{J}_{lr}(\mathrm{\Theta })=\frac{1}{n}\sum _{n=1}^n[\sigma ({\theta }^T{x}^{(i)}+{\theta }_0)-y^{(i)}]$$

• Summary

  $$\begin{array}{rl}{J}_{lr}(\theta ,{\theta }_0)& =\frac{1}{n}\sum _{i=1}^n{L}_{nll}(\sigma ({\theta }^T{x}^{(i)}+{\theta }_0),y^{(i)})+\lambda {\Vert \theta \Vert }^2\\ {\mathbf{\nabla }}_{\theta }{J}_{lr}(\mathrm{\Theta })& =\frac{1}{n}\sum _{i=1}^n[\sigma ({\theta }^T{x}^{(i)}+{\theta }_0)-y^{(i)}]x^{(i)}+2\lambda \theta \\ {\mathbf{\nabla }}_{{\theta }_0}{J}_{lr}(\mathrm{\Theta })& =\frac{1}{n}\sum _{i=1}^n[\sigma ({\theta }^T{x}^{(i)}+{\theta }_0)-y^{(i)}]\end{array}$$

• Algorithm

  Here's the pseudo-code of gradient descent for logistic regression

  

 

 

 

3.3 Linear Regression

3.3.1 Definition

• Hypothesis

  Hypothesis of Linear Regression is a Hyperplane...but we are just trying to fit the data, without making any conclusions from this hyperplane like classification we did previously

  $$h(x^{(i)};\theta ,{\theta }_0)={\theta }^T{x}^{(i)}+{\theta }_0$$

• Training Loss

  The loss function we use for linear regression is Squared Loss

  $$L(g,a)=(g-a{)}^2$$

  While the optimization (minimization) objective uses Mean-Squared Loss

  $$\begin{array}{rl}J(\theta ,{\theta }_0)& =\frac{1}{n}\sum _{i=1}^{n}L(h(x^{(i)};\theta ,{\theta }_0),y^{(i)})\\ & =\frac{1}{n}\sum _{i=1}^n({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)}{)}^2\end{array}$$

  Notice that using the same trick in 1.6.5, offset ${\theta }_0$$\theta_0$ could be merged into ${\theta }^T{x}^{(i)}$$\theta^Tx^{(i)}$ (with $\theta ,x^{(i)}\in {\mathbb{R}}^d⟶{\mathbb{R}}^{d+1}$$\theta, x^{(i)} \in \mathbb{R}^d \longrightarrow \mathbb{R}^{d+1}$)

  Then We could expand and stack features $x^{(i)}$$x^{(i)}$ and results $y^{(i)}$$y^{(i)}$ as matrices $\tilde{X}\in {\mathbb{R}}^{n\times (d+1)}$$\tilde{X} \in \mathbb{R}^{n\times(d+1)}$ and $\tilde{Y}\in {\mathbb{R}}^n$$\tilde{Y} \in \mathbb{R}^{n}$

  $$\begin{array}{cc}\tilde{X}=\left[\begin{array}{cccc}{x}_1^{(1)}& \cdots & x_d^{(1)}& 1\\ ⋮& \ddots & ⋮& ⋮\\ x_1^{(n)}& \cdots & x_d^{(n)}& 1\end{array}\right]& \tilde{Y}=\left[\begin{array}{c}{y}^{(1)}\\ ⋮\\ y^{(n)}\end{array}\right]\end{array}$$

  With the above, rewrite the optimization objective in matrix form as below

  $$\begin{array}{rl}J(\theta ,{\theta }_0)& =\frac{1}{n}(\underset{{\mathbb{R}}^n}{\underbrace{\tilde{X}\theta -\tilde{Y}}}{)}^T(\tilde{X}\theta -\tilde{Y})\\ & =\frac{1}{n}{\Vert \tilde{X}\theta -\tilde{Y}\Vert }^2\end{array}$$

 

 

3.3.2 Direct Solution

A function could be uniquely minimized at a point, if Gradient at that point is 0 and Function "curves up"

The Gradient of optimization objective in 3.3.1 is the following matrix derivative with ${\mathbf{\nabla }}_{\theta }J(\theta ,{\theta }_0)\in {\mathbb{R}}^{d+1}$$\grad_\theta J(\theta, \theta_0) \in \mathbb{R}^{d+1}$

By setting ${\mathrm{\nabla }}_{\theta }J(\theta ,{\theta }_0)=0$$\nabla_\theta J(\theta, \theta_0) = 0$, we could (probabily) find desired unique minimizer $\theta$$\theta$

[IMPORTANT]

$({\tilde{X}}^T\tilde{X})$$(\tilde{X}^T\tilde{X})$ is a matrix of $2^{nd}$$2^{nd}$ derivatives. If the Function does not "curves up", $({\tilde{X}}^T\tilde{X})$$(\tilde{X}^T\tilde{X})$ will not be invertible!

 

 

3.3.3 Demo & Possible Errors

This is the regular situation

The following are possible errors you might encounter in real-life practice

• No Unique Best Hyperplane

  Very simple, the shape of your data happens to be awful...

  

  • Noisy Data

    Maybe you could find a solution, but it's just because of the noise of data like the uncertainty of thermometer...

    It looks like you have found the solution, but no, you shouldn't accept it!

    

• Feature Encoding Problems

  • Correlated Real-life features

    Ex. Doctors and nurses might have the same probability of exposure to some diseases, but they are categorized with one-hot encoding...

  • Too Many Features

    If the training data has only one data point, with only one feature, then you could have infinite hyperplanes as solutions, this is very very very bad!

    

    Generally speaking, your training data should have more data points than features to allow for a unique hyperplane as solution...but sometimes feature dimensions is too high comparing to data point numbers...

• Strategy

  When we are unsure which hyperplane to choose, just choose the $\theta$$\theta$ near 0 unless there's a strong reason not to

  The way to implement this strategy is Ridge Regression (see 3.3.4)

 

 

3.3.4 Ridge Regression

This is for the problem that sometimes there isn't a best Hyperplane as our solution in 3.3.3 (and also overfitting)

Under these situations, $({\tilde{X}}^T\tilde{X})$$(\tilde{X}^T\tilde{X})$ is usually not invertible

The solution is to add a Regularizer / Penalty $R(\theta )=\lambda {\Vert \theta \Vert }^2$$R(\theta)=\lambda\norm{\theta}^{2}$ with $\lambda >0$$\lambda > 0$ to the optimization objective in 3.3.1, this is the same thing as what we did for logistic regression (*see 3.2.4 for *)

The Gradient of the optimization objective of Ridge Regression ${\mathbf{\nabla }}_{\theta }{J}_{ridge}(\theta ,{\theta }_0)$$\grad_{\theta}J_{ridge}(\theta, \theta_0)$ is

Minimizing $J_{ridge}(\theta ,{\theta }_0)$$J_{ridge}(\theta, \theta_0)$ by setting ${\mathrm{\nabla }}_{\theta }{J}_{ridge}(\theta ,{\theta }_0)=0$$\nabla_{\theta}J_{ridge}(\theta, \theta_0)=0$ leads to the following

where $I$$I$ is an identity matrix with $I\in {\mathbb{R}}^{(d+1)\times (d+1)}$$I \in \mathbb{R}^{(d+1)\times (d+1)}$

This is called Ridge Regression because we are adding a "Ridge" of $\lambda$$\lambda$ values along the diagonal of the matrix before inverting it

[IMPORTANT]

• $({\tilde{X}}^T\tilde{X}+n\lambda I)$$(\tilde{X}^T\tilde{X} + n\lambda I)$ is a matrix of $2^{nd}$$2^{nd}$ derivatives. This is ALWAYS invertible with $\lambda >0$$\lambda > 0$

• When using Ridge Regression, we assume features are standardized as in 2.1.2

 

 

3.3.5 Gradient Descent Solution

You may ask: "Why do we still need gradient descent when we could derive $\theta$$\theta$ directly?" (see 3.3.2/4)

Here's why: Matrix Inversion has a time complexity of $O(n^2)\sim O(n^3)$$O(n^2) \sim O(n^3)$...

This Gradient Descent Solution is based on Ridge Regression

• Gradient of $\theta$$\theta$

  $$\begin{array}{rl}{\mathbf{\nabla }}_{\theta }{J}_{ridge}(\theta ,{\theta }_0)& =\frac{2}{n}{\tilde{X}}^T(\tilde{X}\theta -\tilde{Y})+2\lambda \theta \\ & =\frac{2}{n}\sum _{i=1}^n({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)})x^{(i)}+2\lambda \theta \end{array}$$

• Gradient of ${\theta }_0$$\theta_0$

  $${\mathrm{\nabla }}_{{\theta }_0}{J}_{ridge}(\theta ,{\theta }_0)=\frac{2}{n}\sum _{i=1}^n({\theta }^T{x}^{(i)}+{\theta }_0-y^{(i)})$$

Here's the pseudo-code for Gradient Descent for Linear Regression (using Ridge Regression)