ВЕРОЯТНОСТНАЯ ОБРАБОТКА ЛИНГВИСТИЧЕСКОЙ ИНФОРМАЦИИ
В данной главе показано, как можно использовать простые языковые модели, прошедшие статистическое обучение, для обработки коллекций, состоящих из миллионов слов, а не просто отдельных предложений.
В главе 22 было показано, что агент может взаимодействовать с другим агентом (человеком или программой), используя фрагменты текста на естественном языке. Для полного извлечения смысла фрагментов речи необходимо проводить всесторонний синтаксический и семантический анализ фрагментов речи, а такая возможность возникает благодаря тому, что эти фрагменты речи невелики и относятся только к ограниченной проблемной области.
В данной главе рассматривается подход к обеспечению понимания языка, основанный на использовании совокупностей текстов. Совокупностью текстов (corpus, во множественном числе — corpora) называется большая коллекция текстов, подобная тем миллиардам страниц, из которых состоит World Wide Web. Эти тексты написаны людьми и для людей, а задача программного обеспечения состоит в упрощении поиска нужной информации. В этом подходе предусматривается использование статистики и обучения для получения возможности воспользоваться содержимым совокупности, и в нем обычно применяются вероятностные языковые модели, обучение которых может проводиться с использованием существующих данных и которые проще по сравнению с дополненными грамматиками DCG, описанными в главе 22. При решении большинства подобных задач доступный объем данных превышает тот, который требуется для создания более простой языковой модели. В данной главе рассматриваются три конкретные задачи: информационный поиск (раздел 23.2), извлечение информации (раздел 23.3) и машинный перевод (раздел 23.4). Но вначале в ней представлен обзор вероятностных языковых моделей.
ВЕРОЯТНОСТНЫЕ ЯЗЫКОВЫЕ МОДЕЛИ
В главе 22 описана логическая модель языка; в ней для определения того, относится или не относится к некоторому языку данная строка, использовались грамматики CFG и DCG, а в данном разделе представлено несколько вероятностных моделей. Вероятностные модели имеют целый ряд преимуществ. Обучение этих моделей по имеющимся данным осуществляется очень просто: обучение сводится лишь к подсчету количества вариантов (с учетом определенных допусков на то, что из-за малого размера выборки могут возникать ошибки). Кроме того, эти модели являются более надежными (поскольку они способны принять любую строку, хотя и с низкой вероятностью); они отражают тот факт, что не все 100% говорящих на определенном языке согласны с тем, какие предложения фактически входят в состав языка; кроме того, такие модели могут использоваться для устранения неоднозначности, поскольку для выбора наиболее подходящей интерпретации могут применяться вероятностные законы.
Вероятностная языковая модель позволяет определить распределение вероятностей множества строк (которое может быть бесконечно большим). К примерам таких моделей, которые уже рассматривались в данной книге, относятся двух-и трехсловные языковые модели (или модели двух- и трехсловных сочетаний), применявшиеся при распознавании речи (раздел 15.6). В однословной модели (или модели однословных сочетаний) каждому слову в словаре присваивается вероятность P(w). В этой модели предполагается, что слова выбираются независимо, поэтому вероятность строки представляет собой произведение вероятностей входящих в нее слов и определяется выражением
Ниже приведена последовательность из 20 слов, которая была сформирована случайным образом из слов в оригинале данной книги с помощью однословной модели.
logical are as are confusion a may right tries agent goal the was diesel more object then information-gathering search is
В двухсловной модели каждому слову присваивается вероятность PiWilwi) с учетом предыдущего слова. Часть данных о вероятностях таких двухсловных сочетаний приведена в табл. 15.2. Приведенная ниже случайная последовательность слов сформирована с помощью модели двухсловных сочетаний по материалам оригинала данной книги.
planning purely diagnostic expert systems are very similar computational approach would be represented compactly using tic tac toe a predicate
Вообще говоря, в модели л-словных сочетаний учитываются предыдущие л-1 слов и присваивается вероятность P(Wi \ wi.{n.1)...Wi-i). Приведенная ниже случайная последовательность сформирована с помощью модели трехсловных сочетаний по оригиналу данной книги.
planning and scheduling are integrated the success of naive bayes model is just a possible prior source by that time
Даже эти небольшие примеры позволяют понять, что модель трехсловных сочетаний превосходит модель двухсловных сочетаний (а последняя превосходит модель однословных сочетаний) как с точки зрения качества приближенного представления текста на английском языке, так и с точки зрения успешной аппроксимации изложения темы в книге по искусственному интеллекту. Согласуются и сами модели: в модели трехсловных сочетаний строке, сформированной случайным образом, присваивается вероятность Ю-10, в модели двухсловных сочетаний — вероятность 10"29, а в модели однословных сочетаний — вероятность 10"59.
Но оригинал настоящей книги содержит всего лишь полмиллиона слов, поэтому в нем отсутствует достаточный объем данных для выработки качественной модели двухсловных сочетаний, не говоря уже о модели трехсловных сочетаний. Весь словарь оригинала данной книги включает примерно 15 тысяч различных слов, поэтому модель двухсловных сочетаний включает 150002 = 225 миллионов пар слов. Безусловно, что вероятность появления по меньшей мере 99,8% этих пар будет равна нулю, но сама модель не должна указывать на то, что появление любой из этих пар в тексте невозможно. Поэтому требуется определенный способ сглаживания нулевых результатов фактического подсчета количества пар. Простейший способ выполнения этой задачи состоит в использовании так называемого способа сглаживания с добавлением единицы: к результатам подсчета количества всех возможных двухсловных сочетаний добавляется единица. Поэтому, если количество слов в текстовой совокупности равно N, а количество возможных двухсловных сочетаний равно в, то каждому двухсловному сочетанию с фактическим количеством с присваивается оценка вероятности (с+1) / (N+B). Такой метод позволяет устранить проблему л-словных сочетаний с нулевой вероятностью, но само предположение, что все результаты подсчета количества должны быть увеличены точно на единицу, является сомнительным и может привести к получению некачественных оценок.
Еще один подход состоит в использовании метода сглаживания с линейной интерполяцией, в котором предусматривается объединение моделей трех-, двух- и однословных сочетаний с помощью линейной интерполяции. Оценка вероятности определяется по следующей формуле, с учетом того, что с3+с2+с1=1:
РЫх | Wi-2Wi-l) = С3 P{Wi | Wi-2lVi-l) + С2 P(Wi\Wi-i) + Ci P{Wi)
Параметры cL могут быть заранее заданными или полученными путем обучения по алгоритму ЕМ. Существует возможность применения значений ci? независимых от количества n-словных сочетаний, с тем, чтобы можно было присвоить больший вес оценкам вероятностей, полученным на основании больших значений количества.
Один из методов оценки языковой модели состоит в следующем. Вначале текстовая совокупность разделяется на обучающую совокупность и контрольную совокупность. Затем определяются параметры модели с помощью обучающих данных. После этого выполняется расчет вероятности, присвоенной контрольной совокупности с помощью данной модели; чем выше эта вероятность, тем лучше. Одним из недостатков этого подхода является то, что вероятность Р (words) при наличии длинных строк становится весьма небольшой; такие малые числовые значения могут вызвать антипереполнение в арифметике с плавающей точкой или просто стать неудобными для чтения. Поэтому вместо вероятности может быть вычислен показатель связности (perplexity) модели на контрольной строке слов words следующим образом:
Perplexity (words) = 2-log2(p(words) >/N
где N— количество слов words. Чем ниже показатель связности, тем лучше модель. Модель n-словных сочетаний, которая присваивает каждому слову вероятность 1/к, имеет показатель связности к; показатель связности может рассматриваться как средний коэффициент ветвления.
В качестве примера того, для чего может использоваться модель n-словных сочетаний, рассмотрим задачу сегментации — поиска границ между словами в тексте без пробелов. Решением этой задачи обычно приходится заниматься при обработке текстов на японском и китайском языках, в которых отсутствуют пробелы между словами, но авторы полагают, что для большинства читателей более удобным будет пример из английского. Приведенное ниже предложение действительно несложно прочитать любому, кто знает английский язык.
Itiseasytoreadwordswithoutspaces
На первый взгляд может показаться, что для решения такой задачи приходится пользоваться всеми знаниями в области синтаксиса, семантики и прагматики английского языка. Но ниже будет показано, что в данном предложении можно легко восстановить пробелы с использованием простой модели однословных сочетаний.
В одной и предыдущих глав было показано, что для решения задачи поиска наиболее вероятной последовательности прохождения через решетку вариантов выбора слова может использоваться уравнение Витерби (15.9). А в листинге 23.1 приведен вариант алгоритма Витерби, специально предназначенный для решения задачи сегментации. Этот алгоритм принимает в качестве входных данных распределение вероятностей однословных сочетаний, P(word), и некоторую строку. Затем для каждой позиции i в данной строке это алгоритм сохраняет в переменной best [ i ] значение вероятности наиболее вероятной строки, которая охватывает участок от начала до позиции i. Кроме того, в этом алгоритме в переменной words [i] сохраняется слово, оканчивающееся в позиции i, которое получило наибольшую вероятность. После того как по методу динамического программирования будут сформированы массивы best и words, в алгоритме осуществляется обратный поиск через массив words для определения наилучшего пути. В данном случае при использовании модели однословных сочетаний, соответствующей оригиналу этой книги, наиболее приемлемая последовательность слов действительно принимает вид "It is easy to read words without spaces" с вероятностью 10~25. Сравнивая отдельные части этого предложения, можно обнаружить, что слово "easy" имеет вероятность однословного сочетания 2 . 6х10-4, а альтернативный вариант его прочтения, "е as у", имеет намного более низкую вероятность, 9.8Х10"12, несмотря на тот факт, что слова (точнее, имена переменных) "е" и "у" довольно часто встречаются в уравнениях данной книги. Аналогичным образом, другая часть этого предложения характеризуется следующими данными:
Р("without") = 0.0004 PC'with") = 0.005 P("out") = 0.0008
PC'with out") = 0.005 x 0.0008 = 0.000004
function Viterbi-Segmentation(text, P) returns последовательность наиболее подходящих слов sequence и значения вероятностей слов этой последовательности
Листинг 23.1. Алгоритм сегментации строки на отдельные слова с помощью уравнения Витерби. Этот алгоритм восстанавливает наиболее вероятную сегментацию строки на слова после получения строки с удаленными пробелами
Поэтому слово "without" имеет в 100 раз более высокую вероятность, чем сочетание слов "with out", согласно применяемой модели однословных сочетаний.
В данном разделе рассматривались модели n-элементных сочетаний, элементами которых являются слова, но широкое применение находят также модели n-элементных сочетаний, применяемые к другим элементам текста, таким как символы или части речи.