Главная > Разное > Последовательные методы в распознавании образов и обучении машин
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.2. Отбор и упорядочение признаков — разложение Карунена — Лоэва

В данном параграфе излагается другой подход к отбору и упорядочению признаков, в котором не требуется полного знания вероятностных описаний входных образов. Основная идея в сущности заключается в предварительном приписывании весов признакам соответственна их относительной важности для характеристики входных образов независимо от специфической схемы распознавания, используемой в системе. «Относительная важность» понимается здесь в следующем смысле: (1) допускается меньшая ошибка аппроксимации усеченным конечным рядом замеров и (2) несет больше информации относительно различения классов. На основе этой идеи и использования разложения Карунена — Лоэва была разработана оптимальная процедура отбора и упорядочения признаков [7, 8]. Ниже эта процедура описывается в обобщенном варианте [18]. Обобщенное разложение Карунена — Лоэва вначале дается для непрерывного случая, далее приводится соответствующее изложение для дискретного случая.

Рассмотрим наблюдение стохастического процесса Наблюдаемая случайная функция порождена одним из возможных стохастических процессов каждый из которых соответствует одному из классов образов.

Пусть эти случайные функции обладают разложением

где величины являются случайными коэффициентами, удовлетворяющими условию (это можно осуществить путем симметрирования всех случайных функций и поэтому может быть допущено без потери общности); есть множество детерминированных ортонормированных координатных функций на

Определим функцию ковариаций для стохастических процессов следующим образом:

где комплексно-сопряженное После подстановки (2.24) в (2.25) получим

Пусть случайные коэффициенты удовлетворяют условиям

Тогда (2.25) приобретает вид

Таким образом, если для существует разложение (2.24) и случайные коэффициенты удовлетворяют условиям (2.27), то функция ковариаций должна обладать представлением вида (2.28). Далее, из (2.28) следует

Если можно поменять местами суммирование и интегрирование, то (2.29) получит вид

Разложение (2.24), в котором определяется, согласно (2.29) или (2.30), через известную функцию ко-вариаций называется обобщенным разложением Карунена — Лоэва. Было показано, что обобщенное разложение Карунена — Лоэва обладает следующими оптимальными свойствами: (1) оно минимизирует среднеквадратичную ошибку, вносимую при учете лишь конечного числа членов в бесконечном ряде разложения и (2) оно минимизирует функцию энтропии, определенную на дисперсиях случайных коэффициентов разложения. Доказательство этих оптимальных свойств приведено в приложении В.

Следует заметить, что необходимые условия, сформулированные в (2.27), по существу означают, что случайные коэффициенты должны быть некоррелированными между каждой парой координатных функций среди всех классов стохастических процессов. Однако случайные коэффициенты не должны быть некоррелированными между каждой парой координатных функций для одного класса. Тот же результат с теоретико-информационной точки зрения был получен Барабашем [9].

Если вместо случайной функции непрерывно наблюдаемой на берутся только выборочные замеры этой случайной функции, то искомое представление получает следующий вид:

Величины являются случайными коэффициентами, есть составляющая координатного вектора

в представляющего множество ортонормированных координатных векторов. Определим дискретный аналог функции ковариаций для стохастических процессов в виде

Далее, вследствие ортонормированности координатных векторов

Обобщенное разложение Карунена — Лоэва в дискретном случае получает следующий вид:

где величины удовлетворяют (2.33) и случайный коэффициент определяется для каждого формулой

Заметим, что (2.33) является дискретным эквивалентом интегрального уравнения (2.30). Координатные векторы обобщенного разложения Карунена — Лоэва являются в сущности собственными векторами, опредеделяемыми из Оптимальные свойства минимизированной среднёкватгратичной ошибки и функции энтропии обобщенного разложения Карунена — Лоэва приводят к оптимальной процедуре отбора и упорядочения признаков. При правильном построении обобщенной

координатной системы Карунена — Лоэва на основе (2.30) или (2.33) и при расположении координатных функций или координатных векторов в порядке убывания соответствующих им собственных значений измерение признаков, выполняемое согласно этому порядку, будет давать наибольшее количество информации относительно входных образов, где бы ни остановился процесс распознавания при конечном числе измерений. Следующая теорема, суммирующая результаты, полученные в этом параграфе, дает удобный путь для построения оптимальной координатной системы.

Теорема 2.1. Пусть представляют собой стохастических процессов и соответствующие вероятности их реализаций. Пусть эти случайные функции обладают разложением

где случайные коэффициенты с нулевым средним и множество ортонормированных координатных функций на Тогда необходимым и достаточным условием того, что множество координатных функций является обобщенной системой Карунена-Лоэва, определенной в (2.30), будет равенство

где символ Кронекера и

Доказательство достаточности дано в процессе вывода оптимальных свойств обобщенного разложения Карунена — Лоэва в приложении В. Чтобы доказать необходимость, предположим, что функция ковариаций может быть представлена в виде (2.28), где определено из (2.30). Из

Тогда

Заметим, что теорема 2.1 остается справедливой и для дискретного случая, если ввести соответствующие дискретные величины. Из теоремы 2.1 легко видеть, что построение искомой координатной системы можно рассматривать как определение таких координатных функций (или векторов), координатные коэффициенты которых взаимно не коррелированы, так что условия (2.27) удовлетворяются. Процедура в основном заключается в декорреляции координатных коэффициентов в ансамбле всех выборок образов из различных классов. Во многих задачах распознавания, для которых функции ковариаций вещественны и симметричны, процесс декорреляции сводится просто к приведению к диагональной форме рассматриваемых функций ковариаций.

Фактическая процедура отбора и упорядочения признаков сводится для дискретного случая к следующим шагам.

Шаг 1. Получить функцию ковариаций определенную в (2.32), из векторов признаков, найденных из заданных выборок образов. Если составляющие векторов признаков имеют вещественные значения, то будет вещественной симметричной матрицей.

Шаг 2. Найти собственные значения и соответственные им собственные векторы для Пусть собственные векторы нормированы и расположены в порядке Убывания соответствующих им собственных значений. Множество ортонормированных векторов, полученное

таким путем, образует обобщенную координатную систему Карунена — Лоэва.

Шаг 3. Выполнить преобразование (2.34), где величины являются составляющими ортонормированных собственных векторов, полученных в шаге 2. Полученные представляют собой искомые координатные коэффициенты членов обобщенной координатной системы Карунена — Лоэва.

Следует отметить, что при перестановке собственных векторов согласно расположению соответствующих собственных значений в порядке их убывания достигается полное упорядочение замеров признаков. Эти собственные значения представляют собой не что иное, как дисперсии преобразованных коэффициентов. Согласно

Можно получить выражение для средней минимизированной ошибки на периоде времени

которая представляет собой убывающую функцию Так как то полное упорядочение замеров признаков в порядке убывания их собственных значений дает меньшую ошибку, чем любой другой порядок, если процесс распознавания заканчивается при конечном числе измерений. Кроме того, так как предлагаемая процедура не зависит от схемы классификации, используемой в системе распознавания, то задачу отбора подмножества признаков из данного множества можно рассматривать как часть задачи упорядочения признаков.

Процедура полного упорядочения координатных векторов позволит нам отобрать подмножество замеров признаков с минимизированной

среднеквадратичной ошибкой путем простого выбора первых координатных векторов в полученной системе Карунена — Лоэва. Для иллюстрации процедуры в 2.3 будет приведен пример вычислений.

<< Предыдущий параграф Следующий параграф >>
Оглавление