Tensor Notları 3: tc-SVD, Ayna Sınırlı Bir Tensör SVD'si

Önceki notu t-SVD hakkında küçük bir şikâyetle bitirmiştim: blok dairesel (block-circulant) yapısı üçüncü boyutun başa sardığını varsayıyor, yani son dilim ilk dilimin komşusu gibi ele alınıyor. Bu not, o şikâyetle ne yaptığımı anlatıyor. Ortaya çıkan şey, kosinüs dönüşümü üzerine kurulu ve tc-çarpımı adını verdiğim bir tensör çarpımı ile bunun üzerine kurulu bir ayrışım olan tc-SVD. Kosinüs dönüşümüne dayanan ve buna çok yakın bir çarpım Kernfeld, Kilmer ve Aeron'un (2015) çalışmasında da yer alıyor. Tezin kattığı şey öğrenme tarafı: tc-SVD üzerine kurulu sıkıştırma, sınıflandırma, kümeleme ve akan veri için bir güncelleme yöntemi, arkalarındaki deneylerle birlikte.

t-çarpımı kılık değiştirmiş bir evrişimdir

Sorunu görmenin en kolay yolu, aynı matematiğin karşımıza çıktığı bir probleme, görüntülerde bulanıklık gidermeye (deblurring) bakmak. Bulanık bir piksel, komşularının ağırlıklı toplamıdır: y_i = Σ h_i−j x_j; burada h bulanıklık çekirdeğidir. Görüntünün kenarına yakın yerlerde bu toplam, resmin dışında kalan piksellere ihtiyaç duyar. Bu pikseller elimizde yok, dolayısıyla bir şey varsaymak zorundayız. Bu varsayıma sınır koşulu denir.

En basit seçenek periyodik sınırdır: görüntünün kendini tekrar ettiğini varsayarsınız; sağ kenardan taşan her şey soldan geri girer. Bu durumda bulanıklık dairesel bir matrise dönüşür ve FFT her şeyi hızla çözer. t-çarpımı, tam olarak bu modelin bir tensörün üçüncü moduna uygulanmış hâlidir; ikinci bölümde FFT'nin onu ucuz hâle getirmesinin nedeni de budur.

Sorun şu ki gerçek dünyada neredeyse hiçbir şey periyodik değildir. Bir fotoğrafın sağ kenarının sol kenarıyla hiçbir ilgisi yoktur ve ikisini birbirine yapıştırmak, veride hiç olmayan bir sıçrama yaratır. Görüntü onarımında periyodik sınır tipik olarak 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ım sonuçları verdiğini gösterdi.

Onun yerine oraya bir ayna koyun

Yansıtıcı sınır, görüntünün kendi ayna görüntüsü olarak devam ettiğini varsayar. Kenarın hemen dışındaki piksel, hemen içindeki piksele eşittir. Yapay bir sıçrama oluşmaz ve görüntüler için bu çok daha doğal bir varsayımdır.

Aynı resim (çerçeveli) iki farklı şekilde dolgulanmış. Periyodik sınır uyumsuz kenarları birbirine yapıştırır; yansıtıcı sınır ise kesintisiz devam eder.

Yansıtıcı sınırla bulanıklık matrisi artık dairesel değildir; bir Toeplitz-artı-Hankel matrisine dönüşür. Bu kulağa daha kötü geliyor, ama bilinen bir sonuç işimize yarar: simetrik çekirdekler için bu biçimdeki matrisler, tıpkı dairesel matrislerin FFT ile köşegenleştirilmesi gibi, ayrık kosinüs dönüşümü (DCT) ile köşegenleştirilir. DCT de O(n log n) sürede çalışır.

Tek boyuttan tensörlere: tc-çarpımı

Tez bu fikri tensörlere taşıyor. Bir tensörün ön dilimlerini blok dairesel bir matrise yerleştirmek yerine blok Toeplitz-artı-Hankel bir matrise yerleştiriyorum ve üçüncü mod boyunca uygulanan DCT'nin bu matrisi blok köşegenleştirdiğini gösteriyorum. İki tensörün tc-çarpımı bu durumda şöyle işler:

1. İki tensörü de üçüncü mod boyunca DCT tabanlı bir dönüşümle dönüştürün.
2. Karşılık gelen ön dilimlerini sıradan matrisler gibi çarpın.
3. Sonucu geri dönüştürün.

tc-çarpımı, doğrusal cebir yapabilmek için gereken özellikleri korur: doğrusaldır ve birleşmelidir, birim elemanı ve devriği vardır, ortogonal tensörler de mevcuttur. DCT ortonormal biçimiyle kullanıldığında, ortogonal bir tensörle çarpmak Frobenius normunu da korur.

Bunun pratik bir getirisi de var. FFT, veriniz gerçel olsa bile karmaşık sayılarla çalışır. DCT öyle değildir; her şey gerçel kalır. Deneylerimde DCT tabanlı sürümler neredeyse her karşılaştırmada daha hızlıydı ve çoğu zaman FFT tabanlı karşılıklarının yaklaşık yarısı kadar sürdü.

tc-SVD

tc-çarpımı hazır olduğunda SVD öncekiyle aynı kalıbı izler: A = U ∗_c S ∗_c V^T; burada U ve V ortogonal, S ise f-köşegendir. Hesaplamak için üçü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. t-SVD'de olduğu gibi, ilk k terimde kesmek, bu çarpım altında rankı en fazla k olan tensörler arasında Frobenius normuna göre en iyi yaklaşımı verir; onu sıkıştırma ve öğrenme için kullanışlı kılan da budur.

Kesilmiş tc-SVD: U ve V'nin yalnızca k yanal dilimi ve S'nin k köşegen tüpü tutulur.

İşte NumPy ve SciPy ile kısa bir taslak. Okunabilir kalsın diye ortonormal DCT'yi doğrudan kullanıyorum. Toeplitz-artı-Hankel çarpımının arkasındaki tam dönüşüm, Kernfeld, Kilmer ve Aeron'da (2015) olduğu gibi, buna ek olarak bir köşegen ölçekleme ve komşu dilimleri kaydırıp toplama adımı da içerir; ancak algoritmanın genel yapısı aynıdır.

import numpy as np
from scipy.fft import dct, idct

def c_product(A, B):
    Ac = dct(A, type=2, norm="ortho", axis=2)
    Bc = dct(B, type=2, norm="ortho", axis=2)
    return idct(np.einsum("ijk,jlk->ilk", Ac, Bc), type=2, norm="ortho", axis=2)

def tc_svd(A):
    Ac = dct(A, type=2, norm="ortho", axis=2)   # real numbers only
    n1, n2, n3 = A.shape
    U, S, V = np.zeros((n1, n1, n3)), np.zeros((n1, n2, n3)), np.zeros((n2, n2, n3))
    for k in range(n3):
        u, s, vh = np.linalg.svd(Ac[:, :, k])
        U[:, :, k], V[:, :, k] = u, vh.T
        S[:len(s), :len(s), k] = np.diag(s)
    back = lambda T: idct(T, type=2, norm="ortho", axis=2)
    return back(U), back(S), back(V)

A = np.random.rand(6, 5, 4)
U, S, V = tc_svd(A)
Vt = np.transpose(V, (1, 0, 2))                 # transpose every frontal slice
print(np.allclose(A, c_product(c_product(U, S), Vt)))   # True

Bunu ikinci bölümdeki t-SVD koduyla karşılaştırın: karmaşık sayı yok, eşlenikleri takip etme derdi de yok.

Sıkıştırma için bir kısayol

Bir tensörü tc-SVD ile sıkıştırmanın akla ilk gelen yolu, yalnızca ilk k terimi tutmaktır. Tez, tam ayrışımı hiç hesaplamayan, daha ucuz ikinci bir yaklaşım da tanımlıyor. Tüm ön dilimleri toplayıp tek bir matris elde edersiniz, bu toplamın tek bir SVD'sini alırsınız ve k₁ sol ve k₂ sağ tekil vektörü tutarsınız. Ardından her dilim, bir tarafta kesilmiş sol vektörlerin devriğiyle, diğer tarafta sağ vektörlerle çarpılarak küçük bir k₁×k₂ çekirdek olarak sıkıştırılır. Bu yöntem işe yarar, çünkü bu çarpımda U ∗_c S ∗_c V^T ifadesinin dilimlerinin toplamı, U, S ve V'nin dilim toplamları cinsinden düzgünce çarpanlarına ayrılır.

Bir sonraki notta tc-SVD'yi gerçek görevlerde çalıştıracağım: el yazısı rakamları ve yüzleri sınıflandırmak ve birkaç görüntü koleksiyonunu kümelemek; t-SVD, HOSVD ve NMF'ye karşı dürüst sayılarla.

Tarbiat Modares Üniversitesinde Dr. Mansoor Rezghi danışmanlığında hazırladığım “Tensör Temsiliyle Büyük Veri Öğrenimi” başlıklı yüksek lisans tezime dayanan bir serinin parçasıdır.

Bu not İngilizce ve Farsça olarak da yayımlandı: İngilizce · Farsça.