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

• Разин, Николай Алексеевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Разин, Николай Алексеевич

Оглавление

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

образов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

Литература

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ГЛАВА 1

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

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

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

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

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

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

Вторичная структура представляет собой проекцию локальной геометрии пространственной структуры белка в последовательность символов трехбуквенного алфавита: Н - helix (спираль), S - strand (полотно), С - coil (петля). Вторичную структуру предсказывают множеством методов [8, 9].

Проблема предсказания вторичной структуры белка впервые была поднята в начале 1960-х, когда число белковых структур определяли с помощью рентгеновской кристаллографии. С применением методов машинного обучения было достигнуто значительное повышение точности прогнозирования [10]. Несмотря на то, что средняя точность предсказания увеличилась, существует очевидное отсутствие прогресса в этой области в последние десятилетия. Например, эксперименты в рамках конференций-турниров CASP (Critical Assessment of the Protein Structure Prediction)[ll], которые проводятся с начала 1990-х годов, яс-

но показывают отсутствие какой-либо значительной положительной тенденции в точности предсказания вторичной структуры белка, по крайней не менее 10 лет с 1992 по 2002 год. Вероятно, именно по этой причине проблема предсказания вторичной структуры белка была удалена из списка проблем, изучаемых в рамках СА8Р (см. публикации СА8Р-5 [12]).

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

Наиболее популярный способ предсказания вторичной структуры белка в позиции £ - это её оценка исходя из локального контекста, т.е на основании фрагмента аминокислотной последовательности фиксированной длины, симметрично расположенного по отношению к целевой позиции Ь [10]. Роль исходной обучающей совокупности играет множество белков с известной вторичной структурой, в котором "учитель"для каждой позиции в аминокислотных последовательностях указал один из трёх индексов /1(ЬеИх), й^гапё), с(соИ). Обычно в качестве рабочей обучающей совокупности используют множество фрагментов аминокислотных последовательностей, вырезанных из исходных белков и играющих роль отдельных объектов распознавания, для каждого из которых указан тип вторичной структуры /г, 5, с, соответствующий центру фрагмента. Однако аминокислотные фрагменты, представляющие такие объекты, не являются векторами числовых признаков. В силу этого обстоятельства задача распознавания вторичной структуры белков относится к классу задач обучения восстановлению зависимостей без явно выраженного вектора признаков объектов.

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

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

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

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

сверхпроводниках

Примером задачи восстановления числовой зависимости является задача моделирования намагниченности в сверхпроводниках [14]. Данные для этой задачи предоставлены Национальным Технологическим Институтом Стандартов (National Institute of Standards and Technology) http://www.nist.gov/ index.html.

Набор данных состоит из объектов и £ Ü, представленных одним наблюдаемым признаком z(cü) = z{uS) б!и одним скрытым признаком у{ю) е Ш.

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

у = -2000(50 + z)~w/9.

(1.1.1)

Это задача восстановления регрессионной зависимости, в данном случае нелинейной, и к ней по-прежнему применима гипотеза компактности, как и к задаче обучения распознаванию образов, пример которой кратко рассмотрен в предыдущем разделе, - если объекты близки в смысле подходящей меры сходства или несходства, то, скорее всего, значения их скрытой характеристики также близки. Использования евклидовой метрики в пространстве числовых признаков объектов эквивалентно поиску искомой зависимости в классе линейных моделей у = a7z + 6. В одномерном случае z = z, как в нашем примере, евклидова метрика на числовой оси, выражаемая модулем разности значений скалярного признака, приведет к классу одномерных линейных моделей у = az + b, использование которого при обучении по совокупности прецедентов даст низкую точность восстановленной зависимости.

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

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

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

объектов

Современные методы отбора признаков делятся на Bpannepbi(wrappers), фильтры(йкегз) и встроенные методы(етЬеёёес! methods).

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

запускать алгоритм обучения.

OrabTpbi(filters) похожи на врапперы и используют те же механизмы для отбора лучшего подмножества признаков, однако для оценки используют не обученный алгоритм, а какие-то быстро вычислимые критерии, позволяющие за небольшое время отобрать наилучшее подмножество признаков. Стандартные способы оценки подмножества признаков: корреляция(согге1айоп)и взаимная информация(тиШа1 information). Кроме этого используется ряд других, менее популярных: критерий Акаике, Байесовский критерий(Вауез1ап information criterion).

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

Наконец, встроенные методы(етЬе<Мес1 methods) устроены так, что они отбирают полезные признаки прямо в процессе обучения классификатора. Классическими примерами embedded-методов являются: критерий Lasso, критерий SVM. Такие методы по вычислительно сложности находятся где-то между фильтрами и врапперами. В данной работе мы ограничимся изучением embedded-методов отбора признаков.

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

Рассмотрим сначала стандартную задачу восстановления числовой зависимости в пространстве нескольких числовых признаков объектов, совместно выражаемых действительным вектором х = (xi,...,xn) G Rn. Пусть задана обучающая совокупность пар объект-значение (х^, yj).j = 1,N. Предположим, что данные центрированы и нормированы:

Ejli Уз = Ejli хл = w EjLi x)i =1 для всех i = M (1.2.1)

Требуется найти такой вектор â = (âi, ...,ân) , который восстанавливает числовую зависимость между объектами и поставленными им в соответствие значениями по следующему правилу:

jjj = Xjiâi + ... + xjnân (1-2.2)

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

N

VVy, - Xjidi - ... - Xjnan)2 min (1.2.3)

' 1 3i

Такой подход обладает следующими недостатками:

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

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

Первый недостаток устраняется при помощи очень простой регуляризации (называемой Ridge Regression) за счёт добавления штрафа на вектор а в виде L2 нормы. Критерий выглядит следующим образом:

п N

+ ~~ xilCLl ~ - * Хз^ап)2 min,ß > 0 (1.2.4)

г=1 3=1

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

Для того, чтобы происходил отбор признаков, Тибширани[15] изменил критерий таким образом, чтобы регуляризация происходила при помощи штрафа на вектор а в виде Li нормы:

п N

+ ~ хЯа1 - - - хзпап)2 min, ¡1 > 0 (1.2.5)

г=1 3=1

Такой критерий называется Lasso. В решающем правиле, найденном по критерию (1.2.5), большая часть коэффициентов вектора â принципиально являются нулевыми, что делает полученное решающее правило интерпретируемым. Тем не менее, Lasso обладает следующими недостатками:

• В случае, когда п > N , Lasso оставляет ненулевыми не более N коэффициентов в векторе â , что ограничивает подобный подход в ряде задач отбора признаков

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

• В стандартных случаях, когда N > п , экспериментально замечено, что точность на контроле выше у Ridge регрессии, чем у Lasso.

Первые два недостатка Lasso делают невозможным его использование в некоторых задачах. Например, в задачах отбора генов данные устроены так, что объекты описываются, как правило, сотнями признаков, при том, что самих объектов не более 100. Требования к алгоритму отбора генов таковы, что он должен отбирать тривиальные гены и должен показать группы генов, которые ведут себя одинаковым образом. Ясно, что в таком случае Lasso неприменим, так как в силу своей структуры, отберет не более, чем 100 генов в принципе.

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

Критерий Elastic Net, как и Lasso, отбирает признаки. Но кроме этого, Elastic Net умеет отбирать группы сильно коррелированных признаков. Критерий Elastic Net - это комбинация критериев Ridge регрессии и Lasso:

п N

^[/За- + + - Xjidi - ... - Xjnan)2 min (1.2.6)

t=i j=î

Параметры критерия удовлетворяют /3 ^ 0, /i ^ 0, /3 -f /2 > 0 . Если в критерии (1.2.6) положить /х = 0, получится стандартный Lasso. Если положить /3 = 0, получится Ridge регрессия. Очевидно, что можно выполнить преобразование входных данных хj, j = 1, N, при котором критерий Elastic Net можно будет записать в терминах задачи Lasso. Эксперименты показывают, что в подавляющем большинстве случаев Elastic Net допускает меньше ошибок на контрольной выборке в сравнении с Lasso.

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

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

Классическая теория распознавания образов разрабатывает методы построения решающих правил и классификаторов в предположении, что на исследуемом объекте уже измерены значения так называемых «полезных» признаков. Решающее правило распознавания обычно имеет вид линейной функции в этом пространстве, призванной как можно лучше отнести объекты к тому или иному классу. Положение разделяющей гиперплоскости относительно каждого из классов, естественно, определяется не столько конкретными значениями «полезных» признаков объектов, сколько евклидовыми расстояниями между соответствующими точками в линейном признаковом пространстве [16], [17]. Поэтому именно метрика, определяющая взаимное расположение объектов в этом гипотетическом пространстве, является инструментом для принятия решения о принадлежности объекта к тому или иному классу (1.1). В результате оказывается, что достаточно уметь тем либо иным образом определять степень сходства (или несходства) любых двух объектов, и нет необходимости в явном указании векторов их признаков.

Список литературы диссертационного исследования кандидат наук Разин, Николай Алексеевич, 2013 год

Литература

[1] Гельфанд М. С. Биофизика // Апология Биоинформатики. — 2005. — Т. 50, № 4. - С. 752-766.

[2] Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. — М.: Наука, 1970. — С. 384.

[3] Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974. - С. 415.

[4] Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. - С. 447.

[5] Татарчук А. И., Урлов Е. Н., Моттль В. В. Метод опорных потенциальных функций в задаче селективного комбинирования разнородной информации при обучении распознаванию образов // Математические методы распознавания образов: 14-я Всероссийская конференция. Сборник докладов. — М.: МАКС Пресс, 2009. - Сентябрь, 21-26. - С. 632.

[6] Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. Учеб. пособие. - 2-е изд. - М.: ФИЗМАТЛИТ, 2005. - С. 368. - ISBN: 59221-0559-0.

[7] Беклемишев Д. В. Курс аналитической геометрии и линейной алгебры: Учеб. для вузов. - 11-е, испр. изд. - М.: ФИЗМАТЛИТ, 2006. - С. 312.

[8] Branden С., Tooze J. Introduction to Protein Structure. — 2nd edition. — New York: Garland Publishing, Inc., 1999. - P. 410.

[9] Rost B. Protein secondary structure prediction continues to rise // Journal of Structural Biology. - 2001. - May. - V. 134, no. 2-3. - P. 204-218.

[10] P. Yoo, Zhou В., Zomaya A. Machine learning techniques for protein secondary structure prediction: An overview and evaluation // Current Bioinformatics. — 2008. - May. - V. 3, no. 2. - P. 74-86.

[11] Critical assessment of the protein structure prediction, protein structure prediction center. — 2011.

[12] Predictions without templates: new folds, secondary structure, and contacts in casp5 / P. Aloy, A. Stark, C. Hadley, R. Russell // Proteins. - 2003. - V. 53, no. 6. - P. 436-456.

[13] Torshin I.Y. Bioinformatics in the Post-Genomic Era: The Role of Biophysics. - New York: Nova Biomedical Books, 2007. - ISBN: 1-60021-048.

[14] Superconductivity magnetization modeling / NIST. — Executor: L. Bennett, L. Swartzendruber, H. Brown: NIST, 1994.

[15] Tibshirani Robert. Regression shinkage and selection via the lasso // Journal of the Royal Statistics Society. Series B(Methodological). - 1996. — V. 58, no. 1. - P. 267-288.

[16] Duin R., Pekalska E., de Ribber D.i. Relational discriminant analysis // Pattern Recognition Letters. - 1999. - V. 20. - P. 1175-1181.

[17] Mottl V., Sulimova V., Tatarchuk A. Multy-kernel approach to on-line signature verification // Proceedings of the Eighth IASTED International Conference on Signal and Image Processing. — Honolulu, Hawaii, USA, 2006. — August, 14-16. - P. 448-453.

[18] Vapnik V. Statistical Learning Theory. - John-Wiley & Sons Inc., 1998. -P. 736.

[19] Mercer T. Functions of positive and negative type and their connection with the theory of integral equations. — Trans. London: Philos. Soc., 1999. — P. 416.

[20] Bishop C., Tipping M. Variational relevance vector machines // Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence. — Morgan Kaufmann, 2000. - P. 46-53.

[21] Wang L., Zhu J., Zou H. The doubly regularized support vector machine // Sta-tistica Sinicia. - 2006. - V. 16. - P. 589-615.

[22] Boyd S., Vandenberghe L. Convex Optimization. — Cambridge: Cambridge University Press, 2004.

[23] Sequential minimal optimization: A fast algorithm for training support vector machines / Microsoft Research. — Executor: John Piatt: Microsoft Research, 1998. - MSR-TR-98-14.

[24] Osuna Edgar, Freund Robert, Girosi Federico. An improved training algorithm for support vector machines // Proceedings of the 1997 IEEE Workshop (1997). - IEEE, 1997. - P. 276-285.

[25] Zanni Luca, Serafmi Thomas, Zanghirati Gaetano. Parallel software for training large scale support vector machines on multiprocessor systems. // Journal of Machine Learning Research. - 2006. - V. 7. - P. 1467-1492.

[26] Psvm: Parallelizing support vector machines on distributed computers / Edward Y. Chang, Kaihua Zhu, Hao Wang et al. // NIPS. - 2007. - Software available at http : / /code. google. com/p/psvm.

[27] A feasible bfgs interior point algorithm for solving convex minimization problems / Paul Armand, Jean Charles Gilbert, Sophie Jan-Jégou et al. // SIAM Journal on Optimization. - 2000. - V. 11. - P. 200.

[28] Tibshirani Robert. Regression Shrinkage and Selection Via the Lasso // Journal of the Royal Statistical Society, Series B. - 1994. - V. 58. - P. 267-288.

[29] Dereniowski Dariusz, Kubale Marek. Cholesky factorization of matrices in parallel and ranking of graphs // 5th International Conference on Parallel Processing and Applied Mathematics. Lecture Notes on Computer Science 3019. — Springer-Verlag, 2004. - P. 985—992.

[30] Strassen Volker. Gaussian elimination is not optimal // Numerische Mathematik. - 1969. - V. 13, no. 4. - P. 354-356.

[31] Coppersmith Don, Winograd Shmuel. Matrix multiplication via arithmetic progressions // Journal of Symbolic Computation. — 1990. — V. 9, no. 3. — P. 251-280.

[32] Williams Virginia Vassilevska. Breaking the Coppersmith-Winograd barrier. Unpublished manuscript. — 2011.

[33] GPU Memory Transfer. - 2013.

[34] OpenCL: The open standard for parallel programming of heterogeneous systems. - 2008.

[35] Bernstein Dennis S. Matrix Mathematics: Theory, Facts, and Formulas (Second Edition). — 41 William Street, Princeton, New Jersey 08540: Princeton University Press, 2009. - P. 979. - ISBN: 978-0-691-13287-7.

[36] Meyer Carl D. Matrix Analysis and Applied Linear Algebra. — 2000. — P. 514. - ISBN: 978-0-89871-454-8.

[37] OpenCL Accelerated Cholesky Factorization. — 2011.

[38] Salkuyeh Davod Khojasteh. Generalized Jacobi and Gauss-Seidel Methods for Solving Linear System of Equations // NUMERICAL MATHEMATICS, A Journal of Chinese Universities (English Series). — 2007. — V. 16, no. 2. — P. 164-170.

[39] Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition / R. Barrett, M. Berry, T. F. Chan et al. - Philadelphia, PA: SIAM, 1994.

[40] Design Patterns: Elements of Reusable Object-Oriented Software / Erich Gamma, Richard Helm, Ralph Johnson, Vlissides John. — USA: Addison-Wesley, 1994. - P. 395. - ISBN: 0-201-63361-2.

[41] NVIDIA OpenCL Programming Guide Version 2.3. - 2009.

[42] Ni Y., Niranjan M. Exploiting long-range dependencies in protein beta-sheet secondary structure prediction // Proceedings of the 5th IAPR International Conference on Pattern Recognition in Bioinformatics. — Nijmegen, the Netherlands, 2010. - September, 22-24. - P. 349-357.

[43] Dayhoff M., Schwarts R., Orcutt B. A model of evolutionary change in proteins // Atlas of Protein Sequences. - 1978. - V. 5. - P. 345-352.