Blog
海野です。ちょっと時間があいてしまいましたが、昨年の12月に開催されたNTCIR-9という会議のRecognizing Inference in TExt (RITE)というタスクに、前職の方々と共著で出場しました。
Syntactic Difference Based Approach for NTCIR-9 RITE Task.
Yuta Tsuboi, Hiroshi Kanayama, Masaki Ohno and Yuya Unno. NTCIR-9, 2011. [pdf]
含意関係認識といわれるこのタスクは、大雑把に言うと与えられた2つの文が同じ意味のことを言っているかどうか判定しなさいというタスクです（厳密には一方からもう一方が帰結できるかの判定です）。今日は、その中で使ったTree Edit Distance (TED) について解説します。
TEDは2つの順序付き木が与えられた時、その差を通常の編集距離（Edit Distance）同様、追加・削除・置換の3操作の最小の組み合わせで表す問題として定式化されます。そして、木の再帰性と非常に相性がよく、この問題は木のサイズの多項式時間で解くことができます。これを示したのが、以下の20年以上前の論文です。
Simple fast algorithms for the editing distance between trees and related problems.
Kaizhong Zhang and Dennis Shasha, SIAM J. Comput. Vol. 18, No. 6, pp. 1245-1262, 1989.
木に対する3つの編集操作は、例えば以下の図のような操作です。
この技術を何に応用するかということですが、類似した木構造の差分を表現するのに適しています。今回、与えられた2つの文が同じ事を言っているか否か、というタスクを行いました。そこで、係り受け構文解析をおこない、2つの入力文を木構造にして、両者に対するTEDを計算することで構文木上の差分を明確にしました。すると、例えば否定の「ない」が挿入された、テニヲハが変更された、といった文間の差分が明確になります。これを機械学習とくっつけることで、どういった変更が意味を変更するのに寄与しているかが学習できるという寸法です。
以下ではTEDのアルゴリズムについて解説します。まず最初に、通常の編集距離のおさらいです。編集距離は配列に対する編集操作ですから、配列\(S\)を先頭要素\(H(S)\)と残り\(T(S)\)に分解します。2つの配列が与えられたら、先頭要素同士の比較と、残り要素同士の比較に分解できます。配列中の2要素間の置換コストを\(gamma\)という関数で表すと（追加と削除はそれぞれ\(emptyset\)を引数に取るとする）、以下の式で計算できます。
上記の再帰式を動的計画法化させることで、典型的な多項式時間アルゴリズムが完成しました。
さて、ではこの入力が木だったらどうなるでしょう。配列を先頭とそれ以外に分解するのと同様、木の場合もルートとそれ以外に分解すればよさそうです。ところが、ルートの子ノードが複数あると、ルート要素を取り除いたときに木が複数できてしまい、再帰的に記述できません。そこで、最初から入力は「順序付きの木の集合」ということにします。この木の集合を森（forest）と呼ぶことにします。森の中の一番右の木（最右木と呼ぶことにします）のルートノードを削除すると、ルートノードの子ノードをルートとする森と、最右木以外の森の2つの森に分解されるため、再帰的に編集距離を計算できるという寸法です。
森\(F = {T_1, cdots, T_n}\)に対して、一番右の木\(T_n\)のルートノードを\(R(F)\)、\(R(F)\)の子ノードをルートとする木の集合を\(C(F)\)、\({T_1, cdots, T_{n-1}}\)を\(L(F)\)とします。下の図のようなイメージです。
この時、森\(F_1\)と\(F_2\)の間の Tree Edit Distance \(d(F_1, F_2)\)は、先と同様ノード間のコスト関数\(gamma\)を使って以下のように書けます。
なお、上記\(L(F) + C(F)\)は配列の結合を示し、\(R(F)\)以外の全要素ということを示します。通常の編集距離と極めて似た式になりました。違うのは、書き換えの時の計算が2回再起的に呼び出す部分、追加・挿入時に残り要素の計算をする部分です。
再帰的に定義できたら、最後の問題は森の異なり数です。森の異なり数がノード数の多項式サイズに収まらなければ、全体の計算量が多項式サイズに収まりません。実は、異なり数が多項式サイズでしか生成されないことがいえます。
まず、すべてのノードに帰りがけ順（post-order）で番号をつけます。すると、先の操作で生成される森に属するノードは、必ずある範囲の番号、{s, …, t}になります。これは帰納的に証明できます。例で示します。下の図を見てください。
2つの木からなる森に属するノードが{1, …, 9}だったとすると、この森の最右木のルートノードは9です。9の子供は{4, …, 8}ですし、それ以外は{1, …, 3}です。また、追加・挿入時も最右木のルートを除くと、やはり{1, …, 8}となります。いずれも、ある範囲で表現できます。ポイントは、帰りがけ順に番号をつけると、最右木のルートに最大の番号が振られる、という性質を利用しているところです。厳密な証明は省略しますが、これで森を表現するには2つの整数だけ覚えておけば良いことになります。実際は\(O(n^2)\)よりも異なり数は少なく見積もれるのですがそれも省略します。ここまできたら、メモ化再帰や動的計画法で実装すればOKです。
TED自体は20年以上前に開発され、そのアルゴリズム自体も洗練されています。普通の編集距離は有名ですが、TEDに関してはあまり言及されることが少ないのでこの記事を書きました。他にも、XMLやソースコードのような木構造を持ったデータの差分を表現するのにも使えるでしょう。また、NLPの世界でも、前述した含意関係認識など差分に注目すると効果のあるタスクで採用される例も増えているようです。
Tree Edit Models for Recognizing Textual Entailments, Paraphrases, and Answers to Questions.
Michael Heilman and Noah A. Smith. NAACL 2010. [pdf]
例えば、この論文はTEDを拡張して、自然文に対する書き換え操作を自然に表現できるようにしたり、編集操作に対して様々な制約をいれられるようにしています。拡張のため、前述した標準的な動的計画法は使えなくなっていて、代わりに貪欲法と木カーネルを使って探査を行なっています。
基礎的なアルゴリズムはたくさん知っていると、いろいろな所で応用できます。自然言語処理のような応用よりの分野は、こうした基礎をたくさん知っている人が、突然今まで無いアイデアを出してくることがあります。応用だけではなくて基礎的な勉強も大事なのだなぁということをよく痛感します。
