Skip to content
بازگشت به نتایج جست‌وجو

تکمیل ماتریس

معرفی‌شده توسط
Emmanuel Candès & Benjamin Recht
سال
2009
نوع
Convex low-rank recovery
خانواده
Missing data

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

تکمیل ماتریس تکنیکی برای بازیابی یک ماتریس با رتبه پایین از زیرمجموعه‌ای کوچک و احتمالاً تصادفی از درایه‌های آن است. این روش که در سال ۲۰۰۹ توسط امانوئل کاندس و بنجامین رشت معرفی شد، مسئله را به صورت کمینه‌سازی هنجار هسته‌ای (nuclear norm) - یک جانشین محدب برای کمینه‌سازی رتبه - بازتعریف می‌کند و تضمین‌های نظری ارائه می‌دهد که بازیابی دقیق در صورت مشاهده درایه‌ها به طور یکنواخت تصادفی و برآورده شدن شرط انسجام (incoherence) توسط ماتریس، قابل دستیابی است.

شهود پشت روش

یک صفحه گسترده نیمه‌پر از امتیازات کاربر-فیلم را تصور کنید که بیشتر سلول‌های آن خالی هستند. اگر داده‌های زیربنایی ساختار ساده‌ای داشته باشند - مثلاً سلیقه توسط تنها چند عامل پنهان مانند ترجیح ژانر و دوره زمانی توضیح داده شود - آنگاه دانستن حتی کسری کوچک از امتیازات برای پر کردن بقیه با اطمینان کافی است. تکمیل ماتریس از این ساختار پنهان با ابعاد پایین بهره می‌برد، بسیار شبیه به تکمیل یک پازل تصویری که می‌دانید تصویر فقط چند شکل متمایز دارد.

تاریخ

تکمیل ماتریس از ادبیات سنجش فشرده (compressed sensing) پدیدار شد. کاندس و رشت (۲۰۰۹) اولین قضیه بازیابی دقیق را از طریق کمینه‌سازی هنجار هسته‌ای برقرار کردند، که به دنبال آن کار کاندس و تائو در مورد قدرت انسجام بود. این روش از طریق رقابت جایزه نتفلیکس (Netflix Prize)، که در آن روش‌های فیلترینگ مشارکتی با رتبه پایین به دقت توصیه پیشرفته دست یافتند، توجه عمومی گسترده‌ای را به خود جلب کرد. کارهای بعدی توسط رشت، فضل و پارریلو، کمینه‌سازی هنجار هسته‌ای را به تنظیم هنجار رد (trace norm regularization) در یادگیری ماشین مرتبط کردند.

چه زمانی استفاده شود

زمانی از تکمیل ماتریس استفاده کنید که داده‌ها را بتوان به صورت یک ماتریس با درایه‌هایی که به طور سیستماتیک گم شده‌اند سازماندهی کرد و دلیلی برای باور به اینکه سیگنال واقعی دارای رتبه پایین است وجود دارد - به عنوان مثال، در سیستم‌های توصیه‌گر، ژنومیک، تحلیل شبکه‌های اجتماعی و بازیابی تصویر. مفروضات کلیدی این است که درایه‌ها به طور تصادفی گم شده‌اند و ماتریس شرط انسجام را برآورده می‌کند. این روش برای ماتریس‌هایی با گمشدگی ساختاریافته یا غیرتصادفی، ساختار رتبه بسیار بالا، یا زمانی که فرض رتبه پایین توجیه‌پذیر نیست، مناسب نیست. جایگزین‌ها شامل استنباط MICE برای داده‌های عمومی گم‌شده و NMF زمانی که عدم منفی بودن مورد نیاز است، می‌باشند.

محدودیت‌ها و ملاحظات

  • هزینه محاسباتی برنامه‌ریزی نیمه‌معین با ابعاد ماتریس به طور ضعیفی مقیاس می‌شود
  • فرض انسجام ممکن است در مجموعه داده‌های واقعی با گمشدگی ساختاریافته یا داده‌های پرت (outliers) شکست بخورد
  • عملکرد زمانی که رتبه واقعی بسیار کوچکتر از ابعاد ماتریس نیست، کاهش می‌یابد
  • کمینه‌سازی هنجار هسته‌ای می‌تواند به نویز حساس باشد؛ انواع مقاوم، پیچیدگی اضافی را اضافه می‌کنند

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • بازیابی دقیق قابل اثبات تحت شرایط ملایم با یک برنامه محدب با زمان چندجمله‌ای
  • نرخ‌های بسیار بالای گمشدگی را در صورتی که ماتریس واقعاً با رتبه پایین باشد، مدیریت می‌کند
  • نیازی به دانش قبلی از رتبه نیست؛ کمینه‌سازی هنجار هسته‌ای به طور ضمنی آن را پیدا می‌کند
  • تضمین‌های نظری قوی ریشه‌دار در تئوری ماتریس تصادفی و تحلیل محدب

کاربردها

  • فیلترینگ مشارکتی و سیستم‌های توصیه‌گر (پیش‌بینی امتیازات کاربر-مورد)
  • ژنومیک و بیوانفورماتیک (بازیابی ماتریس‌های بیان ژن با اندازه‌گیری‌های گم‌شده)
  • بینایی کامپیوتر (نقاشی مجدد تصویر و تفکیک پس‌زمینه ویدئو)
  • مکان‌یابی شبکه حسگر (بازیابی ماتریس‌های موقعیت از اندازه‌گیری‌های جزئی فاصله)
  • علوم اعصاب (تکمیل ماتریس‌های اتصال عملکردی از مشاهدات جزئی fMRI)

چگونه کار می‌کند

چگونه کار می‌کند

1

الگوریتم با ماتریسی M آغاز می‌شود که درایه‌های آن تنها در یک مجموعه شاخص Ω مشاهده شده‌اند. این مقادیر مشاهده‌شده، محدودیت‌های مسئله بازیابی را تشکیل می‌دهند. فرض می‌شود الگوی پراکندگی به طور یکنواخت تصادفی نمونه‌برداری شده است، که تنظیمات نظری است که در آن تضمین‌های بازیابی دقیق برقرار می‌شوند.

فرمول
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}
2

از آنجایی که کمینه‌سازی مستقیم رتبه ماتریس NP-hard است، کاندس و رشت کمینه‌سازی هنجار هسته‌ای - مجموع مقادیر منفرد - را به عنوان یک آرام‌سازی محدب پیشنهاد می‌کنند. هنجار هسته‌ای همان نقشی را برای ماتریس‌ها ایفا می‌کند که هنجار L1 برای بردارها در سنجش فشرده (compressed sensing) ایفا می‌کند: این هنجار راه‌حل‌های با رتبه پایین را ترویج می‌دهد در حالی که مسئله را از طریق برنامه‌ریزی نیمه‌معین (semidefinite programming) قابل حل نگه می‌دارد.

فرمول
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\Omega
3

برای اینکه بازیابی امکان‌پذیر باشد، بردارهای منفرد ماتریس واقعی نباید بیش از حد با پایه استاندارد هم‌راستا باشند، که با پارامتر انسجام μ کمی می‌شود. ماتریس‌هایی که انرژی خود را در تنها چند سطر یا ستون متمرکز می‌کنند، منسجم هستند؛ ماتریس‌های بسیار موضعی این شرط را نقض می‌کنند و از یک نمونه تصادفی قابل بازیابی نیستند، زیرا اطلاعات زیادی در درایه‌های مشاهده نشده رمزگذاری شده است.

فرمول
\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}
4

هنگامی که تعداد درایه‌های مشاهده‌شده از یک حد آستانه متناسب با μ ضربدر رتبه 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}

دام‌های رایج

  • فرض گمشدگی تصادفی یکنواخت در حالی که مشاهدات واقعی کاربر-انتخاب شده یا سوگیرانه هستند (به عنوان مثال، تنها موارد با امتیاز بالا رتبه‌بندی شده‌اند)، که مدل نمونه‌برداری نظری را نقض می‌کند
  • نادیده گرفتن بررسی شرط انسجام، منجر به بازیابی ضعیف حتی با مشاهدات کافی می‌شود
  • استفاده از کمینه‌سازی هنجار هسته‌ای بدون مقیاس‌بندی یا تنظیم (regularization) در محیط نویزی، که در آن فرمول‌بندی بازیابی دقیق نامناسب است
  • اشتباه گرفتن تکمیل ماتریس با روش‌های اکتشافی تجزیه ماتریس: حداقل مربعات متناوب (alternating least squares) ممکن است به مینیمم‌های محلی همگرا شود و تضمین‌های بازیابی کمینه‌سازی هنجار هسته‌ای را ندارد

پرسش‌های متداول

آیا کمینه‌سازی هنجار هسته‌ای تنها راه حل مسئله تکمیل ماتریس است؟

خیر. حداقل مربعات متناوب (ALS) و گرادیان نزولی بر روی فرم‌های تجزیه شده (مانند SGD بر روی U و V به طوری که M ≈ UV^T) به طور گسترده در عمل برای مقیاس‌پذیری استفاده می‌شوند. با این حال، این رویکردهای غیرمحدب فاقد تضمین‌های بازیابی دقیق کمینه‌سازی هنجار هسته‌ای هستند و ممکن است بدون مقداردهی اولیه دقیق به مینیمم‌های محلی همگرا شوند.

چه مقدار داده برای بازیابی دقیق لازم است؟

کاندس و رشت نشان دادند که تقریباً C·μ·r·n·log(n) درایه مشاهده‌شده برای یک ماتریس n×n با رتبه r و پارامتر انسجام μ کافی است. در عمل، این بدان معناست که یک ماتریس با رتبه پایین اغلب می‌تواند از نمونه‌ای که تنها چند برابر درجه آزادی ذاتی آن است (که برای یک ماتریس n×n برابر r(2n−r) است) بازیابی شود.

شرط انسجام چیست و چرا اهمیت دارد؟

انسجام اندازه‌گیری می‌کند که بردارهای منفرد چقدر در سراسر پایه مختصات پراکنده شده‌اند. ماتریسی که بردارهای منفرد آن متمرکز شده‌اند - مانند یک ماتریس رتبه-۱ که تنها در یک سطر غیرصفر است - بیشتر اطلاعات خود را در مجموعه کوچکی از درایه‌ها ذخیره می‌کند. اگر آن درایه‌ها مشاهده نشده باشند، بازیابی صرف نظر از اینکه چند درایه دیگر شناخته شده‌اند، غیرممکن است.

روش‌های مرتبط

منابع

  1. Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.

    باز کردن مرجع DOI
    کپی شد.