Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithmic Study on Prediction with Expert Advice: Study of 3 novel paradigms with Grouped Experts
KTH, School of Electrical Engineering and Computer Science (EECS).
2018 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

The main work for this thesis has been a thorough study of the novel Prediction with Partially Monitored Grouped Expert Advice and Side Information paradigm. This is newly proposed in this thesis, and it extends the widely studied Prediction with Expert Advice paradigm. The extension is based on two assumptions and one restriction that modify the original problem. The first assumption, Grouped, presumes that the experts are structured into groups. The second assumption, Side Information, introduces additional information that can be used to timely relate predictions with groups. Finally, the restriction, Partially Monitored, imposes that the groups’ predictions are only known for one group at a time.

The study of this paradigm includes the design of a complete prediction algorithm, the proof of a theoretical bound of the worse-case cumulative regret for such algorithm, and an experimental evaluation of the algorithm (proving the existence of cases where this paradigm outperforms Prediction with Expert Advice). Furthermore, since the development of the algorithm is constructive, it allows to easily build two additional prediction algorithms for the Prediction with Grouped Expert Advice and Prediction with Grouped Expert Advice and Side Information paradigms. Therefore, this thesis presents three novel prediction algorithms, with corresponding regret bounds, and a comparative experimental evaluation including the original Prediction with Expert Advice paradigm.

Abstract [sv]

Huvudarbetet för den här avhandlingen har varit en grundlig studie av den nya Prediction with Partially Monitored Grouped Expert Advice and Side Information paradigmet. Detta är nyligen föreslagit i denna avhandling, och det utökar det brett studerade Prediction with Expert Advice paradigmet. Förlängningen baseras på två antaganden och en begränsning som ändrar det ursprungliga problemet. Det första antagandet, Grouped, förutsätter att experterna är inbyggda i grupper. Det andra antagandet, Side Information, introducerar ytterligare information som kan användas för att i tid relatera förutsägelser med grupper. Slutligen innebär begränsningen, Partially Monitored, att gruppens förutsägelser endast är kända för en grupp i taget.

Studien av detta paradigm innefattar utformningen av en komplett förutsägelsesalgoritm, beviset på en teoretisk bindning till det sämre fallet kumulativa ånger för en sådan algoritm och en experimentell utvärdering av algoritmen (bevisar förekomsten av fall där detta paradigm överträffar Prediction with Expert Advice). Eftersom algoritmens utveckling är konstruktiv tillåter den dessutom att enkelt bygga två ytterligare prediksionsalgoritmer för Prediction with Grouped Expert Advice och Prediction with Grouped Expert Advice and Side Information paradigmer. Därför presenterar denna avhandling tre nya prediktionsalgoritmer med motsvarande ångergränser och en jämförande experimentell utvärdering inklusive det ursprungliga Prediction with Expert Advice paradigmet.

Place, publisher, year, edition, pages
2018. , p. 93
Series
TRITA-EECS-EX ; 2018:442
Keywords [en]
online learning; prediction with expert advice; multi-arm bandit problem; regret optimization.
Keywords [sv]
online lärande; förutsägelse med expertråd; multi-arm bandit problem; ångra optimering aktiekurs förutsägelse.
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-254344OAI: oai:DiVA.org:kth-254344DiVA, id: diva2:1331021
Subject / course
Computer Science
Educational program
Degree of Master
Supervisors
Examiners
Available from: 2019-06-26 Created: 2019-06-26 Last updated: 2019-06-26Bibliographically approved

Open Access in DiVA

fulltext(3672 kB)15 downloads
File information
File name FULLTEXT01.pdfFile size 3672 kBChecksum SHA-512
6d50dbc00123153dd0096d903885d3ba7b27a70e94926c2cb0e4e58c84294f3650c1778e8cdefe4624f13360cf562abf0bc39ca445d8d014731a1922a863da9f
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 15 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 22 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf