PAC

PAC Learnability

PAC learnability

1) Hypothesis class H is PAC learnable means / there exist sample complexity m_H with ε and δ .

2) With a sample whose cardinality is more than sample complexity m_H, / Algorithm A returns hypothesis class H with ε and δ / s.t generalization error is less than ε.

3) lower bound of sample complexity is m_H with ε and δ.

4) m_H is less than supremum of  log, cardinality of hypothesis class H over δ, over ε.

샘플을 늘리면 추론과 실제의 차이(error)가 작아질 것이다. 특정 에러 이하, 오차범위 내에서는 추정치=실제값 으로 한다.

통계에서 신뢰구간, 신뢰수준 개념 참고.