Các bài báo kinh điển của KHMT (2): Wald’s sequential analysis theory
Nguyễn Xuân Long | 29 tháng 06, 2005 | 
Bản để in
Nối tiếp bài viết về bài báo nổi tiếng của Shannon, tôi muốn nói về một bài báo kinh điển trong thống kê cùng giai đoạn những năm 40, có vai trò đặc biệt đến KHMT, kinh tế, và operations research, và đẻ ra cả một lĩnh vực mới trong thống kê gọi là sequential analysis. Đó là bài báo sau đây của Abraham Wald, vốn là giáo sư đại học Columbia:
Wald, A. (1945). Sequential tests of statistical hypotheses. Annal of Mathematical Statistics. 16, 117-186.
Bài báo này giới thiệu một vấn đề mới mẻ trong một trong những lĩnh vực quan trọng nhất của ngành thống kê, đó là hypothesis testing, và giới thiệu một hướng giải quyết trọn vẹn. Được thai nghén trong thời kỳ chiến tranh thế giới lần thứ 2, có lẽ Wald đã quan tâm đến những vấn đề rất cụ thể trong lĩnh vực signal processing, như radar signal detection, missile detection, và system failure detection. Chẳng hạn chúng ta có một dãy dữ liệu mà radar có thể bắt được. Chúng ta muốn biết đó là một máy bay địch hay ta, để báo động cho quân đội và dân chúng. Ta muốn ra quyết định sớm nhất có thể được, nhưng cũng hạn chế tình huống báo động giả (false alarm, nói là máy bay kẻ thù trong khi đó là máy bay của ta), cũng như hạn chế tối thiểu tình trạng detection failure (không phát hiện được đây là máy bay địch). False alarm còn được gọi là type 1 error, còn detection failure probability được gọi là type 2 error trong ngôn ngữ ngành thống kê.
Ở dạng đơn giản nhất, bài toán của Wald có thể tóm tắt như sau: Giả sử có một dãy biến ngẫu nhiên độc lập và có cùng hàm phân phối (probability distribution) là P_0 hoặc P_1: X_1, X_2,…,X_n,… Làm thế nào để biết những biến ngẫu nhiên này có hàm phân phối P_0 hay P_1 với sai số nhỏ nhất (cả có thể được mà lại tốn ít mẫu dữ liệu (data sample) nhất? Nếu bạn chỉ cho tôi m mẫu dữ liệu là X_1, X_2,…, X_m, thì vấn đề này đã hoàn toàn đã được giải quyết bằng Neyman-Pearson lemma, và qua đó ta có thể tính được số mẫu dữ liệu tối ưu m là bao nhiêu. Như vậy, lời giải của bài toán radar detection trên là, tùy thuộc vào đòi hỏi tối đa về xác suất báo động giả và xác suất không báo động kịp (type 1 and type 2 probability errors), ta có thể tính được giá trị m tối ưu, và sau khi đã có đủ m mẫu dữ liệu thì sẽ đưa ra quyết định cuối cùng. Phương pháp này gọi là fixed-sample-size test. Tuy nhiên, trên thực tế, nếu bạn là người quan sát radar signal, có lẽ bạn sẽ không chịu làm như vậỵ Nhiều khi bằng cách quan sát chuỗi dữ liệu và theo dõi cách chúng thay đổi, chúng ta có thể đưa ra quyết định chính xác và sớm hơn nhiều.
Những cảm nhận tự nhiên và đơn giản thường là đúng, nhưng phải đợi đến Wald thì mọi việc mới sáng tỏ. Quả thật quan sát này của Wald gây chấn động trong giới thống kê. Hơn nữa, Wald còn đưa ra giải pháp tối ưu cho bài toán trên, sau này đươc gọi là Wald’s sequential likelihood ratio test:
Tại từng thời điểm, sau khi nhận được tín hiệu X_i, chúng ta tính likelihood ratio u_n = P_1(X_n)/P_0(X_n). Quan sát sự biến chuyển của tổng S_n = u_1 +…+u_n, và chúng ta sẽ dừng lại khi S_n vượt ra ngoài một khoảng [A,B] thích hợp. Nếu S_n <>P_0, còn nếu S_n > B thì ta kết luận ngược lại. S_n còn gọi là random walk, và thời điểm n mà chúng ta dừng lại chính là một dạng biến ngẫu nhiên, gọi là hitting time của random walk S_n.
Phải hai năm sau, Wald và học trò của mình là Paul Wolfowitz chứng minh một cách chặt chẽ rằng phương pháp trên là tối ưu nhất. Trên thực tế, Wald’s test có thể tiết kiệm được từ một nửa đến 1/3 số mẫu dữ liệu nếu ta dùng fixed-sample-size test. Điều đáng nói là cùng thời gian đó Arrow, Blackwell và Girshick cũng xuất bản một bài báo chứng minh về tính tối ưu của Wald’s test. Đặc biệt bài báo này lần đầu tiên giới thiệu phương pháp dynamic programming, với khái niệm “cost to go” nổi tiếng, mà 8 năm sau đó được Richard Bellman tổng quát hóa lên cho Markov Decision Processes. Rất tiếc là sau này người ta thường chỉ nhắc đến Bellman với danh nghĩa là người đã sáng tạo ra thuật toán dynamic programming. Bài báo của Wald châm ngòi cho cả lĩnh vực sequential decision-making theory, được áp dụng và phát triển dưới các màu sắc và thuật ngôn khác nhau trong thống kê(sequential analysis), trong operations research (markov decision processes), và trí tuệ nhân tạo ( reinforcement learning)…
Những nhân vật liên quan đến những ngày đầu của sequential analysis đều là những tên tuổi lớn trên bầu trời khoa học. Abraham Wald được coi là một trong những nhà thống kê học lỗi lạc và có ảnh hưỏng nhất của thế kỷ 20, sánh ngang hàng với Fisher và Neyman, những người được coi là ông tổ của thống kê. Kennet Arrow, hiện vẫn là giáo sư ở Stanford, vốn là một học trò của Wald, về sau này được nhận giải Nobel vì những cống hiến trong game-theory. Còn David Blackwell, giáo sư ở Berkeley, được coi là nhà toán học vĩ đại nhất người da đen, có rất nhiều cống hiến về game theory, kinh tế và thống kê học.
Một số tham khảo khác:
Arrow, K. J., Blackwell, D. and Girshick, M. Ạ (1949). Bayes and minimax solutions of sequential decision problems. Econometrica 17, 213-244.
Wald, A and Wolfowitz, J (1948). Optimum character of the sequential probability ratio test. Annal of Math. Statistics 19, 326-339.
Bellman, R (1957). Dynamic programming. Princeton University Press.
