Định lý không có bữa trưa miễn phí

Trong toán học dân gian,"định lý không có bữa trưa miễn phí"của David Wolpert và William G. 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").Wolpert, D.H., Macready, W.G. (1997),"No Free Lunch Theorems for Optimization", IEEE Transactions on Evolutionary Computation 1, 67. 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ê).Wolpert, David (1996),"The Lack of A Priori Distinctions between Learning Algorithms", Neural Computation, pp. 1341-1390.  

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".Wolpert, D.H., and Macready, W.G. (2005)"Coevolutionary free lunches", IEEE Transactions on Evolutionary Computation, 9(6): 721-735

Ví dụ

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:

 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
 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
 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
 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.

 Ghi chú 

 Liên kết ngoài 
 No Free Lunch Theorems
 Graphics illustrating the theorem

Thể loại:Khoa học dân gian
Thể loại:Triết học toán học
Thể loại:Định lý toán học