Does an optimal linear classifier perform no better then chance iff class distributions have the same mean?

Question

Assuming there is some nice $P(x, y)$ over $\mathbb R^n \times \{0, 1\}$, can we claim that: The expected accuracy of the optimal linear classifier trained on a large sample from $P(x, y)$ would not exceed 0.5 if and only if $$\mathbb E[x|y=0] = \mathbb E[x|y=1]$$?

I mean, something like:

$$ P \Big[\mathcal R_P(h^*) \geq 0.5 + \delta \Big] \leq \text{veryfastdecrease}(\delta) \iff \mathbb E[x|y=0] = \mathbb E[x|y=1] $$

Where

• $\mathcal R_P (h) = \mathbb E_{x, y\sim P}[h(x) \neq y]$
• $h^* = \arg\min_{h\in H}\mathcal R_P(h)$
• $H = \{h : x \mapsto \text{sign}(Ax+b)\}$

Thank you.

Answer 1

The answer is no. I'll show a simple counterexample where $p(x \mid y=0)$ and $p(x \mid y=1)$ have the same mean, but it's possible to construct a linear classifier with misclassification rate better than chance. (Side note: chance-level performance is only 0.5 when the marginal probabilities of each class are equal; if one class were more probable than the other, we could always output that class as our prediction and be right most of the time).

Let's consider a one-dimensional case, with $X \in \mathbb{R}$. Inputs from the first class have a uniform distribution on the interval $[0, a]$:

$$P(x \mid y=0) = \left \{ \begin{array}{cl} \frac{1}{a} & \text{if } 0 \le x \le a \\ 0 & \text{otherwise} \end{array} \right .$$

Inputs from the second class have an exponential distribution, with mean equal to that of the uniform distribution (i.e. $\frac{a}{2}$):

$$P(x \mid y=1) = \left \{ \begin{array}{cl} \frac{2}{a} e^{-\frac{2}{a} x} & \text{if } x \ge 0 \\ 0 & \text{otherwise} \end{array} \right .$$

Here's a plot of the input distribution for each class when $a=3$:

Construct a classifier $f_t$ with threshold $t \ge 0$, such that the predicted class is 0 if the input is less than or equal to the threshold, and 1 if the input exceeds the threshold. This classifier is trivially linear because we're using the input itself as the decision variable.

$$f_t(x) = \left \{ \begin{array}{cl} 0 & \text{if } x \le t \\ 1 & \text{otherwise} \\ \end{array} \right .$$

We can measure the the classifier's performance for a given threshold using the misclassification rate (i.e. expected value of the 0-1 loss).

$$L(t) = \int_{-\infty}^t P(x \mid y=1) p(y=1) dx + \int_t^\infty P(x \mid y=0) p(y=0) dx$$

Say the classes are equiprobable, so $p(y=0) = p(y=1) = 0.5$. So, chance-level performance is 0.5. Plugging everything in, we have:

$$\begin{array}{ccl} L(t) & = & \int_{0}^t \frac{1}{a} e^{-\frac{2}{a} x} dx + [t \le a] \int_t^a \frac{1}{2a} dx \\ & = & \frac{1}{2} - \frac{1}{2} e^{-\frac{2t}{a}} + [t \le a] \left ( \frac{1}{2} - \frac{t}{2a} \right ) \end{array}$$

where $[\cdot]$ is the Iverson bracket, which returns 1 when its argument is true, otherwise 0.

The misclassification rate can be less than 0.5 (chance level in this case). Here's the misclassification rate as a function of the threshold, for the same example input distributions as above ($a=3$):