Blog Khoa Học Máy Tính » Trí tuệ nhân tạo

Thư viện bài, chủ đề ‘Trí tuệ nhân tạo’

Bổ đề Sauer

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

Bài học máy qua góc nhìn của lý thuyết tính toán số 4 có chứng minh bổ đề Sauer (bổ đề 5.2) bằng quy nạp. Tuy nhiên, một chứng minh bằng quy nạp không hay lắm vì nó “giấu” trực quan của chứng minh. Trong bài này, chúng ta sẽ chứng minh bổ đề Sauer bằng một kỹ thuật rất phổ biến trong extremal combinatorics gọi là kỹ thuật shifting. Xem các tham khảo sau đây để biết thêm về kỹ thuật shifting:

[1] P. Frankl: The shifting technique in extremal set theory, in Surveys in Combinatorics 1987 (C Whitehead, ed.), London Math. Soc. Lecture Note Series 123, Cambridge University Press (1987), 81–110.

[2] B. Bollobás, Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability. Cambridge University Press 1986.

Rất nhiều định lý cổ điển như định lý Erdos-Ko-Rado (đã chứng minh trên blog này bằng kỹ thuật định trị hai cách) hay định lý Kruskal-Katona đều chứng minh được bằng kỹ thuật shifting. Kỹ thuật này cũng được ứng dụng gần đây trong nhánh phân tích các hàm Boolean. Nhánh này liên hệ mật thiết đến computational learning theory, coding theory, approximation algorithms, và complexity theory: toàn là các đề tài trung tâm của theoretical CS hiện nay.

Ta sẽ phát biểu lại bổ đề Sauer. Gọi $\mathcal H$ là một lớp các hàm số từ $\Omega$ vào $\{0,1\}$ . Có thể hiểu $\mathcal H$ là một bộ các tập con của $\Omega$ . Chú ý rằng cả $\mathcal H$ lẫn $\Omega$ đều có thể vô hạn (thậm chí không đếm được). Với một tập con hữu hạn $S \subseteq \Omega$ , định nghĩa projection của $\mathcal H$ lên như sau: $\Pi_{\mathcal H}(S) = \{ h \cap S \ | \ h \in \mathcal H\}$ . Trong ngữ cảnh “học máy” thì projection của lớp giả thuyết $\mathcal H$ lên một tập hữu hạn các mẫu là bộ tất cả các cách mà các giả thuyết này phân lớp các mẫu này.

Một tập bị băm nát bởi $\mathcal H$ nếu $\Pi_{\mathcal H}(S)$ chính là tập tất cả các tập con của . VC-dimension của $\mathcal H$ là kích thước lớn nhất của một tập con của $\Omega$ bị băm nát bởi $\mathcal H$ . Nếu $\mathcal H$ băm nát một tập con có kích thước lớn tùy ý thì VC-dimension của $\mathcal H$ là vô hạn.

Bổ đề Sauer:

Giả sử $\mathcal H$ có VC-dimension hữu hạn, bằng . Xét một tập con bất kỳ của $\Omega$ . Ta có,

$|\Pi_{\mathcal H}(S)| \leq \sum_{i=0}^d \binom m i$

Chứng minh. Đặt $\mathcal F = \Pi_{\mathcal H}(S)$ . Dĩ nhiên $\mathcal F$ là hữu hạn, và là một bộ các tập con của . Không mất tính tổng quát, ta có thể giả sử m>d . Do $\mathcal H$ không băm nát bất kỳ tập con nào có kích thước $\geq d+1$ , dễ thấy rằng $\mathcal F$ cũng không băm nát bất kỳ tập con nào của với kích thước $\geq d+1$ . Ta sẽ dùng tính chất này để chặn trên $|\mathcal F|$ .

Chúng ta sẽ “xê dịch” (shift) $\mathcal F$ từ từ để thành một bộ $\mathcal G$ các tập con mới của thỏa mãn các điều kiện sau đây:

$|\mathcal G| = |\mathcal F|$
Nếu $A \subset S$ bị băm nát bởi $\mathcal G$ thì cũng bị băm nát bởi $\mathcal F$ .
$\mathcal G$ là một ideal của Boolean lattice trên , nghĩa là nếu $G\in \mathcal G$ thì tất cả các tập con của đều là thành viên của $\mathcal G$ .

Giả sử ta tìm được $\mathcal G$ thỏa mãn các điều kiện trên, thì một tập con của bị $\mathcal G$ băm nát nếu và chỉ nếu $A \in \mathcal G$ . Nhưng $\mathcal G$ không băm nát bất kỳ tập con nào có kích thước $\geq d+1$ . Do đó, tất cả các thành viên của $\mathcal G$ đều có kích thước $\leq d$ . Vì thế $|\mathcal G| \leq \sum_{i=0}^d \binom m i$ .

Đến đây, ta mô tả phép “dịch chuyển” $\mathcal F$ thành $\mathcal G$ thỏa mãn các điều kiện 1, 2, 3 ở trên bằng một thuật toán. Giả sử $S = \{1, 2, \dots, m\}$ .

1. For ( to ) do
2.    Foreach () do
3.        If ( and ), then
4.            Replace  by 
5.        Endif
6.    Endfor
7. Endfor
8. Repeat 1–7 until  no longer changes. Call this final collection

Với mỗi vòng lặp 1–7, nếu bộ $\mathcal F$ không đổi thì thuật toán kết thúc, còn nếu có đổi thì một thành viên nào đó của $\mathcal F$ bị giảm kích thước. Kích thước của các thành viên của $\mathcal F$ không thể giảm mãi (mà $\mathcal F$ vẫn thay đổi), do đó thuật toán sẽ kết thúc.

Bây giờ ta chứng minh rằng $\mathcal G$ thỏa mãn ba điều kiện 1, 2, và 3 ở trên.

Điều kiện 1 đã rõ ràng, vì ta chỉ biến thành $F \setminus \{i\}$ khi $F \setminus \{i\} \notin \mathcal F$
Ta chứng minh rằng tính chất này bất biến sau mỗi lần ta thực hiện vòng lặp 2–6 với một phần tử bất kỳ trong thuật toán trên. Giả sử $\mathcal F$ là bộ tập hợp trước khi vòng lặp này được thực hiện, và $\mathcal F'$ là bộ tập hợp sau khi vòng lặp này được thực hiện.
Giả sử $A\subseteq S$ bị băm nát bởi $\mathcal F'$ . Nếu $i \notin A$ thì dĩ nhiên đã bị băm nát trước thay đổi. Do đó, có thể giả sử $i \in A$ .

Xét một tập con $R\subseteq A$ nào đó. Ta cần chứng minh rằng $R = A \cap F$ với $F \in \mathcal F$ . Do bị băm nát sau vòng lặp, $R = A \cap F'$ với $F' \in \mathcal F'$ . Nếu $i \in R$ thì cũng thuộc $\mathcal F$ . Bây giờ xét trường hợp $i \notin R$ . Tồn tại $T\in \mathal F'$ sao cho $T \cap A = R \cup \{i\}$ . Rõ ràng là cũng thuộc $\mathcal F$ . Nhưng “còn sống sót” sau vòng lặp chứng tỏ là $T \setminus \{i\} \in \mathcal F$ , và do đó $R = A \cap (T \setminus \{i\})$ .
Tính chất này đã rõ.

Chủ đề: Combinatorics & Trí tuệ nhân tạo | Bình luậ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

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 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ẫu theo phân bố $\mathcal D$ trên miền $\Omega$ sao cho rất gần 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

ở tất cả

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

≤ $|\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 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 (

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ố lớn nhất sao cho tồn tại 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ố 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 . 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 “cắt” ra thành (nhãn = 1) và S-X (nhãn = 0).

Tập mẫu 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 . Nói cách khác, 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 “cắt” ra thành (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 đ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 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 đủ 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ẫ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ố 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

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ố 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:

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

Thay vì chặn xác suất 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 bất kỳ, gọi M(h,S) là tổng điểm trong 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ẫ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:

: 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à vẫn nhất quán với trên ) 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 đồ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ứ là ngửa. Gọi hai tập mẫu kết quả là và . Định nghĩa một sự kiện thứ ba:

: 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à vẫn nhất quán với trên ) nhưng $M(h,T') > m\epsilon/2$ .

Do tính i.i.d. của và , dễ thấy rằng và có xác suất bằng nhau. Cố định và và xét một giả thuyết 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ố sao cho $h(\mathbf x_i) \neq h(\mathbf x'_i)$ , và ít nhất đồng tiền ra xấp/ngửa sao cho phần đúng nhảy vào và phần sai nhảy vào . 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 thỏa mãn điều kiện sau đây: bất kỳ learner nào — nếu chỉ lấy 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 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 . Như vậy, mỗi mẫu trong 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 , 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) »

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

Ngô Quang Hưng | 16 tháng 07, 2008 | 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.

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

“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

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 rất gần với khái niệm cần học .

Làm thế nào để đo xem có “gần” 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

là xác suất mà

đưa ra câu trả lời khác

. Chú ý là ta đo lỗi của

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ì và 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 và 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

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 , 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 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ó 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 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ố (tổng số examples trong training set), (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

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

Hành trình vào tâm não

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

Bài nói chuyện của GS Vilayanur Ramachandran. (Cảm ơn anh Duy Nguyen cho link.)

Chủ đề: Trang web hay & Trí tuệ nhân tạo | Bình luận »

Giới thiệu một số sách KHMT [2]: machine learning

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

Nhân đây xin nhắc thêm là về non-combinatorial optimization thì tôi có điểm một danh sách cách đây vài năm . Còn về combinatorial optimization thì anh Hưng đã điểm qua ở bài blog trước.

Chuyển qua machine learning và statistics… Có lần một người bạn tôi hỏi David Blackwell, khi cậu ta mới chập chững vào PhD program. Rằng, có cái gì hay ho tôi nên theo đuổi trong statistics? Blackwell trả lời, nên học machine learning và nonparametric statistics. Tôi gộp cả ML và Stats vì tôi coi hai ngành này là một, dẫu về truyền thống và định hướng hiện tại thì có những sự khác biệt nhất định. Có rất nhiều sách hay trong ngành, nhưng chỉ giới thiệu một số mà tôi quen thuộc hơn cả. Như vậy còn một số sách hay mà chưa được list, xin bạn đọc bổ sung qua comments. Những quyển đánh dấu sao (*) có thể dùng làm sách nhập môn tốt. Ngoài ra, (+) cũng là những quyển sách tôi ưa thích.

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

Chủ đề: Giới thiệu sách & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (3) »

Kiến trúc top-down và bottom-up trong trí tuệ nhân tạo

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

Nhân lục lọi đôi thứ trong archive tôi tìm lại bài tranh luận nhỏ cách đây đúng 5 năm trên VNAI mailing list (của những người bạn VN quan tâm đến AI). Bài này bắt nguồn từ email sau đây của bạn Đặng Việt Dũng về một bài giảng về reactive agent architecture của Rodney Brooks:

On Thu, 4 Jul 2002, Viet Dung Dang wrote:

Cách đây mấy tháng, em có dự 1 bài giảng của Rodney Brooks để quảng cáo cho quyển sách mới của ông tên là “Flesh and Machines”. Như nhiều anh chị đã biết, Rodney Brooks vào năm 1994 đã gây một cơn sốc lớn trong giới nghiên cứu agent, khi ông phủ nhận kiến thức truyền thống (logic-based với knowledge based inference rules) và khai sinh ra kiến trúc Subsumption, mà cốt lõi là purely reactive.

Trong bài giảng em đã được dự, Brooks tiếp tục promote kiến trúc subsumption và nói về việc xây dựng một con humanoid robot dựa trên kiến trúc đó. Một câu hỏi mà chắc mọi người cùng thắc mắc, và em cũng vẫn thắc mắc sau khi dự là theo kiến trúc của Brook, agent hoàn toàn không có internalrepresentation of the world, mà hầu hết chỉ dựa trên các re-active rules. Trong buổi đó, khi trả lời câu hỏi, Brook có nói là nếu xây được một representation như thế thì sai lầm vì model đó sẽ không phản ánh đúng thực chất của thế giới outside.

Tuy nhiên, theo như em hiểu, thực chất con người chúng ta đều có một representation of the world ở trong đầu, và dựa vào đó để suy luận và hành động. Như thế, liệu kiến trúc của Brooks co’ phải là useless khi xây dựng humanoid robot không?

Em cũng nghĩ chắc là không, vì nếu thế thì làm sao Brooks lại đang làm director lab của MIT được

Bài bình luận của tôi không đi vào chi tiết về kiến trúc của Brooks, mà chủ yếu tóm tắt một số sự khác biệt giữa hai truờng phái kiến trúc khác nhau trong AI. Trường phái truyền thống có thể nói bắt nguồn từ John McCarthy ở Stanford, người mà chúng ta đã nói qua ở blog này về Common sense và AI.

On Thu, 4 Jul 2002, XuanLong Nguyen wrote:

This is an interesting question that every student of AI should ask himself at some point. It seems that most people would give up after a few thoughts. Those with whom the question stuck still would probably eventually end up in places such as the directorship of MIT AI lab :-). In the mean time, the rest of us are happily working on obscure problems of knowledge-based systems, Strips worlds, Bayesian nets that seem to be forever in the wrong side of the real world Still, I think it’s fun to talk about — and before the other more knowledgeable members of the list speak out, hopefully — I’d like to add my humble opinions.

Without getting into hairy discussion of intelligence, and AI and so on, lets call the Brooks approach the bottom-up (or the MIT school), while the traditional approach the top-down (or the Stanford school). Roughly speaking, the most distinctive constrast between the two is that the bottom-up approach is behavior-based, while the top-down is representation-based.

Both approaches bear merits as well as difficulties. For a researcher in AI, the comparison also depends on what your immediate objectives are. If the objective is to build an *autonomously* “intelligent” entity that appears to be interesting and capable of doing something deemed interesting, the answer is not clear. The problem with the traditional top-down approach is that in order to break down a system into modules such as knowledge representation, reasoning, planning, learning, multi-agent coordinating, etc one has to necessarily make a lot of simplifying assumptions. Therefore there is no guarantee that such simplification is harmless. Since we still don’t know what it takes build an intelligent entity, whatever that means, we don’t know if such simplifying assumptions help us reach the essence of intelligence faster, or they simply lead us astray to a dead-end path that would preclude the possibility of ever finding any solution.

So this has been one of the strongest criticism of the traditional top-down approach. And for good reasons. The clearest evidence is that after half a century of research in many areas and subareas and subsubareas and subsubsubareas of AI, the field as a whole hasn’t achieved much, and most of us seem to forget the grandiose objective of the field, i.e., to understand and create *autonomous* intelligent entities that can hold up themselves in the real world. One natural alternative is, since we don’t know what it takes to build intelligent entities, we need to imitate what are considered to be intelligent. There are plenty around, not just in humans, but also animals and insects. So it seems plausible to step back to square one and studied the most primitive mechanism there is in the nature. The good news is that by now many researchers are convinced that seemingly sophisticated behaviors can be built up by very simple (and possibly reactive) rules. It is also hoped that one is able to understand and build progressively more sophisticated and intelligent behavior-based entities in much the same way the evolution works.

Needless to say, the progress has been frustratingly slow, and our understanding of nature, including even some of the most primitive insects, remains very limited. It seems that the breakthrough in AI would probably come from this bottom-up approach, given its very interdisciplinary nature and possible contributions coming from computer science and statistics, as well as other computational sciences and experimental sciences (such as neuroscience, physics and biology).

There have been a very strong movement that is more or less advocating small autonomous robots equipped with limited sensory and actuating capabilities but which are nevertheless useful and can hold up in the real world environment. They go by names such as x-insects, smart dust, robotic fly, etc. One distinctive feature of the bottom-up approach is the emphasis on sensors and sensory data processing (interaction with outside world). By contrast, the top-down approach focuses on representing and manipulating abstract knowledge-base with a strong emphasis on methods for obtaining such knowledge in the first place.

Back to the traditional top-down school. It is not without success, though in a limited way. By abstracting away and breaking down the intelligency into many different disconnected parts such as knowledge representation, reasoning, planning, learning, etc these subfields have been reduced to subclasses of problems, whose techniques prove useful for problem-solving, usually with heavy intervention of humans. Within each of the modules, limited intelligent behavior can be achieved. As we all know, an AI search researcher can boast about Deep Blues, while machine learning and control theorist can talk about autonomous vehicles. Planning researchers talk about automatically controlling a spacecraft for a short period of time. More robust, user-friendly softwares in many applications have been incorporating latest AI research advances without notice.

While both aiming for intelligency, the traditional school has an objective very different from the new bottom-up approach. This is exemplified by a popular AI textbook (by Russell and Norvig) which simply proclaims in chapter 1 that it is more concerned about solving problems intelligently, but not to imitate human intelligence in the first place. Perhaps the most convincing argument of
the traditional school of AI is summed up by Drew McDermott (from Yale), who famously wrote that: To say the Deep Blues is not intelligent is to say that airplanes don’t fly because they don’t flip their wings. However, the price this approach has to pay is that by separating the subfields too far apart, it is very hard to glue them back together to build a coherent working autonomous system. In particular, such systems are hopeless in interacting with the outside world.

Nevertheless, the traditional school of AI will be here to stay, and so will the AI planning, knowledge-representation, machine learning, multi-agent researchers :-). Ultimately, in order to have a truly intelligent autonomous entity (whatever it means, again), one has to have knowledge-representation capability, as well as search, inference, extra/interpolation capability, and so on because the most sophisticated intelligent entity, i.e, human, surely have those. But it is not clear if the knowledge representation and reasoning mechanism of that dream intelligent entity is the same as what we know, or are heading for in our search. Neither do we know how they are glued together.

Ideally, one may hope that both approaches in AI will meet somewhere in the search graph, or they never will if the graph is infinite with loops. We can only wait for many years to come to know the answer. And in the mean time, it’s useful to prove the NP-hardness of whatever task there is in each of our favorite building blocks of what are known to us as AI

cheers,
Long [July 04, 2002]

Tóm lại của bài viết dài dòng trên, chúng ta có ba câu hỏi chính mà cả hai anh kiến trúc đều phải đối đầu:

Làm thế nào để thu nhập, cập nhật được kiến thức?
Làm thế nào để mã hóa chúng một cách gọn gàng để có thể truy cập và sử dụng một cách hiệu quả?
Và làm thế nào sử dụng được kiến thức một cách hữu hiệu nhất?

Đó là những câu hỏi lớn không chỉ trong trí tuệ nhân tạo, mà trong công việc và cuộc sống hàng ngày chúng ta luôn phải đối thoải, chẳng hạn như bài blog gần đây của anh Hưng. Trí tuệ nhân tạo là một ngành có tham vọng “nhân tạo” và tự động hóa những giải pháp cho các câu hỏi trên, qua công cụ thuật toán, và các kỹ thuật phần mềm và phần cứng.

5 năm sau, suy nghĩ chung của tôi về vấn đề kiến trúc topdown vs bottom up không thay đổi nhiều. Mặc dù tôi vẫn thiên về kiến trúc topdown hơn, nhưng sự nhận thưc về mặt mạnh và mắt yếu của cả hai kiến trúc đều không thay đổi. Có thể nói trường phái top-down phân tách cả ba câu hỏi một cách tách bạch, và từ đó AI bị chia ra làm nhiều ngả, mỗi ngả tìm cách giải quyết một câu, và tập trung chủ yếu vào câu thứ hai và thứ ba. Còn kiến trúc bottom-up thì tập trung vào câu thứ nhất. Cả hai loại kiến trúc đều rất có ích, nhưng có lẽ một kiến trúc thích hợp nhất sẽ không có sự chia rẽ ba vấn đề trên một cách tách bạch như thế.

Điều đáng nói là ba câu hỏi trên có tính phổ quát không chỉ trong TTNT mà rất nhiều lĩnh vực khác, đặc biệt trong thống kê hiện đại. Ngành thống kê hiện đại vật vã rất nhiều với câu hỏi: Làm thế nào make sense được với data. Data chính là giao diện của bạn, của tôi, của một chính thể trí tuệ nhân tạo trong tương lai, với thế giới bên ngoài. Ngành thống kê cũng phải đối đầu với những câu hỏi như: Khi phải xây dựng một mô hình về thế giới, chúng ta phải bắt đầu từ đâu, bao nhiều prior information thì đủ? Qua đó chúng ta đi đến sự đối đầu giữa Bayesian và frequentists. Hay, làm thế nào để tạo ra các mô hình phức tạp một cách hệ thống? Graphical models, một sự kết hợp của graph theory và probability theory, chính là một giải pháp hướng tới câu trả lời đó. V.v. và v.v. Sự hội tụ giữa TTNT và ngành thống kê góp phần làm ra đời và phát triển lĩnh vực machine learning, và theo chủ quan của tôi, rất có thể trong tương lai không xa machine learning sẽ trở thành một trong những lĩnh vực trung tâm của cả TTNT và thống kê.

Thay cho câu kết, tôi xin trích lại đoạn sau trong Common sense và AI.:

Câu hỏi quan trọng mà tôi quan tâm là: Common sense có phải là khái niệm hữu ích hay không trong việc xây dựng máy tính thông minh? Cụ thể hơn, đó có phải là một khái niệm constructive hay không. Khái niệm này có thể được mổ xẻ và tổng hợp một cách tự động từ giao tiếp của computers với thế giới bên ngoài? Khái niệm đó có thể dễ dàng transfer từ computers này sang computers khác, có thể được tổng quát hoá và suy diễn (inductive and deductive inference) để tạo ra những khái niệm mới có ích?
….

Tôi cho rằng, nhìn từ góc độ mô hình xác suất, rất có thể common sense là một dạng “emerging property/phenomenon”, song không nhất thiết là một khái niệm kiến trúc căn bản của intelligence. Nếu quả thật như thế, thì rất nguy hiểm khi bắt đầu xây dựng một intelligent system bằng cách xây dựng common sense storages. Những systems như vậy sẽ không robust.

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

Bayesian hay frequentist?

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

Vài bài về cuộc tranh luận Bayesian chọi frequentist:

Bài phát biểu của giáo sư Bradley Efron, giáo chủ đời 99 của thống kê thần giáo Hoa Kỳ (ASA) trong đại hội giáo dân 2005.
Một bài nữa của Roderick Little, có rất nhiều tham khảo đến lịch sử và tài liệu của cả hai phe.

Bài của Efron có một đoạn rất hay:

A cartoon history of western thought might recognize three eras: an unpredictable pre-scientific world ruled by willful gods and magic; the precise clockwork universe of Newton and Laplace; and the modern scientific perspective of an understandable world, but one where predictability is tempered by a heavy dose of randomness. Deterministic Newtonian science is majestic, and the basis of modern science too, but a few hundred years of it pretty much exhausted nature’s storehouse of precisely predictable events. Subjects like biology, medicine, and economics require a more flexible scientific world view, the kind we statisticians are trained to understand.

Suy nghĩ cho kỹ, tôi thấy tiến trình phát triển tư duy của mình cũng hao hao cái cartoon history này. Hồi mới bắt đầu đi học, các lý thuyết, định lý như từ trên trời rơi xuống, như “ảo thuật” của các thượng đế tối cao Karp, Cook, Turing, … Sau đó đến classical complexity theory, theory of computation, deterministic algorithms, toán cổ điển … là vũ trụ chính xác của Newton và Laplace. Cuối cùng, khi đối chọi với nhiều vấn đề thực tế như phân tích dữ liệu mạng, bảo mật và mật mã hóa, và cả lý thuyết đương đại như thuật toán xấp xỉ, expanding graphs, định lý PCP và các lớp BPP, ZPP, vân vân, tôi đến với thế giới của các probability distributions, statistical learning theories, và randomness nói chung.

Efron tóm tắt hai phe như sau:

The Bayesian-Frequentist debate reflects two different attitudes to the process of doing science, both quite legitimate. Bayesian statistics is well-suited to individual researchers, or a research group, trying to use all the information at its disposal to make the quickest possible progress. In pursuing progress, Bayesians tend to be aggressive and optimistic with their modeling assumptions. Frequentist statisticians are more cautious and defensive. One definition says that a frequentist is a Bayesian trying to do well, or at least not too badly, against any possible prior distribution. The frequentist aims for universally acceptable conclusions, ones that will stand up to adversarial scrutiny.

Cuộc tranh luận về nền tảng của khoa học thống kê này có hơi hướng của cuộc tranh luận về nền tảng của toán học và logic nói riêng thời đầu thế kỷ 20. Đến hồi (tạm thời) ngã ngũ thế nào cũng có một đột phá trong ngành thống kê.

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

machine learning hay statistics (2)

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

Machine learning hay statistics?
Quá nhiều terminologies làm cho tôi headache
Tôi khoái learning machines, bạn lại thích models
Bạn hỏi tôi về covariates, tôi nói chuyện features

Machine learning hay statistics?
Thứ nào nghe sexy hơn thứ nào boring sh*t?
Một câu hỏi nhỏ, nếu bạn vẫn gà mờ …
Xin chịu khó đọc thêm blog Ka Hờ Mờ Tờ

Tiếp theo bài blog hôm trước, tôi xin nói thêm về sự hỗn độn về thuật ngữ trong machine learning. Dân làm machine learning nói riêng và KHMT nói chung rất sáng tạo trong việc đặt tên cho sản phẩm thuật toán của mình. Mỗi một tít bài báo ở hội nghị thường có kèm tên một thuật toán (hay system, hay architecture mới), cho dù ý tưởng của bài báo chỉ là một thay đổi epsilon của một bài báo trước đó.

Trong machine learning, mỗi một thuật toán máy học mới thường có cái tên là một machine gì đấy, làm ta liên tưởng đến một cậu HAL đang được thai nghén. Vậy nên có cả một vườn thú các learning machines, ví dụ có thể tìm thấy ở Journal of Machine Learning Gossip (một website hóm hỉnh của dân làm ML). Điều này làm cho những người bắt đầu bước vào vườn thú rất choáng. Mặc dù xuất phát điểm mang tính lịch sử của machine learning là từ trí tuệ nhân tạo, nhưng nhìn lại, rất nhiều ý tưởng trong ML đã được khơi nguồn từ statistics, và trong một thời gian khá dài (từ những năm 1950 đến những năm đầu 1990) đáng tiếc là không có sự liên hệ đầy đủ giữa hai ngành. Dưới đây tôi thử liệt kê vài khái niệm trong machine learning và dịch sang ngành thống kê. Đây là open list, ai có thêm thì xin mời bổ sung vào. Để tiện tôi chia ra làm một vài mục:

Mô hình:

machines, learning machines (e.g., support vector machines): models
networks (e.g., neural networks, Bayesian networks, Markov networks): models
concepts: models
multilayer networks: hierachical models
Bayes nets, Bayesian networks: (probabilistic) graphical models
instance-based learning methods: nonparametric models
input features: covariates
output: response variable
model selection: model choice

Thuật toán:

learning algorithms, training algorithms: (frequentist) estimation procedures
Bayesian learning: Bayesian inference
probabilistic reasoning: probabilistic inference
unsupervised learning, clustering algorithms: use of latent (hidden) variable models, generative models
supervised learning, classification algorithms: classification, regression, discriminative models
empirical risk minimization principle: M-estimation methods (M stands for maximization)
cost function: loss function

Một số linh tinh khác:

PAC (probabilistically approximately correct) learning: đảm bảo đúng với xác suất cao
convergence: trong ML thì đây thường chỉ sự hội tụ của thuật toán, nhưng trong statistics thì đây thường nói về tốc độ hội tụ của estimation error của một estimation procedure nào đó
sample: trong ML thì chỉ một data point, trong statistics thì chỉ một tập các data points.

Một số lớn các khái niệm căn bản của ML (thường là bắt đầu một cách ad hoc) đã được giới thiệu và nghiên cứu một cách có hệ thống và chặt chẽ ở ngành thống kê. Ngược lại, còn rất nhiều khái niệm hay và sâu sắc trong thống kê vẫn chưa được áp dụng trong các vấn đề machine learning. Tuy vậy machine learning ngày càng đóng góp cho statistics những khái niệm mới mẻ, đặc biệt liên quan đến khía cạnh computation c

Tầm nhìn ta thật ngắn mà đã thấy bao thứ để làm — Alan Turing

Thư viện bài, chủ đề ‘Trí tuệ nhân tạo’