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

• Забашта Алексей Сергеевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Забашта Алексей Сергеевич

Реферат

Synopsis

Введение

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

1.1 Задача классификации

1.1.1 Описание используемых алгоритмов классификации и восстановления регрессии

1.1.2 Описание используемых метрик качества и ошибки

1.2 Экземпляры для задачи классификации

1.3 Инвариантность набора данных

1.4 Задача выбора алгоритмов и настройка гипер-параметров

1.5 Мета-обучение

1.6 Мета-признаков экземпляров классификации

1.6.1 Базовые мета-признаки

1.6.2 Статистические мета-признаки

1.6.3 Информационно-теоретические мета-признаки

1.6.4 Структура дерева принятия решений

1.6.5 Характеристики работы классификаторов

1.7 Задача направленной генерации наборов данных

1.7.1 Эволюционные алгоритмы

1.7.2 Активное обучение

1.7.3 Генеративно-состязательные сети (GAN)

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

Глава 2. Симметрия набора данных

2.1 Приведение набора данных к общему виду

2.2 Метод максимизации диагонали

2.3 Минимизация разности соседних элементов

2.4 Сортировка по корреляции с классом

2.5 Теоретическое сравнение методов стабилизации

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

Глава 3. Генерация наборов данных эволюционными алгоритмами

3.1 Сведение задачи направленной генерации к задаче минимизации

3.2 Методы на основе прямой модификации набора данных (DIRECT)

3.3 Методы модификации наборов данных на основе оптимизации параметров генератора

3.3.1 Базовые ненаправленные генераторы

3.3.2 Многомерное нормальное распределение (GMM)

3.4 Подход на основе естественных преобразований (NDSE)

3.4.1 Удаление объектов и признаков

3.4.2 Добавление объекта

3.4.3 Добавление признака

3.4.4 Изменения числа классов

3.4.5 Мутация

3.4.6 Кроссовер

3.5 Экспериментальное сравнение методов направленной генерации

3.5.1 Используемые эволюционные алгоритмы

3.5.2 Описание эксперимента по генерации множества наборов данных

3.5.3 Результаты эксперимента по генерации множества наборов данных

3.5.4 Описание эксперимента по генерации выбранных наборов данных

3.5.5 Результаты эксперимента по генерации выбранных наборов данных

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

Глава 4. Применение генеративно-состязательных сетей для задач мета-обучения

4.1 Генеративно-состязательные сети

4.2 Архитектуры генеративно-состязательных сетей для задач мета-обучения

4.3 Свёрточные сети

4.4 Сильно симметричная сеть для работы с симметричными наборами данных

4.4.1 Стратегия свёртки для наборов данных

4.4.2 Стратегия деконволюции для наборов данных

4.5 Графовые представления наборов данных

4.5.1 Представление в виде гиперкуба (HCUBE)

4.5.2 Представление в виде графа с ограничениями (GRAPH)

4.5.3 Графовый свёрточный слой

4.6 Эксперименты по выбору алгоритмов и генерации наборов данных

4.6.1 Описание множества набора данных

4.6.2 Описание процесса обучения сети LM-GAN

4.6.3 Описание эксперимента по выбору алгоритма

4.6.4 Описание эксперимента по генерации наборов данных

4.6.5 Результаты экспериментов с комбинацией набора данных и мета признаков

4.6.6 Результаты экспериментов с методами стабилизации наборов данных

4.6.7 Результаты экспериментов с графовыми представлениями

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

Глава 5. Активное обучение

5.1 Активное обучение

5.2 Стратегии активного обучения

5.2.1 Случайная генерация (RAND)

5.2.2 Максимизация разнообразия

5.2.3 Максимизация неопределенности

5.3 Эксперименты с активным обучением

5.3.1 Результаты

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

Глава 6. Описание и применение программного комплекса

6.1 Описание программного комплекса

6.1.1 Описание основных используемых библиотек

6.1.2 Описание модулей программного комплекса

6.2 Генерация наборов данных для систем автоматической проверки программ

6.2.1 Генерация наборов данных для задачи линейной регрессии

6.2.2 Генерация наборов данных для метода опорных векторов

6.3 Генерация наборов данных для повышения качества выбора гипер-параметров

6.3.1 Описание наборов данных для задачи настройки гипер-параметров

6.3.2 Сравнение систем мета-обучения в задаче настройки гипер-параметров

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

Заключение

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

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

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

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

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

Публикации

Реферат

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

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

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

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

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

1Wolpert, D. H. The supervised learning no-free-lunch theorems // Soft computing and industry. Springer, 2002. P. 25-42.

2Rice, J.R. [etal.]. The algorithm selection problem//Advances in computers. 1976. Vol. 15, no. 65118. P. 5.

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

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

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

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

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

3Brazdil, P., Carrier, C. G., Soares, C., Vilalta, R. Metalearning: Applications to data mining. Springer Science & Business Media, 2008.

4Doan, T., Kalita, J. Predicting run time of classification algorithms using meta-learning // International Journal of Machine Learning and Cybernetics. 2017. Vol. 8, no. 6. P. 1929-1943.

5Feurer, M., Springenberg, J. T., Hutter, F. Initializing bayesian hyperparameter optimization via metalearning // Twenty-Ninth AAAI Conference on Artificial Intelligence. 2015.

6Vanschoren, J., VanRijn, J.N., Bischl, B., Torgo, L. OpenML: networked science in machine learning// ACM SIGKDD Explorations Newsletter. 2014. Vol. 15, no. 2. P. 49-60.

исследований пытаются сгенерировать наиболее сложный экземпляр для ЛР-трудной задачи'.

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

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

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

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

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

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

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

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

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

Объект исследования — задача классификации.

Предмет исследования — генерация наборов данных для задачи классификации.

1Selman, B., Mitchell, D. G., Levesque, H. J. Generating hard satisfiability problems // Artificial intelligence. 1996. Vol. 81, no. 1/2. P. 17-29; Hemert, J. I. van. Evolving combinatorial problem instances that are difficult to solve // Evolutionary Computation. 2006. Vol. 14, no. 4. P. 433-462.

8Reif, M., Shafait, F., Dengel, A. Dataset generation for meta-learning // KI-2012: Poster and Demo Track. 2012. P. 69-73.

9Smith-Miles, K., Tan, T. T. Measuring algorithm footprints in instance space // Evolutionary Computation (CEC), 2012 IEEE Congress on. IEEE. 2012. P. 1-8; Muñoz, M. A., Smith-Miles, K. Generating custom classification datasets by targeting the instance space // In Proceedings of GECCO '17 Companion. ACM. 2017. in press; Muñoz, M.A., Villanova, L., Baatar, D., Smith-Miles, K. Instance Spaces for Machine Learning Classification//Machine Learning. 2017. in press.

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

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

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

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

г) Разработаны стратегии активного обучения для заполнения мета-признакового пространства.

Научная новизна заключается в следующем:

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

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

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

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

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

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

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

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

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

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

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

а) Научная и учебно-методическая конференция

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

б) Научная и учебно-методическая конференция

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

в) Научная и учебно-методическая конференция

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

г) Научная и учебно-методическая конференция

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

д) Научная и учебно-методическая конференция

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

е) Всероссийский V Конгресс молодых ученых. 2016, Санкт-Петербург.

ж) Всероссийский VIII Конгресс молодых ученых. 2019, Санкт-Петербург.

и) Всероссийский IX Конгресс молодых ученых. 2020, Санкт-Петербург.

к) Всероссийская научная конференция по проблемам информатики

СПИСОК-2016, СПбГУ Санкт-Петербург.

л) Всероссийская научная конференция по проблемам информатики

СПИСОК-2019, СПбГУ, Санкт-Петербург.

м) International Conference on Machine Learning (ICML). 2017, Сидней, Австралия.

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

Университета ИТМО.

Университета ИТМО.

Университета ИТМО.

Университета ИТМО.

Университета ИТМО.

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

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

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

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

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

В разделе 1.1 приведено описание задачи классификации.

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

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

- метод ближайших соседей (kNN — k-Nearest Neighbors) строит предсказание на основе ближайших объектов к запросу;

- метод опорных векторов (SVM — Support Vector Machine) разделяет плоскостью на два класса классифицируемое пространство;

- наивный байесовский классификатор (NB — Naïve Bayes) выбирает класс исходя из максимума апостериорной вероятности;

- дерево принятия решений (DT — Decision Tree) содержит в вершинах предикаты, а в листьях — значения целевой переменой;

- случайный лес (RF — Random Forest) — ансамбль деревьев принятия решений, которые обучаются независимо на случайном подмножестве объектов;

- градиентный бустинг — ансамбль деревьев принятия решений, которые обучаются последовательно на основе ошибки предыдущего предсказания;

- алгоритм линейной регрессии аппроксимирует набор данных линейным уравнением;

- глубокая нейронная сеть (DNN — Deep Neural Network) — алгоритм на основе композиции дифференцируемых функций.

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

- точность — отношение числа верно классифицированных объектов к общему числу объектов;

- F-мера — среднее гармоническое полноты и точности предсказания;

- MSE (Mean Squared Error) — среднеквадратичная ошибка;

- RMSE (Root-Mean-Square Error) — корень из среднеквадратичной ошибки;

- MAPE (Mean Absolute Percentage Error) — средняя абсолютная ошибка в процентах;

- SMAPE (Symmetric Mean Absolute Percentage Error) — симметричная средняя абсолютная ошибка в процентах средняя абсолютная ошибка в процентах.

В разделе 1.2 приведено описание способов представления набора данных для задачи классификации. Традиционно набор данных для задачи классификации представляется таблицей, в которой строки кодируют объекты, а столбцы — признаки.

число признаков, а У = [вх.. .вк } — метки классов, к — число классов.

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

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

В разделе 1.3 приведено описание свойства симметрии набора данных.

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

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

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

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

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

В разделе 1.6 приведено описание используемых мета-признаков.

Наборы данных описываются мета-признаками. Это могут быть произвольные числовые характеристики, которыми обладает любой набор данных. Однако для описанного решения задачи выбора алгоритма, это должны быть функции, вычислимые гораздо быстрее, чем выбираемые алгоритмы классификации. Формально, мета-признаковое описание — это многомерная функция ¡1(d) : {d} ^ Rm, где m — число мета-признаков.

Чаще всего при исследовании используются следующие группы мета-признаков:

а) Структура набора данных: число объектов, число признаков, число и энтропия классов.

б) Статистики признаков (минимум, максимум, среднее, дисперсия, коэффициенты асимметрии и эксцесса): корреляция с классом и между признаками, межклассовое и внутриклассовое расстояние.

в) Структура дерева принятия решений (минимум, максимум, среднее, дисперсия): глубина листьев, использование классов, использование признаков.

Эти же мета-признаки используются в данной работе.

10 Wolpert, D. H. The supervised learning no-free-lunch theorems // Soft computing and industry. Springer, 2002. P. 25-42.

11Brazdil, P., Carrier, C. G., Soares, C., Vilalta, R. Metalearning: Applications to data mining. Springer Science & Business Media, 2008.

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

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

В разделе 1.7 ставится задача направленной генерации наборов данных.

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

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

Вторая глава посвящена решению проблемы симметрии наборов данных относительно порядка объектов и признаков.

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

Стабилизация набора данных — приведение набора данных к общему виду перестановкой порядка объектов и признаков. Формально, стабилизация — выбор представителя из класса эквивалентности, который образован перестановкой порядка объектов и признаков. Таким образом, действие любой перестановки порядка объектов и признаков на набор данных будет отменено.

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

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

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

элементов. Данная задача сводится к нескольким задачам коммивояжера, которые решаются жадным алгоритмом (MING) и методом восхождения к вершине (MINH).

В разделе 2.4 описан метод стабилизации наборов данных на основе сортировки по корреляции с классом — метод, упорядочивающий строки и столбцы по значению корреляции. В качестве метрики корреляции используется коэффициент корреляции Пирсона (CORP) и коэффициент ранговой корреляции Спир-мена (CORS).

В разделе 2.5 приведено сравнение методов стабилизации.

Результат сравнения методов стабилизации приведён в таблице Р.1. Как видно из результатов, асимптотическое время совпадает с реальным. Несмотря на то, что методы стабилизации на основе корреляции оказались быстрее, их нельзя применить для стабилизации наборов данных для задачи кластеризации в отличии от других рассматриваемых методов.

Таблица Р.1 - Сравнение методов стабилизации: n — число объектов в стабилизируемом наборе данных, m — число признаков, C = 2000 — лимит числа итераций метода восхождения к вершине. Реальное время вычислялось для стабилизации 10000 наборов данных с 128 объектами и 16 признаками на процессоре Intel Core i5-5350U

Mетод Асимптотическое время Реальное время (м^ Применим для кластеризации?

DIAG о n ■ m 56 да

CORP n ■ m + n log n + m log m 40 нет

CORS n ■ m + n log n + m log m 44 нет

MING о о n ■ m + n ■ m 94 да

MINH n ■ m ■ C 3118 да

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

В разделе 3.1 описан подход к сведению задачи направленной генерации к задаче минимизации

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

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

E¿d) = \J(t - ß(d))T x S— x (t - ß(d)),

где d — полученный экземпляр, j(d) — его мета-признаки, t — значение требуемого вектора мета-признаков, S — матрица ковариаций, оценённая на множестве реальных наборов данных.

В данной работе рассматривается три метода преобразования наборов данных для работы с эволюционными алгоритмами: DIRECT, GMM, NDSE. Эти методы будут описаны далее.

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

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

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

Литература

1. Cook S.A., Mitchell D.G. Finding hard instances of the satisfiability problem // DIM ACS Series in Discrete Mathematics and Theoretical Computer Science. 1997. V. 35. P. 1-17. doi: 10.1090/dimacs/035/01

2. Horie S., Watanabe O. Hard instance generation for SAT // Lecture Notes in Computer Science. 1997. V. 1350. P. 22-31. doi: 10.1007/3-540-63890-3_4

3. Selman B., Mitchell D.G., Levesque H.J. Generating hard satisfiability problems // Artificial Intelligence. 1996. V. 81. N 1-2. P. 17-29.

4. Xu K., Boussemart F., Hemery F., Lecoutre C. Random constraint satisfaction: easy generation of hard (satisfiable) instances // Artificial Intelligence. 2007. V. 171. N 8. P. 514534. doi: 10.1016/j.artint.2007.04.001

5. van Hemert J.I. Evolving combinatorial problem instances that are difficult to solve // Evolutionary Computation. 2006. V. 14. N 4. P. 433-462. doi: 10.1162/evco.2006.14.4.433

6. Ajtai M. Generating hard instances of the short basis problem // Lecture Notes in Computer Science. 1999. V. 1644. P. 1-9.

7. Буздалов М.В. Генерация тестов для олимпиадных задач по программированию с использованием генетических алгоритмов // Научно-технический вестник информационных технологий, механики и оптики. 2011. № 2(72). С. 72-77.

8. Буздалов М.В. Генерация тестов для олимпиадных задач по теории графов с использованием эволюционных стратегий // Научно-технический вестник информационных технологий, механики и оптики. 2011. № 6(76). С. 123-127.

9. Smith-Miles K., Tan T.T. Measuring algorithm footprints in instance space // IEEE Congress on Evolutionary Computation. Brisbane, Australia, 2012. P. 3446-3453. doi: 10.1109/CEC.2012.6252992

10. Asahiro Y., Iwama K., Miyano E. Random generation of test instances with controlled attributes // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996.

References

1. Cook S.A., Mitchell D.G. Finding hard instances of the satisfiability problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1997, vol. 35, pp. 1-17. doi: 10.1090/dimacs/035/01

2. Horie S., Watanabe O. Hard instance generation for SAT. Lecture Notes in Computer Science, 1997, vol. 1350, pp. 22-31. doi: 10.1007/3-540-63890-3_4

3. Selman B., Mitchell D.G., Levesque H.J. Generating hard satisfiability problems. Artificial Intelligence, 1996, vol. 81, no. 1-2, pp. 17-29.

4. Xu K., Boussemart F., Hemery F., Lecoutre C. Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artificial Intelligence, 2007, vol. 171, no. 8, pp. 514-534. doi: 10.1016/j.artint.2007.04.001

5. van Hemert J.I. Evolving combinatorial problem instances that are difficult to solve. Evolutionary Computation, 2006, vol. 14, no. 4, pp. 433-462. doi: 10.1162/evco.2006.14.4.433

6. Ajtai M. Generating hard instances of the short basis problem. Lecture Notes in Computer Science, 1999, vol. 1644, pp. 1-9.

7. Buzdalov M.V. Tests generation for olympiad programming tasks using genetic algorithms. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2011, no. 2, pp. 72-77. (In Russian)

8. Buzdalov M.V. Test generation for programming challenge tasks in graph theory by evolution strategies. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2011, no. 6, pp. 123-127. (In Russian)

9. Smith-Miles K., Tan T.T. Measuring algorithm footprints in instance space. IEEE Congress on Evolutionary Computation. Brisbane, Australia, 2012, pp. 3446-3453. doi: 10.1109/CEC.2012.6252992

10. Asahiro Y., Iwama K., Miyano E. Random generation of test inst anc es with c ontrolle d attribute s. DIMA CS Series in Discrete Mathematics and Theoretical Computer Science, 1996, vol. 26, pp. 377-393. doi: 10.1090/dimacs/026/18

V. 26. P. 377-393. doi: 10.1090/dimacs/026/18

11. Smith-Miles K., Wreford B., Lopes L., Insani N. Predicting metaheuristic performance on graph coloring problems using data mining // Studies in Computational Intelligence. 2013. V. 434. P. 417-432. doi: 10.1007/978-3-642-30671-6-16

12. Smith-Miles K., Baatar D., Wreford B., Lewis R. Towards objective measures of algorithm performance across instance space // Computers and Operations Research. 2014. V. 45. P. 12-24. doi: 10.1016/j.cor.2013.11.015

13. Giraud-Carrier C. Metalearning - a tutorial // Tutorial at 7th Int. Conf. on Machine Learning and Applications, ICMLA. San Diego, California, 2008. P. 11-13.

14. Brazdil P., Giraud-Carrier C., Soares C., Vilalta R. Metalearning. Applications to Data Mining. Springer, 2009. 176 p. doi: 10.1007/978-3-540-73263-1

15. Wolpert D.H., Macready W.G. No free lunch theorems for optimization // IEEE Transactions on Evolutionary Computation. 1997. V. 1. N 1. P. 67-82. doi: 10.1109/4235.585893

16. Wolpert D.H. The supervised learning no-free-lunch theorems // Soft Computing and Industry. 2002. P. 25-42. doi: 10.1007/978-1-4471-0123-9_3

17. Воронцов К.В. Математические методы обучения по прецедентам (теория обучения машин) [Электронный ресурс]. Режим доступа: http://docplayer.ru/2064-K-v-voroncov-http-www-ccas-ru-voron-voron-ccas-ru.html, свободный. Яз. рус. (дата обращения 24.03.2017). 140 c.

18. Николенко С.И., Тулупьев А.Л. Самообучающиеся системы. М.: МЦНМО, 2009. 287 с.

19. Jin Y., Branke J. Evolutionary optimization in uncertain environments - a survey // IEEE Transactions on Evolutionary Computation. 2005. V. 9. N 3. P. 303-317. doi: 10.1109/TEVC.2005.846356

20. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Москва, Физматлит, 2006. 319 с.

21. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. V. 220. N 4598. P. 671680.

22. Скобцов Ю.А. Основы эволюционных вычислений. Донецк: ДонНТУ, 2008. 326 с.

23. Vanschoren J., van Rijn J.N., Bischl B., Torgo L. OpenML: networked science in machine learning // ACM SIGKDD Explorations Newsletter. 2014. V. 15(2). P. 49-60. doi: 10.1145/2641190.2641198

24. Filchenkov A., Pendryak A. Datasets meta-feature description for recommending feature selection algorithm // Proc. Artificial Intelligence and Natural Language and Information Extraction, Social Media and Web Search FRUCT. St. Petersburg, Russia, 2015. P. 11-18. doi: 10.1109/AINL-ISMW-FRUCT.2015.7382962

25. Indyk P., Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality // Proc. 13th Annual ACM Symposium on Theory of Computing. Dallas, USA, 1998. P. 604-613.

Авторы

Забашта Алексей Сергеевич - программист, студент, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация, [e-mail]

Фильченков Андрей Александрович - кандидат физико-математических наук, доцент, Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация,

[e-mail]

11. Smith-Miles K., Wreford B., Lopes L., Insani N. Predicting metaheuristic performance on graph coloring problems using data mining. Studies in Computational Intelligence, 2013, vol. 434, pp. 417-432. doi: 10.1007/978-3-642-30671-6-16

12. Smith-Miles K., Baatar D., Wreford B., Lewis R. Towards objective measures of algorithm performance across instance space. Computers and Operations Research, 2014, vol. 45, pp. 12-24. doi: 10.1016/j.cor.2013.11.015

13. Giraud-Carrier C. Metalearning - a tutorial. Tutorial at 7th Int. Conf. on Machine Learning and Applications, ICMLA. San Diego, California, 2008, pp. 11-13.

14. Brazdil P., Giraud-Carrier C., Soares C., Vilalta R. Metalearning. Applications to Data Mining. Springer, 2009, 176 p. doi: 10.1007/978-3-540-73263-1

15. Wolpert D.H., Macready W.G. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1997, vol. 1, no. 1, pp. 67-82. doi: 10.1109/4235.585893

16. Wolpert D.H. The supervised learning no-free-lunch theorems. Soft Computing and Industry, 2002, pp. 25-42. doi: 10.1007/978-1-4471-0123-9_3

17. Vorontsov K.V. Matematicheskie metody obucheniya po pretsedentam (teoriya obucheniya mashin). Available at: http://docplayer.ru/2064-K-v-voroncov-http-www-ccas-ru-voron-voron-ccas-ru.html (accessed 24.03.2017).

18. Nikolenko S.I., Tulup'ev A.L. Self-Learning Systems. Moscow, MTsNMO Publ., 2009, 287 p. (In Russian)

19. Jin Y., Branke J. Evolutionary optimization in uncertain environments - a survey. IEEE Transactions on Evolutionary Computation, 2005, vol. 9, no. 3, pp. 303-317. doi: 10.1109/TEVC.2005.846356

20. Gladkov L.A., Kureichik V.V., Kureichik V.M. Genetic Algorithms. Moscow, Fizmatlit Publ., 2006, 319 p. (In Russian)

21. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by simulated annealing. Science, 1983, vol. 220, no. 4598, pp. 671-680.

22. Skobtsov Yu.A. Fundamentals of Evolutionary Computation. Donetsk, DonNTU Publ., 2008, 326 p. (in Russian)

23. Vanschoren J., van Rijn J.N., Bischl B., Torgo L. OpenML: networked science in machine learning. ACM SIGKDD Explorations Newsletter, 2014, vol. 15, pp. 49-60. doi: 10.1145/2641190.2641198

24. Filchenkov A., Pendryak A. Datasets meta-feature description for recommending feature selection algorithm. Proc. Artificial Intelligence and Natural Language and Information Extraction, Social Media and Web Search FRUCT. St. Petersburg, Russia, 2015, pp. 11-18. doi: 10.1109/AINL-ISMW-FRUCT.2015.7382962

25. Indyk P., Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality. Proc. 13th Annual ACM Symposium on Theory of Computing. Dallas, USA, 1998, pp. 604-613.

Authors

Alexey S. Zabashta - bachelor, programmer, ITMO University, Saint Petersburg, 197101, Russian Federation, [e-mail]

Andrey A. Filchenkov - PhD, Associate professor, ITMO University, Saint Petersburg, 197101, Russian Federation, [e-mail]

NDSE: Instance Generation for Classification by Given Meta-Feature Description

Alexey Zabashta and Andrey Filchenkov

ITMO University, Computer Technology Lab, Kronverksky pr. 49, 197101 St.Petersburg, Russia {azabashta,afilchenkov}@corp.ifmo.ru

Introduction. Meta-features [1] are variables reflecting various properties of datasets. In machine learning, they are typically used for two purposes. The first one is predicting algorithm performance on new datasets never seen before, that is meta-learning [2]. The second one is analyzing algorithms and finding their weaknesses [3]. Thus, meta-features allow obtaining vector representations of datasets and considering them as points in the corresponding space. The key problem is that such a space will be extremely sparse if we use only real-world datasets. This problem was recognized by researchers and several methods exists for generating new datasets, e.g. [4]. However, most of them generate datasets in an uncontrolled manner, without any guesses on how biased the resulting set of datasets may be in terms of meta-feature space, which does not allow using them for algorithm analysis. This paper is devoted to solve the dataset generation problem in a guided way. The method we propose generates a dataset such that its meta-feature vector is as close as possible to a target meta-feature vector.

Related works. We found only two papers devoted to the problem we solve. In both of them, the authors solve this problem by reducing it to a minimization problem, in which the target function is the distance between target and resulting datasets in a meta-feature space. To solve this problem, they use different evolutionary techniques. In [5], the authors explicitly represent datasets for the genetic algorithm as vectors in #attributes x #objects dimensional space. We will refer to the search in this space as Vect. In [6], the authors use the CMA-ES algorithm to optimize parameters of the Gaussian mixture distribution, which they used for sampling objects the of resulting dataset. We will refer to it as GMM.

NDSE Method. The NDSE method (Natural DataSets Evolution), that we present earlier [7], shares the advantages of both related approaches. This method also uses evolutionary algorithms and its operators have direct access to datasets, not their intermediate representations.

NDSE is based on using operators of adding and removing attributes or objects from a dataset. These operators are equivalent to feature extraction, feature selection, oversampling and undersampling, respectively. We use the following implementation of these operators: random removing of attributes and objects from a dataset, copying of random subsets of objects from the same class for adding new object to dataset, applying random functions, which depends on attributes, class label and random noise, for adding a new attribute to a dataset.

2 Alexey Zabashta and Andrey Filchenkov

In order to apply evolutionary algorithms, mutation and crossover operators are required. Mutation operator uses the operators of adding and removing to change the number of attributes or objects in a dataset. Crossover operator merges two datasets into a single big dataset and then splits it by attributes into two resulting datasets.

NDSE works as follows. It receives a list of meta-features (functions of dataset) and a target meta-feature vector as input. Vanilla version of this method (which we will refer to as NDSE) starts with an empty dataset, while an improved version (which we will refer to as NDSE') uses real-world datasets as an initial population. During its runtime, the method follows a specific evolutionary algorithm, which is the hyperparameter of this method, and which exploits suggested mutation and crossover operators. Fitness function is the distance between the target meta-feature vector and meta-feature vector of a generated dataset.

Experiments. We conduct two experiments. In both of them, the target vector is meta-features of a real dataset for binary classification from OpenML1. We excluded a target dataset from the initial population for the methods that use them in that way. We use different evolutionary strategies implemented in jMetal2 library. We compare NDSE and NDSE' with Vect, Vect' (uses real-world datasets as an initial population) and GMM. The error is the resulting fitness-function value, that is the normalized Euclidean distance between the target and resulting datasets: E(9) = — ^i)/o"i)2, where 9{ and f are i-th

meta-feature values of the target and resulting datasets correspondingly, and Oi is its standard deviation for real-world datasets. We use 29 meta-features, such as general information, informational and statistical metrics, and characteristic of decision tree. Each run in the Short-Run experiment is limited by the 2000 generated datasets, while this limitation is 105 for the Long-Run experiment. The results of the experiments are shown in Table 1.

Table 1. Experimental results. The average error over the 298 target datasets by different evolutionary strategies for the Short-Run experiment and minimal average error at the three target datasets for the Long-Run experiment.

Short-Run (evolutionary algorithms) Long-Run (datasets)

CMAES MOCell NSGAII RAND SMSOA SPEA2 fertility vote Australian

GMM 4.51 6.48 6.08 6.76 6.02 6.08 2.39-10-5 0.91 6.54

Vect — 13.29 13.66 21.57 12.55 13.06 1.67-10-9 5.50 12.29

NDSE — 2.61 2.83 3.89 2.90 2.80 3.13-10-5 0.07 0.51

Vect' — 2.04 1.64 2.63 1.88 1.94 2.38-10-9 0.69 2.21

NDSE' — 1.84 1.75 6.95 1.74 1.60 1.18-10-4 0.11 0.54

As it can be seen, the proposed methods are superior to the baselines. Usage of real-world datasets as an initial population is always better than usage of anything else. The best result is shown by NDSE' with SPEA2.

1 OpenML.org

2 jmetal.github.io/jMetal

NDSE: Instance Generation for Classification 3

Conclusion. In this paper, we suggested a method for generating datasets

given their meta-feature description. The method outperformed the baselines.

Acknowledgments. This work was financially supported by The Russian

Science Foundation, Agreement 17-71-30029 and the Russian Foundation for

Basic Research, Grant 16-37-60115 mol_a_dk.

References

1. Filchenkov, A., Pendryak, A.: Datasets meta-feature description for recommending feature selection algorithm. In: AINL-ISMW FRUCT. pp. 11-18 (2015)

2. Brazdil, P., Carrier, C.G., Soares, C., Vilalta, R.: Metalearning: Applications to data mining. Springer Science & Business Media (2008)

3. Smith-Miles, K., Baatar, D., Wreford, B., Lewis, R.: Towards objective measures of algorithm performance across instance space. Computers & Operations Research 45, 12-24 (2014)

4. Soares, C.: Uci++: Improved support for algorithm selection using datasetoids. In: Pacific-Asia Conference on Knowledge Discovery and Data Mining. pp. 499-506. Springer (2009)

5. Reif, M., Shafait, F., Dengel, A.: Dataset generation for meta-learning. Poster and Demo Track of the 35th German Conference on Artificial Intelligence (KI-2012) pp.

69-73 (2012)

6. Munoz, M.A., Smith-Miles, K.: Generating custom classification datasets by targeting the instance space. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion. pp. 1582-1588. GECCO '17, ACM, New York (2017)

7. Zabashta, A., Filchenkov, A.: NDSE: Method for classification instance generation given meta-feature description. In: AutoML Workshop, International Conference on Machine Learning (2017)

Available online at www.sciencedirect.com

ScienceDirect

Procedía

Computer Science

ELSEVIER

Procedía Computer Science 136 (2018) 174-182

www.elsevier.com/locate/procedia

7th International Young Scientist Conference on Computational Science

Spanning of Meta-Feature Space for Travelling Salesman Problem

Yulia Abdrashitova*, Alexey Zabashtaa'*, Andrey Filchenkova

In this paper, we consider the problem of creating; artificial training set containing instances of a given task with known meta-feature set. We focus on the Traveling saleiocnen problem, however, the approacC we present is applicable for any other optimization task. We modify the Smith-Miles approach for spanning of ccetaifeature spree by introducing set diversity funceion. We use thin funlity o.mction to reduce instance goneration problm to an optimization problem. We can most fully apan the whole meta-feature spaceby maximizing the set diversity fuahty function. Ansther method we present to sample an instance set is generating certain inetances

one by one, making them close to specific meta-feature vectors. In this cane, wc use Euclidian diftance between thegiven meta-fuesaetugreenveteicctoarlgaonrdithombtaainndedsiimnsutlaantceed manentae-afleinatgumreestahsodthaestathrgeeotpftuinmcitzioatniofnoramlgionriimthimzastiuosne.dWoenctohemmpaertea-tlheevseel.twThoeapvaplruoeacohfetshewsiteht

tlte nai've beseline random instance generation method that dth not thke into sccount diversiiy of the obtained instance set. We use genetic flgoritfm and simulated annealing methed as the optimization lalggoritliif^s used on the meta-level. The value of the set diversity function for the naive method is equal to U.123, for the method that directly maximizes diversity by genetic algorithm: U.468, and for the method that generates single instances by simulated annealing: U.5S5.

© 2201 ¡8 The Authors. Publishedby Elsevier BYV.

This is are open access orticle under thee CC BY-NC-ND hcense (httpn:Itcaeetivneoпmtons.orglhcensesfby-nc-nd/n.O/) Tces-rreiiew under responsibihtyoJi'&e ncientific committee of^e 7th LpternatienelYolflf0erentist CoibrhlrncebnCemputational Science.

Keywoeds: Combinatorial optimization; Travelling Salesman Problem; Instance Generation; Meta-Features.

1. Introduction

In this paper we will talk about optimization problems at different levels so we need to determine some terms. We will refer to the term Problem when we talk about abstract concept of problems The Task is a certain Problem and the; Instance ih a specific sample of the Task. For example, if you consider the "Root-finding problem", "Solving the quadratic equations" will be task of this problem and "p2 — x -1=0" will be instance of this task. The Algorithm is

a program that solves some Task and taker Instance of this task as input. a prCoogmrabmintahtaotrisaollvoepstismoimzaetiToanskisanaddtoakmeasinInsotfanacpeploiefdthmis—attahs—ekmaastiincsp,utf.ocus of which is the problem of finding an

optimom! object inn a finite aet of objects [a,2, 3]. Optimization problems are encountered inn many fields of ^nence, engineering cnd economeics. For instance, t2mbinaedrial optimization methodn aru used in determining the optimal

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

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

This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/3.0/)

Prrr-rrvirw under responsibiïity of the scientific committee of the 7th International Younj8 Scientist Conference on Computational Science.

10.1016/j.procs.2018.08.250

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

Abhtract

air traffic network, the distribution of orders between taxi cabs [4], determining the optimal way of cargo delivery, production scheduling in automated manufacturing systems [5].

However, in many optimization problems, a complete search of an optimal solution is impossible due to the time complexity of such search. Therefore, heuristic algorithms are often used in order to find an approximate solution, typically with no guarantees of its optimality, but usually followed with proofs of its polynomial time complexity. However, heuristics perform very differently on instances they were designed to solve [6]. One heuristic can outperform another at some instance of task, but be completely defeated at another. Furthermore, as it was proven by David Walpert and William McCready in the "No free lunch" theorem [7, 8], the expected performance of any heuristic that do not exploits some knowledge of a instance is equal to the expected performance of any other heuristic including random search.

Such limitations can be overcome by using some prior knowledge of instances. Meta-learning is an approach based on these idea [9, 10]. It aims to solve the well-known problem of algorithm selection [11] by building a predictive model using prior knowledge of a new instance in combination with known performance of algorithms in solving other similar instances. Prior knowledge of instances is formalized in meta-features that describe important characteristics of such instances. In order to obtain a known performance of algorithms, one requires a training set that contains instances of task as objects with precomputed results of running the algorithms on this instances, which then are transformed to labels with respect to the exact problem that is solved: predicting performance (regression), ranking algorithms (ranking) or simply selecting the best one (classification).

The accuracy of predictive meta-learning models depends on the training set. Real-world datasets are few and one cannot expect them to be representative. This is why in many cases including combinatorial optimization problems, researchers create dataset manually. However, for learning a meta-learning predictor [12] a system that can generate such datasets is required.

In this paper, we consider the problem of creating artificial training set containing instances of a given task with known meta-feature set. We focus on the Traveling salesman problem (TSP) as one of the most popular and well-known combinatorial optimization problems, however, the approach we present can be applied for any other optimization problem.

The genetic algorithm [13] and the simulated annealing [14] are used to generate TSP instances for a given metafeature vector, and they are compared. To assess the quality of the resulting set of TSP instances, a metric is introduced that characterizes its diversity. On the basis of the introduced metric, another method is proposed for spanning the meta-feature space.

This paper is organized as follows. In Section 2, we present an overview of the subject area, the problem statement and existing approaches to solve it. In Sections 3 and 4, we described methods for generating a single instance and for spanning whole meta-feature space. In Section 5, the proposed methods are compared. Section 6 is a conclusion.

2. Related work

2.1. The algorithm selection problem

Optimization problems are encountered in many fields of science, engineering and economics. For several decades, the question of universal optimization algorithms, the so-called "black boxes", which use limited knowledge regarding the optimization problem they solve, was relevant. To a large extent, these algorithms have gained inspiration from the optimization processes occurring in nature. The two most popular "black boxes" were evolutionary algorithms [15] and the simulated annealing (SA) [14], simulating the processes of natural selection and statistical mechanics, respectively.

But in 1997, David Walpert and William McDried [7] presented a "No free lunch" theorem,which states that for any optimization algorithms, the computational costs averaged over all instances, are equal. The name of this theorem went from the phrase "There is no free lunch", that is, there is no universal algorithm that works best on the whole set of optimization problems.

For any optimization algorithms a1 and a2 after m iterations

Yj Pdm\f, m, ai) = £ P(dm\f, m, a2),

f

f

where dym is the ordered set of size m of values y € Y associated with input values x € X, f : X ^ Y is the objective function, P(dm\ f, m, a) is the conditional probability of obtaining a sequence dym by the algorithm a after m iterations for the objective function f.

For any optimization algorithms a1 and a2

where ®(dym) is the measure of productivity (the target of optimization task). That is, for any measure of the performance of the sum over all target functions f, the mean of metrics values for any algorithm are equal.

Since there is no universal algorithm, the question arises of choosing the most efficient algorithm for a given instance. The problem of choosing the algorithm, first set by John Rice, [11], tends to predict which algorithms from the portfolio are likely to work better based on the measurable characteristics of the set of instances of the task. There are four main components of the model:

• The P is a space of task instances;

• The space of meta-features M containing the measured characteristics of the instances of tasks, represented in the form of vectors;

• The space of algorithms A is the set of considered algorithms for solutions of this task;

• The performance space Y is a mapping of algorithms to a set of performance metrics.

Thus, we need to find a mechanism for generating a map from the meta-feature space M to the space of algorithms A. The problem of choosing an algorithm consists in finding the map S (m(p)) to the space of algorithms A for the given p €p instance with m(p) € M, so that the selected algorithm a € A maximizes the exponent y(a, p) € Y.

In order to use machine learning methods to predict the most efficient algorithm for a given instance, you need to have a diverse learning set. The more diverse will be the set on which the predictor will be trained, the more accurate will be his predictions. In this connection, there arises the problem of spanning the meta-feature space M.

2.2. Traveling salesman problem and its meta-feature representation

The traveling salesman problem (TSP) [16, 17] is one of the most famous problems of combinatorial optimization, which is to find the most profitable route passing through the specified cities, visiting each of them exactly once, with the subsequent return to the starting city. TSP is a NP-complete problem [18]. However, there are exist different approximate solutions [19, 20].

As it was said before, to effectively teach the predictor you need to be able to generate a diverse training set. A simple method of obtaining random instance turns out to be ineffective, since they are quite similar to each other and span a small area of meta-feature space.

The problem of spanning the meta-feature space for the TSP was dealt with by Kate Smith-Miles. In [21], a genetic algorithm generates instances of the task that are hard and easy for the given algorithm, as well as uniquely hard and uniquely easy. This allows us to compare the algorithms that are demonstrated in the works [22, 23], to recognize the strengths and weaknesses of the algorithm, to predict the algorithm for the given instance, which is shown in the paper [21].

X X P(dym \f, m, a1) • ®(dym) = YjYj P(dm \f, m, a1) • Wm),

(2)

d'm f

dm f

The disadvantage of this method is that the space is spanned in with the given algorithms, and it operates with just several algorithms. So this method does not work if you want to compare more algorithms.

In this paper, we will consider the problem of the diverse spanning of the meta-feature space for the traveling salesman problem. Such spanning does not depend on algorithms, so it can be used for any algorithm, as well as for any number of algorithms. That will allow to compare performance of any number of algorithms. At any time, one can add a new algorithm, and for this you do not have to generate a new training set. It also allows to more accurately learn a meta-predictor, as well as better understand the strengths and weaknesses of the algorithm.

We consider the geometric version of TSP, in which cities are points on a 2D plane, and cost is Euclidean distance between points. In our case, the cities will be points on the plane with integer coordinates from 0 to 400. And the fixed number of cities equals to 100.

We use meta-features for the traveling salesman problem, which were used in the work [21]. Namely, a set of 11 meta-features, such as

• the standard deviation of distances;

• coordinates of the centroid of the instance points;

• the radius of the instance points, defined as the average distance from each point to the centroid;

• the proportion of different distances accurate to two decimal places;

• the rectangular area in which all the points lie;

• variance of the normalized distances to the nearest neighbors;

• the dispersion coefficient of the normalized distances to the nearest neighbors;

• the clustering factor (the ratio of the number of clusters to the number of points);

• the ratio of the number of isolated points to the total number of points;

• the variance of the number of cities in the cluster.

In order to be able to use the Euclidean distance as a measure of the proximity of the instances in the meta-feature space, we normalize the meta-features so that they lie in the range from 0 to 1. Thus, the meta-feature space becomes a 11-dimensional hypercube with a single edge.

3. Generation instances with specific meta-features

We reduce problem of generation instances with specific meta-features to optimization problem. Define the error function f.

where %i is the i-th meta-feature of x instance and pi is the target value of i-th meta-feature.

Then the problem of finding instance with specific meta-features reduces to minimizing the error function. For this we use the genetic algorithm and simulation annealing.

3.1. Simulated annealing

The simulated annealing (SA) [14] is a well-known method for solving the optimization problem. It is based on the simulation of the physical process that occurs during the crystallization of the substance, including during the annealing of metals.

The probability of selecting point x* is calculated in accordance with the Gibbs distribution:

(3)

where Ti are elements of an arbitrary decreasing positive sequence that converges to zero, which is an analog of the incident temperature in a crystal.

3.2. Genetic algorithm

Genetic algorithm (GA) [13] is a kind of evolutionary computation using methods of natural evolution. The problem is formalized so that the solution is a vector of genes, where each gene is an object from a fixed set. In its classical implementation, it is assumed that the genotype has a fixed length. In our case, the genome is a point on the plane, i.e. a pair of integers from 0 to 400. The genotype has a fixed length of 100 genes.

The fitness function is used to evaluate how well each individual solves the problem. In our case, we use the error function f is defined earlier (see Eq. 3). The smaller the error function is, the more adapted the individual is.

In this paper, the population consists of 30 individuals. This parameter, as well as other parameters for the genetic algorithm, was chosen based on the work [21].

Then follows a cycle, which is repeated for some number of generations. Two parents are selected using tournament selection, which selects 16 of individuals with the best fitness function value and randomly make pairs from them. After that, for each two selected parents using a uniform crossover that selects each gene with the probability of 50% from firs and 50% from the second parent, a new individual is obtained, which passes into the next generation. Each of new individual undergoes a mutation that replaces each point with a new random point with probability 1%. Best 30 individuals passed to new generation.

4. Spanning of meta-feature space

4.1. Diversity of instance set

We introduce instance set diversity (ISD) function V(X), which would help us to numerically evaluate how well we spanned a meta-feature space as the mean distance to the nearest instance of the set.

E min p(x, y)

v(X)=', (5)

where p(x, y) is the Euclidean distance between meta-feature vectors of instances x and y.

The more the distance from this instance to the nearest one of the given set is, the more unlikely this instance is for the rest in this set. Hence, the larger the value of V(X) is, the more diverse is the set X.

4.2. Instance-wise generation method

We use proposed in previous Section methods for generating instances with specific meta-features. Instance-wise generation method (IGM) generates instances one by one. On each step it randomly chooses target meta-features vector and tries to generate an instance with these meta-features by a method for generating a singe feature. We sample random meta-features as random vertices of 11-dimensional hypercube.

4.3. Maximizing diversity method

The Maximizing diversity method (MDM) explicitly tries to maximize diversity of the instance set. The diversity of the set is used as fitness function.

We will consistently add one new TSP instance to the set of already existing instances trying to maximize resulting diversity.

Table 1. Optimizing the initial temperature

Initial temperature Mean value of the error function

10-6 0.09508

10-5 0.09467

10-4 0.09399

10-3 0.09443

10-2 0.09368

0.03 0.09313

0.1 0.09268

0.3 0.09052

1 0.09276

10 0.12566

102 0.14411

103 0.14586

Formally it generate the set Xn of n TSP instances as

Xi+1 = Xi U jarg min V (Xi U {*})} , (6)

where genetic search is used as argmin function.

The advantage of this method in comparison with the previous one is that it does not depend on the region of admissible values of meta-features. But it depends on the choice of the initial instance of the task at each step, from which we begin the search, trying to maximize the diversity function. It may happen that this instance will be surrounded by instances and will not be able to go beyond this area, because moving in any direction from the center of this region, but not leaving it, the value of the feature of dissimilarity only decreases.

5. Experiments and Results

5.1. Best hyperparameters for simulated annealing

We decided to use the optimization of this algorithm parameter to select the initial temperature. To do this, we selected the initial temperature in the range from 10-6 to 103 and ran an algorithm with such a temperature on the prepared set of 200 vectors of random meta-feature.

As one can see in Table 1, the algorithm works more efficiently at a temperature of 0.3. Therefore, we will use SA with initial temperature T0 = 0.3.

5.2. Comparison of instance generation methods

First, we compare performance of different instance generation methods. As a baseline for the described SA and GA, we use a simple random generation. This method randomly generate points for new instance. It repeats it several times and then chooses the one that minimizes an objective function.

Fig. 1. Mean error of different instance generation methods: green is the random generation, red is simulated annealing method and blue is the genetic algorithm

Table 2. Comparison of methods for spanning of meta-feature space

Method ISD

Random generation method (RGM) 0.123

Maximizing diversity method (MDM) 0.468

Instance-wise generation method (IGM) 0.595

We use a set of 100 vectors with random values of meta-features. The error value is averaged over a set of 100 vectors to reduce the effect of selecting a single instance as the result. As we see in Fig. 1, SA and GA work better than RG. Moreover, SA shows results better than the GA, so we will use it further.

5.3. Comparison of meta-feature space spanning methods

Second, we compare performance of the proposed meta-feature space spanning methods, namely MDM and IGM with SA. As a baseline, we will use Random Generation Method (RGM), that simply generates random instances using random generation.

We generated set of 500 instances by each method and compare ISD of resulting sets.

Table 2 contains the values of ISD function for the described methods. As one can see, MDM is inferior to IGM, but the difference is not so great as with the RGM.

Figure 2 shows the 2-D projection of generated instances from 11-dimensional space obtained by visualizing two first principal components. As one can see, the methods show similar results. The IGM spanned space more expansively than MDM and RGM loses to not naive methods.

0 90 0 95 1 CO 1 05 1Д0 Î;15 1 20 1.25 130 135 1 40 1 45 1 50 1 55 1 GO 1G5 170 175 1 SO 1B5 1 90 1 95 2 00 2 05

Fig. 2. Generated instances in 2-D projection of meta-feature space: blue is the instances generated by RGM, red by MDM and green by IGM.

6. Conclusion

In this work, we focused on the problem of spanning meta-feature space of the Travelling Salesman Problem with instances of this task.

First, we propose a method for generating a travelling salesman problem instance given its meta-feature vector. This method can use a genetic algorithm or the simulated annealing. This method showed better results than random search.

Then we used this method as basis for spanning of meta-feature space method, which is trying to span the metafeature space of TSP with its instances, which we call instance-wise generation method.

Finally, we suggested a metric called instance space diversity, which represent how well the meta-feature space is spanned with generated instances. A method based on genetic algorithm, that optimized this metric, is called maximizing diversity method.

We experimentally compared these two methods with random search. The experiment results showed that both methods proved to be much more effective than the random generation. Comparison showed that the instance-wise generation method is more effective than the maximizing diversity method.

The instances set obtained using the proposed methods can be used to train the predictors of the most effective algorithm for solving a specific instance. Unlike the method proposed in [21], the resulting instances set does not depend on algorithms and can be used for any previously unknown algorithms.

Acknowledgements

The methods for spanning meta-feature space were developed under the research project financially supported by the Russian Foundation for Basic Research, Grant 16-37-60115 mol_a_dk. Their adaptations to the Travelling Salesman Problem, as well as experimental evaluations were obtained under the research project supported by The Russian Science Foundation, Agreement №17-71-30029.

References

[1] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial optimization, Vol. 605, Springer, 1998.

[2] C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: algorithms and complexity, Courier Corporation, 1998.

[3] M. Grotschel, L. Lovasz, A. Schrijver, Geometric algorithms and combinatorial optimization, Vol. 2, Springer Science & Business Media, 2012.

[4] S. Raff, Routing and scheduling of vehicles and crews: The state of the art, Computers & Operations Research 10 (2) (1983) 63-211.

[5] Y. Crama, Combinatorial optimization models for production scheduling in automated manufacturing systems, European Journal of Operational

Research 99 (1) (1997) 136-153.

[6] C. Blum, A. Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM computing surveys (CSUR) 35 (3) (2003) 268-308.

[7] D. H. Wolpert, W. G. Macready, No free lunch theorems for optimization, Evolutionary Computation, IEEE Transactions on 1 (1) (1997) 67-82.

[8] D. H. Wolpert, W. G. Macready, et al., No free lunch theorems for search, Tech. rep., Technical Report SFI-TR-95-02-010, Santa Fe Institute (1995).

[9] R. Vilalta, Y. Drissi, A perspective view and survey of meta-learning, Artificial Intelligence Review 18 (2) (2002) 77-95.

[10] P. Brazdil, C. G. Carrier, C. Soares, R. Vilalta, Metalearning: Applications to data mining, Springer Science & Business Media, 2008.

[11] J. Rice, The algorithm selection problem, Academic Press 15 (1976) 65-118.

[12] A. Zabashta, A. Filchenkov, Ndse: Instance generation for classification by given meta-feature description, in: Proceedings of the International Workshop on Automatic Selection, Configuration and Composition of Machine Learning Algorithms, co-located with ECML PKDD 2017, 2017, pp.102-104.

[13] M. Mitchell, An introduction to genetic algorithms, MIT press, 1998.

[14] S. Kirkpatrick, C. D. Gelatt Jr, M. P. Vecchi, Optimization by simulated annealing, Science 220 (4598) (1983) 671-680.

[15] J. H. Holland, Adaptation in natural and artificial systems, University of Michigan Press.

[16] D. L. Applegate, R. M. Bixby, V. Chvtal, W. J. Cook, The traveling salesman problem, Evolutionary Computation, IEEE Transactions on.

[17] E. L. Lawler, The traveling salesman problem: a guided tour of combinatorial optimization, Wiley-Interscience Series in Discrete Mathematics.

[18] C. H. Papadimitriou, The euclidean travelling salesman problem is np-complete, Theoretical computer science 4 (3) (1977) 237-244.

[19] M. Dorigo, L. M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on evolutionary computation 1 (1) (1997) 53-66.

[20] J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical society 7(1) (1956) 48-50.

[21] K. Smith-Miles, J. van Hemert, Discovering the suitability of optimisation algorithms by learning from evolved instances, Ann Math Artif Intell 61 (2) (2011)87-104.

[22] K. Smith-Miles, T. T. Tan, Measuring algorithm footprints in instance space, Congress on Evolutionary Computation (2012) 1-8.

[23] K. Smith-Miles, D. Baatar, B. Wreford, R. Lewis, Towards objective measures of algorithm performance across instance space, Computers & Operations Research 45 (2014) 12-24.

Generating Datasets for Classification Task and Predicting Best Classifiers with Conditional Generative Adversarial

Networks

Ilya Kachalsky, Alexey Zabashta, Andrey Filchenkov, Georgiy Korneev

ITMO University 197101 49 Kronverksky Pr. St. Petersburg, Russia

[e-mail], [e-mail], [e-mail], [e-mail]

ABSTRACT

We focus on the algorithm selection problem and closely related dataset synthesis problem. We present conditional deep convolutional generative adversarial network we call LM-GAN, generator of which is capable of synthesizing dataset for classification in the matrix form with numeric features and discriminator of which can perform the best classifier prediction for a new never seen dataset. We also suggest a technique for transforming matrices representing datasets to a canonical form. Experimental evaluation shows that the presented network working with matrices in the canonical form outperforms baseline solutions in dataset synthesis and the best classifier prediction.

CCS Concepts

•Computing methodologies ^ Neural networks; Supervised learning by classification; Adversarial learning;

Keywords

Machine Learning; Meta-Learning; Neural Networks

1. INTRODUCTION

In machine learning and optimization, the number of algorithms and approaches capable to handle a task is high enough to rise the problem of algorithm selection. It can be formulated in the following way. Assume we are given a certain task (say, classification or travelling salesperson problem), a set of algorithms that can find a solution for instances of this task, and some performance measure reflecting how well an algorithm solves a task instance. The question is how to select an algorithm for a given instance that is the best with respect to the measure without direct evaluation of algorithm performance on this instance. Rice was the first to state this problem [1], while No Free Lunch

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [e-mail]. ICAAl 2019 October 26-28, 2019, Istanbul, Turkey © 2019 ACM. ISBN 978-1-4503-7253-4/19/10... $15.00 DOI: 10.1145/3369114.3369153

theorems [2] showed that it cannot be solved if we do not have any prior information of a given instance.

A common way to represent such prior knowledge about different instances, or datasets if we consider machine learning tasks, is to use so-called meta-features [3] that are properties of datasets. Once each dataset is associated with a vector of meta-features values, knowledge on how the algorithms perform on some selected datasets can be transferred to make predictions about their performance on a new previously unseen dataset. Meta-features are used for selecting and tuning machine learning and optimization algorithms [4], as well as for algorithm analysis [5].

The number of meta-features used for such prediction is typically several dozens. This results into a lack of real worlds datasets and their low diversity due to the number of existing datasets for a specific task rarely greater than 1000 and they are usually located only in a small number of regions in the meta-feature space. This stimulates search of methods for synthesizing artificial datasets. Existing work on this issue can be divided into two groups. Earlier approaches for dataset synthesis had very limited control on properties which resulting dataset will have [6]. Later approaches are based on using evolutionary algorithms for synthesizing dataset with required properties [7, 8]. This allows for guiding dataset synthesis process at the cost of time required for such synthesis.

The problem of synthesizing complex objects can be solved with generative adversarial networks (GANs) [9] that gained popularity in last few years because of success they showed in generating voice [10], music [11] or even drugs [12, 13], but most of all, images [14, 15, 16, 17]. Being inspired by how powerful GANs are in generating structured objects, we decided to find out if they can be utilized to generate new datasets.

Matrix is the most common structure for datasets in many popular tasks such as classification, clustering or even travelling salesman problem. However, the question of if we can utilize GANs to generate datasets in matrix form is challenging because of one detail. Due to exact order of objects and features has no importance, swapping any two rows or column in the corresponding matrix would produce a matrix representing very same dataset. This is very different from images, where order of columns and rows is fixed. As con-volutional layers application is strictly based on an assumption of feature locality, which is not observed in our case, convolutional GANs cannot be directly applied for dataset

synthesis.

In this paper, we overcome this limitation by 1) proposing a strategy for prepossessing symmetric datasets and 2) modifying CGANs approach for the classification algorithm selection problem. We focus on datasets that have numeric features and a single label as a special feature. We propose 1) matrix processing and transformation operations helping to reduce equivalent matrices to a canonical form, 2) a generative adversarial network capable to generate such matrices, 3) algorithms to train such network.

The rest of this paper is organized as follows. Section 2 describes operations for transforming matrices representing datasets to a canonical form. Section 3 describes the proposed generative adversarial network and algorithms to train it. Finally, in the Section 4, we experimentally compare several datasets processing methods and approaches for the algorithm selection problem.

2. DATASET NORMALIZATION

In this Section, we propose several normalization methods helping to transform all matrices representing the same dataset to a single form. In all methods, we will apply the scaling of columns to 0-1 range.

2.1 Diagonalization

Due to dealing with datasets for the classification task, we can split a given matrix into several sub-matrices that would contain only rows corresponding to a certain class. We want to transform these sub-matrices in such a way that all of them would have a common pattern at their main diagonals. There are only two operations which we can apply to submatrices without changing information they contain: we can simultaneously swap columns in all submatrices and swap independently rows in each of them. This is why we will try to transfer matrix to have most of its values near its main diagonal.

Let the number of features be m and the number of objects in i-th submatrix in dataset be n%. Assume that m >

where

. Define vk (ci,j) =

= Topfc(cj,j) _

7l(cj,j )—Topk ( Ci,j )

Topk(ci,j) is the sum of k largest elements in the column ci,j and Sum(cij) is the sum of all elements in the column ci,j.

An algorithm we propose for matrix normalization consists of the following steps:

1. Mark all elements in all submatrices as active.

2. For each sub-matrix i set ki = , where ni is the number of remaining active rows in the i-th submatrix.

3. Find the column c in which vk(c) is maximal over all active elements in all submatrices. Note that vk(c) considers only active elements in the current column.

4. Swap the first active column with c simultaneously in all sub-matrices.

5. For each submatrix i swap rows in it such that first ki active rows will be sorted in decreasing order by the first active column and contain the largest active elements in current column.

6. For each submatrix i mark all elements in the first active column and k first active rows as inactive and go to the Phase 2 if the matrix still contains active elements.

By using this algorithm, we not only deal with isomorphic data but also give convolutional layers in neural network relational property to grasp onto. You can find a step-by-step example of dataset diagonalization in Figure 1.

2.2 Minimize Difference

Another possible normalization method we consider in this paper is to rearrange the rows and columns so that the sum of the absolute or squared difference between the adjacent rows and columns will be as small as possible. The problem of this method is that underlying task of sorting columns in rows in such way is travelling salesperson problem, solving it is computationally costly.

2.3 Sort by Correlation

The previous methods used only matrix cell values. It may also be useful to use class information. Consider the following method. Sort the columns by the absolute correlation with the class, and sort objects by the value of their scalar product with the feature correlation vector.

3. GENERATIVE ADVERSARIAL NETS 3.1 General Idea and Task Statement

Generative Adversarial Networks is an unsupervised learning technique of training two neural networks: a discriminator and a generator [9]. The main goal is to train the generator to produce new data from the real world data distribution, while the discriminator is useful only for training the generator. Conditional Generative Adversarial Networks (CGAN) [18] are generalization of GAN, in which generator output and discriminator input are conditional. In this paper, we adopt CGAN for the best algorithm prediction problem. We use the generator to synthesize datasets with required meta-features values and use discriminator to predict the best algorithm for a previously unseen dataset.

Let us first specify the task of dataset synthesis given the meta-features values. Let Q be set of all datasets, d 6 Q be one instance. Then vector of meta-features values of length n can be defined as some function y(d) : Q ^ Rn. Let A be a set of m algorithms, from which we want to find the best one to be applied to d. Lambda-feature is a vector of 0 and 1 values and length m, in which 1 indicates the best performing algorithm from A on d. Note that this vector may contain several 1 because several algorithms can share the best score. Then we can define function ЛA(d) : Q ^ [0,1]m. With this in mind, we can define the task of generating dataset given its meta-features values as finding M such as M(y) : Rn ^ D. Then we can define the task of determining the best algorithm on a given dataset as a search for D(y) : Rn ^ [0,1]m. Stating tasks in this way helps to highlight motivation for using GANs because it looks similar to the formal definition of CGAN. In this paper, we suggest the usage of CGAN with convolutional layers.

To solve the proposed task of generating dataset given y and determining Л based on d, we propose new GAN architecture which we call LM-GAN. It is similar to CGAN, in which generator is defined as G(y,z) where z is a random noise sampled from the Normal distribution of zero mean and unit variance. Discriminator in our model will output vector of length m +1. In this vector, the first position is how real is the given dataset and the rest are its Л. In order

76 96 63 96 76 63 96 76 63 96 76 63 96 76 63

80 68 32 68 80 32 94 30 64 94 30 64 94 30 64

83 47 31 47 83 31 68 80 32 47 83 31 47 83 31

54 43 37 43 54 37 47 83 31 68 80 32 68 80 32

30 94 64 94 30 64 43 54 37 43 54 37 43 54 37

82 71 61 71 82 61 89 74 98 89 74 98 89 74 98

74 89 98 89 74 98 71 82 61 71 82 61 71 82 61

60 67 34 67 60 34 67 60 34 49 95 48 49 95 48

95 49 48 49 95 48 49 95 48 67 60 34 67 60 34

Step 1 Step 2 Step 3 Step 4 Step 5

Figure 1: Step by step example of dataset diagonalization. First we begin with two submatrices with 3 features describing 5 objects of one class and 4 objects of another class. Active elements are marked as bold. At the first step ki = k2 = 2, v(cM) = 8°+83 - 78+5542+3° = 28.1(6), v(cla) = 42.(3), v(cM) = 30.1(6), v(c2A) = 21.5, v(c2,2) = 22, v(c2,3) = 38.5. So we select the second column and swap it with the first. At the second step we swap the rows and mark elements as inactive. In the third step ki = 2, k2 = 1 and first active column already contains maximum value v(c) = 95. At the fourth step, we have one active element left in each submatrices. In the fifth step, we have no active elements left and the algorithm is terminated.

Figure 2: Architecture of LM-GAN

to train such model on datasets, we need to propose a loss functions.

The scheme of the proposed LM-GAN architecture can be found in the Figure 2.

3.2 Generator architecture

The generator is basically a deconvolutional neural network, which transforms a vector into a matrix. It is based on the same architecture as for image processing, but the output matrix is not square. Therefore the parameters for different axis are different for the last layers. The generator consists of 5 layers:

1) z:ConvTranspose2d(4,1,0), p:ConvTranspose2d(4,1,0)

2) ConvTranspose2d(4,2,1)

3) ConvTranspose2d(4,2,1)

4) ConvTranspose2d((4,1),(2,1),(1,0))

5) ConvTranspose2d((4,1),(2,1),(1,0))

We use Leaky ReLU (alpha = 0.2) activation functions between the layers. We took the implementation of these layers from PyTorch library [19]. We set the generator loss to be Lg = L(0 - D°(G(z,p),p')).

3.3 Discriminator architecture

The architecture of the discriminator is similar to a reversed architecture of the generator:

1) d:Conv2d((4,1),(2,1),(1,0))

2) Conv2d((4,1),(2,1),(1,0))

3) Conv2d(4,2,1)

4) Conv2d(4,2,1)

5) Conv2d(4,1,0), p:Linear(23)

6) Linear(4)

Loss of discriminator consists of two parts: Lreal and Lfake. Lreai can be defined as L(A — Di..m+i (d, p)) + L(0 — D°(d, p)), where the first part represents how wrong the discriminator determined lambda-features and the second part represents how bad was real/fake prediction. Similarly Lfake = c(p,p') • L[A' — Di..m+i(G(z,p),p')] + L(1 — D°(G(z, p), p')), where p' are meta-features of generated dataset, A' are lambda-features of generated data, c(p, p) is a smoothing coefficient c(p, p') = exp(— \\p — p'||2).

4. EXPERIMENTS 4.1 Data Preprocessing

To test different algorithm selection approaches, we take 976 datasets for classification task from OpenML resource [20]. We performed the following data processing to obtain the collection of datasets in which each dataset has 2 classes, 128 objects (64 objects of each class) and 16 features:

• If there are more classes in the set than required, we divide this dataset into parts corresponding to each class. Next we compose all possible combinations of parts with two different classes. In this way, we will get new data sets with the required number of classes, as well as increase the number of datasets for training. Note that for each dataset obtained using this procedure, we remember the parent dataset to prevent the descendants with the same parent were distributed into the training and test set.

• If the number of features is greater than the specified, we selected the required number of features using the SelectFromModel algorithm from scikit-learn library, which was based on the ExtraTreesClassifier (n_estimators = 50).

• If the number of objects is greater than the specified one, then we remove randomly selected objects until we reach the required number.

Table 1: Average MSE of the relative performance prediction. MF stands for methods that base their predictions on meta-features. RD stands for raw datasets. DD stands for diagonalized datasets, this approach was described in subsection 2.1. The last two methods combine the first and the latter.

MF RD DD MF + RD MF + DD

DT kNN DNN GAN 0.406 ± 0.0149 0.332 ± 0.0081 0.278 ± 0.0112 0.243 ± 0.0007 0.199 ± 0.0008 0.233 ± 0.0011 0.194 ± 0.0008 0.234 ± 0.0020 0.197 ± 0.0005 0.225 ± 0.0019 0.191 ± 0.0006

After processing, we obtained 9911 datasets for binary classification problem. They were divided into two parts: 8000 were used for training and 1911 for testing.

4.2 Meta-features

We use the 23 meta-features described in [21]. They include statistical: Pearson correlation, coefficient of kurtosis and asymmetry; information-theoretical: maximum and average general information, entropy of class labels, signal-to-noise ratio, average entropy of features; decision tree structure: number of leafs, number of vertices, tree width; mean, minimum, maximum and standard deviation of leafs depth, attributes values and vertices per level.

We use Mahalanobis distance as distance in meta-feature space. The covariance matrix for this distance was estimated by all 9911 datasets.

4.3 Algorithm Prediction Experiment Setup

We conduct several experiments to test different algorithm selection approaches. In all experiments, we tried to predict the relative performance of the three algorithms from the Python Scikit-learn library [22]: kNN is KNeighborsClas-sifier(^neighbors=3), SVM is SVC(gamma=2, C=1, ran-domjtate=0), Naive Bayes is GaussianNB(). Knowing relative performance allows for predicting the best algorithm for a given dataset. Due to we run all the algorithms on all the datasets, we already know, which of these algorithms is the best and we use this information as a ground truth for all the datasets. The quality of predictions was evaluated as Mean Squared Error of the relative performance prediction for datasets from the test set.

At the first experiment we tried to predict the relative performance of algorithms using only meta-features. This made it possible to compare with neural network (DNN). As baseline models for comparison, we use Decision tree (DT) and k-nearest neighbors algorithm (kNN) that were used as meta-classifiers.

At the second experiment we tried to evaluate if the diag-onalization technique described in Section 2 is really helpful. To do so, we compare usage of datasets after diagonalization with dataset that we will refer to as raw datasets. However, in datasets, rows and columns can initially be ordered in a certain sequence. Therefore, we will shuffle the rows of the same class and columns in dataset so that the algorithm tries to look for dependencies on the data itself, and not on these sequences. In this case, we cannot use the baseline meta-classifier we used at the first experiment, but we can use GAN to train neural network.

At the third experiment, we tried to predict the relative performance by both meta-features and usage of diagonal-ization technique.

Each experiment was conducted 4 times and training of

Table 2: Average Mahalanobis distance in metafeature space for different datasets generation approaches and baseline average pairwise distance.

Evolutionary algorithm I 1.005 ± 0.0017 Generator from MF + RD GAN 1.147 ± 0.0126 Generator from MF + DD GAN 1.116 ± 0.0044 Average pairwise distance 1.412

neural networks was limited to 20 epochs.

4.4 Algorithm Prediction Results

The results of all three experiments are presented in Table 1. As you can see, the Discriminator of the proposed GAN is better than a simple neural network. Also, the convolution that uses diagonalized instead of raw datasets showed the best result in all experiments.

4.5 Dataset Synthesis Experiment Setup

After training the proposed GAN for the third experiment, we obtain not only Discriminator, which can predict the relative performance, but also the Generator which can generate new datasets given their meta-feature vectors.

At the fourth experiment, we decided to test how efficient is this method for dataset synthesis. We compare this method with the evolutionary algorithm described in [8, 23]. Note that we cannot directly compare these approaches due our approach is divided into phases of learning and synthesis while the evolutionary algorithm has only a synthesis phase, which works slower but more accurate. We compared them on the same number of processed datasets, namely 8000 - 20 because at each epoch our approach processed 8000 datasets and there were 20 epochs in total.

Each of the two models were asked to generate datasets given meta-features values of each of the dataset in the test set. We use Mahalanobis distance between target metafeature vector and meta-features of synthesised dataset as a loss function.

4.6 Dataset Synthesis Results

The results of this test are presented in Table 2. As you can see, our approach is slightly worse than the evolutionary algorithm, but it is still better than the baseline average pairwise distance. Also the method that works with diago-nalized instead of raw datasets showed the better and more stable result again.

5. CONCLUSION

In this paper, we proposed a generative adversarial network LM-GAN, which allows for obtaining the relative per-

formance prediction meta-system. We also proposed several methods for adapting convolutional and deconvolutional networks to the processing of datasets for classification.

We experimentally compared the proposed method on task of predicting the best classification algorithm given a dataset. We showed that the use of convolutional layers with the proposed canonical matrix form makes it possible to improve the quality of prediction based only on meta-features. Also we showed that the methods based on diagonalization instead of raw datasets work better and show more stable performance. Finally, we showed that it is possible to use the generator of the proposed GAN as a generator of new datasets for classification task.

6. ACKNOWLEDGMENTS

The work on the dataset generation was supported by the Russian Science Foundation (Grant 17-71-30029). The work on the other results presented in the paper was supported by the RFBR (project number 19-37-90165) and by the Russian Ministry of Science and Higher Education by the State Task 2.8866.2017/8.9.

7. REFERENCES

[1] John R Rice. The algorithm selection problem. In Advances in computers, volume 15, pages 65-118. Elsevier, 1976.

[2] David H Wolpert and William G Macready. No free lunch theorems for optimization. IEEE transactions on evolutionary computation, 1(1):67-82, 1997.

[3] Pavel Brazdil, Christophe Giraud Carrier, Carlos Soares, and Ricardo Vilalta. Metalearning: Applications to data mining. Springer Science & Business Media, 2008.

[4] Matthias Feurer, Jost Tobias Springenberg, and Frank Hutter. Initializing bayesian hyperparameter optimization via meta-learning. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.

[5] Kate Smith-Miles and Thomas T Tan. Measuring algorithm footprints in instance space. In 2012 IEEE Congress on Evolutionary Computation, pages 1-8. IEEE, 2012.

[6] Jim Young, Patrick Graham, and Richard Penny. Using bayesian networks to create synthetic data. Journal of Official Statistics, 25(4):549, 2009.

[7] Kate Smith-Miles, Davaatseren Baatar, Brendan Wreford, and Rhyd Lewis. Towards objective measures of algorithm performance across instance space. Computers & Operations Research, 45:12-24, 2014.

[8] Alexey Zabashta and Andrey Filchenkov. NDSE: instance generation for classification by given meta-feature description. In CEUR Workshop Proceedings, volume 1998, pages 102-104, 2017.

[9] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672-2680, 2014.

[10] Yuki Saito, Shinnosuke Takamichi, and Hiroshi Saruwatari. Statistical parametric speech synthesis incorporating generative adversarial networks. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 26(1):84-96, 2017.

[11] Hao-Wen Dong, Wen-Yi Hsiao, Li-Chia Yang, and Yi-Hsuan Yang. Musegan: Multi-track sequential generative adversarial networks for symbolic music generation and accompaniment. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.

[12] Evgeny Putin, Arip Asadulaev, Quentin Vanhaelen, Yan Ivanenkov, Anastasia V. Aladinskaya, Alex Aliper, and Alex Zhavoronkov. Adversarial threshold neural computer for molecular de novo design. Molecular Pharmaceutics, 15(10):4386-4397, 2018.

[13] Alex Zhavoronkov, Yan A Ivanenkov, Alex Aliper, Mark S Veselov, Vladimir A Aladinskiy, Anastasiya V Aladinskaya, Victor A Terentiev, Daniil A Polykovskiy, Maksim D Kuznetsov, Arip Asadulaev, et al. Deep learning enables rapid identification of potent ddr1 kinase inhibitors. Nature biotechnology, pages 1-4, 2019.

[14] Emily L Denton, Soumith Chintala, Rob Fergus, et al. Deep generative image models using a laplacian pyramid of adversarial networks. In Advances in neural information processing systems, pages 1486-1494, 2015.