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


'MOOC > Machine Learning (python)' 카테고리의 다른 글

Week 10: Online Learning  (0) 2017.07.20
Week 05: 1. Neural Network Cost Function  (0) 2017.01.28
Programming Exercise 4: Neural Networks Learning  (0) 2017.01.02
Autonomous Driving Example  (0) 2016.10.12
Putting it together  (0) 2016.10.12

Loading [Contrib]/a11y/accessibility-menu.js

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을 아래와 같이 구할 수 있다.


'MOOC > Machine Learning (python)' 카테고리의 다른 글

Week 10: Online Learning  (0) 2017.07.20
Week 05: 2. Backpropagation Algorithm  (1) 2017.02.05
Programming Exercise 4: Neural Networks Learning  (0) 2017.01.02
Autonomous Driving Example  (0) 2016.10.12
Putting it together  (0) 2016.10.12

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를 다시 theta1theta2로 변경 한다.
  • 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(fx0fprime=Noneargs=()gtol=1e-05norm=inf,epsilon=1.4901161193847656e-08maxiter=Nonefull_output=0disp=1retall=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%


'MOOC > Machine Learning (python)' 카테고리의 다른 글

Week 05: 2. Backpropagation Algorithm  (1) 2017.02.05
Week 05: 1. Neural Network Cost Function  (0) 2017.01.28
Autonomous Driving Example  (0) 2016.10.12
Putting it together  (0) 2016.10.12
Random Initialization  (0) 2016.09.19

Autonomous Driving Example


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

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

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


'MOOC > Machine Learning (python)' 카테고리의 다른 글

Week 05: 1. Neural Network Cost Function  (0) 2017.01.28
Programming Exercise 4: Neural Networks Learning  (0) 2017.01.02
Putting it together  (0) 2016.10.12
Random Initialization  (0) 2016.09.19
Gradient Checking  (0) 2016.08.04

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