Não Aqui!

Xiaojun Wan. An Exploration of Document Impact on Graph-Based Multi-Document Summarization.

重要文抽出タスクの既存手法として，文をノードとし，文の（コサイン）類似度をエッジとしたグラフを構築し，PageRankアルゴリズムで，文の重要度を計算する手法がある．この手法の問題点は，文の重要度が文間の類似度のみで決まってしまうことである．すなわち，ある文vがあるとき，その文が属している文書d_vのトピックの中心性や，d_vにおけるvの出現位置に基づく重要度などのファクターを取り込むことができない．

本論文は，文uとvのエッジの重みw_{uv}を，次式で計算する．

• w_{uv} = sim(u, v) {λ π(d_u) ω(u, d_u) + (1 – λ) π(d_v) ω(v, d_v)}

ここで，π(d_u) は文書d_uの重み，ω(u, d_u) は文uの重みである．文書dの重み π(d_u) は，その文書の要約対象文書集合に対するトピック（内容語）の類似度，文書をノードとしてPageRankアルゴリズムを適用したときの活性値などを用いて求める．文vの重み ω(u, d_u) は，文書d_vにおける相対位置や，文書d_v全体に対するトピックの類似度などで計算する．

文グラフのエッジの重みに，文書の重要度や文の重要度などの要素を混ぜ込んでしまい，PageRankの「多くの重要な文と類似する文は重要である」という仮定を破壊し，アルゴリズムの正当性を失わせているので，個人的にはまずいと思う．文ごとにランダム・ウォークの確率を調整するなど，別のやり方があったはず．

Arul Menezes; Chris Quirk. Syntactic Models for Structural Word Insertion and Deletion during Translation.

これまでの統計的機械翻訳では，翻訳において機能語などの要素が挿入・削除される現象が上手く扱えなかった．例えば，英語の名詞句”file name”をスペイン語”nombre de archivo”に翻訳するときは，前置詞”de”が挿入される．本論文は，文法構造を用いた翻訳システムにおいて，文法的な手がかりに基づいて，語を挿入・削除する手法を述べる．究極的には，「NN_1 NN_2 → NN_2 de NN_1」のような，非語彙化翻訳ルールを獲得することが，本研究の目的である．

本論文は，係り受け構造に基づく翻訳モデルであるtreelet translation model (Menezes and Quirk, 2007) を出発点とする．Treelet translation modelは，語彙化された対訳ペアであるtreelet translation pairと，非語彙化ルールであるorder templateから構成されている．

Treelet translation pairは，

• ((old_1/JJ) man_2/NN) → (hombre_2 (viejo_1))
• (man_1/NN) → (hombre_1)

のように，翻訳元言語と翻訳先言語における係り受け関係のペアに，ノードのアライメント情報が付与されたものである．

Order templateは，非語彙化された翻訳ルール（係り受けのペア）である．

• ((x0:*/DT) (x1:*/JJ) *_1/NN) → ((x0) *_1 (x1))
• ((x0:*/DT) (x1:*/JJ) *_1/NN) → ((x0) (x1) *_1)

本論文では，係り受け解析済みの並列文が与えられたときに，order templateを抽出するアルゴリズムを修正し，アライメントが取れていないノードをルールに含むことを許容して，次のようなorder templateを抽出する．

• ((x0:*/JJ) (x1:*/NN) *_1/NN) → (*_1 (*_2) (x1) (x2))
• ((x0:*/JJ) (x1:*/NN) *_1/NN) → (*_1 (de) (x1) (x2))

Treelet translation modelは，名詞句の言い換えなどの研究に十分使えそうなので，個人的には要チェックの論文だった．

Roser Morante; Anthony Liekens; Walter Daelemans. Learning the Scope of Negation in Biomedical Texts.

生命・医学文献中の否定表現の認識と，そのスコープの範囲を認識する研究．学習器には，メモリベースの分類器TiMBLとk-nearest neighbor分類器を用いている．学習データと素性を設計して，学習器を適用するだけ．

生命・医学文献において，否定表現のスコープを認識するのは非常に重要．ただ，機械学習の問題に落とし込むアプローチは，もう少しいろいろ考えられそう．

Mark Dredze; Koby Crammer. Online Methods for Multi-Domain Learning and Adaptation.

Confidence-weighted (CW) linear classifier (Dredze et al., 2008) をマルチドメイン学習に拡張する研究．素性重みの平均値と分散の組 (μ, Σ) をパラメータとしてもつCW分類器を，M個のドメインで学習すると，すべてのパラメータは{(μ_m, Σ_m)}_{m = 1}^{M} と表せる．これらの分類器を統合して一つの分類 (μ_c, Σ_c) を作る方法として，それぞれのドメインのパラメータ（素性重みの平均と分散）の重み付き平均をとる方法（L2）と，KLダイバージェンスから導出された式を用いる方法（KL）を提案している．様々なタスク設定で実験した結果，各ドメインのパラメータの重み付き平均を取る方法（L2）の方が，難しい更新式を使うKL手法よりも，概ね良好な結果を示すことが分かった．

Hal Daumé III. Cross-Task Knowledge-Constrained Self Training.

本論文は，二つのNLPシステムが同じデータ上で動作し，その出力の間に制約χがあるとき，その制約を事前知識と見なし，その制約を満たすタグ付け結果のみを利用するself-trainingフレームワークを提案している．例えば，入力文に対して品詞のタグ付けとチャンキングを行うタガーをシステムh1，固有表現抽出を行うタガーをシステムh2とする．これらの二つのシステム間における制約χとは，例えば「すべてのNNPは固有表現の全体もしくは一部を構成しなければならない」とか，「すべての固有表現はNPの全体もしくは一部で構成されなければならない」など，h1とh2が出力するラベルの一貫性をチェックする0-1関数である．

本論文は，「制約χが与えられているとき，h1及びh2の学習が改善されるか（例えば少ない訓練例で高いパフォーマンスを達成できるか）？」，「制約χはh1とh2のラベル付け結果の正しさを与えるのではなく，結果の一貫性だけを示すものであるが，それで十分か？」という問いに答えるものである．本論文では，self-trainingの戦略として，one-sided learningとtwo-sided learningの二つを考える．

One-seided learningでは，h1の大量の訓練例D1（例えばWSJの8,936文のPOS/chunkデータ）と，h2の少量の訓練例D2′（例えばCoNLL-2003の3,500文）があるとき，以下のアルゴリズムでh2の学習を改善する．

1. D2′からh2を学習で獲得する
2. すべての (x, y1) ∈ D1 に対して:
3.   y2 = h2(x) を計算する
4.   もしχ(y1, y2)が真ならば，(x, y2) をD2′に追加する
5. 新しくできたD2′からh2を再学習で獲得する
6. 必要があればステップ2に戻る

これに対し，two-sided learningでは，h1の少量の訓練例D1′と，h2の少量の訓練例D2′，ラベル付けされていないデータDuがあるとき，以下のアルゴリズムでh1とh2の学習を改善する．

1. D1′からh1，D2′からh2を学習で獲得する
2. すべての x ∈ Du に対して:
3.   y1 = h1(x)，y2 = h2(x) を計算する
4.   もし χ(y1, y2) が真ならば，(x, y1) をD1′に，(x, y2) をD2′に追加する
5. 新しくできたD1′とD2′から，h1とh2を再学習で獲得する
6. 必要があればステップ2に戻る

Two-sided learningの場合は，正解の訓練例D1を使わず，教師無しデータに対してh1を適用したものを用いるので，one-sided learningより性能が悪くなる．論文では，one-sided learningが有効であるために，制約χが満たすべき条件を理論的に示している．また，実験によりone-sided learningが通常のself-trainingよりも優れていることを確認した．

制約χは，ラベル付けの正しさに関する情報を与えるのではなく，２つの分類器の一貫性をチェックするだけであるが，それでも学習器にとって有用な情報であることを，理論的に説明しているところが興味深い．

Razvan Bunescu. Learning with Probabilistic Features for Improved Pipeline Models.

入力xに対して，あるNLPコンポーネントがzを出力し，そのzを入力として，別のNLPコンポーネントがyを出力するというパイプライン・アーキテクチャは，自然言語処理において，よく用いられている．例えば，文に対してPOSタガーを適用して品詞を付与し，係り受け解析を行ったり，固有表現抽出を行うなどの処理は，このパイプライン・アーキテクチャの一例と言える．

本論文では，入力xに対して最適な出力 z* = argmax P(z|x) を求め，そのz*に対して最適な出力 y* = argmax P(y|x,z*) を求めるアーキテクチャをM1と表現する．入力xに対して最適な出力 z* = argmax P(z|x) を求め，そのz*を出力するときの確率 P(z*|x) を，次段のコンポーネントにおける素性の確信度として用いるアーキテクチャをM3と表現する．さらに，入力xに対し，可能なすべての出力 z ∈ Z(x) の条件付き確率 P(z|y) を求め，最終的な出力を y* = argmax \sum_{z ∈ Z(x)} P(y|x,z) と求めるアーキテクチャをM2と表現する．初段のコンポーネントが，CRFに基づく品詞タガーの場合は，xが単語の系列，zが品詞の系列になるが， P(z|x) をすべての z ∈ Z(x) に対して計算するのは，非現実的である．そこで，品詞タガー内のforward-backwardアルゴリズムから計算されるラベル z_i の周辺確率や，隣り合うラベル z_i → z_{i+1} の周辺確率を利用する．係り受け解析の実験結果ではM1よりもM2が良く，固有表現抽出の実験結果ではM1よりもM3の方が良いという結果を報告している．

このように短くまとめると簡単なように見えるが，効率よくM2やM3を実装するには，２つのコンポーネントで用いられる素性の種類や，グラフィカルモデルにおける仮定を積極的に利用して，計算の近似もしくは効率化を図らなけれならない．実際，その統合方法の解説に論文の大半が割かれており，汎用性のあるパイプライン・アーキテクチャとは呼べるかは疑問．

Imed Zitouni; Radu Florian. Mention Detection Crossing the Language Barrier.

“President John Smith said he has no comments.”という例文において，エンティティへの参照表現，例えば”John Smith”（固有表現），”President”（名詞句），”he”（代名詞）などを認識するタスクは，mention detectionと呼ばれる．本論文では，言語資源が乏しい言語（例えばアラビア語やスペイン語など）におけるmention detection性能を向上させるために，言語資源が豊富な言語（例えば英語）の学習データを利用する方法を提案する．

まず，mention detectionタスクを，固有表現抽出と同様に系列ラベリング問題と捉え，log-linearモデルで定式化する（読者注：論文の著者らは言及していないが，論文で提案されているモデルは，状態素性の作り方が特殊なCRFと捉えることができる）．言語資源が乏しい言語のmention detectionを行うときに，資源が豊富な言語（英語）の力を借りる方法として，以下の３つを試している．

1. 入力文を統計的機械翻訳を用いて英語に翻訳し，英語においてmention detectionした結果を，単語アライメントを経由して，元の言語に伝搬（そのままラベル付け）する方法
2. 入力文を統計的機械翻訳を用いて英語に翻訳し，英語においてmention detectionした結果を，元言語のmention detection分類器の素性として取り込む方法
3. 元言語の大量のコーパスを英語に翻訳し，英語においてmention detectionをした後，その結果を元言語に伝搬させ，元言語の訓練例として用いる手法

統計的機械翻訳の面白い使い道ではあるが，アイディアが単純過ぎる気が･･･．

Partha Pratim Talukdar; Joseph Reisinger; Marius Pasca; Deepak Ravichandran; Rahul Bhagat; Fernando Pereira. Weakly-Supervised Acquisition of Labeled Class Instances using Graph Random Walks.

クラスとインスタンスを自動獲得する手法として，構造化されていない文書から獲得したデータ (Van Durme and Pasca, 2008) と，ウェブ文書のテーブルから獲得したデータ (Caferalla et al., 2008) を，Adsorption label-propagationアルゴリズム (Baluja et al., 2008) を用いて統合する．２つのデータに含まれるクラス－インスタンスペアから，一つの二部グラフを構築する．あるインスタンスが各クラスに属する確率は，二部グラフ上のランダムウォークモデルを使い，反復的に算出する．

ハワイから帰ってきてから，時差の関係で早く眠くなるので，夜更かしをせずにテレビを録画して観た．すごいレースだった！　最後はすべてのイギリス人が本当にやばいと思ったに違いない．雨が降らなければ，無難に４位か５位で終了していたレースだけに，またもツキに見放されたかと思ったけど，雨がさらに強くなってドラマチックな幕切れだった．

来年はいろいろなプレッシャーから解放され，アンチのネガティブキャンペーンに負けず，もう少し落ち着いてレースができるようになるといいですね．

イギリスのニュースや新聞ではお祭り騒ぎになっています．普通の記事を貼っても面白くないので，The Sunの記事でも．今日のテレビ中継には，ガールフレンドのNicole Scherzinger（Pussycat Dollsのlead vocal）が映りまくってましたね．

libLBFGS 1.6をリリースしました．変更点は以下の通りです．

• 今道様より頂いた，backtrackingアルゴリズムにおいて，strong Wolfe conditionを満たすようにステップ幅を決定する実装を取り込みました．これにより，サンプルプログラムにおいてbacktrackingアルゴリズムを使っても，途中でコケることなく，最小化が行えるようになりました（すばらしい！）．なお，この実装を頂いたのは，だいぶ前のことになるのですが，私がサボっていたためにリリースがかなり遅れました．今道さま，どうもありがとうございました．
• OW-LQNを適用する変数の範囲を，lbfgs_parameter_t::orthantwise_start と lbfgs_parameter_t::orthantwise_end で設定できるようにしました（以前はorthantwise_startだけでした）．
• C++のサンプルプログラムが欲しいという人がいるので，配布パッケージに同封しました．C++のクラスの中からlbfgs関数を呼び出すときは，lbfgs関数のinstanceパラメータの使い方，staticメンバ関数を経由したコールバックの実装など，ちょっと経験が必要かも知れませんね．

また忙しい時期に突入していくので，今のうちにソフトウェアをリリースしておかねば…．