\documentclass{article}
\usepackage{amsmath,amssymb}
\usepackage{booktabs}

\title{Product Space Embeddings}
\author{Hutter RNN Project}
\date{2026-01-31}

\begin{document}
\maketitle

\section{Construction}

Given two event spaces $A$ (size $m$) and $B$ (size $n$), we construct an embedding of $A$ into $\mathbb{R}^n$ via the product space.

\subsection{Recipe}

\begin{enumerate}
\item \textbf{Product space:} Form $A \times B$ with $m \times n$ cells.
\item \textbf{Count:} For sequence data, count bigram transitions $a \to b$.
\item \textbf{Normalize:} Compute $P(b \mid a)$ for each $a \in A$.
\item \textbf{Embed:} Each $a$ becomes a point in $\mathbb{R}^n$:
\[
\phi(a) = (P(b_1 \mid a), P(b_2 \mid a), \ldots, P(b_n \mid a))
\]
\end{enumerate}

\subsection{Properties}

The embedding $\phi: A \to \mathbb{R}^n$ satisfies:
\begin{itemize}
\item $\phi(a)$ lies on the $(n-1)$-simplex (probabilities sum to 1)
\item Distance in embedding space = distributional similarity
\item $\|\phi(a_1) - \phi(a_2)\|$ small $\Rightarrow$ $a_1, a_2$ predict similar $b$
\end{itemize}

\section{Example: Vowel $\times$ Consonant-Group}

Let $A = \{a, e, i, o, u\}$ (5 vowels) and $B$ = 7 consonant groups:
\begin{itemize}
\item Stops voiced: b, d, g
\item Stops unvoiced: p, t, k
\item Fricatives: f, v, s, z
\item Nasals: m, n
\item Liquids: l, r
\item Glides: w, y
\item Other: c, h, j, q, x
\end{itemize}

Product space: $5 \times 7 = 35$ pairs.

\subsection{Normalized Embeddings}

From 100M bytes of enwik9:

\begin{center}
\begin{tabular}{l|ccccccc}
\toprule
& stops\_v & stops\_uv & fric & nasal & liquid & glide & other \\
\midrule
a & 0.087 & 0.178 & 0.118 & 0.277 & 0.258 & 0.026 & 0.056 \\
e & 0.146 & 0.065 & 0.196 & 0.187 & 0.297 & 0.025 & 0.084 \\
i & 0.108 & 0.153 & 0.214 & 0.318 & 0.092 & 0.001 & 0.115 \\
o & 0.056 & 0.135 & 0.190 & 0.312 & 0.236 & 0.039 & 0.032 \\
u & 0.117 & 0.182 & 0.184 & 0.194 & 0.257 & 0.002 & 0.064 \\
\bottomrule
\end{tabular}
\end{center}

\subsection{Distance Matrix (L2)}

\begin{center}
\begin{tabular}{l|ccccc}
\toprule
& a & e & i & o & u \\
\midrule
a & 0 & 0.180 & 0.208 & 0.102 & 0.113 \\
e & & 0 & 0.265 & 0.187 & 0.131 \\
i & & & 0 & 0.180 & 0.216 \\
o & & & & 0 & 0.151 \\
u & & & & & 0 \\
\bottomrule
\end{tabular}
\end{center}

\textbf{Clusters:}
\begin{itemize}
\item (a, o): 0.102 --- both favor nasals + liquids (``an'', ``on'', ``al'', ``ol'')
\item (a, u): 0.113 --- similar profiles
\item (e, u): 0.131 --- both high liquid (``er'', ``ur'')
\item i is unique: high nasal (``in'', ``im''), almost no glide
\end{itemize}

\section{Information Content}

\begin{align}
H(\text{cgroup}) &= 2.55 \text{ bits} \\
H(\text{cgroup} \mid \text{vowel}) &= 2.48 \text{ bits} \\
I(\text{cgroup}; \text{vowel}) &= 0.07 \text{ bits}
\end{align}

The embedding captures 2.8\% of consonant-group entropy---not much, but interpretable.

\section{Generalization}

The same construction works at any scale:

\begin{center}
\begin{tabular}{lcc}
\toprule
Product Space & Size & Interpretability \\
\midrule
Byte $\times$ Byte & 65,536 & Low \\
ES $\times$ ES & 25 & High \\
Vowel $\times$ CGroup & 35 & High \\
Word $\times$ Word & $V^2$ & Medium \\
\bottomrule
\end{tabular}
\end{center}

\subsection{Connection to Neural Embeddings}

Word2Vec and similar methods learn embeddings via:
\[
\phi(w) = \arg\max P(\text{context} \mid w)
\]

Our construction is the \textbf{exact} version: we compute $P(b \mid a)$ directly from counts, no learning required.

The neural network learns a compressed representation; we get the full distribution.

\section{Hierarchical Embeddings}

For the RNN hidden state $\mathbf{h} \in \mathbb{R}^H$:
\[
\phi(\text{context}) = \mathbf{h}
\]

This is an embedding of variable-length history into fixed-dimensional space.

\textbf{Key insight:} The RNN hidden state IS an embedding of the memory trace.

\end{document}
