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

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

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

Исследование конечно-линейных

статистических моделей. Оптимизация и

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

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

программ

АВТОРЕФЕРАТ

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

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

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

Официальные оппоненты: доктор физико-математических наук, профессор Егоров Владимир Алексеевич (Санкт-Петербургский государственный электротехнический университет “ЛЭТИ”) доктор технических наук, доцент Буре Владимир Мансурович, (Санкт-Петербургский государственный университет, факультет ПМ-ПУ)

Ведущая организация: Санкт-Петербургский государственный по­ литехнический университет

Защита состоится 19 июня 2013 г. в 16.00 часов на заседании диссертационно­ Д.212.232. го совета по защите диссертаций на соискание ученой степени кандидата наук, на соискание ученой степени доктора наук при Санкт-Петер­ бургском государственном университете по адресу: 198504, г. Санкт-Петер­ бург, Петродворец, Ульяновская ул., д.1, НИИФ, аудитория 116.

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

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

Ученый секретарь КУРБАТОВА Г. И.

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

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

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

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

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

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

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

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

Программирование осуществлялось в пакетах R и SAGE, a так же на языке программирования С++ с использованием технологии 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] — раздел о информационном структурировании категориальных данных.

128 страниц текста, включая 19 рисунков. Библиография включа­ цы, из них Содержание работы Рассматривается конечное поле случайный вектор, состоящий из случайных компонент, представляющих собой дискретные случайные величины со значениями в мые реализации вектора, называются набором категориальных признаков, каждый из которых нент Линейная комбинация случайной величиной со значениями в компонента вектора задается равенством Одной из главных задач диссертации является построение конечно–линей­ ных статистических моделей как аналогов методов анализа главных компо­ нент, канонического корреляционного анализа и регрессии. Параметром в дающая линейное преобразование исходного вектора, удовлетворяющее неко­ торому критерию оптимальности.

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

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

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

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

вать односторонний и двусторонний коэффициенты неопределенности Тейла (Theil, 1970) как нормальзованные версии совместной информации вектора хотя бы одной пары матриц преобразований при ограничениях на значения энтропии ры. Кроме того предлагается вариант обобщения этого подхода на случай случайных векторов сказании случайной величины по случайному вектору В качестве меры отличия в данном случае используется вероятность несов­ где минимизация производится по всем возможным биекциям задача заключается в поиске хотя бы одной точки минимума функции на множестве матриц достигается глобальный экстремум, может быть не единствена. Это означа­ ет существование различных способов снижения размерности или несколько видов взаимосвязей или способов классификации. В таких задачах интерес представляет нахождение хотя бы одного решения на основе эмпирического распределения при помощи построенного в последу­ ющих главах специального алгоритма дискретной оптимизации.

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

странства линейных комбинаций (точек грассманиана), для чего используется векторная параметризация грассманиана, которая представляет собой универсальный способ выделения не задают одно и то же подпространство. Эта параметризация описывается в следующей доказанной диссертантом теореме. Зафиксируем полный флаг на пространстве Теорема 1. Отображение (1, 2,..., ) 1, 2,..., уста­ навливает биекцию между -мерными подпространствами при фикси­ рованном и наборами векторов 1, 2,..., такими, что доказательство основано на свойствах флагов. Общий случай рассматривает­ ся при помощи классического клеточного разложение в третьем параграфе.

зований в конечно–линейных моделях сводятся к задачам оптимизации шения задач такого рода существуют методы полного перебора, релаксации (Calvet, 2003), рекурсивный метод ветвей и границ (Land, Doig, 1960) и дру­ гие (Raghavan, Thompson, 1987). Зачастую наиболее эффективными оказыва­ ются методы, основанные на специфических особенностях рассматриваемых функций и объектов. В данном случае предлагается алгоритм оптимизации основанный на векторной параметризация грассманиана.

В первом параграфе на предмет согласованности с флагом исследованы три отношения линейного порядка: лексикографический, степенно–лексико­ графический (импульсный) и обобщенный порядок Грея (Guan, 1998). Упо­ Теорема 2. Лексикографический порядок и обобщенный порядок Грея согла­ сованы с флагом на пространстве = (F ), а степенно–лексикографи­ ческий порядок согласован только при = 1 и при = 2, = 2.

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

Во втором параграфе на основе теоремы 1 построен алгоритм быстро­ го перечисления точек грассманиана FGEA (Fast Grassmannian Enumeration Algorithm). В соответствии с этим алгоритмом, в четвертом параграфе рас­ смотрены два подхода к задаче дискретной оптимизации некоторой функции, заданной на множестве подпространств пространства : поиск оптималь­ ре является cвойство ее монотонного возрастания (или убывания) на множе­ Теорема 4. В случае пошагового перебора алгоритм FGEA (S-FGEA) эф­ фективнее метода полного перебора наборов (1, 2,..., ) более чем в раз, а в случае последовательного перебора (F-FGEA) более, чем в раз.

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

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

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

В случае независимых (| 1| > ) 0, где обозначает вероятность совпадения матриц и для заданного объема выборки сходимости инвариантна относительного линейного обратимого преобразова­ ся падение скорости сходимости. Представление о характере распределения информационной нагрузки можно получить по профилю энтропии, представ­ ляющего собой график значений энтропии всевозможных подпространств.

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

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

которое в крайнем случае может покрыть все множество возможных ной задачей, однако для случая одинаково распределенных и независимых ной величины характеризующей количество ошибок классификации, где = 2 (, ) = min 1 (, ). Здесь () обозначает линейную оболочку вычисляется как минимальное количество замен, необходимое для получе­ различных элементов поля F и выполнено 1 (, ) = 0. Для оценивания () диссертантом доказаны следующие теоремы.

Теорема 5. Количество матриц = (, ) (#X) над F таких, что хо­ тя бы один вектор, задающий такое же разбиение элементов на классов, что и, инцидентен () = 1,...,, вычисляется по формуле:

Теорема 6. Количество векторов таких, что они отличаются от вектора = (1, 2,..., ) ровно в координатах, вычисляется по формуле:

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

Теоретическая оценка из формулы (8) хорошо согласуется при ной при помощи моделирования. Использование этого результата возмож­ но в практических приложениях для проверки адекватности применения ко­ нечно–линейного метода классификации, хотя строгая формализация крите­ рия требует отдельного исследования. Рассматриваемые конечно–линейные модели были успешно применены при обработке реальных медицинских дан­ диссертационного исследования и формулируются основные результаты.

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

Математика, Механика, Астрономия. 2011. Вып. 4. С. 28–37.

Мартынов Б. В., Алексеева Н. П., Ананьевская (Грачева) П. В.

и др. Прогностические факторы у больных с глиомами: симп­ томно-синдромальный анализ // Вестн. Рос. Воен.-мед. акад. 2010.

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 In­ formatics (BMEI). 2010. P. 2603–2606.

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

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