선형분류 | Kangwook Lee’s Tech Blog

1. 개요

- 입력벡터(\(\mathbf{x}\))를 수개의 클래스 중 하나의 클래스로 할당하는 문제(예를 들면, 클래스가 \(C_1, \cdots, C_K\)로 주어질 때 \(\mathbf{x}\)를 이 중 하나로 분류하는 문제)를 분류문제라 한다. 분류문제를 풀기 위한 결정이론으로서 \(k=1, \cdots, K\)에 대해 모든 사후확률 \(p(C_k \mid \mathbf{x})\)을 구해볼 수 있다. (이를 구하기 위하여, 이 값을 직접 모델링해 구하는 discriminative model과 사전확률과 우도를 모델링한 후 베이즈 정리로 구하는 generative model이 있다.) 또는, 분류문제를 풀기 위해 주어진 벡터를 입력으로 하여 수개의 클래스 중 하나의 클래스를 함수값으로 내는 discriminant function을 구해볼 수 있다. (이 경우 확률을 계산하지는 않는다.)

2. linear한 discriminant function

1) 출력으로 0 또는 1만 내는 linear discriminant function

- \(y(\mathbf{w}) = \mathbf{w}^T \mathbf{x} + w_0\)라는 선형함수가 있을 때, 이 함수값이 0 이상이면 그 \(\mathbf{x}\)를 \(C_1\)으로 분류하고 0 미만이면 \(C_2\)로 분류하는 함수를 생각할 수 있다.

- 이 판별함수의 decision boundary는 \(y(\mathbf{x})=0\)이다.

- decision boundary를 가리키는 벡터 \(\mathbf{w}\)가 있고 임의의 벡터 \(\mathbf{x}\)가 있다 할 때, \(\mathbf{x}\)의 decision boundary에 대한 사영 벡터를 \(\mathbf{x}_{\perp} = \mathbf{x}- {y(\mathbf{x}) \over {|\mathbf{w}|}^2} \mathbf{w}\)라 하자.

\(\mathbf{x} - \mathbf{x}_{\perp} = {y(\mathbf{x}) \over {|\mathbf{w}|}^2} \mathbf{w}\) 이므로, \(y(\mathbf{x})\)가 0보다 크면 decision boundary를 기준으로 \(\mathbf{x}\)가 \(\mathbf{w}\)와 같은 방향, 0보다 작으면 \(\mathbf{w}\)와 반대 방향에 있다는 것을 알 수 있다.

2) 클래스가 \(K\)개인 판별함수

- 클래스가 2개가 아니라 \(K\)개라면, 선형함수 \(y_k(\mathbf{w}) = \mathbf{w}_{k}^T \mathbf{x} + w _ {k,0}\) (\(k = 1, \cdots, K\))에 대해 판별함수는 ‘\(y_k(\mathbf{w})\)가 \(y_j(\mathbf{w})\)(\(j=1, \cdots, K\)이면서 \(j \ne k\))보다 크면 \(\mathbf{x}\)를 \(C_k\)로 판별하는 함수’라고 쓸 수 있다.

이를 \(\tilde{\mathbf{x} } = \begin{bmatrix} x_0 & \mathbf{x}^T \end{bmatrix}^T \)와 \(k\)번째 열이 \(\begin{bmatrix} w_{k, 0} & \mathbf{w}_{k}^T \end{bmatrix}^T\)인 행렬 \(\tilde{W}\)를 사용하여, \(y(\mathbf{x}) = \tilde{W}^T \tilde{\mathbf{x} }\) 라고 쓸 수도 있다.

3) 선형분류의 제곱합 에러함수와 \(\tilde{W}\)의 최적값

- 학습데이터 \(\left\{\mathbf{x}_n, \mathbf{t}_n\right\}\) , \(n\)번째 행이 \(\mathbf{t} _ {n}^T\)인 행렬 \(T\), \(n\)번째 행이 \(\tilde{\mathbf{x} } _ {n}^T\)인 행렬 \(\tilde{X}\) (\(n=1, \cdots, N\)) 가 주어질 때 제곱합 에러함수는 \(E_D(\tilde{W}) = {1 \over 2} \mathrm{tr} \left\{(\tilde{X} \tilde{W} - T)^T(\tilde{X} \tilde{W} - T)\right\}\) 로 쓸 수 있다.

- 최대우도법으로 \(E_D(\tilde{W})\)를 최소로 하는 \(\tilde{W}\)를 구하면 \(\tilde{W} = (\tilde{X}^T\tilde{X})^{-1}\tilde{X}^T T\) 이다.

4) 퍼셉트론

- 퍼셉트론은 \(f(a) = \begin{cases} 1, & a \ge 0 \\ -1, & a < 0 \end{cases} \)와 같은 계단형 함수를 사용한다. 따라서 분류함수 \(y(\mathbf{x}) = f( \mathbf{w}^T \phi(\mathbf{x}))\) 또한 퍼셉트론이다.

- \(y(\mathbf{x})\)가 잘못 분류한 데이터 집합 \(\mathcal{M}\)에 대해 에러함수 \(E_P(\mathbf{w}) = - \displaystyle \sum_{n \in \mathcal{M} } \mathbf{w}^T \phi_n t_n \) 이다.

3. 분류문제 결정이론에서 generative model

- 두 클래스 \(C_1, C_2\)가 있고 \(p(C_1 \mid \mathbf{x}) = \sigma(a) = {1 \over {1 + exp(-a)} }\) 라고 가정해 보자. 이 경우 베이즈 정리에 의해 \(a = ln { {p(\mathbf{x} \mid C_1) p(C_1)} \over {p(\mathbf{x} \mid C_2) p(C_2)} }\) 이다.

만약 \(p(\mathbf{x} \mid C_1) = \mathcal{N}(\mathbf{x} \mid \mu_1, \Sigma), p(\mathbf{x} \mid C_2)= \mathcal{N}(\mathbf{x} \mid \mu_2, \Sigma)\) 라면, \(\mathbf{w} = \Sigma^{-1}(\mu_1 - \mu_2)\)를 얻는다.
최대우도법에 의해, \(p(C_1) = {n(C_1) \over {n(C_1) + n(C_2)} }, \mu_1 = {1 \over n(C_1)} \displaystyle \sum _ {n=1}^N t_n \mathbf{x} _ n, \mu_2 = {1 \over n(C_2)} \displaystyle \sum _ {n=1}^N (1-t_n) \mathbf{x} _ n\) 이다. (단, \(n(C_1), n(C_2) \)는 각각 \(C_1, C_2\)에 속하는 샘플 수.)
또, 최대우도법에 의해, \(\Sigma = p(C_1) S_1 + P(C_2) S_2\) 이다.
- \(S_1 = {1 \over n(C_1)} \displaystyle \sum_{n \in C_1}(\mathbf{x} _ n - \mu_1)(\mathbf{x} _ n - \mu_1)^T, S_2 = {1 \over n(C_2)} \displaystyle \sum_{n \in C_2}(\mathbf{x}_n - \mu_2)(\mathbf{x} _ n - \mu_2)^T\)
만약 \(\mathbf{x} = \begin{bmatrix} x_1 & \cdots & x_D \end{bmatrix}^T \)의 각 성분이 모두 0 또는 1인 경우라면 이때는 \(p(\mathbf{x} \mid C_k) = \displaystyle \prod _ {i=1}^D \mu _ {k, i}^{x_i} (1-\mu _ {k, i})^{1-x_i} \) 이 됨을 이용하여 위 식들을 크게 간소화할 수 있다.

- K개의 클래스 \(C_1, \cdots, C_K\)가 있고 \(p(C_k \mid \mathbf{x}) = \sigma(a_k) = {exp(a_k) \over {\sum_j exp(a_j) }\) 라고 가정해 보자. 이 경우 베이즈 정리에 의해 \(a_k = p(\mathbf{x} \mid C_k)p(C_k)\) (\(k=1, \cdots, K\)) 이다.

만약 \(p(\mathbf{x} \mid C_k) = \mathcal{N}(\mathbf{x} \mid \mu_k, \Sigma)\) 라면, \(\mathbf{w}_k = \Sigma^{-1}\mu_k\)를 얻는다.

4. 분류문제 결정이론에서 discriminative model

1) 클래스가 2개인 경우

- 두 클래스 \(C_1, C_2\)가 있고 데이터셋 \(\left\{ \phi_n, t_n \right\}\) (\(n=1, \cdots, N\), \(t_n\)은 0 또는 1) 일때 \(y_n = p(C_1 \mid \phi_n) = \sigma(\mathbf{w} \phi_n)\)라 하자. \(\phi_n\)이 \(M\)차원이라면 구해야 할 파라미터의 개수는 \(M\)개다.

- \(\mathbf{t} = \begin{bmatrix} t_1 & \cdots & t_N \end{bmatrix}^T \)라 할 때, 우도함수 \(p( \mathbf{t} \mid \mathbf{w}) = \displaystyle \prod _ {n=1}^N y_{n}^{t_n} (1-y_n)^{1-t_n}\) 이다. 여기서 \(E(\mathbf{w}) = -\mathrm{ln} p(\mathbf{t} \mid \mathbf{w}) = - \displaystyle \sum _ {n=1}^N \left\{ t_n \mathrm{ln} y_n + (1-t_n) \mathrm{ln} (1-y_n) \right\} \) 을 얻는다. (이를 cross entropy error function이라고도 한다.)

cross entropy는 \(H(p, q) = - \sum_x p(x) \mathrm{ln} q(x)\)의 형태를 갖는다. cross entropy가 최소화될 때 두 확률분포 \(p, q\)의 차이가 최소화되므로, 이를 통해 \(E(\mathbf{w})\)를 최소화될 때가 모델 예측값의 분포와 목표변수의 분포의 차이를 최소화됨을 알 수 있다.

- \(\nabla E(\mathbf{w}) = \displaystyle \sum _ {n=1}^N (y_n - t_n) \phi_n \)

2) 클래스가 \(K\)개인 경우

- \(p(C_k \mid \phi) = { {exp(\mathbf{w} _ {k}^T \phi} \over {\sum_j exp(\mathbf{w} _ {j}^T \phi} }\)

- \(y_{n, k} = y_k(\phi_n)\)이고 \(T\)는 \(n\)행 \(k\)열 성분이 \(t_{n, k}\)인 \(N \times K\) 크기의 행렬이고 \(\mathbf{t} _ n\)은 \(\phi_n\)이 속하는 클래스에 해당하는 성분만 1이고 나머지는 0인 벡터라 하면, 우도함수 \(p(T \mid \mathbf{w} _ 1, \cdots, \mathbf{w} _ K) = \displaystyle \prod _ {n=1}^N \prod _ {k=1}^K y_k(\phi_n)^{t _ {n, k} }\) 이다.

- 또 \(E(\mathbf{w} _ 1, \cdots, \mathbf{w} _ K) = - \displaystyle \sum _ {n=1}^N \sum _ {k=1}^K t _ {n, k} \mathrm{ln} y _ {n, k}\) 이다. 여기서 \(\nabla_{\mathbf{w} _ j} E(\mathbf{w} _ 1, \cdots, \mathbf{w} _ K) = \displaystyle \sum _ {n=1}^N (y _ {n, j} - t _ {n, j} ) \phi_n\) 을 얻는다.