Zerschmetterte Menge

Konzept aus den Bereichen maschinelles Lernen, Datenanalyse und Mengenlehre

Eine zerschmetterte Menge (englisch 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.[1] Es wird unter anderem in der Vapnik-Chernovensky-Theorie (VC-Theorie) des Maschinenlernens verwendet.

Definition

Bearbeiten

Sei   ein Mengensystem und  .   wird  -zerschmettert genau dann, wenn   mit   der Potenzmenge von A, d. h. genau dann, wenn man jede beliebige Teilmenge von   durch Schnitt eines Elements von   mit   erzeugen kann.

Beispiel

Bearbeiten

Halbebenen und Dreiermengen in der Ebene

Bearbeiten

Sei   und   die Menge aller abgeschlossenen Halbebenen in  . Seien außerdem   und  , wobei  ,   und   nicht auf einer Gerade liegen (d. h.,   für alle  ). Dann wird   von   zerschmettert, da man jede der acht Teilmengen der drei Punkte mittels einer abgeschlossenen Halbebene separieren kann.

Sind  ,   und   dagegen kollineare Punkte (alle auf einer Geraden), so kann der mittlere Punkt nicht von den anderen beiden separiert werden und somit wird   nicht von   zerschmettert.

Maschinenlernen

Bearbeiten

Beim Maschinenlernen ist   meist eine Menge möglicher Ergebnisse entsprechend einer bestimmten Verteilung und   stellt eine Menge von bekannten Regeln dar.   wird dann  -zerschmettert, falls grob gesprochen alle Ergebnisse der Verteilung sich aus der Kenntnis der Regeln ergeben.[2]

Bearbeiten

Einzelnachweise

Bearbeiten
  1. 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
  2. Christopher Stover, Shattered Set, Mathworld