Presentazione.tex.backup

%% LyX 1.6.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[10pt,italian,compact]{beamer}
\usepackage[3D]{movie15}
\usepackage{babel}
\usepackage{ae,aecompl}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\setcounter{tocdepth}{2}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{verbatim}
%\includeonlyframes{current_frame}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 % this default might be overridden by plain title style
 \newcommand\makebeamertitle{\frame{\maketitle}}%
 \AtBeginDocument{
   \let\origtableofcontents=\tableofcontents
   \def\tableofcontents{\@ifnextchar[{\origtableofcontents}{\gobbletableofcontents}}
   \def\gobbletableofcontents#1{\origtableofcontents}
 }
\newcommand\itemat[2]{\only<{#1}>{\begin{enumerate} \setcounter{enumi}{#1} \item{#2} \end{enumerate}}}

\renewcommand\emph[2]{\textcolor{#1}{\textbf{{#2}}}}

\newcommand\lyxframe[1]{\begin{frame}[fragile]{#1}}
    \setcounter{MaxMatrixCols}{15}

\newcommand\hidetext[2]{\colorbox{#1}{\textcolor{#1}{#2}}}

\setlength{\parskip}{0pt} % 1ex plus 0.5ex minus 0.2ex}


\setlength{\parindent}{0pt}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{xcolor}
\usepackage{multicol}

%
%\usetheme{Darmstadt}
\usetheme{Frankfurt}
%+++spartano, ok

%\usetheme{Madrid}
%+++ senza boxes, ma carino
%\usetheme{Pittsburgh}
%+ square
%\usetheme{Rochester}
%\usetheme{Singapore}
%super tipico
%\usetheme{Warsaw}

%\usepackage{pstcol,pst-node,pst-tree}
% or ...
%\usecolortheme{albatross}
%\usecolortheme{beaver}
%\usecolortheme{beetle}
%arancione,vivace
%\usecolortheme{crane}

%identico al default
%\usecolortheme{dolphin}
%come il default, piu delicato
%\usecolortheme{rose}
%tutto grigio....
%\usecolortheme{seagull}
% come default, header piu chiaro 
%\usecolortheme{seahorse}
%tutto uguale, header arancione!!!
%\usecolortheme{wolverine}

%\useoutertheme{infolines}
\useoutertheme[subsection=false]{miniframes}
%\useoutertheme{shadow}
%carino
%\useoutertheme{smoothbars}
%\useoutertheme{split}
%\useoutertheme{tree}
%\useoutertheme{default}


%\usepackage{euler}
%

\setbeamercovered{transparent=15}
\setbeamertemplate{navigation symbols}{}
\useinnertheme{circles}
% or whatever (possibly just delete it)
%\usefonttheme{structuresmallcapsserif}
\setbeamerfont{headline}{size=\footnotesize}



\definecolor{A}{rgb}{0.09,0.9,0.9}
\definecolor{C}{rgb}{0.9,0.09,0.09}
\definecolor{E}{rgb}{0.9,0.686842,0.431053}
\definecolor{D}{rgb}{0.175263,0.686842,0.9}
\definecolor{G}{rgb}{0.431053,0.9,0.09}
\definecolor{F}{rgb}{0.9,0.9,0.175263}
\definecolor{I}{rgb}{0.09,0.09,0.9}
\definecolor{H}{rgb}{0.09,0.09,0.09}
\definecolor{K}{rgb}{0.260526,0.772105,0.09}
\definecolor{L}{rgb}{0.09,0.09,0.9}
\definecolor{N}{rgb}{0.9,0.857368,0.9}
\definecolor{Q}{rgb}{0.345789,0.9,0.09}
\definecolor{P}{rgb}{0.601579,0.09,0.516316}
\definecolor{R}{rgb}{0.9,0.260526,0.601579}
\definecolor{T}{rgb}{0.857368,0.345789,0.9}
\definecolor{W}{rgb}{0.9,0.09,0.9}
\definecolor{V}{rgb}{0.9,0.09,0.09}



\makeatother


\begin{document}

\title{Sviluppi Teorici e Applicativi delle Metriche Entropiche di Rohlin}




\author{Dawid Crivelli\\
}

\date{26 Aprile 2012}

\makebeamertitle

\section{Distanze Entropiche}


\lyxframe{Distanza di Rohlin}
Distanza non tra configurazioni, ma tra \emph{black}{partizioni}\\
\bigskip{}
Requisiti:
\begin{itemize}
\item uno spazio di probabilit\`a: $(\mathbf{M},\mathcal{M},\mu)$ 
\item un criterio per partizionare (relazione di equivalenza)
\item usiamo $\mathbf{M}$ discreto
\end{itemize}

\bigskip{}
Ogni sequenza, reticolo, grafo => array con relazioni non locali
\medskip{}


\begin{columns}
\column{0.38\textwidth}
\center{\includegraphics[width=1\textwidth]{presentazione-immagini/reticolo-semplice3}}\null
\column{0.24\textwidth}
\center{da $\mathcal{C}(\mathbf{M})$ a $\mathcal{Z}(\mathbf{M})$}\null
\column{0.38\textwidth}
\center{\includegraphics[width=1\textwidth]{presentazione-immagini/reticolo-semplice4}}\null

\end{columns}




\end{frame}
\lyxframe{Complessit\`a di una partizione}
\begin{comment}
Ad ogni partizione corrispondono configurazioni diverse:\\
\begin{center}
{\tt\{
\colorbox{red}{AAAA}
\colorbox{green}{BB}
\colorbox{blue}{CCC}
\colorbox{red}{AAAA}
\}}\\
{\tt\{
\colorbox{red}{BBBB}
\colorbox{green}{ZZ}
\colorbox{blue}{AAA}
\colorbox{red}{FFFF}
\}}
\end{center}
\end{comment}
Partizione $\Longleftrightarrow$ scomposizione in \emph{black}{atomi} disgiunti di \textit{misura} $\mu(A_k)$
\bigskip{}

Rappresentazione associando ad ogni sito un'etichetta (atomo):\\
\[\mathrm{A}=\{\underbrace{(1,2,3,4)}_{A_1},\underbrace{(5,6)}_{A_2},\underbrace{(7,8,9)}_{A_3},\underbrace{(10,11,12,13)}_{A_4}\}\]
\medskip{}
\[\mathrm{A}=
\begin{bmatrix}
 1 &  2 &  3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 & 11 & 12 & 13 \\
 \colorbox{red}{1} &  \colorbox{red}{1} &  \colorbox{red}{1} &  \colorbox{red}{1} &  \colorbox{green}{2} &  \colorbox{green}{2} &  \colorbox{blue}{3} &  \colorbox{blue}{3} &  \colorbox{blue}{3} &  \colorbox{orange}{4} &  \colorbox{orange}{4} &  \colorbox{orange}{4} &  \colorbox{orange}{4} \\
\end{bmatrix}
\]

\bigskip{}

\emph{black}{Entropia di Shannon}: misura della complessit\`a di una partizione
\[H(A)=\sum_k^n \mu(A_k) \log\left(\mu(A_k)\right)\]

\begin{center}
\begin{tabular}{ll}
H=$\log(n)$ (max) & $\Leftrightarrow$ partizione con n atomi equivalenti\\
H=0 (min) & $\Leftrightarrow$ partizione banale $\nu$
\end{tabular}
\end{center}
\end{frame}

\lyxframe{Partizionamento}
\center{un partizione \`e una relazione di equivalenza}, $i \sim j \Longleftrightarrow i,j \in A_k$

\bigskip{}
\begin{overprint}
\only<1>{\center{\includegraphics[height=0.5\textheight]{presentazione-immagini/reticolo-semplice2}}}

\only<2>{\center{\includegraphics[height=0.5\textheight]{presentazione-immagini/reticolo-bond}}}
\end{overprint}
relazione locale(tra vicini) => partizione globale\\
	=> colorazione di grafi, algoritmo Hoshen-Kopelman $\mathcal{O} (N\log(N))$

\end{frame}

\begin{frame}
\frametitle{Ordinamento parziale e fattori}
\begin{columns}
\column{0.35\textwidth}
\begin{block}{Ordinamento}
\begin{itemize}
\item $\alpha$ \`e \emph{black}{fattore} di $\beta$
\item $\beta$ \`e pi\`u fine di $\alpha$
\item $H(\alpha) < H(\beta)$
\end{itemize}
\end{block}
\bigskip{}
\begin{exampleblock}{Prodotto}
\begin{itemize}
\item propriet\`a associativa
\item elemento neutro $\nu$
\item ogni partizione \`e prodotto di fattori
\item ``\emph{black}{minimo comune multiplo}''
\end{itemize}
\end{exampleblock}
\column{0.65\textwidth}
\vspace{-0.5cm}
\center{\includegraphics[width=1\textwidth]{presentazione-immagini/fattori1}}\null
\vspace{0.8cm}
\center{\includegraphics[width=1\textwidth]{presentazione-immagini/fattori2}}\null

\end{columns}
\end{frame}

\begin{frame}{Prodotti tra partizioni}


Partizione prodotto $\gamma = \alpha \vee \beta$, pi\`u fine: \emph{black}{unione} dei bordi
\bigskip{}

\hspace{0.075\textwidth}\includegraphics[width=0.85\textwidth]{presentazione-immagini/prodotto}

\bigskip{}

Partizione intersezione $\sigma = \alpha \wedge \beta$, meno fine: \emph{black}{intersezione} dei bordi\\

\bigskip{}

\hspace{0.075\textwidth}\includegraphics[width=0.67\textwidth]{presentazione-immagini/intersezione}

\center{\`e il ``\emph{black}{massimo comune divisore}''}
\end{frame}



\begin{frame}{Distanza di Rohlin}


Distanza tra partizioni, tramite l'entropia del prodotto:
\[d_R(\alpha,\beta) = 2\,H(\alpha \vee \beta) - H(\alpha) - H(\beta)\]

Partizioni simili hanno piccola distanza:
\medskip{}
\begin{center}
\includegraphics[width=0.7\textwidth]{presentazione-immagini/distanze} 
\end{center}

\bigskip{}
Funziona perch\'e:
\begin{itemize}
\item prodotto idempotente $\alpha \vee \alpha = \alpha$ \\
\item l'entropia del prodotto \`e crescente $H(\alpha \vee \beta)\geq H(\alpha),\; \forall \beta$
\end{itemize}

\bigskip{}
Distanza piccola per partizioni estramemente frammentate...

\end{frame}


\begin{frame}{Riduzione e amplificazione della distanza}
Ridurre le partizioni: eliminare il pi\`u possibile fattori comuni

\bigskip{}
Definiamo una mappa dalle partizioni alle ridotte 
\[\alpha\otimes\beta\xrightarrow{\text{riduzione}}\hat{\alpha}(\alpha,\beta)\otimes\hat{\beta}(\alpha,\beta)\]
\begin{alertblock}{Algoritmo}
\begin{itemize}
 \item scomposizione delle due partizioni in fattori 
 \item confronto dei fattori tra le due partizioni
 \item scelta e scarto
 \item ricomposizione di ciascuna
\end{itemize}
\end{alertblock}
\bigskip{}
La distanza \`e sempre amplificata: \[R = \frac{d_R(\hat{\alpha}\otimes\hat{\beta})}{d_R(\alpha\otimes\beta)} \geq 1\]
\end{frame}



\begin{frame}{Confronto tra diverse riduzioni}

{\small
\begin{columns}
 \column{0.5\textwidth}
\begin{block}{Fattori lineari}
 \begin{itemize}
  \item \emph{black}{solo} partizioni lineari connesse
  \item ottimale come riduzione
  \item semplicissimo da implementare
 \end{itemize}
\end{block}

 \column{0.5\textwidth}
\begin{block}{Fattori dicotomici semplici}
 \begin{itemize}
  \item ovunque applicabile
  \item oneroso computazionalmente
  \item peggiore nel caso lineare
 \end{itemize}
\end{block}
\end{columns}
}
\bigskip{}
\hspace{-0.25cm}\includegraphics[width=1\textwidth]{presentazione-immagini/confronto_riduzioni}
\end{frame}



\begin{frame}
\frametitle{Definizione topologica della distanza}
Funzionale entropia indipendente dalla misura $\mu$:
\[H_\text{top} = \log(n) \qquad \text{n \`e il numero di atomi}\]
Una distanza di Rohlin opportunamente definita:
\[d_{\text{top}}(\alpha,\beta) = 2 \log (n_{\alpha \vee \beta}) - \log (n_{\alpha}) - \log (n_{\beta}) \]
\bigskip{}
\center{
\includegraphics[height=0.35\textheight]{presentazione-immagini/nr_coperture_dist_top}
}\null

\end{frame}

\section{Sequenze biologiche}


\begin{frame}{Proteine dell'influenza H3N2}

\begin{columns}
\column{0.5\textwidth}
\begin{itemize}
\item proteine come stringhe 
\item approccio \textit{black box}
\item sequenze lunghe 566
\item alfabeto di 24 lettere
\item solo 10\% mutazioni
\item \emph{black}{antigenic drift}
\end{itemize}

\column{0.5\textwidth}
\includegraphics[height=0.5\textheight]{immagini/swine-flu}
%\center{\small{Struttura del virus}}
\end{columns}
\medskip{}
Sequenze a confronto:
\medskip{}
\includegraphics[width=1\textwidth]{presentazione-immagini/seq_lines2}
\end{frame}

\begin{frame}[fragile]
\frametitle{Hamming \`e poco adatto}
\begin{columns}[b]
\column{0.65\textwidth}
\begin{semiverbatim} 
A=\{GHHAVPNGT\textbf{{\color{red}{L}}}VKTITTG\emph{red}{R}ICGDP\emph{red}{H}CDGFQNK\emph{red}{E}W\}
B=\{GHHAVPNGT\emph{red}{I}VKTITTG\emph{red}{E}ICGDP\emph{red}{Q}CDGFQNK\emph{red}{K}W\}
\end{semiverbatim}
\column{0.35\textwidth}
$d_H(A,B)$= \#differenze 
$d_H(A,B)=4$
\end{columns}
\bigskip{}

\begin{columns}
\column{0.65\textwidth}
\visible<2->{\includegraphics[width=0.9\textwidth]{grafici/clusters_hamming2}}

\column{0.35\textwidth}
\visible<2->{
\begin{block}{Antigenic drift}
$d_H \propto t$
\end{block}
}
\end{columns}
\end{frame}

\begin{frame}{Utilizzo misure entropiche}
\begin{overprint}
\begin{enumerate}
  \item<1-> Selezione N sequenze da un database (FluDB, NCBI) e allineamento
  \item<2-> Partizionamento delle sequenze
  \item<3-> Calcolo matrice $d_{ij}$ delle $N(N-1)/2$ distanze tra partizioni
 \medskip{}
\item<4-> N punti, distanti tra di loro $d_{ij}$ --- grafo completo tra le sequenze\medskip{}
\end{enumerate}

\begin{center}
\visible<4->{\includegraphics[height=0.55\textheight,keepaspectratio=true]{grafici/matrice-distanze}}
\end{center}
\end{overprint}

\end{frame}


\begin{frame}
\frametitle{Clustering di sequenze}

Suddivisione di N sequenze in p \emph{blue}{clusters}
\bigskip{}
 \begin{center}
\includegraphics[height=0.55\textheight,keepaspectratio=true]{immagini/dendrogramma}  
 % dendrogramma.png: 1287x784 pixel, 100dpi, 32.69x19.91 cm, bb=0 0 927 564

``Clustering gerarchico agglomerativo''
 \end{center}
\bigskip{}
Altri algoritmi: risultati qualitativamente indistinguibili
\end{frame}


\begin{frame}
\frametitle{Distanza e partizionamento ottimale}
\begin{columns}
 \column{0.5\textwidth}

\begin{overprint}
 \begin{block}{Partizioni di segmenti omogenei}

\begin{center}
\includegraphics[width=1\textwidth,keepaspectratio=true]{presentazione-immagini/partizioni1}

$d_R = 0.13$

\end{center}  
\end{block}
\bigskip{}
 \begin{block}<2->{Partizioni ridotte}
\begin{center}
\visible<2->{\includegraphics[width=1\textwidth,keepaspectratio=true]{presentazione-immagini/partizioni2} 

 $d_R = 1.07$}
\end{center}
\end{block}
\end{overprint}
\column{0.5\textwidth}
\includegraphics<3->[width=1\textwidth,keepaspectratio=true]{presentazione-immagini/clustering_finale}

\end{columns}

\end{frame}

\begin{frame}
\frametitle{Partizionamento alternativo}
\end{frame}

\section{Sistemi magnetici}

\begin{frame}
\frametitle{Sequenze lineari di spin (Ising 1D) }
\[H=-\sum_{i}\, J_{i,i+1}\sigma_{i}\sigma_{i+1}\qquad i\in\left\{ 1,\dots,L\right\} \]

variabili di \emph{blue}{link} $l_{i}=\sigma_{i}\sigma_{i+1}\qquad i\in\left\{ 1,\dots,L-1\right\} $

\[H=-J\sum_{i}l_{i}\]

\[l_{i}=\sigma_{i}\sigma_{i+1}\Longrightarrow {\sigma_{i}}=l_{i}\sigma_{i}\]

\begin{align}
 \left\langle \sigma_{i}\,\sigma_{i+r}\right\rangle &=\frac{1}{Z}\sum_{\sigma}\sigma_{i}\,\sigma_{i+r}\,\exp\left(\beta\sum_{k}l_{k}(\sigma)\right)\\
  &=\exp\left(-\frac{r}{\xi}\right)\qquad\text{con }\xi=-\frac{1}{\log\left(\tanh\beta J\right)}
\end{align}


\end{frame}
\begin{frame}
\frametitle{Clusters di spin $\Longleftrightarrow$ Clusters di link}


\end{frame}
\begin{frame}
\frametitle{Lunghezza di correlazione tra partizioni}


\end{frame}
\begin{frame}
\frametitle{Variazione in temperatura}


\end{frame}
\begin{frame}
\frametitle{Tipi di disordine}


\end{frame}
\begin{frame}
\frametitle{Ising 2D, reticolo quadrato}
\end{frame}

\end{document}