View Full Version : [Algoritmo] Pattern Recognition generica per AI
Salve,
è da un pò che mi trastullo con l'idea di creare una AI, o almeno qualcosa di vagamente "smart".
In barba a reti neurali, riconoscimento visivo etc, ho deciso di affrontare il problema dal punto di vista dell'intelligenza associativa.
Quindi sto provando a trovare un algoritmo che riesca a classificare informazioni generiche "premasticate" sotto forma di Simboli astratti.
Per ora tutto ciò è allo stato di epica se*a mentale, ma si fa just for fun :D
All'interno di questa faccenda, ora ho un problema abbastanza "isolato":
ho due pseudo alberi n-ari in cui i nodi sono Simboli; ogni Simbolo ha n Simboli figli non distinti, ma a cui viene assegnata una posizione relativa al Nodo corrente.
Quindi ad esempio, "pizza" ha come figli "p" "i" "z" "z" "a", in cui Z è lo stesso simbolo, ma prima in posizione 3 e poi 4.
Questo è fondamentale ai fini del funzionamento del programma (credo) e deve valere anche per sequenze di sequenze, es:
"cane gatto cane" deve strutturarsi come "cane" "g" "a" "t" "t" "o" "cane", in cui cane è lo stesso simbolo ed è composto a sua volta da lettere semplici.
Quello che voglio fare è, dati due Simboli (quindi due alberi) trovare tutte le sottosequenze interne a questi due simboli che sono in comune tra i due, per estrarle e renderle un simbolo figlio.
Esempio, ho "pizza ai funghi" e "pizza margherita" come Simboli composti da lettere semplici.
L'algoritmo deve riconoscere la sequenza "pizza" e renderla un simbolo a parte.
Il problema è che queste sequenze possono essere traslate, ripetute (e scalate e rotate, se vengono da una sorgente visiva).
Quindi non basta affatto tenere conto della posizione assoluta.
Al momento ho costruito un Iteratore che proietta tutte le componenti del Simbolo nello stesso spazio di riferimento, poi mi sono perso :D
Chissà se qualcuno avrà il coraggio di leggersi tutto ciò :asd:
PS: non mi importa minimamente delle prestazioni, basta che sappia fare quello che serve... per ottimizzare c'è sempre tempo.
Nessuno? :stordita:
:asd:
cdimauro
13-12-2010, 05:08
Per traslate, scalate e ruotate cosa intendi?
Per traslate, scalate e ruotate cosa intendi?
Beh una "sequenza", quando si connette una sorgente visiva, potrebbe essere per esempio un cartello stradale di divieto di sosta.
Non ci possiamo aspettare che nell'immagine in input appaia sempre al centro, non ruotato e della grandezza "normale";
probabilmente apparirà ai lati, ruotato di qualcosa, e scalato dalla prospettiva.
Lo stesso vale se voglio fare uno scan OCR su una fotografia: le lettere potrebbero trovarsi in qualsiasi posizione.
Ma le informazioni nel database, in entrambi i casi, contemplano solo il simbolo centrato a 0,0 non scalato e non ruotato.
Quindi bisognerebbe cercarli all'interno dell'input in tutte le posizioni possibili, con ogni rotazione e dimensione possibile.
Certamente c'è un modo per non farlo :read:
banryu79
13-12-2010, 11:00
Beh una "sequenza", quando si connette una sorgente visiva, potrebbe essere per esempio un cartello stradale di divieto di sosta.
Non ci possiamo aspettare che nell'immagine in input appaia sempre al centro, non ruotato e della grandezza "normale";
probabilmente apparirà ai lati, ruotato di qualcosa, e scalato dalla prospettiva.
Lo stesso vale se voglio fare uno scan OCR su una fotografia: le lettere potrebbero trovarsi in qualsiasi posizione.
Ma le informazioni nel database, in entrambi i casi, contemplano solo il simbolo centrato a 0,0 non scalato e non ruotato.
Quindi bisognerebbe cercarli all'interno dell'input in tutte le posizioni possibili, con ogni rotazione e dimensione possibile.
Certamente c'è un modo per non farlo :read:
Beh, ma rispetto all'esempio che hai fatto sopra (relativo ad uno spazio monodimensionale, il vettore del testo in ingresso) qua sei già passato ad uno spazio bidimensionale (non a caso parli di "lati").
Se poi si comicia a tirare i ballo OCR e compagnia bella direi che la complessità cresce a dismisura: anche perchè, data una immagine come input, cosa deve riuscire a riconoscere il tuo software?
Non ho capito se devi risconoscere "solo" dei glifi che potrebbero rappresentare del testo o anche altro (appunto cartelli, case, persone ecc...)
Il mio software deve riconoscere le "ricorrenze", cioè quelle disposizioni di simboli in ingresso che vengono ripetute spazialmente o temporalmente.
In maniera del tutto generica, non voglio riconoscere niente di preciso al momento.
Sono passato tra i 2 casi in 2 esempi diversi proprio perchè by design il caso dello stream di testo DEVE essere analogo a quello 2D.
L'algoritmo deve funzionare nello spazio di qualsiasi sorgente venga connessa, che sia testo, suoni, immagini o video.
Diciamo che è l'"obiettivo filosofico" che mi sono posto.
Quindi lo stream di caratteri "pizza" è un pattern ricorrente esattamente quanto un cartello di divieto di sosta o un carattere stampato su carta.
Quello che deve fare il programma è appunto rendersi conto che una parte dell'input "sa di già visto" e quindi estrarla e farne un pattern a parte nell'albero dei componenti.
nel caso dell'OCR, quando poi il programma riconosce il glifo "a", tu gli insegni a connetterlo al carattere "a" (che sono due cose diverse).
E così quando riconoscerà il glifo a, ti risponde il carattere a. Ma appunto leggere è solo una delle cose che puoi insegnargli a fare :read:
EDIT:
se potesse servire, beccatevi la repository di quello che ho buttato giù finora (http://bitbucket.org/tommo89/openmind/overview).
Al momento purtroppo non fa molto perchè ho commentato il merge dell'input.
Il problema messo in questa ottica mi sembra che sia un "semplice" problema di pattern recognition. Quindi ad esempio potresti dare uno sguardo alla teoria decisionale bayesiana.
Il problema messo in questa ottica mi sembra che sia un "semplice" problema di pattern recognition. Quindi ad esempio potresti dare uno sguardo alla teoria decisionale bayesiana.
Mmh in che modo? Non l'ho mai sentito dire e non trovo references decenti :D
Mmh in che modo? Non l'ho mai sentito dire e non trovo references decenti :D
Sinceramente non l'ho mai approfondito, ma è un approccio di tipo statistico per la creazione di algoritmi di pattern recognition.
Giusto per farti un esempio: i filtri antispam molto spesso sono di tipo bayesiano.
http://www.cedar.buffalo.edu/~srihari/CSE555/
http://cgm.cs.mcgill.ca/~godfried/teaching/pr-web.html
Come vedi ci sono anche libri.
cdimauro
13-12-2010, 19:36
Per com'è esposto il problema, la penso come te. Tra l'altro c'è parecchio materiale in letteratura.
Il mio unico dubbio a questo punto è se una roba del genere si possa utilizzare per sviluppare un'IA. Ho forti dubbi in proposito.
Per com'è esposto il problema, la penso come te. Tra l'altro c'è parecchio materiale in letteratura.
Il mio unico dubbio a questo punto è se una roba del genere si possa utilizzare per sviluppare un'IA. Ho forti dubbi in proposito.
Beh ovviamente è un'AI all'acqua di rose, forse è meglio vederla come un motore di ricerca particolarmente intelligente, o come la base associativa di un'AI più grande. E poi vi ho esposto solo una parte minima della faccenda :D
Comunque per come è ora non sarà mai capace di planning, di logica, di ragionamenti quantitativi etc (ma ho in mente roba per questo)
Però ho qualche progettino web per cui sarà comunque utile in questo stato :D
@cionci: non va per niente bene, purtroppo.
Ancora una volta, io non devo estrarre dei pattern da una sorgente raw, i dati sono premasticati in forma di Simboli dalle Sorgenti.
Un algoritmo che stima probabilisticamente UN pattern pesando la lightness dei pixel di un'intera immagine è quanto di più lontano da quello che ho in mente.
E quindi il mio problema è molto più facile, perchè ho un set molto ridotto di punti con le loro coordinate e il loro "significato" stabilito.
Devo solo trovare un modo di individuare tutte le sottodisposizioni in comune tra 2 set di punti casuali.
cdimauro
14-12-2010, 06:21
Puoi usare comunque dei meccanismi di pattern matching, ma non so quanto possa essere pesante l'operazione.
Servirebbe indicizzare opportunamente i dati in modo da facilitare la ricerca e il match del (sub)pattern, ma al momento non mi viene in mente nulla.
@cionci: non va per niente bene, purtroppo.
Ancora una volta, io non devo estrarre dei pattern da una sorgente raw, i dati sono premasticati in forma di Simboli dalle Sorgenti.
Un algoritmo che stima probabilisticamente UN pattern pesando la lightness dei pixel di un'intera immagine è quanto di più lontano da quello che ho in mente.
E' uguale, cambiano le modalità, ma Bayes è comunque applicabile. L'elaborazione del sorgente è solo il primo passo per presentare i dati all'algoritmo. La teoria di Bayes è applicabile comunque anche al tuo.
Tu passerai tutti i pattern all'algoritmo di decisione che ti dirà con quale percentuale il pattern si trova all'interno dell'input.
Puoi usare comunque dei meccanismi di pattern matching, ma non so quanto possa essere pesante l'operazione.
Servirebbe indicizzare opportunamente i dati in modo da facilitare la ricerca e il match del (sub)pattern, ma al momento non mi viene in mente nulla.
E' uguale, cambiano le modalità, ma Bayes è comunque applicabile. L'elaborazione del sorgente è solo il primo passo per presentare i dati all'algoritmo. La teoria di Bayes è applicabile comunque anche al tuo.
Tu passerai tutti i pattern all'algoritmo di decisione che ti dirà con quale percentuale il pattern si trova all'interno dell'input.
Ecco, magari in questa ottica Bayes puo' avere un suo ruolo.
Il problema fondamentale e' "passare tutti i pattern" infatti i pattern da riconoscere non sono conosciuti a priori, una disposizione qualsiasi viene estratta dal rumore solo perche' ad un certo punto si ripete.
In effetti hanno ragione quei paper sul fatto che la mente umana ha un suo set di "expected patterns" che ricerca nell'input, ma appunto non voglio realizzare proprio un'AI.
Se implementassi una cosa del genere (sarebbe facile) l'apprendimento diventerebbe molto piu' lento e "soggettivo", non proprio eccellente se poi vai ad usare la tech in un motore di ricerca, per dirne una.
cdimauro
15-12-2010, 13:05
Non penso che sia complicato, tutto sommato.
Al momento puoi utilizzare un algoritmo di tipo "forza bruta" che, dato un albero, lo visiti nodo per nodo, e per ogni nodo richiami una funzione "di somiglianza" che prende come argomento il nodo stesso e un altro albero, restituendo un albero (anche vuoto) che rappresenti la parte "somigliante" al nodo.
Non penso che sia complicato, tutto sommato.
Al momento puoi utilizzare un algoritmo di tipo "forza bruta" che, dato un albero, lo visiti nodo per nodo, e per ogni nodo richiami una funzione "di somiglianza" che prende come argomento il nodo stesso e un altro albero, restituendo un albero (anche vuoto) che rappresenti la parte "somigliante" al nodo.
Eh il fatto è che messa così, come "altro albero" è valido considerare ogni singola sottodisposizione possibile dell'input, che ricordo è disposto in uno spazio 3D.
Quindi prima tutti i simboli presi uno ad uno, poi tutte le coppie, poi tutte le terne... il numero totale di robe da verificare va rapidamente ad esplodere.
mmh è uno di quei problemi che "a occhio" sono semplici ma poi :D
wingman87
16-12-2010, 00:36
Eh il fatto è che messa così, come "altro albero" è valido considerare ogni singola sottodisposizione possibile dell'input, che ricordo è disposto in uno spazio 3D.
Quindi prima tutti i simboli presi uno ad uno, poi tutte le coppie, poi tutte le terne... il numero totale di robe da verificare va rapidamente ad esplodere.
mmh è uno di quei problemi che "a occhio" sono semplici ma poi :D
Prima tutti i simboli presi uno ad uno, poi per ogni match ottenuto cerchi lì le coppie, poi per ogni match le terne e via così.
Comunque se formalizzassi meglio il problema sarebbe più facile rifletterci sopra perché ancora non sono sicuro di aver capito bene tutto.
Prima tutti i simboli presi uno ad uno, poi per ogni match ottenuto cerchi lì le coppie, poi per ogni match le terne e via così.
Comunque se formalizzassi meglio il problema sarebbe più facile rifletterci sopra perché ancora non sono sicuro di aver capito bene tutto.
Eh questo ha senso. Avevo pensato a limitarmi ai match sui simboli uno ad uno, ma è probabile che compaiano sempre tutti... però salendo alle coppie etc si sgrossa parecchio lavoro.
Inoltre inserendo i matches in uno stack così come sono trovati, esce il vettore ordinato dei risultati :D
Ordinato perchè se scrivo "pizza" sarò interessato prima di tutto al fatto che ha trovato "pizza" nel database, e poi ad eventuali sottopattern meno interessanti.
Magari posso inserire il concetto di "distanza", così che quando passo da coppia a terna (o da n a n+1) considero per l'estensione solo i simboli che compaiono ad una distanza utile.
Il che ha senso perchè non sono interessato veramente a "qualsiasi" combinazione, solo quelle i cui simboli sono piuttosto adiacenti.
In che senso formalizzare meglio? Sarei felice di farlo se potessi formalizzarlo a me stesso :asd:
E' che "so" cosa voglio che faccia, ma molti dettagli non sono fissati, ad esempio le parole in corsivo di cui sopra :D
Cmq thanks, sperimenterò.
cdimauro
16-12-2010, 04:37
Intanto formalizza cos'è un "simbolo". Finora mi sembra d'aver capito che può essere un singolo carattere, o una sequenza di caratteri, giusto?
Un Simbolo è un albero di simboli, connesso in un grafo pesato diretto ad altri simboli (grafo di composizione + grafo di associazione).
Un Simbolo ha un metodo "getAffinity" che restituisce la somiglianza ad un'altro simbolo dato.
Tutto qua :D
Cosa può essere è volutamente trascurato, in maniera da poter lasciare la completa libertà a chi va ad implementare getAffinity nelle sottoclassi, i cosiddetti "simboli primitivi".
I simboli primitivi sono le foglie di un'albero di simboli, e implementano getAffinity direttamente sul proprio contenuto.
Per ora ho creato una sola sottoclasse, cioè CharacterSymbol, che wrappa un carattere unicode, ma idealmente si vorrebbe creare una sottoclasse di Symbol per ogni Sorgente che aggiungiamo al sistema tramite plugin.
Ad esempio una sorgente visiva potrebbe avere come simboli base linee, colori e contrasti; una sonora potrebbe avere l'intensità e il pitch del suono; una di movimento gli sforzi da applicare ad un motore; etc.
La cosa che fa avvicinare questo accrocchio ad una AI, imho, è proprio che dovrebbe riuscire ad associare dati dalle fonti più disparate senza programmazione esplicita per farlo, es:
riconosco una faccia? faccio un movimento.
Cmq dato che ci si può appoggiare a getAffinity l'algoritmo di wingman87 è fattibile :read:
cdimauro
16-12-2010, 20:30
Un Simbolo è un albero di simboli, connesso in un grafo pesato diretto ad altri simboli (grafo di composizione + grafo di associazione).
Un Simbolo ha un metodo "getAffinity" che restituisce la somiglianza ad un'altro simbolo dato.
Tutto qua :D
Cosa può essere è volutamente trascurato, in maniera da poter lasciare la completa libertà a chi va ad implementare getAffinity nelle sottoclassi, i cosiddetti "simboli primitivi".
I simboli primitivi sono le foglie di un'albero di simboli, e implementano getAffinity direttamente sul proprio contenuto.
Per ora ho creato una sola sottoclasse, cioè CharacterSymbol, che wrappa un carattere unicode, ma idealmente si vorrebbe creare una sottoclasse di Symbol per ogni Sorgente che aggiungiamo al sistema tramite plugin.
Ad esempio una sorgente visiva potrebbe avere come simboli base linee, colori e contrasti; una sonora potrebbe avere l'intensità e il pitch del suono; una di movimento gli sforzi da applicare ad un motore; etc.
La cosa che fa avvicinare questo accrocchio ad una AI, imho, è proprio che dovrebbe riuscire ad associare dati dalle fonti più disparate senza programmazione esplicita per farlo, es:
riconosco una faccia? faccio un movimento.
Cmq dato che ci si può appoggiare a getAffinity l'algoritmo di wingman87 è fattibile :read:
Il fatto di avere a che fare con alberi va bene, rende omogeneo l'approccio al problema.
Ma i grafi a che servono? Non ne avevi parlato prima.
Finora ero rimasto a due alberi di cui estrarre delle informazioni di similitudine. O sbaglio?
Il problema è associare, ad esempio, una linea disegnata su una sorgente video proprio ad una linea. Cioè serve un algoritmo per farlo (tutt'altro che banale).
Ed in questi casi non basta fare un matching esatto fra i simboli che compongono l'input, ma bisogna fare una ricerca approssimata.
In sostanza l'algoritmo ti dovrà dire che in una certa posizione della sorgente c'è un dato pattern con una certa probabilità.
Inoltre per il formato intrinseco delle varie sorgenti, l'algoritmo di riconoscimento dovrà variare da sorgente a sorgenti. Basta pensare ad una sorgente monodimensionale come un file di testo o ad una sorgente bidimensionale come una immagine.
Mi ero perso le risposte al thread, uni del cavolo :D
Il fatto di avere a che fare con alberi va bene, rende omogeneo l'approccio al problema.
Ma i grafi a che servono? Non ne avevi parlato prima.
Finora ero rimasto a due alberi di cui estrarre delle informazioni di similitudine. O sbaglio?
Allora, ci sono 2 grafi
-il grafo di Composizione è composto dagli alberi di cui discutevamo; è un grafo e non un albero, per questo è importante che i simboli vengano riconosciuti e riutilizzati.
E' un grafo "speciale" perchè partendo da un qualsiasi nodo, si vede un albero.
L'albero risultante ci dice tutte le sotto-componenti del nodo dato...
l'idea è costruire il riconoscimento di aggregati di simboli in maniera ricorsiva.
-poi c'è il Grafo di Associazione, che forse non avevo citato per bene:
è un grafo direzionato che collega i simboli (sempre gli stessi del primo grafo) a livello paritetico, cioè, tramite dei pesi ci dice quale simbolo "richiama" quale altro simbolo.
Viene costruito per "vicinanza", cioè un arco tra 2 simboli viene costruito o rinforzato quando 2 simboli compaiono vicini nello spazio dell'input.
Ad esempio, 2 parole che compaiono vicine in una frase.
E' importante perchè mentre l'altro grafo ci dice quali simboli sono stati riconosciuti ORA, questo ci dice quali simboli in passato sono stati riconosciuti vicino a quello dato.
Rappresenta la memoria associativa, in poche parole.
@Cionci: questo secondo grafo è quello che risolve il problema che poni.
L'algoritmo che estrae i simboli dalla sorgente video è invece piuttosto semplice, perchè estrae solo i "simboli primitivi", cioè punti, linee, colori e contrasti. Niente che software esistente non faccia agile (OpenCV?).
Il punto è proprio che per riconoscere simboli composti ci si affida alle capacità della "AI".
Quindi non serve nessun algoritmo specifico, basta che la linea compaia qualche volta nello stesso input di qualcos'altro, e i due simboli verranno in futuro richiamati insieme.
Es di procedimento: il pattern del carattere scritto "a" viene riconosciuto dalle sue features con un albero di composizione (grafo 1).
A questo punto si interroga il grafo di associazione, e viene fuori che il simbolo del carattere ASCII "a" è il closest match.
Si prende quel simbolo risultato e si manda in output.
La sorgente "console a riga di comando" lo intercetta e lo stampa.
Hai fatto un OCR :D
PS: Associare due sorgenti diverse è scontato, perchè gli input di tutte le sorgenti vengono "unificati" prima del riconoscimento finale nello stesso spazio di input, formando un solo simbolo che contiene il "contesto corrente". E' un pò una forzatura, ma ci si può lavorare :D
RIEDIT:
ho pescato questo Google n-gram database (http://ngrams.googlelabs.com/datasets) che contiene tutte le sequenze di massimo 5 parole ricorrenti in tutto il database di Google Books... se costruissi il grafo di composizione da questo si avrebbe? Boh :asd:
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.