martedì 31 maggio 2016

Gli adroni come bisturi di precisione

 

E’ di solo pochi giorni fa la notizia di una bimba di 9 anni affetta da un tumore raro (cordoma) che interessa i due estremi della colonna vertebrale curata con i protoni. La terapia che è stata messa in atto si basa sull’utilizzo di fasci di protoni e ioni pesanti. Si tratta di una tecnica all’avanguardia per il trattamento dei tumori più precisa e che provoca meno danni ai pazienti. Nel mondo non sono molti i centri che utilizzano questo tipo di cura: a livello mondiale sono soltanto 48. Vediamo di capire allora come funziona questa nuova e promettente tecnica di bombardamento. Non e’ la prima volta e non sara’ nemmeno l’ultima che la ricerca fondamentale ha ricadute molto importanti nel campo della medicina. Le proprieta’ quantistiche della materia, le radiazioni, l’antimateria, gli acceleratori di particelle e i rivelatori, sono usciti dai laboratori dei fisici per entrare nel mondo degli ospedali per aiutare i medici a guardare dentro i nostri corpi e curare diverse patologie tra cui il cancro. Questo termine indica un processo patologico caratterizzato dall’abnorme accrescimento di un tessuto che determina la comparsa di una tumefazione localizzata con disturbi legati a distruzione del tessuto normale preesistente, a compressione di strutture vicine o a ostruzioni di visceri cavi con ristagno dei secreti in essi contenuti.

In tutti i tumori si riconoscono due componenti di base:

1. il parenchima costituito dalle cellule neoplastiche o trasformate, ovvero quelle cellule che hanno subito un’alterazione genica che causa la crescita anormale del tessuto.

2. lo stroma che funge da sostegno per la massa tumorale ed `e composto da tessutto connettivo e vasi sanguigni.

Sebbene siano le cellule parenchimali a costituire la parte proliferativa della neoplasia, la crescita e l’evoluzione tumorale sono strettamente connesse e influenzate dallo stroma: e’ quest’ultimo infatti che fornisce la struttura di sostegno su cui proliferano le cellule trasformate.

L’evoluzione della maggior parte dei tumori maligni puo’ essere divisa in quattro fasi:

· modificazione maligna delle cellule bersaglio, denominata trasformazione;

· crescita delle cellule trasformate;

· invasione locale

· e, infine, metastasi a distanza (cioe’ localizzazione secondarie a distanza).

clip_image002

La crescita della massa tumorale e la sua velocita’ e’ determinata dalla differenza tra il numero di cellule alterate prodotte e le cellule perse (apoptosi – eliminazione di cellule alterate tramite meccanismo di morte programmata come avviene per esempio nell’embrione umano durante la differenziazione delle dita delle mani e dei piedi generando la morte delle cellule che costituiscono le membrane interdigitali di mani e piedi palmati). In genere, lo squilibrio tra cellule prodotte e cellule perse e’ piu’ alto nei tumori con una frazione di crescita alta. Alcuni linfomi, leucemie e carcinomi polmonari sono caratterizzati da frazioni di crescita elevate e si manifesta un decorso clinico estremamente rapido: il tumore si dice aggressivo. Tumori piu’ largamente diffusi, come il tumore alla mammella e al colon hanno una bassa frazione di crescita e la produzione cellulare supera la perdita di appena il 10 per cento. Il ritmo di accrescimento e’ dunque molto piu’ lento. La frazione di crescita delle cellule tumorali ha un notevole impatto sulla loro suscettibilita’ alla chemioterapia (trattamento terapeutico a base di sostanze chimiche). La maggior parte dei farmaci contro il cancro, infatti, agisce sulle cellule che si trovano nel ciclo replicativo; percio’ i tumori che hanno una frazione di crescita bassa, ad esempio solo del 5 per cento, avranno una crescita lenta, ma saranno refrattari ai trattamenti chemioterapici classici. In questi casi, si ricorre ad altre tecniche di riduzione della massa tumorale di tipo non farmacologico, ad esempio la radioterapia (di cui parleremo a breve) o l’intervento chirurgico. Lo scopo e’ ridurre il numero di cellule tumorali che si trovano nella fase G0 (cellule in una fase di quiescenza temporanea o irreversibile, o in altri termini che hanno interrotto la fase di replicazione) del ciclo cellulare, in modo che le cellule tumorali residue tendano ad entrare nel ciclo replicativo e pertanto diventino sensibili all’azione dei farmaci. Al contrario, tumori aggressivi (come certi linfomi) che contengono un gran numero di cellule nel ciclo replicativo si dissolvono con la chemioterapia e possono anche essere guariti.

Nella crescita di un tumore, inoltre, si distinguono due fasi: una prima fase di evoluzione avascolare e una seconda fase caratterizzata dalla capillarizzazione della massa tumorale. I tumori, infatti, stimolano la crescita dei vasi ematici dell’ospite, processo detto angiogenesi, che e’ essenziale per rifornire di sostanze nutritive le cellule tumorali. Fintanto che la massa tumorale e’ poco estesa (un diametro o uno spessore inferiore ai 2mm), le cellule tumorali riescono a ricevere l’apporto di nutrienti e ossigeno necessari alla loro vita per diffusione dai capillari gia’ esistenti, ma per superare tale soglia e’ necessario un processo di vascolarizzazione. Durante la crescita del tumore, alcune cellule acquisiscono un fenotipo angiogenetico, che gli permette di produrre segnali che inducono la proliferazione delle cellule endoteliali (quelle che rivestono l’interno dei vasi sanguigni e di quelli linfatici), che vanno a costituire i nuovi vasi ematici. Il cambiamento da tumore avascolare a tumore vascolare e’ detto switch angiogenetico. Contrariamente ai vasi normali, i vasi di origine tumorale possono crescere in continuazione, sotto l’azione di fattori di crescita specifici come il VEGF (la proteina piu’ importante di questa categoria e’ il VEFG-A), e costituiscono un sistema ematico irregolare e dalla forma tortuosa. Questo fa si che non tutte le cellule del tumore ricevano il nutrimento necessario, e quindi si creano delle necrosi all’interno della massa tumorale stessa. La vascolarizzazione del tumore e’ una delle condizioni che favorisce maggiormente l’invasivita’ e la metastatizzazione dei tumori maligni. Proprio perche’ l’angiogenesi e’ determinante per la crescita e la diffusione dei tumori, nelle terapie e’ rivolta una grande attenzione ai farmaci che inibiscono questo processo. Rientrano in questa categoria i nuovi farmaci biologici monoclonali come l’avastin (bevacizumab) la cui azione e’ schematizzata nelle immagini sottostanti. In parole semplici l’azione di questi farmaci e’ quella di bloccare i VEGF prodotti dalle cellule tumorali e responsabili della crescita anomala dei vasi sanguigni.

clip_image003

Per quanto riguarda la velocita’ di crescita questa e’ correlata al livello di differenziazione cellulare: meno e’ alto il livello di differenziazione piu’ `e veloce la crescita. Quindi la maggior parte dei tumori maligni cresce piu’ rapidamente rispetto i tumori benigni. Inoltre, la velocita’ di crescita e’ spesso non costante nel tempo perche’ fattori come la stimolazione ormonale, l’adeguatezza dell’apporto ematico e altri fattori ad oggi ancora poco conosciuti possono condizionare la cinetica cellulare. Questo rende la crescita e dimensione di un tumore praticamente impredicibile.

La terza fase, quella dell’invasione locale, avviene in modo differente per tumori benigni e maligni. Quasi tutte le neoplasie benigne crescono formando masse compatte ed espansive che restano localizzate nella loro sede di origine e non hanno la capacita’ di infiltrare gli organi circostanti o invadere a distanza. Poiche’ la loro espansione e’ piuttosto lenta, sviluppano al loro intorno un tessuto connettivo fortemente compresso, detto capsula fibrosa, che li separa dal tessuto d’origine. La crescita dei tumori maligni, invece, e’ accompagnata da una progressiva infiltrazione, invasione e distruzione dei tessuti circostanti. Solitamente le neoplasie maligne sono poco demarcate dal tessuto normale circostante e hanno una crescita irregolare e disomogenea. I tumori maligni a lenta espansione possono sviluppare una capsula fibrosa, ma, generalmente, sviluppano anche delle filiere di cellule che infiltrano le strutture adiacenti.

Queste filiere sembrano al microscopio delle chele di granchio e per questo il tumore maligno e’ anche detto cancro. Nella loro espansione i tumori maligni non rispettano, in genere, i normali confini anatomici e questo rende difficile l’intervento chirurgico di asportazione e, anche qualora il tumore apparisse compatto e ben circoscritto, e’ sempre necessario asportare anche una parte di tessuto sano limitrofo. L’invasivita’ dei tessuti circostanti e’ una delle principali caratteristiche del decorso clinico che permette di distinguere un tumore maligno da uno benigno.

La quarta fase, quella delle metastasi, e’ caratteristica solo delle neoplasie maligne. Le metastasi sono impianti di tumore lontani dal tumore primitivo. L’invasivita’ che caratterizza i tumori maligni permette loro di penetrare nei vasi ematici e linfatici nonche’ nelle cavita’ del corpo. Quelle appena indicate sono le tre principali vie di diffusione per i tumori maligni, che danno l’opportunita’ al cancro di diffondere in altre sedi. Solitamente, tanto piu’ il tumore primitivo e’ aggressivo e di rapido accrescimento, maggiore e’ la possibilita’ che metastatizzi o abbia gia’ metastatizzato.

Piu’ si studiano i tumori e piu’ si capisce quanto essi siano purtroppo intelligenti. Non c’e’ dubbio che come tutte le cellule anche quelle tumorali soddisfano il principio di evoluzione di Darwin e quindi escogitano nuove strategie pur di sopravvivere. Tra queste ricordiamo quelle messe a punto dal tumore del pancreas per ingannare il sistema immunitario o quelle del glioblastoma (tumore del cervello) che e’ in grado di trasformare alcune delle proprie cellule in vasi sanguigni per potersi cosi autoalimentare. Per questo motivo laddove la chirurgia e la chemioterapia non sono d’aiuto e’ possible utilizzare tecniche alternative date in prestito alla medicina dalla fisica nucleare e particellare. L’idea di base e’ di utilizzare le radiazioni per danneggiare il DNA delle cellule tumorali e determinarne cosi la morte.

clip_image004

Tra queste tecniche ricordiamo la radioterapia (generalmente raggi X), i fotoni di alta energia (raggi gamma), generati da sorgenti radioattive, quali il cobalto-60, oppure i fasci di elettroni. Questa radiazione viene indirizzata sull’organismo in corrispondenza del tessuto tumorale e, una volta dentro il corpo, viene assorbita durante il suo percorso da tutti i tessuti e gli organi, non soltanto laddove c’è un tumore, generando i ben noti effetti secondari. Questo, tra l’altro, limita la quantità di radiazione che si può utilizzare, in quanto un utilizzo massiccio mette a rischio la vita stessa del paziente. Una nuova tecnica a disposizione degli oncologi per combattere il cancro e’ quella dell’adroterapia in cui le cellule malate vengono sparate con un acceleratore di particelle.

Fasci di protoni oppure di ioni di carbonio, provenienti da acceleratori dedicati, sono utilizzati con grande successo per il trattamento dei tumori localizzati. L’idea di utilizzare i protoni per il trattamento dei tumori fu proposta nel 1946 da R.R. Wilson ed è stata applicata per la prima volta nel 1954 nel laboratorio di ricerca di fisica nucleare del Lawrence Berkeley National Laboratory, in California, Stati Uniti. In Europa il metodo è stato utilizzato in Svezia, a Uppsala, per la prima volta nel 1957, utilizzando un acceleratore che era stato costruito per ricerche di fisica fondamentale. Da allora, la tecnica si è molto perfezionata ed estesa in tanti paesi del mondo, inclusa l’Italia. Il nome della terapia deriva dal fatto che le particelle che vengono utilizzate, protoni oppure ioni di carbonio, sono adroni – particelle cioe’ composte da quark e che subiscono interazioni forti.

clip_image006

I protoni e gli ioni di carbonio utilizzati nell’adroterapia grazie a delle macchine chiamate acceleratori vengono portati ad una certa energia, che dipende dalla tipologia e localizzazione del tumore, e indirizzati con precisione elevatissima sul paziente.

clip_image008

clip_image010

Entrati nell’organismo, a differenza dei fasci di fotoni o di elettroni, viaggiano sino ai tessuti tumorali danneggiando pochissimo gli altri tessuti, rilasciando invece un’enorme quantità di energia, nel tessuto tumorale. I tessuti sani subiscono pochi danni, mentre quelli malati sono distrutti. Come si puo’ notare dal grafico sottostante la dose massima di energia rilasciata dai protoni e’ piu’ in profondita’ rispetto a quella dei raggi X. Il picco di rilascio dell’energia da parte dei protoni e’ chiamato picco di Bragg.

clip_image012

Controllando l’energia dei fasci si può controllare il posto dove questi rilasciano la loro carica distruttiva nell’organismo. Per tumori superficiali l’energia è più piccola che per un tumore profondo. La terapia con ioni di carbonio ha il vantaggio di avere una maggiore densità di ionizzazione rispetto a quella dei protoni. In questo modo i danni della struttura del DNA all’interno della cellula tumorale si verificano più frequentemente e così diventa più difficile per la cellula cancerosa riparare il danno. L’efficienza biologica della dose è più grande rispetto a quella dei protoni di un fattore tra 1,5 e 3. L’utilizzo degli ioni di carbonio ha però uno svantaggio: la dose, superato il posto dove è localizzato il tumore, non diminuisce a zero, come nel caso dei protoni, in quanto le reazioni nucleari stesse tra gli ioni di carbonio e gli atomi del tessuto portano alla produzione di ioni più leggeri, che possono creare piccoli danni nelle vicinanze del tessuto tumorale (alcuni progetti di ricerca stanno studiando proprio questo aspetto).

Per eseguire l’adroterapia sono necessari:

• un acceleratore di protoni e/o di ioni, che produce più fasci di particelle in modo tale da avere più sale di trattamento;

• un sistema di trasporto dei fasci nelle sale di trattamento;

• un sistema molto preciso di posizionamento del paziente;

• un sistema accuratissimo di controllo dell’energia dei fasci e della dose assorbita dal paziente;

• un sistema tridimensionale di trattamento personalizzato sul paziente ottenuto integrando le immagini diagnostiche ottenute applicando tecniche quali la tomografia a emissione di positroni o la tomografia computerizzata.

Il protocollo di trattamento dipende ovviamente dalla tipologia del tumore. Vengono trattati i tumori localizzati, per esempio i melanomi dell’uvea, occhio, i tumori della base del cranio e della colonna vertebrale e anche alcuni tumori solidi pediatrici. Dopo l’iniziale calibrazione dell’energia, vengono effettuate un numero variabile, 12-16 d’abitudine, di sedute di trattamento.

Alla fine del 2012 esistevano nel mondo circa 40 centri di adroterapia e quasi 100.000 pazienti trattati con fasci adronici. Recentemente è entrato in funzione anche il centro italiano CNAO, vicino a Pavia, per l’adroterapia. L’adroterapia è un metodo molto costoso: l’investimento iniziale è intorno ai 100 milioni di Euro, e i costi per singolo paziente sono a loro volta molto alti – arrivando a decine di migliaia di Euro, un fattore almeno due volte più grande del costo della radioterapia. Oggi i ricercatori di tutto il mondo stanno provando nuovi metodi per costruire acceleratori meno costosi e riuscire a trattare più pazienti con questo metodo molto efficace per i tumori localizzati.

clip_image013

mercoledì 11 maggio 2016

Quando la topologia incontra i big data

 

I big data stanno ricevendo sempre piu’ attenzione da parte dei media,  industrie, laboratori, banche e governi per citarne alcuni. La quantita’ di dati generata ogni giorno, (dalle condizioni meteorologiche ai telefonini, dal web ai satelliti….. ) e’ enorme e molti dei database contengono centinaia e centinaia di variabili (attributi). Si tratta di insiemi cosi grandi e complessi che i metodi tradizionali di analisi  spesso falliscono. Ma allora perche’ cosi tanto interesse? Perche’ i dati contengono informazioni estremamente importanti ed interessanti. Sono delle vere e proprie’ miniere da cui estrarre l’oro (cioe’ l’informazione). Ma questa estrazione non e’ semplice e cio’ non solo a causa del numero di variabili e del numero di istanze ma anche a causa della rumorosita’ e complessita’ dei database. Facciamo un esempio ricorrendo al concetto di correlazione lineare, il cui obiettivo e’ quello di trovare la migliore retta che approssimi un insieme di punti in un piano. Qui di seguito un esempio di correlazione tra l’altezza e peso di un gruppo di persone. L’equazione della retta e’ data da Altezza(Height)=0.6*Peso(Weight)+130.2 il che significa che per esempio una persona che pesa 100 Kg sara’ alta circa 190 cm.

image

Di sicuro una linea retta e’ una forma e questa e’ adatta a rappresentare i punti del grafico. Questo pezzo di informazione e’ molto importante per diverse ragioni. Una e’ che la forma ci da’ un’informazione qualitativa mostrandoci come la variabile altezza varia direttamente con la variabile peso (cioe’ l’altezza aumenta se aumenta il peso). Un’altra e’ che essa permette di prevedere con ragionevole accuratezza una delle due variabili se conosciamo il valore dell’altra. La forma e’ alla base di una nuova metodologia che applica la topologia all’analidsi dei dati (Topology Data Analysis). Per il nostro esempio e’  la forma della linea che risulta un utile principio organizzativo per estrarre delle utili informazioni. Sfortunatamente pero’ i dati non sempre cooperano e si dispongono lungo una retta. Consideriamo, per esempio, l’insieme mostrato di seguito.

image

E’ facile capire che non c’e’ nessuna linea che possa rappresentare tali dati accuratamente. La ragione e’ che questi dati si dispongono in un insieme di tre cluster molto “stretti”. Anche se puo’ sembrare strano un aspetto fondamentale di qualsiasi forma e’ il numero di pezzi connessi in cui l’insieme puo’ essere diviso (In matematica, uno spazio topologico si dice connesso se non può essere rappresentato come l'unione di due o più insiemi aperti non vuoti e disgiunti. In modo poco formale ma abbastanza intuitivo, possiamo dire che la connessione è la proprietà topologica di un insieme di essere formato da un solo "pezzo"). In questo caso quindi la forma non puo’ essere quella di una linea ma quella di 3 pezzi connessi.

image

A questo punto potremmo pensare di procedere assumendo che quasiasi insieme di dati possa essere approssimato da una linea, da una famiglia di clusters o una famiglia di linee. Qui di seguito un altro insieme di dati che dimostra come questo non sia vero.  Chiaramente la regressione lineare (cerchio a destra) in un tale contensto e’ inutile e lo possiamo vedere grazie al fatto che ci rendiamo conto che la forma e’ circolare e cioe’ che possiamo vedere come si dispongono i punti.

image

Un altro esempio in cui la forma rassomiglia a quella di una Y. Questa e’ un’altra forma che spesso capita di incontrare nell’analisi dei big data. Il sistema ha un cuore centrale e 3 filamenti che si estendono a partire da esso. Questo puo’ rappresentare una situazione dove il cuore rappresenta il comportamento tipico e I filamenti invece dei comportamenti estremi dove il sistema sta meno frequentemente. E’ chiaro che questa forma e’ diversa da tutte le altre menzionate.

image

Esistono purtroppo infinite varieta’ di forme possibili nei dati reali e non solo quelle poche riportate fin qui come mostrato nell’immagine qui sotto.

image

E le difficolta’ non finiscono qui. Cosa succede se i punti si trovano in uno spazio a piu’ di 3 dimensioni? Come potremmo renderci conto che si tratta di un cerchio o di una linea?

O meglio: come possiamo insegnare ad un computer a trovare per esempio un cerchio?

Queste sono alcune delle questioni che emergono quando si analizzano i big data. Le risposte vengono dai campi piu’ disparati quali: machine learning, data mining, advanced statistic ecc. Ultimamente comunque come gia’ anticipato un valido contributo sembra venire dalla geometria e in particolare dalla topologia. Quest’ultima chiamata anche la “geometria dei fogli di gomma” e’ lo studio delle proprieta’ delle figure e delle forme che non cambiano quando viene effettuata una deformazione senza strappi, sovrapposizioni o incollature. Per un topologo una sfera e un cubo sono la stessa cosa. Operazioni come questa vengono chiamate deformazioni e due oggetti vengono considerati uguali se e’ possibile deformare uno nell’altro. I topologi studiano gli spazi assegnandogli degli oggetti algebrici chiamati invarianti. Nel caso particolare dell’applicazione della topologia all’analisi dei dati (TDA) l’invariante scelto e’ la cosiddetta “persistenza omologa”. L’omologia ordinaria misura il numero di “buchi” in uno spazio che non possono essere riempiti. Pensiamo ad una sfera. Se disegniamo una curva chiusa sulla sua superficie questa racchiudera’ uno disco di 2 dimensioni e potra’ avere il raggio che vogliamo anche tendente a zero. In questo senso significa che non ci sono buchi sulla superficie di una sfera altrimenti non avremmo potuto ridurre il disco fino ad avere dimensione nulla.

clip_image014

Al contrario questo non e’ vero per la superficie della sfera stessa che racchiude un “vuoto” tridimensionale che non puo’ essere riempito. I numeri di Betti contano quanti buchi non riempibili sono presenti per uno spazio di ogni dimensione.

· β0(X) e’ il numero di componenti connesse (o 0-cicli), in pratica il numero di pezzi separati di cui e’ composto lo spazio

· β1(X) conta i buchi fatti “a circonferenza” dello spazio (1-cicli come quelli di una ciambella)

· β2(X ) conta i vuoti bidimensionali dello spazio (2-cicli come quelli della sfera, del pallone o di una camera d’aria etc).

clip_image016

Qui di seguito il primo numero di Betti per le consonanti coreane.

image

Consideriamo adesso un caso bidimensionale con i dati rappresentati da un insieme discreto di punti come mostrato.

image

L’idea e’ quella di far crescere intorno ad ogni punto un disco di diametro d. Se d inizialmente e’ molto piccolo allora nessuno dei dischi s’interseca. Ma una volta che d cresce (vedi sotto) allora i dischi  iniziano a toccarsi dando origine a dei numeri di Betti diversi da zero. Osserviamo che a partire da d=d1 e fino a che d=d2, avremo un buco tra i 4 dischi cioe’ il buco persistera’ mentre d va da d1 fino a d2. Questo lo possiamo rappresentare con un grafico che prende il nome di barcode come mostrato sotto.

image

Ritorniamo adesso al caso discreto di punti introdotto prima e iniziamo a far crescere i dischi. Fermandoci ad un diametro leggermente superiore a d=1 avremo la seguente situazione. Ci sono due buchi uno in alto a sinistra all’interno del pentagono e uno in basso a destra all’interno del quadrato.

image

Quando il diametro d supera ~1.5 si forma un unico buco grande come mostrato sotto.

image

L’omologia persistente monitora i numeri di Betti utilizzando i barcode al variare del diametro d. Le barre lunghe indicano delle caratteristiche (features) dei dati che possono essere significative. Le barre corte invece spesso nascono dal rumore e possono essere scartate. Quello che si fa quindi e’ passare da una collezione discreta di punti ad una sequenza piu’ complicata di spazi che modellano meglio i dati di quanto possa fare una semplice correlazione lineare.

Gunnar Carlsson della Stanford University e’ uno dei pionieri della TDA. Insieme a dei colleghi ha fondato la compagnia AYASDI, sviluppando un software che si e’ dimostrato un valido strumento nell’analisi dei dati di banche, finanza, governo e industrie. Qui di seguito qualche esempio di applicazione. Dall’analisi di un database di una banca contenente circa 6 milioni di transazioni con circa 300 attributi il software e’ stato capace di isolare quelle fraudolente indicate in rosso.

image

Un altro esempio e’ dato dall’applicazione del software al mondo delle fabbriche di semiconduttori. Sono state analizzate piu’ di 1000 linee di produzione con circa 500 attributi per ogni linea identificando quelle con problemi di bassa qualita’ dei loro prodotti come mostrato nell’mmagine sottostante.

image

In definitiva cosa rende cosi’ potente l’applicazione della topologia nell’analisi dei dati rispetto alle tecniche piu’ tradizionali? La risposta e’ nelle seguenti 3 proprieta’ della topologia.

1. Indipendenza dal sistema di coordinate: la topologia studia le proprieta’ geometriche degli oggetti che non dipendono dal particolare sistema di riferimento utilizzato per rappresentarli

2. Invarianza rispetto alle deformazioni: la topologia studia le proprieta’ delle curve e superfici che non cambiano quando vengono stirate.

image

3. Rappresentazione compressa: la topologia costruisce delle rappresentazioni combinatorie di oggetti continui. Un cerchio (curva continua) puo’ essere rappresentato da una rete esagonale costituita cioe’ da 6 nodi e 6 spigoli (edges).

image

domenica 13 marzo 2016

Matematica e Google

 

image

Molte persone credono che la matematica sia una disciplina fine a se stessa molto astratta e praticamente inutile. I matematici vengono visti come esseri strani che vivono in un universo tutto loro e si occupano di cose che solo loro capiscono e che non servono nella vita di tutti i giorni.

E’ possibile che ci sia qualche cosa di vero in queste affermazioni. Ma di sicuro se non ci fossero stati gli sviluppi matematici fatti negli ultimi anni, molte delle funzionalità che oggi utilizziamo non sarebbero disponibili. La tecnologia avanza con l’avanzare della ricerca matematica e non solo. Anche se molti di noi non se ne accorgono, ogni giorno facciamo uso della matematica. Vogliamo fare un elenco delle applicazioni che vedono coinvolta la ricerca matematica? Proviamoci.

· Fotografia digitale

· Musica digitale

· Film e tv digitali

· Telefonia mobile

· Crittografia

· Navigatore satellitare

· TAC (tomografia assiale computerizzata)

· Previsioni meteo

· Analisi di rischio

· Analisi di economia

· Internet

e tante altre. In questo post, come si intuisce dal titolo ci occuperemo di Internet e in particolare del Page Ranking di Google cioe’ dell’algoritmo utilizzato da Google per assegnare un fattore di importanza alle pagine trovate dal motore di ricerca.

Due studenti dell’Università’ di Stanford, Sergey Brin e Larry Page, hanno fatto la loro fortuna inventando uno dei più potenti motori di ricerca del web “Google”.

Ma cosa deve fare esattamente un motore di ricerca?

Semplicemente ordinare le pagine presenti sul web in base alla loro importanza ogni qualvolta un utente effettua una ricerca. Ma come si può definire l’importanza (page rank) di una pagina?

L’idea dei due studenti e’ stata la seguente.

Ogni pagina web ha una sua propria importanza che deriva dalle connessioni (non direttamente dai contenuti). L’importanza di una pagina viene trasferita in parti uguali alle pagine che essa punta. Quindi l’importanza di una pagina e’ data dalla somma delle frazioni di importanza che gli derivano dalle pagine che ad essa puntano. Facendo ricorso ad una analogia nella vita di tutti i giorni: una persona importante da’ importanza alle persone che frequenta e allo stesso tempo una persona e’ importante se frequenta molte persone importanti.

Passiamo al modello matematico. Supponiamo di numerare le pagine del web da 1 a n. Definiamo la matrice di connettività nel seguente modo:

image

dove i vari elementi sono uguali a 1 se c’e’ un link tra la pagina i e la pagina j altrimenti sono uguali a zero. Facciamo un esempio con 4 pagine, cioè n=4 e supponiamo di avere la seguente matrice di connettività:

image

Schematizziamo le connessioni tra le varie pagine con delle frecce ottenendo il seguente grafo:

image

Sommando i valori della riga i si trova il numero di link che partono dalla pagina i. Indichiamo questo numero con Pi. Sommando, invece, i valori della colonna j si trova il numero di pagine che puntano alla pagina j che indicheremo con Aj. Se adesso indichiamo con xj l’importanza della pagina j risulta che:

image

per j che varia da 1 a n. Considerando il sistema di 4 pagine precedente, possiamo per esempio scrivere:

image

Si tratta, in generale, di un sistema lineare di n equazioni in n incognite. Le soluzioni xj danno il livello di importanza delle singole pagine, cioè il page rank.

Ad oggi, pensate che ci sono circa n=8500000000 pagine attive.

Comunque l’equazione da noi ricavata e’ una versione semplificata. In effetti quella usata da Google e’ data da:

image

dove d e’ un parametro compreso fra 0 e 1, che di solito viene messo a 0.85. I valori di xj sono compresi tra 0 (pagina non importante) e 1 (pagina importantissima.

Ma e’ possibile risolvere un sistema lineare con 8.5 miliardi di incognite? Se utilizzassimo il metodo di eliminazione questo richiederebbe circa 4*109 operazioni matematiche. Sic!

Il calcolatore più veloce esistente al mondo (il Blue Gene dell’IBM) richiederebbe più di 36 milioni di anni per risolvere un tale sistema. Un tempo da ere geologiche....

Eppure Page e Brin calcolano il page rank in continuazione. Come fanno?

Anche se la tecnologia fosse in grado di costruire un computer 1000 volte o anche un milione di volte più veloce sarebbe sempre impossibile risolvere il problema di Google in tempo reale. E allora?

La soluzione la si può ottenere solo sviluppando nuovi metodi matematici. E’ quello che hanno fatto i due sviluppatori di Google che utilizzano il seguente algoritmo.

Prima di tutto assegnano alle pagine dei valori di importanza xj qualsiasi. Inizialmente non importa quale sia il valore. Dopo di che si sostituiscono questi numeri nell’equazione riportata precedentemente ricavando dei nuovi valori di importanza in accordo alla matrice di connettività e ai valori di Pi. A questo punto si inseriscono sempre nella stessa equazione come valori di ingresso xj quelli appena ottenuti. E si ricavano nuovi valori e cosi via. In questo modo viene generata una successione di approssimazioni successive che converge alla soluzione del sistema qualunque siano i valori iniziali utilizzati. Nella figura qui sotto viene riportato l’andamento delle soluzioni del sistema per il caso di 4 pagine riportato sopra come esempio. Notiamo la rapida convergenza delle soluzioni.

image

Andamento delle soluzioni del sistema Page rank per il caso di 4 pagine

Per fare un passo dell’algoritmo qui descritto bisogna eseguire tante moltiplicazioni quanti sono gli elementi non nulli della matrice di connettività C e all’incirca altrettante addizioni. Su ogni riga della matrice C, comunque, mediamente ci sono pochi elementi diversi da zero. Se supponiamo che questo numero sia 50, un passo del metodo iterativo spiegato, su Blue Gene impiegherebbe solo 2 millesimi di secondo. Se anche fossero necessari 1000 passi iterativi basterebbero 2 secondi per approssimare la soluzione di Google.

Fin dalla sua introduzione l’equazione del PageRank  ha ricevuto l’attenzione di moltissimi studiosi che hanno cercato di migliore in tutti i modi il metodo di soluzione del sistema lineare. Qualche anno fa ugruppo di studiosi, tra cui alcuni italiani dell’università’ di Roma e Cagliari, hanno usato un nuovo approccio molto più veloce di quelli esistenti oggi, ricorrendo ad un’analogia con la Fisica Quantistica. In particolare, hanno mostrato che e’ possibile riarrangiare l’equazione Page Rank in modo da ottenere un’equazione simile all’equazione di Schrödinger.

Vi ricordo che l'equazione di Schrödinger rappresenta una delle più importanti conquiste della fisica ed in particolare della meccanica quantistica. Quest'ultima, risalente alla metà degli anni venti e’ stata sviluppata soprattutto da de Broglie e Schrödinger e si basa sul cosiddetto approccio ondulatorio della materia. In questa ottica, si rappresentano le particelle con delle funzioni d'onda in quanto si e’ visto che in certi esperimenti le particelle elementari mostrano comportamenti ondulatori. La funzione d’onda va interpretata in termini probabilistici, cioè il suo modulo al quadrato altro non rappresenta che la probabilità di trovare la particella in un punto x al tempo t. L’equazione di Schrodinger e’ scritta come:

image

dove psi e’ la funzione d’onda, i e’ l’unita immaginaria, h tagliato una costante fisica, m la massa della particella, V(x) il potenziale in cui e’ immersa la particella e i simboli d/dt e d2/dx2 sono la derivata rispetto al tempo e la derivata seconda rispetto alla posizione rispettivamente. Si rimanda il lettore ad un qualsiasi testo di analisi matematica per la definizione di derivata. In parole molto semplici la derivata di una funzione f rispetto al tempo, df/dt , indica quanto rapidamente f cambia al variare del tempo.

Esprimere il PageRank in termini di una funzione d’onda che obbedisce ad un’equazione simil-Schrödinger permette, secondo questo studio, di localizzare velocemente le pagine con un rank più alto senza utilizzare procedure iterative, chiarendo nel contempo il ruolo della topologia nella diffusione delle informazioni nelle reti complesse.

Nell’equazione riarrangiata del PageRank, il potenziale V dell’equazione di Schrödinger corrisponde alla differenza tra il numero di links entranti Pj e il numero di links uscenti Aj da ogni pagina (i nodi della rete mostrata qui di seguito).

 

image

Rappresentazione dell’equazione PageRank e la sua controparte quantistica. Nelle immagini in basso vengono rappresentati il potenziale V e il corrispondente PageRank misurato lungo dei dischi concentrici intorno ad un vertice.

Quando il potenziale V e’ minore di zero (minima energia) la funzione d’onda dell’equazione PageRank e’ localizzata in questa buca di potenziale e il suo valore e’ massimo, indicando che quel nodo, cioè la pagina e’ importante.

Allo stesso modo, quando il potenziale V e’ positivo la funziona d’onda e’ localizzata in questo picco di potenziale e mostra il suo valore più basso, indicando che la pagina non e’ importante.

Questa analogia formale con la fisica quantistica mette a disposizione dello studio del PageRank una serie di strumenti teorici consolidati, sviluppati dai fisici, come la teoria perturbativa.

La differenza di scala tra il mondo delle particelle sub-atomiche ed il Web è enorme ma i ricercatori sono convinti che il loro lavoro potrà portare benefici a tutto quel campo di ricerca che si collega al  PageRank  e che comprende, per esempio, la propagazione della fiducia nei social network od una più efficiente classificazione delle pagine web.

image

Curve di livello del potenziale V e della funzione d’onda. Si può vedere come in prossimità del minimo del potenziale corrisponde il massimo della funzione d’onda e quindi dell’importanza della pagina web. Il calcolo e’ stato effettuato sempre considerando i dischi concentrici dell’immagine precedente

sabato 9 gennaio 2016

Ma i numeri primi sono veramente casuali?

Prima di tutto vediamo cosa significa casualità o come dicono gli inglesi randomness.

Per randomness i matematici e fisici intendono il caos, l’imprevedibilità, l’assenza di strutture interne, l’assenza di qualsiasi particolare configurazione. Per generare un risultato randomico , normalmente si usa una moneta o un dado. Ma nel caso di una sequenza di numeri, come per esempio quella dei numeri primi , 2, 3, 5, 7, 11,13,17,19, 23…. che cosa significa randomico? Semplicemente che non è possibile trovare un algoritmo, una formula matemtica che riproduca esattamente la sequenza, cioè che non è possibile determinare il prossimo termine della sequenza a partire da quelli conosciuti.

Prima dell’avvento della meccanica quantistica c’era un comune accordo tra tutti gli scienziati che “Dio non gioca ai dadi”, cioè la casualità nel lancio di una moneta era solo dovuto al risultato della nostra ignoranza su tutte le forze coinvolte. Se avessimo conosciuto tutto con esattezza allora la casualità sarebbe scomparsa.

La meccanica quantistica, invece, ha mostrato che Dio gioca ai dadi: il comportamento della materia a livello microscopico è imprevedibile. Non c’è modo di prevedere, per esempio, quando un nucleo radioattivo decadrà.

Un team di ricercatori, nel 2003, ha fatto una scoperta proprio sulla distribuzione dei numeri primi nella sequenza dei numeri interi. Il Team costituito da tre fisici dell’Università di Boston, Pradeep Kumar, Plamen Ivanov e Eugene Stanley, ha trovato una specie di ordine nella distribuzione dei primi che mai nessuno aveva notato.

Essi hanno considerato la distanza tra due numeri primi consecutivi e poi la differenza tra queste distanze chiamandola incremento. Per i numeri primi  minori di 20 abbiamo 1, 2, 2, 4, 2, 4, 2 come distanze e 1, 0, 2, -2, 2, -2 come incrementi (vedi figura 1).

Considerando tutti i numeri primi  minori di 50.000.000 hanno trovato che la distribuzione degli incrementi non è quella di una sequenza randomica in quanto esibisce degli alti picchi in corrispondenza di determinati valori di incrementi, dei picchi medi e picchi bassi per altri valori, con una chiara oscillazione di periodo 3 (vedi figura 2). I valori positivi sono quasi sempre seguiti da valori corrispondenti negativi. La frequenza degli incrementi decresce esponenzialmente e questo andamento è evidente sia per i picchi alti che per quelli bassi, formando una forma a “doppia tenda” (vedi figura 2 (b)). Inoltre la frequenza per gli incrementi positivi e quelli negativi è quasi la stessa come si può vedere nella figura 2.

 

Figura 1 Distanze tra numeri primi consecutivi (a) e i loro incrementi (b).

 

Figura 2 Istogramma degli incrementi per il primo milione di numeri primi. La frequenza con cui compaiono gli incrementi mostra un sistema oscillante con periodo 3. Gli incrementi con valori (6k+2) e –(6k+2) per k=0,1,2,3... sono quelli più frequenti. Seguono gli incrementi con valori (6k+4) e –(6k+4) e poi ci sono quelli rari in corrispondenza degli incrementi 6k e -6k (a). Al centro viene riportata la stessa distribuzione ma in scala semilogaritmica (b). E nell’ultimo grafico (c) la stessa cosa ma prendendo il valore assoluto dei valori negativi. Si può vedere chiaramente una legge di potenza.

 

Due ricercatori cinesi hanno ottenuto dei risultati analoghi effettuando dei test di randomness (chiamati FIPS che sta per Federal Information processing Standard) sulla stessa sequenza degli incrementi usata dai tre fisici di Boston. Il test statistico è costituito da 4 differenti sotto-test che sono utilizzati per verificare se una sequenza di numeri è realmente casuale. I risultati ottenuti hanno evidenziato che dei 4 sotto-test effettuati solo due hanno superato la verifica. Questo significa che la distribuzione dei numeri primi non sembra essere una sequenza casuale in senso stretto confermando i risultati dei ricercatori di Boston.

Della serie, casuale (randomica) ma non troppo. Se anche Dio si divertisse a giocare con i dadi, per i numeri primi deve essere successo qualche cosa di strano che al momento non ci è dato sapere.

Un risultato analogo per gli incrementi è visibile anche nella sequenza delle distanze tra i numeri primi. In un mio lavoro, pubblicato sulla rivista matematica SNJ (Smarandache Notions Journal) nel 2002, è riportato l’istogramma della frequenza delle distanze diviso 2 in scala lineare e semilogaritmica (vedi figura 3) da cui si evince un andamento oscillante sovrapposto ad un comportamento esponenziale. In questo caso i picchi delle frequenze sono in corrispondenza delle distanze i cui valori sono multipli di 3.

 

Figura 3 Istogramma delle distanze in scala lineare e semilogaritmica.(Da un articolo dell’autore pubblicato sul giornale SNJ n.13 del 2002)

 

E la sorpresa non finisce qui. La distribuzione dei numeri primi, infatti, mostra un’altra caratteristica che è comune a molti sistemi naturali: il cosiddetto rumore rosa. In fisica si definisce rumore rosa o rumore 1/f, un particolare tipo di rumore in cui le componenti a bassa frequenza f hanno potenza (energia per unità di tempo) maggiore di quelle ad alta frequenza, a differenza del rumore bianco, invece, in cui la potenza è uguale per qualsiasi frequenza (vedi figura 4).

 

Figura 4 Rumore rosa (destra) e rumore bianco (sinistra). Sull’asse verticale viene riportata la potenza e su quello orizzontale la frequenza. Si vede chiaramente che il rumore rosa si concentra nella regione delle basse frequenze mentre quello bianco dappertutto.

 

Se indichiamo con S(f) lo spettro di potenza in funzione della frequenza f,  per il rumore rosa varrà una legge del tipo:    

S(f)=k/fb

dove b è un coefficiente il cui valore è compreso tra 0 e 2 e k una costante. 

Un fisico teorico dell’Università Polacca, Marek Wolf, in un suo articolo ha mostrato che il numero di primi all’interno di particolari intervalli di interi si comporta come un segnale con rumore rosa. In particolare per tutti gli interi tra 1 e N, vengono formati M intervalli di lunghezza L in modo che M=N/L. Dopo di che vengono contati quanti numeri primi ci sono in ogni intervallo formando una sequenza 

XL(t) 

con t=1 per il primo intervallo, 2 per il secondo e cosi via. Nella figura 5 viene mostrato l’andamento di questa sequenza in funzione di t. Calcolando lo spettro di potenza  di questa sequenza, interpretata come un segnale temporale, Wolf si è accorto che esso si comporta come il rumore rosa con un coefficiente pari a 1.64:

SX(f)=k/f1.64

 

Figura 5 Andamento della sequenza XL (vedi testo per la definizione) in funzione di t

 

Nella figura 6, in scala logaritmica viene riportato lo spettro S in funzione della frequenza. Si può vedere chiaramente che indipendentemente dalla lunghezza scelta per gli intervalli, c’è un andamento lineare tra le due variabili, cioè:

ln(SX(f))~b*ln(f) --> SX(f)~f-b

L’indipendenza di b da l sembra suggerire una qualche sorta di auto-similarità nella distribuzione dei primi, un fenomeno già osservato in altri contesti. Questo significa che il tutto sembra essere simile alla parte che è una caratteristica fondamentale della teoria dei frattali piu’ volte trattati in questo blog.

Molti dei sistemi naturali che mostrano un rumore rosa, sono stati spiegati ricorrendo a modelli di tipo SOC  (Self organized criticality), cioè sistemi che autonomamente si auto-organizzano  in uno stato critico come i mucchietti di sabbia, i terremoti o gli incendi delle foreste.

 

Figura 6 Spettro di frequenza della sequenza XL . È chiaro l’andamento lineare indipendente dalla lunghezza degli intervalli.

 

Si tratta di sistemi in uno stato critico. Basta una piccola variazione in ingresso per produrre grosse variazioni in uscita (come il granello di sabbia che può innescare una valanga). La stessa vita può essere interpretata come un sistema in uno stato critico. In bilico tra l’ordine e il caos, la frontiera dove il comportamento di un sistema può essere estremamente complesso. Un po’ a sinistra di questa frontiera e il sistema diventa regolare, ordinato; un po’ a destra e diventa altamente disordinato. La vita è continuamente in bilico tra ordine e disordine. Il primo a parlare di SOC fu il fisico Bak , per spiegare il comportamento dei granelli di sabbia osservato in un suo esperimento che consisteva nel far cadere un granello alla volta al di sopra di un piano. Il più delle volte al cadere di un unico granello di sabbia non succedeva praticamente nulla di significativo. Altre volte invece il granello innescava una reazione a catena nel mucchietto di sabbia, con la generazione di una valanga. Bak  modellò questo sistema con un reticolo bidimensionale e delle regole molto semplici. In modo casuale erano fatti cadere dei granelli di sabbia all’interno del reticolo. Se una cella conteneva più di 4 granelli, questi venivano ridistribuiti alle 4 celle adiacenti o perse al di fuori della frontiera del reticolo. La ridistribuzione portava a delle instabilità con la possibilità di produrre valanghe di dimensioni sempre più grandi (vedi figura 7).

 

Figura 7 Modello del mucchietto di sabbia usato da Bak. I numeri nelle griglie rappresentano il numero di granelli al tempo t. Le diverse rappresentazioni sono immagini del modello a diversi istanti di tempo (da sinistra verso destra e dall’alto verso il basso). Quando una cella raggiunge 4 c’è una ridistribuzione dei granelli nei primi vicini. In nero viene rappresentata una valanga.

 

Misurando la dimensione di tutte le valanghe prodotte, Bak  si accorse, che come per il rumore rosa, alla base del sistema c’era una legge di potenza (vedi figura 8).

Le piccole valanghe erano molto più frequenti di quelle catastrofiche cosi come succede per i terremoti ,  la dimensione degli incendi  nelle foreste, il numero di vittime di un attacco terroristico, il numero di vittime delle guerre e cosi via. Emerge sempre una legge di potenza anche se con coefficienti diversi tra loro (vedi figura 9). Tornando ai numeri primi  questo significa che anche essi possono essere consierati come un sistema in uno stato di criticità auto-organizzata? E se questo fosse vero cosa ha spinto questo insieme verso la criticita’?  Domande a cui nessuno oggi sa rispondere. 

 

Figura 8 Frequenza P(S) delle dimensioni S delle valanghe nel modello del mucchietto di sabbia di Bak. Notare la scala bi logaritmica. Si tratta di una legge di potenza, che evidenzia come ci sia un elevato numero di valanghe di piccole dimensioni e poche valanghe catastrofiche.

 

Figura 9 Legge di potenza per diversi sistemi come: terremoti (f), nomi persone (k) e popolazione citta'(l). Sull’asse verticale è riportata la probabilità che l’evento si verifichi.

http://www.wikio.it