Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
I am writing something about time series classification and wrote the following:
A classifier is a function that for given input $x_1, ..., x_n$ (in this case representing data stored in audio file) returns $y \in C = \{c_1, ..., c_k\}$, where $C$ is a finite set of classes (like $\{M, F\}$).
But then I realised that it might not be true. However, I can't think of any example of a classifier with an infinite possible number of classes. Do they exist? If so, what are some examples?
According to your definition infinite number of classes should be possible.
One way to think about a classification rule is as a division of feature space into segments. Hence, if we consider a one-dimensional feature space $x_1 \in \mathbb{R} $ as an input we can imagine a classifier that returns a class of "$k$" for any input within $[(k-1):k)$. So it would return "$1$" for $[0:1)$, "$2$" for $[1:2)$, etc.
Such a "model" is not estimated from any data but it is a classification rule.
But in practice having a classifier with an infinite number of samples will probably not be possible, because any dataset will be finite. However, we can imagine an "on-line" classifier that is re-adjusted as new samples come in. And in principle new samples can be of a yet-unseen class. Hence the number of classes can keep increasing forever and not be known in advance.
Classifying images to say which integer was depicted would be a classification problem with a countably infinite set of classes, but you would also need an infinitely large image as the input data. It would also be a rather bad way of solving the problem to view it as single classification problem, rather than construct a solution by classifying the digits and constructing the answer from the component parts (if you did it that way, you might not need an infinite dataset to train it).
I doubt there is a practical case of an infinite set of classes as we have rather finite brains and live rather finite lives (in time and space), so we rarely encounter infinities in a meaningful way.
The Distance dependent Chinese restaurant process may be an example. You can think of it as a clustering method, in which the number of clusters is adaptively chosen based on the data. As you add more data points, the number of clusters can in principle increase without bound. So there are an infinite possible number of clusters (or classes), but for any finite amount of data, only finitely many of the clusters are occupied.
