Teorie algoritmického učení je matematický rámec pro analýzu
problémů a algoritmů strojového učení. Synonyma zahrnují teorii formálního učení a algoritmickou induktivní inferenci. Teorie algoritmického učení se liší od teorie statistického učení tím, že nevyužívá statistických předpokladů a analýzy. Jak algoritmická, tak statistická teorie učení se zabývají strojovým učením a lze je tedy považovat za odvětví teorie výpočetního učení.
Rozlišovací charakteristiky
Na rozdíl od teorie statistického učení a většiny statistických teorií obecně, teorie algoritmického učení nepředpokládá, že data jsou náhodné vzorky, to znamená, že datové body jsou na sobě nezávislé. To činí teorii vhodnou pro oblasti, kde jsou pozorování (relativně) bez šumu, ale ne náhodná, jako je jazykové učení a automatizované vědecké objevy.
Základním konceptem teorie algoritmického učení je učení se v limitu: s rostoucím počtem datových bodů by se měl algoritmus učení konvergovat ke správné hypotéze na každé možné datové sekvenci konzistentní s prostorem problému. Jedná se o neperspektivní verzi statistické konzistence,
která také vyžaduje konvergenci ke správnému modelu v limitu, ale umožňuje učícímu se selhat na datových sekvencích s mírou pravděpodobnosti 0.
Algoritmická teorie učení zkoumá schopnost učení Turingových strojů. Jiné frameworky zvažují mnohem omezenější třídu učících se algoritmů než Turingovy stroje, například učící se, kteří počítají hypotézy rychleji, například v polynomiálním čase. Příkladem takového rámce je pravděpodobně přibližně správné učení.
Koncept byl představen v seminární práci E. Marka Golda „Identifikace jazyka v limitu“. Cílem jazykové identifikace je, aby stroj s jedním programem byl schopen vyvinout jiný program, pomocí kterého lze otestovat jakoukoliv danou větu, zda je „gramatická“ nebo „ungrammatická“. Učeným jazykem nemusí být angličtina nebo jiný přirozený jazyk – ve skutečnosti může být definicí „gramatické“ naprosto cokoliv, co testující zná.
Ve Goldově učebním modelu dává tester studentovi v každém kroku ukázkovou větu a student reaguje hypotézou, což je navrhovaný program pro určení gramatické správnosti. Od testera se vyžaduje, aby se v seznamu nakonec objevila každá možná věta (gramatická nebo ne), ale nevyžaduje se žádné konkrétní pořadí. Od studujícího se vyžaduje, aby v každém kroku byla hypotéza správná pro všechny věty, které dosud byly.
O konkrétním studujícím se říká, že je schopen „naučit se jazyk v limitu“, pokud existuje určitý počet kroků, za kterými se jeho hypotéza již nemění. V tomto bodě se skutečně naučil jazyk, protože každá možná věta se objevuje někde v posloupnosti vstupů (minulých nebo budoucích) a hypotéza je správná pro všechny vstupy (minulé nebo budoucí), takže hypotéza je správná pro každou větu. Studující nemusí být schopen poznat, kdy dospěl ke správné hypotéze, vše, co se vyžaduje, je, aby byla pravdivá.
Gold ukázal, že jakýkoli jazyk, který je definován Turingovým strojovým programem, může být naučen v limitu jiným Turingovým-kompletním strojem pomocí výčtu. To se provádí tak, že učící se postupně testuje všechny možné Turingovy strojové programy, dokud se nenajde jeden, který je zatím správný – to tvoří hypotézu pro aktuální krok. Nakonec se dosáhne správného programu, po kterém se hypotéza už nikdy nezmění (ale všimněte si, že učící se neví, že se nebude muset měnit).
Gold také ukázal, že pokud je studující uveden pouze pozitivní příklady (to znamená, že se ve vstupních větách objevují pouze gramatické věty, nikoli věty negrammatické), pak lze zaručit, že se jazyk naučí v limitu pouze tehdy, pokud existuje pouze konečný počet možných vět v jazyce (to je možné, pokud je například známo, že věty mají omezenou délku).
Identifikace jazyka v limitě je vysoce abstraktní model. Neumožňuje limity běhové doby nebo počítačové paměti, které se mohou vyskytnout v praxi, a metoda výčtu může selhat, pokud se vyskytnou chyby ve vstupu. Rámec je však velmi výkonný, protože pokud jsou tyto přísné podmínky zachovány, umožňuje učení jakéhokoli programu, o kterém je známo, že je vyčíslitelný. Je to proto, že Turingův strojový program může být napsán tak, aby napodobil jakýkoli program v jakémkoli konvenčním programovacím jazyce. Viz Church-Turingova teze.
Další identifikační kritéria
Teoretici učení zkoumali další kritéria učení, například následující.
Hranice změn mysli úzce souvisí s hranicemi chyb, které jsou studovány v teorii statistického učení. Kevin Kelly naznačil, že minimalizace změn mysli úzce souvisí s výběrem maximálně jednoduchých hypotéz ve smyslu Occamovy břitvy.