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