규칙기반학습(Rule-Based Learning)

1. 규칙기반학습(Rule-Based Learning)

주어진 입력에 대해서 결과값을 도출하는 방법으로 if-then 방식이라고도 한다. 확고한 규칙(rule)에 따라 학습 및 예측을 하는 방법이다.

좀 더 자세히 이해하기 위해 대표적인 예제인 기상데이터를 가지고 알아보도록 하자.

날씨에 따라 나가서 놀 것인지 아닌지 결정하는 예제이다.

위의 예제는 많은 가설(h)들이 존재한다.

예를 들어, <Sunny, Warm, ?, ?, Warm, ?>일 때 EnjoySpt는 yes라는 가설을 세울 수 있다.

여기서 ‘?’는 don’t care를 의미한다.

2. Find-S Algorithm

위의 예제에서 EnjoySpt가 yes일 조건을 최대한 만족할 수 있는 가설을 찾기 위해 Find-S 알고리즘을 사용하여 찾을 수 있다.

Initialize h to the most specific hypothesis in H

For each positive training instance x

For each attribute constraint in h

IF the constraint  in h is satisfied by x THEN

                                           do nothing

ELSE

                                           replace in h by next more general constraint

satisfied by x

Output hypothesis h

다음과 같이 Instance X 에 대해 최대한 만족할 수 있는 가설을 찾아 나가면 된다.

하지만, Find-S 알고리즘은 consistent한 가설(or data)이라고 가정하므로 inconsistent한 가설(or data)에는 적합하지 않다. 또한, 너무 Specific한 h를 선택하게 되면 다른 가능한 가설들에 대해서 수렴하지 못하는 문제가 있다.

3. Version Space

Tom Mitchell이 제안한 방법으로 가설의 표현에서 그것의 일반화된 정도에 따라 순서를 매길 수 있다고 보았다. 예를 들어, 다섯 장의 카드가 있다고 하자. 이 다섯 장의 카드에 대해서 ‘다섯 장 중 적어도 한 장은 빨간색이다’라는 가설이 ‘다섯 장 중 적어도 두 장이 빨간색이다.라는 가설보다는 일반적(General)하다. 왜냐하면 적어도 두 장의 빨간색 카드를 가지는 모든 다섯 장의 카드의 조합이 빨간색 한 장만 가지는 경우에 포함되기 때문이다. 이렇게 일반화의 정도에 따라 규칙공간의 모든 가설들의 순서를 매길 수 있다. 훈련사례만 주어진 초기 상태에서 가장 구체적인(Sepcific)한 가설은 훈련사례 그 자체가 될 것이고, 가장 일반적인 가설은 널(Null) 가설로써 모든 것을 다 포괄하는 가설이 된다. 이러한 가설들의 집합을 Version Space라고 한다.

4. 대안제거 알고리즘(Candidate Elimination Algorithm)

처음에 가설집합 H는 모든 표현 가능한 가설들로 구성되지만 훈련사레가 주어지게 되면서 그것에 저촉되는 대안 가설들이 Version Space에서 제거된다. 이러한 과정을 통해 마지막까지 남는 가설이 찾고자 하는 가설이 된다. Positive Instance가 주어지면 이를 포함하는 개념이 제거되며 구체화(Specific)으로 진행된다.

Input: training set

Output:

• G = maximally general hypotheses in H

• S = maximally specific hypotheses in H

Algorithm: For each training example d, do

• If d is a positive example

– Remove from G any hypothesis inconsistent with d

– For each hypothesis s in S that is not consistent with d

∗ Remove s from S

∗ Add to S all minimal generalizations h of s such that (a) h is consistent with d, and (b) some member of G is more general than h

∗ Remove from S any hypothesis that is more general than another hypothesis in S

• If d is a negative example

– Remove from S any hypothesis inconsistent with d

– For each hypothesis g in G that is not consistent with d

∗ Remove g from G ∗ Add to G all minimal specializations h of g such that (a) h is consistent with d, and (b) some member of S is more specific than h

∗ Remove from G any hypothesis that is less general than another hypothesis in G

다음 아래의 그림은 기상데이터의 가설에 대한 Candidate Elimination Algorithm을 그림으로 나타낸 것이다.

(출처 : http://ml.informatik.uni-freiburg.de/_media/documents/teaching/ss11/ml/02_versionspace.printer.pdf)