Oberes Vertrauen in maschinelles Lernen gebunden

8

Ich bin auf die Formel gestoßen, um die oberen Vertrauensgrenzen für das Problem der k-bewaffneten Banditen zu erreichen:

$c \sqrt{\frac{ln N_{i}}{n_{i}}}$ $c\sqrt{\frac{\text{ln} N_i}{n_i}}$

Dabei ist die Anzahl der Proben, die wir für diesen bestimmten Banditen haben, und die Gesamtmenge der Proben, die wir von allen Banditen haben. Der gleiche Algorithmus wird auch bei der Monte-Carlo-Baumsuche verwendet, um die obere Konfidenzgrenze zu erhalten. $n_i$ $N_i$

Ich verstehe sehr klar, was eine obere Vertrauensgrenze ist, aber ich verstehe nicht, woher diese Formel kommt. Ich habe versucht, an mehreren Stellen online zu suchen, konnte jedoch keine klare Erklärung dafür finden, wie diese Formel abgeleitet wird. Kann jemand bitte erklären, woher diese Formel kommt? Bitte nehmen Sie an, ich habe keinen guten Hintergrund in der Statistik.

machine-learning mathematical-statistics confidence-interval reinforcement-learning multiarmed-bandit Schachprogrammierer
quelle

Ich persönlich fand, dass banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm eine gute Erklärung enthält. Es beinhaltet einige schwere Mathematik, aber es ist möglich, ein gutes Verständnis zu erlangen, selbst wenn einige der schwereren Gleichungen meiner Meinung nach übersprungen werden. Lesen Sie einfach die Intuition und einige der einfacheren Gleichungen

Dennis Soemers

5

Was Sie dort haben, wird allgemein als Explorationsbegriff bezeichnet. Die obere Konfidenzgrenze ist das empirische Mittel plus dieser Explorationsbedingung.

Betrachten wir jeden Begriff einzeln:

$c$ ist eine Konstante, mit der der Benutzer den Kompromiss zwischen Exploration und Exploitation festlegen kann. Für theoretische Ergebnisse wird es häufig für das jeweilige Problem optimiert (z. B. k-bewaffnete Banditen mit Gaußschen Priors).

$\sqrt{1/n_i}$ ist proportional zur posterioren Standardabweichung nach Aktionsproben . Im Wesentlichen bedeutet dies, dass der Arm weniger unbekannt ist, wenn Sie häufiger an einem Arm ziehen. $n_i$ $i$

$\sqrt{ln(N_i)}$ stellt sicher, dass Sie nicht zu früh aufhören zu erkunden. Wenn sehr groß wird, werden die Stichprobenvarianzen so klein, dass wir sie kompensieren müssen, um sicherzustellen, dass wir nie ganz aufhören zu erforschen. Der größte Teil der technischen Mathematik besteht darin, zu zeigen, dass gerade genug (aber nicht zu viel) Kompensation ist. $N_i$ $\sqrt{ln(N_i)}$

Für eine technischere Beschreibung wurde das Papier von Auer et al. ist ein guter Ausgangspunkt.

Combo
quelle

Der Link am Ende funktioniert bei mir nicht.

Schachprogrammierer

Sollte jetzt funktionieren, tut mir leid

Combo

2

Es kommt von Hoeffdings Ungleichung, die eine Obergrenze für die Wahrscheinlichkeit liefert, dass die Summe der begrenzten unabhängigen Zufallsvariablen um mehr als einen bestimmten Betrag von ihrem erwarteten Wert abweicht. Weitere Informationen zur Ungleichung von Hoeffding finden Sie unter https://en.wikipedia.org/wiki/Hoeffding%27s_inequality . Im Text um Gleichung (3) im Original-UCT-Papier finden Sie eine ausführliche Diskussion zu UCB1 in der Banditeneinstellung http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296

Falke
quelle

Oberes Vertrauen in maschinelles Lernen gebunden

c ln N.ichnich- -- -- -- -- -√clnNinic\sqrt{\frac{\text{ln} N_i}{n_i}}

Antworten:

$c \sqrt{\frac{ln N_{i}}{n_{i}}}$ $c\sqrt{\frac{\text{ln} N_i}{n_i}}$