機械学習プロフェッショナルシリーズ「オンライン予測」読書メモ

サマリー

オンライン予測は、機械学習の分野で使用される、逐次的にデータを受け取り、リアルタイムで予測を行うための理論的な枠組みとなる。オンライン予測は、例えば天気予報や株価の変動予測等の文字通りの予測の問題といったシンプルな予測問題だけではなく、確率的言語モデルの構築、スループットの高いネットワークルーティングの設計、オークションにおける妥当な価格の決定、ゲームにおける最適混合戦略の導出などの、過去の経験から将来の出来事を予測する様々な問題に意思決定問題を組み合わせたものであると定義されている。

またオンライン予測は、与えられたデータの分布を事前に知ることができない場合にも、最適な予測を行うことができるように開発されており、オンライン予測を用いることで、最適な予測手法を見つけ出し、予測性能を最大化することも可能としている。

これらは”バンディット問題の理論とアルゴリズム“で述べられた多腕バンディット問題や、”様々な強化学習技術の理論とアルゴリズムとpythonによる実装“で述べられた強化学習技術とも密接に関係している技術となる。

ここでは、このオンライン予測技術に関して機械学習プロフェッショナルシリーズ「オンライン予測」をベースに様々なアルゴリズムや応用について述べている。

今回は読書メモについて述べる。

機械学習プロフェッショナルシリーズ「オンライン予測」読書メモ

「絶えず流れる情報を、いかに捉え、いかに学習するか？　広告配信、証券投資、経路探索……いまや豊富な応用分野を擁するオンライン予測。Ｈｅｄｇｅ、ＯＧＤ、ＯＮＳなど多彩なアルゴリズムを理解し、使えるようになる。」

まえがき

天気予報や株価予想といったつく時的な予測・意思決定問題は古くから統計学などの立場
1990年代からコンピュータ・サイエンスの理論研究者が学習・予測問題に対して
アルゴリズム観点から取り組み
「計算学習理論」と言う学問が生まれる
中でも逐次的予測問題を扱う理論
オンライン予測理論の特筆すべき点
データの生成過程に対してなんら過程をおいていない
過程がないと予測アルゴリズムの性能を評価することは一般的には不可能
オンライン予測理論では
性能を絶対評価する代わりに
「後から見て適切な」予測戦略に対する相対的な評価を行う
あの時こうしておけばよかったといった後悔の量を定式化および評価
データの生成過程を予測することが困難なオンライン予測問題に対してとても有効
オンライン予測理論は
オンライン予測だけではなく
最適化問題に対しても有効な設計指針を与える

第 1 章 エキスパート統合問題

はじめに
オンライン予測理論の導入として
最も基本的な枠組みであるエキスパート統合問題について述べる
エキスパート統合問題は
その単純さにもかかららず、
様々な領域における意思決定問題を表せる
ユニバーサル符号における情報源の確率分布指定問題や
繰り返しゲームにおける行動選択問題など
1.1 N 人のクイズ王の問題
はじめに
前提条件
東京ドームで行われているクイズ大会の一次予選に参加している
第一問は「ニューヨークの自由の女神は、かつて灯台だった。◯かXか?
◯X形式のクイズがたくさん出題され、成績上位者が予選に進むことができる
かつてこの大会で優勝したことのあるクイズ王(エキスパート)がN人参加しているのを見つけ、彼らの動向を見てから自分の答えを決める
エキスパート達はすぐに答えの陣地に移動するので、カンニング的な戦略をとる時間的余裕がある
エキスパート達の答えをどのように統合すれば良いのか?
問題の定式化や統合アルゴリズムの設計と解析手法について説明する
N人のクイズ王の問題の登場人物
プレイヤー
N人のエキスパート
出題者
プレイヤー以外の主体はプレイヤーの外部にあり、その振る舞いはプレイヤーには制御できない
問題の定義
環境は、ベクトルzt=(zt,1,…,zt,N)∈{0,1}Nをプレイヤーに提示
Ztの第I成分zt,i∈{0,1}は、試行tにおけるクイズに対するi番目のエキスパートの答えを示す
プレイヤーは、答えをxt∈{0,1}と予測し、これを出力
環境は、クイズの正解yt∈{0,1}をプレイヤーに提示
各試行tにおいて、プレイヤーは、 それまでに提示されたデータ系列St=((z1,y1),..,(zt-1,yt-1),zt)にのみ基づいて、 自分の答えxtを決定する
考えるべきアルゴリズムはStからxtを求める部分
プレイヤーの自明な目標
謝り回数(上式)をできるだけ少なくする
統計的学習の手法を使ってみる?
統計的学習の手法を利用する
何らかの仮説クラスH⊆{h:{0,1}N→{0,1}}を導入する
Stをサンプルとみなして仮説ht∈Hを推定した後
xt=ht(zt)を予測値とする
典型的な2値分類学習の問題
学習がうまくいけば汎化誤差Pr(yt≠xt)が0に収束する
謝り回数の期待値を抑えられる
統計的学習の手法がうまくいくためには、 必ずサンプルの生成のされ方に関して、 確率的な過程が必要
例
仮定:{0,1}Nx{0,1}上のある分布Dが存在して、 各事例(zt,yt)は、それぞれ独立に分布Dに従って生成される
N人のクイズ王の問題の場合は、上記のような過程を置くことは不自然
敵対的な環境
サンプルの生成のされ方に関して、 なんの仮定もおかないと、どんなに優れたプレイヤーのアルゴリズムを用いても、 最悪の場合は全問不正解になる
プレイヤーの任意の(決定的)アルゴリズムをAとする
アルゴリズムAは、 仮定Pのもとでは汎化誤差が0に収束するような学習アルゴリズムでも良い
アルゴリズムAにサンプルSiを入力として与えた時、 出力として得られるプレイヤーの答えをA(Si)∈{0,1}として表記する
上記のような環境のアルゴリズムBを考える
偶然に敵対する振る舞いをする可能性が0でないことを示す
実際のエキスパートやクイズの出題しやは、自分の意思でフェアに行動しているつもりでも、運命的にアルゴリズムBと同じ振る舞いをしてしまう可能性も否定できない
環境がプレイヤーのアルゴリズムAを知っているとすると、 クイズを出題する前にプレイヤーの答えが分かるので
それが不正解になるようなクイズを出題すれば良い
敵対的なアルゴリズムを導入して最悪の場合の解析を行う手法
これ以降、敵対的な振る舞いをする環境のみを考える
環境のことを敵対社(adversary)と呼ぶ
1.2 全問正解のエキスパートが存在する場合
はじめに
敵対者を相手にした場合のN人のクイズ王の問題に対する良い戦略は?
まず、全問正解するエキスパートが存在する場合について考える
プレイヤーの素朴な戦略
全問正解をつづけているエキスパートのどれかを選び、そのエキスパーちの真似をする
最悪N-1回しか間違えない
プレイヤーが間違えるたびに、全問正解を続けているプレイヤーが一人以上減る
1.2.1 2分法
最も良い戦略
全問正解を続けているエキスパートの多数決に従う
プレイヤーが間違えたということは、 全問正解を続けているエキスパートの過半数が間違える
プレイヤーが間違えるたびに、 全問正解を続けているエキスパートの数が半分以下になる
2分法の誤り回数に対する定理
全問正解のエキスパートが存在するという過程のもとでは
決定アルゴリズムとしては、2分法が最適である
2分法の最適性
プレイヤの任意の決定的アルゴリズムAに対し
敵対者のアルゴリズムB’を構成する
B’の目標は、プレイヤーの謝り回数をlog2N回にしつつ
全問正解のエキスパートの存在を保証する
簡単のため
エキスパート数Nは2のベキ数 (ある自然数kが存在して、N=2kとする)
アルゴリズムB’は、総試行回数をT=kとおき、アルゴリズムBと同じ方法で、プレイヤーを全問不正解にする
アルゴリズムB’の擬似コード
1.2.2 乱択2分法
全問正解のエキスパートが存在する場合
2分法が決定的アルゴリズムとして最適
謝り回数の上限がlog2N
本項と次項で、 乱択アルゴリズムについて考え、 謝り回数和期待値で評価する
本稿では、次のような単純な戦略を考える
全問正解を続けているエキスパートから 一様ランダムに一人選び、その決定に従う
乱択2分法の性能
lnN≃0.693log2Nなので
乱択2分法は、2分法に比べて約30%性能が改善されている
上式のような級数
入れ子状の筒を用いた伸縮式の機構を持つ望遠鏡に擬えて
オンライン予測ある美リズムでよくもついられる
1.2.3 c乱択2分法
さらに工夫することによる性能の改善が可能になる
2分法と乱択2分法において
試行tでxt=1を出力する確率ptの決め方について考察する
Wtを、試行t-1までのクイズに正解したエキスパートの数
Ktを、それらエキスパートの中で、試行tのクイズで答えを1と予測したエキスパートの数
Ptは、ある関数f:[0,1]→[0,1]を用いてpt=f(Kt/Wt)のように表すことができる
具体的には
2分法の場合は、多数決に基づく決定的な方法なので
乱択2分法の場合は、一様ランダムに選ぶ手法なので
これを一般化して上図に示すように、実数c∈[0, 1/2]をパラメータとする関数fcを用いてpt=fc(Kt/Wt)とするアルゴリズムを C乱択2分法
C乱択2分法アルゴリズム
2分法はc=1/2, 乱択2分法はc=0の特別な場合となる
Cの値を最適化することにより、 もっと良い性能を持つアルゴリズムが導出できる可能性が見える
C乱択2分法の性能を解析するために
試行tでの誤り確率qt=Pr(yt≠xt)とWt+1/Wtの関係について考察する
yt=0の時
yt=1の時
いずれの場合でも上記が成り立つ
右辺の関数を厳密に上から押さえる指数関数をbc-qtとする
bcは、任意のx∈[0,1]に対して、 1 – fc-1(x) ≤ b-xを満たす最大の実数b
パラメータcによって一位に決まる
このbcを用いて、c乱択2分法の性能の性質を評価することができる
bcを最大にするパラメータcを用いた乱択2分法が最適
2分法、乱択2分法、一般のcに対するc乱択2分法のそれぞれの場合の 関数1-fc-1(x)とbc-xの関係補図したもの
最適なc乱択2分法
最適なcの値は約0.15
この結果は、 以下の戦略が優れていることを示す
全問正解を続けているエキスパートの役85%以上の答えが 一致していればその結果に従い
そうでない場合は(意見がある程度割れている)、
多数派の割合を少し増幅した確率で多数派の答えに
残りの確率で少数派の答えに従う
最適なc乱択2分法は
全てのランたくアルゴリズムの中でも最適である
1.3 全問正解のエキスパートが存在するとは限らない場合
はじめに
全問正解のエキスパートが存在するとは限らない、一般の場合
この場合
任意の決定的なプレイヤーに対し
敵対者はアルゴリズムBを用いてAを全問不正解にできる
乱択なプレイヤーに対しても
対乱択プレイヤー用の敵対者のようにytを定めることで
誤り回数の期待値をT/2以上とすることができる
各試行でランダムに答えを予測するプレイヤーの誤り回数の期待値は
どんな敵対者に対しても、ちょうどT/2になる
これらのことから以下の基準のもとでは 各試行でランダムに解答するアルゴリズムが最適であると結論づけられる
プレイヤーの誤り回数(の期待値)を評価指標とし
データ系列((z1,y1),…,(zr,yr))の生成のされ方に何の過程もおかず
プレイヤーの成績を最悪の場合で評価する
上記の議論はN人の振る舞いも含めて最悪の場合を想定したもの
1.3.1 リグレット
より現実的な問題設定を考える
N人のクイズ王の問題で求められているもの
いずれかのエキスパートが(全問正解とはいかないまでも)良い成績を達成した場合に限り
それなりに良い成績を達成することが保証されたアルゴリズム
つまり
全てのエキスパートの成績が悪かったら諦めるが
誰か一人でも良い成績を収めたエキスパートが存在したときは
それなりに良い成績を収めた
この理念に基づいて、 アルゴリズムの評価指標を見直す
今までは
評価指標として誤り回数そのものを用いていた
以降では
アルゴリズムの誤り回数を
最も成績の良かったエキスパートの誤り回数と比較することで
相対的に評価する
オンライン予測の分野で広く受け入れられている、リグレットの定義
REgretA(S)の第1項と第2項はそれぞれ、 アルゴリズムAの謝り回数の期待値、 および最も成績の良かったエキスパートの繰り返し回数
リグレットは、それらの差分として定義されている
従ってリグレットが小さいほど、 アルゴリズムは最優秀なエキスパートに匹敵する成績を収めたことを意味する
RegretA(T)は、総試行回数がTの時の、アルゴリズムAの悪いのリグレットを表す
これ以降本書ではオンライン予測の問題に対して
相対評価のコンセプトに基づいてリグレットを定義する
本書を通じて リグレット(RegretA(S)やRegretA(T))を最小化することが、 アルゴリズム設計の目標となる
1.3.2 リグレットの意味について
全ての思考が終わった後で最優秀エキスパートi*が判明する
この時プレイヤーは
最初から最後までエキスパートi*の通りに答えていれば、誤り回数が上式で澄んだのにと後悔する
その後悔は自分の成績(上式)との差が大きいほど大きくなる
リグレットはこの後悔の大きさを定量化したものになる
一般に
プレイヤーの予測はその後の敵対者のデータ選択に影響を及ぼす可能性がある
例え、リグレットが小さいアルゴリズムであっても
最悪のケースでは、何も改善されない
その場合は「諦める」
すなわち、アルゴリズムの成績は不問にするという立場を取る
1.3.3 重みつき平均アルゴリズム
乱択2分法をほんの少しだけ変個数することで、リグレットの小さいアルゴリズムが得られる
乱択2分法の表現を見直す
試行t-1までの全ての問題に正解したエキスパートの数をWt
そのうち、試行tで答えを1と予測しているエキスパートの数をKtとした時
確率pt=Kt/Wtで、xt=1
確率1-ptで、xt=0
この時WtとKtは、指示変数(上式)を用いて
上式のように表せる
従って上式は、 各エキスパートiにwt,i/Wかで重みづけを行った時の、 エキスパートの予測zt,iの重み月平均となる
環境から正解ytが提示された時、 指示変数は定数β=0を用いて上式のように更新できる
定数βを、0ではなく0<β<1の適当な値をとるパラメータとすると
リグレットが小さいアルゴリズムが得られる
指示変数の更新式を上式で記述する
WAAはptを出力とし
「Pr(xt=1)=ptを満たすxt∈{0,1}をランダムに選び、これを答えて出力する」という後処理のぶぶなんを省力している
実際、WAAの試行tにおける誤り確率はPr(xt≠yt)=|yt-pt|となる
Yt∈{0,1}の場合わけで簡単に確かめられる
全思考における誤り回数の期待値は上式となる
Xtを用いなくともリグレットを評価できる
アルゴリズム
WAAの性能
WAAの誤り回数の期待値の上界を与えるもの
WAAが「最優秀エキスパートの成績に匹敵する」という目標をある程度達成できていることを示す
WAAの等価な別バージョンのアルゴリズム
wt,iの代わりに、規格化された重みw’t,i=wt,i/Wtを保持・更新するもの
詳細のアルゴリズム
1.3.4 改良版重みつき平均アルゴリズム c-WAA
乱択2分歩法をc乱択2分法に拡張した時と同様に
WAAにも変換関数fcを適用することで、性能が改善されたアルゴリズムx-WAAが得られる
C-WAAはアルゴリズム1.4の3行目の代わりに上式を用いる
C乱択2分法の性能評価を行った時と全く同じでc=WAAにおいては上式となる
これを定数bcを用いてbc-qtで上から抑えることにより、c-WAAの誤り回数の期待値の上界を得る
この上界はbcが大きいほど小さくなるので、bcを最大にするcを選ぶことにより、最適なc-WAAが得られる
この結果をまとめた定理
1.3.5 パラメータ β の選択と WAA のリグレット上界の導出
WAAのリグレット上界を導出する
1.3.6 βの自動調整—ダブリング・トリック
1.4 エキスパート統合問題
はじめに
これまでエキスパート統合問題の一例として、N人のクイズ王の問題を取り上げた
ここから、この問題を拡張したエキスパート統合問題について考える
エキスパート統合問題は、3つ組(X,Y,ℓ)によって定義される
XとYは集合
予測値の集合、結果値の集合
ℓはXxYから[0, ∞]への関数
損失関数
エキスパート統合問題(X,Y,ℓ)は、 プレイヤーと敵対者との間のプロトコルとして 上記のように記述される
1.4.1 N 人のクイズ王の問題
1.4.2 オンライン配分問題
1.4.3 重みつき平均アルゴリズム
1.4.4 対数損失と情報圧縮
1.5 重みと損失関数による定式化
1.5.1 エキスパート統合問題の標準形
1.5.2 オンライン配分問題とヘッジアルゴリズム
1.5.3 重みと損失関数による定式化
1.5.4 第2章への準備
1.6 文献ノート

第 2 章 オンライン凸最適化

はじめに

オンライン凸最適化(online convex optimization)とは
様々なオンライン予測問題を抽象化し
統一的に扱うための問題の枠組み

2.1 オンライン凸最適化の枠組み

オンライン凸最適化問題は 以下によって定義される
凸集合Xと
事例空間と呼ぶ
X上の凸関数の集合F⊂{f:X→ℝ|fは凸)の組み(X,F)
オンライン凸最適化問題はプレイヤーと敵対者との間の プロトコルとして上記のように記述される
凸関数ftは明示的に敵対者からプレイヤーに与えられるものと仮定する
つまり、関数値ft(xt)だけでなく
関数ftそのものが与えられる
従って
任意のx∈Xについて
ft(x)がわかるだけでなく
関数ftの勾配∇ft(x)や劣勾配、へし餡なども計算できる
この過程は完全情報設定(full information setting)と呼ばれる
プレイヤーの目標はリグレット(regret)を最小化すること
オンライン凸最適化問題に対するリグレット
プロトコルのイメージ
一方
関数ftの情報が与えられず
関数値ft(xt)脳部位与えられる状況を バンディッド設定(banditsetting)と呼ぶ

2.2 FollowTheLeader(FTL)戦略

2.2.1 FTL戦略の有効性
2.2.2 FTL戦略の限界

2.3 FollowTheRegularizedLeader(FTRL)戦略

2.3.1 損失関数が線形の場合
2.3.2 オンライン線形最適化問題への帰着
2.3.3 オンライン勾配降下法
2.3.4 ブレグマン・ダイバージェンス
2.3.5 FTRL戦略の一般化
2.3.6 オンライン線形最適化問題に対するリグレット下界
2.3.7 損失関数が強凸である場合

2.4 オンラインニュートン法と Follow The Approximate Leader 戦略

2.4.1 オンラインニュートン法(ONS)
2.4.2 FollowTheApproximateLeader(FTAL)戦略

2.5 オフライン最適化への応用
2.6 文献ノート

第 3 章 ランダムネスに基づくオンライン予測

はじめに

ランダムネスを利用したオンライン予測について述べる

3.1 FollowthePerturbedLeader(FPL)戦略

前章では、 FTL戦略、FTRL戦略といった貪欲戦略、 正値付きの貪欲戦略の性質を議論
リグレットの上界を保証するような戦略は他にないのか?
Follow the Perturbed Leader(FPL)戦略は これまでの戦略とは全く異なる
FPLはFTRLと同様にFTLの一種の拡張になる
FTRLを考える時は正則性を用いた
FPLはその代わりにランダムなノイズを 目的関数に足し合わせて貪欲戦略を用いる
FPLアルゴリズム
FPL戦略のリグレット上界

3.2 指数重み型FollowThePerturbedLeader(FPL*)戦略
3.3 FTRL戦略との関連性
3.4 文献ノート

第 4 章 組合せ論的オンライン予測

はじめに
決定空間が何らかの組み合わせ集合や離散構造の集合である場合に 効率的なオンライン学習にいて述べる
4.1 組合せ論的オンライン予測とは
組み合わせ論的オンライン予測問題で 扱う組み合わせ集合の例
エキスパート
エキスパート問題も組み合わせ論的オンライン予測とみなせる
N個の要素から一つを選択するという組み合わせ全体が決定空間
集合の大きさはn
K集合
N個の要素からk個選ぶ組み合わせ全体からなる集合
複数の広告選択の問題はk-集合上のオンライン予測とみなせる
集合の大きさはO(nk)となる
順列
N個の要素の順列からなる集合
順列は、ランキング問題、割り当て問題、スケジューリング問題におけるオンライン予測問題で用いられる
集合の大きさはn!=Ω((n/e)n)となる
パス
パス集合とは、固定のグラフと始点、終点が与えられた時、 始点から終点までのパスの集合全体
オンライン最短経路で用いられる
集合の大きさは、一般にグラフの大きさに対して指数サイズとなる
ナイーブに書く組み合わせをエキスパートとみなして ヘッジアルゴリズムを適用すると
最悪で各試行にし数時間の計算がかかる
組み合わせ論的オンライン問題では
指数的にサイズの大きい決定空間でも 多項式で動作するオンライン予測アルゴリズム を設計することが重要になる
前提として組み合わせ集合が ベクトル集合で表現できると仮定する
決定空間Cはn次元ユークリッド空間の部分集合、C⊂ℝnとする
前述の例でのベクトル集合表現
エキスパート(n=4)
K-集合(n=4,k=2)
順列(n=3)
順列(行列表現)
パス(左図の場合の視点から終点までの経路)
有向グラフ
組み合わせ集合をベクトル集合とみなすことにより
オンライン凸最適化問題と同様に定式化できる
組み合わせ論的オンライン予測問題の定義
本章では簡単のため、 オンライン線形最適化問題(損失関数が線形のばあい)のみを考える
次節以降で、組み合わせ集合に対する、効率的なオンライン予測手法のアプローチを述べる
4.2 サンプリングに基づくアプローチ
まず、サンプリングに基づくアプローチを述べる
4.3 オフライン線形最適化に基づくアプローチ
4.4 連続緩和と離散化に基づくアプローチ
4.5 文献ノート

付録 A 数学的準備

A.1 内積，半正定値行列
A.2 ノルム
A.3 凸集合，凸関数
A.4 凸最適化
A.5 確率に関する不等式