METHOD FOR SYMBOLIC CORRECTION IN HUMAN-MACHINE INTERFACES

• US 20120323560A1
• Filed: 06/14/2012
• Published: 12/20/2012
• Est. Priority Date: 06/16/2011
• Status: Active Grant

• Current Assignee: Asociacion Instituto Tecnológico de Informática
• Original Assignee: Association Instituto Tecnologico de Informatica
• Inventors: Pérez Cortés, Juan Carlos, Llobet Azpitarte, Rafael, Navarro Cerdán, José Ramón, Arlandis Navaro, Joaquim Francesc
• Granted Patent: US 9,201,862 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

Disclosed embodiments include methods and systems for symbolic correction in human-machine interfaces that comprise (a) implementing a language model; (b) implementing a hypothesis model; (c) implementing an error model; and (d) processing a symbolic input message based on weighted finite-state transducers to encode 1) a set of input hypothesis using the hypothesis model, 2) the language model, and 3) the error model to perform correction on the sequential pre-segmented symbolic input message in the human-machine interface. According to a particular embodiment, the processing step comprises a combination of the language model, the hypothesis model, and the error model performed without parsing by employing a composition operation between the transducers and a lowest cost path search, exact or approximate, on the composed transducer.

Claims

1. A method for symbolic correction in human-machine interfaces said method comprising:

(a) implementing a language model;

(b) implementing a hypothesis model;

(c) implementing an error model; and

(d) processing a symbolic input message using a hardware processor, said processing based on weighted finite-state transducers to encode

     1) a set of input hypothesis using said hypothesis model,

     2) said language model, and

     3) said error model in order to perform correction on said symbolic input message in the human-machine interface.

2. The method of claim 1, wherein said processing comprises a combination of said language model, said hypothesis model, and said error model performed without parsing by employing a composition operation between said transducers to generate a composed transducer, as well as a lowest cost path search on said composed transducer.

3. The method of claim 2, wherein said language model uses a grammatical inference algorithm.

4. The method of claim 3, wherein said grammatical inference algorithm is designed to accept a smallest k-Testable Language in the Strict Sense (k-TS language).

5. The method of claim 4, wherein said hypothesis model is based on a weighted finite-state transducer that dynamically models the uncertainty of a symbol-input subsystem.

6. The method of claim 5, wherein said error model complements said hypothesis model incorporating a static model of the uncertainty of said symbol-input subsystem.

7. The method of claim 6, wherein said error model complements said hypothesis model by incorporating a static model of the uncertainty of said symbol-input subsystem including a plurality of edit operations.

8. The method of claim 7, wherein said plurality of edit operations include substitutions, insertions, and deletions.

9. The method of claim 8, wherein said method for symbolic correction in human-machine interfaces includes a probability of transition of the form P(t)=P(LM, EM, HM|t)=P(LM|t)P(EM|t)P(HM|t) and employs tropical semiring WFSTs (, ⊕

, , 0, 1).

10. A symbolic correction apparatus for human-machine interfaces comprising:

(a) a memory to store a language model, a hypothesis model, and an error model, and

(b) a processor configured for processing a symbolic input message, said processing based on weighted finite-state transducers to encode

     1) a set of input hypothesis using said hypothesis model,

     2) said language model, and

     3) said error model in order to perform correction on said symbolic input message in the human-machine interface.

11. The symbolic correction apparatus 10, wherein said processing comprises a combination of said language model, said hypothesis model, and said error model performed without parsing by employing a composition operation between said transducers to generate a composed transducer, as well as a lowest cost path search on said composed transducer.

12. The symbolic correction apparatus 10, wherein said language model uses a grammatical inference algorithm.

13. The symbolic correction apparatus 11, wherein said grammatical inference algorithm is designed to accept a smallest k-Testable Language in the Strict Sense (k-TS language).

14. The symbolic correction apparatus 12, wherein said hypothesis model is based on a weighted finite-state transducer that dynamically models the uncertainty of a symbol-input subsystem.

15. The symbolic correction apparatus 13, wherein said error model complements said hypothesis model incorporating a static model of the uncertainty of said symbol-input subsystem.

16. The symbolic correction apparatus 14, wherein said error model complements said hypothesis model by incorporating a static model of the uncertainty of said symbol-input subsystem including a plurality of edit operations.

17. The symbolic correction apparatus 15, wherein said plurality of edit operations include substitutions, insertions, and deletions.

18. The symbolic correction apparatus 16, wherein said method for symbolic correction in human-machine interfaces includes a probability of transition of the form P(t)=P(LM, EM, HM|t)=P(LM|t)P(EM|t)P(HM|t) and employs tropical semiring WFSTs (, ⊕

, , 0, 1).

19. A non-transitory computer-readable storage medium with an executable program stored thereon to implement symbolic correction in human-machine interfaces, wherein said executable program instructs an apparatus to perform the following steps:

(a) implementing a language model;

(b) implementing a hypothesis model;

(c) implementing an error model; and

(d) processing a symbolic input message, said processing based on weighted finite-state transducers to encode

     1) a set of input hypothesis using said hypothesis model,

     2) said language model, and

     3) said error model in order to perform correction on said symbolic input message in the human-machine interface.

20. The non-transitory computer-readable storage medium of claim 19, wherein (a) said processing comprises a combination of said language model, said hypothesis model, and said error model performed without parsing by employing a composition operation between said transducers to generate a composed transducer, as well as a lowest cost path search on said composed transducer;

(b) said language model uses a grammatical inference algorithm;

(c) said grammatical inference algorithm is designed to accept a smallest k-Testable Language in the Strict Sense (k-TS language);

(d) said hypothesis model is based on a weighted finite-state transducer that dynamically models the uncertainty of a symbol-input subsystem;

(e) said error model complements said hypothesis model incorporating a static model of the uncertainty of said symbol-input subsystem;

(f) said error model complements said hypothesis model by incorporating a static model of the uncertainty of said symbol-input subsystem including a plurality of edit operations;

(g) said plurality of edit operations include substitutions, insertions, and deletions; and

(h) said method for symbolic correction in human-machine interfaces includes a probability of transition of the form P(t)=P(LM, EM, HM|t)=P(LM|t)P(EM|t)P(HM|t) and employs tropical semiring WFSTs (, ⊕

, , 0, 1).