Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 206
Текст из файла (страница 206)
Приближенный вероятностный вывод в сетях РВХ В главе 14 были описаны два алгоритма аппроксимации — взвешивание с учетом правдоподобия (см, листинг 14.5) и метод Монте-Карло на основе цепи Маркова (алгоритм МСМС, см. листинг 14.6). Из этих двух алгоритмов наиболее легко к контексту РВ)Ч адаптируется первый алгоритм. Тем не менее, как будет показано ниже, в стандартный алгоритм взвешивания с учетом правдоподобия необходимо внести несколько усовершенствований, прежде чем появится практически применимый метод. Напомним, что метод взвешивания с учетом правдоподобия действует по принципу осуществления в топологическом порядке выборок в узлах сети, не являющихся узлами свидетельства, и взвешивания каждой выборки с учетом правдоподобия того, что она соответствует наблюдаемым переменным свидетельства.
Как и при использовании точных алгоритмов, алгоритм взвешивания с учетом правдоподобия можно было бы применить непосредственно к развернутой сети РВИ, но по мере увеличения длины последовательностей наблюдений это привело бы к возникновению таких же сложностей, связанных с увеличением требований ко времени и пространству в расчете на каждое обновление. Проблема состоит в том, что в стандартном алгоритме каждая выборка обрабатывается последовательно, по всей сети.
Вместо этого можно просто пропустить через сеть РВИ все д( выборок вместе, проходя каждый раз через один временной срез. Этот модифицированный алгоритм имеет такую же общую форму, как и другие алгоритмы фильтрации, но в нем в качестве прямого сообщения используется множество из дгвыборок. Поэтому первым ключевым усовершенствованием должно быть то, чтобы в этом алгоритме ~яп в качестве приближенного представления текущего распределения вероятностей состояния использовались сами выборки. Такая организация работы соответствует требованию обеспечения "постоянных" затрат времени в расчете на каждое обновление, хотя само это постоянное значение зависит от количества выборок, необходимых для достижения приемлемой аппроксимации истинного апостериорного распределения. Кроме того, нет необходимости развертывать сеть РВ)ч(, поскольку в памяти требуется держать только текущий временной срез и следующий временной срез.
В описании метода взвешивания с учетом правдоподобия, приведенного в главе 14, было указано, что точность алгоритма снижается, если переменные свидетельства находятся в "прямом направлении" от переменных, по которым осуществляется выборка, поскольку в таком случае выборки формируются, не испытывая какого- либо влияния со стороны свидетельства. Рассматривая типичную структуру сети РВХ (допустим, сети РВ)Ч для задачи с зонтиком на рис. 15.12), можно убедиться в том, что в действительности выборку ранее полученных переменных состояния Глава 15. Вероятностные рассуждения во времени 755 можно осуществлять, не пользуясь полученным в дальнейшем свидетельством. Проанализировав фактически этот вопрос более внимательно, можно обнаружить, что ни у одной из переменных состояния не имеется среди ее предков ни одной переменной свидетельства! Поэтому, хотя вес каждой выборки зависит от свидетельства, фактически сформированное множество выборок является полностью независимым от свидетельства.
Например, даже если директор ходит с зонтиком каждый день, в процессе осушествления выборки все еше может создаваться впечатление, что солнечные дни не кончаются. С точки зрения практики это означает, что доля выборок, остаюшихся достаточно близкими к фактическому ряду собьпий, падает экспоненциально со значением с, т.е. с длиной последовательности наблюдении; иными словами, чтобы поддерживать заданный уровень точности, необходимо увеличивать количество выборок экспоненциально в зависимости от с. Учитывая то, что алгоритм фильтрации, работаюший в реальном времени, может использовать лишь фиксированное количество выборок, на практике происходит то, что после небольшого количества этапов обновления ошибка становится весьма значительной. Очевидно, что требуется лучшее решение.
Поэтому второе важное нововведение состоит в том, что ог- множество выборок в основном следует формировать в областях пространства состояний, харакп1еризуюи(ихся высокой вероягппастьв. Такую задачу можно выполнить, отбрасывая выборки, которые, согласно наблюдениям, имеют очень малый вес, вместе с тем увеличивая количество выборок, имеюших большой вес. Благодаря этому появляется возможность создавать множества выборок, которые остаются достаточно близкими к действительным данным. Если выборки рассматриваются как информационные ресурсы для моделирования распределения апостериорных вероятностей, то имеет смысл формировать больше выборок в тех областях пространства состояний, где апостериорная вероятность выше. Для решения именно этой задачи предназначено семейство алгоритмов, называемых алгоритмами 'ж фильтрации частиц.
Метод фильтрации частиц действует следующим образом: прежде всего создается популяция из в)выборок путем формирования выборок из распределения априорных вероятностей в момент времени О, Р(х,), затем, как описано ниже, для каждого временного интервала повторяется цикл обновления. ° Каждая выборка распространяется в прямом направлении путем формирования выборки значения переменной следующего состояния х„,. Для этого в качестве выборки берется текущее значение х„и используется модель переходап(х„,)х,). ° Каждая выборка взвешивается с учетом правдоподобия, которое она присваивает новому свидетельству, Р (е„, ) х„, ) . ° В этой популяции выборок снова осуществляется формирование выборки для создания новой популяции из в) выборок. Каждая новая выборка берется из текущей популяции; вероятность того, что будет получена конкретная выборка, пропорциональна ее весу.
Данные о весах новых выборок уничтожаются. Этот алгоритм подробно показан в листинге 15.3, а пример его применения к сети ОВХ для задачи с зонтиком приведен на рис. 15.13. 757 Глава 15. Вероятностные рассуждения во времени ния прямого сообщения дь, во время с. Поэтому, записав выражение дг(х, ~ еь.) для количества выборок, занимающих состояние х„после обработки наблюдений еь „получаем следующее соотношение для больших значений й: )Ч(м, ~еь„) /ВГ = Р(х,)еьс) (15.21) Теперь распространим каждую выборку в прямом направлении, осуществляя формирование выборок значений переменных состояния во время с+1 и взяв для каждой выборки значения во время с. Количество выборок, достигающих состояния х„„из каждого состояния х„равно вероятности перехода, умноженной на величину популяции х„поэтому общее количество выборок, достигаю)цих х„ь будет равно следующему; д)(х„~(еь,) = ~ Р(х„,(м„) гг(х,~еьд После этого выполним взвешивание каждой выборки по ее правдоподобию применительно к свидетельству во время са1.
Любая отдельная выборка в состоянии х„, полУчает вес Р(в„г ~ х„,) . Это означает, что сУммаРный вес выбоРок в состоЯ- нии х„, после получения свидетельства е„, определяется таким образом: У(хое(впьм) = Р(Е...(ХЬЕ) З)(Мха(ЕЬ„) Далее выполняется этап повторного формирования выборки. Поскольку каждая выборка тиражируется с вероятностью, пропорциональной ее весу, количество выборок в состоянии х„, после повторного формирования выборки пропорционально суммарному весу в состоянии хоп перел повторным формированием выборки, как показано ниже. ВГ(мь1(еь„1) /)Ч = а )Г(хне (еь„г) = а Р(енн(хнп) В)(менатеп,) = П Р(е, 1)хс 1) ) Р(хее(м,) г)(м,)еь„) м„ вЂ” и вг Р(е, 1(х„1) ~ Р(мнн(м,) Р(х,(еь,) (согласно 15.21) м П' Р(ее,(мае),) Р(х„1(хс) Р(х,(еьс) хс Р(хье(еьнц) (согласно 15.3) Поэтому популяция выборок после одного цикла обновления правильно представляет прямое сообщение во время с+1. Итак, алгоритм фильтрации частиц является согласованным, но характеризуется ли он достаточной эффективностью? Создается впечатление, что на практике ответ на этот вопрос является положительным: по-видимому, фильтрация частиц позволяет поддерживать хорошую аппроксимацию истинных апостериорных вероятностей с использованием постоянного количества выборок.
Тем не менее теория еще не дает такой гарантии; в настоящее время в области фильтрации частиц продолжаются интенсивные исследования. Предложено много вариантов и усовершенствова- 758 Часть Ч. Неопределенные знания и рассуждения в условиях неопределенности ний, а спектр приложений этого алгоритма стремительно растет. Поскольку алгоритм фильтрации представляет собой алгоритм формирования выборок, его можно легко применить к гибридным и непрерывным сетям РВХ, что дает возможность воспользоваться этим алгоритмом в таких областях, как отслеживание сложных движушихся образов в видеозаписях (719] и предсказание курсов акций на фондовой бирже (343). 15.6.
РАСПОЗНАВАНИЕ РЕЧИ В данном разделе рассматривается одно из наиболее важных приложений временных вероятностных моделей — сь распознавание речи. Задача состоит в том, чтобы выявить последовательность слов, произнесенных говорящим, используя акустический сигнал. Речь — это доминирующая форма обшения людей, и поэтому надежное распознавание речи с помощью машин было бы чрезвычайно полезным. Еше более важной задачей является понимание речи — идентификация смысла фрагментов речи.
Но изучение этой темы мы отложим до главы 22. Речь — это одно из первых проявлений грубого неоткристализовавшегося мира реальных сенсорных данных, с которыми сталкивается человек после своего рождения. Эти данные являются зашумленными, в буквальном смысле слова: в них может присутствовать не только фоновый шум, но и помехи, возникающие в процессе самого преобразования в осознаваемую человеком форму; слова иногда произносятся по-разному, даже одним и тем же говорящим; различные слова могут звучать одинаково и т.д. По этим причинам со временем возникло понимание того, что распознавание речи должно рассматриваться как одна из задач вероятностного вывода. На наиболее обшем уровне эту задачу вероятностного вывода можно определить следующим образом.
Предположим, что (дог.с(а — случайная переменная, пробегаюшая по всем возможным последовательностям слов, которые могут быть произнесены, а также допустим, что эудпа2 — наблюдаемая последовательность акустических сигналов. В таком случае наиболее вероятной интерпретацией фрагмента речи является то значение переменной йгопг(а, которое максимизирует вероятность Р(ыопс э~ абдпа1) . Как и во многих других случаях, нам может помочь применение правила Байеса: Р(ыпгйа(аддпа1) = а Р(аддпа1(ьопса) Р(ыпппа) Выражение Р( аздпа2 ! ыопда) называется 'а. акустической моделью. Эта модель описывает звуки слов, например, говорит о том, что слово "сейп8" (потолок) начинается с мягкого звука "с" и звучит так же, как квеа1(п8" (уплотнение).
(Слова, звучашие одинаково, часто называют сьомофонами.) Выражение Р(ыопс)а) принято называть языковой моделью. Эта модель задает априорную вероятность каждого фрагмента речи, например указывает, что последовательность слов "))18)) сейп8" (высокий потолок) является гораздо более вероятной, чем "))18)з зеа1(п8" (высокое уплотнение). Языковые модели, используемые в системах распознавания речи, обычно являются очень простыми. Модель двухсловиых сочетаний, которая будет описана ниже вданном разделе, задает вероятность каждого слова, которое следует за каждым другим словом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
