[ML] Perceptron Learning Algorithm (PLA)

*잘못된 내용을 전달할 수도 있으므로 참고하시기 바랍니다.

 

가령 대출을 심사하는 은행원이라고 가정을 해보자. 이때 최종 목적은 돈을 잘 갚을 거 같은 사람한테 돈을 빌려주고, 그에 대한 이자를 받을 수 있게 하는 것이다. 반대로 대출 능력이 없는 사람을 걸러내서 최대한 돈을 안 빌려주는 것도 그 목적 중에 하나다. 결국 은행원이 낼 수 있는 output 자체는 돈을 빌려주냐 마냐가 될 것이다. 물론 이윤을 극대화할 수 있도록 얼마만큼 대출을 하겠느냐도 문제가 될 수 있겠지만, 지금은 일단 돈을 빌려주냐 안 빌려주냐에만 초점을 맞춰보자.

 그러면 은행원은 대출을 원하는 사람의 어떤 모습을 근거로 대출 여부를 판단할까? 당연한 이야기일 수도 있겠지만 일을 할 수 있는 능력이 있느냐, 최종학력은 어떻게 되느냐, 현재 소득 수준은 얼마정도냐 등 여러가지를 고려할 수 있을 것이다. 이런게 모두 고려되면 우리는 하나의 함수를 만들 수 있을 것이다. 다시 말해서 사람의 나이, 학력, 소득 수준 같은 입력을 집어넣어주면 대출을 해주냐 마냐에 대한 결과를 내 보낼 수 있는 식을 만들 수 있을 거라는 것이다. 

 그런데 과연 그 식이 제대로 맞을까? 무턱대고 식하나만 믿고 대출을 해주기에는 변인들이 너무 많다. 가령 옛날에는 돈을 잘벌다가 갑자기 쫄딱 망한 사람한테도 대출을 해줄 수도 있는 노릇이다. 이런 것도 최대한 방지해야 은행원의 목표는 달성될 수 있을 것이다. 

 그런데 우리는 통념상 과거에 돈을 잘 벌면 지금도 돈을 잘 벌고 있을거라고 생각한다. 부익부 빈익빈이라는 말도 있다시피 이런 통념이 생긴 결과 자체도 사람들이 그런 사례를 많이 봐와서 일 것이다. 이렇게 데이터들이 차곡차곡 쌓이면 이것도 대출여부를 결정지을 수 있는 수단이 되게된다. 

 

 지금 위의 사례에 Machine Learning Model 에 필요한 요소들이 전부 다 들어가 있다. 그걸 표로 도식화하면 다음과 같다. 

 

대출 여부를 자동으로 결정짓기 위해서는 결국 target function f을 찾는 것이 궁극적인 목표가 된다. 그런데 당연한 이야기이겠지만 우리는 f를 구할 수 없다. 세상에 완벽한 것은 없기 때문이다. 다만 우리의 가설(hypothesis)를 확고히 하기 위해서 그만큼의 data set을 모으게 된다. 결국 우리는 Machine Learning을 통해서 final hypothesis g를 구하는 게 목적이 되겠다. 앞의 예시를 바탕으로 사람의 나이와 연소득을 바탕으로 hypothesis와 target function을 구하면 다음과 같이 된다. 

앞에서도 말했지만 우리는 ideal function인 f를 구할 수 없다. 다만 지금 주어진 데이터로는 final hypothesis g만 가지고도 어떤 사람에게 대출을 해줘야 할 지를 결정할 수 있다. 그런데 한가지 의문을 가질 수 있다. 지금 입력으로 사람의 나이와 연소득을 주게 되었는데 둘과 output 사이의 관계는 어떻게 될까? 다시말해 둘중에 어떤 요소가 대출 여부를 결정지을 수 있는 중요한 요소가 될까? 이를 위해서 중요하다고 여겨지는 요소에는 weight을 주는 것도 좋을 거 같다.

 

perceptron은 이렇게 주어진 값을 토대로 어떤것에 대한 결정, 즉 binary output을 내보낼때의 상황에서 쓰인다. 이때 위의 입력들은 hypothesis의 입력으로 들어간다. 예를 들어서 위의 대출 문제와 같은 경우에는 다음과 같은 조건문을 세울 수 있다. 

 

그래서 우리가 정한 기준을 만족하면 대출을 하게끔 해주고 아니면 거부하는 형태로 되어 있는 것이다. 거기에 앞에서 잠깐 언급한 요소에 대한 중요도에 따른 weight을 넣게끔 했다. 그런데 잘 보면 우리의 output은 결국 예, 아니오로만 답하는 형태이다. 그리고 이걸 수식으로 표현하기 위해서 sign function을 사용한다. 

 

sign function은 말그대로 x의 입력에 따라서 y가 -1 또는 1을 출력하는 형태를 말한다. 그래서 입력이 0보다 크면 1, 작으면 -1을 출력한다. 참고로 입력이 0일때는 0을 출력으로 내보내기도 하겠지만 우선은 이 상황을 배제하고 수식을 작성하면 다음과 같이 수식을 작성할 수 있다. 

 

여기서 threshold값을 빼주는 형태로 되어 있기 때문에 이걸 반대로 뒤집어서 더하는 형태(b)로 표현했는데 이걸 bias라고 한다. 결국 w(i)x(i)의 합과 bias간의 관계가 사람의 대출 여부를 결정지을 수 있는 수식의 핵심이 될 것이다. 

 그러면 위와 같이 그래프로 그릴 수 있고, 파란 영역에 있는 것들을 대출 가능 자원, 빨간 영역에 있는 것들을 대출 불가능 자원으로 분류할 수 있을 것이다. 그런데 왼쪽 그래프를 보면 파란 것으로 분류되었는데도 빨간 값이 들어가 있는 경우도 있고, 혹은 반대의 경우도 있다. 이 같은 경우가 앞에서 언급한 예측한 결과와 다르게 나온 형태이다. 그러면 이때는 원래의 hypothesis를 수정함으로써 완벽히 분류할 수 있도록 조절이 되어야 한다. 

이렇게 왼쪽의 그래프내의 직선의 기울기가 오른쪽처럼 되야 진정한 linearly separable perceptron classification이 되겠다. 

그러면 지금 입력을 두개로 주고 있기 때문에 직선 방정식은 다음과 같이 정의할 수 있다. 

 

물론 위의 식을 정확히 표현하면 그림에 나온 직선 그래프를 그릴 수 있겠지만, 계산적 편의성을 위해서 bias 자체를 임의의 정수인 w(0)*x(0) 로 가정한다. 그러면 다음과 같이 축약할 수 있게 된다. 

참고로 가장 오른쪽에 있는 표현은 지금 위의 식을 vector form으로 표현했을 때이다. 지금 w와 x는 1xn 행렬과 nx1 행렬간의 inner product를 한 결과와 같기 때문에 이렇게 표현한 것이다. 왜 굳이 vector form으로 표현했는지 궁금할 수 있겠지만 이런 hypothesis의 입력이 수십개가 될 때는 손으로 구하는 게 아니라 matlab같은 걸 사용해야 되는데 이게 matrix 연산에 최적화되어 있다. 그래서 보통 이런 걸 분석하는데 입력은 거진 다 행렬로 주게 된다. 

 이렇게 우리는 하나의 수식을 세웠고, 이 걸 통하면 대출자의 대출여부를 예측할 수 있다. 그런데 앞에서도 언급했던 것처럼 misclassification이 되는 경우가 발생할 때는 분명히 저 classifier를 수정해줘야 한다. 그러면 어떻게 수정할까? 분명 위의 수식은 w와 x로만 구성되어 있고, 출력은 이값을 토대로 계산한다. 그 중에서 x는 입력값 그 자체이기 때문에 결국은 w를 조절하면서 이 classifier를 수정해주게 되는 것이다. 

 결국 이 글의 제목이기도 한 perceptron learning algorithm은 이 가장 optimal한 weight 값을 구하는데 있다. 당연히 처음에 임의의 값을 지정하고 계속 값을 넣어주면서 적절한 weight을 찾아줄 것이기 때문에 어느정도 데이터가 누적될때까지는 잘 맞지 않는다. 그런데 데이터가 어느정도 쌓이게 되면 이정도로도 분류할 수 있게 된다. 

다만 이걸 구하기 위해서는 한가지를 가정해야 한다. 바로 hypothesis의 입력으로 들어가는 dataset이 linear해야 한다는 것이다. 막 생뚱맞게 1의 출력이 몰려있는데 -1이 나오는 결과가 나오는 것으로는 제대로 분류할 수 없기 때문에 제대로 분류하기 위해서는 dataset이 linear 해야 한다. 

PLA의 동작원리는 다음과 같다.

맨위의 수식이야 아까 계산의 단순화를 위해서 vector form으로 바꾼 결과를 sign function에 집어넣은 결과이고, x(n)에 대한 출력 y(n)을 하나의 tuple 형식으로 준비한다. 우리가 이 hypothesis를 바꾸는 시기는 아까도 말했다시피 주어진 hypothesis가 특정 점을 misclassification 할때이다. 그러면 loop를 돌면서 이렇게 misclassification이 될때 weight을 새롭게 업데이트해주면 되는 것이다. 위의 오른쪽 그래프에서 결국 우리가 추구하는 것은 파란색 화살표가 된다. 빨간 색 화살표 말그대로 misclassfied되서 수정이 필요한 경우를 말하는 것이다. 

 자 그럼 loop를 결국 도는데 언제까지 돌까? 사실 가장 optimal한 결과는 당연히 모든 요소들이 제대로 분류될때까지이다. 그런데 만약에 주어진 dataset들이 linearly separable하지 않으면 계속 weight을 수정하다가 어느 순간 무한 루프에 빠지게 될 것이다. 그래서 보통 termination 조건이 적절히(?) 분류될때까지이다. 약간 황당할 수도 있는데 실제로 적절히 분류될때까지만 이런 과정을 수행하고 멈춘다... 사실 코드로 구현할때는 어느정도의 threshold를 두고 그 값이하의 error rate이 나오게 되면 break 하는 식으로 구현된다.

 

 조금 길게 PLA에 대해서 설명해봤다. 사실 이 걸 들었던게 지난학기고, 그냥 막연한 호기심에 들어서인지 성적도 잘 받지 못했다. 그래도 그때 배운 내용을 다시 보는게 중요한 것 같기도 하고, 실제로 내 연구에도 쪼금 필요할 거 같다. 그래서 복습겸 정리하는 것이고, 어쩌면 잘못된 내용이 담겨있을 수도 있다. 그 부분은 참고했으면 좋겠다.