Thư viện bài, chủ đề ‘Lý thuyết tính toán’

“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ì.

Chủ đề: Lý thuyết tính toán & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (2) »

“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 »

Chủ đề: 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 »

Chủ đề: 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 »

Chủ đề: 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) »

“Định lý sự đầy đủ” của Godel

Ngô Quang Hưng | 22 tháng 11, 2007 | Bản để in Bản để in

Bên gỡ rối tơ lòng, bạn Thắng hỏi:

Trong một cuốn sách em thì nó nói rằng nếu có cái điều kiện gì gì đó thì A |– B sẽ suy ra A |= B. Nhờ anh chỉ giùm cho em thấy sự khác biệt giữa 2 khái niệm A|–B và A|== B này cái
…
rồi có Gentzen type và Hilbert type gì gì đó …

Tôi không biết nhiều lắm về các loại deductive calculus, nhưng cũng cố thử trả lời bằng những gì tôi biết, qua một năm học logic cổ điển từ khoa Toán. Trong khi đó nhứng gì bạn Thắng và đa số dân KHMT đọc về logic (tôi đoán là) lại hướng đến logic cho AI cổ điển (hoặc databases), có nhiều chi tiết kỹ thuật hơn những gì tôi biết. Logic dành cho bên Toán không quan tâm đến implementation efficiency của deductive systems, còn logic cho AI và database buộc phải quan tâm vì lý do hiển nhiên. Các bác nào làm AI cổ điển (chắc hơi hiếm) và database giứp giùm nhé!

Đoạn dưới đây chỉ nói về first-order logic (và trường hợp đặc biệt của nó là propositional logic).

A \vdash \varphi thường được dùng để nói rằng “mệnh đề” \varphi có thể suy ra (deduce) được từ các mệnh đề trong tập mệnh đề A cùng với một tập hợp \Lambda các tiên đề cho trước. (Chính xác hơn, thay vì “mệnh đề” thì phải dùng cụm từ well-formed formula (wff).)

Để thật sự biết là A \vdash \varphi hay không, ta phải có một số luật suy dẫn và một tập tiên đề. Tập tiên đề cùng với tập luật suy dẫn gọi là deductive calculus. Hai loại calculus chính là loại Gentzen và loại Hilbert. Loại Gentzen có ít tiên đề, nhiều luật, và (có vẻ) thích hợp hơn cho tính toán [các bác làm AI, automatic theorem proving confirm nhé]. Loại Hilbert có rất nhiều tiên đề (có thể vô hạn) nhưng lại có rất ít luật. Loại này thích hợp cho chứng minh toán học.

Deductive calculus chỉ là một tập hợp các luật cơ bắp. Ví dụ, luật modus ponens bảo \{ a, a \to b\} \vdash b, nghĩa là nếu đã có a và có a \to b thì ta có thể “suy ra” b. Vì chúng chỉ là luật cơ bắp, ta có thể lập chương trình cho máy tính dựa trên các luật này.

A \models \varphi thì phức tạp hơn nhiều. Nó đòi hỏi là dưới một “cấu trúc” bất kỳ nào thì \varphi cũng suy được từ A trong cấu trúc đó. Định nghĩa cấu trúc thỉ rắc rối, nhưng có thể lấy ví dụ đơn giản: có nhiều phép suy dẫn hay mệnh đề chỉ đúng cho cấu trúc số thực nhưng không đúng cho cấu trúc số tự nhiên, tỉ dụ như mệnh đề “với mọi x, tồn tại y sao cho x+y=0“.

Một deductive calculus gọi là “sound” nếu A \vdash \varphi dẫn đến A \models \varphi. Điều này hiển nhiên là cần thiết vì nếu không luật suy dẫn của ta bị hổng trong một nhánh nào đó của Toán học. Hầu hết các deductive calculus hữu dụng đều sound.

Ngược lại, Godel chứng minh được rằng, nếu ta chọn một deductive calculus đơn giản (kiểu Hilbert) với một số vô hạn các tiên đề và một luật suy dẫn duy nhất là luật modus ponens, thì cái calculus này còn “complete” nữa cơ, nghĩa là A \models \varphi thì dẫn đến A \vdash \varphi . (Cái calculus này cũng sound luôn, dễ chứng minh hơn completeness nhiều.)

Godel completeness theorem cho ta thấy rằng cái calculus nọ cực tốt: thay vì phải chứng minh rằng A \models \varphi dưới một cấu trúc bất kỳ (số nguyên, số thực, phức, nhóm, trường, vành, hình topo, combinatorics và vô hạn các “cấu trúc” có thể có), thì ta “chỉ cần” duy dẫn logic dùng hệ tiên đề nọ và luật modus ponens là có thể chứng minh được A \models \varphi

Chủ đề: Lý thuyết tính toán | Bình luận (4) »

Blessings and curses of dimensionality

Nguyễn Xuân Long | 09 tháng 03, 2007 | Bản để in Bản để in

Tôi muốn giới thiệu một bài báo thú vị của David Donoho với tựa đề: The blessings and curses of dimensionality. Donoho là một siêu sao trong ngành thống kê của thập niên 90, ông cũng là một cây viết thú vị. Các bài viết của Donoho dù technical hay không, thường tạo ra nhiều cảm hứng và nhiệt tình cho người đọc. Bài báo trên của Donoho là một lời kêu gọi sự chú ý của giới làm toán nói chung hãy quan tâm hơn và đóng góp các công cụ toán học đến những vấn đề xử lý dữ liệu hóc búa của thế kỷ 21. Đọc nó, và hy vọng bạn sẽ thấy đó cũng là lời kêu gọi đến những nhà khoa học máy tính của hôm nay và ngày mai.

Những vấn đề xử lý dữ liệu không hề xa lạ với dân KHMT chúng ta. Quả thật đó cũng chính là nồi cơm của chúng ta: Làm thế nào để “make sense of” luồng dữ liệu khổng lồ trên web, trong hệ thống máy, trong các sensor networks, trong genome của người và các sinh vật khác, các loại dữ liệu ở dạng text, ảnh, âm thanh, v.v. Làm thế nào để máy tính được grounded trong data mà không bị chết sặc. Những tiến bộ trong công nghệ thông tin — communication, networking, hardware, software, data structure và algorithms — đã tạo nên một cơ sở hạ tầng tuyệt vời để thu thập và biểu hiện dữ liệu. Song chưa đủ. Xử lý luồng dữ liệu khổng lồ như thế nào lại là một chuyện phức tạp hơn nhiều. Ở thế kỷ 21, rất nhiều ngành khoa học lý thuyết, tính toán và thực nghiệm phải cùng nhau xắn tay vào để giải quyết những vấn đề như vậy.

Dân KHMT cũng không lạ gì khái niệm “curses of dimensionality” do Richard Bellman sử dụng lần đầu tiên. Curses of dimensionality nói đến sự khó khăn trong việc giải quyết các bài toán liên quan đến high dimension. Một cách cụ thể, số lượng dimension của bài toán có thể là số lượng biến số liên quan, có thể do số lượng sensors dùng để thu thập data rất lớn. Tùy theo dạng dữ liệu khác nhau mà sensors ở đây cũng nên hiểu theo nghĩa rất linh động, có thể là các routers trong một network, các cameras, các websites, các pixels của từng hình ảnh, độ dài của chuỗi DNA và protein trong sinh học phân tử, v.v. Để xử lý data với dimension khổng lồ như trên với số lượng khổng lồ đòi hỏi tìm kiếm trong một state space lớn gấp nhiều lần, có thể theo đa thức hoặc hàm số mũ (exponential). Đó chính là curses of dimensionality. Đừng vội nghĩ exponential complexity mới là tồi tệ. Nếu thuật toán của bạn scan database N^2 lần, với số dimension N ở mức hàng chục triệu thì đã khó chấp nhận rồi.

Điều thú vị là high-dimension có nhiều blessings. Bạn hãy tự hỏi, tại sao con người ta luôn luôn phải đối mặt với rất nhiều sensory data (qua 7 giác quan) mà thường vẫn không bị tẩu hỏa nhập ma. Tất nhiên đây là một câu hỏi mở để ta cùng suy ngẫm. Trong toán học, một trong những yếu tố thuận lợi của high dimensions chính là khái niệm concentration of measure. Trong lý thuyết xác suất chúng ta đều biết law of large numbers: giá trị trung bình của các sự thể hiện ngẫu nhiên thường hội tụ về giá trị kỳ vọng của biến ngẫu nhiên (constant). Hay định luật central limit: Giá trị trung bình của các sự thể hiện ngẫu nhiên có hành vi giống như biến Gauss. Sâu hơn một chút, một hàm số được định nghĩa trên rất nhiều biến (high dimension), mà sự đóng góp của từng biến vào giá trị hàm số đều nhỏ, thì hàm số đó có hành vi giống như constant vậy. Kỳ thực rất nhiều hàm số mà chúng ta quan tâm trong cuộc sống đều có tính chất này. Trong hình học lồi (convex geometry), rất nhiều vật thể lồi trong high dimension thường có những tính chất phản trực quan: ví dụ một hình hộp trong không gian nhiều chiều có hình dạng rất khác một hình hộp ta biết trong 2 hay 3 chiều. Song những tính chất đó lại được tận dụng một cách hiệu quả để đưa ra những đáp án rất ngoạn mục cho các vấn đề liên quan đến high dimension.
[[Addition 04/03/07: Một quyển sách rất hay và dễ đọc giới thiệu về v/đ này: Keith Ball, Elementary introduction to convex geometry, ở đây .]]
Donoho còn liệt kê ra và dẫn chứng một số yếu tố blessings khác trong không gian nhiều chiều. Để có nó ta cần phải sử dụng các công cụ khác trong toán học.

Đây là một ví dụ của những bài báo mà khi đọc xong, tôi không khỏi cảm thấy mình thật là may mắn vì được sống trong một không gian rất nhiều chiều. Không phải vì mình đã nắm hết được hết các blessings kể trên, mà vì khả năng được tìm tòi và sử dụng các công cụ toán học đẹp đó để giải quyết các vấn đề rất thiết thực. Bring it on, your curses, dear Professor Bellman!

Chủ đề: Giới thiệu sách & Lý thuyết thông tin & Lý thuyết tính toán & Thuật Toán & Toán tối ưu & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (2) »

Lý thuyết tính toán trên mạng

Ngô Quang Hưng | 22 tháng 01, 2007 | Bản để in Bản để in

Bản nháp báo cáo của một workshop do NSF tài trợ.

Chủ đề: Lý thuyết tính toán & Mạng máy tính | Bình luận (4) »

Vài talks về lý thuyết mã mạng

Ngô Quang Hưng | 11 tháng 01, 2007 | Bản để in Bản để in

Talk của Nick Harvey (MIT), talk của Baochun Li (Toronto), talk của Yunnan Wu (Princeton). Trong đó talk của Baochun Li hay nhất.

Tôi sẽ viết tiếp chuỗi bài về lý thuyết mã mạng trong vài tuần tới.

Chủ đề: Lý thuyết thông tin & Lý thuyết tính toán & Mạng máy tính & Thuật Toán | Bình luận (4) »

Notices of the AMS: Kurt Godel

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

Lần trước tôi link về số đặc biệt cho Turing của tờ Notices mà quên link đến số đặc biệt cho Kurt Godel.

Chủ đề: Lý thuyết tính toán | Bình luận »

Notices of the AMS: Alan Turing

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

Issue mới của tờ Notices là số đặc biệt về Alan Turing. Liên quan nhất đến blog KHMT là bài Turing Thesis, Theo cùng tinh thần bài Chung Qui Chỉ Tại Cantor.

Chủ đề: Lý thuyết tính toán | Bình luận »

Các kết quả về tính không xấp xỉ được

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

Quyển Computers and Intractability: A Guide to the Theory of NP-Completeness của Garey và Johnson là tham khảo kinh điển về lý thuyết NP-đầy đủ. Trong 30 năm qua, Johnson vẫn tiếp tục viết các NP-complete columns để cho ta biết các cập nhật mới nhất về các bài toán NP-đầy đủ.

Hồi xưa, ta có thể viết một bài báo chứng minh một bài nào đó là NP-Hard. Nay thì 99.9% các kết quả loại này chỉ là một bổ đề trong phần appendix của một bài báo. Các chứng minh NP-hardness đã trở thành routine như kiểu tính tích phân (mặc dù tính tích phân không phải lúc nào cũng đơn giản!).

Ngày nay, khi đối chọi với một bài toán mới, để có thể đăng tải kết quả thì ngoài chuyện chứng minh là nó NP-hard ta thường phải làm thêm 2 việc nữa: (1) tìm một thuật toán xấp xỉ tốt, và (2) chứng minh rằng xấp xỉ bài này đến một tỉ lệ nhất định cũng NP-hard nốt. Công việc (2) được gọi là chứng minh “hardness of approximation”. (Ta có thể thay giả thiết P khác NP bằng một giả thiết khác trong complexity theory. Giả thiết “hot” nhất hiện nay là Unique Game Conjecture. Xem thêm ở Khot’s homepage, và bài này, bài này nữa.) Kỹ thuật chính để chứng minh các kết quả loại này là dùng Probabilistically Checkable Proofs.

Lẽ tự nhiên, column mới nhất của David Johnson nói về các kết quả loại này — một bước nhảy lượng tử từ NP-hardness lên NP-hardness of approximation. Muốn biết chi tiết hơn, đọc các bài [Trevisan 2004] và [Khot 2005].

Chủ đề: Lý thuyết tính toán & Thuật Toán | Bình luận »

Bài tổng quan về PCP

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

Tôi đã nhắc đến Probabilistically Checkable Proofs trên blog này. Năm ngoái, Irit Dinur có một chứng minh “đơn giản” cho định lý PCP — một trong những định lý quan trọng nhất của Theoretical Computer Science trong vòng 15 năm đổ lại. Bài này thắng giải best paper của STOC 2006. Radhakrishnan và Sudan có bài trên tờ Bulletin of the AMS nói về PCP và chứng minh của Dinur. Tôi có tổ chức một seminar về PCP hồi 2004, tiếc rằng chưa bao giờ có thời gian tập hợp các notes lại thành 1 bài ra trò. Bây giờ mà làm lại seminar này thì các thảo luận sẽ khác đi khá nhiều, sau bài của Dinur.

Chủ đề: Lý thuyết tính toán | Bình luận »

P, NP, và Toán Học

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

Một bài tổng quan rất rất hay của Avi Wigderson, bổ túc cho cái talk ông nói ở ICM 2006. Bài này đào sâu vào phần cuối (và các phát triển sau đó) của bài Chung Qui Chỉ Tại Cantor. Tôi tin rằng tất cả các sinh viên KHMT đều phải đọc qua bài của Avi. Các khái niệm trung tâm của KHMT lý thuyết hiện nay đều được duyệt qua một cách đơn giản và trực quan: computation, undecidability, P vs NP, NP-completeness, lower bounds (and the difficulty of proving them), proof complexity, randomness in computations and proofs (bao gồm interactive proof, zero-knowledge proof, probabilistically checkable proofs).

Chủ đề: Lý thuyết tính toán | Bình luận »

Sai lầm nghiêm trọng của một bài báo ở CACM

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

Một bài viết trong CACM mới đây mắc vài lỗi nghiêm trọng. Xem thảo luận ở complexity blog. Vụ này hứa hẹn nhiều hậu quả đầy màu sắc.

Chủ đề: Lý thuyết tính toán | Bình luận »

Tất cả các hàm đều liên tục?

Ngô Quang Hưng | 02 tháng 06, 2006 | Bản để in Bản để in

Sau lớp 11, chắc ai cũng biết định nghĩa (vô hạn các) hàm không liên tục. Tuy nhiên, có một số nhà toán học theo trường phái constructive mathematics cho rằng tất cả các hàm tính được (computable) đều liên tục. Andrej Bauer có một bài ngắn về đề tài này.

Constructive Mathematics và intuitionism ra đời cũng chỉ tại Cantor (xem toàn bài dạng pdf).

Chủ đề: Lý thuyết tính toán & Thuật Toán | Bình luận (2) »

Các bài kế »