머신 러닝 정리 3 - 룰 베이스 알고리즘이란?

머신러닝이란?

경험에 의해 배우는 프로그램

경험에 의해 특정 테스크의 수행능력이 점차 향상 된다. 

즉, 더 많은 경험이 쌓이면 (혹은 더 많은 사전 지식) 머신러닝의 성능이 점차 좋아질 것이라 기대된다. 

 

Rule Based Learning

이상적인 세상 가정 

관측 에러 X 

모든 것은 일관적 관측 

아래의 종류만으로 결과를 완벽하게 설명 가능 

Sky	Temp	Humid	Wind	Water	Forecast	EnjoySpt
Sunny	Warm	Normal	Strong	Warm	Same	Yes
Sunny	Warm	High	Strong	Warm	Same	Yes
Rainy	Cold	High	Strong	Warm	Change	No
Sunny	Warm	High	Strong	Cool	Change	Yes

 

Function Approximation 

머신러닝의 목표라고도 할 수 있다. 

현실을 잘 반영하는 함수 

 

Instance X 

Features: O : <Sunny, Warm, Normal, Strong, Warm, Same>

Label: Y: <Yes>

 

Training Dataset D 

Instance 관측치 모음 

 

Hypothesis H

X 를 Y 로 변환하는 잠재적으로 가능한 함수  

$h_i$: <Sunny, Warm, ?, ?, ?, Same> $\rightarrow$ Yes

다양한 가설이 가능하다. 

 

Target Function c

알지 못하나, 데이터를 통해 추론해서 목표로하는 함수 즉 h 를 c 로 만드는 것이 목표 

위 그림을 살펴보자. 위 그림의 오른 쪽 Hypothesis H $h_i$ 에 해당하는 Instance X $x_i$ 를 확인해보자. 

각 가설에 따라 해당하는 instance를 확인할 수 있다. 

이 그림이 룰 베이스를 설명한다. 즉, 룰베이스는 필터링 마냥 각각의 룰에 해당하는 것을 거르고 걸러 우리가 원하는 값을 찾을 수 있는 함수를 근사하는 것이다. 

 

Find-S Algorithm

가설 h 에 대하여, 

• D 의 instance x 가 만약 positive 이면, 
• instance x 의 feature f 가 가설 h 에 해당되는지 확인
• 만약, 포함되지 않으면 $h \cup f_i \in x$  

한마디로 정리하자면, instance x 가 positive 임에도 가설에서 해당되지 않던 내역을 가지고 있으면 가설에 추가하게 되는 것이다. 

 

아래 예시를 살펴보자. 

 

Instances

$x_1$ : <Sunny, Warm, Normal, Strong, Warm, Same>

$x_2$ : <Sunny, Warm, Normal, Light, Warm, Same>

$x_4$: <Sunny, Warm, Normal, Strong, Warm, Change>

 

Hypotheses 

$h_0$ = <$\emptyset, \emptyset, \emptyset, \emptyset, \emptyset, \emptyset$>

$h_1$ = <Sunny, Warm, Normal, Strong, Warm, Same>

초기 instance $x_1$ 에 대하여 update 

$h_{0,1,2}$ = <Sunny, Warm, Normal, ?, Warm, Same>

instance $x_2$ 로 인해 Strong 이 아닌 Light 여도 postivie 임을 확인 (합집합)

$h_{0,1,2,4}$ = <Sunny, Warm, Normal, ?, Warm, ?>

instance $x_4$ 로 인해 Same 이 아닌 Change 여도 postivie 임을 확인 (합집합)

 

$h_{0, 1,2, 4}$ 가 실제 함수를 올바르게 근사할까? 사실 알 수 없다. 다른 feature들도 여러 요소를 허용할 수도 있기에, 가능한 가설이 다양하다. 

Version Space

가능한 여러 가설을 하나로 정리하기 어렵다. 

이에 따라 범위를 찾아내는 방법이 제시되었다. 이를 version space라 한다. 

범위를 제안하기 위하여 boundary 설정이 필요하다. 

 

General Boundary G

set of the maximally general hypotheses of the version space

 

Specific Boundary S

set of the maximally specific hypotheses of the version space 

 

Every Hypothesis h, satisfies

$\textrm{VS}_{H,D} = \{ h \in H | \exists s \in S, \exists g \in G, g \leq h \leq s \}$

 

정의만 봤을 때는 G 와 h 의 차이가 직관적으로 다가오지 않는다.  

 

아래 도표를 살펴보자. 

직관적으로 넓게 잡은 범위는 가능한 상황을 모두 가능하다고 가설을 세우는 것이다. 

그러나 좀 좁게 잡은 범위는 가능한 상황이 더 있더라도 specific 하게 예측할 수 있는 경우는 specific 하게 가설을 세우는 것이다. 

 

Candidate Elimination Algorithm

Version space를 만들기 위해서 가장 General, Specific 한 가설을 생성한 후, 점점 좁혀나가서 특정 version space 만을 찾아내는 알고리즘이다. 

 

S 를 가능한 specific 하게 초기화 한다. 

$\textrm{S0}$ : {< $\emptyset, \emptyset, \emptyset, \emptyset, \emptyset, \emptyset $ >}

G 를 가능한 general 하게 초기화 한다. 

$\textrm{G0}$ : {< $?, ?, ?, ?, ?, ?$ >}

 

D 에 있는 각각의 instance x 를  통하여 타겟 값을 좁혀나간다. 

 

만약 x 의 label y 가 postive 라면, 

• S 를 최대한 x 를 포함하는 general 한 범위로 일반화한다. 
• label 을 추론하는데 해당되지 않는 즉, $h(o) != y$인 h를 G 에서 제거한다. 

 

만약 x 의 label y 가 negative 라면, 

• x의 o(feature) G에서 제거할 수 있는 만큼 제거한다. 
• S 에 속한 $h(0) = y$ 의 h 를 제거한다. 

 

$\exists s \in S, \exists g \in G, g \leq h \leq s$ 를 만족하는 h 를 생성한다. 

아래를 살펴보자. 

Candidate Elimination Algorithm 의 과정

Specific, Generalize 하게 업데이트 되는 것을 확인할 수 있다. 

Negative 한 케이스가 업데이트 되는 것도 확인할 수 있다. 

다만, 어떠한 요소때문에 Negative 가 된지 알 수 없으므로 위와 같이 G 가 결정된다. 

 

마지막 케이스를 통해 업데이트를 마쳤다. 그러나 여전히 G 과 S 사이에 여러 가설이 존재할 수 있다. 이 중 하나가 True 값일것이라 기대하며 learning 하는 것이 rule based 방법이다. 

 

추가적으로 새로운 instance 가 들어오면 version space 를 점점 더 narrow down 할 수 있다. 

 

해당 version space를 기반으로 classification 이 가능해진다. 

 

Specific Boundary S

{<Sunny, Warm, ?, Strong, ?, ?>}

 

General Boundary G

{ <Sunny, ?, ?, ?, ?, ? >, <?, Warm, ?, ?, ?, ?> }

 

new instance

<Sunny, Warm, Normal, Strong, Cool, Change>

S 도 통과했으므로 OK 

 

<Rainy, Cold, Normal, Light, Warm, Same>

G 도 통과하지 못하므로 NO

 

<Sunny, Warm, Normal, Light, Warm, Same>

S 는 통과하지 못하나 G 는 통과한다. 즉 해당 instance 는 결정을 못내리는 상황이다. Rule based learning 은 이러한 문제점을 가지고 있다. 

 

위에서 살펴본 Candidate - elimination algorithm 은 아주 이상적인 세상에서만 사용가능하다. 

데이터가 계속 들어오면 이상적인 세상에서는 True function 으로 converge 하게 될 것이다. 

 

이상적인 세상의 조건은 상단에서 언급했다. 

즉, 현실에서는 노이즈가 낀다는 것을 감안해야하고, Decision factor(feature) 또한 관측하지 못한 것이 있을 수 있다.