Method of determining sequences of terminals or of terminals and wildcards belonging to non-terminals of a grammar

• US 20030061024A1
• Filed: 09/13/2002
• Published: 03/27/2003
• Est. Priority Date: 09/18/2001
• Status: Abandoned Application

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Martin, Sven C.
• Application Number:
  US10/242,928
• Publication Number:
  US 20030061024A1
• Time in Patent Office: Days
• US Class Current: 704/4
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

The invention relates to a method of determining sequences of terminals or of terminals and wildcards linked to non-terminals of a grammar in a training corpus of sentences concerning which it is known in each case which non-terminals of the grammar they contain, with the following steps:

determination of sequences of terminals or of terminals and wildcards, and

assignment of the sequences of terminals or of terminals and wildcards to a non-terminal or no non-terminal by means of a classification procedure.

A procedure of this kind may be used, for example, for the automatic learning of the word sequences linked to a semantic grammar in an automated dialog system.

Claims

1. A method of determining sequences of terminals or of terminals and wildcards linked to non-terminals of a grammar in a training corpus of sentences concerning which it is known in each case which non-terminals of the grammar they contain, with the following steps:

determination of sequences of terminals or of terminals and wildcards, and

assignment of the sequences of terminals or of terminals and wildcards to a non-terminal or no non-terminal by means of a classification procedure.

2. A method as claimed in claim 1, characterized in that the sequences of terminals or of terminals and wildeards are purely terminal sequences.

3. A method as claimed in claim 1, characterized in that, in determining the sequences of terminals or of terminals and wildcards, account is taken of the relative frequency of the occurrence of the sequences in the training corpus.

4. A method as claimed in claim 1, characterized in that the assignment of the sequences of terminals or of terminals and wildcards to a non-terminal or no non-terminal is determined iteratively by minimization of the function

5. A method as claimed in claim 1, characterized in that the assignment of the sequences of terminals or of terminals and wildcards to a non-terminal or no non-terminal takes place by means of classification using the exchange procedure.

6. A method as claimed in claim 5, characterized in that the exchange procedure checks the sequences of terminals or of terminals and wildcards for changes in their assignment to a non-terminal or no non-terminal in the order of their frequency in the training corpus.

7. A method as claimed in claim 1, characterized in that, following an assignment of the sequences of terminals or of terminals and wildcards, a sequence comprising two sub-sequences of terminals or of terminals and wildcards, one of which is assigned in precisely the same way as and the other of which is assigned differently from the sequence itself, is removed from the set of sequences determined.

8. A method as claimed in claim 7, characterized in that, after removal of the sequence consisting of two sub-sequences of terminals or of terminals and wildcards, one of which is assigned in precisely the same way as and the other of which is assigned differently from the sequence itself, the respective assignments of the sequences of terminals or of terminals and wildcards to a non-terminal or no non-terminal are repeated.

9. A system for determining sequences of terminals or of terminals and wildcards linked to non-terminals of a grammar in a training corpus of sentences concerning which it is known in each case which non-terminals of the grammar they contain, which is provided:

for determining sequences of terminals or of terminals and wildcards, and

for the assignment of sequences of terminals or of terminals and wildcards to a non-terminal or no non-terminal by means of a classification procedure.

10. Sequences of terminals or of terminals and wildcards linked to non-terminals of a grammar, which have been determined by means of a method comprising the steps:

determination of sequences of terminals or of terminals and wildcards, and

assignment of sequences of terminals or of terminals and wildcards to a non-terminal or no non-terminal by means of a classification procedure, in a training corpus of sentences concerning which it is known in each case which non-terminals of the grammar they contain.