Was ist die VC-Dimension eines Entscheidungsbaums?

Was ist die VC-Dimension eines Entscheidungsbaums mit k Teilungen in zwei Dimensionen? Angenommen, das Modell ist CART und die einzigen zulässigen Teilungen verlaufen parallel zu den Achsen.

Für eine Teilung können wir also 3 Punkte in einem Dreieck ordnen und dann für jede Beschriftung der Punkte eine perfekte Vorhersage erhalten (dh: zerbrochene Punkte).

Aber was ist mit 2 Splits oder einem allgemeinen k?

Ich bin mir nicht sicher, ob dies eine Frage mit einer einfachen Antwort ist, noch glaube ich, dass es eine Frage ist, die überhaupt zu Entscheidungsbäumen gestellt werden muss.

Wenden Sie sich an Aslan et al. , Berechnung der VC-Dimension von Bäumen (2009). Sie lösen dieses Problem, indem sie eine umfassende Suche in kleinen Bäumen durchführen und dann eine ungefähre, rekursive Formel zum Schätzen der VC-Dimension in größeren Bäumen bereitstellen. Sie verwenden diese Formel dann als Teil eines Beschneidungsalgorithmus. Hätte es eine geschlossene Antwort auf Ihre Frage gegeben, wäre sie bestimmt gestellt worden. Sie verspürten das Bedürfnis, sich auch durch relativ kleine Bäume hindurchzubewegen.

Meine zwei Cent wert. Ich bin mir nicht sicher, ob es sinnvoll ist, über die VC-Dimension für Entscheidungen zu sprechen. Betrachten Sie eine dimensionale Antwort, bei der jedes Element ein binäres Ergebnis ist. Dies ist die Situation, die von Aslan et al. Es gibt 2 d mögliche Ergebnisse in diesem Probenraum und 2 d mögliche Reaktionsmuster. Wenn ich einen vollständigen Baum mit d Ebenen und 2 d Blättern baue , kann ich jedes Muster von 2 d zerbrechen$d$$2^d$$2^d$$d$$2^d$$2^d$Antworten. Aber niemand passt auf komplette Bäume. In der Regel werden Sie überarbeitet und anschließend mithilfe der Kreuzvalidierung zurückgeschnitten. Am Ende erhalten Sie einen kleineren und einfacheren Baum, aber Ihre Hypothese ist immer noch groß. Aslan et al. versuchen Sie, die VC-Dimension von Familien isomorpher Bäume abzuschätzen. Jede Familie ist eine Hypothese mit einer eigenen VC-Dimension.

$d=3$$(1,0,0,1),(1,1,1,0),(0,1,0,1), (1,1,0,1)$$x1$$x2$

Aslans Brute-Force-Lösung scheint ziemlich gut zu funktionieren, aber was sie bekommen, ist nicht wirklich die VC-Dimension der Algorithmen, die die Leute verwenden, da diese auf Bereinigung und Kreuzvalidierung beruhen. Es ist schwer zu sagen, was der Hypothesenraum eigentlich ist, da wir im Prinzip mit einer erschütternden Anzahl möglicher Bäume beginnen, dann aber auf etwas Vernünftigeres zurückschneiden. Selbst wenn jemand von vornherein beschließt, nicht über zwei Schichten hinauszugehen, kann es dennoch erforderlich sein, den Baum zu beschneiden. Und wir brauchen die VC-Dimension nicht wirklich, da die Kreuzvalidierung direkt nach dem Out-of-Sample-Fehler erfolgt.

Um Aslan et al. Gegenüber fair zu sein, verwenden sie die VC-Dimension nicht, um ihren Hypothesenraum zu charakterisieren. Sie berechnen die VC-Abmessung von Zweigen und bestimmen anhand dieser Menge, ob der Zweig geschnitten werden soll. In jeder Phase verwenden sie die VC-Dimension der spezifischen Konfiguration des betreffenden Zweigs. Sie betrachten nicht die VC-Dimension des Problems als Ganzes.

Wenn Ihre Variablen stetig sind und die Reaktion vom Erreichen eines Schwellenwerts abhängt, erzeugt ein Entscheidungsbaum im Grunde genommen ein Bündel von Perzeptronen, sodass die VC-Dimension vermutlich größer ist als diese (da Sie den Grenzpunkt schätzen müssen, um die Aufteilung vorzunehmen). . Wenn die Antwort monoton von einer kontinuierlichen Antwort abhängt, zerlegt CART sie in mehrere Schritte, um ein Regressionsmodell zu erstellen. In diesem Fall würde ich keine Bäume verwenden - möglicherweise Gam oder Regression.