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.

Representing Text as Vectors

Nei precedenti posts, ho descritto sistemi question-answering nei quali una domanda è convertita in una forma gestibile computazionalmente (ad esempio in un formula logica), la quale è poi usata per query/interrogare un database di un computer (ad esempio una KB di formule logiche). Probabilmente gli esempi più familiari di question answering oggi si svolgono usando i search engines/motori di ricerca del World Wide Web. Una persona di AI della persuasion logicist potrebbe sperare che ultimamente il testo in pagine web potrebbe essere rappresentato come formule logiche e che una query potrebbe essere rappresentata come una formula logica per essere answered (proved/dimostrata) da formule in una (o più) di quelle pagine web. Ci sono alcuni iniziali tentativi per rispondere alle queries in inglese in questo modo, ma la maggior parte degli Web search engines usa tecniche più semplici e più efficienti. Io darò una semplice idea di come alcuni di essi funzionino. Essi convertono il testo sia i documenti sia le queries in vectors e comparano un query vector contro competing document vectors. Prima, io dirò alcune cose circa i vettori e poi descriverò come il testo può essere rappresentato come un vettore. (ricorderete le mie precedenti discussions dell’ uso di vettori in pattern recognition).

In matematica, un vettore è una quantità che ha direzione, verso e lunghezza. In uno spazio 3D, per esempio si rappresenta un vettore come una freccia disegnato dall’origine di quello spazio ad un punto in questo spazio. La freccia punta nella direzione del vettore e la lunghezza della freccia è il modulo del vettore. Poiché il punto determina il vettore (c’è un unico modo di disegnare una freccia dall’origine ad un punto), le parole “point” e “vector” sono spesso usate come sinonimi. Ogni ordered list di numeri può essere pensata come le coordinate di un punto così come le componenti di un vettore. Per esempio, la list (7, 4, 3, 20) è un vettore in uno spazio 4D. Si possono avere vettori di molte dimensioni. La lunghezza di un vettore è la radice quadrata della somma dei quadrati di tutte le componenti del vettore. (Per vettori 2D, questo calcolo è solo un’applicazione del teorema di Pitagora, cioè, il quadrato della lunghezza dell’ipotenusa di un triangolo rettangolo è la somma dei quadrati dei suoi lati cateti) Per esempio, la lunghezza del vettore (7, 4, 3, 20) è ~21,77.

Si può misurare la similitudine tra due vettori o calcolando la distanza tra i loro estremi (per considerare la loro lunghezza) oppure dalla “smallness” di un angolo compreso tra le loro due direzioni – più piccolo è l’angolo, più simili sono i vettori. Per il metodo dell’angolo, si esegue la seguente computazione di similitudine: Moltiplicare ciascun componente di uno dei vettori per il corrispondente componente dell’altro vettore e poi addizionare insieme tutti questi prodotti. Poi, si divide questa somma per il prodotto delle lunghezze di ciascun vettore. Questo numero finale, che noi chiameremmo S che sta per similitudine, può essere al più 1 se i due vettori sono esattamente allineati (cioè, che puntano nella stessa direzione). Essa è 0 se i due vettori sono perpendicolari a ciascun altro ed esso è negativo se essi puntano in opposte direzioni. Così, più sono simili i vettori, più vicino a 1 è il calcolo della loro S. [I lettori familiari con la trigonometria potrebbero riconoscere questo calcolo come il coseno dell’angolo compreso tra i due vettori (Prodotto Scalare)].

Come esempio, il valore di S per i vettori (7, 4, 3, 20) e (7, 0, 2, 15) può essere calcolato (49+6+300)/(21,77 ×16,67) ~ 0,978, un valore che indica che questi due vettori sono assolutamente simili.

Come possiamo convertire un testo in un vettore? Le persone impegnate nel retrieval di documenti (la cosiddetta information retrieval) hanno escogitato un metodo. Prima, una lista ordered di termini (parole o frasi) è scelta come insieme di documenti per essere rappresentati con vettori. Se i documenti sono riguardanti AI, ci potrebbero essere centinaia di termini che sarebbero appropriati, includendo “search”, “heuristic”, “computer vision”,…Se i documenti sono tutti in inglese e potrebbero essere circa ogni cosa, ci potrebbero essere centinaia di migliaia termini (essenzialmente tutte le parole in inglese). Usualmente i termini scelti sono word stems, così che “computing”, “computers”, e “computed” sarebbero tutti covered dal termine “compute” (Si deve stare attenti riguardo questo tipo di combinazione, fusione, crasi, chiamata “stemming” derivante per evitare di sostituire “flow” per “flower” ). Inoltre, poiché le parole come “and”, “if”, e “therefore” e altre sono seldom relevant per il contenuto di un documento, queste parole non sono usate come termini.

Successivamente, nel processo di rappresentazione di un documento come un vettore, tutte le occorrenze di ciascuno di questi termini nel documento sono contate. Una list di questi numeri di occorrenze è poi assemblata (nello stesso ordine come la list di termini) e questa lista è il vettore rappresentazione del documento. Così, per esempio, se il termine “search” non occorre del tutto in un documento che è rappresentato, se il termine “heuristic” occorre sette volte e il termine “computer vision” occorre tre volte, allora la lista sarebbe, diciamo

(0, 0, 0, 0, 0, 7, 0, 0, 3, 0, 0,…).

Ovviamente, ci potrebbero essere molti, molti 0 perché molti dei termini nella lista scelta di termini potrebbero non occorrere del tutto nel documento e ci potrebbero essere molti più non-zero numeri corrispondenti ai numeri di volte gli altri termini occorrono in quel documento.

Ora, supponiamo di essere interessati alla domanda “What heuristics are used in computer vision?” e poniamo questa query al motore di ricerca in internet. Se noi ipotizziamo che alcuni tipi kind di preprocessing è usato sulla query (e sui documenti) per cambiare parole nei loro “stems” derivati, il vettore rappresentazione della nostra query sarebbe

(0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0,…).

La similitudine S tra la nostra query e il documento che noi abbiamo appena considerato sarebbe 10 diviso il prodotto delle lunghezze di due vettori. Questo valore sarebbe comparato con i valori di similarità contro gli altri documenti per determinare quali documenti sono i più simili e quindi sarebbero retrieved in risposta alla nostra query.

Tutto ciò suona pretty , ma, sebbene l’idea base sia semplice, molte elaborazioni sono necessarie (e sono state aggiunte) per rendere il document retrieval e il retrieval in internet di siti web basati su questa idea pratica e utile. Primo, il count per un termine in un documento è usualmente considerare la lunghezza del testo in quel documento. Poiché più lunghi documenti potrebbero contenere relativamente più occorrenze di una dato termine, il count per un termine è computato come una percentuale del numero totale di tutti i termini nel documento. Secondo, poiché un dato termine potrebbe essere assolutamente comune tra tutti i documenti che sono searched (e così non molto utili per la discriminazione), il count è diminuito da un fattore che dipende dalla frequenza complessiva di quel termine tra questi documenti. Programmi di retrieval più sofisticati usano anche vari metodi statistici per computare la probabilità di una rilevanza di un documento con una query. Un’innovazione inventata da Google classifica i siti web secondo una stima correlata alla loro popolarità o “centrality”, in modo incrementale, i metodi “machine learning” alcuni dei quali saranno descritti in un seguente post sono usati per migliorare la performance di retrieval system e, ovviamente, l’efficienza richiede appropriati schemi di indicizzazione/indexing schemes e l’uso di molte migliaia di computers.

Solving Problems Using Propositional Logic

Un importante caso speciale di rappresentazione logica della conoscenza e di reasoning è il caso in cui nessuna delle formule logiche contiene variabili. Sebbene questo caso potrebbe non avere formule come (Ax)[Man (x) ∩ Mortal (x)], esso potrebbe avere formule come [Man (Socrates)∩Mortal (Socrates) e [Man(Plato) ∩Mortal (Plato)]…Poiché non ci sono variabili questo caso speciale è essenzialmente lo stesso della propositional logic. Questo è perché espressioni come Man (Socrates) e Mortal (Socrates), tutte le volte esse occorrano nella KB, potrebbero essere rimpiazzate da proposizioni, come P014 e Q234, che non hanno strutture interne e sono così completamente unrelated. Lo svantaggio di limitare noi stessi alla propositional logic è che noi avremmo dovuto avere un possibilmente molto esteso quantitativo di formule per coprire tutte all le entità circa le quali vogliamo parlare – invece di usare solo singole formule con variabili che le coprono tutte. Il vantaggio che compensa tuttavia è che i metodi estremamente potenti sono stati sviluppati per il reasoning con quantitativi molto ampi di propositional formulas.

Illustrerò come questi metodi funzionano usando un semplice puzzle logico. Supponiamo che tra gli invitati ad un dinner party ci sono tre individui molesti, Ann, Bill e Charlie. Un amico che è consapevole della dinamica sociale tra queste persone informa la padrona di casa che almeno uno di questi ospiti potrebbe attendere in modo definito, ma che se Ann attende, Bill non attenderà e se Bill attende, Charlie non attenderà e se Charlie attende Anna non attenderà. Basandosi su questa informazione, può la padrona di casa indovinare chi potrebbe attendere?

Se lei fosse una logica, potrebbe convertire l’informazione del di lei amico nel seguente insieme di formule in propositional logic (dove A sta per “Ann is coming”, …):

A v B v C,

¬A v ¬B,

¬B v ¬ C,

¬C v ¬A.

Ricordo dal mio precedente uso di formule logiche che “¬” sta per “not” e che “v” sta per “or”. Formule come queste che consistono di proposizioni (o delle loro negazione) sono connesse congiunte dai segni “or” sono chiamate “clauses”. Le proposizioni individuali stesse sono chiamate “variables” perché i loro valori di verità devono ancora essere assegnati.

Per risolvere il di lei problema, la nostra padrona di casa deve indovinare per assegnare valori di verità (T o F) alle tre proposizioni A, B e C così che tutte le clauses hanno valore T (perché esse derivano da proposizioni ipotizzate essere vere). Se una clause ha valore T, un logico direbbe che essa è “SATisfied”. Per esempio, se A ha valore T, significa che Ann is coming, la prima clause sarebbe SATisfied (non importando qui i valori di B e di C).

I logici e gli informatici hanno calcolato modi di trattare il problema di se o no c’è un assegnamento di valori di verità alle variabili in un insieme di clauses così che tutte le clauses sono satisfied e ciò che quei valori potrebbero essere. La difficoltà è che il problema di determinare la satisfiability, chiamato il “SAT problem” è NP-complete, che implica che, nel caso peggiore in the worst case, il tempo preso da tutti gli algoritmi noti per risolvere i problemi SAT cresce esponenzialmente con la dimensione del problema.

Ovviamente il problema non è un ampio problema e lei non avrebbe difficoltà a risolverlo semplicemente provando i (soli) otto possibili modi di assegnare valori di verità ad A, B, e C per scoprire quale di questi otto soddisfi tutte le di lei clauses. Ma molti problemi computazionali codificati come insiemi di clauses potrebbero implicare centinaia di migliaia di clauses contenenti migliaia di variabili. Questi problemi sarebbero intrattabili per un metodo trial-and-error. Fortunatamente, metodi più efficienti sono stati sviluppati che sono capaci di risolvere problemi molto ampi. Infatti, Bart Selman, uno degli inventori di alcuni di questi metodi più efficienti efficaci, dice “…i correnti solvers possono risolvere instances con un milione o più di variabili e molti milioni di clauses”. Inoltre, egli dichiara che non c’è “solo un risultato di hardware più veloce…è realmente del 95% il risultato dei migliori algoritmi. Noi stiamo ancora trattando un NP-complete problem e un exponential search space. Così, i miglioramenti dell’hardware senza idee algoritmiche non ha troppo impatto”.

Ci sono due tipi principali di metodi per risolvere SAT problems. Una classe consiste di ciò che sono chiamati systematic methods e l’altra classe consiste di ciò che sono chiamati local search methods Infatti, alcuni dei migliori solvers usano tecniche da entrambi questi due metodi.

Other Approaches to Reasoning and Representation

Solving Constraint Satisfaction Problems

In aggiunta ai reasoning methods basati sulla logica o sulle reti semantiche, molte altre tecniche sono state esplorate. In questa sezione, descriverò una classe di problemi chiamati constraint satisfaction problems (CSP) Problemi di Soddisfacimento di Vincoli (o assignment problems problemi di assegnazione) e metodi per risolverli. In questi problemi, noi abbiamo un insieme di oggetti a cui devono essere assegnati valori che soddisfino un insieme di constraints vincoli. Noi abbiamo già visto un esempio di un assignment problem – quello di assigning assegnazione di etichette labels a linee in un’immagine. In questo problema, il constraint vincolo è che a ciascuna linea nell’immagine può essere assegnato una ed una sola label etichetta.

Constraints Vincoli possono essere espressi nella forma di database relations, formule logiche, equazioni o disequazioni. Così, i constraint satisfaction problems problemi di soddisfacimento di vincoli sorgono naturalmente in molti ambienti settings includendo scheduling pianificazione, simulazione, computer vision e robotica. (Uno spreadsheet foglio di calcolo è un semplice constraint satisfaction system, per esempio). Fortunatamente, ci sono alcuni general-purpose metodi di soluzione per questi problemi che sono indipendenti dall’applicazione. Io illustrerò uno di questi metodi con un piccolo esempio.

Si consideri il problema di piazzare quattro regine su una scacchiera 4 × 4 in un modo che nessuna regina può catturare un’altra. Nel problema delle Four-Queens, noi abbiamo quattro objects c₁, c₂, c₃, e c₄che rappresentano le colonne dalla 1 alla 4, rispettivamente, nelle quali una regina potrebbe essere piazzata. Ciascuno di questi oggetti può avere uno di quattro valori, 1, 2, 3 o 4, che corrispondono ai numeri della riga. Così, per esempio, se c₃ ha valore 2, una regina è piazzata nella seconda riga della terza colonna. Il problema delle Four-Queens constrains vincola i valori di queste variabili. Per esempio, se c₁ ha valore 1, c₂ non può avere valore 1 o 2; c₃ non può avere valore 1 o 3; e c₄ non può avere valore 1 o 4. I Constraints Vincoli sono rappresentati come un graph grafo chiamato constraint graph. Ciascun nodo in questo grafo è etichettato da un nome di oggetto insieme con un insieme di tutti i valori per quell’oggetto. Un paio di nodi è connesso da un arco (un edge bordo che ha una direzione) se i possibili valori dell’oggetto at the tail alla coda (estremo posteriore dell’arco) sono constrained vincolati da ognuno dei valori dell’oggetto alla head estremo anteriore testa dell’arco. In questo problema, ciascun oggetto constrains vincola tutti gli altri, così tutti i nodi hanno archi verso tutti gli altri nodi.

Cominciamo con l’assegnare un valore ad uno degli oggetti. Questa assigment assegnazione è un valore “trial” prova e l’inizio di un search process. Se esso non funziona, noi dovremmo to backtrack tornare indietro e provare un altro valore. Supponiamo di iniziare con l’assegnare il valore 2 all’oggetto c₁ (che corrisponde a piazzare una regina nella colonna 1, riga 2). Ora noi esaminiamo iterativamente tutti gli archi ed eliminiamo ogni valore di un oggetto at the tail alla coda di un /arco che è inconsistente (secondo i constraints vincoli) con tutti i valori alla head testa dell’arco. Questo process processo chiamato constraint propagation, halts si ferma quando nessun valore in più può essere eliminato. I primi pochi steps passi del processo potrebbero essere come segue:

1. Primo, guardiamo l’arco da c₂ a c₁: noi possiamo eliminare c₂ = 1, c₂ = 2 e c₂ = 3 perché ciascuno di quei valori è inconsistente con i valori (essendoci solo uno) di c₁

2. Poi, guardiamo l’arco da c₃ a c₁: noi possiamo eliminare c₃ = 2 e c₃ = 4

3. Poi, guardiamo l’arco da c₄ a c₁: noi possiamo eliminare c₄ = 2.

Eliminanare alcuni dei valori, come abbiamo appena fatto, ora renders raffigura persino più valori suscettibili di eliminazione. Revisiting Rivedendo gli archi per verificare check ancora la consistenza potrebbero rivelarsi which ones. L’eliminazione di un valore può essere detta “propagate” sul constraint graph. Continuando il processo della propagation si eliminano tutti eccetto un valore di una variabile per ciascun nodo. A questo punto, tutti gli archi sono consistenti e nessun altro valore può essere eliminato. Il graph mostra come il processo potrebbe andare, cominciando con i valori rimanenti dopo l’esecuzione dei tre passi elencati. In questo caso, la constraint propagation ha risolto il problema (dato che noi siamo partiti con c₁ = 2, una fortunata ipotesi indovinata).

Questo processo per trattare constraint satisfaction problems (CSP) è basato su AC-3 (abbreviazione per Arc Consistency Algorithm No. 3), un algoritmo proposto da Alan K. Mackworth, professore alla University of British Columbia. Mackworth ha continuato il lavoro su constraint problems e le loro applicazioni in robotica e in agent control. (Egli ha anche proposto e costruito i primi robots giocatori di soccer).

Varie estensioni e miglioramenti di AC-3 sono stati proposti.

L’articolo di Vipin Kumar indaga l’intero campo. Compagnie commerciali, come ILOG (che è stata acquisita dalla IBM) routinely regolarmente usano constraint linguaggi di programmazione per applicazioni che involving implicano scheduling e simulazione.

L’esempio delle Four-Queens usato per illustrare constraint propagation happened per trovare una soluzione senza il searching (poiché io ho l’ho iniziato con la selezione c₁ = 2). Ma, se io avessi selezionato c₁ =1 inizialmente invece, la constraint propagation avrebbe eliminato tutti all i valori in tutti i nodi – indicando che non c’è soluzione per il problema delle Four-Queens con una regina nella colonna 1, riga 1. Fare questa selezione e trovare che non c’è allora alcuna soluzione, avrebbe richiesto un search process di livello più alto per backtrack tornare indietro per provare un altro valore. Inoltre, è possibile che una trial selection seguita da una constraint propagation avrebbe lasciato irrisolto il valore di alcuni degli oggetti. In questo caso, una selezione avrebbe dovuto essere fatta per un valore di uno di questi oggetti seguito da più constraint propagation, possibile backtracking tornare indietro, …Così il risolvere constraint satisfaction problems tipicamente richiede ricerca search e molte backtracking procedures sono state proposte e usate.