Supervised Learning Terminology

Instance Space : 가능한 모든 sample들의 집합

Hypothesis Space : 가능한 모든 가설들의 집합

- 예시 : 가능한 모든 정사각형

 

Empirical Error : 가설과 training set과의 error

Generalization Error : Future Sample 까지 고려한 error but 알 수 없음 ( target concept이 무엇인지 모르므로?)

Margin : Hypothesis 의 boundary 와 가장 가까운 instance 사이의 거리

- Margin이 큰 hypothesis? Or 작은 hypothesis? 어느게 더 좋은 것인가?

 

Consistent(h,D) : Empirical Error가 zero이다.

Most specific hypothesis : Consistent 한 가설 중 가장 작은 크기의 hypothesis

Most general hypothesis : Consistent 한 가설 중 가장 작은 크기의 hypothesis

Version space(D,h) : Given training set, consistent 한 가설들의 집합

 

Vapnik-Chervonenkis Dimension(VC dimension) : Hyposthesis Space가 shatter 할 수 있는 집합 중에서 가장 큰 집합의 원소의 개수

- Shatter : N points, Binary Label의 경우 2^N의 경우를 모두 분류할 수 있는 경우, Hypothesis Space가 그 집합을 Shatter한다고 한다.

-- For all dichotomies of D of instance space X, there exists a hypothesis which is consistent(h,D). Then the hypothesis space shatters D. 

 

-Claim VC dimesnion is n

--Proof : VC dimension이 n이라는 것을 보이기 위해서는 적어도 한 개의 n개의 원소를 가지는 집합을 shatter 할 수 있는 것을 보이고 n+1개의 원소를 가지는 모든 집합을 shatter할 수 없음을 보여야 한다.

 

 

Q1) What is the difference between inference and estimation?