はじめに
前回の記事では, 仮説集合が有限である場合の, 仮説の予測損失の上界をHoeffding's ineqを用いて導きました. しかし, 無限仮説集合に対しては同様の方法で実用的な上界を得ることは不可能でした. したがって, 今回は無限仮説集合に対応する方法の一つであるRademacher Complexityを用いて予測損失の上界を導いてみようと思います.
目次
定式化のおさらい
統計的学習理論のモチベーションをおさらいします. 前回記事をお読みいただいている方は読み飛ばしていただいても結構です.
入力空間に値をとる確率変数を, 入力空間から出力空間への写像をとしてlabeling functionと呼びます.
また, 入力が従う確率分布をとします ().
損失関数としてを用いるとします.
このとき, ある仮説の予測損失は次のように定義されます.
つまり, 分布における予測値の損失の期待値です.
をできるだけ小さくするような仮説を見つけ出すことが機械学習の目標です.
ここで, データの真の分布は未知であることが問題であり, 有限の観測データから, 予測損失をできるだけ小さくする仮説を導く必要がありました.
予測損失を観測データから評価する上で最も大きな手がかりは経験損失です. データ が観測されたときの経験損失は次のように定義されます.
ここで, はデータの経験分布です.
また, 仮説集合に含まれる仮説の中で予測損失と経験損失を最小化するような仮説をそれぞれ , と表していました.
ここで私たちが導きたいのは, 観測データから計算できる経験損失を最小化する基準で得られる仮説の期待損失と
仮説集合を用いたときに達成され得る最小の期待損失の差を次のように評価することです.
少なくともの確率で次の不等式が成り立つ.
以降の目標は, 仮説集合のcomplexity項とに依存するconfidence項を具体的に求めることです.
Rademacher Complexity
Rademacher Complexityの導入
何度か名前が出てきていますが, 実数値関数の集合の複雑さの指標として解釈されるEmpirical Rademacher ComplexityとRademacher Complexityを定義します.
さらに, それぞれのサンプルはある分布に独立に従う() とき, 次のRademacher Complexityを定義します.
Rademacher variables はとは独立にサンプルされます. よって, 入力点とそれに対するランダムなラベル付けを 最大でどれくらい予測できてしまう関数を含むか?を測っていると解釈できます. 入力集合とはなんら無関係なランダムノイズの組みに対してよくfittingできてしまうほど, は複雑である, ということです.
Rademacher Complexityの推定
さて, 定義よりRademacher ComplexityはEmpirical Rademacher Complaxityをデータ集合について期待値をとったものでした. しかし, ある入力点のサンプル集合が与えられたとき, Empirical Rademacher Complexityは必ずしもRademacher Complexityに一致するとは限りません. よって, Rademacher Complexityの推定誤差の裾確率を評価することで, 誤差の大きさを見積もってみようと思います.
導出
とおきます.
このとき,
ここでは, 関数の値域がであることとと, であることを用いました.
これにて, 関数がこちらの記事で導出したMacDiamid's ineqのboundedness conditonを満たすことがわかります.
したがって, MacDiamid's ineqでとおくと, 任意のに対して, 次の不等式が成り立つことがわかります.
ここで, 左辺をとおくと,
です. よって,
ですので, 所望の不等式を得ます.
Uniform law of large numbers
さて, 前章でRademacher Complexityを導入しました. 本章では, これを用いて次のUniform law of large numbersを導きます.
導出
まず,
と置きます. ここで先ほど同様にに対してMacDiamid's ineqを適用します.
より, はboundedness conditionを満たすので, 少なくともの確率で, 次の不等式が成り立ちます.
ここで, としました.
次に, 今導いた不等式の右辺の第1項をRademacher Complexityを用いて評価します.
ここで, とは同一分布に従います. また, は+1と-1を等確率でとるRademacher variableです.
このとき, とは同一分布に従います. よって,
これらの結果を合わせると, 少なくともの確率で次の不等式が成り立ちます.
さらに, 前章の (Rademacher Complexity vs Empirical Rademacher Complexity) の結果を用いると, 少なくともの確率で次の不等式が成り立ちます.
以上の結果を統合し, union boundを用いることで, 少なくともの確率で次の不等式が成り立つことを得ます.
損失を用いた時の予測損失の上界
さてようやく本題です. ここでは, 次にように表される損失を用いたときの, 予測損失の確率的上界を導出します. で, また損失は定数でboundされるとします.
ここで, 損失と仮説の合成関数の集合のEmpirical Rademacher Complexityを仮説集合のEmpirical Rademacher Complexityで評価します.
まず, 先ほどの集合を関数と集合を用いて,
と表しておきます. 関数は, -Lipschitzなので, Talagrand's lemma*1を用いると,
が成り立ちます. また,
したがって, 結局のところ
なので, 損失と仮説集合の合成関数の集合のEmpirical Rademacher Complexityは, 仮説集合のEmpirical Rademacher Complexityで上から評価できます.
この事実と, Uniform law of large numbersにおいて, をとすれば, 任意の仮説に対して,
少なくともの確率で次の不等式が成り立ちます.
この不等式を用いれば, 少なくともの確率で次の不等式が成り立つことを導くことができます.
したがって, 所望の確率的上界を次のように得ることができました.
さいごに
本記事では, 損失を用いた場合の予測損失の確率的上界をRademacher Complexityを用いて導出してみました. 相変わらず, 私の誤解で誤った記述をしている可能性が大いにありますので, 見つけた場合はご指摘いただけたら幸いです.
参考
[金森 (2015)] 金森敬文. 2015. 統計的学習理論. 講談社 機械学習プロフェッショナルシリーズ.
[Mohri et al. (2012)] Mohri, M.; Rostamizadeh, A.; and Talwalkar, A. 2012. Foundations of Machine Learning. MIT Press.
*1:Mohri et al. (2012)のlemma 4.2