diff options
| -rw-r--r-- | paper/sections/linear_threshold.tex | 8 | ||||
| -rw-r--r-- | paper/sections/results.tex | 9 | ||||
| -rw-r--r-- | src/convex_optimization.py | 2 | ||||
| -rw-r--r-- | src/make_plots.py | 8 |
4 files changed, 11 insertions, 16 deletions
diff --git a/paper/sections/linear_threshold.tex b/paper/sections/linear_threshold.tex index 56febe1..ff33c07 100644 --- a/paper/sections/linear_threshold.tex +++ b/paper/sections/linear_threshold.tex @@ -1,9 +1,7 @@ -In the Linear Threshold Model, each node $j\in V$ has a threshold $t_j$ from the interval $[0,1]$ and for each node, the sum of incoming weights is less than $1$: $\forall j\in V$, $\sum_{i=1}^m \Theta_{i,j} \leq 1$. +The Linear Threshold model can \emph{also} be cast a generalized linear cascade model. However, as we show below, its link function is non-differentiable and necessitates a different analysis. In the Linear Threshold Model, each node $j\in V$ has a threshold $t_j$ from the interval $[0,1]$ and for each node, the sum of incoming weights is less than $1$: $\forall j\in V$, $\sum_{i=1}^m \Theta_{i,j} \leq 1$. Nodes have two states: susceptible or active. At each time step, each susceptible -node $j$ becomes active if the sum of the incoming weights from active parents is greater than $j$'s threshold $t_j$. Nodes remain active until the end of the cascade, which is reached when no new susceptible nodes become active. - -As such, the source nodes are chosen, the process is entirely deterministic. Let $X^t$ be the indicator variable of the set of active nodes at time step $t-1$, then: +node $j$ becomes active if the sum of the incoming weights from active parents is greater than $j$'s threshold $t_j$. Nodes remain active until the end of the cascade, which is reached when no new susceptible nodes become active. As such, the source nodes are chosen, the process is entirely deterministic. Let $X^t$ be the indicator variable of the set of active nodes at time step $t-1$, then: \begin{equation} X^{t+1}_j = \mathbbm{1}_{\sum_{i=1}^m \Theta_{i,j}X^t_i > t_j} = \mathbbm{1}_{\inprod{\theta_j}{X^t} > t_j} @@ -16,4 +14,4 @@ where we defined again $\theta_j\defeq (\Theta_{1,j},\ldots,\Theta_{m,j})$. In o X^{t+1}_j = \text{sign} \left(\inprod{\theta_j}{X^t} - t_j \right) \end{equation} -The linear threshold model can therefore be cast as a variant of the recently introduced 1-bit compressed sensing model \cite{Boufounos:2008}. Several recent papers study the theoretical guarantees obtained for 1-bit compressed sensing with specific measurements \cite{Gupta:2010}, \cite{Plan:2014}. Whilst they obtained bounds of the order ${\cal O}(n \log \frac{n}{s}$), no current theory exists for recovering positive bounded signals from bernoulli hyperplanes. We leave this research direction to future work.
\ No newline at end of file +The link function of the linear threshold model is the sign function: $z \mapsto \mathbbm{1}_{z > 0}$. This model therefore falls into the 1-bit compressed sensing model \cite{Boufounos:2008} framework. Several recent papers study the theoretical guarantees obtained for 1-bit compressed sensing with specific measurements \cite{Gupta:2010}, \cite{Plan:2014}. Whilst they obtained bounds of the order ${\cal O}(n \log \frac{n}{s}$), no current theory exists for recovering positive bounded signals from bernoulli hyperplanes. We leave this research direction to future work.
\ No newline at end of file diff --git a/paper/sections/results.tex b/paper/sections/results.tex index 9c356c2..805f6b1 100644 --- a/paper/sections/results.tex +++ b/paper/sections/results.tex @@ -20,7 +20,7 @@ a set $\mathcal{T}$ of observations. We will write $n\defeq |\mathcal{T}|$. \label{sec:main_theorem} In this section, we analyze the case where $\theta^*$ is exactly sparse. We -write $S\defeq\text{supp}(\theta^*)$ and $s=|S|$. In our context, $S$ is the set of all nodes susceptible to influence our node $i$. In other words, if $\theta^*$ is exactly $s$-sparse, then node $i$ has at most $s$ parents. Our main theorem will rely on the now standard \emph{restricted eigenvalue condition}. +write $S\defeq\text{supp}(\theta^*)$ and $s=|S|$. Recall, that $\theta_i$ is the vector of weights for all edges \emph{directed at} the node we are solving for. In other words, $S$ is the set of all nodes susceptible to influence our node $i$, also referred to as its parents. Our main theorem will rely on the now standard \emph{restricted eigenvalue condition}. \begin{definition} Let $\Sigma\in\mathcal{S}_m(\reals)$ be a real symmetric matrix and $S$ be @@ -35,11 +35,8 @@ write $S\defeq\text{supp}(\theta^*)$ and $s=|S|$. In our context, $S$ is the set \end{equation} \end{definition} -A discussion of this assumption in the context of generalized linear cascade -models can be found in Section~\ref{sec:re}. - -We will also need the following assumption on the inverse link function $f$ of -the generalized linear cascade model: +This condition, well-known in the sparse recovery literature, captures the idea that the binary vectors of active nodes are not colinear with each other, an essentially necessary condition for recovering $\theta$. In fact, the $(S,\gamma)$-{\bf(RE)} assumption is closely linked to the \emph{Fisher Information Matrix}, which captures the amount of information carried by an observable random variable (here the set of active nodes) about an unknown parameter $\theta$ on which the random variable depends. +A discussion of the $(S,\gamma)$-{\bf(RE)} assumption in the context of generalized linear cascade models can be found in Section~\ref{sec:re}. We will also need the following assumption on the inverse link function $f$ of the generalized linear cascade model: \begin{equation} \tag{LF} \max\left(\left|\frac{f'}{f}(\inprod{\theta^*}{x})\right|, diff --git a/src/convex_optimization.py b/src/convex_optimization.py index 81bee2b..0d506e1 100644 --- a/src/convex_optimization.py +++ b/src/convex_optimization.py @@ -90,7 +90,7 @@ def diff_and_opt(M_val, w_val, f_x, f_xz): def F(x=None, z=None): if x is None: - return 0, cvxopt.matrix(-.01, (n,1)) + return 0, cvxopt.matrix(-.1, (n,1)) elif z is None: y, y_diff = f_x(x, M_val, w_val) return cvxopt.matrix(float(y), (1, 1)),\ diff --git a/src/make_plots.py b/src/make_plots.py index d719337..e9e0de3 100644 --- a/src/make_plots.py +++ b/src/make_plots.py @@ -168,8 +168,8 @@ if __name__=="__main__": #convex_optimization.type_lasso) if 1: compute_graph("../datasets/kronecker_graph_256_cross.txt", - n_cascades=100, lbda=.01, min_proba=.2, max_proba=.7, + n_cascades=2000, lbda=0., min_proba=.2, max_proba=.7, passed_function= - #convex_optimization.sparse_recovery, - convex_optimization.type_lasso, - sparse_edges=False)
\ No newline at end of file + convex_optimization.sparse_recovery, + #convex_optimization.type_lasso, + sparse_edges=True)
\ No newline at end of file |