Induktiv programmering - Inductive programming

Programmeringsparadigmer

Induktiv programmering ( IP ) er et særligt område inden for automatisk programmering , der dækker forskning fra kunstig intelligens og programmering , som omhandler læring af typisk deklarative ( logiske eller funktionelle ) og ofte rekursive programmer fra ufuldstændige specifikationer, såsom input/output -eksempler eller begrænsninger.

Afhængigt af det anvendte programmeringssprog er der flere former for induktiv programmering. Induktiv funktionel programmering , der bruger funktionelle programmeringssprog som Lisp eller Haskell , og især induktiv logisk programmering , der bruger logiske programmeringssprog som Prolog og andre logiske fremstillinger som beskrivelseslogik , har været mere fremtrædende, men andet (programmerings) sprog paradigmer er også blevet brugt, såsom begrænsningsprogrammering eller probabilistisk programmering .

Definition

Induktiv programmering inkorporerer alle tilgange, der vedrører læringsprogrammer eller algoritmer fra ufuldstændige ( formelle ) specifikationer. Mulige input i et IP -system er et sæt træningsinput og tilsvarende output eller en outputevalueringsfunktion, der beskriver den ønskede adfærd for det påtænkte program, spor eller actionsekvenser, der beskriver processen med at beregne specifikke output, begrænsninger for det program, der skal induceres vedrørende dens tidseffektivitet eller kompleksitet, forskellige former for baggrundsviden såsom standard datatyper , foruddefinerede funktioner, der skal bruges, programskemaer eller skabeloner, der beskriver datastrømmen for det påtænkte program, heuristik til vejledning i søgen efter en løsning eller andre forspændinger.

Output fra et IP-system er et program i et vilkårligt programmeringssprog, der indeholder betingelser og loop eller rekursive kontrolstrukturer eller enhver anden form for Turing-komplet repræsentationssprog .

I mange applikationer skal outputprogrammet være korrekt med hensyn til eksemplerne og delvis specifikation, og dette fører til overvejelse af induktiv programmering som et særligt område inden for automatisk programmering eller programsyntese , normalt modsat 'deduktiv' programsyntese, hvor specifikationen er normalt komplet.

I andre tilfælde ses induktiv programmering som et mere generelt område, hvor ethvert deklarativt programmerings- eller repræsentationssprog kan bruges, og vi kan endda have en vis fejl i eksemplerne, som i almindelig maskinindlæring , det mere specifikke område med strukturminedrift eller området med symbolsk kunstig intelligens . Et særpræg er antallet af eksempler eller den nødvendige specifikation. Typisk kan induktive programmeringsteknikker lære af blot nogle få eksempler.

Mangfoldigheden af ​​induktiv programmering kommer normalt fra applikationerne og de sprog, der bruges: bortset fra logisk programmering og funktionel programmering er andre programmeringsparadigmer og repræsentationssprog blevet brugt eller foreslået i induktiv programmering, såsom funktionel logisk programmering , begrænsningsprogrammering , probabilistisk programmering , abduktiv logikprogrammering , modal logik , handlingssprog , agentsprog og mange typer tvingende sprog .

Historie

Forskning om den induktive syntese af rekursive funktionelle programmer startede i begyndelsen af ​​1970'erne og blev bragt på faste teoretiske fundamenter med det gængse THESIS -system for Summers og arbejde fra Biermann. Disse fremgangsmåder blev opdelt i to faser: For det første transformeres input-output-eksempler til ikke-rekursive programmer (spor) ved hjælp af et lille sæt grundlæggende operatører; for det andet søges der efter regelmæssigheder i sporene og bruges til at folde dem til et rekursivt program. De vigtigste resultater indtil midten af ​​1980'erne er undersøgt af Smith. På grund af begrænsede fremskridt med hensyn til den række programmer, der kunne syntetiseres, faldt forskningsaktiviteter betydeligt i det næste årti.

Fremkomsten af ​​logisk programmering bragte en ny elan, men også en ny retning i begyndelsen af ​​1980'erne, især på grund af MIS -systemet i Shapiro, der til sidst gød det nye felt af induktiv logisk programmering (ILP). Plotkins tidlige værker og hans " relative mindst generelle generalisering (rlgg) " havde en enorm indflydelse på induktiv logisk programmering. Det meste af ILP -arbejdet adresserer en bredere klasse af problemer, da fokus ikke kun er på rekursive logikprogrammer, men på maskinindlæring af symbolske hypoteser fra logiske repræsentationer. Der var dog nogle opmuntrende resultater ved indlæring af rekursive Prolog -programmer, f.eks. Quicksort fra eksempler sammen med passende baggrundsviden, f.eks. Med GOLEM. Men igen, efter den første succes, blev samfundet skuffet over begrænsede fremskridt med hensyn til induktion af rekursive programmer med ILP mindre og mindre fokuseret på rekursive programmer og hælder mere og mere til en machine learning -indstilling med applikationer inden for relationel datadrift og vidensopdagelse.

Parallelt med arbejdet i ILP foreslog Koza genetisk programmering i begyndelsen af ​​1990'erne som en generer-og-test baseret tilgang til læringsprogrammer. Ideen om genetisk programmering blev videreudviklet til det induktive programmeringssystem ADATE og det systematisk søgebaserede system MagicHaskeller. Også her læres funktionelle programmer fra sæt af positive eksempler sammen med en outputevalueringsfunktion (fitness), der specificerer den ønskede input/output -adfærd for det program, der skal læres.

Det tidlige arbejde med grammatikinduktion (også kendt som grammatisk inferens) er relateret til induktiv programmering, da omskrivningssystemer eller logikprogrammer kan bruges til at repræsentere produktionsregler. Faktisk betragtede tidlige værker inden for induktiv inferens grammatikinduktion og Lisp -programinferens som stort set det samme problem. Resultaterne med hensyn til lærbarhed var relateret til klassiske begreber, såsom identifikation-i-grænsen, som introduceret i guldets sædvanlige arbejde. For nylig blev sprogindlæringsproblemet behandlet af det induktive programmeringsfællesskab.

I de seneste år er de klassiske tilgange blevet genoptaget og avanceret med stor succes. Derfor er synteseproblemet blevet omformuleret på baggrund af konstruktorbaserede termomskrivningssystemer under hensyntagen til moderne teknikker til funktionel programmering samt moderat brug af søgebaserede strategier og brug af baggrundsviden samt automatisk opfindelse af underprogrammer. Mange nye og vellykkede applikationer er for nylig dukket op ud over programsyntese, især inden for datamanipulation, programmering ved eksempel og kognitiv modellering (se nedenfor).

Andre ideer er også blevet undersøgt med det fælles kendetegn ved at bruge deklarative sprog til fremstilling af hypoteser. For eksempel er brugen af ​​højere ordens funktioner, ordninger eller strukturerede afstande blevet anbefalet for en bedre håndtering af rekursive datatyper og strukturer; abstraktion er også blevet undersøgt som en mere kraftfuld tilgang til kumulativ læring og funktionsopfindelse.

Et kraftfuldt paradigme, der for nylig er blevet brugt til repræsentation af hypoteser i induktiv programmering (generelt i form af generative modeller ) er probabilistisk programmering (og beslægtede paradigmer, såsom stokastiske logikprogrammer og bayesisk logisk programmering).

Anvendelsesområder

Den første workshop om Approaches and Applications of Inductive Programming (AAIP), der blev afholdt i forbindelse med ICML 2005, identificerede alle applikationer, hvor der kræves "læring af programmer eller rekursive regler, [...] først inden for software engineering, hvor strukturel læring, softwareassistenter og softwareagenter kan hjælpe med at aflaste programmører fra rutinemæssige opgaver, give programmeringsstøtte til slutbrugere eller støtte til nybegyndere og programmeringsvejledersystemer. Yderligere anvendelsesområder er sprogindlæring, læring af rekursive kontrolregler til AI-planlægning, læring rekursiv begreber i web-mining eller til dataformat-transformationer ".

Siden da har disse og mange andre områder vist sig at være vellykkede applikationsnischer til induktiv programmering, såsom slutbrugerprogrammering , de relaterede programmeringsområder ved eksempel og programmering ved demonstration og intelligente vejledningssystemer .

Andre områder, hvor der for nylig er blevet anvendt induktiv inferens, er vidensindsamling , kunstig generel intelligens , forstærkningslæring og teorievaluering og kognitiv videnskab generelt. Der kan også være potentielle applikationer inden for intelligente agenter, spil, robotik, personalisering, omgivende intelligens og menneskelige grænseflader.

Se også

Referencer

Yderligere læsning

eksterne links