Neural Networks: Neue Verbindung zwischen konvexen n-Breiten und Deckungszahlen

In der Hochdimensionalen Datenanalyse gilt allgemein, dass die Approximation von Funktionsklassen durch lineare Kombinationen einer festen Basis von Merkmalen schwierig ist. Der schlechteste Fehler der besten Basis schrumpft typischerweise nur mit der Ordnung Θ(n⁻¹ᐟᵈ), wobei n die Anzahl der Basisfunktionen und d die Eingangs­dimension ist.

Dennoch gelingt es bei vielen hochdimensionalen Mustererkennungsaufgaben – etwa bei der Gesichtserkennung – mit sehr kleinen Merkmalsets, die Probleme zuverlässig zu lösen. Diese Klassen weisen also keine „Fluch‑der‑Dimensionalität“ auf. Das neue Ergebnis liefert deshalb eine generelle Charakterisierung solcher Klassen: Der Approximationfehler lässt sich durch die Deckungszahl des sogenannten konvexen Kerns bestimmen.

Für neuronale Netze mit einer versteckten Schicht zeigt die Studie, dass die Deckungszahlen der Funktionen, die von einem einzelnen versteckten Knoten erzeugt werden, die Deckungszahlen des konvexen Kerns nach oben begrenzen. Durch die Anwendung etablierter Resultate erhält man damit obere Schranken für die Approximationsgeschwindigkeit von neuronalen Netzklassen.