# Classifier which minimizes inaccuracy

I recently interviewed for a machine learning job which involved very mathematically rigorous questions. This is one of them, which I'm still very confused about.

Question: Given a data generating distribution $$\mathbb{P}(x,y)$$ and a classifier $$f(x)$$, where $$x$$ is the observation and $$y$$ is the label, prove that the inaccuracy given by:

$$\mathbb{E}[\mathbb{1}(f(x) \neq y)]$$

is minimized by the classifier: $$f^*(x) = \text{sign}\big(\mathbb{P}(y|x) - \frac{1}{2}\big)$$

where $$\mathbb{1}(a \neq b)$$ is $$1$$ when $$a \neq b$$ and $$0$$ otherwise, and $$\text{sign}(a)$$ gives the arithmetic sign of $$a$$, that is $$+1$$ or $$-1$$.

1. What is the meaning of this statement? What does it say on an intuitive level?
2. What information does it give us about the classifier? Can this information be used to design a "practically good" classifier for the problem which can be learned from data?
3. What is the use of this result? How does it relate to, say, designing a logistic regression classifier? I ask about logistic regression because there also we threshold our predicted probability at $$0.5$$.
• I think there are many ways to attack this. Just so I stay in my comfort zone I would say that minimising the inaccuracy is the same as maximising the accuracy and then go ahead and just browbeat the Naive Bayes on them. Tim's answer here and Antoine's answer here give the necessary background. (Side-note: what kind of job was that? Was it about algorithmic trading?) May 24 '19 at 14:44
• No, it was a research job. The work involves experimenting with new ML algorithms and writing papers. Given that the interviewers were researchers themselves, I guess it makes sense that the interview was so mathematical. May 24 '19 at 15:10
• Fair enough. I hope you get the position! (If you want the position) May 24 '19 at 15:11
• Haha, thanks! Yes, I do want the position and am waiting for their decision. Fingers crossed! :) May 24 '19 at 15:18

• Makes sense, thanks. One more thing that was really confusing to me was the $\mathbb{P}(y|x)$. Why is this a probability between [0, 1]? I thought it should be exactly 0 or 1? Is the true label $\mathbb{P}(y|x)$ probabilistic because of noise in the data collection process? May 24 '19 at 15:08
• Not necessarily. For example, assume y $\in$ {0, 1} and x is a real number. The x of samples with label 0 could follow a normal distribution with mean 0 and sd 1 (D1), while the x of samples with label 1 could follow a second normal distribution of mean 1 and sd 1 (D2). What P(y|x) actually tells you is the probability that x was drawn from say D1 as opposed to D2. However, both D1 and D2 overlap at the upper and lower tails, so there is always a degree on uncertainty. The optimal decision boundary would be the x-value where the curves of D1 and D2 intersect. May 24 '19 at 15:25