VC-Wymiar k-najbliższego sąsiada

Jaki jest wymiar VC algorytmu k-najbliższego sąsiada, jeżeli k jest równe liczbie użytych punktów treningowych?

Kontekst: To pytanie zostało zadane na kursie, na który wybrałem, a odpowiedź brzmiała 0. Nie rozumiem jednak, dlaczego tak jest. Moją intuicją jest to, że Wymiar VC powinien wynosić 1, ponieważ powinno być możliwe wybranie dwóch modeli (tj. Zestawów punktów treningowych), aby każdy punkt był oznaczony jako należący do jednej klasy zgodnie z pierwszym modelem i jako należący do innej klasy zgodnie z drugim modelem, powinno być możliwe zniszczenie jednego punktu. Gdzie jest błąd w moim rozumowaniu?

Mówisz, że algorytm to: k-algorytm najbliższego sąsiada z k = liczba wykorzystanych punktów treningowych. Określam to jako jms-k-najbliższy sąsiad .

Ponieważ wymiar VC jest największą liczbą punktów treningowych, które mogą zostać rozbite przez algorytm z błędem pociągu 0, wymiar VC jms-k-najbliższego sąsiada może wynosić tylko k lub 0.

1 instancja treningowa => k = 1: Podczas szkolenia jms-1-najbliższy sąsiad przechowuje dokładnie tę instancję. Podczas aplikacji na dokładnie tym samym zestawie treningowym, jedna instancja jest najbliższa zapisanej instancji szkolenia (ponieważ są one takie same), więc błąd szkolenia wynosi 0.

Zgadzam się, więc wymiar VC wynosi co najmniej 1.

2 instancje treningowe => k = 2: Problem może występować tylko wtedy, gdy etykiety się różnią. W tym przypadku pytanie brzmi, w jaki sposób podejmowana jest decyzja dotycząca etykiety klasy. Głosowanie większością głosów nie prowadzi do wyniku (VC = 0?), Jeśli użyjemy głosu większego ważonego odwrotnie według odległości, wymiar VC wynosi 2 (zakładając, że nie można mieć tego samego wystąpienia treningowego dwa razy z różnymi etykietami, w tym przypadek wymiaru VC wszystkich algorytmów wynosiłby 0 (tak mi się wydaje)).

Nie ma standardowego algorytmu k-najbliższego sąsiada, jest to raczej rodzina z tym samym podstawowym pomysłem, ale o różnych smakach, jeśli chodzi o szczegóły implementacji.

Wykorzystane zasoby: slajdy wymiarowe VC autorstwa Andrew Moore'a