Vài ví dụ về Nghịch lý Braess trong cuộc sống là gì?

Sự kỳ diệu ẩn chứa trong nghịch lý Braess (được đặt theo tên nhà toán học người Đức phát hiện ra điều này) là một trong những câu đố có vẻ như phi logic đấy. Trong một hệ thống khan hiếm tài nguyên có những người ích cố gắng tìm cách cực đại hóa mục đích cá nhân của mình thì - cứ thử nghĩ tới các xa lộ tắc nghẽn ở bất kỳ đô thị lớn nào trên thế giới mà xem - cắt giảm bớt sự lựa chọn của từng người có thể đưa ra được giải pháp với chi phí thấp hơn.

Giao thông tệ quá à? Cứ trách Nghịch lý Braess ấy
Thử tưởng tượng bạn là người quản lý vấn đề giao thông của một thành phố lớn - London, New York, Bắc Kinh hay New Delhi - thị trưởng mới đắc cử muốn thực hiện lời hứa giảm thiểu tắc nghẽn và đã cho bạn toàn quyền quyết định để có thể thay đổi thực trạng này. Ông hoặc bà ấy mời bạn vào văn phòng rồi nói: ông có thể dùng tới một tỷ đô la để tạo ra những con đường mới trong thành phố này. Chỉ cần nói cho tôi biết vị trí, cách thức và tôi sẽ rót tiền.

Trong hình ảnh có thể có: 3 người, mọi người đang cười, mọi người đang đứng

Hơi giật mình một xíu, bạn nói rằng có một định lý do cái ông làm toán người Đức nào đấy tên là Braess chỉ ra rằng thông thường, giải pháp tốt nhất khi có tắc nghẽn là đóng hẳn một vài con đường lại! Bạn thấy mặt thị trưởng hiện lên vẻ kinh hãi: ý ông là, ông muốn dừng một vài tuyến đường đang vận hành một cách hoàn hảo và giảm thiểu lựa chọn của mọi người để cải thiện vấn đề à. Bạn bảo: toán học đã nói như vầy!

Trước khi giải thích về nghịch lý đó thì, đã có nơi nào thực sự làm cách này chưa? Rồi, nhiều thành phố là khác. Seoul cho ngừng một xa lộ có lưu lượng giao thông rất lớn và rất ngạc nhiên là, tình trạng ách tắc được cải thiện.

Mayor Bloomberg, giờ là ứng cử viên tổng thống, đã thực hiện cách làm này khi ông ngăn một phần đường Broadway gần Quảng Trường Thời Đại, và biến nó trở thành phố đi bộ.
Tất nhiên, phần toán học đó hoàn toàn mang tính tổng quát, vì vậy, bài toán có thể ứng dụng ở nhiều lĩnh vực khác, bao gồm cả mạng xã hội nữa đấy.

Trước khi đào sâu vào kiến thức toán học, hãy xem một ví dụ cơ bản. Tôi sẽ lấy hình trong tài liệu của tôi tại hội nghị AAAI 2015 với chủ đề “Optimization to Equilibration: A New Foundation for AI in the 21st century”. (Từ tối ưu tới cân bằng: Nền tảng AI mới trong thế kỷ 21).

Đầu tiên thì, đây là một bức ảnh của Braess cùng Anna Nagurney, một management professor rất tài năng tại UMass, Amherst, cùng nghiên cứu sinh của cô, người đã dịch bài báo tiếng Đức của Braess sang tiếng Anh. Tôi hơi ngạc nhiên khi chưa từng có ai khác làm việc này.

Tôi đã tham dự một buổi xemina của Giáo sư Nagurney và dành nhiều giờ liền khám phá chủ để bất đẳng thức biến phân (variational inequalities - VI) cực kỳ hấp dẫn cùng nghiên cứu sinh trước đây của mình là Ian Gemp, giờ cậu ấy làm việc tại Google Deep Mind. Ian đã sử dụng sức mạnh của VI để khai phá các GAN (generative adversarial network - tạm dịch: mạng đối nghịch tạo sinh), một trong những mô hình hot nhất trong deep learning. Vì vậy, ta có một mối liên hệ đẹp đẽ giữa Braess và deep learning! Ấy là sức mạnh của toán học. Nó có thể kết nối những ý tưởng không liên quan lại với nhau.
Tôi sẽ sử dụng ví dụ trong cuốn sách của Anna Nagurney về kinh tế học mạng lưới (network economic), ví dụ này lấy VI để giải thích nghịch lý Braess. Slide này thuộc bài thuyết trình trong AAAI của tôi.

Trong hình ảnh có thể có: văn bản

Có hai xa lộ chạy từ Amherst tới Boston, và sự ứ tắc trong giao thông trên mỗi con đường là một hàm số của số lượng ô tô đang chạy trên mỗi đoạn đường: ví dụ, mức độ tắc trên đoạn “a” là 10 đơn vị thời gian trên mỗi chiếc ô tô đi qua nó trong từng khoảng thời gian. Mỗi người có thể lựa chọn xem nên đi đường nào, nhưng họ sẽ luôn đi con đường ngắn nhất. Vì vậy, giao thông sẽ phân bổ thế nào đây? Cứ thử nói trong ví dụ này nhé, mỗi phút cần 6 chiếc ô tô đi từ Amherst tới Boston. Bạn có thể dễ dàng chỉ ra rằng cân bằng lưu thoát (equilibrium flow) sẽ chia đôi hai con đường “a-c” và “b-d”.
Vậy nếu bạn thêm một con đường mới thì sao? Khả năng là nó sẽ cải thiện tình trạng tắc nghẽn đúng không. Cứ xem coi nào.

Thêm một con đường mới là “e” sẽ khiến tình trạng tắc nghẽn thêm tồi tệ! Mức độ ứ tắc tăng từ 83 lên 92 cơ đấy! Từ đó, bạn bắt đầu thấy được rằng việc giảm bớt con đường có thể tăng thêm tính hiệu quả, cũng như Seoul và New York đã khám phá được.
Giờ mới đến phần toán học sâu hơn này. VI là công cụ mạnh mẽ trong việc phân tích những trò chơi phức tạp như giao thông với hàng trăm ngàn người quá yêu bản thân mình đang tìm cách cạnh tranh lẫn nhau. Hình thức ấy có thể áp dụng cho bất kỳ mạng lưới nào trong đó mọi thứ di chuyển từ đầu này tới đầu kia và mỗi đỉnh có thể đại diện cho từng đối tượng đang cạnh tranh với nhau. Nagurney đã phát triển ra mô hình hấp dẫn liên quan tới việc phân phối nội dung trên Internet, và Ian đã nghiên cứu đưa ra được một thuật toán rất đẹp để giải thật hiệu quả.

Image result for nghịch lý Braess

Và bạn có những nhà cung cấp dịch vụ đỉnh cao như Netflix, Amazon, Hulu, vv. Họ cạnh tranh nhau gửi cho bạn những nội dung video, nhưng họ cần phụ thuộc vào những đơn vị vận chuyển, cứ nghĩ tới AT&T, Verizon, vv để chuyển thông tin đó tới bạn. Đơn vị vận chuyển cũng cạnh tranh với chính mình nữa. Dưới cùng là các khách hàng, bạn và tôi, luôn luôn lựa chọn giữa nội dung và nhà cung cấp. Nghịch lý Braess cũng có thể áp dụng ở đây đó!
Ta có thể hiểu được vẻ đẹp của toán học ẩn chưa sau VI như thế nào? Rất cần lưu ý là, bạn không thể dễ dàng phát biểu những vấn đề đó dưới dạng bài toán tối ưu được. Những nhà nghiên cứu AI và ML rất thích tối ưu và cho rằng nó cực kỳ mạnh mẽ đấy, vì vậy họ đã sốc khi tận mắt chứng kiến là tối ưu cũng có những giới hạn nhất định. Nói ngắn gọn nhất, trong các vấn đề về kinh tế học mạng lưới, các ma trận Jacobi và Hess là bất đối xứng, và từ đó tính hội tụ của nhiều phương pháp tối ưu đã không còn nữa.

VI cực kỳ hiệu quả trong trường hợp không có hàm mục tiêu, ví dụ như các mô hình GAN, và từ đó ta có các bài toán về điểm yên ngựa (saddle point). Trong trường hợp tốt nhất chúng có thể được coi như các bài toán trường vectơ không bảo toàn, và không tương ứng với gradient của một hàm khả vi nào đấy. Trong những bài toán về cân bằng như vầy, nếu đi theo hướng gradient, ta sẽ sai lầm hoàn toàn. Thực tế thì, bạn nên đi theo hướng trực giao với hướng của gradient cơ!
Để có thể cho bạn nhiều chi tiết khai mở hơn, tôi sẽ trích ra bài báo nghiên cứu sinh của tôi viết, Ian Gemp, cậu ấy đã phát triển được một số thuật toán trường vectơ rất ngầu cho các GAN.

Bài học ở đây là, sự khai mở lớn lao tiếp theo trong AI và ML có thể tới từ những nguồn khá bất ngờ đấy. Hãy học một lớp nào đó ngoài khoa học máy tính mà xem. Anna Nagurney đã thay đổi toàn bộ tầm nhìn về AI của tôi. Bà đã cho ta thấy rằng sự khai mở có thể tới từ những nơi ít ngờ nhất. Thấu hiểu sự tắc nghẽn giao thông cũng có thể rất hữu ích đối với việc phát triển các thuật toán deep learning mới. Ai mà ngờ được cơ chứ?

xem thêm tại ca cuoc bong da:

Game ăn tiền

Ads

Monday, March 9, 2020

Vài ví dụ về Nghịch lý Braess trong cuộc sống là gì?

No comments:

Post a Comment

I Am The Author

Popular

Like Us