On the Compressive Power of Boolean Threshold Autoencoders

The encoder maps a vector to its index, in binary representation, and the decoder maps the index back to the vector. To implement the idea formally denote by $i2b_{d}(j)$ the $d$-dimensional binary vector representing $j$, for $j<2^{d}$ and $0<d$. For example, $i2b_{3}(5)=(1,0,1)$.

Given $d=\lceil\log n\rceil$ define $({\bf f},{\bf g})$ by ${\bf f}({\bf x}^{i})=i2b_{d}(i)$ and $g_{j}({\bf f}({\bf x}^{i}))=x^{i}_{j}$. Clearly, $({\bf f},{\bf g})$ is a perfect autoencoder and can be represented by Boolean functions. ∎

We use the probabilistic method to establish the existence of a set $W$ of $d$ $D$-dimensional weight vectors ${\bf w}^{j}\in\{-1,1\}^{D}$ with the property that the two-layer BTN whose threshold functions are $f_{j}({\bf x})=[{\bf x}\cdot{\bf w}^{j}\geq 1],\ j=0,\ldots,d-1$, yields output vectors that are all different. Denote by ${\bf y}^{i}$ the output vector for ${\bf x}^{i}$, with $y^{i}_{j}=f_{j}({\bf x}^{i})$.

Consider a random $W$ such that each $w^{j}_{i}$ has the value $-1$ or 1 with probability $\frac{1}{2}$. Let us compute a lower bound on the probability that a given pair of output vectors differs in a specific coordinate. Without loss of generality (w.l.o.g.) we take the vectors to be ${\bf y}^{0}$ and ${\bf y}^{1}$, and look at the $\ell$-th coordinate. Because this probability does not depend on the coordinate, since $W$ was chosen at random, let’s denote it by $p_{\{0,1\}}$. Denote by $m_{i}$ the number of 1’s in ${\bf x}^{i}$, and by $m_{\{0,1\}}$ the number of coordinates with value 1 for both ${\bf x}^{0}$ and ${\bf x}^{1}$. W.l.o.g. $x^{0}_{0}=x^{1}_{0}=\cdots=x^{0}_{m_{\{0,1\}}-1}=x^{1}_{m_{\{0,1\}}-1}=1$, $x^{0}_{m_{\{0,1\}}}=\cdots=x^{0}_{m_{0}-1}=x^{1}_{m_{0}}=\cdots=x^{1}_{m_{0}+m_{1}-m_{\{0,1\}}-1}=1$, all other coordinates being 0.

Consequently ${y}^{0}_{\ell}=[\sum_{j=0}^{m_{0}-1}w^{\ell}_{j}\geq 0]$, and ${y}^{1}_{\ell}=[\sum_{j=0}^{m_{\{0.1\}}-1}w^{\ell}_{j}+\sum_{j=m_{0}}^{m_{0}+m_{1}-m_{\{0.1\}}-1}w^{\ell}_{j}\geq 0]$.

Suppose $m_{\{0,1\}}$ is even. Then a lower bound on $p_{\{0,1\}}$ is $p_{\{0,1\}}\geq Prob(\sum_{j=0}^{m_{\{0,1\}}-1}w^{\ell}_{j}=0)\cdot Q$, where $Q$ stands for

By the soon-to-be-stated Lemma 7, $Prob(\sum_{j=0}^{m_{\{0,1\}}-1}w^{\ell}_{j}=0)\geq\frac{1}{\sqrt{2m_{\{0,1\}}}}$. Turning to the estimation of $Q$, Lemma 7 implies that if one of $m_{0}-m_{\{0,1\}},m_{1}-m_{\{0,1\}}$ is odd then $Q=\frac{1}{2}$. In the remaining case that both $r_{0}=m_{0}-m_{\{0,1\}}$ and $r_{1}=m_{1}-m_{\{0,1\}}$ are even

This expression assumes its smallest value, for $r_{0}+r_{1}\geq 1$, when one of $r_{0},r_{1}$ is 0 and the other is 2, in which case its value is $\frac{1}{4}$. We conclude, therefore, that if the number of 1’s that ${\bf x}^{0},{\bf x}^{1}$ have in common is even then $Q\geq\frac{1}{4}$ and $p_{\{0,1\}}\geq\frac{1}{4\sqrt{2m_{\{0,1\}}}}\geq\frac{1}{4\sqrt{2D}}$.

A similar computation for the case that $m_{\{0,1\}}$ is odd shows that if number of 1’s that ${\bf x}^{0},{\bf x}^{1}$ have in common is odd then $p_{\{0,1\}}\geq\frac{1}{4\sqrt{m_{\{0,1\}}}}$.

In summary, the probability that a specific pair of output vectors differ at a specific coordinate is at least

where $M=\max_{0\leq i<j\leq n-1}m_{\{i,j\}}$,

Consequently the probability that all coordinates of two $d$-dimensional output vectors are identical is at most $(1-\frac{1}{4\sqrt{2M}})^{d}$. To ensure that the probability that one of the $\binom{n}{2}$ pairs of vectors ${\bf y}^{i_{0}}$ and ${\bf y}^{i_{1}}$ is identical is less than 1 it is sufficient to choose $d$ such that

i.e. we require $d\geq 8\sqrt{2M}\ln n$. ∎

It suffices to note that if $m$ is even (odd) then $w$ is even (odd), and that $Prob(w<0)=Prob(w>0)$. ∎

We again use the probabilistic method to establish the existence of a network with $d$ output nodes, provided $d\geq 2\log_{2}n$. Equip each output node $y_{k}$, $k=0,\ldots,d-1$ with an activation function $f_{k}$ constructed as follows: assemble a set of bits, $S_{k}$, by adding each one of the $D$ input variables to the set with probability $\frac{1}{2}$, and set $f_{k}({\bf x})$ to be the parity of the set of values that ${\bf x}$ assigns to the variables in $S_{k}$.

Consider an arbitrary fixed output node $y_{k}$. Given a pair of input vectors $({\bf x}^{i},{\bf x}^{j})$, define

Then $f_{k}({\bf x}^{i})=f_{k}({\bf x}^{j})$ if and only if $|B^{i}_{i,j}\cap S_{k}|$ and $|B^{j}_{i,j}\cap S_{k}|$ are either both odd or both even.

If $|B^{i}_{i,j}|>0$, then $Prob(|B^{i}_{i,j}\cap S_{k}|\ is\ even)=Prob(|B^{i}_{i,j}\cap S_{k}|\ is\ odd)=\frac{1}{2}$, because $S_{k}$ is randomly selected. Therefore, if $|B^{i}_{i,j}|>0$ and $|B^{j}_{i,j}|>0$, then the probability that $f_{k}({\bf x}^{i})=f_{k}({\bf x}^{j})$ is ${\frac{1}{2}}$. If $|B^{i}_{i,j}|=0$ then $|B^{j}_{i,j}|>0$, since ${\bf x}^{i}\neq{\bf x}^{j}$, and $Prob(f_{k}({\bf x}^{i})=f_{k}({\bf x}^{j}))=Prob(|B^{j}_{i,j}\cap S_{k}|\ is\ even)=\frac{1}{2}$.

We conclude that $Prob(f_{k}({\bf x}^{i})=f_{k}({\bf x}^{j}))={\frac{1}{2}}$, and the probability that $Prob({\bf y}^{i}={\bf y}^{j})=({\frac{1}{2}})^{d}$. Therefore the probability that there is some pair ${\bf x}^{i},{\bf x}^{j}$ for which ${\bf y}^{i}={\bf y}^{j}$ is smaller than $n^{2}({\frac{1}{2}})^{d}$, which is less than 1 if $d\geq 2\log_{2}n$. ∎

It is well-known that a parity function on $D$ nodes can be implemented by threshold functions while using only one additional layer of at most $D$ nodes. A simple way of doing this is to use a hidden layer with $D$ nodes, $h_{0},...,h_{D-1}$, where node $h_{i}$ has value 1 if the input contains at least $i+1$ 1’s, i.e. $h_{i}({\bf x})=[{\bf e}\cdot{\bf x}\geq i+1]$, where ${\bf e}=(1,...,1)$. The output node that computes the parity of the input has the activation function $[\sum_{i=0}^{D-1}(-1)^{i-1}h_{i}\geq 1]$. The Theorem follows therefore from Theorem 8 when each of the parity functions it uses is implemented this way. ∎

Let the vector of threshold functions for the $n$ nodes in the output layer be $\textit{G}_{j}(\textbf{x})=[\textbf{a}\cdot\textbf{x}\geq b_{j}]$. Clearly $\textit{G}_{j}(\textbf{x}^{i})=[\textbf{a}\cdot\textbf{x}^{i}\geq b_{j}]$ has value 1 if and only if $j\leq i$, i.e. $\textbf{{G}}(\textbf{x}^{i})=\textbf{h}^{i}$. ∎

For ease of exposition we assume that $\log n={2m}$, and $r=\sqrt{n}=2^{m}$.

The nodes $\alpha^{2}_{j}$ simply copy the input, ${\alpha}^{2}_{j}=x_{j},\ j=0,\ldots,D-1$. To define the activation functions of $\alpha^{1}_{i}$ divide the interval $[b_{0},b_{n-1}]$ into $r$ consecutive subintervals $[s_{0},s_{1}-1],\ [s_{1},s_{2}-1],\ldots,[s_{r-1},b_{n-1}]$ each containing $r$ values $b_{i}$, i.e. $s_{0}=b_{0},s_{1}=b_{r},\ldots,s_{r-1}=b_{(r-1)r}$, and $s_{r}=b_{n}+1$. The activation function of $\alpha^{1}_{i}$ is $[{\bf a}\cdot{\bf x}\geq s_{i}]$, $0\leq i\leq r-1$. Clearly, if $h=kr+\ell$ then $\alpha^{1}_{i}=1$ if and only if $i\leq k$, i.e. $\boldsymbol{\alpha}^{1}=\boldsymbol{h}^{k}[r]$.

The output node $\beta^{1}_{i}$ copies $\alpha^{1}_{i},\ 0\leq i\leq r-1$. The remaining output nodes, $\boldsymbol{\beta}^{2}$, represent the ordinal number of ${\bf a}\cdot{\bf x}$ within the $k$-th subinterval. To implement this part of the mapping we follow [21] in employing the ingenious technique of telescopic sums, introduced by [22], and define

The important thing to note here is that if ${\bf a}\cdot{\bf x}$ falls in the $k$-th subinterval, so that $s_{k}\leq{\bf a}\cdot{\bf x}<s_{k+1}$, then $t_{i}$ has the value $b_{kr+i}$, because $\alpha_{0}=\ldots=\alpha_{k}=1$, while $\alpha_{i}=0,\ i>k$.

The activation function of $\beta^{2}_{i}$ is $[{\bf a}\cdot{\bf x}-t_{i}\geq 0]$, $i=0,\ldots,r-1$. Observe that if ${\bf a}\cdot{\bf x}=b_{kr+\ell}$, then $\beta^{2}_{i}=[b_{kr+\ell}-b_{kr+i}\geq 0]$, i.e. $\beta^{2}_{i}=1$ if $i\leq\ell$, and $\beta^{2}_{i}=0$ if $i>\ell$. ∎

To construct the vector of threshold functions for the output nodes, $\textbf{{H}}(\textbf{h}[s])$, set $w^{j}_{0}=z^{0}_{j},j=0,\ldots,d-1$,

and $\textit{H}_{j}(\textbf{h}[s])=[\textbf{w}^{j}\cdot\textbf{h}[s]\geq 1].$ It is easily verified that $\textit{H}_{j}(\textbf{h}[s]^{i})=[z^{i}_{j}\geq 1]=z^{i}_{j}$, i.e. $\textbf{{H}}(\textbf{h}[s]^{i})=\textbf{z}^{i}$ as desired. ∎

Set $N=\binom{n}{2}$ and construct $Y$ as follows:

1. 1.

   index the coordinates of the vectors by $(i,j),\ 0\leq i<j\leq n-1$;

2. 2.

   set ${y}^{k}_{(i,j)}=1$ if and only if $i$ or $j$ is $k$.

A BTN that encodes these vectors with $d$ bits is constructed as follows. The most significant bit is generated by the threshold function

The next most significant bit is generated by

The successive digits are generated in similar fashion, each time using a sum of $\frac{n}{4}$ input bits, until at last the least significant is generated by the slightly different threshold function

It is not difficult to verify that this 2-layer BTN maps $\textbf{y}^{i}$ to the $d$-bit representation of $i$.

To illustrate, consider the case $d=3,\ n=8,\ N=28$. These vectors are encoded by the threshold functions $d_{0}$ (most significant digit) $d_{1}$ and $d_{2}$ (least significant digit)

For example, since in ${\bf y}^{7}$ the coordinates $(0,7),\ldots,(6,7)$ are 1 it has $d_{0}({\bf y}^{7})=d_{1}({\bf y}^{7})=d_{2}({\bf y}^{7})=1$, i.e. its representation is $(1,1,1)$. Similarly, since $y^{1}_{(6,7)}=y^{1}_{(4,5)}=y^{1}_{(2,3)}=0$ whereas $y^{1}_{(1,3)}=1$, $d_{0}({\bf y}^{1})=d_{1}({\bf y}^{1})=0,d_{2}({\bf y}^{1})=1$, so that ${\bf y}^{1}$ has the representation $(0,0,1)$.

To prove the second assertion, suppose to the contrary that there does exist a BTN mapping $\{0,1\}^{d}$ to $Y$, and that it maps $(0,\ldots,0)$ to $\textbf{y}^{k}$ and $(1,\ldots,1)$ to $\textbf{y}^{\ell}$. Consider the threshold function for the bit $x_{(k,\ell)}$ of the output layer. Since by construction $y^{k}_{(k,\ell)}=y^{\ell}_{(k,\ell)}=1$ while $y^{i}_{(k,\ell)}=0$ for all $i\neq k,\ \ell$, it follows that the threshold function for this bit separates the two $d$-dimensional vectors $(0,\ldots,0)$ and $(1,\ldots,1)$ from the remainder of $\{0,1\}^{d}$, a contradiction to the well-known fact that such a threshold function does not exist. ∎

To the two-layer encoder of Theorem 11 add the decoder that maps $\textbf{h}^{i}[n]$ to $\textbf{x}^{i},\ i=0,\ldots,n-1$. That decoder can be obtained from the construction of Lemma 13 by setting ${\bf z}^{i}=\textbf{x}^{i}$ and $s=n$. ∎

On top of the encoder constructed in the proof of Theorem 12 we add a decoder that is a 3-layer network with the $2r$ input nodes $\beta^{1}_{i},\beta^{2}_{i},\ i=0,\ldots,r-1$, $rD$ hidden nodes $\eta_{i,j},\ i=0,\ldots,r-1,\ j=0,\ldots,D-1$, and $D$ output nodes $y_{j},\ j=0,\ldots,D-1$, see Fig. 3. To simplify the description we add a dummy node $\beta^{2}_{r}=0$.

We will see that this decoder outputs $\textbf{y}=\textbf{x}^{kr+\ell}$ when given input $(\boldsymbol{h}^{k}[r],\boldsymbol{h}^{\ell}[r])$, as desired. Equip the node $\eta_{i,j}$ with the activation function

Note that if $\boldsymbol{\beta}^{1}=\boldsymbol{h}^{k}[r]$ then