СИМВОЛЬНАЯ РЕГРЕССИЯ

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

Основные определения

Введем некоторые определения, которые будут использованы в работе.

Определение 1. Регрессия – операция подбора математического выражения, определяющая зависимость переменной  y от входной переменной x, при условии, что выражение имеет статическую значимость, то есть переменные сильно коррелируют друг с другом и мала вероятность случайного возникновения значений выходной переменной.

Определение 2. Целевая функция – функция нескольких переменных, подлежащая оптимизации (минимизации или максимизации), в зависимости от рассматриваемой некоторой оптимизационной задачи.

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

Введение

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

Постановка проблемы

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

Оптимизационная задача

Пусть у нас имеется система, которая при подаче на постоянный сигнал, выдает соответствующее значение выходного сигнала. Имея n наблюдений, можно найти зависимость выходного значения системы от её входа. Другими словами нам нужно найти правило f такое, что y=f(

В основном задача сводится к тому, что мы выбираем, например, линейную зависимость y=kx+b и определяем параметры k и b. В данном случае нам достаточно выбрать из n наблюдений всего лишь 2 значения для нахождения параметров функции, так как у нас 2 неизвестные k и b.

Возникает проблема: по каким 2 наблюдениям следует аппроксимировать функцию. Полученное правило f может сильно расходиться с оставшимися наблюдениями. Для нахождения оптимальных параметров используем метод наименьших квадратов.

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

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

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

Генетический алгоритм

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

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

1) На начальном этапе создается популяция (значения переменных для целевой функции);

2) Размножение или скрещивание, когда часть одного генотипа сливается с частью другого генотипа (выбираются пары векторов, и происходит формирование новых, путем заимствования компонент одного и другого вектора);

3) Мутация (выбираются часть векторов, и случайным образом меняются компоненты этих векторов);

4) Вычисление значений “функции приспособленности” для всех генотипов;

5) Селекция или отбор (выбирается часть векторов, дающих наилучшее значение целевой функции);

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

Символьная регрессия

Формально символьную регрессию можно рассматривать как суперпозицию некоторых заданных функций.

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

Рисунок 1. Пример генотипа.

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

Рисунок 2.Операция скрещивания.

Мутациями могут быть случаи:

Рисунок 3. Мутация со знаком.

Рисунок 4. Мутация с функцией.

Рисунок 5. Мутация с заменой ветки генотипа.

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

Заключение

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

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

1. Toby Segaran. Programming collective Intelligence. USA, Sebastopol: O’Reilly

Media, 2007. – 362 c.