New markov chain based methods for single and cross-domain sentiment classification

Nowadays communication is switching from a centralized scenario, where communication media like newspapers, radio, TV programs produce information and people are just consumers, to a completely different decentralized scenario, where everyone is potentially an information producer through the use of social networks, blogs, forums that allow a real-time worldwide information exchange. These new instruments, as a result of their widespread diffusion, have started playing an important socio-economic role. They are the most used communication media and, as a consequence, they constitute the main source of information enterprises, political parties and other organizations can rely on. Analyzing data stored in servers all over the world is feasible by means of Text Mining techniques like Sentiment Analysis, which aims to extract opinions from huge amount of unstructured texts. This could lead to determine, for instance, the user satisfaction degree about products, services, politicians and so on. In this context, this dissertation presents new Document Sentiment Classification methods based on the mathematical theory of Markov Chains. All these approaches bank on a Markov Chain based model, which is language independent and whose killing features are simplicity and generality, which make it interesting with respect to previous sophisticated techniques. Every discussed technique has been tested in both Single-Domain and Cross-Domain Sentiment Classification areas, comparing performance with those of other two previous works. The performed analysis shows that some of the examined algorithms produce results comparable with the best methods in literature, with reference to both single-domain and cross-domain tasks, in $2$-classes (i.e. positive and negative) Document Sentiment Classification. However, there is still room for improvement, because this work also shows the way to walk in order to enhance performance, that is, a good novel feature selection process would be enough to outperform the state of the art. Furthermore, since some of the proposed approaches show promising results in $2$-classes Single-Domain Sentiment Classification, another future work will regard validating these results also in tasks with more than $2$ classes.

Processi markoviani nascosti

We introduce the notation of Markov chains and their properties, and give the definition of ergodic, irreducible and aperiodic chains with correspective examples. Then, the definition of hidden Markov models is given and their characteristics are examined. We formulate three basic problems regarding the hidden Markov models and discuss the solution of two of them - the Viterbi algorithm and the forward-backward algorithm.

Entanglement entropy in restricted integrable spin-chains

In questa tesi abbiamo presentato il calcolo dell’Entropia di Entanglement di un sistema quantistico unidimensionale integrabile la cui rappresentazione statistica é data dal modello RSOS, il cui punto critico é una realizzazione su reticolo di tutti i modelli conformi minimali. Sfruttando l’integrabilitá di questi modelli, abbiamo svolto il calcolo utilizzando la tecnica delle Corner Transfer Matrices (CTM). Il risultato ottenuto si discosta leggermente dalla previsione di J. Cardy e P. Calabrese ricavata utilizzando la teoria dei campi conformi descriventi il punto critico. Questa differenza é stata imputata alla non-unitarietá del modello studiato, in quanto la tecnica CTM studia il ground state, mentre la previsione di Cardy e Calabrese si focalizza sul vuoto conforme del modello: nel caso dei sistemi non-unitari questi due stati non coincidono, ma possono essere visti come eccitazioni l’uno dell’altro. Dato che l’Entanglement é un fenomeno genuinamente quantistico e il modello RSOS descrive un sistema statistico classico bidimensionale, abbiamo proposto una Hamiltoniana quantistica unidimensionale integrabile la cui rappresentazione statistica é data dal modello RSOS.

Il gruppo delle trecce ed il teorema di Markov

Il lavoro concerne il gruppo delle trecce, il suo legame con i link e si concentra sui teoremi di Markov e Alexander.

Su(3) lattice gauge theories and spin chains

I modelli su reticolo con simmetrie SU(n) sono attualmente oggetto di studio sia dal punto di vista sperimentale, sia dal punto di vista teorico; particolare impulso alla ricerca in questo campo è stato dato dai recenti sviluppi in campo sperimentale per quanto riguarda la tecnica dell’intrappolamento di atomi ultrafreddi in un reticolo ottico. In questa tesi viene studiata, sia con tecniche analitiche sia con simulazioni numeriche, la generalizzazione del modello di Heisenberg su reticolo monodimensionale a simmetria SU(3). In particolare, viene proposto un mapping tra il modello di Heisenberg SU(3) e l’Hamiltoniana con simmetria SU(2) bilineare-biquadratica con spin 1. Vengono inoltre presentati nuovi risultati numerici ottenuti con l’algoritmo DMRG che confermano le previsioni teoriche in letteratura sul modello in esame. Infine è proposto un approccio per la formulazione della funzione di partizione dell’Hamiltoniana bilineare-biquadratica a spin-1 servendosi degli stati coerenti per SU(3).

Algoritmi e ricorsività: macchine di Turing e algoritmi di Markov

In questa questa tesi vengono presentate alcune delle più importanti definizioni di funzione computabile mediante un algoritmo: una prima descrizione è quella data tramite le funzioni ricorsive, un secondo approccio è dato in termini di macchine di Turing, infine, vengono considerati gli algoritmi di Markov. Si dimostra che tutte queste definizioni sono equivalenti. Completa la tesi un breve cenno al lambda-K-calcolo.

Entanglement entropy in 1-d quantum spin chains

In questa tesi abbiamo studiato il comportamento delle entropie di Entanglement e dello spettro di Entanglement nel modello XYZ attraverso delle simulazioni numeriche. Le formule per le entropie di Von Neumann e di Renyi nel caso di una catena bipartita infinita esistevano già, ma mancavano ancora dei test numerici dettagliati. Inoltre, rispetto alla formula per l'Entropia di Entanglement di J. Cardy e P. Calabrese per sistemi non critici, tali relazioni presentano delle correzioni che non hanno ancora una spiegazione analitica: i risultati delle simulazioni numeriche ne hanno confermato la presenza. Abbiamo inoltre testato l'ipotesi che lo Schmidt Gap sia proporzionale a uno dei parametri d'ordine della teoria, e infine abbiamo simulato numericamente l'andamento delle Entropie e dello spettro di Entanglement in funzione della lunghezza della catena di spin. Ciò è stato possibile solo introducendo dei campi magnetici ''ad hoc'' nella catena, con la proprietà che l'andamento delle suddette quantità varia a seconda di come vengono disposti tali campi. Abbiamo quindi discusso i vari risultati ottenuti.

Catene di Markov nascoste e giochi stocastici.

In questa trattazione si introduce il concetto di catena di Markov nascosta: una coppia di processi stocastici (X,O), dove X è una catena di Markov non osservabile direttamente e O è il processo stocastico delle osservazioni, dipendente istante per istante solo dallo stato corrente della catena X. In prima istanza si illustrano i metodi per la soluzione di tre problemi classici, dato un modello di Markov nascosto e una sequenza di segnali osservati: valutare la probabilità della osservazione nel modello, trovare la sequenza nascosta di stati più probabile e aggiornare il modello per rendere più probabile l'osservazione. In secondo luogo si applica il modello ai giochi stocastici, nel caso in cui solo uno dei giocatori non è a conoscenza del gioco in ogni turno, ma può cercare di ottenere informazioni utili osservando le mosse dell'avversario informato. In particolare si cercano strategie basate sul concetto di catena di Markov nascoste e si analizzano i risultati ottenuti per valutare l'efficienza dell'approccio.

Catene di Markov reversibili e applicazioni al metodo Montecarlo basato sulle catene di Markov

Gli argomenti trattati in questa tesi sono le catene di Markov reversibili e alcune applicazioni al metodo Montecarlo basato sulle catene di Markov. Inizialmente vengono descritte alcune delle proprietà fondamentali delle catene di Markov e in particolare delle catene di Markov reversibili. In seguito viene descritto il metodo Montecarlo basato sulle catene di Markov, il quale attraverso la simulazione di catene di Markov cerca di stimare la distribuzione di una variabile casuale o di un vettore di variabili casuali con una certa distribuzione di probabilità. La parte finale è dedicata ad un esempio in cui utilizzando Matlab sono evidenziati alcuni aspetti studiati nel corso della tesi.

Caratterizzazione di sequenze di DNA mediante catene di Markov

Questa tesi si inserisce nell’ambito di studio dei modelli stocastici applicati alle sequenze di DNA. I random walk e le catene di Markov sono tra i processi aleatori che hanno trovato maggiore diffusione in ambito applicativo grazie alla loro capacità di cogliere le caratteristiche salienti di molti sistemi complessi, pur mantenendo semplice la descrizione di questi. Nello specifico, la trattazione si concentra sull’applicazione di questi nel contesto dell’analisi statistica delle sequenze genomiche. Il DNA può essere rappresentato in prima approssimazione da una sequenza di nucleotidi che risulta ben riprodotta dal modello a catena di Markov; ciò rappresenta il punto di partenza per andare a studiare le proprietà statistiche delle catene di DNA. Si approfondisce questo discorso andando ad analizzare uno studio che si ripropone di caratterizzare le sequenze di DNA tramite le distribuzioni delle distanze inter-dinucleotidiche. Se ne commentano i risultati, al fine di mostrare le potenzialità di questi modelli nel fare emergere caratteristiche rilevanti in altri ambiti, in questo caso quello biologico.