## 3 Estimating the Rule Probabilities  
When given a set of training data \(\mathcal{T}\) of either full-parse trees of the grammar or words from the language generated by it, we want to train the grammar according to the maximum likelihood principle, _i.e._, choose rule probabilities such that  
1. the grammar is consistent and
2. the likelihood \(L(\mathcal{T}\text{;}\,\mathcal{P}):=\prod_{t\in\mathcal{T}}\mathcal{P}(f)\) is maximised among all sets of probabilities that satisfy 1. For (non-length-dependent) SCFGs it is well known how this can be achieved [11, 12]:  
* If we are training from full-parse trees the relative frequencies with which the rules occur (among all rules with the same left-hand side) are a maximum-likelihood estimator. * When given a training set of words from \(L(\mathcal{G})\), the rule probabilities can be estimated using the inside-outside algorithm. This algorithm roughly works as follows: Given an initial estimate of the rule probabilities it uses a modified version of the parsing algorithm to determine for each word \(w\) in the training set, each subword \(w_{i,j}\) of \(w\) and each rule \(r\in\mathcal{R}\) the total probability of all full-parse trees for \(w\) that derive \(w_{i,j}\) in a subtree starting with \(r\). Summing up these probabilities for all subwords it gets expected numbers of rule occurrences from which expected relative frequencies can be computed as in the case of given parse trees. By using these expected relative frequencies as a new estimate for the rule probabilities and iterating the procedure we are guaranteed to converge to a set of rule probabilities that gives a (local) maximum likelihood. Both algorithms can easily be converted for LSCFGs: Instead of determining the (actual resp. expected) number of occurrences for each rule globally we determine separate counts for each length interval and use these to compute separate (expected) relative frequencies. This works since each occurrence (resp. probability of occurrence) is tied to a specific subword and thus associated a length. What remains to be shown is that the modified versions of the algorithms still provide rule probabilities that yield consistent grammars and maximize the likelihood. Our proof is based on the observation that an LSCFG is equivalent to an indexed grammar where each intermediate symbol \(A\) is split into a set of indexed symbols \(\mathcal{A}_{i}\) and each rule \(A\rightarrow\quad\) is split into a set of rules \(\mathcal{A}_{i}\rightarrow\quad\), where runs over all possible ways to index the intermediate symbols in such that the sum of the indices plus the number of terminal symbols in is _i._ In this grammar we can derive from each symbol \(\mathcal{A}_{i}\) exactly those words that can be derived from \(A\) in the original grammar and have length \(l\). This indexed grammar is not context-free since it contains infinitely many intermediate symbols and rules but it can be converted into an SCFG by removing all symbols and rules with indices larger than some threshold \(n\) (thereby losing the possibility to generate words longer than \(n\)) and adding a new axiom \(S\) along with rules \(S\to S_{i}\) with probabilities \(P_{\ell}(l)\) (rescaled so they sum to 1). For technical reasons the following formal definition will introduce one additional modification: The rules \(\mathcal{A}_{i}\rightarrow\quad\) are split into two rules \(\mathcal{A}_{i}\rightarrow\mathcal{A}_{\alpha,i}\) with the probability \(P(A\rightarrow\quad:l)\) and \(\mathcal{A}_{\alpha,i}\rightarrow\quad\) with the probability \(p_{\alpha,i}\) (where is the unindexed counterpart of ). This reflects the distinction between  
Intuitively to satisfy this condition we may not group lengths / and / together if there is a rule that can lead to a word of length / but not to one of length / (or vice versa). Note that the partitioning into sets of one element each, which corresponds to not grouping lengths into intervals at all is trivially consistent with each CFG \(G\).