Limite de confiance supérieure dans l'apprentissage automatique

8

Je suis tombé sur la formule pour obtenir les limites de confiance supérieures sur le problème des bandits armés de k:

clnNini

où ni est la quantité d'échantillons que nous avons pour ce bandit particulier et Niest la quantité totale d'échantillons que nous avons de tous les bandits. Le même algorithme est également utilisé dans Monte Carlo Tree Search pour obtenir la borne de confiance supérieure.

Je comprends très clairement ce qu'est une limite de confiance supérieure, mais ce que je ne comprends pas, c'est d'où vient cette formule. J'ai essayé de chercher en ligne à plusieurs endroits, mais je n'ai pas pu trouver d'explication claire sur la façon dont cette formule est dérivée. Quelqu'un peut-il expliquer d'où vient cette formule? Veuillez supposer que je n'ai pas une grande expérience en statistiques.

machine-learning mathematical-statistics confidence-interval reinforcement-learning multiarmed-bandit programmeur d'échecs
la source
J'ai personnellement trouvé que banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm contenait une bonne explication. Cela inclut quelques calculs lourds, mais il est possible d'avoir une bonne compréhension même en sautant certaines des équations les plus lourdes à mon avis. Il suffit de lire l'intuition et certaines des équations les plus simples
Dennis Soemers

Réponses:

5

Ce que vous avez là-bas est communément appelé le terme d'exploration. La limite de confiance supérieure est la moyenne empirique plus ce terme d'exploration.

Examinons chaque terme séparément:

cest une constante qui permet à l'utilisateur de définir le compromis d'exploration / exploitation. Pour les résultats théoriques, il est souvent optimisé pour le problème en question (par exemple, les bandits armés de k avec des antérieurs gaussiens).

1/ni est proportionnelle à l'écart type postérieur après ni exemples d'action i. Essentiellement, cela signifie que lorsque vous tirez un bras plus souvent, le bras est moins connu.

ln(Ni)garantit que vous n'arrêtez pas d'explorer trop tôt. CommeNidevient très grand, les variances d'échantillon deviennent suffisamment petites pour que nous ayons besoin de compenser pour nous assurer que nous n'arrêtons jamais complètement d'explorer. La plupart des calculs techniques consistent à montrer queln(Ni) est juste assez (mais pas trop) de compensation.

Pour une description plus technique, l'article d' Auer et al. est un bon point de départ.

combo
la source
le lien à la fin ne fonctionne pas pour moi.
chessprogrammer
Devrait fonctionner maintenant, désolé pour cela
combo
2

Elle provient de l'inégalité de Hoeffding, qui fournit une limite supérieure sur la probabilité que la somme des variables aléatoires indépendantes bornées s'écarte de sa valeur attendue de plus d'un certain montant. Voir https://en.wikipedia.org/wiki/Hoeffding%27s_inequality pour plus d'informations sur l'inégalité de Hoeffding. Voir le texte autour de l'équation (3) dans le document UCT original pour une discussion détaillée concernant ceci à UCB1 dans le réglage de bandit http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296

Faucon
la source