path: root/notes/presentation/beamer_2.tex

\documentclass[10pt]{beamer}

\usepackage{amssymb, amsmath, graphicx, amsfonts, color, amsthm, wasysym}

\newtheorem{proposition}{Proposition}

\title{Learning from Diffusion processes}
\subtitle{What cascades really teach us about networks}
\author{Jean (John) Pouget-Abadie \\ Joint Work with Thibaut (T-bo) Horel}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}
\frametitle{Introduction}

%notes: Learn what? the network, the parameters of the diffusion process.

\begin{table}
\centering
\begin{tabular}{c | c}
Network & Diffusion process \\[1ex]
\hline
\\
Airports & Infectious diseases (SARS) \\
 & Delays (Eyjafjallajökull) \\[3ex]
Social Network & Infectious diseases (flu) \\
 & Behaviors (Ice Bucket Challenge) \\[3ex]
Internet/WWW & Information diffusion (Memes, Pirated content \dots)
\end{tabular}
\end{table}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Introduction}

What do we know? What do we want to know?

\begin{itemize}
\item We know the {\bf airport network} structure. We observe delays. Can we learn how delays propagate?
\item  We (sometimes) know the {\bf social network}. We observe behaviors. Can we learn who influences whom?
\item Rarely know {\bf blog network}. We observe discussions. Can we learn who learns from whom?
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Independent Cascade Model}

\begin{figure}
\includegraphics[scale=.3]{figures/weighted_graph.png}
\caption{Weighted, directed graph}
\end{figure}

\begin{itemize}
\item At $t=0$, nodes are in three possible states: susceptible, {\color{blue} infected}, {\color{red} dead}
\item Each {\color{blue} infected} node $i$ has a ``one-shot'' probability $p_{i,j}$ of infecting each of his susceptible neighbors $j$ at $t+1$.
\item A node stays {\color{blue}  infected} for one round, then it {\color{red} dies}
\item At $t=0$, each node is {\color{blue} infected} with probability $p_{\text{init}}$
\item Process continues until random time $T$ when no more nodes can become infected. 
\item $X_t$: set of {\color{blue}  infected} nodes at time $t$
\item A {\bf cascade} is an instance of the ICC model: $(X_t)_{t=0, t=T}$
\end{itemize}

%Notes: Revisit the celebrated independent cascade model -> Influence maximisation is tractable, requires knowledge of weights

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Independent Cascade Model}

\begin{figure}
\includegraphics[scale=.5]{figures/weighted_graph.png}
\caption{Weighted, directed graph}
\end{figure}

\begin{block}{Example}
\begin{itemize}
\item At $t=0$, the {\color{orange} orange} node is infected, and the two other nodes are susceptible. $X_0 = $({\color{orange} orange})
\item At $t=1$, the {\color{orange}} node infects the {\color{blue} blue} node and fails to infect the {\color{green} green} node. The {\color{orange} orange} node dies. $X_1 = $({\color{blue} blue})
\item At $t=2$, {\color{blue} blue} dies. $X_2 = \emptyset$
\end{itemize}
\end{block}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Independent Cascade Model}

\begin{figure}
\includegraphics[scale=.5]{figures/weighted_graph.png}
\caption{Weighted, directed graph}
\end{figure}

\begin{itemize}
\item If the {\color{orange} orange} node and the {\color{green} green} node are infected at $t=0$, what is the probability that the {\color{blue} blue} node is infected at $t=1$?
$$1 - \mathbb{P}(\text{not infected}) = 1 - (1 - .45)(1-.04)$$
\end{itemize}


\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Independent Cascade Model}
\begin{figure}
\includegraphics[scale=.5]{figures/weighted_graph.png}
\caption{Weighted, directed graph}
\end{figure}

\begin{itemize}
\item In general, for each susceptible node $j$:
$$\mathbb{P}(j \text{ becomes infected at t+1}|X_{t}) = 1 - \prod_{i \in {\cal N}(j) \cap X_{t}} (1 - p_{i,j})$$
\end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Independent Cascade Model}
For each susceptible node $j$, the event that it becomes {\color{blue} infected} conditioned on previous time step is a Bernoulli:
$$(j \in X_{t+1} | X_t) \sim {\cal B} \big(f(X_t \cdot \theta_j) \big)$$
\begin{itemize}
\item $\theta_{i,j} := \log(1 - p_{i,j})$
\item $\theta_j := (0, 0, 0, \theta_{4,j}, 0 \dots, \theta_{k,j}, \dots)$
\item $f : x \mapsto 1 - e^x$
\begin{align*}
\mathbb{P}(j\in X_{t+1}|X_{t}) & = 1 - \prod_{i \in {\cal N}(j) \cap X_{t}} (1 - p_{i,j}) \\
& = 1 - \exp \left[ \sum_{i \in {\cal N}(j) \cap X_{t}} \log(1 - p_{i,j}) \right] \\
& = 1 - \exp \left[ X_{t} \cdot \theta_{j}\right]
\end{align*}
\end{itemize}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Independent Cascade Model}
For each susceptible node $j$, the event that it becomes {\color{blue} infected} conditioned on previous time step is a Bernoulli:
$$(j \in X_{t+1} | X_t) \sim {\cal B} \big(f(X_t \cdot \theta_j) \big)$$

\begin{block}{Decomposability}
\begin{itemize}
\item Conditioned on $X_t$, the state of node $j$ is sampled independently from node $j+1$
\item We can learn the parents of each node independently
\end{itemize}
\end{block}

\begin{block}{Sparsity}
\begin{itemize}
\item $\theta_{i,j} = 0 \Leftrightarrow \log(1 - p_{i,j}) = 0 \Leftrightarrow p_{i,j} = 0$
\item If graph is ``sparse'', then $p_{j}$ is sparse, then $\theta_j$ is sparse.
\end{itemize}
\end{block}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Sparse Recovery}
\begin{figure}
\includegraphics[scale=.6]{../images/sparse_recovery_illustration_copy.pdf}
\caption{$\mathbb{P}(j \in X_{t+1}| X_t) = f(X_t\cdot \theta)$}
\end{figure}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Sparse Recovery}
\begin{figure}
\includegraphics[scale=.6]{../images/sparse_recovery_illustration.pdf}
\caption{$\mathbb{P}(j \in X_{t+1}| X_t) = f(X_t\cdot \theta)$}
\end{figure}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Learning from Diffusion Processes}
\begin{block}{Problem Statement}
\begin{itemize}
\item We are given a graph ${\cal G}$, and a diffusion process $f$ parameterized by $\left((\theta_j)_j, p_{\text{init}}\right)$. 
\item Suppose we {\bf only} observe $(X_t)$ from the diffusion process.
\item Under what conditions can we learn $\theta_{i,j}$ for all $(i,j)$?
\end{itemize}
\end{block}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Learning from Diffusion Processes}

% \begin{figure}
% \includegraphics[scale=.4]{../images/sparse_recovery_illustration.pdf}
% \caption{Generalized Cascade Model for node $i$}
% \end{figure}

\begin{block}{Likelihood Function}
\begin{align*}
{\cal L}(\theta_1, \dots, \theta_m| X_1, \dots  X_n) = \sum_{i=1}^m \sum_{t} & X_{t+1}^i \log f(\theta_i \cdot X_t) + \\
& (1 - X_{t+1}^i) \log(1 - f(\theta_i \cdot X_t))
\end{align*}
\end{block}

\begin{block}{MLE}
For each node $i$, $$\theta_i \in \arg \max {\cal {L}}_i(\theta_i | X_1, X_2, \dots, X_n) - \lambda \|\theta_i\|_1$$
\end{block}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Conditions}
\begin{block}{On $f$}
\begin{itemize}
\item $\log f$ and $\log (1-f)$ have to be concave
\item $\log f$ and $\log (1-f)$ have to have bounded gradient
\end{itemize}
\end{block}

\begin{block}{On $(X_t)$}
\begin{itemize}
\item Want ${\cal H}$ be the hessian of ${\cal L}$ with respect to $\theta$ to be ``inversible''
\item $ n < dim(\theta) \implies {\cal H}$ is degenerate.
\item {\bf Restricted Eigenvalue condition} = ``almost invertible'' on sparse vectors. 
\end{itemize}
\end{block}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Restricted Eigenvalue Condition}

\begin{definition}
Let $S$ be the set of parents of node $i$.
$${\cal C} := \{ \Delta : \|\Delta\|_2 = 1, \|\Delta_{\bar S}\|_1 \leq 3 \| \Delta_S\|_1 \}$$
${\cal H}$ verifies the $(S, \gamma)$-RE condition if:
$$\forall \Delta \in {\cal C}, \Delta {\cal H} \Delta \geq \gamma$$
\end{definition}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Main Result}
Adapting a result from \cite{Negahban:2009}, we have the following theorem:

\begin{theorem}
Assume 
\begin{itemize}
\item the Hessian verifies the $(S,\gamma)$-RE condition
\item $f$ and $1-f$ are log-concave
\item $|(\log f)'| < \frac{1}{\alpha}$ and $|(\log 1- f)'| < \frac{1}{\alpha}$ 
\end{itemize} then with high probability:
$$\| \theta^*_i - \hat \theta_i \|_2 \leq \frac{6}{\gamma}\sqrt{\frac{s\log m}{\alpha n}}$$
\end{theorem}

\begin{corollary}
By thresholding $\hat \theta_i$, if $n > C' s \log m$, we recover the support of $\theta^*$ and therefore the edges of ${\cal G}$
\end{corollary}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Main result}

\begin{block}{Correlation}
\begin{itemize}
\item Positive result despite correlated measurements \smiley
\item Independent measurements $\implies$ taking one measurement per cascade.
\end{itemize}
\end{block}

\begin{block}{Statement w.r.t observations and not the model}
\begin{itemize}
\item The Hessian must verify the $(S,\gamma)$-RE condition \frownie
\item Can we make a conditional statement on $\theta$ and not $X_t$?
\end{itemize}
\end{block}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Restricted Eigenvalue Condition}

\begin{block}{From Hessian to Expected Hessian}
\begin{itemize}
\item If $n > C' s^2 \log m$ and $(S, \gamma)$-RE holds for $\mathbb{E}({\cal H})$, then $(S, \gamma/2)$-RE holds for ${\cal H}$
\item $\mathbb{E}({\cal H})$ only depends on $p_{\text{init}}$ and $(\theta_j)_j$
\end{itemize}
\end{block}

\begin{block}{From Hessian to Gram Matrix}
\begin{itemize}
\item If $\log f$ and $\log 1 -f$ are strictly log-concave with constant $c$, then if $(S, \gamma)$-RE holds for $\mathbb{E}({\cal H})$, then $(S, c \gamma)$-RE holds for the gram matrix $X X^T$
\item Gram Matrix has natural interpretation:
\begin{itemize}
\item Diagonal : average number of times node is infected
\item Outer-diagonal : average number of times pair of nodes is infected {\emph together}
\end{itemize}
\end{itemize}
\end{block}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Future Work}
\begin{itemize}
\item Better lower bounds
\item Active Learning
\item Lower bound restricted eigenvalues of expected gram matrix
\item Confidence Intervals
\item Show that $n > C' s \log m$ measurements are necessary w.r.t. expected hessian.
\item Linear Threshold model $\rightarrow$ 1-bit compressed sensing formulation
\end{itemize}
\end{frame}


%%%%%%%%%%%%%%%%%

\bibliography{../../paper/sparse}
\bibliographystyle{apalike}

\end{document}