Jaki jest wymiar VC drzewa decyzyjnego?

Jaki jest wymiar VC drzewa decyzyjnego z podziałem k na dwa wymiary? Powiedzmy, że modelem jest CART, a jedyne dozwolone podziały są równoległe do osi.

Tak więc dla jednego podziału możemy zamówić 3 punkty w trójkącie, a następnie dla dowolnego oznaczenia punktów możemy uzyskać doskonałą prognozę (tj. Strzaskane punkty)

Ale co z 2 podziałami lub jakimkolwiek ogólnym k?

Nie jestem pewien, czy jest to pytanie z prostą odpowiedzią, ani nie wierzę, że jest to pytanie, które należy zadać nawet w kwestii drzew decyzyjnych.

Skonsultuj się z Aslanem i in. , Obliczanie wymiaru drzew VC (2009). Rozwiązują ten problem, przeprowadzając wyczerpujące wyszukiwanie w małych drzewach, a następnie zapewniając przybliżoną, rekurencyjną formułę szacowania wymiaru VC na większych drzewach. Następnie używają tej formuły jako części algorytmu przycinania. Gdyby odpowiedź na twoje pytanie była w formie zamkniętej, jestem pewien, że dostarczyliby ją. Czuli potrzebę iteracji przez nawet dość małe drzewa.

$d$$2^d$$2^d$$d$$2^d$$2^d$odpowiedzi Ale nikt nie pasuje do kompletnych drzew. Zazwyczaj zastępujesz, a następnie przycinasz ponownie przy użyciu weryfikacji krzyżowej. Na końcu dostajesz mniejsze i prostsze drzewo, ale Twój zestaw hipotez jest wciąż duży. Aslan i in. spróbuj oszacować wymiar VC rodzin drzew izomorficznych. Każda rodzina jest zestawem hipotez z własnym wymiarem VC.

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

Wydaje się, że rozwiązanie brutalnej siły Aslana działa całkiem dobrze, ale tak naprawdę nie jest to wymiar VC algorytmów używanych przez ludzi, ponieważ opierają się one na przycinaniu i weryfikacji krzyżowej. Trudno powiedzieć, czym właściwie jest przestrzeń hipotez, ponieważ w zasadzie zaczynamy od wstrząsającej liczby możliwych drzew, ale potem przycinamy z powrotem do czegoś bardziej rozsądnego. Nawet jeśli ktoś zacznie od wyboru a priori, aby nie wychodzić poza dwie warstwy, powiedzmy, może nadal być konieczne przycinanie drzewa. I tak naprawdę nie potrzebujemy wymiaru VC, ponieważ walidacja krzyżowa następuje bezpośrednio po błędzie braku próby.

Aby być sprawiedliwym wobec Aslana i wsp., Nie używają wymiaru VC do scharakteryzowania swojej przestrzeni hipotez. Obliczają wymiar VC gałęzi i używają tej ilości do ustalenia, czy gałąź powinna zostać wycięta. Na każdym etapie wykorzystują wymiar VC konkretnej konfiguracji rozważanego oddziału. Nie patrzą na wymiar problemu VC jako całości.

Jeśli twoje zmienne są ciągłe, a odpowiedź zależy od osiągnięcia progu, wtedy drzewo decyzyjne zasadniczo tworzy wiązkę perceptronów, więc wymiar VC prawdopodobnie byłby większy (ponieważ musisz oszacować punkt odcięcia, aby dokonać podziału) . Jeśli odpowiedź zależy monotonicznie od ciągłej odpowiedzi, CART podzieli ją na kilka kroków, próbując odtworzyć model regresji. W tym przypadku nie użyłbym drzew - prawdopodobnie gam lub regresji.