From da6f5798c63748bf5179acbf8b88252e7c64055d Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Thu, 2 Apr 2015 14:31:59 -0400
Subject: More applications

---
 results.tex | 28 ++++++++++++++++++++++++----
 1 file changed, 24 insertions(+), 4 deletions(-)

(limited to 'results.tex')

diff --git a/results.tex b/results.tex
index ce5368d..8735aa3 100644
--- a/results.tex
+++ b/results.tex
@@ -195,7 +195,7 @@ sets are the sets of size at most one).
         \end{displaymath}
         where $c_e(S)$ is one iff $e\in E(S,\bar{S})$. \textbf{TODO:} I think
         this can be written as a matroid rank function.
-    \item \emph{Learning/value of information}: (cite Krause) there is
+    \item \emph{Learning} (cite Krause) there is
         a hypothesis $A$ (a random variable) which is “refined” when more
         observations are made.  Imagine that there is a finite set $X_1,\dots,
         X_n$ of possible observations (random variables). Then, assuming that
@@ -206,9 +206,14 @@ sets are the sets of size at most one).
         \end{displaymath}
         is submodular. The $\log\det$ is the specific case of a linear
         hypothesis observed with additional independent Gaussian noise.
-        This can be written as multivariate concave over modular
-        (\textbf{TODO:} I think multivariate concave over modular is not
-        submodular in general, it is for $\log\det$. Understand this better).
+    \item \emph{Entropy:} Closely related to the previous one. If $(X_1,\dots,
+        X_n)$ are random variables, then:
+        $ f(S) = H(X_S) $ is submodular. In particular, if $(X_1,\dots,
+        X_n)$ are jointly multivariate gaussian, then:
+        \begin{displaymath}
+            f(S) = c|S| + \frac{1}{2}\log\det X_SX_S^T
+        \end{displaymath}
+        for $c= 2\pi e...$ and we fall back to the usual $\log\det$ function.
     \item \emph{data subset selection/summarization:} in statistical machine
         translation, Bilmes used sum of concave over modular:
         \begin{displaymath}
@@ -218,7 +223,22 @@ sets are the sets of size at most one).
         $f$ element $e$ has, and $\phi$ captures decreasing marginal gain when
         we have a lot of a given feature.
         Facility location functions are also commonly used for subset selection.
+    \item \emph{concave spectral functions} One would be tempted to say that
+        any multivariate concave function of a modular function is submodular.
+        This would be the natural generalization of concave over modular.
+        However \textbf{this is not true in general}. However, a possible nice
+        generalization is the following. Let $M$ be a symmetric $n\times
+        n$ matrix, and $g$ is a ``matrix concave'' function. Then:
+        \begin{displaymath}
+            f(S) = \mathrm{Tr}\big(g(M_S)\big)
+        \end{displaymath}
+        is submodular. This contains the $\log\det$ (when $g$ is the matrix
+        $\log$) but tons of other functions (like quantum entropy).
 \end{itemize}
+In summary, the two most general classes of submodular functions (which capture
+all the examples known to man) are: sums of matrix concave functions and sums
+of matroid rank functions. Sums of concave over modular are also nice if we
+want to start with a simpler example.
 
 \section{Passive Optimization}
 
-- 
cgit v1.2.3-70-g09d2

