Category Archives: Xác suất & thống kê

Phương pháp xác suất, thống kê, dùng trong KHMT

Phép “chuyển giản” trong học máy

Ngô Quang Hưng | 03/09/2010 | Bản để in Bản để in
Khái niệm “chuyển giản” (reduction) là khái niệm trung tâm của lý thuyết tính toán và thuật toán. Alina Beygelzimer, John Langford, và Bianca Zadrozny có một tutorial hay ở ICML 2009 về “chuyển giản” trong học máy. Ví dụ, ta có thể “chuyển giản” bài toán phân loại (classification) tổng quát về bài toán [...]
Cũng thuộc về chủ đề Trí tuệ nhân tạo | 5 phản hồi »

HM5 — Định lý Vapnik-Chervonenkis cho mô hình giả thuyết không nhất quán

Ngô Quang Hưng | 30/08/2010 | Bản để in Bản để in
Chúng ta tiếp tục chuỗi bài về đề tài “Học máy từ góc nhìn của lý thuyết tính toán”. Các bài trước là: HM1 — Giới thiệu học máy và mô hình nhất quán HM2 — Một số ví dụ trong mô hình nhất quán HM3 — Mô hình PAC và ví dụ HM4 — [...]
Cũng thuộc về chủ đề Lý thuyết tính toán, Trí tuệ nhân tạo | 10 phản hồi »

PCP 10 — Biến đổi Fourier, định lý Arrow và tính duy lý của sự độc tài

Ngô Quang Hưng | 29/07/2010 | Bản để in Bản để in
Như vậy chúng ta đã có chuyến “de-tour” sang các phép xây dựng đồ thị expanders, tính chất của chúng, và tích zig-zag. Đáng lẽ bài kế tiếp này tôi định viết về kết quả của Omer Reingold hồi 2005. Nhưng lại thôi vì thật ra nếu hiểu tích zig-zag rồi thì hiểu chứng minh [...]
Cũng thuộc về chủ đề KHMT và Kinh Tế, Lý thuyết tính toán, Thuật Toán | 13 phản hồi »

GT 10: Thuật toán AMS ước lượng mô-măng tần số

Ngô Quang Hưng | 12/07/2010 | Bản để in Bản để in
10. Thuật toán AMS ước lượng mô-măng tần số Tưởng tượng một chuỗi (rất nhiều, cả triệu) gói dữ liệu đi qua một router trong thời gian ngắn. Gói thứ có địa chỉ IP nguồn nào đó thuộc tập . Với mỗi , gọi là số lần xuất hiện của địa chỉ , còn gọi [...]
Cũng thuộc về chủ đề Thuật Toán | Phản hồi »

GT 9: Tiền xu Chernoff-Bernstein và mẹo trung vị

Ngô Quang Hưng | 10/07/2010 | Bản để in Bản để in
9. Tiền xu Chernoff-Bernstein và mẹo trung vị 9.1. Tiền xu Chernoff-Bernstein Thảy lần độc lập một đồng xu mà xác suất ra mặt ngửa là thì trị kỳ vọng của số lần ra mặt ngửa là . Ông Chernoff bảo rằng xác suất mà tổng số mặt ngửa quấn quít xung quanh sẽ tiến [...]
Cũng thuộc về chủ đề Thuật Toán | Phản hồi »

GT 8: Con gà của ông Chebyshev

Ngô Quang Hưng | 09/07/2010 | Bản để in Bản để in
8. Con gà của ông Chebyshev 8.1. Khoảng cách giữa tư bản hút máu và xã hội chủ nghĩa Tiếp theo bài trước, hãy nói về con gà của bác nông dân. Bác nông dân và địa chủ ăn hết một con gà, nhưng địa chủ ăn sạch cả con, bao gồm xương, lông, cánh, [...]
Cũng thuộc về chủ đề Thuật Toán | 3 phản hồi »

GT 7: Con gà của ông Markov

Ngô Quang Hưng | 08/07/2010 | Bản để in Bản để in
7. Con gà của ông Markov 7.1. Việt Nam có bao nhiêu trọc phú? Tí và Tèo ăn hết một con gà. Ông Markov bảo rằng không thể nào cả Tí lẫn Tèo đều ăn hơn nửa con gà được. Nếu 10 người ăn hết một con gà, thì không thể có hơn 4 anh [...]
Cũng thuộc về chủ đề Thuật Toán | Phản hồi »

Bayesian or Frequentist, which are you?

Nguyễn Xuân Long | 07/04/2010 | Bản để in Bản để in
Giới thiệu với bạn đọc blog KHMT video bài giảng của GS Michael Jordan ở ML summer school (ở Cambridge tháng 9 năm ngoái) về đề tài thú vị này: http://videolectures.net/mlss09uk_jordan_bfway/ Có cả một số bình luận về machine learning trong không gian chung của các nghiên cứu về thống kê. Còn đây là concluding [...]
Cũng thuộc về chủ đề Toán Ứng Dụng, Trí tuệ nhân tạo | 6 phản hồi »

GT 2: Phân Ly và Phân Cách

Ngô Quang Hưng | 15/12/2009 | Bản để in Bản để in
( tiếp theo bài trước ). 2. Ma trận phân ly và ma trận phân cách Tiến Sĩ Nguyễn Quang A là một trong các trí thức hàng đầu của Việt Nam hiện nay. Tôi không biết gì về các công việc làm ăn của anh Quang A, nhưng tôi biết anh đã một tay [...]
Cũng thuộc về chủ đề Combinatorics, Thuật Toán | 4 phản hồi »

GT 1: Bệnh giang mai, đại số, hồi phục tín hiệu thưa, và dòng dữ liệu

Ngô Quang Hưng | 14/12/2009 | Bản để in Bản để in
1. Đại số và bệnh giang mai Hòa thượng (HT) Thích Học Toán là chuyên gia đại số hàng đầu thế giới. (Tôi học đòi cách viết bài của giáo sư Richard Lipton mà tôi rất thích.) Gần đây HT lại thành celebrity sau bầu chọn của tạp chí Time. Nhất định sẽ có nhiều [...]
Cũng thuộc về chủ đề Bảo mật và mật mã học, KHMT và sinh học, Thuật Toán | 6 phản hồi »

Một survey hay về causal inference

Ngô Quang Hưng | 28/11/2009 | Bản để in Bản để in
Anh Long đã nhắc đến Judea Pearl trong một bài viết cũ. Gần đây Judea Pearl có một bài survey rất hay về causal inference. Tôi chưa “ngâm cứu” hết, nhưng cứ giới thiệu nó ở đây, xem như giữ chỗ khi nào ngâm cứu xong thì bàn kỹ hơn.
Cũng thuộc về chủ đề Trí tuệ nhân tạo | Phản hồi »

Loạt bài giảng xác suất thống kê

Nguyễn Xuân Long | 19/09/2009 | Bản để in Bản để in
Anh Nguyễn Tiến Dũng (GS ĐH Toulouse) đang bắt đầu loạt bài giảng về xác suất và thống kê dành cho SV ĐH (không nhất thiết chỉ cho SV ngành toán). Hứa hẹn sẽ rất thú vị.
Chủ đề Xác suất & thống kê | Phản hồi »

Yêu tổ quốc, yêu thống kê

Ngô Quang Hưng | 03/08/2009 | Bản để in Bản để in
Ngày 1 tháng 10 năm nay là kỷ niệm 60 năm ngày thành lập nước Cộng Hòa Nhân Dân Trung Hoa, ta hay gọi là Trung Quốc, nôm na là Khựa Quốc. Theo tờ Wall Street Journal, cục thống kê quốc gia Trung Hoa phát động phong trào làm nhạc viết thơ tưng bừng kỷ [...]
Cũng thuộc về chủ đề Vui - Giải Trí | 4 phản hồi »

Tản mạn về cơ hội trong ngành Thống kê (và KHMT)

Nguyễn Xuân Long | 03/07/2009 | Bản để in Bản để in
Thị trường công việc cho faculty ở các trường ĐH ở Mỹ năm nay đã khép lại. Tôi đã may mắn tìm được một vị trí mà mình yêu thích, và đang hứng khởi chuẩn bị dọn đến thành phố Ann Arbor, Michigan. Cũng giống như việc chuẩn bị apply vào grad schools để theo [...]
Cũng thuộc về chủ đề Dành cho du học sinh | 16 phản hồi »

PCP 7 — Expanders: góc nhìn xác suất

Ngô Quang Hưng | 29/05/2009 | Bản để in Bản để in
8.d. Spectral expanders và tốc độ hội tụ của random walks trên expanders Trong bài này chúng ta sẽ chứng minh rằng một đồ thị có spectral gap lớn thì “tương đương” với tốc độ hội tụ của một random walk trên đồ thị càng cao. (Sở dĩ ta để tương đương trong ngoặc kép [...]
Cũng thuộc về chủ đề Lý thuyết tính toán, Thuật Toán | 1 phản hồi »