Prefix Probability for Probabilistic Synchronous Context-Free Grammars
Nederhof, Mark-Jan and Satta, Giorgio

Article Structure

Abstract

We present a method for the computation of prefix probabilities for synchronous context-free grammars.

Introduction

Within the area of statistical machine translation, there has been a growing interest in so-called syntax-based translation models, that is, models that define mappings between languages through hierarchical sentence structures.

Definitions

In this section we introduce basic definitions related to synchronous context-free grammars and their probabilistic extension; our notation follows Satta and Peserico (2005).

Effective PSCFG parsing

If 21) = a1 - - - an then the expression w[z’, j], with 0 S i g j g n, denotes the substring ai+1 - - - a,- (if i = j then w[z’, j] = 5).

Prefix probabilities

The joint prefix probability pgefixflvl, 212]) of a

Discussion

We have shown that the computation of joint prefix probabilities for PSCFGs can be reduced to the computation of inside probabilities for the same model.

Topics

probability distribution

Appears in 8 sentences as: probability distribution (5) probability distributions (3)
In Prefix Probability for Probabilistic Synchronous Context-Free Grammars
  1. Prefix probabilities can be used to compute probability distributions for the next word or part-of-speech.
    Page 1, “Introduction”
  2. Prefix probabilities and right prefix probabilities for PSCFGs can be exploited to compute probability distributions for the next word or part-of-speech in left-to-right incremental translation, essentially in the same way as described by Jelinek and Lafferty (1991) for probabilistic context-free grammars, as discussed later in this paper.
    Page 2, “Introduction”
  3. Intuitively, propemess ensures that where a pair of nonterminals in two synchronous strings can be rewritten, there is a probability distribution over the applicable rules.
    Page 3, “Definitions”
  4. We say a PSCFG is consistent if pg defines a probability distribution over the translation, or formally:
    Page 3, “Definitions”
  5. The translation and the associated probability distribution in the resulting grammar will be the same as those in the source grammar.
    Page 5, “Effective PSCFG parsing”
  6. Again, in the resulting grammar the translation and the associated probability distribution will be the same as those in the source grammar.
    Page 6, “Effective PSCFG parsing”
  7. The next step will be to transform Qprefix into a third grammar gl’mfix by eliminating epsilon rules and unit rules from the underlying SCFG, and preserving the probability distribution over pairs
    Page 6, “Prefix probabilities”
  8. Prefix probabilities and right prefix probabilities for PSCFGs can be exploited to compute probability distributions for the next word or part-of-speech in left-to-right incremental translation of speech, or alternatively as a predictive tool in applications of interactive machine translation, of the kind described by Foster et al.
    Page 9, “Discussion”

See all papers in Proc. ACL 2011 that mention probability distribution.

See all papers in Proc. ACL that mention probability distribution.

Back to top.

parsing algorithm

Appears in 6 sentences as: parsing algorithm (3) parsing algorithms (3)
In Prefix Probability for Probabilistic Synchronous Context-Free Grammars
  1. Computation of inside probabilities for PSCFGs is a well-known problem that can be solved using off-the-shelf algorithms that extend basic parsing algorithms .
    Page 2, “Introduction”
  2. This contrasts with the techniques proposed by J elinek and Lafferty (1991) and by Stolcke (1995), which are extensions of parsing algorithms for probabilistic context-free grammars, and require considerably more involved proofs of correctness.
    Page 2, “Introduction”
  3. The recognition algorithm above can easily be turned into a parsing algorithm by letting an implementation keep track of which items were derived from which other items, as instantiations of the consequent and the antecedents, respectively, of the inference rule in figure 1.
    Page 4, “Effective PSCFG parsing”
  4. A probabilistic parsing algorithm that computes pg([w1, 1112]), defined in (1), can also be obtained from the recognition algorithm above, by associating each item with a probability.
    Page 4, “Effective PSCFG parsing”
  5. Computing paprefixflvl, 212]) directly using a generic probabilistic parsing algorithm for PSCFGs is difficult, due to the presence of epsilon rules and unit rules.
    Page 6, “Prefix probabilities”
  6. apply generic probabilistic parsing algorithms for PSCFGs, such as the inside algorithm discussed in section 3, in order to compute the desired prefix probabilities for the source PSCFG Q.
    Page 7, “Prefix probabilities”

See all papers in Proc. ACL 2011 that mention parsing algorithm.

See all papers in Proc. ACL that mention parsing algorithm.

Back to top.

part-of-speech

Appears in 5 sentences as: part-of-speech (5)
In Prefix Probability for Probabilistic Synchronous Context-Free Grammars
  1. Prefix probabilities can be used to compute probability distributions for the next word or part-of-speech .
    Page 1, “Introduction”
  2. Prefix probabilities and right prefix probabilities for PSCFGs can be exploited to compute probability distributions for the next word or part-of-speech in left-to-right incremental translation, essentially in the same way as described by Jelinek and Lafferty (1991) for probabilistic context-free grammars, as discussed later in this paper.
    Page 2, “Introduction”
  3. Prefix probabilities and right prefix probabilities for PSCFGs can be exploited to compute probability distributions for the next word or part-of-speech in left-to-right incremental translation of speech, or alternatively as a predictive tool in applications of interactive machine translation, of the kind described by Foster et al.
    Page 9, “Discussion”
  4. However, one may also compute the probability that the next part-of-speech in the target translation is A.
    Page 9, “Discussion”
  5. This can be realised by adding a rule 3’ : [B —> b, A —> CA] for each rule 3 : [B —> b, A —> a] from the source grammar, where A is a nonterminal representing a part-of-speech and CA is a (pre-)terminal specific to A.
    Page 9, “Discussion”

See all papers in Proc. ACL 2011 that mention part-of-speech.

See all papers in Proc. ACL that mention part-of-speech.

Back to top.

machine translation

Appears in 3 sentences as: machine translation (3)
In Prefix Probability for Probabilistic Synchronous Context-Free Grammars
  1. Within the area of statistical machine translation , there has been a growing interest in so-called syntax-based translation models, that is, models that define mappings between languages through hierarchical sentence structures.
    Page 1, “Introduction”
  2. One should add that, in real world machine translation applications, it has been observed that recognition (and computation of inside probabilities) for SCFGs can typically be carried out in low-degree polynomial time, and the worst cases mentioned above are not observed with real data.
    Page 9, “Prefix probabilities”
  3. Prefix probabilities and right prefix probabilities for PSCFGs can be exploited to compute probability distributions for the next word or part-of-speech in left-to-right incremental translation of speech, or alternatively as a predictive tool in applications of interactive machine translation , of the kind described by Foster et al.
    Page 9, “Discussion”

See all papers in Proc. ACL 2011 that mention machine translation.

See all papers in Proc. ACL that mention machine translation.

Back to top.

PDF available from www.aclweb.org.
Send us an email