mots quotidiens.
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp by hns, version 2.10-pl1.

先月 2007年06月 来月
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

2007年06月04日(月) [n年日記]

#1 Postit.el(TM)

計算機上で何かちょっとしたメモを取りたいとき, Windowsで暮らしている人は 紙copi(Lite) を使えばいいのですが, Unixでは使えません。 委細かまわずChangeLogメモに全部書いてしまうという手もありますが, 検索する必要があるので, 技術的なメモはそれだけまとまっていると便利だと 感じることがあります。
ATRに移ってから, 技術メモは適当なファイルに書き足していたのですが, そろそろ限界を感じてきたので, 環境が新しくなったのを機会に, 昔使っていた postit.el に戻してみました。

Postit.el(上の画像。クリックで拡大) は昔に玉越君が書いて, NAISTにいた時は僕もずっと使っていたものですが, Emacsのバージョンが上がったので使えないかと思い込んでいたら そのまま変更なしに動くことを発見。めちゃめちゃメモが使いやすくなりました。 m でメモを書いたり, ファイルやURLにリンクを張ったり, それらを検索したりする のがEmacsから簡単にできます。 上のEmacsは通常のFedora Coreのもので, バージョンは21.4です。

Postit.elをぐぐると, 改訂版 が置いてある 別の方のページ がヒットしますが, こちらの新しい版では .postit のフォーマットがS式に なっていて, やや不安(カッコが落ちると大変とか, 文字化けしたりした) なので, 前のバージョンの1.2が個人的にはおすすめです。
前バージョンは ここのページ に置いてありますが(webarchive万歳), 万一ない場合は これ を使ってもOKです。
.emacs に,

(autoload 'postit "postit" nil t)
(define-key ctl-x-map "p" 'postit)
と書いておくだけで, C-x p で簡単にメモが使えます。 postit-1.2.tar.gz の中にマニュアルが含まれているので, 使い方はそれを見れば okです。

#2 PPMと言語モデル (2)

岡野原君が書いている ようにPPMをCRPとして解釈できないかという話は, MacKayのところにいる Phil Cowans ( Dasher を実装したのは彼らしい)のD論 "Probabilistic Document Modeling" にあるのを思い出したので, (細かく全て読んでいる時間はないのですが) ざっと読んでみた。
結論から先に言うと, PPM-AはHDPの近似で, PPM-BとPPM-DはKneser-Ney(つまり Pitman-Yor)の特別な場合です。

PPMはWitten-Bell+Katz' Back-offですが, Witten-Bellスムージングは HDPの特別な場合です。 どういうことかというと, HDPでは各文脈で常に新しい語がBase measureから出現する 可能性がありますが, これは重複を許しているため, Base measureからこれまでと 同じ語がサンプルされる可能性があります。これが起こらない(HPYLMの言葉で言うと, tuw=1)の場合は, HDPのスムージングはWitten-Bellと等しくなります。

さて実際には, HDPは0-gramまで再帰的に確率を混合するのに対し, PPMは見つかった最長の文脈を使うという点に違いがあります。 このためにPPMではExclusionという方法を使いますが, これはKatz' Back-off と同じです。
ゆえに, これがHDPの再帰的な混合とどう違うのかというのが問題となるわけですが, 上のCowansのD論ではこれを実際に調べて, PPM(つまり, Witten-Bell+Katz' Back-off) はHDPのかなり良い近似になっている, という結論に達しています。
具体的に言うと, 近似の具合はHDPのconcentrationパラメータαの値によりますが, これが典型的な値(5〜10くらい)の間はほとんど違いがなく, それよりαが大きくなると 微妙にHDPの方が良くなる(さらにαが大きくなると, Exclusionを行わない方が近似が 良くなる)という結果になるようです。

一方, PPM-BとPPM-Dはそれぞれ, Kneser-Neyでディスカウント係数dが 1.0と0.5の特別な場合です。
Pitman-Yorの言葉で言うと, θが0で, dが1.0または0.5, かつ上で書いたように, tuwが常に1であるような(これがK-Nが近似である理由), Pitman-Yor過程の特別な場合です。
岡野原君のエントリを最初に読んだ時に, これはKneser-Ney(=Pitman-Yor)だろうと パッと思ったのですが, θも0になっている特別な場合なので, すぐにわからなかった。;

というわけでまとめると,

ということで, 圧縮で経験的に高性能だった手法は自然言語処理/音声言語処理の 手法と同じだった, という結論になるようです。


2007年06月14日(木) [n年日記]

#1 "The Infinite Tree"

ぷは。
少し余裕ができたので, 1ヶ月くらい前に Finkel のところで読めるようになった "The Infinite Tree" (ACL 2007)を読んでみた。 はっきり言って非常に読みにくいので, 以下に自分用の意味もこめて整理。
ACLのAccepted Paperが出た時にタイトルを見てギクッとしたわけですが, 最初に書いておくと, これは僕の話とは全然関係ありません。 タイトルを見ると, 僕の話のように木の深さが無限であるかのような誤解をして しまいますが, 実はこの場合の木は構文木なので有限で (それどころか, 木構造自体はgivenだとしている), ただ木のタグ (文法的な解析では, NPとかVPとか人間が与えているもの) の種類数に上限がない, という話。

まずモチベーションは, 通常の文法的なタグは粗すぎたり, 逆に細かすぎたりする ので, それを「データの複雑性に沿って」ノンパラメトリックベイズで自動的に決め たい, ということ。
木構造がPTBのように与えられているとすると, 問題はただ, 木の各ノードにどんな タグ(1,2,…,∞)を振るか, という話だけになる。 たとえば,

   <-  ---->
  /  \/     \
 *   *   *<--*
 |   |   |   |
She ate the cake.

という風に木ができている時, 普通は順に木の各ノードに, 順に NN, VP, DT, NN というラベルを振るが, このとき木全体の確率は, ノード間が親子になる確率×ノードから単語が出力される確率で,

L = p(NN|VP)p(NN|VP)p(DT|NN)×p(she|NN)p(ate|VP)p(the|DT)p(cake|NN)

のようになる(実際は再帰的に書ける)。 *1

いま, ラベルが有限で人が与えている場合は上のp(NN|VP)のような確率はコーパス から計算すればいいが, これが未知で, 可算無限個だった場合はどうするか, というのがここでの問題。つまり, 各カテゴリに自然数を振って, p(1|2)p(1|2)p(3|1).. のような確率が最も確からしい割り当てを選ぶことに なる。

これは要するに, タグjがタグkの子供になる確率 p(j|k) を行列にして,
            j
      1 2 3 4 5 6 ..
     +-----------------
   1 |
k  2 |
   3 |
   : |
という可変長のテーブルと, タグkからの単語の出力確率, それに従ったノードのタグを求める話になる。
いま, この行列の各行 p(・|k) は確率分布なので, これはDPから取るのが自然。 ただし, 各行を別々にDPからサンプルすると要素が共有されないので, クラスタjを共有するためには, これを(1段階の)HDPにする必要がある。
..これで説明はほとんど終わり。
論文で書いてある mjk が, 上の p(j|k) を求めるCRPのカウントで, βがHDPの一番下のbase measure のカウント。これを基にして, 各単語に NP, VP, .. のかわりにその親子関係が 全体の確率を最大にするような, 自然数のタグ 1,2,3,.. をサンプリングしていく, というモデルになる, のだと思う。

タイトルもそうだが, 論文の最後に "permit completely unsupervised learning of dependency structure"と書いてあるので, 依存構造木をunsupervisedで学習して タグをつける話なのかと思っていたら, 木はもう与えられていて, 単にそのタグ付け を決める話だけだった。脱力。 *2
Liang の "Infinite PCFG using HDP" (EMNLP 2007) [link] の方がずっとレベルが高そうな話で, こちらの方が本来ACLにふさわしい話だと思うが, Infinite PCFGは全力でまともな 内容を書いているので(PCFG-HMM, HDP-HMM, Structured Mean Field), ACLの レビューアが理解できなかったのではないか, と想像。
Finkelの方は, DPやHDPの説明を途中で長々としていて(それを端折ると, 上のように 単純な説明になる), 難しくてスミマセンネ, のような内容まで最後に書いてある。 *3 HPYLMの話もそうだったし, そこまで子供に書くように書かないと通らないなんて, ACLっていったい.. と思ってしまった。


*1: これは, 子供の確率を独立に計算する"independent child"の場合。 論文では, 子供を順番に生成する "Markov child" の方が性能がよかった と書かれている。
*2: とはいうものの, これで依存構造木が与えられれば, それに完全に自動的に タグを振れることが示されたわけで, 実用的な意味は十分にあると思う。 自明な応用は, 普通に dependency parsing をした後, この方法で依存構造にタグを 付与するということだが, 本来はその二つを同時にやるのが理想的で, 恐らく ある程度はやっているのではないかな, と。
*3: DP, HDP, HPYの計算を全部フォローした僕が読んでも, 書き方がわかりにくくて 何度も読み返さないとわからなかった論文で, 本当にこれが充分理解されて レビューを通ったのか, ちょっと疑問。 この内容だとMark Johnsonあたりにレビューが行っていれば, 一人は理解できそう ですが..。

2007年06月16日() [n年日記]

#1 書店

最近(だいたい1年半くらい前)にオープンした, 光台の けいはんなユータウン に入っている書店, ACADEMIA けいはんな店にこの間とこの日, 初めて入ってみた。
出来てすぐから存在は知っていたが, 「ACADEMIA? どうせ名前だけじゃないの? やまざき貴子の漫画じゃないんだからさ…」と思っていたのだが..

..すいませんなめてました。
鄙には稀な, 旭屋書店のような都会の専門店なみの品揃えで驚いた。 普通の地方の本屋にはまず置いていない, みすず書房の本(全部ではないですが)や, 白水社クセジュ文庫のようなものまで置いてある。
調べると, くまざわ書店 の展開のうち, 全国に数個所あるACADEMIA店の一つらしい。

普通の本はもちろん, 文芸書, 科学書とも非常に充実している。 例えば 「自然界における左と右」 とかが普通に置いてあるわけですが, 特に子供にとっては, 都会に出て大型書店に行ったりするのは無理なので, こういう 本が普通に近くの本屋に置いてあるというのは素晴らしいなあ, と思ってしまった。 特に子供の頃は, 実際にいい本が並んでいる場所(書店や図書館)に行って良いと 思う本を選んで読む, というのはとても大事だと思う。

ただ, いくら光台が研究所が多く, 住民のレベルが高い(らしい) *1 とは言っても, 本当にこれで採算がとれてやっていけるのかなあ.. と少し 心配してしまった。


*1: 話によると, 光台の精華西中学校は妙にレベルが高かったりするらしい。

2007年06月29日(金) [n年日記]

#1 pdfnup

UnixのTips。
これまで, PDFのスライド等を4up,両面で印刷するのに, UnixのAdobe Readerからは そういう指定ができないので, ずっとWindowsのノートを起動して, そちらから 印刷していたのですが, PDFLaTeX関係のシェルスクリプト集 PDFjam に含まれる pdfnup を使うと
% pdfnup --nup 2x2 hoge.pdf
でPDFを4upにできて, 普通に両面印刷できるのを知りました。ブラボー。
印刷してみましたが, Windowsからと遜色ない結果が得られています(Unixからの方が 若干綺麗だった)。
内部で pdflatex を呼んでいる模様なので, それが入っていないと使えないかも しれませんが, 私の所では特に何もしなくても入っていました(tetexに含まれている のかも)。


4 days displayed.
タイトル一覧
カテゴリ分類
 なかのひと
Powered by hns-2.10-pl1, HyperNikkiSystem Project