إكمال المصفوفات
- قدّمه
- Emmanuel Candès & Benjamin Recht
- السنة
- 2009
- النوع
- Convex low-rank recovery
- العائلة
- Missing data
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
إكمال المصفوفات (Matrix Completion) هو أسلوب لاستعادة مصفوفة منخفضة الرتبة من مجموعة صغيرة، قد تكون عشوائية، من مدخلاتها. تم تقديمه بواسطة إيمانويل كانديس وبنجامين ريخت في عام 2009، ويعيد صياغة المشكلة كتقليل المعيار النووي (nuclear norm minimization) - وهو بديل محدب لتقليل الرتبة (rank minimization) - ويوفر ضمانات نظرية بأن الاستعادة الدقيقة ممكنة عندما تُلاحظ المدخلات بشكل عشوائي منتظم وتفي المصفوفة بشرط عدم الترابط (incoherence condition).
الفكرة الحدسية وراء الطريقة
تخيل جدول بيانات مملوء جزئيًا بتقييمات المستخدمين للأفلام حيث تكون معظم الخلايا فارغة. إذا كانت البيانات الأساسية ذات بنية بسيطة - على سبيل المثال، يمكن تفسير الذوق من خلال عدد قليل فقط من العوامل الكامنة مثل تفضيل النوع والعصر - فإن معرفة حتى جزء صغير من التقييمات يكفي لملء الباقي بثقة. يستغل إكمال المصفوفات هذه البنية الكامنة منخفضة الأبعاد، أشبه بإكمال لغز الصور المقطوعة عندما تعرف أن الصورة تحتوي على عدد قليل فقط من الأشكال المميزة.
التاريخ
نشأ إكمال المصفوفات من أدبيات الاستشعار المضغوط. أسس كانديس وريخت (2009) أول نظرية استعادة دقيقة عبر تقليل المعيار النووي، تبعها عن كثب عمل كانديس وتاو حول قوة عدم الترابط. اكتسبت الطريقة اهتمامًا عامًا واسعًا من خلال مسابقة Netflix Prize، حيث حققت طرق الترشيح التعاوني منخفضة الرتبة دقة توصية متطورة. ربط العمل اللاحق بواسطة ريخت وفازل وباريلو بين تقليل المعيار النووي وتنظيم معيار الأثر (trace norm regularization) في التعلم الآلي.
متى تُستخدم
استخدم إكمال المصفوفات عندما يمكن تنظيم البيانات كمصفوفة ذات مدخلات مفقودة بشكل منهجي وهناك سبب للاعتقاد بأن الإشارة الحقيقية منخفضة الرتبة - على سبيل المثال، في أنظمة التوصية، وعلم الجينوم، وتحليل الشبكات الاجتماعية، واستعادة الصور. الافتراضات الرئيسية هي أن المدخلات مفقودة بشكل عشوائي وأن المصفوفة تفي بشرط عدم الترابط. لا يُناسب المصفوفات ذات الفقدان المنظم أو غير العشوائي، أو ذات البنية عالية الرتبة جدًا، أو عندما يكون افتراض الرتبة المنخفضة غير مبرر. تشمل البدائل استكمال MICE للبيانات المفقودة بشكل عام والتحليل غير السلبي للمصفوفات (NMF) عندما تكون اللا-سلبية مطلوبة.
الحدود والاعتبارات
- التكلفة الحسابية للبرمجة شبه المحدبة تتناسب بشكل سيء مع أبعاد المصفوفة
- قد يفشل افتراض عدم الترابط في مجموعات البيانات الحقيقية ذات الفقدان المنظم أو القيم المتطرفة
- يتدهور الأداء عندما لا تكون الرتبة الحقيقية أصغر بكثير من أبعاد المصفوفة
- تقليل المعيار النووي يمكن أن يكون حساسًا للضوضاء؛ المتغيرات القوية تضيف تعقيدًا إضافيًا
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- استعادة دقيقة قابلة للإثبات في ظل ظروف معتدلة باستخدام برنامج محدب بوقت متعدد الحدود
- يتعامل مع معدلات فقدان عالية جدًا عندما تكون المصفوفة منخفضة الرتبة حقًا
- لا يلزم معرفة مسبقة بالرتبة؛ تقليل المعيار النووي يجدها ضمنيًا
- ضمانات نظرية قوية متجذرة في نظرية المصفوفات العشوائية والتحليل المحدب
التطبيقات
- الترشيح التعاوني وأنظمة التوصية (التنبؤ بتقييمات المستخدم-العنصر)
- علم الجينوم والمعلوماتية الحيوية (استعادة مصفوفات التعبير الجيني مع قياسات مفقودة)
- الرؤية الحاسوبية (إعادة بناء الصور وطرح خلفية الفيديو)
- تحديد مواقع شبكات الاستشعار (استعادة مصفوفات المواقع من قياسات المسافة الجزئية)
- علم الأعصاب (إكمال مصفوفات الاتصال الوظيفي من ملاحظات fMRI الجزئية)
كيف يعمل
كيف يعمل
تبدأ الخوارزمية بمصفوفة M التي تُلاحظ مدخلاتها فقط على مجموعة مؤشرات Omega. تشكل هذه القيم المرصودة القيود لمشكلة الاستعادة. يُفترض أن نمط التناثر (sparsity pattern) قد تم أخذ عيناته بشكل عشوائي منتظم، وهو الإعداد النظري الذي تُؤسس فيه ضمانات الاستعادة الدقيقة.
الصيغة
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}نظرًا لأن تقليل رتبة المصفوفة مباشرة هو مشكلة NP-hard، يقترح كانديس وريخت تقليل المعيار النووي - وهو مجموع القيم المفردة (singular values) - كاسترخاء محدب. يلعب المعيار النووي نفس الدور للمصفوفات الذي يلعبه معيار L1 للمتجهات في الاستشعار المضغوط (compressed sensing): فهو يعزز الحلول منخفضة الرتبة مع إبقاء المشكلة قابلة للحل من خلال البرمجة شبه المحدبة (semidefinite programming).
الصيغة
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\Omegaلكي تكون الاستعادة ممكنة، يجب ألا تكون المتجهات المفردة (singular vectors) للمصفوفة الحقيقية متوافقة بشكل مفرط مع الأساس القياسي، ويتم قياس ذلك بمعامل عدم الترابط mu. المصفوفات التي تركز طاقتها في عدد قليل فقط من الصفوف أو الأعمدة تكون غير مترابطة؛ المصفوفات شديدة التركيز تنتهك هذا الشرط ولا يمكن استعادتها من عينة عشوائية، لأن الكثير من المعلومات مشفرة في المدخلات غير المرصودة.
الصيغة
\max_{i} \|U^\top e_i\|^2 \leq \frac{\mu r}{n_1},\quad \max_{j} \|V^\top e_j\|^2 \leq \frac{\mu r}{n_2}عندما يتجاوز عدد المدخلات المرصودة حدًا يتناسب مع mu مضروبًا في الرتبة r مضروبًا في n log n، فإن الحل الأمثل لمشكلة المعيار النووي يستعيد المصفوفة الحقيقية بدقة باحتمالية عالية. تُظهر هذه النتيجة أن حجم العينة المطلوب أكبر فقط بمقدار لوغاريتمي متعدد (polylogarithmically) من درجات الحرية الجوهرية لمصفوفة من الرتبة r، مما يجعل النهج قريبًا من الأمثل من الناحية المعلوماتية.
الصيغة
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}الأخطاء الشائعة
- افتراض فقدان عشوائي منتظم عندما تكون الملاحظات الحقيقية مختارة من قبل المستخدم أو متحيزة (على سبيل المثال، يتم تقييم العناصر ذات التقييم العالي فقط)، مما ينتهك نموذج أخذ العينات النظري
- إهمال التحقق من شرط عدم الترابط، مما يؤدي إلى استعادة ضعيفة حتى مع وجود ملاحظات كافية
- استخدام تقليل المعيار النووي بدون تحجيم أو تنظيم في البيئة الصاخبة، حيث يكون صياغة الاستعادة الدقيقة غير مناسبة
- الخلط بين إكمال المصفوفات واختصارات تحليل المصفوفات: قد يتقارب المربعات الصغرى المتناوبة (alternating least squares) إلى الحد الأدنى المحلي ويفتقر إلى ضمانات الاستعادة لتقليل المعيار النووي
الأسئلة الشائعة
هل تقليل المعيار النووي هو الطريقة الوحيدة لحل إكمال المصفوفات؟
لا. تُستخدم المربعات الصغرى المتناوبة (ALS) والانحدار التدريجي (gradient descent) على الأشكال المحللة (مثل SGD على U و V بحيث M ≈ UV^T) على نطاق واسع في الممارسة العملية لتحقيق قابلية التوسع. ومع ذلك، تفتقر هذه الأساليب غير المحدبة إلى ضمانات الاستعادة الدقيقة لتقليل المعيار النووي وقد تتقارب إلى الحد الأدنى المحلي بدون تهيئة دقيقة.
ما مقدار البيانات المطلوبة للاستعادة الدقيقة؟
أظهر كانديس وريخت أن حوالي C·mu·r·n·log(n) مدخلات مرصودة تكفي لمصفوفة n×n من الرتبة r مع معامل عدم ترابط mu. في الممارسة العملية، يعني هذا أنه يمكن غالبًا استعادة مصفوفة منخفضة الرتبة من عينة هي فقط مضاعف صغير لدرجات حريتها الجوهرية، والتي تساوي r(2n−r) لمصفوفة n×n.
ما هو شرط عدم الترابط ولماذا هو مهم؟
يقيس عدم الترابط مدى انتشار المتجهات المفردة عبر أساس الإحداثيات. المصفوفة ذات المتجهات المفردة المركزة - مثل مصفوفة من الرتبة 1 تكون غير صفرية فقط في صف واحد - تخزن معظم معلوماتها في مجموعة صغيرة من المدخلات. إذا كانت هذه المدخلات غير مرصودة، فإن الاستعادة مستحيلة بغض النظر عن عدد المدخلات الأخرى المعروفة.
طرق ذات صلة
المصادر
Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.
افتح مرجع DOIتم النسخ.