Rudoy2012Намаляване
ОПРОСТЯВАНЕ НА СУПЕРПОЗИЦИИ НА ЕЛЕМЕНТАРНИ ФУНКЦИИ С ИЗПОЛЗВАНЕ НА ТРАНСФОРМАЦИЯТА НА ГРАФИКАТА СЪГЛАСНО ПРАВИЛАТА
Предложен е алгоритъм за опростяване на суперпозиции на по същество нелинейни регресионни модели. Този алгоритъм е подобрение на предложените по-рано методи за опростяване на изрази чрез правила. Суперпозициите са представени като насочен ацикличен граф с обединение на общи поддървета. Такова представяне позволява значително да се разшири класът от допустими трансформации на суперпозиции. Доказана е коректността и пълнотата на предложения алгоритъм. Представени са резултатите от изчислителен експеримент за набор от синтетични данни.
Ключови думи: опростяване на изрази, символна регресия, трансформация на графики по правила.
В редица приложения на регресионния анализ възниква проблемът с възстановяването на регресия от набор от известни данни. В същото време се изисква моделът, апроксимиращ целевата зависимост, да бъде интерпретируем от експерт.
Един от методите за възстановяване на регресия и получаване на интерпретируеми модели е методът на генетичното програмиране [1–5]. Методът се състои в прилагане на принципите на генетичните алгоритми за конструиране на суперпозиция на някои елементарни функции, които най-точно да приближават регресионната извадка.
Въпреки това, когато се възстановява регресията с помощта на генетично програмиране, възниква проблемът с генерирането на излишни формули [6–8], тоест формули, в които някои подизрази могат да бъдат изтрити или заменени с по-прости, без да се влошава качеството на приближението. Например, ако някакъв подизраз в суперпозиция е умножен по нула, тогава целият подизраз може да бъде заменен с нула.
По този начин, за да се конструират интерпретируеми суперпозиции, приближаващи желанотозависимост, е необходима допълнителна процедура за опростяване. В допълнение, процедурата за опростяване на математически изрази е от независим интерес и може да се приложи, например, в системи за компютърна алгебра [9].
По-рано бяха предложени такива методи за опростяване на суперпозиции като опростяване, базирано на правила (RBS) [10, 11] и замяна на поддървета с еквивалентни, но по-малко сложни (еквивалентно опростяване на решения, EDS) [12].
1 Московски физико-технологичен институт, rudoy@forecsys.ru
В работите [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;