2010-08-08
「言語処理のための機械学習入門」を参考に各種モデルに対するEMアルゴリズムを実装したよ
Amazonにもレビューを書いたのですが、高村さんの「言語処理のための機械学習入門」を読みました。
実はこの本を読むのは2回目で、1回目はドラフト版のレビューをさせていただく機会があったのですが、そのときは「言語処理研究者のための機械学習入門」というタイトルで、ちょっと敷居が高いのではないかとコメントしたら「研究者」の部分が削られたという経緯があったりしました。
それはともかくとして、以前読んだときは時間もなくて実装までする暇はなかったのですが、今度はもうちょっとじっくり読みたいなということで、このブログに書いてみようと思います。
EMアルゴリズムは教師なし学習を確率モデルと最尤推定でやろうとするときに必ず出てくる手法で、隠れ変数や欠損値を含む色々なモデルに適用できる汎用的なフレームワークになっています。一般的には混合ガウス分布の場合をまず説明して、それがk-means法の一般化した形になっている、という説明がなされることが多いと思います。しかし、言語処理においては離散変数のクラスタリングを行ないたいことが多く、pLSAやそれをベイズ化したLDAが多く使われていて、そのあたりを丁寧に解説した書籍が欲しいなあ、と思っていたところでした。
以前のPRML読書会などで実装した分も含めてgithubへのリンクをまとめると、こんな感じになりました。実装はpythonです。
- EMアルゴリズムのサンプル：Data-Intensive〜に載っていたビー玉遊びの例
- 混合ガウス分布
- k-menas法：混合ガウス分布の特殊な場合
- 混合ポアソン分布
- 混合多項分布
- pLSA
- 隠れマルコフモデル
勉強のための実装なので、非常に小さく人工的なテストデータで、尤度関数が単調増加することを確かめるのに最低限のコードを書いた感じです。
今回実装してみて興味深かったのが、混合多項分布とpLSAの違いです。文書クラスタリングを例にとって考えると、混合多項分布では文書のクラスタリングを行うのに対して、pLSAでは文書と単語のペアをクラスタリングしていることに相当します。そのためメモリの使用量や必要なクラスタ数が混合多項分布よりpLSAのほうが多く、自由度の高いモデルとなっていることがわかります。
2010-08-03
英語学習に役立つサイト10選
釣りっぽいタイトルにしてみたものの、そこまで使っていません。
- smart.fm
- lang-8
- YouTube
- delicious
- Google Reader
- Myspace
- Digg
あとGoogleを英語設定にするとか。rarejobとか。podcastingもいいですね。
参考：
2010-08-02
英語の勉強を始めた
手始めに英語のブログをRSSリーダに追加してみた。その中で面白かった記事を紹介してみる。
Searching the Searchers with SearchAudit - Microsoft Research
メールアドレスや電話番号をさがすために機械的にクエリーを投げてくるスパム業者に対して、クエリーログを見て検出しようという話。
Data, data everywhere | Data Mining Research - www.dataminingblog.com
最もデータが集まっている分野は天文学であるという話。
2010-08-01
2010-07-31
単語の尤度比データを公開しました
不自然言語処理では単語の尤度比を使ってコーパスの性質を調べたわけですが、そのデータはGoogle N-gramに依存しているため公開は見送るつもりでした。
ところで昨日、id:s-yata氏が作成中のウェブコーパスから集計したN-gramデータを公開されました。
ウェブコーパスの一部から形態素 N-gram コーパスを作成しました - やた＠はてな日記
ということで、さっそく尤度比をとってみました。対象は以下の３つです。
- yata氏のコーパス
- Wikipedia N-gram
- Baidu N-gram（合計とキャリア別）
データはtar.bz2に固めてgithubにアップロードしました。
2010-07-26
Hadoop座談会に行ってきました
- 大谷さん：HadoopとNoSQLとRDBMS
- Hadoopの現状：もうすぐ普及期
- NoSQLの現状：まだ枯れてない
- RDBMSの現状：市場がシュリンクしてきた
- Hadoopの特性：巨大データのバッチ処理に強い
- NoSQLの特性（Cassandraより）：スケーラビリティ
- NoSQLとCAP：Cassandraは多様性、HBaseは一貫性重視
- RDBMSの特性：優れたデータ一貫性(ACID)とクエリー言語をもつ
- CQRSパターン：更新系と参照系は明確に分けましょう
- 一貫性保護をアプリ開発者に任せるのは不可能：コンシステンシーレベルをアプリからもらうのは必須
- アーキテクチャ図：HadoopでViewの構築を行う
- ポイント：一貫性はRDBMS、速度重視はNoSQLに。力技はHadoopで。
- 課題1：RDBMSからHadoop：ネイティブに持ってくる
- HadoopからNoSQQL：HDFSからダイレクトに
- NoSQLの接続先の抽象化ができてない問題
- 課題2：データ構造のポータビリティ、フェイルオーバ
- まとめ：RDBMSは一貫性の高いデータ保持、HadoopはRDBMSとNoSQLのハブになる
- 佐藤一郎さん：分散システム向け計算モデルの過去・現在・未来
- Nii所属、マンモス関係の作業とかモバイルエージェント+加速器とか、環境省で排出権の仕事とか
- 計算モデルの話をする予定だったが変更。CCS?
- 元分散システムの研究者から見たMapReduce/Hadoop
- 大量データ向けのバッチ処理用分散システム
- 計算モデル的な解釈：関数型計算モデル
- 1990年ごろの並列LISPの提案手法と類似
- 手持ちのサーバーよりタスク数が増えてきたときにどうするのか？→20年前の知見が活きている
- MapReduceとHadoopの違い：Indexingに特化してない、フロントに出ている
- Hadoop使いたいからアプリ作るのはやめたほうがいい
- Hadoop向けDSL：アプリケーションを限定すべき
- DCからみたHadoop：消費電力の変動が大きい。評判がよくない
- Hadoopの消費電力の研究：電力モデルが作れない→結論はよくわからない
- Hadoopの外部提供：他社のデータがみえてしまう。セキュリティ的にどうなの？
- データビジネス
- 荒川さん：Hadoopのデータフローまとめ
- HDFSとMapReduceの関係：データローカリティの話
- レプリケーションとスプリット：ローカリティと並列度を上げる
- 多段MR：シーケンス図が残念。DAGで書けばOK
- スケジューラ：ネイティブスケジューラをサポートしない
- 変更耐性：大きなDAGの場合、どこを変えればいい？ 影響範囲が大きすぎる
- 対処法（モデル）
- フロー全体で共通のモデル（静的型）を共有する
- 動的型付けにすればいいんじゃない？→静的型とやってることが同じ
- タプル＋型推論を利用する
- 対処法（処理）：全データを含める？
- 再利用性について
- 多段MRを境界をどうするか
- 対処法：高級言語を利用する（Hive, Pigなど）
- 原子化：入力から出力までアトミックに処理したい→多段スケジューラ
- 併合化：どこを併合化するのか
- 座談会
- クラウドOS
- クラウド時代におけるTX
- プログラミングのパラダイム
2010-07-25
2010-07-24
TokyoRに行ってきました
最近は聞くだけの勉強会のレポートはTwitterでの実況で十分と考えてブログでは書いてないのですが、ネットが繋がらないときはテキストにメモしておくのでアップすることにしました。
共分散構造分析(bob3)
相関分析と因子分析を同時に行うもの？
SEMで回帰分析
SEMで因子分析
BICで比較
マーケティングデータの例
RとPython(yanashi/GREE)
R+Python(Rpy)
RでExcelと同じことをするにはggplot2くらいしかない、けど格好悪い
Flash, Silverlight, Processingなどと連携できる！
PyExcelerator
Django-dataplot
インストール実演
R, Python, pywin32が必要
r = robjects.r
x = robjects.IntVector([1,2,2,2,2])
y = robjects.IntVector([1,2,3,3,3])
print r.cor(x,y)
print r("t.test")(x,y)
R Language Difinition案内 〜Rでハマったときのために〜 @tyatsuta
第１回：なぜ関数型言語でC-likeな文法が実現できるのか？
仕事で：C++, Perl, Ruby, Python, Java, R
趣味で：Scheme, Common Lisp, Haskell, Erlang
Rとは？ C＋APL＋CLOS＋Schemeの機能を有するLisp
APLとは？：「独特な表記」で「配列処理に特化した」「元祖wirte-only言語」
ロケットサイエンティストとは？：「頭の良い人」という意味。冷戦終了後、NASAからウォール街に流れ込んだ。
「APL言語入門」引用禁止だが非常に面白いので読んでください
Rの関数は３種類： closure, builtin, special
special: 引数を評価しない関数
オペレータは関数：x+yは`x`(x,y), "+"(1,2)と書ける（builtin関数）
Assignオペレータ（`<-`)はspecial関数
制御構造も関数： `if`(cond, expr)
関数型言語R：どう見てもLispです本当にありがとうございました。
Rソース→字句解析器→構文解析器→関数型評価器
Rで麻雀
RとC/C++
.C(), .CALL()関数
.so や .dll にコンパイルしておいて呼び出す
C/C++コードの作成：最後の引数がバッファのアドレスになっているのでそこに書き込む
SOの作成： R CMD SHLIB conv_c.cpp
SOの読み込み > dyn.load("conv_so.so")
conv.c <- function(a,b).C("conv_c",
as.double(a), as.integer(length(a)),
as.double(b), as.integer(length(b)),
res=double(length(a)+length(b)-1))
Call()を使う方法
Rcppパッケージ
Rパッケージ作成 @yokkuns
タイトルだけ埋める
次回
8/28 土
2010-07-20
Google N-gram V.S. Baidu N-gram 〜ケータイウェブは本当にエロいのか？〜
背景
近年検索エンジンのBaiduは不自然言語処理コンテストなるものを開催し、今日が締切のはずだったのだが24時間延長されたらしいことを聞いてBaiduコーパスをダウンロードしたid:nokunoは仕事帰りの電車で思いついたアイデアを30分ほどで実装してみたところそれなりに面白い結果がでたので応募してみることにした。
そもそもBaiduのコーパスはエロいというのを最初に@tomityさんが言ったら@mhagiwaraさんがこんなツイートをしたことに話は遡る。
インターネットがエロいのは誰でも知っている。けれど、ケータイウェブが特別にエロいのか？ については寡聞にして知らなかったため、検証してみることにした。
手法
今回はケータイウェブがエロいかどうかを検証するため、以下のコーパス（N-gramデータ）を相互に比較することとした。
- Baidu N-gram（Baidu絵文字入りモバイルウェブコーパス）
- 今回のメインターゲットとなるコーパス。日本のケータイウェブの実態が反映されている。
- キャリアごとに分かれているが、統合して（頻度の和を取って）使うことにした。
- Google N-gram（ウェブ日本語Nグラム）
- Google提供のコーパス。主にPCウェブサイトが中心と見られる。
- そのままでは大規模すぎるため、頻度が10000以上のものに絞っている。
- Wikipedia N-gram
- 個人的な目的でWikipediaのダンプから作成したN-gramデータ。
比較の方法として尤度比を用いることにした。これは頻度をその合計で正規化した確率（尤度）の比をとったものである。
時間がないので既存研究のサーベイは行っていない。誰か詳しい人に解説を譲りたい。
2つのコーパスにおけるあるN-gram列の尤度比rは以下の式で表される。
ここでf1、f2はそのN-gram列の頻度、s1、s2はそれぞれのコーパスの頻度の合計である。
実装
実装はPythonで行った。ファイル名を2つ取って両方に含まれるN-gramとその尤度比をタブ区切りで出力するシンプルなプログラムである。
python/unlp at master from nokuno’s nokuno - GitHub
#!/usr/bin/python #encoding: utf-8 import sys from optparse import OptionParser parser = OptionParser() parser.add_option("-1", dest="file1") parser.add_option("-2", dest="file2") (o, args) = parser.parse_args() ngram1 = {} total1 = 0 for line in open(o.file1): (words, freq) = line.strip().split("\t",2) freq = int(freq) ngram1[words] = freq total1 += freq ngram2 = {} total2 = 0 for line in open(o.file2): (words, freq) = line.strip().split("\t",2) freq = int(freq) ngram2[words] = freq total2 += freq for (words, freq) in ngram1.items(): prob1 = float(freq) / total1 if words in ngram2: prob2 = float(ngram2[words]) / total2 diff = prob1 / prob2 print words + "\t" + str(diff)
実験
Baidu N-gramを「ケータイウェブ」の代表、Google N-gramを「PCウェブ」の代表と考え、それぞれのウェブ＋Wikipediaの比較を行う。
Baidu N-gramとGoogleN-gramの比較
BaiduとGoogleの比較を以下のように行なった。baidu/1gram.txtはbaiduの各キャリアの結合済みファイル、google/1gram.txtは頻度によるカットオフを行ったもの。
$ ./unlp.py -1 baidu/1gram.txt -2 google/1gram.txt | LC_ALL=C sort -nr -k 2 -t " " > b-g.txt （-tの後ろはタブ文字）
Baidu：Googleの尤度比が高い上位20件の単語は以下のようになった。
$ head b-g.txt
エッチ 5119.99561097
オマカセ 595.990737836
♪▼ 510.209064334
アダルト 384.271279233
Game 316.067823711
§ 280.412180468
edit 275.461925725
ジョブセンス 272.359243891
ref 253.820163796
ニチイ 253.653700268
パイズリ 248.756786335
/♪ 246.102132034
j 243.848874582
イクヨクルヨ 228.71580121
エロ 227.976148718
タッタ 222.026317132
サラブレ 215.196758723
[*] 214.942445945
オタメシ 211.5489614
若妻 202.11784817
これにより、ケータイウェブではPCウェブより「エッチ」が5120倍、「アダルト」が384倍多く使われていることがわかった。
BaiduとWikipediaの比較
Baidu N-gramとWikipedia N-gramの比較も行った。
$ ./unlp.py -1 baidu/1gram.txt -2 wikipedia/1gram.txt | LC_ALL=C sort -nr -k 2 -t " " > b-w.txt （-tの後ろはタブ文字）
Baidu N-gramの尤度比が高い1-gram 上位10件を示す。
$ head b-w.txt
ホムペ 92394.3184806
t 86671.9365121
x 27613.1798699
オマカセ 21985.1660878
~。 20382.8729232
コチラ 18075.0464986
オススメサイト 11664.9563719
^^ 10836.2857352
マイプレ 10384.4325095
(^^) 7422.97532719
ケータイウェブでは「ホムペ」「コチラ」「(^^)」などが多く使われていることが分かった。また10位には入っていないが、ケータイウェブではWikipediaと比べて「セフレ」が4381倍、「援交」が1929倍も多く使われていることが分かった。
また、Baidu N-gramのうちauのデータとWikipediaを比較し、尤度比が小さい（Wikipediaの比率が高い）1-gramの上位10件は以下のようになった。
$ tail a-w.txt | tac
アメリカ合衆国 0.00264567964808
同年 0.00398798936786
艦 0.00456043409053
師団 0.00507230636419
1979 0.00510213271866
運行 0.00515332130124
1950 0.0058025915648
翌年 0.00625834576354
1975 0.00633504517707
ソ連 0.00646659592719
政治用語などの真面目な単語や年号が多く、それらしい結果が出ている。
結論
「ケータイウェブはエロい」という仮説はそれなりに実証されたかもしれない。
今後の課題
キャリアごとの比較や、先行研究の調査は今後の課題としたい。
参考文献
Google Japan Blog: 大規模日本語 n-gram データの公開
Wikipediaから作成したN-gramデータを公開しました - nokunoの日記
工藤拓、 賀沢秀人著、「Web 日本語Nグラム第１版」、言語資源協会発行
