# CYK Parsing over Distributed Representations
## 3 Preliminaries
### Encoding and Using Unary Rules
Albeit that it is not the focus of our study, it is important to observe the computational complexity of the core part of D-CYK since it was reduced to \(O(n^{2}|NT|)\) where \(n\) is the length of the input and \(|NT|\) is the cardinality of the set of non-terminal symbols. The computational complexity of the CKY in Algorithm 1 is \(O(n^{3}|R|)\) where \(|R|\) is the size of the grammar. The reduction in complexity is justified by the fact that we regard as a constant the parameter \(d\) associated with the distributed representation, and by the fact that the inner loop in Algorithm 1 starting in Line 8 is absorbed by the matrix operations in Lines 4-6 of Algorithm 3. Yet, this reduction in complexity is paid with the approximation of the results introduced by these matrix operations over the distributed representation of the CYK matrix. To visualize the behavior of the algorithm D-CYK_binary and the effect of using \(\mathbf{R}_{\mathit{b}}[A]\), we use again the running example of Figure 1. The only nonterminal with binary rules is \(S\), and matrix \(\mathbf{R}_{\mathit{b}}[S]\) is:Let us focus on the position \((1,3)\). The operation is the following:

\[P_{A}=\sigma(\raisebox{-14.226378 pt}{\includegraphics[height=14.226378 pt]{ \includegraphics[height=14.



Blocks for different nonterminals are then combined for the next step:

\[\mathbf{L}_{t+1} = \mathbf{L}_{t}+\sum_{A\in NT}\mathbf{L}_{t+1}^{A} \tag{9}\] \[\mathbf{R}_{t+1} = \mathbf{R}_{t}+\sum_{A\in NT}\mathbf{R}_{t+1}^{A} \tag{10}\]

Here, \(\mathbf{L}_{t+1}\) encodes matrix \(\mathbf{P}_{left}\), and \(\mathbf{R}_{t+1}\) encodes matrix \(\mathbf{P}_{right}\) from Algorithm 3, after the first \(t\times|NT|\) iterations of the innermost for-cycle in Algorithm 3. Matrices \(\mathbf{L}_{0}\) and \(\mathbf{R}_{0}\) are taken from the output of Algorithm 2. Finally, Algorithm 2 can be directly implemented by tagging each token \(a_{i}\) from \(w\) using unary rules from \(R\) and by subsequently encoding the tag and the associated indices \(i\) and \(i-1\) in our distributed form. ### Decoding Phase

The decoding phase is based on the specification of Algorithm 4 reported in Section 6. Let \(\mathbf{L}\) be the matrix obtained from Equation (9) after the entire input sequence has been processed by the network in Section 5.1. We apply a simple, memory-less forward layer:

\[y_{t}=\sigma(\mathbf{W}_{d}x_{t}^{(2)}x_{t}^{(1)}\mathbf{L})\]

to the sequence:

\[([0]^{\oplus},[1]^{\oplus}),([0]^{\oplus},[2]^{\oplus}),([0]^{\oplus},[3]^{ \oplus}),\ldots,([0]^{\oplus},[n]^{\oplus})([1]^{\oplus},[2]^{\oplus}),([1]^{ \oplus},[3]^{\oplus}),\ldots,([n-1]^{\oplus},[n]^{\oplus})\]

where \(\mathbf{W}_{d}\) is initialized with rows representing the nonterminal symbols in a distributed way. ## 6 Experiments

The aim of this section is to evaluate the D-CYK algorithm by assessing how close it comes to the traditional CYK algorithm, that is how similar the parsing tables produced by the two algorithms are. For this purpose, we use artificial, ambiguous CFGs. Hence, understanding how good D-CYK is at selecting the best syntactic interpretation in an NLP setting is out of the scope of this study. ### Experimental Setup

We experiment with five different CFGs in Chomsky normal form, named \(G_{i}\) with \(0\leq i\leq 4\). Table 1 reports some elementary statistics about these grammars. Each \(G_{i}\) is obtained from \(G_{i-1}\) by adding new rules and new nonterminal symbols, so that the language generated by \(G_{i-1}\) is always included in the language generated by \(G_{i}\). More precisely, \(G_{1}\) expands over \(G_{0}\) by adding unary rules only; all remaining grammars \(G_{i}\) expand over \(G_{i-1}\) by adding binary rules only. Grammars are directly encoded in \(\mathbf{R}_{u}[A]\) and \(\mathbf{R}_{b}[A]\) as described in Equations (1) and (5). These parameters are not learned, but set. We test each \(G_{i}\) with the same set of 2000 strings obtained by randomly generating strings of various lengths using \(G_{0}\).