Blog Khoa Học Máy Tính

“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

Warning: fopen(/home/asm_conjecture/sites/procul.org/blog/latexrender/tmp/2e43361280d0f4607bb59296be83187a.tex) [function.fopen]: failed to open stream: Permission denied in /home/asm_conjecture/sites/procul.org/blog/latexrender/class.latexrender.php on line 235

Warning: fputs(): supplied argument is not a valid stream resource in /home/asm_conjecture/sites/procul.org/blog/latexrender/class.latexrender.php on line 236

Warning: fclose(): supplied argument is not a valid stream resource in /home/asm_conjecture/sites/procul.org/blog/latexrender/class.latexrender.php on line 237

Warning: copy(2e43361280d0f4607bb59296be83187a.gif) [function.copy]: failed to open stream: No such file or directory in /home/asm_conjecture/sites/procul.org/blog/latexrender/class.latexrender.php on line 271

Warning: unlink(/home/asm_conjecture/sites/procul.org/blog/latexrender/tmp/2e43361280d0f4607bb59296be83187a.tex) [function.unlink]: No such file or directory in /home/asm_conjecture/sites/procul.org/blog/latexrender/class.latexrender.php on line 288

Warning: unlink(/home/asm_conjecture/sites/procul.org/blog/latexrender/tmp/2e43361280d0f4607bb59296be83187a.aux) [function.unlink]: No such file or directory in /home/asm_conjecture/sites/procul.org/blog/latexrender/class.latexrender.php on line 289

Warning: unlink(/home/asm_conjecture/sites/procul.org/blog/latexrender/tmp/2e43361280d0f4607bb59296be83187a.log) [function.unlink]: No such file or directory in /home/asm_conjecture/sites/procul.org/blog/latexrender/class.latexrender.php on line 290

Warning: unlink(/home/asm_conjecture/sites/procul.org/blog/latexrender/tmp/2e43361280d0f4607bb59296be83187a.dvi) [function.unlink]: No such file or directory in /home/asm_conjecture/sites/procul.org/blog/latexrender/class.latexrender.php on line 291

Warning: unlink(/home/asm_conjecture/sites/procul.org/blog/latexrender/tmp/2e43361280d0f4607bb59296be83187a.ps) [function.unlink]: No such file or directory in /home/asm_conjecture/sites/procul.org/blog/latexrender/class.latexrender.php on line 292

Warning: unlink(/home/asm_conjecture/sites/procul.org/blog/latexrender/tmp/2e43361280d0f4607bb59296be83187a.gif) [function.unlink]: No such file or directory in /home/asm_conjecture/sites/procul.org/blog/latexrender/class.latexrender.php on line 293

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

3.2. Toán học của mô hình PAC-learning (cho bài toán classification). Chúng ta vẫn đi theo cái khung có sẵn khi mô tả mô hình này.

1. Học cái gì?

Chúng ta muốn học một khái niệm $c: \Omega \to \{0,1\}$ thuộc về một lớp khái niệm $\mathcal C$ “cho trước”.

2. Lấy data từ đâu ra? Lấy thế nào? Training data là một tập con của miền, mỗi phần tử đều có “nhãn”.

$S = \left\{(\mathbf x_1, c(\mathbf x_1)), \cdots, (\mathbf x_m, c(\mathbf x_m))\right\}$

Mỗi điểm dữ liệu $\mathbf x_i$ được lấy từ miền theo một phân bố xác suất $\mathcal D$ .

3. Data được đưa cho learner thế nào? Đưa off-line, toàn bộ . Mặc dù ta có thể hiểu rằng thuật toán ML “lấy” các điểm dữ liệu theo phấn bố xác suất, nhưng nó chỉ đưa ra giả thuyết sau khi đã có dữ liệu. Do đó vẫn là off-line chứ không phải on-line learning. (Ta sẽ nói về on-line learning sau.)

4. Tối ưu hóa cái gì? Tối ưu dưới các ràng buộc nào?

Lớp khái niệm $\mathcal C$ có thể học được dưới mô hình PAC (PAC-learnable) nếu tồn tại một thuật toán ML thỏa mãn các điều kiện sau đây:

Với mọi $0<\epsilon<1/2$ , $0<\delta<1/2$
Với bất kỳ phân bố xác suất $\mathcal D$ nào trên miền $\Omega$
Thuật toán lấy mẫu độc lập từ $\Omega$ theo phân bố $\mathcal D$
Thuật toán đưa ra một giả thuyết sao cho
$\text{Prob}\left[ \text{err}_{\mathcal D}(h) \leq \epsilon\right] \geq 1 – \delta$

Tham số $\epsilon$ là tham số lỗi, còn $\delta$ là tham số độ tin cậy. Nếu thêm vào đó thuật toán ML còn chạy trong thời gian poly $\left(1/\epsilon, 1/\delta, n, |c| \right)$ thì lớp khái niệm $\mathcal C$ là có thể học được một cách hiệu quả dưới mô hình PAC (efficiently PAC-learnable). Rõ ràng là mô hình PAC sặc mùi xác suất và thống kê, dù rằng các ý tưởng tổ hợp vẫn còn rất hữu dụng trong thiết kế thuật toán ML.

Nhận xét thêm: vẫn chưa có mô hình cụ thể cho nhiễu. Ta sẽ giải quyết vấn đề nhiễu trong một bài sau. Đòi hỏi độ tin cậy cao, lỗi nhỏ, với bất kỳ phân bố $\mathcal D$ nào xem chừng có vẻ quá mạnh. Khá ngạc nhiên là có nhiều lớp khái niệm hoàn toàn không tầm thường lại vẫn học hiệu quả được. Hai “vũ khí” của chúng ta là (i) hàm lỗi được định trị trên cùng phân bố xác suất như training data, và (ii) các mẫu trong training set được lấy độc lập từ cùng một phân bố (i.i.d.). Ngoài ra, bài báo này cho thấy một số lớp khái niệm vẫn học được khi giảm nhẹ yêu cầu i.i.d. một chút.

Ngược lại, không ngạc nhiên khi có nhiều lớp khái niệm không thể học hiệu quả được, và ta sẽ chứng minh được điều đó. Một nguyên do là: phần lớn lý thuyết tính toán cho đến nay, bao gồm cả mô hình PAC, được xây dựng dựa trên phân tích trường hợp tệ nhất (worst case analysis — chúng ta không ràng buộc gì về phân bố $\mathcal D$ ). Hoàn toàn có khả năng, với một lớp khái niệm và data cụ thể nào đó, thuật toán ML của ta vẫn chạy tốt trên thực tế mặc dù ta chứng minh được là trong trường hợp tệ nhất thì lớp khái niệm này không học được. Điểm này tương tự như việc thuật toán đơn hình chạy rất tốt trên thực tế mặc dù về mặt lý thuyết nó không phải là thuật toán thời gian đa thức. Quan điểm này khác biệt về chất với quan điểm Bayesian và phương pháp Bayesian khi mà nhà thiết kế “áp đặt” một phân bố nào đó (prior) lên tập các khái niệm cho trước.

Kế đến, ta xét một vài ví dụ tương tự như trong mô hình nhất quán.

3.3 Lớp khái niệm Boolean Conjunctions có thể học được một cách hiệu quả trong mô hình PAC

Ta dùng chính thuật toán ML đã thiết kế cho lớp khái niệm này trong mô hình nhất quán. Thuật toán này đưa ra giả thuyết là conjunction của một bộ literals, trong đó bao gồm tất cả các literals của khái niệm cần học . Do đó, $c(\mathbf a) = 0 \Rightarrow h(\mathbf a) = 0, \forall \mathbf a \in \Omega$ (mỗi $\mathbf a \in \Omega$ là một cách gán TRUE/FALSE cho các biến Bool). Vì thế, $h(\mathbf a) \neq c(\mathbf a)$ nếu và chỉ nếu $c(\mathbf a)=1$ và tồn tại một literal $l \in h – c$ sao cho a(l) = 0 . Do đó,

$\text{err}_{\mathcal D}(h) = \text{Prob}_{\mathbf a \in \mathcal D} [c(\mathbf a)=1 \wedge \mathbf a(l)=0 \ \text{for some $l \in h-c$}]$

Dùng union bound,

$\text{err}_{\mathcal D}(h) \leq \sum_{l \in h-c} \text{Prob}_{\mathbf a \in \mathcal D} [c(\mathbf a)=1 \wedge \mathbf a(l)=0 ]}$
Định nghĩa $p(l) = \text{Prob}_{\mathbf a \in \mathcal D} [c(\mathbf a)=1 \wedge \mathbf a(l)=0 ]}$ , ta có

$p(l) \leq \epsilon/2n, \forall l \in h-c \Rightarrow \text{err}_{\mathcal D}(h) \leq \epsilon$

và vì thế
$\text{Prob}[\text{err}_{\mathcal D}(h) \leq \epsilon] \geq 1 – \text{Prob}[\exists l \in h-c, p(l) > \epsilon/2n]$
Gọi

là “xấu” nếu $p(l) > \epsilon/2n$ . Xác suất một literal xấu “sống sót” trong h-c

lần lấy mẫu là $\leq \left(1-p(l)\right)^m<\left(1-\epsilon/2n\right)^m$ . Do đó,
[Unparseable or potentially dangerous latex formula. Error 6 ]

như mong đợi nếu ta lấy $m \geq \frac{2n}{\epsilon}\left(\ln(2n) + \ln (1/\delta)\right)$ mẫu. Với bao nhiêu đó mẫu, rõ ràng là thuật toán vẫn chạy trong thời gian đa thức.

Bài tập: chứng minh rằng lớp khái niệm k-CNF có thể học được một cách hiệu quả trong mô hình PAC

3.4 Lớp khái niệm k-Term DNF KHÔNG học được một cách hiệu quả trong mô hình PAC

Chứng minh này gần giống hệt như chứng minh rằng lớp khái niệm này không học được trong mô hình nhất quán. Chỉ có điều là ta dùng giả thiết RP != NP thay vì P != NP, vì thuật toán ML là một thuật toán ngẫu nhiên hóa.

Bài tập: Chứng minh rằng lớp khái niệm axis-parallel rectangles có thể học được một cách hiệu quả trong mô hình PAC.

3.6 Sơ kết

Ta lại thấy rằng cách biểu diễn khái niệm và giả thuyết ảnh hưởng sâu sắc đến tính khả thi của việc học một lớp khái niệm. Nếu với lớp khái niệm k-Term DNF mà ta buộc thuật toán ML phải đưa ra một giả thuyết cùng dạng k-Term DNF thì lớp khái niệm này không học hiệu quả được. Trong khi đó, nếu ta cho phép thuật toán ML dùng k-CNF làm lớp giả thuyết thì lại học hiệu quả được.

Vì lý do này, từ đây về sau ta sẽ cho phép mô tả lớp khái niệm cho trước $\mathcal C$ bằng một dạng biểu diễn trong khi thuật toán trả về khái niệm $h \in \mathcal C$ dùng một dạng biểu diễn khác. Gọi $\mathcal H$ là lớp giả thuyết (theo dạng biểu diễn “khác” đó), ta đã thấy là đôi khi $\mathcal C$ là “học được” nếu $\mathcal H$ đủ “biểu cảm”.

Để hiểu rõ hơn, các ví dụ trên có thể được kết luận như sau:

Lớp khái niệm k-Term DNF không thể học hiệu quả được dùng k-Term DNF (làm lớp giả thuyết).
Lớp khái niệm k-Term DNF có thể học hiệu quả được dùng k-CNF.
Lớp khái niệm k-CNF có thể học hiệu quả được dùng k-CNF.
Lớp khái niệm axis-parallel rectangles có thể học hiệu quả được dùng cách biểu diễn một rectangle bằng tọa độ hai đỉnh đối (hoặc bất kỳ cách biểu diễn bình thường nào.)

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

9 lời bình

Nguyễn Xuân Long says:

July 15, 2008 at 4:50 pm

Cảm ơn bác Hưng, bài viết rất súc tích và nhiều thông tin và thú vị, đặc biệt là về v/d học các Boolean classes.

Tôi có một số nhận xét nhanh (và critical, bác biết rồi đó về PAC:

– Đóng góp về mô hình PAC có ý nghĩa lịch sử với cộng đồng nghiên cứu ML nói riêng và AI nói chung, bởi nghĩa nó giúp cho cộng đồng này chuyển sang sử dụng ngôn ngữ xác suất thống kê thay vì dùng logic để thực hiện inductive inference.

– Sự tập trung vào boolean function classes là hoàn toàn mới và rất KHMT. Tuy vậy những function classes này không có đủ nhiều structures và do đó tôi có cảm tưởng kho’ có tiến xa gì về mặt lý thuyết. Ngoài ra hầu như không có ứng dụng thực tiễn nào cho việc sử dụng function classes này cho to+’i nay.

– Các khía cạnh khác của lý thuyết PAC không mới và hầu như đã được nghiên cứu *rộng* và *sâu* hơn trong lý thuyết thống kê. Xin đưa ví dụ:

++ PAC chủ yếu tập trung vào bài toán classification (cho dữ liệu và nhãn). Tuy nhiên đó chỉ là một vấn đề hẹp trong cả một bức tranh rộng lớn các loại mô hình và statistical inference.
++ PAC tập trung vào worst-case analysis của một số concept classes (như Boolean classes). Theoretical statistics từ những năm 60,70 đã thiết lập lý thuyết độ sộ về worst-case analysis qua minimax theory, cho phép ta biết hiệu quả học tốt nhất có thể được cho từng concept class. Tuy họ không nghien cứu cụ thể Boolean classes, nhưng ứng dụng các kết quả này cho các classes có nhiều analytic structures hơn (ví dụ smooth function classes như spline chẳng hạn, hoặc các dạng class biểu diễn qua mixture models), và có ứng dụng thực tiễn. Các kết quả lower-bound này rất combinatorial. Một số tác giả lớn như Le Cam, Hajek, Pinsker, Birgé, Vapnik,… từ thập niên 60/70.
++ Tôi ngạc nhiên là bác Hưng nói Vapnik không nghiên cứu các vấn đề PAC-learnable như đinh nghĩa ở trên. Lý thuyết VC đi xa và sophisticated hơn nhiều những gì PAC-theory đạt được.
++ PAC cảm thấy khó khăn khi rời khỏi i.i.d. assumption. Lý do tại sao tôi sẽ viết duới đây
++ PAC là một lý thuyết frequentist, tuy nhiên một bức tranh thống nhất cho learning (inference) phải là một sự kết hợp giữa Bayesian framework và frequentist techniques.

Nói ngắn gọn, xét trong sự phát triển chung với cả ngành thống kê thì PAC không mới, phần nhiều tụt hậu so với những phát triển của thống kê lý thuyết đã phát triển ở các thập niên trước đó.

Hạn chế lớn nhất của PAC formulation và learning theory formulation (nhất là thời gian đầu) là lấy learning algorithm (kèm với input/output) là trọng tâm. Kỳ thực là rất quan trọng, nhưng learning algorithm chỉ là mặt nổi của một mặt ẩn quan trọng hơn nhiều, đó là models.

Models dùng ngôn ngữ toán học (đặc biệt là xác suất) để mô phỏng các hiện tượng diễn tả data mà ta có. Data quyết định models, models quyết định thuật toán, chứ không phải ngược lại.

Do đó khi ta design của thuật toán phải tính đến tính chất của models. Khi đó sẽ có hai tương tác/tradeoff quyết định cho design. Tương tác giữa computational và statistical constraints. Thuật toán phải đủ nhanh. Đây là một resource constraint của user, phần nhiều là computational. Nhưng models phải đủ phức tạp để diễn tả data. Cái này là statistical constraint. Tuy nhiên models phức tạp quá thì ta cũng không học vì 2 lý do: overfit (cái này là statistical constraint), hoặc không đủ computational và mathematical tools dde^? học nó.

Như vậy nếu không đặt cả model lên bàn ngay từ đâu thì ta không thể nói gì đuợc nhiều. Mô hình PAC hạn chế chính vì không đặt vai trò của model lên làm trọng tâm. Điều này khác với statistics, cũng như các khoa học khác. (Như bài báo của bác Hưng đã dẫn, model ví dụ chủ yếu của PAC là các Boolean classes, ra^’t i’t structure và ít có ứng dụng với data trong thực tế).

Nếu lấy models làm trọng tâm, thêm các assumptions về chúng, thì thuật toán sẽ đến theo. Các vấn đề về thuật toán và computational complexity vẫn còn nguyên đó, nhưng sẽ fruitful hơn.

Ta cũng có thể phê bình ngược lại với thống kê lý thuyết là họ quá chú trọng về model, nhưng lại hoàn toàn thờ ơ về các vấn đề computational. Phê bình này hoàn toàn đúng, nhưng từ thập niên 90 lại đây thì các nhà thống kê cũng program và optimize rất kinh.

Theo tôi đóng góp lâu dài của ML không phải là về lý thuyết (như PAC), mà chính là các mô hình/thuật toán độc đáo và hiệu quả. Tôi cũng bắt đầu đến với ML theory qua cái nhìn của PAC, và lúc đầu cũng rất ấn tượng với nó. Nhưng nếu học lại ML, tôi sẽ không bắt đầu bằng PAC, mà sẽ bắt đầu cùng với một vài quyển sách nhập môn statistics như quyển của Peter Bickel & Girshik, và quyển về Bayesian statistics của Jim Berger. Nếu muốn đi sâu vào lý thuyết learning, một quyển nhập môn Asymptotic Statistics của Van der Vaart chẳng hạn rất bổ ích. Và tìm hiểu càng nhiều dạng mô hình thống kê càng tốt.
Ngô Quang Hưng says:

July 15, 2008 at 6:06 pm

Hi bác Long, thanks for the informative comment, as always!

Tôi không có ý nói là Vapnik không nghiên cứu về learnability, mà chỉ nói là quyển nature of statistical learning theory của ông không có chương nào về tractability. Tôi sẽ viết về VC-dimension và ứng dụng trong một/hai bài tới.

Tôi cũng hoàn toàn đồng ý với bác là PAC như tôi đã trình bày đến nay rất hạn chế, nó chỉ mô tả mỗi bài classification trong supervised learning. Theo tôi hiểu thì gần đây COLT cũng có vài phát kiến mới, sẽ đọc và viết thêm.
Bach Hung Nguyen says:

July 16, 2008 at 4:28 am

Cảm ơn bác Hưng và bác Long đã viết & bình rất thú vị. Mục “Tối ưu hóa cái gì”, cái này theo em nghĩ thì là minimum error rate training với một hàm lỗi (error/loss function) hoặc là maximum likelihood of training data, do đó dù PAC-learning hay bất cứ loại learning algorithms/models gì cũng có thể dùng chung được thuật toán tối ưu.

Bác Long bình “Tuy nhiên models phức tạp quá thì ta cũng không học vì 2 lý do: overfit (cái này là statistical constraint), hoặc không đủ computational và mathematical tools dde^? học nó.”. Đúng là models càng phức tạp thì càng dễ overfit, nhưng đó là data sparseness và cái này là gốc của statistical learning. Khi thiết kế models ngoài những khoản constraints như bác Long viết thì ta phải quan tâm đến training data. Bác Hồ đã nói là “Tuổi nhỏ làm việc nhỏ, tùy theo sức của mình”, áp dụng vào ML nghĩa là nếu mức độ sophisticated của models phụ thuộc vào training data.

Machine translation có thể được nhìn dưới góc độ 1 bài toán classification. Khi ta muốn dịch 1 câu tiếng Việt sang tiếng Anh, cũng có thể hiều là ta muốn label câu tiếng Việt bởi 1 nhãn là câu tiếng Anh với tập nhãn là vô hạn. Tồn tại một features space bên tiếng Việt gọi là VS và 1 mapping function Phi(V) chuyển câu tiếng Việt V vào VS; tương tự với tiếng Anh là ES và Omega(E). Dịch Việt-Anh tương đương với hàm Omega(E) = W * Phi(V). Công viêc của training là học ma trận W (mùi SVM nồng nặc ) ).

Với ví dụ trên, một câu hỏi là liệu các bài toán có thể ép về 1 dạng nào đó của bài toán classification được ko?
newcomer says:

July 16, 2008 at 5:39 pm

Toi thay dich PAC sang tieng Viet la “Mô hình có lẽ xấp xỉ đúng” co ve nhu nong dan qua. Toi cung cung khong biet se dich nhu the nao nhung ma cho the thay tu “co le” thanh xac suat thi hay hon.
sloth says:

July 17, 2008 at 11:19 am

vài lời bàn loạn, hi vọng các sư phụ (bác Hưng, bác Long, who else?) chiếu cố chỉ giáo.

mô hình PAC, trong mắt của lý thuyết thống kê ko phải là cái gì quá xa lạ.
nhưng theo tôi hiểu thì PAC vẫn có mặt trong các bài báo ở COLT hiện nay (bài toán phân lớp cổ điển) khi xem xét trong ngữ cảnh active learning, semi-supervised learning, lí do là vì không có hoặc đòi hỏi khá nhẹ về phân bố xác suất của dữ liệu.

theo tôi hiểu, các mô hình, giải thuật active learning hay semi-supervised learning đã từng được (và vẫn đang được) xem xét dưới góc độ thống kê, nhưng khi đó luôn có giả thiết (ngầm hoặc hiện) về phân bố xác suất của dữ liệu.

theo tôi hiểu, 1 chủ đề khá hot ở COLT (và SODA?) mấy năm gần đây là “online learning” (nonstochastic) dạng “bandit” (partial feedback) với các biến thể về “number of bandits” (until infinite).
với trình độ < abc về CS lẫn ML, tôi không hiểu ngoài ứng dụng “online advertising” (ở mấy web search engines) và “obvious routing” mà các tác giả này đem ra làm ví dụ, mô hình dự đoán kiểu cờ bạc này có thể có ứng dụng cụ thể ở đâu nữa.

@bác Hưng:
- tôi không thích ví dụ spam filtering bằng ML lắm, vì theo tôi hiểu, lọc spam ở mức này là mức cuối cùng rồi (kiểu nan đề captcha, tính bảo mật của các giải thuật ML).
Ví dụ hiền lành, cổ điển kiểu phân loại emails, bài báo theo chủ đề có phù hợp với ML hơn không?
- tôi không hề có ý định phá bĩnh nhiệt tình của bác, nhưng tôi có mấy câu hỏi củ chuối (tương tự tên sinh viên nào đó của bác?) với tư cách 1 novice reader:
mục đích của series này là gì? tác giả định dẫn readers đi đến đâu?
dành cho đối tượng readers nào? và ko dành cho đối tượng nào?
(theo kiểu cụ Hồ (sgk lớp 4 nói thế): viết cho ai, viết để làm gì, rồi mới viết cái gì, viết như thế nào?)
- có gì thay đổi đáng kể nếu thay các chữ “ta” bằng “tôi” ko?
sorry bác, vì tôi vốn bị dị ứng nặng với các từ ta, chúng ta trong các bài báo mậu dịch vn (chúng ta phải thế này thế nọ, bla bla).
đọc mấy bài báo kiểu đó tôi thực sự chẳng hiểu là người nói, người viết đang muốn nói cụ thể đến ai, hay kiểu phiếm chỉ chí phèo, AQ, …
Ngô Quang Hưng says:

July 17, 2008 at 12:37 pm

Chào bác sloth

1. Các vấn đề liên quan đến online ad hiện nay là rất hot. Tôi có dịp nói chuyện với Prabhakar Raghavan mấy tháng trước và đa số các vấn đền algorithmic hoặc ML ở Yahoo Research ông nêu ra đều liên quan đến đề tài này. (Dĩ nhiên, ông ta cũng nói đến mục tiêu lâu dài hơn là phát triển computational economics/game theory/etc, however online ad is where you win or lose BILLIONS of USD in a few years. Yahoo literally lost roughly a billion dollars due to bad ad strategies/algorithms.)

2. Khi nào viết lại tôi sẽ thay ví dụ khác spam filtering. Quả là ví dụ này có hơi “khinh thường” ML. Dùng doc classification chắc tốt hơn. Thanks for your comments.

3. ta = chúng ta (as in “we” when I write papers, even in sole author papers). “We” doesn’t mean “you and I”, it’s just a standard academic and perhaps boring way to avoid the egoistic “I”

4. Tác giả đọc đến đâu thì dẫn reader(s) đến đó . Như đã nói từ đầu, đây là “nhật ký” của tôi khi đi tìm hiểu xem learnability mô hình bằng toán như thế nào. I’m happy as long as there are more than 2 people who’d take the time to read things I wrote and give useful feedbacks.
npson says:

July 17, 2008 at 3:02 pm

Hom nay, luc loi n-Category Cafe, thay co bai viet nay:
http://golem.ph.utexas.edu/category/2007/06/kernels_in_machine_learning_i.html#comments
Cac chuyen gia co y kien gi khong ?
Nguyen Xuan Long says:

July 17, 2008 at 4:11 pm

@npson: bài blog đó có một số ý, không rõ bác nhắc đến ý nào… Tuy nhiên quan điểm cá nhân tôi thì kernel methods chỉ là một dạng class of models hữu ích cho một số v/đ và data cụ thể, nhưng rất hạn chế trong nhiều trường hợp khác. Tiếp tục refine nó hoặc áp dụng một lớp mô hình hoàn toàn khác là sẽ tùy thuộc vào data. Tôi không coi kernel methods là một thứ cure-all panacea.

Ưu điểm chính của kernel-based models là: chúng đơn giản cho người dùng, vì không đòi hỏi modeling assumption. Chúng cũng đơn giản cho thuật toán học, vì chỉ là một dạng linear model trên một không gian Hilbert. Nhưng việc chúng đủ phức tạp để mô tả nhiều dạng data trong thực tế cho ta thấy vẻ đẹp và sức mạnh của một chút toán học cao cấp (a little more math goes a long way, moving to higher dimensional space, i.e.,
http://www.procul.org/blog/2006/03/08/going-to-higher-dimensional-space/
)

Về lý thuyết thì kernel-based estimator kho^ng phải là optimal in minimax sense. Xem, vi’ du/ một dạng tutorial sau:
E. J. Candès. Modern statistical estimation via oracle inequalities. Acta Numerica, 15 257-325.
(available from his homepage)

và manuscript cũng có online của GS I. Johnstone của Stanford vói tựa “Function estimation”, homepage:
http://stat.stanford.edu/people/faculty/johnstone/index.html

Có thể fix vấn đề (về sự hạn chế của kernel models) bằng cách learn a family of kernels. Tuy nhiên tôi không thích cách này vì nó cũng giống như một dạng đẩy mô hình neural network từ 2 tầng lên thành 3 tầng. Cách này mất đi vẻ đẹp và đơn giản của phương pháp kernel ban đầu. Lợi ích về sức mạnh mô hình chưa thấy đâu nhưng bạn sẽ chết ngập vì các vấn đề optimization phát sinh, (tương tự như với neural nets vậy).

@Nguyên: Có thể nhìn nhận vấn đề bác nói là một dạng classification, nhưng không rõ có useful không?
Nếu tôi muốn tấn công v/đ này tôi sẽ tấn công nó một cách trực diện thay vì reduce nó về một classification formulation, mà theo tôi khá là hạn chế, với bài toán của bác.
npson says:

July 18, 2008 at 2:27 pm

Cam on anh Long. Em khong biet nhieu, thay bac David ben ay lam ve Philosophy cung hoc ML roi co vai y kien khong biet tot xau the nao nen dem ve day hoi chuyen gia ay ma