la logica delle classificazioni:
ID3 e il pensiero selvaggio


Un buon esempio, in intelligenza artificiale, di sistema che utilizza la logica delle classificazioni è ID31 di J.R.Quinlan;
ID3 individua delle regolarità, o regole, all'interno di una base dati di partenza; il cuore del sistema è il CLS (Concept learing system), che procede individuando innanzitutto la variabile (o il test, o l'attributo) più discriminante e ripartendo i dati rispetto ad essa.
Una volta che i dati siano suddivisi in 2 sottoinsiemi sulla base della variabile prescelta, ciascun sottoinsieme viene ulteriormente ripartito seguendo un procedimento analogo (a meno che esso contenga esempi di una sola classe); il processo viene ripetuto in maniera ricorsiva finchè ciascun sottoinsieme non contenga dati di un solo tipo.
Il risultato finale è un albero delle discriminanti che può essere usato in seguito per classificare esempi campione non ancora incontrati, e che costituisce la conoscenza che ID3 ha appreso.

ID3

Un esempio dell'applicazione di ID3 potrebbe essere: individuare le nazioni islamiche in base alla loro bandiera nazionale.

In questo caso l'insieme di addestramento contiene circa 70 esemplari di bandiera, 11 dei quali appartengono a paesi islamici; l'albero comincia con il test più significativo, individuando il colore verde come variabile maggiormente discriminante: la presenza o meno del verde nella bandiera suddivide i dati in 2 sottoinsiemi; le variabili discriminanti sono in seguito: la presenza o meno di lune o di qualche simbolo che richiami una luna, la presenza o meno di croci, ecc.;

dati di partenza: 69 bandiere
è presente il verde?
sì: 26 casino: 43 casi
sono presenti lune?sono presenti croci?
sì: 5 casino: 21 casisì: 8 casino: 35 casi
è presente il bianco?il numero di colori è < 3 ?
sì: 10 casino: 21 casisi: 19 casino: 16 casi



Ma come viene scelta la variabile maggiormente discriminante? è sicuramente questo il punto in cui interverrebbe, nel corrispondente comportamento umano in una situazione simile, la vera intelligenza...

Quinlan utilizzò una misura dell'entropia derivata dall'informatica teorica (chiamata fattore di sorpresa) per valutare la capacità discriminante di ciascuna variabile, ma altri ricercatori hanno suggerito misure di tipo diverso come il test del c2.
In entrambi i casi questo costituisce secondo me il maggior limite di ID3;
altre importanti limitazioni sono:

il pensiero selvaggio


La logica delle classificazioni è un potente e fondamentale metodo utilizzato anche dall'intelligenza umana: la ricerca in IA è sempre stata strettamente associata a quella in campo psicologico; lo stesso CLS trae origine dal lavoro di Jerome Bruner e altri psicologi sperimentali (anche se questo è, come sostiene Forsyth17, uno dei rari casi in cui l'IA ha preso in prestito un concetto dalla psicologia e non viceversa).
In questo modo è stato però purtroppo trascurato il contributo che altre scienze sociali potevano portare; mi riferisco in particolare all'antropologia, che può essere paragonata per importanza allo studio dell'apprendimento nella psicologia infantile (es. Piaget), offrendo una visione di società e culture in condizioni non più sperimentabili nella nostra evoluta società industrializzata.

Un testo molto importante in questo senso è Il pensiero selvaggio2 di Claude Levì-Strauss;
in particolare i paragrafi: Alcuni esempi di metodi classificatori, tra i tanti riportati, molto simili a quello utilizzato da ID3, sono quello degli indiani Navaho, degli Hopi, dei Ngarinyin australiani, ecc.: Gli indiani Navaho, che si autodichiarano "grandi calssificatori", dividono gli esseri viventi in 2 categorie, a seconda che siano o no dotati di parola. Gli esseri senza parola comprendono gli animali e le piante. Gli animali sono ripartiti in 3 gruppi: "correnti", "volanti" o "rampanti"; ciascun gruppo, a sua volta, viene nuuovamente bipartito in "viaggianti su terra" e "viaggianti su acqua" da una parte, e "viaggianti di giorno" e "viaggianti di notte" dall'altra. La ripartizione delle specie ottenuta in questa maniera non è sempre identica a quella della zoologia. Avviene così che uccelli raggruppati in coppie sulla base dell'opposizione maschio-femmina, appartengano di fatto allo stesso sesso ma a 2 generi diversi, giacchè l'associazione è fondata per un verso sulla loro grossezza relativa, per l'altro sul posto che essi occupano nella classificazione dei colori e sulla funzione loro assegnata nella magia e nel rituale. 3 Anche gli Hopi classificano gli esseri e i fenomeni naturali per mezzo di un vasto sistema di corripondenze;
si può riassumerne un modesto frammento nella seguente tabella 4:

NORD-OVESTSUD-OVESTSUD-ESTNORD-ESTZENITHNADIR
COLORIgialloazzurro e verderossobianconeromulticolore
ANIMALIpumaorsogatto selvaticolupoavvoltoiserpente
UCCELLIrigogolo"Blue Bird" (Sialia) pappagallogazzarondinecapinera
ALBERIpino di Douglaspino biancosalice rossopioppo
CESPUGLI"green rabbit brush"
(Chrysothamnus)		"sage brush"
(Artemisia) 		"cliff rose"
(Cowania Stansburiana) 		"gray rabbit brush"
(Chrysothamnus)
FIORI"Mariposa lily"
(Calochortus) 		sprone di cavaliere
(Delphinium) 		(Castilleja)(Anogra)
GRANTURCOgialloazzurrorossobiancopurpureozuccherato
FAGIOLIcornetto
(Phaseolus vulg.)		fagiolo burro
(Phaseolus vulg.) 		fagiolo piccolo lima
(Phaseolus lunatus)		diversi

Per i Ngarinyin (come per altre tribù australiana del Kimberley), la classificazione avviene addirittura a livello di linguaggio: essi riconoscono tre successive dicotomie: primo, quello delle cose e degli esseri tra animati e inanimati; poi quella degli esseri animati in razionali e irrazionali; infine quella degli esseri razionali in maschi e femmine. Nelle lingue con sei classi, la classe riservata agli oggetti manufatti comprende tanto il miele quanto le piroghe, perché il primo è fabbricato dalle api, come le altre dagli uomini. É dunque comprensibile che le lingue in cui qualche classe si è perduta, finiscano col raggruppare insieme gli animali e gli oggetti manufatti. 5

É importante notare che "il totemismo è solo un caso particolare del problema generale delle classificazioni, e un esempio tra gli altri della funzione frequentemente attribuita ai termini specifici per elaborare una classificazione sociale." 6


astrazione e interestingness


Il principio logico alla base dei sistemi di classificazione è "di poter opporre dei termini, che un impoverimento preliminare della totalità empirica permette di percepire come distinti. Come opporre è un problema importante, rispetto a questa esigenza fondamentale, ma da prendere in considerazione in seguito.
In altre parole i sistemi di denominazione e di classificazione, che sono comunemente chiamati totemici, derivano il loro valore operativo dal loro carattere formale: sono specie di codici atti a fare da tramite a messaggi convertibili nei termini di altri codici e ad esprimere nel proprio sistema i messaggi ricevuti attraverso il canale di codici differenti." 7

abstraction is information loss?

l'"impoverimento preliminare della totalità empirica" corrisponde all'individuazione di una variabile discriminante nel caso di ID3 (infatti esso permette di "percepire come distinti dei termini" che vengono posti in opposizione); può essere paragonato al processo di astrazione definito in Coding a transhuman AI, parag. 2.3.2: Use of the term "abstract" to describe the process of forming concepts implies two assumptions:
  1. to create a concept is to generalize
  2. to generalize is to lose information
The conventional wisdom states that categorization consists of generalization , and that generalization consists of focusing on particular features at the expense of others. Ma in seguito, a proposito dell'esempio della creazione del concetto di "tre"18: Sure, calling something a three-group, or placing it into the three-category, can be said to "lose" a lot of information: But to label a rich, complex, multi-step act of perception "information loss" borders on perversion. Seeing the "threeness" of a group doesn't destroy information, it adds information. One perceives everything that was previously known about the object, and its threeness as well. Ciò contrasta solo apparentemente con l'"impoverimento" citato da Lévi-Strauss: un impoverimento preliminare11, temporaneo, che non implica una perdita o diminuzione di informazione. [..] crediamo che il fine ultimo delle scienze umane non consista nel costituire l'uomo ma nel dissolverlo.
[..]
Le riduzioni che consideriamo saranno perciò illegittime, e addirittura inattuabili, se non a due condizioni, di cui la prima consiste nel non impoverire i fenomeni sottoposti a riduzione, e nell'avere la certezza che si sia preliminarmente raccolto intorno a ciascuno tutto quel che contribuisce alla sua ricchezza e alla sua originalità distintiva: poichè non servirebbe a nulla impugnare il martello per battere a lato del chiodo.
[..]
La spiegazione scientifica non consiste nel passaggio dalla complessità alla semplicità, ma nella sostituzione di una complessità meglio intellegibile a un'altra che lo era meno. 15
Non solo: l'analisi di Lévi-Strauss va oltre la categorizzazione (che sembra essere attualmente il limite concettuale in IA), e considera quello di specie12 e il processo bidirezionale di universalizzazione e particolarizzazione che portano rispettivamente alla generalizzazione e alla individuazione e denominazione.

La potenza logica dell'operatore specifico può anche essere esemplificata altrimenti. Essa permette di integrare allo schema classificatorio ambiti diversissimi gli uni dagli altri, fornendo così alle classificazioni un mezzo per superare i loro limiti: sia estendendosi, per universalizzazione, ad ambiti posti fuori dell'insieme iniziale; sia prolungando, per particolarizzazione, il procedimento classificatorio oltre i suoi limiti naturali, cioè fino all'individuazione. 13

Come, sul piano logico, l'operatore specifico opera la transizione, da una parte verso il concreto e l'individuale, dall'altro verso l'astratto e i sistemi di categorie, così, sul piano sociologico, le classificazioni totemiche permettono contemporaneamente di definire lo statuto delle persone nell'ambito del gruppo, e di dilatare il gruppo oltre il suo schema tradizionale. 14


interestingness

Il "come opporre" è giustamente definito anche da Levì-Strauss "importante", e anche in questo caso c'è una corrispondenza diretta con il criterio dell'entropia o del c2 scelto da Quinlan.

Nel caso di EURISKO16, invece, "la selezione è attuata dalle meta-euristiche giudicando e determinando quanto è interessante9 una certa euristica. [..]
Per applicare EURISKO alla teoria degli insiemi, per esempio, si potrebbe cominciare col fornirgli alcune euristiche a livello di oggetto rappresentanti i concetti basilari di tale teoria (come l'uguaglianza e l'unione di insiemi), meta-euristiche per creare concetti plausibili a partire dai precedenti (ad esempio, rimuovere una congiunzione da un predicato per indebolirlo), e meta-euristiche per cercare di determinare cosa è matamaticamente interessante (ad esempio, una coincidenza inaspettata)" 8

le diverse interpretazioni possono essere schematizzate in questo modo:

sistemacriteriometodo
CaTAIutilità(?10)astrazione
EURISKOinterestingnesseuristica
ID3fattore di sorpresaclassificazione
Lévi-Strausscome opporre"impoverimento preliminare"


conclusioni

Esiste una forte analogia tra i metodi classificatori esaminati in campo etnologico e quelli adottati in IA; ID3 è probabilmente il sistema per il quale ciò è più evidente, ma lo stesso può essere verificato per molti altri casi; del resto, i tentativi e gli sviluppi in IA sono condotti dagli stessi esseri umani che compongono le società analizzate dagli antropologi, ed è forse naturale che i metodi utilizzati siano molto simili.
Mi rimane, personalmente, un dubbio: che l'IA abbia purtroppo bisogno di ripercorrere ancora alcune tappe di altre discipline "umanistiche" e debba così scontare l'indifferenza prestata ad opere fondamentali come Il pensiero selvaggio, pubblicate quasi 40 anni fa.

note

  1. Semi-autonomous acquisistion of pattern-based knowledge, in Introductory readings in expert systems, 1982, Gordon and Breach ed.;
    risorse e link (ID3 e apprendimento):
  2. La pensée sauvage, 1962., ed. italiana: Il Saggiatore, ISBN 88-04-33569-6, trad. di Paolo Caruso
  3. p.52, cit. da G.A.Reichard, Navaho classification of natural objects, Flagstaff, 1948
  4. p.54, varie fonti;
  5. p.69, cit. da A. Capell, Language and world view in the Northern Kimberley, West Australia, in Southwestern Journal of Anthropology, vol. 16, n.1, 1960
  6. p.74;
  7. p.89;
  8. tratto da Comparative Ecology, di Eric K. Drexler e Mark S.Miller, in Ecology of computation, Bernardo Humberman editore, 1988 (Elsevier Science Publishers, North Holland); v. Ecologia comparata per una mia traduzione;
  9. nell'originale: interestingness
  10. nel caso del progetto CaTAI non mi è molto chiaro quale sia il principio in base a cui individuare i concetti e procedere nell'apprendimento;
    nel seguito dell'analisi del concetto di "tre" si dice comunque:

    "Corresponding-sets" would probably be the first concept formed.
    After that, if it were useful to do so, would come a tendency to categorize sets into classes of corresponding sets, when it was useful to do so; after that would come the selection of a three-exemplar and the concept of three.
  11. preliminare: che precede, che viene fatto in preparazione, che costituisce una premessa necessaria per qualcosa; quindi non necessariamente un atto definitivo.
  12. per capire l'importanza del concetto di specie si potrebbe considerare l'uso del verbo specificare, che si pone a metà strada tra il categorizzare e il denominare (individuare in maniera univoca), tra il nome comune e il nome proprio:
    categoria è: "ciascuna delle classi più generali nelle quali si ordinano e si distribuiscono tutti i nostri concetti; ciascuna delle forme universali secondo le quali l'intelletto costruisce i suoi giudizi" (o meglio: concetti)
    specie è: "insieme di individui con caratteri simili per cui si distinguono dagli altri individui dello stesso genere [..]" (quindi, all'interno della stessa categoria)

    "È quindi chiaro che il problema dei rapporti che intercorrono tra nomi propri e nomi comuni non è quello del rapporto tra denominazione e significato. Si significa sempre o l'altro o se stessi. Questa è la sola possibilità di scelta, un po' come quella data al pittore tra arte figurativa e arte non figurativa; che però è solo la scelta di assegnare una classe a un oggetto identificabile o, mettendo fuori classe l'oggetto, di farne un modo di classificare se stessi esprimendosi attraverso di esso." (p.200)
  13. p. 182
  14. p. 184
  15. p. 269 e seguente
  16. EURISKO, ideato da Douglas Lenat negli anni '80, è tuttora uno dei programmi per l'acquisizione di conoscenza più avanzato;
  17. Richard Forsyth:
  18. anche Marvin Minsky, in Why people think computers can't parla del concetto di "tre": I'm arguing that Three, for us, has no one single, basic definition, but is a web of different processes that each get meaning from the others. Consider all the roles "Three" plays. One way we tell a Three is to recite "One, Two, Three", while pointing to the different things. To do it right, of course, you have to (i) touch each thing once and (ii) not touch any twice.