2020-2학기 이화여대 김정태 교수님 강의 내용을 바탕으로 본 글을 작성하였습니다.
3장에서 regression model들 중에서 해석/계산적 단순한 성질을 가진 모델에 살펴보았는데, 4장에서는 classification 문제를 푸는 데 비슷한 방법(MLE, Bayesian)을 이용해 접근할 것이다.
Overview
- Linear classification (Discriminant functions)
- Probabilistic generative model
- Probabilistic discriminative model
- The Laplace Approximation
- Bayesian Logistic Regression
Linear classification
▶ Classification problem
- Take an input vector $\mathbf{x}$ and to assign it to one of $K$ discrete classes $C_k$ , where $k = 1, ..., K$.
- The input space is divided into decision regions whose boundaries are called decision boundaries
- Typical target vector for classification $\mathbf{t} = (0, 1, 0, 0, 0)^T$
- We can interpret the value of the target vector as the probability of that the class is $C_k$.
분류 문제의 목표는 $\mathbf{x}$ (입력 벡터)가 주어졌을 때 이를 $K$개의 discrete class $C_k$들 중 하나에 할당하는 것이다. 각각의 입력값들은 하나의 클래스에 할당됨. 따라서 입력 공간은 decision boundary(결정 경계) 또는 decision surface(결정 표면)이라고 불리는 경계를 바탕으로 여러 decision region(결정 구역)들로 나눠지게 된다.
이번 Ch4. 에서는 분류를 위한 선형 모델에 대해 살펴볼 것이다. ("선형" 모델의 의미는 결정 표면들이 입력 벡터 $\mathbf{x}$에 대한 선형 함수라는 것) 클래스들이 선형 결정 표면들을 바탕으로 정확하게 나뉠수 있는 데이터 집합은 linearly separable한 집합이라고 일컫는다.
일반적으로 $K \gt 2$개의 클래스가 있을 경우에는 원 핫 인코딩 (one hot encoding)을 적용하는 것이 편리함. 클래스 $C_j$에 속하는 경우에 대해 원 핫 인코딩을 적용하면 $t$는 $K$ 길이의 벡터가 되며, 이 벡터의 원소 $t_j$의 1값을, 나머지 원소들은 0을 가지게 된다.
마찬가지로 $t_k$의 값을 클래스가 $C_k$일 확률로 해석할 수 있음
▶ Classification methods (세 가지 방법)
- Discriminant function that directly assigns each vector $\mathbf{x}$ to a specific class.
판별 함수(각각의 벡터 $\mathbf{x}$를 특정 클래스에 집접 바로 배정하는 함수)를 만들어 활용하는 방식
- Probabilistic discriminative methods models $p(C_k |\mathbf{x})$ in an inference stage, and then uses this distribution to make optimal decision.
추론 단계에 조건부 확률 분포 $p(C_k|\mathbf{x})$를 모델하고 추후에 이 분포를 활용해 최적 결정을 내림
- Probabilistic generative methods first model the class-conditional densities $p(\mathbf{x}|C_k)$ together with class probability $p(C_k)$, and then compute posterior probabilities using Bayes theorem
$$
p\left(C_{k} \mid \mathbf{x}\right)=\frac{p\left(\mathbf{x} \mid C_{k}\right) p\left(C_{k}\right)}{p(\mathbf{x})} \tag{1}\label{1}
$$
조건부 확률 $p(C_k | \mathbf{x})$를 결정하는데 두 가지 방법이 있으나, 두 번째 방법인, 생성적인 방법으로, 클래스 조건 밀도 $p(\mathbf{x}|C_k)$와 클래스 사전 확률 $p(C_k)$를 모델한 후 필요한 사후 확률을 베이지안 정리를 이용하여 계산하는 방식
Ch4 에서는 분류 문제를 푸는 세 가지 방법의 예시에 대해 살펴볼 예정이지만, 이번 글에서는 "Discriminant function"를 다루고자 한다.
우선, Ch3에서 살펴본 선형 회귀 모델의 경우에 모델의 예측값 $y(\mathbf{x}, \mathbf{w})$는 매개변수 $\mathbf{w}$의 선형 함수로 주어진다. 하지만, Ch4의 분류 문제에서는 discrete value인 클래스 라벨 값을 출력해야 하기 때문에 0과 1사이의 범위에 속하는 사후 확률을 구하기 위해 $f(\cdot)$이라는 비선형 함수를 고려한다.
$$y(\mathbf{x}) = f(\mathbf{w}^T \mathbf{x} + \omega_0) \tag{2}\label{2}$$
일반적으로 머신러닝 교재에서 $f(\cdot)$를 활성화 함수(activation function)이라고 하며, 통계학 문헌에서는 이 함수의 역함수를 연결 함수(link function)라고 한다.
Ch3의 회귀 모델에서와 같이 기저 함수 $\phi(\mathbf{x})$들을 이용하여 입력 변수들에 대해 고정된 비선형 변환을 먼저 적용할 경우에도 이 장에서 사용된 알고리즘들을 동일하게 적용할 수 있다. 일단은 원 입력 공간 $\mathbf{x}$상에서 직접적으로 분류하는 case에 대해 살펴보는 것으로 시작하고자 한다.
▶ Recap
decision problem을 해결하는데 세 가지 접근 방법 Ch1.5.4 (추론과 결정)이 있다. (쉬운 ~ 어려운 순서로 설명)
- 각각의 입력값 $\mathbf{x}$를 class에 사상하는 판별 함수 $f(\mathbf{x})$를 찾는 방법. (확률론 사용하지 않음)
- discriminative model (판별 모델) : 우선 사후 확률 $p(C_k|\mathbf{x})$를 계산하는 추론 문제를 풀어낸 후에 결정 이론을 적용하여 각각의 입력 변수 $\mathbf{x}$에 대한 클래스를 구함
- generative model (생성 모델) : 우선 각각의 클래스 $C_k$에 대해서 조건부 확률 밀도 $p(\mathbf{x}|C_k)$를 알아내는 추론 문제를 풀어낸다. 클래스별 사전 확률 $p(C_k)$도 따로 구한다. 그 다음에 아래 식과 같이 베이지안 정리를 이용해서 각 클래스별 사후 확률 $p(C_k|\mathbf{x})$를 구한다.
$$p(C_k|\mathbf{x}) = \frac{p(\mathbf{x}|C_k) p(C_k)}{p(\mathbf{x})}$$
where
$$p(\mathbf{x}) = \sum_k p(\mathbf{x}|C_k)p(C_k)$$
사후 확률을 구한 후에는 결정 이론을 적용하여 각각의 새 입력 변수 $\mathbf{x}$에 대한 클래스를 구한다. 직간접적으로는 입력값과 출력값의 분포를 모델링하는 방식이라고해서 생성 모델이라고 한다. (이유 : 분포로부터 표본을 추출함으로써 입력 공간에 합성 데이터 포인트들을 생성해 넣는 것이 가능하기 때문)
4.1 Discriminant function (판별 함수)
편의를 위해 먼저 Class가 두 개인 경우에 대해 살펴본다.
▶ Two classes
선형 판별 함수를 가장 단순하게 표현하면 아래 식 (3)과 같은 입력 벡터들의 선형 함수가 된다.
$$y(\mathbf{x}) = \mathbf{w}^T \mathbf{x} + \omega_0 \tag{3}\label{3}$$
- $\mathbf{w}$ : weight vector
- $\omega$ : bias (통계에서 사용하는 bias와 다름, bias의 음의 값은 때때로 threshold라고 부름)
입력 벡터 $\mathbf{x}$는 $y(\mathbf{x}) \geq 0$인 경우에는 $C_1$에, 그렇지 않은 경우에는 $C_2$로 할당한다. 따라서 이 해당하는 결졍 경계는 $y(\mathbf{x})=0$에 해당하며, $D$ 차원 입력 공간상의 $(D-1)$차원 Hyperplane(초평면)에 해당한다.
결정 표면상에 존재하는 두 개의 점 $\mathbf{x}_A$와 $\mathbf{x}_B$를 고려해보자.
만약 $\mathbf{x}$가 결정 표면상(hyperplane)의 점이라면 $y(\mathbf{x}) = 0$이므로, 원점($\mathbf{0}$)으로부터 결정 표면까지의 수직 최단 거리는 다음과 같다.
$$
\frac{\mathbf{w}^{\mathrm{T}} \mathbf{x}}{\|\mathbf{w}\|}=-\frac{w_{0}}{\|\mathbf{w}\|} \tag{4}\label{4}
$$
따라서, $\omega_0$이 결정 표면의 위치를 결정한다는 것을 알 수 있다. (이 성질들에 대해서 $D=2$인 경우를 바탕으로 [그림 1]을 참고)
또한 $y(\mathbf{x})$의 절댓값은 point $\mathbf{x}$와 결정 표면 사이의 수직 거리 $r$에 해당함을 알 수 있음 이를 확인해보기 위해 임의의 point $\mathbf{x}$와 $\mathbf{x}$의 결정 표면에 대한 수직 투영 $\mathbf{x}_{\perp}$를 고려해보자.
$$
\mathbf{x}=\mathbf{x}_{\perp}+r \frac{\mathbf{w}}{\|\mathbf{w}\|} \tag{5}\label{5}
$$
양변에 $\mathbf{w}^T$를 곱하고, $\omega$를 더한 후, $y(\mathbf{x})=\mathbf{w}^T \mathbf{x} + \omega_0$와 $y(\mathbf{x}_{\perp})=\mathbf{w}^T \mathbf{x}_{\perp} + \omega_0=0$을 이용하면 식 (6)을 구할 수 있다. ([그림 1]에 도출 과정에 대한 설명 추가하였으니 참고)
$$
r=\frac{y(\mathbf{x})}{\|\mathbf{w}\|} \tag{6}\label{6}
$$
Ch3에서 살펴본 선형 회귀 모델의 경우와 같이 표기를 일반화하기 위해 추가적인 가변수 $x_0 = 1$을 사용하고, $\widetilde{\mathbf{w}}=\left(w_{0}, \mathbf{w}\right)$와 $\widetilde{\mathbf{x}}=\left(w_{0}, \mathbf{w}\right)$라 정의해 보자.
$$
y(\mathbf{x})=\widetilde{\mathbf{w}}^{\mathrm{T}} \widetilde{\mathbf{x}} \tag{7}\label{7}
$$
이 경우 결정 표면은 $D+1$의 확장된 입력 공간상에서 원점을 지나는 $D$차원의 초평면이 된다.
▶ Multi classes
이제 $K \gt 2$개의 Multi class의 경우를 살펴보자. 여러개의 2-class 판별 함수를 합쳐서 $K$개의 class를 판별할 수 있지만, 아래처럼 어려움을 내포하고 있다. (불확실한 영역 존재..critical!)
$K$개의 선형 함수들로 이루어진 하나의 $K$-class 판별 함수를 고려함으로써 위의 문제들을 피할 수 있다.
$$y_k(\mathbf{x})=\mathbf{x}^T_k \mathbf{x} + \omega_{k0} \tag{8}\label{8}$$
그후 $j \neq k$인 모든 $j$에 대해 $y_k(\mathbf{x}) \gt y_j(\mathbf{x})$면 모든 point $\mathbf{x}$를 class $C_k$에 할당하면 된다. 이때 class $C_k$와 class $C_j$사이의 결정 경계는 $y_k(\mathbf{x})=y_j(\mathbf{x})$로 주어지며, 이에 해당하는 $(D-1)$차원 hyperplane은 다음과 같다.
$$(\mathbf{x}_k-\mathbf{x}_j)^T\mathbf{x}+(\omega_{k0}-\omega_{j0})=0 \tag{9}\label{9}$$
이러한 판별 함수의 결정 경계는 언제나 단일하게 연결되어 있으며, convex(볼록)한 성질을 가지고 있다. 이를 확인하기 위해 [그림 4]처럼 결정 경계 $R_k$상의 두 점인 $\mathbf{x}_A$와 $\mathbf{x}_B$를 고려해 보자.
이제 본격적으로 선형 판별 함수의 parameter(매개변수)를 학습하는 세 가지 방법(이하)에 대해 살펴보자.
- least squares
- Fisher’s linear discriminant
- the perceptron algorithm
▶ Least squares for classification
앞선 Ch3의 regression문제에서의 parameter에 대해 선형 함수인 모델을 살펴봤었다. 이는 제곱합 오류(least squares error) 함수를 최소화하는 문제는 closed 형태의 단순한 매개변수 해를 가지고 있었다. Ch4의 classifier 문제에도 최소제곱법을 적용할 수 있다.
$K$개의 class가 있는 일반적인 문제를 풀기 위해 $t$(target vector)를 "one-hot-encoding"을 사용한다고 가정하자.
(최소 제곱법을 사용하는 것이 타당한 이유 : $\mathbf{x}$(input vector)가 주어졌을 때 $\mathbf{t}$(target vector)의 조건부 기댓값 $E(\mathbf{t}|\mathbf{x})$의 근사값(approximates)을 구하는 방법이라는 점. [교재 참고하기])
이진 부호화(binary coding scheme)의 경우, $\mathbf{x}$(input vector)은 posterior probability(사후 확률)의 vector로 주어지게 되는데, 하지만 불행하게도 이러한 확률들은 상대적으로 성능이 좋지 못하게 된다. 이러한 근사값들은 선형 모델의 제한적인 유연성으로 $(0,1)$ 범위 밖의 값을 가질 수도 있음! 시각적으로 [그림 5]에 설명 예정
우선, 각각의 class $C_k$들을 각각의 선형 모델로 표현할 수 있음
$$y_k(\mathbf{x}) = \mathbf{w}^T_k \mathbf{x} + \omega_{k0} \tag{10}\label{10}$$
where $k=1, ..., K$로, $k$를 vector 표기를 이용해 다음과 같이 표현할 수 있음
$$\mathbf{y}(\mathbf{x}) = \widetilde{\mathbf{W}}^T \widetilde{\mathbf{x}} \tag{11}\label{11}$$
Ch3에서 regression 문제를 풀 때 했었던 것처럼 the sum-of-square error를 최소화해서 매개변수 행렬 $\widetilde{\mathbf{W}}$의 값을 구하기 위해 the sum-of-square error를 식 (12) 같이 정의할 수 있다.
$$E_D({\widetilde{\mathbf{W}}}) = \frac{1}{2}\mathbf{Tr} \{(\widetilde{\mathbf{X}}\widetilde{\mathbf{W}} - \mathbf{T} )^T (\widetilde{\mathbf{X}}\widetilde{\mathbf{W}} - \mathbf{T}) \} \tag{12}\label{12}$$
$\widetilde{\mathbf{W}}$에 대한 미분값을 0으로 놓고 다시 정리하면 $\widetilde{\mathbf{W}}$에 대한 해를 식 (13)과 같이 구할 수 있다.
$$\widetilde{\mathbf{W}} = (\widetilde{\mathbf{X}}^T \widetilde{\mathbf{X}}^{-1})^T \widetilde{\mathbf{X}}^T\widetilde{\mathbf{T}} = \widetilde{\mathbf{X}}^{+}\mathbf{T} \tag{13}\label{13}$$
$\widetilde{\mathbf{X}}^{+}$는 Ch3.1.1에서 다룬 유사행렬(pseudo-inverse of the matrix $\widetilde{\mathbf{ X}}$) 이며, discriminant function 을 식 (14)와 같이 구할 수 있다.
$$\mathbf{y}(\mathbf{x})=\widetilde{\mathbf{W}}^T \widetilde{\mathbf{x}} = \mathbf{T}^T (\widetilde{\mathbf{X}}^{+})^T \widetilde{\mathbf{x}}. \tag{14}\label{14}$$
multi target variable인 경우의 최소 제곱법의 한 가지 흥미로운 성질은 만약 모든 훈련 집합의 target vector들이 전부 식 (15)의 선형 제약 조건을 어떠한 $\mathbf{a}$와 $b$값에 대해 만족한다면, 어떤 $\mathbf{x}$ 값에 대한 모델 예측값이던지 같은 제약 조건 식 (16)을 만족하게 된다는 것이다.
$$\mathbf{a}^T \mathbf{t}_n + b = 0 \tag{15}\label{15}$$
$$\mathbf{a}^T \mathbf{y}(\mathbf{x}) + b = 0 \tag{16}\label{16}$$
따라서 one-hot-encoding을 $K$개의 class의 경우에 사용하면 모델을 통해 만들어진 예측값들은 어떤 $\mathbf{x}$의 경우에든 $\mathbf{y}(\mathbf{x})$의 원소들을 모두 합하면 1이 된다는 성질을 가진다. 하지만, 이 합산 제약 조건만으로는 모델의 출력값을 확률로써 해석하기에 충분하지 않다. 왜냐하면 $(0, 1)$ 구간 사이에 값이 존재해야 한다는 제약 조건이 없기 때문이다. (즉, -, + 값을 가짐)
최소 제곱법 기반의 방법을 사용하면 discriminant function에 대한 해를 정확히 닫힌 형태로 구할 수 있다. 하지만, 이를 직접적으로 모델을 사용하여 결정을 내리고 확률적인 해석을 내리는 데 있어서 두 가지 심각한 문제점이 존재한다.
- We have already seen that least-squares solutions lack robustness to outliers. [그림 5]
- the least-squares solution gives poor results than technique of logistic regression. [그림 6]
최소 제곱법은 원래 가우시안 조건부 분포 가정하에서의 최대 가능도 방법과 연관되어 있는 방식이다. 그렇기 때문에 명확히 가우시이 아닌 분포를 가진 binary target vectors에 대해서 최소 제곱법이 제대로 작동하지 않는 것은 사실 그리 놀라울 일이 아니다. 더 적합한 확률적 모델을 사용하려면 최소 제곱법보다 더 나은 성질은 가지는 분류 테크닉을 만들어 낼 수 있지만 일단 지금은 선형 분류 모델의 매개변수를 찾아내는 비확률적 방식에 대해 좀 더 살펴보도록 하자.
▶ Fisher’s linear discriminant
선형 분류 모델을 dimensionality reduction(차원 감소)에서도 볼 수 있다.
우선, two-category case를 고려하여, 식 (17)을 통해서 $D$ 차원의 입력 벡터 $\mathbf{x}$를 1차원에 투영한다고 해보자.
$$y = \mathbf{w}^T \mathbf{x} \tag{17}\label{17}$$
- If we place a threshold on $y$ and $y \geq -\omega_0$ as class $C_1$.
- otherwise class $C_2$.
일반적으로 일차원에 투영할 경우 상당한 양의 정보를 잃게 되며, 원래의 $D$차원에서는 잘 분리되었던 클래스들이 일차원에서는 심하게 겹칠 수 있다. 하지만, $\mathbf{w}$ (가중치 벡터)의 element들을 잘 조절하면 class 간의 분리를 최대화하는 projection(투영)을 선택할 수 있다. 우선, class $C_1$에 속하는 $N_1$개의 point 들과 class $C_2$에 속하는 $N_2$개의 point들을 고려해보자. 그러면 각 class들의 평균 벡터는 다음과 같다.
$$m_1 = \frac{1}{N_1} \sum_{n \in C_1} \mathbf{x}_n, \qquad m_2 = \frac{1}{N_2} \sum_{n \in C_2} \mathbf{x}_n \tag{18}\label{18}$$
$\mathbf{w}$에 투영되었을 경우에 class 간의 분리 정도를 측정할 수 있는 방법은 투영된 class의 평균들이 얼마나 분리되어 있는가를 살펴보는 것이다. 이에 따르면 아래 식 (19)의 값을 극대화하도록 $\mathbf{w}$를 선택하는 것이다.
$$m_2 - m_1 = \mathbf{w}^T (\mathbf{m}_2 - \mathbf{m}_1) \tag{19}\label{19} $$
아래 식 (20)은 class $C_k$에서 ㅜ영된 데이터들의 평균에 해당된다.
$$m_k = \mathbf{w}^T\mathbf{m}_k \tag{20}\label{20} $$
하지만 $\mathbf{w}$의 크기를 키움으로써 얼마든지 임의의 식의 값을 키울 수 있다. 이 문제를 해결하기 위해 $\mathbf{w}$가 단위 길이를 가지도록 제한해야 한다. 즉, $\sum_i \omega_i^2=1$이 되도록 제한해야 한다. 라그랑주 승수법을 이용하여 제약 조건하에서의 극대화를 하면 $\mathbf{w} \proper (\mathbf{m}_2 - \mathbf{m}_1)$라는 것을 알 수 있다. 이 방식에는 여전히 [그림 7]에서 살펴볼 수 있는 문제점이 있다.
원인 : This difficulty arises from the strongly nondiagonal covariances of the class distributions.
Fisher의 해결 방안 : 투영된 hyperplane에서 class 마다의 평균 사이의 분리 정도를 크게하는 동시에 각 class 내의 분산을 작게 하는 함수를 최대함으로써 class 간의 중복을 최소화하는 것
- $y=\mathbf{w}^T \mathbf{x}$ (일차원 공간 $y$상의 라벨링된 집합으로 변환)
class $C_k$상의 class 내 분산은 식 (21)과 같다.
$$s_k^2 = \sum_{n \in C_k} (y_n - m_k)^2 \tag{21}\label{21}$$
전체 데이터 집합의 class 내 분산은 단순히 $s_1^2 + s_2^2$으로 정의할 수 있으며, fisher criterion(피셔의 기준)은 클래스 간 분산(평균은 아님)과 클래스 내 분산의 비율로 정의된다.
$$ J(\mathbf{w}) = \frac{(m_2-m_1)^2}{s_1^2 + s_2^2} \tag{22}\label{22} $$
식 (17), 식(20), 식(21)을 이용해 fisher criterion을 아래와 같이 $\mathbf{w}$에 종속적인 형태로 변환할 수 있음 (연습문제 4.5)
$$ J(\mathbf{w}) = \frac{\mathbf{w}^T \mathbf{s}_{\mathbf{B}} \mathbf{w}}{\mathbf{w}^T \mathbf{s}_{\mathbf{w}} \mathbf{w}} \tag{23}\label{23} $$
- $\mathbf{S}_{\mathbf{B}}$는 between class(클래스 간) 공분산 행렬
$$\mathbf{S}_{\mathbf{B}} = (m_2 - m_1)(m_2-m_1)^T \tag{24}\label{24}$$
- $\mathbf{S}_{\mathbf{W}}$는 within class(클래스 내) 공분산 행렬
$$\mathbf{S}_{\mathbf{W}} = \sum_{n \in C_1}(\mathbf{x}_n - m_1)(\mathbf{x}_n - m_1)^T + \sum_{n \in C_2}(\mathbf{x}_n - m_2)(\mathbf{x}_n - m_2)^T\tag{25}\label{25}$$
식 (23)을 $\mathbf{w}$에 대해 미분을 하면 $J(\mathbf{w})$가 극대화됨을 알 수 있음 (생략)
$$(\mathbf{w}^T \mathbf{S}_{\mathbf{B}} \mathbf{w})\mathbf{S}_{\mathbf{W}}\mathbf{w} = (\mathbf{w}^T \mathbf{S}_{\mathbf{W}} \mathbf{w})\mathbf{S}_{\mathbf{B}}\mathbf{w} \tag{26}\label{26}$$
▶ Perceptron algorithms
Reference
- Pattern Recognition and Machine Learning
- PRML Example Code (git) : github.com/ctgk/PRML
댓글