NAL’s blog @ 琉球大学情報工学科

今更ですが10.6.8から10.7.x系にアップグレードしました。

10.6.8での開発環境に不具合出たのが切っ掛け。ここで原因追及するぐらいなら安定し始めてるかもしれない最新版でやってみようぐらいの気持ちで。作業前後でもリプライ頂いたのですが、Xcode3,4共存もできるみたいだし（参考: @shinji_kono先生、@shima__shima先生）。

あちこちはまったけど、特に分かり難かったのは python 周りのライブラリの導入方法。

必要に応じてxcode-selectすること。

通常easy_install or pip経由でインストールするか、ソース持ってきて手動で「python setup.py build; sudo python setup.py install」することになるけれども、そのままではこのbuildが通らない。多分クリーンインストールしてると問題なら無いと思うけど、私のように10.6.8からアップグレードしたケースでは10.6.sdkを参照しようとするので、次のように環境変数指定する必要があるっぽい。-archは必要無さそうだけど、念のため。「-L/opt/local/lib」はmacoprtsで入れたライブラリを参照させる場合の話で、そうじゃなければ適宜省略／編集すべし。

% env CC=/usr/bin/gcc CFLAGS=”-O -g -isysroot /Developer/SDKs/MacOSX10.7.sdk -arch x86_64 -L/opt/local/lib” python setup.py build

以下、時系列順に気になった点をメモ。

---

• ダウンロード版は、ダウンロード後にすぐ起動してアップグレードするか否かだけの選択肢で進む。（10.5->10.6時には/Applications, /Users とか残すディレクトリを選択できた気がするのだけど、今回はそういう選択肢は用意されていない）
• 「/Applications/Mac OS X Lion インストール.app」内のInstallESD.dmgでブートディスク作れるらしい。 QT Mac OX X Lionの起動ディスクの作成方法 – [モ]Modern Syntax
• 上記アップグレードイメージは、アップグレード終了後には削除されてる。
• アップグレード直後は動作がもっさりしてる気もするけど、裏でMail.appのデータ移行中なのでそれ次第かな。Spotlight周りもありそう。あと想像してたけどgcc消えたｗ
• Mail.appはスレッド表示できるようになったのね。フォルダ上のどこにあってもスレッドとしてみれるのは嬉しい。（ヘッダしか見てないと思うから、これで意図的に2通使ってスパム表示させるとか何かやれそうな予感）
• Finderは「環境設定」と「表示>ステータスバー」あたりで元表示に戻せる。
• App Store経由でXcode4インストールすると、結構長時間「インストール中」のままになる。「購入済み」タブで進捗状況が見れる。
• 終わったタイミングで「/Developer/Applications/Xcode.app」を起動するも、古いのが立ち上がる。ここでJava要求されるので、指示通りにインストール。（古いのが残ってるってことはgccも残ってる？）
• Xcode4は「/Applications/Xcode.app」にインストールされる。起動後、起動すると古いのを消すかどうか聞かれます．あと，コマンドラインツールとかは起動後に Preferences > Downloads で別途インストールです．gcc は LLVM ですが… あと，場合によっては xcode-select を使う必要もあったりするらしい。
• あれこれmecab, mecab-ipadic, libiconvと格闘するもmecabさんが文字化けしてしまう。
• 手動で入れた「/usr/local/{lib,include}」側のlibiconvを参照すると、mecabコンパイル時点でこける（x86_64用のlibiconv_openとかが見つからないとかか宣う）。しかし、libiconv使うサンプルプログラムは普通にコンパイル通って実行も問題無し。一方、標準or古い「/usr/{lib,include}」側のlibiconvを参照すると、mecabはコンパイルできるものの、文字化け。参照方法をいくつか試してみても状況変わらず。ぐぬぬぬ。
• 参考までにmacports側で入れたら正常に動くか確認してみようと「sudo port install mecab」するとXcodeが古すぎる（10.7.xならXcode4にしろ）と言われる。
• 「xcode-select -print-path」で「/Developer」（Xcode3.xが入ってるトップディレクトリ）になってたので、「xcode-select -switch /Applications/Xcode.app」と指定すると「/Applications/Xcode.app/Contents/Developer」を参照するように。
• これでport動くようになったのでmecabインストール。

% sudo port install mecab
% sudo port install mecab-ipadic-utf8
（このままだと /opt/local/lib/mecab/dic/ がeuc参照してるので変更）
% cd /opt/local/lib/mecab/dic/
% sudo ln -snf ipadic-utf8 sysdic

• portで入れたmecabだと、これで文字化けせずに動く。手動コンパイルした方だと、「手動mecab+portのIPA辞書」でも「portのmecab+手動IPA辞書」でも化ける。手動コンパイルは両方とも不具合あるってこと？
• ここでxcode-selectし直す前にlibiconv入れてた（それで問題無かったけど）ことに気付き、最後の一確認ということでlibiconv, mecab, ipadic をコンパイルし直してみる。が、/usr/local/以下のlibiconv参照するとやっぱりmecabのコンパイルでこける。/usr/以下のデフォルトだか古い環境の残り物だかを参照するとコンパイルできるけど、文字化け。ぐぬぬぬ。
• 不具合のあるmecab, ipadicが邪魔にならないように make uninstall して暫く放置（portのほう使う）。
• mecab-python（pythonバインディング）さんのインストール。普通に「python steup.py build」するとgcc-4.0とかMacOSX10.6.sdkを参照しちゃうので、build時に環境変数を指定してやる必要あり。なお、10.7.3からなのか、私の環境ではMacOSX10.7.sdkが/Applications/Xcode.app/以下のかなり深い場所にあったので、事前にlnしてからやってます。

% sudo ln -snf /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.7.sdk /Developer/SDKs/MacOSX10.7.sdk
% env CC=/usr/bin/gcc CFLAGS=”-O -g -isysroot /Developer/SDKs/MacOSX10.7.sdk -arch x86_64 -L/opt/local/lib” python setup.py build
% sudo python setup.py install

• RMeCabさんのインストール。といっても原則として「パッケージをインストールする」になっちゃって、そのソースパッケージでは「/usr/local/lib/libmecab.2.dylib」を参照してたりする。コンパイル済みでどうしようもないので、lnすることに。

% sudo ln -snf /opt/local/lib/libmecab.2.dylib /usr/local/lib/libmecab.2.dylib

• libsvmさんのインストール。前回の通りに進めると「手順6 Python用 shared libraryのインストール」で「-sonameなんてオプション知らない」と言われる。ググった限りでは作成されるライブラリ名の指定っぽい。ここでサジェストされてるように-install_nameするとOK。手順7以降は前回の要領でやれました。

% cd python
% c++ -shared -dynamiclib -Wl,-install_name,libsvm.so.2 ../svm.o -o libsvm.so.2
% sudo cp libsvm.so.2 /usr/local/lib/

---

多分、これでいろんなケースに対応できるんじゃないかと思うが。。。

複雑系研究室（遠藤研・山田研・當間研・赤嶺研）新配属学生（現3年次）への研究テーマの種提供を目的として、「ロボットは東大に入れるか」キックオフシンポジウムの紹介＋αをしました。

資料：PDF

これから研究室に入って勉強していくという学生がメインターゲットだったので、一つずつ細かい話をするというよりは、こういう観点もあるというのをあれこれ紹介することをメインとしつつ、気になったことをどう調べていけば良いかというtipsを加えた資料になってます。

最後のリファレンスや引用した文章もそうですが、基本的に主観が多分に含まれているので話半分で聞いてくれたらなと思いつつ、後で気になった時に参考文献を探す糸口になれば嬉しい。基本的には、


ぐらいの気持ちで耳を傾けてもらえれば十分。

イベントそのものの概要としては参加記録1の記事一覧にも上げている森山和道の「ヒトと機械の境界面」が読みやすいんじゃないかと想像。

関連記事:

• 「ロボットは東大に入れるか」キックオフシンポジウムへの参加記録
• 「ロボットは東大に入れるか」キックオフシンポジウム参加記録その2
• 山内くんの参加メモ

libsvmをコンパイルして「その場で動かす」だけなら README に書いてある手順で進められますが、実用的には好きな場所で実行できるようにしたい。ということでその手順です。

【蛇足コラム】
svm-trainとかの場所をos.path.exists()で確認するようなスクリプトになっているので絶対パスで指定せざるを得ないのだけど、cdll.LoadLibrary()のように環境変数か何かで指定されたPATHを参照して対象ファイルが存在するかを判断するようなライブラリって無いんだろうか。
ConfigParserあたりで変更箇所を一括管理する形で書くのも良いかもしれないけど。

環境構築手順

1. libsvm本家サイトからソースをダウンロード。
2. コンパイル。

> tar xvfz libsvm-3.1.tar.gz
> cd libsvm-3.1
> make

3. 実行ファイルを ~/bin/libsvm/ に、ツールを ~/bin/libsvm/tools/ にコピー。（要PATH設定）

> mkdir -p ~/bin/libsvm/tools
> cp svm-predict svm-scale svm-train ~/bin/libsvm/
> cp tools/*.py ~/bin/libsvm/tools/

4. スクリプトのパスを修正。

> emacs ~/bin/libsvm/tools/easy.py
is_win32でWindowsか否かに分けてパスをしている箇所で、
svmscale_exe 等のパスを絶対パスで指定。下記は記入例。
=====begin(easy.py)=====
svmscale_exe = "/Users/tnal/bin/libsvm/svm-scale"
svmtrain_exe = "/Users/tnal/bin/libsvm/svm-train"
svmpredict_exe = "/Users/tnal/bin/libsvm/svm-predict"
grid_py = "/Users/tnal/bin/libsvm/tools/grid.py"
gnuplot_exe = "/usr/local/bin/gnuplot"
=====end=====

5. バイナリの動作確認

> svm-train
等と引数無しで実行した時にエラーが出なければ
（使い方が出力されるだけなら）OK。

6. Python用 shared libraryのインストール

> cd python
> make     #../libsvm.so.2 が作成される
> sudo cp ../libsvm.so.2 /usr/local/lib/

7. Python用ライブラリ（スクリプト）の編集

# ライブラリをインストールする場所の確認。
> python -c "from distutils.sysconfig import get_python_lib; print get_python_lib()"
# 以下は「/Library/Python/2.6/site-packages」と出力された場合の例。
> emacs svm.py
「if sys.platform == 'win32':」後でパスを指定している箇所にて、
以下のように変更。元のインデントを保つように注意。
=====begin(svm.py)=====
#libsvm = CDLL(os.path.join(os.path.dirname(__file__),\
#                '../libsvm.so.2'))
cdll.LoadLibrary("libsvm.so.2")
libsvm = CDLL("libsvm.so.2")
=====end=====

8. Python用ライブラリ（スクリプト）のインストール。

> mkdir /Library/Python/2.6/site-packages/libsvm
> cp svm.py svmutil.py /Library/Python/2.6/site-packages/libsvm/
> touch  /Library/Python/2.6/site-packages/libsvm/__init__.py

9. Python用ライブラリの動作確認。

> python
>> from libsvm import svm
でエラーが出なければOK。

参考サイト: Installing libsvm-3.0 for Python on OSX 10.6

ACL-HLT 2011から面白そうな論文5件目。

---

出典情報: P11-1013: Yulan He; Chenghua Lin; Harith Alani, Automatically Extracting Polarity-Bearing Topics for Cross-Domain Sentiment Classification, ACL-HLT 2011

情報検索（Information Retrieval, IR）における検索対象であるドキュメントを自然言語処理して少しでも意味を汲み取って精度良くマッチングさせるためのアプローチとして「単語極性を考慮」するらしい。

前置き

評判分析と極性判定

アンケート調査やAmazonのレビュー等のように、自由記述テキスト形式で書かれた文章集合から価値ある情報として評判情報を抽出することを評判分析（Sentiment Analysis）と言います。評判情報分析、コメント分析、口コミ分析等とも呼ばれています（参考：「テキストを対象とした評価情報の分析に関する研究動向」）。分析の仕方や分析結果にもいろんな切り口がありますが、単語の極性（Polarity）判定では「その単語がポジティブに使われているか、ネガティブに使われているか、それ以外（中立的）に使われているか」を判定することでその後の分析に活用します。

極性判定の難しさ

GoodとかBadのような直接的に良し悪しが判断しやすい単語もありますが、例えば「Small/小さい」という表現を例にとると、ノートPCに関するレビューで「小さくて持ち運びに便利」というニュアンスで書いた言葉ならpositiveと捉えるのが自然ですが、一方でスマートフォンに関するレビューで「液晶画面が小さくて使いづらい」というニュアンスで書いた言葉ならnegativeと捉えるのが自然でしょう。突き詰めると文章毎に判定する必要がありますが、計算コストや実験設定の都合上「分野毎に大まかに判定する」形で評価していることが多いようです。

ベースになる先行研究としてJoint sentiment-topic (JST)があるらしい。JSTは、Latent Dirichlet Allocation (LDA)をベースにした確率モデルになっている。そのLDAは、「全ドキュメントがトピック数Tに分類される前提（固定値）で、トピック毎の単語出現確率を表す確率分布と、文章毎のトピック確率分布の紐付け方（紐付けるためのパラメータ）を推定するというアプローチっぽい。多分。（参考：朱鷺の杜Wiki、LDA入門、分野に依存しない単語極性を考慮した評判分析のための転移学習モデル、LDA (Latent Dirichlet Allocation) の更新式の導出）

この紐付けがうまくいけば、単語に対してトピックと極性情報の対からなる情報を付与することができる。この紐付けのためのパラメータを推定するのが大変というか工夫のしどころらしく、この論文ではLDA→JST→改善JSTという流れでその推定方法をより良くしようとしているのが主題っぽい。

JSTにおける2つの確率分布を紐付けるためのパラメータはいくつかあって、それらをうまく推定してやらないと精度が上がらない。その推定を（1）直接やる人もいれば、（2）バッファ的に何か別の処理を一度通すことで推定しやすくするという人もいれば、（3）パラメータに関与する因子を増やして精度高めようとする人等、様々なアプローチが試みられているようです。

例えば、大元のLDAではパラメータはαとβの2つなのに対し、LDAをベースにしたJSTではα・β・γの3つに増えています。これは、LDAではトピックzをパラメータαだけで分布を推定しようとしているのに対し、JSTでは単語の極性lを考慮するためにγパラメータを追加しているから。つまり、素朴に「トピック毎の単語出現確率を表す確率分布」と「文章毎のトピック確率分布」を直接紐付けることで文書集合を表現するだけでは不十分で、「単語の極性も考慮した方が文書がより適切に表現できるんじゃないの？」といった仮説を考え、前述の（3）のような考え方で因子を増やして対応したモデルを作りだしたのだろうと思います。（妄想で書いてます）

LDA→JSTは置いといて、この論文ではJSTをより改善するために、トピックが持つ語彙ベクトルφをパラメータβだけで分布推定するのではなく、極性ラベルSに基づいたパラメータλを導入することで単語極性をここでも考慮した分布になるように推定しようとしているっぽい。単純にまとめると、α側だけじゃなくβ側でも単語極性を考慮して推定したいらしい。それで「polarity-bearing」と呼んでいるかしら。

LDAからして「名前聞いたことある」ぐらいのレベルなんですが、自然言語処理に限らず特徴ベクトルを構成する要素にラベリングすることが必要で、そのラベリングが分野に応じて異なるケースでは汎用的に使えそうな枠組みですね。例えば、ドキュメント→画像として置き換えると、画像集合を特徴ベクトル集合で表現した上で、各特徴は何らかの概念的なトピックにおいてネガティブ／ポジティブ／中立な意味を有するものとして特徴毎に紐付けした解析しやすいモデリングができたりしないのかしら（妄想）。

一方、欠点というか気になる点としては、JSTでは「トピック」という言葉を使っていますが、これは概念的な用語であって実際にはそれが何を意味しているかは良く分かっていなさそうに見えます。ただ、文字通りのトピックとしても多義語とかいろんな問題でてくるだろうから、一概にこれが欠点という訳では無さそう。良し悪し置いといて、このあたりを俯瞰できる枠組みがあると面白そう。

ACL-HLT 2011から面白そうな論文4件目。

---

出典情報: P11-1012: Peng Cai; Wei Gao; Aoying Zhou; Kam-Fai Wong, Query Weighting for Ranking Model Adaptation, ACL-HLT 2011

Joint Annotation of Search Queriesと同様、ドキュメント検索時にクエリに対して適切なドキュメントを紐付けしようという話らしい。Joint Annotation との違いは、クエリをアノテーションすることで意図を解釈しやすくしようというのではなく、直接クエリを特徴ベクトルとして表現した上で、「既に別の問題領域で学習済みの知識」を活用することで重み調整することで高精度で紐付けましょうという点。

前置き

ランキングアルゴリズム

ある検索要求（ここではクエリ）に対して適切だと思われるコンテンツ（ここではドキュメント）を提示するため、その適切さを何らかの形で点数化し、順位付けるためのアルゴリズムの総称。有名どころはご存知PageRank。ただし、Blog、SNS、Twitter等のユニークなURL付きコンテンツの増加といった環境変化の影響も少なくなく、常に改善が試みられており、今回の論文はその一例です。

特定ランキングアルゴリズムに特化することの問題

検索って便利ですよね。でも何事にも良い面悪い面があるものです。例えば、Coding Horror: Googleに問題アリではスパムサイトを例に問題点を指摘しています。

他にも、例えばGoogleがデファクトスタンダードになってしまうと、事実上Googleの恣意的な考えに基づいてランキングされてしまう一種の検閲に近い状況になってしまうことを問題視している人も少なくないようです。

ここで気に留めて欲しいことは、Googleのランキング手法に問題があるという点ではなく、どのような手法であれ（人手による判断であっても）何らかの作用を受けたランキングになってしまうということです。なので、なるべく「何らかの作用」ができるだけ分かりやすい形で明示されており、作用の種類が自由に選べるぐらい豊富にあるような世界が好ましいだろうと考えています。

（Twitterでもfavotterとかが一つのランキングを実現していますが、今のままで面白いという人もいれば、Twitterが広まり過ぎて上位に来るツイートが有名所ばかりになってつまらないという人もいるでしょう。どちらが良いというよりは、どちらも、それ以外にもあった方が楽しみやすそうですよね）

クエリに適切なドキュメントを紐付けるという問題設定において、
　・クエリ：要求そのもの
　・ソース文書：既にある程度学習した知識を有する問題領域（ドキュメント群）
　・ターゲット文書：今回改めて紐付けしたい問題領域（ドキュメント群）
と用語を使い分けているらしい。

検索対象がAmazonみたいな商品の場合でもそうですが、Webページの場合にはそれどころじゃないぐらい対象が多い。Webページ全てに教師データを用意することは当然不可能なので、教師データを用意する試みがいろいろあります。一つは先に紹介した能動学習（Active Learning）のように「ある程度教師データを用意したからこれを元に学習進めておいて、難しい所は聞いてね」というもの。この論文では能動学習とは異なる方法がベースになっていて、転移学習（Transfer Learning）や知識転移（Knowledge Transfer）と呼ばれる「関連したドメインの知識やデータを転移して目標ドメインの問題をより高精度で解く」ことで教師データの準備コストを削減するアプローチの一種らしい。

この転移学習をベースにしたランキングアルゴリズムを Ranking model adaptation と呼んでいるらしい。異なる領域で学習した知識なりを転移して使うことになるので、領域同士が似ている方がより効果的に学習できるっぽく、クラス分類の転移学習においては（多分その似ている事例を識別して）インスタンスへの重み付けを行うことでうまくいくということが示されているらしい。

一方、そのクラス分類学習における転移学習と、ランキングにおける転移学習には、質的な違いがありこれが大きな問題になる。具体的には図1に示される通り、クラス分類におけるインスタンスは「ソースもターゲットも文書だけ」なのに対し、ランキングでは「クエリと文書の2種類あり、文書がどのクエリに属するか」が存在することを考慮する必要がある。つまり、「どの文書がどのクエリに属するかの情報」を考慮してやらないと高精度な学習結果が得られないはず。

この問題を解決するために、クエリの段階で重要度を直接算出したい。そのイメージが図2に示されていますが、「転移元と転移先において、文書集合が似ているクエリ同士は転移する価値が高く、似ていないなら転移する価値が低い」というようにクエリに紐付けた知識毎に価値を重み付けする（Query Weighting）っぽい。従来の手法だと、クエリが特別扱いされてなく、「素朴に文書アイテムに対して重み付けする（document instance weighting scheme）」形で転移学習しようとしてしまうため、どの知識が似ているかどうかの判断がしづらいらしい。

ところが話は簡単ではなく、クエリの価値を推定するのが（多分計算コスト的に）容易ではないので、(1)各クエリを文書インスタンスを加味した特徴ベクトルに圧縮してから重み付けする方法、(2)ソースとターゲットのクエリ間で類似度を算出することでクエリの価値を算出する方法を提案する。というのがこの論文の主題らしい。

上記2手法を評価するため、計算機実験ではLETOR3.0に基づいたベンチマークとしてTREC-2003とTREC2004で比較検証しているらしい。LETORは「Learning to Rank for Information Retrieval」の略らしい。へー。実験では転移元と転移先をHP03→TD03、HP04→TD04、NP03→TD03、NP04→TD04の4ケース分で結果を確認していて、DSモデルベースで重み調整した方が良い傾向（重み調整無し時で50~70%に対し、4ケースとも数パーセント改善）にあるらしい。ただ、重み調整の仕方によっては「重み調整しない方が良い」ケースもあるので、要調整なんだろうなと想像。

いずれにせよ「素朴にドキュメントと同様に扱う」のではなく、クエリで結びつけたドキュメント集合をクラスタ的に扱って調整してみるというアプローチは面白い。精度的には思った程改善していないように見えるのは、教師データにノイズがあることを加味したアプローチになっていないのが主要因なのかしら。それともこれぐらいの改善でも結構凄いのだろうか。

ACL-HLT 2011から面白そうな論文3件目。
面白そうと書きつつ自然言語処理にそれほど詳しくないから誤解してる部分多々ありそうなんだけど。

---

出典情報: P11-1011: Michael Bendersky; W. Bruce Croft; David A. Smith, Joint Annotation of Search Queries, ACL-HLT 2011

検索エンジンにおいて検索窓に入力される文字列はクエリと呼ばれています。そのクエリをhogehogeしましょうという話らしい。

前置き

クエリから意図を読み取るのは難しい！

一般的にクエリは検索対象となるドキュメントと比べて圧倒的に情報量が少ないです。キーワード1つとか2つといった状況や、構文がハッキリしない曖昧な文章っぽいものが入力されるケースも少なくない。そういう状況下で「ユーザが求めているドキュメントはこれだ！」という判断をする必要がある。単純なキーワード・マッチングだけだと検索漏れが多すぎるので、なんとか工夫して意図を汲み取りましょうという研究事例が多いらしい。

意図を汲み取るために使われる技術の例（＊注1）

例えば、自然言語処理でいうと、以下のような技術を利用されます。

・形態素解析, タガー(tagger): 単語単位で品詞を判定する。
　→動詞や名詞判断すると少しは意図が汲み取りやすくなるかも？
・構文解析, パーサー(parser): 文を句や節単位に区切り、それらがどのような構造になっているかを解析する。
　→クエリに現れた名詞はどんな単語が形容しているのか、作用しているのか、名詞を対象とした何を探そうとしているのかといった情報を利用して意図を汲み取れないか？

ある程度ボリュームがあって綺麗に編集された文章ならばこれらの技術を利用しやすいですが、クエリの場合には文としても不自然だったり不十分だったりするので、既存技術を単純に利用するといったことが困難！　ということで様々な取り組みがあるらしい。

クエリにおける自然言語処理以外の解析例

クエリは確かに文章としては扱い難いのだけど、文章とは異なる特徴もあり、それを利用して意図を汲み取ろうとする解析例もあります。

例えば「一つ目のクエリでめぼしい結果が得られない場合、続けて複数回異なるクエリで試しやすい」という傾向を利用して、時系列順に複数クエリをグルーピングすることができます。これを利用して、そのグルーピングされたクエリ集合をクラスタリングすることで似たクエリ集合を作り、それらの時系列情報を利用して「こういう順序でクエリを入力するユーザはこういう情報を得ようとしている可能性が高い」といったことを抽出しやすくなります。

「もしかして」も、似たクエリ集合から追加キーワードとかキーワード自体の編集を促そうとする形で望んでいるだろうページへの誘導を図る例ですね。ただし、追加キーワードについては割と単純な話じゃなく、「そもそもユーザのクエリがおかしい」ケースも多々あるので、適切な追加キーワードを精度良く提供するという話もあるらしい。

そしてクエリ拡張へ

良く分からないのだけど、「クエリ拡張(query expansion)」というキーワードがあって、こういう「クエリから得られる情報を増やす」とか「クリックされる頻度を利用して返すコンテンツの順番を調整する」といったことでクエリ⇄コンテンツのマッチングを改善する手法の総称をそう呼んでいるのかなと想像。Wikipedia見る限りでは自然言語処理寄りっぽいけど。

この論文におけるベースになる部分は、クエリから意図を汲み取りやすくするために、「ある程度文章っぽいクエリ（例文: who wan the 2004 kentucky derby）」に対して各単語に下記3種のアノテーションすることが大前提になっているらしい。
　・CAP: 各単語が小文字／それ以外。
　・POS TAG: 名詞／動詞／それ以外。
　・SEGmentation: チャンクの開始／チャンクの中。（チャンク＝文節等の塊）

上記のアノテーションがある程度実現出来ているという前提で、それらを利用してクエリを適切に（言語学的に）構造化したいということらしい。イメージ的には、単語毎にアノテーションされている状態から、「単語1番目と単語2番目」といったシーケンシャルな単語集合（shallow sequence）に対して「1つのクエリ語句(a single query term)」であるというアノテーションをしたいっぽい。多分、先の例文でいうところの「who wan the 2004 kentucky derby」では「who wan」、「the 2004 kentucky derby」という2つのサブクエリが組み合わさった一つのクエリなんだ、ということを認識しようということなのかな。この部分がタイトルにある Joint Query Annotation のことっぽい。

SEGmentationタグだけでもこのぐらいならできそうだけど、実際にはこんな綺麗な文章だけじゃないので、CAP、TAG、SEGを組み合わせて利用することでより精度良く Joint Query Annotation を実現しようという試みなんだと思います。

実験では、3種のアノテーションを独立した状態で Joint Query Annotation させた場合(i-QRY, i-PRF)と、3種を組み合わせて利用する場合(j-QRY, j-PRF)とで比較検証しているらしい。ただ、ここを見ると「i-QRY, i-PRF」では、CAP,POS,SEGmentationのアノテーションを独立して処理していて、「j-QRY, j-PRF」ではその3種を合算して最適化する処理をしているように見える。何が違うかというと、3種アノテーションする際に「前者は一度付けたらそれをそのまま正解とみなしており、後者は他アノテーションとの兼ね合いからちょっとおかしそうだから調整し直そうとする」という違いに見える。

大分斜め読みしてるのでどっちの解釈が正しいのかは良く分かってませんが、どちらのアプローチもありだよね。

P.S.

生駒日記によると、
本研究では、これらの3つの系列ラベリングのタスクを同時学習することで、精度を大幅に向上させることができた、という話。

と読むのが正しいらしい。後者の方が正しかったか。

---

＊注1: 実際にはユーザの意図を必ずしも汲み取る必要はありません。結果的にユーザが望んでいる検索結果を提示できれば、クエリに対して望む結果を提示することができれば良い。ここではイメージしやすいようにこう書いています。

ACL-HLT 2011 から面白そうな論文2件目。

---

出典情報: P11-1010: Qixia Jiang; Maosong Sun, Semi-Supervised SimHash for Efficient Document Similarity Search, ACL-HLT 2011

MinHashじゃなくてSimHashなんてものがあったのね。

前置き

N次元特徴ベクトルとして表現することで対象間の類似度を求める

機械学習の多くがそうですが、何かを解析しようと思った場合にはその対象をN次元の特徴ベクトルとして表現することが多いです。どのようにベクトル化したら良いのかは腕の見せ所ですが、適切なベクトル化が実現できるなら、後はそのベクトル同士がどのぐらい似ているか（距離が近いか、角度が近いか、大きさが近いか、etc.）といった問題に落とし込むことができます。同一ベクトル空間に存在する（同じ土俵にいる）なら、その空間上でどのぐらい似ているかを計算（類似検索や近傍探索など）することで「関連商品」とか「類似画像」とかを求めやすくなるわけですね（＊注1）。そのベクトル間類似度を図る指標にはJaccard係数やTanimoto係数等の様々な方法が提案されています。

計算コストを抑えるために擬似的な類似度を高速に求める

ここではそれらを用いて類似度を測れるということが分かっている場合の話（もし図れないのなら適切な類似度を測れる指標自体を考える所からやる必要がある）。ちゃんと図れるんだけど、検索エンジン等の大規模なデータ集合に対して計算する必要がある場合、その計算量が馬鹿にならず事実上そのままでは使えません。それを擬似的に高速に求めましょうというのがMinHashです。MinHashを更に改良した話もこのブログに紹介されていますね。

局所的に鋭敏に反応するハッシュ関数群を用いる手法: LSH

今回この論文タイトルにでている SimHash も基本はハッシュ関数を使ったもので、別名 LSH (Locality Sensitive Hash) とも呼ばれているらしい。正確にはLSHの一例がSimHashということらしい。先に紹介したMinHashもLSHの一例。いずれにせよLSHなら聞いたことあるよー（＊注2）。（SimHashってなんだろうと気になって選んだのでこの時点で興味が半分薄れてしまった）

SimHash(LSH)は、「類似度の高い特徴ベクトル同士は同じハッシュ値になりやすい」ように設計されたハッシュ関数を使うことで「最近傍探索」することで類似度計算を近似しましょうというもの。LSHで良く耳にする実装例としてLikelike（リケリケ、と呼ぶらしい）があります。一種のクラスタリングともみなせるけどかなり特殊で、「同じハッシュ値になるものは似ている事例」にはなりやすいけど、所詮ハッシュ値なので「ハッシュ値」そのものには意味が無く、「近いハッシュ値」に該当する事例が似ているかどうかは相関が無い(はず)のがちょっと残念。（クラスタリングなら各クラスタからの距離を計算することでどのぐらい似ているかの指標を計算することもできる）

論文タイトルには「Semi-Supervised SimHash」とあるので、完全に自動化した手法ではなく、例えば先の能動学習のような形で半自動的にSimHashする手法を提案するというのが趣旨なのかなと想像。LSH良く分からないけど。

アブスト読む限りでは「教師無しLSHは性能が十分じゃない。かといって教師ありLSHでも類似ドキュメントを検出するには十分ではない（ハッシュ値が近いからと言って似ているという話にはならないので、同じハッシュ値にならないと類似ドキュメントとして検出できない）。そこで、類似データが同じハッシュ値となりやすいように事前に重み調整してやることで精度改善を目指す」みたいなことを提案しているらしい。

なんとなく大枠は分かったし、これ以上はLSH/SimHash自体をちゃんと勉強してからじゃないと理解し難そうなので、今回はここまで。

---

＊注1: 適切に特徴ベクトルそのものを(半)自動生成することはできないのだろうか。

＊注2: 上記注1に関連して、「ランダムにハッシュ関数を大量生成して特徴ベクトルそのものを自動生成するために利用できないかなー」とか考えてるのだけど、どうなんだろう。既に作られてる特徴ベクトルから有益な特徴空間に圧縮するという話ではなくて、ベクトル化される前の生データ（文章だったり写真だったり音声だったり）から自動生成させたい。

「自然言語処理分野で世界最大の国際会議ACL-HLT 2011の論文が公開されました」ということらしいので、Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-HLT 2011)から面白そうな論文をリストアップしてみます。

ちら見した感想も書いてありますが、ざっと眺めて気になった点を書いてあるだけなので事実と異なる可能性もあります。気になるなら原本読みましょう。

---

出典情報: P11-1005: Ines Rehbein; Josef Ruppenhofer, Evaluating the Impact of Coder Errors on Active Learning, ACL-HLT 2011

能動学習におけるアノテーション・ノイズが精度に及ぼす影響を評価してるっぽい。

前置き
「能動学習」は機械学習の一種。一般的な教師あり機械学習では、予め正解を付与した事例集合からそれらを分類したり類似判断したりするための有益な判断基準を自動抽出するのに対し、能動学習では抽出した判断基準を用いて未知の事例集合について判断した結果に自信が無い場合、それを人間に質問して正解を確認しながら学習します。つまり、少しずつ事例集合を増やすという対応ができるので、最初から大量の正解事例を用意することなく、苦手な（判断が困難な）事例を判断しながら事例を増やしていくことができたりするので、事例を用意する手間を大きく省けることと、事例自体を追加し続けることができる点が嬉しい。

ここでのアノテーションは、ここでは事例に与える正解と考えてもらって良さそう。つまり、アノテーション・ノイズとは、ある事例に対して与えられた「正解」に誤りが含まれること。人間が手作業で付けるので、判断ミスもあればタイプミスもあるかもしれない。一人の人間だけじゃなく複数の人間で作業することも多いので、個々人の判断基準がそれ難いので、用意された「正解」にも誤りが含まれ得るということです。このノイズが学習に及ぼす影響を調査してみた、というのがこの論文の主旨になります。

一つ目の実験設定としては下記3ケース、
　・rand: ノイズ含んだ事例集合からランダム・サンプルした学習、
　・ALrand: 事例に付与されたクラスをランダムにN%変更するノイズ（片寄無し）を付与した状況での学習、
　・ALbias: 同様のノイズをバイアス付けて付与した状況での学習、
についてノイズの割合を増やしながら比較評価してるらしい。（図1を見ただけで見て取れる結果なだけで読み違えている可能性があるけど）意外なことに結果は、
　・エラー率が低い状況（10％ぐらいまで）: 「rand＜ALrand＜ALbias」の順で精度が良く（「落ちにくい」と読むのが正しい？）、
　・10〜20％ぐらいでは「rand≒ALrand＜ALbias」、
　・20〜30％ぐらいでは「ALrand＜rand＜ALbias」
のように、付与したエラー率によって順番が変わってくるらしい。大雑把な傾向として「rand≒ALrand」や「rand≒ALrand＜ALbias」なのは直感に符号するのだけど、「rand≒ALrand」についてはノイズの割合が変わると割と顕著に差が開くらしい。やってることは質的には同等に見えるのだけど、影響が異なるらしい。一体何故。

その原因を追求するためなのかは分からないけど、筆者は過学習のリスクや能動学習初期段階における判断精度の低さが要因となる問題を避けるために「能動学習時に教えてもらう教師データを鵜呑みするのではなく、そのデータとこれまでの学習結果を組み合わせることでより一般的な特徴ベクトルを生成する。（多分全クラスN個分に対して同処理を行う）。その後、N個の分類器とoracle（システムからの質問に答える人）の関係からそれを学習するのに適切か否かを判断し、適切ならば学習する。適切じゃなければ学習しない。（例えば、全分類器がagreeしてるのに、oracleがdisagreeという状況ならrejectする）」というアプローチを提案しているらしい。実際にはもうちょっと細かいことやってるようだけど、合議アルゴリズムのような形で学習すべきか否かを判断させている訳だ。

結果は、図3を見る限りでは「どちらかというと悪く作用している（精度が落ちやすく見える）」ように見えるのだけど、考察を読む限りでは改善しているらしい。あれ、図の見方間違ってる？（表2では良くなってるところもあるけど、どの時点での精度なのか良く分からず）

ノイズが完全に無いデータなんてのは非現実的だと思うので、意図的なノイズにせよノイズが精度に及ぼす影響とそれを踏まえた学習手法の改善策としては面白いですね。

学科システム落ちてる間にmixiに投稿済みの内容ですが、学生向けという意味でここでも紹介。

ほんの少ししか手伝いできていませんが、ANPI NLP というプロジェクトを通したボランティア活動をしました。某所への寄稿したものなので、ここでは圧縮してかいつまんで紹介してみます。いろんな支援の仕方があるよね、という意味を込めて。

---

　ほんの数年前までのソーシャル・ネットワークでは人間関係を構築する場といった側面が強調されていましたが、今回の震災を切っ掛けに、緊急を要するタスクとして認知し合った人らを中心として繋がり、互いに知識やデータを提供し合い、タスクを分割して協力するといった具体的な活動を行う場やその活動を支援する場（ソーシャル・メディア）としても有効に機能し始める時代へとなってきました。

　活動の一例として、Googleのパーソンファインダー（消息情報）。
（*1）Google Person Finder (消息情報): 2011 東日本大震災
　http://japan.person-finder.appspot.com/

　パーソンファインダーは、インターネットを介した人海戦術によるアプローチ。これ以外にも、専門知識を有する人らがプロジェクトとして協力し合う活動も現れました。

（*2）ANPI NLP (東日本大震災のためのデータマイニング・自然言語処理に関する情報のページ)
　http://trans-aid.jp/ANPI_NLP/
（*3）sinsai.info (東北沖地震 震災情報サイト)
　http://www.sinsai.info/
（*4）Twitter 上の大震災関連「救命・救助要請情報(#j_j_helpme・#311sppt 関連)」要約 & 通報支援サイト
　http://www.selab.cs.tut.ac.jp/~aida/
（*5）東北関東大震災　安否情報　横断サーチ
　http://trans-aid.jp/ANPI_IR/ja/

　（*2）のANPI NLPでは、楽天技術研究所（以下、楽天技研）の萩原さんの声かけにより主に自然言語処理やデータマイニングと呼ばれる分野で活躍している専門家が集い、「Twitterなどから得られる安否確認情報を照合、更新することでPerson Finderの情報を充実させること」を大きなタスクとして取り組まれています。

　そもそもの始まりは、楽天技研の萩原さんによるツイート「こういう緊急時にも自然言語処理が役に立てることはたくさんある。（中略）特に今必要性が高いのは名寄せ技術だと思う。被災者・安否不明者の表記揺れに困っている自治体とか多そう。」のようです（*6）。

（*6）言語処理屋さんが連携していく様子
　http://togetter.com/li/111529

　このツイートを切っ掛けに、
　・Google日本語入力Mozcを開発されている工藤さんがデータ提供。
　・地震を含むツイートを収集していた大阪大学の松村先生からデータ提供。
　・京都大学のGraham Neubigさんから人名・地名モデルの提供。
といったアクションが高々数時間のうちに行われました。このスピード感で進む様子を受けての判断だったのだろうと想像しますが、翌日になる3月15日にハッシュタグ #anpi_nlpとしてTwitter上の情報集約が開始され、加えて情報通信研究機構の内山さんからの提供によりMedia Wiki上での整理が始まりました。切っ掛けとなる最初のツイートから僅か1日後のことでした。

　こうしてANPI NLPが始まり、前述の目的を達成するためのタスクが用意されました。ここで用意された当面のタスクとは、地震関連のツイートデータ約6万件が既にあり、これらのツイートが「安否情報を含んだツイートなのか（もしそうなら人名や地域名がどこに記述されているか）」「救助要請を含んだツイートなのか」「関係のないツイートなのか」といったことを人手で判断し、目印を付与するというものでした。この目印を付与するという作業は、直接的にはコンピュータで処理しやすくなる（パーソンファインダーの情報と照合しやすくなる）というのが利用目的になりますが、それだけではなく間接的な効果にも期待しての人海戦術でした。

　この間接的な効果の例として、分類器の構築があります。分類器とは、入力されたツイートを「安否情報を含んでいるツイートか／そうではないのか」といったYES/NO形式で分類したり、「生存を確認したツイートなのか／死亡を確認したツイートなのか／安否確認の情報を求めているツイートなのか／それ以外なのか」といった複数選択肢のどれに該当するかを自動で分類してくれるシステムのことです。もし、現時点でのツイートデータ6万件についてのみ処理したら全てが終了するというのであれば、全てを人手で処理することも考えられますが、実際には関連ツイートは日々収集され続けます。それら全てを人海戦術で判断するのは事実上不可能のため、少しでもその手間を和らげるために自動化しよう。その自動化をするための技術として、人手で付与した正解データ（分類結果）から「どのように分類するのが最も妥当か」を自動で学習する技術である分類器を使おう。こういった効果を狙っての試みでした。

　3月24日現在では、当初の目的であるパーソンファインダーへの寄与に関しては楽天技研を中心として続けられ、それ以外の災害支援タスク（安否情報ツイートと避難所を関連づけるタスクや、外国語に機械翻訳するといったタスク等）についても提案され、少しずつその結果が出始めているようです。日々更新されている状況ですので、詳細はANPI NLPのサイト上にてご確認頂ければと思います。

　以上、ソーシャル・メディアを通した活動例を紹介すると共に、自然言語処理屋の皆さんが構築されている成果物を利用している一人としてANPI NLPに賛同し、関わった活動内容の一部を紹介してみました。この活動が震災支援の一助となれば幸いです。