Matris Tamamlama
- Ortaya koyan
- Emmanuel Candès & Benjamin Recht
- Yıl
- 2009
- Tür
- Convex low-rank recovery
- Aile
- Missing data
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Matris Tamamlama, küçük, muhtemelen rastgele seçilmiş bir alt kümesinden düşük ranklı bir matrisi kurtarmak için kullanılan bir tekniktir.
Emmanuel Candès ve Benjamin Recht tarafından 2009 yılında tanıtılan bu yöntem, problemi çekirdek norm minimizasyonu — rank minimizasyonu için dışbükey bir vekil — olarak yeniden formüle eder ve matris tutarsızlık koşulunu sağladığında ve girdiler düzgün rastgele gözlemlendiğinde tam kurtarmanın mümkün olduğuna dair teorik garantiler sunar.
Yöntemin mantığı
Çoğu hücresi boş olan, kullanıcı-film derecelendirmelerini içeren kısmen doldurulmuş bir elektronik tablo hayal edin. Eğer altta yatan veriler basit bir yapıya sahipse — örneğin, zevk yalnızca birkaç gizli faktörle, tür tercihi ve dönem gibi, açıklanabiliyorsa — derecelendirmelerin küçük bir kesirini bilmek bile geri kalanını güvenle doldurmak için yeterlidir. Matris tamamlama, yapboz tamamlamaya benzer şekilde, bu gizli düşük boyutlu yapıyı kullanır; sanki resmin yalnızca birkaç farklı şekilden oluştuğunu biliyormuşsunuz gibi.
Tarih
Matris tamamlama, sıkıştırılmış algılama literatüründen ortaya çıkmıştır. Candès ve Recht (2009), çekirdek norm minimizasyonu yoluyla ilk tam kurtarma teoremini ortaya koymuş, ardından Candès ve Tao'nun tutarsızlığın gücü üzerine çalışmaları gelmiştir. Yöntem, düşük ranklı işbirlikçi filtreleme yöntemlerinin en gelişmiş öneri doğruluğunu elde ettiği Netflix Ödülü yarışması aracılığıyla geniş kamu ilgisi görmüştür. Recht, Fazel ve Parrilo'nun sonraki çalışmaları, çekirdek norm minimizasyonunu makine öğrenmesindeki iz normu düzenlileştirmesiyle ilişkilendirmiştir.
Ne zaman kullanılır?
Veriler sistematik olarak eksik girdiler olarak bir matris olarak düzenlenebildiğinde ve gerçek sinyalin düşük ranklı olduğuna inanmak için bir neden olduğunda — örneğin, öneri sistemlerinde, genomikte, sosyal ağ analizinde ve görüntü kurtarmada — matris tamamlama kullanın. Temel varsayımlar, girdilerin rastgele eksik olması ve matrisin bir tutarsızlık koşulunu sağlamasıdır. Yapısal veya rastgele olmayan eksiklikler, çok yüksek ranklı yapılar veya düşük rank varsayımının gerekçelendirilmediği matrisler için uygun değildir. Alternatifler arasında genel eksik veriler için MICE imputasyonu ve negatif olmama durumunun gerekli olduğu durumlarda NMF bulunur.
Sınırlar ve dikkat edilmesi gerekenler
- Yarı-tanımlı programlamanın hesaplama maliyeti, matris boyutlarıyla kötü ölçeklenir
- Tutarsızlık varsayımı, yapısal eksiklikler veya aykırı değerler içeren gerçek veri kümelerinde başarısız olabilir
- Gerçek rank matris boyutlarından çok daha küçük olmadığında performans düşer
- Çekirdek norm minimizasyonu gürültüye duyarlı olabilir; sağlam varyantlar ek karmaşıklık katar
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Hafif koşullar altında, polinom zamanlı dışbükey bir programla kanıtlanabilir şekilde tam kurtarma
- Matris gerçekten düşük ranklı olduğunda çok yüksek eksiklik oranlarını işler
- Rank hakkında önceden bilgi gerekmez; çekirdek norm minimizasyonu bunu örtük olarak bulur
- Rastgele matris teorisi ve dışbükey analize dayanan güçlü teorik garantiler
Uygulama alanları
- İşbirlikçi filtreleme ve öneri sistemleri (kullanıcı-öğe derecelendirmelerini tahmin etme)
- Genomik ve biyoenformatik (eksik ölçümlerle gen ekspresyon matrislerini kurtarma)
- Bilgisayar vizyonu (görüntü tamamlama ve video arka plan çıkarma)
- Sensör ağı yerelleştirme (kısmi mesafe ölçümlerinden konum matrislerini kurtarma)
- Nörobilim (kısmi fMRI gözlemlerinden fonksiyonel bağlantı matrislerini tamamlama)
Nasıl çalışır?
Nasıl çalışır?
Algoritma, girdileri yalnızca bir Ω indeks kümesinde gözlemlenen bir M matrisi ile başlar. Bu gözlemlenen değerler, kurtarma problemi için kısıtlamaları oluşturur. Seyreklik deseni düzgün rastgele örneklenmiş olarak varsayılır; bu, tam kurtarma garantilerinin belirlendiği teorik ortamdır.
Formül
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}Bir matrisin rankını doğrudan minimize etmek NP-zor olduğundan, Candès ve Recht, problemi çözülebilir hale getiren dışbükey bir gevşetme olarak çekirdek normunu — tekil değerlerin toplamı — minimize etmeyi önerirler. Çekirdek normu, sıkıştırılmış algılamada vektörler için L1 normunun oynadığı rolü matrisler için oynar: düşük ranklı çözümleri teşvik ederken, yarı-tanımlı programlama yoluyla problemi çözülebilir tutar.
Formül
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\OmegaKurtarmanın mümkün olması için, gerçek matrisin tekil vektörleri standart baz ile fazla hizalanmamalıdır; bu, μ tutarsızlık parametresi ile ölçülür. Enerjilerini yalnızca birkaç satır veya sütunda yoğunlaştıran matrisler tutarsızdır; yüksek derecede yerelleşmiş matrisler bu koşulu ihlal eder ve rastgele bir örnekten kurtarılamaz, çünkü gözlemlenmeyen girdilerde çok fazla bilgi kodlanmıştır.
Formül
\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}Gözlemlenen girdilerin sayısı, μ'nin rank r çarpı n log n ile orantılı bir eşiği aştığında, çekirdek norm problemi minimizörü, gerçek matrisi yüksek olasılıkla tam olarak kurtarır. Bu sonuç, gerekli örnek boyutunun, rank-r bir matrisin içsel serbestlik derecelerinden yalnızca logaritmik olarak daha büyük olduğunu gösterir ve bu da yaklaşımı bilgi-teorik olarak optimuma yakın hale getirir.
Formül
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}Sık yapılan hatalar
- Gerçek gözlemlerin kullanıcı tarafından seçildiği veya yanlı olduğu (örneğin, yalnızca yüksek puanlı öğelerin derecelendirildiği) durumlarda düzgün rastgele eksikliği varsaymak, teorik örnekleme modelini ihlal eder
- Yeterli gözlemle bile kötü kurtarmaya yol açan tutarsızlık koşulunu kontrol etmeyi ihmal etmek
- Gürültülü ortamda ölçekleme veya düzenlileştirme olmaksızın çekirdek norm minimizasyonu kullanmak, tam kurtarma formülasyonunun uygun olmadığı yerlerde
- Matris tamamlama ile matris ayrıştırma sezgilerini karıştırmak: alternatif en küçük kareler yerel minimumlara yakınsayabilir ve çekirdek norm minimizasyonunun kurtarma garantilerinden yoksundur
Sık sorulan sorular
Matris tamamlama için çekirdek norm minimizasyonu tek yol mudur?
Hayır. Ayrıştırılmış formlar üzerinde alternatif en küçük kareler (ALS) ve gradyan inişi (örneğin, M ≈ UV^T olacak şekilde U ve V üzerinde SGD) ölçeklenebilirlik için pratikte yaygın olarak kullanılır. Ancak, bu dışbükey olmayan yaklaşımlar, çekirdek norm minimizasyonunun tam kurtarma garantilerinden yoksundur ve dikkatli başlatma olmadan yerel minimumlara yakınsayabilir.
Tam kurtarma için ne kadar veriye ihtiyaç vardır?
Candès ve Recht, tutarsızlık parametresi μ'ye sahip n×n rank-r bir matris için yaklaşık C·μ·r·n·log(n) gözlemlenen girdinin yeterli olduğunu göstermiştir. Pratikte bu, düşük ranklı bir matrisin genellikle içsel serbestlik derecelerinin yalnızca küçük bir katından oluşan bir örnekten kurtarılabileceği anlamına gelir; bu, n×n bir matris için r(2n−r)'ye eşittir.
Tutarsızlık koşulu nedir ve neden önemlidir?
Tutarsızlık, tekil vektörlerin koordinat bazına ne kadar yayıldığını ölçer. Yoğunlaşmış tekil vektörlere sahip bir matris — örneğin, yalnızca tek bir satırda sıfırdan farklı olan rank-1 bir matris — bilgisinin çoğunu küçük bir girdi kümesinde depolar. Bu girdiler gözlemlenmemişse, ne kadar çok başka girdi bilinirse bilinsin kurtarma imkansızdır.
İlgili yöntemler
Kaynaklar
Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.
DOI kaynağını açKopyalandı.