БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Многие важные идеи, касающиеся оценки состояния динамических систем, были высказаны математиком К.Ф. Гауссом [526], который сформулировал детерминированный алгоритм наименьших квадратов для решения задачи прогнозирования орбит небесных тел на основании астрономических наблюдений. Российский математик А.А. Марков [983] изложил в своих трудах, посвященных анализу стохастических процессов, подход, получивший в дальнейшем название марковского предположения; он провел оценку свойств марковской цепи первого порядка, состоящей из букв текста поэмы "Евгений Онегин". Важная классификационная работа по фильтрации была выполнена во время Второй мировой войны Винером [1588] для непрерывных временнь/х процессов и Колмогоровым [825] для дискретных временных процессов. Хотя эта научная деятельность привела к важным технологическим усовершенствованиям, достигнутым в течение следующих 20 лет, в ней использовалось представление на основе данных об области определения частот, поэтому многие вычисления оказались весьма громоздкими. Как и было указано Сверлингом [1482] и Калманом [764], непосредственное моделирование стохастических процессов с помощью пространства состояний оказалось намного проще. В последней статье предложен метод прямого вероятностного вывода в линейных системах с гауссовым шумом, который теперь известен под названием фильтров Калмана. Важные результаты в области сглаживания были получены Раухом и др. [1269], и метод, получивший выразительное название метода сглаживания Рауха-Тунга—Стрибеля, все еще широко применяется и в наши дни. Многие ранние результаты исследований были собраны в [531]. В [71] приведена более современная трактовка в байесовском стиле, а также многочисленные ссылки на необъятную литературу по этой теме. В [241] рассматривается "классический" подход к анализу временнь/х рядов.
Во многих приложениях калмановской фильтрации приходится сталкиваться не только с неопределенными данными восприятия и неизвестными законами, но также и с неопределенной идентификацией; это означает, что если ведется текущий контроль за многочисленными объектами, система должна определить, какие данные наблюдений собраны от тех или иных объектов, прежде чем появится возможность обновить оценки состояний каждого из этих объектов. В этом заключается проблема ассоциирования данных [70], [71]. При наличии п последовательностей наблюдений и п трактов слежения (т.е. в довольно благоприятном случае) существует п\ возможных присваиваний последовательностей наблюдений трактам слежения; в правильной вероятностной трактовке должны учитываться все эти варианты присваивания, поэтому можно показать, что такая задача является NP-трудной [301], [302]. По-видимому, на практике хорошо работают методы аппроксимации с полиномиальными затратами времени, основанные на использовании алгоритма МСМС [1180]. Любопытно отметить, что задача ассоциирования данных представляет собой один из экземпляров задачи вероятностного вывода в языке первого порядка; в отличие от большинства задач вероятностного вывода, которые являются чисто пропозициональными, в задаче ассоциирования данных рассматриваются объекты, а также отношение идентификации. Поэтому она тесно связана с вероятностными языками первого порядка, которые упоминались в главе 14. В одной недавно опубликованной работе было показано, что формирование рассуждений об идентичности в общем и ассоциирование данных в частности могут осуществляться в рамках вероятностной инфраструктуры первого порядка [1179].
Скрытая марковская модель и связанные с ней алгоритмы вероятностного вывода и обучения, включая прямой-обратный алгоритм, были разработаны Баумом и Петри [85]. Аналогичные идеи были также высказаны независимо от них в сообществе специалистов по калмановской фильтрации [1269]. Прямой—обратный алгоритм был одним из основных предшественников более общей формулировки алгоритма ЕМ [383]; см. также главу 20. Описание процедуры сглаживания в постоянном пространстве впервые появилось в [127], так же как и алгоритм, действующий по принципу "разделяй и властвуй", который должен быть разработан при решении упр. 15.3.
Динамические байесовские сети (Dynamic Bayesian network — DBN) могут рассматриваться как способ разреженного кодирования марковского процесса; они были впервые применены в искусственном интеллекте Дином и Канадзава [361], Ни-колсоном [1137] и Кьерульфом [803]. Последняя работа включает описание общего дополнения к системе сетей доверия Hugin, которое предоставляет необходимые средства для формирования и компиляции динамической байесовской сети. Динамические байесовские сети нашли широкое применение для моделирования различных сложных процессов движения в системах машинного зрения [698], [718]. В [1443] явно показана связь между моделями НММ и сетями DBN, а также между прямым—обратным алгоритмом и алгоритмом распространения в байесовской сети. Результаты дальнейшего обобщения фильтров Калмана (и других статистических моделей) опубликованы в [1314].
Особенно интересной является история алгоритма фильтрации частиц, описанного в разделе 15.5. Первые алгоритмы формирования выборок для фильтрации были разработаны Хендшиным и Мейном [611], которые принадлежали к сообществу специалистов по теории управления, а идея повторного формирования выборок, лежащая в основе алгоритма фильтрации частицы, появилась в одной из публикаций в советском журнале по системам управления [1639]. В дальнейшем этот алгоритм был еще раз открыт в статистике и назван последовательным повторным формированием выборок с учетом их важности, или SIR (Sequential Importance-sampling Resampling) [939], [1315], в теории управления, под названием фильтрация частиц [581], [582], в искусственном интеллекте, под названием выживание наиболее при
способленного [769], и в области машинного зрения, под названием конденсация [719]. Статья Канадзава и др. [769] включает одно усовершенствование, называемое обращением свидетельства, согласно которому выборка в состоянии на момент времени t+1 осуществляется условно, в зависимости от состояния во время t и свидетельства во время t+1. Это позволяет обеспечить непосредственное влияние свидетельства на формирование выборок; в [406] было показано, что такой метод позволяет уменьшить ошибку аппроксимации.
Другие методы для аппроксимированной фильтрации включают алгоритм вырожденной модели МСМС [991] и метод факторизованной аппроксимации [164]. Оба метода обладают тем важным свойством, что ошибка аппроксимации не расходится во времени. Кроме того, для временнь/х моделей были разработаны вариационные методы (см. главу 14). В [547] обсуждается алгоритм аппроксимации для факторной модели НММ — сети DBN, в которой две или несколько независимо развивающихся марковских цепей связаны с помощью разделяемого потока наблюдений. В [747] рассматривается целый ряд других приложений. Свойства продолжительностей смешивания обсуждаются в [959] и [1164].
Предыстория систем распознавания речи началась в 1920-х годах с создания игрушки Radio Rex — игрушечной собачки, активизируемой голосом. Собачка Rex прыгала в ответ на звуковые частоты около 500 Гц, которые соответствуют звучанию гласной [eh] в слове "Rex!". Немного более серьезная работа в этой области началась после Второй мировой войны. В ATT Bell Labs была создана система для распознавания отдельно произносимых цифр [333] с помощью простого согласования акустических характеристик с шаблонами. Вероятности перехода между фонемами впервые использовались в системе, созданной в лондонском University College Фра-ем [508] и Денесом [384]. Начиная с 1971 года Агентство перспективных исследовательских программ (Defense Advanced Research Projects Agency — DARPA) Министерства обороны США финансировало четыре конкурирующих пятилетних проекта по разработке систем распознавания речи с высокой эффективностью. Победителем этого соревнования и единственной системой, соответствующей требованиям по распознаванию словаря из 1000 слов с точностью 90%, стала система Harpy8, разработанная в университете CMU [952], [953]. Окончательная версия системы Harpy была создана на основе системы Dragon, разработанной аспирантом CMU Джеймсом Бейкером [62]; в системе Dragon впервые использовались скрытые марковские модели для распознавания речи. Почти одновременно с этим в компании IBM была разработана еще одна система на основе модели НММ [730]. Начиная с этого времени вероятностные методы в целом и скрытые марковские модели в частности стали доминировать в исследованиях и разработках по распознаванию речи. Последние годы характеризуются постепенным прогрессом, применением все более крупных наборов данных и моделей, а также ужесточением конкуренции в области решения все более реалистичных речевых задач. Некоторые исследователи изучали возможность использования сетей DBN вместо моделей НММ для распознавания речи с целью применения большей выразительной мощи сетей DBN для более полного охвата сложного скрытого состояния речевого аппарата [1286], [1652].
По проблематике распознавания речи имеется несколько хороших учебников: [568], [699], [731], [1263]. В [1550] собраны важные статьи в этой области, включая некоторые учебные руководства. Материал, представленный в данной главе, основан на обзоре, приведенном в [781], и на учебнике [756]. Результаты исследований в области распознавания речи публикуются в журналах Computer Speech and Language, Speech Communications и IEEE Transactions on Acoustics, Speech, and Signal Processing, в сборнике материалов семинаров DARPA Workshops on Speech and Natural Language Processing, а также в трудах конференций Eurospeech, ICSLP и ASRU.