# CYK Parsing over Distributed Representations
## 3 Preliminaries
### Encoding and Using Unary Rules  
The CYK algorithm uses symbols \(a_{i}\) from the input string \(w=a_{1}a_{2}\cdots a_{n}\) and unary rules to fill in cells \(P[i-1,i]\), as seen in Algorithm 1. We simulate this step in our D-CYK using our distributed representation and matrix operations. D-CYK represents each input token \(a_{i}\) using a dedicated matrix \(\mathbf{P}_{w}\), defined as:  
\[\mathbf{P}_{w} = \sum_{i=1}^{n}[i-1]^{\odot}[i]^{\odot}[a_{i}]^{\odot}\;.\]  
For processing unary rules, we use the first part of the D-CYK algorithm, called D-CYK_unary and reported in Algorithm 2. D-CYK_unary takes \(\mathbf{P}_{w}\) and produces matrices \(\mathbf{P}_{left}\) and \(\mathbf{P}_{right}\) encoding nonterminal symbols resulting from the application of unary rules. ```
1:\(\mathbf{P}_{w}\leftarrow\sum_{i=1}^{n}[i-1]^{\odot}[i]^{\odot}[a_{i}]^{\odot} ;\)\(\mathbf{P}_{left}\leftarrow\mathbf{0}\); \(\mathbf{P}_{right}\leftarrow\mathbf{0}\);
2:for\(i\gets 1\) to \(n\)do
3:for\(A\in NT\)do
4:\(P_{A}\leftarrow\sigma(\mathbf{R}_{u}[A][i]^{\oplus}[i-1]^{\odot}\mathbf{P}_ {w})\)
5:\(\mathbf{P}_{left}\leftarrow\mathbf{P}_{left}+[i-1]^{\odot}[i]^{\odot}[A]^{ \odot}P_{A}\)
6:\(\mathbf{P}_{right}\leftarrow\mathbf{P}_{right}+[A]^{\oplus}[i-1]^{\oplus}[i]^ {\oplus}P_{A}\)
7:endfor
8:endfor
```  
**Algorithm 2** D-CYK_unary(string \(w=a_{1}a_{2}\cdots a_{n}\), matrices \(\mathbf{R}_{u}[A]\)) **return**\(\mathbf{P}_{left}\) and \(\mathbf{P}_{right}\)  
In D-CYK_unary, we also use matrices \(\mathbf{R}_{u}[A]\), for each \(A\in NT\) in the left-hand side of some unary rule. These matrices are conceived of to detect the applicability to matrix \(\mathbf{P}_{w}\) of the rules of the form \(A\to a\), where \(a\) is some alphabet symbol. Matrix \(\mathbf{R}_{u}[A]\) is defined as:  
\[\mathbf{R}_{u}[A] = \sum_{(A\to a)\in R}[a]^{\oplus}\;, \tag{1}\]  
where \(R\) is the set of rules of the grammar. The operation involving \(\mathbf{R}_{u}[A]\) and \(\mathbf{P}_{w}\), which detects whether some rule \(A\to a\) is applicable at position \((i-1,i)\) of the input string, is (Line 4 in Algorithm 2):  
\[P_{A} \leftarrow \sigma(\mathbf{R}_{u}[A][i]^{\oplus}[i-1]^{\oplus}\mathbf{P}_{w })\;,\]  
where \(\sigma(x)\) is a sigmoid function \(\sigma(x)=\frac{1}{1+e^{-(x-0.05)\
eq\emptyset}}\). In fact, \([i]^{\oplus}[i-1]^{\oplus}\mathbf{P}_{left}\approx[a_{i}]^{\ominus}\) extracts the distributed representation of terminal symbol \(a_{i}\). Then:  
\[\mathbf{R}_{u}[A][a_{i}]^{\ominus} = \sum_{(A\to a)\in R}[a]^{\oplus}[a_{i}]^{\ominus}\approx \begin{cases} \mathbf{0}&\text{if }(A\to a_{i})\
otin R\\ \mathbf{1}&\text{if }(A\to a_{i})\in R\end{cases}  \tag{2}\]  
Figure 2: Tetris-like graphical representation for the pieces for symbols in our running example. is reinforced by the subsequent use of the sigmoid function. Hence, if some unary rule with left-hand side symbol \(A\) is applicable, the resulting matrix is approximately the identity matrix \(\mathbf{I}_{i}\) otherwise, the resulting matrix is approximately the zero matrix \(\mathbf{0}\). Then, the operations at Lines 5 and 6:  
\[\mathbf{P}_{\mathit{left}} \leftarrow \mathbf{P}_{\mathit{left}}+[i-1]^{\odot}[i]^{\odot}[A]^{\odot}P_{A}\] \[\mathbf{P}_{\mathit{right}} \leftarrow \mathbf{P}_{\mathit{right}}+[A]^{\odot}[i-1]^{\odot}[i]^{\odot}P_ {A}\]  
add a non-zero matrix to both \(\mathbf{P}_{\mathit{left}}\) and \(\mathbf{P}_{\mathit{right}}\) only if unary rules for \(A\) are matched by matrix \(\mathbf{P}_{w}\) encoding the input string \(w\). We describe the application of D-CYK_unary using the running example in Figure 1 and the Tetris-like representation. The two unary rules \(D\to a\) and \(E\to b\) are represented as \(\mathbf{R}_{u}[D]=[a]^{\oplus}\) and \(\mathbf{R}_{u}[E]=[b]^{\oplus}\), that is:  
\[\mathbf{R}_{u}[D]=\boxed{ \begin{array}{c}\mathbf{a}\\ \mathbf{a}\end{array} }\quad\mathbf{R}_{u}[E]=\boxed{ \begin{array}{c}\mathbf{b }\\ \mathbf{a}\end{array} }\]  
in the Tetris-like form.