Blog
入力\(x\)から出力\(y\)への関数を学習する機械学習の中で、出力が構造を有している問題は構造学習（Structured Output Learning）と呼ばれ、自然言語処理をはじめ、検索のランキング学習、画像解析、行動分析など多くの分野でみられます。
今回はその中でも複数の構造情報を組み合わせても効率的に学習・推論ができる双対分解による構造学習について紹介をします。
# 構造学習についてよく知っているという方は双対分解による構造学習のところまで読み飛ばしてください。
構造学習の導入
構造を有した出力の例として、
- ラベル列 （品詞、形態素列の推定、時系列におけるアクションの推定、センサ列）
- 木 （係り受け解析における係り受け木、構文解析木、談話分析、因果分析）
- グラフ （DAG:述語項構造による意味解析 二部グラフマッチング:機械翻訳の単語対応）
- 順位付集合（検索における順位決定）
などがあります。
構造学習は出力の候補が複数存在する多クラス分類の一種と考えることもできますが、大きく違うのは出力の候補空間に組み合わせ的構造があり、 いくつかの操作を効率的に行える点です。
例として単語列\(w_1 w_2, \ldots, w_n\)が与えられた時に、各単語の品詞\(y_1 y_2, \ldots, y_n\)を推定する問題を考えてみます。長さ\(n\)で、それぞれの位置の品詞候補が\(k\)個の時、候補解の数は\(n^k\)個になります。
入力から出力を推定するために、入力と出力のペアから決定されるスコア関数\(s(x, \mathbf{y})\)を導入しましょう。このスコア関数は、入力と出力が正しい対応がとれているほど高い値をとるような関数です。
訓練データを利用した学習、もしくは外からの知識によってこのスコア関数が与えられたとします。
新しいデータに対する出力を推定する場合は\(s(x, \mathbf{y})\)を最大にするような\(\mathbf{y}^* = \arg \max_{\mathbf{y} } (x, \mathbf{y})\)を求めることにより行います。\(\arg \max_y f(y)\)は\(f(y)\)が最大値をとるような\(y\)を返す関数です。
スコアが最大となる出力を求めるには候補解の数が少なければ、全ての候補解についてスコアを調べれば良いですが、今回の場合、候補解の数が\(n^k\)個あるので、計算量的に困難です。そこで、最大値が効率的に求められるように\(s(x, \mathbf{y})\)に制限を加えます。
ラベル列の場合、よく行われる方法はマルコフ性の導入です。つまり、\(y_i\)は周辺のラベル、\(y_{i-1}\)、\(y_{i+1}\)にしか影響を及ぼさないという仮定を導入します。
これにより、スコア関数は依存関係がある部品から決定されるスコア関数の和\(s(x, \mathbf{y}) = \sum_i s(x, y_{i-1}, y_{i})\)に分解できます。このように分解さえすれば、最大値はよく知られたビタビ法により\(O(n k^2)\)時間で求めることができます。一般に\(t\)個隣のラベルまで影響を及ぼすようにスコア関数を制限すると\(O(n k^{t-1})\)時間で求められます。
Structured Perceptron
実は、この最大となる出力\(y^*\)が効率的に求められさえすれば、訓練データを用いてスコア関数の学習を行うことができます。その中で最も単純ながら強力なStructured Perceptronを紹介します。
“Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms”, Michael Collins, ACL 2002 [pdf]
まず、入力と出力のペアから決定される\(m\)次元実数の特徴ベクトル\(\phi(x, \mathbf{y}) \in R^m\)を用意します。
次にスコア関数をモデルパラメータである重みベクトル\(\mathbf{w} \in R^m\)と特徴ベクトルの内積として次のように定義します。\(s(x, y) = \mathbf{w}^T \phi(x, y)\)．
訓練データ\({(x^i, y^i)}\)が与えられた時、学習の目標は正解に対するスコアがそれ以外の候補解に対するスコアより大きくなるようにスコア、つまり重みベクトルを設定することです。
\(s(x^i, y^i) \geq s(x^i , y) (y^i \neq y)\)
このようにするためには、訓練例（x^i, y^i)が与えられた時、まずそれに対する現在のモデルによる候補解\(y^* = \arg \max_y s(x^i, y)\)を求めます。この\(y^*\)が正解\(y^i\)とあっていればいいのですが、あっていない場合は次のように更新します。
\(\mathbf{w} := \mathbf{w} + \phi(x^i, y^i) – \phi(x^i, y^*)\)
なんとこれだけです。
この更新を全ての訓練例に対し繰り返し適用していくと、正解のペアに対しては高く、それ以外には低いスコアを出すようなスコア関数を得ることができます。
構造学習の課題
ここまでで、\(\arg \max_{\mathbf{y} } s(x, \mathbf{y})\)さえ効率的に求まりさえすれば構造を持った出力問題の学習、推論できるというのをみてきました。これまで多くの研究のなかで様々な問題に対し、どのようにスコア関数を分解すればarg maxが効率的に求まるかが知られています。ラベル列であればビタビ、係り受け解析などの全域木であればMST系のアルゴリズム、木であればCFG化+CYKアルゴリズム、重み付き二部グラフであればLPなどです。
ちょっと高度な話になりますが、CRFなどではarg max関数にくわえて全ての出力に対する和、\(\sum_y s(x, y)\)（分配関数など呼ばれます）も効率的に求める必要があります。arg maxが効率的に求められる多くの問題は\(\sum_y\)も同様に効率的に求められますが、arg maxのみが効率的に求められる問題もいくつか存在します（二部グラフの重み最大マッチングなど）
また真の最大値でなくてもビームサーチなどを利用して近似解さえ求まればよいことが知られています。探索と学習方法の関係については次のACL tutorialで詳しく解説されています。
“From structured prediction to inverse reinforcement learning”, H. Daume. ACL 2010 turorial [pdf]
スコア関数の自由度と計算量はトレードオフの関係にあります。より強力な情報を利用してモデル化しようとすればするほど計算量は増大します。そして、アルゴリズムも実装するのがためらわれるほど複雑になります。
例えば先程のマルコフモデルによる品詞推定では、「文中には高々１回しか動詞は出現しない」や「同じ単語には同じ品詞が付与される」といった文全体のグローバルな情報を扱うことはできません。ラベルの種類数を増やすことで、こうしたグローバルな情報を伝えることもできますが計算量は一気に増大します。
これに対し、一度効率的に求められる簡単なモデルで求めた後に焼きなまし法やMCMCなどでグローバルな情報をいれたスコア関数の最適化を行う方法もありますが、大抵の場合非常に計算量が大きくなりますし、最適な解が得られるという保障がなくなります。
最近では線形計画法を利用してこうしたグローバルな情報を導入したとしても最適解を求めるという方法も多く使われるようになってきました。昔より高速になったとはいえ、実用的には計算量の問題、学習の問題が多く残されています。
双対分解による構造学習
ようやく今回話したい話題に来ることができました。
構造学習において、より強力な情報を使いつつ、最適解（arg max）を効率的に求められる方法の一つとして双対分解を利用する方法が最近提案されました。
Dual Decomposition for Parsing with Non-Projective Head Automata.
T. Koo, A. M. Rush, M. Collins, T. Jaakkola, and David Sontag, EMNLP 2010 [pdf]
On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing.
A. M. Rush, D. Sontag, M. Collins, and T. Jaakkola, EMNLP 2010 [pdf]
（一つ目の論文はbest paperに選ばれています。）
これらの手法は元々グラフィカルモデルのMAP推定などで発展しており、著者メンバーを見ればグラフィカルモデルに強いSontag, Jaakolaらが発展させてきた最適化手法をNLP屋のCollinsやKooらがNLPに応用したということが想定できます。
この方法は名前のゴツさとは裏腹にアルゴリズム、実装はStructured Perceptron並に簡単です。
先ほど説明したように構造学習の場合、使える情報と\(\arg \max\)を効率的に求められるかどうかはトレードオフの関係にあります。学習に役立ちそうな情報を組み合わせて使えば使うほど計算量は爆発しアルゴリズムも煩雑になります。
これに対し、使いたい情報がいくつかの関数に分解でき、それぞれのスコアの最適化が効率的に求められる状況を考えてみます。ここでは二つの目的関数f, hに分解できるとしましょう。\(\arg \max_y g(y) + h(y)\)は効率的に求めることはできない（例えばNP完全）が、\(\arg \max_y g(y)\)、\(\arg \max_y h(y)\)は効率的に求められる場合です。この時、次の問題を考えます。
\(\arg \max_{y, z} f(z) + h(y)\) 但し \(y = z\)
この解を\(L^*\)とします。
ここでのポイントはそれぞれの関数に対し異なる変数を用意し、そして、それらの変数が一致するという制約を入れるということです。
これは一見、元の問題と同じようにみえ、実際これらの最適解は同じですが、これに対する双対問題を考えると、世界がまるでかわってきます。はじめに制約付き問題に対しLagrange緩和を適用し、次の問題を考えます。
\(L(u, y, z) = f(z) + h(y) + \sum_i u_i (y_i – z_i)\)
ここで、\(u_i\)はLagrange変数であり、\(y_i, z_i\)はそれぞれ\(y\)と\(z\)が内部に構造を有している場合、それらを部品に分けた時の変数です。例えば先程の品詞列の推定の場合は各品詞に対応します。
次に、\(z, y\)に関して最大値をとるような関数を考えます。
\(L(u) = \max_{y, z} L(u, y, z) = \max_z (f(z) – \sum_i u_i z_i) + \max_y (h(y) + \sum_i u_i y_i)\)
この関数は\(y = z\)の制約がないので、最初の問題より広い解空間を持ち、常に\(L^* \leq L(u)\)が成り立ちます。つまり最初の問題の上限を与えています。では、\(u\)に関して最小値をとるにすることを考えます。この時、双対定理より
\(L^* = \min_u L(u)\)
が成り立ちます。
さて、\(\min_u L(u)\)はどのように解けるでしょうか。これは凸関数であり、\(u\)に関する勾配を求めることができれば勾配降下法により最適化できます。
\(L(u)\)はmax関数を含みますので微分不可能ですが、劣微分を求めることができます。劣微分は\(L(u)\)の下側にあるベクトル集合からなりますが、その一つ\(d_u\)は次のように求めることができます。
\(d_u = y^* – z^*\)
但し、
\(z^* = \arg \max_{z } f(z) – \sum_i u_i z_i\)
\(y^* = \arg \max_{y } h(y) + \sum_i u_i y_i\)
それぞれのモデルは効率的に求めることができますので勾配も効率的に求めることができます。
そして、勾配法に基づき
\(u := u – \mu (y^* – z^*)\)
のように更新します。但し\(\mu\)は適切に決めたステップ幅です。
この更新を繰り返すことにより\(L(u)\)を小さくしていき\(y^* = z^*\)となった時は主問題と双対問題の値が一致した時なので最適解に達成したことが保障されます。実際、実験結果により、元々の問題がNP完全であるような場合でさえ、殆どの問題で最適解を高速に求めることができたことを報告しています。
この更新式の意味についてもうちょっと考えてみます。ラグランジュ変数である\(\mathbf{u}\)は、二つの最適化問題を一致させる調整役を果たしています。二つの異なるモデルによる解が一致しない場合には、一致しない点を中心にペナルティを更新します。それぞれの問題の最適化の際はこのペナルティ付きで最適化を行うので、一致するような解が選ばれるようになっていきます。
学習の際は一致するという制約を無視してそれぞれのモデルを独立に学習させる方法（local training)でもよいですし、双対分解による最適化を学習時にも適用して学習することも可能です。
双対分解の応用
先ほど上げた論文から実際のアプリケーション例を紹介しましょう。
Kooらは係り受け解析問題に対し双対分解を適用しました。
係り受け解析では与えられた単語列に対し次の条件を満たすような係り受け関係（木）を求めます (i) 各単語には係り先となる単語が一つ存在する (ii) 係り受け関係から構成されるグラフには閉路が存在しない
出力構造が木であることから、スコアにはそれほど複雑なものが使えず、親子以外の情報を使おうとするとアルゴリズムは途端に複雑になり、ようやく今年に入って三つの単語の関係をスコアに考慮しても多項式時間で効率的にarg maxが求まるような方法が提案されている状況でした（これもKooらによる）
Kooらは、a. 抽出されるグラフが木の条件を満たすが、親子関係の情報しかスコアに反映させない b. 親兄弟についての情報を自由にスコアに反映できるが、抽出されるグラフが木である保障はない というa. b. の二つの解を一致させるという最適化問題を解くことにより、出力が木であることが保障されていながら自由に情報を利用できる係り受け解析木を作りました。
これにより最高精度を達成しながら一文あたり数十msでパースできるような驚異的な係り受け解析器を作ることに成功しています。
Rushらは構文解析とTrigram Taggingを組み合わせました。CFG+CKYによる構文解析では一般に葉の部分でのBigram以上のマルコフ情報を組み込むことは困難でしたが、CKYで得られる結果とTrigramモデルにより得られる結果を一致させるという問題を考えることにより、アルゴリズムを複雑にすることなく、よりリッチな情報を組み込むことに成功しています。
また、異なる語彙化構文解析を組み合わせて解析できたことも報告しています
まとめ
双対分解を利用することで複数の異なるモデルが一致するような結果を効率的に求められるようになります。この際、それぞれのモデルの最適化が効率的に解けることさえ保障されていれば、全体の最適化を最適保障ありで求めることができます。そして、その最適化はパーセプトロン並に簡単です。
同時に利用することが一見できなさそうな特徴量やルールもこの方法を利用することで統合することができます。
自然言語処理のように複数の処理のパイプラインによって問題を解く場合や、複数の情報/システムを結合させるような場合、また最適化の制約のせいで、重要な情報を利用できない場合などに有効な方法だと考えられます。
