# CYK Parsing over Distributed Representations
## 3 Preliminaries
### Encoding and Using Unary Rules
Given the input string \(w=aab\), the matrix \(\mathbf{P}_{w}\) is:  
\[\mathbf{P}_{w}=\boxed{ \begin{array}{c}0\\ \mathbf{a}\end{array} }\quad\mathbf{P}_{\mathit{left}}+\boxed{ \begin{array}{ c}\mathbf{a}\\ \mathbf{a}\end{array} }\quad\mathbf{P}_{\mathit{left}}+\boxed{ \begin{array}{ c}\mathbf{a}\\ \mathbf{a}\end{array} }\quad\mathbf{P}_{\mathit{left}}+\boxed{ \begin{array}{ c}\mathbf{a}\\ \mathbf{a}\end{array} }\quad\mathbf{P}_{w})=\mathbf{P}_{\mathit{left}}+\boxed{ \begin{array}{c}\mathbf{a}\\ \mathbf{a}\end{array} }\quad\mathbf{P}_{w})=\mathbf{P}_{\mathit{left}}+\boxed{ \begin{array}{c}\mathbf{a}\\ \mathbf{a}\end{array} }\quad\mathbf{P}_{w})=\mathbf{P}_{\mathit{left}}+\boxed{ \begin{array}{c}\mathbf{a}\end{array} }\quad\mathbf{P}_{w})\]  
The _Update_ part of the assignment can be expressed as:  
\[\begin{array}{c}\text{\emph{Update}}=\boxed{ \begin{array}{c}0\\ \mathbf{a}\end{array} }\quad\boxed{ \begin{array}{c}\mathbf{a}\\ \mathbf{a}\end{array} }\quad\boxed{\begin{array```
1:for\(j\gets 2\) to \(n\)do
2:for\(i\gets j-2\) to \(0\)do
3:for\(A\in NT\)do
4:\(P_{A}\leftarrow\sigma([j]^{\oplus}[i]^{\oplus}\mathbf{P}_{\mathit{left}}\mathbf{ R}_{\mathit{b}}[A]\mathbf{P}_{\mathit{right}})\otimes\mathbf{I}\)
5:\(\mathbf{P}_{\mathit{left}}\leftarrow\mathbf{P}_{\mathit{left}}+[i]^{\ominus}[ j]^{\ominus}[A]^{\ominus}P_{A}\)
6:\(\mathbf{P}_{\mathit{right}}\leftarrow\mathbf{P}_{\mathit{right}}+[A]^{\ominus}[ i]^{\ominus}[j]^{\ominus}P_{A}\)
7:endfor
8:endfor
9:endfor
```

**Algorithm 3** D-CYK_binary(P, rules \(R_{A}\) for each \(A\)) **return**\(\mathbf{P}_{\mathit{left}}\)

Binary rules in \(R\) with nonterminal symbol \(A\) in the left-hand side are all encoded in a matrix \(\mathbf{R}_{\mathit{b}}[A]\) in \(\mathbb{R}^{d\times d}\). \(\mathbf{R}_{\mathit{b}}[A]\) is conceived of for defining matrix operations that detect if rules of the form \(A\to BC\), for some \(B\) and \(C\), fire in position \((i,j)\), given \(\mathbf{P}_{\mathit{left}}\) and \(\mathbf{P}_{\mathit{right}}\). This operation results in a nearly identity matrix \(\mathbf{I}\) for a specific position \((i,j)\) if at least one rule coded in \(\mathbf{R}_{\mathit{b}}[A]\) fires in position \((i,j)\) over positions \((i,k)\) and \((k,j)\), for any value of \(k\). This in turn will enable the insertion of new symbols in \(\mathbf{P}_{\mathit{left}}\) and \(\mathbf{P}_{\mathit{right}}\), for later steps. To define \(\mathbf{R}_{\mathit{b}}[A]\), we encode the right-hand side of each binary rule \(A\to BC\) in \(R\) as \([B]^{\oplus}[C]^{\ominus}\). All the right-hand sides of binary rules with symbol \(A\) in the left-hand side are then collected in matrix \(\mathbf{R}_{\mathit{b}}[A]\):

\[\mathbf{R}_{\mathit{b}}[A] = \sum_{A\to BC}[B]^{\oplus}[C]^{\ominus}. \tag{5}\]

Algorithm 3 uses these rules to determine whether a symbol \(A\) can fire in a position \((i,j)\) for any \(k\). The key part is Line 4 of Algorithm 3:

\[P_{A}\leftarrow\sigma([j]^{\ominus}[i]^{\oplus}\mathbf{P}_{\mathit{left}} \mathbf{R}_{\mathit{b}}[A]\mathbf{P}_{\mathit{right}})\otimes\mathbf{I}\:.\]

Matrix \(\mathbf{R}_{\mathit{b}}[A]\) selects elements in \(\mathbf{P}_{\mathit{left}}\) and \(\mathbf{P}_{\mathit{right}}\) according to rules for \(A\). Matrices \(\mathbf{P}_{\mathit{left}}\) and \(\mathbf{P}_{\mathit{right}}\) have been designed in such a way that, after the nonterminal symbols in the selected elements have been annihilated, the associated spans \((i,k)\) and \((k,j)\) merge into span \((i,j)\). Finally, the terms \([j]^{\ominus}[i]^{\oplus}\) are meant to check whether the span \((i,j)\) has survived. If this is the case, the resulting matrix will be very close to \(n\mathbf{I}\), with \(n\) depending on the number of merges that have produced the span \((i,j)\); otherwise, the resulting matrix will be very close to the null matrix \(\mathbf{0}\). To remove from the resulting matrix the potential \(n\) factor, we use the sigmoid function \(\sigma(x)\). Finally, we apply an element-wise multiplication with \(\mathbf{I}\), which is helpful in removing noise.