« January 2008 | Main | March 2008 »

2008.02.27

最近買った専門書

衝動買い三冊

まだざっとしか読んでない。

・Numerical Recipes: The Art of Scientific Computing 第3版 amazon サイト
 出たばっかり。いろいろ批判も多いかもしれないけど、なんだかんだで参考になります。機械学習系のネタが増えたりとか中身は更に増えてますね。数値最適化の技術も最新の話がいろいろ

・Average Case Analysis of Algorithms on Sequences amazon
シーケンシャルなデータの平均計算量の解析というすごいピンポイントの分野で私にど真ん中。使っている技が見たことが無いのが多い。複素解析とか使うんだと。

・Pattern Discovery in Bioinformatics: Theory and Algorithms amazon contents

バイオでのいろいろなパターンマッチングの技法。permutation pattern matchingとかは初見でした。バイオ特有の話もいろいろ学べました。

| | Comments (153) | TrackBack (0)

tx-0.08

txを0.08にアップデートしました。
・setArray()を追加しました. これでmmapが使えるようになります。
・commonPrefixSearch(), predictiveSearch()の引数が違うバージョンを追加しました
(元々あったが、説明してなかった)
・サンプルプログラムにtxsearch_mmapを追加しました.

| | Comments (46) | TrackBack (0)

2008.02.15

線形識別器チュートリアル

ワークショップ中の夕食で話したのですが、今のところ日本で(素性関数ベース&線形識別器)機械学習のいろいろな手法をまとめて体系的に教えてる資料などがあまりないなぁという話をしていました。

で、探すと、このあたりの大部分をまとめて説明しているいいチュートリアル(英語)がありました。
夏の学校資料[pdf]
その他のコードやリンク

ちょっとだけ解説

現在自然言語処理の多くで使われている学習器は線形識別器です。
入力x(例:単語、文、文書)から出力y(例:品詞、品詞列、文書のトピック)を予測したいという場合は、(x,y)のペアからいろいろな値を取り出し(x,yのペアから値を取り出す関数を素性関数と呼ぶ)、その値を並べたベクトルを素性ベクトルと呼び、f(x,y)とかきます。そして、その素性ベクトルf(x,y)と同じ次元数を持つ重みベクトルwとの内積を測って、その値が正か負か、または大きいか小さいかを調べて、出力は何が尤もらしいかを予測します。

機械学習では、この重みベクトルwを正解データの集合(x_1, y_1), ..., (x_n, y_n) を使って、推定(普通は訓練と呼ぶ)します。正解が正しくでるようにwをチューニングするわけです。このチューニングは基本的には訓練データから各素性に関する統計量を取り、最適化問題を解く事で行われます。

例えば、入力が文書で、出力が「その文書がスパムだったら正の値、そうじゃなかったら負の値をとる」、という問題の場合は、まず、実際にスパムかどうかのラベルがついた文書集合を集めます(もしくは自分で作る)。次に素性関数を設計します。文書分類の場合は単語の出現が重要な情報となるので、各単語が1次元分を担当し、各素性の値は例えばその出現回数とすることが多いです。

素性関数1, 2, 3, 4がそれぞれ単語"Best","Drug","Congratulation","flower"に対応するとしたら、訓練データを使って重みベクトルを訓練すると、重みベクトルは(-1, 3, 1, -2)というふうに、drug, congratulationが出たらスパムとなって、best, flowerが出たらスパムじゃないとなってくれるように学習されます。

それで文書として、best, drug, congratulation, flowerという単語がそれぞれ、1, 3, 0, 1回出現しているものが与えられたら、その素性ベクトルは(1,3,0,1)であり、重みベクトルとの内積は -1*1 + 3*3 + 0*0 + 1*1 = 9 となり、これは正なのでスパムとめでたく判定されるわけです。

線形識別器は非常に単純ですが、それでも自然言語処理だと有効です。理由の一つとして、次元数が非常に大きく(例えば数千万次元とか)、線形でも十分区別する能力があるということがあげられます。

で、問題はどのようにこのwを訓練するかということになり、これには、いろいろな方法があります。例えばNaive Bayesは一番単純なモデルです(それでも強力だが)。このモデルでは各次元が完全に独立だとし、それぞれ独立に学習、推定し、結果をまとめます。

もうちょっと賢い線形識別器だと、各素性は独立じゃなく相関があるものだとし(推定時は独立に扱うが)、学習時にどのような基準(損失関数)で学習するかも工夫されてます。

有名なのだと、出力が簡単な問題(例えば文書分類とか二値分類)を解こうとする場合は次のようなものがあります。
- 線形対数モデル(最大エントロピーモデル、ロジスティック回帰)
- (Linear) Support Vector Machines

出力が構造を持ってる場合、例えば系列(品詞列とか形態素列)とかの場合は、上記のそれぞれが次のようなモデルに拡張されます。
- Conditional Random Fields (条件付確率場)
- Max-margin Markov Network
これらのモデルでは出力、素性、損失関数が部品に分解できるようになっており、出力の候補数が入力長の指数個に比例する数ぐらいあっても動的計画法などで効率よく学習/推定ができるようになっています。

あとは、実装が非常に簡単だけど強力な次のような手法があります。これらはオンライン学習、つまり訓練データを1例ずつ見てパラメータを更新していきます。
- Averaged Perceptron 
- Structured Perceptron 
- MIRA

これらについては上記のチュートリアルにまとめられてます。

#あるといっても広く知られるためにも、やはり日本語の資料もつくりたいですね。

| | Comments (34) | TrackBack (0)

2008.02.14

txをアップデートしました。

tx ver0.07にしました。
・expansionSearch()となっていたのを分けたバージョンのcommonPrefixSearch(), predictiveSearch()を追加
・キー登録数を返すgetKeyNum()を追加
・ソースもちょっと整備しました。

bepとか、他のソフトウェアも時間見つけて、ぼちぼちアップデート、リリースしていきます。

| | Comments (26) | TrackBack (0)

T-FaNT2の話

T-FaNT2が昨日と今日行われました。
(ホームページではT-FaNT08となってますが2008年中にもう1回開くかもなのでT-FaNT2と呼ぶことにします)

いろいろな分野から、その道の第一人者が来てくれて大変面白かったです。
発表者のみなさまありがとうございました。
2,3行ずつ簡単なメモ。間違った理解だったらごめんなさい。

"Latent Variable Models in NLP"
様々なモデル(構文解析、統計的機械翻訳など)で隠れ変数を加えて高い表現力を持つモデルを自動的に求める。Dirichlet過程とか言語知識を加えた(でかい)グラフィカルモデルのおかげで、昔の単純な隠れ変数があるモデルより高精度、柔軟性が高い。ここ数年で非常に強くなっているBerkeley NLP groupの力を感じました。開発された手法・技法をいろいろな分野に適用する速さ、勢いが気持ちいい。

"Dualized L1-regularized Log-Linear Models and Its Application in NLP"
私の発表。L1正規化使うとスパース、コンパクトなモデルが得られるが、それを双対にしたら、パラメータ数が素性数でなく、訓練データ数に比例するようになるので、組み合わせ素性が有効かどうかを効率的に求められるなど、いろいろ素性設計側で面白いことができる。IBISではできなかった組み合わせ素性の自動抽出とか文書分類の実験を追加したのですが、導出とかを分かりやすく説明するのはもうちょっと時間ください・・。力を。実装は公開したいなぁ

"Predicate-argument analysis with DAG parsing"
Shift-Reduce係り受けパーサーを拡張しDirected Acyclic Graphを推定できるようになる、述語項解析などが直接できるようになる。そんな複雑な構造がgreedyな操作列で出せるのと思うのだが結構うまくいく。projectivize(交差する係り受け関係を交差しないようにする変換)が実は遠距離情報をうまく伝えているのかもというのが面白い

"Leveraging User Annotations in Sentiment Summarization"
レビューを各アスペクト毎(電気製品だったらスペックとか)にまとめる。ローカル、グローバルの両方の基準でトピックをとりだすとローカル側できれいにアスペクトがとられる。クラスタリングに対する制約を、別問題がうまく解けるようにするという形でいれるとうまくいくのが面白い。ryanさんもbayesかと思いました

"Learning to Rank: From Pairwise Approach to Listwise Approach"
情報検索などのランキングを正解データから学習。順列上に定義される確率分布を使って訓練データとのKLが小さくなるように学習。精度上がる。今回のモデルはどのクエリにも同じパラメータを使うことになっていたが、クエリ毎にヒットする文書集合は違うから、それを計算量が増えない範囲でどのように入れられるかだなぁ。

"Conditional Random Fields Incorporating Incomplete Annotations"
出力の一部分しか正解をつけていなくても、付けてない所はラベルがどれでも正解という形で学習してしまうとうまくいく。計算量はfoward backwardで効率的に解ける。ルールで自動的につけて一部分に正解つけて、学習したら面白そう

"Semi-supervised Learning for Structured Output Variables"
正解無しデータを生成モデル(っぽいもの)で学習してその結果のパラメータを識別モデルに入れてしまう。そして識別モデルの学習結果からまた生成モデルっぽいものをまた学習。こんな簡単のでそんなにうまくいくのと面白い。半教師学習で現時点で最高精度。

"Comparative parsing evaluation across different grammar frameworks"
最近、HPSGとかCCGとかいろいろな文法理論に基づく「実際に動く」深い構文解析と、penn treebankとかのcollins/charniak parserとかの浅い構文解析を比較するために、共通のフォーマット(この話では木構造)に変換。変換も学習。

"Towards Framework-Independent Evaluation of Syntactic Parsing"
前の話は木構造だったが、こっちでは共通の意味役割のラベル付き係り受けに変換。変換がさらに難しくなっており、もう学習できなく頑張って変換ルールをかく。こちらのほうがよりアプリケーションの評価に近い(と思う)のだが、変換自体が大変なタスクになってる

"Two Topics in Statistical NLP: the Jeopardy Model and an M-Estimator"
二つの木を協調して確率的に生成するStochastic synchronous grammarのより一般的なモデルのJeopardy Modelを使ってQ&Aの、質問の木(構文解析後)と正解候補の木の一致度合いを測る。M-estimationは私が前紹介[pdf]したやつだが、やはり素性が自由に設計できた上での生成モデルと識別モデルの性能差が気になる

"Collapsed Variational Inference for Hierarchical Dirichlet Process"
階層的に生成するモデルの一番最初のprior parameterをさらに上にpriorのせて学習する。collapsed、つまり目的とする変数以外は解析的に積分してしまい、残りでVariational Inferenceをするのだが、conjugateじゃないので、なるように変数を追加。

"Nonparametric Bayesian Approach for The Distributional Hypothesis"
単語のトピックを調べるために直前のN-1単語のコンテキスト情報を使う。単純にN-1単語使うとスパースになっちゃうので、HDPを使う。その単語の直前のコンテキストだけじゃなく、直後のコンテキスト(とかその同じ文中とかでもいいけど)も使いたいが生成モデルの枠組みではきれいに記述するのは難しいかな

"Present and Future of a Text Modeling"
最近のいろいろなトピック型モデルの比較と拡張。言語モデル上でのキャッシュモデルとかバックオフとかも純粋な生成モデルの枠組みで説明できるのがおもしろい。N-gramよりさらに複雑な情報(例えば係り受けぐらいからでもいいが)が生成モデルの枠組みで説明できたら面白い。

| | Comments (47) | TrackBack (0)

2008.02.04

T-FaNT2 ワークショップのお知らせ

私が所属する辻井研究室主催で自然言語・機械学習に関するワークショップ T-FaNT2が東大小柴ホール@本郷で2/12, 2/13に行われます。

T-FaNT2ホームページ

発表者は世界でバリバリ活躍する自然言語処理で若手のよりすぐりの人が集まります。(リスト
(自由に呼んでいいとのことだったので自由に呼んじゃいました)
例えば、係り受け解析にMST(最小全域木)アルゴリズムの適用を創始したRyan Mcdonaldさんとか、いろんなタスクで登場してぶっちぎりの精度を出して任天堂のマリオ的なプレゼンをしていくAria Haghighiさんとか。
Baysianの方も持橋さんをはじめ世界のトップランナーの方がやってきてくださります。

自然言語処理と機械学習の融合の最先端を聞いてみたいという方は是非お越しください。入場は無料です。
但し発表は英語ですので、その点注意してください。また、結構濃い話ばかりなのでアブストを見て予習をしておくとより楽しめるかと。

#参加人数を確認したいので参加希望の方は

1. 氏名:
2. 所属組織:
3. 職(教員、研究者、技術者、大学院生など):
4. 参加日(丸をつけてください): 一日目 2日目 全期間

を書き2月7日までに私宛(hillbig ○ is.s.u-tokyo.ac.jp、○のところを@にかえてください)に連絡していただけると幸いです。当日参加も大丈夫だとは思いますが。

よろしくお願いします。

| | Comments (70) | TrackBack (0)

« January 2008 | Main | March 2008 »