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.

  • $\begingroup$ 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. $\endgroup$
    – user88
    Jun 14 '11 at 22:42
  • $\begingroup$ 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. $\endgroup$
    – Leo
    Jun 17 '11 at 4:01
  • $\begingroup$ @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. $\endgroup$ Jun 17 '11 at 14:33
  • $\begingroup$ 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. $\endgroup$
    – ybakos
    Oct 27 '11 at 16:54

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.

  • $\begingroup$ Knowing the problem you're trying to solve makes anything easy. $\endgroup$ May 27 '13 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.