HM4 — Độ phức tạp mẫu và VC-dimension

NQH | 18/07/2008 |

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

Trong các bài trước ta đã đề cập đến một số vấn đề không học được trong mô hình PAC và tầm quan trọng của việc biểu diễn lớp giả thuyết như thế nào. Có lẽ bài báo đầu tiên nói về tầm quan trọng của (cách biểu diễn) lớp giả thuyết là bài của Pitt và Valiant (JACM, 1988). Có không ít các bài báo tiếp đó đã chứng minh độ khó của một số vấn đề học máy khác, ví dụ Blum và Rivest chứng minh rằng huấn luyện một mạng neural với 3 nodes là NP-khó (tương đương với phần hội của 3 halfspaces là không học được), Alekhnovich et al. ở FOCS 04 chứng minh một số các lớp hàm Bool và decision trees là không học được, V. Feldman ở STOC 06 chứng minh rằng lớp DNF không học được trong mô hình PAC kể cả khi learner có thể “hỏi” data (chứ không phải lấy ngẫu nhiên, xem thêm bài này nữa), Guruswami và Raghavendra ở FOCS 06 chứng minh rằng học halfspaces (còn gọi là perceptron, một cấu trúc cổ điển) với nhiễu là khó (ta sẽ nói về nhiễu sau), v.v. Duyệt qua STOC, FOCS,và COLT những năm gần đây sẽ thấy một vài kết quả nữa. Ngoài ra, còn có một mối liên kết giữa PAC-learning và property testing, một đề tài khá “hot” trong lý thuyết tính toán.

Chứng minh rằng học một lớp khái niệm dùng một lớp giả thuyết nào đó là bài toán khó (NP-khó chẳng hạn) không đáng ngạc nhiên (dù có thể không dễ). Thế nếu ta không giới hạn cả lớp giả thuyết nữa thì sao? Bài toán sẽ khó hơn hay dễ hơn? Một mặt, ta cho learner thêm flexibility, bài toán có vẻ “dễ” hơn. Mặt khác, không giới hạn lớp giả thuyết thì learner output cái gì bây giờ? Ta sẽ quay lại đề tài này trong một bài sau.

4. Occam’s learning và mối liên hệ giữa mô hình nhất quán và mô hình PAC, trường hợp lớp khái niệm hữu hạn

Tóm tắt lại mô hình PAC: learner muốn học khái niệm ${c}$ trong lớp khái niệm ${\mathcal C}$ bằng lớp giả thuyết ${\mathcal H}$ , nghĩa là learner phải đưa ra một giả thuyết ${h\in \mathcal H}$ bằng cách lấy ${m}$ mẫu theo phân bố ${\mathcal D}$ trên miền ${\Omega}$ sao cho ${h}$ rất gần ${c}$ với xác suất rất cao.

Trong đề mục này, ta chỉ xét các lớp giả thuyết hữu hạn, ${\mathcal H}$ có thể giống hoặc khác ${\mathcal C}$ . Một kết quả cổ điển của Valiant nói rằng: nếu learner đưa ra một giả thuyết nhất quán với “khá nhiều” các mẫu lấy độc lập thì đó chính là PAC learner! (Có thể không phải là efficient PAC learner, nhưng chắc chắn là PAC learner.) Cụ thể hơn:

Theorem 1 (Định lý Valiant) Nếu learner có thể đưa ra một giả thuyết ${h \in \mathcal H}$ nhất quán với ${m \geq \frac 1 \epsilon \log\left( \frac{|\mathcal H|}{\delta} \right)}$ mẫu (i.d.d.) thì giả thuyết đó sẽ thỏa điều kiện ${\text{Prob}\left[ \text{err}_{\mathcal D}(h) \leq \epsilon\right] \geq 1 - \delta}$ , nghĩa là learner là một PAC-learner.

Proof: Gọi một giả thuyết gọi là giả thuyết tồi nếu

$\displaystyle \text{err}_{\mathcal D}(h) = \text{Prob}_{\mathbf x \in \mathcal D}[h(\mathbf x) \neq c(\mathbf x)] > \epsilon$

Xác suất mà một giả thuyết tồi nhất quán với ${c}$ ở tất cả ${m}$ mẫu độc lập nhỏ hơn ${(1 - \epsilon)^m}$ . Do đó, xác suất mà giả thuyết learner đưa ra là giả thuyết tồi nhỏ hơn hoặc bằng xác suất tồn tại một giả thuyết tồi trong ${\mathcal H}$ nhất quán với ${c}$ . Union bound cho ta chặn xác suất này bằng ${|\mathcal H|(1-\epsilon)^m}$ . Ép vế cuối cùng nhỏ hơn hoặc bằng ${\delta}$ là xong! $\Box$

Định lý này dẫn đến một kết quả khác, thường được xem như một cách giải thích toán học cho nguyên tắc Occam’s Razor. Đại khái, nguyên tắc này nói rằng khi có một số giả thuyết tốt như nhau cạnh tranh cho việc giải thích cái gì đó thì nên chọn giả thuyết “đơn giản” nhất. Ví dụ: nếu cơ học cổ điển đã đủ để giải thích chuyển động của các hành tinh trong hệ mặt trời thì ta không cần thòng thêm một câu “Thượng đế tạo ra hệ mặt trời” nữa. (Như Laplace nói: “tôi không cần giả thuyết đó“.) Nếu ta chọn “đơn giản” = “ngắn gọn” thì từ định lý Valiant có thể chứng minh được rằng nếu learner đưa ra một giả thuyết “đủ ngắn” và nhất quán với data thì learner đó là PAC-learner. (“Đơn giản” = “ngắn gọn” là cái nhìn của lý thuyết thông tin!)

Từ định lý Valiant, có thể thiết kế một số efficient PAC-learners khá dễ dàng. Ví dụ: ta đã thiết kế một PAC learner để học Boolean conjunctions trong đề mục 3.3. Tổng số giả thuyết dạng Boolean conjuction nhiều nhất là ${3^n}$ . Dùng định lý Valiant, ta chỉ cần dùng thuật toán trong đề mục 2.1 và tìm một giả thuyết nhất quán với ${\frac 1 \epsilon \log \left( \frac{3^n}{\delta} \right)}$ mẫu là xong. Đây hiển nhiên vẫn là thuật toán thời gian đa thức. Tổng số mẫu ta cần thậm chí còn ít hơn tổng số mẫu cần trong thuật toán đã đưa trong đề mục 3.3.

Nếu ta giữ tổng số mẫu ${m}$ cố định, có thể đảo định lý Valiant lại và viết

$\displaystyle \text{Prob}\left[ \text{err}_{\mathcal D}(h) \leq \log\left(|\mathcal H|/\delta\right)/m \right] \geq 1 - \delta$

Có thể hiểu kết quả này nôm na là: ta càng biết nhiều về lớp giả thuyết thì càng có ít giả thuyết ( ${|\mathcal H|}$ giảm) và do đó lỗi của giả thuyết đưa ra càng bé, hoặc càng có nhiều data ( ${m}$ tăng) thì cũng thế.

5. VC-dimension và mối liên hệ giữa mô hình nhất quán và mô hình PAC, trường hợp lớp khái niệm vô hạn

Định lý Valiant xem ra có vẻ hữu dụng. Thế nhưng ta chẳng dùng nó được khi ${\log(|\mathcal H)|}$ lớn ơn một hàm đa thức, thậm chí vô hạn. Ví dụ 1: nếu ta muốn học lớp DNF dùng lớp DNF thì ${|\mathcal H| = 2^{2^n}}$ . Ví dụ 2: tổng số các axis-parallel rectangles là vô hạn, vậy mà vẫn tồn tại một efficient PAC-learner cho lớp axis-parallel rectangles.

May mà ta vẫn có thể chứng minh được một định lý tương tự định lý Valiant cho trường hợp ${\mathcal H}$ là vô hạn, nhưng ta sẽ phải giới thiệu một khái niệm mới cực kỳ thú vị, mang tính tổ hợp, gọi là VC-dimension của một lớp các hàm số. VC-dimension, viết tắt của Vapnik-Chervonenkis dimension, được Vapnik và Chervonenkis giới thiệu trong bài báo kinh điển của họ hồi năm 1971:

V. Vapnik and A. Chervonenkis. “On the uniform convergence of relative frequencies of events to their probabilities.” Theory of Probability and its Applications, 16(2):264–280, 1971.

Bài này của Hosking, Petnault và Sudan viết tổng quan về quan hệ giữa thống kê và data mining giới thiệu khá tốt trực quan của VC-dimension. Blumer et al. ở STOC 89 là bài báo đầu tiên giới thiệu VC-dimension vào ngành COLT; các kết quả của họ là nội dung chính của đề mục này của chúng ta.

5.1. Giới thiệu trực quan về VC-dimension

VC-dimension là một số đo “độ phức tạp” hoặc “dung tích” của một lớp các hàm số. Trong ngữ cảnh của chúng ta, lớp các hàm số chính là lớp giả thuyết. VC-dimension của một lớp giả thuyết là số ${m}$ lớn nhất sao cho tồn tại ${m}$ mẫu mà với bất kỳ cách gán nhãn nào cho các mẫu này ta cũng có thể tìm được một giả thuyết nhất quán với chúng. Dĩ nhiên, nếu không tồn tại số ${m}$ lớn nhất này thì VC-dimension của lớp giả thuyết là vô hạn. VD-dimension cũng được định nghĩa cho cả các lớp hàm biến thực chứ không chỉ các lớp hàm trị 0, 1 như trong bài toán phân loại mà ta đang xét.

Trong ngữ cảnh của statistical learning theory thì VC-dimension là số đo “dung tích” của một tập hợp bất kỳ các mô hình thống kê. Bài này có một đoạn nói rất tốt nên tôi dịch lại ra đây:

Do khái niệm này được định nghĩa dựa trên tổng số mẫu và tính nhất quán của các models trên các mẫu, nó có thể áp dụng cho hầu như tất cả mọi loại models: tuyến tính, phi tuyến, nonparametric và tổ hợp của chúng, bao gồm mạng neural, classification & regression trees, classification & regression rules, radial basis functions, Bayesian networks, và hầu hết tất cả các họ models có thể tưởng tượng ra được. Thêm nữa, VC-dimension cũng là con số đánh giá rất tốt khả năng “khớp” dữ liệu của một lớp models, tốt hơn số tham số của models. Có các ví dụ models với 1 tham số mà có VC-dimension vô hạn, do đó khớp bất kỳ tập mẫu nào. Cũng có các models với ti tỉ tham số nhưng chỉ có VC-dimension nhỏ … Với một số họ models nhất định thì VC-dimension bằng tổng số tham số, ví dụ như các linear regression/discriminant models.

Vapnik và Chervonenkis dùng VC-dimension trong các bất đẳng thức chặn lỗi cho một lớp models cho trước. Cũng như trong PAC-learning, các chặn của họ không phụ thuộc vào phân bố của dữ liệu, phân bố nào cũng được. Bài báo của Blumer et al. áp dụng ý tưởng và vài kỹ thuật của họ vào PAC-learning.

5.2. Toán học của VC-dimension và vài thuộc tính

Lớp khái niệm ${\mathcal H}$ là một tập các hàm số ${h: \Omega \rightarrow \{0,1\}}$ . Mỗi hàm số có thể xem là một tập con của ${\Omega}$ : tập các phần tử của ${\Omega}$ được hàm số gán nhãn bằng ${1}$ . Với một tập mẫu ${S \subseteq \Omega}$ bất kỳ, định nghĩa ${\Pi_{\mathcal H}(S) = \{ h \cap S : h\in\mathcal H\}}$ . Như vậy ${\Pi_{\mathcal H}(S)}$ là tập tất cả các tập con ${X \subseteq S}$ sao cho tồn tại một giả thuyết ${h}$ “cắt” ${S}$ ra thành ${X}$ (nhãn = 1) và ${S-X}$ (nhãn = 0). Ta gọi ${\Pi_{\mathcal H}(S)}$ là tập các “hành vi” (behaviors) của ${\mathcal H}$ trên ${S}$ (còn gọi là tập các dichotomies).

Tập mẫu ${S}$ bị ${\mathcal H}$ băm nát như tương Tàu bởi ${\mathcal H}$ nếu ${\Pi_{\mathcal H}(S)}$ là tập tất cả các tập con của ${S}$ . Nói cách khác, ${S}$ bị băm nát như tương Tàu nếu, cho một tập con ${X \subseteq S}$ bất kỳ ta luôn tìm được một giả thuyết ${h}$ “cắt” ${S}$ ra thành ${X}$ (nhãn = 1) và ${S-X}$ (nhãn = 0).

VC-dimension của ${\mathcal H}$ , ký hiệu là ${\text{VC}(\mathcal H)}$ là kích thước lớn nhất của một tập mẫu bị ${\mathcal H}$ băm nát. (Bỏ “như tương Tàu” đi cho đỡ mỏi tay.) Để hiểu rõ, bạn hãy tự giải thích một cách trực quan các khẳng định sau đây:

${\mathcal H}$ là tập các nửa đường thẳng mở bên trái trên trục thực, ${\text{VC}(\mathcal H) = 1}$
${\mathcal H}$ là tập các đoạn đóng trên trục thực, ${\text{VC}(\mathcal H) = 2}$
${\mathcal H}$ là tập các tập nhiều nhất ${k}$ đoạn đóng trên trục thực, ${\text{VC}(\mathcal H) = 2k}$
${\mathcal H}$ là tập các nửa mặt phẳng, ${\text{VC}(\mathcal H) = 3}$
${\mathcal H}$ là tập các nửa không gian (half-spaces) của ${\mathbb R^d}$ , ${\text{VC}(\mathcal H) = d+1}$
${\mathcal H}$ là tập các hình cầu của ${\mathbb R^d}$ , ${\text{VC}(\mathcal H) = d+1}$
${\mathcal H}$ là tập các axis-parallel rectangles, ${\text{VC}(\mathcal H) = 4}$
${\mathcal H}$ là tập các đa giác lồi d đỉnh trên mặt phẳng, ${\text{VC}(\mathcal H) = 2d+1}$
${\mathcal H}$ là tập các tổ hợp logic của nhiều nhất ${k}$ khái niệm trong một lớp khái niệm ${\mathcal C}$ cho trước, nếu ${\text{VC}(\mathcal C)}$ hữu hạn thì ${\text{VC}(\mathcal H)}$ hữu hạn.
${\mathcal H}$ là tập các tập các đoạn đóng trên thục thực, hoặc tập các tập mở (theo nghĩa hình topo), hoặc tập các Borel sets, thì ${\text{VC}(\mathcal H) = \infty}$

Lemma 2 (Bổ đề Sauer) Định nghĩa ${\Pi_{\mathcal H}(m) = \max\left( |\Pi_{\mathcal H}(S)| : |S| = m \right)}$ . Nếu ${\text{VC}(\mathcal H) = d}$ thì
$\displaystyle \Pi_{\mathcal H}(m) \leq \Phi_d(m) = \sum_{i=0}^d \binom{m}{d} \leq \left( \frac{em}{d} \right)^d = O(m^d)$

Như vậy, bổ đề này cho ta biết nếu VC-dimension của lớp giả thuyết là hữu hạn thì ${|\Pi_{\mathcal H}(m)|}$ sẽ bị chặn trên bởi một đa thức khi ${m}$ đủ lớn. Kết quả này khá phản trực quan. Chú ý rằng, nếu VC-dimension là vô hạn thì ta luôn có ${|\Pi_{\mathcal H}(m)| = 2^m}$ .

Proof: Quy nạp theo ${m+d}$ . Khi ${m=0}$ thì dĩ nhiên bổ đề đúng. Khi ${d=0}$ thì lớp hàm số ${\mathcal H}$ gán tất cả ${\Omega}$ cùng một giá trị (0 hoặc 1), do đó ${|\Pi_{\mathcal H}(m)| = 1 = \Phi_0(m)}$ .

Xét trường hợp tổng quát ${m,d>0}$ , một tập mẫu ${S \subseteq \Omega}$ bất kỳ gồm ${m}$ mẫu, và một phần tử ${s\in S}$ bất kỳ. Chú ý rằng ${\Pi_{\mathcal H}(S)}$ chẳng qua là một bộ các tập con của ${S}$ . Số thành viên trong ${\Pi_{\mathcal H}(S)}$ có thể tính bằng tổng của hai số hạng: một là tổng số các các tập con ${h \in \Pi_{\mathcal H}(S)}$ thỏa ${h \subseteq S-\{s\}}$ , hai là các tổng số các tập con ${h \in \Pi_{\mathcal H}(S)}$ sao cho ${h \subseteq S-\{s\}, h \cup \{s\} \in \Pi_{\mathcal H}(S)}$ .

Dùng ý tưởng trên, định nghĩa

$\displaystyle \mathcal H' = \{ h \in \Pi_{\mathcal H}(S) : s \notin h, h \cup \{s\} \in \Pi_{\mathcal H}(S) \}$

Ta có ${|\Pi_{\mathcal H}(S)| = |\Pi_{\mathcal H}(S-\{s\})| + |\mathcal H'| = |\Pi_{\mathcal H}(S-\{s\})| + |\Pi_{\mathcal H'}(S)|}$ . Dễ thấy rằng ${\text{VC}(\mathcal H') \leq d-1}$ vì nếu ${\mathcal H'}$ băm nát một tập ${X}$ nào đó thì ${\mathcal H}$ sẽ băm nát ${X \cup \{s\}}$ . Áp dụng giả thuyết quy nạp, ta kết luận:

$\displaystyle |\Pi_{\mathcal H}(S)| \leq \Phi_d(m-1) + \Phi_{d-1}(m) = \Phi_d(m)$

$\Box$

(Xem thêm bài này tôi chứng minh bổ đề Sauer bằng cách khác, có lẽ “sạch sẽ” hơn chứng minh trên.)

5.3. Định lý Valiant cho các lớp khái niệm vô hạn (nhưng có VC-dimension hữu hạn)

Theorem 3 Tồn tại một hằng số ${c_0>0}$ sao cho: nếu learner có thể đưa ra một giả thuyết ${h \in \mathcal H}$ nhất quán với ${m \geq \frac{c_0}{\epsilon}\left(\log\left(\frac 1 \delta\right) + \text{VC}(\mathcal H)\log\left(\frac 1 \epsilon\right) \right)}$ mẫu (i.d.d.) thì learner là một PAC-learner.

Proof: Đây là một định lý tuyệt vời về mặt kỹ thuật. Nó khẳng định điều tôi đã biết: cùng một cây Ramirez trong tay John Williams thì khác xa trong tay NQH.

Giống như trong định lý Valiant trường hợp lớp giả thuyết hữu hạn, ta chỉ cần chặn trên xác suất sự kiện “tồi” sau đây xảy ra:

${B}$ : sự kiện tồn tại một giả thuyết tồi ${h \in \mathcal H}$ nhất quán với ${c}$ (Nhớ rằng giả thuyết tồi là giả thuyết có lỗi ${> \epsilon}$ .)

Thay vì chặn xác suất ${B}$ xảy ra, ta sẽ chặn nó bằng xác suất một sự kiện khác dễ “nắm bắt” hơn. Với một tập mẫu ${S}$ bất kỳ, gọi ${M(h,S)}$ là tổng điểm trong ${S}$ mà ${h \neq c}$ . Bây giờ, gọi ${S = \{ \mathbf x_1, \dots, \mathbf x_m\}}$ là training set. Giả sử ta lấy thêm ${m}$ mẫu nữa ${S' = \{\mathbf x'_1, \dots, \mathbf x'_m\}}$ (các “mẫu ma” này chỉ là công cụ phân tích, không phải ta lấy thêm mẫu thật sự khi chạy thuật toán). Định nghĩa một sự kiện thứ hai:

${C}$ : sự kiện tồn tại một giả thuyết ${h \in \mathcal H}$ sao cho ${M(h,S)=0}$ (nghĩa là ${h}$ vẫn nhất quán với ${c}$ trên ${S}$ ) nhưng ${M(h,S') > m\epsilon/2}$ .

Dễ chứng minh rằng, nếu ${m \geq 8/\epsilon}$ thì ${\text{Prob}[C | B] \geq 1/2}$ dùng bất đẳng thức Chernoff, do đó ${\text{Prob}[B] \leq 2\text{Prob}[C]}$ . Giả sử ta thảy ${m}$ đồng tiền xấp ngửa với xác suất ${1/2}$ và tráo ${\mathbf x_i}$ với ${\mathbf x'_i}$ nếu đồng tiền thứ ${i}$ là ngửa. Gọi hai tập mẫu kết quả là ${T}$ và ${T'}$ . Định nghĩa một sự kiện thứ ba:

${D}$ : sự kiện tồn tại một giả thuyết ${h \in \mathcal H}$ sao cho ${M(h,T)=0}$ (nghĩa là ${h}$ vẫn nhất quán với ${c}$ trên ${T}$ ) nhưng ${M(h,T') > m\epsilon/2}$ .

Do tính i.i.d. của ${S}$ và ${S'}$ , dễ thấy rằng ${C}$ và ${D}$ có xác suất bằng nhau. Cố định ${S}$ và ${S'}$ và xét một giả thuyết ${h}$ bất kỳ. Để cho ${M(h,T)=0}$ và ${M(h,T') \geq m\epsilon/2}$ thì phải có ít nhất ${r \ge m \epsilon/2}$ chỉ số ${i}$ sao cho ${h({\bf x}_i) \neq h({\bf x}'_i)}$ , và ít nhất ${r}$ đồng tiền ra xấp/ngửa sao cho phần đúng nhảy vào ${T}$ và phần sai nhảy vào ${T'}$ . Do đó

$\displaystyle \text{Prob}[M(h,T)=0, M(h,T') \ge m\epsilon/2 \ | \ S, S'] \leq 2^{-r} \leq 2^{-m\epsilon/2}$

Thay ${\text{Prob}[D]}$ bằng

$\displaystyle E_{S,S'}\left( \text{Prob}[\exists h \in \mathcal H, M(h,T)=0, M(h,T') \ge m \epsilon / 2 \ | \ S, S'] \right)$

Sau đó, ta có thể thay ${\mathcal H}$ bằng ${\Pi_{\mathcal H}(S \cup S')}$ và suy ra ${\text{Prob}[D]}$ bằng với

$\displaystyle E_{S,S'}\left( \text{Prob}[\exists h \in \Pi_{\mathcal H}(S \cup S'), M(h,T)=0, M(h,T') \geq m\epsilon/2 \ | \ S, S'] \right)$

Áp dụng union bound cho ta

$\displaystyle \text{Prob}[D] \leq |\Pi_{\mathcal H}(S \cup S')| 2^{-m\epsilon/2}$

Với sự giúp đỡ của bổ đề Sauer trong mục trước, phần còn lại chỉ là cơ bắp. $\Box$

6. Một chặn dưới cho độ phức tạp mẫu.

Trong các đề mục 4 và 5, chúng ta đã thấy các điều kiện đủ để learner là PAC-learner: chỉ cần lấy đủ số mẫu và (nếu có thể) đưa ra một giả thuyết nhất quán với các mẫu này. Có hai câu hỏi tự nhiên: (1) nếu không thể đưa ra một giả thiết nhất quán với mẫu thì sao? (Vì nhiều lý do, trên thực tế khả năng này hoàn toàn có thể xảy ra. Chúng ta sẽ quay lại với nó trong bài tới.) và (2) tổng số mẫu cần thiết là bao nhiêu? Định lý dưới đây trả lời câu hỏi số 2 này.

Theorem 4 tồn tại một không gian mẫu ${\Omega}$ , một phân bố ${\mathcal D}$ trên đó, và một lớp giả thuyết ${\mathcal C}$ với VC-dimension bằng ${d}$ thỏa mãn điều kiện sau đây: bất kỳ learner nào — nếu chỉ lấy ${d/2}$ mẫu — thì ${\text{Prob}[ \text{err}_\mathcal D(h) > 1/8] > 1/7}$ .

Như vậy, nếu chỉ lấy ${d/2}$ mẫu thì learner không thể PAC-learn lớp khái niệm trên với tham số lỗi ${1/8}$ và tham số độ tin cậy ${1/7}$ .

Đại khái, chứng minh định lý trên rất đơn giản: xét một tập con ${S}$ của ${\Omega}$ bị băm nát bởi ${\mathcal C}$ . Gán ${\mathcal D}$ là uniform distribution trên tập con này (phần ngoài tập con có density bằng không). Không mất tính tổng quát ta có thể giả sử ${\mathcal C}$ chính là tập tất cả các tập con của ${S}$ . Như vậy, mỗi mẫu trong ${S}$ thuộc về một nửa số khái niệm và không thuộc về một nửa số khái niệm còn lại. Giả sử ta lấy một khái niệm một cách ngẫu nhiên, và learner chỉ thấy một nửa của ${S}$ , thì xác suất mà learner đoán sai trong nửa còn lại sẽ ít nhất là ${1/4}$ . Do đó, tồn tại ít nhất một khái niệm mà learner đoán sai với xác suất ${1/4}$ . Từ đó, dùng bất đẳng thức Markov, kết thúc định lý không khó khăn gì.

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, Vapnik-Chevonenkis. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

6 Comments

Nguyễn Xuân Long

Posted 18/07/2008 at 12:11 pm | Permalink

Hi bác Hưng, very nice presentation, again. Tôi có một số comments về Định lý 5.3.

1. Khái niệm VC-dimension đúng là rất độc đáo, original, đặc biệt là tính chất tổ hợp của chúng và liên hệ trực tiếp đến statistical efficiency (theo Định lý 5.3). Tuy vậy VC dimensions có một số hạn chế fundamental, ở chỗ phần nhiều các function classes hữu ích trên thực tế lại có infinite VC dimensions. Khái niệm tốt hơn để đo độ phức tạp của function classes là khái niệm entropy của Kolmogorov (liên quan đến packing và covering numbers). Không biết bác Hưng có dự định nói về khái niệm này không.

2. Một kết quả rất thú vị là covering number của VC function class thì được chặn trên bởi một đa thức (đối với 1/delta, ở đây delta là kich cở của quả bóng con dùng để cover theo định nghĩa của covering number). Như vậy nếu VC dimension hữu hạn thì entropy cũng vậy, nhưng ngược lại không đúng.

3. Trong một số comments trước tôi nói rằng bên thống kê họ đã phái triển rất sâu rộng khái niệm PAC, và có thể minh họa chính bằng khái niệm entropy này. Cuối thập niên 70 có nhiều kết quả quan trọng để (nói theo ngôn ngữ PAC) để chứng minh PAC-learnability cho các lớp hàm số dựa theo khái niệm entropy (e.g., ví dụ, sử dụng Dudley’s entropy integral). Các kết quả tương tự như Định lý 5.1 ở trên: Ta có thể chặn trên \epsilon theo sample size m (từ Định lý 5.1) .Điều thú vị nhất là các chặn trên này cũng trùng với chặn dưới luôn (minimax bound: với một function class đây là chặn worse-case tốt nhất có thể được với mọi thuật toán learning).

4. Khái niệm entropy (khác với Shannon’s entropy) xuất hiện đầu tiên bên approximation theory của Russian school (xem vi’ du.:
http://www.procul.org/blog/2006/05/24/cac-bai-bao-kinh-oi%e1%bb%83n-khmt-9-birman-and-solomjaks-1967-paper/
)
và có liên hệ mật thiết với information theory.

5. Khái niệm Shannon’s entropy và approximation entropy thực ra có liên hệ với nhau cực kỳ hay, nếu ta sử dụng generalized Bayesian viewpoint. (Tong Zhang gần đây có một bài báo rất thú vị về cái này trên Annals of Statistics, 2006). Hy vọng một dịp nào đó tôi sẽ nói thêm về cái này.

6. Vapnik thường được gắn liền với statistical learning theory như một cha đẻ. Điều này đúng.
Không chỉ trong learning theory, đóng góp của VC theory có thể coi là original trong theoretical statistics, góp phần tạo ra subfield gọi là empirical process theory trong statistics. Nếu Valiant đuợc Turing award, thì tôi nghĩ Vapnik cũng nên được một cái Nhưng sách của Vapnik thường không cân bằng và không ghi nhận xứng đáng các khái niệm khác trong empirical process theory mà tôi nghĩ Vapnik biết rõ là sẽ rất hữu ích và powerful hơn cho learning theory. Có cảm tưởng ông này là một người egoistic. Một quyển sách cân bằng hơn về khái niệm VC theo tôi là của van der Vaart và Wellner (Weak convergence and empirical processes). Quyển này nói kỹ về VC theory, and much much more. Và ứng dụng không chỉ trong classification như PAC’s setting mà trong estimation nói chung.

7. Tôi cảm tưởng dân FOCS/STOC làm về learning theory chưa có exposure nhiều về empirical process theory (ngoài lý thuyết VC ra). Tuy vậy dân COLT với background statistics những năm gần đây có sự dịch chuyển đáng kể từ khái niệm VC sang sủ dụng khái niệm entropy.

8. Qua proof cu?a Định lý 5.3 có thể suy ra là NQH cũng có một cây Ramirez với xác suất cao.

Reply
Ngô Quang Hưng

Posted 18/07/2008 at 5:33 pm | Permalink

Hi bác Long,

Vụ Kolmogorov entropy chắc phải chờ bác viết thôi. Đọc Vapnik review “history of learning theory” thấy rất … tếu . BTW, tôi đọc sách Intro to COLT của Kearns và Vazirani cũng thấy cite Dudley (quyển “A Course on Empirical Processes”).

Valiant sẽ được Turing vì nhiều đóng góp khác chứ không chỉ có PAC (#P, superconcentrator, algebraic complexity, mind circuit, evolvability, hollographic algorithms, v.v.) Hầu như cứ vài năm là Valiant lại có một ý tưởng original mở ra một field mới.

Cảm ơn bác giới thiệu quyển Empirical processes. Các bài báo về PAC trên FOCS/STOCS thật ra has little to do with learning, they’re all about hardness of approximation. Tôi không ngạc nhiên nếu họ không biết statistics nhiều. COLT mới là về learning (from a TCS viewpoint) thật, vì thế COLT community mới rẽ nhánh ra khỏi STOC/FOCS.

Reply
Chính Minh

Posted 09/02/2009 at 6:30 am | Permalink

Thưa chú !

Cháu là một người làm bên Công Nghệ Thông Tin, cụ thế là hướng theo Software Engineering, Information System, Business Management và Báo Chí Truyền Thông

Tình cờ đi qua WebBlog này, tuy mới chỉ đọc lướt nhanh các bài viết này, cháu nhận thấy rằng : Các bài viết trên, quả là chứa đứng nhiều lý thuyết về toán học, trí tuệ nhân tạo, thuật toán, thi quốc tế, các kiểu… Ấy thế mà, cái chứng minh cần thiết, mà nhiều người mong chờ, nó ko làm được là : nó phải chứng tỏ được nó tham ra quá quá trình thế nào, giúp ích ra sao cho cuộc sống con người đây ?? – Quá trình đó, phải chăng là mờ nhạt,

Rất mong chú có câu trả lời, dù chỉ đôi dòng ý nghĩa

Reply
Ngô Quang Hưng

Posted 09/02/2009 at 7:39 am | Permalink

@Chính Minh: để trả lời câu hỏi của bạn, tôi cần hiểu câu hỏi đã.

Thế nào là “giúp ích cho cuộc sống con người”?

1. Hồi Cardano giải phương trình bậc 3 có “giúp ích cho cuộc sống con người” không?

2. Google có giúp ích cho cuộc sống con người không?

Nếu câu trả lời của bạn cho 1 hoặc 2 là “có” thì câu trả lời của tôi (cho câu hỏi của bạn) là “có”, “nó” có giúp ích. (Tại sao liên quan đến Google, tại vì các thuật toán ML ít nhiều phải dùng boosting và support vector machines, những thứ đến từ lý thuyết học máy như đã và sẽ trình bày.)

Nếu câu trả lời của bạn cho cả hai câu 1 và 2 ở trên là “không”, thì câu trả lời của tôi (cho câu hỏi của bạn) là “không”, “nó” không giúp ích gì cho cuộc sống của bạn cả.

Tôi không biết nó có giúp ích cho bạn không; Tôi biết rằng “nó” giúp ích cho cuộc sống của tôi.

Reply
Ngô Quang Hưng

Posted 23/09/2010 at 4:19 pm | Permalink

Bác Long,

Tôi đang (định) đọc bài này của Bartlett và Mendelson về Rademacher và Gaussian complexities. Bác có nhận xét gì về R/G complexities và tương quan với VC dimension không? (Để tôi tiết kiệm thời gian ) Sau bài của Bartlett-Mendelson thì có phát triển gì tiếp theo về R/G complexities không?

Reply
XuanLong Nguyen

Posted 23/09/2010 at 6:43 pm | Permalink

Bác Hưng,
Câu trả lời nằm ở 1. và 2. của comment đầu tiên Classification error được chặn bởi Rademacher/Gaussian complexity, cái này lại được chặn tiếp bởi covering number.

Sau cái này thì theo tôi hiểu có một số phát triển về local complexity, thay vì global complexity, qua đó có thể tìm được faster error rate nếu hypothesis class đủ nhỏ.

Lúc nào rỗi bác đọc mấy cái lower bound papers nhé. Dân statistics nói chung không quen với combinatorial thinking nhiều nên rất cần fresh look từ những chuyên gia combinatorics.

Reply

HM4 — Độ phức tạp mẫu và VC-dimension

6 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ý