Screenshot 2024 06 02 At 11.53.38 Pm.png

Numerosos modelos innovadores, incluidos ChatGPT, Bard, LLaMa, AlphaFold2 y Dall-E 2, han surgido en diferentes dominios desde el inicio de Transformer en el procesamiento del lenguaje natural (NLP). Los intentos de resolver problemas de optimización combinatoria como el problema del viajante (TSP) utilizando el aprendizaje profundo han progresado lógicamente desde redes neuronales convolucionales (CNN) hasta redes neuronales recurrentes (RNN) y, finalmente, modelos basados ​​en transformadores. Utilizando las coordenadas de N ciudades (nodos, vértices, tokens), TSP determina el ciclo hamiltoniano más corto que pasa por cada nodo. La complejidad computacional crece exponencialmente con el número de ciudades, lo que la convierte en una cuestión representativa de NP-difícil en informática.

Se han utilizado varias heurísticas para abordar esto. Los algoritmos de mejora iterativos y los algoritmos estocásticos son las dos categorías principales bajo las cuales se encuentran los algoritmos heurísticos. Ha habido mucho esfuerzo, pero todavía no se puede comparar con los mejores algoritmos heurísticos. El desempeño del Transformador es crucial ya que es el motor que resuelve los problemas de las tuberías; sin embargo, esto es análogo a AlphaGo, que no era lo suficientemente potente por sí solo, pero venció a los mejores profesionales del mundo al combinar técnicas de búsqueda de posprocesamiento como Monte Carlo Tree Search (MCTS). Elegir la próxima ciudad a visitar, dependiendo de las que ya se han visitado, es el núcleo de TSP, y Transformer, un modelo que intenta descubrir relaciones entre nodos utilizando mecanismos de atención, es una buena opción para esta tarea. Debido a su diseño original para modelos de lenguaje, Transformer ha presentado desafíos metafóricos en estudios previos cuando se aplicó al dominio TSP.

Entre las muchas distinciones entre el transformador de dominio del lenguaje y el transformador de dominio TSP está la importancia de los tokens. Las palabras y sus subpalabras se consideran tokens en el ámbito de los idiomas. Por otro lado, en el dominio TSP, cada nodo suele convertirse en un token. A diferencia de una colección de palabras, el conjunto de coordenadas de números reales de los nodos es infinito, impredecible y desconectado. Los índices de tokens y el vínculo espacial entre tokens vecinos son inútiles en esta disposición. La duplicación es otra distinción importante. En cuanto a las soluciones TSP, a diferencia de los dominios lingüísticos, no se puede formar un ciclo hamiltoniano decodificando la misma ciudad más de una vez. Durante la decodificación TSP, se utiliza una máscara visitada para evitar repeticiones.

Investigadores de la Universidad Nacional de Seúl presentan CycleFormer, una solución TSP basada en transformadores. En este modelo, los investigadores combinan las mejores características de un Transformer basado en un modelo de lenguaje de aprendizaje supervisado (SL) con las de un TSP. Los solucionadores de TSP basados ​​en transformadores de corriente son limitados ya que están entrenados con RL. Esto les impide aprovechar plenamente las ventajas de SL, como un entrenamiento más rápido gracias a la máscara visitada y una convergencia más estable. La dureza NP del TSP hace imposible que los solucionadores de SL óptimos conozcan el óptimo global a medida que el tamaño de los problemas aumenta demasiado. Sin embargo, esta limitación puede evitarse si un transformador entrenado para problemas de tamaño razonable es generalizable y escalable. En consecuencia, por el momento coexistirán SL y RL.

El énfasis exclusivo del equipo está en el TSP simétrico, definido por la distancia entre dos puntos cualesquiera y es constante en todas las direcciones. Cambiaron sustancialmente el diseño original para garantizar que el transformador incorpore las propiedades del TSP. Debido a que la solución TSP es cíclica, se aseguraron de que su codificación posicional (PE) del lado del decodificador fuera insensible a la rotación y la inversión. Por lo tanto, el nodo inicial está muy relacionado con los nodos al principio y al final del recorrido, pero muy poco relacionado con los nodos en el medio.

Los investigadores utilizan las coordenadas 2D del codificador para la codificación posicional espacial. Las incrustaciones posicionales utilizadas por el codificador y el decodificador son completamente diferentes. La incrustación de contexto (memoria) de la salida del codificador sirve como entrada al decodificador. Para maximizar rápidamente el uso de la información adquirida, esta estrategia aprovecha el hecho de que el conjunto de tokens utilizados en el codificador y el decodificador es el mismo en TSP. Cambian la última capa lineal del Transformer con una incrustación dinámica; esta es la codificación de contexto del gráfico y actúa como salida (memoria) del codificador.

El uso de incrustación posicional e incrustación de tokens, así como el cambio de la entrada del decodificador y la explotación del vector de contexto del codificador en la salida del decodificador, son dos formas en las que CycleFormer difiere dramáticamente del Transformer original. Estas mejoras demuestran el potencial de los solucionadores de TSP basados ​​en transformadores para mejorar mediante la adopción de estrategias de mejora del rendimiento empleadas en modelos de lenguaje grande (LLM), como aumentar la dimensión de incrustación y el número de bloques de atención. Esto pone de relieve los desafíos actuales y las interesantes posibilidades para futuros avances en este campo.

Según extensos resultados experimentales, con estas características de diseño, CycleFormer puede superar a los modelos SOTA basados ​​en transformadores manteniendo la forma del transformador en TSP-50, TSP-100 y TSP-500. La ‘brecha de optimización’, un término utilizado para medir la diferencia entre la mejor solución posible y la solución encontrada por el modelo, entre SOTA y TSP-500 durante la decodificación de inicio múltiple es del 3,09% al 1,10%, una mejora de 2,8 veces. gracias a CycleFormer.

El modelo propuesto, CycleFormer, tiene el potencial de superar las alternativas SOTA como Pointerformer. Su adherencia a la arquitectura del transformador permite la inclusión de enfoques LLM adicionales, como aumentar la dimensión de incrustación y apilar múltiples bloques de atención, para mejorar el rendimiento. A medida que aumenta el tamaño del problema, los métodos de aceleración de inferencia en grandes modelos de lenguaje, como Retention y DeepSpeed, pueden resultar ventajosos. Si bien los investigadores no pudieron experimentar con TSP-1000 debido a limitaciones de recursos, creen que con suficientes respuestas óptimas de TSP-1000, CycleFormer podría superar a los modelos existentes. Planean incorporar MCTS como un paso de posprocesamiento en estudios futuros para mejorar aún más el rendimiento de CycleFormer.


Revisar la Papel. Todo el crédito por esta investigación va a los investigadores de este proyecto. Además, no olvides seguirnos en Gorjeo. Únete a nuestro Canal de telegramas, Canal de discordiay LinkedIn Grarriba.

Si te gusta nuestro trabajo, te encantará nuestro Boletin informativo..

No olvides unirte a nuestro SubReddit de 43k+ ML | Además, consulte nuestro Plataforma de eventos de IA


Dhanshree Shenwai es ingeniero en informática y tiene una buena experiencia en empresas de tecnología financiera que cubren el ámbito financiero, tarjetas y pagos y banca con un gran interés en las aplicaciones de IA. Le entusiasma explorar nuevas tecnologías y avances en el mundo en evolución de hoy que facilita la vida de todos.