Ugly-Duckling-Theorem

Das Ugly-Duckling-Theorem (zu deutsch Hässliches-Entlein-Theorem) ist ein Satz über Ähnlichkeiten verschiedener Merkmale und damit verbundene Aussagen für die Mustererkennung. Es wurde von Satoshi Watanabe bewiesen und trägt seinen Namen nach dem Kunstmärchen Das hässliche Entlein.

Aussage des Theorems

Auf einer Menge von Merkmalen weisen alle Paare von verschiedenen Mustern dieselbe Ähnlichkeit auf. Betrachtet man die Menge aller möglichen Aussagen auf den Mustern, stimmen beide Muster bei immer gleicher Anzahl Aussagen überein, die Anzahl gleicher Aussagen ist sogar konstant und unabhängig von dem gewählten Musterpaar. Wird zudem die Ähnlichkeit über die Anzahl aller möglichen Aussagen gewählt, so ist jedes Musterpaar gleich ähnlich.

Damit ähnelt ein hässliches Entlein genauso einem Schwan wie zwei Schwäne untereinander. Diese Aussage ist der Namensgeber für dieses Theorem.

Eine Aussage über Ähnlichkeiten oder Unterschiede von Mustern ist damit subjektiv und hängt von vorher erfolgten Annahmen ab.

Eine andere Betrachtungsweise ist das systematische Aufstellen aller erdenklichen Ähnlichkeiten der Muster in dem gegebenen Merkmalsraum, und die Aufnahme von Relationen, scheinen diese noch so sinnlos und ohne Bezug auf einen möglichen Anwendungsfall; und so zeigt sich, dass die Anzahl der Ähnlichkeiten stets gleich ist. Diese scheinbar sinnlos aufgenommenen Ähnlichkeiten erscheinen eben durch vorherige Annahmen und der Definition einer Äquivalenzrelation im speziellen Anwendungsfall nicht.

Beweisidee

Die auf einer Menge von Mustern möglichen Aussagen können bei einer diskreten Darstellung über Prädikate dargestellt werden. Diese lassen sich dann wie zum Beispiel durch „$f_{1}$ AND $f_{2}$“ angeben, wenn $f_{i}$ ein Prädikat bezeichnet. Diese Prädikate sollen nun jeweils eine Möglichkeit aus allen möglichen Ähnlichkeiten darstellen.

Beispielhafte Darstellung von Prädikaten und Mustern

Darstellung vier Elemente in einem Venn-Diagramm mit zwei Prädikaten.

Für Elemente $x_{1},x_{2},x_{3},x_{4}$ lassen sich nun solche Prädikate in einem Venn-Diagramm darstellen. Durch verschiedene Kombinationen der Prädikate können Aussagen formal dargestellt werden. Das Prädikat $f_{2}$ kann nun beispielsweise die Aussage „Farbe Blau“ der Fahrzeuge $x_{2}$ und $x_{3}$ markieren.

Mögliche Kombinationen

Diese Elemente können nun in verschiedenster Weise kombiniert werden. Die Anzahl der Kombinationen wird durch $\sum _{r=0}^{n}{n \choose r}=2^{n}$ berechnet, für $n$ die Anzahl der möglichen Muster.

Für das oben gewählt Beispiel sind dies 16 mögliche Aussagen. Neben True (Wahr), False (Falsch) sind dies:

1 Element ( ${4 \choose 1}=4$) Muster Prädikatendarst. $x_{1}$ $f_{1}\operatorname {AND} \operatorname {NOT} f_{2}$ $x_{2}$ $f_{1}\operatorname {AND} f_{2}$ $x_{3}$ $\operatorname {NOT} f_{1}\operatorname {AND} f_{2}$ $x_{4}$ $\operatorname {NOT} (f_{1}\operatorname {OR} f_{2})$

2 Elemente (${4 \choose 2}=6$) Muster Prädikatendarst. $x_{1}\operatorname {OR} x_{2}$ $f_{1}$ $x_{1}\operatorname {OR} x_{3}$ $f_{1}\operatorname {XOR} f_{2}$ $x_{1}\operatorname {OR} x_{4}$ $\operatorname {NOT} f_{2}$ $x_{2}\operatorname {OR} x_{3}$ $f_{2}$ $x_{2}\operatorname {OR} x_{4}$ $\operatorname {NOT} (f_{1}\operatorname {XOR} f_{2})$ $x_{3}\operatorname {OR} x_{4}$ $\operatorname {NOT} f_{1}$

3 Elemente ( ${4 \choose 3}=4$) Muster Prädikatendarst. $x_{1}\operatorname {OR} x_{2}\operatorname {OR} x_{3}$ $f_{1}\operatorname {OR} f_{2}$ $x_{1}\operatorname {OR} x_{2}\operatorname {OR} x_{4}$ $f_{1}\operatorname {OR} \operatorname {NOT} f_{2}$ $x_{1}\operatorname {OR} x_{3}\operatorname {OR} x_{4}$ $\operatorname {NOT} (f_{1}\operatorname {AND} f_{2})$ $x_{2}\operatorname {OR} x_{3}\operatorname {OR} x_{4}$ $\operatorname {NOT} f_{1}\operatorname {OR} f_{2}$

Geteilte Aussagen

Für die vier Muster im obigen Fall gibt es nun Prädikate, die für ein Paar $(x_{i},x_{j})$ beide Muster beinhalten: Für Prädikate mit nur einem Element gibt es keines, für Prädikate mit zwei Elementen gibt es genau ein Prädikat für $(x_{i},x_{j})$ und für Prädikate mit drei Elementen gibt es zwei solcher Prädikate. So sind dies z. B. für $(x_{1},x_{3})$: $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}$ und True (also $x_{1}\operatorname {OR} x_{2}\operatorname {OR} x_{3}\operatorname {OR} x_{4}$).

Allgemein gibt es für ein Paar $(x_{i},x_{j})$ mit $n$ möglichen Mustern $\sum _{r-2}^{n}{n-2 \choose r-2}=(1+1)^{n-2}=2^{n-2}$ geteilte Aussagen.

Diese Formel ist vor allem unabhängig von den gewählten Mustern, also konstant und jedes Paar hat die gleiche Anzahl gemeinsamer Aussagen.

Anwendung

Ähnlich den No-Free-Lunch-Theoremen, bei denen gezeigt wird, dass es keinen generell besten Klassifikator gibt, zeigt das Ugly-Duckling-Theorem, dass es ebenso ohne vorherige Annahmen keine beste Repräsentation von Merkmalen geben kann. Diese bedeutet in der Mustererkennung, dass eine optimale Klassifikation nur unter Annahmen erfolgen kann und stets spezifisch dem Problem angepasst ist.

Literatur

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