[머신러닝] Lecture 12 Support Vector Machines

https://www.youtube.com/watch?v=doN5SexZjto&list=PLiPvV5TNogxIS4bHQVW4pMkj4CHA8COdX&index=12

SVM(Support-Vector-Machine)은 logistic regression 및 neural networks 보다 괜찮은 성능을 보여주는 supervised learning algorithm 중 하나이다.

먼저 logistic regression에 대해서 상기해보자.
logistice regression은 activation func.인 sigmoid func.으로 예측 함수를 정의하여,
$0\le h_{\theta}(x)\le 1$ 값을 갖도록 만든다.

• 따라서 만약 $y=1$이라면, $h_\theta(x)$도 1에 가까워져야 하며, 이를 위해 $\theta^Tx$의 값은 0보다 매우 커져야 한다.
• 만약 $y=0$이라면, $h_\theta(x)$도 0에 가까워져야 하며, 이를 위해 $\theta^Tx$의 값은 0보다 매우 작아져야 한다.
  

그리고 logistic regression의 cost func.의 cost 식은 아래와 같다.
$-(y\ log \ h_\theta(x) +(1-y) \ log(1-h_\theta(x)))$
더 정확히 표현하면, $h_\theta(x)=\frac{1}{1+e^-{\theta^Tx}}$이므로 다음과 같다.
$-y\ log \ \frac{1}{1+e^-{\theta^Tx}} -(1-y) \ log(1-\frac{1}{1+e^-{\theta^Tx}})$
그리고 cost function의 그래프를 $y=1$일 때의 그래프와 $y=0$일 때의 그래프로 나눠서 보면 아래와 같다.

• 그런 다음 logistic regression의 cost fuction 그래프를 최대한 근사하는 직선으로 표현하면 그림의 핑크색 선과 같다. 그리고 이를 $cost_{j}(z)$라고 하자. ($j$는 클래스 종류를 의미한다.)
• $cost_{0}(z)$ : $y=0$일 때의 cost 함수.
• $cost_{1}(z)$ : $y=1$일 때의 cost 함수.
  

그러면 위에서 구한 $cost_{j}(z)$를 가지고 logistic regression을 SVM으로 정리해보자.

• 우선 logistic regression 식은 다음과 같다.
• $\underset{\theta}{min} \frac{1}{m} \sum_{i=1}^m [y^{(i)}(-log \ h_\theta(x^{(i)})) +(1-y^{(i)})(-log(1-h_\theta(x^{(i)})))] + \frac{\lambda}{2m}\sum_{j=1}^n\theta^2_j$
• 그리고 위에서 아까 구했던 $cost_{j}(z)$으로 ($z=\theta^Tx$) 근사하면 SVM의 regression 식은 다음과 같다.
• $\underset{\theta}{min} \frac{1}{m} \sum_{i=1}^m [y^{(i)}cost_{1}(\theta^Tx) +(1-y^{(i)})cost_{2}(\theta^Tx)] + \frac{\lambda}{2m}\sum_{j=1}^n\theta^2_j$
• 위 SVM 식에서 사실 $\frac{1}{m}$은 최솟값 $\theta$를 찾는 데 영향을 주지 않는다. 따라서 생략이 가능하다.
  (예: $\underset{u}{min}\ 10(u-5)^2+10$의 최솟값을 나타내는 $u$는 5이다. 앞에 10이 없어도 마찬가지다.)
• 그리고 regularization parameter $\lambda$값을 나눠서 regularization 부분의 계수는 $\frac{1}{2}$로 만들고, $cost_j(\theta^Tx)$ 부분의 계수는 $C$로 만든다. ($C \approx \frac{1}{\lambda}$)
• 이렇게 되면 최종 SVM의 regression 수식은 아래와 같이 나온다.
  
  $\underset{\theta}{min} C \sum_{i=1}^m [y^{(i)}cost_{1}(\theta^Tx) +(1-y^{(i)})cost_{2}(\theta^Tx)] + \frac{1}{2}\sum_{j=1}^n\theta^2_j$
  

이처럼 SVM의 regression 수식 (Cost function)을 구할 수 있으며, 예측은 다음과 같다.

• $\theta^Tx \ge 0$면 1로 예측.
• $\theta^Tx < 0$면 0으로 예측.
  

SVM의 cost function을 가지고 분석을 해보자.

• 만약 $y=1$일 경우, 좌측 그래프 $cost_1(z)$에서 $z\ge 1$이어야 cost 값이 0으로 나올 것이다.
• 반대로 $y=0$일 경우, 우측 그래프 $cost_0(z)$에서 $z\le -1$이어야(1이 아니라 -1이 맞음. 오타.) cost 값이 0으로 나올 것이다.
• 그리고 $z=\theta^Tx$이므로, 위 두 경우를 다음과 같이 정리할 수 있다.
• $y=1$이면 $\theta^Tx\ge1$이어야 함.
• $y=0$이면 $\theta^Tx\le-1$이어야 함.
• 그리고 이때 $C$의 값을 고려해야 한다. 예시로 $C=100,000$와 같은 매우 큰 값을 넣으면 어떻게 될까?
  

그렇다면 SVM의 decision boundary는 어떻게 결정될까?

• $C$의 값이 매우 크기 때문에 cost function을 최소화하려면 $C\times0$과 같이 만들어야 한다.
• $y=1$일 때, $cost_1(\theta^Tx)$는 0으로 가야하므로 $\theta^Tx \ge 1$이 된다.
• $y=0$일 때, $cost_0(\theta^Tx)$는 0으로 가야하므로 $\theta^Tx \le -1$이 된다.
  
  따라서 $C$가 매우 클 때, SVM의 cost function은 $\underset{\theta}{min} \ C\times 0 + \frac{1}{2}\sum_{j=1}^n \theta_j^2$이 되어,
  $\underset{\theta}{min} \frac{1}{2}\sum_{j=1}^n \theta_j^2$과 같이 나올 것이다.
  

SVM을 적용하다보면 아래 그림과 같이 핑크색, 연두색, 검은색 등 여러 개의 descision boudary들이 나올 것이다. 그리고 이 중에서 검은색 라인이 가장 큰 margin을 갖는다. (margin은 데이터와 decision boundary 간의 공간을 의미한다.)

• 그리고 검은색 라인과 같이 margin이 가장 크게 나오는 decision boundary를 찾는 게 SVM의 목적이다.
• 따라서 이러한 SVM을 "Large margin classifier"라고 부르기도 한다.
  

만약 Large margin classifier에서 outlier (이상치) 데이터가 있다면 어떻게 될까?

• Small margin classifier에서 처음에는 검은색 선처럼 decision boundary를 만들지만, 만약 그래프의 좌측 아래 X 데이터가 추가된다면 decision boundary는 검은색에서 핑크색 선처럼 변환될 것이다. 하지만, 이렇게 될 경우 overfitting의 문제점이 있다는 것을 알 수 있다.
• 우리는 SVM의 cost function에서 $C$의 값을 매우 크게 주었다. 그리고 $C=\frac{1}{\lambda}$이므로,
  이는 매우 작은 $\lambda$를 의미하기도 한다.
• 따라서 만약 $C$값이 크지 않았다면 검은색 decision boundary는 outlier data가 추가되도 변화가 거의 없을 것이다.
• 이처럼 SVM에서 overfitting 문제를 방지하기 위해 $C$값을 잘 선택해야 한다.
• 너무 큰 $C$ 값 : Small margin (overfitting)
• 너무 작은 $C$ 값 : Large margin (underfitting)
  

SVM에서 비선형 decision boundary의 경우, 예측 함수의 복잡도가 매우 높아진다는 단점이 존재한다.
아래와 같은 decision boundary가 있다고 가정해보자.
$decision \ boundary = \theta_0 + \theta_1x_1 + \theta_2x_2 + \theta_3x_1x_2 + \theta_4x_1^2 + \theta_5x_2^2+...$
이 경우, 해당 함수값이 0보다 크거나 같을 경우 $y=1$로 예측하고, 0보다 작으면 $y=0$으로 예측한다.
위에서 $\theta$ 뒤에 나오는 다항식들을 간편하게 $f$라고 해보자. decision boundary는 다음과 같이 나온다.
$decision \ boundary = \theta_0 + \theta_1f_1 + \theta_2f_2 + \theta_3f_3 + \theta_4f_4 + \theta_5f_5+...$

그리고 입력 features $x$에 대한 랜드마크 $l^{(i)}$를 설정해보자 (이는 features $x$가 들어왔을 때 해당 값을 나타내는 landmark를 설정하는 것이다.). 그러고 나서 위에서 다뤘던 $f_i$를 아래와 같이 정의해보자.

• $f_1=similarity(x,l^{(1)})=exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2})$ : 이는 입력값 $x$에 대한 feature $f_1$과 랜드마크 $l^{(1)}$간의 유사도를 나타낸다.
  $exp$는 $e^x$를 의미하고, $\sigma$는 kernel parameter를 의미한다.
  $||x-l^{(1)}||^2$은 입력 features $x$와 landmark $l^{(1)}$ 간의 거리(유클리드 거리)를 의미한다.
• $f_2=similarity(x,l^{(2)})=exp(-\frac{||x-l^{(2)}||^2}{2\sigma^2})$ : 이는 입력값 $x$에 대한 feature $f_2$와 랜드마크 $l^{(2)}$간의 유사도를 나타낸다.
• $f_3=similarity(x,l^{(3)})=exp(-\frac{||x-l^{(3)}||^2}{2\sigma^2})$ : 이는 입력값 $x$에 대한 feature $f_3$과 랜드마크 $l^{(3)}$간의 유사도를 나타낸다.
• 이처럼 $similarity(x,l^{(i)})$를 "(gaussian) kernel function"(커널 함수)이라고 한다.
• 위 $f$의 값을 통해서 어떤 feature를 선택하는 게 좋을지 확인할 수 있다.
  

$f_1$를 예시로 더 살펴보자.
위 수식에서 있었던 $exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2})$은 $exp(-\frac{\sum_{j=1}^n(x_j-l_j^{(1)})^2}{2\sigma^2})$과 같이 바뀐다.

• 만약 $x \approx l^{(1)}$이라면, $f_1 \approx exp(-0) \approx 1$과 같이 결과가 나올 것이다.
• 반면에 $x$가 $l^{(1)}$에서 멀리 떨어졌다면 (유사도가 매우 낮다면),
  $f_1 \approx exp(-Big \ Number) \approx 0$과 같이 결과가 나올 것이다.
  

그래프를 예시로 그리면 아래와 같다.

• $x \approx \begin{bmatrix}3 \\ 5\end{bmatrix} = l^{(1)}$이면, $f_1 \approx 1$인 것을 볼 수가 있다.
• 이때 kernel parameter $\sigma$의 값에 따라서 그래프의 모양이 달라지는 것을 확인할 수 있다.
  $\sigma$가 작을수록 가파른 모양을 보이고, $\sigma$가 클수록 완만한 모양을 보인다.
  

이제 여러 개의 데이터 $x=\begin{bmatrix}x_1 \\ x_2\end{bmatrix}$를 적용해보자. landmark인 $l^{(i)}$와의 유사도에 따라 $f_i$를 선택한다.

• 먼저 parameter $\theta$의 값은 $\begin{bmatrix}-0.5 \\ 1 \\ 1 \\ 0\end{bmatrix}$이라고 가정하자.
• 다음으로 핑크색 점과 같은 x가 들어왔다고 해보자. 이 경우 x는 $l^{(1)}$과 가장 가깝고($f_1 \approx 1$), 나머지 landmark와는 멀다($f_2,f_3 \approx 0$). 따라서 decision boundary는 다음과 같이 나올 것이다. $\theta_0 + \theta_11 + \theta_20+\theta_30=\theta_0+\theta_1=0.5$ 이는 0보다 크거나 같으므로 $y=1$로 예측할 것이다.
• 그리고 하늘색 점 x를 생각해보자. 이 경우 x는 모든 landmark와 멀다($f_1, f_2,f_3 \approx 0$). 따라서, decision boundary는 다음과 같이 나올 것이다. $\theta_0=-0.5$ 이 값은 0보다 작으므로 $y=0$으로 예측한다.
• 정리하면 parameter $\theta$를 봤을 때, $f_1, f_2$의 값이 1에 가까워야 ($x$가 $l^{(1)},l^{(2)}$에 가까워야) $y=1$로 예측하고, 이 외에는 $y=0$으로 예측한다. 따라서 아래 빨간색 경계선처럼 decision boundary가 나올 것이다.
  경계 내부는 $y=1$로 외부는 $y=0$으로 예측한다.
  
  그렇다면 landmark는 어떻게 세팅하고, kernel function은 어떤 걸 선택해야 할까?

landmark를 선택하는 것부터 알아보자. 위 예시에서는 landmark를 임의로 선택했다.
컴퓨터로 이를 적용하려면 어떤 방식으로 landmark를 선택하면 될까?

• 총 m개의 입력 데이터($x^{(1)}, x^{(2)}, ... , x^{(m)}$)에 대해서, 각 $x^{(i)}$를 landmark $l^{(i)}$로 선택하자. 이는 충분히 타당하다고 볼 수 있다.
  

따라서 새롭게 정의하는 feature $f$는 $x$에 대해서 $m$개의 $f_i$를 갖는다.

• 이를 벡터로 표현하면 다음과 같다. $f=similarity(x,l)=\begin{bmatrix}f_0 \\ f_1 \\ . \\ . \\ f_m\end{bmatrix}(f_0=1)$
• 그리고 각 학습 데이터셋 $(x^{(i)}, y^{(i)})$에 대해서 $f^{(i)}$의 값들은 아래와 같이 나온다. $m+1$개의 각 landmark들과의 유사도를 나타낸다.
  $f^{(i)}=similarity(x^{(i)},l^{(i)})=\begin{bmatrix}f_0^{(i)} \\ f_1^{(i)} \\ . \\ . \\ f_m^{(i)}\end{bmatrix}(f_0=1)$
• 그리고 입력 데이터 $x^{(i)}$의 landmark $l^{(i)}$와의 유사도는 1이 되어 $f^{(i)}_i=1$로 나올 것이다.
• 입력 데이터 $x^{(i)}$는 $\mathbb{R}^{n+1}$ or $\mathbb{R}^{n}$ 차원을 갖는다. ($x_0,x_1,...,x_n$, $n+1$개의 features(columns).)
• 따라서 새롭게 정의한 feature 벡터 $f$도 $\mathbb{R}^{m+1}$ 차원을 갖는다. ($f_0,f_1,...,f_m$)
  

따라서 $f$(kernel)를 통해 SVM을 다음과 같이 표현할 수 있다.
"$y=1$ if $\theta^Tf\ge0$"
그리고 이를 학습하는 것도 이전의 SVM cost function과 유사하다. $x$ 대신 $f$로 바꿔준다.

• SVM : $cost_j(\theta^Tx^{(i)})$
• SVM with kernel : $cost_j(\theta^Tf^{(i)})$
• 그리고 parameter regularization 항에서 $\sum^{n}$인데 이를 $\sum^{m}$으로 바꿔준다. 왜냐하면 기존 feature들의 칼럼 차원이 $n$이었다면, 현재 새롭게 정의한 feature $f$의 차원은 $m$이기 때문이다.
• 그리고 별개의 내용으로, $\sum_j\theta_j^2$은 $\theta^T\theta$로 선형대수를 이용해 한번에 계산할 수가 있으며, 이 경우, 학습 데이터셋이 많아질 수록 연산 비용이 많이 든다는 문제점이 있다.
  따라서 이를 $\theta^TM\theta$와 같이 연산하도록 하여 연산 비용을 줄이는 방법이 존재한다. ($\theta^TM$이 scala 값으로 나와서 $c\theta$와 같이 연산을 할 수 있음.)
  

SVM의 파라미터를 정리하면 다음과 같다.

• $C(=\frac{1}{\lambda})$ (regularization parameter in cost func.) :
  • $C$ 값이 크면, parameter regularization이 줄어들고, 이로 인해 bias는 낮아지지만, variance가 높아지는 문제가 있음.
  • $C$ 값이 작으면, parameter regularization이 커지고, 이로 인해 variance는 낮아지지만, bias가 높아지는 문제가 있음.
• $\sigma^2$(kernel parameter) :
  • $\sigma^2$ 값이 크면, feature $f_i$의 값은 매우 완만한 경사를 보여주며 (웬만하면 다 landmark에 가깝다고 판단), 이로 인해 variance는 낮아지지만, bias가 높아진다는 문제점이 있음.
  • $\sigma^2$ 값이 작으면, feature $f_i$의 값은 매우 가파른 경사를 보여주며 (landmark에 진짜 가까운 것들만 선택), 이로 인해 bias는 낮아지지만, variance가 높아진다는 문제점이 있음.
    

이제 logistic gression과 SVM을 언제 사용해야 하는지 비교해보자.
n : feature들의 개수(차원), m : 학습 데이터셋의 개수(차원)

• $n > m$ : logistic regression 및 SVM without a kernel 사용.
• $n < m$ : SVM with Gaussian kernel 사용.
• $n << m$ : feature 차원을 더 늘린 후, logistic regression 및 SVM without a kernel 사용.
• 반면에 Neurl Networks는 $n, m$과 상관없이 좋은 성능을 보여주지만, 학습 시간이 오래 걸린다는 단점이 있다.