Version  Space

Tom Mitchell : "Version Spaces: A Candidate Elimination Approach to Rule Learning", T.M. Mitchell, Proceedings of the 5th International Joint Conference on Artificial Intelligence, Cambridge MA, August 1977, pp. 305-310.

버전공간 (Version Space) : 이재규 : Tom Mitchell 은 사례로부터 단일개념을 학습하는 하나의 틀을 제공하였다. 그는 먼저 개념의 표현에서 그것의 일반화된 정도에 따라 순서를 매길 수 있다고 보았다. 예를 들어, 다섯 장의 카드에 대해서 ∃c₁ : RED(c₁) 은 다섯장 중 적어도 한 장은 빨간색이다라는 것이며, 이는 적어도 두 장이 빨간색이다라는 뜻인 ∃c₁, c₁ : RED(c₁) ∧ RED(c₂) 보다는 일반적이다. 왜냐하면 적어도 두 장의 빨간색 카드를 가지는 모든 다섯 장의 카드의 조합이 빨간색 한 장만 가지는 경우에 포함되기 때문이다. 이렇게 일반화의 정도에 따라 규칙공간의 모든 개념들의 순서를 매길 수 있다. 훈련사례만 주어진 초기 상태에서 가장 구체적인 개념은 훈련사례 그 자체가 될 것이고, 가장 일반적인 개념은 널 (Null) 진술로서 모든 것을 다 포괄하는 개념 - 즉, 모든 제약과 조건이 떨어진 사례 전체를 일컫는 진술 - 이 될 것이다.

그림 3  규칙공간의 도해

이러한 규칙공간에서 선택가능한 가설집합 H 를 상정할 때 H 중 가장 일반적인 것들을 G 집합이라 하고, 가장 구체적인 집합을 S 라 하자. 그러면 H 는 G 와 S 로 경계지어지는 집합이 될 것이다. Mitchell 은 이러한 가설집합 H 를 사례에 아직 저촉되지 않은 가설집합이라 하고 이를 버전공간 (Version Space) 라 불렀다. 따라서 버전공간 H 는 현재까지 제시된 모든 사례를 수용하는 규칙공간이 된다.

그림 4  규칙공간에서 G 와 S 집합을 경계로 하는 부분공간

Mitchell 은 이러한 버전공간 중 필요한 개념을 생성하는 학습과정을 대안제거 학습알고리즘 (Candidate-elimination Learning Algorithm) 이라 하였다. 이는 처음에 집합 H 는 모든 표현가능한 개념으로서 구성되지만 훈련사례가 주어지게 되면서 그것에 저촉되는 대안개념 (Candidate Concept) 들이 버전공간에서 제거되게 된다. 이러한 제거과정에서 마지막까지 남는 대안개념이 찾고자 하는 개념이 되는 것이다. 긍정사례 (Positive Instance) 가 주어지면 이를 포함하는 개념이 제거되며 따라서 구체화로 진행된다. 그런데 이러한 진행과정은 최소한의 일반화 및 구체화과정만을 허락하고 필요 이상은 진행하지 않는다. 즉, 긍정사례가 주어졌을 때 해당 사례를 포함할 수 있는 최소한의 일반화, 다시 말하면 해당 사례를 포함하는 것 중 최대의 구체화만을 수행한다는 것이다. 이런식으로 집합 H 는 차츰 좁혀지며 결국 우리가 원하는 개념만이 남게 된다.