tek4

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

by - September. 21, 2021
Kiến thức
<p><img class="aligncenter wp-image-6920 size-full" src="https://tek4.vn/wp-content/uploads/2020/12/a-35.jpg" alt="Anh-bia" width="1000" height="650" /></p> <p style="text-align: center;">Chụp bởi <a href="https://unsplash.com/@ross_savchyn">Rostyslav Savchyn</a></p> <p>Phương ph&aacute;p Dual Gradient Descent được d&ugrave;ng phổ biến để tối ưu h&oacute;a h&agrave;m mục ti&ecirc;u c&ugrave;ng với một r&agrave;ng buộc, điều n&agrave;y gi&uacute;p ta đưa ra quyết định tốt hơn.</p> <p>[latexpage]\[min_{x}\;f(x)\;s.t. \;\;C(x)=0\]</p> <p>&Yacute; tưởng ch&iacute;nh l&agrave; chuyển đổi h&agrave;m mục ti&ecirc;u sang h&agrave;m đối ngẫu Lagrange, h&agrave;m n&agrave;y được tối ưu h&oacute;a một c&aacute;ch lặp lại. Lagrangian [latexpage]$\mathcal{L}$ v&agrave; h&agrave;m đối ngẫu Lagrange [latexpage]$g$ được định nghĩa như sau:</p> <p>[latexpage]\[\mathcal{L}(x,\lambda)=f(x)+\lambda C(x)\]</p> <p>[latexpage]\[g(\lambda)=\mathcal{L}(x*(\lambda),\lambda)\]</p> <p>Trong đ&oacute; [latexpage]$x^{*}=argmin_{x}\;\mathcal{L}(x,\lambda)$</p> <p>Trong đ&oacute; [latexpage]$\lambda$ l&agrave; hệ số v&ocirc; hướng, m&agrave; ch&uacute;ng ta gọi l&agrave; nh&acirc;n tử Lagrangian.</p> <p>H&agrave;m đối ngẫu g l&agrave; một giới hạn dưới cho b&agrave;i to&aacute;n tối ưu ban đầu. Nếu h&agrave;m f l&agrave; một h&agrave;m cong lồi (Convex), th&igrave; t&iacute;nh chất Strong Duality sẽ giữ nguy&ecirc;n, nghĩa l&agrave; gi&aacute; trị lớn nhất của h&agrave;m g bằng với gi&aacute; trị thấp nhất của b&agrave;i to&aacute;n tối ưu. V&igrave; vậy, nếu ch&uacute;ng ta t&igrave;m được [latexpage]$\lambda$ m&agrave; tối ưu được h&agrave;m [latexpage]$g$, th&igrave; ta c&oacute; thể giải quyết xong b&agrave;i to&aacute;n tối ưu.</p> <p>Ch&uacute;ng ta sẽ bắt đầu với việc đo&aacute;n ngẫu nhi&ecirc;n cho [latexpage]$\lambda$ v&agrave; sử dụng phương ph&aacute;p tối ưu bất kỳ để giải h&agrave;m mục ti&ecirc;u m&agrave; kh&ocirc;ng bị r&agrave;ng buộc</p> <p>[latexpage]\[x^{*}=argmin_{x}\;\mathcal{L}(x,\lambda)\]</p> <p>Tiếp theo, ch&uacute;ng ta sẽ &aacute;p dụng Gradient Ascent để cập nhật tham số [latexpage]$\lambda$ v&agrave; tối ưu h&agrave;m [latexpage]$g$. Gradient của g được t&iacute;nh như sau:</p> <p>[latexpage]\[\frac{dg}{d\lambda}=\frac{d\mathcal{L}}{dx^{*}}\frac{dx^{*}}{d\lambda}+\frac{d\mathcal{L}}{d\lambda}\]</p> <p>Nếu [latexpage]$x^{*}=argmin_{x}\;\mathcal{L}(x,\lambda), th&igrave; \frac{d\mathcal{L}}{dx^{*}}=0$</p> <p>Cụ thể l&agrave;:</p> <p>[latexpage]\[\frac{dg}{d\lambda}=\frac{d\mathcal{L}}{d\lambda}\]</p> <p>Trong bước 1 b&ecirc;n dưới, ch&uacute;ng ta sẽ t&igrave;m gi&aacute; trị x tối thiểu dựa tr&ecirc;n gi&aacute; trị [latexpage]$\lambda$ hiện tại v&agrave; &aacute;p dụng Gradient Ascent cho h&agrave;m g (bước 2 v&agrave; 3)</p> <ul> <li>T&igrave;m [latexpage]$x^{*}\leftarrow argmin_{x}\;\mathcal{L}(x,\lambda)$</li> <li>T&iacute;nh [latexpage]$\frac{dg}{d\lambda}=\frac{d\mathcal{L}}{d\lambda}(x^{*},\lambda)$</li> <li>[latexpage]$\lambda \leftarrow \lambda+\alpha\frac{dg}{d\lambda}$</li> </ul> <p>Ta sẽ thực hiện xen kẽ c&ugrave;ng l&uacute;c giữa việc cực tiểu h&oacute;a Lagrangian [latexpage]$\mathcal{L}$ tương ứng với c&aacute;c biến căn bản (x), v&agrave; tăng hệ số nh&acirc;n tử Lagrange [latexpage]$\lambda$ bằng Gradient. Với việc lặp lại v&ograve;ng lặp li&ecirc;n tục, b&agrave;i to&aacute;n sẽ đạt tới điểm tối ưu.</p> <h1>Trực quan h&oacute;a</h1> <p>Ch&uacute;ng ta sẽ thực hiện trực quan h&oacute;a c&aacute;ch thức m&agrave; giải thuật hoạt động.</p> <p>Tối thiểu h&oacute;a [latexpage]$f(x)$ với điều kiện [latexpage]$g(x)\leq 0$</p> <p><img style="width: 100%;" src="http://tek4vn.2soft.top/public_files/1-png-3" alt="1" /></p> <p>Giả sử y=g(x) v&agrave; z=f(x). y v&agrave; z sẽ tạo n&ecirc;n một kh&ocirc;ng gian G như b&ecirc;n tr&ecirc;n v&agrave; ch&uacute;ng ta sẽ vẽ trục z so với trục y. Giải ph&aacute;p cho b&agrave;i to&aacute;n sẽ l&agrave; điểm m&agrave;u cam b&ecirc;n tr&ecirc;n, tối thiểu h&oacute;a f trong v&ugrave;ng kh&ocirc;ng gian G v&agrave; g(x)=0. Đường m&agrave;u cam trong h&igrave;nh b&ecirc;n dưới ch&iacute;nh l&agrave; Lagrangian. Hệ số đường thẳng bằng [latexpage]$\lambda$ v&agrave; n&oacute; tiệm cận với đường bi&ecirc;n của G</p> <p><img style="width: 100%;" src="http://tek4vn.2soft.top/public_files/2-png-1" alt="2" /></p> <p>Ch&uacute;ng ta sẽ sử dụng Gradient Ascent để điều chỉnh [latexpage]$\lambda$ (hệ số g&oacute;c) để tối ưu gi&aacute; trị f(x) tiệm cận với G với g(x)=0</p> <p><img style="width: 100%;" src="http://tek4vn.2soft.top/public_files/3-png-1" alt="3" /></p> <p>Đ&acirc;y l&agrave; c&aacute;ch thức m&agrave; Dual Gradient Descent hoạt động.</p> <h1>V&iacute; dụ</h1> <p>Ch&uacute;ng ta sẽ c&ugrave;ng xem x&eacute;t một v&iacute; dụ.</p> <p>Tối ưu h&oacute;a h&agrave;m f với điều kiện [latexpage]$x^{2}+y^{2}=32$</p> <p>[latexpage]\[f(x,y)=x+y\]</p> <p>[latexpage]\[x^{2}+y^{2}-32=0\]</p> <p>Lagrangian c&oacute; dạng như sau:</p> <p>[latexpage]\[\mathcal{L}(x,y,\lambda ')=x+y+\lambda '(x^{2}+y^{2}-32)\]</p> <p>Hoặc</p> <p>[latexpage]\[\mathcal{L}(x,y,\lambda)=x+y+\lambda(0.5x^{2}+0.5y^{2}-16)\]</p> <p>Để tối ưu h&oacute;a hệ số [latexpage]$\mathcal{L}$, ch&uacute;ng ta cần giải như sau:</p> <p>[latexpage]\[\frac{\partial \mathcal{L}}{\partial x}=1+\lambda x=0 \Rightarrow x=\frac{-1}{\lambda}\]</p> <p>[latexpage]\[\frac{\partial \mathcal{L}}{\partial y}=1+\lambda y=0 \Rightarrow y=\frac{-1}{\lambda}\]</p> <p>[latexpage]\[\frac{\partial \mathcal{L}}{\partial \lambda}=0.5x^{2}+0.5y^{2}-16=0 \Rightarrow x^{2}+y^{2}=32\]</p> <p>V&igrave; vậy:</p> <p>[latexpage]\[\lambda=\frac{1}{4}\]</p> <p>Hoặc</p> <p>[latexpage]\[\frac{-1}{4}\]</p> <p>[latexpage]\[x={4,-4}\]</p> <p>[latexpage]\[y={4,-4}\]</p> <p>Bằng c&aacute;ch thay c&aacute;c gi&aacute; trị v&agrave;o, ch&uacute;ng ta c&oacute; thể x&aacute;c định được gi&aacute; trị max hoặc min</p> <p>[latexpage]\[f(4,4)=8=max\]</p> <p>[latexpage]\[f(-4,-4)=-8=min\]</p> <h1>Hệ số nh&acirc;n tử Lagrange</h1> <p>Vậy hệ số nh&acirc;n tử Lagrange l&agrave; g&igrave;? Ch&uacute;ng ta sẽ trực quan h&oacute;a h&agrave;m f c&ugrave;ng với biểu đồ Contour với c&aacute;c gi&aacute; trị kh&aacute;c nhau của d. g l&agrave; h&agrave;m r&agrave;ng buộc.</p> <p><img style="width: 100%;" src="http://tek4vn.2soft.top/public_files/4-png-1" alt="4" /></p> <p style="text-align: center;">Nguồn: Wikipedia</p> <p>Về mặt h&igrave;nh học, điểm tối ưu sẽ nằm ở điểm m&agrave; Gradient tại f(x,y), mũi t&ecirc;n m&agrave;u xanh, được đặt c&ugrave;ng với Gradient tại g(x,y), mũi t&ecirc;n m&agrave;u đỏ.</p> <p><img style="width: 148px; display: block; margin-left: auto; margin-right: auto;" src="http://tek4vn.2soft.top/public_files/5-png" alt="5" height="56" /></p> <p>[latexpage]\[\triangledown _{x,y}f(x,y)=\lambda \triangledown _{x,y}g(x,y)\]</p> <p>Trong đ&oacute; [latexpage]$\lambda$ l&agrave; hệ số nh&acirc;n tử Lagrange<br />Ch&uacute;ng ta c&oacute; nhiều r&agrave;ng buộc [latexpage]$(g^{1},g^{2},...,g^{i})$ v&agrave; ta muốn tối ưu [latexpage]$f(x,y)$ với điều kiện l&agrave; [latexpage]$g^{1}(x,y)=0,...,g^{i}(x,y)=0$</p> <p>Lagrangian được kh&aacute;i qu&aacute;t h&oacute;a như sau:</p> <p>[latexpage]\[\mathcal{L}(x,\lambda)=f(x)+\sum_{i}\lambda_{i}g^{(i)}(x)\]</p> <p>Phương tr&igrave;nh tối ưu sẽ l&agrave;:</p> <p>[latexpage]\[\mathcal{L}'(x,\lambda)=0\]</p> <p>Dual Gradient Descent sử dụng bất kỳ phương ph&aacute;p tối ưu h&oacute;a n&agrave;o để giảm thiểu Lagrange tương ứng với gi&aacute; trị [latexpage]$\lambda$ hiện tại. Để tối ưu h&oacute;a đường quỹ đạo, ch&uacute;ng ta sẽ sử dụng iLQR cho phương ph&aacute;p tối ưu h&oacute;a. Sau đ&oacute;, ch&uacute;ng ta sẽ &aacute;p dụng Gradient Ascent để điều chỉnh [latexpage]$\lambda$. Giải ph&aacute;p tối ưu sẽ được t&igrave;m ra bằng c&aacute;ch lặp lại c&aacute;c v&ograve;ng lặp.</p> <p>Mọi người h&atilde;y tiếp tục 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>