Shattering

만일 어떤 Hypothesis space $H$ 가, Instance Space의 부분집합 $S$ 를 shatter한다는 것은, $S$ 의 일부인 train data $D$ 의 모든 가능한 dichotomy를 설명 가능한 Consistent $h \in H$ 가 존재한다는 것을 의미한다.

\forall dichotomy D of S [\exists h \in H ∋ CONSISTENT(h,D)]

: $J$ 의 모든 subset $S$ 에 대해 특정 function에 의해 개별 인스턴스를 모든 가능한 조합의 이진 레이블로 구분 가능하다는 것을 의미한다.

Dichotomy

어떠한 Instance들을 positive 혹은 negative로 labeling 하는 것.

이러한 조합은 $N$ 개의 instance에 대하여, $2^{N}$ 개의 조합이 가능하다.