3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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, 2011 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, 2011 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$
    – Michael McGowan
    Jun 17, 2011 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, 2011 at 16:54

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Knowing the problem you're trying to solve makes anything easy. $\endgroup$
    – Marc Claesen
    May 27, 2013 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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