オンライン機械学習

線形最小二乗法の単純な例を用いて、オンライン学習における様々な概念を説明する。これらの概念は十分に一般的であるため、例えば他の凸損失関数など、他の設定にも適用できる。

監督付き学習の設定を検討します${\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 O(d^{2})}$保管する$\displaystyle \Sigma _{i}}$[ ^{2 ]​}

再帰的最小二乗法（RLS）アルゴリズムは、最小二乗問題に対するオンラインアプローチを検討します。初期化することで、${\displaystyle \textstyle w_{0}=0\in \mathbb {R} ^{d}}$そして$\displaystyle \textstyle \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}$[ ^{3 ]また、}証明によれば、$\displaystyle \Gamma _{i}=\Sigma _{i}^{-1}}$RLSは適応フィルタの文脈でも考察できます（RLSを参照）。

複雑さ${\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 \left\|w\right\|_{2}^{2}}$そうすれば、同じアルゴリズムが${\displaystyle \Gamma _{0}=(I+\lambda I)^{-1}}$、そして反復処理は次のように進む。${\displaystyle \Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}}$[ ^{2 ]​}

このとき $${\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)}$$ に置き換えられます $${\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})}$$ または${\displaystyle \Gamma _{i}\in \mathbb {R} ^{d\times d}}$による${\displaystyle \gamma _{i}\in \mathbb {R} }$すると、これは確率的勾配降下法アルゴリズムになります。この場合、計算量は${\displaystyle n}$このアルゴリズムのステップは、${\displaystyle O(nd)}$各段階におけるストレージ要件${\displaystyle i}$は一定です${\displaystyle O(d)}$。

ただし、ステップサイズ${\displaystyle \gamma _{i}}$前述のように、期待されるリスク最小化問題を解決するには、ステップサイズを慎重に選択する必要があります。減衰ステップサイズを選択することで、${\displaystyle \gamma _{i}\approx {\frac {1}{\sqrt {i}}},}$平均反復の収束を証明できる${\textstyle {\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}}$この設定は、最適化におけるよく知られた問題である確率的最適化の特殊なケースである。 ^{[ 2 ]}

実際には、データに対して複数の確率的勾配パス（サイクルまたはエポックとも呼ばれる）を実行できます。このようにして得られるアルゴリズムは増分勾配法と呼ばれ、反復に対応します。 $${\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}$これは、第 1 ステップです。このようなシーケンスは、確率的または決定論的である可能性があります。反復回数は、点の数とは切り離されます (各点は複数回考慮できます)。増分勾配法は、経験的リスクの最小化を提供することが示されています。^{[ 4 ]}増分手法は、多数の項の合計で構成される目的関数 (たとえば、非常に大きなデータセットに対応する経験的誤差) を考慮する場合に有利になることがあります。^{[ 2 ]}

カーネルを使用すると、上記のアルゴリズムを非パラメトリックモデル（またはパラメータが無限次元空間を形成するモデル）に拡張できます。対応する手順はもはや真のオンラインではなく、すべてのデータポイントを保存する必要が生じますが、それでも総当たり法よりは高速です。この議論は二乗損失の場合に限定されていますが、任意の凸損失に拡張できます。簡単な帰納法^{[ 2 ]}により、次のことが示されます。${\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_{i}}$再帰を満たす： $${\displaystyle c_{0}=0}$$$${\displaystyle (c_{i})_{j}=(c_{i-1})_{j},j=1,2,...,i-1}$$そして $${\displaystyle (c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x_{i}\rangle {\Big )}}$$ ここで注目してください${\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}$これは、単一の点ペアでカーネルを評価するコストです。^{[ 2 ]}このように、カーネルの使用により、有限次元のパラメータ空間から${\displaystyle \textstyle w_{i}\in \mathbb {R} ^{d}}$カーネルによって表現される、おそらく無限次元の特徴へ${\displaystyle K}$代わりにパラメータ空間で再帰を実行する${\displaystyle \textstyle c_{i}\in \mathbb {R} ^{i}}$次元はトレーニングデータセットのサイズと同じです。一般に、これは表現定理の結果です。^{[ 2 ]}

オンライン凸最適化（OCO）^{[ 5 ]}は、凸最適化を活用して効率的なアルゴリズムを実現する意思決定のための一般的なフレームワークです。このフレームワークは、以下のような繰り返しゲームプレイに基づいています。

のために${\displaystyle t=1,2,...,T}$

• 学習者は入力を受け取る${\displaystyle x_{t}}$
• 学習者の成果物${\displaystyle w_{t}}$固定された凸集合から${\displaystyle S}$
• 自然界は凸型の損失関数を返す${\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のフレームワークに適合しません。たとえば、オンライン分類では、予測領域と損失関数は凸ではありません。このようなシナリオでは、凸化のための2つの単純な手法、ランダム化と代理損失関数が使用されます^{[ 6 ]}。

単純なオンライン凸最適化アルゴリズムの例をいくつか挙げます。

上記は、線形損失関数に対する後悔限界を証明した。${\displaystyle v_{t}(w)=\langle w,z_{t}\rangle }$アルゴリズムを任意の凸損失関数に一般化するために、劣勾配${\displaystyle \partial v_{t}(w_{t})}$の${\displaystyle v_{t}}$は、の線形近似として使用されます。${\displaystyle v_{t}}$近く${\displaystyle w_{t}}$これにより、オンライン劣勾配降下法アルゴリズムが開発された。

パラメータを初期化します${\displaystyle \eta ,w_{1}=0}$

のために${\displaystyle t=1,2,...,T}$

• 予測に使用${\displaystyle w_{t}}$、 受け取る${\displaystyle f_{t}}$自然から。
• 選ぶ${\displaystyle z_{t}\in \partial v_{t}(w_{t})}$
• もし${\displaystyle S=\mathbb {R} ^{d}}$更新${\displaystyle w_{t+1}=w_{t}-\eta z_{t}}$
• もし${\displaystyle S\subset \mathbb {R} ^{d}}$累積勾配を投影する${\displaystyle S}$つまり${\displaystyle w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}}$

OSDアルゴリズムを使用して導出できます${\displaystyle O({\sqrt {T}})}$ヒンジ損失を使用する分類用オンラインSVMの後悔境界${\displaystyle v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}}$

二次正則化FTRLアルゴリズムは、上述のように遅延射影勾配アルゴリズムにつながります。任意の凸関数と正則化関数に上記を適用するには、オンラインミラー降下法を使用します。線形損失関数に対しては、後知恵による最適な正則化を導出でき、これによりAdaGradアルゴリズムが得られます。ユークリッド正則化の場合、後悔限界を示すことができます。${\displaystyle O({\sqrt {T}})}$さらに改善すれば${\displaystyle O(\log T)}$強凸型および指数凹型の損失関数について。