Holographic Reduced Representation

Holographic Reduced Representations are a simple mechanism to represent an associative array of key-value pairs in a fixed-size vector. Each individual key-value pair is the same size as the entire associative array; the array is represented by the sum of the pairs. Concretely, consider a complex vector key $r = (a\_{r}[1]e^{iφ\_{r}[1]}, a\_{r}[2]e^{iφ\_{r}[2]}, \dots)$, which is the same size as the complex vector value x. The pair is "bound" together by element-wise complex multiplication, which multiplies the moduli and adds the phases of the elements:

$y = r \otimes x$

$y = \left(a\_{r}[1]a\_{x}[1]e^{i(φ\_{r}[1]+φ\_{x}[1])}, a\_{r}[2]a\_{x}[2]e^{i(φ\_{r}[2]+φ\_{x}[2])}, \dots\right)$

Given keys $r\_{1}$, $r\_{2}$, $r\_{3}$ and input vectors $x\_{1}$, $x\_{2}$, $x\_{3}$, the associative array is:

$c = r\_{1} \otimes x\_{1} + r\_{2} \otimes x\_{2} + r\_{3} \otimes x\_{3}$

where we call $c$ a memory trace. Define the key inverse:

$r^{-1} = \left(a\_{r}[1]^{−1}e^{−iφ\_{r}[1]}, a\_{r}[2]^{−1}e^{−iφ\_{r}[2]}, \dots\right)$

To retrieve the item associated with key $r\_{k}$, we multiply the memory trace element-wise by the vector $r^{-1}\_{k}$. For example:

$r\_{2}^{−1} \otimes c = r\_{2}^{-1} \otimes \left(r\_{1} \otimes x\_{1} + r\_{2} \otimes x\_{2} + r\_{3} \otimes x\_{3}\right)$

$r\_{2}^{−1} \otimes c = x\_{2} + r^{-1}\_{2} \otimes \left(r\_{1} \otimes x\_{1} + r\_{3} \otimes x3\right)$

$r\_{2}^{−1} \otimes c = x\_{2} + noise$

The product is exactly $x\_{2}$ together with a noise term. If the phases of the elements of the key vector are randomly distributed, the noise term has zero mean.

Source: Associative LSTMs