7.6.2. Разложение Карунена — Лоэва

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

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

где

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

Ортогональные функции и числа определяются следующим образом. Пусть соотношения (7.6.6) — (7.6.8) справедливы для некоторого множества функций некоторого множества чисел и некоторого множества случайных переменных . В таком случае корреляционная функция определяется как

где и принадлежат интервалу Отметим, что, поскольку случайный процесс предполагается непериодическим, корреляционную функцию больше нельзя представлять в виде Из (7.6.9) получаем

Использование (7.6.7) дает

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

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

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

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

Автокорреляционная функция для М распознаваемых классов определяется выражением

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

применимо для распознавания лишь к случайным функциям «одного происхождения».

Подстановка выражения (7.6.13) в (7.6.14) приводит к

Отметим, что в разложении функции изменен индекс. Поскольку базисные функции детерминированны, соотношение (7.6.15) можно записать как

Допустим, что случайные коэффициенты статистически независимы в том смысле, что

где — константа. При выполнении этих условий формула (7.6.16) принимает следующий вид:

Умножение обеих частей (7.6 18) на и интегрирование по интервалу где ортонормированны, дает

Поменяв порядок выполнения суммирования и интегрирования, получим

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

Разложение, определяемое формулой (7.6.13), базисные функции которого отыскиваются с помощью уравнения (7.6.20) или (7.6.21) и автокорреляционная функция вычисляется согласно (7.6.14), называют обобщенным разложением Карунена—Лоэва. Термин «обобщенное» добавляется для того, чтобы подчеркнуть определение корреляционной функции по формуле (7.6.14), а не с помощью выражения , представляющего стандартное определение автокорреляционной функции.

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

Дискретный случай

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

где — количество наблюдений для функции осуществленных в интервале . Выражение (7.6.13) принимает в этом случае вид конечной суммы

причем относительно коэффициентов предполагается, что они удовлетворяют условию — вектор:

Если коэффициенты представлены в векторной форме

где , то (7.6.23) можно представить в более удобной матричной записи:

где Ф — матрица:

Дискретным аналогом автокорреляционной функции (7.6.14) служит автокорреляционная матрица, определяемая как

Подстановка в это соотношение выражения (7.6.26) для даег

Здесь второй шаг следует из детерминистской природы матрицы Ф.

Введя условие

где — диагональная матрица:

формулу (7.6.29) можно привести к виду

Если базисные векторы предполагаются ортонормированными, то обычным умножением (7.6.32) на матрицу Ф получим

так как в силу ортонормированности базисных векторов, составляющих матрицу Ф. Из (7.6.33) следует, что

это уравнение является дискретным аналогом уравнения (7.6.21).

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

последнее условие позволило получить (7.6.33). Исходя из этого свойства, определим коэффициенты разложения:

С помощью прямой подстановки можно проверить, что эти коэффициенты удовлетворяют условию (7.6.30). Кроме того, из формул (7.6.36) следует, что условие допускает еще одну интерпретацию:

т. е. предположение выполняется автоматически, если различные совокупности образов характеризуются нулевыми математическими ожиданиями.

Дискретный вариант обобщенного разложения Карунена — Лоэва представляется формулами (7.6.23) или (7.6.26), где базисными векторами служат ортонормированные собственные векторы корреляционной матрицы (7.6.28). Коэффициенты этого разложения определяются по формулам (7.6.36). Ниже рассматривается применение этих понятий при выборе признаков.

Применение дискретного разложения Карунена — Лоэва при выборе признаков

Основанием применения дискретного разложения Карунена—Лоэва в качестве средства выбора признаков является наличие у него отмеченных выше оптимальных свойств. В дискретном случае принцип минимизации среднеквадратичной ошибки предполагает, что разложение Карунена — Лоэва минимизирует ошибку аппроксимации при использовании в разложении (7.6.23) или (7.6.26) числа базисных векторов, меньшего Принцип минимизации энтропии обеспечивает искомые эффекты кластеризации, которыми обладает метод из § 7.5.

Применение дискретного разложения Карунена — Лоэва при выборе признаков можно рассматривать как линейное преобразование. Если

—матрица преобразования, то, согласно (7.6.36), преобразованные образы (изображения) являются коэффициентами разложения Карунена — Лоэва, т. е. для любого образа принадлежащего классу в силу (7.3.36) выполняется

Поскольку Ф — матрица размера -мерный вектор, то очевидно, что при представляют собой изображения, имеющие размерность, меньшую

Можно показать, что условия оптимальности разложения Карунена — Лоэва выполняются, если в качестве столбцов матрицы преобразования Ф выбраны нормированных собственных

векторов, соответствующих наибольшим характеристическим числам корреляцонной матрицы

Этот результат можно представить в той же форме, что была предложена в § 7.5, с помощью матрицы

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

Резюмируем описанные выше результаты.

1. По образам, входящим в обучающую выборку, при помощи соотношения (7.6.28) вычисляется корреляционная матрица

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

3. Из собственных векторов, соответствующих наибольшим характеристическим числам корреляционной матрицы по формуле (7.6.38) формируется матрица преобразования Ф.

4. По формулам (7.6.36) вычисляются коэффициенты разложения. Эти коэффициенты задают изображения с меньшей размерностью описания.

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

бесполезным, так как он предусматривает изменение характеристик рассматриваемых классов. Естественно, затруднения не возникнут в одном частном случае, когда математические ожидания всех классов равны. В этом случае все образы независимо от их принадлежности классам будут центрироваться относительно одного и того же математического ожидания как в процессе обучения, так и в процессе распознавания.

Хотя предположение об идентичности математических ожиданий всех совокупностей образов ограничивает возможности применения разложения Карунена — Лоэва, не следует считать, что этот подход к выбору признаков не имеет достоинств. Допущения такого типа характерны для большинства статистических методов анализа. Успех применения любого метода зависит только от того, насколько хорошо анализируемые данные соответствуют основным предположениям, принятым при разработке соответствующего статистического метода.

Пример. В качестве простой иллюстрации применения дискретного разложения Карунена — Лоэва рассмотрим обработку образов, представленных на рис. 7.2.

Здесь первый индекс указывает номер класса, которому принадлежит образ, а второй — номер соответствующего образа. Допустив, что , получим

(кликните для просмотра скана)

где обозначают математические ожидания, вычисляемые по всем образам классов соответственно. Выполнение этих операций по методу из § 4.6 дает следующее:

Характеристические числа и соответствующие им нормированные собственные векторы корреляционой матрицы R равны:

Выбрав собственные векторы , соответствующие наибольшим характеристическим числам, получим матрицу преобразования

Воспользовавшись преобразованием получаем изображения:

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

Рассмотрим матрицу преобразования

собственный вектор которой соответствует наибольшему характеристическому числу. Это преобразование переводит образы в точки:

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

Интересно отметить, что преобразование, минимизирующее энтропию, привело в этом случае к получению существенно

лучших результатов, чем преобразование, основанное на разложении Карунена — Лоэва. Это обстоятельство снова подчеркивает тот важный факт, что достоинства определенного метода выбора признаков зависят от того, к какой задаче он применяется.