Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 301
Текст из файла (страница 301)
10] ) Х [0.25! [ зс [0.20] -ч еие [0.30] ) а [0.35] ) отеку [0.05] -+ Ео [О 30] ) зп [О 25] ) оп [О 05] 3[о ил иекЬ Ркспсип лксЕсзе Рксрсязезсп В модели РСЗО вероятность строки, Р[ьгопс]я), представляет собой сумму вероятностей деревьев синтаксического анализа этой строки. А вероятность данного конкретного дерева представляет собой произведение вероятностей всех правил, на основании которых сформированы узлы этого дерева. На рис. 23.! показано, как вычислить вероятность некоторого предложения. Такую вероятность можно вычислить, применяя синтаксический анализатор диаграмм СРО для перечисления возможных вариантов синтаксического анализа, а затем складывая полученные вероятности.
Но если нас интересует только наиболее вероятный вариант синтаксического анализа, то перебор всех маловероятных вариантов представляет собой бесполезную трату времени. Для эффективного поиска наиболее вероятного варианта синтаксического анализа может использоваться одна из разновидностей алгоритма Витерби или же какой-то метод поиска по первому наилучшему совпадению [такой как А'). РР ! 0,60 1'егЬ / 0,10 ЛР Ап!с!е гелин / 0,05 / 0,15 Ечегу немрт яме1Н Рис.
23.!. Дерево синтаксического анализа для предложения тбчегу митрич зте!Й", в котором показаны вероятности каждого поддерева. Вероятность всего дерева в целом равна 3. око. 5ко. 05ко. 35ко. поко. 10=0. 000225. Поскольку эгпо дерево является единственным вариантом синтаксического анализа данного предложения, указанное число представляет собой также вероятность этого предложения Листинг 23.2. Вероятностная контекстно-свободная грамматика (РСР6) н словарь для час- ти грамматики языка Е,. Числа в квадратных скобках показывают вероятность того, что вместо символа н левой части правила будет выполнена подстановка праной части соответ- ствующего правила !!08 Часть |Ч1.
Общение, восприятие и осуществление действий Недостатком грамматик РСРО является то, что они — контекстно-свободные. Это означает, что различие между р("еас а Ьапапа" ), "съешь банан", и р( "еас а Ьапс)аппа" ), "съешь цветной платок", зависит только от соотношения вероятностей р( "Ьапапа" ) и Р( "Ьапс)аппа" ), а не от вероятностей возникновения отношений между глаголом "еар' и соответствующими объектами. Для того чтобы можно было учитывать связи такого рода, нам потребуется контекстнозависимая модель определенного типа наподобие лексикализоваииой грамматики РСРб, в которой определенную роль в оценке вероятности соответствующего словосочетания может играть голова' этого словосочетания.
При наличии достаточного объема обучающих данных может быть получено правило для )гр — э ь'р ыр, обусловленное наличием головы входя(цего в него словосочетания ь'р ("еа!") и головы словосочетания ир ("Ьапапа"). Таким образом, лексикализованные грамматики РСЕО позволяют учитывать некоторые ограничения на совместное вхождение элементов в моделях п-элементных сочетаний, наряду с грамматическими ограничениями моделей СРО.
Еше один недостаток состоит в том, что грамматики РСРО обнаруживают слишком заметное предпочтение по отношению к более коротким предложениям. В такой текстовой совокупности, как архив журнала )Ра(1 аггее) уоигла(, средняя длина предложения составляет около 25 слов. Но обычно грамматика РСРО в конечном итоге присваивает гораздо более высокую вероятность таким правилам, как Я вЂ” э)ур ур, д)ы — >рхопоип и ур — ь(гегЬ. Это означает, что грамматика РСЕО присваивает весьма высокую вероятность многим коротким предложениям, таким как "Не з!ер!" (Он спал), тогда как в указанном журнале с большей вероятностью встречаются предложения наподобие следующего: "1) Ьаз Ьееп геропед Ьу а гейаЫе яочегпгпеп( ьоигсе гйа( (Ье айейагюп ГЬа! Ье з!ер( )з сгейЫе" (Из надежного правительственного источника поступило сообшение, согласно которому заявление о том, что он спал, заслуживает доверия).
Создается впечатление, что словосочетания в этом журнале не являются контекстно-свободными; вместо этого его авторы оценивают допустимую ожидаемую длину предложения и используют полученную оценку в качестве мягкого глобального ограничения на структуру составляемых ими предложений. Такой подход к написанию текста трудно отразить в грамматике РСРО. Определение с помощью обучения вероятностей для грамматики РСРС При создании любой грамматики РСРО приходится преодолевать все сложности, связанные с формированием грамматики СЕО, и наряду с этим решать проблему задания вероятностей для каждого правила. Такие обстоятельства наводят на мысль, что может оказаться более приемлемым подход, предусматривающий определение грамматики по имею(цимся данным с помощью обучения, чем подход, основанный на инженерии знаний.
Как и в случае распознавания речи, могут применяться данные двух типов — прошедшие и не прошедшие синтаксический анализ. Задача намного упрощается, если данные уже преобразованы в деревья с помощью синтаксического анализа лингвистами (или по меньшей мере носителями соответствующего естественного языка, прошедшими специальное обучение). Создание подобной тек- -' Головой словосочетания называется самос важное слово, например существительное в именном словосочетании.
Глава 23. Вероятностная обработка лингвистической информации !!09 стовой совокупности требует больших капиталовложений, и в настоягдее время самые крупные из таких совокупностей содержат "всего лишь" около миллиона слов. А если имеется некоторая совокупность деревьев, то появляется возможность создать грамматику РСРб путем подсчета (и сглаживания). Для этого достаточно просмотреть все узлы, в которых корневым является каждый нетерминальный символ, и создать правило для каждой отдельной комбинации дочерних элементов в этих узлах. Например, если какой-то символ ьгр появляется 100 тысяч раз и имеется 20 тысяч экземпляров дГР со списком дочерних элементов ! !уР, РР), то создается правило мР— + ггР РР [0.20! Если же текст не подвергнут синтаксическому анализу, то задача значительно усложняется.
Это прежде всего связано с тем, что фактически приходится сталкиваться с двумя разными проблемами — определение с помощью обучения структуры грамматических правил и определение с помощью обучения вероятностей, связанных с каждым правилом (с аналогичным различием приходится сталкиваться при определении с помощью обучения параметров нейронных или байесовских сетей).
На данный момент примем предположение, что структура правил известна и предпринимается лишь попытка определить вероятности с помощью обучения. Для этого может использоваться подход на основе алгоритма ожидания — максимизации (ехресгайоп — гпах(гпьзабоп — ЕМ), как и при обучении моделей НММ. В процессе обучения мы будем пытаться определить такие параметры, как вероятности правил. Скрытыми переменными являются деревья синтаксического анализа, поскольку неизвестно, действительно ли строка слов ьгг.ь м! сформирована с помощью правила х — эа. На этапе я оценивается вероятность того, что каждая подпоследовательность сформирована с помощью каждого отдельного правила.
Затем на этапе М оценивается вероятность каждого правила. Весь этот процесс вычисления может осуществляться в режиме динамического программирования с помощью алгоритма, называемого 'з. внутренним — внешним алгоритмом, по аналогии с прямым — обратным алгоритмом, применяемым для моделей НММ. На первый взгляд причины продуктивного функционирования внутреннего— внешнего алгоритма кажутся непостижимыми, поскольку он позволяет успешно сформировать логическим путем грамматику на основании текста, не прошедшего синтаксический анализ. Но этот алгоритм имеет несколько недостатков. Во-первых, он действует медленно; этот алгоритм характеризуется временными затратами 0(п'С'), где и — количество слов в предложении; с — количество не- терминальных символов. Во-вторых, пространство вероятностных присваиваний очень велико и практика показала, что при использовании этого алгоритма приходится сталкиваться с серьезной проблемой, связанной с тем, что он не выходит из локальных максимумов.
Вместо него могут быть опробованы такие альтернативные варианты, как эмуляция отжига, за счет еше большего увеличения обьема вычислений. В-третьих, варианты синтаксического анализа, присвоенные с помощью полученных в результате грамматик, часто трудно понять, а лингвисты находят их неудовлетворительными. В результате этого задача комбинирования знаний, представленных с помощью способов, приемлемых для человека, с данными, которые получены с помощью автоматизированного индуктивного логического вывода, становится затруднительной.
1110 Часть \Ч1. Общение, восприятие и осуществление действий Определение с помощью обучения структуры правил для грамматики РСРО Теперь предположим, что структура грамматических правил неизвестна. В таком случае сразу же возникает проблема, связанная с тем, что пространство возможных множеств правил является бесконечным, поэтому неизвестно, какое количество правил необходимо предусмотреть и какую длину должно иметь каждое правило. Один из способов решения этой проблемы состоит в том, чтобы организовать составление грамматики с помощью обучения в 'з. нормальной форме Хомского; это означает, что каждое правило должно находиться в одной из следующих двух форм: где х, у и е — нетерминальные символы; с — терминальный символ.
В виде грамматики в нормальной форме Хомского, которая распознает точно такой же язык, может быть представлена любая контекстно-свободная грамматика. В таком случае появляется возможность принять произвольное ограничение, согласно которому количество нетерминальных символов будет равно и, и тем самым будет получено из+им правил, где и — количество терминальных символов. Но практика показала, что такой подход является эффективным только применительно к небольшим грамматикам. Предложен также альтернативный подход, называемый 'з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
