N 포인트를 포함하는 데이터셋이 있다고 가정합시다. 이 N 포인트는 양성과 음성으로 2^N 가지 방식으로 라벨링할 수 있습니다. 따라서 N 개의 데이터 포인트로 2^N 가지의 서로 다른 학습 문제가 정의될 수 있습니다. 이러한 문제 중 어느 것에 대해서든지, 양성 사례와 음성 사례를 분리하는 가설 h ∈ H 를 찾을 수 있다면, 우리는 H가 N 포인트를 격파(shatter)한다고 말합니다. 즉, N 사례로 정의할 수 있는 모든 학습 문제는 H에서 추출된 가설로 오류 없이 학습할 수 있습니다. H가 shatter할 수 있는 최대 포인트 수를 H의 Vapnik-Chervonenkis(VC) 차수라고 하며, 이를 VC(H)로 나타내고 H의 capacity를 측정합니다.
여기서 우리는 H의 복잡도를 측정하는 두 번째 척도인 Vapnik-Chervonenkis 차원(VC 차원 또는 간단히 VC(H))을 고려합니다. 우리가 볼 수 있듯이, 우리는 |H| 대신 VC(H)를 사용하는 샘플 복잡도 경계를 제시할 수 있습니다. 많은 경우 VC(H)를 기반으로 한 샘플 복잡도 경계는 식 (7.2)에서의 경계보다 더 타이트할 것입니다. 또한, 이러한 경계는 많은 무한 가설 공간의 샘플 복잡도를 characterize할 수 있으며, 상당히 타이트하다고 보여질 수 있습니다.
VC 차원은 가설 공간 H의 복잡도를 IHI와는 다르게, H를 사용하여 완벽하게 구분할 수 있는 X의 서로 다른 인스턴스의 수로 측정합니다. 이 개념을 더 정확하게 정의하기 위해, 우리는 인스턴스 집합의 샤터링 개념을 먼저 정의합니다. 인스턴스의 일부 집합 S ⊆ X를 고려해봅시다. 예를 들어, 그림 7.3은 X에서 세 개의 인스턴스의 부분 집합을 보여줍니다. Each hypothesis h from H imposes some dichotomy on S. 즉, h는 S를 두 부분 집합 {x ∈ S | h(x) = 1}과 {x ∈ S | h(x) = 0}으로 나눕니다. Given some instance set S, there are $2^{|S|}$ possible dichotomies, though H may be unable to represent some of these. 이때 S의 모든 가능한 dichotomy가 H의 어떤 가설로 표현된다면, H는 S를 shatter한다고 말합니다. (⇔ H의 임의의 가설이 표현하지 못하는 S의 dichotomy가 존재하지 않는다.)
<aside> 📌
Definition: A set of instances S is shattered by hypothesis space H if and only if for every dichotomy of S there exists some hypothesis in H consistent with this dichotomy.
</aside>
(∀ dichotomy 𝐷 of 𝑆)[∃ ℎ ∈ ℋ s.t CONSISTENT (ℎ, 𝐷 )]
Note that if a set of instances is not shattered by a hypothesis space, then there must be some concept (dichotomy) that can be defined over the instances, but that cannot be represented by the hypothesis space.
The ability of H to shatter a set of instances is thus a measure of its capacity to represent target concepts defined over these instances.
인스턴스 집합을 산산조각 내는 능력은 가설 공간의 귀납적 편향과 밀접한 관련이 있다. 제2장에서 언급한 바와 같이, unbiased 가설 공간은 인스턴스 공간 X 위에서 정의 가능한 모든 개념(이분법)을 표현할 수 있는 공간이다. 간단히 말해, unbiased 가설 공간 H는 인스턴스 공간 X를 shatter한다. 만약 H가 X를 shatter할 수 없지만 X의 큰 부분집합 S는 shatter할 수 있다면, 직관적으로 볼 때, H가 shatter할 수 있는 X의 부분집합이 커질수록 H는 더 표현력이 강하다(expressive)고 말할 수 있을 것이다. H의 VC 차원은 바로 이러한 척도이다.
<aside> 📌
정의: 인스턴스 공간 X 위에 정의된 가설 공간 H의 바프닉-체르보넨키스 차원(VC 차원) VC(H)는 H에 의해 산산조각 난 X의 가장 큰 유한 부분집합의 크기이다. 만약 임의의 큰 유한 집합들이 H에 의해 산산조각 났다면, VC(H)=∞이다.
</aside>
유한한 H에 대해 VC(H)≤log2|H|라는 점을 주목하라. 이를 확인하기 위해 VC(H)=d라고 가정하자. 그러면 H는 d개의 인스턴스를 산산조각 내기 위해 2^d개의 서로 다른 가설을 필요로 한다. 따라서 2^d≤|H|가 되며, d=VC(H)≤log2|H|이다.
[설명] d개의 인스턴스를 완벽히 구분하려면 적어도 2^d개의 가설이 필요하다. 가설 공간의 크기 |H|는 가설의 개수이므로 |H|가 주어질 때, 적어도 log2|H|개 이하의 인스턴스만 완벽히 구분 가능하다.