Nyligen har det funnits en ökande mängd forskning om lärande begrepp uttryckt i undergrupper av Prolog; termen induktiv logik programmering (ILP) har använts för att beskriva denna växande kropp av forskning. Denna uppsats syftar till att utvidga ILP:s teoretiska grundvalar genom att undersöka logikprogrammens pac-learnability. Vi fokuserar på program som består av en enda funktionsfri icke-rekursiv klausul, och fokuserar på generaliseringar av ett språk som är känt för att vara pac-lärbart: nämligen språket av determinera funktionsfria klausuler av konstant djup. Vi visar att ett antal syntaktiska generaliseringar av detta språk är svåra att lära, men att språket kan generaliseras till klausuler om konstant lokalitet samtidigt som pac-lärbarhet tillåts. Mer specifikt visar vi först att determinera klausuler om logdjup inte är pac-learnable, oavsett vilket språk som används för att representera hypoteser. Vi undersöker sedan eekten av att tillåta obestämdhet i en klausul, och visar att klausuler med k obestämbara variabler är lika svåra att lära som DNF. Vi visar därefter att ett mer begränsat språk av klausuler med begränsad obestämdhet är inlärbart med hjälp av k-CNF för att representera hypoteser, och att begränsa \lokaliteten" av en klausul till en konstant gör pac-learnability även om en godtycklig mängd obestämdhet är tillåten. Detta sista resultat visar sig också vara en strikt generalisering av det tidigare resultatet för att fastställa funktionsfria klausuler av konstant djup. Slutligen presenterar vi några tillägg av dessa resultat till logiska program med flera klausuler.
Ett annat relaterat papper undersöker inlärningsförmågan hos icke-rekursiva Prolog-program REF; detta dokument innehåller också ett antal negativa resultat som starkt motiverar begränsningen av konstant djup determinitet.
Pac-Learning Non-Recursive Prolog Clauses
{'venue': 'ARTIFICIAL INTELLIGENCE', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}