(57)【要約】【課題】構造のサイズを気にせずに全ての可能な特徴から必要な特徴（部分構造）を自動的に選択し、必要な特徴のみを使ったカーネル計算を可能とする。【解決手段】離散オブジェクトＡ，Ｂから部分構造ｕを抽出する部分構造抽出部１２と、抽出された部分構造ｕに関してカイ二乗値を算出するカイ二乗算出部１３と、算出されたカイ二乗値と閾値とを比較することによって、離散オブジェクトＡ，Ｂに関して統計量に基づく有効な特徴を選択する特徴選択部１４と、特徴選択部１４での判定結果を参照し、有効な特徴のみが最終的なカーネル値に加算されるように、離散オブジェクトＡ，Ｂ間の類似度を表すカーネル値を再帰計算によって算出するカーネル計算部１５と、を設ける。【選択図】        図１
2005222365.tif 000002
【特許請求の範囲】
【請求項１】
離散オブジェクトを入力として離散カーネル値を計算する離散カーネル関数の計算方法であって、
抽出手段が入力された離散オブジェクトから部分構造を抽出する抽出段階と、
前記部分構造に対して特徴選択手段が統計量に基づく有効性を判定する特徴選択段階と、
有効であると判定された部分構造のみが最終的なカーネル値に加算されるように、カーネル計算手段がカーネル値を計算するカーネル計算段階と、
を有する、素性選択機能付き離散カーネル関数の計算方法。
【請求項２】
前記特徴選択段階は、前記部分構造に関する統計量を計算する段階と、前記統計量と所定の閾値とを比較する段階と、前記統計量が前記閾値以上である場合に前記部分構造を有効であると判定する段階と、を有する、請求項１に記載の素性選択機能付き離散カーネル関数の計算方法。
【請求項３】
前記カーネル計算段階において、部分構造ｕ，ｕｖの統計量がともに前記閾値を上回る場合は素性として選択し、ｕｖのみが前記閾値を上回る場合は途中計算値を記憶手段に格納し、ｕ，ｕｖともに閾値を超えない場合は素性として不採用とする、請求項２に記載の素性選択機能付き離散カーネル関数の計算方法。
【請求項４】
離散オブジェクトを入力として離散カーネル値を計算する離散カーネル関数の計算装置であって、
入力された離散オブジェクトから部分構造を抽出する抽出手段と、
前記部分構造に対して統計量に基づく有効性を判定する特徴選択手段と、
有効であると判定された部分構造のみが最終的なカーネル値に加算されるように、カーネル値を再帰的に計算するカーネル計算手段と、
前記カーネル値の計算過程の途中経過を保持する記憶手段と、
を有する、素性選択機能付き離散カーネル関数の計算装置。
【請求項５】
前記特徴選択手段は、前記部分構造に関する統計量を計算し、前記統計量と所定の閾値とを比較し、前記統計量が前記閾値以上である場合に前記部分構造を有効であると判定する、請求項４に記載の素性選択機能付き離散カーネル関数の計算装置。
【請求項６】
前記カーネル計算手段は、部分構造ｕ，ｕｖの統計量がともに前記閾値を上回る場合は素性として選択し、ｕｖのみが前記閾値を上回る場合は途中計算値を前記記憶手段に格納し、ｕ，ｕｖともに閾値を超えない場合は素性として不採用とする、請求項５に記載の素性選択機能付き離散カーネル関数の計算装置。
【請求項７】
コンピュータを、
入力された離散オブジェクトから部分構造を抽出する抽出手段、
前記部分構造に対して統計量に基づく有効性を判定する特徴選択手段、
有効であると判定された部分構造のみが最終的なカーネル値に加算されるように、計算過程の途中経過を記憶手段に保持しながらカーネル値を再帰的に計算するカーネル計算手段、
として機能させるプログラム。
【請求項８】
コンピュータが読み取り可能な記録媒体であって、請求項７に記載のプログラムを格納した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータを用いて自然言語処理タスクなどを実行する際に用いられる離散カーネル関数を計算する技術に関し、特に、離散カーネル関数を高速で計算することができる素性選択機能付き離散カーネル関数の計算方法及び装置に関する。
【背景技術】
【０００２】
カーネル関数は、一般に、機械学習やデータ間の類似度などの算定などの分野において広く使用されている関数である。
【０００３】
近年、ストリングカーネル(String Kernel)（非特許文献１）やツリーカーネル(Tree Kernel)（非特許文献２）など、離散構造を扱うことが可能なカーネル関数が提案され、いくつかの自然言語処理タスクにおいてその有効性が示されている。
【０００４】
ストリングカーネルやツリーカーネルは、より一般的に、コンボリューションカーネル(Convolution Kernel)（非特許文献３）と呼ばれる離散カーネル関数の一種として定義される。このコンボリューションカーネルは、比較対象となる入力オブジェクトがいくつかの部分構造によって構成されているとき、その部分構造同士に定義された部分カーネルの総和を比較対象オブジェクトのカーネルの値と定義している。例えば、ストリングカーネルでは、入力オブジェクトが記号列（例：ａｂｃｄ）の場合に用いられ、その部分構造は入力記号列中のギャップを許した部分記号列（例：ａ，ｂ，ｃ，ｄ，ａｂ，ａｃ，ａｄ，ｂｃ，ｂｄ，ｃｄ，ａｂｃ，ａｂｄ，ａｃｄ，ｂｃｄ，ａｂｃｄ）であると考える。このとき、部分カーネルを部分構造間の重み付き一致数とし、その総和を全体のカーネルの値と定義している。
【０００５】
このコンボリューションカーネルの枠組を用いることにより、テキストを数値ベクトルに変換することなくそのテキストが備える離散構造を自然な形で扱うことができると同時に、これまで明示的に計算することが計算量的に困難であったテキストの構造的な情報を反映した効率的な計算が可能になる。
【０００６】
また、カーネル関数は、機械学習の分野で発達して来たが、カーネルの値は、オブジェクト間の類似度としても定義できることから、クラスタリングや類似性評価方法としても使用することができる。
【０００７】
しかしながら、コンボリューションカーネルの定義では、カーネルの計算に使用する入力オブジェクトの構造のサイズが大きくなると、事実上の素性数は指数関数的に増加するため、データスパースネス（データ希薄性）の問題が起こり、効率的な学習ができなくなる可能性が高くなることが経験的に知られている。
【０００８】
以下に、ストリングカーネルを用いる場合を例に挙げて、実際にどのような現象が起こるかを述べる。
【０００９】
ある入力記号列ｘ，ｙ（ｘ≠ｙ）があるとき、扱う構造のサイズを大きくすると、自分自身に対するカーネルの値Ｋ（ｘ，ｘ），Ｋ（ｙ，ｙ）は非常に大きくなるが、ｘ，ｙ間のカーネルの値Ｋ（ｘ，ｙ）は、Ｋ（ｘ，ｘ），Ｋ（ｙ，ｙ）と比較すると、それほど大きくならないことが多い。これは、鋭いピークを持ったガウシアン（ガウス型分布）と同様で、分布の中心から少しでも外れた場合の値が０に等しくなることと同じ現象である。つまりこれを、ガウシアンカーネルＫ（ｘ，ｙ）＝ｅｘｐ（−‖ｘ−ｙ‖2／２σ2）からの類推で考えると、分散σ2の非常に小さい大きなピークを持ったカーネルとなっているといえる。
【００１０】
テキストのような本来スパースな（希薄な）実データでは、さらにこの傾向は顕著となり、サイズの大きい構造を扱う場合には、自分自身に対するカーネルの値以外はほぼ０と等しくなるといったことはしばしば起こる。つまり、そのようなカーネルを用いる場合には、学習データに出現したサンプルとほぼ同じか、あるいは、全く同じデータに対してしか、信頼性のある学習を行うことができない。
【００１１】
このように、コンボリューションカーネルを使用する際には、扱う構造のサイズを考慮する必要がある。
【００１２】
そこで、これまで提案されているものは、主に、サイズに基づいて構造の平滑化を行おうとする方法である。ストリングカーネルでは、その定義自体が既にこの問題に対応するように作成されている。すなわち、ストリングカーネルにおいて部分構造のサイズｎ以下の部分構造しか扱わない枠組が、これにあたる。つまり、全部分構造中において、サイズに対する閾値により素性選択を行なっていることに等しい。ツリーカーネルの場合でも、例えば、木の階層数をパラメタとし、その階層数以上を扱わないようにする方法（非特許文献２）や、大きい部分木にはペナルティを与える方法（非特許文献４）などの方法が採用されている。
【非特許文献１】H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini, and C. Watkins, "Text Classification Using String Kernel," Journal of Machine Learning Research, 2:419-444, 2002
【非特許文献２】M. Collins and N. Duffy, "Convolution Kernels for Natural Language," Proc. of Neural Information Processing Systems (NIPS '2001), 2001
【非特許文献３】D. Haussler, "Convolution Kernels on Discrete Structures," Technical Report UCS-CRL-99-10, UC Santa Cruz, 1999
【非特許文献４】M. Collins and N. Duffy, "New ranking Algorithms for Parsing and Tagging: Kernels over Discrete Structures and the Voted Perceptron," Proc. of ACL '2002), pp. 263-270, 2002
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上述したように従来の方法では、サイズが大きい構造を扱う際の信頼性を高めるために、構造のサイズに依存して閾値を設ける方法が主流である。しかし、この素性選択基準は、仮に閾値ｎ以上のサイズの部分構造の中に非常に有効な特徴が存在しても、それらはカーネルの値には反映されないという問題点を含んでいる。また、そのサイズの大きい部分構造をカーネルの値に反映させるために閾値の値を大きくしたとしても、データスパースネスの問題の影響で、逆に性能を劣化させることがほとんどである。このように、サイズに基づく素性選択手法は、適用は簡単であるが、仮にサイズの大きい部分構造の中に有効な特徴が存在することがわかっていても、サイズの閾値ｎを大きくすることができないという問題がある。
【００１４】
以上、離散カーネル関数を自然言語処理における「素性選択」に応用する例を説明したが、カーネル関数は、自然言語処理のみならず、類似度算出やクラスタリングなどに応用することができ、自然言語処理におけるカーネル関数を用いた「素性選択」は、より一般的には、カーネル関数による類似度算出などにおける「特徴」の選択と考えることができる。上述した自然言語処理における「素性選択」において構造のサイズが大きな場合に生じる問題点は、カーネル関数によって「特徴」を選択する場合に共通する問題点である。
【００１５】
したがって本発明の目的は、構造のサイズを気にせずに全ての可能な特徴から必要な特徴を自動的に選択し、必要な特徴のみを使ったカーネル計算が可能となるカーネル計算方法及び装置を提供することにある。
【課題を解決するための手段】
【００１６】
本発明では、部分構造のサイズに依存しない特徴選択手法として、コンボリューションカーネルが計算する全ての部分構造から、各部分構造の統計量に基づいて分類に有効であると判定された部分構造のみを特徴として扱う方法を提案する。以下の説明では、自然言語処理分野への適用を念頭において、「特徴」のことを「素性」と表記することがあるが、もちろん、本発明は、自然言語処理分野のみならず他分野にも適用可能である。
【００１７】
すなわち、本発明の素性選択機能付き離散カーネル関数の計算方法は、離散オブジェクトを入力として離散カーネル値を計算する離散カーネル関数の計算方法であって、抽出手段が入力された離散オブジェクトから部分構造を抽出する抽出段階と、部分構造に対して特徴選択手段が統計量に基づく有効性を判定する特徴選択段階と、有効であると判定された部分構造のみが最終的なカーネル値に加算されるように、カーネル計算手段がカーネル値を計算するカーネル計算段階と、を有する。
【００１８】
また本発明の素性選択機能付き離散カーネル関数の計算装置は、離散オブジェクトを入力として離散カーネル値を計算する離散カーネル関数の計算装置であって、入力された離散オブジェクトから部分構造を抽出する抽出手段と、部分構造に対して統計量に基づく有効性を判定する特徴選択手段と、有効であると判定された部分構造のみが最終的なカーネル値に加算されるように、カーネル値を再帰的に計算するカーネル計算手段と、カーネル値の計算過程の途中経過を保持する記憶手段と、を有する。
【００１９】
本発明の手法は、具体的には、全ての部分構造に対して、全学習データ内での正例・負例間の出現頻度の偏りを検定し、出現傾向に偏りがみられる部分構造のみを扱うこととする。つまり、正例・負例間の出現頻度に偏りがある程、それぞれのクラスを特徴付ける特徴として有効であると考える。
【００２０】
これにより、個々の部分構造に対して統計量に基づく重要性のランクを与えることができるため、適切な閾値を与えることで、不要に素性数を増加させず、有効な素性のみを用いて学習・分類が可能となる。
【００２１】
以下、本発明の好ましい態様に基づく離散カーネル計算方法の手順について説明する。
【００２２】
この手順では、統計量の一つとして、カイ二乗（χ2）値を用いて部分構造の検定をおこなう例を示す。Ｃは正例のクラス、
【００２３】
【数１】
2005222365.tif 000003
【００２４】
は負例のクラスを表し、Ｉは任意の部分構造Ｉが出現したことを意味し、
【００２５】
【数２】
2005222365.tif 000004
【００２６】
は出現しない場合を意味する。表１は、カイ二乗値の計算を示す表である。
【００２７】
【表１】
2005222365.tif 000005
【００２８】
ここで、Ｏijを
【００２９】
【数３】
2005222365.tif 000006
【００３０】
両方の条件を満たした場合の観測値とする。例えば、ＯICは、正例中の部分構造が出現した数を意味する。同様に、Ｏiを
【００３１】
【数４】
2005222365.tif 000007
【００３２】
の条件を満たした場合の観測値とする。例えば、ＯCは正例数を意味する。次に、部分構造Ｉが出現するデータ数をｘ、そのうち正例に出現するデータ数をｙとし、同様に、サンプル数をＮ、正例数をＭとおく。
【００３３】
部分構造Ｉのχ2値χ2(Ｉ)を、ｘ(Ｉ)，ｙ(Ｉ)の関数ｃｈｉ(ｘ(Ｉ)，ｙ(Ｉ))と考える。ｘ(Ｉ)，ｙ(Ｉ)は、それぞれ部分構造Ｉに対するｘ，ｙの値である。χ2値は、
【００３４】
【数５】
2005222365.tif 000008
【００３５】
のペアがそれぞれ独立であると仮定した場合の期待値
【００３６】
【数６】
2005222365.tif 000009
【００３７】
と観測値Ｏijとの正規化した偏差であり、以下のように書ける。
【００３８】
【数７】
2005222365.tif 000010
【００３９】
本発明では、まず、χ2値の閾値ｒを与え、コンボリューションカーネルを計算する際に出現した任意の部分構造ｕが、ｒ≦ｕなら通常通りカーネルの値に加算し、ｕ＜ｒの場合は部分構造ｕの値を０とみなしてカーネルの値を計算する。
【発明の効果】
【００４０】
本発明によれば、構造のサイズを気にせずに全ての可能な特徴から必要な特徴を自動的に選択し、必要な特徴のみを使ったカーネル計算が可能となることにより、性能の向上が達成される。具体的には、入力オブジェクトのサイズが大きい場合であっても、有効な学習を行うことができ、また、有効な特徴を含む構造を確実に選択して有効なカーネル値を得ることができるようになる。
【発明を実施するための最良の形態】
【００４１】
次に、本発明の好ましい実施形態について、図面を参照して説明する。ここでは、類似度計算に対して本発明の離散カーネル計算方法を適用した場合を説明する。
【００４２】
本実施形態の手法では、ストリングカーネルの計算の場合と同様の手順を用いて逐次計算を行っていく。だだし、その手順に対し、入力記号列間の共通記号が存在した場合に、そこで計算された部分カーネル値を最終的なカーネル値に含めるかをχ2値で判定する部分が付加される。
【００４３】
まず、前準備として、ある部分構造をｕとする。ｕに対するχ2値は、
χ2(ｕ)＝ｃｈｉ(ｘ(ｕ)，ｙ(ｕ))
であり、その値は、上述の式(1)に基づいて計算される。
【００４４】
また、任意の部分構造ｖに対し、ｕを先頭に持つ全ての部分構造ｕｖのχ2値の上限の値χ2up(ｕ)＝ｃｈｉup(ｘ(ｕ)，ｙ(ｕ))を考える。この上限値χ2up(ｕ)は、明らかに、
【００４５】
【数８】
2005222365.tif 000011
【００４６】
で与えられる。
【００４７】
そこで、本実施形態では、カーネル関数が計算する部分構造であるｕに対して、以下の３つの条件で場合分けをおこなう。この場合分けは、部分構造の統計量に基づく有効性により、それらの部分構造を分類するためのものである。
【００４８】
（１）：  ｒ≦ｃｈｉ(ｘ(ｕ)，ｙ(ｕ))
（２）：  ｒ＞ｃｈｉ(ｘ(ｕ)，ｙ(ｕ))、かつ、ｒ≦ｃｈｉup(ｘ(ｕ)，ｙ(ｕ))
（３）：  ｒ＞ｃｈｉ(ｘ(ｕ)，ｙ(ｕ))、かつ、ｒ＞ｃｈｉup(ｘ(ｕ)，ｙ(ｕ))
このとき、（１）の場合には、ｕのχ2値は閾値ｒ以上なので、これを素性として採用し、最終的なカーネルの値に加算する。すなわち、有効な構造であると判断して、最終的なカーネル値に含めるようにしている。（２）の場合は、ｕのχ2値は閾値ｒ未満なので、最終的なカーネルの値には加算されないが、ｕｖのχ2値が閾値ｒを上回る可能性があるので、内部的には計算値を保持しておく。すなわち、ｕより長い部分構造であってｕを先頭にもつある部分構造について同様の計算をする必要が生じる場合があるので、そのときのために、計算値を内部的に保持しておく。（３）の場合には、ｕとｕｖのχ2値は閾値ｒ未満なので、対象の部分カーネルの値を０とし、以降の計算から削除する。すなわち、ｕを先頭とする部分文字列はどのようなものも閾値ｒ以上とはならないので、そのようなものは以降の計算での処理対象とはしないし、内部的にも計算値を保持しない。
【００４９】
以上の処理を式で書くと以下のようになる。
【００５０】
【数９】
2005222365.tif 000012
【００５１】
ここで、ＫFSSK(Ｓ，Ｔ)は、本実施形態の手順によって計算される、入力記号列Ｓ，Ｔ間のカーネル値を表している。式(3),(4)に示されるように、このカーネル値は、コンボリューションカーネルの一種であるストリングカーネルに属するものである。ただし、式(3),(4)に示すものは、非特許文献１に記載されたストリングカーネルの定義からは拡張されており、また、再帰的に定義されている。以下のＵm(Ｓi，Ｔj)は、部分構造の集合であり、前述の条件（１）を満たすｗ｜ｓi＝ｔj＝ｗを最後の要素とする任意の部分属性列ｕｗで構成される。ここでｗを任意の記号とする。
【００５２】
【数１０】
2005222365.tif 000013
【００５３】
式(5)は、条件（２）を実現している。つまり、ｒ≦χup(ｕｗ)を満たす部分構造のみ、ｕｗを計算し、それ以外は０とする。
【００５４】
【数１１】
2005222365.tif 000014
【００５５】
ここでλは減衰率であり、０≦λ≦１である。
【００５６】
次に、条件（１）の部分構造集合を得るために必要な演算を定義する。式(8)において、条件（１）が成立しない場合には、Ｕm(Ｓi，Ｔj)は空集合とされ、これにより、条件（１）が成立しているときの部分構造ｕのみが最終的なカーネル値に加算されることになる。
【００５７】
【数１２】
2005222365.tif 000015
【００５８】
図１は、上述した本実施形態の計算方法を実施するための装置の構成を示すブロック図である。
【００５９】
図１に示す装置は、入力記号列である離散オブジェクトＡ，Ｂ間のカーネル値を求めることによってそれらオブジェクト間の類似度を算出するものであり、離散オブジェクトＡ，Ｂが入力する入力部１１と、離散オブジェクトＡ，Ｂから部分構造ｕを抽出する部分構造抽出部１２と、抽出された部分構造ｕに関してｃｈｉ(ｘ(ｕ)，ｙ(ｕ))、ｃｈｉup(ｘ(ｕ)，ｙ(ｕ))を算出するカイ二乗算出部１３と、算出されたｃｈｉ(ｘ(ｕ)，ｙ(ｕ))、ｃｈｉup(ｘ(ｕ)，ｙ(ｕ))と閾値ｒとを比較することにより部分構造ｕが上述の条件（１）〜（３）のいずれに該当するかを判定する特徴選択部１４と、特徴選択部１４での判定結果を参照しつつ、式(3)〜(11)に基づいて計算を実行し、離散オブジェクトＡ，Ｂ間の類似度を表すカーネル値を算出するカーネル計算部１５と、カーネル計算部１５での計算の途中経過を格納する中間記憶部１６と、得られたカーネル値を出力する出力部１７と、を備えている。この構成では、特徴選択部１４は、離散オブジェクトＡ，Ｂから統計量に基づく有効な特徴（素性）を選択することとなるので、カーネル計算部１６で実行される再帰計算において、選択された特徴のみが最終的なカーネルの値に加算されることになる。なお、式(3)〜(11)に基づくカーネル値の算出は、再帰計算によるものなので、中間記憶部１６を利用して、計算の途中経過を一時的に格納するようにしている。条件（２）の場合には、内部的には計算値を保持することとなっているが、その計算値Ｋm,uw(Ｓi，Ｔj)も中間記憶部１６に格納される。
【００６０】
次に、上述したカーネル計算方法によって実際に離散カーネルを計算する例を説明する。図２は、記号列（Ｓ：ＡＢＡＣ及びＴ：ＡＢＣ）を入力とした際に、コンボリューションカーネルとしてストリングカーネルを用いた場合の例を示している。図においては、素性選択の閾値ｒとして、１．０を用いている。このとき、部分構造の部分カーネルの値が、カイ二乗値１．０未満の場合は、部分カーネルの値を０としている。よって最終的に得られる値は、カイ二乗値１．０以上の部分カーネルの値の総和である４＋λとなる。
【００６１】
以上、本発明の好ましい実施形態について、記号列を入力した際にコンボリューションカーネルを用いた場合の例を説明したが、本発明は、これに限られるものではなく、離散カーネルとして他のカーネル関数を用いる場合にも適用できる。
【００６２】
以上説明した離散カーネル関数計算方法は、それを実現するためのコンピュータプログラムを、パーソナルコンピュータやワークステーションなどのコンピュータに読み込ませ、そのプログラムを実行させることによっても実現できる。離散カーネル関数計算を行うためのプログラムは、ＣＤ−ＲＯＭなどの記録媒体によって、あるいは、ネットワークを介してコンピュータに読み込まれる。
【００６３】
そのようなコンピュータは、一般に、ＣＰＵと、プログラムやデータを格納するためのハードディスク装置と、主メモリと、キーボードやマウスなどの入力装置と、ＣＲＴなどの表示装置と、ＣＤ−ＲＯＭ等の記録媒体を読み取る読み取り装置と、ネットワークと接続に用いられる通信インタフェースとから構成されている。ハードディスク装置、主メモリ、入力装置、表示装置、読み取り装置及び通信インタフェースは、いずれもＣＰＵに接続している。このコンピュータでは、離散カーネル計算を行うためのプログラムを格納した記録媒体を読み取り装置に装着しその記録媒体からそのプログラムを読み出してハードディスク装置に格納し、あるいは、そのようなプログラムをネットワークからダウンロードしてハードディスク装置に格納し、その後、ハードディスク装置に格納されたプログラムをＣＰＵが実行することにより、上述した離散カーネル計算が行われる。離散カーネル計算の対象となる離散オブジェクトは、予めハードディスク装置内に格納しておいてもよいし、入力装置から入力するようにしてもよい。なお、カイ二乗値を計算し、特徴を選択し、カーネル計算を行うために必要となる、計算結果の一時格納域は、ハードディスク装置上に確保してもよいが、計算の高速化の観点からは、主メモリの記憶領域の一部にそのような一時格納域を設けることが好ましい。
【図面の簡単な説明】
【００６４】
【図１】本発明の実施の一形態のカーネル関数計算装置の構成を示すブロック図である。
【図２】本発明に基づく離散カーネル関数計算の一例を示す図である。
【符号の説明】
【００６５】
１１    入力部
１２    部分構造抽出部
１３    カイ二乗算出部
１４    特徴選択部
１５    カーネル計算部
１６    中間記憶部
１７    出力部
【図１】
2005222365.tif 000016
【図２】
2005222365.tif 000017