성장함수

분쇄 계수 또는 분쇄 수라고도 하는 성장 함수는 세트 계열의 풍요로움을 측정한다.특히 가설 수업의 복잡성을 측정하는 통계 학습 이론의 맥락에서 사용된다.'성장 기능'이라는 용어는 1968년 논문에서 Vapnik과 Chervonenkis에 의해 만들어졌는데, 여기서 그들은 또한 그것의 많은 특성들을 증명했다.^[1]기계학습의 기본 개념이다.^[2][3]

정의들

집합군 정의

$H{\displaystyle }$ ${\displaystyle H}$을(를) 세트 패밀리(세트 세트)로$$ 하고 $C{\displaystyle }$ ${\displaystyle C}$을(를) 세트$$ 집합으로 한다.이들의 교차점은 다음과 같은 집합체로 정의된다.

$H:=\{h\cap C:=\{h\cap C\mid h\in H\}}$

The intersection-size (also called the index) of ${\displaystyle H}$ with respect to ${\displaystyle C}$ is ${\displaystyle H\cap C }$. If a set ${\displaystyle C_{m}}$ has ${\displaystyle m}$ elements then the index is at most ${\displaystyle 2^{m}}$. If the index is exactly${\displaystyle \mathrm{2^<i>m</i>}}$ $그러면{\displaystyle }$ H ${\displaystyle \cap }$ C ${\displaystyle H\cap C}$이(가) $C{\displaystyle }$ ${\displaystyle C}$의 모든 하위 세트를 포함하므로$$ 세트 $C{\displaystyle }$ ${\$displaystyle C$}$이(가) H ${\displaystystyle H}$에 의해 산산조각 난다고 한다$$$.$ 즉,

${\displaystyle H\cap C =2^{ C }}$

성장 함수는 ${\displaystyle C}$ ${\displaystyle \{\backslash }$$displaystyle H\cap C$$}$의 함수로$$ $H{\displaystyle }$ ${\displaystyle \cap }$ ${\displaystyle C}$ ${\$$displaystyle$C}의 크기를 측정한다$.$ 정식으로:

${\displaystyle \operatorname {Growth}(H,m):=\max _{C: C =m} H\cap C }$

가설 등급 정의

마찬가지로 $H{\displaystyle }$ ${\displaystyle H}$을(를) 가설 클래스(이항 함수의 집합)로$$ 하고 $C{\displaystyle }$ ${\displaystyle C}$을(를) $m{\displaystyle }$ ${\displaystyle m}$ 요소로$$ 설정하도록 한다.$H{\displaystyle }$ ${\displaystyle H}$에서 $C{\displaystyle }$ ${\displaystyle$ C$}$까지의 $제한$은 다음과 같이 H {\$displaystyle H}$에서 파생될 수 있는${\displaystyle }$ C ${\$$displaystyle C}$의 이진 함수 집합이다$.$^{[3]: 45}

${\displaystyle H_{C}=\{{(x_{1}),\ldots ,h(x_{m})\mid h\in H,x_{i}\in C\}}}}}$

성장함수는 ${\displaystyle C}$ $displaystyle$C}의$$ 함수로서 H ${\displaystyle C_{}}$ ${\$$}$의 크기를 측정한다$.$^{[3]: 49}

${\displaystyle \operatorname {Growth}(H,m):=\max _{C: C =m} H_{C}}$

예

어떤 x에 1. 도메인의 진정한 라인 R{\displaystyle \mathbb{R}}. 그 set-family H{H\displaystyle}, 형태의 세트\와 같이{\displaystyle\와 같이{x>, x_{0}\mid x\in \mathbb{R}{)>x0∣ x∈ R}}모든 half-lines자 수에서 양의 무한대로, 즉(광선)가 들어 있}0∈ R{\displays.tyle)$_{0}\in \mathbb {R} }$. For any set ${\displaystyle C}$ of ${\displaystyle m}$ real numbers, the intersection ${\displaystyle H\cap C}$ contains ${\displaystyle m+1}$ sets: the empty set, the set containing the largest element of ${\displaystyle C}$, the set containing the two largest elements of $$${\displaystyle C}$ $[\displaystyle C}$등.그러므로: ${\displaystyle \mathrm{성장}}$ ${\displaystyle }$(${\displaystyle H}$ ${\displaystyle ,m}$) = ${\displaystyle \mathrm{m}}$+ 1 ${\displaystyle \operatorname {Growth} (H,m)=m+1$}$$^{[1]: Ex.1} .$H{\displaystyle }$ ${\displaystyle H}$이(가) 열린 하프라인, 닫힌 하프라인 또는 둘 다를 포함하든$$ 마찬가지다.

2. 도메인은 세그먼트${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle [0,1$ 세트 $패밀리{\displaystyle }$ H ${\displaystyle H}$에는 모든 오픈 세트가 포함되어$$ 있다.For any finite set ${\displaystyle C}$ of ${\displaystyle m}$ real numbers, the intersection ${\displaystyle H\cap C}$ contains all possible subsets of ${\displaystyle C}$. There are ${\displaystyle 2^{m}}$ such subsets, so ${\displaystyle \operatorname {Growth} ($$H,m)=2^{m$

3. 도메인은 유클리드 공간 $R{\displaystyle {\mathbb{}}^{}}$ {${\displaystyle {}^{}}$ ${\$ ^{$n}}$ 입니다$.$세트 패밀리 $H{\displaystyle }$ ${\displaystyle H}$에는 x $x{\displaystyle \varphi }$ ${\displaystyle \ge }$ ${\displaystyle 1}$ ${\displaystyle$ x$\cdot \phi \geq 1}$과$($와) 같은 형태의 모든 반공간이 포함되며$$, 여기서 $\varphi {\displaystyle }$ ${\displaysty \pi$}은 고정 벡터다$$.그러면 ${\displaystyle \mathrm{Grow}}$ ${\displaystyle }$(${\displaystyle H}$,${\displaystyle }$m ) = ${\displaystyle \mathrm{Comp}}$ ${\displaystyle }$(${\displaystyle n}$,${\displaystyle }$m ) ${\displaystyle \operatorname {Growth}(H,m)=\Operatorname {Comp}(n,m$ 여기서 Comp는 m 하이퍼플레인에 의한 n차원 공간의 분할에 있는 성분 수입니다.^{[1]: Ex.3}

4. The domain is the real line ${\displaystyle \mathbb {R} }$. The set-family ${\displaystyle H}$ contains all the real intervals, i.e., all sets of the form ${\displaystyle \{x\in [x_{0},x_{1}] x\in \mathbb {R} \}}$ for some ${\displaystyle x_{0},x_{1}\i$$n \mathb {R}$$}$ . $m{\displaystyle }$ ${\displaystyle m}$ 실수의$$$$ C ${\displaystyle$ $H\cap C}$에 대해 교차로 $H{\displaystyle }$ ${\displaystyle \cap }$ C ${\displaystyle M}$ 사이의$$ 모든 런이 $C{\displaystyle }$ ${\\displaystystyle C$}의 연속적인 요소에 포함됨$.$이러한 실행 횟수는${\displaystyle }$(${\displaystyle m\genfrac{}{}{0ex}{}{}{}}$+ ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{}}{}}$ ${\displaystyle 2}$)${\displaystyle }$+ 1 ${\displaystyle {m+1 \선택$ 2$\}+$$1$}이므로 ${\displaystyle \mathrm{성장}}$⁡${\displaystyle }$(${\displaystyle H\genfrac{}{}{0ex}{}{}{},}$ m${\displaystyle }$)${\displaystyle }$=${\displaystyle }$( m${\displaystyle \genfrac{}{}{0ex}{}{}{}}$+ ${\displaystyle \genfrac{}{}{0ex}{}{\mathrm{}}{}}$ ${\displaystyle 2}$)${\displaystyle }$+ 1 ${\displaysty \operatorname {Growth}(H,m)={m+1 \선택$ 2$+1$}이다$.$

다항식 또는 지수

성장 함수를 흥미롭게 하는 주요 특성은 다항식 또는 지수식일 수 있다는 것이다. 그 중간에는 아무것도 없다.

다음은 교차로 크기의 특성이다.^{[1]: Lem.1}

• 만일, 일부의 경우$,$ 크기 $m{\displaystyle }$ ${\displaystyle m}$의 $C{\displaystyle {}_{}}$ ${\displaystyle m_{}}$ ${\$${\displaystyle m}$$}$을 $설정$하고, 일부 숫자의 경우, ${\displaystyle {}_{}}$ ${\displaystyle \le }$ ${\displaystyle m_{}}$$${\$displaystyle n\leq$m},$$${\displaystyle H}$ C ${\displaystyle \ge {}_{}}$ ${\displaystyle \mathrm{Comp}}$ ${\displaystyle }$($n$ ${\displaystyle ,}$ m$){m} \displaystym \operatorname {C}$$-m}$
• ${\displaystyle 그}$ 다음, $H{\displaystyle }$ ${\displaystyle \cap }$ ${\displaystyle C_{}}$ ${\displaystyle m_{}}$ $displaystyle C_{n}\subseteq C_{m}$ 크기가$$ n ${\displaystyle n$${\displaystyle \}{}_{}}$인 $부분집합{\displaystyle {}_{}}$ C ${\displaystyle n_{}}$ = ${\displaystyle {2n}^{}}$ ${\$

이는 성장 함수의 다음 속성을 의미한다.^{[1]: Th.1} 모든 $제품군{\displaystyle }$ H ${\displaystyle H}$에 대해 다음 두 가지 경우가 있다$$.

• 지수 사례:${\displaystyle \mathrm{성장}}$ ${\displaystyle }$(${\displaystyle H}$, m${\displaystyle }$)${\displaystyle }$= ${\displaystyle {2m}^{}}$ ${\$과 동일하다.
• 다항식 사례:${\displaystyle \operatorname {Growth} (H,m)}$ is majorized by ${\displaystyle \operatorname {Comp} (n,m)\leq m^{n}+1}$, where ${\displaystyle n}$ is the smallest integer for which ${\displaystyle \operatorname {Growth} (H,n)<2^{n}}$.

기타 속성

사소한 상한

$유한{\displaystyle }$ H ${\displaystyle$ H$}$의 경우$:$

${\displaystyle \operatorname {Growth}(H,m)\leq H }$

모든 $C{\displaystyle }$ ${\displaystyle C}$에 ${\displaystyle \mathrm{대해}}$$$$H{\displaystyle }$ ${\displaystyle \cap }$ C ${\displaystyle$H$\cap C}$에 있는 원소의 ${\displaystyle 수}$는 최대${\displaystyle }$H {\$displaystyle$ H$}$에 있으므로$$ 성장 $함수$는$$H {\\$displaystyle$ H}가$$ 무한할 때 주로 흥미롭다.

지수 상한

비어 있지 않은 $H{\displaystyle }$ ${\displaystyle H}$의 경우$:$

${\displaystyle \operatorname {Growth}(H,m)\leq 2^{m}}$

즉, 성장함수는 지수 상한을 가진다.

집합 패밀리 $H{\displaystyle }$ ${\displaystyle H}$이(가) 교차점에 $C{\displaystyle }$ ${\displaystyle C$의 가능한 하위 집합이 모두 포함된 경우$$ 집합 $C{\displaystyle }$ ${\displaystyle C}$을(를) 산산조각$$ 낸다고 우리는 말한다.${\displaystyle H\cap C=2^{C}}$. If ${\displaystyle H}$ shatters ${\displaystyle C}$ of size ${\displaystyle m}$, then ${\displaystyle \operatorname {Growth} (H,C)=2^{m}}$, which is the upper bound.

데카르트 교차로

두 세트 패밀리의 데카르트 교차로 정의:

${\displaystyle H_{1}\bigotimes H_{2}:=\{h_{1}\cap h_{2}\mid h_{1}\in H_{1},h_{2}\in H_{2}\}}$.

다음:^{[2]: 57}

${\displaystyle \operatorname {Growth}(H_{1}\bigotimes H_{2},m)\leq \operatorname {Growth}(H_{1},m)\cdot \operatorname {Growthing}(H_{2},m)}$

유니온

두 세트 패밀리의 경우:^{[2]: 58}

${\displaystyle \operatorname {Growth}(H_{1}\컵 H_{2},m)\leq \operatorname {Growth}(H_{1},m)+\operatorname {Growth}(H_{2},m)}$

VC 치수

$H{\displaystyle }$ ${\displaystyle H}$의 VC 치수는 다음 두 가지 경우에 따라 정의된다$$.

• 다항식의 경우 ${\displaystyle \mathrm{VCDim}}$ im$($${\displaystyle H}$ ${\displaystyle )}$= ${\displaystyle n}$- ${\displaystyle 1}$ ${\displaystyle \operatorname {VCDim}(H$${\displaystyle )=}$$n-1}$ $$= ${\displaystyle \mathrm{Growth}}$ ${\displaystyle (H}$, ${\displaystyle {\mathrm{}}^{}}$ )${\displaystyle }$= 2 ${\displaystyle d^{}}$ ${\$ {$Grow$}(H,d)=2^{d$\}.$
• 지수적인 경우 ${\displaystyle \mathrm{VCDim}}$ ${\displaystyle }$( ${\displaystyle H}$)${\displaystyle }$= ${\displaystyle \mathrm{\infty }}$ ${\displaystyle \operatorname {VCDim}(H)=\fty }$.

따라서 ${\displaystyle \mathrm{VCDim}}$ ${\displaystyle }$ (${\displaystyle }$H${\displaystyle }$) ${\displaystyle \ge }$ d ${\displaystyle \operatorname$ {$VCDim}$ ($H)\geq d}$ if-and-only-only$$ Growth(${\displaystyle H}$, ${\displaystyle d}$)${\displaystyle =}$ 2 ${\displaystyle d^{}}$ ${\$ 표시 스타일 $\operatorname {Grow}(H,d)=2^{d$

성장함수는 VC차원 개념의 정교화로 볼 수 있다.The VC dimension only tells us whether ${\displaystyle \operatorname {Growth} (H,d)}$ is equal to or smaller than ${\displaystyle 2^{d}}$, while the growth function tells us exactly how ${\displaystyle \operatorname {Growth} (H,m)}$ changes as a function of ${\displaystyle m}$.

성장 기능과 VC 치수 사이의 또 다른 연결은 Sauer-Shelah 보조정리기가 제공한다.^{[3]: 49}

${\displaystyle \mathrm{VCDim}}$ ${\displaystyle }$ (${\displaystyle H}$)${\displaystyle }$= ${\displaystyle d}$ ${\daystyle \operatorname {VCDim}(H)=d}$인 경우$:$

모든 $m{\displaystyle }$ ${\displaystyle m}$에 대해 $:$ 성장${\displaystyle \mathrm{growth}}$ (${\displaystyle \underset{}{\overset{}{H}}}$, ${\displaystyle m}$) ${\displaystyle \underset{}{\overset{}{}}}$ i${\displaystyle \underset{}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{}}}$ d (${\displaystyle \underset{}{\overset{}{}}\genfrac{}{}{0ex}{}{m}{}}$ ${\displaystyle i}$) ${\$

특히.

모든 > + $(\displaystyle m>d+1}$: ${\displaystyle \mathrm{성장}}$ ${\displaystyle }$( ${\displaystyle H}$, ${\displaystyle m}$) ${\displaystyle \le }$( ${\displaystyle e}$ m${\displaystyle }$/ d${\displaystyle {}^{}}$) d${\displaystyle {}^{}}$= ${\displaystyle O^{}}$( ${\displaystyle m^{}}$) ${\displaysty \operatorname {Streating} (H,m)\leq (em/d)^{d}=O(m^{d})}$

따라서 VC 차원이 유한할 때 성장 함수는 $m{\displaystyle }$ ${\displaystyle m}$과(와) 함께 다항식으로 성장한다$.$

이 상한은 단단하다. 즉, m> d ${\displaystyle$m}에$대해$ 다음과 같은$$ ^{[2]: 56} $VC{\displaystyle }$ 치수$$ d ${\displaystyle$ d}을$($를) 가진 H ${\displaystyle$ H$}$이(가) 존재한다.

${\displaystyle \operatorname {Growth}(H,m)=\sum _{i=0}^{d}{m \선택 i}}}$

엔트로피

성장 함수는 최대 교차로 크기와 관련이 있지만 엔트로피는 평균 교차로 크기와 관련이 있다.^{[1]: 272–273}

${\displaystyle \operatorname {Entropy}(H,m)=E_{C_{m} =m}{\big [}\log _{2}(H\cap C_{m} ){\big ]}}}$

교차로 크기는 다음과 같은 특성을 가지고 있다.모든 세트 패밀리 $H{\displaystyle }$ ${\displaystyle H}$에 대해$:$

${\displaystyle H\cap (C_{1}\cup C_{2}) \leq H\cap C_{1} \cdot H\cap C_{2} }$

따라서 다음과 같다.

${\displaystyle \operatorname {Entropy}(H,m_{1}+m_{2})\leq \operatorname {Entropy}(H,m_{1}+\operatorname {Entropy})(H,m_{2})$

더욱이, ${\displaystyle 엔트로피}$ (${\displaystyle H}$, ${\displaystyle m}$)${\displaystyle }$/ m ${\displaystyle \operatorname {Entropy$${\displaystyle \}}$$(H,m)/m}$ 시퀀스는 $m{\displaystyle }$→$$ [${\displaystyle 0,}$ ${\displaystyle 1}$ $]$ ${\$$displaystyle c\in$ $[0,$$1]$의 $상수$로 수렴된다$.$

또한 임의변수 ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle H}$ ${\displaystyle \cap }$ ${\displaystyle {}_{}}$ ${\displaystyle m{}_{}}$/ m ${\$은 $c{\displaystyle }$ ${\displaystyle c}$ 근처에 집중되어 있다$$$.$

확률론에서의 적용

$\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega}$을(를) 확률 측정값 ${\displaystyle Pr}$ ${\displaystyle \Pr }$이(가) 정의된 집합이 되도록$$ 한다.$H{\displaystyle }$ ${\displaystyle H}$을(를) $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega}$의 하위 집합 계열로 $$두십시오(= 이벤트 계열$$).

$\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega}$의 $m{\displaystyle }$ ${\displaystyle m}$ 요소를$$ 포함하는$$ 세트 $C{\displaystyle {}_{}}$ ${\displaystyle m_{}}$ ${\$을 선택한다고 가정합시다$.$ 여기서 각 요소는 다른 요소와 독립적으로 확률 측정 $P{\displaystyle }$ ${\displaystyle P$에 따라 랜덤하게 선택된다.각 이벤트 $h{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle H}$ ${\displaystyle h\in H}$에 대해 다음 두 가지 양을 비교한다$.$

• $C{\displaystyle {}_{}}$ ${\displaystyle m_{}}$ ${\$즉 ${\displaystyle h}$ ${\displaystyle \cap }$ ${\displaystyle C_{}}$ m${\displaystyle {}_{}}$/ ${\displaystyle m}$ ${\displaystyle h\cap C_{m} /m}$;
• 확률 ${\displaystyle \mathrm{Pr}}$ [${\displaystyle }$h ${\displaystyle ]}$ ${\displaystyle \Pr[h$

$우리$는${\displaystyle }$D ( ${\displaystyle h}$, ${\displaystyle C_{}}$m ) ${\displaystyle :=}$ ${\displaystyle h}$c ${\displaystyle C_{}{}_{}}$m / ${\displaystyle m}$- ${\displaystyle Pr}$[ ${\displaystyle h}$ ${\displaystyle ]}$ $displaystyle D(h,C_{m})$의 차이에 관심이 있다.$={\big$}$h\cap C_{m} /m-\Pr[h]{\big$ $\}\}\}$ 이 차이는 다음 상한을 만족한다.

${\displaystyle \Pr \왼쪽[\forall h\in H:D(h,C_{m})\leq {8(\ln \operatorname {Growth})(H,2m)+\ln(4/\delta ) \overm}\right]~~~~>~~~~1-\cHB }$

이 값은 다음과 같다.^{[1]: Th.2}

${\displaystyle \Pr {\big [}\forall h\in H:D(h,C_{m})\leq \varepsilon {\big ]~~~1-4\cdot \operatorname {성장}(H,2m)\cdot \exp(-\varepsilonm/8)$

즉$,$ $H{\displaystyle }$ ${\displaystyle H}$의 모든 이벤트에 대해 $상대{\displaystyle }$ 빈도가 확률에 가까울 확률은 H ${\displaystyle H}$의 성장 기능에 따라 달라지는 식에 의해 더 낮은 경계가 된다$.$

A corollary of this is that, iff the growth function is polynomial in ${\displaystyle m}$ (i.e, there exists some ${\displaystyle n}$ such that ${\displaystyle \operatorname {Growth} (H,m)\leq m^{n}+1}$), then the above probability approaches 1 as ${\displaystyle m\to \infty }$. I.e$H{\displaystyle }$ ${\displaystyle H}$ 패밀리는 확률상 균일한 합치를 즐긴다$$.

참조