Version space

Da Wikipedia, l'enciclopedia libera.

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.

Version space per un linguaggio ipotetico "rettangolare" in due dimensioni. Le croci verdi sono esempi positivi, mentre i cerchi rossi sono esempi negativi. GB è la frontiera delle ipotesi positive massimamente generale, e SB è la frontiera delle ipotesi positive massimamente specializzata. I rettangoli verdi intermedi rappresentano le ipotesi nel version space.

Storia[modifica | modifica sorgente]

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 | modifica sorgente]

Di solito, laddove esiste un ordine-di-generalità (generality ordering) sulle ipotesi, è possibile rappresentare il version space con due insiemi di ipotesi:

  1. le ipotesi consistenti più specifiche,
  2. le ipotesi consistenti più generali,

dove l'aggettivo consistente è indice di accordo con i dati osservati.

Ipotesi più specifiche[modifica | modifica sorgente]

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 | modifica sorgente]

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 | modifica sorgente]

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 | modifica sorgente]

  1. ^ Mitchell (1997)

Bibliografia[modifica | modifica sorgente]

  • Vincent Dubois, Quafafou, Mohamed, Concept learning with approximation: Rough version spaces, 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, Arlington, VA, 1992, pp. 308–315.

Voci correlate[modifica | modifica sorgente]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica