Stanford CS229: Machine Learning | Lecture 2 강의 정리

Stanford에서 2018년 가을학기에 열린 Andrew Ng 교수의 CS229 머신러닝 강의의 대부분의 내용을 번역 정리한 글입니다.

---

Course : Stanford CS229: Machine Learning Full Course taught by Andrew Ng | Autumn 2018

Course 소개 : CS229는 기계 학습과 통계적 패턴 인식에 대한 포괄적인 소개를 제공합니다. 지도 학습(생성적/판별적 학습, 모수/비모수 학습, 신경망, 서포트 벡터 머신); 비지도 학습(클러스터링, 차원 축소, 커널 메소드); 학습 이론(편향/분산 트레이드오프, 실용적인 조언); 강화 학습 및 적응 제어에 대한 강의를 다룹니다. 또한 기계 학습의 최근 응용에 대해 논의되며, 로봇 제어, 데이터 마이닝, 자율 항법, 생명 정보학, 음성 인식, 텍스트 및 웹 데이터 처리 등이 포함됩니다.

강의 제목 : Stanford CS229: Machine Learning - Linear Regression and Gradient Descent | Lecture 2 (Autumn 2018)

강의 영상: https://youtu.be/4b4MUYve_U8?si=z78_gh9cchHYs_kC

강의 자료 (복원): https://github.com/maxim5/cs229-2018-autumn

강의 syllabus : http://cs229.stanford.edu/syllabus-autumn2018.html

강의를 듣기 전에 알고 있어야 하는 내용

선형대수학 : https://cs229.stanford.edu/notes2022fall/cs229-linear_algebra_review.pdf

확률이론 : https://cs229.stanford.edu/notes2022fall/cs229-probability_review.pdf

---

Intro

Linear Regression과 이를 fitting하는 알고리즘인 Batch / stochastic gradient descent, linear model을 효율적으로 fitting하게 해주는 Normal equation에 대해 다룬다.

Motivate Linear Regression

Linear regression은 가장 간단한 학습 알고리즘 중 하나이다. ALVINN 영상 (자율주행 자동차 영상)은 supervised learning 문제이다. Input X (주행하는 차의 전면을 촬영한 사진)를 Output Y (운전 방향)에 mapping 한다. Output Y가 continuous value이기 때문에 이것은 Linear Regression이다. 더욱 간단한 예로 집의 size-price 데이터가 있을 때 우리는 size에 대한 price 직선을 fitting한다.

Supervised Learning

Superviesd Learning은 Training set을 learning algorithm에 feed 한다.
leraning algorithm은 prediction을 만드는 함수를 ouput 한다. 이 함수를 hypothesis(가설)이라고 한다. hypothesis은 아직 보지 못한 새로운 집의 크기를 input하면 estimated price을 output 한다.

Designing a Learning Algorithm

Learning algorithm을 설계할 때 가장 먼저 어떻게 hypothesis $H$를 표현할 것인가 정해야 한다. Linear regression에서는 $h(x) = \theta_0 + \theta_1 x$로 정의한다. 이 경우 X의 feature가 size 한 개인 경우이다.

data set $X$의 table

X의 feature가 size와 number of bedrooms 두 개일 경우 아래와 같이 표현이 가능하다.
$$
h(x) = \sum^2_{j=0} \theta_jx_j \ \ \ where\ \ x_0 =1
$$
이 경우 $\theta$ 는 3차원 parameter가 되고 feature 또한 3차원 feature가 된다.
$$
\theta = \begin{pmatrix}
\theta_{0} \\
\theta_{1} \\
\theta_{2} \\
\end{pmatrix}
,
\ \
x = \begin{pmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
\end{pmatrix}
$$
행렬을 이용하여 $h(x)$를 다음과 같이 정의할 수 있다.
$$
h(x) =\theta^Tx
$$

Parameters of the learning algorithm

Notations

• $ \theta : parameters$
• $ m : \#training\ examples\ (\# rows\ in\ table\ avobe)$
• $ X : inputs \ / \ features$
• $ y : output\ / \ target\ variable$
• $ (x,y) : training\ example$
• $ (x^{(i)},y^{(i)}) : i^{th}\ training\ example$
• 위의 예시의 경우 $ x^{(1)}_1 = 2014$, $ x^{(2)}_1 = 1600$ 이다.
• $ n={\rm\#} features$
• 위의 예시의 경우 $ n=2$이다.

주어진 위의 notation으로 hypothesis를 아래와 같이 정의할 수 있다.
$$
h(x) = \sum^n_{j=0} \theta_jx_j \ \ \ where\ \ x_0 =1
$$
learning algorithm은 parameters의 값을 정해야 hypothesis를 output으로 내놓을 수 있다. 그렇다면 어떻게 $\theta$를 정해야 할까?
$$ choose \ \theta \ such \ that \ h(x) \approx\ y \ for \ training\ example $$
hypothesis는 $ x$와 $ \theta$에 의존하기 때문에 $ h_{\theta}(x)$로 쓰기도 한다.

Linear Regression Algorithm

Linera regression에서는 아래와 같은 cost function $ J(\theta)$를 정의한다.
$$
J(\theta) = \frac{1}{2} \sum^m_{i=1}\left( h_\theta(x^{(i)})-y^{(i)}\right)^2
$$
$ \frac{1}{2}$ 상수를 곱해준 것은 수학 연산을 쉽게 해주기 위함이다. 위 식이 제곱식이기 때문에 미분했을때 나오는 $ 2$와 곱해져 식이 간단해진다. 위의 cost function을 최소화하는 $ \theta$를 구한다.
$$
\underset{\theta}{\arg\min} \ J(\theta)
$$

Gradient Descent Algorithm

어떤 $ \theta$로 시작해서 ($ \theta=\vec0$) $ J(\theta)$를 감소시키는 방향으로 바꿔준다.
data set이 고정되어 있기 때문에 $ J$는 고정되어 있는 $ \theta$에 대한 함수이다. 따라서 우리가 할 수 있는 것은 $ \theta$를 바꾸어 주는 것 뿐이다.

gradient descent의 각 단계는 아래와 같이 구현된다. (update rule)
$$
\theta_j := \theta_j - \alpha \frac{\partial}{\partial \theta_j}J(\theta)
$$
$ :=$의 의미는 우변을 좌변에 대입한다는 것이다. $ =$와 차이를 보이기 위해 비교하면 $ a:=a+1$은 $ a$를 $ 1$씩 증가시킨다는 의미이다. 반면 $ a=a+1$ 성립하지 않는 식이다.

$ \alpha$는 learning rate를 의미하고 $ \frac{\partial}{\partial \theta_j}J(\theta)$는 $ J(\theta)$의 $ \theta$에 대한 편미분을 의미한다. 편미분 값은 아래와 같이 구할 수 있다.

$$ \begin{align}
\frac{\partial}{\partial \theta_j}J(\theta)\ & = \frac{\partial}{\partial \theta_j} \frac{1}{2}(h_\theta(x)-y)^2 \\
& = 2 \cdot \frac{1}{2}(h_\theta(x)-y) \frac{\partial}{\partial \theta_j}(h_\theta(x)-y) \\
&=(h_\theta(x))-y \cdot \frac{\partial}{\partial \theta_j}\left( \sum^n_{i=0}\theta_ix_i-y\right) \\
&=(h_\theta(x)-y)\ x_j
\end{align}
$$
위 식에 의해 update rule은 다음과 같다.
$$
\theta_j := \theta_j + \alpha (y^{(i)}-h_\theta(x^{(i)}))\ x^{(i)}_j
$$
이 식은 LMS update rule (least mean squares)라고 한다.

Batch Gradient Descent

위의 LMS update rule의 경우 하나의 training example에 대해서만 업데이트한 경우이다. 이것은 두가지로 변형될 수 있는데 첫번째는 아래와 같다.

$$
\begin{align}
& {\rm Repeat\ until\ convergence\ }\{ & \\
&\quad \theta_j := \theta_j + \alpha \sum^m_{i=1} \left(y^{(i)}-h_\theta(x^{(i)})\right)\ x^{(i)}_j & {\rm(for\ every}\ j)\\
\}{}
\end{align}
$$
모든 step에서 training set 전체의 sample들을($ m$개) 확인하여 업데이트 한다. 이것을 Batch Gradient Descent라고 한다.

Linear regression에서 정의한 Cost function은 제곱항의 합 즉, 이차함수이다. 따라서 $ J(\theta)$를 plot 하면 항상 아래와 같은 그림이 나온다.

plot of cost function

$ J(\theta)$는 오직 하나의 global minimun만 가지고 있기 때문에 각 step은 downhill을 따라 이동하여 수렴한다.

plot of cost function

하지만 learning rate($ \alpha$)를 매우 크게 한다면 overshoot 되어 minimum을 지나치게 된다. 만약 learning rate($ \alpha$) 매우 작게 한다면 매우 많은 반복이 필요하여 알고리즘이 느려지게 된다. learning rate($ \alpha$)는 실험을 통해 어떤 값이 가장 효율적인지 구해야 한다. 만약 cost function이 감소하는 것이 아닌 오히려 증가한다면 이것은 learning rate($ \alpha$)가 너무 크다는 강한 신호이다. learning rate($ \alpha$)를 두배, 세배하여 어떤 값이 cost function을 가장 빠르게 감소시키는지 찾아야한다.

regression

gradient descent의 iteration이 반복되면 hypothesis의 $ \theta_0$와 $ \theta_1$은 위와 결국 같이 수렴하게 된다.

Batch gradient descent는 각 step에서 모든 training exapmles를 모두 확인하기 때문에 sample의 개수가 수십,수백만개라면 각 step은 매우 오래걸리게 된다. 만약 cost function이 수렴하기까지 수천, 수만번의 iteration을 반복한다면 이 알고리즘은 매우 비싸지게된다. 이것을 보완하기 위해 나온 것이 Stochastic Gradient Descent이다.

Stochastic Gradient Descent

아래 알고리즘은 Stochasctic Gradient Descent라고 부른다. 여기선 Loop 안에서 한 개의 example에 대해서만 $ \theta$를 업데이트 한다.
$$
\begin{align}
& {\rm Loop\ }\{ & \\
&\quad {\rm for\ i=1 \ to\ m,\{}\\
&\quad\quad \theta_j := \theta_j + \alpha \left(y^{(i)}-h_\theta(x^{(i)})\right)\ x^{(i)}_j & {\rm(for\ every}\ j)\\
&\quad \}\\
\}{}
\end{align}
$$
각 Loop에서 $ \theta$를 업데이트 할 때 하나의 example만 확인하기 때문에 Loop가 끝날 때 parameter가 개선되긴 하지만 그것이 downhill을 곧바로 내려가는 방향은 아니다. 따라서 약간 rando하고 지저분한 방향으로 global minimum을 향해 내려간다. Batch gradient descent에서 global minimum까지 내려가 수렴하여 멈춘 반면에 Stochastic gradient descent에선 완전히 수렴하지 않고 그 주위에서 진동한다.

Global minimum에 완벽히 수렴하지 않더라도 dataset의 크기가 매우 큰 경우 Stochastic gradient descent가 global minimum에 더욱 빨리 접근하기 때문에 이 방법을 사용한다.

Q&A

Q1: stochastic gradient descent를 사용하여 global minimum에 접근 한 뒤 bacth gradient descent를 사용하는 것도 가능한가?

A1: 가능하다. 하지만 dataset이 매우 큰 경우 방법을 바꾸는 것은 거의 사용하지 않는다. 현대의 머신러닝에선 terabyte의 데이터를 사용한다. 따라서 모든 데이터를 확인하는 하나의 step 또한 매우 expensive 하다. 꼭 정확한 global minimum에 도달하지 않아도 된다. 그 근처의 값 또한 나쁘지 않은 값이다. 정확한 global minimum을 찾으려고 고통받지 않아도 된다. 보다 정확한 parameter를 얻기 위해 일반적으로 learning rate를 감소하는 방법을 사용한다. parameter가 진동하는 크기가 감소하여 global minimum 주변의 작은 영역에서 진동하고 있다면 그중에서 아무 값을 취하면 된다. 정확한 global minimum이 아니어도 되지만 최소한 그것과 더 가까운 값이어야 한다. cs230 course에서 다룬 mini-batch gradient descent라는 방법도 있다. 각 step에서 1개의 sample을 확인하는 대신 100개의 sample을 확인 하는 것이다. 이것이 더욱 자주 쓰인다.

Q2: Stochastic gradient를 언제 멈춰야 하는가?

A2: $J(\theta)$를 보면서 감소하는 것이 멈춘 것 같아 보이면 멈추면 된다. linear regression은 local optimum이 없기 때문에 convergence debugging type issue를 덜 겪게 된다. neural network와 같은 highly non-linear한 방법에서는 이 issue를 더욱 고려해야된다.

Normal equation

이 course에서 다루는 generalized linear models, neural networks와 같은 다른 알고리즘은 gradient descent를 사용해야한다. Linear regression에는 gradient descent와 같은 iterative한 알고리즘 없이 optimal value를 바로 구하는 방법이 있다. 이것을 Normal equation이라고 부르고 linear regression에서만 유효하고 이후에 다루게 되는 다른 알고리즘에선 유효하지 않는다.

Notations

• matrix derivative : $ \nabla_{\theta}J(\theta) = \begin{bmatrix} \frac{\partial J(\theta)}{\partial \theta_{0}} \\ \frac{\partial J(\theta)}{\partial \theta_1} \\ \frac{\partial J(\theta)}{\partial \theta_2} \end{bmatrix}$, $\theta \in \mathbb{R}^{n+1}$, $n=2\ {\rm number \ of \ feature}$
• If $ A$ is square matrix ($ A \in \mathbb{R}^{n \times n}$), $ {\rm tr} A$ = sum of diagonal entries = $ \sum_{i}A_{ii}$
• $ {\rm tr}A = {\rm tr}A^T$
• $ f(A) = {\rm tr}\ A$, $ \nabla_{A}f(A)=B^{T}$
• $ {\rm tr}AB = {\rm tr}BA$
• $ {\rm tr}ABC = {\rm tr}CBA$
• $ \nabla_{A}\ {\rm tr}AA^TC=CA+C^TA$

training examples이 담긴 행렬 $X$를 아래와 같이 정의한다. 이것은 design matrix라고 불린다.
$$
X = \begin{bmatrix} (x^{(1)})^{T}\\ (x^{(2)})^{T} \\ \vdots \\ (x^{(m)})^{T} \end{bmatrix}
$$

$ X$에 $ \theta$를 곱하면 이것은 알고리즘의 모든 예측값의 vector가 된다.

$$
X\theta = \begin{bmatrix} (x^{(1)})^{T}\\ (x^{(2)})^{T} \\ \vdots \\ (x^{(m)})^{T} \end{bmatrix}
\begin{bmatrix} \theta_0 \\ \theta_1 \\ \theta_2
\end{bmatrix}
=
\begin{bmatrix} (x^{(1)})^T\theta \\ (x^{(2)})^T\theta \\ \vdots \\ (x^{(m)})^T\theta
\end{bmatrix}
=
\begin{bmatrix}
h_\theta(x^{(1)}) \\ h_\theta(x^{(2)}) \\ \vdots \\ h_\theta(x^{(m)})
\end{bmatrix}
$$
다음으로 training examples의 모든 label이 담긴 comlumn vector $ y$를 정의한다.
$$
y=
\begin{bmatrix}
y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(m)}
\end{bmatrix}
$$

$ J(\theta)$는 위의 행렬들을 이용하여 아래처럼 쓸 수 있다.

$$
J(\theta) = \frac{1}{2} \sum^m_{i=1}\left( h_\theta(x^{(i)}-y^{(i)}\right)^{2}= \frac{1}{2}\left( (X\theta-y)^T(X\theta-y\right)
$$

$ X\theta$는 $m$개의 examples에 대한 learning algorithms의 모든 errors를 담고 있다. 이것은 예측값과 실제 label과의 차이 이다.

$$
X\theta-y=\begin{bmatrix}
h_\theta(x^{(1)})-y^{(1)} \\ h_\theta(x^{(2)})-y^{(2)} \\ \vdots \\ h_\theta(x^{(m)})-y^{(m)}
\end{bmatrix}
$$

$ Z^TZ=\sum\limits_{i}z^2$ 즉 각 요소들의 제곱합이다. $ (X\theta-y)(X\theta-y)^T$는 모든 error들의 제곱 합이 된다. 따라서 $ J(\theta)$는 위와 같이 정의될 수 있다. $ J(\theta)$를 $ \theta$에 대해 미분하면 아래와 같다.

$$
\begin{align}
\nabla_{\theta}J(\theta) & = \nabla_{\theta}\frac{1}{2}\left( (X\theta-y)^T(X\theta-y\right)\\
& =\frac{1}{2}\nabla_{\theta} \left( \theta^TX^TX\theta-\theta^TX^Ty-y^TX\theta+y^Ty \right) \\
& = \frac{1}{2}\nabla_{\theta} {\rm tr} \left( \theta^TX^TX\theta-\theta^TX^Ty-y^TX\theta+y^Ty \right) \\
& = \frac{1}{2} \nabla_{\theta}\left({\rm tr}\theta^TX^TX\theta-2{\rm tr}y^TX\theta \right) \\
& = \frac{1}{2} \left( X^{T}X\theta+ X^{T}X\theta-2X^{T}y\right) \\
& = X^TX\theta-X^Ty \\ & \stackrel{set}{=}0
\end{align}
$$
미분 값이 $ 0$이 되면 $ \theta$값이 최소가 된다. 즉 $ X^TX\theta=X^Ty$ 을 풀어주면 된다. 따라서 $ \theta=(X^TX)^{-1}X^{T}y$로 구할 수 있다. 이 방법을 사용하면 한 번에 global minimum에 대응하면 $ \theta$를 구할 수 있다.