# PCFGs

(Redirected from PCFG)

PCFGs are a generative model used in NLP for parsing modeling and syntax analysis. Using this model, data is generated in a branching process where each non-terminal state produces a sequence of states that are visited in a recursive manner. PCFGs are used in a variety of NLP tasks including: grammar checking, lexical learning and machine translation.

## Short definition of CFGs

• Let $\Sigma$ be an alphabet of observable symbols, called terminals.
• Let $N$ be a set of variable symbols, called non-terminals, including a special start symbols, $S\in N$ .
• The grammar also defines a set of derivation rules, $R$ , for transforming terminal symbols into sequences of terminals and non-terminals. The rules are of the form $X\rightarrow \alpha$ , where $X\in N$ and $\alpha \in \{N\cup \Sigma \}^{*}$ .

## Description of PCFGs

PCFGs extend CFGs by defining a multinomial distribution over the set of derivation rules over each terminal symbol.

• Let $R_{X}$ be the set of derivation rules for the non-terminal $X$ (where $X$ is on the left-hand side of the rule).
• Let $\theta _{X}$ be the multinomial distribution defined over $R_{X}$ such that
• $\forall r=X\rightarrow \alpha \ \in R_{X},\ \theta _{r}\geq 0$ • $\sum _{r\in R_{X}}\theta _{r}=1$ ## The Generative Process

The process begins with the special start symbol $S\in N$ . At every consecutive step, if there are any non-terminal symbols left in the generated sequence, a derivation rule is sampled from the distribution of rules for that non-terminal and it is replaced by the the right-hand of the rule which contains some combination of terminal and non-terminal symbols.

The process ends when there are no more non-terminal symbols in the generated sequence.

This generates a sequence of terminals from $\Sigma ^{*}$ . The probability of generating a sequence given a certain derivation tree is simply the product of the probabilities used in that tree.

## Decoding

Decoding PCFGs is done with variants of the Earley and CYK algorithms.

## Relation to HMMs

HMMs are a special type of PCFGs. We can rewrite an HMM as a PCFG as follows:

• Let $N$ , the set of non-terminals, be the set of states $H$ of the HMM, including start ($S\in H$ ) and end ($E\in H$ ) states.
• Let $\pi _{h,h'}$ be the transition probability from state $h$ to state $h'$ , and let $\tau _{h,x}$ be the emission probability of symbol $x$ in state $h$ .

We can now define the following derivation rules:

• $h\rightarrow \tau _{h,x}\cdot \pi _{h,h'}\cdot x\cdot h'$ , where $x\in \Sigma$ , [/itex]h, h' \in H[/itex]
• $S\rightarrow \pi _{S,h}\cdot h$ , for [/itex]h \in H[/itex]
• $E\rightarrow 1\cdot \epsilon$ 