diff options
Diffstat (limited to 'results.tex')
| -rw-r--r-- | results.tex | 28 |
1 files changed, 24 insertions, 4 deletions
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} |