Version space
# 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.

Questo insieme contiene tutte le ipotesi che non sono state eliminate a causa di un conflitto con i dati osservati.

## Storia

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

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

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

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

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.

