INDUKTIVNÍ PROGRAMOVÁNÍ

inductive programming

Arnošt Veselý

Adresa autora:

Katedra informatiky, PEF ČZU v Praze, 165 21 Praha 6 - Suchdol

Anotace:

V příspěvku je porovnáno klasické (deduktivní) paradigma programování a induktivní paradigma programování. Je diskutována možnost použití těchto paradigmat pro klasický Von Neumannův počítač a pro počítač s neuronovou architekturou a obě paradigmata jsou porovnána z hlediska svých výhod a nevýhod.

Summary:

In the article is compared classical (deductive) programming paradigm and inductive programming paradigm. The possibility of aplication of these paradigms to classical Von Neumann computer and neural computer is discussed.

Klíčová slova:

neuron, neuronová síť, deduktivní programování, induktivní programovaní

Key words:

neuron, neural network, deductive programming, inductive programming

Pojem induktivního programování se objevil v odborné počítačové literatuře v poslední době (Partridge 1997). Je dáván do protikladu ke klasickému (deduktivnímu programování).

Z obecného hlediska realizuje běžící program určitý systém, který má zadavatelem přesně vymezené vlastnosti a přesně definované chování. Takovým systémem může být například databázový systém pro ukládání a vybavování dat a pro pořizování výpisů a statistik z těchto dat. Nebo to může být systém automatického řízení výrobní linky, laboratoře a pod.

Při klasickém programování ten, kdo realizuje program (tj. systémový analytik a programátor), musí (viz obr. 1). :

1. S budoucím uživatelem realizovaného systému prodiskutovat popis a chování systému v jednotlivých situacích. Komunikace s uživatelem je vedena prostředky běžného jazyka a výsledkem je tedy pouze jakýsi intuitivní popis systému.

2. Na základě intuitivního popisu systému vytvoří systémový analytik abstraktní model systému.

3. Na základě abstraktního modelu je zvoleno algoritmické řešení.

4. Je vytvořen program, který bude požadovaný algoritmus realizovat.

5. Program je testován.

Při testování se nejdříve odstraní chyby, které do realizace systému zanesl analytik nebo programátor a které způsobují, že vytvořený program se nechová přesně podle abstraktního modelu.

Potom je třeba chování testovaného systému opět diskutovat se zadavatelem. Vzhledem k tomu, že komunikace při zadávání vlastností systému mezi zadavatelem a analytikem probíhala v běžné řeči a intuitivně, dochází často k tomu, že systém se chová v určitých situacích jinak, než měl zadavatel původně na mysli. Je proto třeba pozměnit abstraktní model systému a následně i algoritmické řešení a program.

Paradigma induktivního programování je jednodušší (viz obr. 2):

1. Systémový analytik prodiskutuje s uživatelem popis a chování systému v jednotlivých situacích. Komunikace s uživatelem je opět vedena prostředky běžného jazyka a výsledkem je tedy pouze intuitivní popis systému.

2. Je vytvořen program, který požadovaný systém realizuje.

3. Provádí se ověřování programu. Pokud chování programu není v souladu s požadavky uživatele, provede se automatická změna přímo v programu a v ověřování programu se pokračuje.

Vzniká ovšem otázka jakým způsobem automatickou změnu programu provádět. Lze postupovat takto:

Vyhodnotí se odchylka chování systému od požadovaného chování. Odchylka je kvantifikována a vyjádří se funkcinálem W. Tento funkcionál samozřejmě závisí na programu, který systém realizuje. Nabízí se proto myšlenka automatickou změnu programu realizovat ve směru gradientu funcionálu W. To jest vytvářet program, který realizuje požadovaný systém postupně tak, že pomocí gradientní metody najdeme minimum funkcionálu W.

Počítač s Von Neumannovou architekturou

Dnešní universální počítače mají Von Neumannovu architekturu. Počítač pracuje tak, že vstupní data zpracovává programem ve strojovém kódu počítače. Program stanoví postupné provádění základních arimetických a logických operací nad vstupními daty. Výsledkem zpracování vstupních dat jsou výstupní data. Tuto situaci lze symbolicky vyjádřit následovně:

Vstupní_data

Výstupní_ data

Pokud tedy program počítače realizuje určitý systém, vstupní data popisují stav prostředí systému a výstupní data reakci systému na tato vstupní data. Tato reakce musí musí splňovat požadavky uživatele.

Například program počítače realizuje lékařský diagnostický systém, který je schopen na základě vyšetření stanovit diagnosu pacienta.

Předpokládejme, že lze kvantifikovat velikost odchylky odezvy realizovaného systému od požadovaného chování systému. Například v případě lékařského diagnostického systému je požadovaným chováním systému správné stanovení diagnosy a za přirozenou kvantitativní míru odchylky od požadovaného chování systému lze vzít průměrnou chybu stanovení diagnosy.

Vzniká otázka, zda lze v tomto případě pro Von Neumannův počítač použít paradigma induktivního programování. Tj. pro systémy, pro které je možné kvantifikovat odchylku jejich skutečného chování od požadovaného chování, najít program realizující systém pomocí gradientní metody.

Instrukce programu jsou kódovány v počítači binárně. Nabízí se proto například možnost měřit vzdálenost mezi instrukcemi a následně i mezi různými programy Hammingovou metrikou. Změna v jednom bitu instrukce může ale zcela změnit chování programu. Funkcionál W proto nebude vzhledem k této metrice spojitý. Ukazuje se, že metriku, vzhledem ke které by byl funkcionál W spojitý nelze efektivně definovat. Proto programovat Von Neumannův počítač podle induktivního paradigmatu nelze.

Neuronový počítač

Jinak je tomu u počítače s neuronovou architekturou. Neuronový počítač tvoří neuronová síť, tj. množina vzájemně propojených neuronů. Určitý počet neuronů (vstupní neurony, receptory) kóduje vstupní data a určitý počet neuronů kóduje výstupní data (výstupní neurony).

Výstupní data závisí na vstupních datech a na architektuře neuronové sítě, která je dána způsobem vzájemného propojení neuronů a váhami těchto propojení. Váhy jednotlivých propojení charakterisují míru, kterou dané propojení přispívá k excitaci neuronu. Chování neuronového počítače lze proto symbolicky vyjádřit takto:

Vstupní_data

Výstupní_ data

V neuronovém počítači tedy propojení mezi jednotlivými neurony a váhy těchto propojení představují program počítače, který definuje jeho chování.

Program pro neuronový počítač lze stanovit jak podle deduktivního tak i induktivního paradigmatu.

V případě deduktivního paradigmatu je třeba na základě abstraktního modelu stanovit propojení a váhy jednotlivých neuronů. To je v obecném případě obtížnější než pro Von Neumannův počítač. V jednodušších případech se algoritmus vyjádří booleovskou funkcí. Jsou známy metody, které k zadané libovolné booleovské funkci dovolí stanovit propojení a váhy jednotlivých neuronů tak, aby booleovská funkce byla neuronovou sítí realizována.

Pro neuronový počítač lze ale použít i induktivní paradigma. Váhy jsou reálná čísla a vzhledem k vahám je změna výstupních dat neuronového počítače spojitá. Pokud tedy funkcionál W měří odlišnost výstupních dat od požadovaných hodnot, je rovněž W spojitý vzhledem ke změně vah. Proto lze hledat optimální program neuronového počítače gradientní metodou, tj. použít paradigma induktivního programování.

Při použití induktivního paradigmatu se na základě intuitivního popisu systému a jeho chování stanoví pouze základní parametry architektury neuronové sítě, tj. stanoví se typ neuronů, jejich celkový počet, u vrstvených sítí počet skrytých vrstev atd. Váhy se obvykle nastaví na začátku náhodně. Výsledný program neuronového počítače se pak hledá gradientní metodou.

Při náhodném nastavení počátečních vah však může konvergence k reálně použitelným vahám trvat dost dlouho. Vzniká otázka, zda lze na základě intuitivního popisu systému stanovit počáteční váhy efektivněji a urychlit tak konvergenční proces. Obvykle se postupuje tak, že ve fázi počátečního intuitivního popisu systému se ve spolupráci s uživatelem definují některé vlastnosti systému pomocí formulí výrokového počtu. Tyto formule výrokového počtu tvoří teorii popisující požadované chování systému. Pro některé architektury neuronového počítače (např pro vrstvené neuronové sítě) je znám způsob jak stanovit architekturu tak, aby neuronový počítač tyto vztahy respektoval ( Towell(1994), Quah (1996), Setiono (1996), Tan (1996) ). Bohužel dosud se nepodařilo zobecnit tento postup pro formule predikátového počtu.

Z toho, co bylo dosud uvedeno, vyplývá:

Pro programování neuronových počítačů lze použít jak deduktivní tak i induktivní programovací paradigma. Stanovit program podle deduktivního programovacího paradigmatu je pro neuronový počítač podstatně obtížnější než pro klasický Von Neumanův počítač.

Klasické počítače s Von Neumanovou architekturou lze programovat pouze podle deduktivního paradigmatu.

Z hlediska realizovaných systémů je zřejmé, že systémy, jejichž požadované chování lze jednoduchými formálními prostředky přesně definovat, je výhodné realizovat s použitím deduktivního programovacího paradigmatu. Např. systém realizující numerické výpočty, databázový systém atd. Proto se použije klasické Von Neumannovy architektury a běžného deduktivního programovacího paradigmatu.

Naproti tomu systémy, jejichž chování jednoduchými formálními prostředky přesně popsat nelze, je výhodné realizovat pomocí induktivního programovacího paradigmatu. Například systémy pro rozpoznávání obrazů, písma, řeči nebo lékařské diagnostické systémy atd. V tomto případě je tedy třeba použít neuronový počítač. Protože neuronový počítač není obvykle k dispozici, používá se jeho simulace na počítači s klasickou Von Neumannovou architekturou.

V posledních letech byly získány teoretické výsledky, které pro programování neuronového počítače dovolují použít spojení deduktivního a induktivního paradigmatu. Při čistě induktivním přístupu je nutné začít s libovolně zvolenými počátečními vahami. Pokud lze vyjádřit požadované vlastnosti výsledného systému teorií výrokového počtu, byla popsána metoda, jak stanovit počáteční váhy neuronového počítače tak, aby tyto vlastnosti byly na počátku splněny. To vede k podstatně rychlejšímu nalezení výsledného programu (tj. ke zrychlení indukce). Bohužel dosud nebyly získány výsledky, které by umožnily podobným způsobem využít vlastnosti systému definované pomocí teorie predikátového počtu.

Literatura

Partridge D. : The Case for Inductive programming, IEEEComputer, January,1997

Quah T.S., Tan CH.L., Raman K.S., Srinivasan B.(1996) : Towards integrating rule-based expert systems and neural networks, Decision Support Systems, 17 , May 1996, Nu 2, pp. 99-118.

R.Setiono, H.Liu (1996) : Symbolic representation of neural networks, IEEE Computer, March, 1996.

Tan Ch.L., Quah T.S., Teh H.H.(1996) : An artificial neural network that models human decision making, IEEE Computer , March, pp. 64 -70.

Towell G., Shawlik J.W.(1994): Knowledge-based artificial neural networks, Artificial Intelligence, 70 , Nu 1-2, October, pp. 119-165.