&nbsp;
Phương ph&aacute;p Conjugate Gradient, viết tắt l&agrave; CG, được sử dụng để giải một phương tr&igrave;nh tuyến t&iacute;nh hoặc để tối ưu h&oacute;a một phương tr&igrave;nh bậc hai. V&agrave; n&oacute; hiệu quả hơn so với Gradient Descent.
<ul style="text-align: justify;">
<li>Giải $Ax=b$. Tương đương với&nbsp;$maximize_{x}\;\;f(x)=\frac{1}{2}x^{T}Ax-b^{T}x$</li>
<li>V&igrave; $f'(x)=Ax-b=0$</li>
</ul>
Trong đ&oacute; A c&oacute; t&iacute;nh đối xứng v&agrave; c&oacute; gi&aacute; trị tuyệt đối lu&ocirc;n dương.
\[x^{T}Ax&gt;0\]
Trong phương ph&aacute;p t&igrave;m kiếm theo đường thẳng (Line Search), ch&uacute;ng ta sẽ x&aacute;c định hướng đi l&ecirc;n c&oacute; độ dốc nhất v&agrave; sau đ&oacute; chọn k&iacute;ch thước của bước đi. V&iacute; dụ, trong phương ph&aacute;p Gradient Ascent, ch&uacute;ng ta t&iacute;nh k&iacute;ch thước bước đi bằng với Gradient nh&acirc;n Learning rate. Đối với h&igrave;nh b&ecirc;n tr&aacute;i b&ecirc;n dưới, điểm m&agrave;u vang sẽ di chuyển sang phải. V&agrave; h&agrave;nh động tiếp theo l&agrave; đi l&ecirc;n v&agrave; hơi quay sang tr&aacute;i tương ứng với độ dốc c&oacute; hướng đi l&ecirc;n cao nhất. Tuy nhi&ecirc;n, điều đ&oacute; sẽ l&agrave;m sai lệch qu&aacute; tr&igrave;nh đi đ&uacute;ng ngay hướng trong bước đầu ti&ecirc;n.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/883104f9-c774-49d0-b5eb-af45f65d232a" alt="" width="600" height="246" />
Phương ph&aacute;p Conjugate Gradient (Tạm dịch: Gradient li&ecirc;n hợp) l&agrave; một phương ph&aacute;p t&igrave;m kiếm theo đường thẳng nhưng đối với mỗi bước di chuyển, n&oacute; sẽ kh&ocirc;ng l&agrave;m sai lệch một phần đ&atilde; được thực hiện của c&aacute;c bước di chuyển trước đ&oacute;. N&oacute; tối ưu h&oacute;a một phương tr&igrave;nh bậc hai với số lượng c&aacute;c bước &iacute;t hơn so với Gradient Ascent. Nếu x l&agrave; N chiều (N tham số), ch&uacute;ng ta c&oacute; thể t&igrave;m thấy điểm tối ưu tối đa l&agrave; N bước. Đối với mỗi bước đi, ch&uacute;ng ta sẽ c&oacute; hướng đi m&agrave; kết hợp với tất cả c&aacute;c bước đi trước đ&oacute;. Điều n&agrave;y đảm bảo rằng ch&uacute;ng t&ocirc;i sẽ kh&ocirc;ng l&agrave;m sai lệch một phần của c&aacute;c bước đi m&agrave; ch&uacute;ng t&ocirc;i đ&atilde; thực hiện. T&oacute;m lại, nếu x l&agrave; 4 chiều th&igrave; cần nhiều nhất l&agrave; 4 lần di chuyển để đạt được điểm tối ưu.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/a9ebacd2-529a-401b-9746-2cfd77723506" alt="" width="600" height="490" />
<ol style="text-align: justify;">
<li>Bắt đầu từ một hướng đi l&ecirc;n nhất định</li>
<li>Đạt tới điểm tối ưu với hướng đi đ&atilde; chọn.</li>
<li>T&igrave;m ra hướng đi mới $dj$ m&agrave; li&ecirc;n kết A với c&aacute;c hướng đi trước đ&oacute; $di$.</li>
</ol>
Về mặt to&aacute;n học, bất kỳ hướng đi mới $dj$ n&agrave;o sẽ đều phải li&ecirc;n kết A với c&aacute;c hướng đi trước đ&oacute; l&agrave; $di$
\[d^{T}_{i}Ad_{(j)}=0\]
Trong đ&oacute; A l&agrave; ma trận ở dạng phương tr&igrave;nh bậc hai. Dưới đ&acirc;y l&agrave; một số v&iacute; dụ về v&eacute;c tơ li&ecirc;n hợp A trong kh&ocirc;ng gian 2 chiều.
&nbsp;
C&aacute;c v&eacute;c t<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/b23f8d4c-0253-44b8-8c99-9b0dc3fbbb41" alt="" width="600" height="304" />ơ li&ecirc;n hợp A đều độc lập với nhau, v&igrave; vậy, N v&eacute;c tơ li&ecirc;n hợp A c&oacute; triển khai sang một kh&ocirc;ng gian N chiều.
\[Ax_{*}=\sum_{i=1}^{n}\alpha_{i}Ad_{i}\]
Phần quan trọng của phương ph&aacute;p CG l&agrave; t&igrave;m được $\alpha$ v&agrave; $d$.
<h1 style="text-align: justify;">Giải thuật Conjugate Gradient</h1>
Trước ti&ecirc;n h&atilde;y c&ugrave;ng xem qua giải thuật Conjugate Gradient. Ch&uacute;ng t&ocirc;i bắt đầu với một phỏng đo&aacute;n ngẫu nhi&ecirc;n cho nghiệm X (Xo) v&agrave; đưa ra phỏng đo&aacute;n tiếp theo X1 với $\alpha$ v&agrave; $d$.
<ul style="text-align: justify;">
<li>$r_{0}:=b-Ax_{0}$</li>
<li>$d_{0}:=r_{0}$</li>
<li>$k:=0$</li>
<li>Thực hiện lặp lại:
<ul>
<li>$a_{k}:=\frac{r^{T}_{k}}{d_{k}^{T}Ad_{k}}$</li>
<li>$x_{k+1}:=x_{k}+\alpha_{k}d_{k}$</li>
<li>$r_{k+1}:=r_{k}-\alpha_{k}Ad_{k}$</li>
<li>Nếu $r_{k+1}$ đủ nhỏ, tho&aacute;t v&ograve;ng lặp</li>
<li>$\beta_{k}:=\frac{r_{k+1}^{T}r_{k+1}}{r_{k}^{T}r_{k}}$</li>
<li>$d_{k+1}:=r_{k+1}+\beta_{k}d_{k}$</li>
<li>$k:=k+1$</li>
</ul>
</li>
<li>Kết th&uacute;c qu&aacute; tr&igrave;nh lặp</li>
<li>Kết quả trả về sẽ l&agrave; $x_{k+1}$</li>
</ul>
Trong đ&oacute;:
<ul style="text-align: justify;">
<li>$a_{k}:=\frac{r^{T}_{k}}{d_{k}^{T}Ad_{k}}$ l&agrave; khoảng c&aacute;ch m&agrave; ch&uacute;ng ta sẽ di chuyển theo hướng p.</li>
<li>$x_{k+1}:=x_{k}+\alpha_{k}d_{k}$ l&agrave; điểm tiếp theo</li>
<li>$r_{k+1}:=r_{k}-\alpha_{k}Ad_{k}$ l&agrave; gi&aacute; trị sai số c&ograve;n c&aacute;ch điểm tối ưu</li>
<li>$d_{k+1}$ l&agrave; hướng đi tiếp theo</li>
<li>$\beta_{k}d_{k}$ l&agrave; hướng đi mới v&agrave; sẽ trực giao A</li>
<li>$d$ l&agrave; hướng đi tiếp theo</li>
</ul>
Đầu ti&ecirc;n, ta sẽ định nghĩa 2 hệ số sau:
<ul style="text-align: justify;">
<li>E l&agrave; gi&aacute; trị sai số giữa phỏng đo&aacute;n ban đầu v&agrave; điểm tối ưu</li>
<li><img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/5a72346d-f9b0-4029-adc8-e75ca0b0c3f2" alt="" width="600" height="541" /></li>
<li>R đo lường khoảng c&aacute;ch từ gi&aacute; trị ch&iacute;nh x&aacute;c CT b (Ax=b). Ch&uacute;ng ta c&oacute; thể coi r giống như gi&aacute; trị sai số e được khai triển bởi A sang một kh&ocirc;ng gian b (khoảng c&aacute;ch Ax từ b)</li>
</ul>
\[e_{(i)}=x_{(i)}-x\]
\[r_{(i)}=b-Ax_{(i)}\]
Từ:
\[f(x)=\frac{1}{2}x^{T}Ax-b^{T}x\]
\[f'(x)=Ax-b\]
Ch&uacute;ng ta c&oacute; thể t&iacute;nh được:
\[-f'(x_{(i)})=b-Ax_{(i)}\]
\[r_{(i)}=-Ae_{(i)}\]
\[r_{(i)}=-f'(x_{(i)})\]
Với:
\[e_{(i)}=x_{(i)}-x\]
\[r_{(i)}=b-Ax_{(i)}\]
Điểm tiếp theo sẽ được t&iacute;nh như sau ($\alpha$ l&agrave; hệ số v&ocirc; hướng v&agrave; $d$ l&agrave; hệ số c&oacute; hướng):
\[x_{(i+1)}=x_{(i)}+\alpha_{(i)}d_{(i)}\]
Để đảm bảo hướng đi tiếp theo trong tương lai sẽ kh&ocirc;ng l&agrave;m sai lệch hướng đi đ&uacute;ng trước đ&oacute;. Giả sử d v&agrave; e trực giao với nhau. tức l&agrave; sai số c&ograve;n lại sau khi thực hiện bước đi n&agrave;y phải trực giao với hướng đi hiện tại. Điều n&agrave;y sẽ c&oacute; nghĩa nếu c&aacute;c bước di chuyển c&ograve;n lại kh&ocirc;ng l&agrave;m sai lệch một phần tiến tr&igrave;nh m&agrave; ch&uacute;ng ta đ&atilde; thực hiện trước đ&oacute;.
\[d_{(i)}^{T}e_{(i+1)}=0\]
\[d_{(i)}^{T}(e_{(i)}+\alpha_{(i)}d_{(i)})=0\]
\[\alpha_{(i)}=-\frac{d_{(i)}^{T}e_{(i)}}{d_{(i)}^{T}d_{(i)}}\]
$\alpha$ phụ thuộc v&agrave;o $e$, hệ số m&agrave; ch&uacute;ng ta chưa biết gi&aacute; trị của n&oacute;. V&igrave; vậy, thay v&igrave; trực giao, ta sẽ thử một phỏng đo&aacute;n kh&aacute;c. Hướng t&igrave;m kiếm mới phải l&agrave; hướng trực giao A với hướng trước đ&oacute;. Định nghĩa của trực giao A như sau:
\[d_{(i)}^{T}Ad_{(j)}=0\]
Để đ&aacute;p ứng c&aacute;c điều kiện n&agrave;y, điểm tiếp theo xi phải l&agrave; điểm tối ưu trong hướng t&igrave;m kiếm d.
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/f73bb7b7-4a23-4128-aa0e-f8d1c7def5a1" alt="" width="600" height="484" />
<ul style="text-align: justify;">
<li>$\frac{d}{d\alpha}f(x_{(i+1)})=0$</li>
<li>$f'(x_{(i+1)})^{T}\frac{d}{d\alpha}x_{(i+1)}=0$</li>
<li>$-r^{T}_{(i+1)}d_{(i)}=0$</li>
<li>$d_{(i)}^{T}Ae_{(i+1)}=0$</li>
</ul>
Với y&ecirc;u cầu b&agrave;i to&aacute;n l&agrave; trực giao A, &alpha; sẽ được t&iacute;nh như sau:
<ul style="text-align: justify;">
<li>$\alpha_{(i)}=-\frac{d_{(i)}^{T}Ae_{(i)}}{d_{(i)}^{T}Ad_{(i)}}$</li>
<li>$= \frac{d_{(i)}^{T}r_{(i)}}{d_{(i)}^{T}Ad_{(i)}}$</li>
</ul>
Với $r_{(i)}=-Ae_{(i)}$
Đến đ&acirc;y l&agrave; kết th&uacute;c của b&agrave;i n&agrave;y. Hy vọng mọi người đ&atilde; nắm được cơ bản về phương ph&aacute;p Conjugate Gradient. Mọi người h&atilde;y theo d&otilde;i c&aacute;c b&agrave;i mới nhất tr&ecirc;n <a href="http://tek4.vn">tek4</a> nh&eacute;!
P/s: Cảm ơn mọi người!
<hr />
Fanpage Facebook:&nbsp;<a href="https://www.facebook.com/tek4.vn/">TEK4.VN</a>&nbsp;
Tham gia cộng đồng để chia sẻ, trao đổi v&agrave; thảo luận:&nbsp;<a href="https://www.facebook.com/groups/tek4.vn/">TEK4.VN - Học Lập Tr&igrave;nh Miễn Ph&iacute;</a>

Admin

Phương Pháp Conjugate Gradient – Học Tăng Cường

Cùng tác giả

Admin

Có liên quan