SnowyField
Supervised LearningMachine LearningCalculusLinear Algebra

Toàn tập về bài toán Least Squares và các phương pháp giải

Giới thiệu chi tiết về phương pháp Least Squares và cách giải bài toán Least Squares bằng các phương pháp khác nhau.

Monday, October 16, 2023
6041 words-31 min read-––– views
Toàn tập về bài toán Least Squares và các phương pháp giải

Hồi quy là một bài toán kinh điển trong Machine Learning mà Least Squares (Bình phương Tối tiểu) là một trong những phương pháp phổ biến. Bằng cách xây dựng một model tương quan giữa các biến đầu vào và biến mục tiêu từ dữ liệu huấn luyện, chúng ta có thể dự đoán giá trị mục tiêu cho các dữ liệu mới.

Trong bài viết này, chúng ta sẽ tìm hiểu về Least Squares và các phương pháp giải cụ thể và chi tiết cho bài toán này.

Khuyến nghị đọc trước QR Decomposition là gì và chi tiết cách tính và Singular Value Decomposition là gì và chi tiết cách tính để sẵn sàng trước khi đi vào bài viết này.

Bài toán Least Squares

Nhắc lại

Model

Model (Mô hình) mà chúng ta hay nghe qua thực chất là một hàm số f(x,θ)f(x, \theta) với xx là một tập hợp các input (đầu vào) và θ\theta là một tập hợp các parameter (tham số).

Với mỗi giá trị xx, model sẽ cho ra một giá trị yy là output (đầu ra) tương ứng. yy thể là một câu trả lời cho một câu hỏi nào đó, một bức ảnh được tạo ra hay một dự đoán về một sự kiện trong tương lai.

Ma trận

Ma trận là một tập hợp các số được sắp xếp thành các hàng và cột. Nó giúp biểu diễn các chiều không gian cao hơn.

Ý nghĩa hình học của ma trận là nó biểu diễn một phép biến đổi tuyến tính, hay nói cách khác nó giống như một hàm số biến đổi một không gian này sang một không gian khác mà phép biến đổi này có thể là tổ hợp của các phép rotate (quay), stretch (co giãn), trượt (shear),...

Ma trận A∈Rm×n\mathbf{A} \in \mathbb{R}^{m \times n} biểu diễn một phép biến đổi từ không gian Rn\mathbb{R}^n sang không gian Rm\mathbb{R}^m.

Least Squares

Least Squares (Bình phương Tối tiểu) là một phương pháp tối ưu hóa để lựa chọn một đường khớp nhất cho một tập hợp các điểm dữ liệu. Đường khớp nhất là đường có tổng bình phương sai số nhỏ nhất giữa các điểm dữ liệu và đường đó.

Nghiệm của bài toán Least Squares là tập hợp giá trị của các parameter ứng với hàm số đã chọn. Từ đó ta sẽ có được một model có thể dự đoán được giá trị output cho một input bất kì.

Công thức

Gọi sự chênh lệch giữa giá trị quan sát được yy và giá trị mà model dự đoán y^\hat{y} là ee.

e=y^−y=f(x,θ)−y\begin{align*} e &= \hat{y} - y \\ &= f(x, \theta) - y \tag{1} \end{align*}

Ta có thể tính được tổng bình phương sai số SS:

S=∑i=1n(yi^−yi)\begin{align*} S &= \sum_{i=1}^{n} (\hat{y_i} - y_i) \\ \end{align*}

Tuy nhiên ee có thể nhận giá trị âm, dẫn đến việc không thể so sánh được với các giá trị khác. Vì vậy chúng ta sẽ nâng cấp hàm SS như sau:

S=∑i=1n∣yi^−yi∣\begin{aligned} S &= \sum_{i=1}^{n} |\hat{y_i} - y_i| \end{aligned}

Lúc này SS đã phản ánh đúng chức năng của việc mô phỏng độ lệch giữa 2 tập giá trị, tuy nhiên hàm trị tuyệt đối ∣x∣|x| là một hàm không khả vi tại x=0x = 0, nên chúng ta không thể dùng nó để tính đạo hàm / gradient. Vì vậy chúng ta sẽ sử dụng hàm bình phương để thay thế cho hàm trị tuyệt đối:

L=12(y^−y)2(2)\begin{aligned} L = \frac{1}{2}(\hat{y} - y)^2 \tag{2} \end{aligned}

Lí do 12\frac{1}{2} được thêm vào là để đơn giản hóa việc tính đạo hàm / gradient của LL: ∇L=y^−y\nabla L = \hat{y} - y.

Sau khi tìm được nghiệm, chúng ta có thể quan sát được vị trí tương quan giữa các điểm dữ liệu và model.

Source: ProProcessEngineer (YouTube)

Source: ProProcessEngineer (YouTube)

Lời giải

Cho f(x,θ)f(x, \theta) là một model có mm tham số: θ={θ0,θ1,…,θm}\theta = \{\theta_0, \theta_1, \dots, \theta_m\}.

Để SS đạt giá trị nhỏ nhất, ta sẽ phải tìm các parameter θ\theta sao cho SS đạt cực trị, vì cực trị duy nhất của SS sẽ luôn rơi vào trường hợp cực tiểu do đây là tổng của các r2≥0r^2 \geq 0.

Lúc này, ta chỉ cần đặt gradient của SS về 00, hay đặt đạo hàm của SS về 00 theo từng parameter θ\theta, vì lúc này θ\theta có vai trò như là một biến/ẩn.

∇S(θ)=0⃗∂S∂θj=0vớij=0,1,…,m∂∂θj(12∑i=1nri2)=0∑i=1nri∂ri∂θj=0∑i=1n(f(xi,θ)−yi)∂(f(xi,θ)−yi)∂θj=0∑i=1n(f(xi,θ)−yi)∂f(xi,θ)∂θj=0\begin{align*} \nabla S(\theta) &= \vec{0} \\ \frac{\partial S}{\partial \theta_j} &= 0 \quad \text{với} \quad j = 0, 1, \dots, m \\ \frac{\partial}{\partial \theta_j} \left( \frac{1}{2} \sum_{i=1}^{n} r_i^2 \right) &= 0 \\ \sum_{i=1}^{n} r_i \frac{\partial r_i}{\partial \theta_j} &= 0 \\ \sum_{i=1}^{n} (f(x_i, \theta) - y_i) \frac{\partial (f(x_i, \theta) - y_i)}{\partial \theta_j} &= 0 \\ \sum_{i=1}^{n} (f(x_i, \theta) - y_i) \frac{\partial f(x_i, \theta)}{\partial \theta_j} &= 0 \tag{3} \\ \end{align*}

Phương trình trên áp dụng cho mọi bài toán Bình phương Tối tiểu.

Ví dụ

Cho tập dữ liệu (x,y)(x, y) có độ lớn n=10n = 10:

x12345678910y132578891012(4)\begin{array}{c|c|c|c|c|c|c|c|c|c|c} x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline y & 1 & 3 & 2 & 5 & 7 & 8 & 8 & 9 & 10 & 12 \\ \end{array} \tag{4}

Mô hình y=θ0+θ1xy = \theta_0 + \theta_1 x

Từ (3)(3), ta có hệ phương trình:

{∑(θ0+θ1xi−yi)∂f(xi,θ)∂θ0=0∑(θ0+θ1xi−yi)∂f(xi,θ)∂θ1=0  ⟹  {∑(θ0+θ1xi−yi)=0∑(θ0+θ1xi−yi)xi=0  ⟹  {∑θ0+θ1∑xi−∑yi=0∑θ0xi+θ1∑xi2−∑xiyi=0  ⟹  {nθ0+θ1∑xi−∑yi=0θ0∑xi+θ1∑xi2−∑xiyi=0\begin{align*} & \begin{cases} \sum (\theta_0 + \theta_1 x_i - y_i) \frac{\partial f(x_i, \theta)}{\partial \theta_0} &= 0 \\ \sum (\theta_0 + \theta_1 x_i - y_i) \frac{\partial f(x_i, \theta)}{\partial \theta_1} &= 0 \\ \end{cases} \\ \implies & \begin{cases} \sum (\theta_0 + \theta_1 x_i - y_i) &= 0 \\ \sum (\theta_0 + \theta_1 x_i - y_i) x_i &= 0 \\ \end{cases} \\ \implies & \begin{cases} \sum \theta_0 + \theta_1 \sum x_i - \sum y_i &= 0 \\ \sum \theta_0 x_i + \theta_1 \sum x_i^2 - \sum x_i y_i &= 0 \\ \end{cases} \\ \implies & \begin{cases} n \theta_0 + \theta_1 \sum x_i - \sum y_i &= 0 \\ \theta_0 \sum x_i + \theta_1 \sum x_i^2 - \sum x_i y_i &= 0 \tag{5} \\ \end{cases} \\ \end{align*}

Từ (4)(4), ta có:

txyx2xy∑t5565385454\begin{array}{c|c|c|c|c} t & x & y & x^2 & xy \\ \hline \sum{t} & 55 & 65 & 385 & 454 \\ \end{array}

Thay vào (5)(5), ta được:

{10θ0+55θ1−67=055θ0+385θ1−550=0  ⟹  {θ0≈0.07θ1≈1.17\begin{align*} & \begin{cases} 10 \theta_0 + 55 \theta_1 - 67 &= 0 \\ 55 \theta_0 + 385 \theta_1 - 550 &= 0 \\ \end{cases} \\ \implies & \begin{cases} \theta_0 &\approx 0.07 \\ \theta_1 &\approx 1.17 \\ \end{cases} \\ \end{align*}
Nghiệm của bài toán là $y = 0.07 + 1.17x$

Nghiệm của bài toán là $y = 0.07 + 1.17x$

Mô hình y=θ0+θ1ex+θ2x2y = \theta_0 + \theta_1 e^x + \theta_2 x^2

Từ (3)(3), ta có hệ phương trình:

{∑(θ0+θ1exi+θ2xi2−yi)∂f(xi,θ)∂θ0=0∑(θ0+θ1exi+θ2xi2−yi)∂f(xi,θ)∂θ1=0∑(θ0+θ1exi+θ2xi2−yi)∂f(xi,θ)∂θ2=0  ⟹  {∑(θ0+θ1exi+θ2xi2−yi)=0∑(θ0+θ1exi+θ2xi2−yi)exi=0∑(θ0+θ1exi+θ2xi2−yi)xi2=0  ⟹  {∑θ0+θ1∑exi+θ2∑xi2−∑yi=0∑θ0exi+θ1∑e2xi+θ2∑exixi2−∑exiyi=0∑θ0xi2+θ1∑exixi2+θ2∑xi4−∑xi2yi=0  ⟹  {nθ0+θ1∑exi+θ2∑xi2−∑yi=0θ0∑exi+θ1∑e2xi+θ2∑exixi2−∑exiyi=0θ0∑xi2+θ1∑exixi2+θ2∑xi4−∑xi2yi=0\begin{align*} & \begin{cases} \sum (\theta_0 + \theta_1 e^{x_i} + \theta_2 x_i^2 - y_i) \frac{\partial f(x_i, \theta)}{\partial \theta_0} &= 0 \\ \sum (\theta_0 + \theta_1 e^{x_i} + \theta_2 x_i^2 - y_i) \frac{\partial f(x_i, \theta)}{\partial \theta_1} &= 0 \\ \sum (\theta_0 + \theta_1 e^{x_i} + \theta_2 x_i^2 - y_i) \frac{\partial f(x_i, \theta)}{\partial \theta_2} &= 0 \\ \end{cases} \\ \implies & \begin{cases} \sum (\theta_0 + \theta_1 e^{x_i} + \theta_2 x_i^2 - y_i) &= 0 \\ \sum (\theta_0 + \theta_1 e^{x_i} + \theta_2 x_i^2 - y_i) e^{x_i} &= 0 \\ \sum (\theta_0 + \theta_1 e^{x_i} + \theta_2 x_i^2 - y_i) x_i^2 &= 0 \\ \end{cases} \\ \implies & \begin{cases} \sum \theta_0 + \theta_1 \sum e^{x_i} + \theta_2 \sum x_i^2 - \sum y_i &= 0 \\ \sum \theta_0 e^{x_i} + \theta_1 \sum e^{2x_i} + \theta_2 \sum e^{x_i} x_i^2 - \sum e^{x_i} y_i &= 0 \\ \sum \theta_0 x_i^2 + \theta_1 \sum e^{x_i} x_i^2 + \theta_2 \sum x_i^4 - \sum x_i^2 y_i &= 0 \\ \end{cases} \\ \implies & \begin{cases} n \theta_0 + \theta_1 \sum e^{x_i} + \theta_2 \sum x_i^2 - \sum y_i &= 0 \\ \theta_0 \sum e^{x_i} + \theta_1 \sum e^{2x_i} + \theta_2 \sum e^{x_i} x_i^2 - \sum e^{x_i} y_i &= 0 \\ \theta_0 \sum x_i^2 + \theta_1 \sum e^{x_i} x_i^2 + \theta_2 \sum x_i^4 - \sum x_i^2 y_i &= 0 \tag{6} \\ \end{cases} \\ \end{align*}

Từ (4)(4), ta có:

tyx2x2yexexye2xexx2x4∑t65385355234843,77385554,49561102107920186,5125333\begin{array}{c|c|c|c|c|c|c|c|c} t & y & x^2 & x^2 y & e^x & e^x y & e^{2x} & e^{x} x^2 & x^4 \\ \hline \sum{t} & 65 & 385 & 3552 &34843,77 & 385554,49 & 561102107 & 920186,51 & 25333 \end{array}

Thay vào (6)(6), ta được:

{10θ0+34843,77θ1+25333θ2−65=034843,77θ0+561102107θ1+920186,51θ2−385554,49=025333θ0+920186,51θ1+25333θ2−3552=0  ⟹  {θ0≈0.1140θ1≈0.0007θ2≈0.0016\begin{align*} & \begin{cases} 10 \theta_0 + 34843,77 \theta_1 + 25333 \theta_2 - 65 &= 0 \\ 34843,77 \theta_0 + 561102107 \theta_1 + 920186,51 \theta_2 - 385554,49 &= 0 \\ 25333 \theta_0 + 920186,51 \theta_1 + 25333 \theta_2 - 3552 &= 0 \\ \end{cases} \\ \implies & \begin{cases} \theta_0 &\approx 0.1140 \\ \theta_1 &\approx 0.0007 \\ \theta_2 &\approx 0.0016 \\ \end{cases} \\ \end{align*}

Mở rộng

Ta có thể đưa bài toán về dạng ma trận miễn là model có dạng đa thức như sau:

y=∑i=1naiϕi(x)y=a1ϕ1(x)+a2ϕ2(x)+⋯+anϕn(x)[y1y2⋮yn]=[ϕ1(x1)ϕ2(x1)…ϕn(x1)ϕ1(x2)ϕ2(x2)…ϕn(x2)⋮⋮⋱⋮ϕ1(xm)ϕ2(xm)…ϕn(xm)][a1a2⋮an]y=Ax\begin{align*} y &= \sum_{i=1}^{n} a_i \phi_i(x) \\ y &= a_1 \phi_1(x) + a_2 \phi_2(x) + \dots + a_n \phi_n(x) \\ \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} &= \begin{bmatrix} \phi_1(x_1) & \phi_2(x_1) & \dots & \phi_n(x_1) \\ \phi_1(x_2) & \phi_2(x_2) & \dots & \phi_n(x_2) \\ \vdots & \vdots & \ddots & \vdots \\ \phi_1(x_m) & \phi_2(x_m) & \dots & \phi_n(x_m) \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{bmatrix} \\ \mathbf{y} &= \mathbf{A} \mathbf{x} \tag{7} \\ \end{align*}

Trong đó, A∈Rm×n\mathbf{A} \in \mathbb{R}^{m \times n} là một ma trận chứa giá trị của các Basic Function (Hàm số Cơ bản) ϕ\phi tại các điểm xx đã cho. Và x∈Rn\mathbf{x} \in \mathbb{R}^n là một vector chứa các parameter aa, hay còn gọi là Coefficient Vector (Vector Hệ số).

📝 Nhắc lại

Basic Function (Hàm số Cơ bản) là một hàm số mà các hàm số khác có thể được biểu diễn dưới dạng tổng tuyến tính của nó. Có nghĩa là ma trận A\mathbf{A} có thể biểu diễn được.

Ví dụ: y=θ0sin(x)+θ1cos(x)y = \theta_0 sin(x) + \theta_1 cos(x) có thể biểu diễn được bằng ma trận A=[sin(xi)cos(xi)]\mathbf{A} = \begin{bmatrix} sin(x_i) & cos(x_i) \end{bmatrix} với các basic function là sin(x)sin(x) và cos(x)cos(x). Trong khi đó y=sin(θ0x)+cos(θ1x)y = sin(\theta_0 x) + cos(\theta_1 x) không thể biểu diễn được vì các parameter θ0\theta_0 và θ1\theta_1 nằm trong hàm số.

Cho trước b∈Rm\mathbf{b} \in \mathbb{R}^m là một vector chứa các giá trị yy quan sát được, lúc này nhiệm vụ của chúng ta là xấp xỉ nghiệm của y\mathbf{y} theo b\mathbf{b} với sai số nhỏ nhất:

y≈bAx≈b\begin{align*} \mathbf{y} &\approx \mathbf{b} \\ \mathbf{A} \mathbf{x} &\approx \mathbf{b} \tag{8} \\ \end{align*}

Lúc này bài toán trở thành tìm vector x∈Rn\mathbf{x} \in \mathbb{R}^n sao cho:

min⁡x∣∣y−b∣∣2=min⁡x∣∣Ax−b∣∣2\begin{align*} &\min_{x} ||\mathbf{y} - \mathbf{b}||_2 \\ = &\min_{x} ||\mathbf{A}\mathbf{x} - \mathbf{b}||_2 \tag{9} \end{align*}

Tập nghiệm của bài toán này là:

Ax=bATAx=ATbx=(ATA)−1ATbx=A†b\begin{align*} \mathbf{A} \mathbf{x} &= \mathbf{b} \\ \mathbf{A}^T \mathbf{A} \mathbf{x} &= \mathbf{A}^T \mathbf{b} \\ \mathbf{x} &= (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T \mathbf{b} \\ \mathbf{x} &= \mathbf{A}^\dagger \mathbf{b} \tag{10} \\ \end{align*}

📝 Nhắc lại

A\mathbf{A} là Non-singular Matrix (Ma trận Khả nghịch) khi và chỉ khi A\mathbf{A} là ma trận vuông và full rank (đủ hạng). Vì vậy, trong nhiều trường hợp, chúng ta có thể thay thế A−1\mathbf{A}^{-1} bằng A†\mathbf{A}^\dagger. Đây là một Pseudo Inverse Matrix (Ma trận Giả Nghịch) được tính bằng (ATA)−1AT(\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T, vì ATA\mathbf{A}^T\mathbf{A} luôn khả nghịch.

Ý nghĩa hình học của Inverse Matrix (Ma trận Nghịch đảo) là nếu A\mathbf{A} biến đổi một không gian nào đó thì A−1\mathbf{A}^{-1} sẽ biến đổi lại về không gian ban đầu. Trong khi đó Pseudo Inverse Matrix sẽ biến đổi về một không gian với các chiều gần giống không gian ban đầu nhất.

Trong trường hợp lí tưởng, khi mà ma trận A\mathbf{A} khả nghịch (full rank và vuông) thì đồng nghĩa với việc phương trình Ax=b\mathbf{A} \mathbf{x} = \mathbf{b} có nghiệm duy nhất. Đồng nghĩa với việc tồn tại một đường đi qua tất cả các điểm đã cho.

Tất nhiên, trong mọi trường hợp thì hầu hết thì phương trình trên sẽ vô nghiệm, hay ma trận A\mathbf{A} sẽ không khả nghịch. Do đó chúng ta nhờ đến Pseudo Inverse Matrix vì nó sẽ giúp ta xấp xỉ được nghiệm lí tưởng cho bài toán.

Ví dụ

Sử dụng tập dữ liệu ở (4)(4) để xấp xỉ đường thẳng y=θ0+θ1x+θ2x2y = \theta_0 + \theta_1 x + \theta_2 x^2.

A=[111124⋮⋮⋮110100]b=[13⋮12]  ⟹  ATA=[1055385553853025385302525333]  ⟹  (ATA)−1=[1.38−0.5260.0417−0.5250.241−0.02080.0417−0.02080.00189]  ⟹  (ATA)−1AT=[0,90,50,18−0,05−0,2−0,27−0,25−0,150,030,3−0,3−0,130,010,10,160,170,140,07−0,04−0,20,020,008−0,004−0,011−0,015−0,015−0,011−0,0040,0080,023]  ⟹  (ATA)−1ATb=[−0.431.42−0.02]\begin{align*} \mathbf{A} &= \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ \vdots & \vdots & \vdots \\ 1 & 10 & 100 \end{bmatrix} \quad \mathbf{b} = \begin{bmatrix} 1 \\ 3 \\ \vdots \\ 12 \end{bmatrix} \\ \implies \mathbf{A}^T \mathbf{A} &= \begin{bmatrix} 10 & 55 & 385 \\ 55 & 385 & 3025 \\ 385 & 3025 & 25333 \end{bmatrix} \\ \implies (\mathbf{A}^T \mathbf{A})^{-1} &= \begin{bmatrix} 1.38 & -0.526 & 0.0417 \\ -0.525 & 0.241 & -0.0208 \\ 0.0417 & -0.0208 & 0.00189 \end{bmatrix} \\ \implies (\mathbf{A}^T \mathbf{A})^{-1}\mathbf{A}^T &= \begin{bmatrix} 0,9 & 0,5 & 0,18 & -0,05 & -0,2 & -0,27 & -0,25 & -0,15 & 0,03 & 0,3 \\ -0,3 & -0,13 & 0,01 & 0,1 & 0,16 & 0,17 & 0,14 & 0,07 & -0,04 & -0,2 \\ 0,02 & 0,008 & -0,004 & -0,011 & -0,015 & -0,015 & -0,011 & -0,004 & 0,008 & 0,023 \end{bmatrix} \\ \implies (\mathbf{A}^T \mathbf{A})^{-1}\mathbf{A}^T\mathbf{b} &= \begin{bmatrix} -0.43 \\ 1.42 \\ -0.02 \end{bmatrix} \\ \end{align*}
Nghiệm của bài toán là $y = -0.43 + 1.42x - 0.02x^2$

Nghiệm của bài toán là $y = -0.43 + 1.42x - 0.02x^2$

QR Decomposition

QR Decomposition (Phân rã QR) là một phương pháp phân rã một ma trận bất kì thành tích của hai ma trận Q\mathbf{Q} và R\mathbf{R}, trong đó Q\mathbf{Q} là một Orthonormal Matrix (Ma trận Trực chuẩn) và R\mathbf{R} là một Upper Triangular Matrix (Ma trận Tam giác trên).

Giải bài toán Least Squares bằng QR Decomposition

Một khi thể phân rã A\mathbf{A} thành tích của hai ma trận Q\mathbf{Q} và R\mathbf{R}, thay vì dùng ma trận giả nghịch như (9)(9), ta có thể biến đổi thành:

Ax=bQRx=bRx=QTbx=R−1QTb\begin{align*} \mathbf{A} \mathbf{x} &= \mathbf{b} \\ \mathbf{Q} \mathbf{R} \mathbf{x} &= \mathbf{b} \\ \mathbf{R} \mathbf{x} &= \mathbf{Q}^T \mathbf{b} \\ \mathbf{x} &= \mathbf{R}^{-1} \mathbf{Q}^T \mathbf{b} \tag{18} \\ \end{align*}

Singular Value Decomposition

Singular Value Decomposition (Phân tích Suy biến) là một phương pháp phân rã một ma trận bất kì thành tích của ba ma trận U\mathbf{U}, Σ\mathbf{\Sigma} và VT\mathbf{V}^T, trong đó U\mathbf{U} và V\mathbf{V} là các Orthonormal Matrix (Ma trận Trực chuẩn) và Σ\mathbf{\Sigma} là một Diagonal Matrix (Ma trận Đường chéo).

Giải bài toán Least Squares bằng Singular Value Decomposition

Quay lại (7)(7), ta có thể phân rã A\mathbf{A} thành tích của ba ma trận U\mathbf{U}, Σ\mathbf{\Sigma} và VT\mathbf{V}^T, khi đó (7)(7) trở thành:

Ax=bUΣVTx=bΣVTx=UTbVTx=Σ−1UTbx=VΣ−1UTb\begin{align*} \mathbf{A} \mathbf{x} &= \mathbf{b} \\ \mathbf{U} \mathbf{\Sigma} \mathbf{V}^T \mathbf{x} &= \mathbf{b} \\ \mathbf{\Sigma} \mathbf{V}^T \mathbf{x} &= \mathbf{U}^T \mathbf{b} \\ \mathbf{V}^T \mathbf{x} &= \mathbf{\Sigma}^{-1} \mathbf{U}^T \mathbf{b} \\ \mathbf{x} &= \mathbf{V} \mathbf{\Sigma}^{-1} \mathbf{U}^T \mathbf{b} \tag{19} \\ \end{align*}

Triển khai code Python

Toàn bộ code có thể xem chi tiết tại: snowyfield1906/ai-general-research/least_squares /least_squares.py.