Many problems in machine learning are difficult to interpret because the high-dimensional state spaces elude intuition. Certain specific traits of these spaces - often referred to as the curse of dimensionality - influence the distribution of objects, metric properties and other aspects in a way that makes it difficult to apply geometric imagination and methods - leave alone differential (smooth) ones - to the manifolds that express decision regions of - in particular classification - problems in these spaces.
In this article we will restrict ourselves to two- or three-dimensional state spaces to see what we can learn from these much more accessible objects.
Decision Regions in Toy Spaces
How many classification problems can an image of two pixels create?
Let define the number of possible pixel values of a grayscale image and his number of pixels. The totality of all these images forms a -dimensional state space and is called the Classification Toy Space of dimension or .
Consider the following problems:
Binary classification :
For and , possible -pixel images exist. contains different subsets 1 2 and every such subset together with his complement can be interpreted as decision regions of a particular binary classification problem. Obviously, the two classification problems and are equivalent. After removing the trivial cases and considering equivalent partitions the same we have finally non-trivial binary problems. Each of them can be represented as a single image with two colors, marking the complementary decision regions. Note that the latter form a binary partition of .
Classification with classes :
The Stirling Number is the number of partitions of a set of elements by non-empty sets: For and we get the previous case. In general, the number of classification problems with categories in is . In the case is a cube.
Regression Toy Spaces
In order to consider regression problems, we will add an additional dimension to every element of classification toy spaces. This dimension contains values in [0,1] that should in general be interpreted as probabilities before the decision step of a classification problem. The corresponding space is called Regression Toy Space or . In case, the context is unambiguous, we simply use the term Toy Space.
|Spiral-shaped regions for a binary classificator||Decision regions for classification problem with multiple categories|
To be continued...