(57)【特許請求の範囲】
【請求項１】
コンピュータによりラベル付き順序木の構造を持ったデータを分類するデータ処理方法であって、
前記コンピュータの内積計算手段が、処理対象の複数の前記ラベル付き順序木の内積を計算するステップと、
前記コンピュータの判断手段が、前記ラベル付き順序木の内積の計算結果に基づいて、当該ラベル付き順序木の分類を行うステップとを含み、
前記ラベル付き順序木の内積を計算するステップは、
前記複数のラベル付き順序木の個々のノードに順次着目して比較し、当該ノードを根に持ち、当該複数のラベル付き順序木に共通して現れる部分木の数を数えるステップと、
数え上げた全ての前記ノードに関する前記部分木の数を加算するステップとを含み、
前記部分木の数を数えるステップは、
比較した前記ノードのラベルが異なる場合に、当該ノードを根に持ち、当該複数のラベル付き順序木に共通して現れる部分木の数を０とするステップと、
比較した前記ノードのラベルが同一であって、共に前記ラベル付き順序木の終端のノードである場合に、当該ノードを根に持ち、当該複数のラベル付き順序木に共通して現れる部分木の数を１とするステップと、
比較した前記ノードのラベルが同一であって、少なくともいずれか一方のノードが前記ラベル付き順序木の終端でない場合に、当該ノードの子ノードのみを対象とし、当該ノードの両方に共通して現れる部分木の数を数えるステップと
を含むことを特徴とするデータ処理方法。
【請求項２】
前記部分木の数を数えるステップにおける、比較した前記ノードのラベルが同一であって、少なくともいずれか一方のノードが前記ラベル付き順序木の終端でない場合のステップにおいて、前記ノードの両方に共通して現れる部分木の数Ｓ（ｎｃ(ｎ1)，ｎｃ(ｎ2)）は、下記演算方法にて算出されることを特徴とする請求項１に記載のデータ処理方法。
演算方法
Ｓ(ｉ，ｊ)を、ノードｎ1の１番目からｉ番目までの子ノードと、ノードｎ2の１番目からｊ番目までの子ノードのみを考慮した場合の、ノードｎ1とノードｎ2の両方に共通して現れる部分木の数とする。そして、ｉ、ｊの初期値を０とし、ｉ、ｊの値を個別に１ずつ加算しながら、ｉ＝ｎｃ(ｎ1)、ｊ＝ｎｃ(ｎ2)となるまで、下記の計算を再帰的に繰り返す。ただし、ｎｃ(ｎ1)は、ノードｎ1における子ノードの個数、ｎｃ(ｎ2)は、ノードｎ2における子ノードの個数、ｃｈ(ｎ1，ｉ)は、ノードｎ1におけるｉ番目の子ノード、ｃｈ(ｎ2，ｊ)は、ノードｎ2におけるｊ番目の子ノードである。
・ｉまたはｊのいずれかが０のとき、
S(i, j) :=１
・ｉ、ｊのいずれも０でないとき、
S(i, j)
:=S(i-1, j) +S(i, j-1) -S(i-1, j-1) +S(i-1, j-1) ・C(ch(n1, i) ,ch(n2, j))
【請求項３】
ラベル付き順序木の構造を持ったデータを分類する情報処理システムにおいて、
処理対象の複数の前記ラベル付き順序木の内積を計算する内積計算部と、
前記内積計算部による前記ラベル付き順序木の内積の計算結果に基づいて、当該ラベル付き順序木の分類を行う判断部とを備え、
前記内積計算部は、前記複数のラベル付き順序木の個々のノードに順次着目して比較し、比較した前記ノードのラベルが異なる場合に、当該ノードを根に持ち、当該複数のラベル付き順序木に共通して現れる部分木の数を０とし、比較した前記ノードのラベルが同一であって、共に前記ラベル付き順序木の終端のノードである場合に、当該ノードを根に持ち、当該複数のラベル付き順序木に共通して現れる部分木の数を１とし、比較した前記ノードのラベルが同一であって、少なくともいずれか一方のノードが前記ラベル付き順序木の終端でない場合に、当該ノードの子ノードのみを対象とし、当該ノードの両方に共通して現れる部分木の数を数え、数え上げた全ての当該ノードに関する前記部分木の数を加算することで前記内積を計算することを特徴とする情報処理システム。
【請求項４】
前記内積計算部は、少なくともいずれか一方のノードが前記ラベル付き順序木の終端でない場合に、当該ノードの子ノードのみを対象とし、当該ノードの両方に共通して現れる部分木の数Ｓ（ｎｃ(ｎ1)，ｎｃ(ｎ2)）を、下記演算方法にて算出することを特徴とする請求項３に記載の情報処理システム。
演算方法
Ｓ(ｉ，ｊ)を、ノードｎ1の１番目からｉ番目までの子ノードと、ノードｎ2の１番目からｊ番目までの子ノードのみを考慮した場合の、ノードｎ1とノードｎ2の両方に共通して現れる部分木の数とする。そして、ｉ、ｊの初期値を０とし、ｉ、ｊの値を個別に１ずつ加算しながら、ｉ＝ｎｃ(ｎ1)、ｊ＝ｎｃ(ｎ2)となるまで、下記の計算を再帰的に繰り返す。ただし、ｎｃ(ｎ1)は、ノードｎ1における子ノードの個数、ｎｃ(ｎ2)は、ノードｎ2における子ノードの個数、ｃｈ(ｎ1，ｉ)は、ノードｎ1におけるｉ番目の子ノード、ｃｈ(ｎ2，ｊ)は、ノードｎ2におけるｊ番目の子ノードである。
・ｉまたはｊのいずれかが０のとき、
S(i, j) :=１
・ｉ、ｊのいずれも０でないとき、
S(i, j)
:=S(i-1, j) +S(i, j-1) -S(i-1, j-1) +S(i-1, j-1) ・C(ch(n1, i) ,ch(n2, j))
【請求項５】
前記ラベル付き順序木の構造を持った複数のデータを、ノードを指示するマークが指示されるべきノードに付された前記ラベル付き順序木である正例と、当該マークが指示されるべきでないノードに付された前記ラベル付き順序木である負例とに分類して格納したインスタンス格納部をさらに備え、
前記判断部は、前記インスタンス格納部に格納されている前記データに対する前記内積計算部の計算結果に基づいて、前記ラベル付き順序木に対する分類規則を学習することを特徴とする請求項３に記載の情報処理システム。
【請求項６】
前記判断部は、前記インスタンス格納部に格納されている前記データに基づく前記分類規則にしたがって、未知の前記ラベル付き順序木の構造を持つデータに対する分類処理を行った場合に、当該分類の結果を前記分類規則に反映させて次回以降の分類処理を行うことを特徴とする請求項５に記載の情報処理システム。
【請求項７】
コンピュータに、
処理対象の複数のラベル付き順序木の内積を計算する処理と、
前記ラベル付き順序木の内積の計算結果に基づいて、当該ラベル付き順序木の分類を行う処理とを実行させ、
前記ラベル付き順序木の内積を計算する処理では、前記複数のラベル付き順序木の個々のノードに順次着目して比較し、比較した前記ノードのラベルが異なる場合に、当該ノードを根に持ち、当該複数のラベル付き順序木に共通して現れる部分木の数を０とし、比較した前記ノードのラベルが同一であって、共に前記ラベル付き順序木の終端のノードである場合に、当該ノードを根に持ち、当該複数のラベル付き順序木に共通して現れる部分木の数を１とし、比較した前記ノードのラベルが同一であって、少なくともいずれか一方のノードが前記ラベル付き順序木の終端でない場合に、当該ノードの子ノードのみを対象とし、当該ノードの両方に共通して現れる部分木の数を数え、数え上げた全ての当該ノードに関する前記部分木の数を加算することで前記内積を計算する処理を実行させることを特徴とするプログラム。
【請求項８】
前記ラベル付き順序木の内積を計算する処理では、少なくともいずれか一方のノードが前記ラベル付き順序木の終端でない場合に、当該ノードの子ノードのみを対象とし、当該ノードの両方に共通して現れる部分木の数Ｓ（ｎｃ(ｎ1)，ｎｃ(ｎ2)）を、下記演算方法にて算出する処理を、前記コンピュータに実行させることを特徴とする請求項７に記載のプログラム。
演算方法
Ｓ(ｉ，ｊ)を、ノードｎ1の１番目からｉ番目までの子ノードと、ノードｎ2の１番目からｊ番目までの子ノードのみを考慮した場合の、ノードｎ1とノードｎ2の両方に共通して現れる部分木の数とする。そして、ｉ、ｊの初期値を０とし、ｉ、ｊの値を個別に１ずつ加算しながら、ｉ＝ｎｃ(ｎ1)、ｊ＝ｎｃ(ｎ2)となるまで、下記の計算を再帰的に繰り返す。ただし、ｎｃ(ｎ1)は、ノードｎ1における子ノードの個数、ｎｃ(ｎ2)は、ノードｎ2における子ノードの個数、ｃｈ(ｎ1，ｉ)は、ノードｎ1におけるｉ番目の子ノード、ｃｈ(ｎ2，ｊ)は、ノードｎ2におけるｊ番目の子ノードである。
・ｉまたはｊのいずれかが０のとき、
S(i, j) :=１
・ｉ、ｊのいずれも０でないとき、
S(i, j)
:=S(i-1, j) +S(i, j-1) -S(i-1, j-1) +S(i-1, j-1) ・C(ch(n1, i) ,ch(n2, j))
【請求項９】
コンピュータを、
処理対象の複数のラベル付き順序木の内積を計算する内積計算手段と、
前記内積計算手段による前記ラベル付き順序木の内積の計算結果に基づいて、当該ラベル付き順序木の分類を行う判断手段として機能させ、
前記内積計算手段の機能として、前記複数のラベル付き順序木の個々のノードに順次着目して比較し、比較した前記ノードのラベルが異なる場合に、当該ノードを根に持ち、当該複数のラベル付き順序木に共通して現れる部分木の数を０とし、比較した前記ノードのラベルが同一であって、共に前記ラベル付き順序木の終端のノードである場合に、当該ノードを根に持ち、当該複数のラベル付き順序木に共通して現れる部分木の数を１とし、比較した前記ノードのラベルが同一であって、少なくともいずれか一方のノードが前記ラベル付き順序木の終端でない場合に、当該ノードの子ノードのみを対象とし、当該ノードの両方に共通して現れる部分木の数を数え、数え上げた全ての当該ノードに関する前記部分木の数を加算することで前記内積を計算する処理を、前記コンピュータに実行させ、
前記判断手段の機能として、ノードを指示するマークが指示されるべきノードに付された前記ラベル付き順序木である正例と、当該マークが指示されるべきでないノードに付された前記ラベル付き順序木である負例とに予め分類された複数のデータに対する内積の計算結果から前記ラベル付き順序木に対する分類規則を、前記コンピュータに学習させることを特徴とするプログラム。
【請求項１０】
前記判断手段の機能として、前記分類規則にしたがって、未知の前記ラベル付き順序木の構造を持つデータに対する分類処理を行った場合に、当該分類の結果を前記分類規則に反映させて次回以降の分類処理を、前記コンピュータに実行させることを特徴とする請求項９に記載のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＸＭＬ（Extensible Markup Language）やＨＴＭＬ（Hypertext Markup Language）などの半構造データを分類する技術に関する。
【０００２】
【従来の技術】
近年、ＸＭＬやＨＴＭＬなどの半構造データが、各種のデータベースやデータ交換に用いるデータフォーマットとして注目されており、これら半構造データに対する各種のデータマイニング手法の開発が重要な課題となっている。
ここで、データマイニングの基本となる、構造を持った例（上記の半構造データ）を２つのクラスに分類する教師有り学習（分類学習）について考える。
【０００３】
ここで考える教師有り学習とは、２つのクラス（これを正のクラスと負のクラスとする）のどちらかに属するようなインスタンス（例）の集合が与えられたときに、属するクラスが未知の新たなインスタンスを正のクラスか負のクラスに正しく分類する分類器を学習することである。正のクラスに属するインスタンスを正例、負のクラスに属するインスタンスを負例と呼ぶ。
教師有り学習は、一般的に、１つのインスタンスを特徴空間の中の点（ベクトル）として表現する。すると、分類器を学習することは、この特徴空間の中の正例と負例の集合（点集合）をうまく（正しくは、まだ与えられていない未知の点を）分類するような規則（分割面の集合）を決定することである。
ベクトル表現が容易な対象、言い換えれば、人間が分類に必要な属性（特徴空間の基底）を決定することができるような場合には、各種学習アルゴリズムにその属性を渡せばよい。しかし、構造をもったインスタンス、すなわち配列、木、グラフ等で表されるようなインスタンスの場合、そのままではベクトルとして表現できない。多くの問題において、インスタンスのもつ部分的な構造を属性として定義するのが有効であるように思われる。例えば、化合物はグラフで表現できるが、その活性は（ある程度は）局所的な構造の積み重ねによって判別できると考えられる。
【０００４】
上記の半構造データは、ラベル付き順序木としてモデル化することができるが、このような構造を持ったインスタンスを扱う教師有り学習の戦略として、関係学習（Relational Learning）がある。関係学習においては、構成要素間の基本的な関係が定義され、これらが局所的な構造を構成する。属性として用いられる局所的な構造は学習の過程において逐次的に構成される。しかしながら、最適な仮説を探索する問題は一般にＮＰ困難となり、ヒューリスティク（発見的）な探索手法に頼らざるを得ない。なお、関係学習については、例えば下記文献１に詳細に記載されている。
文献１：古川、尾崎、植野「帰納論理プログラミング」共立出版、2001
【０００５】
また、構造を持ったインスタンスを扱う教師有り学習の他の戦略として、局所的パタンを発見し、頻出パタンを属性として定義して、通常の学習アルゴリズムに渡す手法がある。この方法は、クラス情報をもたないデータを利用できるという利点がある。しかし、パタン発見のステップは、大抵はやはりＮＰ困難になってしまう。
すなわち、これら２つの手法は、計算量的に処理が多項式時間で終了する保証がない。
【０００６】
そこで、木構造のような複雑な構造を持つインスタンスを扱う教師有り学習の現実的な手法として、サポートベクターマシンに代表されるようなカーネル法による方法がある。サポートベクターマシンについては、例えば、次の文献２に詳細に記載されている。
文献２：V. Vapnik. The Nature of Statistical Learning Theory. Springer Verlag, 1995.
【０００７】
カーネル法の重要な特徴として、カーネルを使ったインスタンスへのアクセスが挙げられる。通常の学習アルゴリズムが、インスタンスのベクトル表現に直接アクセスするのに対し、カーネル法はインスタンスにアクセスする際に常に２つのインスタンスのベクトル表現の内積を通じて行う。したがって、ベクトル表現の次元がいくら大きくとも、その内積の効率的な計算方法が与えられていれば、ベクトル表現の次元は学習や分類のプロセスの計算量に陽には現れない。この内積を与える関数はカーネルと呼ばれ、カーネル法は、このカーネルを用いることで効率的な学習を行うことができる。
【０００８】
【発明が解決しようとする課題】
上記のように、カーネル法を用いることにより、構造を持つインスタンスを扱う学習においても実現可能なシステムを構築することが可能となる。したがって、ＸＭＬやＨＴＭＬなどの半構造データに対するデータマイニングを実現するには、かかる構造を表現するラベル付き順序木に対するカーネルを得ることが課題となる。
【０００９】
従来、全ての可能な部分構造を属性として用いるようなカーネルがいくつか提案されているが、下記の文献３には、自然言語の文の構文解析木に対するカーネルが開示されている。
文献３：M. Collins and Nigel Duffy. Parsing with a Single Neuron : Convolution Kernel for Natural Language Problems. unpublished, 2000.
同文献に開示されている手法では、構文解析木のベクトル表現において、構文解析木に現れる各部分木の出現回数が各属性として用いられる。この場合、１つの構文解析木に現れる部分木の数は、木のサイズに対して指数的に増加するため、これらを陽に数え上げることは計算時間の面から問題がある。そこで、同文献の手法では、部分木の出現数を１つ１つ数え上げることなく、２つの木のベクトル表現を再帰的に計算する方法が提案されている。
【００１０】
しかし、文献３に記載された、カーネルで扱うことのできる木は、構文解析木のように、任意のノードの子ノード集合において、子ノードが互いに識別可能な場合に限られており、一般的な木であるラベル付き順序木には適用できない。
そこで、本発明は、ラベル付き順序木に対するカーネル法を提案し、これを用いた半構造データの分類を実現することを目的とする。
【００１１】
【課題を解決するための手段】
上記の目的を達成するため、本発明は、コンピュータを制御して、構造を持ったインスタンスを分類するための学習を行う、次のようなデータ処理方法として実現される。すなわち、このデータ処理方法は、部分構造を属性とするベクトル表現が可能な構造を持つ複数のインスタンスを入力して内積を計算し、計算結果をメモリに格納する第１のステップと、メモリに格納された計算結果に基づいてこのインスタンスに対する分類学習を進める第２のステップとを含み、第１のステップでは、所定の部分構造に下位の部分構造が内在する場合に、この下位の部分構造に関するマッチングの和を取ることを特徴とする。
【００１２】
より詳しくは、第１のステップにおいて、所定の前記部分構造に下位の部分構造が内在する場合に、当該下位の部分構造における所定の順序が保存されている対応関係において当該部分構造の固有の情報である順序に基づいて動的計画法を適用し、この下位の部分構造に関する全てのマッチングの和を取る。
【００１３】
また、本発明は、コンピュータを制御して、ラベル付き順序木の構造を持ったインスタンスを分類するための学習を行う、次のようなデータ処理方法としても実現される。すなわち、このデータ処理方法は、複数のインスタンスを入力して内積を計算し、計算結果をメモリに格納する第１のステップと、メモリに格納された計算結果に基づいてこのインスタンスに対する分類学習を進める第２のステップとを含み、第１のステップにおいて、木を構成する所定のノードがこの木における終端でない場合に、この所定のノードにおける子孫のノードに関するマッチングの和を取ることを特徴とする。
【００１４】
ここで、さらに好ましくは、第１のステップにおいて、所定のノードにおける子孫のノードに関するマッチングの和を取る際に、所定のノードにおけるラベルが変異していてもマッチしていると判断する。また、対応するノード間の相対位置が保存されていればマッチしていると判断する。
【００１５】
さらに本発明は、コンピュータを制御して、ラベル付き順序木における所望のノードを指示する、次のようなデータ処理方法として実現される。すなわち、このデータ処理方法は、メモリに格納された、ノードを指示するマークを指示されるべきノードに付されたラベル付き順序木である正例の構造とこのマークを指示されるべきでないノードに付されたラベル付き順序木である負例の構造とに基づいて、正例と負例とを分類するための分類規則を得てメモリに格納するステップと、処理対象であるラベル付き順序木に対し、所定のノードにマークを付し、メモリに格納されている分類規則に基づいて正負の分類を行うステップと、分類の結果に応じて、所定のノードにマークを付したラベル付き順序木を処理結果として出力するステップとを含むことを特徴とする。
【００１６】
ここで詳しくは、この分類規則を得てメモリに格納するステップは、複数のラベル付き順序木を入力して内積を計算し、計算結果をメモリに格納するステップと、メモリに格納された計算結果を用いてラベル付き順序木の分類規則を得るステップとを含むことを特徴とする。
【００１７】
さらにまた、本発明は、コンピュータを制御して、複数のラベル付き順序木の内積を計算する、次のようなデータ処理方法としても実現することができる。すなわち、このデータ処理方法は、ラベル付き順序木の終端のノードに対してマッチングを行い、結果をメモリに格納する第１のステップと、ラベル付き順序木の終端でないノードに対して、このノードの子孫のノードに関するマッチングの和を取ることにより、このノードのマッチングを行い、結果をメモリに格納する第２のステップと、メモリに格納された第１のステップにおけるマッチングの結果と第２のステップにおけるマッチングの結果とに基づいて、ラベル付き順序木の内積を計算する第３のステップとを含むことを特徴とする。
さらに詳細には、この第２のステップは、各ノードの順序が保存されている対応関係において動的計画法を適用し、上述した子孫のノードに関するマッチングの和を取る。
【００１８】
また、上記の目的を達成する他の本発明は、ラベル付き順序木の構造を持ったデータを分類する情報処理システムにおいて、前記データのインスタンスを前記木の構造に基づき正例と負例とに分けて格納したインスタンス格納部と、インスタンス格納部からインスタンスを読み出し、カーネル法によりインスタンスの分類及び分類のための学習を行う処理部とを備え、処理部は、複数のインスタンスの内積を計算する際に、木の非終端のノードにおける子孫のノードに関するマッチングの和を取る内積計算部を備えることを特徴とする。
【００１９】
ここで、この内積計算部は、より詳しくは、ノードの順序が保存されている対応関係において動的計画法を適用し、上述した子孫のノードに関するマッチングの和を取る。
【００２０】
さらに、本発明は、コンピュータを制御して上述したデータ処理方法の各ステップに相当する処理を実行させ、または上述した情報処理システムとしてコンピュータを機能させるプログラムとして実現することができる。このプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより提供することができる。
【００２１】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいて、この発明を詳細に説明する。
図１は、本実施の形態による情報処理システムを実現するのに好適なコンピュータ装置のハードウェア構成の例を模式的に示した図である。
図１に示すコンピュータ装置は、演算手段であるＣＰＵ（Central Processing Unit：中央処理装置）１０１と、Ｍ／Ｂ（マザーボード）チップセット１０２及びＣＰＵバスを介してＣＰＵ１０１に接続されたメインメモリ１０３と、同じくＭ／Ｂチップセット１０２及びＡＧＰ（Accelerated Graphics Port）を介してＣＰＵ１０１に接続されたビデオカード１０４と、ＰＣＩ（Peripheral Component Interconnect）バスを介してＭ／Ｂチップセット１０２に接続されたハードディスク１０５及びネットワークインターフェイス１０６と、さらにこのＰＣＩバスからブリッジ回路１０７及びＩＳＡ（Industry Standard Architecture）バスなどの低速なバスを介してＭ／Ｂチップセット１０２に接続されたフロッピーディスクドライブ１０８及びキーボード／マウス１０９とを備える。また、図１には記載していないが、このコンピュータ装置は、後述するようにＣＰＵ１０１の動作性能（動作クロック）を制御する手段として、クロック発信器及びそのコントローラを備える。
なお、図１は本実施の形態を実現するコンピュータ装置のハードウェア構成を例示するに過ぎず、本実施の形態を適用可能であれば、他の種々の構成を取ることができる。例えば、ビデオカード１０４を設ける代わりに、ビデオメモリのみを搭載し、ＣＰＵ１０１にてイメージデータを処理する構成としても良いし、音声による入出力を行うためのサウンド機構を設けたり、ＡＴＡ（AT Attachment）などのインターフェイスを介してＣＤ−ＲＯＭ（Compact Disc Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disc Read Only Memory）のドライブを設けたりしても良い。
【００２２】
図２は、本実施の形態による情報処理システムの構成を説明する図である。
図２を参照すると、本実施の形態の情報処理システムは、インスタンス（ラベル付き順序木）の分類及びその分類のための学習を行う処理部１０と、処理部１０を学習させるためのインスタンスを格納したインスタンス格納部２０とを備える。
図２において、処理部１０は、例えばプログラム制御されたＣＰＵ１０１にて実現される。ＣＰＵ１０を制御するプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより提供され、メインメモリ１０３に読み込まれる。また、インスタンス格納部２０は、メインメモリ１０３にて実現される。なお、メインメモリ１０３に格納されたプログラム及びインスタンスは、必要に応じてハードディスク１０５などの外部記憶装置に退避されることは言うまでもない。
【００２３】
本実施の形態において、処理部１０は、所定の２つのラベル付き順序木の内積を計算する内積計算部１１と、内積計算部１１によって算出される２つのラベル付き順序木の内積に基づいてラベル付き順序木の分類を行う判断部１２とを備える。なお、この内積計算部１１と判断部１２とは、上述したプログラム制御により処理部１０（ＣＰＵ１０１）の機能として実現される仮想的なソフトウェア・ブロックである。
内積計算部１１は、判断部１２からの要求に応じて、インスタンス格納部２０に格納されている所定の２つのインスタンスにおける内積を計算し、判断部１２へ渡す。この計算は、判断部１２がインスタンスに対する分類学習を進める過程で随時行われると共に、未分類のインスタンスを分類する際にも行われる。本実施の形態における内積計算部１１は、後で詳述する手法を用いて、ラベル付き順序木に対する効率的な内積の計算を実現している。
判断部１２は、サポートベクターマシンなどで提供される所定の学習アルゴリズムにより、インスタンス格納部２０に格納されているインスタンスに基づいてラベル付き順序木の分類規則を学習する。そして、所定の未知のラベル付き順序木を入力し、学習により得られた分類規則に基づいて当該ラベル付き順序木を分類し、分類結果を出力する。ここで、判断部１２は、学習しながら、内積計算部１１を介してさらに多くのインスタンスについての内積の計算結果を取得して行くことができる。これによって、より多くのインスタンスについての内積を取得するのに伴って学習が進み、分類の精度が向上する。なお、インスタンス格納部２０に格納される学習用のインスタンスの数が固定されており、膨大でない場合は、内積計算部１１にて予め全てのインスタンスについての内積を計算した後に判断部１２にて判断規則を決定するといった運用も可能である。
インスタンス格納部２０には、処理部１０の判断部１２が学習するためのラベル付き順序木のインスタンスが正例と負例とからなる２つのクラスに分類して格納してある。
【００２４】
本実施の形態では、処理部１０の判断部１２の学習に、サポートベクターマシンに代表されるようなカーネル法を用いる。
本実施の形態の対象であるラベル付き順序木に対する分類学習のための基本的な考え方は、ある程度の複雑さまでの考えられる部分構造を全て列挙し、その部分構造がインスタンス内に現れる回数を属性として用いることによって当該インスタンスをベクトル表現し、学習アルゴリズムに渡すというものである。
ここでカーネル法は、内部でのインスタンスへのアクセス方法として、当該インスタンスのベクトル表現に直接アクセスすることはせず、任意の２つのインスタンスにおける内積しか用いない。すなわち、２つの例のベクトル表現（高次元）をｏ1、ｏ2とすると、学習アルゴリズムによる学習・認識の過程において、内積＜ｏ1,ｏ2＞しか現れず、ｏ1、ｏ2が単独で現れることはない。よって、ｏ1、ｏ2が何次元のベクトルであっても（たとえ無限次元でも）その次元は陽には現れず、内積＜ｏ1,ｏ2＞さえ効率的に計算する方法があれば、陽に高次元空間において計算を行う必要がない。
さらに、汎化誤差の上界は次元に拠らない。すなわち、高次元空間での分類における一般的な問題であるcurse of dimensionalityを回避する。
【００２５】
本実施の形態では、ラベル付き順序木に対してこのカーネル法を適用する。木構造に対するカーネルは、木（インスタンス）における全ての可能な部分木を考え、それが当該木の中に出てくる回数を属性として用いる。
図３は、特に構文解析木について、木（図３（Ａ））と、その木の中の可能な部分木（図３（Ｂ））とを例示する図である。
このカーネルの要旨は以下のようになる。木に現れ得る部分構造（部分木）をsubtree1、subtree2、・・・とすると、２つの木Ｔ1、Ｔ2のベクトル表現は、次の数１式で表現される。
【数１】
0003873135.tif 000002
【００２６】
また、その内積＜Ｔ1，Ｔ2＞は、次の数２式で表される。
【数２】
0003873135.tif 000003
ここで、Ｎ1とＮ2とは、それぞれ木Ｔ1と木Ｔ2とが持つノードの集合である。Ｉsubtreei（ｎ1）は、部分木subtreeiが木Ｔ1において、ノードｎ1に根を持ちながら出現する回数を表すものとする。Ｃ（ｎ1，ｎ2）は、ノードｎ1とノードｎ2とを根に持ち、木Ｔ1及び木Ｔ2に共通して現れるような部分木の数とする。すなわち、Ｃ（ｎ1，ｎ2）＝ΣiＩsubtreei（ｎ1）・Ｉsubtreei（ｎ2）とする。すると、内積＜Ｔ1，Ｔ2＞は、サイズの大きいベクトル表現に直接アクセスすることなく、次のようにして計算することができる。
【００２７】
この計算では、次の３つの場合に分けて、動的計画法によって葉（木の終端）から再帰的に内積＜Ｔ1，Ｔ2＞を計算する。
（１）ｎ1とｎ2とで用いられた生成規則が異なるとき。
（２）ｎ1とｎ2とで用いられた生成規則が同一であり、ｎ1とｎ2とが共に前終端記号であるとき。
（３）ｎ1とｎ2とで用いられた生成規則が同一であり、ｎ1とｎ2の少なくとも一方が前終端記号でないとき。
【００２８】
ここで、部分構造（部分木）がさらに下位の部分構造を内在する場合（上記（３）の場合）について考える。
対象が構文解析木のように兄弟ノードとラベルを共有するようなノードが存在しない木であれば、同じ生成規則がｎ1とｎ2の両方の子ノードの集合を生成するため、子ノードの集合間の１対１対応は一意に決定することができ、ｎ1とｎ2の両方に共通して現れる部分木の数を再帰的に数え上げることができる。
しかし、本実施の形態の対象である、より一般的なラベル付き順序木は、このような子ノードの集合間の１対１対応は一意には決定できず、全ての可能な対応を考慮しなければならない。
ところが、ラベル付き順序木では子ノードの順序が決まっているため、子ノードの順序が保存されているような１対１対応のみを考慮すればよい。すなわち、ノードｎ1のｉ1番目の子ノードがノードｎ2のｉ2番目の子ノードに対応し、ノードｎ1のｊ1番目の子ノードがノードｎ2のｊ2番目の子ノードに対応するとき、ｉ1＜ｊ1かつｉ2＜ｊ2が成立しているような場合のみを考慮すればよい。この制約の下では、動的計画法によって全ての場合を考慮することができる効率的なアルゴリズムを設計できる。
【００２９】
図４、図５は、この内積＜Ｔ1，Ｔ2＞の計算手順を説明するフローチャートである。
初期動作として、処理部１０の内積計算部１１は、インスタンス格納部２０から２つのラベル付き順序木Ｔ1、Ｔ2を入力として受け取る。このラベル付き順序木Ｔ1、Ｔ2の各ノードには後行順（post order）で番号が振られているものとする。なお、以下の説明において、記号「:=」は代入操作を意味する。また、｜Ｎ1｜は木Ｔ1のノード数、｜Ｎ2｜は木Ｔ2のノード数である。
【００３０】
内積計算部１１は、ラベル付き順序木Ｔ1、Ｔ2を入力すると、まず上述した後行順の番号における先頭のノードｎ1、ｎ2を選び（ｎ1＝１、ｎ2＝１）、処理対象とする（ステップ４０１、４０２）。そして、ノードｎ1、ｎ2のラベルが異なるかどうか、すなわち上記（１）の場合に該当するかどうかを調べ（ステップ４０３）、ラベルが異なる、すなわち（１）の場合に該当するならば、
C(n1, n2) :=0
とする（ステップ４０４）。この結果は、メインメモリ１０３の所定の領域に保持される。
ノードｎ1、ｎ2のラベルが同一であり、（１）の場合に該当しない場合、次に内積計算部１１は、当該ノードｎ1、ｎ2はいずれもラベル付き順序木Ｔ1、Ｔ2における葉かどうか、すなわち上記（２）の場合に該当するかどうかを調べ（ステップ４０５）、どちらも葉である、すなわち（２）の場合に該当するならば、
C(n1, n2) :=1
とする（ステップ４０６）。この結果は、メインメモリ１０３の所定の領域に保持される。
【００３１】
ノードｎ1、ｎ2のうち、少なくとも一方が葉ではない（非終端点）、すなわち（２）にも該当しない場合は、ノードｎ1、ｎ2は上記（３）の場合に該当するので、図５に示すサブルーチンにより、Ｃ（ｎ1，ｎ2）を計算する（ステップ４０７）。
ここで、図５を参照し、（３）の場合の処理について説明する。以下の説明において、Ｓ(ｉ，ｊ)は、ノードｎ1の１番目からｉ番目までの子ノードと、ノードｎ2の１番目からｊ番目までの子ノードのみを考慮した場合の、ノードｎ1とノードｎ2の両方に共通して現れる部分木の数とする。また、nc(n1)は、ノードｎ1における子ノードの個数、ch(n1,i)は、ノードｎ1におけるｉ番目の子ノードとする。
【００３２】
内積計算部１１は、まず、パラメータｉ、ｊを初期化（ｉ＝０、ｊ＝０）する（ステップ５０１、５０２）。そして、ｉ＝０またはｊ＝０かどうかを調べ（ステップ５０３）、ｉまたはｊのいずれかが０であれば、
S(i, j) :=1
とする（ステップ５０４）。この結果は、メインメモリ１０３の所定の領域に保持される。
一方、ｉ、ｊのいずれも０でない場合は、
S(i, j) :=S(i-1, j) +S(i, j-1) -S(i-1, j-1) +S(i-1, j-1) ・C(ch(n1, i) ,ch(n2, j))
とする（ステップ５０５）。この結果は、メインメモリ１０３の所定の領域に保持される。
【００３３】
ステップ５０４またはステップ５０５でＳ(ｉ，ｊ)を計算した後、内積計算部１１は、パラメータｊの値を調べ、ｊ＝ｎｃ(ｎ2)でなければ、ｊの値を１加算してステップ５０３へ戻る（ステップ５０６、５０７）。一方、ｊ＝ｎｃ(ｎ2)であれば、次にパラメータｉの値を調べ、ｉ＝ｎｃ(ｎ1)でなければ、ｉの値を１加算してステップ５０２へ戻る（ステップ５０８、５０９）。
以上の処理を再帰的に繰り返すことにより、ノードｎ1、ｎ2における各子ノードの全ての組合せに対して上記の処理が行われる。
ステップ５０８で、ｉ＝ｎｃ(ｎ1)であれば、未処理の子ノードの組合せは無いので、内積計算部１１は、メインメモリ１０３等に格納されているステップ５０４、５０５の結果を用い、
C(n1, n2) :=S(nc(n1), nc(n2))
として、図４の動作へ戻る（ステップ５１０）。なお、この結果は、メインメモリ１０３の所定の領域に保持される。
【００３４】
ステップ４０４、４０５または図５のサブルーチン（ステップ４０７）を経てＣ（ｎ1，ｎ2）が決まったならば、次に内積計算部１１は、ノードｎ2のラベルを調べ、ｎ2＝｜Ｎ2｜でなければ、ｎ2の値を１加算してステップ４０３へ戻る（ステップ４０８、４０９）。一方、ｎ2＝｜Ｎ2｜であれば、次にノードｎ1のラベルを調べ、ｎ1＝｜Ｎ1｜でなければ、ｉの値を１加算してステップ４０２へ戻る（ステップ４１０、４１１）。
以上の処理を再帰的に繰り返すことにより、ラベル付き順序木Ｔ1、Ｔ2における各ノードの全ての組合せに対して上記の処理が行われる。
ステップ４１０で、ｎ1＝｜Ｎ1｜であれば、未処理のノードｎ1、ｎ2の組合せは無いので、内積計算部１１は、メインメモリ１０３等に格納されているステップ４０４、４０６、４０７（５１０））の結果を用い、Ｃ（ｎ1，ｎ2）を、ｎ1＝１、・・・、｜Ｎ1｜とｎ2＝１、・・・、｜Ｎ2｜について全て足し合わせ、結果（これが内積＜Ｔ1，Ｔ2＞の計算結果である）を出力する（ステップ４１２）。出力された内積＜Ｔ1，Ｔ2＞の計算結果は、一時的にメインメモリ１０３の所定の領域に保持され、判断部１２に渡される。判断部１２は、メインメモリ１０３から読み込んだ、この内積＜Ｔ1，Ｔ2＞の計算結果に基づいて、与えられたラベル付き順序木の分類規則を学習する。この分類規則は、例えばメインメモリ１０３に格納され、未分類のラベル付き順序木を分類する際に使用される。
図６は、上述した２つのラベル付き順序木Ｔ1、Ｔ2のカーネルを計算するアルゴリズムを示す図である。
【００３５】
次に、上述したカーネルの計算における計算量を解析する。任意のＣ(ｎ1，ｎ2)の計算量は、ｎ1とｎ2とにおける子ノードの数の積に比例する。次の数３式の計算によって、ラベル付き順序木カーネルの計算量は、２つの木のサイズの積に比例することがわかる。
【数３】
0003873135.tif 000004
【００３６】
以上のようにして、ラベル付き順序木に対するカーネルにより処理部１０の判断部１２の学習が可能となった。これにより、正例のラベル付き順序木の集合と負例のラベル付き順序木の集合とを与えられると、それらを部分的な構造を基準として分類するような分類器としての処理部１０を多項式時間で構成することができる。
これ以後、処理部１０に未知のラベル付き順序木が入力されると、処理部１０は、内積計算部１１にて当該未知のラベル付き順序木と学習に用いられた適当なラベル付き順序木との内積を計算し、メインメモリ１０３等に保持されている分類規則と内積の計算結果とに基づき、判断部１２にて当該未知のラベル付き順序木を分類する。
順序木をカバーするということは、大抵の木状の関係によって記述できる対象をカバーできるということになり、ＸＭＬやＨＴＭＬで表現される半構造データなどが対象に含まれる。また今後、ＸＭＬ等で記述される対象は増えていくと思われ、対象の性質をＸＭＬでうまく表現できれば、これをインスタンスとする分類が可能になる。
【００３７】
次に、上述した処理部１０によるカーネル法を拡張した２つの変形例について説明する。
〔第１の変形例〕
上述したカーネル法では、木構造中に所定の部分木が出現したかどうかの判定が厳密に行われていたが、第１の変形例では、その判定をいくつかのラベルの変異は許すように拡張する。
図７は、第１の変形例における部分木の対応関係を説明する図である。
図７において、subtreeiが木Ｔの所定の位置に出現するかどうかを判定するとき、網掛けのあるノードはラベルに変異のあったノードであると考える。そして、木Ｔのなかでsubtreeiが出現した回数を数えるとき、その回数にラベル変異の分のペナルティを与える（すなわち回数を減らして数える）。
【００３８】
Σをラベルの集合とし、ｆ：Σ×Σ→［０，１］をラベル変異のスコア関数とする。∀ｌ1,ｌ2∈Σに対し、ｆ(ｌ2｜ｌ1)が小さいことは、ｌ1からｌ2への変異に与えるペナルティが大きいことを示す。ｆ(Ａ｜Ａ)＝１、ｆ(Ａ｜Ｄ)＝０：５、ｆ(Ｃ｜Ｂ)＝０：８、ｆ(Ｃ｜Ｃ)＝１とすると、スコアはそれらの積によって、ｆ(Ａ｜Ａ)ｆ(Ａ｜Ｄ)ｆ(Ｃ｜Ｂ)ｆ(Ｃ｜Ｃ)＝０：４というように定義される。木Ｔのベクトル表現におけるｉ番目の要素は、木Ｔの全てのノードのsubtreeiにおける構造がマッチする、全ての位置でのスコアの和と定義する。
【００３９】
図８は、第１の変形例による、ラベルの変異を許す場合のカーネルを計算するアルゴリズムを示す図である。
図８を参照すると、図６のアルゴリズムと比べて、下線を引いた
C(n1, n2) := Sim(n1, n2)
C(n1, n2) := Sim(n1, n2)・S(nc(n1), nc(n2))の部分が変わっている。なお、Ｓｉｍ(ｎ1, ｎ2)は、次の数４式で表される値である。
【数４】
0003873135.tif 000005
全てのラベルについて和を取るのは、全ての起こりうる変異を考慮するためである。
【００４０】
〔第２の変形例〕
第２の変形例では、部分木の出現判定をさらに緩和し、部分木が、ノード間の相対位置が保たれている状態で木の中に埋め込まれているのならば出現したとみなす。すなわち、構造の伸張を許すようにする。
図９は、第２の変形例における部分木の対応関係を説明する図である。
図９において、subtreesiは、木Ｔにおける網掛けのあるノードの位置に図に示したように埋め込まれた状態で出現する。すなわち、subtreeiの中で、あるノードが他のノードの子孫であるならば、その関係は木Ｔに埋め込まれた状態でも保たれていなければならない。同様に、subtreeiの中で、あるノードが他のノードより左にあるのならば、その関係は木Ｔに埋め込まれた状態でも保たれていなければならない。
【００４１】
図１０は、第２の変形例による、構造の伸張を許す場合のカーネルを計算するアルゴリズムを示す図である。
このアルゴリズムでは、次の数５式のように定義される新しい変数Ｃa(ｎ1，ｎ2)を導入する。
【数５】
0003873135.tif 000006
ここで、Ｎniは、ｎiとその全ての子孫を合わせたノードの集合であるとする。所定のノードを根に持つ全ての部分木は、伸張を許さない場合、当該所定のノードの子ノードのそれぞれを根に持つような他の部分木を組み合わせて、そのノードを上に付けることで構成されるのに対し、伸張を許す場合には、当該所定のノードの子孫ノードのそれぞれを根に持つような部分木を組み合わせて、そのノードを上に付けることで構成される。
それ故、次の図６式に示す再帰式によってＣaも再帰的に計算する必要がある。
【数６】
0003873135.tif 000007
この再帰式によって、部分木の出現判定に構造の伸張を許す場合にも、同じ計算量でカーネルを計算することができる。
【００４２】
図１１は、本実施の形態を用いた学習機械の構成例を示す図である。
図１１を参照すると、この学習機械１１１０は、ラベル付き順序木のインスタンスの集合を正例と負例とに分けて格納した例集合データベース１１２０と、分類対象であるラベル付き順序木の集合を格納した分類対象データベース１１３０とに接続されている。ここで、学習機械１１１０は本実施の形態の処理部１０における判断部１２に相当し、例集合データベース１１２０はインスタンス格納部２０に相当する。
学習機械１１１０は、ラベル付き順序木の分類を学習するための分類学習アルゴリズム１１１１を備え、学習を行った結果として分類器１１１２を構成する。この分類学習アルゴリズム１１１１により、学習機械１１１０は、本実施の形態による内積計算部１１が持つカーネルを通じて例集合データベース１１２０にアクセスして学習し、学習により得られた分類規則を持つ分類器１１１２を構成（出力）する。
生成された分類器１１１２は、内積計算部１１が持つカーネルを通じて分類対象データベース１１３０と例集合データベース１１２０とにアクセスする。そして、分類対象データベース１１３０に格納されている正負が未知の（未分類の）インスタンスを分類し、分類結果を出力する。
【００４３】
本実施の形態の適用例として、上記のような学習機械により、インターネット上のウェブページをそのレイアウトに基づいて分類する分類器を構成することができる。
ウェブページを自動的に分類することは、ウェブページのフィルタリングやカテゴリ分けなどの基礎となる重要な技術である。従来、ウェブページの分類は、文章内に出現する単語やページ間のリンクに基づいて行われてきた。これに対し、本実施の形態では、ウェブページを構成するＨＴＭＬ文書の構造に基づく分類が可能である。そして、ＨＴＭＬ文書の構造は、当該ウェブページのレイアウトに反映されるので、本実施の形態により、単語レベル等では区別できない、ページレイアウトに基づく分類が可能となる。
【００４４】
また、本実施の形態の他の適用例として、データマイニングの基本的技術の１つであるクラス分類を、ＸＭＬのような半構造データで表現されたオブジェクトを持つ半構造データベースに対して行うことができる。
従来、主要なデータベースであるリレーショナルデータベースであったが、ＸＭＬの普及により、今後はリレーショナルなデータで表現されたオブジェクトだけではなく、ＸＭＬのような半構造データで表現されたオブジェクトをデータとして持つデータベースが増加していくと考えられる。本実施の形態によれば、このようなデータベースに対して、オブジェクトであるデータの構造に基づいて分類することが可能であるため、この種のデータベースに対する検索その他の処理を行うためのツールとして極めて有効である。
【００４５】
次に、上述したラベル付き順序木の分類手法の応用技術について説明する。
ＸＭＬやＨＴＭＬなどの半構造データから所望の情報を抽出するために、当該半構造データを表現するラベル付き順序木の特定のノードを指示する問題を解く必要のある場合がある。
このような場合、この問題を、正しい場所（ノード）にマークの付いた木（正例）と正しくない場所にマークの付いた木（負例）とを分類する問題に変換することにより、上述した本実施の形態による情報処理システムの学習及び分類手法を適用することができる。
すなわち、マーク済みの木のインスタンスを用いて、正しい場所にマークの付いた木の構造を学習し、分類器を構成する。そして、マークの付されていない木を分類対象として、適当な手順でマーク付けを行い、マークを付けた当該木が当該分類器により正に分類されたならば、該当個所にマークを付けた当該木をノード指示の結果として出力する。
【００４６】
図１２は、本実施の形態を用いてラベル付き順序木の特定のノードを指示するノード指示器を生成する学習装置の構成例を示す図である。
図１２において、学習機械１２１０は、ラベル付き順序木のインスタンスの集合を正例と負例とに分けて格納した例集合データベース１２２０と、ノード指示の対象である（マークの付されていない）ラベル付き順序木のインスタンスの集合を格納したノード指示対象データベース１２３０とに接続されている。
学習機械１２１０は、本実施の形態の処理部１０における判断部１２に相当し、ノード指示のためのラベル付き順序木の分類を学習するノード指示学習アルゴリズム１２１１を備え、学習を行った結果としてノード指示器１２１２を構成する。構成されたノード指示器１２１２は、未分類のラベル付き順序木を分類する分類器としての機能を備え、当該ラベル付き順序木の正しい場所にマークを付け、ノード指示の結果として出力する。
【００４７】
ここで、このシステムによるノード指示の手法について、さらに説明する。本システムでは、まず未処理の、すなわちノード指示のマークが付けられていないラベル付き順序木を対象として、当該ラベル付き順序木の所定のノードに仮にマークを付けたインスタンスを生成する。このインスタンスは、当該ラベル付き順序木の各ノードに対して、それぞれマークを付けたものが生成される（すなわち、ノードの数分のインスタンスが生成される）。そして、ノード指示器１２１２の分類機能により、当該インスタンスの正負の分類を行う。この分類により正と判断されたインスタンスが正しい場所にマークされているインスタンスであるので、かかる分類結果を反映させて、ラベル付き順序木の該当個所にノード指示のマークを付する。なお、正と判断されるインスタンスが複数ある場合は、指示すべきノードが複数存在することを意味するので、これらを全てラベル付き順序木に反映させる。
【００４８】
図１３、図１２に示す学習機械１２１０の学習段階の動作を説明するフローチャートである。
図１３に示すように、初期動作として、正しい場所にマークされたラベル付き順序木の集合Ｔpが例集合データベース１２２０に与えられると（ステップ１３０１）、プログラム制御されたＣＰＵ１０１にて実現される所定の処理手段により、この集合Ｔpを構成するラベル付き順序木に基づいて正しくない場所にマークの付いたラベル付き順序木の集合Ｔnが生成される（ステップ１３０２）。これは、集合Ｔpのラベル付き順序木におけるマークの位置を変更するなどにより生成される。
そして、プログラム制御されたＣＰＵ１０１にて実現される所定の処理手段により、正しいマークの付いたラベル付き順序木の集合Ｔpから本システムで用いる様式の正例の集合Ｅpが生成され、正しくないマークの付いたラベル付き順序木の集合Ｔnから本システムで用いる様式の負例の集合Ｅnが生成され、例集合データベース１２２０に格納される（ステップ１３０３）。ここで、正例の集合Ｅp及び負例の集合Ｅnに含まれる各インスタンスは、ラベル付き順序木の集合Ｔp、Ｔnに含まれる各ラベル付き順序木において、マークの付いたノードとその親ノードとの間にマークを示す特別なノードを挿入することにより生成される（図１４参照）。
学習機械１２１０は、ノード指示学習アルゴリズム１２１１により、本実施の形態による内積計算部１１が持つカーネルを通じて例集合データベース１２２０にアクセスして学習し、学習により得られた分類規則を持つ分類器を構成し、この分類器を機能として持つノード指示器１２１２を構成（出力）する（ステップ１３０４）。分類規則はメインメモリ１０３等に保持され、ノード指示器１２１２による処理において用いられる。
【００４９】
図１５は、図１３の手順で構成されたノード指示器１２１２による動作を説明するフローチャートである。
図１５に示すように、初期動作として、処理対象となるマークの付されていないラベル付き順序木の集合Ｔuがノード指示対象データベース１２３０に格納されると（ステップ１５０１）、プログラム制御されたＣＰＵ１０１にて実現される所定の処理手段により、集合Ｔuに含まれる各ラベル付き順序木を対象として、所定のノードに仮にマークを付けたインスタンスが生成される（ステップ１５０２）。
ノード指示器１２１２は、集合Ｔuに含まれる各ラベル付き順序木に対して、以下の処理を実行する。まず、内積計算部１１が持つカーネルを通じてノード指示対象データベース１２３０と例集合データベース１２２０とにアクセスし、メインメモリ１０３等に保持されている分類規則に基づいて、ステップ１５０２で生成された各インスタンスの正負を分類する（ステップ１５０３、１５０４）。そして、正に分類された全てのインスタンスにおけるマークの位置を反映させて、当該インスタンスに対応するラベル付き順序木の該当ノードにノード指示のマークを付し、出力する（ステップ１５０５）。ステップ１５０３〜１５０５の処理が、集合Ｔuに含まれる全てのラベル付き順序木に対して行われたならば、処理を終了する（ステップ１５０６）。
【００５０】
以上のようにして、本実施の形態を適用したラベル付き順序木のノード指示器１２１２によれば、ラベル付き順序木を構成する各ノードの周辺構造に基づいてノード指示のためのマークを付するノードが決定される。したがって、従来行われていた根からのパスを学習する方法や関係学習を用いた方法と異なり、効率的であると共に、理論的によい汎化性能が得られる。
【００５１】
【発明の効果】
以上説明したように、本発明によれば、ラベル付き順序木に対するカーネル法により、半構造データを分類することが可能となる。
【図面の簡単な説明】
【図１】  本実施の形態による情報処理システムを実現するのに好適なコンピュータ装置のハードウェア構成の例を模式的に示した図である。
【図２】  本実施の形態による情報処理システムの構成を示す図である。
【図３】  構文解析木とその部分木との関係を例示する図である。
【図４】  本実施の形態によるラベル付き順序木のベクトル表現の内積の計算手順を説明するフローチャートである。
【図５】  図４のステップ４０７のサブルーチンにおける処理を説明するフローチャートである。
【図６】  本実施の形態による２つのラベル付き順序木のカーネルを計算するアルゴリズムを示す図である。
【図７】  本実施の形態を拡張した第１の変形例における部分木の対応関係を説明する図である。
【図８】  第１の変形例による、ラベルの変異を許す場合のカーネルを計算するアルゴリズムを示す図である。
【図９】  本実施の形態を拡張した第２の変形例における部分木の対応関係を説明する図である。
【図１０】  第２の変形例による、構造の伸張を許す場合のカーネルを計算するアルゴリズムを示す図である。
【図１１】  本実施の形態を用いた学習機械の構成例を示す図である。
【図１２】  本実施の形態を用いてラベル付き順序木の特定のノードを指示するノード指示器を生成する学習装置の構成例を示す図である。
【図１３】  図１２に示す学習機械の学習段階の動作を説明するフローチャートである。
【図１４】  ノード指示のマークが付されたラベル付き順序木から学習及び分類に用いるインスタンスを生成する手法を説明する図である。
【図１５】  図１３の手順で構成されたノード指示器による動作を説明するフローチャートである。
【符号の説明】
１０…処理部、１１…内積計算部、１２…判断部、２０…インスタンス格納部、１０１…ＣＰＵ、１０３…メインメモリ、１１１０、１２１０…学習機械、１１１１…分類学習アルゴリズム、１１１２…分類器、１１２０、１２２０…例集合データベース、１１３０…分類対象データベース、１２１１…ノード指示学習アルゴリズム、１２１２…ノード指示器、１２３０…ノード指示対象データベース
【図１】
0003873135.tif 000008
【図２】
0003873135.tif 000009
【図３】
0003873135.tif 000010
【図４】
0003873135.tif 000011
【図５】
0003873135.tif 000012
【図６】
0003873135.tif 000013
【図７】
0003873135.tif 000014
【図８】
0003873135.tif 000015
【図９】
0003873135.tif 000016
【図１０】
0003873135.tif 000017
【図１１】
0003873135.tif 000018
【図１２】
0003873135.tif 000019
【図１３】
0003873135.tif 000020
【図１４】
0003873135.tif 000021
【図１５】
0003873135.tif 000022