Pontos rotulados em $ \ {0,1 \} ^ n $ de tal modo que cada separador linear requer pesos exponenciais

Question

Eu quero encontrar amostras rotuladas na $ \ {0,1} ^ n $ De modo que o algoritmo de perceptron leva $ 2 ^ {\ Ômega (n)} $ etapas para convergir. Uma maneira de fazer isso seria encontrar uma sequência de exemplos rotulados que são linearmente separáveis, mas exigem que cada separador linear tenha pelo menos um peso exponencialmente grande. Para mostrar que as amostras são linearmente separáveis, basta mostrar que são consistentes com uma lista de decisões, que deve ser evidente da lista de amostras. Então, minha pergunta é

.

Existe um conjunto de amostras rotuladas $ s $ em $ \ {0,1} ^ n $ que são consistentes com uma lista de decisões e tal que qualquer função de limite linear que marca corretamente $ s $ tem pelo menos um peso exponencialmente grande $ w_i= 2 ^ {\ ômega (n)} $ ?

Aqui estão as definições que estou trabalhando: uma função de limiar linear $ f \ Colon \ {0,1 \} ^ n \ {0,1} $ com pesos associados $ w_0, \ pontos, w_n \ in \ mathbb {r} $ dá $ f (x)= 1 $ se e somente se $ w_1x_1 + w_2x_2 + \ dots + w_nx_n \ geq w_0 $ . Dado um conjunto $ s $ de pontos em $ \ {0,1} ^ n $ rotulado < Classe Span="Recipiente de Matemática"> $ 0 $ ou $ 1 $ , dizemos que uma função de limiar linear $ F $ corretamente rótulos $ s $ se $ f (x)= 1 $ sempre que $ x $ é rotulado $ 1 $ e $ f (x )= 0 $ sempre que $ x $ é rotulado $ 0 $ para todos $ x \ em s $ .

Nota: Eu perguntei a mesma pergunta sobre matemática.stackexchange, já que parecia relevante para os dois campos. aqui é o link para isso.

Answer 1

Håstad deu um exemplo ainda melhor em seu papel no tamanho dePesos para portões de limiar , que requer super peso exponencial.

Um exemplo simples que requer pesos exponenciais é a função $ \ sum_i 2 ^ i (x_i - y_i) \ geq 0 $ ou variantes.