Factor-Graphs.. questi sconosciuti!

L'inferenza statistica è uno strumento veramente potentissimo in molti campi, permette di sfruttare al massimo le informazioni a disposizione, eventualmente corredate da prior distributions ecc ecc, per ricavare delle distribuzioni di probabilità che descrivono un determinato fenomeno. Ad esempio si può utilizzare una tecnica di inferenza come la belief-propagation nelle Bayesian-networks per sapere se in Cina il prezzo del sale aumenterà o diminuirà partendo dal fatto che in Italia piove ecc ecc.. eccessi a parte l'idea è che eventi fra loro apparentemente scorrelati possono influenzare tramite catene di dipendenza altri eventi, le Bayesian-networks hanno sostanzialmente lo scopo di consentire la gestione di queste dipendenze per determinare la distribuzione di probabilità di un evento a posteriori (ovvero date le informazioni disponibili).

Esistono una quantità smodata di tecniche di inferenza statistica, ma -udite udite- moltissime di esse sostanzialmente si pongono come scopo quello di marginalizzare una distribuzione di probabilità coniugata in molte variabili, spesso facilmente fattorizzabile (ad esempio utilizzando le regole relative alle distribuzioni di probabilità condizionata).

I factor-graphs sono uno strumento molto potente per la marginalizzazione di funzioni in molte variabili fattorizzabili in funzioni a poche variabili, del tipo:

data g(x1,x2,...,xn) = PRODi(f(Xi)

dove le xi sono le variabili e gli Xi sono dei sottoinsiemi (di cardinalità "bassa") delle variabili xi,

è possibile sfruttare la fattorizzazione per calcolare efficientemente:
g(xj) = SUMx1(SUMx2(...SUMxj-1(SUMxj+1(...SUMxn(g(x1,x2,...,xn))...))...))

I factor-graphs permettono di effettuare questo calcolo utilizzando un solo semplice algoritmo di nome Sum-Product-Algorithm. Tantissimi algoritmi sono rappresentabili come istanze dei factor-graphs, ad esempio l'algoritmo di Viterbi, il belief-propagation per le Bayesian-networks, forward-backward, Random Markov Fields ecc ecc Turbo-codes decoding.. e ovviamente molti altri algoritmi possono essere costruiti utilizzando lo stesso framework.

Quindi? Non state ancora leggendo l'articolo del link? Ok, allora se non avete voglia di leggere tutto il paper magari date un occhio qui per un tutorial/demo. ;)

C++.. debugging?

Allora, voglio lasciare su questo blog una bella digressione sul C++: avete mai provato a realizzare in C++ una bella libreria tutta tempestata di template, in cui utilizzate pesantemente STL (stdc++), tipi (typedef), namespace, cicici e tututu?

PROVATE!!!

Allora.. cerca che ti cerco.. e mentre sviluppo in C++ (mannaggia a me) un pezzo piuttosto grosso e importante del mio lavoro di dottorato.. come libreria ultra astratta ultra pluggabile ultra sciacquate-gli-uocchie.. tiro su il mio bel ambientino di testing con il connubio CppUnit e Automake/Autoconf/AutoTuttoQuelloCheVuoiFaccioIoNonTiDeviPreoccupareDiNullaTantoIlTuoLavoroNonFunzionaràMai..
..et voilà.. dopo ore di debugging di un test set VUOTO (tutto astratto, template dappertutto.. si inizia con il debugging della sintassi/semantica senza codice reale!).. mi salta fuori il solito errore da C++.. che uno non capisce:

/usr/local/lib/gcc/i686-pc-linux-gnu/4.0.4/../../../../include/c++/4.0.4/cstddef:52: error: '::ptrdiff_t' has not been declared
[altre 1945 righe simili]

Ok, allora.. ci ho messo 3 ore per capire FORSE come risolvere il problema.. fra altre 50 ORE vi faccio sapere se la soluzione adottata riguarda l'utilizzo di un macete a doppio taglio oppure no!

P.S.: I newsgroup mi sono serviti moltissimo in questo caso.. infatti hanno occupato inutilmente 2 di queste 3 ore.. anche ricompilare gcc con una versione più nuova mi ha aiutato.. a inchiodare una macchina per altre 2 di quelle 3 ore.. fortuna che in lab di macchine ce ne sono e si può parallelizzare il tempo!!! Parallelizzare lo spazio no he? Sarebbe utile essere qui e contemporaneamente alle maldive.. ne ho proprio bisogno!!!

Aspetti ortogonali

Come tutti ben sanno, il paradigma di programmazione per aspetti (AOP) è stato inventato appositamente per superare (o tentare di superare) le problematiche di ortogonalità fra differenti aspetti all'interno di un progetto software.

Al di là della poca diffusione e della poca risonanza che ha avuto questo paradigma (se volete un flame sul perché AOP non ha preso piede.. fate pure.. partecipo volentieri ;)), sicuramente un commento è dovuto: il problema dell'ortogonalità è diffuso in ogni dove, e tende a devastare rapidamente il risultato di moltissimi sforzi fatti da programmatori, da progettisti esperti di SE, da DBA, da CTO.. cicici e tututu! Insomma gli aspetti ortogonali rompono e parecchio!

Esempi? Allora: considerate il problema di etichettatura di dati al fine della classificazione, ad esempio chi di noi non ha incontrato l'annoso problema di memorizzare all'interno di una struttura di cartelle sensata la CATERVA di articoli scientifici raccolta in anni di lavoro? Chi di noi non si è accorto che UN ALBERO NON VA BENE? Ovvio, un albero no va bene perché esistono aspetti ortogonali che possono essere descritti solamente tramite un grafo diretto aciclico connesso (DAG). Sigle a parte la struttura dati che in questo caso avrebbe più senso è un MULTIALBERO.. se mi concedete la licenza poetica per coniare questo vocabolo. Si perchè mentre un grafo non distingue l'appartenenza degli archi a una sottostruttura, in questo caso ESISTE!

Ok ok.. sembra che io stia DIVAGANDO un po' troppo deragliando dal fulcro della questione.. ma quello che penso è che queste strutture a multialbero dovrebbero essere adottate in:
- documenti XML, dove spesso vengono solo simulate con riferimenti ovunque;
- linguaggi di programmazione, dove l'ereditarietà consente di ottenere alberi, o al più DAG;
- database, dove spesso si tenta inconsapevolmente di emularli con tabelle e query fra di esse.. ma in molti casi si tende a confondere le query con le tabelle.. soprattutto i discepoli di Access ;), in realtà il problema è che siccome i dati da qualche parte devono finire realmente, li si infila nelle tabelle e gli aspetti ortogonali li si mostra con le query.. quindi aggiungendo l'elaborazione di una query per non costruire una struttura dati adeguata (un multialbero).

L'elenco potrebbe allungarsi.. ma prima vorrei sapere.. siete d'accordo? Volete anche voi un multitagged-XML? ;)

Level-set

Cosa posso dire dei level-set? Che sono uno strumento formidabile, stupendo, comodissimo.. MA:
- l'obbligo di rappresentazione discreta ne limita l'utilizzo a 2 e 3 dimensioni.. con voxel spesso troppo grandi;
- l'elaborazione di uno o più volumi descriventi dei level set diventa oneroso data la quantità di dati da elaborare;
- la loro algebra è molto elegante dal punto di vista teorico, ma nella pratica si scontra con moltissime problematiche, soprattutto quelle di rappresentazione sopracitate.

QUINDI:
Perchè non costruire una sotto-algebra dei level-set manipolabile analiticamente in maniera comoda, così da poter rappresentare efficientemente (in spazio) i level-set per qualunque dimensionalità e da poterli manipolare efficientemente (in tempo) rimuovendo gli ostacoli che ora come ora mostrano?

IDEE:
- si può pensare di utilizzare una famiglia ristretta di funzioni distanza da comporre fra di loro;
- si può mantenere il level-set descritto analiticamente durante tutte le elaborazioni fino a quando non ne servono direttamente i dati (risultati finali o parziali);
- si possono utilizzare tecniche come marching-squares o marching-cubes per determinare l'approssimazione discreta del level-set reale a una precisione arbitraria, e solo quando serve.

Meditate, level-settatori, meditate ;)

Calcolo tensoriale e variazionale.. un simpatico connubio

Come noto, il calcolo tensoriale è uno strumento molto comodo per la manipolazione di strutture geometriche descritte in spazi curvi, ad esempio in cordinate sferiche, cilindriche, o altri arbitrari spazi curvi descritti da mappe invertibili.
Come anche è noto, il calcolo variazionale consente di minimizzare integrali al variare di un funzionale incognito, questo viene utilizzato molto in fisica ad esempio per la ricerca dello stato di equilibrio di membrane o corde elastiche.

Come trovo ovvio proporre, le due fantastiche teorie, che ad esempio mostrano applicazioni in geometria e nel mio campo dell'elaborazione delle immaigni, possono essere messe assieme, e come trovo ancora più ovvio, possono miscelarsi in maniera molto più profonda di quel che si possa pensare a prima vista (stile deformare membrane elastiche descrivendole all'interno di uno spazio curvo).

Un esempio interessante: ogni superficie semplice in 3D (che non interseca sè stessa, che non è degenere riducendosi parzialmente o completamente a una curva o un punto.. ecc ecc.. ce ne sono un po' di proprietà raggruppate sotto la "semplicità") identifica uno spazio curvo in 2D, questo mi porta a pensare immediatamente alla seguente cosa: se lo spazio curvo fosse l'incognita?

Ragionando: tramite le tecniche variazionali è possibile determinare la posizione di equilibrio di una membrana elastica rispetto a determinate forze esterne e interne di elasticità. L'equazione differenziale di Eulero-Lagrange rende esplicite tali dipendenze da tali forze. Lo scopo però è quello di determinare una superficie! Si immagini ora di avere delle entità bidimensionali immerse in \Re^2, si immagini che tali entità abbiano delle proprietà invarianti che rimangono preservate al variare dello spazio curvo in cui vengono immerse, altre proprietà varianti, che dipendono dallo spazio considerato. E' allora possibile costruire un integrale di superficie, in cui il funzionale integrando esprime le proprietà varianti locali di cui minimizzare la "somma", relative alla rappresentazione in 2D delle entità geometriche di interesse, e dipendenti da una superficie {(x,y,z)|(x=x(u,v),y=y(u,v),z=z(u,v)} con (u,v)\in\Re^2, che identifica la deformazione spaziale di \Re^2.

So che tutto questo buttato lì sembra senza senso.. però mi prodigherò nel mostrare un'applicazione pratica più tangibile.. con dettagli in più.. quando questa idea sarà più matura.

Tensor Voting

Il Tensor Voting, tecnica che si sta diffondendo molto rapidamente nella computer vision per il perceptual grouping di informazioni, non può che essere una tecnica citata in questo blog come ospite d'onore: infatti penso che non ci sia nulla di più vicino alla tecnologia, all'arte ed alla percezione di questa tecnica.
Il Tensor Voting affronta il problema di determinare le strutture percettive presenti in un insieme di punti di uno spazio a N dimensioni RN. Tali strutture vengono determinate sfruttando due principi principali:

1. La "continuazione percettiva" di strutture esistent verso il vicinato: ad esempio se osserviamo una linea tratteggiata vediamo comunque una linea, anche se in realtà si tratta solo di tanti segmenti, questo perchè eprcettivamente tentiamo a "continuare" ogni segmento verso il successivo.
2. La "morbidezza delle variazioni" delle strutture stesse: qui si intende parlare di smoothness, in questo caso il senso di questo termine è quello di mantenere il più costante possibile (minimizzarne quindi le variazioni) la curvatura delle strutture. Ad esempio la curva con curvatura costante che può unire due punti è un arco di circonferenza, non obbligatoriamente un segmento, infatti l'arco di circonferenza potrebbe evitare variazioni brusche nella derivata prima della curva in una giunzione precedente o successiva.

Non intendo descrivere qui il Tensor Voding, sarebbe decisamente ridondante (si cerci sulla rete, con autori Medioni, Tang e Mordohai), quello che intendo dare come idee.. o come riflessioni sono le seguenti:

• Esistono tutti gli strumenti matematici che permettono di lavorare algoritmicamente con il Tensor Voting.. ma nessuno strumento di analisi globale, che permetta di interpretarne i risultati.. che sono stupefacenti.. ma che non sono secondo me descritti con sufficiente rigore.. ad esempio non si parla mai dello spazio delle possibili orientazioni, o delle possibili curve, o del fatto che ogni singolo voting è uno step discreto in un automa a stati infiniti.. insomma dal punto di vista analitico manca un bel po' di lavoro (speriamo di essere io a farlo ;).
• Il Tensor Voting è una tecnica molto pontente, non ci sono dubbi.. però credo che il suo nome debba essere spezzato in due:
• Tensor: Si lavora con votanti e voti che sono tensori; i votati sono solo punti.
• Voting: Si tratta di una tecnica di voto, come ad esempio Hough; io direi che la generalizzazione del Tensor Voting più ovvia è il Voting.. una descrizione del voting come meta-tecnica di information transmission fra dati possa essere un formalismo potente, molte tecniche figlie possono essere costruite a partire da questa. Ovviamente in questo caso la matematica analitico-descrittiva del Voting sarebbe l'assoluta essenza del Voting stesso.
• Dal punto di vista computazionale ci sono vari problemi: è una tecnica che può essere resa molto veloce grazie alle giuste strutture dati, però tende ad occupare una quantità di memoria esponenziale al crescere della dimensionalità N, costruire una tecnica efficiente di sintesi dei tensori del tensor voting field per dimensionalità alte potrebbe essere molto utile.
  

Cellular Neural Networks (CNN)

Gli automi cellulari sono sempre stati considerati dei giochini interessanti, fatti per esplorare le basi più semplici della teoria del caos, osservare comportamenti e proprietà emergenti non banalmente deducibili dalle regole di evoluzione del sistema. La loro natura di "stati definiti su nodi du un lattige rettangolare bidimensionale" però li hanno sempre resi molto vicini alle problematiche di elaborazione delle immagini. Ecco qui un lavoro che permette di esplorare alcune tecniche di elaborazione di immagini basate sugli automi cellulari. Lo strumento teorico, estensione dell'automa cellulare classico, prende il nome di rete neurale cellulare (CNN). I risultati sono interessanti, anche se non mostrano nulla di non ottenibile per altre vie, in genere anche in maniera molto più efficiente.

L'idea di estendere però lo strumento affinchè sia in grado di gestire organizzazioni di cellulle in agglomerati capaci di computazione locale non sarebbe malaccio.. si immaginino delle sorte di agglomerati cellulari che si muovono nello spazio degli stati attingendo alle informazioni presenti in esso e nell'immagine, aggregazioni che magari tendono a nutrirsi di pixel a 1 nell'immagine (binaria) da elaborare, la loro evoluzione potrebbe portare ad agglomerati di cellule addensati dove sono presenti curve o aree, portando ad un perceptual grouping dei dati sparsi ed incompleti.

Potrebbe essere un campo divertente in cui giocare :)