Statistical Learning theory (SLT) の授業をドイツの大学院で取っていて、試験に向けて準備するために、自分の疑問と興味をもとに部分的に調べていく記録です。
漠然と知っていること、知りたいこと、興味
Markov inequalityからChebychef inequalityという便利なconcentration inequalityが導入できる。Chebychef inequalityは便利で、例えば、the weak law of large numbersを証明できる。また、Chebychef inequalityの上位互換のChernoff inequalityというものに拡張でき、もっと高次の何かしら定理を示すのにメリットがあるそう。まだ、詳しくは学習していない。
また、重要そうな概念として、Hoeffding's inequalityやMcDiarmid's inequalityがあるらしい。それらを利用することで、Radermacher complexityという概念を導入でき、これがSLTの深淵のロスをいくつかの項目に分解することに役立ち、例えば、ニューラルネットなどの汎化性能などの理論的解析に役立つらしい。このあたりは、何回かに小分けしてブログ記事で、自分の疑問ドリブンで調べながら書いていきます。
また、ロスというのはいくつか種類があり、それぞれ特性がある。（例えば、真のロスは誰にもわからない。）それによって、いろいろな数学のトリックなどが展開されていくようだ。
個人的にSLTはニューラルネット等の理論的解析に便利というのは聞いたことがあるが、自分はMulti-armed banditなどの分野の研究を今後していく可能性がたかく、そこではregret boundというものを示さなければ、レビュワーから叱責されるという文化があるらしい。そのregret boundの導出にも、SLTと関連したconcentration inequalityが頻出するとの噂を聞いた。モチベーションを高めるために、ときおり、実際の論文でどう使われているかとかも切り取ってみてみたい。あと、授業でそのうち扱われるPACベイズとかも気になる。Probably Approximately Correct (PAC) とはなんやねん、関西人の「知らんけど」みたいなノリを感じ、いまキーボードの前でツッコミをしてしまった。
SLT各概念の依存関係ロードマップ
自分は基本的に数学は得意ではないのですが、何が数学の学習を難しくするかなぜか最近考えていました。数学は、かなりボトムアップの文化があります。教科書のはじめに謎のツールを学ばさせられ、後半で何か高度なことを学習するために必要であることが判明します。これは、何をやっているのかわからずやる気がなくなります。自分はトップダウンで目的意識がないとやる気スイッチを押せないので、これはクリティカルです。そして、数学はすべての概念が他の概念と連結しています。なので、おそらく結論として重要な概念があるのだろうが、それがわかりにくい。とりあえず、各コンポーネントの依存関係をDirected Acyclic GraphとしてGeminiに作ってもらった。
現時点で興味深いのはMcDiarmidt's inequalityなので、そこからみてみると、やはり、Hoeffding's inequalityへの依存関係があることがわかった。
1: Hoeffding は McDiarmidの特別なケース。それはほんまか？
McDirmdt inequalityを紹介すると以下：
$Z_1, \dots, Z_n$ be independent random variables taking values in some set $A$. Under the bounded difference assumption, it holds, for all $t > 0$,
$$\mathbb{P}(f(Z_1, \dots, Z_n) - \mathbb{E}f(Z_1, \dots, Z_n) \ge t) \le e^{-2t^2 / \sum_{i=1}^n c_i^2}.$$
Bounded difference assumption (後述)というものを前提として、Hoeffding's inequalityをさらに一般化したものが、McDimiardt inequalityのようだ。
パット見、どれだけ形が異なるのか。そして、それは定性的に何を意味するのか？
Hoeffding inequality (Hoeffding lemmaとは違う) を並べると、右expの中身が、McDiarmdt inequalityと似ているが微妙に違う。$\bar{Z}$ が平均であることが重要。
$$\mathbb{P}(\bar{Z} - \mathbb{E}\bar{Z} \geq t) \leq e^{-2t^2n^2 / \sum_{i=1}^{n}(b_i-a_i)^2}.$$
McDiarmid's inequalityの指数部分 $-2t^2 / \sum_{i=1}^n c_i^2$ に対して、 Hoeffding's inequlaityの指数部分 $-2t^2n^2 / \sum_{i=1}^{n}(b_i-a_i)^2$ では、分母に$n^2$が追加され、分子の$c_i$が$(b_i-a_i)$になっているのが違う。
Hoeffding's ineqaulityでの前提は、$Z_i$ i.i.d.で以下だった： $$\mathbb{P}(a_i \leq Z_i \leq b_i) = 1.$$
次に、MiDiarmdtのBounded asssumptionを見てみると以下：
Assumption 14 (BOUNDED DIFFERENCE ASSUMPTION). Let $A$ be some set; a function $f : A^n \rightarrow \mathbb{R}$ satisfies the bounded difference assumption, if there exist real numbers $c_1, \dots, c_n > 0$ so that for all $i = 1, \dots, n$,
$$\sup_{z_1, \dots, z_n, z_i' \in A} |f(z_1, \dots, z_n) - f(z_1, \dots, z_{i-1}, z_i', z_{i+1}, \dots, z_n)| \leq c_i.$$
$n$は複数の$f$に入れる確率変数たちの数であって、直感的には、Hoeffdingにそれがなくて、McDにあるのかと思ったが違うのか。実際はMcDにnはなく、Hoeffにnが存在する。
これは、Hoeffding inequalityの証明で、Chrnoff inequalityを用いて導出するときに、$\bar{Z}$を実際の平均として展開するときに、$1/n$の部分が出てくることに由来する。このHoeffding's inequalityの平均の操作が、McDiarmidt's inequalityの一般の関数$f$の特殊なケースであることがわかる。このことは、教科書にも"Concentration of sums of bounded i.i.d. random variables"と書かれていることからも推察できある。
この感覚で、再度HoefffdingとMcDiarmditのbounded assumptionを見ると、以下のような対比ができる：
- Hoeffdingの前提: $Z_i$が$[a_i, b_i]$に挟まれている。
- McDirmidtの前提:似たように関数$f$の入力値のひとつを変えたとしても、その関数としての最大(sup)の変化量が$c_i$におさまる。
この２つ目の前提は、Lipcitz連続性と関わっていることが授業で言われていました。
Lipcitz 連続とは$f: \mathbb{R} \to \mathbb{R}$ での任意の $x, y$で以下がなりたつこと：
$$|f(x) - f(y)| \le L \cdot |x - y|$$
これをMcDirmidtの設定に置き換えると、もともとの入力ベクトルと、一つの要素をかえただけの入力ベクトルについて、ハミング距離で以下のような表現ができるらしい:
$$|f(\mathbf{z}) - f(\mathbf{z'})| \le c_i \cdot d_H(\mathbf{z}, \mathbf{z'})$$
このMcDiarmidtの件は、stability conditionとも呼ばれているらしい。
今回の学び
Hoeffding vs McDiarmidの結論と仮定を比べると、前者を一般化したものが後者であることが直感的に理解できた。また、この後者のbounded difference assumptionが、直感的には関数のLipcits連続性と関わっている事がわかった。
次回
次はMcDiarmidt inequalityを使って得られる、この授業な主な結論について、ノートを書いてみたいと思います。あとは、Rademacher complexityに付いて勉強して、わからないことを次の記事に書きます。
PS
学習理論の内容が自分にどれだけ関わるのか知るために、bandit理論解析と今回の２つの不等式を検索してみてたら、普通に学習理論の内容が氷山の一角として出てくるようだ。ここに到達するまで何年かかることやら。そのころに自分はどうなっているのだろうか。2026最もホットなスキルは忍耐と根気か。。どうか、このセメスターは諦めずに頑張れますように。
References
RPTU ML3 (Learning Theory) Lecture notes from Prof. Marius Kloft