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

stats

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

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?

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

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

lần, với số dimension

ở 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

Đị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 :-)?