Algoritm de agregare pentru predicția pachetelor SpringerLink
Abstract
Această lucrare formulează un protocol pentru predicția pachetelor, care este un caz special de predicție on-line sub feedback întârziat. Conform protocolului de predicție a pachetelor, elevul trebuie să facă câteva predicții fără a vedea rezultatele respective și apoi rezultatele sunt dezvăluite dintr-o dată. Lucrarea dezvoltă teoria predicției cu sfaturi de specialitate pentru pachete prin generalizarea conceptului de mixabilitate. Propunem o serie de algoritmi de fuzionare pentru predicția pachetelor cu limite superioare strânse de pierderi de cazuri, similare cu cele pentru algoritmul de agregare al lui Vovk. Spre deosebire de algoritmii existenți pentru setările de feedback întârziat, algoritmii noștri nu depind de ordinea rezultatelor dintr-un pachet. Se efectuează experimente empirice privind seturile de date despre prețuri sportive și case, pentru a studia performanța noilor algoritmi și a le compara cu o metodă existentă.
Introducere
Această lucrare tratează protocolul de predicție on-line, în care un cursant trebuie să prezică rezultatele \ (\ omega _1, \ omega _2 \ ldots \) care apar în succesiune. Elevul primește feedback pe parcurs.
În protocolul de predicție online de bază, pe pas t cursantul produce o predicție \ (\ gamma _t \) și apoi vede imediat rezultatul adevărat \ (\ omega _t \), care este feedback-ul. Calitatea predicției este evaluată printr-o funcție de pierdere \ (\ lambda (\ gamma, \ omega) \) care măsoară discrepanța dintre predicție și rezultat sau, în general vorbind, cuantificând efectul (advers) atunci când o predicție \ (\ gamma \) se confruntă cu rezultatul \ (\ omega \). Performanța cursantului este evaluată prin pierderea cumulată peste T încercări \ (\ sum _ ^ T \ lambda (\ gamma _t, \ omega _t) \) .
În această lucrare, ne preocupă problema predicției cu sfaturi de specialitate. Să presupunem că cursantul are acces la predicțiile unui număr de experți. Înainte ca elevul să facă o predicție, poate vedea predicțiile experților și scopul său este de a suferi pierderi apropiate de cea a celui mai bun expert retrospectiv.
Într-un protocol cu feedback întârziat, poate exista o întârziere în obținerea rezultatelor adevărate \ (\ omega _t \). Este posibil ca elevul să trebuiască să facă câteva predicții înainte de a vedea efectiv rezultatele încercărilor din trecut. Vom lua în considerare un caz special al protocolului respectiv atunci când vor apărea rezultatele pachete: cursantul trebuie să facă câteva predicții, decât toate rezultatele sunt dezvăluite și din nou trebuie făcute câteva predicții.
O problemă care se potrivește în mod natural acestui cadru este asigurată de agregarea predicțiilor caselor de pariuri. Vovk și Zhdanov (2009) prezic rezultatele meciurilor sportive pe baza probabilităților calculate din cotele citate de casele de pariuri. Dacă meciurile apar una câte una, problema se potrivește în mod natural cu predicția de bază cu cadrul de sfaturi ale experților. Cu toate acestea, este obișnuit (de exemplu, în Premier League engleză) ca câteva meciuri să aibă loc în aceeași zi. Ar fi firesc să încerci și să previzi toate rezultatele în prealabil. Toate meciurile din aceeași zi pot fi tratate ca un pachet în cadrul nostru.
Dezvoltăm o teorie a predicției cu sfaturi de specialitate pentru pachete prin extinderea algoritmului de agregare (AA) introdus de Vovk (1990, 1998). În sectă. 2.2 și Anexa A, analizăm teoria existentă a AA pentru prezicerea rezultatelor unice (în terminologia noastră, pachete de mărimea unu). Teoria se bazează pe conceptul de mixabilitate a mediilor de predicție numite jocuri. În sectă. 3, dezvoltăm teoria mixabilității pentru jocuri cu pachete de rezultate. Teorema 1 arată că un joc care implică pachete de K rezultatele au același profil de constante de mixabilitate ca și jocul original cu rezultate unice, dar rata de învățare se împarte la K. Această observație ne permite să gestionăm pachete de dimensiuni constante. Cu toate acestea, după cum sa discutat mai sus, în cazuri cu adevărat interesante, dimensiunea ambalajului variază în funcție de timp și, prin urmare, amestecabilitatea mediului variază de la un pas la altul. Această problemă poate fi abordată în moduri diferite, rezultând algoritmi diferiți cu limite de performanță diferite. În sectă. 4, introducem trei Algoritmi de agregare pentru predicția pachetelor, AAP-max, AAP-incremental și AAP-curent și obțin limite superioare în cel mai rău caz pentru pierderea lor cumulativă.
Teoria generală a AA (Vovk 1998) ne permite să arătăm în Sect. 5 că într-un anumit sens limitele noastre sunt optime. În sectă. 5.1, oferim o derivare independentă a unei limite inferioare pentru cadrul mix-loss al lui Adamskiy și colab. (2016). Cu toate acestea, problema optimității pentru pachete este departe de a fi complet rezolvată și necesită investigații suplimentare.
După cum sa menționat anterior, problema predicției pachetelor poate fi considerată ca un caz special al problemei de feedback întârziat. Această problemă a fost studiată în principal în cadrul optimizării convexe online (Zinkevich 2003; Joulani și colab. 2013; Quanrud și Khashabi 2015). Terminologia și abordarea optimizării convexe online sunt diferite de ale noastre, care se întorc la Littlestone și Warmuth (1994) și au fost chestionate de Cesa-Bianchi și Lugosi (2006).
Problema predicției cu sfaturi de experți pentru feedback întârziat poate fi rezolvată prin rularea copiilor paralele ale algoritmilor care prezic rezultate individuale. În sectă. 2.3, descriem algoritmul Copii paralele, care este în esență BOLD al lui Joulani și colab. (2013) folosind algoritmul de agregare ca algoritm de bază pentru rezultate unice. Teoria algoritmului de agregare implică cel mai rău caz superior la pierderea copiilor paralele. Vedem că termenul de regret se înmulțește cu întârzierea maximă sau dimensiunea ambalajului ca în literatura existentă (Joulani și colab. 2013; Weinberger și Ordentlich 2002).
Limitele pe care le obținem pentru noii noștri algoritmi sunt aceleași (AAP-max și AAP-incremental) sau incompatibile (AAP-curent) cu limitele pentru Copii paralele. Discutăm limitele în sectă. 5 și apoi în sectă. 6 efectuați o comparație empirică a performanței algoritmilor.
Pentru experimente, prezicem rezultatele meciurilor sportive pe baza cotelor caselor de pariuri și stabilim prețurile caselor pe baza descrierilor caselor. Seturile de date sportive includ meciuri de fotbal, care conțin în mod natural pachete, și meciuri de tenis, unde introducem pachete în mod artificial în două moduri diferite. Seturile de date privind prețul locuințelor conțin înregistrări ale tranzacțiilor imobiliare din Ames în SUA și zona Londrei. Seturile de date înregistrează doar luna unei tranzacții, deci sunt organizate în mod natural în pachete. Experimentele privind prețul locuințelor urmează abordarea lui Kalnishkan și colab. (2015): predicția cu sfaturi de experți poate fi utilizată pentru a găsi informații relevante din trecut. Predictorii instruiți pe diferite secțiuni ale datelor anterioare pot fi combinate în modul on-line, astfel încât datele anterioare relevante să fie utilizate pentru predicție.
Performanța algoritmului Copii paralele depinde de ordinea rezultatelor din pachete, în timp ce algoritmii noștri sunt independenți de ordine. Comparăm pierderea cumulativă a algoritmilor noștri cu pierderea copiilor paralele mediată peste permutările aleatorii din pachete. Concluzionăm că, în timp ce copiile paralele pot funcționa foarte bine, mai ales dacă ordinea rezultatelor din pachete oferă informații utile, pierderea algoritmilor noștri este întotdeauna aproape de pierderea medie a copiilor paralele și unii algoritmi depășesc media.
Apoi, comparăm algoritmii noștri, concluzionând că AAP-max este cel mai rău și curentul AAP depășește AAP-incremental dacă raportul dintre dimensiunea maximă și cea minimă a pachetului este mic.