[Algoritmo] Pattern Recognition generica per AI

[cdimauro]

Originariamente inviato da Tommo

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

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

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?

[cionci]

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.

[Tommo]

Mi ero perso le risposte al thread, uni del cavolo

Originariamente inviato da cdimauro

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

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

RIEDIT:
ho pescato questo Google n-gram database 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