[인공지능] Optimization with constraint, Large margin methods

제약조건이 있을 때 optimiztion

일반적으로 object function L(x)를 잡고, 그 값이 min이 되는 경우나 max가 되는 경우가 optimal한 경우로 봤었다.

하지만 만약, L(x) 이외에 g(x)라는 제약조건이 있다면, 언제가 optimal한 값이 될까?

 

예를들어 prediction 함수로 L(x), 제약조건으로 g(x)가 주어졌다고 하자. prediction함수를 maximize하여 optimization 하는 경우를 생각해보면

다음과 같이 쓸 수 있다. L(x)와 g(x)가 아래 그림과 같은 등고선을 갖는다고 가정하자.

feasible region(그림상 노란색 영역) 안에서. 가장 큰 L(x)를 찾는 것이 목표가 되는 것이다. L(x)가 가장 큰 점은 위 그림의 빨간 지점이 될 것이다. (L(x)의 등고선의 중앙부와 가장 가깝다.)이때 이 지점에서 L(x)와 g(x)의 gradiant 방향은 정 반대가 된다. 정반대가 되지 않는다면 다른 optimal값이 있다는 것이다.

 

즉, optimal point의 필수적인 조건은 

 

 

optimization 하기

제약조건이 있는 식을 optimization 하기 위해서, 새로운 식 L'(x)를 정의해준다.

이런 L'(x)를 optimization하는 방법은 제약조건이 없는 L(x)를 optimization했을 때 처럼 미분하여 0이 되는 값을 찾는 것이다.

 

 

 

Karush-Kuhn-Tucker(KKT) condition

optimal point가 나타나는 조건을 얘기한다.

optimal point가 되기 위해선 위 조건 뿐만 아니라 다음과 같은 조건 중 하나는 무조건 만족해야된다.

(1)번 그림은 L(x)의 min값이 region안에 있는 경우로, L(x)의 min값이 L'(x)의 min값이 된다.

(2)번 그림은 L(x)의 min값이 region밖에 있는 경우로, g(x)=0일 때가 무조건 min값이 된다.

 

이때 이런 람다값을 Lagramge multiplier(라그랑주 승수법)이라고 부른다.

 

 

example

L'(x)를 구하여 이분을 해보면 

이는 미지수가 3개이고, 식이 2개이기 때문에, 값을 구할 수 없다. 때문에 KKT-condition을 사용해야된다.

 

 

Large Margin Classifier

margin(data와 boundary까지의 거리)를 최대로 하면 모든 데이터가 알맞게 분류된다는 개념이다.

다음 그림과 같이 2개의 class로 이루어진 data들이 있고, boundary를 통해 나누어져있다고 하자. 선형분류를 했기 때문에 boundary를 w^Tx-b=0으로 두고 마진을 확보하기위해 기준을 1과 -1로 한다.(class값들)

 

class  1 : w^Tx-b > 1

class -1 : w^Tx-b < -1

 

이때 ||w||는 margin에 영향을 주게 된다.

 

 

 

 

||w||가 margin에 영향을 주는 이유

 

즉, margin을 maximize하기 위해선 w의 길이를 minimize하면 된다는 결과를 얻을 수 있다.

(이는 class1 : w^T-b =1 , class-1 : w^T-b=-1 인 조건에서 추출할 수 있는 결과이다.)

 

이를 식으로 정리하면

이를 좀 더 쉽게 만들면 다음과 같이 한번에 표현할 수도 있다.

 

 

 

 

Primal form

 

y_i(w^Tx_i - b)-1  을 g(x)로 보고 (위 제약조건이 있을 때 optimization 참고) object function을 만들면

이러한 형태의 opbject function을 primal form이라 한다.

w차원 + b의 차원으로 object function이 D+1차원이라면 primal form의 parameter는 D+1개가 된다.

이 식을 minimize하여 optimization할 수 있다.

 

 

 

 

 

Dual form

 

primal form을 미분하면 다음과 같은 식을 얻을 수 있다.

이들을 이용해서 L(w,b)를 모두 전개해보면

이러한 형태의 opbject function을 dual form이라 한다.

이 식은 w가 없어지고 라그랑주값 들로만 이루어진 식이 되었다. (알파에 대한 optimization)

L식은 총 N개의 알파값으로 이루어져있으므로 parameter는 N개가 된다.

이 식을 maximize하여 optimization할 수 있다.

 

 

Primal form과 Dual form의 가장 큰 차이는 parameter의 수라고 할 수 있다.

둘 중 어떤것을 사용해도 문제를 풀 수 있다. 다만 문제를 풀 때, primal form은 값을 minimize해야 되고, dual form은 값을 maximize해야 된다는 차이점을 주의해야된다.

 

primal과 dual은 각각 아래 식을 이용해서 분류할 수 있다.

 

 

 

b값 구하는 방법

margin상에 x_s라는 점이 있다고 할 때,  -1 < w^Tx_s-b < 1 이 된다. 

b >  w^Tx_s-1 혹은 

b < w^Tx_s+1 이 되기에

optimal b = b* = 1/2(w^Tx_s+1 + w^Tx_s-1) 이다.