edwith에 올라와있는 문인철 교수님의 인공지능 및 기게학습 개론1을 공부하여 정리한 내용입니다.

A Perfect World for Rule Based Learning

• Rule Based Learning을 사용하기 위해서는 perfect world 라는 가정이 필요하다.
  - No observation errors, No inconsistent observations
  - No stochastic elements in the system we observe
  - Full information in the observations to regenerate the system

Function Approximation

• 머신러닝은 어떻게 하면 Function Approximation을 잘할 수 있는가와 유사하다.
• 스포츠를 즐기기 좋은 날을 예시로 들어 보자.
• Instance X
  - Features: O: <Sunny, Warm, Normal, Strong, Warm, Same> - input 값
  - Label: Y: \ - 실제 판단 근거
• Training Dataset D
• Hypotheses H
  - Potentially possible function to turn X into Y
  - $h_i$: <Sunny, Warm, ?, ?, ?, Same> -> Yes
  - 여러개의 Hypotheses가 존재 가능하다
• Target Function c - 알지 못하지만 목표로 하는 함수
  
• 우리는 Datasets으로부터 General과 Specific 사이에서 적절한 Hypotheses를 찾아야 한다.
• 그림에 나와있는 것처럼 General Hypotheses는 Instance Space에서 넓은 공간을 가지고 Specific한 Hypotheses는 Instance Space에서 좁은 공간을 가진다.

Find-S Algorithm

• 간단한 Rule-based Algorithm의 예시이다

Pseudo code

• 가장 Specific한 Hypotheses H를 세운다.
• 데이터셋에서 한개(x)를 뽑을 것이고 모든 데이터를 이용할 것이다.
  - 만약 x가 positive라면
  - 이 x의 feature에 모든 feature에 대해서
  - 만약 x의 feature와 Hypotheses H의 Feature h와 같다면 아무 것도 하지 않는다.
  - 다르다면 둘을 Union 해준다.
  

Version Space

• 실제로는 Find-S Algorithm은 많은 hypotheses들이 가능하다.
• 그래서 특정 Hypotheses를 찾는다기보다는 범위를 찾는다고 볼 수 있다.
• 이 범위를 Version Space라고 한다.
• 즉, General Boundary G와 Specific Boundary S사이의 모든 hypothesis를 Version Space라고 할 수 있다.
• 

Candidate Elimination Algorithm

• 가장 General hypothesis와 가장 Specific hypothesis를 찾아내서 이를 점점 좁혀서 Version Space를 찾는 방법이다.

Pseudo Code

• For instance x in D
  - If y of x is positive # Specific 한 H를 Generalize하게 만들어줌
  - Generalize S as much as needed to cover o in x
  - Remove any h in G, for which h(o)≠y
  - If y of x is negative # General한 H를 Specific하게 만들어줌
  - Specialize G as much as needed to exclude o in x
  - Remove any h in S, for which h(o)=y
• 
• 이렇게 줄여나가도 여전히 많은 h가 있고 그 중 하나가 우리가 생각하는 function c인지 않을까 생각하는 게 Rule-based Learning이다.
• 
• <Sunny, Warm, Normal, Light, Warm, Same> 예시로 보면,
• Specific한 hypothesis에는 맞지 않지만 General한 hypothesis에는 적합하다.
• 이와 같은 단점 때문에 Rule-based Algorithm은 모든 Task에 사용하기에는 적합하지 않다.

Is this working?

• Perfect World에서 candidate-elimination algorithm converge에서는 돌아간다.
• 하지만 우리가 perfect world에 살고 있지 않기 때문에 우리가 찾고 있는 정확한 hypothesis가 noise때문에 지워질 수도 있다.
• 이러한 noise를 다룰 수 있는 방법은 여러가지가 있고 우리는 이러한 방법 중 하나인 Decision Tree를 다음 시간에 배워볼 것이다.