Online learning - Perceptron Algorithm

인공지능 수업에서 배운 내용에 추가로 공부한 내용을 정리를 해보려고 한다

 

perceptron convergence theorem

$$ \sigma(t) = \begin{cases} 1, & \mbox{if }t>=0\\ -1, & \mbox{if }n<0 \end{cases} $$

먼저 퍼셉트론 수식을 위와 같이 정의하고 시작했다

class는 -1과 1 두가지가 되고 $ x $값이 feature로 주어졌을 때 $ y(x_i) $값이 예측한 클래스의 결과가 된다

이 때 $ y(x) = \sigma(\mathrm{W} ^tx) $로 퍼셉트론 수식을 사용해서 만들 수 있다

 

online algorithm은 이 y(x)를 이용한다

먼저 online algorithm과 batch algorithm의 차이가 무엇인지 알아보았다

 

Batch learning은 학습하는 시점에 모든 데이터가 사용 가능하고 그 모든 데이터를 사용하여 학습 시켜 $ \mathrm{W} $를 구하는 것이다

 

 

 

이와 다르게 Online learning은 데이터가 stream으로 주어져 ml algorithm이 지속적으로 업데이트 될 수 있는 방법이다

 

 

online learning은 잘못 분류된 데이터에 대해 $ \mathrm{W} $를 업데이트 한다

$$ \mathrm{W}_{t+1} = \mathrm{W}_{t} + y_ix_i $$

 

이렇게 $ \mathrm{W} $를 업데이트를 하는 경우는 두가지가 있다

$y_i$가 실제로는 -1인데 1이라고 판단하는 경우와 $y_i$가 1인데 -1이라고 판단하는 경우이다

첫번째 경우는 $ \mathrm{W}^Tx_i $가 0 미만이여야 하는데 0이상이라고 판단한 경우이다 

이 경우는 $ \mathrm{W}^Tx_i $ 가 작아져야하니까 $y_ix_i = -x_i$를 더해주는 것이 결국 $ \mathrm{W}^Tx_i $를 줄여주는 것이라고 볼 수 있다

두번째 경우는 $ \mathrm{W}^Tx_i $를 크게 해주어 해당 데이터를 다음번에는 올바르게 판단할 수 있도록 도와준다

 

이 online algorithm의 장점은 데이터의 dimension에 구애받지 않는다는 것이다

일반적인 optimization의 과정은 데이터의 차원이 크면 계산이 오래 걸린다 

하지만 perceptron convergence는 얼마나 작은 구간에 데이터가 있는지와 margin이 얼마나 커질 수 있는지가 중요하다

data가 lineary separable하다면 위 알고리즘을 사용했을 때 $ k <= R^2 \over \gamma ^2 $ 만에 optimal solution $ \mathrm{W} ^*$을 알 수 있다

 

R은 데이터를 구로 감싼다고 생각했을 때 가장 작은 반지름이라고 생각할 수 있다

$ \gamma $는 boundary로부터 가장 가까운 data 까지의 거리이다

따라서 R이 작아지거나 $ \gamma $가 커질수록 더 적은 반복만으로 optimal solution을 찾을 수 있다

 

CSE 446 : Machin Learning ( University of Washington )

CSE 4007 : Artifical Intelligence  ( Hanyang University )