tek4

Actor-Critic Sử Dụng Kronecker-Factored Trust Region – Học Tăng Cường

by - September. 21, 2021
Kiến thức
<p><img class="aligncenter wp-image-6529 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/a-20.jpg" alt="" width="1000" height="667" /></p> <p style="text-align: center;">Ảnh chụp bởi&nbsp;<a href="https://unsplash.com/@chuklanov">Avel Chuklanov</a></p> <p>Trong b&agrave;i viết n&agrave;y, ch&uacute;ng ta sẽ giới thiệu về phương ph&aacute;p Actor-Critic sử dụng Kronecker-factored Trust Region, viết tắt l&agrave; ACKTR, giống với phương ph&aacute;p tối ưu h&oacute;a bậc một như Gradient Descent. Trong b&agrave;i viết <a href="https://tek4.vn/natural-policy-gradient-hoc-tang-cuong-phan-8/">Natural Policy Gradient của phần 8</a>, ch&uacute;ng ta đ&atilde; giải th&iacute;ch c&aacute;ch Natural Policy Gradient cho ph&eacute;p c&aacute;c phương thức Policy Gradient hội tụ tốt hơn bằng c&aacute;ch kh&ocirc;ng thực hiện c&aacute;c bước đi sai l&agrave;m ph&aacute; hủy hiệu suất của qu&aacute; tr&igrave;nh đ&agrave;o tạo. Tuy nhi&ecirc;n, Natural Policy Gradient l&agrave; phương ph&aacute;p tối ưu h&oacute;a bậc hai, chậm hơn nhiều so với phương ph&aacute;p tối ưu h&oacute;a bậc một.</p> <p>Trong h&igrave;nh b&ecirc;n dưới cho thấy ACKTR vượt trội hơn một số phương ph&aacute;p RL phổ biến như A2C v&agrave; TRPO.</p> <p><img class="aligncenter wp-image-6520 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/a-30.png" alt="Actor-Critic-su-dung-Kronecker" width="770" height="393" /></p> <p style="text-align: center;"><a href="https://arxiv.org/pdf/1708.05144.pdf">Nguồn</a></p> <h1>TRPO</h1> <p>B&agrave;i trước đ&atilde; đề cập về phương ph&aacute;p Natural Policy Gradient c&oacute; c&ocirc;ng thức như sau:</p> <p>[latexpage]\[\triangle \theta = \frac{1}{\beta} F^{-1}g\]<br />Trong đ&oacute; [latexpage]$g = \triangledown _{\theta}L$</p> <p>Tuy nhi&ecirc;n, việc t&iacute;nh ma trận th&ocirc;ng tin Fisher F v&agrave; ma trận nghịch đảo của n&oacute; l&agrave; rất tốn k&eacute;m.</p> <p>[latexpage]\[\triangle \theta = \frac{1}{\beta}F^{-1}g\]</p> <p>TRPO giải quyết vấn đề sau bằng c&aacute;ch sử dụng Gradient li&ecirc;n hợp (Conjugate Gradient) để t&iacute;nh xấp xỉ:</p> <p>[latexpage]\[x\approx\widehat{F}^{-1}\widehat{g}\]</p> <p>Ta chuyển b&agrave;i to&aacute;n tr&ecirc;n th&agrave;nh b&agrave;i to&aacute;n tối ưu ở dạng phương tr&igrave;nh bậc hai. Gradient li&ecirc;n hợp tương tự như Gradient Descent nhưng hiệu quả hơn nhiều đối với phương tr&igrave;nh bậc hai. N&oacute; x&aacute;c định vị tr&iacute; tối ưu trong nhiều nhất N v&ograve;ng lặp, với N l&agrave; số tham số trong m&ocirc; h&igrave;nh chiến thuật &theta;. Điều n&agrave;y nghe c&oacute; vẻ phức tạp nhưng việc t&iacute;nh to&aacute;n sẽ &iacute;t phức tạp hơn nhiều so với việc t&igrave;m ra ma trận nghịch đảo của F. Vậy l&agrave;m thế n&agrave;o ch&uacute;ng ta c&oacute; thể chuyển đổi th&agrave;nh b&agrave;i to&aacute;n tối ưu h&oacute;a? Ch&uacute;ng ta biến đổi phương tr&igrave;nh tuyến t&iacute;nh th&agrave;nh như sau:</p> <p>[latexpage]\[\widehat{F}x\approx\widehat{g}\]</p> <p>V&agrave; sử dụng Gradient li&ecirc;n hợp để tối ưu h&oacute;a phương tr&igrave;nh bậc hai tương ứng như sau:</p> <ul> <li>Giải [latexpage]$Ax=b$</li> <li>Tương đương với [latexpage]$minimize _{x}\;\;f(x)=\frac{1}{2}x^{T}Ax-b^{T}x$ v&igrave; [latexpage]$f'(x)=Ax-b=0$</li> </ul> <p>Để t&iacute;nh xấp xỉ x, ta tối ưu h&oacute;a hệ số sau:</p> <p>[latexpage]\[min _{x\in R^{n}}\;\;\frac{1}{2}x^{T}Fx-g^{T}x\]</p> <h2>Điểm thiếu s&oacute;t của phương ph&aacute;p TRPO</h2> <p>Đối với mỗi lần cập nhật th&ocirc;ng số m&ocirc; h&igrave;nh, ch&uacute;ng ta vẫn cần t&iacute;nh F. Điều n&agrave;y ảnh hưởng đến khả năng mở rộng</p> <ul> <li>Việc t&iacute;nh to&aacute;n F mỗi lần cho m&ocirc; h&igrave;nh chiến thuật hiện tại rất tốn k&eacute;m</li> <li>N&oacute; y&ecirc;u cầu một tập nhiều qu&aacute; tr&igrave;nh m&ocirc; phỏng (Rollouts) để t&iacute;nh xấp xỉ F.</li> </ul> <p>Ch&uacute;ng ta sử dụng một phương tr&igrave;nh thay thế dưới đ&acirc;y để t&iacute;nh F. Nhưng để ch&iacute;nh x&aacute;c, n&oacute; cần phải lấy mẫu rất nhiều dữ liệu.</p> <p>[latexpage]\[F= E_{p(\tau)}\left [ \triangledown _{\theta}log\pi(a_{t}|s_{t})(\triangledown _{\theta}log\pi(a_{t}|s_{t}))^{T} \right ]\]</p> <p>Do vấn đề về khả năng mở rộng, TRPO kh&ocirc;ng c&oacute; t&iacute;nh ứng dụng thực tế cho c&aacute;c mạng học s&acirc;u lớn. Theo c&aacute;c kinh nghiệm thực tế cho thấy, n&oacute; kh&ocirc;ng thực hiện tốt c&aacute;c nhiệm vụ đ&ograve;i hỏi v&agrave; y&ecirc;u cầu mạng t&iacute;ch chập s&acirc;u hoặc RNN. Việc sử dụng Gradient li&ecirc;n hợp cũng l&agrave;m phức tạp qu&aacute; tr&igrave;nh thực hiện. Ch&uacute;ng ta cần một c&aacute;ch tốt hơn v&agrave; c&oacute; thể mở rộng để t&iacute;nh to&aacute;n F. Đ&oacute; l&agrave; những g&igrave; m&agrave;&nbsp;Actor-Critic sử dụng Kronecker-factored Trust Region c&oacute; thể l&agrave;m được.</p> <h1>Actor-Critic sử dụng Kronecker-factored&nbsp;Trust Region</h1> <p>ACKTRK c&oacute; đặc điểm bao gồm:</p> <ul> <li>L&agrave; phương ph&aacute;p Policy Gradient với phương ph&aacute;p tối ưu h&oacute;a v&ugrave;ng tin cậy,</li> <li>C&oacute; kiến tr&uacute;c Actor-Critic tương tự như A2C: một mạng học s&acirc;u để t&iacute;nh to&aacute;n chiến thuật v&agrave; một mạng kh&aacute;c để t&iacute;nh to&aacute;n h&agrave;m lợi &iacute;ch</li> <li>&Aacute;p dụng ph&eacute;p t&iacute;nh xấp xỉ Kronecker-factored&nbsp;để tối ưu h&oacute;a Actor v&agrave; Critic</li> <li>ACKTR tăng tốc độ tối ưu h&oacute;a bằng c&aacute;ch giảm độ phức tạp của việc t&iacute;nh to&aacute;n ma trận nghịch đảo của F (FIM) bằng c&aacute;ch sử dụng ph&eacute;p t&iacute;nh xấp xỉ Kronecker-factored. So với tối ưu h&oacute;a bậc nhất như Stochastic Gradient Descent, ACKTRK chỉ tốn th&ecirc;m khoảng 10% -25% chi ph&iacute; cho việc t&iacute;nh to&aacute;n.</li> </ul> <h2>Kronecker-factored&nbsp;Approximate Curvature (K-FAC)</h2> <p>Ph&eacute;p tối ưu h&oacute;a bậc hai c&oacute; t&iacute;nh ch&iacute;nh x&aacute;c hơn nhưng sự gia tăng về độ phức tạp kh&ocirc;ng thể đ&aacute;nh gi&aacute; được lợi &iacute;ch tốt hơn của n&oacute; so với ph&eacute;p tối ưu h&oacute;a bậc một trong Học tăng cường (RL). Việc t&iacute;nh to&aacute;n ma trận Hessian xấp xỉ</p> <p>[latexpage]\[\Theta (n^{2})\]</p> <p>Điều n&agrave;y l&agrave; kh&ocirc;ng khả thi đối với c&aacute;c m&ocirc; h&igrave;nh mạng học s&acirc;u lớn. K-FAC t&iacute;nh xấp xỉ ma trận nghịch đảo của FIM v&agrave; t&iacute;nh to&aacute;n c&aacute;c lần cập nhật tham số của từng lớp mạng tại một thời điểm n&agrave;o đ&oacute;. Mỗi ph&eacute;p t&iacute;nh chỉ bao gồm c&aacute;c n&uacute;t trong một lớp thay v&igrave; tất cả c&aacute;c n&uacute;t trong to&agrave;n bộ m&ocirc; h&igrave;nh. Do đ&oacute;, độ phức tạp t&iacute;nh to&aacute;n giảm đ&aacute;ng kể.</p> <p>C&aacute;c k&yacute; hiệu như sau:</p> <ul> <li>[latexpage]$p(y|x)$ l&agrave; ph&acirc;n phối đầu ra của mạng nơ-ron</li> <li>[latexpage]$L=log\;p(y|x)$ l&agrave; log-likelihood (khả năng xảy ra)</li> <li>[latexpage]$W\in R^{C_{out}xC_{in}}$ l&agrave; ma trậng trọng số trong lớp [latexpage]$l^{th}$</li> <li>[latexpage]$a \in R^{C_{in}}$ l&agrave; v&eacute;c tơ k&iacute;ch hoạt đầu v&agrave;o</li> <li>[latexpage]$s=Wa$</li> </ul> <p>K-FAC t&iacute;nh to&aacute;n đạo h&agrave;m của L với c&aacute;c tham số m&ocirc; h&igrave;nh w trong một lớp mạng học s&acirc;u, thay v&igrave; to&agrave;n bộ m&ocirc; h&igrave;nh. Sau khi &aacute;p dụng quy tắc chuỗi trong c&aacute;ch t&iacute;nh đạo h&agrave;m (tức l&agrave; t&iacute;nh đạo h&agrave;m ri&ecirc;ng từng biến một giống hồi cấp 3 đ&atilde; học), đạo h&agrave;m ri&ecirc;ng của L với c&aacute;c tham số W trong một lớp c&oacute; dạng như sau:</p> <p>[latexpage]\[\triangledown _{W}L=(\triangledown _{s}L)a^{T}\]</p> <p>F c&oacute; thể được t&iacute;nh như sau:</p> <p>[latexpage]\[F=E_{p(\tau)}\left [ \triangledown _{\theta}log \;\pi(a_{t}|s_{t})(\triangledown _{\theta}log\;\pi(a_{t}|s_{t}))^{T} \right ]\]</p> <p>Ph&eacute;p t&iacute;nh tương tự cho mỗi lớp như sau:</p> <p>[latexpage]\[F_{l}=E\left [ vec \left \{ \triangledown _{W}L\right \} vec \left \{ \triangledown _{W}L\right \}^{T} \right ]\]</p> <p>&Aacute;p dụng c&aacute;c đạo h&agrave;m ri&ecirc;ng trước đ&oacute;, việc t&iacute;nh to&aacute;n được đơn giản h&oacute;a như sau:</p> <p>[latexpage]\[F_{l}=E\left [ vec \left \{ \triangledown _{W}L\right \}vec\left \{ \triangledown _{W}L\right \}^{T} \right ]=E\left [ aa^{T}\otimes \triangledown _{s}L(\triangledown _{s}L)^{T} \right ]\]<br />[latexpage]\[\approx E[aa^{T}]\otimes E[\triangledown _{s}L(\triangledown _{s}L)^{T}]:=A\otimes S:=\widehat{F}_{l}\],<br />trong đ&oacute; A l&agrave; [latexpage]$E[aa^{T}]$ v&agrave; S l&agrave; k&yacute; hiệu cho [latexpage]$E[\triangledown _{s}L(\triangledown _{s}L)^{T}]$</p> <p>Với t&iacute;ch của hai vec-tơ được t&iacute;nh như sau:</p> <p>[latexpage]\[u\otimes v=uv^{T}=\begin{bmatrix}u_{1}\\ u_{2}\\ u_{3}\\ u_{4}\end{bmatrix}\begin{bmatrix}v_{1} &amp;v_{2}&amp;v_{3}\end{bmatrix}=\begin{bmatrix}u_{1}v_{1} &amp; u_{1}v_{2} &amp;u_{1}v_{3} \\ u_{2}v_{1} &amp;u_{2}v_{2} &amp;u_{2}v_{3} \\ u_{3}v_{1} &amp;u_{3}v_{2} &amp; u_{3}v_{3}\\ u_{4}v_{1} &amp;u_{4}v_{2} &amp; u_{4}v_{3}\end{bmatrix}\]</p> <p>&Aacute;p dụng cho:</p> <p>[latexpage]\[(P\otimes Q)^{-1}=P^{-1}\otimes Q^{-1} v&agrave; (P\otimes Q)vec(T)=PTQ^{T}\]</p> <p>C&aacute;c lần cập nhật W cho mỗi lớp c&oacute; dạng:</p> <p>[latexpage]\[vec(\triangle W)=\widehat{F}_{l}^{-1}vec{\triangledown _{W}\mathcal{J}}=vec(A^{-1}\triangledown _{W}\mathcal{J}S^{-1})\]</p> <p>V&igrave; vậy, để t&iacute;nh to&aacute;n c&aacute;c thay đổi tham số cho mỗi lớp, ch&uacute;ng ta sẽ t&igrave;m ma trận nghịch đảo của A v&agrave; S.</p> <p>Ch&uacute;ng ta cập nhật mạng theo từng lớp. Mỗi ph&eacute;p t&iacute;nh chỉ bao gồm c&aacute;c n&uacute;t trong mỗi lớp. H&atilde;y xem x&eacute;t số lượng n&uacute;t trong mỗi lớp l&agrave; h&agrave;ng ngh&igrave;n hoặc h&agrave;ng trăm, thay v&igrave; h&agrave;ng triệu cho to&agrave;n bộ mạng. Điều n&agrave;y c&oacute; thể quản l&yacute; dễ hơn v&agrave; K-FAC l&agrave;m giảm đ&aacute;ng kể độ phức tạp của việc t&iacute;nh to&aacute;n. Ngay cả phương ph&aacute;p trong b&agrave;i b&aacute;o d&agrave;nh cho mạng d&agrave;y đặc (Dense Network), ph&eacute;p t&iacute;nh xấp xỉ K-FAC cho mạng t&iacute;ch chập cũng đ&atilde; được c&aacute;c nh&agrave; nghi&ecirc;n cứu ph&aacute;t triển.</p> <p>Trong TRPO, phương sai trong ph&eacute;p t&iacute;nh to&aacute;n F l&agrave; rất cao. Để cải thiện độ ch&iacute;nh x&aacute;c, nhiều mẫu sẽ được thu thập trong ph&eacute;p t&iacute;nh to&aacute;n F.</p> <p>[latexpage]\[F=E_{p(\tau)}\left [ \triangledown _{\theta}log\;\pi(a_{t}|s_{t})(\triangledown _{\theta}log\;\pi (a_{t}|s_{t}))^{T} \right ]\]</p> <p>K-FAC duy tr&igrave; c&aacute;c ph&eacute;p t&iacute;nh gi&aacute; trị trung b&igrave;nh cho c&aacute;c kỳ vọng A v&agrave; S ở mức xấp xỉ. Điều n&agrave;y l&agrave;m giảm phương sai v&agrave; do đ&oacute; K-FAC y&ecirc;u cầu &iacute;t mẫu hơn nhiều. Kết quả thực nghiệm chứng minh rằng ACKTR hoạt động hiệu quả hơn.</p> <h2>Critic</h2> <p>Trong phương ph&aacute;p Actor-Critic sử dụng Kronecker-factored Trust Region, c&oacute; sử dụng hệ số Critic để ước t&iacute;nh h&agrave;m lợi &iacute;ch. Để đ&agrave;o tạo m&ocirc; h&igrave;nh, ch&uacute;ng ta so s&aacute;nh c&aacute;c dự đo&aacute;n của m&ocirc; h&igrave;nh với c&aacute;c gi&aacute; trị mục ti&ecirc;u (r (x) = ước t&iacute;nh (x) - mục ti&ecirc;u (x)) v&agrave; giải b&agrave;i to&aacute;n dưới dạng b&agrave;i to&aacute;n b&igrave;nh phương nhỏ nhất (c&ograve;n gọi l&agrave; sai số b&igrave;nh phương trung b&igrave;nh MSE). Một c&aacute;ch tiếp cận phổ biến với thuật to&aacute;n bậc hai l&agrave; Gauss-Newton. Nếu ch&uacute;ng ta so s&aacute;nh Actor v&agrave; Critic, c&aacute;c phương tr&igrave;nh cập nhật c&aacute;c tham số m&ocirc; h&igrave;nh c&oacute; dạng đều tương tự nhau.</p> <p>[latexpage]\[\triangle \theta=\frac{1}{\beta}F^{-1}g\]<br />trong đ&oacute; [latexpage]$F^{-1}$ l&agrave; Actor<br />[latexpage]\[\triangledown r(x)\equiv J(x)\]<br />[latexpage]\[\triangle \theta=(J_{k}^{T}J_{k})^{-1}J_{k}^{T}(-r_{k})\]<br />trong đ&oacute; [latexpage]$(J_{k}^{T}J_{k})^{-1}$ l&agrave; Critic</p> <p>Ma trận th&ocirc;ng tin F (FIM) tương đương với ma trận Gauss-Newton về hệ số Critic. Do đ&oacute;, ch&uacute;ng ta c&oacute; thể &aacute;p dụng phương ph&aacute;p t&iacute;nh xấp xỉ K-FAC tương tự cho hệ số Critic v&agrave; cập nhật từng lớp một để giảm độ phức tạp cho việc t&iacute;nh to&aacute;n.</p> <p>B&ecirc;n dưới đ&acirc;y l&agrave; sự cải thiện hiệu suất trong việc &aacute;p dụng chuẩn Gauss-Newton (tối ưu h&oacute;a bậc hai) thay v&igrave; chuẩn Euclid (bậc một) cho hệ số Critic trong ACKTR.</p> <p><img class="aligncenter wp-image-6521 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/a-31.png" alt="Actor-Critic-su-dung-Kronecker" width="770" height="276" /></p> <p style="text-align: center;"><a href="https://arxiv.org/pdf/1708.05144.pdf">Nguồn</a></p> <p>Phương ph&aacute;p Actor-Critic sử dụng Kronecker-factored Trust Region:</p> <ul> <li>Sử dụng ph&eacute;p tối ưu h&oacute;a v&ugrave;ng tin cậy để cải thiện sự hội tụ.</li> <li>T&iacute;nh to&aacute;n c&aacute;c lần cập nhật tham số với K-FAC cho cả hệ số Actor v&agrave; Critic. N&oacute; l&agrave;m giảm độ phức tạp t&iacute;nh to&aacute;n giống với c&aacute;c ph&eacute;p tối ưu h&oacute;a bậc nhất (như Stochastic Gradient Descent).</li> <li>Duy tr&igrave; ph&eacute;p t&iacute;nh gi&aacute; trị trung b&igrave;nh để giảm phương sai trong việc t&iacute;nh to&aacute;n K-FAC. Điều n&agrave;y cho ph&eacute;p K-FAC sử dụng &iacute;t mẫu hơn TRPO để t&iacute;nh gần đ&uacute;ng ma trận nghịch đảo của F một c&aacute;ch ch&iacute;nh x&aacute;c.</li> </ul> <p>ACKTR mở rộng quy m&ocirc; tốt hơn với c&aacute;c m&ocirc; h&igrave;nh mạng học s&acirc;u lớn. N&oacute; giải quyết c&aacute;c nhiệm vụ li&ecirc;n quan tới việc kiểm so&aacute;t li&ecirc;n tục c&ugrave;ng với khả năng quan s&aacute;t Raw pixel m&agrave; TRPO kh&ocirc;ng thể xử l&yacute;.</p> <h2>Hiệu quả hoạt động của ACKTR</h2> <p>ACKTR đạt điểm phần thưởng cao hơn (cột phần thưởng) v&agrave; đạt được hiệu suất trong số lần tập luyện &iacute;t hơn (cột phần thưởng).</p> <p><img class="aligncenter wp-image-6522 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/a-32.png" alt="Actor-Critic-su-dung-Kronecker" width="770" height="296" /></p> <p style="text-align: center;"><a href="https://arxiv.org/pdf/1708.05144.pdf">Nguồn</a></p> <p><img class="aligncenter wp-image-6523 size-full" src="https://tek4.vn/wp-content/uploads/2020/11/a-33.png" alt="Actor-Critic-su-dung-Kronecker" width="770" height="275" /></p> <p style="text-align: center;"><a href="https://arxiv.org/pdf/1708.05144.pdf">Nguồn</a></p> <p>Một điểm lưu &yacute; đ&oacute; l&agrave; ACKTR kh&ocirc;ng hề đơn giản để triển khai cho mạng RNN v&agrave; c&aacute;c mạng c&oacute; c&aacute;c tham số được chia sẻ.</p> <p>Đến đ&acirc;y l&agrave; kết th&uacute;c của b&agrave;i. Mọi người c&oacute; thể g&oacute;p &yacute; v&agrave; tham khảo những b&agrave;i tiếp theo trong series Học tăng cường c&ugrave;ng với <a href="http://tek4.vn">tek4</a> nh&eacute;!</p> <p>P/s: Mong mọi người lu&ocirc;n ủng hộ để <a href="http://tek4.vn">tek4</a> c&oacute; thể ra nhiều b&agrave;i hơn!</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>