БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Было предпринято много попыток написания формальных грамматик естественных языков, как в "чистой" лингвистике, так и в вычислительной лингвистике. К машинно-ориентированным грамматикам такого типа относятся системы, разработанные в рамках проекта Linguistic String Project в Университете штата Нью-Йорк [1343] и проекта XTAG в Университете штата Пенсильвания [403]. Хорошим примером современной системы DCG может служить Core Language Engine [22]. Существует также несколько исчерпывающих, но неформальных грамматик английского языка [701], [735], [1015], [1261]. К хорошим учебникам по лингвистике относятся введение в синтаксис [1342] и учебники по семантике [249], [643]; [1016] в основном посвящена описанию логики и рассчитана на лингвистов.
С середины 1980-х годов наметилась тенденция к тому, что больше информации стали вводить в лексикон и меньше в грамматику. Первой крупной грамматической формальной системой, которая характеризовалась высокой степенью лексикализа-ции, была лексически-функциональная грамматика, или сокращенно LFG (Lexical-Functional Grammar) [183]. Доведение процесса лексикализации до предела приводит к созданию категориальной грамматики, в которой количество грамматических правил может стать крайне малым, например равным двум, или грамматики зависимостей [1033], в которой не существует словосочетаний, а есть только слова. В [1431] описан широко применяемый синтаксический анализатор, в котором используется грамматика зависимостей. Грамматика соединения деревьев, или сокращенно TAG (Tree-Adjoining Grammar) [749], строго говоря, не является лексической, но получила широкое распространение в своей лексикализованной форме [1356]. Интерес представляет общедоступный словарь Wordnet [462], состоящий примерно из 100 000 слов и словосочетаний, классифицированных по частям речи и связанных с помощью семантических отношений, таких как "синоним", "антоним" и "часть—целое".
Первые компьютеризированные алгоритмы синтаксического анализа были продемонстрированы в [1632]. Эффективные алгоритмы были разработаны в конце 1960-х годов, и с тех пор в них было введено лишь немного дополнений [587], [773], [1636]. Рассматриваемый в настоящей главе диаграммный синтаксический анализатор в большей степени соответствует описанному в [427]. Хороший общий обзор по этой теме приведен в книге Ахо и Ульмана [9], посвященной синтаксическому анализу и компиляции. В [1001] показано, как в обычной ситуации можно добиться высокой эффективности алгоритма диаграммного синтаксического анализа с дополнениями. В [256] рассматривается проблема устранения синтаксической неоднозначности.
Направление исследований по формальной семантической интерпретации естественных языков впервые возникло в рамках философии и формальной логики и особенно тесно связано с работой Альфреда Тарского [1490] по семантике формальных языков. Бар-Хиллел впервые проанализировал проблемы прагматики и высказал предположение, что они могут быть решены с помощью формальной логики. В частности, он ввел в лингвистику предложенный Ч. С. Пирсом [1198] термин "индексальный" (indexical), т.е. обладающий смыслом только в непосредственном контексте своего применения [68]. Очерк Ричарда Монтегю English as a formal language (Английский как формальный язык) [1071] представляет собой своего рода манифест сторонников логического анализа языка, но более доступными для восприятия являются [408] и [924]. Полный сборник трудов Монтегю вышел под редакцией Томасона
[1505]. В искусственном интеллекте традиции Монтегю продолжили Макаллестер и Гивен [1007], которые разработали много новых формальных методов.
Идея использования промежуточной, или квазилогической формы, для решения таких проблем, как определение области действия кванторов, впервые выдвинута Вудсом [1614] и в настоящее время применяется во многих современных системах [22], [714].
Первой системой NLP, предназначенной для решения реальной задачи, по-видимому, стала система формирования ответов на вопросы Baseball [590], которая выдавала ответы на вопросы, касающиеся базы данных со статистическими сведениями о бейсболе. Вскоре после этого была разработана система Вудса Lunar [1612], которая отвечала на вопросы об образцах лунного фунта, доставленного на Землю в рамках программы Аполлон. Роджер Шенк со своими студентами создал ряд программ [425], [1358], [1359], [1590], предназначенных для решения задачи понимания языка. Но при разработке этих программ основное внимание было сосредоточено не на языке как таковом, а, скорее, на представлении знаний и формировании рассуждений. К числу рассматриваемых проблем относилось представление стереотипных ситуаций [314], описание организации человеческой памяти [829], [1287], а также понимание планов и целей [1591].
Задачи производства текстов на естественном языке рассматривались с самых первых дней развития работ по машинному переводу, начиная с 1950-го года, но не были сформулированы в связи с потребностями выработки текста на одном языке (а не двух, как при переводе) до 1970-х годов. Характерными исследованиями в этом направлении являются работы, описанные в [571] и [1413]. Одной из первых полномасштабных систем производства текста явилась система Penman [80], основанная на системной грамматике [775]. В 1990-х годах появились две важные общедоступные системы выработки текста, KPML [79] и FUF [433]. К числу наиболее важных книг по производству текста относятся [690], [1029], [1183] и [1275].
Одной из самых ранних работ по устранению неоднозначности явилось исследование Уилкса [1596] по теории семантики предпочтений, в котором предпринимались попытки поиска интерпретаций, позволяющих свести к минимуму количество семантических аномалий. В [661] описана система аналогичного назначения, которая ближе к композиционной семантике, описанной в этой главе. В [666] представлена количественная инфраструктура для измерения качества синтаксической и семантической интерпретации. С тех пор получили более широкое распространение методы, основанные на использовании явной байесовской инфраструктуры [238], [1625]. В лингвистике получила распространение теория оптимальности (Linguistics) [761], основанная на идее формирования мягких ограничений, налагаемых на грамматику, что позволяет выполнять естественное ранжирование интерпретаций, а не использовать грамматику для производства всех возможных вариантов с равным рангом. В [1147] рассматриваются проблемы изучения многочисленных одновременных интерпретаций как метода, применяемого вместо выбора одной интерпретации с максимальным правдоподобием. Литературные критики [437], [663] выразили сомнение в том, удастся ли когда-либо решить проблему устранения или уменьшения неоднозначности.
Формальная модель метонимии представлена в [1150]. В [883] приведены соответствующие результаты анализа и описан каталог метафор, широко применяемых в английском языке. В [1160] представлен сборник статей по метафорам, а в [992] предложен вычислительный подход к интерпретации метафор.
Приведенная в этой главе трактовка разрешения ссылок основана на работе Хоб-бса [662]. Более сложная модель, предложенная в [888], основана на механизме присваивания количественных оценок. В опубликованных немного позже работах [529], [789] использовалось машинное обучение для настройки количественных параметров. Двумя превосходными обзорами проблематики разрешения ссылок являются книги [660] и [1067].
В изданной в 1758 году книге Дэвида Юма Enquiry Concerning the Human Understanding утверждалось, что речь становится связной благодаря действию "трех принципов связи между идеями, а именно: сходство, смежность во времени или пространстве, а также причина или результат". С этого началась долгая история попыток определить отношения связности речи. Множество отношений, которое используется в данной главе, предложено Хоббсом [663]; в [974] представлено более широкое множество, которое включает готовность к принятию решения, свидетельство, обоснование, мотивацию, основание, следствие, предоставление возможностей, использование возможностей, переформулировку утверждения, условие, обстоятельство, причину, соглашение, предысторию и тезис—антитезис. Развитие этой модели привело к созданию теории риторической структуры (Rhetorical Structure Theory — RST), которая, по-видимому, является одной из наиболее перспективных современных теорий [975]. Некоторые примеры, приведенные в настоящей главе, заимствованы из книги, принадлежащей перу Эндрю Келера [756].
В [598] представлена теория связности речи, основанная на изучении сдвига фокуса внимания слушателя, а в [597] предложена близкая к ней теория, основанная на понятии сосредоточения внимания. В [750] собраны важные ранние работы по проблемам речи. Веббер представил модель взаимодействия ограничений синтаксиса и речи в том, что может быть высказано в любом моменте речи [1560], а также описал способ взаимодействия с содержимым речи времен глаголов [1561].
Первый важный результат по индуктивному выводу грамматики оказался отрицательным: Голд [569] показал, что нельзя надежно определить с помощью обучения правильный вариант контекстно-свободной грамматики по множеству строк, полученных с помощью этой грамматики. По сути, его идея состоит в том, что если дано множество строк sl5 s2, sn, то правильная грамматика может либо оказаться всеобъемлющей (S —» word *), либо стать копией входных данных (S —> s1 \ s2 | ... | sn), либо занять какое-то промежуточное положение. Выдающие лингвисты, такие как Хомский [251], [252] и Линкер [1211], [1213], использовали результат Голда для доказательства того, что должна существовать врожденная универсальная грамматика, которой все дети владеют от рождения. При этом особый интерес представляет так называемый довод о бедности стимула (Poverty of the Stimulus), согласно которому дети не получают другой входной языковой информации, кроме положительных примеров: их родители и сверстники главным образом вырабатывают точные примеры используемого ими языка и очень редко исправляют ошибки. Таким образом, поскольку Голд доказал, что определение с помощью обучения контекстно-свободной грамматики на основании положительных примеров является невозможным, то дети уже обязаны "знать" эту грамматику и в процессе обучения языку просто настраивают некоторые параметры этой врожденной грамматики и учат словарь. Хотя эти доводы продолжают повторять многие лингвисты школы Хомского, они были опровергнуты некоторыми другими лингвистами [436], [1243] и большинством ученых, работающих в области компьютерных наук. Еще в 1969 году Хорнинг [679] показал, что с помощью такого метода, как РАС-обучение, можно определить с помощью обучения вероятностную контекстно-свободную грамматику. С тех пор было проведено много убедительных эмпирических демонстраций успешного обучения на основании только положительных примеров, таких как работы в области ILP [1075] и [1101], а также замечательные докторские диссертации [350] и [1370]. С помощью обучения возможно также определить и другие грамматические формальные системы, такие как регулярные языки [386], [1157], регулярные древовидные языки [226] и конечные автоматы [1173].
Система Sequitur разработана Невилл-Маннингом и Уиттеном [1122]. Интересно отметить, что эти авторы, так же как и де Маркен, указали, что предложенные ими схемы индуктивного вывода грамматики представляют собой одновременно хорошие схемы сжатия. Этот результат соответствует принципу кодирования с минимальной длиной описания: из определения качественной грамматики следует, что она должна минимизировать сумму двух значений длины: длины грамматики и длины дерева синтаксического анализа текста.
К работам в области индуктивного логического программирования, относящимся к определению языка с помощью обучения, принадлежат система Chill [1640] и программа Муни и Калиффа [1076]; эти работы позволили определить правила для прошедшего времени глаголов лучше, чем до сих пор удавалось добиться с помощью нейронных сетей или систем деревьев решений. [315] представляет собой отредактированный сборник статей по определению с помощью обучения языка средствами логики.
Ассоциация ACL (Association for Computational Linguistics) проводит регулярные конференции и публикует журнал Computational Linguistics. Проводится также конференция International Conference on Computational Linguistics (COLING). Многие важные ранние статьи собраны в антологии Readings in Natural Language Processing [599]. В [321] основное внимание уделено описанию инструментальных средств, практически применимых для создания систем NLP. В [756] приведено исчерпывающее введение в эту область, [18] посвящена описанию работ, проведенных немного раньше. В [298] и [1207] приведен краткий обзор по синтаксической обработке с помощью различных реализаций на языке Prolog. Много полезных статей с описанием этой области приведено в книге Encyclopedia of А1\ особого внимания заслуживают статьи "Computational Linguistics" и "Natural Language Understanding".