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ê.
26 Comments
Chủ đề này rất hay. (Thực ra tôi cũng dự định viết một bài blog gì đó với cùng tiêu đề như trên
, nhưng cảm ơn bác đã khai mào). “Bayesian hay frequentist” không chỉ là câu hỏi cho dân làm thống kê lý thuyết, mà cũng là một câu hỏi fundamental cho dân trí tuệ nhân tạo. [[Đây chính là một trong những ví dụ trong đầu khi tôi nói đến trong một comment trước đây http://www.procul.org/blog/2007/03/19/machine-learning-hay-statistics-2/
là, nhiều vấn đề dân TTNT mơ hồ suốt một thời gian dài, thực ra đã được dân làm thống kê suy nghĩ rất thấu đáo suốt 100 năm nay.]]
Ngoài sự phân biệt về mặt triết lý và thái độ khoa học, xin chua thêm vài ý:
– một cách xuất phát: frequentists đi từ khái niệm i.i.d (identical and independent), còn bayesian đi từ khái niệm exchangeability của observed data.
– về mặt toán học: có thể xem bayesian formulation là một công cụ toán học để giải quyết một bài toán frequentist. Cụ thể là nếu ta giải một vấn đề constrained optimization. Một cách thông thường là dùng Lagrange multiplier. Bayesian formulation giả sử là ta đã biết cái multiplier đó (đó là prior information). Tất nhiên frequentist formulation có tham vọng hơn, muốn tìm ra cái multiplier đó là cái gì. Như vậy, hai formulation không nhất thiết tương đương nhau, nhưng sẽ là tưong đương nếu anh Bayesian biết được giá trị multiplier “đúng”, theo cái nhìn của anh frequentist.
– nôm na KHMT: frequentist là worst-case analysis, còn Bayesian là average case analysis. Tất nhiên cả hai đều là statistical analysis (phân tích về giá trị kỳ vọng)
– về mặt problem-solving: frequentist view rất sexy, nhưng trong nhiều vấn đề rất khó cho ta thấy được đâu là solution. Nhìn từ góc độ Bayesian tuy khiêm tốn hơn, nhưng lại cho ta thấy structure của optimal solution. Một ví dụ tiêu biểu là sequential analysis. http://www.procul.org/blog/2005/06/29/cac-bai-bao-kinh-oi%e1%bb%83n-c%e1%bb%a7a-khmt-2-walds-sequential-analysis-theory/
Ngày trước, Abraham Wald sáng tạo ra sequential likelihood ratio test (SLRT), nhưng không tài nào chứng minh được nó là optimal. Wald, cũng như phần lớn các nhà thống kê vĩ đại nhất TK 20, là một nhà frequentist. Đến năm 48 thì Wald và Wolfowitz mới chứng minh được, và kỳ thực họ phải dùng cách nhìn Bayesian. Nhưng ngày ấy mà tự nhận mình là Bayesian thì thật là scandalous, nên họ chỉ coi đó là “mathematical device” mà thôi. Arrow, Blackwell và Girsick thì không có mặc cảm ấy, họ đã sử dụng Bayesian formulation và chứng minh được tính tối ưu của SLRT một cách trọn vẹn hơn cùng vào thời điểm đó.
– về mặt application: phương pháp frequentist nói thì hay mà làm thì dở. pp này rất thích hợp cho chứng minh các đảm bảo của các giải pháp thống kê. Còn pp Bayesian thì nói dở (vì subjective!, không chứng minh gì hết), nhưng làm hay. Làm hay với sự góp mặt của công nghệ thông tin và tiến bộ thuật toán! Các vấn đề thực tế thường giải quyết tốt bằng pp Bayesian. Tất nhiên sự phân biệt này cần hiểu một cách vui vẻ, không chặt chẽ! Thường thì nếu bạn có một solution frequentist tốt thì cũng sẽ có một Bayesian solution tốt tương ứng, và ngược lại. Nhưng ý tôi muốn gút lại là ở bên trên, dùng Bayesian formulation cho ta nhìn thấy structure của optimal solution tốt hơn. Ví dụ như Bellman’s dynamic programming methods khó lòng mà ra đời nếu xuất phát điểm của nó không phải là Bayesian point of view!
– về tính cách: dân frequentist thì hay tinh vi vì họ có chứng minh lý thuyết, họ rất toán học, nhưng cứng nhắc. Họ ít khi tạo ra mô hình mới, mà chỉ xoay quanh một số mô hình có sẵn và tìm hiểu chúng càng kỹ càng càng tốt. Dân Bayesian thì thiên nhiều về tìm ra model tốt nhất (cho prior), họ lấy đó làm thú vị: Tìm ra càng nhiều mô hình càng tốt, và áp dụng cho càng nhiều loại dữ liệu càng tốt. Mỗi mô hình là một dạng statistical models/ stochastic processes. Nhưng họ không quan tâm nhiều đến việc chứng minh. (Họ chủ quan hơn!) Còn nếu chứng minh bất kỳ cái gì thì họ sẽ phải dùng pp frequentist.
– Thực ra frequentist và Bayesian không hề đối lập nhau như nhiều người nghĩ trong các vấn đề cụ thể. Chúng đan xen nhau thì đúng hơn, và khi ta giới hạn cái nhìn của ta lại một góc nào đó, thì sẽ thấy đó là cách nhìn frequentist hay cách nhìn Bayesian. Điều này có thể thấy với những ai đã suy nghĩ ít nhiều về các mô hình nhiều tầng. Nếu bạn là Bayesian, bạn sẽ dùng prior cho parameters. Prior dùng hyperparameters. Vậy cái hyperparameters này là random hay unknown? Nếu unknown thì bạn lại thành frequentist mất rồi. Nhưng nếu random thì bạn lại phải suy nghĩ xem hyper-hyper-parameters là gì, unknown hay random? Ta có thể thấy câu hỏi này không thể nào dứt.
– Thực ra Bayesian không có nghĩa là phải dùng subjective prior. Frequentists cũng dùng prior một cách ngầm. Nhưng prior của frequentists thường không tỉ mỉ như của Bayesians. Chẳng ai có thể học được từ con số không cả, phỏng a.
– Về trí tuệ nhân tạo: Đây cũng là khía cạnh tôi rất thích thú. Những agents thông minh tự học thế nào, tự tiến hóa thế nào để cải thiện với kinh nghiệm. Để có thể học và cải thiện từ kinh nghiệm, những AI agents vẫn phải có mô hình về thế giới xung quanh để giao diện với data qua các giác quan. Vấn đề là, các mô hình này được phát triển thế nào? Nếu chúng ta chấp nhận mô hình tuyến hóa của Darwin thì rất có thể mọi thứ bắt đầu từ con số không, nhưng trong quá trình tiến hóa, sự thừa hưởng về di truyền chính là một cách sử dụng prior. Nhưng khi ta nói đến nhân tạo, thì việc dùng prior designed bởi con người là rất khả dĩ. Nếu không ta không thể có prior tốt, không thể tạo ra được AI. Vậy ta hãy theo Bayesian hay frequentist? Theo tôi đây là một câu hỏi không có ý nghĩa, nếu ta nhìn nhận vấn đề mộc cách pragmatic: Nếu một vấn đề (khía cạnh) của thế giới quan đã được chúng ta hiểu tốt, thì nên dùng Bayesian prior. Còn nếu không thì hãy dùng phương pháp frequentist.
– cuộc sống: prior tốt tạo cho bạn một cái bàn đạp tốt, giống như trí thông minh bẩm sinh. Nhưng nếu không có sự rèn luyện (lấy data, update, lấy data update) thì bạn không thể có mô hình tốt về thế giới. Khi bạn đến một nơi hoàn toàn mới, thì bạn nên dùng frequentist methodology, dò dẫm mà phát triển. Còn ở Việt nam thì muốn hay không cũng phải theo Bayesian
Một câu hỏi thú vị mà statistics (đặc biệt là frequentists) nghiên cứu rất sâu là: nên dùng loss functions nào thì tốt, và thế nào thì gọi là tốt. Dịch ra cuộc sống, thì đó chính là câu hỏi sống để làm gì, và sống thế nào. Đó cũng chính là những câu hỏi căn bản nhất của TTNT. Utility functions của AI là gì? Có tồn tại một utility function tối thượng không?
– breakthrough của statistics? Tôi không cho rằng đó là sự ngã ngũ giữa bayesian và frequentist. Theo cảm nhận của tôi thì đến thời điểm này không câu hỏi không còn relevant nhiều nữa mà hai phương pháp đều song song tồn tại vì chúng không đối nghịch nhau như người ta nghĩ. Chúng là hai cái nhìn đan xen nhau khi ta giới hạn tầm nhìn của một bức tranh tổng thể.
Vậy breakthrough của statistics là gì? Lại theo cảm nhận chủ quan của tôi thì đó chính là sự kết hôn giữa statistics và computation, là sự hội tụ của statistics và KHMT, với sự góp mặt của machine learning.
Tôi cũng đã có một hành trình nho nhỏ về mặt tri thức, từ những ngày đầu học đại học cho đến giờ, bắt đầu từ những say mê khờ dại về trí tuệ nhân tạo và khmt, và tôi cảm thấy rất nhiều câu trả lời còn năm ở phía trước từ sự kết hôn ấy.
– Điều thú vị là Berkeley (của những Neyman, LeCam, Lehman), Stanford (của những Stein, Efron,…), Columbia (của Wald), v.v., chính là những thành trì của statistics cổ điển và frequentist statistics, nhưng ngày nay ngay cả những vị đầu ngành ở đây cũng không hề dogmatic về vấn đề này. Những năm đầu tôi cũng nghĩ mình là frequentist, nhưng sau vài lần đụng đầu phải một số vấn đề về sequential analysis, tôi chọn giải pháp ba phải đứng giữa
– Cho đến những năm 70 thì hầu hết các khoa statistics ở Mỹ vẫn theo frequentist school. Tuy nhiên gần đây một số khoa statistics nổi lên là trung tâm của nhiều Bayesian như CMU, Duke. Hôm rồi có dịp dinner với giáo sư James Berger ở Duke, một nhà Bayesian (tác giả của cuốn [[James Berger, Statistical decision theory and Bayesian analysis]] highly recommended cho những ai quan tâm đến pp Bayesian về mặt lý thuyết) tôi có hỏi “what’s the difference between a frequentist and a bayesian”, ông nói, đại ý: cả hai đều tốt, nhưng dân bayesian “have more fun”. Và sau đó ông kể về hành trình của mình khi bắt đầu là một sinh viên cao học về toán đến với frequentist statistics rồi bayesian statistics như thế nào. Khá thú vị.
– Xin lỗi vì comments dài quá dự định và hơi lan man. Đây quả là một trong những favorite topics của statisticians và các nhà trí tuệ nhân tạo (hopefully!) trong buổi ăn trưa, ăn tối và cả khi đi ngủ
Dĩ nhiên, là dân ngoài thống kê thần giáo, đối với tôi thì mèo trắng mèo đen gì không quan trọng miễn là bắt được chuột, nhất là khi các vấn đề của tôi có ground truth rõ ràng.
Em giống bác Hưng “mèo trắng mèo đen gì không quan trọng miễn là bắt được chuột”. Nhưng cũng rất thích hóng hớt nghe bác Long tâm sự về cái vụ Bayesian vs. Frequentist.
Đúng là frequentist school thoạt nghe thì thấy appealing hơn, nhưng theo tôi về mặt thái độ khoa học chuyện ta áp dụng Bayes hay frequentist framework không phải là một sự phản bội principle gì cả. Vấn đề chỉ là sự giả sử how much we know. Bayesian cho ta một framework để incorporate cái assumption đó, từ
rất ítkhông nhiều lắm đến rất nhiều. Trên thực tế, ta không bao giờ biết ground truth (model), mà chỉ có thể evaluate được qua một số observations (cái mà bác Hưng gọi là ground truth!).Nghe thì có vẻ là tôi ủng hộ Bayesian, nhưng kỳ thực phần lớn work của tôi cho đến giờ vẫn là theo frequentist spirit. Có work dùng Bayesian framework, nhưng bên trong thì lại là frequentist luôn
“Bayesian cho ta một framework để incorporate cái assumption đó, từ rất ít đến rất nhiều. Trên thực tế, ta không bao giờ biết ground truth (model), mà chỉ có thể evaluate được qua một số observations (cái mà bác Hưng gọi là ground truth!).”
Em nghĩ ground truth ở đây có thể hiểu là mình giả sử data thuộc vào một sample space nào đó rồi dùng các kiểu models/distributions để có prior rồi làm việc trên đó theo Bayesian. Đúng không nhỉ?
Tôi thấy người ta thường dùng ground truth theo nghĩa là có một ít data đã được labeled cẩn thận, ta dùng nó để validate model. Tôi dùng ground truth theo nghĩa rộng hơn một chút: ground truth = bắt được chuột!
Trong một số bài toán (data mining, search engines chẳng hạn) thì ground truth không rõ ràng như thế. The effectiveness of a model might be subject to interpretation.
Tôi bàn loạn mấy câu: theo tôi hiểu thì bác Nguyên và bác Hưng đang nói đến 2 đối tượng (chuột) và 2 mục đích “bắt chuột” không giống nhau:
“ground truth” theo tinh thần của bác Hưng: là theo tinh thần “1 label of each item in a test data set”. Trường hợp này gồm các bài toán như phân loại, gán nhãn, hồi quy, ước lượng hàm phân bố xác suất, etc.
“ground truth” theo tinh thần của bác Nguyên: là theo tinh thần “clustering”, mục đích là mô tả dữ liệu ko phải bằng 1 giá trị vô hướng mà là trong 1 không gian. Trường hợp này gồm các bài toán “clustering”: data compression, lọc nhiễu, outlier detection, etc.
Tôi chưa rõ bác Hưng muốn nói gì về “tính không rõ ràng của ground truth trong một số bài toán”. Tôi tạm dịch “tính không rõ ràng này” theo mấy khả năng (có vẻ phân loại này của tôi chưa hợp lý?):
- trường hợp không ai biết ground truth là gì cả (“bất khả tri”?): trường hợp bầu cử, hay nói chung là “social choice”. Trong trường hợp này “ground truth” là gì tùy vào tiêu chuẩn đánh giá sử dụng:
- trường hợp “chín người mười ý” (nhiễu ngẫu nhiên?, khách quan): do chuyển đổi thang đánh giá, do khả năng thể hiện những khái niệm hơi mờ bằng 1 giá trị cụ thể. Đây là trường hợp của “test data set” đối với “search engine”. Trường hợp sai số do dụng cụ đo, người thực hiện, thời tiết, … đối với các thí nghiệm vật lý thuộc vào nhóm này.
- “ground truth” có nhiễu cố tình: có kẻ tấn công vào quá trình tạo bộ mẫu, tạo bộ dữ liệu.
Tôi thích nhất là câu này của anh Long: “Tôi cũng đã có một hành trình nho nhỏ về mặt tri thức, từ những ngày đầu học đại học cho đến giờ, bắt đầu từ những say mê khờ dại về trí tuệ nhân tạo và khmt, và tôi cảm thấy rất nhiều câu trả lời còn năm ở phía trước từ sự kết hôn ấy.” – nghe rất là lãng mãn, ai học trí tuệ nhân tạo có vẻ như cung có “cái say mê khờ dại” này
“Khi bạn đến một nơi hoàn toàn mới, thì bạn nên dùng frequentist methodology, dò dẫm mà phát triển” – tôi nghĩ cũng không hẳn là vậy – thực ra ta nên dùng những kiến thức/kỹ năng/kinh nghiệm có trước cho ‘công cuộc khai phá’ thì tôt hơn (một dạng prior nữa rồi), cái này nôm na gọi là transfer learning !? mà transfer learning thì na ná như hierarchical bayes roi.
@achoo: Tôi nghĩ vẫn có những tình huống mà hầu như không có prior tốt.
Thêm vào danh sách các từ điển machine learning: statistics
transfer learning: hierachical models
learning to learn: learning prior
Quên không hỏi bác Hưng, tại sao lại phong cho statistics là thống kê thần giáo nhỉ. Cho tôi biết xác suất bao nhiêu phần là vui, bao nhiêu phần là thật. Và năm sau cho tôi con số update lại
Nhắc đến chuyện machine learning and statistics, Larry Wasserman o CMU, trong cuon sach “All of statistics” cũng có đoạn ngắn đề cập về sự hội tụ của machine learning va statistics:
“Statistics, data mining, and machine learning are all concerned with collecting and analyzing data. For some time, statistics research was conducted in statistics deparment while data mining and machine learning research was conducted in computer science departments. Statisticians thought that computer scientists were reinventing the while. Computer scientists thought that statistical theory didn’t apply their problems.
Things are changing. Statisticians now recognize that computer scientists are making novel contributions while computer scientists now recognize the generality of statistical theory and methodology. Clever data mining algorithms are more scable than statisticians ever thought possible. Formal statistical theory is more pervasive than computer scientists had realized…”
Nó cũng làm tôi nhớ đến bài báo của Breiman “Statistical Modeling: The Two Cultures” (http://www.cis.upenn.edu/group/datamining/ReadingGroup/papers/breiman2001.pdf)
À, Wasserman cũng có một “từ điển” nho nhỏ ve statistics va CS. Theo y toi thi cung chuan lam nhung để tôi liệt kê ra de tham khao:
Statistics CS Meaning
estimation learning using data to estimate an unknown quantity
classfication supervised learning predicting a discrete Y from X
clustering unsupervised learning putting data into groups
data training sample (X1,Y1), … (Xn,Yn)
covariates features the Xi’s
classifier hypothesis a map from covariates to outcomes
hypothesis — subset of a parameter space
confidence interval — interval that contain an unknown quantity
……..
Bayesian inference Bayesian inference statistical methods for using data to update beliefs
frequentist inference —- statistical methods with guaranteed frequency behavior
large deviation
bounds PAC learning uniform bounds on probability errors
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?