§ 8.1. Дискретное разложение Карунена — Лоева

Рассмотрим вначале выбор признаков в случае одного распределения. При наличии только одного распределения нельзя говорить о разделимости классов, т. е. о задаче распознавания образов. Вместо этого мы рассмотрим, насколько точно можно описать объекты, генерированные в соответствии с распределеним с помощью набора признаков. Если с помощью небольшого числа признаков удается точно описать объекты, то можно сказать, что такие признаки эффективны. Хотя эта задача непосредственно не связана с распознаванием образов, знание характеристик отдельных распределений помогает отделить одно распределение от других. Кроме того, выбор признаков для случая одного распределения находит широкое применение в других областях, таких, как представление сигналов и сжатие данных в системах связи. Еще одно ограничение связано с тем, что ищутся только такие признаки, которые можно получить линейным преобразованием исходных переменных. Как видно из рис. 8.1, новый признак у весьма эффективен для представления данных объектов, но этот признак является нелинейной функцией относительно

Рис. 8.1. Нелинейное преобразование.

8.1.1. Критерий минимума среднеквадратичной ошибки.

Пусть X — n-мерный случайный вектор. Тогда X можно точно представить разложением

где

а

Матрица Ф является детерминированной и состоит из линейно независимых векторов-столбцов, т. е.

Следовательно, линейные комбинации столбцов матрицы Ф образуют -мерное пространство, содержащее X. Столбцы матрицы Ф называются базисными векторами. Далее можно предположить, что эти столбцы ортоиормированы, т. е.

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

Следовательно, представляет собой ортогональное преобразование случайного вектора X и тоже является случайным вектором. Каждая компонента является признаком, который вносит вклад в представление наблюдаемого вектора X.

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

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

Заметим, что как X, так и являются случайными векторами. Используем среднюю величину квадрата в качестве критерия для измерейия эффективности подмножества, состоящего из

признаков:

Каждому набору базисных векторов и значений констант соответствует некоторое значение Выберем их таким образом, чтобы минимизировать Оптимальный выбор констант производится следующим образом:

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

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

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

т. е. оптимальные базисные векторы — это собственные векторы ковариационной матрицы Таким образом, минимальная среднеквадратичная ошибка равна

Разложение случайного вектора по собственным векторам ковариационной матрицы представляет собой дискретный вариант разложения Карунена — Лоева.

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

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

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

2. Рассматриваемые признаки взаимно иекоррелировапы, т. е. ковариационная матрица случайного вектора диагональна:

В частном случае, когда случайный вектор X распределен нормально, признаки взаимно независимы.

3. Собственные векторы ковариационной матрицы дают наименьшее значение среднеквадратичной ошибки среди всех ортонормированных базисных векторов. Неортогональные» линейные преобразования в зтой главе не рассматриваются: в случае одного распределения нас интересуют лишь те преобразования, которые сохраняют структуру распределения.

Доказательство свойства 3. Предположим, что мы разложили случайный вектор X по столбцам другой ортогональной матрицы Рассмотрим матрицу

диагональный элемент которой имеет вид

Разобьем матрицу Н на подматрицы следующим образом:

Тогда среднеквадратичная ошибка в случае, если измеряются

только компопент вектора имеет вид

(в соответствии с равенством (8.12), которое было получена только из условия ортогональности Ф. Наша цель состоит том, чтобы показать, что среднеквадратичная ошибка ограничена снизу значением выражения (8.14).

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

Так как матрицы ортогональны, матрица также ортогональна, так как

Разобьем матрицу (8.21) аналогично (8.19):

Из этого следует, что

Тогда суть нашего доказательства состоит в том, чтобы показать:

Из ортогональности матрицы имеем следующие тождества:

Продолжим доказательство:

Первое неравенство следует из того, что наименьшее собственное значение матрицы , a - наибольшее собственное значение матрицы Мы воспользовались здесь матричным тождеством и тождествами (8.26) — (8.28). Подробное обоснование неравенства (8.29) оставлено в качестве упражнения. Когда имеем так что неравенство превращается в равенство.

Рис. 8.2. Примеры разложения Карунена — Лоева.

Доказательство окончено.

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

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

Во-первых, вычислим выборочную ковариационную матрицу Для данных соответственно имеем:

Во вторых, найдем собственные значения и собственные векторы матрицы 2

Таким образом, в обоих случаях базисные векторы повернуты на угол 45°, как показано на рис. 8.2.

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

Рис. 8.2, а показывает, что все четыре объекта можно без ошибки выразить через первый базисный вектор . С другой стороны, для данных б) собственное значение Поэтому мы ожидаем, что при исключении из разложения вектора среднеквадратичная ошибка будет равна 1. Из рис. видног что объекты можно выразить через вектор без ошибки, но объекты и выражаются с ошибкой, равной Поэтому сред неквадратичная ошибка равна

т. е. равна собственному значению