Ugly Duckling Theorem

The Ugly Duckling Theorem (in German Ugly Duckling Theorem ) is a sentence about similarities of different characteristics and related statements for pattern recognition . It was proven by Satosi Watanabe and is named after the art fairy tale The Ugly Duckling .

Statement of the theorem

On a set of features, all pairs of different patterns have the same similarity. If one looks at the set of all possible statements on the patterns, both patterns agree with the same number of statements, the number of identical statements is even constant and independent of the selected pattern pair. If the similarity is also chosen over the number of all possible statements, then each pattern pair is equally similar.

An ugly duckling is just as similar to a swan as two swans are to each other. This statement is the namesake for this theorem.

A statement about similarities or differences of patterns is therefore subjective and depends on assumptions made beforehand.

Another approach is the systematic listing of all conceivable similarities of the patterns in the given feature space, and the inclusion of relations, no matter how senseless and without reference to a possible application; and so it turns out that the number of similarities is always the same. These apparently senselessly recorded similarities do not appear due to previous assumptions and the definition of an equivalence relation in a special application.

Proof idea

The statements that are possible on a set of patterns can be represented in a discrete representation using predicates . These can then be specified, for example with " AND ", if a predicate is designated. These predicates should now each represent one possibility from all possible similarities. ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$ ${\displaystyle f_{i}}$

Exemplary representation of predicates and patterns

Representation of four elements in a Venn diagram with two predicates.

Such predicates can now be represented for elements in a Venn diagram . Statements can be formally represented by various combinations of the predicates. The predicate can now, for example, mark the statement “color blue” of the vehicles and . ${\displaystyle x_{1},x_{2},x_{3},x_{4}}$ ${\displaystyle f_{2}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{3}}$

Possible combinations

These elements can now be combined in various ways. The number of combinations is calculated by, for the number of possible patterns. ${\displaystyle \sum _{r=0}^{n}{n \choose r}=2^{n}}$ ${\displaystyle n}$

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

1 element ( ) ${\displaystyle {4 \choose 1}=4}$ template Predicate st. ${\displaystyle x_{1}}$ ${\displaystyle f_{1}\operatorname {AND} \operatorname {NOT} f_{2}}$ ${\displaystyle x_{2}}$ ${\displaystyle f_{1}\operatorname {AND} f_{2}}$ ${\displaystyle x_{3}}$ ${\displaystyle \operatorname {NOT} f_{1}\operatorname {AND} f_{2}}$ ${\displaystyle x_{4}}$ ${\displaystyle \operatorname {NOT} (f_{1}\operatorname {OR} f_{2})}$

2 elements ( ) ${\displaystyle {4 \choose 2}=6}$ template Predicate st. ${\displaystyle x_{1}\operatorname {OR} x_{2}}$ ${\displaystyle f_{1}}$ ${\displaystyle x_{1}\operatorname {OR} x_{3}}$ ${\displaystyle f_{1}\operatorname {XOR} f_{2}}$ ${\displaystyle x_{1}\operatorname {OR} x_{4}}$ ${\displaystyle \operatorname {NOT} f_{2}}$ ${\displaystyle x_{2}\operatorname {OR} x_{3}}$ ${\displaystyle f_{2}}$ ${\displaystyle x_{2}\operatorname {OR} x_{4}}$ ${\displaystyle \operatorname {NOT} (f_{1}\operatorname {XOR} f_{2})}$ ${\displaystyle x_{3}\operatorname {OR} x_{4}}$ ${\displaystyle \operatorname {NOT} f_{1}}$

3 elements ( ) ${\displaystyle {4 \choose 3}=4}$ template Predicate st. ${\displaystyle x_{1}\operatorname {OR} x_{2}\operatorname {OR} x_{3}}$ ${\displaystyle f_{1}\operatorname {OR} f_{2}}$ ${\displaystyle x_{1}\operatorname {OR} x_{2}\operatorname {OR} x_{4}}$ ${\displaystyle f_{1}\operatorname {OR} \operatorname {NOT} f_{2}}$ ${\displaystyle x_{1}\operatorname {OR} x_{3}\operatorname {OR} x_{4}}$ ${\displaystyle \operatorname {NOT} (f_{1}\operatorname {AND} f_{2})}$ ${\displaystyle x_{2}\operatorname {OR} x_{3}\operatorname {OR} x_{4}}$ ${\displaystyle \operatorname {NOT} f_{1}\operatorname {OR} f_{2}}$

Shared statements

For the four patterns 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 is exactly one predicate for and for predicates with three elements there is two such predicates. So these are z. B. for : and True (also ). ${\displaystyle (x_{i},x_{j})}$ ${\displaystyle (x_{i},x_{j})}$ ${\displaystyle (x_{1},x_{3})}$ ${\displaystyle x_{1}\operatorname {OR} x_{3},x_{1}\operatorname {OR} x_{2}\operatorname {OR} x_{3},x_{1}\operatorname {OR} x_{3}\operatorname {OR} x_{4}}$ ${\displaystyle x_{1}\operatorname {OR} x_{2}\operatorname {OR} x_{3}\operatorname {OR} x_{4}}$

In general, there are shared statements for a couple with possible patterns . ${\displaystyle (x_{i},x_{j})}$ ${\displaystyle n}$ ${\displaystyle \sum _{r-2}^{n}{n-2 \choose r-2}=(1+1)^{n-2}=2^{n-2}}$

Above all, this formula is independent of the selected patterns, i.e. constant and every pair has the same number of common statements.

application

Similar to the no-free lunch theorem , in which it is shown that there is no generally best classifier, the ugly duckling theorem shows that there can be no best representation of features without prior assumptions . In pattern recognition , this means that an optimal classification can only take place under assumptions and is always specifically adapted to the problem.

literature

• Richard O. Duda, Peter E. Hart, David G. Stork: Pattern classification . Wiley, New York 2001, ISBN 0-471-05669-3 .