Insertion sort를 시각화 해보았다
'Visualization' 카테고리의 다른 글
| [Visualization] Selection Sort (0) | 2016.07.03 |
|---|---|
| [Visualization] Bubble Sort (0) | 2016.07.03 |
[Visualization] Insertion Sort
2016. 7. 3. 23:50
[Visualization] Bubble Sort
2016. 7. 3. 23:50
Bubblesort를 시각화 해보았다.
각 interval마다 순차적으로 transition이 일어나야 되는데..
처음에는 setInterval을 이용해보았으나 setInterval은 해당ms 이후에 함수가 실행되도록 해 주고 바로 리턴해버려서 실패했다
결국 d3의 transition.delay()를 이용하여 해결하였다!
'Visualization' 카테고리의 다른 글
| [Visualization] Selection Sort (0) | 2016.07.03 |
|---|---|
| [Visualization] Insertion Sort (0) | 2016.07.03 |
[Perceptron 1] History
2016. 7. 3. 23:28
1957
Perceptron. 벡터의 각 원소에 가중치를 곱한 총합을 가지고 분류한다!
미국의 심리학자 Frank Rosenblatt는 입력으로 하나의 벡터가 주어지면, 이를 두 종류(class)로 분류하는 함수를 배우는 모델인 Perceptron이란 개념을 제시한다.
1969
Perceptrons. 왜 이런 눈아픈 그림을 책 표지로 했을까? 잠시 후에 알아보자!
Marvin Minsky and Seymour Papert은 저서 Perceptrons 을 발간한다. 그들은 perceptron을 다양한 상황들에 적용시켜보면서 그것의 computational capability를 알아보고자 했다. 당대 사람들은 잠재적으로 무한한 가능성을 가진 것처럼 보이는 새로운 'learning machine' 개념의 등장에 흥분한 나머지 이걸로 뭐든지 할 수 있다고 굳게 믿고 있었다. 이러한 비현실적인 기대 때문에 이 개념을 가지고 어떤 class의 문제를 풀 수 있는지에 대해서는 충분히 연구가 이루어지지 않았기 때문에 Minsky와 Papert의 이 책이 무지 큰 의미를 갖는다는 거다.
하지만 기대가 크면 실망도 큰 법이라고, Minsky와 Papert에 의하여, perceptron 의 한계가 너무나 명백하게 제시되면서 사람들은 마음을 돌려버리게 된다.
이를 소위 XOR 사태(The XOR affair)라고 하며 제 1차 AI Winter의 시발점이 된다.
(Rosenblatt은 1971년 Chesapeake Bay에서 보트 사고로 사망한다(자살이라는 설도 있다). 그것도 생일에. 그의 명복을 기리기 위하여 Minsky는 Perceptron의 추가 출판본에 Rosenblatt에 대한 헌사를 추가한다. ㅠㅠ)
Limits of the Perceptron
Perceptron이 해결하지 못하는 대표적인 문제로 다음 두 가지가 있다:- XOR
- Connected predicate
Perceptron과 predicate 둘다 input을 받아서 하나의 binary value를 결과값으로 내놓지 않나? 둘이 뭐가 다른거지?
음...이 부분이 명확하게 이해되지는 않지만, 현재까지 이해한 바로는 다음과 같이 대답할 수 있겠다.
먼저 Minsky의 Perceptron 모델은 Rosenblatt의 그것과 약간 다르다는 것부터 짚고 넘어가야 한다. Rosenblatt과 Minsky 모두 raw input vector를 retina에 빗대어 설명하고 있다. 여기까지는 꽤나 직관적이다. 그러니까, 물체의 상이 눈의 망막에 맺혀 우리가 물체를 '보게' 되듯이, perceptron의 망막에 지금 물체의 상이 맺힌 거다. 이제 다음은 뭘까? 우리 눈은 이를 전기적인 신호로 변환하여 일련의 세포층을 거쳐 이 신호를 뇌로 전달하고, 결국 우리는 물체를 인식하게 된다. 이 과정에서 Rosenblatt과 Minsky의 모델에 차이가 있다. Rosenblatt의 모델은retina의 각 value들이 deterministic하게 다음 layer와 연결되어 있는 반면, Minsky의 모델은 retina의 모든 value를 sequential하게 scan하지 않고, 특정 부분에 주목하여 parallel하게 처리한다. 즉 여기서 predicate을 이용하여 특정 부분만을 인식하는 것. 간단히 말해 perceptron은 retina에 맺힌 input을 받아 decision을 만드는 데 까지의 보다 포괄적인 개념이라면 predicate은 retina의 일부분만을 인식하는 subset과 같은 개념이라고 보면 될 듯하다.
결국 predicate은 retina에 갖다 댄 깔때기인 거다!
여하튼, 이제 이것이 왜 문제가 되는지 알아보자.
하나의 이미지를 생각하자. 여기서는
요런 그림
을 생각해 보자. 각각의 그림을 perceptron에게 보여줘서 이 그림이
연결되어 있는지, 아닌지
알아보고 싶다. 요컨대 A나 D같은 경우는 끊어져 있으므로 0을 반환하고, B나 C같은 경우는 연결되어 있으므로 1을 반환하도록 perceptron을 학습시킬 수 있을까? 여기서 약간의 제약을 위해 predicate, 그러니까 깔때기의 수가 충분히 많지 않고(9개라고 하자!), 깔때기의 크기는 좀 작아서 그림을 전부 덮지는 못하며, 각각의 그림을 볼때마다 깔때기를 움직이지 않는다고 하자.
일단 predicate을 어디에 놓을지부터 생각해보자.
음..이건 딱 봐도 3*3 격자(상상해보자)의 각 교차점에 깔때기를 놓는 것이 각각의 그림 고유의 특징을 잘 잡아낼 것 같다! 그리고 각각의 열을 group 1, 2, 3으로 생각하자.
이제 '학습된' perceptron을 가정하자. 그러니까 이놈은 A, D를 보면 0을, B, C를 보면 1을 뱉어내는 perceptron이다.
A를 봤을 때 0을 뱉어내야 하므로,
$ S_A = \sum_{group1}w_iP_i + \sum_{group2}w_iP_i + \sum_{group3}w_iP_i + \theta < 0 $
이다. P는 각 깔때기가 반환한 값이며, 여기서 $ -\theta $가 임계값이다. 위 식을 간단히 말하면 각 깔때기가 반환한 값에 가중치를 주어 모두 더한 값이 임계값보다 작다는 것을 말한다. 자, B를 봤을 때는 어떨까? 그림을 잘 보면 group1, 2 깔때기들은 뭐가 바뀐지 모른다(그림의 오른편을 손으로 가리고 한번 보자!). 즉 같은 값을 반환한다는 거다. 그럼 달라지는 건 group3 깔때기들이 반환한 값일 것이고, 이 값 때문에 결과값 S는 0 보다 커져야 한다. Group 3 깔때기들때문에 '변화한' 값을 $ \Delta S_3 $라고 하자. 그러면$ S_A + \Delta S_3 \ge 0 $
$ \Delta S_3 \ge -S_A $
이며, C의 경우에는 마찬가지로 group 1에다가 같은 논리를 적용시키면 된다.
$ S_A + \Delta S_1 \ge 0 $
$ \Delta S_1 \ge -S_A $
이제부터 하이라이트다. 우리의 perceptron은 D를 보게 된다. 얘는 학습되었으므로 반드시 D를 보고 0을 반환할 것이다. 즉 $ S_D < 0 $이어야 한다. 그런데, group1, group2와 group3은 각각 자신이 C, A와 B를 볼 때와 다름이 없으므로,
$ S_D = S_A + \Delta S_1 + \Delta S_3 \ge -S_A > 0 $
이다. 왜냐면 $ S_A < 0 $이니까.
이는 모순이므로 우리의 perceptron은 불행히도 이 상태로는 이 그림들의 연결성을 알아낼 수 없다. 유일한 대안은 진짜 인간이 연결성을 알아내듯이, sequential 하게 인식하는 방법밖에는 없다.
다시 Perceptrons의 책 표지를 보자. 위와 아래, 둘 중 어느 그림이 연결되어 있는가?
참고
Neural Networks - A Systematic Introduction, Raul Rojas, Springer-Verlag, Berlin, New-York, 1996. (위 책은 이 사이트에서 볼 수 있다)