Zerschmetterte Menge

Eine zerschmetterte Menge () 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, 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 Halbebenen 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>Christopher Stover, Shattered Set, Mathworld</ref>

Weblinks

• Christopher Stover: Shattered Set. In: MathWorld (englisch).

Einzelnachweise

<references />