1
$\begingroup$

According to Kohavi and John (page 5), in the XOR problem feature $X_1$ is strongly relevant, but I suspect this statement.

The strong relevance definition implies $p(Y=y|X_i=x_i, S_i=s_i) \ne p(Y=y|S_i=s_i)$, this means there are some cases where knowledge of $X_i$ modified the probabilities of classifying $y$ under a certain class.

Let´s consider the $Y=0$ case. In this case, $p(Y=0|Si)=\frac48=\frac12$, considering all possible values of $S_i$ where $Y$ is $0$ (cases $0,1,6,7$ in table below). In this case, probability conditioned by $X_i$ is $p(Y=0|X_1=0,S_i)=\frac24=\frac12$ (cases $0,1$ out of possible $0,1,2,3$ cases), and $p(Y=0|X_1=1,S_i)=\frac24=\frac12$ (cases $6$ and $7$ out of possible cases $4,5,6,7$).

Conversely, for case $Y=1: p(Y=1|S_i)=\frac48=\frac12$ (cases $2, 3, 4$ and $5$). $X_i$ conditioned probability is $p(Y=1|X_1=0,S_i)=\frac24=\frac12$ (cases $2, 3$), $p(Y=1|X_1=1,S_i)=\frac24=\frac12$ (cases $4, 5$).

We see that in any of the possible cases the strong relevance condition holds, and we could say that feature $X_1$ is not strictly required to classify $Y$, although it may improve classification accuracy when added to feature set (for instance on cases $0,1,4,5$ adding $X_1$ improves classification accuracy).

Given that this paper is more than $20$ years old I strongly suspect that my understanding is flawed, what am I missing here?

Table

case    X1  X2  X3  X4  X5  Y
0       0   0   0   1   1   0
1       0   0   1   1   0   0
2       0   1   0   0   1   1
3       0   1   1   0   0   1
4       1   0   0   1   1   1
5       1   0   1   1   0   1
6       1   1   0   0   1   0
7       1   1   1   0   0   0
$\endgroup$
1
$\begingroup$

A feature $X_i$ is strongly relevant iff there exists some $x_i, y$, and $s_i$ for which $p(X_i=x_i, S_i=s_i)>0$ such that $$p(Y=y| X_i = x_i, S_i = s_i) \ne p(Y=y | S_i=s_i)$$

Since $P(X_1=0,(X_2,X_3,X_4,X_5)=(0,0,1,1))>0$,

$$P(Y=0|(X_2,X_3,X_4,X_5)=(0,0,1,1))=\frac12$$

but

$$P(Y=0|X_1=0,(X_2,X_3,X_4,X_5)=(0,0,1,1))=1,$$

$X_1$ is strongly relevant.

I think you did not specify your $s_i$.

$\endgroup$
  • $\begingroup$ Thanks, that's right on point, the definition specifies a certain value for Si rather than all of the possible ones. $\endgroup$ – amiando Nov 3 '18 at 17:16

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.