# 集合分割問題に基づく系列アラインメントのモデル化

西野 正彬 $^{\dagger} \cdot$ 鈴木 潤 $\dagger$ - 梅谷 俊治 ${ }^{\dagger} \cdot$ 平尾 努 $\dagger \cdot$ 永田 昌明 $\dagger$

2 つの系列が与えられたときに, 系列の要素間での対応関係を求めることを系列ア ラインメントとよぶ。系列アラインメントは，自然言語処理分野においても文書対 から対訳関係にある文のペアを獲得する対訳文アラインメント等に広く利用される。既存の系列アラインメント法は，アラインメントの単調性を仮定する方法か，もし くは連続性を考慮せずに非単調なアラインメントを求める方法かのいずれかであっ た.しかし，法令文書等の対訳文書に対する対訳文アラインメントにおいては，単調性を仮定せず，かつ対応付けの連続性を考慮できる手法が望ましい．本論文では， ある大きさの要素のまとまりを単位として系列の順序が大きく変動する場合にアラ インメントを求めるための系列アラインメント法を示す。手法のポイントは, 系列 アラインメントを求める問題を組合せ最適化問題の一種である集合分割問題として 定式化して解くことで，要素のまとまりの発見と対応付けとを同時に行えるように した点にある。 さらに，大規模な整数線形計画問題を解く際に用いられる技法であ る列生成法を用いることで，高速な求解が可能であることも同時に示す. キーワード: 系列アラインメント, 組合せ最適化, 列生成法
## Sequence Alignment as a Set Partitioning Problem

\author{
Masaaki Nishino $^{\dagger}$, Jun Suzuki ${ }^{\dagger}$, Shunji Umetani ${ }^{\dagger}{ }^{\dagger}$, \\ Tsutomu Hirao $^{\dagger}$ and Masaaki Nagata ${ }^{\dagger}$
}

Sequence alignment, which involves aligning elements of two given sequences, occurs in many natural language processing (NLP) tasks such as sentence alignment. Previous approaches for solving sequence alignment problems in NLP can be categorized into two groups. The first group assumes monotonicity of alignments; the second group does not assume monotonicity or consider the continuity of alignments. However, for example, in aligning sentences of parallel legal documents, it is desirable to use a sentence alignment method that does not assume monotonicity but can consider continuity. Herein, we present a method to align sequences where block-wise changes in the order of sequence elements exist. Our method formalizes a sequence alignment problem as a set partitioning problem, a type of combinatorial optimization problem, and solves the problem to obtain an alignment. We also propose an efficient algorithm to solve the optimization problem by applying column generation.

Key Words: Sequence Alignment, Combinatorial Optimization, Column Generation


## 1 はじめに

系列アラインメントとは，2つの系列が与えられたときに，その構成要素間の対応関係を求めることをいう，系列アラインメントは特にバイオインフォマテイクスにおいて DNA P RNA の解析のために広く用いられているが, 自然言語処理においてもさまざまな課題が系列アラインメントに帰着することで解かれている. 代表的な課題として対訳文アラインメント (Moore 2002; Braune and Fraser 2010; Quan, Kit, and Song 2013) があげられる. 対訳文アラインメントは対訳関係にある文書対が与えられたときに, 文書対の中から対訳関係にある文のぺアをすべて見つけるタスクである。統計的機械翻訳においては，対訳コーパスにおいてどの文がどの文と対訳関係にあるかという文対文での対応関係が与えられているという前提のもとで学習処理が実行されるが，実際の対訳コーパスでは文書対文書での対応付けは得られていても文対文の対応付けは不明なものも多い. そのため, 対訳文書間での正しい対訳文アラインメントを求めることは精度のよいモデルを推定するための重要な前処理として位置づけられる．統計的機械翻訳以外の, 例えば言語横断的な情報検索 (Nie, Simard, Isabelle, and Durand 1999)などの課題においても対訳文書間の正しい文アラインメントを求めることは重要な前処理として位置づけられる。また，対訳文アラインメントのほかにも，対訳文書に限定されない文書間の対応付けタスクも系列アラインメントとして解かれている (Qu and Liu 2012; 角田, 乾, 山本 2015;竹中, 若尾 2012).

自然言語処理のタスクにおける系列アラインメント問題を解く手法は, 対応付けの単調性を仮定する方法とそうでない方法とに大別される。単調性を仮定する系列アラインメント法は特に対訳文アラインメントにおいて広く用いられる方法であり，対訳関係にある二つの文章における対応する文の出現順序が大きく違わないことを前提として対応付けを行う。すなわち, 対訳関係にある文書のペア $F, E$ に対し， $F$ の $i$ 番目の文 $f_{i}$ に $E$ の $j$ 番目の文 $e_{j}$ が対応するとしたら，Fの $i+1$ 番目の文に対応する $E$ の文は,（存在するならば） $j+1$ 番目以降であるという前提のもとで対応付けを行っていた。この前提は, 例えば小説のように文の順序が大きく変動すると内容が損なわれてしまうような文書に対しては妥当なものである。一方で単調性を仮定しない方法は (Qu and Liu 2012; 角田他 2015; 竹中, 若尾 2012) などで用いられており, 文間の対応付けの順序に特に制約を課さずに系列アラインメントを求める。図 1 は, それぞれ単調性を仮定した系列アラインメント，仮定しない系列アラインメントの例を表している。白丸が系列中のある要素を表現しており, 要素の列として系列が表現されている。図では 2 の系列の要素間で対応付けがとられていることを線で示している. 単調性を仮定した対応付け手法では，対応関係を表す線は交差しない。一方で仮定しない手法では交差することが分かる.

系列アラインメントにおいて単調性を仮定することは，可能なアラインメントの種類数を大きく減少させる一方で, 動的計画法による効率的な対応付けを可能とする. 先述したように, 対

(a) 単調な系列アラインメント

(b) 非単調な系列アラインメント

図 1 既存の系列アラインメント法によるアラインメント例

訳文アラインメントを行う際に単調性を仮定することは多くの対訳文書に対しては妥当な仮定である。しかし, 単調性を仮定することが妥当でない対訳文書も存在する. 例えば文献 (Quan et al. 2013) では, 単調性が成り立たない文書の例として法令文書を挙げている。そのほかにも例えば百科事典や Wikipedia の記事のように一つの文書が独立な複数の文のまとまりからなる場合には，文のまとまりの出現順序が大きく変動しても内容が損なわれないことがある。このような文書においては，文の順序が大きく変動しないという前提は必ずしも正しいものではないため, 既存の単調性を仮定した系列アラインメント法では正しい対訳文アラインメントが行えない可能性が高い.

一方で，単調性を仮定しない既存のアラインメント法では非単調な対応付けを実現できるものの，対応付けの連続性を考慮することが難しいという問題がある。対応付けの連続性とは， $f_{i}$ が $e_{j}$ と対応付けられているならば， $f_{i+1}$ は $e_{j}$ の近傍の要素と対応付けられる可能性が高いとする性質のことである 1 . もし対応付けにおいて連続性を考慮しないとすると, 系列 $F$ 中のある要素 $f_{i}$ とそれに隣接する要素 $f_{i+1}$ とが, それぞれ $E$ 中で離れた要素と対応付けられてもよいとすることに相当する。対応付けの単調性を仮定できるような対訳文書の対訳文アラインメントについては，明らかに対応付けの連続性を考慮する必要がある。 さらに，単調性が仮定できないような文書のぺアに対する対訳文アラインメントにおいても，ある文とその近傍の文が常に無関係であるとは考えにくい，以上より，文アラインメントにおいては連続性を考慮することが不可欠である。また，対訳文アラインメント以外の系列アラインメントを用いるタスクにおいても，対応付けの対象となる系列は時系列に並んだ文書等，何らかの前後のつながりを仮定できるものが多いことから，連続性を考慮する必要がある。

単調性を仮定できない文アラインメントの例を示す. 図 2 は, 文献 (Quan et al. 2013)の検証

^{1} 4$ 節以降の提案手法の説明では, 説明を簡単にするために，対応付けに順方向の連続性がある場合，すなわち $f_{i}$ と $e_{j}$ が対応付けられているならば $f_{i+1}$ は $e_{j}$ より後ろにある近傍の要素と対応付けられやすい場合のみを扱っている。しかし, 実際には提案法は順方向に連続性がある場合と同様に逆方向の連続性がある場合の対応付けを行うこともできる。逆方向の連続性とは， $f_{i}$ と $e_{j}$ が対応付けられているならば， $f_{i+1}$ は $e_{j}$ 以前の近傍の要素と対応付けられる可能性が高いとする性質のことである.

2 http://www.legistlation.gov.hk
}
"adopted" (領羪) means adopted in pursuance of an adoption order made under the
Adoption rap (Cap) or of any adoption recognized as valid by the law of Hong Kong;

"dependant" (受養人), in relation to a deceased person, means (a) the wife, husband, former wife or former husband of the deceased and any person whose marriage to the deceased has been an

(b) a concubine lawfully taken by the deceased before 7 October 1971;

(c) any person who- (i) was living with the deceased in the same household immediatel before the date of his death; "wife" ( (妻、妻子) means- (a) in the case of a Christian marriage or its civil equivalent, the
lawful wife;

and (b) in the case of any other lawful marriage- (i) the lawful wife of such marriage;

or (ii) if there is more than one lawful wife, the lawful principal wife recognized as such by the personal law of the husband of such marriage, or if there is no lawful principal wife, the lawful wives so recognized.

(2) In deducing any relationship for the purposes of this Ordinance- (a) an adopted person shall be treated as the child of the person or persons by whom he was adopted and not as the child of any other person; and, subject thereto;

“妻”、“妻子” (wife) 指一 (a) 在基督教婚姻或與其相等的世俗婚姻中的合法妻子;及 (b) 在其他合法婚姻中一 (i) 該宗婚姻的合法妻子:或 (ii)（如有超過一個合法妻子)，對丈夫本人有約束力的法律所承認的合法正妻，或(如並無合法正妻)該等法律所承認的各合法妻子;

“受養人" (dependant) 就死者而言，指一 (a) 死者的妻子、丈夫、前妻或前夫，以及與死者所締結的婚姻已經作廢或遭宣布無效的人;

(b) 死者在1971年10月7日以前合法納娶的妾侍;

(c) 符合下列條件的人一 (i) 在緊接死者死亡的日期之前, 與死者在同一住戶內生活，如同夫位:

"“領養" (adopted) 指依據根據《領養條例》(第290章)發出的領養令而領養，或依據香認為有效的方式而領養

（2）為本條例的施行而推斷關係時一 (a) 須視受領養人為領養人的子女而非其他人的子女並且在符合本段的規定下;

図 2 法令文書における非単調な対訳文アラインメントの例

おける文アラインメントの例である，BLIS は香港の法令文書の電子データベースであり，対訳関係にある英語・中国語の文書を保持している。図に示す対訳文は用語の定義を行っている箇所である。両言語の文を比べると，定義する用語の順番が英語と中国語とで異なっており，結果として，局所的には連続なアラインメントが非単調に出現する対訳文書となっている.

本論文では系列の連続性を考慮しつつ，かつ非単調な系列アラインメントを求めるための手法を提案する。このような系列アラインメント法は，単調性を仮定できない文書対の対訳文アラインメントを求める際に特に有効であると考える。仮に文書 $F$ の文が $E$ の任意の文と対応してもよいとすれば，ある文のぺアの良さを評価するスコアを適切に設定することによって，問題を二部グラフにおける最大重みマッチング問題 (Korte and Vygen 2008) として定式化して解くことができる。しかし，Fのある文が $E$ の任意の文と対応してもよいという前提では，近傍の文間のつながりを無視して対応付けを行うことになる。実際の文書ではすべての文がその近傍の文と無関係であるとは考えにくいため, 正しい対応付けが行えない可能性が高い。そこで，提案手法では対訳文アラインメントを組合せ最適化の問題の一つである集合分割問題として定式化して解く，集合分割問題は，ある集合 $S$ とその部分集合族 $S_{1}, \ldots, S_{N}$ が与えられたときに， スコアの和が最大となるような $S$ の分割 $\mathcal{D} \subseteq\left.\{S_{1}, \ldots, S_{N}\right.\}$ を見つける問題である. ここで $\mathcal{D}$ が $S$ の分割であるとは, $S=\cup_{S_{i} \in \mathcal{D}} S_{i}$ かつ $i \neq j$ ならば任意の $S_{i}, S_{j} \in \mathcal{D}$ について $S_{i} \cap S_{j}=\emptyset$ となることをいう。 2 の系列 $F, E$ のある部分列に対する単調な系列アラインメントの集合を $S_{1}, \ldots, S_{N}$ として表現することで，部分列に対するアラインメントの集合 $S_{1}, \ldots, S_{N}$ から系列全体の分割となるような部分集合を選択する問題として $F, E$ 全体に対する系列アラインメン卜を求めることができる.

また，本論文では集合分割問題としての系列アラインメントの定式化とともに，その高速な求解法も同時に示す。提案する集合分割問題に基づく定式化を用いると，系列 $F, E$ に含まれ

る要素の数が増加するに伴い，急激に厳密解の求解に時間がかかるようになるという課題がある.これは, それぞれの系列に含まれる要素の総数を $|F|,|E|$ とすると, 集合分割問題に出現する変数の数 3 が $O\left(|F|^{2}|E|^{2}\right)$ となるためである。集合分割問題は NP 困難であり，変数の数が増加すると各変数に対応する重みの計算および整数線形計画法ソルバを用いた求解に時間がかかるようになる。本論文ではこの課題に対処するために，多くの変数が問題中に出現する大規模な線形計画問題を解く際に用いられる，列生成法 (Lübbecke and Desrosiers 2005) を用いることで高速な系列アラインメントを実現する近似解法も同時に提案する。列生成法は大規模な問題の解を, 出現する変数の個数を制限した小さな問題を繰り返し解くことによって求める手法である，列生成法を用いることによって，そのままでは変数の数が膨大となり解くことができなかった問題を解くことができる。なお，列生成法を用いることで線形計画問題の最適解を得られることは保証されているが, 整数線形計画問題については解を得られることは必ずしも保証されていない。そこで本論文では列生成法で得られた近似解を実験によって最適解と比較し，よい近似解が得られていることを確認する。

なお，以下では説明を簡単にするために特に対訳文書の対訳文アラインメントに話題を限定して説明を進める。ただし, 系列の要素間のスコアさえ定まれば提案法を用いて任意の系列のペアに対する系列アラインメントを行うことが可能である.

## 2 関連研究

対訳文アラインメントに関しては, これまで，文の長さを対応付けに利用する方法 (Gale and Church 1993)，語の翻訳確率と文の長さを利用する方法 (Moore 2002; Braune and Fraser 2010) などが提案されてきているが，ほとんどの方法でアラインメントの単調性を仮定している，単調性を仮定することによって動的計画法によって効率的に対訳文アラインメントを求めることができるという利点はあるが, 序章で述べたように単調性が成り立たない文書対に対しては正しいアラインメントを求めることができないという点がある. Deng らは系列マッチングとクラスタリングをあわせて利用することで，文の順序が入れ替わる場合でも対訳文アラインメントを行える手法を提案している (Deng, Kumar, and Byrne 2007). しかし, Deng らの手法は, ある隣接する二つの文の順序が入れ替わるなど，順序の入れ替わりが小さい範囲で起きることを想定した手法であり，より大きな範囲での順序の入れ替わりには対処できない.

対訳文間の単調性を仮定しない, 非単調な対訳文アラインメントを求めるための手法として,近年 Quan らは半教師あり学習の枠組みに基づく文対応付け手法を提案している (Quan et al. 2013). 彼らの手法は基本的には二部グラフマッチングに基づくアラインメント法であるが, 各

文書における文間の類似度合いを対応付けのための目的関数に用いている点が特徴的である。 Quan らの手法と比較すると，提案法は文のまとまり単位のアラインメントをより明示的に意識した手法となっていることが異なる，Quan らの手法は隣り合う文間の関係を明示的には考慮しないため, 対訳文書間で文の出現順序が全く異なる文書により適している。また，Quan らの手法は二部グラフマッチングに基づく手法のため多対多のアラインメントには対応できないが，提案法は内部で呼び出す既存の単調性を仮定した対訳文アラインメント法を多対多のマッチングを考慮するものに変更することによって，容易に多対多の対訳文アラインメントを行うように拡張できる点も異なる。

対訳文アラインメント以外にも，さまざまな自然言語処理のタスクが系列アラインメント問題として定式化され解かれている。例えば質問応答ウェブサイトにおける質問と回答との対応付け (Qu and Liu 2012)や，ウェブサイトにおけるレビュー文とそれに対する返答のペア (角田他 2015), 条例文 (竹中, 若尾 2012)の対応付けといったタスクなどがある.

対訳文アラインメント以外の自然言語処理における重要な系列アラインメント問題の適用先として，単語アラインメントが挙げられる，単語アラインメント問題に関しては非単調なアラインメントを求めるための手法が数多く提案されてきている. Brown らは, 原言語の各単語は必ず目的言語のある単語に対応付けられるなどの制約のもとで, 生成モデルに基づいた単語の非単調なアラインメントを行っている (Brown, Petra, Pietra, and Mercer 1993)。また, Wu は反転トランスダクション文法に基づいた非単調な単語アラインメント法を提案している (Wu 1997). これらのうち, (Brown et al. 1993) は単語アラインメントに固有の性質を扱っており, 本論文で扱っている対訳文アラインメントに直接適用するのは難しい。また，反転トランスダクション文法に基づく手法は，提案法に類似の非単調な対訳文アラインメントを実現可能な文法規則を設計できる。しかし, 反転トランスダクション文法では連続な文間の非単調なアラインメントの形態が制限される点が提案手法と異なる.

## 3 単調性を仮定した対訳文アラインメント法

提案法の説明の準備として，単調性を仮定した動的計画法に基づく既存の対訳文アラインメント法について説明する。単調性を仮定した対訳文アラインメント法では，対訳文書 $F, E$ のある文のぺア $s \in F, t \in E$ が対応付けられた時のスコア $S(s, t)$ が与えられたときに 4 ，スコアの総和が最大となるような単調な対訳文アラインメントを求める。アラインメントの単調性を仮定すると，最適な系列アラインメントは動的計画法を用いることで高速に求めることができる。


これまでにさまざまなスコア $S(s, t)$ の定義が提案されてきているが, 代表的な対訳文アラインメント法である Moore による手法 (Moore 2002) では, 文の長さと文中の語の翻訳確率とを用いることでペアのスコアを定義し, 対訳文アラインメントに含まれるぺアのスコアが最大となるようにアラインメントを求める。具体的には, $s \in F$ である文 $s$ と $t \in E$ である文 $t$ とのぺアのスコア $S(s, t)$ を

$
S(s, t)=\frac{P\left(m_{s}, m_{t}\right)}{\left(m_{s}+1\right)^{m_{t}}}\left(\prod_{j=1}^{m_{t}} \sum_{i=1}^{m_{s}} \operatorname{tr}\left(t_{j} \mid s_{i}\right)\right)\left(\prod_{i=1}^{m_{s}} u\left(s_{i}\right)\right)
$

として定める。ここで， $m_{s}, m_{t}$ はそれぞれ文 $s, t$ に含まれる単語の総数である。また $, s_{i}, t_{j}$ はそれぞれ $s$ の $i$ 番目の語, $t$ の $j$ 番目の語を表す. $t r\left(t_{j} \mid s_{i}\right)$ は語 $s_{i}$ が $t_{j}$ に翻訳される確率である. $u\left(s_{i}\right)$ は語 $s_{i}$ の文書中での相対頻度を表す. $P\left(m_{s}, m_{t}\right)$ は, 文の長さ（語の数）に応じてスコアを定める関数であり, ポアソン分布を用いて

$
P\left(m_{s}, m_{t}\right)=\frac{\exp \left(-m_{s} r\right)\left(m_{s} r\right)^{m_{t}}}{m_{t} !}
$

として定義される。 $r$ はパラメータである。各確率分布は (Brown et al. 1993) にある手法によってデータから推定できる。

## 4 集合分割問題に基づく対訳文アラインメントのモデル化

本論文で提案する対訳文アラインメント法の概観を示す。提案法のポイントは，文書を連続する文のまとまりに分割してアラインメントを求める点にある。 すなわち，対訳文書のそれぞれを同数の文のまとまりに分割したのち，

(1) どの文のまとまり同士が対応付けられるか

（2）対応付けられた文のまとまりのペアの中で，どの文のペアが対応付けられるかを同時に求めることで対応付けを行う。このときに (1)について非単調な対応付け, (2) については単調な対応付けを行うことによって，連続性を考慮した非単調な対応付けを実現する。それぞれの文書を 3 つのまとまりに分割したときの提案法による対訳文アラインメントの様子を図 3 に示す。図中の白い丸がひとつの文に対応している。また, 複数の丸を囲む四角が文のまとまりを表す。図より，文のまとまり同士の対応付けにおいては非単調な対応付けを行っていることと, 文のまとまりに含まれている文同士の対応付けにおいては単調な対応付けを行っていることが分かる，文のまとまりに含まれる文同士の対応付けは，既存の単調な対訳文アラインメント法によって行われる。つまり，対応付けられる各文書を 1 つのまとまりだとみなした場合は, 文書全体で単調な対応付けを行うことになるため, 提案手法は既存の対訳文アラインメント法と同等である.

図 3 提案法による対訳文アラインメントの概観。各文書を 3 つの連続する文のまとまりに分割し，文のまとまり間で非単調な対応付けを行っている。対応付けられた文のまとまりのぺアに含まれる文間では，単調な対応付けを行っている，結果として文書全体に対する対訳文アラインメントが得られている.

以下で用いる記法について述べる。対応付けをとる対象の 2 つの文書を $F, E$ とし，それぞれ $|F|,|E|$ 個の文からなるとする。 $f_{i}$ を $F$ に含まれる $i$ 番目の文, $e_{k}$ を $E$ に含まれる $k$ 番目の文とする．Fの $i$ 番目から $j$ 番目までの連続する文の集合を $f_{i j} \subseteq F$ とする．たたし $1 \leq i \leq j \leq|F|$ である。同様に， $e_{k l} \subseteq E$ は $E$ の $k$ 番目から $l$ 番目までの連続する文の集合とする. たたし $1 \leq k \leq l \leq|E|$ である.また， $a_{i j k l}$ を文のまとまりのぺア $\left(f_{i j}, e_{k l}\right)$ を表現するために用い, $f\left(a_{i j k l}\right)=f_{i j}, e\left(a_{i j k l}\right)=e_{k l}$ と定義する.

文のまとまり $f_{i j}$ と $e_{k l}$ のペアに対して，既存の単調性を仮定した対訳文アラインメント法を適用することによって得られる文アラインメントのスコアを $\operatorname{seqMatch}\left(f_{i j}, e_{k l}\right)$ とする。すなわち, $f_{i j}, e_{k l}$ 間のある単調なアラインメントを $X$, すべての単調な対訳文アラインメントの集合を $\mathcal{A}_{i j k l}$ とすると, $\operatorname{seqMatch}\left(f_{i j}, e_{k l}\right)$ は

$
\operatorname{seqMatch}\left(f_{i j}, e_{k l}\right)=\max _{X \in \mathcal{A}_{i j k l}} \sum_{(s, t) \in X} S(s, t)
$

として定義される.

## 4.1 集合分割問題に基づく定式化

前節で定義した $\operatorname{seqMatch}\left(f_{i j}, e_{k l}\right)$ は，文のまとまり $f_{i j}$ と $e_{k l}$ のペアに対する対応付けスコアであるとみなすことができる。このスコアを用いて文のまとまり同士の一対一の対応付けを求める．文のまとまり同士の対応付けを求めることができれば，それに含まれる文間の対応付けは $\operatorname{seqMatch}\left(f_{i j}, e_{k l}\right)$ を求める際に既に求めてあるため, 結果として対訳文アラインメントが得られる，可能なすべての文のまとまりのぺア $a_{i j k l}$ の集合を $\mathcal{M}$ とすると，ある文アラインメン卜は，M部分集合であり，かつ文書対の分割となっているような文のまとまりのぺアの集合 $A \subseteq \mathcal{M}$ として表現できる。ただし， $A$ に含まれる任意の文のまとまりのぺア $a, a^{\prime} \in A$ について $f(a) \cap f\left(a^{\prime}\right)=\emptyset$ かつ $e(a) \cap e\left(a^{\prime}\right)=\emptyset$ であり,$\cup_{a \in A} f(a)=F$ かつ $\cup_{a \in A} e(a)=E$ を満たすもの

とする，上記の条件を満たす $A$ の集合を $\mathcal{A}$ とすると，対訳文アラインメントを求める問題は，

$
\hat{A}=\underset{A \in \mathcal{A}}{\operatorname{argmax}}\{\operatorname{score}(A)\}
$

として，マッチングのスコアを最大とする $\hat{A}$ 求める問題として定式化することができる。ここで score(A)は， $F$ と $E$ に対する分割 $A$ を定めたときのスコアであり，以下のように定義する.

$
\operatorname{score}(A)=\lambda^{K} \prod_{a \in A} \operatorname{seqMatch}(f(a), e(a))
$

ここで $K$ は $A$ 中に含まれる文のまとまりのぺアの総数， $\lambda$ はぺアの個数に応じて課されるぺナルティを表すパラメタであり， $0<\lambda \leq 1$ を満たすように設定する。 $\lambda=1$ とすると解に出現する文のまとまりのぺアの個数に制限をつけないことに相当するため，文の連続性を考慮しな

まりの個数に対して大きなぺナルティを与えることに相当するため，できるだけ小ない個数の文のまとまりが解に含まれるようになる，入をある程度以上小さな値に設定すると常に 1 つの文のまとまりのペアに分割されるようになる。これは既存の単調な対訳文アラインメントと等しい.

式 (5) の対数をとると, $\operatorname{score}(A)$ は文のまとまりのペア $a$ に対する線形式に置き換えることができる。よって, ここでの対訳文アラインメント問題は整数線形計画問題 (ILP) として定式化することができる。ILPによる定式化は,

$
\begin{aligned}
& \operatorname{maximize} \sum_{i j k l}\left(w_{i j k l}+\log \lambda\right) y_{i j k l} \\
& \text { subject to } \sum_{i, j: i \leq x \leq j} \sum_{k l} y_{i j k l}=1 \quad \forall x: 1 \leq x \leq|F| \\
& \sum_{i j} \sum_{k, l: k \leq x \leq l} y_{i j k l}=1 \quad \forall x: 1 \leq x \leq|E| \\
& y_{i j k l} \in\{0,1\} \quad \forall i, j, k, l
\end{aligned}
$

となる.ここで， $w_{i j k l}$ は $\log \operatorname{seq} \operatorname{Match}\left(f_{i j}, e_{k l}\right)$ の值である。 $y_{i j k l}$ は文のまとまりのぺア $a_{i j k l}$ をアラインメントに含むことを表す変数であり,$y_{i j k l}=1$ のときは $a_{i j k l}$ が対訳文アラインメントに含まれるとする。制約 (7) は， $F$ 中の $x$ 番目の文を含むすべての文のまとまりのぺア $a_{i j k l}$ のうち, 必ず 1 つだけが解に選択されることを保証するものである. (8) は同様の制約を $E$ に課したものであり，これら 2 つの制約を併せて $F$ と $E$ に含まれる各文が最終的に得られた文のまとまり同士の対応付けのいずれか 1 つに必ず含まれることを保証する。今回用いた定式化は，任意のペア $\left(f_{i j}, e_{k l}\right)$ に対応する集合の集まりである集合族に対する集合分割問題となっている。なお, 提案法は既存の単調な文アラインメント法として, 多対多のアラインメントを求

めることができる手法を用いることによって, 非単調な多対多のアラインメントを実現することができる 5.

## 5 列生成法

式 (6) から (9) からなる整数線形計画問題はすべての文のまとまりのぺア数に対応する数の変数を含む. このようなぺアは $|F||E|(|F|+1)(|E|+1) / 4$ 種類存在するため, 文の数が増加すると整数線形計画問題に含まれる変数の数が急増し, 解を求めるのに時間がかかるという問題がある。本論文では列生成法 (Lübbecke and Desrosiers 2005)を用いた近似解法を導入することでこの問題に対応する。一般的な整数線形計画問題の解法では，すべての変数を求解時に明示的に扱って解を求めるが, 列生成法では目的関数の増加に寄与する可能性がある変数を逐次的に追加しながら問題を解くことで解を求める。最適解において非ゼロとなる変数の数が問題全体で扱う変数の数に対して非常に小さい場合, 最適解においてゼロとなる変数を考慮せずに解が得られる可能性が高いことから，列生成法によって高速に解を得られることが期待できる。

以下，列生成法に基づく解法の詳細を述べる．列生成法を導入するにあたり，いくつかの概念を定義する。まず，式 (6) から (9) からなる整数線形計画問題を線形緩和した問題，つまり制約 $a_{i j k l} \in\{0,1\}$ を $0 \leq a_{i j k l} \leq 1$ へと緩和した問題を主問題 (Master problem: MP) とよぶ.主問題に含まれるすべての変数の集合を $\mathcal{M}$ とする。 MPからいくつかの変数を取り除いた問題を制限された主問題 (Restricted master problem: RMP) とよぶ. RMP に出現する変数の集合を $\mathcal{M}^{\prime} \subseteq \mathcal{M}$ と表す. ある線形計画問題の双対問題とは, もとの問題の各変数にそれぞれ対応する制約条件と，もとの問題の各制約条件に対応する変数からなる線形計画問題のことである. RMP に対しても双対問題を考えることができる。双対問題において RMP における文 $f_{n}$ に関する制約に対応する変数を $u_{n}, e_{m}$ に関する制約に対応する変数を $v_{m}$ とする. 線形計画問題が最適解を持つのであれば，最適解の值はそれは双対問題の最適解の值と一致することが知られており，RMPの最適解を単体法を用いて得ることができたならば，双対問題の最適解も容易に計算可能である。

列生成法は RMP の求解と RMP に追加する変数を求める問題とを繰り返し解くことで MP を解く。追加する変数を求める問題は列生成部分問題とよばれ, 具体的には $a_{i j k l} \in \mathcal{M} \backslash \mathcal{M}^{\prime}$ であるような $a_{i j k l}$ のうち,
-e_{4}, f_{2}-e_{3}, f_{3}-e_{2}, f_{4}-e_{1}$ といったような逆順で単調なアラインメントを解の一部として含むようにすることも可能である。具体的には式 (3) において $\operatorname{seqMatch}\left(f_{i j}, e_{k l}\right)$ を通常順,逆順の全ての可能な対応付けからスコアを最大にするものを選択するように修正すればよい。逆順の単調なアラインメントは，片方の系列を逆順にしたうえで，単調性を仮定した動的計画法によるアラインメント法を実行することで求めることができる.
}

$
\bar{w}_{i j k l}=w_{i j k l}+\log \lambda-\sum_{n=i}^{j} \hat{u}_{n}-\sum_{m=k}^{l} \hat{v}_{m}
$

を最大とするものを一つ求める問題である。ここで, $\hat{u}_{n}$ は RMP の双対問題の最適解における変数 $u_{n}$ の値, $\hat{v}_{m}$ は変数 $v_{m}$ の値とする．以下では $\bar{w}_{i j k l}$ のことを被約費用とよぶ. ある RMP を解いた後に各変数に対する被約費用がすべて負となるとき，RMP の最適解は MP の最適解となることが知られている。最適解において多くの変数の値がゼロとなるような問題においては, 出現する変数の数が MP よりも大幅に少ないRMP を解くことで MP の最適解が得られることが期待できるため, 列生成法は大規模な最適化問題を高速に解くことができる.

列生成部分問題を解くことを考える。前述のとおり，変数は $|F||E|(|F|+1)(|E|+1) / 4$ 個あるため, その全てについて被約費用を求めるのは困難である。 しかし, スコア $w_{i j k l}$ が 3 章で述べたように動的計画法によって求められること，および被約費用の式 (10)において $\hat{u}_{n}, \hat{v}_{m}$ が対応する文ごとにそれぞれ独立に作用していることを利用すると，最大の被約費用を SmithWaterman 法 (Smith and Waterman 1981)に類似した動的計画法によって求めることができる. Smith-Waterman 法はバイオインフォマティクスの分野で提案された, 配列の局所アラインメントを求めるためのアルゴリズムであり, 動的計画法に基づいて長さ $N, M$ の二本の配列に対する局所アラインメントを $O(N M)$ 時間で求めることができる. ここで局所アラインメントとは, 二本の配列の可能な部分配列間の系列アラインメントのうち， スコアを最大とするもののことである．動的計画法は以下の局所アラインメントの再帰的な定義に沿って計算する。なお,以下では説明を簡単にするため, 提案法内で利用する単調なアラインメントを求める手法が一対一のアラインメントのみを求めると仮定している. しかし, 多対多のアラインメントを求めることができる手法を利用した場合であっても，下記の再帰式を容易に拡張することが可能である ${ }^{6}$.

$q[j, l]$ をその末尾の要素がそれぞれ $f_{j}, e_{l}$ であるような文のまとまりのぺアの被約費用 $\bar{w}_{i j k l}$ $(1 \leq i \leq j, 1 \leq k \leq l)$ の最大値とすると, $q[j, l]$ は

$
q[j, l]=\max \left.\{\begin{array}{l}
\log \lambda \\
q[j-1, l-1]+S\left(f_{j}, e_{l}\right)-\hat{u}_{j}-\hat{v}_{l} \\
q[j-1, l]+S\left(f_{j}\right)-\hat{u}_{j} \\
q[j, l-1]+S\left(e_{l}\right)-\hat{v}_{l}
\end{array}\right.
$

として再帰的に計算することができる. なお $q[0,0]=\log \lambda$ とする. ここで $S\left(f_{j}, e_{l}\right), S\left(f_{j}\right), S\left(e_{l}\right)$ は，既存の単調性を仮定した（例えば（Moore 2002）など）対訳文アラインメント法において利用されるスコアであり，それぞれ文 $f_{j}$ と文 $e_{l}$ とを対応付けたときのスコア， $f_{j}$ を $E$ どの文

とも対応させなかったときのスコア,$e_{l}$ を $F$ のどの文とも対応させなかったときのスコアである. 最上段の選択肢 $\log \lambda$ は, $f_{j+1}, e_{l+1}$ を開始位置とする文のまとまりのぺアの被約費用が, $f_{j}, e_{l}$ を含む文のまとまりのペアの被約費用よりも必ず大きくなるときに選択される。すべての $1 \leq j \leq|F|, 1 \leq l \leq|E|$ について動的計画法によって $q[j, l]$ を計算したのちに, それらのうち最大値をとることで被約費用の最大値を求めることができる。 さらに， $q[j, l]$ を計算する際に (11) のどの式をもとに計算したかを記憶しておけげ，最大值をとる $q[j, l]$ からバックトラッキングを実行することによって被約費用を最大とする $x_{i j k l}$ を求めることができる。すなわち, (11)の 4 種類の選択肢のうち，下 3 種類の選択肢のいずれかが利用されたのであればそれぞれの式中に出現している $q[j-1, l-1], q[j-1, l], q[j, l-1]$ のいずれかに遷移し， バックトラッキングを続ける. もし最上段の選択肢 $\log \lambda$ が利用されたのであれば，そこでバックトラッキングを終了する. バックトラッキングを終了したときの状態を $q\left[j^{\prime}, l^{\prime}\right]$ とすると, $i=j^{\prime}+1, \quad k=l^{\prime}+1, \quad$ として $i$ と $k$ が求まる. すべての $q[j, l]$ を計算する動的計画法は $O(|F||E|)$, バックトラッキングは高々 $O(|F|+|E|)$ 時間で実行できるため，Smith-Waterman 法によって被約費用を最大とするアイテムを効率的に選択できる。

列生成法の手順を図 4 に示す。まず RMP に含まれる変数の集合を $\mathcal{M}^{\prime}=\left.\{x_{1|F|, 1|E|}\right.\}$ として初期化する (line 1)、 $x_{1|F|,|| E \mid}$ はすべての文からなる文のまとまりであり, 実行可能解であることから，以降の RMP は必ず実行可能解をもつことが保証される．以降，RMP の求解7 (line 3) と Smith-Waterman 法による列生成部分問題の求解 (line 4) とを繰り返す。もしすべての変数で被約費用が負となったら (line 5), その時点で MP の最適解が得られていることになるので,最後に現在の RMP に整数制約を追加したうえで整数線形計画問題を解いて得られた解を出力する (line 8)．ここで，RMP に整数制約を追加して得られた解が必ずしも元の MP に整数制約を追加して得られた解と一致するわけではないことに注意する必要がある。 すなわち, 提案法

1: $\bar{w}_{1|F|, 1|E|}$ を計算し変数 $x_{1|F|, 1|E|}$ を RMP に追加する.

## 2: loop

RMP を解く.

列生成部分問題を解き，被約費用を最大とするアイテム $x_{i j k l}$ を選択する.

if 最大の費約費用 $\bar{w}_{i j k l}$ が負 then

## break

end if

RMP に変数 $x_{i j k l}$ を追加する.

end loop

10: RMP に整数制約を追加し，整数線形計画問題として解く.

図 4 列生成法を用いた近似アルゴリズム


はヒューリスティクスであり，必ずしも厳密な最適解を得られるわけではない，そこで検証によって厳密解との差を評価する。

## 6 検証

## 6.1 検証設定

提案手法の有効性を検証する。非単調な系列アラインメントはいくつかの研究で検証されているが，正解の対応付けが公開されていないことから，今回は検証のためのデータとして文対応が既知である日本語と英語の対訳文書から生成した人工データを用いた。対訳文書はそれぞれ約 25,000 文からなる。この文書から取り出した 2,500 文から文の長さが一定以上に長いものと短いものとを除いたものをテストデータを生成する元データ，残りを翻訳確率等を推定するための訓練データとして用いた。

テストデータの生成手順は以下のとおりとする。まず，元デー夕のそれぞれの文書集合から， $K$ 個の対応関係にある連続する文のまとまりをランダムに取り出す。なお，対応関係にある文のまとまりには，対訳関係になっていない文も含まれる，その後，取り出した文のまとまりをランダムに並べなおしたのちに，各まとまりに含まれる文を順に並べることで文のまとまり単位での移動があるデータセットを作成した. テストデータの文の数は日本語, 英語ともに 60 文とし，まとまりの数は $K=1,3,6,12,20$ とした。このデータセットを以下では対称データセットとよぶ. $K=1$ のときは単調な対訳文アラインメントを求める問題となっている. 次に, 日本語と英語の文の数が異なるデータセットも同様に作成した。こちらでは日本語の文数を 60 文,英語の文数を 40 文とし, 日本語の 20 文は対応する文が存在しないようにした。日本語のまとまりの数は $K=3,6,12$ とし, 英語のまとまりの数は日本語のまとまりの数の $2 / 3$ とした. このデータセットを以下では非対称データセットとよぶ。最後に，日本語と英語からそれぞれ 60 文選ぶが，そのうち対応関係にあるのは 40 文であり, 残りの日本語・英語の 20 文は対応する文が存在しないようなデータも作成した，以下では対応なしデータセットとよぶ，文のまとまりの数は $K=3,6,12$ とし, そのうち $1 / 3$ については対応する文が存在しないものとした.

比較対象として, Moore らによる系列マッチングに基づく手法 (Moore) と, 二部グラフの重み最大マッチングとして解いた方法 (BM) とを用いた。なお，重み最大マッチングにおける対応付けの重みは式 (1)を用いた。評価は Moore(Moore 2002) にならって, 文の対応付けの再現率 (recall), 適合率 (precision), F 値 (F-measure) を算出した。対称, 非対称の各データセットについて, 異なる $K$ ごとに 5 つのデータセットを生成し, その平均値を最終的な評価値とした.翻訳確率の算出には GIZA++(Och and Ney 2003) を用いた. 整数線形計画問題のソルバとして ILOG CPLEX を用いた。文のまとまりの個数に対するぺナルティ $\lambda$ は， $\lambda=0.1$ と $\lambda=0.01$ の 2 種類を試した。

## 6.2 結果

実験結果を表 $1,2,3$ に示す. 表中の SP + ILP は集合分割問題を整数線形計画問題ソルバで解いた結果, SP + CGは集合分割問題を列生成法で解いた結果を表す。また，BM は二部グラフマッチングによって対訳文アラインメントを行った結果, Moore は Moore らの手法 (Moore 2002）を適用した結果をそれぞれ表す。表より，対称データセットで $K=1$ の場合を除く，いずれのデータセット，および $K$ の值においても， $\lambda=0.1$ としたときの提案手法 (厳密解) が 2 種類のベースラインよりも高い $\mathrm{F}$ 值を示していることが分かる。対称データセットで $K=1$ の場合は単調な対訳文アラインメントとなることから，単調性を仮定する Moore の手法の方がやや高い $\mathrm{F}$ 値を示している。しかし, 提案法との差分は 0.003 ポイントと小さい. 次に $\lambda$ の值の

表 1 再現率, 適合率, $\mathrm{F}$ 値の比較（対称デー夕）

表 2 再現率, 適合率, $\mathrm{F}$ 値の比較（非対称デー夕)

表 3 再現率, 適合率, $\mathrm{F}$ 値の比較（対応なしデータ）

違いによる影響を厳密解同士で比較すると, いずれのデータセットにおいても $K=1,3$ のときは $\lambda=0.01$ の方が $\lambda=0.1$ のときよりもやや高い $\mathrm{F}$ 值を示し, 一方で $K=6,12,20$ のときには $\lambda=0.1$ の方が高い值を示していることが分かる. これは， $\lambda$ が文のまとまりの個数に対するぺナルティであり，入が小さいほど大きなぺナルティを与えていることによって説明できる。つまり，Kが小さいときは文のまとまりの個数が小さくなりがちな $\lambda=0.01$ の方がよい結果を出力し， $K$ が大きいときはより多くのまとまりが出現することを許容する $\lambda=0.1$ の方がよい結果を出力していると考えられる．Mooreによる対応付け手法は単調性を仮定した手法であるため，他の方法と比べると極端に $\mathrm{F}$ 値が悪くなっているのが確認できる.

次に提案手法で厳密解を求めたときと, 列生成法による近似解を求めたときとの結果を比較する。再現率, 適合率, $\mathrm{F}$ 値の低下度合いは, 今回の検証では最大で 0.08 ポイント程度の低下におさまっていることが確認できた. 特に $\lambda=0.1$ のときはいずれのデータに対しても 0.03 ポイント程度の低下におさまっている。なお, 表 1 では列生成法のほうが厳密解法よりも再現率,適合率, $\mathrm{F}$ 値が大きくなる結果が得られているが, これは目的関数と評価指標とが必ずしも一致するわけではないことに起因すると考えられる.

厳密解法と列生成法との平均計算時間の比較を表 4 に示す。表より, CPLEXで数十秒から数百秒かかっていた問題が列生成法によって数秒で解けていることが確認できる。すべてのデー 夕で 30 倍から 400 倍程度の高速化が達成できたが，特に変数の総数が多い対称デー夕, 対応なしデータではほぼすべての設定で 100 倍以上の高速化が確認できた。表 5 に利用された変数の数を示す。集合分割問題をそのまま整数線形計画問題ソルバによって解くと，今回扱ったような数十文程度の対応付けであっても $10^{6}$ 個程度の変数を明示的に扱う必要がある. 扱う変数の個数が多いほどソルバによる求解には時間がかかるため, 文の数が増加するとさらに求解に時間がかかる可能性が高い。一方で列生成法を用いた場合は，最適解において非零になる可能性がある変数しか扱わないため, 最終的に利用された変数は $10^{3}$ 個程度となり, 問題をソルバで素朴に解いた場合と比較して利用される変数の数が大幅に少ないことが分かる. 問題中に出現する変数の個数が少ないとソルバによって高速に解を求めることが可能であるため, 列生成法
表 4 実行時間の比較

(a) 対称データ $(\lambda=0.1)$

(b) 対称データ $(\lambda=0.01)$

(c) 非対称データ $(\lambda=0.1)$

(e) 対応なしデータ $(\lambda=0.1)$

(d) 非対称データ $(\lambda=0.01)$

(f) 対応なしデータ $(\lambda=0.01)$

は高速に動作したと考えられる。

提案法は NP 困難問題である集合分割問題を解いているため，厳密解法の実行時間は問題サイズに対して指数的に増加する。一方で，既存の単調性を仮定した動的計画法に基づく対訳文アラインメント法は, 問題サイズに対して多項式時間で動作する。 そのため, 提案法は列生成法による近似解法を用いたとしても実行時間的には既存手法に対する優位性はない。一方で，対訳文アラインメントはおもに対訳文コーパスを作成するために用いられる技術であり，コー パス生成に用いるために問題とならない速度で動作することが重要である。実験結果が示すように，列生成法による対訳文アラインメント法は数十文からなる対訳文書の文アラインメントを数秒で行うことができるため，提案法は十分に実用に足る技術であるといえる.

最後に，対称データにおいて入力文のサイズを変化させたときの，厳密解法と列生成法の実行時間の変化を図 5 に示す。図の横軸が入力のサイズであり，縦軸が実行時間を表す。なお,実行時間が 3,600 秒を超えたら実験を打ち切りとしている。 入力サイズが大きくなるほど，列生成法と厳密解法の差が広がる傾向があることが分かる.
表 5 出現した変数の数の比較

(a) 対称データ $(\lambda=0.1)$

(b) 対称データ $(\lambda=0.01)$

(c) 非対称デー夕 $(\lambda=0.1)$

(e) 対応なしデータ $(\lambda=0.1)$

(d) 非対称データ $(\lambda=0.01)$

(f) 対応なしデータ $(\lambda=0.01)$

図 5 入力サイズを変化させたときの実行時間の変化

## 7 おわりに

本論文では，対応付けの連続性を考慮しつつ非単調な系列アラインメントを求めるための方法を提案した。集合分割問題として定式化し, 整数線形計画法を用いて解くことによって, 既存手法では対応付けをとるのが難しい状況でも対応付けができることを示した. このような方法は，特に単調性を仮定できないような文書対に対する対訳文アラインメントにおいて効果的である。 さらに，数理計画法の分野で大規模な問題を解く際に利用される技法である列生成法を適用することによって, 最適化問題を解くときに扱わなけれげならない変数の数および各変数のスコアの計算に必要となる動的計画法の実行回数を劇的に減らすことができ, 結果として高速な求解を可能とした。

## 参考文献

Braune, F. and Fraser, A. (2010). "Improved Unsupervised Sentence Alignment for Symmetrical and Asymmetrical Parallel Corpora." In Proceedings of COLING 2010, pp. 81-89.

Brown, P. F., Petra, S. A. D., Pietra, V. J. D., and Mercer, R. L. (1993). "The Mathematics of Statistical Machine Translation: Parameter Estimation." Computational Linguistics, 19 (2), pp. 263-311.

Deng, Y., Kumar, S., and Byrne, W. (2007). "Segmentation and Alignment of Parallel Text for Statistical Machine Translation." Natural Language Engineering, 13 (3), pp. 235-260.

Gale, W. A. and Church, K. W. (1993). "A Program for Aligning Sentences in Bilingual Corpora." Computational Linguistics, 19 (1), pp. 75-102.

Korte, B. H. and Vygen, J. (2008). Combinatorial Optimization: Theory and Algorithms. Springer Verlag.

Lübbecke, M. E. and Desrosiers, J. (2005). "Selected Topics in Column Generation." Operations Research, 53 (6), pp. 1007-1023.

Moore, R. C. (2002). "Fast and Accurate Sentence Alignment of Bilingual Corpora." In Proceedings of AMTA'02, pp. 135-144.

Nie, J.-Y., Simard, M., Isabelle, P., and Durand, R. (1999). "Cross-language Information Retrieval Based on Parallel Texts and Automatic Mining of Parallel Texts from the Web." In Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 74-81. ACM.

Och, F. J. and Ney, H. (2003). "A Systematic Comparison of Various Statistical Alignment Models." Computational Linguistics, 29 (1), pp. 19-51.

Qu, Z. and Liu, Y. (2012). "Sentence Dependency Tagging in Online Question Answering Forums." In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 554-562, Jeju Island, Korea. Association for Computational Linguistics.

Quan, X., Kit, C., and Song, Y. (2013). "Non-Monotonic Sentence Alignment via Semisupervised Learning." In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 622-630, Sofia, Bulgaria. Association for Computational Linguistics.

Smith, T. F. and Waterman, M. S. (1981). "Identification of Common Molecular Subsequences." Journal of Molecular Biology, 147, pp. 195-197.

竹中要一, 若尾岳志 (2012). 地方自治体の例規比較に用いる条文対応表の作成支援. 自然言語処理, 19 (3), pp. 193-212.

角田孝昭, 乾孝司, 山本幹雄 (2015). 対をなす二文書間における文対応関係の推定. 自然言語処理, $22(1)$, pp. 27-58.

Wu, D. (1997). "Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora." Computational Linguistics, 23 (3), pp. 377-403.

## 略歴

西野正彬：2008 年京都大学大学院情報学研究科修士課程修了. 同年, 日本電信電話株式会社入社. 現在, コミュニケーション科学基礎研究所研究員. 自然言語処理, アルゴリズムの研究に従事. 博士 (情報学). 情報処理学会, 人工知能学会, 言語処理学会, ACL 各会員.

鈴木潤：1999 年慶應義塾大学理工学部数理科学科卒業. 2001 年同大学院理工学研究科計算機科学専攻修士課程修了. 同年, 日本電信電話株式会社入社. 2005 年奈良先端大学院大学博士後期課程修了. 2008-2009 年 MIT CSAIL 客員研究員. 現在, NTTコミュニケーション科学基礎研究所に所属. 博士（工学). 主として自然言語処理, 機械学習に関する研究に従事. ACL, 情報処理学会, 言語処理学会各会員.

梅谷俊治：1998 年大阪大学大学院基礎工学研究科博士前期課程修了. 2002 年京都大学大学院情報学研究科博士後期課程指導認定退学. 博士 (情報学). 豊田工業大学助手, 電気通信大学助教を経て, 現在, 大阪大学大学院情報科学研究科准教授. 組合せ最適化の研究に従事. 日本オペレーションズ・リサー 千学会, 情報処理学会, 人工知能学会, INFORMS, MOS, AAAI 各会員.
平尾努：1995 年関西大学工学部電気工学科卒業. 1997 年奈良先端科学技術大学院大学情報科学研究科博士前期課程修了. 同年株式会社 NTT データ入社. 2000 年より NTT コミュニケーション科学基礎研究所に所属. 博士（工学). 自然言語処理の研究に従事. 言語処理学会, 情報処理学会, ACL 各会員.永田昌明：1987 年京都大学大学院工学研究科修士課程修了. 同年, 日本電信電話株式会社入社. 現在, コミュニケーション科学研究所主幹研究員 (上席特別研究員). 工学博士. 統計的自然言語処理の研究に従事. 電子情報通信学会, 情報処理学会, 人工知能学会, 言語処理学会, ACL 各会員.

