/////
📔

Chapter 4. Linear Models for Classification

Created
2020/12/21 12:43
이전 장에서는 단순한 해석적인 특성을 가진 특정 regression 모델을 살펴보았다. 바로 linear regression model인데, 이번 장에서는 이러한 linear model의 classification에 대한 적용을 다룬다. 즉, decision boundary가 input vector xx에 대한 linear function인 linear classification model을 다룬다.
특히 target을 나타내기 위해서는 흔히 사용하듯 2 class의 경우에는 binary representation을, K>2K > 2 class의 경우에는 one hot vector representation을 사용한다.
Chapter 1에서 classification problem에 대한 세 가지 접근 방식을 다루었는데, 되돌아보자면 바로 1) input을 바로 target에 할당하는 discriminant function을 모델링하는 방식, 2) input에 대한 각각의 class의 conditional probability distribution p(Ck∣x)p(C_k | x)를 모델링하는 방식, 3) class-conditional density p(x∣Ck)p(x | C_k)와 prior p(Ck)p(C_k)를 모델링한 후 Bayes' theorem을 이용하여 prior p(Ck∣x)p(C_k | x)를 구하는 방식이다. 이 세 가지 방법에 대해 이번 장에서 하나씩 다룬다.
또한 regression model과는 다르게 classification model에서는 prediction의 값이 구간 (0,1)(0, 1)에 bound되길 바라기 때문에, 다음과 같이 activation function을 이용한다.
y(x)=f(wTx+w0)y(x) = f(w^T x + w_0)
이러한 형태에서도 decision boundary는 y(x)=const→wTx+w0=consty(x) = \text{const} \rightarrow w^T x + w_0 = \text{const}로 정해지기 때문에 xx에 대한 linear function임은 변하지 않는다. 이러한 연유로 위와 같은 모델을 generalized linear model이라 부른다. 하지만 더 이상 parameter에 대해 linearity를 가지지 않으므로, 이전과 같은 해석적인 단순성을 사라진다. 그럼에도 불구하고 꽤나(?) 단순한 형태이기 때문에 사용할 만하다고 한다.

4.1. Discriminant Functions

Discriminant function은 누누이 말했듯 input vector xx를 특정 class로 바로 할당해주는 함수이다. 이번 장에서는 특히 decision surface가 hyperplane인 linear discriminant에 초점을 맞춘다. 먼저 2-class case를 다루고, 이를 K>2K > 2 class case로 확장한다.

4.1.1. Two classes

가장 간단한 형태의 linear discriminant는 바로 다음과 같다.
y(x)=wTx+w0y(x) = w^T x + w_0
여기서 y(x)>0y(x) > 0이면 xx를 C1C_1에, 그렇지 않으면 xx를 C2C_2에 할당한다. 이로써 decision boundary는 D−1D-1-dimensional hyperplane인 y(x)=0y(x) = 0으로 주어진다. 이 때 decision surface 위에 있는 두 벡터 xA,xBx_A, x_B를 생각해보면, y(xA)=y(xB)=0y(x_A) = y(x_B) = 0이고 wT(xA−xB)=0w^T (x_A - x_B) = 0이므로 ww는 decision surface 위에 있는 임의의 vector에 대해 orthogonal이고, 따라서 ww는 decision surface의 방향을 결정한다.
또한 xx가 decision surface 위의 벡터라면 y(x)=0y(x) = 0이고, 원점에서 decision surface까지의 normal distance는 다음과 같이 주어진다.
wTx∣∣w∣∣=−w0∣∣w∣∣\frac{w^T x}{||w||} = -\frac{w_0}{||w||}
따라서 w0w_0는 decision surface의 위치(원점으로부터의 거리)를 결정함을 알 수 있다.
또 y(x)y(x)의 값이 decision surface로부터의 perpendicular distance rr에 대한 signed measure를 제공한다는 사실을 다음과 같이 알아낼 수 있다. 임의의 벡터 xx와 xx의 decision surface에 대한 orthogonal projection x⊥x_{\perp}가 주어졌다고 하자. 먼저 xx는 다음과 같이 표현 가능하다.
x=x⊥+rw∣∣w∣∣x = x_{\perp} + r \frac{w}{||w||}
위 식에 wTw^T를 곱하고 w0w_0를 더하면, 다음과 같은 식을 얻는다.
wTx+w0=(wTx⊥+w0)+rwTw∣∣w∣∣=(0)+r∣∣w∣∣r=y(x)∣∣w∣∣w^T x + w_0 = (w^T x_{\perp} + w_0) + r \frac{w^T w}{||w||} \\ = (0) + r||w|| \\ r = \frac{y(x)}{||w||}
이제부터는 편의를 위해 이전 장에서와 같이 bias parameter w0w_0를 ww와 통합하여 표기한다.

4.1.2. Multiple classes

이제 K>2K > 2 class case에 대한 확장을 살펴본다. 먼저 이를 여러 개의 2-class discriminant function을 통해 표현하고자 할 수 있지만, 이 경우 교재에서 보여주듯 아무런 class에도 할당되지 않거나, 두 개 이상의 class에 할당되는 ambiguous region이 발생하게 된다. 따라서 다음과 같이 KK linear function을 포함한 KK-class discriminant function form을 이용하며,
yk(x)=wkTx+wk0y_k(x) = w_k^T x + w_{k0}
yk(x)y_k(x)가 가장 큰 kk에 대해 $x$를 CkC_k에 할당하게 된다. 이로써 Ck,CjC_k, C_j 사이의 decision boundary는 yk(x)=yj(x)y_k(x) = y_j(x)로 주어지게 되며, 이는 다음과 같이 정의된 (D−1)(D-1)-dimensional hyperplane이다. 해석 및 기하학적 특성은 2-class case와 동일하다.
(wk−wj)Tx+(wk0−wj0)=0(w_k - w_j)^T x + (w_{k0} - w_{j0}) = 0
또한 아주 간단하게 이러한 decision region은 singly connected이며(즉 어떠한 region 내의 임의의 두 벡터가 형성하는 선분 위의 임의의 벡터는 역시 그 region에 속한다), convex이다.
이제 linear discriminant function의 parameter를 결정하는 세 가지 방식 - least squares, Fisher's linear discriminant, perceptron algorithm - 에 대해 알아본다.

4.1.3. Linear squares for classification

Chapter 3에서는 sum-of-squares error function의 최소화가 closed-form solution을 제공해주었는데, 이를 classification에 그대로 적용해보면 어떨까 싶다. Linear discriminant가 conditional expectation E[t∣x]E[t | x]를 근사한다는 점에서 왠지 그럴싸하지만, 안타깝게도 linear model은 (0,1)(0, 1) 구간 바깥의 값을 가질 수 있기 때문에 이러한 확률이 제대로 근사될 수 없다는 치명적인 한계를 가진다.
먼저 위에서 언급한 KK-class discriminant function을 통합하여 다음과 같이 쓴다.
y(x)=WTxy(x) = W^T x
이제 training data {X,T}\{ X, T \}를 생각해보면, sum-of-squares error function은 다음과 같이 쓸 수 있다.
ED(W)=12Tr{(XW−T)T(XW−T)}E_D(W) = \frac{1}{2} Tr \{ (XW - T)^T (XW - T) \}
WW에 대한 미분값을 0으로 두면, 다음과 같이 익숙한 형태를 얻는다.
W=(XTX)−1XTT=X†TW = (X^T X)^{-1} X^T T = X^{\dagger} T
그러면 다음과 같은 discriminant function을 얻는다.
y(x)=WTx=TT(X†)Txy(x) = W^T x = T^T (X^{\dagger})^T x
이 때 least-squares solution은 training set의 모든 target vector가 다음과 같은 linear constraint을 만족하면,
aTtn+b=0a^T t_n + b = 0
model prediction 역시 동일한 linear constraint을 만족한다는 성질을 가지는데,
aTy(x)+b=0a^T y(x) + b = 0
이로써 y(x)y(x)의 sum은 1이 된다. 하지만 그렇다고 각각의 값이 (0,1)(0, 1)로 bound된다는 뜻은 아니며, 실제로 그렇지도 않다. 그리고 누누이 말했듯 이러한 least-squares solution은 outlier에 굉장히 취약한 모습을 보여준다. 더군다나 least-squares solution은 Gaussian conditional distribution에 대한 maximum likelihood solution과 동치인데, classification 상황에서의 target vector는 아무리 봐도 Gaussian과는 거리가 멀어보인다.

4.1.4. Fisher's linear discriminant

Linear classification model에 대한 또 하나의 접근 방식은 바로 dimensionality reduction이다. 예컨대 2-class classification에서 ww를 이용하여 다음과 같이 xx를 one dimension으로 축소할 수 있다.
y=wTxy = w^T x
통상적으로 이러한 projection은 아주 많은 정보의 손실을 야기하지만, ww 값을 잘 조정하여 xx의 separability를 최대한 보존하는 방식의 projection을 꾀할 수 있다. 먼저 C1C_1에 N1N_1개의 데이터를, C2C_2에 N2N_2개의 데이터를 가진 2-class classification 문제를 생각해보자. 여기서 생각해볼 수 있는 가장 간단한 형태의 separation은 두 class의 projected mean의 차이를 극대화하는 것이다.
하지만 이러한 방법은 원래의 space에서는 잘 나뉘어지던 데이터들이 projected space에서는 대부분이 겹쳐버릴 수 있다는 단점을 가진다. 이는 class distribution의 non-diagonal covariance에 기인한다.
여기서 Fisher는 projected mean의 차이를 극대화하는 동시에, intra-class variance를 최소화하여 class-overlap을 최소화하는 방식을 제안한다.
먼저 projected space에서의 within-class variance는 다음과 같고,
sk2=∑n∈Ck(yn−mk)2s_k^2 = \sum_{n \in C_k}{(y_n - m_k)^2}
2-class classification에서의 total within-class variance는 s12+s22s_1^2 + s_2^2와 같이 나타낼 수 있다. 이제 Fisher criterion은 다음과 같다.
J(w)=(m2−m1)2s12+s22J(w) = \frac{(m_2 - m_1)^2}{s_1^2 + s_2^2}
이러한 Fisher criterion을 다시 쓰고 ww에 대해 미분하면, 다음을 알아낼 수 있다.
w∝Sw−1(m2−m1)Sw=∑n∈C1(xn−m1)(xn−m1)T+∑n∈C2(xn−m2)(xn−m2)Tw \propto S_w^{-1} (m_2 - m_1) \\ S_w = \sum_{n \in C_1}{ (x_n - m_1)(x_n - m_1)^T } + \sum_{n \in C_2}{ (x_n - m_2)(x_n - m_2)^T }
위에서 언급했듯, 만약 within-class covariance matrix SwS_w가 diagonal이라면 이는 단순히 projected mean의 linear combination에 불과하다.
이러한 결과가 바로 Fisher's linear discriminant라 불린다. 사실 엄밀하게는 discriminant가 아니라 one dimensional projection에 대한 direction의 결정이라고 보는 게 맞지만, 이러한 projected data를 discriminant를 형성하는 데 효과적으로 활용할 수 있기 때문이다. 예컨대 projected data를 가지고 class-conditional density p(y∣Ck)p(y | C_k)를 Gaussian을 이용해 모델링하여 maximum likelihood를 통해 그 parameter를 알아낼 수 있겠다. 이러한 Gaussian assumption은 y=wTxy = w^T x가 일종의 random variable의 합의 형태이기 때문에 정당성을 얻는다.

4.1.5. Relation to least squares

위와 같은 Fisher discriminant는 특수한 형태의 least squares solution라고 한다. 자세한 내용은 생략한다.

4.1.6. Fisher's discriminant for multiple classes

위와 같은 Fisher discriminant를 K>2K > 2 class case로 확장한다. 자세한 내용은 생략한다.

4.1.7. The perceptron algorithm

간단히 말하자면 각각의 데이터에 대해 틀린 정도를 error function으로 정의한 후, 해당 정보를 이용해 SGD 알고리즘으로 모델을 학습시키는 알고리즘이다. 재미있는 특징은 데이터가 linearly separable하다면 모델은 반드시 수렴하지만 수렴까지 얼마나 오랜 기간이 걸릴 지는 알 수 없다는 점이다. 이 때문에 얼마의 시간이 걸리든 모델이 실제로 수렴하기 전까지는 해당 모델이 수렴할 지 그렇지 않을지 알아낼 수가 없다!

4.2. Probabilistic Generative Models

TBA...