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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

АНАНЬЕВСКАЯ Полина Валерьевна

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

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 б ПАП ^13 005059613

Санкт-Петербург - 2013

005059613

Работа выполнена на кафедре статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель: Официальные оппоненты:

Ведущая организация:

кандидат физико-математических наук, доцент Алексеева Нина Петровна, доктор физико-математических наук, профессор Егоров Владимир Алексеевич (Санкт-Петербургский государственный электротехнический университет "ЛЭТИ") доктор технических наук, доцент Буре Владимир Мансурович, (Санкт-Петербургский государственный университет, факультет ПМ-ПУ) Санкт-Петербургский государственный политехнический университет Защита состоится 19 июня 2013 г. в 16.00 часов на заседании диссертационного совета Д.212.232.50 по защите диссертаций на соискание ученой степени кандидата наук, на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 199034, Санкт-Петербург, В. О., Университетская наб., 7/9, Менделеевский Центр.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета, расположенной по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан « »__2013 г.

Ученый секретарь

диссертационного совета, КУРБАТОВА Г. И.

доктор физ.-мат. наук, профессор

Общая характеристика работы

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

Для анализа данных такого рода используются разнообразные методы, суть которых можно свести к трем основным направлениям: агрегирование информации в структуры меньшей размерности, выявление наиболее связных композиций, прогнозирование итоговой характеристики. Предназначенные для решения таких задач линейные многомерные статистические методы могут применяться в этом случае только после соответствующего преобразования категориальных данных в числовые или порядковые, представленного в работах (Сгеепасге, 1984) и (С1Ш, 1990).

Однако когда для шкалирования наблюдений используются более сложные логические формулы, более уместным оказывается привлечение алгебраических и комбинаторных методов, позволяющих преобразовывать категориальные данные на основе линейных комбинаций случайных величин над конечным полем в новые наборы признаков той же природы, но с более предпочтительными информационными свойствами. Подобные преобразования в работе (Сох, 1972) называются перестановочными трансформациями, но вводятся не линейно, а через систему логических отношений. В работе (В1оотйеЫ, 1974) намечается переход от перестановочных трансформаций к сложению двух бинарных признаков по модулю два, которое использует-

ся для расширения вариантов лог-линейных моделей. В работах (Алексеева 2004, 2007, 2008) посвященных исследованию комбинаторной структуры бинарных признаков на основе конечных геометрий, линейные оболочки над конечным полем используются для обеспечения так называемого симптомно-синдромального подхода к решению задач клинической диагностики. Широкий спектр приложений привел к необходимости развития и формализации такого подхода, заключающегося в использовании линейных преобразований исходных признаков над конечным полем и называемого далее конечно-линейным подходом.

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

Основные положения и результаты, выносимые на защиту. Формализованы и расширены на случай произвольной характеристики поля конечно-линейные статистические модели редукции размерности набора признаков, взаимодействия двух или более наборов и классификации. При помощи моделирования исследована сходимость по вероятности оценок параметров к теоретическим их значениям в данных моделях. Разработан и адаптирован для параллельных вычислений на GPU специальный метод дискретной оптимизации для оценки параметров конечно-линейных моделей, опирающийся на алгебраические свойства многообразий Грассмана. Метод реализован в системе программ, в том числе и на основе параллельных вычислений с использованием технологии CUDA. Для задачи классификации найдена оценка функции распределения количества ошибок классификации в случае независимых и равномерно распределенных исходных признаков.

Методы исследования. В работе применяются методы статистическо-

го моделирования, теории вероятностей, комбинаторики и линейной алгебры. Программирование осуществлялось в пакетах R и SAGE, а так же на языке программирования С++ с использованием технологии CUDA.

Научная новизна. Все основные результаты диссертации являются новыми.

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на семинаре кафедры статистического моделирования мате-матико механического факультета СПбГУ, а так же были представлены на конференциях: the 2nd International Conference on BioMedical Engineering and Informatics (BMEI'09), Tianjin, China, 17-19 October 2009; всероссийская научно-практическая конференция с международным участием «Алмазовские чтения 2011», ФЦСКЭ им. В. А. Алмазова, г. Санкт-Петербург, 19-21 мая 2011 г; V Международная научная конференция (заочная) «Системный анализ в медицине» (САМ 2011), г. Благовещенск, 25-26 мая 2011 г.

Публикации. По теме диссертации опубликованы статьи [1, 2] в журна-

лах по перечню ВАК и статьи [3-5] в сборниках трудов конференций. Статьи [2-5] написаны в соавторстве, в статье [4] автору принадлежит доказательство теоремы о базисных симптомах и импульсный алгоритм поиска оптимального синдрома второго порядка, в статьях [2, 3] — алгоритм дискретной оптимизации и его реализации для исследования связности цепочек РНК и выделения прогностических факторов у больных с глиомами, в статье [5] — раздел о информационном структурировании категориальных данных.

Структура и объем диссертации. Диссертация состоит из введения, 7 глав, заключения и библиографии. Общий объем диссертации 142 страницы, из них 128 страниц текста, включая 19 рисунков. Библиография включает 98 наименований на 11 страницах.

Содержание работы

Рассматривается конечное полеЕ9 и дискретная сигма-алгебра 2?", состоящая из всевозможных подмножеств Через X = ..., Хт)т обозначен случайный вектор, состоящий из тп случайных компонент, представляющих собой дискретные случайные величины со значениями в 2Г«), заданные на некотором вероятностном пространстве (О,Т,Р). В приложениях наблюдаемые реализации вектора X, состоящие из реализаций его одномерных компонент Х{, называются набором категориальных признаков, каждый из которых принимает значения в поле

Линейная комбинация Хт = 04Х1+.. .+атХт, где а, — элементы поля а операции сложения и умножения производятся в поле также является случайной величиной со значениями в (¥1], 25Г').

Любое линейное преобразование случайного вектора X в новый случайный вектор X = (Хп,ХТ2,..., ХТк)т, состоящий из к новых случайных компонент со значениями также в 2^), может быть задано состоящей из

элементов поля F, матрицей А = {ац}. где 1 < г < /г и 1 < j < т. Каждая компонента вектора X = АХ задается равенством ХТ. — ацХ\ + ... + aimXm.

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

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

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

Снижение размерности вектора X сводится к задаче поиска матрицы параметров А = А(к,т), при заданных к < т, чтобы различие между распределениями исходного вектора X = (Xi,..., Xm)T и вектора X = АХ было

минимальным. В качестве меры различия предлагается применять разность энтропий Шеннона (Shennon, 1948) Н(Х) и Н(АХ), при этом задача снижения размерности заключается в поиске хотя бы одной матрицы А = А(к,т), к < т, при которой достигается минимум следующей функции:

а{А) = Н(Х) - Н{АХ). (1)

Выбор такой функции обусловлен широко используемым в работах (Akaike, 1973), (Burg, 1975), (Berger, 1996) принципом максимума энтропии. Принцип заключается в выборе такого распределения для описания эксперимента, которое удовлетворяет заданным ограничениям и имеет максимальную энтропию среди всех распределений, удовлетворяющих таким же ограничениям.

Модель канонической сцепленности предназначена для выявления к зависимостей между векторами X и У с mi и случайными компонентами соответственно. В качестве меры зависимости X и У предлагается использовать односторонний и двусторонний коэффициенты неопределенности Тейла (Theil, 1970)

ЫХМ-'Ш и ВДЭ0 = 2.

Н{У) 4 "" Н(Х) + Н(У)

как нормальзованные версии совместной информации 1(Х,У) = Н(Х) + Н(У) — Н(Х,У). Здесь через Н(Х,У) обозначена энтропия распределения вектора (Х\,..., Хтл, Ух,..., Утг)- Оптимизационная задача состоит в поиске хотя бы одной пары матриц преобразований тп\) = ..., А^)т

для X и )т для у, максимизирующих функции

ай1', л«2»)=Я((А«)г*, (42>т 1=1,..., к. (2)

при ограничениях на значения энтропии Н((А^\ ..., А\^)ТХ) > Нц • Н(Х) и Н((А^\..., А^)ТУ) > Нц • Н(Х), где Нц и Ь^ - управляющие параметры. Кроме того предлагается вариант обобщения этого подхода на случай I случайных векторов Х^ = ..., в = 1,..., /.

Задача жестко-симметрической классификации заключается в предсказании случайной величины У по случайному вектору X = (Хх,..., Хт)Т на основе его линейного преобразования АХ при помощи матрицы параметров А размера 1 х тп так, чтобы отличие между и АХ было минимально. В качестве меры отличия в данном случае используется вероятность несовпадения двух случайных величин АХ и^с учетом перенумерации

Р1(АХ,У)=тт(1-Р(АХ = /(У))\ (3)

где минимизация производится по всем возможным биекциям /: —> осуществляющим перенумерации множества значений У- Оптимизационная задача заключается в поиске хотя бы одной точки минимума функции на множестве матриц А = А( 1, т)

а(А) = Р1(АХ,У). (4)

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

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

Рассмотрим пространство Ут = (Р9)т с базисом, состоящим из т линейно независимых над полем F1J векторов Х\,..., Хт. Любой набор линейно независимых векторов (Хп,..., ХТк) является базисом к-мерного подпространства линейных комбинаций \¥к = (Хп,..., ХТк) пространства У,п. Каж-

дый вектор XTi раскладывается по базису Xi,... ,Хт

Хп = ааХг + ... + aimXm, (5)

где a,ij — элементы поля Fg.

Грассманианом называется множество всех /с-мсрггых подпространств Wk пространства Vm. Нами решается задача о быстром перечислении всех Wk (точек грассманиана), для чего используется векторная параметризация грассманиана, которая представляет собой универсальный способ выделения базисов (ХТ1, ХТ2,... ,ХТк) всех Wk, таким образом, что никакие два базиса не задают одно и то же подпространство. Эта параметризация описывается в следующей доказанной диссертантом теореме. Зафиксируем полный флаг Т на пространстве Vm = (¥g)m,

V0 = {0} С V! = (Хг) с V2 = (Хг, Х2) с ... С Vm = {Хи..., Хт).

Отношение линейного порядка -< на Vm согласовано с флагом J7, если для всех г = 0,1,..., тп и v € Vi, w € Vm \ Ц имеет место v < w.

Теорема 1. Отображение {Хп, ХТ2,..., ХТк) i—> (Хп, ХТ2,..., Хп) устанавливает биекцию между к-мерными подпространствами Wk при фиксированном Т и наборами векторов ХТ], ХТ2,..., ХТк (z Vm такими, что

1. для Хп = ацХх + ... + а{тХт при Si <т имеет место

(а, 1,..., aim) = (ail, • • •, aist, 1,0,..., 0)

2. Хп -< XTj при г < j,

3. для всех Хп и XTj, г < j, выполнено a,j(Sj+1) = 0.

Теорема 1 доказывается для случая q = 2 во втором параграфе, причем доказательство основано на свойствах флагов. Общий случай рассматривается при помощи классического клеточного разложение в третьем параграфе.

В третьей главе показывается, как задачи поиска матриц преобразований А в конечно-линейных моделях сводятся к задачам оптимизации функций (1),(2),(4) на множестве подпространств Wk С Vm над Fg. Для решения задач такого рода существуют методы полного перебора, релаксации (Calvet, 2003), рекурсивный метод ветвей и границ (Land, Doig, I960) и другие (Raghavan, Thompson, 1987). Зачастую наиболее эффективными оказываются методы, основанные на специфических особенностях рассматриваемых функций и объектов. В данном случае предлагается алгоритм оптимизации основанный на векторной параметризация грассманиана.

В первом параграфе на предмет согласованности с флагом исследованы три отношения линейного порядка: лексикографический, степенно-лексикографический (импульсный) и обобщенный порядок Грея (Guan, 1998). Упорядочивание XTi 6 Vm согласно обобщенному порядку Грея осуществляется путем упорядочивания наборов коэффициентов (an,..., aim) в разложении (5) так, что каждый следующий набор (an,..., а*т) отличается от предыдущего (а'а,..., a'im) прибавлением 1 по модулю q ровно к одному а!ц.

Теорема 2. Лексикографический порядок и обобщенный порядок Грея согласованы с флагом Т на пространстве Vm = (Fg)m, а степенно-лексикографический порядок согласован только при т = 1 и при т = 2, q = 2.

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

Во втором параграфе на основе теоремы 1 построен алгоритм быстрого перечисления точек грассманиана FGEA (Fast Grassmannian Enumeration

Algorithm). В соответствии с этим алгоритмом, в четвертом параграфе рассмотрены два подхода к задаче дискретной оптимизации некоторой функции fx, заданной на множестве подпространств пространства Vm: поиск оптимального Wk путем последовательного перебора всех W¡¡, пошаговый перебор к базисных векторов Хп. где на ¿-том шаге максимизируется (минимизируется) функция n(Wi), i < к. Особым требованием к ц при пошаговом переборе является свойство ее монотонного возрастания (или убывания) на множестве вссх Wk, состоящее в том, что для любых Ws С Wt С Vm имеет место H(IVS) < niy/t) (соответственно n{Wt) < ^(iys)).

Теорема 4. В случае пошагового перебора алгоритм FGEA (S-FGEA) эффективнее метода полного перебора наборов (Хп,ХТ2,... ,Хп) более чем в qk раз, а в случае последовательного перебора (F-FGEA) более, чем eqk раз.

В пятом параграфе описывается применение F-FGEA к задаче снижения размерности и задаче классификации, а так же применение S-FGEA к задаче поиска структурной зависимости. В обоих случаях применение основывается на взаимно однозначном соответствии между наборами векторов (ХТ1, ХТ2,..., Хп) и матрицами коэффициентов А, а также на инвариантности энтропии относительно обратимых линейных преобразований и монотонном возрастании при конкатенации случайных векторов.

В четвертой главе алгоритм FGEA в случае поля F2 адаптируется к параллельным вычислениям на графических процессорах Nvidia поколения Fermi с использованием технологии CUDA. В первом параграфе приводится описание особенностей архитектуры таких графических процессоров, отражающихся в методах работы с потоковой структурой и различными видами памяти. Во втором параграфе показано, каким образом реализуется алгоритм FGEA на CUDA с использованием минимального количества памяти, которое достигается за счет свойства порядка Грея из теоремы 3. Третий параграф

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

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

В случае независимых Х1 для А проверяется, что для V е > 0 имеет место Р(\рп ~ 1| > г) —гдерп обозначает вероятность совпадения матриц Л и А

п-юо

для заданного объема выборки п. Для этого моделируется 100 значений оценки рп, вычисляемых в свою очередь по 100 испытаниям и демонстрируется сходимость Ерп —>■ 1 и Е (рп — I)2 —> 0.

П—ЮО П-¥0О

Для независимых Х{ были получены следующие результаты. Скорость сходимости инвариантна относительного линейного обратимого преобразования вектора X над полем но зависит от распределения информационной нагрузки между компонентами X¿. При этом самая высокая скорость сходимости наблюдается в случае матрицы А размера к х т, где к совпадает с количеством 5 компонент Х{, распределение которых вносит основной вклад в общую энтропию. С увеличением т при фиксированном з < т наблюдается падение скорости сходимости. Представление о характере распределения информационной нагрузки можно получить по профилю энтропии, представляющего собой график значений энтропии всевозможных подпространств.

В случае зависимых Х{ теоретическое вычисление А, а следовательно, и моделирование рп, требует явного задания вида зависимости. Перебор всех видов зависимости не представляется возможным. В данном случае при помощи моделирования можно проверить лишь факт существования такой матрицы А, что Р(А = а^тах Н(АХ)) —> 1 и Р(Л,- = а^тах Н(АХ)) —> 0

д п—>оо ^ п—юо

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

Второй параграф посвящен вопросу сходимости по вероятности в задаче классификации. Помимо естественного уменьшения скорости сходимости при увеличении количества компонент т выявлена проблема неоправданно малого количества ошибок классификации при малом объеме выборки п и А ф А. Этот факт обусловлен возрастанием числа вариантов АХ при увеличении т, которое в крайнем случае может покрыть все множество возможных Y.

В общем случае решение проблемы соотношения тип является сложной задачей, однако для случая одинаково распределенных и независимых компонент Хг в рамках ее решения в шестой главе при заданных Y, п, т, q вычисляется оценка функции распределения Fn{t) = P(i] < t) случайной величины г), характеризующей количество ошибок классификации, где т] = р2(Х, Y) = min pi(XT, Y). Здесь С(Х) обозначает линейную оболочку множества столбцов матрицы X = Х(п, т), а Y - итоговый вектор длины п, координаты которого принимают I < q различных значений над F, и задают разбиение п элементов на / классов. Расстояние pi между векторами ХТ и Y определяется по аналогии с (3) pi{XT, Y) = min ро(Хт, Y*), где ро(Хт, Y*) вычисляется как минимальное количество замен, необходимое для получения вектора Хт из вектора Y*. В обозначении ¥ — множество всех векторов Y* € Y, задающих то же разбиение (Y € Y). Вектора Y, Y' € F™ задают одинаковое разбиение тг элементов на I классов, если оба вектора состоят ровно из I различных элементов поля F9 и выполнено f>i{Y, Y') = 0. Для оценивания Fv(t) диссертантом доказаны следующие теоремы.

Теорема 5. Количество матриц X = Х(п,т) (ifK) над F9 таких, что хотя бы один вектор, задающий такое же разбиепиеп элементов на I классов,

что и Y, инцидентен С(Х) = (Х\,... ,Хт), вычисляется по формуле:

m /г-1 \ min(i,r)

m /г-1 \ min(i,r)

r=0 \t=0 / fc=max(0,i+r-n,r-m+l)

(l-k)(r-k) (П->

I у* _ y^J .

fc=max(0,/+r—rc,r—m+1) 4 ' 3

(6)

где Qg = 1, ¿,(1,0) = l> AM) = 0 при l > l, Aq(l,l) = 1,

Л?(г, fc) = Aq(i -1, fc -1) + Л9(/ -1, к) ■ (qk -1 +1),

'A

Обозначим элементы поля F9 числами {1,2,..., g}. Пусть координаты вектора Y принимают ровно г < q значений и Ь{К) = ^ | j/fc = О-

i&K

Теорема 6. Количество R'ЬТ векторов Y таких, что они отличаются от

вектора Y = (?/ъ 2/2, • • •, Уп) ровно в Ь координатах, вычисляется по формуле: \Щ

Rr= Е В"1)' Е (7)

KCl q i=0 K'cK

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

= (8) г=1 4 j=О

где t € Z+, а #Х вычисляется по формуле (б), а по формуле (7). Теоретическая оценка из формулы (8) хорошо согласуется при

P(j] <

t) < 0.1 с эмпирической оценкой функции распределения Fn(t), полученной при помощи моделирования. Использование этого результата возможно в практических приложениях для проверки адекватности применения конечно-линейного метода классификации, хотя строгая формализация критерия требует отдельного исследования. Рассматриваемые конечно-линейные

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

диссертационного исследования и формулируются основные результаты.

Список публикаций автора

1. Ананьевская (Грачева) П. В. Метод дискретной оптимизации на основе параметризации грассманиана в многомерном структурировании дихотомических данных // Вестн. С.-Петерб. ун-та. Сер. 1: Математика, Механика, Астрономия. 2011. Вып. 4. С. 28-37.

2. Мартынов Б. В., Алексеева Н. П., Ананьевская (Грачева) П. В. и др. Прогностические факторы у больных с глиомами: симп-томно-синдромальный анализ // Вестн. Рос. Воен.-мед. акад. 2010. Т. 1, № 29. С. 7-14.

3. Alexeyeva N., Alexeyev A., Ananyevskaya (Gracheva) P. et al. Symptom and syndrom analysis of categorial series, logical principles and forms of logic // Proc. of the 3nd International Conference on BioMedical Engineering and Informatics (BMEI). 2010. P. 2603-2606.

4. Alexeyeva N., Smirnov I., Ananyevskaya (Gracheva) P., Martynov B. The finitely geometric symptom analysis in the glioma survival study // Proc. of the 2nd International Conference on BioMedical Engineering and Informatics (BMEI). 2009. P. 1-4.

5. Алексеева H. П., Ананьевская (Грачева) П. В., Подхалюзина Е. М. Структурирование и систематизация факторов на основе конечных проективных подпространств. // Материалы V международной конференции «Системный анализ в медицине» (САМ), Благовещенск. 2011. С. 14-16.

Подписано в печать 17.04.13 Формат 60x84Vi6 Цифровая Печ. л. 1.0 Тираж 100 Заказ 09/04 печать

Отпечатано в типографии «Фалкон Принт» (197101, г. Санкт-Петербург, ул. Большая Пушкарская, д. 54, офис 2)

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ 04201358145 На правах рукописи

АНАНЬЕВСКАЯ Полина Валерьевна

Исследование конечно-линейных статистических моделей. Оптимизация и

избыточность

05.13.18 - Математическое моделирование, численные методы и комплексы

программ

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель кандидат физ.-мат. наук, доцент Алексеева Нина Петровна

Санкт-Петербург - 2013

Содержание

Глава 1. Конечно-линейные статистические модели.......13

1.1. Обзор классических подходов к многомерному анализу категориальных данных..........................14

1.1.1. Оптимальное шкалирование................15

1.1.2. Анализ главных компонент................16

1.1.3. Канонический корреляционный анализ..........18

1.1.4. Классификация.......................19

1.2. Конечно-линейный подход.....................23

1.2.1. Редукция размерности...................24

1.2.2. Каноническая сцепленность или структурная зависимость .............................26

1.2.3. Жестко-симметрическая классификация.........27

Глава 2. Векторная параметризация многообразия Грассмана 30

2.1. Грассманиан и теорема о векторной параметризации......31

2.2. Уровневый подход к доказательству теоремы в случае поля ¥2 33

2.3. Обобщение доказательства на случай поля ¥д..........37

Глава 3. Алгоритм дискретной оптимизации...........41

3.1. Отношение линейного порядка...................42

3.2. Алгоритм быстрого перечисления точек грассманиана РвЕА . 46

3.3. Монотонные характеристики....................50

3.4. Дискретная оптимизация......................53

3.4.1. Пошаговый и последовательный подходы........53

3.4.2. Оценка эффективности...................54

3.5. Дискретная оптимизация в конечно-линейных моделях.....55

3.5.1. Редукция размерности...................56

3.5.2. Структурная зависимость.................57

3.5.3. Жестко-симметрическая классификация.........59

Глава 4. Детализация алгоритма дискретной оптимизации для параллельной архитектуры CUDA.................61

4.1. Особенности устройства GPU ...................62

4.1.1. Потоковая структура....................63

4.1.2. Виды памяти........................64

4.2. Представление алгоритма дискретной оптимизации в удобном

для параллельных вычислений виде................66

4.3. Быстрый способ вычисления энтропии..............71

4.4. Оценка эффективности на модельных выборках.........72

Глава 5. Моделирование ........................76

5.1. Исследование ассимптотических свойств оценки параметра в модели редукции размерности...................77

5.1.1. Сходимость в случае независимых исходных признаков 77

5.1.2. Сходимость в случае зависимых исходных признаков . 86

5.2. Исследование ассимптотических свойств оценки параметра в модели классификации.......................89

5.2.1. Сходимость в случае независимых исходных признаков 90

5.2.2. Сходимость в случае зависимых исходных признаков . 92

Глава 6. Исследование избыточности классификационной модели .....................................95

6.1. Пространство классификаций...................96

6.2. Теорема об инцидентности векторов случайному векторному

пространству ............................. 102

6.3. Оценка избыточности........................107

6.4. Исследование качества оценки на модельных данных......110

Глава 7. Анализ реальных данных..................114

7.1. Редукция размерности .......................114

7.2. Структурная зависимость .....................118

7.3. Классификация...........................124

Заключение..................................130

Литература..................................132

Введение

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

Для анализа данных такого рода используются разнообразные методы, суть которых можно свести к трем основным направлениям: агрегирование информации в структуры меньшей размерности, выявление наиболее связных композиций, прогнозирование итоговой характеристики. Предназначенные для решения таких задач линейные многомерные статистические методы могут применяться в этом случае только после соответствующего преобразования категориальных данных в числовые или порядковые [1, 2].

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

Подобные преобразования в работе Кокса [3] называются перестановочными трансформациями, но вводятся не линейно, а через систему логических отношений. В работе Блумфильда [4] намечается переход от перестановочных трансформаций к сложению двух бинарных признаков по модулю два, которое используется для расширения вариантов лог-линейных моделей.

с

В работах Алексеевой [5-7], посвященных исследованию комбинаторной структуры бинарных признаков на основе конечных геометрий, линейные оболочки над конечным полем используются для обеспечения симптомно-синдро-мального подхода к решению задач клинической диагностики.

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

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

Методы исследования. В работе применяются методы статистического моделирования, теории вероятностей, комбинаторики и линейной алгебры (алгебраические поля и многообразия Грассмана). Программирование осуществлялось в статистическом пакете R, пакете SAGE, а так же на языке программирования С++ с использованием технологии параллельных вычислений CUDA.

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

модели классификации найдена оценка функции распределения количества ошибок классификации в случае независимых, равномерно распределенных исходных признаков.

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на семинаре кафедры статистического моделирования мате-матико-механического факультета СПбГУ, а так же были представлены на конференциях: the 2nd International Conference on BioMedical Engineering and Informatics (BMEI'09), Tianjin, China, 17-19 October 2009; всероссийская научно-практическая конференция с международным участием «Алмазовские чтения 2011», ФЦСКЭ им. В. А. Алмазова, г. Санкт-Петербург, 19-21 мая 2011 г; V Международная научная конференция (заочная) «Системный анализ в медицине» (САМ 2011), г. Благовещенск, 25-26 мая 2011 г.

Публикации. По теме диссертации опубликованы статьи [8, 9] в журналах по перечню ВАК и статьи [10-12] в сборниках трудов конференций. Статьи [9-12] написаны в соавторстве, в статье [11] автору принадлежит до-

казательство теоремы о базисных симптомах и импульсный алгоритм поиска оптимального синдрома второго порядка, в статьях [9, 10] — алгоритм дискретной оптимизации и его реализации для исследования связности цепочек РНК и выделения прогностических факторов у больных с глиомами, в статье [12] — раздел о информационном структурировании категориальных данных.

Структура и объем диссертации. Диссертация состоит из введения, 7 глав, заключения и библиографии. Общий объем диссертации 142 страниц, из них 127 страниц текста, включая 19 рисунков. Библиография включает 98 наименований на 11 страницах.

В первой главе производится формализация конечно-линейных статистических моделей, в рамках которых ставятся специальные задачи дискретной оптимизации. Первый параграф посвящен обзору существующих вариантов построения аналогов трех многомерных статистических методов (анализ главных компонент [13, 14], канонический корреляционный анализ [15, 16] и методов классификации [17-19]) как задач дискретной оптимизации.

Вопросу многомерного анализа категориальных данных уделяется большое внимание в статистической литературе. Основным подходом, которому посвящено множество работ, является преобразование исходного набора категориальных данных в набор новых числовых признаков, называемом оптимальным шкалированием. Впервые предложенная Фишером в работе [20] идея такого преобразования в дальнейшем получила различные направления развития: множественный анализ соответствий, являющийся обобщением простого анализа соответствий [1, 21] и анализ однородности или гомогенности [2, 22]. Именно эти направления представлены в первом разделе первой главы как задачи оптимизации различных функций.

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

к новому вектору с компонентами той же природы. История такого подхода начинается с работ Кокса и Блумфильда [3, 4], в которых было предложено исследовать линейные преобразования по модулю два как способ упрощения описания исходного набора признаков с двумя градациями. После длительного перерыва этот подход вновь привлек внимание статистиков. Наиболее детальное его описание для случая двух градаций исходных признаков было предложено Алексеевой в работах по симптомпо-синдромальному анализу [5-7], исследующему комбинаторную структуры комплексов факторов. Параллельно симптомно-синдромальному анализу в рамках этого подхода также развивается направление восстановления исходных независимых компонент по их наблюдаемым линейным комбинациям над конечными полями в работах Гутча и Ередора [23, 24].

Во втором разделе первой главы предлагается формализация метода исследования комбинаторной структуры комплексов факторов, заявленного Алексеевой, на основе конечно-линейных статистических моделей для трех рассматриваемых многомерных статистических методов (многомерного структурирования, структурной зависимости и задачи жестко-симметрической классификации). Параметром в каждой из этих моделей является матрица заданной размерности над конечным полем, задающая линейное преобразование исходного вектора, удовлетворяющее некоторому критерию оптимальности. Критериями оптимальности матрицы преобразования в этих задачах являются следующие условия: условие максимума энтропии преобразованного исходного вектора, удовлетворяющее одному из основных статистических принципов — принципу максимума энтропии [25-27], условие максимума коэффициента неопределенности между двумя преобразованными исходными векторами как одной из наиболее известных мер независимости категориальных признаков [28-30] и условие минимума вероятности несовпадения заданной итоговой случайной величины и линейного преобразования исходного век-

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

В то время как направления, основанные на оптимальном шкалировании, для поиска решения оптимизационных задач используют известные алгоритмы сингулярного разложения, метод наименьших квадратов (IRLS) [31], модифицированный векторный метод подгонки (modified vector backfitting algorithm) [32] и крисс-кросс (criss-cross) метод [33], общей проблемой конечно-линейных моделей является необходимость построения эффективного алгоритма дискретной оптимизации.

Во второй главе предлагается векторная параметризация многообразия Грассмана (грассманиана) над конечным полем, на основе которой в последующих главах строится необходимый алгоритм дискретной оптимизации. Векторные параметризации грассманиана на основе использования диаграмм Ферре и расширенных базисных матриц представлены в работе [34]. Применение этих подходов не представляется возможным, поскольку построение каждого следующего подпространства (точки грассманиана) сопряжено с большими вычислительными сложностями. Предлагаемая во второй главе векторная параметризация является модификацией классического клеточного разложения, и позволяет решить задачу быстрого перечисления точек многообразия Грассмана. В теории алгебраических групп обобщение того факта, что грассманнианы имеют клеточную структуру, известно под названием "разложение Брюа"[35], а с точки зрения линейной алгебры клеточное разложение следует из алгоритма Гаусса и существования приведенного ступенчатого вида по строкам [36], но эти подходы являются чисто теоретическими и не дают эффективного способа компьютерного перечисления точек грассманиана.

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

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

Преимуществом предложенного алгоритма дискретной оптимизации является его адаптивность к параллельным вычислениям. Эффективным способом параллельных вычислений является использование графических процессоров (видеокарт), как сопроцессоров, обладающих собственной памятью и обрабатывающих параллельно большое количество потоков [41-43]. В связи с тем, что в последние годы при помощи вычислительных возможностей графических процессоров реализуются многие статистические подходы [44-49], в четвертой главе рассматривается детализация алгоритма дискретной оптимизации для параллельной архитектуры CUDA для видеокарт Nvidia поколения Fermi, включающая возможность быстрого вычисления энтропии без составления гистограммы.

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

Практическое применение рассматриваемых конечно-линейных моделей

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

у

Глава 1

Конечно-линейные статистические модели

Наиболее распространенный подход к построению аналогов многомерных методов для категориальных данных, реали