Was ist Thompson Sampling für Laien?

Ich kann Thompson Sampling und seine Funktionsweise nicht verstehen . Ich las über Multi Arm Bandit und nachdem ich den Upper Confidence Bound Algorithmus gelesen hatte, schlugen viele Texte vor, dass Thompson Sampling eine bessere Leistung als UCB erbringt. Was ist Thompson Sampling?

Zögern Sie nicht, Referenzartikel zum besseren Verständnis bereitzustellen.

Ich werde versuchen, eine Erklärung ohne Mathematik zu geben. Ein Teil dieser Antwort wird von einigen Punkten wiederholt, die ich in einer Antwort auf eine andere Frage zu MAB-Problemen gemacht habe .

Der strategische Kompromiss bei Problemen mit mehrarmigen Banditen: Bei Problemen mit mehrarmigen Banditen spielt der Spieler in jeder Runde einen "Banditen" und versucht, seine erwartete Gesamtrendite über eine bestimmte Anzahl von Runden zu maximieren. Die erwartete Rückkehr jedes der Banditen wird durch einige unbekannte Parameter in dem Problem beschrieben, und wenn wir in jeder Runde mehr Ergebnisse beobachten, erhalten wir mehr Informationen über diese unbekannten Parameter und daher über die erwartete Rückkehr jedes der Banditen . In jeder Spielrunde (mit Ausnahme der letzten) besteht das MAB-Problem darin, dass der Spieler einen strategischen Kompromiss zwischen zwei Zielen eingeht:

• Sofortige Belohnungen: In jeder Runde möchte er eine Verteilung auswählen, die ihm eine hohe erwartete Belohnung in dieser Runde gibt, was eine Präferenz für Verteilungen mit sich bringt, für die er (gegenwärtig) eine hohe mittlere Belohnung erhält.

• Zukünftige Belohnungen (beeinflusst durch Informationsgewinn): Andererseits möchte er sein Wissen über die tatsächlich erwarteten Belohnungen verfeinern, indem er mehr Informationen über die Distributionen erhält (insbesondere über die, die er nicht so oft gespielt hat wie andere), damit er dies kann Verbessere seine Auswahl in zukünftigen Runden.

Die relative Wichtigkeit dieser beiden Dinge bestimmt den Kompromiss, und diese relative Wichtigkeit wird von einer Reihe von Faktoren beeinflusst. Wenn das Problem zum Beispiel nur eine geringe Anzahl verbleibender Runden enthält, ist die Inferenz für zukünftige Versuche relativ weniger wertvoll, wohingegen bei einer großen Anzahl verbleibender Runden die Inferenz für zukünftige Belohnungen relativ wertvoller ist. Der Spieler muss sich also überlegen, wie sehr er sich darauf konzentrieren möchte, die unmittelbaren Belohnungen in der aktuellen Runde zu maximieren, und wie sehr er davon abweichen möchte, um mehr über die unbekannten Parameter zu erfahren, die die erwartete Belohnung für jeden der Banditen bestimmen.

Thompson-Abtastung: Die Grundidee der Thompson-Abtastung besteht darin, dass wir in jeder Runde unser vorhandenes Wissen über die Maschinen in Form einer nachträglichen Überzeugung über die unbekannten Parameter heranziehen und die Parameter aus dieser nachträglichen Verteilung "abtasten". Dieser abgetastete Parameter liefert eine Reihe von erwarteten Belohnungen für jede Maschine, und nun setzen wir unter diesem abgetasteten Parameter auf den mit der höchsten erwarteten Rendite.

Anschaulich scheint das Thompson-Stichprobenverfahren einen Versuch zu beinhalten, die unmittelbar erwartete Rendite in jeder Runde zu maximieren (da dieser Maximierungsschritt nach der Stichprobe des Parameters erfolgt). Da es sich jedoch um eine zufällige Auswahl des Parameters aus dem hinteren Bereich handelt, beinhaltet das Schema ein implizitesVariation der Maximierung der aktuellen Belohnung im Vergleich zur Suche nach weiteren Informationen. Die meiste Zeit erhalten wir einen Parameter "sample", der sich irgendwo im Hauptteil des Seitenzahns befindet, und die Wahl der Maschine entspricht in etwa der Maximierung der sofortigen Belohnung. Manchmal werden wir jedoch nach dem Zufallsprinzip einen Parameterwert abtasten, der weit im hinteren Bereich der Verteilung liegt, und in diesem Fall eine Maschine auswählen, die die sofortige Belohnung nicht maximiert - dh dies ist eher eine "Suche" "um bei zukünftigen Belohnungen zu helfen.

Das Thompson-Schema hat auch die nette Eigenschaft, dass wir dazu neigen, unsere "Suche" zu verringern, wenn wir mehr Informationen erhalten, und dies ahmt den wünschenswerten strategischen Kompromiss bei dem Problem nach, bei dem wir uns weniger auf Suchen konzentrieren möchten, wenn wir mehr Informationen erhalten. Wenn wir mehr und mehr Runden spielen und immer mehr Daten erhalten, nähert sich der Posterior den wahren Parameterwerten an, und so wird die zufällige "Stichprobe" im Thompson-Schema dichter um die Parameterwerte herum, die zu einer Maximierung der Werte führen sofortige Belohnung. Daher besteht die implizite Tendenz, dass dieses Schema früh mit wenig Informationen eher "suchorientiert" und später bei vielen Daten weniger "suchorientiert" ist.

Ein klarer Nachteil des Thompson-Stichprobenplans besteht nun darin, dass die Anzahl der im MAB-Problem verbleibenden Runden nicht berücksichtigt wird. Dieses Schema basiert manchmal auf einem Spiel mit unendlichen Runden, und in diesem Fall ist das kein Problem. Bei MAB-Problemen mit endlichen Runden ist es jedoch vorzuziehen, die Anzahl verbleibender Runden zu berücksichtigen, um die "Suche" zu verringern, wenn die Anzahl zukünftiger Runden abnimmt. (Das optimale Spiel in der letzten Runde besteht insbesondere darin, die Suchanfragen vollständig zu ignorieren und nur auf den Banditen mit der höchsten nachträglich zu erwartenden Rendite zu setzen.) Das Thompson-Schema tut dies nicht und spielt daher in gewisser Weise endliche Runden das ist in bestimmten Fällen eindeutig nicht optimal.

Ich werde es versuchen und ich hoffe es gefällt euch! Es gibt einige Formeln, vor denen Sie Angst haben könnten. Das hoffe ich nicht, denn ich werde mein Bestes tun, um sie so einfach wie möglich zu erklären.

Dies sind die beiden Formeln:

• $P(r|\theta,a,x)$
• $P(\theta|D)$

TL; DR

Mit Thompson Sampling können Sie

1. Wählen Sie einen zufälligen Modellparameter aus allen Modellparametern, die Sie für möglich halten.
2. Handeln Sie einmal gemäß diesem bestimmten Modellparameter.
3. Beobachten Sie die Belohnung, die Sie mit diesem bestimmten Modellparameter erhalten.
4. Lernen Sie aus dieser neuen Erfahrung und aktualisieren Sie Ihre Überzeugung über die möglichen Modellparameter.

Wahrscheinlichkeit??

$r$$a$$x$

Was ist mit diesem seltsamen Kreis?

Wie Sie vielleicht bemerkt haben, habe ich nichts über diesen seltsamen Kreis geschrieben $\theta$das heißt Theta. (Mathematiker haben die Angewohnheit, mit griechischen Buchstaben anzugeben, welche Teile am schwierigsten sind, was das Verständnis noch erschwert.) Dies$\theta$repräsentiert den Modellparameter. Diese Parameter werden verwendet, wenn die Beziehung zwischen Kontext + Aktionen und Belohnung schwieriger ist. Ein Modellparameter könnte beispielsweise sein, wie viel Ihre Belohnung sinkt, wenn 1 mm Regen auf Ihren Kopf fällt. Ein anderer Modellparameter gibt möglicherweise an, wie viel Ihre Belohnung sinkt, wenn Sie einen Regenschirm mitnehmen. Ich habe nur gesagt, dass die Wahrscheinlichkeit das Wesentliche ist, was Sie verstehen wollen. und von zentraler Bedeutung für die Wahrscheinlichkeit sind die Modellparameter. Wenn Sie die Modellparameter kennen$\theta$Sie wissen, wie Kontext + Aktionen mit Belohnung zusammenhängen, und es ist einfach, optimal zu handeln.

Wie können wir diese Modellparameter so kennenlernen, dass ich die maximale Belohnung bekomme?

Das ist die wesentliche Frage für das mehrarmige Banditenproblem. Eigentlich besteht es aus zwei Teilen. Sie möchten die Modellparameter genau kennenlernen, indem Sie alle Arten von Aktionen in verschiedenen Kontexten untersuchen. Wenn Sie jedoch bereits wissen, welche Aktion für einen bestimmten Kontext geeignet ist, möchten Sie diese Aktion ausnutzen und so viel Belohnung wie möglich erhalten. Wenn Sie sich über Ihre Modellparameter nicht sicher sind$\theta$Vielleicht möchten Sie etwas mehr erforschen. Wenn Sie sich über unsere Modellparameter ziemlich sicher sind$\theta$Sie sind sich auch ziemlich sicher, welche Aktion Sie durchführen sollen. Dies wird als Kompromiss zwischen Exploration und Ausbeutung bezeichnet.

Sie haben nichts über diesen posterior gesagt

Der Schlüssel zu diesem optimalen Verhalten ist Ihre (Un) Sicherheit bezüglich der Modellparameter $\theta$. Und der Hintere sagt genau das: In Anbetracht der vorherigen Belohnungen, die wir aus früheren Aktionen in früheren Kontexten erhalten haben, wie viel wissen Sie darüber$\theta$. Wenn Sie zum Beispiel noch nie draußen waren, wissen Sie nicht, wie unglücklich Sie sind, wenn Regen auf Ihren Kopf fällt. Mit anderen Worten, Sie sind sehr unsicher in Bezug auf den Modellparameter "Unglück bei Regen auf dem Kopf". Wenn es manchmal geregnet hat, mit und ohne Regenschirm, können Sie anfangen, etwas über diesen undurchsichtigen Modellparameter zu lernen.

Was schlägt Thomson Sampling mit all diesen Unsicherheiten vor?

Thomson Sampling schlägt etwas sehr Einfaches vor: Wählen Sie einfach einen zufälligen Modellparameter aus Ihrem posterioren Bereich aus, ergreifen Sie eine Aktion und beobachten Sie, was passiert. Wenn Sie zum Beispiel noch nie zuvor draußen waren, kann der Parameter "Unglück, wenn Regen auf dem Kopf" beliebig sein. Also wählen wir einfach eine aus, wir gehen davon aus, dass wir wirklich unglücklich werden, wenn Regen auf unseren Kopf fällt. Wir sehen, dass es regnet (Kontext), also nehmen wir einen Regenschirm (Aktion), weil unser Modellparameter uns sagt, dass wir auf diese Weise die maximale Belohnung erhalten können. Und tatsächlich merkt man, dass man etwas mürrisch wird, wenn man mit einem Regenschirm im Regen läuft, aber nicht wirklich unglücklich ist. Wir lernen daraus, dass Regen + Regenschirm mürrisch ist. Wenn es das nächste Mal regnet, nimmst du wieder einen zufälligen Glauben an, was passiert, wenn Regen auf deinen Kopf fällt. Diesmal könnte es sein, dass es dich überhaupt nicht stört. Jedoch, Sobald Sie auf halbem Weg zu Ihrem Ziel angekommen sind, werden Sie nass und Sie lernen, dass Regen ohne Regenschirm wirklich sehr, sehr schlimm ist. Dies verringert Ihre Unsicherheit über das Unglück, wenn es auf dem Kopf regnet, denn jetzt wissen Sie, dass es wahrscheinlich hoch ist.

Das klingt so einfach!

Ja, es ist nicht so komplex. Der schwierige Teil ist die Stichprobe aus einem Modellparameter posterior. Es ist schwierig, eine Verteilung über alle Modellparameter zu erhalten und aufrechtzuerhalten, die auch für Ihr spezifisches Problem geeignet ist. Aber ... es ist definitiv machbar :).