オンライン学習

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

## はじめに
教師あり学習の設定では、関数  f : X \to Y を学習することが目的である。ここで、X は入力の空間、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} により、予測値 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} を経験リスク最小化あるいはティホノフ正則化を用いた正則化付き経験リスク最小化によって推定するのが一般的である。損失関数の選択により、正則化付き最小二乗法やサポートベクターマシン（SVM）などのよく知られたアルゴリズムが得られる。

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

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

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

### バッチ学習
教師あり学習の設定において、学習すべき関数 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^2d^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) の追加メモリが必要となる。

### オンライン学習：逐次最小二乗法
逐次最小二乗法（RLS）アルゴリズムは、最小二乗問題に対するオンライン的な解法である。初期状態として w_0 = 0 \in \mathbb{R}^d および \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 に関する数学的帰納法により証明可能である。 さらに、\Gamma_i = \Sigma_i^{-1} であることも証明される。

このアルゴリズムを 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 \|w\|_2^2 を考える。この場合も、初期状態 \Gamma_0 = (I + \lambda I)^{-1} として、同様の反復計算により \Gamma_i = (\Sigma_i + \lambda I)^{-1} が得られる。

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

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

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

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

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

この手法は任意の凸損失関数に拡張可能だが、ここでは二乗損失の場合に議論を限定する。簡単な帰納法により、X_i をデータ行列、w_i を i ステップ後の SGD アルゴリズムの出力としたとき、次のように表せる： w_i = X_i^\mathsf{T} c_i ここで c_i = ((c_i)_1, (c_i)_2, ..., (c_i)_i) \in \mathbb{R}^i の漸化式は以下： c_0 = 0  (c_i)_j = (c_{i-1})_j,\quad j=1,2,\dots,i-1  (c_i)_i = \gamma_i \left(y_i - \sum_{j=1}^{i-1} (c_{i-1})_j \langle x_j, x_i \rangle \right) \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 d k) である。（k は一対の点に対するカーネル関数評価のコスト）

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

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

時刻 t = 1, 2, \dots, 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 フレームワークに適合するわけではない。たとえば、オンライン分類では、予測領域や損失関数が凸ではないことが多い。このような場合、ランダム化や代理損失関数によって凸化することで対応可能である。

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

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

#### フォロー・ザ・レギュラライズド・リーダー（FTRL）
正則化項を加えて 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 のとき、正則化関数 R(w) = \frac{1}{2\eta} \|w\|_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} が勾配の累積を保持する形式である。これはネステロフの双対平均法とも呼ばれている。線形損失関数と二乗正則化の組み合わせにおいては、後悔の上限は O(\sqrt{T}) であり、平均後悔は 0 に収束することが保証されている。

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

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

初期化：パラメータ \eta を設定し、w_1 = 0 とする。

時刻 t = 1,2,\ldots,T に対して：

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

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

 v_t(w) = \max \{ 0, 1 - y_t(w \cdot x_t) \} 

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

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

## 継続学習
とは、継続的に情報の流れを処理しながら学習モデルを改善し続ける学習である。

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

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

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

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

## 関連項目
**学習パラダイム**

* 

* 怠惰学習

* 強化学習

* 多腕バンディット問題

* 教師あり学習

**一般的なアルゴリズム**

* オンラインアルゴリズム
* 
* 

* 確率的勾配降下法

**学習モデル**

* 適応共鳴理論
* 
* k近傍法
* 

* パーセプトロン

## 参考文献


## 外部リンク

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