[Theme 06] Perceptron, XOR, MLP, Universal Approximation Theorem

안녕하세요 pulluper 입니다. 이제 ML 6번째 주제입니다. 

이번 시간에는 perceptron의 개념과, xor 문제, 그리고 MLP의 개념에 대하여 살펴 볼 것이고, Universal Approximation Theorem 에 대하여 알아보겠습니다. 그럼 시작하겠습니다 😀😀😀

---

1. Perceptron

 

퍼셉트론은 우리몸의 뉴런을 모방해서 만든 다수의 입력(input)으로 하나의 출력(output)을 만드는 일종의 신호 전달 알고리즘 입니다. 아래의 그림과 같이 뉴런은 왼쪽부분에서 신호를 받고 어떤 임계값(threshold) 이상이면 신호를 오른쪽 부분으로 전달해줍니다. 이와같이 Perceptron 은 다수의 입력들에 대하여 $\sigma(XW+ b)$ 의 출력을 내 보내는 것처럼 구성되어 있습니다. $\sigma$ 는 activation function으로 뉴런의 출력값을 변경시켜주어 신호를 전달할 지 아닐지를 결정하는 역할을 합니다. (Ax+b 는 x가 하나의 vector일때. )

neuron vs perceptron

Perceptron 은 어떤 문제를 풀 수 있었을까요?

 

2. AND/OR/NAND/XOR problem 

 

Perceptron 초기 당시 사람들은 AND OR 문제를 풀면 그것들을 조합해서 스스로 생각할 수 있는 기계를 만들 수 있다고 기대 했습니다. 일단 논리 문제들을 알아보면 다음과 같습니다.

 

AND 문제   : x1, x2 둘다 1 때만 1,

OR 문제     : x1, x2 하나라도 1이면 1,

NAND문제 : AND의 반대(not),

XOR 문제  :  같을 때 0, 다를 때 1 

 

AND OR NAND XOR gate

이를 linear regression 으로 풀면  AND, OR, NAND 은 직선을 구할 수 있습니다. 그러나 XOR 은 1개의 직선으로 풀 수 없었습니다. 이를 푸는 코드는 다음과 같습니다. 

import torch
import torch.nn as nn
from torch.optim import SGD

'''
problem setting 

"AND" gate          "OR" gate           "NAND" gate         "XOR" gate
| x1 | x2 | y |     | x1 | x2 | y |     | x1 | x2 | y |     | x1 | x2 | y | 
| 0  | 0  | 0 |     | 0  | 0  | 0 |     | 0  | 0  | 1 |     | 0  | 0  | 0 |
| 1  | 0  | 0 |     | 1  | 0  | 1 |     | 1  | 0  | 1 |     | 1  | 0  | 1 |
| 0  | 1  | 0 |     | 0  | 1  | 1 |     | 0  | 1  | 1 |     | 0  | 1  | 1 |
| 1  | 1  | 1 |     | 1  | 1  | 1 |     | 1  | 1  | 0 |     | 1  | 1  | 0 |

** graph ** 

^                   ^                   ^                   ^
|                   |                   |                   |  
0          1        1          1        1          0        1          0
|                   |                   |                   |
|                   |                   |                   |
|                   |                   |                   |
0 -- -- -- 0 -->    0 -- -- -- 1 -->    1 -- -- -- 1 -->    0 -- -- -- 1 -->
'''

def gate(x1, x2, y):

    x1 = torch.Tensor(x1)
    x2 = torch.Tensor(x2)

    X = torch.stack([x1, x2], dim=1)
    Y = torch.Tensor(y).unsqueeze(1)
    model = nn.Sequential(nn.Linear(2, 1),
                          nn.Sigmoid(),
                          )

    criterion = nn.BCELoss()
    optimizer = SGD(params=model.parameters(), lr=0.1)

    for iter in range(1000):
        Y_pred = model(X)                       # [4, 1]
        loss = criterion(Y_pred, Y)             # [4, 1]

        optimizer.zero_grad()
        loss.backward()
        optimizer.step()

        if iter % 100 == 0:
            predicted = (Y_pred > 0.5).float()
            acc = (predicted == Y).float().mean()

            print('Iter : {}\t'
                  'loss : {}\t'
                  'Acc  : {}\t'
                  .format(iter,
                          loss,
                          acc))


if __name__ == '__main__':
    # and
    x1 = [0, 1, 0, 1]
    x2 = [0, 0, 1, 1]
    y = [0, 0, 0, 1]

    # or
    x1 = [0, 1, 0, 1]
    x2 = [0, 0, 1, 1]
    y = [0, 1, 1, 1]

    # nand
    x1 = [0, 1, 0, 1]
    x2 = [0, 0, 1, 1]
    y = [1, 1, 1, 0]

    # xor
    x1 = [0, 1, 0, 1]
    x2 = [0, 0, 1, 1]
    y = [0, 1, 1, 0]

    gate(x1, x2, y)

 

왼쪽위 부터 오른쪽 아래 순서대로 AND, OR, NADN, XOR 의 결과

결과를 보면 AND, OR, NAND 의 결과는 Acc 가 1 이 되는 것으로 보아 잘 fitting 이 되는데, XOR의 결과는 하나의 perceptron 을 가지고는 구하기가 힘든 것을 알 수 있습니다. 

 

아래는 fitting 되는 과정을 gif 로 나타낸 그림입니다. 여기서 움직이는 선들은 decision boudary 를 나타내는데, 왼쪽 위부터 오른쪽 아래로 AND OR NAND XOR 문제들 입니다. 그리고 빨간점은 1 파란점은 0 을 뜻합니다. 여기서 앞의 세가지 문제는 잘 구분하는 decision boudary 를 생성합니다. 그러나 XOR 문제는 하나의 선으로 만들기가 불가능 하기 때문에 학습을 하여도 다음과 같은 모습을 보입니다.

 

3. MLP(Multi-Layer-Perceptron or Feed Forward Network)

 

이를 해결하기 위해서는 어떻게 해야 할까요? 이미 제목에 정답이 나와있습니다. 여러개의 Perceptron을 사용하면 됩니다. 그런데 만약 활성화 함수가 없는 퍼셉트론을 여러게 쌓으면 어떻게 될까요? 네 만약 활성화 함수가 없다면 이는 하나의 linear layer 와 같습니다. 즉,  (XW + b)W' + b' 는 일종의 X(WW') + (W'b + b') 으로 보면, 하나의 Linear layer 와 같기 때문입니다. 따라서 XOR문제를 풀 수 없습니다. 

 

- Activation Function 

 

활성화 함수는 신호의 활성화 여부를 알려주는 함수부터 시작했지만 일종의 '공간을 휘는 or 찌그러뜨리는' 역할을 합니다. 이를 통해서 뉴럴 네트워크는 비선형성을 갖게 됩니다. 예를들어 'ReLU, Sigmoid, Tanh' 등 있습니다. 많은 연구가 되고 있으며, 또 다른 아주 많은 활성화 함수가 존재합니다. 

 

- Hidden state 

 

MLP를 여러개의 XW + b (선형변환) 와 활성화 함수의 모임이라고 생각하면, 선형 변환시 output의 차원이라고 생각 할 수 있습니다. 즉, MLP 중간마다 W에 의해서 변환되는 차원의 값 입니다. 

 

아래의 그림을 보시면 처음에는 위치나 간격이 유지되는 XW + b 의 변환이 시작됩니다. 이후 Non-linearilty를 가진 활성화 함수에 의해서 공간이 변하는 모습을 볼 수 있습니다. 

뉴럴 네트워크에 의한 공간변화의 예

https://colah.github.io/posts/2014-03-NN-Manifolds-Topology/

Neural Networks, Manifolds, and Topology -- colah's blog

 

이 개념을 가지고 XOR 문제가 어떻게 풀리는지 알아보겠습니다. 

이번에는 1층의 퍼셉트론이 아닌 2층의 퍼셉트론으로 이루어진 모델을 사용해 보겠습니다. 

 

import torch
import torch.nn as nn
from torch.optim import SGD

def gate(x1, x2, y):

    x1 = torch.Tensor(x1)
    x2 = torch.Tensor(x2)

    X = torch.stack([x1, x2], dim=1)
    Y = torch.Tensor(y).unsqueeze(1)
    model = nn.Sequential(nn.Linear(2, 3),
                          nn.ReLU(),
                          nn.Linear(3, 1),
                          nn.Sigmoid(),
                          )

    criterion = nn.BCELoss()
    optimizer = SGD(params=model.parameters(), lr=0.1)

    for iter in range(1000):
        Y_pred = model(X)                       # [4, 1]
        loss = criterion(Y_pred, Y)             # [4, 1]

        optimizer.zero_grad()
        loss.backward()
        optimizer.step()

        if iter % 100 == 0:
            predicted = (Y_pred > 0.5).float()
            acc = (predicted == Y).float().mean()

            print('Iter : {}\t'
                  'loss : {}\t'
                  'Acc  : {}\t'
                  .format(iter,
                          loss,
                          acc))


if __name__ == '__main__':

    # xor
    x1 = [0, 1, 0, 1]
    x2 = [0, 0, 1, 1]
    y = [0, 1, 1, 0]

    gate(x1, x2, y)

 

학습이 진행될수록 100%의 정확도가 나오는 것을 볼 수 있습니다. 

 

Iter : 0 loss : 0.6947701573371887 Acc   : 0.25
Iter : 10 loss : 0.5985816121101379 Acc   : 0.75
Iter : 20 loss : 0.395317405462265 Acc   : 1.0
Iter : 30 loss : 0.1900641769170761 Acc   : 1.0
Iter : 40 loss : 0.09401008486747742 Acc   : 1.0

 

공간이 휘어지며, XOR 문제의 decision boundary 도 잘 fitting 하는 모습을 볼 수 있습니다. 

 

4. Universal Approximation Theorem

 

마지막으로 universal approximation theorem 에 대하여 알아보겠습니다. 

이 정리는 하나의 은닉층을 갖는 인공신경망은 임의의 연속인 다변수 함수를 원하는 정도의 정확도로 근사할 수 있음을 말합니다. 단, parameter 를 잘못 선택하거나 히든레이어의 뉴런 수가 부족할 경우 충분한 정확도로 근사하는데 실패할 수 있습니다.

 

이는 어떤 1개(이상)의 히든레이어를 갖는 시그모이드 non-linear activation function 을 갖는 뉴럴 네트워크는

임의의 연속함수 f를 근사 할 수 있다는 것입니다.  

 

뉴럴 네트워크의 universality를 알려주고 그런 G 함수의 존재성을 보장해주는 Theorem 입니다. 

 

reference

https://wikidocs.net/24958

01) 퍼셉트론(Perceptron)

https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=windowsub0406&logNo=220883022888 

딥러닝 역사

https://hooni-playground.com/1271/

선형변환과 아핀변환에 대한 고찰 (Linear & Affine Transformation) | Hooni's Playground

https://medium.com/mlearning-ai/tuning-neural-networks-part-ii-considerations-for-initialization-4f82e525da69

Tuning Neural Networks Part II

https://hanlue.tistory.com/12

직관적인 Universal Approximation Theorem 증명

https://3months.tistory.com/140

딥러닝 - Universal Approximation Theorem 실험

https://ko.wikipedia.org/wiki/%EC%8B%9C%EB%B2%A4%EC%BD%94_%EC%A0%95%EB%A6%AC

시벤코 정리 - 위키백과, 우리 모두의 백과사전

https://github.com/csm-kr/xor_prob

GitHub - csm-kr/xor_prob

 

이번 시간에는 Perceptron 그리고  XOR 문제와 Universal Approximation Theorem 를 알아보았습니다. 

질문과 토론은 언제나 환영합니다.