diff options
| -rw-r--r-- | notes.tex | 79 |
1 files changed, 79 insertions, 0 deletions
@@ -3,6 +3,7 @@ \usepackage{amsmath,amsthm,amsfonts} \usepackage{comment} \newtheorem{lemma}{Lemma} +\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]} @@ -13,6 +14,84 @@ \newcommand{\trace}{\mathop{\mathrm{tr}}} \begin{document} + +\section{pomme} + +In this section, we will consider that we are given a \emph{universe} +set $U$ such that all the sets we consider are subsets or $U$ and all +functions defined on sets are defined on the power set of $U$, +$\mathfrak{P}(U)$. + +A 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. + +\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} + + + \section{Understanding the recommender system} \subsection{General problem} |