Intelligenza Artificiale in pillole – Videosorveglianza automatica

12 febbraio 2010 - 7:54 by Charlenger

Tra le tante aree di cui si occupa l’intelligenza artificiale c’è anche l’elaborazione automatica delle immagini. Non in molti sanno che quando applicano un filtro usando photoshop, dietro si avviano una serie di algoritmi molto complessi di analisi ed elaborazione dell’immagine. E probabilmente ancora meno si chiedono come sia possibile che una macchina fotografica di ultima generazione ti mostri dove si trova in tempo reale il volto di una persona. Esistono numerose tecniche di elaborazione delle immagini che si basano sulla statistica, su algoritmi e procedure definite e così via, che sono studiati proprio in intelligenza artificiale.

Una delle tante applicazioni dell’elaborazione automatica delle immagini, o in questo caso particolare di sequenze di immagini, è il processo di “object tracking” ovvero tracciamento degli spostamenti di un oggetto. Questa tecnica consiste nell’individuare in un video (o sequenza di immagini) gli oggetti in movimento all’interno della cornice ripresa.

La tecnica più comunemente usata è il metodo di sottrazione dello sfondo. Questo metodo ha alcuni vantaggi, uno su tutti la semplicità computazionale, ma anche la capacità di adattare le soglie di ricerca, tuttavia esistono metodi più efficaci che si basano su filtri statistici per prevedere come cambieranno i pixel dell’immagine, prevedendone il “movimento”.

Analizzando il metodo di sottrazione dello sfondo, sostanzialmente quello che viene fatto è un conteggio di quanti pixel sono cambiati tra un’immagine e l’altra. Ogni immagine può essere rappresentata come una matrice di valori di dimensione NxMxZ dove NxM sono le dimensioni dell’immagine (e.g. 640×480) e Z è il numero di piani di colore (normalmente 3) che dipende dal modello di rappresentazione (e.g. RGB, HSV, etc).

Quando si applica il metodo di sottrazione dello sfondo, è prima di tutto necessario trasformare le immagini sorgenti in valori della scala di grigio, per semplificare ulteriormente l’onere computazionale. Fatto ciò l’algoritmo di base è semplice:

Per ogni pixel dell’immagine N-esima, calcolarne la differenza con l’immagine N+1-esima, e se questi sono differenti, allora incrementare il conteggio dei pixel differenti. Ovviamente in una sequenza di qualità “normale” o in condizioni in cui la luce può variare sensibilmente, la differenza tra i pixel non è definita in maniera netta, ma è rappresentata da un valore di soglia. Al termine del calcolo delle differenze, si otterrà un valore che rappresenta la percentuale di pixel che sono mutati all’interno dell’immagine. Se questa percentuale è molto alta (più alta della soglia di controllo), allora si può asserire che qualcosa all’interno della cornice di controllo si stia muovendo.

Questa tecnica ha notevoli vantaggi in alcune applicazioni, come la videosorveglianza automatica, ma ha anche notevoli svantaggi per altri contesti, come per esempio quelli in cui è necessario identificare precisamente i contorni dell’oggetto che si muove. Infatti, la tecnica descritta, non utilizzando alcun approccio statistico, non è in grado di stabilire se due pixel molto lontani, abbiano qualche tipo di relazione tra di loro, e non è capace di descrivere dei vettori di movimento che permettano di prevedere dove l’oggetto stia andando.

Recentemente ho pubblicato un progetto che fa uso di questa tecnica e di alcuni accorgimenti statistici per renderne più efficace il funzionamento. Si tratta di un semplice sistema di videosorveglianza automatica che è in grado di inviare dei messaggi email se qualcosa si muove all’interno di una webcam. Il programma può essere configurato per inviare la mail a più indirizzi, da uno specifico indirizzo sorgente, per eseguire un’applicazione esterna in caso di stato di allerta, ed è capace di gestire un numero teoricamente illimitato di webcams (in realtà dipende fortemente dalle prestazioni della macchina su cui gira).

HVideoSecurity non è del tutto portabile in quanto fa uso di librerie native del progetto LTI-Civil per il controllo dell’hardware (le webcam). Per tale motivo la portabilità del programma è limitata ai sistemi operativi per cui sono disponibili sia i driver delle webcam, sia le librerie LTI-Civil.

Ecco alcuni screenshot dell’applicazione:

HVideoSecurity Settings

  

HVideoSecurity Webcam

 

Ed ecco a voi un esempio delle immagini che arrivandomi in allegato in una mail mi hanno avvisato del rientro a casa della mia fidanzata, mentre ero in ufficio:

 

Se fosse stata un’intrusione avrei avuto la notizia in tempo reale… cosa fare dopo… eh beh…


Tags: , , , , , , , , , , , , ,
Pubblicato in Computer Science | Commenti disabilitati


NLP – Natural Language Processing – Introduzione al Naive Bayes Classifier

31 gennaio 2010 - 15:55 by Charlenger

La classificazione documentale, come spiegato nel precedente articolo sull’argomento, si compone di varie fasi e sfrutta vari strumenti. Uno tra quelli presentati è il classificatore ingenuo di Bayes o “Naive Bayes Classifier”. La solita citazione da Wikipedia è:

“A Bayes classifier is a simple probabilistic classifier based on applying Bayes’ theorem (from Bayesian statistics) with strong (naive) independence assumptions. A more descriptive term for the underlying probability model would be “independent feature model”.”

Prima di poter parlare di classificazione documentale sarebbe innanzi tutto necessario parlare di classificazione in maniera più generale. Infatti, la classificazione documentale, altro non è che un normale processo di classificazione, in questo caso basata su un approccio statistico, composta di numeri, regole e formule. Viene spontaneo chiedersi come sia possibile a questo punto che un documento, fatto di parole, lettere, punteggiatura e simboli che vanno ben oltre semplici numeri, possa essere trattato come se fosse una variabile di un’equazione matematica.

La risposta al questio si chiama “modello matematico”. I modelli matematici, grande divertimento dei ricercatori operativi, sono il risultato di processi di analisi e modellazione che permettono di mappare in qualche modo, più o meno coerente e completo, un qualsiasi elemento della realtà. Il “più o meno coerente e completo” è d’obbligo perché è noto che la natura non fa spigoli, cioè il mondo non è lineare, mentre spesso i problemi reali vengono modellizzati in modo tale da essere risolvibili, per esempio, studiandone una versione linearizzata.

Prendendo il caso particolare del metodo statistico di Bayes, e semplificando al minimo il modello matematico da utilizzare, è possibile trasformare un documento in un semplice vettore di numeri che, nel caso del classificatore classico, appartengono all’insieme {0,1}, cioè sono binari. Questa modellazione è possibile grazie a una “legenda” di riferimento detta vocabolario. In questo particolare caso, il vocabolario del modello matematico corrisponde con un vocabolario secondo la sua più stretta e umana definizione.

Passando a un esempio concreto, si supponga di avere questo vocabolario:

[giocatore, sport, calcio, pallone, scarpa, rete, palo, portiere]

e la seguente frase:

“Durante la partita, il giocatore ha dato un calcio al pallone e ha perso la scarpa”

dunque il vettore di riferimento sarebbe:

[1, 0, 1, 1, 1, 0, 0, 0]

Senza andare nel dettaglio della fase di pre-elaborazione dei dati (cioè la loro trasformazione in dati utilizzabili per l’addestramento e la fruizione del classificatore), è possibile illustrare il principio che sta alla base della classificazione ingenua. Tale classificazione è definita in questo modo perché si presuppone che gli elementi che costituiscono i vettori e il vocabolario siano indipendenti tra loro, e dunque non vengano considerate eventuali correlazioni. Per intendere meglio cosa voglia dire ingenuo può essere utile un esempio:

In un documento che parla di biologia, e in particolare del ciclo di vita di una pianta, la probabilità che nel testo appaia la parola “fotosintesi” non è indipendente dalla presenza del termine “clorofilliana”. Nella conoscenza comune è noto associare le due parole e, per di più, la presenza della seconda può addirittura essere correlata in posizione al termine precedente. Sarà infatti molto più probabile incontrare nel testo l’espressione “fotosintesi clorofilliana” che “clorofilliana fotosintesi”.

Quando si parla di classificazione ingenua, si assume che il valore corrispondente a questi due termini, sia indipendente l’uno dall’altro, cioè si ignora il fatto che la presenza delle due parole insieme costituirebbe una maggiore probabilità che un certo testo parli di biologia vegetale. Viene naturale chiedersi perché non lo si consideri. La risposta è già stata fornita in precedenza. Il modello da utilizzare deve essere semplice e computabile e inserire questo tipo di dipendenze (ne esistono anche di molto complesse nella linguistica e nella teoria della probabilità), significherebbe rendere il problema molto complesso, e in vari casi anche NP-Completo.

La regola di Bayes su cui si basa il classificatore dice che:

La probabilità P di un evento E, data l’evidenza F{1,2,…,N} è data dal rapporto tra il prodotto della probabilità del singolo evento P(E) con la probabilità dell’evidenza dato il fatto E, e la probabilità dell’evidenza.

P(E | F1,F2,…,Fn) = P(E) * P(F1,F2,…,Fn | E) / P(F1,F2,…,Fn)

Detto in termini di classificazione, si supponga che l’evento E sia la categoria da assegnare a un certo documento, e che l’evidenza siano i singoli termini che costituiscono il vocabolario, la regola potrebbe esprimersi come “la probabilità che un documento appartenga alla categoria E, data la presenza/assenza delle parole F1,…,Fn è pari al prodotto della probabilità stessa che un documento appartenga a una certa categoria moltiplicato per la probabilità di ciascuna delle parole, presupposto che si tratti della categoria E, diviso la probabilità delle parole stesse.

Anche espresso in questo modo, il concetto non rimane chiarissimo, ma la comprensione di questa legge non è lo scopo di questo articolo. In ogni caso, la legge scritta in questo modo è altamente esauriente ma sarebbe computazionalmente difficile da calcolare e rappresenterebbe il classificatore “ideale” di bayes.

La classificazione infatti avverrebbe calcolando, dato un documento, la probabilità che questo appartenga a ciascuna delle possibili categorie, scegliendo, ovviamente, quella più alta. Come fare dunque a rendere la legge utilizzabile? Proprio utilizzando il principio di “ingenuità”. Infatti, considerato che la probabilità congiunta espressa al numeratore del secondo membro dell’equazione è esprimibile come:

P(E, F1, F2, … Fn) = P(E)*P(F1|E)*P(F2|F2,E)*…*P(Fn|Fn-1,…F1)

La condizione di indipendenza o ingenuità ci permette di dire che per ogni “i” diverso da “j” è valida la seguente relazione:

P(Fi | C, Fj) = P(Fi | C)

Cioè che non c’è nessuna relazione di probabilità tra “fotosintesi” e “clorofilliana”. Questo ci permette di ridurre l’equazione precedente (dove l’evidenza sarà espressa comeF) nel seguente modo:

P(E | F) = P(C)*P(F1|C)*P(F2|C)*…*P(Fn|C)/P(F)

Adesso, posto che nella classificazione ingenua, generalmente, le categorie sono considerate equiprobabili, e che l’evidenza è un fattore identico per ogni categoria, il valore che vogliamo calcolare potrà essere calcolato come:

P(E | F) = P(F1|C)*P(F2|C)*…*P(Fn|C)

Che significa che dato un documento, il valore che ci permette di ipotizzare a quale categoria appartenga, è data dal massimo prodotto di tutti i valori di probabilità di ciascuna parola del vocabolario in relazione a ciascuna categoria. Il concetto può essere spiegato meglio con un esempio pratico.

Supponiamo di prendere un vocabolario di 5 parole:

W = [cane, soldi, deputato, calciatore, locale]

e di avere 3 categorie:

C = [sport, economia, tempo libero]

La prima cosa da fare sarebbe addestrare il classificatore. Per farlo bisogna calcolare le tabelle di probabilità di ciascun termine per ciascuna categoria e per farlo si passa attraverso l’addestramento. Per esemplificare, si prende un insieme di 3 vettori (documenti) per la categoria “sport”:

v1 = [1,0,0,1,1]
v2 = [1,0,0,1,0]
v3 = [0,0,0,1,1]

 La riga relativa alla categoria “sport” per la tabella delle probabilità sarebbe:

sport = [2/3, 0/3, 0/3, 3/3, 2/3]

Si supponga di avere ache le altre due categorie e di avere dunque la seguente tabella delle probabilità positive (quelle negative si calcolano come “1 – p”):

[2/3, 0/3, 0/3, 3/3, 2/3]
[1/3, 2/3, 3/3, 0/3, 0/3]
[2/3, 1/3, 0/3, 1/2, 3/3]

 Se volessimo classificare il seguente documento: “il calciatore ha giocato come un cane”, a cui corrisponde il vettore [1, 0, 0, 1, 1] potremmo calcolare i tre possibili valori come:

v(sport) = 2/3*(1 – 0/3)*(1 – 0/3)*3/3*2/3 = 4/9 = 0,44
v(economia) = 1/3*(1 – 2/3)*(1 – 3/3)*0/3*0/3 = 0
v(tempo libero) = 2/3*(1 – 1/3)*(1 – 0/3)*3/3*2/3 = 8/27 = 0,30

quindi max(V) = 0,44 cioè: il documento è classificato come “sport”.

Emerge subito come il risultato sia fortemente dipendente dai dati con cui viene addestrato il sistema e soprattutto esso non è esente da condizioni limite. Per esempio, l’assenza della parola “deputato”, dal momento che è presente nel 100% dei campioni di economia, andrebbe ad azzerare la probabilità nonostante altre parole potrebbero aumentare significativamente lo stesso valore. Questo sarebbe un caso di sotto-stima dell’insieme di addestramento. Al contrario potrebbero esserci significative differenze nel numero dei documenti utilizzati e una categoria potrebbe essere favorita. In questo caso si ha un problema di sovra-dimensionamento. Per far fronte a questi problemi si usano varie tecniche basate su tecniche che calcolano i valori di probabilità sulla base della frequenza dei termini, la loro rilevanza e la proporzione normalizzata dei documenti (e.g. TF-IDF). Questo genere di approcci può trasformare il vettore che rappresenta il documento da binario a reale (e.g. [0.2, 0.4, ... , 0.7]).

Esistono varie altre tecniche e adattamenti di questo algoritmo o che ne siano valide alternative, per esempio le macchine a vettori di supporto, tuttavia il classificatore Naive Bayes rimane uno dei più usati in quanto è facile da implementare, facilmente personalizzabile in base ai tipi di classificazione che deve svolgere, raffinabile e molto efficiente sebbene fortemente dipendente dalla qualità dei dati forniti per l’addestramento.


Tags: , , , , , , , , , , , , , , ,
Pubblicato in Computer Science | 2 Commenti »


NLP – Natural Language Processing – Una breve introduzione

11 gennaio 2010 - 1:42 by Charlenger

L’elaborazione del linguaggio naturale, in inglese abbreviata con la sigla NLP (Natural Language Processing), è una branca dell’intelligenza artificiale che abbraccia tutte quelle aree all’interno delle quali si ricercano e sviluppano algoritmi per l’estrazione automatica di informazioni a mezzo di calcolatori elettronici a partire da una qualunque forma di linguaggio naturale.

Un linguaggio naturale può essere una forma scritta, verbale o anche gestuale. Qualunque tipo di linguaggio che abbia una struttura definita da regole e che venga “naturalmente” utilizzato per comunicare può quindi essere considerato un linguaggio naturale.

Tutti i problemi affrontati all’interno della NLP possono essere considerati come parte del più generale problema della comprensione del linguaggio naturale che è IA (Intelligenza Artificiale) completo in quanto presuppongono che la macchina sia in grado di sfruttare complesse capacità di logica, deduzione, apprendimento e così via, al fine di avere una conoscenza, per l’appunto, completa (o per lo meno quanto più completa possibile) del mondo in cui essa opera.

Alcune delle aree che fanno capo alla NLP sono le seguenti:

- Riconoscimento Automatico del Parlato (ASR – Automatic Speech Recognition): area che si occupa di estrarre informazioni da informazioni verbali come l’identificazione del parlante, l’identificazione di particolari vocaboli all’interno di una frase, il riconoscimento completo di frasi e così via;
- Classificazione Documentale (DC – Document Classfication): area che si occupa di analizzare testi scritti e di catalogarli o etichettarli secondo particolari categorie, siano esse binarie o multiple, estraendo dai vari documenti informazioni come la rilevanza delle varie parole, somiglianza tra campioni e così via;
- Analisi emozionale (SA – Sentiment Analysis): area che si occupa di estrarre informazioni legate ai sentimenti espressi all’interno di un testo scritto, il parere dell’autore e le possibili relazioni tra due o più documenti in termini di vicinanza a una data opinione;
- Supporto Grammaticale (GS – Grammatical Support): area che si occupa di analizzare testi scritti e di estrarre informazioni legate alla struttura grammaticale del testo in relazione alla lingua in cui è scritto o in relazione a leggi prestabilite da altri documenti;
- Sintesi Vocale (SS – Speech Synthesys): area che si occupa di creare suoni a partire da testi scritti che siano coerenti con le regole fonetiche della lingua da sintetizzare, sulla base di quanto il testo voglia esprimere;
- Interpretazione dei Gesti (GI – Gesture Interpretation): area che si occupa di associare a dei gesti visuali un significato in termini di testo o vocabolo;

Come è facile immaginare, ciascuno di queste aree ha grandi applicazioni sia al livello puro nel mondo accademico e della ricerca, che nel mondo commerciale. Tuttavia spesso non è semplice immaginare quali difficoltà stiano dietro allo sviluppo di tecnologie che si occupino di risolvere problemi che all’apparenza sono piccoli e che rappresentano anche solo una piccola parte di un sotto-problema della comprensione del linguaggio naturale.

Per fare un esempio, non molto spesso ci si ferma a riflettere su quanto complesso sia il nostro sistema di comunicazione. Quando ci capita di parlare con qualcuno in mezzo a una folla, siamo attorniati da migliaia di rumori e voci, dati che il nostro cervello scarta e non traduce in informazioni se non nello stretto necessario. Siamo tuttavia in grado di focalizzarci su ciò che il nostro interlocutore ci sta dicendo, comprenderlo ed elaborare una risposta. Sembra semplice tuttavia per una macchina non lo è. Questo è dovuto al fatto che la comunicazione umana non si basa, come è facile pensare, solo sull’elemento verbale. Essa si basa su moltissimi altri elementi contestuali come i gesti, la conoscenza pregressa, la cultura e così via. Quando crediamo di avere sentito una parola e gli abbiamo associato un significato, non è detto che questo sia avvenuto attraverso la mera elaborazione del suono.

Un celebre esempio presentato da Rabiner, uno dei luminari nel campo del riconoscimento automatio del parlato, mostra come una macchina sia impossibilitata a comprendere una semplice espressione che un umano darebbe per scontata:

“I want an ice cream” – io voglio un gelato

Facile da capire no?

“I want an I scream” – io voglio un io grido

ovviamente non ha significato… per noi. Tuttavia è interessante riflettere sul fatto che una macchina non sa a priori che “want” e “scream” siano dei verbi e che una frase come “I want an …” probabilmente ha bisogno di un complemento oggetto. Ma leggendo la frase ad alta voce con tono naturale ci accorgeremmo che la differenza fonetica è praticamente impercettibile tra le due frasi.

Il cervello umano è un sistema molto complesso e dal quale siamo ancora ben lontani dal crearne uno artificiale in grado di simulare le funzioni di uno reale. La comprensione del linguaggio naturale è un processo che nella nostra mente attiva una serie di processi di analisi sintattica e semantica, lessicale e grammaticale, che sono corredati da filtri percettivi che il nostro cervello impara a usare, come l’ignorare il rumore circostante, il ricostruire frasi o parole incomplete sulla base della “probabilità” che quel suono in quel contesto significasse qualcosa in particolare.

Dal momento che questa è una breve introduzione voglio rifare l’elenco precedente esponendo una singola possibile applicazione di questo tipo di sistemi a livello avanzato e una a livello quotidiano:

- ASR: interfaccia di comando vocale per sistemi complessi (e.g. navigazione in auto, aereo, etc) | sistema di videoscrittura digitale basata sul dettato
- DC: classificazione automatica di testi e frasi per l’interazione con chatbot di supporto online | classificazione di pagine web orientata all’ottimizzazione delle prestazioni dei motori di ricerca
- SA: analisi automatica della reputazione di un’entità sul web | classificazione di opinioni binarie su documenti con struttura specifica
- GS: creazione di testi alternativi e sommari a partire da testi più complessi | correttore sintattico per sistemi di videoscrittura
- SS: creazione di voci realistiche per l’interazione di chatbot di supporto telefonico | sintesi di annunci vocali automatici per stazioni (aeroportuali, ferroviarie, etc)
- GI: interfaccia di comando gestuale per sistemi a scarsa propagazione della voce (ambienti spaziali, subacquei, etc) | sistema di gaming entertainment basato sui movimenti

Ciascuna di queste aree presenta molti agganci e sbocchi interessanti sotto vari punti di vista e rappresenta, nel suo piccolo, una frontiera innovativa sia dal punto di vista della ricerca scientifica, sia dal punto di vista dell’evoluzione commerciale dei prodotti che usiamo quotidianamente.

Per concludere voglio introdurre un progetto attualmente in sviluppo su questo sito web. Di recente ho aggiornato una libreria che era orientata alla classificazione documentale. Questa libreria ha cambiato nome e, sebbene possa sembrare troppo generalizzato, adesso è NLP4J, cioè una libreria che vuole accrescersi cercando di fornire strumenti sempre più completi e general purpose per i temi di NLP. Ovviamente la libreria è, in tema con il progetto JOProject, open source e in Java.

Al momento NLP4J include solo il support per la classificazione documentale ma verrà presto aggiornata sia con i contributi di chiunque volesse mettere alla prova le proprie conoscenze all’interno di questo tema e instaurare una collaborazione, sia con quello che personalmente aggiungerò strada facendo. Una presentazione più dettagliata del progetto seguirà prossimanete. Nel frattempo potete visualizzare lo stato del progetto, scaricare i files relativi a sorgenti, binari e documentazione da queste pagine: pagina del progetto, forum.


Tags: , , , , , , , , , , , , , , , , ,
Pubblicato in Computer Science | 2 Commenti »