Chuyển đến nội dung chính

Phân rã QR trong Machine Learning: Hướng dẫn chi tiết

Tìm hiểu về phân rã QR, kỹ thuật phân rã ma trận biểu diễn ma trận A dưới dạng tích của ma trận trực giao Q và ma trận tam giác trên R.
· 12 phút đọc

Khám phá cùng AI

Phân rã QR là một kỹ thuật phân rã ma trận nền tảng, được sử dụng rộng rãi trong nhiều lĩnh vực của khoa học dữ liệu và machine learning. Khả năng tách các ma trận phức tạp thành những thành phần đơn giản hơn khiến nó trở thành phương pháp cần thiết để giải các bài toán đại số tuyến tính và cải thiện độ ổn định của thuật toán.

Dù bạn đang thực hiện hồi quy tuyến tính bình phương tối thiểu thông thường hay xây dựng hệ gợi ý trong Python hoặc PySpark, hiểu phân rã QR có thể nâng cao đáng kể khả năng làm việc với các bộ dữ liệu lớn và các mô hình toán học phức tạp. 

Phân rã QR là gì?

Khi bạn phân tích, hay phân rã, một ma trận, bạn biểu diễn ma trận đó dưới dạng tích của hai hay nhiều ma trận. Nói cách khác, phân rã ma trận cho phép bạn tách một ma trận thành các thành phần đơn giản hơn, sao cho khi nhân chúng lại với nhau bằng phép nhân ma trận sẽ tái tạo được ma trận ban đầu. Chúng ta quan tâm đến phân rã ma trận vì nó đơn giản hóa nhiều bài toán đại số tuyến tính, khiến chúng dễ giải hơn. 

Phân rã QR là một kỹ thuật phân rã ma trận cụ thể, dùng để phân rã một ma trận thành tích của ma trận trực giao Q và ma trận tam giác trên R. Phương trình thường thấy là A = QR. 

Minh họa phân rã QR

Minh họa phân rã QR. Nguồn: ResearchGate

Để hiểu phân rã QR, bạn cần lưu ý rằng trong đại số tuyến tính, phép nhân ma trận không tuân theo những quy tắc trực giác như phép nhân vô hướng. Cụ thể, phép nhân ma trận không giao hoán, nghĩa là nói chung AB ≠ BA, do đó khái niệm “đảo ngược” trở nên phức tạp hơn.

Ma trận Q và R là gì?

Hãy xem xét hai ma trận quan trọng, Q và R.

Ma trận trực giao Q

Ma trận trực giao Q được đặc trưng bởi tính chất chuyển vị của nó cũng là nghịch đảo của nó, được biểu diễn toán học là QTQ = QQT  =  I, trong đó I là ma trận đơn vị. Chuyển vị, trong ngữ cảnh này, nghĩa là lật ma trận qua đường chéo chính.

Ma trận trực giao còn được đặc trưng bởi việc các cột của nó tạo thành một cơ sở trực chuẩn. Điều này có hai ý: Thứ nhất, các cột trực giao, tức là tích vô hướng của bất kỳ cặp cột khác nhau nào trong ma trận bằng không. Thứ hai, mỗi cột có độ lớn, hay độ dài đơn vị, bằng một.

Ma trận trực giao rất hữu ích vì chúng bảo toàn độ dài của vector và tích vô hướng của chúng. Vì vậy, nếu bạn có một vector và nhân nó với một ma trận trực giao, độ dài của vector đó vẫn giữ nguyên. Tương tự, nếu bạn có hai vector và nhân cả hai với cùng một ma trận trực giao, tích vô hướng giữa chúng cũng không đổi. Cuối cùng, vì ma trận trực giao bảo toàn độ dài và tích vô hướng, chúng không làm biến dạng các thuộc tính hình học của các vector sau phép biến đổi. Tức là, nếu hai vector vuông góc trước biến đổi, chúng sẽ vẫn vuông góc sau khi áp dụng ma trận trực giao. 

Ma trận tam giác trên R

Ma trận tam giác trên R là loại ma trận mà tất cả phần tử dưới đường chéo chính đều bằng không. Dạng này đơn giản hóa các phương trình ma trận và đặc biệt hữu ích khi giải hệ phương trình tuyến tính bằng phép thế lùi hoặc phương pháp khác. Ta cũng có thể nói rằng, trong phân rã QR, R biểu diễn thành phần nắm bắt độ lớn và hướng của ma trận gốc.

Các cách thực hiện phân rã QR

Hãy điểm qua một số cách khác nhau để thực hiện phân rã QR.

Quy trình Gram–Schmidt 

Quy trình Gram–Schmidt là một thuật toán dùng để chuyển một tập các vector độc lập tuyến tính thành một tập trực chuẩn một cách có hệ thống. Quy trình này được dùng cụ thể để xây dựng ma trận Q trong phân rã QR và, sau khi có Q, ta có thể suy ra R. 

Phép quay Givens

Phép quay Givens là một phương pháp khác hỗ trợ phân rã QR. Với phép quay Givens, một loạt các phép quay trên mặt phẳng được áp dụng để đưa các giá trị dưới đường chéo của ma trận A về 0. Mỗi phép quay tác động lên một cặp tọa độ, bảo toàn độ dài vector đồng thời biến đổi ma trận thành dạng tam giác trên. Phương pháp này hiệu quả cho các ma trận thưa vì ở mỗi bước nó chỉ sửa đổi một phần nhỏ của ma trận.

Phản xạ Householder

Phản xạ Householder là kỹ thuật tổng quát hơn, dùng các ma trận phản xạ, gọi là ma trận Householder, để loại bỏ có hệ thống các phần tử dưới đường chéo của ma trận A. Mỗi ma trận Householder phản xạ một vector qua một mặt phẳng trực giao với vector được chọn để đưa một cột dưới đường chéo về 0. Kết quả là một ma trận trực giao Q và một ma trận tam giác trên R. Phản xạ Householder đặc biệt phù hợp với ma trận đặc vì tính ổn định số.

Triển khai phân rã QR trong R

Trong phần này, chúng ta sẽ thực hành phân rã QR trong R bằng cách sử dụng cả hàm dựng sẵn qr() để triển khai nhanh và sau đó đi qua quy trình từ đầu bằng Gram–Schmidt để xây dựng trực giác. Hãy bắt đầu bằng cách tạo matrix_A, sẽ dùng cho cả hai phần.  

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")

Phân rã QR bằng hàm qr()

Chúng ta có thể thực hiện phân rã này trong một bước với hàm qr(). Ta gán kết quả cho đối tượng qr_decomp, là một list chứa phân rã QR. 

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

Khi truy cập thành phần hạng (rank) của đối tượng phân rã QR, ta có thể thấy số cột độc lập tuyến tính trong ma trận đã phân rã. Kết quả cho thấy ma trận có hạng bằng ba, tức có ba cột độc lập tuyến tính, đúng như mong đợi. Khi truy cập thành phần pivot, ta có thể thấy thông tin về phép hoán vị cột được sử dụng trong quá trình phân rã. Kết quả cho thấy các cột của ma trận không bị hoán vị trong quá trình phân rã, vì chỉ số pivot khớp với thứ tự cột ban đầu.

qr_decomp$rank
qr_decomp$pivot
[1] 3
[1] 1 2 3

Bước tiếp theo, ta có thể truy cập ma trận Q và ma trận R lần lượt bằng các hàm qr.Q() và qr.R(). Có thể thấy trong kết quả rằng ma trận Q là hình chữ nhật và ma trận R là hình vuông với các số 0 bên dưới đường chéo. 

# 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

Cuối cùng, vì tò mò, ta có thể kiểm tra xem hàm qr() sử dụng phương pháp nào để phân rã. 

?qr

Ta có thể thấy nội dung sau trong một phần của kết quả:  

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

Nếu kiểm tra tài liệu FORTRAN, ta sẽ thấy dgeqrf là một thủ tục LAPACK sử dụng các phép biến đổi Householder. 

Phân rã QR bằng quy trình Gram–Schmidt

Hãy cố gắng hiểu điều gì xảy ra với hàm qr() bằng cách tự dựng lại không phải đúng triển khai đó mà là một ý tưởng tương tự, theo quy trình Gram–Schmidt và suy luận. Mục đích của bài tập này không phải để tái tạo một phương pháp chính xác mà là để xây dựng hiểu biết của chúng ta.

Xây dựng ma trận Q

Để bắt đầu tạo ma trận Q bằng quy trình Gram–Schmidt, chúng ta cần chuẩn hóa cột đầu tiên của dữ liệu con để thu được cột đầu tiên của Q. Mục tiêu ở đây là biến tập các vector trong ma trận A thành một tập vector mới có độ dài đơn vị bằng một, và đảm bảo các vector này trực giao với nhau.

Để tìm cột đầu tiên của Q, ta trích xuất cột đầu tiên của A, tính chuẩn Euclid, rồi thực hiện chuẩn hóa.

Ôn lại, chuẩn Euclid là thước đo độ dài hay độ lớn của một vector trong không gian Euclid. Ta xét khoảng cách từ gốc tọa độ đến điểm cuối của vector khi coi mỗi phần tử của vector là một tọa độ trong không gian nhiều chiều. Với một vector v = [v1​, v2​, …, vn​], chuẩn Euclid được tính như sau:

Công thức chuẩn Euclid

Vậy, để triển khai trong R, ta bình phương từng cột, lấy tổng, rồi căn bậc hai và cuối cùng là chuẩn hóa.

# 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)

Điều thứ hai cần ôn từ đại số tuyến tính là khái niệm phép chiếu (projection). Phép chiếu là một phép toán chiếu một vector lên một không gian con. Không gian con có thể xem như một không gian chiều thấp hơn trong không gian vector lớn hơn. Kết quả phép chiếu là một vector nằm trong không gian con và gần với vector gốc nhất, đồng thời cũng trực giao với không gian con. 

Hãy hình dung bằng đồ thị sau, trong đó phép chiếu p là điểm gần a nhất từ b, và phải vuông góc với b.

Minh họa phép chiếu trong đại số tuyến tính

Minh họa phép chiếu. Hình do Tác giả tạo.

Ở bước tiếp theo của phân rã QR, ta tính vector trực giao thứ hai bằng cách trước hết tính phép chiếu của cột thứ hai của A lên cột thứ nhất của Q, rồi trừ kết quả đó khỏi cột thứ hai của A. Vector thu được sẽ trực giao với vector thứ nhất. Bước cuối cùng, ta chuẩn hóa vector này để thu được cột thứ hai của Q.

Hãy xem lại công thức của phép chiếu. Ma trận phép chiếu là a nhân a-chuyển vị chia cho đại lượng vô hướng là a-chuyển vị nhân a, rồi nhân với b.

phương trình ma trận phép chiếu

Hoặc, cách khác:

phương trình ma trận phép chiếu

Ta có thể thắc mắc: Hai cách này giống nhau thế nào? Khi nhìn vào phương trình đầu tiên ở trên, phần bên trái b tính một ma trận về cơ bản nắm bắt hướng do vector a xác định và hệ số tỷ lệ cho hướng đó. Điều này tương tự việc tính vector đơn vị của a trong phương pháp tích vô hướng. 

Đoạn mã R sau tính phép chiếu của vector col_2 lên vector q1 bằng phương pháp tích vô hướng.

# 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

Như thấy trong mã trên, việc xây dựng vector trực giao thứ hai và cột tương ứng của ma trận Q bao gồm các bước chiếu, trừ và chuẩn hóa. Các bước cơ bản tương tự như tạo cột đầu tiên của Q, nhưng có khác biệt và phức tạp hơn đôi chút: Trước tiên ta trích xuất cột thứ hai của A; sau đó tạo phép chiếu lên vector đầu tiên của Q; tiếp theo trừ phép chiếu khỏi cột thứ hai của A; rồi thực hiện chuẩn hóa; cuối cùng tạo cột thứ hai của Q.

Ta có thể lặp lại bước thứ hai này cho q3 cho đến cột cuối cùng. Trong trường hợp của chúng ta, các vector trực giao q1, q2 và q3 tạo thành cơ sở của ma trận trực giao Q. Các vector này rất quan trọng vì chúng cung cấp nền tảng để biểu diễn dữ liệu gốc trong một hệ tọa độ mới.

Ở đây, ta thấy quy trình Gram–Schmidt là một quy trình lặp, đảm bảo mỗi vector kế tiếp trực giao với các vector trước đó. Ta cũng nhớ rằng trực giao nghĩa là tích vô hướng của hai vector bằng không, cho thấy chúng vuông góc với nhau trong không gian vector. Hãy kiểm chứng tính trực giao của q1 và q2 bằng tích vô hướng của chúng:

# 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

Xây dựng ma trận R

Giờ ta đã có ma trận Q, cần xây dựng ma trận R. Ma trận R trong phân rã QR chứa thông tin về mối quan hệ giữa các cột của ma trận trực giao Q và bộ dữ liệu gốc. Đây là ma trận tam giác trên, và mỗi phần tử của phần tam giác trên của R được thu bằng cách tính tích vô hướng giữa các cột tương ứng của Q và dữ liệu gốc.

Để xây dựng ma trận tam giác trên R, chúng ta cần tính tích vô hướng của từng cột trong Q với từng cột của bộ dữ liệu gốc. Việc này sẽ tạo ra một ma trận có số hàng bằng số cột của Q, và sẽ là tam giác trên nhờ quy trình trước đó.

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

Ta thấy đầu ra của ma trận R lần này trông hơi khác. Lý do là vì hàm qr() sử dụng phản xạ Householder với độ ổn định số cao hơn so với quy trình phỏng theo Gram–Schmidt mà ta tự xây dựng.

         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

Ta có thể kiểm chứng việc tái tạo bằng cách nhân Q và R và thấy rằng ta nhận lại matrix_A. Ở đây, %*% là phép nhân ma trận trong R.  

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

Phân rã QR trong hồi quy tuyến tính

Phân rã QR được hàm lm() sử dụng mỗi lần nó được gọi trong R. Lý do là vì phân rã QR là một phương pháp ổn định số và hiệu quả để giải hệ tuyến tính, đặc biệt khi làm việc với bộ dữ liệu lớn hoặc khi các biến dự báo, tức các cột của ma trận thiết kế, gần đồng tuyến tính. 

Ta có thể thấy lm() sử dụng phân rã QR bằng cách đơn giản gõ lm vào bảng điều khiển và xem chữ ký hàm, nơi có method = "qr" và qr = TRUE.

lm
lm <- function (formula, data, subset, weights, na.action,
		method = "qr", model = TRUE, x = FALSE, y = FALSE,
		qr = TRUE, singular.ok = TRUE, contrasts = NULL,
		offset, ...)

Có những phương pháp thay thế để tìm các hệ số của hồi quy tuyến tính. Ví dụ, ta có thể tìm hệ số hồi quy tuyến tính bằng cách giải cái gọi là phương trình chuẩn. Ta thậm chí có thể cân nhắc dùng giải tích bằng cách giải đạo hàm riêng của tổng bình phương sai số theo các hệ số và đặt chúng bằng không. Hoặc, trong hồi quy tuyến tính đơn, tức hồi quy chỉ với một biến độc lập và một biến phụ thuộc, ta có thể tìm hệ số góc của đường hồi quy bằng cách nhân hệ số tương quan r với tỷ số giữa độ lệch chuẩn của y và độ lệch chuẩn của x. 

Trong số các phương pháp này, phân rã QR có thể là tốt nhất vì cân bằng được giữa ổn định và hiệu quả. Đặc biệt, phương trình chuẩn, tức ATA x = ATB, có chi phí tính toán rất lớn. Lý do là vì, để giải x, ta viết phương trình dưới dạng x = ((ATA)-1 ) ATB. Phần của phương trình buộc ta phải tìm nghịch đảo của ATA có độ phức tạp thời gian O(n3), nghĩa là khi kích thước ma trận tăng gấp đôi, thời gian cần để nghịch đảo tăng gấp tám lần. Điều này khiến nó là lựa chọn kém cho các bài toán nhiều chiều.

Kết luận

Phân rã QR không chỉ là một khái niệm thuộc đại số tuyến tính. Đây là một phương pháp có phạm vi ứng dụng rộng trong khoa học dữ liệu và machine learning. Bằng cách hiểu và áp dụng phân rã QR, bạn có thể tăng khả năng xử lý các vấn đề phức tạp, chẳng hạn khi làm việc với các bộ dữ liệu lớn và các ước lượng hồi quy tuyến tính. 

Ngoài ra, nếu bạn thấy chủ đề phân rã thú vị, cần nói thêm rằng phân rã thực ra là một ý tưởng tổng quát hơn trong khoa học dữ liệu. Ví dụ, phân rã chuỗi thời gian nghĩa là tách một chuỗi thời gian thành thành phần xu hướng–chu kỳ, mùa vụ và phần dư. Khi cộng hoặc nhân, các thành phần này phục hồi chuỗi thời gian ban đầu. Một ví dụ khác là Biến đổi Fourier, phân rã một ảnh thành các thành phần tần số, hữu ích trong xử lý tín hiệu. 

Khi tiếp tục khám phá các chủ đề nâng cao trong khoa học dữ liệu, bạn sẽ thấy những khái niệm như phân rã QR gắn kết chặt chẽ với các lĩnh vực nền tảng khác. Hãy tham gia các khóa học của chúng tôi: Đại số tuyến tính cho Khoa học Dữ liệu bằng R và Nhập môn Thống kê. Nắm vững các chủ đề liên thông này sẽ giúp bạn giải quyết những vấn đề khoa học dữ liệu thách thức và đa dạng hơn.

Josef Waples

Tác giả

Josef Waples

Tôi là một cây bút và biên tập viên về khoa học dữ liệu, đã có bài đóng góp cho các nghiên cứu đăng trên tạp chí khoa học. Tôi đặc biệt quan tâm đến đại số tuyến tính, thống kê, R và các chủ đề tương tự. Tôi cũng chơi cờ vua khá thường xuyên! 

Chủ đề

Khoa học Dữ liệuR

Liên quan

Xem thêm →