Cài đặt Anaconda trên window và ví dụ Machine Learning

Hôm nay được một đồng chí cùng công ty cũ giới thiệu về Anaconda để code python. Theo mình hiểu Anaconda đơn giản là một IDE giúp ta có thể code python đơn giản hơn, đặc biệt việc cài đặt Anaconda trên window rất đơn giản. Anaconda còn tích hợp rất nhiều thư viện cơ bản, đặc biệt là các thư viện về Machine Learning với giao diện sử dụng và thêm thư viện rất đơn giản.

Công cụ này trước đây mình đã từng nghe nhưng chưa tiến hành sử dụng bao giờ. Trong quá trình học tập và làm việc, mình đã sử dụng nhiều IDE nhưng đều chưa thấy hài lòng. Sau đây mình sẽ hướng dẫn từng bước để cài đặt Anaconda trên window và sử dụng Anaconda để viết một chương trình Machine Learning đơn giản.

Ví dụ:
– Pycharm: cũng khá nổi tiếng nhưng khi cài 1 số thư viện mở rộng vào thì không hiểu sao lại lỗi và bị conflict

– IntellJI: nặng, chậm và cũng conflict (có thể quá phức tạp với mình)

– Cuối cùng thì đành quay về với IDE của chính Python cung cấp, nhưng cũng khá khó chịu với cái khoản cài đặt thêm các thư viện bổ sung.

Nghe đồng chí đó nói với IDE này đã tích hợp sẵn nhiều thư viện về Machine nên cũng vọc thử xem sao, có mất gì đâu.

Tải và cài đặt:

Tài liệu trên mạng có nhiều, mình cài đặt theo trang chủ của nó:
https://www.anaconda.com/download/

Bạn có thể tham khảo thêm:
https://medium.com/@GalarnykMichael/install-python-on-windows-anaconda-c63c7c3d1444

http://xperimentallearning.blogspot.com/2017/02/steps-to-install-anaconda.html

Lưu ý: mình khá nhọ khi cứ next mà không để ý phần tích chọn việc thêm biến môi trường hay là đường dẫn path để khi ở command line của window có thể gọi lệnh conda.
Nếu tích phần đó thì ok không sao, nếu không tích thì dùng lệnh sau để set path(trên command line của window):

set PATH=%PATH%;C:\ProgramData\Anaconda2;C:\ProgramData\Anaconda2\Scripts\

Đường dẫn này phụ thuộc vào nơi bạn cài đặt Anaconda nhé.

Test thử xem sao:

cai-dat-anaconda-tren-window
cai-dat-anaconda-tren-window

Sau khi cài đặt xong thì anaconda có giao diện như sau:

Có vài phần mặc định mà ta có thể dùng:

– Jupyterlab: nhấn vào đó nó nhảy lên web luôn, cái này code và biên dịch trên web localhost của mình luôn.

tính năng Jupyterlab trên Anaconda

– Jupyternotebook: chưa rõ là gì luôn nhưng cũng chạy trên nền web.

– spyder: sẽ hiển thị lên IDE để ta có thể code vài chương trình đơn giản.

Mình làm theo link này để test trước: https://chieupham.github.io/2017/02/18/Python-Windows/

Trên đây là cách cài đặt Anaconda trên window, nếu xong bước này thì ta hoàn toàn có thể thử dùng nó để code một chương trình python đơn giản để test hoặc có thể thử một ví dụ về Machine Learning sau đây với thư viện chuyên về Machine Learning là sklearn.

Ví dụ Machine Learning với Anaconda

B1. Test 1 thư viện mặc định:

>>import numpy
>>umpy.__file__

B2. Test 1 thư viện cần cài thêm:

>import sklearn

Sẽ lỗi luôn

B3. Cài thêm thư viện sklearn

Sử dụng command line của window chạy: conda install scikit-learn
chọn y để đồng ý cài đặt sklearn (phần lưu ý phía trên sẽ có tác dụng cho phần này)
Thử lại xem thư viện có chưa nhé:

>import sklearn

B4. Chạy thử 1 chương trình theo hướng dẫn:
https://machinelearningcoban.com/2016/12/28/linearregression/
Ta có kết quả:

Một ví dụ về Machine Learning với Anaconda

Hay đấy chứ, chúc các bạn thành công!

Tổng hợp về trí tuệ nhân tạo

  • Slide về trí tuệ nhân tạo:

– Bài giảng của thầy Phạm Trọng Hoàn: https://pdfs.semanticscholar.org/presentation/33e2/1d6243aa43da3426198243dc387dcc69bdf1.pdf

– Nhập môn trí tuệ nhân tạo: https://pdfs.semanticscholar.org/presentation/33e2/1d6243aa43da3426198243dc387dcc69bdf1.pdf

– Trí tuệ nhân tạo: http://thuvien.tvu.edu.vn/ebook/download/cntt/baigiangtrituenhantao.pdf

  • Bài báo về trí tuệ nhân tạo:

– Bài nghiên cứu về ứng dụng trí tuệ tạo: https://arxiv.org/ftp/arxiv/papers/1801/1801.03604.pdf

  • Cổng tìm kiếm bài báo nghiên cứu khoa học:

– Semantic Scholar: https://www.semanticscholar.org/

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

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

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.

Tôi cho rằng vấn đề top-down vs. bottom-up về cơ bản là một trade-off giữa scalability và convergence time, theo nghĩa sau đây.

1 Trong kinh tế: kinh tế tập trung (i.e. top-down) giải quyết được một vấn đề nhỏ và cụ thể trong thời gian ngắn (ví dụ như Castro phủ Cuba bằng các cánh đồng mía 🙂 trong vài năm), nhưng kinh tế thị trường (i.e. bottom-up) mới có đủ scalability để giải quyết các bài toán kinh tế xã hội mà objective functions phức tạp, dễ bị curse of dimensionality. Nhưng để phát triển một nền kinh tế thị trường đến tuổi trưởng thành cần đầu tư thời gian lớn.

2 Trong networking (và distributed systems): hai trường phái thiết kế mạng cơ bản là “smart network” (top-down) và “dumb network” (bottom-up). Internet là một thực thể phức tạp được thiết kế với nguyên tắc end-to-end (dumb network). Sự thành công của Internet mấy mươi năm qua là minh chứng hùng hồn của tính scalability của giải pháp bottom-up. Ngược lại, còn rất nhiều vấn đề với design hiện tại, và còn rất lâu Internet mới tiến hóa đến mức làm chúng ta thỏa mãn.

3 Trong phát triển nhân lực: muốn đào tạo “con người mới XHCN” trong 5, 10 năm thì dùng top-down approach, muốn đào tạo các cá nhân sáng tạo đủ trình độ đáp ứng với thời đại thì phải cho tự do tí toáy mất nhiều thời gian hơn.

4 Ta có thể tìm ti tỉ các ví dụ tương tự khác với các scales khác nhau trong AI, chính trị, đời sống, yêu đương (các bác nghĩ một chốc sẽ ra analogy hay 🙂 ).

Tóm lại: khi chưa có tenure thì bác Long cần theo top-down để xây dựng credential nhanh chóng, có tenure rồi thì sang làm bottom-up như Brooks để thành giám đốc MIT AI Lab :-).

Interesting examples! Nhưng có lẽ khác với các lĩnh vực cụ thể trên, trong AI thế nào là kiến trúc bottom-up còn rất mơ hồ. Sự khó khăn này chắc là do tính đòi hỏi sự khái quát trong set-up của AI. Kiến trúc của Brooks còn quá giản đơn và hình như mấy con humanoids vẫn chưa làm gì ngoài mấy cái xác như trong sci-fi. Có lẽ bức tranh về kiến trúc bottom-up mới chỉ dừng lại ở mức độ “a new kind of science” của Wolfram (dẫu cái này cũng chưa có gì lthật à new hay deep gi` cả).

 

Tất cả những gì phần lớn chúng ta làm vẫn là những hòn gạch nhỏ trên tường mà thôi. 🙂

http://www.procul.org/blog/2007/06/25/ki%e1%ba%bfn-truc-top-down-va-bottom-up-trong-tri-tu%e1%bb%87-nhan-t%e1%ba%a1o/

Machine learning hay statistics? P3

Machine learning hay statistics? P3

Có một bài blog gần đây khá thú vị so sánh về machine learning và statistics (của Brendan O’Connor). Những nhận xét về sự khác nhau về culture giữa hai cộng đồng nghiên cứu khá chính xác. Xem ở đây.

Tôi cũng có quan điểm khá rõ ràng về vị trí của hai chuyên ngành này, (xem: đây đây ).

Qua bài blog này thì tôi đọc được bài viết của Leo Breiman trên Statistical Science, viết năm 2001, cũng khá thú vị. Xem ở đây

Xem thêm phần discussions, có tranh luận sôi nổi của nhiều tên tuổi khác, như Brad Efron, Emmanuel Parzen và David Cox. (Tôi rất khoái đọc phần discussions của các các tạp chí thống kê, như trông Journal of Royal Statistical Society B, Stat. Science). Học được rất nhiều quan niện và ý tưởng trong đó, mà ta không dễ dàng thấy được trong một bài báo formal. Giá mà KHMT cũng có phần discussion như vậy trong các tạp chí của mình).

Nói thêm về Leo Breiman, GS ở Berkeley (đã mất vài năm trước). Leo Breiman là một nhà thống kê tên tuổi của thế kỷ 20, một renaissance man. Điều thú vị là Leo Breiman bắt đầu là một probabilist tầm cỡ , sau đó trở thành một applied statistician, sau đó trở thành một cổ động viên nhiệt tình cho machine learning. Sự ủng hộ của một tên tuổi như Breiman cho machine learning có phần thái quá, nhưng có ích cho nhữngn người xuất thân từ ML 🙂

Tôi đồng tình với Breiman về tầm quan trọng của algorithmic modeling (tất nhiên rồi!). Breiman nhấn mạnh quan trọng của sự hiệu quả của thuật toán, prediction accuracy. Điều này, nhìn lại, thường là do các model khá đơn giản, nhưng lại vẫn có hiệu quả thuật toán và hiệu quả thống kê cao trong một số ứng dụng. Do đó Breiman muốn vứt bỏ đi model-based approach. Tôi bất đồng với quan điểm này. (Xem thêm phản hồi của Brad Efron). Tầm quan trọng của models là điều tôi học được từ statistics. Trong research statement tôi mới viết gần đây có ý: Many challenging problems in signal processing and systems can be fruitfully formulated as statistical inference with respect to some underlying model. This view emphasizes the modeling aspect of the approach and focuses on the central role of algorithm as being driven by the model, instead of being the driver.

Tất nhiên mô hình quá phức tạp, không thể verify được thì cũng vô ích. Mô hình tốt mà cồng kềnh thì không chạy thuật toán nhanh được thì cũng vô dụng. Nhưng xây dựng mô hình chính là nền tản của khoa học nói chung. Hiện tượng càng phức tạp buộc phải đòi hỏi các mô hình cũng phức tạp. Để có mô hình hữu ích và hữu dụng, ta cần nhiều công cụ toán học và xác suất, để xây dựng các mô hình mạnh, mà lại có nhiều structure cụ thể để ta có thể suy xét sử dụng (hay không). Ví dụ, ta thường nghĩ về model thông kê như là một hàm xác suất cho một nhóm các biến ngẫu nhiên. Nhưng một mô hình phức tạp hơn có thể là một hàm xác suất cho các objects phức tạp hơn, như các đồ thị, các hàm số. Thậm chí, ta còn có hàm xác suất cho tập các hàm xác suất ngẫu nhiên. Công cụ toán học cần là ở chỗ cho các stochastic processes, tuy có hành vi phức tạp, nhưng vẫn computationally manageable. Các stochastic processes này cho ta những viên gạch để xây các mô hình cho dữ liệu của các hành vi phức tạp.

Hãy hiểu rằng chúng ta đang ngày càng được bao phủ bởi các luồng dữ liệu, từ thế giới thực quanh ta thông quá các giác quan, cũng như từ các phương tiện thông tin đại chúng, từ Internet, từ laptop của bạn. Những gì ta cho là predictable được đều có thể hiểu là tuân thử theo một stochastic process nào đấy gắn kết tất cả mọi thứ với nhau.

Công cụ KHMT luôn luôn cần thiết trong modeling. Làm thế nào để diễn tả các mô hình một cách hiệu quả (data structure). Làm thế nào để inference với các mô hình đó cho tốt? Ta sẽ cần những nguyên tắc căn bản của algorithm design, như divide and conquer, modularity, recursion, memoization, v.v. Gần đây tôi có đối mặt với một số ví dụ cụ thể có liên quan đến vai trò của computation đối với sự đối chọi của frequentist và bayesian. Tôi nghĩ là computational complexity của nhiều vấn đề (và mô hình) làm cho sự đối chọi này không có nhiều ý nghĩa. Bayesians và frequentists đều có vai trò trong đó. Thông thường thì computer scientists (và machine learning researchers) rất thực dụng và không quan tâm đến mèo đen hay mèo trắng. Nhưng điều đáng nói là, computation làm cho môt số quan điểm của từng trường phái trở nên không vững vàng. Computation complexity không chỉ đơn thuần là một khái niệm về hiệu quả về thời gian hay không gian của một algorithm, mà nó gắn liền với khái niệm về độ phức tạp về information, mà qua đó sẽ chi phối quyết định của một người modeler (statisticians) cho dù anh ta khách quan hay chủ quan hay không. Sẽ quay lại cái này khi có dịp.

Quay lại với ML vs statistics. Thực ra sự phân chia giữa các chuyên ngành chỉ mang tính tương đối, và có ý nghĩa hành chính chủ yếu mà thôi. Có lẽ nên để hai ngành tiếp tục đứng riêng biệt, vì điều đó sẽ tạo ra nhiều ví trí trong job market :-). Với tôi thì statistics, KHMT, và machine learning có một tương lai rất sáng, trong một thế kỷ mà càng ngày access của chúng ta với data càng nhiều, càng nhanh, càng dễ dàng, và không thể tránh được.

 

Machine learning hay statistics? P2

Machine learning hay statistics? P2

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 complexity và hiệu quả thuật toán, và ML cũng góp phần phát triển nhiều mô hình (learning machines) rất thích hợp cho large scale và dynamically processed data mà ngành statistics đã từng thờ ơ. Ví dụ một số thuật ngữ sau ở machine learning nhưng không có mặt ở mainstream statistics cho đến thời gian gần đây:

  • computational complexity của một vấn đề learning
  • computational efficiency một learning machines
  • message-passing type algorithms
  • các mô hình về on-line learning
  • reinforcement learning
  • graphical models
  • v.v.

Nhìn lại, không khó mà nhận thấy rằng intellectual root của machine learning là statistics và computer science. Điều này không nằm ngoài quy luật của phát triển khoa học. Những hướng/ngành nghiên cứu mới có triển vọng thường phát triển từ sự giao thoa của nhiều ngành khoa học lớn đi trước nó. Trong lịch sử phát triển của trí tuệ nhân tạo nói chung và machine learning nói riêng, nhiều vị tiền bối trong ngành đã không có sự nhìn nhận xác đáng về cái gốc rễ ấy (statistics và continuous mathematics). Họ đã kỳ vọng là có thể phát triển công nghệ mới mà không cần đến những công cụ toán học đương đại (kể cả xác suất thống kê). Điều này làm cho trí tuệ nhân tạo và machine learning đi chậm lại hoặc lạc hướng vì đã bị cô lập với statistics cũng như các ngành liên quan như signal processing, information theory, operations research,… trong suốt mấy thập niên liền.

Tôi không nói điều gì thực sự mới mẻ ở đây đối với những người nghiên cứu ở cutting-edge của machine learning ngày nay, nhưng có thể là mới mẻ và hy vọng là hữu ích cho những bạn đang dự định nghiên cứu về machine learning, trí tuệ nhân tạo trong KHMT, cũng như nhiều ngành liên quan đến xử lý dữ liệu khác.

ML/CS Stats
learning value estimation
concept tôi nghĩ là nó là discrete output value.
learner model, hypothesis
bounding confidence interval estimation

clustering: còn có cả algebraic structure (manifold, spectral, …)?

Tóm lại theo bác thì Machine Learning có phải là một ngành khoa học không? Hay chỉ là nơi gặp gỡ của một số ngành khoa học cơ bản (stats, cs, info. theory, optimization, …) và rất nhiều ngành ứng dụng liên quan đến xử lý dữ liệu và ra quyết định dựa trên dữ liệu đang có (signal processing, bioinformatics, stats physics/mechantics, OR, game theory, econometrics, …).

Tôi không rõ lý do bác xếp PAC vào mục “linh tinh”. Vì bác không tìm thấy thuật ngữ tương ứng bên stats? Tôi nghĩ là nó tương ứng với “test hypothesis” hoặc là “large deviation (on finite size sample)” (?) nhưng nhấn mạnh vào sample size với fixed error value, và “output domain is a finite set (concept class)”.

on-line learning mà bác nói đến có gồm cả sequential coding, repeated game, … không? Nếu có thì tôi không rõ tại sao “thuật ngữ này không có mặt ở mainstream của stats cho đến gần đây”? Theo tôi hiểu thì “on-line learning” mà bác nói là “without stochastic assumption on the data sequence”.

@tvhvt: Tôi xếp PAC vào linh tinh vì chưa đủ terminologies cho một category mới. PAC có định nghĩa bên cạnh đấy (đúng với xác suất cao). Những ví dụ của bạn là đúng rồi. Điều đáng nói là trước PAC dân ML không dùng ngôn ngữ xác suất để nói chuyện. PAC là work lý thuyết đầu tiên làm chuyện đó, nhưng cái đó bên stat họ làm từ lâu rồi. Cái nhấn mạnh về sample size chỉ là cosmetic.

Online learning (with or without stochastic assumption), related cả với sequential coding bên information theory, theo tôi hiểu không có nhiều bên mainstream stat (mặc dù ta có thể trace một số work bên stat từ những năm 50). Tôi cũng có đọc một số work của statisticians như Vovk, nhưng không coi đó là mainstream. Bạn có ý khác?

clustering: mấy cái manifold/spectral clustering chưa được analyzed về mặt thống kê một cách cẩn thận, nhưng tôi tin tưởng là nó cũng tương ứng với một mô hình latent variable nào đó mà thôi. Ai tìm ra được mô hình đó thì sẽ là một kết quả đáng kể.

ML có phải là KH cơ bản không? Không biệt thế nào là KH cơ bản, nhưng tôi sẽ cho nó trong một rọ với statistics, information theory, signal processing, i.e., nó có cả nền tảng lý thuyết cũng như ứng dụng cụ thể như stat vậy. Thực ra với tôi thì, một cách lý tưởng thì ML = stat + computation

Đoạn thuật ngữ tương ứng ở comment 1, tôi quên lời dặn dò khi gõ dấu lớn hơn, nhỏ hơn của bác Hưng. Xin đọc là:
ML/CS: Stats
learning: value estimation
concept: discrete (nominal) output value
learner: model, hypothesis
bounding: confidence interval estimation
unrealizable hypothesis space: misspecified estimation (?)
semi-supervised learning(?): covariate shift (the training and the test distributions are not the same due to unknown reasons).

Tôi chưa rõ ý bác Long về “cosmetic” của PAC. Theo hiểu biết của tôi thì “sample size estimation, (optimal) experiment(al) design” trong stats chủ yếu là cho hàm hồi quy hoặc density estimation, nghĩa là real-valued output.

Tôi không rõ tiêu chuẩn “mainstream” của bác như thế nào. Có vẻ bác ngầm định là “(mainstream) stats” là xử lý (tìm ra 1 quy luật gì đó) trên bộ (mẫu) dữ liệu lớn vô hạn, là phải có kết quả về “asymptotic statistics”?
Khi “data population” là vô hạn (gồm cả dữ liệu động), muốn “học, mô phỏng” quy luật gì đó từ dữ liệu đã có (hữu hạn, non iid due to unknown reasons of sampling and/or labeling) thì có gọi là ML nhưng stats thì sao ạ? Bác sẽ bảo là Bayes stats đã có những “chước” cho những tình huống này rồi?
Tôi có 1 “phản ví dụ” (không điển hình?): “(supervised) learning the ranking function in document retrieval, web search” (tạm gọi theo mấy bác Yahoo! là “subset ranking”). Tôi chưa tìm ra mô hình nào trong thống kê thỏa mãn tất cả các ràng buộc dưới đây:
– ordinal feature vector/instance:
– ordinal value/instance in the ground truth:
– strictly ordered of K top instances at the output:
– cost function is some rank statistics whose the score function isn’t smoothed because they are ordinal values.

Tôi tạm thời nghĩ là ML

1
\supset

stats

1
\cap

computation.

Tôi không chuyên về clustering nên không rõ lắm. Nhưng theo tôi hiểu thì chuyện analyzed cẩn thận manifold/spectral clustering là phần của “probabilistic methods in graph theory, combinatorics”, không phải độc quyền của stats (?)

Tôi không định ép ML là 1 khoa học cơ bản hay khoa học ứng dụng. Theo tôi thì 1 ngành khoa học phải có:
– đối tượng nghiên cứu riêng: cái này là gì với ML thì tôi vẫn mơ hồ 🙁
– có vấn đề nghiên cứu:
– phương pháp luận nghiên cứu:
– còn công cụ giải quyết thì có thể vay mượn từ bất kì đâu (các ngành khoa học khác, từ thực tế).

machine learning hay statistics? P1

Machine learning hay statistics? P1

Khi tôi đang học đại học ở Postech và tìm một đề tài nghiên cứu tốt nghiệp, tôi làm quen với machine learning một cách tự nhiên. Mặc dù thích cả về lý thuyết thuật toán, nhưng ngày đó machine learning nghe sexy hơn nhiều. Tưởng tượng xem, tôi học ngành máy học (hay học máy nhỉ). Những năm 90 vẫn còn đọng lại dư âm cái hype của những neural networks và genetic algorithms bắt đầu từ thập niên 80. Ôi chà, những thuật toán có cảm hứng từ sinh học. Những lãng mạn từ “2001: A space odyssey” và MIT Robotics lab của Rodney Brook… Ông thầy vung vẩy tờ bìa Tạp chí Nature với cái tít “thế kỷ của brain science“, và tất nhiên tin học sẽ luôn là xe đò trong các khoa học tự nhiên và ứng dụng. This is it! Neural networks và genetic algorithms. Có rất nhiều tạp chí và conference, thậm chí cả PhD program được tập trung vào những lĩnh vực này. Thậm chí có rất nhiều người đã cao giọng khái quát hóa NNs và GAs thành các “paradigm”, “architecture” của trí tuệ nhân tạo trong tương lai. Rất nhiều chương trình nghiên cứu, như của thầy hướng dẫn thời undergraduate của tôi, chỉ xoay vần khá chật vật quanh mô hình này.

Ngày nay, NNs và GAs không còn nằm ở trung tâm của nghiên cứu machine learning hay artificial intelligence nữa. Một cách công bằng, NNs và GAs có thể coi là những dạng mô hình học hữu ích trong nhiều áp dụng thực tế. Nhưng chúng không phải là paradigm tổng quát gì cả, mà cũng có những hạn chế như rất nhiều mô hình thống kê khác. Không có gì bí ẩn tại sao các thuật toán NNs hay GAs lại work và không work. Thế mạnh và yếu đều được hiểu một cách khá cặn kẽ từ nền tảng thống kê cổ điển và hiện đại (classical và modern statistics), lý thuyết xác suất, lý thuyết xấp xỉ, v.v.

Có lẽ đóng góp lịch sử lớn nhất của NNs và GAs là sự hấp dẫn, mới lạ và sự hiệu quả của những phương pháp này. Chúng thu hút một số lượng lớn rất nhiều các kỹ sư, các nhà khoa học thực nghiệm và tính toán, vật lý lý thuyết, … tất cả những ai phải xử lý số lượng dữ liệu lớn và nhiều chiều. Những người này đã quan tâm đến và góp phần phát triển tiếp machine learning. Họ thường không ngại ngần gì với những data sets khổng lồ. Họ cần những giải pháp computation hữu hiệu, nhưng không thích quá nhiều assumption cứng nhắc về dữ liệu. Họ thực dụng, và không bị lệ thuộc vào các mô hình thống kê cổ điển giáo điều. Họ quả cảm và năng động chứ không máy móc như các nhà thống kê cổ điển. Và cũng giống như fashion, machine learning vẫn tiếp tục sexy, nhưng cái hype không còn là NNs hay GAs mà chuyển sang các mô hình thống kê khác, như graphical models (Bayes nets), support vector machines, các mô hình nonparametric Bayes, v.v.

Đó là một câu chuyện sơ lược về machine learning. Các ứng dụng của machine learning thường thú vị và bất ngờ, hương pháp áp dụng thường là những heuristic thông minh, nhưng lại ad hoc. Để phân tích và phát triển tiếp thì machine learning phải dựa vào nền tảng vững chắc của thống kê. Nếu bạn là một sinh viên đại học hoặc bắt đầu học cao học và muốn nghiên cứu về machine learning, thì phải học xác suất thống kê cho vững. Nếu không có thể bị chóng mặt bởi một đống fashionable algorithms của nó.

Vậy về mặt tri thức, machine learning và thống kê khác nhau ở điểm gì?

Đối với tôi, không hề có sự khác biệt mà chúng là một. Có thể nói đây là vision mà tôi chia sẻ với không ít người khác. Theo tôi, cả hai ngành đều cùng phát triển và sẽ hội tụ về thành một điểm trong tương lai. Gọi nó là statistical machine learning, hoặc computational statistics gì đều được. Đóng góp của statistics có tính chất nền tảng trong việc xử lý uncertainty, xử lý noise trong dữ liệu. Đóng góp của machine learning nói riêng và KHMT nói chung là sự chú trọng đến khía cạnh thuật toán và hiệu quả tính toán.

Trước đây thống kê cổ điển không chú trọng nhiều đến khía cạnh computation này, nên các sản phẩm của họ (dưới dạng statistical tests hoặc linear estimation procedures) thường có tính chất về computation rất đơn giản. Do đó chúng chỉ áp dụng được cho các data set rất nhỏ, mặc dù chúng có hiệu quả thống kê rất tốt về mặt lý thuyết; hoặc nếu data set lớn thì chỉ hữu ích khi chúng tuân thủ theo các assumption rất khắc nghiệt. Nhưng sự phát triển không ngừng của KHMT và những thành công của machine learning là cho các nhà thống kê học giật mình, và họ bắt đầu giang rộng vòng tay đón nhận machine learning như một lĩnh vực tiên phong trong statistics, sẵn sàng đón nhận những thách thức về computation bên cạnh độ hiệu quả về thống kê.

Quả thực sự phát triển của machine learning như thổi một luồng gió mới vào chính ngành statistics, làm cho nó sexy hơn. Một mặt khác, nhưng người làm về machine learning cũng cảm thấy cần thiết phải quay lại với những nền tảng của statistics để hiểu và gọt rũa các phương pháp heuristic của họ một cách hoàn chỉnh, và bớt đi phần ad hoc hơn.

Rồi bạn sẽ thấy ngày càng ít những phát biểu kiểu như: “My approach is neural network based, not a statistical one“. Trái lại bạn sẽ nghe thấy các nhà thống kê học nói nhiều hơn đến “algorithms” và “data structure”, còn dân KHMT sẽ nói nhiều đến “statistical analysis”. Bạn nào học machine learning khi trả lời phỏng vấn visa ở lãnh sự quán Mỹ, muốn tránh phiền phức với các chuyên ngành nhạy cảm (như AI, machine learning, vision, robotics,…) có thể thật thà theo giải pháp của tôi: nghiên cứu về statistical computer science Nói với tay lãnh sự rằng, it’s fun, it’s sexy, but not at all sensitive 🙂

ác Long,
Tôi quả thật muốn tìm hiểu về
– Sự áp dụng của Log-linear model, tôi không chắc rằng nó và Logistic Regression là một hay không, chỉ biết nó có tên gọi khác là Maximum Entropy. Sự khác biệt giữa Log-linear model và Bayes model được ET Jaynes đề cập đến trong “Probability: The logic of science”, tuy nhiên quả thật tôi cũng thấy rất mơ hồ về sự khác biệt này. Gần đây trong ngành Statistical Machine Learning, LL Model outperformed Bayes model, với sự tiên phong của FJ Och và Hermann Ney, hiện nay FJ Och đang làm leader nhóm Machine Translation của Google. Tuy nhiên, khi tôi nói chuyện với Bill Byrne http://mi.eng.cam.ac.uk/~wjb31/, anh ấy tỏ vẻ không tin vào LL model, và nói rằng: “Nhiều người cứ hay nói đến Feature Function trong LL Model, nhưng not many ones understand what a Feature Function is”. Tôi cho rằng nhiều researchers của Statistical Machine Learning (theo thuật ngữ của bác) vẫn có cái nhìn hoài nghi với LL model. Cá nhân tôi thì cho rằng LL Model là sexy (mượn lời của bác Long)
– Sự phát triển mạnh của Computational Neuroscience có đem lại điều gì mới mẻ cho Statistical Machine Learning không? Tôi mới để ý đến Comp. Neuro gần đây, và vẫn chưa nắm được các ý chính của nó.

@Cuong: Loglinear model va logistic regression đều thuộc họ GLIM (generalized linear models), mỗi thứ sẽ thích hợp với một việc khác nhau. Các sách basic về statistical models đều cover cả.

Re: log-linear model và Bayes model. Tôi chưa đọc Jaynes’s book nên không comment. Tuy nhiên nếu bạn muốn nói Bayes model là Bayesian models? hay generative Bayesian models? Và log-linear model là một ví dụ cụ thể của discriminative model? Nếu câu hỏi là “Bayesian generative models vs. discriminative models” thì câu trả lời của tôi là “there is no answer”. Tôi không tin vào chuyện một mô hình tốt hơn một mô hình khác. Đây là một vấn đề practical. Tùy thuộc vào data và domain knowledge. Còn Bayesian vs. frequentist methodology? Cũng không có câu trả lời đâu. Tùy vấn đề mà cách nhìn này hữu ích hơn cách kia. Trừ khi bạn nói chuyện triết lý (mà có vẻ như đây là cái mà Jaynes hướng tới). Tôi nhìn nhận chuyện này một cách pragmatic.

LL model is sexy? Tôi không nghĩ là như vậy. Với tôi đó chỉ là một model, không hơn không kém. Bài blog trên tôi nói đến sexy theo nghĩa perception chung của rất nhiều người. Nhưng kỳ thực cá nhân tôi không nghĩ là có bất kỳ một mô hình nào là sexy cả, mặc dù có thể có một số machine learning researchers (hoặc rất nhiều) hay chạy theo một mô hình nào đó mà họ cho là sexy. Một câu nói hay được nhắc là, all models are wrong, but some are useful. Nhưng tôi cũng xin chua thêm là, some are useful *some time*.

Re: Computational Neuroscience: Tôi coi đây là một application domain thú vị để model neural data, và useful theo nghĩa đó. Có thể có insight từ neuroscience được dùng để giúp cho việc tạo ra models thú vị hơn, giải thích được data và dùng để predict tốt hơn. Quả thực có khá nhiều collaboration giữa dân neuroscience và dân statistics/machine learning. Nhưng tôi không kỳ vọng là neuroscience sẽ tạo ra cái mới mẻ ngược lại cho SML.

Cảm ơn bác Long, tôi sẽ quay lại discuss chi tiết hơn sắp tới.

Từ chuyện bác nói “Bayesian vs. frequentist”, tôi liên tưởng đến một thời tôi đọc ở đâu đó về Probability vs. Fuzzy, Lại nhân chuyện bác nói “All models are wrong”, tôi cho rằng Fuzzy hay Prob cũng chỉ là cách ta model the real world thôi.

Nhân tiện tôi thử rephrase lại câu trên thành “All models are wrong, some are more useful than the others on some applications”.

Tôi tạm nghĩ rằng E.T. Jaynes chỉ discuss Maximum Entropy vs. Bayes method, trên bài toán sau:

“We have a feature vector X which we want to assign a label Y.
Bayesian method will try to estimate p(Y|X)=p(X|Y).p(Y)/p(X), i.e. we base on the datapoint’s likelihood p(X|Y) to find its posterior probability p(Y|X).

The maximum entropy method will try to estimate directly p(Y|X)=\frac{exp[\sum_{m=1}^M{lambda_m * H(Y,X)}]}{\sum_Y'{exp[\sum_{m=1}^M{lambda_m * H(Y’,X)}]}}, that is, to try to describe p(Y|X) discriminately using the “feature functions” H(Y,X)”

Đó là phần cơ bản nhất của sự hiểu của tôi về mối quan hệ Maximum Entropy vs. Bayesian Model. 2 models này chắc nằm trong mối quan hệ so sánh discriminative/generative. Tên “Maximum Entropy” được Jaynes dùng trong “The logic of science”, và được dân NLP dùng, ngoài ra nó đôi khi được gọi với tên Log-Linear (trong các papers liên quan đến ngành Machine Translation)

Một teacher của tôi nói rằng: “They are stupid calling log-linear as Maximum Entropy”, tôi thì chưa hiểu sự stupidity này.

Tôi cho rằng Log-Linear sexy hơn Bayesian (generative?) model, vì

a. Nó tổng quát hơn BG ở chỗ: các feature functions H đều có thể là p(X|Y) hoặc p(Y)
b. Nó cho phép dùng weight parameters, trong khi tích p(X|Y).p(Y) thì 2 weight đó đều là 1 (hình như ta cũng có thể dùng weight khác 1 với 2 thành phần của tích này, mà mô hình vẫn được gọi là Bayesian Generative model, tôi không rõ lắm)

Mô hình Log-Linear này được trained thế nào thì tôi vẫn chưa hiểu rõ, chỉ đọc được rằng ta có thể “train as many as 10^6 feature functions” (In particular, the use of discriminative training techniques based on millions of features seems to be promising http://www.elda.org/tcstar-workshop_2006/pdfs/keynotes/tcstar06_och.pdf)

Rất có thể tôi đã lẫn lộn giữa các khái niệm, so sánh không ngang hàng nhau ở đâu đó. Mong bác chỉ bảo.

Hi Cường — log-linear model chỉ là một mô hình khá đơn giản và phù hợp với một số domain như text hay dữ liệu dạng string. So sánh log-linear model với các mô hình Bayes là khập khiễng, giống như so sánh gà có đuôi tím ở rừng U Minh với các loài vât sống ở rừng Cúc Phương vậy. Các mô hình generative hierachical Bayes rất phức tạp hơn nhiều. Các mô hình discriminative như log-linear chỉ là một layer, nhưng ngày nay người ta cũng có những mô hình discriminative có nhiều layer hơn.

Dù dùng discriminative models hay generative models thì ngày nay đều có thể deal được với số lượng features rất lớn. Log-linear models có thể có nhiều features chính vì nó đơn giản và chỉ có một layer, nên về mặt computation thì rất hiệu quả. Nhưng trong nhiều ứng dụng thì nó không đủ để capture những quan hệ phức tạp hơn. Khi đó phải đòi hỏi đến hierchical models (generative hay discriminative gì cũng được).

Thầy Cường nói đúng đó: It’s stupid naive to say log-linear model as maximum entropy. Mặc dù log-linear model có tính chất appealing là đó chính là mô hình có maximum entropy nếu ta có moment constraints. Nhưng không phải lúc nào đó cũng là mô hình tốt. Đó là mô hình tối giản khi ta không còn thông tin nào khác tốt hơn về data ngoài các moment constraints. Nhưng như ai đó trên đã nói, vấn đề là moment với các feature nào. Đó là cả một vấn đề. Và đôi khi, ta có những knowledge hữu ích hơn thì sao. Cái nhìn lành mạnh, với tôi, là coi maximum entropy là một phương pháp để estimate mô hình. Nhưng còn có các phương pháp estimation khác nữa, gom chung là M-estimators (maximizing a risk functional) mà maximum entropy chỉ là một phương pháp đặc biệt trong đó. Nhiều người chỉ biết mỗi maximum entropy method nên họ chỉ dùng nó và tán dương nó lên thành “principle”, v.v.

Going to higher dimensional space?

Going to higher dimensional space?

Bài blog hôm qua của bác Hưng về bài phỏng vấn về trí tưởng tượng và toán học rất thú vị. Có rất nhiều issues đáng nói mà hy vọng bác Hưng có thời gian khai thêm mào. Tôi rất thích rất nhiều câu trả lời của giáo sư Mazur, đặc biệt trước nhiều câu hỏi (có thể cố tình làm) naive. Ví dụ câu sau đây, khi được hỏi:

“What about considerations involving higher dimensions than the three of common spatial experience? Must we rely on analogies to that common world? To what extent would that be possible without, perhaps, deluding ourselves that we are really understanding those more complex spaces, not just squashing them to fit our limited senses?”

Câu hỏi thú vị ở nhiều khía cạnh, cả về triết lý và về toán học. Câu trả lời cũng hay và dài. Sau đây là một trích đoạn, mà tôi tâm đắc từ một khía cạnh khác (algorithmics!):

“One isn’t quite finished if I just give you a finite repertoire — a bag of tricks, so to speak, in the art of squashing — because at a point in onés development of these intuitions, one actually sees more than the mere sum of tricks. One realizes that there is a certain unexpected pliability of spatial intuitions that makes spaces of any dimension equally accessible — equally accessible, and in certain respects (and here’s a surprise) more easily accessible than lower-dimensional spaces. Topologists understand very well that for certain important work, higher dimensional spaces are simply easier than lower-dimensional spaces — therés more room to move around…”

Nếu bạn là một người design thuật toán, có rất nhiều ví dụ tại sao công việc của chúng ta sẽ dễ dàng hơn rất nhiều khi chuyển vấn đề sang không gian nhiều chiều hơn. Vài ví dụ: neural network algorithms (with hidden layers), graphical models (with hidden variables, còn gọi là latent variables trong thống kê), thuật toán dựa trên (higher dimensional) reproducing kernel Hilbert spaces, v.v.

Additional dimensions cho chúng ta nhiều rooms để hiểu, giải thích vấn đề và thậm chí tìm ra các solutions ở đó. Nhiều thứ khi project ngược về lower-dimension trở nên rất khó hiểu, trở thành dạng “không mẫu mực” như đánh đố.

Một ví dụ điển hình khác là sự khác biệt giữa toán “sơ cấp” vs. toán cao cấp hơn.
Nhưng cái này thì có lẽ ai cũng biết…

Tôi thấy rất có lợi cho các graduate students của KHMT nên biết thêm về toán cao cấp, ít nhất là một số khía cạnh của chúng (ví dụ, các khái niệm cơ bản về abstract algebra, topology, measure theory). Đấy chính là một cách mở rộng cái knowledge/educational background space của chính mình lên higher dimensional space. Nó sẽ giúp ích bạn lâu dài trong công việc, và đôi khi cũng gây ấn tượng tốt với những đồng nghiệp trong KHMT đang sống ở 2-dimensional plane 🙂

Blessings and curses of dimensionality

Blessings and curses of dimensionality

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

1
N^2

lần, với số dimension

1
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!

Giới thiệu một số sách về tối ưu hóa

Giới thiệu một số sách về tối ưu hóa

Định chỉ viết một comment ngắn gọn vào bài viết hôm trước của anh Hưng, nhưng tôi thấy vấn đề này đáng một bài blog riêng. Những ai phải đối đầu với những vấn đề cụ thể trong nghiên cứu về kỹ thuật (engineering) đều gặp phải những bài toán tối ưu hóa (optimization) phức tạp, hoặc là rất nhiều chiều (high dimension), hoặc liên quan đến tính không lồi (nonconvexity), hoặc liên quan đến tính phi tuyến tính (nonlinearity), hoặc có tính tổ hợp và rời rạc (combinatorial/discrete), hoặc một vài các yếu tố khó khăn trên gộp lại.

Những kiến thức ban đầu về numerical analysis học từ đại học và phổ thông thì rất hạn chế, không đủ để giải quyết những vấn đề thực tế. Mặt khác, lại có rất nhiều sách về optimization. Một học trò bắt đầu tìm hiểu về optimization thường bị hoa mắt về các loại thuật ngữ programming (như linear programming, nonlinear programming, quadratic programming, convex programming, semi-infinite programming, semidefinite programming, d.c. programming, integer programming v.v)

Phải bắt đầu từ đâu? Cái gì thì cần đọc và cái gì không? Đây là những câu hỏi thường gặp phải với những ai bắt đầu tìm hiểu sâu một chút về optimization. Trừ khi ngành của bạn nghiên cứu chuyên về optimization (như giáo sư Hoàng Tụy), thường thì chúng ta không thể đọc hết mọi thứ một lúc, mà phải có chiến thuật học tập (chủ yếu là tự học). Chỉ nên học những khái niệm căn bản trước, và sau đó tra khảo thêm các phương pháp optimization mới khi cần.

Như anh Hưng đã nói, quyển đầu tiên nên sử dụng là quyển miễn phí của Stephen Boyd and Lieven Vandenberghe.

Convex optimization, S. Boyd and L. Vandenberghe, Cambridge Press, 2002.

Quyển này viết rất rõ ràng dễ hiểu, nhiều minh họa hình học, và chú trọng đặc biệt những khái niệm căn bản về giải tích lồi, trong đó có khái niệm đối ngẫu trong bài toán convex optimization. Thế mạnh của quyển sách là sự tập trung vào những bài toán có thể quy ra thành convex problems. Rất nhiều ví dụ thú vị bắt nguồn từ thực tế hoặc các nghiên cứu các ngành như thống kê hay information theory, nằm trong diện này, và do đó có thể giải quyết hiệu quả bằng interior point method. Phương pháp interior point (của hai nhà toán học người Nga, Nemirovski và Nesterov), có thể nói một trong những nguyên nhân chính góp phần dẫn đến sự ứng dụng rộng rãi của convex optimization methods vào các vấn đề trong engineering.

Xin nói thêm Nemirovski là người có nhiều đóng góp to lớn đối với lớp thuật toán hiện đại về optimization. Ông này cũng có ảnh hưởng đến sự phát triển của thuật toán polynomial time đầu tiên (của Khachyan) cho linear programs vào những năm 70 bằng ellipsoid methods. Thuật toán của Khachyan không được hiệu quả so với thuật toán simplex (dù về mặt lý thuyết có thể là exponential-time) của Dantzig, nhưng gây chấn động trong giới computational complexity. Đến thập niên 80 thì Karmakar mới giới thiệu một thuật toán hiệu quả hơn cho linear programs. Ý tưởng của Karmakar được Nemirovski phát triển lên cho semidefinite programs (cái sau kỳ thực có thể coi như linear programs cho không gian là những ma trận dương tính), và các bài toán convex bậc cao hơn.

Quyển sách của Boyd và Vandenberghe chủ yếu chỉ tập trung vào những ý tưởng thuật toán mới kể trên. Tuy vậy hai tác giả bỏ qua nhiều phương pháp tối ưu cổ điển rất hữu dụng cho cả các bài toán convex và nonconvex. Do đó, theo tôi nên đọc quyển sách của Boyd song song với quyển sách của Bertsekas:

Nonlinear programming. Dimitri P. Bertsekas, 2nd Edition, 2004.

Bertsekas nói rất tỉ mỉ về các vấn đề cụ thể ta thường phải đối phải khi phải sử dụng một thuật toán tối ưu. Ví dụ, nếu dung gradient descent thì cần phải tính đến chuyện điều khiển update stepsize như thế nào, v.v. Có mô tả khá đầy đủ các phương pháp cổ điển khác như conjugate gradient, golden section, v.v.

Đi sâu vào các dạng bài toán convex đặc thù, như linear programming (chuyên sâu về linear constraints và linear cost functions), có một quyển sách rất tốt của hai người đồng hương và đồng nghiệp của Bertsekas:

Linear optimization. Dimitris Bertsimas and John N. Tsitsiklis., 1997 .

Rất nhiều bài toán ta thường gặp hàng ngày và trong nghiên cứu có thể quy về dạng linear programs khá đơn giản (ví dụ như max flow, min cut).

Một dạng bài toán convex khác khá thú vị, liên quan đến max functions (hàm số có thể biểu diễn dưới dạng maximum của một số hàm khác). Bài toán đi tìm giá trị cực tiểu của max functions gọi là bài toán min-max, và hay gặp nhiều trong nhiều tình huống như game theory, decision theory và thống kê. Nếu là max của một số lượng vô hạn các hàm khác, thì bài toán minimax này được gọi là semi-infinite programs. Một quyển sách rất hay đi sâu về lĩnh vực này là:

Optimization: Algorithms and Consistent Approximations, by Elijah Polak, 1997.

Polak và Bertsikas có thể được xếp vào nhóm những người muôn năm cũ, so với lớp hậu sinh như Boyd. Những lớp già thường vẫn có những túi mẹo rất quý. Đọc những quyển sách của họ ta có thể học được nhiều cách nhìn vấn đề thú vị mà không thấy ở quyển sách của Boyd.

Rất nhiều vấn đề ta gặp không thể nào quy được về các dạng lồi cơ bản như kể trên. Tuy vậy những phương pháp optimization cho bài toán convex, và những hiểu biết về giải tích lồi rất cần thiết và hữu ích. Một mảng quan trọng là các vấn đề về combinatorial optimization, hay còn gọi là integer programming. Làm thế nào để sử dụng các phương pháp convex optimization (như linear programming, hay semidefinite programming) để thiết kế các thuật toán xấp xỉ cho các bài toán có tính chất combinatorial này? Đây đang là một hướng nghiên cứu nóng hổi trong thập niên 90 cho tới nay. Như anh Hưng đã nhắc đến, có nhiều đóng góp đáng kể của các tác giả như Lovasz, Schrijver, Jean Lasserre, Michel Goemans, v.v. Đây là một lĩnh vực cực kỳ rộng lớn, bao trùm nhiều ngành từ bên toán, theoretical CS, operations research, AI,… và tôi cũng không biết là bao. Theo tôi biết thì chưa có một quyển sách hệ thống nào về mảng này, đặc biệt nói về sự kết hợp giữa lý thuyết convex optimization cổ điển với combinatorial optimization, ngoài hệ thống lecture notes mà anh Hưng đã nhắc đến.

Một lĩnh vực rất rộng và tổng quát để tấn công các bài toán không convex gọi là global optimization. Chú ý là phần lớn các phương pháp optimization cho các bài toán convex đều dựa vào khái niệm gradient/subgradient, và do đó các update đều mang tính địa phương (local). Các phương pháp update không mang tính local có thể kể ra như các phép cắt, các phép decomposition, các phép branch and bound v.v. Giáo sư Hoàng Tụy chính là một trong những cha đẻ của lĩnh vực này. Một quyển sách rất hay của ông là:

Convex Analysis and Global Optimization (Nonconvex optimization and its applications), Hoang Tuy, Kluwer Academic Publishers, 1998.

Link to amazon.

Giá của quyển này trên amazon thật là kinh khủng. Có lẽ giáo sư Hoàng Tụy phải in thêm nhiều nữa. Quyển sách của Hoàng Tụy có phần đầu giới thiệu những khái niệm cơ bản về giải tích lồi (convex analysis) một cách rất súc tích, rõ ràng và bổ ích. Sau đó tác giả đi vào các khái niệm về d.c. programming (difference-of-convex programming), và các phương pháp global optimization kinh điển, bắt đầu từ nhát cắt Tụy nổi tiếng mà tác giả đã giới thiệu vào năm 1964. Xuyên suốt quyển sách là một tính chất căn bản của các hàm số liên tục (có lẽ tổng quát hơn thế): Tất cả các hàm này, kể cả khi không convex, đều có thể biểu diễn dưới dạng hiệu của hai hàm convex. Với các tập hợp không convex cũng có phát biểu tương tự. Vấn đề là làm sao ta có thể lợi dụng những tính chất về convexity để tìm điểm global optimum của các hàm d.c. Có thể nói có cả một trường phái về D.C. programming rất hung hậu bao gồm nhiều nhà toán học người Việt nam (ở viện Toán ở trong nước và nước ngoài). Đây là lĩnh vực khó, chưa có nhiều thuật toán hiệu quả, và hình như sự hiện diện còn hạn chế trong mainstream của ngành optimization.

Nếu nghề của bạn phải sử dụng nhiều đến optimization algorithms, thì không chóng thì chày cũng phải bỏ thời gian để tìm hiểu quy củ hơn các khái niệm cơ bản về giải tích lồi, như khái niệm đối ngẫu, convex calculus, v.v. Giải tích lồi tuy không khó, và có tính hình học trực quan cao, nhưng tôi vẫn luôn kinh ngạc khi thấy những khái niệm này xuất hiện “bất thình lình” ở mọi ngóc ngách một cách khá sâu sắc trong information theory, trong statistics, trong decision theory,… Hiểu biết sâu về giải tích lồi có thể giúp ta thiết kế và phân tích các thuật toán hiệu quả cho nhiều vấn đề tưởng như rất hóc búa.

Một quyển sách kinh điển về giải tích lồi là của Rockafellar:

Convex Analysis (Princeton Landmarks in mathematics and physics), R. Rockafellar, 1996.

Quyển sách này nên dung để tra khảo khi bạn cần tìm hiểu hoặc sử dụng một cách thấu đáo một khái niệm nào đó về giải tích lồi. Không nên dung để tự học vì sẽ bị ngập ngày vào những chi tiết chưa cần ngay. Để tự học thêm về convex analysis, một quyển sách rất tốt của hai tác giả người Pháp là:

Convex analysis and minimization algorithms, Jean-Baptiste Hiriart-Urruty and Claude Lemarechal. .

Quyển này viết rất sư phạm. Được chia làm hai volumes, phần một dành cho người mới học, phần hai cho cả chuyên gia. Ngoài ra, các tác giả còn có một quyển sách tóm lược cho cả hai cuốn vào một volume. Tất cả đều rất bổ ích.

Chắc chắn còn nhiều quyển sách rất hay về optimization nữa mà tôi chưa biết. Những chuyên gia nghiên cứu về optimization (các nhà toán học ứng dụng) phải mất cả đời để suy nghĩ và sáng tạo các thuật toán mới. Còn với những người sử dụng optimization trong công việc của mình như phần lớn dân học KHMT, có lẽ cũng phải mất cả đời tìm hiểu và mày mò sử dụng, biến tấu chúng vào bài toán cụ thể thì mới thành thạo được.

Vài quyển sách về optimization tôi không muốn giới thiệu cho bất kỳ ai vì các lý do (chủ quan) khác nhau:

Convex analysis and nonlinear optimization: Theory and Examples (by Jonathan Borwein, Adrian Lewis) : Quá ngắn gọn và cô đọng, có lẽ chỉ dành cho chuyên gia.

Combinatorial optimization: algorithms and comnplexity (Christo Papadimitriou and Ken Steiglitz): Không tệ, nhưng hơi hời hợt.

Nemirovski cùng với Ben-Tal còn là những người đầu tiên nghiên cứu về robust optimization, một lĩnh vực đang được nghiên cứu nhiều hiện nay. Về convex optimization, hai ông cũng có một cuốn sách thiên về conic optimization, Lectures on Mordern Convex Optimization. Bertsimas, người viết cuốn sách Introduction to Linear Optimization cũng đang nghiên cứu nhiều về robust optimization. Ngoài ra, ông vừa mới viết xong một cuốn sách về discrete optimization, Optimization over Integers cùng với Weismantel. Ông này cùng với sinh viên của mình nghiên cứu một thuật toán mới cho integer optimization dựa trên integral basis. Một cuốn sách của Schrijver về linear optimization cũng rất hay đó là Introduction to Linear and Integer Optimization. Lasserre là một người nghiên cứu khá nhiều lĩnh vực, giống như Bertsimas. Một lĩnh vực ông nghiên cứu nhiều là ứng dụng của hình học đại số (algebraic geometry) vào nhiều bài toán khác nhau, chẳng hạn như moment relaxation for integer optimization, hiện đang là relaxation tốt nhất. Về lĩnh vực hình học đại số này, còn phải kể đến Parrilo, người cũng đã có nhiều đóng góp mặc dù còn khá trẻ.

Một ý cuối cùng, cuốn sách của giáo sư Hoàng Tuỵ gần 200USD thì làm sao sinh viên có thể mua được. Đã có ai hỏi giáo sư về điều này chưa :-)?

Common sense và AI

Common sense và AI

Bài blog gần đây của anh Hưng nhắc đến câu chuyện với John McCarthy. Vị GS nổi tiếng này cho rằng: (…) không tin rằng common sense có gì fundamentally statistical hay probabilistic. Tôi nghĩ đây là một vấn đề thú vị — “blog-friendly” topic — nên lôi nó ra đây.

JMC là một trong những người đặt nền móng cho ngành TTNT cổ điển từ đầu thập kỷ 60. Ông là một trong những người khởi xướng việc sử dụng ngôn ngữ logic để biểu diễn và suy diễn kiến thức (knowledge) và common sense. Ý tưởng và sự ảnh hưởng của JMC thống trị giới nghiên cứu mainstream về AI trong suốt các thập kỷ sau đó. Nghiên cứu về AI liên quan chủ yếu đến số 0 và số 1 và gọi là “symbolic AI”, cho đến khi Judea Pearl xuất bản quyển sách landmark về graphical models năm 1988, và một số tác giả về cognitive science (Rumelhart, Hinton và William) nghiên cứu các mô hình neural networks cho learning. Với sự ra đời (thực ra là re-discovery) của neural nets, giống như nhiều thứ buzzwords trong KHMT và trong AI, có một dạo người ta tung hô “connectionist AI” như một câu trả lời mới cho TTNT. “Symbolic AI” bị rơi vào tình trạng defensive từ những ngày đó. Tuy nhiên ta không nên bị cuốn vào sự phân biệt non nớt giả tạo này.

Để hiểu JMC nói gì, tất nhiên ta phải đồng ý với nhau về ngôn ngữ. Trước hết, common sense là gì ? Common sense theo nghĩa thông thường, và common sense trong TTNT? Không dễ trả lời, cũng như nhiều thứ trong nghiên cứu TTNT, các khái niệm thường không có định nghĩa rõ ràng và gây tranh cãi, giống như câu hỏi “thế nào là AI” vậy. Hãy tạm đồng ý với nhau common sense là … common sense theo nghĩa hiểu của con người, đó là những mớ kiến thức căn bản thông thường trong cuộc sống, cần thiết cho sự sinh tồn và giao tiếp. Tất nhiên đây không phải là định nghĩa, nhưng có thể làm cho nó chặt chẽ hình thức hơn.

Giả sư chúng ta đồng ý với nhau về common sense rồi. Rất có thể JMC có lý, rằng khái niệm common sense (do JMC định nghĩ) không có tính chất probabilistic về bản chất. Nhưng cũng có thể JMC không đúng.

Với tôi thì common sense là khái niệm probablistic hay logical không quan trọng. 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?

Nói theo ngôn ngữ của AI, làm thế nào để học (learn) được common sense ? Câu hỏi này đến nay không hề được giải quyết. Một trong những khó khăn khi dùng pure logic để định nghĩa common sense là những khái niệm như “noise” và “uncertainty”. Những thứ này được coi là nuisance, chứ không phải là một phần của mô hình. Có nhiều cố gắng để khắc phục, những khái niệm khá rắc rối như non-monotonic logic và circumscription, nhưng vẫn không đạt được nhừng yêu cầu mà tôi nhắc tới ở trên: khả năng learnability (inductive inference).

Hãy tạm vứt bỏ khái niệm common sense ra khỏi đầu và nhìn theo một hướng ngược lại, cái gì thì (máy tính) có thể (tự động) học được ? Làm thế nào để giao diện máy tính với thế giới xung quanh, thông qua dữ liệu, để học được một cái gì đó hữu ích? Trong khi trường phái AI của JMC không có câu trả lời, thì đây chính là vấn đề của thống kê học: Làm thế nào để học được các mô hình hữu ích từ dữ liệu? Lý thuyết xác suất là một ngôn ngữ hữu hiệu để biểu diễn các mô hình thống kê, và có một lý thuyết đồ sộ về lý thuyết cũng như về tính toán (computation) làm sao có thể học được các mô hình thống kê từ dữ liệu. Ứng dụng của xác suất ở khắp nơi trong các ngành khoa học có sự giao diện với dữ liệu thực.

Vậy, có sự liên hệ gì không giữa các mô hình học được (bằng ngôn ngữ xác suất thống kê) với khái niệm common sense của JMC. Đến đây, ta có thể tạm thấy rằng câu hỏi này không có nhiều ý nghĩa như trước nữa. Sự xa cách giữa hai khái niệm này cũng chính là khoảng cách giữa hai trường phái top-downbottom-up trong TTNT. Top-down chính là dạng architecture được khởi xướng từ nhóm JMC và các lớp kế cận, và đã thống trị suy nghĩ của mainstream AI trong suốt thời gian dài. Tại sao là gọi là “top-down”? Một anh bạn chuyên gia về knowledge representation nói vui với tôi cách reasoning top-down sau đây: AI là quan trọng. Để có intelligence thì phải common sense để communicate. Do đó common sense quan trọng. Để có common sense, ta phải biểu diễn chúng, do đó vấn đề representation of logic rất quan trọng. Vì common sense có lẽ là khái niệm logical, nên ta sẽ dùng logic để biểu diễn và manipulate common sense…

Tìm cách bắc cầu giữa cái khoảng trống này (giữa hai trường phái) không phải là không thú vị. 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.

Ngoài ngôn ngữ xác suất thì còn ngôn ngữ nào có thể dùng để học các mô hình từ dữ liệu. Có, ví dụ như fuzzy logic của Zadeh . Nhưng những thứ làm được bằng fuzzy logic cũng có thể làm được bằng lý thuyết xác suất. Và lý thuyết xác suất là một lý thuyết toán học đồ sộ hơn, đã được xây dựng từ hàng trăm năm nay. Có lẽ câu hỏi đáng nói hơn không phải là vấn đề ngôn ngữ biểu diễn, rằng thế giới của chúng ta có “fundamentally probabilistic/random” hay không. Nhưng cái này vượt ra ngoài tầm của tôi mà sang địa hạt của theoretical physicists.

Trong hoàn cảnh không (và sẽ không) có định nghĩa và định hướng rõ ràng về AI, vấn đề thú vị có lẽ không phải là: AI nên sử dụng statistical methods hay logical methods. Vấn đề thú vị với tôi là, làm thế nào để giao diện máy tính với streams of data của thế giới bên ngoài. Nói cách khác, làm thế nào để máy tính có khả năng thích ứng (adapt) với môi trường xung quanh được cảm nhận qua các loại sensory data. Data ở đây có thể là bits, pulses, radio signals, video images, sounds, texts, documents, numbers, sequences, matrices,… Tôi cho rằng đây là một trong những topic quan trọng nhất của cả computer science trong thế kỷ 21. Các chuyên ngành của KHMT như architectures, operating systems, programming languages đang từng bước đối diện với nó. Nếu đó là quan tâm chính của AI, tuyệt. Nếu không, thì tôi sẽ không quan tâm đến AI làm gì. Câu hỏi trên đây không phải là quan tâm riêng của machine learning, đó cũng là quan tâm chung của signal processing , của information theory, của statistics , của các khoa học liên quan đến dữ liệu thực. Điều mà những người computer scientists đóng góp được vào trong việc trả lời câu hỏi này, làm sao sử dụng được những công cụ tính toán (algorithms, data structures) và các công cụ toán học (sơ và cao cấp) để giải quyết khi số lượng data rất khổng lồ.

Đó chính là thứ nghiên cứu về AI mà tôi quan tâm, cho dù nó có liên quan đến common sense hay không.

Trước khi bình loạn bài viết rất hay của anh Long, xin kể nốt một đoạn trong cái talk của JMC. Một đồng nghiệp của tôi hỏi câu tương tự câu tôi đã hỏi riêng John: “ông nghĩ gì về 3 cách tiếp cận AI: statistical/probabilistic methods, formal logic, và neural nets”. John trả lời: “hiện nay thì formal logic đang đi trước, nhưng cuối cùng thì bọn làm neural net sẽ thành công, song hành với sự thành công của neuro-science”.

Ý John tin rằng nếu ta hiểu rõ cấu trúc vật lý của não bộ con người thì ta có thể emulate chúng. JMC không nhắc gì đến probabilistic/statistical methods trong câu trả lời, gián tiếp khẳng định lại câu trả lời trước đó của mình.

Khẳng định này của John cần thêm một chút elaboration; Ví dụ: nếu giả thiết quantum mind là đúng thì ta lại còn phải chờ thêm advances in quantum computing nữa chứ không chỉ có các advances in neuroscience. Dĩ nhiên, ta cũng có thể cãi rằng nếu giả thiết này là đúng thì quantum computing là một phần của neuroscience. Tôi cho rằng như vậy thì hơi ép lý quá.

Mặt khác, nếu giả thiết trên là đúng thì neural networks và probabilistic/statistical methods lại converge ở một nơi, khi đó thì thú vị biết mấy! (Xem thêm mớ papers về consciousness nhìn từ các khoa học khác nhau.)

Nếu neural networks chỉ các thuật toán neural networks, thì thật ra các thuật toán này cũng có thể xếp vào một dạng statistical models. Các models này có thể pass messages dưới dạng numbers hoặc một dạng data nào đó, nhưng đều có thể được intepret và analyzed bằng các mô hình thống kê một cách trực tiếp hay gián tiếp. Qua đó có thể giải thích và hiểu khá thấu đáo là tại sao thuật toán kiểu như neural nets lại work, kỳ thực không có gì bí ẩn cả…

Neural networks của con người có thể coi là các statistical models hay không? Rất có thể. (Câu trả lời sẽ là chắc chắn, nếu ta giả sử các tín hiệu thông tin pass trong não là measurable theo nghĩa toán học của measure theory). Khó khăn là chúng ta chưa có access (và physical measurement) đầy đủ đến các messages được pass trong bộ não. Nhưng đã có một số nghiên cứu dùng Kalman filter (một dạng statistical models cụ thể) để phân tích và control não thông qua data được thu lượm được từ các cục cảm ứng từ đóng vào sọ (khỉ và người được thí nghiệm). Chúng ta đã nói về chuyện này ở đâu đó trong blog này, nhưng tôi không mò ra được trong archives.

Hôm trước tôi có dịp nói chuyện với một số vị profs làm về signal processing và information theory và statistics ở Berkeley. Được biết họ đang có một joint project làm về neuroscience. Như vậy đây đang là một active area cho dân EE/CS va` Stat.

Tôi rất ngạc nhiên khi anh Long không nhắc gì đến COLT (Computational Learning Theory) và các đóng góp của Valiant, đặc biệt là khi câu hỏi chính anh Long đặt ra là cái gì thì (máy tính) có thể (tự động) học được?. (Ngoài ra, trong bài viết có lẽ anh Long cũng nên address cả câu hỏi cái gì thì (máy tính) không thể tự động học được?.

Nhân tiện nói thêm, giáo sư Valiant cũng là một nhân vật đặc biệt mà tôi đã có dịp nói chuyện. Rất tiếc là tôi biết quá ít về learning theory để có thể hỏi ông các vấn đề liên quan. Tôi biết tốt hơn về các công trình khác của Valiant thời 70 (như superconcentrators, concentrators, #P, …) nên chỉ nói chuyện được với ông về các đề tài khá cũ này. Không cần phải hỏi, cha đẻ của sharp-P rất là … sharp :-).

Đồng ý với anh Hưng về đóng góp đặc biệt của Valiant trong COLT ở thập niên 80, đặc biệt là mặt lịch sử. Đóng góp của Valiat về learnability gây chấn động trong dân làm machine learning (lúc đó người ta mới hiểu ra rằng why learning is possible). Tuy nhiên một phần đó là do những người làm về learning nói riêng và TTNT nói chung không để ý đến probability/statistics literature. Nhìn lại thì những lý thuyết của Valiant chỉ là một subset rất nhỏ của những gì người ta đã biết từ trước đó rồi (goes back to Fisher từ những năm 30, cho đến Le Cam thập niên 60, cho đến Dudley rồi Vapnik, etc làm về empirical processes ở thập niên 70).

Cái gì thì không học được? Nếu dùng measure theory thì vấn đề chính là cái gì thì measure được (measurable theo nghĩa toán học) thì máy tính sẽ học được hết (bang cach dùng statistical models), vấn đề là học được bao nhiêu mà thôi.

Quay lại đôi chút về human neural network as statistical models…
Tất nhiên nếu chúng ta đi sâu vào đến quantum level và các vị làm quantum physics chỉ ra rằng không bao giờ measure được mọi thứ thì chịu… Nhưng nếu ta dừng lại ở những thứ data observed/measured được bằng physical instruments thì luôn luôn có thể dùng probablistic/statistical methods để phân tích.

Vụ điều khiển máy tính bằng ý nghĩ tôi cũng không tìm lại được post cũ, tuy nhiên các bạn có thể xem bài này ở tạp chí Nature.

Nói leo với các bác một cái nhỉ. Bác Long viết “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ắc bác ngụ ý kiểu xây dựng những ontology database là sẽ không robust đúng không nhỉ? Đọc đoạn này thì em thấy đây là kiểu bias-variance trade-off trong Machine Learning.

Về vụ điều khiển máy tính và suy nghĩ, chẳng đâu xa lab em đang có 2 chú làm về cái này. Em thấy hay phết. Đại khái là cái project đấy là cố gắng để máy tính có thể nhận dạng được các suy nghĩ đơn giản trong đầu ví dụ: nước, quả táo, ăn, uống. Ý tưởng là mỗi khi não người nghĩ đến một object hoặc action nào đó thì sẽ sinh ra một loại sóng điện gì đó; bằng cách thu thập các sóng đặc trưng trong não thì có thể nhận dạng được các suy nghĩ.

Nhân nói đến chuyện common sense và statistical methods trong AI. Có một ví dụ thế này, hồi lâu rồi cách đây độ vài chục năm vào một mùa hè giữa những năm 50s dân làm máy tính (hội ở Mĩ) mới họp nhau lại bàn bạc để tìm xem bây giờ bài toán nào có tính ứng dụng cũng như khả thi giải được. Sau mấy chầu rượu thịt chó, các bác phán Machine Translation sẽ là bài toán tốt để làm, và có thể làm được trong vòng khoảng 20-30 năm. Có vài lí do để họ tin điều đó là lúc đó thì lí thuyết biểu diện logic đang mạnh, khả năng tiên đoán về độ phức tạp của bài toán Machine Translation còn quá giới hạn, common sense là dậy cho máy tính 1 đống grammar rules là có thể xử lí được bài toán, vân vân và vân vân.

Thực tế thì những năm 50s Bộ Quốc Phòng Mĩ (DoD) bắt đầu tài trợ cho các dự án về dịch máy (lúc đầu gọi là mechanical translation sau này đổi thành machine translation – MT). Hội nghị đầu tiên về MT được tổ chức tại MIT. Cũng vào khoảng thời gian những năm 50s và 60s, Zellig Harris (MIT) và học trò của mình, Noam Chomsky, theo đuổi các ý tưởng về việc phát triển một hệ thống hình thức mô tả ngôn ngữ. Công trình tiêu biểu của Chomsky là lý thuyết ngôn ngữ hình thức (formal language theory), và đặc biệt là các kết quả về văn phạm phi ngữ cảnh (context-free grammar).

Đến những năm 70s, sau 20 năm thì nghành MT vẫn tắc tị. Vài điểm yếu là không thể dịch được với vốn từ lớn, không thể dịch nhanh, tốn qua nhiều thời gian vào việc xây dựng các luật ngôn ngữ, và tranh cãi xem luật nào đúng hơn hay hiệu quả hơn. Dân làm MT chật vật không biết tiến về đâu.

Thế rồi có một bác tên gọi là Fred Jelinek, lúc đó đang ở IBM, mới quyết tâm áp dụng các mô hình thống kê vào bài toán Nhận Dạng Tiếng Nói (NDTN). Một bài toán được coi là dễ hơn Machine Translation 1 tí xíu. Fred lấy cảm hứng không phải từ ngông ngữ học, hay ngữ âm học mà là từ khoa học xử lý thông tin và trí tuệ nhân tạo. Công trình “A Mathematical Theory of Communication” của Claude Shannon đăng trên tạp chí khoa học Bell Labs năm 1948 là bước ngoặt quan trọng có ảnh hưởng to lớn đến toàn bộ nghành khoa học máy tính nói chung và nghành nghiên cứu và xử lý ngông ngữ nói riêng. Shannon đã chuyển đổi khái niệm nội dung thông tin từ một khái niệm có tính chất duy lí trí sang một dạng toán học có thể tính toán được là entropy. Kết quả của Shannon được ứng dụng trong rất nhiều lĩnh vực ví dụ như DSP, coding theory, …. Trong CL, entropy là độ đo dùng để đánh giá các mô hình ngôn ngữ. Fred Jelinek là một trong những học trò của Shannon đã áp dụng các phương pháp luận của Information Theory, Statistics, & Optimization vào hệ thống NDTN bằng phương pháp thông kê.

Một câu nói nổi tiếng của Fred là “Every time I fire a linguist, the performance of our speech recognition system goes up.”

Những tiến bộ của statistical methods trong NDTN ảnh hưởng đến MT với sự ra đời của bài báo “The Mathematics of Statistical Machine Translation” vào năm 93. Không có gì ngạc nhiên là các tác giả đến từ nhóm của Fred Jelinek tại IBM. Bài này được giới làm xử lí ngôn ngữ tự nhiên (NLP) đánh giá là bài báo quan trọng nhận của trong vòng 20 năm gần đây của nghành. Chỉ trong vòng chưa đầy 10 năm, tất cả các hệ thống SMT đều outperform các hệ thống rule-based MT có tuổi đời phát triển lâu hơn nhiều.

Vậy thì với hai hệ thống NDTN và Dịch Tự Động, liệu pp thống kê có phải là lời giải cuối cùng hay rộng hơn với những bài toán học của máy tính, pp thống kê có phải là lời giải tốt nhất hay không? Quan sát của tôi thấy rằng trong vòng khoảng 5 năm nữa statistical methods vẫn outperform các pp kiểu như McCathy, nhưng chắc chắn rằng pp thống kê sẽ dừng lại ở một ngưỡng nào đó. Một trong những dấu hiệu là năm ngoái, Google, một cty hiếm khi xuất đầu lộ diện ở các hội thảo, đã trình bầy hệ thống Dịch Tự Động bằng pp thống kê với dữ liệu huấn luyện là 200 Tỉ Từ. Learning curve của hệ thống này gần như là ở plateau trong khoảng từ 150 Tỉ đến 200 Tỉ. Chất lượng dịch rất tốt, thời gian huấn luyện là độ 3-4 ngày trên cluster khoảng 1000 máy. Dân làm SMT thường kinh lắm là dậy cho máy tính với độ 2-3 Tỉ Từ.

Dúng là câu trả lời hôm qua của tôi hơi vơ đũa cả nắm và nhiều lỗ hổng. Thực ra có thể thêm một bài blog dài ở đây. Nếu không sử dụng nền tảng là lý thuyết xác suất thì tôi không có câu trả lời, vì ngoài lý thuyết xác suất (mà dân làm thống kê, và dân làm information theory như Shannon et al) đã quantify rất khéo) không có cách nào để quantify learnability (sẽ nói thêm ở dưới). Còn trong phạm vi lý thuyết xác suất, thì vấn đề giới hạn của learning có thể học được chừng nào (lower bounds/achievable bounds) chính là vấn đề rates (trade-off giữa learning error và number of samples cần phải dùng, using minimax bounds). Đây là vấn đề lý thuyết thú vị và khó. Nhưng dân làm statistics đã nghiên cứu từ lâu (từ thời Le Cam thập niên 60). Tuy nhiên đây không phải là formulation duy nhất. Gần đây, tôi cảm tưởng formulation về list decoding problem của Sudan và các co-authors là một hướng hay có thể add thêm flavor của complexity theory vào learning.

Một comment về nền tảng lý thuyết xác suất: Tất nhiên là phải có giới hạn ở đâu đó. Ví dụ về mặt toán học có nhiều objects kỳ quái, nhưng Cantor set, tuy dense nhưng lại chỉ có Lebesgue measure 0. Phần lớn các phương pháp xác suất thống kê ngầm hiểu là underlying measure và underlying topology match each other in a regular (nice) way. Vì vậy hoàn toàn có thể come up với những objects mà các phuong phap TK hiện tại sẽ break down…

Tuy vậy trong phạm vi PPTK, tôi nghĩ còn rất rất lâu mới đi đến điểm đó, đặc biệt các ứng dụng đời thường trong AI, signal processing, statistics. Những cái anh Hưng nói trong security thì chắc là dễ đến điểm limit đó thật.

Nếu nhìn vào signal processing và information theory/coding theory, có lịch sử phát triển lâu hơn nhiều so với AI thì thấy ngôn ngữ xác suất còn vai trò nền tảng quan trọng thế nào. Trong những ngành này chưa ai dự đoán về limit của nền tảng này trong các phương pháp coding/compression/communications state of the art.

Thông thường một công cụ nào đó đạt tới giới hạn thì lại có thể improved bằng cách khác nhưng không phải là từ bỏ PPTK. Điều thường xảy ra nhất là người ta thay một mô hình đang sử dụng bằng mô hình khác thích hợp hơn. Để làm được điều này phải có hai nhân tố: (1) Hiểu vấn đề (problem domain) sâu sắc hơn và (2) Có công cụ toán học mạnh hơn.

Một ví dụ: Hồi những năm 80 thì người ta làm rùm beng lên với neural nets. Chẳng qua đây chỉ là một cách supercomposition của các hàm số đơn giản mà thôi. Một dạng toán học của thế kỷ 18/19. Tuy nhiên sau vài năm cũng run into limit, vì để learn những mô hình này thì phải giải quyết một bài toán optimization không lồi và không đơn giản. Cuối thập niên 90 thì rùm beng với kernel methods, việc optimization đơn giản hơn learning neural nets nhiều, nhưng khả năng approximate vẫn rất mạnh vì dùng function spaces vô hạn chiều. Machine learning phát triển bằng cách áp dụng công cụ toán học của những năm 40/50 của thế kỷ 20 thay vì công cụ của thế kỷ 18/19. Bên signal processing cũng rùm beng về wavelet methods, chẳng qua là áp dụng công cụ của toán học của những năm 60/70. Việc bùng nổ về graphical models ở machine learning/statistical physics/coding/computational biology/ chẳng qua là cách áp dụng graph theory vào để combine các building blocks là những mô hình thống kê đơn giản hơn.

Việc sử dụng tất cả các công cụ kể trên, đều dựa trên nền tảng là PPXS/TK.

Đơn giản là tôi nghĩ lý thuyết xác suất/measure theory cho phép xây dựng rất nhiều structures giàu có (stochastic processes), và có thể combine/absorb rất nhiều lĩnh vực khác của toán học để tạo ra những công cụ mạnh. Đặc biệt những ngành trong analysis như harmonic analysis/approximation theory. Gần đây bắt đầu có một số người đã /đang sử dụng các công cụ algebraic geometry nữa… Nói chung tôi thấy càng blend analysis với algebra thì càng ra nhiều công cụ mạnh cho learning (và khi đó thì chúng ta càng phải học thêm nhiều toán 🙂

Tuy nhiên tôi cũng nghĩ nhiều thứ không thể learn được, như trong phần comment trước của tôi với anh Hưng. Những cái gì không phải là “common sense” thì chắc chắn là khó. Ngoài ra những gì phải ngoại suy (extrapolation) thì chắc chắn là khó (nếu không nói là vô vọng) hơn là nội suy (interpolation).

Tôi vẫn nghĩ để tạo ra trí tuệ nhân tạo, cách tiếp cận của sinh học sẽ nhanh và đúng hướng hơn khoa học máy tính.

AI đã phát triển hơn nửa thế kỷ, nhưng ứng dụng thực tế thì như thế nào? Nhận dạng tiếng nói, chữ viết được bao nhiêu??? Dường như các chuyên gia CS cứ cố gắng hiểu và điều khiển mọi quá trình tư duy của con người, nhưng đến bao giờ mới hiểu hết được cấu trúc não bộ để mà mô phỏng. Chưa kể vấn đề Ý thức ở đâu mà ra nằm ngoài phạm trù nghiên cứu của KHMT.

Trong khi đấy, bên sinh học chẳng cần biết con người được cấu tạo như thế nào vẫn nhân bản được 1 con người hoàn toàn mới.

Tôi nghĩ là không cần phải biết não cấu tạo như thế nào, mà chỉ cần tách được riêng não và nuôi sống nó, rồi nhân bản. Đấy là việc của các nhà sinh học. Nhiệm vụ của các nhà CS là tìm cách nối bàn phím, màn hình vào bộ não ấy.