Как еще генетические алгоритмы могут помочь глубокому обучению?

PHYGITALISM
Aug 12, 2019 · 7 min read

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

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

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

Но нерешённых проблем в глубоком обучении остается достаточно, как в теории, так и на практике. Есть замечательная поговорка:

”Чем глубже в лес — тем злее партизаны”. (с) народ

С нейронными сетями так же:

“Чем глубже становится архитектура, тем сложнее её обучать”. (с) народ, который занимается глубоким обучением

Мы, команда Phygitalism, стараемся найти новые варианты применения глубокого обучения и новые подходы, в частности в области 3D machine learning (раздел машинного обучения, имеющий дело с 3-х мерными данными: 3D модели, сцены, облака точек и пр.). Но так же нам нравится “копаться под капотом” — разбираться в математике, скрывающейся за алгоритмами, и пытаться улучшить алгоритмы на уровне теории.

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

Публикация, разъясняющая данный подход:

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

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

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

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

Область искусственного интеллекта, которая пытается ответить на подобные вопросы, называется нейроэволюция [1]. Несмотря на первоначальный позитивный настрой учёных и исследователей, которые в конце XX века получили некоторые обнадёживающие результаты [2], сегодня методы нейроэволюции применяются в основном для вспомогательных задач глубокого обучения, например для настройки гиперпараметров алгоритмов (кстати, с этого года этот подход входит в стандарт TensorFlow). Также методы нейроэволюции успешно применяются в области обучения с подкреплением [3], но для решения основных оптимизационных задач все же принято использовать именно градиентный подход. Почему же так вышло и может ли данный подход снова стать популярным в будущем? Давайте попробуем разобраться.

В качестве экспериментальной задачи рассмотрим классификацию рукописных цифр (датасет MNIST) с помощью полносвязной нейронной сети. Архитектура рассматриваемой сети представлена на рисунке 1.

Рисунок 1. Архитектура полносвязной сети классификатора для задачи MNIST

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

Рисунок 2. Рой частиц, ищущий глобальный минимум функции

Для реализации метаэвристических алгоритмов будем использовать библиотеку PyGMO под Python 3.

Теперь нужно определиться с критерием качества (objective/fitness function), который мы будем оптимизировать. Обычно для обучения нейронной сети используют две функции: функцию потерь на обучающей выборке (loss function) и функцию-метрику качества на тестовой выборке (validation metric). Первая функция выбирается гладкой и на ней происходит оптимизация градиентным спуском. Вторая же функция обычно не является гладкой и используется для определения обобщающей способности сети.

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

После написания несложного кода можно провести несколько численных экспериментов. На графике ниже видно, что градиентный метод смог добиться почти 100% значения accuracy почти в 8 раз быстрее, чем PSO, который не достиг и 80%.

Рисунок 3. Сравнение времени и результата работы градиентного метода и PSO

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

Рисунок 4. а) Слева — пучок реализации; б) Справа — усреднение по пучку методом Монте-Карло

На рисунке 4а) можно увидеть, как растет точность от увеличения числа поколений для разных запусков (с различными random seed и лучшими из найденных параметрами алгоритма). Из усреднения 4б) видно, что алгоритм с течением времени перестает наращивать точность — для дальнейшего улучшения результата работы необходимо менять шаг/разбиение сетки.

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

Дело в том, что нейронная сеть в компьютере представляется в виде вычислительного графа, который мы умеем аналитически дифференцировать, например TensorFlow делает это автоматически после задания архитектуры. Функция потерь (Loss function, objective) алгоритма, рассчитываемая на тренировочной выборке, в отличие от доли правильных ответов (accuracy), рассчитываемой на тестовой выборке, выбирается непрерывной. А это значит, что для неё можно достаточно быстро и точно определить градиент. Поэтому градиентный метод получает своё первое преимуществодополнительная информация о ландшафте функции потерь. Вторым преимуществом градиентного метода является возможность подстраивать скорость обучения (learning rate), что позволяет на более поздних этапах обучения лучше исследовать оптимизируемые параметры на более мелких масштабах.

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

Значит ли всё вышесказанное, что ̶п̶л̶а̶с̶т̶м̶а̶с̶с̶о̶в̶ы̶й̶ градиентный мир победил? Благодаря теореме о бесплатных завтраках [4] мы знаем, что это не так. Для каждой задачи найдётся алгоритм, который её решает лучше, чем другие, и для каждого алгоритма найдутся плохие задачи.

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

Спасибо за внимание и удачных экспериментов!

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

[1] Stanley, Kenneth O. (2017–07–13). “Neuroevolution: A different kind of deep learning”. O’Reilly Media. Retrieved 2017–09–04

[2] Hiroaki Kitano Empirical Studies on the Speed of Convergence of Neural Network Training using Genetic Algorithms AAAI-90 Proceedings

[3] Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O. Stanley, Jeff Clune — Deep Neuroevolution: Genetic Algorithms are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning. arXiv:submit/2107557 [cs.AI] 18 Dec 2017

[4] Wolpert, D.H., Macready, W.G. (1997), “No Free Lunch Theorems for Optimization”, IEEE Transactions on Evolutionary Computation 1, 67

Автор

Вадим Кондаратцев / vadim@phygitalism.com

PHYGITALISM

Создаем проекты на стыке XR, ML и других интерактивных…

PHYGITALISM

Создаем проекты на стыке XR, ML и других интерактивных технологий

PHYGITALISM

Written by

Мы - команда PHYGITALISM, реализуем фиджитал-проекты и много экспериментируем с XR, интерактивными технологиями и машинным обучением.

PHYGITALISM

Создаем проекты на стыке XR, ML и других интерактивных технологий