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

Мотивация

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

Хорошо, чтобы отбросить матричную нотацию, вам нужно будет выбрать размеры входного и скрытого слоев. Допустим, есть 3 входных объекта и 4 скрытых узла. Итак, ваши матрицы:

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

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

Но вот изюминка. С помощью нейронных сетей пытаются найти оптимальные значения всех w и b, чтобы минимизировать определенную функцию потерь. Однако есть еще одна идея - исправить все символы w и b и просто изменить символическое выражение самостоятельно! Или, другими словами, изменить функциональную форму аппроксиматора. Именно в этом суть символической регрессии. Изменение, естественно, может иметь две формы. Вы можете добавить новые символьные выражения (математические операции) или удалить некоторые из существующих.

Но как?

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

Разница между генетическим программированием (GP) и более известными генетическими алгоритмами (GA) заключается в том, что GP представляет решения в виде деревьев, а GA - в виде строк. Основная причина использования представления в виде дерева - это способность фиксировать внутреннюю структуру решения. Это очень актуально в нашем приложении, поскольку каждое математическое выражение может быть представлено в виде дерева. См. Пример ниже

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

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

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

глянуть

Конечно, вы можете написать все самостоятельно, но уже есть пакеты с открытым исходным кодом, посвященные этой теме. Лучшее, что мне удалось найти, называется gplearn. Самым большим плюсом является то, что он следует API scikit-learn (методы fit и _2 _ / _ 3_).

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

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

Набор данных метрик Facebook

Чтобы проиллюстрировать, как gplearn работает на практике, давайте возьмем игрушечный набор данных, называемый метриками Facebook (ссылка) из репозитория машинного обучения UCI. Он был создан на основе неизвестной страницы бренда косметики в Facebook. См. Ниже интересующие атрибуты.

Целевая Total Interactions - это сумма всех лайков, репостов и комментариев, полученных постом после его публикации. Мы применяем некоторую предварительную обработку, а затем обучаем символический регрессор. Для простоты включены только двоичные операции по умолчанию: add, sub, mul, div. Самое подходящее решение после 20 поколений следующее.

add (add (add (mul (Почтовый час, Почтовый месяц), sub (Paid_1.0, Category_3)), add (add (mul (Почтовый час, Почтовый день недели), div (mul (Почтовый час, Почтовый месяц) ), sub (Category_3, Category_1))), mul (add (Post Weekday, Category_1), add (Type_Photo, Post Month)))), add (sub (Paid_1.0, Category_3), sub (Type_Status, Paid_1.0) )))

Ясно, что этот текстовый формат не оптимален для визуализации. См. Ниже представление в виде дерева.

Эм, так что именно это говорит? Как мне максимизировать взаимодействие? Что ж, это не имеет значения. Результат символической регрессии трудно понять, но да ладно, это действительно круто!

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

PS

Я впервые столкнулся с символической регрессией, когда просматривал публичные ядра на Kaggle (example_1 и example_2). Ожидая проработанных фрагментов кода, я не мог не рассмеяться, когда увидел эти чудовищные формулы, которым удалось получить очень приличный балл в официальной таблице лидеров.

использованная литература

  1. Коза, Джон Р. «Генетическое программирование как средство программирования компьютеров путем естественного отбора». Статистика и вычисления 4, вып. 2 (1994): 87–112.
  2. (Моро и др., 2016) Моро С., Рита П. и Вала Б. (2016). Прогнозирование показателей эффективности социальных сетей и оценка влияния на построение бренда: подход интеллектуального анализа данных. Журнал бизнес-исследований, 69 (9), 3341–3351.
  3. Документация gplearn

Обновлено: 2 июля 2018 г.

Первоначально опубликовано на jankrepl.github.io 2 июля 2018 г.