Đị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").[1] 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ê).[2]

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".[3]

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:

  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.[4]

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ú

  1. ^ Wolpert, D.H., Macready, W.G. (1997),"No Free Lunch Theorems for Optimization", IEEE Transactions on Evolutionary Computation 1, 67.
  2. ^ Wolpert, David (1996),"The Lack of A Priori Distinctions between Learning Algorithms", Neural Computation, pp. 1341-1390. Lưu trữ 2016-12-20 tại Wayback Machine
  3. ^ Wolpert, D.H., and Macready, W.G. (2005)"Coevolutionary free lunches", IEEE Transactions on Evolutionary Computation, 9(6): 721-735
  4. ^ Forster, Malcolm R. (1999). Minds and Machines. 9 (4): 543–564. doi:10.1023/A:1008304819398. |title= trống hay bị thiếu (trợ giúp)

Liên kết ngoài

Read other articles:

Chevy Chase

Chevy Chase Cornelius Crane Chevy Chase (lahir 8 Oktober 1943) merupakan seorang aktor, komedian, dan penulis berkebangsaan Amerika Serikat yang memenangkan nominasi Emmy Award. Dia dilahirkan di New York City. Dia berkarier di dunia film sejak tahun 1968. Filmografi Film Tahun Judul Peran Keterangan 1968 Walk... Don't Walk Pedestrian Short film 1974 The Groove Tube The Fingers/Geritan/Four Leaf Clover 1976 Tunnel Vision Himself 1978 Foul Play Tony Carlson Nominated—Golden Globe Award for B...

 

Petualangan Hachi si Lebah Madu

Petualangan Hachi si Lebah MaduBerkas:The Adventures of Hutch the Honeybee.jpgCuplikan pada serial televisi昆虫物語 みなしごハッチ(Konchū Monogatari Minashigo Hatchi)GenrePetualangan Seri animeSutradaraIppei KuriProduserTatsuo YoshidaSkenarioJinzo ToriumiMusikNobuyoshi NishibeStudioTatsunoko ProductionsSaluranasli Fuji Television TV7 (2002-2004), Spacetoon (2005-2011), RTV (23 Juni 2018-sekarang)Tayang 7 April 1970 – 8 September 1971Episode91[1] (Daftar episode)  Po...

 

Malindi

MalindiMunisipalitasPilar Vasco da GamaNegara KenyaKabupatenKabupaten KilifiDidirikanAbad ke 13 – 14Dimukimkan kembali1861Populasi (2009) • Total207.253 [1]Zona waktuUTC+3 (WAT) Pemandangan kota lama Malindi Malindi (sempat disebut sebagai Melinde) adalah sebuah kota di Teluk Malindi, mulut Sungai Galana, pesisir Samudera Hindia, Kenya. Kota tersebut berjarak 120 kilometer dari timur laut Mombasa. Populasi Malindi sebesar 207,253 menurut sensus 2009.[1]...

العلاقات الصربية الليتوانية

العلاقات الصربية الليتوانية صربيا ليتوانيا   صربيا   ليتوانيا تعديل مصدري - تعديل   العلاقات الصربية الليتوانية هي العلاقات الثنائية التي تجمع بين صربيا وليتوانيا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارن...

 

Mauritania

Untuk kerajaan kuno, lihat Mauretania. Artikel ini bukan mengenai Mediterania atau Mauritius. Republik Islam Mauritaniaالجمهورية الإسلامية الموريتانيةAl-Jumhūrīyah al-Islāmīyah al-Mūrītānīyah (Arab)République Islamique de Mauritanie (Prancis) Bendera Lambang Semboyan: شرف, إخاء, عدل (Arab: Kehormatan, Persaudaraan, Keadilan)Lagu kebangsaan: نشيد وطني موريتانيNašid Waṭanī Mūrītāniyy Perlihatkan BumiPerlihatkan pet...

 

Pembagian administratif Taiwan

Peta administrasi Republik Tiongkok secara konstitusional Republik Tiongkok di Taiwan sekarang ini masih mengklaim seluruh daratan Tiongkok sebagai wilayah negara mereka. Namun secara de-facto, wilayah di bawah administrasi Republik Tiongkok hanya pulau Taiwan, Pescadores, Quemoy dan Matsu. Administrasi tingkat satu dan dua Taipei Taipei Baru Keelung Taoyuan Hsinchu Kota Hsinchu Miaoli Taichung Changhua Penghu Nantou Yunlin Chiayi Kota Chiayi Tainan Kaohsiung Pingtung Yilan Hualien Taitung Pr...

Rudy Larriva

American animator and director Rudy LarrivaRudy Larriva, American animator.BornRudolph Larriva(1916-02-12)February 12, 1916El Paso, Texas, U.S.DiedFebruary 19, 2010(2010-02-19) (aged 94)Irvine, California, U.S.OccupationAnimator/Film directorYears active1939–1986Children1Signature Rudolph Larriva (February 12, 1916 – February 19, 2010) was an American animator and director from the 1940s to the 1980s. Early life Born in El Paso, Texas, which his parents moved out at the age ...

 

Evrytania

Regional unit in Central Greece, GreeceEvrytania Περιφερειακή ενότηταΕυρυτανίαςRegional unitMunicipalities of EvrytaniaEvrytania within GreeceCoordinates: 39°0′N 21°40′E / 39.000°N 21.667°E / 39.000; 21.667CountryGreeceRegionCentral GreeceCapitalKarpenisiArea • Total1,868 km2 (721 sq mi)Population (2011) • Total20,081 • Density11/km2 (28/sq mi)Time zoneUTC+2 • ...

 

Islam dan perang

Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia.Bantulah untuk mengembangkan artikel ini. Jika tidak dikembangkan, artikel ini akan dihapus pada 11 Maret 2024. Artikel atau bagian mungkin perlu ditulis ulang agar sesuai dengan standar kualitas Wikipedia. Anda dapat membantu memperbaikinya. Halaman pembicaraan dari artikel ini mungkin berisi beberapa saran. Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan....

Latium adiectum

View of Fondi, ancient Fundi, at the foot of the Monti Aurunci in Latium adiectum. The flat country is reclaimed marshland, similar to but not part of the Agro Pontino. It is now called the South Pontino. The Via Appia went through this region on its way south to Campania, which is located beyond the mountains seen in the distance. Latium adiectum (transl. attached Latium) or Latium Novum was a region of Roman Italy between Monte Circeo and the river Garigliano, south of and immediately...

 

USC Trojans men's volleyball

American college volleyball team USC Trojans men's volleyballUniversityUniversity of Southern CaliforniaHead coachJeff Nygaard (1st season)ConferenceMPSFLocationLos Angeles, CaliforniaHome arenaGalen Center (capacity: 10,258)NicknameTrojansColorsCardinal and gold[1]   NCAA Tournament champion1977, 1980, 1988, 1990NCAA Tournament runner-up1979, 1981, 1985, 1986, 1987, 1991, 2009, 2012NCAA Tournament appearance1982, 2011Conference tournament champion1991, 2...

 

Réseau hydrographique de l'Indre

Réseau hydrographique de l'Indre Localisation du département de l'Indre sur la carte des bassins hydrographiques français. Géographie Pays France Région Centre-Val de Loire Département Indre Bassins Bassins hydrographiques Loire-Bretagne Sous-bassins DCE Loire moyenne Vienne - Creuse Caractéristiques Principaux cours d'eau Cher, Indre, Creuse, Gartempe, Arnon, Anglin, Claise, Bouzanne et Benaize. Longueur totale 3 000 km Cours eau > 50km 14 Cours eau > 10km 73 Planification SDAG...

Long Shot (Kelly Clarkson song)

Song by Kelly ClarksonLong ShotSong by Kelly Clarksonfrom the album All I Ever Wanted Recorded2008StudioValley Village, California(Bay7 Studios)Calabasas, California(Sparky Dark Studio)Hollywood, California(Sunset Sound Studios)GenrePopLength3:36LabelRCASongwriter(s)Katy Perry, Glen Ballard, Matt ThiessenProducer(s)Howard Benson Long Shot is a song by American singer Kelly Clarkson, from her fourth studio album, All I Ever Wanted (2009). The song was written by Katy Perry, Glen Ballard, and M...

 

Los Angeles Open 1975

Los Angeles Open 1975 Sport Tennis Data 15 settembre – 21 settembre Edizione 49ª Superficie Cemento indoor Montepremi 100 000 $ Campioni Singolare Arthur Ashe Doppio Anand Amritraj / Vijay Amritraj 1974 1976 Il Los Angeles Open 1975 è stato un torneo di tennis giocato sul cemento indoor a Los Angeles negli Stati Uniti. È stata la 49ª edizione del torneo, che fa parte del Commercial Union Assurance Grand Prix 1975. Si è giocato dal 15 al 21 settembre 1975. Indice 1 Partecipan...

 

Wisconsin Center for Film and Theater Research

American archive of research materials Established1960PurposeArchive for performing arts researchHeadquarters816 State StreetMadison, Wisconsin 53706Coordinates43°04′31″N 89°24′00″W / 43.0752°N 89.4°W / 43.0752; -89.4Websitewcftr.commarts.wisc.edu The Wisconsin Center for Film and Theater Research (WCFTR) is a major archive of motion picture, television, radio, and theater research materials. Located in the headquarters building of the Wisconsin Historical ...

Fibrinase

FXIII membuat ikatan melintang pada jaringan fibrin. Fibrinase (bahasa Inggris: fibrinase, fibrinoligase, fibrin stabilizing factor, Laki-Lorand factor, Factor XIII, FXIII) adalah zimogen berjenis transglutaminase yang disintensis oleh Saccharomyces cerevesiae[1] dan beredar dalam sirkulasi darah dalam bentuk heterotetramer yang terdiri dari dua subunit A yang bersifat katalitik dan dua subunit B sebagai pengusungnya. Fibrinase mempunyai waktu paruh berkisar antara 9-14 hari.[...

 

آصف علي أصغر فيضي

آصف علي أصغر فيضي   معلومات شخصية الميلاد 10 أبريل 1899   الوفاة 23 أكتوبر 1981 (82 سنة)   مومباي،  ومَهَارَشتِرة،  والهند  مواطنة الهند (26 يناير 1950–) اتحاد الهند الراج البريطاني  عضو في مجمع اللغة العربية بدمشق  الحياة العملية المدرسة الأم كلية سانت جونزكلية ال�...

 

The Ink Spots

American pop vocal band (1934–1954) The Ink SpotsThe Ink Spots in 1944Background informationOriginIndianapolis, Indiana, United StatesGenresPopeasy listeningswingYears active1934–1954LabelsVictorDeccaWebsiteInkspots.comMusical artist The Ink Spots were an American vocal pop group who gained international fame in the 1930s and 1940s. Their unique musical style predated the rhythm and blues and rock and roll musical genres, and the subgenre doo-wop. The Ink Spots were widely accepted in bot...

Ahmednagar

City in North Maharashtra, India This article is about the city in Maharashtra. For other uses, see Ahmednagar (disambiguation). This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Ahmednagar – news · newspapers · books · scholar · JSTOR (November 2017) (Learn how and when to remove this message) City in Maharas...

 

Heimskringla

Una pagina manoscritta della saga di Harald Hárfagri. Heimskringla è il nome norreno di un'opera epica (quasi completamente in prosa) che raccoglie diverse saghe scandinave, messe assieme attorno al 1225 dal poeta, storico e uomo politico islandese Snorri Sturluson (1179 - 1242). Indice 1 Fonti 2 Contenuto 3 Suddivisione 4 Curiosità 5 Altri progetti 6 Collegamenti esterni Fonti Snorri, nella prima parte della sua opera, fa frequente riferimento al poema epico Ynglingatal (le geste dei Yng...