Las redes neuronales han sido durante mucho tiempo herramientas poderosas para manejar tareas complejas basadas en datos. Aún así, a menudo luchan por tomar decisiones discretas bajo limitaciones estrictas, como enrutar vehículos o programas de programación. Estos problemas de decisión discretos, comúnmente encontrados en la investigación de operaciones, son computacionalmente intensivos y difíciles de integrar en los marcos suaves y continuos de las redes neuronales. Tales desafíos limitan la capacidad de combinar modelos basados en el aprendizaje con razonamiento combinatorial, creando un cuello de botella en aplicaciones que exigen ambas.
Un problema importante surge al integrar solucionadores combinatorios discretos con sistemas de aprendizaje basados en gradientes. Muchos problemas combinatorios son NP-Hard, lo que significa que es imposible encontrar soluciones exactas en un tiempo razonable para grandes casos. Las estrategias existentes a menudo dependen de solucionadores exactos o introducen relajaciones continuas, lo que puede no proporcionar soluciones que respeten las limitaciones difíciles del problema original. Estos enfoques generalmente implican costos computacionales fuertes, y cuando los oráculos exactos no están disponibles, los métodos no logran entregar gradientes consistentes para el aprendizaje. Esto crea una brecha donde las redes neuronales pueden aprender representaciones, pero no pueden tomar decisiones complejas y estructuradas de una manera que escala.
Los métodos de uso común se basan en solucionadores exactos para tareas de inferencia estructurada, como solucionadores de mapas en modelos gráficos o relajaciones de programación lineal. Estos métodos a menudo requieren repetidas llamadas de Oracle durante cada iteración de capacitación y dependen de formulaciones de problemas específicas. Las técnicas como pérdidas de fenchel-young o métodos basados en perturbaciones permiten un aprendizaje aproximado, pero sus garantías se descomponen cuando se usan con solucionadores inexactos como las heurísticas de búsqueda locales. Esta dependencia de las soluciones exactas obstaculiza su uso práctico en tareas combinatorias de mundo real a gran escala, como el enrutamiento de vehículos con solicitudes dinámicas y ventanas de tiempo.
Investigadores de Google Deepmind y ENPC proponen una solución novedosa al transformar las heurísticas de búsqueda locales en capas combinatorias diferenciables a través de la lente de los métodos de la cadena Markov Monte Carlo (MCMC). Los investigadores crean capas MCMC que operan en espacios combinatorios discretos al mapear sistemas de vecindad específicos de problemas en distribuciones de propuestas. Este diseño permite a las redes neuronales integrar las heurísticas de búsqueda locales, como el recocido simulado o las aguas de metrópolis, como parte de la tubería de aprendizaje sin acceso a solucionadores exactos. Su enfoque permite el aprendizaje basado en el gradiente sobre soluciones discretas mediante el uso de reglas de aceptación que corrigen el sesgo introducido por los solucionadores aproximados, asegurando la solidez teórica al tiempo que reduce la carga computacional.
Con más detalle, los investigadores construyen un marco en el que las heurísticas de búsqueda locales proponen soluciones de vecinos basados en la estructura del problema, y las reglas de aceptación de los métodos MCMC aseguran que estos movimientos dan como resultado un proceso de muestreo válido sobre el espacio de la solución. La capa de MCMC resultante se aproxima a la distribución objetivo de soluciones factibles y proporciona gradientes imparciales para una sola iteración bajo una pérdida de yung de Fenchel dependiente del objetivo. Esto permite realizar el aprendizaje incluso con iteraciones mínimas de MCMC, como usar una sola muestra por pase hacia adelante mientras se mantiene las propiedades de convergencia teórica. Al integrar esta capa en una red neuronal, pueden entrenar modelos que predicen los parámetros para problemas combinatorios y mejoran la calidad de la solución con el tiempo.
El equipo de investigación evaluó este método en un problema de enrutamiento de vehículos dinámicos a gran escala con ventanas de tiempo, una compleja tarea de optimización combinatoria del mundo real. Mostraron que su enfoque podría manejar grandes instancias de manera eficiente, superando significativamente los métodos basados en perturbaciones bajo presupuestos de tiempo limitado. Por ejemplo, su capa MCMC logró un costo relativo de prueba de 5.9% en comparación con las líneas de base anticipadas cuando se usa una inicialización basada en heurística. En comparación, el método basado en la perturbación logró 6.3% en las mismas condiciones. Incluso a presupuestos de tiempo extremadamente bajos, como un límite de tiempo de 1 ms, su método superó a los métodos de perturbación superiores a un gran margen, lo que alcanza el 7.8% de costo relativo versus 65.2% para los enfoques basados en perturbaciones. También demostraron que inicializar la cadena MCMC con soluciones de verdad en tierra o estados heurísticos mejorados mejoró la eficiencia del aprendizaje y la calidad de la solución, especialmente cuando se usa un pequeño número de iteraciones de MCMC.
Esta investigación demuestra una forma de principios de integrar problemas combinatorios de NP-Hard en redes neuronales sin depender de solucionadores exactos. El problema de combinar el aprendizaje con la toma de decisiones discretas se aborda mediante el uso de capas MCMC construidas a partir de heurísticas de búsqueda locales, permitiendo una capacitación teóricamente sólida y eficiente. El método propuesto une la brecha entre aprendizaje profundo y optimización combinatoria, proporcionando una solución escalable y práctica para tareas complejas como el enrutamiento del vehículo.
Mira el Papel. Todo el crédito por esta investigación va a los investigadores de este proyecto. Además, siéntete libre de seguirnos Gorjeo Y no olvides unirte a nuestro 95k+ ml de subreddit y suscribirse a Nuestro boletín.
Nikhil es consultor interno en MarktechPost. Está buscando un doble grado integrado en materiales en el Instituto Indio de Tecnología, Kharagpur. Nikhil es un entusiasta de AI/ML que siempre está investigando aplicaciones en campos como biomateriales y ciencias biomédicas. Con una sólida experiencia en la ciencia material, está explorando nuevos avances y creando oportunidades para contribuir.