Обработка символьных последовательностей методами машинного обучения на основе дифференцируемого выравнивания тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Офицеров Евгений Петрович

• Офицеров Евгений Петрович
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Офицеров Евгений Петрович

Введение

Глава 1. Модель дифференцируемого редакционного

расстояния для поиска строковой медианы

1.1 Задача поиска строковой медианы

1.1.1 Расстояние Левенштейна

1.1.2 Выравнивание последовательностей

1.2 Гладкая аппроксимация расстояния Левенштейна

1.2.1 Матричное представление строк

1.2.2 Дифференцируемое редакционное расстояние

1.2.3 Рекуррентные формулы для расчета ДРР

1.2.4 Рекуррентные формулы для расчета градиента ДРР

1.2.5 Валидация ДРР на синтетических данных

1.3 Численный метод приближенного поиска строковой

медианы при помощи ДРР

1.3.1 Стохастический градиентный спуск

1.3.2 Сравнение с жадным алгоритмом

Глава 2. Классификация строк на основе коротких

подпоследовательностей

2.1 Задача классификации строк на основе мотивов

2.1.1 Постановка задачи

2.1.2 Замечания

2.2 Примеры строковых классификаторов

2.2.1 Линейный классификатор на основе метрики

Смита Ватермана

2.2.2 Классификатор на основе сверточных нейронных сетей

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

и последовательности

2.3.1 Рекуррентные формулы для расчета ДМ С

2.3.2 Расчет производных ДМС

Стр.

2.4 Классификация последовательностей на основе ДМС

2.4.1 Модель слоя поиска мотивов

2.4.2 Модель позиционного классификатора

2.4.3 Позиционный слой поиска мотивов

2.5 Интерпретация моделей на основе ДМС

2.5.1 Определение мотивов, влияющих на выбор класса

2.5.2 Визуализация вероятностной матрицы мотива

2.5.3 Карты выравнивания и их визуализация

Глава 3. Применение дифференцируемого выравнивания в

задачах машинного обучения

3.1 Кластеризация строковых данных методом К-средних

3.1.1 Кластеризация синтетических данных

3.1.2 Кластеризация репертуара Т-клеточных рецепторов

3.2 Классификация последовательностей на основе мотивов

3.2.1 Классификация синтетических наборов последовательностей

3.2.2 Предсказание связывания пептидов и молекул МНС

Глава 4. Программная реализация

4.1 Архитектура комплекса программ

4.1.1 Общая структура комплекса

4.1.2 Интерфейс библиотеки Chaîner

4.2 Модуль Chaîner Edit Distance

4.2.1 Расчет ДРР с использованием CUDA

4.2.2 Интерфейс модуля

4.3 Модуль Chainer Motif

4.3.1 Расчет ДМС с использованием CUDA

4.3.2 Интерфейс модуля

Заключение

Список сокращений и условных обозначений

Список литературы

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

Введение

Актуальность темы исследования. Во многих прикладных задачах возникает необходимость обработки больших наборов символьных последовательностей переменной длины методами машинного обучения. Например, многие вопросы прикладной биоинформатики сводятся к задачам классификации, регрессии и кластеризации на множествах строк. Решению подобных проблем посвящено множество исследований. В качестве примера можно привести работу X. Сайго и Д. Верта, Н. Уэда и Т. Акутсу 2004 года [1], в которой метод опорных векторов в сочетании со строковым ядром на основе локального выравнивания используется для поиска гомологичных участков белковых последовательностей. Также в последнее время большое применение в биоинформатике получили алгоритмы на основе глубокого обучения. Подробный обзор таких исследований дан М. Вайнбергом, Д. Мерико, А. Делонгом и Б. Д. Фрейем в работе, опубликованной в 2018 году [2] в журнале Nature Biotechnology.

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

где С - алфавит, С* - множество строк над алфавитом С произвольной конечной длины, И С С* — конечный набор строк, ЕБ(а,Ь) — редакционное расстояние Левенштейна, которое определяется как минимальное количество вставок, замен и удалений одного символа, необходимых чтобы преобразовать строку а в строку Ь.

Впервые функция ЕБ была предложена в 1965 году В. И. Левенштей-ном для случая бинарного алфавита [3]. Впоследствии в 1974 году Р. Вагнер и М. Фишер обобщили метрику Левенштейна на случай произвольного алфавита, а также предложили полиномиальный алгоритм динамического программирования для ее вычисления [4]. Редакционное расстояние

(В.1)

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

Задача поиска строковой медианы (В.1) играет ключевую роль во многих приложениях, в том числе в машинном обучении. Например в работах [5] и [6] описываются алгоритмы кластеризации и классификации символьных последовательностей, в основе которых лежит поиск строковой медианы.

В работе Ц. Хигуэра 2000 года [7] было доказано, что проблема (В.1) является МР-сложной. В 1997 году [8] Ф. Касакуберта и М. Антонио предложили жадный алгоритм, позволяющий находить приближенное решение задачи поиска строковой медианы за полиномиальное время. Идея данного метода состоит в последовательном добавлении в конец текущего приближения медианы одиночных символов, так чтобы значение целевой функции в задаче (В.1) уменьшалось. Процесс начинается с пустой строки и останавливается, когда при добавлении очередного символа целевая функция начинает у в ел и ч и в ат ься.

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

Проблема классификации на основе мотивов весьма актуальна для биоинформатики. Ранее в работе 2005 года [9] К. Ф. Бликас, И. Л. Димит-риос и Аристидис предложили использовать для её решения сверточную нейронную сеть [10]. Недостатком такой модели является тот факт, что получаемый классификатор не учитывает возможные разрывы в мотиве. Впоследствии подход на основе нейронных сетей развивался в работах [11;

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

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

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

Решены следующие задачи:

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

2. На основе теоремы достижимости разработана модель гладкой аппроксимации расстояния Левенштейна, называемая дифференцируемым редакционным расстоянием (ДРР), и найдены рекуррентные формулы для эффективного вычисления ее значений и градиента.

3. Предложен эффективный численный метод для приближенного поиска строковой медианы.

4. Разработана модель дифференцируемой меры схожести мотива (короткой подпоследовательности) и последовательности (ДМС), а также модель классификатора последовательностей на основе этой меры.

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

6. Разработано обобщение алгоритма кластеризации К-средних для строковых данных с поиском медианы при помощи ДРР. Предложенный алгоритм исследован на синтетических данных, а также на примере репертуара Т-клеточных рецепторов.

7. Предложенная модель нейронной сети валидирована на синтетических данных, а также применена задаче предсказания связывания пептидов и молекул МНС второго класса.

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

Научная новизна. Новыми является предложенная модель дифференцируемого редакционного расстояния вместе с рекуррентными формулами для ее расчета и численный метод для поиска строковой медианы при помощи ДРР. Также новыми являются: предложенная модель дифференцируемой меры схожести мотива и последовательности, архитектуры нейронных сетей на основе ДМС, обобщение алгоритма К-средних для строковых данных с поиском медианы при помощи ДРР.

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

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

Основные положения, выносимые на защиту:

1. Параметрическая модель дифференцируемого редакционного расстояния (ДРР), аппроксимирующая расстояние Левенштейна и в пределе совпадающая с ним; численный метод расчета ДРР и его градиента на основе выведенных рекуррентных формул.

2. Модель дифференцируемой меры схожести мотива и последовательности (ДМС), учитывающая возможные вставки символов; численный метод для расчета ДМС на основе полученных рекуррентных формул.

3. Эффективный численный метод приближенного поиска строковой медианы при помощи ДРР за полиномиальное время.

4. Численный метод кластеризации символьных последовательностей на базе алгоритма К-средних с поиском медианы при помощи ДРР.

5. Модель слоя нейронной сети для решения задачи классификации строк на основе ДМС и ее обоснование.

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

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

Апробация работы. Основные результаты работы докладывались на:

— пятом Европейском конгрессе по иммунологии (Амстердам, Нидерланды, 2 5 сентября 2018);

— международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2019» (Москва, МГУ имени М. В. Ломоносова, 8-12 апреля, 2019);

— XVI международной конференции «Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложения и проблемы истории», посвященной 80-летию со дня рождения профессора Мишеля Деза (Тула, ТГПУ им. Л. Н. Толстого, 13-18 мая, 2019).

Публикации. Основные результаты по теме диссертации изложены в 12 печатных изданиях, 5 из которых изданы в журналах, рекомендованных ВАК, 7 в тезисах докладов. Также 1 работа размещена на сервисе препринтов arXive.org. Получено свидетельство о государственной регистрации программы для ЭВМ № 2019615354.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения. Полный объём диссертации составляет 93 страницы, включая 13 рисунков и 8 таблиц. Список литературы содержит 76 наименований.

Глава 1. Модель дифференцируемого редакционного расстояния для поиска строковой медианы

В данной главе предлагается математическая модель гладкой аппроксимации расстояния Левенштейна, называемая дифференцируемым редакционным расстоянием (ДРР), которая позволяет решить задачу приближенного поиска строковой медианы с использованием численных методов оптимизации первого порядка (применяется стохастический градиентный спуск). Приводится теоретическое обоснование ДРР, а также предлагается эффективный способ расчета значений и градиента ДРР на основе рекуррентных формул. Результаты данной главы отражены в публикациях автора [14; 15].

1.1 Задача поиска строковой медианы 1.1.1 Расстояние Левенштейна

Пусть С = {дх,... ,дп} — конечное множество различных символов -алфавит, п = |С|, С* — пространство всевозможных последовательностей символов или строк х = х(1)х(2)... х(Ь) над С произвольной длины Ь = |ж| ^ 0.

Как известно, естественной метрикой в С* является редакционное расстояние Левенштейна Е^(хх,х2) [16]. Для двоичного алфавита она была введена В.И. Левенштейном [3]. Данная метрика определяется как минимальное количество вставок, замен и удалений символов, необходимых для преобразования одной строки в другую. Для ее эффективного вычисления используется алгоритм динамического программирования Вагнера Фишера [4].

Пусть хх и х2 две строки в пространстве С* с длинами Ьх ж Ь2 соответственно. Для вычисления Е^(хх,х2) используется вспомогательная матрица

8(г,]) = ЕБ(:п(1: 1),х2(1: 3)), г = ТД, 3 = 1^2,

где Х\(1 : %) = Х\(1)... Х\(г), х2(1 : ]) = х2(1)... х2(]) — префиксы строк Х\ и х2 длины г и ] соответственно. Для вычисления значений Ь(г,]) в алго-

и

ритме Вагнера Фишера используется следующая рекуррентные формула:

ЕБ(Ж1,Ж2) = Ъ(Ь\,Ь2),

где

и

6(г,0) = г, 6(0,; )= 3,

Ь(ч) = ш1п{6(г-1,^ )+!,Ь(г,з— 1)+1,Ь(г—1,3-1)+0}, 6 =

0, Ж1(г) = Х2(з) 1 Ж1(^)= Ж2(; )

Данная формула позволяет эффективно вычислять редакционное расстояние за полиномиальное время 0(Ь1Ь2). Благодаря этому данное расстояние широко применяется в разнообразных задачах на строковых данных, в том числе машинного обучения.

Расстояние Левенштейна удовлетворяет всем аксиомам метрики (см. [16]). Также для него справедливы следующие неравенства:

|^1| — |ж2|| ^ ЕБ(ж1,ж2) ^ шах{|ж1|,|ж2|}.

(1.1)

Существенной проблемой, возникающей при работе со строками, является тот факт, что редакционное расстояние является дискретной функцией, к которой неприменимы эффективные методы гладкой оптимизации. Как следствие, многие базовые задачи оптимизации, содержащие метрику Левенштейна, становятся крайне сложными. В качестве важного примера можно привести упомянутую во введении проблему поиска строковой медианы, которая сводится к следующей проблеме дискретной оптимизации:

т(Б) = а^штУ^ЕБ(а,6). (1.2)

. /О * ' ■

абС*

ЪеВ

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

Предлагаемый алгоритм на основе ДРР решает данные проблемы. В его основе лежит понятие дифференцируемого выравнивания последовательностей.

1.1.2 Выравнивание последовательностей

Редакционное расстояние между двумя последовательностями также может быть определено с использованием термина выравнивание последовательностей [16]. Глобальным выравниваем двух строк называется вставка в строки пробелов (в том числе и на их концах) таким образом, чтобы каждый г-й символ или пробел первой строки соответствовал г-му символу или пробелу второй строки (пары пробел пробел не допускаются).

Приведем пример выравнивания для двух строк х\ = аЬсс!е и х2 = ааЬсс:

а Ь с с1 е .

- 1 (1-3)

а а □ с с

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

Отметим, что помимо редакционного расстояния существуют и другие функции, позволяющие оценить «качество» выравнивания, например локальная оценка выравнивания SW по алгоритму Смита-Ватермана [17], которая потребуется в разделе 2.2). Большинство таких метрик построено на выборе выравнивания с наилучшей оценкой среди всевозможных выравниваний двух строк, где соответствующий максимум (минимум) вычисляется с помощью алгоритма динамического программирования, подобного алгоритму Вагнера Фишера. Получаемые таким образом метрики являются дискретными функциями, которые как ранее упоминалось, трудно применять во многих прикладных задачах.

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

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

Определение 1. Соответствием последовательностей Х',Х2 Е G* называется произвольная пара (x'1lx,2) подпоследовательностей равной длины

К! = 141 =

х!' = X1(i'i) . . . X\(i'i) с Х\, х2 = Х2 (i'1)... х2 (i") с х2.

Здесь I называется длиной соответствия.

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

Утверждение 1. Редакционное расстояние Левенштейна ,между строками Х\ и х2 длины L' и L2 соответственно может быть рассчитано по формуле

ED(zi,z2) = min {dH(х'ъх'') + (Li - I) + (L2 — I)} , (1.4)

где минимум берется по всем, соответствиям (х'1}х2), I = | = !х2!, dн - расстояние Хеминга (число не совпадающих символов вх' и х2).

Действительно, в выражении (1.4) величина ^н(xi,x2) равна числу замен соответствующего предписания, а слагаемые L' — I и L2 — I — числам вставок и удалений.

Для примера (1.3) имеем соответствие (abed,abcc) длины 4, число замен dH(abcd,abcс) = 1 (требуется заменить 4-й символ), число вставок отвечает парам пробел символ и равно 1, число удалений отвечает парам символ пробел и также равно 1. Таким образом, длина предписания равна 3.

1.2 Гладкая аппроксимация расстояния Левенштейна 1.2.1 Матричное представление строк

Основная идея дифференцируемого выравнивания состоит в представлении последовательностей, (позиционно) вероятностными матрицами (ВМ) X = (X(%,])) Е [0,1]Ьхте, строки которых X({) являются вероятностными (или стохастическими) векторами, т.е. X(г,]) = 1, г = 1,Ь, Ь ^ 0 (Ь = 0 отвечает пустой матрице 0). Множество ВМ обозначим через Уп.

Такой подход не является новым и ранее описан, например, в работе [18]. Отметим, что в данном случае термин «вероятностный» означает формальное соответствие строк матрицы требованию X(г,]) = 1,

X(',\) Е [0,1]. В этом случае строкаХ(%) может пониматься как дискретное распределение па множестве символов алфавита С) которое характеризует г-ю позицию последовательности х. Такая интерпретация строк матрицы X в дальнейшем используется в задачах, связанных с визуализацией (см. раздел 2.5). Для поиска медианы вероятностная интерпретация не столь важна, однако термин «вероятностная матрица» для удобства сохраняется.

Очевидно, что каждой последовательности х = х(1).. .х(Ь) над алфавитом С однозначно соответствует бинарная ВМ вида

1 х(ъ) = д3

X ) = { , г = 1,L, 2 = 1,п.

0, х(г) = д3

Ясно, что Уп,ъ С Уп. Кроме того, множество Уп,ъ биективно соответствует пространству последовательностей С*. Этот факт позволяет не делать различия между строками и их представлениями в виде бинарных ВМ.

Утверждение 1 легко переносится на представления строк в виде бинарных ВМ. Также как и в случае последовательностей будем пользоваться обозначениями X = X(1).. .X(V) и Ь = |Хгде X(%) — строки матрицы X. Через

п

11*1« - Х2(1)Ь = ^ ) - Х2(1,,3 )|

3=1

обозначим 1^-норму между вектор-строками Х1(г) и Х2(г).

Утверждение 2. Пусть Х1,Х2 Е Ущь — матричные представления строк х1,х2 Е С*, Ь1 = |Х^7 Ь2 = |Х21. Тогда,

ЕБ(ХЬХ2) = шш{1 ||Х1 - Х^|1 + (¿1 - /) + (¿2 - о} . (1.5)

Здесь минимум берется по всем, (матричным) соответствиям (Х1,Х''); I = |ХЦ = |Х''|; т. е. подматрицам вида Х1 = Х1 (¿1) ...Х1(^)7 Х'' =

Х (¡7) ...Х (■г"2

||Х -Х2||, = ||х;(а.) -Х2(а)||ь (1.6)

а=1

г^е Х1(а)=Х1(г/а^Х?(а) = Х2(^).

Доказательство. Для доказательства утверждения достаточно показать, что ||Х1 - Х'' |1 = 2(1н (хХ1,хХ2). Справедливость этого легко выводится из следующего равенства для бинарных вероятностных векторов:

„ ,„ м, Х1(а)=Х';(а),

||Х1(а) -Х£(а)||1 = ( ' 1( ) ( ^

(2, Х1(а) = Х''(а).

Утверждение 2 позволяет естественным образом определить функцию ЕБ(Х1,Х2) для произвольных вещественных ВМ Х1,Х2 Е Уп. По-прежнему, ЕБ(Х1,Х2) вычисляется по выравниваниям последовательностей Х1(1)... Х1(Ь1) и Х2(1)... Х2(Ь2) заданием соответствий (Х1,Х2'). Только в отличии от бинарного случая величина 2 ||Х1 - Х'211 будет принимать вещественные значения. Кроме того, эта функция является почти

Х1 Х2

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

Утверждение 3. Функция, ЕБ(Х1,Х2) удовлетворяет неравенствам,

Х1 , Х2 Е Уп

Доказательство. Пусть для определенности |Х1| ^ |Х2|. Соответствием

( Х1 , Х2 ) | Х1 | = | Х2 |

ЕБ(Х1,Х2) ^ 1 ||Х1 -Х21|1 + |Х1| - |Х1| + |Х21 - |Х2'| ^

^ 2(|Х1|1 + ||Х21|1) + |Х2|-|Х21.

Имеем

|*l| п Ш

Mi = ЕЕ ]| = E1 = i^ii,

i=1 j=1 i=1

аналогично H^'Hi. = |Х2'|. Поэтому

ED(Xi,X2) ^ iX'H + |X21 - 1ХЩ = |X2|.

С другой етороны, для любых соответствий

2 ||х; - x2'||i + |Xi| - |ХЦ + |Х2| - |Х,?| £ |Xi| + |Х2| - 2|ХЦ = |Х2| - |Xi|,

откуда следует, что ED(Xi,X2) £ |Х2| - |Xi| и, аналогично, ED(Xi,X2) £ |-|^2|. □

Нам потребуется операция округления round(X): Vn ^ Уп,ъ- Оно определяется построчно: round(X) = round(Xi)... round(X(L)). Округлением вектор-строки X (г) называется бинарная строк а длины п, в которой максимальный из элементов X(i,j) заменяется единицей (если таких несколько, то, например, первый), а остальные X(i,j) — нулями. Несложно показать, что округление отвечает наилучшему приближению вектора X(г) по ^-метрике вероятностным бинарным вектором.

Определение 2. Задача поиска, строковой медианы М(D) для конечного набора строк D по метр икс ED может быть сформулирована в следующем матричном виде:

к

S (D,U) = min V ED(Dk ,Х), М (D) = arg 5 (D,U), (1.7) k=1

где U = Vn£ и D = {Dk}f=1 С Vn,b — набор бинарных BM, представляющих строки.

Докажем следующее полезное утверждение.

Утверждение 4. Для длины медианы М справедлива следующая оценка:

|М| < 2Ld, (1.8)

где Ld = ^ X^i. | _ средняя длина строк из мн ожества D.

Доказательство. Обозначим за Г(X) = ЕЕ(_Ок,Х) минимизируе-

мую функцию. Для пустой матрицы имеем Г(0) = ^^ 1 |-ОкЕсли

|М| > k=i |Dk| то в силу (1.1) находим:

к

F(М) llMHDkll ^

k=i

к

Dim i-D i)

k=i

( К IM l - £ lDk |)

k=1

^ F(0).

Поэтому M не может быть медианой и (1.8) верно. □

Минимум в этой дискретной задаче (1.7) достигается на некоторой бинарной ВМ В Е длина которой удовлетворяет условию (1.8). Следующая основная теорема показывает, что минимум не изменится, если его искать на объемлющем непрерывном пространстве Vn.

Теорема 1. Имеем

S (D,Vn,b) = S (D,Vn).

Кроме того, еслиХ* Е Vn — решение задачи S(D,Vn), то round(X*) Е Vn,b также решение S(D,Vn), а, значит, и решение S(D,Vn,b)•

Из этой теоремы следует, что медиана М(D) = round(X*).

Доказательство. Обозначим за VnL и V^ соответствующие подмножества Vn и Vn^i содержащие только матрицы длины L. В силу утверждений (3) и (4) достаточно рассматривать только L ^ 2LD, где Lp = щ |Dk| -

D

S(D,Vn) = min S(D,VnL). (1.9)

Теперь достаточно доказать утверждение теоремы на множествах и

п,о

Пусть

(X) = ^ ЕБ(Д,,Х), X Е^, к=1

тохда

' ^, и

Fd(X) = V min Ц||Dk - Xk'Hi + |Dk| - |Dk| + L - |Xf| 1 , 7 >^fc')E"(DfcД)\211 k k 111 1 k 1 1 k 1 1 k ]y

где Q(Dk,X) — множество всех соответствий для ВМ Dk и X или, что эквивалентно, их индексов (г'к, г'к) = (г'к(1), г'к(1))... (г'к(lk), i'k(^))'■

D'k = Dk(гк(1))... Dk(ik(lк)) = Dk(гк),

Xk = X (i к (1)) ...X (i к (I к )) = X (i к).

Поскольку все Q(Dk,X) представляют собой конечные множества, то можно записать:

Fd(X) = mmЕ ЦIlDk(4) - X(i'í)||i + \Dk| + L - 2lk\ , (1.10) k=i ^ '

где M С Q(D1,X) х ... х Q(Dк,X) — множество всевозможных наборов

X D

Сумму в (1.10) можно переписать в виде:

к -1

1 = £ П |Dkй) - Xdk)l|i + D| + L - 2lk\ =

к =i

к 1 к к

Е 2 11 Dk (ik) - X (ik )||i + Y, \Dk | +KL - 2 Y lk.

k=i k=i k=i

Далее имеем

к 1 к 1к 1

Е 2 "В &) -х &= ЕЕ 2 № -х & У))"1-к=1 к=1 3=1

Учтем, что Ик(гкСШ и X(г'к(])) — вектор строки бинарной и произвольной ВМ, т. е. ^=1 В к (г к (Д ^ = 1, ^ ™=1Х ^ к (Д ^ = 1, тогда

п

\Dk(ikU)) -X(гк(Mlli = Е \Dk(Ш, г) -X(гк(j), г)\ =

=i

= ^X «(j), г) + 1 - X (ik (j), го) = 2 - 2X «(j), r0) =

r=ro

= 2 - 2 Dk(ik(j)) • X(ik(j)),

где через «•» обозначено скалярное произведение векторов.

Таким образом

I = ¿\Dk| + KL - 2£ |fe| + ¿ ¿(1 - Dk(4(J)) • X(i¡.(J))) =

k=1 k=1 k=1 j = 1

= Z - E E(X(¿k(j)) -Dk(íkÜ)) + 1),

k=1 =1

Z = Ef=i |Dk | + KL.

Учтем, что X(i'k(j), r) = 1. Тогда

¡ = Z - £ ¿(X(ik(j)) • (Dk(4ü)) + и),

k=1 j=1

где 1n = (1,... 1) — вектор из n единиц. Если для i = 0, L, j = 0,n положить

n ,Dk dk W¿) + 1, * = 4 W, ^ 1, lp,

Dк,г'k,г>> U) = ,

0, иначе,

X L L

j = ^ - EEX « • D м k¿ k w = ^ - Ex « • N^' «,

к=1 i=1 i=l

где Ní^ín (i) = Dk,i' i" (¿) — целочисленные векторы. Тогда выражение

(1.10) можно переписать в следующем виде:

jz - EX « -Ní>,í ' (г) j

Fd (X) = min { Z - > ^X (i) • Nit¿' (г^ =

(г ',г")GM

(г) • N>¿'«} .

= Z - mа П^Х(г) •Ni,,i'(г^ . (1.11)

Из соотношения (1.11) следует, что функция Fd (Х) является выпуклой кусочно-линейной функцией (см. [19], пример 3.5). Также из (1.11) вытекает, что

S (DVL) = min Fd (Х) = min ... min Fd (Х).

X eVnL X (1) X (L)

Поскольку Fd(Х) является выпуклой (вниз) функцией, каждый минимум достигается в некоторой крайней точке (бинарном векторе) Х*(г) Е

В общем случае минимум может достигаться в выпуклой комбинации крайних точек, т. е. Х*(ь) = ^Уа Е Е [0,1], = 1 1 ^ т ^ п- Легко видеть, что в этом случае округление вектора гоип^Х*(^)) совпадет с одним из У8 и также является решением. Следовательно, гоип^Х*) — решение $(В,Упь), а, значит, и $(В,У^Ь). Теорема доказана. □

1.2.2 Дифференцируемое редакционное расстояние

Приведенная выше теорема позволяет решать дискретную задачу оптимизации (1.7) на множестве произвольных вероятностных матриц. Однако функция ED(Xi,X2) по-прежнему определяется через не гладкую операцию минимума. Чтобы использовать при решении задачи (1.7) эффективные численные методы оптимизации первого порядка в диссертации предлагается модель гладкой аппроксимации расстояния Левенштейна, называемая дифференцируемым редакционным расстоянием (ДРР). Для построения ДРР, предлагается заменить минимум в выражении (1.5) на экспоненциально-взвешенную сумму, в машинном обучении называемую гладким минимумом soft min (рис. 1.1). Для конечного множества вещественных чисел D операция soft min определяется как

х етх

softmin(D; т) = xED-,

v ' ' ^тх '

xed

где т < 0 — параметр аппроксимации (в дальнейшем для краткости может опускаться). Известно, что softmin( D; т) стремится к minD [20]. Действительно, нетрудно показать, что

min D < soft min (D; т) < minD + С етА, (1.12)

где С = \D\(mean D — minD) и А = minx=x«eD \х' — х"\. Отсюда следует, что гладкий минимум стремится к обычному экспоненциально быстро.

Список литературы диссертационного исследования кандидат наук Офицеров Евгений Петрович, 2020 год

Список литературы

1. Protein homology detection using string alignment kernels / H. Saigo [и др.] // Bioinformatics. 2004. Т. 20, № 11. С. 1682 1689.

2. Deep learning in biomedicine / M. Wainberg [и др.] // Nature biotechnology. 2018. T. 36, № 9. C. 829.

3. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов / В. И. Левенштейн // Доклады Академии наук. Т. 163. Российская академия наук. 1965. С. 845 848.

4. Wagner R. A. The string-to-string correction problem / R. A. Wagner, M. J. Fischer // Journal of the ACM (JACM). 1974. T. 21, № 1. C. 168 173.

5. Dinu L. P. Clustering based on median and closest string via rank distance with applications on DNA / L. P. Dinu, R. T. Ionescu // Neural Computing and Applications. 2014. T. 24, № 1. C. 77 84.

6. Martinez-Hinarejos C. D. Use of median string for classification / C. D. Martinez-Hinarejos, A. Juan, F. Casacuberta // Proceedings 15th International Conference on Pattern Recognition. ICPR-2000. T. 2. IEEE. 2000. C. 903 906.

7. Higuera C. de la. Topology of strings: Median string is NP-complete / C. de la Higuera, F. Casacuberta // Theoretical computer science. 2000. T. 230, № 1/2. C. 39 48.

8. Kruzslicz F. Improved greedy algorithm for computing approximate median strings / F. Kruzslicz // Acta Cybernetica. 1999. T. 14, № 2. C. 331 339.

9. Blekas K. Motif-based protein sequence classification using neural networks / K. Blekas, D. I. Fotiadis, A. Likas // Journal of Computational Biology. 2005. T. 12, № 1. C. 64 82.

10. Backpropagation applied to handwritten zip code recognition / Y. LeCun [и др.] // Neural computation. 1989. Т. 1, № 4. C. 541 551.

11. Predicting the sequence specificities of DNA-and RNA-binding proteins by deep learning / B. Alipanahi [и др.] // Nature biotechnology. 2015.

T. 33, № 8. C. 831.

12. Hassanzadeh H. R. DeeperBind: Enhancing prediction of sequence specificities of DNA binding proteins / H. R. Hassanzadeh, M. D. Wang // 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE. 2016. C. 178 183.

13. Deep motif: Visualizing genomic sequence classifications / J. Lanchantin [и др.] // arXiv preprint arXiv:1605.01133. 2016.

14. Горбачев Д. В. Новый подход к поиску строковой медианы и визуализация строковых кластеров / Д. В. Горбачев, Е. П. Офицеров // Чебышевский сборник. 2019. Т. 20, № 2. С. 190 200.

15. Ofiiserov Е. Soft edit distance for diflerentiable comparison of symbolic sequences / E. Ofitserov, V. Tsvetkov, V. Nazarov // arXiv preprint arXiv:1904.12562. 2019.

16. Гасфилд Д. Строки, деревья и последовательности в алгоритмах / Д. Гасфилд. Невский диалект СПб., 2003. С. 269 273.

17. Identification of common molecular subsequences / Т. F. Smith, M. S. Waterman [и др.] // Journal of molecular biology. 1981.

T. 147, № 1. C. 195 197.

18. Leung H. C. Finding exact optimal motifs in matrix representation by partitioning / H. C. Leung, F. Y. Chin // Bioinformatics. 2005.

T. 21, suppl_2. С. И86 ii92.

19. Boyd S. Convex optimization / S. Boyd, L. Vandenberghe. Cambridge university press, 2004.

20. Applications of lp-Norms and their Smooth Approximations for Gradient Based Learning Vector Quantization. / M. Lange [и др.] // ESANN. 2014.

21. Яблонский С. В. Введение в дискретную математику / С. В. Яблонский. Высш. шк., 2010.

22. Ruder S. An overview of gradient descent optimization algorithms / S. Ruder // arXiv preprint arXiv:1609.04747. 2016.

23. Rosen ,J. В. The gradient projection method for nonlinear programming. Part I. Linear constraints / J. B. Rosen // Journal of the society for industrial and applied mathematics. 1960. T. 8, № 1. C. 181 217.

24. Lindemann P. The gilbert-johnson-keerthi distance algorithm / P. Lindemann // Algorithms in Media Informatics. 2009.

25. Cameron S. Enhancing GJK: Computing minimum and penetration distances between convex polyhedra / S. Cameron // Proceedings of international conference on robotics and automation. T. 4. IEEE. 1997. C. 3112 3117.

26. Офицеров E. 77. Классификация последовательностей на основе коротких мотивов / Е. П. Офицеров // Чебышевский сборник. 2018.

Т. 19, № 1. С. 187 199.

27. Bishop С. М. Pattern recognition and machine learning / С. M. Bishop, springer, 2006.

28. Russell S. J. Artificial Intelligence-A Modern Approach (3rd internat. edn.) / S. J. Russell, P. Norvig. Pearson Education, 2010. C. 710 713.

29. Rubinstein R. Y. The cross-entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation and machine learning / R. Y. Rubinstein, D. P. Kroese. Springer Science & Business Media, 2013.

30. The MHC motif viewer: a visualization tool for MHC binding motifs / N. Rapin [и др.] // Current protocols in immunology. 2010. T. 88, № 1. C. 18 17.

31. Use of the Perception algorithm to distinguish translational initiation sites in E. coli / G. D. Stormo [и др.] // Nucleic acids research. 1982. T. 10, № 9. C. 2997 3011.

32. Jacovi A. Understanding «involutional neural networks for text classification / A. Jacovi, O. S. Shalom, Y. Goldberg // arXiv preprint arXiv:1809.08037. 2018.

33. Gers F. A. Learning to forget: Continual prediction with LSTM / F. A. Gers, J. Schmidhuber, F. Cummins. 1999.

34. Empirical evaluation of gated recurrent neural networks on sequence modeling / J. Chung [m /j,p.] // arXiv preprint arXiv:1412.3555. 2014.

35. Attention is all you need / A. Vaswani [m /j,p.] // Advances in neural information processing systems. 2017. C. 5998 6008.

36. Empirical evaluation of gated recurrent neural networks on sequence modeling / J. Chung [m /j,p.] // arXiv preprint arXiv:1412.3555. 2014.

37. Basic local alignment search tool / S. F. Altschul [m /j,p.] // Journal of molecular biology. 1990. T. 215, № 3. C. 403 410.

38. Bohning D. Multinomial logistic regression algorithm / D. Bohning // Annals of the institute of Statistical Mathematics. 1992. T. 44, № 1. C. 197 200.

39. Albert A. On the existence of maximum likelihood estimates in logistic regression models / A. Albert, J. A. Anderson // Biometrika. 1984. T. 71, № 1. C. 1 10.

40. Glorot X. Deep sparse rectifier neural networks / X. Glorot, A. Bordes, Y. Bengio // Proceedings of the fourteenth international conference on artificial intelligence and statistics. 2011. C. 315 323.

41. Clevert D.-A. Fast and accurate deep network learning by exponential linear units (elus) / D.-A. Clevert, T. Unterthiner, S. Hochreiter // arXiv preprint arXiv:1511.07289. 2015.

42. Ioffe S. Batch normalization: Accelerating deep network training by reducing internal covariate shift / S. Ioffe, C. Szegedy // arXiv preprint arXiv:1502.03167. 2015.

43. Basheer I. A. Artificial neural networks: fundamentals, computing, design, and application / I. A. Basheer, M. Hajmeer // Journal of microbiological methods. 2000. T. 43, № 1. C. 3 31.

44. Menard S. Applied logistic regression analysis. T. 106 / S. Menard. Sage, 2002. C. 41 63.

45. Wilkinson L. The history of the cluster heat map / L. Wilkinson, M. Friendly // The American Statistician. 2009. T. 63, № 2. C. 179 184.

46. Lloyd S. Least square quantization in PCM's / S. Lloyd // Bell Telephone Laboratories Paper. 1957.

47. Frey B. J. Clustering by passing messages between data points /

B. J. Frey, D. Dueck // science. 2007. T. 315, № 5814. C. 972 976.

48. Двоенко С. Д. Кластеризация множества, описанного парными расстояниями и близостями между его элементами / С. Д. Двоенко // Сибирский журнал индустриальной математики. 2009. Т. 12, № 1. С. 61 73.

49. Clustal W and Clustal X version 2.0 / M. A. Larkin [и др.] // bioinformatics. 2007. Т. 23, № 21. С. 2947 2948.

50. Ghodsi М. DNACLUST: accurate and efficient clustering of phylogenetic marker genes / M. Ghodsi, B. Liu, M. Pop // BMC bioinformatics. 2011. T. 12, № 1. C. 271.

51. Muthen B. Finite mixture modeling with mixture outcomes using the EM algorithm / B. Muthen, K. Shedden // Biometrics. 1999. T. 55, № 2. C. 463 469.

52. Офицеров E. 77. Кластеризация последовательностей с помощью дифференцируемого редакционного расстояния / Е. П. Офицеров // Материалы Международного молодежного научного форума «ЛОМО-НОСОВ-2019» секция «Биоинженерия и Биоинформатика» подсекция «Биоинформатика» [Электронный ресурс]. 2019.

53. Maaten L. v. d. Visualizing data using t-SNE / L. v. d. Maaten, G. Hinton // Journal of machine learning research. 2008. T. 9, Nov.

C. 2579 2605.

54. Nazarov V. Visualisation of immune receptor sequences via projection into high-dimensional space with Siamese neural networks / V. Nazarov, E. Ofitserov, V. Tsvetkov // Abstracts of the 5th European Congress of Immunology ECI 2018 - Amsterdam, The Netherlands. - 2018. -P. 111.

55. Офицеров E. 77. Статистическая модель периферической селекции Т-клеточных рецепторов / Е. П. Офицеров // Известия Тульского государственного университета. Технические науки. 2017. № 2. С. 138 143.

56. Офицеров Е. П. Глубокая модель селекции Т-клеточных рецепторов / Е. П. Офицеров // Известия Тульского государственного университета. Технические науки. 2017. № 12 2. С. 350 355.

57. Deep learning model for prediction of probability for thymic selection for T-cell receptor sequences / S. Tolstoukhova [et al.] // Proceedings of Moscow Conference on Computational Molecular Biology. - 2017.

58. Tolstoukhova S. Deep learning model of clonal selection for T-cell receptor sequences / S. Tolstoukhova, E. Ofitserov, V. Nazarov // Abstracts of European Conference on Computational Biology. - 2017.

59. Офицеров E. Статистический вывод параметров селекции иммунных рецепторов с помощью алгоритма градиентного спуска с переменным шагом / Е. Офицеров, А. Воеводская, В. Назаров // Новые информационные технологии в автоматизированных системах. 2016.

№ 19. С. 149 155.

60. Antigen-Specific TCR Signatures of Cytomegalovirus Infection / A. Huth [и др.] // The Journal of Immunology. 2019. T. 202, № 3.

C. 979 990.

61. Kingma D. P. Adam: A method for stochastic optimization /

D. P. Kingma, J. Ba // arXiv preprint arXiv:1412.6980. 2014.

62. Ofitserov E. TCR sequence motif based classification of CD4-CD8 cells /

E. Ofitserov, V. Tsvetkov, V. Nazarov // Abstracts of the 5th European Congress of Immunology ECI 2018 - Amsterdam, The Netherlands. -2018. - P. 520.

63. Improved methods for predicting peptide binding affinity to MHC class II molecules / К. K. Jensen [и др.] // Immunology. 2018. Т. 154, № 3. С. 394 406.

64. Nazarov V. Robust prediction of peptide-МНС binding affinity with deep neural networks / V. Nazarov, V. Tsvetkov, E. Ofitserov // Abstracts of the 5th European Congress of Immunology ECI 2018 - Amsterdam, The Netherlands. - 2018. - P. 517.

65. Dropout: a simple way to prevent neural networks from overfitting / N. Srivastava [и др.] // The Journal of Machine Learning Research. 2014. T. 15, № 1. C. 1929 1958.

66. An introduction to ROC analysis // Pattern Recognition Letters. 2006. T. 27, № 8. C. 861 874. ROC Analysis in Pattern Recognition.

67. Офицеров E. П. Программный комплекс для решения задач машинного обучения на строковых данных при помощи дифференцируемого редакционного расстояния / Е. П. Офицеров // Известия Тульского государственного университета. Технические науки. 2017. № 5. С. 370 376.

68. Офицеров Е. П. Программный комплекс для обработки строк методами дифференцируемого выравнивания // Сведетельство о государственной регистрации программы для ЭВМ 2019615354 / Е. П. Офицеров. 2019.

69. Tensorflow: A system for large-scale machine learning / M. Abadi [и др.] // 12th Symposium on Operating Systems Design and Implementation 16). 2016. C. 265 283.

70. Ketkar N. Introduction to pytorch / N. Ketkar // Deep learning with python. Springer, 2017. C. 195 208.

71. Chainer: a next-generation open source framework for deep learning / S. Tokui [и др.] // Proceedings of workshop on machine learning systems (LearningSys) in the twenty-ninth annual conference on neural information processing systems (NIPS). T. 5. 2015. С. 1 6.

72. Nishino R. 0. Y. U. D. CuPy: A NumPy-Compatible Library for NVIDIA GPU Calculations / R. O. Y. U. D. Nishino, S. H. C. Loomis. .

73. cudnn: Efficient primitives for deep learning / S. Chetlur [и др.] // arXiv preprint arXiv: 1410.0759. 2014.

74. Oliphant Т. E. A guide to NumPy. Т. 1 / Т. E. Oliphant. Trelgol Publishing USA, 2006.

75. On automatic differentiation / A. Griewank [и др.] // Mathematical Programming: recent developments and applications. 1989. T. 6, № 6. C. 83 107.

76. Neubig G. On-the-fly operation batching in dynamic computation graphs / G. Neubig, Y. Goldberg, C. Dyer // Advances in Neural Information Processing Systems. 2017. C. 3971 3981.