# What is the association rule learning approach to the logical XOR problem?

The "exclusive or" function has a long and arduous history in the AI/machine learning communities. From my understanding of "association rule learning", xor would appear to be a problem for this type of learning. That is, suppose we have the following data:

A    B    C
0    0    0
0    1    1
1    0    1
1    1    0


Clearly the rule I would seek from this data is that $A\oplus B = C$. However, it is my undnerstanding that association rule learning techniques would instead discover the rules $A \Rightarrow C$ and $B \Rightarrow C$ each with 50% confidence.

Is my assessment correct that this is a known issue within association rule learning, and if so, are there standard ways of handling such issues? I can imagine some workarounds, but I'm not sure they fit within the context of association rule learning.

• For me, the problem with XOR is that you have to look at all relevant variables at once to find any clue what's going on -- this of course greatly complicates discovering such rules in many-dimensional systems. – user88 Jun 14 '11 at 22:42
• I'm not an expert in the association rule learning, but what about this: C = A XOR B = NOT(A OR NOT(B)) OR NOT(NOT(A) OR B). Thus, if you introduce new variables X = NOT(A OR NOT(B)) and Y = NOT(NOT(A) OR B), then you will be able to derive the rule C = X OR Y = A XOR B. – Leo Jun 17 '11 at 4:01
• @Leo Yeah I imagined that what you suggested and similar approaches were possible, but they all seemed quite ad hoc. As such, I was wondering if there was a more robust, standard approach to the problem. – Michael McGowan Jun 17 '11 at 14:33
• While you can apply association rules to this idea (don't forget the rule A->B) I'm not sure that it's exactly meaningful in this context. – ybakos Oct 27 '11 at 16:54

## 1 Answer

In this situation you can try to put ~A and ~B into features, then you can learn these rules:

A AND ~B ⇒ C

~A AND B ⇒ C

The problem is the increasing execution time because the number of features is doubled. In addition, you need to know that there is the XOR problem before learning.

• Knowing the problem you're trying to solve makes anything easy. – Marc Claesen May 27 '13 at 9:28