Induktīvā
izveduma teorija:
1970-tie gadi
jeb
Algoritmu sintēze pēc piemēriem
jeb
Melnās kastes
atšifrēšana ar eksperimentiem
Kārlis Podnieks, LU prof.
(C) K.Podnieks, 2005
|
Induktīvā
izveduma teorija: jeb Algoritmu sintēze pēc piemēriem jeb Melnās kastes
atšifrēšana ar eksperimentiem Kārlis Podnieks, LU prof. (C) K.Podnieks, 2005 |
-------------------------------------------------Noregulē savas pārlūkprogrammas loga platumu!-------------------------------------- |
Mērķis Šajā pirmajā lekcijā es gribētu aplūkot induktīvā izveduma teorijas visabstraktāko versiju, ko mēs pētījām 1970-to gadu pirmajā pusē. Neļausim pētāmo modeli tuvināt reāliem uzdevumiem vairāk par absolūti nepieciešamo minimumu. Mēģināsim izpētīt pilnīgi visu, kas iespējams tieši šajā abstrakcijas līmenī. Kā šis modelis izskatās no 30 gadu distances? Vai tur nav palikušas kādas neatrisinātas problēmas? |
Vēsture - Platons, 427-347 pmē. Mans vēstures avots: Brian R. Gaines. General System Identification - Fundamentals and Results. In Klir, G.J., Ed. Applied General Systems Research, New York, USA: Plenum Press, 1978, pp. 91-104. Melnās kastes ideja pirmoreiz ir radusies nevis "apakšā" (pie galīgiem automātiem), bet "augšā" - vērtējot cilvēku izziņas procesu kopumā. Pirmās šaubas par to, ka, varbūt, pasaule ir melna kaste, kuras "īsto uzbūvi" mēs nekad neuzzināsim, ir izteiktas Platona līdzībā par alu (the simile of the cave). Vairums cilvēku dzīvo kā cietumnieki, kuri no dzimšanas ir tā pieķēdēti pie alas grīdas, ka var redzēt tikai ēnas (savu paša ēnu ieskaitot), kas kustas uz alas dibensienas. Viņiem liekas, ka šīs ēnas tad arī ir vienīgā īstā pasaule (jo citas nav...). Platonam gan tālāk seko optimistisks turpinājums, bet pēc 2000 gadiem D. Jūms (David Hume, 1711-1776) jau pavisam noteikti saprata, ka mūsu zināšanu atbilstību reālajai pasaulei nekādā absolūtā nozīmē pierādīt nav iespējams. Mūsdienu terminos: pasaule ir melna kaste, ar kuru mēs eksperimentējam, veidojam tās modeļus, ja mūsu rīcība saskaņā ar šiem modeļiem ir sekmīga, tad mēs drīkstam domāt, ka "zinām", kā pasaule uzbūvēta... (bet tikai pēdiņās!) |
Vēsture - Moore, 1956 Edward F. Moore (1925-2003) E. F. Moore. Gedanken experiments on sequential machines. In: C. E. Shannon and J. McCarthy's Automata Studies, Princeton University Press, 1956, pp. 129-153. Šeit pirmo reizi aplūkots uzdevums "atšifrēt" galīgu automātu, novērojot tā reakcijas uz dažādiem ieejas datiem. Tas izrādījās reāli atrisināms uzdevums. Ideja par Tūringa mašīnas "atšifrēšanu" ar eksperimentiem laikam nevarēja uzreiz rasties... |
Vēsture - Zadeh, 1956 Lotfi A. Zadeh - fuzzy logic izgudrotājs, dzimis 1921, Baku. Zadeh, L. A.On the identification problem. IRE Transactions on Circuit Theory, Vol. 3, N 4, pp. 277-281, December 1956, (citēju pēc Gaines apskata [1978]). Problēma - "determining the input-output relationship of a black box by experimental means", given 1) a black box X, whose input-output relationship is not known a priori; 2) the input space of X; 3) a class of models for such black boxes, M, which on the bases of a priori information about X is known to contain a model for it determine, by observing the response of X to various inputs, a member of M which is equivalent to X in the sense that its responses to all time functions in the input space of X are identical to those of X. Zadeh ieteica saukt to par "identification", noraidot citus terminus kā mazāk piemērotus (characterization, measurement, evaluation, gedanken experiments etc.) Zadeh galvenokārt interesēja nepātraukto sistēmu (tehnisko, bioloģisko, ekonomisko) identifikācija. Sistēmu identifikācijas ideju viņš iekļāvis savā "contribution list". |
Vēsture - Chomsky/Miller, 1957 Tikko radusies (Chomsky) kontekst-brīvo valodu teorija iedvesmoja arī mēģinājumus modelēt ar tās palīdzību valodas apgūšanas procesus, kad cilvēkbērnam tiek piedāvāti pareizas un nepareizas runas piemēri, no kuriem viņš neapzināti "izsecina" valodas gramatiku un "izmanto" to, veidojot savu runu. (Modelēt - tas šeit nozīmē izveidot datorprogrammu, kas kaut vai daļēji spēj to pašu.) Termini: grammar discovery vai inference of grammars. Noam Chomsky un George A. Miller N. Chomsky, and G. A. Miller. Pattern Conception. Report AFCRC-TN-57-57, 1957 |
Vēsture - Solomonoff, 1964 1957.gada aprīlī tika uzsākts projekts, kura mērķis bija "to understand the induction process sufficiently well to mechanize it". R. J. Solomonoff. A formal theory of inductive inference. Part I. Information and Control, Vol. 7, N 1, pp. 1-22, March 1964 (available online) R. J. Solomonoff. A formal theory of inductive inference. Part II. Information and Control, Vol. 7, N 2, pp. 224-254, June 1964 (unavailable online) Viņš konsekventi lieto terminu Theory of Inductive Inference. Bet raksta Part I ir runa tikai par varbūtību aprēķiniem: kāda varbūtība, ka ļoti garu simbolu virkni T kā nākošais turpinās simbols b. Solomonoff pretendē uz Kolmogorova un Chaitin sarežgītības jēdziena atklāšanu. Kaut kādā ziņā viņu var uzskatīt par nākošās vērtības prognozēšanas idejas autoru? Chaitin: Solomonoff was not a mathematician. He was interested in artificial intelligence and in the problem of scientific induction, theory building and prediction. His first paper, in two parts in Information & Control, is full of interesting ideas. Unfortunately his math isn't very good and he doesn't really succeed in doing too much with these ideas. Gold [1967]: Another approach which has been proposed (Solomonoff, 1964) uses "identification by enumeration", ... (tas laikam ir jāmeklē Part II, un runa ir par valodas izvēli no rekursīvas numerācijas - tas ir viens no populārajiem paņēmieniem mūsu teorijā). |
Kāda ideja, kas "uz lietu neattiecas"... Solomonoff 1997.gada rakstā lpp.5: ideja, ka elementāros varbūtību sadalījumus ģenerē evolūcija: tie indivīdi, kuri izmanto sliktus sadalījumus, caurmērā atstāj mazāk pēcnācēju. Varbūt, tāpēc t.s. "subjektīvo varbūtību" koncepcija tomēr pilnīgi tukša nav? Bet visam pamatā tomēr paliek notikumu iestāšanās biežumi. |
Vēsture - Gold, 1967 E. Mark Gold? E. M. Gold. Limiting recursion. Journal of Symbolic Logic, Vol. 30, N 1, pp. 28-48, March 1965 E. M. Gold. Language identification in the limit. Information and Control, Vol. 10, pp. 447-474, 1967 (received February 20, 1967) Liekas, viņš pirmais iedrošinājās aplūkot problēmu maksimāli vispārīgā līmenī - būtībā - kā patvaļīgu Tūringa mašīnu atšifrēšanu. Plus ideja par "identifikāciju robežā" (sk. arī Aizerman et al., 1964, http://citeseer.lcs.mit.edu/context/49749/0) Golda publikāciju saraksts. |
E. Mark Gold Award, 1999- Iesākās International Conference on Algorithmic Learning Theory 1999 (ALT'99 ). ALT'05 un pilns prēmēto saraksts. DS'05 un Carl Smith Award |
E. Mark Gold Ko vēl par viņu var uzzināt? [28.10.2005] Kādā ģenealoģijas datu bāzē var izlasīt, ka viņa pilns vārds ir Edward Mark Gold, ka 1964. gadā viņš
ieguvis Viņa vadītājs bija Roderick Ross (savukārt Rossa Ph.D. University of Toronto, 1958, vadītājs bija Abraham Robinson). Tai pašā laikā pie Rossa darbojās vēl trīs doktoranti:
|
E. Mark Gold, turpinājums Viņa tīmekļa vietne: http://www.fungold.com FUNGOLD.com Sevišķi sk.: http://www.fungold.com/5d3m1y_Asia.htm unCopyrighted by E Mark Gold -- Steal me! Sell me!Sieva: Noella Reid GOLD: noella@fungold.com, viņas aizraušanās ir savas ģenealoģijas
pētīšana. http://www.fungold.com/Noella/geneal.htm - te ir Noellas (bet ne Marka) bilde. http://www.fungold.com/Noella/Popmom.htm - saskaņā ar šo, bērnu viņiem, liekas, nav. Bet 2004.gada 25. novembrī ... |
Problēma, ar kuru iesākām mēs... Kā cilvēki iemācās algoritmus? Vairums cilvēku pašus algoritmus nemaz neiemācās, viņi iemācās algoritmus izpildīt. Pašus algoritmus spiesti iemācīties tikai programmētāji. Piemērs: veselu skaitļu saskaitīšanas apmācība, izmantojot algoritma darbības piemērus (nevis aprakstot algoritmu vispārīgā veidā): 175 a1a2a3
... an-1an Vispārīgā veidā šo algoritmu vajadzētu zināt tikai programmētājam, kurš vēlas realizēt programmu, kas prot saskaitīt, piemēram, 1000-zīmīgus skaitļus. |
Modelis Modelējam: cilvēka vietā liekam datoru. Kā dators varētu apgūt kādu algoritmu, ja tam būtu pieejami tikai šī algoritma darbības piemēri? Kas ir algoritms? Tūringa mašīnas programma? Galīgs automāts? Programma kādā specifiskā valodā? Visabstraktākais modelis - Tūringa mašīnu programmas. Ko algoritms dara? Abstrakts modelis: zinot x, izrēķina f(x) (x - naturāls skaitlis, f(x) - arī, t.i. f - visur definēta rekursīva funkcija N->N). Citi varianti? Kas ir algoritma darbības piemēri?
Visabstraktākais modelis - ir pieejami tikai pāri: T.i. šeit tiek doti tikai algoritma darbības rezultāti, pats darbības process parādīts netiek. Vēl var būt noderīgi papildus ierobežojumi (constraints), ko var izmantot meklējot "īsto" programmu: ir labi, ja iepriekš zināms, ka funkcija f pieder kādai specifiskai funkciju klasei (piemēram, ir zināms, ka tā ir polinoms). Labs modelis vai sliktas matemātikas paraugs? |
Modelis (turpinājums) Kas tad ir "tas", kam tiks uzdots meklēt programmu, kas rēķina funkciju f, izmantojot informāciju par šīs funkcijas vērtībām: <0, f(0)>, <1, f(1)>, <2, f(2)>, ... , <n, f(n)>, ...? "Tas", protams, ir algoritms, un "to" toreiz bija pieņemts saukt par stratēģiju ("to" daži sauc par learner - mācekli, citi - par IIM - Inductive Inference Machine). Oficiālā definīcija paredz, ka stratēģija S saņem pēc kārtas funkcijas vērtības f(0), f(1), ..., f(n), ... un pēc katras jaunas vērtības saņemšanas cenšas sintezēt programmu, kas rēķina funkciju f. Rezultātā rodas hipotēžu virkne S(<f(0)>) - tā ir programma-hipotēze, kas rēķina funkciju f vai kādu citu funkciju, S(<f(0), f(1)>) - tāpat, S(<f(0), f(1), f(2))- tāpat, ... S(<f(0), f(1), ..., f(n)>), ... Tātad, tīri tehniski, stratēģija S ir algoritms, kas saņemot jebkuru galīgu skaitļu virkni <b0, b1, ..., bn> , vai nu ģenerē no tās kādu hipotēzi (programmu) S(<b0, b1, ..., bn>), vai arī strādā līdz bezgalībai (tad sakām, ka hipotēze nav definēta). Funkcijai f hipotēzi S(<f(0), f(1), ..., f(n)>) sauc par pareizu, ja tā ir definēta un (kā programma) katram x izrēķina f(x). Citādi šo hipotēzi sauc par kļūdainu. Stratēģija S sintezē (izved, identificē) funkciju f, ja hipotēžu virkne S(<f(0)>), S(<f(0), f(1)>), ..., S(<f(0), f(1), ..., f(n)>), ... konverģē (stabilizējas) uz pareizu hipotēzi, t.i. sākot ar kādu n=n0, S(<f(0), f(1), ..., f(n)>)=p0, kur p0 ir programma, kas visiem x izrēķina f(x) (Gold [1967]). Labs modelis vai sliktas matemātikas paraugs? Un tomēr, šajā lekcijā mēs stingri turēsimies pie šī ļoti augstā abstrakcijas līmeņa, neļaujot modeli tuvināt reāliem uzdevumiem. Mēģināsim izpētīt pilnīgi visu, kas iespējams tieši šajā līmenī. 04/02/2005 K.Freivalds: Definīcija liktos dabiskāka, ja tajā būtu tikai prasība par hipotēžu pareizību, sākot ar kādu brīdi, bet ne prasība par hipotēžu stabilizāciju. [Tā tad būtu definīcija GN00, sk. tālāk.] |
Starp citu... Vai ir dabiski, ka funkcijas vērtības f(0), f(1), ..., f(n), ... tiek padotas stratēģijai tieši šadā secībā? Vai pāri <x, f(x)> nevarētu pienākt patvaļīgā - arī nerekursīvā - secībā? Vai arī - tieši otrādi - stratēģija varētu pati pēc savas izvēles uzdot jautājumus "f(x)=?", un mēs uz tiem atbildētu? Gold [1967], Theorem I.3 - tur jau pašā sākumā pārbaudīts, ka mūsu pieņemtajā abstrakcijas līmenī ir vienalga, kuru no variantiem aplūkot (svarīgi tikai, lai stratēģijai būtu pieejamas visas funkcijas vērtības). |
Pirmās teorēmas Teorēma 1 (Gold [1967], Theorem I.5). Neviena stratēģija nespēj sintezēt visas visur definētās rekursīvās funkcijas, kam ir tikai vērtības 0, 1 [pat definīcijā GN00, sk. tālāk]. Vispirms pierādīsim šādu lemmu: Lemma 1. Ja stratēģija S spēj sintezēt visas gandrīz 0-konstantās funkcijas b0, b1, ..., bn, 0, 0, 0, ..., tad katrai galīgai virknei <b0, b1, ..., bn> var atrast tādu skaitli m, ka saņemot virkni <b0, b1, ..., bn, 0, 0, ..., 0> (m nulles), S izdos kā hipotēzi tādas funkcijas h programmu, kam h(n+m+1)=0. Pierādījums. Liekam stratēģijai S paralēli visiem m ģenerēt hipotēzes S(<b0, b1, ..., bn, 0, 0, ..., 0>) (m nulles), katrai uzģenerētajai hipotēzei h paralēli liekam rēķināt funkcijas vērtību h(n+m+1). Ja stratēģija S spēj sintezēt visas gandrīz 0-konstantās funkcijas, tad mēs noteikti sagaidīsim tādu m un tādu h, ka h(n+m+1)=0. Tiešām, ja tā nenotiks, tad S nespēs sintezēt funkciju b0, b1, ..., bn, 0, 0, ..., 0, .... Q.E.D. Tagad iterēsim lemmu 1, iegūstot otru lemmu. Lemma 1A. Eksistē algoritms, kas katrai stratēģijai S, kura spēj sintezēt visas gandrīz 0-konstantās funkcijas b0, b1, ..., bn, 0, 0, 0, ..., uzbūvē visur definētu rekursīvu funkciju f, kam ir tikai vērtības 0, 1, un kuras sintēzes procesā S bezgalīgi daudz reižu izdod kļūdainas hipotēzes. Pierādījums. Ja funkcijas f vērtības f(0), ..., f(n) jau ir nodefinētas, tad turpināsim ar lemmu 1: atradīsim tādu m, ka saņemot virkni <f(0), ..., f(n), 0, 0, ..., 0> (m nulles), S izdos kā hipotēzi tādas funkcijas h programmu, kam h(n+m+1)=0. Funkciju f tad definēsim tālāk šādi: f(n+1)=0, ..., f(n+m)=0, f(n+m+1)=1. Tad stratēģijas hipotēze h būs kļūdaina. Iterējot šos soļus, iegūstam visur definētu rekursīvu funkciju f, kurai stratēģija S bezgalīgi daudz reižu ģenerē kļūdainas hipotēzes. Q.E.D. Teorēmas 1 pierādījums. Vai nu stratēģija S, nespēj sintezēt visas gandrīz 0-konstantās funkcijas, vai arī tai var uzbūvēt visur definētu rekursīvu funkciju f, kam ir tikai vērtības 0, 1, un kuras sintēzes procesā S bezgalīgi daudz reižu izdod kļūdainas hipotēzes. Q.E.D. |
Starp citu... Lemmu 1A var viegli pastiprināt: Lemma 1X. Eksistē algoritms, kas katrai stratēģijai S, kura spēj sintezēt visas funkcijas kādā "vāji blīvā" rekursīvi sanumurējamā visur definētu funkciju klasē, uzbūvē visur definētu rekursīvu funkciju f, kam ir tikai vērtības 0, 1, un kuras sintēzes procesā S bezgalīgi daudz reižu izdod kļūdainas hipotēzes. "Blīva" klase U: katrai virknei <b0, b1, ..., bn> eksistē funkcija f no U, kas pie x<=n dod vērtības b0, b1, ..., bn. "Vāji blīva" klase U: katrai funkcijai f no U un katram n eksistē cita funkcija g no U, kas pie x<=n sakrīt ar f. (Cita - tas nozīmē, ka f<>g.) |
Pirmās teorēmas (turpinājums I) Rekursīvi sanumurējama visur definētu funkciju klase rodas no rekursīvas visur definētas divu argumentu funkcijas g(i, x). Numerācijas i-tā funkcija: gi(x) = g(i, x). Vizuāli tā ir uz divām pusēm bezgalīga matrica: g0: g(0, 0), g(0, 1), g(0,
2), ... Teorēma 2 (Gold [1967], Theorem I.6, I.7). Katrai rekursīvi sanumurējamai visur definētu funkciju klasei U eksistē stratēģija, kas sintezē visas U funkcijas [un kam visas hipotēzes ir definētas] [un kas vienmēr izdod kā hipotēzes tikai visur definētu funkciju programmas] [un kam visas hipotēzes ir "konsistentas"]. Pierādījums. Saņemot vērtību virkni f(0), f(1), ..., f(n), mēs jau iepriekš zinām, ka kādam i tā ir virkne gi(0), gi(1), ..., gi(n). Ja atrodam pirmo tādu i<=n, tad to arī izdodam kā hipotēzi S(<f(0), f(1), ..., f(n)>) (ja neatrodam, tad izdodam kā hipotēzi funkcijas f(0), f(1), ..., f(n), 0, 0, ... programmu). Šī stratēģija sintezē jebkuru klases U funkciju - tās hipotēžu virkne ir nedilstoša un stabilizējas uz vismazāko i tādu, ka f=gi. Q.E.D. Piezīme. Pieļaujot daļēji definētu funkciju numerācijas, teorēmas 2 analogu pierādīt nav iespējams (jo eksistē visu daļēji definēto rekursīvo funkciju numerācija). "Konsistenta" hipotēze - programma S(<f(0), f(1), ..., f(n)>), kas katram x<=n pareizi izrēķina f(x). |
Pirmās teorēmas (turpinājums I) Teorēma 3 (Bārzdiņš, 1972). Eksistē sintezējama [definīcija GN] funkciju klase, kas nav nevienas rekursīvi sanumurējamas visur definētu funkciju klases apakškopa. Pierādījums.
Aplūkosim šādu funkciju klasi V. Šīs klases
funkcijas f iegūst no visām iespējamām visur
definētām rekursīvām funkcijām g šādā veidā: ja
pg ir kods jebkurai programmai, kas rēķina
funkciju g, tad f vērtību virkne ir: 1) Klasi V sintezē ļoti vienkārša stratēģija: saņemot f(0), t.i. funkcijas g programmu pg, no tās izveido funkcijas f programmu, kas ir pareiza jau pēc pirmā mēģinājuma. 2) Klase V neietilpst nevienā rekursīvi sanumurējamā visur definētu funkciju klasē. Tiešām, katrai visur definētu funkciju numerācijai t(n, x) definējam g(n) = t(n, n+1)+1. Tad g atbilstošā funkcija f numerācijā t(n, x) nebūs atrodama. Q.E.D. Ko nozīmē "definīcija GN"? Ar GN tiek apzīmēta visur definētu rekursīvu funkciju klašu kopa. Katrai klasei no kopas GN eksistē stratēģija, kas sintezē visas šīs klases funkcijas. Citiem vārdiem: klase U pieder GN, ttt, ja eksistē stratēģija, kas sintezē visas šīs klases funkcijas. Kāpēc GN? GN - "Gēdela numuri" - tā laika modes lieta. 19/09/2005 Vēlāk GN-sintēzi sāka saukt par EX-identifikāciju vai EX-learning (EX nozīmē "explanes", "program explanes its output data"). Šo terminu ieveda 1983.gadā: J. Case, C. Smith. Comparison of Identification Criteria for Machine Inductive Inference. Theoretical Computer Science, 25 (1983), pp. 193-220 |
Pirmās teorēmas (turpinājums II) Teorēma 3A ("jauna"? Nē! Sk. zemāk.). Ja stratēģija vienmēr izdod kā hipotēzes tikai visur definētu funkciju programmas, tad visu šīs stratēģijas sintezēto funkciju kopa ir rekursīvi sanumurējamas visur definētu funkciju klases apakškopa. Pierādījums. Stratēģijai S veidojam numerāciju. Paralēli darbinām S uz visām iepējamām vērtību virknēm <b0, b1, ..., bn>, tiklīdz tā izdod kādu hipotēzi, t.i. visur definētas funkcijas programmu, tā liekam šo funkciju mūsu veidojamā numerācijā kā nākošo. Aiz tās ieliekam konstanto funkciju 0. Q.E.D. Jautājumi. Kāpēc šo triviālo faktu nemin 1970-gadu raksti? Vai stratēģijai, kas tiecas sintezēt visur definētas funkcijas, ir "tiesības" izdot kā hipotēzes daļēji definētu funkciju programmas? Sekas: šajā ierobežotajā definīcijā, a) sintezējamu klašu apvienojums ir sintezējams, b) sintezējamas klases papildinājums nav sintezējams. 04/02/2005 R. Freivalds: Šīs definīcijas trūkums ir prasība, lai stratēģija izdotu kā hipotēzes visur definētu funkciju numurus arī tad, ja tā nemaz netaisās tai padoto funkciju sintezēt. 06/02/2005 K. Podnieks: Šis iebildums attiecas tikai uz "neblīvām" funkciju klasēm, t.i. tādām, kuru funkciju sākuma segmenti nedod visas iespējamās galīgās skaitļu virknes. 19/09/2005 Izrādās, ka teorēma 3A pierādīta minētajā Case & Smith [1983] rakstā un tur izdarīts arī secinājums, ka "mašīnas", kuru hipotēzes ir tikai visur definētas funkcijas (PEX-learning, P - Popperian), ir vājākas par "mašīnām", kurām kā hipotēzes atļautas arī daļēji definētas funkcijas (EX-learning). Problēmas? Kā sintēzes iespējas ietekmē pārējās divas prasības: a) visām hipotēzēm jābūt definētām, b) visām hipotēzēm jābūt "konsistentām"? Tie neliekas grūti jautājumi... |
Pirmās teorēmas (turpinājums III) Teorēma 4 (Bārzdiņš, 1972). Eksistē divas sintezējamas funkciju klases [definīcijā GN un pat NV', sk. tālāk], kuru apvienojums nav sintezējams [pat plašākajā definīcijā GN00, sk. tālāk]. Pierādījums. Klasi V ņemam no teorēmas 3 pierādījuma, klase V' = visas "gandrīz 0-konstantās" funkcijas (t.i. visas virknes b0, b1, ..., bn, 0, 0, 0, ...). Klase V' ir rekursīvi sanumurējama. Apvienojums VUV' nav sintezējams. Jāizmanto nekustīgā punkta teorēma... Pieņemsim, ka mums ir stratēģija S, kas sintezē jebkuru gandrīz 0-konstantu funkciju. Katram naturālam skaitlim i definējam šādu funkciju fi. Vispirms, fi(0)=i. Tālāk, paralēli darbinām S uz visām galīgām virknēm <i, 0, 0, ..., 0> (n-1 nulles), un tiklīdz S izdod hipotēzi h tādu, ka h(n+1)=0, tad definējam fi(x)=0, ja 1<=x<=n, un fi(n+1)=1. Tādā veidā hipotēze h noteikti būs kļūdaina. No šī brīža procesu turpinām, tikai tagad liekam stratēģijai S paralēli ģenerēt visas iespējamās hipotēzes S(<fi(0), ..., fi(n+1), 0, 0, ..., 0>) utt. Ja S tiešām sintezē visas gandrīz 0-konstantās funkcijas, tad, iterējot šos soļus, mēs iegūstam visur definētu rekursīvu funkciju fi, kurai stratēģija S bezgalīgi daudz reižu ģenerē kļūdainas hipotēzes. Tagad paņemsim funkciju gi(x)=fi(x+1) un pielietosim nekustīgā punkta teorēmu, iegūstot tādu i0, kas ir funkcijas gi0 programma. Tad atbilstošā funkcija fi0 pieder klasei V (jo fi0(0)=i0, t.i. turpinājuma funkcijas gii0 programma). Bet šai funkcijai stratēģija S bezgalīgi daudz reižu ģenerē kļūdainas hipotēzes. Pretruna. Q.E.D. Nekustīgā punkta teorēma. Ja mums ir algoritms, ka katram naturālam skaitlim i ģenerē kādu funkciju gi, tad eksistē tāds i0, kas ir atbilstošās funkcijas gi0 programma. Piezīme. V' vietā var izmantot jebkuru blīvu rekursīvi sanumurējamu visur definētu funkciju klasi, kurai ikviena funkcija f pieder vai nepieder neatkarīgi no vērtības f(0). Var iztikt arī ar funkcijām, kuru vērtības ir tikai 0, 1. Cik tālu to vēl var pastiprināt? |
Problēma 1? Kā redzams no teorēmas 4 pierādījuma, stratēģijas, kas sintezē klases V funkcijas, nespēj sintezēt visas gandrīz 0-konstantās funkcijas. Vai tās ir "pilnvērtīgas" stratēģijas? "Gandrīz konstanta" funkcija f: sākot ar kādu x=x0, f(x)=c. Ja mēs aplūkotu tikai "pilnvērtīgas" stratēģijas, t.i. tikai tās, kuras spēj sintezēt visas gandrīz konstantās funkcijas, kā tad mainītos mūsu teorija? Vai tad: a) būtu sintezējamas tikai rekursīvi sanumurējamas visur definētu funkciju klašu apakškopas? b) sintezējamo klašu kopa būtu slēgta pret apvienojumiem? 04/02/2005 K. Čerāns: Ja 3 funkciju klases A, B, C ir tādas, ka apvienojumi AUB, AUC un BUC ir sintezējami, vai tad būs sintezējams arī apvienojums AUBUC? J. Vīksna: Būs sintezējams, jo var noorganizēt 3 minēto stratēģiju "balsošanu". Publika: Vai šo ideju var novest līdz precīzam pierādījumam? 07-09/06/2007 Senigallijā (Itālija), MolPAGE projekta mītiņā. Sk. foto. 1) Juris Vīksna ātri atrada negatīvu atbildi Problēmai 1a: eksistē sintezējama funkciju klase, kas satur visas gandrīz konstantās funkcijas un kas nav nevienas rekursīvi sanumurējamas visur definētu funkciju klases apakškopa. Pierādījums. Klasi U definējam šādi: tajā ietilpst visas gandrīz konstantās funkcijas, kā arī tās funkcijas no klases n (010 | 101)00, kam n ir turpinājuma Gēdela numurs. Te svarīgi ir tas, ka otrā veida funkcijas ir viegli atšķiramas no pirmā veida funkcijām. Klasi U sintezē šāda stratēģija. Ja pēdējās 3 saņemtās funkcijas f vērtības ir vienādas (piemēram, ar c), tad uzskatām, ka arī tālāk sekos tikai vērtība c un tādu arī izdodam hipotēzi. Pretējā gadījumā uzskatām, ka f(0) ir turpinājuma Gēdela numurs un no tā tad arī atvasinām f Gēdela numuru. Q.E.D. 2) Nākošais uzdevums: vai visu to visur definēto funkciju klase U, kam viena no vērtībām ir tās Gēdela numurs, ir sintezējama? Arī uz šo jautājumu Juris ātri atrada negatīvu atbildi. Ņemam visu to funkciju f klasi V, kam f(2n)=n visiem n. Skaidrs, ka V ir U apakšklase, kā arī tas, ka jebkurai stratēģijai S funkcijas vērtības f(2n+1) mēs varam izvēlēties tā, ka S šo funkciju nesintezēs. 3) Vēl viens uzdevums Problēmas 1 stilā. Sauksim funkciju klasi U par "galīgi slēgtu", ja reizē ar katru funkciju f tā satur arī visas tās funkcijas g, kam g(x) atšķiras no f (x) ne vairāk kā galīgam skaitam x-u. Skaidrs, ka katra rekursīvi sanumurējama visur definētu funkciju klase ir "galīgi slēgtas" rekursīvi sanumurējamas visur definētu funkciju klases apakškopa. Vai eksistē "galīgi slēgta" sintezējama klase, kas nav nevienas rekursīvi sanumurējamas visur definētu funkciju klases apakškopa? [Šo sintēzes veidu man gribējās nosaukt par "robusto" sintēzi, bet šis termins jau ir aizņemts, sk. tālāk.] Arī uz šo jautājumu Juris ātri atrada atbildi: eksistē. Tiešām, aplūkosim visu to funkciju f klasi U0, kam vērtības f(2n), sākot ar kādu n, ir konstantas un vienādas ar kādu f Gēdela numuru. Vērtības f(2n+1) netiek ierobežotas. Skaidrs, ka U0 ir "galīgi slēgta". Sintezējošā stratēģija vienkārši izdod kā hipotēzi pēdējo saņemto f(2n) vērtību. Pierādījums, ka U0 nav nevienas rekursīvi sanumurējamas visur definētu funkciju klases apakškopa, ir analoģisks pārējiem tādiem pierādījumiem: Lemma. Ja eksistē rekursīvs 1:1 operators, kas katru vispārīgi rekursīvu funkciju pārveido par klases U funkciju, tad U nav nevienas rekursīvi sanumurējamas visur definētu funkciju klases apakškopa. Lemmas pierādījums. Kā domā kolēģi? Konkrētajā klases U0 gadījumā vajadzīgais rekursīvais operators ir šāds. Ņemam patvaļīgu vispārīgi rekursīvu funkciju g, un naturālu skaitli i, un taisām šādu funkciju fi: f(2n)=i, f(2n+1)=g(n) visiem n. Tad pielietojam nekustīgā punkta teorēmu un atrodam i0 tādu, ka i0 ir funkcijas fi0 Gēdela numurs. Tad fi0 arī būs rekursīvā operatora rezultāts. Skaidrs, ka operators ir 1:1 un ka fi0 vienmer pieder klases U0. Q.E.D. Līdz ar to visi mani neatrisināto problēmu meklējumi "pagājušos laikos" ir beigušies neveiksmīgi. Zemāk minētie robust learning pētījumi (Bārzdiņa hipotēze un Mark Fulk rezultāts) ir daudz nopietnāks mēginājums šajā virzienā. |
19/09/2005 Kaut kādā ziņā "pieeja no citas puses" Problēmai 1 varētu būt: Barzdins' Conjecture 1997.gada pārskata rakstā W. Gasarch, C. Smith. A Survey of Inductive Inference with an Emphasis on Queries. In A. Sorbi, editor, Complexity, Logic, and Recursion Theory, number 187 in Lecture notes in Pure and Applied Mathematics Series, M. Dekker, 1997 (var dabūt no http://citeseer.ist.psu.edu/gasarch97survey.html) kā 1980.gadā izteikta private communication minēta Barzdins' Conjecture, saskaņā ar kuru (tā raksta pārskata autori), Teorēmu 2 un 3 pierādījumos izmantotās metodes "ir vienīgās iespējamās induktīvā izveduma metodes" (pirmā - rekursīvi sanumurējamu funkciju klašu sintēze, otrā - self-referencing, t.i. funkcijas vērtībās iekodētas programmas izmantošana). Šīs hipotēzes formalizācija minēta kā netriviāls uzdevums. (Laikam) vēlāk tika ieteikta šādas formalizēta hipotēzes versija. Sauksim funkciju klasi U par robusti sintezējamu, ja pielietojot jebkuru rekursīvu operatoru, U pārveidojas par sintezējamu klasi. Formalizētā Bārzdiņa hipotēze: robusti sintezējamas ir tikai rekursīvi sanumurējamu funkciju klašu apakškopas. (Ideja: rekursīvs operators var iznīcināt funkcijas vērtībās iekodēto programmu.) Šādā formā šo hipotēzi 1990.gadā izdevās apgāzt: M. Fulk. Robust separations in inductive inference. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS), pages 405-410, St. Louis, Missouri, 1990. Ideja: iekodēt funkcijas programmu nevis tās vērtībās, bet klases "topoloģijā". Tādā veidā izdodas iegūt robusti sintezējamu klasi, kas nav nevienas rekursīvi sanumurējamas klases apakškopa. Par Mark
Fulk sk. http://www.ifip.org/minutes/C99/C99_TC1.htm Pārskatu par robust learning sk. 2001. gada rakstā: http://citeseer.ist.psu.edu/323043.html |
Konkurenti Teorēmu 4 gandrīz vienlaicīgi un neatkarīgi pierādīja arī: Jerome A. Feldman. Some decidability results on grammatical inference and complexity. Information and Control, 1972, vol. 20, pp. 244-262 (valodu identifikācijai šis pierādījums ir daudz vieglāks) Lenore Blum, Manuel Blum. Inductive Inference: A Recursion Theoretic Approach. FOCS, 1973, pp. 200-208 Lenore Blum, Manuel Blum. Toward a Mathematical Theory of Inductive Inference, Information and Control, 1975, vol. 28, N2, pp. 125-155 Matemātiķu biogrāfiju indeksā ir tikai Lenore! Bildes: tad un tagad. Manuelam - 60, viņa publikācijas, ievēlēts akadēmijā. |
Funkciju prognozēšana Kad radusies šī ideja? Ideju varētu piedēvēt R. Solomonoff [1964], bet īsti matemātiski rezultāti parādās tikai pašā pirmajā latviešu rakstā par induktīvā izveduma teoriju: J. M. Barzdin. Prognostication of automata and functions. Information Processing 71, B. Gilchrist, Ed. Elsevier North-Holland, New York, 1972, pp. 81-84 Prof. Bārzdiņš varētu pastāstīt, kā tas notika, kāds tajā dienā bija laiks? Prognozēšana ir programmu sintēzei it kā tikai attāli līdzīgs uzdevums: prognozēšanas stratēģija S saņem funkcijas f sākuma nogriezni <f(0), f(1), ..., f(n)> un cenšas uzminēt vērtību f(n+1). Ja S(<f(0), f(1), ..., f(n)>)<>f(n+1), tad mēs sakām, ka S kļūdās. Teiksim, ka S prognozē f, ja, sākot ar kādu n vērtību n0, visas S prognozes ir pareizas, t.i. ja n>=n0, tad S(<f(0), f(1), ..., f(n)>)=f(n+1). Te var uzdot tos pašus jautājumus, ko sintēzes gadījumā, un saņemt ļoti līdzīgas atbildes. Teorēma 1P. Neviena stratēģija nespēj prognozēt visas visur definētās rekursīvās funkcijas, kam ir tikai vērtības 0, 1 [pat visplašākajā definīcijā NV'']. Teorēma 2P. Katrai rekursīvi sanumurējamai visur definētu funkciju klasei U eksistē stratēģija, kas prognozē visas U funkcijas [un kurai visas prognozes ir definētas, definīcija NV]. Pierādījumi ir identiski sintēzes gadījumam. |
Prognozēšanas 3 modeļi Tāpat kā pie sintēzes, arī šeit it kā niecīgas nianses stipri ietekmē situāciju. NV (Bārzdiņš, 1971) Prasām, lai prognozes S(<f(0), f(1), ..., f(n)>) vienmēr ir definētas. T.i. mēs negribam nevienu prognozi gaidīt bezgalīgi ilgi. NV' (Bārzdiņš, 1971) Prasām, lai prognozes S(<f(0), f(1), ..., f(n)>) ir definētas visiem n, ja S prognozē funkciju f. T.i., tikai tajā funkciju klasē, par ko interesējamies, mēs negribam prognozi gaidīt bezgalīgi ilgi. NV'' (Podnieks, 1974) Neprasām neko. Pagaidām skaidrs, ka NV <= NV' <= NV''. |
Pirmās teorēmas (P) Teorēma 3P (Bārzdiņš, 1971). Ja stratēģijas prognozes ir vienmēr definētas (definīcija NV), tad visu šīs stratēģijas prognozēto funkciju kopa ir rekursīvi sanumurējamas visur definētu funkciju klases apakškopa. Pierādījums. Stratēģijai S veidojam numerāciju. Sanumurējam visas iespējamās vērtību virknes <b0, b1, ..., bn>, un i-jai virknei definējam šādu funkciju gi: gi(0)=b0, ..., gi(n)=bn, gi(n+1)=stratēģijas S prognoze, gi(n+2)=stratēģijas S nākošā prognoze, utt. Ja S prognozē kādu funkciju f, tad tā atrodas šajā numerācijā. Q.E.D. Secinājums. Saskaņā ar definīciju NV ir prognozējamas rekursīvi sanumurējamu visur definētu funkciju klašu apakškopas, un tikai tās. |
Pirmās teorēmas (P, turpinājums I) Teorēma 4P (Bārzdiņš, 1971). Eksistē funkciju klase, kas ir prognozējama saskaņā ar definīciju NV', bet kas neietilpst nevienā rekursīvi sanumurējamā visur definētu funkciju klasē [tātad NV < NV']. Pierādījums. Ņemam funkciju klasi V no teorēmas 3 pierādījuma. Teorēma 5P. Eksistē funkciju klase, kas ir prognozējama saskaņā ar definīciju NV', bet nav prognozējama saskaņā ar definīciju NV''. Pierādījums - seko no citām teorēmām, sk. tālāk. Secinājums. NV < NV'< NV''. |
Kāds sakars prognozēšanai ar sintēzi? Teorēma 5X (Podnieks, 1974). Ja funkciju klase ir prognozējama saskaņā ar definīciju NV', tad tā ir sintezējama saskaņā ar definīciju GN. Bet ne otrādi. [Tātad NV'< GN] Pierādījums. Pozitīvā daļa ir viegla - pamēģināsim... Negatīvās daļas pierādījumā izmantota arī viena M. Augustona ideja. Mēģinot salīdzināt NV'' prognozēšanu ar sintēzi, nonākam pie jauna, plašāka (un nedaudz dīvaina?) sintēzes jēdziena, kur netiek prasīta hipotēžu stabilizācija, bet tikai to pareizība, sākot ar kādu brīdi: GN00 (Podnieks, 1974) Teiksim, ka stratēģija S sintezē funkciju f, ja, sākot ar kādu n=n0, S(<f(0), f(1), ..., f(n)>)=pn, kur pn ir jebkura programma, kas visiem x izrēķina f(x). Teorēma 6X (Podnieks, 1974). Funkciju klase ir prognozējama saskaņā ar definīciju NV'', tad un tikai tad, ja tā ir sintezējama saskaņā ar definīciju GN00. [NV''=GN00] Pierādījums nav grūts (varam pamēģināt...). Secinājumi. 1) Arī pēc definīcijas GN00 neviena stratēģija nespēj sintezēt visas visur definētās rekursīvās funkcijas. Sk. teorēmas 1 (Gold, 1967) pierādījumu. 2) GN00 nav slēgta pret apvienojumiem. Sk. teorēmas 4 (Bārzdiņš, 1974) pierādījumu: klase V pieder GN (un pat NV'), V' ir rekursīvi sanumurējama, bet VUV' īstenībā nepieder pat GNoo. 3) GN<GN00 (Bārzdiņš, 1974). Pierādījums ir ne-triviāls (diagonāl-konstrukcija). 19/09/2005 Minētajā Case & Smith [1983] rakstā definīcija GN00 ir nosaukta par BC-identification vai BC-learning (BC - Behaviorally Correct), motivējot, ka tā ir semantikas mācīšanās ("we care only about what the program does"), nemeklējot vienotu fiksētu sintaksi. Sintakse ir EX-learning mērķis ("we care about what the program is"). |
Labāka terminoloģija? Tagad, atskatoties, liekas, ka adekvātāki būtu šādi apzīmējumi: 1) SN - sintēzes stratēģijai jāstabilizējas uz vienu pareizu hipotēzi. Kā hipotēzes tai ir atļautas tikai visur definētu funkciju programmas. 2) SN' - sintēzes stratēģijai jāstabilizējas uz vienu pareizu hipotēzi. Kā hipotēzes ir atļautas arī daļēji definētu funkciju programmas. 3) SN'' - sintēzes stratēģijai nav obligāti jāstabilizējas uz vienu hipotēzi, bet ar laiku visām hipotēzēm jābūt pareizām. Kā hipotēzes ir atļautas arī daļēji definētu funkciju programmas. Teorēma (kopsavilkums). Šajos mainītajos apzīmējumos: 1) SN=NV<NV'<SN'<SN''=NV''. 2) Ja ņemam funkciju klasi no SN=NV un funkciju klasi no NV', tad apvienojums var nepiederēt pat SN''=NV''. Piezīme. Kā ar 1 & 3 kombināciju - tikai visur definētas hipotēzes, bet bez stabilizācijas prasības? Sk. teorēmu 3A - tad sintezējamas ir tikai rekursīvi sanumurējamu visur definētu funkciju klašu apakškopas, t.i. sanāk tas pats, kas definīcijā NV. |
Problēma? Kāpēc mēs esam "piesējušies" vērtības f(n+1) prognozēšanai? Vai tā ir vienīgā iespējamā definīcija? Vai nevarētu mēģināt labāk prognozēt f(n+2), vai f(n+10) un f(n+11)? Citiem vārdiem - prasīt, lai, sākot ar kādu n, zinot <f(0), ..., f(n)> mums pareizi jāprognozē jebkura vērtība f(n+k), kur k pieder kādai galīgai vai bezgalīgai kopai K (tā būtu "K-prognozēšana", mūsu izpētītās {1}-prognozēšanas vietā)? Vai tādā veidā rodas kaut kas jauns, vai arī viss reducējas uz jau izpētītājām definīcijām? Man liekas, ka nekas jauns te nerodas... Pamēģiniet paši. |
Problēma 2? Vai ir tiesa, ka ja kāda funkciju klase ir sintezējama vai prognozējama (jebkurā no definīcijām) tad šīs klases papildinājums tāds nav (nav sintezējams pat definīcijā GN00)? Definīcijai NV to laikam varētu vieglāk pierādīt, jo rekursīvi sanumurējamas visur definētu funkciju klases papildinājums noteikti ir "ļoti grūti" sintezējams/prognozējams? Un kā ar pārējām definīcijām? |
Vēl viena attīstības iespēja - pēdējā? Vai ir iespējami vēl kādi šīs teorijas attīstības virzieni, paliekot tai pašā augstajā abstrakcijas līmenī? Visas līdz šim aplūkotās sintēzes un prognozēšanas definīcijas "darbojas" uz visas naturālo skaitļu virknes: 0, 1, 2, ..., n, ... Saņemot funkcijas vērtības <f(0), f(1), ..., f(n)>, mums jāmēģina uzminēt vai nu f(n+1), vai funkcijas f programmu. Bet, ja (sk. Freivalds [1974]) visu skaitļu virknes vietā mēs aplūkotu patvaļīgu virkni W = {x0, x1, ..., xn, ...} un saņemot <f(x0), f(x1), ..., f(xn)>, mēģinātu uzminēt f(xn+1) vai tādas funkcijas f1 programmu, kas uz virknes W neatšķiras no f? Kāda te ir motivācija? Principā te katrai no aplūkotajām sintēzes un prognozēšanas definīcijām var piekārtot vēl 3 analogus: s) Stratēģijai jātiek galā ar jebkuru virkni W. ss) Stratēģijai jātiek galā ar jebkuru virkni W, kurā ir bezgalīgi daudz naturālu skaitļu. sss) Katrai virknei W atļauts izmantot savu stratēģiju (bet visām funkcijām vienu!). Piemēram, aplūkosim GN
versijas: Teorēma (Freivalds [1974]). GNs < GNss < GNsss < GN. Pierādījums. Viegli pierādīt ir tikai pēdējo nevienādību (pamēģiniet paši...). Tādas pat teorēmas var pierādīt arī par NV, NV' un GN00 analogiem. Un pat, ka (GN^NV')-(GNsss U NV'sss) <> 0, un (GNsss^NV'sss)-(GNss U NV'ss) <> 0, bet NV'ss = NV's un GNss - (GNs U NV's) <> 0. Problēma? Vai te tiešām ir izpētīti visi varianti? |
Kāpēc - induktīvā izveduma teorija? Matemātiķi ir slikti terminu izgudrotāji. Rekursīvās funkcijas? Kāpēc ne saprotamāk - izrēķināmās (computable) funkcijas? Kurš termins "pareizāks"? Machine learning? Ļoti vispārīgs termins, kas aptver ne tikai "mācīšanos no piemēriem". Program synthesis? Te akcentēta struktūra, kas tiek pakāpeniski būvēta. Mūsu teorēmu pierādījumos programmas dažkārt tiešām tika būvētas... Identification? Te akcentēta izvēle no gataviem risinājumiem. Meklējot funkciju dotajā numerācijā, mēs tā arī darījām... Inductive inference? |
Mūsu tā laika raksti J. M. Barzdin. Prognostication of automata and functions. Information Processing 71, B. Gilchrist, Ed. Elsevier North-Holland, New York, 1972, pp. 81-84 J. Bārzdiņš. Par programmu sintēzi pēc atsevišķiem piemēriem. Simpozijs "Programmēšanas teorija", Novosibirska, 1972 J. Bārzdiņš, R.Freivalds. Par vispārīgi rekursīvu funkciju prognozēšanu. Dokladi AN SSSR, 1972, 206. sējums, N3 R. Freivalds. Vienmērīgā un nevienmērīgā prognozējamība. LVU Zinātniskie raksti, 210.sējums, 1974 (Algoritmu un programmu teorija, 1. izlaidums), 68-81 lpp. K. Podnieks. Funkciju robežsintēzes un prognozēšanas dažādu tipu salīdzināšana. LVU Zinātniskie raksti, 210.sējums, 1974 (Algoritmu un programmu teorija, 1. izlaidums), 68-81 lpp. J. Bārzdiņš. Divas teorēmas par funkciju robežsintēzi. LVU Zinātniskie raksti, 210.sējums, 1974 (Algoritmu un programmu teorija, 1. izlaidums), 82-88 lpp. Klātneesošie kolēģi: Mihails Augustons, New Mexico Univ, tagad, arī, publikācijas. Jefims Kinbers, publikācijas, grāmata (kopā ar Carl Smith, ir tulkota japāņu valodā). |
Kas notiek tagad (šajā abstrakcijas līmenī)? Esmu atpalicis... Bet nupat, meklējot ar google "ex-identifies" adresē http://math.uni-heidelberg.de/logic/berichte.html atradu interesantu 2003.gada rakstu S. Jain, W. Menzel, F.
Stephan: Sk. arī |
