# Linear Regression


```
# Linear Regression 1 Variable
# Independent: Number of A grades in 1st year (freshmen year)
x = [3,1,0,4]
# Dependent: Number of A grades in 2nd year (sophomore year)
y = [2,2,1,3]
# Hypothesis function
def hypothesis(theta0,theta1,x):
  h = theta0 + theta1 * x
  return h

# Cost function
def cost(theta0,theta1,x,y):
  # Number of training examples
  m = len(x)
  J = 0
  for i in range(m):
    J = J + ( hypothesis(theta0,theta1,x[i]) - y[i] )**2
    # print(i, " : ", J)
  J = J / (2*m)
  return J

theta0 = 0
theta1 = 1
J = cost(theta0,theta1,x,y)
print(J)

theta0 = -1
theta1 = 2
theta1 = 0.5
x = 6
x = 4
h = hypothesis(theta0,theta1,x)
print(h)

x = [1,2,4,0]
y = [0.5,1,2,0]
v_theta0 = [1,1,0.5,0,0.5]
v_theta1 = [0.5,1,0,0.5,0.5]
for i in range(len(v_theta0)):
  J = cost(v_theta0[i],v_theta1[i],x,y)
  print(i, " : ", J)
```

    0.5
    1.0
    0  :  0.5
    1  :  2.03125
    2  :  0.34375
    3  :  0.0
    4  :  0.125


# Linear Algebra


```
import numpy as np
import scipy.linalg as la
from numpy.linalg import matrix_power as mpow

M = np.array([[3,4],[-1,5]])
print('Matrix:\n', M)
print('Matrix Transposition:\n', M.T)
print('Elementwise Multiplication:\n', M * M)
print('Matrix Multiplication:\n', M @ M)
print('Matrix Power:\n', mpow(M,2))
I = np.eye(2)
print('Identity:\n', I)
A = np.array([[1,2],[3,4]])
print('Matrix:\n', A)
print('Matrix Invertion:\n', la.inv(A))
trace_A = np.trace(A)
print('Trace:\n', trace_A)
det_A = la.det(A)
print('Determinant:\n', det_A)
print('Hamilton:\n +A**2 = \n', A @ A)
print('trace_A * A = \n', trace_A * A)
print('det_A * I = \n', det_A * I)
print('A**2 - trace_A * A + det_A * I = \n', A @ A - trace_A * A + det_A * I)

A = np.array([[4,3],[6,9]])
B = np.array([[-2,9],[-5,2]])
print('A = \n', A)
print('B = \n', B)
print('A-B = \n', A-B)

x = np.array([2,7,4,1])
print('x = \n', x)
print('3*x = \n', 3*x)

u = np.array([5,1,9])
print('u = \n', u)
print('uT = \n', u.reshape(3,1))

u = np.array([1,3,-1])
v = np.array([2,2,4])
print('u = \n', u)
print('v = \n', v)
print('uT * v = \n', u @ v)
```

    Matrix:
     [[ 3  4]
     [-1  5]]
    Matrix Transposition:
     [[ 3 -1]
     [ 4  5]]
    Elementwise Multiplication:
     [[ 9 16]
     [ 1 25]]
    Matrix Multiplication:
     [[ 5 32]
     [-8 21]]
    Matrix Power:
     [[ 5 32]
     [-8 21]]
    Identity:
     [[1. 0.]
     [0. 1.]]
    Matrix:
     [[1 2]
     [3 4]]
    Matrix Invertion:
     [[-2.   1. ]
     [ 1.5 -0.5]]
    Trace:
     5
    Determinant:
     -2.0
    Hamilton:
     +A**2 = 
     [[ 7 10]
     [15 22]]
    trace_A * A = 
     [[ 5 10]
     [15 20]]
    det_A * I = 
     [[-2. -0.]
     [-0. -2.]]
    A**2 - trace_A * A + det_A * I = 
     [[0. 0.]
     [0. 0.]]
    A = 
     [[4 3]
     [6 9]]
    B = 
     [[-2  9]
     [-5  2]]
    A-B = 
     [[ 6 -6]
     [11  7]]
    x = 
     [2 7 4 1]
    3*x = 
     [ 6 21 12  3]
    u = 
     [5 1 9]
    uT = 
     [[5]
     [1]
     [9]]
    u = 
     [ 1  3 -1]
    v = 
     [2 2 4]
    uT * v = 
     4


$$ h_\theta(x) = \theta_0 + \theta_1 x_1 + ... + \theta_n x_n = \theta^Tx $$ 

\begin{align*}h_\theta(x) =\begin{bmatrix}\theta_0 \hspace{2em} \theta_1 \hspace{2em} ... \hspace{2em} \theta_n\end{bmatrix}\begin{bmatrix}x_0 \newline x_1 \newline \vdots \newline x_n\end{bmatrix}= \theta^T x\end{align*}

\begin{align*}
x_j^{(i)} &= \text{value of feature } j \text{ in the }i^{th}\text{ training example}
\newline x^{(i)}& = \text{the input (features) of the }i^{th}\text{ training example}
\newline m &= \text{the number of training examples}
\newline n &= \text{the number of features} \end{align*}


\begin{align*}& \text{repeat until convergence:} \; \lbrace \newline \; & \theta_j := \theta_j - \alpha \frac{1}{m} \sum\limits_{i=1}^{m} (h_\theta(x^{(i)}) - y^{(i)}) \cdot x_j^{(i)} \; & \text{for j := 0...n}\newline \rbrace\end{align*}




feature scaling and mean normalization

$$ x_i := \frac{x_i-\mu_i}{s_i} $$


If $\alpha$ is too small: slow convergence.

If $\alpha$ is too large: may not decrease on every iteration and thus may not converge.


```
x0 = [1,1,1,1]
x1 = [2104,1416,15314,852]
x2 = [5,3,3,2]
x3 = [1,2,2,1]
x4 = [45,40,30,36]
y = [46,232,315,178]
m = len(y)
x0 = [1,1,1,1]

X = [x0,x1,x2,x3,x4]
```

# Normal Equation
$$ \theta = (X^TX)^{-1}X^Ty $$


$ (X^TX)$ non invertible, singular degenerate


1.   Redundant features (LD)
Delete one of such futures


2.   Too many features (e.g. $ m \leq n$ )

Delete some futures or use regularization

# Gradient Descent vs Normal Equation

| Criteria | Gradient Descent | Normal Equation   |
|---|------|------|
| Need to choose alpha |   Yes  | No |
| Iterations |   Many  | Single |
| Time |   $O(kn^2)$  | $O(n^3)$ |
| Size |   Large  | Not very large <10.000 |


# Classification
Binary: 0 Negative class, 1 Positive class
Classification: $ y=0 $
 or $1$

Multiclasse: >2 classes

## Linear regression

$$ h_\theta(x) = \theta^Tx $$ 

if $ h_\theta(x) \geq 0.5 $, predict $ y = 1$

if $ h_\theta(x) \lt 0.5 $, predict $ y = 0$

$ h_\theta(x) < 0 $ or $  > 1 $

Conclusion: 

Linear regression doesn't suit classification problems very well

## Logistic Regression
One desires that
$$ 0 \leq h_\theta(x) \leq 1 $$

We have the sigmoid or logistic function
$$ g(z) = \frac{1}{1+e^{-z}} $$ 

With the following properties
\begin{align*}
g(z) \geq 0.5, \qquad  \text{when} \; z \geq 0
\end{align*}
\begin{align*}
&z=0, \qquad\quad e^{0}=1 &\Rightarrow g(z)=\frac{1}{2} \newline
&z \to \infty,\qquad\; e^{-\infty} \to 0 &\Rightarrow g(z)=1 \newline
&z \to -\infty,\quad\;\; e^{\infty}\to \infty &\Rightarrow g(z)=0
\end{align*}





```
import numpy as np
import matplotlib.pyplot as plt
# evenly sampled z at 0.1 intervals
z = np.arange(-5, 5., 0.1)
exp_z = np.exp(z)
exp_minus_z = np.exp(-z)
one_plus_exp_minus_z = 1 + np.exp(-z)
inv_one_plus_exp_minus_z = 1./(1 + np.exp(-z))

plt.style.use(['dark_background'])
plt.rcParams.update({'font.size': 15})

f, (ax1, ax2) = plt.subplots(2, 1, sharex=True)
ax1.plot(z, exp_z)
ax1.set_title('$e^{z}$')
ax2.scatter(z, exp_minus_z)
ax2.set_title('$e^{-z}$')
#ax2.set_title('$\frac{1}{1+e^{-z}}$')
f, (ax1, ax2) = plt.subplots(2, 1, sharex=True)
ax1.plot(z, one_plus_exp_minus_z)
ax1.set_title('$1 + e^{-z}$')
ax2.scatter(z, inv_one_plus_exp_minus_z)
ax2.set_title('$\\frac{1}{1+e^{-z}}$')
```


Hypothesis representation
$$ h_\theta(x) = g(\theta^Tx) = \frac{1}{1+e^{-\theta^Tx}} $$ 

Thus
\begin{align*}
h_\theta(x) = g(\theta^T x) \geq 0.5, \qquad \text{when} \; \theta^T x \geq 0
\end{align*}
In a nutshell
\begin{align*}& \theta^T x \geq 0 \Rightarrow y = 1 \newline& \theta^T x < 0 \Rightarrow y = 0 \newline\end{align*}

Probability that $y=1$, given $x$ parametrized by $\theta$

$$h_\theta(x) = P(y=1|x;\theta) $$

Regarding that
$$  P(y=0) + P(y=1) = 1 $$

### Decision Boundary

if $ h_\theta(x) \geq 0.5 $,
predict $ y = 1$;
$ g(z) \geq 0.5 $,
when $z = \theta^Tx \geq 0$

if $ h_\theta(x) \lt 0.5 $,
predict $ y = 0$
$ g(z) \lt 0.5 $,
when $z = \theta^Tx \lt 0$

Decision boundary is a property of the hypothesis and not of the dataset

### Cost function

\begin{align*}
& J(\theta) = \dfrac{1}{m} \sum_{i=1}^m \mathrm{Cost}(h_\theta(x^{(i)}),y^{(i)}) \newline
& \mathrm{Cost}(h_\theta(x),y) = -\log(h_\theta(x)) \; & \text{if y = 1} \newline
& \mathrm{Cost}(h_\theta(x),y) = -\log(1-h_\theta(x)) \; & \text{if y = 0}
\end{align*}

\begin{align*}
& \mathrm{Cost}(h_\theta(x),y) = 0 \text{ if } h_\theta(x) = y \newline
& \mathrm{Cost}(h_\theta(x),y) \rightarrow \infty \text{ if } y = 0 \; \mathrm{and} \; h_\theta(x) \rightarrow 1 \newline
& \mathrm{Cost}(h_\theta(x),y) \rightarrow \infty \text{ if } y = 1 \; \mathrm{and} \; h_\theta(x) \rightarrow 0
\end{align*}

Penalizes absence of extremely high and low probability cases (as 0 and 1)




```
import numpy as np
import matplotlib.pyplot as plt
# evenly sampled z at 0.1 intervals
z = np.arange(0.01, 1., 0.01)

log_z = np.log(z)
negative_log_1minusz = -np.log(1-z)
#fig, ax = plt.subplots()
# red dashes, blue squares and green triangles
plt.style.use(['dark_background'])
plt.rcParams.update({'font.size': 15})
plt.plot(z, -log_z, 'bs', z, negative_log_1minusz, 'g^')
plt.legend(['$-\log(z)$, if $y=1$','$-\log(1-z)$, if $y=0$'])
plt.xlabel('Hypothesis: $z = h_\\theta(x) $')
plt.ylabel('Cost Function: $J(h_\\theta(x),y) $')
#plt.axis([0, 1, 0, 5])
plt.show()

f, (ax1, ax2) = plt.subplots(2, 1, sharex=True)
ax1.plot(z, log_z)
ax1.set_title('$\log(z)$')
ax2.scatter(z, -log_z)
ax2.set_title('$-\log(z)$');

```

As always $y=0$ or $y=1$
$$ \mathrm{Cost}(h_\theta(x),y) = -y \log(h_\theta(x)) - (1-y)\log(1-h_\theta(x)) $$


Principle of maximum likelihood estimation: statistics idea to find parameters


\begin{align*}
& h = g(X\theta)\newline
& J(\theta) = \frac{1}{m} \cdot \left(-y^{T}\log(h)-(1-y)^{T}\log(1-h)\right) \end{align*}


\begin{align*}
& \text{Repeat} \; \lbrace \newline
& \; \theta_j := \theta_j - \frac{\alpha}{m} \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)}) x_j^{(i)} \newline
& \rbrace
\end{align*}


$$ \theta := \theta - \frac{\alpha}{m}X^T(g(X\theta)-y)$$


```

```

Optimization algorithms (Line search)
*   Gradient descent
*   Conjugate gradient
*   BFGS
*   L-BFGS

Advantages
*   No need to manually pick $\alpha$
*   Often faster than gradient descent

Disadvantages
*   More complex

Compute cost function and its derivative




```
def cost_function(theta):
  J = (theta[0] - 5) ** 2 + (theta[1] - 5) ** 2
  return J
def derivative_cost_function(theta):
  dJdtheta = [2*(theta[0] - 5),2*(theta[1] - 5)]
  return dJdtheta
theta = [5, 5]
J = cost_function(theta)
dJdtheta = derivative_cost_function(theta)
print(J)
print(dJdtheta)
```

    34
    [10, 6]


# Optimization Algorithms


```
>>> from scipy.optimize import minimize, rosen, rosen_der
>>> x0 = [1.3, 0.7, 0.8, 1.9, 1.2]
```

## Nelder Mead


```
res = minimize(rosen, x0, method='Nelder-Mead',
               options={'gtol': 1e-6, 'disp': True})
print(res.x)
print(res.message)
```

    Optimization terminated successfully.
             Current function value: 0.000066
             Iterations: 141
             Function evaluations: 243
    [0.99910115 0.99820923 0.99646346 0.99297555 0.98600385]
    Optimization terminated successfully.


    /usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:2: OptimizeWarning: Unknown solver options: gtol
      


## BFGS


```
res = minimize(rosen, x0, method='BFGS', jac=rosen_der,
...                options={'gtol': 1e-6, 'disp': True})
print(res.x)
print(res.hess_inv)
```

    Optimization terminated successfully.
             Current function value: 0.000000
             Iterations: 26
             Function evaluations: 31
             Gradient evaluations: 31
    [1. 1. 1. 1. 1.]
    [[0.00763624 0.0125159  0.02359808 0.0465684  0.09317974]
     [0.0125159  0.02489687 0.04727754 0.09353774 0.18708048]
     [0.02359808 0.04727754 0.09483095 0.18783847 0.37561493]
     [0.0465684  0.09353774 0.18783847 0.37715312 0.75414172]
     [0.09317974 0.18708048 0.37561493 0.75414172 1.51296479]]



```
fun = lambda x: (x[0] - 1)**2 + (x[1] - 2.5)**2
>>> cons = ({'type': 'ineq', 'fun': lambda x:  x[0] - 2 * x[1] + 2},
...         {'type': 'ineq', 'fun': lambda x: -x[0] - 2 * x[1] + 6},
...         {'type': 'ineq', 'fun': lambda x: -x[0] + 2 * x[1] + 2})
>>> bnds = ((0, None), (0, None))
```

SLSQP


```
>>> res = minimize(fun, (2, 0), method='SLSQP', bounds=bnds,
...                constraints=cons, options={'gtol': 1e-6, 'disp': True})
print(res.x)
```

    Optimization terminated successfully.    (Exit mode 0)
                Current function value: 0.8000000011920985
                Iterations: 3
                Function evaluations: 13
                Gradient evaluations: 3
    [1.4 1.7]


    /usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:2: OptimizeWarning: Unknown solver options: gtol
      


# Multiclass
One vs all/rest

Train a logistic regression classifier $h^{(i)}_\theta(x)$ for each class $i$ to predict the probability that $y = i$.

To make a prediction on a new $x$,
pick the class $i$
that maximizes $h_\theta(x)$


\begin{align*}
& y \in \lbrace0, 1 ... n\rbrace \newline
& h_\theta^{(0)}(x) = P(y = 0 | x ; \theta) \newline
& h_\theta^{(1)}(x) = P(y = 1 | x ; \theta) \newline
& \cdots \newline
& h_\theta^{(n)}(x) = P(y = n | x ; \theta) \newline
& \mathrm{prediction} = \max_i( h_\theta ^{(i)}(x) )
\end{align*}

2.Question 2
Suppose you have the following training set, and 
fit a logistic regression classifier
$$ h_\theta(x) = g(\theta_0 + \theta_1x_1 + \theta_2 x_2)$$

TRUE
*   $J(\theta)$ will be a convex function, so gradient descent should converge to the global minimum.
*   At the optimal value of \thetaθ (e.g., found by fminunc), we will have $J(\theta) \geq 0$.
*   Adding polynomial features (e.g., instead using
$$h_\theta(x) = g(\theta_0 + \theta_1x_1 + \theta_2 x_2 + \theta_3 x_1^2 + \theta_4 x_1 x_2 + \theta_5 x_2^2) $$
could increase how well we can fit the training data,
but wouldn't increase $J(\theta)$ because we are now summing over more terms.

FALSE

The positive and negative examples cannot be separated using a straight line.
So, gradient descent will fail to converge.

FALSE

Because the positive and negative examples cannot be separated using a straight line,
linear regression will perform as well as logistic regression on this data.

FALSE

If we train gradient descent for enough iterations, for some examples $x^{(i)}$
in the training set it is possible to obtain $h_\theta(x^{(i)}) > 1$.


3.Question 3
For logistic regression, the gradient is given by
$$\frac{\partial}{\partial \theta_j} J(\theta)
= \frac{1}{m}\sum_{i=1}^m{ (h_\theta(x^{(i)}) - y^{(i)}) x_j^{(i)}}$$
Which of these is a correct gradient descent update for logistic regression
with a learning rate of $\alpha$?

FALSE
$$\theta := \theta - \alpha \frac{1}{m} \sum_{i=1}^m{
 \left(\frac{1}{1 + e^{-\theta^T x^{(i)}}} - y^{(i)}\right) x^{(i)}}$$

FALSE (the hypothesis function is not like that)
$$\theta := \theta - \alpha \frac{1}{m} \sum_{i=1}^m{
 \left(\theta^T x - y^{(i)}\right) x^{(i)}}, \quad
 \text{(simultaneously update for all j)}$$

TRUE (vectorized)
$$\theta := \theta - \alpha \frac{1}{m} \sum_{i=1}^m{
 (h_\theta(x^{(i)}) - y^{(i)}) x^{(i)}}, \quad
 \text{(simultaneously update for all j)}$$
 
TRUE (discrete)
$$\theta_j := \theta_j - \alpha \frac{1}{m} \sum_{i=1}^m{
 \left(\theta^T x - y^{(i)}\right) x_j^{(i)}}, \quad
 \text{(simultaneously update for all j)}$$
 

4.Question 4

TRUE
*   The cost function $J(\theta)$ for logistic regression trained with $m \geq 1$
examples is always greater than or equal to zero.
*   The one-vs-all technique allows you to use logistic regression
for problems in which each $y^{(i)}$ comes from a fixed, discrete set of values.


FALSE (train k classifiers for k classes)

Since we train one classifier when there are two classes,
we train two classifiers when there are three classes (and we do one-vs-all classification).

FALSE (that's not the reason)

For logistic regression, sometimes gradient descent will converge to a local minimum
(and fail to find the global minimum).
This is the reason we prefer more advanced optimization algorithms
such as fminunc (conjugate gradient/BFGS/L-BFGS/etc).

5.Question 5
Suppose you train a logistic classifier
$$h_\theta(x) = g(\theta_0 + \theta_1x_1 + \theta_2 x_2)$$
Suppose 
$$\theta_0 = 6, \theta_1 = -1, \theta_2 = 0 $$
Decision boundary is

|		 |     |        |
|---|-----------|------|
|$y = 1$| 	|	$y = 0$|
|		    | $x1 = 6$  |        |
	 

# Overfitting

Underfit: high bias

Overfit:
*   high variance
*   too many features
*   fit the training set very well
*   fail to new generalized cases

Prevent overfitting
1.   Reduce number of features
*   Manual selection
*   Algorithm selection

2.   Regularization
*   Keep all features, but reduce magnitude of parameters $\theta_j$
*   Work well, when a lot of slightly useful features
* Too large $\lambda$ can cause underfit
* $J(\theta)$ is still convex
* can impair the performance on training examples
* $\geq$ performance on predictions not in the training set


## Regularization





Cost function

Penalization

$$ \min_\theta = 
\dfrac{1}{2m} \sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})^2 
+ \lambda \sum_{j=1}^n \theta_j^2 $$


### Gradient descent

\begin{align*} & \text{Repeat}\ \lbrace \newline & \ \ \ \ \theta_0 := \theta_0 - \alpha\ \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_0^{(i)} \newline & \ \ \ \ \theta_j := \theta_j - \alpha\ \left[ \left( \frac{1}{m}\ \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)})x_j^{(i)} \right) + \frac{\lambda}{m}\theta_j \right] &\ \ \ \ \ \ \ \ \ \ j \in \lbrace 1,2...n\rbrace\newline & \rbrace \end{align*}




$$ \theta_j := \theta_j \left(1- \alpha \frac{\lambda}{n}\right) 
- \frac{\alpha}{m} \sum_{i=1}^m (h_\theta(x^{(i)}) - y^{(i)}) x_j^{(i)} $$


$\lambda, \alpha, m > 0 \implies 1- \alpha \frac{\lambda}{m} < 1 $ 

### Normal equation

\begin{align*}& \theta = \left( X^TX + \lambda \cdot L \right)^{-1} X^Ty \newline& \text{where}\ \ L = \begin{bmatrix} 0 & & & & \newline & 1 & & & \newline & & 1 & & \newline & & & \ddots & \newline & & & & 1 \newline\end{bmatrix}\end{align*}

$X$ is non-invertible if $m < n$, and may be non-invertible if $m = n$.

However $X^TX + \lambda \cdot L$ becomes invertible.

Logistic Regression
$$ J(\theta) = -\frac{1}{m}\sum_{i=1}^m \left[ 
  y^{(i)}\log(h_\theta(x^{(i)}))
  +(1-y^{(i)})\log(1-h_\theta(x^{(i)}))
  \right] $$

Regularized Logistic Regression
$$ J(\theta) = -\frac{1}{m}\sum_{i=1}^m \left[ 
  y^{(i)}\log(h_\theta(x^{(i)}))
  +(1-y^{(i)})\log(1-h_\theta(x^{(i)}))
  \right]
  + \frac{\lambda}{2m} \sum_{j=1}^n \theta_j^2 $$

Hypothesis function
$$ h_\theta(x) = \frac{1}{1+e^{-\theta^Tx}} $$ 

# Linear vs Logistic Regression

## Differences
\begin{align*}
&\text{Regression} & \text{Linear} & & \text{Logistic}\newline
&h = & \theta^T X && \dfrac{1}{1+e^{-\theta^T X}} \newline
&J = & \frac{(h-y)^T(h-y)}{2m} &&\frac{\left(-y^{T}\log(h)-(1-y)^{T}\log(1-h)\right)}{m}
\end{align*}

## Similarities
Gradient
$$\frac{\partial J}{\partial \theta}=  \frac{X^{T}(h-y)}{m} $$
Cost Function Penalty
$$pJ = \frac{\lambda}{2m} \sum_{j=1}^n \theta_j^2$$
Gradient Function Penalty
$$p\frac{\partial J}{\partial \theta} = \frac{\lambda}{m} \sum_{j=1}^n \theta_j$$

Remark
$\theta_0$ is not penalized

# Parameter estimation

Gradient Descent
$$ \theta := \theta - \alpha \frac{\partial J}{\partial \theta} $$

Normal Equation
$$ \theta = (X^TX)^{-1}X^Ty $$

# Neural Networks

* gray scale: 0-255

* RGB: 3x 0-255

1980 popular, ressuregence today

Dendrite
* input wires
Axon
* output wires
Synapse

Sigmoid Logistic activation function
$$ h_\Theta(x) = \frac{1}{1+e^{-\Theta^Tx}} $$ 

Bias
* $x_0 = 1$

Parameters
* weights

Layer
1. Input
2. Hidden
3. Output

$a_i^{(j)}$: Activation of unit $i$ in layer $j$

$\Theta^{(j)}$: matrix of weights controlling function mapping from layer $j$ to layer $j+1$

$s_j$ units in layer $j$, $s_{j+1}$ units in layer ${j+1}$
$\implies \Theta^{(j)} \in \mathbb{R}^{ s_{j+1} \times (s_{j}+1)}$

where $1$ refers to the bias nodes $x_0$ and $\Theta_0^{(j)}$


## Forward propagation

Ex: $1$ hidden layer 
$$[x_0 x_1 x_2 x_3] \implies [a_1^{(2)} a_2^{(2)} a_3^{(2)}] \implies  h_\Theta(x) $$

Activation functions
\begin{align*}
a_1^{(2)} = g(\Theta_{10}^{(1)}x_0 + \Theta_{11}^{(1)}x_1 + \Theta_{12}^{(1)}x_2 + \Theta_{13}^{(1)}x_3) = g(z_1^{(2)}) \newline
a_2^{(2)} = g(\Theta_{20}^{(1)}x_0 + \Theta_{21}^{(1)}x_1 + \Theta_{22}^{(1)}x_2 + \Theta_{23}^{(1)}x_3) = g(z_2^{(2)}) \newline
a_3^{(2)} = g(\Theta_{30}^{(1)}x_0 + \Theta_{31}^{(1)}x_1 + \Theta_{32}^{(1)}x_2 + \Theta_{33}^{(1)}x_3) = g(z_3^{(2)}) \newline
h_\Theta(x) = a_1^{(3)} = g(\Theta_{10}^{(2)}a_0^{(2)} + \Theta_{11}^{(2)}a_1^{(2)} + \Theta_{12}^{(2)}a_2^{(2)} + \Theta_{13}^{(2)}a_3^{(2)})
\end{align*}

Vectorize
\begin{align*}
z_1^{(2)} = \Theta_{10}^{(1)}x_0 + \Theta_{11}^{(1)}x_1 + \Theta_{12}^{(1)}x_2 + \Theta_{13}^{(1)}x_3 \newline
z_2^{(2)} = \Theta_{20}^{(1)}x_0 + \Theta_{21}^{(1)}x_1 + \Theta_{22}^{(1)}x_2 + \Theta_{23}^{(1)}x_3 \newline
z_3^{(2)} = \Theta_{30}^{(1)}x_0 + \Theta_{31}^{(1)}x_1 + \Theta_{32}^{(1)}x_2 + \Theta_{33}^{(1)}x_3
\end{align*}

\begin{align*}
z_k^{(2)} = \Theta_{k0}^{(1)}x_0 + \Theta_{k1}^{(1)}x_1 + \cdot\cdot\cdot + \Theta_{kn}^{(1)}x_n
\end{align*}

\begin{align*}
a_1^{(2)} = g(z_1^{(2)}) \newline
a_2^{(2)} = g(z_2^{(2)}) \newline
a_3^{(2)} = g(z_3^{(2)})
\end{align*}


\begin{align*}
a^{(1)} =
x = 
\begin{bmatrix}
x_0 \newline
x_1 \newline
\cdots \newline
x_n
\end{bmatrix}
,\qquad
a^{(j)} =
g(z^{(j)}) = 
g\left(
\begin{bmatrix}
z_1^{(j)} \newline
z_2^{(j)} \newline
\cdots \newline
z_n^{(j)}
\end{bmatrix}
\right)
\end{align*}

$$ z^{(j)} = \Theta^{(j-1)}a^{(j-1)} $$

$$ z^{(j+1)} = \Theta^{(j)}a^{(j)} $$

$$ h_\Theta(x) = a^{(j+1)} = g(z^{(j+1)}) $$

Forward propagation algorithm
\begin{align}
a^{(1)} &= x \quad (\text{add } a_0^{(1)}) \\
z^{(2)} &= \Theta^{(1)}a^{(1)}\\
a^{(2)} &= g(z^{(2)}) \quad (\text{add } a_0^{(2)}) \\
z^{(3)} &= \Theta^{(2)}a^{(2)}\\
a^{(3)} &= g(z^{(3)}) \quad (\text{add } a_0^{(3)}) \\
z^{(4)} &= \Theta^{(3)}a^{(3)}\\
a^{(4)} &= g(z^{(4)})
\end{align}


```

x = [1;2;3];
Theta1 = ones(3,3);
a2 = zeros(3,1);

function sig = sigmoid(z)
  sig = 1/(1 + exp(-z))
end

for i =1:3
  for j = 1:3
    a2(i) = a2(i) + x(j) * Theta1(i,j);
  end
  a2(i) = sin(a2(i));
end

a2v = sin(Theta1*x)

a2v = sin(x * Theta1)

t1 = [1 2.1 1.3; 1 0.6 -1.2]
t1_ = [1 0.6 -1.2; 1 2.1 1.3]
t2 = [1 3.1 4.5]
t2_ = [1 4.5 3.1]


a1 = x
a2 = sigmoid(t1 * a1)
a2_ = sigmoid(t1_ * a1)

a3 = sigmoid(t2 * a2)
a3_ = sigmoid(t2_ * a2_)

h = a3
h = a3_

```

## Non-linear classification: XOR/XNOR

\begin{align*}
y = \;& x_1 \text{XOR}\; x_2 \newline
& x_1 \text{XNOR}\; x_2\newline
& \text{NOT} (x_1 \text{XOR}\; x_2) \newline
\end{align*}
$$ x_1,x_2 \in \{0,1\} $$

\begin{align*}
y = \;& x_1 \text{AND}\; x_2 \newline
\end{align*}


Truth tables

| $x_1$ | $x_2$ |  OR  | AND | XOR | XNOR | NAND | NOR | 
|-------|-------|------|-----|-----|------|------|-----|
|1      |1      |1     |1    |0    |1     |0     |0    |
|1      |0      |1     |0    |1    |0     |1     |0    |
|0      |1      |1     |0    |1    |0     |1     |0    |
|0      |0      |0     |0    |0    |1     |1     |1    |

|~$x_1$ |~$x_2$ |  OR  | AND | XOR | XNOR | NAND | NOR | 
|-------|-------|------|-----|-----|------|------|-----|
|0      |0      |0     |0    |0    |1     |1     |1    |
|0      |1      |1     |0    |1    |0     |1     |0    |
|1      |0      |1     |0    |1    |0     |1     |0    |
|1      |1      |1     |1    |0    |1     |0     |0    |

* X: exclusive
* N: not
* XNOR: not XOR
* $x_1$ NOR $x_2$  = (NOT $x_1$) AND (NOT $x_2$)

$$\Theta_0^{(1)} = 10$$
Not
$$\Theta_0^{(1)} = -20$$


|                | $x_1$ OR $x_2$ | $x_1$ AND $x_2$ | $x_1$ NOR $x_2$ | 
|----------------|:-:|:-:|:-:|
|$\Theta_0^{(1)}$|10 |-30|10 |
|$\Theta_1^{(1)}$|20 |20 |-20|
|$\Theta_2^{(1)}$|20 |20 |-20|





```
import numpy as np
import matplotlib.pyplot as plt
# evenly sampled z at 0.1 intervals
z = np.arange(-5, 5., 0.1)

def sigmoid_function(z):
  sigmoid = 1./(1 + np.exp(-z))
  return sigmoid


inv_one_plus_exp_minus_z = 1./(1 + np.exp(-z))

plt.style.use(['dark_background'])
plt.rcParams.update({'font.size': 15})

plt.scatter(z, sigmoid_function(z))
plt.title('$g(z) = \\dfrac{1}{1+e^{-z}}$')
plt.xlabel('z')

print('g(-4) = ', sigmoid_function(-4))
print('g(4) = ', sigmoid_function(4))

theta = np.array([-10,20,20])
x0 = np.array([1,1,1,1])
x1 = np.array([1,1,0,0])
x2 = np.array([1,0,1,0])
z = theta[0] * x0 + theta[1] * x1 + theta[2] * x2
sigmoid_function(z)
```

## Multiclass Classification

* 10 classes
* 3 layers
* hidden layer has 5 units

one vs all
* $\Theta^{(2)}$ has 60 elements
 * must add 1 element from bias unit

## Quiz

* without hidden layer is not possible to represent XOR function
* any logical binary function can be approximated by some neural network
* sigmoid activation function $\in [0,1]$
* $a_1^{(3)} + a_2^{(3)} + a_3^{(3)} = 1 $


## Backpropagation
* $L$ = total number of layers in the network
* $s_l$ = number of units (not counting bias unit) in layer $l$
* $K$ = number of output units/classes

\begin{gather*}
J(\Theta) =
 - \frac{1}{m} \sum_{i=1}^m \sum_{k=1}^K 
 \left[y^{(i)}_k \log ((h_\Theta (x^{(i)}))_k)
 + (1 - y^{(i)}_k)\log (1 - (h_\Theta(x^{(i)}))_k)\right] 
 + \frac{\lambda}{2m}\sum_{l=1}^{L-1} \sum_{i=1}^{s_l} \sum_{j=1}^{s_{l+1}}
 ( \Theta_{j,i}^{(l)})^2
 \end{gather*}



Backpropagation

Given training set
$\{(x^{(1)},y^{(1)}),\cdot\cdot\cdot,(x^{(m)},y^{(m)})\}$
* Set 
$$\Delta_{ij}^{(l)}:=0 \quad \forall (l,i,j)$$

For training example $t=1:m$:


1.   Set 
$$a^{(1)}:= x^{(t)} \quad (\text{add } a_0^{(1)})$$
2.   Perform forward propagation to compute $a^{(l)}$ for $l=2,\cdot\cdot\cdot,L$
\begin{align}
z^{(2)} &= \Theta^{(1)}a^{(1)}\\
a^{(2)} &= g(z^{(2)}) \quad (\text{add } a_0^{(2)}) \\
z^{(3)} &= \Theta^{(2)}a^{(2)}\\
a^{(3)} &= g(z^{(3)}) \quad (\text{add } a_0^{(3)}) \\
z^{(4)} &= \Theta^{(3)}a^{(3)}\\
a^{(4)} &= g(z^{(4)})
\end{align}
3. Compute  the error
$$\delta^{(L)} = a^{(L)} - y^{(t)}$$
4. Compute $\delta^{(L-1)},\delta^{(L-2)},\cdot\cdot\cdot,\delta^{(2)}$
$$ \delta^{(l)} = ((\Theta^{(l)})^T\delta^{(l-1)}) \;.*\;
a^{(l)} \;.*\; (1-a^{(l)}) $$
where
$$ g'(z^{(l)}) = a^{(l)} \;.*\; (1-a^{(l)}) $$
5. Update $$ \Delta^{(l)}:= \Delta^{(l)} + \delta^{(l+1)}(a^{(l)})^T $$
6. Compute the derivatives
\begin{align}
D_{ij}^{(l)} &:= \dfrac{1}{m}\left(\Delta_{ij}^{(l)} + \lambda\Theta_{ij}^{(l)}\right) &\text{if } j \neq 0 \\
D_{ij}^{(l)} &:= \dfrac{1}{m}\left(\Delta_{ij}^{(l)}\right) 
&\text{if } j = 0
\end{align}
where
$$ \dfrac{\partial J(\Theta)}{\partial \Theta_{ij}^{(l)}} = D_{ij}^{(l)}
$$

Unroll

Matrix to vector
``` octave
thetaVector = [ Theta1(:); Theta2(:); Theta3(:); ]
deltaVector = [ D1(:); D2(:); D3(:) ]
```

Vector to matrix
``` octave
Theta1 = reshape(thetaVector(1:110),10,11)
Theta2 = reshape(thetaVector(111:220),10,11)
Theta3 = reshape(thetaVector(221:231),1,11)
```



Gradient Checking

To ckeck if backprop is correctly implemented


$$ \dfrac{\partial J(\Theta)}{\partial \Theta} \approx 
\dfrac{J(\Theta+\epsilon)-J(\Theta-\epsilon)}{2\epsilon} $$

$$ \dfrac{\partial J(\Theta)}{\partial \Theta_{j}} \approx 
\dfrac{J(\Theta_1,...,\Theta_j+\epsilon,...,\Theta_n)-J(\Theta_1,...,\Theta_j-\epsilon,...,\Theta_n)}{2\epsilon} $$

$ \epsilon = 10^{-4} $


```
x = 1
eps = 0.01

def cost(x):
  J = x ** 3
  return J

def cds(x,eps):
  dJdx = ( cost(x+eps) - cost(x-eps) ) / (2*eps)
  return dJdx

grad_approx = cds(x,eps)
grad_approx
```




    3.0001000000000055




```
x = 1
eps = 0.01

def cost(x):
  J = 2 * x ** 4 + 2
  return J

def cds(x,eps):
  dJdx = ( cost(x+eps) - cost(x-eps) ) / (2*eps)
  return dJdx

grad_approx = cds(x,eps)
grad_approx
```




    8.000800000000007




``` octave
epsilon = 1e-4;
for i = 1:n,
  thetaPlus = theta;
  thetaPlus(i) += epsilon;
  thetaMinus = theta;
  thetaMinus(i) -= epsilon;
  gradApprox(i) = (J(thetaPlus) - J(thetaMinus))/(2*epsilon)
end;
```



Random initialization

Symmetry breaking

``` octave
Theta1 = rand(10,11) * (2 * INIT_EPSILON) - INIT_EPSILON;
Theta2 = rand(10,11) * (2 * INIT_EPSILON) - INIT_EPSILON;
Theta3 = rand(1,11) * (2 * INIT_EPSILON) - INIT_EPSILON;
```

$$ \epsilon_{init} = \dfrac{\sqrt{6}}{\sqrt{L_{in} + L_{out}}} $$
where $L_{in}=s_l$ and $L_{out}=s_{l+1}$ are the # units in the layers adjacent to $\Theta^{(l)}$



``` octave
W = rand(L_out, 1 + L_in) * 2 * epsilon_init - epsilon_init;
```





Reasonable default: 1 hidden layer

if > 1 hidden layer, keep the same amount of units in every layer (usually the more the better)

\# units: [ # inputs , 3 x # inputs ]


Training a neural network

1.   Randomly initialize weights
2.   Implement forward propagation to get $h_\Theta(x^{(i)})$
3.   Implement code to compute cost function $J(\Theta)$
4.   Implement backprop to compute partial derivatives $ \dfrac{\partial J(\Theta)}{\partial \Theta_{jk}^{(l)}}  $
5.   Gradient checking
6.   Use optmization with backprop to try to minimize $ J(\Theta) $ (non convex, gradient descent could converge to local minima)



``` octave
for i = 1:m,
   Perform forward propagation and backpropagation using example (x(i),y(i))
   (Get activations a(l) and delta terms d(l) for l = 2,...,L
```






```

```

# What to try next

1.   Get more training examples: fixes high variance
2.   Try smaller sets of features: fixes high variance
3.   Try getting additional features: fixes high bias
4.   Try adding polynomial features: fixes high bias
5.   Try decreasing $\lambda$: fixes high bias
6.   Try increasing $\lambda$: fixes high variance

# ML diagnostic
1.   Can give guidance
2.   Can be time-consuming to implement and try, but can be worth
3.   Can rule out certain actions


# Evaluate our hypothesis
1.   Random split training set (70%) and test set (30%)
2.   Fit with training data, minimizing cost function
3.   Compute test set error
4.   Misclassification error

# Random split
1.   Training set (60%)
2.   Cross validation set (20%)
3.   Test set (20%)

# Procedure
1.   Fit training set
2.   Cross validate on validation set
3.   Estimate error on test set

$$ err(h_\Theta(x),y) =
\begin{matrix}
1 & \mbox{if } h_\Theta(x) \geq 0.5\
and\ y = 0\
or\ h_\Theta(x) < 0.5\ and\ y = 1\newline
0 & \mbox otherwise\end{matrix}$$

# Bias or Variance

1. High bias (underfit) : $J_{train}(\theta)\approx J_{cv}(\theta): high,\ \lambda: high$, simple NN, cheaper
2. Just right, $\lambda: intermediate$
3. High variance (overfit): $J_{train}(\theta): low\ \lt\lt\ J_{cv}(\theta): high,\ \lambda: small$, increase training set could help, large NN, expensive: icnrease $\lambda$

# Regularization

1. Create a list of lambdas (i.e. $\lambda\in\{0,0.01,0.02,0.04,0.08,0.16,0.32,0.64,1.28,2.56,5.12,10.24\}$);
2. Create a set of models with different degrees or any other variants.
3. Iterate through the $\lambda$ and for each $\lambda$ go through all the models to learn some $\Theta$.
4. Compute the cross validation error using the learned $\Theta$ (computed with $\lambda$) on the $J_{CV}(\Theta)$​ without regularization or $\lambda=0$.
5. Select the best combo that produces the lowest error on the cross validation set.
6. Using the best combo $\Theta$ and $\lambda$, apply it on $J_{test}(\Theta)$ to see if it has a good generalization of the problem.

# ML system design

Spam classifier

* Collect lots of data ("honeypot" project)
* develop sophisticated features (from header)
* develop sophisticated features (from body)
* develop sophisticated algorithm to detect misspellings

# Error analysis
* implement simple algorithm quickly (one day) and test on your cross validation data
* plot learning curves to decide if more data, features are likely to help
* manual error analysis
 * categorize
 * identify candidates features to correct
* define a numerical evaluation: cross validation error





# Error Metrics for Skewed Classes





|           |   | Actual | class |
|-----------|---|--------|-------|
|           |   | 1      | 0     |
| Predicted | 1 | TP     | FP    |
| class     | 0 | FN     | TN    |


* A good classifier should have both a high precision and high recall on the cross validation set

* Do you identify the actual positive?
$$ \text{Recall}
= \frac{\text{true positives}}{\text{# of actual positive}}
= R = \frac{TP}{TP+FN} $$

* Are your positive predictions correct?
$$ \text{Precision}
= \frac{\text{true positives}}{\text{# of predicted positive}}
= P = \frac{TP}{TP+FP} $$



|                | Threshold  | Precision     | Recall       |
|-----------------------|-----|---------------|--------------|
| Baseline              | 0.5 | Intermediate  | Intermediate |
| Avoid false positives | 0.7 | High          | Low          |
| Avoid false negatives | 0.3 | Low           | High         |


$$ \text{Average}
= \frac{P+R}{2}
$$

<!---
$$ \text{average}
= \frac{P+R}{2}
= \frac{1}{2}\left(\frac{TP}{TP+FP} + \frac{TP}{TP+FN}\right)
= \frac{1}{2}\left(\frac{TP(TP+FN+TP+FP)}{(TP+FP)(TP+FN)}\right)
= \frac{1}{2}\left(\frac{TP(TP+FN+TP+FP)}{(TP+FP)(TP+FN)}\right)$$
-->

\begin{align}
F_1 \;\text{score} 
&= 2\cdot\frac{P\cdot R}{P+R}
= 2\cdot 
\frac{\frac{TP}{TP+FP}\frac{TP}{TP+FN}}
{\frac{TP}{TP+FP}+\frac{TP}{TP+FN}}
\\
&= 2\cdot 
\frac{\frac{(TP)^{2}}{(TP+FP)(TP+FN)}}
{\frac{TP(TP+FN+TP+FP)}{(TP+FP)(TP+FN)}}
= \frac{2(TP)}{2(TP)+FN+FP}
\end{align}

$$ F_1 \;\text{score} 
= 2\cdot\frac{P\cdot R}{P+R} $$


$$ \text{Accuracy}
= \frac{\text{true positives}+\text{true negatives}}
{\text{# of examples}}
= \frac{TP+TN}{TP+FP+TN+FN} $$

|Alg| Precision (P)| Recall (R)| Average| $F_1 \text{score}$ |
|---|------|------|------|-------|
| 1 | 0.5  | 0.4  | 0.45 | 0.444 |
| 2 | 0.7  | 0.1  | 0.4  | 0.175 |
| 3 | 0.02 | 1.0  | 0.51 | 0.039 |


```
#TP = 80; FP = 20;
#FN = 80; TN = 820;


TP = 85; FP = 890;
FN = 15; TN = 10;


# Actual: 1: 1% spam / 0: 99% not spam

# predict all spam (y=1)
#TP = 1; FP = 99;
#FN = 0; TN = 0;

# predict all not spam (y=0)
TP = 0; FP = 0;
FN = 1; TN = 99;

'''
The classifier achieves 99% accuracy on the training set because of
how skewed the classes are. We can expect that the cross-validation set 
will be skewed in the same fashion, 
so the classifier will have approximately the same accuracy.

Since 99% of the examples are y = 0,
always predicting 0 gives an accuracy of 99%.
Note, however, that this is not a good spam system,
as you will never catch any spam.
'''

print("Recall: ", recall(TP,FN))
n = TP + FP + TN + FN
print("Accuracy: ", accuracy(TP,TN,n))


def precision(TP,FP):
  return TP / (TP+FP)


def recall(TP,FN):
  return TP / (TP+FN)


def average(P,R):
  return (P+R)/2


def f1_score(P,R):
  return 2*P*R/(P+R)


def accuracy(TP,TN,n):
  return (TP+TN)/n




P = precision(TP,FP)
R = recall(TP,FN)
# Total examples
n = TP + FP + TN + FN


print("Precision: ", P)
print("Recall: ", R)
print("Average: ", average(P,R))
print("F1 Score: ", f1_score(P,R)) 
print("Accuracy: ", accuracy(TP,TN,n))
```


```
import numpy as np

P = [0.5, 0.7, 0.02]
R = [0.4, 0.1, 1.0]

P = np.array(P)
R = np.array(R)

def average(P,R):
  return (P+R)/2

def f1_score(P,R):
  return 2*P*R/(P+R)

print("Average: ", average(P,R))
print("F1 Score: ", f1_score(P,R)) 
```

    Average:  [0.45 0.4  0.51]
    F1 Score:  [0.44444444 0.175      0.03921569]


# Data for ML

* features contain sufficient information to predict, e.g. human expert can predict y when given only x
* low bias with many parameters could use large dataset, if few parameters it will underfit
* Threshold
 * Low = more y = 1 predictions.
 So more true positives and less false negatives
 Therefore higher recall
 * High = more y = 0 predictions.
 So less true positives and more false negatives.
 Therefore lower recall
* Using very large training set makes it unilikely for model to overfit
 * A sufficiently large training set will not be overfit, as the model cannot overfit some of the examples without doing poorly on the others.
* on skewed datases (much more positive or negative), accuracy is not a good metric, you should use F-score based on precision and recall
* if your model is underfitting, obtain more data is unlikely to help


# SVM: Support Vector Machine

Large margin classifier

It could be derived from an alternative interpretation of the logistic regression.

The hypothesis function of the Logistic Regression is:

$$ h_\theta(x) = \frac{1}{1+e^{-\theta^Tx}} $$ 

Let's simplify the notation with $ z = -\theta^Tx $

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


Optimization convex: global minimum


```
import numpy as np
import matplotlib.pyplot as plt

plt.style.use(['dark_background'])
plt.rcParams.update({'font.size': 14})


z = np.arange(-5, 5., 0.1)

def LogReg_hypothesis(z):
  hypothesis = 1./(1 + np.exp(-z))
  return hypothesis

hypothesis = LogReg_hypothesis(z)
plt.scatter(z, hypothesis)

plt.legend(['$\\dfrac{1}{1+e^{-z}}$'])
plt.xlabel('$z = \\theta^{T}x $')
plt.ylabel('Hypothesis: $h_\\theta(x)$');


```

Its cost function
$$ \mathrm{Cost}(h_\theta(x),y) = -y \log(h_\theta(x)) - (1-y)\log(1-h_\theta(x)) $$

As we replace the simplified Logistic Regression hypothesis  function

$$ \mathrm{Cost}(z,y) = -y \log\frac{1}{1+e^{-z}} - (1-y)\log\left(1-\dfrac{1}{1+e^{-z}}\right) $$

Let's look to the extreme cases:
1. $ y=1 \implies \mathrm{cost}_1 = -\log\;\dfrac{1}{1+e^{-z}} $
2. $ y=0 \implies \mathrm{cost}_2 = -\log\;\left(1-\dfrac{1}{1+e^{-z}}\right)$


```
z = np.arange(-3, 3., 0.1)

def LogReg_cost_function(z, y):
  cost = - y*np.log(1./(1 + np.exp(-z)))-(1-y)*np.log(1- 1./(1 + np.exp(-z)))
  return cost

# plt.legend(['$\\text{cost}_1$, if $y=1$','$\\text{cost}_2$, if $y=0$'])
cost1 = LogReg_cost_function(z, y=1)
#cost_1 = -np.log(1./(1 + np.exp(-z)))
cost2 = LogReg_cost_function(z, y=0)
#cost_2 = -np.log(1- 1./(1 + np.exp(-z)))

plt.figure(figsize=(8,6))
plt.plot(z, cost1, 'bs',
         z, cost2, 'g^')
plt.legend(['$ y=1,\, cost_1 = -\log\;\\dfrac{1}{1+e^{-z}}$',
            '$ y=0,\; cost_2 = -\log\;\\left(1-\\dfrac{1}{1+e^{-z}}\\right)$'])
plt.xlabel('$z = \\theta^{T}x $')
plt.ylabel('Cost Function: $J(h_\\theta(x),y) $')
#plt.axis([0, 1, 0, 5])
plt.show()
```

If we consider the regularization terms

\begin{equation*}
\mathop{\mbox{min}}_\theta\ 
\frac{1}{m}\sum_{i=1}^{m}
\left[
  y^{(i)} \text{cost}_1(\theta^Tx^{(i)})
  + (1-y^{(i)}) \text{cost}_0(\theta^Tx^{(i)})
\right]
+\frac{\lambda}{2m} \sum_{j=1}^n \theta^2_j
\end{equation*}




```
import pandas as pd


z = np.arange(-3, 3., 0.1)

cost1 = np.zeros(len(z))
idx = np.where(z<1)
cost1[idx] = SVM_linear(z[idx],a=-1,b=1)

cost0 = np.zeros(len(z))
idx = np.where(z>-1)
cost0[idx] = SVM_linear(z[idx],a=1,b=1)

plt.plot(z,cost0,label='cost0')
plt.plot(z,cost1,label='cost1')
plt.legend();

pd.DataFrame({'z': z,
              'cost1': cost1,
              'cost2': cost2}).round(2).head()
```


We could rewrite this as:

\begin{equation*}
\mathop{\mbox{min}}_\theta\ 
C \sum_{i=1}^{m}
\left[
  y^{(i)} \text{cost}_1(\theta^Tx^{(i)})
  + (1-y^{(i)}) \text{cost}_0(\theta^Tx^{(i)})
\right]
+\frac{1}{2} \sum_{j=1}^n \theta^2_j
\end{equation*}

$J = y^{(i)} \text{cost}_1(\theta^Tx^{(i)}) + (1-y^{(i)}) \text{cost}_0(\theta^Tx^{(i)}) $

* if $y^{(i)}=0 \implies J = \text{cost}_0(\theta^Tx^{(i)})$
 * if $\theta^Tx^{(i)}\le -1 \implies \text{cost}_0 = 0$
* if $y^{(i)}=1 \implies J = \text{cost}_1(\theta^Tx^{(i)})$
 * if $\theta^Tx^{(i)}\ge 1 \implies \text{cost}_1 = 0$

Therefore $J=0$
* if $y^{(i)}=0$ and $\theta^Tx^{(i)}\le -1$ or
* if $y^{(i)}=1$ and $\theta^Tx^{(i)}\ge 1$

if the regularization parameter $C$ is very large, $C=100.000$, so is highly sensible to outliers

$$ C \approx \frac{1}{\lambda} $$




```
z = np.arange(-3, 3., 0.1)


def SVM_linear(z,a,b):
  return a*z + b


def SVM_cost0(z):
  cost0 = np.zeros(len(z))
  idx = np.where(z>-1)
  cost0[idx] = SVM_linear(z[idx],a=1,b=1)
  return cost0


def SVM_cost1(z):
  cost1 = np.zeros(len(z))
  idx = np.where(z<1)
  cost1[idx] = SVM_linear(z[idx],a=-1,b=1)
  return cost1
  

def SVM_cost_function(z, y):
  cost = y*SVM_cost1(z) + (1-y)*SVM_cost0(z)
  return cost

cost1 = SVM_cost_function(z, y=1)
cost2 = SVM_cost_function(z, y=0)

plt.figure(figsize=(8,6))
plt.plot(z, cost1, 'bs',
         z, cost2, 'g^')
plt.legend(['$ y=1,\, cost_1 $',
            '$ y=0,\; cost_0 $'])
plt.xlabel('$z = \\theta^{T}x $')
plt.ylabel('Cost Function: $J(z,y) $')
plt.show()
```


```
x1 = np.arange(-1, 6., 0.1)
x2 = np.arange(-1, 6., 0.1)
theta0 = -3
theta1 = 1
theta2 = 0
y = theta0 + theta1*x1 + theta2*x2
predict = np.zeros(len(y))
idx = np.where(y>0)
predict[idx] = 1
predict
```




    array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
           0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
           0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
           1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
           1., 1.])



## Kernels

Non-linear decision boundary

Gaussian

Given $x$, compute new feature $f_i$ depending on proximity to landmarks $l$ (new features)

\begin{equation*}
f_1 =\text{similarity}(x,l^{(1)})
= \exp\left(-\frac{\left\Vert x-l^{(1)} \right\Vert^2}{2\sigma^2}\right)
\end{equation*}

$sim(x,l^{(1)}) \in [0,1]$

If $ x = l^{(1)} $:
\begin{equation*}
f_1 
= \exp\left(-\frac{0^2}{2\sigma^2}\right)
= 1
\end{equation*}


If $ x \approx l^{(1)} $:
\begin{equation*}
f_1 
\approx \exp\left(-\frac{0^2}{2\sigma^2}\right)
\approx 1
\end{equation*}

If $x$ far from $l^{(1)}$:
\begin{equation*}
f_1 
\approx \exp\left(-\frac{\left(\text{large number}\right)^2}{2\sigma^2}\right)
\approx 0
\end{equation*}


* C: regularization parameter (large: all data must fit, including outlier, overfit)
* $\sigma$ bandwith how fast the similarity metric decreases (to 0)

* Large C
 * lower bias
 * higher variance (overfit)
 * ~ small $\lambda$
* Small C
 * higher bias (underfit)
 * lower variance
 * ~ large $\lambda$

* Large $\sigma^2$
 * features $f_i$ vary more smoothly
 * higher bias
 * lower variance

* Small $\sigma^2$
 * features $f_i$ vary less smoothly
 * lower bias
 * higher variance


* Overfit
 * Decrease C
 * Increase $\sigma^2$

* Underfit
 * Increase C
 * Decrease $\sigma^2$


Options for kernels
1. No kernels (Linear Kernel)
 * n (feature) large, m (train set) small

2. Gaussian Kernel
 * need to choose $\sigma^2$
 * n small and/or m large
 * perform feature scaling

Other kernels
* polynomial : $(x^T l + \text{constant})^\text{degree}$
* string, chi-square, histogram, intersection

Multi-class classification
* packages
* one vs all method
 * $K$ classes $ \implies K$ classifiers





```
l_1 = 5
x1 = 3

x = np.arange(0,10,0.1)
sigma = 1
f_1 = np.exp(-(x-l_1)**2/(2*sigma**2))
plt.plot(x,f_1);
```


```
sigma = 2
f_1 = np.exp(-(x-l_1)**2/(2*sigma**2))
plt.plot(x,f_1);
```

# Logistic regression vs SVMs
* $n$: number of features
* $m$: number of training examples

If $n \gg m $ ($n=10.000$, $m=10\cdot\cdot\cdot1.000$)
* Logistic regression
* SVM without a kernel

If $n$ is small, $m$ is intermediate ($n=1\cdot\cdot\cdot1.000$, $m=10\cdot\cdot\cdot10.000$)
 * SVM with Gaussian kernel

If $n \ll m $ ($n=1\cdot\cdot\cdot1.000$, $m=50.000+$)
* Create/add more features
 * Logistic regression
 * SVM without a kernel

Neural network likely to work well for most of these settings, but may be slower to train

Logistic regression and SVM without a kernel
* provides a linear straight line decision boundary

$n=10$ features and $m=5000$ examples
* logistic regression classifier with gradient descent
 * training set: underfit (reduced performance on training or cross-validation sets)

* create/ add new polynomial features
* logistic regression cost function is convex, so gradient descent will always find the global minimum

# Spam

https://spamassassin.apache.org/old/publiccorpus/


```

```


```
# TODO
import sys

z = np.arange(-3, 3., 0.1)

def SVM_linear(z,a,b):
  return a*z - b

def SVM_cost_function(z, y):
  cost = np.zeros(len(z))
  b = 0.5
  if y == 1:
    cost1 = [SVM_linear(i,a=-1,b) if z<1 for i in z]
  elif y == 0:
    cost0 = [SVM_linear(i,a=1,b) if z>-1 for i in z]
  else:
    sys.exit('ERROR: Not programmed such y. Please enter 0 or 1') 

  
  return cost

cost1 = np.zeros(len(z))

cost1[z<1] = [SVM_linear(i,a=-1,b) if z>-1 for i in z]
```

44ce8f2c61ed2e520d56d1ccb35c196aeec63505
ipynb
Jupyter Notebook
GoogleColab/MachineLearningStanford.ipynb
viniciusriosfuck/dscodenation
b59fb4417f6b348538f500123fe0ed4d048e2505
MIT
2020-11-09T18:18:41.000Z
2020-11-09T18:18:41.000Z
GoogleColab/MachineLearningStanford.ipynb
inaborges/dscodenation
710113aeed64f3302fe207201a967cc7cdc9e8e7
MIT
2020-07-21T17:28:07.000Z
2020-08-05T22:30:35.000Z
GoogleColab/MachineLearningStanford.ipynb
inaborges/dscodenation
710113aeed64f3302fe207201a967cc7cdc9e8e7
MIT
2020-07-21T22:40:33.000Z
2020-07-21T22:40:33.000Z
Qwen/Qwen-72B
1. YES
2. YES