[인공지능 및 기계학습 개론] 2.2 Introduction to Rule Based Algorithm

이번 포스팅에서는 지난 포스팅에서 다룬 예를 몇몇 algorithm을 토대로 살펴보도록 하겠습니다.

 

http://www.edwith.org/machinelearning1_17/lecture/10580

[LECTURE] 2.2. Introduction to Rule Based Algorithm : edwith

 

---

 

[인공지능 및 기계학습 개론] 2.1 Rule Based Machine Learning Overview에서 다뤘던 예를 이어서 보겠습니다. 분류모형을 만들고자 하는데, 그 중 첫번째 알고리즘으로 Find-S Algorithm이라는 것이 있습니다. 이 알고리즘은 Null hypothesis $\mathbf{h}_0=<\emptyset,\emptyset,\emptyset,\emptyset,\emptyset,\emptyset>$를 시작으로 instance를 하나씩 받으면서 label이 positive인 경우에만 instance의 feature와 hypothesis의 feature를 비교하고, 다른 feature에 대해서만 hypothesis의 feature를 기존 hypothesis의 feature와 instance의 feature의 union으로 update 해줍니다. 이 과정을 모든 instance에 대해서 반복하는 algorithm이 되겠습니다. Pseudo code로 보면 아래와 같습니다.:

 

pseudo code of find-s algorithm

 

이러한 과정을 반복하면 target function에 수렴(converge)할 수 있을까요? 사실 너무나 많은 후보군이 되는 hypotheses가 생기게 되어 convergence를 찾기가 쉽지 않습니다. 그래서 우선은 가능한 모든 hypotheses의 집합을 생각하고 그 안에서 좁혀나가는 방식을 생각하고자 하는데, 이렇게 모든 가능한 hypotheses의 집합을 Version Space (VS) 라고 부릅니다. 좀 더 공식화해보면, 가장 general한 case와 specific한 case를 생각하고 그 사이의 hypotheses를 고려하는 것입니다. 이 때 가장 general한 case의 모임을 general boundary (G) 라고 하고, 가장 specific한 모임을 specific boundary (S) 라고 합니다. 그러면 hypotheses 전체의 집합을 $H$라 할 때 $H$ 위에 partial order를 아래와 같이 줍니다.: $$ g > h \Leftrightarrow g\text{ is more general than } h $$ $H$에 있는 임의의 두 hypotheses끼리 항상 위와 같은 비교를 할 수는 없기에 (e.g. 다 똑같고 날씨만 하나는 sunny, 하나는 rainy라면 어느 하나가 다른 하나보다 더 general 하다고 말할 수 없습니다.) partial order라고 하였고, 이에 관련해서는 구글링 해보시기 바랍니다. 이렇게 order를 주면 version space를 다음과 같이 묘사할 수 있겠습니다.: $$ VS_{H,D}\coloneqq\{h\in H\::\:g\ge h\ge s\text{ for some }s\in S\text{ and }g\in G\} $$ 그러면 아래 그림과 같은 ordering을 얻을 수 있습니다.:

 

version space

 

이제 version space를 잡았으니 이 안에서 우리의 target hypothesis를 찾는 방법을 알아보도록 하겠습니다. Candidate Elimination Algorithm이라는 것인데, 거칠게 말하면 $G$와 $S$ 사이를 좁혀가며 사이에 있는 target hypothesis를 특정하는 것이 목표인 algorithm입니다. 바로 Pseudo code를 보겠습니다.:

 

pseudo code of candidate elimination algorithm

 

위 pseudo code에서 $h(o)$라는 것은 hypothesis를 function 혹은 mask라 생각하고 $x$의 feature sequence인 $o$에 씌운 것이라 생각하시면 됩니다. 예를 바로 보는 것이 이해가 빠르니 바로 예를 보도록 하겠습니다.

 

progress of candidate elimination algorithm - 1

 

$0$번째 step (initialization) 에서는 모든 경우를 다 거절하는 $S0$와 모든 경우를 다 수용하는 $G0$를 두고 시작합니다. 첫 번째 step이 시작되고 첫 번째 instance를 봅니다. label을 보니 Yes(positive)이기 때문에, specific한 대상을 첫 번째 instance에 맞게 generalize 합니다. 그렇게 하면 $$ S1: \text{{<Sunny, Warm, Normal, Strong, Warm, Same>}} $$ 이 되고, general part는 변함이 없기 때문에 $G1=G0$ 입니다. 두 번째 step이 되면, 여전히 두 번째 instance 역시 label이 positive이기 때문에 $S1$을 generalize 합니다. 이 때 $S1$에 있는 hypothesis와 두 번째 instance 사이의 차이를 보면 Humid column만 다른 것을 알 수 있습니다. 일반화를 하는 것이기 때문에 해당 부분은 don't care 처리를 합니다. (사진 속 물음표 처리) 여전히 general part는 변화가 없기에 $G2=G1$ 가 되겠습니다.

 

progress of candidate elimination algorithm - 2

 

세 번째 step을 보면 드디어 세 번째 instance의 label이 negative가 나왔습니다. 따라서 specific part는 그대로 두고 (i.e. $S3=S2$), general part만 보도록 하겠습니다. 세 번째 instance의 feature를 제외한 feature를 추가하는 방식으로 generalize가 일어나는데, 예를 들어 세 번째 instance의 Sky column은 Rainy이므로 Sunny로 바꾸어서 hypothesis $G3$에 추가합니다. 이 때 기존 specific part와 모순이 없어야 함을 염두에 두고 일반화 해야 합니다. 지금은 $S3$에 있는 hypothesis의 Sky column 또한 Sunny이므로 무리 없이 $\text{<Sunny, ?, ?, ?, ?, ?>}$를 추가할 수 있겠습니다. Temp column의 경우는 방금 전과 같이 잘 진행이 됩니다. Humid column의 경우 instance의 feature는 High이므로 원래대로라면 Normal로 바꿔 generalize 해야하지만, specific part를 보면 don't care 처리가 되어 있기 때문에 이 부분은 Normal로 추가하지 않습니다. 추가하면 general part와 모순이 발생하기 때문입니다. (이 부분이 바로 위에서 말한 $h(o)$가 negative인 부분입니다.) 그렇게 Wind, Water column 또한 추가하면 모순이 일어나므로 추가하지 않고, 마지막으로 Forecast column의 경우 Change를 Same으로 바꾸어 추가해도 문제가 없기 때문에 추가합니다. 그렇게 하면 $$ G3: \text{{<Sunny, ?, ?, ?, ?, ?>, <?, Warm, ?, ?, ?, ?>, <?, ?, ?, ?, ?, Same>}} $$ 이 되겠습니다. Pseudo code 상으로는 Generalize/Specialize 하는 부분과 Remove 하는 부분이 나누어져 서술이 되어 있지만, 사실은 함께 진행한다고 생각해도 무방할 듯 합니다.

 

progress of candidate elimination algorithm - 3

 

이 과정을 모든 instance에 대해서 반복해주면 $S4$와 $G4$를 얻게 되는데, 결국 이 사이의 hypotheses는 하나로 특정되지 않기 때문에, 위 4개의 instance가 아닌 다른 instance가 들어오고 그 instance가 만약 $S4$나 $G4$에 딱 걸리는게 아니라면, 그 사이에 있는 hypotheses의 선택에 따라 positive를 줄 수도 있고 negative를 줄 수도 있을 것입니다. 가령 $$ \text{<Sunny, Warm, Normal, Strong, Cool, Change>} $$ 라는 feature sequence가 들어온다면, 이는 version space 내에 속하는 instance인데, $$ \mathbf{h}_1:\text{<Sunny, Warm, ?, Strong, Cool, ?>} $$ 이란 hypothesis에 의해서는 positive한 결과를 줄 것이고, $$ \mathbf{h}_2:\text{<Sunny, Warm, High, Strong, ?, ?>} $$ 이란 hypothesis에 의해서는 negative한 결과를 줄 것입니다. 

 

이런 경우 뿐만 아니라 애초에 해당 version space에 들어가지 않는 instance도 얼마든지 들어올 수 있는데, 이 경우 해당 모델로는 대응이 불가합니다. 예를 들어 $$ \text{<Sunny, Warm, Normal, Light, Warm, Same>} $$ 과 같은 instance의 경우 specific part에서부터 걸리기 때문에 version space에 들어오지 않고, 따라서 이런 input을 받을 model은 엉뚱한 결과를 줄 수 밖에 없을 것입니다. 이러한 문제가 발생하는 이유는 모든 정보가 training dataset에 반영이 되어 있다는 perfect world assumption을 만족하지 않기 때문인데요. 사실 현실에서는 이런 가정이 성립할리가 없기에 해당 상황은 얼마든지 일어날 수 있음을 알아야 합니다.

 

---

 

이런 문제가 있는데 machine learning이 왜 그렇게 사람들 사이에서 좋게 회자되는 것일까요? 사실 이러한 모델들은 굉장히 초기 모델들이고, 앞으로 다룰 machine learning 내지 deep learning model들은 이러한 문제가 어느정도 제거되었기 때문에 쓸 수 있는 것입니다. 말 그대로 introduction인 만큼, warming up을 했다고 생각하면 좋을 것 같습니다.

 

다음 포스팅에서 뵙겠습니다.