tc-SVD nedir?

tc-SVD, kosinüs dönüşümüne dayalı bir tensör çarpımı olan tc-çarpımı üzerine kurulu, üçüncü mertebeden tensörler için bir tekil değer ayrışımıdır. t-SVD'de gizli olan periyodik (başa saran) sınırı yansıtıcı (ayna) bir sınırla değiştirir; böylece FFT'nin yerini ayrık kosinüs dönüşümü (DCT) alır ve her hesaplama reel sayılarda kalır. Mahdi Molavi'nin Tarbiat Modares Üniversitesi'ndeki yüksek lisans tezinde geliştirilmiştir; yakından ilişkili bir kosinüs dönüşümü çarpımı Kernfeld, Kilmer ve Aeron'da (2015) yer alır.

Ortadan kaldırdığı varsayım

t-SVD ayrışımının arkasındaki t-çarpımı, üçüncü mod boyunca bir dairesel evrişimdir. Bunun neden önemli olduğunu görüntü bulanıklığı giderme gösterir. Bulanık bir piksel, komşularının ağırlıklı bir toplamıdır, y_i = ∑_j h_i−j x_j, ve görüntünün kenarına yakın yerlerde bu toplam resmin dışında kalan piksellere ihtiyaç duyar. Onlar hakkında bir şey varsaymak zorundasınız ve bu varsayıma sınır koşulu denir.

Periyodik sınır, sinyalin tekrarlandığını varsayar: sağ kenardan düşen her şey soldan geri girer. Bulanıklık dairesel bir matrise dönüşür ve FFT onunla yapılan her hesaplamayı hızlandırır. t-çarpımı tam olarak bu modeli bir tensörün üçüncü modu boyunca uygular. Sorun şu ki gerçek veri nadiren periyodiktir. Bir fotoğrafın sağ kenarının sol kenarıyla hiçbir ilgisi yoktur ve bir zaman serisinin sonu genellikle başlangıcıyla ilgisizdir. Bunları birbirine yapıştırmak veride hiç olmayan bir sıçrama yaratır ve görüntü onarımında periyodik sınır genellikle kenarlar boyunca artefaktlar bırakır. Ng, Chan ve Tang (1999), yansıtıcı bir sınırın aynı O(n log n) maliyetle daha iyi onarımlar verdiğini gösterdi.

Başa sarma yerine ayna

Yansıtıcı sınır, sinyalin kendi ayna görüntüsü olarak devam ettiğini varsayar: kenarın hemen dışındaki değer hemen içindeki değere eşittir, dolayısıyla yapay bir sıçrama olmaz. Bulanıklık matrisi bu durumda dairesel değil Toeplitz-artı-Hankel yapısındadır ve simetrik çekirdekler için bu biçimdeki matrisler, yine O(n log n) sürede çalışan DCT ile köşegenleştirilir.

Aynı resim (çerçeveli) iki şekilde dolduruluyor. Periyodik sınır uyumsuz kenarları birbirine yapıştırır; yansıtıcı sınır pürüzsüzce devam eder.

tc-çarpımı ve tc-SVD

Tezde bu fikri tensörlere taşıdım. Ön dilimler blok dairesel bir matris yerine blok Toeplitz-artı-Hankel bir matrise yerleştirilir ve üçüncü mod boyunca uygulanan DCT bu matrisi blok köşegenleştirir. İki tensörün tc-çarpımı üç adımda hesaplanır:

1. iki tensörü de üçüncü mod boyunca DCT tabanlı bir dönüşümle dönüştürün (Toeplitz-artı-Hankel yapısına uyan bir köşegen ölçekleme ve bir kaydırma ile birlikte DCT);
2. ön dilimlerini, sıradan matrisler olarak, ikişer ikişer çarpın;
3. sonucu geri dönüştürün.

Çarpım, doğrusal cebirin ihtiyaç duyduğu şeyleri korur. Doğrusal ve birleşmelidir, bir birim elemanı ve bir transpozu vardır ve ortogonal tensörler mevcuttur. DCT ortonormal biçimiyle kullanıldığında, ortogonal bir tensörle çarpmak Frobenius normunu da korur. Ayrışım ardından t-SVD kalıbını izler:

A = U ∗_c S ∗_c V^T

burada U ve V ortogonal, S ise f-köşegendir. Üçüncü mod boyunca DCT alır, her ön dilimde sıradan bir SVD çalıştırır ve çarpanları geri dönüştürürsünüz. Ortonormal DCT ile ilk k terime kesmek, bu çarpım altında rankı en fazla k olan tensörler arasında Frobenius normunda en iyi yaklaşımı verir; bu, t-SVD'nin kendi çarpımı altında sahip olduğu garantinin aynısıdır.

Kesilmiş tc-SVD: U ve V tensörlerinin yalnızca k yanal dilimi ve S tensörünün k köşegen tüpü tutulur.

Bundan t-SVD'ye göre iki pratik fark doğar. Karmaşık sayılar ve eşlenik çiftlerin takibi yoktur; deneylerimde DCT tabanlı sürümler neredeyse her karşılaştırmada daha hızlıydı ve çoğu zaman sürenin yaklaşık yarısında tamamlandı. Tez ayrıca tam ayrışımı atlayan daha ucuz bir sıkıştırma yolu da anlatıyor: tüm ön dilimleri toplayın, toplamın tek bir SVD'sini alın, k₁ sol ve k₂ sağ tekil vektörü tutun ve her dilimi küçük bir k₁×k₂ çekirdeğe sıkıştırın.

Ne için kullandım

• Sınıflandırma. Her görüntü, veri tensörünün bir yanal dilimidir. Yaklaşım I, Kilmer ve çalışma arkadaşlarının t-SVD yöntemini, U tensörünün ilk k yanal diliminden oluşan tek bir ortak tabanla genelleştirir. Tezde yeni olan Yaklaşım II, her sınıf için bir tc-SVD tabanı kurar ve bir test görüntüsünü, onu en küçük artıkla yeniden oluşturan sınıfa atar. MNIST ve CBCL yüz veri kümesi üzerinde test edildi.
• Kümeleme. Kesilmiş bir V üzerinde k-means, isteğe bağlı olarak iki taraftan da indirgenmiş (iki taraflı kesme); ORL, PIE-pose, Extended Yale B ve COIL-100 üzerinde.
• fMRI. ADNI'den alınan dinlenim durumu fMRI verileriyle (82 denek) erken hafif bilişsel bozukluğu (eMCI) sağlıklı kontrollerden ayırt etmek; her denek, satırları 130 zaman noktası, sütunları 90 beyin bölgesi olan bir matris olarak saklandı.
• Akış verisi. Brand'in artımlı SVD'sini (2002) genelleştiren artımlı bir tc-SVD: yeni dilimler dönüştürülür ve her ön dilim yeniden hesaplanmak yerine güncellenir.

Raporlandığı şekliyle sonuçlar

• MNIST ve CBCL'de doğruluk t-SVD'ninkiyle neredeyse tamamen aynıydı (iki MNIST eğrisi de %97 civarında), çalışma süresi ise kabaca yarısı kadardı.
• Kümelemede (on çalıştırmanın ortalaması alınmış en iyi NMI), iki taraflı tc-SVD ORL'de (0,730) ve Extended Yale B'de (0,799) en iyisiydi. PIE-pose'da tüm t-SVD ve tc-SVD varyantları mükemmele yakındı; iki taraflı t-SVD biraz öndeydi (0,994). COIL-100'de HOSVD (0,749) ve NMF (0,730) iki tensör SVD'sini de geride bıraktı.
• Tek taraflı tc-SVD her veri kümesinde tek taraflı t-SVD'den hızlıydı: ORL, Yale B ve COIL-100'de sürenin yarısından azına ihtiyaç duydu, PIE-pose'daki fark ise yaklaşık %13'tü. Yale B ve COIL-100'de HOSVD daha da hızlıydı.
• eMCI ile sağlıklı kontrollerin ayrımında (82 denek, leave-one-out), k değerleri arasındaki en iyi doğruluk tc-SVD için %86,5 (k = 44), t-SVD için %70,7 (k = 13) oldu; bu, tezdeki en büyük farktı. tc-SVD değeri k seçimine duyarlıydı ve bu, bir tanı aracı değil, küçük ölçekli bir çalışmaya ait araştırma sonucudur.

Yani ayna sınırı evrensel bir kazanan değil. Tutarlı avantajı hızdı; doğruluktaki kazanımlar veri kümesine bağlıydı.

Kod

MATLAB uygulaması MIT Lisansı altında github.com/mahdipc/tcSVD adresinde açık kaynak olarak yayımlanıyor. tc-SVD'nin yanı sıra karşılaştırma için FFT tabanlı t-SVD'yi, artımlı güncellemeleri, sınıflandırma ve kümeleme kodunu ve bir HOSVD referans yöntemini içerir. MATLAB için Tensor Toolbox gerektirir. Aşağıdaki fonksiyon adları depodaki yazımıyla verilmiştir:

A = rand(32, 50, 32);           % 50 images of 32x32, one lateral slice each
[U, S, V] = tcSVD(A, 10);       % rank-10 tc-SVD
Ak = tcProdact(U, tcProdact(S, tcTranspose(V)));
relative_error = norm(A(:) - Ak(:)) / norm(A(:))

Tensor Notları'nın 3. bölümü (bkz. Notlar bölümü) bir NumPy ve SciPy taslağı içeriyor; tez özeti ise projenin tamamını ele alıyor.

Sık sorulan sorular

t-SVD ile tc-SVD arasındaki fark nedir?

İkisi de tensörü üçüncü mod boyunca dönüştürür, her ön dilim için bir matris SVD'si çalıştırır ve geri dönüştürür. t-SVD FFT kullanır, periyodik bir sınır varsayar ve karmaşık aritmetikle çalışır; tc-SVD ise DCT kullanır, yansıtıcı bir sınır varsayar ve reel sayılarda kalır.

tc-SVD her zaman t-SVD'den daha mı iyidir?

Hayır. Tez deneylerinde sınıflandırma doğruluğunda t-SVD ile aynı düzeydeydi, ORL ve Extended Yale B'de daha iyi kümeler verdi ve erken evre Alzheimer üzerine küçük bir fMRI çalışmasında daha yüksek bir en iyi doğruluğa ulaştı (tc-SVD için %86,5, t-SVD için %70,7; bu değer k seçimine duyarlıydı). PIE-pose'da t-SVD biraz öndeydi; COIL-100'de ise HOSVD ve NMF ikisini de geride bıraktı. Neredeyse her karşılaştırmada t-SVD'den daha hızlıydı.

tc-SVD neden t-SVD'den daha hızlıdır?

DCT her hesaplamayı reel sayılarda tutar; FFT ise veri reel olsa bile karmaşık sayılarla çalışır. Tez deneylerinde DCT tabanlı sürümler neredeyse her karşılaştırmada daha hızlıydı ve çoğu zaman sürenin yaklaşık yarısında tamamlandı.

tc-SVD'yi kim geliştirdi?

tc-SVD ve onun üzerine kurulan öğrenme yöntemleri, Mahdi Molavi'nin Dr. Mansoor Rezghi danışmanlığında hazırladığı Tensör Temsiliyle Büyük Veri Öğrenimi başlıklı yüksek lisans tezinden (Tarbiat Modares Üniversitesi, 2019) gelir. Yakından ilişkili bir kosinüs dönüşümü çarpımı Kernfeld, Kilmer ve Aeron'da (2015) yer alır.

tc-SVD için kod var mı?

Evet. Sınıflandırma, kümeleme ve artımlı güncellemeleri içeren bir MATLAB uygulaması MIT Lisansı altında github.com/mahdipc/tcSVD adresinde.

Bu bölümdeki diğer sayfalar

• CP, Tucker (HOSVD) ve t-SVD karşılaştırması
• Tensör nedir?
• t-SVD nedir?