Perceptron Convergence Theorem과 그 증명

 
인공지능의 초창기 개념은 퍼셉트론(perceptron)에서부터 시작한다. 오늘 포스팅에서는 On Convergence Proofs for Perceptrons(Novikoff, 1963)을 분석하여 인공지능 학습의 기본 원리를 담고 있는 Convergence Theorem이 무엇인지와 그 증명을 살펴보고자 한다.
 

퍼셉트론

퍼셉트론의 개념은 1943년 McCulloh & Pitts에 의해 생겼지만, 이를 1957년 하드웨어로 구현하여 퍼셉트론의 발명가로 알려진 사람은 Frank Rosenblatt이다.

Frank Rosenblatt, 퍼셉트론의 발명가

 
Rosenblatt가 만든 퍼셉트론은 현재 AI 분야에서 개념적으로 다루어지는 것과 달리 이미지 인식용 하드웨어 기계였다. 이 Mark 1 perceptron machine은 입력층, 은닉층, 출력층의 3개의 층으로 구성되어 있었다.

Mk. 1 Perceptron Machine

Perceptron Convergence Theorem

Perceptron Convergence Theorem은 퍼셉트론의 학습 결과가 특정 값에 수렴함을 수학적으로 보여 준다.
 
먼저, K차원 유클리드 공간에 속하고, 아래와 같은 벡터 y가 존재하는 N개의 벡터(associator weights)를 상정하자.

 
y는 associator weight에 속하는 임의의 벡터와 내적해도 theta보다 큰, 역시 K차원 유클리드 공간에 속하는 벡터이다. 이때, theta는 threshold를 의미한다.
이 associator weight에 해당하는 N개의 벡터를 각 수열의 항으로 하는 새로운 무한수열(training sequence)을 구성한다. 각 벡터가 새로운 무한수열에 등장할 확률은 모두 동일하다.

 
이제, 새로운 수열 v_n을 아래와 같이 재귀적으로 정의하자. 초항 v_0은 랜덤한 값이 주어진다.

 
Perceptron Convergence Theorem은 수열 v_n이 수렴한다고 주장한다. 즉, 어떤 m에 의해 v_n의 m번째 항부터는 아래를 만족한다.

 
여기서 수열 v_n을 위와 같이 정의하는 과정을 error-correction procedure라고 한다.

Perceptron Convergence Theorem의 증명

먼저,

 
을 만족하는 training sequence (w_i_n) 들은 모두 배제하고 생각해도 된다. v_n을 수렴하지 않도록 만드는 데 아무런 영향을 주지 못하기 때문이다. 따라서, 새로운 training sequence는 모든 step에서 correction이 일어난다고 가정하자. 즉, 새로운 training sequence는 아래를 만족한다.

식 (1)

 
이제, 여기서 n은 n번째 step까지 오는 과정에서 이루어진 correction의 횟수이다. 우리는 n에 최댓값이 존재함을 보이면 된다. 그러면 그 최댓값보다 큰 step에서는 correction이 더 이상 이루어지지 않을 것이다.
 

Lemma 1

 
Perceptron Convergence Theorem이 참이라면,

부등식 (2)

 
이 성립하게 된다. 이는 어떤 양의 상수 C와 충분히 큰 n에 대하여
 

부등식 (3)

와 동치임을 보이자.
 

Proof

 

모든 step에서 correction이 일어났다는 가정에 의해

 
이 성립하므로, 부등식 (2)은

 
로 바꿀 수 있다. 코시-슈바르츠 부등식(CSI)에 따르면
 

가 성립한다. 이때

이라면, 

로 잡아 부등식 (3)가 성립한다. 반면에

이라면,
 

 
로 잡으면 충분히 큰 n에 대하여 부등식 (3)가 성립한다. (얼마 이상의 n이면 되겠는지는 직접 구해 보시길...) ■
 

---

식 (1)을 양변 제곱하고 정리한 뒤, n, n-1, ..., 0까지 부등호를 쭉 연결하여 정리하면

을 얻을 수 있다.
 
그러면 이제 증명이 완료되었다. Lemma 1에서 v_n의 크기의 제곱은 n의 이차항을 하한으로 갖지만, 위 식에서는 n의 1차항을 상한으로 갖기 때문에 n은 유한할 수밖에 없다. ■
 

연속한 Perceptron Convergence Theorem

위에서 증명한 정리는 이산함수(수열)에 관한 내용인데, Perceptron Convergence Theorem을 연속함수로 아래와 같이 확장할 수 있다.
 

---

매개변수 t에 대해 정의된 m차원 유클리드 공간 상의 smooth vector function v(t)에 대해, 벡터 y가 존재하여

를 만족하고,

를 만족하는 b의 상한이 존재한다.

---

Perceptron Convergence Theorem이 가지는 의의

이 정리는, 퍼셉트론의 학습 알고리즘이 선형적으로 분리할 수 있는 데이터 집합에 의해 항상 수렴한다는 것을 보여 준다. 즉, 데이터셋을 선형적으로 분리할 수 있다면, 퍼셉트론은 유한한 수의 반복 후에 오류를 만들지 않는 가중치 집합을 찾을 수 있다.

 

K개의 특성을 가지고 있는 데이터는 K차원 공간 상의 한 지점으로 나타낼 수 있다. 선형 분리 가능성(linear separability)은 이러한 K차원 공간 상의 평면 (혹은 초평면)으로 이 데이터셋이 둘로 분리가 된다는 것을 의미한다.