# Split-Based Algorithm for Weighted Context-Free Grammar Induction
## 2 Weighted Grammar-Based Classifier System
### Split Algorithm  
This method is based on [19; 20], where grammar is induced incrementally. During each iteration of the algorithm, a new \(X_{j}\) nonterminal symbol is created from another \(X_{i}\) nonterminal symbol through a split operation. The symbol selected for the split operation is the symbol most often used in rule weight estimation (having the largest count) (see line 2 in Algorithm 2). This symbol is generally called the split symbol. Then, for all \(X_{i}\to t\) terminal rules, we create new terminal rules, replacing \(X_{i}\) with \(X_{j}\) (see lines 3-5 in Algorithm 2). Next, new nonterminal rules are created in two ways:  
1. For symbols \(X_{i}\) and \(X_{j}\), create all possible rules (see line 6 in Algorithm 2). Since the rules are in CNF, their number is 8. 2. For all nonterminal rules with \(X_{i}\) in the form \(X_{a}\to X_{b}X_{c}\), where \(X_{a},X_{b}\) or \(X_{c}\) is \(X_{i}\), create new untimely rules in the same form, replacing \(X_{i}\) with \(X_{j}\). For multiple occurrences of \(X_{i}\) in a rule, create all combinations (see lines 7-20 in Algorithm 2). ```
1:Load the sentence and grammar
2:\(L\leftarrow\) sentence length
3:\(|N|\leftarrow\) number of nonterminal symbols
4:Create an array \(\text{CKY}[L][L]\)
5:Create an array \(\text{wCKY}[L][L][|N|]\)
6:
7:for\(i\gets 1\) to \(L\)do
8:for\(w_{i}\) in sentencedo\(\triangleright\)sentence \(=w_{1}\dots w_{L}\)
9:for\(A\to w_{i}\) in \(TR\)do\(\triangleright\)\(TR=\)terminal rules
10: write \(A\) in \(\text{CKY}[i][1]\)
11: write \(\phi(A\to w_{i})\) in \(\text{wCKY}[i][1][A]\)\(\triangleright\) rule weight
12:endfor
13:endfor
14:endfor
15:
16:for\(i\gets 2\) to \(L\)do
17:for\(j\gets 1\) to \(L-i+1\)do
18:for\(k\gets 2\) to \(i-1\)do
19:for\(A\to BC\) in \(NR\)do\(\triangleright\)\(NR=\)non-terminal rules
20:if\(\text{wCKY}[i][k][B]>0\)and\(\text{wCKY}[k][j][C]>0\)then
21: write \(A\) in \(\text{CKY}[i][j]\)
22: write \(\phi(A\to BC)\times\text{wCKY}[i][k][B]\times\text{wCKY}[k][j][C]\) in \(\text{wCKY}[i][j][A]\)
23:endif
24:endfor
25:endfor
26:endfor
27:endfor
```  
**Algorithm 1** Stochastic CKY  
To illustrate the split method, suppose there is the set of rules: \(R=\{Y\to BC,Y\to YC,B\to DY,S\to YY,Y\to a,B\to b,Y\to b\}\), the set of nonterminals \(N=\{Y,B,C,D\}\), the set of terminals \(T=\{a,b\}\), and the start symbol \(S\). We select the symbol with the largest count (let it be \(Y\)) and create a new symbol--a split symbol--\(Z\). According to the lines 3-5 of the Algorithm 2, new terminal rules are generated: \(\{Z\to a,Z\to b\}\). The new nonterminal rules are generated as follows. 1. From \(Y\) and split symbol \(Z\) create: \(Y\to YY\), \(Y\to YZ\), \(Y\to ZY\), \(Y\to ZZ\), \(Z\to ZZ\), \(Y\to YZ,Z\to ZY,Z\to YY\) (line 6 of Algorithm 2). 2. From \(\{Y\to BC,B\to DY\}\) create new following rules \(\{Z\to BC,B\to DZ\}\) and from \(\{Y\to YC,S\to YY\}\) rules \(\{Z\to ZC,Z\to YC,Y\to ZC,S\to ZZ,S\to ZY,S\to YZ\}\) (lines 7-21 of Algorithm 2). The result is: \(R=\{Y\to YY,Y\to YZ,Y\to ZY,Y\to ZZ,Y\to ZZ,Z\to ZZ,Z\to ZY,Z\to YY,Z\to ZC,Z\to YC,S\to ZZ,S\to ZZ,S\to YY,S\to YZ,Y\to BC,Y\to YC,B\to DY,S\to YY,Y\to a,B\to b,Y\to b,Z\to a,Z\to b\}\), \(N=\{Z,Y,B,C,D\}\), \(T=\{a,b\}\), \(S=S\).