2.2. Introduction to Rule Based Algorithm

Find-s Algorithm : D에 있는 모든 x instance 중에서, x가 positive라고 한다면 모든 feature를 판단한다.

Hypothesis의 값과 feature의 값이 다르면 아무런 행동을 하지 않지만, 두 값이 다르면 Hypothesis의 값을 수정하여 이 경우에서도 나감을 포함시켜준다.

 

예시)

h0 = <null, null, null, null, null, null> : 어떠한 경우에서도 나가놀지 않은 경우

이 때, x1 = <Sunny, Warm, Normal, Strong, Warm, Same> 일 때 나가놀았다면 h0과 x1을 합집합하여

h1 = <Sunny, Warm, Normal, Strong, Warm, Same>로 변경한다.

x2 = <~, Light, ~> 일 때도 나가 놀았다면 h1의 Strong과 x2의 Light을 union하면 ?로 변경한다.

>> 특정한 instance에 대한 coverage를 가지고 있는 특정 hypothesis를 만든다.

 

Version Space : 특정 범위를 찾아서 그 범위 내의 possible hypthesis의 perimeter를 만든다.

두 가지의 boundary를 잡는다. 첫 번째는 General Boundary, 두 번째는 Specific Boundary 이다.

여러 hypothesis의 집합으로, general한 것보다는 specific하고, specific한 것 보다는 general하다.

 

Candidate Elimination Algorithm : 특정 Version Space를 만들기 위해 가장 specific한 가설과 가장 general한 가설을 만들고 boundary를 좁힙으로써 하나의 범위를 만들수 있다.

1. 가장 specific한 hypothesis인 S를 만든다.

2. 가장 general한 hypothesis인 G를 만든다.

3.

Datas = "상황에 따른 데이터"
for x in Datas:
    #데이터의 label이 참이라면:
    if y of x is postivie:
        """specific한 범위인 S에서 y에 대해 positive가 나올 수 있도록
        Generalize한다."""
        """단, instance에 대한 feature을 커버할 수 있을만큼만 generalize."""
        """단, G에 대해서 성립하지 않는다면 이 instance를 버린다."""
        
    elif y of x is negative:
        """G를 좀 더 specific하게 만들어주어야 한다."""
        """S에서 x라는 경우의 수를 없애준다."""

>> 양쪽을 조금씩 고쳐나가는 알고리즘이다.

 

Classifying nest instance:

만약 G를 만족하지만 S를 만족하지 않는다면 이 instance를 어떻게 예측할 것인가? 

>> 이러한 단점 때문에 여러 분야에서 쓰이기가 어렵다.

 

Limitation of Rule Based Algorithm:

observed system라는 perfect world에선 많은 데이터를 통해 true or false를 구별할 수 있다.(모든 조건이 observation에 담을 수 있다.)

하지만 우리는 perfect world에 살고 있지 않다. 노이즈가 발생할 수 있고, 정말 많은 Decision factor가 발생할 수 있다. 

맞는 hypothesis임에도 불구하고 노이즈에 의해 제거되는 limitation이 발생한다.