Top > Search of Japanese Patents > SYNTACTIC ANALYSIS DEVICE, METHOD, AND PROGRAM

SYNTACTIC ANALYSIS DEVICE, METHOD, AND PROGRAM

Patent code P180015650
File No. 5470
Posted date Nov 22, 2018
Application number P2016-223547
Publication number P2018-081505A
Patent number P6597978
Date of filing Nov 16, 2016
Date of publication of application May 24, 2018
Date of registration Oct 11, 2019
Inventor
  • (In Japanese)西野 正彬
  • (In Japanese)山本 章博
Applicant
  • (In Japanese)日本電信電話株式会社
  • (In Japanese)国立大学法人京都大学
Title SYNTACTIC ANALYSIS DEVICE, METHOD, AND PROGRAM
Abstract PROBLEM TO BE SOLVED: To provide a syntactic analysis device, a method, and a program that can perform syntactic analysis considering an arbitrary constraint condition on a production rule.
SOLUTION: The BDD constructing unit 30 constructs a binary decision diagram corresponding to a logical function representing a logical constraint which is a constraint condition on an input production rule. A syntactic analysis unit 32 obtains a set of possible derivations based on a set of previously given production rules and a series of terminal symbols, uses a propositional variable to express that each production rule is employed in the derivation based on the set of possible derivations obtained, defines a logical function expressing whether or not it is a correct derivation for a series of terminal symbols by using the propositional variable, constructs a binary decision diagram corresponding to the defined logical function, and then finds a derivation that satisfies the constraint condition and maximizes the probability by using the binary decision diagram which is the logical product of the constructed binary decision diagram and the binary decision diagram corresponding to the defined logical function.
Outline of related art and contending technology (In Japanese)

確率文脈自由文法は自然言語文の構文解析に用いられる基礎的な技術である。確率文脈自由文法Gは、G=(M,T,R,S,P)からなる5つ組として定義される。ここでMは非終端記号の集合、Tは終端記号の集合、Rは生成規則の集合、Sは開始記号、Pは生成規則に付与された確率値の集合である。確率文脈自由文法がチョムスキー標準形であるとすれば、生成規則は以下(1)~(3)式のいずれかである。

【数1】
(省略)
・・・(1)
(省略)
・・・(2)
(省略)
・・・(3)

ここでA、B、及びCは非終端記号、αは終端記号、Sは開始記号、εは空列を表すものとする。

各規則は、規則の左辺(以下では頭部とよぶ)の非終端記号Aを右辺の記号列に書き換えることを表している。ある規則A→BCを適用するとは、非終端記号Aを含む系列において、Aを非終端記号の列BCに書き換えることを表す。

各規則に対してはその規則が適用される確率が付与されている。与えられた確率文脈自由文法において、規則の頭部が非終端記号Aであるような規則の集合をr1,...,rmとすると、各規則riには出現確率wiが与えられる。ここで確率wi

【数2】
(省略)

を満たす。各確率は、非終端記号Aが与えられたときに確率wiで生成規則riを適用することを表している。

ある確率文脈自由文法Gが与えられると、それを用いた構文解析が可能となる。すなわち、与えられた終端記号の列α1,α2,...,αnに対して、開始記号Sから当該終端記号の列を導出するための生成規則の適用による非終端記号の書き換えの列を得ることができる。ある構文解析は、開始記号に対して適用した生成規則の列として表現することができる。この列を導出ともよぶ。また、生成規則の列に含まれる各規則に付与された確率の積として、その解析が得られる確率が定義される。

確率文脈自由文法を用いることで自然言語文のように曖昧さのある対象に対する構文解析を行うことができるため、自然言語文の解析や、RNA(リボ核酸)の二次構造予測などに用いられてきた。また、確率文脈自由文法が与えられたときに、ある系列に対する構文解析のうち、確率が最大となるものを発見する問題は、系列の長さをNとするとO(N3)の動的計画法を用いることで解くことができる。

Field of industrial application (In Japanese)

本発明は、構文解析装置、方法、及びプログラムに係り、特に、終端記号の系列に対して、構文解析を行うための構文解析装置、方法、及びプログラムに関する。

Scope of claims (In Japanese)
【請求項1】
 
終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置であって、
入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するBDD構築部と、
予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求め、
前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現し、
前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義し、
前記定義された論理関数に対応する二分決定グラフを構築し、
前記BDD構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求める構文解析部と、
を含む構文解析装置。

【請求項2】
 
前記構文解析部は、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義する請求項1に記載の構文解析装置。

【請求項3】
 
終端記号の系列に対して、確率文脈自由文法に基づいた構文解析を行う構文解析装置における構文解析方法であって、
BDD構築部が、入力された、確率文脈自由文法における非終端記号を書き換えるための生成規則に関する制約条件である論理制約を表す論理関数に対応する二分決定グラフを構築するステップと、
構文解析部が、予め与えられた生成規則の集合と、前記終端記号の系列とに基づいて、予め定められた開始記号から前記終端記号の系列を得るまでの、前記生成規則の列を導出とし、前記終端記号の系列に対して可能な導出の集合を求めるステップと、
前記構文解析部が、前記求められた前記可能な導出の集合に基づいて、前記導出において各生成規則が利用されることを、命題変数を用いて表現するステップと、
前記構文解析部が、前記命題変数を用いて前記終端記号の系列に対する正しい導出であるか否かを表現する論理関数を定義するステップと、
前記構文解析部が、前記定義された論理関数に対応する二分決定グラフを構築するステップと、
前記構文解析部が、前記BDD構築部によって構築された前記二分決定グラフと、前記定義された論理関数に対応する前記二分決定グラフとの論理積となる前記二分決定グラフを用いて、前記制約条件を満たし、かつ、確率が最大となる導出を求めるステップと、
を含む構文解析方法。

【請求項4】
 
前記構文解析部が定義するステップは、前記終端記号の系列に含まれる前記終端記号の各々について、非終端記号を前記終端記号に書き換える生成規則が、前記導出において利用されることを表す命題変数と、前記終端記号の系列に含まれる部分系列の各々について、前記部分系列に対応して前記生成規則が、前記導出において利用されることを表す命題変数とを用いて、前記論理関数を定義する請求項3に記載の構文解析方法。

【請求項5】
 
コンピュータを、請求項1又は請求項2に記載の構文解析装置の各部として機能させるためのプログラム。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2016223547thum.jpg
State of application right Registered
Please contact us by e-mail or facsimile if you have any interests on this patent. Thanks.


PAGE TOP

close
close
close
close
close
close
close