オンライン最適化とRegret最小化

大量のデータから、何か有益な情報を求める問題の多くは最適化問題を解くことに帰着されます．
最適化問題とは与えられた関数fの値を最小（最大）にするような変数xを探すといった問題です。

例えば、機械学習（これを利用する自然言語処理、情報検索など）、画像処理、AI(ロボットの経路制御）、
など多くの分野で最適化問題は登場します。

その中でもオンライン最適化（機械学習の文脈でいえばオンライン学習）と呼ばれる最適化手法は
実用性の高さと実装のしやすさから多く利用されるようになってきました。

このオンライン最適化は近年Regret（後悔）最小化というゲーム理論などで使われていた枠組みで
解析されることが多くなってきました。

今回はこのRegret最小化について簡単に解説してみようと思います。

（機械学習が詳しい人向けに補足すると、VC次元など他の機械学習を解析する手法と比べてRegret最適化の面白い点は入力、最適化関数に対する仮定が非常に少ない点、有限回数に対する収束度合いを求められ、それがタイトな場合が多い点などです。）

厳密な議論については[1]を参考にしてください。

Regret最小化の問題設定は次の通りです。

プレイヤーは毎回、可能なアクション集合Kから一つのアクションx∈Kを選択します．
その後に関数fが提示され、コストf(x)が決まります。
この操作を何回も繰り返していきます。t回目のアクションと関数をそれぞれx_t、f_tとします。ここでf_tは必ずしも同じでなく毎回違ってもよいものとします。

この時、プレイヤーは合計コストf_1(x_1)+f_2(x_2)+...+f_t(x_t)をどのようにすれば最小化することができるでしょうか。

合計コストで戦略をそのまま評価するには関数を自由に決められるのでどんな戦略に対しても
コストを無限大にすることができるので問題設定として面白くありません。

そこで、同じアクションしかとらない固定戦略の中で最も合計コストが少なくなる戦略が達成する合計コストとの差を考えてみます。これを「あの戦略をとっていればよかったのに・・」との差を測る指標というわけでRegret（後悔）と呼びます。

もう少し詳しく説明してみます。T回ラウンドが進んだ後に、時間を巻き戻して合計コストが最小になるようなアクションをx^*を一つ選びます。

この時、ある戦略AのRegret(A)とは、最適の固定戦略と実際にとった戦略との合計コストの差をいいます。

Regret_T(A) = (f_1(x_1)+f_2(x_2)+...+f_t(x_t) ) - (f_1(x^*)+f_2(x^*)+...+f_t(x^*) )

さて、この値がどのような意味を持つのかについて考えてみましょう

Regret_T(A)が試行回数Tに対し線形（O(T))であれば、どれだけ回数を重ねても最適な戦略との差は埋まりません。
それに対し、Regret_T(A)がTに対し線形よりも少しでも小さければ(o(T))、試行回数を重ねるにつれ、最適な固定戦略と戦略Aによる
1回あたりのコストの差は0に近づいていきます。つまり、_1...f_tがどのような形をとっても最適な固定戦略に限りなく近づくことが言えます。

このRegret最小化問題はオンライン最適化を特殊ケースとしてふくんでいます

関数fが与えられた時、その値f(x)が最小となるような入力x=x^*を求めるのが最適化問題でした。
オンライン最適化の場合は毎回関数が固定であり、プレイヤーのアクションは毎回その時点での最適化結果に対応します。

この場合Regret_T(A)はfの最適値f(x^*)と、現在の最適化結果f(x_t)との差の合計となります。Regret_T(A)=o(T)を達成するような戦略は最適値を見つけられるようなオンライン最適化であることがいえます。

オンライン学習の例をみていきましょう
機械学習の目標は（すごい大雑把にいえば）訓練例とパラメータθで特徴付けられる学習器F（θ)が与えられた時、
訓練例を全て正しく分類してくれるようなパラメータθ^*を求めることです。

オンライン学習の場合には毎回訓練例が一つ与えられ、それを利用して現在のパラメータを更新します。

t回目の関数f_tをt番目の訓練例を正解した時0, 不正解の時に1となるような関数に選ぶことで、Regret_T(A)は最適なパラメータθ^*を利用した場合の不正解数と、現在のオンライン学習の不正解数の差となります。

Regret_T(A)/Tが0に速く近づけば近づくほど、より高速な学習が達成できることになります。

====

もう少し実際の問題に近づけてみましょう

- 各関数 f_tが凸関数（f_1..f_tが同じ関数である必要はない）
- とりうるアクションxが凸空間中の点（多くの場合m次元ユークリッド空間中の点）

まず最初に最も単純な戦略Follow The Leader(FTL)を紹介します。

この戦略ではt回目のアクションx_tを次のように決定します

f_1(x) + f_2(x) + ... + f_{t-1}(x) を最小化するようなアクションxをx_tとする

一見よさそうな戦略ですが、f_1...f_{t-1}とf_tの間に何も仮定をおいていない点に注意してください。
f_t(x_t)を最小化したいのに、それと全く関係の無いf_1...f_{t-1}を最小化するxを選んでいるわけです。

実際、この戦略がうまくいかないようなコスト関数の例を作ることができます。
例えば、アクションが一次元中の-1<=x<=1中の点だとし、f_i(x) = (1/2)(-1)^{i}x という関数がi回目に来るとすると
FTLの戦略のとるアクションは最初は0のあと、-1,1,-1..1となりコスト値は常に1です。
それに対しこのコスト関数列に対する最適な固定戦略はx=0であり、コストの合計値は0です。
よって、Regret_T(A)=T-1であり、縮まることがありません。

どのように改善できるかを考えてみると、最適な固定戦略との差を評価している以上、毎回のアクションが大きく変わって
しまわなければよさそうです。そこで、t回目のアクションx_tを次のように求めてみることを考えてみます

f_1(x_t) + f_2(x_t) + ... + f_{t-1}(x_t) + 1/C R(x_t)を最小化するようなアクションx_t

但し、R(a)は正規化項でaから実数への関数、Cは学習時のパラメータです。この戦略をRegularized Follow The Leader
(RFTL)と呼びます。

このRFTLはいくつかの重要なオンライン最適化法をふくんでいます。
fが線形関数、xがシンプレックス上にあり、R(x)=-x log xの場合、RTFLはmultiplicative
updateと一致します（x_{t+1} ∝ x_t e^{-C f_t'(x_t)})
fがxの線形関数、xが単位円上にあり、R(x)=|x|_2^の場合、RTFLは勾配降下法に一致します（x_{t+1} ∝ x_t - Cf_t'(x_t))

そして、RTFLはFTLと非常に似ているのにも関わらずどんなコスト関数に対してもうまくいきます。
つまりRegret_T(A)=o(T)を達成します。

具体的にはRegret_T(A) <= 2(λDT)^{1/2}です。但し、
λは{f_i}とRによってのみ決定される定数、
Dは正則化関数とx^*, x_1によってのみ決定される定数です。

証明はコーシー・シュワルツの定理とテイラー展開を使って比較的素直に導出できます。（[1]を参照）

この結論は、もちろんその特殊な場合であるオンライン凸最適化にも適用できます。
つまりこのFTLという単純な戦略は正則化項を入れることにより、どんなコスト関数がやってきても動的に対応でき、常に最適解に漸近する戦略に化けます。

# コスト関数を調整することで、いくらでもRegretを増やすことができるように思えますが、
　この戦略を騙すように、コスト関数を調整すればするほど、最適な戦略が達成するコスト値も上昇し、
　結局Regretは大きくすることはできません。

===

最後に、最近の話を少しみてみましょう

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization,
J. Duchi, E. Haza, Y. Singer, COLT 2010 [pdf]

この手法ではRegret最小化を詳細に分析することにより、現時点で最も高速に収束し、任意の損失関数、正則化（L1正則化も含む）を利用できるようなオンライン最適化アルゴリズムを構成することに成功しています。

通常の正則化に加え、Regret自体が小さくなるような正則化項を入れて更新即を導くと
他のオンライン最適化（例えばCWやAROW）が行っているのと同じように確信度が高い次元に対しては更新幅を小さくしそうでない場合は大きく更新するような更新即が自然と導くことができます。

この手法では任意の損失関数、正則化が使えるので、例えばL1正則化を併用することでCW, AROWと同程度の性能でありながら、多くのパラメータが0であるような結果を得ることができます。

また、結果として得られるパラメータの更新即は非常にシンプルで実用的です。

==

Regret 最小化については以下の簡潔によくまとまったサーベイが参考になります。
今回の解説の例や解説も以下から引用いたしました。
[1] "The convex optimization approach to regret minimization", E.Hazan, [pdf]