نقاط المسمى في $ \ {0،1 \} ^ n $ بحيث يتطلب كل فاصل خطي الأوزان الأسية

Question

أريد أن أجد العينات المسمى في $ \ {0،1 \} ^ n $ بحيث يأخذ خوارزمية perceptron 2 ^ ^ {\ أوميغا (ن)} $ خطوات تتلاقى. سيتم العثور على طريقة واحدة للقيام بذلك في إيجاد تسلسل من الأمثلة المسمى التي يتم فصلها بشكل خطي، ولكنها تتطلب كل فاصل خطي لديه وزن كبير على الأقل بشكل كبير. لإظهار أن العينات منفصلة بشكل خطي، يكفي أن نظهر أنهم متسقون مع قائمة القرار، والتي يجب أن تكون واضحة من قائمة العينات. لذلك، سؤالي هو

هل هناك مجموعة من العينات المسمى $ S $ في $ \ {0،1 \} ^ n $ تتوافق مع قائمة القرار ومع هذه الوظيفة الخطية العتبة التي تسميتها بشكل صحيح $ S $ لديها واحد على الأقل وزن كبير (SPAN Class=" حاوية الرياضيات "> $ w_i= 2 ^ {\ omega (n)} $ ؟

هنا هي التعريفات التي أعملها مع: وظيفة عتبة خطية $ f \ colon \ {0،1 \} ^ n \ {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 $ المسمى < Span Class="حاوية الرياضيات"> $ 0 $ أو $ 1 $ ، نقول أن وظيفة العتبة الخطية $ f $ التسميات الصحيحة $ S $ إذا كان $ f (x)= 1 $ كلما $ x $ يتم وصف $ 1 $ and $ f (x )= 0 $ كلما $ x $ يتم وصف $ 0 $ لجميع $ x \ in s $ .

ملاحظة: قد طلبت نفس السؤال على math.stackexchange منذ أن بدا وثيق الصلة بكلتا المجالين. هنا هو الرابط لذلك.

Answer 1

أعطى HÅSTAD مثالا أفضل في ورقته بحجمالأوزان لبوابات العتبة ، والتي تتطلب أوزان فائقة الأسي.

مثال بسيط يتطلب الأوزان الأسية هو وظيفة $ \ sum_i 2 ^ i (x_i - y_i) \ geq 0 $ أو المتغيرات.