# Split-Based Algorithm for Weighted Context-Free Grammar Induction
## 2 Weighted Grammar-Based Classifier System
### Rule Weight Estimation
#### 2.5.1 Inside-Outside  
[PERSON] introduced the inside-outside algorithm [21]. Its computational complexity is \(O(L^{3}|N|^{3})\), where \(L\) is the sentence length and \(|N|\) is the number of nonterminal symbols in the grammar [22].  
The inside-outside algorithm starts the estimation process from the initial probabilities/weights of the rules (usually assigned randomly). At each iterative step, it updates the probability/weight of the rule based on the frequency of the rule in the training set. To better understand the algorithm, let us introduce the basic nomenclature.  
* **Probability/weight of the rule**:
* for nonterminal rules: \(\phi(X\to YZ)\)
* for terminal rules: \(\phi(X\to x)\)
* **Probability/weight of deriving a sentence from grammar**: \[P(W)=P(S\Rightarrow w_{1}w_{2}\ldots w_{n})\] (1) where \(\Rightarrow\) stands for sentence derivation, \(W\) stands for sentence output, and \(w_{1}w_{2}\ldots w_{n}\) are the individual words of the sentence \(W\).
* **The inside probability*
* is the probability of deriving from a given symbol the nonterminal sequence of words \(w_{i}\ldots w_{j}\) from the sentence \(W=w_{1}\ldots w_{n}\): \[\beta_{ij}(X)=P(X\Rightarrow w_{i}\ldots w_{j})\] (2) where \(X\) is any nonterminal grammar symbol. Figure 3 shows the graphical interpretation of the inside probability for the nonterminal Y symbol, \(\beta_{ij}(Y)\).
* **The outside probability*
* is the probability of deriving from the starting symbol the string \(w_{1}\ldots w_{i-1}Xw_{j+1}\ldots w_{n}\) from the sentence \(W=w_{1}\ldots w_{n}\): \[\alpha_{ij}(X)=P(S\Rightarrow w_{1}\ldots w_{i-1}Xw_{j+1}\ldots w_{n})\] (3) Figure 4 shows the graphical representation of the outside probability for the nonterminal symbol \(Y\), \(\alpha_{ij}(Y)\).
* **Estimated number of uses of the rule*
* determines how often the rule occurs for a single sentence:  
Figure 4: Graphical representation of the outside probability.  
Figure 3: Graphical representation of the inside probability.  
for terminal rules: \[c_{\phi}(X\to x,W)=\frac{\phi(X\to x)}{P(W)}\sum_{i\leq 1}\beta_{ii}(X)\] (4) for nonterminal rules: \[c_{\phi}(X\to YZ,W)=\frac{\phi(X\to YZ)}{P(W)}\sum_{1\leq i\leq j\leq k\leq n} \alpha_{ik}(X)\beta_{ij}(Y)\beta_{j+1,k}(Z)\] (5)
* **The total estimated number of uses of the rule** determines how often the rule occurs in all sentences in the training set: \[count(X\to\alpha)=\sum_{i=1}^{n}c_{\phi}(X\to\alpha,W_{i})\] (6) where \(X\to\alpha\) stands for a terminal or nonterminal rule and \(W_{i}\) for successive sentences in the training set.
* **The new weight/probability of a rule** is calculated as the ratio of the total estimated uses of a given rule to the sum of the estimated total uses of a rule with the same left-hand symbol: \[\phi^{{}^{\prime}}(X\to\alpha)=\frac{count(X\to\alpha)}{\sum_{\gamma}count(X \to\gamma)}\] (7) where \(X\to\gamma\) stands for a rule with the same left-hand side symbol as the rule in the numerator and any right-hand side form (\(gamma\)) of a rule in a CNF, either a terminal symbol or two nonterminal symbols.