Techniques
A variant of the CYK algorithm finds the Viterbi parse of a sequence for a given SCFG. The Viterbi parse is the most likely derivation (parse) of the sequence by the given SCFG.
The Inside-Outside algorithm is an analogue of the Forward-Backward algorithm, and can be used to compute the total probability of all derivations that are consistent with a given sequence, based on some SCFG. This is equivalent to the probability of the SCFG generating the sequence, and is intuitively a measure of how consistent the sequence is with the given grammar.
The Inside/Outside algorithms can also be used to compute the probabilities that a given production will be used in a random derivation of a sequence. This is used as part of an Expectation-maximization algorithm to learn the maximum likelihood probabilities for an SCFG based on a set of training sequences that the SCFG should model. The algorithm is analogous to that used by hidden Markov models.
Read more about this topic: Stochastic Context-free Grammar
Famous quotes containing the word techniques:
“It is easy to lose confidence in our natural ability to raise children. The true techniques for raising children are simple: Be with them, play with them, talk to them. You are not squandering their time no matter what the latest child development books say about “purposeful play” and “cognitive learning skills.””
—Neil Kurshan (20th century)
“The techniques of opening conversation are universal. I knew long ago and rediscovered that the best way to attract attention, help, and conversation is to be lost. A man who seeing his mother starving to death on a path kicks her in the stomach to clear the way, will cheerfully devote several hours of his time giving wrong directions to a total stranger who claims to be lost.”
—John Steinbeck (1902–1968)