Code này làm gì?

Tham số đầu vào là một chuỗi ASCII 8-bit.

push ebp
mov ebp, esp
push ebx
mov ebx, [ebp + 8]
mov eax, ebx
_loop:
mov edx, [eax]
add eax, 4
lea ecx, [edx - 01010101h]
not edx
and ecx, edx
test ecx, 80808080h
jz _loop
test ecx, 8080h
jnz _label
shr ecx, 10h
add eax, 2
_label:
add cl, cl
sbb eax, 3
sub eax, ebx
pop ebx
leave
ret

Code ban đầu rất gọn (tìm thấy trong một mẫu virút), tôi sửa lại (và làm cho nó xấu đi) để có thể biên dịch với NASM. Câu hỏi phụ: tại sao lại viết như thế này mà không viết kiểu bình thường?

Chủ đề Chưa phân loại | 4 phản hồi »

Bún măng vịt chợ Cũ

Bữa rồi đi siêu thị, tui thấy có bán vịt đông lạnh. Thế là tui hào hứng quá, khệ nệ rinh về nhà 2 con. Chắc bà con thắc mắc: “Vịt thôi mà, có gì đâu mà hào hứng ghê dữ vậy?” Xin thưa là ở bên cái đất nước ngạo mạn này, tui hiếm khi thấy vịt bán trong siêu thị. Gà thì thôi ê hề, nhìn phát ngán, trong khi vịt năm thì mười họa mới thấy góp vui. Tui thì lại khoái ăn vịt, vì vịt có thể nấu thành nhiều món khoái khẩu của tui. Chợ người châu Á thì hay có bán vịt, cũng đông lạnh chứ không được tươi rói như ở nhà đâu, nhưng nhà tui xa chợ, mỗi lần đi phải lái xe cả tiếng đồng hồ. Bởi vậy mà khi thấy một bầy vịt đông lạnh trong siêu thị, tui mới hào hứng, rồi lùa về nhà luôn 2 con cho bõ ghét.

Đem vịt về, chưa kịp nấu gì, còn đang vứt trong tủ lạnh, thì tối hôm đó tui đã nằm mơ. Sáng ra nước dãi tui chảy đầy một bên má, chèm nhẹp thấy ớn. Tại vì tui nằm mơ thấy được đi ăn bún măng vịt ở chợ Cũ. Bún măng vịt này không bán trong quán, không bán trong sạp, mà chỉ là một gánh, đặt ở lề đường, ngay đầu mặt chợ đường Hàm Nghi. Theo nhận định của trợ lý ẩm thực cho tui, tức là cái miệng của tui, thì bún măng vịt của cái gánh này ngon nhứt thiên hạ. Ngon nhì thiên hạ dĩ nhiên là bún măng vịt được vợ tui nấu cho ăn rồi, và mặc dù có muốn nịnh vợ đến đâu đi chăng nữa, tui cũng không thể đưa bún măng vịt bả nấu lên ngôi thứ nhất để “dìm hàng” bún măng vịt chợ Cũ xuống vị trí thứ hai được.

Đọc tiếp »

Chủ đề Chưa phân loại | 6 phản hồi »

Hai tham luận “nặng ký” tại TetCon 2013

CFP của TetCon 2013 đã đi được nửa chặng đường. Tổng kết lại thì có một tin vui và một tin buồn.

Tin buồn là số lượng bài mà chúng tôi nhận được từ cộng đồng trong nước ít và chất lượng chưa cao. Đây không phải là một tin quá ngạc nhiên, bởi số lượng người làm an toàn thông tin ở Việt Nam vẫn rất ít. Chúng ta có Hiệp hội ATTT, nhưng trong đó có nhiều CISO hơn là chuyên gia kỹ thuật lành nghề. Chúng ta có giải thưởng ATTT hàng năm, nhưng giải này trao cho các CISO, chứ không phải dành cho các hacker. Đây cũng là tình trạng chung của ngành công nghệ thông tin ở Việt Nam: quá nhiều nhà quản lý và quá ít kỹ sư giỏi.

Một điểm mới trong hội thảo năm nay là sẽ có một số diễn giả người nước ngoài, trình bày bằng tiếng Anh -1-. Việc mở rộng TetCon cho các diễn giả nước ngoài vừa giúp giải quyết vấn đề thiếu bài, vừa đem đến cho TetCon những cập nhật mới nhất trong ngành an toàn thông tin trên thế giới. Dẫu vậy nếu “quốc tế hóa” TetCon quá sớm và quá nhanh, chúng tôi e rằng cộng đồng trong nước sẽ không theo kịp, dẫn dẫn đến tình trạng diễn giả nước ngoài nói những vấn đề mà người nghe không hiểu hoặc không quan tâm. Do đó chúng tôi vẫn ưu tiên cho các diễn giả người Việt với các đề tài thiết thực, gần gũi với cộng đồng trong nước. Với diễn giả nước ngoài chúng tôi hoặc là mời trực tiếp, không thông qua CFP; hoặc là “chọn mặt gửi CFP” – chỉ gửi CFP đến một nhóm nhỏ chọn lọc.

Tin vui là chúng tôi nhận được một số bài chất lượng cao từ nhóm diễn giả này, trong đó nổi bật là bài của Eduardo Vela và Bruce Dang đến từ Google và Microsoft.

Bruce Dang là lãnh đạo đội “penetration testing” tại Microsoft, chịu trách nhiệm về sự an toàn của tất cả những sản phẩm phần mềm và phần cứng mới. Trong những năm qua, anh ấy đã trình bày về kỹ thuật phân tích mã khai thác lỗi trong Microsoft Officedịch ngược mã nhân hệ điều hành và nghiên cứu về virút máy tính Stuxnet. Chuyên môn của anh là về nhân Windows và dịch ngược mã. Tại TetCon 2013, Bruce sẽ trình bày về những kỹ thuật chống khai thác lỗi (exploit mitigations) trên Windows 8. Đây là một đề tài chuyên sâu, dành cho những ai thích dịch ngược mã và khai thác lỗi. Điều thú vị là anh Bruce là người Mỹ gốc Việt, nêu rất có thể anh ấy sẽ trình bày bằng tiếng Việt ;-).

Eduardo Vela là đồng nghiệp của tôi ở Google và là chuyên gia hàng đầu thế giới về an toàn web. Ở đội của tôi anh ấy là một “go-to guy” mà nhiều người phải hỏi ý kiến khi “đụng” các vấn đề về an toàn trình duyệt (browser security) và ứng dụng web (web application security). Eduardo còn là một lập trình viên JavaScript siêu hạng và là đồng tác giả Web Application Obfuscation, cuốn sách được đánh giá là đã “đưa tấn công trình duyệt lên một tầm cao mới”. Thú thật là mỗi lần nói chuyện với Eduardo xong là tôi lại cảm thấy không an tâm duyệt web :-(. Tại TetCon 2013, Eduardo sẽ nói về những quyết định sai lầm (về mặt an toàn) khi người ta thiết kế WWW và những nỗ lực của anh ấy và đồng nghiệp để khắc phục những sai lầm đó. Tôi nghĩ đây là một đề tài vừa thiết thực vừa không quá khó nắm bắt, phù hợp với tất cả mọi người.

Ban tổ chức sẽ cập nhật thông tin mới nhất về chương trình TetCon 2013 tại đâyHạn chót để gửi bài đến TetCon 2013 là ngày 3/12/2012. Trong tuần tới chúng tôi sẽ có thông báo chính thức về thời gian, địa điểm và mở hệ thống để đăng ký tham dự.

Để tổ chức được TetCon với giá vé thấp nhưng vẫn đảm bảo được chất lượng của các tham luận, ban tổ chức rất hi vọng sẽ nhận được sự hỗ trợ về mặt tài chính của các cá nhân, doanh nghiệp, tổ chức trong và ngoài nước. Mời xem ở đây để biết thêm thông tin về quyền lợi của nhà tài trợ.

-1- Nếu điều kiện thuận lợi, ban tổ chức sẽ thuê người dịch cabin thông dịch trực tiếp những tham luận này.

Chủ đề Bảo mật và mật mã học, Thông báo | 1 phản hồi »

Các câu hỏi phỏng vấn [45]

  1. Cho hai dãy số đã sắp xếp theo thứ tự tăng dần. Mỗi dãy dài n. Cho một tham số 1 ≤ k ≤ n, thiết kế thuật toán trả về số nhỏ thứ k trong tập 2n số.
Chủ đề Thuật Toán | Tagged , | 15 phản hồi »

Bayes chọi tần suất (4): ngẫu nhiên hay không ngẫu nhiên

Các bài trước:
Bayes chọi tần suất (3): vai trò của mô hình
Bayes chọi tần suất (2): suy diễn và thuật toán
Bayes chọi tần suất (1): một chút lịch sử

4. Hiệp 1: Ngẫu nhiên hay không ngẫu nhiên

Chúng ta đã dọn xong sàn đấu để cho Bayes và tần suất có thể tranh đo.

Ta đã đồng ý với nhau được điều này: Để có thể suy diễn ra được một cơ chế chân lý \theta từ dữ liệu X thì cần phải có chất kết dính giữa dữ liệu X và tham số \theta. Chất dính này được mô tả bằng một mô hình toán học thông qua ngôn ngữ xác suất. Mô hình dùng cho ta biết cơ chế sinh dữ liệu X nếu ta đã biết quy luật \theta. Mô hình được biểu diễn dưới dạng phân bố xác suất P(X|\theta). Chú ý rằng với cách nhìn này, biến X được coi là ngẫu nhiên; dữ liệu thu thập được trong thực tế được coi là realizations (hiện sinh) của X.

Như vậy, suy diễn thống kê là một dạng bài toán ngược (inverse problem). Nếu biết X rồi, làm sao truy ra được \theta. Dẫu đã đồng ý với nhau về vai trò của mô hình xác suất P(X|\theta), ta vẫn có thể bất đồng về bản chất của \theta. Sự bất đồng căn bản nhất giữa hai trường phái là thế này:

Với trường phái Bayes, tham số \theta là một biến ngẫu nhiên lấy giá trị trong tập hợp \Theta nào đấy. Với trường phái tần suất, tham số \theta nằm trong tập hợp \Theta, mà ta có thể không biết giá trị chính xác của nó, nhưng dứt khoát rằng \theta không phải là biến ngẫu nhiên.

Suy diễn tần suất, do đó, đòi hỏi xác định giá trị đúng của \theta trên cơ sở những dữ liệu quan sát được (mẫu của X). Với suy diễn Bayes, vì \theta là ngẫu nhiên, câu hỏi xác định giá trị của \theta là vô nghĩa. Thay vào đó, ta cần phải tìm được hàm phân bố của \theta trên cơ sở dữ liệu quan sát được X.

Từ sự khác biệt căn bản này dẫn đến những cách biệt bất ngờ, đôi khi rất đáng kể, về cách chúng ta suy diễn từ dữ liệu, trong ứng dụng cụ thể và cả trong triết lý khái quát. Ta sẽ nói dần về những cách biệt này ở các bài sau.

Nếu chỉ tạm dừng ở mức độ khác nhau về mặt định nghĩa, liệu ta đã có thể kết luận được điều gì chưa? Ai đúng, ai sai? Giữa ông Bayes và ông tần suất, ai sẽ là người tôi thích, ai là người bạn sẽ khăn gói theo đuổi trong hành trình tìm ra chân lý này?

Đây cũng là một thời điểm thích hợp để phân biệt sự khác nhau căn bản giữa một vấn đề suy diễn/ học thống kê (cụ thể như bài toán phân cụm, bài toán chia lớp, hay bài toán bà lão hàng xén tung đồng xu ở đường Kim Mã mà ta đã nêu ra ở loạt bài trước), với một vấn đề toán học thuần túy.

Nói nôm na, suy diễn = suy luận + diễn giải. Phần suy luận chính là phần toán học thuần túy, chắc chắn như 1+1 = 2 vậy. Nhưng phần diễn giải là cái mà người ta cãi nhau cả ngày không hết. Bởi vì, cứ cho rằng có một phân bố sinh dữ liệu P(X|\theta) thực sự, thì chỉ có Trời mới biết chân lý \theta là ngẫu nhiên hay không ngẫu nhiên. Nêu ta đồng ý với nhau là \theta là không ngẫu nhiên, thì ta sẽ có một lý thuyết suy diễn tần suất nhất quán về mặt toán học. Nếu \theta được cho là ngẫu nhiên, thì ta lại có một lý thuyết suy diễn khác, lý thuyết suy diễn Bayes, cũng hoàn toàn nhất quán về mặt toán học. Nhưng rõ ràng là hai kết quả suy diễn của hai lý thuyết này là khác nhau:

Bà hàng xén ở đường Kim Mã, dùng lý thuyết tần suất, sau một thời gian quan sát sẽ cho bạn biết rằng: Sáng thứ hai lúc 7 giờ sáng ở trước cửa hàng tôi xác suất bị tắc đường khoảng \theta = 89%. Ngoài ra bà còn quả quyết rằng nếu quan sát thêm một thời gian nữa thì con số của bà sẽ càng chính xác. Ông bơm xe đạp cạnh đó, dùng lý thuyết Bayes, sau một thời gian quan sát sẽ cho bạn biết rằng: “Cái xác suất bị tắc đường \theta mà anh hỏi ấy, tôi cho là nó vẫn còn ngẫu nhiên lắm. Tin tôi đi, tôi ngồi chữa xe đạp ở đường này 2 năm rồi. Nhưng về mặt trung bình thì tôi tính rồi, khoảng 90%, phương sai trong khoảng 12%. Nếu anh muốn biết thêm các thông số khác về phân bố thì tôi cũng tính ra được…”

Tuy khác nhau, kết quả của hai trường phái nhiều khi vẫn có thể liên hệ được với nhau về mặt lý thuyết (toán học). Đôi khi dung hoà được với nhau, nhưng đôi khi thì lại không. Trên thực tế, kết quả suy diễn Bayes và tần suất thường đưa ra các kết quả không khác nhau là bao (khi ta cần so sánh những khái niệm có thể so sánh được, như giá trị \theta của bà hàng xén làm tần suất với giá trị trung bình của \theta của bác bơm xe làm Bayes.

Nhưng sự khác biệt của Bayes và tần suất lại dẫn đến những chú trọng khác nhau của người làm thống kê trong việc phát triển các kỹ năng suy diễn. Dân Bayes và dân theo tần suất thường có cái nhìn rất khác nhau về vai trò của dữ liệu và vai trò của tiên nghiệm, về tính chủ quan và khách quan, về vai trò mô hình và thuật toán, v.v.

Chúng ta sẽ thong thả nói về những liên hệ và những cách biệt này ở các bài tới.

Bài sau: 5. Hiệp 2: Khách quan và chủ quan

Chủ đề Toán Ứng Dụng, Trí tuệ nhân tạo, Xác suất & thống kê | 7 phản hồi »

Ở lại trường hay ra ngoài làm?

Bạn Trọng Đức (?) có câu hỏi này mà tôi không ở hoàn cảnh có thể trả lời được thoả đáng vì tôi chưa “ở lại trường” bao giờ, hy vọng các bạn khác có thể giúp:

Em chào các thầy. Tình hình là tơ lòng em đang chút rối bời thế này ạ:

Hiện em là sinh viên năm cuối. Em có dự định là sau này học cao học về CS ở bên Mỹ. Em đang phân vân sau khi tốt nghiệp vào hè năm sau thì có 2 hướng : Một là, em có nên ở lại trường không. Ở lại thì có nhiều thời gian nghiên cứu cùng thầy hướng dẫn, đi học Tiếng Anh… nhưng mà có vấn đề là chỉ làm hợp đồng nên lương ít, 3 cọc 3 đồng, chắc phải đi dạy thêm, làm thêm. Hai là ra ngoài làm lập trình cho công ty, lương chắc kha khá hơn. Em đang phân vân 2 hướng này quá, chưa biết chọn hướng nào. Mong các thầy tư vấn giùm em ạ. Em xin cám ơn.

Nếu bạn chỉ nhắm cao học thôi thì kinh nghiệm làm cho cty là một điểm nhấn cho resume. Nhưng nếu bạn muốn học PhD luôn thì việc ở lại trường có thể giúp bạn tập tành nghiên cứu, học thêm Toán, có bài báo xuất bản, dẫn đến dễ được nhận vào chương trình PhD tốt hơn.

Chủ đề Dành cho du học sinh | Tagged | 2 phản hồi »

Các câu hỏi phỏng vấn [44]

(Cập nhật 15/10: Hôm trước gõ thiếu một dòng, đã sửa lại.)

  1. Hàm tìm kiếm nhị phân sau đây bị vấn đề gì, sửa ra sao?
    bool binary_search(const vector<int>& sorted_vec, int key) {
        size_t mid, left = 0, right = sorted_vec.size()-1;
        while (left <= right) {
            mid = left + (right-left)/2;
            if (key > sorted_vec[mid])
                left = mid+1;
            else if (key < sorted_vec[mid])
                right = mid-1;
            else
                return true;
        }
        return false;
    }
    
Chủ đề C++, Thuật Toán | Tagged | 14 phản hồi »

Tấn công CRIME

Tấn công CRIME là một tấn công mới nhắm vào giao thức SSL/TLS mà anh Juliano Rizzo và tôi vừa trình bày ở hội thảo ekoparty 2012 cách đây vài ngày.

Khi nào có thời gian tôi sẽ viết một bài mô tả chi tiết, tạm thời mời xem slides ở đây. Nếu anh chị nào có thắc mắc gì thì có thể đặt câu hỏi ở trên slides hoặc ở đây cũng được.

Chủ đề Chưa phân loại | 2 phản hồi »

Độ phức tạp của bài toán định trị truy vấn

Bài trước lược khảo các khái niệm và kết quả của logic bậc nhất và định nghĩa truy vấn hội (conjunctive queries). Một cách vắn tắt, lớp các truy vấn hội là lớp các truy vấn có dạng

\displaystyle  \varphi(x_1,\dots,x_k) = \exists x_{k+1},\dots, \exists x_n R_1 \wedge R_2 \wedge \cdots \wedge R_r,

trong đó {x_1,\dots,x_k} là các biến tự do, {x_{k+1},\dots,x_n} là các biến bị giới hạn, và {R_1,\dots, R_r} là các công thức nguyên tử (atomic formula). Các truy vấn hội tương đương với các phát biểu SQL dạng select ... from ... where ... mà phần where là hội của các đẳng thức đơn giản. Một cách đơn giản khác để biểu diễn các truy vấn hội là dùng ngôn ngữ datalog: các truy vấn hội biểu diễn bằng datalog có thể viết dưới dạng

\displaystyle  q(x_1,\dots,x_k) \text{ :- } R_1(\bar A_1) \wedge \cdots \wedge R_r(\bar A_r)

trong đó các biến tự do nằm trong phần “đầu” (head) của truy vấn datalog {q}, và {R_1,\cdots,R_r} là các nguyên tử (atom) trong phần “thân” (body) của truy vấn. Đa số các truy vấn vào CSDL hiện nay là truy vấn hội, cho nên lớp các truy vấn hội là lớp các truy vấn cực kỳ quan trọng cả về mặt thực tế lẫn lý thuyết.

Đọc tiếp »

Chủ đề Cơ sở dữ liệu, Lý thuyết tính toán, Logic | Tagged , , , | Phản hồi »

TetCon 2013 – Call for Papers

Đến hẹn lại lên, hội thảo TetCon 2013 sẽ được tổ chức vào ngày 11/1/2013 tại Tp.HCM (địa điểm cụ thể sẽ được thông báo sau). Hôm nay chúng tôi bắt đầu nhận bài tham luận tại địa chỉ https://sites.google.com/a/tetcon.org/2013/cfp.

Đề tài
Tham luận có thể thuộc các chủ đề như:
* Điện toán đám mây.
* Thương mại điện tử.
* Thiết bị di động.
* Tấn công từ chối dịch vụ.
* Trình duyệt web và HTML5.
* Ứng dụng web và các khung ứng dụng.
* Phần mềm độc hại và an toàn cho người dùng cuối.
* Phòng chống và phát hiện xâm nhập.
* Theo dõi và quản trị an toàn mạng.

Chúng tôi khuyến khích những tham luận bàn về các đề tài như:
* An toàn trong sử dụng điện toán đám mây.
* Đảm bảo an toàn cho một trang ngân hàng điện tử, thanh toán điện tử hoặc website buôn bán sản phẩm.
* Lập trình an toàn trên Android hoặc iOS.
* Những tính năng mới trong HTML5 và ảnh hưởng của chúng đến sự an toàn của web
* Kiện toàn an ninh cho những khung ứng dụng quen thuộc như .NET, LAMP, Ruby On Rails, Django, v.v.
* Bài học rút ra từ những lần bị tấn công từ chối dịch vụ.
* Kiện toàn an ninh cho hệ thống mạng nội bộ doanh nghiệp.
* Kinh nghiệm xây dựng và triển khai các hệ thống phòng chống và phát hiện xâm nhập.

Nếu bạn có những kinh nghiệm thiết thực rút ra từ thực tiễn đảm bảo an toàn thông tin cho sản phẩm hoặc hệ thống thông tin của doanh nghiệp thì hãy gửi cho chúng tôi! Nếu được chấp thuận, hội đồng chuyên môn sẽ góp ý, hỗ trợ bạn hoàn thiện tham luận và bạn sẽ có tối đa 45′, bao gồm thời gian hỏi đáp, để trình bày ở hội thảo. Lưu ý chúng tôi không chấp nhận những bài quảng cáo sản phẩm hay dịch vụ.

Ngày quan trọng
* Hạn chót gửi đề tài: 3/12/2012.
* Ngày công bố chương trình: 10/12/2012.
* Ngày hội thảo: 11/1/2013.

Quyền lợi diễn giả
Nếu được chọn làm diễn giả, bạn sẽ được:
* Quà tặng của BTC.
* Nếu bạn không ở Tp.HCM, có thể chúng tôi sẽ đài thọ vé máy bay khứ hồi và khách sạn.

Chủ đề Chưa phân loại | Phản hồi »

Bayes chọi tần suất (3): vai trò của mô hình

3. Vai trò của mô hình xác suất

Chúng ta đã định nghĩa thể nào là một suy diễn thống kê (statistical inference). Ta đã nói về vai trò của thuật toán trong việc tìm kiếm ra một thống kê thích hợp cho một vấn đề suy diễn cụ thể.

Chắc hẳn bạn đã bắt đầu sốt ruột, muốn biết mặt mũi ông Bayes và ông tần suất thế nào. Để còn quyết định chọn chỗ để ngồi xem hai ông ấy tỉ thí, và chọn phe nữa.

Để hiểu được sự khác biệt đầu tiên và căn bản nhất của hai phe, ta cần nói đến một khái niệm quan trọng nữa. Đó là mô hình xác suất, và vai trò của mô hình trong suy diễn thống kê.

Giả sử bạn muốn nhờ cậy một chuyên gia thống kê, học máy nào đó. Bạn cung cấp dữ liệu X, và cần ông ta tìm ra được quy luật hay cơ chế \theta đằng sau mớ dữ liệu bùng nhùng bí ẩn ấy.

Nhà thống kê xào xáo các thủ thuật của ông ấy một hồi, rồi đưa cho bạn giải pháp T(X). Ông ấy quả quyết rằng đó chính là quy luật mà bạn được tìm kiếm. Bạn kiểm chứng T(X) với các dữ liệu mới khác và vô cùng kinh ngạc vì nhận thấy nó rất khớp vói các dữ liệu mới đó. Có vẻ như T(X) đúng là cơ chế mà bạn cần tìm. Tại sao vậy?

Xin nhấn mạnh là T(X) chỉ được tính toán trên cơ sở dữ liệu X. Không ai biết thực sự \theta là gì cả. (Chỉ có ông Trời mới biết). Để có thể tìm ra \theta từ X, ắt hẳn phải có một chất keo gì đó để gắn dữ liệu X với chân lý \theta. Nếu không có chất keo này thì không thể nào suy được ra \theta từ dữ liệu được.

Đọc tiếp »

Chủ đề Toán Ứng Dụng, Trí tuệ nhân tạo, Xác suất & thống kê | Tagged , , | 4 phản hồi »

Bayes và tần suất trong suy diễn thống kê (2): suy diễn và thuật toán

2. Suy diễn và thuật toán

Ta vẫn chưa thể đi thẳng vào câu chuyện Bayes chọi tần suất. Trước hết, cần định nghĩa thế nào là suy diễn thống kê (hay học thống kê)?

Một định nghĩa giản dị: Suy diễn thống kê là quá trình chắt lọc ra các quy luật từ dữ liệu thực tế.

Có hai đại lượng quan trọng trong suy diễn thống kê. Dữ liệu thực tế sẽ được biểu diễn bởi biến  X , còn quy luật hay cơ chế đằng sau dữ liệu quan sát được sẽ được biểu diễn bằng  \theta .  X  \theta nằm trong các không gian đã định trước, \mathcal{X}\Theta. Cụ thể hóa các không gian này rất quan trọng, nhưng ta tạm thời chưa nói nhiều về chúng.

Một suy diễn thống kê sẽ được biểu diễn bởi một ánh xạ đi từ dữ liệu đến tập hợp các quy luật có thể \Theta, X \mapsto T(X) \in \Theta . Chúng ta giả dụ rằng \theta là biểu diễn của cơ chế để sinh ra dữ liệu X. \theta là chân lý mà ta có thể không biết được chắc chắn. Nhưng thông qua T(X) ta muốn ước lượng, suy xét được \theta càng chính xác tỉ mỉ càng tốt. Vì T(X) là một hàm số áp dụng vào dữ liệu, nó còn được gọi là một thống kê.

Đọc tiếp »

Chủ đề Toán Ứng Dụng, Trí tuệ nhân tạo, Xác suất & thống kê | Tagged , , | 7 phản hồi »

Bayes và tần suất trong suy diễn thống kê (1)

1. Một chút lịch sử

Hầu như những ai có một chút liên hệ với thống kê và học máy đều đã từng nghe nói đến sự khác biệt và đối chọi giữa phương pháp Bayes và phương pháp tần suất. Những người nghiên cứu lý thuyết và ứng dụng của thống kê đều có lúc phải đối đầu với một sự lựa chọn giữa Bayes và tần suất. Bản chất của sự khác biệt này là gì?

Đây là câu chuyện rất dài và sẽ là nội dung của loạt bài này. Sự khác biệt giữa hai phương pháp Bayes và tần suất có thể được mô tả từ rất nhiều góc độ khác nhau, đi từ những cái rất cốt lõi cho đến những thứ rất râu ria. Với dân nghiên cứu thống kê và học máy, với một vấn đề cụ thể đôi khi sự lựa chọn giữa hai phương pháp suy diễn này lại dẫn đến các giải pháp khác biệt với kết quả suy diễn không thống nhất.

Bayes chọi tần suất cũng là một chủ đề thú vị lúc trà dư tửu hậu. Đôi khi với kết quả “đẫm máu”. Chuyện này có thật: Khoảng 15 năm về trước ở khoa tôi có một ông làm về phương pháp Bayes, còn ông kia chủ trương theo tần suất. Cả hai ông này rất uy tín trong ngành (ông Bayes lúc đó là trưởng khoa, còn ông tần suất đã từng làm editor cho Annals of Statistics). Thế mà trong một bữa tiệc vui vẻ của toàn khoa ở nhà riêng một đồng nghiệp, trong lúc ngà ngà nói chuyện Bayes chọi tần suất một hồi thế nào mà hai bác xông ra đánh nhau thật, làm mọi người phải xô ra ngăn.

Mặc dù phương pháp Bayes và tần suất có thể truy về Thomas Bayes (thể kỷ 18) và Pierre-Simon Laplace (thế kỷ 19), sự đối chọi của hai trường phái chỉ thực sự thành hình ở đầu thế kỷ 20, khi suy luận thống kê được xây dựng trên một nền tảng toán học tương đối chắc chắn với công của Ronald Fisher, Karl Pearson, Jerzy Neyman, De Finetti và Abraham Wald và một số nhà tiên phong khác. Trong một thời gian dài từ trước thế chiến hai, phương pháp tần suất được phát triển rất mạnh. Đến tận khoảng 15 năm trở về trước sự lựa chọn giữa Bayes và tần suất còn ảnh hưởng đến cơ hội nghề nghiệp. Tần suất thắng thế và thống trị khắp các khoa thống kê ở Mỹ, từ Berkeley, Stanford đến Harvard, Chicago. Phương pháp Bayes chỉ được nghiên cứu ở vài khoa thống kê nhỏ hơn (khi đó) như Carnegie Mellon và Duke. Thay vì sử dụng phương pháp Bayes hay tần suất, bạn sẽ được (bị) gọi là nhà thống kê Bayes hay nhà tần suất. Không có chỗ dung dưỡng cho cả hai phương pháp đối với từng người. Ở châu Âu về cơ bản tần suất cũng thống trị, nhưng có một số trường phái theo đuổi Bayes rất kiên định ở Italy và Anh.

Ngày nay sự đối chọi này bớt phần khốc liệt máu lửa hơn. Khoa học thống kê cũng bớt dần tính triết lý giáo điều mà dịch dần về tính thực dụng do phải đối đầu với các vấn đề có dữ liệu phức tạp và khổng lồ. Mèo trắng hay mèo đen đều được miễn là bắt được chuột. Phương pháp Bayes được từng bước tiếp nhận và ưa chuộng, và được dạy và học ở hầu hết các khoa thống kê. Sự phát triển và giao thoa với khoa học máy tính cũng làm thay đổi một cách bản chất về các nền tảng lý thuyết của suy diễn thống kê. Ngoài cái kiềng tần suất và Bayes, bây giờ còn có một cái kiềng nữa là sự phức tạp của giải thuật học máy (learning algorithm). Hiện tại chưa có một lý thuyết hoàn chỉnh để dung hòa được sự tương tác và đối chọi giữa ba cái kiếng này.

Mặc dù vậy, nhưng khác biệt căn bản giữa Bayes và tần suất vẫn còn nguyên. Và với những đột phá trong vài thập niên gần đây về khía cạnh thuật toán và những vấn đề mở về sự giằng co giữa hiệu quả thống kê và hiệu quả và thuật toán, câu chuyện về Bayes và tần suất không những vẫn còn nóng hổi tính thời sự, mà còn mang nhiều sắc thái mới vô cùng thú vị.

Chủ đề Toán Ứng Dụng, Xác suất & thống kê | 3 phản hồi »

Chúc mừng bác Văn

Giải Fulkerson là một giải đỉnh của toán rời rạc, tối ưu, (và KHMT liên quan) dành cho các bài báo xuất sắc nhất trong ngành. Ba năm một lần.

Anders Johansson, Jeff Kahn, and Van H. Vu, “Factors in random graphs”, Random Structures and Algorithms 33: 1-28, 2008. [ pdf ]

Chủ đề Tin tức đó đây | Phản hồi »

Logic bậc nhất và truy vấn hội

Bài trước lược khảo các khái niệm và kết quả liên quan đến siêu đồ thị phi chu trình và đồ thị dây cung. Bài sau chúng ta sẽ dùng cái khái niệm và kết quả này để thảo luận thuật toán cổ điển của Yannakakis định trị các phép truy vấn hội (conjunctive queries). Mục tiêu của bài này là để giới thiệu các khái niệm của logic bậc nhất dùng để định nghĩa phép truy vấn hội. Ngoài ra, ta sẽ rảo qua một vài ứng dụng của truy vấn hội. Do đằng nào cũng nói về ngữ pháp và ngữ nghĩa của logic bậc nhất, ta cũng sẽ đi vòng và điểm qua vài kết quả cơ bản của logic bậc nhất. Lưu ý rằng một số sách viết về logic trong khoa học máy tính dùng “ngôn ngữ” và “diễn dịch” thay vì “từ vựng” và “cấu trúc” như ta dùng ở đây, theo thuật ngữ của logic học cổ điển.

Đọc tiếp »

Chủ đề Cơ sở dữ liệu, Logic | Tagged , | 7 phản hồi »