Let f(x) be optimal classifier for binary classification where output is modelled noisy.

What does it mean "f(x) makes a mistake only if there is an error on the test point x"? Basically, what is meant by "error on the test point x"?

For content, please see:



Page: 6, last paragraph


1 Answer 1


For noisy random test dataset $(\mathbb{x}, y)$, the similarity-based non-optimal nearest neighbor classifier $g_N$ will have out-of-sample misclassification error probability as expressed by $P[g_N(\mathbb{x}) \neq y]$, and obviously if its nearest neighbor in the training data is erroneously labeled then error probability is pretty high for KNN (=1 for 1NN) classifier, thus nearest neighbor classifier makes a mistake if there's an error on the test point or on its nearest neighbor.

On the other hand, since your assumed optimal (Bayes) classifier $f$ for binary classification where output, say $1$ and $-1$, is modelled noisy via a unique conditional probability distribution $\pi(\mathbb{x})$, for the same noisy random test dataset $(\mathbb{x}, y)$ its out-of-sample misclassification error probability is expressed by $P[f(\mathbb{x}) \neq y]=\text{min}(\pi(\mathbb{x}), 1−\pi(\mathbb{x}))$. Note the erroneously labeled training data outlier(s) would not have much effect on the assumed optimal conditional distribution $\pi(\mathbb{x})$ as long as the whole training data is enough and representative for its population

  • $\begingroup$ you say " ...there's an error on the test point or on its nearest neighbor." What does "there's an error on the test point " mean? $\endgroup$ Commented Nov 21, 2023 at 1:22
  • $\begingroup$ It simply means for some test data features $\mathbb{x}$ its $y$ class label is erroneous, for instance, -1 instead of 1, which is possible. $\endgroup$
    – cinch
    Commented Nov 21, 2023 at 2:36
  • $\begingroup$ I am not sure. To measure error on test point $\mathbf{}x$, you have to know its ground true, ie, the true class label. Otherwise, you cannot define the error. $\endgroup$ Commented Nov 21, 2023 at 8:30
  • $\begingroup$ Error in a test data is in the exactly same sense as error in a training data which as explained in my answer could cause a KNN classifier to misclassify even a correctly labeled test data, once you understand there may be error in training data, you understand same in test data, as both are sometimes partitioned from a single dataset via (k-fold) cross validation. The error measured is for the classifier we're pursuing, not the so called ground truth training/test data themselves which we cannot learn but accept albeit may be erroneous, 'ground truth' naming seems misleading you. $\endgroup$
    – cinch
    Commented Nov 21, 2023 at 16:23
  • 1
    $\begingroup$ Even the optimal classifier would make a mistake if there's an error on the test point whose probability is expressed in the 2nd paragraph of my above answer, the 'error' here is defined to be the classifier's possible out-of-sample misclassification for a randomly drawn sample out of the test dataset $(\mathbb{x}, y)$ which is a random vector, thus it's not defined based on any ground truths but based on the said randomly drawn test data sample. Your mentioned ground truth is only a realized drawn sample from an inherently random source. Hope this clarifies more. $\endgroup$
    – cinch
    Commented Nov 21, 2023 at 19:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .