Arrependimento interno na otimização convexa on-line

19

A "otimização convexa on-line" de Zinkevich ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) generaliza os algoritmos de aprendizado de "minimização de arrependimento", de configurações lineares a convexas e fornece bom "arrependimento externo" . Existe uma generalização semelhante para arrependimento interno? (Não tenho muita certeza nem do que exatamente isso significaria.)

lg.learning online-learning Noam
fonte
É possível adicionar uma breve descrição do arrependimento interno à pergunta?
Moritz
Nos habituais "especialistas", definir arrependimento interno significa que, em retrospecto, você não gostaria de trocar uma ação por outra, consistentemente ao longo de toda a história. O artigo de Blum-Mansour é provavelmente a melhor referência para o arrependimento interno versus externo: jmlr.csail.mit.edu/papers/volume8/blum07a/blum07a.pdf
Noam

Respostas:

9

Tente "Aprendizado sem arrependimentos em jogos convexos", de Gordon, Greenwald e Marks http://portal.acm.org/citation.cfm?id=1390202 . Parece abstrato, provavelmente responde à sua pergunta, ou pelo menos qualquer pessoa que responda a essa pergunta citaria ou seria citada por esse artigo.

Warren Schudy
fonte
0

Este artigo da Avrim Blum aponta uma conexão entre arrependimento externo e interno. De acordo com seu resumo, arrependimento externo é uma medida de quão ruim um algoritmo é comparado à melhor ação fixa, enquanto arrependimento interno se compara à melhor variação desse método (melhor permutação fixa de saídas, como relatar a classe A sempre que o algoritmo original reportou classe B).

Alexandre Passos
fonte
11
O artigo de Blum-Mansour não está na configuração "otimização convexa on-line", mas na configuração "experts" linear. Minha pergunta é se algo semelhante ou algum outro algoritmo de arrependimento interno direto pode ser aplicado na configuração convexa.
Noam