#5 L’incredibile ubiquità della topologia persistente

da admin | 18 Agosto 2016 | Focus, top10 MaddMaths! 2015/16

C’è una branca della matematica chiamata “Topologia persistente” che ha applicazioni spesso sorprendenti all’analisi della forma e ai problemi di classificazione e recupero dei dati. Cerchiamo di capire meglio di cosa si tratta.

Pubblicato originariamente il 12 agosto 2015. Ripubblicato il 18 agosto 2016.

di Massimo Ferri

La geometria offre ottimi strumenti alla visione artificiale e alla pattern recognition. I problemi di classificazione, riconoscimento, ricerca di difetti, recupero in database estesi si risolvono talvolta trovando una trasformazione (euclidea, affine o proiettiva) che sovrapponga un’immagine a un’altra; qui l’algebra matriciale risulta vincente. Soprattutto, però, questi problemi si affrontano associando ad ogni immagine una stringa di misure geometriche (descrittori di forma) compiute su di essa ed eseguendo classificazione, riconoscimento, ecc. sulle stringhe invece che sulle immagini. Questa prassi funziona benissimo su pezzi meccanici, veicoli, oggetti rigidi: per esempio Google riconosce un monumento anche se fotografato da un’angolazione insolita. Però le cose cambiano con immagini di origine naturale; la rigidità della geometria diventa un ostacolo: riconoscere la somiglianza fra un uomo seduto e uno in piedi è problematico.

È qui che la topologia, molto più “libera” della geometria, sembra essere la carta giusta da giocare. Invece che dalla sovrapponibilità mediante trasformazioni geometriche, l‘equivalenza fra due spazi topologici \(X, Y\) è data dall’eventuale esistenza di un omeomorfismo \(\varphi: X \to Y\), cioè una funzione continua con inversa continua. L’uomo seduto e l’uomo in piedi sono omeomorfi, cioè esiste fra loro un omeomorfismo, ma non una trasformazione geometrica. Allora basta sostituire la geometria con la topologia, l’algebra matriciale con l’omeomorfismo? Purtroppo ci sono due problemi.

In genere è difficile capire se due spazi sono omeomorfi o no. Allora interviene la topologia algebrica, che associa a uno spazio degli enti (invarianti) che risultano uguali per spazi omeomorfi. Perciò se due spazi \(X, Y\) hanno invarianti diversi sono sicuramente non omeomorfi (purtroppo il viceversa non vale).

Invarianti di questo tipo sono i numeri di Betti: \(\beta_0(X)\) è il numero di componenti connesse (o 0-cicli), in pratica il numero di pezzi separati da cui è composto \(X\); \(\beta_1(X)\) conta i buchi fatti “a circonferenza” di \(X\); 1-cicli; come quello di una ciambella); \(\beta_2(X)\) conta i vuoti bidimensionali di \(X\) (come quelli di un pallone o di una camera d’aria; 2-cicli) e così via. Per capire davvero il significato di questi concetti occorrono definizioni formali; non sono male l’articolo di Wikipedia Betti number e il più generale Omologia.

C’è un secondo problema: la geometria è troppo rigida, ma la topologia è troppo libera. La battuta “per un topologo una tazza con manico e una ciambella sono la stessa cosa” è fondata: i due oggetti sono omeomorfi; si può vedere con deformazioni continue come nella Fig. 1 o nel video da cui è tratta. I numeri di Betti naturalmente coincidono: \(\beta_0=1, \beta_1=1, \beta_2=0\) eccetera per entrambi.

Fig. 1 La tazza si trasforma in ciambella (cortesia di H. Segerman e K. Crane).

L’idea base della topologia persistente è di associare il concetto di forma non solo a uno spazio topologico \(X\), ma ad una coppia \((X, f)\) dove \(f\) è una funzione continua (che chiameremo funzione filtrante) definita su \(X\), a valori solitamente nei numeri reali. A questo punto la topologia algebrica (in particolare il suo settore omologia, di cui fanno parte i numeri di Betti) viene applicata ad ogni insieme di sottolivello \(X_u\), costituito dai punti \(x\in X\)per cui \(f(x)\le u\). Per esempio possiamo mettere tazza \(X\) e ciambella \(Y\) come nella Fig.2 in basso, e usare come funzione \(f\) la quota. Entrambi gli oggetti hanno quota minima \(a\) e massima \(c\). Se \(a-\varepsilon\) è un numero appena sotto ad \(a\), allora \(X_{a-\varepsilon} = Y_{a-\varepsilon} = \emptyset\); invece \(X_c=X, Y_c=Y\). Se applichiamo l’omologia agli insiemi di sottolivello intermedi, ecco che possiamo distinguere tazza e ciambella! Infatti (Fig. 2 in alto) \(\beta_1(X_{a’})=1 \ne 0= \beta_1(Y_{a’})\) e (Fig.2 in mezzo) \(\beta_1(X_{b’})=2 \ne 1=\beta_1(Y_{b’})\). In realtà la teoria è più complicata (e più informativa) e si avvale di suoi specifici descrittori di forma: k-PBN, PD, barcode (vedi Box 1 di approfondimenti).

Fig. 2 Insiemi di sottolivello per la tazza (a sinistra) e la ciambella.

Box 1 – Descrittori di forma dalla topologia persistente

Per ogni \((X, f)\), per un fissato grado k, si considerano i possibili \(X_u, X_v\) con \(u<v\); in corrispondenza della coppia di numeri \((u, v)\) si registra quanti k-cicli di \(X_u\) sono ancora esistenti e distinti in \(X_v\). La funzione a valori interi così definita sul semipiano \(u<v\) è chiamata funzione dei Numeri di Betti Persistenti in grado k (brevemente k-PBN). Questa funzione in grado 1, per tazza e ciambella, è illustrata nella Fig. 3 in alto. Sia \(c’=c\) – (spessore del fondo della tazza); nell’1-PBN di sinistra, il trapezio di vertici \((a, a), (b, b), (b, c’), (a, c’)\) c’ informa che l’1-ciclo presente negli insiemi di sottolivello \(X_{a’}\), con (a \le a’<b\), “sopravvive” negli \(X_{b’}\) con \(a’<b'<c\) fino a “morire” in \(X_{c’}\) (“ucciso” dal fondo della tazza) e oltre. Il triangolo adiacente ci dice che i due 1-cicli di un \(X_{b’}\) con \(b \le b'<c’\) si ritrovano in tutti gli \(X_{b”}\) se \(b'<b”<c’\), ma non se \(b”\ge c’\), nel qual caso solo l’1-ciclo del manico sopravvive. Per la ciambella \(Y\) vediamo un 1-ciclo nascere a livello \(b\) e non morire mai. La stessa informazione è convogliata dai diagrammi di persistenza (PD; Fig. 3 in mezzo) e dai barcode (Fig. 3 in basso).

Fig. 3 Funzioni PBN in grado 1 (in alto), i corrispondenti PD (in mezzo) e barcode (in basso) per tazza (a sinistra) e ciambella.

La Fig. 4 mostra gli stessi descrittori in grado 0 – cioè per le componenti connesse – per le lettere M e W con l’ordinata come funzione filtrante. Questi descrittori di forma (PBN, PD, barcode) sono convenienti perché hanno sempre la stessa, semplice struttura qualunque sia il tipo di dato che li ha prodotti. Uno stesso classificatore di PBN (o PD o barcode) diventa così estremamente versatile.

Fig. 4 Omologia persistente in grado 0 per M e W.

Il concetto di 0-PBN nacque, col nome di Funzione di Taglia (Size Function), nella tesi di dottorato di P. Frosini e successivi articoli [1,2], e fiorì in collaborazione col gruppo di A. Verri a Genova per anni prima che, indipendentemente, l’idea fosse sviluppata oltreoceano [3-5]. Per questa scuola di pensiero le funzioni filtranti formalizzano gli aspetti o gli scopi che guidano l’esperto nel ritenere simili o dissimili due campioni. Con la \(f\) usata prima, per esempio, la tazza e una caraffa sono indistinguibili; il che ha senso, ma solo in una certa ottica: avremo gli stessi PBN per qualunque oggetto concavo, con un fondo e con un manico. Per certi scopi è ragionevole considerare simili un uomo seduto e uno in piedi; per altri può essere invece opportuno considerare più importante la posizione e ritenere simili un uomo e uno scimpanzé seduti. Il diverso punto di vista si può concretizzare nella scelta della funzione filtrante. Questa impostazione conferisce un’estrema applicabilità alla teoria: si ottengono PBN non solo da immagini, ma anche da superfici triangolate, da suoni, da sequenze video ecc. Come nel caso dei descrittori di forma geometrici, invece di confrontare gli oggetti di studio si confrontano i loro descrittori di forma topologici.

Abbiamo fatto cooperare fino a 25 diverse funzioni filtranti, scelte caso per caso, per classificare foglie, caratteri, firme, leucociti, disegni, profili umani, alfabeto dei segni, nei e melanomi. Le funzioni filtranti possono essere le più svariate: distanze da punti fissati, flessione, torsione, tono di grigio, altezza di una nota, ecc.

Per esempio, nella classificazione dei globuli bianchi in granulociti (eosinofili, neutrofili, basofili), monociti, linfociti, lo spazio \(X\) è il bordo della cellula. Le funzioni filtranti \(f_1, f_2, f_3\) usate associano ad ogni punto \(P\) del bordo un numero calcolato lungo il raggio \(r\) che unisce \(P\) al baricentro della cellula (Fig. 5 a sinistra): \(f_1\) associa la somma dei toni di grigio lungo \(r\), \(f_2\) ne associa la massima variazione lungo \(r\) ed \(f_3\) associa la somma delle variazioni, in valore assoluto, da pixel a pixel lungo \(r\). La Fig. 5 a destra mostra gli 0-PBN corrispondenti ad \(f_1\) per due cellule (colori diversi indicano numeri diversi).

Fig. 5 0-PBN per la classificazione di leucociti.

Con la stessa filosofia altri gruppi hanno analizzato cellule carcinomatose, microcircuiti, generi musicali e cicloni tropicali. Anche i colleghi/concorrenti di Stanford hanno recentemente adottato lo stesso punto di vista per il riconoscimento di lesioni epatiche; la motivazione che li aveva spinti a (re)inventare la topologia persistente era, invece, tutt’altra (vedi Box 2).

Le ricerche attuali riguardano soprattutto:

l’uso di funzioni filtranti con codominio \(\mathbb{R}^n\), che permettono un’applicabilità ancora maggiore,
la stabilità dei descrittori di forma (PBM, PD e barcode) rispetto a piccole variazioni delle funzioni filtranti,
il loro calcolo approssimato,
il loro confronto veloce, che al momento presenta una complessità computazionale elevata,
il rapporto con la pseudodistanza naturale, una misura di dissimilarità fra coppie del tipo \((X, f)\),
semplificazioni derivanti da simmetrie [6].

Nuove affascinanti applicazioni, che coinvolgono anche ricercatori italiani, approdano alle neuroscienze [7] e alla linguistica [8]. A chi vuole approfondire l’argomento consiglio un’introduzione formale ma scorrevole all’omologia persistente: [9].

Box 2 – Persistenza e campionamento

Curiosamente, la stessa matematica venne concepita da gruppi statunitensi [3-5] per un’esigenza del tutto diversa: ricostruire la topologia di un oggetto continuo a partire da un suo campionamento. Nella Fig. 6 i punti neri sono i punti rilevati da un sensore su un oggetto sconosciuto \(X\), di cui si vuole dedurre la forma, in particolare il numero di Betti \(\beta_1\). Una possibile ricostruzione si ottiene dilatando ogni punto in un dischetto o un poligono di diametro crescente finché si ottiene uno spazio connesso (\(\beta_0=1\)). Questo presenta tre buchi (Fig. 6 a sinistra), quindi \(\beta_1=3\); possiamo dedurre che lo stesso valga per l’oggetto reale \(X\) che abbiamo campionato? Se aumentassimo ulteriormente il diametro dei dischetti (la funzione filtrante) vedremmo due buchi sparire e ne vedremmo nascere un altro (Fig. 6 a destra); adesso \(\beta_1=2\). Ma di tutti questi buchi solo uno “persiste” lungo tutta l’espansione, perciò possiamo ragionevolmente supporre \(\beta_1(X)=1\).

Si parla di topologia, omologia “persistente” proprio perché l’informazione più rilevante è insita nei cicli con “vita” più lunga. Infatti i cicli poco persistenti (che producono triangoli piccoli nelle funzioni PBN, punti vicini alla diagonale \(u=v\) nei PD, segmenti corti nei barcode) rappresentano rumore; questo vale anche nella nostra impostazione della teoria.

Fig. 6 Dilatazione di un campionamento e 1-cicli più o meno persistenti.

Bibliografia

[1] P. Frosini, Measuring shapes by size functions, Proc. of SPIE, Intelligent Robots and Computer Vision X: Algorithms and Techniques, Boston 1991, 1607 (1992), 122-133.

[2] A. Verri, C. Uras, P. Frosini, M. Ferri, On the use of size functions for shape analysis, Biol. Cybernetics 70 (1993), 99-107.

[3] V. Robins, Toward computing homology from finite approximations, Topology Proc. 24 (1999), 503-532.

[4] H. Edelsbrunner, D. Letscher, A. Zomorodian, Topological persistence and simplification, Proc. 41st IEEE Symp. Found. Comput. Sci. (2000), 454-463.

[5] G. Carlsson, Topology and data, Bull. Amer. Math. Soc. 46.2 (2009), 255-308.

[6] P. Frosini, G. Jabłoński, Combining persistent homology and invariance groups for shape comparison, preprint, arXiv: 1312.7219 (2015).

[7] G. Petri, P. Expert, F. Turkheimer, R. Carhart-Harris, D. Nutt, P.J. Hellyer, F. Vaccarino, Homological scaffolds of brain functional networks, J. Royal Soc. Interface 11.101 (2014): 20140873.

[8] A. Port, I. Gheorghita, D. Guth, J.M. Clark, C. Liang, S. Dasu, M. Marcolli, Persistent topology of syntax, preprint, arXiv:1507.05134 (2015).

[9] H. Edelsbrunner, J. Harer, Persistent homology-a survey, Contemp. Math. 453 (2008), 257-282.