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


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

  • $\begingroup$ for Gaussian $P(x|y)$ that must be relatively easy to prove $\endgroup$
    – MInner
    Mar 10, 2017 at 1:53

1 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$:

enter image description here

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$):

enter image description here


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.