안정성(학습 이론)

알고리즘 안정이라고도 알려진 안정성은 기계 학습 알고리즘이 입력에 대한 작은 변화로 인해 어떻게 변하는지 계산 학습 이론의 개념이다.안정적인 학습 알고리즘은 훈련 데이터를 약간 수정해도 예측이 크게 변하지 않는 알고리즘이다.예를 들어, 1000개의 손편지와 라벨("A"에서 "Z"까지)을 교육 세트로 사용하여 알파벳의 손편지를 인식하도록 훈련되고 있는 기계 학습 알고리즘을 생각해 보십시오.이 교육 세트를 수정하는 한 가지 방법은 예를 생략하는 것이며, 손으로 쓴 편지와 라벨의 999개 예만 사용할 수 있도록 하는 것이다.안정적인 학습 알고리즘은 1000초 및 999초 훈련 세트와 유사한 분류기를 생성할 수 있다.

안정성은 학습되는 정보의 유형보다는 학습 과정의 속성이기 때문에 언어 학습에서 물리 및 공학에서의 역문제로 이어지는 여러 유형의 학습 문제에 대해 연구할 수 있다.안정성 연구는 2000년대 일반화와 연관성이^{[citation needed]} 있는 것으로 나타났을 때 연산학습 이론에서 중요해졌다.대규모 학습 알고리즘, 특히 경험적 위험 최소화 알고리즘의 경우 특정 유형의 안정성이 우수한 일반화를 보장하는 것으로 나타났다.

역사

머신러닝 시스템 설계의 중심 목표는 학습 알고리즘이 한정된 숫자에 대해 훈련을 받은 후 새로운 예에 대해 일반화하거나 정확하게 수행하도록 보장하는 것이다.1990년대에, 감독된 학습 알고리즘에 대한 일반화 한계를 얻는 데 있어 이정표가 달성되었다.역사적으로 일반화를 증명하기 위해 사용된 기술은 경험적 양의 균일한 수렴 특성을 그들의 수단에 사용하면서 알고리즘이 일관성이 있다는 것을 보여주는 것이었다.이 기법은 많은 종류의 경험적 위험 최소화(ERM) 알고리즘에 대한 일반화 한계를 얻기 위해 사용되었다.ERM 알고리즘은 훈련 세트 $S{\displaystyle }$ ${\displaystyle S}$에 대한 경험적 오류를 최소화하기 위해$$ 가설 $공간{\displaystyle }$ H ${\displaystyle H}$에서 솔루션을 선택하는 알고리즘이다$.$

블라디미르 Vapnik가 ERM 이항 분류 알고리즘에 대해 입증한 일반적인 결과는 모든 대상 함수 및 입력 분포$,$ $VC-차원$ d {\$displaystyle{\displaystyle }$ d} 및 n {\displaystyle $n}$ 훈련$$ 예제를$$ 가진 가설 $공간{\displaystyle }$ H$$${\\\$$displaystyle H$}에 대해 알고리즘이 일관성이 있으며 훈련 어를 생성한다는 것이다.실제 오류로부터 최대 $O{\displaystyle (d\sqrt{\frac{}{}}}$ ${\displaystyle \sqrt{\frac{n}{}}}$) ${\$및 로그 요인).그 결과는 후에 고유한 미니마이저가 없는 기능 클래스를 가진 거의 ERM 알고리즘으로 확장되었다.

VC 이론으로 알려지게 된 것을 사용한 Vapnik의 연구는 학습 알고리즘의 일반화와 학습 중인 함수의 가설$$ 공간 $H{\displaystyle }$ ${\displaystyle H}$의 특성 사이에 관계를 설정했다.그러나 이러한 결과는 무한 VC차원 가설공간을 가진 알고리즘에는 적용할 수 없었다.달리 말하면, 학습되는 정보의 복잡성이 너무 커서 측정할 수 없는 경우에는 이러한 결과를 적용할 수 없다.예를 들어 회귀와 같은 가장 간단한 기계 학습 알고리즘에는 제한되지 않은 VC-차원 가설 공간이 있다.또 다른 예는 임의 길이의 문장을 만들 수 있는 언어 학습 알고리즘이다.

안정성 분석은 2000년대에 컴퓨터 학습 이론을 위해 개발되었으며 일반화 한계를 얻기 위한 대안 방법이다.알고리즘의 안정성은 $가설공간{\displaystyle }$ H ${\displaystyle H$의 직접적 속성이 아니라 학습과정의 속성이며, 가장 가까운 이웃과 같이 무한하거나 정의되지 않은 VC-dimension을 가진 가설공간을 가진 알고리즘에서 평가할 수 있다.안정적 학습 알고리즘은 예를 들어 예를 들어, 훈련 세트를 약간 수정했을 때 학습된 기능이 크게 변하지 않는 알고리즘이다.손실 함수에 대한 학습 알고리즘의 안정성을 평가하기 위해 크로스 유효성 검사 원아웃(CVLoo) 알고리즘에 Leave One Out 오류가 사용된다.이와 같이 안정성 분석은 기계학습에 민감도 분석을 적용하는 것이다.

클래식 결과 요약

• 1900년대 초반 - 학습 이론의 안정성은 안드레이 니콜라예비치 티호노프(Andrey Nicolayevich Tikhonov^{[citation needed]})의 추적으로 학습 지도 $(\displaystyle L}$의 연속성 측면에서 가장 일찍 설명되었다$.$
• 1979 - Devroye와 Wagner는 알고리즘의 이탈-원아웃 동작이 표본의 작은 변화에 대한 민감도와 관련이 있다고 보았다.^[1]
• 1999 - Kearns와 Ron은 유한 VC-차원성과 안정성 사이의 연관성을 발견했다.^[2]
• 2002 - 한 랜드마크 논문에서 부스케와 엘리스제프는 학습 알고리즘의 균일한 가설 안정성 개념을 제안했고, 낮은 일반화 오류를 내포하고 있음을 보여주었다.그러나 균일한 가설 안정성은 두 함수의 가설공간에 불과한 ERM 알고리즘을 포함하여 알고리즘의 대분류에는 적용되지 않는 강한 조건이다.^[3]
• 2002 - Kutin과 Niyogi는 Bousquet과 Elisseff의 결과를 거의 모든 곳에서 안정이라고 부르는 몇 가지 약한 형태의 안정성에 대한 일반화 한계를 제공함으로써 확장시켰다.또한, 그들은 ERM 알고리즘의 안정성과 일관성 사이의 관계를 설정하기 위해 PAC(Presidently Correct) 설정에서 초기 단계를 밟았다.^[4]
• 2004 - Poggio 외 연구진은 안정성과 ERM 일관성 사이의 일반적인 관계를 입증했다.그들은 CVEELoo 안정성이라고 하는 1회성 안정성의 통계적 형태를 제안하였고, 이것이 a) 경계 손실 등급의 일반화를 위해 충분하고, b) 사각 손실, 절대값, 절대값과 같은 특정 손실 기능에 대한 ERM 알고리즘의 일관성(따라서 일반화)에 필요하고 충분하다는 것을 보여주었다.이항분류손실^[5]
• 2010 - 셰일브 슈워츠 외 연구진은 가설 공간과 손실 등급 간의 복잡한 관계로 인해 Vapnik의 원래 결과에 문제가 있음을 알아차렸다.그들은 서로 다른 손실 수업과 다른 유형의 학습, 감독 및 감독되지 않은 학습을 포착하는 안정성 개념에 대해 논의한다.^[6]
• 2016 - Moritz Hardt 외.는 모델을 업데이트하기 위해 각 인스턴스를 사용하는 횟수와 가설에 대한 특정 가정을 고려할 때 구배 강하의 안정성을 입증했다.^[7]

예비 정의

우리는 학습 알고리즘 훈련 세트와 관련된 몇 가지 용어를 정의하여 안정성을 다방면으로 정의하고 현장에서의 정리를 제시할 수 있다.

학습 맵 $L{\displaystyle }$ ${\displaystyle L}$이라고도 하는 시스템 학습 알고리즘이 교육 데이터 세트를 매핑하는데$,$ 이 세트는 레이블이 붙은 예$({\displaystyle x}$, y${\displaystyle }$) ${\displaystyle(x,y$의 $함수$ $f{\displaystyle }$ ${\displaystyle$ y$}$에 X ${\displaysty$ X$}$에서 $Y{\displaystyle }$ ${\\\\displaysty$$}$까지 입니다.$Playstyle Y}$은(는) 훈련 예시와 같은 공간에 있다$$.함수 $f{\displaystyle }$ ${\displaystyle f}$은(는) $H{\displaystyle }$ ${\displaystyle H}$라는 함수의 가설 공간에서 선택된다$.$

알고리즘이 학습하는 교육 세트는 다음과 같이 정의된다.

${\displaystyle S=\{z_{1}=(x_{1},\ y_{1}}\, ..\ z_{m}=(x_{m},\ y_{m})\}}$

크기 $m{\displaystyle }$ ${\displaystyle m}($$Z$ = ${\displaystyle X}$ ${\displaystyle \times }$ ${\displaystyle Y}$ ${\displaystyle Z=X\time$ Y$})$

미확인 분포 D에서 I.I.D.

Thus, the learning map ${\displaystyle L}$ is defined as a mapping from ${\displaystyle Z_{m}}$ into ${\displaystyle H}$, mapping a training set ${\displaystyle S}$ onto a function ${\displaystyle f_{S}}$ from ${\displaystyle X}$ to ${\displaystyle Y}$. Here, we consider only deter$L{\displaystyle }$ ${\displaystyle L}$이(가) $S{\displaystyle }$ ${\displaystyle S$에 대해 대칭인$$ 미니스틱 알고리즘. 즉, 훈련 세트의 요소 순서에 따라 달라지지 않는다.더욱이, 우리는 모든 기능이 측정 가능하고 모든 세트가 셀 수 있다고 가정한다.

예제 $z{\displaystyle }$= (${\displaystyle }$x${\displaystyle }$, y )${\displaystyle z=(x,y)}$에 대한 $가설$ f ${\displaystyle f}$의 $손실{\displaystyle }$ V ${\$$displaystyle$ V$}$은${\displaystyle (f}$ ,${\displaystyle }$z${\displaystyle }$)${\displaystyle }$= ${\displaystyle V}$($f,z)=V(f(x),y)$로 정의된다$.$

$f{\displaystyle }$ ${\displaystyle f}$의 경험적 오류는 ${\displaystyle I_{}}$ $S{\displaystyle {}_{}}$[ ${\displaystyle f}$ ${\displaystyle ]}$= ${\displaystyle \mathrm{1n}}$ ${\displaystyle \sum }$ V ${\displaystyle (f,}$ ${\displaystyle z_{}}$ i${\displaystyle {}_{}}$) ${\displaystyle I_{S}[f]={\frac${1$}{n}}\sum V(f,z_{i})$이다$.$

$f{\displaystyle }$ ${\displaystyle f}$의 실제 오류는 $I{\displaystyle }$[ ${\displaystyle f}$ ${\displaystyle ]}$= E ${\displaystyle {}_{}}$ V ${\displaystyle (f}$, z${\displaystyle }$) ${\displaystyle I[f]=\mathb {E} _{z}V(f,z)}$이다.

m 크기의 훈련 세트 S가 주어지면, 우리는 모든 i = 1....,m에 대해 다음과 같이 수정된 훈련 세트를 만들 것이다.

• i번째 요소를 제거하여

${\displaystyle S^{i}=\{z_{1},...,\ z_{i-1},\ z_{i+1},...,\z_{m}\}}}}$

• i-th 요소를 교체하여

${\displaystyle S^{i}=\{z_{1},...,\ z_{i-1},\ z_{i},\z_{m}\}}}}$

안정성 정의

가설 안정성

알고리즘 $L{\displaystyle }$ ${\displaystyle L}$에는 다음과 같은 경우 손실 함수 V에 대한 가설 안정성 β가 있다$$.

${\displaystyle \forall i\in \{1,...,m\}\mathb {E}_{S,z}[V(f_{S}z)-V(f_{S^{i},z) ]\leq \beta .}$

점-와이 가설 안정성

알고리즘 $L{\displaystyle }$ ${\displaystyle L}$은 다음과 같은 경우 손실 함수 V에 대한 점-와이 가설 안정성 β를 가진다$$.

${\displaystyle \forall i\in \{1,...,m\}\mathb {E}_{S}[ V(f_{S}}z_{i})-V(f_{S^{i}{i}}},z_{i}) ]\leq \bta .}$

오류 안정성

알고리즘 $L{\displaystyle }$ ${\displaystyle L}$은 다음과 같은 경우 손실 함수 V에 대한 오류 안정성 β를 가진다$$.

${\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\}, \mathb {E} _{Z(F_{S}z)-\mathb {E} _{Z(V_{S^{i},z) \leqbeta }}}}$

균일 안정성

알고리즘 $L{\displaystyle }$ ${\displaystyle L}$은 다음과 같은 경우 손실 함수 V에 대해 동일한 안정성 β를 가진다$$.

${\displaystyle \forall S\in Z^{m},\all i\in \{1,...,m\}\sup_{z\in Z}V(f_{S},z)-V(f_{S^{i},z) \leq \beta }}}$

균일한 안정성 β의 확률론적 버전은 다음과 같다.

${\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\},\mathbb {P} _{S}\{\sup _{z\in Z} V(f_{S},z)-V(f_{S^{ i}},z) \leq \beta \}\geq 1-\delta }$

알고리즘은 $\beta {\displaystyle }${\$displaystyle$ \$beta }$의 ${\displaystyle 값}$이 O ${\displaystyle (\frac{\mathrm{1m}}{}}$) {\$displaystyle$O({\$frac {$1}{m$})$로 감소할$$ 때 안정적이라고 한다$.$

1-아웃 교차 검증(CVLoo) 안정성

알고리즘 $L{\displaystyle }$ ${\displaystyle L}$에는 다음과 같은 경우 손실 함수 V에 대한 CVloo 안정성 β가 있다$$.

${\displaystyle \for \in \{1,...,m\}\mathb {P} _{S}\{V(f_{S}},z_{i})-V(f_{S^{i}}} \leq \{CV}\geq 1-delta _{CV}}}}$

(CVLoo) 안정성의 정의는 앞에서 살펴본 포인트-가설적 안정성과 동일하다.

예상-유휴-원아웃 오류(${\displaystyle }$ ${\displaystyle l}$ ${\displaystyle o}$ ${\displaystyle o_{}}$ e ${\displaystyle r_{}}$ ${\$ 안정성

알고리즘 $L{\displaystyle }$ ${\displaystyle L}$은(는) $각{\displaystyle }$ n에 대해 $\beta {\displaystyle {}_{}^{}}$ ${\displaystyle E_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle m_{}^{}}$ ${\$ $Eloo_{err}$ 안정성이$$ 있으며$$$$$$$\Delta {\displaystyle {}_{}^{}}$ ${\displaystyle E_{}^{}}$ ${\displaystyle L_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$err$}}}:{m$:

${\displaystyle \forall i\in \{1,...,m\},\mathbb {P} _{S}\{ I[f_{S}]-{\frac {1}{m}}\sum _{i=1}^{m}V(f_{S^{ i}},z_{i}) \leq \beta _{EL}^{m}\}\geq 1-\delta _{EL}^{m}}$, with ${\displaystyle {\beta }_{EL}^{}}$$m{\displaystyle }$ ${\$ 및$$ $\Delta {\displaystyle {}_{}^{}}$ E ${\displaystyle {}_{}^{}}$ ${\displaystyle m_{}^{}}$ ${\$ m에 대해 0으로 설정$$${\displaystyle ,}$ → ${\displaystyle \mathrm{\infty }}$ ${\displaystystym$ m$,\rightarrow \ft.}$

고전적 정리

From Bousquet and Elisseff (02):

경계 손실이 있는 대칭 학습 알고리즘의 경우 알고리즘이 위의 확률론적 정의와 함께 균일 안정성이 있는 경우 알고리즘이 일반화된다.

균일 안정성은 모든 알고리즘에 의해 충족되는 것은 아니지만 놀랍게도 정규화 알고리즘의 크고 중요한 클래스에 의해 충족되는 강한 조건이다.일반화의 속박은 기사에 나와 있다.

출처: 무케르지 외 (06):

• 경계 손실이 있는 대칭 학습 알고리즘의 경우 알고리즘에 위에 정의된 바와 같이 Leave-one-out CVloo(CVDoo) 안정성과 기대-leave-one-out 오류(${\displaystyle \mathrm{El}}$ ${\displaystyle o}$ ${\displaystyle o_{}}$ e ${\displaystyle r_{}}$ ${\$ 안정성이 모두 있으면 알고리즘이 일반화된다.
• 두 조건만으로는 일반화를 위한 충분치 않다.그러나 두 가지 모두 일반화를 보장한다(반대가 사실이 아님).
• 특히 ERM 알고리즘의 경우(사각형 손실에 대해 설명), Leave-one-out cross-validation(CVLoo) 안정성은 일관성과 일반화를 위해 필요하며 충분하다.

이것은 학습 이론의 기초에 있어서 중요한 결과로서, 이전에 관계가 없었던 알고리즘의 두 가지 속성인 안정성과 일관성이 ERM(및 특정 손실 기능)과 동등하다는 것을 보여주기 때문이다.일반화의 속박은 기사에 나와 있다.

안정적인 알고리즘

안정성이 입증된 알고리즘 목록과 관련 일반화 한계를 제공하는 글이다.

• 선형 회귀 분석^[8]
• {0-1} 손실 함수가 있는 k-NN 분류기.^[1]
• Replicating Kernel Hilbert Space에서 경계 커널 및 정규화기가 표준인 SVM(Vector Machine) 분류 지원.큰 정규화 상수 $[\displaystyle C]$가 좋은 안정성으로 이어진다$$.^[3]
• 소프트 마진 SVM 분류.^[3]
• 정규화된 최소 제곱 회귀 분석.^[3]
• 분류를 위한 최소 상대 엔트로피 알고리즘.^[3]
• $n{\displaystyle }$ ${\displaystyle n}$과(와) 함께 증가하는 regressor의 $숫자$$$k {\$displaystyle k}$과(와) 함께 백깅 정규화기 버전$.$^[9]
• 다중 클래스 SVM 분류.^[9]
• Tikhonov 정규화가 적용된 모든 학습 알고리즘은 균일한 안정성 기준을 만족하므로 일반화할 수 있다.^[10]

참조

추가 읽기