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

January 5, 2018 in Regular | No comments

Trong chuỗi bài này mình sẽ giới thiệu phương pháp multiplicative weight update (viết tắt là MWU). Phương pháp này có rất nhiều ứng dụng trong các lĩnh vực khác nhau như Machine Learning (cụ thể là Adaboost), tối ưu, khoa học máy tính, lý thuyết game v.v. Chuỗi bài chủ yếu dựa trên survey của Arora, Hazan và Kale [1] và note của Gupta [2]. Về lịch sử của phương pháp này, bạn đọc có thể xem trên wikipedia.

Bài toán tham khảo chuyên gia

Bài toán như sau:

Tham khảo chuyên gia: Bạn là một người đầu tư chứng khoán và bạn muốn dự đoán xem trong ngày tiếp theo, giá của chứng khoán là lên hay xuống. Bạn bỏ tiền ra thuê $n$ chuyên gia chứng khoán. Mỗi người sẽ cho bạn một dự đoán là 1 hoặc 0 (1 tương ứng với dự đoán chứng khoán sẽ lên trong ngày tiếp theo và 0 tương ứng với dự đoán chứng khoán sẽ xuống trong ngày tiếp theo.). Giả sử bạn chỉ thuê các chuyên gia đó trong vòng $T$ ngày.

Một chuyên gia được gọi là giỏi nhất nếu trong vòng $T$ ngày, chuyên gia đó dự đoán sai ít nhất. Đương nhiên là bạn muốn nghe theo chuyên gia giỏi nhất, nhưng bạn không biết ai là giỏi nhất trong số $n$ chuyên gia này (cho đến khi nhìn vào kết quả dự đoán của các chuyên gia sau $T$ ngày). Hãy đề xuất một chiến lược tổng hợp ý kiến các chuyên gia sao cho số lần bạn dự đoán sai là ít nhất.

 

Remark: Khi dự đoán cho ngày tiếp theo, bạn có thể tùy ý sử dụng kết quả của những ngày trước đó để tổng hợp ý kiến của các chuyên gia.

Trường hợp có một chuyên gia hoàn hảo: Một chuyên gia được gọi là hoàn hảo nếu như trong vòng $T$ ngày, chuyên gia ấy không đoán sai lần nào. Bạn có thể làm như sau để đảm bảo số lần bạn đoán sai không vượt quá $\log_2(n)$: luôn dự đoán theo số đông (nếu đúng một nửa dự đoán 0 và một nửa dự đoán 1 thì chọn tùy ý một trong 2.). Nếu ngày hôm sau kết quả dự đoán của số đông là sai thì loại những người đoán sai ra khỏi danh sách chuyên gia.

Không khó để thấy rằng, sau tối đa $\log_2(n)$ lần sai thì chỉ còn lại đúng một chuyên gia trong danh sách, và chuyên gia này là chuyên gia hoàn hảo. Như vậy, trong $T$ ngày thì bạn chỉ sai tối đa $\log_2(n)$ lần.

Remark: $\log_2(n)$ thự sự là đáng ngạc nhiên, vì nếu bạn có 100 chuyên gia và bạn thuê họ trong 1000 ngày thì bạn chỉ sai tối đa 7 lần, giả sử có một chuyên gia hoàn hảo.

Trường hợp đặc biệt trên gợi ý cho chúng ta một cách giải quyết bài toán kể cả khi không có chuyên gia hoàn hảo. Giả sử chuyên gia giỏi nhất đoán sai $M$ lần trong $T$ ngày. Ta sẽ sử dụng lại chiến lược trong trường hợp đặc biệt ở trên. Nếu thiểu số đoán sai thì ta loại thiểu số đó ra khỏi danh sách các chuyên gia. Tuy nhiên, khi còn lại đúng một chuyên gia mà chuyên gia này cũng đoán sai trong ngày tiếp theo thì ta sẽ khởi động lại, i.e, đưa $n$ chuyên gia trở lại danh sách và tiếp tục phép dự đoán. Ta gọi chiến lược này là chiến lược cứng.

Theorem 1: Số lần dự đoán sai tối đa là $M(\log_2(n)+1)$ nếu bạn áp dụng chiến lược cứng, trong đó $M$ là số lần dự đoán sai của chuyên gia giỏi nhất.

 
Chứng minh: Ta gọi mỗi lần danh sách các chuyên gia trở thành rỗng là kết thúc một vòng dự đoán (a prediction round). Dễ thấy trong mỗi vòng dự đoán, số lần đoán sai tối đa là $\log_2(n)$, theo như phân tích ở trên. Trong mỗi vòng dự đoán, chuyên gia giỏi nhất sẽ sai ít nhất một lần. Do chuyên gia này dự đoán sai không quá $M$ lần, nên số vòng dự đoán là $M$. Sau vòng dự đoán cuối cùng, chuyên gia giỏi nhất trở thành hoàn hảo, và do đó, bạn chỉ sai thêm không quá $\log_2(n)$ lần nữa. Như vậy, tổng số lần mà bạn dự đoán sai không quá $M(\log_2(n)+1)$.

Mặc dù chiến lược cứng cho bạn một cận khá đẹp về số lần sai tối đa, nhưng cận này gần như không hữu dụng. Trở lại ví dụ trên, $n = 100, T = 1000$, chuyên gia giỏi nhất dự đoán đúng 90% (nghĩa là sai $100$ lần), thì số lần sai tối 766 lần. Nói cách khác, độ chính xác của bạn không quá $24\%$!?!

Tuy nhiên, có chiến lược mà số lần sai tối đa là $O(M + \log_2(n))$ mà ta sẽ tìm hiểu trong phần tiếp theo đây.

Chiến lược lấy ý kiến đa số theo trọng số

Ý tưởng của chiến lược lấy ý kiến đa số theo trọng số (multiplicative weighted majority) là gán cho mỗi chuyên gia một trọng số và ta sẽ giảm trọng số của các chuyên gia sau mỗi lần dự đoán sai. Ban đầu mỗi chuyên gia sẽ được coi như nhau và được cấp trọng số $1$. Chiến lược dự đoán được minh họa bằng giả mã sau:

MultiplicativeWeightMajority($n,T$):
    $w_0[1,\ldots,n] \leftarrow [1,1,\ldots, 1]$
    for $t = 0$ to $T$
        $W_t \leftarrow \sum_{i=1}^n w_t[i]$
        for $i \leftarrow 1$ to $n$
            $I[i] \leftarrow $ the prediction of the i-th expert
        $c \leftarrow \sum_{i=1}^n \frac{w_t[i]}{W_t} I[i]$
        if $c \geq 1/2$
            you predict $1$
        else
            you predict $0$
    for each wrong expert $i$
        $w_{t+1}[i] \leftarrow \frac{1}{2}w_t[i]$
    for each correct expert $i$
        $w_{t+1}[i] \leftarrow w_t[i]$

 

Giả sử trong ngày thứ $t$, chuyên gia thứ $i$ có trọng số $w_t[i]$. Giá trị $W_t$ trong giả mã trên là tổng trọng số của các chuyên gia tại ngày thứ $t$. $I[i]$ là dự đoán của chuyên gia thứ $i$. Chú ý $I[i] \in \{0,1\}$. Giá trị $c$ chính là trung bình dự đoán của các chuyên gia có kết hợp trong số. Nếu $c \geq 1/2$, có nghĩa là hơn "một nửa" chuyên gia dự đoán $1$, thì bạn cũng dự đoán 1. Ngược lại bạn sẽ dự đoán 0.

Sau khi dự đoán, bạn sẽ quan sát kết quả của ngày tiếp theo. Bạn sẽ giảm trọng số của các chuyên gia dự đoán sai đi một nửa, và giữ nguyên trọng số của các chuyên gia có dự đoán đúng.

Ta có thể coi chiến lược lấy ý kiên chuyên gia này là chiến lược mềm, vì mỗi lần các chuyên gia đoán sai, ta sẽ không loại họ ra khỏi danh sách chuyên gia mà chỉ giảm trọng số của họ. Chuyên gia nào càng tệ thì trọng số bị giảm càng nhiều, do đó ảnh hưởng của chuyên gia đó sẽ càng ít trong các vòng sau đó. Về mặt trực quan thì chiến lược này có vẻ tốt, nhưng để biết nó có sự thự tốt hơn chiến lược cứng hơn thì cần phân tích toán học tỉ mỉ hơn.

Theorem 2: Nếu sử dụng chiến lược mềm thì số lần bạn dự đoán sai tối đa là $2.41(M + \log_2 n)$, trong đó $M$ là số lần dự đoán sai của chuyên gia giỏi nhất.

 
Chứng minh: Theo mô tả của thủ tục MultiplicativeWeightMajority mỗi lần một chuyên gia dự đoán sai, trọng số của chuyên gia đó sẽ bị giảm đi một nửa.

Trước hết ta so sánh $W_{t+1}$ và $W_t$. Do trọng số của các chuyên gia luôn giảm, ta có $W_{t+1} \leq W_t$. Tuy nhiên, nếu bạn đoán sai ở ngày thứ $t$, tổng trọng số của các chuyên gia sai bị giảm đi một nửa. Do tổng trọng số của các chuyên gia sai ít nhất là 1/2, ta có $W_{t+1} \leq (3/4)W_t$.

Do đó, $W_T$ cuối cùng không quá $(3/4)^{X}n$ trong đó $X$ là số lần bạn dự đoán sai ($W_0 = n$).

Do chuyên gia giỏi nhất sai $M$ lần và mỗi lần sai trọng số của chuyên gia này giảm đi một nửa, trọng số của chuyên gia này trong ngày thứ $T$ là $(1/2)^M$. Ta có bất phương trình:

$(1/2)^M \leq (3/4)^X n \qquad (2)$

Giải bất phương trình $(2)$, ta thu được $X \leq 2.41 (M + \log_2 n)$ (bạn đọc tự kiểm chứng).

Trở lại ví dụ ban đầu $T = 1000, n = 100$. Giả sử chuyên gia giỏi nhất có độ chính xác 90% thì số lần bạn đoán sai sử dụng chiến lược mềm không quá 258, tức là độ chính xác của bạn khoảng $75\%$. Thực sự là chiến lược không quá tệ. Nên nhớ đây chỉ là cận cho trường hợp xấu nhất.

Bạn có thể hỏi tại sao lại chọn giảm trọng số đi $1/2$? Thực ra không nhất thiết; con số $1/2$ chỉ để phép phân tích nhìn đẹp hơn thôi. Có rất nhiều chiến lược giảm trọng số, mà tùy ngữ cảnh hoặc biến thể của bài toán mà ta chọn một chiến lược cho phù hợp. Mình sẽ cung cấp vài ví dụ với các chiến lược khác nhau trong loạt bài này.

Tiếp theo đây ta xét một chiến lược khác.

Theorem 3: Xét chiên lược giảm trọng số sau: mỗi lần bạn dự đoán sai, bạn sẽ giảm trọng số của các chuyên gia dự đoán sai theo công thức sau:

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

Trong đó, $\epsilon$ là một hằng số tùy ý nhỏ hơn hoặc bằng $1/2$. Nếu sự dụng chiến lược này, tổng số lần dự đoán sai của bạn là không quá:

$2(1+\epsilon)M + \frac{2\ln n}{\epsilon} \qquad (4)$

Ở đây, $M$ là số lần dự đoán sai của chuyên gia giỏi nhất.

 

Chi tiết chứng minh Theorem 2 coi như bài tập cho bạn đọc (bài tập 1)

Sử dụng ngẫu nhiên, ta còn có thể loại bỏ được số 2 trong phương trình (4). Cụ thể:

Theorem 4: (chiến lược ngẫu nhiên) Xét chiến lược ngẫu nhiên sau: mỗi lần dự đoán, thay vì tổng hợp ý kiến các chuyên gia, bạn chọ ra ngẫu nhiên một chuyên gia và lấy dự đoán của chuyên gia được chọn làm dự đoán cho bạn. Các chuyên gia sẽ được chọn theo phân bố của trọng số tương ứng. 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 (5)$

Sau mỗi lần dự đoán, trọng số của các chuyên gia dự đoán sai sẽ bị giảm theo công thức sau:

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

Trong đó, $\epsilon$ là một hằng số tùy ý nhỏ hơn hoặc bằng $1/2$. Nếu sự dụng chiến lược này, kì vọng số lần dự đoán sai của bạn là không quá:

$(1+\epsilon)M + \frac{\ln n}{\epsilon} \qquad (8)$

Ở đây, $M$ là số lần dự đoán sai của chuyên gia giỏi nhất.

 
Trong bài tiếp theo, mình sẽ chứng minh trường hợp tổng quát hơn của Thoerem 4. Kĩ thuật chứng minh định lý này cũng giống như chứng minh Theorem 2. Mình khuyến khích bạn đọc thử tự chứng minh.

Xét lại ví dụ $T = 1000, n = 100$. Giả sử chuyên gia giỏi nhất có độ chính xác 90%, chọn $\epsilon = 0.1$ thì chiến lược ngẫu nhiên cho số lần dự đoán sai kì vọng là 157, hay độ chính xác kì vọng của chiến lược ngẫu nhiên là $85\%$.

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] 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 Theorem 3, sử dụng ý tưởng trong chứng minh Theorem 2.

  1. Chứng minh rằng $W_{t+1} \leq (1 - \epsilon/2)W_t$.
  2. Sử dụng kết quả phần a, chứng minh Theorem 3. Bạn có thể sử dụng công thức xấp xỉ $-\ln(1-x) \sim x + x^2$ để chứng minh được đơn giản hơn.
Facebook Comments

Tags: , , ,

Reply

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