Machines Learning 学习笔记(Week3)

#Supervised Learning

##Classification Problem

**1. Hypothesis Function:**

- "Sigmoid Function" or "Logistic Function":
$g(z) = \frac{1}{1+e^{-z}} $

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

![Logistic_function.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/d0d04a44-0809-0c40-3caf-3244334744aa.png)

- Interpretation:
the probability that our output is 1
$h_\theta(x) = P(y=1|x;\theta) = 1 - P(y=0|x;\theta) $

- Decision Boundary:
    - when 
$h_\theta(x) \geq 0.5 \rightarrow y=1, h_\theta(x) < 0.5 \rightarrow y=0$
means $g(z) \geq 0.5 \rightarrow z \geq 0 \rightarrow y=1 $
    - z is the input (e.g. $z = \theta^Tx$)
    - decision boundary could be any shape:
    
<img width="203" alt="DB.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/6945787b-a34d-ffbd-dd61-ab9e4e1421e0.png"><img width="285" alt="NLDB.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/6c8c5ae2-a96d-2f25-37df-1a9479283e26.png">

**2. Cost Function:**

```math
J(\theta) = - \frac{1}{m}
\sum_{i=1}^{m}
\Bigl[y^{(i)}log\bigl(h_\theta(x^{(i)})\bigr)
+(1-y^{(i)})log\bigl(1-h_\theta(x^{(i)})\bigr)
\Bigr]
```

Vectorized implementation:
$h=g(X\theta)$
$J(\theta)=\frac{1}{m} \bigl(-y^Tlog(h)-(1-y)^Tlog(1-h)\bigr)$

**3. Gradient Descent:**
Repeat {

```math
\theta_j := \theta_j- \frac{\alpha}{m}
\sum_{i=1}^{m}
\bigl(h_\theta(x^{(i)})-y^{(i)}\bigr)x_j^{(i)}
```

}
Vectorized implementation:
$\theta := \theta - \frac{\alpha}{m}X^T\bigl(g(X\theta)-\vec{y}\bigr)$

##Advanced Optimization
- Optimization algorithms:
 - Gradient descent
 - Conjugate gradient
 - BFGS
 - L-BFGS

Code:
First, we need to provide a function that evaluates both 
$J(\theta)$, and
$\frac{\alpha}{\alpha\theta_j}J(\theta)$

```matlab
function [jVal, gradient] = costFunction(theta)
  jVal = [...code to compute J(theta)...];
  gradient = [...code to compute derivative of J(theta)...];
end
```

Then we use "fminunc()" optimization algorithm along with the "optimset()" function that creates an object containing the options we want to send to "fminunc()".

```matlab
options = optimset('GradObj', 'on', 'MaxIter', 100);
initialTheta = zeros(2,1);
   [optTheta, functionVal, exitFlag] = fminunc(@costFunction, initialTheta, options);
```

##Multiclass Classification: One-vs-all
Multiclass means y = {0,1, ... ,n}. Simply apply the same logistic algorithem to each class:

Train a logistic regression classifier $h_\theta(x)$ for each class￼ to predict the probability that ￼ ￼y = i￼ ￼.

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

<img width="486" alt="MCC.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/4073ceb5-6343-14ad-a352-be57b920f241.png">

## The Problem of Overfitting

Too many features, too complicated function - high variance:
<img width="553" alt="overfit.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/7c1f5936-30fb-a2b3-01eb-901900a55f3a.png">

**1. Regularized Cost Function:**
regularize all of our theta parameters in a single summation:

```math
min_\theta \rightarrow J(\theta)= \frac{1}{2m}\Biggl[ 
\sum_{i=1}^m \bigl(h_\theta(x^{(i)})-y^{(i)} \bigr)^2 +
\lambda\sum_{j=1}^n\theta_j^2  \Biggr]
```

The $\lambda$, or lambda, is the regularization parameter.

**2. Regularized Gradient Descent:**

- Regularized Linear Regression:

Repeat {

```math
\theta_0 := \theta_0 - \alpha\frac{1}{m} \sum_{i=1}^m \bigl(h_\theta(x^{(i)})-y^{(i)}\bigr)x_0^{(i)}
```

```math
\theta_j := \theta_j - \alpha \Biggl[ \Bigl(\frac{1}{m} \sum_{i=1}^{m} \bigl(h_\theta(x^{(i)})-y^{(i)} \bigr)x_j^{(i)}\Bigr)+\frac{\lambda}{m}\theta_j \Biggr]\qquad j\in {1,2...n}
```

}

$\theta_j$ can also be represented as:
$\theta_j := \theta_j(1-\alpha\frac{\lambda}{m})-\alpha\frac{1}{m} \sum_{i=1}^m \bigl(h_\theta(x^{(i)})-y^{(i)})x_j^{(i)}$

Intuitively, you can see it as reducing the value of $\theta_j$ by some amount on every update.

- Normal Equation:

$\theta = (X^TX+\lambda L)^{-1}X^Ty$
where $L$ = 

```math
\begin{bmatrix}
0& & & &  \\
 &1& & &  \\
 & &1& &  \\
 & & &\ddots& \\
 & & & &1\\
\end{bmatrix}\qquad (n+1) \, x \, (n+1) \, dimension
```

- Regularized Logistic Regression:

Repeat {

```math
\theta_0 := \theta_0 - \alpha\frac{1}{m} \sum_{i=1}^m \bigl(h_\theta(x^{(i)})-y^{(i)}\bigr)x_0^{(i)}
```

```math
\theta_j := \theta_j - \alpha \Biggl[ \Bigl(\frac{1}{m} \sum_{i=1}^{m} \bigl(h_\theta(x^{(i)})-y^{(i)} \bigr)x_j^{(i)}\Bigr)+\frac{\lambda}{m}\theta_j \Biggr]\qquad j\in {1,2...n}
```

}
 
>Cost function (regularized):
$J(\theta) = - \frac{1}{m}
\sum_{i=1}^{m}
\Bigl[y^{(i)}log\bigl(h_\theta(x^{(i)})\bigr)
+(1-y^{(i)})log\bigl(1-h_\theta(x^{(i)})\bigr)
\Bigr]+\frac{\lambda}{2m}\sum_{j=1}^n\theta_j^2$