Науковці з Університету Берклі взялися за навчання штучного інтелекту розв'язуванню кросвордів та представили нового переможця Американського кросвордного турніру. Berkeley Crossword Solver майже не піддається на гру слів та долає до 81,7 відсотка головоломок, не пропускаючи і не плутаючи літери майже у 100 відсотках випадків. Про успіхи BCS розробники повідомили у блозі своєї лабораторії.
GIPHY
Навіщо штучному інтелекту кросворди?
Після того, як штучний інтелект розібрався з купою ігор від шахів до Dota 2 і навіть розв'язав проблему згортання білків для біологів, може здатися, що кросворди є чимось на кшталт відпочинку для розробників, однак ні. Мовна гра, яка передбачає заповнення клітинок словами за підказками, є однією з найпопулярніших подібних, вимагає не тільки широких знань з різних тем і розуміння гри слів, а і необхідності замислюватися над кількома відповідями, що можуть перетинатися.
Тож для штучного інтелекту кросворди — це відмінний полігон для розучування мовних навичок. І йому доволі пощастило, що кросворди чи не щодня публікуються у журналах і газетах, а найбільш досвідчені їх американські прихильники ще і щороку змагаються на турнірі American Crossword Puzzle Tournament, де найкращі учасники вгадують понад 100 слів за три хвилини. Новий Berkeley Crossword Solver від розробників з Університету Берклі — не перший алгоритм на теренах мистецтва розв'язування кросвордів. Однак новий підхід дослідників з відділу досліджень штучного інтелекту університету (Berkeley Artificial Intelligence Research) забезпечив йому достатню точність, щоб обійти гравців Американського турніру з розв'язування кросвордів.
Як алгоритми розв'язують кросворди?
Оскільки розв'язування кросвордів навіть алгоритмами виходить за рамки простого генерування відповідей на кожну підказку, Berkeley Crossword Solve довелося навчити додатковим обмеженням. Так спочатку він генерував відповіді для кожного питання незалежно, заповнюючи головоломку, а потім перебирав їх наново, враховуючи обмеження щодо кількості символів та слова, що перетинаються.
Ключовим на першому етапі є те, що алгоритм не шукає остаточної відповіді, а просто підбирає кандидатів, щоб погодити їх пізніше. Формально розв'язання кросворда є завданням із задоволення обмежень, що максимізує загальну кількість правильних слів і літер у розв'язку, і навіть дає змогу уникнути рішень, які можуть мати хибно високі оцінки з погляду подібності відповіді питанню (опису слова). Навчали алгоритм на наборі даних з більш ніж шести мільйонів пар запитань і відповідей, який варіюється за авторами, охоплює понад 70 років культурного контексту, і містить приклади, які є важкими навіть для досвідчених у вирішенні кросвордів людей.
Схема роботи Berkeley Crossword Solver. Eric Wallace et al.
Як справився Berkeley Crossword Solve?
На момент публікації результатів роботи нового Berkeley Crossword Solve найуспішнішими у розв'язуванні кросвордів системами були Proverb, яка зайняла 213 місце з 252 у турнірі 1998 року та Dr. Fill із 43 місцем. Dr. Fill вдавалося розв'язати до 57 відсотків кросвордів із журналу The New York Times, однак у Berkeley Crossword Solve це вже 82 відсотки та перше місце у турнірі з 12 825 балами порівняно із 12 810 у найкращого гравця.
Розробники оцінили Berkeley Crossword Solve на головоломках від п'яти великих видавців кросвордів, включаючи The New York Times. У результаті він впорався з відповідями (і правильно розставив літери у клітинки кросворда) в середньому в 99,7 відсотка випадків, причому якщо забрати вузькі теми, то його успіх збільшився до 99,9 відсотка. Без жодної помилки Berkeley Crossword Solve вирішив 81,7 відсотка головоломок, що на 24,8 відсотка краще, ніж Dr. Fill.
Втім, як зазначають вчені, успіхи алгоритму ще не означають, що кросворди повністю здалися під натиском технологій. Berkeley Crossword Solve погано справлявся зі словами з вузькоспеціалізованих тем, а також його іноді збивали з пантелику різні мовні явища, як-то багатозначні слова, наприклад.
Мова є складним і багатогранним явищем, яке потроху все ж здається штучному інтелекту. Так нейромережі тепер не лише більш менш прийнятно перекладають тексти чи навіть пишуть вірші, а і вчаться відповідати на питання розгорнуто, і при цьому підкріплювати свої відповіді посиланнями на джерела. Також беруть на себе зобов'язання читати за вас умови користування на сайтах та допомагати відновлювати втрачені фрагменти давньогрецьких текстів.