Thư viện bài tháng 07 năm 2008

“Học máy” từ góc nhìn của lý thuyết tính toán (4)

Ngô Quang Hưng | 18 tháng 07, 2008 | Bản để in Bản để in

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 hardness của một số vấn đề học máy khác, ví dụ Blum và Rivest chứng minh rằng training một neural network với 3 nodes là NP-Hard (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-hard chẳng hạn) không đáng ngạc nhiên (dù không dễ dàng). 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:

Đị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.

Chứng minh. Gọi một giả thuyết gọi là giả thuyết tồi nếu

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

Như vậy, 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 ≤ 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 ≤ |\mathcal H|(1-\epsilon)^m. Ép vế cuối cùng nhỏ hơn hoặc bằng \delta là xong!
QED.

Đị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 về mặt toán học 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 trong 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 hypothesis “đủ 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-learner 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

\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 bài 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 classification 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 statistical models. 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 \to \{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).

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

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ì

\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 hypothesis 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.
Chứng minh. 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

\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:
|\Pi_{\mathcal H}(S)| \leq \Phi_d(m-1) + \Phi_{d-1}(m) = \Phi_d(m)

QED.

(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)

Định lý. 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.

Chứng minh. Đâ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 (đâ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>8/\epsilon thì \text{Prob}[C | B] \geq 1/2 dùng bất đẳng thức Markov, và 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')>m\epsilon/2 thì phải có ít nhất r>m\epsilon/2 chỉ số i sao cho h(\mathbf x_i) \neq h(\mathbf 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 đó

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

Thay \text{Prob}[D] bằng
E_{S,S'}\left( \text{Prob}[\exists h \in \mathcal H, M(h,T)=0, M(h,T') > 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
E_{S,S'}\left( \text{Prob}[\exists h \in \Pi_{\mathcal H}(S \cup S'), M(h,T)=0, M(h,T')>m\epsilon/2 \ | \ S, S'] \right)

Áp dụng union bound cho ta
\text{Prob}[D] \leq |\Pi_{\mathcal H}(S \cup S')| 2^{-m\epsilon/2}

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

QED.

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.

Định lý: 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ì.

Chuyên mục: Lý thuyết tính toán & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (4) »

Phát triển và lụi tàn của CAPTCHA

Ngô Quang Hưng | 16 tháng 07, 2008 | Bản để in Bản để in

Một bài viết thú vị từ Computer World. Ngoài reCAPTCHA và 3-D CAPTCHA ra, còn ý tưởng nào khác giải quyết vụ này không? Một số dự án đề nghị users giải toán vi tích phân gì đó (thay vì điền chữ như CAPTCHA). Dĩ nhiên, máy tính sẽ tốt hơn người trong tác vụ tính tích phân :-) .

Đây là một đề tài rất hấp dẫn, xứng đáng một vài luận án tiến sĩ. Có một cái vòng luẩn quẩn: ta muốn dùng máy và thuật toán AI để sản sinh ra các objects mà người dễ nhận ra còn máy thì không. Trong khi đó, mục tiêu cuối cùng của AI lại là tối thiểu hóa khoảng cách giữa máy và người. Do đó, AI càng phát triển thì bài toán này càng khó giải quyết dùng AI. Dân làm mật mã sẽ bảo: dùng một authentication scheme nào đó. Nhưng vấn đề privacy sẽ nảy sinh.

Một tin không liên quan: giáo sư Papert, người bị đụng xe ở Hà Nội hồi 2006 và bất tỉnh cả tháng trời đang … học để trở thành Papert trở lại.

Chuyên mục: Bảo mật và mật mã học & Trí tuệ nhân tạo | Bình luận (3) »

Dưới đáy tháp Ivory

Ngô Quang Hưng | 15 tháng 07, 2008 | Bản để in Bản để in

Tờ Atlantic mới có một bài hay tuyệt!!! Nhớ đọc hết toàn bài. (Không biết các bạn đọc đã từng dạy hay học tại chức có tìm thấy một vài cảm giác quen thuộc không?)

Trích một đoạn:

I wonder, sometimes, at the conclusion of a course, when I fail nine out of 15 students, whether the college will send me a note either (1) informing me of a serious bottleneck in the march toward commencement and demanding that I pass more students, or (2) commending me on my fiscal ingenuity—my high failure rate forces students to pay for classes two or three times over.

What actually happens is that nothing happens. I feel no pressure from the colleges in either direction. My department chairpersons, on those rare occasions when I see them, are friendly, even warm. They don’t mention all those students who have failed my courses, and I don’t bring them up. There seems, as is often the case in colleges, to be a huge gulf between academia and reality. No one is thinking about the larger implications, let alone the morality, of admitting so many students to classes they cannot possibly pass. The colleges and the students and I are bobbing up and down in a great wave of societal forces—social optimism on a large scale, the sense of college as both a universal right and a need, financial necessity on the part of the colleges and the students alike, the desire to maintain high academic standards while admitting marginal students—that have coalesced into a mini-tsunami of difficulty. No one has drawn up the flowchart and seen that, although more-widespread college admission is a bonanza for the colleges and nice for the students and makes the entire United States of America feel rather pleased with itself, there is one point of irreconcilable conflict in the system, and that is the moment when the adjunct instructor, who by the nature of his job teaches the worst students, must ink the F on that first writing assignment.

Chuyên mục: Giáo dục | Bình luận (6) »

“Học máy” từ góc nhìn của lý thuyết tính toán (3)

Ngô Quang Hưng | 14 tháng 07, 2008 | Bản để in Bản để in

3. Mô hình có lẽ xấp xỉ đúng (Probably Approximately Correct) (viết tắt là mô hình PAC)

Hạn chế lớn nhất của mô hình nhất quán, như đã nói, là nó không đếm xỉa gì đến khả năng dự đoán tương lai. Một hạn chế thứ hai là trên thực tế training data ta thường có được theo một phân bố xác suất (probability distribution) nào đó. Ví dụ như trong bộ lọc spam emails, tần suất xuất hiện của cùng một (loại) spam email khá là lớn (Viagara, lừa đảo Nigeria, v.v.), chứ không phải mỗi email chỉ xuất hiện một lần như ta mô tả mô hình nhất quán. Phân bố xác suất này không được nắm bắt trong mô hình nhất quán. Mô hình PAC sẽ vượt qua được hai hạn chế chính kể trên.

3.1. Về mặt trực quan, mô hình PAC nói như sau. Thuật toán ML của ta có thể lấy mẫu độc lập từ một phân bố xác suất \mathcal D nào đó trên miền \Omega. Mỗi mẫu đều có nhãn. Sau đó, thuật toán ML sẽ đưa ra một giả thuyết h \in \mathcal C (lớp khái niêm cho trước) sao cho chúng ta rất tin rằng h rất gần với khái niệm cần học c.

Làm thế nào để đo xem h có “gần” c hay không? Định nghĩa hàm lỗi như sau:

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

Nói cách khác, “mức độ lỗi” của h là xác suất mà h đưa ra câu trả lời khác c. Chú ý là ta đo lỗi của h dùng cùng một phân bố xác suất mà training data được lấy mẫu. (Nôm na: bắt lỗi mà dùng khác phân bố xác suất thì giống như bạn cho tôi chỉ toàn Nigeria spam emails, rồi sau đó bắt lỗi tôi rằng tôi không biết Viagra emails cũng là spam; vậy thì … tội cho tôi quá!)

Giá trị \text{err}_{\mathcal D}(h) càng nhỏ thì h và c càng gần nhau. Đây chính là thước đo khả năng dự đoán tương lai của thuật toán ML trong mô hình PAC. Thước đo này được tính trên toàn bộ domain \Omega, nó bao gồm tất cả những examples không có trong training data set.

Làm thế nào để đo “độ tin cậy“? Chúng ta sẽ yêu cầu h và c rất gần với xác suất rất cao; xác suất này còn gọi là độ tin cậy vào thuật toán ML. (Độ tin cậy được đo dựa trên một phân bố có các thành tố của \mathcal D và cả các bits ngẫu nhiên mà thuật toán ML của chúng ta dùng. Điểm này sẽ rõ hơn khi ta xét các ví dụ trong các bài về sau.)

Đọc tiếp toàn bài »

Chuyên mục: Lý thuyết tính toán & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (9) »

“Học máy” từ góc nhìn của lý thuyết tính toán (2)

Ngô Quang Hưng | 10 tháng 07, 2008 | Bản để in Bản để in

Trong bài trước ta đã định nghĩa cụ thể mô hình nhất quán. Có một vài điểm tinh tế cần nói rõ hơn.

Thứ nhất, tổng số concepts trong lớp concepts đã biết \mathcal C thường là rất lớn, có thể là hàm mũ của m, có thể vô hạn. Thứ hai, khi ta nói thuật toán ML cần “đưa ra” một giả thuyết h \in \mathcal C thì ta đã ngầm định một cách biểu diễn h nào đó. Nhớ rằng, mỗi concept là một hàm số từ \Omega vào \{0,1\}. Kích thước của \Omega rất lớn (như tổng số emails trong bài spam classification), không thể nào biểu diễn một concept bằng một lookup table được. Tổng số các concepts có thể có là 2^{|\Omega|}, do đó “chặn thông tin” (information theoretic bound) cho ta biết sẽ có rất nhiều concepts cần ít nhất \Theta(|\Omega|) bits để biểu diễn, không thể nhỏ hơn. (Đấy là trường hợp domain hữu hạn, nếu vô hạn thì còn tệ hơn nữa.)

Vì thế, yêu cầu “khái niệm đang học thuộc về một lớp các khái niệm cho trước” là cần thiết. Nói cách khác, lớp các khái niệm cho trước này phải “vừa vừa phải phải” thôi, phức tạp quá ai mà học cho được! Nhắc lại, ta ngầm định rằng khi nói “cho trước \mathcal C” ta cũng “cho” luôn cả một cách biểu diễn một khái niệm bất kỳ trong \mathcal C. Khái niệm cần học c có biểu diễn kích thước |c|.

Thứ hai, ta giả sử mỗi phần tử của \Omega có thể biểu diễn bằng \Theta(n) bits. Ví dụ, \Omega có thể là \mathbb R^n hoặc một vector gồm n từ khóa trong một email.

Thứ ba, khi yêu cầu thuật toán ML chạy trong thời gian đa thức, ta muốn nói là đa thức của các tham số m (tổng số examples trong training set), n (kích thước một phần tử trong domain), và |c| (kích thước của biểu diễn khái niệm đang học).

Đoạn trên có lẽ là khó hiểu khi đọc lần đầu. Tôi viết xong rồi cũng không hiểu thế nào là “cho trước”?. Ta hãy xét một vài ví dụ, sau đó bạn đọc quay lại đoạn ở trên chắc là sẽ thấy dễ hiểu hơn.

Đọc tiếp toàn bài »

Chuyên mục: Lý thuyết tính toán & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (1) »

“Học máy” từ góc nhìn của lý thuyết tính toán (1)

Ngô Quang Hưng | 09 tháng 07, 2008 | Bản để in Bản để in

Computational Learning Theory (COLT) bắt đầu từ bài báo kinh điển của Valiant hồi 1984 trên tờ CACM. (Thế mới thấy CACM bây giờ chán, không còn thấy original research articles mấy nữa. Hy vọng là cố gắng cải tổ của Moshe Vardi mới đây sẽ làm CACM thú vị hơn, thành một tờ Science cho ngành CS). Tôi quan tâm đến COLT trong quá trình tìm hiểu xem làm thế nào để mô tả về mặt toán học khái niệm “learnability” (của máy, và có khi cả của người). Ví dụ: làm thế nào để biết/chứng minh rằng một vấn đề nào đó là không thể learn được.

Chuỗi bài này có thể xem là nhật ký của tôi trong hành trình tìm hiểu này. Góc nhìn của COLT đến vấn đề learning là góc nhìn của một nhà lý thuyết tính toán và độ phức tạp. Vì thế, COLT nhảy vào các vấn đề tractability (theo nghĩa lý thuyết tính toán), độ phức tạp không/thời gian, … của learning ngay lập tức. Đây là những vấn đề mà các cách tiếp cận khác hầu như không đề cập. Ví dụ: các quyển The Nature of Statistical Learning Theory của Vapnik hay Pattern Recognition and Machine Learning của Bishop không có chương nào nói về tractability của learning problem(s). Có cả pros lẫn cons của cách tiếp cận COLT, như chúng ta sẽ thấy trong hành trình.

Đọc tiếp toàn bài »

Chuyên mục: Lý thuyết tính toán & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (3) »

Du học sinh

Ngô Quang Hưng | 03 tháng 07, 2008 | Bản để in Bản để in

Xem cái này bên PhD Comics.

Chuyên mục: Dành cho du học sinh & Vui - Giải Trí | Bình luận »