Айвазян С.А., Бухшгабер В.М., Енюков И.С., Мешалкин Л.Д. - Прикладная статистика (1027378), страница 103
Текст из файла (страница 103)
Отождествляя, как обычно, пространство всех (р х д)-матриц А — — (а„, ! < 1 < р, 1 ( ! ~ о) с евклидовым пространством Я"», получаем, что М1.(р, о) является открытой областью в )с»», выделяемой условием де! !АА'!~ О, а МО (р, ч)— замкнутым подмногообразием в Р», выделяемым условием АА' = 1», т. е. у (о + 1)/2 уравнениями, связывающими ро координат (а,»). Например, МО (р, 1) =-(О Е Г»», !!О!( = 1) (одно уравнение связи на р координат); МО (р, 2) =-((0„0,) Р й»ХЯ»= К", (0,(=1, 10,1= =1, 0;0,=0)) (три уравнения связи на 2 р координат). Размерность многообразия МО (р, д) на 2 мень»(»+ !! ше, чем размерность объемлющего пространства К»».
Таким образом, применение обычных численных процедур для решения оптимизационных задач на многообразиях Мй (р, о) и МО (р, о) как подмножествах евклидова пространства К»» практически невозможно. Отметим, что попытка построить метод градиентного спуска на МО (р, о) была предпринята в! !21, 3 0.101.
Трудности, которые встретились на этом пути, типичны для реализации процедур условной оптимизации при большом числе уравнений связи на координаты. В !37 — 39) разработаны численные методы оптимизации функций на многообразии 6 (р, о). Оказалось, что если использовать внутреннюю геометрию этого многообразия, то эти методы реализуются при помощи аналогов основных алгоритмов безусловной оптимизации, 20.3.2.
Алгоритмы оптимизации функций иа многообразиях проекций. Пусть Ф (Е) — некоторая функция на многообразии 6 (р, д). Опишем сначала алгоритм решения задачи (20.31), реализующий аналог методов покоординатной оптимизации. Фиксируем в КР некоторый ортонормнрованный базис й» = (0,», ..., Ор») и обозначим через 1.» = 1. (Й) подпространство, натянутое на первые д векторов (О,, ..., ..., О»). Возьмем 1.» за начальную точку алгоритма оптимизации. Допустим, что уже построены 1.„..., 1., причем каждое 1. представляет собой д-мерное подпространство в Р', натянутое на первые д векторов ортонормированного базиса 11 = (О,, ..., 0„), т.
е. 1. = 1. (11 ). Опишем переход от (8, 1. ) к (8 .„, 1. +,). Выберем У, 1 < У ( д и у, 1 < у ~ р — д, введем семейство базисов »»' (У, у, а) = (011», (У, у), ..., Ор (к у)), где 9; (уу)=созаО» +з1паО~+;,„, О,+у (й у)= = — жп аО„„+ соз а0,„1,„, (20.32) О~ (1, у) ==-0~, если У ~ У или У+у, и получим семейство д-мерных плоскостей 1. (У, у; а), где 1, (У, у, а) натянуто на (О, (н у), ..., 0„(й у)). О п р е дел е н и е 20.3. Семейство д-мерных плоскостей 1. (0 у; а) ~ Р» называется (У, у)-координатной линией в 6 (д, р), проходящей через точку 1. = 1. (У, у; О) в локальной системе координат, задаваемой базисом й„.
Обоснование такого определения см. в (37), где описаны все необходимые факты о структуре многообразия 6 (р, д). Ограничив функцию Ф (1.) на семейство плоскостей Е (У, у; а) получаем обычную числовую функцию от а, а Е (О, 2 п). Положим Ф (1. (~', у; а)) = Фо (а). Используя одну из стандартных процедур оптимизации числовой функции Ф„(а), находим а,= агй гпах Фц(а) »еу».1»! и полагаем 8 +,— — В(У, у; а), 1. +,— — 1. (У, у'; а). Цикл процедуры оптимизации завершен. Используя описанный шаг алгоритма, можно реализовать методы покоординатной оптимизации.
Например, упорядочив множество пар (му),! < у < д, 1 < у ~ р — уи зациклив его, можно получить сколь угодно длинную последовательность пар (у, у) и соответствующую последовательность точек (.„Е„..., 1., 1 е„... Заметим, что по построению, Ф (1 ) < Ф М < ." < Ф (1. ) < Ф (1 +ч) < " 18» о Рц= — Фц(а)(о=о ои (20.33) где Фц(а)=Ф($.о(й $; а)). Градиент Р= (1 ц) удобно представлять в виде д х (р — д)- матрицы с вектор-столбцами у; = (у„), 1< $ < д. П р и м е р 20.4.
Пусть Х Е Гсо и Хь — его ортогональная проекция на некоторое д-мерное линейное подпространство $. с: К~. Рассмотрим на многообразии б (р, д) функцию Ф (1.) = $(ХьЦо и вычислим ее градиент в точке 1.о = = 1. (~о). Из (20.31) следует Ф ($. (й /; а)) = ~~', (91о Х)'+ (соз ай(о Х + з(п аО;ч-по Х)', 1=1 г~г (20.34) поэтому непосредственно из (20.33) получаем: Гц=2(9''оХ)(Ог'+гХ)=*29,"о(ХХ')9;,.я 1ч'$<д, 1<1< (20.35) Пусть А ($.о) — проекция из Гсо в $(о, задаваемая (рх д)- матрицей, строки которой 9;,, ..., 9'„и А ($.о~)— проекция из (со в Гсо-о, задаваемая (р х (р — 4)-матрицей со строками Оо'.ь, „, ..., 9' р,о Тогда из (20.35) следует, что градиент функции $(Хь((' в точке 1.„относительно базиса $$о можно записать в виде д Х (р — с))-матрицы Г = 1в, = 2А (1.о) ХХ' А ($.ог)'.
(20.36) Если функция Ф ($.) непрерывно зависит от $., то, используя компактность многообразия б (р, д), получаем, что Ф ($.) — ограниченная сверху функция и последовательность (Ф ($. )) сходится. Рассмотрим теперь дифференцируемую функцию Ф ($,) на б (р, 4. Опишем алгоритмы, реализующие методы градиентной оптимизации. Пусть, как и выше, 1.„= $. ($$о) с: )со, где йо = (Оиь ..., 9„„) — ортогональный базис в Йо и $.о (г', $; а) — (с, /) -я координатная линия в б (р, л), проходящая через $.о. О п р е дел е н н е 20.4. Градиентом функции Ф ($.) в точке $. относительно локальной системы координат, задаваемой базисом йо, называется д (р — е)-мерный вектор Г= (Гц, 1~ 1= д, 1((~р — о), вычисляемый по формуле При помощи функции |~Х»|(' легко показать, как зависит вид градиента Г = Г0 от выбора базиса й.
Пусть В» = (О,», ..., 9„„), и = 1, 2 — ортонормированные базисы в Яр. Заметим, что 1, (й!) = Е (8!) = Е„тогда и только тогда, когда существуютортогональная(!7:! 7)-матрица В, переводящая базис (вго ..., Оч!) в подпространстве 1., с: Я» в его базис (О,,, 9,), и ортогональная (р — су) х (р — !))-матрица В1, переводящая базис (9 ч„л..., 0»л ) в ортогональном дополнении Е,~- к 1., ~ Р' в его базис (9 .„, „ 0„,), Следовательно, если Е (В!) = Е (8») = Е„то Гв,=В'Гв,В . П р и м е р 20.5. Пусть Х!"! = (Х,, . „Х„) — выборка в )гр. Вычислим градиент функции Ф (Е) на многообразии Грассмана, соответствующей проекционному индексу Р (А) !» для статистики !р (у„..., у„) = — „у ~~у"! — )',~~*, где );— в=! средний вектор выборки У!"!.
Имеем Ф (1.) = — ~' 1(Х! — Х„)» Г.' 1 а,май !=! Используя формулу (20.33), получаем в точке Е„= Е (8„): л — ~~ 2А (1») (Х! — Х») (Х! — Х») ' А (Ц-)' = !=! = 2А ().а) Хх А (Е»!) ', А(1.»)?'х А(Ц)' =О нли в терминах базиса й»! В'Х 0! =О (2О.37) для всех 1 ~ ! < !7, 1:-1:~ р — д. Рассматривая (р Х р)-матрицу Хх как преобразование пространства й», получаем, что условие (20.37) выполняется тогда н только тогда, когда Хх переводит подпространство где ьх — ковариационная матрица выборки Х!"!.
Таким образом, условие экстремальности подпространства Е» за-, писывается в виде 1 в себя, т. е. когда 1.,— собственное подпространство ковариационной матрицы'. Как показано выше, ортогональная проекция А (1.») из )сл в )х!» является выразительной относительно г" (А) тогда и только тогда, когда 1.„ = Е (А) является экстремальной точкой функции Ф (1.). Таким образом, для проекционного индекса г'(А), пои строенного по статистике — ,'~ !!у! — у»)!з на !)-мерных выл борках, выразительными являются ортогональные проекции иа собственные (! -мерные подпространства ковариацнонной матрицы Хх и только они. Для д = ! этот результат лежит в основе метода главных компонент (см. гл. 13).
Нетрудно показать, что подмножество 1.» является собственным для матрицы Хх тогда и только тогда, когда оно натянуто на какие-либо д главных компонент этой матрицы. Если выборка Х разбита на А классов (подвыборок) Хз= Х (и!)=(Х,з, ..., Х,, !); 1=1, ..., й, то определены: %х = ~ и!Хх, — матрица внутриклассового рассеивания; з= ! Вх = Х я! (Х»! — Х»)(Х»! — Х»)' — матрица межклассоз=! ного рассеивания. Отметим, что %х + Вх = Хх. Соответственно определены: внутриклассовый разброс: З,х —— = Зр %х, межклассовый разброс: Змх = ЗРВх, Бах + + Зад=ах. П р и м е р 20.6.
Пусть Х = () Х!. Рассмотрим проек!=! ционный индекс г" (А) для статистики зр вг '!.) 7! где А — проекция из 1»л в 1»» и У! = АХ!. Ясно, что г" (А) является для всех д > 1 О-инвариантным, а для д = ! даже 6!.-инвариантным, но Р (А) не является И.-инвариантным, если д) 1. Следовательно, г" (А) можно использовать для поиска выразительных одномерных проекций и выразительных д-мерных ортогональных проекций из )тя в )»». В каждом из случаев возникает оптимизационная задача ' В терминах базиса тз» (р Х л)-матрнца А (!.!) называется собственная для матрицы лх, если существует (» Х »)-матряца С, такая, что А (Ь») Хх — — С А (1.») Прн» = 1втосоответствуетобычномуопределенню собственного вектора. ка многообразии Грассмана для функции, которая в точке 1.
= 3. (9), где 8 =- (О„..., 0») — ортонормироваиный базис, вычисляется по формуле Ф(Е) = Ф«х (Ь) ьР Ат«х А Фх(«.) ЗР АахА' (20.38) где А = А (Е) — матрица проекции, составленная из «) векторов строк 0„..., 0 „, Имеем: Фх(ь) Кг"«)ф х(") «Р хяг"«)«Рх(") ага«) Ф($.)— Фх(!) С л е д с т в и е 20.4. Для проекционного индекса Р (А), соответствующего отношению усредненного внутриклассового разброса к общему разбросу, наиболее выразительные ортогональные проекции задаются матрицами, составленными из собственных векторов симметрической матрицы %х — ТХх, где у = г" (А). Описанная выше итерационная процедура оптимизации на многообразии Грассмана 6 (р, д), примененная к функции Ф(А) = ЗР (А%х А') ЗР (Аах А ) позволяет отыскать такие выразительные проекции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
