Занятие 10. Символьная регрессия Краткое содержание Понятие символьной регрессии Синтаксические деревья и обратная польская запись Понятие генетического алгоритма Символьная регрессия: практический пример

Символьная регрессия - метод построения регрессионных моделей путём перебора суперпозиций заранее заданного набора функций Достоинства: 1. Возможно использовать в том случае, когда неизвестен вид модели Недостатки: 1.Ресурсоёмкость 2. Нередко полученные модели избыточно сложны Для поиска оптимальной модели применяют так называемые генетические алгоритмы. Привычная для нас запись формул сложна и неудобна для использования в генетических алгоритмах (из-за разного приоритета операций, скобок и т.п.)

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

Обратная польская запись Традиционная (инфиксная) запись Обратная польская (постфиксная) запись 2*(3+5) – (6+7)/(8-9) * / = 8; 8*2 = = 13; 8-9 = -1 13/-1 = -13; 16 – (-13) = 29 Вход Стек * / Вход Стек + 2 * / Вход Стек * / Вход Стек / Вход Стек - / Вход Стек / Вход Стек - 29 Вычисление выражения Особенности обратной польской записи: У операций отсутствует приоритет Не нужны скобки Все операции записываются единообразно Особенности работы со стеком 1. Новые значения добавляются на его вершину 2. Операции берут значения с вершины стека и помещают результат на вершину

Генетические алгоритмы Генерация исходной (случайной) популяции Отбор части популяции с использованием целевой функции Получение недостающей части популяции скрещиванием и мутациями Желаемый результат достигнут? Вернуть результат ДА НЕТ Генетические алгоритмы – алгоритмы нелинейной оптимизации. Ключевые характеристики: Работа с большим количеством потенциальных решений («популяцией») Использование целевой функции для отбора членов популяции Получение новых членов популяции операциями «скрещивания» (комбинированием) и «мутациями» (случайные изменения) Ср. с процессом эволюции в живой природе (идея генетического алгоритма была взята именно из биологии)

Пример символьной регрессии Члены популяции Выражения в обратной польской записи Члены популяции Выражения в обратной польской записи Скрещивание Шаг 1. Взять два случайных члена популяции Шаг 2. Разделить каждое выражение на две части и поменять их местами A B + C D + * => (A+B)*(C+D) C D / B A ^ + => (C/D)+B^A Результат A B + C / B A ^ + => (A+B)/C+B^A C D D + * => C*(D+D) Шаг 3. Внести случайные изменения («мутации» в коэффициенты и операции) Скрещивание Шаг 1. Взять два случайных члена популяции Шаг 2. Разделить каждое выражение на две части и поменять их местами A B + C D + * => (A+B)*(C+D) C D / B A ^ + => (C/D)+B^A Результат A B + C / B A ^ + => (A+B)/C+B^A C D D + * => C*(D+D) Шаг 3. Внести случайные изменения («мутации» в коэффициенты и операции)

Пример символьной регрессии Результат регрессии X [ ] + U- [2.0115] ^ [3.8315] [0.3417] ^ [0.6995] / [0.6995] ^ + Упрощенный результат регрессии (X – )^ (3.8315^0.3417)^0.6995/ = = (X – )^