Punti etichettati in $ \ {0,1 \} ^ n $ ANCHE che ogni separatore lineare richiede pesi esponenziali

Question

Voglio trovare campioni etichettati in $ \ {0,1} ^ n $ in modo tale che l'algoritmo perceptron prenda $ 2 ^ {\ omega (n)} $ passaggi per convergere. Un modo per farlo sarebbe quello di trovare una sequenza di esempi etichettati che sono linearmente separabili, ma richiedono che ogni separatore lineare abbia almeno un peso esponenziale. Per dimostrare che i campioni sono linearmente separabili, è sufficiente dimostrare che sono coerenti con un elenco decisionale, che dovrebbe essere evidente dall'elenco dei campioni. Quindi, la mia domanda è

.

Esiste un insieme di campioni etichettati $ s $ in $ \ {0,1 \} ^ n $ che sono coerenti con un elenco decisionale e tale che qualsiasi funzione di soglia lineare che etichetta correttamente $ s $ ha almeno un peso esponenziale di peso $ w_i= 2 ^ {\ omega (n)} $ ?

Ecco le definizioni con cui sto lavorando: una funzione soglia lineare $ f \ Colon \ {0,1 \} ^ n \ to \ {0,1 \} $ con pesi associati $ w_0, \ dots, w_n \ in \ mathbb {r} $ dà $ f (x)= 1 $ se e solo se $ w_1x_1 + w_2x_2 + \ dots + w_nx_n \ geq w_0 $ . Dato un set $ s $ di punti in $ \ {0,1 \} ^ n $ etichettato < Span Class="Math-Container"> $ 0 $ o $ 1 $ , diciamo che una funzione soglia lineare $ f $ etichette correttamente $ s $ se $ f (x)= 1 $ ogni volta $ x $ è etichettato $ 1 $ e $ f (x )= 0 $ quando $ x $ è etichettato $ 0 $ per tutti i $ x \ in s $ .

Nota: Avevo chiesto la stessa domanda su Math.stackexchange da quando sembrava rilevante per entrambi i campi. qui è il link per quello.

Answer 1

Håstad ha dato un esempio ancora migliore nel suo documento sulla dimensione diPesi per porte soglia , che richiede pesi super esponenziali.

Un semplice esempio che richiede pesi esponenziali è la funzione $ \ sum_i 2 ^ i (x_i - y_i) \ geq 0 $ o varianti.