Algoritmo de aprendizaje aumentado

Un algoritmo de aprendizaje aumentado es un algoritmo que puede utilizar una predicción para mejorar su rendimiento. ^[1] Mientras que en los algoritmos regulares solo se ingresa la instancia del problema, los algoritmos de aprendizaje aumentado aceptan un parámetro adicional. Este parámetro adicional suele ser una predicción de alguna propiedad de la solución. Luego, el algoritmo utiliza esta predicción para mejorar su tiempo de ejecución o la calidad de su salida.

Descripción

Un algoritmo de aprendizaje aumentado normalmente requiere una entrada . Aquí hay un ejemplo de problema y un consejo: una predicción sobre una determinada propiedad de la solución óptima. El tipo de instancia del problema y la predicción dependen del algoritmo. Los algoritmos de aprendizaje aumentado suelen satisfacer las dos propiedades siguientes: ${\displaystyle ({\mathcal {I}},{\mathcal {A}})}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle {\mathcal {A}}}$

• Consistencia. Se dice que un algoritmo de aprendizaje aumentado es consistente si se puede demostrar que tiene un buen rendimiento cuando se le proporciona una predicción precisa. ^[1] Por lo general, esto se cuantifica dando un límite al rendimiento que depende del error en la predicción.
• Robustez. Un algoritmo se considera robusto si su desempeño en el peor de los casos puede limitarse incluso si la predicción dada es inexacta. ^[1]

Los algoritmos de aprendizaje aumentado generalmente no prescriben cómo se debe realizar la predicción. Para ello se puede utilizar el aprendizaje automático . ^{[ cita necesaria ]}

Ejemplos

búsqueda binaria

El algoritmo de búsqueda binaria es un algoritmo para encontrar elementos de una lista ordenada . Necesita pasos para encontrar un elemento con algún valor conocido en una lista de longitud . Con una predicción para la posición de , se puede utilizar el siguiente algoritmo de aprendizaje aumentado. ^[1] ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle O(\log(n))}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle x}$

• Primero, mire la posición en la lista. Si , se ha encontrado el elemento. ${\displaystyle i}$ ${\displaystyle x_{i}=y}$
• Si es , mire las posiciones hasta que encuentre un índice con . ${\displaystyle x_{i}<y}$ ${\displaystyle i+1,i+2,i+4,\ldots }$ ${\displaystyle j}$ ${\displaystyle x_{j}\geq y}$
  • Ahora realice una búsqueda binaria en . ${\displaystyle x_{i},\ldots ,x_{j}}$
• Si , haz lo mismo que en el caso anterior, pero en su lugar considera . ${\displaystyle x_{i}>y}$ ${\displaystyle i-1,i-2,i-4,\ldots }$

El error se define como , donde está el índice real de . En el algoritmo de aprendizaje aumentado, sondear las posiciones requiere pasos. Luego se realiza una búsqueda binaria en una lista de tamaño como máximo , que requiere pasos. Esto hace que el tiempo total de ejecución del algoritmo . Entonces, cuando el error es pequeño, el algoritmo es más rápido que una búsqueda binaria normal. Esto muestra que el algoritmo es consistente. Incluso en el peor de los casos, el error será como máximo . Entonces el algoritmo toma como máximo los pasos, por lo que el algoritmo es robusto. ${\displaystyle \eta =|i-i^{*}|}$ ${\displaystyle i^{*}}$ ${\displaystyle y}$ ${\displaystyle i+1,i+2,i+4,\ldots }$ ${\displaystyle \log _{2}(\eta )}$ ${\displaystyle 2\eta }$ ${\displaystyle \log _{2}(\eta )}$ ${\displaystyle 2\log _{2}(\eta )}$ ${\displaystyle n}$ ${\displaystyle O(\log(n))}$

Más ejemplos

Los algoritmos de aprendizaje aumentado son conocidos por:

• El problema del alquiler de esquís ^[2]
• El problema de igualación de peso máximo ^[3]
• El problema de la paginación ponderada ^[4]

Ver también

• Aprendizaje automático

Referencias

1. Mitzenmacher, Michael ; Vassilvitskii, Sergei (31 de diciembre de 2020). "Algoritmos con predicciones". Más allá del análisis de algoritmos en el peor de los casos . Prensa de la Universidad de Cambridge. págs. 646–662. arXiv : 2006.09123 . doi :10.1017/9781108637435.037.
2. Wang, Shufan; Li, Jian; Wang, Shiqiang (2020). "Algoritmos en línea para alquiler de esquí en varias tiendas con asesoramiento de aprendizaje automático". NIPS'20: Actas de la 34ª Conferencia Internacional sobre Sistemas de Procesamiento de Información Neural . arXiv : 2002.05808 . ISBN 1-71382-954-1. OCLC  1263313383.
3. Dinitz, Michael; Soy, Sungjin; Lavastida, Thomas; Benjamín, Benjamín; Vassilvitskii, Sergei (2021). "Emparejamientos más rápidos a través de duales aprendidos". Avances en sistemas de procesamiento de información neuronal (PDF) . Curran asociados, Inc.
4. Bansal, Nikhil; Coester, cristiano; Kumar, Ravi; Purohit, Manish; Vee, Erik (enero de 2022). "Paginación ponderada con aprendizaje aumentado". Actas del Simposio anual ACM-SIAM de 2022 sobre algoritmos discretos (SODA) . Sociedad de Matemática Industrial y Aplicada. págs. 67–89. doi :10.1137/1.9781611977073.4.

Enlaces externos

• Una descripción general de las publicaciones sobre el aprendizaje de algoritmos aumentados.