Penyelesaian Matriks
- Diperkenalkan oleh
- Emmanuel Candès & Benjamin Recht
- Tahun
- 2009
- Jenis
- Convex low-rank recovery
- Keluarga
- Missing data
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Penyelesaian matriks adalah teknik untuk memulihkan matriks berperingkat rendah dari sebagian kecil entri yang mungkin acak.
Diperkenalkan oleh Emmanuel Candès dan Benjamin Recht pada tahun 2009, teknik ini merumuskan ulang masalah sebagai minimisasi norma nuklir — sebuah pengganti cembung untuk minimisasi peringkat — dan memberikan jaminan teoretis bahwa pemulihan yang tepat dapat dicapai ketika entri diamati secara seragam secara acak dan matriks memenuhi kondisi inkorensi.
Intuisi di balik metode
Bayangkan spreadsheet yang terisi sebagian dari peringkat pengguna-film di mana sebagian besar sel kosong. Jika data yang mendasarinya memiliki struktur sederhana — katakanlah, selera dijelaskan oleh hanya beberapa faktor laten seperti preferensi genre dan era — maka mengetahui sebagian kecil peringkat sudah cukup untuk mengisi sisanya dengan percaya diri. Penyelesaian matriks memanfaatkan struktur dimensi rendah yang tersembunyi ini, mirip dengan melengkapi teka-teki jigsaw ketika Anda tahu gambarnya hanya memiliki beberapa bentuk yang berbeda.
Sejarah
Penyelesaian matriks muncul dari literatur penginderaan terkompresi. Candès dan Recht (2009) menetapkan teorema pemulihan tepat pertama melalui minimisasi norma nuklir, diikuti oleh karya Candès dan Tao tentang kekuatan inkorensi. Metode ini mendapatkan perhatian publik yang luas melalui kompetisi Netflix Prize, di mana metode penyaringan kolaboratif berperingkat rendah mencapai akurasi rekomendasi terbaik. Karya selanjutnya oleh Recht, Fazel, dan Parrilo menghubungkan minimisasi norma nuklir dengan regularisasi norma jejak dalam pembelajaran mesin.
Kapan digunakan
Gunakan penyelesaian matriks ketika data dapat diatur sebagai matriks dengan entri yang hilang secara sistematis dan ada alasan untuk percaya bahwa sinyal sebenarnya memiliki peringkat rendah — misalnya, dalam sistem rekomendasi, genomik, analisis jaringan sosial, dan pemulihan gambar. Asumsi utama adalah bahwa entri hilang secara acak dan matriks memenuhi kondisi inkorensi. Ini tidak sesuai untuk matriks dengan kelangkaan terstruktur atau non-acak, struktur peringkat sangat tinggi, atau ketika asumsi peringkat rendah tidak dapat dibenarkan. Alternatif termasuk imputasi MICE untuk data hilang umum dan NMF ketika non-negativitas diperlukan.
Batasan dan pertimbangan
- Biaya komputasi pemrograman semidefinit berskala buruk dengan dimensi matriks
- Asumsi inkorensi mungkin gagal dalam kumpulan data nyata dengan kelangkaan terstruktur atau pencilan
- Kinerja menurun ketika peringkat sebenarnya tidak jauh lebih kecil dari dimensi matriks
- Minimisasi norma nuklir dapat sensitif terhadap kebisingan; varian yang kuat menambahkan kompleksitas tambahan
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Pemulihan tepat yang dapat dibuktikan di bawah kondisi ringan dengan program cembung waktu polinomial
- Menangani tingkat kelangkaan yang sangat tinggi ketika matriks benar-benar berperingkat rendah
- Tidak diperlukan pengetahuan sebelumnya tentang peringkat; minimisasi norma nuklir secara implisit menemukannya
- Jaminan teoretis yang kuat berakar pada teori matriks acak dan analisis cembung
Penerapan
- Penyaringan kolaboratif dan sistem rekomendasi (memprediksi peringkat pengguna-item)
- Genomik dan bioinformatika (memulihkan matriks ekspresi gen dengan pengukuran yang hilang)
- Visi komputer (inpainting gambar dan pengurangan latar belakang video)
- Lokalisasi jaringan sensor (memulihkan matriks posisi dari pengukuran jarak parsial)
- Neurosains (melengkapi matriks konektivitas fungsional dari observasi fMRI parsial)
Cara kerjanya
Cara kerjanya
Algoritma dimulai dengan matriks M yang entri-entrinya hanya diamati pada himpunan indeks Omega. Nilai-nilai yang diamati ini membentuk kendala untuk masalah pemulihan. Pola kelangkaan diasumsikan diambil secara seragam secara acak, yang merupakan latar teoretis di mana jaminan pemulihan yang tepat ditetapkan.
Rumus
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}Karena meminimalkan peringkat matriks secara langsung adalah NP-sulit, Candès dan Recht mengusulkan minimisasi norma nuklir — jumlah nilai singular — sebagai relaksasi cembung. Norma nuklir memainkan peran yang sama untuk matriks seperti yang dimainkan norma L1 untuk vektor dalam penginderaan terkompresi: ia mempromosikan solusi berperingkat rendah sambil menjaga masalah tetap dapat dikelola melalui pemrograman semidefinit.
Rumus
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\OmegaAgar pemulihan dimungkinkan, vektor singular dari matriks sebenarnya tidak boleh terlalu selaras dengan basis standar, dikuantifikasi oleh parameter inkorensi mu. Matriks yang memusatkan energinya hanya pada beberapa baris atau kolom adalah inkoren; matriks yang sangat terlokalisasi melanggar kondisi ini dan tidak dapat dipulihkan dari sampel acak, karena terlalu banyak informasi yang dikodekan dalam entri yang tidak diamati.
Rumus
\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}Ketika jumlah entri yang diamati melebihi ambang batas yang berbanding lurus dengan mu dikalikan peringkat r dikalikan n log n, minimizer masalah norma nuklir memulihkan matriks sebenarnya secara tepat dengan probabilitas tinggi. Hasil ini menunjukkan bahwa ukuran sampel yang diperlukan hanya lebih besar secara polilogaritmik daripada derajat kebebasan intrinsik dari matriks peringkat-r, membuat pendekatan ini mendekati optimal secara teori informasi.
Rumus
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}Kesalahan umum
- Mengasumsikan kelangkaan acak seragam ketika observasi nyata dipilih pengguna atau bias (misalnya, hanya item yang diberi peringkat tinggi yang diberi peringkat), yang melanggar model pengambilan sampel teoretis
- Mengabaikan pemeriksaan kondisi inkorensi, yang menyebabkan pemulihan buruk bahkan dengan observasi yang cukup
- Menggunakan minimisasi norma nuklir tanpa penskalaan atau regularisasi dalam pengaturan bising, di mana formulasi pemulihan tepat tidak sesuai
- Mengacaukan penyelesaian matriks dengan heuristik faktorisasi matriks: kuadrat terkecil bergantian dapat konvergen ke minimum lokal dan tidak memiliki jaminan pemulihan dari minimisasi norma nuklir
Pertanyaan yang sering diajukan
Apakah minimisasi norma nuklir satu-satunya cara untuk menyelesaikan penyelesaian matriks?
Tidak. Kuadrat terkecil bergantian (ALS) dan penurunan gradien pada bentuk terfaktorisasi (misalnya, SGD pada U dan V sedemikian rupa sehingga M ≈ UV^T) banyak digunakan dalam praktik untuk skalabilitas. Namun, pendekatan non-cembung ini tidak memiliki jaminan pemulihan yang tepat dari minimisasi norma nuklir dan dapat konvergen ke minimum lokal tanpa inisialisasi yang cermat.
Berapa banyak data yang dibutuhkan untuk pemulihan yang tepat?
Candès dan Recht menunjukkan bahwa sekitar C·mu·r·n·log(n) entri yang diamati cukup untuk matriks peringkat-r n×n dengan parameter inkorensi mu. Dalam praktik ini berarti matriks berperingkat rendah seringkali dapat dipulihkan dari sampel yang hanya merupakan kelipatan kecil dari derajat kebebasan intrinsiknya, yang sama dengan r(2n−r) untuk matriks n×n.
Apa itu kondisi inkorensi dan mengapa itu penting?
Inkorensi mengukur seberapa tersebar vektor singular di seluruh basis koordinat. Matriks dengan vektor singular yang terkonsentrasi — seperti matriks peringkat-1 yang hanya bukan nol di satu baris — menyimpan sebagian besar informasinya dalam sejumlah kecil entri. Jika entri tersebut tidak diamati, pemulihan tidak mungkin dilakukan terlepas dari berapa banyak entri lain yang diketahui.
Metode terkait
Sumber
Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.
Buka referensi DOIDisalin.