Data processing: speech signal processing – linguistics – language – Linguistics – Natural language
Reexamination Certificate
1999-05-05
2001-08-14
Thomas, Joseph (Department: 2644)
Data processing: speech signal processing, linguistics, language
Linguistics
Natural language
C704S255000, C704S257000, C704S275000
Reexamination Certificate
active
06275792
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
(Not Applicable)
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
(Not Applicable)
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates to the field of computer speech recognition and more particularly to a method and system for generating a minimal set of test phrases for testing a natural commands grammar.
2. Description of the Related Art
Speech recognition, also referred to as speech-to-text, is the technology that enables a computer to transcribe spoken words into computer recognized text equivalents. In practice, speech recognition has been employed in spoken command recognition and dictation. Spoken command recognition finds its greatest utility when incorporated in computer game applications, multimedia titles, and application navigation programs. Spoken command recognition can support the recognition of single words or short phrases spoken with continuous speech, such as “Open File”. In contrast, the dictation function is most evident in word processing and document generation applications.
During the past decade there has been significant progress in the development of speech recognition systems. In consequence of technical advances in speech modeling techniques and recognition search strategies combined with the increased processing power of workstations and personal computers, large vocabulary continuous speech recognition is now feasible. In conjunction with advances in Natural Language Understanding (NLU), these new technical capabilities have made possible the incorporation of more natural styles of human-computer verbal interactions.
NLU technology represents the next generation of speech technology to come to market. Specifically, NLU technology permits a computer to understand the meaning of spoken or typed words. Moreover, NLU can render possible a computer's understanding of a query or statement put forth in natural human language. Simply put, using NLU technology a computer can understand not merely spoken words, but the meaning behind each spoken word. Software applications that seek to exploit this technology include expert systems, applications having user “wizards”, database access systems for problem resolution, database search engines including the Internet, and combined query and response systems.
Related to NLU technology, natural command grammars bridge the gap between the simple command grammar and the NLU technology of the future. Natural command grammars, to some extent, represent the middle ground between the simple command grammar and NLU. Specifically, the natural command grammar is a finite state grammar that allows NLU-like flexibility in the number of allowable expressions per function. Presently, the nature of continuous speech recognizers necessitates a grammar's specification of every possible utterance potentially provided to the application. Significantly, the constraints on word choice imposed by these grammars can reduce perplexity and, accordingly, can lower the recognition error rate.
Although there are a number of approaches to structuring a natural commands grammar, the recognizer grammar commonly specified using Backus-Naur Form (BNF) seems most logical and has become widely used. The structure of the BNF grammar has comments, a root node branching out to sentence set nodes, sentence set nodes that branch out to sentences, or natural commands, variables in sentences that connect to phrase nodes, and a translation rule at the end of each line of grammar. It is the translation rule that translates the natural command into a functional statement which can be used by a back-end program to execute the program's functions without requiring a separate parsing program.
While simple grammars are relatively easy to develop and test, more complex grammars, including NLU and natural command grammars, are very difficult to develop and test comprehensively. For natural command grammars, the number of valid commands is for all practical purposes infinite, precluding exhaustive testing. Hence, testing every possible phrase in a natural commands grammar to verify correct interpretation by a translation rule interpreter, or other parsing technique, can be extraordinarily difficult and extremely inefficient. Current methods provide only for manual testing of each translation rule. Moreover, manual testing has proven error prone and time consuming. No present method can automatically create a minimum set of test sentences.
SUMMARY OF THE INVENTION
The invention concerns a method and system for automatically generating a minimal set of test phrases for testing a natural commands grammar. The invention as taught herein has advantages over all known methods now used to produce test cases for a natural commands grammar, and provides a novel and nonobvious system, including apparatus and method, for automatically generating a minimal set of test phrases for testing a natural commands grammar. The method involves selecting a line of text, the line having a valid phrase for the natural commands grammar and a translation rule for translating the valid phrase into a functional statement; forming a test phrase for the selected line of text; detecting a previous inclusion of the test phrase in the minimal set of test phrases; and, adding the test phrase to the minimal set of test phrases only if the test phrase has not been previously included in the minimal set of test phrases.
Additionally, the forming step can include identifying the selected line as either a sentence line or sub-sentence line; searching the natural commands grammar for a sentence line having a valid phrase incorporating the identified sub-sentence line; repeating the searching step and the determining step if the sentence line found in the searching step is determined to have been previously considered in the searching step; and, composing a test phrase from the valid phrase of the sentence line found in the searching step. As part of the forming step, the composing step can comprise determining whether the sentence line is a terminal node or non-terminal node; extracting from the sentence line of a node determined to be non-terminal, each variable incorporated in the sentence line; obtaining a valid phrase from each sub-sentence line corresponding to each extracted variable; combining each valid phrase obtained in the obtaining step with the valid phrase of the selected sentence line determined to be a non-terminal node in the determining step; and, designating the combined valid phrase as a test phrase. Finally, the detecting step can include detecting the test phrase in the minimal set of test phrases; and, determining a previous use of the test phrase detected in the minimal set of test phrases.
REFERENCES:
patent: 5642519 (1997-06-01), Martin
patent: 5664173 (1997-09-01), Fast
patent: 5754860 (1998-05-01), McKeeman et al.
patent: 5802370 (1998-09-01), Sitbon et al.
patent: 5970451 (1999-10-01), Lewis et al.
patent: 5991712 (1999-11-01), Martin
patent: 5995918 (1999-11-01), Kendall et al.
patent: 6094635 (2000-07-01), Scholz et al.
patent: 6115820 (2000-09-01), Lewis
International Business Machines Corp.
Senterfitt Akerman
Thomas Joseph
LandOfFree
Method and system for generating a minimal set of test... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for generating a minimal set of test..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for generating a minimal set of test... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2496468