Lamento interno en la optimización convexa en línea

19

La "optimización convexa en línea" de Zinkevich ( http://www.cs.cmu.edu/~maz/publications/ICML03.pdf ) generaliza los algoritmos de aprendizaje de "minimización de arrepentimiento" de una configuración lineal a una configuración convexa y ofrece un buen "arrepentimiento externo" . ¿Existe una generalización similar para el arrepentimiento interno? (No estoy totalmente seguro ni siquiera qué significa exactamente eso).

Noam
fuente
¿Es posible agregar una breve descripción del arrepentimiento interno a la pregunta?
Moritz
En los "expertos" habituales, establecer el arrepentimiento interno significa que, en retrospectiva, no querrá cambiar una acción con otra, de manera consistente a lo largo de toda la historia. El artículo de Blum-Mansour es probablemente la mejor referencia para el arrepentimiento interno versus externo: jmlr.csail.mit.edu/papers/volume8/blum07a/blum07a.pdf
Noam

Respuestas:

9

Pruebe "Aprendizaje sin arrepentimiento en juegos convexos" de Gordon, Greenwald y Marks http://portal.acm.org/citation.cfm?id=1390202 . Su resumen parece que probablemente responde a su pregunta, o al menos cualquiera que responda esa pregunta citaría o sería citado por ese documento.

Warren Schudy
fuente
0

Este papel de Avrim Blum señala una conexión entre el arrepentimiento externo y el interno. Según su resumen, el arrepentimiento externo es una medida de qué tan mal se compara un algoritmo con la mejor acción fija, mientras que el arrepentimiento interno se compara con la mejor variación de ese método (mejor permutación fija de salidas, como informar la clase A cuando el algoritmo original informa clase B).

Alexandre Passos
fuente
1
El artículo de Blum-Mansour no está en la configuración de "optimización convexa en línea", sino en la configuración lineal de "expertos". Mi pregunta es si se puede aplicar algo similar o algún otro algoritmo de arrepentimiento interno directo en la configuración convexa.
Noam