pátek 6. března 2015

Jak naprogramovat umělou inteligenci při výpočtu matematických příkladů

Již od 6. třídy základní školy hledám odpověď na to, jak správně udělat program, který zvládne vyřešit (téměř) libovolný matematický problém, podobně jako by to dělal člověk, podá kompletní postup a nakonec ještě výsledek v mnoha formátech. Řešení jsem již nalezl a tento článek má sloužit jako teoretický nádech toho, jak to zhruba funguje.

Nebojte se rekurze

Znáte lepší příklad rekurze, než samotnou matematiku? Již paní učitelka na Základní škole říkávala: "Matematika je královna všech věd, protože všechno vychází ze všeho a vše je vzájemně propojeno."

Sice jsem tomu tehdy moc nerozuměl, ale jak plynul čas, tak jsem pochopil samotnou podstatu toho všeho. Pro vyřešení libovolného matematického problému v zásadě nepotřebuji mít pokročilé znalosti dané problematiky, stačí jen znát obecná pravidla a naprosto vše lze odvodit na základě předchozích znalostí.

Asi vás napadá, že takto nemůžeme pokračovat do nekonečna a nějaké základní znalosti mít musíme, takže si nejprve definujeme seznam základních pravidel, o kterých prohlásíme, že platí za jakýchkoli okolností a nebudeme je hlouběji zkoumat (aspoň tedy ne po programové části). Tyto základní (primitivní) entity budou tvořit jádro našeho systému, takže jakýkoli složitější problém půjde postupně rozdělit na kombinaci těchto pravidel.

V rámci úspory zde nebudu vypisovat všechna pravidla, která moje jádro využívá, takže bude muset stačit jen několik příkladů. Veškeré "vzorečky" jsou pouze symbolické:

  1. Znaky 0, 1, 2, 3, 4, 5, 6, 7, 8 a 9 jsou čísla.
  2. Mezi čísly lze použít tyto operace: + (sčítání), - (odčítání), * (násobení, opakované sčítání), / (dělení, opakované odečítání), ^ (mocnění, opakované násobení), ...
  3. Mocnění má přednost před násobením a dělením, násobení a dělení má přednost před sčítáním a odčítáním.
  4. sin, cos, tg, tan, log, ... jsou funkce (definovány se samostatným algoritmem, využívám zabudovaných funkcí přímo v PHP).
  5. samovolně ležící znak (rozmezí a-z) je proměnná, skupina znaků je buď funkce (zjišťuje se podle tabulky, nebo skupina proměnných, které se mezi sebou násobí).
  6. znak "=" znázorňuje rovnost, obě strany si musí být rovny.

Takto můžeme pokračovat dál a definovat si veškeré matematické poučky, až vytvoříme obrovskou znalostní bázi toho, co vše se může v zápisu vyskytovat. V zásadě pouze popisujeme chování jednotlivých entit, nikoli postupy, jak s nimi pracovat.

Těžkou práci nechme strojům

Představme si, že máme k dispozici počítač, který zná veškeré matematické poučky pouze na teoretické bázi a ještě nikdy neřešil nějaký konkrétní příklad, vůbec nezná žádné chytré metody, zkrátka se neučil jako člověk, ale jako stroj.

Jak si tedy poradí s následujícím příkladem?

5 + 3 * x = 20

Na tuto otázku neexistuje jednoznačná odpověď, protože jsme ještě nezačali počítat a nemáme k dispozici žádný vyhodnocovací algoritmus, pouze seznam základních pravidel. Pojďme si tedy nejprve teoreticky říct, jak by program měl postupovat a čeho by si měl všímat.

Už jenom podle syntaxe příkladu je jasné, že si jej musí podle naučených pravidel rozdělit na několik oblastí, které bude řešit samostatně a opět použije stejná pravidla. Protože jsou matematické zápisy strukturované a záleží na pořadí jednotlivých entit a platí nejrůznější pravidla ohledně přednosti, tak se dělení na jednotlivé elementy musí provést rekurzivně. Ideálně tedy tak, že se nalezne první rozdělující pravidlo, zavolá se znovu dělící funkce s rozdělenými objekty a takto se pokračuje dále, než je vše rozděleno na triviální elementy, které lze řešit přímo.

  1. Nejprve tedy program zjistí, že zápis obsahuje znak "=", který celý příklad dělí na 2 nezávislé části. Provede tedy hrubé rozdělení řetězce se vstupem na 2 nezávislé a zavolá je jako argument vyhodnocovací funkce, která provedla toto rozdělení (zkrátka spustí rekurzi).
  2. Rozhodovací funkce se spouští znovu a tentokrát má za úkol zpracovat 2 různé vstupy. Neví jak, jediné co ví je fakt, že její výstup musí vyhovět podmínce rovnosti obou vstupů. Začne tedy znovu aplikovat další vhodný vzorec ze své znalostní báze.
  3. Dále si všimne, že násobení má přednost před sčítáním, takže nejprve musí násobit a poté výsledek přičíst. Není nic lehčího, než proces násobení převést rovnou na výsledek - ale na jaký, když je v předpisu neznámá proměnná? To ještě nevíme, ale můžeme si na to napsat opět rekurzi a poznamenat si podmínku toho, jaký očekáváme výstup.

    V kódu by to mohlo vypadat třeba takto:
    5 + rekurze("3*x")
  4. Dobrá, máme k dispozici už jen sčítání dvou entit, to je triviální, takže ukončujeme rekurzi, náš "strom" pravidel je hotový a můžeme jít vyhodnocovat.
Vyhodnocení pravidel

V této fázi máme k dispozici seznam pravidel, která musíme splnit, abychom našli řešení. Pravidla jsme si vytvořili na základě rekurze, která podle naučených vzorců prošla zadání.

Protože program ví, že se obě strany musí rovnat a že znak "x" představuje proměnnou (nějaké číslo), tak může začít zkusmo dosazovat, než se trefí. V tomto není žádná logika, program to bude zkrátka jenom zkoušet a za nějaký čas se dostane k výsledku.

Při každém pokusu o nějaké řešení provede analýzu všech podmínek a pokud se všechny splní, tak je program ukončen a vypíše se výsledek. Pokud by bylo vstupních podmínek mnoho, tak můžeme nasadit nějaký algoritmus, který bude hlídat postupné "blížení" k výsledku a bude omezovat kroky, které nemají smysl a akorát plýtvají čas.

Expení znalostí

Pokud takový program vypočítá mnoho různých příkladů, tak si může postupně ukládat, jak postupoval a jaké metody vedly často k dobrému výsledku. Pokud se nějaká metoda dobře osvědčí, tak jí může zařadit jako nové pravidlo a příště ji nebude muset znovu odvozovat a bude "chytřejší" a hlavně rychlejší.

Na podobném principu funguje i lidský mozek a jeho schopnost provádět nové objevy při zkoumání světa. Efektivitu zatím neřešme, takto jsme totiž sestrojili plně funkční univerzální "mozek", který se popere s téměř libovolně složitým úkolem. Bude jen vyžadovat definici toho, co může udělat a další definice si postupně vytvoří (spíše odvodí na základě pozorování) sám.

Pokud bychom měli opravdu hodně výpočetního výkonu, tak můžeme takto prakticky sestrojit umělou inteligenci, ale to je v současné době spíše nereálné, protože tato metoda neřeší mnoho problémů, které reálně nastanou. Cílem článku bylo spíše vysvětlení toho, jaké myšlenkové metody jsem při návrhu umělé inteligence ve svém vyhledávači použil.