Hispanopedia Wiki
Articulo de referencia

Algoritmo de aprendizaje aumentado

Un algoritmo de aprendizaje aumentado (también llamado algoritmo con predicciones) es un algoritmo que puede utilizar una predicción para mejorar su rendimiento. [ 1 ] Mientras ...

Hispanopedia WikiContenido en espanolLectura gratuita

Un algoritmo de aprendizaje aumentado (también llamado algoritmo con predicciones) es un algoritmo que puede utilizar una predicción para mejorar su rendimiento. [ 1 ] Mientras que en los algoritmos regulares solo se introduce 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. Esta predicción es utilizada por el algoritmo para mejorar su tiempo de ejecución o la calidad de su resultado. La aplicación más común son los algoritmos en línea , donde se proporciona una predicción sobre la instancia incierta.

Descripción

Un algoritmo de aprendizaje aumentado normalmente toma una entrada(I,A){\displaystyle ({\mathcal {I}},{\mathcal {A}})}. AquíI{\displaystyle {\mathcal {I}}}es una instancia problemática yA{\displaystyle {\mathcal {A}}}es la predicción. Una predicción puede ser cualquier objeto. Los tipos más comunes son los siguientes:

  • Predicción de una solución óptima. La predicción proporciona una solución al problema o caracteriza una solución óptima.
  • Predicción de la entrada. Esto se utiliza principalmente para problemas en línea .
  • Predicción de acciones algorítmicas. Una predicción adaptada a un algoritmo específico que sugiere una ejecución específica del mismo.

Los algoritmos de aprendizaje aumentado suelen satisfacer las siguientes tres propiedades: [ 1 ]

  • 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.
  • Suavidad. Un algoritmo de aprendizaje aumentado se considera suave si su rendimiento puede acotarse mediante una función de la calidad de la predicción. En este caso, la calidad puede medirse de una manera específica para cada problema. Esto también se conoce como error de predicción.
  • Robustez. Un algoritmo de aprendizaje aumentado se denomina robusto si su rendimiento en el peor de los casos puede acotarse incluso si la predicción dada es inexacta.

Los algoritmos de aprendizaje aumentado generalmente no prescriben cómo debe realizarse la predicción. Para ello, se puede utilizar el aprendizaje automático .

Aplicaciones

A continuación se presentan algunos ejemplos de problemas en los que se han aplicado algoritmos de aprendizaje aumentado.

Algoritmos en línea

Arranque en caliente

Estructuras de datos

El algoritmo de búsqueda binaria es un algoritmo para encontrar elementos de una lista ordenada.incógnita1,…,incógnitanorte{\displaystyle x_{1},\ldots ,x_{n}}. Se necesitaO(registro⁡(norte)){\displaystyle O(\log(n))}pasos para encontrar un elemento con algún valor conocidoy{\displaystyle y}en una lista de longitudnorte{\displaystyle n}Con una prediccióni{\displaystyle i}para el puesto dey{\displaystyle y}, se puede utilizar el siguiente algoritmo de aprendizaje aumentado. [ 1 ]

  • Primero, observe la posición.i{\displaystyle i}en la lista. Siincógnitai=y{\displaystyle x_{i}=y}El elemento ha sido encontrado.
  • Siincógnitai<y{\displaystyle x_{i}<y}, observe las posicionesi+1,i+2,i+4,…{\displaystyle i+1,i+2,i+4,\ldots }hasta que un índicej{\displaystyle j}conincógnitaj≥y{\displaystyle x_{j}\geq y}se encuentra.
    • Ahora realiza una búsqueda binaria enincógnitai,…,incógnitaj{\displaystyle x_{i},\ldots ,x_{j}}.
  • Siincógnitai>y{\displaystyle x_{i}>y}, haga lo mismo que en el caso anterior, pero en su lugar considerei−1,i−2,i−4,…{\displaystyle i-1,i-2,i-4,\ldots }.

El error se define comoη=|i−i∗|{\displaystyle \eta =|ii^{*}|}, dóndei∗{\displaystyle i^{*}}es el índice real dey{\displaystyle y}. En el algoritmo de aprendizaje aumentado, sondeando las posicionesi+1,i+2,i+4,…{\displaystyle i+1,i+2,i+4,\ldots }aceptaregistro2⁡(η){\displaystyle \log _{2}(\eta )}pasos. Luego se realiza una búsqueda binaria en una lista de tamaño como máximo2η{\displaystyle 2\eta }, que tomaregistro2⁡(η){\displaystyle \log _{2}(\eta )}pasos. Esto hace que el tiempo total de ejecución del algoritmo2registro2⁡(η){\displaystyle 2\log _{2}(\eta )}Por lo tanto, cuando el error es pequeño, el algoritmo es más rápido que una búsqueda binaria normal. Esto demuestra que el algoritmo es consistente. Incluso en el peor de los casos, el error será como máximonorte{\displaystyle n}. Entonces el algoritmo toma como máximoO(registro⁡(norte)){\displaystyle O(\log(n))}pasos, por lo que el algoritmo es robusto.

Más ejemplos

Algoritmos de aproximación

Diseño de mecanismos

Véase también

Referencias

  1. 1 2 3 Mitzenmacher, Michael ; Vassilvitskii, Sergei (31 de diciembre de 2020). «Algoritmos con predicciones». Más allá del análisis del peor caso de los algoritmos . Cambridge University Press. págs. 646–662 . arXiv : 2006.09123 . doi : 10.1017/9781108637435.037 . ISBN  978-1-108-63743-5.
  2. ↑ Purohit, Manish; Svitkina, Zoya; Kumar, Ravi (2018). "Mejora de algoritmos en línea mediante predicciones de aprendizaje automático" . Advances in Neural Information Processing Systems 31 (NeurIPS 2018) . Montreal, Canadá. pp. 9684–9693 . Consultado el 18 de diciembre de 2025 . 
  3. ↑ Bansal, Nikhil; Coester, Christian; Kumar, Ravi; Purohit, Manish; Vee, Erik (enero de 2022). «Paginación ponderada aumentada por aprendizaje». Actas del Simposio Anual ACM-SIAM de 2022 sobre Algoritmos Discretos (SODA) . Sociedad de Matemáticas Industriales y Aplicadas. págs. 67–89 . doi : 10.1137/1.9781611977073.4 . ISBN  978-1-61197-707-3.
  4. ↑ Bamas, Étienne; Maggiori, Andreas; Svensson, Ola (2020). "El método primal-dual para el aprendizaje de algoritmos aumentados" . Advances in Neural Information Processing Systems 33 (NeurIPS 2020) . Conferencia virtual . Recuperado el 18 de diciembre de 2025 .
  5. ↑ Grigorescu, Elena; Lin, Young-San; Silwal, Sandeep; Song, Maoyuan; Zhou, Samson (2022). "Algoritmos aumentados por aprendizaje para programación lineal y semidefinida en línea". arXiv : 2209.10614 [ cs ].
  6. ↑ Im, Sungjin; Kumar, Ravi; Montazer Qaem, Mahshid; Purohit, Manish (2021). "Programación no clarividente con predicciones" . Actas del 33.er Simposio ACM sobre paralelismo en algoritmos y arquitecturas (SPAA 2021) . Conferencia virtual, EE. UU.: ACM. págs. 285–294 . doi : 10.1145/3409964.3461790 . Recuperado el 18 de diciembre de 2025 . 
  7. ↑ Lindermayr, Alexander; Megow, Nicole (2025). "Predicciones de permutación para la planificación no clarividente" . ACM Transactions on Parallel Computing . 12 (2). ACM: 4:1–4:26. ​​doi : 10.1145/3711872 . Recuperado el 18 de diciembre de 2025 .
  8. ↑ Jin, Billy; Ma, Will (2022). "Emparejamiento bipartito en línea con asesoramiento: compensaciones estrictas entre robustez y consistencia para el modelo de dos etapas" . Advances in Neural Information Processing Systems 35 (NeurIPS 2022) . Nueva Orleans, Luisiana, Estados Unidos . Consultado el 18 de diciembre de 2025 .
  9. ↑ Dinitz, Michael; Im, Sungjin; Lavastida, Thomas; Benjamin, Benjamin; Vassilvitskii, Sergei (2021). "Emparejamientos más rápidos mediante duales aprendidos". Avances en sistemas de procesamiento de información neuronal (PDF) . Curran Associates, Inc.
  10. ↑ Cohen-Addad, Vincent; d'Orsi, Tommaso; Gupta, Anupam; Lee, Euiwoong; Panigrahi, Debmalya (2024). "Algoritmos de aproximación con aprendizaje aumentado para el problema del corte máximo y problemas relacionados" . Advances in Neural Information Processing Systems 38 (NeurIPS 2024) . Vancouver, Columbia Británica, Canadá . Recuperado el 18 de diciembre de 2025 .
  11. ↑ Antoniadis, Antonios; Eliás, Marek; Polak, Adam; Venzin, Moritz (2025). "Algoritmos de aproximación para la optimización combinatoria con predicciones" . Actas de la Decimotercera Conferencia Internacional sobre Representaciones de Aprendizaje (ICLR 2025) . Singapur: OpenReview . Consultado el 18 de diciembre de 2025 .
  12. ↑ Agrawal, Priyank; Balkanski, Eric; Gkatzelis, Vasilis; Ou, Tingting; Tan, Xizhi (2024). "Diseño de mecanismos aumentados por aprendizaje: aprovechamiento de predicciones para la ubicación de instalaciones" . Matemáticas de la investigación operativa . 49 (4). INFORMS: 2626–2651 . doi : 10.1287/MOOR.2022.0225 . Recuperado el 18 de diciembre de 2025 .
  • Panorama general de las publicaciones sobre algoritmos de aprendizaje aumentado