Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 296
Текст из файла (страница 296)
В табл. 22.8 показано, как действует этот алгоритм применительно к входному тексту "аЬсс]ЬсаЬсс[". Алгоритм восстанавливает оптимально компактную грамматику для этого текста. Входныеданаые Грамматика Комментарии 1 а я — » а я -+ аЬ я — з аЬс я — » аЬсс) 5 — » аьсс)Ь я -ч аЬсс)Ьс я -» алцл; А -» ьс 2 аЬ 3 аЬс 4 аЬсс) 5 аЬссп» б аЬсс)Ьс Ьс встречается дважды Таблипа 22.8. Трассировка выполнения задания, в котором система Беяийвг осуществляет индуктивный вывод грамматики для входного текста "аЬсйЬсаЬсг)".
Работа начинается с введения правила для я и добавления каждого символа к копну этого правила по очереди. После добавления шестого символа обнарулщвается первое вхождение повторяющейся парьс Ьс. Поэтому оба вхождения Ьс заменяются новым иетермннальным символом А и вводится правило А-аьс. После добавления еще трех символов девятый символ вызывает еще одно повторение Ьс, поэтому такая пара снова заменяется символом А. Это приводит к появлению двух вхожаений символов ал, поэтому они заменяются новым нетерминальным символом в. После добавления десятого и последнего терминального символа обнаруживаются два вхождения всг, поэтому они заменяются новым нетермннальным символом с. По теперь символ в появляется только один раз, в правой части правила с, поэтому в заменяется его расширением ад Глава 22.
Общение 1091 Окончание табл. 13.8 Входные данные Грамматика Комментарии 7 аЬсдЬса 8 аЬсдЬсаЬ 9 аЬсс)ЬсаЬс  — > алдяа; Л -+ Ьс  — > алдлаь; Л ч Ьс В -+ алдлаьс; А ч Ьс В -ч алдлал; л -ь Ьс Ьс встречается дважды ал встречается дважды В -ч В ЫВ; Л -+ Ьс; В -+ аЛ 10 аЬсдЬсаЬсд В -ч Вдлвд; А -+ Ьс;  †> ал В-ч САС; А -ч Ьс; В -ч ал~ С вЂ” ч Вд  — ч с с> л — > ьс; с -ч адд Вд встречается дважды в встречается только один ркз В следующей главе будут описаны другие алгоритмы индуктивного вывода грамматики, которые могут применяться к вероятностным контекстно-свободным грамматикам.
А теперь обратимся к проблеме определения с помощью обучения грамматики, которая дополнена семантикой. Поскольку расширенная грамматика представляет собой логическую программу, состоящую из хорновских выражений, то для этого могут применяться методы индуктивного логического программирования. Одной из программ индуктивного логического программирования (1пдцсйче 1.о8(с Ргойгапптнпй — П.Р) является 0711! (16401, которая на основании примеров определяет с помощью обучения грамматику и специализированный синтаксический анализатор для этой грамматики. Целевой проблемной областью являются запросы к базе данных на естественном языке. Обучающие примеры состоят из пар, в которые собраны строки из слов и соответствующих запросов, например, как показано ниже.
Ъ Как называется столица штата с наибольшим количеством населения? Иьае ьз еье сарьеа1 об Сье зеаее ыьеь сне 1акяезе рорц1аеьоп? Апамек(с, Сардеа1(з, с) л Ьасдеае(р, Веаее(з) л Рорц1аедоп(а, р) ) ) Задача программы С)йй состоит в том, чтобы определить с помо)цью обучения предикат Расзе ( вессс)В, доеду), который является совместимым с примерами и, можно надеяться, допускает приемлемое обобщение применительно к другим примерам. Непосредственное использование метода П.Р для определения этого предиката с помощью обучения приводит к достижению слишком низкой производительности: полученный с помощью индуктивного вывода синтаксический анализатор имеет точность лишь приблизительно 20% Но, к счастью, системы обучения с помощью 11.Р могут совершенствоваться путем введения дополнительных знаний.
В данном случае большая часть предиката Ратзе была определена в виде логической программы и задача системы С)011 свелась к тому, что нужно было осуществить логический вывод правил управления, которыми может руководствоваться синтаксический анализатор при выборе одного варианта синтаксического анализа перед другим. После введения этих дополнительных знаний система С)йй достигла точности от 70 до 85% при решении различных задач обработки запросов к базе данных. 1092 Часть ЧП. Общение, восприятие и осуществление действий 22.9.
РЕЗЮМЕ Разработка способов понимания естественного языка является одним из наиболее важных направлений развития искусственного интеллекта. Это направление подпитывается идеями, взятыми из философии и лингвистики, а также обогащается методами логического и вероятностного представления знаний и формирования рассуждений. В отличие от других областей искусственного интеллекта, для понимания естественного языка требуется эмпирическое исследование фактического поведения людей, что, в свою очередь, представляет собой сложную и интересную задачу. ° Агенты посылают друг другу сигналы, чтобы добиться определенных целей; проинформировать, предупредить, попросить помо|ць, поделиться знаниями или что-то пообещать.
Отправка сигнала таким образом называется речевым актом. В конечном итоге все речевые акты представляют собой попьпку заставить других агентов во что-то поверить или что-то сделать. ° Язык состоит из принятых в соответствии с соглашениями знаков, которые несут в себе смысл. Многие животные используют знаки только в их непосредственном виде. А люди, по-видимому, являются единственной разновидностью животных, которая применяет грамматику для производства структурированных сообщений, характеризующихся неограниченным разнообразием. ° Общение требует от говорящего выполнения трех этапов: достижение намерения донести некоторую идею, осуществляемое в уме производство цепочки слов и их физический синтез.
После этого слушающий должен выполнить четыре этапа: восприятие, синтаксический анализ, устранение неоднозначности и усвоение смысла. Все варианты использования языка являются ситуационными; под этим подразумевается, что смысл фрагмента речи может зависеть от той ситуации, в которой он был произведен. ° Полезными инструментальными средствами, позволяющими учитывать некоторые аспекты естественного языка, являются формальная теория языка и грамматики структуры словосочетаний (в частности, контекстно-свободные грамматики).
° Синтаксический анализ предложений, выраженных на контекстно-свободном языке, может осуществляться за время 0(п') с помощью диаграммного синтаксического анализатора. ° Чтобы можно было проще справиться с задачами согласования подлежащего и глагольного сказуемого, а также выбора падежа местоимения, удобно воспользоваться таким методом, как расширение грамматики. Применение необходимых расширений обеспечивается с помощью формальной системы, представляющей собой грамматику определенных выражений (Оейп!ге С!ацзе Огапппаг — ОСО).
Грамматика ОСО обеспечивает синтаксический анализ и семантическую интерпретацию (и даже производство) текста с помо|цью логического вывода. ° С помощью расширенной грамматики может также осуществляться семантическая интерпретация. Одним из удобных посредников между деревьями синтаксического анализа и семантическими представлениями может стать квази- логическая форма. 1093 Глава 22. Общение ° Очень важной проблемой при понимании естественного языка является неоднозначность; большинство предложений имеют много возможных интерпретаций, но обычно подходящей является только одна из них. Устранение неоднозначности основано на знаниях о мире, о текущей ситуации и о нормативном использовании языка.
° Большинство языков существуют в контексте множества предложений, а не только одного предложения. В основе исследования связных текстов лежит понятие речи. В этой главе описано, как можно разрешать местоименные ссылки, охватывающие несколько предложений, и показано, благодаря чему предложения соединяются в связные отрывки текста. ° Метод индуктивного вывода грамматики позволяет определять с помощью обучения грамматику на основании примеров, хотя и существуют ограничения, касающиеся того, насколько успешно может быть обобщена эта грамматика. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ Наука о знаках и символах как элементах языка была названа 'з.семиотикой Джоном Локком [941], хотя она не получила развития до ХХ столетия [353], [1198].
К новейшим обзорным исследованиям относятся [273] и [429]. Идея языка как действия была сформулирована в рамках философских исследований лингвистической направленности, проводимых в ХХ веке [49), [596], [1608], и особенно ярко отразилась в книге арсаева Асгз [1375). Прародителем идеи речевых актов был Протагор (ок. 430 г. до н.э.), который определил четыре типа предложений: просьба, вопрос, ответ и приказ. Модель речевого акта, основанная на плане, была впервые предложена в [278].
Связь между языком и действием исследовалась с использованием распознавания плана для понимания рассказов Виленским [1591]. В [277] собраны более современные работы в этой области. Как и семантические сети, контекстно-свободные грамматики (называемые также грамматиками структуры словосочетаний) представляют собой повторное изобретение метода, который был впервые использован древнеиндийскими филологами (особенно Папини, ок. 350 г. до н.э.), изучающими шастрический санскрит [716]. Они были повторно изобретены Ноамом Хомским [250) для анализа английского синтаксиса и независимо от него Джоном Бэкусом для анализа синтаксиса языка А18о1-58. Наур [1! 16] расширил систему обозначений Бэкуса, и теперь его заслуги отмечены тем, что буква ")ч]" в обозначении формы В)ч]Р, которое первоначально расшифровывалось как "Васкцз )ч!оппа! Рогш" (нормальная форма Бэкуса), считается сокрашением от его фамилии [58].
Одну из разновидностей расширенной грамматики, называемой Ъ.грамматикой атрибутов, которая удобна для представления языков программирования, предложил Кнут [808]. Грамматики определенных выражений были введены в научный обиход Колмерором [284), а в дальнейшем доработаны и популяризированы Перейрой и Уорреном [1208). Язык программирования Рго1о8 был разработан Аленом Колмерором специально для решения задачи синтаксического анализа французского языка. Колмерор фактически ввел в действие формальную систему, называемую грамматикой метаморфоз, которая превосходила по !094 Часть ЪЧ!. Обшение, восприятие и осушествление действий своим возможностям грамматику определенных выражений, но вскоре после этого появилась более практичная грамматика Г)СО. Было предпринято много попыток написания формальных грамматик естественных языков, как в "чистой" лингвистике, так и в вычислительной лингвистике.
К машинно-ориентированным грамматикам такого типа относятся системы, разработанные в рамках проекта 1лпйшзпс Вгг[пй Рго]есг в Университете штата Нью-Йорк [1343] и проекта ХТАО в Университете штата Пенсильвания [403]. Хорошим примером современной системы РСО может служить Соге 1 апйцайе Епй(пе [22]. Существует также несколько исчерпываюШих, но неформальных грамматик английского языка [701], [735], [1015], [1261]. К хорошим учебникам по лингвистике относятся введение в синтаксис [1342] и учебники по семантике [249], [643]; [1016] в основном посвяшена описанию логики и рассчитана на лингвистов. С середины 1980-х годов наметилась тенденция к тому, что больше информации стали вводить в лексикон и меньше в грамматику. Первой крупной грамматической формальной системой, которая характеризовалась высокой степенью лексикализации, была лексически-функциональная грамматика, или сокращенно 1.РО (1.ех(са1- Гцпсйопа1 Огапппаг) [183].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
