[ML] Kernel Method

 

 

 

Deep Neural Network나 Decision Tree를 학습시킬 때, Empirical Risk Minimization을 목표로 했음.

훈련 데이터 (Empirical) 에 대한 에러 (Risk) 를 최소화 하는 것.

 

Neural Network에서는 정답값과 예측값의 차이를 최소화 하기 위해 가중치를 조정했고,

Decision Tree에서는 데이터의 엔트로피를 줄이는 방향으로 가지를 쳤다. 

 

다만, 훈련 데이터에만 너무 집착하다 보면 Overfitting이 발생한다. Validation과 Regularization을 사용함. 

 

 

 

 

두 클래스를 구분하는 선을 긋는다고 하자. 사실 Solution1과 Solution2 모두 잘 구분하긴 함.

ERM 관점으로는 완벽한 분류임. 근데 새로운 데이터가 들어온다고 했을 때, Solution2가 더 적합해 보인다.

데이터 사이에 여유 공간이 좀 있으니까, 새로운 데이터랑도 잘 맞지 않을까? 

 

여유 공간 == Margin 

 

Hyperplane은 w * x + b = 0 으로 구성됨. (중앙선이라고 생각하면 됨)

2차원에서는 Line인데, 3차원에서는 Plane이다. 4차원 이상에서는 Hyperplane으로 불림. 그냥 구분선임.

w - 결정 경계에 수직인 벡터 

x - 입력 데이터의 위치 

b - Hyperplane의 위치를 조절하는 상수 

 

Support Vector Machine은 이 결정경계 말고도 두 가지 보조 경계선을 추가로 정의한다.

각 클래스의 데이터 중, 결정 경계에 가장 가까운 데이터를 지나가도록 설정됨.

 

 

 

 

 

 

두 경계선 위에 놓이는 데이터 포인트를 Support Vector라고 부른다.

이 Support Vector가 결정 경계를 정의하는데에 사용되고, 나머지 데이터는 모델 학습에 영향을 미치지 않음. 

 

Margin은 결정 경계와 가장 가까이 있는 데이터 까지의 최단 거리. (점과 평면 사이의 거리 공식으로 구할 수 있음)

SVM 에서는 이 거리를 양쪽으로 확보해서 도로를 구성한다. 

 

훈련할 때는 데이터가 고정되어 있지만, 실제 데이터는 다름. Margin이 넓으면 데이터가 삐딱하게 들어와도 잘 분류될 수 있다.

Overfitting 방지에도 사용됨.

 

아무렇게나 w와 b를 줄이는게 아니라, 모든 훈련 데이터가 Margin 경계선 밖에 분류되어야 함. (Hard Margin)

공식 넣어서 쓰면 Margin Width = 2 / || w || 로 유도된다.

 

저 Margin Width를 최대화 해야 함. 즉, || w || 를 최소화 하는게 목표. - Convex Optimization 문제로 변환.

Convex Optimization 문제는 일반적인 최적화 문제보다 Solution을 찾기 쉽고 컴퓨터가 계산하기 쉬움. 

 

Hard Margin + Convex Optimization 문제를 풀어보자.

그냥 미분해서 0되는곳 찾으면 편한데, Hard Margin 조건때문에 안된다. 맘대로 w 줄이다 보면 제약 조건을 어길 수 있음.

 

라그랑주 승수법을 사용해 편하게 풀자. - 제약 조건을 어기면 Penalty를 부과하는 조건을 추가하는 방식.

 

 

 

 

기존 목표 함수에 제약 조건을 합쳐서 Lp 함수를 만들었다.

 

라그라주 승수는 제약 조건마다 하나씩 붙는 가중치이고, 그 오른쪽은 제약조건으로 데이터가 도로 밖으로 잘 분류됐는지 확인하는 부분이다.

이제 미분할 수 있음. w와 b로 편미분해서 0이 되는 지점을 확인할 수 있다. (KKT 조건)

 

 

 

 

 

Lp 를 w에 대해 미분하고 0으로 둔다. 이러면 가중치 벡터 w는 입력 데이터 x의 선형 결합으로 표현됨. 

즉, 라그랑주 승수만 구하면 가중치 w는 공짜임.

 

Lp를 b에 대해 미분하고 0으로 놓는다.

라그랑주 승수와 클래스 y의 곱을 sum 치면 0이 되어야 한다는 제약 조건이 생김.

 

두 결과를 원본 라그랑주 함수에 대입하면 w와 b를 식에서 완전히 제거할 수 있음.

그러면 이제 라그랑주 승수만 남는다 - Dual Problem

 

Dual Problem은 라그랑주 승수에 대한 Quadratic Programming 문제로 풀 수 있어 해결하기가 훨씬 쉽다. (이차함수 + 최적화)

w와 b를 직접 구하지 않고도 데이터간 내적 값만 알면 라그랑주 승수를 구할 수 있고, 이 내적을 대체하는 함수가 Kernel Function.

 

Dual Problem을 풀었을 때 라그랑주 승수가 0보다 큰 데이터 x들이 최종 결정 경계에 영향을 미치는 Support Vector가 된다.

 

 

 

---

 

 

 

 

Hard Margin 조건은 사실 데이터가 완벽하게 분리될 때만 사용할 수 있는 모델이다. 현실적으로 저런 데이터는 잘 없음. 

이상치 하나 때문에 Support Vector Machine이 최적해를 찾지 못하는 경우가 있을 수 있다.

 

그래서 Soft Margin을 도입함. Hard Margin은 절대로 실수를 용납하지 않지만 Soft Margin은 어느정도 실수는 용납해준다.

 

데이터 x가 제약 조건을 어긴 정도를 측정하는 변수인 Slack Variable을 사용한다.

 

 

 

Margin을 최대화하는건 여전히 중요하고, 여기에 Slack Variable의 총합인 Error를 최소화하는 조건이 추가된다.

두 목표를 합치고, 둘 사이의 중요도를 조절하는 상수를 도입해서 식을 다시 작성한다.

 

C는 오류에 대해 벌점을 얼마나 강하게 줄 지 결정하는 HyperParameter로, C가 작을수록 오류를 허용하는 정도가 높다.

 

Soft Margin 문제를 풀기 위해 제약 조건이 추가된 새로운 라그랑주 함수를 정의하자.

 

 

 

 

 

Lp 함수에 Slack Variable 관련 항이 추가된다. 새로운 제약 조건이 추가됐으니 새로운 라그랑주 승수를 도입함.

또 w, b, Slack Variable로 각각 미분하고 0으로 둔다.

 

Slack Variable로 미분할 때, 라그랑주 승수 두 개를 더하면 C가 되는 사실을 알게 됨. 

그런데 새로 추가한 라그랑주 승수는 0보다 크거나 같아야 하니 기존 라그랑주 승수에 대한 조건이 추가된다.

 

식정리를 다 하고 보니까 Dual Problem의 목표 함수는 Hard Margin과 똑같음.

다만 기존 라그랑주 승수에 대한 제약 조건만 변경된다.

 

데이터가 Non-Linear하다면? 더 높은 차원으로 옮겨서, 거기서 선형으로 나눠야 함.

그런데 데이터를 고차원 공간으로 옮기는 작업의 오버헤드가 너무 너무 크다. 차원이 커질수록 계산하다가 컴퓨터 죽는다. 

 

Dual Problem을 다시 보자. 데이터 x는 단독으로 사용되는 곳이 없음; 두 데이터의 내적값만 알면 x가 어떻게 구성되어있는지 몰라도 라그랑주 상수를 구할 수 있다. 

 

여기서 Kernel Method가 사용된다. - 고차원으로 가서 내적 후 돌아올 필요 없이, 저차원에서 그 내적 값만 계산하는 함수.

 

 

 

 

 

Linear Kernel - 기본 선형 SVM

Polynomial Kernel - 다항식 곡선으로 분류 

RBF Kernel - 무한 차원으로 보내는 효과

Hyper-Tangent - 신경망과 유사 

 

 

 

원래 Support Vector Machine은 Classification을 위한 모델이지만, 살짝 비틀면 Regression에서도 활용할 수 있다.

이걸 Support Vector Regression이라고 부름.

 

SVM은 Margin 밖에 데이터를 두지만, SVR은 모든 데이터를 도로 안에 집어넣는다.

 

 

 

 

Regression Line을 중심으로 위아래로 도로를 만들고, 데이터가 이 도로 안에 들어오면 오차가 없다고 친다. 

데이터가 저 도로 밖으로 나가면 나간 정도만큼의 벌점을 부여함. 

 

도로의 너비가 너무 넓으면 Underfitting, 너무 좁으면 Overfitting 발생하니 적당하게 조절하기..

 

기존 회귀는 모든 데이터가 내 그래프 위에 있어야 함을 의미한다면, SVR은 도로 안에만 들어오면 오차가 있어도 통과시켜줌.