Puntos etiquetados en $ \ {0,1 \} ^ n $ de modo que cada separador lineal requiere pesos exponenciales

Question

Quiero encontrar muestras etiquetadas en $ \ {0,1 \} ^ n $ de tal que el algoritmo de perceptron toma $ 2 ^ {\ Omega (n)} $ Pasos para converger. Una forma de hacerlo sería encontrar una secuencia de ejemplos marcados que sean linealmente separables, pero requieren que cada separador lineal tenga al menos un peso exponencialmente grande. Para demostrar que las muestras son linealmente separables, es suficiente para demostrar que son consistentes con una lista de decisiones, que debe ser evidente a partir de la lista de muestras. Entonces, mi pregunta es

¿Existe un conjunto de muestras etiquetadas $ s $ en $ \ {0,1 \} ^ n $ que son consistentes con una lista de decisiones y de tal que cualquier función de umbral lineal que etiquete correctamente $ s $ tiene al menos un peso exponencialmente grande $ w_i= 2 ^ {\ _ omega (n)} $ ?

Aquí están las definiciones con las que estoy trabajando: una función de umbral lineal $ f \ colon \ {0,1 \} ^ n \ a \ {0,1 \ \ \ a \ {0,1 \} $ con pesas asociadas $ w_0, \ dots, w_n \ in \ mathbb {r} $ le da $ f (x)= 1 $ si y solo si $ w_1x_1 + w_2x_2 + \ dots + w_nx_n \ geq w_0 $ . Dado un conjunto $ s $ de puntos en $ \ {0,1 \} ^ n $ etiquetado < Span Class="Math-contenedor"> $ 0 $ o $ 1 $ , decimos que una función de umbral lineal $ F $ correctamente etiquetas $ s $ si $ f (x)= 1 $ siempre que $ x $ está etiquetado $ 1 $ y $ f (x )= 0 $ siempre que $ x $ está etiquetado $ 0 $ para todos $ x \ en S $ .

Nota: había hecho la misma pregunta sobre matemath.stAckexchange, ya que parecía relevante para ambos campos. aquí es el enlace para eso.

Answer 1

Håstad le dio un ejemplo aún mejor en su papel en el tamaño dePesos para puertas de umbral , que requiere pesos súper exponenciales.

Un ejemplo simple que requiere pesos exponenciales es la función $ \ sum_i 2 ^ i (x_i - y_i) \ geq 0 $ o variantes.