БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Подход с применением моделей п-буквенных сочетаний для моделирования языка был предложен Марковым [983]. Клод Шеннон [1394] впервые создал модели n-словных сочетаний английского языка. Хомский [250], [251] указал на ограничения моделей на основе конечных автоматов по сравнению с моделями на основе контекстно-свободных грамматик и пришел к заключению: "Вероятностные модели не позволяют каким-то образом добиться лучшего понимания некоторых основных проблем синтаксической структуры". Это утверждение справедливо, но в нем игнорируется тот факт, что вероятностные модели обеспечивают лучшее понимание некоторых других основных проблем, а именно тех проблем, которые не могут быть решены с помощью контекстно-свободных грамматик. Замечания, сделанные Хом-ским, оказали неблагоприятный эффект, выразившийся в том, что в течение двух десятилетий многие исследователи избегали использования статистических моделей. Положение изменилось лишь после того, как указанные модели снова вышли на передний план и стали применяться при распознавании речи [730].
Метод сглаживания с добавлением единицы был предложен Джеффри [728], а метод сглаживания с удалением путем интерполяции разработан Елинеком и Мер-сером [732], которые использовали этот метод для распознавания речи. В число других методов входят сглаживание Виттена-Белла [1605] и сглаживание Гуда-Тьюринга [257]. Последний метод также широко применяется при решении задач биоинформатики. Проблематика биостатистических и вероятностных задач NLP постепенно сближается, поскольку в каждой из этих областей приходится иметь дело с длинными структурированными последовательностями, выбранными из алфавита непосредственных составляющих.
Простые модели n-буквенных и n-словных сочетаний не являются единственными возможными вероятностными моделями. В [136] описана вероятностная модель текста, называемая скрытым распределением Дирихле, в которой документ рассматривается как комбинация тем, а каждая из тем характеризуется собственным распределением слов. Эта модель может рассматриваться как дополнение и уточнение модели скрытой семантической индексации Дирвестера [376] (см. также [1169]); кроме того, она тесно связана с моделью сочетания многочисленных причин [1345].
В вероятностных контекстно-свободных грамматиках (Probabilistic Context-Free Grammar — PCFG) устранены все недостатки вероятностных моделей, отмеченные Хомским, и они показали свои преимущества над обычными контекстно-свободными грамматиками. Грамматики PCFG были исследованы Бутом [151] и Са-ломаа [1346]. В [729] представлен алгоритм декодирования стека, представляющий собой один из вариантов алгоритма поиска Витерби, который может использоваться для определения наиболее вероятной версии синтаксического анализа с помощью грамматики PCFG. В [63] представлен внешний—внутренний алгоритм, а в [889] описаны области его применения и ограничения. В [236] и [804] обсуждаются проблемы синтаксического анализа с помощью грамматик в виде банка деревьев.
В [1467] показано, как определять с помощью обучения грамматические правила на основе слияния байесовских моделей. Другие алгоритмы для грамматик PCFG представлены в [235] и [980]. В [282] приведен обзор результатов, полученных в этой области, и даны пояснения к одной из наиболее успешных программ статистического синтаксического анализа.
К сожалению, грамматики PCFG при выполнении самых различных задач показывают более низкую производительность по сравнению с простыми п-элементными моделями, поскольку грамматики PCFG не позволяют представить информацию, связанную с отдельными словами. Для устранения этого недостатка некоторые авторы [281], [237], [713] предложили варианты лексикализованных вероятностных грамматик, в которых совместно используются контекстно-свободные грамматики и статистические данные, касающиеся отдельных слов.
Первой попыткой собрать сбалансированную совокупность текстов для эмпирической лингвистики явилось создание коллекции Brown Corpus [493]. Эта совокупность состояла примерно из миллиона слов с отметками, обозначающими части речи. Первоначально эта коллекция хранилась на 100 тысячах перфокарт. Банк деревьев синтаксического анализа Пенна [982] представляет собой коллекцию, состоящую примерно из 1,6 миллиона слов текста, дня которого вручную выполнен синтаксический анализ с преобразованием в деревья. Эта коллекция помещается на компакт-диске. В издании British National Corpus [905] данная коллекция была расширена до 100 миллионов слов. В World Wide Web хранится свыше триллиона слов больше чем на 10 миллионах серверов.
В последнее время растет интерес к области информационного поиска, обусловленный широким применением поиска в Internet. В [1296] приведен обзор ранних работ в этой области и представлен принцип ранжирования вероятностей. В [980] дано краткое введение в проблематику информационного поиска в контексте статистических подходов к решению задач NLP. В [59] приведен обзор общего назначения, заменивший более старые классические работы [492] и [1347]. Книга Managing Gigabytes [1606] посвящена решению именно той задачи, о которой говорит ее название, — описанию того, как можно эффективно индексировать, применять сжатие и выполнять запросы применительно к совокупности текстов гигабайтовых размеров. В рамках конференции TREC, организованной Национальным институтом стандартов и технологии (National Institute of Standards and Technology — NIST) при правительстве Соединенных Штатов, проводятся ежегодные соревнования между системами информационного поиска и публикуются труды с описанием достигнутых результатов. За первые семь лет таких соревнований производительность участвующих в них программ выросла примерно в два раза.
Наиболее широко применяемой моделью для информационного поиска является модель векторного пространства Салтона [1348]. В первые годы развития этой области указанная работа Салтона была фактически самой влиятельной. Имеются также две альтернативные вероятностные модели. Модель, представленная в этой книге, основана на [1225]. В ней моделируется совместное распределение вероятностей P(D,Q) в терминах P(Q\ D). В другой модели [985], [1297] используется вероятность P(D \ Q). В [879] показано, что обе эти модели основаны на одном и том же совместном распределении вероятностей, но от выбора модели зависит то, какие методы должны применяться для определения параметров с помощью обучения. Описание, приведенное в данной главе, основано на обеих этих моделях. В [1522] приведено сравнение различных моделей информационного поиска.
В [187] описана реализация машины поиска для World Wide Web, включая алгоритм PageRank, в основе которого лежит независимый от запроса критерий качества документа, базирующийся на анализе Web-ссылок. В [805] описано, как находить авторитетные источники информации в Web с использованием анализа ссылок. В [1411] приведены результаты исследования журнала с данными о миллиарде поисковых операций, выполненных в Web. В [864] приведен обзор литературы по исправлению орфографических ошибок. В [1230] описан классический алгоритм выделения основы с помощью правил, а в [860] описан вариант, в котором применяется словарь.
В [980] приведен хороший обзор проблематики классификации и кластеризации документов. В [738] используются теория статистического обучения и теория машин векторов поддержки для теоретического анализа ситуаций, в которых классификация должна быть успешной. В [37] приведены данные о том, что при классификации новостных сообщений агентства Reuters, относящихся к категории "Earnings" (Доходы), была достигнута точность 96%. В [824] приведены данные о том, что при использовании наивного байесовского классификатора достигается точность вплоть до 95%, а при использовании байесовского классификатора, в котором учитываются некоторые зависимости между характеристиками, — вплоть до 98,6%. В [922] приведен обзор результатов, достигнутых за сорок лет применения наивных байесовских моделей для классификации и поиска в тексте.
Последние достижения в этой области публикуются в журнале Information Retrieval и в трудах ежегодной конференции SIGIR.
Одними из первых программ извлечения информации являются Gus [143] и Frump [380]. В основе некоторых проектов современных систем извлечения информации лежат работы в области семантических грамматик, проводившиеся в 1970-х и 1980-х годах. Например, в интерфейсе системы резервирования авиабилетов с семантической грамматикой используются такие категории, как Location (место нахождения) и FlyTo (место назначения), а не NP и VP. Описание результатов реализации одной из систем, основанных на семантических грамматиках, приведено в [130].
Новейшие результаты исследований по извлечению информации пропагандируются на ежегодных конференциях MUC (Message Understanding Conference), спонсором которых выступает правительство США. Система FASTUS была разработана Хоббсом и др. [664]; в сборнике статей, в котором впервые была опубликована информация об этой системе [1299], можно найти информацию и о других системах, в которых используются модели конечных автоматов.
В 1930-м году Петр Троянский (Petr Troyanskii) подал заявку на патент, в котором была сформулирована идея "машины перевода", но в то время еще не существовали компьютеры, позволяющие реализовать эту идею. В марте 1947 года Уоррен Вивер (Warren Weaver), сотрудник Фонда Рокфеллера, написал Норберту Винеру письмо, в котором указал, что решение задачи машинного перевода вполне возможно. Опираясь на работы в области криптографии и теории информации, Вивер писал: "Когда я рассматриваю статью, написанную на русском языке, я говорю себе: «Она фактически написана на английском языке, но закодирована странными символами. Теперь я приступаю к ее декодированию»". В течение следующего десятилетия все сообщество специалистов в этой области предпринимало упорные попытки декодирования текстов на иностранном языке таким способом. Компания IBM продемонстрировала соответствующую зачаточную систему в 1954 году. Энтузиазм, характерный для этого периода, показан в [69] и [942]. Последующее разочарование в возможностях машинного перевода описано Линдсеем [935], указавшим также на некоторые препятствия, связанные с необходимостью обеспечения взаимодействия синтаксиса и семантики, а также с потребностью в наличии знаний о мире, с которыми сталкивается машинный перевод. Правительство США выразило недовольство полным отсутствием прогресса в этой области и сформулировало свое заключение в одном из отчетов, который известен как отчет ALPAC [21]: "Нет ни ближайших, ни обозримых перспектив создания практически применимых систем машинного перевода". Однако работы в ограниченном объеме продолжались, и в ВВС США в 1970 году была развернута система Systran, которая была взята на вооружение Европейским экономическим сообществом в 1976 году. В том же 1976 году была развернута система перевода сообщений о погоде Taum-Meteo [1255]. К началу 1980-х годов возможности компьютеров возросли до такой степени, что выводы отчета ALPAC потеряли свою актуальность. В [1548] приведены сведения о некоторых новейших приложениях машинного перевода, основанных на системе Wordnet. Учебное введение в эту область приведено в [710].
Первые предложения по использованию статистического машинного перевода были сделаны в заметках Уоррена Вивера, опубликованных в 1947 году, но возможность практического применения этих методов появилась только в 1980-х годах. Описание этой тематики, приведенное в данной главе, основано на работе Брауна и его коллег из компании IBM [195], [196]. Эти труды весьма насыщены математической символикой, поэтому прилагаемый к ним учебник Кевина Найта [806] воспринимается как глоток свежего воздуха. В более современных исследованиях по статистическому машинному переводу наблюдается отказ от модели двухсловных сочетаний в пользу моделей, которые включают некоторые синтаксические конструкции [1627]. Первые работы в области сегментации предложений были выполнены Пал-мером и Херстом [1166]. Задача выравнивания двуязычных предложений рассматривается в [1042].
Есть две превосходные книги по вероятностной обработке лингвистической информации: книга [235] является краткой и точной, а книга [980] — всеобъемлющей и современной. С состоянием работ по созданию практических методов обработки лингвистической информации можно ознакомиться по материалам проводимой один раз в два года конференции Applied Natural Language Processing (ANLP) и конференции Empirical Methods in Natural Language Processing (EMNLP), а также по публикациям в журнале Natural Language Engineering. Организация SIGIR финансирует выпуск информационного бюллетеня и проведение ежегодной конференции по информационному поиску.