Artificial Neural Networks 2014-1 Data Mining발표 Artificial Neural Networks 2014.04.28 Hyukjin Kwon

Contents Neural Network? History of Neural networks A simple example Biological Neural Network / Artificial Neural Network Some Simple Neural Network Models Other representative model Application areas

Neural Network?

Neural Network? 인간의 두뇌와 신경 세포 모델에 대한 연구에서 시작. 가장 기본적인 단위는 뉴런이라는 세포. 각각의 뉴런은 신경 시스템에서 여러 가지 기능적인 역할을 담당 ‘ connectionist models’ or ‘parallel distributed processing’ 으로도 불림. Derived from., 사고를 생성하는 인간의 두뇌를 분석하고, 이를 처리 메커니즘으로 규명한다면! 생각하는 기계를 만들 수 있지 않을까 하는 아이디어에서 출발한 이론 기존 방식 절차적인 순서에 의한 알고리즘을 통해 기호를 처리하여 문제를 해결 신경망 이론(기존 방식과 차이) 인간의 두뇌 신경조직을 모델로 하여 단순한 기능을 하는 처리기(신경세포)들을 대규모로 상호 연결한 다음 연결 강도를 조절하여 문제를 해결

History of Neural networks

History of Neural networks McCulloch, Pitts., 1943 인간의 두뇌가 수 많은 신경 세포들로 구성된 잘 정의된 컴퓨터라 생각, 신경 세포의 신호 처리 과정을 모형화하여 단순한 패턴 분류 모형을 개발 신경망 최초의 수학적 모델을 제안 뉴론(neuron : 신경 세포)이 하나의 처리 단위로서의 계산 기능만을 중시,학습 기능에 대해서는 도외시 Hebb., 1949 뉴런의 시냅스(synapse : 신경 연접)에서 일어나는 상관 학습에 관하여 기술 (저서“The Organization of Behavior") ”Hebb의 학습 규칙“이라는 신경망 학습 규칙을 개발 뉴런에서 일어나는 학습 방법을 관찰함으로써 규칙: ”만약 뉴런 A가 뉴런 B의 활성화에 반복적으로 기여한다면, 뉴런 B를 활성화시키는데 있어서 뉴런 A의 효용성은 증가한다“ 학습에 관한 연구를 크게 발전, 적응적인(adaptive) 신경망 연구에 많은 영향 정리 1943 : 인공 신경망 모델 1949 : 학습 규칙 1958 : 퍼셉트론 모델 1960 : 델타 학습 규칙 1969 : 퍼셉트론의 한계 입증 1970 후반 : PDP 그룹 결성, 신경망 연구 부흥 1980 초반 : 은닉층 모델, 오류 역전파 알고리즘 제안, 홈필드 모델, SOM, ART 1987 : IEEE 국제 학술제의 개최, 국제 신경망 학회(INNS) 조직

History of Neural networks Rosenblatt.,1958 신경망 모델 ‘퍼셉트론(perceptron)’ 을 제안 패턴을 인식하기 위하여 학습 기능을 이용함으로써 당시 큰 기대 수학적 분석과 디지털 컴퓨터를 사용한 시뮬레이션 방법을 병행 이의 등장으로 많은 학자들이 신경망의 연구에 관심을 갖게 됨 Minsky, Papert., 1969 퍼셉트론 모델을 수학적으로 철저히 분석 퍼셉트론이 XOR 함수와 같이 단순한 선형 분리 문제를 풀 수 없음을 밝혀내면서 신경망에 관한 연구는 침체 (저서 “Perceptrons“) Grossberg, Willshaw, Amari, Anderson, Kohonen etc., In the late 1960s-In the early 1970s 사람 눈의 움직임을 모방한 신경망, 분산 기억 모델의 수학적 분석, 선형 연상 기억 장치, 자기-조직화 연상 기억 장치 등에 관한 독자적 연구를 계속. 정리 1943 : 인공 신경망 모델 1949 : 학습 규칙 1958 : 퍼셉트론 모델 1960 : 델타 학습 규칙 1969 : 퍼셉트론의 한계 입증 1970 후반 : PDP 그룹 결성, 신경망 연구 부흥 1980 초반 : 은닉층 모델, 오류 역전파 알고리즘 제안, 홈필드 모델, SOM, ART 1987 : IEEE 국제 학술제의 개최, 국제 신경망 학회(INNS) 조직

History of Neural networks Rumelhart, McClelland., In the late 1970s PDP(Parallel Distributed Processing) 그룹을 결성 신경망에 대한 연구가 다시 부흥되기 시작 In the early 1980s 입력층과 출력층 사이에 한 개 이상의 은닉층(hidden layer)을 둔 모델이 등장 퍼셉트론에서처럼 하나의 조정층(adjustable layer)을 갖는 모델의 한계점을 극복하기 위한 방법 특히, PDP 그룹에서 은닉층 (hidden layer), 오류 역전파(error back propagation) 학습 알고리즘을 제안 선형 분리 문제뿐 만 아니라, 그 외의 여러 가지 문제들을 해결할 수 있는 계기를 마련 신경망에 대한 연구가 다시 활성화 In the late 1980s Hopfield network (Hopfield ) Neocognition (Fukushima) Boltzmann 머신 (Hinton) RCE(Restricted Coulomb Energy) 네트워크 (Cooper, Elbaum) SOFM(Self Organization Feature Map) (Kohonen) And so on.. 현재까지 다양한 분야에서 신경망에 대한 연구와 응용이 진행. 정리 1943 : 인공 신경망 모델 1949 : 학습 규칙 1958 : 퍼셉트론 모델 1960 : 델타 학습 규칙 1969 : 퍼셉트론의 한계 입증 1970 후반 : PDP 그룹 결성, 신경망 연구 부흥 1980 초반 : 은닉층 모델, 오류 역전파 알고리즘 제안, 홈필드 모델, SOM, ART 1987 : IEEE 국제 학술제의 개최, 국제 신경망 학회(INNS) 조직

A simple example

A simple example of learning A very simple way to recognize handwritten shapes Consider a neural network with two layers of neurons. top layer의 뉴런은 알려진 모양을 나타낸다. bottom layer의 뉴런은 pixel intensities(픽셀의 강도)를 나타낸다. A pixel gets to vote if it has ink on it. Each inked pixel can vote for several different shapes. The shape that gets the most votes wins.

A simple example of learning How to display the weights The input image 1 2 3 4 5 6 7 8 9 0 각 출력 유닛에 입력 이미지의 map을 지정하고, Map에 해당 픽셀에서 각 픽셀에서부터 전달되는 Weight를 표시한다 Weight의 크기와 신호를 표시하는 색을 표현하는 영역에 검정과 흰색 칠(blob)을 사용한다.

A simple example of learning How to display the weights The image 1 2 3 4 5 6 7 8 9 0 각 네트워크에 이미지를 보여주고 active 픽셀에서 올바른 클래스에 weight를 증가시키고 그렇지 않은 클래스는 active 픽셀에서 weight를 감소시킨다.

A simple example of learning How to display the weights

A simple example of learning How to display the weights

A simple example of learning How to display the weights

A simple example of learning How to display the weights

A simple example of learning How to display the weights

A simple example of learning The learned weights 잉크와 가장 오버랩 많이 되는 템플릿이 출력값으로 표시. Hand-written digits(손으로 쓴 숫자)을 다루는 방법은 너무 복잡해서 전체 모양을 매칭하기에 간단한 템플릿에 의해 캡처되기 힘들다. 숫자의 허용되는 모든 변화를 모두 캡쳐하기 위해서, 숫자를 구성하는 특징을 배울 필요가 있다.

Biological Neural Network Artificial Neural Network

Biological Neural Network 뉴런(신경세포): 신경망에서 가장 기본이 되는 단위 뉴런의 기본적 기능: 정보의 수용, 연산처리, 출력의 전송, 비선형성, 다입력 1출력, 흥분성과 억제성의 시냅스 결합, 순은, 적응, 피로 등 뉴런은 1000개에서 100,000개의 다른 뉴런들과 연결 인공신경망에서는 인간 두뇌의 1% 가량의 연결성도 현재 수준에서 원활히 처리하기 힘듦.

Artificial Neural Network 연산(뉴런) 가중치 출력 입력 신경망은 가중치를 반복적으로 조정하여 학습. 가중치는 장기 기억을 위한 기본 수단, 뉴런 입력 강도, 중요도를 표현. 뉴런의 기능 중 정보처리와 관련된 몇 가지 성질을 추상화한 뉴런 모델이 다수 제안. 가장 단순한 모델은 McCulloch, Pitts., 1943에 의해 제시.

Artificial Neural Network 첫째, 인간의 두뇌를 흉내내기에는 우리가 가진 컴퓨터의 성능이 터무니없이 모자랍니다. 과거 구글이 인공신경망을 이용해 유튜브 동영상에서 고양이 얼굴을 인식하는 것을 소개한적이 있는데 이는 중앙처리장치(CPU) 1만6천개가 필요했습니다. 반면 인간의 두뇌는 1011개의 뉴런과 1014개의 시냅스 연결로 이루어져 있다고 추정합니다. 이런 둘의 규모를 비교하면 정말 우리가 현재 인공으로 구현한 것은 자연에 비해 조족지혈입니다. 둘째, 아이러니하게도 인공신경망은 도대체 그 속을 알 수가 없다는(?) 단점이 있습니다. 아무리 성공적인 인공신경망이라고 해도 사람이 개개의 노드를 들여다보고 “1번 노드는 이러이러한 작용을, 2번 노드는 이러이러한 작용을 한다”라고 관찰한 뒤 “따라서 이 인공신경망이 작동하는 방식은 이러이러하다”라고 일반화할 수가 없습니다. 기능이 각각의 노드에 있지 않고 연결망 전체에 있기 때문입니다. 작동만 하면 되지 왜 일반화를 해야하냐고 반문할 수 있겠으나, 유한한 학습 자료로 훈련시킨 신경망을 신뢰할 수 있는 유일한 방법은 그 작동기제를 일반화하는 분석 뿐입니다. 그렇지 않으면 어느날 듣도보도 못한 입력값이 들어왔을 때 인공신경망이 어떤 엉뚱한 대답을 할 지 전혀 예상할 수 없기 때문입니다. 자연신경망 (a)와 인공신경망 (b)의 비교 (출처: 유신, 사이언스온,2012) 자연신경망이 감각기관으로부터 받은 입력에 반응해서 근육을 움직이는 출력값을 내놓듯, 인공신경망 또한 주어진 입력값에 반응해서 출력값을 내놓는다. 공을 받는 행위가 훈련을 통해 숙련되듯, 인공신경망도 학습을 통해 기능을 갖춘다.

Some Simple Neural Network Models

ANN 모델 종류 입력형식 학습방식 NN model 지도 학습 Hopfield network 지도 학습 및 비지도 Counterpropagation network 이진입력 학습을 결합한 학습 비지도 학습 ART model Perceptron Multilayer Perceptron 지도 학습 실수입력 Competitive learning SOM 비지도 학습

McCulloch-Pitts Neuron 인간의 신경활동을 2진 단위(binary unit)들의 결합으로 설명 각 뉴런의 입력, 출력은 1 or 0 1은 뉴런이 흥분 상태 0은 뉴런이 정지상태 1943년 McCulloch와 Pitts에 의해 제안. 초기 신경 시스템 모델 중 가장 잘 알려짐.

McCulloch-Pitts Neuron 뉴런은 Activation function을 사용. Activation function을 이용한 출력 결정 There are two equivalent ways to write the equations for a binary threshold neuron: 1 if 0 otherwise Z는 뉴런으로 들어가는 입력의 순 가중치의 합 xi는 입력 i의 값, wi는 입력 i의 가중치, n은 뉴런의 개수, y는 뉴런의 출력을 의미 Threshold는 negative bias를 갖는 것과 동일.

Activation function 뉴런의 출력 결정 계산 Activation function은 활성화함수 Linear neurons Binary threshold neurons Sign Activation neurons Rectified Linear neurons (linear threshold neurons) 선형 활성화 함수 (linear activation function) : 뉴런의 입력 값에 가중치가 적용된 것과 같은 값을 출력 값으로 산출. Sigmoid neurons

Activation function Binary threshold neurons Sign Activation neurons 계단(step)과 부호(sign) 활성화 함수는 하드 리밋 함수(hard limit function)라고도 불리움. 분류와 패턴인식 작업에서 결정을 내리는 뉴런에 주로 쓰임

Rectified Linear neurons (linear threshold neurons) Activation function Rectified Linear neurons (linear threshold neurons) Sigmoid neurons 시그모이드 함수(sigmoid function)는 양과 음의 무한대 사이에 있는 입력값을 0~1 사이에 있는 적당한 값으로 변환. 시그모이드 함수를 사용하는 뉴런은 역전파 (Back Propagation) 신경망에 사용

Perceptrons The first generation of neural networks The Perceptron, proposed by Rosenblatt is somewhat more complex than a single layer network with threshold activation functions. Structure 하나의 뉴런에 의해 생성되는 신경망 구조 K개의 입력, 1개의 bias, K+1개의 weight로 이루어진다. S는 특징벡터 X에 대한 선형함수형태로 나타난다. 선형 분류기 이다. 활성함수는 계단함수이다(threshold activation functions). 뉴럴 네트워크를 이루는 뉴런들의 연결가중치를 조금씩 조정하므로써 목표와 최대한 근접한 해를 찾는 방법 및 구조를 뜻합니다. (퍼셉트론은 결과가 다시 앞 뉴런의 입력으로 사용되는 피드백 구조를 사용하지 않기 때문에 피드포워드 뉴럴 네트워크(Feed-forward Neural Network)라고도 불립니다

The standard Perceptron architecture Perceptrons The first generation of neural networks feature units decision unit input units hand-coded weights or programs learned weights 입력 노드가 두 개인 단층 퍼셉트론 The standard Perceptron architecture If, single scalar quantity가 threshold보다 크면 input벡터는 타겟 클래스의 출력값 2차원 평면 위의 점(x1, x2)에 대해 0 또는 1의 값을 출력 각 feature activation들이 어떻게 가중치를 얻는지 학습 Raw input 벡터를 활성벡터로 변환한다. 이때, 사용자가 가중치를 주거나 프로그램에서 할당할 수 있다.

Perceptrons 학습(learning) 또는 훈련(training): 입출력에서의 연결선의 weight를 조정하는 것 학습 데이터(learning data) : 신경망을 학습시키기 위하여 주어진 입력과 원하는 출력의 쌍(pair) 학습 데이터를 통해 잘 훈련된 신경망은 학습되지 않은 입력에 대해서도 근접한 해를 출력 학습 데이터가 입력과 출력의 쌍으로 구성된 경우의 학습 방법을 지도 학습(supervised learning) 학습 데이터가 입력과 출력 모두로 구성된 것이 아니라 입력만으로 구성되는 경우(입력 데이터들만으로 연결 가중치를 조정하는 경우)의 학습 방법을 비지도 학습(unsupervised learning) 단층 퍼셉트론은 XOR 문제에 적용될 수 없는 등 제약이 많아서 바람직한 신경망 모델은 되지 못함 이러한 단층 퍼셉트론의 문제를 해결할 수 있는 대표적인 모델이 다층 퍼셉트론(multi-layered perceptron)

Multi-Layer Perceptron (MLP) 단층 퍼셉트론은 XOR 문제를 해결하지 못함. 이를 해결할 수 있는 대표적 모델기법이 다층 퍼셉트론 여러 신경망 모델 중 가장 일반적이며, 대표적인 모델. 다층 퍼셉트론은 입력층과 출력층 사이에 1개 이상의 은닉층(hidden layer)이 존재하는 시그모이드 함수를 전달 함수로 사용. 학습을 통한 지정된 출력을 요구->supervised network 목적: 출력의 지속적인 검증 및 학습을 통하여 기대되는 결과를 획득. 다층으로 퍼셉트론을 연결함으로써 비선형적 성질을 가능하게 함.

Multi-Layer Perceptron (MLP) 𝒉_𝑠𝑢𝑚 𝒌 𝒊 = 𝑙=0 𝑛 𝐻 𝑘+1 −1 ℎ 𝑘+1 𝑙 𝑤 𝑘 𝑙,𝑖 𝑜_𝑠𝑢𝑚 𝒊 = 𝑙=0 𝑛 𝐻 1 −1 ℎ 1 𝑙 𝑤 0 𝑙,𝑖 𝜏(𝒉_𝑠𝑢𝑚 𝒌 𝒊 )= 𝒉 𝒌 𝒊 𝜏(𝑜_𝑠𝑢𝑚 𝒊 )= 𝑜 𝒊 𝐸= 1 2 𝑙=1 𝑛 𝑂 (𝑡 𝑙 − 𝑜 𝑙 ) 2 𝜏 𝑠 = 1 1+ 𝑒 −𝑎𝑥 𝑜𝑟 2 1+ 𝑒 −𝑎𝑥 −1 𝑋 :𝑖𝑛𝑝𝑢𝑡 𝑣𝑒𝑐𝑡𝑜𝑟 𝑥 𝒊 :𝑋의 𝑖+1번째 원소(0부터 시작) 𝐻_𝑆 (𝑘) : 𝑘번째 ℎ𝑖𝑑𝑑𝑒𝑛 𝑙𝑎𝑦𝑒𝑟의 𝒉_𝑠𝑢𝑚 𝒌 𝒊 들로 이루어지는𝑣𝑒𝑐𝑡𝑜𝑟 𝐻 (𝑘) : 𝑘번째 ℎ𝑖𝑑𝑑𝑒𝑛 𝑙𝑎𝑦𝑒𝑟의 𝑜𝑢𝑡𝑝𝑢𝑡 𝑣𝑒𝑐𝑡𝑜𝑟 𝒉 𝒌 𝒊 : 𝐻 𝑘 의 𝑖+1번째 원소 0부터 시작 𝑂_𝑆 :최종𝑜𝑢𝑡𝑝𝑢𝑡 𝑙𝑎𝑦𝑒𝑟의 𝑜_𝑠𝑢𝑚 𝒊 들로 이루어지는𝑣𝑒𝑐𝑡𝑜𝑟 𝑂 :최종𝑜𝑢𝑡𝑝𝑢𝑡 𝑣𝑒𝑐𝑡𝑜𝑟 𝑜 𝒊 :𝑂의 𝑖번째 원소 𝑊 (𝑘) :𝑘번째 ℎ𝑖𝑑𝑑𝑒𝑛 𝑙𝑎𝑦𝑒𝑟의 입력 가중치 벡터 𝑤 𝒌 𝒊,𝑗 :𝑘+1번째 𝑙𝑎𝑦𝑒𝑟의 𝑖노드의 출력이 𝑘번째 𝑙𝑎𝑦𝑒𝑟의 𝑗노드에 입력될 때의 가중치 𝑛 𝑉 : 𝑉의 원소 수 𝑇 :목표 𝑜𝑢𝑡𝑝𝑢𝑡 𝑣𝑒𝑐𝑡𝑜𝑟 부류𝑣𝑒𝑐𝑡𝑜𝑟 𝑡 𝒊 :𝑇의 𝑖+1번째 원소(0부터 시작) 𝐸 :오차제곱합 𝜏 𝑠 : 활성 함수

Back propagation Algorithm Back propagation은 multilayer, feedforward 신경망에서 사용되는 학습 알고리즘 지도 학습 (supervised learning). 즉, 학습을 하기 위해서는 입력 데이터와 원하는 출력(d) 데이터가 있어야 함. 입력이 신경망의 가중치(weights)와 곱하고 더하는 과정을 몇 번 반복하면 입력의 결과값인 출력(y)이 나옴. 이 때 출력(y)은 학습 데이터에서 주어진 원하는 출력(d)와 다름. 결국, 신경망에서는 (y - d)만큼의 오차(E = y - d)가 발생하며, 오차에 비례하여 출력층의 가중치를 갱신하고, 그 다음 은닉층의 가중치를 갱신. 가중치를 갱신하는 방향이 신경망의 처리 방향과는 반대 방향.

Error back propagation Algorithm 개념 은닉층의 학습을 위해 출력층에서 발생한 오류를 이용하여 은닉층 오차계산 다시 이 값을 입력층으로 역전파시켜, 출력층의 오차가 원하는 수준이 될 때까지 반복 다층 퍼셉트론 구조의 대표적인 학습방법. 최종 출력벡터와 목표 출력벡터(부류벡터)의 오차 제곱합을 줄이는 방향으로 각 퍼셉트론의 가중치를 조절. 오차제곱합을 비용함수로 하고 이를 줄이는 방향으로 가중치를 조절한다. 내리막 경사법을 이용. 신경망의 처리 : 입력층 → 은닉층 → 출력층 Weight 갱신의 학습방향: 출력층 → 은닉층 calculation Weight update Input Output Error(e) = y – d y: 데이터 입력에 대한 결과 값 d: 원 하는 값 오차(e = y - d)

Back propagation Algorithm 보충 Forward Propagation Backward Propagation (Sensitivity) 3. Weight Bias Update

Other representative model

Hopfield Networks 2가지 제약조건 ① 뉴런 사이의 연결강도 (weight) 는 대칭이다. 즉, wij = wji 생물학적 뉴런에서는 일반적으로 대칭성 성립이 안됨. ② 각 뉴런들은 완전히 비동기적으로 (asynchronously) 동작할 때만 안정된 상태에 도달 가능. 만약 동기적으로 작동할 때에는 에너지가 안정된 상태에 도달하지 못할 수 있으며, 무한 루프에 빠질 수 있음. 특징 뉴런의 작용을 단지 임계값(threshold)의 작용으로 보고 훈련에 의한 정보가 연결강도에 의해 표현된다는 간단한 이론에 기초 연상기억 (associative memory) 이나 순회판매원 문제 (Traveling Salesman Problem) 와 같은 최적화 (optimization) 문제를 해결하는데 있어 매우 유용 많은 수의 비동기적이고 국소적인 계산을 통하여 전역적 최적화 (global optimization) 를 이룰 수 있다는 것이 증명됨.

Hopfield network 의 기본 구조 Hopfield Networks 자신을 제외한 모든 unit들간 양방향으로 상호 연결된 network 입출력(초기버전): 이진수, 전달함수는 계단함수 (hard limiter) 사용 입출력(1986년~ ): 아날로그인 버전이 발표 Hopfield network 의 기본 구조 x0, x1, x2 ... xN-1 은 입력된 패턴 x0', x1', x2' ... xN-1' 은 network 가 수렴한 상태의 출력패턴 각 unit들은 자신을 제외한 다른 모든 unit들과 완전 연결 상태 출력 : +1, -1(양과 음의 에너지 상태를 표시)

Hopfield Networks 보충 자료 1단계 : M개의 패턴을 이용하여 N개 뉴런 사이의 연결 가중치를 지정 wij: 뉴런 i에서 뉴런 j로의 연결가중치 Xsi: s 클래스에 속하는 학습패턴의 i번째 요소값(+1 or -1) 2단계 : 미지의 입력패턴을 신경회로망에 제시 3단계 : 뉴런들의 출력과 가중치를 곱한 값을 합하여 전달함수를 통과 함수 fh 는 hard limiting 비선형 함수 4단계 : 수렴(출력의 변화가 없음)할 때까지 3단계를 계속 반복 5단계 : 2단계로 분기 출력 : +1, -1(양과 음의 에너지 상태를 표시)

Hopfield Networks 예제 따라서, 도시의 숫자가 커짐에 따라 경우의 수도 기하급수적으로 커짐. 본 예제의 목표는 최적화 문제의 예 TSP(Traveling Salesman Problem) NP-Complete 클래스에 속함. '최적' 의 해답보다는 '좋은' 해답 도출 행렬의 엔트리 숫자만큼 처리 unit 필요. 100 (102) 개의 unit를 필요 경우의 수 10개의 도시의 경우 9!/2 = 36,28,000/2 = 181,440 30 개 도시의 경우 4 × 1030 따라서, 도시의 숫자가 커짐에 따라 경우의 수도 기하급수적으로 커짐. 본 예제의 목표는 100개의 unit를 가진 네트워크가 수렴하여 순방을 나타내는 좋은 행렬값을 구하는 것. 출력 : +1, -1(양과 음의 에너지 상태를 표시) 순회판매원 문제란 방문하여야 할 도시들과 이들 사이의 거리가 주어졌을 경우, 순회판매원이 여러개의 도시를 방문하는데 어떤 특정한 도시를 출발하여, 어떠한 도시도 두 번 방문함이 없이 모든 도시들을 거쳐 처음 출발한 도시로 되돌아 오는데, 총 여행 거리가 최소가 되는 경로의 순서를 정하는 문제

Hopfield Networks 예제 에너지 식 에너지 함수는 다음의 문제들을 지키면서 만들어져야 함. ① 각 도시를 꼭 한번씩만 방문해야 한다. ② 동시에 두 도시를 방문할 수 없다. ③ 정해진 도시들만 (예를 들면 n 개) 방문해야 한다. ④ 순회거리의 총합이 최소가 되어야 한다. 출력 : +1, -1(양과 음의 에너지 상태를 표시) 순회판매원 문제란 방문하여야 할 도시들과 이들 사이의 거리가 주어졌을 경우, 순회판매원이 여러개의 도시를 방문하는데 어떤 특정한 도시를 출발하여, 어떠한 도시도 두 번 방문함이 없이 모든 도시들을 거쳐 처음 출발한 도시로 되돌아 오는데, 총 여행 거리가 최소가 되는 경로의 순서를 정하는 문제 (a), (b), (c), (e): 네트워크 처리의 중간 결과 (d): 네트워크의 최종상태 (f): 최종 결과 최종 결과가 훌륭해 보이지만 최적의 해는 아님.

Competitive Learning 비지도 학습 단순한 구조 Hard Learning: 오직 경쟁에서 승리한 뉴런의 가중치만 업데이트 Soft Learning: 승리한 뉴런과 그와 유사한 뉴런의 가중치를 업데이트 Simple competitive network는 기본적으로 두가지 네트워크로 구성 1) Hamming net 2) Maxnet

Competitive Learning 예제 Competitive Hebbian Learning JAVA Source code 참조 사이트 http://www.sund.de/netze/applets/gng/full/DemoGNGcode.html

Competitive Learning 예제 Competitive Hebbian Learning Initial state. b-f) Intermediate states. g) Final state. h) Voronoi tessellation corresponding to the final state. Obviously, the method is sensitive to initialization since the initial positions are always equal to the final positions. Simple ring-shaped data distribution을 위한 시뮬레이션 단계 http://www.sund.de/netze/applets/gng/full/DemoGNGcode.html

Competitive Learning 예제 Competitive Hebbian Learning Competitive Hebbian learning simulation results (after 40000 input signals for three different probability distributions) http://www.sund.de/netze/applets/gng/full/DemoGNGcode.html

Competitive Learning 보충 자료 Agustin Rodriguez, Muneeb Mahmood Thomas Golisano College of Computing and Information Sciences - Computer Science Feedforward + Recurrent Network 입력에 대하여 Hamming distance를 최소화 하는 Network

Self-Organizing Maps SOM Structure Feature 스스로 학습을 할 수 있는 능력을 이용한 신경망 모델 핀란드의 헬싱키공과 대학의 Kohonen에 의해서 제안 ‘자기조직화’란 주어진 입력 패턴에 대하여 정확한 해답을 미리 주지 않고 자기 스스로 학습 할 수 있는 능력 Structure 코호넨 네트워크(Kohonen Network)는 역전파 네트워크와는 달리 일반적으로 계층적인 시스템이 아니며 2개의 층으로 이루어져 있음 네트워크의 첫 번째 층은 입력층(input layer)이고, 두 번째 층은 경쟁층(competitive layer)인데 2차원 격자(grid) 모든 연결들은 첫 번째 층에서 두 번째 층의 방향으로 되어 있으며, 두 번째 층은 완전 연결(fully connected) Feature 층내의 뉴런의 연결강도 벡터(연결 가중치)가 임의값을 가지면서 적합하게 초기화 연결강도 벡터와 입력벡터가 통상 0에서 1사이의 정규화된 값을 사용하여야 한다(코호넨 네트워크에서는 매우 중요 ) 초기 경쟁학습은 매번 승자뉴런만을 학습시키므로 초기 가중치벡터들의 분포에 따라 전혀 학습이 이루어지지 않은 출력뉴런들이 생기는 문제점 기존의 경쟁학습을 개선하여 입력벡터와 가장 가까운 출력뉴런의 이웃뉴런들을 함께 학습 시키는 알고리즘

Self-Organizing Maps Competition Cooperation Adaption Self-organizing Feature Map’s Algorithm [단계 1] 연결강도를 초기화 [단계 2] 새로운 입력 벡터를 제시 [단계 3] 입력 벡터와 모든 뉴런들 간의 거리를 계산(Euclidean metric) [단계 4] 최소거리에 있는 출력 뉴런을 선택하며, 출력 뉴런의 이웃 뉴런들도 선택 [단계 5] 승자 뉴런과 이웃 뉴런들의 연결강도를 조정 w(new)ij = w(old)ij + α(ai - w(old)ij) [단계 6] 단계 2로 가서 반복한다. 모든 뉴런들이 변화가 없을 때 종료 Competition Cooperation Adaption

Self-Organizing Maps 예제 [단계 1] 연결강도를 초기화 [단계 2] 새로운 입력벡터를 제시, 입력: X=(0.1, 0.9) [단계 3] d0 = (0.1-0.5)2 + (0.9-0.9)2 = 0.16, d1 = 0.05, d2 = 0.02(승자뉴런) [단계 4] d2 = 0.02(승자뉴런) 선택 [단계 5] d2의 연결 가중치 조정 W02(t+1) = 0.2+0.5(0.1-0.2) =0.15 W12(t+1) = 0.8+0.5(0.9-0.8) =0.85 → [W02(t+1), W12(t+1)]와 일정 거리 내에 있는 뉴런들에 대하여 가중치값 보정 만약 d1이 승자뉴런 d2에 가장 가깝다면 W01(t+1) = 0.3 +0.5(0.1-0.3) =0.15 W11(t+1) = 1.0 +0.5(0.9-1.0) =0.85 승자뉴런과 이웃한 뉴런의 출력 값은=1, 그 외 뉴런의 출력값= 0 (단, 학습률은 0.5)

Adaptive Resonance Theory 적응 공명 이론 Carpenter and Grossberg in 1987 비지도 학습 구성: A comparison field Recognition filed Reset module 안정-적응(stability-plasticity)에 의한 자율 정규화 Basic ART Structure 중요한 사건에 대해서 이를 내부적으로 잘 표현(적응) 중요치 않은 사건은 현재 학습된 내용에 손상을 주지 않고, 안정된(stable) 상태 입력이 들어오면 기존의 학습된 지식과 유사한 지를 비교 만일 비슷하면 새로운 입력을 기존의 학습된 내용과 결합시켜 학습된 지식을 수정하고, 다르다면 입력패턴을 새로운 지식으로 받아들여서 기억장소에 저장하게 됨.

Adaptive Resonance Theory 적응 공명 이론 ART는 competitive learning의 확장 competitive layer와 input layer사이에 feedback mechanism을 더함으로써 stability-plasticity dilemma를 해결. (안정-적응에 의한 자율 정규화) feedback mechanism approach의 결과 실제 환경에서의 pattern-classification 문제에 적합한 두 가지 neural network architecture인 ART1과 ART2가 개발 ART1가 ART2는 input pattern의 성격으로 구분이 되는데 ART1은 input vector가 binary. ART2는 analog로써 gray-scale pattern을 processing.

Adaptive Resonance Theory 적응 공명 이론 참조: http://www.myreaders.info/05-Adaptive_Resonance_Theory.pdf http://medusa.sdsu.edu/Robotics/Neuromuscular/Theses/Hongyu/chapter3.pdf

Application areas

음성 합성 및 인식 문장을 음성으로 변환하는 신경망 시스템 문자 입력을 음소로 출력하는 부분에 신경망 모델을 사용 Sejnowski, Rosenberg 문자 입력을 음소로 출력하는 부분에 신경망 모델을 사용 NETtalk: 음소를 합성하는 음성 합성기를 통해 출력된 음소를 합성 • 학습 방법: Rumelhart와 Williams의 오류 역전파 방법 • 임의의 가중치를 가진 비훈련 상태에서 시작하여, 짧은 시간을 거친 후에는 NETtalk는 계속적이고 서투른 발음을 시작 • 모든 발음이 연결되고 단지 하나의 말소리로 들리게 됨 • 훈련을 통하여 학습을 계속하면 소리가 분리되고 하나 이상의 말소리가 들리게 됨 • 출력은 유아의 발음과 같다. 학습이 계속될수록 NETtalk의 출력은 어린이처럼 발음하기 시작하고, 단어들은 명백히 분리할 수 있게 됨 • 기존의 일반적인 방법을 이용하여 문장을 음소로 변환시키는 시스템도 동일한 기능을 수행할 수 있지만, 개발하는데 몇 년이 걸리며 또한 음운 법칙을 배우는데 많은 시간이 걸림 • 반면에 NETtalk는 학습 능력이 있으므로 단지 3개월 정도의 개발 기간만이 소요

언어 학습 영어 동사의 과거 시제를 배우는 신경망 Rumelhart, McClelland • 연구의 목적: 신경망이 아이들이 자라면서 동사의 과거 시제에 관한 법칙을 배우는 것과 같은 능력을 가질수 있는가를 시험하기 위함 • 원형 동사의 음소 표현을 입력으로 받아 과거 시제의 음소 표현을 출력 • 모델의 구조가 좌우 대칭인 경우에 유용한 볼츠만 머신 학습 방법을 사용 • 초기 학습을 거친 후에는 언어적 법칙을 발견하지만 모든 원형 동사에 동일한 법칙을 적용 • 그 다음 단계에서는 규칙과 불규칙을 구분하게 되고 마지막 단계에서는 변형 법칙까지도 학습하게 됨 • 응용 결과: 신경망은 학습 능력이 있고, 훈련을 통하여 주어진 정보를 일반화시킴으로써 새로운 입력 정보에 적응할 수 있음을 확인 • 또한 신경망을 이용한 자연어 처리에 관한 연구도 수행 • 문맥으로부터 단어의 어떤 의미가 정확한지를 신경망에 훈련시킨 후, 단어의 의미를 분별할 수 있는 신경망이 개발 • Ex. 문장 “Bob threw a fight" 와 "Bob threw a ball"에서 threw의 의미 차이를 신경망을 통하여 이해할 수 있음

문자 인식 인쇄체 및 필기체 문자의 인식 능력을 바탕으로 이미 우편봉투 자동분류, 수표 및 지로용지의 인식, 인구센서스 결과의 통계, 세금보고서의 자동처리 현재 세계적으로 독일의 Siemens, 일본의 NEC, 미국의 CEDAR, SUNY at Buffalo 등이 우편물 분류를 중심으로 한 높은 기술 수준을 보유 국내) 1999년 우편물 자동분류기 개발사업, 금융권 전장표 자동처리 시스템 사업 등을 시작으로 여러 기업들이 경쟁하고 있으며, 펜컴퓨터용 인식기, 한글 필기인식, 형식문서 인식 등을 위하여 산학연 컨소시움을 중심으로 활발하게 연구되고 있음

영상 처리 미국 국방연구원(DARPA)의 지원에 의한 잠수함의 장애물 인식 신경망에 관한 연구 잠수함은 바다속을 항해할 때 음파를 쏘아서 돌아오는 반사파를 분석함으로써 장애물이 암초인지, 적의 잠수함인지, 아니면 물고기인지 구별 처음 2년에 걸쳐 전문가 시스템을 개발하였으나 실용화에는 많은 문제점이 노출 그러나 다층 퍼셉트론 모델을 이용하여 60개의 노드와 12개의 중간 노드 그리고 2개의 출력 노드를 갖는 신경망에 오류 역전파 방법으로 학습시킨 결과, 상당히 우수한 결과 신경망을 이용한 무인 자동차 운행 시스템 개발 이 시스템은 자동차 운전석에 카메라를 부착하고 운전 페달에 센서를 달아서 사람이 운전하는 동안 화면(핸들)과 손발(가속, 브레이크 페달)의 움직임이 어떤 식으로 일어나는지에 대한 자료를 수집한 후 이를 사용하여 신경망을 학습 960개의 입력 유닛을 통해 운전대의 방향과 가속 및 브레이크 페달을 제어하는 출력을 생성함으로써 자동차를 제어 실제로 고속도로에서 100km 정도의 속도로 주행한 바 있음

영상 처리 주가 변동 예측, 항공사 좌석 예약 관리, 고객의 은행 신용도 판별, DNA 코드 분석 등에도 응용 대규모의 복잡한 데이터로부터 유용한 규칙이나 새로운 지식을 발견하기 위한 데이터마이닝(data mining)에 관한 연구에서도 신경망이 활용 Ex) 신용카드 회사에서 고객의 카드를 결재할 때 도용인지 아닌지 판별하는 문제 이를 위해, 평소 그 고객의 카드 사용 행태를 신경망에 학습시킨 후, 카드 결재 시 신경망을 사용하여 지금까지의 사용 패턴과의 차이를 분석하여 심각한 차이가 발생할 경우 결재를 거부함으로써 카드 도용을 방지하는 시스템이 개발 이외에도 인간의 DNA 구조를 분석하거나, 천체 데이터를 분류하고 특징을 찾아주는 등의 순수 학문적인 연구에서도 신경망이 기여.

참고 문헌 IT CookBook, 패턴인식 개론: MATLAB 실습을 통한 입체적 학습, 한학용, 한빛아카데미, 2005 인공지능 개념 및 응용(3판) 도용태, 김일곤, 김종완, 박창현 공저 , 사이텍미디어, 2009 Introduction to Data Mining, Pang-Ning Tan, pp. 246-256, pp. 594-600, Peason, 2005 Neural Networks for Machine Leaning, Geoffrey Hinton, lecture material, University of TORONTO Introduction to Machine Learning, Ethem Alpaydin, MIT press. Neural Network Design, Martin T.Hagan, Howard B.Demuth, Mark Beale, PWS Publishing Company. Neural Networks and Learning Machine, Simon Haykin, Prentice Hall. New Usage of SOM for Genetic Algorithm, 김정환, 문병로, 정보과학회, pp. 440-448, 33(4), 2006 The parallel distributed processing approach to semantic cognition, James L. McClelland & Timothy T. Rogers, Nature Reviews Neuroscience, 4, pp. 310-322, 2003 The Organization of Behavior, Hebb, D, O, Lawrence Erlbaum Assoc Inc, 2007 Machine Learning, Tom Mitchell, McGraw Hill www.wikipedia.org http://labs.seas.wustl.edu/bme/raman/Lectures/Lecture10_CompetitiveLearning.pdf http://www.shy.am/wp-content/uploads/2009/01/kohonen-self-organizing-maps-shyam-guthikonda.pdf http://genome.tugraz.at/MedicalInformatics2/SOM.pdf