[P] Binary 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)