Apple giới thiệu phương pháp Newton bán trơn giúp tăng tốc tính toán Optimal Transport

Tác giả: Tianyi Lin†, Marco Cuturi, Michael I. Jordan‡

Các bộ ước lượng vận chuyển tối ưu (OT) dựa trên kernel cung cấp một quy trình ước lượng hàm thay thế để giải quyết các bài toán OT từ dữ liệu mẫu. Các nghiên cứu gần đây cho thấy những bộ ước lượng này có hiệu quả thống kê cao hơn so với các bộ ước lượng OT dạng plug-in (dựa trên quy hoạch tuyến tính) khi so sánh các độ đo xác suất trong không gian nhiều chiều [Vacher và cộng sự, 2021]. Tuy nhiên, lợi ích thống kê đó lại đi kèm với chi phí tính toán rất đắt đỏ: do việc tính toán dựa trên phương pháp điểm trong bước ngắn (SSIPM), vốn đòi hỏi số lượng vòng lặp lớn trong thực tế, nên các bộ ước lượng này nhanh chóng trở nên không khả thi khi kích thước mẫu n tăng lên. Để mở rộng các bộ ước lượng này cho n lớn hơn, chúng tôi đề xuất một mô hình điểm cố định không trơn cho bài toán OT dựa trên kernel và chứng minh rằng nó có thể được giải quyết hiệu quả thông qua phương pháp Newton bán trơn (SSN) chuyên biệt: Bằng cách khai thác cấu trúc của bài toán, chúng tôi cho thấy chi phí mỗi vòng lặp khi thực hiện một bước SSN có thể được giảm đáng kể trong thực tế. Chúng tôi chứng minh rằng phương pháp SSN của mình đạt được tốc độ hội tụ toàn cục O(1/√k) và tốc độ hội tụ bậc hai cục bộ trong các điều kiện chính quy tiêu chuẩn. Chúng tôi cho thấy sự cải thiện tốc độ đáng kể so với SSIPM trên cả tập dữ liệu tổng hợp và dữ liệu thực tế.

Các tài liệu đọc thêm và cập nhật.

*Đóng góp ngang nhau

Hai hạn chế nổi bật từ lâu đã cản trở tính ứng dụng của các phương pháp vận chuyển tối ưu trong học máy. Thứ nhất, chi phí tính toán O(n³) của các bộ giải dựa trên mẫu tiêu chuẩn (khi sử dụng trên các lô gồm n mẫu) là quá lớn. Thứ hai, ràng buộc bảo toàn khối lượng khiến các bộ giải OT trở nên quá cứng nhắc trong thực tế: vì chúng phải khớp *tất cả* các điểm từ cả hai độ đo, nên đầu ra của chúng có thể bị ảnh hưởng nặng nề bởi…

Đọc thêm

Các nguyên lý khớp nối đằng sau vận chuyển tối ưu (OT) đang đóng vai trò ngày càng quan trọng trong học máy, một xu hướng có thể quan sát thấy khi OT được sử dụng để giải quyết sự mơ hồ của tập dữ liệu trong các ứng dụng (ví dụ: hệ gen học đơn bào) hoặc được sử dụng để cải thiện các phương pháp phức tạp hơn (ví dụ: cơ chế chú ý cân bằng trong các mô hình transformer hoặc học tự giám sát). Để mở rộng sang các bài toán thách thức hơn, ngày càng có sự đồng thuận rằng OT đòi hỏi các bộ giải có khả năng vận hành trên…

Đọc thêm