Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion
تقترح هذه الورقة خوارزمية الجار الأقرب ثنائية الجانب لإكمال المصفوفات في ظل نماذج العوامل غير الخطية الكامنة ذات النعومة المنخفضة والنسب العالية من القيم المفقودة، مع إثبات أنها تحقق معدلات خطأ مثالية (minimax optimal) تتكيف مع نعومة الدالة الأساسية وتطابق أداء النموذج المثالي (oracle performance) حتى مع وجود مدخلات مفقودة حتمية.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
في العصر الرقمي، نحن محاطون باستمرار بشبكات شاسعة من المعلومات، من الأفلام التي تقترحها خدمة البث إلى الخطوات اليومية التي يتتبعها تطبيق صحي. هذه الشبكات نادراً ما تكون مكتملة؛ فالمستخدمون يتخطون التقييمات، والمستشعرات تفشل في تسجيل البيانات، والناس ببسا هم لا يحضرون في كل موعد مجدول. يكمن التحدي أمام العلماء في ملء هذه القطع المفقودة بدقة دون اختراع معلومات كاذبة. هذه المشكلة، المعروفة باسم "إكمال المصفوفة"، تعتمد على فكرة أن الأنماط الخفية تربط البيانات التي نراها بالبيانات التي لا نراها. فإذا كان الشخص الذي يحب أفلام الحركة يميل أيضاً إلى الاستمتاع بأفلام الخيال العلمي، يمكن للنظام استخدام هذا الرابط لتخمين ما قد يعتقده بشأن فيلم جديد لم يشاهده بعد. ومع ذلك، فإن بيانات العالم الحقيقي فوضوية؛ فالمعلومات المفقودة غالباً ما تكون غير عشوائية؛ فقد يتخطى المستخدم تقييم فيلم لأنه لم يكلف نفسه عناء القيام بذلك لشدة كرهه له، أو قد يفشل مستشعر ما في العمل تحت ظروف معينة فقط. علاوة على ذلك، فإن العلاقات بين المستخدمين والعناصر غالباً ما تكون معقدة وغير خطية، مما يعني أن القواعد البسيطة ذات الخطوط المستقيمة لا يمكنها استيعاب الصورة الكاملة.
قام فريق من الباحثين في جامعة كورنيل وجامعة بنسلفانيا بتطوير طريقة جديدة لمعالجة هذا اللغز الصعب، وتحديداً عندما تكون البيانات مفقودة بطريقة منحازة والأنماط الأساسية معقدة. لقد ركزوا على تقنية تسمى "الجيران الأقرب"، والتي تعمل من خلال إيجاد صفوف وأعمدة متشابهة في شبكة البيانات لإجراء التنبؤات. وبينما تمت دراسة هذا النهج من قبل، إلا أن النظريات السابقة كانت تفترض غالباً أن البيانات مفقودة بشكل عشوائي أو أن العلاقات بين نقاط البيانات سلسة وبسيطة. تساءل الباحثون عما إذا كان بإمكان هذه الطريقة أن تنجح أيضاً عندما تكون البيانات مفقودة بسبب القيم التي تحتويها، وعندما تكون الروابط بين المستخدمين والعناصر متعرجة وغير منتظمة بدلاً من كونها سلسة.
للإجابة على ذلك، حلل الفريق خوارزمية "الجيران الأقرب ثنائية الجانب". تخيل شبكة تمثل فيها الصفوف الأشخاص، وتمثل الأعمدة لحظات زمنية أو أحداثاً معينة. تبحث الخوارزمية عن أشخاص يتصرفون بشكل مشابه للشخص المعني، وتبحث أيضاً عن لحظات مشابهة للحظة المعنية. ومن خلال حساب متوسط النتائج المعروفة من الأشخاص المتشابهين واللحظات المتشابهة، تقوم الطريقة بتقدير القيمة المفقودة. أثبت الباحثون رياضياً أن هذا النهج يتكيف مع تعقيد البيانات؛ فإذا كانت الأنماط الخفية خشنة وغير منتظمة للغاية، تقوم الطريقة بتعديل بحثها لتجد القدر المناسب من التشابه، وإذا كانت الأنماط أكثر سلاسة، فإنها تصقل بحثها وفقاً لذلك. والأهم من ذلك، أنهم أظهروا أن هذه الطريقة تعمل بنفس كفاءة نظام مثالي وعليم يمتلك بالفعل العوامل الخفية التي تحرك البيانات، رغم أن الخوارزمية نفسها لا تعرف ماهية تلك العوامل.
كما أظهرت الدراسة أن الطريقة تظل قوية حتى عندما يكون جزء كبير من البيانات مفقوداً بطريقة حتمية. فعلى سبيل المثال، في سيناريو حيث تُفقد عشرون بالمائة من البيانات بشكل مضمون بسبب قاعدة محددة — مثل عدم تلقي المستخدم لإشعار إذا كان غير متاح — لا تزال الخوارمة تنجح. إنها لا تنهار عندما لا يكون الفقد عشوائياً بل مرتبطاً بالبنية الأساسية للنظام. وقد تحقق الباحثون من هذه النتائج النظرية من خلال عمليات محاكاة حاسوبية مكثفة، واختبار الطريقة مقابل تقنيات أخرى متنوعة. وفي هذه الاختبارات، تفوق نهجهم ثنائي الجانب باستمرار على الطرق القياسية، حيث حافظ على انخفاض ثابت في معدلات الخطأ مع توفر المزيد من البيانات، بينما عانت الطرق الأخرى أو فشلت في التحسن.
ولرؤية كيف يعمل هذا في العالم الحقيقي، طبق الفريق طريقتهم على بيانات من دراسة صحية متنقلة تسمى "HeartSteps". تضمنت هذه الدراسة سبعة وثلاثين مشاركاً تلقوا إشعارات على هواتفهم لتشجيعهم على المشي. كان الهدف هو تقدير عدد الخطوات التي كان سيتخذها الشخص لو تلقى نوعاً معيناً من الإشعارات، حتى عندما لم يتم إرسال ذلك الإشعار فعلياً. ولأن المشاركين لم يكونوا متاحين في كل لحظة، ولأن الإشعارات أُرسلت باحتمالية معينة، كانت البيانات غير مكتملة ومنحازة. عامل الباحثون المستخدمين كصفوف وأوقات القرار كأعمدة، مما خلق شبكة ذات مدخلات مفقودة. وعندما قارنوا طريقتهم بالأخرى، أنتج نهج الجيران الأقرب ثنائي الجانب التقديرات الأكثر دقة، مع أقل قدر من الأخطاء وأكثر النتائج اتساقاً. لقد نجح في التنقل عبر البيانات المفقودة للكشف عن النتائج المرجحة للتدخلات.
تكمن أهمية هذا العمل في قدرته على التعامل مع الواقع الفوضوي للسلوك البشري وبيانات المستشعرات. ومن خلال إثبات أن استراتيجية بحث تكيفية بسيطة نسبياً يمكن أن تضاهي أداء نظام مثالي ذي معرفة كاملة، قدم الباحثون أداة قوية لمجالات تتراوح من محركات التوصية إلى التجارب الطبية. لقد أظهروا أنه حتى عندما تكون البيانات مفقودة وليست عشوائية والارتباطات معقدة، فإننا لسنا بحاجة لمعرفة الأسباب الخفية لإجراء تنبؤات دقيقة. نحن ببساطة بحاجة إلى النظر إلى الجيران في كلا الاتجاهين — عبر الأشخاص وعبر الزمن — وترك الأنماط تظهر. يشير هذا الاكتشاف إلى أنه في عالم من المعلومات غير المكتملة، يمكن للنوع الصحيح من المتوسطات أن يكشف الحقيقة دون الحاجة إلى حل اللغز بأكمله أولاً.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.