@Chapter
03. Gradient Descent & Normal Equation.
@
Line fitting 방법
gradient descent.
normal equation.

두 개 비교하면서 왜 gradient descent를 쓰는지 알아보자.
@
Gradient descent is
$W := W - \alpha \frac{\partial C}{\partial W}$
@
Normal equation에 대해 알아보자.
$y = a x + b$ 에서,
정의역은 실수이며 x는 입력 데이터 역할이다.
y는 목표값 역할이다.
두개가 더해지면 data set이다. 입력데이터와 그 데이터에 대한 정답으로 구성되어있다.
@
위 식을 matrix로 표현해보자.
$y = a x + b 1$
변수는 여러가지 값이 대입될수 있는 것이다. 그래서 x는 벡터보다는 일반적으로는 행렬이라고 보는게 타당하다.
x도 여러개, y도 여러개이므로, (단, a, b는 정의역과 치역에 대해 항상 일정하므로 항상 벡터이다.)
$\begin{bmatrix} y \end{bmatrix} = \begin{bmatrix} x&1 \end{bmatrix} \begin{bmatrix} a\\b \end{bmatrix}
$
일반적으로 행렬 [x, 1] 이 앞에서 곱해지고 뒤에 벡터가 오는게 맞다. 일반적으로 그렇게 계산한다. 벡터가 앞에
오는 경우는 거의 없다. 행렬(앞)에 벡터(뒤)를 곱해서 벡터가 나오는게 일반적이다.
[y] 와 [x, 1] 를 지금은 간단하게 표현했지만 데이터가 여러개가 들어올때는 여러값을 가질 수 있는 행렬이다.
예를들어,
$\begin{bmatrix} y_{0}\\y_{1}\\...\\y_{m} \end{bmatrix} = \begin{bmatrix} x_{0}&1 \\ x_{1}&1 \\ ...
x_{m}&1 \end{bmatrix} \begin{bmatrix} a\\b \end{bmatrix} $ 에서,
$\begin{bmatrix} y_{0}\\y_{1}\\...\\y_{m} \end{bmatrix}$ 와 $\begin{bmatrix} x_{0}&1 \\ x_{1}&1 \\ ...
\\ x_{m}&1 \end{bmatrix}$ 의 각각의 정의역, 공역에 대해서 항상 일정한 상수가 나오므로 [a, b] 을 그대로 쓰면
된다.
@
위의 식을 방정식을 풀어서 우리는 [a, b] 를 구해야한다.
@
사실 gradient descent도 마찬가지이다.
$W := W - \alpha \frac{\partial C}{\partial W}$
위 식을 볼 때, 위에서 표현된 방정식( $y=ax+b$ ) 관점에서 이렇게 볼수도 있다.
$ a := a - \alpha \frac{\partial C}{\partial a}$
$ b := b - \alpha \frac{\partial C}{\partial b}$
이 때에, 각각, a와 b를 구하는 것이다.
@
어쨌든,
$\begin{bmatrix} y_{0}\\y_{1}\\...\\y_{m} \end{bmatrix} = \begin{bmatrix} x_{0}&1 \\ x_{1}&1 \\ ...
x_{m}&1 \end{bmatrix} \begin{bmatrix} a\\b \end{bmatrix} $
위 식에서 $\begin{bmatrix} a\\b \end{bmatrix}$ 를 구해보자.
@
matrix 계산할 때 $\begin{bmatrix} x_{0}&1 \\ x_{1}&1 \\ ... \\ x_{m}&1 \end{bmatrix}$ 이 곱해져있으므로,
이 행렬의 역행렬을 양변에 곱해서 $\begin{bmatrix} a\\b \end{bmatrix}$ 를 구할 수 있다.
@
그런데 기본적으로, 행과 열이 같지 않은 비정방행렬에 대해서는 역행렬을 구할 수 없다. 행과 열이 같아야 행렬식을
구할수 있고, 행렬식을 알아야지 역행렬을 구할 수 있기때문에, 일반적으로 정방행렬이 아니면 역행렬이 존재하지
않는다 라고 생각해도 된다.
따라서 먼저 정방행렬로 만들어주는 작업이 필요하다.
이때 pseudo inverse 라는 테크닉을 쓴다. pseudo inverse 는 임의의 크기를 가지는 행렬을 정방행렬로 만들어 주는
방법이다.
$\begin{bmatrix} y_{0}\\y_{1}\\...\\y_{m} \end{bmatrix} = \begin{bmatrix} x_{0}&1 \\ x_{1}&1 \\ ...
x_{m}&1 \end{bmatrix} \begin{bmatrix} a\\b \end{bmatrix} $ 이 수식에서,
$\begin{bmatrix} x_{0}&1 \\ x_{1}&1 \\ ... \\ x_{m}&1 \end{bmatrix}$는 m*2 크기의 행렬이다.
따라서, 2*m 행렬을 앞에 곱해주면 2*2 행렬을 만들수 있다. 그리고 2*m 행렬은 transpose 해서 만든다.
일반적으로, 자기자신의 transpose를 앞에다 곱해주면 정방행렬이 나온다.
$\begin{bmatrix} y_{0}\\y_{1}\\...\\y_{m} \end{bmatrix} = \begin{bmatrix} x_{0}&1 \\ x_{1}&1 \\ ...
x_{m}&1 \end{bmatrix} \begin{bmatrix} a\\b \end{bmatrix} $
자기 자신의 transpose 앞에다 곱해준다. 좌변의 Y앞에도.
$ \begin{bmatrix} x_{0}&x_{1}&...&x_{m} \\ 1&1&...&1 \end{bmatrix} \begin{bmatrix} y_{0}\\y_{1}
\\...\\y_{m} \end{bmatrix} = \begin{bmatrix} x_{0}&x_{1}&...&x_{m} \\ 1&1&...&1 \end{bmatrix} \begin
{bmatrix} x_{0}&1 \\ x_{1}&1 \\ ... \\ x_{m}&1 \end{bmatrix} \begin{bmatrix} a\\b \end{bmatrix} $
따라서, 아래와 같은 형태로 정리된다.
$X^{T}Y = X^{T}XA $
@
$X^{T}$ 의 역행렬을 구한다. $(X^{T})^{-1}$
양변에 구한 역행렬을 곱한다.
$(X^{T})^{-1}X^{T}Y = (X^{T})^{-1}X^{T}XA $
= $IA$ ( I, A 가 모두 2*2 라면 )
= A
따라서, 데이터 셋을 이용해서 $(X^{T})^{-1}X^{T}Y$ 연산을 해주면 A (기울기, y절편) 가 구해진다.

@
이렇게 normal equation ($(X^{T})^{-1}X^{T}Y$)으로 행렬연산을 통해 기울기와 y절편을 쉽게 구할 수 있는데 왜
gradient descent 가 더 좋다고 하냐?
거기엔 이유가 있다.
@
비교.
Gradient descent
1.
가장 큰 장점 : 배치를 쓸 필요가 없다.
데이터 셋이 쭉 있을때 그걸 다 수행할 필요가 없다.
모두 알 필요없이 하나만 알고 이 데이터에 fitting할 hypothesis function만 알고 있으면 그리고 이 함수가 미분이
가능하면, cost function을 구해서 gradient descent 를 사용할수있다.
우리는 gradient descent를 사용할때 어쨌든 초기값을 정해준다.
그리고 데이터 하나 하나에 대해서 hypothesis function에 대한 cost를 즉각즉각 알수 있다.
그래서 굳이 데이터를 다 알지 않아도 hypothesis function만 알고있으면 batch process 필요없이 구할 수 있다.
1.
데이터셋이 10만개 있을때, gradient descent는 데이터셋을 다 보지 않아도 프로세스를 끝낼 수 있다. 만약
2만개에서 cost function이 최소점으로 가면 더이상 움직이지 않을것이다. 중지조건이 명확하다.
단점:
1.
learning rate ($\alpha$) 이 있다. 이걸 튜닝을 잘해야한다.
Normal equation
1.
무조건 batch process로 풀어야한다. 데이터를 모아야한다는 말이다.
모으면서 하나하나 하려고 하면, 현재 matrix 안에 있는 데이터의 평균을 내는 것 이기때문에, 전체 matrix들에서
모든 데이터가 다 들어가야한다.
그럼 matrix에 데이터 채우는데도 시간이 오래걸리고, 연산하고 꺼내는데도 시간이 걸린다. matrix 연산은 차원이
많아질수록 연산이 굉장히 폭발적으로 많아진다.
1.
learning rate 이 없다. batch size을 다 알고 있기 때문에 그렇다. 데이터를 전부 알고 있으니까 그것의 평균선을
구하면 되니까 learning rate이 따로 필요없이 바로 구할수가 있는 것이다.
1.
모든 데이터에 대해 연산을 시작하기 때문에 모든 데이터를 알지 못하면, 예를들어 10만개중 2만개만 넣었으면 2만개에
대해서만 hypothesis function이 fitting이 되는 것이다.
@
따라서, 머신러닝이나 딥러닝에서는 cost function에서 최소점을 찾는 알고리즘으로서는 normal equation보다는
gradient descent가 더 적합하다.