Command Palette
Search for a command to run...
أفضل حدود الأخطاء المثلى لتعلم آليات التحويل التتابعي
أفضل حدود الأخطاء المثلى لتعلم آليات التحويل التتابعي
Zachary Chase Steve Hanneke Shay Moran Jonathan Shafer
Abstract
نحلّ حلًا دقيقًا لمشكلة مفتوحة منذ 30 عامًا تتعلق بقدرة البيانات غير المُعلّمة في التعلّم عبر الإنترنت، من خلال تحديد الفجوة بدقة بين التعلّم التحويلي (transductive) والتعلّم عبر الإنترنت القياسي. نُثبت أن كل فئة مفاهيم ذات بعد ليتلستون (Littlestone dimension) يساوي ( d )، فإن حد الخطأ التحويلي يكون على الأقل ( \Omega(\sqrt{d}) ). وهذا يُحدث تحسينًا أساسيًا على الحدود الدنيا السابقة التي كانت على التوالي ( \Omega(\log \log d) )، ( \Omega(\sqrt{d}) )، و ( \Omega(\sqrt{\log d}) )، والتي قدمها بن-ديفيد، كوشيليفيتز، ومانسور (1995، 1997) وهاننيك، موران، وشافر (2023). كما نُظهر أن حدّنا هذا هو حدّ دقيق: لكل قيمة ( d )، توجد فئة ذات بعد ليتلستون ( d ) تحقق حدًّا للخطأ التحويلي يساوي ( O(\sqrt{d}) ). كما أن حدّنا العلوي يُحسّن أفضل حدّ علوي معروف سابقًا، وهو ( \frac{2}{3} \cdot d )، الذي قدمه بن-ديفيد وآخرون (1997). تُظهر هذه النتائج وجود فجوة تربيعية بين التعلّم التحويلي والتعلّم عبر الإنترنت القياسي، مما يُبرز الفائدة الناتجة عن الوصول المُتقدّم إلى تسلسل الأمثلة غير المُعلّمة. ويشكّل هذا تباينًا صارخًا مع بيئة التعلّم القائم على نموذج PAC، حيث تُظهر التعلّم التحويلي والقياسي تعقيدات عينية متشابهة.