XOR 문제

XOR Problem

퍼셉트론의 선형분리 학습 메커니즘으론 XOR을 결과를 학습시킬 수 없는 문제

• 오랫동안 풀리지 않아 AI의 침체기(AI 겨울)을 불러온 문제

• 민스키 박사가 1969년에 현재의 방법으론 XOR 문제를 해결 할 수 없음을 수학적으로 증명
  • MLP(Multilayer Neural Networks)를 통해 해결 가능 함을 제안
  • 그러나 MLP는 학습시킬 수 없는 모델이라는 가설 제시

▶

• 민스키 박사의 논문 이후 많은 연구자들이 AI 연구 포기
  • 10년동안 진전이 거의 없음 = AI 겨울

단층 퍼셉트론이 풀 수 있는 것과 없는 것

퍼셉트론 하나는 입력에 가중치를 곱해 더한 값이 임계값을 넘으면 1, 아니면 0 을 내는 계단 함수를 활성화 함수로 쓴다. 이 출력은 입력 공간을 직선(초평면) 하나로 둘로 가르는 것과 같다. 따라서 0 과 1 을 직선 하나로 나눌 수 있는(선형 분리 가능한) 논리 연산만 학습할 수 있다.

x1	x2	AND	OR	NAND	NOR	XOR
0	0	0	0	1	1	0
0	1	0	1	1	0	1
1	0	0	1	1	0	1
1	1	1	1	0	0	0

연산	선형 분리	단층 퍼셉트론(계단 함수)
AND	가능	구현할 수 있다
OR	가능	구현할 수 있다
NAND	가능	구현할 수 있다
NOR	가능	구현할 수 있다
XOR	불가능	구현할 수 없다

XOR 은 (0,1)·(1,0) 이 1, (0,0)·(1,1) 이 0 이어서 같은 값끼리 대각선으로 놓인다. 어떤 직선을 그어도 두 무리를 가를 수 없다. 계단 함수를 쓰는 단층 퍼셉트론이 수행하지 못하는 논리 문제는 XOR 하나이며, AND·OR·NAND·NOR 는 모두 가능하다.

다층으로 해결

선형 분리 가능한 연산을 층으로 쌓으면 XOR 을 만들 수 있다.

XOR(x1, x2) = AND( NAND(x1, x2), OR(x1, x2) )

첫 층에서 NAND 와 OR 을 각각 계산하고, 둘째 층에서 그 결과를 AND 로 묶는다. 이렇게 은닉층을 둔 구조가 멀티 레이어 퍼셉트론이다. 다층 신경망을 실제로 학습시키는 방법은 1986년 무렵 역전파 알고리즘이 널리 알려지면서 해결되었다.

같이 보기

• 퍼셉트론
• 멀티 레이어 퍼셉트론
• 활성화 함수
• 역전파
• 인공 신경망
• 논리 연산