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

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?)

• I can't understand this. Is that code from some language? Which? Can you formulate this in mathematical notation using $\LaTeX$? Note that "is there... [a] machine learning [algorithm]..." is pretty broad and may not be answerable here. Can you clarify your situation & your question? – gung May 19 '16 at 20:33
• @gung As I understand it, there are n binary-valued independent variables, and the dependent variable is the logical XOR of some subset of the independent variables. The question is how to identify the subset of variables participating in the XOR operation. – josliber May 19 '16 at 20:37
• @gung What josliber said is on-spot. Is it still broad if it's any answer that gives a solution which does not have O(!n) computing time, is acceptable? – LyingOnTheSky May 19 '16 at 20:45

1 Answer

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.