Week 10: Online Learning

Online Learning을 사용하는 경우는 아래와 같다.

• 연산량이 너무 많을 때
• 데이터가 스트리밍 이여서 새로운 데이터 대해서 계속 해서 학습 해야할 때 또는 데이터가 사용자에 의해서 계속 생성 될 때

알고리즘

Repeat forever {
Get (x,y) corresponding to a user.
update $\theta$ using (x,y)
$\theta_{j}$ := $\theta_j$ -\alpha ($h_{\theta}$(x)-y)$x_j$ (j=0,...,n)
}

결국 fixed training데이터를 사용하지 않게 된다.
또한 한번 training에 사용 했던 데이터는 다시 쓰지 않는다.

p(y = 1|x; θ)
Probability that y =1, given x, parameterized by θ

사용 예

• shipping service를 사용자가 선택 할지 안할지에 대한 정보를 웹사이트 데이터로 구축해서 누적 한다.
• product search를 할 때 사용자가 선택한 옵션에 맞추어서 가장 인기있는 phone 10개를 보여주고 그것에대한 선호도를 선택하게 한다. 이러한 결과는 즉시 다시 학습에 사용 될 수 있다.

Quiz

Week 05: 2. Backpropagation Algorithm

본 장에서는 각각의 레어이어의 Wegiht을 학습하기위한 backpropagation알고리즘에 대해서 다룬다.

Gradient computation with forward propagation

각각의 Layer의 wegiht 초기 값을 결정하기 위해서 아래와 같이 forward propagation을 수행하게 된다.

아래와 같이 각각의 레이어에 맞는 $a^{(j)}$ 값들이 결정 된다.

Gradient computation: Backpropagation algorithm

Bakpropagatio 알고리즘의 목적은 각각의 $\theta$값들이 Cost function $J$에 미치는 영향을 효율적으로 계산하는 것이다. 즉Gradient를 계산 하는 것이다.

Gradient를 구하게 되면, Gradient descent알고리즘으로 아래와 같이 cost $J$를 최소화 하는 $\Theta$를 찾을 수 있다.

$$ min_{\theta}J(\theta) $$

Gradient는 아래와 같이 편미분을 수행 해야 한다.

$$\dfrac{\partial}{\partial \Theta_{i,j}^{(l)}}J(\Theta)$$

이것을 빨리 계산하기 위해서 Backpropagation알고리즘을 이용한다.

각각의 레어이어의 노드 j에서의 에러는 아래와 같이 정의된다.

$\delta_{j}^{(l)}$ = error of node $j$ in layer $l$.

마지막 레이어 에서의 error 값은 델타는 아래와 같이 계산 된다.
$$ \delta^{(L)} = a^{(L) - y} $$
L은 총 레이어의 수를 의미하고 $a^{L}$은 마지막 레이어에서의 activiation unit의 output이다.

각 레이어의 local error를 나타내는 식은 아래와 같이 $\delta$로 표현 된다.

$$\delta^{(l)} = ((\Theta^{(l)})^T \delta^{(l+1)})\ .*\ g'(z^{(l)})$$

이후 뉴런 계층도 아래와 같이 계산된다.
$$\delta^{(3)} = ((\Theta^{(3)})^T \delta^{(4)})\ .*\ g'(z^{(3)})$$

$$\delta^{(2)} = ((\Theta^{(2)})^T \delta^{(3)})\ .*\ g'(z^{(2)})$$

$\delta^{(L)}$를 이용해서 나머지 $\delta$들의 값들은 위와 같이 계산된다.
여기서 $\delta^{(1)}$이 없는 이유는 input 값을 변경하지 않기 위함이다.
input은 error로 생각하지 않는다.

식 유도하기

우선, network 구조는 위의 네트웍을 따른다.

이제 아래와 같이 $\theta^{(3)}$이 Cost function에 미치는 영향(gradient)을 계산해보자.

Sigmoid derivative
$$g(x) = \dfrac{1}{1 + e^{-x}}$$
$$\dfrac{d}{dx}g(x) = g(x)(1 - g(x))$$

Chain rule에 의해서 Cost function은 다음과 같이 편미분 된다.
Cost function을 미분을 간단하기 위해서 cross entropy가 아닌 square error로 생각하자. 그리고 non-multiclass classification (k=1)로 생각한다. 그럼 아래의 cross entropy가 간단해 진다.
실제로도 거의 유사하게 동작하기 위해서 만들어진 cost function이다.

$$cost(t) =y^{(t)} \ \log (h_\Theta (x^{(t)})) + (1 - y^{(t)})\ \log (1 - h_\Theta(x^{(t)}))$$

$$Cost = \frac{1}{2}(\hat{y}-y)^2$$

$$ \frac { \partial Cost }{\partial \theta^{ (3) }} = \frac { \partial Cost } {\partial a^{(4)} } \cdot \frac { \partial a^{(4)} }{\partial z^{ (4) }} \cdot \frac { \partial z^{(4)}} {\partial \theta ^{ (3) }} $$

$$ = (\hat{y}-y) \times g(z^{(4)})(1-g(z^{(4)}))\times a^{ (3) }$$

$$ = (\hat{y}-y) \times \hat{y}(1-\hat{y})\times a^{ (3) }$$

결국 $g(z^{(4)})=a^{(4)}$는 예측 값이므로 $\hat{y}$로 치환한 것이다.
그리고 특정 부분을 $\delta^{L}$로 치환 하면 아래와 같다.
여기서 $L$은 마지막 Layer를 의미한다.

$$\delta ^{ (L) }= (\hat{y}-y) \times \hat{y}(1-\hat{y})$$

$$=\delta^{(L)}\times a^{ (3) }$$

두 번째는 $\theta^{(2)}$이 Cost function에 미치는 영향을 계산해보자.

$$\frac { \partial Cost }{\partial \theta^{ (2) }} = \frac { \partial Cost } {\partial a^{(4)} } \cdot \frac { \partial a^{(4)} }{\partial z^{ (4) }} \cdot \frac { \partial z^{(4)}} {\partial a^{(3)}} \cdot \frac { \partial a^{(3)}} {\partial z^{(3)}} \cdot \frac { \partial z^{(3)}} {\partial \theta^{(2)}} $$

$$=(\hat{y}-y) \times \hat { y } (1-\hat { y } )\times \theta ^{ (3) }\times \frac { \partial a^{(3)}} {\partial z^{(3)}} \times \frac { \partial z^{(3)}} {\partial \theta^{(2)}}$$

나머지 뒷 부분도 모두 미분하면 아래와 같이 유도 된다.

$$=(\hat{y}-y) \times \hat { y } (1-\hat { y } )\times \theta ^{ (3) }\times g(z^{(3)})(1-g(z^{(3)}))\times a^{(2)} $$

여기서도 위와 마찬가지로 $\delta^{(3)}$을 정의해서 치환 하면 아래와 같다.

$$\delta^{(3)} = (\hat{y}-y) \times \hat{y}(1-\hat {y} )\times \theta^{(3)}\times g(z^{(3)})(1-g(z^{(3)}))$$

$$ \frac { \partial Cost } {\partial \theta ^{ (2) }} = \delta^{(3)}\times a^{ (2) }$$

그리고 $\delta^{(3)}$을 계산하기 위해서 앞에서 계산된 $\delta^{(L)}$을 활용할 수 있다.

$$\delta^{(L)} = (\hat{y}-y) \times \hat { y } (1-\hat { y } )$$

$$\delta^{(3)} = \delta ^{(L)} \times \theta^{(3)}\times g(z^{(3)})(1-g(z^{(3)}))$$

결국 생각해보면 각각의 $\delta$만 계산할 수 있다면, 해당 $\theta$즉 wegiht가 Cost function에 미치는 영향(Gradient)를 계산할 수 있다.
왜냐하면, $a^{(3)}$, $a^{(2)}$같은 값들은 forward propagation을 통해서 쉽게 구할 수 있기 때문이다.
그리고 각 layer에서의 gradient는 앞에서 계산한 delta를 활용하여 계산량을 줄일 수 있다.

$\delta_j^{(l)}$의 의미는 $a_j^{(l)}$에 대한 에러이다.
좀 더 formal하게 표현 하면 delta values are actually the derivative of the cost function:

$$\delta_j^{(l)} = \dfrac{\partial}{\partial z_j^{(l)}} cost(t)$$

결국 아래와 같이 Andrew Ng교수님이 말한 식이 유도 된 것이다.

$$\delta^{(l)} = ((\Theta^{(l)})^T \delta^{(l+1)})\ .*\ g'(z^{(l)})$$

$$ \frac { \partial Cost } {\partial \theta^{(l)}}=a^{(l)}\delta^{(l+1)}$$

결국 아래의 Andrew Ng 교수님 수업에서 말한 식이 도출 되었다.

Analyzing the mathematics

위 예제는 결국 [3-5-5-5]의 구조를 가진다. bais는 생각하지 않는다.
$\theta^{3}$는 [4 X 5]의 matrix 이다. bias를 포함하면 4 X 6 이지만 그렇게 생각하지 않는다.
$(\theta^{(3)})^{T}$라고 하면 결국 transpose 이기 때문에 [5 X 4] matrix가 된다.

이전에 계산한 $\delta^{4}$는 4x1 vector라고 하자.
[5 X 4] matrix with [4 X 1] vector를 계산하면 결국 [5 X 1] vector가 된다.
[5 X 1] matrix의 dimensionality는 $a^3$ vector와 같게 된다. 따라서 pairwise multiplication이 성공 한다.

결국, $\delta^{3}$은 $a^3.*(1-a^3)$이랑 연산을해서 구해 질 수 있다.
$\delta^2$도 마찬가지로 구할 수 있다.

Why do we do this?

모든 $\delta$를 계산 했다면 그것을 가지고
Cost function에 대한 각각의 $\theta$에 따른 Partial Derivative를 구할 수 있다.
이러한 Partial Derivative를 통해서 $\theta$값들이 Cost Function에 미치는 영향을 알 수 있다.
그리고 이 영향을 이용해서 gradient descent를 수행해서 최적화를 달성 할 수 있다.

Backpropagation의 장점은 이런한 각각의 $\theta$값을 $\delta$를 이용해서 효율적으로 구할 수 있다는 것이다.
하지만 이 방법을 이용하면 쉽게 구할 수 있다.

결국 아래와 같이 regularization을 람다 0으로 설정해서 무시한다면 간단한 식이 완성 된다.
$$ \dfrac{\partial}{\partial \Theta_{i,j}^{(l)}}J(\Theta) = a_j^l \delta_i^{(l+1)}$$

그리고 이러한 partial derivative 값들을 이용해서 cost function을 최소화 하는 $\theta$값들을 찾게 된다.
즉 각각의 $\theta$가 y에 미치는 영향을 계산하여 각각의 $\theta$를 업데이트 할 수 있는 것이다.

좀 더 자세한 Python기반 코드는 링크에 있다.

알고리즘 상세 설명

Training set이 아래와 같이 있다고 가정해 보자.
$\lbrace (x^{(1)}, y^{(1)}) \cdots (x^{(m)}, y^{(m)})\rbrace$

최종적인 델타값은 모든 트레닝에 대해서 각각의 델타값을 누적한다음 평균값을 구해야 한다.
따라서 누적을 위한 델타 값을 아래와 같이 0으로 설정한다.
$\Delta^{(l)}_{i,j}$

이제 루프를 전 트레이닝 셋에 대해서 돌면서 수행 한다.

For t = 1 to m 까지

$a^{(1)}$은 $x^{(t)}$로 초기화 된다.
forward propagation을 통해서 각각의 layer에 있는 $a^l$들을 계산한다. l=1,2,..,L 까지 존재한다.
그다음 output label과 함께 $\delta^L$을 계산하고 그것을 이용해서 순차적으로 $\delta^L=a^L-y^t$를 계산하게 된다.
이렇게 함으로써 초기 delta 값들이 구해진다.
그다음 back propagation을 통해서 L-1 layer 를 구하고 차큰 차큰 내려 간다.
그리고 각 layer에서의 델타들을 아래와 같이 누적 시킨다.

여기서,

• $l$ = layer
• $j$ = node in that layer
• $i$ = the error of affected node in the target layer

위의 것을 vectorize하면 아래와 같다.

Finally
Loop를 모두 실행 하면 아래와 같이 누적한 값으로 평균 값을 구한다.
해당 평균 에러는 모든 트레이닝 데이터에 대한 값이 된다.

최종 Cost function J에 대한 partial derivative는 아래와 같이 구해진다.

결국 이를 통해서 각각의 $\theta$즉 parameter에 대한 partial derivative를 계산 할 수 있게 된다.
출력값에 미치는 영향을 계산 할 수 있으므로 이를 조정 할 수 있게 된다.

강의 슬라이드 페이지는 아래와 같다.

사실, Back-propagation의 좀 더 자세한 내용은 많인 강의에서 다루지 않는다.
이것도 나름 상세한 강의에 속하는 것 같다.
대략적인 컨셉과 수식적 표현은 알겠는데 아직 까지 남에게 설명할 정도는 안되는 것 같다.

Week 05: Neural Network Cost Function

1. Cost Function

Training Set은 아래와 같다고 하자.
$$ (X^1,y^1),(x^2,y^2),(x^3,y^3)...(x^n,y^m) $$

$L$은 network에 존재하는 Layer의 수이다.
아래와 같은 network 모형에서는 $L$은 4이다.
$s_{l}$은 layer $l$에서의 unit의 숫자이다. 단 여기서 bias unit은 카운트 하지 않는다.

결국, 아래와 같은 값을 가지게 된다.

• $l$ = 4
• $s_1$ = 3
• $s_2$ = 5
• $s_3$ = 5
• $s_4$ = 4

2. Types of classification problems with NNs

Binary Classification

당연히 output은 0,1 이다.
k = 1 이다.

Multi-class classification

k개의 distinct classifications가 존재 한다.
$y$는 k-dimensional vector of real numbers이다.
모습은 아래와 같다.

Cost function for neural networks

일반적인 (regularized) logistic regression cost function은 아래와 같다.

위 식에 약간의 중첩 summation을 추가한 것이다.
이것은 다중 아웃풋 노드를 처리하기 위함이다.
$h_{\theta}(x)$는 k dimensional vector이고 $h_{\theta}(x)_{i}$는 vector에서 i로 참조 되어 진다.

Cost function만 따로 띠어내면 아래와 같다.
결국, k=4라고 할 때 각각의 Logistic regression classifier를 합하게 된다.
트레이닝 데이터 1에서 m 까지에서 가능한 output vector를 모두 합친것을 의미한다.

삼중 summation 되어서 복잡해 보이지만, 그냥 단순히 모든 $\theta$를 합친다는 의미이다.
즉 l layer에서의 j 번째 unit에서 i 번째 input이나 activation과 매칭되는 모든 것들의 합을 구해서 람다 만큼 증폭을 시켜서 overfitting을 줄여주는 것이다.

최종적으로 두개의 식을 합치면 regularized neural network cost function을 아래와 같이 구할 수 있다.

Programming Exercise 4: Neural Networks Learning

This exercise is to implement the backpropagation algorithm for neural netwroks.
The application is hand-written digit recognition.

• ex4data1.mat: training set of ahnd-written digits
• ex4weights.mat: neural network parameters for exercise 4
• computeNuericalGradient.m: numerically compute gradients.

구현해야 할 함수들

• sigmoidGradient.m: compute the gradient of the sigmoid function.
• randInitializeWeights.m: randomly initialize weights.
• nnCostFunction.m: Neural network cost function.

Neural Networks

이전 과제에서는 matlab으로 feedforard propagation을 구현 했었다.
이번엔 python을 이용해서 최적의 parameter들을 찾는 backpropagation을 구현해 보도록 한다.

1.1 Visualizing the data

데이터를 읽어서 2-dimensional plot으로 표시하는 작업을 수행 한다.
5000개의 training example들로 구성 되어 있다.
각각의 손글씨 이미지들은 20 pixel by 20 pixel grayscale image로 구성되어 있다.
각각의 pixel들은 floating point number로 구성 되어 있다.
이것을 unrolled하게 된다면 400-dimensional vector로 구성 된다.
각각은 단일 row vector가 된다. 트레이닝이 5000이므로 최종적인 input X는 5000 by 400이 된다.

y는 1~9 숫자값을 가지고 있다. matlab에서는 0을 반드시 가지고 있으므로 10으로 그것을 labeled 한다.

Python 구현
필요 라이브러리 Load

%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import scipy.io #Used to load the OCTAVE *.mat files
import scipy.misc #Used to show matrix as an image
import matplotlib.cm as cm #Used to display images in a specific colormap
import random #To pick random images to display
import scipy.optimize #fmin_cg to train neural network
import itertools
from scipy.special import expit #Vectorized sigmoid function

datafile = 'data/ex4data1.mat'

mat = scipy.io.loadmat( datafile )

X, y = mat['X'], mat['y']

#Insert a column of 1's to X as usual
X = np.insert(X,0,1,axis=1)

print "'y' shape: %s. Unique elements in y: %s"%(y.shape,np.unique(y))
print "'X' shape: %s. X[0] shape: %s"%(X.shape,X[0].shape)
#X is 5000 images. Each image is a row. Each image has 400 pixels unrolled (20x20)
#y is a classification for each image. 1-10, where "10" is the handwritten "0"

출력 결과

'y' shape: (5000, 1). Unique elements in y: [ 1  2  3  4  5  6  7  8  9 10]
'X' shape: (5000, 401). X[0] shape: (401,)

이미지 출력함수

def getDatumImg(row):
    """
    Function that is handed a single np array with shape 1x400,
    crates an image object from it, and returns it
    """
    width, height = 20, 20
    square = row[1:].reshape(width,height)
    return square.T
    
def displayData(indices_to_display = None):
    """
    Function that picks 100 random rows from X, creates a 20x20 image from each,
    then stitches them together into a 10x10 grid of images, and shows it.
    """
    width, height = 20, 20
    nrows, ncols = 10, 10
    if not indices_to_display:
        indices_to_display = random.sample(range(X.shape[0]), 100)
        
    big_picture = np.zeros((height*nrows,width*ncols))
    
    irow, icol = 0, 0
    for idx in indices_to_display:
        if icol == ncols:
            irow += 1
            icol  = 0
        iimg = getDatumImg(X[idx])
        big_picture[irow*height:irow*height+iimg.shape[0],icol*width:icol*width+iimg.shape[1]] = iimg
        icol += 1
    fig = plt.figure(figsize=(6,6))
    img = scipy.misc.toimage( big_picture )
    plt.imshow(img,cmap = cm.Greys_r)

displayData()

최종적으로 10x10으로 축소해서 100장을 출력 한다.

1.2 Model representation

NN의 구성은

• 3 layers. an input layer (20x20)+1, a hidden layer, and an output layer.
• a set of network parameters ($\theta^{(1)}$,$\theta^{(2)}$)이고 이미 완벽히 학습된 parameters는ex4weights.mat에 저장되어 있다.
• $\theta^{(1)}$은 25 dimension을 $\theta^{(2)}$는 10 dimension을 가진다.

• theta1 has size 25 x 401
• theta2 has size 10 x 26
• X has size 5000 x 401
• Y has size 5000 x 1

모델 표현에 필요한 코드는 다음과 같다.

#You have been provided with a set of network parameters (Θ(1),Θ(2)) 
#already trained by us. These are stored in ex4weights.mat
datafile = 'data/ex4weights.mat'
mat = scipy.io.loadmat( datafile )
Theta1, Theta2 = mat['Theta1'], mat['Theta2']
# The matrices Theta1 and Theta2 will now be in your workspace
# Theta1 has size 25 x 401
# Theta2 has size 10 x 26

# These are some global variables I'm suing to ensure the sizes
# of various matrices are correct
#these are NOT including bias nits
input_layer_size = 400
hidden_layer_size = 25
output_layer_size = 10 
n_training_samples = X.shape[0]

#Some utility functions. There are lot of flattening and
#reshaping of theta matrices, the input X matrix, etc...
#Nicely shaped matrices make the linear algebra easier when developing,
#but the minimization routine (fmin_cg) requires that all inputs

def flattenParams(thetas_list):
    """
    Hand this function a list of theta matrices, and it will flatten it
    into one long (n,1) shaped numpy array
    """
    flattened_list = [ mytheta.flatten() for mytheta in thetas_list ]
    combined = list(itertools.chain.from_iterable(flattened_list))
    assert len(combined) == (input_layer_size+1)*hidden_layer_size + \
                            (hidden_layer_size+1)*output_layer_size
    return np.array(combined).reshape((len(combined),1))

def reshapeParams(flattened_array):
    theta1 = flattened_array[:(input_layer_size+1)*hidden_layer_size] \
            .reshape((hidden_layer_size,input_layer_size+1))
    theta2 = flattened_array[(input_layer_size+1)*hidden_layer_size:] \
            .reshape((output_layer_size,hidden_layer_size+1))
    
    return [ theta1, theta2 ]

def flattenX(myX):
    return np.array(myX.flatten()).reshape((n_training_samples*(input_layer_size+1),1))

def reshapeX(flattenedX):
    return np.array(flattenedX).reshape((n_training_samples,input_layer_size+1))

• flattenParams 들어온 matrix로 구성된 list를 단일 [n,1] matrix로 변환 한다.
• reshapeParams: 들어온 flattened_array를 다시 theta1, theta2로 변경 한다.
• flattenX 들어온 X를 [n,1]로 변경 한다.
• reshapeX flatten을 다시 X로 reshape한다.

1.3 Feedforward and cost function

Now you will implement the cost function and gradient for the neural network.
First, complete the code in nnCostFunction.m to return the cost.

nnCostFunction은 아래 4개의 인자를 입력으로 받는다.

• mythetas_flattened
• myX_flattened
• myy
• mylambda=0.

원래 참값을 아래와 같이 표현을 변경해주는 코드가 필요하다.

def computeCost(mythetas_flattened,myX_flattened,myy,mylambda=0.):
    """
    This function takes in:
        1) a flattened vector of theta parameters (each theta would go from one
           NN layer to the next), the thetas include the bias unit.
        2) the flattened training set matrix X, which contains the bias unit first column
        3) the label vector y, which has one column
    It loops over training points (recommended by the professor, as the linear
    algebra version is "quite complicated") and:
        1) constructs a new "y" vector, with 10 rows and 1 column, 
            with one non-zero entry corresponding to that iteration
        2) computes the cost given that y- vector and that training point
        3) accumulates all of the costs
        4) computes a regularization term (after the loop over training points)
    """
    
    # First unroll the parameters
    mythetas = reshapeParams(mythetas_flattened)
    
    # Now unroll X
    myX = reshapeX(myX_flattened)
    
    #This is what will accumulate the total cost
    total_cost = 0.
    
    m = n_training_samples

    # Loop over the training points (rows in myX, already contain bias unit)
    for irow in xrange(m):
        myrow = myX[irow]
                
        # First compute the hypothesis (this is a (10,1) vector
        # of the hypothesis for each possible y-value)
        # propagateForward returns (zs, activations) for each layer
        # so propagateforward[-1][1] means "activation for -1st (last) layer"
        myhs = propagateForward(myrow,mythetas)[-1][1]

        # Construct a 10x1 "y" vector with all zeros and only one "1" entry
        # note here if the hand-written digit is "0", then that corresponds
        # to a y- vector with 1 in the 10th spot (different from what the
        # homework suggests)
        tmpy  = np.zeros((10,1))
        tmpy[myy[irow]-1] = 1
        
        # Compute the cost for this point and y-vector
        mycost = -tmpy.T.dot(np.log(myhs))-(1-tmpy.T).dot(np.log(1-myhs))
     
        # Accumulate the total cost
        total_cost += mycost
  
    # Normalize the total_cost, cast as float
    total_cost = float(total_cost) / m
    
    # Compute the regularization term
    total_reg = 0.
    for mytheta in mythetas:
        total_reg += np.sum(mytheta*mytheta) #element-wise multiplication
    total_reg *= float(mylambda)/(2*m)
        
    return total_cost + total_reg
       

def propagateForward(row,Thetas):
    """
    Function that given a list of Thetas (NOT flattened), propagates the
    row of features forwards, assuming the features ALREADY
    include the bias unit in the input layer, and the 
    Thetas also include the bias unit

    The output is a vector with element [0] for the hidden layer,
    and element [1] for the output layer
        -- Each element is a tuple of (zs, as)
        -- where "zs" and "as" have shape (# of units in that layer, 1)
    
    ***The 'activations' are the same as "h", but this works for many layers
    (hence a vector of thetas, not just one theta)
    Also, "h" is vectorized to do all rows at once...
    this function takes in one row at a time***
    """
   
    features = row
    zs_as_per_layer = []
    for i in xrange(len(Thetas)):  
        Theta = Thetas[i]
        #Theta is (25,401), features are (401, 1)
        #so "z" comes out to be (25, 1)
        #this is one "z" value for each unit in the hidden layer
        #not counting the bias unit
        z = Theta.dot(features).reshape((Theta.shape[0],1))
        a = expit(z)
        zs_as_per_layer.append( (z, a) )
        if i == len(Thetas)-1:
            return np.array(zs_as_per_layer)
        a = np.insert(a,0,1) #Add the bias unit
        features = a

실행 코드

#Once you are done, using the loaded set of parameters Theta1 and Theta2,
#you should see that the cost is about 0.287629
myThetas = [ Theta1, Theta2 ]

#Note I flatten the thetas vector before handing it to the computeCost routine,
#as per the input format of the computeCost function.
#It does the unrolling/reshaping itself
#I also flatten the X vector, similarly
print computeCost(flattenParams(myThetas),flattenX(X),y)

실행 결과

0.287629165161

함수 실행

• flattenParams(myThetas) -> (10285,1) # (25*401) + (10*26) 이다.
• flattenX(X) -> (2005000, 1) #5000*401 이다.
• propagateForward는 인자로 1개의 입력 값을 받아서 thetas [theta1, theta2]가 저장된 것을 가지고 연산을 시작 한다. 최종적으로 z W*X가 저장된 것과 a activation(z)된 결과를 저장된한 두 개를 각layer별로 저장한 tuple을 반환하게 된다.

1.4 Regularized cost function

overfitting 문제를 막기 위해서 Regularized cost function을 Design 한다.

#Once you are done, using the loaded set of parameters Theta1 and Theta2,
#and lambda = 1, you should see that the cost is about 0.383770
myThetas = [ Theta1, Theta2 ]
print computeCost(flattenParams(myThetas),flattenX(X),y,mylambda=1.)

2. Backpropagation

오류 역전파를 구현 한다.
computeCost를 통해서 grad값을 받을 수 있다.
계산한 graident를 가지고 cost function $J(\theta)$를 advanced optimizer fmincg를 이용해서 최적화 할 수 있다.

우선 각각의 parameter들에 대한 cost-function에 대한 gradient를 backpropagation algorithm으로 계산해 본다.

2.1 Sigmoid Gradient

sigmoid의 gradient를 알기 위해서는 derivative를 수행 한다.
$g'(z) = g(z)(1 - g(z))$
여기서 $g(z)$는 아래와 같다.
$g(z) = \frac{1}{1+e^{-z}}$ 이다.

def sigmoidGradient(z):
    dummy = expit(z)
    return dummy*(1-dummy)

위 구현이 맞는지 확인해 보는 방법은 z값을 아주 큰 양수나 음수를 넣었을 때 0에 근접한 값이 나오면 된다.
그리고 z=0이라면 gradient는 0.25가 되어야 한다.

실행결과는 아래와 같다.

print(sigmoidGradient(5))
print(sigmoidGradient(0))
print(sigmoidGradient(-5))

0.00664805667079
0.25
0.00664805667079

이러한 특성 때문에 추후에 Vanishing gradient 문제가 발생한다.

원인은 다음과 같다.

• Weight matrix W가 큰 값으로 초기화 되었다면
• $Z = W^{T}X$의 결과는 당연히 큰 값이다.
• sigmoid(Z)는 당연히 0아니면 1이다.
• sigmoid(z)의 도함수는 $ g(z)(1 - g(z))$ 이므로 결국
• z가 0,1이 빈번하면 계속 0이된다. 대부분의 경우에 말이다.
• 그리고 이렇게 앞부분에서 0이 발생하면 backwrad pass는 모두 chain rull로 연결 되어 있으므로 전부다 zero가 된다.
• local gradient의 maximum은 0.25이다. 그것도 z가 0.5일 때 말이다. 즉 1번 sigmoid를 지날 때마다 그것의 magnitude는 항상 one quarter 만큼 까지 작아지며 그 이상 작아지는 경우도 많다.
• 결국 초기값 설정이 중요하다.

2.2 Random Initialization

초기 weight값을 저장한 $\theta$를 랜덤하게 초기화 시켜야 한다.
모두 같은 값이면 항상 같은 error를 가지므로 값이 같이 변해서 의미가 없어 진다.

uniformly 하게 range [-x,x]범위로 초기화 하는 것이다.
작은 값으로 초기화 하는것이 sigmoid의 derivative 특성상 유리하다. 큰 값으로 해버리면 0이되고 chain rule을 이용한
backpropagation 알고리즘 특성상 학습이 되지 않는다.

초기화 공식은 아래와 같다.
$$ \varepsilon { init }=\frac { \sqrt {6} }{ \sqrt {L{in}+L_{out}} } $$
where $L_{in}=s_l$ and $L_{out}=s_{l+1}$ 이다.

def genRandThetas():
    epsilon_init = 0.12
    theta1_shape = (hidden_layer_size, input_layer_size+1)
    theta2_shape = (output_layer_size, hidden_layer_size+1)
    rand_thetas = [ np.random.rand( *theta1_shape ) * 2 * epsilon_init - epsilon_init, \
                    np.random.rand( *theta2_shape ) * 2 * epsilon_init - epsilon_init]
    return rand_thetas

2.3 Backpropagation

def backPropagate(mythetas_flattened,myX_flattened,myy,mylambda=0.):
    
    # First unroll the parameters
    mythetas = reshapeParams(mythetas_flattened)
    
    # Now unroll X
    myX = reshapeX(myX_flattened)

    #Note: the Delta matrices should include the bias unit
    #The Delta matrices have the same shape as the theta matrices
    Delta1 = np.zeros((hidden_layer_size,input_layer_size+1))
    Delta2 = np.zeros((output_layer_size,hidden_layer_size+1))

    # Loop over the training points (rows in myX, already contain bias unit)
    m = n_training_samples
    for irow in xrange(m):
        myrow = myX[irow]
        a1 = myrow.reshape((input_layer_size+1,1))
        # propagateForward returns (zs, activations) for each layer excluding the input layer
        temp = propagateForward(myrow,mythetas)
        z2 = temp[0][0]
        a2 = temp[0][1]
        z3 = temp[1][0]
        a3 = temp[1][1]
        tmpy = np.zeros((10,1))
        tmpy[myy[irow]-1] = 1
        delta3 = a3 - tmpy 
        delta2 = mythetas[1].T[1:,:].dot(delta3)*sigmoidGradient(z2) #remove 0th element
        a2 = np.insert(a2,0,1,axis=0)
        Delta1 += delta2.dot(a1.T) #(25,1)x(1,401) = (25,401) (correct)
        Delta2 += delta3.dot(a2.T) #(10,1)x(1,25) = (10,25) (should be 10,26)
        
    D1 = Delta1/float(m)
    D2 = Delta2/float(m)
    
    #Regularization:
    D1[:,1:] = D1[:,1:] + (float(mylambda)/m)*mythetas[0][:,1:]
    D2[:,1:] = D2[:,1:] + (float(mylambda)/m)*mythetas[1][:,1:]
    
    return flattenParams([D1, D2]).flatten()

$\delta$를 구하기 위해서 Backpropagation을 수행하면 다음과 같다.

#Actually compute D matrices for the Thetas provided
flattenedD1D2 = backPropagate(flattenParams(myThetas),flattenX(X),y,mylambda=0.)
D1, D2 = reshapeParams(flattenedD1D2)

아래의 $\delta$는 구하려고하는 2개의 $\theta$값의 matrix 구조와 정확히 일치한다.
이유는 해당 $\delta$가 gradient를 의미하고 이것을 이용해서 $\theta$값을 조정하기 때문이다.

• D1.shape은 (25,401)이다. $\theta_{1}$ 25 x 401
• D2.shape은 (10,26)이다. $\theta_{2}$ 10 x 26

입력받는 인자는 4개이다.

• mythetas_flattened <- flattenParams(myThetas), 구하고자하는 2개의 $\theta$를 담고있다.
• myX_flattened <- flattenX(X), 입력된 이미지값 20x20+1(bias)
• myy <- y, 참값
• mylambda=0. <- 정규화의 수치

델타 값을 구하는 공식은 아래와 같다.
$$ \delta^{(l)} = ((\Theta^{(l)})^T \delta^{(l+1)})\ .*\ g'(z^{(l)}) $$
해당 공식과 같이 각각의 델타값을 계산한 것이다.

2.4 Gradient cheecking

def checkGradient(mythetas,myDs,myX,myy,mylambda=0.):
    myeps = 0.0001
    flattened = flattenParams(mythetas)
    print(flattened.shape)
    
    flattenedDs = flattenParams(myDs)
    myX_flattened = flattenX(myX)
    n_elems = len(flattened) 
    #Pick ten random elements, compute numerical gradient, compare to respective D's
    for i in xrange(10):
        import time
        #Actually compute D matrices for the Thetas provided
        start_time=time.time() #taking current time as starting time
        x = int(np.random.rand()*n_elems)
        epsvec = np.zeros((n_elems,1))
        epsvec[x] = myeps
        cost_high = computeCost(flattened + epsvec,myX_flattened,myy,mylambda)
        cost_low  = computeCost(flattened - epsvec,myX_flattened,myy,mylambda)
        mygrad = (cost_high - cost_low) / float(2*myeps)
        elapsed_time=time.time()-start_time #again taking current time - starting time 
        print (elapsed_time)
        print "Element: %d. Numerical Gradient = %f. BackProp Gradient = %f."%(x,mygrad,flattenedDs[x])

실행

checkGradient(myThetas,[D1, D2],X,y)

(10285, 1)
0.372140884399
Element: 8125. Numerical Gradient = 0.000022. BackProp Gradient = 0.000022.
0.366824150085
Element: 6642. Numerical Gradient = -0.000070. BackProp Gradient = -0.000070.
0.368250131607
Element: 7657. Numerical Gradient = -0.000001. BackProp Gradient = -0.000001.
0.362774133682
Element: 5270. Numerical Gradient = -0.000031. BackProp Gradient = -0.000031.
0.356532096863
Element: 5933. Numerical Gradient = 0.000057. BackProp Gradient = 0.000057.
0.350827932358
Element: 5394. Numerical Gradient = 0.000001. BackProp Gradient = 0.000001.
0.391266107559
Element: 2606. Numerical Gradient = -0.000006. BackProp Gradient = -0.000006.
0.363577127457
Element: 6160. Numerical Gradient = 0.000075. BackProp Gradient = 0.000075.
0.379949092865
Element: 8722. Numerical Gradient = 0.000001. BackProp Gradient = 0.000001.
0.373861789703
Element: 931. Numerical Gradient = 0.000100. BackProp Gradient = 0.000100.

backpropagation을 이용할 경우 단 0.37의 시간으로 모든 gradient를 계산 할 수 있다.
하지만 numerical 방식으로는 한번에 1개의 theta값만 계산 가능하므로 계산적 오버해드가 크다고 할 수 있다.

2.5 Learning parameters using fmincg

fmin_cg함수를 이용해서 학습을 수행 한다.

• Minimize a function using a nonlinear conjugate gradient algorithm.

간략히 설명하면 아래와 같다.

• 장점
  • No need to manually pick $\alpha$.
    • inter-loop를 돌면서 최적의 learning rate을 스스로 매번 다르게 결정한다.
  • Often faster than gradient descent.
• 단점
  • More complex.

#Here I will use scipy.optimize.fmin_cg

def trainNN(mylambda=0.):
    """
    Function that generates random initial theta matrices, optimizes them,
    and returns a list of two re-shaped theta matrices
    """

    randomThetas_unrolled = flattenParams(genRandThetas())
    result = scipy.optimize.fmin_cg(computeCost, x0=randomThetas_unrolled, fprime=backPropagate, \
                               args=(flattenX(X),y,mylambda),maxiter=50,disp=True,full_output=True)
    return reshapeParams(result[0])

fmin_cg의 인자는 아래와 같다.
scipy.optimize.fmin_cg(f, x0, fprime=None, args=(), gtol=1e-05, norm=inf,epsilon=1.4901161193847656e-08, maxiter=None, full_output=0, disp=1, retall=0,callback=None)

• f(x, *args): Objective function to be minimized. Here x must be a 1-D array of the variables that are to be changed in the search for a minimum, and args are the other (fixed) parameters of f.
• fprime: callable, fprime(x, *args), optional
  A function that returns the gradient of f at x. Here x and args are as described above for f. The returned value must be a 1-D array. Defaults to None, in which case the gradient is approximated numerically (see epsilon, below).

학습 수행 결과

#Training the NN takes about ~70-80 seconds on my machine
learned_Thetas = trainNN()

실행 결과

Warning: Maximum number of iterations has been exceeded.
         Current function value: 0.279615
         Iterations: 50
         Function evaluations: 112
         Gradient evaluations: 112

정확도 검증

def predictNN(row,Thetas):
    """
    Function that takes a row of features, propagates them through the
    NN, and returns the predicted integer that was hand written
    """
    classes = range(1,10) + [10]
    output = propagateForward(row,Thetas)
    #-1 means last layer, 1 means "a" instead of "z"
    return classes[np.argmax(output[-1][1])] 

def computeAccuracy(myX,myThetas,myy):
    """
    Function that loops over all of the rows in X (all of the handwritten images)
    and predicts what digit is written given the thetas. Check if it's correct, and
    compute an efficiency.
    """
    n_correct, n_total = 0, myX.shape[0]
    for irow in xrange(n_total):
        if int(predictNN(myX[irow],myThetas)) == int(myy[irow]): 
            n_correct += 1
    print "Training set accuracy: %0.1f%%"%(100*(float(n_correct)/n_total))

정확도 결과

computeAccuracy(X,learned_Thetas,y)

Training set accuracy: 96.2%

Autonomous Driving Example

자동 드라이빙의 경우 Dean Pomerleau가 만든것이다.
CMU의 Robotics Institute의 Adjunct Faculty이다.

같은 길에 대해서는 몇분만 트레이닝을 하면 사람과 같이 정확하게 동작하게 된다.

지금 사례를 찾아보면 테슬라 등등에서 훨씬 더 좋은 Auto Driving이 존재 한다.

Putting it together

When training a neural network, the first thing you need to do is pick some network architecture.

Architectures mean connectivity pattern between the neurons

히든 레이어를 1개만 쓰는것이 일반 적이다.

많은 히든 레이러를 쓰고 싶으면 같은 수의 neuron으로 구성하는 것이 일반 적이다.

Hidden Layer가 많을 수록 잘 동작 할 수도 있지만 Computation Cost가 높기 때문에 신중히 선택해야 한다.

구현을 위한 과정은 아래와 같다.

위코드는 For-loop를 사용했지만 Advanced를 하게 되면 vectorization을 통해서 for-loop을 쓰지 않고
Backpropagation을 수행 할 수 있다.

그 다음 partial derivative가 정상적으로 동작하는지 알기 위해서 gradient checking 코드를 이용해서 확인 해야 한다.
$J(\theta)$가 non-convex function이라서 global minimum이 아닌 local minimum에 머물 지라도 practical problem에서는 그렇게 문제는 되지 않는다고 한다.

수업 초기에 보여주었던 그래프를 통해서 Gradient Descent Alogirhtm이 어떻게 $\theta$값을 최소화하는지 알아 보도록 하겠다.
해당 그래프는 아래와 같다.

Quiz

Backpropagation은 non-linear function을 classification하기 위한 하나의 좋은 algorithm이다.

Random Initialization

Neural Netwrok을 구현하기 위해서는
맨 처음에는 $\theta$를 초기화 하는 코드를 자성해야 한다.

보통 취하는 방법은 아래처럼 random initialTheta를 취하는 것이다.

optTheta = fminunc(@costFunction, initialTheta, options)

의문점은 Zero initialization에 관한 의문이 생긴다.
Logistic regression을 작성할 때는 별 다른 문제가 되지 않는다. 하지만 Nueral Netwrok이라면 그것은 문제가 된다.

위와 같이 0으로 초기화후 Gradient Descent 알고리즘을 수행하면 모든 Hidden Layer들이 정확히 같이 값이 변화기 때문에
그저 중복적인 Hidden Layer에 지나지 않게 된다.

Quiz

Gradient Checking

Backprogation Algorithm은 구현이 다소 복잡하고 여러 방법으로 구현 할 수 있기 때문에
subtle bug를 찾기가 어렵다.

이것을 디버그하기 위한 아이디어가
Gradient Checking이다.

모든 복잡한 Nueral Network Algorithm을 개발할 때 사용 할 수 있다.

위 그림에서 파란색은 실제 미분 했을 때 구해지는 접선의 기울기이다.
해당 값은 epsilon을 이용해서 approximation할 수 있다.
빨간색과 같이 slope를 approximation하면 꽤 근사하게 구해지는 것을 알 수 있다.

추가로 위 그림에서 파란색 수식은 epsilon을 한번만 사용한 one sided difference이다.
이것 보다 빨간색 수식으로 epsilon을 두번 사용한 것이 더 정확하게 estimation할 수 있다.

Quize

So these equations give you a way to numerically approximate the partial derivative of $J$ with respect to any one of your parameters $\theta_i$.

구현해야 할것은 아래의 For loop이다.

결국 back-propagation을 통해서 DVec을 구하게 된다.
그리고 우리가 대략적으로 구한 gradApprox랑 비교하게 된다.

Backpropagation is a relatively efficient way to compute a derivative or a partial derivative of a cost function wrt to all our parameters.

이것을 통해서 구현이 정상적으로 이뤄 졌는지를 알 수 있다.

마지막으로 요점을 정리하면 아래와 같다.

• Implementation Notes

  • Implement backpropagation to compute DVec (unrolled $D^{(1)}$, $D^{(2)}$, $D^{(3)}$).
  • Implement numerical gradient check to compute gradApprox.
  • Make sure they give similar values.
  • Turn off gradient checking. Using backpropacation code for learning.

  이 부분이 가장 중요한데, gradient checking은 computationally 굉장히 expensive 하기 때문에 학습할 때는 반드시 꺼야 한다. 당연한 말이지만 그래서 1960년대 nueral network 자체가 죽은것이다.
  이것을 해결한 알고리즘이 Backpropagation이기 때문이다. 딱 한번 구현 확인 용도로만 쓰자.

Quize

Neural Networks Learning: Implementation note unrolling

Octave programming

아래 방법 처럼 초기 Weight vector를 생성하고
이것을 긴 하나의 vector로 언롤링 한다.
그리고 reshape을 이용해서 다시 복구 할 수 있다.

octave:1> Theta1 = ones(10,11)
Theta1 =

   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   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   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   1
   1   1   1   1   1   1   1   1   1   1   1
   1   1   1   1   1   1   1   1   1   1   1

octave:2> Theta2 = 2 *ones(10,11)
Theta2 =

   2   2   2   2   2   2   2   2   2   2   2
   2   2   2   2   2   2   2   2   2   2   2
   2   2   2   2   2   2   2   2   2   2   2
   2   2   2   2   2   2   2   2   2   2   2
   2   2   2   2   2   2   2   2   2   2   2
   2   2   2   2   2   2   2   2   2   2   2
   2   2   2   2   2   2   2   2   2   2   2
   2   2   2   2   2   2   2   2   2   2   2
   2   2   2   2   2   2   2   2   2   2   2
   2   2   2   2   2   2   2   2   2   2   2

octave:3> Theta3 = 3*ones(1,11)
Theta3 =

   3   3   3   3   3   3   3   3   3   3   3

octave:8> thetaVec = [ Theta1(:); Theta2(:); Theta3(:)];
octave:9> size(thetaVec)
ans =

   231     1

octave:10> reshape(thetaVec(1:110), 10,11)
ans =

   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   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   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   1
   1   1   1   1   1   1   1   1   1   1   1
   1   1   1   1   1   1   1   1   1   1   1

위와 같이 긴 vector를 만듬으로써 fminunc의 성능을 끌어 올릴 수 있다.
Cost function을 계산 할때에는 reshape을 통해서 각각의 다시 계산하게 된다.

Neural Networks_Learning_3

Backpropagation Intuition

Backpropagation은 수학적으로 클린한 알고리즘은 아니다.
이것은 linear regression이나 Logistic regression와 비교하면 복잡한 알고리즘에 속한다.

먼저 Forward Propagation을 설명해 보자.

위 Neural Network의 구조는 [2 2 2 1]의 구조를 가진다.
$\theta$에서 $i$는 다음 layer에서 영향을 미칠 node의 위치를 나타낸다.
$j$는 특정 layer에서의 node위치를 의미한다.
$l$은 layer의 위치를 의미한다.

$z$에서 $a$로 변경 될때는 activation function을 거친다는 것을 알아두자.

What is backpropagation doing?

일단 output이 1개 뿐이라고 생각해보자. 그럼 Cost function이 위와 같이 간단해 진다.
그리고 regularization term을 무시하기 위해서 $\lambda$는 0으로 설정 한다.
cross entropy형태의 cost function은 결국 Square Error를 근사시키기 위한 변형 함수이다.
직관을 위해서 그냥 Square Error라고 생각하자.
그럼 좀 더 쉽게 생각 할 수 있다.

Forward propagation을 꺼구로 수행한것 처럼 계산하면
아래와 같이 식을 구할 수 있다.

결국 $\delta$라는 것은 실제 y와 예측한값 a간의 error를 나타낸다.
좀더 수학적으로 표현하면, 아래와 같다.
$$ \delta^{(l)}_{j} = \frac{\partial cost(i)}{\partial z_j^{(l)}} $$
여기서 $j$는 $\ge 0$를 만족 한다.
cost(i)는 cross entropy 값이다.

Programming Exercise 3: Multi-class classification and Neural Networks

Introduction

one-vs-all logistic regression과 neural networks를 구현하고 이를 통해서 hand-written digits를 인식해 볼 것이다.

Files included in this exercise

ex3.m - Octave/MATLAB script that steps you through part 1
ex3 nn.m - Octave/MATLAB script that steps you through part 2
ex3data1.mat - Training set of hand-written digits
ex3weights.mat - Initial weights for the neural network exercise
submit.m - Submission script that sends your solutions to our servers
displayData.m - Function to help visualize the dataset
fmincg.m - Function minimization routine (similar to fminunc)
sigmoid.m - Sigmoid function
[] lrCostFunction.m - Logistic regression cost function
[] oneVsAll.m - Train a one-vs-all multi-class classifier
[] predictOneVsAll.m - Predict using a one-vs-all multi-class classifier
[] predict.m - Neural network prediction function

전반적으로 ex3.m과 ex3_nn.m파일을 가지고 작업을 하게 된다.

1. Multi-class Classification

우선, 이전에 개발한 Logistic regression을 확장해서 one-vs-all classification을 구현 하게 된다.

1.1 Dataset

ex3data1.mat에 저장되어 있다.
이 파일에는 5000개의 handwritten digit들이 training example로써 5000개 저장되어 있다.
.mat format은 native Ooctave/MATLAB matrixv 포멧을 의미한다.

정확히 저장 되었다면 결과 값이 matrix에 저장 되게 된다.

% Load saved matrices from file
load('ex3data1.mat');
% The matrices X and y will now be in your Octave environment

20 by 20 grid of pixels is "unrolled" into a 400-dimensional vector.
결국 Eample 하나는 single row가 되고 matrix는
5000 by 400 matrix가 된다.

호환성을 위해서 0을 10으로 mapping 하고 나머지는 그대로 mapping 한다.

1.2 Visualizing the data

displayData 코드는 랜덤으로 100개의 image들을 선택해서 보여주게 된다.

1.3 Vectorizing Logistic Regression

Training 시간을 줄이기 위해서 vectorization을 반드시 수행 해야 한다.

1.3.1 Vectorizing the cost function

vectorization을 이용해서 unregularized cost function을 lrCostFunction.m에 다가 구현을 한다.
반드시 fully vectorized version을 만들어야 한다.
이것의 의미는 loop가 없어야 함을 의미한다.

1.3.2 Vectorizing the gradient

gradient descent algorithm도 vectorization을 통해서 적용을 하게 된다.

Cost Function과 Gradient를 모두 적용한 matlab 코드는 아래와 같다.

1.3.3 Vectorizing regularized logistic regression

Regularzation 까지 적용한 Vectorization을 생성 한다.
최종 코드는 아래와 같다.

lrCostFunction.m

function [J, grad] = lrCostFunction(theta, X, y, lambda)
%LRCOSTFUNCTION Compute cost and gradient for logistic regression with
%regularization
%   J = LRCOSTFUNCTION(theta, X, y, lambda) computes the cost of using
%   theta as the parameter for regularized logistic regression and the
%   gradient of the cost w.r.t. to the parameters.

% Initialize some useful values
m = length(y); % number of training examples

% You need to return the following variables correctly
J = 0;
grad = zeros(size(theta));

% ====================== YOUR CODE HERE ======================
% Instructions: Compute the cost of a particular choice of theta.
%               You should set J to the cost.
%               Compute the partial derivatives and set grad to the partial
%               derivatives of the cost w.r.t. each parameter in theta
%
% Hint: The computation of the cost function and gradients can be
%       efficiently vectorized. For example, consider the computation
%
%           sigmoid(X * theta)
%
%       Each row of the resulting matrix will contain the value of the
%       prediction for that example. You can make use of this to vectorize
%       the cost function and gradient computations.
%
% Hint: When computing the gradient of the regularized cost function,
%       there're many possible vectorized solutions, but one solution
%       looks like:
%           grad = (unregularized gradient for logistic regression)
%           temp = theta;
%           temp(1) = 0;   % because we don't add anything for j = 0
%           grad = grad + YOUR_CODE_HERE (using the temp variable)
%

H_theta = sigmoid(X * theta);

% Cost
J =(1/m) * sum(-y .* log(H_theta) - (1 - y) .* log(1 - H_theta)) + ...
   (lambda/(2*m)) * norm(theta([2:end]))^2;

G = (lambda/m) .* theta;
G(1) = 0; % extra term for gradient

% Gradient
grad = ((1/m) .* X' * (H_theta - y)) + G;


% =============================================================

grad = grad(:);

end

1.4 One-vs-all Classification

one-vs-all classification을 multiple regularized logistic regression 이용한 방법이다.

작성해야할 코드는 oneVsAll.m이다.

oneVsAll.m

function [all_theta] = oneVsAll(X, y, num_labels, lambda)
%ONEVSALL trains multiple logistic regression classifiers and returns all
%the classifiers in a matrix all_theta, where the i-th row of all_theta
%corresponds to the classifier for label i
%   [all_theta] = ONEVSALL(X, y, num_labels, lambda) trains num_labels
%   logisitc regression classifiers and returns each of these classifiers
%   in a matrix all_theta, where the i-th row of all_theta corresponds
%   to the classifier for label i

% Some useful variables
m = size(X, 1);
n = size(X, 2);

% You need to return the following variables correctly
all_theta = zeros(num_labels, n + 1);

% Add ones to the X data matrix
X = [ones(m, 1) X];

% ====================== YOUR CODE HERE ======================
% Instructions: You should complete the following code to train num_labels
%               logistic regression classifiers with regularization
%               parameter lambda.
%
% Hint: theta(:) will return a column vector.
%
% Hint: You can use y == c to obtain a vector of 1's and 0's that tell use
%       whether the ground truth is true/false for this class.
%
% Note: For this assignment, we recommend using fmincg to optimize the cost
%       function. It is okay to use a for-loop (for c = 1:num_labels) to
%       loop over the different classes.
%
%       fmincg works similarly to fminunc, but is more efficient when we
%       are dealing with large number of parameters.
%
% Example Code for fmincg:
%
%     % Set Initial theta
%     initial_theta = zeros(n + 1, 1);
%
%     % Set options for fminunc
%     options = optimset('GradObj', 'on', 'MaxIter', 50);
%
%     % Run fmincg to obtain the optimal theta
%     % This function will return theta and the cost
%     [theta] = ...
%         fmincg (@(t)(lrCostFunction(t, X, (y == c), lambda)), ...
%                 initial_theta, options);
%

for k = 1:num_labels

    initial_theta = zeros(n + 1, 1);
    options = optimset('GradObj', 'on', 'MaxIter', 500); % iteration could be bigger, e.g. 500

    [theta] = ...
         fmincg (@(t)(lrCostFunction(t, X, (y == k), lambda)), ...
                 initial_theta, options);

    all_theta(k,:) = theta';
end
% =========================================================================
end

1.4.1 One-vs-all Prediction

주어진 image를 prediction 해보자.
10개의 classifier가 존재하고 이중에서 가장 높은 probability를 가지는 것으로 prediction 하게 된다.

작성해야할 코드는 predictOneVsAll 함수 이다.
이전에 학습된 #\theta$를 이용해서 prediction을 수행하게 된다.
정확도는 94.9%를 기록하게 된다.

predictOneVsAll.m

function p = predictOneVsAll(all_theta, X)
%PREDICT Predict the label for a trained one-vs-all classifier. The labels
%are in the range 1..K, where K = size(all_theta, 1).
%  p = PREDICTONEVSALL(all_theta, X) will return a vector of predictions
%  for each example in the matrix X. Note that X contains the examples in
%  rows. all_theta is a matrix where the i-th row is a trained logistic
%  regression theta vector for the i-th class. You should set p to a vector
%  of values from 1..K (e.g., p = [1; 3; 1; 2] predicts classes 1, 3, 1, 2
%  for 4 examples)

m = size(X, 1);
num_labels = size(all_theta, 1);

% You need to return the following variables correctly
p = zeros(size(X, 1), 1);

% Add ones to the X data matrix
X = [ones(m, 1) X];

% ====================== YOUR CODE HERE ======================
% Instructions: Complete the following code to make predictions using
%               your learned logistic regression parameters (one-vs-all).
%               You should set p to a vector of predictions (from 1 to
%               num_labels).
%
% Hint: This code can be done all vectorized using the max function.
%       In particular, the max function can also return the index of the
%       max element, for more information see 'help max'. If your examples
%       are in rows, then, you can use max(A, [], 2) to obtain the max
%       for each row.
%

[x, ix] = max(sigmoid(X * all_theta'), [], 2);

p = ix;

% =========================================================================
end

단순 logistic regression으로도 아래와 같이 훌륭한 결과를 얻을 수 있다.

Loading and Visualizing Data ...
Program paused. Press enter to continue.

Training One-vs-All Logistic Regression...
Iteration   457 | Cost: 1.311466e-02
Iteration   500 | Cost: 5.080189e-02
Iteration   500 | Cost: 5.760187e-02
Iteration   500 | Cost: 3.306492e-02
Iteration   500 | Cost: 5.445615e-02
Iteration   500 | Cost: 1.825591e-02
Iteration   500 | Cost: 3.064138e-02
Iteration   500 | Cost: 7.845164e-02
Iteration   500 | Cost: 7.118580e-02
Iteration   500 | Cost: 8.567845e-03
Program paused. Press enter to continue.

Training Set Accuracy: 96.460000
octave:38> 

2. Neural Networks

이전까지는 Logistic regression을 다중으로 사용해서 이미지 숫자를 구별하는 방법을 했었다.

여기서는 handwritten digits을 인식하기 위해서 neural network을 이용하게 된다.

하지만 parameter trained은 직접 하지 않고 이미 학습한 $\theta$값을 이용한다.

여기서는 이미 정의된 $\theta$를 이용해서 feedforward propagation algorithm을 구현 하는데 의미가 있다.

2.1 Model representation

입력, 히든, 출력 이렇게 3개의 레이어로 구성된 neural network 이다.

입력은 20x20 이미지 이기때문에 400이라고 할 수 있다.
이것에 bias unit 값으로 +1이 추가 된다.

neural network에서 쓰이는 parameter들은 이미 학습 되어져서 ex3weights.mat에 저장되어 있다.
히든 레이어는 25개의 unit으로 구성되어 있고 output 레이어는 10개의 unit으로 구성되어 있다.

이전에 강의 자료에서 설명되었듯이 $\theta^{j}$의 dimension은 $s_{j+1} \times s_{j}+1$로 정의 된다.
따라서 아래와 같은 matrix를 구성하게 된다.

% Load saved matrices from file
load('ex3weights.mat');
% The matrices Theta1 and Theta2 will now be in your Octave
% environment
% Theta1 has size 25 x 401
% Theta2 has size 10 x 26

2.2 Feedforward Propagation and Prediction

predict.m을 구현 함으로써 feedforward propagaction을 구현하게 된다.

어떤 example $i$에 대해서 $h_{\theta}(x^{(i)})$를 이용해서 digit을 prediction 하게 된다.
one-vs-all classification과 같이 가장큰 확률을 가지는 i class로 prediction 된다.

predict.m

function p = predict(Theta1, Theta2, X)
%PREDICT Predict the label of an input given a trained neural network
%   p = PREDICT(Theta1, Theta2, X) outputs the predicted label of X given the
%   trained weights of a neural network (Theta1, Theta2)

% Useful values
m = size(X, 1);
num_labels = size(Theta2, 1);

% You need to return the following variables correctly
p = zeros(size(X, 1), 1);

% ====================== YOUR CODE HERE ======================
% Instructions: Complete the following code to make predictions using
%               your learned neural network. You should set p to a
%               vector containing labels between 1 to num_labels.
%
% Hint: The max function might come in useful. In particular, the max
%       function can also return the index of the max element, for more
%       information see 'help max'. If your examples are in rows, then, you
%       can use max(A, [], 2) to obtain the max for each row.
%

a1 = [ones(m, 1) X]; % add 1

z2 = a1 * Theta1';

a2 = [ones(size(sigmoid(z2), 1), 1) sigmoid(z2)]; % add 1

z3 = a2 * Theta2';
a3 = sigmoid(z3); % H_theta(x)

[x, ix] = max(a3, [], 2);

p = ix;

% =========================================================================
end

결과를 확인해보면,
우선 ex3_nn.m은 미리 학습에 의해서 정해진 Theta1과 Theta2를 불러온다.
그런다음 예제 5000개가 저장된 X를 입력해서 prediction 하게 된다.

최종 결과를 참값 y를 통해서 비교하게된다.
정확도는 97.5%가 나오게 된다.

그다음에는 하나하나 이미지를 보여주면서 생성한 모델이 어떻게 prediction 하는지 확인 할 수 있다.

실행결과

Loading and Visualizing Data ...
Program paused. Press enter to continue.

Loading Saved Neural Network Parameters ...

Training Set Accuracy: 97.520000
Program paused. Press enter to continue.

Displaying Example Image

Neural Network Prediction: 8 (digit 8)
Program paused. Press enter to continue.

Week 04: Neural Networks

Non-linear Hypotheses

Model representation 1

$\theta$를 weight라고도 하고 parameter라고도 한다.

activiation fucntion을 sigmoid (logistic)이라고도 한다.

Neural networks -notation

• $a_i^{(j)}$, activiation of unit i in layer j

  • 해석하면 만약, $a_1^{2}$라고 하면 두번째 레이어에 있는 첫번째 유닉이라는 의미 이다.

• $\theta_i^{(j)}$ 이란 결국 layer j에서 layer j+1로 연결 시켜주는 mapping function을 의미한다.

  • Prameters for controlling mapping from one layer to the next
  • $s_j$란 layer j에 있는 유닛을 말한다.
  • $s_{j+1}$ unit은 layer j+1에 있는 유을 말한다.
  • 결국 $\theta^j$의 dimension은 $s_{j+1}$ by $s_{j}+1$로 결정 된다.
    • 왜냐하면, $s_{j+1}$은 layer (j+1)의 유닉수와 같기 때문이다
    • is equal to the number of units in layer j, plus an additional unit
  • Looking at the Ɵ matrix
    • Column length is the number of units in the following layer
    • Row length is the number of units in the current layer + 1 (because we have to map the bias unit)

Model representation 2

Forward propagation: Vectorized implementation

이전에 설계한 구조를 아래와 같다.

이것을 formula로 좀더 정리해 보면

a^(2)는 R^3로 삼차원 vector를 의미한다.
x와 a^(1)은 같기 때문에 동일하다는 판단하에 지울 수 있다.

추가로 bias에 대해서 입력으로 넣어준다.
4차원 vector로 정의되고 R^4가 된다.

이러한 과정을 forward propagation이라고 한다.

Neural Network Learning its own features

아래의 그림과 같이 Neural netwrok이 하는 일은 그저 logistic regression이 하는 일과 같다.

단지, original features, $x_1$, $x_2$, $x_3$를 사용하는 것이 아닌
새로운 features, $a_1^2$, $a_2^2$, $a_3^2$를 사용하게 된다.

결국 이것을 이용해서 Hypothesis를 구현하게 되면 아래와 같다.

$$ h_{\theta}^{(x)} = 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 ) $$

위 equation은 완벽히 Logistic regression과 일치 한다.

Applications: Examples and Intuitions 1

Neural network이 어떻게 non-linear function을 간단히 해결 하는지 다루겠다.

AND의 경우

OR의 경우

Applications: Examples and Intuitions 2

Yann LeCun 교수의 handwritten digit classification에 관한 비디오이다.
Video

7.Multi-class classification

In this section, I want to tell you about how to use nerual entworks to do multiclass classification where we may have more than one category that we're trying to distinguish amongst.

이것은 an extention of the one versus all method 이다.

즉, 결과가 0이나 1이 아니라면 그것은 multiclass classification 이라고 할 수 있다.

하나의 예제로 pedestrian, car, motobike or truck 이 4가지중 하나를 추출하는 classification이 있다고 생각해 보자.
이것을 위해서는 output vector가 4개의 숫자를 가져야 한다.

• 1 is 0/1 pedestrian
• 2 is 0/1 car
• 3 is 0/1 motocycle
• 4 is 0/1 truck

만약 이미지가 pedestrian 이라면 [1,0,0,0]의 값을 얻게 된다.

결국 아래와 같이

$$ h_{\theta}^{(i)} = y^{(i)} $$
로 결정 된다.

Programming Exercise 2: Regularized Logistic Regression

Microchip 제작에 관한 Quality Assureance (QA)를 예측하는 작업을 수행 한다.

QA동안에 microchip은 많은 test를 겪게 된다.

chips manager라고 가정하고 이제 2개의 test 결과를가지고 해당 chips을 통과 시킬지 말지를 결정하는 것을 생각해 보자.

이번에는 결국 아래의 파일만 구현하면 된다.

• [*] costFunctionReg.m - Regularized Logistic Regression Cost

2.1 Visualizing the data

이전과 같이 일단 visualization 부터 수행 한다.
ex2_reg를 실행하면 기본적으로 아래와 같이 그래프를 그려 준다.

해당 분포를 보면 linear dicision boundary로는 결정을 할 수 없는 것을 알 수 있다.

2.2 Feature mapping

mapFeature.m에 의해서 featrue의 수를 증가 시킨다.

6 제곱 까지 증가시킨 다항식을 통해서 정확도 높은 dicision boundary를 생성 할 수 있다.

mapping 함수를 통해서 two features vector는 28-dimensional vector로 변경 된다.

이러한 feature mapping은 좀더 설명 가능한 classifier를 생성하게 도와 준다. 하지만 overfitting에 대해서는 민감하게 반응하게 된다.

2.3 Cost Function and Gradient

regularized logistic regression을 완성하기 위해서 cost function과 gradient function을 costFunctionReg.m에다가 구현 한다.

Regularized Cost Function
$$ J(\theta) = \frac{1}{m}\sum_{i=1}^{m}\big[-y^{(i)}\, log\,( h_\theta\,(x^{(i)}))-(1-y^{(i)})\,log\,(1-h_\theta(x^{(i)}))\big] + \frac{\lambda}{2m}\sum_{j=1}^{n}\theta_{j}^{2} $$

Vectorized Cost Function
$$ J(\theta) = \frac{1}{m}\big((\,log\,(g(X\theta))^Ty+(\,log\,(1-g(X\theta))^T(1-y)\big) + \frac{\lambda}{2m}\sum_{j=1}^{n}\theta_{j}^{2} $$

Partial derivative
$$ \frac{\delta J(\theta)}{\delta\theta_{j}} = \frac{1}{m}\sum_{i=1}^{m} ( h_\theta (x^{(i)})-y^{(i)})x^{(i)}{j} + \frac{\lambda}{m}\theta{j} $$

Vectorized
$$ \frac{\delta J(\theta)}{\delta\theta_{j}} = \frac{1}{m} X^T(g(X\theta)-y) + \frac{\lambda}{m}\theta_{j} $$

$\theta_0$는 regularization 하지 않는다. $j$는 1부터 시작하게 된다.

모든 $\theta$가 0으로 초기화 되었을 때의 cost 값은 0.693이다.

costFunctionReg.m

function [J, grad] = costFunctionReg(theta, X, y, lambda)
%COSTFUNCTIONREG Compute cost and gradient for logistic regression with regularization
%   J = COSTFUNCTIONREG(theta, X, y, lambda) computes the cost of using
%   theta as the parameter for regularized logistic regression and the
%   gradient of the cost w.r.t. to the parameters.

% Initialize some useful values
m = length(y); % number of training examples

% You need to return the following variables correctly
J = 0;
grad = zeros(size(theta));

% ====================== YOUR CODE HERE ======================
% Instructions: Compute the cost of a particular choice of theta.
%               You should set J to the cost.
%               Compute the partial derivatives and set grad to the partial
%               derivatives of the cost w.r.t. each parameter in theta

H_theta = sigmoid(X * theta);

% Cost
J =(1/m) * sum(-y .* log(H_theta) - (1 - y) .* log(1 - H_theta)) + ...
   (lambda/(2*m)) * norm(theta([2:end]))^2;

G = (lambda/m) .* theta;
G(1) = 0; % extra term for gradient

% Gradient
grad = ((1/m) .* X' * (H_theta - y)) + G;

% =============================================================

end

2.3.1 Learning parameters using fminunc

이전과 같이 ex2_reg.m에서 fminunc 함수를 이용해서 $\theta$를 최적화 한다.

2.4 Plotting the decision boundary

plotDecisionBoundary.m에 의해서 non-linear decision boundary를 그리게 된다.

그리고 최종적인 train accuracy는 다음과 같다.

Train Accuracy: 83.050847

2.5 Optional (ungraded) exercises

$\lamda$를 조절해 가면서 overfitting과 underfitting을 적용해 볼 수 있다.
e2_reg.m에서 lamda 값만 변경하면 아래와 같이 수행 할 수 있다.

lamda= = 0
Train Accuracy:86.440678

lamda = 100
Train Accuracy: 61.016949

Programming Exercise 2: Logistic Regression 

Introduction

여기선 logistic regression을 구현하고 서로다른 두개의 datasets에 적용해 본다.

작업해야할 파일들은 아래와 같다.

• ex2.m - Octave/MATLAB script that steps you through - the exercise
• ex2 reg.m - Octave/MATLAB script for the later parts of the exercise
• ex2data1.txt - Training set for the first half of the exercise
• ex2data2.txt - Training set for the second half of the exercise
• submit.m - Submission script that sends your solutions to our servers
• mapFeature.m - Function to generate polynomial features

• plotDecisionBoundary.m - Function to plot classifier’s decision boundary

• [*] plotData.m - Function to plot 2D classification data

• [*] sigmoid.m - Sigmoid Function
• [*] costFunction.m - Logistic Regression Cost Function
• [*] predict.m - Logistic Regression Prediction Function
• [*] costFunctionReg.m - Regularized Logistic Regression Cost

*가 들어간 것들이 구현해야될 파일 이다.

ex2.m과 ex2_reg.m의 파일이 전체적인 exercise를 다루고 있는 것들이다. 이 두 파일은 dataset을 set up하고 문제를 해결하기 위해서 우리가 작성해야할 function들을 호출하는 순서로 구성 되어 있다.

직접적으으로 ex2.m과 ex2_reg.m을 수정할 필요는 없다. 그저 각각의 다른파일에 저장된 function의 내용을 채우면 된다.

1. Logistic Regression

학생들이 대학에 입할 할 수 있는지 아닌지에 대한 예측을 가능 하도록 하는 Logistic regression classifier를 구현 한다.

과거 지원자의 두 과목 시험 점수와 그에 따른 admission결과를 training set으로 하여 model을 생성하게 된다.

모델로 만약 어떤 사용자의 시험 성정 2개가 주어진다면 이 사용자가 과거 대비 입학을 할 수 있을지에 대한 probability를 구하게 된다.

1.1 Visualizing the data

데이터 형태 파악을 위해서 일단 plot을 그려 보는것이 효과 적이다.

plotData function을 호출해서 plot을 그리게 된다.

당연히 plotData.m 파일의 함수를 구현해야 그래프가 그려 진다.

ex2.m

#파일 읽기
data = load('ex2data1.txt')

data = 

   34.62366   78.02469    0.00000
   30.28671   43.89500    0.00000
   35.84741   72.90220    0.00000
   60.18260   86.30855    1.00000
   79.03274   75.34438    1.00000
   45.08328   56.31637    0.00000
   61.10666   96.51143    1.00000
   ....

size(data)

ans =

   100     3

# 총 100개의 데이터가 있다.
# 1-2 열이 과목 점수고, 3번째 열이 admission 여부를 나타낸다. 각각을 X와 Y로 끄집어 낸다.
X = data(:,[1,2])
y = data(:,3)

# 두개를 그래프 그리기 위해서 인자로 넘겨 준다.
plotData(X,y)

plotData.m

function plotData(X, y)
%PLOTDATA Plots the data points X and y into a new figure
%   PLOTDATA(x,y) plots the data points with + for the positive examples
%   and o for the negative examples. X is assumed to be a Mx2 matrix.

% Create New Figure
figure; hold on;

% ====================== YOUR CODE HERE ======================
% Instructions: Plot the positive and negative examples on a
%               2D plot, using the option 'k+' for the positive
%               examples and 'ko' for the negative examples.
%

% Find Indices of Positive and Negtive Example
pos = find(y == 1);
neg = find(y == 0);

% Plot Example
plot(X(pos, 1), X(pos, 2), 'k+', 'LineWidth', 2, 'MarkerSize', 7);
plot(X(neg, 1), X(neg, 2), 'ko', 'MarkerFaceColor', 'yellow', 'MarkerSize', 7);


% =========================================================================

1.2 Implementation

1.2.1 Warmup exercise: sigmoid function

그냥 몸풀기 정도로 logistic regression에서 사용하는 hypothesis는 다음과 같다.

$$ h_{\theta} = g(\theta^{T} x) $$

여기서 g는 sigmoid function이다. sigmoid는 아래와 같다.

$$ g(z) = \frac{1}{1+e^{-z}} $$
위 sigmoid를 sigmoid.m에다가 구현 한다.

function g = sigmoid(z)
%SIGMOID Compute sigmoid functoon
%   J = SIGMOID(z) computes the sigmoid of z.

% You need to return the following variables correctly 
g = zeros(size(z));

% ====================== YOUR CODE HERE ======================
% Instructions: Compute the sigmoid of each value of z (z can be a matrix,
%               vector or scalar).

g = 1.0 ./ (1.0 + exp(-z));

% =============================================================
end

코드에서 ./는 엘리먼트 나눗셈이다.
즉, 두개의 배열이 있을때 각각의 엘리먼트 끼리 나누는 것이다.
z인자가 matrix로 들어올 수 있기 때문에 이렇게 해줘야 한다.

sigmoid test
아래와 같이 잘 구현 되었는지 확인해보면
큰 positive value면 1이, 큰 negative value면 0이
0이면 0.5로 잘 나오는것을 알 수 있다.

octave:7> sigmoid(100000000)
ans =  1
octave:8> sigmoid(-100000000)
ans = 0
octave:9> sigmoid(0)
ans =  0.50000

그리고 matrix형태로 z 값을 넣어보면, 아래와 같이 각각에 대해서 sigmoid가 잘 적용되는 것을 알 수 있다.

octave:10> sigmoid(data)
ans =

   1.00000   1.00000   0.50000
   1.00000   1.00000   0.50000
   1.00000   1.00000   0.50000
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.50000
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.50000
   1.00000   1.00000   0.50000
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.50000
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.50000
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.73106
   1.00000   1.00000   0.50000

제출

octave:1> submit()
== Submitting solutions | Logistic Regression...
Use token from last successful submission (leejaymin@gmail.com)? (Y/n): 
== 
==                                   Part Name |     Score | Feedback
==                                   --------- |     ----- | --------
==                            Sigmoid Function |   5 /   5 | Nice work!
==                    Logistic Regression Cost |   0 /  30 | 
==                Logistic Regression Gradient |   0 /  30 | 
==                                     Predict |   0 /   5 | 
==        Regularized Logistic Regression Cost |   0 /  15 | 
==    Regularized Logistic Regression Gradient |   0 /  15 | 
==                                   --------------------------------
==                                             |   5 / 100 | 

1.2.2 Cost function and gradient

logistic regression의 cost function을 설계해 본다.
costFunction.m을 구현 하면 된다.

$$ J(\theta) = \frac{1}{m} \sum_{i=1}^{m}{-y^{(i)} log(h_{\theta}(x^{(i)})) - (1-y^{(i)}) log(1-h_{\theta}(x^{(i)})) } $$

vectorized cost function
$$ J(\theta) = \frac{1}{m}\big((\,log\,(g(X\theta))^Ty+(\,log\,(1-g(X\theta))^T(1-y)\big) $$

이 Cost function을 gradient descent 알고리즘을 적용 하면 아래와 같다.

Partial derivative
$$ \frac{\delta J(\theta)}{\delta\theta_{j}} = \frac{1}{m}\sum_{i=1}^{m} ( h_\theta (x^{(i)})-y^{(i)})x^{(i)}_{j} $$

Vectorized partial derivative
$$ \frac{\delta J(\theta)}{\delta\theta_{j}} = \frac{1}{m} X^T(g(X\theta)-y) $$

gradient descent formula 자체는 linear regression 때와 동일하다. 하지만 $h_{\theta}x$의 정의가 다른 것이다.

이제 초기 $\theta$의 값을 0,0,0 으로해서 계산을 수행해 보면
cost 값은 0.693이 나와야 한다.

costFunction.m

function [J, grad] = costFunction(theta, X, y)
%COSTFUNCTION Compute cost and gradient for logistic regression
%   J = COSTFUNCTION(theta, X, y) computes the cost of using theta as the
%   parameter for logistic regression and the gradient of the cost
%   w.r.t. to the parameters.

% Initialize some useful values
m = length(y); % number of training examples

% You need to return the following variables correctly
J = 0;
grad = zeros(size(theta));

% ====================== YOUR CODE HERE ======================
% Instructions: Compute the cost of a particular choice of theta.
%               You should set J to the cost.
%               Compute the partial derivatives and set grad to the partial
%               derivatives of the cost w.r.t. each parameter in theta
%
% Note: grad should have the same dimensions as theta
%

H_theta = sigmoid(X * theta);

J = (1.0/m) * sum(-y .* log(H_theta) - (1.0 - y) .* log(1.0 - H_theta));

grad = (1.0/m) .* X' * (H_theta - y);


% =============================================================

end

X matrix에 theta를 모두 곱한것이 z가 된다.
즉, $\theta^{T}x$인 향태인 것이다.
theta_0,1,2 순으로 저장이 되어 있다.

결국

octave:31> size(X)
ans =

   100     3

octave:32> size(initial_theta)
ans =

   3   1

[100,3] * [3,1] 을 수행해서 [100,1] 짜리 matrix를 생성 한다.
당연히 초기 theta들은 모두 0이므로 sigmoid(0)은 0.5이므로 H_thetha는 0으로 채워져 있다.

-y .* log(H_theta) - (1.0 - y) .* log(1.0 - H_theta)

의 값은 0.69315이고 이것이 100개 있다. 이대로 쭉 계산하면

1/100 * (0.69315) * 100 이므로 결과는 0.69315가 나온다.

두 번쨰로 gradient descent formula구현한 코드는

grad = (1.0/m) .* X' * (H_theta - y);

이다. 위와 같이 matrix 연산을 통해서 모든 training data와 모든wegiht vector ($\theta$)에 대해서 한번에 처리하게 된다.

그리고 이것에 대한 초기 gradient 조정 값은 아래와 같다.

Gradient at initial theta (zeros): 
 -0.100000 
 -12.009217 
 -11.262842 

제출

==                                   Part Name |     Score | Feedback
==                                   --------- |     ----- | --------
==                            Sigmoid Function |   5 /   5 | Nice work!
==                    Logistic Regression Cost |  30 /  30 | Nice work!

1.2.3 Learning parameters using fminunc

Linear regression에서는 gradient descent algorithm을 직접 구현 했었다. 하지만 여기서는 Octave에서 제공하는 fminunc라는 함수를 이용할 것이다.

fminunc

• initial values of the parameters we are trying to optimize.
• A function that, when given the training set and a particular $\theta$, computes the logistic regression cost and gradient with respect to $\theta$ for the dataset (X,y)

이것을 위해서는 어떤 parameters를 넣으면 될지는 아래와 같다.

%  Set options for fminunc
options = optimset('GradObj', 'on', 'MaxIter', 400);

%  Run fminunc to obtain the optimal theta
%  This function will return theta and the cost 
[theta, cost] = ...
    fminunc(@(t)(costFunction(t, X, y)), initial_theta, options);

GradObj를 option on으로 설정 했다.
gradient를 수행해서 최적화 하겠다는 의미이다.
MaxIter의 option은 400으로 설정 했다. 400번 이후로는 그냥 terminates 된다.

fminunc는 최적의 costfunction 값이 나올 때가지 400번 반복 한다. 그다음 최적의 weight vector가 저장된 theta와 그때의 cost를 반환 하게 된다.

재밌는 것은 지난번과 달리 loop를 만들지도 않았고learning rate도 따로 설정하지 않았다.
fminunc를 사용할때 설정할것은 cost와 gradient를 계산해줄 함수만 넣어주면 된다.

결국 아래의 과정이 수행된 것이다.

ex2.m을 실행하면 최적의 $\theta$ 값과 cost값으로 아래와 같이 출력 한다.

Program paused. Press enter to continue.

Cost at theta found by fminunc: 0.203498

theta: 
 -25.161272 
 0.206233 
 0.201470 

그리고 이미 작성된 코드 plotDecisionBoundary.m에 의해서 아래와 같이 Decision Boundary가 그려 진다.

1.2.4 Evaluating logisitic regression

이제 학습된 파라메터들을 이용해서 (wegiht vector, $\theta$) 어떤 학생의 시험점수 2개가 있다면 이 학생이 admission을 받을지 안받을지를 예측해 볼 수 있다.

예로
Exam 1 score: 45
Exam 2 score: 85
위와 같을때 admission probability는 0.776이다. 코드는 아래와 같다.

prob = sigmoid([1 45 85] * theta);
fprintf(['For a student with scores 45 and 85, we predict an admission ' ...
         'probability of %f\n\n'], prob);

이것을 위해서 predict.m파일을 구현 한다.

predict.m

function p = predict(theta, X)
%PREDICT Predict whether the label is 0 or 1 using learned logistic
%regression parameters theta
%   p = PREDICT(theta, X) computes the predictions for X using a
%   threshold at 0.5 (i.e., if sigmoid(theta'*x) >= 0.5, predict 1)

m = size(X, 1); % Number of training examples

% You need to return the following variables correctly
p = zeros(m, 1);

% ====================== YOUR CODE HERE ======================
% Instructions: Complete the following code to make predictions using
%               your learned logistic regression parameters.
%               You should set p to a vector of 0's and 1's
%

p = sigmoid(X * theta);

idx_1 = find(p >= 0.5);
idx_0 = find(p < 0.5);

p(idx_1) = ones(size(idx_1));
p(idx_0) = zeros(size(idx_0));

% =========================================================================
end

이제 작성된 predict함수를 이용해서 training data에 대한 prediction 정확도를 보자.

% Compute accuracy on our training set
p = predict(theta, X);

fprintf('Train Accuracy: %f\n', mean(double(p == y)) * 100);

정확도가 높이 나왔다. 이러한 검증 방식은 사실 문제가 있다.
학습 데이터로 모델을 평가하면 상당히 성능이 좋게 나오기 때문이다. overffting이 되면 될 수록 성능은 더 좋기 때문이다.
substitution error라고도 부른다.

Train Accuracy: 89.000000

여기까지 했을 때의 점수 이다.

==                                   Part Name |     Score | Feedback
==                                   --------- |     ----- | --------
==                            Sigmoid Function |   5 /   5 | Nice work!
==                    Logistic Regression Cost |  30 /  30 | Nice work!
==                Logistic Regression Gradient |  30 /  30 | Nice work!
==                                     Predict |   5 /   5 | Nice wor

Week 03: Regularization and Quiz

1. The problem of overfitting

첫 번째 그림의 모델의 상태를 underfitting이라고 하고 high bias인 상태라고 한다.

세 번째를 overfitting 이라고 부르며 high variance로도 알려져 있다.
이것은 high oder polynomial (고차 다항식)을 이용한 것으로 트레이닝 data에 거의 완벽히 fit 시키게 된다.
당연히 hypothesis의 space는 많은 공간을 차지하게 된다.

Overffting을 간단히 요약하면,
엄청나게 많은 feature들을 이용해서 학습하게 된다 그러면 cost function은 거의 zero에 다가서게 하는
함수를 만들 수 있다.

Addressing overfitting:

1. Reduce number of features.
   1. Manually select which features to keep
   2. Model selection algorithm (later in course)
2. Regularization
   1. Keep all features, but reduce magnitude of parameters θ
   2. Works well when we have a lot of features, each of which contributes a bit to predicting y

2. Cost Function

고차 다항식의 경우 좀더 구불 구블한 선을 만들어서
Training data에 더 fit한 모델을 생성 할 수 있다.

Regularization의 기본적인 아이디어는

$\theta_n$에 엄청나게 큰 값을 줘서 패널티를 주는 것이다.
그렇게 하면 min function에 의해서 $\theta_n$값은 결국 0에 가까워 질 수 밖에 없는 것이다.

결국 이것을 수식으로 나타내면 아래와 같다.

$$ J(\theta )=\frac { 1 }{ 2m } \left[ \sum { i=1 }^{ m }{ (h{ \theta }(x^{ (i) })-y^{ (i) })^{ 2 }+\lambda \sum _{ j=1 }^{ n }{ \theta _{ j }^{ 2 } } } \right] $$

그냥 convention에 의해서 \theta_0부터 시작하지 않고 \theta_1부터 시작 하는 것이다.
위에서 \lambda는 Regularization의 rate이 된다.

3. Regularized Linear Regression

• Previously, we looked at two algorithms for linear regression
  • Gradient descent
  • Normal equation
• Our linear regression with regularization is shown below

Regularization with the normal equation

• Normal equation is the other linear regression model
  • Minimize the J(θ) using the normal equation
  • To use regularization we add a term (+ λ [n+1 x n+1]) to the equation
    • [n+1 x n+1] is the n+1 identity matrix

4. Regularized Logistic Regression

logistic regression은 feature의 수가 늘어나면, overffting 되는 경향이 존재한다.

Logistic regression cost function은 다음과 같다.

이것에 아래의 추가 term을 더해서 regularization을 한다.

함수는 아래와 같다.

• Where y is a discrete value
  • Develop the logistic regression algorithm to determine what class a new input should fall into
• Classification problems
  • Email -> spam/not spam?
  • Online transactions -> fraudulent?
  • Tumor -> Malignant/benign
• Variable in these problems is Y
  • Y is either 0 or 1
    • 0 = negative class (absence of something)
    • 1 = positive class (presence of something)
• Start with binary class problems
  • Later look at multiclass classification problem, although this is just an extension of binary classification
• How do we develop a classification algorithm?
• • Tumour size vs malignancy (0 or 1)
  • We could use linear regression
  • • Then threshold the classifier output (i.e. anything over some value is yes, else no)
    • In our example below linear regression with thresholding seems to work

• We can see above this does a reasonable job of stratifying the data points into one of two classes
  • But what if we had a single Yes with a very small tumour 
  • This would lead to classifying all the existing yeses as nos
• Another issues with linear regression
  • We know Y is 0 or 1
  • Hypothesis can give values large than 1 or less than 0
• So, logistic regression generates a value where is always either 0 or 1
• • Logistic regression is a classification algorithm - don't be confused

• What function is used to represent our hypothesis in classification
• We want our classifier to output values between 0 and 1
• When using linear regression we did h_θ(x) = (θ^T x)
• For classification hypothesis representation we do h_θ(x) = g((θ^T x))
• Where we define g(z)
  • z is a real number
• g(z) = 1/(1 + e^-z)
  • This is the sigmoid function, or the logistic function
• If we combine these equations we can write out the hypothesis as
• 
• What does the sigmoid function look like
• Crosses 0.5 at the origin, then flattens out]
  • Asymptotes at 0 and 1

• Given this we need to fit θ to our data

• When our hypothesis (h_θ(x)) outputs a number, we treat that value as the estimated probability that y=1 on input x
  • Example
    • If X is a feature vector with x₀ = 1 (as always) and x₁ = tumourSize
    • h_θ(x) = 0.7
      • Tells a patient they have a 70% chance of a tumor being malignant
  • We can write this using the following notation
    • h_θ(x) = P(y=1|x ; θ)
  • What does this mean?
    • Probability that y=1, given x, parameterized by θ
• Since this is a binary classification task we know y = 0 or 1
  • So the following must be true
    • P(y=1|x ; θ) + P(y=0|x ; θ) = 1
    • P(y=0|x ; θ) = 1 - P(y=1|x ; θ)

• Gives a better sense of what the hypothesis function is computing
• Better understand of what the hypothesis function looks like
  • One way of using the sigmoid function is;
    
    • When the probability of y being 1 is greater than 0.5 then we can predict y = 1
    • Else we predict y = 0
  • When is it exactly that h_θ(x) is greater than 0.5?
    • Look at sigmoid function
      • g(z) is greater than or equal to 0.5 when z is greater than or equal to 0
        
      • 
      • 
        
    • So if z is positive, g(z) is greater than 0.5
      • z = (θ^T x)
    • So when 
      • θ^T x >= 0 
      • 결국 위와 같을 때, 즉 Z가 0보다 크다면 0.5 이상의 값이 되어서 logistic regression은 이 때 1로 prediction을 하게 된다.
    • Then h_θ >= 0.5
• So what we've shown is that the hypothesis predicts y = 1 when θ^T x >= 0 
  • The corollary of that when θ^T x <= 0 then the hypothesis predicts y = 0 
  • Let's use this to better understand how the hypothesis makes its predictions

• 좀 더 디테일 하게 들어가 보자.
• h_θ(x) = g(θ₀ + θ₁x₁ + θ₂x₂)

• 최종 적으로 학습을 통해서 hypethosis는 아래와 같은 weight vector를 가진다고 가정해 보자.
• So, for example
  • θ₀ = -3
  • θ₁ = 1
  • θ₂ = 1
• So our parameter vector is a column vector with the above values
  • So, θ^T is a row vector = [-3,1,1]
• What does this mean?
• 결국 위의 예제와 같이 0을 기점으로 1과 0의 prediction이 결정 된다.
• • The z here becomes θ^T x
  • We predict "y = 1" if
    • -3x₀ + 1x₁ + 1x₂ >= 0
    • -3 + x₁ + x₂ >= 0
• We can also re-write this as
  • If (x₁ + x₂ >= 3) then we predict y = 1
  • If we plot
    • x₁ + x₂ = 3 we graphically plot our decision boundary

• Means we have these two regions on the graph
• • Blue = false
  • Magenta = true
  • Line = decision boundary
  • • Concretely, the straight line is the set of points where h_θ(x) = 0.5 exactly
  • The decision boundary is a property of the hypothesis
    • Means we can create the boundary with the hypothesis and parameters without any data
      • Later, we use the data to determine the parameter values
    • i.e. y = 1 if
      • 5 - x₁ > 0
      • 5 > x₁

• 비선 형에 대해서도 고차원 다항식을 통해서 decision boundary를 얻을 수 있다.
• Get logistic regression to fit a complex non-linear data set
• • Like polynomial regress add higher order terms
  • So say we have
  • • h_θ(x) = g(θ₀ + θ₁x₁+ θ₃x₁² + θ₄x₂²)
    • We take the transpose of the θ vector times the input vector 
    • • Say θ^T was [-1,0,0,1,1] then we say;
      • Predict that "y = 1" if
      • • -1 + x₁² + x₂² >= 0
          or
        • x₁² + x₂² >= 1 
      • If we plot x₁² + x₂² = 1 (원의 방정식)
        • This gives us a circle with a radius of 1 around 0

• Mean we can build more complex decision boundaries by fitting complex parameters to this (relatively) simple hypothesis
• More complex decision boundaries?
• • By using higher order polynomial terms, we can get even more complex decision boundaries

• Fit θ parameters
• Define the optimization object for the cost function we use the fit the parameters
• • Training set of m training examples
  • • Each example has is n+1 length column vector

• This is the situation
  • Set of m training examples
  • Each example is a feature vector which is n+1 dimensional
  • x₀ = 1
  • y ∈ {0,1}
  • Hypothesis is based on parameters (θ)
    • Given the training set how to we chose/fit θ?
• Linear regression uses the following function to determine θ

• Instead of writing the squared error term, we can write
• • If we define "cost()" as;
    • cost(h_θ(xⁱ), y) = 1/2(h_θ(xⁱ) - yⁱ)²
    • Which evaluates to the cost for an individual example using the same measure as used in linear regression

  • We can redefine J(θ) as
    

    

    
    

    • Which, appropriately, is the sum of all the individual costs over the training data (i.e. the same as linear regression)

  • 
    

To further simplify it we can get rid of the superscripts
• So
  
• 
• 위에서 정의한 Cost Function은 linear regression에서는 optimization 알고리즘인 gradient descent로 잘 동작 했지만, hypothesis function이 sigmoid로 바뀐다면 이것은 optimize가 잘 되지 않는 문제점이 있다.
• 결국 다른 cost function의 구조를 찾아야 한다.

• What does this actually mean?
  • This is the cost you want the learning algorithm to pay if the outcome is h_θ(x) and the actual outcome is y
  • If we use this function for logistic regression this is a non-convex function for parameter optimization
    • Could work....
• What do we mean by non convex?
• We have some function - J(θ) - for determining the parameters
• Our hypothesis function has a non-linearity (sigmoid function of h_θ(x) )
  • This is a complicated non-linear function
• If you take h_θ(x) and plug it into the Cost() function, and them plug the Cost() function into J(θ) and plot J(θ) we find many local optimum -> non convex function
• 만약 이상태로 gradient descent algorithm을 실행 한다면, global minimum으로 converge 되지 않는다.
• 
  
• Why is this a problem
  • Lots of local minima mean gradient descent may not find the global optimum - may get stuck in a global minimum
• We would like a convex function so if you run gradient descent you converge to a global minimum

• To get around this we need a different, convex Cost() function which means we can apply gradient descent

• This is our logistic regression cost function
• • This is the penalty the algorithm pays
  • Plot the function
• Plot y = 1
• • So h_θ(x) evaluates as -log(h_θ(x))

• So when we're right, cost function is 0
  • Else it slowly increases cost function as we become "more" wrong
  • X axis is what we predict
  • Y axis is the cost associated with that prediction
• This cost functions has some interesting properties
  • If y = 1 and h_θ(x) = 1
    • If hypothesis predicts exactly 1 and thats exactly correct then that corresponds to 0 (exactly, not nearly 0)
  • As h_θ(x) goes to 0
    • Cost goes to infinity
    • This captures the intuition that if h_θ(x) = 0 (predict P (y=1|x; θ) = 0) but y = 1 this will penalize the learning algorithm with a massive cost
• What about if y = 0
• then cost is evaluated as -log(1- h_θ( x ))
• • Just get inverse of the other function

• Now it goes to plus infinity as h_θ(x) goes to 1
• With our particular cost functions J(θ) is going to be convex and avoid local minimum

• Define a simpler way to write the cost function and apply gradient descent to the logistic regression
  • By the end should be able to implement a fully functional logistic regression function
• Logistic regression cost function is as follows

• This is the cost for a single example
• • For binary classification problems y is always 0 or 1
  • • Because of this, we can have a simpler way to write the cost function
    • • Rather than writing cost function on two lines/two cases
      • Can compress them into one equation - more efficient 
  • Can write cost function is
    • cost(h_θ, (x),y) = -ylog( h_θ(x) ) - (1-y)log( 1- h_θ(x) ) 
      • This equation is a more compact of the two cases above
  • We know that there are only two possible cases
  • • y = 1
      • Then our equation simplifies to
        • -log(h_θ(x)) - (0)log(1 - h_θ(x))
          • -log(h_θ(x))
          • Which is what we had before when y = 1
    • y = 0
      • Then our equation simplifies to
        
        • -(0)log(h_θ(x)) - (1)log(1 - h_θ(x))
        • = -log(1- h_θ(x))
        • Which is what we had before when y = 0
    • Clever!
• So, in summary, our cost function for the θ parameters can be defined as
• 
  

• Why do we chose this function when other cost functions exist?
  • This cost function can be derived from statistics using the principle of maximum likelihood estimation
    • Note this does mean there's an underlying Gaussian assumption relating to the distribution of features 
  • Also has the nice property that it's convex
• To fit parameters θ:
  • Find parameters θ which minimize J(θ)
  • This means we have a set of parameters to use in our model for future predictions
• Then, if we're given some new example with set of features x, we can take the θ which we generated, and output our prediction using
          
• 
• 
  
• • This result is
  • • p(y=1 | x ; θ)
    • • Probability y = 1, given x, parameterized by θ

• Now we need to figure out how to minimize J(θ)
• • Use gradient descent as before
  • Repeatedly update each parameter using a learning rate

• Previously we looked at gradient descent for minimizing the cost function
• Here look at advanced concepts for minimizing the cost function for logistic regression
  • Good for large machine learning problems (e.g. huge feature set)
• What is gradient descent actually doing?
• • We have some cost function J(θ), and we want to minimize it
  • We need to write code which can take θ as input and compute the following
  • • J(θ)
    • Partial derivative if J(θ) with respect to j (where j=0 to j = n)

• Given code that can do these two things
  • Gradient descent repeatedly does the following update

• So update each j in θ sequentially
• So, we must;
  • Supply code to compute J(θ) and the derivatives
  • Then plug these values into gradient descent
• Alternatively, instead of gradient descent to minimize the cost function we could use
  • Conjugate gradient
  • BFGS (Broyden-Fletcher-Goldfarb-Shanno)
  • L-BFGS (Limited memory - BFGS)
• These are more optimized algorithms which take that same input and minimize the cost function
• These are very complicated algorithms
• Some properties
• • Advantages
    • No need to manually pick alpha (learning rate)
      • Have a clever inner loop (line search algorithm) which tries a bunch of alpha values and picks a good one
    • Often faster than gradient descent
      • Do more than just pick a good learning rate
    • Can be used successfully without understanding their complexity
  • Disadvantages
  • • Could make debugging more difficult
    • Should not be implemented themselves
    • Different libraries may use different implementations - may hit performance

• How to use algorithms
• • Say we have the following example

• Example above
  • θ₁ and θ₂ (two parameters)
  • Cost function here is J(θ) = (θ₁ - 5)² + ( θ₂ - 5)²
  • The derivatives of the J(θ) with respect to either θ₁ and θ₂ turns out to be the 2(θ_i - 5)
• First we need to define our cost function, which should have the following signature

• Input for the cost function is THETA, which is a vector of the θ parameters
• Two return values from costFunction are
  • jval
    • How we compute the cost function θ (the underived cost function) 
      • In this case = (θ₁ - 5)² + (θ₂ - 5)²
  • gradient
    • 2 by 1 vector
    • 2 elements are the two partial derivative terms
    • i.e. this is an n-dimensional vector
      • Each indexed value gives the partial derivatives for the partial derivative of J(θ) with respect to θ_i
      • Where i is the index position in the gradient vector 
• With the cost function implemented, we can call the advanced algorithm using

• Here
• • options is a data structure giving options for the algorithm
  • fminunc
    • function minimize the cost function (find minimum of unconstrained multivariable function)
  • @costFunction is a pointer to the costFunction function to be used
• For the octave implementation
  • initialTheta must be a matrix of at least two dimensions 

• How do we apply this to logistic regression?
• • Here we have a vector 

• Here
  • theta is a n+1 dimensional column vector
  • Octave indexes from 1, not 0
• Write a cost function which captures the cost function for logistic regression

• Getting logistic regression for multiclass classification using one vs. all
• Multiclass - more than yes or no (1 or 0)
• • Classification with multiple classes for assignment

• Given a dataset with three classes, how do we get a learning algorithm to work?
• • Use one vs. all classification make binary classification work for multiclass classification
• One vs. all classification
• Split the training set into three separate binary classification problems
• i.e. create a new fake training set
• Triangle (1) vs crosses and squares (0) h_θ¹(x)
  • P(y=1 | x₁; θ)
• Crosses (1) vs triangle and square (0) h_θ²(x)
  • P(y=1 | x₂; θ)
• Square (1) vs crosses and square (0) h_θ³(x)
• P(y=1 | x₃; θ)

• Overall
  
  • Train a logistic regression classifier h_θ⁽ⁱ⁾(x) for each class i to predict the probability that y = i
  • On a new input, x to make a prediction, pick the class i that maximizes the probability that h_θ⁽ⁱ⁾(x) = 1 

Assignment Linear Regression

Programming Excerise 1: Linear Regression

The file structure is as bellow.

ex1.m - Octave/MATLAB script that steps you through the exercise
ex1 multi.m - Octave/MATLAB script for the later parts of the exercise
ex1data1.txt - Dataset for linear regression with one variable
ex1data2.txt - Dataset for linear regression with multiple variables
submit.m - Submission script that sends your solutions to our servers
[] warmUpExercise.m - Simple example function in Octave/MATLAB
[] plotData.m - Function to display the dataset
[] computeCost.m - Function to compute the cost of linear regression
[] gradientDescent.m - Function to run gradient descent
[†] computeCostMulti.m - Cost function for multiple variables
[†] gradientDescentMulti.m - Gradient descent for multiple variables
[†] featureNormalize.m - Function to normalize features
[†] normalEqn.m - Function to compute the normal equations

* indicates files you will need to complete
† indicates optional exercises

warmUpExercise.m

This is wam up excerise.
Just make indentity matric 5x5.

open the files and write A=eye(5).
Then submit files to the server.

I am done for firt problem according to instruction of course.

>> warmUpExercise()

ans =

     1     0     0     0     0
     0     1     0     0     0
     0     0     1     0     0
     0     0     0     1     0
     0     0     0     0     1

>> submit()
== Submitting solutions | Linear Regression with Multiple Variables...
Login (email address): leejaymin@gmail.com
Token: QthyIC5bQxQOPOXf
== 
==                                   Part Name |     Score | Feedback
==                                   --------- |     ----- | --------
==                            Warm-up Exercise |  10 /  10 | Nice work!
==           Computing Cost (for One Variable) |   0 /  40 | 
==         Gradient Descent (for One Variable) |   0 /  50 | 
==                       Feature Normalization |   0 /   0 | 
==     Computing Cost (for Multiple Variables) |   0 /   0 | 
==   Gradient Descent (for Multiple Variables) |   0 /   0 | 
==                            Normal Equations |   0 /   0 | 
==                                   --------------------------------
==                                             |  10 / 100 | 
== 

Linear regression with one variable

Suppose you are the CEO of restaurant franchise and are considering different cities for opning a new branch.

You'd like to use this data to help you select which city to expand to next.

The file ex1data1.txt contains the dataset for our linear regression problem.
The first column is the population of a city and the second column is the profit of a food truck in that city.
A negative value for profit indicates loss.

6.1101,17.592
5.5277,9.1302
8.5186,13.662
7.0032,11.854
5.8598,6.8233
8.3829,11.886
7.4764,4.3483
8.5781,12

2.1 Plotting the Data

plot(x, y, 'rx', 'MarkerSize', 10); % Plot the data
ylabel('Profit in $10,000s'); % Set the y−axis label
xlabel('Population of City in 10,000s'); % Set the x−axis label

2.2 Gradient Descent

In this part, you will fit the linear regression parameters $\theta$ to our dataset using gradient descent.

2.2.1 Update Equations

The objective of linear regression is to minimize the cost function:

$$J(\theta)=\frac{ 1 }{ 2m } \sum_{ i=1 }^{ m }{ ( h_{\theta}(x^{(i)}) - y^{(i)})^{2}}$$

where the hypothesis $h_{\theta}(x)$ given by the linear model

hθ(x) = θT x = θ0 + θ1x1

Recall that the parameters of your model are the θj values. 
These are the values you will adjust to minimize cost J(θ). One way to do this is to use the batch gradient descent algorithm. 
In batch gradient descent, each iteration performs the update

$$\theta_{j} := \theta_{j} - \alpha \frac{1}{m} \sum_{i=1}^{m}{(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}}$$

(simultaneously update $\theta_{j}$ for all j).

With each step of gradient descent, your parameters \theta_{j} come closer to the optimal values that will achieve the lowest cost $J(\theta)$.

2.2.2 Implementation

In ex1.m, we have already set up the data for linear regression.
In the following lines, we add another dimension to our data to accomodate the $\theta{0}$ intercept term.
We also initialize the initial parameters to 0 and the learning rate alpha to 0.01.

X = [ones(m, 1), data(:,1)]; % Add a column of ones to x
theta = zeros(2, 1); % initialize fitting parameters
iterations = 1500;
alpha = 0.01;

2.2.3 Computing the cost $J(\theta)$
As you perform gradient descent to learn minimize the cost function J(\theta),
it is helpful to monitor the convergence by computing the cost.
In this section, you will implement a function to calculate $J(\theta)$ so you can check the convergence of your gradient descent implementation.

Your next task is to complete the code in the file computeCost.m, which
is a function that computes J(θ). As you are doing this, remember that the
variables X and y are not scalar values, but matrices whose rows represent
the examples from the training set.
Once you have completed the function, the next step in ex1.m will run
computeCost once using θ initialized to zeros, and you will see the cost
printed to the screen.

You should expect to see a cost of 32.07.

solution is as below:

function J = computeCost(X, y, theta)
%COMPUTECOST Compute cost for linear regression
%   J = COMPUTECOST(X, y, theta) computes the cost of using theta as the
%   parameter for linear regression to fit the data points in X and y

% Initialize some useful values
m = length(y); % number of training examples

% You need to return the following variables correctly 
J = 0;

% ====================== YOUR CODE HERE ======================
% Instructions: Compute the cost of a particular choice of theta
%               You should set J to the cost.

J = 1/(2*m) * (X * theta - y)' * (X * theta - y); % vectorized form


% =========================================================================
end

apostrophe means that a matrix will be transposed. 
Finally, above equation is equal to $J(\theta)=\frac{ 1 }{ 2m } \sum_{ i=1 }^{ m }{ ( h_{\theta}(x^{(i)}) - y^{(i)})^{2}}$

If you don't remember vertorized form, below lecture can make you to be getting better understanding.
For full contents, go back to the linear algebra lecuture.

%% =================== Part 3: Gradient descent ===================
fprintf('Running Gradient Descent ...\n')

X = [ones(m, 1), data(:,1)]; % Add a column of ones to x
theta = zeros(2, 1); % initialize fitting parameters

% Some gradient descent settings
iterations = 1500;
alpha = 0.01;

% compute and display initial cost
computeCost(X, y, theta)

The result

>> computeCost(X, y, theta)

ans =

   32.0727

Submit()

>> submit()
== Submitting solutions | Linear Regression with Multiple Variables...
Use token from last successful submission (leejaymin@gmail.com)? (Y/n): Y
== 
==                                   Part Name |     Score | Feedback
==                                   --------- |     ----- | --------
==                            Warm-up Exercise |  10 /  10 | Nice work!
==           Computing Cost (for One Variable) |  40 /  40 | Nice work!
==         Gradient Descent (for One Variable) |   0 /  50 | 
==                       Feature Normalization |   0 /   0 | 
==     Computing Cost (for Multiple Variables) |   0 /   0 | 
==   Gradient Descent (for Multiple Variables) |   0 /   0 | 
==                            Normal Equations |   0 /   0 | 
==                                   --------------------------------
==                                             |  50 / 100 | 

2.2.4 Gradient descent

Next, you will implement gradient descent in the file gradientDescent.m.
The loop structure has been written for you, and you only need to supply the updates to θ within each iteration.

As you program, make sure you understand what you are trying to optimize and what is being updated. 
Keep in mind that the cost J(θ) is parameterized by the vector θ, not X and y. 
That is, we minimize the value of J(θ) by changing the values of the vector θ, not by changing X or y. Refer to the equations in this handout and to the video lectures if you are uncertain.

A good way to verify that gradient descent is working correctly is to look at the value of J(θ) and check that it is decreasing with each step. 
The starter code for gradientDescent.m calls computeCost on every iteration and prints the cost. 
Assuming you have implemented gradient descent and computeCost correctly, your value of J(θ) should never increase, and should converge to a steady value by the end of the algorithm.

After you are finished, ex1.m will use your final parameters to plot the linear fit. 
The result should look something like Figure 2:

Your final values for θ will also be used to make predictions on profits in areas of 35,000 and 70,000 people. 
Note the way that the following lines in ex1.m uses matrix multiplication, rather than explicit summation or looping, to calculate the predictions.
This is an example of code vectorization in
Octave/MATLAB.

predict1 = [1, 3.5] * theta;
predict2 = [1, 7] * theta;

function [theta, J_history] = gradientDescent(X, y, theta, alpha, num_iters)
%GRADIENTDESCENT Performs gradient descent to learn theta
%   theta = GRADIENTDESENT(X, y, theta, alpha, num_iters) updates theta by 
%   taking num_iters gradient steps with learning rate alpha

% Initialize some useful values
m = length(y); % number of training examples
J_history = zeros(num_iters, 1);

for iter = 1:num_iters

    % ====================== YOUR CODE HERE ======================
    % Instructions: Perform a single gradient step on the parameter vector
    %               theta. 
    %
    % Hint: While debugging, it can be useful to print out the values
    %       of the cost function (computeCost) and gradient here.
    %
    Update = 0;
    for i=1:m,
        Update = Update + alpha/m * (theta' * X(i,:)' - y(i)) *  X(i,:)';
    end

    theta = theta - Update;

    % ============================================================

    % Save the cost J in every iteration    
    J_history(iter) = computeCost(X, y, theta);

end

end

what is meaning of :.
It is that selected all elements.

So, two eqautions are same.
$$\theta_{j} := \theta_{j} - \alpha \frac{1}{m} \sum_{i=1}^{m}{(h_{\theta}(x^{(i)})-y^{(i)})x_{j}^{(i)}}$$

    for i=1:m,
        Update = Update + alpha/m * (theta' * X(i,:)' - y(i)) *  X(i,:)';
    end

without loop, we can implement above function using vectorization.

That is as below:

% or a better way
H_theta = X * theta;
grad = (1/m).* x' * (H_theta - y);
theta = theta - alpha .* grad;

submit()

>> submit()
== Submitting solutions | Linear Regression with Multiple Variables...
Use token from last successful submission (leejaymin@gmail.com)? (Y/n): Y
== 
==                                   Part Name |     Score | Feedback
==                                   --------- |     ----- | --------
==                            Warm-up Exercise |  10 /  10 | Nice work!
==           Computing Cost (for One Variable) |  40 /  40 | Nice work!
==         Gradient Descent (for One Variable) |  50 /  50 | Nice work!
==                       Feature Normalization |   0 /   0 | 
==     Computing Cost (for Multiple Variables) |   0 /   0 | 
==   Gradient Descent (for Multiple Variables) |   0 /   0 | 
==                            Normal Equations |   0 /   0 | 
==                                   --------------------------------
==                                             | 100 / 100 | 
== 
>> 

Week 02: Octave Tutorial

목차

1. Basic operations
2. Moving Data Around
3. Computing on Data
4. Plotting data
5. For while if statements and functions
6. Vectorization

Basic operations

make 2x3 matrix, containing one values.

>> ones(2,3)

ans =

     1     1     1
     1     1     1

make 2x3 matrix, containing zero values.

>> zeros(2,3)

ans =

     0     0     0
     0     0     0

Computing on data

element-wise multiplication of two matrices.

A .* B

If you want to buy A transposed, the way to do that
apostrophe(')

A'

Vectorization

고속 linear alrgebra comptuing을 통해서
고속 병렬 처리를 수행 할 수 있다.
parallel hardware에 잘 적용이 되어 질 수도 있다.

아래와 같이 vectorized implementation으로 구현할 경우
코드의 길이가 절대적으로 줄어드는것은 물론
속도면에서도 많은 향상을 가져 온다.

다른 programming language에서는 해당 언어 syntax에 맞춰서 그렇게 처리하면 된다.

좀 더 복잡한 예제인 Gradient Descent를 보자.
j의 값은 0,1,2 로서 2차원 이라고 가정 하자.
그리고 아래와 같을때 모든 Theta는 simultaneously update 되어야 한다.

풀어서보면 vector끼리의 substraction의 형태로 처리 될 수 있다.

각각을 아래와 같이 간소화된 vector 연산으로 줄일 수 있다.
$$ \theta := \theta - \alpha \delta $$

Computing Parameters Analytically

Normal Equation

아래와 같이 점점 느리게 converge 하는 문제를 normal equation을 통해서 해결할 수 있다고 한다.

X는 training set vector를 의미한다.
Y는 prediction 할려는 vector를 의미한다.

X는 m by (n+1) dimensional matrix이다.
Y는 m-dimensional vector 이다.

m은 number of examples 이고
n은 number of features 이다.

https://en.wikipedia.org/wiki/Linear_least_squares_(mathematics)
https://en.wikipedia.org/wiki/Gramian_matrix

Linear Regression with multiple variables

multiple features

다중 feature와 다중 variable에 대해서 어떻게 linear regression을 적용하는지 알아 보겠다.

Gradient descent for multiple variables

아래와 같이 각각을 편미분(partial derivative)해서 동시에 업데이트하면서 최적화를 시키면 된다.
중요한것은 $X_0$를 항상 0으로 인지하기 때문에 $\theta_0$가 달라지지 않게 된다.
따라서 new algorithm 공식과 같이 간소화하여 작성할 수 있게 된다.

Gradient descent in pratice 1: Feature Scaling

이장에서는 pratical trick을 학습한다. 그것은 gradient descent를 잘 동작하게 하는 알고리즘이다.

서로다른 scale을 가지는 feature들에 대해서 feature scale을 비슷하게 해줄 경우 
Gradient descent algorihtm을 실행 했을때 좀 더 빠르게 converge 하게 된다.

서로다른 scale일 경우 아래의 그림과 같이 매우 Cost function J의 contour skinny elliptical shape을 가지게 된다.
이때 약간의 trick을 적용하면 좀더 circle스럽게 되고 금방 converge 된다.

좀 더 일반적으로 수식을 정리해 보자.

간단 수업 퀴즈

Gradient descent in practice 2: Learning rate

또 다른 TIP인 Learning Rate에서 다루겠다.

두가지 관점이 존재한다.

• Debugging: How to make sure gradient descent is working correctly.
• How to choose learning rate a.

아래의 그래프를 보면 이전에는 X축이 $\theta$ 이지만 현재는 그것이 아닌 interation이다.
$J(\theta)$ should decrease after every interation.
400 interation 이후로는 converge step의 정도가 줄어들게 된다.

하지만 이렇게 얼마만큼의 iteration 이후에 converge 될지를 예측하는 것은 매우 어려운 작업이다.

대부분의 경우에 대해서 x axis를 # of iterations로 설정 함으로써 gradient descent의 learning rate을 조절 할 수 
있게 된다.

Features and polynomial regression

적합한 featrue를 선택하는 방법에 대해서 다룬다.

Housing price를 prediction하는 문제에 대해서 생각해 보자.
아래와 같이 frontage와 depth 두개의 feature들이 있다고 생각해보자.
frontage는 앞부분 길이고 depth는 위에서 부터 아래까지의 길이를 의미한다.
따라서 두개의 feature를 그대로 반영해서 쓰는것보단 두개를 하나로 묶어서
$$ Area = frontage \times depth$$
로 계산하는 것이 좋다.

Polynomial regression

Quadratic model: $\theta_0+\theta_1x+\theta_2x^2$
하지만 qudratic model은 타당하지 않다. 왜냐면 다시 값이 내려가기 때문이다.
집 크기가 커진다고 가격이 작아질수는 없기 때문이다.

그럼 다른 삼차함수(cubic function)을 생각해 볼 수도 있다.
$$\theta_0+\theta_1x+\theta_2x^2+\theta_3x^3$$

위와 같이 서로다르게 size 값이 작용하므로 주의 있게 사용 해야 한다.

하지만 cubic 모델을 qudratic 모델의 대안으로 사용하는 것이 아닌 다른 방법을 생각해 볼 수도 있다.
square root(제곱근)함수를 사용 할 수도 있다.
급격히 올라가지만 그렇다고 다시 내려가지는 않게 된다.

Week 01 Linear Algebra Review

1.Matrices and Vectors

아래와 같이 $R^4$즉 4차원 Vector를 4행 1열 matrix로 표현할 수 있다.
그리고 각각의 값은 0으로 시작할수도 있고 1로 시작할 수도 있다.
마지막으로 대문자 A,B,C,X 와 같은것들은 보통 Vector를 나타내며, 소문자 a,b,c,x는 scalar를 나타낸다.

3.Matrix Vector Multiplication

Matrix 연산을 통해서 Hyposis fucntion의 연산을 한줄로 아래와 같이 끝낼 수 있다.
Computationably efficient 하다고 할 수 있다.

4.Matrix Vector Multiplication

matrix 곱하기 matrix의 공식은 아래와 같다.

Matrix 곱하기 Matrix을 이용해서
hypothesis 함수들의 연산을 효율적으로 할 수도 있다.

3개의 hypotheses 함수들에 대해서 4개의 house size 인자를 넣어서 각각 빠르게 계산할 수 있다.

5.Matrix Multiplication Properties

matrix multiplication은 하나의 연산으로 여러 연산들을 함축 할 수 있기 때문에 매우 강력한 연산 스타일이다.
하지만 여기서는 주의해서 사용해야할 부분들을 다루도록 한다.

교환법칙 (commutative law) 성립 안
결합법칙 (Associative law) 성립함

단위행렬 (Identity Matrix) 부분

중요한것은 $A \times I$의 경우 I는 n by n 이고
$I \times A$의 경우 I는 m by m 이라는 것이다.

6.Inverse and Transpose

Inverse Matrix은 Identity Matrix을 만들어 내는 것이다.

단 inverse matrix은 없을 수도 있다.
따라서 Machine Learning algorithm에서 이것을 처리하는 것이 중요하다고 할 수 있다.

Matrix Transpose

전치 행렬을 (Transpose Matrix)이라고 한다.