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

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

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

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

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

ЗАДАЧАХ ВОССТАНОВЛЕНИЯ ЗАВИСИМОСТЕЙ ПО

ЭМПИРИЧЕСКИМ ДАННЫМ

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

АВТОРЕФЕРАТ

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

Москва — 2013

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

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

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

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

кандидат технических наук, доцент Копылов Андрей Валериевич.

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

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт проблем управления РАН.

Защита состоится 19 декабря 2013 г. в 15-30 на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр им. А.А. Дородницына Российской академии наук», расположенном по адресу: 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 г.), «Распознавание образов в биоинформатике»

(PRIB-2012, Токио, Япония, 2012 г.), «Международная конференция по распознаванию образов» (ICPR-2012, Цукуба, Япония, 2012 г.), «Математические методы распознавания образов» (Казань, 2013 г.).

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

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

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

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

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

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

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

Начнём с задачи обучения распознаванию двух классов объектов. Для того, чтобы эффективно отбирать из заданного множества вторичных признаков релевантные, предлагается использовать критерий SVM с квадратичномодульной регуляризацией. Как и в классической SVM, предполагается, что объекты реального мира описываются признаками x() = (1 (),..., ()), которых значительно больше, чем объектов в обучающей выборке, в нашем случае =. Исследуется следующая задача поиска оптимальной разделяющей гиперплоскости (x, a) = + 0 для заданной обучающей совокупности:

Коэффициенты, должны удовлетворять условиям: 0, 0, + > 0.

Критерий остаётся строго выпуклым, гарантируя единственность решения.

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

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

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

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

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

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

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

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

Это значит, что в терминах теоретического подхода для каждой обучающей совокупности убывающая последовательность точек бифуркации 0 задаёт соответствующую дискретную последовательность разбиений множества признаков, начиная с разбиения, в котором все признаки отсутствуют 0 = + =, и заканчивая разбиением, включающим в себя все признаки = I. Между двумя соседними точками бифуркации разбиение остаётся неизменным 1 > >, но следует отметить, что, вообще говоря, размер множества активных признаков | | не является монотонно возрастаюI щей функцией от значения параметра селективности.

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

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

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

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

1. Алгоритм Штрассена умножает две матрицы размеров за ( 2.807 ) 2. Алгоритм Коперника-Винограда, имеющий сложность умножения ( 2.3755 ) 3. Алгоритм Вильямс, имеющий сложность ( 2.3727 ) Представим, что у нас в распоряжении очень простая вычислительная система - видеокарта NVidia Geforce 310M, имеющая 16 GPU. Оценим, каких размеров должна быть матрица, чтобы алгоритм Штрассена дал выигрыш по сравнению с распараллеливанием на 16 ядер. Ответ прост: = 16 32.807 1000000.

В оперативной памяти такая матрица занимала бы 81000000 8 терабайт, что на текущий момент технически невозможно принципиально. Ясно, что при переходе к более мощным вычислительным системам выигрыш в скорости будет только увеличиваться при неизменных размерах матрицы. Что касается алгоритма Вильямс и алгоритма Коперника-Винограда, то эти алгоритмы имеют очень большую константу сложности, поэтому выигрывают у современных алгоритмов на матрицах, размеры которых превосходят современные технические возможности компьютеров. Поэтому в рамках данной работы параллельное умножение матриц на видеокарте - лучшее решение из всех возможных, исходя из количества арифметических операций. Если рассмотреть детали технической реализации, то необходимо учесть тот факт, что матрицу, загруженную в оперативную память компьютера, необходимо 1 раз скопировать в оперативную память видеокарты, что по порядку величины занимает ( 2 ) операций. Учитывая современные скорости передачи информации CPU GPU и GPU CPU, даже для матрицы 10000 10000 подобная операция копирования займет меньше секунды, что в разы меньше времени, которое тратится на операции умножения матриц на GPU. В рамках данной работы выполнено две реализации алгоритмов умножения матриц: для однопроцессорной машины(CPU) и для видеокарты(GPU). В качестве фреймворка, на базе которого выполнялась реализация алгоритмов, был взят OpenCL. Это удобный современный фреймворк, сочетающий в себе возможность гибкой разработки на C++ и реализованный практически подо все современные видеокарты, в частности карты NVidia. Видно, что выигрыш при перемножении матриц больших размеров доходит до 25 раз. Это связано не только с тем, что на видеокарте большее количество ядер, чем на центральном процессоре, но ещё и с тем, что планировщик параллельных вычислений на видеокарте работает лучше и оптимальнее распределяет нагрузку, чем аналогичный планировщик на CPU.

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

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

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

Для предсказания вторичной структуры белка на основе его фрагментов мы применили Машину Релевантных Объектов, описанную в данной работе. Мы ограничились рассмотрением задачи определения strand’ов во вторичной структуре белков, которая, как показывает практика, представляет собой наиболее проблематичную часть вторичной структуры. Целью данной работы является скорее исследование эффективности RVM к проблеме оконного предсказания вторичной структуры, чем установление нового рекорда точности. Тем не менее, эксперименты на RS126 показали точность около 75% в определении strand’ов.

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

Пусть = {1, · · ·, 20 } алфавит на множестве аминокислот. Для каждой позиции в окне = (, ) и каждой из 20 аминокислот определен бинарный признак () = 1, если =, и () = 0, если 1,..., 20). Мы исследовали три вышеозначенные функции сравнения, основанные на таком признаковом описании объектов. В статьях, посвящённых сравнению белков на базе фрагментов, показано, что позиционный принцип сравнения работает лучше, когда применяется к сравнительно небольшим длинам окон, поэтому использовалась рекомендованная длина окна 2 + 1 = 13.

Суть сравнения двух аминокислотных фрагментов (, ) на базе разложения Фурье заключается в использовании вектора признаков в рамках одного метода сравнения (, ) = (f ( ), f ( )). Мы исследовали три функции:

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

Каждый фрагмент отнесен к классу = ±1, согласно тому, является ли его центральный элемент стрендом или не является. Мы выполнили 4 эксперимента на данном наборе данных.

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

Множество функций сравнения формируется из (11), (12), т.е. их = 6.

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

Каждый из четырёх экспериментов был устроен следующим образом.

Мультимодальный RVM обучался на совокупности, = 1600 для всех {0, 0.3, 0.5, 0.6, 0.8, 0.9999, 0.99999( 1)}. Максимальное значение параметра + в данном эксперименте намеренно заменено на 1, так как экспериментально было определено, что при = 1 все признаки исключаются из решающего правила. Таким образом, обучение мультимодальной RVM запускалось 4 7 = 28 раз. Это серьезный объём вычислений для настольного компьютера.

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

щей гиперплоскости. Наиболее важное значение имеют множества релевантных объектов(аминокислотных фрагментов обучающей совокупности)() = { : ( = 0)} {1, } и релевантных модальностей () = { : ( = 0)} () = |()|. Параметр был определен на основании процедуры кроссвалидации и составил = 0.001.

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

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

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

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

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

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

Набор данных состоит из объектов, представленных одним наблюдаемым признаком z() = 1 () R и одним скрытым признаком () R.

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

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

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

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

Особенность скрытой заданной функции указывает на то, что алгоритм должен отобрать только первую функцию 1 (z, z ) как единственную адекватную функцию искомой зависимости, а в качестве релевантных объектов отобрать небольшое количество объектов обучающей совокупности.{ } Таким образом, мы имеем полный набор I = = () из = = вторичных признаков, сформированный из = 4 модальностей и = объектов обучения. Для подобной экспериментальной структуры максимальное значение параметра селективности равняется 94.5.

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

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

ЗАКЛЮЧЕНИЕ

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

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. // ICPRproceedings. — 2012.

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

[5] Выпуклые критерии релевантных векторов для сокращения размерности описания объектов, представленных парными отношениями / О. С. Середин, В. В. Моттль, А. И. Татарчук, Н. А. Разин // Известия Тульский Государственный Университет. — 2013. — Т. 1. — С. 165 – 176.

[6] Применение Машины Релевантных Объектов в задачах восстановления числовых зависимостей / Разин Н. А., Черноусова Е. О., Красоткина О. В., Моттль В. В // Машинное обучение и анализ данных. — 2013. — [7] Разин Н. А., Моттль В. В. Численная реализация алгоритмов селективного комбинирования разнородных представлений объектов в задачах распознавания образов // Машинное обучение и анализ данных. — 2013. — Т. 1, Жирным шрифтом выделены публикации в журналах, рекомендованных ВАК. Все приведённые в статьях результаты исследований получены лично автором. Все статьи, кроме [3], [4], написаны лично автором с последующим участием соавторов в редактировании текста.

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

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

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

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

АВТОРЕФЕРАТ

Формат 6084 1/16. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 338.

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

Отдел оперативной полиграфии «Физтех-полиграф»

141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9.