測度の収束の種類としてVague Convergenceというものがあることを知る。

定義自体は弱収束とよく似ている。 $\mathbb{R}$上の測度の列$(\mu_{n})_{n=0, \ldots}$が$\mu$にVague収束するとは、任意の$f\in \mathcal{C}_{\infty}(\mathbb{R})$に対して、 $\int_{\mathbb{R}} f(x) \mathrm{d}{\mu_{n}}(x)$が$\int_{\mathbb{R}} f(x) \mathrm{d}{\mu}(x)$に収束することをいう。 ここで、$\mathcal{C}_{\infty}(\mathbb{R})$は、$\mathbb{R}$上の連続関数$f$で、$f(x) \to 0$ (as $x \to \pm \infty$)となるものを言う （下記の参考文献では$\mathcal{C}_{0}(\mathbb{R})$と書いているけれど、自分はこの記号はコンパクト台に使うことが多い気がしたので表記を変えてみた）。

上記の定義は$\mathbb{R}$上であったが、Vague収束の概念はより一般的にLocally Compact Hausdorffな位相空間でも良いらしい。

上の定義で、$\mathcal{C}_{\infty}(\mathbb{R})$を連続関数全体の集合$\mathcal{C}^{0}(\mathbb{R})$に変更すると弱収束の定義になる。 $\mathcal{C}_{\infty}(\mathbb{R}) \subset \mathcal{C}^{0}(\mathbb{R})$なので、弱収束すればVague収束するが、その逆は成立しない。 例えば参考文献の例を挙げると、$\mu$を台がコンパクトで全空間での積分が有限な測度として、$\mu_{n}(x) = \mu(x-n)$と定義すると、$(\mu_{n})_{n=0, \ldots}$は0にVague収束するが弱収束はしない。 従って、Vague収束は弱収束より真に弱い条件となっている。

しかし、測度が確率測度であるときはVague収束の収束先に追加で条件をつければ弱収束が言える。 具体的には参考文献のFact2にある通り、確率測度列がVague収束し、さらに収束先も確率測度である時、この収束列はVague収束先に弱収束している。

出典

RANDOM MATRIX THEORYの12ページ3.1章

参考文献

• RANDOM MATRIX THEORY S. Kargin and E. Yudovina

• WikipediaのVague topologyの項目

証明が面白かったので紹介。

$\Sigma = \lbrace 0, 1\rbrace$を2文字からなるアルファベット集合、$\Sigma^{\ast}$を$\Sigma$をアルファベットとする語(word)全体の集合とする。 語$w\in \Sigma^{\ast}$に対して、$w$の長さを$|w|$で表す（空文字は長さ$0$とみなす） 語の集合$S\subset \Sigma^{\ast}$が、prefix-freeであるとは、任意の語$w, w’\in S$に対して、$w$は$w’$のprefixではない事を言う （空文字は全ての語のprefixであるとする。従って$S$がprefix-freeでかつ空文字を含むならば、$S$は空文字のみからなる集合である）。

以上の設定のもとでKraftの定理の主張は以下の通り：語の集合$S\subset \Sigma^{\ast}$がprefix-freeならば、 $\sum_{w\in S} \frac{1}{2^{|w|}} \leq 1$

$S$がprefix-freeでなかったら、結論は成立するとは限らない。例えば$S = \lbrace 0, 1, 00\rbrace$などが反例である。

証明は次の通り。 確率1/2ずつで表裏が出るコインを投げる過程を繰り返して行いながら$\Sigma^{\ast}$の元を作成する過程を考える。 初期状態は空文字で、各試行で表が出たら0、裏が出たら1を一番後ろに追加する。もし$S$のいずれかの元が得られたらそこでコイン投げを終了する。 この過程では$S$の元が一つ得られて終了するか、永遠に過程が終わらないかのいずれかの事象が起こる。 さらに$S$がprefix-freeであるという条件から、任意の$w\in S$に対して、$w$が得られるコイン投げ過程の途中で他の$S$の元が得られることはない。 $w\in S$が得られる確率は$1/2^{|w|}$なので、

$1 \geq $ ($S$のいずれかの元が得られる確率) $= \sum_{w\in S}$ ($w$が得られる確率) $=\sum_{w\in S} \frac{1}{2^{|w|}}$

10月30日のPyData Tokyo MeetUp #1にて「Caffeとmafを用いたディープラーニング開発・実験方法」というタイトルで発表を行いました。 発表資料はSlideShareで公開しています。当日の発表に関する情報はconnpassにまとめられています （私以外の発表の資料へのリンクや当日のUstreamでの配信へのリンクもあります）。 また、当日までのtwitterの反応はtogetterにもまとめられています。

• PyData Tokyo Meetup #1 - Deep Learning(connpass)
• PyData Tokyo MeetUp #1(togetter)

勉強会の立ち上げ会での講演という大役で恐れ多くありましたが、興味を持っていただいたようで当日は質問や議論で盛りあがり一安心しました。 発表の機会をくださったPyData発起人の皆様、発表を聞いてくださった方々に改めてお礼を申し上げます。 PyDataは「濃い」勉強会を行うことを目標としているとのことで、陰ながら応援をさせていただければと考えております。

発表内容について

今回はディープラーニングライブラリの中でも特に開発が活発に行われているCaffeと、PFI/PFNで開発している実験ビルドツールのmafをそれぞれ紹介しました。 また、 発起人の柴田さんから、Caffeを用いて参加者の方が自分で何か作れるようになるとうれしい人が集まっていると事前に聞いておりましたので、 デモを通じてmafとCaffeを用いて具体的に実験を行う具体的な方法を紹介しました。

質問の回答

頂いた質問について、きちんと答えられなかったものがいくつかありましたので、ここで改めて回答いたします。 自分が質問を間違って理解していたら申し訳ありません。指摘していただけるとありがたいです。

高次元な入力データを扱う方法について

入力が高次元で疎な場合に、BlobとLayerを駆使して効率的に学習を行う方法がないかという質問を頂きました。 疎なデータを入力するためのInput Blob(Sparse Blob)は議論で挙がり、Pull Request上で既に実装されているのですが、まだマージされていないようです。 ですので、もし利用する場合には、ローカルレポジトリにforkし、このリクエストをマージし、自己責任で利用する必要がありそうです。

参考：Sparse Data Support #937

また、返答中で「Torch7と勘違いしているかもしれない」とも話しました。 確認した所、疎なデータを入力して内積計算するLayerがTorch7にも存在しました。

参考：SparseLinear Layer関係 - コード - ドキュメント

mafをCaffeで実行する際の-j1オプションについて

デモでmafを用いてCaffeを実行した際、1並列での実行を指定する-j1オプションを付けたのはなぜかという質問にきちんと回答ができていませんでした。 これは今回のデモで用いたNeural NetでのData Layerがleveldb形式であった事が原因です。

Data Layerを用いて入力データを与える場合、入力ファイルを予め適切なファイル形式に変換しなければなりません（そのためのスクリプトはCaffe側で用意されています）。 その形式の1つのleveldb形式では、同じファイルに複数のプロセスから同時にデータにアクセスすることができません（下記issue参照）。 今回のデモでは、色々なパラメータでのprototxtを生成・利用しましたが、Data Layerで利用しているファイルは共通していました。 そのため、複数のタスクが並列に走った場合競合が発生します。 下記のissueによると、ファイル形式がleveldbではなくLMDBを用いれば並列実行しても問題ないようです。

参考：Parallel access to Leveldb #695

Mac OS 10.9でのCaffeのインストールについて

公式サイトに手順は書かれていますが、Mac OS 10.9でのインストール方法は10.8以前とは異なります。 その原因の一つがデフォルトで使用するC++ライブラリです。 Mac OS 10.9ではデフォルトC++コンパイラであるClang++はlibc++をデフォルトで用いています。 しかし、NVIDIAのCUDAはlibstdc++でコンパイルしたライブラリとしかリンクできません。

これの回避策は大きく分けて2通りあります。 一つ目はClangのコンパイラをlibc++からlibstdc++に変更する方法でこれは本家サイトで紹介されています。 もしGPUを使用しないのであれば、もう一つの方法として、10.8以前の方法に1つ手順を加えるだけでインストールを行う方法があります。 具体的には、Makefile.configの中で–libstdc++を利用する部分を削除し、コメントアウトされているCPU_ONLY:=1を有効すれば良いです。 これにより、GPUを使わないのでデフォルトのライブラリがlibc++でも問題なくCaffeをビルドできます。

GPUを使用しない場合のインストール手順はtwitterで@mooopanさんに指摘していただきました(参考)。ありがとうございます。

(2015/1/1追記)

上記とほぼ同等の内容を会社のリサーチブログに載せたので、こちらでの文章は下書きとして未公開にしていましたが、せっかくこちらのブログ用にも整形していたので、こちらでも公開しました。

先日9月25日の社内セミナーにて「実験プログラム開発方法論」というタイトルで発表を行いました。 発表資料はSlideShareで公開しています。当日の発表はUstreamのPFIチャンネルから視聴可能です。 また、発表に関連する資料群（デモのレポジトリ・実験メモ・発表に関連して書いた文書）などをgoogle docsで公開しています。

• PFI Show(Ustream)
• 20140925PFIセミナー関連資料置き場

以下では発表内容の簡単なまとめ、発表の補足、実験プログラムについて考える経緯について、随筆的に書いていこうと思います。

ランダム行列のチュートリアルに出てきて「おー」と思ったけれど、冷静に見たら$\tan$の加法定理だった。

出典

下記参考文献の11ページ、3.1章

参考文献

• RANDOM MATRIX THEORY S. Kargin and E. Yudovina

NIPS2012のランダム行列のチュートリアルからの抜粋。

$\mathbf{W}_{d}$を$d$次元対称行列で対角要素は$0$、非対角要素は標準正規分布に従う独立な確率変数とする。 すなわち、

$\lambda_{d}$を$\mathbf{W}_{d}$の最大固有値とすると、$\lambda_{d}/\sqrt{d}$は$d\to \infty$でalmost surelyに2に収束する。

参考にしているチュートリアルでの比較的簡単な証明で得られる結果（参考資料の定理4.1.1）では、 ここまでtightなバウンドを示すことができない（$\log d$のfactorがかかる）。 これ自体の証明は結構大変らしいが、できれば何か直感的な理解ができるような説明があるとうれしい。

また、ここで$\mathbf{W}_{d}$の事をWigner行列と呼んでいるが、Wigner行列自体はもっと広いクラスの行列を指す言葉の様子。 統計物理の文脈でよく出るようで、関連するチュートリアルや講義資料が多く見つかった。

（追記）

しばらく前にここまで原稿を書いた後によくよく考えたら、これはWigner’s Semicircle Lawからすぐに示せることに気づいた。 実際、以下のTodd Kemp氏のレクチャーノートで、Lemma 6.1としてこの事実をSemicircle Lawから示している。 NIPS2012のチュートリアルにあった「難しい定理」というのはSemicircle Lawの事だったのかな。

ついでに上に挙げたWigner行列のもっと広義の定義というのは、Kemp氏のチュートリアルによると、各エントリが独立かつ2乗の期待値が有限。さらに対角成分はi.i.d.の分布、非対角成分も（対角成分とは異なるかもしれない）i.i.d.の分布というものを言う（従って、スカラーの確率変数としては対角成分と非対角成分の2種類しかなく、2乗の期待値もその2種類での有限性だけ言えば十分）。 また、Wigner行列を$d^{-1/2}$（$d$は行列のサイズ）でスケール変換したものもWigner行列と言うらしい。

出典

Tropp氏のチュートリアルの35ページ、4.4.1章

参考文献

• User-Friendly Tools for Random Matrices: An Introduction

Joel A. Tropp氏のNIPS2012のチュートリアル

• Statistical Mechanics and Random Matrices

Alice Guionnet氏のレクチャーノート

• MATH 247A: INTRODUCTION TO RANDOM MATRIX THEORY

Todd Kemp氏のレクチャーノート

通常の確率変数と同様に行列に値を取る確率変数に対しても積率母関数とキュムラント母関数を定義できる。 具体的には$d$次正方行列に値を取る確率変数$\mathbf{X}$に対して、その積率母関数(Moment Generating Function:MGF)$ M_{\mathbf{X}}$とキュムラント母関数(Cummurant Generating Function:CGF) $\Xi_{\mathbf{X}}$をスカラー値の場合と同様の形式に以下で定義する。すなわち、

ここで$\theta \in \mathbb{R}$。

すると、CGFに関して次が成立する。$\mathbf{X}_{i}(i = 1, \ldots, n)$を$d$次正方行列に値を取る独立な確率変数として、次の不等式が成立する。

スカラー値の確率変数の場合、MGFには乗法性、CGFには加法性が成立する。MGFの乗法性は次のように示せる。

ここで、3行目の等式では、$X_{i}$達の独立性を用いた。この式の$\log$を取れば、CGFの加法性も言える。

しかし、行列値の場合はこのような式変形はできない。 スカラー値$x, y$に対しては、$\exp(x+y) = \exp(x)\exp(y)$が成立する。 一方、行列$\mathrm{X}, \mathrm{Y}$に対しては、一般的には$\exp(\mathrm{X}+\mathrm{Y}) = \exp(\mathrm{X})\exp(\mathrm{Y})$が成立せず、従って、2行目の等式が成立しないためである （例えば$\mathrm{X}, \mathrm{Y}$が可換である事は$\exp$の分配法則が成立する十分条件である）。

冒頭に上げた定理は、それにもかかわらず$\mathrm{tr} \exp$を取ればCGFに関しては劣加法性だけは成立している事を主張している。

出典

下記のチュートリアルの25ページ、Lemma 3.5.1

参考文献

• User-Friendly Tools for Random Matrices: An Introduction

Joel A. Tropp氏のNIPS2012のチュートリアル

非負の確率変数が外れ値を取る確率は期待値で抑えられるという定理。 Concentration Inequalityと呼ばれる一連の不等式達の中でおそらくいちばん基本的な不等式。 Wikipediaにあるように証明は数行で終わるのだけれど、応用範囲がものすごく広くここからこの系統の種々の不等式を導ける。

$X$を$\mathbb{R}$に値を取る非負の確率変数。$t>0$に対して以下が成立する。

$X$が非負の条件を外すと簡単に反例を作れる（例えば$X$が常に負を取るような確率変数など）。

出典

色々。例えばWikpediaのConcentration Inequalitiesの項目。

Octopressのブログの下書きはmarkdownで書かれている。 業務内でもmarkdownを書く機会は多いのでこれを機会にemacsにmarkdown-modeを導入することにした。

既にel-getは導入済みだったので、markdown-mode自体はel-getで導入した。

1

M-x el-get-install markdown-mode

基本的には下記のサイトで紹介されている方法で導入できたが、Octopressが自動生成するmarkdownテンプレートの拡張子が.markdownなので、markdonw-modeに紐付ける拡張子は.mdと.markdownの2種類とした。その結果.emacsの設定は以下のようになった。

1
2
3
4

;; markdown
(autoload 'markdown-mode "markdown-mode.el" "Major mode for editing Markdown files" t)
(add-to-list 'auto-mode-alist '("\\.md\\'" . markdown-mode))
(add-to-list 'auto-mode-alist '("\\.markdown\\'" . markdown-mode))

参考サイト

• Futurismo

この方法で導入することができた。

せっかくブログ記事にカテゴリを付与しているのに、カテゴリ名で記事一覧を引く事ができないのは不便なのでトップ画面にカテゴリ一覧を追加した。

参考サイト

• Octopress Top Categories Plugin を使う

amay077さんのQiitaの投稿。記事の通りに作業しうまく導入できた。