대표자 정리

컴퓨터 과학의 경우, 통계적 학습 이론에서 대표자 정리는 재현 커널 힐버트 공간에 걸쳐 정의된 정규화된 경험적 위험 함수의 미니마이저 $∗{\$ f$^{*}$이(가) 에서 평가된 커널 제품의 유한 선형 결합으로 표현될 수 있음을 나타내는 몇 가지 관련 결과 중 하나이다.교육 세트 데이터에 포인트를 입력한다.

형식명세서

다음과 같은 대표자 정리 및 그 증거는 슐코프, 헤르브리치, 스몰라 때문이다.^{[citation needed]}

정리:Consider a positive-definite real-valued kernel ${\displaystyle k:{\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$ on a non-empty set ${\displaystyle {\mathcal {X}}}$ with a corresponding reproducing kernel Hilbert space ${\displaystyle H_{k}}$. Let there be given

• 교육 샘플$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$)${\displaystyle }$, …${\displaystyle }$(${\displaystyle x_{}}$ n${\displaystyle {}_{}}$, ${\displaystyle y_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle \in }$ ${\displaystyle X\mathbb{}}$ ${\displaystyle \times }$ R ${\$}, }, }, }, }, }, }, },
• $\mathb {R}$ 및 \mathb {R}에 대해 엄격하게 증가하는 실제 값 함수 $g{\displaystyle }$ :${\displaystyle }$[${\displaystyle 0,}$ \${\displaystyle }$)${\displaystyle }$→ ${\displaystyle R\mathbb{}}$ ${\$to$$\mathb {R}$$및
• 임의 오류 $함수{\displaystyle }$ E${\displaystyle }$:${\displaystyle }$( ${\displaystyle X\mathcal{}}$ ${\displaystyle \times }$ ${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {}^{}{}^{}}$) ${\displaystyle n^{}}$→ ${\displaystyle R\mathbb{}}$ ${\displaystyle \cup }${${\displaystyle }$∞} ${\displaystyle E\colon({\mathcal$ {$X}\time\mathb$ {$R}^{2}^{n}\to \mathb {R}\$cupto $\lbrace \cup \lbe \$lblb$$\$in$ }, .

$H{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$에 대해 다음과 같은 정규화된 경험적 위험 기능을 정의한다$.$

${\displaystyle f\mapsto E\left(x_{1},y_{1},f(x_{1}), ...,(x_{n},y_{n},f(x_{n})\rig(\lLvert f\rVert \rig).}$

그런 다음, 경험적 위험을 최소화하는 방법

${\displaystyle f^{*}=\operatorname {argmin} _{f\in H_{k}}\left\lbrace E\left((x_{1},y_{1},f(x_{1})),...,(x_{n},y_{n},f(x_{n}))\right)+g\left(\lVert f\rVert \right)\right\rbrace ,\quad (*)}$

서식의 대표성을 인정하다.

${\displaystyle f^{*}(\cdot )=\sum _{i=1}^{n}\cd_k(\cdot ,x_{i}),}$

여기서 $\alpha {\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle R\mathbb{}}$ ${\$에 $1{\displaystyle \mathrm{}}$ ${\displaystyle \le }$ ${\displaystyle i}$ $displaystyle 1\leq$ i$\leq n}$모두.

증명: 매핑 정의

${\displaystyle {\begin{aigned}\varphi \colon {\mathcal {X}&\to H_{k}\\varphi (x)&=k(\cdot ,x)\ended}}}}$

(따라서 ${\displaystyle \phi }$(${\displaystyle x}$) = k${\displaystyle }$(${\displaystyle ,}$ ,${\displaystyle x}$ )$${\$displaystyle \varphi (x)=k(\cdot ,x)}$은 그 자체로${\displaystyle }지도{\displaystyle \mathcal{}}$ X →$$ {\$displaystyle${\$mathcal {X$}\to $\mathb${R$}}}}$이다.$$$k{\displaystyle }$ ${\displaystyle k}$은(는) 재생성 커널이므로,

${\displaystyle \varphi (x')=k(x'),x)=\langle \varphi(x'),\varphi(x)\angle ,}$

여기서 ${\displaystyle ⟨,}$⋅, ⋅,${\displaystyle }$\,$$\$displaystyle \langle \cdot,\cdot \rangle }}$은(는)$$H k {\$displaystyle H_{$k}}}}에 있는 내제품이다$.$

Given any ${\displaystyle x_{1},...,x_{n}}$, one can use orthogonal projection to decompose any ${\displaystyle f\in H_{k}}$ into a sum of two functions, one lying in ${\displaystyle \operatorname {span} \left\lbrace \varphi (x_{1}),...,\varp$$hi (x_{n})\right\rbrace }$, 그리고 다른 하나는 직교 보어에 있다.

${\displaystyle f=\sum _{i=1}^{n}\reason _{i}\varphi(x_{i})+v,}$

여기서 $⟨{\displaystyle }$ ${\displaystyle v}$ ,${\displaystyle \phi }$( x ${\displaystyle i_{}}$) ${\displaystyle ⟩}$= ${\displaystyle 0}$ ${\displaystyle \langle v,\varphi (x_{i})\angle =0}$ 모든 $i{\displaystyle }$ ${\displaystyle$ i$}$에 대한$$ $.$

위의 직교 분해와 재현 특성을 함께 보면 어떤 교육 $지점{\displaystyle {}_{}}$ ${\displaystyle x_{}}$ j ${\$에든 f ${\displaystyle f}$을(를) 적용하면 결과가$$ 나온다는 것을 알 수 있다.

${\displaystyle f(x_{j})=\left\langle \sum _{i=1}^{n}\alpha _{i}\varphi (x_{i})+v,\varphi (x_{j})\right\rangle =\sum _{i=1}^{n}\alpha _{i}\langle \varphi (x_{i}),\varphi (x_{j})\rangle ,}$

우리가 관찰하는 것은 $v{\displaystyle }$ ${\displaystyle v}$과(와) 무관하다$.$ 따라서 오류$$ 함수 $E$의 값$(*)$은 v {\$displaystyle v}$과$($와) 무관하다$.$ 두 번째 용어(정규화 용어)의 경우,$$v {\$displaysty v}$은 $\sum {\displaystyle \underset{}{\overset{}{}}}$ i =${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle ({}_{}}$ ${\displaystyle i_{}}$)와$$직교직교직교직교)이기 때문에$플레이스타일 \sum _{i=1$}^{n$}\filename _{i$}\i}\{$i}\i}\varphi$($x_{$i}) 및 g ${\$displaystyle g$}$은(는) 완전히 단조롭다.

${\displaystyle {\begin}g\왼쪽(\lVert f\rVert \right)&=g\n(\lVert \sum _{i=1}^{n}\alpha _{i}\i}+v\rVert \right)\\\\\\\&=g\왼쪽({\sqrt {\lVert \sum _{i=1}^{n}\알파 _{i}\varphi(x_{i})\rVert ^{2}+\lVert v\rVert ^{2}}}\오른쪽)\\&\geq g\left(\lVert \sum _{i=1}^{n}\알파 _{i}\varphi(x_{i})\rVert \right.\end{정렬}}}$

따라서 $v{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle v=0}$을(를) 설정해도 첫 번째 기간(*)에는 영향을 미치지$$ 않는 반면 두 번째 기간은 엄격히 감소한다.따라서 (*)의$$ 모든 미니마이저 $f{\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$는 $v{\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle v=0},$ 즉 형식이어야 한다$.$

${\displaystyle f^{*}(\cdot )=\sum _{i=1}{n}\sum _{i}\varphi(x_{i})=\sum _{i=1}^{n}\i}k(\cdot ,x_{i}),}}}}$

원하는 결과야

일반화

위에서 언급된 정리는 집합적으로 "대표자 정리"라고 언급되는 결과 집단의 특별한 예다. 여기서 우리는 몇 가지 그러한 것을 설명한다.

대표자 정리의 첫 번째 진술은 키멜도르프와 와바에 의한 것이었다.

${\displaystyle {\reasoned}E\left((x_{1},y_{1},f(x_{1})),...,(x_{n},y_{n},f(x_{n}))\right)&={\frac {1}{n}}\sum _{i=1}^{n}(f(x_{i})-y_{i})^{2},\\g(\lVert f\rVert )&=\lambda \lVert f\rVert ^{2}\end{aligned}}}$

> ${\displaystyle \lambda >0}.$슐코프, 헤르브리치, 스몰라(Smola)는 제곱 손실 비용의 가정을 완화하고 정규화기를 힐베르트 공간 표준의$$ 엄격히 단조롭게 증가하는 함수 $g{\displaystyle }$ (${\displaystyle \cdot }$) ${\displaysty g(\cdot$)가 되도록 허용함으로써 이 결과를 일반화했다.

보정되지 않은 상계항목을 추가하여 정규화된 경험적 위험 기능을 증강함으로써 더 일반화할 수 있다.예를 들어 슐코프, 헤르브리치, 스몰라 등도 최소화를 고려한다.

${\displaystyle {\tilde {f}}^{*}=\operatorname {argmin} \left\lbrace E\left((x_{1},y_{1},{\tilde {f}}(x_{1})),...,(x_{n},y_{n},{\tilde {f}}(x_{n}))\right)+g\left(\lVert f\rVert \right)\mid {\tilde {f}}=f+h\in H_{k}\oplus \operatorname {span} \lbrace \psi _{p}\mid 1\leq p\leq M\rbrace \right\rbrace ,\quad (\dagger )}$

i.e., we consider functions of the form ${\displaystyle {\tilde {f}}=f+h}$, where ${\displaystyle f\in H_{k}}$ and ${\displaystyle h}$ is an unpenalized function lying in the span of a finite set of real-valued functions ${\displaystyle \lbrace \psi _{p}\co$$lon {\mathcal {X}}\to \mathbb {R} \mid 1\leq p\leq M\rbrace }$. Under the assumption that the ${\displaystyle n\times M}$ matrix ${\displaystyle \left(\psi _{p}(x_{i})\right)_{ip}}$ has rank ${\displaystyle M}$, they show that the minimizer ${\displaystyle {\tilde$${f}^{*}$ in$$${\displaystyle }$( )${\displaystyle (\$displaystyle (\$displaystyle )}$에서 양식의 표현을 승인함$$

${\displaystyle {\tilde{f}^{*}(\cdot )=\sum _{i=1}{n}\alpha _{i}k(\cdot ,x_{i}++_{p=1}^{p}\p}\psi(\cdot )}$

여기서 $\alpha {\displaystyle {}_{}}$ ${\displaystyle i_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle p_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle R\mathbb{}}$ ${\$ _${i$},\beta $_{p}\in$\mathb {$R} 및$ $\beta {\displaystyle {}_{}}$ ${\displaystyle p_{}}$ ${\$는 모두 고유하게 결정된다$$.

대표자 정리가 존재하는 조건은 아르기리우, 미첼리, 폰틸에 의해 조사되었는데, 그는 다음과 같은 사실을 증명하였다.

정리:Let ${\displaystyle {\mathcal {X}}}$ be a nonempty set, ${\displaystyle k}$ a positive-definite real-valued kernel on ${\displaystyle {\mathcal {X}}\times {\mathcal {X}}}$ with corresponding reproducing kernel Hilbert space ${\displaystyle H_{k}}$, and let ${\displaystyle$$R\colon H_{k}\to \mathb {R}은($는) 서로 다른 정규화 함수가 된다$$.Then given a training sample ${\displaystyle (x_{1},y_{1}),...,(x_{n},y_{n})\in {\mathcal {X}}\times \mathbb {R} }$ and an arbitrary error function ${\displaystyle E\colon ({\mathcal {X}}\times \mathbb {R} ^{2})^{m}\to \mat$$hbb {R} \cup \lbrace \infort$ \$rbrace$ $\},$ 미니마이저

${\displaystyle f^{*}=\operatorname {argmin} _{f\in H_{k}}\left\lbrace E\left((x_{1},y_{1},f(x_{1})),...,(x_{n},y_{n},f(x_{n}))\right)+R(f)\right\rbrace \quad (\ddagger )}$

정규화된 경험적 위험의 형태적 표현을 허용한다.

${\displaystyle f^{*}(\cdot )=\sum _{i=1}^{n}\cd_k(\cdot ,x_{i}),}$

where ${\displaystyle \alpha _{i}\in \mathbb {R} }$ for all ${\displaystyle 1\leq i\leq n}$, if and only if there exists a nondecreasing function ${\displaystyle h\colon [0,\infty )\to \mathbb {R} }$ for which

$[\displaystyle R(f)=h(\lVert f\rVert).}$

효과적으로, 이 결과는 상이한 정규화 정규화 $정규화{\displaystyle }$ R (${\displaystyle }$risk ) $\{\backslash {\displaystyle }$$displaystyle R(\cdot )}$에 필요하고도 충분한 조건을 제공하며, 이 조건에서는$$ 해당 정규화된 경험적 위험 최소화 ${\displaystyle (\dadager )}$이(가)가 대표자 정리를 하게 된다$$${\displaystyle .}$특히, 이는 광범위한 종류의 정규화된 위험 최소화(Kimeldorf와 Wahba가 원래 고려했던 것보다 훨씬 더 광범위함)가 대표자의 정리를 가지고 있음을 보여준다.

적용들

대표자 이론은 규칙화된 경험적 위험 최소화 문제$){\displaystyle (\ddager )}}$를 극적으로 단순화하기 때문에 실제적인 관점에서 유용하다$.$ 가장 흥미로운 응용 분야에서는 최소화를$$ 위한 검색 $도메인{\displaystyle {}_{}}$ ${\displaystyle H_{}}$ k$${\$displaystyle H_{k}}}}}$이(가)의 무한 차원 하위 공간이 될 것이다.${\displaystyle L^{}}$ ${\displaystyle {2\mathrm{}}^{}}$( ${\displaystyle X}$) ${\displaystyle L^{2}({\mathcal {X$ 따라서 검색(서면)은 유한메모리 및 유한정밀 컴퓨터에 대한 구현을 인정하지 않는다.이와는 대조적으로, 대표자 정리에 의해$$ $제공$되는 f${\displaystyle {}^{}}$ (${\displaystyle )}$ $){\displaystyle f^{*}(\cdot )$의 표현은 계수 ${\displaystyle {\alpha \mathrm{}}_{}=}$ (${\displaystyle {}_{}}$ 1,${\displaystyle }$.${\displaystyle }$, ${\displaystyle {\alpha }_{}}$n )의${\displaystyle }$최적 $n{\displaystyle }$ ${\$ $n}$ -차원$$ 벡터 탐색으로 원래의 ($무한$ 차원) 최소화 문제를 감소시킨다.$ha =(\alpha _{1},...,\alpha _{n})\in \mathb {R}$^{$n$ $\alpha {\displaystyle }$ ${\displaystyle \alpha }$은(는) 표준 함수 최소화 알고리즘을 적용하여 얻을 수 있다$$.따라서 대표자의 이론은 일반적인 기계 학습 문제를 실제 컴퓨터에서 실제로 구현할 수 있는 알고리즘으로 줄일 수 있는 이론적 근거를 제공한다.

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2012년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

다음은 대표자 정리에 의해 존재가 보장되는 미니마이저에 대한 해결방법의 예를 제시한다.이 방법은 모든 양의 확정 $커널{\displaystyle }$ K ${\displaystyle K}$에 적용되며 복잡한(아마도 무한 치수) 최적화 문제를 숫자로 해결할 수 있는 단순한 선형 시스템으로 변환할 수 있다.

최소 제곱 오차 함수를 사용한다고 가정하십시오.

일부 $function{\displaystyle }$ >0${\displaystyle \{\backslash }$$displaystyle \lambda >0}$에 대한 정규화 함수 g ($x$ )${\displaystyle }$=$$ ${\displaystyle {x\mathrm{}}^{}}$ ($x)=\lambda$ x$^{2$ 대표자 정리로는 미니마이저.

형태를 갖추다

일부 $\alpha {\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ =${\displaystyle {}^{}({}_{}^{}}$ ${\displaystyle {1\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$,${\displaystyle }$… ,${\displaystyle {}_{}^{}}$ ${\displaystyle n_{}^{}}$ ${\displaystyle {}_{}^{}}$) ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ ${\$1}^},\$dots,\alpha _{n}^}}\in \mathb {R} ^{n$에 주목

우리는 $\alpha {\displaystyle {}^{}}$∗$${\$displaystyle$\ ^ $^{*}}}$이(가) 형태를 가지고 있음을$$ 알 수 있다.

여기서 $A{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}}$= ${\displaystyle k(}$ x ${\displaystyle i_{}}$, ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle A_{ij}=k(x_{i},x_{j})$ $및$ y${\displaystyle }$= ${\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$,${\displaystyle }$, ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$) ${\displaysty y=(y_{1},\dots ,y_{n$이것은 다음과 같이 고려되고 단순화될 수 있다.

$A{\displaystyle {}^{}}$ ${\displaystyle {⊺}^{}}$ ${\displaystyle {}^{}}$+ ${\displaystyle \lambda }$ ${\displaystyle A}$ ${\displaystyle A^{\intercal }}A+\lambda$ A$}$이(가) 양적으로 확실하므로, 이 표현에 대한 하나의 글로벌 미니마는 실제로 존재한다.Let ${\displaystyle F(\alpha )=\alpha ^{\intercal }(A^{\intercal }A+\lambda A)\alpha -2\alpha ^{\intercal }Ay}$ and note that ${\displaystyle F}$ is convex.그러면 $\alpha {\displaystyle {}^{}}$,{\$displaystyle \alpha^{*}}$ 글로벌 미니마인$$,${\displaystyle {\mathrm{}}_{}}$ ${\displaystyle \mathrm{F}}$ =${\displaystyle }$0$${\$displaystyle \nabla$_{\$alpha }F=$0}}을 설정하여 해결할 수 있다$.$ 모든 양의 한정된 수식은 되돌릴 수 없다는 것을 상기하면 우리는 알 수 있다.

선형 해결 방법을 통해 미니마이저를 찾을 수 있다.

참고 항목

• 머서의 정리
• 커널 메서드

참조

• Argyriou, Andreas; Micchelli, Charles A.; Pontil, Massimiliano (2009). "When Is There a Representer Theorem? Vector Versus Matrix Regularizers". Journal of Machine Learning Research. 10 (Dec): 2507–2529.
• Cucker, Felipe; Smale, Steve (2002). "On the Mathematical Foundations of Learning". Bulletin of the American Mathematical Society. 39 (1): 1–49. doi:10.1090/S0273-0979-01-00923-5. MR 1864085.
• Kimeldorf, George S.; Wahba, Grace (1970). "A correspondence between Bayesian estimation on stochastic processes and smoothing by splines". The Annals of Mathematical Statistics. 41 (2): 495–502. doi:10.1214/aoms/1177697089.
• Schölkopf, Bernhard; Herbrich, Ralf; Smola, Alex J. (2001). A Generalized Representer Theorem. Computational Learning Theory. Lecture Notes in Computer Science. Vol. 2111. pp. 416–426. CiteSeerX 10.1.1.42.8617. doi:10.1007/3-540-44581-1_27. ISBN 978-3-540-42343-0.