버전 공간 학습

Version space learning
2차원의 "직각" 가설 언어에 대한 버전 공간입니다.녹색 플러스는 긍정적인 예시이고 빨간색 원은 부정적인 예시입니다.GB는 최대 일반 긍정 가설 경계이고, SB는 최대 특이적 긍정 가설 경계입니다.중간(얇은) 직사각형은 버전 공간의 가설을 나타냅니다.

버전 공간 학습은 기계 학습, 특히 이진 분류에 대한 논리적 접근법입니다.버전 공간 학습 알고리즘은 논리적인 문장 집합으로 간주되는 사전 정의된 가설의 공간을 검색합니다.공식적으로, 가설 공간은 분리[1] 공간이다.

(즉, 가설 1이 참이거나 가설 2 또는 가설 1에서 n까지의 부분 집합 중 하나임)버전 공간 학습 알고리즘은 가설 공간을 제한하기 위해 사용하는 예를 제시합니다. 각 예 x에 대해 [2]x와 일치하지 않는 가설은 공간에서 제거됩니다.이 가설 공간의 반복적인 미세화는 후보 제거 알고리즘이라고 불리며, 알고리즘의 버전 [1]공간 내에 유지되는 가설 공간입니다.

버전 공간 알고리즘

가설에 대한 일반 순서가 있는 환경에서는 버전 공간을 (1) 가장 구체적인 일관된 가설과 (2) 가장 일반적인 일관된 가설의 두 가지 집합으로 나타낼 수 있습니다. 여기서 "일관성"은 관측된 데이터와 일치함을 나타냅니다.

가장 구체적인 가설(즉, 특정 경계 SB)은 관찰된 양성 훈련 예제를 포함하며 가능한 한 나머지 특징 공간은 거의 없다.이러한 가설은 더 이상 줄어들면 긍정적인 훈련 사례를 배제하고, 따라서 일관성이 없어진다.이러한 최소 가설은 기본적으로 진정한 개념은 이미 관측된 양의 데이터에 의해 정의된다는 (비정론적) 주장을 구성합니다.따라서 새로운(예전에는 볼 수 없었던) 데이터 포인트가 관찰되면 음으로 간주해야 한다(즉, 데이터가 이전에 규칙화되어 있지 않은 경우에는 제외된다).

가장 일반적인 가설(즉, 일반 경계 GB)은 관찰된 긍정적인 훈련 예제를 포함하지만 부정적인 훈련 예제를 포함하지 않고 나머지 특징 공간의 많은 부분을 포함한다.더 확대하면 부정적인 훈련 사례가 포함되므로 일관성이 없어집니다.이러한 최대 가설은 기본적으로 진정한 개념은 이미 관측된 음의 데이터에 의해 정의된다는 (낙관적인) 주장을 구성합니다.따라서, 새로운(예전에는 볼 수 없었던) 데이터 포인트가 관찰된 경우, 양수라고 가정해야 한다(즉, 데이터가 이전에 배제되지 않은 경우, 해당 데이터 포인트는 제외된다).

따라서 학습 중에 버전 공간(그 자체가 모든 일관된 가설을 포함하는 집합일 수 있음)은 하한과 상한(최대 일반 및 최대 특정 가설 집합)으로 표현될 수 있으며, 이러한 대표 집합에 대해서만 학습 연산이 수행될 수 있다.

학습 후 알고리즘에 의해 학습된 가설을 테스트함으로써 보이지 않는 예에 대해 분류할 수 있다.예제가 다중 가설과 일치하는 경우 다수결 규칙을 [1]적용할 수 있습니다.

이력

버전 공간의 개념은 1980년대[2] 초에 솔루션 검색의 맥락에서 감독 학습의 기본 문제를 이해하기 위한 프레임워크로 Mitchell에 의해 도입되었다.버전 공간 프레임워크에 부수되는 기본적인 "후보 제거" 검색 방법은 일반적인 학습 알고리즘은 아니지만, 개발된 몇 가지 실용적인 구현이 있다(예: Sverdlik & Renolds 1992, Hong & Tsang 1997, Dubois & Quafou 2002).

버전 공간 학습의 주요 단점은 노이즈를 처리할 수 없다는 것입니다. 일관되지 않은 예시는 버전 공간을 붕괴시킬 수 있습니다. 즉, 빈 공간이 되어 분류가 [1]불가능해질 수 있습니다.이 문제의 한 가지 해결책은 Dubois와 Quafou에 의해 제안되어 대략적인 버전 [3]공간을 제안했다. 대략적인 집합 기반 근사치는 일관성 없는 데이터가 존재하는 상황에서 특정되고 가능한 가설을 학습하는 데 사용된다.

「 」를 참조해 주세요.

  • 정식 개념 분석
  • 유도 로직 프로그래밍
  • 거친 세트.[개략적인 집합 프레임워크는 피처셋에 의해 모호성이 도입되는 경우에 초점을 맞추고 있습니다.즉, 사용 가능한 피쳐 세트를 사용해도 다른 카테고리에 속하는 오브젝트를 명확하게 할 수 없기 때문에 타깃 개념을 명확하게 설명할 수 없습니다.버전 공간 프레임워크는 빈곤한 데이터 세트에 의해 모호성이 도입되는 (고전적 유도) 사례에 초점을 맞춘다.즉, 이용 가능한 데이터가 가설을 고유하게 추출하지 못하기 때문에 대상 개념을 결정적으로 설명할 수 없습니다.당연히 두 가지 유형의 모호성은 같은 학습 문제에서 발생할 수 있습니다.]
  • 귀납적 추론.[인덕션의 일반적인 문제에 대해서]

레퍼런스

  1. ^ a b c d Russell, Stuart; Norvig, Peter (2003) [1995]. Artificial Intelligence: A Modern Approach (2nd ed.). Prentice Hall. pp. 683–686. ISBN 978-0137903955.
  2. ^ a b Mitchell, Tom M. (1982). "Generalization as search". Artificial Intelligence. 18 (2): 203–226. doi:10.1016/0004-3702(82)90040-6.
  3. ^ Dubois, Vincent; Quafafou, Mohamed (2002). "Concept learning with approximation: Rough version spaces". Rough Sets and Current Trends in Computing: Proceedings of the Third International Conference, RSCTC 2002. Malvern, Pennsylvania. pp. 239–246. doi:10.1007/3-540-45813-1_31.
  • Hong, Tzung-Pai; Shian-Shyong Tsang (1997). "A generalized version space learning algorithm for noisy and uncertain data". IEEE Transactions on Knowledge and Data Engineering. 9 (2): 336–340. doi:10.1109/69.591457.
  • Mitchell, Tom M. (1997). Machine Learning. Boston: McGraw-Hill.
  • Sverdlik, W.; Reynolds, R.G. (1992). "Dynamic version spaces in machine learning". Proceedings, Fourth International Conference on Tools with Artificial Intelligence (TAI '92). Arlington, VA. pp. 308–315.