Twitterで見かけた問題

先日、こんな問題を見かけました ([1], 元ツイートは2010年)。

“子どもが二人いる。（少なくとも）一人は男で火曜日に生まれた。二人とも男である確率は？（「火曜日に」を聞かなかった場合の確率も求めてください）”

条件つき確率の問題でして、個人的にはいい問題だなーと感じました。

で、率直にいうと答えは

• 「火曜日に」という情報を聞かなかった場合は 1/3
• 「火曜日に」という情報を聞いた場合は 13/27 (=0.48148…)

です。

図を見て3秒で理解する

ところが、とくに13/27という数字は、仮に条件つき確率の定義を知識として知っていたとしても、全く自明でない印象を受けてしまいます。
13とか27とかマジで？という感じ。

実際に計算して確認しようとすると3分くらいかかるのですが、願わくばもっと短時間で、何が起きているのか理解したいです。3秒くらいで。

というわけで、3秒で理解するための図を作りました。こちらです。

図では、AさんとBさんの性別と誕生日の曜日をタテヨコに並べてあります。2人分の性別と誕生日の組み合わせなので、14 * 14 = 196マスあります。
今、「一方は火曜日に生まれた男である」という情報を聞いたので、そうでないマスを黒く塗りつぶすと27マスだけ残ります。その中で、二人とも男であるのは赤く塗った13マスなので、13/27という数字が出てきます。

概要

Wasserstein距離がKLダイバージェンスで抑えられるという不等式のことを輸送不等式というのでした。例えば距離空間$(X, d)$上の確率測度$\mu$が$T_1(C)$を満たすというのは、任意の確率測度$\nu$に対して
$$
W_1(\mu, \nu) \leq \sqrt{C D_{KL} (\mu, \nu)}
\tag{1}
$$
が成り立つことをいいます。

$f: X \to \mathbb{R}$がLipschitz関数のとき、
$$
\forall t > 0, \quad \Pr [ f - \mathbb{E}f \geq t] \leq \exp \left( - \frac{C t^2}{2 \lVert f \rVert_{Lip}^2} \right)
\tag{2}
$$
が成り立つという性質を考えます。言葉でいえば「すべてのLipschitz関数の像がsub-Gaussianのように振る舞う」ということです。このような性質をGaussian concentrationと呼びます。

実は、(1)ならば(2)が成り立ちます。

機械学習系分野ではどう役立っているか

学習理論やランダム行列論などでは、Gaussian concentrationはとてもありがたい性質です。最終的なアプリケーションで欲しいのは、あくまで(2)の形の集中不等式なのですが、そうだとしても(1)の形で集中不等式の情報を保持していた方が何かと便利な場合があります。

例えば、学習理論では、独立同分布に従うデータについての対数尤度や経験リスクがどう振る舞うかということに興味があるわけですが、要素技術としては「単体で(2)を満たすような確率分布の$n$個の直積が再び(2)を満たすかどうか」を考える必要が出てきます。そのとき、少なくとも(1)の形の不等式は直積操作で保存されるということがわかっているので都合が良いです。集中不等式界隈（？）では、こういう性質を不等式のテンソル化 (tensorization) と呼びます。

前提

Generic chainingのタイトさを個人的に理解するためのノートの3つめ。

• その1
• その2

実は、とてもわかりやすい資料[1]を発見したため、あまり自分でリライトする意味がなくなりつつある。でも一応自分の言葉でまとめておく。

$X_t$は平均0の$d$-sub-Gaussian processとする。つまり、増分がsub-Gaussianであるような確率過程とする：
$$
\Pr(| X_s - X_t| \geq u) \leq 2 \exp \left( - \frac{u^2}{2d(s,t)^2}\right).
\tag{1}
$$
下つきの添字がスペース上の都合で書きにくいときは$X_t = X(t)$とも書く。

特に、$X_t$がガウス過程のときは、距離$d$として、$X_t$から定まる内在的な距離
$$
d(s, t) = \sqrt{\mathbb{E}(X_t - X_t)^2}
$$
を用いればよい。

平均0なので、$t_0 \in T$を固定すれば
$$
\mathbb{E}\sup_t X(t) = \mathbb{E}\sup_t (X(t) - X(t_0))
$$
が成り立つ。左辺に興味がある場合も、右辺を考えた方が今は都合がよい。$Y = \sup_t (X(t) - X(t_0))$は非負なので、
$$
\mathbb{E} Y = \int_0^\infty \Pr(Y \geq u) \dd u
$$
が成り立つ。

ひとことまとめ

輸送不等式の双対表現がおもしろかったので。

輸送不等式

最適輸送 (optimal transport) というジャンルがある。元々どういう問題なのかは[1]などに譲るとするが、最適輸送で出てくる色々なツールが、他の問題を考えるときにも色々と有益だということが知られていて、確率論の別のジャンルでもしばしば使われる。

$(X, d)$を距離空間とする。$\mu, \nu$を$X$上の (Borel) 確率測度とする。$X^2$上の確率測度$\pi$で、軸方向への周辺分布がそれぞれ$\mu$と$\nu$に等しいようなものをカップリングという。

カップリングは、「輸送計画」みたいなものに相当する。つまり、$X$という空間上にある$\mu$という山を切り崩して$\nu$という山に移し替えたい。どの部分を切り取ってどこに持っていくかということを表したものが$\pi$である。
ところが、山を切り崩して移動するというのをタダで行えるわけではない。$X$上の点$x_1$から$x_2$に荷物を運ぶのに、$x_1$と$x_2$の距離が遠いほど多くコストがかかるかかるという状況を考える。沖縄などの地域で通販の送料が無料にならなかったりするのはそういう理由だろう（沖縄に住んでいらっしゃる方はすみません）。例えば、単位体積を$x_1$から$x_2$に運ぶのに、$d^p(x_1, x_2)$円かかるとする。このとき、全体での輸送コストは
$$
\int_{X^2} d^p(x_1, x_2) \dd \pi(x_1, x_2)
$$
のと書ける。このコストを最小化するように輸送計画を設計しようというのが、最適輸送という問題である。

上の最小値を
$$
\inf_\pi \int_{X^2} d^p(x_1, x_2) \dd \pi(x_1, x_2)
$$
とする。実は、輸送するためのコストが最小限いくらかかるかで、確率測度のあいだの距離が測れる。実際、
$$
W_p(\mu, \nu) := \left( \inf_\pi \int_{X^2} d^p(x_1, x_2) \dd \pi(x_1, x_2) \right)^{1/p}
$$
は距離になるが、これをWasserstein距離という（注1）。

$\mu$と$\nu$のKLダイバージェンスを$D(\mu, \nu)$と書く（定義は下）。この記事でいう輸送不等式というのは、次のようなものである：
任意の確率測度$\nu$に対して、不等式
$$
W_p^p(\mu, \nu) \leq \sqrt{C D(\mu, \nu)}
\tag{1}
$$
が成り立つとき、$\mu$は輸送不等式$T_p(C)$をみたすという。

連鎖 (Chaining)

前回の続き。

このノートの落とし所としては次のようなものを想定している：

• 確率過程の最大値をバウンドするためのchainingという技術がある
• chainingで得られるバウンドが非最適な場合がある
• generic chainingという技術を使うとそのギャップが埋まる

でも今回は、chainingについて書いたら力つきて終わりそうだ。

距離エントロピー

$(T, d)$ を擬距離空間とする。$d$ で $T$ の大きさをはかり、それが $T$ 上の確率過程の最大値に与える影響が知りたいのだった。

大きさのはかり方としてここで想定しているのは、

• 半径 $\epsilon$ の球が最低いくつあれば $T$ を覆うことができるか ($\epsilon$-netの最小数)
• 半径 $\epsilon$ の球を最大いくつ $T$ の中に押し込めるか ($\epsilon$-packingの最大数)

といったもので、前者を被覆数 (covering number)、後者をパッキング数 (packing number)という。

はじめに

学習理論や機械学習周辺を勉強していると、しばしば「確率過程の最大値」というものが出てくる。確率過程といっても色々あるものの、主に興味があるのは経験過程とその極限として出てくるガウス過程の2つだ。これらは、「リスクの挙動が知りたい」「M推定量の一致性が知りたい」といった統計的なモチベーションに関係してくる。

このノートでは、確率過程の最大値の測り方についての、比較的つっこんだ内容を数回に分けて書こうと思う。

ノートの趣旨

Generic chainingと呼ばれるものに関して知られている結果を、証明抜きで並べようと思う。

Generic chainingとは何をするためのものか

経験過程やガウス過程の最大値は、添え字の空間が大きすぎると暴れる。

平均0の確率過程 $(X_t)$ があるとき、添え字の空間には $(X_t)$ の相関構造をもとに擬距離が入る。ところがその距離の意味で添え字の空間が大きすぎると、$\sup_t |X_t|$ は発散してしまう。大きさの測り方はいろいろあるのだが、基本的には全有界性のようなものがコントロールされていることが望ましい。例えば、カバリングナンバー ($\epsilon$ を固定したときの $\epsilon$-netの要素数の最小値) が大きすぎないことが条件になる。

逆に、「添字空間の大きさを測る尺度」によって確率過程の最大値をタイトに評価できることが知られている。

そこでようやく表題の概念が出てくる。
ワンセンテンスで言えば、Generic chainingというのは、確率過程の最大値を添字空間の大きさを使って評価するやり方のなかで、とりわけ高級なものである。同目的のテクニックに連鎖 (chaining) という名前がついているものがまずあって、それをさらに一般化したものなのでこういう名前がついている。

結論の一部を先取りすると、距離の入った添字空間 $(T, d)$ の複雑さの尺度を、次のような量で測る：
$$
\gamma_2(T, d) := \inf \sup_{t \in T} \sum_{n=0}^\infty 2^{n/2} d(t, T_n)
$$
$T_n$ というのは $T$ の「代表点の集合」で、基本的には $n=0,1,\ldots$ とともに要素数が増えていく。だんだん解像度を上げていく感じだ。$T_n$ 要素数の増え方にはある程度制限がかかっていて、$\inf$ はそのような $T_n$ の全体にわたってとる。
このように定義した $\gamma_2$ という謎の量が、なぜかガウス過程のsupの性質をとてもよく捉えている。

これがしかしどの程度重要な概念かというと、言ってしまえばマニアックな知識だ。機械学習の論文を読む人間の95%にとって必要にならない程度だと思う。それでも、例えば昨年 (2015年) のNIPSにもそれ自体をテーマにした論文が通っていたりして、やっている人はやっている。つまり、この知識が必要になる残りの5%とは、学習理論をやっている人間のことである。

はじめに

Hexoでブログを生成した。MathJaxのプラグインもあるため、LaTeXの数式を労力なく書けそうだからである。

とはいえ、MathJaxでものを書くのは初めてだ。ここではHexoプラグインの導入方法と、MathJaxの記述方法についてまとめておく。（2016/3/22現在）

プラグイン導入

hexo-mathプラグインを利用することにした。

1

$ npm install hexo-math --save

でインストールし、Hexoプロジェクトの設定ファイル _config.yml に以下を記述する:

1
2
3
4
5
6
7
8

math:
  engine: 'mathjax'
  mathjax:
    src: http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML
    config:
      tex2jax:
        inlineMath: [ ['$','$'], ["\\(","\\)"] ]
        displayMath: [ ['$$','$$'], ["\\[","\\]"] ]

基本的な記述

行内数式はLaTeXと同様で $ f(x) = x^2 $のように書けばよい: $f(x)=x^2$.
別行立てで書くには $$ で挟んで書く。

1
2
3
4
5

$$
\mathbb{E} \max_{s,t\in S: d(s,t) \leq \delta} |X(t)-X(s)| \leq (16 \sqrt{2} + 2)
\int_0^\delta \sqrt{\log 2N(T, d, \varepsilon)} \mathrm{d}\varepsilon
\tag{999}
$$

$$
\mathbb{E} \max_{s,t\in S: d(s,t) \leq \delta} |X(t)-X(s)| \leq (16 \sqrt{2} + 2)
\int_0^\delta \sqrt{\log 2N(T, d, \varepsilon)} \mathrm{d}\varepsilon
\tag{999}
$$

なるほどなあ。むしろ、何ができないのか試したくて\mathbb{E}などを試したのだが、普通に使えるようなのでありがたい。これで$\mathbb{R}$とか$\mathbb{Z}$なども使い放題である。その他に使えるLaTeXコマンドの一覧はMathJaxのドキュメントに載っている。

マクロ

MathJaxではマクロも定義できるが、今回は必要に応じて次のように書けばよい。YAMLなせいか心持ちすっきりと書けている気がする。

1
2
3
4
5
6
7
8
9
10
11
12
13

math:
  engine: 'mathjax' # or 'katex'
  mathjax:
    src: http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML
    config:
      tex2jax:
        inlineMath: [ ['$','$'], ["\\(","\\)"] ]
        displayMath: [ ['$$','$$'], ["\\[","\\]"] ]
      TeX:
        Macros:
          dd: \mathrm{d}
          RR: \mathbb{R}
          argmax: \operatorname*{argmax}

1
2
3

$$
\argmax_{t \in T} f(t)
$$

$$
\argmax_{t \in T} f(t)
$$

Hexo特有の記法

ところで、Hexoにはこれとは別にHexo記法というものが存在し、次のように書くことで同様の結果が得られる。

1
2
3
4

{% math %}
\mathbb{E} \max_{s,t\in S: d(s,t) \leq \delta} |X(t)-X(s)| \leq (16 \sqrt{2} + 2)
\int_0^\delta \sqrt{\log 2N(T, d, \varepsilon)} \mathrm{d}\varepsilon
{% endmath %}

ただし、hexo-mathの現在の仕様では、mathブロックの中に単一の行しかないときはインライン数式、それ以外はディスプレイ数式として勝手に解釈される。個人的にはちょっと不便だなとも思う。