Introduction to Rule Based Algorithm

Find S Algorithm

• Initialize h to the most specific in H
• empty set -> include x1 -> include x2 ... -> include xn
  

Version Space

• Many hypotheses possible, and No way to find the convergence
• Need to setup the perimeter of the possible hypothesis
• The set of the possible hypothesis == Version Space, VS
  • General Boundary, G
  • Specific Boundary, S
    

Candidate Elimination Algorithm

• initialize S to maximally specific h in H
• initialize G to maximally general h in H
• positive: change S
• negative: change G
  

Progress

How to classify the next instance?

• Some example
  • General boundary -> O
  • Speicific boundary -> X
  • ???? => disadvantage of rule based learning

Is this working?

• working on the perfect world
• but we don't live in the perfect world
  • any noise in o of D
  • decision factor other than o of x
  • a correct h can be removed by the noise -> cannot say yes and no