adding bayes description + references

1 files changed, 44 insertions, 28 deletions

diff --git a/finale/mid_report.tex b/finale/mid_report.tex
index 38d9020..9873abd 100644
--- a/finale/mid_report.tex
+++ b/finale/mid_report.tex
@@ -73,30 +73,37 @@ Two subquestions:
 The study of edge prediction in graphs has been an active field of research for
 over a decade~\cite{Nowell08, Leskovec07, AdarA05}.~\cite{GomezRodriguez:2010}
 introduced the {\scshape Netinf} algorithm, which approximates the likelihood of
-cascades represented as a continuous process.  The algorithm was improved in
-later work~\cite{gomezbalduzzi:2011}, but is not known to have any theoretical
+cascades represented as a continuous process.  The algorithm, relying on
+Maximum-Likelihood and convex relaxations was improved in later
+work~\cite{gomezbalduzzi:2011}, but is not known to have any theoretical
 guarantees beside empirical validation on synthetic networks.
 \cite{Netrapalli:2012} studied the discrete-time version of the independent
 cascade model and obtained the first ${\cal O}(s^2 \log m)$ recovery guarantee
 on general networks, by using unregularized MLE and making a {\it correlation
-decay\/} assumption, which limits the number of new infections at every step. In
-this setting, they show a lower bound of the number of cascades needed for
-support recovery with constant probability of the order $\Omega(s \log (m/s))$.
-They also suggest a {\scshape Greedy} algorithm, which achieves a ${\cal O}(s
-\log m)$ guarantee in the case of tree graphs. The work of~\cite{Abrahao:13}
-studies the same continuous-model framework as \cite{GomezRodriguez:2010} and
-obtains an ${\cal O}(s^9 \log^2 s \log m)$ support recovery algorithm, without
-the \emph{correlation decay} assumption.  \cite{du2013uncover,Daneshmand:2014}
-propose Lasso regularization of MLE for recovering the weights of the graph
-under a continuous-time independent cascade model. The work
-of~\cite{du2014influence} is slightly orthogonal to ours since they suggest
-learning the \emph{influence} function, rather than the parameters of the
-network directly.
+decay\/} assumption, which limits the number of new infections at every step.
+They also suggest a {\scshape Greedy} algorithm, with provably good performance
+in tree graphs, which maintains a counter of each node's antecedents, i.e. the
+set of nodes infected at a prior time step to its infection time. The work
+of~\cite{Abrahao:13} studies the same continuous-model framework as
+\cite{GomezRodriguez:2010} and obtains an ${\cal O}(s^9 \log^2 s \log m)$
+support recovery algorithm, without the \emph{correlation decay} assumption.
+\cite{du2013uncover,Daneshmand:2014} propose Lasso regularization of MLE for
+recovering the weights of the graph under a continuous-time independent cascade
+model. The work of~\cite{du2014influence} is slightly orthogonal to ours since
+they suggest learning the \emph{influence} function, rather than the parameters
+of the network directly.
 
-More recently, the inference of Hawkes process is perhaps the closest related
-topic to our work, with recent papers \cite{linderman2014discovering,
-linderman2015scalable} , focusing on MLE, EM, and Variational
-Inference methods to learning these processes.
+More recently, the continuous process studied in previous work has been
+reformulated as a Hawkes process, with recent papers
+\cite{linderman2014discovering, linderman2015scalable, simma2012modeling},
+focusing on Expectation-Maximization, and Variational Inference methods to learn
+these processes. Because of the discrete nature of the GLC model, we hope to
+bring a better understanding to the link between the properties of a graph and
+its \emph{learnability}. We wish to further explore the idea of non-product
+priors raised in \cite{linderman2014discovering, linderman2015scalable}, since
+the experimental validation of their work focused on simple graph priors.
+Finally, the \emph{Active Learning} formulation is, to the best of the
+authors' knowledge, novel in this context.
 
 \section{Model}
 
@@ -228,6 +235,7 @@ then the model is identifiable.
 \section{Inference}
 
 \subsection{Maximum-Likelihood Estimation}
+\label{MLEsec}
 
 Because transitions occur independently for each node $i$, the log-likelihood
 is a sum of $k$ terms, each term $i$ only depending on $\bt_i$. Hence, each
@@ -282,11 +290,19 @@ Though straightforward MCMC could be applied here, recent
 work~\cite{caimo2011bayesian, koskinen2010analysing, robins2007recent} has shown
 that ERGM inference has slow convergence and lack of robustness, developping
 better alternatives to naive MCMC formulations. Experiments using such a prior
-are ongoing, but we present only simple product distribution-type priors here.
+are ongoing, but we present results only for simple product distribution-type
+priors here.
 
 \paragraph{Inference}
-We can sample from the posterior by MCMC\@. This might not be the fastest
-solution however. We could greatly benefit from using an alternative method:
+We can sample from the posterior by MCMC\@ using the PyMC library, which works
+relatively well (see paragraph on \emph{experiments}. If the prior is a product
+distribution, then we can simply do Bayesian GLM regression, as in
+Section~\ref{MLEsec}. However, computing the posterior edge-by-edge does not
+accomodate for complex priors, which could encourage for example the presence of
+triangles or two stars. For such priors, we must sample from the posterior of
+the Markov chain directly, which is what we have done here.  This method is very
+slow however, and scales badly as a result of the number of cascades and number
+of nodes. We could greatly benefit from using an alternative method:
 \begin{itemize}
 \item EM\@. This approach was used in \cite{linderman2014discovering,
 simma2012modeling} to learn
@@ -314,12 +330,12 @@ parameter space.
 \includegraphics[scale=.4]{../simulation/plots/2015-11-05_22:57:26.pdf}}
 \subfloat[][1000 cascades]{
 \includegraphics[scale=.4]{../simulation/plots/2015-11-05_22:58:29.pdf}}
-\caption{Bayesian Inference of $\Theta$ with MCMC using a $Beta(1, 1)$ prior.
-For each figure, the plot $(i, j)$ on the $i^{th}$ row and $j^{th}$ column
-represent a histogram of samples taken from the  posterior of the corresponding
-edge $\Theta_{i, j}$. The red line indicates the true value of the edge weight.
-If an edge does not exist (has weight $0$) the red line is confounded with the y
-axis.}
+\caption{Bayesian Inference of $\Theta$ with MCMC using a $Beta(1, 1)$ prior on
+each edge.  For each figure, the plot $(i, j)$ on the $i^{th}$ row and $j^{th}$
+column represent a histogram of samples taken from the  posterior of the
+corresponding edge $\Theta_{i, j}$. The red line indicates the true value of the
+edge weight.  If an edge does not exist (has weight $0$) the red line is
+confounded with the y axis.}
 \label{betapriorbayeslearning}
 \end{figure}