Perceptron, Multi-layer perceptron, Back-propagation algorithm

Perceptron

위쪽이 사람의 신경을 나타내는 것이고, 아래쪽이 Perceptron을 나타내는 그림이다.

- 사람의 신경을 본떠 만든 perceptron은 input층, 중간 처리 과정층, output층이 존재한다.

Perceptron: the limit

XOR problem

Perceptron은 어떠한 직선으로도 XOR 문제를 해결할 수가 없다.

Solution?

차원 변환(좌표축 변환, 좌표평면 변환)

이를 통해 선형 분류가 가능해진다.

Multi-layer Perceptron(MLP)

은닉층 (Hidden layer)

겉으로 보이지 않는 내부의 변환과정을 수행하는 layer

은닉층에서의 변환과정으로 1차로 분류되지 않던 문제가 가능해짐

총 3개의 Perceptron으로 구성

• 갈색 점선으로 감싸진 은닉층은 Perceptron의 Perceptron이므로 중간과정을 정확하게 모를 수도 있다.(어떤 입력이 들어올 지, 어떤 출력이 나갈지)
• 은닉층의 수가 많아질수록, 차원이 변화되는 느낌을 더 많이 줄 수 있다.

Back-propagation(BP)

어떠한 $w$와 $b$를 사용해야 할 지 알 수 없는 문제가 존재
신경망 성능의 비결: 오차(오류) 역전파 알고리즘

• 신경망 내부의 가중치는 오차 역전파 방법을 사용해 수정(학습)함
• 오차 역전파는 경사 하강법의 확장 개념

How?

• 가중치를 구하는 방법은 경사 하강법과 동일
• 임의의 가중치를 선언하고 결과값을 이용해 오차를 구한 뒤, 오차가 최소인 지점으로 계속해서 이동
• 오차가 최소가 되는 점(미분했을 때 기울기가 0인 지점)을 찾으면 종료

BP for Perceptron

실제 값과 예측 값의 오차를 통해 가중치를 수정

• 처음 $W$는 임의의 random한 값 $\rarr$ 이후 BP를 통해 수정

BP for Multi-layer Perceptron

• 오차에 대한 가중치의 수정이 역으로 전파된다.

오차 역전파 구동 방식
1. 임의의 초기 가중치($w$)를 준 뒤 결과($y_{out}$)를 계산
2. 계산 결과와 우리가 원하는 값 사이의 오차를 구함
3. 경사 하강법을 이용해 바로 앞의 가중치(바로 직전의 은닉층)를 오차가 작아지는 방향으로 수정
4. 위 과정을 더 이상 오차가 줄어들지 않을 때까지 반복

• 새 가중치는 현 가중치에서 '가중치에 대한 기울기'를 뺀 값
  $W(t+1)=W_t-\frac{\partial_{오차}}{\partial W}$

신경망 학습 과정

MLP in detail

Perceptron

은닉층에서 가중치 합과 활성화 함수를 사용

• Threshold logic unit(TLU)
• TLU는 inputs의 가중합을 계산
  input이 n개인 경우, $z=w_1x_1+w_2x_2+\cdots+w_nx_n=x^Tw$
  $\Rightarrow\,h_w(x)=step(z),\,where\,z=x^Tw$

  

Step function위와 같은 형태로, $z$가 0보다 큰 시점부터 $y$값의 변화가 생기고, 0보다 작은 시점에서는 $y$값의 변화가 없다.
$\Rightarrow$ 가중치합을 인자로 받아, 어느 정도 이상의 가중치합($\sum$) 값이 나와야만 유의미한 $y$값의 변화가 존재함을 의미, 분류를 위해 사용

• input과 output으로 두 개의 layers 존재
  • 위와 같이 모든 노드가 연결되어 있는 경우, Fully connected layer or Dense layer
• Bias neuron:
  • 항상 1을 출력
  • TLU(sigma)들에 강제적으로 1을 더함 $\Rightarrow$ 전체 output값이 threshold를 넘기게 될 수도 있고 넘지 않을 수도 있다.
• single perceptron
  • $h_w(x)=step(z),\,where\,z=x^Tw$
• Perceptron with bias neuron
  • $h_{W,b}(X)=\phi(XW+b)$
  • $X,W$는 matrix, $b$는 vector, $\phi$는 활성화 함수를 의미

어떻게 Perceptron이 학습하는가?

• 학습의 목표
  • 에러를 최소화하는 $W$를 변경하는 것이 목표
  • Perceptron learning rule(weight update):
    ${w_{i,j}}^{(next\,step)}=w_{i,j}+\eta(y_j-\hat y_j)x_i$
  • $w_{i,j}$는 bias를 포함한 가중치 matrix
  • $\eta$는 learning rate을 의미, 증가할수록 오차의 반영률이 증가
  • $(y_j-\hat y_j)$는 오차, $x_i$는 input
• MLP는 layer로 구분했을 때,
  • input layer (1개), hidden layer (여러 개 가능), output layer (1개)로 구분 가능
• output layer를 제외한 모든 layer는 다음 layer와 fully connected

DNN

hidden layers가 더 많아진다면 Deep Neural Network(DNN)를 구성

BP training algorithm

• gradients를 자동으로 계산하는데 효율적인 기법을 사용하는 Gradient Descent이다.

Gradient Descent
일반적인 최적화 알고리즘

특정 learning step을 반복하면서 cost가 최소가 되는 지점(즉, 미분 값이 0인 지점)을 찾기 위해, 해당 방향으로 가중치를 update하는 기법

• 에러를 최소화하는 것이 목표이고, 가중치와 bias를 변경해야 한다.
• 궁극적으로는, 최선책을 찾을 때까지 반복

1) mini-batch 방법을 사용하여 특정 sample마다 update를 진행
2) Forward pass: (순방향 진행)

• input들을 신경망에 투입(이때 $w,b$는 random), input layer $\rarr$ hidden layers $\rarr$ output layer
• predictions(예측값)이 생성

3) 예측 값과 실제 값을 비교하여 에러를 계산
4) 어떤 connection이 에러에 큰 영향을 줬는지 계산하면서 connection에 대한 가중치를 update
5) backpropagation: 1 layer에 대한 가중치 update가 완료되면, backward로 직전 layer에 변경사항을 전달
6) 가중치 update를 반복하면서 최종적으로 parameter($w,b$)를 수정

But for BP

• 해당 알고리즘이 잘 작동하기 위해서는, step function을 대체해야 한다.
  • gradient descent를 위해서는 편미분을 해야하는데, step function의 경우 모든 점에서 미분 가능한 것(즉, gradient계산 불가능)이 아니기 때문에, 모든 점에서 미분이 가능한 logistic(sigmoid) function으로 대체해야 한다.
  • $\sigma(z)=1/(1+exp(-z))$

Popular activation functions

---

Perceptron in Math

Perceptron

구조

Perceptron의 구조

• bias는 정확하게는 input이라고는 할 수 없다.
• step function을 활성화 함수로 사용

동작

Perceptron의 동작

• 해당하는 특징 값과 가중치를 곱한 결과를 모두 더하여 $s$를 구하고, 활성화 함수$\tau$를 적용
• step function을 사용하기에 최종 출력은 $y$는 +1 or -1
• $w_0$: bias
  $y=\tau(s)\\ 이때\,s=w_0+\sum^d_{i=1}w_ix_i,\quad\tau(s)=\begin{cases}\,\,\,\, 1\quad s\geq0\\-1\quad s<0\end{cases}$

행렬 표기

$s=w^Tx+w_0,$ 여기서 $x=(x_1,x_2,\cdots,x_d)^T,\,w=(w_1,w_2,\cdots,w_d)^T$

• bias 항을 추가하면,

$s=w^Tx,$ 여기서 $x=(1,x_1,x_2,\cdots,x_d)^T,\,w=(w_0,w_1,w_2,\cdots,w_d)^T$

최종적으로, $y=\tau(w^Tx)$, $y$는 예측값 또는 출력값, $\tau$는 step funciton, $w^Tx$는 가중치합

학습

목적함수 설계

이를 잘하는 것이 ML의 목표
$J(w)$로 표기 (perceptron의 매개변수를 $w=(w_0,w_1,w_2,\cdots,w_d)^T$라 표기하는 경우)
목적함수의 조건

• $J(w)\geq0$: 미분이 가능하기 위함
• $w$가 최적이면, 즉 모든 sample을 맞히면 $J(w)=0$
• 틀리는 sample이 많은 $w$일수록 $J(w)$는 큰 값을 가진다. (=cost가 증가)

위 3가지 조건을 만족하므로, 아래의 식은 목적함수로 적합하다.

Y는 w가 틀리는 sample의 집합

Gradient 계산

이는 편미분을 하겠다는 의미

• $\theta = \theta-\rho g$ ($\rho$는 learning rate, g 반영률)를 위해서는 Gradient $g$가 필요
• 위에서 구한 목적함수를 편미분하면,를 얻을 수 있고, 이는 $g$가 된다. 이를 대입하면,
• $\theta = \theta-\rho g\,\Rightarrow$

perceptron 학습 알고리즘

• 위의 학습 알고리즘을 사용하면, 훈련집합의 sample을 모두 맞출(즉 $Y=\empty$) 때까지 세대(line 3~9)를 반복
  • batch 기반의 학습 $\rarr$ 틀린 sample을 모아서 한 번에 학습

perceptron 학습 알고리즘의 스토캐스틱 버전

• sample 순서를 섞음. 틀린 sample이 발생하면 즉시 update

Multi Layer Perceptron

• Perceptron은 선형 분류기라는 한계
  • XOR문제에 대한 선형 분리가 불가능 (75%가 정확도의 한계)

특징 공간 변환

• Perceptron 2개를 사용한 XOR문제의 해결 $\larr$ 직선 하나로는 불가능
  • Perceptron 1가 2가 모두 +1이면 $\bullet$ 부류이고 그렇지 않으면 $\square$ 부류로 판단

• Perceptron 2개를 병렬로 결합하면,
  • 원래 공간 $x=(x_1,x_2)^T$를 새로운 특징 공간 $z=(z_1,z_2)^T$로 변환
  • 새로운 특징 공간 $z$에서는 선형 분리 가능함
  • 사람이 수작업으로 특징(feature) 학습을 수행한 셈

• Perceptron 1개를 순차 결합하면,
  • 새로운 특징 공간 $z$에서 선형 분리를 수행하는 Perceptron 3을 순차 결합하면, Multilayer Perceptron

이는 아래의 Stacking 기법과 유사하다.

• 다층 Perceptron의 용량

  

  • 3개의 Perceptron을 결합하여 빗금친 영역에 대한 분류도 가능해짐
  • Perceptron 개수가 증가하면 분할 가능한 영역의 수도 증가하고, 더 다양한 특징에 대한 분류가 가능해진다.
  • 일반화하여, $p$개 Perceptron을 결합하면 $p$차원 공간으로 변환
    • 1 + $\sum^p_{i=1}i$개의 영역으로 분할
      • $p$가 클수록 신경망의 용량이 커짐 $\rarr$ 하지만 너무 커지게 되면 Overfitting 가능성도 커짐

활성화 함수

• 신경망이 사용하는 다양한 활성화함수
  • step function: 모든 값이 미분 가능하지 않음
  • Logistic sigmoid
  • Hyperbolic Tangent function
  • Softplus
  • ReLU: 0보다 작으면 0, 0보다 크면 input값
• 딱딱한 공간 분할과 부드러운 공간 분할

  

구조

• 입력층-은닉층-출력층의 2층 구조
  • $d+1$개의 입력노드($d$는 특징의 개수, bias까지 포함), $c$개의 출력노드($c$는 부류 개수)
  • $p$개의 출력노드($p$는 hyperparameter(사용자 지정 매개변수))
    • $p$가 너무 크면 Overfitting, 너무 작으면 Underfitting
• 입력층-은닉층-은닉층-출력층의 3층 구조

Multi Layer Perceptron의 매개변수(가중치)

위 그림과 아래 행렬 표현식의 색을 맞춰보면 이해될 것이다.

• $U_1$는 입력층-은닉층을 연결
• $U_2$는 은닉층-출력층을 연결
• $u^1_{pd}$: 은닉층의 $p$번째 출력 노드와 입력층의 $d$번째 입력노드를 연결
• $u^2_{kj}$: 출력층의 $k$번째 출력 노드와 입력층의 $j$번째 입력노드를 연결

동작

특징 벡터 $x$를 출력 벡터 $o$로 매핑하는 함수로 간주할 수 있음

• 2층 Perceptron: $o=f(x)=f_2\big(f_1(x)\big)$
  • $f_2$: 2번째 hidden 층, $f_1$: 첫번째 hidden, $x$: input
• 3층 Perceptron: $o=f(x)=f_3\Big(f_2\big(f_1(x)\big)\Big)$
• 층이 4이상이 되면 딥러닝

노드가 수행하는 연산

Multi Layer Perceptron의 동작을 행렬로 표기
$o=\tau(U^2\tau_h(U^1x))$

은닉층은 특징 추출기(extractor)
인간이 보지 못하는 특징을 추출

오차 역전파 알고리즘

목적함수의 정의

목적함수

• 평균 제곱 오차(MSE: Mean Squared Error)로 정의
• 온라인 모드: $e=\frac{1}{2}||y-o||^2_2$
• 배치 모드: $e=\frac{1}{2n}\sum^n_{i=1}||y_i-o_i||^2_2$

알고리즘 설계

새로운 가중치를 어떻게 반영하느냐?

• 2층 Perceptron의 경우, $\theta=\{U^1,U^2\}$
  $J(\theta)=\frac{1}{2}||y-o(\theta)||^2_2$
• $J(\theta)=J(\{U^1, U^2\})$의 최저점을 찾아주는 경사 하강법 (GD)
  $U^1=U^1-\rho\frac{\partial J}{\partial U^1}\\\ \\ U^2=U^2-\rho\frac{\partial J}{\partial U^2}$

  

오차 역전파의 유도

• $U^2$를 구성하는 $u^2_{kj}$로 미분하면,(다음 층인 출력층에서 $k$번째 노드만 $u^2_{kj}$의 영향을 받기 때문에 나머지 노드는 상수취급이 가능)

  

  • 활성화 함수를 무엇으로 정하느냐에 따라 미분이 달라진다. (Step function은 모든 점에서 미분이 가능하지 않아서 사용하지 않는다.)

유도한 식 모두 정리

$osum_k$는 변수로 저장해놓으면, 매 노드마다 반복되는 $U_2$(GD)를 다시 계산할 필요가 없다.

위와 같이 행렬 표기를 사용하는 경우
GPU를 사용한 고속 행렬 연산에 적합하고, 병렬화를 통해 속도가 향상된다.
(GPU가 훨씬 더 빠른 학습 속도를 가진다.)

Mini-batch 스토캐스틱 경사 하강법

Mini-batch 방식

"SGD: 매 sample마다 update를 수행하면 오래 걸린다."
"BGD: 모든 sample에 대해 기다렸다가 한 번에 처리하는 것도 오래 걸린다."

• Mini-batch는 한 번에 $t$개의 sample을 처리한다.
  • $t=1$이면, 스토캐스틱 경사 하강법
  • $t=n$이면, Batch 경사 하강법
• GPU가 없거나 성능이 좋지 않은 경우, 한 sample마다 update하는 방식인 스토캐스틱 경사 하강법이 더 좋을 수 있다.

  

Multi Layer Perceptron의 특성

오차 역전파 알고리즘의 속도

• 오차 역전파 알고리즘은 Forwardpass보다 약 1.5~2배의 시간이 소요된다. (많은 계산이 필요하기 때문)

성능 향상을 위한 휴리스틱의 중요성

• hidden layer의 개수, node의 개수를 지정하는 것이 중요(Architecture)
• 가중치의 초기값 설정
• 학습률: 학습률이 크면 변화폭이 커짐
• 활성화 함수를 무엇으로 하느냐에 따라 미분값이 달라진다.