|
Im ersten Teil der Arbeit beschäftigen wir uns mit dem Problem der Einbettung einer Konzeptklasse in eine Anordnung von Euklidischen Halbräumen. Wir geben untere Schranken für die Dimension und obere Schranken für den Margin solcher
Anordnungen. Für einige Konzeptklassen geben wir Einbettungen mit optimalem Margin explizit an. Ferner diskutieren wir Anwendungen unserer Resultate in der Kommunikationskomplexität.
Im zweiten Teil der Arbeit beschäftigen wir uns mit der kompetitive Analyse von Lernalgorithmen. Insbesondere vereinfachen wir den Beweis einer relativen Fehlerschranke von Vovk für on-line lineare Regression. Wir beweisen eine neue Schranke
für off-line lineare Regression und verallgemeinern die Resultate für on-line lineare Regression auf ein Problem im Reinforcement Lernen.
|