オンライン学習

機械学習および データマイニング
問題 分類 クラスタリング 回帰 異常検知 相関ルール（英語版） 強化学習 構造化予測（英語版） 特徴量設計（英語版） 表現学習（英語版） オンライン学習 半教師あり学習 教師なし学習 ランキング学習（英語版） 文法獲得（英語版）
教師あり学習（分類 • 回帰） 決定木（英語版） アンサンブル （バギング、ブースティング、 ランダムフォレスト） k-NN 線形回帰 単純ベイズ ニューラルネットワーク ロジスティック回帰 パーセプトロン 関連ベクトルマシン (RVM)（英語版） サポートベクトルマシン (SVM)
クラスタリング BIRCH（英語版） 階層的（英語版） k平均法 期待値最大化法 (EM) DBSCAN OPTICS（英語版） 平均値シフト（英語版）
次元削減 因子分析 CCA ICA LDA（英語版） NMF PCA t-SNE
構造化予測（英語版） グラフィカルモデル ベイジアンネットワーク CRF HMM
異常検知 k-NN 局所外れ値因子法
ニューラルネットワーク オートエンコーダ ディープラーニング DeepDream 多層パーセプトロン RNN LSTM GRU 制約ボルツマンマシン（英語版） SOM CNN
強化学習 TD学習 Q学習 SARSA
理論 偏りと分散のトレードオフ 計算論的学習理論（英語版） 経験損失最小化（英語版） オッカム学習（英語版） PAC学習 統計的学習（英語版） VC理論（英語版）
学会・論文誌等 NIPS（英語版） ICML（英語版） ML（英語版） JMLR（英語版） ArXiv:cs.LG
全般 統計学および機械学習の評価指標
Category:機械学習 Category:データマイニング
表 話 編 歴

オンライン学習（online machine learning）とは、機械学習において、データを逐次的に利用する形で学習を行う手法である。対照的な学習法に、全体の訓練データセットを一括で学習するバッチ学習がある。オンライン学習は、データセット全体での学習が計算上非現実的な場合によく用いられアウトオブコア学習（英語版）が必要とされる。また、アルゴリズムがデータ中の新しいパターンに動的に適応する必要がある場合や、データが時間の関数として生成される状況（例：国際金融市場の価格予測）においても使用される。オンライン学習アルゴリズムは破滅的忘却に陥りやすいが、これは継続学習（英語版）の手法によって対処可能である。

教師あり学習の設定では、関数 ${\displaystyle f:X\to Y}$ を学習することが目的である。ここで、${\displaystyle X}$ は入力の空間、${\displaystyle Y}$ は出力の空間であり、${\displaystyle X\times Y}$ 上の同時確率分布 ${\displaystyle p(x,y)}$ から得られる事例に対して高い予測精度を目指す。実際には、学習者は真の分布 ${\displaystyle p(x,y)}$ を知ることはできず、通常は例 ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ からなる訓練セットへのアクセスのみが与えられる。

この設定においては、損失関数 ${\displaystyle V:Y\times Y\to \mathbb {R} }$ により、予測値 ${\displaystyle f(x)}$ と正解 ${\displaystyle y}$ との違いを測定する。目的は、関数空間 ${\displaystyle {\mathcal {H}}}$（仮説空間）から関数 ${\displaystyle f\in {\mathcal {H}}}$ を選び、ある損失の指標を最小化することである。モデルの種類（統計的モデルまたは敵対的モデル）に応じて、損失の定義が異なり、それにより学習アルゴリズムも異なるものとなる。

統計的学習モデルでは、訓練データ ${\displaystyle (x_{i},y_{i})}$ は真の分布 ${\displaystyle p(x,y)}$ に従って得られたと仮定され、目的は期待損失（リスク）を最小化することである：$${\displaystyle I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .}$$このような状況では、関数 ${\displaystyle {\hat {f}}}$ を経験リスク最小化あるいはティホノフ正則化を用いた正則化付き経験リスク最小化によって推定するのが一般的である。損失関数の選択により、正則化付き最小二乗法やサポートベクターマシン（SVM）などのよく知られたアルゴリズムが得られる。

このカテゴリにおける純粋なオンライン学習モデルでは、新しい入力 ${\displaystyle (x_{t+1},y_{t+1})}$、現在の予測器 ${\displaystyle f_{t}}$、および追加の保存情報（通常は訓練データサイズに依存しない）を用いて学習を行う。たとえば非線形なカーネル法のような場合、真の意味でのオンライン学習は実現困難であるが、${\displaystyle f_{t+1}}$ を ${\displaystyle f_{t}}$ および過去のすべてのデータ ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{t},y_{t})}$ に基づいて更新するハイブリッドなオンライン学習が可能である。この場合、必要な記憶容量は定数ではなくなるが、新しいデータが追加される際の計算時間はバッチ学習に比べて短くなる可能性がある。

このような問題への対処法として、${\displaystyle b\geq 1}$ 個のデータ点を一度に処理するミニバッチ法がある。${\displaystyle b}$ が全体の訓練データ数に比べて十分小さい場合、これは擬似的なオンライン学習と見なすことができる。ミニバッチ手法は、訓練データを何度も繰り返し用いることで最適化され、確率的勾配降下法などのアルゴリズムでアウトオブコア学習が実現される。これらはバックプロパゲーションと組み合わせることで、現在では人工ニューラルネットワークの訓練における事実上の標準手法となっている。

線形最小二乗法は、オンライン学習におけるさまざまな概念を説明するための単純な例である。この考え方は、他の凸損失関数を用いる場合にも一般化可能である。

教師あり学習の設定において、学習すべき関数 ${\displaystyle f}$ が以下のような線形関数であるとする：$${\displaystyle f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}}$$ここで、${\displaystyle x_{j}\in \mathbb {R} ^{d}}$ は入力データ点のベクトル、${\displaystyle w\in \mathbb {R} ^{d}}$ は線形フィルタのベクトルである。目標は、このフィルタベクトル ${\displaystyle w}$ を求めることである。

このために、以下のような二乗損失関数を使用する：$${\displaystyle V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}}$$これにより、経験損失を最小化する ${\displaystyle w}$ を求める：$${\displaystyle 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}}$$ここで、${\displaystyle y_{j}\in \mathbb {R} }$ である。

${\displaystyle X}$ を ${\displaystyle i\times d}$ のデータ行列、${\displaystyle y\in \mathbb {R} ^{i}}$ を最初の ${\displaystyle i}$ 個のデータ点に対する目的値の列ベクトルとする。

共分散行列 ${\displaystyle \Sigma _{i}=X^{\mathsf {T}}X}$ が可逆であると仮定した場合（そうでない場合はティホノフ正則化によって処理するのが望ましい）、線形最小二乗問題における最適解 ${\displaystyle f^{*}(x)=\langle w^{*},x\rangle }$ は以下のように与えられる：$${\displaystyle w^{*}=(X^{\mathsf {T}}X)^{-1}X^{\mathsf {T}}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}.}$$このとき、共分散行列${\displaystyle \Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{\mathsf {T}}}$の計算には ${\displaystyle O(id^{2})}$ 時間を要し、${\displaystyle d\times d}$ 行列の逆行列計算には ${\displaystyle O(d^{3})}$ 時間を要する。残りの積の計算には ${\displaystyle O(d^{2})}$ 時間が必要であり、全体の計算時間は ${\displaystyle O(id^{2}+d^{3})}$ となる。

データセット全体が ${\displaystyle n}$ 個の点を含むと仮定した場合、各データ点 ${\displaystyle i=1,\ldots ,n}$ ごとに再計算を行うと、全体の複雑度は ${\displaystyle O(n^{2}d^{2}+nd^{3})}$ となる。なお、行列 ${\displaystyle \Sigma _{i}}$ を保存しておくことで、更新は ${\displaystyle x_{i+1}x_{i+1}^{\mathsf {T}}}$ を加えるだけで済み、これには ${\displaystyle O(d^{2})}$ 時間しかかからない。これにより、全体の計算時間は ${\displaystyle O(nd^{2}+nd^{3})=O(nd^{3})}$ に削減されるが、${\displaystyle \Sigma _{i}}$ を保存するために ${\displaystyle O(d^{2})}$ の追加メモリが必要となる^[1]。

逐次最小二乗法（RLS）アルゴリズムは、最小二乗問題に対するオンライン的な解法である。初期状態として ${\displaystyle w_{0}=0\in \mathbb {R} ^{d}}$ および ${\displaystyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}}$ としたとき、前節で示した線形最小二乗法の解は次の反復により計算できる：$${\displaystyle \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}}}}$$$${\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)}$$この反復アルゴリズムは、${\displaystyle i}$ に関する数学的帰納法により証明可能である^[2]。 さらに、${\displaystyle \Gamma _{i}=\Sigma _{i}^{-1}}$ であることも証明される。

このアルゴリズムを ${\displaystyle n}$ ステップ適用する場合の計算量は ${\displaystyle O(nd^{2})}$ であり、これはバッチ学習による計算よりも高速である。各ステップ ${\displaystyle i}$ で必要な記憶は ${\displaystyle \Gamma _{i}}$ の保存のみであり、これは ${\displaystyle O(d^{2})}$ で一定である。

共分散行列 ${\displaystyle \Sigma _{i}}$ が可逆でない場合には、正則化項を導入した損失関数 ${\displaystyle \sum _{j=1}^{n}\left(x_{j}^{\mathsf {T}}w-y_{j}\right)^{2}+\lambda \|w\|_{2}^{2}}$ を考える。この場合も、初期状態 ${\displaystyle \Gamma _{0}=(I+\lambda I)^{-1}}$ として、同様の反復計算により ${\displaystyle \Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}}$ が得られる。

以下の更新式：$${\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)}$$において、${\displaystyle \Gamma _{i}\in \mathbb {R} ^{d\times d}}$ をスカラーの ${\displaystyle \gamma _{i}\in \mathbb {R} }$ に置き換えた場合、次のようになる：$${\displaystyle 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})}$$これは確率的勾配降下法（SGD）として知られるアルゴリズムである。この方法により、${\displaystyle n}$ ステップに要する計算量は ${\displaystyle O(nd)}$ に削減される。各ステップにおける記憶要件は ${\displaystyle O(d)}$ であり、定数である。

ただし、ステップサイズ ${\displaystyle \gamma _{i}}$ の選択は、期待損失最小化問題の解に収束させるために慎重でなければならない。一般に、${\displaystyle \gamma _{i}\approx {\frac {1}{\sqrt {i}}}}$ のような減衰ステップサイズを選ぶことで、平均反復 ${\displaystyle {\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}}$ の収束が証明される。この設定は、最適化理論における確率的最適化の一例である。

実際には、データに対して複数回の確率的勾配降下パス（サイクルまたはエポックとも呼ばれる）を行うことがある。このアルゴリズムはインクリメンタル勾配法と呼ばれ、次のような反復式で定義される：$${\displaystyle w_{i}=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})}$$ここで、${\displaystyle t_{i}}$ は ${\displaystyle i}$ 番目のステップで使用される訓練点のインデックスを示す。${\displaystyle t_{i}}$ の列は確率的または決定的に選ばれることがある。これにより、各データ点が複数回使用される可能性があるため、反復回数と訓練点数は切り離される。

インクリメンタル勾配法は、経験リスクを最小化する解を得られることが証明されている^[3]。特に、非常に大規模なデータセットにおける経験損失のように、多数の項の和で構成される目的関数を考慮する場合において、この手法は有利である。

カーネルを用いることで、上述のアルゴリズムを非パラメトリックなモデル（もしくは、パラメータが無限次元空間に属するモデル）へと拡張することが可能である。このような手法は、すべてのデータ点を保存する必要があるため厳密にはオンライン学習とは言えないが、全データに対して逐次的に処理を行うバッチ法よりも高速である。

この手法は任意の凸損失関数に拡張可能だが、ここでは二乗損失の場合に議論を限定する。簡単な帰納法により、${\displaystyle X_{i}}$ をデータ行列、${\displaystyle w_{i}}$ を ${\displaystyle i}$ ステップ後の SGD アルゴリズムの出力としたとき、次のように表せる：$${\displaystyle w_{i}=X_{i}^{\mathsf {T}}c_{i}}$$ここで ${\displaystyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}}$ の漸化式は以下：$${\displaystyle c_{0}=0}$$$${\displaystyle (c_{i})_{j}=(c_{i-1})_{j},\quad j=1,2,\dots ,i-1}$$$${\displaystyle (c_{i})_{i}=\gamma _{i}\left(y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x_{i}\rangle \right)}$$${\displaystyle \langle x_{j},x_{i}\rangle }$ は ${\displaystyle \mathbb {R} ^{d}}$ 上の標準的な内積（カーネル）である。よって、予測関数は次のように表される：$${\displaystyle f_{i}(x)=\langle w_{i-1},x\rangle =\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle }$$ここで、一般的なカーネル ${\displaystyle K}$ を導入し、予測関数を次のように定義する：$${\displaystyle f_{i}(x)=\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)}$$このとき、先の証明と同様に以下の漸化式により最小二乗損失を最小化する予測器が得られる：$${\displaystyle (c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x_{i}){\Big )}}$$上式では ${\displaystyle c_{i}}$ を更新するためにすべての過去データを保持する必要がある。${\displaystyle n}$ 番目のデータ点に対する漸化式の計算コストは ${\displaystyle O(n^{2}dk)}$ である。（${\displaystyle k}$ は一対の点に対するカーネル関数評価のコスト）

このように、カーネルを導入することで、元の有限次元のパラメータ空間 ${\displaystyle w_{i}\in \mathbb {R} ^{d}}$ から、カーネル ${\displaystyle K}$ によって表される無限次元の特徴空間へと移行することが可能である。代わりに、サイズ ${\displaystyle i}$ の訓練データに対応する係数ベクトル ${\displaystyle c_{i}\in \mathbb {R} ^{i}}$ 上での漸化式を用いる。この性質は一般に表現定理（英語版）の帰結である。

オンライン凸最適化（Online Convex Optimization, OCO）は、効率的なアルゴリズムを可能とする凸最適化の枠組みに基づいた意思決定の一般的なフレームワークである。以下の繰り返しとして定式化される^[4]：

時刻 ${\displaystyle t=1,2,\dots ,T}$ に対して：

• 学習者は入力 ${\displaystyle x_{t}}$ を受け取る。

• 学習者は固定された凸集合 ${\displaystyle S}$ から ${\displaystyle w_{t}}$ を出力する。

• 自然（環境）は凸損失関数 ${\displaystyle v_{t}:S\rightarrow \mathbb {R} }$ を返す。

• 学習者は損失 ${\displaystyle v_{t}(w_{t})}$ を被り、モデルを更新する。

目的は、後知恵で見た最良の固定点 ${\displaystyle u\in S}$ に対する累積損失との差を最小化することである。例として、オンライン線形回帰では、重みベクトルは ${\displaystyle S=\mathbb {R} ^{d}}$ から選ばれ、自然は損失関数 ${\displaystyle v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}}$ を返す（ここで ${\displaystyle y_{t}}$ は ${\displaystyle v_{t}}$ を通じて暗に提供される）。

ただし、すべてのオンライン予測問題がこの OCO フレームワークに適合するわけではない。たとえば、オンライン分類では、予測領域や損失関数が凸ではないことが多い。このような場合、ランダム化や代理損失関数によって凸化することで対応可能である。

以下に OCO における代表的なアルゴリズムをいくつか紹介する：

最も単純な学習則は、過去のすべてのラウンドでの損失が最小となる仮説を選ぶ方法である。このアルゴリズムは「フォロー・ザ・リーダー」と呼ばれ、時刻 ${\displaystyle t}$ においては以下のように定義される：$${\displaystyle w_{t}=\mathop {\operatorname {arg\,min} } _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)}$$この方法は貪欲法（greedy algorithm）の一種とみなすことができる。オンライン二乗最適化（損失関数が ${\displaystyle v_{t}(w)=\|w-x_{t}\|_{2}^{2}}$ の場合）では、後悔の上限が ${\displaystyle \log(T)}$ であることが示されている。しかし、オンライン線形最適化など他のモデル族に対しては、このような良好な後悔の上限は得られない。そのため、正則化を追加することで FTL を拡張する必要がある。

正則化項を加えて FTL の出力を安定化させたアルゴリズム。正則化関数 ${\displaystyle R:S\to \mathbb {R} }$ を導入し、時刻 ${\displaystyle t}$ において以下のように定義される：$${\displaystyle w_{t}=\mathop {\operatorname {arg\,min} } _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)}$$特に、損失関数が線形、すなわち ${\displaystyle v_{t}(w)=\langle w,z_{t}\rangle }$ であり、${\displaystyle S=\mathbb {R} ^{d}}$ のとき、正則化関数 ${\displaystyle R(w)={\frac {1}{2\eta }}\|w\|_{2}^{2}}$ を選ぶと、以下の更新則が得られる：$${\displaystyle w_{t+1}=-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}}$$この式は ${\displaystyle w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})}$ と書き換えられ、これはオンライン勾配降下法と同一である。

もし ${\displaystyle S}$ が ${\displaystyle \mathbb {R} ^{d}}$ の凸部分集合であるならば、${\displaystyle S}$ への射影を行う必要があり、更新則は以下のように変わる：$${\displaystyle w_{t+1}=\Pi _{S}(-\eta \sum _{i=1}^{t}z_{i})=\Pi _{S}(\eta \theta _{t+1})}$$このアルゴリズムは「レイジー・プロジェクション」とも呼ばれ、${\displaystyle \theta _{t+1}}$ が勾配の累積を保持する形式である。これはネステロフの双対平均法とも呼ばれている。線形損失関数と二乗正則化の組み合わせにおいては、後悔の上限は ${\displaystyle O({\sqrt {T}})}$ であり、平均後悔は 0 に収束することが保証されている。

前節では、線形損失関数 ${\displaystyle v_{t}(w)=\langle w,z_{t}\rangle }$ に対して後悔の上限を証明した。これを任意の凸関数に拡張するには、関数 ${\displaystyle v_{t}}$ の点 ${\displaystyle w_{t}}$ における劣勾配 ${\displaystyle \partial v_{t}(w_{t})}$ を線形近似として用いる。この手法により得られるアルゴリズムが「オンライン劣勾配降下法（Online Subgradient Descent, OSD）」である。

アルゴリズムは以下のように定義される：

初期化：パラメータ ${\displaystyle \eta }$ を設定し、${\displaystyle w_{1}=0}$ とする。

時刻 ${\displaystyle t=1,2,\ldots ,T}$ に対して：

• ${\displaystyle w_{t}}$ を用いて予測を行い、自然から損失関数 ${\displaystyle v_{t}}$ を受け取る。
• ${\displaystyle z_{t}\in \partial v_{t}(w_{t})}$ を選択する（${\displaystyle z_{t}}$ は部分勾配）。
• もし ${\displaystyle S=\mathbb {R} ^{d}}$ であれば、更新則は ${\displaystyle w_{t+1}=w_{t}-\eta z_{t}}$ となる。
• もし ${\displaystyle S\subset \mathbb {R} ^{d}}$ であれば、累積勾配に基づいて ${\displaystyle S}$ への射影を行い、${\displaystyle \theta _{t+1}=\theta _{t}+z_{t}}$ により ${\displaystyle w_{t+1}=\Pi _{S}(\eta \theta _{t+1})}$ を計算する。

この OSD アルゴリズムを用いることで、サポートベクターマシン（SVM）の分類タスクに対するオンライン版において、後悔が ${\displaystyle O({\sqrt {T}})}$ に抑えられることが示されている。ここで用いられる損失関数ヒンジ損失（英語版）であり、以下のように定義される：

${\displaystyle v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}}$

二乗正則化付きのFTRL（Follow The Regularized Leader）アルゴリズムは、前節で述べたような遅延射影付き勾配アルゴリズムを導出する。任意の凸関数および正則化関数に対してこの手法を拡張するには、オンライン鏡像降下法を用いる。

線形損失関数に対して後悔を最小化するような最適な正則化手法は、理論的に導出可能であり、この手法はAdaGradアルゴリズムと呼ばれる。ユークリッドノルムによる正則化を用いた場合、後悔は ${\displaystyle O({\sqrt {T}})}$ に抑えられる。さらに、損失関数が強凸または指数的に凹である場合には、後悔の上限は ${\displaystyle O(\log T)}$ に改善される。

継続学習（英語版）とは、継続的に情報の流れを処理しながら学習モデルを改善し続ける学習である^[5]。

継続学習能力は、現実世界の変化に常時対応するソフトウェアシステムや自律エージェントにとって不可欠である。一方で、現状の機械学習およびニューラルネットワークモデルによる継続学習には課題が残る。非定常なデータ分布から漸進的に得られる情報を継続的に学習することは、通常、破滅的忘却を引き起こすからである。

オンライン学習の枠組みは、選択する学習モデルに応じて異なる解釈を持つ。それぞれの解釈は、関数列 ${\displaystyle f_{1},f_{2},\ldots ,f_{n}}$ の予測性能に対する異なる意味合いを持つ。ここでは代表的な 確率的勾配降下法（SGD）アルゴリズムを例に挙げて説明する。このアルゴリズムの反復式は以下の通りである：

$${\displaystyle w_{t}=w_{t-1}-\gamma _{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})}$$解釈のひとつは、上記の式を用いて期待リスク ${\displaystyle I[w]}$ を最小化する問題に確率的勾配降下法を適用するものである^[6]。無限のデータストリームを仮定した場合、例 ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),\ldots }$ は ${\displaystyle p(x,y)}$ に従って独立同分布（i.i.d.）により得られると考えられる。このとき、関数 ${\displaystyle V(\cdot ,\cdot )}$ の勾配列は期待リスクの勾配の確率推定値と見なすことができ、確率的勾配降下法の収束解析を適用して ${\displaystyle I[w_{t}]-I[w^{\ast }]}$ の偏差を評価することが可能である。ここで ${\displaystyle w^{\ast }}$ は ${\displaystyle I[w]}$ の最小値を与える点である^[7]。この解釈は有限の訓練データセットにおいても有効であるが、その場合はデータに複数回アクセスすることで勾配の独立性が失われる。ただし、特定の条件下では理論的解析は依然として可能である。

2つ目の解釈は、有限の訓練データセットにおける SGD を 逐次的勾配法（incremental gradient descent）の一例と見なすものである。この場合、評価対象は経験リスクとなる：$${\displaystyle I_{n}[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i})\ .}$$このとき、反復式で使われる勾配は ${\displaystyle I_{n}[w]}$ の勾配の確率推定値となるため、この解釈もまた確率的勾配降下法と関連している。ただし対象となるのは期待リスクではなく経験リスクである。したがって、この解釈ではデータに複数回アクセスすることが許容され、むしろ推定誤差を減らす効果がある。つまり、${\displaystyle I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]}$ の偏差に対してより厳密な上限評価が可能である。ここで ${\displaystyle w_{n}^{\ast }}$ は ${\displaystyle I_{n}[w]}$ の最小値を与える点である。

学習パラダイム

• 継続学習（英語版）

• 怠惰学習

• 強化学習

• 多腕バンディット問題

• 教師あり学習

一般的なアルゴリズム

• オンラインアルゴリズム
• オンライン最適化（英語版）
• ストリーミングアルゴリズム（英語版）

• 確率的勾配降下法

学習モデル

• 適応共鳴理論
• 階層的時系列記憶（英語版）
• k近傍法
• ベクトル量子化学習（英語版）

• パーセプトロン

1. ^ L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015. Chapter 7 - Online Learning
2. ^ Kushner, Harold J.; Yin, G. George (2003). Stochastic Approximation and Recursive Algorithms with Applications (第二版 ed.). New York: Springer. pp. 8–12. ISBN 978-0-387-21769-7 
3. ^ Bertsekas, D. P. (2011). Incremental gradient, subgradient, and proximal methods for convex optimization: a survey. Optimization for Machine Learning, 85.
4. ^ Hazan, Elad (2015). Introduction to Online Convex Optimization. Foundations and Trends in Optimization. http://ocobook.cs.princeton.edu/OCObook.pdf 
5. ^ 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. http://dx.doi.org/10.1016/j.neunet.2019.01.012. 
6. ^ Bottou, Léon (1998). “Online Algorithms and Stochastic Approximations”. Online Learning and Neural Networks. Cambridge University Press. ISBN 978-0-521-65263-6. https://archive.org/details/onlinelearningin0000unse 
7. ^ Stochastic Approximation Algorithms and Applications, Harold J. Kushner and G. George Yin, New York: Springer-Verlag, 1997. ISBN 0-387-94916-X; 第2版は 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