Khoa học máy tính: Các thuật toán cải thiện nhanh chóng như thế nào?

Các nhà khoa học của MIT cho thấy các thuật toán đang cải thiện nhanh như thế nào trên một loạt các ví dụ, chứng tỏ tầm quan trọng của chúng trong việc phát triển tính toán.

Các thuật toán giống như cha mẹ của một máy tính. Chúng cho máy tính biết cách hiểu thông tin để đến lượt chúng, chúng có thể tạo ra điều gì đó hữu ích từ nó.

Thuật toán càng hiệu quả thì máy tính càng phải làm ít công việc hơn. Đối với tất cả các tiến bộ công nghệ trong phần cứng máy tính và tuổi thọ còn nhiều tranh cãi của Định luật Moore, hiệu suất máy tính chỉ là một mặt của bức tranh.

Ở hậu trường, xu hướng thứ hai đang diễn ra: Các thuật toán đang được cải thiện, do đó, cần ít sức mạnh tính toán hơn. Mặc dù hiệu quả của thuật toán có thể ít được chú ý hơn, nhưng bạn chắc chắn sẽ nhận thấy nếu công cụ tìm kiếm đáng tin cậy của bạn đột nhiên trở nên nhanh bằng 1/10 hoặc nếu việc di chuyển qua các tập dữ liệu lớn giống như lội qua bùn.

Điều này khiến các nhà khoa học từ Phòng thí nghiệm Khoa học Máy tính và Trí tuệ Nhân tạo (CSAIL) của MIT đặt câu hỏi: Các thuật toán cải tiến nhanh như thế nào?

Dữ liệu hiện có về câu hỏi này chủ yếu là giai thoại, bao gồm các nghiên cứu điển hình về các thuật toán cụ thể được cho là đại diện cho phạm vi rộng hơn. Đối mặt với sự khan hiếm bằng chứng này, nhóm đã bắt đầu thu thập dữ liệu từ 57 sách giáo khoa và hơn 1.110 tài liệu nghiên cứu, để theo dõi lịch sử khi nào các thuật toán trở nên tốt hơn. Một số bài báo nghiên cứu đã trực tiếp báo cáo các thuật toán mới tốt như thế nào và những bài báo khác cần được các tác giả xây dựng lại bằng cách sử dụng “mã giả”, phiên bản viết tắt của thuật toán mô tả các chi tiết cơ bản.

Tổng cộng, nhóm đã xem xét 113 “họ thuật toán”, tập hợp các thuật toán giải quyết cùng một vấn đề đã được sách giáo khoa khoa học máy tính đánh dấu là quan trọng nhất. Đối với mỗi 113, nhóm đã xây dựng lại lịch sử của nó, theo dõi mỗi khi một thuật toán mới được đề xuất cho vấn đề và ghi chú đặc biệt về những thuật toán hiệu quả hơn. Hiệu suất khác nhau và cách nhau nhiều thập kỷ, bắt đầu từ những năm 1940 đến nay, nhóm nghiên cứu đã tìm thấy trung bình 8 thuật toán cho mỗi gia đình, trong đó một cặp đã cải thiện hiệu quả của nó. Để chia sẻ cơ sở dữ liệu tổng hợp kiến thức này, nhóm cũng đã tạo Algorithm-Wiki.org.

Các nhà khoa học đã lập biểu đồ về tốc độ cải thiện của các họ này, tập trung vào tính năng được phân tích nhiều nhất của các thuật toán – tốc độ mà họ có thể đảm bảo để giải quyết vấn đề (trong máy tính có thể nói: “độ phức tạp thời gian trong trường hợp xấu nhất”). Những gì nổi lên là khả năng biến đổi rất lớn, nhưng cũng là những hiểu biết quan trọng về cách cải tiến thuật toán biến đổi đối với khoa học máy tính.

Đối với các vấn đề máy tính lớn, 43 phần trăm họ thuật toán đã có những cải tiến hàng năm bằng hoặc lớn hơn những lợi ích được cho là nhiều từ Định luật Moore. Trong 14 phần trăm các vấn đề, sự cải thiện hiệu suất từ các thuật toán vượt trội hơn rất nhiều so với những vấn đề đến từ phần cứng được cải tiến. Lợi ích từ cải tiến thuật toán đặc biệt lớn đối với các vấn đề dữ liệu lớn, vì vậy tầm quan trọng của những tiến bộ đó đã tăng lên trong những thập kỷ gần đây.

Sự thay đổi lớn nhất mà các tác giả quan sát được là khi một họ thuật toán chuyển từ độ phức tạp hàm mũ sang đa thức. Số lượng nỗ lực cần thiết để giải quyết một vấn đề theo cấp số nhân giống như một người cố gắng đoán một tổ hợp trên một ổ khóa. Nếu bạn chỉ có một mặt số 10 chữ số duy nhất, nhiệm vụ rất dễ dàng. Với bốn mặt số giống như một ổ khóa xe đạp, thật khó để không ai lấy trộm xe đạp của bạn, nhưng vẫn có thể tưởng tượng được rằng bạn có thể thử mọi cách kết hợp. Với 50, điều đó gần như không thể – sẽ mất quá nhiều bước. Các vấn đề có độ phức tạp theo cấp số nhân cũng giống như đối với máy tính: Khi chúng lớn hơn, chúng nhanh chóng vượt quá khả năng xử lý của máy tính. Việc tìm ra một thuật toán đa thức thường giải quyết được điều đó, giúp bạn có thể giải quyết các vấn đề theo cách mà không có cải tiến phần cứng nào có thể làm được.

Khi những lời bàn tán của Định luật Moore sắp kết thúc nhanh chóng lan tràn khắp các cuộc trò chuyện toàn cầu, các nhà nghiên cứu nói rằng người dùng máy tính sẽ ngày càng cần phải chuyển sang các lĩnh vực như thuật toán để cải thiện hiệu suất. Nhóm nghiên cứu cho biết những phát hiện xác nhận rằng trong lịch sử, lợi ích từ các thuật toán là rất lớn, vì vậy tiềm năng là có. Nhưng nếu lợi nhuận đến từ các thuật toán thay vì phần cứng, chúng sẽ trông khác. Việc cải tiến phần cứng từ Định luật Moore diễn ra suôn sẻ theo thời gian và đối với các thuật toán, lợi ích thu được thường lớn nhưng không thường xuyên.

Neil Thompson, một nhà khoa học nghiên cứu của MIT tại CSAIL và Trường Quản lý Sloan, đồng thời là tác giả cấp cao của bài báo mới cho biết: “Đây là bài báo đầu tiên cho thấy các thuật toán đang cải thiện nhanh như thế nào trong nhiều ví dụ. “Thông qua phân tích của mình, chúng tôi có thể nói có thể thực hiện thêm bao nhiêu tác vụ nữa bằng cách sử dụng cùng một lượng sức mạnh tính toán sau khi một thuật toán được cải thiện. Khi các vấn đề tăng lên đến hàng tỷ hoặc hàng nghìn tỷ điểm dữ liệu, cải tiến thuật toán trở nên quan trọng hơn đáng kể so với cải tiến phần cứng. Trong thời đại mà tác động môi trường của điện toán ngày càng đáng lo ngại, đây là một cách để cải thiện các doanh nghiệp và các tổ chức khác mà không có mặt trái. “

Tham khảo: “Các thuật toán cải thiện nhanh đến mức nào?” của Yash Sherry và Neil C. Thompson, ngày 20 tháng 9 năm 2021, Kỷ yếu của IEEE .
DOI: 10.1109 / JPROC.2021.3107219

Thompson đã viết bài báo cùng với sinh viên Yash Sherry đến thăm MIT. Bài báo được xuất bản trong Kỷ yếu của IEEE . Công việc này được tài trợ bởi Tides Foundation và MIT Initiative về nền kinh tế kỹ thuật số.

Theo Scitechdaily