[ML] Theory of the perceptron

MIT openlearninglibrary에서 perceptron 관련 좋은 내용이 있어 공유해본다. 참고로 이전에도 한번 perceptron 관련 내용을 다룬 적이 있다.

[Machine Learning] Perceptron Learning Algorithm (PLA)

Linear separability

\(x\)와 \(y\)로 이뤄진 어떤 dataset \(\mathcal{D}_n\)이 있는 상태에서 해당 dataset 전부를 통틀어 아래의 수식을 만족하는 parameter \(\theta, \theta_0\) 이 있으면 \(\mathcal{D}_n\)은 linear separable하다고 표현한다.

$$ y^{(i)}\left(\theta ^ Tx^{(i)} + \theta _0\right) > 0 \; \; . $$

이를 다르게 표현하면 어떤 classifier를 정의하는 hypothesis \(h\)가 존재하고, 이 classifier가 training dataset을 잘 구분할 수 있다고 할 수 있다.

$$ h(x^{(i)}; \theta , \theta _0) = y^{(i)} \; \; . $$

또는 training error 가 0 일 때도 linear separable하다고 표현할 수 있다.

$$ \mathcal{E}_ n(h) = 0 \; \; . $$

Convergence theorem

우선 perceptron algorithm에 대한 기본 정의를 하자면, 만약 training data \(\mathcal{D}_n\)이 linear separable하다면 perceptron algorithm은 이를 구분지을 수 있는 linear separator를 찾는 것이 보장되어 있다. linear separability를 다른 관점에서 표현하자면 separator와 dataset간의 margin으로도 볼 수 있다. 보통 이때는 separator를 hyperplane이라고도 할 수 있는데, 우선은 hyperplane에 관해서 특정점간의 margin에 대해서 정의해보고자 한다.

일단 앞에서 소개했던 것처럼 separator, 또는 hyperplane은 \(\theta, \theta_0\)으로 표현할 수 있는데, 특정 점 \(x\)와의 거리는 아래와 같이 정의할 수 있다.

$$ \frac{\theta ^ Tx + \theta _0}{\left\lVert \theta \right\rVert }\; \; . $$

(위 식은 어떤 선과 점간의 거리를 구하는 공식을 hyperplane관점에서 표기한 것이다. 사실 이 내용은 중고등학교 때 점과 선간의 거리를 구하는 방법으로 배우기도 했고, cosine distance라고도 알려져 있다)

그러면 해당 점에도 label \(y\)가 있을테니, hyperplane에 대한 labeled point (\(x, y\))의 margine은 다음과 같이 표현할 수 있겠다.

$$ y \cdot \frac{\theta ^ Tx + \theta _0}{\left\lVert \theta \right\rVert }\; \; . $$

(사실 수학적으로 복잡해보일 수 있으나, 매우 간단한 내용이다. 참고로 \(y\)는 -1 또는 1인 값을 가지고, 이를 distance와 곱한 값이다)

위의 식이 양수이면 당연히 hyperplane에 의해서 정의된 linear classifier가 labeled point \(x, y\)를 잘 구분하는 것이 된다.

이제 앞에서 다룬 dataset \(\mathcal{D}_n\)과 hyperplane간의 margin을 최소화하는 것이 목표가 될 것이고, 식으로는 아래와 같이 정의할 수 있다.

$$ \min _ i \left(y^{(i)} \cdot \frac{\theta ^ T x^{(i)} + \theta _0}{\left\lVert \theta \right\rVert }\right)\; \; . $$

만약 dataset에 있는 모든 점들이 linear classifier에 의해서 잘 구분된다면 이 margin은 양수가 될 것이다. 그리고 이 경우에는 그 classifier의 hyperplane과 가장 가까운 점간의 거리를 표현한 것이 위 식이 되겠다.

그림 1. hyperplane

한번 예시를 통해서 이해해보고자 한다. 위의 그림과 같은 linear classifier, \(h\)가 있고, 이를 구성하는 hyperplane \(\theta, \theta_0\)이 있다고 가정해보자

$$ \theta = \begin{bmatrix} 1 \\ -1 \end{bmatrix}, \theta_0 = 1 $$

그러면 이 hyperplane을 이용해서 linear classifier를 표현하면 다음과 같이 된다.

$$ \theta^T x + \theta_0 = 0 $$

보다시피 위의 좌표계에는 3개의 점이 있는데, 각각의 margin은 다음과 같이 구할 수 있다.

$$ y^{(1)} \cdot \frac{\theta^T x^{(1)} + \theta_0}{\Vert \theta \Vert} = 1 \cdot \frac{-2 + 1}{\sqrt{2}} = - \frac{\sqrt{2}}{2} $$

$$ y^{(2)} \cdot \frac{\theta^T x^{(2)} + \theta_0}{\Vert \theta \Vert} = 1 \cdot \frac{1 + 1}{\sqrt{2}} = \sqrt{2} $$

$$ y^{(3)} \cdot \frac{\theta^T x^{(3)} + \theta_0}{\Vert \theta \Vert} = -1 \cdot \frac{-3 + 1}{\sqrt{2}} = \sqrt{2} $$

참고로 \(x^{(1)}\)은 linear classifier가 잘못 구별했기 때문에, 이에 대한 margin도 음수가 나왔다. 그렇기 때문에 전체 dataset에 대한 margin은 위에서 구한 margin중 가장 작은 값이 되기 때문에 \(-\frac{\sqrt{2}}{2}\)가 되겠다.

여기서 Convergence Theorem을 정리해볼 수 있다. 물론 linear classifier가 다양한 케이스가 있겠지만, 간단하게 표기하기 위해서 origin \((0, 0)\)을 지난다고 가정해보자. 이 때 몇가지 조건을 만들어보면

1. 모든 \(i = 1, \dots, n\)에서 어떤 \(\gamma > 0\)에서  \(y^{(i)} \frac{\theta ^{*T}x^{(i)}}{\left\lVert \theta ^*\right\rVert } \geq \gamma\)를 만족하는 \(\theta^*\)가 존재하고,
2. 모든 \(i=1, \dots, n\)에서 dataset이 \(R\)이라는 boundary내에 존재한다면, (\(\Vert x^{(i)} \Vert \leq R \))

perceptron algorithm은 최대 \((\frac{R}{\gamma})^2\)의 잘못된 분류를 할 수 있다는 theorem을 정의할 수 있다.

이 theorem을 증명하기 위해서 몇가지 조건을 설정해야 한다. 우선 \(\theta^{(0)} = 0\) 이라고 하고, 현재의 perceptron algorithm이 \(k\)번 잘못된 분류를 할 때의 hyperplane을 \(\theta^{(k)}\)라고 해보자. 그리고 우리가 찾고자 하는 이상적인 classifier를 \(\theta^*\) 라고 해보면, 우리가 바라는 것은 현재의 hyperplane이 이상적인 hyperplane과 거의 유사하게 변화하는 것이다. 두 값간의 상관성을 다루는 metric은 여러가지가 있겠지만, 가장 쉽게 생각해볼 수 있는 유사성 관련 metric은 cosine similarity이다. 간단하게 말해, 비교하고자 하는 두 요소간의 각도를 보고 유사성을 판단하는 것으로, 매번 학습이 되면서 \(\theta^{(k)}\)가 update가 되면, 둘간의 각도는 점점 줄어들고, 그러면서 현재의 hyperplane은 이상적인 hyperplane으로 가게 될 것이다.

사실 말이 cosine similarity여서 어려워보이지만, 간단하게 두 hyperplane간의 dot product로 구할 수 있다.

$$ \cos (\theta ^{(k)}, \theta ^*) = \frac{\theta ^{(k)} \cdot \theta ^*}{ \lVert \theta ^{(k)}\rVert \lVert \theta ^*\rVert } $$

그러면 이를 두 개로 나눠서 생각해보자.

$$ \cos \left(\theta ^{(k)}, \theta ^*\right) = \left(\frac{\theta ^{(k)} \cdot \theta ^*}{\left\lVert \theta ^*\right\rVert }\right)\cdot \left(\frac{1}{\left\lVert \theta ^{(k)}\right\rVert }\right)\; \; ,$$

이를 일반적인 사례로 적용시켜서, \(i\)번째 dataset (\(x^{(i)}, y^{(i)}\))에서 \(k\)번 잘못 분류한 케이스가 있다고 하면, theorem의 첫번째 항목을 대입시켜서 위의 첫번째 항에 대한 lower boundary를 정의할 수 있다.

$$ \begin{align}  \frac{\theta ^{(k)} \cdot \theta ^*}{\left\lVert \theta ^*\right\rVert } &= \frac{\left(\theta ^{(k-1)} + y^{(i)}x^{(i)}\right)\cdot \theta ^*}{\left\lVert \theta ^*\right\rVert } \\ &= \frac{\theta ^{(k-1)}\cdot \theta ^*}{\left\lVert \theta ^*\right\rVert } + \frac{ y^{(i)}x^{(i)}\cdot \theta ^*}{\left\lVert \theta ^*\right\rVert } \\ &\geq \frac{\theta ^{(k-1)}\cdot \theta ^*}{\left\lVert \theta ^*\right\rVert } + \gamma \\ &\geq k \gamma \end{align}  $$

이제 두번째 항에 대해서도 고려해보면, theorem의 두번째 조건을 이용해서 이 항에 대한 upper boundary도 설정할 수 있다.

$$ \begin{align} \left\lVert \theta ^{(k)}\right\rVert ^2 &=  \left\lVert \theta ^{(k-1)} + y^{(i)}x^{(i)}\right\rVert ^2 \\ &= \left\lVert \theta ^{(k-1)}\right\rVert ^2 + 2y^{(i)} {\theta ^{(k-1)}}^ Tx^{(i)} + \left\lVert x^{(i)}\right\rVert ^2 \\ &\leq \left\lVert \theta ^{(k-1)}\right\rVert ^2 + R^2 \\ &\leq k R^2 \end{align} $$

당연히 앞에서 구한 cosine similarity는 해당 값이 클수록 유사한 것이니까, 위에서 구한 두 inequality를 조합시키면 다음과 같은 식을 구할 수 있다.

$$ \cos \left(\theta ^{(k)}, \theta ^*\right) = \frac{\theta ^{(k)} \cdot \theta ^*}{\left\lVert \theta ^{(k)}\right\rVert  \left\lVert \theta ^*\right\rVert } = \left(\frac{\theta ^{(k)} \cdot \theta ^*}{\left\lVert \theta ^*\right\rVert }\right) \frac{1}{\left\lVert \theta ^{(k)}\right\rVert } \geq (k\gamma )\cdot \frac{1}{\sqrt {k}R} = \sqrt {k}\cdot \frac{\gamma }{R} $$

그리고 또 당연한 이야기지만 cosine의 최대값은 1이기 때문에 마지막으로 구한 항이 1이 되는 조건을 구할 수 있게 되고, 결국은 perceptron algorithm을 통해서 잘 못 분류되는 최대의 경우를 구할 수 있다.

$$ 1 \geq \sqrt{k} \frac{\gamma}{R} \\ k \leq (\frac{R}{\gamma})^2 $$

결론은 앞에서도 소개한 것처럼 \(R\)이 training vector에 대한 classification의 upper boundary라고 하면 perceptron algorithm을 돌렸을 때, 최대 \(\frac{R}{\gamma})^2\) 만큼의 classification error가 발생한다는 것이다. 그러면 perceptron algorithm으로 분류하지 못하는 경우도 존재하는데, 그건 뭔가 싶은 궁금증이 생길 수 있다. 사실 위의 classification error에 대한 boundary는 앞에서 언급한 convergence theorem의 가정을 만족하는 상황에서만 성립하는 케이스이고, XOR dataset처럼 선형적으로 분류하기 어려운 경우는 해당 가정을 만족하지 않기 때문에 애초에 perceptron algorithm을 돌릴수도 없다.

출처: openlearninglibrary.mit.edu/courses/course-v1:MITx+6.036+1T2019/

Introduction to Machine Learning