はじめに
Foundation of Machine Learning のSanovの定理を読んでいる際に、躓いた部分があるので、それの備忘録。
結論：パラメータの範囲に気をつける！
定理の主張（誤植ver）
$X_1, \ldots, X_n$を独立同分布で、$[0, 1]$に値を取る確率変数とし$E[X_1] = q$とする。また、$\hat{X} = 1/m \sum_{i=1}^{n}p_i$とする。このとき、任意の$p \in [0, 1]$に対して、
\begin{align}
P[\hat{X} \geq p] \leq e^{-m KL(p || q)}
\end{align}が成り立つ。(Foundation of Machine Learning より)
どこがおかしい？
証明では任意パラメータ$t > 0$を導入して、Chernoff限界を用いて上界を求めているが、最後の$t$での最適化を行うときに、
$$ t = \log \frac{(1-q)p}{q(1-p)} $$
という形が出てくる。このとき、$t$の範囲から、
\begin{align}
\log \frac{(1-q)p}{q(1-p)} > 0 \
\Leftrightarrow \ q > p
\end{align}
となる。なので、定理が成り立つような$p$の範囲は$q > p$である。
編集後記
- 「p = 0入れたら左辺＝1になるから、成り立たんやん。。。」と思ってずっと悩んでいたが、わかってしまえば単純な落とし穴だった。
- Sanovの定理は、調べてみるともっと複雑な記述が見られて大変そうだった。
- chatGPTとのやり取りが、面白かったので一部抜粋
自分：「X_iの値域が[0, 1]だから、\hat{X}も[0, 1]なわけで、左辺の確率は絶対に1になるはず。それなのに、右辺は1以下になってる。これはどういうこと？」
GPT：（一部抜粋）「p=0 の場合の解釈
今回の場合、p=0 においては、確率 $P[\hat{X} \geq 0]=1$ であるのに対して、右辺の式が $(1−q)^m$ であり、これが 1 未満になる場合があります。しかし、これは単に右辺が上界であり、左辺が常にこれより小さいことを示しているに過ぎません。
つまり、不等式の形自体は問題なく、右辺が 1 よりも小さい場合もあくまで「上界」としての役割を果たしているのです。これは以下のようにまとめられます。
- 左辺: 実際の確率、今回の場合は 1（特に p=0では）。
- 右辺: 上界を提供するもの。たとえこの上界が 1 より小さくなったとしても、これはあくまで保証としての役割を果たしています。
結論
不等式は「任意の p に対して確率の上界を与える」ためのものであり、p=0 において右辺が 1 以下になることは、不等式の構造上の矛盾を示すものではありません。むしろ、上界として期待される挙動を示していると言えます。」
徹夜明けとかだったら、納得してしまいそう笑
コメント