Các bài báo kinh điển của KHMT (3)

Một bài báo được trích dẫn rộng rãi trong giới KHMT, xử lý thông tin, machine learning, v.v. là bài báo của Chernoff:

Chernoff, H. (1952). A measure of asymptotic efficiency for tests of an hypothesis based on the sum of observations. Ann. Math. Statist. 23, 493.

Một cách tóm tắt, nếu bạn có n biến ngẫu nhiên độc lập, và cùng hàm phân phối F (independent and identically distributed, or i.i.d.) x_1, x_2,..., x_n, để ước tính giá trị trung bình của hàm phân phối F, chúng ta đều biết rằng chỉ việc lấy tổng của n dữ liệu này cộng lại và chia cho n. Một định lý căn bản và quan trọng bậc nhất của lý thuyết xác suất, law of large numbers, nói rằng, (với những điều kiện thích hợp), khi n đủ lớn thì ước đoán trên của ta sẽ tiến dần đến giá trị trung bình chính xác của F. Đây chính là hiện tượng concentration nổi tiếng trong xác suất.

Tất nhiên mọi ước đoán đều có sai số, và xác suất của sai số đó, còn gọi là tail probability, được chứng minh trong bài báo của Chernoff là exponentially small. Chernoff còn giới thiệu trong bài báo của mình khái niệm Chernoff exponent, chính là rate of the exponential decrease. Khái niệm này vô cùng hữu ích trong hypothesis testing và coding theory, và có vai trò tương tự như khái niệm mutual information và entropy của Shannon vậy. Một bài báo rất nổi tiếng khác với kết quả tương tự như của Chernoff, nhưng tổng quát và chặt hơn nhiều:

Shannon, Gallanger, and Berlekamp (1967). Lower bounds to error probability. Information and Control, 10(1).

Chernoff không phải người đầu tiên, và cũng không phải người cuối cùng nói về hiện tượng concentration trong lý thuyết xác suất, bài báo nổi tiếng của ông chỉ là một kết quả đơn giản nhưng vô cùng hữu ích. Chernoff's bound là một ví dụ đơn giản nhất của cả một mảng nghiên cứu đồ sộ về large deviation theory: Làm sao để ước tính error probability khi chúng ta dùng dữ liệu quan sát được để tính một thống kê cụ thể nào đó (như mean và variance). Nghiên cứu về large deviation theory quan tâm cả đến những dãy biến ngẫu nhiên không độc lập, và mở rộng cả đến những vật thể xác suất vô hạn chiều (như empirical processes).

Tôi hy vọng sẽ có dịp nói thêm (và nghe nhiều hơn ở blog này) về hiện tượng concentration, không chỉ trong lý thuyết xác suất, mà trong cả tự nhiên và cuộc sống của chúng ta nữa. Vì lẽ đó, hiện tượng concentration và large deviation theory chính là nền tảng cơ bản tạo nên nhiều ứng dụng rộng rãi trong khoa học công nghệ nói chung và ngành máy tính, điện tử nói riêng. Xin liệt kê một vài ví dụ chung:

 

• Xây dựng thuật toán ngẫu nhiên (randomized algorithms): Rất nhiều vấn đề mà người ta chưa tìm được deterministic algorithm một cách hiệu quả, nhưng lại có nhiều thuật toán ngẫu nhiên mà có thể giải quyết hiệu quả được vấn đề trong phần lớn các trường hợp. Rất nhiều thuật toán ngẫu nhiên trong ngành KHMT là ứng dụng cụ thể của các thuật toán sampling nổi tiếng, như Monte Carlo và Monte Carlo Markov Chain (bao gồm Gibbs sampling, Metropolis-Hasting sampling,vv...).
• Rất nhiều tính chất thuật toán rất khó được mổ xẻ trong từng trường hợp, nhưng hiện tượng concentration (thường là đúng) nói rằng ta chỉ nên phân tính những tính chất chung (average behavior/properties) là đủ. Điều này làm cho cuộc sống của ta dễ dàng hơn nhiều. (Ví dụ, bạn muốn tìm số cliques trong một graph ngẫu nhiên? Hoặc bạn muốn tìm max cut trong một graph bằng một thuật toán độc đáo? )
• Trong việc học một mô hình từ dữ liệu (Learning a model from empirical data): Nếu càng có nhiều dữ liệu, hiện tượng concentration giúp ta biết rằng, ta sẽ tìm được mô hình càng chính xác. Đây chính là nền tảng của toàn bộ ngành thống kê, machine learning, và nói chung tất cả các ngành khoa học có liên quan đến xây dựng mô hình từ dữ liệu như computational biology, public health, demography, vv...

Lý thuyết thông tin (information theory/coding theory/signal processing):
Shannon cho chúng ta biết rằng nếu dùng code block đủ dài (tương tự như khi có đủ dữ liệu) thì sẽ tồn tại một phương pháp coding/compression hầu như không có lỗi.