``Exponentiated Gradient Algorithms for Log-Linear Structured Prediction’’ A.Globerson, T.Y.Koo, X.Carreras, M.Collins を読んで 渡辺一帆（東大・新領域）
構成 １．Introduction ２．Primal and Dual Problems for Log-Linear Models（モデルと主、双対問題） ３．Exponentiated Gradient Algorithms（Kivinen & Warmuth, 1997）（アルゴリズム） ４．Convergence Results （収束性の証明） 4.1 Divergence Measures 4.2 Convergence of the Batch Algorithm 4.3 Convergence of the Online Algorithm 4.4 Convergence Rate of the Batch Algorithm 4.5 Convergence for Max-Margin Learning 5. Structured Prediction with LLEG (ラベルが構造を持つ場合) 6. Related Work 7. Experiments（多クラス分類と係り受け解析で実験） 8. Conclusion この辺りがメイン
対数線形モデル（2節） （条件付き）対数線形モデル 入力 ラベル (xに依存しても良い) 時系列、木などの内部構造をもつ高次元データ 特徴ベクトル を用意 （条件付き）対数線形モデル :パラメータ ○ の分類は ○ ロジスティック回帰モデルを含む
主問題と双対問題（2節） 学習データ 正則化された対数尤度を最大化 主問題 とおく 双対問題 制約： 各 は確率分布 （ ） （ と書く）
導出 とおく （等号は のとき） これを に代入してQを得る
Exponentiated Gradient（３節） Exponentiated Gradient Algorithm (Kivinen and Warmuth, 1997) を により更新 ：学習係数 オンラインだと とする 双対問題のQだと
ダイバージェンス（4.1節） 間のダイバージェンス KL-ダイバージェンス Bregman ダイバージェンス マハラノビス距離 ：凸関数
収束性の証明（4.2節） Lemma 1 Lemma 2 ○ オンラインも同様に証明可能 （4.3節） は任意の凸関数（具体的な形にはよらない） のようにηをとれば EGの更新で は単調減少する 双対問題のQだと Lemma 2 ととれば (略証) となることを使う ○ オンラインも同様に証明可能 （4.3節）
収束の速さ（4.4節） Lemma 4 (Kivinen & Warmuth, 1997) Lemma 2 任意の に対し、 Lemma 2 t=1,…Tの和をとり Qが単調減少することから （最適解）とすると とするには ○ Max-Marginの場合（ のとき）も同様 （4.5節）
構造があるとき（5節） ラベル はパーツ の集合だとする :パーツ全体 のように分解できるとする の代わりに を使う パーツの個数だけ はパーツ の集合だとする :パーツ全体 のように分解できるとする の代わりに を使う パーツの個数だけ 変換は で更新できる。 （EGでの はyに含まれるrに関する項のみきいてくるので）
実験（7節） 多クラス分類 構造がある場合（係り受け解析） この例では（たまたま） EG(primal)も単調増加（しかも速い） 目的関数の値 分類精度 共役勾配法、L-BFGSと比較 計算時間 計算時間 構造がある場合（係り受け解析） 目的関数の値 解析精度 特徴ベクトル を単語のペア に与える 計算時間 計算時間
結論 対数線形モデルに対し最適解への収束が保証されたアルゴリズムを提案 証明のほとんどはBregmanダイバージェンスとKLダイバージェンスの間の関係に因る 他の関数Qについても同様の解析が可能であると期待される オンラインアルゴリズムについても1/Tの収束の速さを証明するのは今後の課題