Induktiv programmering

Induktiv programmering ( IP ) är ett speciellt område för automatisk programmering , som täcker forskning från artificiell intelligens och programmering , som adresserar inlärning av typiskt deklarativa ( logiska eller funktionella ) och ofta rekursiva program från ofullständiga specifikationer, såsom in-/utdataexempel eller begränsningar.

Beroende på vilket programmeringsspråk som används finns det flera typer av induktiv programmering. Induktiv funktionell programmering , som använder funktionella programmeringsspråk som Lisp eller Haskell , och framför allt induktiv logikprogrammering , som använder logiska programmeringsspråk som Prolog och andra logiska representationer som beskrivningslogik , har varit mer framträdande, men andra (programmerings)språk paradigm har också använts, såsom begränsningsprogrammering eller probabilistisk programmering .

Definition

Induktiv programmering inkluderar alla tillvägagångssätt som handlar om inlärningsprogram eller algoritmer från ofullständiga ( formella ) specifikationer. Möjliga ingångar i ett IP-system är en uppsättning träningsingångar och motsvarande utgångar eller en utvärderingsfunktion, som beskriver det önskade beteendet för det avsedda programmet, spår eller åtgärdssekvenser som beskriver processen för att beräkna specifika utdata, begränsningar för programmet som ska induceras om dess tidseffektivitet eller dess komplexitet, olika typer av bakgrundskunskap såsom standarddatatyper, fördefinierade funktioner som ska användas, programscheman eller mallar som beskriver dataflödet för det avsedda programmet, heuristik för att vägleda sökningen efter en lösning eller andra fördomar.

Utdata från ett IP-system är ett program i något godtyckligt programmeringsspråk som innehåller villkor och loop eller rekursiva kontrollstrukturer, eller någon annan typ av Turing-komplett representationsspråk .

I många applikationer måste utgångsprogrammet vara korrekt med avseende på exemplen och delspecifikationen, och detta leder till att induktiv programmering betraktas som ett speciellt område inom automatisk programmering eller programsyntes, vanligtvis i motsats till " deduktiv " programsyntes, där specifikationen är vanligtvis komplett.

I andra fall ses induktiv programmering som ett mer allmänt område där alla deklarativa programmerings- eller representationsspråk kan användas och vi kan till och med ha en viss grad av fel i exemplen, som i allmän maskininlärning, det mer specifika området för strukturmining eller området för symbolisk artificiell intelligens . En utmärkande egenskap är antalet exempel eller delspecifikationer som behövs. Vanligtvis kan induktiva programmeringstekniker lära sig av bara några få exempel.

Mångfalden av induktiv programmering kommer vanligtvis från applikationerna och språken som används: förutom logisk programmering och funktionell programmering, har andra programmeringsparadigm och representationsspråk använts eller föreslagits i induktiv programmering, såsom funktionell logisk programmering , begränsningsprogrammering , probabilistisk programmering , abduktiv logikprogrammering , modal logik , handlingsspråk , agentspråk och många typer av imperativspråk .

Historia

Forskning om den induktiva syntesen av rekursiva funktionella program startade i början av 1970-talet och lades på fasta teoretiska grunder med det framträdande THESIS-systemet från Summers och Biermanns arbete. Dessa tillvägagångssätt delades upp i två faser: för det första omvandlas input-output-exempel till icke-rekursiva program (spår) med hjälp av en liten uppsättning grundläggande operatorer; för det andra söks regelbundenheter i spåren efter och används för att vika dem till ett rekursivt program. Huvudresultaten fram till mitten av 1980-talet kartläggs av Smith. På grund av begränsade framsteg med avseende på utbudet av program som kunde syntetiseras, minskade forskningsaktiviteterna avsevärt under det kommande decenniet.

Tillkomsten av logisk programmering gav en ny elan men också en ny riktning i början av 1980-talet, särskilt på grund av att Shapiros MIS-system så småningom skapade det nya området för induktiv logikprogrammering (ILP). De tidiga verken av Plotkin, och hans " relativ minst allmänna generalisering (rlgg) ", hade en enorm inverkan i induktiv logikprogrammering. Det mesta av ILP-arbetet tar upp en bredare klass av problem, eftersom fokus inte bara ligger på rekursiva logikprogram utan på maskininlärning av symboliska hypoteser från logiska representationer. Det fanns dock några uppmuntrande resultat när det gäller att lära sig rekursiva Prolog-program som att snabbsortera från exempel tillsammans med lämplig bakgrundskunskap, till exempel med GOLEM. Men igen, efter den första framgången, blev samhället besviket över begränsade framsteg när det gäller induktionen av rekursiva program med ILP som allt mindre fokuserade på rekursiva program och lutade mer och mer mot en maskininlärningsmiljö med tillämpningar inom relationell datautvinning och kunskapsupptäckt .

Parallellt med arbetet inom ILP föreslog Koza genetisk programmering i början av 1990-talet som en genererings- och testbaserad metod för lärandeprogram. Idén med genetisk programmering vidareutvecklades till det induktiva programmeringssystemet ADATE och det systematiskt-sökningsbaserade systemet MagicHaskeller. Även här lärs funktionella program från uppsättningar av positiva exempel tillsammans med en utvärderingsfunktion (fitness) som specificerar det önskade input/outputbeteendet för programmet som ska läras in.

Det tidiga arbetet med grammatisk induktion (även känd som grammatisk inferens) är relaterat till induktiv programmering, eftersom omskrivningssystem eller logikprogram kan användas för att representera produktionsregler. Faktum är att tidiga verk inom induktiv slutledning ansåg grammatikinduktion och Lisp-program slutledning som i princip samma problem. Resultaten i termer av inlärningsbarhet var relaterade till klassiska begrepp, såsom identifiering-i-gränsen, som introducerades i guldets nyskapande arbete. På senare tid togs språkinlärningsproblemet upp av den induktiva programmeringsgemenskapen.

Under de senaste åren har de klassiska metoderna återupptagits och utvecklats med stor framgång. Därför har syntesproblemet omformulerats mot bakgrund av konstruktorbaserade termomskrivningssystem med hänsyn till moderna tekniker för funktionell programmering, såväl som måttlig användning av sökbaserade strategier och användning av bakgrundskunskap samt automatisk uppfinning av underprogram. Många nya och framgångsrika applikationer har nyligen dykt upp bortom programsyntes, särskilt inom området datamanipulation, programmering genom exempel och kognitiv modellering (se nedan).

Andra idéer har också utforskats med den gemensamma egenskapen att använda deklarativa språk för representation av hypoteser. Till exempel har användningen av högre ordningens funktioner, scheman eller strukturerade avstånd förespråkats för en bättre hantering av rekursiva datatyper och strukturer; abstraktion har också utforskats som ett mer kraftfullt tillvägagångssätt för kumulativ inlärning och funktionsuppfinning.

Ett kraftfullt paradigm som nyligen har använts för representation av hypoteser i induktiv programmering (vanligtvis i form av generativa modeller ) är probabilistisk programmering (och relaterade paradigm, såsom stokastiska logikprogram och Bayesiansk logikprogrammering).

Användningsområden

Den första workshopen om tillvägagångssätt och tillämpningar av induktiv programmering (AAIP) som hölls i samband med ICML 2005 identifierade alla tillämpningar där "inlärning av program eller rekursiva regler krävs, [...] först inom området mjukvaruteknik där strukturellt lärande, mjukvaruassistenter och programvaruagenter kan hjälpa till att befria programmerare från rutinuppgifter, ge programmeringsstöd till slutanvändare eller stöd för nybörjare och programmeringshandledaresystem. Ytterligare användningsområden är språkinlärning, inlärning av rekursiva styrregler för AI-planering, inlärning rekursiv koncept inom webbmining eller för transformationer av dataformat".

Sedan dess har dessa och många andra områden visat sig vara framgångsrika applikationsnischer för induktiv programmering, såsom slutanvändarprogrammering , de relaterade områdena programmering genom exempel och programmering genom demonstration , och intelligenta handledningssystem .

Andra områden där induktiv slutledning nyligen har tillämpats är kunskapsinhämtning , artificiell allmän intelligens , förstärkningsinlärning och teoriutvärdering och kognitionsvetenskap i allmänhet. Det kan också finnas potentiella tillämpningar inom intelligenta agenter, spel, robotik, personalisering, omgivande intelligens och mänskliga gränssnitt.

Se även

• Evolutionär programmering
• Induktivt resonemang
• Testdriven utveckling

Vidare läsning

•   Flener, P.; Schmid, U. (2008). "En introduktion till induktiv programmering". Granskning av artificiell intelligens . 29 (1): 45–62. doi : 10.1007/s10462-009-9108-7 . S2CID 26314997 .
•    Kitzelmann, E. (2010). "Induktiv programmering: En undersökning av programsyntestekniker" (PDF) . Tillvägagångssätt och tillämpningar av induktiv programmering . Föreläsningsanteckningar i datavetenskap. Vol. 5812. s. 50–73. CiteSeerX 10.1.1.180.1237 . doi : 10.1007/978-3-642-11931-6_3 . ISBN 978-3-642-11930-9 . {{ citera bok }} : Saknas eller tom |title= ( hjälp )
• Partridge, D. (1997). "Följet för induktiv programmering". Dator . 30 (1): 36–41. doi : 10.1109/2.562924 .
•   Flener, P.; Partridge, D. (2001). "Induktiv programmering". Automatiserad mjukvaruteknik . 8 (2): 131–137. doi : 10.1023/a:1008797606116 . S2CID 6675212 .
• Hofmann, M.; Kitzelmann, E. (2009). "Ett enande ramverk för analys och utvärdering av induktiva programmeringssystem" . Handlingar från den andra konferensen om artificiell allmän intelligens : 55–60.
• Muggleton, S.; De Raedt, L. (1994). "Induktiv logikprogrammering: teori och metoder" . The Journal of Logic Programming . 19–20: 629–679. doi : 10.1016/0743-1066(94)90035-3 .
•   Lavrac, N.; Dzeroski, S. (1994). Induktiv logikprogrammering: tekniker och tillämpningar . New York: Ellis Horwood. ISBN 978-0-13-457870-5 . https://web.archive.org/web/20040906084947/http://www-ai.ijs.si/SasoDzeroski/ILPBook/
• Muggleton, S.; De Raedt, Luc.; Poole, D.; Bratko, I.; Flach, P.; Inoue, K.; Srinivasan, A. (2012). "ILP fyller 20" . Maskininlärning . 86 (1): 3–23. doi : 10.1007/s10994-011-5259-2 .
•    Gulwani, S.; Hernandez-Orallo, J.; Kitzelmann, E.; Muggleton, SH; Schmid, U.; Zorn, B. (2015). "Induktiv programmering möter den verkliga världen" . Kommunikation från ACM . 58 (11): 90–99. CiteSeerX 10.1.1.696.3800 . doi : 10.1145/2736282 . hdl : 10251/64984 . S2CID 425881 .

externa länkar

• Community-sida för induktiv programmering , värd av University of Bamberg.