ИНДУКТИВНЫЙ ВЫВОД ГРАММАТИКИ
Индуктивный вывод грамматики представляет собой задачу определения с помощью обучения грамматики на основе данных. Очевидно, что попытка решить такую задачу вполне оправдана, поскольку практика показала, насколько сложно конструировать грамматику вручную, а в Internet можно бесплатно получить миллиарды готовых примеров фрагментов речи. Но такая задача является сложной, поскольку пространство возможных грамматик бесконечно, а проверка того, что данная конкретная грамматика производит необходимое множество предложений, требует больших вычислительных затрат.
Одной из интересных моделей является система Sequitur [1122]. Для нее не требуется никаких входных данных, кроме одного отрывка текста (который не требуется даже предварительно разбивать на предложения). Эта система формирует грамматику в очень специализированной форме — грамматику, которая производит лишь единственную строку, а именно первоначальный текст. Иначе к анализу результатов этой системы можно подойти таким образом, что Sequitur в процессе обучения определяет лишь такой объем грамматических правил, который является достаточным для синтаксического анализа данного текста. Ниже приведена приемлемая разбивка с помощью скобок, обнаруженная этой системой для одного предложения из более крупного текста с информацией о новостях.
[Most Labour][sentiment [[would still][favor the] abolition]][[of [the House]][of Lords]]
В этом фрагменте правильно выделены такие составляющие, как словосочетание РР "of the House of Lords", хотя и допущены отклонения от традиционного метода анализа, например артикль "the" включен в одну группу с предшествующим глаголом, а не со следующим существительным.
Система Sequitur основана на той идее, что "хорошая грамматика — компактная грамматика". В частности, в ней принудительно применяются следующие два ограничения. Во-первых, ни одна пара смежных символов не должна появляться в грамматике больше одного раза. Если пара символов А в появляется в правой части нескольких правил, то эту пару следует заменить новым нетерминальным символом, назвать его, допустим, С и ввести правило С->А в. Во-вторых, каждое правило должно использоваться по меньшей мере дважды. Если некоторый нетерминальный символ С появляется в грамматике только один раз, то необходимо удалить правило для С и заменить его единственное вхождение правой частью данного правила. Эти два ограничения применяются в процедуре жадного поиска, которая сканирует текст слева направо, инкрементно наращивая в ходе этого грамматику и налагая ограничения, как только появляется такая возможность. В табл. 22.8 показано, как действует этот алгоритм применительно к входному тексту "abcdbcabcd". Алгоритм восстанавливает оптимально компактную грамматику для этого текста.
РЕЗЮМЕ
Разработка способов понимания естественного языка является одним из наиболее важных направлений развития искусственного интеллекта. Это направление подпи-тывается идеями, взятыми из философии и лингвистики, а также обогащается методами логического и вероятностного представления знаний и формирования рассуждений. В отличие от других областей искусственного интеллекта, для понимания естественного языка требуется эмпирическое исследование фактического поведения людей, что, в свою очередь, представляет собой сложную и интересную задачу.
• Агенты посылают друг другу сигналы, чтобы добиться определенных целей: проинформировать, предупредить, попросить помощь, поделиться знаниями или что-то пообещать. Отправка сигнала таким образом называется речевым актом. В конечном итоге все речевые акты представляют собой попытку заставить других агентов во что-то поверить или что-то сделать.
• Язык состоит из принятых в соответствии с соглашениями знаков, которые несут в себе смысл. Многие животные используют знаки только в их непосредственном виде. А люди, по-видимому, являются единственной разновидностью животных, которая применяет грамматику для производства структурированных сообщений, характеризующихся неограниченным разнообразием.
• Общение требует от говорящего выполнения трех этапов: достижение намерения донести некоторую идею, осуществляемое в уме производство цепочки слов и их физический синтез. После этого слушающий должен выполнить четыре этапа: восприятие, синтаксический анализ, устранение неоднозначности и усвоение смысла. Все варианты использования языка являются ситуационными; под этим подразумевается, что смысл фрагмента речи может зависеть от той ситуации, в которой он был произведен.
• Полезными инструментальными средствами, позволяющими учитывать некоторые аспекты естественного языка, являются формальная теория языка и грамматики структуры словосочетаний (в частности, контекстно-свободные грамматики).
• Синтаксический анализ предложений, выраженных на контекстно-свободном языке, может осуществляться за время О (л3) с помощью диаграммного синтаксического анализатора.
• Чтобы можно было проще справиться с задачами согласования подлежащего и глагольного сказуемого, а также выбора падежа местоимения, удобно воспользоваться таким методом, как расширение грамматики. Применение необходимых расширений обеспечивается с помощью формальной системы, представляющей собой грамматику определенных выражений (Definite Clause Grammar — DCG). Грамматика DCG обеспечивает синтаксический анализ и семантическую интерпретацию (и даже производство) текста с помощью логического вывода.
• С помощью расширенной грамматики может также осуществляться семантическая интерпретация. Одним из удобных посредников между деревьями синтаксического анализа и семантическими представлениями может стать квазилогическая форма.
• Очень важной проблемой при понимании естественного языка является неоднозначность; большинство предложений имеют много возможных интерпретаций, но обычно подходящей является только одна из них. Устранение неоднозначности основано на знаниях о мире, о текущей ситуации и о нормативном использовании языка.
• Большинство языков существуют в контексте множества предложений, а не только одного предложения. В основе исследования связных текстов лежит понятие речи. В этой главе описано, как можно разрешать местоименные ссылки, охватывающие несколько предложений, и показано, благодаря чему предложения соединяются в связные отрывки текста.
• Метод индуктивного вывода грамматики позволяет определять с помощью обучения грамматику на основании примеров, хотя и существуют ограничения, касающиеся того, насколько успешно может быть обобщена эта грамматика.
Наука о знаках и символах как элементах языка была названа семиотикой Джоном Локком [941], хотя она не получила развития до XX столетия [353], [1198]. К новейшим обзорным исследованиям относятся [273] и [429].
Идея языка как действия была сформулирована в рамках философских исследований лингвистической направленности, проводимых в XX веке [49], [596], [1608], и особенно ярко отразилась в книге Speech Acts [1375]. Прародителем идеи речевых актов был Протагор (ок. 430 г. до н.э.), который определил четыре типа предложений: просьба, вопрос, ответ и приказ. Модель речевого акта, основанная на плане, была впервые предложена в [278]. Связь между языком и действием исследовалась с использованием распознавания плана для понимания рассказов Виленским [1591]. В [277] собраны более современные работы в этой области.
Как и семантические сети, контекстно-свободные грамматики (называемые также грамматиками структуры словосочетаний) представляют собой повторное изобретение метода, который был впервые использован древнеиндийскими филологами (особенно Панини, ок. 350 г. до н.э.), изучающими шастрический санскрит [716]. Они были повторно изобретены Ноамом Хомским [250] для анализа английского синтаксиса и независимо от него Джоном Бэкусом для анализа синтаксиса языка Algol-58. Наур [1116] расширил систему обозначений Бэкуса, и теперь его заслуги отмечены тем, что буква "N" в обозначении формы BNF, которое первоначально расшифровывалось как "Backus Normal Form" (нормальная форма Бэкуса), считается сокращением от его фамилии [58]. Одну из разновидностей расширенной грамматики, называемой грамматикой атрибутов, которая удобна для представления языков программирования, предложил Кнут [808]. Грамматики определенных выражений были введены в научный обиход Колмерором [284], а в дальнейшем доработаны и популяризированы Перейрой и Уорреном [1208]. Язык программирования Prolog был разработан Аленом Колмерором специально для решения задачи синтаксического анализа французского языка. Колмерор фактически ввел в действие формальную систему, называемую грамматикой метаморфоз, которая превосходила по своим возможностям грамматику определенных выражений, но вскоре после этого появилась более практичная грамматика DCG.