[패턴인식]Chapter 5.3 Generalized Linear Disciminant Functions
(김경환 교수님의 자료와 수업을 통해 제작되었습니다.)
5.3 Generalized Linear Disciminant Functions
앞장에서는 linear한 1차 discriminant funcion을 살펴보았다. 다음과 같이 쓸 수 있다.
이에 2차 discriminant function은 다음과 같이 쓸 수 있다.
위에서 나온 것 처럼, $x_ix_j=x_jx_i$이기 때문에, $w_{ij}=w_{ji}$라고 일반성의 손실 없이 가정할 수 있다. 때문에, separate plane을 정하는데에 사용되는 계수의 개수는 d(d+1)/2개 이다. 대각성분과 대각성분이 아닌 것을 더한 것이다. symmetric하기 때문에 d(d+1)/2개만 필요하게 된다. symmetric하지 않다면 $d^2$일 것이다.
$g(x)=0$에 의해 정해지는 separating surface는 1차 discriminant function과 달리 hyperqudratic이다. 이와 같이 3차항 $w_{ijk}x_ix_j$를 추가하면 더 복잡한 separating surface를 설계할 수 있게 될 것이다. 이를 일반화하면 다음과 같다.
위에서 사용된 $a$는 $\hat{d}$차원에 해당하며, $\hat{d}$개의 $y_i(x)$($\varphi $함수라고도 불린다.)함수는 x의 임의의 함수일 수 있다. 기존 d dimension에서 $\hat{d}$ 차원으로 옮겨진 것이다.
우리는 5.1~2를 거쳐 linear discriminant function에 대해 알아보았고, 그에 해당하는 장점이 존재한다는 것을 살펴보았다. 따라서 linear하게 구분할 수 없는 x에 대해 y로 mapping 시킴으로써 linear한 discriminant function으로 문제에 접근할 수 있게 될 것이다. 즉, y로 mapping 시켰을 때 linear하게 나오도록 하는 mapping을 찾고, 그를 적용시켜주어야 한다는 것이다. 이에 homogeneous linear discriminant function을 찾게 된다.
위 그림 중 왼쪽에서 1차원으로 정의된 x가 존재하고, 이는 nonsimply 하게 연결되어 있고, 하나의 decision bounday(1차원이므로 점에 해당)에 의해 구분될 수 없기 때문에, linear한 성격을 갖지 않게 된다.
따라서, 3차원으로 차원을 늘리고자 하였고, $y=(1 x x^2)^t$의 mapping을 적용한다. 오른쪽 사진을 보면 회색 평면에 의해 위와 아래에 각각 R1과 R2로 구분할 수 있다는 점을 확인할 수 있을 것이다. nonlinear한 성격을 갖고 있던 것이 3차원으로 mapping 시킴으로써 linear한 discriminant function을 갖게 된 것이다.
$a^ty=0$에 쓰이는 a가 $(-1,1,2)^t$라면, $a^t(1 x x^2)=0$이므로, $-1+x+2x^2=0$으로 boundary가 생기게 된다. 이는 $(x+1)(x-0.5)$이므로, 이 값이 0보다 작은 경우에는 -1과 0.5사이에 존재하고, 이는 1차원의 boundary와 동일하게 되는 결과를 얻게 될 것이다.
이는 2차원에서 nonlinear한 decision boundary를 가짐을 확인할 수 있고, 이에 3차원으로 $y=(x_1 x_2 \alpha x_1x_2)^t$로 하여 얻어지는 공간에서 주황색 plane으로 R1과 R2를 구분할 수 있게 된다. $\hat{H}$에 의해 위의 검정색 영역에 대해서는 R1, 아래의 검정색 영역에 대해서는 R2라고 판정하게 된다.
이 역시 nonlinear한 문제에서 linearly separable하게끔 만들어주는 것이다. 여기서의 y가 위에서와 같이 phi function이 된다.
$g(x)$를 $a^ty$라고 쓸 수 있는 편리성을 이용하고자, $x_0=1$로 하여 위와 같이 쓸 수 있다. 기존 x에 1을 추가하여 y의 벡터를 만들고, 기존 $w_1,\cdots,w_d$에서 $w_0$을 추가한다. 다음과 같다.
차원이 늘어났다고 생각할 수 있고, 그렇게 생각한다면 decision boundary는 y공간의 원점을 지나게 될 것이다.
하지만, 우리는 $y_0$=1인 부분에 대해서만 조사해야 하므로, $y_0=1$을 만족하는 2차원 평면을 보면, 원점을 지날 필요는 없다는 것을 볼 수 있다. d차원의 x공간으로 부터 d+1차원의 y 공간으로 매핑하였고, 이는 사소하나 간단한 계산, linear하게 변형해주는 것을 이끌 수 있다.
y에서 $\hat{H}$까지의 거리는 $|g(x)|/||a||$혹은 $|a^ty|/||a||$에 의해 주어질 것이다. $||a||\geq ||w||$이므로, 이 거리는 x에서 H까지의 거리 이하이다.
이번 장에서는 linearly separable하지 않은 x에 대해 y로 mapping 시켜 linear하게 만들어주는 과정을 살펴보았다. 1차원에서 3차원으로 늘리거나 2차원에서 3차원으로 늘려 하나의 plane만으로 R1과 R2의 경계를 만들어줄 수 있게 되었다.
또한, 기존의 $g(x)$를 조금 더 간단하게, linear한 표현으로 만들어 주고자 d차원에서 (d+1)차원으로 늘려주었고, $y_0=1$, a에는 기존 $w$에 $w_0$를 추가했다. 이에 만들어진 $g(x)=a^ty=0$을 만족하는 decision boundary는 y공간에서 원점을 지나는 성질을 가지는 것을 알 수 있었다.
Reference
- pattern classification by richard o. duda