Cách nhà nghiên cứu AI tại Google giải mã bài toán họ tập hợp hóc hại bị bỏ ngỏ nửa thế kỷ

1. Giả thuyết Frankl: Câu đố nửa thế kỷ về họ tập hợp đóng đối với phép hợp

Trong toán học tổ hợp, có những bài toán mang lớp áo mộc mạc tới mức một học sinh trung học cũng hiểu ngay đề bài, nhưng lại đủ sức giam cầm những bộ óc kiệt xuất nhất suốt nhiều thập kỷ. Giả thuyết họ tập hợp đóng đối với phép hợp (union-closed sets conjecture) là một câu đố điển hình như thế. Hơn 40 năm trôi qua kể từ ngày ra đời, nó đứng vững như một pháo đài bất khả xâm phạm trước mọi mũi tấn công của giới nghiên cứu lý thuyết.

Để hình dung bài toán, hãy bắt đầu từ nền tảng quen thuộc: các tập hợp chứa những con số, chẳng hạn $\{1, 2\}$ hay $\{2, 3, 4\}$. Phép toán trọng tâm ở đây là phép hợp (union) — tức gom toàn bộ phần tử của các tập hợp lại với nhau mà không tính phần tử trùng lặp. Ví dụ, khi hợp hai tập hợp $\{1, 2\}$ và $\{2, 3, 4\}$, ta sẽ thu được $\{1, 2, 3, 4\}$.

Một bộ sưu tập (hay “họ”) các tập hợp được gọi là “đóng đối với phép hợp” nếu hợp của bất kỳ hai tập hợp nào trong họ cũng cho ra một tập hợp đã nằm sẵn trong họ đó. Chẳng hạn, hãy xem xét họ gồm 4 tập hợp sau:

$$ \{1\}, \{1, 2\}, \{2, 3, 4\}, \{1, 2, 3, 4\} $$

Dù ghép đôi hai tập hợp bất kỳ nào trong 4 tập hợp trên rồi lấy hợp, kết quả vẫn luôn thuộc về chính họ này. Do đó, đây là một họ đóng đối với phép hợp hoàn chỉnh.

Những thảo luận sơ khai về cấu trúc này manh nha từ thập niên 1960, nhưng bài toán chỉ thực sự thành hình vào năm 1979 qua bài báo của Péter Frankl — nhà toán học người Hungary, người sau này sang Nhật Bản định cư vào thập niên 1980 và có niềm đam mê biểu diễn xiếc đường phố. Frankl dự đoán rằng: Mọi họ tập hợp hữu hạn đóng đối với phép hợp đều bắt buộc phải chứa ít nhất một phần tử xuất hiện trong tối thiểu 50% số tập hợp của họ đó.

Mốc 50% được xem là dự đoán tự nhiên nhất vì hai lý do:

• Có sẵn những cấu trúc đối xứng mẫu mực: Điển hình là họ gồm 1024 tập con tạo từ các số từ 1 đến 10. Họ này đóng đối với phép hợp, và mỗi số trong 10 số đều góp mặt ở đúng 512 tập hợp (chính xác 50%).
• Chưa từng xuất hiện phản ví dụ: Suốt từ năm 1979, không ai tìm ra được bất kỳ họ tập hợp đóng nào vi phạm quy tắc này.

Tuy vậy, việc linh cảm điều gì đó đúng đắn khác xa với việc chứng minh nó. Trong nhiều thập kỷ, tiến triển gần như bằng không. Các nghiên cứu trước đây chỉ đưa ra được các ngưỡng biến đổi phụ thuộc vào tổng số lượng tập hợp, chứ không tìm được một tỷ lệ phần trăm cố định cho mọi họ tập hợp bất kể quy mô lớn nhỏ.

Nhà toán học Will Sawin thuộc Đại học Columbia từng nhận định: “Bài toán tạo cảm giác dễ chịu và tương đồng với nhiều vấn đề đơn giản khác, nhưng trên thực tế nó đã đẩy lùi mọi nỗ lực công phá của giới toán học.”

Sự ngoan cố ấy khiến nhiều học giả chùn bước. Họ sợ phung phí nhiều năm sự nghiệp vào một câu hỏi quyến rũ nhưng dường như không lối thoát. Ký ức năm 2013 của một nghiên cứu sinh trẻ tại Đại học Rutgers đã minh chứng rõ điều này: khi anh bước vào phòng làm việc của Giáo sư Michael Saks và nhắc tới giả thuyết Frankl, vị giáo sư — người từng tiêu tốn bao tâm lực cho nó — đã suýt đuổi anh ra ngoài với lời thở dài: “Justin, cậu lại làm tôi phải nghĩ về bài toán quái ác ấy rồi, và tôi thì chẳng muốn thế chút nào đâu.” Chàng nghiên cứu sinh đó chính là Justin Gilmer.

2. Ngã rẽ công nghệ và cuộc hội ngộ bất ngờ tại Rutgers

Thời điểm năm 2013, Justin Gilmer gần như bị giả thuyết Frankl chi phối tâm trí. Suốt một năm trời, phần lớn thời gian của ông là tản bộ trên các con đường rợp bóng cây tại Rutgers, trăn trở tìm kiếm lời giải. Nhưng rốt cuộc, nỗ lực ấy chỉ đem lại một bài học duy nhất: thấu hiểu tường tận tại sao một bài toán nhìn qua có vẻ giản đơn lại sở hữu sức kháng cự ghê gớm đến vậy.

“Tôi nghĩ rất nhiều người đã vật lộn với bài toán này cho tới khi cảm thấy thỏa mãn vì đã hiểu tại sao nó lại hóc búa. Có lẽ tôi là người đã dành cho nó nhiều thời gian hơn đa số mọi người,” Gilmer nhớ lại.

Bảo vệ xong luận án Tiến sĩ toán vào năm 2015, Gilmer nhận ra mình không còn tha thiết với giảng đường hàn lâm. Ông tự học lập trình, rẽ hướng sang ngành công nghệ và trở thành nhà nghiên cứu học máy (machine learning) cùng trí tuệ nhân tạo (AI) tại Google. Toán lý thuyết dần trôi vào quên lãng.

Bảy năm sau, vào giữa tháng 10 năm 2022, Gilmer bay từ California sang New York dự đám cưới một người bạn. Tiện đường, ông ghé thăm Giáo sư Saks tại trường cũ Rutgers. Trong bữa trưa, hai thầy trò trò chuyện rôm rả nhưng tuyệt nhiên không đả động gì tới toán học. Gilmer hào hứng chia sẻ về công việc tại Google, về các mô hình học máy mà ông đang theo đuổi.

Sau bữa ăn, khi tản bộ dưới tiết trời thu nắng đẹp trên chính những lối đi mà 9 năm trước mình từng ôm nỗi ám ảnh thất bại, một tia sáng bất ngờ lóe lên trong đầu Gilmer. Không còn bị trói buộc bởi những công cụ tổ hợp truyền thống, ông chợt nảy ra ý tưởng: Liệu có thể dùng Lý thuyết thông tin (Information Theory) — ngành học vốn gắn liền với khoa học máy tính — để giải quyết bài toán năm xưa?

Trở về California, Gilmer âm thầm theo đuổi linh cảm này suốt một tháng. Ông làm việc cật lực vào các buổi tối sau giờ hành chính ở Google và tận dụng toàn bộ các ngày cuối tuần. Dù luôn chuẩn bị tâm lý cho thất bại, ông ngạc nhiên thấy các vướng mắc logic cứ liên tiếp được giải tỏa. Ngày 16 tháng 11 năm 2022, Gilmer công bố kết quả lên arXiv. Bài báo lập tức thổi bùng một làn sóng nghiên cứu sôi động tại Oxford, MIT, Viện IAS Princeton. Nhưng trước khi bắt tay đào sâu bài toán, các nhà toán học hàng đầu đều ngơ ngác đặt chung một câu hỏi: “Justin Gilmer này rốt cuộc là ai?”

3. Chiếc chìa khóa Entropy: Khi toán tổ hợp soi bóng qua lăng kính Claude Shannon

Ý tưởng của Gilmer bắt đầu từ một nghịch lý số học giản đơn. Giả sử bạn có một họ đóng đối với phép hợp gồm 100 tập hợp. Nếu bắt cặp hai tập hợp bất kỳ để lấy hợp, bạn có tới 4950 cặp khác nhau. Làm sao 4950 kết quả hợp ấy lại có thể rơi gọn gàng trở lại vào đúng 100 tập hợp ban đầu, trừ khi bên trong các tập hợp đó phải có những phần tử xuất hiện lặp lại với tần suất rất cao?

Để đo lường sự xuất hiện này, Gilmer đã viện tới Lý thuyết thông tin — lĩnh vực cung cấp công cụ toán học chuẩn xác để tính toán những gì diễn ra khi ta rút ngẫu nhiên các đối tượng.

Lý thuyết thông tin được Claude Shannon đặt nền móng qua bài báo kinh điển năm 1948 mang tên “A Mathematical Theory of Communication”. Shannon đã xây dựng phương pháp tính toán lượng thông tin cần thiết để truyền đi một thông điệp dựa trên độ bất định (uncertainty hay entropy) của thông điệp đó. Mối liên hệ khăng khít giữa lượng thông tin và độ bất định chính là cốt lõi trong tư tưởng của Shannon.

Hãy xem xét một ví dụ gần gũi về việc tung đồng xu 5 lần rồi truyền kết quả:

• Đồng xu cân bằng: Khả năng ngửa và sấp là 50-50. Kết quả mỗi lần tung hoàn toàn khó lường và chứa sự bất ngờ tối đa, đòi hỏi trọn vẹn 5 bit thông tin để truyền tải.
• Đồng xu lệch: Nếu đồng xu có tới 99% khả năng ngửa, sự bất ngờ biến mất. Hai bên có thể quy ước chỉ gửi 1 bit (ví dụ số 1) nếu đồng xu ra toàn mặt ngửa — điều gần như chắc chắn xảy ra.

Như vậy, biến cố càng khó đoán thì càng chứa nhiều thông tin; ngược lại, biến cố có xu hướng thiên lệch rõ ràng thì chứa ít thông tin hơn.

Quy luật này áp dụng hoàn hảo cho các họ tập hợp số. Với họ gồm 1024 tập hợp tạo từ các số từ 1 đến 10, nếu ta chọn ngẫu nhiên hai tập hợp rồi truyền đi danh sách phần tử của chúng, lượng thông tin cần dùng sẽ phản ánh độ bất định xem phần tử đó có mặt hay không. Chẳng hạn, nếu số 1 xuất hiện ở 50% số tập hợp, độ bất định của nó là cực đại, tương tự xác suất 50% mặt ngửa của đồng xu cân bằng.

Lý thuyết thông tin thỉnh thoảng vẫn được dùng trong toán tổ hợp — chuyên ngành Gilmer từng học thời nghiên cứu sinh. Dù vậy, trên chuyến bay về nhà, ông vẫn canh cánh nỗi lo rằng đây chỉ là sự ngây ngô của một người nghiệp dư: chắc hẳn các chuyên gia đã thử qua hướng đi này và thấy nó chỉ là một “món đồ chơi lấp lánh” vô dụng.

“Thú thật, tôi hơi ngạc nhiên vì trước đây chưa từng có ai nghĩ đến điều này,” Gilmer chia sẻ. “Nhưng có lẽ tôi không nên quá bất ngờ, bởi bản thân tôi cũng từng suy nghĩ về bài toán suốt một năm trời và vốn đã biết về lý thuyết thông tin từ trước đó.”

4. Chiến lược phản chứng: Mâu thuẫn thông tin lật đổ giả thiết ngược

Gilmer bắt tay vào nghiên cứu nhờ nguồn cảm hứng từ các cuộc thảo luận mở nhiều năm trước trên blog của nhà toán học Tim Gowers. Do đã rời xa toán thuần túy khá lâu, ông thậm chí phải vừa làm vừa mở cuốn giáo trình bên cạnh để ôn lại các công thức đã quên.

“Bạn hẳn sẽ nghĩ một người đưa ra kết quả lớn thì không cần phải giở lại Chương 2 của cuốn ‘Elements of Information Theory’, nhưng tôi đã phải làm đúng như thế đấy,” Gilmer hóm hỉnh kể lại.

Chiến lược chứng minh của Gilmer dựa trên phương pháp phản chứng. Ông giả định một tình huống ngược lại hoàn toàn: Tồn tại một họ tập hợp đóng đối với phép hợp mà không có bất kỳ phần tử nào xuất hiện trong dù chỉ 1% số tập hợp. Nếu ví dụ phản chứng này tồn tại, giả thuyết Frankl sẽ bị bác bỏ.

Bây giờ, giả sử ta chọn ngẫu nhiên hai tập hợp $A$ và $B$ từ họ này, rồi xem xét từng phần tử. Tỷ lệ để tập hợp $A$ chứa số 1 là bao nhiêu? Và tập hợp $B$ thì sao? Do mỗi phần tử chỉ có dưới 1% cơ hội xuất hiện, ta không kỳ vọng $A$ hay $B$ chứa số 1. Vì thế, mức độ bất ngờ — tức lượng thông tin thu được — là rất thấp khi biết cả hai tập hợp đều vắng bóng số 1.

Nhưng hãy xét xác suất để hợp của $A$ và $B$ (tức $A \cup B$) chứa số 1. Tỷ lệ này vẫn nhỏ, nhưng chắc chắn cao hơn xác suất số 1 có mặt trong từng tập hợp riêng lẻ. Con số này bằng tổng xác suất số 1 xuất hiện trong $A$ cộng xác suất xuất hiện trong $B$ rồi trừ đi xác suất xuất hiện ở cả hai tập hợp. Do đó, khả năng số 1 nằm trong phép hợp sẽ nhích lên xấp xỉ gần 2%.

Mức 2% tuy nhỏ nhưng đã nhích gần hơn về phía mốc 50-50 (nơi có độ bất định cao nhất). Điều này đồng nghĩa với việc ta cần nhiều thông tin hơn để thông báo kết quả đó. Tóm lại, nếu tồn tại họ tập hợp mà không phần tử nào đạt ngưỡng 1%, thì phép hợp của hai tập hợp sẽ chứa nhiều thông tin hơn bản thân từng tập hợp thành phần.

Ryan Alweiss từ Đại học Princeton nhận xét đầy thán phục: “Ý tưởng hé lộ từng phần tử một và đo lường lượng thông tin thu được là cực kỳ thông minh. Đó chính là linh hồn cốt lõi của bài chứng minh.”

Đến đây, Gilmer tung ra mắt xích then chốt: Ông chứng minh điều ngược lại, rằng trong bất kỳ họ đóng đối với phép hợp nào, hợp của hai tập hợp nhất thiết phải chứa ít thông tin hơn (hoặc bằng) so với các tập hợp ban đầu, chứ không bao giờ có thể chứa nhiều hơn!

Lý do bắt nguồn từ quy luật phân bố kích thước. Với họ 1024 tập con từ 1 đến 10, nếu chọn hú họa hai tập hợp, trung bình chúng có kích thước 5 phần tử (loại kích thước chiếm đa số với 252 tập hợp). Nhưng khi lấy hợp, kết quả thường phình to lên thành tập hợp khoảng 7 phần tử. Trong khi đó, số tập hợp chứa 7 phần tử chỉ có vẻn vẹn 120 tập hợp.

Trọng tâm ở chỗ: Độ bất định của hai tập hợp ban đầu lớn hơn nhiều so với độ bất định về hợp của chúng. Phép hợp luôn kéo lệch về phía các tập hợp có kích thước lớn hơn — nơi số lượng khả năng xảy ra lại ít hơn nhiều. Do đó, kết quả của phép hợp dễ đoán hơn (tựa như đồng xu bị lệch), đồng nghĩa với việc phép hợp chứa ít thông tin hơn các tập hợp tạo ra nó.

Như vậy, Gilmer đã dồn bài toán vào ngõ cụt phản chứng:

• Nếu không phần tử nào đạt ngưỡng 1%, phép hợp buộc phải chứa nhiều thông tin hơn.
• Nhưng cấu trúc toán học của họ đóng lại bắt buộc phép hợp phải chứa ít thông tin hơn.
• Mâu thuẫn không thể dung hòa!

Sự mâu thuẫn này chứng minh giả thiết phản chứng là sai lầm. Bắt buộc phải có ít nhất một phần tử xuất hiện trong tối thiểu 1% tổng số các tập hợp.

5. Cơn địa chấn arXiv và cuộc chạy đua chinh phục mốc 38%

Khi công bố chứng minh lên arXiv vào ngày 16 tháng 11 năm 2022, Gilmer có kèm một ghi chú rằng phương pháp của ông hoàn toàn có thể được tối ưu hóa bằng các công cụ giải tích để nâng ngưỡng chặn lên mức 38%, tiến gần hơn tới mốc 50% của Frankl.

Dự đoán ấy ứng nghiệm gần như ngay tức thì. Chỉ năm ngày sau, vào ngày 21 tháng 11, ba nhóm nghiên cứu độc lập từ các viện trường danh tiếng đã đồng loạt đăng tải các bài báo chỉ cách nhau vài giờ đồng hồ. Họ cùng dựa trên phương pháp lý thuyết thông tin của Gilmer để nâng ngưỡng lên xấp xỉ 38% (con số chính xác là $\frac{3 – \sqrt{5}}{2} \approx 38.2\%$). Dù chặng đường chạm tới 50% vẫn cần thêm những đột phá mới, làn sóng bùng nổ ban đầu đã khai thác triệt để sức mạnh từ cách tiếp cận của Gilmer.

Nhiều người ngạc nhiên hỏi tại sao Gilmer không tự mình tính ra con số 38%. Câu trả lời của ông vô cùng chân thành: sau nhiều năm rời xa toán lý thuyết, ông đơn giản là đã quên mất một số kỹ thuật biến đổi giải tích phức tạp.

“Kiến thức của tôi đã hơi bị mai một, và thú thật là tôi bị mắc kẹt ở đoạn tính toán đó,” Gilmer chia sẻ. “Nhưng tôi rất hào hứng muốn xem cộng đồng toán học sẽ đưa kết quả này đi xa đến đâu.”

6. Lăng kính liên ngành: Khi tư duy AI phá vỡ điểm nghẽn toán học lý thuyết

Dưới góc nhìn của chính Gilmer, việc rời bỏ nghiên cứu thuần túy để làm việc trong ngành học máy không phải là quãng thời gian ngắt quãng vô ích, mà ngược lại chính là chìa khóa then chốt dẫn tới thành công.

“Đó là cách duy nhất tôi có thể giải thích tại sao mình từng suy nghĩ về bài toán này suốt một năm thời nghiên cứu sinh mà không đạt tiến triển nào, rồi bỏ toán sáu năm, để rồi quay lại và tạo ra bước đột phá này,” Gilmer bộc bạch. “Tôi không biết giải thích thế nào khác ngoài việc tư duy làm việc trong ngành học máy đã tạo ra một góc nhìn mới lệch khỏi lối mòn trong suy nghĩ của tôi.”

Câu chuyện của Justin Gilmer không chỉ mang lại niềm phấn khích cho giới toán tổ hợp, mà còn là một minh chứng sống động cho giá trị của sự giao thoa liên ngành. Khi các nhà nghiên cứu đào quá sâu vào một lĩnh vực hẹp, họ rất dễ bị đóng khung trong những phương pháp truyền thống vốn đã chạm trần giới hạn. Bằng việc bước chân ra ngoài, tiếp cận các bài toán xác suất và tối ưu hóa trong học máy, Gilmer đã vô tình trang bị cho mình chiếc chìa khóa lý thuyết thông tin — thứ công cụ mà các nhà toán học thuần túy suốt nửa thế kỷ qua đã vô tình bỏ lỡ.

Bài viết tham khảo Quanta Magazine (quantamagazine.org).