[Algoritmo] Pattern Recognition generica per AI

[Tommo]

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

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

Chissà se qualcuno avrà il coraggio di leggersi tutto ciò

PS: non mi importa minimamente delle prestazioni, basta che sappia fare quello che serve... per ottimizzare c'è sempre tempo.

[Tommo]

Nessuno?

[cdimauro]

Per traslate, scalate e ruotate cosa intendi?

[Tommo]

Originariamente inviato da cdimauro

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

[banryu79]

Originariamente inviato da Tommo

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

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...)

[Tommo]

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

EDIT:
se potesse servire, beccatevi la repository di quello che ho buttato giù finora.
Al momento purtroppo non fa molto perchè ho commentato il merge dell'input.

[cionci]

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.

[Tommo]

Originariamente inviato da cionci

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

[cionci]

Originariamente inviato da Tommo

Mmh in che modo? Non l'ho mai sentito dire e non trovo references decenti

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]

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.

[Tommo]

Originariamente inviato da cdimauro

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
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

@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]

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]

Originariamente inviato da Tommo

@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.

[Tommo]

Originariamente inviato da cdimauro

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.

Originariamente inviato da cionci

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]

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.

[Tommo]

Originariamente inviato da cdimauro

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

[wingman87]

Originariamente inviato da Tommo

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

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.

[Tommo]

Originariamente inviato da wingman87

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
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
E' che "so" cosa voglio che faccia, ma molti dettagli non sono fissati, ad esempio le parole in corsivo di cui sopra

Cmq thanks, sperimenterò.

[cdimauro]

Intanto formalizza cos'è un "simbolo". Finora mi sembra d'aver capito che può essere un singolo carattere, o una sequenza di caratteri, giusto?

[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