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 bạn hỏi thế công trình của HT có ý nghĩa như thế nào trong cuộc sống, hoặc ít nhất cũng tìm cách “diễn Nôm” ý nghĩa của đóng góp của HT. Để trả lời các câu hỏi kiểu đó, xin mạn phép gợi ý 3 hướng trả lời sau đây. (Hướng cuối cùng là liên quan đến KHMT, cho nên các bạn hủ máy tính có thể nhảy xuống đó mà đọc, bỏ qua các hướng đầu.)
- Kể lại một truyền thuyết về Euclid, do Stobaeus kể lại:
Khi một chú học trò hỏi Euclid: “chúng ta học hình học thì được cái gì?”, Euclid gọi một anh nô lệ vào bảo: “cho nó một đồng xu, vì nó muốn kiếm lời từ cái nó học”.
- Kể lại câu chuyện của Cụ Hinh và Anh La:
Nghe thiên hạ đồn rằng có bộ kinh tiếng Phạn nọ rất thâm sâu. Cụ Hinh cầu cạnh anh La giảng giải cho. Anh La nhíu mày, rít thuốc, nhâm nhi cà fê cả buổi sáng. Đến chiều, anh La dịch toàn bộ kinh sang tiếng Bồ.
Cụ Hinh xem xong gật gù tán thưởng.
- Đại số có ứng dụng trong trị bệnh giang mai.
Hồi thế chiến thứ 2, Robert Dorfman và David Rosenblatt là hai nhà kinh tế làm việc cho phòng quản lý giá cả (Office of Price Administration) của Mỹ. Họ thiết kế một thủ thục thử máu để chỉ ra ứng viên quân dịch nào có bệnh giang mai. Hồi đó người ta chưa biết chữa giang mai, và rất sợ nó lây lan vào quân dân. (Mặc dù penicillin được Alex Fleming khám phá hồi 1928, phương pháp sản xuất penicilin hàng loạt phải chờ đến đầu thập thiên 40, và sau đệ nhị thế chiến người ta mới thật sự sản xuất penicillin cho đại chúng.) Dorfman có một bài ở tạp chí Annals of Mathematical Statistics mô tả bài toán này và một giải pháp đơn giản.
Số là người ta có thể lẫy mẫu máu của các ứng viên quân dịch. Sau đó có thể dùng phép thử máu Wasserman để xem mẫu máu có kháng nguyên giang mai hay không. Nếu có kháng nguyên giang mai thì nhiều khả năng là chú nhóc bị bệnh, và vì thế sẽ mất dịp tham gia D-Day. Hãy bỏ qua vụ false positive, và cho rằng phép thử máu không bị lỗi: nếu phép thử bảo có là có! (Chúng ta sẽ quay lại với trường hợp phép thử bị lỗi sau.) Vấn đề là thử nhiều triệu mẫu máu như vậy rất tốn thời gian và công sức. Ý tưởng của Dorfman là bỏ nhiều mẫu máu vào một “nhóm” và thử cùng một lúc. Nếu phép thử bảo không thì tất cả các mẫu máu đều âm tính. Nếu phép thử bảo có thì ít nhất một trong các mẫu máu là dương tính. Câu hỏi là, cho trước 
Từ bài báo đó, Môn thử nhóm
- Thay mẫu máu bằng các đồng tiền, và phép thử máu bằng phép cân tiền thì ta có các biến thể của các bài toán tìm tiền giả rất phổ biến.
- Stan Ulam (một đồng tác giả của bom nguyên tử H) trong quyển Adventures of a Mathematician
có đặt một bài toán gọi là bài toán “20 câu hỏi” như sau: Tí nghĩ trong đầu một số nguyên giữa
và một triệu, Tèo có quyền hỏi Tí các câu hỏi nhị phân (nghĩa là câu trả lời chỉ là Có hoặc Không). Tèo cần hỏi bao nhiêu câu hỏi để đoán được con số mà Tí nghĩ? Ở đây, con số bí mật là mẫu máu bị giang mai, các câu hỏi nhị phân là các phép thử máu. Dĩ nhiên, Tí có thể nghĩ nhiều hơn một số bí mật, và trong một biến thể khác thì Tèo cần phải chỉ ra tất cả các con số bí mật mà Tí nghĩ.
- Sàng DNA (DNA screening)
trong sinh học tính toán
- Pattern matching
- Dòng dữ liệu (data streaming)
- Compressed sensing & sparse signal recovery
- Nén ảnh
- Nhiều ứng dụng trong mạng máy tính như Thiết kế MAC-protocol cho các mạng cục bộ và mạng cảm biến, gán kênh trong mạng không dây
- Rất nhiều ứng dụng trong bảo mật như Digital forensics, Xác minh các chữ ký điện tử theo nhóm
- vân vân
Một biến thể rất quan trọng của bàn toán thử nhóm là “thử nhóm bất ứng biến” (non-adaptive group testing), trong đó chúng ta phải thiết kế tất cả các phép thử trước, thử tất các các nhóm cùng một lúc, rồi từ đó chỉ ra các mẫu máu bị bệnh. Nếu cho phép “ứng biến” thì mẫu sau có thể tùy thuộc vào kết quả thử của mẫu trước. Ví dụ như Tèo hỏi Tí “số bạn nghĩ có lớn hơn 500 nghìn không?”, nếu câu trả lời là Có thì hỏi tiếp “số bạn nghĩ có lớn hơn 750 nghìn không?”, còn nếu câu trả lời là Không thì hỏi “số bạn nghĩ có lớn hơn 250 nghìn không?” Trong biến thể “bất ứng biến” thì không được thiết kế các câu hỏi kiểu đó, mà phải viết tất cả các câu hỏi lên giấy, gửi cho Tí tất cả, rồi dựa trên tất cả các câu trả lời để xác định các con số bí mật.
Năm 1964, Kautz và Singleton viết một bài báo trên tạp chí IEEE Transactions on Information Theory, trong đó họ đề ra một cách thiết kế các nhóm chỉ cần 
Mã MDS phổ biến nhất là mã Reed-Solomon, được dùng hàng ngày trong các ổ đĩa cứng, trong các CD và DVD, trong hệ thống truyền thông xDSL, trong truyền thông vệ tinh, vân vân và vân vân. Ý tưởng chính của mã RS rất đơn giản: để gửi một đa thức bậc 
Gần đây hơn, mã RS và các mã RS tổng quát còn được chứng minh là có tính chất “giải mã danh sách” được (list-decodable), liên quan rất mật thiết đến lý thuyết độ phức tạp và định lý PCP. Dùng các kết quả này, không những chúng ta có thể thiết kế các phép thử nhóm hiệu quả (chỉ cần 
Hy vọng là mối liên hệ giữa đại số và bệnh giang mai đã được thiết lập. Lần tới chúng ta sẽ đi vào chi tiết kỹ thuật — không phải của bệnh giang mai — mà là của cả bài toán thử nhóm, các thuật toán xây dựng phép thử và giải mã kết quả thử, và của cả một số ứng dụng của bài toán thử nhóm.
7 Comments
Bài viết hay quá, chú ạ. Câu hỏi số 2. của Stan Ulam cháu cũng có nghĩ qua, rồi sau đó giải bằng cách xây dựng một binary decision tree. Đếm số lá & cm rằng chiều cao của cây phải ít nhất là log(N).
Lúc nào rảnh rỗi hơn là phải mượn quyển Combinatorial group testing and its applications về đọc thôi.
@Phong: xây dựng cây quyết định chắc được xếp vào nhóm adaptive group testing. Trong khi ở đây người ta muốn thực hiện các phép thử đồng thời cơ.
@Bác Hưng: Bác Hưng ơi có thể giải thích cho PB về vai trò của expanded graph trong việc thiết kế ma trận đo không ?
Do PB sử dụng thử nghiệm một thuật toán gọi là sparse matching pusuit (SMP) dựa trên expanded graph ở đây
http://groups.csail.mit.edu/toc/sparse/wiki/index.php?title=Sparse_Recovery_Experiments
theo lý thuyết thì SMP có giới hạn số phép đo M là O(Klog(K/N) với N là không gian tín hiệu và K là số sparse( ứng với d trong expanded graph). Nhưng thực nghiệm thì số phép đo M của SMP lại khá lớn. Chẳng hạn với K =50 thì M của SMP là 2200 trong khi Linear programming là 500. Khi PB đem thử nghiệm với giải thuật Orthogonal Matching pursuit (OMP)
http://igorcarron.googlepages.com/mondaymorningalgorithmasseenonnuitblanch
với cùng loại ma trận sparse thì kết quả là M là khoảng 700 với K =50.
Cho nên PB không rõ vậy expanded graph có tác dụng gì, vì OMP cũng như LP không quan tâm đến cách thức cấu tạo của ma trận đo ?
Hi PB,
Khoảng cách xa giữa thực nghiệm và lý thuyết nhiều khi nằm trong cái hằng số trong big-O. Tôi hoàn toàn không phải chuyên gia về sparse signal recovery, dù đã nghe và nói chuyện với Piotr Indyk về SMP. Tuy nhiên tôi sẽ cố gắng trong các bài tới giải thích mối liên hệ giữa expander graphs và group testing, và expander graphs với SMP.
“… Nhất định sẽ có nhiều bạn hỏi thế công trình của HT có ý nghĩa như thế nào trong cuộc sống, …”
Tôi xin kể câu chuyện chứng kiến trực tiếp, Hoà thượng có thể xác nhận chuyện này
Hồi tháng 8 năm 08, ở ĐH Quy nhơn có diễn ra Đại hội toán toàn quốc lần thứ 7, khi đó HT được mời báo cáo phiên toàn thể đầu tiên. Kết thúc đoạn trình bày sang đoạn hỏi han, giữa lúc mọi người rất quan tâm và thán phục thì một chị đứng lên hỏi, đại ý yêu cầu anh Châu cho biết ứng dụng trong cuộc sống của các kết quả vừa được trình bày trong báo cáo. Hội trường xì xào, HT bực ra mặt và trả lời rằng:
“chả có ứng dụng gì”.
Sau đó có một câu hỏi của GS Nguyễn Tự Cường dẫn đến câu trả lời của HT là
“…Langland rất vui vì giả thiết bị bế tắc lâu nay đã được chứng minh, và Langland lại hăm hở tiếp tục công việc”
Ngay lập tức có một bác đứng lên nói: “đấy đấy đó là một ứng dụng đấy, đã cứu vớt được một cuộc đời”
Hoà thượng chỉ cười xoà.
Tôi xin lỗi các anh vì viết kể lể dài dòng quá.
Hi bac Hu+ng,
Dde tai nay rat hay, va noi chung chua dduoc phat trien nhieu. Ddac biet ddi tu cac mo hinh xac suat cho nhom va cac cau truc dai so khac (mot vi du kinh dien la Haar measure), va lam the nao dde giai quyet van de statistical estimation trong do. Code design dung cac cau truc dai so rat nhieu, nhung khia canh thong ke, theo cam nhan cua toi, thi moi chi xoay quanh ap dung kha don gian cua hypothesis testing.
Dan engineer thi co gang design codes va chung minh tinh chat cua no. Voi cai nhin thong ke, toi dac biet quan tam den van de lam sao hoc duoc good design tu du lieu. Dung nhu bac noi, moi thu deu co the duoc coi la experiment design. Vi du trong signal processing gan day co compressed sensing/sparse signal recovery, do la mot dang dimensionality reduction, kinh dien hon thi co quantization theory. Trong thong ke va trong machine learning thi cung co variable selection, dimension reduction, sparse regression, structure learning, etc. Tat ca deu duoc coi la van de learning of design.
Trong coding noi rieng va experiment design noi chung thi khai niem thong ke su dung chu yeu la khai niem khoang cach (divergence) giua cac ham phan bo do cac design khac nhau tao ra; tong quat hon la cac khai niem asymptotics ve information. Cai nay co tu thoi nhung nam 50, voi Kullback, Leibler va Blackwell, khong ke dden Shannon. Tuy nhien su lien he giua khai niem asymptotic ve information va cau truc to hop cua cac design thi noi chung rat la long leo, theo toi duoc biet. Cai nay cac nha thong ke thi chiu vi it nguoi ranh re ve to hop va dai so. Ma dan lam to hop va dai so thi lai biet it hon ve thong ke. Ai ket hop duoc ca hai ky nang nay thi co the se tao ra duoc nhung ket qua moi.
Lam the nao de estimate duoc good design tu data? Gan day mot huong hay la su dung cac phuong phap convex relaxation (nhu l1-relaxation trong compressed sensing chang han). Nhieu nguoi nhay len cai bandwagon nay, tham chi ca Terrence Tao. Nhung rat co the huong nay da ddi dden gioi han, vi phan lon cac ket qua chung minh duoc dua tren cau truc mo hinh tuyen tinh rat don gian cua du lieu. Voi cau truc phuc tap hon mot chut thi chiu. Toi nghi ve lau dai cac phuong phap Bayesian se rat trien vong va rong mo. Van de o day, quay lai comment ban dau, la lam sao tao ra cac ham phan bo cho cac cau truc dai so va cau truc to hop — cai nay se cho ta cac prior distribution huu ich. De biet cai nay thi phai hoc them nhieu ve stochastic processes.
Hi bác Long, tôi hoàn toàn đồng ý với kết luận này:
Tôi quan tâm đến thử nhóm từ góc nhìn tổ hợp (và một ít đại số cho codes) vì hai lý do: một là trong một số ứng dụng thì đây là góc nhìn đúng (có thể có chặn trên cho số mẫu dương tính), hai là ngại đung vào phân bố xác suất cho các mẫu dương tính vì sợ không chứng minh được kết quả gì hay ho
, và rất khó chứng minh lower bound.
Ví dụ, kết quả “decode in polylog time” của bọn tôi (link ở trên) sẽ phải bị biến thành “decode in expected polylog time with some expected quality”, và tôi chưa biết làm cách nào để có kết quả như vậy. Mặc dù, tôi phải đồng ý rằng trong nhiều ứng dụng thì thiết lập bài toán thống kê tự nhiên hơn bài toán tổ hợp nhiều.
Sao hok thấy viết bài về Compressed Sensing và khôi phục dữ liệu thưa thớt ?? Chủ đề này mình đang theo đuổi. :d