Home > Conferences > EMNLP2008

2008.11.06

Attacking Decipherment Problems Optimally with Low-Order N-gram Models

Sujith Ravi; Kevin Knight. Attacking Decipherment Problems Optimally with Low-Order N-gram Models.

文字列置換による暗号化は,平文が”decade”のときに,{(d→Q), (e→W), (c→B), (a→S)}という文字置換操作を行い,”QWBSQW”という暗号文を得るという操作である.本研究は,”QWBSQW”のような暗号文を受け取ったときに,その平文を解読する方法として,低次なn-gram言語モデルと,整数計画法を用いる手法を提案している.

整数計画法による定式化は,bi-gram言語モデルで近似された平文Mの生成確率 P(M) を目的関数とし,変数として,平文のi番目の文字がpで,(i+1)番目の文字がrかどうかを表現する0–1変数 link_{ipr},平文の文字pを暗号文の文字qへ置換するかどうかを表す0-1変数 key_{pq} を決定する.整数計画法の制約条件として,「平文と暗号文の文字の間に一対一の対応が取れていること」「あるノードの左側のエッジと右側のエッジの数が同じであること(平文のbi-gramをエッジとして一つのパスができることを保証する)」「エッジ変数群 link_{ipr} が,置換変数群 key_{pq} と矛盾しないこと」を導入している.

本論文では引用されていないが,CRFで確率を最大にするラベルシーケンス(argmax)を求める際,「それぞれのラベルはシーケンスの中に一回しか出現してはいけない」など,マルコフ性に反する制約を導入したいとき,整数計画法でargmaxを求める方法が提案されている(Roth and Yih. Integer linear programming inference for conditional random fields. ICML, 2005).本研究は,これと類似のアイディアで,文字の置換を表す変数とその制約を追加した手法と捉えることができる.

Summarizing Spoken and Written Conversations

Gabriel Murray; Giuseppe Carenini. Summarizing Spoken and Written Conversations.

本論文は,会話文の要約システムを提案し,AIMコーパス(会議の議事録),及びメールのログ(Enronコーパス)において評価をしている.要約システムは,ある文を抽出すべきかどうかを判別する二値分類器(ロジスティック回帰)から構成されている.

分類器の素性として,文の長さ(SLEN, SLEN2),文の位置(TLOC, CLOC),発話された時間(TPOS1, TPOS2),発話前後の空白時間(SPAU, PPAU),発話者の発話の多さ(DOM),現在の発話者が会話を始めたかどうか(BEGAUTH),特定の発話者もしくは発言ターンで頻繁に用いられている語を重視する重み付けで文のスコアを計算したもの(MXS, MNS, SMS, MXT, MNT, SMT),直後の発話内容との類似性(COS1, COS2),会話全体との類似性(CENT1, CENT2),エントロピーに基づく重み付け(THISENT, PENT, SENT)を用いている.

Topic-Driven Multi-Document Summarization with Encyclopedic Knowledge and Spreading Activation

Vivi Nastase. Topic-Driven Multi-Document Summarization with Encyclopedic Knowledge and Spreading Activation.

本論文は,Document Understanding Conferences (DUC) のquery-focused summarizationタスクのように,要約対象文書集合と検索欲求が与えられているとき,その検索欲求に含まれるエンティティに関連するエンティティを収集し,検索クエリ拡張を行う手法を提案している.クエリ拡張のためのリソースとして,WikipediaとWordNetを比較している.

Wikipediaを用いたクエリ拡張では,検索欲求に含まれるエンティティをタイトルに含むWikipedia記事を検索し,その記事の最初のパラグラフに含まれるアンカーテキストを,拡張されたクエリと見なし,文書を収集する.収集された文書に対して,係り受け解析を行い,ノードを語,エッジを係り受け関係としたグラフ上で,PageRankアルゴリズムを適用し,活性値の高い語を拡張トピック語として取り出す.重要文抽出では,トピック語,拡張クエリ語,拡張トピック語,係り受け関係に関するスコアの和を,文のスコアとしている.

An Exploration of Document Impact on Graph-Based Multi-Document Summarization

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の「多くの重要な文と類似する文は重要である」という仮定を破壊し,アルゴリズムの正当性を失わせているので,個人的にはまずいと思う.文ごとにランダム・ウォークの確率を調整するなど,別のやり方があったはず.

Syntactic Models for Structural Word Insertion and Deletion during Translation

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は,名詞句の言い換えなどの研究に十分使えそうなので,個人的には要チェックの論文だった.

Learning the Scope of Negation in Biomedical Texts

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

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

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

Online Methods for Multi-Domain Learning and Adaptation

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手法よりも,概ね良好な結果を示すことが分かった.

Cross-Task Knowledge-Constrained Self Training

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 learningtwo-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よりも優れていることを確認した.

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

Learning with Probabilistic Features for Improved Pipeline Models

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を実装するには,2つのコンポーネントで用いられる素性の種類や,グラフィカルモデルにおける仮定を積極的に利用して,計算の近似もしくは効率化を図らなけれならない.実際,その統合方法の解説に論文の大半が割かれており,汎用性のあるパイプライン・アーキテクチャとは呼べるかは疑問.

Mention Detection Crossing the Language Barrier

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を行うときに,資源が豊富な言語(英語)の力を借りる方法として,以下の3つを試している.

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

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

Next »