Hypothetically speaking, Given infinite amounts of training data and validation data, can we achieve perfect classification (score of 1) given ML algorithms such as KNN?
Thank you.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Think of the example of recognising cats vs dogs and imagine you are provided with an infinite amount of images of cats only. $\endgroup$– gentedCommented Mar 7, 2019 at 18:25
-
$\begingroup$ shouldn't an infinite amount of data generally tend towards the true output of the data generating process? Or is this irrelevant? When we get a dog and realize it is the wrong classification then wouldn't our KNN learn that? $\endgroup$– skidjoeCommented Mar 7, 2019 at 18:39
-
$\begingroup$ You realise that it is the wrong classification once you are applying it onto a test set; this means the training with infinitely many examples is finished already. The underlying point is that you not only need many examples, but that such examples must span all classes (namely you need both positive and negative examples). $\endgroup$– gentedCommented Mar 7, 2019 at 18:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Short answer : no.
In real life data sets, the data your work with is usually not separable. No matter the shape of the boundary you chose, some points will not have the expected behavior.
If you make more assumptions, then yes, you may achieve a perfect score. Say:
you have a data set and two classes $A$ and $B$ such that $d(A,B) > \epsilon $ for some positive $\epsilon$. (1)
the training sample you observe is uniformly sampled from $A$ an $B$ (otherwise @gented counter example applies)
Given a new point $x$, you want to decide whether it belongs to $A$ or $B$. Now, calling $a_n$ the sequence of points in $A$ and $b_n$ the sequence of points in $B$ start looking for an $n$ such that $d(x, a_n) < \epsilon / 2 $ or $d(x, b_n) < \epsilon / 2 $. Such an $n$ exists (as long as $x$ belongs to one of the classes) otherwise you could prove the existence of a hole in the datasets, contradicting the second hypothesis. Once $n$ found, you know that $x\in A$ if $d(x, a_n) < \epsilon / 2 $.
This is more or less a 1-nearest neighbor search, with a stopping criterion ensuring that we do not need to evaluate the distances between a new point and "all" the points.
(1) the distance between the two sets being defined as the (limit of the) smallest distance between two points from $A$ and $B$
$\begingroup$
$\endgroup$
It depends mainly on the featuers you are using. Imagine, for instance, that you are trying to determine the sex of every human being on Earth knowing only his/her date of birth. Good luck training your model on infinite data!
However, if the classes are perfectly separated by the features incorporated in the model, you can find 100$ accuracy even on finite samples
