2.2. Introduction to Rule Based Algorithm

Files: https://strutive07.github.io/assets/images/2_2_Introduction_to_Rule_Based_Algorithm/IE661-Week_2-Part_1-icmoon-ver-1.pdf last update datetime: Jan 04, 2020 2:10 PM

Find-S algorithm

instance x 를 가장 잘 표현하는 hypotheses를 찾는 알고리즘.

현재 hypotheses에 참인 instance가 있으면 합집합으로 합치면서 hypotheses를 갱신.

Version space

답이 될 만한 hypotheses의 집합 == version space

• General boundary G
  • VS의 가장 general한 hypotheses
• Specific boundary S
  • VS에서 가장 specific gks hypotheses

Candidate Elimination algorithm

Version space를 찾기 위한 algorithm

1. 초기화
   • 가장 specific 한 hypotheses 설정하기 as S
     • 전부 negativ야! 라고 판단
   • 가장 general 한 hypotheses 설정하기 as G
     • 전부 positive야! 라고 판단
2. For instance x in Data
   1. positive data 라면?

      1. S 를 최소한으로 일반화

         

      2. 그리고 해당 데이터를 false로 판단하는 G 삭제

   2. negative data 라면?

      1. G를 최소한으로 spefic하게 변화

         

      2. 그리고 해당 데이터를 true로 판단하는 S 삭제

계속 수렴하면 가능함. 단, perfect world에서만 가능