Suponha que eu tenha pontos em . Isso induz um diagrama de Voronoi. Se eu atribuir a cada um dos pontos um rótulo , eles induzirão uma função binária em . Pergunta: qual é a dimensão VC de todas essas funções binárias possíveis induzidas por alguns pontos e alguma rotulagem desses pontos?
9
Respostas:
Por favor, verifique o Teorema 21.5, Seção 21 do livro "Uma teoria probabilística do reconhecimento de padrões (1996)" de Devroye, Gyorfi e Lugosi. Eu acho que o seguinte limite superior é válido: VC .≤ k + ( d+ 1 ) k2registrok
fonte