Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 211
Текст из файла (страница 211)
При наличии п последовательностей наблюдений и и трактов слежения (т.е. в довольно благоприятном случае) существует п! возможных присваиваний последовательностей наблюдений трактам слежения; в правильной вероятностной трактовке должны учитываться все эти варианты присваивания, поэтому можно показать, что такая задача является ]ч]Р-трудной [301], [302]. По-видимому, на практике хорошо работают методы аппроксимации с полиномиальными затратами времени, основанные на использовании алгоритма МСМС [1180].
Любопытно отметить, что задача ассоциирования данных представляет собой один из экземпляров задачи вероятностного вывода в языке первого порядка; в отличие от большинства задач вероятностного вывода, которые являются чисто пропозициональными, в задаче ассоциирования данных рассматриваются объекты, а также отношение идентификации.
Поэтому она тесно связана с вероятностными языками первого порядка, которые упоминались в главе 14. В одной недавно опубликованной работе было показано, что формирование рассуждений об идентичности в общем и ассоциирование данных в частности могут осуществляться в рамках вероятностной инфраструктуры первого порядка [1179]. Скрытая марковская модель и связанные с ней алгоритмы вероятностного вывода и обучения, включая прямой — обратный алгоритм, были разработаны Баумом и Петри [85]. Аналогичные идеи были также высказаны независимо от них в сообществе специалистов по калмановской фильтрации [1269]. Прямой — обратный алгоритм был одним из основных предшественников более обгдей формулировки алгоритма ЕМ [383]; см.
также главу 20. Описание процедуры сглаживания в постоянном пространстве впервые появилось в [127], так же как и алгоритм, действующий по принципу "разделяй и властвуй*', который должен быть разработан при решении упр. !5 3. Динамические байесовские сети (Рупашьс Вауез)ап пе1ччог]с — РВ]ч]) могут рассматриваться как способ разреженного кодирования марковского процесса; они были впервые применены в искусственном интеллекте Дином и Канадзава ]361], Николсоном [1137] и Кьерульфом [803]. Последняя работа включает описание общего дополнения к системе сетей доверия Нп81п, которое предоставляет необходимые средства для формирования и компиляции динамической байесовской сети. Динамические байесовские сети нашли широкое применение для моделирования различных сложных процессов движения в системах машинного зрения [698], [718].
В [1443] явно показана связь между моделями НММ и сетями РВИ, а также между прямым — обратным алгоритмом и алгоритмом распространения в байесовской сети. Результаты дальнейшего обобщения фильтров Качмана (и других статистических моделей) опубликованы в [1314].
Особенно интересной является история алгоритма фильтрации частиц, описанного в разделе 15.5. Первые алгоритмы формирования выборок для фильтрации были разработаны Хендшиным и Мейном ]611], которые принадлежали к сообществу специалистов по теории управления, а идея повторного формирования выборок, лежащая в основе алгоритма фильтрации частицы, появилась в одной из публикаций в советском журнале по системам управления [1639]. В дальнейшем этот алгоритм был еще раз открыт в статистике и назван последовательным повторным формированием выборок с учетом их важности, или $!К (Бейпепйа1 !шронапсе-зашрйп8 Кезашр11п8) [939], [1315], в теории управления, под названием фильтрпция частиц [58!], [582], в искусственном интеллекте, под названием выживание наиболее при- 773 Глава 15.
Вероятностные рассуждения во времени способленного [769], и в области машинного зрения, под названием конденсация [719]. Статья Канадзава и др. [769] включает одно усовершенствование, называемое обращением свидетельства, согласно которому выборка в состоянии на момент времени 0+1 осуществляется условно, в зависимости от состояния во время е и свндетельства во время с+1.
Это позволяет обеспечить непосредственное влияние свидетельства на формирование выборок; в [406] было показано, что такой метод позволяет уменьшить ошибку аппроксимации. Другие метолы для аппроксимированной фильтрации включают алгоритм вырожденной модели МСМС [991] и метод факторизованной аппроксимации [164). Оба метода обладают тем важным свойством, что ошибка аппроксимации не расходится во времени.
Кроме того, для временных моделей были разработаны вариационные методы (см, главу 14). В [547) обсуждается алгоритм аппроксимации для факторной модели НММ вЂ” сети РВИ, в которой две или несколько независимо развивающихся марковских цепей связаны с помощью разделяемого потока наблюдений. В [747) рассматривается целый ряд других приложений. Свойства продолжительностей смешивания обсуждаются в [959] и [1164]. Предыстория систем распознавания речи началась в 1920-х годах с создания игрушки Кайо Кех — игрушечной собачки, активизируемой голосом. Собачка Кех прыгала в ответ на звуковые частоты около 500 Гц, которые соответствуют звучанию гласной ! егз! в слове "Кех!".
Немного более серьезная работа в этой области началась после Второй мировой войны. В АТТ Ве!1 Баба была создана система для распознавания отдельно произносимых цифр [333] с помощью простого согласования акустических характеристик с шаблонами. Вероятности перехода между фонемами впервые использовались в системе, созданной в лондонском 13п!уегз11у Сойейе Фраем [508] и Денесом [384]. Начиная с 1971 года Агентство перспективных исследовательских программ [РеГепзе Аг!уапсег! Кезеагсй Рго3есш Айепсу — РАКРА) Министерства обороны США финансировало четыре конкурирующих пятилетних проекта по разработке систем распознавания речи с высокой эффективностью.
Победителем этого соревнования и единственной системой, соответствующей требованиям по распознаванию словаря из 1000 слов с точностью 90% стала система Натру", разработанная в университете СМ13 [952), [953]. Окончательная версия системы Натру была создана на основе системы Ргайоп, разработанной аспирантом СМ1/ Джеймсом Бейкером [62]; в системе Ргайоп впервые использовались скрытые марковские модели для распознавания речи.
Почти одновременно с этим в компании 1ВМ была разработана еше одна система на основе модели НММ [730]. Начиная с этого времени вероятностные методы в целом и скрытые марковские модели в частности стали доминировать в исследованиях и разработках по распознаванию речи. Послелние годы характеризуются постепенным прогрессом, применением все более крупных наборов данных и моделей, а также ужесточением конкуренции в области решения все более реалистичных речевых задач. Некоторые исследователи изучали возмож- " Система Неагзау-11 14401, занявшая второе место в этом соревновании, испытала значительное влияние со стороны других направлений исследований в области искусственного интеллекта, поскольку в ней использовалась архитектура классной доски.
Она представляла собой экспертную систему на основе правил с многочисленными, более или менее независимыми, модульными источниками знаний, взаимодействовавшими через общую классную доску, на которой они могли писать и читать. Системы классной лоски стали основой современных архитектур пользовательского интерфейса. 774 Часть \~. Неопределенные знания и рассуждения в условиях неопределенности ность использования сетей 0ВХ вместо моделей НММ для распознавания речи с целью применения большей выразительной моши сетей ()ВХ для более полного охвата сложного скрытого состояния речевого аппарата [1286], [1652].
По проблематике распознавания речи имеется несколько хороших учебников: [568], [699], [73!], [1263]. В [1550] собраны важные статьи в этой области, включая некоторые учебные руководства. Материал, представленный в данной главе, основан на обзоре, приведенном в [781], и на учебнике [756]. Результаты исследований в области распознавания речи публикуются в журналах Сотршег ЮреесЬ алпЕал8иа8е, Зреесй Соттитсагюпз и !ЕЕЕ 7галзасгюпз ол Асоиясз, Зреесй, апг) 3(лпа! Ргосеззт8, в сборнике материалов семинаров РАКРА )('ог1п)юрз оп 5реесл алд р)шига) уал8иа8е Ргосетлл, а также в трудах конференций Ешозреесл, 7СБЕР и АЯ1(7.
УПРАЖНЕНИЯ 15.1. Покажите, что любой марковский процесс второго порядка может быть пере- оформлен в виде марковского процесса первого порядка с дополненным множеством переменных состояния. Может ли такое преобразование всегда быть выполнено экономно, т.е. без увеличения количества параметров, необходимых для определения модели перехода? 15.2. В этом упражнении рассматривается, что происходит с вероятностями в мире задачи с зонтиком по мере приближения к пределу в длинных временных послеловательностях.
а) Предположим, что наблюдается нескончаемая последовательность дней, в которых директор появляется на работе с зонтиком или без зонтика. Покажите, что, по мере того, как проходят эти дни, вероятность дождя в текущий день возрастает монотонно в направлении к фиксированной точке. Рассчитайте эту фиксированную точку. б) Теперь рассмотрим задачу прогнозирования все дальше и дальше в будущее по данным только первых двух наблюдений с зонтиком.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
