Многие важные идеи, касающиеся оценки состояния динамических систем, были высказаны математиком К.Ф.Гауссом [526], который сформулировал детерминированный алгоритм наименьших квадратов для решения задачи прогнозирования орбит небесных тел на основании астрономических наблюдений. Российский математик А.А. Марков [983] изложил в своих трудах, посвященных анализу стохастических процессов, подход, получивший в дальнейшем название марковского предположения; он провел оценку свойств марковской цепи первого порядка, состоящей из букв текста поэмы "Евгений Онегин". Важная классификационная работа по фильтрации была выполнена во время Второй мировой войны Винером [1588] для непрерывных временных процессов и Колмогоровым [825] для дискретных временных процессов. Хотя эта научная деятельность привела к важным технологическим усовершенствованиям, достигнутым в течение следующих 20 лет, в ней использовалось представление на основе данных об области определения частот, поэтому многие вычисления оказались весьма громоздкими. Как и было указано Сверлингом [1482] и Калманом [764], непосредственное моделирование стохастических процессов с помощью пространства состояний оказалось намного проще. В последней статье предложен метод прямого вероятностного вывода в линейных системах с гауссовым шумом, который теперь известен под названием фильтров Калмана. Важные результаты в области сглаживания были получены Раухом и др. [1269], и метод, получивший выразительное название метода сглаживания Рауха-Тунга—Стрибеля, все еще широко применяется и в наши дни. Многие ранние результаты исследований были собраны в [531]. В [71] приведена более современная трактовка в байесовском стиле, а также многочисленные ссылки на необъятную литературу по этой теме. В [241] рассматривается "классический" подход к анализу временных рядов.
Во многих приложениях калмановской фильтрации приходится сталкиваться не только с неопределенными данными восприятия и неизвестными законами, но также и с неопределенной идентификацией; это означает, что если ведется текущий контроль за многочисленными объектами, система должна определить, какие данные наблюдений собраны от тех или иных объектов, прежде чем появится возмож-
ность обновить оценки состояний каждого из этих объектов. В этом заключается проблема "2S-ассоциирования данных [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]. Начиная с этого времени вероятностные методы в целом и скрытые марковские модели в частности стали доминировать в исследованиях и разработках по распознаванию речи. Последние годы характеризуются постепенным прогрессом, применением все более крупных наборов данных и моделей, а также ужесточением конкуренции в области решения все более реалистичных речевых задач. Некоторые исследователи изучали возмож-
8 Система Hearsay-II [440], занявшая второе место в этом соревновании, испытала значительное влияние со стороны других направлений исследований в области искусственного интеллекта, поскольку в ней использовалась архитектура классной доски. Она представляла собой экспертную систему на основе правил с многочисленными, более или менее независимыми, модульными источниками знаний, взаимодействовавшими через общую классную доску, на которой они могли писать и читать. Системы классной доски стали основой современных архитектур пользовательского интерфейса.
ность использования сетей 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.
Back