Perceptron algorithm

개요

Perceptron algorithm에 대해 알아보면서 분류 algorithm이 어떻게 작동하는지 직관을 얻는다.

 

Hypothesis of perceptron algorithm

아래와 같이 training dataset이 구성되어 있다고 가정한다.

즉, data x는 d dimension + 1(intercept term)차원에 살고, label y는 0과 1 둘 중 하나의 값을 가진다. 정리해보면, 이진 분류를 위한 training dataset이라고 할 수 있을 것이다.

 

Perceptron algorithm에서는 아래와 같은 가설을 적용하여 이진 분류를 진행한다.

z = $\theta^Tx$가 되고, z는 1 또는 0으로 mapping이 되는 식이다.

만약, $\theta^Tx$이 음수의 값을 낸다면 0으로 mapping될 것이고, $\theta^Tx$이 0 혹은 양수의 값을 낸다면 1로 mapping될 것이다.

t time step의 $\vec{\theta}$가 위 사진과 같은 벡터라고 가정한다면, 위와 같이 분류가 될 수 있는 것이다.

$\theta^Tx$ = 0인 직선이 hyperplane을 형성하여 classifier의 역할을 수행한다.

 

Update rule of perceptron algorithm

Perceptron algorithm에서 사용하고자 하는 parameter update rule은 아래와 같은 모습이다.

위와 같은 update rule을 통해 어떻게 parameter update가 이뤄지는 것일까?

 

우선, 아래와 같은 두 벡터가 있다고 생각해보자.

벡터 a는 parameter 벡터이고, 벡터 b는 데이터 x 벡터라고 가정한다.

현재 두 벡터가 이루고 있는 각이 90도보다 크기 때문에, $\theta^Tx$ < 0인 값이 나오는 상황이라고 할 수 있을 것이다.

그렇다는 말은 $\theta^Tx$는 곧 0으로 분류되는 상황이다. 하지만 데이터 x의 label은 1이라고 가정해보자.

즉, 현재 inference는 0인데, label은 1인 상황인 것이다.

 

Inference를 1로 만들기 위해서는, $\theta^Tx$ 값을 0 혹은 양수로 만들어야 한다.

이는 두 벡터가 이루는 각이 90도 혹은 90도 보다 작은 각이어야 한다.

그렇게 하기 위해서는 어떻게 해야 할까?

 

-> 두 벡터 중 하나를 가지고 나머지 벡터에 소량을 더해주는 것이다.

위는 벡터 a에 alpha값으로 scaling 해준 벡터 b를 더해준 상황이다.

그렇다면 결과적으로 아래와 같은 모습이 나타난다.

여전히 두 벡터는 90도 보다 큰 각을 이루고 inference를 0으로 하고 있지만, 맨 처음 두 벡터가 이루는 각보다는 작아졌다.

perceptron algorithm은 이와 같은 과정을 가지는 paramter update rule을 가지고 있다.

label y와 가설과의 차이가 없으면 0일 것이고 아무런 업데이트가 이루어지지 않는다.

label y와 가설과의 차이가 존재하면 1이라는 값이 발생하여 $\alpha x$를 통해 벡터 간의 사이를 좁히려 하는 것이다.

(-를 통해서 두 벡터 간의 사이를 넓혀줄 수도 있을 것이다.)

 

이러한 위와 같은 식으로 parameter update가 가능해지는 이유는 아래와 같다.

벡터를 더할 때, 무조건 양수인 벡터가 더해지기 때문에 벡터 사이의 거리를 좁히려는 노력은 언제나 성공하게 된다.

 

Paramter update로 hyperplane이 변경되는 상황 예시(using sgd)

위는 t번째 $\vec{\theta}$에 $\alpha y$를 빼줌으로써 두 벡터가 이루는 각의 크기를 크게해주어 parameter update를 한 후, hyperplane을 변경시키는 모습이다.