온라인 기계 학습

컴퓨터 과학에서 온라인 기계 학습(Online machine learning)은 데이터가 순차적으로 제공되고 각 단계에서 미래 데이터에 대한 최적의 예측기를 업데이트하는 기계 학습 방법으로, 전체 트레이닝 셋에서 한 번에 학습하여 최적의 예측기를 생성하는 배치 학습 기술과는 대조된다. 온라인 학습은 전체 데이터셋을 통해 훈련하는 것이 계산적으로 불가능하여 아웃 오브 코어(out-of-core) 알고리즘이 필요한 기계 학습 영역에서 일반적으로 사용되는 기술이다. 또한 알고리즘이 데이터의 새로운 패턴에 동적으로 적응해야 하는 상황이나, 데이터 자체가 시간의 함수로 생성되는 경우(예: 금융 국제 시장의 가격 예측)에도 사용된다. 온라인 학습 알고리즘은 치명적 망각에 취약할 수 있으며, 이는 증분 학습 접근 방식으로 해결될 수 있는 문제이다.

온라인 기계 학습 알고리즘은 광고 수익 극대화를 위한 후원 검색, 포트폴리오 최적화, 최단 경로 예측 (예: 지도 애플리케이션의 도로 교통과 같은 확률적 가중치 사용), 스팸 필터링, 실시간 사기 탐지, 전자 상거래를 위한 가변적 가격 책정 등 다양한 분야에 적용된다. 초기 훈련 후 지속적이고 실시간 적응을 가능하게 하기 위해 LLM(Large Language Model)에 온라인 학습 패러다임을 사용하는 것에 대한 관심도 커지고 있다.^[1]

서론

지도 학습 설정에서, 입력 공간 $X$ 와 출력 공간 $Y$ 에 대한 함수 $f:X\to Y$ 를 학습하는 것이 목표이며, 이 함수는 $X\times Y$ 상의 결합분포 $p(x,y)$ 에서 추출된 인스턴스에 대해 잘 예측해야 한다. 실제로는 학습자는 인스턴스에 대한 실제 분포 $p(x,y)$ 를 알지 못한다. 대신, 학습자는 일반적으로 $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ 과 같은 예제들의 트레이닝 셋에 접근할 수 있다. 이 설정에서, 손실 함수는 $V:Y\times Y\to \mathbb {R}$ 로 주어지며, $V(f(x),y)$ 는 예측 값 $f(x)$ 와 실제 값 $y$ 사이의 차이를 측정한다. 이상적인 목표는 함수 공간인 가설 공간 ${\mathcal {H}}$ 에서 함수 $f\in {\mathcal {H}}$ 를 선택하여 총 손실의 어떤 개념을 최소화하는 것이다. 모델 유형(통계적 또는 적대적)에 따라 다른 손실 개념을 고안할 수 있으며, 이는 다른 학습 알고리즘으로 이어진다.

온라인 학습의 통계적 관점

통계적 학습 모델에서 훈련 표본 $(x_{i},y_{i})$ 는 실제 분포 $p(x,y)$ 에서 추출되었다고 가정하며, 목표는 기대 "위험"을 최소화하는 것이다. $I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .$ 이러한 상황에서 일반적인 패러다임은 경험적 위험 최소화 또는 정규화된 경험적 위험 최소화(티호노프 정칙화를 통해)를 통해 함수 ${\hat {f}}$ 를 추정하는 것이다. 여기서 손실 함수의 선택은 정규화된 최소제곱법 및 서포트 벡터 머신과 같은 여러 잘 알려진 학습 알고리즘을 발생시킨다. 이 범주에서 순수한 온라인 모델은 새로운 입력 $(x_{t+1},y_{t+1})$ , 현재 최적의 예측기 $f_{t}$ 및 추가로 저장된 정보(일반적으로 훈련 데이터 크기와 무관한 저장 요구 사항을 가질 것으로 예상됨)에만 기반하여 학습한다. 비선형 커널 메소드와 같은 많은 공식에서는 진정한 온라인 학습이 불가능하지만, $f_{t+1}$ 이 $f_{t}$ 와 모든 이전 데이터 포인트 $(x_{1},y_{1}),\ldots ,(x_{t},y_{t})$ 에 의존하도록 허용되는 재귀 알고리즘을 사용한 하이브리드 온라인 학습 형태를 사용할 수 있다. 이 경우, 모든 이전 데이터 포인트를 저장해야 하므로 공간 요구 사항이 더 이상 일정하다고 보장되지 않지만, 배치 학습 기술에 비해 새로운 데이터 포인트가 추가될 때 솔루션을 계산하는 데 시간이 덜 걸릴 수 있다.

위의 문제를 극복하기 위한 일반적인 전략은 미니 배치(mini-batch)를 사용하여 학습하는 것으로, 한 번에 $b\geq 1$ 개의 데이터 포인트의 작은 배치를 처리하며, 이는 총 훈련 포인트 수보다 훨씬 작은 $b$ 에 대한 유사-온라인 학습으로 간주될 수 있다. 미니 배치 기술은 훈련 데이터를 반복적으로 통과하여 기계 학습 알고리즘의 최적화된 out-of-core 버전을 얻는 데 사용된다. 예를 들어, 확률적 경사 하강법이 있다. 역전파와 결합될 때, 이는 현재 인공 신경망 훈련을 위한 사실상의 훈련 방법이다.

예시: 선형 최소 제곱

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

배치 학습

$f$ 가 학습될 선형 함수인 지도 학습 설정을 고려한다. $f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}$ 여기서 $x_{j}\in \mathbb {R} ^{d}$ 는 입력(데이터 포인트) 벡터이고 $w\in \mathbb {R} ^{d}$ 는 선형 필터 벡터이다. 목표는 필터 벡터 $w$ 를 계산하는 것이다. 이를 위해, 제곱 손실 함수 $V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}$ 를 사용하여 경험적 손실을 최소화하는 벡터 $w$ 를 계산한다. $I_{n}[w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle ,y_{j})=\sum _{j=1}^{n}(x_{j}^{\mathsf {T}}w-y_{j})^{2}$ 여기서 $y_{j}\in \mathbb {R} .$

$X$ 를 $i\times d$ 데이터 행렬이라고 하고, $y\in \mathbb {R} ^{i}$ 를 첫 번째 $i$ 개의 데이터 포인트가 도착한 후의 목표 값의 열 벡터라고 하자. 공분산 행렬 $\Sigma _{i}=X^{\mathsf {T}}X$ 가 역행렬을 가진다고 가정하면 (그렇지 않으면 티호노프 정칙화를 사용하여 유사하게 진행하는 것이 선호됨), 선형 최소 제곱 문제에 대한 최적의 해 $f^{*}(x)=\langle w^{*},x\rangle$ 는 다음과 같이 주어진다. $w^{*}=(X^{\mathsf {T}}X)^{-1}X^{\mathsf {T}}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}.$

이제 공분산 행렬 $\Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{\mathsf {T}}$ 를 계산하는 데 $O(id^{2})$ 시간이 걸리고, $d\times d$ 행렬을 역행렬하는 데 $O(d^{3})$ 시간이 걸리며, 나머지 곱셈은 $O(d^{2})$ 시간이 걸려 총 시간은 $O(id^{2}+d^{3})$ 이 된다. 데이터셋에 총 $n$ 개의 포인트가 있을 때, 모든 데이터 포인트 $i=1,\ldots ,n$ 가 도착한 후 해를 다시 계산하는 순진한 접근 방식은 총 복잡도가 $O(n^{2}d^{2}+nd^{3})$ 이다. $\Sigma _{i}$ 행렬을 저장하면 각 단계에서 업데이트하는 데 $x_{i+1}x_{i+1}^{\mathsf {T}}$ 를 추가하는 데만 $O(d^{2})$ 시간이 걸려 총 시간이 $O(nd^{2}+nd^{3})=O(nd^{3})$ 으로 줄어들지만, $\Sigma _{i}$ 를 저장하는 데 $O(d^{2})$ 의 추가 저장 공간이 필요하다.^[2]

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

재귀적 최소 제곱(RLS) 알고리즘은 최소 제곱 문제에 대한 온라인 접근 방식을 고려한다. $\textstyle w_{0}=0\in \mathbb {R} ^{d}$ 및 $\textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}$ 로 초기화하면 이전 섹션에서 주어진 선형 최소 제곱 문제의 해가 다음 반복으로 계산될 수 있음을 보여줄 수 있다. $\Gamma _{i}=\Gamma _{i-1}-{\frac {\Gamma _{i-1}x_{i}x_{i}^{\mathsf {T}}\Gamma _{i-1}}{1+x_{i}^{\mathsf {T}}\Gamma _{i-1}x_{i}}}$ $w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)$ 위 반복 알고리즘은 $i$ 에 대한 귀납법으로 증명될 수 있다.^[3] 증명은 또한 $\Gamma _{i}=\Sigma _{i}^{-1}$ 임을 보여준다. RLS를 적응형 필터의 맥락에서도 볼 수 있다(RLS 참조).

이 알고리즘의 $n$ 단계 복잡도는 $O(nd^{2})$ 로, 해당 배치 학습 복잡도보다 한 자릿수 빠르다. 여기에서 각 단계 $i$ 에서의 저장 요구 사항은 행렬 $\Gamma _{i}$ 를 저장하는 것이며, 이는 $O(d^{2})$ 로 일정하다. $\Sigma _{i}$ 가 역행렬을 갖지 않는 경우, 문제 손실 함수의 정규화된 버전 $\sum _{j=1}^{n}\left(x_{j}^{\mathsf {T}}w-y_{j}\right)^{2}+\lambda \left\|w\right\|_{2}^{2}$ 를 고려한다. 그러면 동일한 알고리즘이 $\Gamma _{0}=(I+\lambda I)^{-1}$ 로 작동하며, 반복은 $\Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}$ 을 제공함이 쉽게 증명된다.^[2]

확률적 경사 하강법

이 식 $w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)$ 이 $w_{i}=w_{i-1}-\gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{i}\rangle ,y_{i})$ 으로 대체되거나 $\Gamma _{i}\in \mathbb {R} ^{d\times d}$ 가 $\gamma _{i}\in \mathbb {R}$ 으로 대체되면, 이는 확률적 경사 하강법 알고리즘이 된다. 이 경우, 이 알고리즘의 $n$ 단계에 대한 복잡도는 $O(nd)$ 로 감소한다. 각 단계 $i$ 에서의 저장 요구 사항은 $O(d)$ 로 일정하다.

그러나 위에서 설명한 대로 기대 위험 최소화 문제를 해결하기 위해 스텝 사이즈 $\gamma _{i}$ 를 신중하게 선택해야 한다. 감소하는 스텝 사이즈 $\gamma _{i}\approx {\frac {1}{\sqrt {i}}},$ 를 선택함으로써 평균 반복 ${\textstyle {\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}}$ 의 수렴을 증명할 수 있다. 이 설정은 최적화에서 잘 알려진 문제인 확률적 최적화의 특수한 경우이다.^[2]

증분 확률적 경사 하강법

실제로는 데이터에 대해 여러 번의 확률적 경사 하강 통과(사이클 또는 에포크라고도 함)를 수행할 수 있다. 이렇게 얻은 알고리즘을 증분 경사 하강법이라고 하며 다음과 같은 반복에 해당한다. $w_{i}=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})$ 확률적 경사 하강법과의 주요 차이점은 여기서는 $i$ 번째 단계에서 어떤 훈련 포인트를 방문할지 결정하기 위해 시퀀스 $t_{i}$ 가 선택된다는 것이다. 이러한 시퀀스는 확률적이거나 결정적일 수 있다. 그러면 반복 횟수는 포인트 수와 분리된다(각 포인트는 한 번 이상 고려될 수 있다). 증분 경사 하강법은 경험적 위험을 최소화하는 값을 제공하는 것으로 나타날 수 있다.^[4] 증분 기법은 매우 큰 데이터셋에 해당하는 경험적 오류와 같이 많은 항의 합으로 구성된 목적 함수를 고려할 때 유리할 수 있다.^[2]

커널 메소드

커널은 위의 알고리즘을 비모수 모델(또는 매개변수가 무한 차원 공간을 형성하는 모델)로 확장하는 데 사용될 수 있다. 해당 절차는 더 이상 진정한 온라인이 아니며 대신 모든 데이터 포인트를 저장해야 하지만, 무차별 대입 방식보다 여전히 빠르다. 이 논의는 제곱 손실의 경우에만 한정되지만, 어떤 볼록 손실로도 확장될 수 있다. ^[2]에 의해 쉽게 귀납적으로 증명될 수 있듯이, $X_{i}$ 가 데이터 행렬이고 $w_{i}$ 가 SGD 알고리즘의 $i$ 단계 후 출력이라면, $w_{i}=X_{i}^{\mathsf {T}}c_{i}$ 여기서 $c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}$ 이고 시퀀스 $c_{i}$ 는 다음 재귀를 만족한다. $c_{0}=0$ $(c_{i})_{j}=(c_{i-1})_{j},j=1,2,...,i-1$ 이고 $(c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x_{i}\rangle {\Big )}$ 여기서 $\langle x_{j},x_{i}\rangle$ 는 $\mathbb {R} ^{d}$ 에 대한 표준 커널이며, 예측기는 다음 형태를 갖는다. $f_{i}(x)=\langle w_{i-1},x\rangle =\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle .$

이제 일반 커널 $K$ 가 도입되고 예측기가 다음과 같다고 하면, $f_{i}(x)=\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)$ 동일한 증명은 최소 제곱 손실을 최소화하는 예측기가 위의 재귀를 다음과 같이 변경함으로써 얻어짐을 보여준다. $(c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x_{i}){\Big )}$ 위의 표현식은 $c_{i}$ 를 업데이트하기 위해 모든 데이터를 저장해야 한다. $n$ 번째 데이터 포인트에 대해 재귀를 평가할 때 총 시간 복잡도는 $O(n^{2}dk)$ 이며, 여기서 $k$ 는 단일 쌍의 포인트에 대한 커널을 평가하는 비용이다.^[2] 따라서 커널을 사용하면 유한 차원 매개변수 공간 $\textstyle w_{i}\in \mathbb {R} ^{d}$ 에서 매개변수 공간 $\textstyle c_{i}\in \mathbb {R} ^{i}$ 에서 재귀를 수행함으로써 커널 $K$ 로 표현되는 무한 차원 특징으로 이동할 수 있게 되었으며, 이 매개변수 공간의 차원은 훈련 데이터셋의 크기와 같다. 일반적으로 이는 표현자 정리의 결과이다.^[2]

온라인 볼록 최적화

온라인 볼록 최적화(OCO) ^[5]는 효율적인 알고리즘을 가능하게 하는 볼록 최적화를 활용하는 일반적인 의사 결정 프레임워크이다. 이 프레임워크는 다음과 같은 반복 게임 플레이 방식이다.

$t=1,2,...,T$ 에 대해

학습자는 입력 $x_{t}$ 를 받는다.
학습자는 고정된 볼록 집합 $S$ 에서 $w_{t}$ 를 출력한다.
자연은 볼록 손실 함수 $v_{t}:S\rightarrow \mathbb {R}$ 를 반환한다.
학습자는 손실 $v_{t}(w_{t})$ 를 겪고 모델을 업데이트한다.

목표는 후회, 즉 누적 손실과 나중에 가장 좋은 고정점 $u\in S$ 의 손실 간의 차이를 최소화하는 것이다. 예를 들어, 온라인 최소 제곱 선형 회귀의 경우를 고려하자. 여기서 가중치 벡터는 볼록 집합 $S=\mathbb {R} ^{d}$ 에서 오고, 자연은 볼록 손실 함수 $v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}$ 를 반환한다. 여기서 $y_{t}$ 는 $v_{t}$ 와 함께 암시적으로 보내진다.

그러나 일부 온라인 예측 문제는 OCO 프레임워크에 적합하지 않을 수 있다. 예를 들어, 온라인 분류에서는 예측 도메인과 손실 함수가 볼록하지 않다. 이러한 시나리오에서는 볼록화를 위한 두 가지 간단한 기술, 즉 무작위화 및 대리 손실 함수가 사용된다.

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

선행자 따르기 (FTL)

가장 간단한 학습 규칙은 (현재 단계에서) 과거의 모든 라운드에 걸쳐 손실이 가장 적었던 가설을 선택하는 것이다. 이 알고리즘을 "선행자 따르기"(Follow the leader)라고 하며, 라운드 $t$ 는 단순히 다음과 같이 주어진다. $w_{t}=\mathop {\operatorname {arg\,min} } _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)$ 이 방법은 탐욕 알고리즘으로 볼 수 있다. 온라인 2차 최적화(손실 함수가 $v_{t}(w)=\left\|w-x_{t}\right\|_{2}^{2}$ 인 경우)의 경우, $\log(T)$ 로 증가하는 후회 경계를 보일 수 있다. 그러나 온라인 선형 최적화와 같은 다른 중요한 모델 패밀리의 경우 FTL 알고리즘에 대해 유사한 경계를 얻을 수 없다. 이를 위해 FTL에 정규화를 추가하여 수정한다.

정규화된 선행자 따르기 (FTRL)

이는 FTL 솔루션을 안정화하고 더 나은 후회 경계를 얻는 데 사용되는 FTL의 자연스러운 수정이다. 정규화 함수 $R:S\to \mathbb {R}$ 가 선택되고 라운드 $t$ 에서 다음과 같이 학습이 수행된다. $w_{t}=\mathop {\operatorname {arg\,min} } _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)$ 특별한 예로, 온라인 선형 최적화의 경우, 즉 자연이 $v_{t}(w)=\langle w,z_{t}\rangle$ 형태의 손실 함수를 반환하는 경우를 고려한다. 또한, $S=\mathbb {R} ^{d}$ 라고 하자. 어떤 양수 $\eta$ 에 대해 정규화 함수 ${\textstyle R(w)={\frac {1}{2\eta }}\left\|w\right\|_{2}^{2}}$ 가 선택되었다고 가정하자. 그러면 후회를 최소화하는 반복이 다음과 같이 됨을 보일 수 있다. $w_{t+1}=-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}$ 이는 $w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})$ 로 다시 작성될 수 있으며, 이는 온라인 경사 하강법과 정확히 일치한다.

만약 $S$ 가 $\mathbb {R} ^{d}$ 의 일부 볼록 부분 공간이라면, $S$ 는 그 위에 투영되어야 하며, 이는 수정된 업데이트 규칙을 이끌어낸다. $w_{t+1}=\Pi _{S}(-\eta \sum _{i=1}^{t}z_{i})=\Pi _{S}(\eta \theta _{t+1})$ 이 알고리즘은 벡터 $\theta _{t+1}$ 이 기울기를 축적하기 때문에 지연 투영(lazy projection)으로 알려져 있다. 또한 네스테로프의 이중 평균화 알고리즘으로도 알려져 있다. 선형 손실 함수와 이차 정규화의 이 시나리오에서, 후회는 $O({\sqrt {T}})$ 로 경계지어지며, 따라서 평균 후회는 원하는 대로 $0$ 으로 수렴한다.

온라인 부분 경사 하강법 (OSD)

위에서 선형 손실 함수 $v_{t}(w)=\langle w,z_{t}\rangle$ 에 대한 후회 경계가 증명되었다. 알고리즘을 임의의 볼록 손실 함수로 일반화하기 위해, $w_{t}$ 근처에서 $v_{t}$ 의 선형 근사로 $v_{t}$ 의 subgradient $\partial v_{t}(w_{t})$ 를 사용하여 온라인 부분 경사 하강법 알고리즘을 얻는다.

매개변수 $\eta ,w_{1}=0$ 초기화

$t=1,2,...,T$ 에 대해

$w_{t}$ 를 사용하여 예측하고, 자연으로부터 $f_{t}$ 를 받는다.
$z_{t}\in \partial v_{t}(w_{t})$ 를 선택한다.
$S=\mathbb {R} ^{d}$ 인 경우, $w_{t+1}=w_{t}-\eta z_{t}$ 로 업데이트한다.
$S\subset \mathbb {R} ^{d}$ 인 경우, 누적 기울기를 $S$ 에 투영한다. 즉, $w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}$

OSD 알고리즘을 사용하여 분류를 위한 온라인 버전의 SVM에 대해 $O({\sqrt {T}})$ 후회 경계를 도출할 수 있으며, 이는 힌지 손실 $v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}$ 을 사용한다.

기타 알고리즘

Quadratic하게 정규화된 FTRL 알고리즘은 위에서 설명한 지연 투영 경사 알고리즘으로 이어진다. 임의의 볼록 함수와 정규화자에 대해 위를 사용하려면 온라인 미러 하강법을 사용한다. 선형 손실 함수에 대해 후회 최적의 정규화를 사후에 도출할 수 있으며, 이는 AdaGrad 알고리즘으로 이어진다. 유클리드 정규화의 경우, $O({\sqrt {T}})$ 의 후회 경계를 보일 수 있으며, 이는 강하게 볼록하고 exp-오목 손실 함수에 대해 $O(\log T)$ 로 더욱 개선될 수 있다.

연속 학습

연속 학습은 정보의 지속적인 흐름을 처리하여 학습된 모델을 끊임없이 개선하는 것을 의미한다.^[6] 지속적으로 변화하는 현실 세계에서 상호 작용하는 소프트웨어 시스템 및 자율 에이전트에게는 연속 학습 능력이 필수적이다. 그러나 비정상적인 데이터 분포에서 점진적으로 사용 가능한 정보를 지속적으로 습득하는 것은 일반적으로 치명적 망각으로 이어지기 때문에 기계 학습 및 인공 신경망 모델에게는 연속 학습이 어려운 과제이다.

온라인 학습의 해석

온라인 학습 패러다임은 학습 모델의 선택에 따라 다양한 해석을 가지며, 각각 함수열 $f_{1},f_{2},\ldots ,f_{n}$ 의 예측 품질에 대해 다른 함의를 갖는다. 이 논의에서는 전형적인 확률적 경사 하강법 알고리즘이 사용된다. 위에서 언급했듯이, 그 재귀는 다음과 같이 주어진다. $w_{t}=w_{t-1}-\gamma _{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})$

첫 번째 해석은 위에서 정의된 기대 위험 $I[w]$ 를 최소화하는 문제에 적용되는 확률적 경사 하강법을 고려한다.^[7] 실제로, 무한한 데이터 스트림의 경우, 예제 $(x_{1},y_{1}),(x_{2},y_{2}),\ldots$ 가 분포 $p(x,y)$ 에서 독립적이고 동일하게 분포되었다고 가정하므로, 위 반복에서 $V(\cdot ,\cdot )$ 의 기울기 시퀀스는 기대 위험 $I[w]$ 의 기울기에 대한 확률적 추정치의 독립적이고 동일하게 분포된 표본이며, 따라서 확률적 경사 하강법에 대한 복잡도 결과를 적용하여 $I[w_{t}]-I[w^{\ast }]$ 의 편차를 경계 지을 수 있다. 여기서 $w^{\ast }$ 는 $I[w]$ 의 최소값이다.^[8] 이 해석은 유한 훈련 세트의 경우에도 유효하며; 데이터에 대한 여러 번의 통과로 인해 기울기가 더 이상 독립적이지 않지만, 특정 경우에는 복잡도 결과를 여전히 얻을 수 있다.

두 번째 해석은 유한 훈련 세트의 경우에 적용되며, SGD 알고리즘을 증분 경사 하강법의 한 예로 간주한다.^[4] 이 경우, 대신 경험적 위험을 살펴본다. $I_{n}[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i})\ .$ 증분 경사 하강법 반복에서 $V(\cdot ,\cdot )$ 의 기울기가 $I_{n}[w]$ 의 기울기에 대한 확률적 추정치이므로, 이 해석은 확률적 경사 하강법과도 관련이 있지만, 기대 위험이 아닌 경험적 위험을 최소화하는 데 적용된다. 이 해석은 기대 위험이 아닌 경험적 위험과 관련이 있으므로, 데이터에 대한 여러 번의 통과가 허용되며 실제로 $I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]$ 의 편차에 대한 더 엄격한 경계를 제공한다. 여기서 $w_{n}^{\ast }$ 은 $I_{n}[w]$ 의 최소값이다.

구현

Vowpal Wabbit: 여러 환산, 중요도 가중치, 다양한 손실 함수 및 최적화 알고리즘을 지원하는 것으로 유명한 오픈 소스 고속 아웃오브코어 온라인 학습 시스템이다. 훈련 데이터 양과 무관하게 특징 집합의 크기를 제한하기 위해 해싱 트릭을 사용한다.
Scikit-learn: 다음 알고리즘의 아웃오브코어 구현을 제공한다.
- 분류: 퍼셉트론, SGD 분류기, 나이브 베이즈 분류.
- 회귀: SGD 회귀 분석기, 수동 공격 회귀 분석기.
- 클러스터링: 미니 배치 K-평균.
- 특징 추출: 미니 배치 사전 학습, 증분 PCA.

같이 보기

학습 패러다임

일반 알고리즘

학습 모델

각주

↑ “Online Training of Large Language Models: Learn while Chatting”. 《arxiv.org》. 2025년 10월 3일에 확인함.
↑ ^가 ^나 ^다 ^라 ^마 ^바 ^사 L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015. Chapter 7 - Online Learning
↑ Kushner, Harold J.; Yin, G. George (2003). 《Stochastic Approximation and Recursive Algorithms with Applications》 Seco판. New York: Springer. 8–12쪽. ISBN 978-0-387-21769-7.
↑ ^가 ^나 Bertsekas, D. P. (2011). Incremental gradient, subgradient, and proximal methods for convex optimization: a survey. Optimization for Machine Learning, 85.
↑ Hazan, Elad (2015). 《Introduction to Online Convex Optimization》 (PDF). Foundations and Trends in Optimization.
↑ Parisi, German I.; Kemker, Ronald; Part, Jose L.; Kanan, Christopher; Wermter, Stefan (2019). 《Continual lifelong learning with neural networks: A review》. 《Neural Networks》 113. 54–71쪽. arXiv:1802.07569. doi:10.1016/j.neunet.2019.01.012. ISSN 0893-6080. PMID 30780045.
↑ Bottou, Léon (1998). 〈Online Algorithms and Stochastic Approximations〉. 《Online Learning and Neural Networks》. Cambridge University Press. ISBN 978-0-521-65263-6.
↑ Stochastic Approximation Algorithms and Applications, Harold J. Kushner and G. George Yin, New York: Springer-Verlag, 1997. ISBN 0-387-94916-X; 2nd ed., titled Stochastic Approximation and Recursive Algorithms and Applications, 2003, ISBN 0-387-00894-2.

외부 링크

6.883: Online Methods in Machine Learning: Theory and Applications. Alexander Rakhlin. MIT

[1] “Online Training of Large Language Models: Learn while Chatting”. 《arxiv.org》. 2025년 10월 3일에 확인함.

[lorenzo-2] 가 ^나 ^다 ^라 ^마 ^바 ^사 L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015. Chapter 7 - Online Learning

[3] Kushner, Harold J.; Yin, G. George (2003). 《Stochastic Approximation and Recursive Algorithms with Applications》 Seco판. New York: Springer. 8–12쪽. ISBN 978-0-387-21769-7.

[bertsekas-4] 가 ^나 Bertsekas, D. P. (2011). Incremental gradient, subgradient, and proximal methods for convex optimization: a survey. Optimization for Machine Learning, 85.

[5] Hazan, Elad (2015). 《Introduction to Online Convex Optimization》 (PDF). Foundations and Trends in Optimization.

[6] Parisi, German I.; Kemker, Ronald; Part, Jose L.; Kanan, Christopher; Wermter, Stefan (2019). 《Continual lifelong learning with neural networks: A review》. 《Neural Networks》 113. 54–71쪽. arXiv:1802.07569. doi:10.1016/j.neunet.2019.01.012. ISSN 0893-6080. PMID 30780045.

[7] Bottou, Léon (1998). 〈Online Algorithms and Stochastic Approximations〉. 《Online Learning and Neural Networks》. Cambridge University Press. ISBN 978-0-521-65263-6.

[kushneryin-8] Stochastic Approximation Algorithms and Applications, Harold J. Kushner and G. George Yin, New York: Springer-Verlag, 1997. ISBN 0-387-94916-X; 2nd ed., titled Stochastic Approximation and Recursive Algorithms and Applications, 2003, ISBN 0-387-00894-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]