[P] Binary Classification : Support Vector Machine / Logistic Regression

• Binary Classification
• Linear Classification
• Support Vector Machine
• Logistic Regression

심층 신경망의 수학적 기초 3강 (9월 9일), 4강 (9월 14일) 에 기반합니다.

이 문서는 $\LaTeX$를 pandoc으로 변환하여 작성하였기 때문에, 레이아웃 등이 깔끔하지 않을 수 있습니다. 언젠가 pdf 버전의 노트를 공개한다면 그쪽을 참고하면 좋을 것 같습니다.

Binary Classification

잠시 앞서의 정의를 돌아보자.

데이터 $X_1, \dots X_n \in \mathcal{X}$이 있고, 이에 대한 정답 라벨 $Y_1, \dots Y_n \in \mathcal{Y}$이 주어진 경우를 생각해 보자. 이때, 어떤 True Unknown Function $f_\star : \mathcal{X} \to \mathcal{Y}$ 가 있다고 생각하면, $Y_i = f_\star(X_i)$ 를 만족한다.

우리는, $X_i, Y_i$로부터, $f_\star$과 가까운 어떤 함수 $f$를 찾아내는 작업을 수행하고 싶다. $X_i$들에 대해 $Y_i$는 사람이 수집한 데이터를 쓰기 때문에, 이를 Supervised Learning이라고 부른다.

Supervised Learning을 위해, 우리는 다음과 같은 최적화 문제를 생각할 것이다. \(\underset{\theta \in \Theta}{\minimize}\ \frac{1}{N}\sum_{i = 1}^{N} \ell(f_\theta(x_i), f_\star(x_i))\)

특히, 이번에는 $\mathcal{X} = \R^p$, $\mathcal{Y} = \Set{-1, +1}$ 인 문제를 생각하자. 즉, 데이터를 두 클래스로 분리해내는 것이다. 이때, 특별히 이 데이터가 linearly seperable한지를 생각한다. 어떤 초평면 $a^T x + b$ 가 존재하여, $y$값을 $a^T x + b$의 부호에 따라 찍어낼 수 있으면 linearly seperable하다고 정의한다.

Linear Classification

Binary classifcation, 특히 linear classifcation 문제를 해결하기 위해 다음과 같은 affine model을 생각한다. \(f_{a, b}(x) = \sgn(a^T x + b)\) 여기에 loss function으로, 틀린 라벨의 개수를 세는 것이 매우 자연스럽다. 이렇게 컴팩트하게 쓸 수 있다. \(\ell(y_1, y_2) = \frac{1}{2}\abs{1 - y_1 y_2}\)

이제, 다음의 최적화 문제를 풀고 싶다. \(\underset{a \in \R^p, b \in \R}{\minimize}\ \frac{1}{N}\sum_{i = 1}^{N} \ell(f_{a, b}(x_i), y_i)\) 그러면 Linearly seperable한지는 이 최적화 문제의 최적해가 0인지와 동치이다. 그런데, 이 함수는 연속함수가 아니기 때문에 (정확히는 대충 미분가능하다는 조건을 요구한다) SGD같은 알고리즘을 돌릴수가 없다.

Support Vector Machine

따라서, 이 문제를 continuous하게 relaxation하고자 한다. 관점을 바꾸면, 이 라벨이 1일 / -1일 ‘Confidence’를 반환하도록 모델을 좀 잘 확장하고자 한다. 0.5이면 ‘아마도 1일 것으로 보인다’ 같은 느낌으로.

이를 위해서는 $y_i f_{a, b}(x_i) > 0$ 을 만족해야 한다.

그런데, 실제로는 이렇게 하면 $f$값이 0 근처에서만 왔다갔다하는 문제가 있고, 이는 numerical한 면에서나 neural network의 confidence라는 해석으로나 적절하지 않으므로 적당히 margin을 주는 것이 바람직하다.

적당히 margin을 1만큼 줘서, $y_i f_{a, b}(x_i) \geq 1$ 을 만족하면 좋을 것 같다. 여기서 ‘좋을 것 같다’ 는 말은 반대로 저 성질을 만족하지 않으면 페널티를 부과하겠다는 발상으로도 해석될 수 있고… 이 페널티 함수를 최소화하는 문제로 쓰면, \(\underset{a \in \R^p, b \in \R}{\minimize}\ \frac{1}{N}\sum_{i = 1}^{N} \max(0, 1 - y_i f_{a, b}(x_i)) = \frac{1}{N}\sum_{i = 1}^{N} \max(0, 1 - y_i (a^T x_i + b))\)

데이터가 linearly seperable하면, 이 식도 optimal value가 0임을 알 수 있다. 이 방법을 Support Vector Machine 이라고 부르며, 흔히 regularizer를 추가한 아래 식으로 쓴다.\(\underset{a \in \R^p, b \in \R}{\minimize}\ \frac{1}{N}\sum_{i = 1}^{N} \max(0, 1 - y_i (a^T x_i + b)) + \frac{\lambda}{2}\norm{a}^2\)

이 최적화 문제 (Relaxation 넣기 전!)가 원본 문제의 relaxation이라는 사실을 보이는 것은 어렵지 않다. 원래 문제의 최적해를 $p_1^\star$ 라 하고, SVM의 최적해를 $p_2^\star$ 라 하면, $p_1^\star = 0 \iff p_2^\star = 0$ 임을 알 수 있다.

결국, relaxed supervised learning은 point prediction을 relaxation 해서 label value 대신 그 label의 probability를 예측하는 방향으로 생각하는 것. Single prediction보다 훨씬 realistic한 세팅으로 생각할 수 있다.

Logistic Regression

Linear binary classification에 대한 또다른 방법. 여전히 Decision boundary $a^T x + b$ 를 알고자 한다. 먼저...

Binary classification에서, 우리가 확인한 데이터의 Label을 확률벡터로 만들어서 (만약 완전히 label이 하나라면, (1, 0) 과 (0, 1) 처럼) 표현한 것을 empirical distribution $\mathcal{P}(y)$ 라고 정의하기로 한다.

다음과 같은 모델을 이용하여 최적화하는 supervised learning을 Logistic Regression이라 한다. \(f_{a, b}(x) = \begin{bmatrix} \frac{1}{1 + e^{a^T x + b}} \\ \frac{1}{1 + e^{-(a^Tx + b)}} \end{bmatrix}\)

이 모델을 이용하여, 다음과 같은 최적화 문제를 해결하고자 한다. \(\underset{a \in \R^p, b \in \R}{\minimize}\ \sum_{i = 1}^{N} \DKL{\mathcal{P}(Y_i)}{f_{a, b}(X_i)}\) 즉, 우리는 empirical distribution과의 KL-Divergence를 최소화하고 싶다. 이 식을 정리하면... \(\underset{a \in \R^p, b \in \R}{\minimize}\ \sum_{i = 1}^{N} H(\mathcal{P}(Y_i), f_{a, b}(X_i)) + \text{ Terms independent of } a, b\) 정확히 Cross entropy $H$를 전개하고, 오른쪽 term들을 다 버리면... \(\underset{a \in \R^p, b \in \R}{\minimize}\ - \frac{1}{N}\sum_{i = 1}^{N} \P(y_i = -1) \log\left(\frac{1}{1 + e^{a^Tx_i + b}}\right) + \P(y_i = 1)\log\left(\frac{1}{1 + e^{-a^Tx_i - b}}\right)\) 이는 다시, $\P(y_i = 1)$ 과 $\P(y_i = -1)$ 이 one-hot이므로, 둘중에 어느쪽이 1인지를 깔끔하게 정리하여, \(\underset{a \in \R^p, b \in \R}{\minimize}\ - \frac{1}{N}\sum_{i = 1}^{N} \log\left(\frac{1}{1 + e^{-y_i(a^Tx_i + b)}}\right)\) 단조감소함수인 Loss function $\ell(z) = \log(1 + e^{-z})$를 도입하여 부호를 떼고 깔끔하게 정리할 수 있다. \(\underset{a \in \R^p, b \in \R}{\minimize}\ \frac{1}{N}\sum_{i = 1}^{N}\ell(y_i(a^T x_i + b))\) 이 문제를 해결한 후, $a^T x + b$ 의 부호에 따라 prediction한다.

SVM과 비교하면, 출발점이 달랐지만 결국은 같은 문제가 되는데, $\ell(z)$ 를 어떻게 정의하느냐의 문제가 된다. SVM은 $\max(0, 1-z)$이고, Logistic regression은 $\log(1 + e^{-z})$ 를 쓰는 경우로 생각할 수 있다. 좌표에 그려보면 두 함수가 사실 굉장히 비슷하게 생겼다.

SVM과 LR은 둘다 (Decision boundary가 hyperplane이라는 관점에서) Linear classifier이지만, LR이 좀더 자연스럽게 multiclass classification으로 확장된다. (Softmax Regression)