REPOZITORIJ > REZULTATI

Povzetek

Odkrivanje enačb, tesno povezano s simbolno regresijo in pogosto obravnavano pod tem
izrazom, preučuje metode za iskanje simbolnih enačb, ki opisujejo zakonitosti v opazovanih
podatkih. Večina obstoječih pristopov k odkrivanju enačb je zasnovana za šumne meritve,
zato je njihov cilj predvsem odkrivanje približnih enačb. V številnih matematičnih okoljih
pa približki niso dovolj; cilj je iz podatkov brez šuma rekonstruirati eksaktne enačbe. V
tej disertaciji uvedemo eksaktno odkrivanje enačb, obliko odkrivanja enačb, usmerjeno v
iskanje enačb, ki opazovane podatke rekonstruirajo eksaktno (torej brez napak) in so, kadar
je to mogoče, ekvivalentne izhodiščnim enačbam.
Izhodišče disertacije je potreba po odkrivanju eksaktnih zakonitosti v matematičnih
podatkih, kakršna so celoštevilska zaporedja iz spletne zbirke On-Line Encyclopedia of Integer
Sequences, OEIS. Obstoječi pristopi k odkrivanju enačb običajno izhajajo iz približne
simbolne regresije ali iz specializiranih metod eksperimentalne matematike in računalniške
algebre. To delo povezuje obe vrsti pristopov z razvojem širše uporabnih metod za eksaktno
odkrivanje enačb, utemeljenih v teoriji števil in računski algebraični geometriji.
V disertaciji razvijemo dva algoritma. Prvi, Diofantos, problem eksaktnega odkrivanja
enačb nad celimi števili prevede na reševanje sistemov linearnih diofantskih enačb. Pri
tem Diofantos aproksimativno naravo regresije nadomesti z eksaktno aritmetiko in metodami
za reševanje diofantskih enačb ter tako omogoča odkrivanje polinomske enačbe, ki
se z opazovanimi podatki ujemajo brez odstopanj. Drugi algoritem, MoadeeB, obravnava
odkrivanje enačb kot izračun ideala polinomov, ki so ničelni na opazovanih podatkih. Z
Gröbnerjevimi bazami MoadeeB omogoča odkrivanje eksaktnih polinomskih, implicitnih
polinomskih in racionalnih enačb nad celimi in racionalnimi števili.
Metodi ovrednotimo na obsežnih testnih množicah iz OEIS in na sintetičnih testnih
množicah, ustvarjenih na podlagi polinomskih, racionalnih in implicitnih polinomskih
enačb. Na več kot 30.000 zaporedjih spletne zbirke OEIS rekonstruirata številne znane
relacije in odkrijeta tudi nekatere doslej nedokumentirane relacije. Po uspešnosti sta
konkurenčni najsodobnejšim pristopom simbolne regresije, sinteze programov in eksperimentalne
matematike. Njuno praktično vrednost dodatno pokažemo z odkritjem ene
poenostavljene rekurzije in dveh predhodno neznanih rekurzivnih relacij za zaporedja
OEIS; uredniki OEIS so te rezultate nato vključili v zbirko. Sintetične preizkusne množice
potrdijo, da se metodi dopolnjujeta: Diofantos je najprimernejši za polinomske enačbe,
MoadeeB pa za racionalne in implicitne enačbe.
Disertacija kot celota prinaša tri glavne prispevke. Prvič, eksaktno odkrivanje enačb
opredeli kot samostojno nalogo na stičišču odkrivanja enačb in eksperimentalne matematike.
Drugič, za to nalogo uvede dve komplementarni metodi. Tretjič, odkrivanje rekurzij
iz celoštevilskih zaporedij preoblikuje v problem odkrivanja enačb in s tem simbolno regresijo
neposredneje poveže z matematičnimi podatkovnimi zbirkami, kot je OEIS. Rezultati
kot celota kažejo, da je eksaktno odkrivanje enačb izvedljiv in obetaven pristop k
rekonstrukciji znanih matematičnih relacij, oblikovanju novih matematičnih hipotez ter
bogatenju matematičnih baz znanja.