Nous avons récemment publié le Berkeley Crossword Solver (BCS), l’état actuel de l’artwork pour résoudre les mots croisés à l’américaine. Le BCS mix la réponse aux questions neurales et l’inférence probabiliste pour obtenir des performances presque parfaites sur la plupart des mots croisés de type américain, comme celui illustré ci-dessous :
Determine 1 : Exemple de mots croisés à l’américaine
Une model antérieure du BCS, en collaboration avec Dr.Fill, a été le premier programme informatique à surpasser tous les concurrents humains dans le meilleur tournoi de mots croisés au monde. La model la plus récente est le système actuel le plus performant sur les mots croisés du New York Instances, atteignant 99,7 % de précision des lettres (voir le doc approach, démo Internetet libération de code).
Les mots croisés sont difficiles pour les humains et les ordinateurs. De nombreux indices sont vagues ou sous-spécifiés et ne peuvent être répondus tant que les contraintes de croisement ne sont pas prises en compte. Alors que certains indices sont similaires à la réponse aux questions factoïdes, d’autres nécessitent un raisonnement relationnel ou la compréhension de jeux de mots difficiles.
Voici quelques exemples d’indices tirés de notre ensemble de données (réponses au bas de cet article) :
- Ils sont distribués à l’école HAAS de Berkeley (4)
- Heures d’hiver. à Berkeley (3)
- Area ender que l’UC Berkeley a été l’une des premières écoles à adopter (3)
- Angeleno à Berkeley, disons (8)
Le BCS utilise un processus en deux étapes pour résoudre les mots croisés. Premièrement, il génère une distribution de probabilité sur les réponses possibles à chaque indice à l’aide d’un modèle de question-réponse (QA); deuxièmement, il utilise l’inférence probabiliste, combinée à la recherche locale et à un modèle de langage génératif, pour gérer les conflits entre les réponses croisées proposées.
Determine 2 : Schéma d’structure du solveur de mots croisés de Berkeley
Le modèle de réponse aux questions du BCS est basé sur le DPR (Karpukhin et al., 2020), qui est un modèle bi-encodeur généralement utilisé pour récupérer des passages pertinents pour une query donnée. Plutôt que des passages, cependant, notre approche cartographie à la fois les questions et les réponses dans un espace d’intégration partagé et trouve des réponses directement. Par rapport à la méthode de pointe précédente pour répondre aux indices de mots croisés, cette approche a obtenu une amélioration absolue de 13,4 % de la précision des 1000 meilleurs QA. Nous avons effectué une analyse manuelle des erreurs et constaté que notre modèle d’assurance qualité fonctionnait généralement bien sur les questions impliquant des connaissances, un raisonnement de bon sens et des définitions, mais qu’il avait souvent du mal à comprendre les jeux de mots ou les indices liés au thème.
Après avoir exécuté le modèle QA sur chaque indice, le BCS exécute une propagation de croyance en boucle pour mettre à jour de manière itérative les probabilités de réponse dans la grille. Cela permet aux informations provenant de prédictions à haute confiance de se propager à des indices plus difficiles. Après la convergence de la propagation des croyances, le BCS obtient une answer de puzzle initiale en prenant avidement la réponse de probabilité la plus élevée à chaque place.
Le BCS affine ensuite cette answer à l’aide d’une recherche locale qui tente de remplacer les caractères à faible confiance dans la grille. La recherche locale fonctionne en utilisant une distribution de proposition guidée dans laquelle les caractères qui avaient des probabilités marginales plus faibles pendant la propagation des croyances sont remplacés de manière itérative jusqu’à ce qu’une answer localement optimale soit trouvée. Nous évaluons ces caractères alternatifs à l’aide d’un modèle de langage au niveau des caractères (ByT5, Xue et al., 2022), qui gère mieux les nouvelles réponses que notre modèle d’assurance qualité à livre fermé.
Determine 3 : Exemple de modifications apportées par notre procédure de recherche locale
Nous avons évalué le BCS sur les puzzles de cinq grands éditeurs de mots croisés, dont le New York Instances. Notre système obtient une précision des lettres de 99,7 % en moyenne, qui passe à 99,9 % si vous ignorez les puzzles qui impliquent des thèmes rares. Il résout 81,7 % des énigmes sans une seule erreur, ce qui représente une amélioration de 24,8 % par rapport au système de pointe précédent.
Determine 4 : Résultats comparés à l’état de l’artwork précédent Dr.Fill
L’American Crossword Puzzle Event (ACPT) est le tournoi de mots croisés le plus vital et le plus ancien et est organisé par Will Shortz, l’éditeur de mots croisés du New York Instances. Deux approches antérieures de la résolution de mots croisés par ordinateur ont attiré l’consideration du grand public et ont concouru dans l’ACPT : Proverb et Dr.Fill. Proverb est un système de 1998 qui s’est classé 213e sur 252 concurrents du tournoi. Le premier concours de Dr.Fill a eu lieu à l’ACPT 2012, et il s’est classé 141e sur 650 concurrents. Nous nous sommes associés au créateur de Dr.Fill, Matt Ginsberg, et avons combiné une première model de notre système QA avec la procédure de recherche de Dr.Fill pour surpasser les 1033 concurrents humains dans l’ACPT 2021. Notre soumission conjointe a résolu les sept énigmes en moins d’une minute, ne manquant que trois lettres sur deux énigmes.
Determine 5 : Résultats du Tournoi américain de mots croisés 2021 (ACPT)
Nous sommes vraiment enthousiasmés par les défis qui restent dans les mots croisés, y compris la gestion de thèmes difficiles et des jeux de mots plus complexes. Pour encourager les travaux futurs, nous publions un ensemble de données de 6,4 hundreds of thousands d’indices de réponse aux questions, une démo du Berkeley Crossword Solver et notre code sur http://berkeleycrosswordsolver.com.
Réponses aux indices : MBAS, PST, EDU, INSTATER
