4. Linear Models for Classification

이 장에서는 선형 모델을 통한 분류 문제를 다룬다. 분류 문제에서는 대개 클래스 라벨을 1-K 인코딩으로 표기한다. 분류 문제에는 3가지 다른 접근법이 있다. 첫 번째는 각 벡터를 특정 클래스로 할당하는 판별 함수를 만드는 것이다. 다른 방법은 추론 단계에서 조건부확률분포를 모델링하고 이를 연속적으로 적용하는 것이다. 이는 직접 모델링할 수도 있고 클래스 조건부 분포를 모델링한 뒤 베이즈 정리를 통해 구할 수도 있다. 적당한 연속함수 f에 대해 y(\mathbf{x}) = f(\mathbf{w}^{T} \mathbf{x} + w_{0})인 경우를 일반화된 선형 모델이라 하는데, 이는 f가 비선형일 수 있기 때문에 선형은 아니지만 그럼에도 불구하고 일반적인 비선형 모델에 비해서는 간단하다. 이 장에서 다루는 알고리즘은 입력에 고정된 기저 함수를 적용해 전처리해도 동일하게 적용할 수 있다.

4.1. Discriminant Functions

판별함수는 입력 벡터를 K개의 클래스 중 하나에 할당하는 함수이다.

4.1.1. Two classes

선형 판별 함수의 가장 간단한 형태는 y(\mathbf{x}) = \mathbf{w}^{T} \mathbf{x} + w_{0}으로서 판별 경계는 y(\mathbf{x}) \geq 0이다. 이 때 \mathbf{w}는 결정 평면의 방향을 결정하고 w_{0}은 결정 평면의 상대적 위치를 결정한다. 또한, y(\mathbf{x})의 값은 점과 결정 평면간의 수직 거리를 나타낸다. \tilde{\mathbf{x}} = (1, \mathbf{x}), \tilde{\mathbf{w}} = (w_{0}, \mathbf{w})로 놓으면 y(\mathbf{x}) = \tilde{\mathbf{w}}^{T} \tilde{\mathbf{x}}로 더 편리하게 나타낼 수 있다.

4.1.2. Multiple classes

K > 2 개의 클래스를 생각해 보자. 이는 K - 1개의 일대다 이진 분류기를 쓸 수도 있고 K(K-1)/2 개의 일대일 이진 분류기를 쓸 수도 있다. 또는 y_{k}(\mathbf{x}) = \mathbf{w}_{k}^{T} \mathbf{x} + w_{k0} 형태의 식 K개로 이루어진 단일 K-클래스 판별식을 통해 y_{k}(\mathbf{x})을 최대로 만드는 k를 고를 수도 있다. 이 경우 결정 영역이 항상 단순볼록연결영역이 된다. 클래스가 2개일 때는 위의 방법들이 차이가 없다. 이제 선형 판별 함수의 매개변수를 학습하는 법을 알아보자.

4.1.3. Least squares for classification

회귀 문제가 아닌 분류 문제에서는 단순히 제곱오차합을 최소화시키는 매개변수를 찾는 접근법이 불가능하다. 그 대신에 \mathbf{y}(\mathbf{x}) = \tilde{\mathbf{W}}^{T} \tilde{\mathbf{x}}에 대해 제곱오차합 E_{D}(\tilde{\mathbf{W}}) = \frac{1}{2} \mathrm{tr}[(\tilde{\mathbf{X}} \tilde{\mathbf{W}} - \mathbf{T})^{T} (\tilde{\mathbf{X}} \tilde{\mathbf{W}} - \mathbf{T})   ] 를 최소화시키는 해 \tilde{\mathbf{W}} = (\tilde{\mathbf{X}}^{T} \tilde{\mathbf{X}})^{-1} \tilde{\mathbf{X}}^{T} \mathbf{T}을 생각할 수 있다. 이 최소제곱해는 \mathbf{y}(\mathbf{x})의 원소의 합이 1이 된다는 것은 보장하지만, 각각의 값이 0과 1 사이에 존재한다는 것까지 보장하지는 않는다. 또한, 이상치에 취약하다는 문제점도 있고, 애초에 제곱오차합은 클래스 분류 문제에 있어서는 적합한 함수가 아니다. 이는 가우시안의 최대가능도근사에 대응하기 때문이다.

4.1.4. Fisher’s linear discriminant

선형 판별 문제는 차원 감소 문제로 볼 수도 있다. y = \mathbf{w}^{T}\mathbf{x}를 통해 1차원으로 사영시켜 푸는 것이다. 이 때 적절한 \mathbf{w}의 값을 라그랑주 승수를 통해 구하면 클래스들을 분리하는 데 있어 최적의 값을 구할 수 있다. 이 값은 다음과 같다:

\mathbf{w} = \mathbf{S}_{W}^{-1} (\mathbf{m}_{2} - \mathbf{m}_{1})

\mathbf{S}_{W} = \sum_{n \in \mathcal{C}_{1}} (\mathbf{x}_{n} - \mathbf{m}_{1})(\mathbf{x}_{n} - \mathbf{m}_{1})^{T} + \sum_{n \in \mathcal{C}_{2}} (\mathbf{x}_{n} - \mathbf{m}_{2})(\mathbf{x}_{n} - \mathbf{m}_{2})^{T}

위의 결과를 피셔의 선형 판별식이라 한다.

4.1.5. Relation to least squares

이진 분류 문제에서는 피셔 기준은 최소 제곱법의 특수해이다. 또한, 1-K 코딩 대신 클래스 C_{k} = N / N_{k}로 코딩하면 가중치의 최소제곱해는 피셔 해와 동치가 된다.

4.1.6. Fisher’s discriminant for multiple classes

피셔의 선형 판별식을 K개의 클래스로 일반화하면 다음과 같다.

\mathbf{s}_{W} = \sum_{k=1}^{K} \sum_{n \in \mathcal{C}_{k}} (\mathbf{y}_{n} - \mathbf{\mu}_{k})(\mathbf{y}_{n} - \mathbf{\mu}_{k})^{T}

\mathbf{s}_{B} = \sum_{k=1}^{K} N_{k} (\mathbf{\mu}_{k} - \mathbf{\mu})(\mathbf{\mu}_{k} - \mathbf{\mu})^{T}

J(\mathbf{W}) = \mathrm{tr}[\mathbf{s}_{W}^{-1} \mathbf{s}_{B}]

이 판별식의 특성은 이 기준으로 찾을 수 있는 선형 특성은 최대 K – 1개라는 것이다.

4.1.7. The perceptron algorithm

선형 판별식의 또 다른 예는 퍼셉트론 알고리즘이다. 여기서 \mathbf{w}를 결정하는 데 쓰는 알고리즘은 오차 함수 최소화법에서 착안된다. 이 때 적합한 오차함수는 퍼셉트론 기준 E_{P}(\mathbf{w}) = -\sum_{n \in \mathcal{M}} \mathbf{w}^{T} \mathbf{\phi}_{n} t_{n} 로 구간별 선형이다. 이후 이 오차 함수에 대해 추계적 경사 하강법을 적용해 \mathbf{w}_{\tau + 1} = \mathbf{w}_{\tau} + \eta \mathbf{\phi}_{n} t_{n}의 형태로 가중치를 업데이트한다. 즉, 오분류가 발생할 때마다 가중치에 두 클래스의 차를 학습율을 곱해 더하는 것이다. 추계적 경사 하강법은 전체 오차 함수를 각 단계마다 감소시킨다는 보장은 없다. 하지만, 정확한 해가 존재한다면 그 해에 수렴함이 보장된다. 하지만 해가 여러 개인 경우 어떤 해로 수렴할지 알 수 없으며 선형 분리가 가능하지 않은 데이터에 대해서는 수렴하지 않는다. 또한, K > 2개의 클래스에 대해 일반화할수도 없다. 이는 간단한 문자를 분류하는 작업 등에 쓰이며, 아달린 등의 발전 형태가 있다.

4.2. Probabilistic Generative Models

이제 클래스 조건분포 p(\mathbf{x} | \mathcal{C}_{k})와 클래스 사전분포 p(\mathcal{C}_{k})을 계산해 사후분포를 계산하는 법을 알아보자. 클래스 \mathcal{C}_{1}의 사후분포는 다음과 같다: p(\mathcal{C}_{1} | \mathbf{x}) = \sigma(a), \sigma(a) = \frac{1}{1 + e^{-a}}, a = \ln \frac{p(\mathbf{x} | \mathcal{C}_{1}) p(\mathcal{C}_{1})}{p(\mathbf{x} | \mathcal{C}_{2}) p(\mathcal{C}_{2})}

K개 클래스에 대해서는 다음과 같이 일반화된다. p(\mathcal{C}_{k} | \mathbf{x}) = \frac{e^{a_{k}}}{\sum_{j} e^{a_{j}}} 이는 소프트맥스 함수라고도 한다.

4.2.1. Continuous inputs

이진 분류에서 클래스 조건분포가 가우시안인 경우에는 사후분포는 다음과 같다.

p(\mathcal{C}_{1} | \mathbf{x}) = \sigma(\mathbf{w}^{T} \mathbf{x} + w_{0})

\mathbf{w} = \mathbf{\Sigma}^{-1} (\mathbf{\mu}_{1} - \mathbf{\mu}_{2})

w_{0} = -\frac{1}{2} \mathbf{\mu}_{1} \mathbf{\Sigma}^{-1} \mathbf{\mu}_{1} +\frac{1}{2} \mathbf{\mu}_{2} \mathbf{\Sigma}^{-1} \mathbf{\mu}_{2} + \ln \frac{p(\mathcal{C}_{1})}{p(\mathcal{C}_{2})}

이 때 결정 경계는 선형으로 나타난다. K개 클래스에 대해서 확장해도 마찬가지다. 하지만 각 클래스 조건분포가 공분산을 공유하지 않는 경우라면 결정 경계는 \mathbf{x}에 대한 이차함수가 된다.

4.2.2. Maximum likelihood function

클래스 조건분포와 사전분포를 구했다면 그 분포의 가능도를 최대화시키는 매개변수의 값도 판정할 수 있다. 이는 다음과 같다:

p(\mathcal{C}_{1}) = \pi = \frac{N_{1}}{N_{1} + N_{2}}

\mathbf{\mu}_{1} = \frac{1}{N_{1}} \sum_{n=1}^{N} t_{n} \mathbf{x}_{n}

\mathbf{\mu}_{2} = \frac{1}{N_{2}} \sum_{n=1}^{N} (1 - t_{n}) \mathbf{x}_{n}

\mathbf{\Sigma} = \frac{1}{N} \sum_{n \in \mathcal{C}_{1}} (\mathbf{x}_{n} - \mathbf{\mu}_{1})(\mathbf{x}_{n} - \mathbf{\mu}_{1})^{T} + \frac{1}{N} \sum_{n \in \mathcal{C}_{2}} (\mathbf{x}_{n} - \mathbf{\mu}_{2})(\mathbf{x}_{n} - \mathbf{\mu}_{2})^{T}

이는 K개의 클래스로 확장될 수 있다. 가우시안의 특성 때문에 이 해는 이상치에 취약하다.

4.2.3. Discrete features

특성이 이산적일 때는 어떻게 될까? 이 때는 특성치들이 클래스에 대해 조건부독립이라는 나이브 베이즈 가정을 한다. 즉, 클래스 조건분포를 p(\mathbf{x} | \mathcal{C}_{k}) = \prod_{i=1}^{D} \mu_{ki}^{x_{i}} (1 - \mu_{ki})^{1 - x_{i}} 로 가정하는 것이다. 이를 대입하면 다음을 얻는다:

a_{k}(\mathbf{x}) = \sum_{i=1}^{D} [x_{i} \ln \mu_{ki} + (1 - x_{i}) \ln (1 - \mu_{ki})] + \ln p(\mathcal{C}_{k})

즉, \mathbf{x}에 대해 선형이다. 이는 K > 2개의 클래스에 대해서도 일반화 가능하다.

4.2.4. Exponential family

일반화된 지수족 함수, 즉 p(\mathbf{x} | \mathbf{\lambda}_{k}) = h(\mathbf{x}) g(\mathbf{\lambda}_{k}) e^{\mathbf{\lambda}_{k}^{T} \mathbf{u}(\mathbf{x})} 형태의 함수에 대해서는 다음의 해를 얻는다.

a_{k}(\mathbf{x}) = \frac{1}{s} \mathbf{\lambda}_{k}^{T} \mathbf{x} + \ln g(\mathbf{\lambda}_{k}) + \ln p(\mathcal{C}_{k})

역시 \mathbf{x}에 대해 선형이다.

4.3. Probabilistic Discriminative Models

다중 클래스 분류 문제에 대해 사후확률은 소프트맥스로 나타낸 뒤 이 매개변수는 최대가능도근사로 구할 수 있다. 이외에 또 다른 방법으로 반복 재가중 선형 제곱법이 있다. 매개변수를 찾는 생성적(간접적) 방법과 구별적(직접적) 방법의 차이는 구별적 방법에서는 학습해야 할 매개변수의 수가 더 적어진다는 장점이 있다.

4.3.1. Fixed basis functions

선형 분리가 안 되는 입력에 대해서는 적당한 기저 함수를 통해 변환해 선형 분리시킬 수 있다. 하지만 이 변환이 클래스 조건분포간의 중첩을 줄여준다는 보장은 없다. 이러한 고정 기저 함수에는 중요한 한계점이 있다.

4.3.2. Logistic regression

일반화된 선형 모델에 대한 이진 분류의 경우 클래스 사후분포가 p(\mathcal{C}_{1} | \mathbf{\phi}) = \sigma(\mathbf{w}^{T} \mathbf{\phi})의 형태로 나타나는데 이를 로지스틱 회귀라 한다. 이는 특성 공간의 차원이 M차원이면 학습해야 할 매개변수가 M개뿐이라는 이점이 있다. 매개변수를 최대가능도추정하기 위한 오차함수는 다음과 같다:

E(\mathbf{w}) = -\sum_{n=1}^{N} (t_{n} \ln y_{n} + (1 - t_{n}) \ln (1 - y_{n}))

이를 교차 엔트로피 오차 함수라 한다. 이는 추계적 경사 하강법으로 최소화할 수 있다. 단, 최대가능도추정은 선형 분리 가능한 데이터에 대해서 심하게 과적합될 위험이 있다는 것을 염두에 둘 필요가 있다. 이는 사전분포를 둬서 (정규화해서) 해결 가능하다.

4.3.3. Iterative reweighted least squares

로지스틱 회귀는 시그모이드 함수가 비선형이기 때문에 닫힌 해가 없다. 그 대신 다음의 뉴턴-랩슨 법을 쓴다: \mathbf{w}_{new} = \mathbf{w}_{old} - \mathbf{H}^{-1} \nabla E(\mathbf{w})

뉴턴-랩슨 법은 선형 회귀에 대해서는 한 단계만에 최소제곱해를 얻는다. 로지스틱 회귀에 대해서는 그렇지 않지만, 헤시안이 양의 정칙이기 때문에 오차함수가 볼록이고 유일한 최소값을 갖는다. 이 경우를 반복 재가중 최소 제곱법이라 한다.

4.3.4. Multiclass logistic regression

다클래스 로지스틱 회귀의 경우 클래스 사후분포는 특성 변수에 대한 소프트맥스 함수로 나타난다. 이 경우에도 오차 함수는 교차 엔트로피의 형태로 나타난다. 역시 이에 대해서 헤시안이 양의 정칙이기 때문에 오차함수가 볼록이며 유일한 최소값을 갖는다. 똑같이 반복 재가중 최소 제곱법으로 수렴시킬 수 있다.

4.3.5. Probit regression

이진 분류에 대해 다른 형태의 연결 함수를 생각해 보자. 하나의 예는 프로빗 함수로서, 다음과 같이 정의된다:

\mathrm{erf}(a) = \frac{2}{\sqrt{\pi}} \int_{0}^{a} e^{-\theta^{2}} d \theta

\Phi(a) = \frac{1}{2}(1 + \mathrm{erf}(\frac{a}{\sqrt{2}}))

이를 프로빗 회귀라고 하며, 역시 최대가능도추정으로 매개변수 추정을 할 수 있다. 이것의 이점은 이상치에 더 강하다는 것이다. 하지만, 데이터가 올바르게 라벨링되지 않았을 경우 역시 오작동하게 된다.

4.3.6. Canonical link functions

일반적인 지수족 함수에 대해서 위의 결과들을 확장할 수 있는데, 이 경우 정의되는 자연적 연결 함수는 y = f(\mathbf{w}^{T} \mathbf{\phi})일 때 f^{-1}이 된다. f^{-1}(y) = \phi(y)로 택할 경우 오차 함수의 경사는 \nabla E(\mathbf{w}) = \frac{1}{s} \sum_{n=1}^{N} (y_{n} - t_{n}) \mathbf{\phi}_{n}이 된다.

4.4. The Laplace Approximation

로지스틱 회귀에 대해서는 \mathbf{w}에 대해 직접 적분하는 것이 불가능하다. 그래서 다음의 라플라스 근사를 사용한다: f(\mathbf{z}) \simeq f(\mathbf{z}_{0}) e^{-\frac{1}{2} (\mathbf{z} - \mathbf{z}_{0})^{T} \mathbf{A} (\mathbf{z} - \mathbf{z}_{0})}

이로 얻어지는 근사는 q(\mathbf{z}) = \mathcal{N}(\mathbf{z} | \mathbf{z}_{0}, \mathbf{A}^{-1})이 된다. (\mathbf{A} = -\nabla \nabla \ln f(\mathbf{z}) \rvert_{\mathbf{z} = \mathbf{z}_{0}})

라플라스 근사를 적용하기 위해서는 먼저 최빈값 \mathbf{z}_{0}을 찾아야 한다. 또한, 가우시안에 기반하므로 실변수에만 적용 가능하다는 단점도 있다.

4.4.1. Model comparison and BIC

분포에 대한 근사뿐만 아니라 정규화 상수에 대한 근사도 수행할 수 있다. 이는 다음과 같다:

Z \simeq f(\mathbf{z}_{0}) \frac{(2 \pi)^{\frac{M}{2}}}{\lvert \mathbf{A} \rvert^{\frac{1}{2}}}

이를 이용해 모델의 증거도를 비교할 수 있다. 이는 \ln p(\mathcal{D}) \simeq \ln p(\mathcal{D} | \mathbf{\theta}_{MAP}) + \ln p(\mathbf{\theta}_{MAP}) + \frac{M}{2} \ln (2 \pi) - \frac{1}{2} \ln \lvert \mathbf{A} \rvert를 통해 얻어지는데, 첫째 항을 제외한 항들의 합을 오컴 인자라 하며 모델 복잡도를 징벌한다. 이는 -\frac{1}{2} M \ln N으로 근사될 수 있는데, 이를 베이지안 정보 기준이라 한다. 아카이케 정보 기준이나 베이지안 정보 기준은 편리하지만 맹신해서는 안 된다.

4.5. Bayesian Logistic Regression

이제 베이지안 로지스틱 회귀를 알아보자.

4.5.1. Laplace approximation

사후분포에 대해 라플라스 근사를 적용한 값은 다음과 같다.

q(\mathbf{w}) = \mathcal{N}(\mathbf{w} | \mathbf{w}_{MAP}, \mathbf{S}_{N})

\mathbf{S}_{N}^{-1} = \mathbf{S}_{0}^{-1} + \sum_{n=1}^{N} y_{n}(1-y_{n})\mathbf{\phi}_{n}\mathbf{\phi}_{n}^{T}

4.5.2. Predictive distribution

클래스 \mathcal{C}_{1}에 대한 사후예측분포는 다음과 같이 근사된다:

p(\mathcal{C}_{1} | \mathbf{\phi}, \mathbf{t}) \simeq \int \sigma(\mathbf{w}^{T} \mathbf{\phi}) q(\mathbf{w}) d \mathbf{w}

a = \mathbf{w}^{T} \mathbf{\phi}일 때 이는 p(\mathcal{C}_{1} | \mathbf{t}) = \int \sigma(a) \mathcal{N}(a | \mu_{a}, \sigma_{a}^{2}) da, \mu_{a} = \mathbf{w}_{MAP}^{T} \mathbf{\phi}, \sigma_{a}^{2} = \mathbf{\phi}^{T} \mathbf{S}_{N} \mathbf{\phi}이 된다.

이 적분은 직접 해석적으로 구할 수는 없으나, 프로빗 함수로 잘 근사된다. 프로빗 함수로 근사하는 이유는 가우시안과 컨볼루션했을 때 해석적으로 해를 구할 수 있게 되기 때문이다. 이를 적용하면 p(\mathcal{C}_{1} | \mathbf{\phi}, \mathbf{t}) = \sigma(\kappa(\sigma_{a}^{2}) \mu_{a}) 이 된다. (\kappa(\sigma^{2}) = (1 + \frac{\pi \sigma^{2}}{8})^{-\frac{1}{2}})

이 결정 경계를 정할 때 단순히 동등한 사전확률에서 미감지율을 최소화시키는 것을 목적으로 한다면 \mathbf{w}에 대한 주변화는 쓸모가 없다. 하지만, 결정 경계가 좀 더 복잡해진다면 이것이 중요한 역할을 하게 된다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중