132.231.141.109 am 4. Juli 2024 um 07:55 Uhr

2024-07-04T07:55:07Z

Neue Seite

__KEIN_INHALTSVERZEICHNIS__
Eine '''zerschmetterte Menge''' ({{enS|shattered set}}) ist in der Mathematik ein Konzept aus den Bereichen [[Maschinenlernen]], Datenanalyse und [[Mengenlehre]].

Der Begriff wurde von [[J. Michael Steele]] 1975 in seiner Dissertation eingeführt.<ref>Die Dissertation von Steele in Stanford ''Combinatorial Entropy and Uniform Limit Laws,'' wurde teilweise in den Annals of Probability veröffentlicht, ''Empirical discrepancies and subadditive processes'', Band 6, 1978, S. 118–227, [http://www-stat.wharton.upenn.edu/~steele/Rants/ShatteredSets.html Steele: Shattered Sets]</ref> Es wird unter anderem in der Vapnik-Chernovensky-Theorie (VC-Theorie) des Maschinenlernens verwendet.

== Definition ==
Sei <math>(X, \mathcal{F})</math> ein [[Mengensystem]] und <math>A \subseteq X</math>.
<math>A</math> wird <math>\mathcal{F}</math>-''zerschmettert'' genau dann, wenn <math>\{\, F \cap A | F \in \mathcal{F} \,\} = \mathcal{P}(A)</math> mit <math>\mathcal{P}(A)</math> der [[Potenzmenge]] von A, d. h. genau dann, wenn man jede beliebige Teilmenge von <math>A</math> durch Schnitt eines Elements von <math>\mathcal{F}</math> mit <math>A</math> erzeugen kann.

== Beispiel ==
=== Halbebenen und Dreiermengen in der Ebene ===
Sei <math>X = \R^2</math> und <math>\mathcal{F}</math> die Menge aller abgeschlossenen [[Halbebene]]n in <math>\R^2</math>.
Seien außerdem <math>x,y,z\in\R</math> und <math>A=\{x,y,z\}</math>, wobei <math>x</math>, <math>y</math> und <math>z</math> nicht auf einer Gerade liegen (d. h., <math>\alpha x + \beta y+\gamma z \ne 0</math> für alle <math>\alpha,\beta,\gamma\in\R\setminus\{0\}</math>). Dann wird <math>A</math> von <math>\mathcal{F}</math> zerschmettert, da man jede der acht Teilmengen der drei Punkte mittels einer abgeschlossenen Halbebene separieren kann.

Sind <math>x</math>, <math>y</math> und <math>z</math> dagegen [[kollineare Punkte]] (alle auf einer Geraden), so kann der mittlere Punkt nicht von den anderen beiden separiert werden und somit wird <math>A</math> nicht von <math>\mathcal{F}</math> zerschmettert.

=== Maschinenlernen ===
Beim Maschinenlernen ist <math>A</math> meist eine Menge möglicher Ergebnisse entsprechend einer bestimmten Verteilung und <math>\mathcal{F} </math> stellt eine Menge von bekannten Regeln dar. <math>A</math> wird dann <math>\mathcal{F}</math>-zerschmettert, falls grob gesprochen alle Ergebnisse der Verteilung sich aus der Kenntnis der Regeln ergeben.<ref>[https://mathworld.wolfram.com/ShatteredSet.html Christopher Stover, Shattered Set], Mathworld</ref>

== Weblinks ==
*{{MathWorld| id = ShatteredSet| title = Shattered Set| author = Christopher Stover}}
== Einzelnachweise ==
<references />
[[Kategorie:Mengenlehre]]

Zerschmetterte Menge - Versionsgeschichte

132.231.141.109 am 4. Juli 2024 um 07:55 Uhr