온라인 머신 러닝

시리즈의 일부
기계 학습 및 데이터 마이닝
문제 분류 클러스터링 회귀 이상 검출 데이터 클리닝 자동 ML 어소시에이션 규칙 강화 학습 구조화된 예측 기능 엔지니어링 기능 학습 온라인 학습 준지도 학습 비지도 학습 순위 매기기 학습 문법 유도
지도 학습 (분류 • 회귀) 의사결정 트리 앙상블 배깅 부스팅 랜덤 포레스트 k-NN 선형 회귀 네이비 베이즈 인공신경망 로지스틱 회귀 분석 퍼셉트론 관련 벡터 머신(RVM) 서포트 벡터 머신(SVM)
클러스터링 버치 치유하다 계층적 k자형 기대 최대화(EM) DBSCAN 광학 평균 이동
치수 축소 인자 분석 CCA ICA LDA NMF PCA PGD t-SNE
구조화된 예측 그래픽 모델 베이즈 네트 조건부 랜덤 필드 히든 마르코프
이상 검출 k-NN 국소 특이치 계수
인공신경망 자동 인코더 인지 컴퓨팅 딥 러닝 딥 드림 다층 퍼셉트론 RNN LSTM GRU ESN 저장고 계산 제한 볼츠만 기계 GAN somerset. 컨볼루션 뉴럴 네트워크 유넷 트랜스포머 비전. 스파이킹 뉴럴 네트워크 메모리 트랜지스터 전기화학 RAM(ECRAM)
강화 학습 Q-러닝 사사 시간차(TD) 멀티 에이전트 셀프 플레이
인간과의 학습 액티브 러닝 크라우드 소싱 휴먼 인 더 루프
모델 진단 학습 곡선
이론. 커널 머신 바이어스-분산 트레이드오프 컴퓨터 학습 이론 경험적 리스크 최소화 오컴 러닝 PAC 학습 통계학 학습 VC 이론
기계학습장 NeurolIPS ICML ML JMLR ArXiv:cs.LG
관련 기사 인공지능 용어집 기계 학습 연구를 위한 데이터 세트 목록 기계학습의 개요
v t

컴퓨터 과학에서 온라인 머신 러닝은 전체 트레이닝 데이터 세트를 동시에 학습하여 최적의 프레딕터를 생성하는 배치 학습 기법과 달리 데이터가 순차적으로 사용 가능하게 되고 각 단계에서 미래의 데이터에 대한 최적의 프레딕터를 업데이트하는 기계 학습 방법이다.온라인 학습은 전체 데이터 세트에 대한 훈련이 계산적으로 불가능한 기계 학습 영역에서 사용되는 일반적인 기술이며, 코어 외 알고리즘이 필요합니다.또한 알고리즘이 데이터의 새로운 패턴에 동적으로 적응해야 하는 상황이나 주가 예측과 같이 데이터 자체가 시간의 함수로 생성되는 상황에도 사용된다.온라인 학습 알고리즘은 치명적인 간섭을 일으키기 쉬우며, 이는 증분 학습 접근방식으로 해결할 수 있는 문제입니다.

서론

지도 학습 설정에서는 f${\displaystyle }$: ${\displaystyle X}$ ${\displaystyle \to }$ (\$displaystyle$ f$:X\to$Y )의$$ $함수$를 학습합니다. $여기$서 X $(\displaystyle$ X$)$는 입력의 $공간$이고$$Y (\$displaystyle$$$Y)는 출력의 공간으로 간주되며, 이는 예를 들어${\displaystyle }p{\displaystyle }$ ${\displaystyle (\backslash }$displaystyle Y$$)에서 도출되는 것을 잘 예측합니다.$스타일$ p$($$x,y)$는 X${\displaystyle }$×$$(\$displaystyle$ X$\times$ Y$)$에 해당됩니다. 실제로 학습자는 인스턴스${\displaystyle (}instance{\displaystyle )}$에 대한 $실제$분포 p($x,y)$를 결코 알지 못합니다.대신, 학습자는 ${\displaystyle {일반적}_{}}$으로 교육용 예$({\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$1 ${\displaystyle ),}$ ${\displaystyle ...}$ ,${\displaystyle }$( ${\displaystyle x_{}}$n , ${\displaystyle {}_{}{n}_{}}$ $),$ \$ldots ,$ ( $x$_ {$n$ , $y _${ $n$ )에 $액세스할$ 수 있습니다. 이 $설정$에서는 손실 함수는${\displaystyle }V{\displaystyle }$ :${\displaystyle Y}$ × ${\displaystyle Y}$ ${\displaystyle \to }$ { $style$ V$:$Y$\times$ Y$\to$ \$mathbb {R}$${\displaystyle }$$。$${\displaystyle V}$ (${\displaystyle x}$) ,${\displaystyle }$y$$) { $displaystyle$V ($f$ ($x$ , y ) } $measures$$$ 、 예측값${\displaystyle }f{\displaystyle }$ (${\displaystyle x}$) { $displaystyle$f ($x$ ) 、 $true값{\displaystyle }$y ( \ $displaystyle$y$$)의$$ 차이를 측정합니다.이상적인 목표는 함수 $f{\displaystyle }$ ${\displaystyle H\mathcal{}}$($여기$서$$H {\$displaystyle {H}}$는 가설 공간이라고 하는 함수의 공간)를 선택하여 전체 손실의 개념을 최소화하는 것입니다.모델의 유형(통계적 또는 적대적)에 따라 상실의 다른 개념을 고안할 수 있으며, 이는 상이한 학습 알고리즘으로 이어진다.

온라인 학습 통계 뷰

통계적 학습 모델에서 훈련 샘플$({\displaystyle {xi}_{}}$ $)$ {$displaystyle (x_{i$}, $y_{i})$은 실제 $분포{\displaystyle }$ p${\displaystyle (x,}$y$)$ {$displaystyle$ p$(x,y)}$에서 추출된 것으로 가정하며, 목표는 예상되는 "위험"을 최소화하는 것이다.

${\displaystyle I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y),dp(x,y)\ .}$

이 상황에서 공통적인 패러다임은 경험적 위험 최소화 또는 정규화된 경험적 위험 최소화(일반적으로 티코노프 정규화)를 통해 $함수{\displaystyle \stackrel{}{}}$f$^(\$를 추정하는 것이다.여기서 손실 함수의 선택은 정규화된 최소 제곱 및 지원 벡터 기계와 같은 몇 가지 잘 알려진 학습 알고리즘을 발생시킨다.이 범주의 순수 온라인 모델은 새로운 입력$({\displaystyle x_{}}$t +${\displaystyle {}_{}{1}_{}}$, ${\displaystyle y_{}}$t +$)(x$ style $(x_{t+1$ $현재$ 최고의 예측 $변수{\displaystyle {}_{}}$ ${\displaystyle f_{}}${$displaystyle f_{t$}}) 및 일부 추가 저장 정보(보통 교육 데이터 크기에 관계없이 저장 요구 사항이 있을 것으로 예상됨)만을 기반으로 학습합니다.예를 들어 비선형 커널 방식 등 많은 공식에서 진정한 온라인 학습은 불가능하지만 ${\displaystyle f_{}}$ t$$+ ${\displaystyle 1_{}}$ $({$$displaystyle f_{t+$$1})$ 및$$ ${\displaystyle {모든}_{}}$ 이전 데이터 포인트$({\displaystyle {x\mathrm{}}_{}}$1, ${\displaystyle {}_{}{1\mathrm{}}_{})}$에 $의존$할 수 있는 $경우{\displaystyle {}_{}}$ 재귀 알고리즘을 사용한 하이브리드 온라인 학습 형식을 사용할 수 있습니다${\displaystyle .}$${\displaystyle ,}$ ( ${\displaystyle {}_{}{t}_{}}$ , ${\displaystyle y_{}}$t$$) { $display$ style ($x _$ ${$1} , $y$_ {1$}$ ) , \$ldots$, ( x$_$ {$t$ , y$_$ { t )$\}$ 。이 경우 이전의 모든 데이터 포인트를 저장해야 하므로 공간 요건은 일정하지 않지만 새로운 데이터 포인트를 추가하는 경우 배치 학습 기술에 비해 계산에는 시간이 적게 소요될 수 있습니다.

위의 문제를 극복하기 위한 일반적인 전략은 미니 배치를 사용하여 학습하는 것입니다. 미니 배치는 한 번에$$소량의 ${\displaystyle \mathrm{데이터}}$ 포인트를 처리하는 것으로, 이는 총 교육 포인트 수보다 훨씬 적은 b$$${\displaystyle \{\backslash }$$display style$ b$}$에 $대한{\displaystyle }$ 의사 온라인 학습으로 간주할 수 있습니다.미니 배치 기법은 예를 들어 확률적 경사 하강과 같은 기계 학습 알고리즘의 최적화된 코어^{[clarification needed]} 외 버전을 얻기 위해 훈련 데이터를 반복적으로 전달하는 것과 함께 사용된다.역전파와 결합하면 현재 인공신경망을 양성하기 위한 사실상의 훈련방법이다.

예제: 선형 최소 제곱

선형 최소 제곱의 간단한 예는 온라인 학습에서 다양한 아이디어를 설명하는 데 사용됩니다.아이디어는 예를 들어 다른 볼록 손실 함수와 같은 다른 설정에 적용될 수 있을 정도로 충분히 일반적입니다.

배치 학습

f$${\$displaystyle$ f$}$가 학습해야 할 선형 함수인 감독 학습 설정을 고려하십시오.

$\displaystyle f(x_{j})=\cdot w,x_{j}\rangle =w\cdot x_{j}$

${\displaystyle {여기}_{}}$서 x j$$ R \$style x_{j}\in \mathbb {R}^{d}$는 입력(데이터 포인트)의 $벡터$이고 w${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ d$$\ $displaystyle$ w$\in \mathbb {R}$^ {$d}$는 선형 필터 벡터입니다.필터 $벡터$를 w$\backslash$$displaystyle$w로 계산하는 것이 목표입니다. 이를 위해 제곱 손실 함수

${\displaystyle V(x_{j}), y_{j}=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}}$

경험적 손실을 최소화하는 $벡터{\displaystyle }$ w$\displaystyle$w를$$ 계산하는 데 사용됩니다.

${\displaystyle I_{n}[w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle,y_{j}=\sum _{j=1}^{n}(x_{j}^{})^{n}T}w-y_{j}^{2}}$

어디에

$y$ ${\displaystyle j\mathbb{}}$ { R \ $displaystyle$y_{$j}$\ $in$ \ $mathbb$ { R$\}$ $。$

X$(\displaystyle$ X$)$를${\displaystyle }$i ×$$(\$displaystyle$ i$\times$ d$)$ $데이터$ 매트릭스, $(\$ y$\in\mathbb {R} ^{$i$$})를 $첫{\displaystyle }$ 번째$$i(\$displaystyle$i) 데이터$$ 포인트 도착 후의 목표값 열 벡터라고 합니다.공분산 행렬 ${\displaystyle {\delta }_{}}$ i $=$ ${\displaystyle {}^{}}$ ${\displaystyle T^{}}$ ({$displaystyle \Sigma$ _${i$}=$X^{T}X$$})$ 가역행렬이라고 가정할 때(따라서 티코노프 정규화를 유사한 방식으로 진행하는 것이 선호됨), ${\displaystyle \mathrm{최선}}$의 $솔루션{\displaystyle {}^{}}$ f${\displaystyle {}^{}}$δ (${\displaystyle x}$) $displaystyle$ f$= rel$ ($x$)에 의해 주어집니다.

$X^{T}X)^{-1}X{$$T}y=\Sigma$ _${i}^{-1}\sum$_{$j=1}^{i}x_{j}y_{j$

이제 공분산 행렬 ${\displaystyle {\delta i}_{}}$ ${\displaystyle {}_{}}$ $=$ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle i_{}^{}}$ x j$$ { $displaystyle \Sigma$ _${i}=\sum$ _{$j=1$}^{$i}x_{$$j$}^{{j}^{T$}}$은${\displaystyle (}$는) 시간${\displaystyle }$O(${\displaystyle {i\mathrm{}}^{}}$ d2$)$ {$displaystyle O(id^{2$ {$displaystyle$ d$\times$ d$}$ $행렬$을 반전하면 $시간{\displaystyle }$O($displaystyle$ d${\displaystyle {}^{}}$times d$\})$가 소요되며 나머지 곱셈에는 $시간{\displaystyle }$ O$displaystyle$ O$(d^{3$$})$$${2$\})$가 소요되며 총 시간 ${\displaystyle {O\mathrm{}}^{}(}$d)가 소요됩니다.$yle$ O$(id^{2}+$${\displaystyle {}^{}}$$^{3$ 데이터 세트에$$n개의 \$displaystyle$${\displaystyle \mathrm{n개}}$의 총점이 $있는{\displaystyle }$ 경우$,$(\$displaystyle$ i$=1,\ldots,n$의 도착 후 솔루션을 재계산하려면 순진한 접근법은 총 $복잡도{\displaystyle }$O$(n$ ${\displaystyle {}^{}{}^{}}$ ${\displaystyle \mathrm{d2}{}^{}}$+ $display$ 3$)$가 됩니다.when storing the matrix ${\displaystyle \Sigma _{i}}$, then updating it at each step needs only adding ${\displaystyle x_{i+1}x_{i+1}^{$$T$ O$displaystyle$ O$(d^{2})$시간이$$ $걸리며{\displaystyle }$ 총 시간은 O${\displaystyle (n}$ ${\displaystyle {d2\mathrm{}}^{}}$+ ${\displaystyle {}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$)$=$ $(ndisplaystyle$ O$(nd^{2}+nd^{3$로 $단축$되지만 O$(display$ 2$)$의 추가 저장 공간이 $있습니다$$.$

온라인 학습: 재귀 최소 제곱

재귀 최소 제곱(RLS) 알고리즘은 최소 제곱 문제에 대한 온라인 접근 방식을 고려합니다.${\displaystyle {w\mathrm{}}_{}}$ 0 ${\displaystyle {}_{}}$ ${\displaystyle 0{\mathbb{}}^{}}$ R ${\displaystyle {}^{}}$\ $displaystyle w _$ { 0 } $= 0$ \ $in$\$mathbb { R$ } ^ { $d$} { ${\displaystyle 0_{}}$ ${\displaystyle {\mathbb{}}^{}}$ 0 ${\displaystyle =}$ R ${\displaystyle d^{}}$×$$d \ $displaystyle \ Gamma$_ { 0$=$$I\in \mathbb {R} ^{d\times$ d$\}$ 。이전 섹션에서 설명한 선형 최소 제곱 문제의 해법은 다음과 같은 반복으로 계산할 수 있습니다.

$\displaystyle \Gamma _{i}=\Gamma _{i-1}-{\frac {Gamma _{i}x_{i}^{T}\Gamma _{i-1}}{1+x_{i}^{T}\Gamma _{i-1}x_{i}}}}$

$\displaystyle w_{i}=w_{i-1}-\Gamma_{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i}}$

위의 반복 알고리즘은 i$\displaystyle$^[2]인덕션을 사용하여 증명할 수 있습니다.이 증명은 또한 ${\displaystyle {\gamma }_{}}$ i ${\displaystyle {}_{}}$ ${\displaystyle {\sigma }_{}^{}}$i -$$ { $displaystyle$\ $Gamma$_ { i } = \ $Sigma$_ { $i$}^{ -$1$ 이며, RLS는 적응형 필터의 맥락에서 볼 수도 있습니다(RLS 참조).

이 알고리즘의$$n개의 \$displaystyle$n 스텝의$$ $복잡도$는 O${\displaystyle ({}^{}}$ $)\displaystyle$ O$(nd^{2$로 대응하는 배치 학습 복잡도보다 훨씬 빠릅니다.$여기$서의 각 $i$의 스토리지$$ 요건은 O${\displaystyle }$( ${\displaystyle {d\mathrm{}}^{}}$)$$( $displaystyle$\ $Gamma$_ {$i$$}$)에서 일정하게 행렬 ${\displaystyle i_{}}$ i$$( \ $displaystyle$ \ Sigma _ { $i$$$} )를 저장하는 것입니다.${\displaystyle {III}_{}}$\ $displaystyle$\ $Sigma$_ {$$$i$ } 가$$ 반전할 수 없는 경우, funced version의 일반적인 문제를 고려하십시오.tion${\displaystyle \underset{j}{\overset{}{}}}$ j ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle \underset{}{\overset{}{1}}}$ ( ${\displaystyle x_{}^{}}$ j ${\displaystyle {}_{}^{}{}_{}^{}}$ - ${\displaystyle {}_{}{}^{}{j}_{}}$ )${\displaystyle {}^{}{2\mathrm{}}^{}}$ + ${\displaystyle w}$ ${\displaystyle {\mathrm{}}_{}^{}}$ 2$$( \ $displaystyle \sum$_ { j$$=$1 }^{n}($x_{$j}^)$$T}w-y_{j}^{2}+\lambda w_{2$ 그러면 동일한 알고리즘이 ${\displaystyle {\delta \mathrm{}}_{}}$ 0 ${\displaystyle =}$ ($I$+ ${\displaystyle \delta {}^{}}$I${\displaystyle {)}^{}}$ -$$ \$Gamma _{0$} = (I$+\lambda$ I$)^{-$1$\}$ 에서 ${\displaystyle {동작}_{}}$하고 있음을 쉽게 알 수 있습니다.

확률적 경사 강하

이럴 때

$\displaystyle w_{i}=w_{i-1}-\Gamma_{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i}}$

에 의해 대체됩니다.

$\displaystyle w_{i}=w_{i-1}-\display_{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i}=w_{i-1}-\gamma_{i}\gamma V(\langle w_{i},x_{i}\rangle,y_{i}})$

또는 ${\displaystyle {\gamma }_{}}$ i ${\displaystyle {}_{}}$ ${\displaystyle {}^{}}$ d${\displaystyle {}^{}}$×$$ \ $displaystyle$\ $Gamma$_ { $i$} \ $in$\$mathbb { R$ } ^ {$d$ \ $times$ d$}$ by$$ ${\displaystyle i_{}}$ i${\displaystyle {}_{}r\mathbb{}}$ R$$\ $displaystyle$\$gamma$_ { $i$} \ $in$\ $mathbb${ $R$ 이것이 확률적 경사 하강 알고리즘이 됩니다.이 경우 이 알고리즘의 n개의 $\displaystyle$n $스텝$의 복잡도는 O$)\display$ O$(nd$로 감소합니다.$모든$ $단계$에서의 스토리지$$요건은 $O{\displaystyle }$(${\displaystyle d}$ ) { $displaystyle$O ($d$ )$$。

단, 위와 같이 예상되는 리스크 최소화 문제를 해결하기 위해서는 스텝사이즈 ${\displaystyle {①}_{}}$ i$\display$ \$gamma$ _${i}$를 신중하게 선택해야 합니다.감쇠 단계 ${\displaystyle {크기}_{}}$ i i${\displaystyle {}_{}\frac{\sqrt{i}}{}}$ 1${\displaystyle \frac{}{}}$i$$, \ $displaystyle \ display style$_ { i } \ {\ \ $frac$ { } { \ $frac$ { } { \ $frac$ { $i$} }$$${ n$ $1$ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$ ${\displaystyle \underset{}{\overset{}{=}}}$ $1$ n w i =$frac$ { $1$} =$frac$ { 1$sum$} { frac { displaysty } } } } } $1$ 。이 설정은 확률적 최적화의 특수한 경우로,^[1] 최적화의 잘 알려진 문제입니다.

증분 확률적 경사 강하

실제로는 데이터에 대해 복수의 확률적 경사 패스(사이클 또는 에폭이라고도 함)를 수행할 수 있습니다.이렇게 얻은 알고리즘은 증분 구배법이라고 불리며 반복에 대응한다.

$\displaystyle w_{i}=w_{i-1}-\displayla V(\langle w_{i-1},x_{t_{i}}\rangle,y_{t_{i}}})$

확률적 구배법의 주된 차이점은 i$\displaystyle$i-step에서$$ $방문$할 훈련 포인트를 결정하기 위해 ${i}$를 선택한다는 것이다.그러한 순서는 확률적일 수도 있고 결정적일 수도 있다.그런 다음 반복 횟수가 포인트 수로 분리됩니다(각 포인트는 두 번 이상 고려될 수 있습니다).증분 경사 방법은 경험적 ^[3]위험에 대한 최소화를 제공하는 것으로 나타날 수 있다.증분 기법은 많은 용어의 합으로 구성된 객관적 함수를 고려할 때 유리할 수 있다. 예를 들어 매우 큰 데이터 ^[1]세트에 해당하는 경험적 오류이다.

커널 방식

커널을 사용하여 위의 알고리즘을 비파라미터 모델(또는 파라미터가 무한 차원 공간을 형성하는 모델)로 확장할 수 있습니다.대응하는 순서는 더 이상 진정한 온라인 상태가 아니라 모든 데이터 포인트를 저장해야 하지만 여전히 brute force 방식보다 빠릅니다.이 논의는 볼록 손실까지 확장될 수 있지만 제곱 손실의 경우로 제한됩니다.$Xi($xisplaystyle $X_{i$})가$$ 데이터 $매트릭스$이고 $wi($xisplaystyle $w_{i$})가$$ SGD 알고리즘의 i$(\displaystyle$ i$)$ 단계$$ $후$의 출력이라는 $것$을 쉽게 알 수 있습니다.

${\displaystyle w_{i}=X_{i}^{T}c_{i}}$

${\displaystyle {여기}_{}}$서 c i ${\displaystyle =}$( c${\displaystyle {}_{}{}_{}{i}_{}}$ ) ${\displaystyle {1\mathrm{}}_{}}$, ( ${\displaystyle c_{}{}_{}}$i )${\displaystyle {}_{}{2\mathrm{}}_{}}$,${\displaystyle }$.${\displaystyle }$, ( ${\displaystyle {}_{}{}_{}{i}_{}}$ ) ${\displaystyle i_{}{\mathbb{}}^{}}$ R$$ \ $displaystyle$$c$_ { i }$=$ ( ( $c _$ {$i$ )$_$ { } _ {2} , ( c$$${\displaystyle {\_}_{}}$ {$i$ )$_$ { $i$} \ $in{\displaystyle {}_{}}$$$\ $mathbb$$R ^$ { $i$$$} } 。

${\displaystyle c_{0}=0}$

${\displaystyle (}$ ${\displaystyle c_{}{}_{}}$i ) ${\displaystyle j_{}{}_{}=}$ ( ${\displaystyle c_{}}$i -${\displaystyle {}_{}{}_{}{1}_{}}$ )${\displaystyle j}$ , ${\displaystyle \mathrm{j}}$ $=$ ${\displaystyle 1}$, 2,${\displaystyle }$.${\displaystyle }$,${\displaystyle i}$ - ${\displaystyle 1}$( c $_${ $i } _$ { $display$style ( c$_$ { i - 1 ) $_${ $j$} _ {$j$ , j = 1, 2, $...$ i -$1$ } 、

${\displaystyle (c_{i})_{i}=\big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\nagle x_{j},x_{i}\rangle {Big}}}$

${\displaystyle {}^{}}$서${\displaystyle {}_{}}$ x${\displaystyle {}_{}{j}_{}}$ , ${\displaystyle x_{}}$ i ${\$ { $displaystyle$\ $langle x$_ {$j$ , $x$_ { $i$} \ $rangle$}는$$ R$$d \ $displaystyle$\$mathbb${ $R }$ ^ { $d$}의 표준 커널이며 프레딕터는 다음과 같습니다.

${\displaystyle f_{}}$i (${\displaystyle x}$ ) ${\displaystyle =}$ ${\displaystyle ⟨}$ ${\displaystyle w_{}}$i -${\displaystyle {}_{}{1}_{}}$ , $x$ ${\displaystyle ⟩⟩}$ ${\displaystyle \underset{}{\overset{}{=}}}$ 1${\displaystyle \underset{}{\overset{}{}}}$ -${\displaystyle \underset{}{\overset{}{}}\underset{}{\overset{}{1}}}$ ( ${\displaystyle {}_i}$ -${\displaystyle {}_{}{}_{}{1}_{}}$ ) ${\displaystyle j_{}{}_{}{}_{}}$ \ $display f _${ $i$} ( x ) = \ $sum$ _ { $j = 1$^{ $i }$ ( c$_ i$ -$1$ )$x$

대신 일반 $커널{\displaystyle }$K(\$style$ K$)$가 도입되어 프레딕터가

${\displaystyle f_{i}(x)=\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)}$

그리고 같은 증거는 또한 최소 제곱 손실을 최소화하는 예측 변수가 위의 재귀로 변경됨으로써 얻어진다는 것을 보여줄 것이다.

${\displaystyle (c_{i})_{i}=\big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x_{i}}{\Big}}}}$

위의 식에서는 $\$ 업데이트를 $위해{\displaystyle {}_{}}$ 모든 데이터를 저장해야 합니다.$(\displaystyle$ n$)$ -번째$$ 데이터 포인트의 평가 시 재귀의 총 복잡도는 O${\displaystyle ({n\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle \mathrm{dk}}$ $)(n displaystyle$ O$(n^{2} dk$입니다.$여기$서$$k(\$displaystyle$ k$)$는 단일 포인트 ^[1]쌍으로 커널을 평가하는 비용입니다.따라서 커널의 사용은 $파라미터{\displaystyle {}_{}}$ ${\displaystyle {ci}_{}}$의 공간에서 재귀(recursive)를 수행하는 대신 ${\displaystyle {}^{}}$$$K로 표현되는 유한 치수 파라미터 $공간$ ${i}\in \mathbb {R}$ ^{d$}$에서 $kernel{\displaystyle }$ K {\$displaystyle$ K$}$로 이동하는 것을 가능하게 했다.$§$ $Ri \displaystyle$ \$textstyle$c_{$i}\$in $\mathbb {R$i}. 치수는 트레이닝 데이터 세트의 크기와 동일합니다${\displaystyle .}$일반적으로 이것은 대표자 ^[1]정리의 결과이다.

온라인 볼록 최적화

온라인 볼록 최적화(OCO)는 효율적인 알고리즘을 가능하게 하기 위해 볼록 최적화를 활용하는 의사 결정을 위한 일반적인 프레임워크입니다.이 프레임워크는 다음과 같이 반복 게임을 하는 것이다.

t ${\displaystyle =1}$,${\displaystyle 2}$, ${\displaystyle ...,}$ ${\displaystyle T}${$displaystyle$ t$=1$, $2, ...T}$의 경우

• 학습자가 $입력{\displaystyle {}_{}}$ ${\displaystyle x_{}}$ t$(\$를 수신합니다.
• 학습자가 고정 볼록 $세트{\displaystyle }$ S$(\displaystyle$ S$)$에서 $\$displaystyle $w_{t$}를$$ $출력$합니다.
• 자연은 볼록 손실 $함수{\displaystyle {}_{}}$ ${\displaystyle v_{}}$ t${\displaystyle {}_{}}$: ${\displaystyle S}$ ${\displaystyle \to }$ ${\displaystyle R\mathbb{}}$ ${\$$S\rightarrow \mathbb {R}$$}$ 。
• 학습자가 $손실{\displaystyle {}_{}}$ v${\displaystyle {}_{}{}_{}}$ ( ${\displaystyle w_{}}$t$$) { $displaystyle v$_ { $t$} ( $w$_ { $t$} )를$$ 경험하고 모델을 업데이트합니다.

$목표$는 후회, 즉 누적 손실과 ${\displaystyle \mathrm{최선}}$의 $고정점$ 손실의$$ 차이를 최소화하는 $것이다.$예를 들어 온라인 최소 제곱 선형 회귀 분석의 경우를 고려해 보십시오.여기서 무게 벡터는 볼록 $집합{\displaystyle {}_{}}$ S ${\displaystyle =}$ ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$\ $displaystyle$ S = \ $mathbb${ $R$} ^ { $d$} 、 nature ${\displaystyle =}$ (${\displaystyle w}$w , ${\displaystyle {}_{}}$ ${\displaystyle t_{}{}_{}}$ - ${\displaystyle {}_{}{}^{t\mathrm{}}}$ ) ${\displaystyle 2}$ ($$\ $displaystyle$ v$_$ { $t$} = ( \ $displaystyle w$ , $x t$} \ $rang$} )^{ $rang$ { t } )로부터 반환한다.${\displaystyle v_{}}$ t$${ $display style$ v _ { $t$} 。

그러나 일부 온라인 예측 문제는 OCO 프레임워크에 맞지 않는다.예를 들어 온라인 분류에서 예측 영역과 손실 함수는 볼록하지 않다.그러한 시나리오에서는 볼록화를 위한 두 가지 간단한 기법, 즉 무작위화와 대리 손실^{[citation needed]} 함수를 사용한다.

간단한 온라인 볼록 최적화 알고리즘은 다음과 같다.

리더에 따르기(FTL)

가장 간단한 학습 규칙은 (현재 단계에서) 과거 모든 라운드에서 손실이 가장 적은 가설을 선택하는 것입니다.이 알고리즘은 Follow the leader라고 불리며 다음과 같이 간단히 $라운드{\displaystyle }$ t$\displaystyle$t로 표시됩니다$$.

${\displaystyle w_{t}=\operatorname {display,min}_{w\in S}\sum _{i=1}^{t-1}v_{i}(w)}$

따라서 이 방법은 탐욕 알고리즘으로 간주될 수 있습니다.온라인 2차 최적화(손실함수가 ${\displaystyle v_{}}$t (${\displaystyle w}$ ) ${\displaystyle =w}$ - ${\displaystyle x_{}}$ ${\displaystyle t{}_{}{}_{\mathrm{}}^{}}$ 2$$ 2 ( w ) =$$w - x $_$ { $t$} _ { {$2$t } _ { 2$$})의 경우, 로그${\displaystyle \log }$ (${\displaystyle }$T$)$ \ $displaystyle \log$ ( T$$)$$log imp imp imp imp for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for for that that that that that that that that that that that that that that for that that that that that that for for for for for for for log log for for for for that that that that that온라인 선형 최적화와 같은 모델 제품군입니다.그러기 위해서는 정규화를 추가하여 FTL을 변경합니다.

정규화된 리더(FTRL)를 따릅니다.

이는 FTL 솔루션을 안정화하고 더 나은 후회 경계를 얻기 위해 사용되는 FTL의 자연스러운 수정입니다.${\displaystyle \mathrm{정규화}}$ $함수{\displaystyle }$R : S ${\displaystyle \to }$ {\$displaystyle$ R$:$$S\rightarrow \mathbb {R}$을$($를) 선택하고 다음과 같이 라운드 t에서 학습을 수행합니다.

${\displaystyle w_{t}=\operatorname {display,min}_{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)}$

특별한 예로서 온라인 선형 최적화의 예를 들어, 자연이 v${\displaystyle {}_{}t}$ (${\displaystyle }$w ) ${\displaystyle =}$ = ${\displaystyle w}$, ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$ { $style v$_ { $t$} = \ $displayle$w , z$_$ { $t$} \ $rangle$ $\}$$형식$의 손실 함수를 반송한다고 $가정$합니다.또, S ${\displaystyle =}$ ${\displaystyle {}^{}}$ d$${ $display style$ S = \ $mathbbb$} { d$}$ { display { d }$$} { display st} 。${\displaystyle w{}_{\mathrm{}}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$({ $displaystyle R$ (w ) =$flac${ $1$} {$2$ \ eta }} $w$_ { $2$}$$$2$ { { 2 } chosen chosen chosen chosen $。$그러면 후회를 최소화하는 반복이 되는 것을 알 수 있습니다.

${\displaystyle w_{t+1}=-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}$

이 값은 ${\displaystyle {w\mathrm{t}}_{}}$ + ${\displaystyle {}_{}}$ $=$ ${\displaystyle w_{}}$t - ${\displaystyle {}_{}\mathrm{}{}_{}{}_{}}$t (${\displaystyle {}_{}{w}_{}}$ t$$)\$display w_{t+$1}=$w_{t}-\$eta \$display la$v_${t}(w_${t$\})$로 고쳐 쓸 수 있습니다.이것은 온라인 구배 강하와 매우 유사합니다.

대신 S가 R $\$의 볼록 부분 공간인 경우 S를 투영해야 하므로 업데이트 규칙이 변경됩니다.

${\displaystyle w_{t+1}=\Pi _{S}(-\eta \sum _{i=1}^{t}z_{i})=\Pi _{S}(\eta \theta _{t+1})}$

이 알고리즘은 ${\displaystyle {벡터\theta }_{}}$ t${\displaystyle {}_{}}$+ $(\$ _${t+1})$이 구배를 누적하기$$ 때문에 느린 투영이라고 불립니다.네스테로프의 이중 평균 알고리즘이라고도 합니다.선형 손실 함수 및 2차 정규화의 이 시나리오에서는 후회는 O${\displaystyle }$(${\displaystyle T\sqrt{}}$)(\$displaystyle$ O$({\sqrt {T$에 의해 $제한$되며, 따라서 평균 후회는 원하는 대로 0이 됩니다.

온라인 경사하강(OSD)

상기 선형 손실 $함수{\displaystyle {}_{}}$ v${\displaystyle {}_{}t}$ (${\displaystyle }$w ) ${\displaystyle =}$ ${\displaystyle ⟨w}$ , ${\displaystyle {}_{}}$ ${\displaystyle t_{}}$ \ $displaystyle v$_ { $t$} = \ $sclle$w , z$_$ { $t$$$$}$ $。$알고리즘을 볼록 손실 함수로 일반화하려면 , ($w$$$) \ $display$ ${\displaystyle {style}_{}}$$\ class v_t$( $w)$ { t } $\}{\displaystyle \mathrm{}}$ $。$${\displaystyle w_{}}$ ${\displaystyle t_{}}$$${ $displaystyle w$_ { $t$} $w{\displaystyle {}_{}}$ wv t { $t$}에$$ $대한{\displaystyle {}_{}}$ 근사값으로, 온라인 준구배 강하 알고리즘으로 이어집니다.

$파라미터{\displaystyle }$ ${\displaystyle ,,}$ ${\displaystyle {w\mathrm{}}_{}}$ 1 ${\displaystyle {}_{}}$ { $displaystyle \eta$,$w$_ {1} =$0$} 을 초기화합니다.

t ${\displaystyle =1}$,${\displaystyle 2}$, ${\displaystyle ...,}$ ${\displaystyle T}${$displaystyle$ t$=1$, $2, ...T}$의 경우

• $\$를 사용하여 $예측$하고 자연에서 $\$를 수신합니다.
• ${\displaystyle z_{}}$ t ${\displaystyle {}_{}\mathrm{}{tv}_{}}$t ( ${\displaystyle {}_{}{t}_{}}$ )$$\ $displaystyle z_{t}$ \ $in$\ $partial v_{t}(w_{t})$를 $선택$합니다.
• S ${\displaystyle =}$ ${\displaystyle {}^{}}$ d$$\$style$ S = \$mathbb {R}$^{$d$$\}$인 $경우{\displaystyle }$ ${\displaystyle w_{}{t}_{}}$ + ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ -${\displaystyle {}_{}{z}_{}}$ z$$t { $display$ w $_${ $t$+ 1 } $= w$ _ { t } - \$eta$ z $_${ t } 로 $업데이트$합니다.
• S${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ d$$\ $style$ S \ $subset$\$mathbb { R$ } ^{$d$인 $경우{\displaystyle }$, 누적 그라데이션이$$S { $display style$ S$$}에 투영됩니다. $즉{\displaystyle {}_{,}}$ ${\displaystyle w_{}}$ + ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\pi }_{}}$ S${\displaystyle {}_{}}$( ${\displaystyle t}$ ${\displaystyle {\theta }_{}}$ t +${\displaystyle {}_{}{1}_{}}$ ${\displaystyle ),{}_{}{}_{}}$ + ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ t${\displaystyle {}_{}}$+ ${\displaystyle t_{}}$ + ${\displaystyle {}_{}}$ + ${\displaystyle t_{}}$\ t \ t { \ $display w_{$t + t + t + t1 } } } } $=$$Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}$

OSD 알고리즘을 사용하여 분류용 온라인 버전의 SVM에 대한 O${\displaystyle }$($T$ ) ( \ $sqrt${$T }$ ) 후회$$ 경계를 $도출$할 수 있습니다. 여기서 힌지 ${\displaystyle {}_{}}$ v${\displaystyle {}_{}{t}_{}}$ (${\displaystyle w}$ ) ${\displaystyle =max}$ {${\displaystyle 0}$ ,${\displaystyle 1}$ - ${\displaystyle y_{}}$ ( ${\displaystyle {}_{}}$ ${\displaystyle \cdot }$ 0 - ${\displaystyle {}_{}{}_{}}$) ${\displaystyle \}}$ $、$ { $display v$ _ { t$$}$$= max { 1 . 0 . stylash }$\}}$

기타 알고리즘

직교적으로 정규화된 FTRL 알고리즘은 위에서 설명한 것처럼 느릿느릿하게 투영된 경사 알고리즘으로 이어집니다.임의의 볼록함수 및 정규자를 위해 위 사항을 사용하려면 온라인 미러 강하를 사용한다.선형 손실 함수에 대해 나중에 최적의 정규화를 도출할 수 있으며, 이는 AdaGrad 알고리즘으로 이어진다.유클리드 정규화의 경우 O${\displaystyle }$( ${\displaystyle T\sqrt{}}$) \ $displaystyle$ O ( { \ $sqrt${ $T$}$$} )의 후회 $한계$를 나타낼 수 있으며, 이는 O${\displaystyle }$( ${\displaystyle \log t}$T$$) \ $displaystyle$ O ( \ $log$ T$$)로 더욱 개선될 수 있다.

계속적인 학습

연속학습이란 연속적인 ^[5]정보 스트림을 처리함으로써 학습된 모델을 지속적으로 개선하는 것을 의미한다.끊임없이 변화하는 현실 세계에서 상호작용하는 소프트웨어 시스템과 자율 에이전트에 지속적인 학습 기능이 필수적입니다.그러나 비정상 데이터 분포에서 점진적으로 사용 가능한 정보를 지속적으로 획득하면 일반적으로 치명적인 망각으로 이어지기 때문에 지속적인 학습은 기계 학습과 뉴럴 네트워크 모델의 과제이다.

온라인 학습의 해석

온라인 학습의 패러다임은 학습 모델의 선택에 따라 해석이 다르며, 각 $모델$은${\displaystyle {}_{}{기능\mathrm{}}_{}}$ ${\displaystyle {f1\mathrm{}}_{}{}_{},}$ $…,$ ${\displaystyle {fn}_{}}$(\$displaystyle f_{1}, f_{2},\ldots,$ f_$\{$$n$}) 순서의 예측 품질에 대해 명확한 의미를 갖는다.이 논의에는 프로토타입 확률적 경사 강하 알고리즘이 사용된다.위에서 설명한 바와 같이 그 재귀는 다음과 같습니다.

$\displaystyle \textstyle w_{t}=w_{t-1}-\displayla V(\langle w_{t1},x_{t}\rangle,y_{t})}$

첫 번째 해석은 확률적 경사 강하법을 ^[6]위에서 정의한 기대 $위험{\displaystyle }$I [ $]$ \ $display style$I [ $w$]의$$ 최소화 문제에 적용하는 것으로 간주한다.실제로 무한 데이터 스트림의 경우${\displaystyle }$(${\displaystyle {x\mathrm{}}_{}{}_{}}$, y${\displaystyle {}_{}{1\mathrm{}}_{}}$ ${\displaystyle ),}$ (${\displaystyle {x\mathrm{}}_{}}$2, y${\displaystyle {}_{}{2\mathrm{}}_{}}$ ${\displaystyle ),}$(x ${\displaystyle {}_{}}$ $),$ ($x_{1}), (x_{2}, y_${2}), \ldots $}$는 (x${\displaystyle }$, ${\displaystyle y}$ )의 $분포{\displaystyle }$p$(x$, y )에서 도출된 것으로 $가정$됩니다$.$$위$의 반복에서$$cdot )는$$ 예상 $위험{\displaystyle }$I [ $w$ \ $displaystyle$I [ $w$] \ $displaystyle$ I$$[ $w ]$} $} method$ } method } method } } } } } } } of of of of of of of of$$ of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of of${\displaystyle w^{}}$ ${\$ { \ $display style$ w^ { \ $ast }$ is$$${\displaystyle }$、 I [ $]{$ $display style$I [ w$]$^[7]의 최소값입니다.이 해석은 또한 유한 훈련 세트의 경우에도 유효하다. 데이터를 통과하는 다중 경로로 구배는 더 이상 독립적이지 않지만 특별한 경우에는 여전히 복잡성 결과를 얻을 수 있다.

두 번째 해석은 유한 훈련 세트의 경우에 적용되며 SGD 알고리즘을 증분 경사 강하 방법의 ^[3]인스턴스로 간주한다.이 경우 대신 경험적 위험을 살펴봅니다.

${\displaystyle I_{n}[w]=sum _{i=1}^{n}V(\langle w,x_{i}\rangle,y_{i}\.}$

증분 경사 강하 반복에서 V${\displaystyle }$( ${\displaystyle ,}$ , ${\displaystyle )}$) { $displaystyle$ V ( \$cdot$, \$cdot$ )$$}의 경사도 역시 I${\displaystyle {}_{}{n}_{}}$ [ $]$ \ $displaystyle I_{n}[w]$ $\}$의 확률적 추정치이므로, 이 해석은 확률적 경사 강하법과도 관련이 있으나 경험적 위험을 최소화하기 위해 적용된다.예상되는 리스크에 대응합니다.이 해석은 예상 위험이 아닌 경험적 위험과 관련이 있으므로 데이터를 통과하는 다중 통과가 쉽게 허용되며 실제로 $편차$에 대한 경계가 엄격해집니다${\displaystyle {}_{}}$ $여기$서 ${$$n}$ - ${\displaystyle {}_{}^{}}${n$}$ [$w_{t}$ - $I_{n}$ - {$n$} - I_{n} $-$ w_style w_n$}$ ($여기$서$$w_n$)$는 I n${\displaystyle {}_{}}$[ $]{$ $displaystyle I_{n}[w$의 최소값입니다.

실장

• 서약팔 와빗:오픈 소스 고속 코어 외 온라인 학습 시스템. 많은 기계 학습 감소, 중요도 가중치 부여 및 다양한 손실 기능 및 최적화 알고리즘의 선택을 지원하는 것으로 주목됩니다.해싱 트릭을 사용하여 훈련 데이터의 양에 관계없이 피쳐 세트의 크기를 제한합니다.
• skikit-learn: 알고리즘의 핵심 외 구현을 제공합니다.
  • 분류:퍼셉트론, SGD 분류기, Naigive Bayes 분류기.
  • 회귀: SGD Regressor, Passive Aggressive Regressor.
  • 클러스터링:미니 배치 K-평균
  • 기능 추출:미니 배치 사전 학습, 증분 PCA.

「 」를 참조해 주세요.

학습 패러다임

• 증분 학습
• 게으른 학습
• 오프라인 학습, 반대 모델
• 강화 학습
• 멀티 암 도적
• 지도 학습

일반적인 알고리즘

• 온라인 알고리즘
• 온라인 최적화
• 스트리밍 알고리즘
• 확률적 경사 강하

학습 모델

• 적응 공명 이론
• 계층형 시간 메모리
• k-param 네이버알고리즘
• 학습 벡터 양자화
• 퍼셉트론

레퍼런스

외부 링크

• http://onlineprediction.net/, 온라인 예측용 Wiki.
• 6.883: 머신 러닝의 온라인 방법:이론과 응용 프로그램알렉산더 라클린.MIT