三日目は体調も良好で，一日しっかり聴講することができた．学会も最終日だからかセッション数も一つ少なく，ややゆとりのあるスケジュール．三日目も色々な発表を聞いたが，記憶に残ったのは以下の3つ． Machine Translation Detection from Monolingual Web-Text: MT で自動翻訳された文書を識別する問題．面白い問題設定で，かつ，問題に関する深い観察・理解から導かれた手がかりを用いて識別器を構築しており，誠実な研究という印象を受けた．テストデータの作り方がやや人工的，局所的で苦しく，多分に苦労の跡が感じられる．ここは2日目で触れたテキスト再利用に関するコーパスのように，ユーザに機械翻訳結果を利用しつつ翻訳してもらってコーパスを作り，評価していたら，隙もなくより妥当な評価ができたのではないかな*1．企業の研究らしく実世界データを用いた実験もあって，こう

学会の一日は招待講演で始まる．初日と三日目は認知言語学や大脳生理学など周辺分野の研究者による学術的な講演なのに対し，この日はサービス寄り話で顔本のグラフ検索の話．まああんまり聞いててワクワクする話ではなかった．自分は研究室内でこの手の産業寄りの話ばかり聞いているので，個人的に（この会議には）その手の話は期待していないというのがあるのかも．多分普通の聴講者はワクワクするのだと思うけど． 続いて，Best Paper Award, Best Student Paper Award の発表．ちなみに，Best Student Paper Award は A corpus-based evaluation method for Distributional Semantic Models (from Student Research Workshop) だった． 初日は起きる時間が現地時間にピッタ

公開しているコードについて問い合わせを受ける機会が増えてきたので，もう少しソフトウェアとして導入・利用し易くしようとインタフェース周りを作り直した．自作の（コマンドライン）オプション解析と手書きの環境依存 Makefile が利便性を損ねているのは明らかだったので，標準的なオプション解析ライブラリとビルドツールに対応することにした．オプション解析を書き換えたのはだいぶ前（自作の学習器が MacPorts から導入可能になっていた - ny23の日記）のことだけど関連するのでまとめてメモしておく． C++ で使えるオプション解析ライブラリは古典的な GNU getopt を初めとして getoptpp, google-gflags, boost::program_options, cmdline など色々あるが，最近のもので定番と呼べるほどのものはないようだ． How to Parse Co

以前 Lua の処理系 LuaJIT が速くて羨ましいという話を書いたが，最近は Python でも JIT コンパイラ PyPy の性能向上が著しいようだ．どれぐらい速いかというと，以前実験した PA-I（機械学習）で LuaJIT での実行速度を上回るぐらい*1．Python はもともとスクリプト言語の中では実行速度が速い方だったが，PyPy の急速な性能向上によって Perl や Ruby といった競合言語に対して（実行速度の点で）差を広げつつあるようだ． そういうわけで，最近スクリプトを Python で書く機会が増えている．Python でコードを書く上でやっかいなのは（まともな）ワンライナーが書けないこと*2と，（処理系のバラつきに起因する）移植性の問題である．前者はどうにもならないので，perl / ruby / sed + awk などで回避することになるが，後者は公開する

巷にある構文解析器には，解析結果を木構造で端末に表示する機能がある．あった方が良いだろうなと思いつつ，自分で実装するのはいかにも面倒そうだと感じて，今まで後回しにしていた．いい加減そろそろ無いと困ると感じるようになってきたので，先日の通勤電車の中で暇つぶしに書いたら，思いの外あっけなく実装できたので，メモ代わりに残しておく．最初 Ruby でワンライナーで書けないかなと思ったが，流石に難しかったので，練習も兼ねて Python で実装してみた． #!/usr/bin/env python # -*- coding: utf-8 -*- # Usage: lattice_to_tree.py < in.KNP # translate parser output into human-readable dependency tree structure import sys # customi

第二著者としてかなりコミットしていたビジュアル（可視化）系の共著論文が，採択率 1/3 ぐらいの国際会議に採録された．11月の湯治中に最初の採否の通知が来たのだけど，国際会議にも関わらず条件付き採録という結果だった．結果が来るのは知っていたものの（まさか国際会議で条件付き採録とは予想できず）湯治中だったので迷惑をかけてしまったが，第一著者を中心にせっせと直して（自分も途中から参加して）先月末に再投稿した．それから一週間，改めて採否の結果が来て，ようやく採録となった．今回の研究はそもそもネタを持ち込んだのが自分なので，無事通ってくれてほっとした．採録されたのは可視化系の国際会議なので，自分の専門分野の研究者にはほとんど知られることは無いかも知れない．折角なので，少しこの研究のことなどを書いてみる． 今回の研究は，大規模データ（個人的な感覚では中規模ぐらい）を，文ではなく構文解析した結果の可視

C++ の次期標準，C++0x (C++11) の標準案が ISO に全会一致で承認されて一ヶ月半ほど経つので C++0x でプログラムを書いてみることにした．折角なので，以前から実装しようと思っていたサポートクラスに基づく多クラス Passive Aggressive アルゴリズム Exact Passive-Aggressive Algorithm for Multiclass Classification Using Support Class (SDM 2010) を実装してみる． コンパイラには現時点で C++0x に最も対応していると期待できる GCC 4.7 (SVN 先端; 20110927) を利用．GCC の C++0x の対応状況は以下を参照． C++0x Support in GCC - GNU Project - Free Software Foundation

（半）指導している学生が IPA 品詞体系に基づく構文解析器が遅過ぎて実験が進まないというので，手元の構文解析器（Juman 品詞体系を想定）を IPA 品詞体系に対応させてみた．構文解析器のコードは素性抽出周りを10行くらいいじるだけで簡単に対応させることができた（公開済）． 次に，構文解析器の訓練に使う注釈付きデータが必要になるが，これには Juman 品詞体系に基づく注釈付きデータに IPA 品詞体系の品詞タグを付与して使うことにした．品詞タグを変換するには， 元の Juman 品詞体系の品詞タグを IPA 品詞体系に変換する IPA 品詞体系の形態素解析器を用いて自動付与する という二つの方法が考えられる．今回は運用時の状況を考慮して，構文解析器とパイプライン的に組み合わせる予定の形態素解析器／辞書を利用して品詞タグを再付与することにした．以下がそのスクリプト． #!/usr/bi

先週末から SWIG を使って分類器と学習器の Perl/Python/Ruby/Lua バインディングを書いていた．3年ぐらい前に書いた分類器の Ruby バインディングは，Ruby の C インタフェースが変わってそのままでは動かなかったので，結局一から書き直すことに．Python -> Ruby -> Perl -> Lua と書いてきて一番大変だったのは Perl．学部の時少し使っただけで，もはや文法をほとんど覚えていなかったので，何よりテスト用のスクリプトを書くのが大変だった． SWIG で書いた std::vector 用の入力インタフェースは以下．スクリプト言語側の配列を C++ の std::vector に詰め直して関数に渡すだけ．色々拾ったり編集したりしたものだけど，言語横断的に見れたほうが便が良いのでメモしておく．swig-2.0.3 + Perl 5.8.9/5.1

Python で書いた Passive Aggressive-I が C++ 実装に比べて50倍遅かったので，（スクリプト言語でも）もう少しぐらい速くならないかと思って，スクリプト言語で最速の処理系 (LuaJIT) を持つ Lua で Passive Aggressive-I を実装してみることにした． Lua はアプリケーションへの組み込みを意図し，高速な動作，ポータビリティ，拡張の容易さなどを重視して設計されたコンパクトな汎用スクリプト言語．今月の TIOBE Programming Community Index では Ruby の一つ下の12位にランキングされている*1．これは，iPhone アプリの開発者による利用が増えているというのが大きい*2と思うが，プログラム言語の設計者たちへのインタビューを纏めた Masterminds of Programming（邦訳: 言語設計者

朝から晩まで神保町で某成果報告会に参加していた．明日・明後日は自分にも仕事があるので，聴講に専念できるのは今日だけ．質疑応答システム Watson/DeepQA に関する Keynote で人が1.5倍増になり，それが終わると人が漣のように引いていく，そういう一日だった．講演時間も短く，内容は一般向けの概要紹介*1．という感じだったが，それでも興味深かった．Jeopardy! で出される質問は基本的に factoid 型なので，質問文を適切に解釈をすることができれば答えの候補を列挙することは比較的容易で，人に匹敵する回答精度を達成するには（構文解析＋共参照解析による）質問文の柔軟な解釈と，多様な観点を考慮した回答候補のランキングが重要だったのこと*2．また質疑で，適切な回答を見つけてくる際には Wikipedia が知識源として必要不可欠だったという言及もあった．個人的には「構文解析の大切

2月20日から東京で開かれる某国際会議で Christopher Manning が Part-of-Speech Tagging From 97% to 100%: Is It Time for Some Linguistics?*1 と題した基調講演を行うそうだ．自分はこの会議には参加しないので，講演を聴講することはできないのだけど，著者のホームページで講演内容に関する原稿が公開されていたので読んでみた．一言でまとめると，この原稿で Manning は，業界的には半ば「終わった」とみなされている品詞タグ付けタスクにおいて，現状の解析器の誤りの半数程度が注釈付けに起因することを指摘し，それを踏まえて「注釈を修正すること」の是非を議論している．かつて品詞タグ付けタスクに取り組んだことがある人や，自分で新しくタスクを定義してデータの注釈付けに取り組んでいる人は，是非読んで欲しい*2．それ以外

2月に入ってから一週間の間にジャーナルの再査読3件と論文の締切りが重なってやや忙しかったが，今日やっと全てを片付けて一段落した．今回は再査読なので本当は一回目の査読より楽なはずなのだけど，実際には一回目より大変な査読になった．その一番の理由は不採録としたコメント（2件）の取り扱われ方（今回は両方とも再査読することになった）． 一つのジャーナルではそれがそのまま著者に渡ってしまっており，著者らは対応しようと苦慮しているのだけど（不採録コメントでは単に問題点を指摘しているだけで，どう直せば良いか具体的な方針を示していない項目もあって）十分に対応できているとは言えない箇所も多く，そのまま再査読するなら不採録（か良くて照会後判定）とせざるを得ない．ただ，不採録コメントに直接対応しようとすること自体にそもそも無理があって，これで採否を判断するのは忍びないと感じる．再査読に回すのであれば（採録のための

一年ほど前に構文解析器を公開したが，（文節区切りされたデータを入力する仕様で）単体では使えない状態のままずっと放置していた．ところが最近になって，幾つかの共著論文で公開した構文解析器を引用する機会があり，このままではマズイと思ったので，現時点で使っている文節区切り - ny23の日記で書いた200行弱のシンプルな文節区切りの実装を同梱してみた．文節区切りの入出力がパイプ経由の文字列渡しなのは明らかに無駄なのだけど，気にしないことにしよう． MeCab と組み合わせる場合，解析速度は新聞記事だと入出力（UTF-8）込みで12,000文／秒，ブログ記事なら21,000文／秒程度（3.2 Ghz CPU; MeCab だけだと，新聞記事で22,000文／秒程度（入出力込み）なので，そんなに悪くない速度ではないかと）*1．係り受けのところだけで評価すると（デフォルトのパラメタで）解析精度は91.8

k-means を実装していて，疎ベクトルと密ベクトルのトレードオフ（距離計算の速度差）が気になったので軽く実験してみた．具体的に知りたかったのは，どれぐらい疎なら疎ベクトルを使った方が距離計算が速くなるか，という問に対する答え．空間使用率の改善については sparse vector における index と value の型のサイズ比でほぼ自明に分かるが，速度に関してはコンパイラの最適化の加減もあるので良く分からない．以下がテストコード（ややずぼらな実装）． [追記] 折角なので，Eigen 3.0-beta2 とも比べてみた． #include <sys/time.h> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <tr1/random> #include <eig

昨日，今日と電車に乗っている時間が長かったので，暇つぶしに論文を読んでいた． Making k-means even faster (SDM 2010) この論文では，Elkan の三角不等式を用いた k-means の高速化手法 Using the triangle inequality to accelerate k-means (ICML 2003) のアイデアを元に，空間計算量を悪化せず k-means を高速化する手法を提案している．手法自体の新規性はそれほどない感じだけど，空間使用率を大幅に改善しつつ，かつ実際に幾つかのデータで Elkan の手法以上の高速化が得られたことに意義があるのかな． [追記; 2013/02/20] 別解出力をサポートした高速 k-means の C++ 実装を公開 - ny23の日記 で実装を公開しました．自分の専門分野だと，クラスタリングする対象

先週は，今年の研究が始められていないのを不安に感じつつ，査読をやっていた．ここ数年は，一年辺り，ジャーナルが5本，国際会議が10-20本ぐらいの分量．数的にはさほど多くはないと思うのだけど，査読する論文のほとんど（80%ぐらい？）が自分の専門分野外のため，一本の査読にも最低半日はかかる（関連論文まで確認しだすと数日かかる）．専門分野の査読だと，過去に5本とか7本とか回ってきたときでも，一日かそこらで終った記憶があるので，この差は非常に大きい（ここで言う専門分野の会議とは，自分が論文を出したことがある会議だけでなく，普段論文を読むだけ周辺分野の会議も含む; 過去査読した専門分野外の論文は例えば，P2P framework, image mining, social annotaion, PSO など）．専門外の論文の査読コストは専門分野の査読コストの数倍ぐらい，と考えると，専門分野の査読を5

大規模データで単語の数を数える - ny23の日記 でみたように，単純に高頻度の item が欲しい場合には，小規模データで単語の数を数えてみた (1) - ny23の日記 で使った sketch-based なアルゴリズムよりは，counter-based なアルゴリズムの方が（キーを陽に保存するので）使い勝手が良い．というわけで，space saving アルゴリズムを実装してみた．カウンタのデータ構造には，原著論文 Space saving (Efficient computation of frequent and top-k elements in data streams, ICDT 2005) に書いてある stream summary をほぼ定義通り素直に実装して利用． // GNU GPL version 2 copyright@ny23 #include <cstdio

大規模データで単語の数を数える - ny23の日記 で書いた Count-Min Sketch で，誤差を減らすヒューリスティクス (conservative update) New directions in traffic measurement and accounting (SIGCOMM Comput. Commun. Rev., 32(4), 2002) を実装して，動的ダブル配列を使って Wikipedia のテキスト処理を高速化 - ny23の日記 の小規模データ（1.5GiB の Wikipedia 本文）の単語カウントでその効果を見てみた．考えるところはハッシュ関数に何を使うかぐらいで（キーを陽に保持しない限りは）実装はとても簡単． // GNU GPL version 2 copyright@ny23 #include <cstdio> #include <cstdl

大規模データから one-pass で item（n-gram など）の頻度を数える手法に関するメモ．ここ数年，毎年のように超大規模な n-gram の統計情報を空間／時間効率良く利用するための手法が提案されている．最近だと， Storing the Web in Memory: Space Efficient Language Models with Constant Time Retrieval (EMNLP 2010) とか．この論文では，最小完全ハッシュ関数や power-law を考慮した頻度表現の圧縮など，細かい技術を丁寧に組み上げており，これぐらい工夫が細かくなってくるとlog-frequency Bloom filter (ACL 2007) ぐらいからから始まった n-gram 頻度情報の圧縮の研究もそろそろ収束したかという印象（ちょうど論文を読む直前に，この論文の7節の