Blog Khoa Học Máy Tính » Xác suất & thống kê

Thư viện bài, chủ đề ‘Xác suất & thống kê’

Vượt định kiến bằng Lăng Ba Vi Bộ

Ngô Quang Hưng | 26 tháng 10, 2008 | Bản để in

Mục lục.

1. Hội xu ngửa
2. Từ ngữ dùng để phỉ báng, xưa và nay
3. Đập đầu vào tường mãi, một trong hai thứ sẽ vỡ
4. Đồng hồ nguyên tử ở bệnh viện phụ sản
5. Bọn cướp biển và hiện tượng ấm toàn cầu
6. Shakespeare và một triệu con khỉ
7. Khi những con giun đất hiển linh
8. Vượt định kiến bằng Lăng Ba Vi Bộ
9. Được làm vua, thua làm … chú thích

Hội xu ngửa.
Tương truyền rằng, nhà vua ở một vương quốc vĩ đại nọ rất yêu khoa học. Tên miền của vương quốc này là NN. Ông ta muốn tìm hiểu cơ động học của tiền xu vào những đêm nguyệt thực, vì đây là những đêm thiên địa dung hòa, vũ trụ tiết lộ bí mật của nó. Cứ mỗi lần nguyệt thực, ông yêu cầu mỗi người dân thảy một đồng xu xem nó sấp hay ngửa. Sau một thời gian, dân chúng cũng nhiễm tinh thần yêu chân lý của nhà vua, và họ đưa ra những mô hình dự đoán sấp ngửa. Ngưu tầm ngưu, mã tầm mã, mô hình tầm mô hình.

Hiệp hội mười đồng xu ngửa ra đời trong hoàn cảnh ấy. Mô hình dự đoán của hiệp hội này rất đơn giản: các đồng xu thảy trong một đêm nguyệt thực luôn ra mặt ngửa. Vương quốc nọ có khoảng 100 triệu dân. Hiệp hội mười đồng xu ngửa có trên dưới 100 nghìn thành viên. Họ có cả một website tên là “xungửa.còm” rất đông khách vãng lai. Tất cả các đồng xu thảy bởi 100 nghìn thành viên này trong 10 lần nguyệt thực gần đây nhất đều cho ra mặt ngửa, vị chi là 1 triệu đồng xu ngửa. Các trải nghiệm của họ hoàn toàn nhất quán với mô hình. Họ lý luận rằng xác suất mà cả một triệu đồng xu đều ngửa là một phần 2 lũy thừa một triệu. Mà 2 mũ 130 thôi đã nhiều hơn tổng số nguyên tử trên toàn vũ trụ rồi. Do đó lý thuyết của họ không thể nào sai!

Trời sinh cả Du lẫn Lượng. Song song với họ, còn có hiệp hội mười đồng xu úp, rồi điều tra census thường niên của nhà vua cho thấy còn có cả hiệp hội hiệp hội năm ngửa, năm sấp, hiệp hội sấp ngửa năm lần, hiệp hội sấp sấp ngửa ngửa sấp hai lần, và cỡ chừng 1019 hiệp hội khác. Các hiệp hội này tranh cãi nhau chí tử, sắp sửa bạo loạn đến nơi.

Ông vua nọ rất buồn, cố gắng đứng ra hòa giải. Phụng thiên thừa mệnh, hoàng đế chiếu rằng: đến 7 đêm nguyệt thực kế tiếp, tự thân vua sẽ thảy đồng xu, và hiệp hội nào đoán đúng cả 7 đồng xu sẽ là kẻ chiến thắng, hội trưởng sẽ được phong chức quốc sư, tiền tài quyền lực không bút nào tả xiết, kể cả các tay bút sừng sỏ nhất của Minh Biện (nghĩa là không sừng sỏ gì lắm). Nguyệt thực thì mỗi năm có từ 0 đến 3 lần, phải chờ đến 5 năm sau kết quả mới được công bố. Kết quả là: còn đến cả chục hiệp hội đoán đúng cả 7 đồng xu! Ông vua thấy thế buồn quá ngã vật ra chết lăn quay cù quày, ôm xuống tuyền tài cái mộng giải thích cơ động học đồng xu. Mặc dù chẳng hội nào chiếm được chức thái sư, kể từ ngày đó, các hiệp hội này danh tiếng nổi như cồn, trở thành các trường phái nghiên cứu môn cơ động học đồng xu đêm nguyệt thực mà hiện nay có rất nhiều môn đệ tử trên toàn thế giới.

Từ ngữ dùng để phỉ báng, xưa và nay.

Đó là chuyện xưa. Ngày nay, ở một quốc gia khác với tên miền VN, cũng có nhiều môn phái lớn. Chỉ hơi khác là các mặt đồng xu ở quốc gia này được in nhiều thứ hơn là sấp/ngửa:

Đồng xu	Ngửa	Sấp
1	Mũi tẹt	Mũi tẹt hơn
2	Làm cho Tuổi Trẻ	Làm cho Thanh Niên
3	Thi Đại Học được ≥ 13.5 điểm (vừa đậu!)	Thi Đại Học được < 13.5 điểm
4	Sinh ra trong gia đình khá giả	Sinh ra trong gia đình nghèo
5	Bố mẹ cho genes tốt	Bố mẹ không cho genes tốt
6	Sinh bên này vĩ tuyến 17	Sinh bên kia vĩ tuyến 17
7	Cao trên 1 mét 45	Cao dưới 1 mét 45
8	Vòng ngực trên 72cm	Vòng ngực dưới 72cm
9	Cha mẹ đặt tên là Lê Văn Kiểm	Cha mẹ đặt tên là Tăng Minh Phụng
10	…	…

Và hiệp hội mười xu ngửa trong quốc gia này có tên rất lạ là hiệp hội èo lít. Những người còn nhớ văn hóa vương quốc NN cổ xưa không thể hiểu được tại sao mười xu ngửa trong quốc gia VN lại được gọi là èo lít, chắc là cần thương hiệu mới vì sợ vi phạm tác quyền. Nhưng khác nhau chỉ về tên gọi, còn hiện tượng thì vẫn như ở NN: các hiệp hội vào In Tờ Lét phỉ nhau chí tử. Thậm chí thành viên các hiệp hội còn dùng những từ như “ngu”, “dốt”, “cộng sản”, “chống cộng Bolsa”, “hèn”, “đểu”, vân vân, để gọi nhau.

Hồi xưa ở vương quốc NN người ta hay chửi nhau: “mày là cái đồ sấp ngửa ngửa sấp sấp”.

Đập đầu vào tường mãi, một trong hai thứ sẽ vỡ.
Trong vương quốc VH, xu ngửa = nhà xuất bản nhận in bản thảo, xu sấp = nhà xuất bản từ chối in bản thảo.

Năm 1995, một phụ nữ người Anh nộp bản thảo của mình và nhận được 12 đồng xu sấp liên tục. Thay vì gia nhập hội một tá xu sấp, bà ta thử thêm xu mười ba và lần này là xu ngửa từ nhà xuất bản Bloomsbury. Đồng xu ngửa này cũng xém nữa là sấp nếu không nhờ một cô bé 8 tuổi tên Alice Newton, con gái của giám đốc Bloomsbury, đã đọc chương một và đòi bố cho xem chương hai. Tuy nhận in, một biên tập viên của Bloomsbury gợi ý rằng phụ nữ nọ nên đi tìm việc khác vì viết sách trẻ em rất ít tiền. Người phụ nữ đó tên là Joanne Rowling. Bản thảo đánh trên máy đánh chữ có tựa đề “Harry Potter và hòn đá của Triết Gia”. Đồng xu ngửa số 13 biến Rowling thành người đầu tiên trong lịch sử thế giới trở thành tỉ phú tiền đô nhờ viết sách, và là người giàu thứ 1062 trên thế giới, theo tạp chí Forbes.

Chỉ trong phạm vi sách trẻ em, bản thảo quyển And to Think That I Saw It on Mulberry Street nhận được khoảng 27, 28 đồng xu sấp. Đó là bản thảo đầu tay của Theodor Seuss Geisel, được biết nhiều hơn qua cái tên Dr. Seuss. Phần còn lại là lịch sử. Trong top 100 các sách thiếu nhi bán chạy nhất mọi thời đại, 16 quyển là của Dr. Seuss. Ông viết khoảng 60 sách thiếu nhi, bán được cỡ 220 triệu bản.

Thế nhỡ những người như Rowling và Dr. Seuss gia nhập hội mười xu sấp hơi sớm một chút thì sao?

Một tác giả Mỹ đã nhận toàn xu sấp, và tự tử chết. Mẹ ông ta đem một bản thảo đến nhà văn Walker Percy và Percy giúp đem in. Bản thảo nọ là quyển A Confederacy of Dunces. Tác giả đã chết tên là John Kennedy Toole. Năm 1981, tiểu thuyết này được có mỗi … giải Pulitzer.

Trong thế giới điện ảnh (ĐA), xu ngửa = phim có lời nhiều, xu sấp = phim lời ít. Các hội sấp ngửa tương tự như thế giới VH nhiều không kể xiết. Xem thêm A Drunkard’s Walk có nhiều ví dụ.
Các bệnh viện phụ sản có đồng hồ nguyên tử
Chiêm tinh học là một giáo phái xu ngửa có truyền thống vài nghìn năm. Các tín đồ tin rằng giờ/ngày/tháng/năm sinh và vị trí trăng sao có thể dùng để đoán vận mệnh, tính cách cá nhân và các sự kiện xã hội. Không ít nghiên cứu khoa học đã cho thấy chiêm tinh học đoán chính xác bằng với … đoán bừa, ví dụ xem mấy bài này trên tờ Nature và các tham khảo từ đó:

Shawn Carlson. “A double-blind test of astrology“. Nature, 318, 419 - 425 (05 December 1985).
John Maddox, Defending Science Against Anti-Science, Nature, 368:185, 1994.

Hoặc gần đây hơn, các nhà khoa học đã ghi lại hành trình cá nhân của 2000 người sinh trong khoảng vài phút của nhau, hồi đầu tháng 3 năm 1958, mà theo chiêm tinh học thì họ sẽ có “số phận” tương tự. Họ đánh giá khoảng 100 đặc điểm, bao gồm chỉ số IQ, nghề nghiệp, sức khỏe tinh thần, khả năng nghệ thuật, toán học, khoa học, thể thao, khả năng đọc, viết, vân vân. Đây là tất cả các đặc điểm mà chiêm tinh học khẳng định có thể “đoán” dùng hồ sơ khai sinh. Kết quả là Chiêm Tinh Học hoàn toàn sai (uniformly negative).

Tín đồ chiêm tinh học cãi: “cách nhau vài phút là làm số phận khác nhau lắm rồi“. Thế nhưng nếu bạn đi xem chiêm tinh gia đoán số phận thì họ sẽ vui lòng lấy dữ liệu ngày giờ sinh rất không chính xác mà bạn đưa ra. Bạn có bao giờ đi một cái bệnh viện phụ sản mà ở đó có đồng hồ nguyên tử, hay đồng hồ caesium chưa? Mà đồng hồ nguyên tử cũng chỉ đúng đến 1 phần 10 mũ 10 giây thôi.

Vả lại, kể cả khi có đồng hồ nguyên tử thì tính giờ sinh từ lúc nào nhỉ? Ông bố đứng bên cạnh cầm đồng hồ (nguyên tử) quả lắc, nhăm nhăm thấy bà mụ vừa lấy con mình ra là … bấm ngay à? Nếu thò cái đầu ra thì có gọi là “ra đời” chưa? Nếu phải ra ngoài hẳn thì mới tính vào giờ sinh thì những đứa bé chết trong các ca sinh khó khăn là không có “số mệnh” à? Còn những đứa bé phải mổ thì tính giờ sinh thế nào?

Lý luận như trên của tín đồ chiêm tinh thuộc về vương quốc tất cả các đồng xu hai mặt đều ngửa. Đoán kiểu nào cũng đúng, bằng chứng ngược kiểu gì cũng sai. Trong vương quốc này, hiệu ứng Forer được thấy ở khắp nơi. Năm 1948, nhà tâm lý học Bertram R. Forer đưa cho sinh viên của ông một bộ câu hỏi xác định cá tính (personality test). Sau khi các sinh viên trả lời bộ câu hỏi xong, thì mỗi sinh viên nhận được một bản “đánh giá cá tính” dựa trên các câu trả lời của bản thân sinh viên họ. Mỗi sinh viên sẽ chấm điểm bản đánh giá cá tính của bản thân mình xem đúng hay sai, điểm từ 0 (hoàn toàn sai) đến 5 (hoàn toàn đúng). Các bản đánh giá cá tinh này được các sinh viên cho điểm trung bình 4.26: rất ấn tượng!

Chỉ có một vấn đề nhỏ: Ferer đã phát cho tất cả các sinh viên cùng một bản đánh giá cá tính mà ông chép lại từ các horoscopes. Bản đánh giá cá tính này có nội dung như sau:

You have a need for other people to like and admire you, and yet you tend to be critical of yourself. While you have some personality weaknesses you are generally able to compensate for them. You have considerable unused capacity that you have not turned to your advantage. Disciplined and self-controlled on the outside, you tend to be worrisome and insecure on the inside. At times you have serious doubts as to whether you have made the right decision or done the right thing. You prefer a certain amount of change and variety and become dissatisfied when hemmed in by restrictions and limitations. You also pride yourself as an independent thinker; and do not accept others’ statements without satisfactory proof. But you have found it unwise to be too frank in revealing yourself to others. At times you are extroverted, affable, and sociable, while at other times you are introverted, wary, and reserved. Some of your aspirations tend to be rather unrealistic.

Các chiêm tinh gia là các nhà tâm lý đại tài, nhưng khả năng dự đoán tương lai của họ thì bằng với khả năng bệnh viên phụ sản Từ Dũ có đồng hồ nguyên tử trên từng giường đẻ.

Vài chục năm trước, một người Tây Ban Nha trúng sổ số độc đắc. Chuỗi số độc đắc kết thúc bằng con số 48. Rất tự hào về “thành tựu” của mình, ông ta tiết lộ bí mật: “tôi nằm mơ thấy số 7 trong 7 đêm liền, mà 7 lần 7 là 48, do đó tôi tìm mua các số kết thúc bằng 48, nhờ đó trúng độc đắc”. Ông này có thể bầu làm vua của vương quốc các đồng xu 2 mặt ngửa. Xem

Stanley Meisler, Spain lottery — Not even war stops it. Los Angeles Times, Dec 30, 1977.
Bọn cướp biển và hiện tượng ấm toàn cầu

Năm 2005, ban giáo dục tiểu ban Kansas đòi dạy Intelligent Design — một thông điệp tôn giáo giả danh khoa học — trong các trường phổ thông. Để minh họa cho tính nhố nhăng của lý luận của ban giáo dục, Bobby Henderson đã làm một cái chart so sánh tổng số cướp biển và nhiệt độ toàn cầu (xem ảnh), và sau đó thành lập đại giáo phái Quỷ Mì Ý Bay có đến vài chục triệu tín đồ (để chế diễu ban giáo dục nọ). Chúng ta sẽ bàn về giáo phái Quỷ Mì Ý Bay trong một dịp khác, điều ta cần là cái chart giảm cướp biển thì tăng nhiệt độ toàn cầu ở trên.

Một giáo phái xu ngửa có rất nhiều tín đồ có tên là Objectivism. Giáo chủ là Ayn Rand, với Alan Greenspan là một (cựu) giáo dân. Sau vụ khủng hoảng tài chính lần này, Greenspan thừa nhận:

“I made a mistake in presuming that the self-interests of organizations, specifically banks and others, were such as that they were best capable of protecting their own shareholders and their equity in the firms.”

Greenspan, 82, who relinquished leadership of the Fed just two years ago, said the collapse of the sub-prime mortgage industry — and the vast, mostly hidden trade in derivative financial instruments it spawned — exposed a “flaw” in his categorical reliance on free markets.

Khoan xét đến việc Objectivism là đúng hay sai (tín đồ của họ bảo vệ tới cùng, cho rằng Greeenspan không phải là free marketeer thật sự), trong riêng thế giới của Greenspan thì năm nay cướp biển không giảm mà quả đất vẫn ấm lên.
Shakespeare và một triệu con khỉ
Định lý vô hạn các con khỉ đại khái nói rằng, cho thật nhiều các con khỉ gõ lung tung vào các bàn phím, thì với xác suất cực gần với 1, chúng sẽ gõ được Hamlet của Shakespeare. Ta có thể chứng minh điều này bằng lý thuyết xác suất không khó khăn gì.

Trong một hội nghị năm 1996, Robert Wilensky nói:

Chúng ta từng nghe bảo rằng một triệu con khỉ ngồi ở một triệu bàn phím có thể gõ toàn bộ các tuyệt tác của Shakespeare. Bây giờ, may nhờ có Internet, ta biết rằng điều này không đúng sự thật.

Con khỉ đang gõ bài này thấy rất nhột.

Các nhà nghiên cứu tại trường đại học Plymouth ở Anh đã thí nghiệm hồi năm 2003: bỏ một máy tính vào chuồng khỉ ở vườn thú Paignton ở Tây Nam nước Anh. Bọn khỉ lấy đá đập tán loạn vào máy tính; sau đó thì tiểu tiện, đại tiện vào bàn phím, cuối cùng mới gõ một đống chữ S, và vài chữ A, J, L, M, cho ra 5 trang sản phẩm. Mike Phillips, một trong số các nhà nghiên cứu này, nói: “rõ ràng tiếng Anh không phải tiếng mẹ đẻ của khỉ“.

Gạt đùa bỡn sang một bên. Định lý khỉ thật sự nói rằng, bất kỳ cái gì — nếu tồn tại — thì dù hiếm hoi đến mấy mà có đủ người tìm thì tìm vẫn ra. Thậm chí không cần một “chiến lược” tìm kiếm gì cả. Các con khỉ chỉ gõ loạn cào cào lên thôi. Bỏ một cây kim lên bãi cát. Một người vốc 10 nắm cát bất kỳ thì khả năng tìm ra kim trong đó là không tưởng. Nhưng nếu có một triệu người, mỗi người vốc 10 nắm cát bất kỳ, thì nhiều khả năng là tìm được kim. Khi độ hiếm hoi giảm xuống (đến không hiếm hoi) thì tổng số khỉ cần thiết sẽ giảm xuống. Nếu một nửa bãi cát có kim thì chỉ cần một gã vốc một nắm cát là đủ.

Nếu một gã nào đó trong một triệu gã tìm kim bãi cát ở trên mà tìm được kim thì không phải hắn có công năng đặc dị gì. Con khỉ gõ được Hamlet thì vẫn là con khỉ. Điểm này được Taleb lập đi lập lại trong hai quyển Fooled by Randomness và Black Swan. Chỉ cần sự ngẫu nhiên, một vài mutual funds sẽ có những thời điểm lời khủng khiếp, một vài cá nhân sẽ có những thành công vượt bực (Bill Miller của Legg Mason Capital Management chẳng hạn).

Những hội sấp ngửa “sống sót” trong vương quốc NN là hoàn toàn ngẫu nhiên, có thể chứng minh được bằng lý thuyết xác suất. Điểm này tương tự như công ty đoán giá xì tốc, inc trong bài điểm sách Thiên Nga Đen phần 1, và kiểu logical fallacy như bác Khoa đã viết trong bài điểm sách Halo Effect.
Khi những con giun đất hiển linh

đủ thứ lý thuyết lăng nhăng

thấy thích thú về bức ảnh … rồi thôi

Trong một mớ hỗn mang rộng lớn, bao giờ cũng có các góc nhỏ có một trật tự nào đó. Hiện tượng này xuất hiện rất nhiều trong phương pháp xác suất, theo nghĩa của Paul Erdos, khi ta chứng minh rằng trong một không gian mẫu đủ lớn thì các local patterns sẽ tồn tại. Nhìn mãi lên mây sẽ thấy một số đám mây trông giống con rồng, con chó, con … giun đất. Không hiểu tại sao đến bây giờ người ta không viết truyền thuyết về con giun đất hiển linh.

Trong mớ hỗn mang nhân quả của hiện tượng ấm toàn cầu, cái “trật tự” cướp biển giảm làm tăng nhiệt độ quả đất không dùng để kết luận ra cái gì được hết!

Vượt định kiến bằng Lăng Ba Vi Bộ
Hội viên hội xu ngửa đã có mô hình sai vì họ khái quát hóa từ một vài “mẫu” địa phương. Nhiều định kiến xuất phát từ cùng một lỗi như thế. Ai đó gặp vài anh Việt Kiều rồi kết luận Việt Kiều ở Mỹ làm nails đánh bài. Người khác gặp vài anh du học sinh rồi kết luận du học sinh Việt Nam ở bẩn và không biết xem bóng bầu dục. Thử tưởng tượng Rowling kết luận, sau 12 lần bị từ chối, rằng Harry Potter sẽ không bao giờ được nhận xuất bản.

Những đồng xu trong vương quốc NN được ném độc lập với nhau. Trong cuộc sống chúng ta thường gặp các đồng xu xâu lại với nhau thành chuỗi bằng một sợi dây vô hình nào đó. Người Bắc có nhiều bạn bè người Bắc, Người Nam có nhiều bạn bè người Nam, họ giúp nhau thắt chặt những định kiến vùng miền. Kết quả của đồng xu kế tiếp “correlate” chặt chẽ với đồng xu trước. Gia đình ba mẹ tin vào chiêm tinh học sẽ tiêm nhiễm cho con niềm tin này. Đồng xu của em bé vừa ra đời đã có mặt nặng mặt nhẹ.

Giả sử ta có một ly nước chanh, có đường ở dưới nhưng chưa khuấy lên, thì không thể nếm nước trên bề mặt (cho dù nếm cả ngụm) để kết luận là ly nước không có đường. Đầu tiên phải khuấy nó lên. Tiếc rằng, trên thực tế thì không thể “khuấy” Việt Kiều không làm nail và Việt Kiều làm nail rồi mới làm bạn ngẫu nhiên với họ. Nhưng điều có thể làm là nếm ly nước ở nhiều chỗ: bên phải một cái, dưới đáy một cái, bên trái một cái, v.v. Phương pháp này trong lý thuyết xác suất gọi là phương pháp Monte Carlo. Nhưng làm bạn với Việt Kiều Cali, New York, Chicago, Ithaca, v.v. một cách ngẫu nhiên như thế cũng rất khó vì giới hạn Vật Lý. Có thể phần nào giải quyết tình trạng này bằng Markov Chain Monte Carlo, gọi nôm na là Lăng Ba Vi Bộ.
Được làm vua, thua làm … chú thích
Một phần không nhỏ những gì diễn ra trong cuộc sống và xã hội là kết quả của sự ngẫu nhiên (NN). Trong một miền hỗn mang to lớn, nếu nhìn vào một góc nhỏ nào đó ta có thể tìm được một trật tự nhất định. Trật tự đó chẳng có ý nghĩa gì ghê gớm.

Không thể đánh giá con người hay sự vật/việc chỉ dùng kết quả thành bại được. Sẽ là một lỗi logic cơ bản nếu bài này kết luận rằng tất cả thành bại đều do ngẫu nhiên (vì các loại ví dụ kể trên chỉ là một số đồng tiền ngửa ủng hộ luận điểm này!!!). Dĩ nhiên tài năng có ảnh hưởng đến kết quả, nhưng con người có xu hướng đánh giá thấp vai trò của sự ngẫu nhiên.

Sẽ có ít định kiến hơn nếu chúng ta hiểu ý nghĩa của xác suất, không bước trên lối mòn định sẵn mà cần “Lăng Ba Vi Bộ” tìm Thiên Nga Đen.

Nếu thi thoảng có gặp nhiều xu sấp, thì không nên gia nhập hội xu sấp ngay. Đây là lý do tại sao những người kiên trì thường thành công, thiên tài có thể “tu luyện” được. Ngược lại, Einstein cảnh báo rằng: “định nghĩa của sự điên rồ là làm một thứ lập đi lập lại mà mong đợi kết quả khác nhau“.

Cuối cùng: thế nhỡ đâu tất cả những gì nhân loại chứng kiến/đo đạc được cho đến nay đều là xu ngửa thì sao? Nhỡ đâu ba định luật Newton và sự tiến hóa sinh vật cũng là xu ngửa. Đây là vấn đề qui nạp (induction) của David Hume, vượt quá khuôn khổ bài viết. Rất hy vọng có thể quay lại đề tài này trong một bài viết tới.

Chủ đề: Giới thiệu sách & Xác suất & thống kê | Bình luận (7) »

“Học máy” từ góc nhìn của lý thuyết tính toán (4)

Ngô Quang Hưng | 18 tháng 07, 2008 | Bản để in

Trong các bài trước ta đã đề cập đến một số vấn đề không học được trong mô hình PAC và tầm quan trọng của việc biểu diễn lớp giả thuyết như thế nào. Có lẽ bài báo đầu tiên nói về tầm quan trọng của (cách biểu diễn) lớp giả thuyết là bài của Pitt và Valiant (JACM, 1988). Có không ít các bài báo tiếp đó đã chứng minh hardness của một số vấn đề học máy khác, ví dụ Blum và Rivest chứng minh rằng training một neural network với 3 nodes là NP-Hard (tương đương với phần hội của 3 halfspaces là không học được), Alekhnovich et al. ở FOCS 04 chứng minh một số các lớp hàm Bool và decision trees là không học được, V. Feldman ở STOC 06 chứng minh rằng lớp DNF không học được trong mô hình PAC kể cả khi learner có thể “hỏi” data (chứ không phải lấy ngẫu nhiên, xem thêm bài này nữa), Guruswami và Raghavendra ở FOCS 06 chứng minh rằng học halfspaces (còn gọi là perceptron, một cấu trúc cổ điển) với nhiễu là khó (ta sẽ nói về nhiễu sau), v.v. Duyệt qua STOC, FOCS,và COLT những năm gần đây sẽ thấy một vài kết quả nữa. Ngoài ra, còn có một mối liên kết giữa PAC-learning và property testing, một đề tài khá “hot” trong lý thuyết tính toán.

Chứng minh rằng học một lớp khái niệm dùng một lớp giả thuyết nào đó là bài toán khó (NP-hard chẳng hạn) không đáng ngạc nhiên (dù không dễ dàng). Thế nếu ta không giới hạn cả lớp giả thuyết nữa thì sao? Bài toán sẽ khó hơn hay dễ hơn? Một mặt, ta cho learner thêm flexibility, bài toán có vẻ “dễ” hơn. Mặt khác, không giới hạn lớp giả thuyết thì learner output cái gì bây giờ? Ta sẽ quay lại đề tài này trong một bài sau.

4. Occam’s learning và mối liên hệ giữa mô hình nhất quán và mô hình PAC, trường hợp lớp khái niệm hữu hạn

Tóm tắt lại mô hình PAC: learner muốn học khái niệm trong lớp khái niệm $\mathcal C$ bằng lớp giả thuyết $\mathcal H$ , nghĩa là learner phải đưa ra một giả thuyết $h\in \mathcal H$ bằng cách lấy mẫu theo phân bố $\mathcal D$ trên miền $\Omega$ sao cho rất gần với xác suất rất cao.

Trong đề mục này, ta chỉ xét các lớp giả thuyết hữu hạn, $\mathcal H$ có thể giống hoặc khác $\mathcal C$ . Một kết quả cổ điển của Valiant nói rằng: nếu learner đưa ra một giả thuyết nhất quán với “khá nhiều” các mẫu lấy độc lập thì đó chính là PAC learner! (Có thể không phải là efficient PAC learner, nhưng chắc chắn là PAC learner.) Cụ thể hơn:

Định lý Valiant. Nếu learner có thể đưa ra một giả thuyết $h \in \mathcal H$ nhất quán với $m \geq \frac 1 \epsilon \log\left( \frac{|\mathcal H|}{\delta} \right)$ mẫu (i.d.d.) thì giả thuyết đó sẽ thỏa điều kiện $\text{Prob}\left[ \text{err}_{\mathcal D}(h) \leq \epsilon\right] \geq 1 - \delta$ , nghĩa là learner là một PAC-learner.

Chứng minh. Gọi một giả thuyết gọi là giả thuyết tồi nếu

$\text{err}_{\mathcal D}(h) = \text{Prob}_{x \in \mathcal D}[h(\mathbf x) \neq c(\mathbf x)] > \epsilon$
Như vậy, xác suất mà một giả thuyết tồi nhất quán với

ở tất cả

mẫu độc lập nhỏ hơn $(1-\epsilon)^m$ . Do đó, xác suất mà giả thuyết learner đưa ra là giả thuyết tồi ≤ xác suất tồn tại một giả thuyết tồi trong $\mathcal H$ nhất quán với

≤ $|\mathcal H|(1-\epsilon)^m$ . Ép vế cuối cùng nhỏ hơn hoặc bằng $\delta$ là xong!

QED.

Định lý này dẫn đến một kết quả khác thường được xem như một cách giải thích về mặt toán học nguyên tắc Occam’s Razor. Đại khái, nguyên tắc này nói rằng khi có một số giả thuyết tốt như nhau cạnh tranh trong việc giải thích cái gì đó thì nên chọn giả thuyết “đơn giản” nhất. Ví dụ: nếu cơ học cổ điển đã đủ để giải thích chuyển động của các hành tinh trong hệ mặt trời thì ta không cần thòng thêm một câu “Thượng đế tạo ra hệ mặt trời” nữa. (Như Laplace nói: “tôi không cần giả thuyết đó“.) Nếu ta chọn “đơn giản” = “ngắn gọn” thì từ định lý Valiant có thể chứng minh được rằng nếu learner đưa ra một hypothesis “đủ ngắn” và nhất quán với data thì learner đó là PAC-learner. (”Đơn giản” = “ngắn gọn” là cái nhìn của lý thuyết thông tin!)

Từ định lý Valiant, có thể thiết kế một số efficient PAC-learner khá dễ dàng. Ví dụ: ta đã thiết kế một PAC learner để học Boolean conjunctions trong đề mục 3.3. Tổng số giả thuyết dạng Boolean conjuction nhiều nhất là 3^n . Dùng định lý Valiant, ta chỉ cần dùng thuật toán trong đề mục 2.1 và tìm một giả thuyết nhất quán với $\frac 1 \epsilon \log \left( \frac{3^n}{\delta} \right)$ mẫu là xong. Đây hiển nhiên vẫn là thuật toán thời gian đa thức. Tổng số mẫu ta cần thậm chí còn ít hơn tổng số mẫu cần trong thuật toán đã đưa trong đề mục 3.3.

Nếu ta giữ tổng số mẫu cố định, có thể đảo định lý Valiant lại và viết

$\text{Prob}\left[ \text{err}_{\mathcal D}(h) \leq \log\left(|\mathcal H|/\delta\right)/m \right] \geq 1 - \delta$
Có thể hiểu kết quả này nôm na là: ta càng biết nhiều về lớp giả thuyết thì càng có ít giả thuyết ( $|\mathcal H|$ giảm) và do đó lỗi của giả thuyết đưa ra càng bé, hoặc càng có nhiều data (

tăng) thì cũng thế.

5. VC-dimension và mối liên hệ giữa mô hình nhất quán và mô hình PAC, trường hợp lớp khái niệm vô hạn

Định lý Valiant xem ra có vẻ hữu dụng. Thế nhưng ta chẳng dùng nó được khi $\log(|\mathcal H)|$ lớn ơn một hàm đa thức, thậm chí vô hạn. Ví dụ 1: nếu ta muốn học lớp DNF dùng lớp DNF thì $|\mathcal H| = 2^{2^n}$ . Ví dụ 2: tổng số các axis-parallel rectangles là vô hạn, vậy mà vẫn tồn tại một efficient PAC-learner cho bài axis-parallel rectangles.

May mà ta vẫn có thể chứng minh được một định lý tương tự định lý Valiant cho trường hợp $\mathcal H$ là vô hạn, nhưng ta sẽ phải giới thiệu một khái niệm mới cực kỳ thú vị, mang tính tổ hợp, gọi là VC-dimension của một lớp các hàm số. VC-dimension, viết tắt của Vapnik-Chervonenkis dimension, được Vapnik và Chervonenkis giới thiệu trong bài báo kinh điển của họ hồi năm 1971:

V. Vapnik and A. Chervonenkis. “On the uniform convergence of relative frequencies of events to their probabilities.” Theory of Probability and its Applications, 16(2):264–280, 1971.

Bài này của Hosking, Petnault và Sudan viết tổng quan về quan hệ giữa thống kê và data mining giới thiệu khá tốt trực quan của VC-dimension. Blumer et al. ở STOC 89 là bài báo đầu tiên giới thiệu VC-dimension vào ngành COLT; các kết quả của họ là nội dung chính của đề mục này của chúng ta.

5.1. Giới thiệu trực quan về VC-dimension

VC-dimension là một số đo “độ phức tạp” hoặc “dung tích” của một lớp các hàm số. Trong ngữ cảnh của chúng ta, lớp các hàm số chính là lớp giả thuyết. VC-dimension của một lớp giả thuyết là số lớn nhất sao cho tồn tại mẫu mà với bất kỳ cách gán nhãn nào cho các mẫu này ta cũng có thể tìm được một giả thuyết nhất quán với chúng. Dĩ nhiên, nếu không tồn tại số lớn nhất này thì VC-dimension của lớp giả thuyết là vô hạn. VD-dimension cũng được định nghĩa cho cả các lớp hàm biến thực chứ không chỉ các lớp hàm trị 0, 1 như trong bài toán classification ta đang xét.

Trong ngữ cảnh của statistical learning theory thì VC-dimension là số đo “dung tích” của một tập hợp bất kỳ các statistical models. Bài này có một đoạn nói rất tốt nên tôi dịch lại ra đây:

Do khái niệm này được định nghĩa dựa trên tổng số mẫu và tính nhất quán của các models trên các mẫu, nó có thể áp dụng cho hầu như tất cả mọi loại models: tuyến tính, phi tuyến, nonparametric và tổ hợp của chúng, bao gồm mạng neural, classification & regression trees, classification & regression rules, radial basis functions, Bayesian networks, và hầu hết tất cả các họ models có thể tưởng tượng ra được. Thêm nữa, VC-dimension cũng là con số đánh giá rất tốt khả năng “khớp” dữ liệu của một lớp models, tốt hơn số tham số của models. Có các ví dụ models với 1 tham số mà có VC-dimension vô hạn, do đó khớp bất kỳ tập mẫu nào. Cũng có các models với ti tỉ tham số nhưng chỉ có VC-dimension nhỏ … Với một số họ models nhất định thì VC-dimension bằng tổng số tham số, ví dụ như các linear regression/discriminant models.

Vapnik và Chervonenkis dùng VC-dimension trong các bất đẳng thức chặn lỗi cho một lớp models cho trước. Cũng như trong PAC-learning, các chặn của họ không phụ thuộc vào phân bố của dữ liệu, phân bố nào cũng được. Bài báo của Blumer et al. áp dụng ý tưởng và vài kỹ thuật của họ vào PAC-learning.

5.2. Toán học của VC-dimension và vài thuộc tính

Lớp khái niệm $\mathcal H$ là một tập các hàm số $h: \Omega \to \{0,1\}$ . Mỗi hàm số có thể xem là một tập con của $\Omega$ : tập các phần tử của $\Omega$ được hàm số gán nhãn bằng . Với một tập mẫu $S \subseteq \Omega$ bất kỳ, định nghĩa $\Pi_{\mathcal H}(S) = \{ h \cap S : h\in\mathcal H\}$ . Như vậy $\Pi_{\mathcal H}(S)$ là tập tất cả các tập con $X \subseteq S$ sao cho tồn tại một giả thuyết “cắt” ra thành (nhãn = 1) và S-X (nhãn = 0).

Tập mẫu bị $\mathcal H$ băm nát như tương Tàu bởi $\mathcal H$ nếu $\Pi_{\mathcal H}(S)$ là tập tất cả các tập con của . Nói cách khác, bị băm nát như tương Tàu nếu, cho một tập con $X \subseteq S$ bất kỳ ta luôn tìm được một giả thuyết “cắt” ra thành (nhãn = 1) và S-X (nhãn = 0).

VC-dimension của $\mathcal H$ , ký hiệu là $\text{VC}(\mathcal H)$ là kích thước lớn nhất của một tập mẫu bị $\mathcal H$ băm nát. (Bỏ “như tương Tàu” đi cho đỡ mỏi tay.) Để hiểu rõ, bạn hãy tự giải thích một cách trực quan các khẳng định sau đây:

$\mathcal H$ là tập các nửa đường thẳng mở bên trái trên trục thực, $\text{VC}(\mathcal H) = 1$
$\mathcal H$ là tập các đoạn đóng trên trục thực, $\text{VC}(\mathcal H) = 2$
$\mathcal H$ là tập các tập nhiều nhất đoạn đóng trên trục thực, $\text{VC}(\mathcal H) = 2k$
$\mathcal H$ là tập các nửa mặt phẳng, $\text{VC}(\mathcal H) = 3$
$\mathcal H$ là tập các nửa không gian (half-spaces) của $\mathbb R^d$ , $\text{VC}(\mathcal H) = d+1$
$\mathcal H$ là tập các hình cầu của $\mathbb R^d$ , $\text{VC}(\mathcal H) = d+1$
$\mathcal H$ là tập các axis-parallel rectangles, $\text{VC}(\mathcal H) = 4$
$\mathcal H$ là tập các đa giác lồi d đỉnh trên mặt phẳng, $\text{VC}(\mathcal H) = 2d+1$
$\mathcal H$ là tập các tổ hợp logic của nhiều nhất khái niệm trong một lớp khái niệm $\mathcal C$ cho trước, nếu $\text{VC}(\mathcal C)$ hữu hạn thì $\text{VC}(\mathcal H)$ hữu hạn.
$\mathcal H$ là tập các tập các đoạn đóng trên thục thực, hoặc tập các tập mở (theo nghĩa hình topo), hoặc tập các Borel sets, thì $\text{VC}(\mathcal H) = \infty$

Bổ đề Sauer Định nghĩa $\Pi_{\mathcal H}(m) = \max\left( |\Pi_{\mathcal H}(S)| : |S| = m \right)$ . Nếu $\text{VC}(\mathcal H) = d$ thì

$\Pi_{\mathcal H}(m) \leq \Phi_d(m) = \sum_{i=0}^d \binom{m}{d} \leq \left( \frac{em}{d} \right)^d = O(m^d)$

Như vậy, bổ đề này cho ta biết nếu VC-dimension của lớp hypothesis là hữu hạn thì $|\Pi_{\mathcal H}(m)|$ sẽ bị chặn trên bởi một đa thức khi đủ lớn. Kết quả này khá phản trực quan. Chú ý rằng, nếu VC-dimension là vô hạn thì ta luôn có $|\Pi_{\mathcal H}(m)| = 2^m$ .
Chứng minh. Quy nạp theo m+d . Khi m=0 thì dĩ nhiên bổ đề đúng. Khi d=0 thì lớp hàm số $\mathcal H$ gán tất cả $\Omega$ cùng một giá trị (0 hoặc 1), do đó $|\Pi_{\mathcal H}(m)| = 1 = \Phi_0(m)$ .

Xét trường hợp tổng quát m,d>0 , một tập mẫu $S \subseteq \Omega$ bất kỳ gồm mẫu, và một phần tử $s\in S$ bất kỳ. Chú ý rằng $\Pi_{\mathcal H}(S)$ chẳng qua là một bộ các tập con của . Số thành viên trong $\Pi_{\mathcal H}(S)$ có thể tính bằng tổng của hai số hạng: một là tổng số các các tập con $h \in \Pi_{\mathcal H}(S)$ thỏa $h \subseteq S-\{s\}$ , hai là các tổng số các tập con $h \in \Pi_{\mathcal H}(S)$ sao cho $h \subseteq S-\{s\}, h \cup \{s\} \in \Pi_{\mathcal H}(S)$ .

Dùng ý tưởng trên, định nghĩa

$\mathcal H' = \{ h \in \Pi_{\mathcal H}(S) : s \notin h, h \cup \{s\} \in \Pi_{\mathcal H}(S) \}$
Ta có $|\Pi_{\mathcal H}(S)| = |\Pi_{\mathcal H}(S-\{s\})| + |\mathcal H'| = |\Pi_{\mathcal H}(S-\{s\})| + |\Pi_{\mathcal H'}(S)|$ . Dễ thấy rằng $\text{VC}(\mathcal H') \leq d-1$ vì nếu $\mathcal H'$ băm nát một tập

nào đó thì $\mathcal H$ sẽ băm nát $X \cup \{s\}$ . Áp dụng giả thuyết quy nạp, ta kết luận:
$|\Pi_{\mathcal H}(S)| \leq \Phi_d(m-1) + \Phi_{d-1}(m) = \Phi_d(m)$

QED.

(Xem thêm bài này tôi chứng minh bổ đề Sauer bằng cách khác, có lẽ “sạch sẽ” hơn chứng minh trên.)

5.3. Định lý Valiant cho các lớp khái niệm vô hạn (nhưng có VC-dimension hữu hạn)

Định lý. Tồn tại một hằng số sao cho: nếu learner có thể đưa ra một giả thuyết $h \in \mathcal H$ nhất quán với $m \geq \frac{c_0}{\epsilon}\left(\log\left(\frac 1 \delta\right) + \text{VC}(\mathcal H)\log\left(\frac 1 \epsilon\right) \right)$ mẫu (i.d.d.) thì learner là một PAC-learner.

Chứng minh. Đây là một định lý tuyệt vời về mặt kỹ thuật. Nó khẳng định điều tôi đã biết: cùng một cây Ramirez trong tay John Williams thì khác xa trong tay NQH.

Giống như trong định lý Valiant trường hợp lớp giả thuyết hữu hạn, ta chỉ cần chặn trên xác suất sự kiện “tồi” sau đây xảy ra:

: sự kiện tồn tại một giả thuyết tồi $h \in \mathcal H$ nhất quán với (Nhớ rằng giả thuyết tồi là giả thuyết có lỗi $> \epsilon$ .)

Thay vì chặn xác suất xảy ra, ta sẽ chặn nó bằng xác suất một sự kiện khác dễ “nắm bắt” hơn. Với một tập mẫu bất kỳ, gọi M(h,S) là tổng điểm trong mà $h \neq c$ . Bây giờ, gọi $S = \mathbf x_1, \dots, \mathbf x_m$ là training set. Giả sử ta lấy thêm mẫu nữa $S' = \mathbf x'_1, \dots, \mathbf x'_m$ (đây chỉ là công cụ phân tích, không phải ta lấy thêm mẫu thật sự khi chạy thuật toán). Định nghĩa một sự kiện thứ hai:

: sự kiện tồn tại một giả thuyết $h \in \mathcal H$ sao cho M(h,S)=0 (nghĩa là vẫn nhất quán với trên ) nhưng $M(h,S') > m\epsilon/2$ .

Dễ chứng minh rằng, nếu $m>8/\epsilon$ thì $\text{Prob}[C | B] \geq 1/2$ dùng bất đẳng thức Markov, và do đó $\text{Prob}[B] \leq 2\text{Prob}[C]$ .

Giả sử ta thảy đồng tiền xấp ngửa với xác suất 1/2 và tráo $\mathbf x_i$ với $\mathbf x'_i$ nếu đồng tiền thứ là ngửa. Gọi hai tập mẫu kết quả là và . Định nghĩa một sự kiện thứ ba:

: sự kiện tồn tại một giả thuyết $h \in \mathcal H$ sao cho M(h,T)=0 (nghĩa là vẫn nhất quán với trên ) nhưng $M(h,T') > m\epsilon/2$ .

Do tính i.i.d. của và , dễ thấy rằng và có xác suất bằng nhau. Cố định và và xét một giả thuyết bất kỳ. Để cho M(h,T)=0 và $M(h,T')>m\epsilon/2$ thì phải có ít nhất $r>m\epsilon/2$ chỉ số sao cho $h(\mathbf x_i) \neq h(\mathbf x'_i)$ , và ít nhất đồng tiền ra xấp/ngửa sao cho phần đúng nhảy vào và phần sai nhảy vào . Do đó

$\text{Prob}[M(h,T)=0, M(h,T')>m\epsilon/2 \ | \ S, S'] \leq 2^{-r} \leq 2^{-m\epsilon/2}$
Thay $\text{Prob}[D]$ bằng
$E_{S,S'}\left( \text{Prob}[\exists h \in \mathcal H, M(h,T)=0, M(h,T') > m \epsilon / 2 \ | \ S, S'] \right)$
Sau đó, ta có thể thay $\mathcal H$ bằng $\Pi_{\mathcal H}(S \cup S')$ và suy ra $\text{Prob}[D]$ bằng với
$E_{S,S'}\left( \text{Prob}[\exists h \in \Pi_{\mathcal H}(S \cup S'), M(h,T)=0, M(h,T')>m\epsilon/2 \ | \ S, S'] \right)$
Áp dụng union bound cho ta
$\text{Prob}[D] \leq |\Pi_{\mathcal H}(S \cup S')| 2^{-m\epsilon/2}$
Với sự giúp đỡ của bổ đề trong mục trước, phần còn lại chỉ là cơ bắp.

QED.

6. Một chặn dưới cho độ phức tạp mẫu.

Trong các đề mục 4 và 5, chúng ta đã thấy các điều kiện đủ để learner là PAC-learner: chỉ cần lấy đủ số mẫu và (nếu có thể) đưa ra một giả thuyết nhất quán với các mẫu này. Có hai câu hỏi tự nhiên: (1) nếu không thể đưa ra một giả thiết nhất quán với mẫu thì sao? (Vì nhiều lý do, trên thực tế khả năng này hoàn toàn có thể xảy ra. Chúng ta sẽ quay lại với nó trong bài tới.) và (2) tổng số mẫu cần thiết là bao nhiêu? Định lý dưới đây trả lời câu hỏi số 2 này.

Định lý: tồn tại một không gian mẫu $\Omega$ , một phân bố $\mathcal D$ trên đó, và một lớp giả thuyết $\mathcal C$ với VC-dimension bằng thỏa mãn điều kiện sau đây: bất kỳ learner nào — nếu chỉ lấy mẫu — thì $\text{Prob}[ \text{err}_\mathcal D(h) > 1/8] > 1/7$ .

Như vậy, nếu chỉ lấy d/2 mẫu thì learner không thể PAC-learn lớp khái niệm trên với tham số lỗi 1/8 và tham số độ tin cậy 1/7 .

Đại khái, chứng minh định lý trên rất đơn giản: xét một tập con của $\Omega$ bị băm nát bởi $\mathcal C$ . Gán $\mathcal D$ là uniform distribution trên tập con này (phần ngoài tập con có density bằng không). Không mất tính tổng quát ta có thể giả sử $\mathcal C$ chính là tập tất cả các tập con của . Như vậy, mỗi mẫu trong thuộc về một nửa số khái niệm và không thuộc về một nửa số khái niệm còn lại. Giả sử ta lấy một khái niệm một cách ngẫu nhiên, và learner chỉ thấy một nửa của , thì xác suất mà learner đoán sai trong nửa còn lại sẽ ít nhất là 1/4 . Do đó, tồn tại ít nhất một khái niệm mà learner đoán sai với xác suất 1/4 . Từ đó, dùng bất đẳng thức Markov, kết thúc định lý không khó khăn gì.

Chủ đề: Lý thuyết tính toán & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (2) »

“Học máy” từ góc nhìn của lý thuyết tính toán (3)

Ngô Quang Hưng | 14 tháng 07, 2008 | Bản để in

3. Mô hình có lẽ xấp xỉ đúng (Probably Approximately Correct) (viết tắt là mô hình PAC)

Hạn chế lớn nhất của mô hình nhất quán, như đã nói, là nó không đếm xỉa gì đến khả năng dự đoán tương lai. Một hạn chế thứ hai là trên thực tế training data ta thường có được theo một phân bố xác suất (probability distribution) nào đó. Ví dụ như trong bộ lọc spam emails, tần suất xuất hiện của cùng một (loại) spam email khá là lớn (Viagara, lừa đảo Nigeria, v.v.), chứ không phải mỗi email chỉ xuất hiện một lần như ta mô tả mô hình nhất quán. Phân bố xác suất này không được nắm bắt trong mô hình nhất quán. Mô hình PAC sẽ vượt qua được hai hạn chế chính kể trên.

3.1. Về mặt trực quan, mô hình PAC nói như sau. Thuật toán ML của ta có thể lấy mẫu độc lập từ một phân bố xác suất $\mathcal D$ nào đó trên miền $\Omega$ . Mỗi mẫu đều có nhãn. Sau đó, thuật toán ML sẽ đưa ra một giả thuyết $h \in \mathcal C$ (lớp khái niêm cho trước) sao cho chúng ta rất tin rằng rất gần với khái niệm cần học .

Làm thế nào để đo xem có “gần” hay không? Định nghĩa hàm lỗi như sau:

$\text{err}_{\mathcal D}(h) = \text{Prob}_{\mathbf x \in \mathcal D}[h(\mathbf x) \neq c(\mathbf x)]$
Nói cách khác, “mức độ lỗi” của

là xác suất mà

đưa ra câu trả lời khác

. Chú ý là ta đo lỗi của

dùng cùng một phân bố xác suất mà training data được lấy mẫu. (Nôm na: bắt lỗi mà dùng khác phân bố xác suất thì giống như bạn cho tôi chỉ toàn Nigeria spam emails, rồi sau đó bắt lỗi tôi rằng tôi không biết Viagra emails cũng là spam; vậy thì … tội cho tôi quá!)

Giá trị $\text{err}_{\mathcal D}(h)$ càng nhỏ thì và càng gần nhau. Đây chính là thước đo khả năng dự đoán tương lai của thuật toán ML trong mô hình PAC. Thước đo này được tính trên toàn bộ domain $\Omega$ , nó bao gồm tất cả những examples không có trong training data set.

Làm thế nào để đo “độ tin cậy“? Chúng ta sẽ yêu cầu và rất gần với xác suất rất cao; xác suất này còn gọi là độ tin cậy vào thuật toán ML. (Độ tin cậy được đo dựa trên một phân bố có các thành tố của $\mathcal D$ và cả các bits ngẫu nhiên mà thuật toán ML của chúng ta dùng. Điểm này sẽ rõ hơn khi ta xét các ví dụ trong các bài về sau.)

Đọc tiếp toàn bài »

Chủ đề: Lý thuyết tính toán & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (9) »

“Học máy” từ góc nhìn của lý thuyết tính toán (2)

Ngô Quang Hưng | 10 tháng 07, 2008 | Bản để in

Trong bài trước ta đã định nghĩa cụ thể mô hình nhất quán. Có một vài điểm tinh tế cần nói rõ hơn.

Thứ nhất, tổng số concepts trong lớp concepts đã biết $\mathcal C$ thường là rất lớn, có thể là hàm mũ của , có thể vô hạn. Thứ hai, khi ta nói thuật toán ML cần “đưa ra” một giả thuyết $h \in \mathcal C$ thì ta đã ngầm định một cách biểu diễn nào đó. Nhớ rằng, mỗi concept là một hàm số từ $\Omega$ vào $\{0,1\}$ . Kích thước của $\Omega$ rất lớn (như tổng số emails trong bài spam classification), không thể nào biểu diễn một concept bằng một lookup table được. Tổng số các concepts có thể có là $2^{|\Omega|}$ , do đó “chặn thông tin” (information theoretic bound) cho ta biết sẽ có rất nhiều concepts cần ít nhất $\Theta(|\Omega|)$ bits để biểu diễn, không thể nhỏ hơn. (Đấy là trường hợp domain hữu hạn, nếu vô hạn thì còn tệ hơn nữa.)

Vì thế, yêu cầu “khái niệm đang học thuộc về một lớp các khái niệm cho trước” là cần thiết. Nói cách khác, lớp các khái niệm cho trước này phải “vừa vừa phải phải” thôi, phức tạp quá ai mà học cho được! Nhắc lại, ta ngầm định rằng khi nói “cho trước $\mathcal C$ ” ta cũng “cho” luôn cả một cách biểu diễn một khái niệm bất kỳ trong $\mathcal C$ . Khái niệm cần học có biểu diễn kích thước |c| .

Thứ hai, ta giả sử mỗi phần tử của $\Omega$ có thể biểu diễn bằng $\Theta(n)$ bits. Ví dụ, $\Omega$ có thể là $\mathbb R^n$ hoặc một vector gồm từ khóa trong một email.

Thứ ba, khi yêu cầu thuật toán ML chạy trong thời gian đa thức, ta muốn nói là đa thức của các tham số (tổng số examples trong training set), (kích thước một phần tử trong domain), và |c| (kích thước của biểu diễn khái niệm đang học).

Đoạn trên có lẽ là khó hiểu khi đọc lần đầu. Tôi viết xong rồi cũng không hiểu thế nào là “cho trước”?. Ta hãy xét một vài ví dụ, sau đó bạn đọc quay lại đoạn ở trên chắc là sẽ thấy dễ hiểu hơn.

Đọc tiếp toàn bài »

Chủ đề: Lý thuyết tính toán & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (1) »

“Học máy” từ góc nhìn của lý thuyết tính toán (1)

Ngô Quang Hưng | 09 tháng 07, 2008 | Bản để in

Computational Learning Theory (COLT) bắt đầu từ bài báo kinh điển của Valiant hồi 1984 trên tờ CACM. (Thế mới thấy CACM bây giờ chán, không còn thấy original research articles mấy nữa. Hy vọng là cố gắng cải tổ của Moshe Vardi mới đây sẽ làm CACM thú vị hơn, thành một tờ Science cho ngành CS). Tôi quan tâm đến COLT trong quá trình tìm hiểu xem làm thế nào để mô tả về mặt toán học khái niệm “learnability” (của máy, và có khi cả của người). Ví dụ: làm thế nào để biết/chứng minh rằng một vấn đề nào đó là không thể learn được.

Chuỗi bài này có thể xem là nhật ký của tôi trong hành trình tìm hiểu này. Góc nhìn của COLT đến vấn đề learning là góc nhìn của một nhà lý thuyết tính toán và độ phức tạp. Vì thế, COLT nhảy vào các vấn đề tractability (theo nghĩa lý thuyết tính toán), độ phức tạp không/thời gian, … của learning ngay lập tức. Đây là những vấn đề mà các cách tiếp cận khác hầu như không đề cập. Ví dụ: các quyển The Nature of Statistical Learning Theory của Vapnik hay Pattern Recognition and Machine Learning của Bishop không có chương nào nói về tractability của learning problem(s). Có cả pros lẫn cons của cách tiếp cận COLT, như chúng ta sẽ thấy trong hành trình.

Đọc tiếp toàn bài »

Chủ đề: Lý thuyết tính toán & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (3) »

Thống kê và đá phạt đền

Ngô Quang Hưng | 15 tháng 11, 2007 | Bản để in

Theo bài báo này ở Journal of Economics Psychology:

In soccer penalty kicks, goalkeepers choose their action before they can clearly observe the kick direction. An analysis of 286 penalty kicks in top leagues and championships worldwide shows that given the probability distribution of kick direction, the optimal strategy for goalkeepers is to stay in the goal’s center

Chưa chi đã thấy sai. Nếu các thủ môn đa số đều không nhảy sang trái hay sang phải, như bài gợi ý, thì phân bố hướng đá bóng sẽ không còn như cũ nữa vì bọn cầu thủ đâu có đá ngẫu nhiên theo một “kick direction distribution” nào đó. Các bác nào làm về game theory ném đá bài báo nọ đi! (Có khi lại được thêm một publication.)

Khi thủ môn đổi chiến lược theo cái posterior thì các cầu thủ sẽ đổi prior.

Chủ đề: Nghiên cứu nghiên kiếc & Xác suất & thống kê | Bình luận (2) »

Giới thiệu một số sách KHMT [2]: machine learning

Nguyễn Xuân Long | 07 tháng 10, 2007 | Bản để in

Nhân đây xin nhắc thêm là về non-combinatorial optimization thì tôi có điểm một danh sách cách đây vài năm . Còn về combinatorial optimization thì anh Hưng đã điểm qua ở bài blog trước.

Chuyển qua machine learning và statistics… Có lần một người bạn tôi hỏi David Blackwell, khi cậu ta mới chập chững vào PhD program. Rằng, có cái gì hay ho tôi nên theo đuổi trong statistics? Blackwell trả lời, nên học machine learning và nonparametric statistics. Tôi gộp cả ML và Stats vì tôi coi hai ngành này là một, dẫu về truyền thống và định hướng hiện tại thì có những sự khác biệt nhất định. Có rất nhiều sách hay trong ngành, nhưng chỉ giới thiệu một số mà tôi quen thuộc hơn cả. Như vậy còn một số sách hay mà chưa được list, xin bạn đọc bổ sung qua comments. Những quyển đánh dấu sao (*) có thể dùng làm sách nhập môn tốt. Ngoài ra, (+) cũng là những quyển sách tôi ưa thích.

Đọc tiếp toàn bài »

Chủ đề: Giới thiệu sách & Trí tuệ nhân tạo & Xác suất & thống kê | Bình luận (3) »

Thiên nga đen [2]

Ngô Quang Hưng | 01 tháng 08, 2007 | Bản để in

(viết tiếp review quyển Thiên Nga Đen, xem phần 1)

3. Confirmation Bias:

Đây là một trong những lỗi logic nhiều người phạm phải mà tôi thấy bức xúc nhất trong các lỗi logic. Do đó, tôi rất đồng cảm với Taleb về các thảo luận xung quanh lỗi confirmation bias. (Dĩ nhiên, như các phần các trong quyển sách, Taleb viết ngông nghênh và phóng đại, có khả năng làm một số bạn đọc phiền lòng.)

Confirmation bias là lỗi chỉ nhăm nhăm đi tìm bằng chứng ủng hộ một mệnh đề nào đó, rồi cho rằng mệnh đề đó đúng. Các ví dụ của Taleb đa phần nhắm “bắn” vào các ngành tài chính, kinh tế, và khoa học xã hội. Ví dụ, Taleb cho rằng thị trường tài chính về cơ bản là không dự đoán được, nhưng người ta vẫn lăng xê nhiều “thiên tài” bằng cách như sau: anh nào đầu tư lỗ lã thì bị đuổi, anh nào đầu tư có lời thì được giữ lại. Như vậy, cơ chế giữ nhân viên kiểu này nghiễm nhiên giữ lại “thiên tài”, cho dù họ chỉ may mắn đầu tư có lời. (Tôi không chuyên về tài chính nên xin dành cho các chuyên gia “bắn” lại Taleb về ví dụ này.) Taleb có một ví dụ khác tôi thấy rất hay: ai cũng kể vào resumé của mình tất cả những thành tích mà mình đã đạt được, nhằm minh chứng rằng mình khá/giỏi về một lãnh vực nào đó. Đây cũng là một dạng confirmation bias. Taleb cho rằng, nếu ta kể trong resumé những thứ mà ta không biết, hoặc đã thất bại trong lãnh vực nọ, hoặc liệt kê cả thành lẫn bại, thì có phải là thông tin chính xác hơn, và resumé ít ấn tượng hơn không.

Nhận xét: riêng về đề tài này tôi có rất nhiều ví dụ tự mình quan sát thấy hàng ngày.

Những người tin bói toán thường chỉ nhớ những gì thầy bói nói đúng, nâng ông thầy bói lên thành “thông thiên bác học”. Một số người muốn chứng minh họ có giác quan thứ sáu bằng cách phạm lỗi lầm kiểu như sau, “tôi vừa nghĩ đến anh X thì anh X gọi điện thoại”. Hừm, những khi nghĩ đến anh X mà anh X không gọi điện thoại thì ta đâu có nhớ tới sự kiện đó. Trong quyển sách best-seller Surely you’re joking Mr. Feynman, Richard Feynman có kể lại vài chuyện về cái “giác quan thứ sáu” này rất tếu. Vân Vân và vân vân.
Tôi đi đón con ở nhà trẻ, hay thấy cô giáo bế con mình! Nếu không ý thức về confirmation bias, có thể tôi đã kết luận rằng con mình buổi chiều hay quấy nên cô giáo bế, hoặc cô giáo thích con mình nên hay bế nó. Trên thực tế, cả hai kết luận đều sai, tôi chỉ chú ý khi đứa trẻ cô bế là con mình.
Từ ví dụ “resume” của Taleb, tôi nghĩ đến ví dụ sau đây. Chúng ta thường hay khen “anh X thông minh lắm”, sau đó cho nhiều bằng chứng cho thấy anh X thông minh như giành giải nhất IMO năm 19yy, có Ph.D. xuất sắc ngành zzz, vân vân. Nhưng nếu, cũng anh X nọ, ta lại đi liệt kê một danh sách những điều ngu ngốc anh ta đã làm (tôi đảm bảo là khá dài — nếu suy từ bụng tôi ra), thì mệnh đề “anh X thông minh lắm” biến thành mệnh đề rỗng. (Cần thêm quantifiers cho các mệnh đề kiểu đó!)
Về mặt kỹ thuật, nhiều quyển sách lý thuyết xác suất có nêu ra trò lừa đảo sau đây, minh họa rất tốt cho cái confirmation bias. Giả sử mỗi sáng chủ nhật, bạn nhận được một email từ công ty Đoán Giá Xì Tốc Inc. dự đoán stock của AT&T tuần tới sẽ tăng hay giảm. Email này để minh chứng là họ nói đúng, và nói với bạn rằng nếu bạn trả cho họ 100USD, họ sẽ gửi dự đoán tuần kế tiếp cho. Hơn thế nữa, công ty Đoán Giá Xì Tốc Inc. sẽ bồi hoàn toàn bộ 100USD nếu họ đoán sai. Hấp dẫn chưa?
Bạn chưa tin tưởng lắm, vì sợ họ lừa đảo gì đó. Tuần sau, bạn thấy họ đã đoán đúng tuần trước, và lại nhận được một email y chang như thế. Họ đoán đúng liên tục 7 tuần liền! À hah. Chắc công ty này (CEO tên là NQH) phải sở hữu “thiên tài” đoán giá xì tốc. Đến đây thì bạn tin sái cổ. Xác suất đoán ngẫu nhiên mà trúng 7 lần liên tục là 1/128. Rất thấp!

Công ty đó có “thiên tài” thế này. Tuần đầu tiên họ gửi email đến 128 người, một nửa số đó đoán stock tăng, một nửa đoán stock giảm. Tuần sau họ chỉ gửi email đến 64 người mà lượt email đầu đã đoán trúng! Cứ thế 7 tuần liền. Dĩ nhiên, họ không chỉ gửi ra 128 emails mà sẽ gửi 128 triệu email. Nếu chỉ 1/100 số người nhận “7 lần đoán trúng” này bị lừa, cho họ 100USD, thì họ đã kiếm được 10 triệu USD trong 7 tuần. Đơn giản chưa? Chẳng qua, bạn tin “thiên tài” của họ vì bạn chỉ có bằng chứng “confirm” cái thiên tài đó mà không biết về các bằng chứng ngược lại. Tôi rất thích ví dụ này vì nói xong ai cũng hiểu ngay ý nghĩa của lỗi “confirmation bias”.
Về mặt triết học thì Karl Popper (và phần nào, cả David Hume trước đó) đã thiết kế cả một nền tảng lý thuyết về confirmation bias và cái ông gọi là corroboration of evidence (xem quyển Logic of Scientific Discovery, và quyển Cọnjectures and Refutations). Tuy nhiên, tôi lại thích nhất tư tưởng của Popper như ông trình bày rất rõ ràng trong quyển Poverty of Historicism (bác Nguyễn Quang A đã dịch quyển này sang tiếng Việt với tựa đề “Sự khốn cùng của Chủ nghĩa lịch sử,”, tiếc rằng bản dịch này cực rối rắm, kiểu sấm Hegel). Cho dù Lakatos đã có những phê phán sắc sảo về chi tiết kỹ thuật, tôi vẫn thấy cơ sở lý luận của Popper về cơ bản là cách tốt nhất để phân biệt khoa học và ngụy khoa học, dự đoán khoa học và “rùa rắn khoa học” kiểu công ty Đoán Xì Tốc Inc.
Popper quan sát thấy rằng, rất nhiều nhánh “khoa học xã hội” (bao gồm Marx và Freud) phạm phải narrative fallacy và confirmation bias. Họ có một lý thuyết vĩ đại nào đó, sau đó “fit” các sự kiện lịch sử vào lý thuyết đó. Sự kiện lịch sử nào không fit vào lý thuyết thì được xem là “outlier”. Không có một lý thuyết khoa học xã hội nào dự đoán chính xác được cái gì. Ngoài ra, lối trình bày lý thuyết một cách mù mờ làm cho các “lý thuyết” này tưởng chừng như đoán được nhiều thứ mà thật ra cũng chỉ là “trò lừa đảo vĩ đại” theo lời Taleb. Một lỗi nữa cũng rất nghiêm trọng là khi lịch sử không “fit” vào lý thuyết nào thì các “nhà khoa học” này thay đổi lý thuyết để “fit” lịch sử.

Taleb có nhắc đến Popper vài trang, nhưng tôi thấy Taleb chưa “give full credit” cho Popper. Toàn bộ quyển sách của Taleb có thể được tóm gọn là “tư tưởng Popper qua ngôn ngữ xác suất đại chúng”.

Riêng về dự đoán thì tôi đồng ý với Popper 2 tay 2 chân. Khi nào bạn đọc một lý thuyết chính trị vĩ đại nào đó, bạn thử làm thí nghiệm sau đây trong đầu: nếu ta đem lý thuyết này dự đoán tương lai thì nó đúng được bao nhiêu phần trăm? (Nhớ đừng phạm phải lỗi confirmation bias.) Khi làm thí nghiệm này xong tôi thường thấy các lý thuyết này không ấn tượng như chiều dày của quyển sách chứa nó nữa! Popper đã có một quan sát rất chính xác, nếu chỉ chăm chăm đi tìm bằng chứng ủng hộ một mệnh đề mù mờ nào đó, thì chúng ta gần như có thể chứng minh bất kỳ điều gì!

(còn tiếp.)

Chủ đề: Giới thiệu sách & Xác suất & thống kê | Bình luận (13) »

Thiên nga đen [1]

Ngô Quang Hưng | 30 tháng 07, 2007 | Bản để in

Tôi đọc xong quyển Black Swan của Nassim Nicholas Taleb vài tuần trước. Đã định viết review ngay mà đến giờ mới “giáng bút”. Đã có một đống reviews quyển sách NY Times Best Seller này từ rất nhiều các báo chí danh tiếng. Tôi không đọc hầu hết các reviews này, tự viết bao giờ cũng thích hơn!

(Ảnh của Wikipedia.) Trước khi khám phá ra thiên nga đen tồn tại trên đời (ở Úc), người ta đã tin rằng tất cả các thiên nga đều trắng. Một sự kiện bất ngờ như thế thay đổi toàn bộ thế giới quan (về thiên nga) của nhân loại. Đây là cái theme của quyến sách.

Nhận xét chung: Taleb không có nhiều ý tưởng thật sự mới, nhưng lối trình bày provocative và các bằng chứng trải rộng nhiều nhánh tư duy cho ta một bức tranh nhiều màu sắc về đề tài này. Quyển sách hấp dẫn dù khá dài dòng văn tự, ta có cảm giác như đang ngồi nhậu với một ông chú biết nhiều nhưng … hơi xỉn và đang lè nhè dông dài. Quan trọng hơn cả, nó làm ta suy nghĩ! Đó là thành công của quyển sách.

Trong Black Swan, Taleb muốn thuyết phục chúng ta các luận điểm chính sau đây.

1. Extremistan và Mediocristan: Sự vận hành của thế giới trong một domain nào đó (lịch sử, kinh tế, tài chính, thời tiết, v.v.) thuộc về một trong hai loại: Extremistan và Mediocristan. Theo ngôn ngữ thống kê thì Extremistan chứa các fat-tail distributions, và Mediocristan chứa các loại distributions kiểu Gaussian.

Ví dụ: xét 1000 người bất kỳ đang đọc blog KHMT (wishful thinking is a virtue!). Bỗng nhiên Bill Gates ghé qua làm cho cái mean-income tăng đột biến, trong khi đó dù có Yao Ming nhắm nhé thì vẫn không làm tăng chiều cao trung bình lên mấy. Income distribution thuộc về Extremistan, còn height-distribution thuộc về Mediocristan.

Taleb đưa ra rất nhiều ví dụ để minh chứng rằng thế giới này càng lúc càng bị ảnh hưởng sâu sắc bởi các Extremistan distributions: ngày 11/9, sự phát triển đột biến của Internet, Google, vụ sụp đổ của Long-Term Capital Management, vụ sập thị trường chứng khoán năm 1987, chiến tranh, sự khám phá ra thiên nga đen ở Úc, v.v.. Đây là các distributions mà một sự kiện hiếm hoi có thể thay đổi toàn bộ cấu trúc của distribution. Do đó, khi cái sự kiện unlikely này xảy ra, hậu quả thường rất nghiêm trọng vì chúng ta tập trung “model” cái “bình thường” (với một Gaussian-like distribution nào đó mà Taleb gọi là “trò lừa đảo trí thức vĩ đại”).

Nhận xét: ý tưởng này không mới. Tôi rất ngạc nhiên là Taleb, một người đọc rất nhiều như ông thể hiện trong sách (thậm chí NP-completeness cũng được nhắc đến ở một footnote), lại không nhắc gì đến The Structure of Scientific Revolutions của Kuhn. Cái mới ở đây — và xuyên suốt quyển sách — là cách trình bày vấn đề của Taleb, và lối hành văn trịch thượng đội lối hài hước, hoặc hài hước đội lốt trịch thượng. Lúc đầu đọc thấy hơi khó chịu, nhưng đọc một chút rồi thấy têu tếu. Về mặt kỹ thuật thì GARCH, Extreme Value Theory, robust statistics là ví dụ của các phát triển kỹ thuật để giải quyết trường hợp thiên nga đen. Phỏng vấn Taleb ở đây có nhiều câu hỏi hay mà Taleb không trả lời thỏa đáng. Tờ The American Statistician cũng có các bài review trong số tháng 8, và bài trả lời của Tabeb.

2. Narrative Fallacy: đây là một lỗi logic có nguồn gốc sinh học. Taleb cho rằng (và tôi đồng ý) rằng con người có xu hướng dùng pattern recognition để “fit” các quan sát mới vào các mô hình đã có sẵn trong đầu. Báo chí, ví dụ, khi báo cáo các tin tức thường tìm cách ghép chúng vào nhau theo một trật tự nhân quả nào đó để cho dễ nhớ và dễ “make sense of the world”. Cụ thể hơn, ngay sau khi Saddam Hussein bị bắt thì Bloomberg News chạy cái tít sau đây: “U.S. Treasuries Rise; Hussein Capture May Not Curb Terrorism”, nửa tiếng sau đó thì U.S. Treasuries giảm và họ đổi ngay một cái tít khác: “U.S. Treasuries Fall; Hussein Capture Boots Allure of Risky Assets”.

Taleb đưa ra rất nhiều ví dụ kiểu này để minh họa rằng cái xu hướng “make sense of the world” của con người làm cho chúng ta có thói quen xấu nhét những cái “nhân” nhố nhăng để giải thích cái “quả” nào đó. Khi đã “fit” một cái nhân vào thì thường là ta rơi vào cái hố Mediocristan, trong khi cái ta đang quan sát có thể lại là Extremistan — cái mà Taleb cho rằng đang có xu hướng thống trị thế giới.

Nhận xét: ý tưởng này cũng không mới. Người ta đã biết về xu hướng “pattern recoginition” này của não bộ trong các nghiên cứu y sinh học từ lâu. Tôi đọc trong quyển The God Delusion và

Tầm nhìn ta thật ngắn mà đã thấy bao thứ để làm — Alan Turing

Thư viện bài, chủ đề ‘Xác suất & thống kê’