In informatica, la teoria dell'apprendimento computazionale (o semplicemente teoria dell'apprendimento) è un sotto-campo dell'intelligenza artificiale dedicato allo studio della progettazione e dell'analisi degli algoritmi di apprendimento automatico.
Descrizione generale Nell'apprendimento automatico lo studio e i relativi risultati teorici è stato focalizzato principalmente su un tipo di apprendimento induttivo detto apprendimento supervisionato. Nell'apprendimento supervisionato, a un algoritmo vengono fornite istanze etichettate in modo utile alla soluzione del problema dato. Ad esempio, le istanze potrebbero costituire descrizioni di funghi e le etichette potrebbero indicare se essi siano commestibili o meno. L'algoritmo accetta istanze precedentemente etichettate e le utilizza per indurre un classificatore. Questo classificatore è una funzione che assegna etichette alle istanze, incluse quelle che non sono state considerate dall'algoritmo in precedenza durante la fase di addestramento. L'obiettivo dell'algoritmo è ottimizzare alcune misure delle prestazioni dei classificatori, come ad esempio la minimizzazione del numero di errori commessi su nuove istanze.
Oltre ai limiti delle prestazioni, la teoria dell'apprendimento computazionale studia la complessità in tempo e la fattibilità dei problemi di apprendimento e dei relativi algoritmi. In tale teoria, un problema (classe di funzioni) è considerato fattibile se esiste un algoritmo risolutivo che può essere eseguito in tempo polinomiale. Esistono due tipi di risultati di complessità temporale:
Risultati positivi Dimostrare che una certa classe di funzioni possa essere appresa in tempo polinomiale. Risultati negativi Dimostrare che alcune classi non possono essere apprese in tempo polinomiale.
I risultati negativi si basano spesso su assunzioni comunemente accettate come plausibili, ma non ancora dimostrate, come:
Complessità computazionale – P ≠ NP (problema P contro NP); Crittografia – Esistenza di funzioni unidirezionali.
Ci sono diversi approcci alla teoria dell'apprendimento computazionale, basati su diverse assunzioni sui principi di inferenza utilizzati per generalizzare a partire da dati limitati. Tra queste, diverse definizioni di probabilità (si veda la probabilità frequentista, probabilità bayesiana) e assunzioni diverse riguardanti la generazione di campioni. I diversi approcci includono:
Apprendimento esatto, proposto da Angluin; Apprendimento probabilmente approssimativamente corretto (o PAC learning), proposto da Valiant; Teoria VC, proposta da Vapnik e Chervonenkis; Inferenza induttiva, sviluppata da Solomonoff; Teoria dell'apprendimento algoritmico, dal lavoro di Gold; Apprendimento automatico online, dal lavoro di Littlestone.
Sebbene il suo obiettivo primario sia comprendere l'apprendimento in astratto, la teoria dell'apprendimento computazionale ha portato, sul fronte pratico, allo sviluppo di nuovi algoritmi. Ad esempio, la teoria PAC ha ispirato il boosting, la teoria VC ha portato alle macchine a vettori di supporto e l'inferenza bayesiana ha portato alle reti bayesiane.
Note
Voci correlate Apprendimento probabilmente approssimativamente corretto Induzione di grammatiche Occam learning Teoria dell'informazione
Bibliografia Rassegne
Angluin, D. 1992. Computational learning theory: Survey and selected bibliography. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 351–369. http://portal.acm.org/citation.cfm?id=129712.129746 D. Haussler. Probably approximately correct learning. In AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, pp. 1101–1108. AAAI, 1990. http://citeseer.ist.psu.edu/haussler90probably.html
Selezione delle feature
A. Dhagat e L. Hellerstein, "PAC learning with irrelevant attributes", in 'Proceedings of the IEEE Symp. on Foundation of Computer Science', 1994. http://citeseer.ist.psu.edu/dhagat94pac.html
Apprendimento ottimale della notazione O
Oded Goldreich, Dana Ron. On universal learning algorithms . http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2224
Risultati negativi
M. Kearns e Leslie Valiant. 1989. Cryptographic limitations on learning boolean formulae and finite automata. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 433–444, ACM. http://citeseer.ist.psu.edu/kearns89cryptographic.html
Tolleranza agli errori
Michael Kearns e Ming Li. Learning in the presence of malicious errors. SIAM Journal on Computing, 22(4):807–837, 1993. http://citeseer.ist.psu.edu/kearns93learning.html Kearns, M. (1993). Efficient noise-tolerant learning from statistical queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pp. 392–401. http://citeseer.ist.psu.edu/kearns93efficient.html
Equivalenza
D.Haussler, M.Kearns, N.Littlestone e M. Warmuth, Equivalence of models for polynomial learnability, Proc. 1st ACM Workshop on Computational Learning Theory (1988) 42-55. Pitt, L.; Warmuth, M. K., Prediction-Preserving Reducibility, in Journal of Computer and System Sciences, vol. 41, n. 3, 1990, pp. 430–467, DOI:10.1016/0022-0000(90)90028-J.
Collegamenti esterni
Categoria:Apprendimento automatico Categoria:Teoria della complessità computazionale Categoria:Intelligenza artificiale