2015년 10월 31일 토요일

퍼셉트론

1)퍼셉트론
퍼셉트론은 인간의 신경세포인 뉴런을 매우 단순히 모사하여 계산 가능한 형태로 만든 알고리즘이다.


퍼셉트론이 하는 일, 국어, 영어, 수학점수, 반영률이 50%, 80%, 30%이라해서
그렇게 가중치를 곱해서 합산한 점수가 100점을 넘으면 시험에 합격하는 것,
이를 수식으로 표현하면,

이때 철수가 시험에서 각각 60, 70, 80점을 받았다면, 가중치 합의 값은
110 = 60*0.5 + 70*0.8 + 80*0.3
으로 100보다 크기 때문에 합격했다고 할 수 있다.

퍼셉트론은 이처럼 선형 분리가능(가중치 합을 이용해 분리가능) 문제를 풀 수 있는 아주 심플한 알고리즘입니다.



2) 비선형 분리 문제


위 그림에서 왼쪽은 비선형 분리가능 문제이고, 오른쪽 그림은 선형 분리가능 문제입니다.
말 그대로 직선만으로 구분이 가능한가, 곡선이 있어야만 구분이 가능한가가 이 둘의 차이입니다.

앞서 살펴본 것과 같이, 퍼셉트론은 선형 분리문제를 풀 수 있는 알고리즘이었습니다.
따라서 성적을 다 더해서 합격, 불합격을 결정하는 아주 쉬운 문제는 풀 수 있었지만
내일 비가 올지 안 올지, 내일의 주가가 오를지 내릴 지와 같은 매우 어려운 문제들은
대부분 비선형 분리가능 문제로 단층 퍼셉트론으로는 풀 수 가 없었습니다.

과거에는 XOR문제라는 가장 간단한 비선형 분리가능 문제가 퍼셉트론의 한계라는 연구가 나오면서 한 때 인공신경망 연구에 겨울이 오기도 했었습니다.



위처럼 XOR 1이 한 개 일때에만 1을 내보내는 굉장히 단순한 문제임에도 불구하고 직선 하나로는 0 1을 나눌 수 없는 문제입니다.



3) 다층 퍼셉트론

그런데 이러한 비선형 분리가능 문제를 여러 층의 퍼셉트론을 쌓으면서 해결할 수 있다는 사실이 알려지면서 또 다시 인공신경망연구가 활발해지기 시작했습니다. 다층퍼셉트론은 간단히 말해
직선을 여러 번 그어서 비선형 분리가능 문제를 해결하려는 개념으로 생각할 수 있습니다.

그래서 이처럼 여러 개의 퍼셉트론을 여러층으로 쌓을 경우 굉장히 복잡한 문제도 해결할 수 있게 된 것.



-관련 키워드
패턴인식, 기계학습, 다층 퍼셉트론을 이용한 XOR 문제 해결, 딥러닝
-Reference
http://blog.naver.com/2011topcit/220510759079

2015년 10월 24일 토요일

P-NP문제


 File:Complexity classes.png

Pnp에 속하지만, npp에 속하는지는 밝혀지지 않았다.
P결정론적 튜링 기계다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이다.
NP비결정론적 튜링 기계(NTM)다항 시간 안에 풀 수 있는 판정 문제집합

비결정론적 튜링 기계(nondeterministic Turing machine, NTM)튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말한다. 이것은 비결정론적 유한 오토마타와 유사한 개념이다.
이동 가능성이 하나로 정해져 있는 결정론적 튜링 기계와는 반대로, 이 기계에서 이동할 수 있는 상태의 개수는 상황에 따라 다르며, 여러 개가 되거나 아예 없을 수도 있다.

 

NTM으로, TM을 나타낼 수 있다. NTM의 무수한 상태이동 경로중 TM의 상태이동경로가 있을 것이기 때문에, TM으로 NTM의 이동경로를 나타낼 수 있는가?
NTM중에는 확률적 튜링 기계(Probabilistic Turing machine, 비결정론적 튜링 기계의 하나로, 기계의 다음 상태가 확률적으로 정해지는 성질을 가진다.)도 있다.

PTM에서 A상태에서 B,C,D로 갈 확률이 각각 30%라고 하자, 이것을 TM으로 구현해 내는 것이 가능한가? TM에서는 A의 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있다. 원천적으로 이동하는 하나의 상태가 정해진 이상 나머지 상태로 갈 가능성은 차단된다. 이렇게만 판단하면, TM으로 PTM를 구현할 수 없다.

PTM TM을 구현할 수는 있나?, A상태에서 다른상태로 이동하는 TM의 경로를 A상태에서 확률적으로 포함시키면 되기에, PTMTM을 포함시킨다. 즉 비결정론적 튜링기계는 결정론적 튜링기계를 자신의 내부에 포함시킨다.

TM으로 다항시간 안에 풀 수 있는 판정문제는, NTM으로도 다항시간 안에 풀 수 있다고 증명이 되었다고 한다. 문제는 NTM으로 다항시간 안에 풀 수 있는 모든 문제들이, TM으로 다항시간 안에 풀 수 있느냐 하는 것. 단순히 생각을 해보았을 떄, TM으로 NTM을 구현해내지 못해내니, TM으로 다항시간안에 못풀어 내는 NTM이 있을 것 같다.

언뜻 단순해 보이는데, 이게 단순하다면 왜 그렇게 많은 사람들이 NP=P가 아니라는 것을 증명해내지 못한걸까? 그것은 단 하나의 Np complete문제도 P problem에 포함되거나, 포함되지 않는 것을 증명해내지 못했기 때문이다.

왜 어려울 수 밖에 없는가? P problem과는 달리, NP complete는 비결정론적 튜링머신으로 판정하는 문제이므로 일반적인 해법이 있을 수가 없기 때문이다. 퍼지이론과 같이 애매한 것을 정량화 시키는, , 일반적이지 않은 것을 일반적으로 다루려는 기법들이 있으나, NTM의 본질적인 특성상 일반적인 해법을 찾는 것은 역시 불가능한 시도 같다.

NP-완전(NP-complete, NP-C, NPC)NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제 P=NP의 형태로 풀리게 된다. 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 PNP의 형태로 풀리게 된다.

PNP에 속하기에 P, NP로 환원할 수 있으며, 모든 NP문제는 NP complete로 환원될 수 있다,즉 모든PNP complete로 환원되어 진다. 다시 말해 문제의 키 포인트는 NP completeP로 환원될 수 있느냐 없느냐 하는 것, NP completeP로 환원되어 진다면, NP complete, TM으로 다항시간안에 풀어 낼 수 있게된다. , NPcompleteP로 환원되어지기 위해서는 NTM으로 다뤄지는 문제가 TM의 문제로 환원되어져야 한다는 것이고, 이것은 NP문제에 일반적인 해법이 있음을 의미한다.

소수를 찾는 일반적인 해법이 존재한다면, NTM문제가, TM문제로 환원되고, 다항시간안에 답이 도출된다는 것을 의미한다. 결국 NP completeP에 속하게 되어 NP=P가 성립하게 된다. 소수의 일반적인 해법을 찾으려는 시도는 전부 NP=P임을 증명하기 위한 시도와 같다.

 

-reference
https://ko.wikipedia.org/wiki/P-NP_%EB%AC%B8%EC%A0%9C

-연관 키워드
복잡도, 결정문제, 오토마타, 리만가설, 해석적 정수론, 휴리스틱, 리만제타함수, 원자론, 양자역학