Spazio dei concetti superesponenziale e parole semplici

Articolo originale
Eliezer Yudkowsky
Eliezer Yudkowsky
24 Febbraio 2008
24 Febbraio 2008

Lo spazio delle cose, potreste pensare, è uno spazio veramente enorme. Molto più grande della realtà, perché mentre la realtà contiene solo le cose che esistono, lo spazio delle cose contiene ogni cosa che potrebbe esistere.

In effetti, nel modo in cui ho “definito” lo Spazio delle Cose con dimensioni per ogni possibile attributo — inclusi gli attributi correlati come densità, volume e massa — lo Spazio delle Cose potrebbe essere definito in modo troppo impreciso per avere qualcosa che potremmo chiamare una grandezza. Ma è comunque importante poter visualizzare lo Spazio delle Cose in qualche modo. Certamente, nessuno può veramente comprendere uno stormo di passeri se tutto quello che vede è una nuvola di cose che cinguettano e battono le ali, piuttosto che un raggruppamento di punti nello Spazio delle Cose.

Ma per quanto vasto possa essere lo Spazio delle Cose, non è nulla in confronto allo Spazio dei Concetti.

“Concetto”, nel campo dell’apprendimento automatico, significa una regola che include o esclude determinati esempi. Se vedi i dati 2:+, 3:-, 14:+, 23:-, 8:+, 9:- puoi supporre che il concetto sia “numeri pari”. Esiste una letteratura abbastanza ampia (come prevedibile) su come imparare i concetti dai dati… dati esempi casuali, dati esempi scelti… dati possibili errori nella classificazione… e soprattutto, dati differenti spazi di regole possibili.

Supponiamo, per esempio, di voler imparare il concetto “giorni buoni per giocare a tennis”. Gli attributi possibili per i giorni sono:

Cielo: {Limpido, Nuvoloso, Pioggia}
Temperatura: {Caldo, Freddo}
Umidità: {Normale, Alta}
Vento: {Forte, Debole}

Ci vengono poi presentati i seguenti dati, dove + indica un esempio positivo del concetto, mentre – indica una classificazione negativa:

+ Cielo: Limpido; Temperatura: Caldo; Umidità: Alta; Vento: Forte.
- Cielo: Pioggia; Temperatura: Freddo; Umidità: Alta; Vento: Forte.
+ Cielo: Limpido; Temperatura: Caldo; Umidità: Alta; Vento: Debole.

Cosa dovrebbe inferire un algoritmo da tutto questo?

Un apprenditore automatico potrebbe rappresentare un concetto che si adatta a questi dati come segue:

Cielo: ?; Temperatura: Caldo; Umidità: Alta; Vento: ?

In questo formato, per determinare se il concetto accetta o rifiuta un esempio, confrontiamo elemento per elemento: ? accetta qualsiasi cosa, ma un valore specifico accetta solo quel valore.

Quindi il concetto indicato sopra accetta solo giorni con Temperatura=Caldo e Umidità=Alta, ma Cielo e Vento possono avere qualsiasi valore. Questo si adatta sia alle classificazioni negative che a quelle positive dei dati visti finora — anche se non è l’unico concetto che gli si può adattare.

Possiamo anche semplificare la rappresentazione del concetto come {?, Caldo, Alta, ?}.

Senza entrare nei dettagli, l’algoritmo classico sarebbe:

  • Scegliamo l’insieme delle ipotesi più generali che si adattano ai dati — quelle che accettano il maggior numero di casi possibile, compatibilmente con i dati noti.
  • Scegliamo un altro insieme con le ipotesi più specifiche che si adattano ai dati — quelle che escludono il maggior numero possibile di casi, compatibilmente con i dati noti.
  • Ogni volta che vediamo un esempio negativo, rafforziamo il minimo necessario le ipotesi più generali, in modo che il nuovo insieme sia ancora il più generale possibile pur rispettando i dati noti.
  • Ogni volta che vediamo un esempio positivo, indeboliamo il minimo necessario le ipotesi più specifiche, in modo che il nuovo insieme sia ancora il più generale possibile pur rispettando i dati noti.
  • Continuiamo finché rimane un’unica ipotesi. Questa sarà la risposta se il concetto che stiamo cercando era nel nostro spazio delle ipotesi.

Nel caso sopra, l’insieme delle ipotesi più generali sarebbe {?, Caldo, ?, ?} e {Limpido, ?, ?, ?}, mentre l’insieme delle ipotesi più specifiche contiene solo {Limpido, Caldo, Alta, ?}.

Qualunque altro concetto che puoi trovare che si adatta ai dati, sarà strettamente più specifico di una delle ipotesi generali, e strettamente più generale delle ipotesi specifiche.

(Per approfondimenti consiglio Machine Learning di Tom Mitchell, dal quale ho preso e adattato questo esempio).

Ora, potreste notare che il formato usato sopra non può rappresentare tutti i possibili concetti. Ad es. “Giocare a tennis quando il cielo è limpido o l’aria è calda”. Questo corrisponde ai dati, ma nella rappresentazione dei concetti definita prima non esiste una quadrupla di valori che descriva la regola.

Chiaramente, il nostro apprenditore automatico non è molto generale. Perché non permettergli di rappresentare tutti i possibili concetti, così che possa imparare con la maggiore flessibilità possibile?

I giorni sono composti da queste quattro variabili, una variabile con 3 valori e tre variabili con 2 valori ciascuna. Così possiamo trovare 3*2*2*2 = 24 possibili tipi di giorno.

Il formato che abbiamo usato per descrivere i concetti ci permette di richiedere, per ciascuna variabile, uno di questi valori, oppure di lasciare la variabile libera. Quindi in questa rappresentazione ci sono 4*3*3*3 = 108 concetti. Perché l’algoritmo più-generale/più-specifico funzioni, dobbiamo partire con l’ipotesi più specifica “nessun esempio è mai positivo”. Se aggiungiamo quella, abbiamo un totale di 109 concetti.

Non è sospetto il fatto che ci siano più possibili concetti che possibili giorni? Assolutamente no: dopo tutto un concetto può essere visto come una raccolta di giorni. Un concetto può essere visto come l’insieme di giorni che lo classificano positivamente o, isomorficamente, l’insieme dei giorni che lo classificano negativamente.

Quindi lo spazio di tutti i possibili concetti che classificano i giorni, è l’insieme di tutti i possibili insiemi di giorni, che contiene 224 = 16,777,216 elementi.

Questo spazio completo comprende tutti i concetti di cui abbiamo discusso finora. Ma include anche concetti come “Classifica positivamente solo i casi {Limpido, Caldo, Alta, Forte} e {Limpido, Caldo, Alta, Debole} e rifiuta qualunque altra cosa” o “Classifica negativamente solo il caso {Pioggia, Freddo, Alta, Forte} e accetta tutto il resto”. Include anche concetti senza una rappresentazione compatta, semplicemente liste di cosa è o non è permesso.

Questo è il problema quando si cerca di costruire un apprenditore induttivo “completamente generale”: non può imparare un concetto finché non ha visto ogni possibile esempio nello spazio delle cose.

Se aggiungiamo altri attributi ai giorni — come la temperatura dell’acqua le previsioni per domani — il numero dei possibili giorni aumenta esponenzialmente con il numero degli attributi. Ma questo non è un problema, nel nostro spazio concettuale ristretto, perché possiamo limitare un grande spazio utilizzando un numero logaritmico di esempi.

Diciamo che aggiungiamo l’attributo Acqua: {Calda, Fredda} ai giorni, il che porta a 48 i possibili giorni e a 325 i possibili concetti. Diciamo che ciascun giorno che vediamo sia, in genere, classificato positivo da circa la metà dei concetti attualmente possibili, e classificato negativamente dall’altra metà. Quindi, quando impariamo l’effettiva classificazione di un esempio, dividiamo a metà lo spazio dei concetti compatibili. Così potrebbero bastare solo 9 esempi (29 = 512) per ridurre 325 possibili concetti fino a uno.

Anche se i giorni avesse quaranta attributi binari, ci vorrebbe ancora un numero ragionevole di esempi per restringere a uno la lista dei concetti possibili. 64 esempi, se ciascuno è classificato positivo da metà dei concetti rimanenti. Supponendo, naturalmente, che la regola effettiva sia rappresentabile nel nostro sistema!

Se invece vuoi pensare a tutte le possibilità, beh, auguri. Lo spazio di tutti i possibili concetti cresce superesponenzialmente col numero degli attributi.

Quando arriviamo a parlare di dati con quaranta attributi binari, il numero di possibili esempi supera i mille miliardi — ma il numero dei possibili concetti supera i due-elevato-a-mille-miliardi. Per restringere quello spazio concettuale superesponenziale, dovremmo vedere più di mille miliardi di esempi, prima di poter dire cosa è dentro e cosa è fuori. In effetti, dovremmo vedere ogni possibile esempio.

E attenzione, questo è con quaranta attributi binari. 40 bit, o 5 byte, da classificare semplicemente come “Sì” o “No”. 40 bit implicano 2^40 possibili esempi, e 2^(2^40) possibili concetti che classificano quegli esempi come positivi o negativi.

E così, qui nel mondo reale, dove gli oggetti richiedono più di 5 byte per essere descritti e non sono disponibili mille miliardi di esempi e c’è rumore nei dati da cui dobbiamo apprendere, noi possiamo solo pensare a concetti altamente regolari. Una mente umana — o anche l’intero universo osservabile — non è neanche vagamente abbastanza grande per considerate tutte le altre ipotesi.

Da questa prospettiva, l’apprendimento non solo si basa sul bias di induzione, è praticamente solo bias di induzione — se confronti il numero di concetti eliminati a priori, rispetto a quelli eliminati dalla pura evidenza.

Ma che cos’ha a che fare tutto questo (chiederai) con l’uso corretto delle parole?

È la vera ragione per cui le parole hanno un’intensione oltre che un’estensione.

Nell’articolo di ieri, concludevo:

Il modo per dividere la realtà alle giunzioni naturali, è di definire i tuoi confini intorno a concentrazioni inusuali di densità di probabilità.

In quella affermazione (leggermente modificata) avevo deliberatamente evitato una qualificazione chiave, perché non avevo modo di spiegarla fino ad oggi. Un’affermazione migliore sarebbe:

Il modo per dividere la realtà alle giunzioni naturali, è di definire confini semplici intorno a concentrazioni inusuali di densità di probabilità nello Spazio delle Cose.

Altrimenti creeremmo dei buffi confini non contigui che raccolgono solo gli esempi già visti, esempi che non potrebbero essere descritti con nessun messaggio più breve delle nostre osservazioni stesse, e che dicono: “Questo è quello che ho visto prima e quello che mi aspetto di vedere ancora in futuro”.

Nel mondo reale, niente al disopra del livello delle molecole si ripete esattamente. Socrate ha una forma molto simile a quella di tutti gli altri umani che sono vulnerabili alla cicuta, ma non ha esattamente la loro stessa forma. Quindi l’ipotesi che Socrate sia un “uomo” si basa sul tracciare confini semplici intorno al gruppo degli uomini nello Spazio delle Cose. Piuttosto che, “Cose che hanno esattamente la forma [5-megabyte di specifiche della forma 1] e con [un sacco di altre caratteristiche], o esattamente la forma [5-megabyte di specifiche della forma 2] e [un sacco di altre caratteristiche], …, sono uomini.”

Se non tracci confini semplici intorno alle tue esperienze, non puoi usarle per fare inferenze. Così cerchi di descrivere “arte” con definizioni intensionali come “quello che è fatto per ispirare emozioni complesse per il solo scopo di ispirarle”, piuttosto che limitarti a indicare una lunga lista di cose che sono o non sono arte.

In effetti, la precedente affermazione su “come dividere la realtà alle sue giunzioni naturali” è un po’ uovo-e-gallina: non puoi determinare la densità delle osservazioni, finché non hai fatto almeno un po’ di divisione. E la distribuzione di probabilità deriva dal tracciare i confini, non il contrario — se tu avessi già la distribuzione di probabilità, avresti già quello che serve per generare le inferenze, quindi perché preoccuparsi di tracciare confini?

E questo suggerisce un altro — sì, ancora un altro — motivo per sospettare dell’affermazione che “puoi definire una parola come ti pare”. Quando consideriamo le dimensioni superesponenziali dello Spazio dei Concetti, diventa chiaro che prendere in considerazione un particolare concetto è un atto non poco audace — non solo per noi, ma per qualsiasi mente con una capacità di calcolo limitata.

Presentarci la parola “wiggin”, definito come “una persona con gli occhi verdi e i capelli neri”, senza qualche ragione per sollevare questo particolare concetto all livello della nostra attenzione deliberata, è come un investigatore che dicesse: “Beh, non ho uno straccio di motivo per immaginare chi abbia assassinato quegli orfani… bada bene, neanche un’intuizione… ma abbiamo considerato come sospetto John Q. Wiffleheim che abita in 1234 Norkle Rd?”

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Chaos Legion wants you!