스탠포드 머신러닝 강의 7 Lecture 7 - Kernels | Stanford CS229: Machine Learnin

스탠포드 머신러닝 강의 1:20 / 1:20:24Lecture 7 - Kernels | Stanford CS229: Machine Learning (Autumn 2018)

주요내용

• Optimization Problem
• Representer Theorem
• Kernels (SVM)
• Examples of Kernels (SVM)

Recap

지난 시간에 배웠던 내용을 정리합니다. Optimal margin classifier를 설명합니다.

감마를 최대화하는 w와 b를 구하면 됩니다. 이말은 모든 예제가 구해지면 감마보다 큰 지오매트릭 마진을 같는다는 의미 입니다. 모든 셈플을 잘 분리한다는 말이지요. (반대로 이말은 아웃라이어가 있을때 민감하게 반응한다는 단점이 있습니다. 이것을 어떻게 해결하는지는 뒤에서 설명합니다.)

w와 b에 일정한 값을 곱해도 같은 직선이라는 것을 설명합니다.

Gradient Descent 를 설명합니다.

w는 경계선의 기울어짐을 결정하고 b는 경계선의 수직방향으로의 이동 정도를 결정합니다.

이 내용을 3차원에서 설명해보면 아래와 같습니다. 3차원에서는 2차원에서의 선이 평면으로 나타납니다. 아래 예시에서 w는 평면의 각도를 결정합니다. w3이 0 이라서 수직이 되었네요.

w를 구하기 위한 상세 공식 유도를 아래와 같이 설명합니다.

24:34

Kernel Trick 커널 트릭

커널 트릭은 아래와 같습니다.
1) 커널은 이너프러덕으로 계산된다
2) 피처 x가 2개든, 3개든 얼마든지 매핑 함수를 통해 100,000 또는 수억개의 피처로 만들 수 있다. (아래 그림의 오른쪽 내용)
3) 2)에서 매핑된 변수(Φ(x))들과 z 함수(Φ(z))들을 계산하는 방법을 찾는다.
4) 알고리즘에 있는 <x, z> 를 k<x, z> 로 바꾼다.
이말을 합처보면 고차원 매핑(2)과 내적(3)을 하는 것이 커널 입니다.

커널의 예를 들어 보겠습니다.
x 는 아래와 같습니다.

그러면 아래와 같이 x를 고차원으로 매핑시킨 Φ(x)와 여러변수의 Φ(z)를 만들 수 있습니다. : 여기에서 매핑함수 Φ() 는 R^(n^2)로 정의했기 때문에 3개의 변수(x1, x2, x3)가 9개의 변수(x1,x1, x1,x2, ...)로 변경되었습니다. 이를 계산하기 위해서는 O(n^2)의 시간이 필요합니다.

더 좋은 방법을 생각해 보겠습니다. 아래 그림의 제일 위에 있는 공식 처럼 k(x,z) 를 다른 계산 방법으로 바꿀 수 있습니다. 즉, 함수를 거치지 않고 두 행렬의 곱으로 계산할 수 있습니다. 아래는 (x^Tz)^2가 Φ(x)^T Φ(z)와 같음을 증명하는 내용입니다. (x^Tz)^2 를 두개로 나누어서 () () 이렇게 만들었고 아래 처럼 쭉 따라서 가다보니 결국 (빨간색/녹색 동그라미처럼 두 항목을 곱한 값을 더한다는 것과 같은데...이말은 결국 제일 위줄 공식의 가운데에 있는 Φ(x)^T Φ(z)와 같은 결과이기 때문에 두 공식이 같음이 증명됩니다.
속도는 둘다 R^n 행렬이기 때문에 T 트렌스포즈하고 곱을 하면 O(n) 시간만 있으면 계산이 됩니다.

다시말하면 결국 Φ(x)의 한 행의 내용(빨간 동그라미)과 Φ(z)의 한 행의 내용(녹색 동그라미)을 곱해서 합친 것이 (x^Tz)^2와 같습니다.

여기에 상수 c를 추가해도 역시 소요시간은 O(n) 입니다. Φ(x)는 n+d 중에 d개의 피처를 갖을 수 있는데 최대 d의 깊이를 가질 수 있습니다. 그래서 d=5라면 아래와 같이 x1, x2, x3, x12, x29 도 될수 있고 x1, x2^2, x2,x18 도 될 수 있습니다. 이것은 (n+d)^d 와 비슷합니다.

SVM을 정의 하면
Optimal margin classifier + Kernel Trick = Support Vector Machine
이 됩니다.
이말은 적은 데이터로 많은 피처들을 만들어서 아주 효율적으로 계산해서 효과적으로 분류하는 모델을 만들게 됨을 의미합니다. SVM이 다른 말로 커널인줄 알았는데 조금 다른 것이 이었네요.
아래의 영상을 통해 SVM이 어떻게 동작하는 지 이해를 높일 수 있습니다.
https://www.youtube.com/watch?v=3liCbRZPrZA

여러 차원에 있던 데이터들을 잘 분리하는 하이퍼플레인(평면)이 있는데 이런 그래프를 2차원 으로 축소하면 하이퍼블레인(평면)이 선으로 바뀌어 표시됩니다. 그대신 직선이 아닌 구불구불한 선이 될 수 있습니다. 이러한 2차원 결과를 보여주는 것이 아래 그림 입니다. 이해되시나요. 위의 동영상을 보셨다면 이해가 되실 것 같습니다.

자, 이제 커널을 만드는 방법에 대해서 이야기 합니다. 여러 가정/조건이 있습니다. x, z가 비슷하면 커널함수 k(x,z)의 결과가 커야하고, 반대로 다르면 함수의 결과가 작아야 합니다. 이것은 벡터의 성질과 동일합니다. 이러한 조건을 만족하는 함수중하나가 아래의 공식입니다.

또다른 조건은 지금까지 맞다고 가정했던 공식인 k(x,z) = Φ(x)^T Φ(z) 입니다. 그리고 k(x,x) = Φ(x)^T Φ(x) >= 0 입니다. x1 부터 xd까지의 값을 가진 d 포인트가 있다고 합니다. 이때 K(커널행렬)은 R^(d*d) 입니다. 요소의 표시는 K(sub ij) = k(x(i), x(j)) 로 표시합니다.

그래서 벡터 z가 주어졌을때 커널과 계산 공식을 유도해보면 결국 K가 0보다 크거나 같습니다.

이것은 머서이론 (Mercer Theorem)과 같습니다.

그래서 앞서 커널을 만드는 방법을 설명할때 조건과 이에 적합한 예시를 들었던 아래의 커널함수는 유효함을 알수 있고 이것은 가장 많이 쓰이는 가우시안 커널입니다.

그 밖에도 선형 커널이 있는데 이는 선형함수와 같은 결과를 나타냅니다.

커널 트릭 중 이너프러덕은 다른 모델에서도 많이 쓰이는 방법입니다. < x(i), x(j) >


아래와 같이 2차원에 그래프를 그렸을때 빨간색과 같이 모든 것을 잘 분리하는 모델을 만들고 싶지 않을 것입니다. 왜냐하면 실제 추론 시에는 이렇게 할경우 더 안좋은 성능을 내기 때문입니다. 즉, 훈련데이터에 오버피팅 되어서 실제 추론시에는 성능이 낮아지는 것입니다. Variance가 커지겠네요. 그래서 빨간색 분리선보다는, 이상한 자리에 있는 값들은 잘 못 분리하더라도 파란색 분리선처럼 만들고 싶을 것입니다.

이렇게 하기 위해서 정규화를 할 수 있습니다. L1 놈/노름 소프트 마진 SVM 입니다. 오차 c를 이용하여 분리선과 오차거리를 고려해서 분리하게 됩니다.

L1 놈/노름 소프트 마진 SVM을 쓰는 다른 이유는 아웃라이어 하나만 들어와도 많이 다른 분리선을 만들기 때문에 이를 방지하기 위해 L1 norm soft margin SVM을 쓰는 것이 좋습니다. 옵티마이저가 최악의 케이스도 분리/포함하도록 되었는 경우 이와 같은 문제가 있습니다. 녹색 x 하나 만으로 기존에 파란색 선에서 녹색선처럼 많은 각도가 변경됩니다.

가우시안 커널의 성능도 매우 좋은데 MNIST와 같은 이미지 데이터에 대한 분류에서도 높은 성능을 냅니다. 0과 1의 픽셀 정보를 이용해서 하나의 벡터로 만들어서 SVM의 입력으로 넣고 분류하면 됩니다. SVM은 때로는 딥러닝 보다 좋은 성능을 낼때도 있으며 턴키 알고리즘으로 쉽게 만들 수 있습니다.

Examples of Kernels (SVM)

프로틴 시퀀스 분리 모델의 예시입니다. A부터 Z로 표시되는 원소로 구성된 프로틴의 아미노산 유무를 가지고 프로틴의 기능을 분리하는 모델을 만든다고 가정 합니다. 실제로는 20개인데 알파벳을 이용해서 이해를 쉽게하기 위해 26개를 이용합니다. 왼쪽에 시퀀스에서 등장한 4개의 문자를 오른쪽 피처 4개의 문자와 같으면 그 갯수를 누적하여 표시합니다. BAJT는 왼쪽에서 두번 나와서 오른쪽에 2로 표시됬습니다. 이렇게 해서 Φ(x)를 만들고 k(x,x)를 가우시안 커널을 이용하여 만들어 적용하면 됩니다.

SUMMARY

정리하면 SVM은 커널트릭과 최적의 마진 분리를 이용하는 분류 알고리즘 입니다. 커널 트릭은 입력 데이터를 다차원 데이터로 매핑/변환 하는 함수 Φ(x)와 그 결과와 커널함수 k(x,z) 결과의 행렬을 가지고 분류 모델을 만듭니다. 이러한 결과에 정규화 L1 norm soft margin SVM을 이용하고 오차 c를 추가하여 아웃라이어에 강한 분류 모델을 만듭니다. 최적의 마진 분리는 Geometric margin 지오메트릭 마진은 경계선을 근접한 요소와의 거리를 기준으로 경계선을 나누눈 방법입니다. SVM은 턴키 알고리즘으로 쉽게 개발/활용할 수 있을 뿐만 아니라 초기 딥러닝 모델 만큼이나 성능이 좋아서 지금도 많이 쓰입니다.



아래는 강의 영상 링크 입니다.
https://www.youtube.com/watch?v=8NYoQiRANpg&list=PLoROMvodv4rMiGQp3WXShtMGgzqpfVfbU&index=7