Makine Öğreniminde QR Ayrışımı: Ayrıntılı Bir Rehber

QR ayrışımı, veri bilimi ve makine öğreniminin çeşitli alanlarında yaygın olarak kullanılan temel bir matris çarpanlarına ayırma tekniğidir. Karmaşık matrisleri daha basit parçalara ayırma yeteneği, doğrusal cebir problemlerini çözmek ve algoritmaların kararlılığını artırmak için çok ihtiyaç duyulan bir yöntem olmasını sağlar.

İster en küçük kareler doğrusal regresyonu yapıyor olun, ister Python’da veya Python ya da PySpark ile tavsiye motorları kuruyor olun, QR ayrışımını anlamak büyük veri kümeleri ve karmaşık matematiksel modellerle çalışabilme becerinize önemli ölçüde katkı sağlar. 

QR Ayrışımı Nedir?

Bir matrisi çarpanlarına ayırdığınızda (decompose ettiğinizde), o matrisi iki veya daha fazla matrisin çarpımı olarak ifade edersiniz. Başka bir deyişle, matris çarpanlarına ayırma, bir matrisi daha basit bileşenlere bölmenize ve bu bileşenleri matris çarpımıyla yeniden çarptığınızda özgün matrisi yeniden elde etmenize olanak tanır. Matris çarpanlarına ayırma, birçok doğrusal cebir problemini basitleştirir ve çözmeyi kolaylaştırır; bu yüzden önemlidir. 

QR ayrışımı, bir matrisi ortogonal bir Q matrisi ile üst üçgensel bir R matrisinin çarpımına ayırmak için kullanılan özel bir matris çarpanlarına ayırma tekniğidir. Sıkça gördüğümüz denklem A = QR’dir. 

QR ayrışımının görselleştirilmesi. Kaynak: ResearchGate

QR ayrışımını anlamak için, doğrusal cebirde matris çarpımının skaler çarpımın sezgisel kurallarını izlemediğini takdir etmeniz gerekir. Özellikle, matris çarpımı değişmeli değildir; yani genel olarak AB ≠ BA’dır ve bu nedenle “ters” kavramı daha karmaşıktır.

Q ve R Matrisleri Nedir?

İki önemli matrise, yani Q ve R’ye bir göz atalım.

Ortogonal matris Q

Ortogonal bir Q matrisi, transpozesinin aynı zamanda tersi olması özelliğiyle tanımlanır; bu, matematiksel olarak Q^TQ = QQ^T  =  I şeklinde ifade edilir; burada I birim (özdeşlik) matrisidir. Bağlam açısından, transpoze etmek, matrisi köşegeni üzerinden çevirmek anlamına gelir.

Ortogonal bir matrisin bir diğer özelliği de sütunlarının ortonormal bir baz oluşturmasıdır. Bu iki anlama gelir: Birincisi, sütunlar ortogonaldir; yani matristeki herhangi iki farklı sütunun nokta çarpımı sıfırdır. İkincisi ise her sütunun büyüklüğü (birim uzunluğu) birdir.

Ortogonal matrislerle çalışmak iyidir çünkü vektörlerin uzunluklarını ve nokta çarpımlarını korurlar. Yani bir vektörünüz varsa ve onu bir ortogonal matrisle çarparsanız, vektörün uzunluğu aynı kalır. Ayrıca, iki vektörünüz varsa ve her ikisini de aynı ortogonal matrisle çarparsanız, aralarındaki nokta çarpımı da aynı kalır. Son olarak, ortogonal matrisler uzunlukları ve nokta çarpımlarını koruduğundan, dönüşümden sonra vektörlerin geometrik özelliklerini bozmazlar. Yani, iki vektör dönüşümden önce birbirine dikse, ortogonal matrisi uyguladıktan sonra da dik kalırlar. 

Üst üçgensel matris R

Üst üçgensel bir R matrisi, ana köşegenin altındaki tüm elemanların sıfır olduğu bir matris türüdür. Bu form, matris denklemlerini basitleştirir ve özellikle geri yerine koyma (back substitution) gibi yöntemlerle doğrusal denklem sistemlerini çözmede faydalıdır. QR ayrışımında R’nin, özgün matrisin büyüklük ve yönelimini yakalayan bileşeni temsil ettiğini de söyleyebiliriz.

QR Ayrışımı Yapmanın Yolları

QR ayrışımını gerçekleştirmenin farklı yollarına kısaca bakalım.

Gram–Schmidt süreci 

Gram–Schmidt süreci, doğrusal olarak bağımsız bir vektör kümesini sistematik biçimde ortonormal bir kümeye dönüştürmek için kullanılan bir algoritmadır. Bu süreç, QR ayrışımımızdaki Q matrisini oluşturmak için özellikle kullanılır ve Q’yu elde ettikten sonra R’yi türetebiliriz. 

Givens döndürmeleri

Givens döndürmeleri, QR ayrışımına yardımcı olmak için kullanılan bir başka yöntemdir. Givens döndürmelerinde, matris A’nın köşegeninin altına sıfırlar yerleştirmek için bir dizi düzlemsel döndürme uygulanır. Her döndürme, vektörün uzunluğunu korurken matrisi üst üçgensel forma dönüştürecek şekilde bir koordinat çifti üzerinde etkili olur. Bu yöntem, her adımda matrisin yalnızca küçük bir kısmını değiştirdiğinden seyrek matrisler için verimlidir.

Householder yansımaları

Householder yansımaları, Householder matrisleri olarak bilinen yansıma matrislerini kullanarak matris A’nın köşegen altı elemanlarını sistematik olarak yok eden daha genel bir tekniktir. Her Householder matrisi, köşegenin altındaki bir sütunu sıfırlamak için seçilen vektöre dik bir düzlem boyunca bir vektörü yansıtır. Sonuç olarak bir ortogonal Q matrisi ve bir üst üçgensel R matrisi elde edilir. Householder yansımaları, sayısal kararlılıkları nedeniyle özellikle yoğun matrisler için uygundur.

R’da QR Ayrışımının Uygulanması

Bu bölümde, hızlı bir uygulama için yerleşik qr() fonksiyonunu kullanarak ve ardından sezgimizi güçlendirmek için Gram–Schmidt sürecini en baştan adım adım izleyerek R’da QR ayrışımını pratiğe dökeceğiz. Her iki bölümde de kullanacağımız matrix_A’yı oluşturarak başlayalım.  

matrix_A <- matrix(c(21, 21, 22.8, 21.4, 18.7, 18.1, 14.3, 24.4, 22.8, 19.2, 17.8, 16.4, 17.3, 15.2, 10.4, 10.4, 14.7, 32.4, 30.4, 33.9, 21.5, 15.5, 15.2, 13.3, 19.2, 27.3, 26, 30.4, 15.8, 19.7, 15, 21.4, 
              2.62, 2.875, 2.32, 3.215, 3.44, 3.46, 3.57, 3.19, 3.15, 3.44, 3.44, 4.07, 3.73, 3.78, 5.25, 5.424, 5.345, 2.2, 1.615, 1.835, 2.465, 3.52, 3.435, 3.84, 3.845, 1.935, 2.14, 1.513, 3.17, 2.77, 3.57, 2.78, 
              110, 110, 93, 110, 175, 105, 245, 62, 95, 123, 123, 180, 180, 180, 205, 215, 230, 66, 52, 65, 97, 150, 150, 245, 175, 66, 91, 113, 264, 175, 335, 109), 
            nrow = 32, ncol = 3, byrow = FALSE)

# Add column names
colnames(matrix_A) <- c("column_1", "column_2", "column_3")

qr() fonksiyonunu kullanarak QR ayrışımı

Bu çarpanlara ayırmayı tek adımda qr() fonksiyonuyla yapabiliriz. Sonucu, QR ayrışımını içeren bir liste olan qr_decomp nesnesine atarız. 

# Perform and Display the QR decomposition
(qr_decomp <- qr(matrix_A))

QR ayrışımı nesnesinin rank bileşenine eriştiğimizde, ayrıştırılmış matrisimizdeki doğrusal olarak bağımsız sütun sayısını görebiliriz. Çıktı, matrisin rank’ının üç olduğunu, yani üç doğrusal olarak bağımsız sütun bulunduğunu gösterir; bu da beklediğimiz bir sonuçtur. Pivot bileşenine eriştiğimizde ise ayrıştırma sırasında kullanılan sütun permütasyonuna dair bilgileri görürüz. Çıktı, pivot indislerinin özgün sütun sıralamasıyla eşleştiğini, yani ayrıştırma sırasında sütunların permüte edilmediğini belirtir.

qr_decomp$rank
qr_decomp$pivot

[1] 3
[1] 1 2 3

Sonraki adım olarak, sırasıyla qr.Q() ve qr.R() fonksiyonlarını kullanarak Q ve R matrislerine erişebiliriz. Çıktıda Q matrisinin dikdörtgen, R matrisinin ise köşegen altı sıfırlar bulunan kare bir matris olduğunu görebiliriz. 

# Extract and Display the Q and R matrices
(Q_matrix <- qr.Q(qr_decomp))
(R_matrix <- qr.R(qr_decomp))

           [,1]         [,2]         [,3]
 [1,] -0.17721481  0.023462372 -0.015872336
 [2,] -0.17721481 -0.001889138 -0.060272525
 [3,] -0.19240465  0.077625112 -0.019039920
 [4,] -0.18059033 -0.030282834 -0.118470211
 [5,] -0.15780557 -0.089157964  0.064671266
 [6,] -0.15274229 -0.099258795 -0.187022354
 [7,] -0.12067485 -0.161573766  0.277715036
 [8,] -0.20590673  0.012764996 -0.275768785
 [9,] -0.19240465 -0.004891570 -0.156509401
[10,] -0.16202497 -0.082397566 -0.117343880
[11,] -0.15021065 -0.101326680 -0.120852866
[12,] -0.13839633 -0.182888939 -0.033166125
[13,] -0.14599125 -0.136918208  0.028289904
[14,] -0.12826977 -0.170282764  0.014320506
[15,] -0.08776353 -0.381326588 -0.165554550
[16,] -0.08776353 -0.398625266 -0.160607236
[17,] -0.12405037 -0.332631845 -0.083208412
[18,] -0.27341714  0.219354877 -0.069242665
[19,] -0.25653954  0.250472633 -0.021737724
[20,] -0.28607534  0.275923528 -0.005454217
[21,] -0.18143421  0.045632512 -0.033447865
[22,] -0.13080141 -0.140377926 -0.045388530
[23,] -0.12826977 -0.135983661 -0.031340393
[24,] -0.11223605 -0.201937338  0.228196652
[25,] -0.16202497 -0.122661730 -0.004593473
[26,] -0.23037925  0.176744505 -0.035884026
[27,] -0.21940881  0.138786843  0.013273146
[28,] -0.25653954  0.260613237  0.211010230
[29,] -0.13333305 -0.101525496  0.418085457
[30,] -0.16624437 -0.009027316  0.183837006
[31,] -0.12658201 -0.152109209  0.596664759
[32,] -0.18059033  0.012963861 -0.046253102

      column_1  column_2  column_3
[1,] -118.5003 -16.11602 -711.9200
[2,]    0.0000 -10.05857 -496.9319
[3,]    0.0000   0.00000  283.7369

Son adım olarak, merak ettiğimiz için, qr() fonksiyonunun ayrıştırma için hangi yöntemi kullandığını kontrol edebiliriz. 

?qr

Çıktının bir parçası olarak şunu görebiliriz:  

The function computes the QR decomposition of a matrix using the LINPACK or LAPACK routine dgeqrf.

FORTRAN dokümantasyonuna bakacak olursak, dgeqrf’in Householder dönüşümlerini kullanan bir LAPACK yordamı olduğunu görürüz. 

Gram–Schmidt süreciyle QR ayrışımı

qr() fonksiyonunda neler olduğunu, aynı uygulamayı birebir yeniden yazmasak da Gram–Schmidt sürecini izleyip düşünerek benzer bir fikri kendimiz kurarak anlamaya çalışalım. Bu alıştırmanın amacı birebir bir yöntemi kopyalamak değil, kavrayışımızı derinleştirmektir.

Q matrisinin oluşturulması

Gram–Schmidt sürecini kullanarak Q matrisimizi oluşturmaya başlamak için, alt küme verisinin ilk sütununu normalize ederek Q’nun ilk sütununu elde etmemiz gerekir. Buradaki amaç, matris A’daki vektör kümesini birim uzunluğu bir olan yeni bir vektör kümesine dönüştürmek ve bu vektörlerin birbirine ortogonal olmasını sağlamaktır.

Q’nun ilk sütununu bulmak için A’nın ilk sütununu çıkarır, Öklid normunu hesaplar ve ardından normalizasyon yaparız.

Hatırlamak gerekirse, Öklid normu bir vektörün Öklid uzayındaki uzunluğunun veya büyüklüğünün bir ölçüsüdür. Her vektör elemanını çok boyutlu uzayda birer koordinat olarak aldığımızda, vektörün başlangıç noktasından uç noktasına olan mesafeyi dikkate alırız. v = [v1​, v2​, …, vn​] vektörü için Öklid normu şu şekilde hesaplanır:

Bunu R’da uygulamak için her sütunu kareler, toplamını alır, sonra karekökünü alır ve son olarak normalize ederiz.

# Extract the first column of the subset data
col_1 <- matrix_A[, 1]

# Calculate the Euclidean norm of the first column
norm_col_1 <- sqrt(sum(col_1^2))

# Normalize and display the first column to get the first column of Q
(q1 <- col_1 / norm_col_1)

Doğrusal cebirden gözden geçirmemiz gereken ikinci kavram izdüşümdür (projection). İzdüşüm, bir vektörü bir alt uzaya yansıtan matematiksel bir işlemi ifade eder. Alt uzay, daha büyük vektör uzayı içinde daha düşük boyutlu bir uzay olarak düşünülebilir. Ortaya çıkan izdüşüm, alt uzay içinde yer alan ve yansıtılan özgün vektöre en yakın olan vektördür; bu vektör aynı zamanda alt uzaya diktir. 

Bunu, aşağıdaki grafikte olduğu gibi görselleştirmeye çalışalım; burada p izdüşümü, a’ya b’den en yakın olan ve b’ye dik olmak zorunda olan noktadır.

Bir izdüşümün görselleştirilmesi. Görsel: Yazar.

QR çarpanlarına ayırmanın bir sonraki adımında, önce A’nın ikinci sütununun Q’nun ilk sütununa izdüşümünü hesaplayıp bunu A’nın ikinci sütunundan çıkararak ikinci ortogonal vektörü hesaplarız. Ortaya çıkan vektör, ilk vektöre ortogonal olacaktır. Son adımda, bu vektörü normalize ederek Q’nun ikinci sütununu elde ederiz.

Bir izdüşümün denklemine göz atalım. İzdüşüm matrisi, a ile a-transpozun çarpımının, skaler değer olan a-transpoz ile a çarpımına bölünmesi ve bunun b ile çarpılmasıdır.

Ya da alternatif olarak:

Bu iki yöntemin nasıl aynı olduğunu merak edebiliriz. Şöyle ki, yukarıdaki ilk denklemde, b’nin solunda kalan kısım, özünde a vektörünün belirlediği yönü ve o yön için ölçekleme katsayısını yakalayan bir matris hesaplar. Bu, nokta çarpımı yönteminde a’nın birim vektörünü hesaplamaya benzer. 

Aşağıdaki R kodu, col_2 vektörünün q1 vektörü üzerine nokta çarpımı yöntemiyle izdüşümünü hesaplar.

# Extract the second column of the subset data
col_2 <- matrix_A[, 2]

# Calculate the projection of col_2 onto q1
projection_col_2_q1 <- sum(col_2 * q1) * q1

# Calculate the second orthogonal vector
v2 <- col_2 - projection_col_2_q1

# Calculate the Euclidean norm of the second orthogonal vector
norm_v2 <- sqrt(sum(v2^2))

# Normalize the second orthogonal vector to get the second column of Q
q2 <- v2 / norm_v2

Yukarıdaki kodda görüldüğü gibi, ikinci ortogonal vektörü ve Q matrisinin karşılık gelen sütununu oluşturmak; izdüşüm, çıkarma ve normalizasyon süreçlerinden oluşur. Temel adımlar, Q’nun ilk sütununu oluşturmaya benzer olsa da biraz farklı ve daha kapsamlıdır: Önce A’nın ikinci sütununu çıkarırız; sonra Q’nun ilk vektörü üzerine bir izdüşüm oluştururuz; ardından bu izdüşümü A’nın ikinci sütunundan çıkarırız; daha sonra normalizasyon yaparız; nihayetinde Q’nun ikinci sütununu elde ederiz.

Bu ikinci adımı q3 için de son sütuna kadar tekrar edebiliriz. Bizim durumumuzda, ortogonal vektörler q1, q2 ve q3, ortogonal Q matrisinin temelini oluşturur. Bu vektörler, özgün verileri yeni bir koordinat sisteminde ifade etmenin temelini sağladıkları için önemlidir.

Burada, Gram–Schmidt sürecinin her bir ardışık vektörün kendinden öncekilere ortogonal olmasını güvence altına alan yinelemeli bir süreç olduğunu görüyoruz. Ayrıca, ortogonalliğin iki vektörün nokta çarpımının sıfır olması anlamına geldiğini, bunun da vektör uzayında birbirlerine dik olduklarını gösterdiğini hatırlıyoruz. q1 ve q2’nin nokta çarpımını kullanarak ortogonalliğini doğrulayalım:

# Calculate the dot product of q1 and q2
dot_product_q1_q2 <- sum(q1 * q2)

# Print the dot product to confirm orthogonality
print(dot_product_q1_q2)

[1] 2.43295e-16

R matrisinin oluşturulması

Artık Q matrisine sahip olduğumuza göre, R matrisini oluşturmamız gerekir. QR ayrışımındaki R matrisi, ortogonal Q matrisinin sütunları ile özgün veri kümesi arasındaki ilişkilere dair bilgileri içerir. Üst üçgensel bir matristir ve R’nin üst üçgensel kısmındaki her bir eleman, Q’nun ilgili sütunları ile özgün verinin nokta çarpımı alınarak elde edilir.

Üst üçgensel R matrisini oluşturmak için, Q’nun her sütununun özgün veri kümesinin her sütunuyla nokta çarpımlarını hesaplamamız gerekir. Bu işlem, Q’daki sütun sayısı kadar satıra sahip bir matrisle sonuçlanacak ve önceki sürecimiz nedeniyle üst üçgensel olacaktır.

matrix_A <- matrix_A %>% as.matrix()

# Calculate and display the R matrix by multiplying Q^T and the subset data
R_matrix <- t(Q_matrix) %*% matrix_A

Bu kez R matrisimizin çıktısının biraz farklı göründüğünü görüyoruz. Bunun nedeni, qr() fonksiyonunun, bizim Gram–Schmidt esinli sürecimize kıyasla daha yüksek sayısal kararlılığa sahip Householder yansımalarını kullanmasıdır.

         column_1      column_2  column_3
[1,] -1.185003e+02 -1.611602e+01 -711.9200
[2,]  5.814446e-16 -1.005857e+01 -496.9319
[3,]  7.633287e-15  1.338669e-15  283.7369

Q ve R’yi çarparak matrix_A’yı geri elde ettiğimizi doğrulayabiliriz. Burada %*%, R’da matris çarpımı içindir.  

Q_matrix %*% R_matrix

   column_1 column_2 column_3
 [1,]     21.0    2.620      110
 [2,]     21.0    2.875      110
 [3,]     22.8    2.320       93
 [4,]     21.4    3.215      110
 [5,]     18.7    3.440      175
 [6,]     18.1    3.460      105
 [7,]     14.3    3.570      245
 [8,]     24.4    3.190       62
 [9,]     22.8    3.150       95
[10,]     19.2    3.440      123
[11,]     17.8    3.440      123
[12,]     16.4    4.070      180
[13,]     17.3    3.730      180
[14,]     15.2    3.780      180
[15,]     10.4    5.250      205
[16,]     10.4    5.424      215
[17,]     14.7    5.345      230
[18,]     32.4    2.200       66
[19,]     30.4    1.615       52
[20,]     33.9    1.835       65
[21,]     21.5    2.465       97
[22,]     15.5    3.520      150
[23,]     15.2    3.435      150
[24,]     13.3    3.840      245
[25,]     19.2    3.845      175
[26,]     27.3    1.935       66
[27,]     26.0    2.140       91
[28,]     30.4    1.513      113
[29,]     15.8    3.170      264
[30,]     19.7    2.770      175
[31,]     15.0    3.570      335
[32,]     21.4    2.780      109