Định Lý Không Có Bữa Trưa Miễn Phí

Macready xuất hiện năm 1997 trong bài báo"Tối ưu các định lý không có bữa trưa miễn phí"(No Free Lunch Theorems for Optimization"). Trước đây, Wolpert kế thừa các định lý không có bữa trưa miễn phí dành cho học máy (suy luận thống kê).

Năm 2005, Wolpert và Macready đã chỉ ra định lý đầu tiên trong bài báo"tuyên bố rằng bất kỳ hai thuật toán tối ưu nào đều là tương đương khi hiệu suất của chúng đều là trung bình xuyên suốt trên tất cả các vấn đề có thể xảy ra".

Giả sử chúng ta có 2 ngày, mỗi ngày chỉ xuất hiện một dạng hình học: hình vuông hoặc hình tam giác. Theo đó, trong 2 ngày chúng ta có 4 kịch bản (lịch sử) có thể xảy ra như sau:

1. Kịch bản 1: (hình vuông, hình tam giác): ngày 1 là hình vuông, ngày 2 là hình tam giác
2. Kịch bản 2: (hình vuông, hình vuông): ngày 1 là hình vuông, ngày 2 là hình vuông
3. Kịch bản 3: (hình tam giác, hình tam giác): ngày 1 là hình tam giác, ngày 2 là hình tam giác
4. Kịch bản 4: (hình tam giác, hình vuông): ngày 1 là hình tam giác, ngày 2 là hình vuông

Mỗi kịch bản dự doán đều có xác suất bằng nhau, chính xác bằng 0.5. Nếu chúng ta dự đoán ngày 1 sẽ xuất hiện hình vuông, thì xác suất hình vuông xuất hiện ngày 1 là 0.5. Rõ hơn, chúng ta thấy kịch bản 1 và kịch bản 2 đều là hình vuông, tức là có 2 kịch bản có hình vuông trong ngày 1. Tuy nhiên, kịch bản 3 và kịch bản 4 không phải là hình vuông mà là hình tam giác. Vì vậy, xác suất hình vuông xuất hiện ngày 1 là 2/4 = 0.5 với 4 là tổng các kịch bản có thể xảy ra.

Theo ví dụ này, định lý không có bữa trưa miễn phí cho thấy rõ hơn rằng hiệu suất của các thuật toán chỉ mang tính trung bình trên tất cả các khả năng có thể xảy ra, không có thuật toán nào tốt hơn thuận toán nào.

• No Free Lunch Theorems
• Graphics illustrating the theorem