Data Mining and Decision Trees

Data Mining è il processo di estrarre informazione utile da grandi databases. Per esempio, si consideri un database circa il behavior delle persone che hanno una carta di credito. Esso potrebbe includere registrazioni di pagamento, importi medi di acquisto, tassa sui pagamenti ritardati, saldi medi,… Metodi appropriati di data-mining potrebbero rivelare, tra le altre cose, che le persone con alta commisione sui pagamenti ritardati, alti acquisti medi e altre caratteristiche identificate tendono avere alti saldi medi.

Un importante metodo di data-mining usa i dati per costruire decision trees. Consideriamo un database molto semplice per illustrare come i decision trees funzionano. Supponiamo che una compagnia, diciamo la Wal-Mart, mantiene un database nel quale essa archivia informazione riguardante famiglie alle quali essa ha precedentemente spedito buoni sconto per alcuni dei suoi prodotti. Supponiamo che il database ha informazione riguardante la posizione della famiglia (urbana, suburbana o rurale), il tipo di casa (o ranch o a più piani), se o no la famiglia è un precedente cliente di Wal-Mart, e se o no la famiglia ha risposto ad ognuno dei suoi precedenti della posta promozionale. (Ovviamente, questo è solo un inventato esempio illustrativo; io non so in effetti nulla riguardante il reale database della Wal-Mart).

Una rappresentazione tabulare di questo database potrebbe essere simile a questa:

Household	Location	Type	Customer	Response
3014	suburban	ranch	yes	no
3015	rural	multistory	no	yes
…	…	…	…	…
5489	urban	ranch	yes	no

Ciascuna riga nella tabella è chiamata un “record”. Gli items al top di ciascuna colonna sono chiamati “attributes”, e gli elementi in una colonna sono chiamati i “values” del corrispondente attributo

L’analisi di questo database, con metodi che spiegherò nei prossimi post, potrebbero rivelare che il decision tree ha catturato informazione riguardante quali famiglie hanno risposto alla posta promozionale e quali no. I tests su attribute values sono vicini ai nodi interni dell’albero (in boxes rettangoli) e i risultati (se o no c’era una risposta) sono vicini ai tips (o leaves dell’albero). Questo albero potrebbe essere utile per fare previsioni circa le risposte attese precedentemente per inviare un’ altra mail(ing).

I metodi sono stati sviluppati per costruire (cioè, apprendere) dei decision trees come questo (e anche molto più grande di quelli) automaticamente da grandi databases. Descriverò un po’ della storia e come i metodi principali funzionano.

Decision Trees

Il successivo, sulla mia lista di nuovi sviluppi in ML, è la automatic construction di strutture chiamate “decision tree” da grandi databases. I decision trees consistono di sequenze di tests per determinare una categoria o un valore numerico da assegnare a un data record. I decision trees sono particolarmente appropriati per l’uso con dati non-numerici così come con dati numerici. Per esempio, un database del personale dei dipendenti potrebbe includere informazione riguardante un dipartimento di un impiegato, diciamo, marketing, produzione o contabilità. Nel linguaggio del database, i data items come questi sono chiamati “categorical” (per distinguerli dai numerical data). Nei prossimi posts, descriverò queste strutture, i metodi di apprendimento per costruirli automaticamente e alcune delle loro applicazioni.

Case-Based Reasoning

Un sottoinsieme di AI, chiamato “Case-Based Reasoning” (CBR) può essere visto come un tipo generalizzato di memory-based learning. In CBR una stored library di “cases” è usata per aiutare nell’analisi, nell’interpretazione e nella soluzione di nuovi casi. In medicina, per esempio, i records diagnostici e terapeutici per pazienti costituiscono una letteratura di casi; quando un nuovo caso si presenta, casi simili possono essere retrieved se consultati dalla letteratura per aiutare nella diagnosi e nella terapia. Nella giurisprudenza anglosassone (a differenza di quella di origine romana) la legge si basa su precedenti usati nelle interpretazioni di e nelle decisioni circa nuovi casi (seguendo la pratica legale di stare decisis che affida ad un mandatario quei casi che sono decisi sulla base di una serie di precedenti casi).

Casi che sono simili ad un nuovo caso possono essere pensati considerati come i suoi “neighbors” in uno generalizzato “space” di casi. Per retrieve close neighbors, l’idea di closeness in questo spazio deve essere basata su alcune misure di affinità. Una delle pioniere in case-based reasoning, Janet Kolodner, professoressa di computing and cognitive science al Georgia Institute of Technology, descrive il processo come segue:

Good cases [per retrieval il recupero] sono quelli che hanno il potenziale per fare rilevanti revisioni circa il nuovo caso. Il recupero è fatto usando caratteristiche del nuovo caso come indici all’interno della raccolta del caso. I casi etichettati da sottoinsiemi di quelle caratteristiche o dalle caratteristiche che possono essere derivate da quelle caratteristiche sono richiamati [Noi poi allora selezioniamo tra questi] il più promettente caso o casi per arguire logicamente ….Talvolta è appropriato scegliere il caso migliore; talvolta uno ridotto insieme è necessario.

Quando il caso retrieved (o i casi) è adattato ad essere applicato ad un nuovo caso esso potrebbe poi (se ha avuto successo) essere rivisto cosicché le parti che potrebbero essere utili per la soluzione di problemi futuri possono essere conservate nella sempre crescente raccolta dei casi.

Il case-based reasoning ha radici nel modello di memoria dinamica di Roger Schank. Il primo lavoro fu fatto da due Ph.D. studenti di Schank, Janet Kolodner e Michael Lebowitz. Un’altra importante fonte di idee per CBR deriva dalle idee di Minsky circa i frames. Edwina Rissland, professoressa alla University of Massachusetts ad Amherst e un’altra pioniera in CBR, scrive che il suo lavoro sul CBR è una diretta conseguenza del di lei lavoro su ‘constrained example generation’,…che ha modellato la costruzione di nuovi esempi dalla modificazione di esistenti esempi ‘close’ passati (rappresentati come frames) recuperati da una network di esempi”. Rissland e i suoi studenti hanno dato importanti contributi all’uso di CBR in giurisprudenza.

Secondo una pagina web mantenuta dall’Artificial Intelligence Applications Institute alla University of Edinburgh, “Case-based Reasoning è una delle tecnologie di AI applicate con maggior successo nei recenti anni. Applicazioni commerciali e industriali possono essere sviluppate rapidamente ed esistenti databases aziendali possono essere usati come knowledge sources (Kss). Helpdesks e sistemi diagnostici sono le più comuni applicazioni.”

Memory-Based Learning

L’usuale approccio in AI di trattare ampi quantitativi di dati è di ridurre l’ammontare di essi in qualche modo. Per esempio, una rete neurale è capace di rappresentare quello che è importante circa un ampio ammontare di training data dalla struttura della network e i weight values. Similmente, apprendere una Bayesian network da dati riduce questi dati all’interno di una struttura di nodi della network e le sue conditional probability tables (CPTs).

Tuttavia, le nostre crescenti abilità di memorizzare ampi quantitativi di dati in memorie di computer in accesso rapido e di computare con questi dati ha attivato tecniche che memorizzano e usano tutti i dati come essi sono necessari – senza alcuna precedente sintesi qualunque. Cioè, queste tecniche non tentano di ridurre l’ammontare di dati prima che sia in realtà usato per qualche task. Tutta la necessaria riduzione, per esempio per una decisione, è eseguita al momento in cui una decisione deve essere presa. Descriverò alcuni di questi metodi di learning memory-based successivamente.

Ho già menzionato i metodi “nearest-neighbor” per classificare un punto in uno spazio multidimensionale. La “k-nearest-neighbor rule”, per esempio, assegna un data point alla stessa categoria come quella della maggioranza dei k-stored data points che sono i più vicini ad esso. Una tecnica simile può essere usata per associare un valore numerico (o insieme di valori) ad un data point. Per esempio, la media dei valori memorizzata associata con il k-nearest neighbor può essere assegnata al nuovo point. Questa versione della regola può essere usata in applicazioni di controllo. La regola k-nearest-neighbor è un prototipico esempio di memory-based learning ed essa suggerisce molte questioni domande circa possibili estensioni.

Primo, per applicare la regola nearest-neighbor, ciascun dato deve essere una lista di numeri – un punto o un vettore in uno spazio multidimensionale. Così, una domanda è “Come rappresentare i dati così che qualcosa come il metodo nearest-neighbor può essere applicato?” Secondo, quanta è la “distance” che deve essere misurata tra data points? Quando, se i dati sono rappresentati da punti in uno spazio multidimensionale, la distanza euclidea è la scelta naturale. Persino in questo caso, tuttavia, è usuale “scale” le dimensioni così che undue weight non necessario non è dato a quelle dimensioni per le quali i dati sono più “spread out”. Se i dati non sono rappresentati come punti in uno spazio, un altro modo di misurare i dati è la “closeness”. Molti metodi sono stati proposti che dipendono in funzione della forma dei dati.

Terzo, tra i k-closest data points, quelli più vicini dovrebbero condizionare il risultato di più rispetto a quelli distanti? Il metodo base k-nearest-neighbor può essere esteso ponderando by weighting l’importanza di data points in una maniera modo dipendente in funzione della loro closeness. Usualmente, un “kernel” è usato che dà un weight gradualmente in diminuzione a data points che sono sempre più lontani.

Quarto, quale sarebbe il valore di k? Quanti nearby neighbors stiamo per usare nel prendere la nostra decisione circa un nuovo piece di dati? Ebbene, con il giusto tipo di kernel, all i data points possono essere considerati. Quelli che sono più lontani avrebbero semplicemente zero o un influsso trascurabile sulla decisione. La domanda circa quale valore di k usare è ora sostituita dalla domanda circa quanto lontano l’influsso del kernel sarebbe esteso.

Infine, dopo che tutti i weighted neighbors sono considerati, come facciamo noi a prendere una decisione o assegnare un valore o valori numerici? Sarebbe lo stesso come quello associato con una majority vote dei neighbors o forse con “average” dei weighted neighbors? Varie versioni di quelli che sono chiamati statistical regression methods possono essere implementati in funzione di questa scelta.

Andrew W. Moore e Christopher G. Atkeson sono tra i pionieri nello sviluppo di estensioni alle regole k-nearest-neighbor e l’applicazione di queste estensioni a molti importanti problemi in data mining e in robot control.

Oltre alle applicazioni in robotica e in control, i metodi di apprendimento memory-based learning sono stati usati anche in altre aree includendo data mining e NLP.

Machine Learning

Le tecniche automatizzate di raccolta-dati, insieme a un economico apparato di conservazione della memoria di massa, hanno consentito l’acquisizione e il mantenimento di prodigiosi quantitativi di dati. Punto di vendita/acquisti di clienti, letture di temperatura e pressione (insieme ad altri dati sul meteo), nuovi feeds, transazioni finanziarie di tutti i tipi, pagine Web e records di interazione Web sono solo alcuni di numerosi esempi. Ma il grande volume di dati grezzi (unprocessed) richiede tecniche efficienti efficaci di “data-mining” per classificare, quantificare ed estrarre informazione utile. I metodi di Machine Learning stanno giocando un crescente importante ruolo nella data analysis perché essi possono trattare enormi quantitativi di dati.

La maggior parte dei metodi di ML costruiscono ipotesi da dati. Così (per usare un classico esempio), se un ampio insieme di dati contiene molte istanze di cigni che sono bianchi e nessuna istanza di cigni che sono di altri colori, allora un algoritmo di una ML potrebbe fare l’inferenza che “all swans are white”. Questa inferenza è “inductive” piuttosto che “deductive”. Le inferenze deduttive seguono necessariamente e logicamente dalle loro premisses, mentre invece quelle induttive sono ipotesi che sono sempre soggette a falsificazione con dati aggiuntivi. (Ci potrebbe essere ancora un’isola non scoperta di cigni neri). Inoltre, inferenze induttive, basate su ampi quantitativi di dati, sono estremamente utili. Infatti, la scienza stessa è basata su inferenze induttive.

Mentre, prima del 1980, ML (rappresentato principalmente da metodi di neural network) era considerato da alcuni come ai margini di AI, ML è recentemente diventato molto più centrale nella moderna AI. Ho già descritto un esempio, cioè, l’uso di Bayesian networks che sono automaticamente costruite da dati. Altri sviluppi, iniziati intorno agli anni ottanta, hanno reso il ML uno dei più prominenti rami di AI.

Temporal Bayesian Networks

Gli esempi di Bayesian Networks illustrati nell’ultimo post, insieme a quelle più ampie usate in molte applicazioni, sono ciò che si potrebbe chiamare “static”. Cioè, le proposizioni e le quantità rappresentate dai nodi e dalle CPTs sono senza tempo nel senso che esse trattano lo stesso istante nel tempo (o tutti i momenti nel tempo). Inoltre io ho già descritto una probabilistic network che implica quantità, differenti volte, cioè, gli hidden Markov models. Ho già spiegato come gli HMMs erano usati in speech recognition. Una particolare HMM è chiamata un first-order Markov process perché ciascuno stato dipende solo dall’immediatamente precedente stato. In processi di ordine più alto, ciascuno stato è condizionato da più di un precedente stato.

In una HMM network, ciascun x_i, è una “state variable” e gli y_i sono “observable variables”. È stato ipotizzato che i valori degli stati sono unknown (cioè , “hidden”) ma che le observables possono essere misurate e così conosciute. Ciascuno stato causa un’associata osservabile e il successivo stato. Noi ipotizziamo che conosciamo le CPTs della network, cioè, le probabilities delle observables e lo stato successivo dato il valore di uno stato. Dato il valore di uno o più observables, noi possiamo calcolare aggiornate updates probabilities di stati usando ognuno dei metodi per computing probabilities in una Bayesian Network.

Ecco un esempio. Supponiamo un aircraft, le condizioni meteo in un aeroporto remoto siano o con nebbia o senza nebbia. Un sensore all’aeroporto registra il meteo e un trasmettitore invia un segnale ogni cinque minuti. Questo segnale, quando esso è ricevuto da un aeroplano che sta tentando di atterrare all’aeroporto, potrebbe occasionalmente essere in errore. Così, gli stati, cioè, gli x nel HMM modeling di questo processo, possono avere valori di 1 o 0, con un valore di 1 che indica nebbia. I segnali sono ricevuto dall’aircraft, gli y nei HMM, anche hanno valori di 1 o 0, con un valore di 1 che indica nebbia è stato osservato. Ma le osservazioni potrebbero essere in errore. Per essere concreti, supponiamo la probabilità che il successivo stato abbia lo stesso valore come quello del presente stato è 75% (nebbia tende a persistere) e la probabilità che una osservabile è in errore è 5%. Queste probabilities consentono la costruzione di CPTs di Bayesian Network. (L’esempio può essere reso più realistico consentendo ciascuno stato per evidenziare gradi di nebbiosità e per dipendere da stati in aggiunta al singolo precedente stato).

Il pilota di un aircraft aeroplano deve make a decision (prendere una decisione) circa il tentare di atterrare o non basato sulla sequenza di y ricevuti. Per esempio, egli o ella potrebbero voler conoscere la probabilità che la landing strip è foggy proprio ora basata su una sequenza di precedenti osservazioni e includendo quello presente. Nel linguaggio degli HMM, l’operazione che calcola questa probabilità è chiamata “filtering”. Alternativamente, il pilota potrebbe voler computare la probabilità che la pista di atterraggio sarebbe stato nebbioso 10 minuti da ora basato su queste osservazioni. Questa operazione è chiamata “prediction”. Sebbene non sarebbe di molta utilità per il pilota, lui o lei potrebbero essere curiosi circa la probabilità che la pista di atterraggio era nebbioso 10 minuti prima basato su una sequenza di osservazioni e includere la presente. Questa operazione è chiamata “smoothing” (appianamento).

Nella mia discussione di speech recognition, ho menzionato che gli HMM stati corrispondono a singole parole e che le osservazioni corrispondono a segmenti di forme d’onda. In questa applicazione noi vogliamo computare la più likely/probabile sequenza di parole date tutte le osservazioni di forme d’onda fino al presente.

Tutte queste computazioni – filtering, prediction, smoothing e most-likely-state sequence – possono essere eseguite usando Bayesian Network inferences procedures. Ci sono molte specializzate versioni, alcune delle quali originate in campi al di fuori di AI. Questo dipende dall’applicazione e dai particolari delle networks implicate.

Di queste, io potrei menzionare l’algoritmo forward-backward, il Viterbi algoritmo e il Kalman filtering. Il lettore coraggioso matematicamente può trovare chiare spiegazioni nell’eccellente textbook di Russell e Norvig. Il fatto che piene spiegazioni implicano una piuttosto complicata matematica testimonia ancora il grande incremento nella profondità tecnica di AI che iniziò negli anni ottanta.

Gli HMMs, includendo il mio esempio foggy not-foggy, hanno una singola variabile di stato a ciascun istante di tempo. È possibile costruire networks nelle quali ci sono più variabili di stato ad ogni istante di tempo – tutti quelli che hanno influsso su ciascun altro, le osservazioni e successive variabili di stato. Queste sono tipicamente chiamate “Dynamic Bayesian networks” (DBNs) e furono per la prima volta esplorate in AI da Thomas Dean e Keiji Kanazawa. Additional state e observation variables rendono esatte le computazioni intrattabili, ma molti metodi pratici di approssimazione, come “particle filtering” (che descriverò in più dettagli successivamente) sono stati sviluppati. E, proprio come con le ordinary Bayesian Networks, le Dynamic Bayesian networks possono essere apprese da databases contenenti informazioni riguardanti processi temporali. Esse sono state usate in molte applicazioni, principalmente frame-to-frame dependencies possono essere sfruttate per riconoscere e localizzare oggetti che si muovono. Un’altra è nella certificazione di sistemi per evitare la collisione per aeroplani con equipaggio e senza equipaggio.

Sebbene questo capitolo è stato riguardante le Bayesian Networks, esse sono solo un tipo di un importante classe chiamata “probabilistic graphical models”. I Markov random fields, spesso chiamati Markov networks, sono un altro membro di quella classe nella quale i links tra nodi sono nondirectional. Essi erano originariamente stati sviluppati per trattare problemi in fisica statistica, ed essi ora trovano applicazioni in molte aree includendo image processing, sensory perception e brain modeling. Le Boltzmann machines sono esempi di Markov random fields. Ci sono anche modi per interpretare altre neural networks come esempi di probabilistic graphical models.

Probabilistic Relational Models

Un’importante elaborazione delle Bayesan networks, chiamata “ Probabilistic Relational Models” (PRMs), è stata sviluppata dalla professoressa di Stanford Daphne Koller, insieme con gli/le di lei studenti Avi Pfeffer e Lise Getoor e un collaboratore, Nir Friedman (ex studente alla Stanford e ora professore alla Hebrew University). I PRMs integrano probability con il predicate calculus. [Un precedente lavoro sul combinare queste due forme representational fu fatto da molti ricercatori, in particolare da David Poole alla University of British Columbia]. I PRMs exploit sfruttano il fatto che alcuni nodi in una network potrebbero condividere gli stessi attributi eccetto per i valori di variabili interne a quegli attributi ( molto simile al fatto che nel predicate calculus lo stesso predicato potrebbe essere scritto con differenti valori per le sue internal variables).

Per esempio, una network che mostra che una persona ha un tipo di sangue e informazione cromosomica che dipendono dai cromosomi ereditati dai di lui o di lei genitori avrebbe ripetuto subnetworks. In questo caso, un singolo “template” è usato per realizzare differenti subnetworks le cui attribute variables sono istanziate per differenti individui. Usare i PRMs rende il progetto di Bayesan networks molto più efficiente rispetto a come sarebbe il processo di dover progettare ciascuna (solo leggermente un po’ differente) subnetwork separatamente. Koller dice che lei era motivata a pensare circa i PRMs in una conversazione con uno studente che doveva convertire una Bayesan network modeling modellando una three-lane freeway a tre corsie in un modeling a four-lane freeway. Ella ricorda dicendo”…ma questo è solo aggiungere un corsia in più, sicuramente tu puoi riusare un po’ della struttura”.

La struttura e le CPTs di un PRM possono o essere specificate da un progettista o apprese dai data. Un benefit aggiunto dei PRMs è che oggetti risultanti dall’istanziare template variables possono essere connessi nella risultante Bayesian network; relazioni tra questi oggetti possono essere specificate by hand o appresi. Come con ogni Bayesian network, le probabilistic inference procedures possono essere usate per answer queries circa le probabilities di alcuni nodi, date quelle di altri.

I PRMs e strutture correlate sono stati usati in una varietà di applicazioni, includendo una per recovering regulatory networks di dati di espressione genica.

Come per quanto riguarda le Bayesian networks in generale, ci sono da ora molte, molte applicazioni. Per dare un flavor della loro varietà, menzionerò il loro uso in genomic studies, in automobile traffic forecasting and routing, in modeling disease outbreaks e nell’indovinare le successive azioni di un utente di un computer per rendere il sistema operativo Windows una “prefetch” application data in memoria prima che sia ad esso domandato. Ci sono anche compagnie che vendono knowledge-capturing e reasoning systems basati su Bayesian networks.

Una cosa che tutte queste applicazioni ci hanno insegnato è l’importanza di impressionanti quantità di data che Peter Norvig, il co-autore del principale libro di testo di AI e Director of Research at Google, ha dimostrato per essere il tema maggiore della moderna AI. Infatti, Norvig affermò che Google è il sistema di AI più grande nel mondo.

Automatic Construction of Bayesian Networks

Una delle ragioni perché le Bayesian Networks sono diventate così importanti è che esse possono essere automaticamente costruite da ampi databases. Cioè, esse possono essere “learned” e le apprese versioni possono essere usate per ragionare circa l’argomento in questione. Due dei pionieri in questo sviluppo di questi learning methods furono Greg Cooper e Edward Herskovits. L’argomento continua ad essere un’attiva area di ricerca e ci sono molti altri che hanno dato significativi contributi.

Ecco, in termini generali, come funziona il processo. L’apprendere una network implica l’apprendere la struttura della network, cioè la disposizione dei suoi nodi e dei collegamenti connessioni e anche le CPTs della network. Spiegherò come le CPTs per una nota struttura possono essere apprese e successivamente come la struttura stessa può essere appresa, sebbene i due processi sono realmente interconnessi. Consideriamo ancora la Bayesian Network a quattro nodi per il motore dell’automobile. Come potremmo noi apprendere le CPT per il nodo P4 (cioè, Car Starts) – i cui unici genitori sono P2 (cioè, Car Cranks) e P3 (cioè Fuel System OK) Usando le mie abbreviazioni per quelle proposizioni, la CPT è composta per le seguenti conditional probabilities:

p(P4 | P2, P3),

p(P4 | P2, ¬P3),

p(P4 | ¬P2, P3)

p(P4 | ¬P2, ¬P3)

Se noi avevamo una ampia collezione di campioni di situazioni nelle quali l’auto talvolta parte e talvolta no, nelle quali l’auto talvolta cranks e talvolta no, e in quali il fuel system sistema di alimentazione talvolta era ok e talvolta non lo era, noi potremmo usarli per tabulare ciò che sono chiamati “sample statistics”. Per esempio, noi potremmo notare il numero di volte in questi campioni in cui l’auto è partita quando l’auto did not cranck e il fuel system sistema di alimentazione era ok e dividere quel numero per il numero totale di volte in cui l’auto did not cranck e il fuel system sistema di alimentazione era ok. Questa frazione potrebbe essere usata come una stima di p(P4 | ¬P2, P3). Noi potremmo fare simili stime delle altre tre possibilità e simili stime per le probabilities nelle altre CPTs nella network. Con una sufficientemente ampia collezione di campioni, queste stime sarebbe state ragionevolmente attendibili: maggiore è il numero di campioni, migliori sono le stime.

La raccolta di sample statistics (talvolta aumentati da alcune aggiuntive computazioni che qui tralascio) fornisce un metodo per stimare le CPTs di una network con known structure. Ora, come potremmo noi apprendere le strutture di una unknown network? Il metodo ha come conseguenza la seguente sequenza di passaggi (algoritrmo) :

1. Partire con una qualche struttura candidata di base, come quella che non ha connessioni tra nodi e usare la data collection per stimare le sue CPTs (Ricordo che la CPT di un nodo senza genitori è just la unconditional probability per quel nodo. Esso può essere stimato dalla frazione di volte la sua associata proposizione è vera nel data set)

2. Calcolare una “goodness measure” per questa network. Una delle proposte misure è basata su quanto bene la network con le sue calcolate CPTs, potrebbe essere usata per trasmettere (cioè, rigenerare) l’originaria data collection

3. Iniziare un processo di ricerca “hill-climbing” valutando “nearby” networks che differisce da una precedente per piccoli cambiamenti (che potrebbero implicare l’aggiunta di un arco, cancellarne uno che è già lì e scambiare i nodi). Per valutare le networks cambiate, sono calcolate le loro CPTs e la goodness. Decidere per la network cambiata con il migliore improvement in goodness.

4. Continuare il processo di hill-climbing finché nessuno più improvements può essere fatto (o finché qualche predefinito stopping criterion è incontrato)

Sebbene questo processo appare (per) essere assolutamente tedioso (ed esso lo è), i computers possono eseguire questo processo di hill-climbing in modo ragionevolmente efficiente e piuttosto complicate networks sono state apprese.

Talvolta la struttura di una network può essere semplificata sostanzialmente aggiungendo nodi per la network che rappresenta attributi che non occorrono nel data set. I metodi con i quali la network apprende sono stati estesi per essere capaci di apprendere ad installare “hidden nodes”che rappresentano questi attributi inventati. Attributi inventati dai data sono spesso utili per deepening la nostra comprensione dei fenomeni che diedero origine ai data.

Representing Probabilities in Networks

Bayesian Networks

Molto del reasoning umano è circa le proposizioni e le quantities che sono incerte/uncertain. Le nostre opinioni/beliefs circa molte cose sono provisional/provvisorie (cioè, soggette a cambiare) e qualified/condizionate (cioè, che hanno vari livelli di confidence/fiducia). Anche i sistemi di AI, necessitano di essere capaci di trattare uncertain information/informazione incerta. I fatti, le statements/proposizioni e le regole di un agente AI dovrebbero essere più appropriatamente per essere pensati come provisional/provvisori e qualified/condizionati. Dopo tutto, una parte della sua informazione è fornita da umani e una parte originata da sensori con precisione e reliability/ affidabilità limitate. Eppure, molto del primo lavoro in AI ha ignorato la natura uncertain/incerta della conoscenza. Infatti, Marvin Minsky osservò che il suo volume edito dei primi articoli su AI non conteneva “alcun esplicito uso di nozioni probabilistiche”.

Attualmente molti ricercatori di AI, tuttavia riconoscono che molta della conoscenza necessaria per le macchine necessita di essere qualified/condizionata con valori di probabilità e che questo reasoning con questa conoscenza può quindi più appropriatamente essere fatto con gli strumenti/tools della probability theory. Ma proprio come è il caso con il logical reasoning, il probabilistic reasoning è soggetto alla vecchia nemesi di AI, la combinatorial explosion. Supponiamo, per esempio, che la conoscenza di un agent consiste di un insieme di proposizioni. A causa di possibili interdipendenze tra le proposizioni, un accurato probabilistico reasoning dipende dal/è in funzione del conoscere più che appena solo la probabilità di ciascuna di quelle proposizioni individualmente. Invece, i valori di probabilità per varie combinazioni delle proposizioni prese insieme, chiamate “joint probabilities” sono usualmente richieste; questo conduce nel caso generale, a impraticabilmente ampie rappresentazioni e computazioni intrattabili/intractable.

I precedenti sistemi di AI che potrebbero trattare l’incertezza/uncertainty, come MYCIN e PROSPECTOR, fanno semplificare assumptions/ipotesi per diminuire queste difficoltà rappresentazionali e computazionali. Tuttavia, poiché questi sistemi fallirono nel considerare importanti interdipendenze tra le loro convinzioni, essi spesso diedero risultati inappropriati dovuti a causa di queste come la sovrastima dell’evidenza. Durante gli anni ottanta alcuni nuovi metodi potenti furono inventati (e importati da altri campi) che erano meglio capaci di trattare le dependencies/dipendenze. Essi involve/implicano il rappresentare uncertain beliefs/opinioni incerte e le loro dependencies in una forma grafica chiamata un “probabilistic graphical model”. Descriverò la più importante versione di questi modelli in questo post.

Primo, per illustrare alcune delle difficoltà involved/implicate in reasoning circa uncertain beliefs/opinioni incerte e come noi potremmo trattarle, guardiamo un esempio involving/che implica varie proposizioni circa un motore di automobile. Ecco alcune delle cose che potremmo dire circa un motore e i suoi componenti:

P1: The starter motor is ok

P2: The starter motor cranks the engine when the starter switch is turned on

P3: The fuel system is ok

P4: The car starts when the starter switch is turned on.

Queste proposizioni sono assolutamente ovviamente correlate. Per una cosa, P4 dipende dalle altre tre – la triste osservazione che P4 è falsa certamente cambierebbe la nostra fiducia circa le altre tre. Inoltre, non richiederebbe un meccanico di auto per conoscere sapere che P1 e P2 sono correlate.

Una piena considerazione delle dependencies implicate qui richiede un elenco di tutte le possibilità per cose che sono ok e non ok e ci sono sedici di queste possibilities/possibilità. Se noi denotiamo l’opposto di una proposizione inserendo un segno di negation (¬) premesso ad esso, allora ¬P1 denota “The starter motor is not ok”. Usando questa notazione, le sedici possibilities/ possibilità sono

P1, P2, P3, P4,

P1, P2, P3, ¬P4,

P1, P2, ¬P3, P4,

P1, P2, ¬P3, ¬P4,

P1, ¬P2, P3, P4,

P1, ¬P2, P3, ¬P4,

P1, ¬P2, ¬P3, P4,

P1, ¬P2, ¬P3, ¬P4,

¬P1, P2, P3, P4,

¬P1, P2, P3, ¬P4,

¬P1, P2, ¬P3, P4,

¬P1, P2, ¬P3, ¬P4,

¬P1, ¬P2, P3, P4,

¬P1, ¬P2, P3, ¬P4,

¬P1, ¬P2, ¬P3, P4,

e

¬P1, ¬P2, ¬P3, ¬P4.

Un esperto che conosce i motori e le loro attese/expected reliabilities/affidabilità sarebbe, presumibilmente, capace di assegnare valori di probabilità a ciascuno di questi sedici “states” nei quali un engine system potrebbe trovare se stesso. Per esempio, l’esperto potrebbe specificare che la overall/complessiva joint probability/probabilità congiunta che ogni cosa è ok, denotata da p(P1, P2, P3, P4) è 0,999. Egli o ella dovrebbe specificare questi sedici numeri. (In realtà solo quindici dovrebbero essere necessari. Questi sono i soli possible states/possibili stati e uno di essi deve essere il caso.) Knowing/sapere conoscere queste joint probabilities/probabilità congiunte renderebbe capace una persona (che possegga pazienza e capacità nella probability theory) di a calcolare altre probabilities/probabilità certain/certe, come la probabilità che la macchina parte dato solo, diciamo, che il fuel system/il sistema di alimentazione è sicuramente ok.

Specificare i quindici numeri per questo piccolo esempio non sembra troppo arduo, ma per un più realistico problema, diciamo uno con trenta differenti proposizioni, si dovrebbero specificare 2³⁰-1 = 1073741823 numeri. Inoltre, se ci sono anche quantità che potrebbero considerare molti valori ( in aggiunta a proposizioni, che sono binary-valued), il numero di possibilities si espande ancora di più.

Ovviamente, io ho ipotizzato/assumed qui il caso peggiore/the worst case, in altri termini, il caso in cui tutte e quattro le proposizioni potrebbero dipendere in modi complessi complicati indipendentemente da ciascun altro. Poi ciascuna delle sedici probabilities potrebbero essere computate calcolate da formule come

p(P1, P2, P3, P4) = p(P1)p(P2)p(P3)p(P4)

(con i segni ¬ inseriti come richiesto), e noi avremmo necessità solo per specificare probabilities per ciascuna delle quattro proposizioni individualmente.

Il mio esempio riguardante i motori di automobile è in effetti un po’ tra questi due estremi. Così anche ci sono molto più ampi e più realistici problemi. Questa “inbetweeness” è la chiave per rendere il probabilistic reasoning più tractable/trattabile. Sebbene c’era un precedente recognition/ riconoscimento e exploitation/sfruttamento di questo fatto da statistici, fu Judea Pearl che ha sviluppato alcuni dei principali metodi representational e computational.

Pearl, un professore di informatica alla UCLA, era perplesso del contrasto tra, da una parte, la ease/facilità con cui gli umani ragionano e make inferences/fanno inferenze basate su uncertain information/informazione incerta e, dall’altra, le difficoltà computazionali di duplicare queste capacità abilità di usare calcoli basati sulla probability. Come egli disse, egli iniziò con le seguenti conjectures/congetture:

1. The consistent agreement/La consistente accettazione tra plausibile reasoning/il ragionamento plausibile [da parte degli umani] e il calcolo della probabilità potrebbe non essere una coincidenza ma fortemente suggerisce che l’intuizione umana invoca qualche forma grezza/some crude form di probabilistic computation/calcolo probabilistico.

2. Alla luce della velocità e effectiveness/efficacia del reasoning, le difficoltà computazionali che affliggevano i precedenti sistemi probabilistici potrebbero non essere molto fondamentali e dovrebbero essere superate dal fare la scelta/choice giusta di semplificare le assumptions/ipotesi che gli umani memorizzano/store nella loro head.

L’intuizione fondamentale di Pearl fu che beliefs/le opinioni circa proposizioni e altre quantità potrebbero spesso essere considerate come “direct causes” di altre beliefs e che questi causali collegamenti/causal linkages potrebbero essere rappresentati in strutture grafiche che codificano semplificando le assumptions/ipotesi circa relazioni tra probabilities.

Per essere chiari, Pearl non fu il primo a suggerire di usare strutture grafiche per codificare la probabilistic information. Egli stesso menziona il precedente lavoro. Russell e Norvig scrissero che il lavoro dello statistico inglese I. J. Good “potrebbe essere considerato come un precursore delle moderne Bayesian networks…” E i fisici fanno risalire strettamente il correlato lavoro di Hans A. Bethe.

Per il nostro esempio del motore dell’automobile, invece di quindici probabilities che sarebbe necessarie nel caso generale, ora noi necessitiamo solo di otto. Queste sono come segue: le

probabilities di P4 dati P2 e P3 per i quattro differenti stati di P2 e P3,

p(P4 | P2, P3),

p(P4 | P2, ¬P3),

p(P4 | ¬P2, P3),

p(P4 | ¬P2, ¬P3);

la probabilità di P2 dato P1 per i due differenti stati di P1, cioè, p(P2|P1) e p(P2|¬P1); e le probabilità di P1 e P3, cioè, p(P1) e p(P3). Ciascuno di questi insiemi di valori di probabilità è stored/memorizzato in quella che è chiamata una “conditional probability table” (CPT) associata al suo corrispondente nodo nella rete.

Usando un risultato dalla teoria della probabilità tutte e sedici le joint probabilities/ probabilità congiunte (richieste per un accurate probabilistic reasoning) possono essere computato da queste otto.

Poiché la regole di Bayes gioca un ruolo prominente nel computare le probabilità dei vari nodi date le probabilità degli altri, Pearl ha coniato la frase “Bayesian belief networks” (usualmente semplificata in Bayesian networks o belief networks) per questi tipi di grafi. È stato dimostrato che è piuttosto facile costruire ampie Bayesian networks notando attentamente quali proposizioni direttamente influenzano (“cause”) le altre. Networks così costruite sono quelle che i graph theorists chiamano “directed acyclic graphs” (DAGs): “directed” perché le frecce point/puntano da cause nodes/nodi nodi causati e “acyclic” perché seguendo le frecce fuori da un nodo non conducono mai indietro a quello stesso nodo.

Ci si potrebbe chiedere, da dove i valori di probabilità nelle CPTs arrivano? Per alcune networks, forse un esperto che conosce come certain proposizioni affect/hanno effetti su altre potrebbe essere capace di make guesses/fare supposizioni circa le probabilities. Queste guesses/ supposizioni sono chiamate “subjective probabilities”, basate come esse sono nozioni/notions subjective di un esperto riguardanti causa ed effetto. Tuttavia, di gran lunga il metodo più utile per populating le CPTs con valori è stimarli da un ampio database di casi reali.

Da qualsiasi mezzo esse sono ottenute, le CPTs (insieme con la struttura della network) sono usate in computazioni riguardanti come le probabilità di alcuni nodi nella rete sono affected/influenzate dalle probabilità degli altri. Queste computazioni sono chiamate “probabilistic inference”. Vari metodi computational pratici sono stati ideati – anche per le piuttosto ampie networks necessarie per problemi realistici reali.

Senza esaminare ogni effettiva computazione, userò la piccola network del motore per illustrare tre principali stili di probabilistic inference in Bayesian networks. Per esempio, se tutti noi sapevamo per certo che era che the starter motor was ok [cioè, p(P1)=1)], noi potremmo computare la probabilità che the car will start. “Migrating” i valori di probabilità noti downward verso il basso nella network (nella direzione delle frecce) è usualmente chiamata “causality reasoning”. Invece, se noi sapevamo che l’auto non sarebbe partita [cioè, p(P4)=0], noi potremmo computare le probabilità del starter motor/motorino di avviamento che è ok e del fuel system/sistema di alimentazione che è ok. I valori di probabilità di Migrating upward verso l’alto nella rete (contro la direzione delle frecce) è usualmente chiamata “evidential” oppure “diagnostic” reasoning. Esso è quello che i medici (e altri trouble-shooters/tecnici riparatori) fanno quando essi hanno un sintomo e tentano di inferire le probabilità delle cause.

C’è un altro anche importante stile di reasoning e che è chiamato “explaining away”. Ecco un esempio: Supponiamo che noi sappiamo di sapere che l’auto non parte e che noi abbiamo computato i valori di probabilità per il fuel system/sistema di alimentazione che è il problema (cioè, non ok) e per il starter motor/motorino di avviamento che è il problema. Poi successivamente, noi troviamo che in effetti lo starter motor ha, infatti fallito. Considerando questa aggiuntiva informazione, noi potremmo trovare che la probabilità del fuel system che è il problema decrescerebbe. Il problema del starter motor “explains” il fatto che l’auto non partirebbe, così noi abbiamo meno ragione per sospettare del fuel system. Il fatto che il starter motor non parte “explains away” il possibile problema del fuel system. La strategia per explaining away è comunemente usata in medicina, diritto, scienza e nel ragionare quotidiano. Per esempio, un defense attorney/avvocato difensore potrebbe citare l’evidenza che alcune altre persone (non il suo cliente) era identificato sul sistema di monitoraggio TV della banca, explaining away così il coinvolgimento del suo cliente nella rapina in banca.

Io posso illustrare l’effetto explaining-away con effettivi inference calculations eseguiti su una rete un po’ più ampia network circa i motori. Dopo aver osservato che l’auto non parte , la probabilità che lo starter motor è il problema è computato per essere 0,023 (usando le CPTs della rete network) e la probabilità che il fuel system sia il problema è computata per essere 0,283. Ma inoltre osservare che il starter motor ha fallito, la probabilità che il fuel system è la causa del problema fa diminuire da più di metà a 0,1.

Se noi volessimo costruire una Bayesian network circa un motore di automobile che era più realistico reale e utile, noi dovremmo menzionare molte più componenti e sottosistemi. Questa network potrebbe contenere centinaia di nodi insieme alle loro associate CPTs. Anche se conditional independencies ridurrebbero il numero di individuali singole probabilità che necessitano di essere specificate, ancora il loro numero può essere così ampio che esatte probabilistic inferences sarebbero ancora computationally intrattabili – ipotizzando che i valori per queste probabilità potrebbero anche persino essere gathered/raccolti. Fortunatamente, varie semplificazioni sono possibili che permettono ulteriori riduzioni nel numero di probabilità necessarie. Con esse, computazioni per approssimazione, ma ancora utili, inferences in networks large diventano praticabili. È degno menzionare che alcune di queste semplificazioni e metodi computazionali approssimati implicano piuttosto complicati strumenti matematici, molti di essi derivanti da campi adiacenti come la statistica e control engineering/ingegneria dell’automazione. Questi tipi di Bayesian network calculations forniscono un altro caso di come i problemi precedentemente pensati per essere intrattabili computationally hanno dato la precedenza a tecniche avanzate.

Bayesian networks che contengono centinaia di nodi sono state usate per applicazioni in biologia, medicina, document classification, image processing, diritto, error-correction decoding e molti altri campi. Molte di queste networks sono derivate automaticamente da ampi data sets/insiemi di dati, un argomento che discuterò nel prossimo articolo.

Latent Semantic Analysis

Alcuni ricercatori hanno suggerito che rappresentare testo come vettori cattura il “meaning” del testo. Come possono essere i “significati” se le rappresentazioni di un vettore sono computate solo da quanto spesso i vari termini occorrono in documenti e non del tutto dall’ordine nel quale quei termini occorrono? (Dopo tutto, il significato di “Dog bites man” è assolutamente differente da quello di “Man bites dog”.) Thomas K. Landauer e colleghi, prima nel suo Cognitive Science Research Group alla Bell Communications Research (un discendente dei Bell Laboratories) nella metà degli anni ottanta, e successivamente alla University of Colorado, hanno proposto un vector-based scheme per catturare il meaning, che essi chiamarono Latent Semantic Analysis (LSA).

Ecco, in un esempio su scala ridotta, come il metodo LSA funziona. Diciamo che abbiamo un piuttosto lungo documento o un altro materiale di testo riguardante un certo argomento. Noi dividiamo il materiale in sezioni, chiamate “passages” di circa 100 termini ciascuno. Supponendo che il vocabolario del materiale è catturato da 1000 termini (che potrebbero consistere di parole individuali o combinazioni di parole), allora ciascuno di questi passages è rappresentato da un vettore a 1000 dimensioni. Supponiamo di avere 100 di questi vettori.

È difficile (impossibile realmente) visualizzare uno spazio a 1000 dimensioni nel quale i nostri vettori are incorporati , ma forse si può almeno immaginare che alcuni “sottospazi” di dimensioni minori potrebbero contenere tutti o la maggior parte dei vettori.

Usando complicate tecniche matematiche, è possibile costruire uno spazio dimensionale più basso che adeguatamente “contains” 100 vettori (forse, diciamo, in uno spazio a 50 dimensioni). LSA usa metodi basati su una tecnica chiamata “Singular Value Decomposition” (SVD).

Ovviamente, la rappresentazione di questi vettori in 50 dimensioni sarebbe differente rispetto a quella che era in 1000 dimensioni. Molti di questi termini associati con dimensioni nello spazio più ampio contiene in nuovi componenti nello spazio più piccolo. Inoltre, secondo Landauer e colleghi, esso è questa combinazione che consente l’estrazione del latente complessivo significato dai separati passaggi del documento. Come essi dicono nello spiegare un esempio del processo, “…se noi stessimo per cambiare la entry in ognuna cell dell’originario, i valori nella ricostruzione con dimensioni ridotte potrebbero essere cambiati dovunque; questo è il senso matematico nel quale LSA esegue inferenza o induzione”

Trasformare vettori in quelli con componenti in numero inferiore essenzialmente collega insieme molti dei termini occorrenti ( e non occorrenti) negli originari passaggi dai quali i vettori erano derivati. Questo linking insieme può essere pensato come creare un più alto livello di “concept” basato sui termini associati. Esprimere un testo documento in termini di questi concetti (cioè in termini di vettori di dimensione ridotta) ha estratto, secondo i ricercatori alla LSA, l’essenziale “significato” del documento. I vettori di dimensioni ridotte possono collegare insieme termini da differenti sezioni di un testo se essi occorrono in passages che hanno un simile significato anche se essi non occorrono nello stesso passage.

Il processo di LSA consente la computazione della similarità tra ogni due passaggi nel documento, diciamo computando la dimensione dell’angolo tra i due corrispondenti vettori di dimensione ridotta. Insieme al processo di rappresentazione dei passages da vettori di dimensione ridotta, il metodo di LSA anche produce una rappresentazione di ciascun termine nell’intero insieme di termini con un vettore avente la stessa ridotta dimensione. Usando questa rappresentazione, la similarità tra due termini può anche essere computata in aggiunta alla similarità tra un termine e un passaggio. Infine, un documento stesso può essere rappresentato come un vettore consistente della media dei suoi passaggi vettori. Una volta così rappresentati, la similarità tra documenti può essere computata. Questo passo è usato in una delle applicazioni di LSA chiamata “Latent Semantic Indexing” (LSI). Il metodo LSI è riportato per offrire qualche miglioramento su metodi standard di retrieval.

LSA è stato usato in molte settings, includendo la classificazione della valutazione di saggi scritti da college-entrance-exam test-takers, per aiutare gli studenti ad apprendere capacità nello scrivere, aiutando a diagnosticare la schizofrenia dalle verbalizzazioni del paziente e creando sommari di parole chiave di documenti. In aggiunta, esso è stato usato per mimare alcune capacità umane come l’assegnazione di un punteggio oltre alla media di test-takers sulla synonym portion del TOEFL (il ETS TEst of English as a Foreign language) e realizzare un punteggio per passare un esame a scelta multipla che usa i vettori da una LSA analisi di un introduzione ad un manuale di psicologia.

Un lettore potrebbe obiettare che un sistema LSA per classificare saggi potrebbe essere sventato da qualcuno che scrivesse un ampio quantitativo di parole appropriate in ordine casuale senza esprimere alcun coerente pensiero del tutto. I counters di Landauer a questa obiezione dicendo che esso dovrebbe essere hard “ottenere le parole good senza scrivere un buon saggio…Noi abbiamo provato a scrivere saggi bad e ottenere good gradi e noi possiamo talvolta farlo se noi conoscessimo il materiale realmente bene. Il modo più facile per imbrogliare questo sistema è di studiare hard, conoscere il materiale e scrivere un buon saggio.”

Nel 1998, Landauer e colleghi hanno formato le Knowledge Analysis Technologies (KAT) per sviluppare applicazioni educative di LSA. KAT fu acquistato da Pearson Education nel 2004 e commercializza LSA-based prodotti educativi come Pearson Knwoledge Technologies (PKT).

Alcuni ricercatori hanno sottolineato che il principale potere dei metodi della LSA è nella riduzione della dimensionalità dei vettori e che c’erano molti altri metodi (alcuni dei quali erano più semplici rispetto a quello usato in LSA) per ridurre la dimensionalità. Infatti, in uno dei loro primi articoli circa LSA, Landauer e Susan Dumais descrivono un analogo a LSA basato su una neural network.

Un’estensione probabilistica al Latent Semantic Indexing è stata proposta e testata da Thomas Hofmann. Un più generale modello probabilistico è stato sviluppato da David Blei, Andrew Ng e Michael Jordan. Modelli probabilistici di tutti i tipi iniziarono a giocare un ruolo molto prominente in AI che iniziava negli ultimi anni ottanta.