# CYK Parsing over Distributed Representations
## 3 Preliminaries
### Distributed Representations with Holographic Reduced Representations  
Holographic reduced representations (HRRs), introduced in [26] and extended in [27], are distributed representations well suited for our aim of encoding the two-dimensional parsing table \(P\) of the CYK algorithm and for implementing the operation of selecting the content of its cells \(P[i,j]\). In the following, we introduce the operations we use, along with a graphical way to represent their properties. The graphical representation is based on Tetris-like pieces. These HRRs represent sequences of symbols \(s=s_{1}\ldots s_{n}\) in vectors \(\vec{s}\) by composing vectors \(\vec{s_{i}}\) of symbols \(s_{i}\) in the sequences. Hence, these representations offer an encoder and a decoder for sequences in vectors. The encoder and the decoder are not learned, but rely on the statistical properties of random vectors and the properties of a basic operation for composing vectors. The basic operation is circular convolution [26], extended to shuffled circular convolution in [27], which is non-commutative and, then, alleviates the problem of confusing sequences with the same symbols in different order. The starting point of a distributed representation and, hence, of HRR is how to encode symbols into vectors: symbol \(a\) is encoded using a random vector \(\vec{a}\in\mathbb{R}^{d}\) drawn from a multivariate normal distribution \(\vec{a}\sim N(0,\mathbf{I}\frac{1}{\sqrt{d}})\). These are used as basis vectors for the Johnson-Lindenstrauss transform [28], as well as for random indexing [29]. The main property of these random vectors is the following:  
\[\vec{a}^{\top}\vec{b} \approx \begin{cases}1&\text{if }\vec{a}=\vec{b}\\ 0&\text{if }\vec{a}\
eq\vec{b}\end{cases} \]  
In this paper, we use the matrix representation of the shuffled circular convolution introduced in [27]. In this way, symbols are represented in a way where composition is just matrix multiplication and the inverse operation is matrix transposition. Given the above symbol encoding, we can define a basic operation \([\,]^{\oplus}\) and its approximate inverse \([\,]^{\odot}\). These operations take as input a symbol and provide a matrix in \(\mathbb{R}^{d\times d}\) and are the basis for our encoding and decoding. The first operation is defined as:  
\[[a]^{\oplus} = \text{A}_{\circ}\Phi\,\]  
where \(\Phi\) is a permutation matrix to obtain the shuffling [27] and \(\text{A}_{\circ}\) is the circulant matrix of the vector \(\vec{a}^{\top}= \begin{pmatrix}a_{0}&a_{1}&\ldots&a_{d-1}\end{pmatrix} \), that is:  
\[\text{A}_{\circ}= \begin{bmatrix}a_{0}&a_{d-1}&\ldots&a_{1}\\ a_{1}&a_{0}&\ldots&a_{2}\\ \vdots&\ddots&\vdots\\ a_{d-2}&a_{d-3}&\ldots&a_{d-1}\\ a_{d-1}&a_{d-2}&\ldots&a_{0}\end{bmatrix} = \begin{bmatrix}a_{0}&&\ldots&\\ a_{0}(\vec{a})&s_{1}(\vec{a})&\ldots&s_{d-1}(\vec{a})\\ \begin{bmatrix}a_{0}&\ldots&\\ a_{1}&\ldots&\\ a_{d-1}&\ldots&\\ \end{bmatrix}\end{bmatrix} \]  
Figure 1: A simple context-free grammar (CFG), the Cocke–Younger–Kasami (CYK) parsing table \(P\) for the input string \(w=aab\) as constructed by Algorithm 1, and the “distributed” representation \(\mathbf{P}_{l\!\!\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!l\!\!l\  
while \(s_{i}(\vec{a})\) is the circular shifting of \(i\) positions of the vector \(\vec{a}\). Circulant matrices are used to describe circular convolution. In fact, \(\vec{a}\ast\vec{b}=\mathrm{A}_{\circ}\vec{b}=\mathrm{B}_{\circ}\vec{a}\) where \(\ast\) is circular convolution. This operation has a nice approximated inverse in:  
\[[a]^{\odot} = \Phi^{\top}\mathrm{A}_{\circ}^{\top}\.\]  
We then have:  
\[[a]^{\oplus}[b]^{\odot} \approx \begin{cases}\mathbf{I}&\text{if }\vec{a}=\vec{b}\\ \mathbf{0}&\text{if }\vec{a}\
eq\vec{b}\end{cases} \]  
since \(\Phi\) is a permutation matrix and therefore \(\Phi\Phi^{\top}=I\) and since:  
\[\mathrm{A}_{\circ}^{\top}\mathrm{B}_{\circ} \approx