\textbf{系列アラインメント}とは，2つの系列が与えられたときに，その構成要素間の対応関係を求めることをいう．系列アラインメントは特にバイオインフォマティクスにおいてDNAやRNAの解析のために広く用いられているが，自然言語処理においてもさまざまな課題が系列アラインメントに帰着することで解かれている．代表的な課題として\textbf{対訳文アラインメント}\cite{moore02:_fast,braune10:_improv,quan-kit-song:2013:ACL2013}があげられる．対訳文アラインメントは対訳関係にある文書対が与えられたときに，文書対の中から対訳関係にある文のペアをすべて見つけるタスクである．統計的機械翻訳においては，対訳コーパスにおいてどの文がどの文と対訳関係にあるかという文対文での対応関係が与えられているという前提のもとで学習処理が実行されるが，実際の対訳コーパスでは文書対文書での対応付けは得られていても文対文の対応付けは不明なものも多い．そのため，対訳文書間での正しい対訳文アラインメントを求めることは精度のよいモデルを推定するための重要な前処理として位置づけられる．統計的機械翻訳以外の，例えば言語横断的な情報検索~\cite{nie1999cross}などの課題においても対訳文書間の正しい文アラインメントを求めることは重要な前処理として位置づけられる．また，対訳文アラインメントのほかにも，対訳文書に限定されない文書間の対応付けタスクも系列アラインメントとして解かれている~\cite{qu-liu:2012:ACL2012,孝昭15,要一12}．自然言語処理のタスクにおける系列アラインメント問題を解く手法は，対応付けの\textbf{単調性}を仮定する方法とそうでない方法とに大別される．単調性を仮定する系列アラインメント法は特に対訳文アラインメントにおいて広く用いられる方法であり，対訳関係にある二つの文章における対応する文の出現順序が大きく違わないことを前提として対応付けを行う．すなわち，対訳関係にある文書のペア$F$，$E$に対し，$F$の$i$番目の文$f_i$に$E$の$j$番目の文$e_j$が対応するとしたら，$F$の$i+1$番目の文に対応する$E$の文は，（存在するならば）$j+1$番目以降であるという前提のもとで対応付けを行っていた．この前提は，例えば小説のように文の順序が大きく変動すると内容が損なわれてしまうような文書に対しては妥当なものである．一方で単調性を仮定しない方法は~\cite{qu-liu:2012:ACL2012,孝昭15,要一12}などで用いられており，文間の対応付けの順序に特に制約を課さずに系列アラインメントを求める．図~\ref{fig:prevwork}は，それぞれ単調性を仮定した系列アラインメント，仮定しない系列アラインメントの例を表している．白丸が系列中のある要素を表現しており，要素の列として系列が表現されている．図では2つの系列の要素間で対応付けがとられていることを線で示している．単調性を仮定した対応付け手法では，対応関係を表す線は交差しない．一方で仮定しない手法では交差することが分かる．\begin{figure}[t]\begin{center}\includegraphics{23-2ia1f1.eps}\end{center}\caption{既存の系列アラインメント法によるアラインメント例}\label{fig:prevwork}\end{figure}系列アラインメントにおいて単調性を仮定することは，可能なアラインメントの種類数を大きく減少させる一方で，動的計画法による効率的な対応付けを可能とする．先述したように，対訳文アラインメントを行う際に単調性を仮定することは多くの対訳文書に対しては妥当な仮定である．しかし，単調性を仮定することが妥当でない対訳文書も存在する．例えば文献~\cite{quan-kit-song:2013:ACL2013}では，単調性が成り立たない文書の例として法令文書を挙げている．そのほかにも例えば百科事典やWikipediaの記事のように一つの文書が独立な複数の文のまとまりからなる場合には，文のまとまりの出現順序が大きく変動しても内容が損なわれないことがある．このような文書においては，文の順序が大きく変動しないという前提は必ずしも正しいものではないため，既存の単調性を仮定した系列アラインメント法では正しい対訳文アラインメントが行えない可能性が高い．一方で，単調性を仮定しない既存のアラインメント法では非単調な対応付けを実現できるものの，対応付けの\textbf{連続性}を考慮することが難しいという問題がある．対応付けの連続性とは，$f_i$が$e_j$と対応付けられているならば，$f_{i+1}$は$e_j$の近傍の要素と対応付けられる可能性が高いとする性質のことである\footnote{\ref{sec:setpart}節以降の提案手法の説明では，説明を簡単にするために，対応付けに順方向の連続性がある場合，すなわち$f_i$と$e_j$が対応付けられているならば$f_{i+1}$は$e_{j}$より後ろにある近傍の要素と対応付けられやすい場合のみを扱っている．しかし，実際には提案法は順方向に連続性がある場合と同様に逆方向の連続性がある場合の対応付けを行うこともできる．逆方向の連続性とは，$f_i$と$e_j$が対応付けられているならば，$f_{i+1}$は$e_{j}$以前の近傍の要素と対応付けられる可能性が高いとする性質のことである．}．もし対応付けにおいて連続性を考慮しないとすると，系列$F$中のある要素$f_i$とそれに隣接する要素$f_{i+1}$とが，それぞれ$E$中で離れた要素と対応付けられてもよいとすることに相当する．対応付けの単調性を仮定できるような対訳文書の対訳文アラインメントについては，明らかに対応付けの連続性を考慮する必要がある．さらに，単調性が仮定できないような文書のペアに対する対訳文アラインメントにおいても，ある文とその近傍の文が常に無関係であるとは考えにくい．以上より，文アラインメントにおいては連続性を考慮することが不可欠である．また，対訳文アラインメント以外の系列アラインメントを用いるタスクにおいても，対応付けの対象となる系列は時系列に並んだ文書等，何らかの前後のつながりを仮定できるものが多いことから，連続性を考慮する必要がある．単調性を仮定できない文アラインメントの例を示す．図\ref{fig:hourei}は，文献~\cite{quan-kit-song:2013:ACL2013}の検証で用いられているBilingualLawsInformationSystem(BLIS)\footnote{http://www.legistlation.gov.hk}コーパスに含まれる対訳文書における文アラインメントの例である．BLISは香港の法令文書の電子データベースであり，対訳関係にある英語・中国語の文書を保持している．図に示す対訳文は用語の定義を行っている箇所である．両言語の文を比べると，定義する用語の順番が英語と中国語とで異なっており，結果として，局所的には連続なアラインメントが非単調に出現する対訳文書となっている．\begin{figure}[t]\begin{center}\includegraphics{23-2ia1f2.eps}\end{center}\caption{法令文書における非単調な対訳文アラインメントの例}\label{fig:hourei}\end{figure}本論文では系列の連続性を考慮しつつ，かつ非単調な系列アラインメントを求めるための手法を提案する．このような系列アラインメント法は，単調性を仮定できない文書対の対訳文アラインメントを求める際に特に有効であると考える．仮に文書$F$の文が$E$の任意の文と対応してもよいとすれば，ある文のペアの良さを評価するスコアを適切に設定することによって，問題を二部グラフにおける最大重みマッチング問題\cite{korte08:_combin_optim}として定式化して解くことができる．しかし，$F$のある文が$E$の任意の文と対応してもよいという前提では，近傍の文間のつながりを無視して対応付けを行うことになる．実際の文書ではすべての文がその近傍の文と無関係であるとは考えにくいため，正しい対応付けが行えない可能性が高い．そこで，提案手法では対訳文アラインメントを組合せ最適化の問題の一つである\textbf{集合分割問題}として定式化して解く．集合分割問題は，ある集合$S$とその部分集合族$S_1,\ldots,S_N$が与えられたときに，スコアの和が最大となるような$S$の分割$\mathcal{D}\subseteq\{S_1,\ldots,S_N\}$を見つける問題である．ここで$\mathcal{D}$が$S$の分割であるとは，$S=\cup_{S_i\in\mathcal{D}}S_i$かつ$i\neqj$ならば任意の$S_i,S_j\in\mathcal{D}$について$S_i\capS_j=\emptyset$となることをいう．2つの系列$F$,$E$のある部分列に対する単調な系列アラインメントの集合を$S_1,\ldots,S_N$として表現することで，部分列に対するアラインメントの集合$S_1,\ldots,S_N$から系列全体の分割となるような部分集合を選択する問題として$F$,$E$全体に対する系列アラインメントを求めることができる．また，本論文では集合分割問題としての系列アラインメントの定式化とともに，その高速な求解法も同時に示す．提案する集合分割問題に基づく定式化を用いると，系列$F$,$E$に含まれる要素の数が増加するに伴い，急激に厳密解の求解に時間がかかるようになるという課題がある．これは，それぞれの系列に含まれる要素の総数を$|F|$,$|E|$とすると，集合分割問題に出現する変数の数\footnote{集合分割問題における変数の数は，可能な$F$,$E$の部分系列のペアの総数と等しい．詳細は\ref{sec:setpart}章を参照．}が$O(|F|^{2}|E|^{2})$となるためである．集合分割問題はNP困難であり，変数の数が増加すると各変数に対応する重みの計算および整数線形計画法ソルバを用いた求解に時間がかかるようになる．本論文ではこの課題に対処するために，多くの変数が問題中に出現する大規模な線形計画問題を解く際に用いられる，\textbf{列生成法}\cite{lubbecke05:_selec_topic_colum_gener}を用いることで高速な系列アラインメントを実現する近似解法も同時に提案する．列生成法は大規模な問題の解を，出現する変数の個数を制限した小さな問題を繰り返し解くことによって求める手法である．列生成法を用いることによって，そのままでは変数の数が膨大となり解くことができなかった問題を解くことができる．なお，列生成法を用いることで線形計画問題の最適解を得られることは保証されているが，整数線形計画問題については解を得られることは必ずしも保証されていない．そこで本論文では列生成法で得られた近似解を実験によって最適解と比較し，よい近似解が得られていることを確認する．なお，以下では説明を簡単にするために特に対訳文書の対訳文アラインメントに話題を限定して説明を進める．ただし，系列の要素間のスコアさえ定まれば提案法を用いて任意の系列のペアに対する系列アラインメントを行うことが可能である．