Im Expertenproblem geben Ihnen Experten täglich binäre Vorhersagen, und Sie müssen vorhersagen, ob es morgen regnen wird.
Das heißt, am Tag kennen Sie die früheren Vorhersagen der Experten, das tatsächliche Wetter für die Tage und die Vorhersagen für morgen und müssen vorhersagen, ob es am nächsten Tag regnen wird.
Im klassischen Weighted Majority- Algorithmus macht der Algorithmus -Fehler, wobei die Anzahl der Fehler des besten Experten ist.
Für mich scheint dies ein äußerst schwaches Versprechen zu sein, da es keinen Nutzen daraus zieht, Vorhersagen mehrerer Experten zu kombinieren.
Angenommen, jedes Ergebnis ist , die Vorhersage des Experten am Tag ist und das Ergebnis des Tages ist . Wir können einen Gegner mit optimaler gewichteter Mehrheit als optimale Gewichtsfunktion , so dass die Entscheidung des Gegners am Tag als wird. dh die gewichtete Mehrheit der Vorhersagen in Bezug auf den Vektor . Mit dieser Notation konnte der vorherige Gegner (bester Experte) nur Einheitsvektoren auswählen.
Wir können dann den optimalen Fehler für die Tage wie definieren :
Wie würden Sie das Bedauern im Vergleich zu E minimieren ?
Um zu sehen, dass dies ein viel mächtigerer Gegner ist, betrachten Sie den Fall von Experten und Tagen, in denen das Ergebnis immer . Wenn , dann hatte jeder Experte einen Fehler, aber einen gewichteten Mehrheitsvektor von hatte keine.
Antworten:
Wenn Ihnen die Randomisierung nichts ausmacht, bieten Ihnen Standard-Online-Lernalgorithmen im "Online Convex Optimization Framework" erwartungsgemäß im Wesentlichen das, wonach Sie fragen. Der Grund dafür ist, dass diese Algorithmen erforderlich sind, um zu jedem Zeitschritt eine Verteilung an Experten auszugeben , wobei ein erwarteter Verlust zu erwarten ist, der der Erwartung entspricht, einen Experten aus dieser Verteilung auszuwählen. Und sie haben ein geringes erwartetes Bedauern im Vergleich zu der besten Verteilung unter Experten, dh .w∈Δ([n]) O(lnn/T−−−−−√)
Sie können beispielsweise den klassischen Algorithmus für multiplikative Gewichte verwenden, bei dem es sich nur um eine gewichtete Mehrheit handelt, bei dem jedoch ein Experte ausgewählt wird, der mit einer Wahrscheinlichkeit proportional zu seinem "Gewicht" folgt. Dies wird in Aroras Umfrage (Satz 6) erwähnt: https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf
quelle