Bayesian hay frequentist?
Ngô Quang Hưng | 02 tháng 04, 2007 | 
Bản để in
Vài bài về cuộc tranh luận Bayesian chọi frequentist:
- Bài phát biểu của giáo sư Bradley Efron, giáo chủ đời 99 của thống kê thần giáo Hoa Kỳ (ASA) trong đại hội giáo dân 2005.
- Một bài nữa của Roderick Little, có rất nhiều tham khảo đến lịch sử và tài liệu của cả hai phe.
Bài của Efron có một đoạn rất hay:
A cartoon history of western thought might recognize three eras: an unpredictable pre-scientific world ruled by willful gods and magic; the precise clockwork universe of Newton and Laplace; and the modern scientific perspective of an understandable world, but one where predictability is tempered by a heavy dose of randomness. Deterministic Newtonian science is majestic, and the basis of modern science too, but a few hundred years of it pretty much exhausted nature’s storehouse of precisely predictable events. Subjects like biology, medicine, and economics require a more flexible scientific world view, the kind we statisticians are trained to understand.
Suy nghĩ cho kỹ, tôi thấy tiến trình phát triển tư duy của mình cũng hao hao cái cartoon history này. Hồi mới bắt đầu đi học, các lý thuyết, định lý như từ trên trời rơi xuống, như “ảo thuật” của các thượng đế tối cao Karp, Cook, Turing, … Sau đó đến classical complexity theory, theory of computation, deterministic algorithms, toán cổ điển … là vũ trụ chính xác của Newton và Laplace. Cuối cùng, khi đối chọi với nhiều vấn đề thực tế như phân tích dữ liệu mạng, bảo mật và mật mã hóa, và cả lý thuyết đương đại như thuật toán xấp xỉ, expanding graphs, định lý PCP và các lớp BPP, ZPP, vân vân, tôi đến với thế giới của các probability distributions, statistical learning theories, và randomness nói chung.
Efron tóm tắt hai phe như sau:
The Bayesian-Frequentist debate reflects two different attitudes to the process of doing science, both quite legitimate. Bayesian statistics is well-suited to individual researchers, or a research group, trying to use all the information at its disposal to make the quickest possible progress. In pursuing progress, Bayesians tend to be aggressive and optimistic with their modeling assumptions. Frequentist statisticians are more cautious and defensive. One definition says that a frequentist is a Bayesian trying to do well, or at least not too badly, against any possible prior distribution. The frequentist aims for universally acceptable conclusions, ones that will stand up to adversarial scrutiny.
Cuộc tranh luận về nền tảng của khoa học thống kê này có hơi hướng của cuộc tranh luận về nền tảng của toán học và logic nói riêng thời đầu thế kỷ 20. Đến hồi (tạm thời) ngã ngũ thế nào cũng có một đột phá trong ngành thống kê.
Xin lỗi, tôi không quen với cách format trong wordpress nên hôi lộn xộn.
Sẵn đây xin hỏi anh Hưng là làm thế nào để edit một cái post cũ?
Tx
@achoo: normal users chắc không edit lại comment được. Nếu cần bạn cứ cut-and-paste, post comment mới, rồi tôi xóa cái cũ đi thôi.
@Long: tôi gọi đùa là thần giáo cho “sang” thôi. Khi mà một giáo phái tranh cãi về giáo lý 250 năm ròng, một nửa tin cái này, nửa khác tin cái kia, gần đây hai phe mới có xu hướng hòa giải, thì gọi là thần giáo cũng được chứ sao :-).
@Nguyên: nếu mình đã “giả sử data thuộc vào một sample space nào đó” thì chắc không gọi là truth được.
@tvhvt and to all: nhân bạn nhắc đến ““ground truth” có nhiễu cố tình“, hiện nay tôi đang rất quan tâm đến một theoretical framework cho vấn đề “poison một learner”, theo nghĩa giống như DNS poisoning, cache poisoning trong networking. Có bác nào biết vài tham khảo tốt không?
Bác Hưng, bác nói đúng, bỏ chữ “giả sử” đi ạ.
@bác Hưng: bác định bắt chuột cống phải không ạ? Tôi mù tịt về bài toán của bác :(, nó có gì giống và khác với “active sampling, selective sampling, cryptanalysis” ạ?
@achoo & bác Long: tôi coi “learning to learn” = “transfer learning” = “multi-task learning” or “domain adaptation” = “conjoint analysis”, tôi không/chưa thấy nên đội mũ “prior” cho những trường hợp này.
Nhân achoo nhắc đến quyển “All of stats” của Wasserman, tôi có một nhận xét chủ quan, mong các cao thủ phản biện:
Các nghiên cứu lý thuyết của các bác stats hiện giờ xoay quanh các bài toán cơ bản của ML hoặc của computation, kiểu như: gán nhãn với 2 giá trị 0/1 (gồm cả crypto/crypta?), hồi quy (cổ điển, trên tập “nhãn” là toàn bộ tập số thực) hoặc là ước lượng hàm phân bố. Mối quan tâm chính của họ là khả năng, tốc độ hội tụ, active learning/selective sampling.
Còn các nghiên cứu ứng dụng (ý tôi là “miễn là bắt được chuột”, không quan tâm “hội tụ, chặn chiếc”) thì lại lo đi tìm giải thuật hiệu quả cho các bài toán ít phổ biến hơn trong statistical textbooks như ordinal regression, multi-label multi-class labeling (trường hợp các nhãn kiểu nominal, ordinal lẫn overlapped).
Đối với những bài toán chưa hề xuất hiện trong statistical textbook (kiểu như learning of retrieval functions for search engine, for collaborative filtering, …) thì liệu có hi vọng (sớm) được các bác stats/computation dốc sức nghiên cứu lý thuyết không nhỉ?
Tôi bổ sung 1 mục từ vào từ điển ML/Stats/CS:
(pool-based) selective sampling (the most popular kind of active sampling) in ML has the similar objective as (optimal) experiment(al) design in Stats/Optimization.
Nhưng theo tôi hiểu thì có 2 chi tiết hơi khác:
- về bài toán: các bác stats khi xem xét OED thì chỉ quan tâm bài toán xác định hàm hồi quy (và thường là dạng tuyến tính hoặc là logistic). Còn các bác ML/computation thì lại quan tâm chủ yếu đến bài toán gán nhãn, phân lớp.
- về cách thức lấy mẫu: OED chỉ quan tâm 1 lần chọn mẫu (batch), còn selective sampling không có giới hạn gì về số item(s) chọn ở mỗi vòng cả.
Tôi có 1 câu hỏi: có ai có nguồn tài liệu tham khảo (tốt) về trường hợp sequential selective sampling khi nhãn (hindsight groundtruth) là các overlapped labels không ạ?
@tvhvt: active sampling và selective sampling là từ góc nhìn của người bắt chuột cống, tôi thì lại muốn một theoretical framework mô tả cơ chế hoạt động và hiệu quả của con chuột. Theo một nghĩa nhất định, cái tôi muốn biết là một nửa của cryptanalysis trong ngữ cảnh của machine learning. Tôi muốn phát triển một adversarial model cho các learners.
@bác Hưng: tôi chưa hiểu rõ ý bác “active sampling, selective sampling là từ góc nhìn của người bắt chuột cống” và “một nửa của crypta” là gì
“một nửa của sự thật không còn là sự thật”, một nửa của cơ chế tương tác thì nó là gì ạ?
Tôi quan tâm đến “selective sampling” và tôi cũng cần các mô hình của “adversary”. Theo hiểu biết của tôi thì độ khó của “adversarial model” phụ thuộc vào nhiều yếu tố. Trường hợp cụ thể của tôi là 2 bài toán “selective sampling” liên quan đến hàm sắp xếp các tài liệu cho search engine từ các câu truy vấn khác:
(1) chọn được những câu truy vấn có ích cho việc học trước khi đòi hỏi editor cung cấp nhãn cho các tài liệu đối với các câu truy vấn này.
(2) chọn được những tài liệu (web page) và những câu truy vấn có ích cho việc so sánh chất lượng của nhiều hơn 2 search engines. Kết quả thực nghiệm trên bộ dữ liệu của TREC thì tôi và một vài người khác, theo các kiểu “học hành” khác nhau đã khoanh được vùng. Nhưng “lower and upper bounds of sample complexity” thì chưa ai biết là có thể sớm tìm ra không, có gì hấp dẫn đối với các bác “computation, stats” không.
Tôi bị mắc ở thang giá trị của nhãn (output) và lượng hóa khái niệm “non realizable hypothesis” (hàm/mô hình học lý tưởng (không có lỗi trên tập dữ liệu học) không rơi vào tập các hàm đang xét).
Tôi không biết bài báo này có ích gì cho bác không:
http://www.cs.berkeley.edu/~tygar/papers/Machine_Learning_Security/asiaccs06.pdf
@bác Hưng: “adversary modelling” của bác có nhằm giải quyết vấn đề xyz spam với xyz = blog, email, web, … không?
Cảm ơn tvhvt nhiều, that’s exactly the kind of papers I’m looking for. Đại khái, bài toán của tôi nằm trong ngữ cảnh packet classification, nhưng ý tưởng chính hoàn toàn có thể ứng dụng vào xyz (blog’s, web’s, email’s spams, etc.) Tuy nhiên trong ngữ cảnh packet classification thì attackers có thêm vài cách để “confuse” a learner (ví dụ như gửi packet streams qua nhiều paths khác nhau trên mạng, buộc các learners phải hợp tác với nhau), vì thế tôi nói nó không giống cryptanalysis hoàn toàn. Tôi quan tâm đến 2 vấn đề chính: (1) làm thế nào để “poison” một learner để rồi sau đó learner sẽ có very high false negative rate, (2) và tương tự như thế cho false positive rate.
Cái “adversary model” của tvhvt đề cập ở trên có vẻ khá interactive, hiện tôi muốn xem xét các model ít interactive thôi (cho dễ).
V/đ này rất thú vị. tvhvt thử tìm hiểu xem sequential analysis có áp dụng ít nhiều cho vấn đề này được không. Trong sequential analysis thì những vấn đề như bounding số lượng sample được nghiên cứu khá kỹ. Tất nhiên sẽ không applicable một cách trực tiếp ngay, tôi cảm thấy một số ý tưởng của SA sẽ hữu ích.
@bác Long: bác có thể cho tôi chỉ dẫn nguồn tài liệu tốt về “sequential analysis” được không? Cảm ơn bác trước.
@bác Hưng: kịch bản “confuse 1 learner” của bác (đi đường vòng, đòi hỏi các learners phải hợp tác với nhau) có điểm tương tự với 1 trò của spam. Theo tôi biết thì sử dụng meta-learner để ngăn chặn là một giải pháp (tôi chạy lung tung giữa 2 đối tượng?).
Tôi chưa hiểu rõ ý định “poison” của bác. Nếu bác chỉ có 2 nhãn cho mỗi packet thì bác có thể làm cho learner bị ngộ độc bằng cách làm cho bộ dữ liệu học bị lệch hẳn đi.
Tôi chưa hiểu rõ ý nhiều/ít interactives của bác
Có một literature đồ sộ về lĩnh vực này. Một số sách kinh điển: Sequential analysis của A. Wald (1947), Sequential analysis của Siegmund (1985), Optimal stopping rules của Shiryaev (1978). Có thể bắt đầu bằng survey paper sau đây:
Lai T. L. Sequential analysis: Some classical problems and new challenges. Statistica Sinica, 11, 2001, pp. 303–408.
Nếu bạn không kiếm được online thì email riêng cho tôi lấy pdf file.
Các anh ơi cho em hỏi về Rewriting System (RS) với?theo em hiểu thì đây là 1 hệ thu gọn (hệ viết lại) dựa trên 1 hệ luật (rules) xây dựng trước đó, đúng không ạ? Em có ý định xây dựng 1 RS để rút gọn 1 đa thức chẳng hạn,nhưng cái này khó vì thuật toán không hề đơn giải. Hay 1 RS để phân tích 1 số nguyên ra thừa số nguyên tố nhưng cái này lại không biết xây dựng các rule như thế nào(thuật toán phân tích ra thừa số nguyên tố thì đơn giản, nhưng xây dựng luật để phân tích thì …chẳng biết làm thế nào?) các anh cho em xin ý kiến chỉ giáo nhé!thanks.
@Giahanh: tôi không chuyên về các computer algebra systems hay symbolic computation nói chung, nhưng tôi biết rằng các thuật toán rút gọn đa thức trong các computer algebra systems đã khá phổ biến và được nghiên cứu kỹ nhiều năm nay rồi (Mathematica, Maple, Macsyma làm cái này rất hiệu quả). Vì thế, thay vì đi tìm một thuật toán cho riêng mình thì có lẽ đi đọc literature thì tốt hơn. Xem một bài báo tổng quan của Odlyzko ở trường cũ của tôi có khá nhiều references. Theo tôi hiểu thì hầu hết các thuật toán liên quan đến đa thức (đơn giản, rút gọn, …) đều áp dụng các ý tưởng từ Grobner bases. String-rewriting là một trường hợp đặc biệt của Grobner bases.
Bài toán phân tích một số nguyên ra thừa số nguyên tố (Factoring) là một bài toán mở, theo nghĩa là người ta không biết có giải thuật hiệu quả nào để giải nó, nhưng cũng không chứng minh được nó là NP-Hard. (Nếu có giải thuật hiệu quả thì hầu hết các cryptographic protocols trên Internet đi … tiêu đời.) Trong khi đó, thuật toán lừng danh của Peter Shor cho ta biết là có thể giải Factoring hiệu quả trên máy lượng tử (mô hình toán học thôi).
Cảm ơn anh Hưng về những góp ý quý báu này nhé!Phần phân tích ra thừa số nguyên tố em muốn xây dựng 1 tập luật để áp dụng cho các số nhằm mô phỏng 1 hệ suy dẫn ấy mà, nhưng lại không biết xây dựng hệ luật như thế nào?