THUẬT TOÁN NÀO CHO DỮ LIỆU NÀO?
Florent Krzakala, Đại học Sorbonne, và
Lenka Zdeborová, CNRS
Làm thế nào để tìm kiếm thông tin thích đáng trong một tập hợp lớn các dữ liệu thoạt nhìn có vẻ lộn xộn? Vấn đề nan giải này, mang tính quyết định trong thời đại của dữ liệu lớn, được nhìn nhận theo một cách mới, nhờ sự tương tự với các giai đoạn chuyển pha, được nghiên cứu trong vật lý thống kê.
Một phần quan trọng của thế giới chúng ta bị các thuật toán chi phối, thứ đang kiểm soát những cơ sở hạ tầng lớn và đưa ra những quyết định tối ưu. Tuy nhiên, những lý do cơ bản cho sự thành công của chúng ngày càng bí ẩn, khi nhiệm vụ, mà các thuật toán này phải hoàn thành, ngày càng trở nên phức tạp hơn, đặc biệt trong lĩnh vực trí tuệ nhân tạo (AI). Chúng ta cũng đang bước vào một kỷ nguyên mà những phương pháp phát hiện bằng thuật toán, từ một lượng lớn các dữ liệu, chắc chắn sẽ đóng một vai trò trội nhất trong các khám phá khoa học. Nhưng chúng ta cần phải có một lượng dữ liệu lớn cỡ nào để tìm ra một cách hiệu quả một tín hiệu thích đáng trong một tập hợp lớn các dữ liệu thoạt nhìn có vẻ hỗn độn? Câu hỏi này về tính phức hợp của thuật toán nằm ở trung tâm của lý thuyết phức hợp tính toán.
Mục đích của lí thuyết trên là nghiên cứu số lượng những nguồn lực (thời gian, không gian, bộ nhớ...) cần thiết để thuật toán có thể vận hành một cách trơn tru. Tuy nhiên, theo lý thuyết này, chúng ta không giải quyết được hầu hết những vấn đề hiện đại của dữ liệu lớn! Chúng thuộc nhóm được gọi là NP-khó và lý thuyết cho chúng ta biết rằng việc trích xuất một tín hiệu trong tình huống nhiễu, khi đó sẽ rất khó như việc mò kim (tín hiệu) dưới đáy biển (dữ liệu). Tuy nhiên, các ứng dụng của tin học hiện đại thường giải quyết một cách hiệu quả những vấn đề thuộc nhóm NP-khó trên quy mô lớn. Đó là trường hợp, ví dụ, của các hệ thống nhận dạng giọng nói hoặc hệ thống nhận dạng hình ảnh trong lĩnh vực trí tuệ nhân tạo. Các thuật toán này sử dụng những mạng lưới nơron nhân tạo, giúp tối ưu hóa, một cách hiệu quả, những chức năng rất phức tạp với hàng triệu biến số.
Sự phát hiện các cộng đồng
Nghịch lý này phát sinh từ đâu? Lý thuyết phức hợp cổ điển dựa trên một cách tiếp cận được gọi là “tồi tệ”. Nó xếp loại độ khó của các tác vụ thuật toán theo những gì có thể xảy ra một cách khó nhất. Nhưng một tác vụ có thể khó trong trường hợp tồi tệ nhất, nhưng lại dễ trong thực hành: ví dụ, nếu khó để mò kim đáy biển “trong trường hợp tồi tệ nhất” (với một biển cả mênh mông và một cây kim nhỏ xíu), thì vấn đề có thể dễ hơn nếu cây kim có kích thước đủ lớn.
Vậy, liệu chúng ta có thể phát triển một lý thuyết phức hợp về thuật toán thích hợp hơn, cho phép giải thích việc giải quyết những vấn đề đó hay không? Một số hành vi phức tạp trong vật lý thống kê, tương đương về mặt toán học với những hành vi được quan sát trong những dữ liệu thống kê ở quy mô lớn và có thể giúp chúng ta làm được điều đó.
 |
| Ernst Ising (1900-1998) |
 |
| Renfrey Potts (1925-2005) |
Một ví dụ cổ điển là ví dụ về phương hướng của các cộng đồng trong một đô thị. Hãy tưởng tượng có hai nhóm người (A và B) mà các thành viên có xu hướng giao du thường xuyên hơn với những người thuộc nhóm của mình. Nếu đưa cho chúng tôi một danh sách những cặp quen biết nhau, thì chúng tôi có nhiều khả năng lập lại được một danh sách những người thuộc nhóm A và những người thuộc nhóm B. Vấn đề này, xuất hiện hơn bốn mươi năm trước trong khuôn khổ các nghiên cứu về xã hội học, tương đương về mặt toán học với mô hình nghiên cứu nhiệt động lực học của các vật liệu composite, được nhà vật lý học người Đức Ernst Ising phát minh vào năm 1920 và được nhà toán học người Úc Renfrey Potts hoàn thiện vào năm 1951. Trong các vật liệu như vậy, những nguyên tử giống nhau cũng đều có xu hướng được kết nối và những phương trình để xử lý trong hai mô hình đều gần giống nhau. Tuy nhiên, các mục tiêu thì khác nhau: trong khi trong khoa học dữ liệu, các mô hình được sử dụng để hướng dẫn việc thiết kế các thuật toán, thì trong vật lý học, các mô hình được nghiên cứu theo một lăng kính mang tính học thuật nhiều hơn. Đặc biệt, vật lý thống kê thường xử lý các giai đoạn chuyển pha. Tuy nhiên, sự tương ứng giữa các giai đoạn vật lý (chất lỏng, chất lỏng chậm đông hay thủy tinh, chất rắn) và những miền các tham số mà một nhiệm vụ phân tích dữ liệu cụ thể là điều bất khả, khó hoặc đơn giản, về mặt thuật toán, sẽ cho phép hiểu được những giới hạn của các tham số mà một vấn đề dễ giải quyết trở thành một vấn đề khó giải quyết, thậm chí không thể giải quyết được.
▲ Tương tự, khi một chất lỏng thay đổi trạng thái một cách đột ngột theo nhiệt độ, thì một vấn đề về thuật toán sẽ đột nhiên trở nên dễ giải quyết hơn hoặc khó giải quyết hơn tùy thuộc vào lượng thông tin có sẵn.
Bằng cách sử dụng phép loại suy này, chúng tôi đã chỉ ra rằng, việc tìm các cộng đồng trong một tập hợp lớn các dữ liệu, vượt quá một ngưỡng được thể hiện dưới dạng nhiễu trong các dữ liệu (ví dụ, khi những sai sót về đo lường cho ra quá nhiều mối quan hệ giữa những người thuộc những nhóm rõ ràng khác biệt nhau) và trong số lượng các dữ liệu, thì có nhiều khả năng tìm thấy các cộng đồng[1]. Nhưng nếu tình trạng nhiễu ở mức độ đủ thấp, thì chúng tôi có thể phát triển một phương pháp cho phép phát hiện các cộng đồng, theo cách rất gần với một mức tối ưu có thể tính toán được. Giữa hai ngưỡng này, vì vậy, có một pha “cứng”, mà chúng tôi không biết được thuật toán hiệu quả. Công việc của chúng tôi là tìm ra một ma trận – một bảng điểm số – mà nghiên cứu cho phép phát triển một thuật toán hiệu quả cho nhiệm vụ phát hiện các cộng đồng này. Điều đáng ngạc nhiên là, sau khi đã giới thiệu ma trận này, các đồng nghiệp toán học đã chứng minh kết quả của chúng tôi, một cách chặt chẽ, và đã sử dụng kết quả đó để giải quyết một vấn đề mở về toán học về sự tồn tại của những ma trận cụ thể (ma trận Ramanujan)[2]. Sự tương tác giữa các nhà vật lý học, nhà thống kê học, nhà xác suất học và nhà toán học, vì vậy, đã mang lại những thành quả đặc biệt. Ngoài việc cung cấp nguồn cảm hứng cho các nhà toán học, nó còn giúp nắm bắt những khả năng, đồng thời những hạn chế của các số liệu thống kê hiện đại[3]. ■
Bối cảnh
Để trích xuất những định luật có thể kiểm chứng được, cho đến giờ, người ta đề xuất một mô hình có thể so sánh tiếp với dữ liệu. Sự xuất hiện của dữ liệu lớn đã lật ngược phương pháp: chúng tôi tìm cách trích xuất thông tin thích đáng trực tiếp từ dữ liệu. Chúng ta có thể sử dụng thuật toán hiệu quả nào để sử dụng vì mục đích này?
Giáo sư và nhà nghiên cứu
 |
| Florent Krzakala |
 |
| Lenka Zdeborová |
Giảng viên tại Đại học Sorbonne, Florent Krzakala làm việc tại trường Ecole normale supérieure (ENS) ở Paris. Ông là trưởng bộ môn Mô hình và Khoa học Dữ liệu tại ENS, được tài trợ bởi quỹ Capital Fund Management.
Lenka Zdeborová, nhà nghiên cứu tại CNRS, làm việc tại Viện Vật lý lý thuyết của CEA ở Saclay.
Để biết thêm
Tạp chí LaRecherche đã xuất bản
- Hồ sơ “La théorie de la complexité [Lý thuyết phức hợp]”, số 464, tháng 5 năm 2012.
- Số đặc biệt “Vaincre les épidémies [Chiến thắng dịch bệnh]”, số 19, tháng 10 năm 2016.
Đọc thêm
- Pablo Jensen, Pourquoi la société ne se laisse pas mettre en équations [Tại sao xã hội không chịu bị biến thành các phương trình], Seuil, 2018.
- Marc Barthelemy, The Structure and Dynamics of Cities [Cấu trúc và Động lực của các thành phố], Cambridge University Press, 2016.
- D. Sornette, “Physics and Financial Economics (1776-2014): Puzzles, Ising and Agent-based Models [Vật lý học và kinh tế học tài chính (1776-2014): Câu đố, Các mô hình Ising và mô hình dựa vào tác nhân]”, Rep. Prog. Phys., 77, 062001, 2014.
- Jean-Paul Delahaye, Complexité aléatoire et complexité organisée [Sự phức hợp ngẫu nhiên và sự phức hợp có tổ chức], Quæ, 2009.
- Eugène Angelier, Les Sciences de la complexité et le vivant [Khoa học phức hợp và con người], Lavoisier-Tec và Doc, 2008.
Trên mạng
- iscopif.fr
Trang web của Viện nghiên cứu các Hệ thống phức hợp, Paris Ile-de-France.
- www.santafe.edu
Viện nghiên cứu đầu tiên chuyên ngành khoa học phức hợp, tại Santa Fe, Hoa Kỳ.
- tinyurl.com/Theraulaz
Cách thức nhóm của Guy Theraulaz nghiên cứu và mô hình hóa các tổ kiến.
- politoscope.org
Những công cụ để nghiên cứu sự hình thành các cộng đồng chính trị thông qua các mạng xã hội.
- epicx-laboratoire.com/outreach.html
Trang web của Phòng thí nghiệm dịch tễ trong môi trường phức hợp (EPIcs), do Vittoria Coliza quản lý.
- digitalepidemiologylab.org
Nhóm dịch tễ học kỹ thuật số tại EPFL sử dụng dữ liệu từ các mạng xã hội để mô hình hóa sự phát triển của dịch bệnh.
- tinyurl.com/MparkAutomCel
Hội thảo toán học Mathematic Parc về các tế bào ô-tô-mát, của Irène Marcovici, thuộc Đại học Lorraine.
- tinyurl.com/KrzakalaPhysSta
Hội thảo của Florent Krzakala về vật lý thống kê và xử lý tín hiệu.
Huỳnh Thiện Quốc Việt dịch
Nguồn: Quels algorithmes pour quelles données?, trong nguyệt san số 537 [La Recherche], tháng 7-8 năm 2018.
Chú thích:
[1] L. Zdeborová và F. Krzakala, Adv. Trong Phys., 65, 453, 2016.↩
[2] C. Bordenave và cộng sự, Ann. Probab., 46, 1, 2018.↩
[3] AS Bandeira và cộng sự, Arxiv: 1803. 11132, 2018.↩
