From 6ea40a753fada423daff3db2d69bc3e58bb99d51 Mon Sep 17 00:00:00 2001 From: jeanpouget-abadie Date: Mon, 28 Sep 2015 18:18:39 -0400 Subject: LT is submodular only in expectation --- notes/extensions.tex | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'notes') diff --git a/notes/extensions.tex b/notes/extensions.tex index 78cb336..cb78e35 100644 --- a/notes/extensions.tex +++ b/notes/extensions.tex @@ -41,8 +41,7 @@ $$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'. +infinity, it is harder to violate the inequality. (TH) note that the LT model is +NOT submodular for every fixed value of thresholds, but only in expectation over +the random draw of these thresholds. \end{document} -- cgit v1.2.3-70-g09d2