Confiança superior limitada no aprendizado de máquina

8

Me deparei com a fórmula para obter limites superiores de confiança no problema dos bandidos armados com k:

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

onde é a quantidade de amostras que temos para esse bandido específico e é a quantidade total de amostras que temos de todos os bandidos. O mesmo algoritmo é usado na Pesquisa em árvore de Monte Carlo também para obter o limite de confiança superior. $n_i$ $N_i$

Entendo muito claramente o que é um limite superior de confiança, mas o que não entendo é de onde vem essa fórmula. Tentei procurar on-line em vários lugares, mas não consegui encontrar uma explicação clara de como essa fórmula é derivada. Alguém pode explicar de onde vem esta fórmula? Por favor, assuma que eu não tenho um ótimo histórico em estatística.

machine-learning mathematical-statistics confidence-interval reinforcement-learning multiarmed-bandit programador de xadrez
fonte

Pessoalmente, achei que o banditalgs.com/2016/09/18/the-upper-confidence-bound-algorithm continha uma boa explicação. Isso inclui um pouco de matemática pesada, mas é possível obter um bom entendimento mesmo quando pular algumas das equações mais pesadas na minha opinião. Basta ler a intuição e algumas das equações mais simples

Dennis Soemers

5

O que você tem lá é comumente chamado de termo de exploração. O limite de confiança superior é a média empírica mais este termo de exploração.

Vamos considerar cada termo separadamente:

$c$ é uma constante que permite ao usuário definir o trade-off de exploração / exploração. Para resultados teóricos, é frequentemente otimizado para o problema em questão (por exemplo, bandidos armados com k com prior gaussiano).

$\sqrt{1/n_i}$ é proporcional ao desvio padrão posterior após amostras de ação . Essencialmente, isso diz que, à medida que você puxa um braço com mais frequência, há menos desconhecido sobre ele. $n_i$ $i$

$\sqrt{ln(N_i)}$ garante que você não pare de explorar cedo demais. À medida que se torna muito grande, as variações da amostra se tornam pequenas o suficiente para compensarmos para garantir que nunca paremos completamente de explorar. A maior parte da matemática técnica é mostrar que é apenas a compensação (mas não muito). $N_i$ $\sqrt{ln(N_i)}$

Para uma descrição mais técnica, o artigo de Auer et al. é um bom ponto de partida.

combinação
fonte

o link no final não funciona para mim.

Chessprogrammer

Deve funcionar agora, desculpe por isso

combo

2

Ele vem da desigualdade de Hoeffding, que fornece um limite superior à probabilidade de que a soma das variáveis aleatórias independentes delimitadas se desvie do valor esperado em mais do que uma certa quantia. Veja https://en.wikipedia.org/wiki/Hoeffding%27s_inequality para mais informações sobre a desigualdade de Hoeffding. Veja o texto em torno da equação (3) no documento original da UCT para uma discussão detalhada sobre isso com o UCB1 na configuração de bandidos http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296

Falcão
fonte

Confiança superior limitada no aprendizado de máquina

clnNini−−−−−√clnNinic\sqrt{\frac{\text{ln} N_i}{n_i}}

Respostas:

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