ノンパラメトリックバウンドについて情報理工学系研究科数理情報学専攻数理第四研究室博士三年指導教員：駒木文保准教授鈴木大慈 2008年8月14日 1 発表の流れ • 経験過程の一般論 – ドンスカークラスの十分条件 – 凸コスト最小化におけるノンパラメトリックバウンド – Tsybakovの低雑音条件 2 経験過程の理論（一様大数の法則，一様中心極限定理） 3 大数の法則 a.s. 0 中心極限定理分布収束正規分布 4 d個の関数大数の法則 0 多変量中心極限定理多変量正規分布 123 ‥ d 5 無限(個)の関数一様大数の法則 0 一様中心極限定理上上の分布として分布収束ガウシアンプロセス 6 例：一様大数の法則 • 対数尤度関数 7 例：一様中心極限定理 • 経験累積分布関数 :真のCDF :経験CDF 一様分布経験過程 (Kolmogorov-Smirnov検定) 8 • 以降，一様中心極限定理が成り立つ関数族を考える． ※ 一様中心極限定理 → 一様大数の法則 • (P-)ドンスカークラス – 一様中心極限定理が成り立つ関数集合 9 ドンスカーの必要十分条件１．有限個の元を任意に持ってきて，その経験過程がある正規分布に収束する．２．有限個の元でF をうまく近似できる（漸近等連続性⇔漸近タイト） θ1 θ2 θ3 θ4 ‥ θk 有限個の元を増やしてゆくと間が連続的につながる 10 ２．の十分条件関数集合： • 準備：関数集合の複雑さ ε-カバリングナンバー :ノルムd によるε-ボールでを覆うのに必要な最小のボールの個数 ε-ブラケッティングナンバーと出来るような最小のK 11 ２．の十分条件関数集合： • 一様エントロピー条件有限離散確率測度の中でsupとるまたは Dudley積分という 12 カバリングナンバーの例 • d 次元，有界 • VC次元 V，有界それのconvex hull 13 カバリング/ ブラケッティングナンバーの例 •ガウスカーネルにより生成されるRKHSの単位球（d次元，コンパクト集合上） [Steinwart, Scovel: A.S. 2005] •ソボレフ空間の単位球：α階連続微分可能なd次元実数空間上の関数次元が高いほど複雑，滑らかなほど単純 14 一様なバウンド関数集合Fの部分集合で二乗ノルムがδ以下の集合ブラケットでも似たような不等式が成り立つの場合 15 Dudley積分について ※ カバリングナンバーは関数集合の複雑さを表す．関数集合F を有限個の元で近似するのに必要な個数を表している．積分は解像度を上げてゆくことに対応．同じε-ボールの中に入っている元は高々 2εの距離にある． 16 Dudley積分の雰囲気をつかむ • Hoeffdingの不等式 →一様カバリングナンバー：独立で期待値0の確率変数 s.t. • Bernsteinの不等式 →ブラケッティングナンバー：独立で期待値0の確率変数 s.t. ただし， 17 Maximal-Inequality1 • Hoeffdingの不等式に対するMaximal-Ineq. 有限個の関数集合：どれも期待値０ Maximal Inequality これを，解像度を細かくしていって積分（チェイニング）したのがDudley積分 18 Maximal-Inequality2 • Bernsteinの不等式に対するMaximal-Ineq. 有限個の関数集合：どれも期待値０ Maximal Inequality 19 バウンドを出してみる 20 設定 • 凸コスト最小化：正則化項なしロス関数lの条件： • リプシッツ連続 • Modulus of convexity 21 ：最適解関数集合の条件 1. 一様有界 2. 多項式複雑さとするとリプシッツ連続性より Modulus of convexity 22 ≦0 Talagrand’s Concentration Inequality 一様バウンド 23 Tsybakovの低雑音条件 24 Tsybakovの低雑音条件：入力変数の空間：出力変数の空間：X,Y上の確率分布 Tsybakovの低雑音条件 (Noise Exponent α) としておく [Tsybakov: 2004, A.S.] 25 二値判別・経験誤差最小化 N個のサンプル用いる判別機の集合（モデル）経験リスク経験リスク最小化真のリスク (誤り確率) 真の最適解 :モデルFの複雑さはρ (0≦ ρ ≦ 1) :真の解はモデルに含まれている 26 低雑音条件における汎化誤差経験リスク最小化元の真のリスク ≦0 経験過程の理論しかし Tsybakovの低雑音条件のもとでは Fast Learning Rate より速い [Tsybakov: 2004, A.S.] 27 論理の概要 Tsybakovの低雑音条件：リスクが低いなら，真との距離も近い一様なバウンドならばすると高い確率で一様バウンドの最適性から同じ論理を繰り返すと（cf:Talagrand’s Concentration Inequality）不動点 28 これらを別々に扱ってはいけない．近いものは似た振る舞いをする． 29 終了 30