説明

情報処理装置、自然言語解析方法、プログラムおよび記録媒体

【課題】 係り受け構造を有する照会パターンに対する文のマッチング・スコアを演算すること。
【解決手段】 本発明の情報処理装置100は、解析対象の文150と、照会パターン160と、上記文内の言語単位間の係り易さを指標する指標値170とを入力として取得する入力部110と、文が照会パターンにマッチする程度を指標するマッチングのスコアを、上記照会パターン160に含まれる各係り受け関係が対応付けられる各指標値を少なくとも変数とする関数で表して演算するスコア演算部120とを含む。スコア演算部120は、上記照会パターンの部分構造と文の範囲との対応付けを試行して、上記関数の部分演算結果を、再利用するため記憶領域130に格納しながら、この部分構造および範囲の内部に関して再帰的に演算することによって、上記スコアを算出する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、自然言語解析技術に関し、より詳細には、係り受け構造を有する照会パターンに対する文のマッチング・スコアを演算するための情報処理装置、自然言語解析方法、プログラムおよび記録媒体に関する。
【背景技術】
【0002】
近年、コンピュータおよびインターネットなどの情報処理技術の発展に伴い、非定型なテキスト情報が膨大に生成されるようになり、テキスト情報を活用する重要性が高まっている。日本語や英語など自然言語による文は、形態素解析によって単語に分割し、係り受け構文解析することによって、それら単語間の意味的な係り受け構造を推定することができる。近年は、製品の評判情報等から特定の評判表現を抽出したり、技術に関する特徴表現を抽出したりすることに対する要望は高く、特定の単語の有無だけではなく、より上位の意味表現である係り受け構造を考慮した情報検索および情報抽出を高精度に行うことができる技術の開発が望まれている。
【0003】
しかし、簡易な単語の有無だけでなく、係り受け構造を考慮した情報検索および情報抽出では、係り受け構文解析自体の誤りによる抽出漏れを引き起こす可能性がある。自然言語で記述された文は、自然言語固有の曖昧さに起因して、1つの文に対して解釈可能な構文木が複数存在し得る。このため、係り受け構文解析は、形態素解析などに比較して解析誤りを生じさせやすい。解析精度は、文節単位では約90%前後であるが、係り受け構造全体が正しく解析される精度はさらに低くなる。単純な試算では、パターン中に2つの係り受け関係が含まれれば、その解析精度は約81%となり、3つなら約73%程度まで低下してしまう。
【0004】
係り受け構造を考慮して情報検索および情報抽出を行うための従来技術としては、1ベスト法、Nベスト法、文内共起と呼ばれる手法が知られている。1ベスト法は、文に対してスコアが最大となるベストの構文解析結果に対してパターンマッチングを行う方法である。Nベスト法は、文に対してスコア上位N通りの構文解析結果を取得して、N通りの構文解析結果に対してパターンマッチングを行い、いずれかの構文解析結果中にマッチするものがあれば、マッチすると判定する方法である(非特許文献1)。文内共起は、文に対して複数の単語が共起しているか否かでマッチングを行う手法である。また、非特許文献2は、係り受け木からの情報抽出をロバストに行うことを目的として、係り受け木上の距離の期待値を計算する手法を開示している。その他、木構造のパターン抽出に関する従来技術としては、例えば特許第4049141号公報(特許文献1)、特許第4341077号公報(特許文献2)、特開2001−134575号公報(特許文献3)が知られている。
【先行技術文献】
【特許文献】
【0005】
【特許文献1】特許第4049141号公報
【特許文献2】特許第4341077号公報
【特許文献3】特開2001−134575号公報
【非特許文献】
【0006】
【非特許文献1】V. M. Jimenez, A. Marzal,”Computation of the n best parse trees for weighted and stochastic context-free grammars.”,Advances in Pattern Recognition,Lecture Notes in Computer Science,Volume 1876/2000,183-192,2000.
【非特許文献2】海野 裕也、坪井 祐太,”係り受け周辺確率に基づく文節間距離”,言語処理学会第16回年次大会発表論文集,頁23−26,2010年3月.
【非特許文献3】J. M. Eisner,”Three New Probabilistic Models for Dependency Parsing: An Exploration”,COLING '96 Proceedings of the 16th conference on Computational linguistics, Volume 1,1996.
【発明の概要】
【発明が解決しようとする課題】
【0007】
しかしながら、上述した1ベスト法は、構文解析が成功した場合には正しいマッチ結果を与えるが、構文解析が失敗した場合は、正しいマッチ結果が与えられない可能性がある。図28は、従来技術による構文解析結果に対するマッチングを説明する図である。図28(A)に示す照会パターンを用いて、図28(B)および(C)に示す構文解析結果に対して1ベスト法でマッチングを行う場合、最良とされた解析結果が正しい図28(B)である場合は、正しくパターンにマッチし、文が正しく抽出されるが、最良と判断された解析結果が図28(C)のような誤ったものである場合、パターンはマッチせず、抽出漏れを発生させてしまう。さらに、1ベスト法は、マッチしたか否かしか判定することができず、情報検索および情報抽出における適合率および再現率を調整することができない点でも充分なものではなかった。
【0008】
上述したNベスト法は、複数通りの構文解析結果に対するマッチングが行われるため、1ベスト法と比較して堅牢性に優れる。しかしながら、上位N通りの解析結果にはマッチしたものがなく、N+1以下の順位にパターンにマッチする解析結果が存在したとしても、その場合ヒットせず、抽出漏れを発生させてしまう。Nを増やすことで堅牢性を向上できるが、1つの文に対して存在し得る構文木の数は、文長に対して指数関数的に増大するため、文の構文解析候補を全列挙するためには文長に対し指数個の解析結果が必要となり現実的ではなく、全列挙しない場合でも、取りこぼしを低減するためには少なくとも当該指数個に比例したNが必要となり、必要な記憶容量および計算量が増大する。また、実用上許容できる現実的なN(〜20)では、全体のほんの一部しか考慮することができず、1ベストと同様に抽出漏れが発生しやすい。さらに、Nベストは、構文解析結果のスコアを与えることができるが、N個中でマッチした構文解析結果の解析候補を足しても大きな値とはならないため、値の大小で解析結果の確からしさを判定することも容易ではない。
【0009】
上述した文内共起は、単語が共起しているあらゆる文を網羅できるため、再現率100%を達成することができる。しかしながら、文内共起では、文中における単語間の関係性が考慮されないため、明らかに単語間に係り受け関係がない文も抽出されてしまい、効率的ではなく、適合率を向上させることもできない。さらに、文内共起も同様に、マッチしたか否かしか判定することができず、情報検索および情報抽出における適合率および再現率を調整することができない点では1ベスト法と同様である。また非特許文献2に開示される係り受け木上の距離の期待値を計算する手法は、単語間の距離を確率的に求めることで堅牢性を向上させているが、係り受け構造を有するパターンのマッチングを取り扱えるものではなかった。
【0010】
情報検索および情報抽出では、単にマッチしたか否かではなく、トレードオフの関係にある適合率および再現率を任意のレベルに調整できることが好ましい。例えば、検索漏れが望ましくない場合には、網羅性を優先し再現率を高めることが好ましい。検索漏れはある程度許容できるが、正確な結果を得たいという場合は、正確性を優先し適合率を高め、信頼性の高い情報だけを検索および抽出することが好ましい。
【0011】
上述した適合率および再現率を任意のレベルに調整できる、係り受け構造を考慮した情報検索および情報抽出の実用的な技術は現時点では知られておらず、したがって、依然として係り受け構造を有する照会パターンに対する文のマッチング・スコアを、文の構文解析候補を全列挙することなく算出し、情報検索および情報抽出における適合率および再現率を所望のレベルで調整することを可能とするマッチング・スコアの演算手法の開発が望まれていた。さらに、適合率および再現率を所望のレベルに調整することができる係り受け構造を考慮した情報検索および情報抽出技術の開発が望まれていた。
【0012】
本発明は、上記従来技術における問題点に鑑みてなされたものであり、本発明は、係り受け構造を有する照会パターンに対する文のマッチング・スコアを、文の構文解析候補を全列挙することなく算出し、情報検索および情報抽出における適合率および再現率を所望のレベルで調整可能とし、ひいては構文解析誤りに高い堅牢性を実現することができる情報処理装置、自然言語解析方法、プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【0013】
本発明は、上記従来技術の課題を解決するために、以下の特徴を有する情報処理装置を提供する。本発明の情報処理装置は、解析対象の文と、該文内の言語単位間の係り易さを指標する指標値と、照会パターンとを入力として取得する。情報処理装置は、上記取得したデータを用いて、文が照会パターンにマッチする程度を指標するマッチングのスコアを、照会パターンに含まれる各係り受け関係が対応付けられる各指標値を少なくとも変数とする関数で表して演算する。情報処理装置は、スコア演算過程では、上記照会パターンの部分構造と文の範囲との対応付けを試行して、上記指標値を少なくとも変数とする関数の部分演算結果を、再利用するため記憶領域に格納しながら、上記部分構造および範囲の内部に関して再帰的に演算することによって、パターンに対する文のマッチングのスコアを算出する。
【0014】
本発明によれば、また、上記マッチングのスコアを表す関数は、対応付けられる各指標値の積を含む関数とすることができる。上記関数の部分演算結果は、照会パターンの部分構造を文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値の積を含む関数で表される部分スコアとすることができる。
【0015】
さらに、本発明によれば、上記指標値は、文内の各言語単位間の係り受け周辺確率、または係り易さを指標する重みを用いることができる。上記マッチングのスコアは、文に対する解析候補中の照会パターンを部分木として有する候補が生成されるパターン周辺確率、または文に対する解析候補中の照会パターンが部分木として出現する見込みを意味するパターン出現回数期待値とすることができる。マッチングのスコアを表す関数は、対応付けられる各係り受け周辺確率の積として上記パターン周辺確率を近似することができ、または上記照会パターンが出現する解析候補にわたる該解析候補に含まれる各係り受け関係の各重みの積の総和を規格化した関数で表すことができる。上記部分スコアは、部分構造内の各係り受け関係に対応付けられる各係り受け周辺確率の積の局所最大値、または上記文の範囲内側の各対応付けの組み合わせにわたる前記各重みの積の総和とすることができる。また本発明によれば、上述した特徴を有する情報処理装置が実行する自然言語解析方法、上記情報処理装置を実現するためのプログラム、および該プログラムを格納する記録媒体を提供することができる。
【0016】
上記構成によれば、マッチングのスコアを解析対象の文の言語単位間に与えられる評価値の関数で表し、動的計画法を適用することによって、係り受け構造を有する照会パターンに対する文のマッチングの程度を指標し、確率として取り扱うことができるスコアを、全解析候補を列挙することなく効率的に計算することが可能となる。その際の計算量は、動的計画法を適用して演算コストを記憶コストに交換することができるため、文長L、パターンサイズMに対してO(LM)程度で済む。
【図面の簡単な説明】
【0017】
【図1】統計的係り受け構文解析の結果を説明する図。
【図2】本発明の実施形態によるマッチング・スコアの算出方法の概略を説明する図。
【図3】本発明の第1の実施形態によるコンピュータ装置の機能ブロック図。
【図4】本発明の第1の実施形態における(A)解析対象の文および(B)係り受け周辺確率のデータ構造を例示する模式図。
【図5】本発明の第1の実施形態における照会パターンのデータ構造を例示する図。
【図6】本発明の第1の実施形態によるマッチング・スコア演算方法を説明する概念図。
【図7】左側に親ノードがある場合の照会パターンの構文木を示す図。
【図8】本発明の第1の実施形態における(A)左シーケンス関数および(B)左リンク関数を説明する図。
【図9】本発明の第1の実施形態における(A,B)左シーケンス関数の疑似コードおよび再帰呼び出しを説明する概念図、並びに(C,D)左リンク関数の疑似コードおよび再帰呼び出しを説明する概念図。
【図10】本発明の第1の実施形態における(A,B)右シーケンス関数の疑似コードおよび再帰呼び出しを説明する概念図、並びに(C,D)右リンク関数の疑似コードおよび再帰呼び出しを説明する概念図。
【図11】本発明の第1の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理のメインルーチンを示すフローチャート。
【図12】本発明の第1の実施形態によるメインルーチンによる、初期の照会パターンと解析対象の文との対応付けを示す図。
【図13】本発明の第1の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理において呼び出される左シーケンス関数のルーチンを示すフローチャート。
【図14】本発明の第1の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理で呼び出される左リンク関数のルーチンを示すフローチャート。
【図15】本発明の第1の実施形態による左シーケンス関数、左リンク関数、右シーケンス関数および右リンク関数の相互再帰的な呼び出しを説明する図。
【図16】本発明の第1の実施形態において、関数の相互再帰的な呼び出しにより、照会パターンの全体構造から末端までの対応付けが行われる様子を示す図。
【図17】本発明の第1の実施形態によるマッチング・スコア演算機能を組み込んだ情報検索システムの機能ブロック図。
【図18】本発明の第2の実施形態によるコンピュータ装置の機能ブロック図。
【図19】本発明の第2の実施形態によるマッチング・スコア演算方法を説明する概念図。
【図20】本発明の第2の実施形態における左シーケンス関数を説明する図。
【図21】本発明の第2の実施形態における(A)左リンク関数および(A)左マッチ関数を説明する図。
【図22】本発明の第2の実施形態における(A)左シーケンス関数(B)左リンク関数および(C)左マッチ関数の疑似コードを示す図。
【図23】本発明の第2の実施形態における(A)右シーケンス関数(B)右リンク関数および(C)右マッチ関数の疑似コードを示す図。
【図24】本発明の第2の実施形態による左右のシーケンス関数、左右のリンク関数および左右のマッチ関数の相互再帰的な呼び出しを説明する図。
【図25】実験例1の結果および1ベスト法の比較例1の結果を示すROCグラフ。
【図26】実験例2の結果および1ベスト法による比較例2〜4の結果を示すROCグラフ。
【図27】実験例3の結果および1ベスト法による比較例5〜7の結果を示すROCグラフ。
【図28】従来技術による構文解析結果に対するマッチングを説明する図。
【発明を実施するための形態】
【0018】
以下、本発明について実施形態をもって説明するが、本発明は、後述する実施形態に限定されるものではない。なお、以下に説明する実施形態では、照会パターンに対する文のマッチング・スコアを演算するコンピュータ装置を一例として説明する。
【0019】
[用語説明]
以下まず、本発明の実施形態で使用する用語について説明する。図1は、統計的係り受け構文解析の結果を説明する図である。図1は、解析対象の文「エンジンが|走行中に|突然|煙を|噴いた」に対し、係り受け構文解析を実施した場合の解析結果を模式的に表す。解析対象の文は、事前に形態素解析等の事前処理が施されており、単語列または文節列(単語および文節は、いずれも文から区分される言語単位である。以下、言語単位として文節を例に説明するが、言語に応じてまたは任意に、単語または文節を選択することができる。)として与えられる。
【0020】
「解析候補」とは、文節列として与えられる解析対象の文に対する統計的(確率的)係り受け構文解析において、該文に対して存在し得る構文木をいう。図1には、便宜上4つの解析候補の構文木が例示されているが、解析候補は文に対して存在可能なあらゆる構文木を含み、その数は文長(文節数)に対して指数的に増大する。「解析候補の解析確率」とは、文に対し統計的係り受け構文解析を実行した場合に、解析候補の構文木に対して与えられる確率をいう。各解析候補の解析確率は、全解析候補にわたって解析確率の総和をとると1になるよう規格化されている。
【0021】
「係り受け周辺確率」とは、文内の文節間の係りやすさを指標する周辺確率であり、本質的には、係り受けペアを含むすべての構文木の解析候補の解析確率の総和に一致する。文中のi番目の文節を係り元としてj番目の文節を係り先とした係り受けペアの係り受け周辺確率は、p(i,j)で表される。ある係り受けペアを含む解析候補を全列挙することは現実的には困難であるが、仮に図1中に全解析候補が列挙されているとすると、文「エンジンが|走行中に|突然|煙を|噴いた」における係り受けペア「エンジンが→噴いた」の係り受け周辺確率は、この係り受けペアが出現している2番目および3番目の候補の解析確率の総和(0.3+0.2=0.5)となる。同様に、係り受けペア「煙を→噴いた」の係り受け周辺確率は、この係り受けペアが出現している1〜4番目の解析候補の解析確率の総和(0.4+0.3+0.2+0.1=1.0)となる。係り受け周辺確率は、動的計画法を適用することにより計算可能であることが知られている。
【0022】
「パターン周辺確率」とは、全解析候補中のパターンを部分木として含む構文木の解析候補が生成される周辺確率であり、本発明の実施形態では、照会パターンに対する文のマッチング・スコアとして利用することができる。「パターン周辺確率」は、本質的には、全解析候補中のパターンを部分木として含む構文木解析候補の解析確率の総和に一致する。図1に示す例では、文「エンジンが|走行中に|突然|煙を|噴いた」におけるパターン「エンジンが→噴いた,煙を→噴いた」のパターン周辺確率は、このパターンが出現している2番目および3番目の解析候補に与えられた解析確率の総和(0.3+0.2=0.5)となる。なお、パターン周辺確率は、0〜1の実数をとる。
【0023】
全解析候補を列挙して、各候補がパターンにマッチするか否かを判定して、マッチする候補の解析確率の総和をとることは現実的には困難であるが、以下に説明する本発明の第1の実施形態により、解析候補を全列挙することなく、パターン周辺確率を効率的に近似計算することが可能である。本発明の第1の実施形態では、解析候補を全列挙することなく、確率として取り扱えるパターン周辺確率を求めるために、マッチングに関与した係り受けペアの係り受け周辺確率の積でパターン周辺確率を近似する。図2は、本発明の実施形態によるマッチング・スコアの算出方法の概略を説明する図である。図2(A)は、係り受け構造を有する照会パターンを例示し、図2(B)は、本発明の第1の実施形態によるパターン周辺確率の近似計算を説明する図である。
【0024】
図2に示す例では、文「エンジンが|走行中に|突然|煙を|噴いた」におけるパターン「エンジンが→噴いた,煙を→噴いた」のパターン周辺確率は、マッチングに関与する係り受けペア「エンジンが→噴いた」および「煙を→噴いた」の係り受け周辺確率の積(0.5×1=0.5)で近似計算することができる。また、係り受けペア「エンジンが→噴いた」および「煙を→噴いた」の各係り受け周辺確率は、上述したように、それぞれ、係り受けペアが出現している2番目および3番目の解析候補に与えられた解析確率の総和(0.3+0.2=0.5)、および1〜4番目の解析候補に与えられた解析確率の総和(0.4+0.3+0.2+0.1=1.0)となり、これらは既存技術で算出することができる。
【0025】
「パターン出現回数期待値」とは、全解析候補中のパターンが出現する回数の期待値をいい、本発明の実施形態では、照会パターンに対する文のマッチング・スコアとして利用することができる。パターン出現回数期待値は、本質的には、解析候補の構文木に出現するパターンの総数と、該構文木の解析確率との積の全解析候補にわたる総和に一致する。図1に示す例では、文「エンジンが|走行中に|突然|煙を|噴いた」におけるパターン「エンジンが→噴いた,煙を→噴いた」のパターン出現回数期待値は、各解析候補の解析確率と、候補中の出現回数との積の全解析候補にわたる総和(0.4×0+0.3×1+0.2×1+0.1×0=0.5)となる。
【0026】
全解析候補を列挙して、候補中にパターンが出現する回数を計数し、候補の出現回数と解析確率との積を求め、全解析候補にわたり総和をとることは現実的には困難であるが、以下に説明する本発明の第2の実施形態により、全解析候補を列挙することなく、パターン出現回数期待値を効率的に計算することが可能である。図2(C)は、本発明の第2の実施形態によるパターン出現回数期待値の計算方法を説明する図である。図2(C)に示す例では、パターン「エンジンが→噴いた,煙を→噴いた」が出現する構文木の解析候補の出現回数が数え上げられ、パターンが出現する解析候補の解析確率と、それぞれの出現回数との積の総和(0.3×1+0.2×1=0.5)で計算することができる。
【0027】
なお、図1に示す例では、第2および第3番目の候補での出現回数はいずれも「1」であるため、上記例のパターン出現回数期待値はパターン周辺確率に一致する。しかしながら、解析候補中に複数回出現することも想定され、その場合パターン出現回数期待値が1以上となる可能性もある。例えば、文「A部長は、B部長が発言したことに関して発言した」に対して照会パターン「部長…発言…[動詞]」が与えられた場合を考える。この場合、上述したパターン周辺確率をマッチング・スコアとする第1の実施形態では、最大の出現箇所の周辺確率を計算し、「A部長…発言した」か「B部長…発言した」かのいずれか高い方に対応付けた場合の周辺確率が返される。これに対して、上述したパターン出現回数期待値をマッチング・スコアとする第2の実施形態では、「A部長…発言した」および「B部長…発言した」の両方をカウントし、1以上の値が返る場合がある。パターン周辺確率は、構文解析の確信度が重要である場合により好適に使用することができ、パターン出現回数期待値は、単純に出現している回数が重要であるときにより好適に用いることができる。
【0028】
本発明の第1および第2の実施形態によるマッチング・スコアの演算処理では、動的計画法を適用することにより、構文解析候補を全列挙することなく効率的に、それぞれマッチング・スコアとして用いられるパターン周辺確率またはパターン出現回数期待値を演算する。以下、第1実施形態によるマッチング・スコア(パターン周辺確率)の演算処理について説明する。
【0029】
[第1の実施形態]
以下、上述した用語の説明を踏まえて、本発明の第1の実施形態による照会パターンに対する文のマッチング・スコアを演算するコンピュータ装置について説明する。図3は、本発明の第1の実施形態によるコンピュータ装置100の機能ブロックを示す。図3に示すコンピュータ装置100は、概ねパーソナル・コンピュータ、ワークステーションまたはメインフレームなどの汎用コンピュータとして構成されている。コンピュータ装置100は、図示しないCPU(Central Processing Unit)と、RAM(Random Access Memory)と、HDD(Hard Disk Drive)やSSD(Solid State Drive)などの記憶装置と、必要に応じてNIC(Network Interface Card)とを備え、Windows(登録商標)、UNIX(登録商標)、AIX(登録商標)、Linux(登録商標)などのOSの制御下で稼働する。図3に示す各機能部(詳細は後述する。)は、CPUの作業領域を提供するメモリ上にプログラムを展開し、CPUの制御の下プログラムを実行させて、各ハードウェア資源を動作制御することによって、コンピュータ装置100上に実現される。
【0030】
本発明の実施形態によるコンピュータ装置100は、解析対象の文150および照会パターン160を含む入力データを取得する入力部110と、入力データを用いてマッチング・スコアを算出するスコア演算部120と、マッチング・スコアを含む解析結果を出力する出力部140とを含む。
【0031】
解析対象の文150は、入力部110に入力される前段階で、形態素解析などの文字列解析手法で単語列に分割され、各単語には適宜品詞タグ付け(Part-of-Speech Tagging)がなされる。解析対象の文150は、自然言語の種類にもよるが、単語列または文節列として与えられる。解析対象の文は、日本語や英語などあらゆる自然言語で記述された文とすることができるが、基本的には非交差(projective)の係り受け関係を扱うものとし、単方向および双方向の係り受け関係が許容される。つまり、交差がほとんど無いほとんどの言語に適用することができる。英語などの双方向の係り受けを有する文に対しても適用することができる。図4(A)は、解析対象の文150を例示し、文長Lの文節列(x,x,…,x)が示されている。
【0032】
本発明の実施形態では、上記解析対象の文150に付属し、文内の各文節ペアの係り易さを指標する係り受け周辺確率170がさらに入力データとして与えられる。i番目の文節からj番目の文節への係り受け周辺確率p(i,j)は、予め文に対して統計的構文解析を施した結果として取得することができる。図4(B)は、係り受け周辺確率170のデータ構造を模式的に例示しており、係り元番号iを行とし、係り先番号jを列としたテーブルが示されており、係り受け周辺確率の値に比例した面積の正方形がセル内に示されている。
【0033】
統計的係り受け構文解析は、統計学的手法を取り入れた係り受け構文解析手法であり、与えられた文について各単語または文節の係り先の単語または文節を同定する問題を解く自然言語解析処理である。数学的には、解析対象の文をi番目の文節(単語)を表す要素xを用いて文節列x={x,x,…,x}で表し、係り受け構造をi番目の文節の係り先インデックスを表す要素yを用いて列y={y,y,…,y}∈Nで表し、文節列と係り受け構造に対する確率変数をそれぞれX,Yで表すと、1ベスト法は、X=xが与えられたときのY=yの同時分布P(Y=y|X=x)を最大化するyを決定することに対応する。Nベスト法は、P(Y=y|X=x)が大きい順にyをNセット決定することに対応する。なお、統計的構文解析の詳細については、非特許文献3を参照することができる。
【0034】
上記照会パターン160は、文節にマッチさせるパターン要素をノードとし、パターン要素間の係り受け関係をエッジとした木構造で表すことができる。照会パターン160は、数学的には、文節にマッチさせるi番目のパターン要素を表す要素pを用いて、長さMのパターン列p={p,p,…,p}を用いて表すことができる。照会パターン160の係り受け構造については、パターン要素pの親ノード(係り先)のインデックスを返す関数par(p,i)で表すことができる。照会パターン160は、好適には、非交差係り受け構文木の部分木、すなわち、順序付きであり、左右別に子ノードが定義され得る木構造とすることができる。このため、各ノードを左から右へ辿ったときの順序で文中に出現することがマッチの条件となる。また、照会パターンの文頭または末尾にルートを仮想的に設定し、設定されたルートを頂点として、係り受け構造に対応して木構造が定義される。
【0035】
ノード間に定義される関係としては、注目するノードをnとして、親ノードPAR(n)、最左子ノードLCH(n)、最右子ノードRCH(n)、兄弟ノードSIB(n)を挙げることができる。最左子ノードLCH(n)は、注目ノードnの左側の子ノードであって、一番左側にあるノードをいい、最右子ノードRCH(n)は、注目ノードnの右側の子ノードであって、一番右側にあるノードをいう。兄弟ノードSIB(n)は、注目ノードnと親を同一とするノードであって、注目ノードnが親の左側に存在する場合には注目ノードnの右側に存在するノードをいい、注目ノードnが親の右側に存在する場合には注目ノードnの左側に存在するノードをいう。照会パターン160のあらゆる係り受け構造は、上記PAR(n)、最左子ノードLCH(n)、最右子ノードRCH(n)、兄弟ノードSIB(n)を用いて、直接的にまたは間接的に表すことができる。
【0036】
図5(A)に示す照会パターン160aでは、ルートを注目ノードnとした場合、注目ノードnの最左子ノードLCH(n)としてパターン要素「発言した」が、パターン要素「発言した」の最左子ノードLCH(LCH(n))としてパターン要素「社長が」が規定される。パターン要素「発言した」を注目ノードnとしてみた場合には、注目ノードnの親ノードPAR(n)がルートで、注目ノードnの最左子ノードLCH(n)がパターン要素「社長が」に対応する。
【0037】
図5(B)に示す照会パターン160bでは、ルートを注目ノードnとした場合、注目ノードnの最左子ノードLCH(n)としてパターン要素「噴いた」が規定され、パターン要素「噴いた」の最左子ノードLCH(LCH(n))としてパターン要素「エンジンが」が規定され、パターン要素「エンジンが」の兄弟ノードSIB(LCH(LCH(n)))としてパターン要素「煙を」が規定されている。パターン要素「エンジンが」を注目ノードnとしてみた場合は、注目ノードnの親ノードPAR(n)がパターン要素「噴いた」に対応し、注目ノードnの兄弟ノードSIB(n)がパターン要素「煙を」に対応する。
【0038】
照会パターン160の各ノードを構成するパターン要素としては、上述した「社長」や「エンジンが」といった単語や文節の文字表現そのものとしてもよいし、正規形、「動詞」や「名詞」などの品詞その他のタグ情報に対する制約条件、ワイルドカードを利用した正規表現としてもよく、特に限定されるものではない。ここで、パターン要素pがi番目の文節xにマッチする場合に「真(1)」を出力し、マッチしない場合に「偽(0)」を出力するパターンマッチング関数M(x,p)∈{0,1}を定義する。
【0039】
再び図3を参照すると、スコア演算部120は、入力部110が取得した入力データを用いて、照会パターン160に対する解析対象の文150のマッチング・スコアを演算する。上述したように第1の実施形態においては、解析対象の文150に対し存在可能な全解析候補の中で上記照会パターン160を部分木として有する候補が生成されるパターン周辺確率をマッチング・スコアとして用いる。パターン周辺確率は、照会パターン160に規定される各係り受け関係が対応付けられる各係り受け周辺確率p(i,j)の関数で表され、より具体的には、マッチングに関与する各係り受け周辺確率p(i,j)の積で近似される。本実施形態では、スコア演算部120により、大域的に最大となるパターン周辺確率が最終的に算出され、同時に照会パターン160と解析対象の文150との最適な対応付けも決定される。
【0040】
対応付けは、数学的には、パターン要素pをマッチさせる文節のインデックスmを用いて、長さMのマッチング列m={m,m,…,m}∈Nとして表すことができる。なお、任意のiに対してM(xmi,p)=1である必要がある。また本発明の第1の実施形態において、マッチング・スコアは、数学的には、以下の式(1)で表す値を求めることになる。なお、下記式(1)中のV(y,m,p)は、パターン列pをマッチング列mでマッチさせたとき、パターン列pの親と係り受け構造を表す列yの親とが一致するときに1を返す関数である。すなわち、V(y,m,p)は、任意のiに対してymi=mpar(p,i)であるとき1を返し、妥当性を保証するための制約条件として用いられる。
【0041】
【数1】

【0042】
上記式(1)は、このままでは計算できないため、同時分布を周辺確率の積で近似する。すなわち、P(Y=y|X=x)を下記式(2)で表される係り受け周辺確率の積で近似する。
【0043】
【数2】

【0044】
スコア演算部120は、複数の関数群122〜128を備えており、これらの関数群122〜128を再帰的に呼び出すことで、全解析候補を列挙することなく、上記パターン周辺確率を演算する。より具体的には、スコア演算部120は、上記関数群122〜128を用いて、照会パターン160の部分構造と解析対象の文150の範囲との対応付けを試行し、上記係り受け周辺確率の積の部分演算結果を上記部分構造および範囲の内側に関して再帰的に算出する。一度計算された部分演算結果は、動的計画テーブル130内に格納され、演算過程で再び必要になった際に、再度演算する代わりに動的計画テーブル130に格納された値が参照され再利用される。動的計画テーブル130は、部分演算結果を格納するための記憶領域であり、例えばRAM、HDDやSSDなどによる記憶領域により提供される。
【0045】
本発明の第1の実施形態では、照会パターン160の部分構造と解析対象の文150の範囲との対応付けが相互再帰的に扱えることを利用し、動的計画法を適用して、本来計算量的に困難のあるパターン周辺確率の効率的な近似計算を可能としている。本実施形態では、上記関数群として、左シーケンス関数122、右シーケンス関数124、左リンク関数126および右リンク関数128の4つの関数が定義されるが、これらの関数群を用いたスコア演算部120の処理については、詳細を後述する。
【0046】
出力部140は、スコア演算部120が算出したパターン周辺確率(マッチング・スコア)を含む演算結果180を出力する。また第1の実施形態では、パターン周辺確率の演算とともに、照会パターン160の解析対象の文150に対する最適なマッチング列mも求められるため、上記パターン周辺確率とともに、マッチング列mが規定するマッチ位置も演算結果180に含めることができる。
【0047】
以下、図6〜図8を参照しながら、本発明の第1の実施形態によるマッチング・スコア演算処理について説明する。図6は、本発明の第1の実施形態によるマッチング・スコア演算方法を概念的に説明する図である。本発明の第1の実施形態では、照会パターンに対してEisner構文木と同様の構文木を考える。図6中の三角形および台形は、それぞれ、1次のEisnerアルゴリズムにおける、半成分を表す完全スパン(Complete Span)、および係り受け関係を表す非完全スパン(Incomplete Span)に相当するものである。本発明の実施形態では、各図形は、照会パターンの部分構造を表しており、マッチング・スコアの演算過程で、各図形が表す部分構造と、解析対象の文中の範囲(スパン)との最適な対応付けが検索される。
【0048】
図6には、照会パターンの注目ノードnに関連して、最左子ノードLCH(n)、注目ノードn、最右子ノードRCH(n)、兄弟ノードSIB(n)および親ノードPAR(n)が順に並べられている。まず、図6中に示した第3の構文木生成規則により、照会パターンのパターン要素を表すこれらノード各々から、それぞれ半成分を表す左向き三角形および右向き三角形の各組が生成される。続いて、図6中に示した第2の構文木生成規則により、最左子ノードLCH(n)の右向き三角形と、注目ノードnの左向き三角形とから、左向き台形Fが生成される。この左向き台形Fは、最左子ノードLCH(n)および注目ノードnの間の部分構造を表し、最左子ノードLCH(n)から注目ノードnへの係り受け関係を表す。同様に、注目ノードnの右向き三角形と、最右子ノードRCH(n)の左向き三角形とから、最右子ノードRCH(n)から注目ノードnへの係り受け関係を表す右向き台形Hが生成され、兄弟ノードSIB(n)から親ノードPAR(n)への係り受け関係を表す左向き台形Jについても同様である。
【0049】
さらに、図6中に示した第1の構文木生成規則により、最左子ノードLCH(n)の左向き三角形Gと、最左子ノードLCH(n)および注目ノードnの間の部分構造を表す上記左向き台形Fとから、最左子ノードLCH(n)および注目ノードnの間の部分構造を表す左向き三角形Cが生成される。同様に、上記右向き台形Hと、最右子ノードRCH(n)の右向き三角形Iとから右向き三角形Dが生成され、兄弟ノードSIB(n)の左向き三角形Kと上記生成された左向き台形Jとから左向き三角形Eが生成される。
【0050】
さらに、図6中に示した第2の構文木生成規則により、上記右向き三角形Dと左向き三角形Eとから、注目ノードnから親ノードPAR(n)への係り受け関係を表す左向き台形Bが生成される。図6中に示した第1の構文木生成規則により、さらに、左向き三角形Cと、左向き台形Bとから、最左子ノードLCH(n)および親ノードPAR(n)の間の部分構造を表す左向き三角形Aが生成される。このようにして、LCH(n)、n、RCH(n)、SIB(n)およびPAR(n)間の部分構造各々を表す図形をノードとしたEisner構文木と同様の構文木が生成される。
【0051】
なお、図6は、注目ノードnを中心とした照会パターンの一部構造を表したものであり、具体的な照会パターンに応じて、さらに詳細な構造が定義される。例えば最左子ノードLCH(n)を注目ノードとしてさらにLCH(LCH(n))、RCH(LCH(n))、SIB(LCH(n))が定義されたり、親ノードPAR(n)のさらに親ノードPAR(PAR(n))が定義されたりする場合があり、これらは図示を省略されていることに留意されたい。さらに、上記RCH(n)を注目ノードとする場合など、注目ノードが親ノードの右側に存在する場合には、図7に示すように、PAR(n)、SIB(n)LCH(n)、nおよびRCH(n)の順となり、各部分構造各々を表す図形をノードとした構文木が生成される。
【0052】
最終的には、照会パターンの末尾にルートを設定した場合は、ルートから照会パターンの最左子孫までの全体構造を表す左向き三角形が生成される。あるいは、照会パターンの文頭にルートを設定した場合は、ルートから最右子孫までの全体構造を表す右向き三角形が生成される。なお、ルートを頭に設定するか、末尾に設定するかは任意であり、以下の説明では、解析対象の文および照会パターン共に末尾にルートが設定されるものとする。
【0053】
マッチング・スコア演算では、スコア演算部120は、上記照会パターンの構文木の全体構造を表す左向き三角形を、解析対象の文の頭から末尾までの範囲に一旦対応付け、ルートノードの最左子ノードLCH(root)から順に対応付けを開始させる。本発明の実施形態では、上記左向き三角形および右向き三角形は、図3に示した左シーケンス関数122および右シーケンス関数124に対応し、上記左向き台形および右向き台形は、左リンク関数126および右リンク関数128に対応する。スコア演算過程では、スコア演算部120は、上記関数群122〜128を再帰的に呼び出して、各図形が表す部分構造と解析対象の文中の範囲との対応付けを試行し、上記台形で表される係り受け関係に対応して係り受け周辺確率によるスコアを与え、最適なマッチング列mと、そのパターン周辺確率とを求める。
【0054】
以下、上記シーケンス関数122,124およびリンク関数126,128の処理について詳細を説明する。図8は、本発明の第1の実施形態における(A)左シーケンス関数および(B)左リンク関数を説明する図である。図9は、本発明の第1の実施形態における(A,B)左シーケンス関数の疑似コードおよび左シーケンス関数による再帰呼び出しを説明する概念図、並びに(C,D)左リンク関数の疑似コードおよび左リンク関数による再帰呼び出しを説明する概念図である。図10は、本発明の第1の実施形態における(A,B)右シーケンス関数の疑似コードおよび右シーケンス関数による再帰呼び出しを説明する概念図、並びに(C,D)右リンク関数の疑似コードおよび右リンク関数による再帰呼び出しを説明する概念図である。
【0055】
図8(A)および図9(A,B)に示すように、左シーケンス関数122は、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、
(1)親ノードPAR(n)がr番目の文節に対応しており、
(2)注目ノードnおよびその子孫が、l,…,r−1の範囲に存在し、
(3)注目ノードnがPAR(n)の左側に存在する
ときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。つまり、左シーケンス関数122は、注目ノードnに関し、最左子孫(LCH(n)の子孫の左側末端)と親ノードPAR(n)との間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。
【0056】
左シーケンス関数122は、上記部分構造の内側の構造を探索するために、上述した条件(2)により、l,…,r−1のいずれかに対し注目ノードnの対応付けを試行する。試行位置を変数iで表すと、注目ノードn(=p)がi番目の文節xにマッチする場合、パターンマッチング関数M(x,p)は、「真(1)」を出力する(疑似コードではmatch(n,i)=true)。注目ノードnがxにマッチするとき、照会パターンの部分構造中の注目ノードnから親ノードPAR(n)への係り受け関係が、文中のi番目→r番目の文節ペア間に対応付けられ、係り受け周辺確率p(i,r)が与えられる。
【0057】
また、注目ノードnがxにマッチする場合、非交差条件により、注目ノードnの最左子ノードLCH(n)およびその子孫は、範囲l,…,i−1に存在することになるので、LCH(n)と、変数lと、変数iとを引数として与えて左シーケンス関数122を再帰的に呼び出す。同様に、注目ノードnの最右子ノードRCH(n)およびその子孫、並びに兄弟ノードSIB(n)およびその子孫たちは、非交差条件により、範囲i+1,…,r−1に存在することになるので、詳細を後述する左リンク関数126を再帰的に呼び出す。
【0058】
図9(A)で示す疑似コードのように、左シーケンス関数left_seq()は、少なくとも注目ノードnがマッチする各試行位置iについて、該試行位置iの左半分および右半分の範囲に関して、照会パターンの部分構造のさらに内側の対応付けを試行する左シーケンス関数122および左リンク関数126を再帰的に呼び出す。左シーケンス関数left_seq()は、再帰的に呼び出された左シーケンス関数122および左リンク関数126から戻された各部分演算結果と、上記与えられた係り受け周辺確率p(i,r)との積を計算する。注目ノードnがマッチする試行位置iが複数ある場合には、その最大値が選択されて、部分演算結果として呼び出し元に返される。
【0059】
右シーケンス関数124については、図10(A,B)に疑似コードおよび再帰呼び出しを説明する概念図を示す。右シーケンス関数124も、左シーケンス関数と同様に、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、
(1)親ノードPAR(n)がl番目の文節に対応しており、
(2)注目ノードnおよびその子孫が、l+1,…,rの範囲に存在し、
(3)注目ノードnがPAR(n)の右側に存在する
ときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。
【0060】
つまり、右シーケンス関数124は、図10(A)および(B)に示すように、注目ノードnに関し、親ノードPAR(n)と最右子孫(RCH(n)の子孫の右側末端)との間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。右シーケンス関数124は、上記部分構造のさらに内側の構造を探索するために、上述した条件(2)により、l+1,…,rのいずれかに対し注目ノードnの対応付けを試行する。注目ノードnが文節xにマッチするとき、照会パターンの部分構造中の注目ノードnから親ノードPAR(n)への係り受け関係が文中のi番目→l番目の文節ペア間に対応付けられ、係り受け周辺確率p(i,l)が与えられる。また、非交差条件により、注目ノードnがマッチする試行位置iの左半部に注目ノードnの兄弟およびその子孫、並びにnの最左子およびその子孫が存在し、右半部に注目ノードnの最右子およびその子孫が存在する。そこで、右シーケンス関数124は、その内側に関してさらに対応付けを試行する右シーケンス関数124および右リンク関数128を再帰的に呼び出し、戻された各部分演算結果と、上記与えられた係り受け周辺確率p(i,l)との積の最大値を出力する。
【0061】
図8(B)および図9(C,D)に示すように、左リンク関数126は、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、
(1)親ノードPAR(n)がr番目の文節に対応しており、
(2)注目ノードnがl番目の文節に対応しており、
(3)注目ノードnの最右子ノードRCH(n)およびその子孫、並びに兄弟ノードSIB(n)およびその子孫が、l+1,…,r−1の間に存在し、
(4)注目ノードnがPAR(n)の左側に存在する
ときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。つまり、左リンク関数126は、注目ノードnに関し、当該注目ノードnと親ノードPAR(n)との間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。
【0062】
非交差条件により、最右子ノードRCH(n)の子孫右側末端は、兄弟ノードSIB(n)の子孫左側末端よりも左にある。そこで、左リンク関数126は、上記部分構造の内側の構造を探索するために、注目ノードnの最右子ノードRCH(n)の子孫右側末端と、兄弟ノードSIB(n)の子孫左側末端との境界を(i,i+1)の位置で試行する。なお、両者の間に他の文節が存在することもある。
【0063】
そして、最右子ノードRCH(n)およびその子孫たちは、l+1,…,i−1に存在するはずなので、左リンク関数126は、各試行位置iについて、RCH(n)と、変数lと変数iとを引数として与えて、右シーケンス関数124を再帰的に呼び出す。同様に、兄弟ノードSIB(n)およびその子孫たちは、非交差条件に従い、i+1,…,r−1の間に存在するはずなので、左リンク関数126は、各試行位置iについて、SIB(n)と、変数i+1と変数rとを引数として与えて、左シーケンス関数122を再帰的に呼び出す。図9(C)で示す疑似コードのように、左リンク関数left_link()は、再帰的に呼び出された右シーケンス関数124および左シーケンス関数122から戻された各部分演算結果の積を計算し、各試行位置iにおける最大値を選択して、部分演算結果として呼び出し元に返す。
【0064】
右リンク関数128については、図10(C,D)に疑似コードおよび再帰呼び出しを説明する概念図を示す。右リンク関数128も、左リンク関数と同様に、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、
(1)親ノードPAR(n)がl番目の文節に対応しており、
(2)注目ノードnがr番目の文節に対応しており、
(3)注目ノードnの最左子ノードLCH(n)およびその子孫、並びに兄弟ノードSIB(n)およびその子孫が、l+1,…,r−1の間に存在し、
(4)注目ノードnがPAR(n)の右側に存在する
ときの当該文の範囲における係り受け周辺確率の積の最大値を出力する関数である。
【0065】
つまり、右リンク関数128は、図10(C)および(D)に示すように、注目ノードnに関し、注目ノードnの親ノードPAR(n)と当該注目ノードnとの間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。右リンク関数128は、上記部分構造のさらに内側の構造を探索するために、注目ノードnの兄弟ノードSIB(n)の子孫右側末端と、最左子ノードLCH(n)の子孫左側末端との境界を(i,i+1)の位置で試行する。そして、右リンク関数128は、各試行位置iについて、兄弟ノードSIB(n)と変数lと変数iとを引数として与えて右シーケンス関数124を再帰的に呼び出し、最左子ノードLCH(n)と変数i+1と変数rとを引数として与えて、左シーケンス関数122を再帰的に呼び出す。図10(C)で示す疑似コードのように、右リンク関数right_link()は、再帰的に呼び出された右シーケンス関数124および左シーケンス関数122から戻された各部分演算結果の積を計算し、各試行位置iにおける最大値を選択して、部分演算結果として呼び出し元に返す。
【0066】
以下、本発明の第1の実施形態による、上述した関数群を用いたマッチング・スコア演算処理の詳細について説明する。図11は、本発明の第1の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理のメインルーチンを示すフローチャートである。図11に示す処理は、解析対象の文150、照会パターン160および係り受け周辺確率170が指定されたマッチング・スコア演算の指令が与えられたことに応答して、ステップS100から開始する。
【0067】
ステップS101では、入力部110は、指定された解析対象の文150、照会パターン160、係り受け周辺確率170を入力データとして取得する。解析対象の文は、データベースやファイルなどから取得することができる。係り受け周辺確率は、解析対象の文に対して事前に統計的構文解析が施されている場合は、その解析データとして取得することができる。統計的構文解析が事前に施されていなければ、解析対象の文に対し統計的構文解析を実行して、その解析データとして取得することができる。照会パターンは、データベースやファイルなどから取得することができ、またはユーザ指定された照会文を解釈して取得することができる。
【0068】
ステップS102では、スコア演算部120は、照会パターンのルートと、0と文長Lとを与えて、左シーケンス関数left_seq(root,0、L)を呼び出す。図12は、マッチング・スコア演算処理のメインルーチンによる、初期の照会パターンと解析対象の文との対応付けを示す図である。図12に示すように、照会パターンの左向き三角形によって表される最左子孫からルートまでの全体構造が、解析対象の文頭から末尾までの全範囲に対して対応付けられる。
【0069】
再び図11を参照すると、左シーケンス関数left_seq(root,0、L)以降のすべての再帰的な演算が完了して、戻された演算結果を取得すると、ステップS103では、出力部140は、得られたマッチング・スコアAと、マッチング列mとを演算結果として出力し、ステップS104で本マッチング演算処理を終了する。
【0070】
図13は、本発明の第1の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理において呼び出される左シーケンス関数left_seq(n,l,r)のルーチンを示すフローチャートである。図13に示す処理は、例えば図11に示したステップS102の処理で呼び出され、ステップS200から開始する。ステップS201では、スコア演算部120は、引数として与えられたノードnが空の値(null)であるか否かを判定する。ステップS201で、ノードnがnullであると判定された場合(YES)は、ステップS202へ処理を分岐し、値「1」を戻り値として、ステップS217で本処理を終了し、呼び出し元に返す。これは、照会パターンの木構造において枝の末端まで辿り着いたことを意味する。一方、ステップS201で、ノードnがnullではないと判定された場合(NO)は、ステップS203へ処理を分岐する。
【0071】
ステップS203では、スコア演算部120は、引数として与えられた変数lと変数rとが同じ値であるか否かを判定する。ステップS203で、変数lと変数rとが同じ値であると判定された場合(YES)は、ステップS204へ処理を分岐させる。ステップS204では、スコア演算部120は、値「0」を戻り値として、ステップS217で本処理を終了し、呼び出し元に返す。一方、ステップS203で、変数lと変数rとが異なる値であると判定された場合(NO)は、ステップS205へ処理を分岐させる。
【0072】
ステップS205では、スコア演算部120は、動的計画テーブル130を参照し、引数(n,l,r)に対応して既に左シーケンス関数の演算結果がキャッシュされているか否かを判定する。ステップS205で、引数(n,l,r)に対応して演算結果がキャッシュされており、利用可能である場合(YES)は、ステップS206へ処理を分岐させる。ステップS206では、スコア演算部120は、再度演算する代わりに、動的計画テーブル130から引数(n,l,r)に対応するキャッシュ値を読み出し、ステップS217で本処理を終了させ、呼び出し元にキャッシュ値を返す。本発明の実施形態では、同じ引数のセットに対して、2度以上計算が繰り返されないため、照会パターンのサイズ、解析対象の文の長さに対して、多項式時間で計算することができる。
【0073】
一方、ステップS205で、未だキャッシュされていないと判定された場合(NO)は、ステップS207へ処理を分岐する。ステップS207では、スコア演算部120は、演算結果の戻り値として返すための部分スコアの最大値を保持する変数maxを初期化し、ステップS208〜ステップS214のループを実行する。ステップS208〜ステップS214のループでは、スコア演算部120は、現在対応付けを行っている範囲の開始位置lから終了位置r−1までの各試行位置iについて、ステップS209〜ステップS213の処理を実施する。ステップS209では、スコア演算部120は、引数として与えられたノードnが試行位置iの文節xにマッチするか否かを判定する。ステップS209で、マッチしないと判定された場合(NO)には、ステップS214へ分岐し、次のiへ処理を進める。
【0074】
一方、ステップS209で、ノードnが試行位置iの文節xにマッチすると判定された場合(YES)には、ステップS210へ処理を分岐させる。この場合、現在対応付けを行っている範囲の開始位置lから試行位置i−1までの範囲内に最左子ノードLCH(n)およびその子孫が存在し得るため、ステップS210では、スコア演算部120は、ノードnの最左子ノードLCH(n)と、変数lと、変数iとを与えて、左シーケンス関数left_seq()を再帰的に呼び出す。左シーケンス関数left_seq()から演算結果が戻されると、戻り値は変数Aに代入される。またマッチする場合、試行位置i+1から現在対応付けを行っている範囲の終了位置lまでの範囲内に最右子ノードRCH(n)および兄弟ノードSIB(n)並びにこれらの子孫が存在し得るため、ステップS211では、スコア演算部120は、ノードnと、変数iと、変数rとを与えて、左リンク関数left_link()を再帰的に呼び出す。左リンク関数left_link()から演算結果が戻されると、戻り値は変数Bに代入される。
【0075】
ステップS212では、スコア演算部120は、マッチする試行位置iと変数rとに対応する係り受け周辺確率p(i,r)と、ステップS210の左シーケンス関数left_seq(LCH(n),l,i)からの戻り値Aと、ステップS211の左リンク関数left_link(n,i,r)からの戻り値Bとの積sを計算する。ステップS213では、スコア演算部120は、現在保持しているmaxの値と、ステップS213で計算された積sとを比較して、大きな方の値でmaxを更新する。
【0076】
ステップS208〜ステップS214では、変数lから変数r−1までの各試行位置iのうち、nにマッチするものに関して、上記係り受け周辺確率p(i,r)と、最左子ノードの左シーケンス関数の演算結果Aと、左リンク関数の演算結果Bとの積sがそれぞれ計算され、その中で局所最大の値がmaxに保持される。ステップS208〜ステップS214のループを抜けると、ステップS215では、スコア演算部120は、動的計画テーブル130のcache_lseq[n,l,r]の配列にmaxの値を記憶し、(n,l,r)を計算済みに設定する。ステップS216では、スコア演算部120は、maxを戻り値として、ステップS217で本処理を終了させ、呼び出し元に返す。
【0077】
図14は、本発明の第1の実施形態によるコンピュータ装置が実行する、マッチング・スコア演算処理で呼び出される左リンク関数left_link(n,l,r)のルーチンを示すフローチャートである。図14に示す処理は、例えば図13に示したステップS211の処理で呼び出され、ステップS300から開始する。ステップS301では、スコア演算部120は、引数として与えられた変数lと変数rとが同じ値であるか否かを判定する。ステップS301で、変数lと変数rとが同じ値であると判定された場合(YES)は、ステップS302へ処理を分岐させる。ステップS302では、スコア演算部120は、値「0」を戻り値として、ステップS314で本処理を終了し、呼び出し元に返す。一方、ステップS301で、変数lと変数rとが異なる値であると判定された場合(NO)は、ステップS303へ処理を分岐する。ステップS303では、スコア演算部120は、動的計画テーブル130を参照し、引数(n,l,r)に対応して既に左リンク関数の演算結果がキャッシュされているか否かを判定する。ステップS303で、対応する演算結果がキャッシュされており、利用可能であると判定された場合(YES)は、ステップS304へ処理を分岐させる。ステップS304では、スコア演算部120は、動的計画テーブル130から引数(n,l,r)に対応するキャッシュ値を読み出し、ステップS314で本処理を終了させ、呼び出し元にキャッシュ値を返す。
【0078】
一方、ステップS303で、未だ計算されていないと判定された場合(NO)は、ステップS305へ処理を分岐する。ステップS305では、スコア演算部120は、演算結果の戻り値として返すための最大値を保持する変数maxをで初期化し、ステップS306〜ステップS311のループへ処理を進める。ステップS306〜ステップS311では、スコア演算部120は、現在対応付けを行っている範囲の開始位置lから終了位置r−1までの各試行位置iについて、ステップS307〜ステップS310の処理を実行する。
【0079】
試行位置iは、最右子ノードRCH(n)の子孫の右側末端と、兄弟ノードSIB(n)の子孫の左側末端との境界を表す。現在対応付けを行っている範囲の開始位置lから試行位置i−1までの範囲内に最右子ノードRCH(n)およびその子孫が存在し得る。そこで、ステップS307では、スコア演算部120は、引数として与えられたノードnの最右子ノードRCH(n)と、変数lと、変数iとを与えて、右シーケンス関数right_seq()を再帰的に呼び出す。右シーケンス関数right_seq()から演算結果が戻されると、戻り値は変数Aに代入される。
【0080】
また、試行位置i+1から、現在対応付けを行っている範囲の終了位置r−1までの範囲内に兄弟ノードSIB(n)およびその子孫が存在するため、ステップS308では、スコア演算部120は、引数として与えられたノードnの兄弟ノードSIB(n)と、変数i+1と、変数rとを与えて、左シーケンス関数left_seq()を再帰的に呼び出す。左シーケンス関数left_seq()から演算結果が戻されると、戻り値は変数Bに代入される。ステップS309では、ステップS307の右シーケンス関数right_seq()からの戻り値Aと、ステップS308の左シーケンス関数left_seq()からの戻り値Bとの積sを計算する。ステップS310では、現在保持しているmaxの値と、ステップS309で計算された積sとを比較して、大きな方の値でmaxを更新する。
【0081】
ステップS306〜ステップS311では、変数lから変数r−1までの各試行位置iについて、上記最右子ノードに関する右シーケンス関数right_seq()の演算結果Aと、兄弟ノードに関する左シーケンス関数left_seq()の演算結果Bとの積sが求められ、その中で局所最大の値がmaxに保持される。ステップS306〜ステップS311のループを抜けると、ステップS312では、スコア演算部120は、動的計画テーブル130のcache_llink[n,l,r]の配列にmaxの値を記憶して、(n,l,r)を計算済みに設定する。ステップS313では、スコア演算部120は、maxの値を戻り値として、ステップS314で本処理を終了させ、呼び出し元に返す。
【0082】
図15は、上記左シーケンス関数、左リンク関数、右シーケンス関数および右リンク関数の相互再帰的な呼び出しを説明する図である。マッチング・スコア演算処理は、メインルーチンから、照会パターンのEisner構文木のルートノード(全体構造を表す。)および解析対象の文の全範囲を引数として左シーケンス関数left_seq()が呼び出されて開始する。なお、文頭にルートが設定される場合には、右シーケンス関数right_seq()が呼び出される。左シーケンス関数left_seq(n,l,r)は、ノードnにマッチする各試行位置iで、現在対応付けを行っている範囲(l,…,r)を分割し、親反対側の左半分の範囲(l,…,i)について最左子ノードLCH(n)を引数として順方向の左シーケンス関数left_seq(LCH(n),l,i)を再帰的に呼び出すとともに、親側の右半分の範囲(i,…,r)についてノードnを引数として順方向の左リンク関数left_link(n,i,r)を再帰的に呼び出す。
【0083】
左リンク関数left_link(n,l,r)は、各試行位置iで現在対応付けを行っている範囲(l,…,r)を分割し、親反対側の左半分の範囲(l,…,i)について最右子ノードRCH(n)を引数として逆方向の右シーケンス関数right_seq(RCH(n),l,i)を再帰的に呼び出し、親側の右半分の範囲(i+1,…,r)について兄弟ノードSIB(n)を引数として順方向の左シーケンス関数left_seq(SIB(n),i+1,r)を再帰的に呼び出す。
【0084】
右シーケンス関数right_seq(n,l,r)は、ノードnにマッチする各試行位置iで現在対応付けを行っている範囲を分割し、親側の左半分の範囲(l,…,i)についてnを引数として順方向の右リンク関数right_link(n,l,i)を再帰的に呼び出すとともに、親反対側の右半分の範囲(i,…,r)について最右子ノードRCH(n)を引数として順方向の右シーケンス関数right_seq(RCH(n),i,r)を再帰的に呼び出す。右リンク関数right_link(n,l,r)は、各試行位置iで現在の範囲を分割し、親側の左半分の範囲(l,…,i)について兄弟ノードSIB(n)を引数として順方向の右シーケンス関数rihgt_seq(SIB(n),l,i)を再帰的に呼び出し、親反対側の右半分の範囲(i+1,…,r)について最左子ノードLCH(n)を引数として逆方向の左シーケンス関数left_seq(LCH(n),i+1,r)を再帰的に呼び出しする。
【0085】
図16は、上記左シーケンス関数、左リンク関数、右シーケンス関数および右リンク関数の相互再帰的な呼び出しにより、照会パターンの全体構造から末端までの対応付けが行われる様子を示す図である。まず、最上段の左向き三角形で表される照会パターンの全体構造が、解析対象の文の文頭から末尾までの全範囲に対応付けられて、ルートの最左子ノードLCH(root)を引数とした左シーケンス関数left_seq(B)が呼び出される。左シーケンス関数left_seq(B)は、ノードBにマッチする試行位置で、対応付けを行っている範囲を分割し、左半分の範囲について最左子ノードLCH(B)を引数とした左シーケンス関数left_seq(A)を再帰的に呼び出す。同時に、左シーケンス関数left_seq(B)は、右半分の範囲については、ノードBを引数とした左リンク関数left_link(B)を再帰的に呼び出す。ここで、ノードBからルートへの係り受け周辺確率がスコアとして与えられる。
【0086】
左シーケンス関数left_seq(A)は、ノードAにマッチする試行位置で、左半分の範囲について最左子ノードLCH(A)を引数とした左シーケンス関数left_seq(null)を呼び出す。左シーケンス関数left_seq(A)は、同時に、右半分の範囲については、ノードAを引数とした左リンク関数left_link(A)を呼び出す。ここで、ノードAからノードBへの係り受け周辺確率がスコアとして与えられる。左シーケンス関数left_seq(null)に対しては、照会パターンの末端に達したことを示す1が返される。
【0087】
一方、左リンク関数left_link(B)は、対応付けている範囲内で、最右子ノードRCH(B)および兄弟ノードSIB(B)の子孫間を境界する位置を試行し、左半分の範囲について最右子ノードRCH(B)を引数とした右シーケンス関数right_seq(C)を、右半分の範囲について兄弟ノードSIB(B)を引数とした左シーケンス関数left_seq(D)を、各試行位置毎に呼び出す。
【0088】
右シーケンス関数right_seq(C)について説明を続けると、右シーケンス関数right_seq(C)は、ノードCにマッチする試行位置があればその位置で、左半分の範囲についてノードCを引数とした右リンク関数right_link(C)を呼び出す。ここで、ノードCにマッチする試行位置があればノードCからノードBへの係り受け周辺確率がスコアとして与えられる。ノードCにマッチする試行位置がなければ0が戻される。右シーケンス関数right_seq(C)は、同時に、右半分の範囲については、最右子ノードRCH(C)を引数とした右シーケンス関数right_seq(null)を呼び出す。右シーケンス関数right_seq(null)に対しては、照会パターンの末端まで達したため1が返される。右リンク関数right_link(C)は、対応付けている範囲内で、兄弟ノードSIB(C)および最左子ノードLCH(C)の子孫間を境界する位置を試行し、左半分の範囲について兄弟ノードSIB(C)を引数とした右シーケンス関数right_seq(null)を、右半分の範囲について最左子ノードLCH(C)を引数とした左シーケンス関数left_seq(null)を、それぞれ試行位置毎に呼び出す。右シーケンス関数right_seq(null)および左シーケンス関数left_seq(null)に対しては、照会パターンの末端まで達したため1が返される。上述した処理は、左シーケンス関数left_seq(D)についても同様である。
【0089】
さらに図16中に吹き出しで、照会パターンのノードA’とノードB’との間にノードA’の兄弟ノードであるノードE’が存在する場合は、上記左リンク関数left_link(A)は、対応付けている範囲内で、最右子ノードRCH(A)および兄弟ノードSIB(A)の子孫間を境界する位置を試行し、左半分の範囲について最右子ノードRCH(A)を引数とした右シーケンス関数right_seq(null)を、右半分の範囲について兄弟ノードSIB(A)を引数とした左シーケンス関数left_seq(E)を各試行位置毎に呼び出す。左シーケンス関数left_seq(E)については、上記と同様であり、ノードEにマッチする試行位置が見つかった段階でノードE’からノードBへの係り受け周辺確率がスコアとして与えられ返される。
【0090】
上述したような再帰的な呼び出しを繰り返すことによって、照会パターンの各末端を対応付けた段階でその系列の再帰的な呼び出しを終了し、各部分演算における係り受け周辺確率の積の最大値が戻されていく。最終的に、最適なマッチングmでのパターン周辺確率を近似する最大化された係り受け周辺確率の積が、左シーケンス関数left_seq(root)に返される。
【0091】
図15および図16に示すような再帰的な呼び出しを相互に行うことによって、照会パターンの全体構造から末端のノードの対応付けまでが行われ、局所最大の周辺確率を与える各マッチング位置が検索され、大域的最大となるパターン周辺確率の近似値を与える最適なマッチング列mが決定され、同時に、大域的最大となるパターン周辺確率が近似計算される。
【0092】
なお、上述までは、解析対象の文に対するマッチング・スコアの演算処理について説明してきた。以下、上記マッチング・スコアの演算処理組み込んで、係り受け構造を考慮した情報検索を行う情報検索システムについて説明する。図17は、第1の実施形態によるマッチング・スコア演算機能を組み込んだ情報検索システムの機能ブロック図である。図17に示す情報検索システムを構成する検索エンジン190は、同様に、コンピュータ装置上に実現される。検索エンジン190は、ユーザとの入出力のインタフェースとなる検索インタフェース192と、上述までの入力部110と、スコア演算部120と、出力部140とを含む。さらに、情報検索システムは、検索対象の文書を格納する文書データベース194を含み、検索エンジン190は、文書データベース194にアクセス可能とされている。なお、各文書は、1以上の文を含み、各文書と各文との関係、例えば文書内の文の位置などは、予め対応付けられているものとする。同様に、各文は、予め形態素解析などの文字列解析が実施されており、文節または単語の列として構成され、係り受け周辺確率のデータも与えられているものとする。
【0093】
検索インタフェース192は、ユーザから、照会パターンを規定する検索クエリと、必要に応じて条件とを含むユーザ入力196を取得する。条件は、検索結果に含めるマッチング・スコアに対する閾値、その他文書の検索範囲を指定したりするための条件を含む。なお、条件は、ユーザから与えられてもよいし、システムのデフォルト値として与えられてもよい。検索クエリは、照会パターンを規定するパターン列pおよびその親子関係を定義するpar(p,i)を直接与えてもよいし、所定のフォーマットに従って記述された文字列を解釈して照会パターンのパターン列pおよびpar(p,i)を与えてもよし、さらに予め照会パターンを記述したファイルなどがあれば、そのファイル名等で与えてもよい。
【0094】
検索インタフェース192は、ユーザ入力196を受け取ると、照会パターンと検索範囲の文集合の各文を指定する文識別値を入力部110に渡し、各文のマッチング・スコアの演算を依頼する。入力部110は、解析対象の文を指定する情報に従い、文書データベース194から文およびその係り受け周辺確率のデータを取得して、解析対象の文と、照会パターンと、係り受け周辺確率とを入力データとしてスコア演算120に渡す。あるいは、他の実施形態では、検索インタフェース192は、文書データベース194から解析対象の文およびその係り受け周辺確率のデータを取得して、直接入力部110に渡して、各文のマッチング・スコアの演算を依頼することもできる。
【0095】
スコア演算部120は、与えられた文に対してマッチング・スコアを計算し、出力部140は、与えられた各文に対するマッチング列mおよびスコアを検索インタフェース192に返す。検索インタフェース192は、依頼した各文に対するマッチング・スコアおよびマッチング列を取得すると、ユーザ指定された閾値、またはデフォルトの閾値を基準として、閾値以上のスコアが与えられた文の集合を取得し、検索結果198をユーザに提示する。ここで、閾値のレベルを調整することで、情報検索における適合率および再現率を調整することが可能となる。これにより、より適合率を高めて正確な評判情報を取得したり、再現率を高めて製品の不具合を示す全ての文を網羅して取得したりすることができる。
【0096】
また、文書と文との関係が予め対応付けられてれば、例えばマッチした文書のサマリや、文書内のマッチした箇所周辺のサマリ上で、マッチングした箇所を強調表示することができる。さらに他の実施形態では、文書等の文集合内の各文にわたるスコアの総和を求めることもできる。これにより、例えば製品の不具合を示す文がどの程度存在するのかを知ることができるようになる。
【0097】
以上説明した第1の実施形態によれば、係り受け構造を有する照会パターンに対する文のマッチングの程度を指標し、確率として取り扱うことができるパターン周辺確率を効率的に近似計算することができる。上述したようにパターン周辺確率は、全解析候補中のパターンを部分木として含む構文木の解析候補が生成される周辺確率であり、全解析候補中のパターンを部分木として含む構文木解析候補の解析確率の総和に一致する。したがって、従来では、全解析候補を列挙し、パターンマッチングにより照会パターンにマッチする構文木の候補を抽出し、その候補の解析確率の総和を求める必要があった。この場合、解析候補が文長に対して指数的に増大してしまうため、計算量的に困難があり、現実的ではなかった。
【0098】
これに対して本発明の第1の実施形態によるコンピュータ装置100では、パターン周辺確率を上記解析対象の文の文節ペア間に与えられる係り受け周辺確率の積で近似し、動的計画法を適用することによって、全解析候補を列挙することなく効率的に近似計算することができる。本発明の第1の実施形態による動的計画法が適用されたスコア演算処理では、照会パターンの部分構造と解析対象の文の範囲との対応付けを試行する関数群が再帰的に呼び出され、上記部分演算結果が照会パターンの部分構造および文の範囲の内側に関して再帰的に算出され、これにより、大域的な照会パターンに対するパターン周辺確率が求められる。なお、計算量は、動的計画法が適用でき、演算コストを記憶コストに交換することができるため、文長L、パターンサイズMに対してO(LM)程度で済む。
【0099】
[第2の実施形態]
以下、本発明の第2の実施形態によるマッチング・スコアを演算するコンピュータ装置について説明する。第2の実施形態によるコンピュータ装置は、第1の実施形態で算出したパターン周辺確率に代えて、パターン出現回数期待値をマッチング・スコアとして算出する。図18は、本発明の第2の実施形態によるコンピュータ装置200の機能ブロックを示す。図18に示すコンピュータ装置200は、第1の実施形態と同様の構成を有しているが、入力部210に入力される入力データと、スコア演算部220が備える関数群と、出力部240が出力する演算結果が相違する。
【0100】
本発明の第2の実施形態における入力データは、解析対象の文250と、照会パターン260とを含む点で第1の実施形態と同様であるが、第1の実施形態における係り受け周辺確率p(i,j)に代えて、重みf(i,j)が取得される点で相違する。重みf(i,j)は、第1の実施形態の係り受け周辺確率と同様に、i番目の文節からj番目の文節への係りやすさを指標するものである。重みf(i,j)は、係り受け条件付き対数線形モデルで定義されるものであり、文節iおよび文節j間の特徴ベクトルφ(i,j)と、学習データより推定される重みベクトルwとの内積の指数関数で計算することができる。重みf(i,j)は、統計的構文解析の過程で生成されるデータである。
【0101】
スコア演算部220は、入力部210が取得した入力データを用いて、照会パターン260に対する解析対象の文250のマッチング・スコアを演算する。第2の実施形態においては、解析対象の文250に対し存在可能な全解析候補の中のパターンが出現する回数の期待値、すなわちパターン出現回数期待値をマッチング・スコアとして算出する。パターン出現回数期待値は、本質的には、解析候補の構文木に出現するパターンの総数と、該構文木の解析確率との積の全解析候補にわたる総和に一致する。各解析候補の解析確率Pは、解析候補の構文木に含まれる係り受けペアの上記重みf(i,j)の関数として表される。より具体的には、各解析候補の解析確率Pは、解析候補の構文木に含まれる係り受けペアの重みf(i,j)の積、すなわち下記式(3)で表される。なお、下記式(3)中のZは、分配関数であり、各解析候補の重みfの積を全候補にわたり総和を取った値であり、上記重みfの積を分配関数Zで割ることにより、全候補での総和が1となり、規格化された解析確率として用いることができるようになる。
【0102】
【数3】

【0103】
本発明の第2の実施形態において、マッチング・スコアは、数学的には、以下の式(4)で表す値を求めることになる。下記式(4)は、本実施形態では、第1の実施形態とは異なり、重みf(i,j)が与えられ、外側が第1の実施形態のmax関数ではなくマッチング列mでの総和Σとなっており、分配関数Zも計算可能であるため、最大のスコアを与えるマッチング列mを決定することはできないが、近似なしに確率Pをそのまま計算することができる。また、外側がmについての総和Σとなっているため、照会パターンが解析候補中に出現する事象分だけ確率Pが加算されていき、結果として、解析候補での照会パターンの出現回数とその解析確率との積の総和が求められる。
【0104】
【数4】

【0105】
スコア演算部220は、左右のシーケンス関数222,224、左右のリンク関数226,228および左右のマッチ関数230,232を備えており、これらの関数群を再帰的に呼び出すことで、全解析候補を列挙することなく、上記パターン出現回数期待値を演算する。より具体的には、スコア演算部220は、複数の関数群222〜232を用いて、照会パターン260の部分構造と解析対象の文250の範囲との対応付けを試行し、照会パターンが出現する事象にわたる上記重みの積和の部分演算結果を、上記部分構造および範囲の内側に関して再帰的に算出する。一度計算された部分演算結果は、第1の実施形態と同様に、動的計画テーブル234内に格納され、演算過程で再び必要になった際に、再度演算する代わりに動的計画テーブル234に格納された値が再利用される。第2の実施形態では、照会パターン260の部分構造と解析対象の文250の範囲との対応付けを試行の過程では、パターンの構造が再帰的にたどられていたが、第2の実施形態における対応付けの試行過程では、解析対象の文の構造が再帰的にたどられながら、パターンの構造も再帰的にたどられる。
【0106】
出力部240は、スコア演算部220が算出したパターン出現回数期待値(マッチング・スコア)を含む演算結果280を出力する。第2の実施形態では、マッチング列mの総和が計算されるため、マッチング列mは求められず、上記パターン出現回数期待値のみが演算結果280に含められる。
【0107】
以下、図19〜図23を参照しながら、本発明の第2の実施形態によるマッチング・スコア演算処理について説明する。図19は、本発明の第2の実施形態によるマッチング・スコア演算方法を概念的に説明する図である。本発明の第2の実施形態では、解析対象の文に対してEisner構文木と同様の構文木を考える。図19中の三角形および台形は、それぞれ、1次のEisnerアルゴリズムにおける完全スパンおよび非完全スパンに相当する。さらに図19中の「*」が付された台形は、照会パターンに規定される係り受け関係に対応付けられた文の構文木上の係り受け関係であることを意味している。なお、図18には、構文解析結果の構文木の一例を示すが、実際には、あらゆる構文解析結果に対してマッチング・スコアの総和を計算する。
【0108】
本発明の第2の実施形態では、照会パターンおよび解析対象の文の両方に関して動的計画法を適用し、解析対象の構文木の構築を行うと同時に、照会パターンの部分構造と解析対象の文の範囲との対応付けを試行する。スコア演算部220は、照会パターンのルートノード(全体構造)を上記文の構文木のルートノード(全体範囲)に対応付けるところから開始する。まず、照会パターンの全体構造を表す左向き三角形を、解析対象の文の頭から末尾までの範囲に一旦対応付け、照会パターンのルートノードの最左子ノードLCH(root)から順に対応付けを行う。
【0109】
本発明の実施形態では、上記左向き三角形および右向き三角形は、図18に示した左シーケンス関数222および右シーケンス関数224に対応し、印なし上記左向き台形および右向き台形は、左リンク関数226および右リンク関数228に対応し、「*」印有りの上記左向き台形および右向き台形は、左マッチ関数230および右マッチ関数232に対応する。スコア演算過程では、スコア演算部220は、上記関数群222〜232を再帰的に呼び出して、照会パターンの部分構造と解析対象の文中の範囲との対応付けを試行し、上記台形で表される係り受け関係に対応して重み(i,j)によるスコアを与えるとともに、照会パターンの係り受け関係をマッチする(「*」印有り)か、マッチしない(印なし)かの場合に分けてそれぞれ処理を進め、照会パターンの構造と文の構造との両方を辿りながら、マッチング・スコアを算出する。
【0110】
以下、本発明の第2の実施形態で用いられるシーケンス関数222,224、リンク関数226,228およびマッチ関数230,232について詳細を説明する。図20は、本発明の第2の実施形態における左シーケンス関数を説明する図である。図21は、本発明の第2の実施形態における(A)左リンク関数および(B)左マッチ関数を説明する図である。図22は、本発明の第2の実施形態における(A)左シーケンス関数(B)左リンク関数および(C)左マッチ関数の疑似コードを示す図である。図23は、本発明の第2の実施形態における(A)右シーケンス関数(B)右リンク関数および(C)右マッチ関数の疑似コードを示す図である。
【0111】
図20および図22(A)に示すように、第2の実施形態の左シーケンス関数222は、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、
(1)親ノードPAR(n)がr番目の文節に対応しており、
(2)文の構文木上でのPAR(n)の左子孫末端がlで、したがってnとその子孫はl,…r−1の範囲に存在し、
(3)注目ノードnがPAR(n)の左側に存在する
ときの当該文の範囲における重みの積の総和を出力する関数である。つまり、左シーケンス関数222は、注目ノードnに関し、注目ノードnの親ノードPAR(n)の左子孫末端と親ノードPAR(n)との間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。
【0112】
左シーケンス関数222は、上記照会パターンの部分構造および上記文の範囲について内側の構造を探索するために、上述した条件(2)により、範囲l,…,r−1のいずれかに対し、文の構文木上の親ノードPAR(n)の最左子ノード(最左子ノードがパターン上の注目ノードnにマッチする場合もあり、マッチしない場合もある。)の対応付けを試行する。試行位置を変数iで表すと、このとき文中のi番目→r番目の文節ペア間に親ノードPAR(n)の最左子ノードから親ノードPAR(n)への係り受け関係が試行され、重みf(i,r)が与えられる。なお、ここでいう試行位置iは、照会パターン上の最左子ノードではなく、文の構文木上での親ノードPAR(n)の最左子ノード(注目ノードnにマッチする場合には、パターン上の最左子ノードにも一致する。)の位置である点に留意されたい。
【0113】
注目ノードnが、親ノードPAR(n)の最左子ノードが対応付けられている文節xにマッチする場合(図20(A))、注目ノードnの最右子ノードRCH(n)およびその子孫、並びに兄弟ノードSIB(n)およびその子孫たちは、非交差条件により、範囲i+1,…,r−1に存在し得るので、詳細を後述する左マッチ関数230を再帰的に呼び出す。同時に、注目ノードnの最左子ノードLCH(n)およびその子孫は、範囲l,…,i−1に存在し得るので、LCH(n)と、変数lと、変数iとを引数として与えて左シーケンス関数222を再帰的に呼び出す。
【0114】
一方、注目ノードnが、親ノードPAR(n)の最左子ノードが対応付けられている文節xにマッチしない場合(図20(B)。マッチさせない場合を含む。)は、注目ノードnおよびその子孫たちは、範囲i+1,…,r−1に存在し得るので、詳細を後述する左リンク関数226を再帰的に呼び出す。残りに対応するパターン要素は無いので、範囲l,…,i−1については、nullと、変数lと、変数iとを引数として与えて左シーケンス関数222を呼び出す。
【0115】
図22(A)で示す疑似コードのように、左シーケンス関数left_seq_e()は、注目ノードnがマッチする各試行位置iについて、試行位置iの左半分および右半分の範囲に関して、着目している照会パターンの構造の内側の次の部分構造に進め、対応付けを試行する左シーケンス関数222および左マッチ関数230を再帰的に呼び出す。左シーケンス関数left_seq_e()は、再帰的に呼び出された左シーケンス関数222および左マッチ関数230から戻された各部分演算結果と、上記与えられた重みf(i,r)との積を計算し、部分スコアに加算する。本実施形態では、さらに、左シーケンス関数left_seq_e()は、各試行位置iについて、試行位置iの左半分の範囲に関して、nullを与えて左シーケンス関数222を呼び出すとともに、試行位置iの右半分の範囲に関して、着目している照会パターンの部分構造のまま、対応付けを試行する左リンク関数226を再帰的に呼び出す。左シーケンス関数left_seq_e()は、各試行位置iについて、左シーケンス関数222から戻された部分演算結果(1である)と、再帰的に呼び出された左リンク関数226から戻された部分演算結果と、上記与えられた重みf(i,r)との積を計算し、部分スコアに加算し、部分演算結果として呼び出し元に返す。
【0116】
左リンク関数226は、図21(A)および図22(B)に示すように、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、
(1)親ノードPAR(n)がr番目の文節に対応しており、
(2)文の構文木上でのPAR(n)の最左子ノードがl番目の文節に対応しており、かつ、注目ノードnとマッチしておらず、
(3)文の構文木上でのPAR(n)の最左子ノード(l番目の文節)の右子孫と、最左子ノードの兄弟とが、非交差条件より、l+1,…,r−1の間に存在し、
(4)注目ノードnがPAR(n)の左側に存在する
ときの当該文の範囲における重みの積の総和を出力する関数である。つまり、左リンク関数226は、注目ノードnに関し、親ノードPAR(n)の最左子ノードの左側末端と親ノードPAR(n)との間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。
【0117】
非交差条件により、最左子ノードの右子孫と、最左子ノードの兄弟ノードの子孫とは隣り合っている。そこで、左リンク関数226は、最左子ノードの右子孫の右側末端と、最左子ノードの兄弟ノードの子孫左側末端との境界を(i,i+1)の位置で試行する。
【0118】
そして、最左子ノードの兄弟の子孫は、i+1,…,r−1の間に存在し得るので、左リンク関数226は、ここに注目ノードnを対応させて、注目ノードnと、変数i+1と変数rとを引数として与えて左シーケンス関数222を再帰的に呼び出す。一方、最左子ノードの右子孫はl+1,…,i−1に存在し得るが、ここに対応させる照会パターンのノードは無いので、nullと、変数lと変数iとを引数として与えて、右シーケンス関数224を呼び出す。図22(B)で示す疑似コードのように、左リンク関数left_link_e()は、各試行位置iについて、右シーケンス関数224の部分演算結果と、再帰的に呼び出された左シーケンス関数222から戻された部分演算結果の積を計算し、部分スコアに加算し、部分演算結果として呼び出し元に返す。
【0119】
左マッチ関数230は、図21(B)および図22(C)に示すように、照会パターンのノードnと、解析対象の文の範囲における開始位置を示す変数lと、終了位置を示す変数rとを引数として受け取り、
(1)親ノードPAR(n)がr番目の文節に対応しており、
(2)文の構文木上でのPAR(n)の最左子ノードがl番目の文節に対応しており、かつ、注目ノードnとマッチしており、
(3)文の構文木上でのPAR(n)の最左子ノードの右子孫と、最左子ノードの兄弟とが、非交差条件より、l+1,…,r−1の間に存在し、
(4)注目ノードnがPAR(n)の左側に存在する
ときの当該文の範囲における重みの積の総和を出力する関数である。つまり、左マッチ関数230は、注目ノードnに関し、注目ノードnの左側末端と親ノードPAR(n)との間の部分構造を、変数lおよび変数rで規定される文の範囲に対応付けする関数である。
【0120】
非交差条件により、最左子ノードの右子孫と、最左子ノードの兄弟ノードの子孫とは隣り合っている。そこで、左マッチ関数230は、最左子ノードの右子孫の末端と、最左子ノードの兄弟ノードの子孫左側末端との境界を(i,i+1)の位置で試行する。そして、最左子ノードの右子孫は、l+1,…,iの間に存在し得るので、左マッチ関数230は、ここに最右子ノードRCH(n)を対応させて、最右子ノードRCH(n)と、変数lと変数iとを引数として与えて右シーケンス関数224を再帰的に呼び出す。同時に、最左子ノードの兄弟の子孫は、i+1,…,r−1の間に存在し得るので、左マッチ関数230は、ここに兄弟ノードSIB(n)を対応させて、兄弟ノードSIB(n)と、変数i+1と変数rとを引数として与えて左シーケンス関数222を再帰的に呼び出す。図22(C)で示す疑似コードのように、左マッチ関数left_match_e()は、各試行位置iについて、再帰的に呼び出された右シーケンス関数224および左シーケンス関数222から戻された各部分演算結果の積を計算し、部分スコアに加算し、部分演算結果として呼び出し元に返す。
【0121】
なお、右シーケンス関数224、右リンク関数228および右マッチ関数232については、図23(A)、(B)および(C)にそれぞれ疑似コードが示されており、上述までの左シーケンス関数222、左リンク関数226および左マッチ関数230についての説明や、第1の実施形態での説明から容易に理解できるため、詳細な説明は割愛する。
【0122】
図24は、上記左右のシーケンス関数、左右のリンク関数および左右のマッチ関数の相互再帰的な呼び出しを説明する図である。マッチング・スコア演算処理は、メインルーチンから、照会パターンの構文木のルートノード(全体構造を表す。)と解析対象の文の全範囲とを引数として左シーケンス関数left_seq_e()が呼び出されて開始する。
【0123】
左シーケンス関数left_seq_e(n,l,r)は、ノードnにマッチする場合として、ノードnにマッチする各試行位置iで、現在対応付けを行っている範囲(l,…,r)を分割し、親反対側の左半分の範囲(l,…,i)について順方向の左シーケンス関数left_seq_e(LCH(n),l,i)を再帰的に呼び出すとともに、親側の右半分の範囲(i,…,r)について順方向の左マッチ関数left_match_e(n,i,r)を再帰的に呼び出す。左シーケンス関数left_seq_e(n,l,r)は、さらにノードnにマッチしない場合として、各試行位置iで現在対応付けを行っている範囲(l,…,r)を分割し、親反対側の左半分の範囲(l,…,i)について順方向の左シーケンス関数left_seq_e(null,l,i)を再帰的に呼び出すとともに、親側の右半分の範囲(i,…,r)について順方向の左リンク関数left_link_e(n,i,r)を再帰的に呼び出す。
【0124】
左リンク関数left_link_e(n,l,r)は、各試行位置iで現在対応付けを行っている範囲(l,…,r)を分割し、親反対側の左半分の範囲(l,…,i)について逆方向の右シーケンス関数right_seq_e(null,l,i)を再帰的に呼び出し、親側の右半分の範囲(i+1,…,r)について順方向の左シーケンス関数left_seq_e(n,i+1,r)を再帰的に呼び出す。一方、左マッチ関数left_match_e(n,l,r)は、各試行位置iで現在対応付けを行っている範囲(l,…,r)を分割し、親反対側の左半分の範囲(l,…,i)について、逆方向の右シーケンス関数right_seq_e(RCH(n),l,i)を再帰的に呼び出し、親側の右半分の範囲(i+1,…,r)について順方向の左シーケンス関数left_seq_e(SIB(n),i+1,r)を再帰的に呼び出す。
【0125】
右シーケンス関数right_seq_e(n,l,r)は、ノードnにマッチする場合として、ノードnにマッチする各試行位置iで範囲を分割し、親側の左半分の範囲(l,…,i)について順方向の右マッチ関数right_match_e(n,l,i)を再帰的に呼び出すとともに、親反対側の右半分の範囲(i,…,r)について順方向の右シーケンス関数right_seq_e(RCH(n),i,r)を再帰的に呼び出す。右シーケンス関数right_seq_e(n,l,r)は、さらにノードnにマッチしない場合として、各試行位置iで範囲(l,…,r)を分割し、親側の左半分の範囲(l,…,i)について、順方向の右リンク関数right_link_e(n,l,i)を再帰的に呼び出すとともに、親反対側の右半分の範囲(i,…,r)について順方向の右シーケンス関数right_seq_e(null,i,r)を再帰的に呼び出す。
【0126】
右リンク関数right_link_e(n,l,r)は、各試行位置iで範囲(l,…,r)を分割し、親側の左半分の範囲(l,…,i)について順方向の右シーケンス関数right_seq_e(n,l,i)を再帰的に呼び出し、親反対側の右半分の範囲(i+1,…,r)について逆方向の左シーケンス関数left_seq_e(null,i+1,r)を再帰的に呼び出す。右マッチ関数right_match(n,l,r)は、各試行位置iで現在の範囲を分割し、親側の左半分の範囲(l,…,i)について順方向の右シーケンス関数rihgt_seq_e(SIB(n),l,i)を再帰的に呼び出し、親反対側の右半分の範囲(i+1,…,r)について逆方向の左シーケンス関数left_seq_e(LCH(n),i+1,r)を再帰的に呼び出す。
【0127】
図24に示すような再帰的な呼び出しを相互に行うことによって、解析対象の文の構文木を構築するとともに、照会パターンの全体構造から末端のノードまでの対応付けが行われ、照会パターンが構文木中に出現する事象を数え上げながら、構文木での照会パターンの出現回数とその解析確率と積の総和であるパターン出現回数期待値が計算される。なお、得られる重みf(i,j)の積は、そのままでは、規格化されておらず、確率として取り扱うことができない。そこで、上記マッチング・スコアの計算過程で同時に求められる全解析候補にわたる規格化されていない確率の総和Zで割り、重みf(i,j)の積を確率として扱う形に処理することが好ましい。
【0128】
以上説明した第2の実施形態によれば、係り受け構造を有する照会パターンに対する文のマッチングの程度を指標するパターン出現回数期待値を、効率的に近似なしに計算することができる。上述したようにパターン出現回数期待値は、全解析候補中のパターンが出現する出現回数の期待値であり、解析候補中のパターンの出現回数とその解析確率との積の全解析候補にわたる総和に一致する。したがって、従来では、全解析候補を列挙し、パターンマッチングにより照会パターンにマッチする構文木の候補を抽出するとともにマッチする回数を計数し、その候補の解析確率とマッチ回数と積の総和を求める必要があった。この場合、解析候補が文長に対して指数的に増大してしまうため、計算量的に困難があり、現実的ではなかった。
【0129】
これに対して本発明の第2の実施形態によるコンピュータ装置200では、解析候補の確率を上記解析対象の文の文節ペア間に与えられる重みの積に比例する関数で表し、動的計画法を適用することによって、全解析候補を列挙することなく効率的に近似なしに、パターン出現回数期待値を計算することができる。本発明の第2の実施形態による動的計画法が適用されたスコア演算処理では、照会パターンの部分構造と解析対象の文の範囲との対応付けを試行し、同時に解析対象の文の構造を探索する関数群が再帰的に呼び出され、上記部分演算結果が照会パターンの部分構造および文の範囲の内側に関して再帰的に算出され、これにより、パターン出現回数期待値が求められる。なお、計算量は、動的計画法が適用でき、演算コストを記憶コストに交換することができるため、文長L、パターンサイズMに対してO(LM)程度で済む。なお、上述までは、解析対象の文に対するマッチング・スコアの演算処理について説明してきたが、第1の実施形態と同様に、上記マッチング・スコアの演算処理組み込んで、係り受け構造を考慮した情報検索や情報抽出を行うこともできる。
【0130】
[実験]
1.コンピュータにおける実装
クロック数3.0GHzのマルチコア・プロセッサ(インテル(登録商標)Core(登録商標)2Duo)と2GBのRAMを備えるThinkStation(登録商標)を用いて、本発明の第1実施形態によるマッチング・スコア演算のプログラムを実装するコンピュータ・システムを実装した。このコンピュータ・システムのオペレーティング・システムは、WINDOWS(登録商標)XPとした。上記プログラムは、Java(登録商標)のプログラミング言語によって記述した。
【0131】
2.実験結果
2.1.実験例1および比較例1
解析対象データとして毎日新聞(登録商標)の95年データを用い、照会パターンは、「首相…発言…[動詞]」(首相と発言とが[動詞]に係っていることを意味する。)を用いた。マッチング・スコアとしてパターン周辺確率を用いて、上記解析対象データの各文に対してマッチング・スコア演算プログラムを適用し、マッチング・スコア順にソートし、上位k件のFalse−PositiveおよびTrue−positiveの件数をプロットし、ROC(Receiver Operating Characteristic)グラフを作成した。なお、図25は、実験例1の結果および1ベスト法による比較例1の結果を示す。
【0132】
図25に示すように、人手で与えられる正解18件中、1ベスト法の比較例では、3件が解析誤りのため検出できず15件のみ検出し、16件の誤検出があったのに対し、実験例1では、上位51件で全ての正解を網羅することができ、上位12件目では10件(約8割)が正解し、高い適合率が得られた。
【0133】
2.2.実験例2および比較例2〜4
解析対象データとして同じく毎日新聞(登録商標)の95年データを用い、照会パターンは、「首相…選挙…[動詞]」(首相と選挙とが[動詞]に係っていることを意味する。)を用いた。マッチング・スコアとしてパターン周辺確率を用いて、上記解析対象データの各文に対してマッチング・スコア演算のプログラムを適用し、マッチング・スコア順にソートし、上位k件のFalse−PositiveおよびTrue−Positiveの件数をプロットし、ROCグラフを作成した。なお、図26(A)は、実験例2の結果および1ベスト法による比較例2の結果を示す。図26(B)は、実験例2の結果および5ベスト法による比較例3の結果を示す。図26(C)は、実験例2の結果および10ベスト法による比較例4の結果を示す。なお、上記条件では、単純な文字列一致の場合302件ヒットした。また、Nベスト法では、出力されたN個の構文木それぞれとマッチングを行い、マッチした構文木のスコアの総和をマッチング・スコアとした。さらに、上記Nベストのマッチング・スコアを、N個の構文木のスコアの総和で割り、正規化したものを比較例3’、比較例4’で示す。
【0134】
図26に示すように、人手で与えられる正解34件中、1ベスト法の比較例2では、10件は解析誤りのため検出できず24件のみ検出し、16件の誤検出があった。また5ベスト法の比較例3では、4件の正解が見つからず、また10ベスト法の比較例4では、1件の正解が見つからなかった。これに対し、実験例2では、上位55件で全ての正解を網羅することができた。
【0135】
2.3.実験例3および比較例5〜7
解析対象データとして同じく毎日新聞(登録商標)の95年データを用い、照会パターンは、「首相(…の…に)…を…[動詞]」(「…の」が「…に」に係り、「首相」、「…に」、「…を」は[動詞]に係っていることを意味する。)を用いた。マッチング・スコアとしてパターン周辺確率を用いて、上記データの各文に対してマッチング・スコア演算のプログラムを適用し、マッチング・スコア順にソートし、上位k件のFalse−PositiveおよびTrue−Positiveの件数をプロットし、ROCグラフを作成した。なお、図27(A)は、実験例3の結果および1ベスト法による比較例5の結果を示す。図27(B)は、実験例2の結果および5ベスト法による比較例6の結果を示す。図27(C)は、実験例2の結果および10ベスト法による比較例7の結果を示す。なお、単純な文字列一致の場合2054件ヒットした。Nベストの比較例6および比較例7のマッチング・スコアを正規化したものを比較例6’、比較例7’で示す。
【0136】
図27に示すように、人手で与えられる正解80件中、1ベスト法の比較例5では、10件は解析誤りのため検出できず70件のみ検出し、25件の誤検出があった。また5ベスト法の比較例6では、4件の正解が見つからず、また10ベスト法の比較例7では、2件の正解が見つからなかった。これに対して、実験例3では、上位149件で、正解の80件全てを網羅することができた。さらに、1ベスト法の比較例5では、上位20件中4件が誤りであるのに対し、実験例3では、上位20件が全て正解であった。上位側で、5ベストおよび10ベストに比較して高い正解率が得られた。また、正規化すると、比較例6’および比較例7’ともに、上位のスコアが1につぶれてしまい、順位付けができなくなった。
【0137】
図25〜図27に示す実験結果から、本発明のマッチング・スコアの演算処理は、従来の1ベスト法、Nベスト法を用いる場合に比べて、再現性が高く、再現性および適合率を調整することが可能であることが示された。また、検索結果のスコアがばらつき、再現性および適合率を好適に調整することが可能であることが示された。
【0138】
以上説明したように、本発明の実施形態によれば、係り受け構造を有する照会パターンに対する文のマッチング・スコアを、文の構文解析候補を全列挙することなく算出し、情報検索および情報抽出における適合率および再現率を所望のレベルで調整可能とし、ひいては構文解析誤りに高い堅牢性を実現することができる、情報処理装置、自然言語解析方法、プログラムおよび記録媒体を提供することが可能となる。
【0139】
なお、本発明につき、発明の理解を容易にするために各機能部および各機能部の処理を記述したが、本発明は、上述した特定の機能部が特定の処理を実行するほか、処理効率や実装上のプログラミングなどの効率を考慮して、いかなる機能部に、上述した処理を実行するための機能を割当てることができる。
【0140】
また、本発明では、好適に適用できる言語としては、上記例示した日本語、英語の他、中国語、アラビア語、ドイツ語、フランス語、ロシア語、韓国語など、上述した以外の言語についても適用可能である。
【0141】
本発明の上記機能は、C++、Java(登録商標)、Java(登録商標)Beans、Java(登録商標)Applet、Java(登録商標)Script、Perl、Python,Rubyなどのオブジェクト指向プログラミング言語などで記述された装置実行可能なプログラムにより実現でき、装置可読な記録媒体に格納して頒布または伝送して頒布することができる。
【0142】
これまで本発明を、特定の実施形態をもって説明してきたが、本発明は、実施形態に限定されるものではなく、他の実施形態、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用・効果を奏する限り、本発明の範囲に含まれるものである。
【符号の説明】
【0143】
100,200…コンピュータ装置、110,210…入力部、120,220…スコア演算部、122,222…左シーケンス関数、124,224…右シーケンス関数、126,226…左リンク関数、128,228…右リンク関数、130…動的計画テーブル、140,240…出力部、150,250…解析対象の文、160,260…照会パターン、170…係り受け周辺確率、180,280…演算結果、190…検索エンジン、192…検索インタフェース、194…文書データベース、196…ユーザ入力、198…検索結果、230…左マッチ関数、232…右マッチ関数、234…動的計画テーブル、270…重み

【特許請求の範囲】
【請求項1】
パターンに対する文のマッチングのスコアを算出する情報処理装置であって、
解析対象の文と、該文内の言語単位間の係り易さを指標する指標値と、照会パターンとを入力として取得する入力部と、
前記文が前記照会パターンにマッチする程度を指標するマッチングのスコアを、前記照会パターンに含まれる各係り受け関係が対応付けられる各指標値を少なくとも変数とする関数で表して、演算するスコア演算部と
を含み、
前記スコア演算部は、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用するため記憶領域に格納しながら、前記部分構造および前記範囲の内部に関して再帰的に演算することによって、前記スコアを算出する、情報処理装置。
【請求項2】
前記マッチングのスコアを表す関数は、前記対応付けられる各指標値の積を含む関数であり、
前記関数の部分演算結果は、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値の積を含む関数で表される部分スコアであり、
前記スコア演算部は、前記再帰的な演算によって前記照会パターンの構造を辿る、請求項1に記載の情報処理装置。
【請求項3】
前記指標値は、前記文内の各言語単位間の係り受け周辺確率であり、
前記マッチングのスコアは、前記文に対する解析候補中の前記照会パターンを部分木として有する候補が生成されるパターン周辺確率であり、
前記マッチングのスコアを表す関数は、前記対応付けられる各係り受け周辺確率の積であり、前記パターン周辺確率を近似し、
前記部分スコアは、前記部分構造内の各係り受け関係に対応付けられる各係り受け周辺確率の積の局所最大値であり、
前記スコア演算部は、前記再帰的な演算によって、前記照会パターンの構造を辿りながら、前記パターン周辺確率を大域的に最大化することを特徴とする、請求項2に記載の情報処理装置。
【請求項4】
前記指標値は、前記文内の各言語単位ペア間の係り易さを指標する重みであり、
前記マッチングのスコアは、前記文に対する解析候補中の前記照会パターンが部分木として出現する見込みを意味するパターン出現回数期待値であり、
前記マッチングのスコアを表す関数は、前記照会パターンが出現する解析候補に含まれる各係り受け関係の各重みの積を規格化して該解析候補の確率を表し、前記照会パターンが出現する解析候補にわたる該解析候補の確率と出現回数との積の総和であり、
前記部分スコアは、前記文の範囲内側の各対応付けの組み合わせにわたる前記各重みの積の総和であり、
前記スコア演算部は、前記再帰的な演算によって、前記照会パターンの構造および前記文の構造を辿りながら、前記照会パターンが出現する事象を数え上げ、前記照会パターンが出現した解析候補の確率を加算して、前記パターン出現回数期待値を算出することを特徴とする、請求項2に記載の情報処理装置。
【請求項5】
前記照会パターンは、言語単位にマッチさせるノードと係り受け関係を表すエッジとからなる木構造を構成し、前記スコア演算部は、前記再帰的な演算を行うための関数群として、
前記照会パターン内の第1注目ノードの子孫親反対側末端と親ノードと間の部分構造を文の第1範囲に対応付けて、前記第1注目ノードをマッチさせ得る各試行位置に関して、該試行位置から前記親ノードの位置への係り受け関係に対応付けられる前記指標値を与えるとともに、前記第1範囲内の該試行位置を境界とした親反対側範囲について順方向の第1型関数を再帰的に呼び出し、全試行位置にわたる前記部分スコアを出力する前記第1型関数を含む、請求項2に記載の情報処理装置。
【請求項6】
前記スコア演算部は、前記再帰的な演算を行うための関数群として、さらに、
前記照会パターン内の第2注目ノードと親ノードとの間の部分構造を文の第2範囲に対応付けて、前記第2注目ノードの親側末端の子ノードと兄弟ノードとの子孫間を境界させる各試行位置に関して、前記第2範囲内の該試行位置を境界とした親反対側範囲について逆方向の前記第1型関数を再帰的に呼び出し、前記第2範囲内の該試行位置を境界とした親側範囲について順方向の前記第1型関数を再帰的に呼び出し、全試行位置にわたる部分スコアを出力する第2型関数を含み、
前記第1型関数は、前記順方向の第1型関数の呼び出しとともに、前記第1範囲の前記試行位置を境界とした親側範囲について順方向の前記第2型関数を再帰的に呼び出すことを特徴とする、請求項5に記載の情報処理装置。
【請求項7】
前記第1型関数は、前記順方向の第1型関数の呼び出しの際に前記第1注目ノードの親反対側末端の子ノードを与え、前記順方向の第2型関数の呼び出しの際に当該第1注目ノードを与え、
前記第2型関数は、前記逆方向の第1型関数の呼び出しの際に前記第2注目ノードの親側末端の子ノードを与え、前記順方向の第1型関数の呼び出しの際に前記第2注目ノードの兄弟ノードを与えることを特徴とする、請求項6に記載の情報処理装置。
【請求項8】
前記スコア演算部は、前記再帰的な演算を行うための関数群として、さらに、
前記照会パターン内の第3注目ノードの親ノード子孫末端と該親ノードとの間の部分構造を文の第3範囲に対応付けて、前記第3注目ノードの子孫の親反対側末端を境界させる各試行位置に関して、前記第3範囲の試行位置を境界とした親側範囲について順方向の前記第1型関数を再帰的に呼び出し、全試行位置にわたる部分スコアを出力する第3型関数を含み、
前記第1型関数は、前記第1注目ノードがマッチしない場合の各試行位置に関して、前記第1範囲内の該試行位置を境界とした親側範囲について順方向の前記第3型関数を再帰的に呼び出すことを特徴とする、請求項6に記載の情報処理装置。
【請求項9】
前記第1型関数は、前記順方向の第1型関数の呼び出しの際に前記第1注目ノードの親反対側末端の子ノードを与え、前記順方向の第2型関数の呼び出しの際に当該第1注目ノードを与え、
前記第2型関数は、前記照会パターンの部分構造の内側に処理を進めて、前記逆方向の第1型関数の呼び出しの際に前記第2注目ノードの親側末端の子ノードを与え、前記順方向の第1型関数の呼び出しの際に前記第2注目ノードの兄弟ノードを与え、
前記第3型関数は、前記照会パターンの部分構造の内側に処理を進めず、前記順方向の第1型関数の呼び出しの際に前記第3注目ノードを与えることを特徴とする、請求項8に記載の情報処理装置。
【請求項10】
前記関数群は、それぞれ、前記照会パターンの部分構造の右端に注目ノードの親ノードが位置する左方向関数と、前記照会パターンの部分構造の左端に注目ノードの親ノードが位置する右方向関数とを含む、請求項5に記載の情報処理装置。
【請求項11】
前記解析対象の文は、複数の文からなる文集合の各要素として与えられ、
検索依頼に応答して、前記文集合の要素のうち、該要素に対して取得されたマッチングのスコアが検索条件を満たすものを検索結果として出力する情報検索インタフェースをさらに含むことを特徴とする、請求項1に記載の情報処理装置。
【請求項12】
前記情報検索インタフェースは、前記検索条件を受け付けることを特徴とする、請求項11に記載の情報処理装置。
【請求項13】
前記解析対象の文は、複数の文からなる文集合の各要素として与えられ、
前記文集合の各要素に対して取得されたマッチングのスコアの総和を求めて出力する機能部をさらに含むことを特徴とする、請求項1に記載の情報処理装置。
【請求項14】
前記解析対象の文は、非交差であり、双方向または単方向であり、前記照会パターンは、非交差係り受け木の部分木である、請求項1に記載の情報処理装置。
【請求項15】
パターンに対する文のマッチングのスコアを算出する情報処理装置であって、
解析対象の文と、該文内の各言語単位間の係り受け周辺確率と、照会パターンとを入力として取得する入力部と、
前記文に対する解析候補中の前記照会パターンを部分木として有する候補が生成されるパターン周辺確率を、前記照会パターンに規定される各係り受け関係が対応付けられる各係り受け周辺確率の関数で表して、前記スコアとして演算するスコア演算部と
を含み、
前記スコア演算部は、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用のため記憶領域に格納しながら前記部分構造および前記範囲の内側に関して再帰的に演算することによって、前記パターン周辺確率を算出する、情報処理装置。
【請求項16】
前記パターン周辺確率を表す関数は、前記各係り受け周辺確率の積であり、前記パターン周辺確率を近似し、
前記関数の部分演算結果は、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係が対応付けられる各係り受け周辺確率の積の局所最大値であり、
前記スコア演算部は、前記再帰的な演算によって前記パターン周辺確率を大域的に最大化することを特徴とする、請求項15に記載の情報処理装置。
【請求項17】
パターンに対する文のマッチングのスコアを算出する情報処理装置であって、
解析対象の文と、該文内の各言語単位間の係り易さを指標する重みと、照会パターンとを入力として取得する入力部と、
前記文に対する解析候補中の前記照会パターンが部分木として出現するパターン出現回数期待値を、前記照会パターンが出現する候補に含まれる各係り受け関係の各重みを変数とする関数で表して、前記スコアとして演算するスコア演算部と
を含み、
前記スコア演算部は、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用するため記憶領域に格納しながら前記部分構造および前記範囲の内部に関して再帰的に算出することによって、前記パターン出現回数期待値の演算する、情報処理装置。
【請求項18】
前記パターン出現回数期待値を表す関数は、前記照会パターンが出現する解析候補に含まれる各係り受け関係の各重みの積を規格化して該解析候補の確率を表し、前記照会パターンが出現する解析候補にわたる該解析候補の確率と出現回数との積の総和であり、
前記関数の部分演算結果は、前記文の範囲内側の各対応付けの組み合わせにわたる前記各重みの積の総和であり、
前記スコア演算部は、前記再帰的な演算によって前記照会パターンが出現する事象を数え上げながら、前記照会パターンが出現した解析候補の確率を加算して、前記パターン出現回数期待値を算出することを特徴とする、請求項17に記載の情報処理装置。
【請求項19】
コンピュータ・システムが実行する、係り受け構造を有するパターンに対する自然言語で記述された文のマッチングのスコアを算出する自然言語解析方法であって、
コンピュータ・システムが、解析対象の文と、該文内の言語単位間の係り易さを指標する指標値と、照会パターンとを入力として取得し、記憶領域に記憶するステップと、
コンピュータ・システムが、前記文が前記照会パターンにマッチする程度を指標するマッチングのスコアを、前記照会パターンに含まれる各係り受け関係が対応付けられる各指標値を少なくとも変数とする関数で表して、プロセッサにより演算するステップと
を含み、
前記演算するステップは、
前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用するため記憶領域に格納しながら演算するサブステップを前記部分構造および前記範囲の内部に関して再帰的に呼び出すステップを含む、自然言語解析方法。
【請求項20】
前記マッチングのスコアを表す関数は、前記対応付けられる各指標値の積を含む関数であり、
前記関数の部分演算結果は、前記照会パターンの部分構造を前記文の範囲に対応付けたときの該部分構造内の各係り受け関係に対応付けられる各指標値の積を含む関数で表される部分スコアであり、
前記再帰的に呼び出すステップにより、前記照会パターンの構造が辿られることを特徴とする、請求項19に記載の自然言語解析方法。
【請求項21】
コンピュータ・システム上に、パターンに対する文のマッチングのスコアを算出する情報処理装置を実現するためのコンピュータ実行可能なプログラムであって、前記コンピュータ・システムを、
解析対象の文と、該文内の言語単位間の係り易さを指標する指標値と、照会パターンとを入力として取得する入力部、および
前記文が前記照会パターンにマッチする程度を指標するマッチングのスコアを、前記照会パターンに含まれる各係り受け関係が対応付けられる各指標値を少なくとも変数とする関数で表して、演算するスコア演算部であって、前記照会パターンの部分構造と前記文の範囲との対応付けを試行して、前記関数の部分演算結果を、再利用するため記憶領域に格納しながら前記部分構造および前記範囲の内部に関して再帰的に演算することによって、前記スコアを算出する、当該スコア演算部
として機能させるためのプログラム。
【請求項22】
請求項21に記載のコンピュータ実行可能なプログラムをコンピュータ読取可能に格納する記録媒体。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate


【公開番号】特開2012−185561(P2012−185561A)
【公開日】平成24年9月27日(2012.9.27)
【国際特許分類】
【出願番号】特願2011−46709(P2011−46709)
【出願日】平成23年3月3日(2011.3.3)
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MASCHINES CORPORATION
【復代理人】
【識別番号】100110607
【弁理士】
【氏名又は名称】間山 進也
【Fターム(参考)】