Phương ph&aacute;p Importance Sampling đ&oacute;ng một vai tr&ograve; quan trọng trong phương ph&aacute;p lấy mẫu để ph&acirc;n t&iacute;ch v&agrave; học tập tăng cường (RL). Trong RL, Importance Sampling t&iacute;nh c&aacute;c h&agrave;m gi&aacute; trị cho một chiến thuật $\pi$ với c&aacute;c mẫu được thu thập trước đ&oacute; từ một chiến thuật cũ $\pi &rsquo;$. N&oacute;i c&aacute;ch kh&aacute;c, việc t&iacute;nh to&aacute;n tổng số phần thưởng khi thực hiện một h&agrave;nh động sẽ rất mất c&ocirc;ng sức. Tuy nhi&ecirc;n, nếu h&agrave;nh động mới gần giống với h&agrave;nh động trước đ&oacute;, phương ph&aacute;p Importance Sampling cho ph&eacute;p việc t&iacute;nh to&aacute;n gi&aacute; trị phần thưởng mới dựa tr&ecirc;n c&aacute;ch t&iacute;nh cũ.
Cụ thể như sau, với phương ph&aacute;p Monte Carlo, bất cứ khi n&agrave;o cập nhật cho chiến thuật $\theta$, ch&uacute;ng ta cần thu thập một đường quỹ đạo ho&agrave;n to&agrave;n mới để t&iacute;nh to&aacute;n phần thưởng kỳ vọng.
$\triangledown _{\theta}J(\theta)\approx\frac{1}{N}\sum_{i=1}^{N}\left ( \sum_{t=1}^{T}\triangledown_{\theta} log\;\pi_{\theta}(a_{i,t}|s_{i,t})\right )\left ( \sum_{t=1}^{T}r(s_{i,t},a_{i,t}) \right )$
Một đường quỹ đạo c&oacute; thể chứa h&agrave;ng trăm phần tử v&agrave; sẽ kh&ocirc;ng hiệu quả cho mỗi lần phải cập nhật lại. Với phương ph&aacute;p Importance Sampling, ch&uacute;ng ta chỉ sử dụng lại c&aacute;c mẫu cũ để t&iacute;nh to&aacute;n lại tổng gi&aacute; trị phần thưởng. Tuy nhi&ecirc;n, khi chiến thuật hiện tại ch&ecirc;nh lệch với chiến thuật cũ qu&aacute; nhiều, độ ch&iacute;nh x&aacute;c sẽ giảm xuống. Do đ&oacute;, ch&uacute;ng ta cần thường xuy&ecirc;n đồng bộ h&oacute;a lại cả hai chiến thuật.
Trong một ngữ cảnh kh&aacute;c. ch&uacute;ng ta sử dụng Importance Sampling để viết lại phương tr&igrave;nh Policy Gradient v&agrave; sử dụng ch&uacute;ng để đưa ra c&aacute;c giải ph&aacute;p mới.
V&iacute; dụ: ch&uacute;ng ta c&oacute; thể đặt lại ph&eacute;p tối ưu h&oacute;a c&ugrave;ng với c&aacute;c r&agrave;ng buộc kh&ocirc;ng cho ph&eacute;p việc thay đổi chiến thuật qu&aacute; mức. Ch&uacute;ng ta sẽ điều chỉnh lại &yacute; tưởng về v&ugrave;ng tin cậy.
$maximize_{\theta}\;\;\widehat{\mathbb{E}}\left [ \frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{old}}(a_{t}|s_{t})}\widehat{A}_{t} \right ]$
Với điều kiện $\widehat{\mathbb{E}}_{t}[KL[\pi_{\theta_{old}}(\cdot |s_{t}),\pi_{\theta}(\cdot |s_{t})]]\leq \delta$
Kh&ocirc;ng thực hiện c&aacute;c bước đi qu&aacute; mức, ch&uacute;ng ta sẽ đảm bảo được rằng ch&uacute;ng ta sẽ kh&ocirc;ng thực hiện c&aacute;c thay đổi sai lầm v&agrave; l&agrave;m hỏng qu&aacute; tr&igrave;nh đ&agrave;o tạo. Khi ch&uacute;ng ta tiếp tục cải thiện chiến thuật, ch&uacute;ng ta sẽ t&igrave;m ra được giải ph&aacute;p tối ưu.
<h1 style="text-align: justify;">Vậy Importance Sampling l&agrave; g&igrave;?</h1>
Importance Sampling l&agrave; một kỹ thuật ước t&iacute;nh gi&aacute; trị kỳ vọng của f(x) trong đ&oacute; x c&oacute; ph&acirc;n phối dữ liệu p. Tuy nhi&ecirc;n, Thay v&igrave; lấy mẫu từ p, ch&uacute;ng ta sẽ t&iacute;nh kết quả từ việc lấy mẫu q.
$\mathbb{E}_{p}[f(x)]=\mathbb{E}_{q}\left ( \frac{f(X)p(X)}{q(X)} \right )$
Ch&uacute;ng ta sẽ sử dụng ph&acirc;n phối lấy mẫu q để t&iacute;nh gi&aacute; trị kỳ vọng cho p sử dụng c&ocirc;ng thức sau:
$\mathbb{E}[f(x)]\approx \frac{1}{n}\sum_{i=1}^{n}\frac{f(X_{i})p(X_{i})}{q(X_{i})}\;\;\;X_{i}\sim q$
Để đảm bảo hiệu quả, q(xi) phải kh&aacute;c 0 nếu p(xi) tương ứng cũng kh&aacute;c 0. Ch&uacute;ng ta sẽ lấy mẫu một v&iacute; dụ như sau.
Đầu ti&ecirc;n ta sẽ t&iacute;nh to&aacute;n Ep[f(x)] v&agrave; Eq[f(x)]. Hai hệ số n&agrave;y phải kh&aacute;c nhau. Trong v&iacute; dụ b&ecirc;n dưới, ch&uacute;ng ta sẽ t&iacute;nh Eq[f(x)] với ph&acirc;n phối p.
<ul style="text-align: justify;">
<li>$f(1)=2,f(2)=3, f(3)=4$, c&ograve;n lại bằng 0</li>
</ul>
Giả sử x&aacute;c suất ph&acirc;n phối p v&agrave; q l&agrave;:
<ul style="text-align: justify;">
<li>$p(x=1)=\frac{1}{3},p(x=2)=\frac{1}{3},p(x=3)=\frac{1}{3}$</li>
<li>$q(x=1)=0,q(x=2)=\frac{1}{3},q(x=3)=\frac{2}{3}$</li>
<li>$\mathbb{E}_{p}[f(x)]=2*\frac{1}{3}+3*\frac{1}{3}+4*\frac{1}{3}=3$</li>
<li>$\mathbb{E}_{q}[f(x)]=3*\frac{1}{3}+4*\frac{2}{3}=3\frac{2}{3}$</li>
</ul>
Ch&uacute;ng ta sẽ điều chỉnh lại trọng số cho gi&aacute; trị kỳ vọng với ph&acirc;n phối p
$\mathbb{E}_{q}[f(x)]=\mathbb{E}\left [ f(x)\frac{q(x)}{p(x)} \right ]$
$=\mathbb{E}_{p}[f(x=2)]*\frac{q(x=2)}{p(x=2)}+\mathbb{E}_{p}[f(x=3)]*\frac{q(x=3)}{p(x=3)}$
$=3*\frac{1}{3}*1+4*\frac{1}{3}*2=3\frac{2}{3}$
Ch&uacute;ng ta c&oacute; thể sử dụng c&aacute;c ph&acirc;n phối lấy mẫu kh&aacute;c nhau để t&iacute;nh gi&aacute; trị kỳ vọng. Trong học tăng cường, ch&uacute;ng ta sử dụng lại c&aacute;c kết quả lấy mẫu từ một chiến thuật cũ để điều chỉnh chiến thuật hiện tại.
Trong phương ph&aacute;p lấy mẫu v&agrave; ph&acirc;n t&iacute;ch, p(x) đ&atilde; được m&ocirc; h&igrave;nh h&oacute;a v&agrave; việc t&iacute;nh to&aacute;n p(x) cho mỗi x sẽ kh&ocirc;ng qu&aacute; kh&oacute;. Đối với phương ph&aacute;p lấy mẫu v&agrave; ph&acirc;n t&iacute;ch, ch&uacute;ng ta sẽ sử dụng ph&acirc;n phối q, dễ kiểm so&aacute;t hơn, để tạo c&aacute;c mẫu.
<h1 style="text-align: justify;">Importance Sampling tối ưu</h1>
Độ ch&iacute;nh x&aacute;c của gi&aacute; trị kỳ vọng sẽ tăng l&ecirc;n khi số lượng mẫu tăng l&ecirc;n. Vậy đ&acirc;u sẽ l&agrave; ph&acirc;n phối lấy mẫu tốt nhất để giảm thiểu phương sai của ph&eacute;p t&iacute;nh?
Để t&iacute;nh kỳ vọng của f.
$E_{p(x)}[f(x)]$
Ch&uacute;ng ta sẽ sử dụng Importance Sampling c&ugrave;ng với ph&acirc;n phối lấy mẫu q.
$E_{p(x)}[f(x)]\approx \frac{1}{N}\Sigma_{i}\frac{p(x_{i})}{q(x_{i})}f(x_{i})$
Để ph&eacute;p t&iacute;nh c&oacute; phương sai thấp nhất, ph&acirc;n phối mẫu q phải:
$q(x)\propto p(x)|f(x)|$
Về cơ bản, nếu ch&uacute;ng ta muốn giảm phương sai của ph&eacute;p t&iacute;nh, ch&uacute;ng ta sẽ phải lấy c&aacute;c điểm dữ liệu với gi&aacute; trị phần thưởng cao hơn.
<h1 style="text-align: justify;">Importance Sampling được chuẩn h&oacute;a</h1>
C&oacute; nhiều m&ocirc; h&igrave;nh ML thuộc mạng Bayesian hoặc Markov Random Field (MRF). Trong mạng Bayes, p c&oacute; thể được t&iacute;nh to&aacute;n dễ d&agrave;ng. Nhưng l&agrave;m thế n&agrave;o ch&uacute;ng ta c&oacute; thể triển khai với c&aacute;c m&ocirc; h&igrave;nh kh&aacute;c như MRF?
\[p(x)=\frac{\widehat{p}(x)}{Z}\]
Ch&uacute;ng ta sẽ viết lại c&ocirc;ng thức sử dụng p chưa chuẩn h&oacute;a.
$E_{p}[f(x)]=\int f(x)p(x)dx$
$=\frac{1}{X}\int f(x)\frac{\widehat{p}(x)}{q(x)}q(x)dx$
$=\frac{\int f(x)r(x)q(x)dx}{\int r(x)q(x)dx}$
$=\frac{\sum _{m}f(x^{m})r^{m}}{\sum_{m}r^{m}}$
$=sum_{m}f(x^{m})w^{m}$
Trong đ&oacute;:
$r(x)=\frac{\widehat{p}(x)}{q(x)}$
$x^{m}\sim q(x)$
$r^{m}=\frac{\widehat{p}(x^{m})}{q(x^{m})}$
$w^{m}=\frac{r^{m}}{\sum_{m}r^{m}}$
Ch&uacute;ng ta sẽ t&iacute;nh $r^{m}$ với ph&acirc;n phối chưa chuẩn h&oacute;a v&agrave; tổng $r^{m}$ để chuẩn h&oacute;a ph&acirc;n phối. Điều n&agrave;y gi&uacute;p tr&aacute;nh được việc t&iacute;nh to&aacute;n hệ số chuẩn h&oacute;a th&ocirc;ng thường Z, thường sẽ rất kh&oacute; khăn trong việc t&iacute;nh to&aacute;n. Đ&acirc;y được gọi l&agrave; Importance Sampling chuẩn h&oacute;a.
Phương ph&aacute;p Importance Sampling chưa chuẩn h&oacute;a sẽ kh&ocirc;ng bị ch&ecirc;nh lệch, trong khi Importance Sampling chuẩn h&oacute;a th&igrave; ngược lại. Tuy nhi&ecirc;n, Importance Sampling chuẩn h&oacute;a c&oacute; gi&aacute; trị phương sai thấp hơn.
\[E_{p}[f(x)]\approx \sigma_{m}f(x^{m})w^{m}\]
$w^{m} =1$ nếu ch&uacute;ng ta chỉ thu thập 1 điểm dữ liệu.
Mọi người h&atilde;y theo d&otilde;i c&aacute;c b&agrave;i tiếp theo 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 Importance Sampling – Học Tăng Cường

Cùng tác giả

Admin

Có liên quan