Rudoy2012Reduction

СПРОЩЕННЯ СУПЕРПОЗИЦІЙ ЕЛЕМЕНТАРНИХ ФУНКЦІЙ ЗА ДОПОМОГОЮ ПЕРЕТВОРЕННЯ ГРАФІВ ЗА ПРАВИЛАМИ

Пропонується алгоритм спрощення суперпозицій суттєво нелінійних регресійних моделей. Цей алгоритм є удосконаленням раніше запропонованих методів спрощення виразів за правилами. Суперпозиції представляються як спрямованого ациклічного графа з об'єднанням загальних поддеревьев. Таке уявлення дозволяє суттєво розширити клас допустимих перетворень суперпозицій. Доводиться коректність та повнота запропонованого алгоритму. Наводяться результати обчислювального експерименту набору синтетичних даних.

Ключові слова: спрощення виразів, символьна регресія, перетворення графів за правилами.

У ряді додатків регресійного аналізу постає завдання відновлення регресії за набором відомих даних. При цьому від моделі, що апроксимує цільову залежність, вимагається інтерпретованість експертом.

Одним із методів відновлення регресії та отримання інтерпретованих моделей є метод генетичного програмування [1–5]. Метод полягає у застосуванні принципів генетичних алгоритмів для побудови суперпозиції деяких елементарних функцій, яка б найточніше апроксимувала регресійну вибірку.

Однак при відновленні регресії за допомогою генетичного програмування виникає проблема породження надлишкових формул [6–8], тобто таких формул, в яких деякі вирази можуть бути видалені або замінені більш простими без погіршення якості апроксимації. Наприклад, якщо деяке подвыражение в суперпозиції множиться на нуль, усе це подвыражение можна замінити на нуль.

Таким чином, для побудови інтерпозиційних суперпозицій, що апроксимуютьзалежність, потрібна додаткова процедура спрощення. Крім того, процедура спрощення математичних виразів представляє самостійний інтерес і може бути застосована, наприклад, у системах комп'ютерної алгебри [9].

Раніше запропоновані такі методи спрощення суперпозицій, як спрощення виразів за правилами (rule-based simpliﬁcation, RBS) [10, 11] та заміна піддерев'я на еквівалентні, але меншої складності (equivalent decision simpliﬁcation, EDS) [12].

1 Московський фізико-технічний інститут, [email protected]

У роботах [10–12] слова «суперпозиція», «формула» та «математичний вираз» (або просто «вираз») взаємозамінні і позначають деяку композицію вільних змінних, констант та елементарних функцій. У цій роботі використовується термін «суперпозиція».

У роботі пропонується алгоритм, заснований на спрощенні суперпозицій за правилами. У цьому суперпозицією називається деяка композиція елементарних функцій, а правила описують, як пов'язані між собою. Як приклад таких правил можна вказати log exp id або t n t m t n+m .

Раніше пропонувалося [7, 9, 13–15] представляти суперпозиції у вигляді відповідного їм дерева, над яким і оперували алгоритми, що пропонувалися. У цій роботі суперпозиція представляється не у вигляді дерева, а у вигляді спрямованого ациклічного графа, де різні функції можуть приймати як аргумент одне

і той самий вираз. Прикладом може бути суперпозиція cos 2 t + sin 2 t, де t якийсь складний вираз. Таким чином, завдання, що шукається, зводиться до завдання знаходження загальних виразів у вихідному дереві суперпозиції і завдання правил спрощення на безлічі подібних ациклічних графів.

У другій частині цієї роботи поставлено завданняспрощення суперпозицій елементарних функцій за правилами. У третій частині пропонується загальний план алгоритму спрощення суперпозицій за правилами, що складається з двох етапів: перетворення дерева суперпозиції в проміжне уявлення, до якого застосовуються задані правила. Ці етапи описані у четвертій та п'ятій частинах відповідно. У шостій частині описано обчислювальний експеримент, і наведено його результати на модельних даних.

2 Постановка задачі

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

Тут під ізоморфізмом двох суперпозицій розуміється таке еквівалентне перетворення, що обидві суперпозиції дають однакові результати при тих самих значеннях вільних змінних.

Визначимо поняття, що використовуються.

Нехай задано множину G = fg i g елементарних функцій. Для кожної функції g i задана область визначення X i область значення Y i . Для більшої спільності вважатимемо, що константи є нуль-арними (нуль-місцевими) функціями функціями, які мають аргументів.

Якщо множина значень Y i функції g i міститься в області визначення X i+1 функції g i+1 , тобто

g i: X i! Y i X i+1; i = 1; 2; : : : ; 1;