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.

Giáo sư Lofti Zadeh, thuyết mờ, và con đường đi đến một trí tuệ nhân tạo

Giáo sư Lofti Zadeh, thuyết mờ, và con đường đi đến một trí tuệ nhân tạo

Hôm nay tôi nhân được một email quảng cáo của một hội nghị sắp tới được tổ chức để kỷ niệm những công hiến của giáo sư Lofti Zadeh , cha đẻ của lý thuyết mờ (fuzzy sets and fuzzy logic).

Trước khi Zadeh xuất bản công trình đầu tiên về lý thuyết tập mờ vào năm 1965, ông đã là một trong những nhà nghiên cứu tên tuổi nhất ở Mỹ trong ngành điện tử, xử lý tín hiệu, lý thuyết hệ thống, v.v. Ông chính là người sáng tạo ra phương pháp z-transform cho tín hiệu rời rạc, là một trong những người đặt nền móng cho lý thuyết state-space cho linear systems mà chúng ta được học trong những sách giáo khoa về signal and systems, phát triển lý thuyết dự đoán của Wiener. Chỉ nhờ những cống hiến của những năm 1950 của Zadeh cũng đủ để người ta nhắc đến ông như những ông tổ của signal processing, cùng với những Claude Shannon, Richard Bellman hay Nobert Wiener.

Từ năm 1965 trở đi, Zadeh cống hiến toàn bộ sức lực của mình vào phát triển lý thuyết tập mờ, logic mờ và ứng dụng của chúng trong lý thuyết điều khiển, hệ thống và trí tuệ nhân tạo. Zadeh tin rằng lý thuyết mờ chính là ngôn ngữ chủ đạo, là một chìa khóa quan trọng để giúp cho chúng ta mở cửa lâu đài bí ẩn Trí tuệ nhân tạo mà Turing đã
gõ cửa giúp.

Về sự đón nhận của giới hàn lâm (academics) với lý thuyết của Zadeh thì có nhiều tranh cãi. Nói chung giới nghiên cứu về signal processing cũng như giới nghiên cứu trí tuệ nhân tạo ở Mỹ thì rất lạnh nhạt. Những người làm về xác suất và thông kê thì nhún vai, cho rằng lý thuyết mờ có thể xây dựng trực tiếp từ nền tản của lý thuyết xác suất đồ sộ và lâu đời hơn. Mặc dù vậy, ở châu Âu, Nhật bản và các nước khác thì nghe nói phong trào nghiên cứu về lý thuyết mờ và ứng dụng của chúng phát triển rất mạnh. Có một vài bloggers ở đây là chuyên gia về lĩnh vực này.

Với những người ngoại đạo, thì chúng ta có thể thấy chữ fuzzy xuất hiện trên các máy giặt của Nhật bản và Hàn Quốc. Vài năm trước khi về thăm nhà, tôi còn được giới thiệu một cuốn sách nghiên cứu về Kinh Dịch bằng lý thuyết tập mờ của giáo sư vật lý Hoàng Phương. (Cách đây vài năm báo chí ở Mỹ hay nhắc đến chữ fuzzy math của Bush, nhưng có lẽ Bush không biết mình nói gì :-).

Là một học trò của ngành trí tuệ nhân tạo (TTNT), thỉnh thoảng vẫn thấy Zadeh đi đến office hay ra quán cafe, nhưng tôi thú thật cũng không hiểu biết gì nhiều về lý thuyết mờ. Đó là kết quả của sự giáo dục chính thống về trí tuệ nhân tạo trong suốt 50 năm qua, hầu như bỏ lý thuyết này ra ngoài. Điều thú vị là giáo sư Stuart Russell, tác giả của quyển sách giáo khoa nhập môn TTNT rất hợp thời trang hiện nay, người vẫn coi Zadeh là một mentor, cũng không phải là một người theo đuổi quan điểm của Zadeh về TTNT. Hai ông này có hai offices ở ngay cạnh nhau.
Ở trong khoa Electrical Engineering and Computer Science ở Berkeley, Zadeh luôn là một nhân vật được tất cả mọi người kính trọng. Nhưng ông luôn là một nhà tiên phong cô đơn ở đây. Một giáo sư về signal processing trong khoa từng nói với tôi: “Trước năm 60 thì Zadeh là thần đồng, còn sau đó ông ấy là một tên điên khùng”.
Điều đó cho ta thấy sự tiếp nhận của giới mainstream trong ngành với Zadeh còn nhiều trắc trở thế nào.

Tại sao lý thuyết của Zadeh lại có một lịch sử trắc trở như vậy, với dân làm về signal processing, hay dân làm về xác suất thống kê, thì tôi không biết nhiều để suy đoán. Tuy nhiên trong ngành TTNT, thì có lẽ ta đã có thể kết luận được vài điều. Khi Zadeh xuất bản những ý tưởng đầu tiên về tập mờ với hy vọng nó sẽ là một ngôn ngữ cho TTNT, ông đã đi trước TTNT ít nhất 20 năm. Khi ấy những ông tổ của TTNT, như John McCarthy, Herbert Simon , Alen Newell đang còn đắm chìm trong sức mạnh tính toán của máy tính và vẻ đẹp và sức mạnh của ngôn ngữ logic toán học. Họ cho rằng logic hy vọng sẽ là ngôn ngữ thích hợp nhất để xây dựng TTNT. PhảI đến hơn 20 năm sau, người ta mới nhận ra rằng mặc dù logic có thể là ngôn ngữ hữu hiệu để computers có thể biết chơi cờ và suy luận rất … logic, nhưng lại rất hạn chế trong những lĩnh vực đòi hỏi sự tiếp xúc với thế giới bên ngoài, với tín hiệu (signal), với số liệu (data). Zadeh, với những kinh nghiệm nghiên cứu về signal và systems từ những năm 1950 đã nhận ra hạn chế của logic từ lâu. Nhưng trong hơn 3 thập niên từ những năm 1960 cho đến hết những năm thập niên 80, giới nghiên cứu TTNT ở Mỹ chịu sự thống trị của trường phái của McCarthy, Simon hay Newell, và những thế hệ học trò của ông.

Ngày nay, người ta nhận ra rằng để giúp cho computers có những khả năng để vượt qua được thử thách của Turing, có lẽ cần cả ngôn ngữ logic và ngôn ngữ xác suất. (Và cả fuzzy logic nữa, nếu bạn không sống ở xứ sở của bánh mì kẹp thịt McDonald). Có rất nhiều thành tựu vượt bậc trong việc phát triển các thuật toán và hardware về chơi cờ, nhận dạng, xử lý âm thanh, hình ảnh, hay ngôn ngữ. Nhưng chúng ta sẽ đạt được TTNT hay không? Đâu là những cơ chế nền móng nhất để có thể tạo ra được một cái gọi là TTNT? Đâu là ngôn ngữ thống nhất của một hệ thống có TTNT? Những hiểu biết của chúng ta về computation, logic và probability có đủ không, hay chúng ta phải cần cả sự trợ giúp của cả neuroscientists, molecular biologists, và physicists nữa? Hay chúng ta nên định nghĩa lại khái niệm TTNT, với sự trợ giúp của những nhà triết học? Hay chúng ta cứ khai triển thêm trên cơ sở thử thách của Turing, để xây dựng máy tính có thể vượt qua những thử thách chông gai đó trước đã?

Có quá nhiều câu hỏi mà hình như ngày nay, chúng ta vẫn không biết hơn là bao so với Turing của những năm 50 của thế kỷ trước. Để có thể tiến tới gần những câu trả lời, ngành KHMT chắc chắn phải cần thêm nhiều nhà khoa học tiên phong và độc đáo như Lofti Zadeh.

Fuzzy logic của Zadeh thực ra không bị lãng quên đến mức như vậy. Mọi sinh viên học máy tính hay tóan ở những năm cuối của ĐH tổng hợp (not technical univ) ở Châu Âu (eg. Đức, Ba Lan, Finland, etc.)trong 1-2 kỳ năm 4 hoặc thứ 5 khi học về các lọai non-standard logics đều được học về Fuzzy logics. Dĩ nhiên nó chỉ là 1 trong nhiều models nên ng ta không dành cho nó nhiều thời gian được. Vả lại trong đó có mấy định lý hay ho đâu mà dạy? Có 2 lý do mà dân Tóan không thích Fuzzy logic. Thứ nhất là dân Tóan ghét every non-boolean logics vì chấp nhận nó đồng thời phải xây dựng lại nền tảng của Tóan và xd lại phần lớn các lý thuyết và định lý. Đây là 1 việc khổng lồ và gần như không tưởng cho nhân lọai. Có thể đếm trên đầu ngón tay những lý thuyết Tóan đã được xây dựng lại trên cơ sở khác với logic cổ điển. Thứ hai là nó không có giá trị gì lớn đối với Tóan cả. Ý định mở rộng lý thuyết tập hợp (fuzzy set) của Zadeh không thành công về mặt Tóan, cái fuzzy set định nghĩa được = lý thuyết tập hợp 1 cách dễ dàng. Nếu vậy thì không thể là nền tảng được. Còn bọn làm xác suất ghét fuzzy *** bời vì bản thân xác suất chính là fuzzy set rồi, bọn nó không coi là có dạng uncertainty nào khác. Còn các kiểu fuzzy sets khác thì phần lớn là vô nghĩa, phải vứt bỏ theo bọn probabilists. Nói cách khác dạng possibility math theory là quá rộng và không cần thiết. Trên thực tế thì tòan bộ Vật lý lượng tử được xây dựng nhờ 1 dạng fuzzy là xác suất, còn fuzzy *** mà không phải xác suất thì chắc 0 có chỗ đứng trong tự nhiên, just speculation, nhưng có thể dùng vào 1 số việc hữu ích khác 🙂 Bọn Tóan thì ghét không những vì non-boolean mà cả cái hàm “degree” trong fuzzy không là additive measure. Còn chuyện dùng fuzzy logic trong các electronic programable devices thì vì nó khá tiện lợi, ng ta đã dùng nó từ lâu lắm rồi, như trong ABS của xe hơi (80’s), diều hòa nhiệt độ, máy giặt, Lifts (elevators), refrigators, cameras, controllers, etc. Ví dụ việc hữu ích của fuzzy ***(logic,set,messure)có thể nhìn thấy ngay (obviously) trong việc chuẩn đóan bệnh trong Y khoa dựa trên quan sát các symptoms (expert systems).

Nói thêm là 1 giáo sư lớn cần phải biết cho ra lò những học trò lớn, nếu không thì ý tưởng sẽ chết – thường nhiều năm sau ai đó lại rediscover nó. Fuzzy concept ra đời 40 năm rồi, nhưng phát triển về mặt Tóan học lèo tèo chảng có gì. Tầm vóc của possibility “theory” sẽ khác hẳn nếu có ng develop nó thành theory thực sự với những định lý lớn, tương tự hoặc khác hẳn của probability theory. Lúc đó mới có thể nói đến alternative one, cạnh tranh với probability, vốn có nền tảng Tóan vững chăc hơn 70 năm rồi.
Còn vai trò của fuzzy logic đối với AI sau 20 năm nữa thì tôi chưa dám bàn, dù nhiều ng cho đây là ngõ cụt, tôi vẫn tin là là ảnh hưởng của nó sẽ gia tăng.

Implementation of AI Platforms to create competitive advantages for enterprises

Implementation of AI Platforms to create competitive advantages for enterprises

To be updated

Dr. Le Hong Viet – FPT Corporation (Vietnam)

Mr. Le Hong Viet was appointed Chief Technology Officer (CTO) and President of FPT Technology Council in November, 2015. With a strong technical background and hands-on experience working abroad in designing and developing complex IT systems with leading enterprises, his vision is to enhance FPT technology capability; bring good surprise to align with customer values and create FPT’s technology eco-system.

Reinforcement learning for mobile robots

Reinforcement learning for mobile robots

Deep Reinforcement Learning have proven robustness in many areas such as robotics, games. In Deep Reinforcement Learning, neural networks have strong ability to deal with high dimensional data, a good mean to learn features and functional approximation while reinforcement learning can make a system learn itself for a new goal and in a new environment.
From success of deep reinforcement learning, we are motivated to investigate methods that enable unmanned vehicle remember environment, identify location of target objects and navigate themselves to the target.
In the presentation, we briefly review notion of reinforcement learning and how deep learning enhance the success of reinforcement learning recent years. Some related research and toolboxes also will be introduced. Lastly, we will discuss challenges and some achievement in our research project.

Dr. Nguyen Do Van – Vietnam National University (Vietnam)

Dr. Nguyen Do Van received B.Eng. degree in Information Technology from Le Quy Don University in 2004 with honor, M.Eng and PhD degree in 2011 and 2014 respectively, in Information Science and Control Engineering from Nagaoka University of Technology, Japan.
He currently is a researcher at Institute of Information Technology, MIST. He also is an adjunct lecturer at Faculty of Information Technology, University of Engineering and Technology, Vietnam National University, Hanoi.
His research interest includes Machine Learning (Deep Learning, Reinforcement Learning), Data Mining (Statistical Model, Big Data), Intelligent Systems and Robotics. He is now advising an industrial project on Graph representation learning for social network mining and leading a research project on Deep reinforcement learning for intelligent mobile robots.
Dr. Van is member of the Institute of Electrical and Electronics Engineers (IEEE), International Rough Set Society (IRSS) and The Vietnamese Association for Pattern Recognition (VAPR). He was the recipient of Vietnam Intelligence Award in 2003 and AIAI Best Paper Adward in 2015.

Applied AI for predicting the quality of irrigation services in the Red river delta

Applied AI for predicting the quality of irrigation services in the Red river delta

To predict the satisfaction of users who use the water services is very important for the fee exemption policy to water and agriculture services. This policy has positive impacts on the water exploited and management enterprises, the national budget and social security. In this talk, some machine learning models are presented to predict the satisfaction of users related to the quality of irrigation service in the red river delta. Experimental results showed that the non-linear machine learning models achieve lower regression errors than linear models, these linear models are commonly used by irrigation experts. The diversity and feasibility of these machine learning models can be applied for dealing with economic problems in the domain of water resource management.

Dr. Nguyen Thanh Tung – Thuyloi University (Vietnam)

Tung Nguyen received his BS and MSc. degree in Information Technology from Vietnam National University (Hanoi) and a PhD. in Computer Applied Technology from Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, China. He has worked as a lecturer, researcher, consultant positions related to data management and mining for more than 20 years. He has been a visiting researcher at Vietnam Institute for Advanced Study in Mathematics (VIASM), big data institute-Shenzhen University in China (2015), Machine learning and Robot Lab, Department of Computer Science, SUSTech and Center for Automata Processing, Department of Computer Science, University of Virginia.
His current research interests include Artificial intelligence, Machine learning and Data mining, especially advanced machine learning methods for the problems of classification; statistical learning, regression ensemble methods for high-dimensional data. He has published around 20 papers in international journals and conference proceedings in these areas.