Książka „Wprowadzenie do uczenia maszynowego” autorstwa Ethem Alpaydın stwierdza, że wymiar VC prostokąta wyrównanego do osi wynosi 4. Ale jak prostokąt może zniszczyć zestaw czterech punktów współliniowych z naprzemiennymi dodatnimi i ujemnymi punktami?
Czy ktoś może wyjaśnić i udowodnić wymiar VC prostokąta?
tl; dr: Niepoprawna jest definicja wymiaru VC.
Wymiar VC prostokątów jest liczebnością maksymalnego zestawu punktów, które mogą zostać rozbite przez prostokąt.
Wymiar VC prostokątów wynosi 4, ponieważ istnieje zestaw 4 punktów, które mogą zostać rozbite przez prostokąt, a żaden zestaw 5 punktów nie może zostać rozbity przez prostokąt. Tak więc, chociaż prawdą jest, że prostokąt nie może rozbić zestawu czterech współliniowych punktów z naprzemiennymi dodatnimi i ujemnymi, wymiar VC nadal wynosi 4, ponieważ istnieje jedna konfiguracja 4 punktów, która może zostać rozbita.
Wymiar VC algorytmu to maksymalna liczba punktów, takich jak
istnieje taki układ punktów, że
dla wszystkich etykiet tych punktów algorytm nie popełnia błędów
I rzeczywiście, układ czterech punktów (jak diament) jest taki, że prostokąt może oddzielić dowolny zestaw dodatnich punktów od innych. To, że istnieje układ czterech punktów, w których prostokąt ulegnie awarii, nie ma znaczenia.
Rozważ to jak grę między tobą a przeciwnikiem. Ty wybierasz lokalizację punktów, a przeciwnik i tak je nazywa. Jeśli wygra, znajdując etykietę, której nie można rozbić, wymiar VC jest mniejszy niż liczba punktów, ale jeśli wygrasz, wymiar VC jest równy lub większy niż liczba punktów. W swoim pytaniu nie jesteś zmuszony wybrać tego układu, możesz znaleźć lepszy układ punktów, który pozwoli ci wygrać.
źródło