Data processing: speech signal processing – linguistics – language – Linguistics – Natural language
Reexamination Certificate
1999-08-13
2001-12-18
Edouard, Patrick N. (Department: 3644)
Data processing: speech signal processing, linguistics, language
Linguistics
Natural language
Reexamination Certificate
active
06332118
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique for analyzing natural language by applying a dependency grammar.
2. Description of the Related Art
A dependency grammar is a grammar which describes a syntax structure, defining a modification relation between two words and its type as basic elements. Available as a publication which discloses a method for analyzing natural language by applying the dependency grammar is “Dependency Grammar Based on Strength of Modification Relation—Restrictive Grammar” (which will be hereinafter referred to as “Publication 1”) on the Journal of the Information Processing Society, vol. 33, no. 10, pp. 1211-1223. According to the method described in Publication 1, all possible solutions are attained by effecting a bottom-up depth-first analysis, while writing all possible dependency relations between two clauses into an analysis table, or a chart.
Available as a publication which discloses a method for attaining all possible solutions by performing a bottom-up depth-first analysis is “A New Statistical Parser Based on Bigram Lexical Dependencies” (which will be hereinafter referred to as “Publication 2”) in the Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, July 1996. According to the method described in Publication 2, especially in Chapter 3 thereof, a bottom-up chart system is employed as an analyzing algorithm. Of two local analyzing result, priority is given to one having a higher possibility of usage, and the other having a lower possibility of usage is dismissed. The method described in Publication 2 employs the structure which writing words into a chart in a unit of dependency relations connective (that is, the dependency relation connective words having possibility to have linguistic meanings) words in which grammatical rule applied to words except a head word is completed.
Available as a publication which discloses another bottom-up chart system like Publication 2 is “Bilexical Grammars And A Cubic-Time Probabilistic Parser” (which will be hereinafter referred to as “Publication 3”) in Proceedings of the International Workshop on Parsing Technologies, MIT, September 1997. The differences between Publication 2 and Publication 3 is a unit to be written into a chart. The method described in Publication 3 employs non-connective (that is, local analysis result to which linguistic meanings is hardly given) aligned result of local analysis in general as the unit of chart writing instead of local analysis result in which application of the grammatical rule is completed. According to this structure, the method of Publication 3 realizes a solution for limiting words at ends in a section to which further grammatical rule should be applied.
Giving priority to meanings for extracting meaning having the highest priority is a general method for clarifying vague meanings contained in natural language. It is difficult to compare priorities of meanings analyzed by the depth-first analysis like the technique disclosed in Publication 1 because the depth-first analysis is the time series analysis. The depth-first analysis also has difficulties for reusing the local analysis result for further analysis. According to those disadvantages, breadth-first analysis like techniques described in Publications 2 or 3 are often used for analyzing the natural language.
It is known a chart method which helps the breadth-first analysis. Available as a publication which discloses algorithm for the chart method is “Fundamentals of Natural Language Processing” written by Hirosato Nomura, published by The Institute of Electronics, Information and Communication Engineers, 1988, Chapter 2, Section 3 (which will be hereinafter referred to as “Publication 4”). The chart method features: controlling analysis order based on dynamic programming scheme; utilizing local analysis result registered in a chart; and classifying local analysis result having different internal structure but have the same grammatical function which will be shown at applying the grammatical rule carried out later, into the same group (this feature is so called “packing”). Because of those features, the chart method helps the breadth-first analysis to carry out an arbitral context-free grammar rule application with the calculation amount of an order of the 3rd power of the number of words in an input sentence.
Detailed explanation of the calculation amount of the chart method will now be described. Basically, the chart method groups local analysis results in adjacent sections into one. Construction analysis will proceed smoothly if the free-context grammar application employs the chart method, because applicability of the grammar rule to the local analysis result depends only on non-terminal symbols in the analysis result.
More precisely, further analysis will be simplified with using packages including local analysis result because word strings in a section can be packed into one regardless how complex structure they have, in a case where the word strings in one section are grouped in the same non-terminal symbol. Thus, the maximum number of the local analysis result in one section is a fixed number. The fixed number does not depend on the number of input words but the number of non-terminal symbols. Accordingly, the calculation amount per one basic calculation is also restricted by a fixed number uniformly. In this case, the maximum amount of calculation is an order of the 3rd power of the number of the words because the number of the basic calculations is equal to the number of combinations of adjacent two sections.
It is known that the maximum amount of calculation will be an order of the 5th power of the number of input words in a case where the chart method is simply applied to the dependency grammar. “apply” means applying grammar rule and packing with the dependency structure as a unit of edges. In this case, the dependency structure has grouped words in which a head word act as a parent word, and the grammar rule application to the words except the head word has been completed. This method is a directly extended method of analyzing context-free grammar using the chart method.
In the dependency grammatical rule, the state of the head word of a dependency structure determine which grammatical rule is applicable to the dependency structure later. However, it is generally unknown that which word in a section is a head word for the dependency structure of the analysis result regarding to the section concerned. Therefore, the maximum number of packed local analysis result in the section may be order of the number of the words in the section. As a result, the amount of calculation will be the 5th power of the number of the words.
To avoid this problem, the method described in Publication 3 employs generally non-connected structure in stead of employing the completed local structure including a head word acting as an edge i.e. a unit of words to be registered in a chart. The method determines the edges so that only a start word and an end word of the section determines grammatical function of the structure. Thus determined edges limits the number of functions (the number of cases) for further grammatical rule application to the analysis result in a section. In this case, the number of functions is a fixed number represented by the product of the number of states regarding to the grammatical rule applied to the start and end words of the section. This fixed number does not depend on the number of the words. As a result, the amount of calculation to obtain full result by the method of Publication 3 will also be an order of the 3rd power of the number of input words like the case of context-free grammatical rule application.
Analyzing method of Publication
3
will now be described with reference with a program list shown in FIG.
35
. The program list shown in
FIG. 35
is quoted from section 4.3 of Publication 3. In the program list, contents described in “(* . . . )” at line ends of lines
4
,
9
-
14
, and
18
represe
Edouard Patrick N.
Foley & Lardner
NEC Corporation
LandOfFree
Chart parsing method and system for natural language... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Chart parsing method and system for natural language..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chart parsing method and system for natural language... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2576951