Não Aqui!

ワイキキで取った写真をアップロード．

Phil Blunsom; Miles Osborne. Probabilistic Inference for Machine Translation.

A Discriminative Latent Variable Model for Statistical Machine Translation (Blunsom et. al., 2008) の続編．前作では，synchronus context free grammar (SCFG) に基づく機械翻訳システムを，導出dを隠れ変数とするlog-linearモデルで定式化し，識別モデルで大域最適化を行う方法を示した．しかし，パラメータ推定（具体的には正則化項の計算）を可能にするため，翻訳システムから言語モデルを省略していた．

本論文では，言語モデルを確率的識別モデルに取り込むため，モンテカルロ法に基づいて正則化項を計算する．つまり，可能な導出をすべて列挙するのではなく，その部分集合をサンプリングして正則化項を近似する．本論文では，その部分集合を求めるアルゴリズムとして，ビーム探索を用いる方法，Markov Chain Monte Carlo (MCMC)を用いる方法を提案している．

Chris Callison-Burch. Syntactic Constraints on Paraphrases Extracted from Parallel Corpora.

表現e_1からe_2への言い換え確率は，f-e言語間の並列コーパスに対して，フレーズ抽出ヒューリスティック (Och and Ney, 2004) を用いて，p(e_2|e_1) = \sum_f p(f|e_1) p(e_2, f, e_1) ≒ \sum_f p(f|e_1) p(e_2|f) と計算される．しかしながら，この手法は”equal”-”equal rights”, “create equal”-”equal”に見られるように，部分文字列を含む言い換えペアを抽出してしまうため，言い換え後の文が文法的に正しくなる保証がない．例えば，”create equal”を”equal”に言い換えると，文から動詞が消えてしまう恐れがある．

この問題に対処するため，言い換え元の表現の文法カテゴリに基づく制約を導入する．表現e_1の文法カテゴリをs(e_1)とすると，表現e_1からe_2への言い換え確率を，p(e_2|e_1,s(e_1))  = 1/|C| * \sum_{c \in C} \sum_f p(f|e_1, s(e_1)) p(e_2|f, s(e_1)) と計算する．表現e_1の文法カテゴリs(e_1)には，CCGスタイルの記法（例えば”VP/(NP/NNS)”）を採用する．

André Filipe Torres Martins; Dipanjan Das; Noah A. Smith; Eric P. Xing. Stacking Dependency Parsers.

現在の係り受け解析の主流は，graph-based methods (例えばMSTParser) とtransition-based method (例えばMaltParser) に大別される．graph-based methodsは，構文木全体のスコアを，その構成要素であるエッジのスコアの和（もしくは積）を取り，構文木全体のスコアが最大になるように動作するが，スコアの構成要素が局所的なエッジから組み立てられているため，構文木全体としての特徴量を取り込みづらいという問題点がある．transition-based methodsは，Shift-reduceパーサーのように，これまでの構文解析結果と，現在の状態が与えられたとき，次のパーサーの動作として最も適切なものを選択するか，これらの選択の系列全体を最適化することによって動作するが，得られた構文木全体が最適かどうかは保証されない．

Nivre and McDonald (2008) は，graph-basedとtransition-basedを組み合わせる方法として，stacked parsingを提案した．このフレームワークは，あるパーサーの解析結果を，別のパーサーの素性として取り込むことで，１層目のパーサーの解析誤りを訂正し，解析精度を向上させる方法を提案した．本論文は，このstacked parsingのstacked learningとしての解釈を与え，１層目と２層目のパーザーとして，種々の組み合わせを試し，Nivre and McDonald (2008) の精度を超える結果を報告している．

David Smith; Jason Eisner. Dependency Parsing by Belief Propagation.

グラフィカルモデルに基づく係り受け解析に，グローバルな素性を取り込む方法として，loopy berief propagationの利用を提案している．belief propagationを利用するには，ノード間の信念メッセージ量を計算する必要があるが，ノード素性，エッジ素性，孫素性，兄弟素性の信念量の計算は，自然に計算でき，計算量は高々o(n^3)である．しかし，エッジの数，木構造を満たすか，各ノードの親が一つになっているかなどのグローバルな素性の信念メッセージの量の計算は工夫が必要であり，本論文はこれらをすべて，高々o(n^3)で計算する方法を示している．

Slav Petrov; Aria Haghighi; Dan Klein. Coarse-to-Fine Syntactic Machine Translation using Language Projections.

SCFGに基づく翻訳モデルは，n-gram言語モデルを用いない限り，CKYアルゴリズムに類似したアルゴリズムで翻訳ができるので，非常に効率がよい．しかし，n-gram言語モデルを組み合わせようとすると，探索空間が非常に広くなり，計算量が急増する．この問題に対処するため，翻訳先の言語モデルをbi-gramからスタートし，候補を絞ってからtri-gram言語モデルを導入する方法が提案されている（Zhang and Gildea, 2008）．しかし，bi-gram言語モデルと組み合わせるだけでも，計算量はかなり膨大になる．

本論文は，計算量の増大が起こる原因として，「翻訳先の言語の可能な候補（単語）が多すぎること」に着目し，翻訳先の言語モデルの単語をクラスタリングする．翻訳文をデコードするときは，クラスタ数が少ない言語モデル（最小では16 unigrams, or 4096 tri-grams）からデコードを開始し，徐々に言語モデルのクラスタ数を増やしていく，マルチパス・デコーディングを行う．クラスタリング方法としては，ランダムクラスタリング，頻度クラスタリング，HMMクラスタリング，JClusterを試し，HMMクラスタリング，JClusterが低いパープレキシティを達成した．また，翻訳の評価実験では，１回のデコーディングだけで翻訳を行うベースラインと比較して，粒度の異なる言語モデルを用いた複数回のデコーディングを行う方が，翻訳速度，翻訳精度ともに向上することを示した．

プレゼンは，プログレッシブJPEGのように，最初はぼやーっとぼけている文字がだんだんとはっきりしていくアニメーションで，すごく分かりやすかった．

Ron Bekkerman; Koby Crammer. One-Class Clustering in the Text Domain.

あるトピックに関連する文書と関連しない文書が混ざっている文書集合が与えられたとき，トピックに関連する文書集合（核）と関連しない文書（ノイズ）に分類する教師無し手法を提案し，その手法の理論的な裏づけを行う．まず，単語wのトピックへの関与度を表す指標として，ρ(w) = p(w) / q(w)を用いる．ここで，p(w)は与えられた文書集合中におけるwの出現確率，q(w)は膨大な文書集合（例えばGoogle Web1Tコーパスなど）中におけるwの出現確率である．ある文書dのトピック度をp(w)とq(w)のKL-divergenceで計ると， KL_d(p||q) = \sum_{w \in G} p(d, w) log{p(w)/q(w)} =  \sum_{w \in G} p(d, w) log ρ(w) である（ここで，Gはq(w)に含まれる単語の集合）．

k個の核の文書を取り出すには，与えられた文書をKL_d(p||q)の高い順k個取り出せばよい（Max-KLアルゴリズム）．ただし，このアルゴリズムはすべての文書の長さが同じであるという仮定が入ってしまうため，次のOne-Class Co-Clustering (OCCC) アルゴリズムを提案する．

1. 単語をρ(w)の高い順に整列し，スコアの高いm_r個の単語を取り出して，Rとする．
2. 与えられたそれぞれの文書を，単語集合Rから成るbag-of-wordsで表現する
3. このようにしてp(w)を表現した文書に対し，KL_d(p||q)を計算し，スコアの高い順にk件の文書を取り出す

ここで，m_rはパラメータである（推定方法は論文参照）．本論文はさらに，EMアルゴリズムを用いた１クラス・クラスタリング手法（LTB）を提案しているが，実験ではOCCCがLTBと同等な性能を出すと報告している．

提案手法は非常にシンプルだが，その理論的裏付けを真面目にやっていて，すごい．

Omar Zaidan; Jason Eisner. Modeling Annotators: A Generative Approach to Learning from Annotator Rationales.

近年，能動学習や半教師あり学習に見られるように，学習に必要な訓練例をできるだけ少なくするアプローチが盛んに提案されている．これに対し，本研究は訓練例をアノテーションするときに，その根拠情報（rationales）を示してもらうことで，学習器のパラメータθを，アノテータが暗に持っているパラメータθ*に近づけることを試みる．文xをラベルy = {+1, -1}に分類タスク（例えば評判情報のポジ・ネガ判定）を例に考えると，この問題設定における学習データは，{(x1, y1, r1), … (xN, yN, rN)}と表される．ここで，rは文書x中の根拠情報（正確には根拠情報の位置）を表す．学習器のパラメータをθとし，アノテータが根拠情報を付与する時のパラメータをφとすると，次式の（正則化付き）対数尤度を最大化したい．

Π p_θ(y,x) * p_φ(r|x,y,θ) * P_prior(θ,φ)

最初の要素は，通常の文書分類器，次の要素はアノテータが何処に根拠情報を付与するか予測するものである．文書分類器は，単語ユニグラムを素性とした最大エントロピー法でモデル化する．根拠情報rは，文書xの中で根拠情報の箇所にI, そうでない箇所にOをラベル付けする系列ラベリング問題であると考え，線形連鎖CRFでモデル化する．CRFの状態素性としては，文書のラベルyと位置mのユニグラム素性の重みθ_{x_m}の符号が一致し，かつ重みの絶対値が大きいときに強力に発火する素性g_rel，文書のラベルと位置mのユニグラムの重みθ_{x_m}の符号が異なり，かつ重みの絶対値が大きいときに強力に発火する素性g_antirelから構成される．パラメータ推定では，θとφを同時に最適化する必要があるが，θを固定してφをL-BFGSで最適化し，次にφを固定してθをL-BFGSで最適化する手順を繰り返す．評価実験では，映画の評判分析コーパスを用い，根拠情報を利用しない学習器と比較すると，根拠情報を用いる提案手法の方が，統計的に有意な差で優れていることが示している．

根拠情報を用いるというアイディア自体に加え，論文中における議論の組み立て方が非常に上手いので，お薦めの論文．冒頭から抽象的な話が続いて煙幕が張られるが，セクション5を読むとすっきり．根拠情報をモデルに取り込む方法は，他にもいろいろ考えられそう．

Yunyao Li; Rajasekar Krishnamurthy; Sriram Raghavan; Shivakumar Vaithyanathan; H. V. Jagadish.
Regular Expression Learning for Information Extraction.

文書群Dに対して，ある情報抽出のタスク（例えば電話番号の認識など）を遂行する初期正規表現R_0を適用して，マッチした文字列をM(R_0, D)で表す．このとき，マッチした文字列に対して，正例（実際に電話番号である場合）と負例（電話番号でない場合）のラベル付けがなされているとし，それぞれM_p(R_0, D), M_n(R_0, D)で表す．このとき，正例を識別するためのF1スコアが最大にになるように，初期正規表現R_0を反復的に変形し，目的のタスクを遂行する正規表現を獲得する．正規表現R_iをR_{i+1}に変形するときは，マッチする文字列の範囲が狭くなる方向，すなわちM(R_i, D) ⊂ M(R_{i+1}, D)となるように，ルール変形を行う．ある正規表現R_iから変形しうる候補を列挙し，その中でF1スコアが最も大きくなる候補を選択する反復アルゴリズムで，初期正規表現R_0を改善していく．

個人的な意見では，正規表現上で学習アルゴリズムを組み立てずに，目的の表現を受理する有限状態オートマトンを自動獲得する方が，より自然なアプローチだと思う（というか，そういう研究はありそう）．

Jeremy Jancsary; Johannes Matiasek; Harald Trost. Revealing the Structure of Medical Dictations with Conditional Random Fields.

自動音声認識で書き起こしたカルテ（medical dictation）を構造化するため，セグメンテーションとセクション名推定を同時に行う．入力文書として自動音声認識で書き起こされたテキストを想定しているため，文の境界情報を信頼せず，入力文書のそれぞれの単語に対して”CHIEF-COMPLAINT”, “HISTORY-OF-PRESENT-ILLNESS”, “PHYSICAL-EXAMINATION”のようなセクション・ラベルを，BIO表記で付与する．また，”PHYSICAL-EXAMINATION”セクションの一部に”VITAL SIGN”というサブセクションがあるという，セクションの階層構造も考慮するため，セクション名の線形連鎖に加えて，セクション－サブセクションの依存構造をモデルに取り込み，格子型のCRFを用いてタグ付けを行う．CRFのグラフィカルモデル中にループができるので，loopy brief propagationを使ってパラメータ推定を行う．