diff options
| -rw-r--r-- | notes2.tex | 149 |
1 files changed, 130 insertions, 19 deletions
@@ -5,6 +5,7 @@ \newtheorem{lemma}{Lemma} \newtheorem{fact}{Fact} \newtheorem{example}{Example} +\newtheorem{prop}{Proposition} \newcommand{\var}{\mathop{\mathrm{Var}}} \newcommand{\condexp}[2]{\mathop{\mathbb{E}}\left[#1|#2\right]} \newcommand{\expt}[1]{\mathop{\mathbb{E}}\left[#1\right]} @@ -18,34 +19,144 @@ \section{Problem} \begin{itemize} -\item $D = (x_i)_{1\leq i\leq n}$ -\item $(x_i)_{1\leq i\leq n}$ sampled in an i.i.d fashion from $\mu$ +\item database $D = (X_i)_{1\leq i\leq n}$ +\item $(X_i)_{1\leq i\leq n}\in\big(\mathbf{R^d}\big)^n$ sampled in an i.i.d + fashion from the probability distribution $\mu$ \end{itemize} -There is a function $F$ and you are interested in estimating the value -$F(\mu)$. We assume that you have an estimation scheme $\tilde{F}$, -which given a set of data points $S$ returns an estimation -$\tilde{F}(S)$ which is optimal in some sense. Your also given a -revenue function $R$ which is a decreasing function of the estimation -error. Then the value $V$ of the databse is defined by: +We assume that there is a common variable $P$ which is the underlying +phenomenon that we are interesting in, and all the variables in the database, +are noisy realisations of this phenomenon: \begin{displaymath} - V(D) = \max_{S\subseteq D} R\left(| F(\mu) - \tilde{F} |\right) + X_i = P + N_i \end{displaymath} +where the $N_i$ are pairwise independent and also independent from $H$. -\begin{example} - -\end{example} -\begin{fact} +We are interested in defining the $\emph{value}$ of a subset $S$ of the +database $D$. The approaches to such a definition can be classified in two main +families: +\begin{itemize} + \item \emph{Information theoretic:} We use the entropy of $P$ as a measure + of the uncertainty. Then the value of a subset $S$ is the decrease of + entropy induced by revealing it: + \begin{displaymath} + V(S) = H(P) - H(P\,|\,S) + \end{displaymath} + \item \emph{Statistical:} in this case you are trying to estimate the + phenomenon. The variance of the estimation is used as a measure of + the uncertainty. The value of a set $S$ can be defined as the average + reduction of the variance over all the points in the database once you + observe $S$: + \begin{displaymath} + V(S) = \frac{1}{|D|}\sum_{x\in D} \sigma_x^2 - \sigma_{x|A}^2 + \end{displaymath} +\end{itemize} + +Once you have defined a notion of value, there are several problems you can +address: +\begin{enumerate} + \item \emph{budget auctions:} the points in the database are associated + with users. Each user $i$ has a cost $c_i$ for revealing his data. You + are given a budget $B$ and you want to select a subset $S$ of users and + a payment scheme which is truthful. The value of the subset + $S$ should be as big as possible with the constraint that the payments + should stay within budget. + \item \emph{value sharing:} the goal is to find a value sharing method to + split the whole value of a subset $S$ among its participants. + \item \emph{k-best auctions:} this one is very similar to \emph{budget + auctions}, but instead of having a budget constraint, the constraint is + on the number of people in the subset $S$. +\end{enumerate} + +These problems have already been studied, and optimal or near-optimal solution +are already known when the value function is submodular. Fortunately, it can be +shown that the information theoretic value defined above is submodular. + +\section{Submodularity} + +In this section, we will consider that we are given a \emph{universe} set $U$. +A set function $f$ is a function defined on the power set of $U$, $\mathfrak{P}(U)$. + +A set function $f$ defined on $\mathfrak{P}(U)$ will be said \emph{increasing} if +it is increasing with regards to inclusion, that is: + +\begin{displaymath} + \forall\,S\subseteq T,\quad f(S)\leq f(T) +\end{displaymath} + +A \emph{decreasing} function on $\mathfrak{P}(U)$ is defined similarly. + +A set function $f$ defined on $\mathfrak{P}(U)$ is said to be +\emph{submodular} if it verifies the diminishing returns property, that is, +the marginal increments when adding a point to a set, is a set decreasing +function. More formally, for any point $x$ in $U$, we can define the marginal +increment of $f$ regarding $x$, it is the set function defined as: +\begin{displaymath} + \Delta_x f(S) = f(S\cup\{x\}) - f(S) +\end{displaymath} +Then, $f$ is \emph{submodular} iff. for all $x$ in $U$, $\Delta_x f$ is a set +decreasing function. - \begin{itemize} - \item If $R$ is decreasing then $V$ is increasing in the size of $D$. - \item If $R$ is concave then $V$ is supermodular. - \end{itemize} -\end{fact} +Similarly, a \emph{supermodular} is a function whose marginal increments are set +increasing functions. +\begin{prop} + Let $R:\mathbf{R}\rightarrow \mathbf{R}$ be a decreasing concave function and + $f:\mathfrak{P}(U)\rightarrow\mathbf{R}$ be a decreasing submodular function, + then the composed function $R\circ f$ is increasing and supermodular. +\end{prop} \begin{proof} + The increasingness of $R\circ f$ follows immediately from the decreasingness + of $R$ and $f$. + + For the supermodularity, let $S$ and $T$ be two sets such that $S\subseteq + T$. By decreasingness of $f$, we have: + \begin{displaymath} + \forall\,V,\quad f(T)\leq f(S)\quad\mathrm{and}\quad f(T\cup V)\leq f(S\cup V) + \end{displaymath} + + Thus, by concavity of $R$: + \begin{displaymath}\label{eq:base} + \forall\,V,\quad\frac{R\big(f(S)\big)-R\big(f(S\cup V)\big)}{f(S)-f(S\cup V)} + \leq\frac{R\big(f(T)\big)-R\big(f(T\cup V)\big)}{f(T)-f(T\cup V)} + \end{displaymath} + $f$ is decreasing, so multiplying this last inequality by + $f(S)-f(S\cup V)$ and $f(T)-f(T\cup V)$ yields: + \begin{multline} + \forall V,\quad\Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(T)-f(T\cup V)\big)\\ + \leq \Big(R\big(f(T)\big)-R\big(f(T\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big) + \end{multline} + + $f$ is submodular, so: + \begin{displaymath} + f(T\cup V)-f(T)\leq f(S\cup V) - f(S) + \end{displaymath} + + $R\circ f$ is increasing, so: + \begin{displaymath} + R\big(f(S)\big)-R\big(f(S\cup V)\big)\leq 0 + \end{displaymath} + + By combining the two previous inequalities, we get: + \begin{multline*} + \forall V,\quad\Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big)\\ + \leq \Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(T)-f(T\cup V)\big) + \end{multline*} + + Injecting this last inequality into \eqref{eq:base} gives: + \begin{multline*} + \forall V,\quad\Big(R\big(f(S)\big)-R\big(f(S\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big)\\ + \leq \Big(R\big(f(T)\big)-R\big(f(T\cup V)\big)\Big)\big(f(S)-f(S\cup V)\big) + \end{multline*} + + Dividing left and right by $f(S)-f(S\cup V)$ yields: + \begin{displaymath} + \forall V,\quad R\big(f(S)\big)-R\big(f(S\cup V)\big) + \leq R\big(f(T)\big)-R\big(f(T\cup V)\big) + \end{displaymath} + which is exactly the supermodularity of $R\circ f$. \end{proof} -\end{document}
\ No newline at end of file +\end{document} |