US 2007/0192084 A1 · Induction of grammar rules

Abstract

A method of grammar rule induction comprises obtaining a monolingual set of phrases from a bilingual corpus of translation pairs. For each of the monolingual phrases in turn, initialising, with inactive edges formed from headwords identified in the phrase, the agenda of a dependency grammar chart parser arranged to form packed edges in the chart. Running the chart parser and adding to the agenda, for each inactive edge removed from the agenda, one or more active edges created as if all possible grammar rules existed. When the agenda is empty, ascertaining the alternations of each edge in the packed edge corresponding to the complete phrase, and finding their respective highest frequencies. For the set of phrases, summing, for each alternation, its respective highest frequencies, and ranking the sums. Then, selecting alternations in rank order to form the required set of grammar rules until the required set has become sufficient such that for each monolingual phrase there exists at least one analysis corresponding to the required set of grammar rules.

Claims26

Dependent claims

A method of generating a set of grammar rules for a given language, referred to as the required set of grammar rules, comprising the steps:

(a) acquiring a set of phrases in the given language, those phrases existing in a corpus of phrase translation pairs;
(b) generating a set of grammar rules in respect of the set of phrases;
(c) generating, by an analysis generator and using said set of grammar rules, for each member of the set of phrases, a respective set of analyses;
(d) ascertaining, for each of the analyses, the respective alternations thereof;
(e) ranking the alternations in accordance with a predetermined criterion;
(f) responding to a trigger by actually or effectively transferring the current highest ranking alternation or alternations from the ranked list of alternations to a list of selected alternations and entering a trigger-waiting state;
and
(g) responding actually or effectively to the entry of the trigger-waiting state by ascertaining whether there exists, for each member of the stored set of phrases, at least one analysis corresponding to the current list of selected alternations acting as grammar rules, and either generating a said trigger upon a negative outcome or taking no action upon a positive outcome, whereupon in this latter case the current list of selected alternations is then deemed to be the required set of grammar rules.

5 more elements

Apparatus for generating a set of grammar rules for a given language, referred to as the required set of grammar rules, comprising:

a store for storing, in use, a set of phrases in the given language, those phrases existing in a corpus of phrase translation pairs;
a grammar rule generator for generating, for a set of phrases in the store, a set of grammar rules in respect of the set of phrases;
an analysis generator arranged to use the generated grammar rules for generating, for each member of the stored set of phrases, a predetermined number of analyses;
means for ascertaining, for each of the analyses, the respective alternations thereof;
means for forming a list of the alternations ranked in accordance with a predetermined criterion;
alternation selection means responsive to a trigger for changing from a quiescent state to an active state in which it actually or effectively transfers the current highest ranking alternation or alternations from the ranked list of alternations to a list of selected alternations and returns to its quiescent state;
and
means responsive actually or effectively to the return of the alternation selection means to its quiescent state for ascertaining whether there exists, for each member of the stored set of phrases, at least one analysis corresponding to the current list of selected alternations acting as grammar rules, and being arranged to trigger the alternation selection means upon a negative outcome and to take no action upon a positive outcome, whereupon in this latter case the current list of selected alternations is then deemed to be the required set of grammar rules.

5 more elements

A method of generating a set of bilingual grammar rule pairs for a given pair of languages, referred to as the required set of grammar rule pairs, comprising the steps:

(a) acquiring a first set of phrases in a first of the pair of languages and a corresponding second set of phrases in the second of the pair of languages, said first and second sets of phrases constituting a set of phrase translation pairs in the given pair of languages;
(b) generating a set of grammar rules in respect of said first set of phrases;
(c) generating, by an analysis generator and using said possible grammar rules, for each member of said first set of phrases, a predetermined number of analyses;
(d) ascertaining, for each of the analyses, the respective alternations thereof;
(e) applying steps (b) to (d) to said second set of phrases, mutatis mutandi, and
(f) ascertaining each alternation of the respective alternations of said first set of phrases which is aligned with an alternation of the respective alternations of said second set of phrases, each such aligned pair of alternations being referred to as an alternation pair;
(g) ranking the alternation pairs in accordance with a predetermined criterion;
and
(h) making the highest ranking alternation pair or alternation pairs a member or members of a set of selected alternation pairs, and similarly for the next highest ranking alternation pair or alternation pairs, and so on, and ceasing when the set of selected alternation pairs acting as grammar rule pairs has become sufficient such that for each member of the set of phrase translation pairs there exists, for each of the phrases of the particular member, at least one analysis corresponding to the set of selected alternation pairs whereupon the current list of selected alternation pairs is then deemed to be the required set of grammar rule pairs.

6 more elements

Apparatus for generating a set of bilingual grammar rule pairs for a given pair of languages, referred to as the required set of grammar rule pairs, comprising:

a store for storing a first set of phrases in a first of the pair of languages and a corresponding second set of phrases in the second of the pair of languages, said first and second sets of phrases constituting a set of phrase translation pairs in the given pair of languages;
a grammar rule generator for generating, for a stored set of phrases, a set of grammar rules in respect of the set of phrases;
an analysis generator arranged to use the generated grammar rules for generating, for each member of the stored set of phrases, a predetermined number of analyses;
means for ascertaining, for each of the analyses, the respective alternations thereof;
means for ascertaining each alternation of the respective alternations of said first set of phrases which is aligned with an alternation of the respective alternations of said second set of phrases, each such aligned pair of alternations being referred to as an alternation pair;
means for forming a list of the alternation pairs ranked in accordance with a predetermined criterion;
and
means for creating the required set of grammar rule pairs by repeated operation of actually or effectively transferring the current highest ranking alternation pair or alternation pairs from the ranked list of alternation pairs to a list of grammar rule pairs and then checking whether there exists, for each phrase of each member of the stored set of phrase translation pairs, at least one analysis corresponding to that list of grammar rule pairs, and being arranged to cease operation upon a positive outcome of that check, the said list of grammar rule pairs being then deemed to be the required set of grammar rule pairs.

5 more elements

Dependencies are inferred from the claim text.

Induction of grammar rules

Life of this patent

Induction of grammar rules

Life of this patent

Abstract

Claims26