Paralel Lineer Cebir Temeli

[5]'te tek makinalı ortamda matris çarpımının nasıl yapılacağını, ve nasıl görülecebileğini anlattık. Satır bakış açısı, kolon bakış açısı işlendi. Peki parallel bir ortamda hangi matematik bizi ilgilendirmeli? Mesela \(A^TA\)'yi ele alalım. Bu çarpım oldukça önemli çünkü başka sonuçlar için de kullanılabiliyor, Eşsiz Değer Ayrıştırması (Singular Value Decomposition -SVD-) bunlardan biri.

Büyük Veri ve paralel işlem bağlamında \(A^TA\)'nin önemli şurada; eğer \(A\) matrisi "uzun boylu ve zayıf'' ise, yani çok miktarda satırı ama az miktarda kolonu var ise, \(m \times d\) diyelim, \(A^TA\) çarpımı bize \(d \times d\) boyutunda ufak bir matris verir. Eğer SVD hesabını bu matris üzerinden yapabilirsek, işimizi kolaylaştırmış oluruz.

Satırsal olarak \(A^TA\) hesabı yapmak için satır satır gezerken her satırın kendisi ile dışsal çarpımını (outer product) alıp sonuçları toplamak yeterli [9]. İşlemi daha sözel tarif eden bir açıklama [3]'de bulunabilir.

Peki eşitliğin sağından \(V\)'yi nasıl çıkartırız? Bir dikgen matris çarpı köşegen bir matris çarpı o dikgen matrisin devriği bize bir şeyi hatırlatıyor mu? Evet, bu bir özdeğer / özvektör hesabına benziyor, [2]'de görüldüğü gibi \(A=S\Lambda S^{-1}\) ayrıştırması da var (birimdik matrislerde tersi alma işleminin devrik ile aynı şey olduğunu unutmayalım). O zaman \(A^TA\)'nin öz hesabını yaparsak oradaki özvektör bize \(V\) matrisini verecektir.

Yani \(V\) elde edildikten sonra onunla \(A\)'yi çarpıyoruz, sonra \(\Sigma^{-1}\) ile. \(A\) ne kadar büyük olursa olsun onu bir vektör \(V\) ile çarpmak hızlı işler, \(\Sigma\) ise köşegen, seyrek bir matristir, onun çarpımı da basittir.

import numpy.linalg as lin
import pandas as pd

k = 7 # izdusum uzayinin boyutlari
df = pd.read_csv("../linear_app10rndsvd/w1.dat",sep=';',header=None)
A = np.array(df)[:,1:]
print (A.shape)

ATA = np.dot(A.T,A)
eval,evec = lin.eig(ATA)
u,s,v = lin.svd(A)
print (evec.shape)
print (v.shape)

print ( np.mean(np.abs(evec) - np.abs(v.T)))

Fark çok ufak (abs ile mutlak değer kullandık çünkü bazen tüm bir kolon diğerinin eksi hali olabiliyor).

QR ile SVD yapmak mumkundur. QR ayrıştırması [4] kolonların hepsi bilindiği gibi birbirine dik (orthogonal) birim vektörler olan bir \(Q\) matrisi ve üst üçgensel (upper triangular) bir \(R\) matrisi oluşturur. Ayrıştırmanın \(A^TA\) ile bağlantısı nedir? Eğer \(A\) yerine onun ayrıştırmasını \(QR\) koyarsak,

Tum \(Q\) vektorleri birbirine dik, ve birim vektorler ise, \(Q^T Q\) birim matrisi \(I\) olur. O zaman

Peki \(A^TA\) hesaplayıp (böylece \(R^TR\)'yi elde edince) onun içinden \(R\)'yi nasıl çekip çıkartırız? Şimdi Cholesky ayrıştırması kullanmanın zamanı. Cholesky ayrıştırması (herhangi bir simetrik pozitif kesin \(C\) matrisi üzerinde)

olarak bilinir, yani bir matris alt üçgensel (lower triangular -ki L harfi oradan geliyor-) \(L\) matrisine ve onun devriği olan üst üçgensel \(L^T\)'nin çarpımına ayrıştırılır. Elimizde \(R^TR\) var, ve ona benzer \(LL^T\) var, \(R\) bilindiği gibi üst üçgensel, \(L\) alt üçgensel, \(L^T\) ve \(R\) birbirine eşit demek ki. Yani \(A^TA\) üzerinde sayısal hesap kütüphenimzin Cholesky çağrısı kullanmak bize \(QR\)'in \(R\)'sini verir.

Şu anda akla şu soru gelebilir: madem kütüphane çağrısı yaptık, niye \(A\) üzerinde kütüphenimizin \(QR\) çağrısını kullanmıyoruz?

Cevap Büyük Veri argümanında saklı. Bu ortamda uğraşılan verilerde \(A\) matrisi \(m \times n\) boyutlarındadır, ve \(m\) milyonlar, hatta milyarlarca satır olabilir. Şimdilik \(m >> n\) olduğunu farzedelim, yani \(m\), \(n\)'den "çok, çok büyük", yani "boyut kolonlarının", ki \(n\), sayısı binler ya da onbinlerde. Bu gayet tipik bir senaryo aslında, ölçüm noktaları (boyutlar) var, ama çok fazla değil, diğer yandan o ölçümler için milyonlarca veri noktası toplanmış. Tipik bir aşırı belirtilmiş (överdetermined) sistem - ki en az kareler (least squares) gibi yaklaşımların temel aldığı sistemler bunlardır, eldeki denklem sayısından daha fazla ölçüm noktası vardır. Bu arada en az karelerden bahsettik, \(QR\)'in kullanıldığı alanlardan biri en az karelerin çözümüdür.

Argümana devam ediyoruz, kütüphane qr çağrısını \(A\) üzerinde yaparsak, \(m \times n\) gibi devasa bir matris üzerinde işlem yapmak gerekir. Ama \(A^TA\) üzerinde işlem (Cholesky) yaparsak, ki bu çarpımın boyutu \(n \times m \cdot m \times n = n \times n\), yani çok daha ufak bir matristir. \(A^TA\)'in işlem bedeli çok ufak, birazdan anlatacağımız yöntem sayesinde bu bedel \(O(m)\).

Simdi \(QR\) sonuçlarını kullanarak SVD hesaplamaya gelelim. SVD bize ne verir?

\(U\) ve \(V^T\) dikgen (orthogonal) matrislerdir, \(\Sigma\) sadece köşegeni boyunca değerleri olan bir matristir. Daha fazla detay için bkz [4]. Şimdi \(A = QR\) yerine koyalım,

Bu son formüledeki \(Q^TU\) ibaresi, iki dikgen matrisin çarpımıdır. Lineer Cebir kurallarına göre iki dikgen matrisin çarpımı bir diğer ortogonal matristir. Bu yeni dikgen matrise \(U_R\) adı verelim, o zaman

Bu son formül bize bir şeyler söylüyor. \(R\)'nin SVD üzerinden ayrıştırılabileceğini söylüyor ve bu ayrıştırma sonrası ele geçen \(U_R,V^T\) ve \(\Sigma\) köşegen matrisleridir! Bu çok önemli bir sonuç. Bu ayrıştırmanın sonucu \(A\)'nin ki ile birbirine çok benziyor, tek fark \(U\) ile \(U_R\). Bu iki matris arasındaki geçiş şöyle:

Bu demektir ki eğer \(R\) üzerinde kütüphanemizin svd çağrısını kullanırsak (ki \(R\) nispeten ufak olduğu için bu ucuz olur) ele geçen \(U_R\)'i alıp, \(Q\) ile çarparsak, \(A\) ayrıştırmasının \(U\)'sunu elde ederiz! \(Q\) ile paralel yapılabilir.

[6] [Lineer Cebir ve Hadoop](https://burakbayramli.github.io/dersblog/sk/2015/03/lineer-cebir-hadoop.html)