Bayes Theorem and Concept Learning

Bayes Theorem and Concept Learning

이제 베이즈 정리와 concept learning간에 어떤 관계가 있을지 생각해보자.

Brute-Force Bayes Concept Learning

instance $<x_1, \cdots,x_m>$이 있고, training data D를 $D = \;<d_1, \cdots, d_m>$ 이라 해보자.

Brute-Force MAP Learning

1. For each hypothesis $h$ in $H$, calculate the posterior prob$\\$
   $P(h|D) = \frac{P(D|h)P(h)}{P(D)}$ $\\$
   $\\$ 2. Output the hypothesis $h_{MAP}$ with the highest posterior prob
   $\\$$\\$
   $h_{MAP} = \underset{h\in H}{\mathrm{argmax}}\;P(h|D)$

그러나, 이는 사실상 계산이 불가능하다. 예전의 enjoysports의 경우만 생각하더라도 무려 5120개의 h가 있다고 한다.
따라서, 브루트포스 방법을 사용하려면 $P(h)$와 $P(D|h)$를 specify해야 한다.

---

그렇다면 어떻게 $P(h)$와 $P(D|h)$를 specify해야 할까?

먼저, 문제를 쉽게 생각하기 위해 다음과 같은 3가지 가정을 해보자

1. training data $D$ is noise free, $d_i = c(x_i)$ where $c : X \to \left \{0, 1 \right \}$
2. target concept $c$ is contained in hypothesis space $H$
3. believe that any h is more probable than any other $\to$ uniform

이 3가정을 통해, 먼저 $P(h)$를 specify해보자

즉, uniform distribution을 만든다.

$P(D|h)$ 는 다음처럼 specify 한다.

그렇다면 두가지 경우가 있을 수 있다

• $h$ is inconsistent with $D$
  $\\$
  $P(h|D) = \frac{P(D|h)P(h)}{P(D)} = \frac{0\cdot P(h)}{P(D)} = 0$

• $h$ is consistent with $D$
  $\\$
  $p(h|D) = \frac{P(D|h)P(h)}{P(D)} = \frac{1 \cdot \frac{1}{|H|}}{P(D)} = \frac{1 \cdot \frac{1}{|H|}}{\frac{|VS_{H,D}|}{|H|}} = \frac{1}{|VS_{H,D}|}$

즉, 최종적으로 다음처럼 표현이 가능해진다.

Remark
1. every consistent h has posterior prob $\frac{1}{|VS_{H,D}|}$
2. every consistent h is a MAP hypothesis!