[DL from Scratch] Chapter 2: Perceptron

해당 Post는 밑바닥부터 시작하는 딥러닝 1권을 읽으면서 정리한 내용들로 구성되어 있다.

밑바닥부터 시작하는 딥러닝

직접 구현하고 움직여보며 익히는 가장 쉬운 딥러닝 입문서

이번 Chapter 2에서는 Perceptron 알고리즘을 설명한다.

이 perceptron 알고리즘은 Neural Network의 기원이 되는 알고리즘이기에, Perceptron의 구조를 배우는 것은 Neural Network와 Deep Learning으로 나아가는데 중요한 아이디어를 제공해준다.

따라서 해당 Chapter 2에서는 Perceptron을 사용하여 간단한 문제를 풀어나간다.

2.1) Perceptron이란?

Perceptron은 multiple signal을 input으로 받아서 single signal을 output으로 출력하는 Algorithm이다.

이때, signal이라 함은 전류나 강물처럼 flow가 있는 것으로 생각하자.

Perceptron output signal은 실제 전류와 달리 0과 1의 (flow / no flow) 값을 가질 수 있다.

• $0$: No Signal (No flow)
• $1$: Signal (flow)

위의 그림은 입력으로 총 $d$개의 input signal을 받은 Perceptron의 예시이다.

• $x_i$: Input Signal
• $w_i$: Weight(가중치, $i = 1, 2, ... , d$)
• $w_0$: Bias(편향)

Weight(Bias)은 학습에 의해 Neural Network가 알아서 설정하는 값이므로 Bias ($b = w_0 x_0 = w_0$)는 Weight($w_0$)이 아닌 Input Signal ($x_0 = 1$)을 1로 fix시킨다.

위 그림의 원을 Neuron or Node라 하고, Input Signal이 Output Neuron으로 전달될 때 각각 고유한 weight가 곱해진다.

즉, 각 weight($w_i$)와 input signal($x_i$)간의 linear combination인 신호의 총합 $\mathbf{w}^T\mathbf{x}$가 Output Neuron으로 전달된다.

$\mathbf{w}$와 $\mathbf{x}$가 모두 column vector이므로 앞의 $\mathbf{w}$에 Transpose $\mathbf{w}^T$를 취한다.

그리고 이 $\mathbf{w}^T\mathbf{x}$가 정해진 한계를 넘어설 때만 1을 출력하고, 그렇지 않으면 0을 출력한다.

1을 출력할 때, 뉴런이 활성화되었다고도 표현한다.

책에서는 그 한계를 임계값이라 하며 Threshold $\theta$로 표현한다.

$$y = \begin{cases} 0 \: (\mathbf{w}^T\mathbf{x} \leq \theta) \\ 1 \:(\mathbf{w}^T\mathbf{x} > \theta) \end{cases}$$

Perceptron은 Multiple Input Signal $x_i$에 대하여 각각 고유한 weight $w_i$를 부여한다.

weight는 각 input signal이 output signal에 주는 영향력을 조절하는 요소로 작용한다. 즉 weight가 클수록 해당 input signal이 더 중요하게 작용한다.

2.2) Simple Logic Gates

Perceptron을 이용한 간단한 활용 문제를 알아보자.

Logic Gate 중 AND Gate를 첫 번째로 시작하자.

AND Gate는 Input이 2개, Output이 1개인 Logic Gate이다.

Input에 대한 Output Signal의 대응 표를 Truth Table이라 한다.

AND Gate는 2개의 Input Signal이 모두 1일 경우에만 1을 출력하고, 그 외에는 0을 출력한다.

이러한 AND Gate를 Perceptron으로 표현하기 위해서는 적절한 Parameter의 조합 $(w_1, w_2, \theta)$를 찾으면 된다.

가능한 paramter의 조합은 무수히 많다: $(0.5, 0.5, 0.7), (0.5, 0.5, 0.8), (1.0, 1.0, 1.0)$ 등 모두 가능하다.

NAND Gate는 AND Gate의 Output에다 Not Gate를 추가한 것이라 볼 수 있다. (Not AND)

즉, AND Gate의 출력을 Reverse 시킨 것이라 볼 수 있다.

즉, Input Signal이 모두 1일 때만 0이고, 그 외에는 1을 출력한다.

NAND Gate의 특징 중 알면 도움되는 부분은:

• Complementary: NAND = NOT + AND = OR + NOT
  • $\bar{xy} = \bar{x} + \bar{y}$
• Invervter: 하나의 input에 1을 걸면 나머지 input을 reverse하는 inverter로 작동
  • $\bar{x \cdot 1} = \bar{x}$
• Deterministic: 하나의 input에 0을 걸면 output은 무조건 1
  • $\bar{x \cdot 0} = 1$

NAND Gate도 마찬가지로 Parameter의 조합 $(w_1, w_2, \theta)$은 무수히 많이 존재한다.

$(w_1, w_2, \theta) = (-0.5, -0.5, -0.7)$ 등 여러 조합이 있다.

사실 AND Gate를 구현하는 Parameter의 부호를 모두 Reverse시키면 NAND Gate가 된다.

OR Gate는 Input Signal이 모두 0이면 0, 그 외에는 1을 출력하는 Gate이다.

즉, Input Signal 중 하나가 1이기만 하면 나머지 Input과 관계없이 항상 1을 출력한다.

OR Gate도 마찬가지로 Parameter의 조합 $(w_1, w_2, \theta)$은 무수히 많이 존재한다.

지금은 우리가 직접 parameter $(w_1, w_2, \theta)$를 결정하고 있지만, Machine Learning Problem은 이러한 parameter를 컴퓨터가 알아서 결정하도록 한다.

Learning이란 적절한 Parameter를 찾는 작업이며, 사람은 perceptron의 structrue를 고민하고 컴퓨터에 train할 데이터를 주는 일을 한다.

AND Gate는 곱하기, OR Gate는 더하기라 생각하면 편하다. 다만, OR Gate 중 $1 + 1 = 1$연산으로 작용하는 것만 실제 산수와 다르다는 것만 기억하자.

정리하자면, 우리는 지금 NAND, OR, AND Gate들을 모두 동일한 구조인 Perceptron을 통해 구현할 수 있음을 알았다.

세 개의 Logic Gate에서 다른 점은 오직 parameter의 조합 $(w_1, w_2, \theta)$뿐이다.

즉, 동일한 구조의 Perceptron을 사용하되 parameter의 값만 적절히 조정하면 다양한 Logic Gate를 구현할 수 있는 것이다.

$$\mathbf{w}^T\mathbf{x} = \theta$$

위의 식에서 $\mathbf{x}, \mathbf{w} \in \mathcal{R}^2$라면 2D x-plane에서의 Hyperplane의 자취로 해석가능하다.

즉, Parameter Set $(w_1, w_2, \theta)$가 주어졌을 때, $\mathbf{x} = [x_1, x_2]^T$의 자취는 vector $\mathbf{w} = [w_1, w_2]^T$에 수직이며 원점으로부터의 거리가 $\frac{\left| \theta \right|} {\left| w \right|}$인 Line을 따른다.

해당 거리를 만족하는 직선은 2개가 존재하는데, 이 중 $\theta$의 부호에 따라 두 직선 중 하나로 결정된다.

쉽게 생각해서 weight vector $\mathbf{w}$에 inner product를 했을 때 그 값이 일정하려면 해당 vector와 수직인 직선 중 하나이다.


직선의 위치를 결정하는 것은 $\theta$ parameter에 의해 원점으로부터의 거리에 따라 확정된다.

2.3) Perceptron Implementation

간단한 AND Gate 부터 Python을 이용하여 구현해보자.

Parameter Set $(w_1, w_2, \theta)$는 function안에서 초기화하고, weight와 input signal의 inner product (linear combination)가 threshold를 넘으면 1을, 넘지 않으면 0을 반환한다.

# AND Gate
def AND(x1, x2):
    w1, w2, theta = 0.5, 0.5, 0.7
    y = x1 * w1 + x2 * w2
    return 1 if y > theta else 0

print(AND(0, 0)) # 0
print(AND(1, 0)) # 0
print(AND(0, 1)) # 0
print(AND(1, 1)) # 1

$$y = \begin{cases} 0 \: (\mathbf{w}^T\mathbf{x} \leq \theta) \\ 1 \:(\mathbf{w}^T\mathbf{x} > \theta) \end{cases}$$

위의 식에서 $\theta$를 $-b$로 치환하면 Perceptron의 동작이 아래와 같이 바뀐다.

$$y = \begin{cases} 0 \: (\mathbf{w}^T\mathbf{x} + b \leq 0) \\ 1 \:(\mathbf{w}^T\mathbf{x} + b > 0) \end{cases}$$

즉, Threshold $\theta$를 0으로 바꾸는 대신, 기존 식에 Bias $b=w_0$를 추가하면 동일하게 동작한다.

즉, Perceptron은 Input Signal과 Weight간 inner product를 수행하고 이에 bias를 더하여, 그 값이 0을 넘으면 1을 출력하고 그렇지 않으면 0을 출력한다.

numpy를 사용하여 간단하게 결과를 확인하면서 진행해보자.

import numpy as np
x = np.array([0, 1])
w = np.array([0.5, 0.5])
b = -0.7
print((w * x).sum() + b)

# -0.19999999999999996

혹은 bias 를 weight vector안에 포함하여 같이 처리하는 방법도 있다.

이때, bias $b = w_0$로 놓고 input vector의 $x_0 = 1$으로 처리한다.

x = np.array([1, 0, 1])
w = np.array([-0.7, 0.5, 0.5])
print((w * x).sum())

# -0.19999999999999996

numpy에서 사용하는 연산을 살펴보자.

• *연산: 두 Array의 shape이 같을 때 cross-correlation 연산을 사용 (element-wise multiplication)
• .sum(): Array 안의 모든 element의 합을 계산 (summation)

weight와 bias를 도입한 AND Gate는 다음과 같이 구현할 수 있다.

def AND(x1, x2):
    x = np.array([x1, x2])
    w = np.array([0.5, 0.5])
    b = -0.7
    y = np.sum(x * w) + b
    return 1 if y > 0 else 0

여기에서 $-\theta$가 $b$로 치환되었으며, bias $b$는 weight $\mathbf{w}$와 기능이 다르다는 사실에 주목하자.

weight $\mathbf{w}$는 input signal이 output에 주는 영향력(중요도)를 조절하는 paramter고, bias $b=w_0$는 뉴런이 얼마나 쉽게 활성화(민감도)하느냐를 조정하는 parameter이다.

예를 들어 $b=-0.1$이면 각 input signal에 weight을 곱한 값들의 합이 0.1을 초과할 때만 뉴런이 활성화된다.

만약 $b=-20$이면 각 input signal에 weight을 곱한 값들의 합이 20을 넘지 않으면 뉴런이 활성화되지 않기에,

bias $b$는 Neuron이 얼마나 쉽게 활성화되는지에 대한 민감도를 나타낸다고 볼 수 있다.

다만, bias $b$와 weight $\mathbf{w}$는 '편향' 과 '가중치'로 서로 구별하기도 하지만, 해당 책에서는 문맥에 따라 모두 '가중치'라고 부르는 경우도 있다.

NAND Gate는 위에서 말했듯이, AND Gate의 parameter들을 모두 reverse시키면 된다.

def NAND(x1, x2):
    x = np.array([x1, x2])
    w = np.array([-0.5, -0.5])
    b = 0.7
    y = np.sum(x * w) + b
    return 1 if y > 0 else 0

OR Gate도 이와 비슷하게 구현가능하다.

def OR(x1, x2):
    x = np.array([x1, x2])
    w = [0.5, 0.5]
    b = -0.2
    y = np.sum(x * w) + b
    return 1 if y > 0 else 0

앞에서 언급했듯이, AND, NAND, OR Gate 모두 동일한 perceptron structure를 가지고 있으며 paramter의 차이만 있다고 했다.

코드를 통해서 봐도, 전체적인 구조는 유지된 채 paramter value만 바뀌고 있음을 알 수 있다.

2.4) Limitations of Perceptrons

지금까지는 NAND, AND, OR Gate의 3가지 Logic Gate들을 구현할 수 있었다. 계속해서 XOR Gate도 살펴보자.

XOR Gate는 Exclusive OR Gate로, Input으로 받는 2개의 Element $x_1, x_2$가 서로 달라야만 1을 출력하는 Logic Gate이다.

$$x \oplus y = xy' + x'y = (x+y)(x'+y')$$

• OR Gate와 NAND Gate를 AND Gate로 연결하여 구현
• Truth Table을 작성하여 가능한 모든 Input Signal ($0, 1$)에 대해 조사하면 동일한 Truth Table을 가진다

다만, 지금까지 본 Single Perceptron 으로는 XOR Gate를 구현할 수 없다.

Perceptron은 하나당 2D X-Plane에서 하나의 Hyperplane이라는 Linear Boundary를 형성한다.

이때, 4개의 Point $(x_1, x_2) = (0, 0), (0, 1), (1, 0), (1, 1)$에 대하여 Output $y$에 따라 boundary를 나눠야 하는데 어떠한 line를 그려도 $y$에 따라 2개의 section으로 구분할 수 없다.

• $(x_1, x_2) = (0, 0), (1, 1)$: 0을 출력
• $(x_1, x_2) = (0, 1), (1, 0)$: 1을 출력

XOR Gate를 만들려면 직선 하나로 위의 조건을 만족하는 2개의 Section으로 나눌 수 없다.

Single-Layer Perceptron은 linear boundary만 생성한다는 한계가 존재한다.

$$\mathbf{w}^T\mathbf{x} = \theta$$

위의 boundary는 vector $\mathbf{x}$에 수직인 linear hyperplane으로, Single-layer perceptron은 오직 선형 경계만 표현 가능하다.

2.5) Multi-Layer Perceptron

위에서 언급했듯이, 단일 perceptron으로 만드는 Single-Layer Perceptron은 linear boundary만 생성하므로 XOR Gate를 구현할 수 없었다.

다만, 여러 Perceptron을 층을 쌓아 만드는 Multi-Layer Perceptron(MLP)는 Linear boundary를 여러 개 생성할 수 있어, XOR Gate를 표현할 수 있다.

우선, XOR Gate를 해결하는 방법은 잠시 뒤에 살펴보도록 하고, 우선 XOR Gate 문제를 다른 관점에서 생각해보자.

XOR Gate를 구현하는 방법은 다양하다. 그 중 하나는 AND, NAND, OR Gate를 조합하는 방법이다.

$$x \oplus y = xy' + x'y = (x+y)(x'+y')$$

XOR Gate는 다음과 같이 OR Gate와 NAND Gate를 AND Gate로 연결하여 구현할 수 있다.

Input Signal $x_1, x_2$에 대해 Output Signal을 Truth Table로 작성해보면 기존 XOR Gate와 동일한 것을 알 수 있다.

그렇다면 이제 XOR Gate를 NAND, OR Gate 그리고 AND Gate를 이용하여 코드로 구현해보자.

def XOR(x1, x2):
    return AND(NAND(x1, x2), OR(x1, x2))

print(XOR(0, 0)) # 0 
print(XOR(1, 0)) # 1
print(XOR(0, 1)) # 1
print(XOR(1, 1)) # 0

위와 같이 간단하게 Python으로 XOR Gate를 구현할 수 있다.

XOR Gate는 Multi-Layer Perceptron으로 구성된 다층 구조의 Network이다.

XOR Gate는 AND, OR Gate가 Single-Layer인 것에 비해, 2층으로 구성된 Multi-Layer Percetpron이다.

실제로 위의 그림에서는 3개의 Layer로 구성된 MLP지만, weight을 갖는 Layer는 사실 2개 (0층과 1층 사이, 1층과 2층 사이) 뿐이니 2층 Perceptron이라고 하자.


문헌에 따라서는 구성 층의 개수를 기준으로 하거나, weight을 갖는 layer의 개수를 기준으로 할 수도 있다.

이처럼 층이 여러 개인 Perceptron을 우리는 Multi-Layer Perceptron: MLP라 부른다.

즉, 2층 구조를 사용하면 Perceptron으로 XOR Gate를 구현할 수 있게 된다.

이는 Linear Boundary를 아래 사진과 같이 하나 더 추가하여 총 2개의 Hyperplane으로 $(x_1, x_2)$를 성공적으로 separate할 수 있다.

이는 Single Layer Perceptron으로는 표현하지 못한 것을 층을 하나 늘려 구현할 수 있었기에, MLP는 Deep하게 Layer들을 쌓아(Non-linear boundary) 더 다양한 것을 표현할 수 있다.

MLP는 지금까지 보아온 회로보다 더 복잡한 회로를 만들 수 있다.

예를 들어, 덧셈을 처리하는 가산기도 만들 수 있고, 2진수를 10진수로 변환하는 Encoder, 어떤 조건을 충족하면 1을 출력하는 회로 (parity 검사 회로)도 perceptron으로 표현할 수 있다.

즉, Perceptron을 잘 이용한다면 Computer 까지 표현할 수 있게 된다.

Computer는 정보를 처리하는 기계이기 때문에, 무언가를 input으로 넣어주면 정해진 방법으로 처리하고 해당 output을 출력한다.

즉, 정해진 방법으로 출력한다는 것은 Computer도 마치 perceptron 처럼 input과 output으로 구성된 특정 규칙대로 계산을 수행한다는 뜻이다.

놀라운 사실은, NAND Gate의 조합만으로도 컴퓨터가 수행하는 일을 재현할 수 있다는 것이다. Perceptron으로 NAND Gate를 구현할 수 있기에, 이는 Perceptron을 이용하여 Computer의 기능들을 구현할 수 있다는 뜻이다.

이것이 어떻게 가능한지에 대해서는 아래의 링크에 첨부한 책을 읽어보면 된다. 이 책은 NAND로 테트리스가 작동하는 컴퓨터를 만드는 방법을 설명하고 있다.

The Elements of Computing Systems: Building a Modern Computer from First Principles: Nisan, Noam, Schocken, Shimon: 9780262640688: Amazon.com: Books

The Elements of Computing Systems: Building a Modern Computer from First Principles [Nisan, Noam, Schocken, Shimon] on Amazon.com. *FREE* shipping on qualifying offers. The Elements of Computing Systems: Building a Modern Computer from First Principles

Follow

단순히 NAND라는 단순한 소자만으로 컴퓨터와 같은 복잡한 system을 구현할 수 있다는 것이다.

그렇다면 몇 개의 Layer로 구성된 Perceptron을 이용하여 Computer를 표현할 수 있을까?

이론상으로는 2-Layer Perceptron이면 Computer를 만들 수 있다.

• 2-Layer Perceptron은 1 Hidden-Layer Perceptron과 동일하다.
• 이는 Universal Approximation Theorem에서 자세하게 설명되어 있다.
• Existence에 대한 이론이지, Optimal이나 그렇게 Training된다는 보장은 없다.

1개의 hidden layer만 있어도 arbitrary continuous function $f$를 구현할 수 있다.

그러나 2-Layer Percetpron 구조에서 weight을 적절히 설정하여 Computer를 만들기란 너무 어렵다. 실제로도 NAND 등의 저수준 소자에서 시작하여 Computer를 만드는데 필요한 module을 단계적으로 만들어가는 쪽이 자연스러운 방법이다.

즉, 처음에는 AND와 OR Gate, 그 다음에는 Half Adder와 Full Adder, 그 다음에는 ALU, CPU로 순서대로 구현한다.

따라서 perceptron으로 표현하는 Computer도 multi-layer를 이용하여 다시 층층이 겹친 구조로 만드는 방향이 자연스러운 흐름이다.

2.7) 정리

Chapter 2에서는 perceptron에 대해 배웠다. Perceptron은 간단한 알고리즘으로 그 구조를 쉽게 이해할 수 있으며, 이는 Chapter 3에서 배울 Neural Network의 기초가 된다.

이번 장에서 배운 내용들은:

• Perceptron은 Multiple Input Singal을 받아서 Single Output Signal을 출력하는 Algorithm이다.
• Perceptron은 weight $\mathbf{w}$와 bias $b=w_0$를 parameter로 설정한다.
• Perceptron으로 AND, OR, NAND Gate등의 Logic Gate를 구현할 수 있다.
• XOR Gate는 single-layer perceptron으로는 표현할 수 있다.
• Single-Layer Perceptron은 linear boundary만 표현가능하며, Multi-Layer Perceptron은 nonlinear section도 표현가능하다.
• MLP는 이론상 2-layer (1 hidden layer)로 구성되어 있어도 Computer를 표현할 수 있다