Week 2.2 Introduction to Rule Based Algorithm

1. Find - S Algorithm

Find - S Algorithm : h0 로 부터 특정한 Coverage를 가진 h를 찾아나가는 과정

 

1. 초기 h0는 null로 setting => 어떠한 경우의 조건도 만족시키지않는다.

2. Instance x1과 h0의 각각 feature를 비교해 합집합을 만들어 새로운 h1을 만든다.

( 즉 x1의 첫번째 Sunny 와 h0의 null의 합집합은 Sunnny 라 h1의 첫번째는 Sunny 가 된다. )

3. Instance x2 와 h1을 비교한다.

(4번째 feature 인 x2의 Light 와 h1의 Strong 이 다르다. 즉 h1 가설의 Strong 이 아니더라도 x2를 통해 Enjoy sport를 한다는것을 학습하게 된다. Strong 과 Light 를 union 하면서 Don't care 로 바뀐다. (?) )

 

VS 는 여러 Hypotheses의 집합이다.

2가지 Boundary 를 잡아야 한다. 

1) General Boundary : G

2) Specific Boundary : S

 

 

2. Candidate Elimination Algorithm

특정 version space를 만들기위해 가장 specific 한 가정 , 가장 general 한 가정을 만들어서 boundary 를 좁혀나가는것.

 

S0은 instance에 있는 feature들을 cover 할수 있는 만큼만 generalize 시킨다.

G0은 specific 한 case가 negative로 판정 안하면 제외시킨다.

 

아래의 예시를 살펴보자.

S0은 무조건 Enjoy sport을 안하기 때문에 에러를 만든다. 그래서 첫번째 instance를 보고 S1처럼 hypothesis를 relax 시켜준다. 그다음 두번째 instace를 통해 Humid 를 Don't care ( ? ) 로 generalize 시킨다.

 

1.Specific

S2에 의해 generalize 된 Humid part의 ?(Don't care)는 specific 하게 만들수 없다.

 

2.Generalize

세번째 Instace를 가장 General 한 G0,G1,G2 의 Hypothesis를 보고 판별하면 Enjoy sport 를 해야하지만 결과는 그렇지 않기 때문에 Error 가 발생한다.

그러면 Hypothesis를 좀더 Specific 하게 만들어야한다.

그래서 Rainy , Cold , Chagne 의 part를 통해 조금 더 Specific 하게 만들수 있다. (G3)

 

<Sunny , ?,?,?,?,? >을 만들어 Rainy 일 경우에 EnjoySport를 안하게 만들수 있다.

<? , Warm,?,?,?,? >을 만들어 Cold 일 경우에 EnjoySport를 안하게 만들수 있다.

<? , ?,?,?,?,Same >을 만들어 Change 일 경우에 EnjoySport를 안하게 만들수 있다.

 

 

1. Specific

네번째 Instace 와 S2,S3의 H를 비교해보면 Water의 Cool , Warm 이 다르지만 Enjoy sport가 Yes이기 때문에 ?로 변경된다. Forecast 도 Same , Change 가 다르지만 ?로 변경할수 있다.

그렇게 되면 S4 :(Sunny,Warm, ?,Strong,?,?) 로 좀더 Specific 하게 만들수 있다.

 

2. Generalize

네번째 Instace와 G3의 <?,?,?,?,?,Same> 와 비교해보면 네번째 Instace는 G3의 조건을 만족시키지 못하지만 Enjoy sport는 Yes 이다. 즉 G3의 <?,?,?,?,?,Same>를 Drop 시킨다.

 

여전히 많은 Hypothesis가 있을수 있다. 그중에서 True functiton C를 찾는것이 Rule based Learning 이다.

 

<Sunny, Warm , Normal , Light , Warm , Same>이라는 Instace를 General H 와 Specific H를 통해 판변해보자.

그러면 S를 통해 보면 Enjoy Sport가 No 이지만 , G를 통해보면 Enjoy Sport 가 Yes 이다.

이런 경우 판정을 어떻게 해야할까? 충분한 Data가 없어 결정을 내리지 못하는 상황이 되버렸다.

이런것이 Rule based learning 이 여러 분야에 쓰이기 쉽지 않은점이 된다.