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

• Бояров Андрей Александрович
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Бояров Андрей Александрович

Введение

Глава 1. Алгоритмы машинного обучения в условиях

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

1.1 Методы кластеризации

1.1.1 Задача кластеризации

1.1.2 Модель смеси гауссовых распределений

1.1.3 Смесь гауссовых распределений с разреженными параметрами

1.1.4 Метод к-средних

1.1.5 Модификации метода к-средних

1.1.6 БЫ алгоритм

1.1.7 Метод распространения близости

1.1.8 Основанная на плотности пространственная кластеризация для приложений с шумами (ЭВБСАК)

1.1.9 Вариационный Байесовский вывод для смеси гауссовых распределений

1.1.10 Оценка качества кластеризации

1.2 Алгоритмы классификации по малому количеству данных

1.2.1 Задача обучения по малому количеству данных

1.2.2 Глубокие нейронные сети

1.2.3 Метрические подходы

1.2.4 Оптимизационные подходы

1.2.5 Рекуррентные подходы

1.3 Стохастическая аппроксимация

Глава 2. Рандомизированные алгоритмы обучения в условиях

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

2.1 Рандомизированный алгоритм кластеризации в условиях

отсутствия разметки данных

Стр.

2.1.1 Кластеризация смеси гауссовых распределений при неизвестных, но ограниченных помехах

2.1.2 Оценивание параметров смеси гауссовых распределений

без учителя при разреженных параметрах

2.2 Рандомизированный подход к обучению классификатора в

условиях малого количества данных

2.2.1 Многозадачное обучение

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

Глава 3. Результаты экспериментов

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

3.1.1 Случай к-средних

3.1.2 Смесь гауссовых распределений

3.1.3 Внешние возмущения

3.1.4 Смесь гауссовых распределений с разреженными параметрами

3.2 Тестирование классификатора в задаче обучения по малому количеству данных

3.3 Верификация авторства средневековых рукописей на арабском языке

3.3.1 Верификация одного автора

3.3.2 Верификация множества авторов

Заключение

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

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

Введение

Актуальность темы. За последние несколько лет стремительное развитие получили различные методы машинного обучения. Среди них глубокие свёрточные нейронные сети [1], рекуррентные нейронные сети [2], логистическая регрессия [3], метод опорных векторов [4], метод k-средних [5] и т.п. Эти алгоритмы широко применяются в распознавании образов, в интеллектуальной обработке текстов, в робототехнике, в управлении беспилотными аппаратами, в рекомендательных системах. Наибольшего прогресса получилось добиться в развитии методов обучения с учителем. Алгоритмы этого семейства основаны на минимизации некоторой функции потерь с помощью градиентных методов. При наличии большого объёма размеченных и «прочищенных» данных такой подход даёт хорошие результаты.

Теоретические исследования, лежащие в основе методов классификации и кластеризации, входящих в семейство методов машинного обучения, и методов распознавания образов, представлены в работах Р. А. Фишера (R. A. Fisher) [6], В. А. Якубовича [7], Я. З. Цыпкина [8; 9], М. А. Ай-зермана [10], В. Н. Фомина [11], В. Н. Вапника и А. Я. Червоненкиса [12], Дж. Хартигана (J. Hartigan) [13], Х. Барлоу (H. Barlow) [14], Л. Кауфмана (L. Kaufman) [15], Б. Т. Поляка [16], А. Л. Фрадкова [17] и др. Глубокие нейронные сети образуют подкласс алгоритмов машинного обучения, называющийся глубоким обучением (deep learning), который в последние годы активно развивается. Он основывается на работах Ф. Розенблатта (F. Rosenblatt) [18], К. Фукунаги (K. Fukunaga) [19], Д. Румельхарта (D. Rumelhart) с соавторами [20], Дж. Хинтона (J. Hinton) [21; 22], Я. ЛеКуна (Y. LeCun) [1; 23; 24], Й. Бенджио (Y. Bengio) [25; 26]. Обзоры современных алгоритмов машинного обучения и распознавания образов даны в работах Т. Хасти (T. Hastie) с соавторами [3], К. Бишопа (K. Bishop) [27], И. Гудфеллоу (I. Goodfellow) с соавторами [28], К. В. Воронцова [29]. Одной из ключевых задач, которая решается большинством алгоритмов машинного обучения, является задача многомерной оптимизации, широко освещённая в фундаментальных исследованиях Б. Т. Поляка [30], С. Бойда (S. Boyd) с соавторами [31], Х. Носедала (J. Nocedal) [32], Ю. Е. Нестерова [33], Л. Боттоу (L. Bottou) [34; 35].

Для успешной работы основных стандартных алгоритмов машинного обучения с учителем необходимы известные параметры моделирования данных, возможность вычисления градиента для оптимизируемой функции потерь (функционала качества) и обучающая выборка как можно большего объёма, данные из которой можно аппроксимировать с помощью нормального распределения [30]. Однако, в реальных условиях эти требования часто бывают не выполнены: во многих случаях даже гипотеза о центрированности данных относительно некоторых центроидов не подтверждается, и бывает невозможно вычисление градиента для функции потерь. Например, данные могут по своей природе иметь разреженную (sparse) структуру (как смесь гауссовых распределений с разреженными параметрами (sparse Gaussian mixture model) [36]). В таких случаях стандартные универсальные методы могут давать смещённую оценку искомых параметров. Для подобных случаев необходимо разрабатывать новые методы, способные работать в таких нестандартных условиях.

Для понижения сложности вычислений или для «обогащения» последовательности наблюдений часто используются рандомизированные алгоритмы. Начало исследованиям применения алгоритмов рандомизации в машинном обучении было положено статьёй М. Вадьясагара (M. Vidyasagar) [37]. Затем эти исследования были продолжены и расширены М. Кампи (M. Campi) [38], О. Н. Граничиным [39; 40], Ю. C. Попковым [41], Б. Т. Поляком и М. В. Хлебниковым [42], Р. Темпо (R. Tempo) с соавторами [43]. Одно из направлений применения рандомизации в машинном обучении — использование поисковых алгоритмов стохастической аппроксимации, описанных в работах О. Н. Гра-ничина [39; 44; 45], Б. Т. Поляка и А. Б. Цыбакова [46], Дж. С. Спалла (J. C. Spall) [47; 48], Х. Кушнера (H. Kushner) и Г. Г. Ина (G. G. Yin) [49], В. С. Боркара (V. S. Borkar) [50], А. В. Назина [51; 52]. Особый интерес представляют алгоритмы стохастической аппроксимации для оптимизации нестационарных функций потерь (изменяющихся со временем), которые представлены в исследованиях А. Т. Вахитова и О. Н. Граничина с соавторами [53—55], Дж. С. Спалла (J. C. Spall) с соавторами [56].

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

ками и т.п.). Каждая новая задача требует сбора и подготовки нового набора данных, что является достаточно трудоёмкой задачей и зачастую требует усилий большого числа людей. Однако, в мире существует (в основном благодаря развитию Интернета, социальных сетей и смартфонов) огромное количество неразмеченных данных. Одной из важнейших задач, связанных с таким типом данных, является задача самообучения и один из её частных случаев — задача кластеризации. Отсутствие заранее известной структуры и разметки данных является источником неопределённостей, для работы с которым необходимо разрабатывать новые подходы. Рандомизированный подход к решению задачи самообучения был предложен в работе О. Н. Граничина и О. А. Измаковой [57].

Другой вид неопределённостей, связанный с обработкой слабо размеченных данных, возникает в задачах обучения и классификации по малому количеству примеров (few-shot learning), которые входят в более широкий круг задач мета-обучения (meta-learning). В таких задачах алгоритму доступен для обучения некоторый набор классов с небольшим количеством размеченных данных. Он должен обучиться по нескольким элементам (например, 1, 5 или 10) на класс с высоким качеством определять этот класс. Кроме того, в процессе эксплуатации алгоритму на вход будут приходить представители новых классов, которых не было в обучающей выборке. Алгоритм должен иметь возможность адаптироваться для работы с этими новыми классами, не теряя при этом в качестве работы на старых классах. Методы этого семейства крайне востребованы, так как необходимость в адаптации к новым классам всего по нескольким примерам возникает во многих прикладных задачах. Поэтому разработка адаптивных алгоритмов, способных работать в условиях таких неопределённостей, является крайне актуальной. Задачи мета-обучения были описаны в работах Ю. Шмид-хубера (J. Schmidhuber) [58], С. Бенджио (S. Bengio) [59], Б. Лэйка (B. Lake) с соавторами [60], М. Андричовица (M. Andrychowicz) с соавторами [61] и развиты в статьях О. Виньялиса (O. Vinyalis) [62], Дж. Снелла (J. Snell) [63], Ч. Финн (C. Finn) с соавторами [64]. Отметим, что сейчас существует лишь небольшое количество прикладных программ, реализующих алгоритмы самообучения и обучения по малому количеству примеров и позволяющих быстро применять их как для данных, полученных путём имитационного моделирования, так и к реальным нестандартным задачам (например, для определения авторства средневековых манускриптов).

Важность и актуальность разработки новых алгоритмов машинного обучения в условиях отсутствия разметки и малого количества данных для развития искусственного интеллекта в Российской Федерации подтверждается в Указе Президента Российской Федерации «О развитии искусственного интеллекта в Российской Федерации», в котором в пункте 5в сформулировано, что «перспективные методы искусственного интеллекта — ... алгоритмы решения задач на основе данных с частичной разметкой и (или) незначительных объёмов данных», в Указе в пункте 30б отмечается, что «фундаментальные научные исследования должны быть направлены на создание принципиально новых научных результатов, в том числе на создание универсального (сильного) искусственного интеллекта, и решение иных задач, ... включая реализацию следующих приоритетов: ... автономное самообучение и развитие адаптивности алгоритмов к новым задачам».

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

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

Для достижения сформулированной цели были поставлены следующие задачи:

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

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

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

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

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

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

Основные результаты, выносимые на защиту:

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

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

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

4. Разработан набор прикладных программ, реализующих алгоритмы из пунктов 1, 2, 3, и демонстрирующих их работоспособность как на смоделированных синтетических примерах, так и в реальных задачах классификации рукописных букв и верификации авторства средневековых арабских манускриптов.

Научная новизна: Все основные научные результаты диссертации являются новыми.

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

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

Апробация работы. Результаты диссертации докладывались на семинарах кафедр системного программирования и теоретической кибернетики математико-механического факультета СПбГУ, семинарах Лаборатории анализа и моделирования социальных процессов СПбГУ, семинарах кафедры математического моделирования и энергетических систем факультета прикладной математики - процессов управления СПбГУ, семинарах «Теория автоматического управления» Лаборатории 7 Института Проблем Управления РАН, на Шестой традиционной всероссийской молодежной летней школе «Управление, информация и оптимизация» (дер. Григорчиково Московской области, Россия, 22-29 июня, 2014) (первое место по результатам конкурса алгоритмов машинного обучения, проводившегося среди участников школы [65]), на международных конференциях 2017 1st International Workshop on Arabic Script Analysis and Recognition (ASAR) (April 3-5, 2017, Nancy, France), 2017 IEEE Conference on Control Technology and Applications (August 27-30, 2017, Kohala Coast, Hawaii, USA).

Результаты диссертации были использованы в работах по грантам РФФИ 16-07-00890 «Рандомизированные алгоритмы в автоматическом управлении и при извлечении знаний», РФФИ 17-51-53053 «Разработка методов получения суперразрешения цифровых моделей поверхности на основе свёрточных нейронных сетей», РНФ 16-19-00057 «Адаптивное управление с прогнозирующими моделями при переменной структуре пространства состояний с приложением к системам сетевого управления движением и автоматизации медицинского оборудования».

Публикации. Основные результаты по теме диссертации изложены в 9 работах [66—74], из них [71] опубликована в издании из списка ВАК, три [69—71] опубликованы в изданиях, индексируемых в базах данных Web of Science и Scopus, [74] — свидетельство на программу для электронных вычислительных машин.

Работы [66; 69—71; 74] написаны в соавторстве. В работах [66; 70; 71] А. А. Боярову принадлежат формулировки и доказательства теорем, результаты экспериментов и имитационного моделирования, соавторам — общая постановка задачи и выбор направления решения. В работе [69] А. А. Бояро-ву принадлежит разработка алгоритма классификации, соавторам — общая постановка задачи и разработка алгоритм предобработки данных. В [74] А. А. Боярову принадлежат разработка алгоритмов классификации и архитектура программного обеспечения, соавторам — общая постановка задачи и разработка алгоритмов предобработки данных.

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

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

В первой главе приводятся описания проблем обучения в условиях отсутствия разметки и по малому количеству данных, а также даётся обзор основных алгоритмов для решения этих задач, сопровождающийся обзором литературы по теме исследования. В разделе 1.1 ставится задача кластеризации в контексте обучения без учителя и рассматриваются стандартные методы, применяемые для решения поставленной задачи. В подразделе 1.1.1 приводится формулировка проблемы кластеризации в виде оптимизационной задачи. В подразделе 1.1.2 рассматривается смесь гауссовых распределений как основная модель для исследуемой проблемы кластеризации. Подраздел 1.1.3 содержит описание модели смеси гауссовых распределений с разреженными параметрами, которая используется, например, для моделирования различных шумов. В подразделах 1.1.4 — 1.1.9 приводятся описания алгоритмов машинного обучения, применяемых для решения сформулированных задач. Рассматриваются алгоритмы как с оценкой ковариационных матриц кластеров, так и без неё. Подраздел 1.1.10 содержит описание критериев оценки качества кластеризации. В

разделе 1.2 описываются задачи обучения по малому количеству размеченных данных и основные подходы, используемые для её решения. В подразделе 1.2.1 ставится проблема классификации по малому количеству размеченных примеров. Подраздел 1.2.2 включает в себя описание глубоких нейронных сетей и основных понятий, связанных с ними. Нейронная сеть является основным видом модели, используемой для решения задачи обучения по малому количеству данных. В следующих подразделах даётся описание методов, входящих в три основные группы алгоритмов классификации по малому количеству примеров: подраздел 1.2.3 представляет метрические подходы, подраздел 1.2.4 — оптимизационные, подраздел 1.2.5 — рекуррентные. В разделе 1.3 содержится описание алгоритмов оценивания неизвестных параметров системы на основе методов стохастической аппроксимации в силу перспективности использования такого подхода для решения задач, поставленных в предыдущих разделах.

Во второй главе формулируются и доказываются основные теоретические результаты диссертационного исследования. В разделе 2.1 рассматривается применение рандомизированного подхода в задаче кластеризации. В подразделе 2.1.1 описывается основной рандомизированный алгоритм стохастической аппроксимации для кластеризации в модели смеси гауссовых распределений. Сформулирована и доказана Теорема 1 о состоятельности оценок центров кластеров и ковариационных матриц, полученных с помощью этого алгоритма. Проведён анализ основных свойств построенного рандомизированного алгоритма. В подразделе 2.1.2 рассматривается случай смеси гауссовых распределений с разреженными параметрами, в котором оригинальные методы кластеризации значительно теряют в качестве работы. Для такой модели данных описывается модификация алгоритма стохастической аппроксимации с рандомизацией на входе для кластеризации, предложенного в предыдущем подразделе. Для оценок параметров, получаемых с помощью описанной модификации, сформулирована и доказана Теорема 2 об их состоятельности. Раздел 2.2 посвящён описанию рандомизированного подхода для обучения в условиях малого количества данных. В подразделе 2.2.1 рассматривается задача многозадачного обучения и для неё формулируется специальная новая функция потерь (функция качества). В подразделе 2.2.2 описывается алгоритм стохастической аппроксимации с рандомизацией на входе для классификации в условиях малого количества примеров, а также формулируется и доказывается Теорема 3 о состоятельности получаемых с помощью этого алгоритма оценок

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

В третьей главе приводятся результаты экспериментов, иллюстрирующие работу предложенных подходов, и их апробации в реальной задаче. В разделе 3.1 описываются результаты, полученные для имитационного моделирования в задаче кластеризации смеси гауссовых распределений. В подразделе 3.1.1 рассматривается случай оценки только центров кластеров и проводится сравнение метода, предложенного в подразделе 2.1.1, со стандартными методами самообучения, используемыми в такой задаче. В подразделе 3.1.2 описывается случай построения оценок центроидов и ковариационных матриц и представляются результаты сравнения алгоритма, предложенного в подразделе 2.1.1, со стандартными аналогами. Подраздел 3.1.3 посвящён экспериментам при наличии аддитивного внешнего шума и их результатам для метода, предложенного в подразделе 2.1.1, и других алгоритмов кластеризации. В подразделе 3.1.4 рассматриваются эксперименты в случае модели смеси гауссовых распределений с разреженными параметрами. Приводятся результаты сравнения метода, представленного в подразделе 2.1.2, со стандартными алгоритмами кластеризации. Раздел 3.2 посвящён результатам тестирования предложенного в подразделе 2.2.2 подхода к обучению классификатора по малому количеству примеров на стандартном наборе данных Омниглот. В разделе 3.3 описывается апробация представленных в разделе 2.2 методов в задаче верификации авторства средневековых арабских манускриптов.

В заключении формулируются основные результаты диссертационного исследования.

Глава 1. Алгоритмы машинного обучения в условиях отсутствия разметки и малого количества данных

Машинное обучение — это область знаний, которая имеет тесную связь со статистическим анализом данных, распознаванием образов, оптимизацией. Под алгоритмом машинного обучения понимается алгоритм, способный учиться на данных. В работе T. Митчелла (T. Mitchell) [75] даётся следующее определение способности учиться: «Говорят, что компьютерная программа учится из опыта E относительно некоторого класса задач T и меры качества P, если её качество на задачах из T, измеренное с помощью P, увеличивается с опытом Е». Опыт Е, класс задач T и мера качества P могут меняться в зависимости от конкретной проблемы.

Методы машинного обучения можно в широком смысле разделить на две категории в зависимости от типа данных, к которым они применяются: обучение с учителем (supervised learning) и обучение без учителя или самообучение (unsupervised learning). Алгоритм обучения с учителем использует данные, для которых есть разметка: каждый пример из данных обладает меткой того класса, к которому он принадлежит. Эти метки затем используются при обучении для получения сигналов о том, как нужно изменить параметры обучаемой модели, чтобы повысить качество классификации. Важно отметить, что в стандартной постановке задачи классификации классы в обучающей (тренировочной) выборке совпадают с классами на тесте. Задача регрессии также решается методами, относящимся к обучению с учителем. В этом случае каждому элементу данных ставится в соответствие некоторое вещественное число, которое используется для изменения параметров обучаемой модели таким образом, чтобы максимально приблизить предсказанное моделью число к истинному, например в среднеквадратическом смысле.

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

только входные данные, никаких внешних дополнительных сигналов для этой задачи нет.

Методы обучения с учителем и без учителя можно разделить следующим образом. В случае задачи самообучения для входного случайного вектора x необходимо построить оценку вероятностного распределения P(x) или некоторых интересующих свойств этого распределения. При обучении с учителем для каждого x доступно число y (метка класса), и алгоритм обучается предсказывать y по x, строя оценку P(y|x).

В отдельную категорию выделяют методы обучения с подкреплением (reinforcement learning), которые обучают последовательность действий в некотором окружении для достижения поставленной цели. Для этого они используют реакцию окружения на действия [76; 77]. Однако, в диссертации внимание сфокусировано на задачах кластеризации и классификации.

Алгоритмы обучения с учителем, особенно при использовании их с глубокими нейронными сетями, способны качественно работать в различных задачах классификации, регрессии и распознавания образов [78—82]. Но для обучения им необходимы большие объёмы размеченных данных. Без них точность этих алгоритмов значительно деградируют. Сбор, подготовка и разметка тренировочных данных под каждую задачу являются крайне трудоёмкими операциями и требуют ручного труда и больших затрат по времени. Для алгоритмов обучения без учителя (и в частности кластеризации), напротив, такая разметка данных не требуется. Стандартные методы классификации не способны быстро и качественно адаптироваться под новые классы, которых не было в обучающей выборке. Это свойство приводит к рассмотрению алгоритмов обучения и классификации по малому количеству примеров (few-shot learning).

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

1.1 Методы кластеризации

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

1.1.1 Задача кластеризации

Методы обучения без учителя направлены на то, чтобы извлечь некоторую полезную информацию о распределении данных без указаний человека, в отличии от методов обучения с учителем, где таким указанием является разметка. Примером такой полезной информации служит разбиение данных на группы похожих по определённому признаку примеров, как в случае задачи кластеризации. В классической постановке целью алгоритмов самообучения является нахождение некоторого «лучшего» представления данных [14]. Под «лучшим» имеется ввиду такое представление, которое сохраняет как можно больше информации о входных данных и является при этом более простым, чем исходное [14; 83; 84]. Суть задачи кластеризации заключается в определении групп во входных данных, которые и будут давать такое «лучшее» представление. Примером этого является использование алгоритмов кластеризации для сжатия (или квантизации) данных [85; 86].

Список литературы диссертационного исследования кандидат наук Бояров Андрей Александрович, 2020 год

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

1. LeCun, Y. Backpropagation applied to handwritten zip code recognition / Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, L. D. Jackel // Neural Computation. - 1989. - Т. 1, № 4. - С. 541-551.

2. Rumelhart, D. E. Learning representations by back-propagating errors / D. E. Rumelhart, G. E. Hinton, R. J. Williams [и др.] // Cognitive Modeling. -. - Т. 5, № 3. - С. 1.

3. Hastie, T. The elements of satistical learning: data mining, inference and prediction / T. Hastie, R. Tibshirani, J. Friedman, J. Franklin // The Mathematical Intelligencer. - 2005. - Т. 27, № 2. - С. 83-85.

4. Cortes, C. Support-vector networks / C. Cortes, V. Vapnik // Machine Learning. - 1995. - Т. 20, № 3. - С. 273-297.

5. Lloyd, S. Least squares quantization in PCM / S. Lloyd // IEEE Transactions on Information Theory. - 1982. - Т. 28, № 2. - С. 129-137.

6. Фишер, Р. А. Статистические методы для исследователей / Р. А. Фишер. - М. : Госстатиздат, 1958. - 267 с.

7. Якубович, В. А. К теории адаптивных систем / В. А. Якубович // Доклады Академии Наук. Т. 182. - Российская академия наук. 1968. -С. 518-521.

8. Цыпкин, Я. З. Адаптация, обучение и самообучение в автоматических системах / Я. З. Цыпкин // Автоматика и телемеханика. - 1966. - № 1. -С. 23-61.

9. Цыпкин, Я. З. Основы теории обучающихся систем / Я. З. Цыпкин. -М. : Наука, 1970. - 252 с.

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

11. Фомин, В. Н. Математическая теория обучаемых опознающих систем / В. Н. Фомин. - Л. : ЛГУ, 1976. - 236 с.

12. Вапник, В. Н. Теория распознавания образов: статистические проблемы обучения / В. Н. Вапник, А. Я. Червоненкис. — М. : Наука, 1974. — 416 с.

13. Hartigan, J. A. Statistical theory in clustering / J. A. Hartigan // Journal of Classification. — 1985. — Т. 2, № 1. — С. 63—76.

14. Barlow, H. B. Unsupervised learning / H. B. Barlow // Neural Computation. — 1989. — Т. 1, № 3. — С. 295—311.

15. Kaufman, L. Finding Groups in Data: an Introduction to Cluster Analysis. Т. 344 / L. Kaufman, P. J. Rousseeuw. — John Wiley & Sons, 2009.

16. Polyak, B. T. Acceleration of stochastic approximation by averaging /

B. T. Polyak, A. B. Juditsky // SIAM Journal on Control and Optimization. — 1992. — Т. 30, № 4. — С. 838—855.

17. Фрадков, А. Л. К задаче синтеза самообучающихся распознающих систем / А. Л. Фрадков // Вестник Ленинградского Университета. — 1972. — № 13. — С. 70—76.

18. Rosenblatt, F. Principles of Neurodynamics / F. Rosenblatt. — New York : Spartan Press, 1962. — 616 p.

19. Fukunaga, K. Introduction to Statistical Pattern Recognition / K. Fukunaga. — 1972.

20. Rumelhart, D. E. Learning representations by back-propagating errors / D. E. Rumelhart, G. E. Hinton, R. J. Williams // Nature. — 1986. — Т. 323, № 6088. — С. 533.

21. Hinton, G. E. Connectionist learning procedures / G. E. Hinton // Machine Learning. — Elsevier, 1990. — С. 555—610.

22. Hinton, G. E. Reducing the dimensionality of data with neural networks / G. E. Hinton, R. R. Salakhutdinov // Science. — 2006. — Т. 313, № 5786. —

C. 504—507.

23. LeCun, Y. Gradient-based learning applied to document recognition / Y. LeCun, L. Bottou, Y. Bengio, P. Haffner [и др.] // Proceedings of the IEEE. — 1998. — Т. 86, № 11. — С. 2278—2324.

24. LeCun, Y. Deep learning / Y. LeCun, Y. Bengio, G. Hinton // Nature. — 2015. — Т. 521, № 7553. — С. 436.

25. Bengio, Y. Learning long-term dependencies with gradient descent is difficult / Y. Bengio, P. Simard, P. Frasconi [и др.] // IEEE Transactions on Neural Networks. - 1994. - Т. 5, № 2. - С. 157-166.

26. Bengio, Y. Representation learning: A review and new perspectives / Y. Bengio, A. Courville, P. Vincent // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2013. - Т. 35, № 8. - С. 1798-1828.

27. Bishop, C. M. Pattern Recognition and Machine Learning / C. M. Bishop. -Springer, 2006.

28. Goodfellow, I. Deep Learning / I. Goodfellow, Y. Bengio, A. Courville. -2016.

29. Воронцов, К. В. Математические методы обучения по прецедентам (теория обучения машин) / К. В. Воронцов. - 2011. - URL: http://www. machinelearning.ru/wiki/images/6/6d/Voron-ML- 1.pdf.

30. Поляк, Б. Т. Введение в оптимизацию / Б. Т. Поляк. - М. : Наука, 1983.

31. Boyd, S. Convex Optimization / S. Boyd, L. Vandenberghe. - Cambridge university press, 2004.

32. Nocedal, J. Numerical Optimization / J. Nocedal, S. Wright. - Springer Science & Business Media, 2006.

33. Нестеров, Ю. Е. Введение в выпуклую оптимизацию / Ю. Е. Нестеров. -М. : МЦНМО, 2010.

34. Bottou, L. The tradeoffs of large scale learning / L. Bottou, O. Bousquet // Advances in Neural Information Processing Systems. - 2008. - С. 161-168.

35. Bottou, L. Online learning and stochastic approximations / L. Bottou // Online Learning in Neural Networks. -. - Т. 17, № 9. - С. 142.

36. Dahlin, J. Sparse Bayesian ARX models with flexible noise distributions / J. Dahlin, A. Wills, B. Ninness // IFAC-PapersOnLine. - 2018. - Т. 51, № 15. - С. 25-30.

37. Vidyasagar, M. Randomized algorithms for robust controller synthesis using statistical learning theory / M. Vidyasagar // Automatica. - 2001. - Т. 37, № 10. - С. 1515-1528.

38. Campi, M. C. Classification with guaranteed probability of error / M. C. Campi // Machine Learning. - 2010. - Т. 80, № 1. - С. 63-84.

39. Граничин, О. Н. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах / О. Н. Граничин, Б. Т. Поляк. -М. : Наука, 2003. - 291 с.

40. Granichin, O. Randomized Algorithms in Automatic Control and Data Mining / O. Granichin, Z. Volkovich, D. Toledano-Kitai. - Springer, 2015. -С. 251.

41. Popkov, Y. S. Randomized machine learning: Statement, solution, applications / Y. S. Popkov, Y. A. Dubnov, A. Y. Popkov // 2016 IEEE 8th International Conference on Intelligent Systems (IS). - IEEE. 2016. -С. 27-39.

42. Поляк, Б. Т. Метод главных компонент: робастные версии / Б. Т. Поляк, М. В. Хлебников // Автоматика и телемеханика. - 2017. - № 3. -С. 130-148.

43. Tempo, R. Randomized Algorithms For Analysis and Control of Uncertain Systems: With Applications / R. Tempo, G. Calafiore, F. Dabbene. -Springer Science & Business Media, 2012. - С. 360.

44. Граничин, О. Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения / О. Н. Граничин // Вестник Ленинградского Университета. Серия 1: Математика, Механика, Астрономия. - 1989. - № 1. - С. 19-21.

45. Граничин, О. Н. Процедура стохастической аппроксимации с возмущением на входе / О. Н. Граничин // Автоматика и телемеханика. - 1992. -№ 2. - С. 97-104.

46. Поляк, Б. Т. Оптимальные порядки точности поисковых алгоритмов стохастической оптимизации / Б. Т. Поляк, А. Б. Цыбаков // Проблемы Передачи Информации. - 1990. - Т. 26, № 2. - С. 45-53.

47. Spall, J. C. Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. Т. 65 / J. C. Spall. - John Wiley & Sons, 2005.

48. Spall, J. C. Identification for systems with binary subsystems / J. C. Spall // IEEE Transactions on Automatic Control. - 2013. - Т. 59, № 1. - С. 3-17.

49. Kushner, H. Stochastic Approximation and Recursive Algorithms and Applications. Т. 35 / H. Kushner, G. G. Yin. - Springer Science & Business Media, 2003.

50. Borkar, V. S. Stochastic Approximation: a Dynamical Systems Viewpoint. Т. 48 / V. S. Borkar. - Cambridge University Press, 2008.

51. Назин, А. В. Пассивная стохастическая аппроксимация / А. В. Назин, Б. Т. Поляк, А. Б. Цыбаков // Автоматика и телемеханика. - 1989. -№ 11. - С. 127-134.

52. Назин, А. В. Асимптотические свойства квазиоптимальных алгоритмов стохастической аппроксимации при неизвестной плотности помех / А. В. Назин // Автоматика и телемеханика. - 1995. - № 10. - С. 70-77.

53. Вахитов, А. Т. Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации / А. Т. Вахитов, О. Н. Граничин, Л. С. Гуревич // Автоматика и телемеханика. -2009. - № 11. - С. 70-79.

54. Granichin, O. Simultaneous perturbation stochastic approximation for tracking under unknown but bounded disturbances / O. Granichin, N. Amelina // IEEE Transactions on Automatic Control. - 2014. - Т. 60, № 6. - С. 1653-1658.

55. Граничин, О. Н. Поисковые алгоритмы стохастической аппроксимации с рандомизацией на входе / О. Н. Граничин // Автоматика и телемеханика. - 2015. - № 5. - С. 43-59.

56. Zhu, J. Tracking capability of stochastic gradient algorithm with constant gain / J. Zhu, J. C. Spall // 2016 IEEE 55th Conference on Decision and Control (CDC). - IEEE. 2016. - С. 4522-4527.

57. Граничин, О. Н. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения / О. Н. Граничин, О. А. Измакова // Автоматика и телемеханика. - 2005. - № 8. - С. 52-63.

58. Schmidhuber, J. Evolutionary Principles in Self-Referential Learning, or on Learning How to Learn: The Meta-Meta-... Hook : дис. ... канд. / Schmidhuber Jiirgen. - Technische Universitat Miinchen, 1987.

59. Bengio, S. On the optimization of a synaptic learning rule / S. Bengio, Y. Bengio, J. Cloutier, J. Gecsei // Preprints Conf. Optimality in Artificial and Biological Neural Networks. - Univ. of Texas. 1992. - С. 6-8.

60. Lake, B. M. Human-level concept learning through probabilistic program induction / B. M. Lake, R. Salakhutdinov, J. B. Tenenbaum // Science. -2015. - Т. 350, № 6266. - С. 1332-1338.

61. Andrychowicz, M. Learning to learn by gradient descent by gradient descent / M. Andrychowicz, M. Denil, S. Gomez, M. W. Hoffman, D. Pfau, T. Schaul,

B. Shillingford, N. De Freitas // Advances in Neural Information Processing Systems. - 2016. - С. 3981-3989.

62. Vinyals, O. Matching networks for one shot learning / O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra [и др.] // Advances in Neural Information Processing Systems. - 2016. - С. 3630-3638.

63. Snell, J. Prototypical networks for few-shot learning / J. Snell, K. Swersky, R. Zemel // Advances in Neural Information Processing Systems. - 2017. -

C. 4077-4087.

64. Finn, C. Model-agnostic meta-learning for fast adaptation of deep networks / C. Finn, P. Abbeel, S. Levine // Proceedings of the 34th International Conference on Machine Learning. - 2017. - С. 1126-1135.

65. Воронцов, К. В. Методы статистического обучения. Задача диагностики заболеваний по электрокардиограмме / К. В. Воронцов. - 2014. - URL: http: / / www.machinelearning.ru / wiki / images /0/ 0a/Voron-2014-06-26-school-VI.pdf.

66. Берникова, О. А. Методы оптического распознавания текста на арабском языке / О. А. Берникова, А. А. Бояров, О. И. Редькин, А. А. Сенов // Стохастическая оптимизация в информатике. - 2013. - Т. 9, № 2. -С. 3-20.

67. Boiarov, A. Randomized GMM clusterization / A. Boiarov // Управление, Информация и Оптимизация (VI ТМШ). - 2014. - С. 24-24.

68. Бояров, А. А. Стохастическая оптимизация для обучения признаков без учителя / А. А. Бояров // Стохастическая оптимизация в информатике. - 2015. - Т. 11, № 2. - С. 3-16.

69. Boiarov, A. Arabic manuscript author verification using deep convolutional networks / A. Boiarov, A. Senov, A. Knysh // 2017 1st International Workshop on Arabic Script Analysis and Recognition (ASAR). - IEEE. 2017. - С. 1-5.

70. Boiarov, A. Simultaneous perturbation stochastic approximation for clustering of a Gaussian mixture model under unknown but bounded disturbances / A. Boiarov, O. Granichin, H. Wenguang // 2017 IEEE Conference on Control Technology and Applications (CCTA). - IEEE. 2017. - С. 1740-1745.

71. Бояров, A. А. Алгоритм стохастической аппроксимации с рандомизацией на входе для оценивания параметров смеси гауссовых распределений без учителя при разреженных параметрах / A. А. Бояров, О. Н. Граничин // Автоматика и телемеханика. - 2019. - Т. 80, № 8. - С. 44-63.

72. Бояров, А. А. Рандомизированный алгоритм стохастической аппроксимации для кластеризации смеси гауссовых распределений при разреженных параметрах / А. А. Бояров // Стохастическая оптимизация в информатике. - 2019. - Т. 15, № 1. - С. 3-19.

73. Бояров, А. А. Алгоритм стохастической аппроксимации с рандомизацией на входе для многозадачного обучения по малому количеству данных / А. А. Бояров // Стохастическая оптимизация в информатике. - 2019. -Т. 15, № 2. - С. 13-39.

74. Заявка 2013619440 Рос. федерация. «Программа для оптического распознавания визуальной текстовой информации на арабском языке» (ОРТА-2Б.ГРС) : Рос. Федерация / О. А. Берникова, А. А. Бояров, О. Н. Граничин, О. И. Редькин, А. А. Сенов ; правообладатель ФГБОУ ВПО "Санкт-Петербургский государственный университет" (СПбГУ) ; рук. Фед. службы по интеллект. собств. Симонов Б. П. - № 2013661320 ; заявл. 18.10.2018 ; опубл. 05.12.2013.

75. Mitchell, T. M. Machine Learning / T. M. Mitchell. - 1997.

76. Sutton, R. S. Reinforcement Learning: an Introduction / R. S. Sutton, A. G. Barto. - MIT press, 2018.

77. Bertsekas, D. P. Neuro-dynamic programming: an overview / D. P. Bertsekas, J. N. Tsitsiklis // Proceedings of 1995 34th IEEE Conference on Decision and Control. Т. 1. - IEEE. 1995. - С. 560-564.

78. Krizhevsky, A. Imagenet classification with deep convolutional neural networks / A. Krizhevsky, I. Sutskever, G. E. Hinton // Advances in Neural Information Processing Systems. - 2012. - С. 1097-1105.

79. Szegedy, C. Going deeper with convolutions / C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. — 2015. — C. 1—9.

80. He, K. Deep residual learning for image recognition / K. He, X. Zhang, S. Ren, J. Sun // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. — 2016. — C. 770—778.

81. Taigman, Y. Deepface: Closing the gap to human-level performance in face verification / Y. Taigman, M. Yang, M. Ranzato, L. Wolf // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. — 2014. — C. 1701—1708.

82. Hinton, G. Deep neural networks for acoustic modeling in speech recognition / G. Hinton, L. Deng, D. Yu, G. Dahl, A.-r. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, B. Kingsbury [h gp.] // IEEE Signal Processing Magazine. — 2012. — T. 29.

83. Olshausen, B. A. Emergence of simple-cell receptive field properties by learning a sparse code for natural images / B. A. Olshausen, D. J. Field // Nature. — 1996. — T. 381, № 6583. — C. 607.

84. Hinton, G. E. Generative models for discovering sparse distributed representations / G. E. Hinton, Z. Ghahramani // Philosophical Transactions of the Royal Society of London. Series B: Biological Sciences. — 1997. — T. 352, № 1358. — C. 1177—1190.

85. Linder, T. Learning-theoretic methods in vector quantization / T. Linder // Principles of Nonparametric Learning. — Springer, 2002. — C. 163—210.

86. Biau, G. On the performance of clustering in Hilbert spaces / G. Biau, L. Devroye, G. Lugosi // IEEE Transactions on Information Theory. — 2008. — T. 54, № 2. — C. 781—790.

87. McLachlan, G. J. Mixture Models: Inference and Applications to Clustering. T. 84 / G. J. McLachlan, K. E. Basford. — M. Dekker New York, 1988.

88. McLachlan, G. Finite Mixture Models / G. McLachlan, D. Peel. — John Wiley & Sons, 2004.

89. Banfield, J. D. Model-based Gaussian and non-Gaussian clustering / J. D. Banfield, A. E. Raftery // Biometrics. — 1993. — C. 803—821.

90. Girolami, M. Mercer kernel-based clustering in feature space / M. Girolami // IEEE Transactions on Neural Networks. - 2002. - T. 13, № 3. - C. 780-784.

91. Carvalho, C. M. The horseshoe estimator for sparse signals / C. M. Carvalho, N. G. Polson, J. G. Scott // Biometrika. - 2010. - T. 97, № 2. - C. 465-480.

92. Forgy, E. W. Cluster analysis of multivariate data: efficiency versus interpretability of classifications / E. W. Forgy // Biometrics. - 1965. -T. 21. - C. 768-769.

93. MacQueen, J. Some methods for classification and analysis of multivariate observations / J. MacQueen [h gp.] // Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. T. 1. - Oakland, CA, USA. 1967. - C. 281-297.

94. Megiddo, N. On the complexity of some common geometric location problems / N. Megiddo, K. J. Supowit // SIAM Journal on Computing. -1984. - T. 13, № 1. - C. 182-196.

95. Shindler, M. Fast and accurate k-means for large datasets / M. Shindler, A. Wong, A. W. Meyerson // Advances in Neural Information Processing Systems. - 2011. - C. 2375-2383.

96. Leone, M. Clustering by soft-constraint affinity propagation: applications to gene-expression data / M. Leone, M. Weigt // Bioinformatics. - 2007. -T. 23, № 20. - C. 2708-2715.

97. Bolshoy, A. Genome Clustering: From Linguistic Models to Classification of Genetic Texts. T. 286 / A. Bolshoy, Z. Volkovich, V. Kirzhner, Z. Barzily. -Springer Science & Business Media, 2010.

98. Anick, P. G. Exploiting clustering and phrases for context-based information retrieval / P. G. Anick, S. Vaithyanathan // ACM SIGIR Forum. T. 31. -ACM. 1997. - C. 314-323.

99. Zheng, X. Image segmentation based on adaptive K-means algorithm / X. Zheng, Q. Lei, R. Yao, Y. Gong, Q. Yin // EURASIP Journal on Image and Video Processing. - 2018. - T. 2018, № 1. - C. 68.

100. Coates, A. An analysis of single-layer networks in unsupervised feature learning / A. Coates, A. Ng, H. Lee // Proceedings of the 14th International Conference on Artificial Intelligence and Statistics. - 2011. - C. 215-223.

101. Sculley, D. Web-scale k-means clustering / D. Sculley // Proceedings of the 19th International Conference on World Wide Web. — ACM. 2010. — С. 1177—1178.

102. Mladenovic, N. The p-median problem: A survey of metaheuristic approaches / N. Mladenovic, J. Brimberg, P. Hansen, J. A. Moreno-Perez // European Journal of Operational Research. — 2007. — Т. 179, № 3. —

C. 927—939.

103. Reese, J. Solution methods for the p-median problem: An annotated bibliography / J. Reese // NETWORKS: An International Journal. — 2006. — Т. 48, № 3. — С. 125—142.

104. Arthur, D. k-means++: The Advantages of Careful Seeding : тех. отч. /

D. Arthur, S. Vassilvitskii ; Stanford. — 2006.

105. Dempster, A. P. Maximum likelihood from incomplete data via the EM algorithm / A. P. Dempster, N. M. Laird, D. B. Rubin // Journal of the Royal Statistical Society: Series B (Methodological). — 1977. — Т. 39, № 1. —

C. 1—22.

106. Neal, R. M. A view of the EM algorithm that justifies incremental, sparse, and other variants / R. M. Neal, G. E. Hinton // Learning in Graphical Models. — Springer, 1998. — С. 355—368.

107. Vorontsov, K. EM-like algorithms for probabilistic topic modeling / K. Vorontsov, A. Potapenko // Machine Learning and Data Mining. — 2013. — Т. 1, № 6. — С. 657—686.

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

D. Dueck // Science. — 2007. — Т. 315, № 5814. — С. 972—976.

109. Ester, M. A density-based algorithm for discovering clusters in large spatial databases with noise. / M. Ester, H.-P. Kriegel, J. Sander, X. Xu [и др.] // KDD. Т. 96. — 1996. — С. 226—231.

110. Schubert, E. DBSCAN revisited, revisited: why and how you should (still) use DBSCAN / E. Schubert, J. Sander, M. Ester, H. P. Kriegel, X. Xu // ACM Transactions on Database Systems (TODS). — 2017. — Т. 42, № 3. — С. 19.

111. Gialampoukidis, I. Community detection in complex networks based on DBSCAN* and a Martingale process / I. Gialampoukidis, T. Tsikrika, S. Vrochidis, I. Kompatsiaris // 2016 11th International Workshop on Semantic and Social Media Adaptation and Personalization (SMAP). - IEEE. 2016. - C. 1-6.

112. Shen, J. Real-time superpixel segmentation by DBSCAN clustering algorithm / J. Shen, X. Hao, Z. Liang, Y. Liu, W. Wang, L. Shao // IEEE Transactions on Image Processing. - 2016. - T. 25, № 12. - C. 5933-5942.

113. Attias, H. Inferring parameters and structure of latent variable models by variational Bayes / H. Attias // Proceedings of the 15th conference on Uncertainty in Artificial Intelligence. - Morgan Kaufmann Publishers Inc. 1999. - C. 21-30.

114. Pfitzner, D. Characterization and evaluation of similarity measures for pairs of clusterings / D. Pfitzner, R. Leibbrandt, D. Powers // Knowledge and Information Systems. - 2009. - T. 19, № 3. - C. 361.

115. Tan, P.-N. Introduction to Data Mining / P.-N. Tan, M. Steinbach, V. Kumar. - Pearson Education India, 2016.

116. Hubert, L. Comparing partitions / L. Hubert, P. Arabie // Journal of Classification. - 1985. - T. 2, № 1. - C. 193-218.

117. Strehl, A. Cluster ensembles-a knowledge reuse framework for combining multiple partitions / A. Strehl, J. Ghosh // Journal of Machine Learning Research. - 2002. - T. 3, Dec. - C. 583-617.

118. Fowlkes, E. B. A method for comparing two hierarchical clusterings / E. B. Fowlkes, C. L. Mallows // Journal of the American Statistical Association. - 1983. - T. 78, № 383. - C. 553-569.

119. Ren, S. Faster r-cnn: Towards real-time object detection with region proposal networks / S. Ren, K. He, R. Girshick, J. Sun // Advances in Neural Information Processing Systems. - 2015. - C. 91-99.

120. Ronneberger, O. U-net: Convolutional networks for biomedical image segmentation / O. Ronneberger, P. Fischer, T. Brox // International Conference on Medical Image Computing and Computer-Assisted Intervention. - Springer. 2015. - C. 234-241.

121. Koch, G. Siamese neural networks for one-shot image recognition / G. Koch, R. Zemel, R. Salakhutdinov // ICML Deep Learning Workshop. T. 2. — 2015.

122. Santoro, A. Meta-learning with memory-augmented neural networks / A. Santoro, S. Bartunov, M. Botvinick, D. Wierstra, T. Lillicrap // International Conference on Machine Learning. — 2016. — C. 1842—1850.

123. Ravi, S. Optimization as A Model For Few-Shot Learning / S. Ravi,

H. Larochelle. — 2016.

124. McCulloch, W. S. A logical calculus of the ideas immanent in nervous activity / W. S. McCulloch, W. Pitts // The Bulletin of Mathematical Biophysics. — 1943. — T. 5, № 4. — C. 115—133.

125. Shen, Y. Learning semantic representations using convolutional neural networks for web search / Y. Shen, X. He, J. Gao, L. Deng, G. Mesnil // Proceedings of the 23rd International Conference on World Wide Web. — ACM. 2014. — C. 373—374.

126. Kim, Y. Convolutional neural networks for sentence classification / Y. Kim // Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). — 2014. — C. 1746—1751.

127. Oord, A. v. d. Wavenet: A Generative Model For Raw Audio / A. v. d. Oord, S. Dieleman, H. Zen, K. Simonyan, O. Vinyals, A. Graves, N. Kalchbrenner, A. Senior, K. Kavukcuoglu // arXiv preprint arXiv:1609.03499. — 2016.

128. Rethage, D. A wavenet for speech denoising / D. Rethage, J. Pons, X. Serra // 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). — IEEE. 2018. — C. 5069—5073.

129. Schmidhuber, J. Evolino: Hybrid neuroevolution/optimal linear search for sequence prediction / J. Schmidhuber, D. Wierstra, F. J. Gomez // Proceedings of the 19th International Joint Conferenceon Artificial Intelligence (IJCAI). — 2005.

130. Sutskever, I. Sequence to sequence learning with neural networks /

I. Sutskever, O. Vinyals, Q. V. Le // Advances in Neural Information Processing Systems. — 2014. — C. 3104—3112.

131. Bromley, J. Signature verification using a "siamese" time delay neural network / J. Bromley, I. Guyon, Y. LeCun, E. Sackinger, R. Shah // Advances in Neural Information Processing Systems. — 1994. — C. 737—744.

132. Chopra, S. Learning a similarity metric discriminatively, with application to face verification / S. Chopra, R. Hadsell, Y. LeCun [h gp.] // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. — 2005. — C. 539—546.

133. Lake, B. M. The Omniglot challenge: a 3-year progress report / B. M. Lake, R. Salakhutdinov, J. B. Tenenbaum // Current Opinion in Behavioral Sciences. — 2019. — T. 29. — C. 97—104.

134. Wichrowska, O. Learned optimizers that scale and generalize / O. Wichrowska, N. Maheswaranathan, M. W. Hoffman, S. G. Colmenarejo, M. Denil, N. de Freitas, J. Sohl-Dickstein // Proceedings of the 34th International Conference on Machine Learning. — JMLR. org. 2017. — C. 3751—3760.

135. Rusu, A. A. Meta-learning with Latent Embedding Optimization / A. A. Rusu, D. Rao, J. Sygnowski, O. Vinyals, R. Pascanu, S. Osindero, R. Hadsell // arXiv preprint arXiv:1807.05960. — 2018.

136. Donahue, J. Decaf: A deep convolutional activation feature for generic visual recognition / J. Donahue, Y. Jia, O. Vinyals, J. Hoffman, N. Zhang, E. Tzeng, T. Darrell // International Conference on Machine Learning. — 2014. — C. 647—655.

137. Jamal, M. A. Task Agnostic Meta-Learning for Few-Shot Learning / M. A. Jamal, G.-J. Qi // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. — 2019. — C. 11719—11727.

138. Finn, C. Probabilistic model-agnostic meta-learning / C. Finn, K. Xu, S. Levine // Advances in Neural Information Processing Systems. — 2018. — C. 9516—9527.

139. Hochreiter, S. Long short-term memory / S. Hochreiter, J. Schmidhuber // Neural Computation. — 1997. — T. 9, № 8. — C. 1735—1780.

140. Mishra, N. A Simple Neural Attentive Meta-learner / N. Mishra, M. Rohaninejad, X. Chen, P. Abbeel // arXiv preprint arXiv:1707.03141. — 2017.

141. Lea, C. Temporal convolutional networks: A unified approach to action segmentation / C. Lea, R. Vidal, A. Reiter, G. D. Hager // European Conference on Computer Vision. — Springer. 2016. — C. 47—54.

142. Robbins, H. A stochastic approximation method / H. Robbins, S. Monro // The Annals of Mathematical Statistics. - 1951. - С. 400-407.

143. Kiefer, J. Stochastic estimation of the maximum of a regression function / J. Kiefer, J. Wolfowitz // The Annals of Mathematical Statistics. — 1952. — Т. 23, № 3. — С. 462—466.

144. Blum, J. R. Multidimensional stochastic approximation methods / J. R. Blum // The Annals of Mathematical Statistics. — 1954. — С. 737—744.

145. Растригин, Л. А. Статистические методы поиска / Л. А. Растригин. — М. : Наука, 1968.

146. Spall, J. C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation / J. C. Spall // IEEE Transactions on Automatic Control. — 1992. — Т. 37, № 3. — С. 332—341.

147. Huber, P. J. Robust Statistics / P. J. Huber. — Springer, 2011.

148. Vorontsov, K. Additive regularization of topic models / K. Vorontsov, A. Potapenko // Machine Learning. — 2015. — Т. 101, № 1—3. — С. 303—323.

149. Hoerl, A. E. Ridge regression: Biased estimation for nonorthogonal problems / A. E. Hoerl, R. W. Kennard // Technometrics. — 1970. — Т. 12, № 1. — С. 55—67.

150. Tibshirani, R. Regression shrinkage and selection via the lasso / R. Tibshirani // Journal of the Royal Statistical Society: Series B (Methodological). — 1996. — Т. 58, № 1. — С. 267—288.

151. Ruder, S. An Overview of Multi-task Learning in Deep Neural Networks / S. Ruder // arXiv preprint arXiv:1706.05098. — 2017.

152. Kendall, A. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics / A. Kendall, Y. Gal, R. Cipolla // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. — 2018. — С. 7482—7491.

153. Srivastava, N. Dropout: a simple way to prevent neural networks from overfitting / N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, R. Salakhutdinov // The Journal of Machine Learning Research. — 2014. — Т. 15, № 1. — С. 1929—1958.

SAINT PETERSBURG STATE UNIVERSITY

Manuscript copyright

Boiarov Andrei Alexandrovich

Randomized approach to unsupervised and few-shot learning

Specility 01.01.09 -«Discrete Mathematics and Mathematical Cybernetics»

Dissertation is submitted for the degree Candidate of Physical and Mathematical Sciences

Translated from Russian

Scientific advisor:

Professor, Doctor of Science in Physics and Mathematics

Granichin Oleg Nikolaevich

Saint Petersburg - 2020

Table of contents

Introduction...................................103

Chapter 1. Unsupervised and few-shot machine learning algorithms 111

1.1 Clustering methods...........................112

1.1.1 Clustering problem.......................112

1.1.2 Gaussian mixture model....................115

1.1.3 Gaussian mixture model with sparse parameters.......116

1.1.4 Method k-means ........................118

1.1.5 Modifications of the k-means method.............119

1.1.6 EM algorithm ....................................................121

1.1.7 Affinity propagation method..................122

1.1.8 Density-based spatial clustering of applications with noise . . 123

1.1.9 Variational Bayesian Gaussian mixture inference.......124

1.1.10 Evaluation of the quality of clustering.............124

1.2 Few-shot learning algorithms......................126

1.2.1 The few-shot learning problem.................127

1.2.2 Deep neural networks......................128

1.2.3 Metric approaches........................129

1.2.4 Optimization approaches....................133

1.2.5 Recurrent approaches......................135

1.3 Stochastic approximation........................135

Chapter 2. Randomized algorithms for unsupervised and few-shot

learning .............................139

2.1 Randomized clustering algorithm....................139

2.1.1 Clustering a Gaussian mixture model with unknown but bounded disturbances ............................................140

2.1.2 Unsupervised parameters estimation of Gaussian mixture

model with sparse parameters ..................................146

2.2 Randomized approach to a few-shot learning classifier........150

2.2.1 Multi-task learning ..............................................150

2.2.2 Stochastic approximation algorithm with randomization at

the input for multi-task few-shot learning...........151

Chapter 3. Experiments results ......................157

3.1 Simulation for the problem of clustering a Gaussian mixture model

with unknown but bounded disturbances...............157

3.1.1 The case of k-means ......................158

3.1.2 Gaussian mixture model....................160

3.1.3 External disturbances......................162

3.1.4 Gaussian mixture model with sparse parameters.......162

3.2 Testing a classifier in the few-shot learning task............165

3.3 Verification of authorship of medieval manuscripts in Arabic.....168

3.3.1 Single author verification....................169

3.3.2 Verification of many authors..................174

Conclusion....................................176

Bibliography ..................................177

Introduction

Relevance of the topic. Over the past few years, various machine learning methods, such as deep convolutional neural networks [1], recurrent neural networks [2], logistic regression [3], support vector machine [4], k-means method [5] etc., have developed rapidly. These algorithms are widely used in pattern recognition, word processing, robotics, control of unmanned vehicles, and recommendation systems. The greatest progress was achieved in the development of supervised learning methods. The algorithms of this family are based on minimizing the loss function using gradient methods. In the presence of a large volume of labeled and "cleaned" data, this approach gives good results.

The theoretical studies underlying the classification and clustering methods that are part of the family of machine learning methods and pattern recognition methods are presented in the works of R. A. Fisher [6], V. A. Yakubovich [7], Y. Z. Tsypkin [8; 9], M. A. Aizerman [10], V. N. Fomin [11], V. N. Vapnik and A. Y. Chervonenkis [12], J. Hartigan [13], H. Barlow [14], L. Kaufman [15], B. T. Polyak [16], A. L. Fradkov [17] and other. Deep neural networks form a subclass of machine learning algorithms called deep learning, which in recent years has been actively developed. It is based on works of F. Rosenblatt [18], K. Fukunaga [19], D. Rumelhart with co-authors [20], J. Hinton [21; 22], Y. LeCun [1; 23; 24], Y. Bengio [25; 26]. Surveys of modern machine learning and pattern recognition algorithms are given in the works of T. Hastie with co-authors [3], K. Bishop [27], I. Goodfellow with co-authors [28], K. V. Vorontsov [29]. One of the key tasks that most machine learning algorithms reduce to is the multidimensional optimization problem, which is widely covered in basic research of B. T. Polyak [30], S. Boyd with co-author [31], J. Nocedal [32], Y. E. Nesterov [33], L. Bottou [34; 35].

For the successful work of the basic standard supervised machine learning algorithms, known data modeling parameters, the ability to calculate the gradient for the optimized loss function (quality functional), and as many training data as possible that can be approximated using the normal distribution are required [30]. However, under real conditions, these requirements are often not fulfilled: often even the hypothesis of data centeredness with respect to certain centroids is not confirmed, and it is impossible to calculate the gradient for the loss function. For example, data may be sparse in nature (like sparse Gaussian mixture model [36]).

Therefore, standard universal methods give a biased estimate of the desired parameters. For such cases, it is necessary to develop new methods that can work in such non-standard conditions.

Randomization algorithms are often used to reduce computational complexity or to "enrich" the sequence of observations. The beginning of research on the application of randomization methods in machine learning was laid by the article of M. Vidyasagar [37]. Then these studies were continued and expanded by M. Campi [38], O. N. Granichin [39; 40], Y. S. Popkov [41], B. T. Polyak and M. V. Khlebnikov [42], R. Tempo with co-authors [43]. One of the applications of randomization in machine learning is the stochastic approximation algorithms described in the works of O. N. Granichin [39; 44; 45], B. T. Polyak and A. B. Tsybakov [46], J. C. Spall [47; 48], H. Kushner and G. G. Yin [49], V. S. Borkar [50], A. V. Nazin [51; 52]. Of particular interest are stochastic approximation algorithms for optimizing non-stationary loss functions (varying with time), which are presented in studies of A. T. Vakhitov u O. N. Granichin with coauthor [53—55], J. C. Spall with co-author [56].

Standard supervised machine learning algorithms work successfully when they learn on a large amount of labeled data. Such data sets are relatively few for a relatively small range of tasks (recognition and localization of objects, recognition of faces, emotions and postures of a person), a parallel case for translating texts between languages, etc.). Each new task requires the collection and preparation of a new dataset, which is a rather time-consuming task and often requires the efforts of a large number of people. However, in the world there is (mainly due to the development of the Internet, social networks and smartphones) a huge amount of unlabeled data. One of the most important tasks associated with this type of data is the unsupervised learning (self-learning) problem and one of its special cases is the clustering problem. The lack of a pre-known structure and markup of data is a source of uncertainties, for which new approaches need to be developed. A randomized approach to the clustering task was proposed in the work of O. N. Granichin and O. A. Izmakova [57].

Another type of uncertainty associated with the processing of poorly labeled data arises in the few-shot learning tasks that are part of a wider range of the meta-learning tasks. In such problems, a certain set of classes with a small amount of labeled data is available for learning the algorithm. It must be trained in several elements (for example, 1, 5 or 10) per class with high quality to determine this class.

In addition, during the operation of the algorithm, elements of new classes that were not in the training set will come to the input. The algorithm should be able to adapt to work with these new classes, without losing the quality of work on old classes. The methods of this family are extremely in demand, since the need for adaptation to new classes in just a few examples arises in many applied problems. Therefore, the development of adaptive algorithms that can work in conditions of such uncertainties is extremely urgent. The tasks of meta-learning have been described in works of J. Schmidhuber [58], S. Bengio [59], B. Lake with co-authors [60], M. Andrychowicz with co-authors [61] and developed in papers of O. Vinyalis [62], J. Snell [63], C. Finn with co-authors [64]. Note that now there are only a small number of application programs that implement self-learning and few-shot learning algorithms and allow to quickly apply them both to data obtained by simulation and to real non-standard tasks (for example, to determine the authorship of medieval manuscripts).

Thus, it can be concluded that the task of developing and mathematically substantiating approaches that can work efficiently under conditions of unlabeled and poorly labeled data is the key to the further development of machine learning algorithms and artificial intelligence, which confirms the relevance of the chosen research topic.

The aim of the work is the development and mathematical justification of machine learning algorithms that are resistant to uncertainties arising in the absence of markup and a small amount of data.

To achieve the stated aim, the following problems were posed:

1. Investigate, develop and mathematically justify the general clustering algorithm in a Gaussian mixture model, capable of working efficiently with unknown but bounded disturbances, and realizing the idea of "online" learning.

2. Investigate, develop and mathematically justify a modification of the general clustering algorithm for the conditions of a Gaussian mixture model with sparse parameters.

3. Investigate, develop and mathematically justify the training method for a adaptive few-shot learning classifier.

4. Investigate the working capacity and quality of work of the developed new algorithms both in terms of comparative modeling and in the real task of determining the authorship of medieval manuscripts.

Research methods. The dissertation uses methods of probability theory and mathematical statistics, optimization and estimation methods, machine learning methods, randomized algorithms, simulation modeling.

The main results of the dissertation:

1. Proposed, mathematically justified and researched the general clustering algorithm in a Gaussian mixture model, capable of working efficiently with unknown but bounded disturbances, and realizing the idea of "online" learning.

2. Proposed, mathematically justified and researched a modification of the general clustering algorithm for the conditions of a Gaussian mixture model with sparse parameters.

3. Proposed and mathematically justified the training method for a adaptive few-shot learning classifier.

4. A set of application programs has been developed that implement the algorithms from items 1, 2, 3, and demonstrate their performance both on simulated examples and in problems of classifying handwritten letters and verifying authorship of medieval Arabic manuscripts.

Scientific novelty: All the main scientific results of the dissertation are new.

Theoretical value and practical significance. The theoretical value of the results lies in the development, mathematical justification and study of a generalized adaptive clustering algorithm in a model of a mixture of Gaussian distributions, which remains operational with unknown but bounded disturbances; in the development and justification of the modification of this clustering algorithm, which is able to work qualitatively in a mixture of Gaussian distributions with sparse parameters. A method for training an adaptive classifier in a small number of labeled examples based on a new multitask loss function, the parameters of which are optimized using stochastic approximation, is proposed and mathematically justified.

The proposed adaptive clustering methods can be used in tasks related to data processing "on the fly" (online) without labeling. Such data occurs, for example, when filtering spam or in streaming services. The clustering method of a a Gaussian mixture model with sparse parameters can be applied in practice to determine the structure of noise in measuring systems. The proposed approach to training an adaptive few-shot learning classifier using a small number of labeled examples can be used in many problems where at the time of training all possible classes are unknown and little labeled data is given for each class. An example is the

task of recognizing handwritten letters among various alphabets and verifying the authorship of medieval manuscripts in a small number of available text samples.

Approbation of work. The results of the dissertation were reported at the seminars of the departments of software engineering and theoretical cybernetics of the faculty of mathematics and mechanics of Saint Petersburg State University, at the seminars of the Research laboratory for analysis and modeling of social processes of Saint Petersburg State University, at the seminars of the department of mathematical modelling of energetic systems of the faculty of applied mathematics and control process of Saint Petersburg State University, at the seminars "Theory of automatic control" of the Laboratory 7 of Institute of control science of Russian academ of science, at the Sixth traditional youth summer school "Control, Information and Optimization" (village of Grigorchikovo, Moscow Region, Russia, June 22-29, 2014) (first place according to the results of a machine learning algorithm contest held among school participants [65]), at international conferences 2017 1st International Workshop on Arabic Script Analysis and Recognition (ASAR) (April 3-5, 2017, Nancy, France), 2017 IEEE Conference on Control Technology and Applications (August 27-30, 2017, Kohala Coast, Hawaii, USA).

The dissertation results were used in the grants RFBR 16-07-00890 "Randomized algorithms in automatic control and knowledge extraction", RFBR 17-51-53053 "Development of methods for obtaining superresolution of digital surface models based on convolutional neural networks", RFBR 16-19-00057 "Adaptive control with predictive models with a variable structure of the state space with an application to the systems of network traffic control and automation of medical equipment".

Publications. The main results obtained in the dissertation are presented in 9 works [66—74], of which [71] was published in a publication from the list of the Higher Attestation Commission, three [69—71] published in publications indexed in the Web of Science and Scopus databases, [74] is the certificate for a program for electronic computers.

Works [66; 69—71; 74] written in collaboration. In the works [66; 70; 71] А A. Boiarov owns the formulations and proofs of theorems, the results of experiments and simulation, co-authors — the general formulation of the problem and the choice of direction of solution. In the work [69] А A. Boiarov owns the development of a classification algorithm, co-authors — general statement of the problem and development of a data preprocessing algorithm. In [74] А A. Boiarov

owns the development of classification algorithms and software architecture, coauthors — general statement of the problem and development of data preprocessing algorithms.

Scope and structure of work. The dissertation consists of an introduction, three chapters and conclusions. The full scope of the dissertation is 92 pages, including 18 figures and 9 tables. The list of references contains 153 items.

In the introduction, the relevance of the topic of the dissertation is substantiated, the goal is formulated and the research objectives are set, the main results are summarized.

In the first chapter provides descriptions of the problems of unsupervised and few-shot learning, and also provides an overview of the main algorithms for solving these problems, accompanied by a review of the literature on the topic of research. Section 1.1 sets the task of clustering, one of the most important tasks of the unsupervised learning, and discusses standard methods used to solve the problem. Subsection 1.1.1 gives the wording of the clustering problem in the form of an optimization problem. Subsection 1.1.2 considers a mixture of Gaussian distributions as the main model for the clustering problem under study. Subsection 1.1.3 contains a description of a Gaussian mixture model with sparse parameters, which is used, for example, to model various noises. Subsections 1.1.4 — 1.1.9 provide descriptions of machine learning algorithms used to solve this problem. Algorithms are considered both with an estimation of covariance matrixes of clusters, and without it. Subsection 1.1.10 contains a description of the criteria for evaluation of the quality of clustering. Section 1.2 contains descriptions of the few-shot learning task and the main approaches used to solve it. In subsection 1.2.1, the problem of classification by a small number of labeled examples is posed. Subsection 1.2.2 includes a description of deep neural networks and the basic concepts associated with them. This description is necessary, since the neural network is the main type of model used to solve the few-shot learning problem. The following sections describe the methods included in the three main groups of classification algorithms for a small number of examples: subsection 1.2.3 represents metric approaches, subsection 1.2.4 — optimization, subsection 1.2.5 — recurrent. Section 1.3 contains a description of algorithms for estimating unknown parameters of the system based on stochastic approximation methods because of the promise of using this approach to solve the problems posed in the previous sections.

In the second chapter, the main theoretical results of the dissertation research are formulated and proved. Section 2.1 discusses the use of a randomized approach in the clustering problem. Subsection 2.1.1 describes the main randomized algorithm for stochastic approximation for clustering in a Gaussian mixture model. Theorem 1 on the consistency of the estimates of the centers of clusters and covariance matrices obtained using this algorithm is formulated and proved. The analysis of the basic properties of the constructed randomized algorithm is carried out. In subsection 2.1.2, we consider the case of a mixture of Gaussian distributions with sparse parameters, in which the original clustering methods significantly lose their quality of work. For such a data model, a modification of the randomized algorithm of stochastic approximation for clustering proposed in the previous subsection is described. To estimate the parameters obtained using the described modification, Theorem 2 on their consistency is formulated and proved. Section 2.2 describes a randomized approach for few-shot learning. In subsection 2.2.1, we consider the problem of multitasking training and with the help of it we formulate a new loss function (quality function). In subsection 2.2.2, we describe the randomized algorithm of stochastic approximation for few-shot classification, and also formulate and prove Theorem 3 on the consistency of parameter estimates obtained using this algorithm. In this subsection proposed the method for training on a small amount of data, based on the randomized algorithm of stochastic approximation for tracking, formulate and prove Theorem 4 justifying the obtained estimates.

In the third chapter presents the results of experiments and testing, illustrating the work of the proposed approaches. Section 3.1 describes the results obtained for simulation in the problem of clustering of a Gaussian mixture model. In subsection 3.1.1, considered the case of evaluating only the centers of clusters and compare the method proposed in subsection 2.1.1 with the standard self-learning methods used in such a problem. In subsection 3.1.2, described the case of constructing estimates of centroids and covariance matrices and present the results of comparing the algorithm proposed in subsection 2.1.1 with standard analogues. Subsection 3.1.3 is devoted to experiments in the presence of additive external noise and their results for the method proposed in subsection 2.1.1 and other clustering algorithms. In subsection 3.1.4, we consider experiments in the case of a model of a mixture of Gaussian distributions with sparse parameters. The results of comparing the method presented in 2.1.2 with standard clustering algorithms are presented. Section 3.2 is devoted to the test results of the approach proposed in 2.2.2 for

training the few-shot classifier on a standard data set. Section 3.3 describes the approbation of the methods presented in Section 2.2 in the problem of verification of authorship of medieval Arabic manuscripts.

B conclusion, the main results of the dissertation research are formulated.

Chapter 1. Unsupervised and few-shot machine learning algorithms

Machine learning is a field of knowledge that has a close relationship with statistical data analysis, pattern recognition, and optimization. A machine learning algorithm is an algorithm that can learn from data. In the work of T. Mitchell [75] the following definition of the ability to learn is given: "A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E". Experience E, class of tasks T and performance measure P may vary depending on the specific problem.

Machine learning methods can be broadly divided into two categories depending on the type of data to which they are applied: supervised learning and unsupervised learning. The supervised learning algorithm uses data for which there is markup: each example of the data has a label of the class to which it belongs. These labels are then used in training to receive signals about how to change the parameters of the training model in order to improve the quality of classification. It is important to note that in the standard statement of the classification problem, the classes in the training sample coincide with the classes on the test. The regression problem is also solved by methods related to a supervised learning. In this case, a certain real number is assigned to each data element.

Unsupervised learning algorithms work with data for which the markup is unknown. The purpose of the methods in this category is to identify some useful structure in the data. Such a structure can be an estimate of the probability distribution that generated the input data, or a breakdown of the data into groups of similar examples in the case of a clustering problem. Self-learning algorithms can use only input data for training, there are no external additional signals for this task.

Supervised learning and unsupervised learning methods can be divided as follows. In the case of a self-learning problem for an input random vector x, it is necessary to construct an estimate of the probability distribution P(x) or some properties of this distribution of interest. In the case of a supervised learning for each x is available a number y and the algorithm learns to predict y by x by estimating P(y|x).

Reinforced learning methods, which trains the sequence of actions in a certain environment to achieve its goal, is distinguished into a separate category. To do this,

they use the reaction of the environment to actions [76; 77]. However, the dissertation focuses on the problems of clustering and classification.

Supervised learning algorithms, especially when used with deep neural networks, are able to work qualitatively in various problems of classification, regression and pattern recognition [78—82]. But for training, they need large amounts of labeled data. Without them, the accuracy of these algorithms is significantly degraded. The collection, preparation and labeling of training data for each task are extremely time-consuming operations and require manual labor. For unsupervised learning algorithms (and in particular clustering), on the contrary, such data labeling is not required. Standard classification methods are not able to quickly and efficiently adapt to new classes that were not in the training set. This property leads to consideration of few-shot learning algorithms.

In this chapter, the problems of clustering and few-shot learning are formulated, the main methods for solving them are presented, and the approaches of stochastic approximation that will be further used to solve these problems are considered.

1.1 Clustering methods

This section discusses the basic self-learning algorithms in the absence of a labeling. The clustering problem and the data model under study are formulated — a mixture of Gaussian distributions. Classical algorithms for solving the problem are presented.

1.1.1 Clustering problem

Unsupervised learning methods are aimed at extracting some useful information about the distribution of data without instructions from a person, in contrast to supervised learning methods, where this indication is a labeling. An example of such useful information is the splitting of data into groups of examples similar in a certain way, as in the case of a clustering problem. In the classical setting,

the goal of self-learning algorithms is to find some "best" data representation [14]. By "best" is meant a representation that stores as much information as possible about the input data and is thus simpler than the original [14; 83; 84]. The essence of the clustering task is to determine the groups in the input that will give such a "best" representation. An example of this is the use of clustering algorithms to compress (or quantize) data. [85; 86].

Let formulate the clustering problem. Let (Q, F, P) is a probability space, where Q = Rd, F is a a-algebra of subsets of Q, P(X) — probability distribution defined on a set of input data X = {x1, x2,...}, which is a subset of Euclidean space Rd, k > 1 is a a natural number. Denote by 1..k a set of indices {1,2,... ,k}. We assume that the set of input data X is divided into k unknown subsets

{X?,..., Xk} : X = [i2i..kX?

so that the probability distribution P(X) can be represented using a mixture of distributions:

k

P(X) = X p,P(X?), (1.1)

i=1

where pi (pi > 0) u P(X?), i 2 1..k, — corresponding probabilities and distributions.

The clustering problem (or cluster analysis) is to find the optimal partition X of the input data sets X into k non-empty clusters

k

X(X) = {Xi, ...,Xk} : X = [Xi u Xi \ Xj = 0, i = j.

i=1

Partitioning X is determined by function yX : X ! 1..k, which maps each point X to a cluster index. Thus,

Xi = {x 2 X|yx(x) = i}. (1.2)

The task of clustering is to find the best such partition:

X ? = {Xl,...,Xk }.

The clustering problem can be described as follows: elements belonging to one group (cluster) are more similar than elements belonging to different groups (clusters). To solve this problem, some penalty function (quality function) qi is

introduced and determining "proximity " to the cluster i, i 2 1..k. Then, to obtain optimal clustering, it is necessary to minimize the functionality:

F(X) = EXf (X, x) ! min, (1.3)

X

where EX — symbol of conditional expectation, subject to a fixed set X and

f (X, x) = qyx (x)(X, x).

If vectors 6i, i 2 1..k, is interpreted as cluster centers or centroids and matrices Г^ i 2 1..k, — as covariance matrices, then the clustering quality functional (1.3) takes the form

k л

F(X) = X qi(6i, Г, x)P(dx) ! min . (1.4)

1=1 X

For i 2 1..k and fixed x 2 X every function q^, •, x) depends only on 6i и Г^ i.e. qi(•, •, •) : Rd x Rdxd x X ! R. Then you can choose a partition rule

Хг(0, Г) = {x 2 X : qi(6i, Гг, x) 6 qj(6j, Г,-, x), j 2 1, 2,...,i - 1;

qi(6i,Гг,x) 6 qj(6j,Г3,x), j 2 i + 1,i + 2,...,k}, i 2 1..k,

which minimizes (1.3). Then 0 = (61, 62,... ,6k) — (d x k)-matrix, и Г — a set, consisting of k matrices Г1, Г2,..., Гк, where Г1 2 Rdxd, i 2 1..k.

True clustering of input to minimize (1.4), leads to the following rule, according to which x refers to a specific cluster:

l = argmin^L.k qi(6i,Гг,x),

где l = l(0, Г, x) — label of the cluster to which the data point is assigned x. Let в/ 2 Rk — vector, consisting of zeros and ones per position l. Then the functional (1.4) can be rewritten as follows:

F(0, Г) = j eTq(0, Г, x)P(dx) ! min, (1.5)

X

where q(0,Г,x) 2 Rk is value vector qi(6i,Г1,x),i 2 1..k.

An important particular case corresponds to a uniform distribution P(-) and the penalty function, which is the square of the Mahalanobis distance

qi (6г, Гг, x) = (x - ✓if^x - 6i). (1.6)

1.1.2 Gaussian mixture model

The statement of the clustering problem considers the representation of the probability distribution of data through a mixture of distributions (1.1). One of the most common and widely used is the case of a Gaussian Mixture Model (GMM) [87—90]:

k

f (X, x) = f (6, r, x) = X PiG(x|0i, ri), (1.7)

i=1

where G(x|0i, ri) is an average density of the Gaussian distribution 0i 2 Rd and covariance matrix ri, i 2 1..k. This approach will be considered as a data description model.

Consider the problem: By input sequence {x1, x2,...} and setpoint k find the parameters 0i 2 Rd and p, i 2 1..k, of Gaussian distributions, a mixture of which spawned an input sequence. Such a task fits into the framework of the clustering problem formulated above.

There are many possible partitions of the set X into k subsets. The problem of finding unknown parameters 0i 2 Rd and ri, i 2 1..k, is closely related to the

clustering problem, which according to (1.4) consists in finding:

kZ

F(X) = X /(x - 0i)Tr-1(x - 0i)P(dx) ! min. (1.8)

i=1 X

For a input sequence {x1, x2,... ,xn} the functional (1.8) takes the form

F(6, r) = XX (xj - 0i)Tr-1(xj - 0i) ! min, j 2 1..n. (1.9)

i=1 xj ex, '

This connection lies in the fact that in the case of the GMM data model and in the above statement of the clustering problem, finding the optimal GMM parameters is equivalent to finding the optimal clustering parameters. This connection is justified by the following Lemma 1.

L e m m a 1. Let the sequence {x1, x2,... ,xn} generated by a mixture of Gaussian distributions (1.7) with parameters 6? and P?. Then, under the conditions given above, for n the functional (1.9) tends to a minimum at 6? u P?.

Доказательство. If the sequence {xn} generated by GMM with parameters 0? and T?then with these parameters a minimum is achieved minus the logarithm of the likelihood function

Xln(XXPiG(x|6i,Г^ .

x2X \i=1 J

By the definition of the density of the normal distribution, this expression can be rewritten as k

XX (- In Pi(2^)"d 1Г |-1 + 1/2(xj - ✓iy^-V - 6i)) , j 2 1..n. (П.1)

i=1 xj GXj

Denote the first term in (П.1) as L and the second as R then

argmine,rL = argmine,rR = (0?, Г?) при n !i.

Functional (1.9) can be rewritten by (1.4) and (1.6) as

k

F(0, Г) = X |Xi|-1 X (xj - ^Г-1^ - 6i), j 2 1..n.

i=1 xj GXj

Thus

argmine,rF(0, Г) = argmine,rR = (0?, Г?) при n !i.

□

Lemma 1 shows that the optimized functional (1.9) can be represented as the sum minus the logarithms of the likelihood functions for one-component GMMs.

1.1.3 Gaussian mixture model with sparse parameters

In [36] an interesting model of a Gaussian mixture model with sparse parameters (sparse GMM). With this approach, a model is constructed with a large number of parameters, many of which are then reduced to zero in the process of tuning to data (hence the "sparse" in the name). To simulate such properties, it is necessary to use a priori distributions, which have a large probabilistic

mass concentrated at zero, and long tails to correspond to possible large system parameters. To achieve this behavior in this model, the average value is given as

0i 2 Rd, 0ii - N(0,a2), a - C+(0,1), l 2 1..d, (1.10)

where C+(0,1) means the Cauchy distribution bounded on the positive axis (takes only positive values), with parameters 0 and 1. The diagonal covariance matrix is specified using

ri = diag(a2, o"2,..., a2), a - C+ (0; 0,5), j 2 1..d. (1.11)

This choice of distributions for modeling corresponds to "horseshoe prior" method [91] the use of which allows us to satisfy the sparse properties described above due to the fact that in the Cauchy distribution a large mass of probabilities are concentrated around the mode. Such a distribution has tails that attenuate, as a result of which the parameters will decrease to zero, unless the opposite follows from the data.

Weights pi — D(e0,..., e0),i 2 1..k are assumed to belong to the Dirichlet distribution, where the parameter e0 — kap) derived from gamma distribution

with mean k-1 and dispersion (Opk2)-1, o = 10.

-40 -20 0 20 40 60 80 -8-4 -2 02468 10 -10 -6-6-4 -2 0246

Fig. 1.1 — Sparse GMM (k = 3,d = 2): Left: type 1; Center: type 2; Right: type 3.

In a sparse GMM, three main types of cluster behavior can be distinguished (consider the case k = 3,d = 2) (Fig. 1.1) due to the fact that often centroids lie close to zero. With such a data model, situations often arise when data from one cluster lie inside another, which makes the clustering procedure difficult. Authors of [36] used this approach to simulate many different noise distributions.

1.1.4 Method k-means

Despite the large number of diverse approaches to the clustering problem, algorithms based on minimizing the distances (or other values determining the dissimilarity of objects) between data elements and cluster centroids remain one of the most popular. (distance-based clustering or partition-based clustering). Among such approaches, the most popular is the k-means method [5; 92; 93]. It is looking for such a partition X that minimizes the sum of squares of intracluster distances. Each cluster is characterized by a corresponding centroid. All matrices r consider as unit. Then becomes (1.6) Euclidean distance. This task is NP-hard [94] and in the worst case, the time complexity of the algorithm is exponential [95]. Algorithm 1. k-means.

Input: X — data, k is a number of clusters, maximum number of iterations Output: 0 — centroids estimate, X — data partition 1: Initialization : n := 0. Randomly selected k initial centroids

00 = (go, 0§,..., g) from elements X. 2: Classification : i 2 l..k

Xn = {x 2 X : ||0n - x||2 6 ||gn - x||2, j 2 1..k} 3: Minimization : gn+1 = p^ny Pxj2X« Xj

4: Iteration : n := n + 1. Steps 2 and 3 are repeated until the centroids stop changing or the maximum number of iterations is reached. The advantages of the k-means method include:

— Ease of implementation.

— Convergence to the local minimum of the loss function (1.9).

— The rate of convergence to a local minimum. The disadvantages:

— The number of clusters k must be set in advance.

— Sensitivity to initialization and outliers in data.

— Processes all data at the same time.

Due to its advantages k-means algorithm has been widely used in many areas of data mining, such as bioinformatics [96; 97], text mining [98], computer vision [3; 99], feature learning in machine learning [100] etc.

1.1.5 Modifications of the k-means method

As noted in the previous section k-means algorithms has both advantages and disadvantages. One of these drawbacks is that the method needs all the data at the same time to process it. In practice, quite often a situation arises when the elements of the set X enter the system in turn: x1, x2, x3,.... To correct this drawback, several approaches were proposed based on the idea of learning "on the fly" (online learning), when centroids are iteratively recounted simultaneously with the arrival of new data.

The algorithm [101] uses mini-batches (subsamples from training data) to reduce the computational time required for convergence to a local solution, while minimizing the same objective function. The results obtained in this way are only slightly worse than the corresponding results of the original algorithm. Algorithm 2. Mini-batch k-means.

Input: X - data, k is a number of clusters, t is an iteration number, b is a size of mini-batch

Output: 6 — centroids estimate, X — data partition 1: Initialization : Randomly selected k initial centroids

60 = (§0, b0,..., §0) from elements X. 2: V = 0

3: for i = 1 to t do

4: Randomly select b examples from X. 5: for x 2 M do

6: l = l(6, r, x) — an index closest to x centroid. 7: d[x] = §i 8: end for 9: for x 2 M do

10: § = d[x]

11: v[§] = v[§] + 1

12: q=vk .

13: § = (1 - q)§ + qx 14: end for 15: end for

With a single size mini-batch b = 1, this algorithm processes the input data one by one.

Another important modification of the k-means algorithm is the k-medoids method [102; 103], which is more resistant to outliers and noise in the data. One of the popular implementations of this method is the algorithm Partitioning Around Medoids (PAM) [15]. By medoid is meant an object representing a cluster whose distances with all elements of the cluster are minimal. A medoid is an object from a cluster. Ia the case of the k-medoids in functional (1.9) 6^, i = 1..k are medoids.

Algorithm 3. k-medoids. Input: X — data, k is a number of clusters, maximum number of iterations Output: 0 — medoids estimate, X — data partition

1: Initialization : Randomly selected k initial medoids 0 = (g1, g2,..., g) from elements X.

2: Randomly selects a data point — not a medoid.

3: This point is made by a medoid instead of the nearest medoid.

4: If the value of the functional (1.9) since the new medoid has become smaller, then we leave this point as a medoid.

5: Iteration : Steps 2, 3, 4 are repeated until the medoids stop changing or the maximum number of iterations is reached.

The result of the k -means method depends largely on the initial values of the centroids 00 = (g°, g°,...,g). The original algorithm uses random initialization, which can lead to poor quality clustering. One of the common reasons for this result is the collapse of the clusters — a situation where several clusters are too close to each other, while others begin to include "extr" elements.

The idea of modification k-means++ [104] is that the initial centroids are iteratively selected so that they are as far apart as possible:

1. The first centroid is randomly selected from the data.

2. For each data element, the (Euclidean) distance to the nearest centroid is calculated.

3. A new centroid is selected among the data elements with a probability proportional to the square of the distance for this element from 2.

4. Steps 2 and 3 are repeated until k centroids are typed.

Using the k-means++ minimizes the possibility of collapse of clusters and allows for more stable clustering.

1.1.6 EM algorithm

The EM (expectation-maximization) algorithm [105; 106] is widely used in mathematical statistics and machine learning to find the parameters of a probabilistic model, for example, for thematic modeling [107]. It is based on maximizing likelihood when the model depends on hidden variables. The EM algorithm is traditionally used to estimate the parameters of a mixture of Gaussian distributions [3; 27] (in this case, the algorithm is denoted GMM-EM).

For simplicity, we consider the case of a two-component GMM with diagonal covariance matrices and variances a2, a^ In this case, according to (1.7)

f (6, r, x) = (1 - p)G(x|0i, a2) + pG(x|92, a2),

and the likelihood function takes the form