(57)【要約】      （修正有）【課題】単語とスロットの列からなるテンプレートを自然言語文書から抽出する。【解決手段】抽出装置１０１の除去部１０２は、複数のフレーズをアクセプトするＳｅｑＢＤＤから偽辺を除去することにより、偽辺なしダイアグラムを得る。頻度部１０３は、偽辺なしダイアグラムに含まれるノードに、複数のフレーズをアクセプトした際に通過する頻度を対応付ける。置換部１０４は、偽辺なしダイアグラムにおいて、ノードに対応付けられた頻度に基づくスロット条件が満たされるノードをスロットノードに置換し、辺を介して隣り合う複数のスロットノードを１つのスロットノードに置換し、第１ノードからの分岐先であり、第２ノードへの集結元である複数のスロットノードを、１つのスロットノードに置換することにより、置換済ダイアグラムを得る。出力部１０５は、置換済ダイアグラムの開始ノードから始まる各経路を、テンプレートとして出力する。【選択図】図６
2018120401.tif 000002
【特許請求の範囲】
【請求項１】
複数のフレーズをアクセプトする系列二分決定ダイアグラムから偽辺を除去することにより、前記複数のフレーズをアクセプトする偽辺なしダイアグラムを得る除去部、
前記偽辺なしダイアグラムに含まれるノードに、前記複数のフレーズをアクセプトした際に通過する頻度を対応付ける頻度部、
前記偽辺なしダイアグラムにおいて、
(a)ノードに対応付けられた頻度に基づくスロット条件が満たされるノードをスロットノードに置換し、
(b)辺を介して隣り合う複数のスロットノードを1つのスロットノードに置換し、
(c)第1ノードからの分岐先であり、第2ノードへの集結元である複数のスロットノードを、1つのスロットノードに置換する
ことにより、置換済ダイアグラムを得る置換部、
前記置換済ダイアグラムの開始ノードから始まる各経路を、テンプレートとして出力する出力部
を備えることを特徴とする抽出装置。
【請求項２】
前記除去部は、前記系列二分決定ダイアグラムにおいて、
(a)第1ノードから偽辺を介して第2ノードに至り、前記第2ノードから真辺を介して第3ノードに至る経路から、前記偽辺を除去し、前記第1ノードから前記第3ノードへ至る新たな真辺を追加し、
(b)偽終端ノードへ至る真辺ならびに偽辺を除去する
処理を繰り返すことにより、前記偽辺なしダイアグラムを得る
ことを特徴とする請求項1に記載の抽出装置。
【請求項３】
前記除去部は、前記系列二分決定ダイアグラムにおいて、
第1ノードのラベルと第2ノードのラベルが一致し、
前記第1ノードから、第1真辺が第1真子ノードへ至り、
前記第2ノードから、第2真辺が第2真子ノードへ至り、
前記第1ノードから第1偽辺が、前記第2ノードから第2偽辺が、いずれも偽子ノードへ至れば、
前記第2ノードに至る辺の先を前記第1ノードへ置換し、前記第1真辺が至る先を、前記第1真子ノードと前記第2真子ノードとを結合したノードへ置換し、前記第2真辺と前記第2偽辺とを削除する
ことを特徴とする請求項1または2に記載の抽出装置。
【請求項４】
前記偽辺なしダイアグラムに含まれるノードに対応付けられる頻度が、前記偽辺なしダイアグラムの開始ノードに対応付けられる頻度に対して、所定の比較基準において十分に小さいノードは、前記スロット条件を満たす
ことを特徴とする請求項1から3のいずれか1項に記載の抽出装置。
【請求項５】
前記偽辺なしダイアグラムに含まれるノードに対応付けられる頻度が、前記ノードの親ノードに対応付けられる頻度に対して、所定の比較基準において十分に小さいノードは、前記スロット条件を満たす
ことを特徴とする請求項1から3のいずれか1項に記載の抽出装置。
【請求項６】
前記置換部は、前記偽辺なしダイアグラムに含まれるノードに対応付けられる頻度が、所定の閾値より小さいノード、ならびに、当該ノードに出入りする辺を削除してから、前記スロットノードへの置換を行う
ことを特徴とする請求項1から5のいずれか1項に記載の抽出装置。
【請求項７】
前記複数のフレーズは、共通する単語から開始され、
前記出力されるテンプレートは、前記共通する単語から始まるテンプレートである
ことを特徴とする請求項1から6のいずれか1項に記載の抽出装置。
【請求項８】
抽出装置が、複数のフレーズをアクセプトする系列二分決定ダイアグラムから偽辺を除去することにより、前記複数のフレーズをアクセプトする偽辺なしダイアグラムを得る除去ステップ、
前記抽出装置が、前記偽辺なしダイアグラムに含まれるノードに、前記複数のフレーズをアクセプトした際に通過する頻度を対応付ける頻度ステップ、
前記抽出装置が、前記偽辺なしダイアグラムにおいて、
(a)ノードに対応付けられた頻度に基づくスロット条件が満たされるノードをスロットノードに置換し、
(b)辺を介して隣り合う複数のスロットノードを1つのスロットノードに置換し、
(c)第1ノードからの分岐先であり、第2ノードへの集結元である複数のスロットノードを、1つのスロットノードに置換する
ことにより、置換済ダイアグラムを得る置換ステップ、
前記抽出装置が、前記置換済ダイアグラムの開始ノードから始まる各経路を、テンプレートとして出力する出力ステップ
を備えることを特徴とする抽出方法。
【請求項９】
コンピュータを、
複数のフレーズをアクセプトする系列二分決定ダイアグラムから偽辺を除去することにより、前記複数のフレーズをアクセプトする偽辺なしダイアグラムを得る除去部、
前記偽辺なしダイアグラムに含まれるノードに、前記複数のフレーズをアクセプトした際に通過する頻度を対応付ける頻度部、
前記偽辺なしダイアグラムにおいて、
(a)ノードに対応付けられた頻度に基づくスロット条件が満たされるノードをスロットノードに置換し、
(b)辺を介して隣り合う複数のスロットノードを1つのスロットノードに置換し、
(c)第1ノードからの分岐先であり、第2ノードへの集結元である複数のスロットノードを、1つのスロットノードに置換する
ことにより、置換済ダイアグラムを得る置換部、
前記置換済ダイアグラムの開始ノードから始まる各経路を、テンプレートとして出力する出力部
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、単語とスロットの列からなるテンプレートを、自然言語文書から抽出する技術に関する。
【背景技術】
【０００２】
従来から、二分決定ダイアグラム(BDD; Binary Decision Diagram)を応用した系列二分決定ダイアグラム(SeqBDD; Sequence Binary Decision Diagram)を自然言語処理に利用する技術が提案されている。たとえば、特許文献1に開示される技術では、2つの文書に含まれる文同士の対応付けを決定するために、SeqBDDを利用する。非特許文献1に開示される技術では、頻出部分列を抽出するために、SeqBDDを利用する。非特許文献2には、SeqBDDに係る簡約技術や最適化技術等が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第5959480号公報
【非特許文献】
【０００４】
【非特許文献１】Elsa Loekito, James Bailey, and Jian Pei, "A Binary Decision Diagram Based Approach for Mining Frequent Subsequences", Knowledge and Information Systems, Volume 24, Number 2, Pages 235-268, 2010年
【非特許文献２】Shuhei Denzumi, Ryo Yoshinaka, Hiroki Arimura and Shin-ichi Minato, "Sequence binary desicion diagram: Minimization, relationship to acyclic automata, and complexities of Boolean set operations", Discrete Applied Mathematics, Volume 212, Pages 61-80, http://dx.doi.org/10.1016/j.dam.2014.11.022, 2016年10月30日
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、「regard X as Y」(XをYとみなす)「magnitude X earthquake at Y」(Yにおける震度Xの地震)などのような、複数のスロット(上記例のXやY)と単語(上記例のregard, as, magnitude, earthquake, at)を並べたフレーズからなるテンプレートを、各種の自然言語文書から抽出したい、という要望がある。
【０００６】
しかしながら、非特許文献1に開示される技術では、頻出する部分列を抽出することができるが、スロットを有するテンプレートを抽出することはできない。
【０００７】
自然言語文書から、できるだけ多くのテンプレートをできるだけ誤りなく、高速に抽出したい、という要望は強い。
【０００８】
本発明は、上記の課題を解決するためのもので、単語とスロットの列からなるテンプレートを自然言語文書から抽出するのに好適な抽出装置、抽出方法、ならびに、コンピュータを、当該抽出装置として機能させるプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明においては、抽出装置が、
複数のフレーズをアクセプトする系列二分決定ダイアグラムから偽辺を除去することにより、前記複数のフレーズをアクセプトする偽辺なしダイアグラムを得て、
前記偽辺なしダイアグラムに含まれるノードに、前記複数のフレーズをアクセプトした際に通過する頻度を対応付け、
前記偽辺なしダイアグラムにおいて、
(a)ノードに対応付けられた頻度に基づくスロット条件が満たされるノードをスロットノードに置換し、
(b)辺を介して隣り合う複数のスロットノードを1つのスロットノードに置換し、
(c)第1ノードからの分岐先であり、第2ノードへの集結元である複数のスロットノードを、1つのスロットノードに置換する
ことにより、置換済ダイアグラムを得て、
前記置換済ダイアグラムの開始ノードから始まる各経路を、テンプレートとして出力する。
【００１０】
また、本発明に係る抽出装置は、コンピュータが有するプロセッサが、コンピュータ読取可能な非一時的な情報記録媒体(non-transitory computer-readable information recording medium)に記録されたプログラムに含まれるコードを実行することにより実現することができ、当該プログラムは、コンピュータ通信網等の一時的な通信媒体(transitory communication medium)を介して転送することができる。
【００１１】
さらに、本発明に係る抽出装置は、FPGA(Field Programmable Gate Array)やASIC(Application Specific Integrated Circuit)などの技術を利用し、コンピュータ読取可能な非一時的な情報記録媒体に記録されたプログラムを設計図として参照し、種々の変換や処理を施すことによって、専用の電子回路、もしくは、専用のハードウェアとして構築することができる。
【発明の効果】
【００１２】
本発明によれば、単語とスロットの列からなるテンプレートを自然言語文書から抽出するのに好適な抽出装置、抽出方法、ならびに、コンピュータを、当該抽出装置として機能させるプログラムを提供することができる。
【図面の簡単な説明】
【００１３】
【図１】フレーズab, ac, bcをアクセプトするBDDの説明図である。
【図２】フレーズab, ac, bcをアクセプトするSeqBDDの説明図である。
【図３】フレーズab, ac, bcをアクセプトする偽辺なしダイアグラムの説明図である。
【図４】フレーズac, abc, aac, acc, abbcをアクセプトするSeqBDDの説明図である。
【図５】フレーズac, abc, aac, acc, abbcをアクセプトする偽辺なしダイアグラムの説明図である。
【図６】本実施形態に係る抽出装置の構成を示す説明図である。
【図７】本実施形態に係る抽出処理の制御の流れを示すフローチャートである。
【図８】同じ単語から始まるフレーズを与えてできる偽辺なしダイアグラムの例を示す説明図である。
【図９】従来技術におけるノード共有を示す説明図である。
【図１０】本実施形態におけるノード共有を示す説明図である。
【図１１】処理Getvertexの制御の流れを示すフローチャートである。
【図１２】従来技術と本実施形態によって抽出されたテンプレートのMRRおよびRecallを示すグラフである。
【発明を実施するための形態】
【００１４】
以下に本発明の実施形態を説明する。なお、本実施形態は説明のためのものであり、本願発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。
【００１５】
(BDD, SeqBDD, 偽辺なしダイアグラム)
以下では、本実施形態において利用されるBDD、SeqBDD、ならびに、偽辺なしダイアグラムについて説明する。これらはいずれも、a, b, cというシンボルを含むフレーズをアクセプトする。これらのシンボルは、一般の自然言語処理においては、文字、単語、あるいは、形態素に相当するものである。図1は、フレーズab, ac, bcをアクセプトするBDDの説明図である。
【００１６】
本図では、丸印でノード(node、あるいは、vertex)が表現され、各ノードには、フレーズ内に出現するシンボルがラベルとして付されている。菱形は開始ノードを表しており、実線の矢印は、真辺(true-edge、あるいは、1-edge)を、破線の矢印は、偽辺(false-edge、あるいは、0-edge)を、それぞれ意味する。正方形は、終端ノードを意味しており、中に1が描かれたものは、真終端ノード(true-terminal-node、あるいは、1-terminal-node)、中に0が描かれたものは、偽終端ノード(false-terminal-node、あるいは、0-terminal-node)と呼ばれる。
【００１７】
なお、ある辺があるノードから他のノードに至る場合、この辺を親子関係と解して、前者を後者の親ノード、後者を前者の子ノードと呼ぶ。また、共通する親ノードを持つ複数の子ノードを、兄弟ノードと呼ぶ。
【００１８】
本図に示す矢印を開始ノードから終端ノードまで辿ると、たとえば、「a, 真辺, b, 偽辺, c, 真辺, 1」「a, 偽辺, b, 真辺, c, 偽辺, 0」等のような経路が得られる。BDDは、フレーズを先頭からスキャンしたときに出会うシンボルが条件を満たすか否かを表現している。
【００１９】
ここで、上記の経路における「真辺」は「に出会う。」と、「偽辺」は「に出会わない。」と、「1」は、「アクセプト」と、「0」は、「リジェクト」と、それぞれ解釈すると、上記のこの2つの経路は、「aに出会う。bに出会わない。cに出会う。アクセプト」「aに出会わない。bに出会う。cに出会わない。リジェクト」と解すすることができる。すなわち、本図のBDDは、「ac」というフレーズはアクセプトするが、「b」というフレーズはリジェクトする。
【００２０】
このように、あるノードから伸びる真辺と偽辺は、それぞれ、フレーズを先頭からスキャンするときに、当該ノードに付されたラベルに出会ったときと出会わなかったときの遷移を表す。
【００２１】
図2は、フレーズab, ac, bcをアクセプトするSeqBDDの説明図である。SeqBDDは、BDDに対する簡約、最適化を行うことで得られるダイアグラムで、その具体的な手法については、非特許文献1, 2等に開示されている。本図では、偽終端ノードに至る経路を省略して図示している。特に、非特許文献2においては、関数Reduceにおいて関数Getvertexを呼び、その中で共有可能なサブダイアグラムをまとめあげることで、最適化を図っている。
【００２２】
さて、これは、SeqBDDから偽辺を除去することができれば、開始ノードから真終端ノードに至るまでの任意の経路をたどり、ノードに付されたラベルをそのまま並べることで、当該経路に対するフレーズが得られ、これを深さ優先探索によって繰り返すことで、テンプレートの侯補がすべて得られることになる。このため、本実施形態では、SeqBDDから偽辺なしダイアグラムを作る。
【００２３】
図3は、フレーズab, ac, bcをアクセプトする偽辺なしダイアグラムの説明図である。第1ノードから偽辺が第2ノードへ伸び、当該第2ノードから真辺が第3ノードへ伸びている場合には、当該偽辺を除去して、第1ノードから第3ノードへ伸びる新たな真辺を追加する、という処理を繰り返すことで、本図に示すように、偽辺なしダイアグラムを得ることができる。すなわち、図2における「開始ノード, 真辺, a, 偽辺, b」という経路から偽辺が除去されて開始ノードからbへ伸びる真辺が追加され、「a, 真辺, b, 偽辺, c」という経路から偽辺が除去されてaからcへ伸びる真辺が追加されている。
【００２４】
以下では、スロットを含むテンプレートを抽出する例について考える。図4は、フレーズac, abc, aac, acc, abbcをアクセプトするSeqBDDの説明図である。ここでアクセプトされるフレーズそのものは、ac, abc, aac, acc, abbcであるから、人が見れば、「aとcで何かを挟む」テンプレート、すなわち、スロットXに0個以上のシンボルが入るテンプレートaXcが抽出されるべきである、と考えつくはずである。そこで、このSeqBDDに対して、偽辺除去の処理を施してみる。
【００２５】
図5は、フレーズac, abc, aac, acc, abbcをアクセプトする偽辺なしダイアグラムの説明図である。このダイアグラムを見ると、上方のノードaから多数のノードへ辺が分岐しており、多数のノードから出た辺が下方のノードcへ集結していることがわかる。そこで、上方のaと下方のcは、テンプレートにおいて「lexical」(文字通り、その姿のまま)出現し、分岐途中の多数のノードを、1つのスロットとしてまとめることで、テンプレートaXcが得られる。
【００２６】
なお、本図のように、菱形の開始ノードから辺を介して至るノードが1つである場合には、両ノードを一体化して処理することができる。したがって、本図から菱形および菱形から伸びる辺を除去し、上方のノードaを開始ノードとして取り扱うことができる。
【００２７】
(抽出装置)
以下では、複数のフレーズからテンプレートを抽出する処理を実行する抽出装置の実施形態について説明する。図6は、本実施形態に係る抽出装置の構成を示す説明図である。図7は、本実施形態に係る抽出処理の制御の流れを示すフローチャートである。
【００２８】
本図に示す抽出装置101は、典型的には、コンピュータが有する1以上のプロセッサが、非一時的なコンピュータ読取可能な情報記録媒体に記録されたプログラムを1以上のメモリにロードして実行することによって実現される。ただし、プログラムを電子回路やハードウェアの設計図として利用するFPGAやASIC等の技術においては、抽出装置101は、電子回路の組合せによって実現される。
【００２９】
本実施形態に係る抽出装置101は、除去部102、頻度部103、置換部104、出力部105を備える。また、生成部109を備えることとしても良い。
【００３０】
生成部109を備える態様では、生成部109は、複数のフレーズをアクセプトするSeqBDDを生成する(ステップS701)。これは、非特許文献1, 2に開示される技術を応用することによって行われる。また、これらの技術によって別途用意されたSeqBDDをそのまま利用することもできる。この場合には、生成部109における生成は、必要ない。
【００３１】
次に、除去部102は、SeqBDDから偽辺を除去することにより、SeqBDDと共通する複数のフレーズをアクセプトする偽辺なしダイアグラムを得る(ステップS702)。
【００３２】
具体的には、除去部は、SeqBDDにおいて、
(a)第1ノードから偽辺を介して第2ノードに至り、第2ノードから真辺を介して第3ノードに至る経路から、偽辺を除去し、真辺が至る先を第3ノードへ置換し、
(b)偽終端ノードへ至る真辺ならびに偽辺を除去する
という処理を、偽辺がなくなるまで繰り返せば良い。
【００３３】
なお、本願発明者は、スロットを含むテンプレートを抽出する目的に好適なSeqBDDの最適化処理を上記(a)(b)に先立って実行する技術に想到している。この最適化技術については、後述する。
【００３４】
一方、頻度部103は、偽辺なしダイアグラムに含まれるノードに、複数のフレーズをアクセプトした際に通過する頻度を対応付ける(ステップS703)。
【００３５】
SeqBDDを生成する際に、複数のフレーズのそれぞれが与えられるごとに、各ノードおよび各辺に対して通過回数を数えておき、偽辺を除去する際にこの値を通算することによって、各ノードおよび各辺に対して頻度を対応付けることができる。また、あらためて、偽辺なしダイアグラムに複数のフレーズをアクセプトさせることによって頻度の対応付けを行っても良い。本図では、後者の場合についての情報の出入りの様子を図示している。
【００３６】
なお、ステップS701-S703の処理は、上記のように逐次的に行うのではなく、フレーズを1個与えるごとにオンザフライ(on-the-fly)で実行することも可能である。
【００３７】
さらに、置換部104は、偽辺なしダイアグラムにおいて、
(a)ノードに対応付けられた頻度に基づくスロット条件が満たされるノードをスロットノードに置換し、
(b)辺を介して隣り合う複数のスロットノードを1つのスロットノードに置換し、
(c)第1ノードからの分岐先であり、第2ノードへの集結元である複数のスロットノードを、1つのスロットノードに置換する
ことにより、置換済ダイアグラムを得る(ステップS704)。
【００３８】
置換済ダイアグラムは、図5において、複数のノードを「slot」としてまとめあげたダイアグラムに相当するものである。
【００３９】
ここで、スロット条件として最も単純なものは、あるノードに対応付けられた頻度と、開始ノードに対応付けられた頻度(これは、アクセプト可能な複数のフレーズの総数に等しい。)と、の比が、所定の閾値より小さい、というものである。この態様では、辺を辿る必要はなく、各ノードに対応付けられた頻度を参照するだけで、いずれをスロットとすべきか、を定めることができる。
【００４０】
このほか、ノードpからノードqへ至る辺が存在する場合に、親ノードpに対応付けられた頻度freq(p)に対する子ノードqに対応付けられた頻度freq(q)の比freq(q)/freq(p)が、所定の閾値より小さければ、子ノードqがスロット条件を満たす、としても良い。freq(q)/freq(p)が小さい、ということは、親ノードpには、子ノードqのほかにも子ノードが(多数)ある、ということを意味するからである。
【００４１】
このようにして、ノードをスロットに置換した後は、親子スロット(親子関係にある2つのスロットノード)や、分岐-集結スロット(あるノードからの分岐先であり、他のあるノードへの集結元であるスロット)を1つのスロットにまとめあげることで、整備されたテンプレートが得られる。
【００４２】
最後に、出力部105は、置換済ダイアグラムの開始ノードから始まる各経路を、テンプレートとして出力して(ステップS705)、本処理を終了する。上記のように置換済ダイアグラムの開始点から始まる全経路を、深さ優先探索によって列挙することによって、スロットを含むテンプレートが得られることになる。
【００４３】
出力部105から出力されるテンプレートにおいては、置換済ダイアグラムを開始ノードから終端ノードまで走査する経路内にて出会った頻度のうち最小の頻度を、当該テンプレートの頻度とすることができる。したがって、この頻度が多い順に、および/または、この頻度が所定の閾値以上のテンプレートを出力すれば、抽出されたテンプレートのうち確度の高いものを得ることができる。
【００４４】
なお、複数のフレーズとして、同じ単語から始まるものを採用することができる。たとえば、動詞regardから始まる以下のフレーズ
regard him as … 
regard her as … 
regard it as … 
regard the problem as … 
regard some money as … 
を与えることで、動詞regardに関するテンプレートを抽出する例について考える。
【００４５】
図8は、同じ単語から始まるフレーズを与えてできる偽辺なしダイアグラムの例を示す説明図である。本図に示す例では、開始ノードregard、および、末尾のノードasに対応付けられる頻度は5であり、それ以外のノードhim, her, it, the, problem, some, moneyに対応付けられる頻度は1となっている。そこで、スロット条件として「ノードの頻度が開始ノードの頻度の半分以下」「ノードの頻度が親ノードの頻度の半分以下」などを採用した場合には、ノードhim, her, it, the, problem, some, moneyは、すべてスロットになる。
【００４６】
まず、theとproblemからできたスロットは親子関係にあるから、これを1つのスロットに置換する。また、someとmoneyからできたスロットは親子関係にあるから、これを1つのスロットに置換する。すると、5つのスロットは、いずれも、regardを親に持ち、asを子に持つ分岐-集結スロットであるから、これらをまとめて、1つのスロットに置換する。
【００４７】
なお、大量の自然言語文書に出現する複数のフレーズを元にテンプレートを抽出しようとする場合には、通過回数が1回(あるいは、所定閾値以下)のノードや辺を除去してから、スロットノードへの置換を行うこととしても良い。このような処理を行うことで、テンプレートとしてふさわしくないものをあらかじめ除去して、処理を効率良く進めることが可能となる。
【００４８】
(偽辺の共有による最適化)
非特許文献2に開示される技術では、関数Getvertexの中で、2つのノードu, vをまとめあげる処理をしている。図9は、従来技術におけるノード共有を示す説明図である。本図に示すように、ノードu, vのlabelが共通し(u.label = v.label = w)、uの偽子ノード(u.0)とvの偽子ノード(v.0)が一致し、uの真子ノード(u.1)とvの真子ノード(v.1)が一致する場合に、ノードu, vを1つにまとめあげる処理を実行することで、ダイアグラムを簡潔にすることとしている。
【００４９】
一方、本実施形態において、抽出装置101に与えられてSeqBDDを生成する際に参照される複数のフレーズは、事例として集められたものである。したがって、得られたSeqBDDがアクセプトできないフレーズには、以下の2種類がある。
(1)たとえば文法的な誤りを含む等により、本来的にリジェクトすべきフレーズ。
(2)たまたま事例として収集されなかったフレーズ。
【００５０】
本実施形態では、これらを同一視することによって、ダイアグラムをさらに簡略化するための条件を緩和(relax)することができる。
【００５１】
図10は、本実施形態におけるノード共有を示す説明図である。本図に示すように、SeqBDDから緩和されたSeqBDDを得るには、付されたlabelが共通する2つのノードu, v (u.label = v.label = w)に対して、ノードuの偽子ノード(u.0)とノードvの偽子ノード(v.0)が一致する場合に、ノードuの真子ノード(u.1)とノードvの真子ノード(v.1)とのユニオン(union; 集合演算∪)を、ノードuの真子ノード(u.1)として書き込んで、ノードvを除去する。
【００５２】
ここで、ユニオンとは、2つのダイアグラムを結合したもので、アクセプトできるフレーズが集合の意味で足し合わされることになり、非特許文献2においては、演算Meld∪により表現される。
【００５３】
これらの処理は、除去部102によって実行され、具体的には、SeqBDDにおいて、
第1ノード(u)のラベル(u.label)と第2ノード(v)のラベル(v.label)が一致(u.lavel = v.label = w)し、
第1ノード(u)から、第1真辺が第1真子ノード(u.1)へ至り、
第2ノード(v)から、第2真辺が第2真子ノード(v.1)へ至り、
第1ノード(u)から第1偽辺が、第2ノード(v)から第2偽辺が、いずれも偽子ノード(u.0 == v.0)へ至れば、
第2ノードに至る辺の先を第1ノードへ置換し、第1真辺が至る先を、第1真子ノードと第2真子ノードとを結合したノード(Union(u.1, v.1))へ置換し、第2真辺と第2偽辺とを削除する
という処理を、できなくなるまで繰り返し実行すれば良い。この処理は、以下のような再帰的関数(recursive function)Getvertexを利用すれば良い。以下のGetvertexは、非特許文献2に開示されるGetvertexを緩和して、偽辺ならびに偽ノードの共有をより一層進めるものである。
【００５４】
図11は、処理Getvertexの制御の流れを示すフローチャートである。本図において、非特許文献2との差異がある部分には、下線を付している。
【００５５】
本図に示すように、関数Getvertexは、3つの引数v, g0, g1をとる。v、g0、g1は、いずれかのノードである。
【００５６】
まず、本処理では、抽出装置101は、g1が偽終端ノードであるか否かを調べる(ステップS901)。そうであれば(ステップS901;Yes)、抽出装置101は、g0をリターンして本関数を終了する(ステップS902)。
【００５７】
次に、抽出装置101は、vのラベルv.labelとg0の組合せ(v.label,g0)に対応付けられてハッシュテーブルに登録されている値をuに取得する(ステップS903)。
【００５８】
ハッシュテーブルに、vのラベルとg0の組合せに対応付けられて登録された値がなかった場合には、u=nullとなる(ステップS904;Yes)。
【００５９】
u≠nullであれば(ステップS904;No)、抽出装置101は、uからvへ真辺のみを辿って到達することができるか調べる(ステップS905)。到達できなければ(ステップS905;No)、抽出装置101は、Union(g1,u.1)を求め、uの真子ノードu.1を求められたUnion(g1,u.1)に書き換え(ステップS906)、uをリターンして本関数を終了する(ステップS907)。
【００６０】
一方、u=null(ステップS904;Yes)、もしくは、uからvへ真辺のみを辿って到達することができる(ステップS905;Yes)ならば、抽出装置101は、vの偽子ノード(v.0)および真子ノード(v.1)をg0およびg1とし(ステップS908)、ハッシュテーブルに、vのラベルとg0の組に対応付けてvを登録して(ステップS909)、vをリターンして本関数を終了する(ステップS910)。
【００６１】
なお、ステップS905において、uからvへ至る経路があるか否かをチェックしているのは、緩和されたSeqBDDにおいて、循環が生じてしまうのを防止するためである。
【００６２】
関数Getvertexは、非特許文献2に開示される通り、SeqBDDを簡約(reduce)する関数Reduceから呼び出される。関数Reduceは、簡約すべきダイアグラムの開始ノードvを引数としてとる。そして、引数として渡されたノードvが偽終端ノードもしくは真終端ノードであれば、当該ノードvをリターンする。
【００６３】
そうでなければ、Getvertex(v, Reduce(v.0), Reduce(v.1))をリターンする。すなわち、ノードvと、ノードvの偽子ノードv.0を再帰的にReduceした結果と、ノードvの真子ノードv.1を再帰的にReduceした結果と、を関数Getvertexに渡す。
【００６４】
このように、緩和されたSeqBDDを用いてテンプレートを抽出すれば、できあがるダイアグラムをさらに最適化し、処理の高速化を図ることができる。また、たまたま与えられなかったフレーズと出現すべきでないフレーズとを混ぜ込んで処理するため、抽出されるテンプレートが正しいものである可能性が高まるものと期待される。
【００６５】
そこで、実験を行って、得られるテンプレートの特性を比較した。図12は、従来技術と本実施形態によって抽出されたテンプレートのMRRおよびRecallを示すグラフである。本図では、従来技術であるパーズ(Parse/丸)によりテンプレートを抽出した場合、従来のSeqBDDに対して直ちにスロットノードへの変換を施した場合(SeqBDD/三角)、SeqBDDにおいて偽子ノードのまとめあげを行った場合(Relaxed SeqBDD/菱形)の場合の3通りについて、カットオフ値を0, 100, 200, 500, 1000, 2000, 5000, 10000として得られたテンプレートのMRR(Mean Reciprocal Rank)およびRecall(再現率)を表したものである。
【００６６】
本図を見ると、本実施形態に係る2つの技術は、いずれも従来技術より高いMRRを示している。また、一般に、MRRとRecallはトレードオフの関係にあるが、Relaxed SeqBDDでは、いずれも良好な結果が得られていることがわかる。
【００６７】
本処理を実行することにより、従来技術に比べて、偽辺を共有できる可能性が増す。このため、テンプレートを抽出するためのダイアグラムをより簡潔にすることができ、処理の高速化を図ることができる。
【００６８】
(まとめ)
以上説明したように、本実施形態に係る抽出装置は、
複数のフレーズをアクセプトする系列二分決定ダイアグラムから偽辺を除去することにより、前記複数のフレーズをアクセプトする偽辺なしダイアグラムを得る除去部、
前記偽辺なしダイアグラムに含まれるノードに、前記複数のフレーズをアクセプトした際に通過する頻度を対応付ける頻度部、
前記偽辺なしダイアグラムにおいて、
(a)ノードに対応付けられた頻度に基づくスロット条件が満たされるノードをスロットノードに置換し、
(b)辺を介して隣り合う複数のスロットノードを1つのスロットノードに置換し、
(c)第1ノードからの分岐先であり、第2ノードへの集結元である複数のスロットノードを、1つのスロットノードに置換する
ことにより、置換済ダイアグラムを得る置換部、
前記置換済ダイアグラムの開始ノードから始まる各経路を、テンプレートとして出力する出力部
を備える。
【００６９】
また、本実施形態に係る抽出装置において、
前記除去部は、前記系列二分決定ダイアグラムにおいて、
(a)第1ノードから偽辺を介して第2ノードに至り、前記第2ノードから真辺を介して第3ノードに至る経路から、前記偽辺を除去し、前記第1ノードから前記第3ノードへ至る新たな真辺を追加し、
(b)偽終端ノードへ至る真辺ならびに偽辺を除去する
処理を繰り返すことにより、前記偽辺なしダイアグラムを得る
ように構成することができる。
【００７０】
また、本実施形態に係る抽出装置において、
前記除去部は、前記系列二分決定ダイアグラムにおいて、
第1ノードのラベルと第2ノードのラベルが一致し、
前記第1ノードから、第1真辺が第1真子ノードへ至り、
前記第2ノードから、第2真辺が第2真子ノードへ至り、
前記第1ノードから第1偽辺が、前記第2ノードから第2偽辺が、いずれも偽子ノードへ至れば、
前記第2ノードに至る辺の先を前記第1ノードへ置換し、前記第1真辺が至る先を、前記第1真子ノードと前記第2真子ノードとを結合したノードへ置換し、前記第2真辺と前記第2偽辺とを削除する
ように構成することができる。
【００７１】
また、本実施形態に係る抽出装置において、
前記偽辺なしダイアグラムに含まれるノードに対応付けられる頻度が、前記偽辺なしダイアグラムの開始ノードに対応付けられる頻度に対して、所定の比較基準において十分に小さいノードは、前記スロット条件を満たす
ように構成することができる。
【００７２】
また、本実施形態に係る抽出装置において、
前記偽辺なしダイアグラムに含まれるノードに対応付けられる頻度が、前記ノードの親ノードに対応付けられる頻度に対して、所定の比較基準において十分に小さいノードは、前記スロット条件を満たす
ように構成することができる。
【００７３】
また、本実施形態に係る抽出装置において、
前記置換部は、前記偽辺なしダイアグラムに含まれるノードに対応付けられる頻度が、所定の閾値より小さいノード、ならびに、当該ノードに出入りする辺を削除してから、前記スロットノードへの置換を行う
ように構成することができる。
【００７４】
また、本実施形態に係る抽出装置において、
前記複数のフレーズは、共通する単語から開始され、
前記出力されるテンプレートは、前記共通する単語から始まるテンプレートである
ように構成することができる。
【００７５】
本実施形態に係る抽出方法は、
抽出装置が、複数のフレーズをアクセプトする系列二分決定ダイアグラムから偽辺を除去することにより、前記複数のフレーズをアクセプトする偽辺なしダイアグラムを得る除去ステップ、
前記抽出装置が、前記偽辺なしダイアグラムに含まれるノードに、前記複数のフレーズをアクセプトした際に通過する頻度を対応付ける頻度ステップ、
前記抽出装置が、前記偽辺なしダイアグラムにおいて、
(a)ノードに対応付けられた頻度に基づくスロット条件が満たされるノードをスロットノードに置換し、
(b)辺を介して隣り合う複数のスロットノードを1つのスロットノードに置換し、
(c)第1ノードからの分岐先であり、第2ノードへの集結元である複数のスロットノードを、1つのスロットノードに置換する
ことにより、置換済ダイアグラムを得る置換ステップ、
前記抽出装置が、前記置換済ダイアグラムの開始ノードから始まる各経路を、テンプレートとして出力する出力ステップ
を備える。
【００７６】
本実施形態に係るプログラムは、コンピュータを、
複数のフレーズをアクセプトする系列二分決定ダイアグラムから偽辺を除去することにより、前記複数のフレーズをアクセプトする偽辺なしダイアグラムを得る除去部、
前記偽辺なしダイアグラムに含まれるノードに、前記複数のフレーズをアクセプトした際に通過する頻度を対応付ける頻度部、
前記偽辺なしダイアグラムにおいて、
(a)ノードに対応付けられた頻度に基づくスロット条件が満たされるノードをスロットノードに置換し、
(b)辺を介して隣り合う複数のスロットノードを1つのスロットノードに置換し、
(c)第1ノードからの分岐先であり、第2ノードへの集結元である複数のスロットノードを、1つのスロットノードに置換する
ことにより、置換済ダイアグラムを得る置換部、
前記置換済ダイアグラムの開始ノードから始まる各経路を、テンプレートとして出力する出力部
として機能させる。
【００７７】
本発明は、本発明の広義の精神と範囲を逸脱することなく、様々な実施の形態及び変形が可能とされるものである。また、上述した実施の形態は、この発明を説明するためのものであり、本発明の範囲を限定するものではない。すなわち、本発明の範囲は、実施の形態ではなく、特許請求の範囲によって示される。そして、特許請求の範囲内及びそれと同等の発明の意義の範囲内で施される様々な変形が、この発明の範囲内とみなされる。
【産業上の利用可能性】
【００７８】
本発明によれば、単語とスロットの列からなるテンプレートを自然言語文書から抽出するのに好適な抽出装置、抽出方法、ならびに、コンピュータを、当該抽出装置として機能させるプログラムを提供することができる。
【符号の説明】
【００７９】
101 抽出装置
102 除去部
103 頻度部
104 置換部
105 出力部
109 生成部
【図１】
2018120401.tif 000003
【図２】
2018120401.tif 000004
【図３】
2018120401.tif 000005
【図４】
2018120401.tif 000006
【図５】
2018120401.tif 000007
【図６】
2018120401.tif 000008
【図７】
2018120401.tif 000009
【図８】
2018120401.tif 000010
【図９】
2018120401.tif 000011
【図１０】
2018120401.tif 000012
【図１１】
2018120401.tif 000013
【図１２】
2018120401.tif 000014