Phương pháp multiplicative weight update II-- Multiplicative weight update II

Tiếp tục bài trước, ta tìm hiểu các chiến lược ra quyết định dựa trên tham khảo ý kiến chuyên gia. Nếu bạn chưa đọc bài trước thì cũng chưa nên đọc bài này. Một số bất đẳng thức sau đây sẽ có ích trong các chứng minh:

$\begin{array} {l} -\ln(1-\epsilon) & \leq \epsilon + \epsilon^2 \qquad \mbox{ when }\epsilon \leq 1/2 \\ \ln(1+\epsilon) &\geq \epsilon - \epsilon^2 \qquad \mbox{ when }\epsilon \leq 1/2 \\ (1-\epsilon)^x &\leq (1 -\epsilon x) \qquad \mbox{ when }\epsilon \leq 1/2, x \in [0,1]
\\ (1+\epsilon)^{-x} &\leq (1 -\epsilon x) \qquad \mbox{ when }\epsilon \leq 1/2, x \in [-1,0]
\\ (1-\epsilon) &\leq e^{-\epsilon}
\\ e^{-\epsilon } &\leq (1 - \epsilon + \epsilon ^2) \qquad \mbox{when }\epsilon \in [1,1] \end{array} \qquad (1)$

Chứng minh các bất đẳng thức này không khó, và chi tiết coi như bài tập cho bạn đọc (bài tập 1).

Bài toán tham khảo chuyên gia (tiếp)

Trong bài trước, chúng ta đã tìm hiểu trò chơi đoán chứng khoán lên/xuống (1/0) sử dụng ý kiến của $n$ chuyên gia. Mục tiêu của trò chơi là dự đoán sai ít nhất có thể. Nhìn dưới góc độ kinh tế, nếu mỗi dự đoán sai bạn phải trả chi phí $1$ đồng và nếu dự đoán đúng bạn không phải trả gì cả thì mục tiêu của bài toán là tìm một chiến lược dự đoán sao cho tổng chi phí nhỏ nhất.

Rõ ràng bài toán trên đã đơn giản hóa thực tế tới mức không thực tế. Trong post này, ta sẽ xét bài toán tổng quát hơn và thực tế hơn. Thay vì chỉ đoán chứng khoán lên/ xuống, bạn phải dự đoán giá trị lên/xuống của chứng khoán. Với mỗi dự đoán, bạn sẽ phải trả một chị phí là một số thực $c$. Ở đây ta cho phép $c$ < $0$; trong trường hợp này, thực ra là bạn đã thu được lợi nhuận thay vì phải trả một chi phí. Tuy nhiên, ta vẫn dùng từ chi phí cho phát biểu của bài toán trở nên đơn giản.

Phát biểu bài toán: Ta vẫn sử dụng các kí hiệu $n,T$ như trong bài toán tham khảo chuyên gia ở bài trước. Giả sử trong ngày thứ $t$, chuyên gia $i$ cho một dự đoán, và dự đoán này sẽ tương ứng với một chi phí $m_t[i] \in [-1,1]$. (Nếu $m_t[i] $ < $0$ thì dự đoán của chuyên gia này sẽ mang về lợi nhuận cho bạn và ngược lại.) Tìm một chiến lược tổng hợp ý kiến chuyên gia sao cho tổng chi phí trong $T$ ngày là nhỏ nhất.

 

Trong quá trình dự đoán $T$ ngày, tổng chi phí của chuyên gia thứ $i$ là $\sum_{t=1}^T m_t[i]$. Mục tiêu của chúng ta là tìm một chiến lược sao cho chi phí cuối cùng gần với chi phí của chuyên gia giỏi nhất, i.e, chuyên gia có tổng chi phí $\sum_{t=1}^T m_t[i]$ nhỏ nhất.

So sánh với bài toán trong post trước, bài toán này có hai điểm khiến nó trở nên thú vị hơn:

  1. Tổng hợp ý kiến theo đa số không còn xác định trong bài toán này, vì giá trị dự đoán là một số thực.
  2. Ngay cả khi lấy trung bình dự đoán của các chuyên gia thì chi phí của dự đoán này chưa chắc đã là chi phí trung bình của các chuyên gia. Lý do là hàm chi phí và giá trị dự đoán có thể không phải tuyến tính.

Do hai điểm trên, rất khó để xác định chiến lược dự đoán tất định sẽ nên như thế nào. Chính vì vậy, ta sẽ sử dụng các chiến lược ngẫu nhiên trong bài này. Một chiến lược ngẫu nhiên cho bài toán dự đoán 0/1 đã được mô tả trong Theorem 4 của bài trước.

Trong bước dự đoán thứ $t$, bạn sẽ chọn ra một chuyên gia theo một phân bố xác suất $\mathbb{p}_t$, và sử dụng dự đoán của chuyên gia đó làm dự đoán của mình. Ta sẽ coi phân bố xác suất này như một vector có $n$ chiều. Tương tự, coi hàm chi phí $\mathbb{m}_t$ như một vector $n$ chiều với chiều thứ $i$ có giá trị $m_t[i]$ (chi phí tương ứng với dự đoán của chuyên gia thứ $i$). Theo chiến lược ngẫu nhiên này, chi phí kì vọng tại bước thứ $t$ là:

$\sum_{i=1}^n p_t[i]m_t[i] = \langle \mathbb{m}_t,\mathbb{p}_t \rangle \qquad (2)$

Ở đây ta kí hiệu $\langle \mathbb{x}, \mathbb{y} \rangle$ là tích vô hướng của hai vector $\mathbb{x}, \mathbb{y}$.

Chiến lược dự đoán ngẫu nhiên: Ban đầu mỗi chuyên gia có trọng số $1$ ($w_0[i] = 1$ for all $1\leq i \leq n$). Để dự đoán cho ngày $t+1$, bạn sẽ chọn ra một chuyên gia ngẫu nhiên theo phân bố của trọng số $\mathbb{p}_t$. Cụ thể, xác suất chuyên gia thứ $i$ được chọn là:

$p_t[i] = \frac{w_t[i]}{W_t}\qquad (3)$

trong đó $W_t = \sum_{i=1}w_t[i]$. Bạn sẽ lấy dự đoán của chuyên gia được chọn làm dự đoán của mình, với chi phí là $m_t[i] \in [-1,1]$.

Sau khi so sánh kết quả, bạn sẽ cập nhật lại trọng số của các chuyên gia theo chiến lược:

$w_{t+1}[i] = (1 - \epsilon \cdot m_t[i])w_t[i] \qquad (4)$

với $\epsilon$ < $1/2$.

 

Chú ý, trong chiến lược ngẫu nhiên, ta cập nhật lại trọng số của chuyên gia bất kể dự đoán của chuyên gia mang lại lợi nhuận hay không. Nếu chuyên gia dự đoán không tốt, chi phí $m_t[i] \geq 0$ và phép cập nhật sẽ giảm trọng số của chuyên gia. Nhưng nếu chuyên gia đó dự đoán tốt, $m_t[i]$ < $0$ thì trọng số của chuyên gia sẽ được tăng lên.

Theorem 5: Giả sử bạn chọn chuyên gia theo chiến lược ngẫu nhiên thì với mọi chuyên gia $i$, ta có:

$\sum_{t=1}^T\langle \mathbb{m}_t,\mathbb{p}_t \rangle \leq \sum_{t=1}^T m_t[i] + \epsilon \sum_{t=1}^T |m_t[i]| + \frac{\ln n}{\epsilon} \qquad (5) $

 

Đại lượng $\sum_{t=1}^T\langle \mathbb{m}_t,\mathbb{p}_t \rangle$ là chi phí kì vọng cuối cùng mà bạn phải trả trong vòng $T$ ngày, còn đại lượng $\sum_{t=1}^T m_t[i]$ là chi phí của chuyên gia thứ $i$.

Để hiểu kĩ hơn về các đại lượng trong phương trình $(5)$ thì ta cần so sánh với các con số thiết lập trong bài trước. Cụ thể, nếu $m_i[t] \in \{0,1\}$ như trong thiết lập của bài trước, thì $\sum_{t=1}^T m_t[i]$ chính là số lần chuyên gia thứ $i$ dự đoán sai. Như vậy, phương trình $(5)$ cho chúng ta kì vọng số lần dự đoán sai là không quá $(1+\epsilon) M + \frac{\ln n}{\epsilon}$ trong đó $M$ là số lần dự đoán sai của chuyên gia giỏi nhất. Ta thu được cận trong Theorem 4 của bài trước.

Chứng minh Theorem 5: Kĩ thuật chứng minh giống trong chứng minh Theorem 2. Ta có:

$\begin{array} {l} w_T[i] & = \prod_{m_t[i]\geq 0}(1-m_t[i]\epsilon) \prod_{m_t[i] \mbox{<} 0}(1-m_t[i]\epsilon) \\ &\geq (1+\epsilon)^{-\sum_{m_t[i] \mbox{<} 0}m_t[i]}(1-\epsilon)^{\sum_{m_t[i] \geq 0}m_t[i]}\qquad \mbox{by applying }(1) \end{array} \qquad (6)$

Ta sẽ tính $W_{t+1}$ từ $W_t$:

$\begin{array} {l} W_{t+1} & = \sum_{i} w_{t+1}[i] \\
&= \sum_{i} w_t[i](1 - m_t[i]\epsilon) \\
&\leq W_t - \epsilon \sum_{i} w_t[i]m_t[i]\\
&= W_t - \epsilon W_t \sum_{i} p_t[i]m_t[i] \\
&= W_t(1 - \epsilon \langle \mathbb{m}_t,\mathbb{p}_t \rangle)\\
&\leq W_t e^{-\epsilon \langle \mathbb{m}_t,\mathbb{p}_t \rangle} \qquad \mbox{by applying }(1)\end{array}$

Do đó, ta có:

$\begin{array} {l} W_{T} & \leq n\cdot e^{-\epsilon \sum_{t=1}^T \langle \mathbb{m}_t,\mathbb{p}_t \rangle}\end{array} \qquad (7)$

Do $w_T[i] \leq W_T$, từ (6) và (7), ta có:

$\begin{array}{l} -\ln(1+\epsilon)\sum_{m_t[i] \mbox{<} 0}m_t[i] + \ln(1-\epsilon)\sum_{m_t[i] \geq 0}m_t[i] &\leq -\epsilon\sum_{t=1}^T \langle \mathbb{m}_t,\mathbb{p}_t \rangle + \ln n \end{array} \qquad (8)$

Sắp xếp lại hai vế của (8) ta được:

$\begin{array} {l} \sum_{t=1}^T \langle \mathbb{m}_t,\mathbb{p}_t \rangle &\leq \frac{- \ln(1-\epsilon)}{\epsilon}\sum_{m_t[i] \geq 0}m_t[i] + \frac{\ln(1+\epsilon)}{\epsilon}\sum_{m_t[i] \mbox{<} 0}m_t[i] + \frac{\ln n}{\epsilon} \\
&\leq (1+\epsilon)\sum_{m_t[i] \geq 0}m_t[i] + (1-\epsilon)\sum_{m_t[i] \mbox{<} 0}m_t[i] + \frac{\ln n}{\epsilon} \quad \mbox{by applying }(1) \\
&\leq \sum_{t=1}^T m_t[i] + \epsilon \sum_{t=1}^T |m_t[i]| + \frac{\ln n}{\epsilon}\end{array} $


Từ Theorem 5, ta thu được hệ quả sau.

Corollary 1: Gọi $p^*$ là một phân bố bất kì giữa các chuyên gia. Giả sử bạn chọn chuyên gia theo chiến lược ngẫu nhiên thì với mọi chuyên gia $i$, ta có:

$\sum_{t=1}^T\langle \mathbb{m}_t,\mathbb{p}_t \rangle \leq \langle m_t,p^* \rangle + \epsilon\langle |m_t|,p^* \rangle+ \frac{\ln n}{\epsilon} \qquad (9) $

Ở đây, $|m_t|$ là một vector mà mỗi phần tử là giá trị tuyệt đối của phần tử tương ứng trong $m_t$.

 

Trong thiết kế giải thuật, Corollary 1 hay được dùng hơn. Mặc dù là một hệ quả, nhưng Corrollary 1 và Theorem 5 là tương đương (bài tập 3).

Lợi nhuận thay vì chi phí

Ta đảo ngược bài toán như sau: sau mỗi ngày $t$, dự đoán của chuyên gia $i$ mang về cho bạn một lợi nhuận (có thể âm) $m_t[i]$. Tìm một chiến lược tổng hợp ý kiến chuyên gia sao cho tổng lợi nhuận sau $T$ ngày là lớn nhất.

Ta có thể quy bài toán tối đa lợi nhuận về bài toán tối thiểu chi phí bằng cách đảo dấu của đầu vào. Ta có:

Theorem 6: Trong bài toán cực đại lợi nhuận, nếu các chuyên gia theo được chọn theo chiến lược ngẫu nhiên thì với mọi chuyên gia $i$, ta có:

$\sum_{t=1}^T\langle \mathbb{m}_t,\mathbb{p}_t \rangle \geq \sum_{t=1}^T m_t[i] - \epsilon \sum_{t=1}^T |m_t[i]| - \frac{\ln n}{\epsilon} \qquad (10) $

 

Đại lượng $\sum_{t=1}^T\langle \mathbb{m}_t,\mathbb{p}_t \rangle $ có thể được hiểu là tổng lợi nhuận kì vọng sau $T$ ngày.

Từ Theorem 6, ta cũng thu được một hệ quả giống Corollary 1, nhưng cho trường hợp cực đại lợi nhuận.

Corollary 2: Trong bài toán cực đại lợi nhuận, gọi $p^*$ là một phân bố bất kì giữa các chuyên gia. Giả sử bạn chọn chuyên gia theo chiến lược ngẫu nhiên thì với mọi chuyên gia $i$, ta có:

$\sum_{t=1}^T\langle \mathbb{m}_t,\mathbb{p}_t \rangle \geq \langle m_t,p^* \rangle - \epsilon\langle |m_t|,p^* \rangle- \frac{\ln n}{\epsilon} \qquad (11) $

Ở đây, $|m_t|$ là một vector mà mỗi phần tử là giá trị tuyệt đối của phần tử tương ứng trong $m_t$.

 

Giải thuật Hedge

Giải thuật này được đề xuất bởi Freund và Schapire [2]. Cũng trong cùng một công trình, Freund và Schapire đưa ra một ứng dụng của giải thuật này trong thiết kế thuật toán machine learning nổi tiếng Adaboost.

Theorem 7: Ta vẫn áp dụng chiến lược ngẫu nhiên ở trên. Tuy nhiên, sau mỗi ngày, các chuyên gia sẽ cập nhật lại trọng số theo hàm mũ. Cụ thể:

$w_{t+1}[i] = w_t[i]e^{- \epsilon \cdot m_t[i]} \qquad (12)$

Với mọi chuyên gia $i$, ta có:

$\sum_{t=1}^T\langle \mathbb{m}_t,\mathbb{p}_t \rangle \leq \sum_{t=1}^T m_t[i] + \epsilon \sum_{t=1}^T \langle (\mathbb{m}_t)^2,\mathbb{p}_t \rangle + \frac{\ln n}{\epsilon} \qquad (13) $

Trong đó $(\mathbb{m}_t)^2$ là một vector thu được bằng cách bình phương theo từng phần tử của vector $\mathbb{m}_t$.

 

Ta gọi cách cập nhật trong số này là giải thuật Hedge. Chứng minh Theorem 7 rất giống chứng minh Theorem 5. Chi tiết chứng minh sẽ được hướng dẫn trong bài tập 2.

Trường hợp chi phí trong đoạn $[-\rho, \rho]$

Trong trường hợp chi phí $m_t[i] \in [-\rho, \rho]$ ($\rho \geq 1$) với mọi $i, t$ thì ta áp dụng chuẩn hóa chi phí về đoạn $[-1,1]$. Cụ thể, đặt $m_t[i]' = m_t[i]/\rho$. Áp dụng Theorem 5 cho hàm chi phí $m'_t$, ta có:

$\sum_{t=1}^T\langle \mathbb{m}_t/\rho,\mathbb{p}_t \rangle \leq \sum_{t=1}^T m_t[i]/\rho + \epsilon \sum_{t=1}^T |m_t[i]|/\rho + \frac{\ln n}{\epsilon} \qquad (14) $

Từ $(14)$ ta suy ra:

Theorem 8: Áp dụng chiến lược ngẫu nhiên với hàm chi phí $m_t[i]\in [-\rho, \rho]$ ($\rho \geq 1$), với mọi chuyên gia $i$, ta có:

$\sum_{t=1}^T\langle \mathbb{m}_t,\mathbb{p}_t \rangle \leq \sum_{t=1}^T m_t[i] + \epsilon \sum_{t=1}^T |m_t[i]| + \frac{\rho\cdot\ln n}{\epsilon} \qquad (15) $

 

Tham khảo

[1] S. Arora and E. Hazan and S. Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing 8.1 (2012): 121-164.
[2] Y. Freund and R. E. Schapire. A Desicion-theoretic Generalization of On-line Learning and an Application to Boosting. European Conference on Computational Learning Theory. Springer, Berlin, Heidelberg, 1995.
[3] A. Gupta. The Multiplicative Weights Algorithm. Lecture Notes, CMU. Accessed 01/05/2018.

Bài tập

Bài tập 1: Chứng minh các bất đẳng thức trong (1).

Bài tập 2: Trong bài này, ta sẽ tìm hiểu cách chứng minh Theorem 7.

  1. Chứng minh rằng $W_{t+1} \leq W_t(1 - \epsilon \langle \mathbb{m}_t,\mathbb{p}_t \rangle + \epsilon^2 \langle (\mathbb{m}_t)^2,\mathbb{p}_t \rangle )$, sử dụng bất đẳng thức cuối cùng trong (1).
  2. Từ (a) suy ra $W_T \leq n e^{- \epsilon \langle \mathbb{m}_t,\mathbb{p}_t \rangle + \epsilon^2 \langle (\mathbb{m}_t)^2,\mathbb{p}_t \rangle }$, sau đó áp dụng $w_T[i] \leq W_T$ để chứng minh (9).

Bài tập 3: Giả sử Corollary 1 đúng, chứng minh Theorem 1.

Facebook Comments

Tags: , , , ,

Reply

Your email address will not be published. Required fields are marked *