HM5 — Định lý Vapnik-Chervonenkis cho mô hình giả thuyết không nhất quán

NQH | 30/08/2010 |

HM4: Độ phức tạp mẫu và VC dimension.
HM6: Độ phức tạp Rademacher

Hai mô hình (nhất quán và PAC) chúng ta thấy cho đến nay đều không thực tế lắm. Trên thực tế dữ liệu thường có nhiễu, việc tìm một giả thuyết nhất quán với nhiều mẫu trở nên khó khăn. Đôi khi không tồn tại giả thuyết nào nhất quán với dữ liệu, hoặc cho dù có tồn tại thì nhiễu cũng làm cho không tồn tại. Vả lại, nhất quán với dữ liệu bị nhiễu thì cũng không hay ho gì. Đó là chưa kể việc đi tìm một giả thuyết nhất quán với dữ liệu có thể là bài toán NP-khó, và thậm chí có thể trên thực tế không tồn tại cái khái niệm mà mình đang muốn học.

(Từ giờ trở đi, tôi sẽ dịch “learner” là “học giả”. Học giả ở đây là một thuật toán máy tính chứ không phải là một gã hói đầu. “Học giả như hòa như đạo. Bất học giả như cảo như thảo.”)

Như vậy chúng ta cần một mô hình cho phép học giả trả về một giả thuyết không nhất quán với mẫu, và phải tìm cách đo chất lượng học giả — kể cả khi không có cái khái niệm mà mình muốn học. Bài này kết thúc bằng chứng minh định lý Vapnik-Chervonenkis, một trong những định lý quan trọng nhất của lý thuyết học máy thống kê (statistical learning theory).

7. Mô hình giả thuyết không nhất quán

Trong mô hình này, ta giả sử cả training data lẫn test data đều gồm các điểm ${({\bf x},y)}$ được lấy mẫu từ không gian ${\Omega \times \{0,1\}}$ theo một phân bố ${\mathcal D}$ chưa biết nào đó. Dễ thấy rằng giả định này tổng quát hơn giả định của mô hình PAC, vì với PAC thì các điểm ${({\bf x},y)}$ được lấy mẫu dựa trên phân bố của ${{\bf x}}$ và khái niệm cần học.

Chất lượng của một giả thuyết ${h}$ được đo bằng “lỗi thật” của nó, định nghĩa như sau:

$\displaystyle \text{err}(h) := \mathop{\textnormal{Prob}}_{({\bf x}, y) \leftarrow \mathcal D} [h({\bf x}) \neq y]$

Lỗi này cũng được gọi là lỗi tổng quát hóa (generalization error) của giả thuyết ${h}$ . Trong trường hợp lý tưởng thì chúng ta muốn giải quyết vấn đề sau đây.

Định nghĩa 1 (Bài toán lý tưởng) Tìm giả thuyết ${h^* \in \mathcal H}$ sao cho lỗi thật ${\text{err}(h^*)}$ là tối thiểu. Nói cách khác,
$\displaystyle h^* = \mathop{\text{argmin}}_{h\in \mathcal H} \text{ err}(h).$

Gọi là trường hợp lý tưởng vì chúng ta không biết ${\mathcal D}$ , do đó không thể tính hàm ${\text{err}(h)}$ . Nếu ta biết phân bố ${\mathcal D}$ thì rõ ràng là giả thuyết sau đây là tối ưu:

$\displaystyle h_{\text{\sc opt}}({\bf x}) = \begin{cases} 1 & \textnormal{if} \ \text{Prob}[ y=1 \ | \ {\bf x}] \geq 1/2\\ 0 & \textnormal{if} \ \text{Prob}[ y=0 \ | \ {\bf x}] < 1/2 \end{cases}.$

Giả thuyết này được gọi là Bayes optimal classifier, còn giá trị ${\text{err}(h_{\text{\sc opt}})}$ — gọi là lỗi Bayes — nhỏ hơn bất kỳ ${\text{err}(h)}$ nào khác. Cũng lưu ý rằng ${h_{\text{\sc opt}}}$ không nhất thiết là phải thuộc về lớp giả thuyết ${\mathcal H}$ cho trước. (Chúng ta sẽ quay lại với chủ đề giả thuyết cuối cùng không thuộc ${\mathcal H}$ trong bài tới khi ta thảo luận thuật toán AdaBoost.)

Quay lại với cách “cài đặt” vấn đề trong mô hình giả thuyết không nhất quán ở trên. Do ta không biết ${\mathcal D}$ , bài toán thật sự không thể là bài toán tìm giả thuyết với lỗi thật tối thiểu. Một lối ra khá phổ dụng trong các trường hợp tối ưu các hàm không tính được là ta dùng một hàm khác, tính/ước lượng được, để xấp xỉ cái lỗi thật ${\text{err}(h)}$ mà ta không tính được. Cụ thể hơn, định nghĩa lỗi thực nghiệm (empirical error) như sau:

$\displaystyle \widehat{\text{err}}(h) = \frac{|\{i : h({\bf x}_i) \neq y_i\}|}{m}$

Lỗi thực nghiệm còn được gọi là lỗi huấn luyện (training error) hoặc rủi ro thực nghiệm (empirical risk cho 01 loss function). Đôi khi, để nhấn mạnh là lỗi thực nghiệm được đo trên bộ mẫu ${S}$ , ta dùng ký hiệu ${\widehat{\text{err}}_S(h)}$ .

Chúng ta sẽ chứng minh cái gọi là định lý hội tụ đều (uniform convergence theorem). Định lý này nói rằng, với số mẫu đủ lớn thì lỗi thật và lỗi thực nghiệm của một giả thuyết bất kỳ không xa nhau là mấy. (Với một giả thuyết ${h}$ cố định thì trị kỳ vọng của lỗi thực nghiệm là lỗi thật, do đó định lý này hữu lý.) Do đó, thay vì tìm giả thuyết với lỗi thật nhỏ nhất (đằng nào cũng không làm được) thì ta có thể cố tìm giả thuyết với lỗi thực nghiệm nhỏ nhất. Chiến lược này gọi là chiến lược tối thiểu rủi ro thực nghiệm (empirical risk minimization hay ERM)

Định nghĩa 2 (ERM) Tìm giả thuyết ${\hat h^* \in \mathcal H}$ sao cho lỗi thực nghiệm ${\widehat{\text{err}}(\hat h^*)}$ là tối thiểu. Nói cách khác,
$\displaystyle \hat h^* = \mathop{\text{argmin}}_{h\in \mathcal H} \widehat{\text{err}}(h).$

Các học giả Occam như thảo luận trong các bài trước (tìm giả thuyết nhất quán với toàn bộ mẫu — lỗi thực nghiệm bằng không) là trường hợp đặc biệt của lời giải bài toán trên. Bài toán ERM trên cho phép cả trường hợp ta không tìm được giả thuyết nhất quán. Một trong những điểm yếu của ERM (với 01 loss function như định nghĩa ở trên) là nó thường là bài toán NP-khó (xem bài này chẳng hạn).

Định lý 3 (Định lý hội tụ đều cho ${\mathcal H}$ hữu hạn) Xét trường hợp lớp giả thuyết ${\mathcal H}$ là hữu hạn. Nếu ta lấy
$\displaystyle m \geq \frac{\log\left( \frac{2|\mathcal H|}{\delta}\right)}{2\epsilon^2}$

mẫu từ phân bố ${\mathcal D}$ thì
$\displaystyle \text{Prob}\left[|\text{err}(h) - \widehat{\text{err}}(h)| \leq \epsilon, \ \forall h \in \mathcal H \right] \geq 1-\delta.$

Chứng minh: Rất dễ. Áp dụng bất đẳng thức Hoeffing (một dạng con gà Chernoff, và là trường hợp đặc biệt của bất đẳng thức McDiarmid) ta có, với ${h}$ bất kỳ:

$\displaystyle \text{Prob}\left[|\text{err}(h) - \widehat{\text{err}}(h)| > \epsilon\right] < 2e^{-2\epsilon^2m}.$

Sau đó, union bound cho ta

$\displaystyle \text{Prob}\left[\forall h \in \mathcal H, |\text{err}(h) - \widehat{\text{err}}(h)| > \epsilon\right] < 2|\mathcal H|e^{-2\epsilon^2m}.$

Từ đó dẫn đến kết luận của định lý. $\Box$

Từ định lý hội tụ đều, ta thấy rằng lời giải cho bài toán ERM cũng khá tốt so với lời giải của bài toán lý tưởng:

$\displaystyle \text{err}(\hat h^*) \leq \widehat{\text{err}}(\hat h^*) + \epsilon \leq \widehat{\text{err}}(h^*) + \epsilon \leq \text{err}(h^*) + 2\epsilon.$

Ta có thể viết lại sự phụ thuộc của lỗi tổng quát hóa ${\text{err}(h)}$ vào lỗi thực nghiệm ${\widehat{\text{err}}(h)}$ , độ phức tạp của lớp giả thuyết ${\log |\mathcal H|}$ , tổng số mẫu ${m}$ và độ tin cậy như sau:

$\displaystyle \text{err}(h) \leq \widehat{\text{err}}(h) + \sqrt{\frac{\log(2|\mathcal H|) + \log(1/\delta)}{m}}$

Có vài điểm đáng chú ý:

Độ phức tạp mẫu phụ thuộc vào ${\epsilon^2}$ chứ không còn là ${\epsilon}$ như trong mô hình PAC.
Tăng ${m}$ thì lỗi tổng quát hóa giảm. Cho học giả càng nhiều ví dụ càng tốt. Dĩ nhiên làm thế sẽ ảnh hưởng đến thời gian chạy của học giả.
Độ phức tạp của lớp giả thuyết càng nhỏ càng tốt.
Lỗi thực nghiệm càng bé càng tốt.
Tuy nhiên, có một trade-off giữa lỗi thực nghiệm và độ phức tạp của lớp giả thuyết. Nếu lớp giả thuyết quá đơn giản thì khả năng ta tìm được một giả thuyết có lỗi thực nghiệm bé sẽ giảm. Khi độ phức tạp của lớp giả thuyết tăng lên thì sẽ dễ tìm giả thuyết ${h}$ có lỗi thực nghiệm ${\widehat{\text{err}}(h)}$ nhỏ. Nhưng đến một lúc nào đó thì số hạng thứ hai (chứa ${\log (2|\mathcal H|)}$ ) sẽ áp đảo số hạng thứ nhất, và ta bị vấn đề overfitting, một vấn đề thật sự đau đầu trong thống kê.

Trong hai bài tới, chúng ta sẽ thảo luận thuật toán AdaBoost và thuật toán Support Vector Machine; có vẻ như chúng chống chọi vấn đề overfitting khá tốt.

Trong trường hợp ${\mathcal H}$ vô hạn thì ta có định lý hội tụ đều dùng VC-dimension, là một trong những định lý quan trọng nhất trong statistical learning theory.

Định lý 4 (Định lý hội tụ đều cho ${\mathcal H}$ vô hạn — Còn gọi là định lý Vapnik-Chervonenkis) Xét trường hợp lớp giả thuyết ${\mathcal H}$ là vô hạn với ${d = \text{\sc vcd}(\mathcal H)}$ . Nếu ta lấy
$\displaystyle m = \Omega\left( \frac{d}{\epsilon^2}\log\frac{1}{\epsilon} + \frac{1}{\epsilon^2} \log \frac 1 \delta\right)$

mẫu từ phân bố ${\mathcal D}$ thì
$\displaystyle \text{Prob}\left[|\text{err}(h) - \widehat{\text{err}}(h)| \leq \epsilon, \ \forall h \in \mathcal H \right] \geq 1-\delta.$

Chứng minh: Ta cần chứng minh bất đẳng thức sau đây:

$\displaystyle \mathop{\text{Prob}}_S \left[ \sup_{h \in \mathcal H} |\text{err}(h) - \widehat{\text{err}}_S(h)| > \epsilon \right] \leq \delta,$

trong đó ${S=\{({\bf x}_1,y_1), \cdots, ({\bf x}_m,y_m)\}}$ là tập ${m}$ mẫu độc lập. Giống như trong trường hợp định lý VC cho mô hình PAC, ta dùng cái mẹo lấy mẫu kép. Ta lấy thêm ${m}$ mẫu độc lập ${S'=\{({\bf x}'_1,y'_1), \cdots, ({\bf x}'_m,y'_m)\}}$ nữa (chỉ là công cụ chứng minh, không lấy thật). Chứng minh bao gồm bốn bước.

Bước 1. chuyển từ vô hạn xuống hữu hạn. Ta sẽ chứng minh rằng

$\displaystyle \mathop{\text{Prob}}_S \left[ \sup_{h \in \mathcal H} |\text{err}(h) - \widehat{\text{err}}_S(h)| > \epsilon \right] \leq 2 \cdot \mathop{\text{Prob}}_{S,S'} \left[ \sup_{h \in \mathcal H} |\widehat{\text{err}}_{S}(h) - \widehat{\text{err}}_{S'}(h)| > \epsilon/2 \right]$

Với một bộ mẫu ${S}$ đã lấy, nếu ${\sup_{h \in \mathcal H} |\text{err}(h) - \widehat{\text{err}}_S(h)| > \epsilon}$ thì định nghĩa ${h_S}$ là một hàm (tùy hỉ) trong ${\mathcal H}$ miễn sao ${|\text{err}(h_S) - \widehat{\text{err}}_S(h_S)| > \epsilon}$ ; còn nếu ${\sup_{h \in \mathcal H} |\text{err}(h) - \widehat{\text{err}}_S(h)| \leq \epsilon}$ thì định nghĩa ${h_S}$ là một hàm bất kỳ trong ${\mathcal H}$ .

Trước hết, dùng bất đẳng thức Chernoff, dễ chứng minh được rằng, với mọi ${S}$ và ${m \geq 100/\epsilon^2}$ ta có:
$\displaystyle \mathop{\text{Prob}}_{S'} \left[ |\text{err}(h_S) - \widehat{\text{err}}_{S'}(h_S)| < \epsilon/2 \right] \geq 1/2.$

(Không cần đến ${100}$ , để cho vui thôi; cỡ ${8}$ là đủ.)

$\displaystyle \begin{array}{rcl} && \mathop{\text{Prob}}_S \left[ \sup_{h \in \mathcal H} |\text{err}(h) - \widehat{\text{err}}_S(h)| > \epsilon \right]\\ &=& \mathop{\text{E}}_S \left[ {\bf 1}_{\{|\text{err}(h_S) - \widehat{\text{err}}_S(h_S)| > \epsilon\}} \right]\\ &\leq & 2 \cdot \mathop{\text{E}}_S \left[ {\bf 1}_{\{|\text{err}(h_S) - \widehat{\text{err}}_S(h_S)| > \epsilon\}} \cdot \mathop{\text{Prob}}_{S'} \left[ |\text{err}(h_S) - \widehat{\text{err}}_{S'}(h_S)| < \epsilon/2 \right] \right]\\ &\leq & 2 \cdot \mathop{\text{E}}_S \left[ {\bf 1}_{\{|\text{err}(h_S) - \widehat{\text{err}}_S(h_S)| > \epsilon\}} \cdot \mathop{\text{E}}_{S'} \left[ {\bf 1}_{\{|\text{err}(h_S) - \widehat{\text{err}}_{S'}(h_S)| < \epsilon/2\}} \right] \right]\\ &=& 2 \cdot \mathop{\text{E}}_{S,S'} \left[ {\bf 1}_{\{|\text{err}(h_S) - \widehat{\text{err}}_S(h_S)| > \epsilon\}} \cdot {\bf 1}_{\{|\text{err}(h_S) - \widehat{\text{err}}_{S'}(h_S)| < \epsilon/2\}} \right]\\ &=& 2 \cdot \mathop{\text{Prob}}_{S,S'} \left[ |\text{err}(h_S) - \widehat{\text{err}}_S(h_S)| > \epsilon \text{ and } |\text{err}(h_S) - \widehat{\text{err}}_{S'}(h_S)| < \epsilon/2 \right]\\ &\leq & 2 \cdot \mathop{\text{Prob}}_{S,S'} \left[ \sup_{h \in \mathcal H} |\widehat{\text{err}}_{S}(h) - \widehat{\text{err}}_{S'}(h)| > \epsilon/2 \right] \end{array}$
Bước 2. đối xứng hóa dùng các biến Rademacher ${\sigma_i \in \{-1,1\}, i \in [m]}$ , nghĩa là ${\text{Prob}[\sigma_i=1]=\text{Prob}[\sigma_i=-1]=1/2}$ . Ta sẽ chứng minh rằng
$\displaystyle \mathop{\text{Prob}}_{S,S'} \left[ \sup_{h \in \mathcal H} |\widehat{\text{err}}_{S}(h) - \widehat{\text{err}}_{S'}(h)| > \epsilon/2 \right] \leq 2 \cdot \mathop{\text{Prob}}_{S,\sigma} \left[ \sup_{h \in \mathcal H} \frac 1 m \left| \sum_{i=1}^m \sigma_i {\bf 1}_{\{h({\bf x}_i) \neq y_i\}} \right| > \epsilon/4 \right]$

Lưu ý rằng ${{\bf 1}_{\{h({\bf x}_i) \neq y_i\}}}$ và ${{\bf 1}_{\{h({\bf x}'_i) \neq y'_i\}}}$ có cùng phân bố, do đó ${({\bf 1}_{\{h({\bf x}_i) \neq y_i\}} - {\bf 1}_{\{h({\bf x}'_i) \neq y'_i\}})}$ và ${-({\bf 1}_{\{h({\bf x}_i) \neq y_i\}} - {\bf 1}_{\{h({\bf x}'_i) \neq y'_i\}})}$ có cùng phân bố với trị kỳ vọng bằng ${0}$ . Ta có:
$\displaystyle \begin{array}{rcl} && \mathop{\text{Prob}}_{S,S'} \left[ \sup_{h \in \mathcal H} |\widehat{\text{err}}_{S}(h) - \widehat{\text{err}}_{S'}(h)| > \epsilon/2 \right]\\ &=& \mathop{\text{Prob}}_{S,S'} \left[ \sup_{h \in \mathcal H} \frac 1 m \left| \sum_{i=1}^m ({\bf 1}_{\{h({\bf x}_i) \neq y_i\}} - {\bf 1}_{\{h({\bf x}'_i) \neq y'_i\}}) \right| > \epsilon/2 \right]\\ &=& \mathop{\text{Prob}}_{S,S',\sigma} \left[ \sup_{h \in \mathcal H} \frac 1 m \left| \sum_{i=1}^m \sigma_i \left({\bf 1}_{\{h({\bf x}_i) \neq y_i\}} - {\bf 1}_{\{h({\bf x}'_i) \neq y'_i\}}\right) \right| > \epsilon/2 \right]\\ &\leq& \mathop{\text{Prob}}_{S,S',\sigma} \left[ \left\{ \sup_{h \in \mathcal H} \frac 1 m \left| \sum_{i=1}^m \sigma_i {\bf 1}_{\{h({\bf x}_i) \neq y_i\}} \right| > \epsilon/4 \right\} \text{ or } \left\{ \sup_{h \in \mathcal H} \frac 1 m \left| \sum_{i=1}^m \sigma_i {\bf 1}_{\{h({\bf x}'_i) \neq y'_i\}} \right| > \epsilon/4 \right\} \right]\\ &\leq& 2 \cdot \mathop{\text{Prob}}_{S,\sigma} \left[ \sup_{h \in \mathcal H} \frac 1 m \left| \sum_{i=1}^m \sigma_i {\bf 1}_{\{h({\bf x}_i) \neq y_i\}} \right| > \epsilon/4 \right] \end{array}$
Bước 3. thay vì xét cái ${\sup_{h\in \mathcal H}}$ ở vế phải bất đẳng thức trên, ta chỉ cần xét các “dichotomies” của lớp giả thuyết ${\mathcal H}$ trên tập ${\{ {\bf x}_i \ | \ ({\bf x}_i, y_i) \in S\}}$ . Áp dụng bất đẳng thức Hoeffding và union bound là ta sẽ có:
$\displaystyle \mathop{\text{Prob}}_{S,\sigma} \left[ \sup_{h \in \mathcal H} \frac 1 m \left| \sum_{i=1}^m \sigma_i {\bf 1}_{\{h({\bf x}_i) \neq y_i\}} \right| > \epsilon/4 \right] \leq \Pi_{\mathcal H}(m) \cdot 2 \cdot e^{-m\epsilon^2/32}.$

Cụ thể hơn, với mọi ${h}$ , ${\sigma_i {\bf 1}_{\{h({\bf x}_i) \neq y_i\}}}$ là các biến độc lập với trị kỳ vọng bằng ${0}$ , dao động giữa ${1}$ và ${-1}$ . Do đó, bất đẳng thức Hoeffding cho ta biết (conditioning on ${S}$ )
$\displaystyle \mathop{\text{Prob}}_\sigma \left[ \frac 1 m \left| \sum_{i=1}^m \sigma_i {\bf 1}_{\{h({\bf x}_i) \neq y_i\}} \right| > \epsilon/4 \left| \right. S \right] \leq 2 \cdot e^{-m\epsilon^2/32}.$

Với một bộ mẫu ${S}$ đã chọn thì tổng số dãy ${({\bf 1}_{\{h({\bf x}_1) \neq y_1\}}, \cdots, {\bf 1}_{\{h({\bf x}_m) \neq y_m\}})}$ khác nhau bị chặn trên bởi ${\Pi_{\mathcal H}(m)}$ . Do đó, union bound hoàn tất bước 3, vì
$\displaystyle \mathop{\text{Prob}}_\sigma \left[ \sup_{h\in \mathcal H} \frac 1 m \left| \sum_{i=1}^m \sigma_i {\bf 1}_{\{h({\bf x}_i) \neq y_i\}} \right| > \epsilon/4 \left| \right. S \right] \leq \Pi_{\mathcal H}(m) \cdot 2 \cdot e^{-m\epsilon^2/32}.$
Bước 4. Bổ đề Sauer và tính toán cơ bắp hoàn tất chứng minh định lý. Bổ đề Sauer cho biết ${\Pi_{\mathcal H}(m) \leq (em/d)^d}$ . Do đó ta chỉ cần chọn ${m}$ sao cho
$\displaystyle 8 (em/d)^d e^{-m\epsilon^2/32} \leq \delta$

là xong. Dễ thấy rằng ${m = \Omega\left( \frac{d}{\epsilon^2}\log\frac{1}{\epsilon} + \frac{1}{\epsilon^2} \log \frac 1 \delta\right)}$ đủ thỏa.

$\Box$

Chủ đề : Lý thuyết tính toán, Trí tuệ nhân tạo, Xác suất & thống kê and tagged COLT, học máy, VC-dimension. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

12 Comments

XuanLong Nguyen

Posted 31/08/2010 at 10:05 am | Permalink

Lại thêm một bài hay trong một loạt bài rất thú vị. Xin phép nitpick bác Hưng một tí về “nhiễu”.

“Đôi khi không tồn tại giả thuyết nào nhất quán với dữ liệu, hoặc cho dù có tồn tại thì nhiễu cũng làm cho không tồn tại.”: Tùy bác định nghĩa thế nào là nhiễu. Nếu nhiễu là random noise thì phần sau của câu này không chính xác lắm. Lý thuyết của Shannon là một ví dụ tại sao nhiễu không ngăn ta transmit hay reconstruct tín hiệu một cách chính xác. Nhưng nói chung với estimation theory (mà trong đó statistical learning theory và thậm chí lý thuyết kinh điển của Shannon là những trường hợp “đặc biệt” và thú vị)) thì nhiễu không phải là một nuissance.

“Vả lại, nhất quán với dữ liệu bị nhiễu thì cũng không hay ho gì.”: Tuy đây là quan điểm truyền thống trong KHMT — nhiễu là xấu — nhưng trong XSTK và trong các lĩnh vực liên quan đến data trong KHMT ngày nay (như vision, natural language processing, networking) thì data luôn luôn được coi là có “nhiễu”. Đã là data thì phải nhiễu rồi, chỉ có điều nhiễu nhiều hay ít và nhiễu thế nào.

“Đó là chưa kể việc đi tìm một giả thuyết nhất quán với dữ liệu có thể là bài toán NP-khó, và thậm chí có thể trên thực tế không tồn tại cái khái niệm mà mình đang muốn học.”: Đồng ý phần đầu, nhưng phần sau của câu này làm tôi hơi hoang mang. Có lẽ bác nói là chúng ta không thể biểu diễn được chính xác khái niệm mình đang muốn học bằng các cấu trúc (toán học) nhất định, như tập các hàm tuyến tính, tập các hàm smooth, tập các stochastic processes nào đó, v.v. , thay vì nói về sự không tồn tại. Cho nên phải cần xấp xỉ. Định lý VC là một ví dụ nói về tính chất của estimation error, nhưng không nói gì về khía cạnh approximation (error).

Reply
Ngô Quang Hưng

Posted 31/08/2010 at 10:32 am | Permalink

Thanks bác Long,

Ý tôi nói “không tồn tại giả thuyết nhất quán” là không tồn tại giả thuyết trong lớp giả thuyết cho trước. Đúng như bác nói là tôi đang muốn nói đến một mathematical format nhất định cho giả thuyết. Đoạn này tôi chỉ đang nói đến các giới hạn của PAC-formulation, vì nó bỏ qua không mô hình hóa thế nào là nhiễu. Cái mô hình “giả thuyết không nhất quán” này “embrace” nhiễu luôn.

Câu “không tồn tại khái niệm mình đang muốn học” đúng là hơi … vô nghĩa — may có bác giải thích rồi. We have to learn how to hand-wave before learning how to fly.

À, bác có biết chứng minh nào của định lý 4 ở trên dùng phương pháp nào khác về chất không?

Reply
XuanLong Nguyen

Posted 31/08/2010 at 11:34 am | Permalink

Mọi cách chứng minh upper bound (kiểu ĐL 4) đều dùng uniform bound argument (taking sup over entire set of hypothesis H). Tôi chỉ biết một cách tương tự, nhưng tổng quát hơn (cho mọi function class) của Richard Dudley. Step 1 va step 2 thì giống như trên, nhưng step 3 thì dùng “chaining method” để upper bound cái chặn cho Rademacher variables bằng entropy integral. Đối với linear function class thì cái entropy integral này có thể chặn bằng VC dimension. Nhưng cách chứng minh này tổng quát hơn vì nó có thể áp dụng được cả function class mà VC dimension là vô hạn.

Cách dùng uniform bound không phải là hay, trong trường hợp chúng ta biết nhiều hơn về hypothesis space H (như trong Bayesian settup chẳng hạn, khi mà có một số vủng của H mà khả năng chứa đựng solution cao hơn các vủng khác.)

Reply
- Ngô Quang Hưng
  
  Posted 31/08/2010 at 4:46 pm | Permalink
  
  Đúng là kiểu worst-case analysis từ quan điểm frequentist thường sẽ không thể dẫn đến bounds tốt được. Đọc về smooth analysis (xem bác Văn giới thiệu, hay bài của Gowers), tôi đang nghĩ là có một liên hệ chặt chẽ nào đó giữa hai nhánh. Smooth analysis là một cố gắng “thoát ly” khỏi cái worst-case curse, nhưng cũng tránh luôn average-case analysis vì average-case analysis đòi hỏi “prior” mạnh quá.
  
  Reply
  - xuanlong
    
    Posted 01/09/2010 at 7:56 am | Permalink
    
    Tôi cũng đọc 2 bài của bác Văn và Gowers, đều rất thích. Nhưng tôi nghĩ cách của Spielman & Teng cũng là một dạng prior cụ thể thôi. Nhưng đúng đó là một “reasonable prior”.
    
    Mất một thời gian dài tôi mới ngộ ra, cũng như việc phải “embrace” nhiễu thay vì coi nó là “nuissance”, ta nên embrace prior thay vì làm kiếu worst case (minimax) analysis. Tìm ra “reasonable prior” để phân tích chính là name of the game.
    
    Reply
XuanLong Nguyen

Posted 31/08/2010 at 11:49 am | Permalink

À, còn để chứng minh lower bound, kiểu như

\inf_{a\in A} \sup_{h \in H} ErrorOfEstimation \geq RateOfSampleSize

(bằng từ: trong mọi “học giả” a \in A, luôn tồn tại một khái niệm h \in H mà error estimation không thể nhỏ hơn RateOfSampleSize). Các lower bound này đều dùng combinatorial argument rất hay. Chắc bác sẽ rất thích.

RateOfSampleSize tất nhiên phụ thuộc vào H. Thường cho các cấu trúc H kinh điển, thì cái RateofSampleSize này cũng bằng với rate của upper bound kiểu ĐL 4.

Nhưng tôi không hiếu sao dân stat learning theory khong lam nhieu về lower bounds. Cái này trong Statistics gọi là lý thuyết minimax, của Le Cam, Fano, Assouad. Sau này có đóng góp của Donoho, Birge’, Massart và một vài vị khác.

Reply
- Ngô Quang Hưng
  
  Posted 31/08/2010 at 4:40 pm | Permalink
  
  Ý bác nói cái lower bound kiểu như trong section 6 của bài trước à. (BTW, tôi sẽ viết lại section này, chứng minh chặn tốt hơn — $\Omega(d/\epsilon)$ thay vì là $d/2$ .) Đúng là tôi thấy rất ít lower bounds, khi nào bác thấy cái nào hay ho thì ghi lại nhé.
  
  Reply
  - xuanlong
    
    Posted 31/08/2010 at 6:12 pm | Permalink
    
    Lower bound này còn thô sơ. Vấn đề là phải chỉ ra điều kiện khi nào thì lower bound = upper bound (có học giả). Cái trỏ này, về nhiều mặt rất giống trò bounds của NP và P.
    
    Có một long history về minimax bounds. Bài tổng quan về kỹ thuật này đọc rất dễ chịu (Yu, 1992):
    
    http://www.stat.berkeley.edu/~binyu/ps/LeCam.pdf
    
    Một ví dụ về một bài gần đây hơn, cho trường hợp vấn đề là học một unknown density function (Yang and Barron, 1999)
    
    http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1017939142
    
    Bài này nói về vấn đề estimate một functional của unknown density, dùng kỹ thuật khác (Birge and Massart, 1996)
    
    http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1176324452
    
    Hai bài sau dùng hai kỹ thuật khác nhau đều được đề cập trong bài báo tổng quan đầu tiên.
    
    Nhân tiện, tôi hiện cũng có một vấn đề mở đã ba năm nay, liên quan đến lower bound và các bài references trên. Trong bài báo dưới đây (to appear in IEEE Trans. Info) tôi có propose một phương pháp học KL divergence (mutual
    information) of two unknown densities
    http://arxiv.org/abs/0809.0853
    (Phương pháp này đáng nói ở chỗ nó không đòi hỏi học từng density rồi estimate — cách này hơi bổ củi và không phải là hay ho gì).
    
    Câu hỏi ở đây là khi nào thì phương pháp này có phải là tối ưu (tức là chặn trên bằng chặn dưới). Đối với entropy functional thì đã biết kết quả rồi (thông qua bài báo của Birge-Massart trên đây). Tuy vậy với relative entropy (KL divergence/mutual information) thì chưa. Kết quả cho relative entropy chắc chắn là khó hơn entropy vì cái sau là trường hợp đặc biệt của cái đầu. Tuy nhiên tôi không rõ về bản chất thì có khó hơn hẳn hay không.
    
    Reply
Na K54

Posted 02/09/2010 at 6:57 am | Permalink

co’ ba’c nao bit tai lieu ve boosting algorithm khong chi em voi!! em dang tim hieu ve cac boosters

Reply
Administrator

Posted 02/09/2010 at 7:31 am | Permalink

@Na K54, xem http://www.cs.princeton.edu/~schapire/boost.html

Reply
Quốc Hưng

Posted 06/04/2011 at 2:57 pm | Permalink

Em đang chờ bài viết tiếp theo của anh Hưng về Online Learning (Regret Minimization) nhưng chưa thấy, nên em xin post câu hỏi ở đây mong anh Hưng, anh Long, và các anh chị đi trước cho thêm thông tin.
- Em thấy hầu như ko có bài báo nào đi theo hướng online, incremental training cho 1 hypothesis duy nhất (tại mỗi thời điểm), mà đa số dùng 1 nhóm experts, hoặc xét cả 1 hypothesis space, rồi update weight distribution. Nguồn gốc sâu xa là vì sao ạ? Các anh có biết bài báo nào dùng cách đầu, cập nhật giả thuyết mới mỗi khi có 1 sample mới ko?
- Có cách nào đánh giá “learning progress” cho cả 2 cách trên (xét single hypothesis, hoặc update weights) sau 1 hoặc một vài sample mới? Liệu có phương pháp nào ước lượng information gain của bên Active Learning có thể dùng được (để đánh giá learning progress) cho Online Learning ko ạ?

Reply
- NQH
  
  Posted 06/04/2011 at 4:15 pm | Permalink
  
  Hi Quốc Hưng,
  
  Nếu là 1 hypothesis duy nhất thì còn “train” gì nữa. Hay là tôi hiểu sai câu hỏi. Hay ý bạn nói là ta “update weight” của một hypothesis duy nhất? Như vậy nhiều khả năng là không phân lớp được dữ liệu nào hay ho hết. Cả một lớp các hàm phân lớp có khi còn chưa đủ “biểu cảm” để phân lớp dữ liệu nữa là một hàm.
  
  Đánh giá “learning progress” thì có thể ta dùng empirical error của combined hypothesis trên toàn bộ data đã thấy cho đến nay.
  
  Hy vọng sẽ có bài về online learning sớm. Hôm nọ vừa mới chat với bác Long về đề tài này.
  
  Reply

HM5 — Định lý Vapnik-Chervonenkis cho mô hình giả thuyết không nhất quán

12 Comments

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ý