Cleaning up the project proposal

1 files changed, 95 insertions, 69 deletions

diff --git a/finale/project_proposal.tex b/finale/project_proposal.tex
index 5e0d21c..c8607e6 100644
--- a/finale/project_proposal.tex
+++ b/finale/project_proposal.tex
@@ -1,96 +1,122 @@
-\documentclass[8pt]{article}
+\documentclass[10pt]{article}
+\usepackage[utf8x]{inputenc}
 \usepackage{fullpage, amsmath, amssymb, amsthm}
+\usepackage{bbm}
+\DeclareMathOperator*{\argmax}{argmax}
 
-\title{Regression Analysis with Network data}
-\author{Jean Pouget-Abadie, Thibaut Horel}
-\date{}
+\title{Regression Analysis with Network Data}
+\author{Thibaut Horel \and Jean Pouget-Abadie}
 
 \begin{document}
 \maketitle
 
-\subsection*{The Network Inference problem}
+\section{Background: Cascade Models and Network Inference}
 
-The network inference problem concerns itself with learning the edges and the
-edge weights of an unknown network. Each edge weight $\theta_e, e\in E$ is a
-parameter to be estimated. The information at our disposal is the result of a
-cascade process on the network. Here, we will focus on the Generalized Linear
-Cascade (GLC) model introduced in~\cite{paper} presented below.
+The Network Inference Problem concerns itself with learning the edges and the
+edge weights of an unknown network on the set of vertices $V$. Formally, the
+set of parameters to learn is a matrix $\theta\in\mathbb{R}^{V\times V}$ where
+$\theta_{u,v}$ is the weight corresponding to the pair of vertices $(u, v)$.
+The observations at our disposal for this learning task are samples drawn for
+a probabilistic cascade model. In this project, we will focus on the
+Generalized Linear Cascade (GLC) model introduced in~\cite{pouget} that we
+briefly present below.
 
-\paragraph{The GLC model}
-
-Consider a graph $\mathcal{G} = (N, E)$, where nodes $N$ can be one of three
-possible states: susceptible, infected, and immune.  Let $x^t$ be the indicator
-variable of ``infected nodes'' at time step $t$.  A \emph{generalized linear
-cascade model} is a cascade model such that for each ``susceptible'' node $i$ at
-time step $t$, the probability of $i$ becoming ``infected'' at time step $t+1$
-conditioned on $x^t$ is a Bernoulli variable of parameter $f(\theta_i
-\cdot X^t)$:
+\paragraph{GLC model.} The nodes in $V$ can be in one of three possible states:
+susceptible, infected, and immune.  Let $x^t$ be the indicator variable of
+``infected nodes'' at time step $t$ and $S_t$ be the set of susceptible nodes
+at time step $t$. A \emph{generalized linear cascade model} is a discrete-time
+random process in which the conditional law of $x^{t+1}$ given $x^t$ takes the
+following form: for each ``susceptible'' node $i$ at time step $t$, the
+probability of $i$ becoming ``infected'' at time step $t+1$ conditioned on
+$x^t$ is a Bernoulli variable of parameter $f(\theta_i \cdot x^t)$:
 \begin{equation}
-    \mathbb{P}(x^{t+1}_i = 1|x^t) = f(\theta_i \cdot x^t)
+    \label{eq:model}
+    \mathbb{P}(x^{t+1}_i = 1\,|\,x^t) = f(\theta_i \cdot x^t),
+    \quad i\in S_t
 \end{equation}
-where $f: \mathbb{R} \rightarrow [0,1]$. There is no a priori rule for the
-transition from and to the immune and susceptible state, but the most commonly
-studied GLC model, known as the Independent Cascade model, assumes that all
+for some function $f: \mathbb{R} \rightarrow [0,1]$ and where $\theta_i
+= (\theta_{u, i})_{u\in V}$. There is no a priori rule for the transition from
+and to the immune and susceptible state, but the most commonly studied GLC
+model, known as the Independent Cascade model \cite{Kempe:03}, assumes that all
 infected nodes at time step $t$ are immune for all time steps $t' \geq t+1$.
 Under this assumption, a cascade ends when no ``infected'' nodes remain. The
 designer is also free to decide the initial state of graph $\mathcal{G}$ at the
-beginning of every cascade process. For simplicity, we will suppose that, at the
-start of each cascade, one node is chosen uniformly at random to be
+beginning of every cascade process. For simplicity, we will suppose that, at
+the start of each cascade, one node is chosen uniformly at random to be
 ``infected'', and that all other nodes are in the ``susceptible'' state.
 
-\bigskip
-The network inference problem can therefore be formalized as finding the support
-of the edge weight vector $\theta$ from the observation of ${(x^c_t)}_{c\in
-\mathcal{C}, t\in \mathcal{T}_C}$, where $\mathcal{C}$ indexes the cascade
-number, and $\mathcal{T}_C$ the time step in that cascade. Prior work has
-observed that the network inference problem is decomposable node-by-node
-i.e.~solving for $\beta_{i} = \{\theta_{i,j} | j \in N\}$ for node $i$. This can
-easily be formulated as the following maximum likelihood program:
-$$ \theta_{i} \in \arg \max_\theta \log
-\mathcal{L}_i(\theta_i\,|\,x^1,\ldots,x^n) = \frac{1}{|{\cal T}_i|} \sum_{t\in
-{\cal T}_i } x_i^{t+1}\log f(\theta_i\cdot x^{t}) + (1 -
-x_i^{t+1})\log\big(1-f(\theta_i \cdot x^t)\big)$$
-where $\mathcal{T}_i = \{\text{node i is ``susceptible'' at time step } t\}$.
-The reader will note the above problem boils down to fitting a generalized
-linear model. In particular, if $f$ is the sigmoid function, we are performing
+\paragraph{Inference.} A cascade is the collection of vectors $x^t$ for all
+time steps until the cascade ends. Given a sample of independent cascades, the
+parameters $\theta$ can be estimated using maximum likelihood estimation. Prior
+work has observed that the MLE problem can be decomposed node-by-node
+\emph{i.e}, $\theta_i$ can be learned independently for each node $i$ by
+solving the following optimization program:
+\begin{equation}
+    \label{eq:mle}
+    \hat{\theta}_{i} \in \argmax_\theta
+    \log \mathcal{L}_i(\theta_i) =
+    \sum_{t:i\in S_t} x_i^{t+1}\log f(\theta_i\cdot x^{t})
+    + (1 - x_i^{t+1})\log\big(1-f(\theta_i \cdot x^t)\big)
+\end{equation}
+The reader will observe that the above problem reduces to fitting a generalized
+linear model. It is important to note that even though the cascades are
+independent, the vectors $x^t$ observed within a cascade are not independent
+since they follow the Markov process described in \eqref{eq:model}. In the
+particular case where $f$ is the sigmoid function, we are performing
 logistic regression:
-$$
+\begin{displaymath}
 \begin{cases}
-y_i^* = \theta_i \cdot x_i + \epsilon \text{~where~} \epsilon\sim
-Logistic(0, 1) \text{~and~} x = {(x^t)}_{t \in \mathcal{T}_i}\\
-y_i = [y_i^* > 0] \text{~where~} y_i^t = x_i^{t+1}
+    y^t = \theta_i \cdot x^t + \varepsilon^t
+    &\text{where } \varepsilon^t\sim \text{Logistic}(0, 1)\\
+    \tilde{y}^t = \mathbf{1}\{y^t > 0\} &\text{where } x_i^{t+1} = \tilde{y}^t
 \end{cases}
-$$
+\end{displaymath}
 
-\subsection*{Objectives}
+\section{Problem Statement}
 
+A growing series of work (see for example \cite{Netrapalli:2012,
+Daneshmand:2014, pouget}) has focused on solving the Network Inference Problem
+under different cascade models and obtaining estimators with close-to-optimal
+convergence rates. However, these works often rely on hard-to-interpret
+assumptions which often hide subtle properties of the probabilistic model
+\eqref{eq:model}. The overarching goal of the current project is to analyze the
+fundamental statistical properties of observations coming from model
+\eqref{eq:model} and of the MLE estimator \eqref{eq:mle}. In particular we are
+interested in the following questions:
 \begin{itemize}
-\item Try a Bayesian approach to estimate these parameters. Use the posterior
-predictive distribution to obtain confidence intervals for the edge parameters.
-Validate this with bootstrapping. How does this perform in different networks?
-Can you intuitively link certain node-level/graph-level properties with the
-resulting variance on the estimated parameter?
-\item Do the previous observations correspond with the theoretical result, given
-by the Fisher information matrix: $$\hat \beta \sim \mathcal{N}(\beta,
-I{(\theta)}^{-1})$$ where $I(\theta) = - {\left(\frac{\partial^2\log
-\mathcal{L}}{\partial \theta^2} \right)}^{-1}$
+\item Is the model \eqref{eq:model} identifiable and is the MLE estimator
+    \eqref{eq:mle} consistent? Are there networks which are fundamentally
+    ambiguous and for which the Network Inference Problem is unsolvable?
+\item Use a Bayesian approach to estimate the parameters. Use the posterior
+    predictive distribution to obtain confidence intervals for the edge
+    parameters. Validate this with bootstrapping.
+\item Are there networks which are harder to learn than others? Can the
+    variance of the MLE estimator be related to certain graph theoretic
+    properties of the network?
+\item Do the previous observations match with the theoretical result, given
+by the Fisher information matrix:
+\begin{displaymath}
+    \hat{\theta}_i \sim \mathcal{N}(\theta_i, I{(\theta_i)}^{-1})
+    \quad \text{where}\;
+    I(\theta) = - \left(\frac{\partial^2\log \mathcal{L}_i}{\partial \theta^2}
+    \right)^{-1}
+\end{displaymath}
 \item Are there networks in which the Fisher information matrix is singular?
-What happens to the estimation of $\beta$ in this case?
-\item What if the generative process is generated with a different link
-function? Is there a regularization scheme which can mitigate any bias/exploding
-variance in the estimated parameters?
+What happens to the estimation of $\theta_i$ in this case?
+\item Is the estimator \eqref{eq:mle} robust to the choice of $f$? What if the
+    observations are generated with $f_1$, but \eqref{eq:mle} is solved with
+    $f_2\neq f_1$? Is there a regularization scheme which can mitigate any bias
+    or lack of convergence in the estimated parameters?
 \end{itemize}
 
-\subsection*{Program plan}
-
-The project will be a series of simulations to answer each of the above
-questions? When possible, we will try to explain the results found in the
-simulation with a simplified analysis on toy-networks. Thibaut and I have worked
-together in the past, and have kept our contributions balanced.
+\paragraph{Roadmap.} We plan to answer the above question by a mixture of
+a theoretical-based and a simulation-based approaches. We expect some of these
+questions to be hard from the theoretical standpoint. In those cases, the
+hardness can be mitigated by using simulations or focusing on specific cases:
+toy-networks (star graph, cycle, complete graph, etc.) or simpler cascades
+models (the Voter Model for example).
 
-\begin{thebibliography}{1}
-\bibitem{paper} Pouget-Abadie, J. and Horel, T. \emph{Inferring Graphs from
-Cascades: A Sparse Recovery Framework}, ICML 2015
-\end{thebibliography}
+\bibliography{sparse}
+\bibliographystyle{abbrv}
 
 \end{document}