Tag Archives: sentence generation

Grammar problem #1 – repeated tokens

It is quite easy to write a speech recognition grammar. After all, it’s only a text file. And with the help of a good editor, we can expect the grammar to be free of syntax errors, i.e. to conform to the SRGS specification (ABNF or XML).

The real challenge is in making sure that the grammar does not contain any “error” from the point-of-view of the set of sentences it accepts, and the semantic values it associates to these sentences. We also have to make sure that it does not over-generate (accept sentences that are not part of the usual spoken language or cannot be uttered in the context of the question asked).

This post is the first in a series that will show the most common types of errors made when developing grammars and how they can be found and fixed using the advanced features of NuGram IDE. The examples I’ll use are all variants of grammars we’ve seen in the course of our grammar developments projects, either internally or for our customers.

Problem 1: Repeated Tokens

We’ll start this series with a very simple one. Suppose I’m editing a long list of ordered tokens. It is very tempting to copy one of the items and paste it as many times as needed and edit the copies. I do this all the time. It’s such a common pattern in text editing (and programming, unfortunately…) Of course, it is very easy to forget editing one of the copies.

For example, let’s say I want to write a number grammar. I’ll start writing something like:

public $r1To9 =
  one {out.number=1} |

and then copy/paste the first item 8 times, replace “one” by the digits “two” to “nine” and do the same for their corresponding semantic value. I’ll get something like:

public $r1To9 =
  one {out.number=1} |
  two {out.number=2} |
  three {out.number=3} |
  four {out.number=4} |
  five {out.number=5} |
  five {out.number=6} |
  seven {out.number=7} |
  eight {out.number=8} |
  nine {out.number=9}
;

Of course, you’ve already seen the error (probably much faster than I have). It’s easy here since you have the offending fragment right before our eyes. But when developing a grammar with many rules, it may not be that obvious. And even carefully reviewing the grammar may not suffice. (How many times do we miss typos in our own texts that another reviewer finds in a matter of seconds?)

So how do we find the problem? In this case, I simply need to build a coverage test set with the sentence generator using the Tags Coverage strategy. The following video shows how to do that:

Of course, in this example, I knew how to proceed to find the problem. In practice, and this will be a recurring idea in the series, a grammar needs to be tested in many different ways. There are many techniques and tools that need to be applied. The Tags Coverage (or the All Paths) generation strategy is often the first we use. It has the advantage of exercising all the semantic actions and finding lots of potential problems very early on in the debugging process.

In my next post in this series, I’ll write about ambiguities, how they affect speech recognition performance, and how to detect and deal with them.

Effective sentence generation

There has been some activity lately on the Yahoo VUIDs group about the difficulty of generating sentences from a speech recognition grammar. This is a recurrent problem in speech grammar engineering, one that really deserves a full blog post (and maybe more than one), especially since we’ve worked hard on this problem in the last year. So I’ll share my thoughts on this subject.

First, let me surmmarize why this problem is so difficult.

The problem

You have an  ABNF (or GrXML, or GSL) grammar for which you would like to generate sentences. Except if it’s a toy grammar or a small item-list, the grammar will most certainly generate thousands, millions, or even more different sentences, if not an infinite number of them. Why? That’s simple:

  • It can contain repeated items. If you have 10 words repeated 4 times, you have 10,000 sentences. When you have unbounded repeats, of course you get an infinite language.
  • It can contain all sort of filler words, to better handle disfluencies (hesitations, corrections, etc.). When you have those fillers at the start and end of every possible sentence, the number of sentences grows very rapidly. For example, just adding 9 optional filler words at the start and end of every sentences multplies the number of sentences by a factor of 100.

For example, one of our VoiceXML applications has a grammar that generates 29,822,907,679,607,676,696 sentences! (after removing some fillers that would have made the language infinite.) And it’s just a grammar for collecting a building number, albeit a highly tuned one. Pretty standard stuff.

As you have certainly guessed, it is rather impractical to generate all sentences. Are you really interested in reviewing tens of thousands of sentences? Remember that most sentences will only differ in very uninteresting ways (the pre/post fillers, a “two” instead of a “three”, etc.).

What would you want to generate sentences for?

Sentence generation can be helpful in many situations:

  • Grammar coverage. Coverage test sets can be built in many different ways. But one that works very well is to start with the grammar and generate sentences. As you do so, you add some or all of them to the coverage set, either as ING (in-grammar) or OOG (out-of-grammar) sentences.
  • To detect problems. Sentence generation is often an effective way to find potential problems with a grammar. Typical problems are over-generation (which can lead to reduced recognition accuracy) and grammar problems (misplaced parentheses, missing parentheses, misplaced vertical bar, etc.).
  • Application testing. Some people use the generated sentences in manual application test scripts. Automated, text-based testing tools could also use sentence generation to “navigate” an application call flow.

Some available tools

Many, if not most, recognition engine vendors provide tools to generate sentences from a grammar. For example, Nuance 9 comes with parseTool, which lets you generate a fixed number of random sentences from either a GrXML grammar or a compiled grammar.

Those tools, however, are rarely adequate at dealing with a large number of sentences in an effective way. They either exhaustively generate all sentences, or they generate a fixed number of random sentences. As I mentioned above, the exhaustive generation strategy works well only for very simple grammars. The random strategy, on the other hand, doesn’t provide any control mechanisms that enable us to only generate the sentences we want. As a result, we typically end up with mostly redundant sentences in which some sentence patterns are grossly over-represented while others are missing.

Our approach

In NuGram IDE Pro, we have implemented a very different approach to sentence generation. I won’t go into explaining all the details here, but let me emphasize some aspects of our approach:

  • The generation strategies can be configured on a rule-by-rule basis.
  • The generation algorithm can be started on arbitrary expansions (sequences of words and rule references) that can be derived from the root rule. These expansions are usually produced by the Sentence Explorer tool.
  • The available strategies are:
    • All sentences – This is the default strategy. As one would expect, it consists in exhaustively generating all the sentences. However, all referenced rules will obey their own strategy.
    • First sentence – This strategy generates a single sentence, the “first” in the document order.
    • Random sentences – This strategy generates a configurable number of random sentences each time the rule is referenced from another rule.
    • Tags coverage – This strategy generates the smallest set of sentences that will cover all the semantic actions in the rule and its referenced rules (and recursively). This is a very effective strategy to build coverage sets to test all the semantic tags in a grammar/rule.
    • All paths – This strategy is a variable of the tags coverage strategy. It generates the smallest set of sentences to cover all the paths in a rule and its referenced rules (and recursively).
    • Rule examples – This strategy consists in using the examples in the rule’s documentation comment. This strategy is dangerous in that it can generate sentences that are not parsable by the grammar if the examples are not changed when the rule is modified.

Here is a screencast showing these concepts in action:

That’s it for now. My next post will be about how to use the sentence generation tool to effectively find common problems with grammars and how to fix them.

And I’d be very interested in knowing how you deal yourself with this problem. So leave me a comment!