$ \ {0,1 \} ^ n $的标记点，使每个线性分隔符需要指数权重

Question

我想在 $ \ {0,1 \} ^ n $ 中找到标记的样本，使得perceptron算法需要收敛的步骤。这样做的一种方法是找到一种标记的示例的序列，该示例是线性可分离的，但需要每个线性分离器具有至少一个指数大的重量。为了表明样品是线性可分离的，它足以表明它们与决定列表一致，从样本列表中应该是显而易见的。所以，我的问题是

是否存在一组标记样本 $ s $ 在 $ \ {0,1 \} ^ n $ 与决定列表一致，使得任何正确标签 $ s $ 的任何线性阈值函数都有至少一个指数大的重量 $ w_i= 2 ^ {\ oomga（n）} $ ？

以下是我正在使用的定义：线性阈值函数 $ f \ colon \ {0,1 \} ^ n \ to \ {0,1 \} $ 与关联权重 $ w_0，\ dots，w_n \ in \ mathbb {r} $ 给出 $ f （x）= 1 $ 如果且仅当 $ w_1x_1 + w_2x_2 + \ dots + w_nx_n \ geq w_0 $ 。给定集合 $ s $ 在 $ \ {0,1 \} ^ n $ 标记<跨越类=“math-container”> $ 0 $ 或 $ 1 $ ，我们说一个线性阈值函数 $ f $ 正确标签 $ s $ 如果 $ f（x）= 1 $ 每当每当 $ x $ 标记为 $ 1 $ 和 $ f（x ）= 0 $ 每当 $ x $ 标记为 $ 0 $ 所有 $ x \ in s $ 。

注意：我在math.stackexchange上提出了同样的问题，因为它看起来与这两个领域相关。 这里是那个的链接。

Answer 1

håstad在他的论文中给出了一个更好的例子阈值门的重量，这需要超级指数权重。

需要指数权重的简单示例是函数 $ \ sum_i 2 ^ i（x_i - y_i）\ geq 0 $ 或变体。