선형 분류기

기계 학습에서 선형 분류기는 각 객체의 특성(피처)에 대한 선형 결합을 기반으로 분류 결정을 내린다. 더 간단한 정의는 선형 분류기란 결정 경계가 선형인 분류기라고 말하는 것이다. 이러한 분류기는 문서 분류와 같은 실용적인 문제, 그리고 보다 일반적으로 많은 변수(피처)를 가진 문제에 대해 잘 작동하며, 비선형 분류기에 필적하는 정확도를 달성하면서도 훈련 및 사용에 소요되는 시간이 더 적다.

정의

분류기에 대한 입력 특성 벡터가 실수 벡터 \vec x인 경우, 출력 점수는 다음과 같다.

y = f(\vec{w}\cdot\vec{x}) = f\left(\sum_j w_j x_j\right),

여기서 \vec w 는 가중치의 실수 벡터이고 f는 두 벡터의 내적을 원하는 출력으로 변환하는 함수이다. (다시 말해, \vec{w}는 \vec x를 R로 매핑하는 1-형식 또는 선형 범함수이다.) 가중치 벡터 \vec w는 레이블이 지정된 훈련 표본 집합으로부터 학습된다. 흔히 f는 임계값 함수로, \vec{w}\cdot\vec{x}의 모든 값 중 특정 임계값 이상인 것을 첫 번째 클래스로, 나머지 모든 값을 두 번째 클래스로 매핑한다. 예를 들어,

위 첨자 T는 전치를 나타내며 \theta 는 스칼라 임계값이다. 더 복잡한 f는 항목이 특정 클래스에 속할 확률을 제공할 수 있다.

이진 분류 문제의 경우, 선형 분류기의 동작을 초평면으로 고차원 입력 공간을 나누는 것으로 시각화할 수 있다: 초평면의 한쪽에 있는 모든 점은 "예"로 분류되고, 나머지는 "아니오"로 분류된다.

선형 분류기는 분류 속도가 중요한 상황에서 자주 사용되는데, 이는 특히 \vec x가 희소(sparse)할 때 가장 빠른 분류기인 경우가 많기 때문이다. 또한 선형 분류기는 문서 분류에서처럼 \vec x의 차원 수가 큰 경우에도 매우 잘 작동하며, 이때 \vec x의 각 요소는 일반적으로 문서 내 단어의 출현 횟수이다(문서-단어 행렬 참조). 이러한 경우 분류기는 적절히 정규화되어야 한다.

생성 모델과 판별 모델

선형 분류기 \vec w의 매개변수를 결정하는 방법에는 크게 두 가지 부류가 있다. 생성 모델과 판별 모델이 그것이다.[^2][^3] 전자의 방법은 결합 확률 분포를 모델링하고, 후자의 방법은 조건부 밀도 함수 P({\rm class}|\vec x)를 모델링한다. 이러한 알고리즘의 예는 다음과 같다:

• 선형 판별 분석(LDA)—가우시안 조건부 밀도 모델을 가정
• 다항 분포 또는 다변량 베르누이 사건 모델을 사용하는 나이브 베이즈 분류기

두 번째 부류의 방법에는 판별 모델이 포함되며, 이는 훈련 집합에 대한 출력의 품질을 최대화하려고 시도한다. 훈련 비용 함수에 추가 항을 넣으면 최종 모델의 정규화를 쉽게 수행할 수 있다. 선형 분류기의 판별적 훈련 예시는 다음과 같다:

• 로지스틱 회귀—관측된 훈련 집합이 분류기의 출력에 의존하는 이항 모델에 의해 생성되었다고 가정하고 \vec w의 최대 우도 추정을 수행
• 퍼셉트론—훈련 집합에서 발생하는 모든 오류를 수정하려고 시도하는 알고리즘
• 피셔의 선형 판별 분석—다른 가정 없이 클래스 간 산포와 클래스 내 산포의 비율을 최대화하는 알고리즘("LDA"와는 다르다). 이는 본질적으로 이진 분류를 위한 차원 축소 방법이다.[^4]
• 서포트 벡터 머신—결정 초평면과 훈련 집합의 예시 사이의 마진을 최대화하는 알고리즘

참고: 이름에도 불구하고, LDA는 이 분류 체계에서 판별 모델에 속하지 않는다. 그러나 LDA를 다른 주요 선형 차원 축소 알고리즘인 주성분 분석(PCA)과 비교하면 그 이름이 의미를 갖는다. LDA는 데이터의 레이블을 활용하는 지도 학습 알고리즘인 반면, PCA는 레이블을 무시하는 비지도 학습 알고리즘이다. 요약하면, 이 이름은 역사적 산물이다.[^5]

판별적 훈련은 조건부 밀도 함수를 모델링하는 것보다 더 높은 정확도를 제공하는 경우가 많다. 그러나 결측 데이터의 처리는 조건부 밀도 모델에서 더 쉬운 경우가 많다.

위에 나열된 모든 선형 분류기 알고리즘은 커널 트릭을 사용하여 다른 입력 공간 \varphi(\vec x)에서 작동하는 비선형 알고리즘으로 변환할 수 있다.

판별적 훈련

선형 분류기의 판별적 훈련은 보통 지도 학습 방식으로 진행되며, 원하는 출력이 포함된 훈련 집합과 분류기의 출력과 원하는 출력 사이의 불일치를 측정하는 손실 함수가 주어진 최적화 알고리즘을 사용한다. 따라서 학습 알고리즘은 다음과 같은 형태의 최적화 문제를 푼다[^1]

\underset{\mathbf{w}}{\arg\min} ;R(\mathbf{w}) + C \sum_{i=1}^N L(y_i, \mathbf{w}^\mathsf{T} \mathbf{x}_i)

여기서

• 는 분류기 매개변수의 벡터이고,
• 는 분류기의 예측과 번째 훈련 예시에 대한 실제 출력 사이의 불일치를 측정하는 손실 함수이며,
• 는 매개변수가 너무 커지는 것(과적합 유발)을 방지하는 정규화 함수이고,
• 는 정규화와 손실 함수 사이의 균형을 제어하는 스칼라 상수(학습 알고리즘 사용자가 설정)이다.

널리 사용되는 손실 함수에는 힌지 손실(선형 SVM용)과 로그 손실(선형 로지스틱 회귀용)이 있다. 정규화 함수 가 볼록하면 위의 문제는 볼록 문제가 된다. 이러한 문제를 풀기 위한 많은 알고리즘이 존재하며, 선형 분류에 널리 사용되는 것으로는 (확률적) 경사 하강법, L-BFGS, 좌표 하강법, 뉴턴 방법 등이 있다.

같이 보기

• 역전파
• 선형 회귀
• 퍼셉트론
• 이차 분류기
• 서포트 벡터 머신
• 위노 (알고리즘)

각주

추가 읽을거리

1. Y. Yang, X. Liu, "텍스트 분류의 재검토", Proc. ACM SIGIR Conference, pp. 42–49, (1999). paper @ citeseer
2. R. Herbrich, "커널 분류기 학습: 이론과 알고리즘," MIT Press, (2001).

---

각주

[^1]: 대규모 선형 분류의 최근 발전

[^2]: T. Mitchell, [https://www.cs.cmu.edu/~tom/mlbook/NBayesLogReg.pdf 생성 모델과 판별 모델 분류기: 나이브 베이즈와 로지스틱 회귀.] Draft Version, 2005

[^3]: A. Y. Ng and M. I. Jordan. [http://www.cs.berkeley.edu/~jordan/papers/ng-jordan-nips01.ps 판별 분류기 대 생성 분류기: 로지스틱 회귀와 나이브 베이즈의 비교.] in NIPS 1

[^4]: R.O. Duda, P.E. Hart, D.G. Stork, "패턴 분류", Wiley, (2001). ISBN 0-471-05669-3

[^5]: Duda, Richard O.. 패턴 분류. John Wiley & Sons, Inc. (2001)