# help with understanding strong relevant feature

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


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$$.

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