Review sách: The Master Algorithm

the-master-algorithm-by-pedro-domingos

Dạo gần đây rảnh nên đọc được nhiều hơn, tạm thời sẽ review sách trước khi quay lại với series về Học củng cố (a.k.a. Reinforcement Learning).

Mình biết tới Pedro Domingos cách đây vài năm, khi đang làm vài thứ liên quan tới Sum-Product Networks. Lúc đó khá ấn tượng với paper SPN, vì cách tiếp cận thật sự rất fresh và original. Mặc dù vậy SPN có những hạn chế cố hữu (có thể sẽ viết 1 bài riêng về cái này) nên ứng dụng thực tế không nhiều. Tiếp theo “truyền thống” đó, sách này của Domingos cũng trình bày 1 góc nhìn tươi mới và hệ thống về Machine Learning nói chung.

Đọc sách này, người đọc rất dễ liên tưởng tới A Brief History of Time của Stephen Hawking. Cả 2 đều là sách nhập môn dành cho người không chuyên, một quyển cho Vật lí hiện đại và quyển kia cho Máy học. Cả 2 quyển sách đều làm việc đó bằng cách kể một câu chuyện, đều bắt đầu và diễn tiến bằng mục tiêu đi tìm một lí thuyết chung nhất cho lĩnh vực của nó: trong sách của Hawking là sự hợp nhất Thuyết tương đối rộng của Einstein với Quantum physics, trong sách của Domigos là universal learner: thuật toán “trùm cuối” của cả ngành Machine Learning. Mỗi quyển sách đều chỉ chứa đúng 1 công thức: sách của Hawking là E = mC^2, của Domingos là công thức của Markov Logic Networks. Thậm chí không biết vô tình hay cố ý, Domigos còn sử dụng chính xác định nghĩa của Hawking về scientific theory.

Tuy nhiên mình biết Machine Learning nhiều hơn một ít so với Vật lí lượng tử, thành ra cách tiếp nhận 2 quyển sách cũng khác nhau. Có lẽ một người học Vật lí đọc sách của Hawking cũng sẽ có cảm giác gần giống khi mình đọc sách của Domingos (và ngược lại – người đó đọc sách của Domingos cũng sẽ có cảm giác như mình đọc sách của Hawking). Cả 2 quyển đều đáng đọc, kể cả với những người làm việc lâu năm trong cả 2 ngành.

Anyway, mình khá thích sách của Domingos (bên cạnh một số điểm không thích), đặc biệt là các analogy mà tác giả dùng để giải thích các khái niệm trong ML. Mình sẽ ghi một vài analogy như vậy ở dưới đây, bạn nào tò mò có thể tự mua sách đọc thêm. Những analogy này sẽ rất hữu ích cho bạn nào đang đi dạy về ML, hoặc là thường xuyên phải giải thích ML cho người ngoại đạo.

Đầu tiên là hàm Sigmoid, hay gọi chung là S-curve. Domingos gọi đây là hàm quan trọng nhất thế giới. Thật ra hàm sigmoid rất đơn giản, nó là hàm phase transition (từ 0 lên 1) nên có thể biểu diễn rất nhiều hiện tượng thực tế (neuron sẽ gửi một signal vào axom khi nó tích đủ năng lượng, xác suất đảo chiều quay của electron quanh hạt nhân khi chịu tác dụng của từ trường, etc…), nhưng sigmoid còn là hàm smooth, nên tính toán vô cùng tiện lợi, và dễ làm toán. Thực tế ta có thể gặp hàm sigmoid ở rất nhiều nơi, kể cả trong kinh tế và các hiện tượng xã hội học (The Singularity của Ray Kurzweil rất có thể chỉ là một cách diễn giải sai lầm cho phần đầu của hàm Sigmoid). Đạo hàm của hàm sigmoid là một hàm exponential (bell curve), bất kể hàm smooth nào cũng có thể xấp xỉ bằng tổng của các hàm S-curve: khi hàm tăng thì ta cộng một S-curve, giảm thì trừ một S-curve. Bằng cách này ta có thể xấp xỉ hàm sine và cosine dễ dàng bằng S-curve. Hàm cosine được dùng trong DCT, thành ra cũng thấy hơi lạ là chưa có ai làm Discrete S-curve Transform (hoặc tại mình chưa biết?).

Thứ hai là The curse of dimensionality. Những ai học ML đàng hoàng chắc đều biết khái niệm này, nhưng đây là cách giải thích dễ hiểu nhất mà mình từng đọc: giải sử bạn có một trái cam, với phần tép cam có bán kính bằng 95% bán kính của cả quả cam (phần vỏ chiếm 5% còn lại). Nếu quả cam ở trong không gian 3 chiều (quả cam thật), thì phần tép cam có thể tích bằng 0.95^3 = 0.86 = 86\% thể tích cả quả cam. Giờ nếu quả cam ở trong không gian 100 chiều, thì thể tích của phần tép cam là 0.95^{100} = 0.006 = 0.6\% cả quả cam (nghĩa là quả cam chỉ toàn vỏ). Đây là một ví dụ cho thấy intuition của con người về không gian thấp chiều sẽ không còn đúng trong không gian nhiều chiều hơn. Chẳng hạn trong khi huấn luyện ML models bằng gradient descent, người ta nói nhiều về local minimum, nhưng thật ra trong không gian nhiều chiều thì đa số là saddle point chứ không phải là local optima.

Cuối cùng, đương nhiên phải nói 1 ít về nội dung quyển sách, nhưng nếu bạn nào không muốn bị spoiled thì không nên đọc đoạn dưới đây.

Ý tưởng xuyên suốt của quyển sách là toàn bộ võ lâm Supervised Machine Learning được chia làm 5 trường phái:

  • Phái Symbolic, với bí kíp Inverse deduction, có các cao thủ là Decision Tree và Logic Programming nói chung. Võ công phái này chuyên về suy diễn logic và các phép biến đổi logic, lấy cảm hứng từ logic hình thức, có nguồn gốc xa xưa từ thời Aristote.
  • Phái Evolutionary, với bí kíp Genetic Algorithms, có cao thủ là Genetic Programming. Võ công phái này lấy cảm hứng từ quá trình tiến hóa của tự nhiên.
  • Phái Bayesian, với bí kíp Probabilistic Inference (điển hình là Bayes theorem), có cao thủ là Graphical models. Võ công phái này xuất phát từ việc không tin tuyệt đối bố con thằng nào (gán xác suất cho tất cả mọi thứ), và có nguồn gốc từ ngành Statistics.
  • Phái Connectionist, với bí kíp backpropagation, có cao thủ là neural networks. Võ công phái này lấy cảm hứng từ neuroscience.
  • Phái Analogizers, với bí kíp extrapolation và analogical reasoning nói chung (A với B cùng chung 1 loại nếu A nhìn hao hao giống B, hoặc ở “gần” B). Cao thủ phái này gồm từ nearest neighbors cho tới SVM. Võ công phái này lấy cảm hứng từ tâm lí học và mathematical optimization.

Mỗi trường phái đều có điểm mạnh, yếu riêng, và đương nhiên một thuật toán kết hợp điểm mạnh của cả 5 trường phái có lẽ sẽ phù hợp để làm universal learner (hay Master Algorithm, như Domingos gọi), và là công cụ quan trọng để xây dựng General AI. Domigos đã cố gắng xây dựng một thuật toán như vậy, gọi là Markov Logic Network (đề tài PhD của một ông giáo của mình ngày trước), nhưng dĩ nhiên MLN vẫn chưa phải là universal learner.

Cách phân chia này khá mới, và mình cũng khá bất ngờ. Tuy nhiên nó chưa tính tới các thể loại ML khác như unsupervised, reinforcement, etc… Mặc dù vậy, mình vẫn thấy rất có cảm tình với ý tưởng kết hợp logic và probabilistic reasoning, cùng với tất cả những thứ khác.

Tóm lại, The Master Algorithm, mặc dù chưa đạt được tới tầm cỡ như A Brief History of Time, vẫn là sách đáng đọc cho các bạn trẻ mới bắt đầu học ML. Những người có thâm niên hơn chắc chỉ cần đọc 10 trang đầu là đủ. Hai chương cuối của sách toàn là chuyện “chém gió”, nên có thể đọc để giải trí cũng được.

Advertisements

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s