&nbsp;
C&aacute;c giải thuật tối ưu trong RL sẽ được đề cập trong b&agrave;i viết n&agrave;y.
<h1>V&ugrave;ng tin cậy</h1>
C&oacute; hai phương ph&aacute;p tối ưu h&oacute;a ch&iacute;nh bao gồm t&igrave;m kiếm theo một đường thẳng (Line search) v&agrave; V&ugrave;ng tin cậy (Trust Region). Gradient Descent l&agrave; một phương ph&aacute;p t&igrave;m kiếm theo đường thẳng. Đầu ti&ecirc;n, ch&uacute;ng ta sẽ x&aacute;c định hướng c&oacute; chiều giảm dần v&agrave; thực hiện một bước đi theo hướng đ&oacute;. Trong Gradient Descent, k&iacute;ch thước của bước đi bằng:
<pre>Gradient &times; Learning Rate <img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/285c95a6-0615-4e63-a921-7dff6a7d574c" alt="" width="817" height="405" /></pre>
&nbsp;
Trong v&ugrave;ng tin cậy, ch&uacute;ng ta sẽ x&aacute;c định k&iacute;ch thước bước đi tối đa m&agrave; ch&uacute;ng ta muốn d&ograve; t&igrave;m v&agrave; sau đ&oacute; x&aacute;c định điểm tối ưu trong v&ugrave;ng tin cậy n&agrave;y. H&atilde;y bắt đầu với k&iacute;ch thước bước đi tối đa ban đầu $\delta$, l&agrave; b&aacute;n k&iacute;nh của v&ugrave;ng tin cậy (v&ograve;ng tr&ograve;n m&agrave;u v&agrave;ng). Mục ti&ecirc;u của ch&uacute;ng ta l&agrave; t&igrave;m điểm tối ưu cho m trong b&aacute;n k&iacute;nh $\delta$.
\[max_{s\in \mathbb{R}^{n}}\;m_{k}(s)\]
\[s.t.\;\;\left \| s \right \|\leq \delta\
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/0f5c48dc-a32b-45a1-b72e-708519940f60" alt="" width="817" height="1000" />
V&ugrave;ng tin cậy c&oacute; thể được mở rộng hoặc thu nhỏ trong thời gian thực hiện để điều chỉnh theo độ cong của bề mặt v&agrave; c&oacute; nhiều khả năng c&oacute; thể xảy ra. Trong phương ph&aacute;p v&ugrave;ng tin cậy truyền thống, v&igrave; ch&uacute;ng ta t&iacute;nh xấp xỉ h&agrave;m mục ti&ecirc;u f với m, một khả năng xảy ra sẽ l&agrave; thu hẹp v&ugrave;ng tin cậy nếu m l&agrave; h&agrave;m t&iacute;nh xấp xỉ k&eacute;m của f tại điểm tối ưu. Ngược lại ch&uacute;ng ta sẽ triển khai rộng hơn. Sau đ&acirc;y l&agrave; phương ph&aacute;p v&ugrave;ng tin cậy sẽ tự động điều chỉnh k&iacute;ch thước theo c&aacute;c đặc điểm vừa đề cập.
<ol>
<li>Bước khởi tạo: Đặt $k =0, \;\triangle _{0} &gt; 0$ v&agrave; chọn điểm bắt đầu $x_{0}$ với phỏng đo&aacute;n ban đầu. $\eta \in (0,1),\; \eta_{s}\in (0,\eta_{v}),\; \gamma _{i}\geq 1$ v&agrave; $\gamma_{d} \in (0,1)$</li>
<li>Cho tới khi đạt tới điểm hội tụ, thực hiện lặp lại c&aacute;c bước sau:</li>
</ol>
<ul>
<li>X&acirc;y dựng một m&ocirc; h&igrave;nh bậc hai $m(s)$ với $s \mapsto f(x_{k}+s)$</li>
<li>Giải b&agrave;i to&aacute;n v&ugrave;ng tin cậy để t&igrave;m ra $s_{k}$ sao cho $m(s_{k}) &ldquo;&lt;&rdquo; f_{k}$ v&agrave; $\left \| s \right \|\leq \triangle _{k}$ v&agrave; x&aacute;c định
<ul>
<li>$p_{k}=\frac{f_{k}-f(x_{k}+s_{k})}{f_{k}-m_{k}(s_{k})}$</li>
</ul>
</li>
<li>Nếu $p_{k} \geq \eta_{v}$, đặt $x_{k+1}=x_{k}+s_{k}$ v&agrave; $\triangle_{k+1}= \gamma_{i}\triangle _{k}$</li>
<li>Nếu $p_{k} \geq \eta_{s}$, đặt $x_{k+1}=x_{k}+s_{k}$ v&agrave; $\triangle _{k+1}=\triangle _{k}$</li>
<li>V&agrave; nếu $p_{k} &lt; \eta _{s}$, đặt $x_{k+1}=x_{k}$ v&agrave; $\triangle _{k+1}=\gamma _{d} \triangle _{k}$</li>
<li>Tăng k l&ecirc;n 1 đơn vị</li>
</ul>
<h1>Phương ph&aacute;p Newton</h1>
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/c3029106-c340-4708-92a0-1aa99ac5fb89" alt="" width="817" height="311" />
<a href="https://www.mathworks.com/matlabcentral/fileexchange/52362-newton-s-method">Nguồn</a>
Để giải $f(x) = 0$, ch&uacute;ng ta sẽ tiếp tục v&ograve;ng lặp cho đến khi n&oacute; hội tụ.
\[x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}\]
N&oacute; được sử dụng để tối ưu h&oacute;a:
<img style="display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/9256169c-81a4-4bed-a47e-19224fe2b072" alt="" width="817" height="311" />
<a href="http://fourier.eng.hmc.edu/e176/lectures/NM/node25.html">Nguồn</a>
V&ograve;ng lặp được sử dụng sẽ l&agrave;:
\[x_{n+1}=x_{n}-\frac{f'(x_{n})}{f''(x_{n})}\]
<h1>B&agrave;i to&aacute;n b&igrave;nh phương tối thiểu phi tuyến t&iacute;nh sử dụng phương ph&aacute;p Gauss-Newton</h1>
Giả sử ch&uacute;ng ta c&oacute; một h&agrave;m $g(t)$ được m&ocirc; h&igrave;nh h&oacute;a theo c&aacute;c tham số x1 v&agrave; x2.
\[g(t)=x_{1}e^{x_{2}t}\]
V&agrave; ch&uacute;ng ta c&oacute; c&aacute;c mẫu đ&agrave;o tạo cho t với nh&atilde;n đầu ra l&agrave; y.
\[t_{i}:\;\;1\;2\;3\;4\;5\;8\]
\[y_{i}:\;\;3\;4\;6\;11\;20\]
Ch&uacute;ng ta c&oacute; thể x&aacute;c định một h&agrave;m r để đo lường sai số giữa m&ocirc; h&igrave;nh của ch&uacute;ng ta v&agrave; nh&atilde;n đầu ra:
\[r_{i}(x)=g(t_{i})-y_{i}=x_{1}e^{x_{2}t_{i}}-y_{i}\]
B&acirc;y giờ, mục ti&ecirc;u của ch&uacute;ng ta l&agrave; tối ưu h&oacute;a m&ocirc; h&igrave;nh g với c&aacute;c mẫu để giảm thiểu h&agrave;m mục ti&ecirc;u sau:
\[min_{x\in R^{n}}\;f(x)=\frac{1}{2}\sum_{i=1}^{m}r_{i}(x)^{2}\]
Trong phần n&agrave;y, ch&uacute;ng ta sẽ &aacute;p dụng b&agrave;i to&aacute;n b&igrave;nh phương tối thiểu phi tuyến với phương ph&aacute;p Gauss-Newton.
Ph&eacute;p tối ưu h&oacute;a của phương ph&aacute;p Newton c&oacute; dạng:
\[x_{n+1}=x_{n}-\frac{f'(x_{n})}{f''(x_{n})}\]
\[f''(x_{n})(x_{n+1}-x_{n})=-f'(x_{n})\]
Theo phương tr&igrave;nh tr&ecirc;n, ch&uacute;ng ta c&oacute; thể viết lại &Delta;x l&agrave; hướng t&igrave;m kiếm p. Phương tr&igrave;nh c&oacute; dạng như sau:
\[\triangledown ^{2}f(x)p^{N}=-\triangledown f(x)\]
Ta sẽ t&iacute;nh đạo h&agrave;m bậc một v&agrave; bậc hai như sau:
\[f(x)=\frac{1}{2}\sum_{i=1}^{m} r_{i}(x)^{2}=\frac{1}{2}r(x)^{T}r(x)\]
\[\triangledown f(x)=\triangledown r(x)r(x)=J(x)^{T}r(x)\]
Trong đ&oacute;:
<ul>
<li>$\triangledown r(x)\equiv J(x)$</li>
<li>$\triangledown ^{2}f(x)=\triangledown r(x)\triangledown r(x)^{T}+\sum_{i=1}^{m}r_{i}(x)\triangledown ^{2}r_{i}(x)$</li>
<li>$=J(x)^{T}J(x)+Q(x)\approx J(x)^{T}J(x)$</li>
</ul>
Trong phương ph&aacute;p Gauss-Newton, ch&uacute;ng ta t&iacute;nh gần đ&uacute;ng đạo h&agrave;m cấp hai ở tr&ecirc;n m&agrave; kh&ocirc;ng sử dụng số hạng Q. Số hạng Q sẽ nhỏ hơn số hạng đầu ti&ecirc;n v&agrave; nếu b&agrave;i to&aacute;n kh&ocirc;ng c&oacute; số dư th&igrave; r = Q = 0.
Phương ph&aacute;p Gauss-Newton &aacute;p dụng ph&eacute;p t&iacute;nh gần đ&uacute;ng n&agrave;y cho phương ph&aacute;p Newton.
\[\triangledown ^{2}f(x)p^{N}=-\triangledown f(x)\]
\[\triangledown ^{2}f(x)\approx J(x)^{T}J(x)\]
\[\triangledown f(x)=J(x)^{T}r(x)\]
\[J(x)^{T}J(x)p^{GN}=-J(x)^{T}r(x)\]
\[x'=x+p^{GN}\]
Hướng t&igrave;m kiếm sử dụng phương ph&aacute;p Gauss-Newton c&oacute; dạng:
\[p=(J^{T}_{k}J_{k})^{-1}J_{k}^{T}(-r_{k})\]
Tr&ecirc;n đ&acirc;y l&agrave; c&aacute;c giải thuật tối ưu trong RL, hy vọng rằng mọi người đ&atilde; qua được một số giải thuật.
P/s: 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;. 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

Giải Thuật Tối Ưu Trong RL – Học Tăng Cường

Cùng tác giả

Admin

Có liên quan