Дискретная оптимизация на основе управления ансамблем алгоритмов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Шаламов Вячеслав Владимирович

• Шаламов Вячеслав Владимирович
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Шаламов Вячеслав Владимирович

Реферат

Synopsis

Введение

Глава 1. Обзор предметной области

1.1. Задача оптимизации

1.2. Задачи машинного обучения и оценка качества их решения

1.2.1. Алгоритмы, параметры и гиперпараметры

1.2.2. Задача классификации

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

1.2.4. Меры качества кластеризации и их выбор

1.3. Задачи выбора и настройки алгоритмов

1.3.1. Выбор алгоритма

1.3.2. Оптимизация гиперпараметров алгоритма

1.3.3. Использование суррогатных функций

1.3.4. Автоматизация выбора алгоритмов и гиперпараметров

1.4. Обучение с подкреплением

1.4.1. Постановка задачи обучения с подкреплением

1.4.2. Задача о многоруком бандите и алгоритмы решения

1.5. Маршрутизация

1.5.1. Задача о погрузке и доставке и методы ее решения

1.5.2. Локальные изменения маршрута

1.6. Постановка цели и задач диссертации

Выводы по главе

Глава 2. Одновременный выбор и оптимизация гиперпараметров

алгоритма классификации

2.1. Задача распределения временного ресурса для оптимизации гиперпараметров и ее сведение к задаче о многоруком бандите

2.2. Определение функции выигрыша для задачи классификации

2.3. Использование априорных знаний в оптимизации гиперпараметров для алгоритмов классификации

2.3.1. Модификация метода байесовской оптимизации для оптимизации гиперпараметров

2.3.2. Описание экспериментов по ускорению оптимизации гиперпараметров в задачах классификации

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

Выводы по главе

Глава 3. Одновременный выбор и оптимизация гиперпараметров

алгоритма кластеризации

3.1. Оптимизация гиперпараметров алгоритмом SMAC

3.1.1. Стандартные алгоритмы решения задачи о многоруком бандите применительно к задаче кластеризации

3.1.2. Методы на основе алгоритма SMAC для задачи кластеризации

3.1.3. Использование внутреннего устройства SMAC в решении задачи о многоруком бандите

3.2. Инвертирование суррогатной функции для использования в задаче оптимизации гиперпараметров

3.2.1. Описание алгоритма

3.2.2. Эксперименты по настройке гиперпараметров

3.3. Экспериментальное исследование предложенных методов . . 125 Выводы по главе

Глава 4. Подход к оптимизации с использованием ансамбля оптимизационных алгоритмов

4.1. Определение процесса оптимизации

4.2. Компромисс между исследованием и использованием

4.3. Итеративное применение алгоритмов

4.4. Сведение задачи оптимизации к задаче о многоруком бандите 131 Выводы по главе

Глава 5. Построение маршрута в задаче о погрузке и доставке

5.1. Итерационное построение маршрута

5.2. Эволюционное построение маршрута

5.3. Комбинирование локальных изменений

5.3.1. Чистые стратегии

5.3.2. Смешанные стратегии

5.3.3. Стратегии, основанные на статистике

5.4. Экспериментальное исследование методов оптимизации маршрута

Выводы по главе

Заключение

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

Список иллюстраций

Список таблиц

Приложение А. Акт об использовании и внедрении результатов

диссертационного исследования

Приложение Б. Полученные графики

Приложение В. Таблицы с результатами

Приложение Г. Награды автора, полученные во время работы над

диссертацией

Приложение Д. Публикации автора по теме диссертации

Реферат

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

Общая характеристика работы

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

Компании стремятся решить свою задачу машинного обучения наиболее эффективно, что зачастую достигается с помощью выбора алгоритма машинного обучения и его гиперпараметров. Заранее неизвестно, какой алгоритм машинного обучения с большей точностью выдаст предсказание для данной задачи, что теоретически подтверждается №Ъ-теоремой [126].

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

Также системы автоматического машинного обучения создаются для решения задач обучения с учителем, в первую очередь — задачи классификации. По сравнению с ней, в задаче кластеризации отсутствуют метки объектов, а значит алгоритм кластеризации должен не только разбить объекты на группы, но и оценить качество разбиения. Дополнительной сложностью служит отсутствие методологических основ выбора оценки качества кластеризации. Данная тема подробно рассмотрена С. Б. Муравьевым [132] в его диссертации, а методы выбора гиперпараметров алгоритмов обучения без учителя исследовались ранее И. Р. Баймуратовым [129].

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

Автоматическое машинное обучение зародилось в 1990-х годах с разработкой алгоритма поиска по решетке [39] для оптимизации гиперпараметров алгоритмов классификации (например, выбор ядра в алгоритме SVM). Уже в начале 2000-х годов были предложены более эффективные стратегии оптимизации гиперпараметров для ограниченного пространства поиска [30; 33; 92]. В 2009 году впервые попытались выбрать модель алгоритма классификации вместе с настройкой полного конвейера для решения этой задачи [49]. Начиная с 2011 года стало активно развиваться направление байесовской оптимизации гиперпараметров [7; 114], в котором затратное вычисление качества алгоритма предлагается заменять вычислением значений суррогатной функции, аппроксимирующей целевую. Изначально в качестве неё брали гауссовский процесс [99], а затем регрессию случайного леса [28]. В 2013 году был предложен алгоритм выбора модели [20]. В 2017-2018 годах были созданы коммерческие AutoML системы [9; 57; 124] и были предложены более эффективные решения [66]. Системы для автоматического машинного обучения Auto-WEKA [18], Auto-WEKA 2.0 [19], TPOT [51], Auto-Skleam [44], Hyperopt-Skleam [78], ATM [14] а также пространство поиска и метод поиска для каждой из них приведены в таблице Р.1.

Кроме того, разработано много методов оптимизации гиперпараметров, их можно разделить на группы:

- Поиск по решетке — систематическое исследование пространства поиска, преобразованного к дискретным значениям.

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

- Последовательная оптимизация на основе модели (Sequential Modelbased Optimization, SMBO) [7; 64; 68] — итеративная оптимизация на основе теоремы Байеса. Вводится суррогатная функция (обычно гаус-совский процесс или случайный лес), которая заменяет вычисление качества модели с определенной конфигурацией гиперпараметров. Предполагается, что значение для неэффективных конфигураций будет вычисляться реже. Кроме того предложен метод древовидного Парзенов-ского оценщика (Tree-structured Parzen estimator, TPE) [7], оценивающего правдоподобие.

- Эволюционные алгоритмы [43; 49] — разнообразные методы, используемые для оптимизации в целом, для решения задачи оптимизации гиперпараметров требуют в несколько раз больше времени, чем альтернативные методы.

- Подходы, в основе которых лежит сведение задачи к задаче о многоруком бандите [47; 58], используют разбиение пространства поиска на подпространства.

- Градиентный спуск — итеративный алгоритм минимизации, который требует вычисления оптимизируемой функции f, что в общем случае неприменимо к оптимизации гиперпараметров, поэтому на f накладываются ограничения [82; 97].

Таблица Р.1 - Библиотеки для автоматического машинного обучения, клф -классификация, рг - регрессия.

Библиотека Год Задача Пространство поиска Метод

Auto-WEKA 2012 клф 39 алгоритмов классификации, с каждым связано 0-6 категориальных и 0-6 количественных гиперпараметров поиск по сетке

Auto-WEKA 2.0 2019 клф 39 алгоритмов классификации, с каждым связано 0-13 гиперпараметров перебор алгоритмов + SMAC для оптимизации гиперпараметров

ТРОТ 2016 клф 5 классификаторов генетический алгоритм

АШо^Ыеат 2015 клф, рг 15 классификаторов, всего 110 конфигураций мета-обучение для старта SMAC + ансамблирова-ние

Нурегор^ Skleam 2014 клф, рг 7 классификаторов, всего 53 гиперпараметра рандомизация + перебор

АТМ 2017 клф 14 классификаторов, с каждым связано 1 — 84 гиперпараметра полный перебор

Описанные методы реализованы во многих библиотеках настройки гиперпараметров, их обзор представлен в разделе 1.5 диссертации.

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

а) На момент начала исследований (в 2016 году) не было достаточно общей библиотеки автоматического машинного обучения.

б) Отдельно выбирается алгоритм и отдельно настраиваются его гиперпараметры.

в) Поиск в пространстве [алгоритмы х гиперпараметры] ресурсоёмок.

г) Алгоритмы оптимизации имеют смещения.

д) Не существует метода выбора и настройки алгоритма кластеризации, эффективного для конкретной задачи.

В данной работе предложим их решение.

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

Для достижения поставленной цели исследование предполагает решение следующих задач:

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

б) Разработать метод решения задачи классификации на основе выбора алгоритма из ансамбля.

в) Разработать метод решения задачи кластеризации на основе выбора алгоритма из ансамбля.

г) Предложить подход к оптимизации с использованием ансамбля оптимизационных алгоритмов.

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

е) Программно реализовать методы, изложенные выше.

ж) Разработать и провести экспериментальные исследования предложенных методов.

Объект исследования — задача машинного обучения в оптимизационной постановке.

Предмет исследования — совместные выбор и оптимизация гиперпараметров алгоритмов машинного обучения.

На защиту выносятся следующие основные положения, обладающие научной новизной:

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

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

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

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

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

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

Соответствие паспорту специальности. В соответствии с паспортом специальности 1.2.1 - «Искусственный интеллект и машинное обучение» диссертация относится к области исследований «16. Исследования в области специальных методов оптимизации, проблем сложность и элиминации перебора, снижения размерности».

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

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

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

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

а) The Genetic and Evolutionary Computation Conference (GECCO 2016), 2016 г., Денвер, Колорадо, США.

б) International Conference on Artificial Intelligence Applications and Innovations, 2016 г., Салоники, Греция.

в) Всероссийский конгресс молодых ученых Университета ИТМО, 2017 г., Университет ИТМО, Санкт-Петербург

г) International Conference on Machine Learning AutoML Workshop, 2017 г., Сидней, Австралия.

д) 7th International Young Scientists Conference, 2018 г., Ираклион, Греция.

е) Всероссийский конгресс молодых ученых Университета ИТМО,

2019 г., Университет ИТМО, Санкт-Петербург.

ж) XLIX Научная и учебно-методическая конференция Университета ИТ-МО, 2020 г., Университет ИТМО, Санкт-Петербург.

и) Всероссийский конгресс молодых ученых Университета ИТМО,

2020 г., Университет ИТМО, Санкт-Петербург.

к) L Научная и учебно-методическая конференция Университета ИТМО,

2021 г., Университет ИТМО, Санкт-Петербург.

л) Летняя конференция AIRI по искусственному интеллекту, 2022 г., Университет «Сириус», Сочи.

м) 11th International Young Scientists Conference, 2022 г., Университет ИТ-МО, Санкт-Петербург.

Награды. В ходе работы над диссертацией, автор был удостоен следующих наград:

- 2016 Gecco Student Workshop, 2е место на конкурсе лучших статей.

- 2019 Финалист Научной Премии Яндекса имени Ильи Сегаловича.

- 2020 Лауреат Научной Премии Яндекса имени Ильи Сегаловича.

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

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

Идея методов одновременного выбора алгоритма и оптимизации его гиперпараметров в задаче классификации и кластеризации на основе обучения с подкреплением принадлежит автору диссертации совместно с научным руководителем А.А. Фильченковым.

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

В публикации [112] идея применения обучения с подкреплением для выбора локальных изменений при построении маршрута принадлежит лично автору диссертации автору диссертации совместно с научным руководителем А.А. Фильченковым, разработка алгоритма и проведение экспериментов осуществлялось лично автором. А.А. Шалыто выступал научным консультантом.

В публикации [101] идея метода одновременного выбора алгоритма и оптимизации его гиперпараметров в задаче кластеризации на основе обучения с подкреплением, автору диссертации совместно с научным руководителем А.А. Фильченковым и С.Б. Муравьевым. Разработка алгоритма осуществлялась автором совместно с С.Б. Муравьевым. Реализация алгоритмов на базе предло-

женного метода и проведение вычислительных экспериментов принадлежит автору диссертации совместно с В.А. Ефимовой.

В публикации [111] идея принадлежит лично автору диссертации совместно с А.А. Фильченковым. Разработка алгоритмов, их реализация и проведение вычислительных экспериментов принадлежит лично автору диссертации. А.А. Шалыто выступал научным консультантом.

В публикации [110] идея совмещения эволюционного подхода и локальных изменений принадлежит лично автору диссертации. Реализация алгоритмов и проведение вычислительных экспериментов принадлежит лично автору диссертации. А.А. Фильченков и Д.В. Чивилихин выступали научными консультантами.

Публикации. Основное содержание диссертации опубликовано в семи статьях. Среди которых пять публикаций в изданиях, индексируемых в базах Web of Science или Scopus, одна публикация в журналах из перечня ВАК и один охранный документ на результат интеллектуальной деятельности.

Регистрация программ. Автором по теме диссертации были получены свидетельство о регистрации программы для ЭВМ: Программа выбора и настройки модели для решения задачи кластеризации на основе алгоритма оптимизации SMAC для ЭВМ/Шаламов В. В. [и др.]-№2019610924, опубл. 18.01.2019.

Объем и структура работы. Диссертация состоит из введения, пяти содержательных глав, заключения и приложения. Объем диссертации составляет 179 страниц, она содержит 13 рисунков и 15 таблиц. Список литературы содержит 139 наименований.

Содержание работы

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

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

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

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

с подкреплением (подробнее в разделе 1.4), а именно решений задачи о многоруком бандите, описываемой в подразделе 1.4.2.

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

В разделе 1.1 определяется задача оптимизации, приводится ее математическая постановка, описываются практические применения.

Оптимизация — это задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства. Задача дискретной оптимизации — это задача поиска максимума или минимума функции f, определенной на конечном или счетном множестве. То есть среди элементов х^ € X, найти такой элемент х*, который позволяет получить минимальное значение функции f (х*), где / : X ^ М.

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

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

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

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

Определение 2. Гиперпараметры алгоритма машинного обучения — это параметры, значения которых задаются до начала обучения алгоритма и не изменяется в процессе обучения.

В рамках настоящей работы выделим следующие понятия:

Гиперпараметрический алгоритм А — алгоритм машинного обучения с поставленным ему в соответствие набором гиперпараметров А и набором параметров ©. Примером гиперпараметрического алгоритма является многослойный перцептрон (гиперпараметры: число слоев, число нейронов на каждом слое, функция активации, метод обучения с присущими ему гиперпараметрами). Другим примером является однослойная нейронная сеть (гиперпараметры: число

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

Гиперпараметризованный алгоритм A\ — гиперпараметрическй алгоритм A с выбранными значениями всех гиперпараметров Л. Примером гипер-параметризованного алгоритма является многослойный перцептрон из прошлого примера с числом скрытых слоев, равным двум: тремя нейронами на первом слое, тремя нейронами на втором слое, функцией активации ReLU и гиперпара-метризированным методом оптимизации Adam. Обучение применимо только к гиперпараметризованным алгоритмам.

Обученный алгоритм A\,g — это гиперпараметризованный алгоритм A\ с выбранными значениями всех параметров в. Примером гиперпараметризован-ного алгоритма является гиперпараметризованный многослойный перцептрон из предыдущего примера с единичными значениями на всех ребрах.

Рассматривается задача классификации, заключающаяся в нахождении функции f : X ^ Y, где X — признаки, описывающие объекты, а Y — метки (классы), ассоциированные с каждым объектом. Гиперпараметризован-ный алгоритм A\ сопоставляет обучающей выборке D = d1,d2,...dn, где di = (Xi,yi) G X х Y, обученный алгоритм A\ e. Полученная в ходе обучения A\,eD может быть применен к любому объекту Xj G X, результатом чего является предсказание метки для этого объекта: A\,eD (xj) = yj [60]. Для оценки качества решения задачи классификации используются точность, полнота, Fi -мера, эмпирический риск и другие.

Рассматривается задача кластеризации, которая формально определяется как разбиение набора данных из векторов в F—мерном пространстве X = {x 1, X2,... ,xN } G RF. Результатом кластеризации X будет n дизъюнктных кластеров (подмножеств X), которые разбивают X на n групп: C = {c1, c2,..., cn}, где Uc eC cn,cn П ci = 0 V n = l. Также в подразделе 1.2.4 описываются разнообразные меры качества кластеризации.

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

Для машинного обучения задача выбора гиперпараметризованного алгоритма из ансамбля исследуется уже в течении трех десятилетий [102]. Изначально гиперпараметризованный алгоритм выбирали только в задаче классификации и для этого разрабатывались решающие правила [6]. Другим очевидным способом выбора элемента из множества стал случайный выбор [37]. Спустя несколько лет появились и другие способы как, например, выбор гипер-параметризованного алгоритма с помощью эвристических правил для конкретной задачи. Позже показал свою эффективность выбор гиперпараметризованно-го алгоритма с помощью k-стратового скользящего контроля (англ. k-fold cross-validation) [105]. K-стратовый скользящий контроль требует значительного времени, так как заключается в обучении всех гиперпараметризованных алгоритмов, после чего идет оценка результатов, достигаемых обученными алгоритмами на подвыборке набора данных. На данный момент разработаны более успешные

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

Пусть дан набор данных D и метрика качества решения задачи Q. Также будем считать, что задан набор (ансамбль) m гиперпараметризованных алгоритмов A = (A^ ,.., Am ) Необходимо выбрать гиперпараметризованный алгоритм Ад,, достигающий максимальной меры качества Q на данных D. В нашем случае — это задача минимизации эмпирического риска:

АД, е arg max Q(A{. д„ ,D).

Ai3 ел j

Известным теоретическим результатом в области является No Free Lunch (NFL) теорема, которая утверждает, что если не используется априорная информация о задаче, все функции имеют одинаковую производительность при усреднении по всем возможным задачам [126]. Как следствие, не существует единственного наилучшего алгоритма оптимизации, который бы подходил любой задаче больше, чем другие. Другое следствие: не существует и единственной наилучшей предсказательной модели машинного обучения для задач, таких как классификация и регрессия, не использующих априорные знания о задаче [125].

Задача оптимизации гиперпараметров заключается в подборе значений гиперпараметров гиперпараметрического алгоритма. Например, для метода ближайших соседей (kNN, k Nearest Neighbours) гиперпараметром может быть функция расстояния (евклидово, Махаланобиса и другие), а при использовании регрессии — степень полинома. Для некоторых статистических и регрессионных алгоритмов машинного обучения гиперпарметры подбирают аналитически или сводят задачу к более простой задаче оптимизации. Однако в общем случае гиперпараметры аналитически под конкретную задачу не подобрать.

Рассмотрим формальную постановку задачи оптимизации гиперпараметров в методологии машинного обучения. Пусть дан набор данных для обучения с учителем или без него D и метрика качества решения задачи Q. Также пусть задан гиперпараметрический алгоритм А, который может гипераметризован вектором из пространства Л и вектором параметров из пространства в. Оптимизация гиперпараметров заключается в подборе таких Л* е Л, при которых AA,,gD достигнет наилучшего качества на D:

Л* = argmax Q(Ax¿d ,D).

АеЛ

Среди алгоритмов оптимизации гиперпараметров можно выделить следующие: поиск по решетке (Grid Search) [24], случайный поиск (Random Search) [118], стохастический градиентный спуск [95], древовидный парзе-новский оценщик (Tree-structured Parzen estimator) [7] и байесовская оптимизация, к которой относится алгоритм последовательной оптимизации по модели (Sequental Model-Based Optimization, далее SMBO) [114].

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

Список литературы диссертационного исследования кандидат наук Шаламов Вячеслав Владимирович, 2023 год

Литература

1. Zhang G.P. Neural networks for classification: a survey // IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews). 2000. V. 30. N 4. P. 451-462. doi: 10.1109/5326.897072

2. Aly M. Survey on multiclass classification methods: Technical Report, Caltech. California Institute of Technology, 2005. 9 p.

3. Liaw A., Wiener M. Classification and regression by randomForest // R news. 2002. V. 2. N 3. P. 18-22.

4. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Science & Business Media, 2009. 745 p.

5. Van Der Malsburg C. Frank Rosenblatt: principles of neurodynamics: perceptrons and the theory of brain mechanisms // Brain Theory. Springer, 1986. P. 245-248. doi: 10.1007/978-3-642-70911-1_20

6. Муравьёв С.Б., Ефимова В.А., Шаламов В.В., Фильченвюв А.А., Сметанников И.Б. Автоматическая настройка гиперпараметров алгоритмов кластеризации с помощью обучения с подкреплением // Научно-технический вестник информационных технологий, механики и оптики. 2019. Т. 19. № 3. С. 508-515. doi: 10.17586/2226-1494-2019-19-3-508-515

7. Ефимова В.А., Фильченюэв А.А., Шалыто А.А. Применение обучения с подкреплением для одновременного выбора модели алгоритма классификации и ее структурных параметров // Машинное обучение и анализ данных. 2016. Т. 2. № 2. С. 244-254.

8. Yu T., Zhu H. Hyper-parameter optimization: A review of algorithms and applications // arXiv preprint. arXiv:2003.05689. 2020.

9. Chang C.-C., Lin C.-J. LIBSVM: A library for support vector machines // ACM Transactions on Intelligent Systems and Technology. 2011. V. 2. N 3. P. 27. doi: 10.1145/1961189.1961199

10. Pedregosa F., Varoquaux G., Gramfort A., Michel V., Thirion B., Grisel O., Blondel M., Prettenhofer P., Weiss R., Dubourg V., Vanderplas J., Passos A., Cournapeau D., Brucher M., Perrot M., Duchesnay E. Scikit-learn: Machine learning in Python // Journal of Machine Learning Research. 2011. V. 12. P. 2825-2830.

11. Bergstra J., Komer B., Eliasmith C., Yamins D., Cox D.D. Hyperopt: a Python library for model selection and hyperparameter optimization // Computational Science & Discovery. 2015. V. 8. N 1. P. 014008. doi: 10.1088/1749-4699/8/1/014008

References

1. Zhang G.P. Neural networks for classification: a survey. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2000, vol. 30, no. 4, pp. 451-462. doi: 10.1109/5326.897072

2. Aly M. Survey on multiclass classification methods. Technical Report, Caltech, California Institute of Technology, 2005, 9 p.

3. Liaw A., Wiener M. Classification and regression by randomForest. R news, 2002, vol. 2, no. 3, pp. 18-22.

4. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Science & Business Media, 2009, 745 p.

5. Van Der Malsburg C. Frank Rosenblatt: principles of neurodynamics: perceptrons and the theory of brain mechanisms. Brain Theory, Springer, 1986, pp. 245-248. doi: 10.1007/978-3-642-70911-1_20

6. Muravyov S.B., Efimova V.A., Shalamov V.V., Filchenkov A.A., Smetannikov I.B. Automatic hyperparameter optimization for clustering algorithms with reinforcement learning. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2019, vol. 19, no. 3, pp. 508-515. (in Russian). doi: 10.17586/2226-1494-2019-19-3-508-515

7. Efimova V.A., Filchenkov A.A., Shalyto A.A. Reinforcement-based simultaneous classification model and its hyperparameters selection. Machine Learning and Data Analysis, 2016, vol. 2, no. 2, pp. 244254. (in Russian)

8. Yu T., Zhu H. Hyper-parameter optimization: A review of algorithms and applications. arXiv preprint, arXiv:2003.05689, 2020.

9. Chang C.-C., Lin C.-J. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2011, vol. 2, no. 3, pp. 27. doi: 10.1145/1961189.1961199

10. Pedregosa F., Varoquaux G., Gramfort A., Michel V., Thirion B., Grisel O., Blondel M., Prettenhofer P., Weiss R., Dubourg V., Vanderplas J., Passos A., Cournapeau D., Brucher M., Perrot M., Duchesnay E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 2011, vol. 12, pp. 2825-2830.

11. Bergstra J., Komer B., Eliasmith C., Yamins D., Cox D.D. Hyperopt: a Python library for model selection and hyperparameter optimization.

12. Maclaurin D., Duvenaud D., Adams R. Gradient-based hyperparameter optimization through reversible learning // Proceedings 32nd International Conference on Machine Learning. 2015. P. 2113-2122.

13. Bergstra J.S., Bardenet R., Bengio Y., Kegl B. Algorithms for hyperparameter optimization // Advances in Neural Information Processing Systems: Proc. 5th Annual Conference on Neural Information Processing Systems (NIPS 2011). 2011. P. 2546-2554.

14. Gijsbers P., Vanschoren J., Olson R.S. Layered TPOT: Speeding up tree-based pipeline optimization // arXiv preprint. arXiv:1801.06007. 2018.

15. Fortin F.-A., De Rainville F.-M., Gardner M.-A., Parizeau M., Gagne C. DEAP: Evolutionary algorithms made easy // Journal of Machine Learning Research. 2012. V. 13. P. 2171-2175.

16. Hazan E., Klivans A., Yuan Y. Hyperparameter optimization: A spectral approach // arXiv preprint. arXiv:1706.00764. 2017.

17. Martinez-Cantin R. BayesOpt: A bayesian optimization library for nonlinear optimization, experimental design and bandits // Journal of Machine Learning Research. 2014. V. 15. P. 3735-3739.

18. Thornton C., Hutter F., Hoos H.H., Leyton-Brown K. Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms // Proc. 19th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD 2013). 2013. P. 847855. doi: 10.1145/2487575.2487629

19. Feurer M., Klein A., Eggensperger K., Springenberg J.T., Blum M., Hutter F. Efficient and robust automated machine learning // Advances in Neural Information Processing Systems. 2015. P. 2962-2970.

20. Bischl B., Richter J., Bossek J., Horn D., Thomas J., Lang M. mlrMBO: A modular framework for model-based optimization of expensive black-box functions // arXiv preprint. arXiv:1703.03373. 2017.

21. Probst P., Wright M.N., Boulesteix A.-L. Hyperparameters and tuning strategies for random forest // Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. 2019. V. 9. N 3. P. e1301. doi: 10.1002/widm.1301

22. Hutter F., Hoos H.H., Leyton-Brown K. Sequential model-based optimization for general algorithm configuration // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2011. V. 6683. P. 507-523. doi: 10.1007/978-3-642-25566-3_40

23. Feurer M., Hutter F. Hyperparameter optimization // Automated Machine Learning. Springer, 2019. P. 3-33. doi: 10.1007/978-3-030-05318-5_1

24. Springenberg J.T., Klein A., Falkner S., Hutter F. Bayesian optimization with robust Bayesian neural networks // Advances in Neural Information Processing Systems. 2016. P. 4141-4149.

25. Snoek J., Ripped O., Swersky K., Kiros R., Satish N., Sundaram N., Patwary M.M.A., Prabhat, Adams R.P. Scalable Bayesian optimization using deep neural networks // Proc. 32nd International Conference on Machine Learning (ICML). 2015. P. 2171-2180.

26. Klein A., Falkner S., Mansur N., Hutter F. RoBO: A flexible and robust bayesian optimization framework in Python // Proc. 31st Conference on Neural Information Processing Systems. 2017.

27. Mann H.B., Whitney D.R. On a test of whether one of two random variables is stochastically larger than the other // Annals of Mathematical Statistics. 1947. V. 18. N 1. P. 50-60.

Computational Science & Discovery, 2015, vol. 8, no. 1, pp. 014008. doi: 10.1088/1749-4699/8/1/014008

12. Maclaurin D., Duvenaud D., Adams R. Gradient-based hyperparameter optimization through reversible learning. Proceedings 32n International Conference on Machine Learning, 2015, pp. 2113-2122.

13. Bergstra J.S., Bardenet R., Bengio Y., Kégl B. Algorithms for hyperparameter optimization. Advances in Neural Information Processing Systems: Proc. 5th Annual Conference on Neural Information Processing Systems (NIPS2011), 2011, pp. 2546-2554.

14. Gijsbers P., Vanschoren J., Olson R.S. Layered TPOT: Speeding up tree-based pipeline optimization. arXiv preprint, arXiv:1801.06007, 2018.

15. Fortin F.-A., De Rainville F.-M., Gardner M.-A., Parizeau M., Gagne C. DEAP: Evolutionary algorithms made easy. Journal of Machine Learning Research, 2012, vol. 13, pp. 2171-2175.

16. Hazan E., Klivans A., Yuan Y. Hyperparameter optimization: A spectral approach. arXiv preprint, arXiv:1706.00764, 2017.

17. Martinez-Cantin R. BayesOpt: A bayesian optimization library for nonlinear optimization, experimental design and bandits. Journal of Machine Learning Research, 2014, vol. 15, pp. 3735-3739.

18. Thornton C., Hutter F., Hoos H.H., Leyton-Brown K. Auto-WEKA: Combined selection and hyperparameter optimization of classification algorithms. Proc. 19th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD 2013), 2013, pp. 847855. doi: 10.1145/2487575.2487629

19. Feurer M., Klein A., Eggensperger K., Springenberg J.T., Blum M., Hutter F. Efficient and robust automated machine learning. Advances in Neural Information Processing Systems, 2015, pp. 2962-2970.

20. Bischl B., Richter J., Bossek J., Horn D., Thomas J., Lang M. mlrMBO: A modular framework for model-based optimization of expensive black-box functions. arXiv preprint, arXiv:1703.03373, 2017.

21. Probst P., Wright M.N., Boulesteix A.-L. Hyperparameters and tuning strategies for random forest. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2019, vol. 9, no. 3, pp. e1301. doi: 10.1002/widm.1301

22. Hutter F., Hoos H.H., Leyton-Brown K. Sequential model-based optimization for general algorithm configuration. Lecture Notes in Computer Science (including subseries Lectur Notes in Artificial Intelligence and Lectur Notes in Bioinformatics), 2011, vol. 6683, pp. 507-523. doi: 10.1007/978-3-642-25566-3_40

23. Feurer M., Hutter F. Hyperparameter optimization. Automated Machine Learning. Springer, 2019, pp. 3-33. doi: 10.1007/978-3-030-05318-5_1

24. Springenberg J.T., Klein A., Falkner S., Hutter F. Bayesian optimization with robust Bayesian neural networks. Advances in Neural Information Processing Systems, 2016, pp. 4141^149.

25. Snoek J., Ripped O., Swersky K., Kiros R., Satish N., Sundaram N., Patwary M.M.A., Prabhat, Adams R.P. Scalable Bayesian optimization using deep neural networks. Proc. 322ndInternational Conference on Machine Learning (ICML), 2015, pp. 2171-2180.

26. Klein A., Falkner S., Mansur N., Hutter F. RoBO: A flexible and robust bayesian optimization framework in Python. Proc. 31s Conference on Neural Information Processing Systems, 2017.

27. Mann H.B., Whitney D.R. On a test of whether one of two random variables is stochastically larger than the other. Annals of Mathematical Statistics, 1947, vol. 18, no. 1, pp. 50-60.

Авторы

Смирнова Валентина Сергеевна — старший лаборант, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация; разработчик, ООО «Ю.Би.Си», Санкт-Петербург, 192019, Российская Федерация, ORCID: 0000-0002-4774-3624, [e-mail] Шаламов Вячеслав Владимирович — программист, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, Scopus ID: 57191077141, ORCID: 0000-0002-5647-6521, [e-mail] Ефимова Валерия Александровна — научный сотрудник, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, Scopus ID: 57207459404, ORCID: 0000-0002-5309-2207, [e-mail]

Фильченков Андрей Александрович — кандидат физиюэ-мате-матических наук, руководитель лаборатории, доцент, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, Scopus ID: 55507568200, ORCID: 0000-0002-1133-8432, [e-mail]

Authors

Valentina S. Smirnova — Senior Laboratory Assistant, ITMO University, Saint Petersburg, 197101, Russian Federation; Software Engineer, OOO U.B.C., Saint Petersburg, 192019, Russian Federation, ORCID: 0000-0002-4774-3624, [e-mail] Viacheslav V. Shalamov — Software Engineer, ITMO University, Saint Petersburg, 197101, Russian Federation, Scopus ID: 57191077141, ORCID: 0000-0002-5647-6521, [e-mail] Valeria A. Efimova — Researcher, ITMO University, Saint Petersburg, 197101, Russian Federation, Scopus ID: 57207459404, ORCID: 00000002-5309-2207, [e-mail]

Andrey A. Filchenkov — PhD, Laboratory Head, Associate Professor, ITMO University, Saint Petersburg, 197101, Russian Federation, Scopus ID: 55507568200, ORCID: 0000-0002-1133-8432, [e-mail]

УДК 004.021:004.852:004.832.23

Автоматическая настройка гиперпараметров алгоритмов кластеризации с помощью обучения с подкреплением

С.Б. Муравьев, В.А. Ефимова, В.В. Шаламов, А.А. Фильченков, И.Б. Сметанников

Аннотация

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

Ключевые слова

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

Благодарности

Работа выполнена при финансовой поддержке правительства Российской Федерации, субсидия 08-08 и РФФИ, грант 16-37-60115-мол_а_дк.

Automatic hyperparameter optimization for clustering algorithms with reinforcement learning

Sergey Muravyov, Valeria Efimova, Viacheslav Shalamov, Andrey Filchenkov, Ivan

Smetannikov

Abstract

Subject of Research. The paper deals with clustering algorithms hyperparameters optimization, used in machine learning.

Model selection problem was comprehensively studied, and the need of the tradeoff between exploration and exploitation was identified. Thus, the problem was reduced to multi-armed bandit problem. Method. In this work, the approach for simultaneous algorithm selection and hyperparameters optimization was proposed. We used solution of the Multiarmed Bandit problem and considered Softmax- and UCB1-based in combination of different reward functions. Main Results. Experiments on various datasets from UCI repository were conducted. The results of experiments confirmed that proposed algorithms in general achieve significantly better results than exhaustive search method. It also helped to determine the most promising version of the algorithm we propose. Practical Relevance. The suggested algorithm can be successfully used for model selection and tuning for clustering algorithms, can be applied in a wide range of clustering tasks in various areas, including biology, psychology, image analysis, and other.

Keywords

Machine learning, clustering, algorithm selection, hyperparameter optimization, multi-armed bandit, reinforcement learning

Acknowledgements

This work was financially supported by the Government of Russian Federation, grant 08-08 and the Russian Foundation for Basic Research, Grant 16-37-60115 mol_a_dk.

Введение

Задача кластеризации заключается в разбиении множества объектов на подмножества похожих между собой объектов. Кластеризация нацелена на обнаружение

естественных структур в данных [1-4]. Задача кластеризации возникает во многих областях, среди которых биология [4], психология [5], обработка изображений [6], распознавание образов [3], компьютерная безопасность [7] и других.

В случае применения кластеризации на практике нужно оценивать полученные кластеры с точки зрения исследуемой предметной области и определять, передают ли они истинные связи между объектами [8]. Считается, что не существует четкого и однозначного определения кластера [9, 10]. Было предложено множество методов анализа кластеров, но в большинстве таких исследований авторы не определяют четко, что же их метод должен обнаруживать, и не дают формального определения истинных кластеров [11].

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

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

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

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

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

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

Задача выбора модели алгоритма и ее гиперпараметров в общем случае формально записывается как поиск модели алгоритма который бы минимизировал :

где — набор моделей алгоритмов, с каждой из которых связано пространство гиперпараметров , , ..., соответственно.

Рассмотрим существующие способы решения задачи выбора модели. Одним из них является мета-обучение. Данный подход включает в себя построение мета-

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

Выбору числа кластеров посвящены многие работы, как в общем случае [15, 16], так и для конкретного алгоритма [17]. Число кластеров выбирается в соответствии с характеристиками набора данных или же разбирается результат работы алгоритма. Статей по настройке других гиперпараметров не найдено. Также были изучены современные исследования по теме кластеризации, но автоматический выбор модели кластеризации и оптимизация ее гиперпараметров нигде не описан.

Заметим, что в задаче классификации для выбора модели и настройки ее гиперпараметров было создано несколько подходов: Auto-WEKA [18], Tree-based Pipeline Optimization Tool (TPOT) [19], auto-sklearn [20], в том числе это происходит и методами обучения с подкреплением [21]. Кроме того, библиотека Auto-WEKA 2.0 поддерживает выбор модели в задаче регрессии [22].

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

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

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

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

Разделение на кластеры

Рис. 1. Схема базового метода настройки гиперпараметров.

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

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

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

Поиск подобного компромисса является задачей обучения с подкреплением. Для его осуществления исходная задача сводится к задаче о многоруком бандите [23]. В задаче о многоруком бандите рассматривается агент с ручками, с каждой из которых связано некоторое неизвестное распределение. В течение хода агент выбирает ручку и получает случайную награду из связанного с ней распределения. Цель агента — максимизировать полученную за k итераций награду.

Пусть задан некоторый временной бюджет T на поиск лучшего алгоритма Требуется разбить его на интервалы таким образом, что при запуске процессов с ограничением по времени мы получим значение функции качества Q такое, что: , где и , В этом случае каждой ручке алгоритма многорукого бандита соответствует определённая модель алгоритма кластеризации из конечного множества А, а вызову ручки i на итерации k — процесс оптимизации гиперпараметров этой модели в течение времени . В результате будет достигнуто качество кластеризации , определяемое с помощью меры, оно и задает награду, получаемую по завершении итерации. Схема метода представлена ниже (рис. 2).

Рис. 2. Схема предложенного метода настройки гиперпараметров.

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

Здесь мы не рассмотрели выбор следующей ручки для запуска. Изначально этот шаг определялся с помощью известных алгоритмов решения задачи о многоруком бандите — Softmax и UCB1 [23]. Кроме того, значение суммарной награды ручки было заменено на значение средней награды, что при экспериментах обозначим RL-smx-tf, такое определение награды позволило убрать прямую зависимость от номера итерации.

Были предложены и другие методы определения следующей ручки на основе внутреннего устройства алгоритма SMAC [12], а именно ожидаемого улучшения (expected improvement, EI) и свойств случайного леса. В ходе работы SMAC оценивает конфигурации с помощью ожидаемого улучшения, значения которого предсказывает случайный лес.

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

где и

То есть R — вектор наград, получаемых каждой ручкой обучения с подкреплением, U — вектор поправок, которые вносятся в соответствии с затраченным временем, а S — функция нормализации, аналогичная той, что используется внутри алгоритма Softmax.

Описание экспериментов

В экспериментах участвовало 7 моделей алгоритмов: k-Means, DBSCAN, Affinity Propagation, Agglomerative Clustering, Mean Shift, Gaussian Mixture, Bayesian Gaussian Mixture. Эксперименты проводились на наборах реальных данных, находящихся в репозитории UCI и доступных по ссылке1. Для экспериментов использовалось шесть мер оценки разбиения: Calinski-Harabaz (CH), Sillhouette (Sil), sym, gd41, os, cop. CH и Sil были выбраны на основании проведенного исследования времени вычисления как требующие самых незначительных временных ресурсов [24]. Другие были выбраны согласно статье [25], так как они лучше всего соответствуют когнитивными представлениями людей-асессоров. В исследовании использован алгоритм оптимизации гиперпараметров SMAC, который минимизирует значение целевой функции, поэтому эксперименты нацелены на минимизацию меры качества. Значения некоторых мер увеличиваются с ростом качества, в этом случае они брались с противоположным знаком, что в данном случае равносильно. Следовательно, во всех последующих таблицах лучшим является меньшее значение.

Эксперименты запускались через систему slurlm2, предназначенную для проведения экспериментов и управления ресурсами, из-за чего случайным образом распределялись планировщиком между серверами с 64-ядерными процессорами AMD Opteron 6378 @ 2.4 GHz, 256 GB RAM и AMD Opteron 6380 @ 2.5 GHz, 496 GB RAM. Все вычисления производились в один поток, на который выделялось до 2 Гб оперативной памяти.

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

В итоговое сравнение для наглядности было включено сравнение с качеством, достигаемым алгоритмами с параметрами по умолчанию. Кроме того, в него были включены случайный поиск (random search, RS), последовательный метод (exhaustive search, EX) и четыре предложенных вариации обучения с подкреплением.

Изначальный вариант обучения с подкреплением обозначим RL (reinforcement learning) — предложенный подход на основе решения задачи о многоруком бандите с алгоритмом Softmax по нормализованным мерам и времени.

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

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

1 http://archive.ics.uci.edu/ml/index.php

2 https://slurm.schedmd.com

Рис. 3. Графики зависимостей значения меры от затраченного времени. Линии на графике обозначают среднее значение целевой функции для каждого метода, затененная соответствующим цветом область — доверительный интервал, а треугольные символы — минимум и максимум из значений при данном временном бюджете.

Табл. 1. Численные значения мер при значении временного бюджета . RL-smx-tf — предложенный подход на основе решения задачи о многоруком бандите с алгоритмом Softmax. RL-max-EI — предложенный подход на основе решения задачи о многоруком бандите с алгоритмом иСВ1. Жирным шрифтом отмечен минимальный результат.

Мер а Набор данных По умолчанию RS EX RL RL-max-EI RL-smx-tf

ch iris 278,8425 -250,3009 -281,3849 -281,3849 -281,3849 -281,3849

ch glass 101,4215 -128,2044 -177,7988 -177,7988 -176,5833 -177,7988

ch wholesal e 720,3281 -841,9137 -937,1773 -937,1773 -930,7756 -937,1773

ch idiabets 196,5603 -129,1122 -222,7155 -236,3504 -194,1084 -223,7569

ch yeast 264,5704 -220,0934 -296,1348 -313,8025 -275,7446 -295,4888

ch krvskp 266,6803 -167,3435 -239,7293 -257,6422 -192,4901 -243,5241

sil iris -0,60186 -0,512 -0,6019 -0,6019 -0,6002 -0,6019

sil glass -0,4987 -0,5042 -0,5515 -0,5515 -0,5471 -0,5515

sil wholesal e -0,69 -0,6432 -0,6897 -0,6897 -0,6828 -0,6897

sil idiabets -0,2759 -0,3226 -0,485 -0,5082 -0,42 -0,4973

sil yeast -0,6032 -0,4961 -0,579 -0,6531 -0,4919 -0,6019

sil krvskp -0,1378 -0,0935 -0,1774 -0,205 -0,1077 -0,1794

sym iris -0,0018 -0,0022 -0,0026 -0,0026 -0,0025 -0,0026

sym glass -0,0014 -0,0012 -0,0016 -0,0016 -0,0016 -0,0016

sym wholesal e -0,0007 -0,0014 -0,0023 -0,0023 -0,002 -0,0021

sym idiabets -0,0004 -0,0029 -0,0045 -0,0045 -0,0031 -0,0045

sym yeast -0,0003 -0,0002 -0,0003 -0,0004 -0,0003 -0,0003

sym krvskp -0,0002 -0,0001 -0,0001 -0,0002 -0,0001 -0,0001

gd41 iris -0,9115 -1,033 -1,1794 -1,1794 -1,171 -1,1794

gd41 glass -1,0928 -1,2415 -1,3835 -1,3891 -1,3625 -1,3891

gd41 wholesal e -1,2480 -0,6553 -1,1417 -1,248 -0,9297 -1,1442

gd41 idiabets -1,4944 -1,0303 -1,5209 -1,6061 -1,2516 -1,5074

gd41 yeast -1,4082 -0,7502 -1,1374 -1,414 -1,0358 -1,1901

gd41 krvskp -1,1774 -0,6604 -0,6958 -0,7591 -0,4739 -0,7528

os iris -32,3439 -2156,962 -3117,5877 -3106,3131 -3121,1775 -3121,1775

os glass 491,5247 -665,8316 -870,8715 -889,9995 -862,5762 -864,0331

os wholesal e -62,2361 -4084,9359 -6017,3197 -6135,9152 -4793,4681 -5253,2299

os idiabets 15642,84 -20453,783 -27841,9049 -29445,211 -24058,733 -24574,1892

os yeast 863,8433 -17632,971 -21663,9475 -18411,641 -19935,217 -20804,6337

os krvskp -300,551 -6949,9832 -6920,002 -5628,3257 -7117,0635 -5951,1009

cop iris 0,605 2,3603 0,605 0,605 0,9535 0,605

cop glass 2,2106 2,5235 0,6639 0,6173 1,8419 0,6173

cop wholesal e 1,9267 3,1852 1,4982 0,8767 2,3827 1,27

cop idiabets 1,8873 3,2621 1,6182 1,1682 2,4276 1,4847

cop yeast 2,3059 7,8689 5,5026 3,3133 6,3696 4,748

cop krvskp 1,6455 2,3082 2,0637 1,8845 2,1271 1,8385

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

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

Заключение

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

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

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

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

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

Литература

1. Halkidi, M., Batistakis, Y., Vazirgiannis, M., 2001. On clustering validation techniques. Journal of intelligent information systems, 17(2-3), pp.107-145.

2. Jain, A.K., Dubes, R.C., 1988. Algorithms for clustering data.

3. Mirkin, B., 2005. Clustering for data mining: a data recovery approach. Chapman, Hall/CRC.

4. Sneath, P.H., Sokal, R.R., 1973. Numerical taxonomy. The principles and practice of numerical classification.

5. Holzinger, K.J., Harman, H.H., 1941. Factor analysis; a synthesis of factorial methods.

6. Chou, C.H., Su, M.C., Lai, E., 2004. A new cluster validity measure and its application to image compression. Pattern Analysis and Applications, 7(2), pp. 205-220.

7. Barbará, D., Jajodia, S. eds., 2002. Applications of data mining in computer security (Vol. 6). Springer Science & Business Media.

8. Guyon, I., Von Luxburg, U., Williamson, R.C., 2009, November. Clustering: Science or art. In NIPS 2009 workshop on clustering theory (pp. 1-11).

9. Aggarwal, C.C., Reddy, C.K. eds., 2013. Data clustering: algorithms and applications. CRC press.

10. Fraley, C., Raftery, A.E., 1998. How many clusters? Which clustering method? Answers via model-based cluster analysis. The computer journal, 41(8), pp. 578-588.

11. Hennig, C., 2015. What are the true clusters?. Pattern Recognition Letters, 64, pp. 53-62.

12. Hutter, F., Hoos, H.H., Leyton-Brown, K., 2011, January. Sequential model-based optimization for general algorithm configuration. In International Conference on Learning and Intelligent Optimization (pp. 507-523). Springer, Berlin, Heidelberg.

13. Pal, N.R., Biswas, J., 1997. Cluster validation using graph theoretic concepts. Pattern Recognition, 30(6), pp. 847-857.

14. Ferrari, D.G., De Castro, L.N., 2015. Clustering algorithm selection by meta-learning systems: A new distance-based problem characterization and ranking combination methods. Information Sciences, 301, pp. 181-194.

15. Tibshirani, R., Walther, G., Hastie, T., 2001. Estimating the number of clusters in a data set via the gap statistic. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 63(2), pp. 411^423.

16. Sugar, C.A., James, G.M., 2003. Finding the number of clusters in a dataset: An information-theoretic approach. Journal of the American Statistical Association, 95(463), pp.750-763.

17. Pelleg, D., Moore, A.W., 2000, June. X-means: Extending k-means with efficient estimation of the number of clusters. In Icml (Vol. 1, pp. 727-734).

18. Thornton, C., Hutter, F., Hoos, H.H., Leyton-Brown, K., 2012. Auto-WEKA: Automated selection and hyper-parameter optimization of classification algorithms. CoRR, abs/1208.3719.

19. Olson, R.S., Bartley, N., Urbanowicz, R.J., Moore, J.H., 2016, July. Evaluation of a tree-based pipeline optimization tool for automating data science. In Proceedings of the Genetic and Evolutionary Computation Conference 2016 (pp. 485^92). ACM.

20. Feurer, M., Klein, A., Eggensperger, K., Springenberg, J., Blum, M., Hutter, F., 2015. Efficient and robust automated machine learning. In Advances in Neural Information Processing Systems (pp. 2962-2970).

21. Ефимова, В.А., Фильченков, А.А., Шалыто, А.А., 2016. Применение обучения с подкреплением для одновременного выбора модели алгоритма классификации и ее структурных параметров. Машинное обучение и анализ данных, 2(2), С .244-254.

22. Kotthoff, L., Thornton, C., Hoos, H.H., Hutter, F., Leyton-Brown, K., 2017. Auto-WEKA 2.0: Automatic model selection and hyperparameter optimization in WEKA. The Journal oof Machine Learning Research, 15(1), pp. 826-830.

23. Sutton, R.S., Barto, A.G., 1998. Introduction to reinforcement learning (Vol. 135). Cambridge: MIT press.

24. Arbelaitz, O., Gurrutxaga, I., Muguerza, J., Pérez, J. M., Perona, I., 2013. An extensive comparative study of cluster validity indices. Pattern Recognition, 46(1), pp. 243-256.

25. Filchenkov, A., Muravyov, S., Parfenov, V., 2016, November. Towards cluster validity index evaluation and selection. In Artificial Intelligence and Natural Language Conference (AINL), IEEE (pp. 1-8). IEEE.

Available online at www.sciencedirect.com

ScienceDirect

Procedia Computer Science 00 (2017) 000-000

www.elsevier.com/locate/procedia

7th International Young Scientists Conference in HPC and Simulation, YSC 2018, 2-6 July, 2018 Heraklion, Greece

Reinforcement-based Method for Simultaneous Clustering Algorithm Selection and its Hyperparameters Optimization

Viacheslav Shalamov^*, Valeria Efimovaa, Sergey Muravyova, Andrey Filchenkova

aITMO University, 197101, 49 Kronverksky pr., St Petersburg, Russia

Abstract

A wide range of clustering algorithms exists, most of them expose many hyperparameters, on which clustering partition quality depends. Simultaneous algorithm (model) selection and its hyperparameters optimization is considered to be a sophisticated task, which is known according to some sources as combined algorithm selection and hyperparameter optimization. In this paper, we focus on problem of selecting a clustering algorithm and its hyperparameter vector simultaneously given a dataset in order to achieve the best partition quality. We propose a method for selecting a proper clustering algorithm and its hyperparameter vector using reinforcement learning. Instead of tuning hyperparameters for all available clustering algorithms and selecting one showing the best performance, we make them to compete for time that they can use for optimizing their own hyperparameters. In our algorithm, we use a framework for multi-armed bandit problem, which is a special case of reinforcement learning. Each clustering algorithm is considered as an arm in the multi-armed bandit setting, while assigning a time budget to optimize hyperparameters of a clustering algorithm is considered as playing the corresponding arm. We conducted series of experiments for comparing out reinforcement learning approach to the classical exhaustive search approach. We conducted experiments on 20 datasets from UCI Repository such as Iris, haberman, krvskp, glass and other. We use 19 cluster validity indices to validate the clusters, built by selected and configured algorithm. As a hyperparameter optimization algorithm, we used SMAC. Our approach managed to improve model selection and hyperparameter optimization process, by sustaining the exploration-exploitation trade-off and spending available time budget more wisely.

© 2017 The Authors. Published by Elsevier B.V.

Peer-review under responsibility of the scientific committee of the 6th International Young Scientist conference in HPC and Simulation.

Keywords: clustering; algorithm selection; hyperparameter optimization; multi-armed bandit; reinforcement learning;

1. Introduction

Clustering is a ubiquitous data analysis tool, applied in virtually all disciplines. The goal of clustering is to divide a set of objects into meaningful groups called clusters. Nowadays, the data collected from different areas represents one

* Corresponding author E-mail address: [e-mail]

1877-0509 © 2017 The Authors. Published by Elsevier B.V.

Peer-review under responsibility of the scientific committee of the 6th International Young Scientist conference in HPC and Simulation.

of the biggest and most interesting information sources, so their processing deliver hidden knowledge to professionals as patterns form, this allows to use it in crucial processes like medicine, financial operations and purchase trends analysis [15].

Many clustering algorithms and their variations exist, such as KMeans, Affinity Propagation, DBSCAN, Agglom-erative Clustering, Mean Shift, Gaussian Mixture, Variational Bayesian estimation of a Gaussian mixture, Spectral Clustering, Birch and many others. It is well known that no single algorithm achieves the best performance over all instances of a problem class [28, 27, 32].

Rice [25] has formulated the Algorithm Selection Problem (ASP), which is to select the best algorithm from an algorithm set that will show the best performance with respect to a performance criterion on a given problem without running all the algorithms from the set. The ASP is considered an NP-hard problem and has been tackled in different research fields [8, 24].

Assuming, that we have already somehow chosen the algorithm itself, we still have to optimize its hyperparameters to make it learn from data its structure. Optimizing hyperparameters of a clustering algorithm belongs to Algorithm configuration problem. Algorithm configuration trades human time for machine time and automates a task that would otherwise be performed manually. End users of an algorithm can also apply algorithm configuration procedures to configure an existing algorithm for high performance on problem instances of interest.

The algorithm configuration problem can be formally stated as follows: given a parameterized algorithm A (the target algorithm), a set (or distribution) of problem instances I and a cost metric c, find parameter settings of A that minimize c on I. The cost metric c is often based on the runtime required to solve a problem instance, or, in the case of optimization problems, on the solution quality achieved within a given time budget. Various automated procedures have been proposed for solving this algorithm configuration problem. Existing approaches differ in whether or not explicit models are used to describe the dependence of target algorithm performance on parameter settings.

Model-free algorithm configuration methods are relatively simple, can be applied out-of-the-box, and have recently led to substantial performance improvements across a variety of constraint programming domains. This research goes back to the early 1990s [22, 13] and has lately been gaining momentum. Some methods focus on optimizing numerical (i.e., either integer- or real-valued) parameters (see, e.g., [7, 1, 4]), while others also target categorical (i.e., discrete-valued and un-ordered) domains [16]. The most prominent configuration methods are the racing algorithm F-RACE [5], iterated local search algorithm PARAMILS [20, 19] and genetic algorithm GGA [2]. Recent progress in model-based approaches promises to lead to the next generation of algorithm configuration procedures. Sequential model-based optimization (SMBO) [17] iterates between fitting models and using them to make choices about new configurations to investigate. It offers the balance between exploration the search space and exploitation most promissing configurations. It can also be used to quantify importance of each parameter and parameter interactions. However, SMBO has inherited a range of limitations inappropriate to the automated algorithm configuration setting. Thus, there is a more sophisticated Sequential Model-based Algorithm Configuration (SMAC) method [18].

Simultaneous algorithm (model) selection and its hyperparameters optimization is considered to be a sophisticated task, which is known according to some sources as Combined Algorithm Selection and Hyperparameter optimization (CASH) [31]. The success of using machine learning in different areas leads to increased demand of systems, which can be used "out-of-the-box", without involving experts to run them. Modern research is focused on this problem of automated machine learning, the AutoML.

There is an open library for algorithm selection and hyperparameter optimization called Auto-WEKA [31], which implements a brute force approach. This library allows to automatically choose the best classification or regression algorithm out of fixed portfolio, simultaneously optimizing its hyperparameters using SMAC [18]. Unfortunately, this approach is relatively slow, because of the brute force. Furthermore, there is no clustering algorithms support in it.

Another library in that area is auto-sklearn [11]. First, authors use meta-learning, using features and meta-features of the dataset to rank models (algorithms). After that, authors use Bayesian optimization approach to perform algorithm configuration for the top-ranked models.

Furthermore, there is a Tree-based Pipeline Optimization Tool (TPOT) [23]. It is based on applying pipelines of optimization, which are arranged as a tree. As the results of their research show, this approach appears to be not much effective, but it takes relatively small amount of resources (time and computation power) to be run.

In the last decade, meta learning approach for that task is growing too [21]. There was meta-learning approach [6, 29] suggested for CASH task, but in this case, algorithm portfolio was fixed.

Several papers are devoted to full-model search [10, 12, 26]. Most of them use evolutionary algorithms and feature processing without paying much attention to hyperparameter optimization.

Despite of plenty works devoted to hyperparameter optimization problem, there is no work considering clustering algorithms among them. To the best of authors' knowledge, no research about clustering algorithms selection and hyperparameter optimization exist.

In this paper, we propose reinforcement learning-based approach for simultaneous model selection and hyperparameter optimization.

The remainder of this paper is organized as follows. In Sectionv2, we describe in details of the learning algorithm and its hyperparameter selection problem. The suggested method, based on multi-armed bandit problem, is presented in Section3. In Section 4, experiment results are presented and discussed. In Section 5 we summarize the results, provides some conclusions and insight we got from that series of experiments and outline the future work.

2. Problem Statement

Selection of the best hyperparameter vector for an algorithm, which is called algorithm configuration problem, can be formally stated as follows: given a parameterized algorithm, a set (or distribution) of problem instances and a performance measure, find parameter settings of the algorithm that minimize the performance measure on given instances. The existing approaches to solve this problem differ in whether or not explicit models are used to describe the dependence of target algorithm performance on parameter settings.

The following is a formal description of the algorithm and its hyperparameters selection problem.

Let A be a hyperparameter space related to a learning algorithm A. We will denote the algorithm with preselected hyperparameter vector A € A as Aa.

We are given a set of algorithms (models) without hyperparameters A = {A1,..., Am} and a unlabelled dataset D = {dj,..., dn}. We should choose a parametrized algorithm A A* that is the most efficient with respect to a quality measure Q.

Quality is estimated with one of 20 clustering validity indexes. Their description and mathematical formulation you can find in [3].

Hyperparameter optimization is the process of selecting hyperparameters A* € A of a learning algorithm A to optimize its performance. Therefore, we can write:

A* € argmin Q(Aa, D).

In this paper, we consider simultaneous algorithm selection and hyperparameters optimization. Each learning algorithm A1 is associated with hyperparameter space Ai. The goal is to find algorithm A'a* minimizing the measure Q:

A A* € arg min Q(Aj, D).

A AieA.AeAi A

We assume that hyperparameter optimization is performed during sequential hyperparameter optimization process. Let us give formal description. Sequential hyperparameter optimization process for a learning algorithm Ai:

ni(t, A1, {A)})=0) ^ Ak+1 € Ai.

It is a hyperparameter optimization method run on the clustering algorithm Ai with time budget t, also it stores best found hyperparameter vectors within previous k iterations {Aj}k=0.

All of the hyperparameter optimization methods listed in the introduction can be described as a sequential hyperparameter optimization process, for instance, Grid Search or any of SMBO algorithm family including SMAC method, which is used in this paper.

Suppose that a sequential hyperparameter optimization process ni is associated with each clustering algorithm Ai. Then the previous problem can be solved by running all these processes. However, a new problem arises: time minimization problem for the best algorithm search. In practice, there is a similar problem that is more interesting in practical terms. It is the problem of finding the best algorithm in fixed time. Let us describe it formally.

Let T be a time budget for the best algorithm A'a, searching. We should split T into intervals T = t1 + • • • + tm such that if we run process ni with time budget ti we will get minimal Q.

min Q(A{ , D)-> min,

j *' (tl.....tm)

where Aj € A ,Aj = nj(tj, Aj, 0) and tj + ... + tm = T; ti > 0 Vi.

Thus, there is a problem of splitting those budgets between optimization processes.

3. Approach

In this problem, the key source is hyperparameter optimization time limit T. Let us split T up to q equal small intervals with duration t and call them time budgets. Now we can solve time budget assignment problem. Let us have a look at our problem in a different way. For each time interval we should choose a process to be run during this interval before this interval starts.

On one hand, it cannot be known in advance, what performance will be shown by algorithms on a particular task. By spending all the resources on tuning the best algorithm hyperparameters, we can miss other algorithms which can become even better after proper hyperparameter optimization. On the other hand, when we spread resources equally on each algorithm, too much resources will be wasted on unpromising algorithms. Thus, the point is to maintain balance between exploration and exploitation [14], between tuning currently best algorithms and trying others.

In our algorithm, we use a framework for Multi-Armed Bandit problem, which is a special case of Reinforcement Learning [30]. Multi-Armed bandit problem is formulated as follows. There is a slot-machine (the bandit) with N arms. Playing each of the arms grants a certain reward. This reward is chosen according to an unknown probability distribution, specific to this arm. At each iteration k, an agent chooses an arm ai and get a reward r(i, k). The agent's goal is to minimize the total loss by time T. In this paper, we use the Softmax algorithm for solving this problem [30].

As stated above, in order to spend resources rationally, the algorithm has to maintain balance between tuning particular algorithm and trying others. Consider an arm of multi-armed bandit to represent an algorithm (a model), and playing the arm corresponds to running hyperparameters optimization process for some time. The reward for that play will be the proportional to what the algorithm can achieve after hyperparameter optimization.

In this paper, we associate arms with sequential hyperparameters optimization processes {ni(t, A', {^k}q=0) ^ ^q+1 € A^^ for learning algorithms A = {A1,..., Am}. After playing arm i = ak at iteration k, we assign time budget t to a process nak to optimize hyperparameters. When time budget runs out, we receive hyperparameter vector A'k. Finally, when the selected process stops, we evaluate the result using empirical risk estimated for the process ni at iteration k, that is Q(A', , D).

The suggested algorithm MASSCAH (Multi-armed simultanous selection of clustering algorithm and its hyperparameters) is presented Algorithm 1. There, MABSolver is implementing a multi-armed bandit problem solution, getConeig(') is a function that returns A'x , which is the best found configuration by q iterations to algorithm

a'.

Data: D is the given dataset, q is the number of iterations, t is time budget for one iteration,

{njNj are sequential hyperparameter optimization processes. Result: Лл is algorithm with chosen hyperparameters

for i = 1,..., N do

л ^ ni(t, Ai, 0) Ei ^0U Q(Air D)

best^err ^ mini=i.....n ei

best_proc ^ arg mini=i.....n ei

for j = i, . . . , q do

i ^ MABSoLVER({Ei}i=1.....N)

Л ^ ni(t,Ai, Ш^) e ^ Q(A\, D) Ei ^ Ei U e

if e < best^err then best^err ^ e best_proc ^ i

end

end

return GETC0NFIG(nb„st_proc)

Algorithm 1: MASSCAH (Multi-armed simultanous selection of clustering algorithm and its hyperparameters)

4. Experiments

Experiments were performed on 20 different real datasets from UCI repository1. We didn't use some specific criteria to select datasets, but we made them vary in size and number of features. These datasets characteristics are presented in Table 1.

The suggested approach allows to use any hyperparameter optimization method. We use SMAC method. We consider 7 well-known clustering algorithms: KMeans (1 categorical and 6 numerical hyperparameters), Affinity Propagation (0 and 3), Mean Shift (0 and 4), Agglomerative Clustering (3 and 1), DBSCAN (1 and 3), Gaussian Mixture (1 and 4), and Bayesian Gaussian Mixture (1 and 6).

As we have previously stated, we are given time T to find the solution of the main problem. The suggested method requires splitting T into small equal intervals t. We give the small interval to a selected process ni at each iteration.

In previous paper [9] we compare the method performance for different time budget t values to find the optimal value. We use time budget t = 10 seconds.

To estimate clustering algorithms quality we use 19 most popular and reasonable clustering validity indexes: Dunn index, CalinskiHarabasz index, C-Index, DaviesBouldin index, Silhouette index, Generalized Dunn indices (gD31, gD41, gD51, gD33, gD43, gD53), S_Dbw index, CS index, DaviesBouldin*, Score function, Sym-index, COP index, SV-Index, OS-Index[3].

The general time limitation is T = 25 minutes, as at previous paper. We run each configuration 5 times with random seeds of SMAC algorithm. The comparison of the average results is shown in Table 1 full comparison is shown in appendix.

As can be seen from the table, suggested method appears to be better than old solution (Exhaustive Search) on 15 datasets out of 20. On one dataset, our solutions is indistinguishable from old solution. On the last 4 datasets, our method appears to be worse, but it is due to size and structural properties of that datasets.

1 http://www.cs.ubc.ca/labs/beta/Projects/autoweka/datasets/

Table 1. Comparison of exhaustive search with the proposed method for selecting clustering algorithm and its hyperparameters for the given dataset using 20 clustering validity indexes. For each dataset we show, value of how many indices is better, same or worse for our approach then for exhaustive search.

dataset objects features better same worse

spect 79 22 18 1 0

iris 150 4 14 4 1

tae 151 5 10 6 3

wine 178 12 15 3 1

flags 194 29 12 3 4

parcinson 195 22 13 2 4

seeds 210 6 15 1 3

glass 214 9 17 0 2

haberman 306 2 9 1 9

bacup 306 35 11 4 4

verebral 310 5 14 4 1

ecoli 336 11 12 2 5

ionosphere 351 32 15 2 2

whosale 440 7 13 3 3

forestfires 517 12 11 4 4

balance 624 4 10 5 4

indianiabets 768 8 8 1 10

yeast 1039 7 6 1 12

car 1210 5 6 2 11

banknote 1372 4 5 0 14

In the previous research, we tackled classification task [9]. In that case, quality measurement required amount of computations linear to the size of the dataset, which could be considered negligible.

In the case of clustering task, validity index calculation time can become comparable to the time of dataset clustering itself, thus significantly increasing computations. It seems clear now, that Multi-armed-bandit iteration size and budget size have to be calculated in correspondence with the dataset size.

Let's demonstrate the importance and the effect of model selection and it's hyperparameter optimization. At 1 is presented the visual comparison of clusters, obtained by algorithms with default parameters in comparison to algorithms with optimized parameters for data from table 2.

Let us emphasize, that clustering with default algorithms by default is not only worse in general (according to cluster validity indices value), but sometimes fails to find clusters at all, which makes validity index calculation pointless.

In Table 2 we present the comparison of validity index values achieved when clustering algorithms with default parameters are used. In MASSCAH column, we show the best value achieved by every validity index after model selection and its hyperparameters optimization.

5. Conclusion

In this paper, we present and examine a new solution to the problem of simultaneously selecting a learning algorithm and its hyperparameters. The proposed approach is based on a multi-armed bandit problem solution.

It appears that our approach achieves better results that the exhaustive search in most of the cases. We also see clear dependency of results on the time required to compute a cluster validity index: the more time is required, the less is difference between the two approaches, which clearly indicate that our approach tend to outperform the exhaustive search in a long run and the more time is given to find a model, the bigger the difference between the results will be.

(e) default (f) MASSCAH

Fig. 1. Visual comparison of default clustering and algorithms with optimized hyperparameters.

The suggested method can be improved by applying meta-learning in order to evaluate algorithm quality to prepro-cess a given dataset before running any algorithm. This evaluation can be used as a prior knowledge of an algorithm reward. Moreover, we can add a context vector to hyperparameters optimization process and use solutions of a contextual multi-armed bandit problem. We can select some datasets by meta-learning and then get the empirical risk estimate and use it as context.

Table 2. Comparison of clustering algorithms with default parameters and optimized algorithms performance (validity index value). The dash (-) means that the validity index can not be calculated (usually because there is only one cluster).

CVI Dataset KMeans Aff Prop Mean Shift Ward DBSCAN MASSCAH

ch iris -219.4058 -210.3796 -278.8425 -277.6491 - -281.3849

ch glass -101.4215 -70.0679 -42.7050 -176.2822 -13.9286 -177.7988

ch wholesale -937.1750 -911.9150 -681.3412 -529.9717 -720.3281 -937.1821

ch indiandiabests -126.1178 -49.9867 -17.0386 -196.5603 -7.1757 -236.351

ch yeast -264.5704 -105.7099 -33.9568 -215.9781 -79.6601 -315.996

ch krvskp -155.1293 -31.3933 - -226.6803 - -257.642

sil iris -0.3500 -0.3483 -0.5996 -0.6019 - -0.60186

sil glass -0.3570 -0.2953 -0.4388 -0.4987 -0.4451 -0.551455

sil wholesale -0.5889 -0.5155 -0.6900 -0.5964 -0.6444 -0.696902

sil indiandiabests -0.1653 -0.1309 -0.2759 -0.2196 -0.4851 -0.515592

sil yeast -0.1998 -0.1552 -0.4480 -0.2867 -0.6032 -0.662353

sil krvskp -0.1027 -0.1378 - -0.1011 - -0.229205

cop iris 5.5650 5.7149 6.1734 0.6050 - 0.6050215

cop glass 5.4967 7.9817 5.7963 6.2830 2.2106 0.617259

cop wholesale 5.2221 7.4574 3.2456 1.9267 2.9376 0.614976

cop indiandiabests 5.4034 8.1379 2.3834 4.0959 1.8873 0.287655

cop yeast 10.0984 15.1260 2.6277 4.9766 2.3059 0.826727

cop krvskp 2.1438 3.5413 - 1.6455 - 0.929226

Acknowledgements

The algorithm for simultaneously selecting best algorithm and its hyperparameters was developed under the research project financially supported by the Russian Foundation for Basic Research, Grant 16-37-60115 mol_a_dk. Its

adaptation to the clustering, as well as experimental evaluation were obtained under the research project supported by the Ministry of Education and Science of the Russian Federation, Project No 2.8866.2017/8.9.

References

[1] Adenso-Diaz, B., Laguna, M., 2006. Fine-tuning of algorithms using fractional experimental designs and local search. Operations research 54, 99-114.

[2] Ansotegui, C., Sellmann, M., Tierney, K., 2009. A gender-based genetic algorithm for the automatic configuration of algorithms, in: International Conference on Principles and Practice of Constraint Programming, Springer. pp. 142-157.

[3] Arbelaitz, O., Gurrutxaga, I., Muguerza, J., Perez, J.M., Perona, I., 2013. An extensive comparative study of cluster validity indices. Pattern Recognition 46, 243-256.

[4] Balaprakash, P., Birattari, M., Stutzle, T., 2007. Improvement strategies for the f-race algorithm: Sampling design and iterative refinement, in: International workshop on hybrid metaheuristics, Springer. pp. 108-122.

[5] Birattari, M., Yuan, Z., Balaprakash, P., Stutzle, T., 2010. Empirical methods for the analysis of optimization algorithms, chapter f-race and iterated f-race: an overview.

[6] Brazdil, P.B., Soares, C., Da Costa, J.P., 2003. Ranking learning algorithms: Using ibl and meta-learning on accuracy and time results. Machine Learning 50, 251-277.

[7] Coy, S.P., Golden, B.L., Runger, G.C., Wasil, E.A., 2001. Using experimental design to find effective parameter settings for heuristics. Journal of Heuristics 7, 77-97.

[8] Cruz-Reyes, L., Gómez-Santillán, C., Perez-Ortega, J., Landero, V., Quiroz, M., Ochoa, A., 2012. Algorithm selection: From meta-learning to hyper-heuristics, in: Intelligent Systems. InTech, pp. 77-102.

[9] Efimova, V., Filchenkov, A., Shalyto, A., 2016. Reinforcement-based simultaneous algorithm and its hyperparameters selection. arXiv preprint arXiv:1611.02053 .

[10] Escalante, H.J., Montes, M., Sucar, L.E., 2009. Particle swarm model selection. Journal of Machine Learning Research 10, 405-440.

[11] Feurer, M., Klein, A., Eggensperger, K., Springenberg, J., Blum, M., Hutter, F., 2015. Efficient and robust automated machine learning, in: Advances in Neural Information Processing Systems, pp. 2962-2970.

[12] Gorissen, D., Dhaene, T., Turck, F.D., 2009. Evolutionary model type selection for global surrogate modeling. Journal of Machine Learning Research 10,2039-2078.

[13] Gratch, J., Dejong, G., 1992. COMPOSER: A Probabilistic Solution to the Utility Problem in Speed-up Learning. Technical Report UILU-ENG-92-1704; UIUCDCS-R-92-1724. Illinois Univ., Urbana. Dept. of Computer Science.

[14] Gupta, A.K., Smith, K.G., Shalley, C.E., 2006. The interplay between exploration and exploitation. Academy of management journal 49,

693-706.

[15] Halkidi, M., Batistakis, Y., Vazirgiannis, M., 2001. On clustering validation techniques. Journal of intelligent information systems 17,107-145.

[16] Hutter, F., 2009. Automated configuration of algorithms for solving hard computational problems. Ph.D. thesis. University of British Columbia.

[17] Hutter, F., Hoos, H.H., Leyton-Brown, K., 2010. Sequential model-based optimization for general algorithm configuration (extended version). Technical Report. Technical Report TR-2010-10, University of British Columbia, Computer Science.

[18] Hutter, F., Hoos, H.H., Leyton-Brown, K., 2011. Sequential model-based optimization for general algorithm configuration, in: Learning and Intelligent Optimization. Springer, pp. 507-523. doi:10.1007/978-3-642-25566-3_40.

[19] Hutter, F., Hoos, H.H., Leyton-Brown, K., Stutzle, T., 2009. Paramils: an automatic algorithm configuration framework. Journal of Artificial Intelligence Research 36, 267-306.

[20] Hutter, F., Hoos, H.H., Stutzle, T., 2007. Automatic algorithm configuration based on local search, in: Aaai, pp. 1152-1157.

[21] Mantovani, R.G., Rossi, A.L., Vanschoren, J., Carvalho, A.C.P.d.L., et al., 2015. Meta-learning recommendation of default hyper-parameter values for svms in classifications tasks, in: European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases; International Workshop on Meta-Learning and Algorithm Selection, University of Porto.

[22] Minton, S., Johnston, M.D., Philips, A.B., Laird, P., 1992. Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence 58, 161-205.

[23] Olson, R.S., Bartley, N., Urbanowicz, R.J., Moore, J.H., 2016. Evaluation of a tree-based pipeline optimization tool for automating data science, in: Proceedings of the Genetic and Evolutionary Computation Conference 2016, ACM, New York, NY, USA. pp. 485-492. URL: http://doi.acm.org/10.1145/2908812.2908918, doi:10.1145/2908812.2908918.

[24] Pappa, G.L., Ochoa, G., Hyde, M.R., Freitas, A.A., Woodward, J., Swan, J., 2014. Contrasting meta-learning and hyper-heuristic research: the role of evolutionary algorithms. Genetic Programming and Evolvable Machines 15, 3-35.

[25] Rice, J.R., 1976. The algorithm selection problem, in: Advances in computers. Elsevier. volume 15, pp. 65-118.

[26] Rosales-Perez, A., Gonzalez, J.A., Coello, C.A.C., Escalante, H.J., Reyes-Garcia, C.A., 2014. Multi-objective model type selection. Neurocomputing 146, 83-94.

[27] Smith-Miles, K.A., 2008. Towards insightful algorithm selection for optimisation using meta-learning concepts, in: Neural Networks, 2008. IJCNN 2008.(IEEE World Congress on Computational Intelligence). IEEE International Joint Conference on, IEEE. pp. 4118-4124.

[28] Smith-Miles, K.A., 2009. Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Computing Surveys (CSUR) 41, 6.

[29] Sun, Q., Pfahringer, B., 2013. Pairwise meta-rules for better meta-learning-based algorithm ranking. Machine learning 93, 141-161. doi:10. 1007/s10994-013-5387-y.

[30] Sutton, R.S., Barto, A.G., 1998. Reinforcement learning: An introduction. MIT press.

[31] Thornton, C., Hutter, F., Hoos, H.H., Leyton-Brown, K., 2012. Auto-weka: Automated selection and hyper-parameter optimization of classification algorithms. CoRR, abs/1208.3719 doi:10.1145/2487575.2487629.

[32] Wolpert, D.H., Macready, W.G., 1997. No free lunch theorems for optimization. IEEE transactions on evolutionary computation 1, 67-82.

dataset DB Dunn CH Sil gd31 gd41 gd51 gd33 gd43 gd53 cs DB*

glass as 1.5596 -0.6089 -177.7988 -0.5515 -0.8544 -1.4209 -86.2716 -0.0078 -0.0111 -1.2269 0.0541 0.6248

ex 1.5755 -0.6063 -177.6249 -0.548 -0.8074 -1.3084 -74.1009 -0.0072 -0.0096 -0.6571 0.0657 0.782

haberman as 1.0405 -0.1028 -289.8077 -0.4679 -0.6121 -0.9002 -63.4616 -0.1978 -0.0105 -2.2475 0.0501 0.6624

ex 1.4353 -0.1372 -362.7029 -0.4889 -0.6257 -1.0482 -72.216 -0.1988 -0.0107 -2.6377 0.3856 0.7006

ionosphere as 1.502 -0.5573 -118.3217 -0.4131 -0.728 -1.062 -82.7318 -0.0096 -0.0093 -0.9979 0.0557 0.7521

ex 1.5125 -0.495 -118.3217 -0.3954 -0.6747 -1.0469 -79.0257 -0.0079 -0.0082 -0.9665 0.0619 0.75

iris as 1.4946 -0.2945 -281.3849 -0.6019 -0.7372 -1.1794 -76.2148 -0.0292 -0.0134 -1.3168 0.1309 0.7479

ex 1.6197 -0.2788 -280.6377 -0.6019 -0.7114 -1.1283 -74.6768 -0.0221 -0.0123 -1.1741 0.117 0.7479

seeds as 1.3827 -0.1871 -311.6437 -0.4837 -0.808 -1.2616 -88.6867 -0.0205 -0.0119 -1.7009 0.1049 0.6921

ex 1.4993 -0.1481 -311.6437 -0.4836 -0.8036 -1.2565 -86.3792 -0.0169 -0.0094 -1.6028 0.1625 0.69

spect as 1.8907 -0.6766 -20.1442 -0.3225 -0.8714 -0.885 -27.2582 -0.1736 -0.0292 -2.4241 1.0246 0.9653

ex 2.0825 -0.6657 -20.1004 -0.3152 -0.8633 -0.826 -26.8203 -0.1268 -0.0287 -2.046 1.0436 0.9753

verebral as 1.3072 -0.4152 -213.5053 -0.5635 -0.768 -1.4779 -78.0945 -0.014 -0.0138 -1.2482 0.1427 0.6532

ex 1.3078 -0.4152 -213.5053 -0.5635 -0.768 -1.4693 -77.3672 -0.0121 -0.0109 -1.2567 0.1613 0.6579

whosale as 1.336 -0.5569 -937.1811 -0.6965 -0.9506 -1.2821 -124.4972 -0.0141 -0.0116 -1.8433 0.1304 0.668

ex 1.4446 -0.5569 -935.0724 -0.6918 -0.9069 -1.2741 -124.6003 -0.0114 -0.0115 -1.8433 0.1353 0.668

wine as 1.5277 -0.4119 -91.6599 -0.3258 -0.7452 -1.727 -106.8355 -0.0249 -0.0188 -1.9011 0.0881 0.7747

ex 1.6181 -0.3773 -91.5559 -0.3258 -0.7263 -1.6496 -102.4028 -0.0223 -0.0163 -1.5932 0.1246 0.7811

car as 1.6019 -0.454 -339.6651 -0.4591 -0.7183 -0.9832 -337.7486 -0.0075 -0.0014 -2.2083 1.1065 0.8162

ex 1.6619 -0.4387 -339.6651 -0.6524 -0.7306 -0.9809 -283.4081 -0.0212 -0.0015 -1.9793 0.8913 0.8058

yeast as 1.4266 -0.5811 -315.9935 -0.657 -0.7927 -1.5423 -156.7465 -0.0031 -0.002 -0.5604 0.3942 0.7102

ex 1.4579 -0.627 -311.8121 -0.657 -0.7933 -1.552 -228.5318 -0.0023 -0.0017 -1.3568 0.2731 0.7096

parcinson as 1.5269 -0.3519 -92.1241 -0.5587 -1.0153 -1.4554 -55.873 -0.1086 -0.013 -3.6605 0.1265 0.7676

ex 1.5474 -0.3519 -92.1241 -0.5242 -0.9152 -1.4004 -50.3627 -0.1138 -0.0128 -3.0076 0.119 0.7637

backup as 1.6299 -0.6926 -76.1603 -0.4005 -0.9181 -1.3626 -109.1429 -0.0213 -0.0104 -1.9375 0.2007 0.8147