El solucionador de crucigramas de Berkeley: el blog de investigación de inteligencia artificial de Berkeley


Recientemente publicamos Berkeley Crossword Solver (BCS), el estado actual del arte para resolver crucigramas al estilo americano. El BCS combina la respuesta a preguntas neuronales y la inferencia probabilística para lograr un rendimiento casi perfecto en la mayoría de los crucigramas de estilo estadounidense, como el que se muestra a continuación:



Figura 1: Ejemplo de crucigrama estilo americano

Una versión anterior del BCS, junto con Dr.Fill, fue el primer programa de computadora en superar a todos los competidores humanos en el torneo de crucigramas más importante del mundo. La versión más reciente es el sistema actual de mayor rendimiento en crucigramas de The New York Times, que logra una precisión de letra del 99,7 % (consulte la documento técnico, demostración weby liberación de código).

Los crucigramas son un desafío tanto para los humanos como para las computadoras. Muchas pistas son vagas o no están bien especificadas y no se pueden responder hasta que se tengan en cuenta las restricciones de cruce. Si bien algunas pistas son similares a la respuesta a preguntas factoides, otras requieren un razonamiento relacional o la comprensión de juegos de palabras difíciles.

Aquí hay un puñado de pistas de ejemplo de nuestro conjunto de datos (respuestas al final de esta publicación):

  • Se entregan en la Escuela HAAS de Berkeley (4)
  • horario de invierno en Berkeley (3)
  • Ender de dominio que UC Berkeley fue una de las primeras escuelas en adoptar (3)
  • Angeleno en Berkeley, digamos (8)

El BCS utiliza un proceso de dos pasos para resolver crucigramas. Primero, genera una distribución de probabilidad sobre las posibles respuestas a cada pista utilizando un modelo de pregunta y respuesta (QA); en segundo lugar, utiliza la inferencia probabilística, combinada con la búsqueda local y un modelo de lenguaje generativo, para manejar los conflictos entre las respuestas de intersección propuestas.



Figura 2: Diagrama de arquitectura del Berkeley Crossword Solver

El modelo de respuesta a preguntas de BCS se basa en DPR (Karpukhin et al., 2020), que es un modelo de dos codificadores que generalmente se usa para recuperar pasajes que son relevantes para una pregunta determinada. Sin embargo, en lugar de pasajes, nuestro enfoque mapea tanto las preguntas como las respuestas en un espacio integrado compartido y encuentra las respuestas directamente. En comparación con el método de vanguardia anterior para responder a las pistas de los crucigramas, este enfoque obtuvo una mejora absoluta del 13,4 % en la precisión del control de calidad de los 1000 principales. Realizamos un análisis manual de errores y descubrimos que nuestro modelo de control de calidad generalmente funcionaba bien en preguntas relacionadas con el conocimiento, el razonamiento de sentido común y las definiciones, pero a menudo tenía dificultades para comprender los juegos de palabras o las pistas relacionadas con el tema.

Después de ejecutar el modelo de control de calidad en cada pista, el BCS ejecuta una propagación de creencias en bucle para actualizar iterativamente las probabilidades de respuesta en la cuadrícula. Esto permite que la información de las predicciones de alta confianza se propague a pistas más desafiantes. Después de que converge la propagación de la creencia, el BCS obtiene una solución inicial del acertijo tomando con avidez la respuesta de mayor probabilidad en cada posición.

Luego, el BCS refina esta solución mediante una búsqueda local que intenta reemplazar los caracteres de baja confianza en la cuadrícula. La búsqueda local funciona mediante el uso de una distribución de propuesta guiada en la que los caracteres que tenían probabilidades marginales más bajas durante la propagación de creencias se reemplazan iterativamente hasta que se encuentra una solución óptima localmente. Calificamos estos caracteres alternativos utilizando un modelo de lenguaje a nivel de carácter (ByT5, Xue et al., 2022), que maneja las respuestas novedosas mejor que nuestro modelo de control de calidad de libro cerrado.



Figura 3: Ejemplo de cambios realizados por nuestro procedimiento de búsqueda local

Evaluamos el BCS en crucigramas de cinco importantes editores de crucigramas, incluido The New York Times. Nuestro sistema obtiene una precisión de letra del 99,7 % en promedio, que salta al 99,9 % si ignora los acertijos que involucran temas raros. Resuelve el 81,7 % de los acertijos sin un solo error, lo que supone una mejora del 24,8 % con respecto al anterior sistema de última generación.



Figura 4: Resultados comparados con Dr.Fill de última generación anterior

El American Crossword Puzzle Tournament (ACPT) es el torneo de crucigramas más grande y de mayor duración y está organizado por Will Shortz, el editor de crucigramas del New York Times. Dos enfoques previos a la resolución de crucigramas por computadora atrajeron la atención general y compitieron en el ACPT: Proverb y Dr.Fill. Proverb es un sistema de 1998 que ocupó el puesto 213 entre 252 competidores en el torneo. La primera competencia de Dr.Fill fue en ACPT 2012 y ocupó el puesto 141 entre 650 competidores. Nos asociamos con el creador de Dr.Fill, Matt Ginsberg, y combinamos una versión anterior de nuestro sistema de control de calidad con el procedimiento de búsqueda de Dr.Fill para superar a los 1033 competidores humanos en el ACPT de 2021. Nuestra presentación conjunta resolvió los siete acertijos en menos de un minuto, y solo faltaron tres letras en dos acertijos.



Figura 5: Resultados del Torneo Americano de Crucigramas 2021 (ACPT)

Estamos realmente entusiasmados con los desafíos que quedan en los crucigramas, incluido el manejo de temas difíciles y juegos de palabras más complejos. Para alentar el trabajo futuro, estamos publicando un conjunto de datos de 6,4 millones de pistas de respuestas a preguntas, una demostración de Berkeley Crossword Solver y nuestro código en http://berkeleycrosswordsolver.com.

Respuestas a las pistas: MBAS, PST, EDU, INSTATER

Fuente del artículo

Deja un comentario