diff options
Diffstat (limited to 'notes/extensions.tex')
| -rw-r--r-- | notes/extensions.tex | 16 |
1 files changed, 16 insertions, 0 deletions
diff --git a/notes/extensions.tex b/notes/extensions.tex index ef73bf4..78cb336 100644 --- a/notes/extensions.tex +++ b/notes/extensions.tex @@ -29,4 +29,20 @@ Therefore, $\mathbb{E}[X_{n+1} | X_n] = A^T X_n$ and $\mathcal{G} = \sum_i A^i $\mathbb{E}[X_0X_0^T] = \frac{1}{m} I_m$ and it follows that $$\mathcal{G} = \frac{1}{m} \sum_{i=1}^T A^i (A^T)^i$$ +\section{Submodularity of Generalized Linear Cascades} + +For which link functions is the resulting influence function submodular? We know +it to be true for the IC and LT model, what about the Logistic cascade model? + +The answer is no. If we take the example of three nodes $(A, B, C)$ with the +possiblity to influence a remaining node D with respective edge weights: $a$, +$b$, and $c$, then we see that the following equality must be verified: +$$2\sigma(a+b) \geq \sigma(a+b+c) + \sigma(a)$$ + +We see that for $a=.5$, $,b=.5$, and $c=1$, the equality is violated. +Interestingly however is that if we let the scale parameter of the sigmoid go to +infinity, we recover the LT model which is submodular. In fact, by slowly +increasing the scale parameter, it becomes harder to find values of $a, b, c$ +which violate the inequality. We therefore have a parameterized function which +is `close to submodular'. \end{document} |