기계학습 7주차 노트 (Coursera, CS229, by Andrew Ng)


#1

온수당 Machine Learing Note (week #7)

  • Support Vector Machine

  • progress: 7 주차

  • date: 2016.06.21

  • 장소: 사당동 씨어터

  • Note:

  • 1주와 2주는 supervised learing 에서 Linear Regression(선형 회귀)을 공부했습니다.
  • 3주는 classification(군집화)에 대하여 공부했습니다.
  • 4주는 기계학습에서 사용하는 신경망(neural network)을 공부했습니다.
  • 5주는 신경망이 어떻게 학습을 하는지에 대하여 공부합니다.
  • 5주차 이후 중간 복습하는 시간을 가졌습니다.
  • 6주차에서는 기계학습에 도움될 여러가지 것을 공부합니다.
  • 6주차에서 Machine learning에 디자인에 대한 부분을 시간상 이번주에 하고,
  • 7주차에서 해야 할 Support Vector Machine에 대한 부분을 공부합니다.

Week7 contents

  • Large Margin Classification

Optimization Objective

Large Margin Intuition

Mathematics Behind Large Margin Classification

  • Kernels

Kernels I

Kernels II

  • SVMs in Practice

Using A SVM

Large Margin Classification

많은 지도학습에서 사용하는 알고리즘을 서로 비교하면 성능은 비슷하다. 하지만 학습할 데이터의 총량이나 학습에 사용할 요소(feature), 그리고 매개변수(parameter)의 수등에 따라서 알고리즘을 선택하여야 한다. 이번주에 소개할 SVM(Support Ventor Machine)은 학회는 물론이고, 실제 현장에서도 자주 사용되는 알고리즘이다. 또한 비선형에 대해서도 아주 강력한 학습방법을 나타낸다. 그래서 많은 Classification 문제에 SVM을 많이 사용한다.

Optimization Objective

Logistic regression 에서 가설함수로 signoid 함수를 사용하였다.

여기서

  • y = 1 이 되려면 가설함수 Hθ(x) = 1이 되어야하고, θTx ≫ 0 을 만족시키게 되는 θ를 찾고 싶은 것이다.
  • y = 0 이 되려면 가설함수 Hθ(x) = 0이 되어야하고, θTx ≪ 0 을 만족시키게 되는 θ를 찾고 싶은 것이다. .

한 개 training example 에 해당하는 비용함수 cost function을 생각해보자.

Cost function 을 가설 함수 Hθ(x)로 정리하면

이것을 Logistic Regression에서 사용한 Sinnoid 함수를 이용해서 가설 함수에 대입하여 다시 쓰면

이 될 것이다.

y=1 이 되는 ( θTx ≫ 0 ) 를 구하면

이를 근사화하는 piecewise-linear 함수로 z에 대하여 다시 쓰면 cost 1 (z) 로 나타낼 수 있다.

이 그래프는 y = 1 이 되는 z 값의 변화에 따른 비용함수 값을 나타낸 것이다.

  • Z가 커지면, 비용 함수 값은 낮아진다.
  • Z가 0이나 음수가 되면 비용함수 값은 커진다.
  • Logistic regression에서 원하는 θTx가 양수 값(1)을 가지기 위해서는 매우 큰 값이 되면 될 수로 비용함수가 작아지므로 좋다.

y=0 이 되는 ( θTx ≪ 0 ) 를 구하면

이를 근사화하는 piecewise-linear 함수로 z에 대하여 다시 쓰면 cost 0 (z) 로 나타낼 수 있다.

이 그래프는 y = 0 이 되는 z 값의 변화에 따른 비용함수 값을 나타낸 것이다.

  • Z가 커지면, 비용 함수 값은 커진다.
  • Z가 0이나 음수가 되면 비용함수 값은 작아진다.
  • Logistic regression에서 원하는 θTx가 음양수 값(0)을 가지기 위해서는 매우 작은 값이 되면 될 수로 비용함수가 작아지므로 좋다.

SVM의 비용 함수 Cost function

  • Logistic regression은 log 를 이용해서 cost function을 정의했다.

  • SVM은 이와 비슷하지만, 새롭게 정의한 cost1(.) : piecewise-linear한 함수를 사용한다.
  • Logistic regression의 비용함수 (cost function)에 새롭게 정의한 cost 1 (.) 과 cost0(.) 를 대입하면
  • SVM 비용함수(cost function)가 된다.

  • 이 함수를 hinge loss function이라고 부른다.
  • 특징
  • example당 cost의 평균 대신 합을 사용한다.
  • 1/m 을 사용하지 않는다.
  • regularization 을 조정하는계수 λ를 대신하여 C=1 / λ 을 사용해서 trade-off를 한다.
  • SVM은 y가 0, 1 인 확률을 대신하여 가설 함수의 값이 1 혹은 0이 된다.

Large Margin Intuition

  • Large Margin Clissifiers : SVM을 사용해서 분류를 하면 그 분류되는 경계가 최대가 된다.

  • 지금까지 logistic regression에서는 0을 기준으로해서 구분을 했다면

  • SVM은 θTx가 0일 때를 기준으로 classification을 하지 않고

  • +1 이상일 때와 -1 이하일 때로 구분한다.

Y가 1이 되려면

Y가 0이 되려면

large margin classifiers

  • 이렇게 +1과 -1로 구분하는 것이 SVM이 구분되는 경계선과의 여유(margin)이 최대가 된다.

SVM의 비용함수를 다시 써보면

Cost function 을 간략히 쓰면 min (C x A) + B 로 생각할 수 있다.

여기서 학습한 수 C가 충분히 크다면 min (C x A) 를 하기 위해서는 A는 0이 되어야 최소값을 가진다.

  • A를 0으로 만들려면 어떻게 되어야만 할까?

  • 만약 Y = 1 로 구분되는 것이라면

  • A 항을 0 으로 만들기 위해서는 θ가 들어간 θTx 또한 (+1)보다 큰 값이면 된다.
  • 동일한 방법으로 Y = 0 으로 구분되는 것이라면
  • A 항을 0 으로 만들기 위해서는 θ가 들어간 θTx 또한 (-1)보다 작은 값이면 된다.
  • 이것을 다시 정리하면 C * A + B 에서
  • C * A -> A 가 0,
  • 즉 A 가 0이 되는 “(+1)보다 크다, (-1)보다 작다” 이면
  • B는 regularization 항이고 B가 최소가 되는 값이 비용함수가 최소가 되는 최적 값이라고 말 할 수 있다.

우리가 하려고 했던것은 "구분하는 경계 조건을 어떻게 할 것인가?"

이 그림에서 두선 사이에 중간 선을 선택하면 두 분류(y = 0, 혹은 y = 1) 간의 margin을 최대가 된다.

다른 예시를 보자.

학습한 수 C가 적은 수 일 때

두가지를 구분하는 경계선 decision boudary 를 SVM 구했다고 하자.

이때 검은 선으로 경계선이 된다.

학습한 수 C가 충분히 클 때

  • SVM을 통해서 C가 충분히 크기 때문에,
  • 다른 것들과 조금 다른 위치에 있는 outliers에 대해서도
  • 경계 조건을 최대화하는 SVM의 원리에 따라
  • 민감하게 반응하여
  • 최대가 되는 위치로 경계선이 이동해서 구해진다.

Mathematics Behind Large Margin Classification

어떻해서 SVM이 Large Margin Classification으로 동작하는지 수학을 통해서 좀 더 알아보자.

벡터의 내적을 떠올려 보자.

  • U라는 2D 벡터는 u1, u2로 이루어 져 있다.

  • 이것을 그래프로 그리면

  • V라는 2D 벡터는 v1, v2로 이루어 져 있다.

  • 이 u, v 벡터의 내적 (inner product)를 구하면

  • 두 벡터의 내적 (inner product) uTv는

  • 벡터 v를 u에 project 한 벡터의 길이 p에 벡터 u의 길이를 곱한 것이다.

  • 이 때 p 는 scalar이지만 음수가 될 수 있다.

SVM의 decision boudary를 찾는 것은?

SVM의 decision boundary를 찾는 것은 다음의 optimization problem을 푸는 것이다.

여기에서 θTx를 구하는 것이 SVM이다.

  • 이 식을 단순화시키면

  • bias θ0은 0으로 놓고,

    • θ0= 0
  • 2-dimension feature (feature가 2개)인 경우를 가정하도록 하자.

    • n = 2 - (x1, x2)
  • 두개의 매개변수를 가지고 정리하면.

  • 이것을 다시 Root를 써서 다시 정리하면

  • 벡터의 내적에서 보았듯이

  • 이식에서 θ는 2 x 1의 벡터 이다.

  • θ0= 0의 참값이다.

  • 이것을 θ에 대하여 정리하면

  • 따라서 SVM의 비용함수로 정리한 식을 다시 써서 정리하면

  • 이식은 위의 과정을 거쳐서 다음처럼 정리 할 수 있다.

가 되고, 따라서 SVM은 Squared Norm을 최소화 하는 것이라고 할 수 있다.

  • 그럼 θT x에 대해서 위의 식을 그래프로 해서 다시 설명해 보자.

  • 벡터 x는 x1, x2로 해서 그래프로 그리면 빨간 X 위치로 나타낼 수 있다.

  • 벡터 θ를 같은 죄표에 놓고 그리면

  • θT x 는 다음 식처럼 정리할 수 있다.

  • 이식을 통해서 SVM의 비용함수 Cost function을 간략화해서 다시 정리하면.

  • (θT x) >= 1 , ( y = 1 일때) --> p(i) * ||θ|| >= 1 이 된다.
  • (θT x) <= -1, ( y = 0 일때) --> p(i) * ||θ|| <= -1 이 된다.

SVM의 예시

예를 들어서 SVM을 다시 보자.

  • θ0 = 0 일때 경계선을 그리면
  • SQRT (θ1, θ2) = 0 이므로 원점(0,0)을 지나는 경계선이 된다.
  • 이 때 SVM은 이선을 선택하지 않는다.
  • 경계선이 구분할 값들과 가깝다.
  • 왜 그러한지 θ를 보면서 알아보자.
  • θ는 항상 decision boundary와 90’이다.
  • 따라서 다음처럼 θ를 추가해서 그래프를 그릴 수 있다.

  • x1에 대해서 θT x1를 구해보자.
  • 원점(0,0)에서 P1만큼 벡터 내적을 구한 위치가 된다.
  • x2에 대해서 θT x2를 구해보자.
  • 원점(0,0)에서 P2만큼 벡터 내적을 구한 위치가 된다.
  • 여기서 p1 * ||θ|| 는 1보다 큰 값이어야 하며,
  • 여기서 p2 * ||θ|| 는 -1보다 작은 값이어야 한다.
  • 따라서 ||θ|| 는 큰 값이 되어야만 한다.

  • 다른 경계선을 구했다고 하자.

  • 여기서 p1 * ||θ|| 는 1보다 큰 값이어야 하며,
  • 여기서 p2 * ||θ|| 는 -1보다 작은 값이어야 한다.
  • 따라서 ||θ|| 는 작은 값이 될 수 있다.

  • 따라서 첫번째 경계 조건이 아닌 두번째 경계 조건을 SVM은 선택하게 된다.

  • SVM의 Decision boundary에 대하여 수학으로 정리하면

  • θ를 normal vector로 갖는 hyperplane이다.
  • decision boundary와 θ는 서로 orthogonal하다.
  • θ에 해당하는 p 값이 작다면 p(1)||θ||≥+1을 만족시키는 θ 의 길이는 커져야 한다.
  • SVM은 optimization problem은 조건을 만족하는 한 가장 작은 ||θ|| 를 찾는것이 목적이므로
  • 최대 margin의 decision boundary를 구하게 된다.

Kernels

다음과 같은 학습 데이터는 비선형 (non-linear decision boundary)가 필요하다.

  • x1,x2,…와 같은 요소(feature)를 일반적인 형태로 표현하면 f1,f2,… 라고 할 수 있다.
  • 이것은 다시 말해 fx는 기존의 feature들을 모종의 처리 과정을 통해 변환한 새로운 feature이다.
  • 그럼 이제 이 fx 를 어떻게 구하면 non-linear decision boundary를 구할 수 있는지 알아보자.

Kernels I

세가지 요소(feature)가 있다고 하자.

  • x1과 x2 의 축에 이것을 그렸다.

  • 여기서 주의할 점은 l1, l2, l3에 대한 값이 아닌 새로운 (x1,x2)에 대한 공간에 그렸다는 것이다.

  • l1, l2, l3 는 지도학습 (지도자가 수작업으로 선정하였다. 이것을 landmark라고 한다.

  • feature fx 는 원래 feature가 각 landmark에 얼마나 가까운가를 나타내는 것으로 정의한다.

  • 여기서는 Gaussian 함수를 예로 들었다.

  • 즉 fx는 landmark에 가까울수록 큰 값을, 멀수록 작은 값이다.

  • 예시 x은 l1 landmark 와의 관계 (x, l1)을 구하면

  • f1 = exp(- (|| x - l1 ||2 ) / 2σ2) 이며

  • σ : the standard deviation
  • σ2: the variance

  • (x, l1)에 대하여 || x - l1 || 이 된다.

  • 이것은 x이 첫번째 landmark에 가깝다면 f1 ≈ 1 이 된다. 멀다며 f1 ≈ 0 이 된다.

  • 갈은 방법으로 [x, l2], [x, l3] 에 대한 식을 구할 수 있다.

  • f2 = similarity(x, l1) = exp(- (|| x - l2 ||2 ) / 2σ2)
  • f3 = similarity(x, l2) = exp(- (|| x - l1 ||2 ) / 2σ2)

kernel

f1, f2, f3 로 나타낸 함수를 kernel이라고 한다.

  • f1 = similarity(x, l1) = exp(- (|| x - l1 ||2 ) / 2σ2)
  • f2 = similarity(x, l2) = exp(- (|| x - l2 ||2 ) / 2σ2)
  • f3 = similarity(x, l3) = exp(- (|| x - l3 ||2 ) / 2σ2)

  • l1이 [3, 5] 인 벡터라고 하면 f1에 대한 gaussian 함수로 바꿀 수 있으며,
  • gaussian 함수에서 σ2 각을 각각 1, 0.5, 3 에 대하여 그래프로 그릴 수 있다.
  • 여기서 x를 1을 구분하는 경계선을 구한다고 하면.
    • θ0+ θ1 * f1+ θ2 * f2 + θ3 * f3 >= 0 이 되며
    • 여기서
      • θ0 = -0.5
      • θ1 = 1
      • θ2 = 0
      • θ3 = 0
    • -0.5 + 1 + 0 + 0 = 0.5 이며 0.5 > 0 이다.
    • 이 점을 그리면 보라 색 점이 된다.

  • 다시 x를 0을 구분하는 경계선을 구한다고 하면.
    • θ0+ θ1 * f1+ θ2 * f2 + θ3 * f3 >= 0 이 되며
    • 여기서
      • θ0 = -0.5
      • θ1 = 0
      • θ2 = 0
      • θ3 = 0
    • -0.5 + 0 + 0 + 0 = -0.5 이며, -0.5 < 0 이다.
    • 이 점을 그리면 하늘색 점이 된다.

  • 이 식을 통하여 f1, f1는 1에 가깝지만, f3는 0에 가깝다.

  • 예시에 주어진 숫자를 θ에 대입해서 계산하면 각각 f에 대하여 어떤 값이 나올지 계산 할 수 있다.
  • 예시는 decision boundary로 붉은 선을 그릴 수 있었고,
  • 이것은 는non-linear decision boundary 이다.

Kernels II

좀더 복잡한 문제에 대하여 생각해 보자.

각각의 landmark l1, l2, l3에 대하여 y = 1 이 되는 θ를 구하면.

  • 주어진 학습 데이터는 (x1, y1) , (x2, y2), (x3, y3), , , (x (m) , y (m) )

  • l1 = x (1), l2 = x (2), , lm = x (m) 으로 정의 되며,

  • x에 대하여 각각의 similarity f를 구할 수 있다.

  • 가설 함수 y = 1 일 때 θT f > 0 을 구하면

  • 학습에 대하여 다음처럼 정리할 수 있다.

  • 여기서 c가 충분히 크다면 Lower bias, High variance가 되며

  • 여기서 c가 작다면 high bias, lower variance 가 된다.

  • σ2가 크다면, 요소 (feature)에 대하여 매우 부드러운 gaussian 초공간 변환이 될 것이며,

  • σ2가 작다면 , 요소 (feature)에 대하여 매우 급격한 gaussian 초공간 변환이 된다.

SVMs in Practice

Using A SVM

SVM은 이미 잘 알려진 알고리즘이다. 따라서 각 언어 별로 잘 구현된 library가 많다. 직접 구현하는 것 보다는 잘 만들어진 libray package를 이용하는 것이 좋다. ex) liblinear, libsvm, …

여기서 주의해야 할 것은 C값과 kernel의 종류이다.

  • 가우시안 이외에도 많은 커널이 있다.

여러 종류의 학습 자료를 SVM을 통하여 구분하는 방법 (Multi-Class classification using SVM)

구분할 대상이 2개가 아닌 K개 인 경우를 생각해 보자.

많은 프로그래밍 라이브러리 패키지에서 여러 종류를 구분하는 SVM 방법을 가지고 있다.

이전에 배웠던 one vs all 방법처럼 y = i 부터 K번째 까지 반복하며 SVM을 진행하여 여러가지 데이터를 구분할 수 있다.