How to find how which inputs correlate to output in XOR way

Question

Let's say this is my function:

bit f( bit bits[] ) = bits[0] ^ bits[2] ^ bits[7] ^ ...

I have a list of bits[]. I ran the function (f) on that list of bits[]. Is there proper (Not O(!n)) machine learning that can recover that function (f)?

I thought of seeing it as integer addition (e.g. bits[0] + bits[2] + bits[7] + ...), and then dropping all the integer's bits, except the first one, but I don't know how to recover that integer. (Isn't that impossible, because it lost most of it's entropy retrieved from the transformation of the input?)

Answer 1

You have $n$ binary-valued independent variables and $m$ observations in a data matrix $X$ and your dependent variable $y$ is the XOR ($\oplus$) of some subset of the independent variables. Consider a small example:

$$ \begin{align*} X &= \left(\begin{array}{ccc} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0\end{array}\right) \\ y &= \left(\begin{array}{c} 0 \\ 1 \\ 0\end{array}\right) \end{align*} $$

Here, the dependent variable is the $\oplus$ of the first and second independent variables (but not the third). Your question is how to efficiently determine the subset of variables participating in the calculation of the dependent variable.

To solve this, for each independent variable $i$ define binary variable $z_i$ indicating if that variable participates in the $\oplus$. This yields a system of binary conditions that must hold:

$$ \neg(0z_1\oplus 0z_2\oplus 1z_3) \\ 0z_1\oplus 1z_2\oplus 0z_3 \\ \neg(1z_1\oplus 1z_2\oplus 0z_3) $$

We can convert these into arithmetic modulo 2:

$$ \begin{align*} z_3 &= 0~\mod 2 \\ z_2 &= 1~\mod 2 \\ z_1 + z_2 &= 0~\mod2 \\ \end{align*} $$

All that remains is to perform Gaussian elimination on the system, which can be performed in polynomial time. In the system here, we end up with:

$$ \begin{align*} z_3 &= 0~&\mod 2 \\ z_2 &= 1~&\mod 2 \\ z_1 &= -1~&\mod2 \\ \end{align*} $$

Now it is easy to compute that $z_1, z_2 = 1$ and $z_3 = 0$, meaning we keep variables 1 and 2 but not 3. Since the procedure only relies on Gaussian elimination, it runs in polynomial time in $n$ and $m$.

Note that this is a case of the XOR-Satisfiability problem.