Интернет бросает вызов экспертам по кроссвордам


Кроссворды очень популярны и представляют собой полезную область исследований для современного искусственного интеллекта (ИИ). В отличие от решения других знаменитых игр (таких как шахматы), решение кроссвордов требует изменения парадигмы в сторону способности решать задачи, для которых людям требуются обширные семантические знания (сегодня в Интернете есть много сервисов облегчающих эту задачу, например, http://bezbukv.ru/scanwords/167/290/292/298/). В этой статье рассказывается о WebCrow, программы для автоматического решения кроссвордов, в котором необходимые знания добываются из Интернета: раскрытие ключей осуществляется главным образом путем доступа к сети через поисковые системы и применения методов обработки естественного языка. Основная идея WebCrow - использовать агент для онлайнового доступа в Интернет для решения кроссвордов - была упомянута в краткой новостной статье Франчески Кастеллани, «Program Cracks Crosswords», Nature, 6 октября 2004 года. В конкурсах на Европейской конференции по искусственному интеллекту (ECAI) в 2006 году и других конференциях этот веб-подход позволил WebCrow превзойти своих людей-соперников. Подобно тому, как шахматы когда-то называли «дрозофилой искусственного интеллекта», мы считаем, что системы кроссвордов могут быть полезны дрозофиле агентов, работающих в сети.

Игры и головоломки воспроизводят сложность реального мира с «наименьшими начальными структурами» (Minsky 1968), что делает их изучение важным как для теоретических, так и для практических задач. С момента рождения искусственного интеллекта (ИИ) играм и головоломкам уделялось большое внимание. Игра, которая привлекла наибольшее внимание компьютерных ученых, - это шахматы. Отцы-основатели ИИ, такие как Маккарти, Саймон (Simon and Schaeffer 1992), Сэмюэл, Шеннон (Shannon 1950), Тьюринг и фон Нейман, были вовлечены в автоматическую игру в шахматы. После десятилетий безуспешных попыток (Mittman and Newborn 1980, Munakata 1996), машина IBM Deep Blue достигла удивительного результата в победе над чемпионом мира Гари Каспаровым в мае 1997 года (Campbell, Hoane и Hsu 2002).

Игры играют роль лаборатории, где машины можно безопасно тестировать путем прямой конкуренции с людьми. Наряду с разработкой успешных игровых программ, исследование должно также включать методологическую дискуссию о том, как достигается эта производительность. Deep Blue в значительной степени полагался на вычислительную мощность, объединенную с алгоритмом поиска, основанным на статических функциях оценки, для оценки различных конфигураций игры. Вместо того, чтобы полагаться на заранее запрограммированный подход, Тесавро разработал TD-gammon (Tesauro 1994), сильный автоматический игрок в нарды, который использует идею обучения подкреплению. Эти исследования TD-gammmon оказали значительное влияние на другие области и области применения.

Работа с пословицами включала использование в веб-майнинга, но используемые подходы были почти полностью недокументированы. Веб-доступ лежит в основе WebCrow. Он в значительной степени не опирается ни на большие базы данных кроссвордов, ни на многие экспертные модули, относящиеся к конкретным доменам, но в первую очередь на интеллектуального агента, который работает в режиме онлайн на многоязычном веб-хранилище информации. Интересно, что динамическая эволюция сети влияет на поведение программы во времени, таким образом, автоматически реагируя на эволюцию человеческой культуры. Более того, благодаря веб-центрированной архитектуре WebCrow лучше подходит для работы с разными языками. Основной особенностью WebCrow на самом деле является модуль веб-поиска, который включает в себя специальную форму веб-ответов на вопросы. Модуль опирается на ядро ​​информационно-поисковых технологий, включая службу поисковой системы, и обработку естественного языка (Aravind 1991, Manning and Schütze 1999). Вместо того чтобы полагаться в основном на экспертные модули, цель WSM состоит в том, чтобы иметь дело с энциклопедическими знаниями, необходимыми во время процесса ответов на подсказки, подчеркивая таким образом роль ответов на вопросы, что является ключевым моментом во многих языковых играх, таких как Trivial Pursuit или Jeopardy. Идея использования веб-агента знаний также принята в Lam et al. (2003), в которой рассказывается об игре-викторине «Кто хочет стать миллионером?». В этой игре агенту приходится выбирать один ответ из небольшого числа возможных вариантов - функцию, которая смягчает сложность задачи. Несмотря на плохие результаты по «легким для человека» вопросам, таким как «Сколько ног у рыбы?», Машина все еще способна работать на среднем уровне человека с 70% правильных ответов. Хотя сеть имеет фундаментальное значение для процесса ответа, она мало помогает при освещении и организации «очевидных понятий повседневной жизни», таких как «у мужчин две лодыжки» или «у рыб нет ног». На самом деле, несмотря на свои размеры, Интернет, как правило, не в состоянии охватить эти основные понятия просто потому, что веб-сообщество состоит из людей, которые обычно не обмениваются тривиальными понятиями.

Решение кроссвордов выполняется двумя последовательными задачами: (1) ответить на подсказки, создав список кандидатов; (2) заполните головоломку с лучшей комбинацией ответов. Во время ответа на подсказку WebCrow анализирует подсказки, используя методы НЛП программирования на естественном языке, которые используются для координации ресурсов знаний и ранжирования всех найденных кандидатов для каждой подсказки. Программа использует Интернет (запрашивая Google), чтобы найти новые энциклопедические знания. Кроме того, есть ряд других экспертов, отвечающих на вопросы, которые обращаются к лингвистическим и опытным знаниям. После того, как эти экспертные модули обработают все подсказки, списки взвешенных ответов объединяются (в результате получается один единственный список на подсказку), и запускается модуль заполнения сетки. Во время процесса заполнения окончательная оценка ассоциируется с каждым кандидатом путем распространения вероятностей, предоставленных на этапе ответа на подсказку, по сети ограничений, определенной сеткой кроссвордов. Наконец, A * используется для генерации заполненной конфигурации с наибольшей суммой апостериорных вероятностей слова.

Выводы

Помимо интригующей задачи решения кроссвордов самой по себе, эксперименты, проведенные с WebCrow, иллюстрируют преимущества, извлекаемые из плодотворного взаимодействия с сетью и вытекающей из этого способности атаковать проблемы, которые для человека требуют глубоких семантических знаний. WebCrow не является критически зависимым от экспертных модулей и может работать с разными языками. Это связано с тем, что он сильно зависит от своей способности извлекать знания энциклопедии из Интернета.

WebCrow - это пример того, как системы искусственного интеллекта рисуют в Интернете свои знания. Это область активных исследований в ряде областей ИИ. Как писал Том Митчелл, «впервые в истории каждый компьютер имеет доступ к практически неограниченному и растущему текстовому корпусу» (Stone and Hirsh 2005), предоставляя большие возможности для майнинга с помощью систем ИИ (например, Etzioni [2007]) и помогая устранить узкое место в приобретении знаний (Hendler 2005).

Архитектура, принятая в WebCrow, может предлагать решения соответствующих проблем из разных дисциплин, от извлечения информации до когнитивной науки или от экономики до биологии. Исследования генов с использованием компьютерной лингвистики (Searls 2002) подчеркивают междисциплинарный интерес таких методов. Кроме того, интеллектуальные сетевые агенты могут оказать сильное влияние на поддержку научных исследований в различных дисциплинах (Bloom 1996). Например, ученый-робот (King et al. 2004) мог бы извлечь выгоду из приобретения биологических знаний из Интернета для генерирования функциональных геномных гипотез. Агенты, вдохновленные архитектурой WebCrow, могут автономно получать доступ и обрабатывать большие объемы онлайн-данных, чтобы стимулировать эффективные междисциплинарные спекуляции (см., Например, в Neuroscience, Voss [2001]).

Интересно, что поскольку шахматы известны как «дрозофила искусственного интеллекта» (McCarthy 1997), кроссворды могут быть дрозофилами интеллектуальных агентов, основанных на сети. Британские загадочные кроссворды были использованы для первого отбора знаменитой команды взлома кодов в Bletchley Park, которая способствовала рождению компьютеров. Теперь сетевые агенты могут сами решать кроссворды, и их автономные рассуждения в огромном веб-хранилище могут значительно помочь в решении реальных проблем.

Использованные источники

  1. Abney, S. 1997. Part-of-Speech Tagging and Partial Parsing. In Corpus-Based Methods in Language and Speech Processing, ed. S. Young and G. Bloothooft. Dortrecht, Holland: Kluwer Academic Publishers.

  2. Aravind, K. J. 1991. Natural Language Processing. Science 253(5025): 1242–1249.

  3. Bloom, F. E. 1996. An Internet Review: The Compleat Neuroscientist Scours the World Wide Web. Science 274(5290): 1104–1108.
  4. Bouzy, B., and Cazenave, T. 2001. Computer Go: An AI Oriented Survey. Artificial Intelligence 132(1): 39–103.
  5. Campbell, M., Jr.; Hoane, A. J.; and Hsu, F. H. 2002. Deep Blue. Artificial Intelligence 134(1–2): 57–83.
  6. Chakrabarti, S. 2002. Mining the Web: Discovering Knowledge from Hypertext Data. San Mateo, CA: Morgan Kauf- mann Publishers.
  7. Cook, S. A. 1983. An Overview of Computational Complexity. Communications of ACM 26(6): 400–408.
  8. Ernandes, M.; Angelini, G.; Gori, M. 2005. WebCrow: A WEB-based System for CROssWord Solving. In Proceedings of the Twentieth National Conference of Artificial Intelligence (AAAI-05), 1412–1417. Menlo Park, CA: AAAI Press.
  9. Etzioni, E. 2007. Machine Reading: Papers from the 2007 AAAI Spring Symposium. Technical Report SS-07-06, Association for the Advancement of Artificial Intelligence, Menlo Park, CA.
  10. Gelly, S., and Silver, D. 2007. Combining Online and Offline Knowledge in UCT. In Proceedings of the 24th international Conference on Machine Learning (ICML ‘07), 273–280. New York: Association for Computing Machinery.
  11. Harabagiu, S.; Moldovan, D.; Pasca, M.; Mihalcea, R.; Surdeanu, R.; Bunescu, R.; Girju, R.; Rus, V.; and Morarescu,P. 2000. FALCON: Boosting Knowledge for Answer Engines. In Proceedings of the Ninth Text Retrieval Conference (TREC-9). Washington, DC: National Institute of Standards and Technology.
  12. Hart, P. E.; Nilsson, N. J.; and Raphael, B. 1968. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics (SSC4)2: 100107. 
  13. Hendler, J. 2005. Knowledge Is Power: A View from the Semantic Web. AI Magazine 26(4): 76–84.
  14. Keim, G. A.; Shazeer, N. M.; Littman, M. L.; Agarwal S.; Cheves, C. M.; Fitzgerald, J.; Grosland, J.; Jiang, F.; Pollard, S.; Weinmeister, K. 1999. PROVERB: The Probabilistic Cruciverbalist. In Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI-99), 710–717. Menlo Park, CA: AAAI Press.
  15. King, R. D.; Whelan, K. E.; Jones, F. M.; Reiser, P. G. K.; Bryant, C. H.; Muggleton, S. H.; Kell, D. B.; and Oliver, S.G. 2004. Functional Genomics Hypothesis Generation and Experimentation by a Robot Scientist. Nature 427(6971)(15 January): 247–252.
  16. Kumar, K. 1992. Algorithms for Constraint-Satisfaction Problems: A Survey. AI Magazine 13(1): 32–44.
  17. Kwok, C. C. T.; Etzioni, O.; and Weld, D. S. 2001. Scaling Question Answering to the Web. ACM Transactions on Information Systems (TOIS) 19(3) (July): 242–262.


A Web-Based Agent Challenges Human Experts on Crosswords
Marco Ernandes, Giovanni Angelini, Marco Gori

Авторизация
Забыли свой пароль?