独断と偏見によるノンパラ入門

「ノンパラメトリック」って言うくらいだからパラメータ無いんかと思ってたら、パラメータめっちゃあるし。
機械学習のネーミングのひどさはこれに始まった話じゃあないけど、それにしたって。
ノンパラの一番素朴なやつ( K-means とか)は本当にパラメータ無くてデータだけだから納得なんだけど、だんだん欲が出てパラメータ足しちゃったり派生させちゃったりしてるうちに、よくわかんなくなってきちゃったんだろうかねえ。まったく。
どれどれ、と英語版 Wikipedia"Non-parametric statistics" を見たら、なんか意味が4種類くらい書いてあるし。じゃあ名前分けろよ。

en.wikipedia.org

とりあえずここで言う「ノンパラ」とは、変数の個数決めなくていい「分布の分布」なメタっぽいやつのこと。つまりディリクレ過程とか、ディリクレ過程とか、そこらへん。
「あー、ノンパラベイズね」だけど、ベイズさんは「炎上上等とネタ論文投稿したら案の定炎上しちゃった。てへ。でももう 250年くらい経つってのにまだ燃えてるとか、一部の板の住人に蛇蝎のごとく嫌われてるとか、ありえないし。さすがにわかっとったら投稿しなかったよ……(ショボンヌ」というかわいそうな人なので、そっとしておいてあげよう。というわけでベイズうんぬんはスルー。
では始まり。

コインとサイコロ

今日のお話の主役は、コインとサイコロ。
コインは投げたら表か裏が出る。縁で立っちゃったら? とかそういう突っ込みは却下。
コインの表の出る確率は 0 から 1 の間の値 p で表そう。高校までの数学で投げているコインは p=0.5 のコインだ。


サイコロは6面のよくあるやつだけじゃあなくて、4面とか20面とか100面とか、何面でもOK。じゃがいも適当に削ってなんか書いたやつとかでも、投げたときになにか値が決まるなら、それは「サイコロ」。
サイコロは例えば面の数が4なら、(0.5, 0.2, 0.1, 0.3) みたいに4つの面それぞれの出る確率の組で表せることにする。足したら1になるのはいいよね。
高校までの数学で振っているサイコロは (1/6, 1/6, 1/6, 1/6, 1/6, 1/6) だ。

ベータ分布とディリクレ分布

ノンパラに進む足がかりとして、まず「5回投げたら表を 2回、裏を 3回出してくれそうなコイン」ってのを考えてみる。


「それって確率 2/5 で表が出るコインってことだよね? 終了〜」


で、本当に終わってくれればいいけど*1,残念ながらそうは問屋が卸さない。
まず p=2/5 というコインは本当に「5回投げたら表を 2回、裏を 3回出してくれる」のか。
そして p=2/5 じゃあなかったら、そのコインは「5回投げたら表を 2回、裏を 3回出してくれない」のか。
そこら辺を考えると、「5回投げたら表を 2回、裏を 3回出してくれそうなコイン」を表す p は、1個の値に決めつけるんじゃあなくて、いろんな可能性を考えておいた方がよさそうな気がしてくる。つまり、「5回投げたら表を 2回、裏を 3回出してくれそうなコイン」を表す p は何かの分布にしたがってる、と言える。
実はその分布にはちゃんと「ベータ分布」って名前が付いてる。


ベータ分布にはパラメータが2つあるので、Beta(a, b) と書くことにしよう。
そうすると、「5回投げたら表が 2回、裏が 3回出してくれそうなコインをくれる分布」は、パラメータが 2 と 3 であるベータ分布 Beta(2, 3) で得られちゃうのだ。なんて簡単。
Beta(2, 3) からコインをもらってくると、 p=0.29 とか p=0.46 とか、そのたびにいろいろな確率を持つコインが得られる。


じゃあ「10回振ったら 1を3回、2を2回、3を1回、4を2回、5を1回、6を1回出してくれそうなサイコロをくれる分布」もあるのか?
こちらもちゃんとある。「ディリクレ分布」だ。
欲しいサイコロをくれる分布は、ベータ分布の時と同じように Dir(3, 2, 1, 2, 1, 1) と書ける。
Dir(3, 2, 1, 2, 1, 1) からもらうサイコロは、(0.32, 0.06, 0.07, 0.29, 0.19, 0.07) みたいな。こちらも同じくもらうたびに違うサイコロが出てくる。


実のところ、ベータ分布はディリクレ分布の値が2個の場合、つまり「2面のサイコロの分布」だったりする。
なので以降サイコロとディリクレ分布の話がメインになるが、一応コインの場合も含まれている。でも後でもう一度ベータ分布が出てくるので憶えてて。
なお、ベータ分布もディリクレ分布もパラメータに0以上の実数を許していて、特に1より小さい値を指定したときがキモカワイイのだけど、残念ながら今回はそこら辺パス。

どうして「サイコロの分布」がいるの?

そうそう、気をつけて欲しいのは、考えようとしているのは「サイコロの分布」だってところ。「サイコロの出目の分布」じゃあないよ。
なんか言葉遊びのようだけど、この程度で混乱していたら、後で出てくる頭の体操ステージで撃沈するのでよろしく。


話を進める。
ここで各面に単語が書いてあるサイコロを考えてみよう。わかりやすいイメージとしては、6面サイコロに「私」「オレ」「は」「男」「女」「です」とかなにか単語が書いてある。サイコロを振って出る「値」はその単語だ。これを振って、出てきた言葉を順に並べたら、はい「文章」のできあがり。
この例だと6面しかないので少なすぎるんだけど、10000面とかあるサイコロならそこそこ豊富な単語が書けそうだ。いや、そんなサイコロの実物を作るんじゃあなくて、コンピュータの中に用意するんだけどね。


「すげー、頭いいなあ。よーし、今度の読書感想文はそれで行こう〜」
「あほか。そんな横着なやりかたで、まともな文章が出来るわけないって」


でも機械学習ってそんなもんよ? ホント。
えっとでもまあ、実際このサイコロだけで文章を作るのはさすがに無理にしても、文章の分類とかには役に立ったりするのよ、これが。今日のテーマと違うからそっちはやらないけどね。


ただし役に立たせるには、「役に立つ単語サイコロ」が必要。その「役に立つ単語サイコロ」、どこから持ってこよう?
どこかのピラミッドの奥に言語の真の分布を体現したサイコロが眠っている……って言ったら自然言語の人は我先に取りに行くだろうけど、どこのピラミッドなのかまだ知らないのでその手は使えない。


そうだ、何かお手本文章(コーパス)を使ってサイコロを作ろうじゃあないか。
例えば「不思議の国のアリス」に使われている単語を頻度順に並べたら、「the が1643回、and が872回、(2566語省略)、zealand が1回、zigzag が1回」出てきていた。
ってことは「the を1643回、and を872回、(2566語省略)、zealand を1回、zigzag を1回出してくれる単語サイコロ」があればいいよね。
そう、ここに「サイコロの分布」、つまりディリクレ分布が登場するわけだ。

ノンパラの入り口「分布の分布」

さて、ノンパラの入り口がもうすぐ見えるところまで来たよ。


こうして「サイコロの分布」で満足してみんな幸せになりましたとさ……で、終わってくれるはずもなく、しばらくしたらだんだんいろんな不満が出てくる。
いくつかあるんだけど語ると長いので、一番わかりやすいところを1つだけ。
こうやって作った「不思議の国のアリス・サイコロ」には、「不思議の国のアリス」に出てくる単語しか載ってない。当たり前。
でも文章を作るにも分類するにも、それは結構困ることなんだ。


その解決方法はいくつもある。「スムージングとか?」そうそうそれとか。
でもここではそうじゃあない解決方法を考えてみよう。


ディリクレ「サイコロ」分布は、例えば Dir(3, 2, 1, 2, 1, 1) みたいな感じだった。ここからは6面までのサイコロしか出てこない。このようにディリクレ分布は面の数が固定されてしまうので、このままでは未知の単語を直接扱えるわけがない。
もしサイコロ分布が単なるディリクレ分布ではなく、つまり面の数に上限がなかったらどうだろう? そうすれば未知の単語も扱えるようになるのでは?
んーでも、コントロールできないほど自由に変化されたら困るし、「不思議の国のアリス」から作ったという性質まで失われるのもまずいから、「サイコロ分布」の変化しうる範囲とかは決めておきたいね。
あ。それって『「サイコロ分布」の分布』ってこと?


さあ頭の体操のお時間です。
『「サイコロ分布」の分布』に「サイコロ分布」をちょうだい、と言うと、「不思議の国のアリス」から作った、でも未知の単語も入ってるかもしれない「単語サイコロ分布」がもらえる。
その「単語サイコロ分布」に「単語サイコロ」をちょうだい、と言うと、「不思議の国のアリス」の単語を持つ、さらに未知の単語も載ってるかもしれない「単語サイコロ」がもらえる。
その「単語サイコロ」を振ると、「不思議の国のアリス」の単語か、あるいは未知の単語が出る。


OK?


他の解決方法に比べて、『「サイコロ分布」の分布』は未知単語を真っ向から扱おうとする。その分なんかややこしいことになってるけど、いろいろ嬉しいんだ。
しかし『「サイコロ分布」の分布』なんてそんな複雑そうなもの、あるんだろうか。

ディリクレ過程

あるんだ。それが「ディリクレ過程」。
ディリクレ過程は、確率変数の個数を決めなくていい「分布の分布」。そう、最初にそれが「ノンパラ」だと言ったっけ。


ディリクレ過程を実現する方法を考えてみよう。
要は、「サイコロの分布」が未知の単語も扱えるようにすればいいのだから、単純に2つほど方法がありそうだ。
1つは、最初から無限個の面を持つサイコロの分布を考えておく方法。
もう1つは、とりあえず今出ることがわかっている単語たちに加え、「その他」を面に持つサイコロの分布を用意して、サイコロを振ったときに「その他」が出たら、サイコロの分布を作り直す(面を一つ増やす)方法。


実はどちらでも同じディリクレ過程を実現できることがわかっている。それぞれの方法にちゃんと名前も付いている。
無限面サイコロ方式は「Stick-breaking(棒折り) 表現」、「その他」方式は「中華レストラン表現」という。いやふざけてないよ。ホントのホント。
この分野の研究をしている人たちは、至極まじめな顔で「このパラメータだと、こっちのテーブルにお客が座りすぎてしまう……どうしよう」とか考えてるときに我に返って何考えてたのかわかんなくなっちゃったりしないかな、論文書いてて煮詰まってきたら思わず「中華レストラン表現」を「中華レストラン表現(笑)」に全置換してストレス発散してみちゃったりとかしてんじゃあないかな、とかついいろいろ想像を巡らせてしまう。余計なお世話。


ディリクレ過程がどんなものか、Stick-breaking 表現でさわりを見てみよう。
記号の説明から全部書くと長いので、Stick-breaking 表現の一番のポイント、無限面サイコロをベータ分布で作ってるところだけピックアップ。
数式が苦手で、じっと見てるとじんましんが出たり気が遠くなるって人はちょっと薄目で眺めてくれれば。

\displaystyle\pi'_k \sim {\rm Beta}(1, a), \hspace{2ex} \pi_k=\pi'_k\prod_{j=1}^{k-1}(1-\pi'_j) \hspace{2ex} (k=1,...,\infty)

1つ目の式は「 π'_k を Beta(1, a) からもらっている」ということを表している。k は 1 から無限大まで動くので、要するに「表 1回、裏 a回出てくれそうなコイン」を無限枚用意するということだ。
2つ目の式はちょいややこしいんだが、意訳すると、「1枚目のコインを投げて表が出たら1つ目の単語。裏だったら2枚目のコインを投げて、表が出たら2つ目の単語。裏だったら3枚目(以下同様)」ということを表している。


整理すると、ベータ分布から無限個の「単語選びコイン」をもらうことで、「無限面サイコロの分布」を作り出している、というわけ。
ディリクレ過程から分布をもらおうすると、この「無限面サイコロの分布」が得られるので、ディリクレ過程は『「サイコロ分布」の分布』であるということになる。
あーホントややこしい。書いてても、あってるかどうか何回か読み返しちゃったよ。


簡単なことをわざわざ複雑にして素人を煙に巻いているだけのように見えるかもしれない。けど、ディリクレ過程は適当に作られているわけじゃあなくて、結構細かいところまで考え抜かれて便利な性質をいくつも持っている、とても強力な分布なんだ、これは。

Pitman-Yor 過程

せっかくここまで来たから、おまけにノンパラな分布をもう一つ紹介しとこう。


こうしてディリクレ過程で満足してみんな幸せになりましたとさ……で、終わってくれるはずもなく、しばらくしたらまたまただんだんいろんな不満が出てくる。
一番は「減衰が早すぎる」こと。
文章での単語の頻度は一般に「ベキ分布」という裾の長〜い分布に従うことが知られていて、これはとてもゆっくり減衰していく。いわゆる「ロングテール」というやつだ。
ところが、Stick-breaking 表現をよく見ればわかるんだが、ディリクレ過程では単語が選ばれる確率はだいたい指数的に減衰していく。これはベキ分布よりもかなり速い。その違いのせいで精度がでてないんじゃあないか、という疑惑が。
どうしたらいい?


そうだ、ディリクレ過程は単語選びコインが全部同じベータ分布から作ってたんだった。だから指数的に減衰しちゃうんだ。後ろの方の単語になればなるほど裏が出やすいコインにすれば、減衰が遅くなるんじゃね?
えいやっと。

\displaystyle\pi'_k \sim {\rm Beta}(1-d, c+dk), \hspace{2ex} \pi_k=\pi'_k\prod_{j=1}^{k-1}(1-\pi'_j) \hspace{2ex} (k=1,...,\infty)

ベータ分布のパラメータだけを変えてみた。こいつは k が増えるほど2番目のパラメータが大きくなる(後ろの方の単語になるほど裏の出やすいコインがもらえる)ので、ディリクレ過程より減衰が遅いことを期待できる。


実はこれが「 Pitman-Yor 過程」。ベキ分布に従うものを Pitman-Yor 過程を使ってモデル化するとなかなかいい精度が出ちゃったりということで、最近 hot なノンパラ分布。ちなみに d=0 でディリクレ過程に一致するので、その意味でも筋がいい。
最新の論文でちらほら見かける名前だからとっっても難しげだけど、こうしてみると案外そうでもない? ごめんウソ。なんだかんだ結構難しいよ、やっぱり。

あとがき

新年一発目にいつもと毛色の違う、なんかヨタ話っぽいのやりたいなと思って、じゃあちょうど今絶賛予習中の Pitman-Yor / sequence memoizer あたりを……って書いてみたらこうなった。反省はしていない。
独断と偏見なので、語弊がちらほら多々あるだろうけど、まあ細かいのは笑って見逃して。いくらなんでもこれは、ってのは優しくご指摘下さいましまし。

*1:実際それで話が終わりになる立場の人もいるけど