Polishing: end of section 2

1 files changed, 57 insertions, 56 deletions

diff --git a/paper/sections/model.tex b/paper/sections/model.tex
index 0f7eff7..1625292 100644
--- a/paper/sections/model.tex
+++ b/paper/sections/model.tex
@@ -1,8 +1,8 @@
-We consider a graph ${\cal G}= (V, E, \Theta)$, where $\Theta$ is $|V|\times
-|V|$ matrix of paremeters describing the edge weights of $\mathcal{G}$.
-A \emph{cascade model} is a Markov process over the finite state space $\{0, 1,
-\dots, K\}^V$. An \emph{influence cascade} is a realisation of the random
-process described by a cascade model.
+We consider a graph ${\cal G}= (V, E, \Theta)$, where $\Theta$ is a $|V|\times
+|V|$ matrix of paremeters describing the edge weights of $\mathcal{G}$. We
+define $m\defeq |V|$. A \emph{cascade model} is a Markov process over the
+finite state space $\{0, 1, \dots, K\}^V$. An \emph{influence cascade} is
+a realisation of the random process described by a cascade model.
 
 In practice, we restrict ourselves to discrete-time homogeneous cascade models.
 At $t=0$, each node in the graph has a constant probability $p_{init}$ of being
@@ -14,21 +14,23 @@ and \cite{Abrahao:13}.
 
 \subsection{Generalized Linear Cascade Models}
 
-Denoting by $X^t$ the state of the cascade at time step $t-1$, we interpret
-$X^t_j = 1$ for some node $j\in V$ as ``node $j$ is active'', \emph{i.e}, ``$j$
-exhibits the source nodes' behavior at time step $t+1$''.  We draw inspiration
+Denoting by $X^t$ the state of the cascade at time step $t$, we interpret
+$X^t_j = 1$ for node $j\in V$ as ``node $j$ is active'', \emph{i.e}, ``$j$
+exhibits the source nodes' behavior at time step $t$''.  We draw inspiration
 from \emph{generalized linear models} (GLM) to define a generalized linear
 cascade.
 
-\begin{definition} Let us denote by $\{\mathcal{F}_t, t\in\ints\}$ the natural
+\begin{definition}
+    \label{def:glcm} 
+    Let us denote by $\{\mathcal{F}_t, t\in\ints\}$ the natural
     filtration induced by $\{X_t, t\in\ints\}$. A \emph{generalized linear
     cascade} is characterized by the following equation:
     \begin{displaymath}
-        \P[X^{t+t}=x\,|\, \mathcal{F}_t] =
-        \prod_{i\in V} f(\inprod{\theta_i}{X^{t}})^{x_i}
+        \P[X^{t+1}=x\,|\, \mathcal{F}_t] =
+        \prod_{i=1}^m f(\inprod{\theta_i}{X^{t}})^{x_i}
         \big(1-f(\inprod{\theta_i}{X^{t}}\big)^{1-x_i}
     \end{displaymath}
-where $f:\mathbb{R}\to[0,1]$.
+where $f:\mathbb{R}\to[0,1]$ and $\theta_i$ is the $i$-th column of $\Theta$.
 \end{definition}
 
 It follows immediately from this definition that a generalized linear cascade
@@ -45,13 +47,22 @@ cascade model.
 
 In this section, we show that both the Independent Cascade Model and the Voter
 model are Generalized Linear Cascades. The Linear Threshold model will be
-discussed in Section~\ref{sec:linear_threshold}
+discussed in Section~\ref{sec:linear_threshold}.
 
 \subsubsection{Independent Cascade Model}
 
-In the independent cascade model, nodes can be either susceptible, active or inactive. At $t=0$, all source nodes are ``active'' and all remaining nodes are ``susceptible''. At each time step $t$, for each edge $(i,j)$ where $j$ is susceptible and $i$ is active, $i$ attempts to infect $j$ with probability $p_{i,j}\in[0,1]$. If $i$ succeeds, $j$ will become active at time step $t+1$. Regardless of $i$'s success, node $i$ will be inactive at time $t+1$. In other words, nodes stay active for only one time step. The cascade process terminates when no active nodes remain.
+In the independent cascade model, nodes can be either susceptible, active or
+inactive. At $t=0$, all source nodes are ``active'' and all remaining nodes are
+``susceptible''. At each time step $t$, for each edge $(i,j)$ where $j$ is
+susceptible and $i$ is active, $i$ attempts to infect $j$ with probability
+$p_{i,j}\in[0,1]$, the infection attempts are independent of each other. If $i$
+succeeds, $j$ will become active at time step $t+1$. Regardless of $i$'s
+success, node $i$ will be inactive at time $t+1$. In other words, nodes stay
+active for only one time step. The cascade process terminates when no active
+nodes remain.
 
-If we denote by $X^t$ the indicator variable of the set of active nodes at time step $t-1$, then if $j$ is susceptible at time step $t-1$, we have:
+If we denote by $X^t$ the indicator variable of the set of active nodes at time
+step $t$, then if $j$ is susceptible at time step $t+1$, we have:
 \begin{displaymath}
     \P\big[X^{t+1}_j = 1\,|\, X^{t}\big]
     = 1 - \prod_{i = 1}^m (1 - p_{i,j})^{X^t_i}.
@@ -62,33 +73,35 @@ Defining $\Theta_{i,j} \defeq \log(1-p_{i,j})$, this can be rewritten as:
     \P\big[X^{t+1}_j = 1\,|\, X^{t}\big]
     = 1 - \prod_{i = 1}^m e^{\Theta_{i,j}X^t_i}
     = 1 - e^{\inprod{\theta_j}{X^t}}
-\end{equation} where we defined $\theta_j\defeq (\Theta_{1,j},\ldots,\Theta_{m,j})$.
+\end{equation}
+which is a Generalized Linear Cascade model with inverse link function $f(z)
+= z$.
 
 \subsubsection{The Voter Model}
 
-In the Voter Model, nodes can be either red or blue, where ``blue'' is the source state. The parameters of the graph are normalized such that $\forall i, \ \sum_j \Theta_{i,j} = 1$. Each round, every node $j$ chooses one of its neighbors with probability $\Theta_ij$ and adopts their color. The cascades stops at a fixed horizon time T or if all nodes are of the same color. If we denote by $X^t$ the indicator variable of the set of blue nodes at time step $t-1$, then we have:
+In the Voter Model, nodes can be either red or blue, where ``blue'' is the
+source state. The parameters of the graph are normalized such that $\forall i,
+\ \sum_j \Theta_{i,j} = 1$. Each round, every node $j$ independently chooses
+one of its neighbors with probability $\Theta_ij$ and adopts their color. The
+cascades stops at a fixed horizon time T or if all nodes are of the same color.
+If we denote by $X^t$ the indicator variable of the set of blue nodes at time
+step $t$, then we have:
 \begin{equation}
 \mathbb{P}\left[X^{t+1}_j = 1 | X^t \right] = \sum_{i=1}^m \Theta_{i,j} X_i^t = \inprod{\theta_j}{X^t}
 \tag{V}
 \end{equation}
+which is again a Generalized Linear Cascade model with inverse link function
+$f(z) = z$.
 
 \subsection{Maximum Likelihood Estimation}
 
-Recovering the intrinsic graph parameters $\Theta$ from observed influence
-cascades is the central question of the present work and is important for the
-following two reasons: \begin{enumerate} \item knowing the influence parameters
-            allows for future prediction of influence cascades.  \item when the
-        set of edges $E$ is unknown, it can be recovered from the influence
-parameters.  \end{enumerate} We note that recovering the edges in $E$ from
-observed influence cascades is a well-identified problem known as the
-\emph{Graph Inference} problem. However, recovering the influence parameters is
-no less important and has been seemingly overlooked so far. The machinery
-developped in this work addresses both problems for a large class of well-known
-cascade models.
-
-In both models, the unknown influence parameters are described by an $m\times
-m$ matrix $\Theta$. Furthermore, the information of the edges of $G$ is fully
-contained in $\Theta$:
+Recovering the model parameter $\Theta$ from observed influence cascades is the
+central question of the present work. Recovering the edges in $E$ from observed
+influence cascades is a well-identified problem known as the \emph{Graph
+Inference} problem. However, recovering the influence parameters is no less
+important and has been seemingly overlooked so far. In this work we focus on
+recovering $\Theta$, noting that the set of edges $E$ can then be recovered
+through the following equivalence:
 \begin{displaymath}
     (i,j)\in E\Leftrightarrow  \Theta_{i,j} \neq 0
 \end{displaymath}
@@ -104,31 +117,19 @@ problem:
 where $\lambda$ is the regularization factor which helps at preventing
 overfitting as well as controlling for the sparsity of the solution.
 
-Note that both the (IC) and the (LT) models are decomposable in the following
-sense: the state evolution of each node at each time step happens independently
-of the following nodes \emph{and} the state evolution of node $j\in V$ only
-depends on $\theta_j$, the $j$-th column of $\Theta$. Consequently, the
-log-likelihood function $\mathcal{L}$ can be written as a sum of $m$ terms,
-each term $j\in\{1,\ldots,m\}$ only involving $\theta_j$. Since this is equally
-true for $\|\Theta\|_1$, each column $\theta_j$ of $\Theta$ can be estimated by
-a separate optimization program:
+The generalized linear cascade model is decomposable in the following sense:
+given Definition~\ref{def:glcm}, the log-likelihood can be written as the sum
+of $m$ terms, each term $i\in\{1,\ldots,m\}$ only depending on $\theta_i$.
+Since this is equally true for $\|\Theta\|_1$, each column $\theta_i$ of
+$\Theta$ can be estimated by a separate optimization program:
 \begin{equation}\label{eq:pre-mle}
-    \hat{\theta}_j \in \argmax_{\theta} \mathcal{L}_j(\theta_j\,|\,x^1,\ldots,x^n)
-    + \lambda\|\theta_j\|_1
+    \hat{\theta}_i \in \argmax_{\theta}\frac{1}{n_i}\mathcal{L}_i(\theta_i\,|\,x^1,\ldots,x^n)
+    + \lambda\|\theta_i\|_1
 \end{equation}
-
-Furthermore, the state evolution of a node $j\in V$ has the same structure in
-both models: the transition from susceptible to active at time step $t+1$ is
-controlled by a Bernoulli variable whose parameter can be written
-$f(\inprod{\theta_j}{x^t})$ for some function $f$. Hence, if we denote by $n_j$
-the first step at which $j$ becomes active, we can rewrite the  MLE program
-\eqref{eq:pre-mle}:
+where we denote by $n_i$ the first step at which node $i$ becomes active and
+where:
 \begin{multline}
-    \hat{\theta}_j \in \argmax_{\theta} \frac{1}{n_j}
-    \sum_{t=1}^{n_j-1}\log\big(1-f(\inprod{\theta_j}{x^t})\big)\\
-\log f(\inprod{\theta_j}{x^{n_j}})+ \lambda\|\theta_j\|
+    \mathcal{L}_i(\theta_i\,|\,x^1,\ldots,x^n) = \frac{1}{n_i}
+    \sum_{t=1}^{n_i-1}\log\big(1-f(\inprod{\theta_i}{x^t})\big)\\
++\log f(\inprod{\theta_i}{x^{n_i}})+ \lambda\|\theta_i\|_1
 \end{multline}
-
-
-
-