# CYK Parsing over Distributed Representations
## 3 Preliminaries
### Encoding and Using Unary Rules
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Grammar** & **Rules** & **Binary** \\ \hline \(G_{0}\) & 8 & 5 \\ \(G_{1}\) & 25 & 5 \\ \(G_{2}\) & 28 & 8 \\ \(G_{3}\) & 34 & 14 \\ \(G_{4}\) & 41 & 21 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Chomsky normal form grammars used in the experiments. We report the total number of rules and the number of binary rules. As we want to understand whether D-CYK is able to reproduce the original CYK, we use Algorithm 4 to decode \(\textbf{P}_{left}\) into a set \(Dec(\textbf{P}_{left})\) of triples of the form \((i,j,A)\). This set represents the parsing table computed by algorithm D-CYK, as already described in Section 4.1. ```
1:for\(i\gets 0\) to \(n-1\)do
2:for\(j\gets i+1\) to \(n\)do
3:for each \(A\) in \(NT\)do
4:if\(\sigma([A]^{\oplus}[j]^{\oplus}[i]^{\oplus}\textbf{P}_{left})_{0,0}>0.99\)then
5: add \(A\) to \(P[i,j]\)
6:endif
7:endfor
8:endfor
9:endfor
```

**Algorithm 4** Dec(\(\textbf{P}_{left}\)) **return** table \(P\)

Set \(Dec(\textbf{P}_{left})\) and the set of triples representing the parse table \(P\) obtained by applying the traditional CYK algorithm on the same grammar and string are then compared by evaluating precision and recall, considering \(P\) as the oracle, and combining the two scores in the usual way into the \(F1\)-measure (\(F1\)). \(F1\) measures how much the decoding of matrix \(\textbf{P}_{left}\) is similar to the original parsing table \(P\). We experiment with six different dimensions \(d\) for matrix \(\textbf{P}_{left}\): 100, 1000, 2000, 3000, 4000, 5000, and 6000. ### Results and Discussion

For grammar \(G_{0}\) and for strings of length \(\leq\) 7, Figure 3 shows that, as the dimension \(d\) of matrix \(\textbf{P}_{left}\) increases, D-CYK can approximate more precisely the information computed by the traditional CYK algorithm, as attested by the increase of measure \(F1\). The increase of \(F1\) is mainly due to an improvement in precision, while recall is substantially stable. On the downside, the length of the input string affects the accuracy of D-CYK. This is seen in Figure 4, reporting several tests on grammar \(G_{0}\) for different dimensions \(d\). Even for our highest

Figure 3: \(F1\) vs. dimension \(d\) on strings with length \(\leq\) 7 and grammar \(G_{0}\). dimension \(d=6000\), there is a 20% drop in accuracy, as measured by \(F1\), for strings of length eight. The size of the grammar is also a major problem. In fact, the accuracy of the D-CYK algorithm is affected by the number of rules/nonterminals for increasingly larger grammars \(G_{1}\) to \(G_{4}\), as shown in Figure 5.

In addition to these results, we also experimented with a seq2 seqmodel based on LSTM by considering the task as the production of the sequence of symbols in the CKY matrix from the input sequence. We prepared an additional dataset of 2000 examples for training. However, the neural network did not produce significative results. For this reason, we omitted the table here. The task is too complex to be learned by a trivial seq2 seq model. Figure 4: \(F1\) vs. string length for different dimensions \(d\) on grammar \(G_{0}\). Figure 5: \(F1\) vs. length of strings with grammars \(G_{1}\), \(G_{2}\), \(G_{3}\) and \(G_{4}\). ## 7 Conclusions and Future Work

At present, the predominance of symbolic, grammar-based algorithms for parsing of natural language has been successfully challenged by neural networks, which are based on distributed representations. However, Weiss et al. [24] and Suzgun et al. [25] showed the limitations of recurrent neural networks in capturing context-free languages in their full generality, when the input string is provided in plain form. Following this line of investigation, in this short article, we make a first step toward the definition of neural networks that can process context-free languages. We introduce the D-CYK algorithm, which is a distributed version of CYK, a classical parsing algorithm for context-free languages.