Version space
Un version space, nel campo del concept learning (o induzione), è il sottoinsieme di tutte le ipotesi consistenti con gli esempi di training osservati.[1]
Questo insieme contiene tutte le ipotesi che non sono state eliminate a causa di un conflitto con i dati osservati.
Storia modifica
La notazione Version Spaces venne introdotta da Tom M. Mitchell come base per capire il problema fondamentale dell'apprendimento supervisionato (supervised learning) nel contesto del solution search (ricerca di una soluzione). Sebbene il metodo "candidate elimination" (usato nel Version Space framework) non sia un algoritmo di apprendimento molto popolare, esistono alcune implementazioni pratiche che sono state realizzate (e.g. Sverdlik & Reynolds 1992, Hong & Tsang 1997, Dubois & Quafafou 2002).
L'algoritmo per il Version Space modifica
Di solito, laddove esiste un ordine-di-generalità (generality ordering) sulle ipotesi, è possibile rappresentare il version space con due insiemi di ipotesi:
- le ipotesi consistenti più specifiche,
- le ipotesi consistenti più generali,
dove l'aggettivo consistente è indice di accordo con i dati osservati.
Ipotesi più specifiche modifica
Le ipotesi più specifiche (i.e. la frontiera specializzata SB) sono quelle che includono gli esempi positivi di training osservati, e tali che siano nel più piccolo spazio rimanente delle feature. Queste sono le ipotesi che, nel caso venissero ridotte ulteriormente, escluderebbero un esempio positivo di training, e diverrebbero quindi inconsistenti. Queste ipotesi minimali costituiscono essenzialmente un caso pessimistico in cui il concetto di verità è definito esclusivamente sulla base dei dati positivi osservati fino a quel momento. Nel caso si osservasse un nuovo dato (novel data point), questo dovrebbe essere assunto negativo (i.e. se il dato non è stato incluso (ruled in) in precedenza, il dato viene escluso (ruled out)).
Ipotesi più generali modifica
Le ipotesi più generali (i.e. la frontiera generale GB) sono quelle che includono gli esempi positivi di training osservati e lo spazio rimanente delle feature che non include gli esempi negativi di training. Queste sono le ipotesi che, se estese ulteriormente, includerebbero gli esempi negativi di training, e quindi diventerebbero inconsistenti. Queste ipotesi massimali costituiscono di fatto un caso ottimistico in cui il concetto di verità è definito esclusivamente dai dati negativi osservati in precedenza. Dunque, se viene osservato un nuovo dato, questo dovrebbe essere assunto positivo (i.e. se il dato non è stato escluso (ruled out) in precedenza, il dato viene incluso (ruled in)).
Conclusione modifica
Quindi, durante il processo di apprendimento (learning process), il version space (i.e. un insieme - in teoria infinito - che contiene tutte le ipotesi consistenti) può essere completamente definito dal suo lower-bound e dal suo upper-bound (rispettivamente l'insieme delle ipotesi massimamente generale e l'insieme delle ipotesi massimamente specializzato), e le operazioni di apprendimento (learning operations) possono essere eseguite in questi insiemi rappresentativi.
Note modifica
- ^ Mitchell (1997)
Bibliografia modifica
- Vincent Dubois, Quafafou, Mohamed, Concept learning with approximation: Rough version spaces, in Rough Sets and Current Trends in Computing: Proceedings of the Third International Conference, RSCTC 2002, Malvern, Pennsylvania, 2002, pp. 239–246.
- Tzung-Pai Hong, Shian-Shyong Tsang, A generalized version space learning algorithm for noisy and uncertain data, in IEEE Transactions on Knowledge and Data Engineering, vol. 9, n. 2, 1997, pp. 336–340, DOI:10.1109/69.591457.
- John Stuart Mill, A System of Logic, Ratiocinative and Inductive: Being a Connected View of the Principles of Evidence and the Methods of Scientific Investigation, Honolulu, HI, University Press of the Pacific, 1843/2002.
- Tom M. Mitchell, Machine Learning, Boston, McGraw-Hill, 1997.
- W. Sverdlik, Reynolds, R.G., Dynamic version spaces in machine learning, in Proceedings, Fourth International Conference on Tools with Artificial Intelligence (TAI '92), Arlington, VA, 1992, pp. 308–315.
