Thuật toán FFT của OpenAI: Không phải đột phá, mà là một "khai thác" sai lệch

Minh họa về thuật toán và tính toán

Trong tuần vừa qua, OpenAI đã công bố một loạt bài báo toán học, trong đó có một kết quả được quảng bá là "thuật toán biến đổi Fourier nhanh hơn". Tuy nhiên, theo phân tích của Ben Recht trên blog argmin, đây không phải là một đột phá thực sự, mà là một ví dụ điển hình cho thấy lý thuyết khoa học máy tính đang ngày càng trở nên xa rời thực tế.

Biến đổi Fourier nhanh (FFT) là gì và tại sao nó quan trọng?

Biến đổi Fourier nhanh (FFT) là một trong những phát minh quan trọng nhất của xử lý tín hiệu số. Về bản chất, FFT là cách nhanh để trích xuất nội dung tần số từ tín hiệu, cho phép phân tích, lọc và thao tác các tần số trên các dải phổ khác nhau một cách hiệu quả.

Thuật toán FFT được James Cooley và John Tukey công bố năm 1965 (dù Gauss đã phát hiện ra ý tưởng tương tự từ năm 1805), hoạt động dựa trên nguyên lý chia để trị. Thay vì tính toán với độ phức tạp bậc hai O(n²), FFT chỉ cần khoảng 5n log₂n phép toán.

Để hình dung cụ thể: khi n là 1.000, n² là 1.000.000 còn 5n log n chỉ khoảng 50.000 — nhanh hơn 20 lần. Khi n là 1.000.000, mức tăng tốc lên tới 10.000 lần. Sự khác biệt này có thể quyết định một phép biến đổi có khả thi hay không trong các ứng dụng xử lý tín hiệu.

Minh họa về độ phức tạp thuật toán

Vấn đề với ký hiệu "big-O" và các thuật toán "ngân hà"

Kể từ khi FFT ra đời, giới toán học không ngừng tìm kiếm các thuật toán nhanh hơn. Về lý thuyết, giới hạn dưới của phép biến đổi Fourier là khoảng n phép toán — bởi chỉ để ghi kết quả ra cũng đã cần n bước. FFT chậm hơn giới hạn này khoảng 5 log₂n lần, và với n cỡ một nghìn tỷ thì hệ số này lên tới 200.

OpenAI tuyên bố đã tìm ra thuật toán có số hạng log(n) nhỏ hơn một chút. Nghe qua có vẻ hấp dẫn, nhưng vấn đề nằm ở chỗ ký hiệu big-O đã bị lạm dụng đến mức trở nên vô nghĩa.

Định nghĩa chuẩn của big-O nói rằng: thuật toán có thời gian chạy T(n) = O(F(n)) nếu tồn tại một số nguyên N và một hằng số C sao cho thời gian chạy thực tế bị chặn trên bởi C nhân với F(n), miễn là n đủ lớn. Vấn đề là chữ "đủ lớn" có thể mang nghĩa cực kỳ phi thực tế.

O(n) không có nghĩa là 50n. Nó có thể có nghĩa là 10⁸⁰n. Một thuật toán yêu cầu n + 10⁸⁰ vẫn được coi là thuật toán "thời gian tuyến tính".

Richard Lipton và Ken Regan gọi những thuật toán có hằng số ẩn khổng lồ như vậy là thuật toán ngân hà (galactic algorithms). Với thuật toán FFT của OpenAI, giá trị ước lượng của C lên tới 10¹⁰⁰ khi N = 10¹². Nghĩa là ngay cả khi n = 10¹⁰⁰, FFT Cooley-Tukey cổ điển vẫn nhanh hơn tới 10⁹⁹ lần.

Mô hình tính toán không tồn tại trong thực tế

Vấn đề nghiêm trọng hơn nằm ở mô hình tính toán mà OpenAI sử dụng. Thuật toán giả định có thể lưu trữ và nhân các số phức ở độ chính xác tùy ý. Thực tế, thuật toán yêu cầu nhân các số phức có độ lớn tăng siêu đa thức theo n. Nếu lưu trữ dưới dạng bit, yêu cầu bộ nhớ sẽ tăng theo hàm mũ so với độ dài đầu vào.

Chúng ta không có máy tính nào có thể thực hiện phép nhân như vậy trong một phép toán duy nhất. Vì thế, ngay cả khi định lý trong bài báo là "đúng" (không ai kiểm chứng và cũng chẳng ai quan tâm), nó vẫn không giải quyết được bài toán mà chúng ta thực sự đặt ra khi tìm kiếm một FFT nhanh hơn.

Điều này không hề gây ngạc nhiên với những người quen với phân tích lý thuyết về FFT:

• Năm 1973, Jacques Morgenstern đã chứng minh rằng không thể tính biến đổi Fourier nhanh hơn ½ n log n nếu các hệ số phức có độ lớn bị chặn.
• Bốn mươi năm sau, Nir Ailon chứng minh không thể tính FFT nhanh hơn n log n mà không gây bất ổn định số nghiêm trọng.

Kết quả mới của OpenAI vì thế không phải là một đột phá toán học, mà là một sự lạ lùng của việc các nhà khoa học máy tính định nghĩa đặc tả thiết kế của mình một cách tồi tệ.

Khi lý thuyết mất kết nối với câu hỏi ban đầu

Tác giả Ben Recht cho rằng nhiều kết quả "lớn" khác trong kho bài báo của OpenAI cũng có thể bị phê bình theo cách tương tự. Ví dụ, một kết quả về nhân hai ma trận trong O(n^2.25) phép toán sử dụng một công trình mà ngay cả hằng số ẩn trong big-O cũng không thể ước lượng được — nó có thể coi như vô hạn.

Nếu được viết tốt hơn nhiều, những bài báo này có thể đã lọt vào các hội nghị danh giá nhất về lý thuyết khoa học máy tính (STOC hoặc FOCS). Bài về nhân ma trận thậm chí có thể đoạt giải thưởng. Nhưng cả hai đều không liên quan gì đến máy tính thực tế!

Vấn đề nằm ở văn hóa của ngành lý thuyết khoa học máy tính: họ chủ động khuyến khích việc không chạy thuật toán trên máy tính. Việc viết bài báo khẳng định một thuật toán tồn tại mà không bao giờ viết ra mã nguồn là điều được chấp nhận. Lý thuyết khoa học máy tính đã trở thành một dạng toán học không còn bận tâm đến máy tính.

AI khuếch đại những thói quen xấu của giới học thuật

Điểm đáng chú ý nhất trong phân tích của Recht là cách AI đang khuếch đại các vấn đề cố hữu của giới học thuật:

• AI rất giỏi tự động hóa những xu hướng tồi tệ nhất của chúng ta
• Nó khuếch đại các thực hành văn hóa không được ai ưa nhưng không cá nhân nào dám đi ngược
• Nó khai thác các truyền thống máy móc khó thay đổi bằng hành động tập thể
• Theo cách đó, AI giờ đây có thể viết ra những bài báo lý thuyết vô dụng

Tuy nhiên, có thể chính trong sự phi lý của kho bài chứng minh hỗn độn mà OpenAI công bố, cộng đồng có thể cùng nhìn lại và nhận ra rằng đã đến lúc nên làm điều gì đó khác.

Ý nghĩa cho cộng đồng công nghệ Việt Nam

Với các kỹ sư và nhà phát triển phần mềm tại Việt Nam, câu chuyện này mang lại một bài học thực tiễn: đừng nhầm lẫn giữa cải tiến lý thuyết và cải tiến thực tế. Khi đánh giá một thuật toán hay một thư viện mới, điều quan trọng không chỉ là độ phức tạp lý thuyết mà còn là hằng số ẩn, mô hình tính toán giả định và khả năng triển khai trên phần cứng thực tế.

Trong bối cảnh làn sóng AI đang tạo ra ngày càng nhiều kết quả nghiên cứu được công bố với tốc độ chóng mặt, việc phân biệt đâu là đóng góp thực chất và đâu chỉ là sản phẩm của các mô hình ngôn ngữ lớn trở nên quan trọng hơn bao giờ hết.