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:

clnNini

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 iniNi

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.

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

Respostas:

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).

nii1/ni é 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.nii

Niln(Ni) 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).Niln(Ni)

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