tek4

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

by - September. 21, 2021
Kiến thức
<p><img class="aligncenter wp-image-6922 size-full" src="https://tek4.vn/wp-content/uploads/2020/12/a-36.jpg" alt="Anh-bia" width="1000" height="667" /></p> <p style="text-align: center;">Chụp bởi&nbsp;<a href="https://unsplash.com/@zhenhu2424">Zhen Hu</a></p> <p>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.</p> <ul> <li>Giải [latexpage]$Ax=b$. Tương đương với&nbsp;[latexpage]$maximize_{x}\;\;f(x)=\frac{1}{2}x^{T}Ax-b^{T}x$</li> <li>V&igrave; [latexpage]$f'(x)=Ax-b=0$</li> </ul> <p>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.</p> <p>[latexpage]\[x^{T}Ax&gt;0\]</p> <p>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.</p> <p><img class="aligncenter wp-image-6923 size-full" src="https://tek4.vn/wp-content/uploads/2020/12/Capture-79.png" alt="Phuong-phap-Conjugate-Gradient" width="886" height="364" /></p> <p>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.</p> <p><img class="aligncenter wp-image-6926 size-full" src="https://tek4.vn/wp-content/uploads/2020/12/Capture-81.png" alt="Phuong-phap-Conjugate-Gradient" width="686" height="560" /></p> <p style="text-align: center;">Chỉnh sửa từ <a href="https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf">nguồn</a></p> <ol> <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 [latexpage]$dj$ m&agrave; li&ecirc;n kết A với c&aacute;c hướng đi trước đ&oacute; [latexpage]$di$.</li> </ol> <p>Về mặt to&aacute;n học, bất kỳ hướng đi mới [latexpage]$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; [latexpage]$di$</p> <p>[latexpage]\[d^{T}_{i}Ad_{(j)}=0\]</p> <p>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.</p> <p><img class="aligncenter wp-image-6924 size-medium" src="https://tek4.vn/wp-content/uploads/2020/12/a-35-300x152.png" alt="Vi-du" width="300" height="152" /></p> <p style="text-align: center;"><a href="https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf">Nguồn</a></p> <p>C&aacute;c v&eacute;c tơ 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.</p> <p>[latexpage]\[Ax_{*}=\sum_{i=1}^{n}\alpha_{i}Ad_{i}\]</p> <p>Phần quan trọng của phương ph&aacute;p CG l&agrave; t&igrave;m được [latexpage]$\alpha$ v&agrave; [latexpage]$d$.</p> <h1>Giải thuật Conjugate Gradient</h1> <p>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 [latexpage]$\alpha$ v&agrave; [latexpage]$d$.</p> <ul> <li>[latexpage]$r_{0}:=b-Ax_{0}$</li> <li>[latexpage]$d_{0}:=r_{0}$</li> <li>[latexpage]$k:=0$</li> <li>Thực hiện lặp lại: <ul> <li>[latexpage]$a_{k}:=\frac{r^{T}_{k}}{d_{k}^{T}Ad_{k}}$</li> <li>[latexpage]$x_{k+1}:=x_{k}+\alpha_{k}d_{k}$</li> <li>[latexpage]$r_{k+1}:=r_{k}-\alpha_{k}Ad_{k}$</li> <li>Nếu [latexpage]$r_{k+1}$ đủ nhỏ, tho&aacute;t v&ograve;ng lặp</li> <li>[latexpage]$\beta_{k}:=\frac{r_{k+1}^{T}r_{k+1}}{r_{k}^{T}r_{k}}$</li> <li>[latexpage]$d_{k+1}:=r_{k+1}+\beta_{k}d_{k}$</li> <li>[latexpage]$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; [latexpage]$x_{k+1}$</li> </ul> <p>Trong đ&oacute;:</p> <ul> <li>[latexpage]$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>[latexpage]$x_{k+1}:=x_{k}+\alpha_{k}d_{k}$ l&agrave; điểm tiếp theo</li> <li>[latexpage]$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>[latexpage]$d_{k+1}$ l&agrave; hướng đi tiếp theo</li> <li>[latexpage]$\beta_{k}d_{k}$ l&agrave; hướng đi mới v&agrave; sẽ trực giao A</li> <li>[latexpage]$d$ l&agrave; hướng đi tiếp theo</li> </ul> <p>Đầu ti&ecirc;n, ta sẽ định nghĩa 2 hệ số sau:</p> <ul> <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> </ul> <p><img class="aligncenter wp-image-6925 size-full" src="https://tek4.vn/wp-content/uploads/2020/12/Capture-80.png" alt="Vi-du" width="386" height="348" /></p> <ul> <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> <p>[latexpage]\[e_{(i)}=x_{(i)}-x\]</p> <p>[latexpage]\[r_{(i)}=b-Ax_{(i)}\]</p> <p>Từ:</p> <p>[latexpage]\[f(x)=\frac{1}{2}x^{T}Ax-b^{T}x\]</p> <p>[latexpage]\[f'(x)=Ax-b\]</p> <p>Ch&uacute;ng ta c&oacute; thể t&iacute;nh được:</p> <p>[latexpage]\[-f'(x_{(i)})=b-Ax_{(i)}\]</p> <p>[latexpage]\[r_{(i)}=-Ae_{(i)}\]</p> <p>[latexpage]\[r_{(i)}=-f'(x_{(i)})\]</p> <p>Với:</p> <p>[latexpage]\[e_{(i)}=x_{(i)}-x\]</p> <p>[latexpage]\[r_{(i)}=b-Ax_{(i)}\]</p> <p>Điểm tiếp theo sẽ được t&iacute;nh như sau ([latexpage]$\alpha$ l&agrave; hệ số v&ocirc; hướng v&agrave; [latexpage]$d$ l&agrave; hệ số c&oacute; hướng):</p> <p>[latexpage]\[x_{(i+1)}=x_{(i)}+\alpha_{(i)}d_{(i)}\]</p> <p>Để đả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;.</p> <p>[latexpage]\[d_{(i)}^{T}e_{(i+1)}=0\]</p> <p>[latexpage]\[d_{(i)}^{T}(e_{(i)}+\alpha_{(i)}d_{(i)})=0\]</p> <p>[latexpage]\[\alpha_{(i)}=-\frac{d_{(i)}^{T}e_{(i)}}{d_{(i)}^{T}d_{(i)}}\]</p> <p>[latexpage]$\alpha$ phụ thuộc v&agrave;o [latexpage]$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:</p> <p>[latexpage]\[d_{(i)}^{T}Ad_{(j)}=0\]</p> <p>Để đ&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.</p> <p><img class="aligncenter wp-image-6927 size-full" src="https://tek4.vn/wp-content/uploads/2020/12/Capture-82.png" alt="Vi-du" width="692" height="558" /></p> <p style="text-align: center;">Chỉnh sửa từ <a href="https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf">nguồn</a></p> <ul> <li>[latexpage]$\frac{d}{d\alpha}f(x_{(i+1)})=0$</li> <li>[latexpage]$f'(x_{(i+1)})^{T}\frac{d}{d\alpha}x_{(i+1)}=0$</li> <li>[latexpage]$-r^{T}_{(i+1)}d_{(i)}=0$</li> <li>[latexpage]$d_{(i)}^{T}Ae_{(i+1)}=0$</li> </ul> <p>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:</p> <ul> <li>[latexpage]$\alpha_{(i)}=-\frac{d_{(i)}^{T}Ae_{(i)}}{d_{(i)}^{T}Ad_{(i)}}$</li> <li>[latexpage]$= \frac{d_{(i)}^{T}r_{(i)}}{d_{(i)}^{T}Ad_{(i)}}$</li> </ul> <p>Với [latexpage]$r_{(i)}=-Ae_{(i)}$</p> <p>Đế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> <p>P/s: Cảm ơn mọi người!</p> <hr /> <p style="text-align: center;"><em><strong>Fanpage Facebook:</strong>&nbsp;<a href="https://www.facebook.com/tek4.vn/">TEK4.VN</a></em>&nbsp;</p> <p style="text-align: center;"><em><strong>Tham gia cộng đồng để chia sẻ, trao đổi v&agrave; thảo luận:</strong>&nbsp;<a href="https://www.facebook.com/groups/tek4.vn/">TEK4.VN - Học Lập Tr&igrave;nh Miễn Ph&iacute;</a></em></p>