imported>Ole...liikhj: /* growthexperiments-addlink-summary-summary:1|1|0 */

2024-09-01T12:27:36Z

growthexperiments-addlink-summary-summary:1|1|0

Neue Seite

Das '''Ugly-Duckling-Theorem''' (zu deutsch ''Hässliches-Entlein-Theorem'') ist ein [[Satz (Mathematik)|Satz]] über Ähnlichkeiten verschiedener Merkmale und damit verbundene Aussagen für die [[Mustererkennung]]. Es wurde von [[Satoshi Watanabe (Physiker)|Satoshi Watanabe]] bewiesen und trägt seinen Namen nach dem [[Kunstmärchen]] ''[[Das hässliche Entlein (Mä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ädikat (Logik)|Prädikate]] dargestellt werden. Diese lassen sich dann wie zum Beispiel durch „<math>f_1</math> [[Konjunktion (Logik)|AND]] <math>f_2</math>“ angeben, wenn <math>f_i</math> 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 ===
[[Datei:Venn-Diagramm mit 4 Elementen und 2 Praedikate.svg|mini|Darstellung vier Elemente in einem Venn-Diagramm mit zwei Prädikaten.]]
Für Elemente <math>x_1, x_2, x_3, x_4</math> 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 <math>f_2</math> kann nun beispielsweise die Aussage „Farbe Blau“ der Fahrzeuge <math>x_2</math> und <math>x_3</math> markieren.

=== Mögliche Kombinationen ===
Diese Elemente können nun in verschiedenster Weise kombiniert werden. Die Anzahl der Kombinationen wird durch <math>\sum_{r=0}^n {n \choose r} = 2^n</math> berechnet, für <math>n</math> 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:
{|
|- style="vertical-align:top;"
|
{| class="wikitable"
|+ 1 Element ( <math>{4 \choose 1} = 4</math>)
!Muster!!Prädikatendarst.
|-
|<math>x_1</math>||<math>f_1 \operatorname{AND} \operatorname{NOT} f_2</math>
|-
|<math>x_2</math>||<math>f_1 \operatorname{AND} f_2</math>
|-
|<math>x_3</math>||<math>\operatorname{NOT} f_1 \operatorname{AND} f_2</math>
|-
|<math>x_4</math>||<math>\operatorname{NOT} (f_1 \operatorname{OR} f_2)</math>
|}
|
{| class="wikitable"
|+ 2 Elemente (<math>{4 \choose 2} = 6</math>)
!Muster!!Prädikatendarst.
|-
|<math>x_1 \operatorname{OR} x_2</math>||<math>f_1</math>
|-
|<math>x_1 \operatorname{OR} x_3</math>||<math>f_1 \operatorname{XOR} f_2</math>
|-
|<math>x_1 \operatorname{OR} x_4</math>||<math>\operatorname{NOT} f_2</math>
|-
|<math>x_2 \operatorname{OR} x_3</math>||<math>f_2</math>
|-
|<math>x_2 \operatorname{OR} x_4</math>||<math>\operatorname{NOT } (f_1 \operatorname{ XOR } f_2)</math>
|-
|<math>x_3 \operatorname{OR} x_4</math>||<math>\operatorname{NOT} f_1</math>
|}
|
{| class="wikitable"
|+ 3 Elemente ( <math>{4 \choose 3} = 4</math>)
!Muster!!Prädikatendarst.
|-
|<math>x_1 \operatorname{OR} x_2 \operatorname{OR} x_3</math>||<math>f_1 \operatorname{OR} f_2</math>
|-
|<math>x_1 \operatorname{OR} x_2 \operatorname{OR} x_4</math>||<math>f_1 \operatorname{OR} \operatorname{NOT} f_2</math>
|-
|<math>x_1 \operatorname{OR} x_3 \operatorname{OR} x_4</math>||<math>\operatorname{NOT} (f_1 \operatorname{AND} f_2)</math>
|-
|<math>x_2 \operatorname{OR} x_3 \operatorname{OR} x_4</math>||<math>\operatorname{NOT} f_1 \operatorname{OR} f_2</math>
|}
|}

=== Geteilte Aussagen ===
Für die vier Muster im obigen Fall gibt es nun Prädikate, die für ein Paar <math>(x_i, x_j)</math> 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 <math>(x_i, x_j)</math> und für Prädikate mit drei Elementen gibt es zwei solcher Prädikate. So sind dies z. B. für <math>(x_1, x_3)</math>: <math>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</math> und ''True'' (also <math>x_1 \operatorname{OR} x_2 \operatorname{OR} x_3 \operatorname{OR} x_4</math>).

Allgemein gibt es für ein Paar <math>(x_i, x_j)</math> mit <math>n</math> möglichen Mustern <math>\sum_{r-2}^n {n-2 \choose r-2} = (1+1)^{n-2} = 2^{n-2}</math> 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-Theoreme]]n, 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 ==
* {{Literatur |Autor=Richard O. Duda, Peter E. Hart, David G. Stork |Titel=Pattern classification |Verlag=Wiley |Ort=New York |Datum=2001 |ISBN=0-471-05669-3}}

[[Kategorie:Klassifizierung]]
[[Kategorie:Satz (Mathematik)]]

Ugly-Duckling-Theorem - Versionsgeschichte

imported>Ole...liikhj: /* growthexperiments-addlink-summary-summary:1|1|0 */