情報論的学習理論テクニカルレポート 2009
Technical Report on Information-Based Induction Sciences 2009 (IBIS2009)

木構造および化学構造に対する特徴ベクトル：埋め込み、検索、構造推定

Feature Vectors for Trees and Chemical Structures: Embedding,Search and Pre-Image
阿久津 達也∗Tatsuya Akutsu
Abstract: In this short article, we briefly review our recent results on feature vectors ontree structures. For edit distance between trees, it is shown that the edit distance between
two ordered trees can be approximated within a factor of O(h) by using the edit distance
between the corresponding Euler strings, and the edit distance between two unordered
trees can be approximated within a factor of O(h) by using feature vectors consisting of
the numbers of occurrences of subtrees (each induced by a node and its descendants), where
h is the minimum height of input trees. For the pre-image problem on trees (i.e., inferringa tree from a feature vector consisting of the numbers of occurrences of vertex-labeledpaths), it is shown that the problem can be solved in polynomial time in the size of an
output graph if the graphs are trees whose maximum degree is bounded by a constant andthe lengths of given paths and alphabet size are bounded by constants, but is NP-hard evenfor trees of bounded degree if the maximum length of paths is not bounded. A practicalbranch-and-bound algorithm for the pre-image problem is also reviewed.
Keywords: feature vector, kernel methods, embedding, tree edit, graph pre-image

1

まえがき
特徴ベクトルはカーネル法を始めとする機械学習手法などにおいて幅広く利用されている。一方、高速検索などを目的に文字列の編集距離の特徴ベクトルを用いた

L1 空間への埋め込みが理論計算機科学分野で研究されてきた [4]。これらを背景に、筆者はいくつかの共同研
究を通じて、木構造の編集距離の特徴ベクトルを用いた

L1 空間への埋め込み、および、パスの出現頻度に基づく特徴ベクトルからの木構造の推定という問題に取り組んできた。本稿ではその結果について概観する。

2木の編集距離の埋め込み

頂点の挿入、削除、置換の最小回数（もしくは最小コスト）として定義される。順序木の編集距離は O(n3 ) 時間で計算でき、無順序木の編集距離の計算は NP 困難であることが知られている [6]。ここで、木 T1 と木 T2 の間の編集距離を DT (T1 , T2 ) とする。この距離を特徴ベクトル間の距離により近似するのが目標である。
順序木の場合には、木を深さ優先探索した結果得られるオイラー文字列を用いることにより、順序木の情報を文字列に変換することができる。木 T に対するオイラー文字列を s(T ) とし、T1 , T2 のうち、低い方の木の高さを h とすると、
1D (s(T1 ), s(T2 )) ≤ DT (T1 , T2 ) ≤ (2h+1)DS (s(T1 ), s(T2 ))2 S木の編集距離は文字列の編集距離を（根付き）木に拡が成立する [2]。なお、DS (s1 , s2 ) は文字列 s1 , s2 に対張したものであり、木 T1 を木 T2 に変換するのに必要なする編集距離である。この結果は木の高さが低い場合に∗ 京都大学

化学研究所 バイオインフォマティクスセンター,〒 611-0011 京 都 府 宇 治 市 五ヶ庄, tel. 0774-38-3015, e-mailtakutsu@kuicr.kyoto-u.ac.jp,
Bioinformatics Center, Institute for Chemical Research, Kyoto
University, Gokasho, Uji, Kyoto 611-0011, Japan.

は、オイラー文字列間の編集距離により順序木間の編集距離が良い精度で近似できることを示しており、文字列の編集距離に対する埋め込みを用いると、順序木間の編集距離が効率的に埋め込める事を示唆している。なお、

木の高さが高い場合には意味のある近似精度とはならないので、その場合に対する拡張についても研究を行っている [3]。
無順序木の場合には、各頂点とその子から誘導される部分木で同型なものの個数を並べた特徴ベクトルをφ(T ) とする。この特徴ベクトルに対し、

4

おわりに木の編集距離の埋め込みについては木の高さに制限のない場合については未解決であり、高速検索その他の応用とともに、今後の課題となっている。
一方、グラフの pre-image 問題については、理論面からは一般的なグラフ構造の場合の計算複雑度の解析、ま1
φ(T1 )−φ(T2 )1 ≤ DT (T1 , T2 ) ≤ φ(T1 )−φ(T2 )12h + 2

た、応用面からは枚挙と枝刈りに基づく手法の更なる効が成立する [7]。この結果は木の高さが低い場合には、特題となっている。

率化、および、化学構造設計への具体的応用が今後の課徴ベクトル間の L1 距離により、無順序木間の編集距離が良い精度で近似できることを示している。

謝辞3する。

特徴ベクトルからの構造推定

本稿で述べた研究の共同研究者各位に感謝の意を表サポートベクターマシン (SVM) などに代表されるカーネル法においては、カーネル関数は特徴ベクトルの内積

参考文献として定義される。SVM などを用いて精度の高い予測[1] T. Akutsu and D. Fukagawa, “Inferring a graphを行うためには、もとのデータの性質を反映した特徴ベfrom path frequency”, Lecture Notes in Computer

クトルを設計することが重要であり、数多くの研究が行Science, 3537:371–382, 2005.

われてきた。一方、与えられた特徴ベクトル v からもとの構造 φ−1 (v) を計算する問題は pre-image 問題とよばれ、機械学習分野でもいくつかの研究が行われてきた[5]。しかしながら、計算量の観点からはほとんど研究さ[2] T. Akutsu, “A relation between edit distance forordered trees and edit distance for Euler strings”,
Information Processing Letters, 100:105–109, 2006.

れていなかったため、木構造を対象にラベル付きパスの[3] T. Akutsu, D. Fukagawa, and A. Takasu, “Approx-

出現回数からなる特徴ベクトルを用いた場合についてのimating tree edit distance through string edit dis-

研究を行い、以下の結果を得た [1]。

tance”, Algorithmica, to appear.

• パスの最大長、頂点の最大次数、（頂点の）ラベルの種類のいずれもが定数である場合には、v から[4] A. Andoni and K. Onak, “Approximating edit
distance in near-linear time”, Proc. ACM An-

φ−1 (v) の計算（有無の判定を含む）は多項式時間で可能。

nual Symposium on Theory of Computing, 199–204,2009.

• 頂点の最大次数、ラベルの種類のいずれもが定数で[5] G.H. Bakir, A. Zien, and K. Tsuda, “Learning to

あってもパスの最大長に制限がなければ NP 困難。

find graph pre-images”, Lecture Notes in Computer
Science, 3175:253–261, 2004.

• パスの最大長が定数であっても、頂点の最大次数、ラベルの種類に制約がなければ NP 困難。
化学構造においては、ベンゼン環などを 1 個の頂点と[6] P. Bille, “A survey on tree edit distance and relatedproblem”, Theoretical Computer Science, 337:217–239, 2005.

みなしてしまえば木構造を持つものが多い。そこで、上記の pre-image 問題に対するアルゴリズムを新規化学構造の設計に応用することが考えられる。しかしながら、上記アルゴリズムは多項式の次数が高すぎて実用的でない。そこで、木構造の効率的枚挙といくつかの枝刈り手法を組み合わせた、より実用的なアルゴリズムを開発している [8]。現時点では、水素原子を除いて 20〜30 原子程度までのサイズの木状構造を持つ化合物に対して現実的な時間で φ−1 (v) が計算可能となっている。

[7] D. Fukagawa, T. Akutsu, and A. Takasu, “Constant factor approximation of edit distance ofbounded height unordered trees”, Lecture Notes in
Computer Science, 5721:7–17, 2009.
[8] Y. Ishida, L. Zhao, H. Nagamochi, and T. Akutsu,“Improved algorithms for enumerating tree-likechemical graphs with given path frequency”,
Genome Informatics, 21:53–64, 2008.