Ugly-Duckling-Theorem

The Ugly Duckling Theorem ( Ugly Duckling to German theorem) is a theorem on similarities of various features and related statements for pattern recognition. It has been proved by Watanabe Satosi and is named after the literary fairy tale The Ugly Duckling.

Statement of the theorem

On a set of features, all the pairs of different patterns on the same similarity. If we consider the set of all possible statements on the patterns, both patterns are always the same number in match statements, the number of similar statements is even constant and independent of the chosen pattern pair. If, moreover, the similarity chosen over the number of all possible statements, each pair of patterns is equal similar.

This is similar to an ugly duckling a swan just like two swans with each other. This statement is the namesake for this theorem.

A statement about the similarities or differences of samples is thus subjective and depends on previously made ​​assumptions.

Another approach is the systematic placing of all possible similarities of the pattern in the given feature space, and the inclusion of relations, yet these seem so pointless and without reference to a possible application; and it is found that the number of similarities is always the same. This seemingly pointless recorded similarities do not appear just by prior assumptions and the definition of an equivalence relation in the specific application.

Idea of ​​proof

The possible on a set of patterns statements can be presented in predicates at a discrete representation. These can then be such as by "AND" specify if a predicate refers. These predicates are now each represent an opportunity for all sorts of similarities.

Exemplary representation of predicates and patterns

For items such predicates can now be represented in a Venn diagram. Through various combinations of the predicates statements can be formally represented. The predicate can now, for example, highlight the statement " Blue " and the vehicles.

Possible combinations

These elements may then be combined in various ways. The number of the combinations is calculated for the number of possible patterns.

For the chosen example above, these are 16 possible statements. In addition to True ( True), False ( False) are:

Divided statements

For the four samples in the above case, there are now predicates that contain both patterns for a pair: For predicates with only one element there is none, for predicates with two elements there exists a predicate for and for predicates with three elements, there are two such predicates. So these are for example: and True ( so ).

Generally, there are shared statements for a couple of possible patterns.

This formula is mainly independent of the selected patterns, so constant and each pair has the same number of common statements.

Application

Similar to the No- Free- Lunch theorems, where it is shown that there is no generally best classifier shows the Ugly Duckling theorem, that there can be no best representation of features as well without prior assumptions. This means in the pattern recognition that an optimum classification can only be done under assumptions and is always specifically adapted to the problem.