Выпуклые критерии и параллелизуемые алгоритмы селективного комбинирования разнородных представлений объектов в задачах восстановления зависимостей по эмпирическим данным

Разин, Николай Алексеевич

Теоретические основы информатики

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

кандидата физико-математических наук: Разин, Николай Алексеевич
город: Москва
год: 2013
специальность ВАК РФ: 05.13.17

Диссертация по информатике, вычислительной технике и управлению на тему «Выпуклые критерии и параллелизуемые алгоритмы селективного комбинирования разнородных представлений объектов в задачах восстановления зависимостей по эмпирическим данным»

Автореферат диссертации по теме "Выпуклые критерии и параллелизуемые алгоритмы селективного комбинирования разнородных представлений объектов в задачах восстановления зависимостей по эмпирическим данным"

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

Разин Николай Алексеевич

ВЫПУКЛЫЕ КРИТЕРИИ И ПАРАЛЛЕЛИЗУЕМЫЕ АЛГОРИТМЫ СЕЛЕКТИВНОГО КОМБИНИРОВАНИЯ

РАЗНОРОДНЫХ ПРЕДСТАВЛЕНИЙ ОБЪЕКТОВ В ЗАДАЧАХ ВОССТАНОВЛЕНИЯ ЗАВИСИМОСТЕЙ ПО ЭМПИРИЧЕСКИМ ДАННЫМ

Специальность 05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ 2 8

диссертации на соискание учёной степени кандидата физико-математических наук

Москва-2013

005540185

Работа выполнена на кафедре «Интеллектуальные системы» факультета управления и прикладной математики Федерального государственного автономного образовательного учреждения высшего профессионального образования «Московский физико-технический институт (государственный университет)».

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

Моттль Вадим Вячеславович.

Официальные оппоненты: доктор физико-математических наук, доцент

Устинин Михаил Николаевич. Место работы: Федеральное государственное бюджетное учреждение науки Институт математических проблем биологии РАН, заместитель директора по научной работе.

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

Ведущая организация: Федеральное государственное бюджетное учре-

ждение науки Институт проблем управления РАН.

Защита состоится 19 декабря 2013 г. в 15-30 на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр им. A.A. Дородницына Российской академии наук», расположенном по адресу: 119333, г.Москва, улица Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан 11 ноября 2013 года.

Ученый секретарь диссертационного совета

Д 002.017.02, д.ф.-м.н., профессор (/¿/ /¿¡¿Ся/^ Рязанов В.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

Объект исследования: прикладные задачи распознавания образов, в которых единственным способом восприятия объекта распознавания является измерение его сходства/несходства с другими объектами.

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

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

Задачи исследования. Для реализации изложенных основных принципов предлагаемого подхода к построению выпуклых критериев и параллелизуемых алгоритмов селективного комбинирования разнородных представлений объектов в задачах восстановления зависимостей по эмпирическим данным в данной работе ставятся следующие основные задачи:

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

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

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

4. Разработка последовательных алгоритмов выбора уровня селективности в задачах обучения на основе парного сравнения объектов.

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

6. Экспериментальное исследование разработанных алгоритмов обучения распознаванию образов и восстановления числовых зависимостей на основе селективного комбинирования функций парного сравнения объектов.

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

Научная новизна. В работе впервые предложена концепция отбора релевантных объектов и релевантных способов сравнения объектов одновременно.

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

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

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

3. Эффективные последовательные алгоритмы выбора уровня селективности в задачах обучения на основе парного сравнения объектов.

4. Эффективные последовательные алгоритмы в задачах восстановления числовых зависимостей на основе парного сравнения объектов.

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

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

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

Связь с плановыми научными исследованиями. Работа выполнена при поддержке грантов Российского фонда фундаментальных исследований №№ 11-07-00409-а, 11-07-00634-а, 12-07-13142-офи-м.

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

Апробация работы. Основные положения и результаты диссертации докладывались на конференциях: «Интеллектуализация обработки информации» (Будва, Черногория, 2012 г.), «Распознавание образов в биоинформатике» (РЮВ-2012, Токио, Япония, 2012 г.), «Международная конференция по распознаванию образов» (1СР11-2012, Цукуба, Япония, 2012 г.), «Математические методы распознавания образов» (Казань, 2013 г.).

Публикации. По тематике работы опубликовано 7 статей, в том числе 2 статьи в журналах, рекомендованных ВАК.

Структура и объём работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы. Материал изложен на 105 страницах, содержит 9 рисунков, 4 таблицы, список литературы из 43 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проанализирован круг прикладных задач, приводящих к необходимости обучения при отсутствии явного вектора признаков и необходимости отбора релевантных объектов и релевантных методов парного сравнения объектов. Проанализированы классические методы отбора признаков в задачах восстановления зависимостей по эмпирическим данным. Проанализированы классические методы беспризнакового восстановления зависимостей по эмпирическим данным. Сформулированы основные проблемы существующих методов восстановления зависимостей в случае отсутствия явного вектора признаков.

Алгоритм вычисления оценок, предложенный Ю.И. Журавлёвым еще в 70-х годах, как раз ставит задачу отбора подмножества реле-вантных объектов (опорного подмножества объектов), описывая каждый объект множеством значений разных функций парного сравнения. Но, в силу недостатка вычислительных мощностей, для решения этой задачи используется комбинаторный подход, а не оценивается разделяющая гиперплоскость. Впоследствии Роберт Дьюин предложил использовать не сами признаки в качестве описания объектов, а значения некоторой функции парного сравнения 5(и/,а/') данного объекта со всеми объектами обучающей совокупности ы^ & О. = = 1. А,г.

В данной работе рассматривается ситуация, когда функций парного сравнения, описывающих объекты, задано несколько: Si(oj',w"),i = 1 ,т. Из этих функций нужно выбрать подмножество релевантных. Соответственно, каждый объект теперь описывается mN числами, то есть мы имеем ситуацию, когда количество признаков, которыми характеризуется объект, значительно превышает объём обучающей совокупности. Поэтому очень важно отобрать из этого множества признаков релевантные, чтобы избежать эффекта переобучения и чтобы процесс распознавания нового объекта не требовал большого количества памяти и вычислительных ресурсов.

Начнём с задачи обучения распознаванию двух классов объектов. Для того, чтобы эффективно отбирать из заданного множества вторичных признаков релевантные, предлагается использовать критерий SVM с квадратично-модульной регуляризацией. Как и в классической SVM, предполагается, что объекты реального мира со G fl описываются п признаками х(ш) = (xi(w),.... хп(и>)), которых значительно больше, чем объектов N в обучающей выборке, в нашем случае п = mN. Исследуется следующая задача поиска

оптимальной разделяющей гиперплоскости у(х, а) = ^^ сцт^ + 6 «s О Для за-

¿=1

данной обучающей совокупности:

' п N

+ МЫ! + I] 5J min ¿=1 j=1 а' '

" _ (1)

»(X>sit + b) ^ 1 - 6j,j = 1 ,N t=l _

Коэффициенты ß, ¡i должны удовлетворять условиям: ß ^ 0, fi ^ 0, ß + ß > 0. Критерий остаётся строго выпуклым, гарантируя единственность решения.

Критерий обучения (1) остаётся полностью применимым в ситуации, когда представление объектов при помощи функцию сравнения S(w', со") более удобно, чем при помощи признакового описания x(w). Значения функции сравнения объекта и> е П на каждом из N объектов обучающей совокупности xi (ш) = S(uji,uj) могут быть использованы как его вторичные признаки. В этом случае мы получаем обобщённую версию RVM - Relevance Vector Machine, впервые предложенную Кристофером Бишопом и Майклом Типпингом, которую в нашей версии следует назвать Relevance Object Machine, потому что нет никакой связи с представлением объектов при помощи векторов признаков.

Возможность представления объектов несколькими априори равновероятными функциями парного сравнения Si(ui',ui"),i = l,m не влияет принципиально на критерий, кроме того, что количество вторичных признаков расширяется до mN:

{ Xu = Si(uii,ui) ддя всех шей xuj = Si(tüi,ш^для j-ого объекта ujj

Прямое обобщение критерия (1) даёт выпуклый критерий обучения, который отличается только количеством переменных:

' т N N

Л ]С+v\au\] + J25i m,ir? >

— ----üu.b.öi

г—1 ¡=1 j=1 '

m N

viC^Z Y1 aüXü<j + sjJ = mv

i=i г=1 __

JjZ 0,j = l,N

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

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

п N п

Y,(ßai + +- J2 mjn <4)

!= 1 j=1 i= 1 3

Здесь 0 ^ ß < +оо, О ^ ß < +оо.

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

' п N

]r{ßa2i + + J262j~> ,min,

^T , a>°ii—Av

J=1 __(5)

8j = =N

i= 1

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

разделяющей гиперплоскости явным образом, тем самым производя отбор релевантных признаков. Это свойство данного критерия описывается следующей теоремой:

Теорема 1. Оптимальная гиперплоскость (ац,г = 1,п,1 = 1, N. Ь) определяется равенствами

ац = ^{вц + ц), эц < -ц, ац = 0,-/2 ^ ЭЦ ^ ц, _0.il = ^(«г/ - /.> М,

^ >() «|7/О '1<1Х<1.3 _1 У]

Ъ = —

(6) (7)

где

Sil — Vj^jxiUji j:Xj>0

{j : 0 < Xj < 1} и {j : Xj = 1} - подмножества ненулевых решений {j : Xj > 0} двойственной задачи выпуклого программирования:

(W(Xu...,XN\fi) = ZUXi-

N j=i

mm 0

ft - J2 yj^jxu,j i=i

T,f= 1 Узхз = _

{O^Xj^l, j = l,N

Аналогичная теорема для задачи восстановления числовых зависимостей:

i n N

"43 S Y1 г—1 ;=1

шах

(8)

Теорема 2. Значения коэффициентов регрессии (ац, г = 1, п, 1 = 1, А', Ь) определяется равенствами

1 / " \ *

äj(5i, ...,5n) = <

\j=i / j=i N

0, -fj./2 < Sjxij < м/2,

(9)

3=1

\ äjXij - ii j, ¿зхи > m/2'

где Sj,j = 1. N - решение двойственной задачи квадратичного программнро-

"з

вания:

^ = \ Е {™п +| - }2+- - у) т1п(5) (10> ¿=1

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

Для численного решения задач (3) предлагается эффективный, хорошо масштабируемый на многопроцессорные системы итерационный алгоритм. Построение стандартного классификатора БУМ сводится к решению задачи квадратичного программирования. Кроме того, на практике появляются неквадратичные задачи БУМ, которые сводятся к решению выпуклой задачи оптимизации, но скорость работы стандартных методов становится узким горлышком при построении разделяющей гиперплоскости. Один из известных подходов к построению стандартного классификатора БУМ - использовать эвристический алгоритм БМО. Во-первых, БМО заточен под решение именно квадратичной задачи, к которой сводится классический 8УМ, а значит неквадратичные задачи выпуклой оптимизации этим алгоритмом решать нельзя. Во-вторых, 8МО делает большое количество итераций, поэтому на очень больших объёмах данных его ускорить не удастся.

Существующие способы, оптимизирующие скорость построения классификатора БУМ, не годятся по следующим причинам.

• Классические методы решения БУМ заточены под стандартный БУМ, а именно его «квадратичность», поэтому не обобщаются на критерий произвольного вида.

• Способы класса БМО делают очень много «легковесных» итераций. Естественно, если выборка большая, такие алгоритмы будут работать очень долго. Задействовать мощности современных кластеров в случае с ЯМО либо с другим аналогичным алгоритмом, делающим много итераций, невыгодно.

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

• Метод проекции градиента

• Метод условного градиента

• Метод внутренней точки (метод штрафных функций)

Каждый из перечисленных методов обладает своими преимуществами и недостатками. Нас в первую очередь интересует скорость работы этих методов и требуемая для их работы память. Метод проекции градиента и метод условного градиента требуют линейных расходов по памяти в зависимости от размерности задачи. Однако, их слабая сторона - количество итераций, которые эти методы делают. Очень часто даже в задачах небольшой размерности (N ~ 100 ) эти методы выполняют тысячи итераций. Естественно, что как бы отдельная итерация ни была ускорена, все равно принципиально большой скорости достигнуть не получится в силу того, что этих итераций выполняется очень много.

Метод внутренней точки в этом смысле обладает гораздо более высокими показателями скорости. Даже на больших объёмах данных (N ~ 1000) этот метод выполняет десятки итераций. Однако, каждая итерация вычислительно оказывается тяжёлой. Связано это с тем, что метод внутренней точки сводит исходную задачу математического программирования к задаче безусловной оптимизации, добавляя к целевой функции штрафные функции, штрафующие выход переменных оптимизации за пределы области допустимых ограничений. Сама задача безусловной оптимизации решается методом Ньютона, что означает, что на каждой итерации нужно перемножить матрицы размеров N х N и решить систему линейных уравнений размеров N х N . Первая из этих операций очень хорошо параллелится. Вторая операция тоже может быть распараллелена, но менее эффективно. Метод внутренней точки требует много памяти для хранения матриц размеров N х N , то есть потребление памяти в этом случае растет квадратично от размерности задачи.

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

Для численного поиска решения критерия (5) в задачах восстановления числовых зависимостей предлагаются эффективные алгоритмы регуляризации.

Идея алгоритма регуляризации впервые была сформулирована для критерия Лассо(¡3 = 0) и затем расширена на случай Elastic Net(/3 > 0). Мотивацией послужило предположение, что поиск зависимости вектора коэффициентов

регрессии от параметра селективности = в один проход сразу для

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

Пусть коэффициент (3 > О взят достаточно малым, чтобы гарантировать строгую выпуклость целевой функции Elastic Net (1). В основе теоретического обоснования алгоритма регуляризации для всех значений параметра селективности /i > 0 лежит математический факт, что зависимость аД/х), определённая обучающим критерием Elastic Net - непрерывная, кусочно-линейная функция, имеющая конечное количество точек бифуркации. Будем рассматривать эти точки как уменьшающуюся последовательность (/imax = //0 > > ....,> цм = 0). Можно доказать, что количество нетривиальных точек М удовлетворяет неравенству п ^ М ij 2П, где п = |1| - количество признаков.

Это значит, что в терминах теоретического подхода для каждой обучающей совокупности убывающая последовательность точек бифуркации /imax —¥ Hk —> 0 задаёт соответствующую дискретную последовательность разбиений множества признаков Р^, начиная с разбиения, в котором все признаки отсутствуют Iq = tg (J = 0> и заканчивая разбиением, включающим в себя все признаки Пд/ = I. Между двумя соседними точками бифуркации разбиение остаётся неизменным рк-i > /< > /<ь но следует отметить, что, вообще говоря, размер множества активных признаков |1Ц.| не является монотонно возрастающей функцией от значения параметра селективности ¡i.

Теоретически всего точек бифуркации может быть 2п. Однако такое число чрезмерно велико для применения предлагаемого алгоритма Машины Релевантных Обьектов, базирующегося на принципе отбора признаков. В нашем случае количество вторичных признаков п = |I| = rnN превышает размер обучающей совокупности ЛГ = |JJ| в такое же количество раз, сколько задано функций парного сравнения объектов т = |К|. Поэтому мы будем использовать «урезанный» алгоритм регуляризации.

Окончательным результатом алгоритма регуляризации является последовательность подмножеств активных признаков 1ь к = 0,1,..., М. Мощность этих подмножеств в общем случае возрастает от 0 до полного количества признаков п = mN, но её зависимость от параметра селективности необязательно монотонная.

Четвертая глава посвящена численной реализации алгоритмов, изложенных во второй и третьей главах. Алгоритмы регуляризации и алгоритмы решения выпуклой задачи (3) устроены так, что это итерационные алгоритмы, основное время работы которых заключается в выполнении на каждой итерации операций умножения и решения системы линейных уравнений для матриц размеров N х N, где N - количество объектов обучающей совокупности.

Кроме стандартного алгоритма умножения матриц N х N за время 0(Лг3), известны также алгоритмы, работающие быстрее:

1. Алгоритм Штрассена умножает две матрицы размеров N х N за 0(N2m?)

2. Алгоритм Коперника-Винограда, имеющий сложность умножения 0(iV2'3755)

3. Алгоритм Вильяме, имеющий сложность 0(N%3727)

Представим, что у нас в распоряжении очень простая вычислительная система - видеокарта NVidia Geforce 31 ОМ, имеющая 16 GPU. Оценим, каких размеров должна быть матрица, чтобы алгоритм Штрассена дал выигрыш по сравнению с распараллеливанием на 16 ядер. Ответ прост: N = 1 б3-2 807 ~ 1000000. В оперативной памяти такая матрица занимала бы 8х11°"(]°200 и 8 терабайт, что на текущий момент технически невозможно принципиально. Ясно, что при переходе к более мощным вычислительным системам выигрыш в скорости будет только увеличиваться при неизменных размерах матрицы. Что касается алгоритма Вильяме и алгоритма Коперника-Винограда, то эти алгоритмы имеют очень большую константу сложности, поэтому выигрывают у современных алгоритмов на матрицах, размеры которых превосходят современные технические возможности компьютеров. Поэтому в рамках данной работы параллельное умножение матриц на видеокарте - лучшее решение из всех возможных, исходя из количества арифметических операций. Если рассмотреть детали технической реализации, то необходимо учесть тот факт, что матрицу, загруженную в оперативную память компьютера, необходимо 1 раз скопировать в оперативную память видеокарты, что по порядку величины занимает 0{N2) операций. Учитывая современные скорости передачи информации CPU —> GPU и GPU —> CPU, даже для матрицы 10000 х 10000 подобная операция копирования займет меньше секунды, что в разы меньше времени, которое тратится на операции умножения матриц на GPU. В рамках данной работы выполнено две реализации алгоритмов умножения матриц: для однопроцессорной машины(СРи) и для видеокарты(ОРи). В качестве фреймворка, на базе которого выполнялась реализация алгоритмов, был взят OpenCL. Это удобный современный фреймворк, сочетающий в себе возможность гибкой разработки на С++ и реализованный практически подо все современные видеокарты, в частности карты NVidia. Видно, что выигрыш при перемножении матриц больших размеров доходит до 25 раз. Это связано не только с тем, что на видеокарте большее количество ядер, чем на центральном процессоре, но ещё и с тем, что планировщик параллельных вычислений на видеокарте работает лучше и оптимальнее распределяет нагрузку, чем аналогичный планировщик на CPU.

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

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

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

Рис. I: Среднее время работы двух разных реализаций алгоритма умножения матриц - на видеокарте и на однопроцессорной машине - в зависимости от размера умножаемых матриц.

Для предсказания вторичной структуры белка на основе его фрагментов мы применили Машину Релевантных Объектов, описанную в данной работе. Мы ограничились рассмотрением задачи определения э^апсГов во вторичной структуре белков, которая, как показывает практика, представляет собой наиболее проблематичную часть вторичной структуры. Целью данной работы является скорее исследование эффективности КУМ к проблеме оконного предсказания вторичной структуры, чем установление нового рекорда точности. Тем не менее, эксперименты на 118126 показали точность около 75% в определении Бй-апсРов.

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

Пусть А = {а1, ■ ■ ■ , а20} алфавит на множестве аминокислот. Для каждой позиции —Т окне и> = (ат, —Т ^ г ^ Т) и каждой из 20 аминокис-

лот определен бинарный признак гтк(ш) — 1, если ат = ак, и гтк(со) = 0, если ат ф ак.

Т 20

т=~Т к= 1

52(о/,ы") = ехр{-7Ыи/) - гтк(ш")}2}, (11)

Т 20

= ^ \г7к(и) - гтк{ш")\.

т=—Т к= 1

Все признаки образуют бинарный вектор z(w) = zTк{и>), —Т ^ т < Т, к = 1,..., 20). Мы исследовали три вышеозначенные функции сравнения, основанные на таком признаковом описании объектов. В статьях, посвящённых сравнению белков на базе фрагментов, показано, что позиционный принцип сравнения работает лучше, когда применяется к сравнительно небольшим длинам окон, поэтому использовалась рекомендованная длина окна 2Т + 1 = 13.

Суть сравнения двух аминокислотных фрагментов (си', и>") на базе разложения Фурье заключается в использовании вектора признаков в рамках одного метода сравнения S(ui',üj") = S(f(u/), f(w")). Мы исследовали три функции:

S4(u>',cü") = fr(w')f(w"),

S5(wV) = exp {-7||íV) - %")ll2}, (12)

20 4

56(ü/, ш") - fki(oj'%

k=l 1=0

В качестве обучающей выборки использовался стандартный набор белков RS126. Этот набор содержит 126 белков, среди которых схожестью менее 25% обладают все белки длиной более 80 аминокислот. Точность классификации оценивалась для разных уровней селективности аминокислотных фрагментов и разных функций сравнения этих фрагментов. В общей сложности из белков набора RS126 получилось |íí| = 19075 фрагментов и € Í1 длиной 2Т + 1 = 35. Каждый фрагмент отнесен к классу у = ±1, согласно тому, является ли его центральный элемент стрендом или не является. Мы выполнили 4 эксперимента на данном наборе данных.

В каждом эксперименте множество всех окон Q было случайным образом разбито на обучение f2¿r S Г2 размера N = |í2tr| = 1600 и контроль íltest = размера |f2¿est| = 17475.

Множество функций сравнения формируется из (11), (12), т.е. их п = 6. Функции сравнения, основанные на методе Фурье (12), учитывают 2Т+1 = 35 аминокислот каждого фрагмента, а сравнение по позициям (11), применяемое к более коротким фрагментам длины 2Т + 1 = 13, игнорирует 11 аминокислот с обеих сторон фрагментов длины 35.

Каждый из четырёх экспериментов был устроен следующим образом. Мультимодальный RVM обучался на совокупности Гltr, N = 1600 для всех ¡i € {0,0.3.0.5,0.6,0.8,0.9999,0.99999(/г -» 1)}. Максимальное значение параметра /1 —> +оо в данном эксперименте намеренно заменено на //, 1, так как экспериментально было определено, что при д = 1 все признаки исключаются из решающего правила. Таким образом, обучение мультимодальной RVM запускалось 4 х 7 = 28 раз. Это серьезный объём вычислений для настольного компьютера.

Результат каждого обучения мультимодального RVM с конкретным значением ¡i есть подмножество вторичных релевантных признаков F = {i, j :

Ф 0} Я: Р и значений параметров е Р, разделяю-

щей гиперплоскости. Наиболее важное значение имеют множества релевантных объектов(аминокислотных фрагментов обучающей совокупности)=

: 3¿(йу ^ 0)} С {1, А} и релевантных модальностей /(/1) = {г : ^ 0)} С

/ = {1,п}. Обозначим мощности этих двух множеств = |./(/х)| ^ А и = |/(/л)| ^ п. Параметр /3 был определен на основании процедуры кросс-валидации и составил /3 = 0.001.

Оставшееся множество = О \ Пгг аминокислотных фрагментов было случайно разбито на 10 подмножеств для контроля, после чего мы посчитали точность распознавания вторичной структуры {стренд} против {нестренд} для каждого из них. Окончательная точность для каждого из значений селективности характеризуется двумя числами: мат. ожиданием Асс(^) и дисперсией сг(ц). Доверительный интервал для точности классификации мы оценили как Асс(ц) ± 2ст(р).

Рисунок (2) демонстрирует зависимость точности предсказания Асс(ц) и количества релевантных аминокислотных фрагментов, участвующих в решающем правиле N(¡1), от уровня селективности /х. Из рисунка видно, что во всех экспериментах наилучшая точность классификации 75.5% достигается при /л = 0, т.е. когда все 1600 аминокислотных фрагментов, образующих обучающую совокупность, и все б функций сравнения участвуют в разделяющей гиперплоскости. Последняя соответствует пространству вторичных признаков размерностью пАг = 9600, получаемых из фрагмента со = (аг е А, —Т ^ г Особенно интересно, что не наблюдается эффекта переобучения после построения разделяющей гиперплоскости в линейном пространстве векторов вторичных признаков х(и) = (х^(ш),г = 1,6,у = 1,1600) е К9600, чья размерность в 6 раз превышает количество объектов обучающей совокупности.

Рис. 2: Экспериментальная зависимость количества релевантных аминокислотных фрагментов N и точности распознавания стрендов на контроле Асс от уровня селективности /а.

С ростом д уменьшается количество релевантных фрагментов и

количество релевантных функций сравнения n(fi), формирующих вторичные признаки аминокислотных фрагментов. Точность остаётся практически на одном уровне во всех независимых экспериментах вплоть до уровня селективности fj, = 0.9999, когда осталось порядка 300 релевантных аминокислотных фрагментов из 1600 и только п = 3 функции сравнения. Уменьшение точности по отношению к её уровню для /и. = 0 не превосходит 1%.

При дальнейшем увеличении д > 0.9999 происходит значительное снижение точности распознавания на всех обучающих совокупностях.

Кроме задачи распознавания образов, в данной работе эффективность Машины Релевантных Объектов проверена на задаче восстановления числовой зависимости, которая заключается в моделировании намагниченности в сверхпроводниках. Данные для этой задачи предоставлены Национальным Технологическим Институтом Стандартов^Ыайопа! Institute of Standards and Technology) http : / /www. nist. gov/index. html.

Набор данных состоит из объектов и G SI, представленных одним наблюдаемым признаком z(w) = (ш) S R и одним скрытым признаком у (tu) G К.

Скрытый признак - это измеренная намагниченность сверхпроводника, наблюдаемый признак - это логарифм от времени, прошедшего с момента старта эксперимента до момента его завершения. Истинная зависимость между скрытым и наблюдаемым признаком описывается у = —2000(50 + z{)~10/9.

Набор данных содержит |f2| = 154 объекта, которые случайно разбиты на N = 75 объектов для обучения и Ntest = 79 объекта для контроля. На Рис. (3) показана заданная скрытая функция у*(z), которую нужно оценить, и обучающая совокупность {(zj,yj),j = 1,..., Af}.

Рис. 3: Обучающая совокупность N = 75 и восстановленная по ней зависимость у'(г). Маркеры Он х обозначают объекты обучающей совокупности Zj и, соответственно, релевантные объекты.

Далее мы применили к обучающей совокупности предложенную в работе Машину Релевантных Объектов с отбором модальностей для фиксированного значения параметра /3 = 15 и для т = 4 функций парного сравнения:

Я^иЛш") = 51(2', ъ") = (1 + -

З3(ш',ш") = ехр(—1.5 * - + + и ;

= = ехр(-1.5|^ - г'{\)

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

Таким образом, мы имеем полный набор I = {г = (/,;;)} из п = тМ = 300 вторичных признаков, сформированный из т = 4 модальностей и ЛГ = 75 объектов обучения. Для подобной экспериментальной структуры максимальное значение параметра селективности равняется (1тах та 94.5.

Применение алгоритма регуляризации привело к тому, что лучшее значение селективности равно ц = 186.4, давая минимальное среднее значение ошибки 1еауе-опе-ои1 С}^00 = 0.000695. Средний квадрат ошибки на контроле оказался немного выше: О1^1 = 0.000805. Обе оценки хорошо согласуются со значением квадрата отклонения истинной зависимости от наблюдаемых значений скрытой переменной Уаг(у) = 0.00052.

Соответствующее подмножество релевантных вторичных признаков I = {(/у)} содержит 11 элементов. Все эти элементы были сформированы разными релевантными объектами ] = {]} С I, связанными с одной и той же функцией парного сравнения ¿^(г', г"), как и ожидалось.

ЗАКЛЮЧЕНИЕ

Основные результаты работы:

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

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

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

4. Разработаны последовательные алгоритмы выбора уровня селективности в задачах обучения на основе парного сравнения объектов.

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

6. Экспериментально исследованы разработанные алгоритмы обучения распознаванию образов и восстановления числовых зависимостей на основе селективного комбинирования функций парного сравнения объектов.

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

Основные положения диссертации опубликованы в следующих работах

[1] Выпуклые критерии релевантных векторов для сокращения размерности представления объектов в беспризнаковом распознавании образов / Олег Середин, Вадим Моттль, Александр Татарчук, Николай Разин // Сборник трудов ИОИ-9. - 2012. - С. 50 - 53.

[2] Применение мультимодальной rvm в задаче распознавания вторичной структуры белков / Николай Разин, Дмитрий Сунгуров, Вадим Моттль и др. // Сборник трудов ИОИ-9. - 2012. - С. 585 — 588.

[3] Convex support and relevance vector machines for selective multimodal pattern recognition / Oleg Seredin, Vadim Mottl, Alexander Tatarchuk et al. // ICPR-2012 proceedings. - 2012.

[4] Multi-Modal Relevance Vector Machines for protein secondary structure prediction / Nikolay Razin, Dmitry Sungurov, Vadim Mottl et al. // PRIB-2012 proceedings. - 2012. — P. 153 — 165.

[5] Выпуклые критерии релевантных векторов для сокращения размерности описания объектов, представленных парными отношениями /

О. С. Середин, В. В. Моттль, А. И. Татарчук, Н. А. Разин // Известия Тульский Государственный Университет. — 2013. — Т. 1. — С. 165- 176.

[6] Применение Машины Релевантных Объектов в задачах восстановления числовых зависимостей / Разин Н. А., Черноусова Е. О., Красотки-на О. В., Моттль В. В // Машинное обучение и анализ данных. — 2013. — Т. 1, № 5. — С. 641 -652.

[7] Разин Н. А., Моттль В. В. Численная реализация алгоритмов селективного комбинирования разнородных представлений объектов в задачах распознавания образов // Машинное обучение и анализ данных. — 2013. — Т. 1, № 6. - С. 734 - 750.

Жирным шрифтом выделены публикации в журналах, рекомендованных

ВАК. Все приведённые в статьях результаты исследований получены лично

автором. Все статьи, кроме [3], [4], написаны лично автором с последующим

участием соавторов в редактировании текста.

Разин Николай Алексеевич

ВЫПУКЛЫЕ КРИТЕРИИ И ПАРАЛЛЕЛИЗУЕМЫЕ АЛГОРИТМЫ

СЕЛЕКТИВНОГО КОМБИНИРОВАНИЯ РАЗНОРОДНЫХ ПРЕДСТАВЛЕНИЙ ОБЪЕКТОВ В ЗАДАЧАХ ВОССТАНОВЛЕНИЯ ЗАВИСИМОСТЕЙ ПО ЭМПИРИЧЕСКИМ ДАННЫМ

АВТОРЕФЕРАТ

Подписано в печать 11.11.2013. Формат 60x84 Уш. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 338. Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9.

Текст работы Разин, Николай Алексеевич, диссертация по теме Теоретические основы информатики

Министерство образования и науки РФ Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

П1ппй1 На правах рукописи

04201452570

Разин Николай Алексеевич

Выпуклые критерии и параллелизуемые алгоритмы селективного комбинирования разнородных представлений объектов в задачах восстановления зависимостей по эмпирическим

данным

Специальность 05.13.17 - Теоретические основы информатики

Диссертация на соискание учёной степени кандидата физико-математических наук

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

доктор технических наук, профессор, Моттль Вадим Вячеславович

Москва - 2013

Оглавление

ВВЕДЕНИЕ 5

1 ПРОБЛЕМА ВОССТАНОВЛЕНИЯ ЗАВИСИМОСТЕЙ ПО ЭМПИРИЧЕСКИМ ДАННЫМ ПРИ ОТСУТСТВИИ ЯВНО ВЫРАЖЕННОГО ВЕКТОРА ПРИЗНАКОВ ОБЪЕКТОВ 10

1.1 Прикладные задачи построения моделей эмпирических зависимостей при отсутствии явно выраженного вектора признаков объектов 10

1.1.1 Прогнозирование вторичной структуры белка как задача обучения распознаванию образов............... 10

1.1.2 Задача определения намагниченности в сверхпроводниках . 12

1.2 Современные методы отбора признаков объектов.......... 13

1.2.1 Критерий обучения Lasso ................... 14

1.2.2 Критерий обучения Elastic Net................. 16

1.3 Современные методы беспризнакового восстановления зависимостей .................................... 17

1.3.1 Метод потенциальных функций................ 17

1.3.2 Принципы восстановления зависимостей на основе метода потенциальных функций.................. 19

1.3.3 Произвольная функция попарного сравнения объектов ... 23

1.3.4 Метод релевантных векторов на основе метода потенциальных функций.........................23

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

1.4.1 Линейное пространство вторичных признаков объектов и задача их отбора.........................25

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

1.4.3 Итерационный принцип численного решения выпуклых задач обучения .........................30

1.4.4 Последовательные процедуры регуляризации........32

1.4.5 Параллельная реализация отдельной итерации .......33

2 МНОГОМОДАЛЬНЫЙ МЕТОД РЕЛЕВАНТНЫХ ОБЪЕКТОВ ДЛЯ

ЗАДАЧ ОБУЧЕНИЯ РАСПОЗНАВАНИЮ ОБРАЗОВ 34

2.1 Выпуклый критерий обучения - дважды регуляризованная машина опорных векторов..........................34

2.1.1 Машина КУМ с произвольными функциями парного сравнения ...............................35

2.2 Двойственная запись критерия и разбиение множества вторичных признаков.................................35

2.3 Итерационный алгоритм решения двойственной задачи.......38

2.3.1 Вспомогательные теоремы и утверждения..........38

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

2.3.3 Анализ сложности алгоритма решения выпуклых задач селективного комбинирования потенциальных функций ... 43 2.4 Обобщение алгоритма на случай произвольной выпуклой целевой функции для 8УМ-подобных задач обучения распознаванию

образов..................................46

3 МНОГОМОДАЛЬНЫЙ МЕТОД РЕЛЕВАНТНЫХ ОБЪЕКТОВ ДЛЯ ЗАДАЧ ОЦЕНИВАНИЯ ЧИСЛОВЫХ ЗАВИСИМОСТЕЙ 47

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

3.2 Двойственная запись критерия и разбиение множества вторичных признаков.................................48

3.3 Итерационный алгоритм решения двойственной задачи.......52

3.3.1 Вспомогательные теоремы и обозначения..........53

3.3.2 Описание итерационного алгоритма решения двойственной задачи............................57

3.3.3 Анализ сложности итерационного алгоритма регуляризации 58

3.4 Последовательный алгоритм регуляризации.............59

3.4.1 Вспомогательные теоремы...................61

3.4.2 Алгоритм регуляризации....................70

3.4.3 Анализ сложности алгоритма регуляризации ........74

4 ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ ОБУЧЕНИЯ 75

4.1 Модульная реализация распараллеливания..............75

4.1.1 Умножение матриц.......................75

4.1.2 Решение системы линейных уравнений............76

4.2 Реализация алгоритма умножения матриц ..............78

4.2.1 Параллельное умножение матриц на CPU..........79

4.2.2 Параллельное умножение матриц на видеокарте NVidia GeForce 31 ОМ..........................81

4.3 Полученное ускорение.........................84

5 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МНОГОМОДАЛЬНОГО МЕТОДА РЕЛЕВАНТНЫХ ОБЪЕКТОВ 86

5.1 Модельные эксперименты .......................86

5.1.1 Задача обучения распознаванию образов...........86

5.1.2 Задача восстановления числовой зависимости........89

5.2 Прогнозирование вторичной структуры белка как задача обучения распознаванию образов.........................91

5.2.1 Метод скользящего окна....................91

5.2.2 Методы попарного сравнения аминокислотных фрагментов 93

5.2.3 Позиционный метод сравнения................93

5.2.4 Сравнение на базе Фурье-спектра...............94

5.2.5 Результаты численных экспериментов............95

5.3 Восстановление зависимости намагниченности в сверхпроводниках в зависимости от времени проведения эксперимента как задача восстановления числовой зависимости ..............97

ЗАКЛЮЧЕНИЕ 100

Литература 102

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

Положения, выносимые на защиту.

2. Выпуклые критерии, отбирающие релевантные объекты и релевантные

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

Апробация работы. Основные положения и результаты диссертации докладывались на конференциях: «Интеллектуализация обработки информации» (Будва, Черногория, 2012 г.), «Распознавание образов в биоинформатике» (РШВ-2012, Токио, Япония, 2012 г.), «Международная конференция по распознаванию образов» (1СРЯ-2012, Цукуба, Япония, 2012 г.), «Математические методы распознавания образов» (Казань, 2013 г.).

По теме диссертации автором опубликовано 7 работ (из них 2 в изданиях из перечня ВАК).

Обоснованность и достоверность результатов и выводов подтверждена:

1. Сравнением реализованных алгоритмов и подходов с аналогами;

2. Строгостью и корректностью математических доказательств, рассуждений;

3. Опытом практического применения результатов исследования на реальных прикладных задачах;

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

5. Подтверждением результатов экспертными оценками специалистов;

6. Обсуждением результатов исследования на российских и международных научных конференциях и семинарах;

7. Публикациями результатов исследования в рецензируемых научных изданиях, в том числе рекомендованных ВАК РФ.

ГЛАВА 1

ПРОБЛЕМА ВОССТАНОВЛЕНИЯ ЗАВИСИМОСТЕЙ ПО ЭМПИРИЧЕСКИМ ДАННЫМ ПРИ ОТСУТСТВИИ ЯВНО

ВЫРАЖЕННОГО ВЕКТОРА ПРИЗНАКОВ ОБЪЕКТОВ

1.1 Прикладные задачи построения моделей эмпирических зависимостей при отсутствии явно выраженного вектора признаков объектов

1.1.1 Прогнозирование вторичной структуры белка как задача обучения распознаванию образов

Наглядным примером задачи распознавания образов при отсутствии явно выраженного вектора признаков является задача предсказания вторичной структуры белка по его первичной структуре [1].

В наст

Похожие работы

Информатика, вычислительная техника и управление
05.13.00