[ML] 2. Binary Classification & Linear Regression

2.1 Binary Classification

• 이 챕터에서 쭉 다루게 되는 Linear Model이란 line들의 집합으로 이루어진 model로, 많은 문제들에 대해 종종 good choice가 된다. start로써 나쁘지 않다.

Chapter3에서는 크게 두가지의 중요한 문제에 대해 이런 linear model을 적용해볼 것이다.

1. classification
2. regression

2.1.1 Binary classifcation

binary classification을 위한 linear model을 정의해보자. d+1차원의 input vector x를 받아 출력을 내는 우리의 가설 h(x)에 대해
$$
h(x)=sign(w^Tx)
$$
로 정의할 수 있다. 이 때

• w는 d+1의 weight column vector (including bias element 1)
• d: input dimension
• x의 첫번째 성분은 원래의 input에 붙일 bias 성분인 1
• sign: 부호에 따라 1 or -1

물론 이런 linear모델은 실제로 적용하기 매우 어려운 경우가 많다. 선으로 쪼개지지 않는 non-linearly separable한 Data space의 경우에는 non-linear model을 사용하거나 input space를 linearly separable하게 바꿔줘야 한다.

그럼 이제 이런 linear model h에 대해 해야할 일은 h의 in-sample Error를 줄이는 것으로 다음 equation을 푸는 w를 찾는 것이 목표가 된다.(w가 h를 결정하므로)
$$
min \frac{1}{N}[sign(W^Tx_n) \ne y_n]
$$
그런데, 일반적으로 이 equation의 optimal solution을 구하는 것은 NP-hard문제이므로 local minimum을 구하는 근사적 solution을 많이 이용한다. 이 때 사용하는 algorithm을 pocket algorithm이라 한다. 이는 PLA를 simple하게 extend한 알고리즘인데 pseudo로는 다음과 같다.

set the pocket weight vector w_hat to w(0) to PLA
for t in range(T):
    run PLA for one update to obtain w(t+1)
    evaluate Ein(w(t+1)) # about all examples
    if w(t+1) is better than w_hat in terms of E_in
        then set w_hat to w(t+1)
return w_hat

즉 계속 PLA를 돌리면서 최적의 weight를 찾아가는 것이다. 당연히 PLA보다 엄청 느리고 global minimum을 보장하지 못한다. PLA algorithm에 대해서는 다음 글을 참고하면 된다.

About PLA algorithm: https://talkingaboutme.tistory.com/entry/Machine-Learning-Perceptron-Learning-Algorithm-PLA

2.2 Linear Regression

다음과 같은 Data set을 보자.

<그림1: Data의 분포>

이런 Data set을 보면 어느 정도 Data set이 빨간 선에 근사하여 나타나는 경향을 보인다는 것을 납득할 수 있을 것이다. 이런 사실에 기반하여 x와 y사이의 관계를 선형적으로 근사하는 통계적 방법을 선형 회귀(linear regression)라 한다. 이렇게 선형회귀 모델을 정의해놓았을 때 좋은 점은 새로 들어온 input x1에 대해 y1값을 어느정도 추론해볼수 있다는 것이다. '근사'라는 표현을 사용한 것은 어느 정도의 noise (in sample error)를 허용하기 때문이다.

또한, 찾는 것은 y=f(x)가 아니라 y~P(y|x) 의 확률 분포가 된다. 즉 <그림1>에서 우리가 그은 직선은 다음 <그림2>에서와 같이 분포의 평균을 지나는 직선이 될 것이다.

<그림2>

또한 이런 근사는 1차원의 input에 대해서만 가능한 것이 아니고 n차원의 mulit-dimension input에 대해서도 적용가능한 방법이다. 만약 d가 2보다 크거나 같다면 linear regression의 결과는 다음 <그림3>과 같은 hyperplane이 될 것이다.

<그림3: DATA의 차원이 2 이상일 때 Regression의 결과>

이제 우리가 관심있는 것은 알고리즘이니까 이에 대해 다루어보자.

2.2.1 Linear Regression algorithm

실제로는 근사된 hyperplane과 out of sample간의 out of sample Error를 줄이는 알고리즘이 가장 좋은 알고리즘일 것이나 이는 training data에서 측정할 수 없는 값이므로 이 대신 in sample error를 줄이는 것을 목표로 한다. error를 least-square로 정의할 때 in-sample error는 다음과 같이 정의할 수 있다. N은 sample의 수다.
$$
E_{in}(h)=\frac{1}{N}\sum _{n=1}^{N}{(h(x_n)-y_n)^2 }
$$
remind: 이 때 h(x)는 weight vector w에 대해 다음과 같이 정의될 것이다. (x_0=1)
$$
h(x)=\sum _{i=0 }^{ d }{w_ix_i }
$$
이 때 linear regression의 목표는 E_in(h)를 최소로 만드는 w를 찾는 것이다.

이 question의 solution에는 여러가지 방법이 있는데 우선 minimize할 식이 quadratic form이므로 in-sample error는 다음<그림4>와 같은 꼴일 것이다. (연속, 미분가능의 가정 필요 + least square일때만)

<그림4: in-sample error 곡면>

따라서 최적의 위치는 자명하므로 다음과 같은 수학적 풀이 한 번이면 된다.
$$
\nabla E_{in}(w)= \vec{0}
$$
또한, generalize된 해석적 풀이로써 Gradient Descent(경사 하강법)을 제안하기도 한다.

Gradient descent의 구체적인 방법은 다음 Chapter인 logistic regression에서 중요하게 다룬 내용이므로 다음 글을 참고하길 바란다.

Gradient Descent:

이제 첫번째로 제안한 in-sample error vector=0 의 방정식을 풀어 답을 얻는 방법을 써보면 다음과 같다. 미분은 생략한다.
$$
\nabla E_{in}(w)=\frac{2}{N}(X^TXw-X^Ty)=0
$$
따라서 다음과 같은 normal equation을 푸는 것이 목표다.
$$
X^TXw=Xy
$$
이는 (X^TX)의 행렬이 invertible한지에 따라 w를 구할 수 있는지 없는지가 결정되는 방정식이지만 실제에서는 pseudo-inverse를 사용하므로 invertibility에 대해 크게 신경쓰지 않아도 된다. 따라서 w를 다음과 같이 정의하면 linear regression 끝.
$$
w_{lin}=(X^TX)^{-1}X^Ty
$$
구하는 직선인 g(x)는 다음과 같이 정의
$$
g(x)=w_{lin}^Tx
$$
앞으로 나올 수식 중 이렇게 analytical하게 풀리는 case는 매우 희귀하다. 앞으로는 거의 iterative method를 사용하게 된다.

또, 이렇게 주어진 Data에 대한 error인 in-sample error를 줄이는 것이 아직 보지 못한 Data에 대한 error인 out of sample error를 줄이는 것을 gaurantee하는데 이는 증명하기 귀찮으니까 넘어가자.

Reference: Abu-Mostafa, Yaser S., Malik Magdon-Ismail, and Hsuan-Tien Lin. Learning from data. Vol. 4. New York, NY, USA:: AMLBook, 2012.