[머신러닝 코세라 강의] (2주차) "Gradient Descent 벡터 표현" Machine Learning (by Andrew Ng)

 

Andrew Ng 교수님의 Coursera 머신 러닝 수업 중 Octave 를 사용하는 튜토리얼 내용을 정리중이다. 오늘은 다른 프로그래밍 언어에서도 참고할만한 vectorization 개념과 Octave 코드에 대해서 다루어보도록 하겠다. 파이썬 코드는 다음 포스팅에 마련해두어야겠다. 

 

Octave 관련 내용 목차: 

(1) Basic Operations

(2) Moving Data Around

(3) Computing Data

(4) Plotting Data

(5) Control Statements: for, while, if statement
[Octave 관련 이전 포스팅, (1-5) 바로가기 링크]

(6) Vectorization (이번 포스트)

 

(6) Vectorization

 

(numerical) linear algebra 라이브러리를 이용하면 속도가 더 빨라질 수 있다.

 

$$h_{\theta }(x)=\sum _{j=0}^n{\theta }_j{x}_j$$

$$={\theta }^{T}x$$

where $\theta$ 와 $x$ 는 vector. 

 

Unvectorized implementation.

octave:3> prediction = 0.0;

octave:4> n = length(x)

n =  3

octave:5> for j = 1:n,

> prediction = prediction + theta(j)*x(j)

> end;

prediction =  2

prediction =  14

prediction =  44

 

Vectorized implementation.

octave:6> prediction = theta'*x;

octave:7> prediction

prediction =  44

 

두 값이 동일함을 볼 수 있다. 코드도 짧고 속도도 빠르다.

 

Gradient descent

$${\theta }_j:={\theta }_j-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x_i)-y_i)x_i^j$$

for $n=2$, 

${\theta }_0:={\theta }_j-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x_i)-y_i)x_i^0$

${\theta }_1:={\theta }_j-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x_i)-y_i)x_i^1$

${\theta }_2:={\theta }_j-\alpha \frac{1}{m}\sum _{i=1}^m(h_{\theta }(x_i)-y_i)x_i^2$

를 벡터 형태로 만들어보자. 

$$\theta :=\theta -\alpha \delta$$

where $\delta =\frac{1}{m}\sum _{i=1}^m(h_{\theta }(x_i)-y_i)x_i$ 

에서 $\theta \in {\mathbb{R}}^{n+1}$, $\alpha \in {\mathbb{R}}^n$, $\delta \in {\mathbb{R}}^{n+1}$. 

 

$\delta$ 에 집중해보자. 

${\delta }_0=\frac{1}{m}\sum _{i=1}^m(h_{\theta }(x_i)-y_i)x_i^0$.

 

인데, $(h_{\theta }(x_i)-y_i)\in \mathbb{R}$ 이고, $x_i\in {\mathbb{R}}^{n+1}$. 

$\delta =\sum _{i=1}^m(h_{\theta }(x_i)-y_i)x_i=(h_{\theta }(x_1)-y_1)x_1+(h_{\theta }(x_2)-y_2)x_2+...+(h_{\theta }(x_n)-y_n)x_n$ 이다.

여기서 각각의 $(h_{\theta }(x_i)-y_i)x_i$ 는 scala $\times$ vector 형태이다.  

 

$\delta$ 를 매트릭스의 곱형태로 표현해보자. 

 

$\delta =\sum _{i=1}^m(h_{\theta }(x_i)-y_i)x_i=(h_{\theta }(x_1)-y_1)x_1+(h_{\theta }(x_2)-y_2)x_2+...+(h_{\theta }(x_n)-y_n)x_n$

$=(h_{\theta }(x_1)-y_1)\left[\begin{array}{c}{x}_1^0\\ x_1^1\\ x_1^2\end{array}\right]+(h_{\theta }(x_2)-y_2)\left[\begin{array}{c}{x}_2^0\\ x_2^1\\ x_2^2\end{array}\right]+...+(h_{\theta }(x_n)-y_n)\left[\begin{array}{c}{x}_n^0\\ x_n^1\\ x_n^2\end{array}\right]$

$=\left[\begin{array}{cccc}{x}_1^0& x_2^0& ...& x_n^0\\ x_1^1& x_2^1& ...& x_n^1\\ x_1^2& x_2^2& ...& x_n^2\end{array}\right]\left[\begin{array}{c}(h_{\theta }(x_1)-y_1)\\ (h_{\theta }(x_2)-y_2)\\ ...\\ (h_{\theta }(x_n)-y_n)\end{array}\right]$

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

where $y=\left[\begin{array}{c}{y}_1\\ y_2\\ ...\\ y_n\end{array}\right]$

 

마무리하며

 

[ ] 추후에 gradient descent 알고리즘을 위의 matrix 방식을 적용하면 계산 속도가 더 빨라질 것 같다. 

     - cost function 과  gradient descent algorithm 을 for loop 을 이용해서 구하는 링크

 

부록

 

NOTE: $x^T(h_{\theta }(x)-y)$ 를 도출하는 과정에서 vector ($x^T$) 와 scala ($h_{\theta }(x_i)-y_i$) 들과 관련된 내용:

$\left[\begin{array}{ccc}1& 3& 5\\ 2& 4& 6\end{array}\right]\left[\begin{array}{c}a\\ b\\ c\end{array}\right]$

$=\left[\begin{array}{c}1a+3b+5c\\ 2a+4b+6c\end{array}\right]$

$=\left[\begin{array}{c}1\\ 2\end{array}\right]a+\left[\begin{array}{c}3\\ 4\end{array}\right]b+\left[\begin{array}{c}5\\ 6\end{array}\right]c$