Một bài toán kinh điển trong truyền thông không dây đã được giải sau khoảng 25 năm, với sự hỗ trợ của hai mô hình AI là GPT-5.6 và Fable 5.
Dimitris Papailiopoulos, nhà nghiên cứu chính tại Microsoft Research và phó giáo sư tại Đại học Wisconsin-Madison, đã chứng minh một thuật toán thời gian đa thức có thể đạt chính xác ngưỡng Maximum Likelihood, hay xác suất tối đa, trong bài toán phát hiện MIMO. Ông cho biết quá trình hoàn thiện chứng minh kéo dài khoảng 7 ngày.
MIMO là công nghệ cho phép truyền nhiều luồng dữ liệu cùng lúc qua nhiều anten. Trong bài toán phát hiện MIMO, bộ phát gửi một chuỗi bit qua kênh truyền. Kênh này trộn các tín hiệu và thêm nhiễu, còn bộ thu phải khôi phục chính xác chuỗi bit ban đầu.
Về lý thuyết, cách chắc chắn nhất là thử toàn bộ các khả năng rồi chọn phương án phù hợp nhất với tín hiệu nhận được. Nhưng với N bit, số khả năng lên tới 2^N. Khi N tăng, phương pháp này nhanh chóng trở nên không khả thi.
Từ năm 1989, Sergio Verdú đã chứng minh bài toán này là NP-khó trong trường hợp xấu nhất. Tuy nhiên, các kênh không dây thực tế thường được tạo ra ngẫu nhiên chứ không phải những trường hợp được cố tình thiết kế để gây khó khăn. Vì vậy, giới nghiên cứu đặt ra một câu hỏi khác: liệu có thể xây dựng thuật toán nhanh nhưng vẫn đạt được khả năng khôi phục tối ưu trong các kênh ngẫu nhiên?
Năm 2001, Babak Hassibi và Haris Vikalo cho rằng thuật toán Sphere Decoding có thể đạt độ phức tạp đa thức. Nhưng đến năm 2005, Joakim Jaldén và Björn Ottersten chứng minh rằng độ phức tạp kỳ vọng của phương pháp này thực tế vẫn tăng theo cấp số nhân.
Sau đó, các nhà nghiên cứu thử nhiều hướng khác như thư giãn bán xác định, tìm kiếm lật bit, AMP và các phương pháp vật lý thống kê. Một phương pháp Box Relaxation năm 2020 đã cải thiện đáng kể kết quả, nhưng vẫn cần tỷ lệ tín hiệu trên nhiễu khoảng 4logN, cao gấp đôi ngưỡng lý thuyết.
Khoảng cách giữa "về mặt thống kê có thể khôi phục" và "có thuật toán nhanh để khôi phục" vì thế tồn tại suốt nhiều năm.
Nghiên cứu mới của Papailiopoulos thu hẹp khoảng cách này bằng một thuật toán gồm hai bước và có độ phức tạp đa thức, khoảng O(N³) phép toán.
Điểm đáng chú ý là ý tưởng này đến từ sự kết hợp giữa con người và AI. Papailiopoulos thử bài toán với GPT-5.6 và Fable 5. Hai mô hình đưa ra những hướng tiếp cận khác nhau. GPT-5.6 đề xuất một hướng dựa trên AMP, trong khi Fable 5 đưa ra phương pháp kết hợp làm tròn LMMSE với thuật toán lật bit tham lam.
Cuối cùng, Papailiopoulos chọn hướng do Fable đề xuất và sử dụng GPT-5.6 để kiểm tra, phát hiện và sửa các lỗ hổng trong chứng minh.
Thuật toán có hai bước chính. Đầu tiên, LMMSE tạo ra một nghiệm gần đúng rồi làm tròn các giá trị thành +1 hoặc -1. Nghiệm này chưa hoàn hảo nhưng bài toán chứng minh cho thấy số bit sai chỉ ở mức O(N), tức tỷ lệ bit sai giảm dần khi kích thước hệ thống tăng.
Bước thứ hai sử dụng lật bit tham lam. Thuật toán kiểm tra từng bit, chọn phép lật giúp giảm hàm chi phí nhiều nhất rồi tiếp tục lặp lại. Chứng minh cho thấy khi nghiệm hiện tại còn sai, luôn tồn tại một phép lật giúp giảm chi phí. Vì vậy thuật toán không bị mắc kẹt ở nghiệm sai và cuối cùng chỉ có thể dừng tại chuỗi bit chính xác.
Điểm quan trọng hơn là nghiên cứu không chỉ chứng minh thuật toán mới đạt ngưỡng 2logN. Nó còn chứng minh rằng nếu tỷ lệ tín hiệu trên nhiễu thấp hơn ngưỡng này một chút, ngay cả Maximum Likelihood cũng bắt đầu thất bại. Điều đó cho thấy thuật toán mới đã chạm đúng giới hạn lý thuyết của bài toán.
Papailiopoulos từng nghiên cứu chính bài toán này từ khi còn là nghiên cứu sinh. Năm 2009, ông cùng Alex Dimakis thử giải nó bằng phương pháp MCMC nhưng không thành công. 17 năm sau, chính bài toán từng khiến ông bối rối lại trở thành một trong những vấn đề ông giải được với sự hỗ trợ của AI.
Điều đáng chú ý nhất không phải là AI tự mình giải được một bài toán 25 năm tuổi. Papailiopoulos vẫn phải kiểm tra từng bước, đơn giản hóa các chứng minh và tự xác minh toàn bộ lập luận. Nhưng câu chuyện cho thấy AI đang bắt đầu đóng một vai trò khác trong nghiên cứu toán học: không chỉ trả lời câu hỏi, mà còn đề xuất hướng chứng minh, tìm lỗ hổng và giúp nhà nghiên cứu khám phá những con đường mà trước đó họ chưa thử.
Tham khảo:
Dimitris Papailiopoulos, nhà nghiên cứu chính tại Microsoft Research và phó giáo sư tại Đại học Wisconsin-Madison, đã chứng minh một thuật toán thời gian đa thức có thể đạt chính xác ngưỡng Maximum Likelihood, hay xác suất tối đa, trong bài toán phát hiện MIMO. Ông cho biết quá trình hoàn thiện chứng minh kéo dài khoảng 7 ngày.
MIMO là công nghệ cho phép truyền nhiều luồng dữ liệu cùng lúc qua nhiều anten. Trong bài toán phát hiện MIMO, bộ phát gửi một chuỗi bit qua kênh truyền. Kênh này trộn các tín hiệu và thêm nhiễu, còn bộ thu phải khôi phục chính xác chuỗi bit ban đầu.
Về lý thuyết, cách chắc chắn nhất là thử toàn bộ các khả năng rồi chọn phương án phù hợp nhất với tín hiệu nhận được. Nhưng với N bit, số khả năng lên tới 2^N. Khi N tăng, phương pháp này nhanh chóng trở nên không khả thi.
Từ năm 1989, Sergio Verdú đã chứng minh bài toán này là NP-khó trong trường hợp xấu nhất. Tuy nhiên, các kênh không dây thực tế thường được tạo ra ngẫu nhiên chứ không phải những trường hợp được cố tình thiết kế để gây khó khăn. Vì vậy, giới nghiên cứu đặt ra một câu hỏi khác: liệu có thể xây dựng thuật toán nhanh nhưng vẫn đạt được khả năng khôi phục tối ưu trong các kênh ngẫu nhiên?
25 năm khoảng cách giữa lý thuyết và thuật toán
Các nghiên cứu trước đây xác định một ngưỡng quan trọng. Khi tỷ lệ tín hiệu trên nhiễu đạt khoảng 2logN, xác suất khôi phục chính xác toàn bộ dữ liệu sẽ tiến tới 1. Đây được xem là ngưỡng Maximum Likelihood.Năm 2001, Babak Hassibi và Haris Vikalo cho rằng thuật toán Sphere Decoding có thể đạt độ phức tạp đa thức. Nhưng đến năm 2005, Joakim Jaldén và Björn Ottersten chứng minh rằng độ phức tạp kỳ vọng của phương pháp này thực tế vẫn tăng theo cấp số nhân.
Sau đó, các nhà nghiên cứu thử nhiều hướng khác như thư giãn bán xác định, tìm kiếm lật bit, AMP và các phương pháp vật lý thống kê. Một phương pháp Box Relaxation năm 2020 đã cải thiện đáng kể kết quả, nhưng vẫn cần tỷ lệ tín hiệu trên nhiễu khoảng 4logN, cao gấp đôi ngưỡng lý thuyết.
Khoảng cách giữa "về mặt thống kê có thể khôi phục" và "có thuật toán nhanh để khôi phục" vì thế tồn tại suốt nhiều năm.
Nghiên cứu mới của Papailiopoulos thu hẹp khoảng cách này bằng một thuật toán gồm hai bước và có độ phức tạp đa thức, khoảng O(N³) phép toán.
Điểm đáng chú ý là ý tưởng này đến từ sự kết hợp giữa con người và AI. Papailiopoulos thử bài toán với GPT-5.6 và Fable 5. Hai mô hình đưa ra những hướng tiếp cận khác nhau. GPT-5.6 đề xuất một hướng dựa trên AMP, trong khi Fable 5 đưa ra phương pháp kết hợp làm tròn LMMSE với thuật toán lật bit tham lam.
Cuối cùng, Papailiopoulos chọn hướng do Fable đề xuất và sử dụng GPT-5.6 để kiểm tra, phát hiện và sửa các lỗ hổng trong chứng minh.
Thuật toán có hai bước chính. Đầu tiên, LMMSE tạo ra một nghiệm gần đúng rồi làm tròn các giá trị thành +1 hoặc -1. Nghiệm này chưa hoàn hảo nhưng bài toán chứng minh cho thấy số bit sai chỉ ở mức O(N), tức tỷ lệ bit sai giảm dần khi kích thước hệ thống tăng.
Bước thứ hai sử dụng lật bit tham lam. Thuật toán kiểm tra từng bit, chọn phép lật giúp giảm hàm chi phí nhiều nhất rồi tiếp tục lặp lại. Chứng minh cho thấy khi nghiệm hiện tại còn sai, luôn tồn tại một phép lật giúp giảm chi phí. Vì vậy thuật toán không bị mắc kẹt ở nghiệm sai và cuối cùng chỉ có thể dừng tại chuỗi bit chính xác.
Điểm quan trọng hơn là nghiên cứu không chỉ chứng minh thuật toán mới đạt ngưỡng 2logN. Nó còn chứng minh rằng nếu tỷ lệ tín hiệu trên nhiễu thấp hơn ngưỡng này một chút, ngay cả Maximum Likelihood cũng bắt đầu thất bại. Điều đó cho thấy thuật toán mới đã chạm đúng giới hạn lý thuyết của bài toán.
Papailiopoulos từng nghiên cứu chính bài toán này từ khi còn là nghiên cứu sinh. Năm 2009, ông cùng Alex Dimakis thử giải nó bằng phương pháp MCMC nhưng không thành công. 17 năm sau, chính bài toán từng khiến ông bối rối lại trở thành một trong những vấn đề ông giải được với sự hỗ trợ của AI.
Điều đáng chú ý nhất không phải là AI tự mình giải được một bài toán 25 năm tuổi. Papailiopoulos vẫn phải kiểm tra từng bước, đơn giản hóa các chứng minh và tự xác minh toàn bộ lập luận. Nhưng câu chuyện cho thấy AI đang bắt đầu đóng một vai trò khác trong nghiên cứu toán học: không chỉ trả lời câu hỏi, mà còn đề xuất hướng chứng minh, tìm lỗ hổng và giúp nhà nghiên cứu khám phá những con đường mà trước đó họ chưa thử.
Tham khảo:
