December 31, 2009

PythonでLDAを実装してみる

Latent Dirichlet Allocationはテキストのような不連続データのための生成的確率モデル。入力はドキュメント。出力はドキュメントを特徴づける何か(tf-idfみたいなもん)。

基本的なアイディアは、あるドキュメントは潜在的ないくつかのトピックが混合していて、それぞれのトピックは語の分布で特徴づけられている、ということ。

論文[1]ではαとβというパラメータを用いてドキュメントが以下のように生成されると仮定している。
  1. ドキュメントのトピックの分布θがディリクレ分布Dir(α)に基づいて選ばれる。
  2. ドキュメントの語数N個になるまで以下を繰り返す。
    1. トピックznが多項分布Mult(θ)に基づいて選ばれる。
    2. 単語wnが確率p(wn|zn,β)で選ばれる。
ただし、トピックzの数をk個、単語wの種類をV個とすると、パラメータαはk次元のベクトル、βはk x V次元の行列でβij=p(wj|zi)。


Fig.1 LDAのグラフィカルモデル。Mはコーパス内のドキュメントの数。Nは各ドキュメントの語の数。αによって分布θが決まり、分布θに従ってzが選ばれ、zとβに従ってwが選ばれる。


ここで、ドキュメントにおけるαとβの値がわかれば、トピックがどんな割合であって(α)、そのトピックに関する語がどんな割合で存在するか(β)がわかる。つまり、ドキュメントが上のようなプロセスで生成されているとしてαとβの値はいくつかということを推定するのがLDAの目的。

αとβを推定する方法は変分ベイズEMアルゴリズムを利用するものやGibbs Samplerを利用するものなどが提案されています。また、いくつもの派生的なモデルも提案されています。

本稿では、論文[1]と
lda, a Latent Dirichlet Allocation package
http://chasen.org/~daiti-m/dist/lda/
のmatlabの方をパクっ参考にして、変分ベイズEMをPythonで実装してみました。

実行方法

要Numpy、SciPy。
python lda.py [-Nclasses] [-Iemmax] [-Ddemmax] [-Eepsilon] 入力ファイル名 出力ファイル名
classesはクラスの数。emmaxはEMの最大反復回数。demmaxは一つのドキュメントのEM最大反復回数。epsilonは収束条件。
たとえば、トピックの数が10個、「train」が入力で「model」に出力する場合は、
python lda.py -N10 train model

入力

テキストファイル。
1:1 2:4 5:2
1:2 3:3 5:1 6:1 7:1
2:4 5:1 7:1
ってな具合のフォーマット。行がドキュメント、<語のID>:<カウント>。SVMのライブラリでつかうフォーマットと似ている。上記の参考にしたサイトの上から1/3あたりのDownloadからcかmatlabバージョンをダウンロードして解凍するとtrainというファイルがありそのまま使える。

出力

<出力ファイル名>.alpha
<出力ファイル名>.beta
の二つ。alphaは長さがトピック数のリスト。betaはトピックの数×語の数の二次元リストになっている。はず。

References

[1] Blei et al., Latent Dirichlet Allocation, The Journal of Machine Learning Research, 2003.

ソース

lda.py


雑感

すごく…遅いです…

December 28, 2009

Pythonで順列や組み合わせを手に入れる

from itertools import ...

IteratorArguments
product()p, q, ... [repeat=1]
permutations()p[, r]
combinations()p, r

product('ABCD', repeat=2)AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)AB AC AD BC BD CD

10.7. itertools — Functions creating iterators for efficient looping — Python v2.6.4 documentation

December 26, 2009

Chironで実行可能なSilverlightアプリをつくるときのコマンド

構成が
app/app.py
app/app.xaml
index.html
で、index.html内で
<param name="source" value="app.xap"/>
としたら
Chiron /d:app /z:app.xap

Google App Engineでテンプレートを使おうとしたらUnicodeDecodeError

Google App Engineでテンプレートを使おうとしたらエラーが出る。

UnicodeDecodeError: 'ascii' codec can't decode byte 0xe3 in position 116: ordinal not in range(128)

どうやらテンプレートで日本語を使おうとしたときのunicodeのエンコード・デコードのエラーっぽい。

…
sentence = 'すもももももももものうち。'
template_values = {'sentence':sentence}
path = os.path.join(os.path.dirname(__file__), 'index.html')
self.response.out.write(template.render(path,template_values))
…

これのtemplate.render()に

.decode('utf-8')

をつけて

…
sentence = 'すもももももももものうち。'
template_values = {'sentence':sentence}
path = os.path.join(os.path.dirname(__file__), 'index.html')
self.response.out.write(template.render(path,template_values).decode('utf-8'))
…

となおしたら、大丈夫だった。テンプレートはutf-8で。

December 25, 2009

MacでLaTeXはDrag & Drop pTeXがいい

Snow Leopardになっても小川版pTeXがすごくいい。

Drag & Drop pTeX - JIS X0212 for pTeX
http://www2.kumagaku.ac.jp/teacher/herogw/

ghostscriptのインストールも忘れずに!

  1. 古いものを削除。アンインストールツールが付いている。


  2. pTeX.appをアプリケーションフォルダにドラッグアンドドロップ。


  3. TeXShopのPath設定で(pdf)TeXを

    /Applications/pTeX.app/teTeX/bin

    に。TeX + dvips + distllerの設定も

    Xtexshop

    に。dvipdfmxでフォントを埋め込む。なお埋め込まない場合はXtexshop-ryu。文字コードの認識しない場合は

    Shift_JIS/ヒラギノフォント埋め込みの場合は“dotexshop”、同/フォント非埋め込みの場合は“dotexshop-ryu”
    EUC/ヒラギノフォント埋め込みの場合は“dotexshop-euc”、同/フォント非埋め込みの場合は“dotexshop-euc-ryu”
    UTF-8/ヒラギノフォント埋め込みの場合は“dotexshop-utf8”、同/フォント非埋め込みの場合は“dotexshop-utf8-ryu”


  4. ついでに文字コードもUTF-8に。


  5. あとは Typesetting の Default Script を Tex + DVI にして、Misc の BibTeX を jbibtexにする。

December 23, 2009

MacのEclipseでGoogle App EngineのPYTHONPATH




Eclipseで新しいGoogle App Engineのプロジェクトを作るときのGoogle App Engine Directory、あるいはプロジェクトを指定してからプロパティでPyDev - PYTHONPATHのExternal Librariesの場所は
/Applications/GoogleAppEngineLauncher.app/Contents/Resources/GoogleAppEngine-default.bundle/Contents/Resources/google_appengine
PyDev - PYTHONPATHのExternal LibrariesではAdd Source FolderしてからCtrl+Shift+Gで直接場所を指定できる。


/usr/local/bin/dev_appserver.py
"${project_loc}/src"
--port==9999

December 18, 2009

ことえりにZコマンドを



Google日本語入力で使える「Zコマンド」がすごいのようにことえりのユーザ辞書に単語を登録した。

z+[hjkl] = ←↓↑→
z+- = ~
z+[ = 『
z+] = 』
z+, = ‥
z+. = …
z+/ = ・

記号入のほうは登録するときは注意が必要。たとえば「z.」は「z。」で登録しないとうまく行かない。

ユーザ辞書にRegister Wordsするときのショートカットは

Ctrl + Shift + N

MacからEPDことEnthought Python Distributionを消す方法

以下引用。

• On Mac, you'll need to uninstall manually as Apple does not yet support a standard uninstall mechanism for .mpkg installers. The recommended uninstall commands are as follows. The instructions suffixed by a #* are specific to restoring a different Python interpreter, in this case MacPython 2.5 from python.org. If you want to restore a different Python, you'll need to know where your backup Python environment is and customize these commands based on that information.

cd /Library/Frameworks/Python.framework/Versions
sudo rm -rf 2.5.2001 Current
sudo ln -fhs 2.5 Current
cd /Applications
sudo rm -rf "EPD 2.5.2001"
cd /usr/local/bin
PYTHON=/Library/Frameworks/Python.framework/Versions/Current
sudo ln -fsh $PYTHON/bin/python
sudo ln -fsh $PYTHON/bin/pythonw
sudo ln -fsh $PYTHON/bin/python2.5
sudo ln -fsh $PYTHON/bin/pythonw2.5

As an example, on OS X 10.6, to restore the default Python installation you would set the PYTHON variable as:

PYTHON=/System/Library/Frameworks/Python.framework/Versions/2.6
EPD - Frequently Asked Questions (FAQ) :: Products :: Enthought, Inc.

December 16, 2009

Ubuntu 9.10とWindowsのデュアルブートでデフォルトのOSをWindowsにする

UbuntuとWindows 7とのデュアルブートにしようとした。デフォルトで起動するOSをWindows 7にしたくてググったら、/boot/grub/menu.lstを書き換えましょう、という記事がたくさん見つかったのだけど、そもそもmenu.lstが見つからない。

で、さらに調べたらGrub2に関する記事を読め、と。

デフォルトのOSを切り替えるためにはStartUpManagerを使いなさいとのこと。

手順にしたがってソフトウェアセンターからStartUpManagerをインストールして、



システム > システム管理からStartUp-Managerを起動して設定した。


December 13, 2009

jQuery + PythonのJSONでのデータのやり取り


jQueryとPython CGIのデータのやり取りをJSONでおこないたい。
構成は、
index.html
sample.js
sample.py
(lib/jquery/jquery-1.3.2.js)

index.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
        <title>jQuery + Python</title>
    </head>
    <body>
        <h1>jQuery + Python</h1>
    
  <form id="hoge">
   <input type="text" name="foo" />
   <input type="text" name="bar" />
   <input type="text" name="baz" />
  </form>
  
  <a id="foo" href="#">show</a>
  <a id="bar" href="#">clear</a>
  <div id="baz"></div>

  <script type="text/javascript" src="lib/jquery/jquery-1.3.2.js"></script>
  <script type="text/javascript" src="sample.js"></script>
    </body>
</html>


sample.js

p2jはパラメータからJSON形式に変換する関数。どこかのページに掲載されていたのですが、失念してしまいました。すいません。
var $j = jQuery.noConflict();

function p2j(d) {
 if (d.constructor != Array) {
  return d;
 }
 var data={};
 for(var i=0;i<d.length;i++) {
  if (typeof data[d[i].name] != 'undefined') {
   if (data[d[i].name].constructor!= Array) {
    data[d[i].name]=[data[d[i].name],d[i].value];
   } else {
    data[d[i].name].push(d[i].value);
   }
  } else {
   data[d[i].name]=d[i].value;
  }
 }
 return data;
};


$j(document).ready(function(){ 
 $j('#foo')
 .click(function() {  
  // クエリ
  var query = $j(":input").serializeArray();
  console.log(p2j(query));
  
  // GETリクエスト
  $j.get('sample.py', query, function(text) {
   // 結果の処理
   var json = JSON.parse(text);
   var html = "";
   for (var i in json) {
    html += json[i].key + ':' + json[i].value + ' ';
   }
   $j('#baz').html(html);   
  });
  
  return false;
 });
 
 $j('#bar')
 .click(function (){
  $j('#baz').html('');
 }); 
});


sample.py

JSON形式にするにはjsonモジュールかsimplejsonモジュールがいいかもしれません。
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import cgi
import cgitb; cgitb.enable()
import json

print "Content-type: text/javascript; charset=utf-8"
print

form = cgi.FieldStorage()

foo = form.getfirst("foo", "")
bar = form.getfirst("bar", "")
baz = form.getfirst("baz", "")

print json.dumps([{'key':'foo','value':foo},
                  {'key':'bar','value':bar},
                  {'key':'baz','value':baz}])