20.3. Теория процедур оптимизации проекционных индексов

Пусть — выборка объема в Каждая статистика на -мерных выборках объема задает проекционный индекс , где А — некоторая проекция из .

Обозначим через — множество всех проекций из (см. п. 20.2.1). Решение статистической задачи методом целенаправленного проецирования содержит два этапа:

1) выбор проекционного индекса ;

2) решение оптимизационных эадач для функции на соответствующем подмножестве .

Вопросы, связанные с этапом 1, достаточно подробно разобраны в гл. 19. Основная цель настоящего параграфа — изложить теорию алгоритмов решения задач этапа 2.

20.3.1. Области оптимизации в задачах поиска выразительных проекций.

Начнем со структуры множества . Как отмечалось в п. 20.2.1, каждая проекция из однозначно определяется -матрицей А, удовлетворяющей условию . Поставим в соответствие -матрице А набор из q ее -мерных вектор-строк и заметим, что тогда и только тогда, когда эти векторы линейно независимы.

Пусть — линейное -мерное подпространство в натянутое на векторы составляющие матрицу проекции А. Тогда имеет место следующая лемма

Лемма 20.3. Соответствие позволяет отождествить с множеством всех пар , где L — -мерное подпространство в , а — некоторый базис в этом подпространстве.

Аналогично пусть — множество всех ортогональных проекций из в (см. п. 20.2.1). Тогда верна следующая лемма.

Лемма 20.4. Соответствие позволяет отождествить с множеством всех пар , где -мерное подпространство в — некоторый ортонормированный базис в этом подпространстве.

Указанное соответствие отождествляет, в частности, множество всех проекций из с множеством ненулевых векторов а множество всех ортогональных проекций из с множеством единичных векторов 9 (см. п. 20.2.1).

Определение 20.1. Статистика на (-мерных выборках называется инвариантной относительно преобразования В пространства если ).

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

Определение 20.2. Проекционный индекс F, построенный по статистике инвариантной относительно любого невырожденного преобразования, называется -инвариангным и соответственно О-инвариантным, если инвариантна относительно любого ортогонального преобразования.

Введем теперь так называемое многообразие Гроссмана , точками которого являются -мерные линейные подпространства .

Возьмем некоторый -инвариантный проекционный индекс . Рассмотрим -мерное линейное подпространство выберем в нем базис и тем самым получим проекцию из в . Положим, по определению,

(20.30)

Проекция определена с точностью до выбора базиса в L, но так как является -инвариантным, то формула (20.30) корректно задает функцию на многообразии Грассмана .

Следствие 20.2. Задача поиска выразительной проекции А для -инвариантного проекционного индекса эквивалентна задаче:

Следствие 20.3. Задача поиска выразительной ортогональной проекции А для О-инвариантного проекционного индекса также эквивалентна задаче (20.31). Естественно, при построении в этом случае необходимо взять некоторый ортогональный базис в найденном экстремальном подпространстве

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

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

Например, (одно уравнение связи на координат);

(три уравнения связи на координат).

Размерность многообразия на меньше, чем размерность объемлющего пространства Таким образом, применение обычных численных процедур для решения оптимизационных задач на многообразиях и как подмножествах евклидова пространства практически невозможно. Отметим, что попытка построить метод градиентного спуска на была предпринята в [121, § 6.10]. Трудности, которые встретились на этом пути, типичны для реализации процедур условной оптимизации при большом числе уравнений связи на координаты.

В [37—39] разработаны численные методы оптимизации функций на многообразии . Оказалось, что если использовать внутреннюю геометрию этого многообразия, то эти методы реализуются при помощи аналогов основных алгоритмов безусловной оптимизации.

20.3.2. Алгоритмы оптимизации функций на многообразиях проекций.

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

Опишем переход от Выберем введем семейство базисов где

(20.32)

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

Определение 20.3. Семейство -мерных плоскостей с называется -координатной линией в , проходящей через точку в локальной системе координат, задаваемой базисом

Обоснование такого определения см. в [37], где описаны все необходимые факты о структуре многообразия .

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

и полагаем Цикл процедуры оптимизации завершен.

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

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

Рассмотрим теперь дифференцируемую функцию на . Опишем алгоритмы, реализующие методы градиентной оптимизации.

Пусть, как и выше, , где — ортогональный базис в координатная линия в , проходящая через

Определение 20.4. Градиентом функции в точке относительно локальной системы координат, задаваемой базисом называется -мерный вектор вычисляемый по формуле

(20.33)

где

Градиент удобно представлять в матрицы с вектор-столбцами

Пример 20.4. Пусть и — его ортогональная проекция на некоторое -мерное линейное подпространство Рассмотрим на многообразии функцию и вычислим ее градиент в точке

Из (20.31) следует

(20.34)

поэтому непосредственно из (20.33) получаем:

(20.35)

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

(20.36)

При помощи функции легко показать, как зависит вид градиента от выбора базиса .

Пусть — ортонормированные базисы в

Заметим, что тогда и только тогда, когда существуют ортогональная -матрица В, переводящая базис в подпространстве в его базис и ортогональная -матрица переводящая базис в ортогональном дополнении к в его базис

Следовательно, если то

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

Имеем

Используя формулу (20.33), получаем в точке

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

(20.37)

или в терминах базиса

Рассматривая -матрицу как преобразование пространства получаем, что условие (20.37) выполняется тогда и только тогда, когда переводит подпространство в себя, т. е. когда -собственное подпространство ковариационной матрицы.

Как показано выше, ортогональная проекция из в R является выразительной относительно тогда и только тогда, когда является экстремальной точкой функции

Таким образом, для проекционного индекса F (А), построенного по статистике - на -мерных выборках, выразительными являются ортогональные проекции на собственные q-мерные подпространства ковариационной матрицы и только они.

Для этот результат лежит в основе метода главных компонентам, гл. 13). Нетрудно показать, что подмножество является собственным для матрицы тогда и только тогда, когда оно натянуто на какие-либо q главных компонент этой матрицы.

Если выборка X разбита на k классов (подвыборок) то определены:

— матрица внутриклассового рассеивания;

— матрица межклассового рассеивания. Отметим, что . Соответственно определены; внутриклассовый разброс: межклассовый разброс:

Пример 20.6. Пусть Рассмотрим проекционный индекс F (А) для статистики

где А — проекция из . Ясно, что F (А) является для всех О-инвариантным, а для даже -инвариантным, но не является -инвариантным, если Следовательно, F (А) можно использовать для поиска выразительных одномерных проекций и выразительных (-мерных ортогональных проекций из в R.

В каждом из случаев возникает оптимизационная задача на многообразии Грассмана для функции, которая в точке , где — ортонормированный базис, вычисляется по формуле

(20.38)

где матрица проекции, составленная из q векторов строк

Имеем:

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

Описанная выше итерационная процедура оптимизации на многообразии Грассмана , примененная к функции

позволяет отыскать такие выразительные проекции.

Рассмотрим методы оптимизации проекционных индексов на множестве всех проекций из

Пусть обозначает совокупность всех положительно определенных симметричных -матриц. Ставя в соответствие паре матриц , где , а (), матрицу получаем взаимнооднозначное соответствие между множеством всех таких пар

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

Пусть С — некоторая ортогональная -матрица. Тогда если проекции В соответствует пара , то, как легко видеть, проекции СВ соответствует пара (СМС', СА).

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

тогда и только тогда, когда для некоторой ортогональной матрицы

Считая координатами симметрической матрицы М ее матричные коэффициенты можно отождествить множество с соответствующим подмножеством в евклидовом пространстве

Условие положительной определенности матриц показывает, что это подмножество является открытой выпуклой областью в Следовательно, для вычисления градиента функции по М можно использовать обычные правила дифференцирования по матричным коэффициентам матрицы М. Вычисление градиента по А проводится по описанному выше правилу (см. формулу (20.33)).