HM6 — Độ phức tạp Rademacher

HM5: Mô hình giả thuyết không nhất quán và định lý hội tụ đều Vapnik-Chervonenkis
HM7: AdaBoost

Trong bài HM 5, ta đã giới thiệu mô hình giả thuyết không nhất quán và chứng minh định lý hội tụ đều của Vapnik và Chervonenkis. Đây là một trong những định lý cơ bản nhất của lý thuyết học máy thống kê. Ta gọi tắt nó là định lý VC. Định lý VC chặn trên lỗi tổng quát hóa bằng lỗi thực nghiệm và độ phức tạp VC (hay VC dimension) của lớp giả thuyết. Trong bài này, ta chứng minh một kết quả tổng quát hơn định lý VC. Ta sẽ chặn trên lỗi tổng quát hóa bằng lỗi thực nghiệm và cái gọi là độ phức tạp Rademacher. Định lý VC là một hệ quả trực tiếp của chặn trên dùng độ phức tạp Rademacher này. Chứng minh kết quả này cũng trực quan hơn rất nhiều so với chứng minh định lý VC trong bài trước. Bạn có thể quên luôn chứng minh của bài trước đi. Ngoài ra, ta sẽ dùng kết quả của bài này để phân tích thuật toán AdaBoost thảo luận trong bài tới. Phần lớn bài này viết theo bài giảng số 3 của Mehryar Mohri ở NYU.

1. Độ phức tạp Rademacher

Gọi ${\mathcal G}$ là một họ các hàm từ một miền ${\mathcal Z}$ nào đó vào đoạn ${[a,b]}$ . Trong các ứng dụng thì ${\mathcal Z = \Omega \times \{0,1\}}$ hay ${\mathcal Z = \Omega \times \{-1,1\}}$ . Gọi ${\mathcal D}$ là một phân bố xác suất trên miền ${\mathcal Z}$ . Phân bố này sẽ được hiểu ngầm trong các phát biểu xác suất dưới đây, để tránh ký hiệu lằng nhằng quá.

Gọi ${S}$ là một tập ${m}$ phần tử bất kỳ của ${\mathcal Z}$ . Độ phức tạp Rademacher thực nghiệm (của ${\mathcal G}$ , tính tương đối theo ${S}$ ) được định nghĩa là

$\displaystyle \hat{\mathcal R}_S(\mathcal G) = \mathop{\mathbf E}_\sigma \left[ \sup_{g \in \mathcal G} \frac 1 m \sum_{i=1}^m \sigma_ig(z_i) \ | \ S = (z_1, \dots, z_m) \right]$

Trong đó, ${\sigma = (\sigma_1,\dots, \sigma_m)}$ là một vector của các biến Rademacher: ${\sigma_i = \pm 1}$ với xác suất ${1/2}$ .

Nếu ${\mathcal G}$ là họ các hàm phân loại (classifiers), mỗi hàm lấy giá trị ${\pm 1}$ , thì độ phức tạp Rademacher thực nghiệm có thể hiểu nôm na như sau. Ta gán giá trị ${\pm 1}$ ngẫu nhiên vào ${m}$ điểm của ${S}$ . Rồi tính trung bình xem cái hàm phân loại tốt nhất của ${\mathcal G}$ phân loại đúng được bao nhiêu. Ví dụ, nếu ${\mathcal G}$ là một tập các hàm rất hùng mạnh, với bất kỳ cách gán ${\pm 1}$ nào vào ${S}$ cũng tồn tại hàm ${g}$ gán nhãn chính xác, thì độ phức tạp Rademacher bằng ${1}$ . Ta chia độ phức tạp cho ${m}$ là để “bình thường hóa” số đo này cho nó không phụ thuộc vào số mẫu.

Độ phức tạp Rademacher của ${\mathcal G}$ là trị kỳ vọng của độ phức tạp Rademacher thực nghiệm:

$\displaystyle \mathcal R_m(\mathcal G) = \mathop{\mathbf E}_{S \sim \mathcal D^m} \left[ \hat{\mathcal R}_S(\mathcal G) \right].$

Quan sát đầu tiên của ta liên hệ độ phức tạp Rademacher của một bộ hàm phân loại và bộ hàm mất mát (loss functions) tương ứng. Cụ thể hơn, gọi ${\mathcal H}$ là một bộ các hàm ${\Omega \rightarrow \{-1,1\}}$ . Mỗi hàm của ${\mathcal H}$ là một hàm phân loại nhị phân. Từ giờ trở đi ta dùng các nhãn ${\{-1,1\}}$ thay vì nhãn ${\{0,1\}}$ cho tiện về mặt toán học. Đặt ${\mathcal Z = \Omega \times \{-1,1\}}$ . Như vậy các phần tử ${z \in \mathcal Z}$ có dạng ${z = (\mathbf x, y)}$ với ${\mathbf x \in \Omega}$ và ${y \in \{-1,1\}}$ . Xét một phân bố ${\mathcal D}$ trên ${\mathcal Z}$ tùy hỉ. Định nghĩa một họ hàm ${\mathcal G}$ từ ${\mathcal Z}$ vào ${[0,1]}$ như sau. Với mỗi ${h \in \mathcal H}$ , định nghĩa ${g(\mathbf x, y) = \mathbf 1_{h(\mathbf x) \neq y}}$ .

Bổ đề 1 Ta có
$\displaystyle \begin{array}{rcl} \widehat{\textnormal{err}}_S(h) &=& \frac 1 m \sum_{i=1}^m g(z_i) \\ \textnormal{err}(h) &=& \mathop{\mathbf E}[g(z)]\\ \hat{\mathcal R}_S(\mathcal G) &=& \frac 1 2 \hat{\mathcal R}_S(\mathcal H)\\ \mathcal R_m(\mathcal G) &=& \frac 1 2 \mathcal R_m(\mathcal H). \end{array}$

Chứng minh: Hai đẳng thức đầu tiên là định nghĩa. Đẳng thức thứ tư là hệ quả trực tiếp của đẳng thức thứ ba. Ta chứng minh đẳng thức thứ ba.

$\displaystyle \begin{array}{rcl} \hat{\mathcal R}_S(\mathcal G) &=& \mathop{\mathbf E}_\sigma\left[ \sup_{h\in \mathcal H} \frac 1 m \sum_{i=1}^m \sigma_i\mathbf 1_{h(\mathbf x_i) \neq y_i} \ | \ S = (z_1,\dots, z_m) \right]\\ &=& \mathop{\mathbf E}_\sigma\left[ \sup_{h\in \mathcal H} \frac 1 m \sum_{i=1}^m \frac 1 2 \sigma_i(1-h(\mathbf x_i) y_i) \ | \ S = (z_1,\dots, z_m) \right]\\ &=& \frac 1 2 \mathop{\mathbf E}_\sigma\left[ \frac 1 m \sum_{i=1}^m \sigma_i + \sup_{h\in \mathcal H} \frac 1 m \sum_{i=1}^m (-\sigma_iy_i)h(\mathbf x_i) \ | \ S = (z_1,\dots, z_m) \right]\\ &=& \frac 1 2 \mathop{\mathbf E}_\sigma\left[ \sup_{h\in \mathcal H} \frac 1 m \sum_{i=1}^m \sigma_ih(\mathbf x_i) \ | \ S = (z_1,\dots, z_m) \right]\\ &=& \frac 1 2 \hat{\mathcal R}_S(\mathcal H) \end{array}$

Đẳng thức thứ tư ta dùng quan sát đơn giản là ${(-\sigma_iy_i)}$ có phân bố giống hệt ${\sigma_i}$ và các ${\sigma_i}$ độc lập nhau. $\Box$

Độ phức tạp Rademacher liên quan đến VC-dimension như thế nào? Massart hồi 2000 cho ta câu trả lời. Ta sẽ chứng minh bổ đề sau ở cuối bài, sau khi đã làm quen hơn với độ phức tạp Rademacher.

Bổ đề 2 Gọi ${\mathcal H}$ là một bộ các hàm số vào ${\{-1,1\}}$ . Với ${S}$ là một tập ${m}$ mẫu bất kỳ, ta có
$\displaystyle \hat{\mathcal R}_S(\mathcal H) \leq \sqrt{\frac{2\log \Pi_{\mathcal H}(S)}{m}}.$

Và do đó,
$\displaystyle {\mathcal R}_m(\mathcal H) \leq \sqrt{\frac{2\log \Pi_{\mathcal H}(m)}{m}} \leq \sqrt{\frac{2d\log(me/d)}{m}}.$

Trong đó ${d}$ là VC-dimension của ${\mathcal H}$ .

Dùng cái gọi là độ phức tạp Gaussian, Bartlett và Mendelson chứng minh một chặn khác chặt hơn nữa: ${\hat{\mathcal R}_S(\mathcal H) = O(\sqrt{d/n})}$ , và vì thế ${\mathcal R_m(\mathcal H) = O(\sqrt{d/n})}$ . Ta sẽ quay lại với Gaussian complexity vào dịp khác.

2. Các chặn cho độ phức tạp Rademacher

Kết quả chính của đề mục này là từ một bài báo của Koltchinskii và Panchenko hồi năm 2002. Các bác cựu Liên Xô ngố rất giỏi mấy trò này. Dùng Liên Xô ngố chứ không phải Nga ngố là vì bác Vladimir Koltchinskii tốt nghiệp đại học Kiev. Còn Dmitry Panchenko là học trò của Koltchinskii.

Để chứng minh kết quả chính này ta cần bất đẳng thức McDiarmid của Colin McDiarmid. BĐT này khá dễ nhớ và dễ dùng.

Định lý 3 (BĐT McDiarmid) Xét ${m}$ biến ngẫu nhiên độc lập ${X_1, \dots, X_m}$ trên một miền ${\mathcal X}$ nào đó, và một hàm số ${f: \mathcal X^m \rightarrow \mathbb R}$ . Hàm số ${f}$ thỏa điều kiện là thay đổi tọa độ thứ ${i}$ thì chỉ thay đổi giá trị của ${f}$ nhiều nhất là ${c_i}$ . Cụ thể hơn, với mọi ${i}$ , ${x_1,\dots, x_m, x'_i}$ ta có
$\displaystyle |f(x_1,\dots,x_{i-1},x_i,x_{i+1},\dots, x_m) - f(x_1,\dots,x_{i-1},x'_i,x_{i+1},\dots, x_m)| \leq c_i.$

Thì với mọi ${\epsilon >0}$ ta có
$\displaystyle \text{Prob}[ f - \mathop{\mathbf E}[f] \geq \epsilon ] \leq \exp\left(\frac{-2\epsilon^2}{\sum_{i=1}^mc_i^2}\right),$

và
$\displaystyle \text{Prob}[ f - \mathop{\mathbf E}[f] \leq - \epsilon ] \leq \exp\left(\frac{-2\epsilon^2}{\sum_{i=1}^mc_i^2}\right).$

Định lý 4 (Koltchinskii-Panchenko) Gọi ${\mathcal G}$ là một bộ các hàm từ miền ${\mathcal Z}$ vào ${[0,1]}$ . Với mọi ${\delta>0}$ , với xác suất ít nhất là ${1-\delta}$ bất đẳng thức sau đây đúng với mọi ${g \in \mathcal G}$ ,
$\displaystyle \mathop{\mathbf E}[g(z)] \leq \frac 1 m \sum_{i=1}^m g(z_i) + 2\mathcal{R}_m(\mathcal G) + \sqrt{\frac{\log\frac 1 \delta}{2m}}. \ \ \ \ \ (1)$

Với mọi ${\delta>0}$ , với xác suất ít nhất là ${1-\delta}$ bất đẳng thức sau đây đúng với mọi ${g \in \mathcal G}$ ,
$\displaystyle \mathop{\mathbf E}[g(z)] \leq \frac 1 m \sum_{i=1}^m g(z_i) + 2\hat{\mathcal R}_S(\mathcal G) + 3 \sqrt{\frac{\log\frac 2 \delta}{2m}}. \ \ \ \ \ (2)$

Chứng minh: Để đơn giản hóa ký hiệu, ta định nghĩa

$\displaystyle \begin{array}{rcl} \mathop{\mathbf E}[g] &=& \mathop{\mathbf E}[g(z)] \\ \widehat{\mathop{\mathbf E}}_S[g] &=& \frac 1 m \sum_{i=1}^m g(z_i)\\ \Phi(S) &=& \sup_{g \in \mathcal G} \mathop{\mathbf E}[g] - \widehat{\mathop{\mathbf E}}_S[g]. \end{array}$

Để chứng minh (1), ta cần chứng minh rằng ${\Phi(S) \leq 2\mathcal{R}_m(\mathcal G) + \sqrt{\frac{\log\frac 1 \delta}{2m}}}$ với xác suất cao. Để chứng minh điều này thì ta chứng minh ${\mathop{\mathbf E}_S[\Phi(S)] \leq 2\mathcal{R}_m(\mathcal G)}$ , sau đó áp dụng bất đẳng thức McDiarmid vào hàm số ${f = \Phi}$ . Nói chung, chìa khóa của toàn bộ định lý là chứng minh quan hệ ${\mathop{\mathbf E}_S[\Phi(S)] \leq 2\mathcal{R}_m(\mathcal G)}$ bằng kỹ thuật “đối xứng hóa”.

Lưu ý rằng ${\mathop{\mathbf E}[g] = \mathop{\mathbf E}_{S'}\left[ \widehat{\mathop{\mathbf E}}_{S'}[g] \right].}$ Ta có

$\displaystyle \begin{array}{rcl} \mathop{\mathbf E}_S[\Phi(S)] &=& \mathop{\mathbf E}_S \left[ \sup_{g \in \mathcal G} \mathop{\mathbf E}[g] - \widehat{\mathop{\mathbf E}}_S[g] \right]\\ &=& \mathop{\mathbf E}_S \left[ \sup_{g \in \mathcal G} \mathop{\mathbf E}_{S'} \left[\widehat{\mathop{\mathbf E}}_{S'}[g] - \widehat{\mathop{\mathbf E}}_S[g] \right] \right]\\ \text{(Jensen)} &\leq & \mathop{\mathbf E}_S \left[ \mathop{\mathbf E}_{S'} \left[ \sup_{g \in \mathcal G} \widehat{\mathop{\mathbf E}}_{S'}[g] - \widehat{\mathop{\mathbf E}}_S[g] \right] \right]\\ &=& \mathop{\mathbf E}_{S,S'} \left[ \sup_{g \in \mathcal G} \frac 1 m \sum_{i=1}^m (g(z'_i) - g(z_i)) \right]\\ &=& \mathop{\mathbf E}_{S,S',\sigma} \left[ \sup_{g \in \mathcal G} \frac 1 m \sum_{i=1}^m \sigma_i(g(z'_i) - g(z_i)) \right]\\ &\leq& \mathop{\mathbf E}_{S',\sigma} \left[ \sup_{g \in \mathcal G} \frac 1 m \sum_{i=1}^m \sigma_i g(z'_i) \right]+ \mathop{\mathbf E}_{S,\sigma} \left[ \sup_{g \in \mathcal G} \frac 1 m \sum_{i=1}^m -\sigma_i g(z_i) \right]\\ &=& 2 \mathcal R_m(\mathcal G). \end{array}$

Đẳng thức ở dòng thứ ${5}$ là một dạng “đối xứng hóa” (symmetrization) đơn giản: sau khi lấy các mẫu ${z'_i, z_i}$ ta có thể hoán chuyển ${z'_i}$ và ${z_i}$ từ ${S'}$ sang ${S}$ và ngược lại. Do ${S'}$ và ${S}$ là các mẫu độc lập, sự hoán chuyển này không thay đổi phân bố của chúng.

Bây giờ ta áp dụng bất đẳng thức McDiarmid vào hàm ${\Phi}$ . Khi thay một điểm ${z_i \in S}$ bằng ${z'_i}$ nào đó, giá trị của hàm ${\Phi(S)}$ thay đổi nhiều nhất là ${1/m}$ . Do đó, từ bất đẳng thức McDiarmid ta có

$\displaystyle \Phi(S) \leq \mathop{\mathbf E}_{S}[\Phi(S)] + \sqrt{\frac{\log \frac 1 \delta}{2m}}$

với xác suất ít nhất là ${1-\delta}$ . Đó là chứng minh (1).

Để chứng minh (2) thì ta lại áp dụng McDiarmid một lần nữa. Lần này là với hàm số ${\hat{\mathcal R}_S(\mathcal G)}$ . Trước hết, McDiarmid như lần 1 cho ta

$\displaystyle \Phi(S) \leq \mathop{\mathbf E}_{S}[\Phi(S)] + \sqrt{\frac{\log \frac 2 \delta}{2m}} \ \ \ \ \ (3)$

với xác suất ít nhất ${1-\delta/2}$ . Rồi từ bất đẳng thức vừa chứng minh, ta có ${\mathop{\mathbf E}_{S}[\Phi(S)] \leq 2{\mathcal R}_m(\mathcal G) = 2\mathop{\mathbf E}_S[ \hat{\mathcal R}_S(\mathcal G) ]}$ . Khi thay ${S}$ chỉ một mẫu thì ${\hat{\mathcal R}_S(\mathcal G)}$ thay đổi nhiều nhất là ${1/m}$ . Do đó, với xác suất ít nhất ${1-\delta/2}$ ta có

$\displaystyle \hat{\mathcal R}_m(\mathcal G) \leq \hat{\mathcal R}_S(\mathcal G) + \sqrt{\frac{\log \frac 2 \delta}{2m}}. \ \ \ \ \ (4)$

Từ (3) và (4) ta có (2). $\Box$

3. Một số hệ quả của chặn độ phức tạp Rademacher

Từ Bổ đề 1 và Định lý 4, ta có hệ quả sau đây.

Hệ quả 5 Gọi ${\mathcal H}$ là một họ các hàm phân lớp từ ${\Omega}$ vào ${\{-1,1\}}$ . Thì với mọi ${\delta>0}$ , với xác suất ít nhất ${1-\delta}$ ta có
$\displaystyle \begin{array}{rcl} \text{err}(h) &\leq&\widehat{\text{err}}(h) + \mathcal{R}_m(\mathcal H) + \sqrt{\frac{\log \frac 1 \delta}{2m}}\\ \text{err}(h) &\leq&\widehat{\text{err}}(h) + \widehat{ \mathcal R}_S(\mathcal H) + 3 \sqrt{\frac{\log \frac 1 \delta}{2m}}. \end{array}$

Chặn thứ 2 chỉ phụ thuộc vào dữ liệu, do đó có khả năng hữu dụng trong việc chọn mô hình phân lớp, giúp giải quyết vấn đề model selection. Vấn đề là làm thế nào để tính độ phức tạp Rademacher một cách hiệu quả, chưa nói đến việc chọn một hàm ${h\in \mathcal H}$ với ${\sum_i \sigma_ih(\mathbf x_i)}$ lớn nhất. Bài này khó tương đương với bài toán tối thiểu hóa lỗi thực nghiệm (ERM), và nói chung là ${\mathbf{NP}}$ -khó. Câu hỏi tự nhiên là, có một “độ phức tạp” nào hữu dụng và dễ tính hơn không?

Từ hệ quả trên và Bổ đề 2 ta có định lý VC. Vậy ta chứnh minh bổ đề 2. Nhưng ta sẽ chứng minh một bổ đề còn tổng quát hơn Bổ đề 2, gọi là Bổ đề Massart. Mấy cái mẹo dùng trong chứng minh bổ đề Massart rất phổ dụng trong các chứng minh hiện tượng tập trung (concentration inequalities).

Bổ đề 6 (Bổ đề Massart) Xét một tập con hữu hạn ${A \subset \mathbb R^m}$ , với ${L = \max_{\mathbf x \in A} \|\mathbf x \|_2}$ . Ta có
$\displaystyle \mathop{\mathbf E}_\sigma\left[ \frac 1 m \sup_{\mathbf x \in A} \sum_{i=1}^m \sigma_ix_i \right] \leq \frac{L\sqrt{2\log|A|}}{m}.$

Chứng minh: Ta dùng cái mẹo Bernstein, còn gọi là phương pháp mô-măng mũ (exponential moment method). Do hàm mũ là hàm lồi, bất đẳng thức Jensen suy ra, với ${t>0}$ ta có

$\displaystyle \begin{array}{rcl} \exp\left( t \mathop{\mathbf E}_\sigma\left[ \sup_{\mathbf x \in A} \sum_{i=1}^m \sigma_ix_i \right] \right) &\leq& \mathop{\mathbf E}_\sigma \left[ \exp\left( t \sup_{\mathbf x \in A} \sum_{i=1}^m \sigma_ix_i \right) \right]\\ &=& \mathop{\mathbf E}_\sigma \left[ \sup_{\mathbf x \in A} \exp\left( t \sum_{i=1}^m \sigma_ix_i \right) \right]\\ &\leq& \sum_{\mathbf x \in A} \mathop{\mathbf E}_\sigma \left[ \exp\left( t \sum_{i=1}^m \sigma_ix_i \right) \right]\\ &=& \sum_{\mathbf x \in A} \prod_{i=1}^m \mathop{\mathbf E}_\sigma \left[ \exp\left( t \sigma_ix_i \right) \right] \end{array}$

Đến đây, ta dùng một bất đẳng thức tạm gọi là bất đẳng thức Hoeffding nhỏ, thường dùng làm bước chính trong chứng minh BĐT Hoeffding (lớn). BĐT Hoeffding nhỏ phát biểu như sau: nếu ${X}$ là một biến ngẫu nhiên với ${\mathop{\mathbf E}[X]=0}$ và ${X\in [a,b]}$ thì, với mọi ${s>0}$ ta có ${\mathop{\mathbf E}[\exp(sX)] \leq \exp(s^2(b-a)^2/8)}$ . Chứng minh BĐT này rất đơn giản. (Xem ở đây chẳng hạn.) Từ BĐT Hoeffding nhỏ ta có

$\displaystyle \mathop{\mathbf E}_\sigma \left[ \exp\left( t \sigma_ix_i \right) \right] \leq \exp(t^2(2x_i)^2/8) = \exp(t^2x_i^2/2).$

Như vậy,

$\displaystyle \exp\left( t \mathop{\mathbf E}_\sigma\left[ \sup_{\mathbf x \in A} \sum_{i=1}^m \sigma_ix_i \right] \right) \leq \sum_{\mathbf x \in A} \prod_{i=1}^m \exp(t^2x_i^2/2) \leq |A| \exp(t^2L^2/2).$

Lấy ${\log}$ hai vế, với mọi ${t>0}$ ta có

$\displaystyle \mathop{\mathbf E}_\sigma\left[ \sup_{\mathbf x \in A} \sum_{i=1}^m \sigma_ix_i \right] \leq \frac{\log|A|}{t} + \frac{tL^2}{2}.$

Chọn ${t = \frac{\sqrt{2\log|A|}}{L}}$ để giảm thiểu vế phải là hoàn tất toàn bộ chứng minh. $\Box$

Bài tập: chứng minh Bổ đề 2 từ Bổ đề Massart.

HM6 — Độ phức tạp Rademacher

Post a Comment Cancel reply

Thông điệp ngắn

Phản hồi mới

Bài mới

Thư khố

Chuyên Mục

Báo chí

Bảo mật

Blog Việt

Chưa phân loại

Giáo dục

Kỹ thuật

Khoa học khác

Kinh tế, luật pháp, xã hội

Lý thuyết & thuật toán

Mạng

Não học

Toán học

Vật Lý