En el problema de los expertos, expertos le dan predicciones binarias a diario, y usted tiene que predecir si va a llover mañana.
Es decir, en el día , usted conoce las predicciones pasadas de los expertos, el clima real para los días y las predicciones para mañana, y tiene que predecir si lloverá al día siguiente.
En el algoritmo clásico de mayoría ponderada , el algoritmo comete errores , donde es el número de errores del mejor experto.
Para mí, esto parece una promesa extremadamente débil, ya que no permite ningún beneficio al combinar las predicciones de varios expertos.
Suponga que cada resultado es , la predicción del experto el día es y el resultado del día es . Podemos definir un adversario de `` mayoría ponderada óptima '' como una función de peso óptima , de modo que la decisión tomada por el adversario en el día se define como , es decir, la mayoría ponderada de las predicciones, con respecto al vector . Usando esta notación, el adversario anterior (mejor experto) solo podía elegir vectores unitarios.
Entonces podemos definir el error óptimo para los días como:
¿Cómo minimizarías el arrepentimiento, en comparación con ?
Para ver que este es un adversario mucho más poderoso, considere el caso de expertos y días en los que el resultado siempre fue . Si , entonces cada experto tuvo un error, pero un vector de mayoría ponderada de no tenía ninguno.
Respuestas:
Si no le importa la aleatorización, los algoritmos de aprendizaje en línea estándar en el "marco de optimización convexo en línea" le brindan esencialmente lo que pide, con expectativa. La razón es que estos algoritmos son necesarios para generar una distribución en los expertos en cada paso de tiempo, sufriendo una pérdida esperada igual a la expectativa de elegir un experto de esta distribución. Y tienen un bajo arrepentimiento esperado en comparación con la mejor distribución de expertos, es decir, .w∈Δ([n]) O(lnn/T−−−−−√)
Por ejemplo, puede tomar el algoritmo clásico de pesos multiplicativos, que es solo mayoría ponderada, pero elegir un experto para seguir con probabilidad proporcional a su "peso". Esto se menciona en la encuesta de Arora (Teorema 6): https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf
fuente