From e80124c06ad4b9af98f64e110551aab584c12010 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sat, 2 Mar 2013 22:25:34 -0800 Subject: UCB talk --- slides/BudgetFeasibleExperimentalDesign.tex | 587 ++++++++++++++++++++++++++++ 1 file changed, 587 insertions(+) create mode 100644 slides/BudgetFeasibleExperimentalDesign.tex (limited to 'slides/BudgetFeasibleExperimentalDesign.tex') diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex new file mode 100644 index 0000000..04e2f8e --- /dev/null +++ b/slides/BudgetFeasibleExperimentalDesign.tex @@ -0,0 +1,587 @@ +\documentclass{beamer} +\usepackage[utf8x]{inputenc} +\usepackage[greek,english]{babel} +\usepackage[LGR,T1]{fontenc} +\usepackage{amsmath,bbm,verbatim} +\usepackage{algpseudocode,algorithm} +\usepackage{graphicx} +\DeclareMathOperator*{\argmax}{arg\,max} +\DeclareMathOperator*{\argmin}{arg\,min} +\usetheme{Boadilla} +\newcommand{\E}{{\tt E}} + +\title[EconCS Seminar]{Budget Feasible Mechanisms for Experimental Design} +\author[Horel, Ioannidis, Muthu]{Thibaut Horel$^*$, \alert{Stratis Ioannidis}$^\dagger$, and S. Muthukrishnan$^\ddagger$} +\institute[]{$^*$INRIA-ENS, $^\dagger$Technicolor, $^\ddagger$Rutgers University} +\setbeamercovered{transparent} +\setbeamertemplate{navigation symbols}{} +%\AtBeginSection[] +%{ +%\begin{frame} +%\frametitle{Outline} +%\tableofcontents[currentsection] +%\end{frame} +%} + + +\newcommand{\ie}{\emph{i.e.}} +\newcommand{\eg}{\emph{e.g.}} +\newcommand{\etc}{\emph{etc.}} +\newcommand{\reals}{\ensuremath{\mathbb{R}}} + +\usefonttheme[onlymath]{serif} +\begin{document} + +\begin{frame} +\maketitle +\end{frame} + +\section{Introduction} + + +\begin{frame}{Motivation:A Data Market} + \begin{center} + \includegraphics<1>[scale=0.4]{st1a.pdf} + \includegraphics<2>[scale=0.4]{st1b.pdf} + \includegraphics<3>[scale=0.4]{st1c.pdf} + \includegraphics<4>[scale=0.4]{st1d.pdf} + \includegraphics<5>[scale=0.4]{st1dd.pdf} + \includegraphics<6>[scale=0.4]{st1e.pdf} + \includegraphics<7>[scale=0.4]{st1f.pdf} + \includegraphics<8>[scale=0.4]{st1g.pdf} + \end{center} + + % \begin{center} + % \begin{overprint} + % \onslide<1-8>\begin{center}\end{center} +% \end{overprint} + % \end{center} +\end{frame} + +\begin{frame}{Challenges} +% \begin{overprint} + \begin{itemize} + \item<1-> Value of data? + \visible<3-4>{\begin{itemize} + \item Experimental Design + \end{itemize}} +\vspace*{1cm} + \item<2-> Strategic users? + \visible<4>{\begin{itemize} + \item Budget Feasible Auctions [Singer 2010] + \end{itemize}} + \end{itemize} +% \end{overprint} +\end{frame} + +\begin{frame}{Contributions} + \pause + \begin{itemize} + \item Experimental design when users are strategic + \pause + \vspace*{1cm} + \item Linear Regression + \pause + \begin{itemize} + \item \emph{Deterministic}, truthful, budget feasible, 12.98-appriximate mechanism. + \pause + \item Singer 2010, Chen 2011:\\ \emph{Randomized}, universaly truthful, budget feasible, 7.91-approximate mechanism. + \end{itemize} + \pause + \vspace*{1cm} + \item Generalization to other machine learning tasks. + \end{itemize} +\end{frame} + + +\section{Setting} +\begin{frame}{Outline} +\tableofcontents +\end{frame} + +\begin{frame}{Outline} + \tableofcontents[currentsection] +\end{frame} + + +\begin{frame}{Experimental Design} + \begin{center} + \includegraphics<1>[scale=0.4]{st2.pdf} + \includegraphics<2>[scale=0.4]{st3.pdf} + \includegraphics<3>[scale=0.4]{st4.pdf} + \includegraphics<4>[scale=0.4]{st5.pdf} + \includegraphics<5>[scale=0.4]{st6.pdf} + \includegraphics<6>[scale=0.4]{st7.pdf} + \includegraphics<7>[scale=0.4]{st8.pdf} + \includegraphics<8>[scale=0.4]{st9.pdf} + \end{center} + + \begin{center} + \begin{overprint} + \onslide<1>\begin{center}$N$ users (``experiment subjects'') \end{center} + \onslide<2> + \begin{center} + $x_i\in \reals^d$: public features (\eg, age, gender, height, \etc) + \end{center} + \onslide<3> + \begin{center} + $y_i\in \reals$: private data (\eg, survey answer, medical test outcome, etc.) + \end{center} + \onslide<4> + %\begin{} + \textbf{Gaussian Linear Model.} There exists $\beta\in \reals^d$ s.t. + \begin{displaymath} + y_i = \beta^T x_i + \varepsilon_i,\quad + \varepsilon_i\sim\mathcal{N}(0,\sigma^2), \quad i=1,\ldots,N + \end{displaymath} +%$$y_i = \beta^Tx_i + \varepsilon_i, i=1,\ldots, N$$ + %\end{center} + \onslide<5-7> + \begin{center} + Experimenter {\tt E} wishes to learn $\beta$ and can perform at most $k$ experiments. + \end{center} + \onslide<8> + \begin{center}{\tt E} computes estimate $\hat{\beta}$ of $\beta$ through ridge regression. + \end{center} + \end{overprint} + \end{center} + +\end{frame} + +\begin{frame}{Linear (Ridge) Regression} +%There exists $\beta\in \reals^d$ s.t. +% \begin{displaymath} +% y_i = \beta^T x_i + \varepsilon_i,\quad +% \varepsilon_i\sim\mathcal{N}(0,\sigma^2), \quad i=1,\ldots,N +% \end{displaymath} +\visible<1->{Let $S\subset [N]\equiv \{1,\ldots,N\}$ be the set of experiments performed.\\\medskip} +\visible<2->{Assume that \E\ has a \emph{prior} on $\beta$: +$$\beta \sim \mathcal{N}(0,\sigma^2 R). $$} +\visible<3->{Maximum a-posteriori estimation: +\begin{align*} + \hat{\beta} &= \argmax_{\beta\in\reals^d} \mathbf{P}(\beta\mid y_i, i\in S) \\ +&=\argmin_{\beta\in\reals^d} \big(\sum_{i\in S} (y_i - {\beta}^Tx_i)^2 + + \only<3-4>{\alert<4->{{\beta}^TR^{-1}\beta}\big)} \only<5>{\alert{\|\beta\|_2^2}\big)~~~~~} +%= (R+{X_S}^TX_S)^{-1}X_S^Ty_S +\end{align*} +} +\visible<4->{\hspace*{3in}\alert{Ridge Regression}\\} +\visible<5>{\hspace*{3in}$R=I$: homotropic prior} +\end{frame} + +\begin{frame}{Value Function} +Select $S\subset [N]$, s.t. $|S|\leq k$. +\\\bigskip +\visible<2->{ +Information Gain/D-optimality Criterion: +\begin{align*} +V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\ +\visible<3->{& = \frac{1}{2}\log\det (R^{-1}+X_S^TX_S)} +\end{align*} +\visible<3->{where $$X_S=[x_i^T]_{i\in S}\in \reals^{|S|\times d}$$} +} +\end{frame} + +%\begin{frame}{Classic Experimental Design} +%\begin{center} +%\includegraphics[scale=0.3]{st10.pdf} +%\end{center} +%\begin{align*} +%\text{Maximize}& & V(S) &= \log \det (R^{-1}+X^T_SX_S) \\ +%\text{subj. to}& & |S|&\leq k +%\end{align*} +%\end{frame} + + +\begin{frame}{Cardinality vs. Budget Constraint} +\begin{center} +\includegraphics<1>[scale=0.3]{st10a.pdf} +\includegraphics<2>[scale=0.3]{st10b.pdf} +\includegraphics<3>[scale=0.3]{st10c.pdf} +\includegraphics<4>[scale=0.3]{st10d.pdf} +\includegraphics<5->[scale=0.3]{st10f.pdf} +\end{center} + + \begin{center} + \begin{overprint} +\onslide<1>\begin{align*} +\text{Maximize}& & V(S) &= \log \det (R^{-1}+X^T_SX_S) \\ +\text{subj. to}& & |S|&\leq k +\end{align*} + + \onslide<2>\begin{center} + Each subject $i\in [N]$ has a cost $c_i\in \reals_+$ + \end{center} + \onslide<3> + \begin{center} + \E\ has a budget $B$. + \end{center} + \onslide<4-5> + \begin{center} + \E\ can pay subjects\visible<5>{; $y_i$ is revealed only if $i$ is paid.} + \end{center} + \onslide<6-> +\begin{block}{\textsc{Experimental Design Problem (EDP)} } +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &V(S) = \log \det (\alert<7>{I}+X^T_SX_S) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B + \end{align*} +\end{block} + \visible<7>{\alert{$R=I$: homotropic prior}} + + \end{overprint} + \end{center} +\end{frame} + +\begin{frame}{Full-Information Setting} +\begin{block}{\textsc{Experimental Design Problem (EDP)} } +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &V(S) = \log \det ({I}+X^T_SX_S) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B + \end{align*} +\end{block} +\begin{itemize} +\item<2-> EDP is NP-hard +\item<3-> $V$ is submodular, monotone, non-negative, and $V(\emptyset)=0$ +\item<4-> $\frac{1}{1-1/e}$-approximable (Sviridenko 2004, Krause and Guestrin 2005) +\end{itemize} +\end{frame} + +\begin{frame}{Strategic Subjects} +%\begin{center} +%\includegraphics<1->[scale=0.3]{st10c.pdf} +%\end{center} +%\begin{overprint} +\begin{itemize} +\visible<2->{\item +Subjects are \alert{strategic} and may lie about costs $c_i$.}\\\bigskip +\visible<3>{\item +Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} +\end{itemize} +\end{frame} + +\begin{frame}{Budget Feasible Mechanism Design [Singer 2010]} +\begin{center} +\includegraphics<1>[scale=0.3]{st11a.pdf} +\includegraphics<2>[scale=0.3]{st11b.pdf} +\includegraphics<3>[scale=0.3]{st11c.pdf} +\includegraphics<4>[scale=0.3]{st11d.pdf} +\end{center} +\begin{itemize} +%\item<1->Fix budget $B$ and value function $V:2^{[N]}\to\reals_+$ +\item<2->Let $c=[c_i]_{i\in [N]}$ be the subject costs. +\item<3-> A mechanism $\mathcal{M}(c)=(S(c),p(c))$ comprises +\begin{itemize} +\item<3-> an \alert{allocation function} $S:\reals_+^N\to 2^{[N]}$, and +\item<4> a \alert{payment function} $p:\reals_+^N\to \reals_+^N$. +\end{itemize} +\end{itemize} +\end{frame} +%\section{Budget feasible mechanism design} + +%\begin{frame}{Budget Feasible Mechanism Design [Singer 2010]} +%\begin{itemize} +% \item set of $N$ sellers: $\mathcal{A} = \{1,\ldots,N\}$; a buyer +% \vspace{0.3cm} +% \pause +% \item $V$ value function of the buyer, $V:2^\mathcal{A}\rightarrow \mathbb{R}^+$ +% \vspace{0.3cm} +% \pause +% \item $c_i\in\mathbb{R}^+$ price of seller's $i$ good +% \vspace{0.3cm} +% \pause +% \item $B$ budget constraint of the buyer +%\end{itemize} +% +%\vspace{0.5cm} +%\pause +% +%\begin{block}{Goal} +% \begin{itemize} +% \item Find $S\subset \mathcal{A}$ \alert{maximizing} $V(S)$ +% \vspace{0.3cm} +% \item Find \alert{payment} $p_i$ to seller $i\in S$ +% \end{itemize} +%\end{block} +%\end{frame} + +\begin{frame}{Objectives} + Mechanism $\mathcal{M}=(S,p)$ must be: + \pause + \vspace{0.3cm} + \begin{itemize} + \item Normalized: $p_i=0$ if $i\notin S$. + \vspace{0.2cm} + \pause + \item Individually Rational: $p_i\geq c_i,\;i\in S$ + \vspace{0.2cm} + \pause + \item Truthful: $p_i(c_i,c_{-i})-\mathbbm{1}_{i\in S(c_i,c_{-i})}\cdot c_i \geq p_i(c_i',c_{-i})-\mathbbm{1}_{i\in S(c_i',c_{-i})}\cdot c_i $ + \vspace{0.2cm} + \pause + \item budget feasible: $\sum_{i\in S} p_i \leq B$ + \vspace{0.2cm} + \end{itemize} + + \pause + \vspace{0.3cm} + + Mechanism must be: + \vspace{0.3cm} + \pause + \begin{itemize} + \item computationally efficient: polynomial time + \pause + \vspace{0.2cm} + \item constant approximation: $V(OPT) \leq \alpha V(S)$ with: + \begin{displaymath} + OPT = \arg\max_{S\subset \mathcal{A}} \left\{V(S)\mid \sum_{i\in S}c_i\leq B\right\} + \end{displaymath} + \end{itemize} +\end{frame} + + +\begin{frame}{Known Results} + When $V$ is submodular: + \vspace{1cm} + \pause + \begin{itemize} + \item \alert{randomized}, universally truthful, budget feasible mechanism, + approximation ratio: $7.91$ [Singer 2010, Chen \emph{et al.}, 2011] + \vspace{1cm} + \pause + \item \alert{deterministic} mechanisms for specific submodular $V$ functions: + \vspace{0.3cm} + \begin{itemize} + \item Knapsack: $2+\sqrt{2}$ [Singer 2010, Chen \emph{et al.}, 2011] + \vspace{0.3cm} + \item Matching: 7.37 [Singer, 2010] + \vspace{0.3cm} + \item Coverage: 31 [Singer, 2012] + \vspace{0.3cm} + \end{itemize} + \end{itemize} +\end{frame} + + +\begin{comment} +\begin{frame}{Outline} + \tableofcontents[currentsection] +\end{frame} + +\begin{frame}{Linear Regression} + \begin{center} + \includegraphics<1-4>[scale=0.5]{5.pdf} + \includegraphics<5>[scale=0.5]{6.pdf} + \includegraphics<6>[scale=0.5]{7.pdf} + \includegraphics<7>[scale=0.5]{8.pdf} + \end{center} + + \begin{center} + \begin{overprint} + \onslide<1>\begin{center}$N$ users\end{center} + \onslide<2> + \begin{center} + $x_i$: public features (e.g. age, gender, height, etc.) + \end{center} + \onslide<3> + \begin{center} + $y_i$: private data (e.g. disease, etc.) + \end{center} + \onslide<4> + \begin{center} + Gaussian Linear model: $y_i = \beta^Tx_i + \varepsilon_i$ + \end{center} + \begin{displaymath} + \beta^* = \arg\min_\beta \sum_i |y_i-\beta^Tx_i|^2 + \end{displaymath} + \end{overprint} + \end{center} +\end{frame} + +\begin{frame}{Experimental design} + \begin{itemize} + \item Public vector of features $x_i\in\mathbb{R}^d$ + \item Private data $y_i\in\mathbb{R}$ + \end{itemize} + + \vspace{0.5cm} + + Gaussian linear model: + \begin{displaymath} + y_i = \beta^T x_i + \varepsilon_i,\quad\beta\in\mathbb{R}^d,\; + \varepsilon_i\sim\mathcal{N}(0,\sigma^2) + \end{displaymath} + + \pause + \vspace{0.5cm} + + Which users to select?\pause{} Experimental design $\Rightarrow$ D-optimal criterion + + \vspace{0.5cm} + + \begin{block}{Experimental Design} + \begin{displaymath} + \textsf{\alert{maximize}}\quad V(S) = \log\det\left(I_d + \sum_{i\in S} x_i x_i^T\right)\quad \textsf{\alert{subject to}}\quad |S|\leq k + \end{displaymath} + \end{block} +\end{frame} + +\begin{frame}{Budgeted Experimental design} + \begin{displaymath} + \textsf{\alert{maximize}}\quad V(S) = \log\det\left(I_d + \sum_{i\in S} x_i x_i^T\right)\quad \textsf{\alert{subject to}}\quad \sum_{i\in S}c_i\leq B + \end{displaymath} + + \vspace{1cm} + + \begin{itemize} + \item the non-strategic optimization problem is NP-hard + \vspace{0.3cm} + \pause + \item $V$ is submodular + \vspace{0.3cm} + \pause + \item previous results give a randomized budget feasible mechanism + \vspace{0.3cm} + \pause + \item deterministic mechanism? + \end{itemize} +\end{frame} + +\begin{frame}{Main result} +\end{comment} + +\section{Main Result} + + +\begin{frame}{Outline} + \tableofcontents[currentsection] +\end{frame} + + +\begin{frame}{Our Main Result} + \begin{theorem} + There exists deterministic, budget feasible, individually rational and truthful mechanism for + EDP which runs in polynomial time. Its + approximation ratio is: + \begin{displaymath} + \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)}+\varepsilon + \simeq 12.98 +\varepsilon + \end{displaymath} + \end{theorem} +\end{frame} + +\begin{frame}{Sketch of proof} + \begin{block}{Mechanism (Chen et. al, 2011) for submodular $V$} + \begin{itemize} + \item Find $i^* = \arg\max_i V(\{i\})$ + \item Compute $S_G$ greedily + \item Return: + \begin{itemize} + \item $\{i^*\}$ if $V(\{i^*\}) \geq \only<1-2>{V(OPT_{-i^*})}\only<3>{\alert{V(OPT_{-i^*})}}\only<4->{\alert{L^*}}$ + \item $S_G$ otherwise + \end{itemize} + \end{itemize} + \end{block} + + \vspace{0.5cm} + \pause + + Valid mechanism, approximation ratio: 8.34 + + \vspace{0.5cm} + \pause + + \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute + + \vspace{0.5cm} + \pause + + \begin{columns}[c] + \begin{column}{0.53\textwidth} + \alert{Solution:} Replace $V(OPT_{-i^*})$ with \alert<7>{$L^*$}: + \pause + \begin{itemize} + \item computable in polynomial time + \pause + \item close to $V(OPT_{-i^*})$ + \end{itemize} + \end{column} + \pause + \begin{column}{0.45\textwidth} + \begin{itemize} + \item Knapsack (Chen et al., 2011) + \item Coverage (Singer, 2012) + \end{itemize} + \end{column} + \end{columns} +\end{frame} + +\begin{frame}{Sketch of proof (2)} + \begin{displaymath} + L^* = \arg\max_{\lambda\in [0,1]^n} \left\{\log\det\left(I_d + \sum_i \lambda_i x_i x_i^T\right)\mid \sum_{i=1}^n\lambda_i c_i\leq B\right\} + \end{displaymath} + \vspace{1cm} + \begin{itemize} + \item polynomial time?\pause{} convex optimization problem + \pause + \vspace{0.5cm} + \item close to $V(OPT_{-i^*})$?\pause + \vspace{0.5cm} + \begin{block}{Technical lemma} + \begin{displaymath} + L^* \leq 2 V(OPT) + V(\{i^*\}) + \end{displaymath} + \end{block} + \end{itemize} +\end{frame} + +\section{Generalization} + +\begin{frame}{Outline} + \tableofcontents[currentsection] +\end{frame} + +\begin{frame}{Generalization} + \begin{itemize} + \item Generative model: $y_i = f(x_i) + \varepsilon_i,\;i\in\mathcal{A}$ + \pause + \item prior knowledge of the experimenter: $f$ is a \alert{random variable} + \pause + \item \alert{uncertainty} of the experimenter: entropy $H(f)$ + \pause + \item after observing $\{y_i,\; i\in S\}$, uncertainty: $H(f\mid S)$ + \end{itemize} + + \pause + \vspace{0.5cm} + + \begin{block}{Value function: Information gain} + \begin{displaymath} + V(S) = H(f) - H(f\mid S),\quad S\subset\mathcal{A} + \end{displaymath} + \end{block} + + \pause + \vspace{0.5cm} + + $V$ is \alert{submodular} $\Rightarrow$ randomized budget feasible mechanism +\end{frame} + + +\begin{frame}{Conclusion} + \begin{itemize} + \item Experimental design + Auction theory = powerful framework + \vspace{1cm} + \pause + \item deterministic mechanism for the general case? other learning tasks? + \vspace{1cm} + \pause + \item approximation ratio $\simeq \alert{13}$. Lower bound: \alert{$2$} + \end{itemize} +\end{frame} +\end{document} + + -- cgit v1.2.3-70-g09d2 From b6a88dc29d0a5a0598c68666408c6197fbc6fe0e Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sun, 3 Mar 2013 20:15:00 -0800 Subject: almost extensions --- slides/BudgetFeasibleExperimentalDesign.tex | 389 +- slides/st10f.svg | 528 +- slides/st5.pdf | Bin 97997 -> 98032 bytes slides/st5.svg | 6 +- slides/st6.pdf | Bin 116105 -> 116209 bytes slides/st6.svg | 28 +- slides/st6a.pdf | Bin 0 -> 123407 bytes slides/st6a.svg | 7090 +++++++++++++++++++++++++ slides/st6b.pdf | Bin 0 -> 130541 bytes slides/st6b.svg | 7169 ++++++++++++++++++++++++++ slides/st6c.pdf | Bin 0 -> 131637 bytes slides/st6c.svg | 7231 ++++++++++++++++++++++++++ slides/st6d.pdf | Bin 0 -> 133769 bytes slides/st6d.svg | 7293 ++++++++++++++++++++++++++ slides/st6e.pdf | Bin 0 -> 135396 bytes slides/st6e.svg | 7351 ++++++++++++++++++++++++++ slides/st6f.pdf | Bin 0 -> 146469 bytes slides/st6f.svg | 7387 +++++++++++++++++++++++++++ 18 files changed, 44104 insertions(+), 368 deletions(-) create mode 100644 slides/st6a.pdf create mode 100644 slides/st6a.svg create mode 100644 slides/st6b.pdf create mode 100644 slides/st6b.svg create mode 100644 slides/st6c.pdf create mode 100644 slides/st6c.svg create mode 100644 slides/st6d.pdf create mode 100644 slides/st6d.svg create mode 100644 slides/st6e.pdf create mode 100644 slides/st6e.svg create mode 100644 slides/st6f.pdf create mode 100644 slides/st6f.svg (limited to 'slides/BudgetFeasibleExperimentalDesign.tex') diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex index 04e2f8e..ca60e04 100644 --- a/slides/BudgetFeasibleExperimentalDesign.tex +++ b/slides/BudgetFeasibleExperimentalDesign.tex @@ -27,6 +27,7 @@ \newcommand{\ie}{\emph{i.e.}} \newcommand{\eg}{\emph{e.g.}} \newcommand{\etc}{\emph{etc.}} +\newcommand{\etal}{\emph{et al.}} \newcommand{\reals}{\ensuremath{\mathbb{R}}} \usefonttheme[onlymath]{serif} @@ -83,9 +84,14 @@ \item Linear Regression \pause \begin{itemize} - \item \emph{Deterministic}, truthful, budget feasible, 12.98-appriximate mechanism. + \item We present a \alert{deterministic, poly-time}, truthful, budget feasible, 12.98-appriximate mechanism. \pause - \item Singer 2010, Chen 2011:\\ \emph{Randomized}, universaly truthful, budget feasible, 7.91-approximate mechanism. + \vspace*{0.5cm} + \item Previous results: + \begin{itemize} + \item \alert{Randomized}, poly-time, universally truthful, 7.91-approximate mechanism. [Singer 2010, Chen 2011] + \item Deterministic, \alert{exponential time}, truthful mechanism. [Chen 2011] + \end{itemize} \end{itemize} \pause \vspace*{1cm} @@ -104,21 +110,23 @@ \end{frame} -\begin{frame}{Experimental Design} +\begin{frame}{Formulating the Problem} \begin{center} \includegraphics<1>[scale=0.4]{st2.pdf} \includegraphics<2>[scale=0.4]{st3.pdf} \includegraphics<3>[scale=0.4]{st4.pdf} \includegraphics<4>[scale=0.4]{st5.pdf} \includegraphics<5>[scale=0.4]{st6.pdf} - \includegraphics<6>[scale=0.4]{st7.pdf} - \includegraphics<7>[scale=0.4]{st8.pdf} - \includegraphics<8>[scale=0.4]{st9.pdf} + \includegraphics<6>[scale=0.4]{st6a.pdf} + \includegraphics<7>[scale=0.4]{st6b.pdf} + \includegraphics<8>[scale=0.4]{st6c.pdf} + \includegraphics<9>[scale=0.4]{st6d.pdf} + \includegraphics<10->[scale=0.4]{st6e.pdf} \end{center} \begin{center} \begin{overprint} - \onslide<1>\begin{center}$N$ users (``experiment subjects'') \end{center} + \onslide<1>\begin{center}$N$ users (``experiment subjects''), $[N]\equiv \{1,\ldots,N\}$ \end{center} \onslide<2> \begin{center} $x_i\in \reals^d$: public features (\eg, age, gender, height, \etc) @@ -132,54 +140,155 @@ \textbf{Gaussian Linear Model.} There exists $\beta\in \reals^d$ s.t. \begin{displaymath} y_i = \beta^T x_i + \varepsilon_i,\quad - \varepsilon_i\sim\mathcal{N}(0,\sigma^2), \quad i=1,\ldots,N + \varepsilon_i\sim\mathcal{N}(0,\sigma^2), \quad i\in [N] \end{displaymath} %$$y_i = \beta^Tx_i + \varepsilon_i, i=1,\ldots, N$$ %\end{center} - \onslide<5-7> + \onslide<5> \begin{center} - Experimenter {\tt E} wishes to learn $\beta$ and can perform at most $k$ experiments. + Experimenter {\tt E} wishes to learn $\beta$. \end{center} - \onslide<8> - \begin{center}{\tt E} computes estimate $\hat{\beta}$ of $\beta$ through ridge regression. + \onslide<6>\begin{center} + Each subject $i\in [N]$ has a cost $c_i\in \reals_+$ + \end{center} + \onslide<7> + \begin{center} + \E\ has a budget $B$. + \end{center} + \onslide<8-9> + \begin{center} + \E\ pays subjects\visible<9>{; $y_i$ is revealed only if $i$ is paid.} + \end{center} + \onslide<10> + \begin{center}{\tt E} estimates ${\beta}$ through \emph{ridge regression}. + \end{center} + \onslide<11> + \begin{center} +%\begin{enumerate} +Goal: Determine (a) who to pay and (b) how much,\\ so that $\hat{\beta}$ is as accurate as possible. +%\begin{align*} +% \text{Determine (a) who to pay:}\quad &S\subseteq [N], \text{ and}\\ +% \text{(b)~ how much:}\quad &p_i\in \reals_+,~~i\in S. +%\end{align*} +%\end{enumerate} + \end{center} + \onslide<12-> + \begin{center}Users are \alert{strategic}: the may lie about costs $c_i$\visible<13>{\\ Users \alert{cannot manipulate $x_i$ or $y_i$}.} %\\(tamper-proof experiments) \end{center} + \end{overprint} \end{center} \end{frame} -\begin{frame}{Linear (Ridge) Regression} -%There exists $\beta\in \reals^d$ s.t. -% \begin{displaymath} -% y_i = \beta^T x_i + \varepsilon_i,\quad -% \varepsilon_i\sim\mathcal{N}(0,\sigma^2), \quad i=1,\ldots,N -% \end{displaymath} -\visible<1->{Let $S\subset [N]\equiv \{1,\ldots,N\}$ be the set of experiments performed.\\\medskip} -\visible<2->{Assume that \E\ has a \emph{prior} on $\beta$: +\begin{frame}{Budget Feasible Mechanism Design [Singer 2010]} +Let $S\subset [N]$ be the set of experiments performed, and + $c=[c_i]_{i\in [N]}$ be the subject costs. \\\bigskip +\visible<2->{Let $V(S)\in\reals_+$ denote the \alert{value} of the experiments.} +\visible<3->{$$\text{High }V(S) \Leftrightarrow \text{ estimate }\hat{\beta}(S) \text{ is close to }\beta $$} +\visible<4->{ +%\item<1->Fix budget $B$ and value function $V:2^{[N]}\to\reals_+$ +\begin{block}{Reverse Auction Mechanism} + A mechanism $\mathcal{M}(c)=(S(c),p(c))$ comprises +\begin{itemize} +\item an \alert{allocation function} $S:\reals_+^N\to 2^{[N]}$, and +\item a \alert{payment function} $p:\reals_+^N\to \reals_+^N$. +\end{itemize} +\end{block} +} +\end{frame} + + +\begin{frame}{Budget Feasible Mechanism Design [Singer 2010] (cont'd)} + We seek mechanisms $\mathcal{M}=(S,p)$ that are: + \pause + \vspace{0.3cm} + \begin{itemize} + \item Normalized: $p_i=0$ if $i\notin S$. + \vspace{0.2cm} + \pause + \item Individually Rational: $p_i\geq c_i,\;i\in S$ + \vspace{0.2cm} + \pause + \item Truthful: $p_i(c_i,c_{-i})-\mathbbm{1}_{i\in S(c_i,c_{-i})}\cdot c_i \geq p_i(c_i',c_{-i})-\mathbbm{1}_{i\in S(c_i',c_{-i})}\cdot c_i $ + \vspace{0.2cm} + \pause + \item budget feasible: $\sum_{i\in S} p_i \leq B$ + \vspace{0.2cm} + \end{itemize} + + \pause + \vspace{0.3cm} + + In addition, $\mathcal{M}$ must be: + \vspace{0.3cm} + \pause + \begin{itemize} + \item computationally efficient: polynomial time + \pause + \vspace{0.2cm} + \item constant approximation: $V(OPT) \leq \alpha V(S)$ with: + \begin{displaymath} + OPT = \arg\max_{S\subset \mathcal{A}} \left\{V(S)\mid \sum_{i\in S}c_i\leq B\right\} + \end{displaymath} + \end{itemize} +\end{frame} + + + + +\begin{frame}{Which Experiments Are Informative?} + +\alt<1>{What is the appropriate value function $V$?} {Let $S\subset [N]$ be the set of experiments performed.\\\medskip} +%\end{overprint} +\visible<3->{Assume that \E\ has a \emph{prior} on $\beta$: $$\beta \sim \mathcal{N}(0,\sigma^2 R). $$} -\visible<3->{Maximum a-posteriori estimation: +\visible<4->{Maximum a-posteriori estimation: \begin{align*} \hat{\beta} &= \argmax_{\beta\in\reals^d} \mathbf{P}(\beta\mid y_i, i\in S) \\ &=\argmin_{\beta\in\reals^d} \big(\sum_{i\in S} (y_i - {\beta}^Tx_i)^2 - + \only<3-4>{\alert<4->{{\beta}^TR^{-1}\beta}\big)} \only<5>{\alert{\|\beta\|_2^2}\big)~~~~~} + + \only<4-5>{\alert<5->{{\beta}^TR^{-1}\beta}\big)} \only<6>{\alert{\|\beta\|_2^2}\big)~~~~~} %= (R+{X_S}^TX_S)^{-1}X_S^Ty_S \end{align*} } -\visible<4->{\hspace*{3in}\alert{Ridge Regression}\\} -\visible<5>{\hspace*{3in}$R=I$: homotropic prior} +\visible<5->{\hspace*{3in}\alert{Ridge Regression}\\} +\visible<6>{\hspace*{2.8in}\alert{$R=I$: homotropic prior}} \end{frame} -\begin{frame}{Value Function} -Select $S\subset [N]$, s.t. $|S|\leq k$. -\\\bigskip +\begin{frame}{Which Experiments Are Informative? (contd.)} +Let $S\subset [N]$ be the set of experiments performed.\\\bigskip + \visible<2->{ Information Gain/D-optimality Criterion: \begin{align*} V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\ -\visible<3->{& = \frac{1}{2}\log\det (R^{-1}+X_S^TX_S)} +\visible<3->{& = \frac{1}{2}\log\det (R^{-1}+\sum_{i\in S}x_ix_i^T)} \end{align*} -\visible<3->{where $$X_S=[x_i^T]_{i\in S}\in \reals^{|S|\times d}$$} + +\visible<4->{ \emph{I.e.}: $$\alert{\text{Value of~}S=\text{Reduction of Uncertainty.}} $$} +\vspace*{-0.7cm} } +\end{frame} + +\begin{frame}{Full Information Setting} +\onslide<2->{ +\begin{block}{\textsc{Experimental Design Problem (EDP)} } +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &V(S) = \log \det (\alert<3>{I}+\sum_{i\in S}x_ix_i^T) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B +\end{align*} +\end{block} +} +\begin{itemize} +\item<3->$R=I$: homotropic prior +\item<4-> EDP is NP-hard +\item<5-> $V$ is submodular, monotone, non-negative, and $V(\emptyset)=0$ +\item<6-> $\frac{1}{1-1/e}$-approximable (Sviridenko 2004, Krause and Guestrin 2005) +\end{itemize} + + + \end{frame} %\begin{frame}{Classic Experimental Design} @@ -192,7 +301,7 @@ V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\ %\end{align*} %\end{frame} - +\begin{comment} \begin{frame}{Cardinality vs. Budget Constraint} \begin{center} \includegraphics<1>[scale=0.3]{st10a.pdf} @@ -209,17 +318,6 @@ V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\ \text{subj. to}& & |S|&\leq k \end{align*} - \onslide<2>\begin{center} - Each subject $i\in [N]$ has a cost $c_i\in \reals_+$ - \end{center} - \onslide<3> - \begin{center} - \E\ has a budget $B$. - \end{center} - \onslide<4-5> - \begin{center} - \E\ can pay subjects\visible<5>{; $y_i$ is revealed only if $i$ is paid.} - \end{center} \onslide<6-> \begin{block}{\textsc{Experimental Design Problem (EDP)} } \vspace*{-0.4cm} @@ -306,53 +404,22 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} % \end{itemize} %\end{block} %\end{frame} +\end{comment} -\begin{frame}{Objectives} - Mechanism $\mathcal{M}=(S,p)$ must be: - \pause - \vspace{0.3cm} - \begin{itemize} - \item Normalized: $p_i=0$ if $i\notin S$. - \vspace{0.2cm} - \pause - \item Individually Rational: $p_i\geq c_i,\;i\in S$ - \vspace{0.2cm} - \pause - \item Truthful: $p_i(c_i,c_{-i})-\mathbbm{1}_{i\in S(c_i,c_{-i})}\cdot c_i \geq p_i(c_i',c_{-i})-\mathbbm{1}_{i\in S(c_i',c_{-i})}\cdot c_i $ - \vspace{0.2cm} - \pause - \item budget feasible: $\sum_{i\in S} p_i \leq B$ - \vspace{0.2cm} - \end{itemize} - - \pause - \vspace{0.3cm} - - Mechanism must be: - \vspace{0.3cm} - \pause - \begin{itemize} - \item computationally efficient: polynomial time - \pause - \vspace{0.2cm} - \item constant approximation: $V(OPT) \leq \alpha V(S)$ with: - \begin{displaymath} - OPT = \arg\max_{S\subset \mathcal{A}} \left\{V(S)\mid \sum_{i\in S}c_i\leq B\right\} - \end{displaymath} - \end{itemize} -\end{frame} - - -\begin{frame}{Known Results} +\begin{frame}{Strategic Subjects} When $V$ is submodular: \vspace{1cm} \pause \begin{itemize} - \item \alert{randomized}, universally truthful, budget feasible mechanism, + \item \alert{Randomized}, poly-time, universally truthful mechanism, approximation ratio: $7.91$ [Singer 2010, Chen \emph{et al.}, 2011] - \vspace{1cm} + \vspace{0.5cm} \pause - \item \alert{deterministic} mechanisms for specific submodular $V$ functions: + \item Deterministic, \alert{exponential time}, truthful mechanism, + approximation ratio: $8.34$ [Singer 2010, Chen \emph{et al.}, 2011] + \vspace{0.5cm} + \pause + \item \alert{Deterministic, poly-time}, truthful mechanisms for specific submodular functions $V$ : \vspace{0.3cm} \begin{itemize} \item Knapsack: $2+\sqrt{2}$ [Singer 2010, Chen \emph{et al.}, 2011] @@ -453,7 +520,7 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} \begin{frame}{Main result} \end{comment} -\section{Main Result} +\section{Main Results} \begin{frame}{Outline} @@ -461,41 +528,173 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} \end{frame} -\begin{frame}{Our Main Result} - \begin{theorem} +\begin{frame}{Main Results} + \begin{theorem}<2-> There exists deterministic, budget feasible, individually rational and truthful mechanism for EDP which runs in polynomial time. Its approximation ratio is: \begin{displaymath} - \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)}+\varepsilon - \simeq 12.98 +\varepsilon + \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} + \simeq 12.98 \end{displaymath} \end{theorem} + \begin{theorem}<3-> + There is no 2-approximate, budget feasible, individually rational and truthful mechanism for + EDP. \end{theorem} + +\end{frame} + +\begin{frame}{Myerson's Theorem} +\begin{theorem}[Myerson 1981] + A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is +truthful iff: +\begin{enumerate} +\item<2-> + $S$ is \alert{monotone}, \emph{i.e.},%\\ for any agent $i$ and $c_i' \leq c_i$, for any fixed costs $c_{-i}$ of agents in $[N]\setminus\{i\}$, + $$\text{for all}~c_i' \leq c_i,\quad i\in S(c_i, +c_{-i})\text{ implies }i\in S(c_i', c_{-i}),$$ and +\item<3-> + subjects are paid \alert{threshold payments}, \emph{i.e.}, $$\text{for all }i\in S(c), \qquad p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}.$$ +\end{enumerate} +\end{theorem} +\uncover<4->{Focus on \alert{monotone} mechanisms.} + +\end{frame} + +\begin{frame}{A Greedy Construction for Submodular $V$} +Construct $S_G$ by adding elements with \emph{highest marginal-value-per-cost}.\\ +\bigskip +\visible<2->{If $S_G=S$ so far, add to it: +\begin{align*} + i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy} +\end{align*} +Stop when budget $B$ is reached. +} + +\end{frame} + +\begin{frame}{A Randomized Mechanism for Submodular $V$ [Singer 2010]} + \begin{block}{Allocation $S$:} + \begin{itemize} + \item Let $i^* = \arg\max_i V(\{i\})$ + \item Compute $S_G$ greedily over $[N]\setminus i^*$ + \item Return $S$: + \begin{itemize} + \item Selected at random between $i^*$ and $S_G$ + \end{itemize} + \end{itemize} + \end{block} + \vspace{0.5cm} +\uncover<2->{ +[Singer 2010] Along with threshold payments, this mechanism is: +\begin{itemize} +\item poly-time, +\item universally truthful, +\item budget-feasible +\item 7.91-approximate [Chen \etal\ 2011]. +\end{itemize} +} \end{frame} -\begin{frame}{Sketch of proof} - \begin{block}{Mechanism (Chen et. al, 2011) for submodular $V$} +\begin{frame}{A Deterministic Mechanism for Submodular $V$ [Singer 2010]} + \begin{block}{Allocation $S$} \begin{itemize} \item Find $i^* = \arg\max_i V(\{i\})$ \item Compute $S_G$ greedily \item Return: \begin{itemize} - \item $\{i^*\}$ if $V(\{i^*\}) \geq \only<1-2>{V(OPT_{-i^*})}\only<3>{\alert{V(OPT_{-i^*})}}\only<4->{\alert{L^*}}$ + \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert<3>{V(OPT_{-i^*})}$ \item $S_G$ otherwise \end{itemize} \end{itemize} \end{block} - + \vspace{0.5cm} +\uncover<2->{ +[Singer 2010] Along with threshold payments, this mechanism is: +\begin{itemize} +\item truthful, +\item budget-feasible +\item 8.34-approximate [Chen \etal\ 2011]. +\end{itemize} \vspace{0.5cm} \pause + \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute +} +\end{frame} - Valid mechanism, approximation ratio: 8.34 +\begin{frame}{Blueprint for Deterministic, Poly-time Algorithm} +Azar and Gamzu 2008, Singer 2010, Chen \etal\ 2011: + \begin{block}{Allocation $S$} + \begin{itemize} + \item Find $i^* = \arg\max_i V(\{i\})$ + \item Compute $S_G$ greedily + \item Return: + \begin{itemize} + \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert{L^*}$ + \item $S_G$ otherwise + \end{itemize} + \end{itemize} + \end{block} \vspace{0.5cm} - \pause + \begin{columns}[c] + \begin{column}{0.53\textwidth} +Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause + \begin{itemize} + \item computable in polynomial time + \pause + \item close to $V(OPT_{-i^*})$ + \pause + \item monotone in costs $c$ + \end{itemize} + \end{column} + \pause + \begin{column}{0.45\textwidth} + \begin{itemize} + \item Knapsack (Chen \etal, 2011) + \item Coverage (Singer, 2012) + \end{itemize} + \end{column} + \end{columns} +\end{frame} - \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute +\begin{frame}{Main Technical Contribution: Relaxation for EDP} +\alt<1>{\begin{block}{\textsc{EDP} } +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &V(S) = \log \det (I+\sum_{i\in S}x_ix_i^T) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B +\end{align*} +\end{block} +} +{ +\begin{block}{Convex Relaxation} +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &L(\lambda) = \log \det (I+\sum_{i\in [N]}\lambda_ix_ix_i^T) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}\lambda_ic_i\leq B, \lambda_i\in [0,1] +\end{align*} +\end{block} +} +\pause +\pause + \begin{itemize} + \item Poly-time: $L$ is convex and self-concordant + \pause + \vspace{0.5cm} + \item Close to $V(OPT)$:\pause + \vspace{0.5cm} + \begin{block}{Technical Lemma} + \begin{displaymath} + L^* \leq 2 V(OPT) + V(\{i^*\}) + \end{displaymath} + \end{block} + \end{itemize} + \pause + Proved using \emph{pipage rounding} [Ageev and Sviridenko 2004] +\end{frame} +\begin{comment} \vspace{0.5cm} \pause @@ -518,7 +717,6 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} \end{column} \end{columns} \end{frame} - \begin{frame}{Sketch of proof (2)} \begin{displaymath} L^* = \arg\max_{\lambda\in [0,1]^n} \left\{\log\det\left(I_d + \sum_i \lambda_i x_i x_i^T\right)\mid \sum_{i=1}^n\lambda_i c_i\leq B\right\} @@ -537,8 +735,9 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} \end{block} \end{itemize} \end{frame} +\end{comment} -\section{Generalization} +\section{Extensions \& Generalization} \begin{frame}{Outline} \tableofcontents[currentsection] diff --git a/slides/st10f.svg b/slides/st10f.svg index 1ddfe0a..72fd0b0 100644 --- a/slides/st10f.svg +++ b/slides/st10f.svg @@ -16,7 +16,7 @@ width="688.68484" height="404.61727" xml:space="preserve" - sodipodi:docname="st10d.svg"> + + + + + + + + + + + + + + + + + + + + + - - - - - - - - - - - - - - - - - - -2$ + sodipodi:role="line">2$ 13$ -13$ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Experimenter + + + + + + + + + + + + +? + + + + + + + + + + + + + + + + + + + + + \ No newline at end of file diff --git a/slides/st6b.pdf b/slides/st6b.pdf new file mode 100644 index 0000000..d4cc19c Binary files /dev/null and b/slides/st6b.pdf differ diff --git a/slides/st6b.svg b/slides/st6b.svg new file mode 100644 index 0000000..d2f33a3 --- /dev/null +++ b/slides/st6b.svg @@ -0,0 +1,7169 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Experimenter + + + + + + + + + + + + + +? + + + + + + + + + + + + + + + + + + + + + + \ No newline at end of file diff --git a/slides/st6c.pdf b/slides/st6c.pdf new file mode 100644 index 0000000..6cdcc1c Binary files /dev/null and b/slides/st6c.pdf differ diff --git a/slides/st6c.svg b/slides/st6c.svg new file mode 100644 index 0000000..0208461 --- /dev/null +++ b/slides/st6c.svg @@ -0,0 +1,7231 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Experimenter + + + + + + + + + + + + + + + +? + + + + + + + + + + + + + + + + + + + + + + + +2$ + + + +13$ + + + + \ No newline at end of file diff --git a/slides/st6d.pdf b/slides/st6d.pdf new file mode 100644 index 0000000..b16466f Binary files /dev/null and b/slides/st6d.pdf differ diff --git a/slides/st6d.svg b/slides/st6d.svg new file mode 100644 index 0000000..67ed02f --- /dev/null +++ b/slides/st6d.svg @@ -0,0 +1,7293 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Experimenter + + + + + + + + + + + + + + +? + + + + + + + + + + + + + + + + + + + + + + +2$ + + +13$ + + + \ No newline at end of file diff --git a/slides/st6e.pdf b/slides/st6e.pdf new file mode 100644 index 0000000..a532f43 Binary files /dev/null and b/slides/st6e.pdf differ diff --git a/slides/st6e.svg b/slides/st6e.svg new file mode 100644 index 0000000..dc24c6e --- /dev/null +++ b/slides/st6e.svg @@ -0,0 +1,7351 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Experimenter + + + + + + + + + + + + + + + + +? + + + + + + + + + + + + + + + + + + + + + + + + +2$ + + + + +13$ + + + + +ridge regression + + + + \ No newline at end of file diff --git a/slides/st6f.pdf b/slides/st6f.pdf new file mode 100644 index 0000000..45b9414 Binary files /dev/null and b/slides/st6f.pdf differ diff --git a/slides/st6f.svg b/slides/st6f.svg new file mode 100644 index 0000000..f2245ca --- /dev/null +++ b/slides/st6f.svg @@ -0,0 +1,7387 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Experimenter + + + + + + + + + + + + + + + + + +? + + + + + + + + + + + + + + + + + + + + + + + + + +p2=2$ + + + + + +p3=13$ + + + + + +ridge regression + + + + +S = {2,3} + \ No newline at end of file -- cgit v1.2.3-70-g09d2 From 2c022bdaaba14864c82aeae51eba5821b75dc506 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Sun, 3 Mar 2013 21:32:23 -0800 Subject: done sun night --- slides/BudgetFeasibleExperimentalDesign.tex | 91 ++++++++++++++++++++++++++--- 1 file changed, 84 insertions(+), 7 deletions(-) (limited to 'slides/BudgetFeasibleExperimentalDesign.tex') diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex index ca60e04..98de9c2 100644 --- a/slides/BudgetFeasibleExperimentalDesign.tex +++ b/slides/BudgetFeasibleExperimentalDesign.tex @@ -126,7 +126,7 @@ \begin{center} \begin{overprint} - \onslide<1>\begin{center}$N$ users (``experiment subjects''), $[N]\equiv \{1,\ldots,N\}$ \end{center} + \onslide<1>\begin{center}$N$ ``experiment subjects'', $[N]\equiv \{1,\ldots,N\}$ \end{center} \onslide<2> \begin{center} $x_i\in \reals^d$: public features (\eg, age, gender, height, \etc) @@ -528,7 +528,7 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} \end{frame} -\begin{frame}{Main Results} +\begin{frame}{Our Main Results} \begin{theorem}<2-> There exists deterministic, budget feasible, individually rational and truthful mechanism for EDP which runs in polynomial time. Its @@ -737,13 +737,62 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause \end{frame} \end{comment} -\section{Extensions \& Generalization} +\section{Generalization} \begin{frame}{Outline} \tableofcontents[currentsection] \end{frame} -\begin{frame}{Generalization} +\begin{frame}{Towards More General ML Tasks} + \begin{center} + \includegraphics<1>[scale=0.4]{st2.pdf} + \includegraphics<2>[scale=0.4]{st3.pdf} + \includegraphics<3>[scale=0.4]{st4.pdf} + \includegraphics<4-5>[scale=0.4]{st25.pdf} + \includegraphics<6->[scale=0.4]{st26.pdf} + \end{center} + + \begin{overprint} + \onslide<1> + \begin{center}$N$ experiment subjects\end{center} + \onslide<2> + \begin{center} + $x_i\in \Omega$: public features + \end{center} + \onslide<3> + \begin{center} + $y_i\in \reals$: private data + \end{center} + \onslide<4-5> + \begin{center} + \textbf{Hypothesis.} There exists $h:\Omega\to \reals$ s.t. + % \begin{displaymath} + $y_i = h(x_i) + \varepsilon_i,$ %\quad + where $\varepsilon_i$ are independent. + \visible<5>{Examples: Logistic Regression, LDA, SVMs, \etc} + % \end{displaymath} + \end{center} +%$$y_i = \beta^Tx_i + \varepsilon_i, i=1,\ldots, N$$ + %\end{center} + \onslide<6> + \begin{center} + Experimenter {\tt E} wishes to learn $h$, and has a prior distribution over $$\mathcal{H}=\{\text{mappings from }\Omega\text{ to }\reals\}.$$ + \end{center} + \onslide<7->\begin{center} +\vspace*{-0.5cm} +% \begin{block} +%{Value function: Information gain} + \begin{displaymath} + V(S) = H(h) - H(h\mid y_i,i\in S),\quad S\subseteq[N] + \end{displaymath} + % \end{block} + \visible<8>{$V$ is submodular! [Krause and Guestrin 2009]} + \end{center} + \end{overprint} + +\end{frame} + +\begin{comment} \begin{itemize} \item Generative model: $y_i = f(x_i) + \varepsilon_i,\;i\in\mathcal{A}$ \pause @@ -769,18 +818,46 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause $V$ is \alert{submodular} $\Rightarrow$ randomized budget feasible mechanism \end{frame} +\end{comment} \begin{frame}{Conclusion} \begin{itemize} - \item Experimental design + Auction theory = powerful framework + \item Experimental design + Budget Feasible Mechanisms \vspace{1cm} \pause - \item deterministic mechanism for the general case? other learning tasks? + \item Deterministic mechanism for other ML Tasks? General submodular functions? \vspace{1cm} \pause - \item approximation ratio $\simeq \alert{13}$. Lower bound: \alert{$2$} + \item Approximation ratio $\simeq \alert{13}$. Lower bound: \alert{$2$} \end{itemize} \end{frame} +\begin{frame}{} +\vspace{\stretch{1}} +\begin{center} +Thank you! +\end{center} +\vspace{\stretch{1}} +\end{frame} + +\begin{frame}{Non-Homotropic Prior} +Recall that: +\begin{align*} +V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\ +& = \frac{1}{2}\log\det (R^{-1}+\sum_{i\in S}x_ix_i^T) +\end{align*} +What if $R\neq I$? +\begin{theorem} + There exists a truthful, poly-time, and budget feasible mechanism for the objective + function $V$ above. Furthermore, + the algorithm computes a set $S^*$ such that: + \begin{displaymath} + OPT \leq + \frac{5e-1}{e-1}\frac{2}{\mu\log(1+1/\mu)}V(S^*) + 5.1 +\end{displaymath} +where $\mu$ is the largest eigenvalue of $R$. +\end{theorem} +\end{frame} + \end{document} -- cgit v1.2.3-70-g09d2 From b56081efab1175872c153d2a83d0462296ffa486 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Mon, 4 Mar 2013 18:37:49 -0800 Subject: more proof stuff --- slides/BudgetFeasibleExperimentalDesign.tex | 118 +++++++++++++++++++--------- 1 file changed, 82 insertions(+), 36 deletions(-) (limited to 'slides/BudgetFeasibleExperimentalDesign.tex') diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex index 98de9c2..cc8a1a6 100644 --- a/slides/BudgetFeasibleExperimentalDesign.tex +++ b/slides/BudgetFeasibleExperimentalDesign.tex @@ -3,7 +3,7 @@ \usepackage[greek,english]{babel} \usepackage[LGR,T1]{fontenc} \usepackage{amsmath,bbm,verbatim} -\usepackage{algpseudocode,algorithm} +\usepackage{algpseudocode,algorithm,bbding} \usepackage{graphicx} \DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} @@ -12,7 +12,7 @@ \title[EconCS Seminar]{Budget Feasible Mechanisms for Experimental Design} \author[Horel, Ioannidis, Muthu]{Thibaut Horel$^*$, \alert{Stratis Ioannidis}$^\dagger$, and S. Muthukrishnan$^\ddagger$} -\institute[]{$^*$INRIA-ENS, $^\dagger$Technicolor, $^\ddagger$Rutgers University} +\institute[Technicolor]{$^*$INRIA-ENS, $^\dagger$Technicolor, $^\ddagger$Rutgers University} \setbeamercovered{transparent} \setbeamertemplate{navigation symbols}{} %\AtBeginSection[] @@ -84,17 +84,17 @@ \item Linear Regression \pause \begin{itemize} - \item We present a \alert{deterministic, poly-time}, truthful, budget feasible, 12.98-appriximate mechanism. - \pause - \vspace*{0.5cm} - \item Previous results: - \begin{itemize} - \item \alert{Randomized}, poly-time, universally truthful, 7.91-approximate mechanism. [Singer 2010, Chen 2011] - \item Deterministic, \alert{exponential time}, truthful mechanism. [Chen 2011] - \end{itemize} + \item We present a \alert{deterministic, poly-time}, truthful, budget feasible, 12.98-approximate mechanism. + % \pause + % \vspace*{0.5cm} + % \item Previous results: + % \begin{itemize} + % \item \alert{Randomized}, poly-time, universally truthful, 7.91-approximate mechanism. [Singer 2010, Chen 2011] + % \item Deterministic, \alert{exponential time}, truthful mechanism. [Chen 2011] + % \end{itemize} \end{itemize} \pause - \vspace*{1cm} + \vspace*{1cm} \item Generalization to other machine learning tasks. \end{itemize} \end{frame} @@ -133,7 +133,7 @@ \end{center} \onslide<3> \begin{center} - $y_i\in \reals$: private data (\eg, survey answer, medical test outcome, etc.) + $y_i\in \reals$: private data (\eg, survey answer, medical test outcome, movie rating, etc.) \end{center} \onslide<4> %\begin{} @@ -157,7 +157,7 @@ \end{center} \onslide<8-9> \begin{center} - \E\ pays subjects\visible<9>{; $y_i$ is revealed only if $i$ is paid.} + \E\ pays subjects\visible<9>{; $y_i$ is revealed only if $i$ is paid at least $c_i$.} \end{center} \onslide<10> \begin{center}{\tt E} estimates ${\beta}$ through \emph{ridge regression}. @@ -173,7 +173,7 @@ Goal: Determine (a) who to pay and (b) how much,\\ so that $\hat{\beta}$ is as a %\end{enumerate} \end{center} \onslide<12-> - \begin{center}Users are \alert{strategic}: the may lie about costs $c_i$\visible<13>{\\ Users \alert{cannot manipulate $x_i$ or $y_i$}.} %\\(tamper-proof experiments) + \begin{center}Users are \alert{strategic}: they may lie about costs $c_i$\visible<13>{\\ Users \alert{cannot manipulate $x_i$ or $y_i$}.} %\\(tamper-proof experiments) \end{center} \end{overprint} @@ -227,9 +227,9 @@ Let $S\subset [N]$ be the set of experiments performed, and \item computationally efficient: polynomial time \pause \vspace{0.2cm} - \item constant approximation: $V(OPT) \leq \alpha V(S)$ with: + \item approximation: $OPT \leq \alpha V(S)$ with: \begin{displaymath} - OPT = \arg\max_{S\subset \mathcal{A}} \left\{V(S)\mid \sum_{i\in S}c_i\leq B\right\} + OPT = \max_{S\subset \mathcal{A}} \left\{V(S)\mid \sum_{i\in S}c_i\leq B\right\} \end{displaymath} \end{itemize} \end{frame} @@ -422,11 +422,11 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} \item \alert{Deterministic, poly-time}, truthful mechanisms for specific submodular functions $V$ : \vspace{0.3cm} \begin{itemize} - \item Knapsack: $2+\sqrt{2}$ [Singer 2010, Chen \emph{et al.}, 2011] + \item \textsc{Knapsack}: $2+\sqrt{2}$ [Singer 2010, Chen \emph{et al.}, 2011] \vspace{0.3cm} \item Matching: 7.37 [Singer, 2010] \vspace{0.3cm} - \item Coverage: 31 [Singer, 2012] + \item \textsc{Coverage}: 31 [Singer, 2012] \vspace{0.3cm} \end{itemize} \end{itemize} @@ -530,7 +530,7 @@ Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} \begin{frame}{Our Main Results} \begin{theorem}<2-> - There exists deterministic, budget feasible, individually rational and truthful mechanism for + There exists a deterministic, budget feasible, individually rational and truthful mechanism for EDP which runs in polynomial time. Its approximation ratio is: \begin{displaymath} @@ -577,7 +577,7 @@ Stop when budget $B$ is reached. \begin{block}{Allocation $S$:} \begin{itemize} \item Let $i^* = \arg\max_i V(\{i\})$ - \item Compute $S_G$ greedily over $[N]\setminus i^*$ + \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$ \item Return $S$: \begin{itemize} \item Selected at random between $i^*$ and $S_G$ @@ -600,10 +600,10 @@ Stop when budget $B$ is reached. \begin{block}{Allocation $S$} \begin{itemize} \item Find $i^* = \arg\max_i V(\{i\})$ - \item Compute $S_G$ greedily + \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$ \item Return: \begin{itemize} - \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert<3>{V(OPT_{-i^*})}$ + \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert<3>{OPT_{-i^*}}$ \item $S_G$ otherwise \end{itemize} \end{itemize} @@ -616,9 +616,10 @@ Stop when budget $B$ is reached. \item budget-feasible \item 8.34-approximate [Chen \etal\ 2011]. \end{itemize} - \vspace{0.5cm} - \pause - \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute +} +\uncover<3-> +{ \vspace{0.5cm} + \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute\ldots } \end{frame} @@ -643,7 +644,7 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause \begin{itemize} \item computable in polynomial time \pause - \item close to $V(OPT_{-i^*})$ + \item close to $OPT_{-i^*}$ \pause \item monotone in costs $c$ \end{itemize} @@ -651,13 +652,55 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause \pause \begin{column}{0.45\textwidth} \begin{itemize} - \item Knapsack (Chen \etal, 2011) - \item Coverage (Singer, 2012) + \item \textsc{Knapsack} (Chen \etal, 2011) + \item \textsc{Coverage} (Singer, 2012) \end{itemize} \end{column} \end{columns} \end{frame} +\begin{frame}{Finding a Relaxation} +\alt<1>{\begin{block}{Submodular Maximization} +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &V(S) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B +\end{align*} +\end{block} +} +{ +\begin{block}{Multilinear Relaxation} +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &F(\lambda)=\mathbb{E}_{\lambda}[V(S)] = \textstyle\sum_{S\subset [N]}V(S)\prod_{i\in S}\lambda_i\prod_{i\notin S}(1-\lambda_i)\\ + \text{subj. to}\qquad &\textstyle\sum_{i\in [N]}\lambda_i c_i\leq B,\\& \lambda_i\in[0,1], i\in [N] +\end{align*} +\end{block} +} +\medskip +\visible<2->{Replace $V$ with expectation when $i\in[N]$ is included with probability $\lambda_i$. }\visible<3->{Let $\lambda^*$ be optimal solution. Then:} +\bigskip +\visible<3->{ +\begin{itemize} +\item<3->$F(\lambda^*)$ is monotone in $c$. +\item<4->$F(\lambda^*)$ is close to $OPT$ under a certain condition on $F$ ($\epsilon$-convexity). Can be shown through \alert{pipage rounding} [Ageev and Sviridenko 2004].\\ +\end{itemize}} +\bigskip +\visible<5->{Good relaxation candidate, if it can be computed in poly-time.} +\visible<6->{ +\begin{center} +\begin{tabular}{lc} + \textsc{Knapsack} &\Checkmark +\end{tabular}\qquad +\begin{tabular}{lc} + \textsc{Coverage} &\XSolidBrush\\ + EDP &\XSolidBrush +\end{tabular} +\end{center} +} +\end{frame} + + \begin{frame}{Main Technical Contribution: Relaxation for EDP} \alt<1>{\begin{block}{\textsc{EDP} } \vspace*{-0.4cm} @@ -678,20 +721,23 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause } \pause \pause +$L(\lambda^*)$ is: \begin{itemize} - \item Poly-time: $L$ is convex and self-concordant + \item Monotone in $c$ +\pause + \item Poly-time: $L$ is convex and self-concordant (Boyd\&Vanderberghe) \pause - \vspace{0.5cm} - \item Close to $V(OPT)$:\pause - \vspace{0.5cm} + % \vspace{0.5cm} + \item Close to $OPT$:\pause + % \vspace{0.5cm} \begin{block}{Technical Lemma} \begin{displaymath} - L^* \leq 2 V(OPT) + V(\{i^*\}) + L(\lambda^*) \leq 2 OPT + V(\{i^*\}) \end{displaymath} \end{block} \end{itemize} \pause - Proved using \emph{pipage rounding} [Ageev and Sviridenko 2004] + Proved by showing that $L(\lambda)\leq 2 F(\lambda)$, where $F$ the multilinear relaxation of $V$. %using \emph{pipage rounding} [Ageev and Sviridenko 2004] \end{frame} \begin{comment} @@ -711,8 +757,8 @@ Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause \pause \begin{column}{0.45\textwidth} \begin{itemize} - \item Knapsack (Chen et al., 2011) - \item Coverage (Singer, 2012) + \item \textsc{Knapsack} (Chen et al., 2011) + \item \textsc{Coverage} (Singer, 2012) \end{itemize} \end{column} \end{columns} -- cgit v1.2.3-70-g09d2 From aac827337cae6769113b06fe589cbe4ea7c6028b Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Mon, 4 Mar 2013 19:06:20 -0800 Subject: proof steps --- slides/BudgetFeasibleExperimentalDesign.tex | 20 +++++++++++++++++--- 1 file changed, 17 insertions(+), 3 deletions(-) (limited to 'slides/BudgetFeasibleExperimentalDesign.tex') diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex index cc8a1a6..bb39ebd 100644 --- a/slides/BudgetFeasibleExperimentalDesign.tex +++ b/slides/BudgetFeasibleExperimentalDesign.tex @@ -732,14 +732,28 @@ $L(\lambda^*)$ is: % \vspace{0.5cm} \begin{block}{Technical Lemma} \begin{displaymath} - L(\lambda^*) \leq 2 OPT + V(\{i^*\}) + L(\lambda^*) \leq 2 OPT + 2V(\{i^*\}) \end{displaymath} \end{block} \end{itemize} - \pause - Proved by showing that $L(\lambda)\leq 2 F(\lambda)$, where $F$ the multilinear relaxation of $V$. %using \emph{pipage rounding} [Ageev and Sviridenko 2004] +% \pause +% Proved by showing that $L(\lambda)\leq 2 F(\lambda)$, where $F$ the multilinear relaxation of $V$. %using \emph{pipage rounding} [Ageev and Sviridenko 2004] \end{frame} +\begin{frame}{Proof Steps} + \begin{block}{Technical Lemma} + \begin{displaymath} + L(\lambda^*) \leq 2 OPT + 2V(\{i^*\}) + \end{displaymath} + \end{block} +\uncover<2->{For all $\lambda\in [0,1]^N$, we show that $L(\lambda) \leq 2F(\lambda)$, where $F$ the multi-linear relaxation of $V$.\\ +\bigskip} +\uncover<3->{ +We show this by establishing first that $\frac{\partial_i F(\lambda)}{\partial_i L(\lambda)}\geq \frac{1}{2}$, and arguing about the minima of $\frac{F(\lambda)}{L(\lambda)}$ over the simplex.\\ +\bigskip +} +\uncover<4>{Finally, we show that $F(\lambda^*)\leq OPT+V(\{i^*\})$ through pipage rounding.} +\end{frame} \begin{comment} \vspace{0.5cm} \pause -- cgit v1.2.3-70-g09d2 From 208570078463ffba34607be087f968de3d06297c Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Tue, 5 Mar 2013 18:03:08 -0800 Subject: final --- slides/BudgetFeasibleExperimentalDesign.tex | 24 +- slides/st31a.pdf | Bin 0 -> 2643551 bytes slides/st31a.svg | 2950 ++++++++++++++++++++++++++ slides/st31b.pdf | Bin 0 -> 2651223 bytes slides/st31b.svg | 2799 +++++++++++++++++++++++++ slides/st31c.pdf | Bin 0 -> 2657787 bytes slides/st31c.svg | 2849 +++++++++++++++++++++++++ slides/st31d.pdf | Bin 0 -> 2647366 bytes slides/st31d.svg | 2783 ++++++++++++++++++++++++ slides/st31dd.pdf | Bin 0 -> 2652500 bytes slides/st31dd.svg | 2824 +++++++++++++++++++++++++ slides/st31e.pdf | Bin 0 -> 2647671 bytes slides/st31e.svg | 2851 +++++++++++++++++++++++++ slides/st31f.pdf | Bin 0 -> 2652266 bytes slides/st31f.svg | 2973 ++++++++++++++++++++++++++ slides/st31g.pdf | Bin 0 -> 2658809 bytes slides/st31g.svg | 3017 +++++++++++++++++++++++++++ 17 files changed, 23058 insertions(+), 12 deletions(-) create mode 100644 slides/st31a.pdf create mode 100644 slides/st31a.svg create mode 100644 slides/st31b.pdf create mode 100644 slides/st31b.svg create mode 100644 slides/st31c.pdf create mode 100644 slides/st31c.svg create mode 100644 slides/st31d.pdf create mode 100644 slides/st31d.svg create mode 100644 slides/st31dd.pdf create mode 100644 slides/st31dd.svg create mode 100644 slides/st31e.pdf create mode 100644 slides/st31e.svg create mode 100644 slides/st31f.pdf create mode 100644 slides/st31f.svg create mode 100644 slides/st31g.pdf create mode 100644 slides/st31g.svg (limited to 'slides/BudgetFeasibleExperimentalDesign.tex') diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex index bb39ebd..aef36b0 100644 --- a/slides/BudgetFeasibleExperimentalDesign.tex +++ b/slides/BudgetFeasibleExperimentalDesign.tex @@ -12,7 +12,7 @@ \title[EconCS Seminar]{Budget Feasible Mechanisms for Experimental Design} \author[Horel, Ioannidis, Muthu]{Thibaut Horel$^*$, \alert{Stratis Ioannidis}$^\dagger$, and S. Muthukrishnan$^\ddagger$} -\institute[Technicolor]{$^*$INRIA-ENS, $^\dagger$Technicolor, $^\ddagger$Rutgers University} +\institute[]{$^*$INRIA-ENS, $^\dagger$Technicolor, $^\ddagger$Rutgers University} \setbeamercovered{transparent} \setbeamertemplate{navigation symbols}{} %\AtBeginSection[] @@ -40,16 +40,16 @@ \section{Introduction} -\begin{frame}{Motivation:A Data Market} +\begin{frame}{Motivation: A Data Market} \begin{center} - \includegraphics<1>[scale=0.4]{st1a.pdf} - \includegraphics<2>[scale=0.4]{st1b.pdf} - \includegraphics<3>[scale=0.4]{st1c.pdf} - \includegraphics<4>[scale=0.4]{st1d.pdf} - \includegraphics<5>[scale=0.4]{st1dd.pdf} - \includegraphics<6>[scale=0.4]{st1e.pdf} - \includegraphics<7>[scale=0.4]{st1f.pdf} - \includegraphics<8>[scale=0.4]{st1g.pdf} + \includegraphics<1>[scale=0.4]{st31a.pdf} + \includegraphics<2>[scale=0.4]{st31b.pdf} + \includegraphics<3>[scale=0.4]{st31c.pdf} + \includegraphics<4>[scale=0.4]{st31d.pdf} + \includegraphics<5>[scale=0.4]{st31dd.pdf} + \includegraphics<6>[scale=0.4]{st31e.pdf} + \includegraphics<7>[scale=0.4]{st31f.pdf} + % \includegraphics<8>[scale=0.4]{st31g.pdf} \end{center} % \begin{center} @@ -84,7 +84,7 @@ \item Linear Regression \pause \begin{itemize} - \item We present a \alert{deterministic, poly-time}, truthful, budget feasible, 12.98-approximate mechanism. + \item We present a deterministic, poly-time, truthful, budget feasible, 12.98-approximate mechanism. % \pause % \vspace*{0.5cm} % \item Previous results: @@ -749,7 +749,7 @@ $L(\lambda^*)$ is: \uncover<2->{For all $\lambda\in [0,1]^N$, we show that $L(\lambda) \leq 2F(\lambda)$, where $F$ the multi-linear relaxation of $V$.\\ \bigskip} \uncover<3->{ -We show this by establishing first that $\frac{\partial_i F(\lambda)}{\partial_i L(\lambda)}\geq \frac{1}{2}$, and arguing about the minima of $\frac{F(\lambda)}{L(\lambda)}$ over the simplex.\\ +We show this by establishing first that $\frac{\partial F/\partial \lambda_i}{\partial L/\partial \lambda_i}\geq \frac{1}{2}$, and arguing about the minima of $\frac{F(\lambda)}{L(\lambda)}$ over the simplex.\\ \bigskip } \uncover<4>{Finally, we show that $F(\lambda^*)\leq OPT+V(\{i^*\})$ through pipage rounding.} diff --git a/slides/st31a.pdf b/slides/st31a.pdf new file mode 100644 index 0000000..81a6200 Binary files /dev/null and b/slides/st31a.pdf differ diff --git a/slides/st31a.svg b/slides/st31a.svg new file mode 100644 index 0000000..a358079 --- /dev/null +++ b/slides/st31a.svg @@ -0,0 +1,2950 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + \ No newline at end of file diff --git a/slides/st31b.pdf b/slides/st31b.pdf new file mode 100644 index 0000000..9230122 Binary files /dev/null and b/slides/st31b.pdf differ diff --git a/slides/st31b.svg b/slides/st31b.svg new file mode 100644 index 0000000..a44b5d5 --- /dev/null +++ b/slides/st31b.svg @@ -0,0 +1,2799 @@ + + + +image/svg+xml + + + + + + + + +data + + + + + + + + + + + + + + + + + + + + + +data + + + + + + + + + + +data + + + + + + + + + + + + + + + + + \ No newline at end of file diff --git a/slides/st31c.pdf b/slides/st31c.pdf new file mode 100644 index 0000000..84d8798 Binary files /dev/null and b/slides/st31c.pdf differ diff --git a/slides/st31c.svg b/slides/st31c.svg new file mode 100644 index 0000000..a722a99 --- /dev/null +++ b/slides/st31c.svg @@ -0,0 +1,2849 @@ + + + +image/svg+xmlClassification algorithm,Regression model,Recommender engine, etc. + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + +data + + + + + + + + + +data + + + + + + + + + + +Data Mining + + + + + + \ No newline at end of file diff --git a/slides/st31d.pdf b/slides/st31d.pdf new file mode 100644 index 0000000..5c941cc Binary files /dev/null and b/slides/st31d.pdf differ diff --git a/slides/st31d.svg b/slides/st31d.svg new file mode 100644 index 0000000..2a090dc --- /dev/null +++ b/slides/st31d.svg @@ -0,0 +1,2783 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +$$ + + + +$ + + + +$$$ + + + + + + + + + + \ No newline at end of file diff --git a/slides/st31dd.pdf b/slides/st31dd.pdf new file mode 100644 index 0000000..cca1133 Binary files /dev/null and b/slides/st31dd.pdf differ diff --git a/slides/st31dd.svg b/slides/st31dd.svg new file mode 100644 index 0000000..2954fb4 --- /dev/null +++ b/slides/st31dd.svg @@ -0,0 +1,2824 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +$$ + + + + +$ + + + + +$$$ + + + + + + + + + + + \ No newline at end of file diff --git a/slides/st31e.pdf b/slides/st31e.pdf new file mode 100644 index 0000000..983e7fe Binary files /dev/null and b/slides/st31e.pdf differ diff --git a/slides/st31e.svg b/slides/st31e.svg new file mode 100644 index 0000000..169b499 --- /dev/null +++ b/slides/st31e.svg @@ -0,0 +1,2851 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +$$ + + +$ + + +$$$ + + +$ + + +$$ + + +$$$ + + + \ No newline at end of file diff --git a/slides/st31f.pdf b/slides/st31f.pdf new file mode 100644 index 0000000..f8716f4 Binary files /dev/null and b/slides/st31f.pdf differ diff --git a/slides/st31f.svg b/slides/st31f.svg new file mode 100644 index 0000000..6121267 --- /dev/null +++ b/slides/st31f.svg @@ -0,0 +1,2973 @@ + + + +image/svg+xml + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + + + + + +data + + + + + + + + + + + +data + + + + + + + + + + + + + + + + + + +$$ + + +$ + + +$$$ + + +$ + + +$$ + + +$$$ + + + \ No newline at end of file diff --git a/slides/st31g.pdf b/slides/st31g.pdf new file mode 100644 index 0000000..fa1083d Binary files /dev/null and b/slides/st31g.pdf differ diff --git a/slides/st31g.svg b/slides/st31g.svg new file mode 100644 index 0000000..8f26050 --- /dev/null +++ b/slides/st31g.svg @@ -0,0 +1,3017 @@ + + + +image/svg+xmlClassification algorithm,Regression model,Recommender engine, etc. + + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + + + +data + + + + + + + + + + +data + + + + + + + + + + + +Data Mining + + + + + + +$$ + +$ + +$$$ + +$ + +$$ + +$$$ + + \ No newline at end of file -- cgit v1.2.3-70-g09d2 From fc8bef3550fc35e2d6663665ee4c437aaa75eda1 Mon Sep 17 00:00:00 2001 From: Stratis Ioannidis Date: Mon, 25 Mar 2013 21:05:46 -0700 Subject: google --- definitions.tex | 1 + slides/BudgetFeasibleExperimentalDesign.tex | 2 +- slides/BudgetFeasibleExperimentalDesignGoogle.tex | 980 +++++++ slides/beamerbfootertechnicolor.png | Bin 0 -> 4039 bytes slides/beamerblogotechnicolor.png | Bin 0 -> 7333 bytes slides/beamercolorthemetechnicolor.sty | 65 + slides/beamerfontthemetechnicolor.sty | 34 + slides/beamerfootertechnicolor.png | Bin 0 -> 5197 bytes slides/beamerinnerthemetechnicolor.sty | 276 ++ slides/beamerlogotechnicolor.png | Bin 0 -> 7436 bytes slides/beamerouterthemetechnicolor.sty | 58 + slides/beamersampletechnicolor1.jpg | Bin 0 -> 122259 bytes slides/beamersampletechnicolor10.jpg | Bin 0 -> 122571 bytes slides/beamersampletechnicolor11.jpg | Bin 0 -> 90693 bytes slides/beamersampletechnicolor12.jpg | Bin 0 -> 102076 bytes slides/beamersampletechnicolor13.jpg | Bin 0 -> 154429 bytes slides/beamersampletechnicolor14.jpg | Bin 0 -> 196715 bytes slides/beamersampletechnicolor15.jpg | Bin 0 -> 81874 bytes slides/beamersampletechnicolor16.jpg | Bin 0 -> 346310 bytes slides/beamersampletechnicolor17.jpg | Bin 0 -> 414694 bytes slides/beamersampletechnicolor2.jpg | Bin 0 -> 451481 bytes slides/beamersampletechnicolor3.jpg | Bin 0 -> 293218 bytes slides/beamersampletechnicolor4.jpg | Bin 0 -> 273250 bytes slides/beamersampletechnicolor5.jpg | Bin 0 -> 128110 bytes slides/beamersampletechnicolor6.jpg | Bin 0 -> 90245 bytes slides/beamersampletechnicolor7.jpg | Bin 0 -> 144036 bytes slides/beamersampletechnicolor8.jpg | Bin 0 -> 198050 bytes slides/beamersampletechnicolor9.jpg | Bin 0 -> 314462 bytes slides/beamerthemetechnicolor.sty | 192 ++ slides/stg-1.pdf | Bin 0 -> 119989 bytes slides/stg-1.svg | 3210 ++++++++++++++++++++ slides/stg-2.pdf | Bin 0 -> 113421 bytes slides/stg-2.svg | 3171 ++++++++++++++++++++ slides/stg-3.pdf | Bin 0 -> 109978 bytes slides/stg-3.svg | 3065 +++++++++++++++++++ slides/stg-4.pdf | Bin 0 -> 114812 bytes slides/stg-4.svg | 3002 +++++++++++++++++++ slides/stg-5.pdf | Bin 0 -> 109669 bytes slides/stg-5.svg | 3003 +++++++++++++++++++ slides/stg-6.pdf | Bin 0 -> 118955 bytes slides/stg-6.svg | 3057 +++++++++++++++++++ slides/stg-7.pdf | Bin 0 -> 108921 bytes slides/stg-7.svg | 2929 +++++++++++++++++++ slides/stg-8.pdf | Bin 0 -> 62180 bytes slides/stg-8.svg | 2356 +++++++++++++++ slides/stg-9.pdf | 0 slides/stg31dd.svg | 2824 ++++++++++++++++++ slides/stgall.svg | 3232 +++++++++++++++++++++ 48 files changed, 31456 insertions(+), 1 deletion(-) create mode 100644 slides/BudgetFeasibleExperimentalDesignGoogle.tex create mode 100644 slides/beamerbfootertechnicolor.png create mode 100644 slides/beamerblogotechnicolor.png create mode 100644 slides/beamercolorthemetechnicolor.sty create mode 100644 slides/beamerfontthemetechnicolor.sty create mode 100644 slides/beamerfootertechnicolor.png create mode 100644 slides/beamerinnerthemetechnicolor.sty create mode 100644 slides/beamerlogotechnicolor.png create mode 100644 slides/beamerouterthemetechnicolor.sty create mode 100644 slides/beamersampletechnicolor1.jpg create mode 100644 slides/beamersampletechnicolor10.jpg create mode 100644 slides/beamersampletechnicolor11.jpg create mode 100644 slides/beamersampletechnicolor12.jpg create mode 100644 slides/beamersampletechnicolor13.jpg create mode 100644 slides/beamersampletechnicolor14.jpg create mode 100644 slides/beamersampletechnicolor15.jpg create mode 100644 slides/beamersampletechnicolor16.jpg create mode 100644 slides/beamersampletechnicolor17.jpg create mode 100644 slides/beamersampletechnicolor2.jpg create mode 100644 slides/beamersampletechnicolor3.jpg create mode 100644 slides/beamersampletechnicolor4.jpg create mode 100644 slides/beamersampletechnicolor5.jpg create mode 100644 slides/beamersampletechnicolor6.jpg create mode 100644 slides/beamersampletechnicolor7.jpg create mode 100644 slides/beamersampletechnicolor8.jpg create mode 100644 slides/beamersampletechnicolor9.jpg create mode 100644 slides/beamerthemetechnicolor.sty create mode 100644 slides/stg-1.pdf create mode 100644 slides/stg-1.svg create mode 100644 slides/stg-2.pdf create mode 100644 slides/stg-2.svg create mode 100644 slides/stg-3.pdf create mode 100644 slides/stg-3.svg create mode 100644 slides/stg-4.pdf create mode 100644 slides/stg-4.svg create mode 100644 slides/stg-5.pdf create mode 100644 slides/stg-5.svg create mode 100644 slides/stg-6.pdf create mode 100644 slides/stg-6.svg create mode 100644 slides/stg-7.pdf create mode 100644 slides/stg-7.svg create mode 100644 slides/stg-8.pdf create mode 100644 slides/stg-8.svg create mode 100644 slides/stg-9.pdf create mode 100644 slides/stg31dd.svg create mode 100644 slides/stgall.svg (limited to 'slides/BudgetFeasibleExperimentalDesign.tex') diff --git a/definitions.tex b/definitions.tex index 49dd5bc..962a438 100644 --- a/definitions.tex +++ b/definitions.tex @@ -19,6 +19,7 @@ \DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \newcommand{\reals}{\ensuremath{\mathbb{R}}} +\newcommand{\naturals}{\ensuremath{\mathbb{N}}} \newcommand{\prob}{\ensuremath{\mathrm{Pr}}} \newcommand{\stratis}[1]{\textcolor{green}{Stratis: #1}} \newcommand{\thibaut}[1]{\textcolor{blue}{Thibaut: #1}} diff --git a/slides/BudgetFeasibleExperimentalDesign.tex b/slides/BudgetFeasibleExperimentalDesign.tex index aef36b0..7155040 100644 --- a/slides/BudgetFeasibleExperimentalDesign.tex +++ b/slides/BudgetFeasibleExperimentalDesign.tex @@ -252,7 +252,7 @@ $$\beta \sim \mathcal{N}(0,\sigma^2 R). $$} \end{align*} } \visible<5->{\hspace*{3in}\alert{Ridge Regression}\\} -\visible<6>{\hspace*{2.8in}\alert{$R=I$: homotropic prior}} +\visible<6>{\hspace*{2.8in}\alert{$R=I$: homotropic prior, $\lambda=1$}} \end{frame} \begin{frame}{Which Experiments Are Informative? (contd.)} diff --git a/slides/BudgetFeasibleExperimentalDesignGoogle.tex b/slides/BudgetFeasibleExperimentalDesignGoogle.tex new file mode 100644 index 0000000..3fcec7c --- /dev/null +++ b/slides/BudgetFeasibleExperimentalDesignGoogle.tex @@ -0,0 +1,980 @@ +\documentclass[10pt]{beamer} +\usepackage[utf8x]{inputenc} +\usepackage[greek,english]{babel} +\usepackage[LGR,T1]{fontenc} +\usepackage{amsmath,bbm,verbatim} +\usepackage{algpseudocode,algorithm,bbding} +\usepackage{graphicx} +\DeclareMathOperator*{\argmax}{arg\,max} +\DeclareMathOperator*{\argmin}{arg\,min} +\usetheme{technicolor} +\newcommand{\E}{{\tt E}} + +\title{Budget Feasible Mechanisms \hspace*{5cm}for Experimental Design} +\subtitle{Thibaut Horel$^*$, Stratis Ioannidis$^\dagger$, and S. Muthukrishnan$^\ddagger$} +\author{$^*$INRIA-ENS, $^\dagger$Technicolor, $^\ddagger$Rutgers University} +\setbeamercovered{transparent} +%\setbeamertemplate{navigation symbols}{} +%\AtBeginSection[] +%{ +%\begin{frame} +%\frametitle{Outline} +%\tableofcontents[currentsection] +%\end{frame} +%} + + +\newcommand{\ie}{\emph{i.e.}} +\newcommand{\eg}{\emph{e.g.}} +\newcommand{\etc}{\emph{etc.}} +\newcommand{\etal}{\emph{et al.}} +\newcommand{\reals}{\ensuremath{\mathbb{R}}} + +\usefonttheme[onlymath]{serif} +\begin{document} + +\maketitle + +\section{Introduction} + + +\begin{frame}{Motivation: A Data Market} + \begin{center} + \includegraphics<1>[scale=0.4]{st31a.pdf} + \includegraphics<2>[scale=0.4]{st31b.pdf} + \includegraphics<3>[scale=0.4]{st31c.pdf} + \includegraphics<4>[scale=0.4]{st31d.pdf} + \includegraphics<5>[scale=0.4]{st31dd.pdf} + \includegraphics<6>[scale=0.4]{st31e.pdf} + \includegraphics<7>[scale=0.4]{st31f.pdf} + % \includegraphics<8>[scale=0.4]{st31g.pdf} + \end{center} + + % \begin{center} + % \begin{overprint} + % \onslide<1-8>\begin{center}\end{center} +% \end{overprint} + % \end{center} +\end{frame} + +\begin{frame}{Challenges} +% \begin{overprint} + \begin{itemize} + \item<1-> Value of data? + \visible<3-4>{\begin{itemize} + \item Experimental Design + \end{itemize}} +\vspace*{1cm} + \item<2-> Strategic users? + \visible<4>{\begin{itemize} + \item Budget Feasible Auctions [Singer 2010] + \end{itemize}} + \end{itemize} +% \end{overprint} +\end{frame} + +\begin{frame}{Contributions} + \pause + \begin{itemize} + \item Experimental design when users are strategic + \pause + \vspace*{1cm} + \item Linear Regression + \pause + \begin{itemize} + \item We present a deterministic, poly-time, truthful, budget feasible, 12.98-approximate mechanism. + % \pause + % \vspace*{0.5cm} + % \item Previous results: + % \begin{itemize} + % \item \alert{Randomized}, poly-time, universally truthful, 7.91-approximate mechanism. [Singer 2010, Chen 2011] + % \item Deterministic, \alert{exponential time}, truthful mechanism. [Chen 2011] + % \end{itemize} + \end{itemize} + \pause + \vspace*{1cm} + \item Generalization to other machine learning tasks. + \end{itemize} +\end{frame} + + +\section{Setting} +\begin{frame}{Outline} +\tableofcontents +\end{frame} + +\begin{frame}{Outline} + \tableofcontents[currentsection] +\end{frame} + + +\begin{frame}{Formulating the Problem} + \begin{center} + \includegraphics<1>[scale=0.4]{st2.pdf} + \includegraphics<2>[scale=0.4]{st3.pdf} + \includegraphics<3>[scale=0.4]{st4.pdf} + \includegraphics<4>[scale=0.4]{st5.pdf} + \includegraphics<5>[scale=0.4]{st6.pdf} + \includegraphics<6>[scale=0.4]{st6a.pdf} + \includegraphics<7>[scale=0.4]{st6b.pdf} + \includegraphics<8>[scale=0.4]{st6c.pdf} + \includegraphics<9>[scale=0.4]{st6d.pdf} + \includegraphics<10->[scale=0.4]{st6e.pdf} + \end{center} + \vspace*{-2em} + \begin{center} + \begin{overprint} + \onslide<1>\begin{center}$N$ ``experiment subjects'', $[N]\equiv \{1,\ldots,N\}$ \end{center} + \onslide<2> + \begin{center} + $x_i\in \reals^d$: public features (\eg, age, gender, height, \etc) + \end{center} + \onslide<3> + \begin{center} + $y_i\in \reals$: private data (\eg, survey answer, medical test outcome, movie rating, etc.) + \end{center} + \onslide<4> + %\begin{} + \textbf{Gaussian Linear Model.} There exists $\beta\in \reals^d$ s.t.\vspace*{-1em} + \begin{displaymath} + y_i = \beta^T x_i + \varepsilon_i,\quad + \varepsilon_i\sim\mathcal{N}(0,\sigma^2), \quad i\in [N] + \end{displaymath} +%$$y_i = \beta^Tx_i + \varepsilon_i, i=1,\ldots, N$$ + %\end{center} + \onslide<5> + \begin{center} + Experimenter {\tt E} wishes to learn $\beta$. + \end{center} + \onslide<6>\begin{center} + Each subject $i\in [N]$ has a cost $c_i\in \reals_+$ + \end{center} + \onslide<7> + \begin{center} + \E\ has a budget $B$. + \end{center} + \onslide<8-9> + \begin{center} + \E\ pays subjects\visible<9>{; $y_i$ is revealed only if $i$ is paid at least $c_i$.} + \end{center} + \onslide<10> + \begin{center}{\tt E} estimates ${\beta}$ through \emph{ridge regression}. + \end{center} + \onslide<11> + \begin{center} +%\begin{enumerate} +Goal: Determine (a) who to pay and (b) how much,\\ so that $\hat{\beta}$ is as accurate as possible. +%\begin{align*} +% \text{Determine (a) who to pay:}\quad &S\subseteq [N], \text{ and}\\ +% \text{(b)~ how much:}\quad &p_i\in \reals_+,~~i\in S. +%\end{align*} +%\end{enumerate} + \end{center} + \onslide<12-> + \begin{center}Users are \alert{strategic}: they may lie about costs $c_i$\visible<13>{\\ Users \alert{cannot manipulate $x_i$ or $y_i$}.} %\\(tamper-proof experiments) + \end{center} + + \end{overprint} + \end{center} + +\end{frame} + +\begin{frame}{Budget Feasible Mechanism Design [Singer 2010]} +Let $S\subset [N]$ be the set of experiments performed, and + $c=[c_i]_{i\in [N]}$ be the subject costs. \\\bigskip +\visible<2->{Let $V(S)\in\reals_+$ denote the \alert{value} of the experiments.} +\visible<3->{$$\text{High }V(S) \Leftrightarrow \text{ estimate }\hat{\beta}(S) \text{ is close to }\beta $$} +\visible<4->{ +%\item<1->Fix budget $B$ and value function $V:2^{[N]}\to\reals_+$ +\begin{block}{Reverse Auction Mechanism} + A mechanism $\mathcal{M}(c)=(S(c),p(c))$ comprises +\begin{itemize} +\item an \alert{allocation function} $S:\reals_+^N\to 2^{[N]}$, and +\item a \alert{payment function} $p:\reals_+^N\to \reals_+^N$. +\end{itemize} +\end{block} +} +\end{frame} + + +\begin{frame}{Budget Feasible Mechanism Design [Singer 2010] (cont'd)} + We seek mechanisms $\mathcal{M}=(S,p)$ that are: + \pause + \vspace{0.3cm} + \begin{itemize} + \item Normalized: $p_i=0$ if $i\notin S$. + \vspace{0.2cm} + \pause + \item Individually Rational: $p_i\geq c_i,\;i\in S$ + \vspace{0.2cm} + \pause + \item Truthful: $p_i(c_i,c_{-i})-\mathbbm{1}_{i\in S(c_i,c_{-i})}\cdot c_i \geq p_i(c_i',c_{-i})-\mathbbm{1}_{i\in S(c_i',c_{-i})}\cdot c_i $ + \vspace{0.2cm} + \pause + \item budget feasible: $\sum_{i\in S} p_i \leq B$ + \vspace{0.2cm} + \end{itemize} + + \pause + \vspace{0.3cm} + + In addition, $\mathcal{M}$ must be: + \vspace{0.3cm} + \pause + \begin{itemize} + \item computationally efficient: polynomial time + \pause + \vspace{0.2cm} + \item approximation: $OPT \leq \alpha V(S)$ with: + \begin{displaymath} + OPT = \max_{S\subset \mathcal{A}} \left\{V(S)\mid \sum_{i\in S}c_i\leq B\right\} + \end{displaymath} + \end{itemize} +\end{frame} + + + + +\begin{frame}{Which Experiments Are Informative?} + +\alt<1>{What is the appropriate value function $V$?} {Let $S\subset [N]$ be the set of experiments performed.\\\medskip} +%\end{overprint} +\visible<3->{Assume that \E\ has a \emph{prior} on $\beta$: +$$\beta \sim \mathcal{N}(0,\sigma^2 R). $$} +\visible<4->{Maximum a-posteriori estimation: +\begin{align*} + \hat{\beta} &= \argmax_{\beta\in\reals^d} \mathbf{P}(\beta\mid y_i, i\in S) \\ +&=\argmin_{\beta\in\reals^d} \big(\sum_{i\in S} (y_i - {\beta}^Tx_i)^2 + + \only<4-5>{\alert<5->{{\beta}^TR^{-1}\beta}\big)} \only<6>{\lambda\alert{\|\beta\|_2^2}\big)~~~~~} +%= (R+{X_S}^TX_S)^{-1}X_S^Ty_S +\end{align*} +} +\visible<5->{\hspace*{3in}\alert{Ridge Regression}\\} +\visible<6>{\hspace*{2.8in}\alert{$R=\lambda I$: homotropic prior}} +\end{frame} + +\begin{frame}{Which Experiments Are Informative? (contd.)} +Let $S\subset [N]$ be the set of experiments performed.\\\bigskip + +\visible<2->{ +Information Gain/D-optimality Criterion: +\begin{align*} +V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\ +\visible<3->{& = \frac{1}{2}\log\det (R^{-1}+\sum_{i\in S}x_ix_i^T)} +\end{align*} + +\visible<4->{ \emph{I.e.}: $$\alert{\text{Value of~}S=\text{Reduction of Uncertainty.}} $$} +\vspace*{-0.7cm} +} +\end{frame} + +\begin{frame}{Full Information Setting} +\onslide<2->{ +\begin{block}{\textsc{Experimental Design Problem (EDP)} } +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &V(S) = \log \det (\alert<3>{I}+\sum_{i\in S}x_ix_i^T) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B +\end{align*} +\end{block} +} +\begin{itemize} +\item<3->$R=I$: homotropic prior +\item<4-> EDP is NP-hard +\item<5-> $V$ is submodular, monotone, non-negative, and $V(\emptyset)=0$ +\item<6-> $\frac{1}{1-1/e}$-approximable (Sviridenko 2004, Krause and Guestrin 2005) +\end{itemize} + + + +\end{frame} + +%\begin{frame}{Classic Experimental Design} +%\begin{center} +%\includegraphics[scale=0.3]{st10.pdf} +%\end{center} +%\begin{align*} +%\text{Maximize}& & V(S) &= \log \det (R^{-1}+X^T_SX_S) \\ +%\text{subj. to}& & |S|&\leq k +%\end{align*} +%\end{frame} + +\begin{comment} +\begin{frame}{Cardinality vs. Budget Constraint} +\begin{center} +\includegraphics<1>[scale=0.3]{st10a.pdf} +\includegraphics<2>[scale=0.3]{st10b.pdf} +\includegraphics<3>[scale=0.3]{st10c.pdf} +\includegraphics<4>[scale=0.3]{st10d.pdf} +\includegraphics<5->[scale=0.3]{st10f.pdf} +\end{center} + + \begin{center} + \begin{overprint} +\onslide<1>\begin{align*} +\text{Maximize}& & V(S) &= \log \det (R^{-1}+X^T_SX_S) \\ +\text{subj. to}& & |S|&\leq k +\end{align*} + + \onslide<6-> +\begin{block}{\textsc{Experimental Design Problem (EDP)} } +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &V(S) = \log \det (\alert<7>{I}+X^T_SX_S) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B + \end{align*} +\end{block} + \visible<7>{\alert{$R=I$: homotropic prior}} + + \end{overprint} + \end{center} +\end{frame} + +\begin{frame}{Full-Information Setting} +\begin{block}{\textsc{Experimental Design Problem (EDP)} } +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &V(S) = \log \det ({I}+X^T_SX_S) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B + \end{align*} +\end{block} +\begin{itemize} +\item<2-> EDP is NP-hard +\item<3-> $V$ is submodular, monotone, non-negative, and $V(\emptyset)=0$ +\item<4-> $\frac{1}{1-1/e}$-approximable (Sviridenko 2004, Krause and Guestrin 2005) +\end{itemize} +\end{frame} + +\begin{frame}{Strategic Subjects} +%\begin{center} +%\includegraphics<1->[scale=0.3]{st10c.pdf} +%\end{center} +%\begin{overprint} +\begin{itemize} +\visible<2->{\item +Subjects are \alert{strategic} and may lie about costs $c_i$.}\\\bigskip +\visible<3>{\item +Subjects \alert{do not lie} about $y_i$ (tamper-proof experiments).} +\end{itemize} +\end{frame} + +\begin{frame}{Budget Feasible Mechanism Design [Singer 2010]} +\begin{center} +\includegraphics<1>[scale=0.3]{st11a.pdf} +\includegraphics<2>[scale=0.3]{st11b.pdf} +\includegraphics<3>[scale=0.3]{st11c.pdf} +\includegraphics<4>[scale=0.3]{st11d.pdf} +\end{center} +\begin{itemize} +%\item<1->Fix budget $B$ and value function $V:2^{[N]}\to\reals_+$ +\item<2->Let $c=[c_i]_{i\in [N]}$ be the subject costs. +\item<3-> A mechanism $\mathcal{M}(c)=(S(c),p(c))$ comprises +\begin{itemize} +\item<3-> an \alert{allocation function} $S:\reals_+^N\to 2^{[N]}$, and +\item<4> a \alert{payment function} $p:\reals_+^N\to \reals_+^N$. +\end{itemize} +\end{itemize} +\end{frame} +%\section{Budget feasible mechanism design} + +%\begin{frame}{Budget Feasible Mechanism Design [Singer 2010]} +%\begin{itemize} +% \item set of $N$ sellers: $\mathcal{A} = \{1,\ldots,N\}$; a buyer +% \vspace{0.3cm} +% \pause +% \item $V$ value function of the buyer, $V:2^\mathcal{A}\rightarrow \mathbb{R}^+$ +% \vspace{0.3cm} +% \pause +% \item $c_i\in\mathbb{R}^+$ price of seller's $i$ good +% \vspace{0.3cm} +% \pause +% \item $B$ budget constraint of the buyer +%\end{itemize} +% +%\vspace{0.5cm} +%\pause +% +%\begin{block}{Goal} +% \begin{itemize} +% \item Find $S\subset \mathcal{A}$ \alert{maximizing} $V(S)$ +% \vspace{0.3cm} +% \item Find \alert{payment} $p_i$ to seller $i\in S$ +% \end{itemize} +%\end{block} +%\end{frame} +\end{comment} + +\begin{frame}{Strategic Subjects} + When $V$ is submodular: + % \vspace{1cm} + \pause + \begin{itemize} + \item \alert{Randomized}, poly-time, universally truthful mechanism, + approximation ratio: $7.91$ [Singer 2010, Chen \emph{et al.}, 2011] + \vspace{0.5cm} + \pause + \item Deterministic, \alert{exponential time}, truthful mechanism, + approximation ratio: $8.34$ [Singer 2010, Chen \emph{et al.}, 2011] + \vspace{0.5cm} + \pause + \item \alert{Deterministic, poly-time}, truthful mechanisms for specific submodular functions $V$ : + \vspace{0.3cm} + \begin{itemize} + \item \textsc{Knapsack}: $2+\sqrt{2}$ [Singer 2010, Chen \emph{et al.}, 2011] + \vspace{0.3cm} + \item \textsc{Matching}: 7.37 [Singer, 2010] + \vspace{0.3cm} + \item \textsc{Coverage}: 31 [Singer, 2012] + \vspace{0.3cm} + \end{itemize} + \end{itemize} +\end{frame} + + +\begin{comment} +\begin{frame}{Outline} + \tableofcontents[currentsection] +\end{frame} + +\begin{frame}{Linear Regression} + \begin{center} + \includegraphics<1-4>[scale=0.5]{5.pdf} + \includegraphics<5>[scale=0.5]{6.pdf} + \includegraphics<6>[scale=0.5]{7.pdf} + \includegraphics<7>[scale=0.5]{8.pdf} + \end{center} + + \begin{center} + \begin{overprint} + \onslide<1>\begin{center}$N$ users\end{center} + \onslide<2> + \begin{center} + $x_i$: public features (e.g. age, gender, height, etc.) + \end{center} + \onslide<3> + \begin{center} + $y_i$: private data (e.g. disease, etc.) + \end{center} + \onslide<4> + \begin{center} + Gaussian Linear model: $y_i = \beta^Tx_i + \varepsilon_i$ + \end{center} + \begin{displaymath} + \beta^* = \arg\min_\beta \sum_i |y_i-\beta^Tx_i|^2 + \end{displaymath} + \end{overprint} + \end{center} +\end{frame} + +\begin{frame}{Experimental design} + \begin{itemize} + \item Public vector of features $x_i\in\mathbb{R}^d$ + \item Private data $y_i\in\mathbb{R}$ + \end{itemize} + + \vspace{0.5cm} + + Gaussian linear model: + \begin{displaymath} + y_i = \beta^T x_i + \varepsilon_i,\quad\beta\in\mathbb{R}^d,\; + \varepsilon_i\sim\mathcal{N}(0,\sigma^2) + \end{displaymath} + + \pause + \vspace{0.5cm} + + Which users to select?\pause{} Experimental design $\Rightarrow$ D-optimal criterion + + \vspace{0.5cm} + + \begin{block}{Experimental Design} + \begin{displaymath} + \textsf{\alert{maximize}}\quad V(S) = \log\det\left(I_d + \sum_{i\in S} x_i x_i^T\right)\quad \textsf{\alert{subject to}}\quad |S|\leq k + \end{displaymath} + \end{block} +\end{frame} + +\begin{frame}{Budgeted Experimental design} + \begin{displaymath} + \textsf{\alert{maximize}}\quad V(S) = \log\det\left(I_d + \sum_{i\in S} x_i x_i^T\right)\quad \textsf{\alert{subject to}}\quad \sum_{i\in S}c_i\leq B + \end{displaymath} + + \vspace{1cm} + + \begin{itemize} + \item the non-strategic optimization problem is NP-hard + \vspace{0.3cm} + \pause + \item $V$ is submodular + \vspace{0.3cm} + \pause + \item previous results give a randomized budget feasible mechanism + \vspace{0.3cm} + \pause + \item deterministic mechanism? + \end{itemize} +\end{frame} + +\begin{frame}{Main result} +\end{comment} + +\section{Main Results} + + +\begin{frame}{Outline} + \tableofcontents[currentsection] +\end{frame} + + +\begin{frame}{Our Main Results} + \begin{theorem}<2-> + There exists a deterministic, budget feasible, individually rational and truthful mechanism for + EDP which runs in polynomial time. Its + approximation ratio is: + \begin{displaymath} + \frac{10e-3 + \sqrt{64e^2-24e + 9}}{2(e-1)} + \simeq 12.98 + \end{displaymath} + \end{theorem} + \begin{theorem}<3-> + There is no 2-approximate, budget feasible, individually rational and truthful mechanism for + EDP. \end{theorem} + +\end{frame} + +\begin{frame}{Myerson's Theorem} +\begin{theorem}[Myerson 1981] + A normalized mechanism $\mathcal{M} = (S,p)$ for a single parameter auction is +truthful iff: +\begin{enumerate} +\item<2-> + $S$ is \alert{monotone}, \emph{i.e.},%\\ for any agent $i$ and $c_i' \leq c_i$, for any fixed costs $c_{-i}$ of agents in $[N]\setminus\{i\}$, + $$\text{for all}~c_i' \leq c_i,\quad i\in S(c_i, +c_{-i})\text{ implies }i\in S(c_i', c_{-i}),$$ and +\item<3-> + subjects are paid \alert{threshold payments}, \emph{i.e.}, $$\text{for all }i\in S(c), \qquad p_i(c)=\inf\{c_i': i\in S(c_i', c_{-i})\}.$$ +\end{enumerate} +\end{theorem} +\uncover<4->{Focus on \alert{monotone} mechanisms.} + +\end{frame} + +\begin{frame}{A Greedy Construction for Submodular $V$} +Construct $S_G$ by adding elements with \emph{highest marginal-value-per-cost}.\\ +\bigskip +\visible<2->{If $S_G=S$ so far, add to it: +\begin{align*} + i = \argmax_{j\in\mathcal{N}\setminus S}\frac{V(S\cup\{i\}) - V(S)}{c_i}\label{greedy} +\end{align*} +Stop when budget $B$ is reached. +} + +\end{frame} + +\begin{frame}{Constant-Approximation Algorithm for Submodular $V$} + \begin{block}{Allocation $S$:} + \begin{itemize} + \item Let $i^* = \arg\max_i V(\{i\})$ + \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$ + \item Return: + \begin{itemize} + \item $i^*$ if $V(\{i^*\})>V(S_G)$ + \item $S_G$ o.w. + \end{itemize} + \end{itemize} + \end{block} +\vspace*{2em} +\uncover<2->{ +[Singer 2010] This algorithm is: +\begin{itemize} +\item poly-time, +\item $\frac{5e}{e-1}$-approximate. +\end{itemize} +} +\uncover<3-> +{ \vspace{0.5cm} + \alert{Problem:} As a mechanism, it is not monotone\ldots +} +\end{frame} + +\begin{frame}{Randomized Mechanism for Submodular $V$} + \begin{block}{Allocation $S$:} + \begin{itemize} + \item Let $i^* = \arg\max_i V(\{i\})$ + \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$ + \item Return $S$: + \begin{itemize} + \item Selected at random between $i^*$ and $S_G$ + \end{itemize} + \end{itemize} + \end{block} + \vspace{0.5cm} +\uncover<2->{ +[Singer 2010] Along with threshold payments, this mechanism is: +\begin{itemize} +\item poly-time, +\item universally truthful, +\item budget-feasible +\item 7.91-approximate [Chen \etal\ 2011]. +\end{itemize} +} +\uncover<3-> +{ \vspace{0.5cm} + \alert{Problem:} $OPT\leq 7.91 \cdot \alert{\mathbb{E}[V(S)]}$\ldots +} +\end{frame} + +\begin{frame}{Deterministic Mechanism for Submodular $V$} + \begin{block}{Allocation $S$} + \begin{itemize} + \item Find $i^* = \arg\max_i V(\{i\})$ + \item Compute $S_G$ greedily over $[N]\setminus \{i^*\}$ + \item Return: + \begin{itemize} + \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert<3>{OPT_{-i^*}}$ + \item $S_G$ otherwise + \end{itemize} + \end{itemize} + \end{block} + \vspace{0.5cm} +\uncover<2->{ +[Singer 2010] Along with threshold payments, this mechanism is: +\begin{itemize} +\item truthful, +\item budget-feasible +\item 8.34-approximate [Chen \etal\ 2011]. +\end{itemize} +} +\uncover<3-> +{ %\vspace{0.1cm} + \alert{Problem:} $OPT_{-i^*}$ is NP-hard to compute\ldots +} +\end{frame} + + +\begin{frame}{Blueprint for Deterministic, Poly-time Algorithm} +Azar and Gamzu 2008, Singer 2010, Chen \etal\ 2011: + \begin{block}{Allocation $S$} + \begin{itemize} + \item Find $i^* = \arg\max_i V(\{i\})$ + \item Compute $S_G$ greedily + \item Return: + \begin{itemize} + \item $\{i^*\}$ if $V(\{i^*\}) \geq \alert{L^*}$ + \item $S_G$ otherwise + \end{itemize} + \end{itemize} + \end{block} + \vspace{0.2cm} + \begin{columns}[c] + \begin{column}{0.53\textwidth} +Key idea:\\ Replace $OPT$ with a \alert{relaxation $L^*$}:\pause + \begin{itemize} + \item computable in polynomial time + \pause + \item close to $OPT_{-i^*}$ + \pause + \item monotone in costs $c$ + \end{itemize} + \end{column} + \pause + \begin{column}{0.45\textwidth} + \begin{itemize} + \item \textsc{Knapsack} (Chen \etal, 2011) + \item \textsc{Coverage} (Singer, 2012) + \end{itemize} + \end{column} + \end{columns} +\end{frame} + + +\begin{frame}{Finding a Relaxation} +\alt<1>{\begin{block}{Submodular Maximization} +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &V(S) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B +\end{align*} +\end{block} +} +{ +\begin{block}{Multilinear Relaxation} +\vspace*{-0.6cm} +\begin{align*} + \text{Maximize}\qquad &F(\lambda)=\mathbb{E}_{\lambda}[V(S)] = \textstyle\sum_{S\subset [N]}V(S)\prod_{i\in S}\lambda_i\prod_{i\notin S}(1-\lambda_i)\\ + \text{subj. to}\qquad &\textstyle\sum_{i\in [N]}\lambda_i c_i\leq B,\\& \lambda_i\in[0,1], i\in [N] +\end{align*} +\vspace*{-0.6cm} +\end{block} +} +\medskip +\visible<2->{Replace $V$ with expectation when $i\in[N]$ is included with probability $\lambda_i$. \\} +\visible<3->{\begin{itemize} +\item +For $S\subseteq [N]$, +$V(S) = F(\lambda)\text{ for }\lambda_i=\mathbbm{1}_{i\in S}\quad\visible<4->{\Rightarrow\quad OPT \leq F(\lambda^*).}$ +\visible<5->{%\vspace*{-0.6cm} +\item If $V$ is submodular, for any $\lambda\in [0,1]^N$, there exists $\bar{\lambda}$ \\with \emph{at most one} $\bar{\lambda}_i\notin\{0,1\}$ s.t. +\begin{align*}F(\lambda) \leq F(\bar{\lambda}) &\visible<7->{=(1-\bar{\lambda}_i) V(S)+\bar{\lambda}_i V(S\cup \{i\})}\visible<8->{\leq V(S)+ V(\{i\})}\\ +\visible<9->{&\Rightarrow\quad F(\lambda^*)\leq OPT+V(\{i^*\})} \end{align*}} + \visible<6->{shown through \alert{pipage rounding} [Ageev and Sviridenko 2004]} +\end{itemize} +} +\end{frame} + +\begin{frame}{Finding a Relaxation} +\begin{block}{Multilinear Relaxation} +\vspace*{-0.6cm} +\begin{align*} + \text{Maximize}\qquad &F(\lambda)=\mathbb{E}_{\lambda}[V(S)] = \textstyle\sum_{S\subset [N]}V(S)\prod_{i\in S}\lambda_i\prod_{i\notin S}(1-\lambda_i)\\ + \text{subj. to}\qquad &\textstyle\sum_{i\in [N]}\lambda_i c_i\leq B,\\& \lambda_i\in[0,1], i\in [N] +\end{align*} +\vspace*{-0.6cm} +\end{block} +\medskip +\visible<2->{ For $\lambda^*$ the optimal solution. Then:} +\medskip +\visible<3->{ +\begin{itemize} +\item<3->$F(\lambda^*)$ is close to $OPT$: +$$OPT \leq F(\lambda^*) \leq OPT +V(\{i^*\})$$ %under a certain condition on $F$ ($\epsilon$-convexity): +%can be shown through +%\alert{pipage rounding} [Ageev and Sviridenko 2004].\\ +\item<4->$F(\lambda^*)$ is monotone in $c$. +\end{itemize}} +\medskip +\visible<5->{Good relaxation candidate, if it can be computed in poly-time.} +\visible<6->{\vspace*{-0.3cm} +\begin{center} +\begin{tabular}{lc} + \textsc{Knapsack} &\Checkmark +\end{tabular}\qquad +\begin{tabular}{lc} + \textsc{Coverage} &\XSolidBrush\\ + EDP &\XSolidBrush +\end{tabular} +\end{center} +} +\end{frame} + + +\begin{frame}{Main Technical Contribution: Relaxation for EDP} +\alt<1>{\begin{block}{\textsc{EDP} } +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &V(S) = \log \det (I+\sum_{i\in S}x_ix_i^T) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}c_i\leq B +\end{align*} +\end{block} +} +{ +\begin{block}{Convex Relaxation} +\vspace*{-0.4cm} +\begin{align*} + \text{Maximize}\qquad &L(\lambda) = \log \det (I+\sum_{i\in [N]}\lambda_ix_ix_i^T) \\ + \text{subj. to}\qquad &\textstyle\sum_{i\in S}\lambda_ic_i\leq B, \lambda_i\in [0,1] +\end{align*} +\end{block} +} +\pause +\pause +$L(\lambda^*)$ is: + \begin{itemize} + \item Monotone in $c$ +\pause + \item Poly-time: $L$ is convex and self-concordant (Boyd\&Vanderberghe) + \pause + % \vspace{0.5cm} + \item Close to $OPT$:\pause + % \vspace{0.5cm} + \begin{block}{Technical Lemma} + \begin{displaymath} + OPT\leq L(\lambda^*) \leq 2 OPT + 2V(\{i^*\}) + \end{displaymath} + \end{block} + \end{itemize} +% \pause +% Proved by showing that $L(\lambda)\leq 2 F(\lambda)$, where $F$ the multilinear relaxation of $V$. %using \emph{pipage rounding} [Ageev and Sviridenko 2004] +\end{frame} + +\begin{frame}{Proof Steps} + \begin{block}{Technical Lemma} + \begin{displaymath} + OPT\leq L(\lambda^*) \leq 2 OPT + 2V(\{i^*\}) + \end{displaymath} + \end{block} +\uncover<2->{For all $\lambda\in [0,1]^N$, we show that $L(\lambda) \leq 2F(\lambda)$, where $F$ the multi-linear relaxation of $V$.\\ +\bigskip} +\uncover<3->{ +We show this by establishing first that $\frac{\partial F/\partial \lambda_i}{\partial L/\partial \lambda_i}\geq \frac{1}{2}$, and arguing about the minima of $\frac{F(\lambda)}{L(\lambda)}$ over the simplex.\\ +\bigskip +} +\uncover<4>{Finally, we show that $F(\lambda^*)\leq OPT+V(\{i^*\})$ through pipage rounding.} +\end{frame} +\begin{comment} + \vspace{0.5cm} + \pause + + \begin{columns}[c] + \begin{column}{0.53\textwidth} + \alert{Solution:} Replace $V(OPT_{-i^*})$ with \alert<7>{$L^*$}: + \pause + \begin{itemize} + \item computable in polynomial time + \pause + \item close to $V(OPT_{-i^*})$ + \end{itemize} + \end{column} + \pause + \begin{column}{0.45\textwidth} + \begin{itemize} + \item \textsc{Knapsack} (Chen et al., 2011) + \item \textsc{Coverage} (Singer, 2012) + \end{itemize} + \end{column} + \end{columns} +\end{frame} +\begin{frame}{Sketch of proof (2)} + \begin{displaymath} + L^* = \arg\max_{\lambda\in [0,1]^n} \left\{\log\det\left(I_d + \sum_i \lambda_i x_i x_i^T\right)\mid \sum_{i=1}^n\lambda_i c_i\leq B\right\} + \end{displaymath} + \vspace{1cm} + \begin{itemize} + \item polynomial time?\pause{} convex optimization problem + \pause + \vspace{0.5cm} + \item close to $V(OPT_{-i^*})$?\pause + \vspace{0.5cm} + \begin{block}{Technical lemma} + \begin{displaymath} + L^* \leq 2 V(OPT) + V(\{i^*\}) + \end{displaymath} + \end{block} + \end{itemize} +\end{frame} +\end{comment} + +\section{Generalization} + +\begin{frame}{Outline} + \tableofcontents[currentsection] +\end{frame} + +\begin{frame}{Towards More General ML Tasks} + \begin{center} + \includegraphics<1>[scale=0.4]{st2.pdf} + \includegraphics<2>[scale=0.4]{st3.pdf} + \includegraphics<3>[scale=0.4]{st4.pdf} + \includegraphics<4-5>[scale=0.4]{st25.pdf} + \includegraphics<6->[scale=0.4]{st26.pdf} + \end{center} + + \begin{overprint} + \onslide<1> + \begin{center}$N$ experiment subjects\end{center} + \onslide<2> + \begin{center} + $x_i\in \Omega$: public features + \end{center} + \onslide<3> + \begin{center} + $y_i\in \reals$: private data + \end{center} + \onslide<4-5> + \begin{center} + \textbf{Hypothesis.} There exists $h:\Omega\to \reals$ s.t. + % \begin{displaymath} + $y_i = h(x_i) + \varepsilon_i,$ %\quad + where $\varepsilon_i$ are independent. + \visible<5>{Examples: Logistic Regression, LDA, SVMs, \etc} + % \end{displaymath} + \end{center} +%$$y_i = \beta^Tx_i + \varepsilon_i, i=1,\ldots, N$$ + %\end{center} + \onslide<6> + \begin{center} + Experimenter {\tt E} wishes to learn $h$, and has a prior distribution over $$\mathcal{H}=\{\text{mappings from }\Omega\text{ to }\reals\}.$$ + \end{center} + \onslide<7->\begin{center} +\vspace*{-0.5cm} +% \begin{block} +%{Value function: Information gain} + \begin{displaymath} + V(S) = H(h) - H(h\mid y_i,i\in S),\quad S\subseteq[N] + \end{displaymath} + % \end{block} + \visible<8>{$V$ is submodular! [Krause and Guestrin 2009]} + \end{center} + \end{overprint} + +\end{frame} + +\begin{comment} + \begin{itemize} + \item Generative model: $y_i = f(x_i) + \varepsilon_i,\;i\in\mathcal{A}$ + \pause + \item prior knowledge of the experimenter: $f$ is a \alert{random variable} + \pause + \item \alert{uncertainty} of the experimenter: entropy $H(f)$ + \pause + \item after observing $\{y_i,\; i\in S\}$, uncertainty: $H(f\mid S)$ + \end{itemize} + + \pause + \vspace{0.5cm} + + \begin{block}{Value function: Information gain} + \begin{displaymath} + V(S) = H(f) - H(f\mid S),\quad S\subset\mathcal{A} + \end{displaymath} + \end{block} + + \pause + \vspace{0.5cm} + + $V$ is \alert{submodular} $\Rightarrow$ randomized budget feasible mechanism +\end{frame} + +\end{comment} + +\begin{frame}{Conclusion} + \begin{itemize} + \item Experimental design + Budget Feasible Mechanisms + \vspace{1cm} + \pause + \item Deterministic mechanism for other ML Tasks? General submodular functions? + \vspace{1cm} + \pause + \item Approximation ratio $\simeq \alert{13}$. Lower bound: \alert{$2$} + \end{itemize} +\end{frame} +\begin{frame}{} +\vspace{\stretch{1}} +\begin{center} +{\Huge Thank you!} +\end{center} +\vspace{\stretch{1}} +\end{frame} + +\begin{frame}{Non-Homotropic Prior} +Recall that: +\begin{align*} +V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\ +& = \frac{1}{2}\log\det (R^{-1}+\sum_{i\in S}x_ix_i^T) +\end{align*} +What if $R\neq I$? +\begin{theorem} + There exists a truthful, poly-time, and budget feasible mechanism for the objective + function $V$ above. Furthermore, + the algorithm computes a set $S^*$ such that: + \begin{displaymath} + OPT \leq + \frac{5e-1}{e-1}\frac{2}{\mu\log(1+1/\mu)}V(S^*) + 5.1 +\end{displaymath} +where $\mu$ is the largest eigenvalue of $R$. +\end{theorem} +\end{frame} + +\end{document} + + diff --git a/slides/beamerbfootertechnicolor.png b/slides/beamerbfootertechnicolor.png new file mode 100644 index 0000000..3fead01 Binary files /dev/null and b/slides/beamerbfootertechnicolor.png differ diff --git a/slides/beamerblogotechnicolor.png b/slides/beamerblogotechnicolor.png new file mode 100644 index 0000000..e11f0d3 Binary files /dev/null and b/slides/beamerblogotechnicolor.png differ diff --git a/slides/beamercolorthemetechnicolor.sty b/slides/beamercolorthemetechnicolor.sty new file mode 100644 index 0000000..3563bee --- /dev/null +++ b/slides/beamercolorthemetechnicolor.sty @@ -0,0 +1,65 @@ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -*- Mode: Latex -*- %%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% beamercolorthemetechnicolor.sty --- +%% Author : Marc Joye +%% Last Modified On: Sun Jul 24 22:50:08 2011 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\newif\ifmj@black\mj@blackfalse +\ifx\undefined\mj@blackcolor\else + \csname mj@black\mj@blackcolor\endcsname +\fi +\DeclareOptionBeamer{black}[true]{\csname mj@black#1\endcsname} +\newif\ifmj@boxes\mj@boxesfalse +\ifx\undefined\mj@boxescolor\else + \csname mj@boxes\mj@boxescolor\endcsname +\fi +\DeclareOptionBeamer{boxes}[true]{\csname mj@boxes#1\endcsname} +\ProcessOptionsBeamer + +% Cf. +\definecolor{Gray}{RGB}{108,109,112} +\definecolor{Gray10}{RGB}{93,93,96} % PMS Cool gray 10 +\definecolor{Gray8}{RGB}{124,123,126} % PMS Cool gray 8 +\definecolor{Gray6}{RGB}{157,156,157} % PMS Cool gray 6 +\definecolor{Gray4}{RGB}{177,175,174} % PMS Cool gray 4 +\definecolor{Gray2}{RGB}{203,201,198} % PMS Cool gray 2 +\definecolor{Violet}{RGB}{211,107,198} % PMS 252 +\definecolor{MediumViolet}{RGB}{119,45,107} % PMS 255 +\definecolor{Olive}{RGB}{186,216,10} % PMS 382 +\definecolor{MediumOlive}{RGB}{112,112,20} % PMS 385 + + +\mode + +\setbeamercolor{titlegraphic}{bg=Gray,fg=white} +\setbeamercolor{footline}{fg=Gray} +\setbeamercolor{separation line}{fg=Gray,bg=black} +\setbeamercolor{subtitle}{fg=Gray} + +\setbeamercolor{item}{fg=structure.fg} +\setbeamercolor{sidebar left}{use=structure,bg=structure.fg!10} +\setbeamercolor{itemize subitem}{fg=Gray8} +\setbeamercolor{itemize subsubitem}{fg=Gray4} + +\ifmj@black + \setbeamercolor*{normal text}{fg=white,bg=black} + \setbeamercolor*{structure}{fg=white} + %\setbeamercolor*{background canvas}{bg=black} +\else + \setbeamercolor*{normal text}{fg=black,bg=white} + \setbeamercolor*{structure}{fg=black} +\fi + +\ifmj@boxes + \setbeamercolor{block title}{use=normal text,fg=normal text.bg,bg=normal text.fg!75!normal text.fg} + \setbeamercolor{block title alerted}{use={normal text,alerted text},fg=normal text.bg,bg=alerted text.fg!75!normal text.fg} + \setbeamercolor{block title example}{use={normal text,example text},fg=normal text.bg,bg=example text.fg!75!normal text.fg} + \setbeamercolor{block body}{parent=normal text,use=block title,bg=block title.bg!15!bg} + \setbeamercolor{block body alerted}{parent=normal text,use=block title alerted,bg=block title alerted.bg!15!bg} + \setbeamercolor{block body example}{parent=normal text,use=block title example,bg=block title example.bg!15!bg} + \setbeamertemplate{blocks}[default] +\fi + + + +\mode diff --git a/slides/beamerfontthemetechnicolor.sty b/slides/beamerfontthemetechnicolor.sty new file mode 100644 index 0000000..e7b4f73 --- /dev/null +++ b/slides/beamerfontthemetechnicolor.sty @@ -0,0 +1,34 @@ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -*- Mode: Latex -*- %%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% beamerfontthemetechnicolor.sty --- +%% Author : Marc Joye +%% Last Modified On: Tue Jul 26 17:25:08 2011 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\newif\ifmj@trebuchet\mj@trebuchetfalse +\ifx\undefined\mj@trebuchetfont\else + \csname mj@trebuchet\mj@trebuchetfont\endcsname +\fi +\DeclareOptionBeamer{trebuchet}[true]{\csname mj@trebuchet#1\endcsname} +\ProcessOptionsBeamer + +% Better than default police but should be updated with Trebuchet-MS. +% See file beamerthemetechnicolor.sty +\RequirePackage[T1]{fontenc} +\RequirePackage{helvet} + +\ifmj@trebuchet\renewcommand{\sfdefault}{trebuchet}\fi + + +\mode + +\setbeamerfont{structure}{series=\bfseries} +\setbeamerfont{title}{size=\Large,series=\mdseries} +\setbeamerfont{author}{size=\footnotesize,series=\mdseries} +\setbeamerfont{part name}{size=\Large,series=\mdseries} +\setbeamerfont{part title}{size=\large,series=\mdseries} +\setbeamerfont{frametitle}{size=\Large,series=\mdseries} +%\setbeamerfont{section in toc}{series=\mdseries} +\setbeamerfont{block title}{size={}} + + +\mode \ No newline at end of file diff --git a/slides/beamerfootertechnicolor.png b/slides/beamerfootertechnicolor.png new file mode 100644 index 0000000..dfe0c39 Binary files /dev/null and b/slides/beamerfootertechnicolor.png differ diff --git a/slides/beamerinnerthemetechnicolor.sty b/slides/beamerinnerthemetechnicolor.sty new file mode 100644 index 0000000..2825963 --- /dev/null +++ b/slides/beamerinnerthemetechnicolor.sty @@ -0,0 +1,276 @@ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -*- Mode: Latex -*- %%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% beamerinnerthemetechnicolor.sty --- +%% Author : Marc Joye +%% Last Modified On: Fri Oct 21 13:17:42 2011 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\newif\ifmj@black\mj@blackfalse +\ifx\undefined\mj@blackcolor\else + \csname mj@black\mj@blackcolor\endcsname +\fi +\newif\ifmj@firsttitlepage\mj@firsttitlepagetrue + +\mode + +%-------------------------------------------------------------------- +%--- General default settings +%-------------------------------------------------------------------- +\setbeamertemplate{sections/subsections in toc}[square] +\setbeamertemplate{items}[square] + +% Technicolor images +\ifmj@black + \pgfdeclareimage[width=\paperwidth]{footertechnicolor}{beamerbfootertechnicolor.png} + \pgfdeclareimage[width=87.5pt]{flogotechnicolor}{beamerblogotechnicolor.png} + \pgfdeclareimage[width=59.5pt]{logotechnicolor}{beamerblogotechnicolor.png} +\else + \pgfdeclareimage[width=\paperwidth]{footertechnicolor}{beamerfootertechnicolor.png} + \pgfdeclareimage[width=87.5pt]{flogotechnicolor}{beamerlogotechnicolor.png} + \pgfdeclareimage[width=59.5pt]{logotechnicolor}{beamerlogotechnicolor.png} +\fi + +% Use Technicolor logo +\logo{\pgfuseimage{logotechnicolor}} + +% Use default sample image for title page +\def\mj@titlegraphicprefix{beamersampletechnicolor} +\def\mj@titlegraphicimage{\mj@titlegraphicprefix11} +\def\mj@titlegraphicoptions{\@empty} +\long\def\titlegraphic{\@ifstar{\mj@titlegraphics}{\mj@titlegraphic}} +\def\mj@titlegraphic{\@ifnextchar [{\mj@@titlegraphic}{\mj@@titlegraphic[]}} +\def\mj@titlegraphics{\@ifnextchar [{\mj@@titlegraphics}{\mj@@titlegraphics[]}} +\def\mj@@titlegraphic[#1]#2{% + \gdef\mj@titlegraphicoptions{#1} + \gdef\mj@titlegraphicimage{#2}} +\def\mj@@titlegraphics[#1]#2{% + \gdef\mj@titlegraphicoptions{#1} + \ifnum#2>0 + \gdef\mj@titlegraphicimage{\mj@titlegraphicprefix#2}\fi} +\newlength{\mj@titlegraphicheight} +\setlength{\mj@titlegraphicheight}{.458\paperheight} +\renewcommand{\inserttitlegraphic}{% + \includegraphics[width=\paperwidth,height=\mj@titlegraphicheight,\mj@titlegraphicoptions]{\mj@titlegraphicimage}} + + +%-------------------------------------------------------------------- +%--- Blocks +%-------------------------------------------------------------------- +\defbeamertemplateparent{blocks}[technicolor]{block begin,block end,% + block alerted begin,block alerted end,% + block example begin,block example end} +{} + +% Correct default block template when block title is empty +% Default block +\defbeamertemplate{block begin}{technicolor} +{ + \par\vskip\medskipamount% + \ifx\@empty\insertblocktitle\else% + \begin{beamercolorbox}[colsep*=.75ex]{block title} + {\usebeamerfont*{block title}\insertblocktitle}% + \end{beamercolorbox}% + {\parskip0pt\par}% + \ifbeamercolorempty[bg]{block title} + {} + {\ifbeamercolorempty[bg]{block body}{}{\nointerlineskip\vskip-0.5pt}}% + \fi + \usebeamerfont{block body}% + \begin{beamercolorbox}[colsep*=.75ex,vmode]{block body} + \ifbeamercolorempty[bg]{block body}{\vskip-.25ex}{\vskip-.75ex}\vbox{}% +} +\defbeamertemplate{block end}{technicolor}% +{\end{beamercolorbox}\vskip\smallskipamount} + +% Alerted block +\defbeamertemplate{block alerted begin}{technicolor} +{ + \par\vskip\medskipamount% + \ifx\@empty\insertblocktitle\else% + \begin{beamercolorbox}[colsep*=.75ex]{block title alerted} + {\usebeamerfont*{block title alerted}\insertblocktitle}% + \end{beamercolorbox}% + {\parskip0pt\par}% + \ifbeamercolorempty[bg]{block title alerted} + {} + {\ifbeamercolorempty[bg]{block body alerted}{}{\nointerlineskip\vskip-0.5pt}}% + \fi + \usebeamerfont{block body alerted}% + \begin{beamercolorbox}[colsep*=.75ex,vmode]{block body alerted} + \ifbeamercolorempty[bg]{block body alerted}{\vskip-.25ex}{\vskip-.75ex}\vbox{}% +} +\defbeamertemplate{block alerted end}{technicolor}% +{\end{beamercolorbox}\vskip\smallskipamount} + +% Example block +\defbeamertemplate{block example begin}{technicolor} +{ + \par\vskip\medskipamount% + \ifx\@empty\insertblocktitle\else% + \begin{beamercolorbox}[colsep*=.75ex]{block title example} + {\usebeamerfont*{block title example}\insertblocktitle}% + \end{beamercolorbox}% + {\parskip0pt\par}% + \ifbeamercolorempty[bg]{block title example} + {} + {\ifbeamercolorempty[bg]{block body example}{}{\nointerlineskip\vskip-0.5pt}}% + \fi + \usebeamerfont{block body example}% + \begin{beamercolorbox}[colsep*=.75ex,vmode]{block body example} + \ifbeamercolorempty[bg]{block body example}{\vskip-.25ex}{\vskip-.75ex}\vbox{}% +} +\defbeamertemplate{block example end}{technicolor}% +{\end{beamercolorbox}\vskip\smallskipamount} + +\setbeamertemplate{blocks}[technicolor] + + +%-------------------------------------------------------------------- +%--- Part page +%-------------------------------------------------------------------- +\defbeamertemplate*{part page}{technicolor}[1][]{% + \thispagestyle{empty}% + %Dimension \beamer@tempdim is used to remove the (left) sidebar on part pages + %when outer theme sidebar is used. + \beamer@tempdim=\z@% + \ifx\undefined\beamer@sidebarwidth\else% + \ifx\beamer@sidebarside\beamer@lefttext% + \advance\beamer@tempdim by \beamer@sidebarwidth% + \fi% + \addtolength{\textwidth}{\beamer@tempdim}% + \fi% + \vbox to\z@{\vspace*{25pt}\vss}% + \vskip.17\paperheight% + \vbox to16pt{\hskip-\beamer@tempdim% + \begin{beamercolorbox}[ht=.17\paperheight,wd=\paperwidth,center,sep=\z@,dp=\z@]{separation line}% + \mbox{}% + \end{beamercolorbox}\vss}% + \vbox to.75\mj@titlegraphicheight{\hskip-\beamer@tempdim% + \begin{beamercolorbox}[wd=\paperwidth,ht=\mj@titlegraphicheight,dp=\z@,sep=\z@]{titlegraphic}% + \vspace*{12pt}% + \begin{beamercolorbox}[sep=8pt,ht=5.5ex,dp=1ex,right,rightskip=-.5\beamer@rightmargin]{titlegraphic} + {\usebeamerfont{part name}\partname~\insertromanpartnumber}% + \end{beamercolorbox} + \vbox to\z@{\vspace*{-12pt}% + \begin{beamercolorbox}[sep=4mm,wd=\paperwidth,ht=2.25ex,dp=1ex,right]{title} + \usebeamerfont{part title}\usebeamercolor[fg]{titlegraphic}\insertpart\par + \end{beamercolorbox}\vss}\vskip.162\paperheight + \end{beamercolorbox}\vss}% + \vbox to\z@{\hskip-\beamer@tempdim% + \begin{beamercolorbox}[wd=\paperwidth,dp=\z@,center,sep=\z@]{}% + \pgfuseimage{footertechnicolor}% + \end{beamercolorbox}\vss}% + % + \vskip.08\paperheight + \vbox to\z@{% + \hbox{\hskip\paperwidth\hskip-\beamer@tempdim\hskip-115pt\pgfuseimage{flogotechnicolor}}\vss}} + +\setbeamertemplate{part page}[technicolor] + + +%-------------------------------------------------------------------- +%--- Title page +%-------------------------------------------------------------------- +% Page style "empty" with navigation symbols removed +\def\ps@mj@empty{% + \let\@mkboth\@gobbletwo% + \def\@oddhead{\begingroup% + \setbox\beamer@tempbox=\hbox{\usebeamertemplate***{background canvas}\hyper@pagetransition\hyper@pageduration}% + \beamer@tempdim=\ht\beamer@tempbox% + \setbox\beamer@tempbox=\hbox{\lower\beamer@tempdim\hbox{\box\beamer@tempbox}}% + \wd\beamer@tempbox=0pt\ht\beamer@tempbox=0pt\dp\beamer@tempbox=0pt% + \setbox\@tempboxa=\hbox{\usebeamertemplate***{background}}% + \beamer@tempdim=\ht\@tempboxa% + \setbox\@tempboxa=\hbox{\lower\beamer@tempdim\hbox{\box\@tempboxa}}% + \wd\@tempboxa=0pt\ht\@tempboxa=0pt\dp\@tempboxa=0pt% + \vbox{\hbox{\hskip-\Gm@lmargin\raise\headheight\box\beamer@tempbox\box\@tempboxa}\hfil}% + \endgroup} + \def\@oddfoot{} + \let\@evenhead\@oddhead + \let\@evenfoot\@oddfoot} + +\defbeamertemplate*{title page}{technicolor}[1][]{% + \thispagestyle{mj@empty}% + \beamer@plainframetrue% + \beamer@tempdim=\z@% + \ifx\undefined\beamer@sidebarwidth\else% + \ifx\beamer@sidebarside\beamer@lefttext\advance\beamer@tempdim by \beamer@sidebarwidth\fi% + \addtolength{\textwidth}{\beamer@tempdim}% + \fi% + \setbox\beamer@tempbox=\hbox{{\usebeamerfont{title}\inserttitle}}% + \beamer@dima=\wd\beamer@tempbox\advance\beamer@dima8pt + \vbox to\z@{\vspace*{25pt}\hskip-\beamer@tempdim% + \ifmj@firsttitlepage% + \ifx\@empty\insertsubtitle\ifdim\beamer@dima>\hsize\vskip\z@\fi\fi% + \vbox to\z@{\vss% + \begin{beamercolorbox}[sep=8pt,ht=5.5ex,dp=1ex,right,rightskip=-.5\beamer@rightmargin]{title} + \usebeamerfont{title}\inserttitle%MJ + \end{beamercolorbox}} + \ifx\@empty\insertsubtitle\else% + \vskip-1ex% + \vbox to\z@{\hskip-\beamer@tempdim% + \begin{beamercolorbox}[sep=8pt,ht=2.25ex,dp=1ex,right,rightskip=-.5\beamer@rightmargin]{title} + \usebeamerfont{subtitle}\usebeamercolor[fg]{subtitle}\insertsubtitle + \end{beamercolorbox}\vss} + \fi% + \fi% + \vss}% + \vskip.17\paperheight% + \vbox to16pt{\hskip-\beamer@tempdim% + \begin{beamercolorbox}[ht=.17\paperheight,wd=\paperwidth,sep=\z@,dp=\z@]{separation line}% + \mbox{}% + \end{beamercolorbox}\vss}% + \vbox to.75\mj@titlegraphicheight{\hskip-\beamer@tempdim% + \begin{beamercolorbox}[wd=\paperwidth,ht=\mj@titlegraphicheight,dp=\z@,left,sep=\z@]{titlegraphic}% + \ifmj@firsttitlepage% + \inserttitlegraphic% + \else + \vbox to\z@{\vss% + \begin{beamercolorbox}[sep=8pt,ht=5.5ex,dp=1ex,right,rightskip=-1.5\beamer@rightmargin]{titlegraphic} + \usebeamerfont{title}\inserttitle + \end{beamercolorbox}}% + \vskip.041\paperheight% + \vbox to\z@{\vss% + \begin{beamercolorbox}[sep=8pt,ht=2.25ex,dp=1ex,right,rightskip=-1.5\beamer@rightmargin]{title} + \ifx\@empty\insertsubtitle\else% + \usebeamerfont{subtitle}\usebeamercolor[fg]{titlegraphic}\insertsubtitle% + \fi + \end{beamercolorbox}}\vskip.162\paperheight + \fi + \end{beamercolorbox}\vss}% + \vbox to\z@{\hskip-\beamer@tempdim% + \begin{beamercolorbox}[wd=\paperwidth,dp=\z@,center,sep=\z@]{}% + \pgfuseimage{footertechnicolor}% + \end{beamercolorbox}\vss}% + % + \vskip.08\paperheight + \vbox to\z@{% + \hbox{\hskip\paperwidth\hskip-\beamer@tempdim\hskip-115pt\pgfuseimage{flogotechnicolor}}\vss}% + \vbox to\z@{\hskip-\beamer@tempdim% + \begin{beamercolorbox}[sep=8pt,left,wd=.7\paperwidth]{author} + \ifx\@empty\insertauthor\else% + \def\beamer@andtitle{\ \raisebox{1.5pt}{$\centerdot$}\enspace\ } + \usebeamerfont{author}\insertauthor + \fi + \end{beamercolorbox}\vss}} + +\setbeamertemplate{title page}[technicolor] + + +%-------------------------------------------------------------------- +%--- Frame title +%-------------------------------------------------------------------- +\setbeamertemplate{frametitle}{% + \beamer@tempdim=\paperwidth + \advance\beamer@tempdim by -\beamer@leftsidebar% + \advance\beamer@tempdim by -\beamer@rightsidebar% + \begin{beamercolorbox}[wd=\beamer@tempdim,ht=2.4ex,dp=1ex,leftskip=\beamer@leftmargin]{frametitle}% + \usebeamercolor{frametitle}\usebeamerfont{frametitle}\insertframetitle + \end{beamercolorbox} + \nointerlineskip\vskip.2ex + + \advance\beamer@tempdim by -\beamer@leftmargin% + \advance\beamer@tempdim by -7pt% + \hbox to\beamer@tempdim{\usebeamercolor[fg]{separation line}{\rule{\beamer@tempdim}{.67pt}}}} + + +\mode diff --git a/slides/beamerlogotechnicolor.png b/slides/beamerlogotechnicolor.png new file mode 100644 index 0000000..1778f47 Binary files /dev/null and b/slides/beamerlogotechnicolor.png differ diff --git a/slides/beamerouterthemetechnicolor.sty b/slides/beamerouterthemetechnicolor.sty new file mode 100644 index 0000000..bd6fbf9 --- /dev/null +++ b/slides/beamerouterthemetechnicolor.sty @@ -0,0 +1,58 @@ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -*- Mode: Latex -*- %%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% beamerouterthemetechnicolor.sty --- +%% Author : Marc Joye +%% Last Modified On: Sun Jul 24 22:32:14 2011 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\newif\ifmj@numbering\mj@numberingfalse +\ifx\undefined\mj@numberingouter\else + \csname mj@numbering\mj@numberingouter\endcsname +\fi +\DeclareOptionBeamer{numbering}[true]{\csname mj@numbering#1\endcsname} +\ProcessOptionsBeamer + + +\mode + +%-------------------------------------------------------------------- +%--- Navigation symbols +%-------------------------------------------------------------------- +\setbeamertemplate{navigation symbols}[only frame symbol] +% No navigation symbols in handout or trans mode +\only{\setbeamertemplate{navigation symbols}{}} + + +%-------------------------------------------------------------------- +%--- Headline and footline +%-------------------------------------------------------------------- +% Slide number as default cartouche +\def\mj@cartouche{% + %\newcommand*\handoutname{handout} + \hskip3em\ifmj@numbering\llap{\insertframenumber{}\,/\,\inserttotalframenumber}\fi\quad% + %\ifx\beamer@currentmode\handoutname\else + \usebeamertemplate***{navigation symbols} + %\fi% + \hskip4.5em\rlap{\insertdate}} + +\defbeamertemplate*{headline}{technicolor theme}{} +\defbeamertemplate*{footline}{technicolor theme}{% + \vbox to\z@{\vss% + \beamer@tempdim=\paperwidth + \advance\beamer@tempdim by -\beamer@leftmargin + \advance\beamer@tempdim by -73pt %59.5 + 7 + 13.5 + \hskip\beamer@leftmargin% + \vbox to\z@{\vskip1pt% + \begin{beamercolorbox}[wd=\beamer@tempdim,ht=2.25ex,dp=1ex]{structure} + \Tiny\mj@cartouche + \end{beamercolorbox}\vss}\par + \hskip\beamer@leftmargin% + \hbox to\beamer@tempdim{\usebeamercolor[fg]{footline}{\rule{\beamer@tempdim}{.67pt}}}% + \vskip13.4pt}} + +\defbeamertemplate*{sidebar right}{technicolor theme}{% + \vfill% + \llap{\insertlogo\hskip7pt}% + \vskip5pt} + + +\mode \ No newline at end of file diff --git a/slides/beamersampletechnicolor1.jpg b/slides/beamersampletechnicolor1.jpg new file mode 100644 index 0000000..cd2a24c Binary files /dev/null and b/slides/beamersampletechnicolor1.jpg differ diff --git a/slides/beamersampletechnicolor10.jpg b/slides/beamersampletechnicolor10.jpg new file mode 100644 index 0000000..084ffe7 Binary files /dev/null and b/slides/beamersampletechnicolor10.jpg differ diff --git a/slides/beamersampletechnicolor11.jpg b/slides/beamersampletechnicolor11.jpg new file mode 100644 index 0000000..8b0b082 Binary files /dev/null and b/slides/beamersampletechnicolor11.jpg differ diff --git a/slides/beamersampletechnicolor12.jpg b/slides/beamersampletechnicolor12.jpg new file mode 100644 index 0000000..593f420 Binary files /dev/null and b/slides/beamersampletechnicolor12.jpg differ diff --git a/slides/beamersampletechnicolor13.jpg b/slides/beamersampletechnicolor13.jpg new file mode 100644 index 0000000..1f78e8f Binary files /dev/null and b/slides/beamersampletechnicolor13.jpg differ diff --git a/slides/beamersampletechnicolor14.jpg b/slides/beamersampletechnicolor14.jpg new file mode 100644 index 0000000..28dae0c Binary files /dev/null and b/slides/beamersampletechnicolor14.jpg differ diff --git a/slides/beamersampletechnicolor15.jpg b/slides/beamersampletechnicolor15.jpg new file mode 100644 index 0000000..be6aece Binary files /dev/null and b/slides/beamersampletechnicolor15.jpg differ diff --git a/slides/beamersampletechnicolor16.jpg b/slides/beamersampletechnicolor16.jpg new file mode 100644 index 0000000..0617bdf Binary files /dev/null and b/slides/beamersampletechnicolor16.jpg differ diff --git a/slides/beamersampletechnicolor17.jpg b/slides/beamersampletechnicolor17.jpg new file mode 100644 index 0000000..1c9a476 Binary files /dev/null and b/slides/beamersampletechnicolor17.jpg differ diff --git a/slides/beamersampletechnicolor2.jpg b/slides/beamersampletechnicolor2.jpg new file mode 100644 index 0000000..159435c Binary files /dev/null and b/slides/beamersampletechnicolor2.jpg differ diff --git a/slides/beamersampletechnicolor3.jpg b/slides/beamersampletechnicolor3.jpg new file mode 100644 index 0000000..e8ad0a0 Binary files /dev/null and b/slides/beamersampletechnicolor3.jpg differ diff --git a/slides/beamersampletechnicolor4.jpg b/slides/beamersampletechnicolor4.jpg new file mode 100644 index 0000000..8aa0e9c Binary files /dev/null and b/slides/beamersampletechnicolor4.jpg differ diff --git a/slides/beamersampletechnicolor5.jpg b/slides/beamersampletechnicolor5.jpg new file mode 100644 index 0000000..fea726f Binary files /dev/null and b/slides/beamersampletechnicolor5.jpg differ diff --git a/slides/beamersampletechnicolor6.jpg b/slides/beamersampletechnicolor6.jpg new file mode 100644 index 0000000..fc63f2f Binary files /dev/null and b/slides/beamersampletechnicolor6.jpg differ diff --git a/slides/beamersampletechnicolor7.jpg b/slides/beamersampletechnicolor7.jpg new file mode 100644 index 0000000..3d7a161 Binary files /dev/null and b/slides/beamersampletechnicolor7.jpg differ diff --git a/slides/beamersampletechnicolor8.jpg b/slides/beamersampletechnicolor8.jpg new file mode 100644 index 0000000..d0d1418 Binary files /dev/null and b/slides/beamersampletechnicolor8.jpg differ diff --git a/slides/beamersampletechnicolor9.jpg b/slides/beamersampletechnicolor9.jpg new file mode 100644 index 0000000..ce30db4 Binary files /dev/null and b/slides/beamersampletechnicolor9.jpg differ diff --git a/slides/beamerthemetechnicolor.sty b/slides/beamerthemetechnicolor.sty new file mode 100644 index 0000000..de10ffc --- /dev/null +++ b/slides/beamerthemetechnicolor.sty @@ -0,0 +1,192 @@ +\def\fileversion{0.9} +%\def\filedate{2010/03/02} +\def\filedate{2011/10/21} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% +% BEAMER Technicolor Theme +% +%----------------------------------------------------------------------------- +% Author: Marc Joye +% Address: Technicolor, Security & Content Protection Labs +% 1 avenue de Belle Fontaine +% 35576 Cesson-Sévigné Cedex, France +% E-mail: marc.joye@technicolor.com +% URL: http://www.thlab.net/~joyem/ +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%% TO DO: Default use of Trebuchet-MS font. Meanwhile, if you are +%%% using MikTeX 2.4 (or higher), you can install the winfonts package +%%% as described at URL +%%% . The +%%% Trebuchet-MS font can then be used by adding the line +%%% \renewcommand{\sfdefault}{trebuchet} in the preamble of your +%%% document. Yet another way is to add the option "trebuchet" when +%%% using the technicolor theme, \usetheme[trebuchet]{technicolor}. + +\NeedsTeXFormat{LaTeX2e} +\typeout{^^J *** Technicolor Presentation v\fileversion\space for Beamer + LaTeX2e - Marc Joye ***^^J} + +\ProvidesPackage{beamerthemetechnicolor}[\filedate] +\PassOptionsToPackage{pdfpagemode=FullScreen}{hyperref} + +\newif\ifmj@black +\newif\ifmj@boxes +\newif\ifmj@numbering +\newif\ifmj@outline +\newif\ifmj@trebuchet +\newif\ifmj@outlinefp\mj@outlinefpfalse +\newif\ifmj@showsecondtp\mj@showsecondtptrue +\DeclareOptionBeamer{black}[true]{\csname mj@black#1\endcsname% + \def\mj@blackcolor{#1}} +\DeclareOptionBeamer{boxes}[true]{\csname mj@boxes#1\endcsname% + \def\mj@boxescolor{#1}} +\DeclareOptionBeamer{numbering}[true]{\csname mj@numbering#1\endcsname% + \def\mj@numberingouter{#1}} +\DeclareOptionBeamer{outline}[true]{\csname mj@outline#1\endcsname% + \csname mj@outlinefp#1\endcsname} +\DeclareOptionBeamer{outline*}[true]{\csname mj@outline#1\endcsname} +\DeclareOptionBeamer{trebuchet}[true]{\csname mj@trebuchet#1\endcsname% + \def\mj@trebuchetfont{#1}} +\DeclareOptionBeamer{secondtitlepage}[true]{\csname mj@showsecondtp#1\endcsname} +\ExecuteOptionsBeamer{black=false,boxes=true,numbering=true,outline=false,trebuchet=false,secondtitlepage=true} +\ProcessOptionsBeamer + + +%--- Macros +\newcommand{\cartouche}[1]{\gdef\mj@cartouche{#1}} +\providecommand{\email}[1]{\href{mailto:#1}{#1}} +\newcommand{\absput}[3]{\vbox to\z@{\kern#2\hbox to\z@{\kern#1{#3}\hss}\vss}} +\newcommand{\mj@error}[2]{% + \GenericError{\space \space \space \@spaces \@spaces \@spaces }% + {Technicolor Presentation Error: #1}{See the documentation for explanation.}{#2^^J}} + + +%--- Page settings +\setbeamersize{text margin left=0.51cm} +\setbeamersize{text margin right=0.51cm} +\setbeamercovered{dynamic} +\setlength{\doublerulesep}{.5pt} +\setlength{\arraycolsep}{1.4pt} +\let\le\leqslant +\let\leq\leqslant +\let\ge\geqslant +\let\geq\geqslant + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode + +%-------------------------------------------------------------------- +%--- General settings +%-------------------------------------------------------------------- + +% Frames are top-aligned +\beamer@centeredfalse + +% Start in full-screen mode +\hypersetup{pdfpagemode=FullScreen} + +% Date initialized to null +\date{} + +% Default outline +\ifmj@outline + \AtBeginSection[]% Do nothing for section* + {% + \begingroup + \setbeamertemplate{footline}{} + \addtocounter{framenumber}{-1} + \frame{\transdissolve% + \frametitle{Outline} + \tableofcontents[currentsection]} + \endgroup} +\fi +\AtBeginPart{% + \frame[label=part\thepart,part]{\transdissolve\partpage} + \ifmj@outline + \begin{frame} + \frametitle{Outline of Part \thepart} + \tableofcontents[pausesections] + \end{frame} + \fi} + +% Do not insert the frame number for slides in the appendix +\newcounter{mj@lastframe} +\newif\ifmj@appendix\mj@appendixfalse +\let\mj@appendixbak\appendix +\def\appendix{% + \mj@appendixtrue + \global\setcounter{mj@lastframe}{\insertframenumber}% + \mj@numberingfalse + \mj@appendixbak} +\AtEndDocument{% + \ifmj@appendix\if@filesw% + \immediate\write\@auxout{\string\@writefile{nav}% + {\noexpand\headcommand{% + \noexpand\def\noexpand\inserttotalframenumber{\the\c@mj@lastframe}}}}% + \fi\fi} + + +%-------------------------------------------------------------------- +%--- Layout +%-------------------------------------------------------------------- +\usecolortheme{technicolor} +\usefonttheme{technicolor} +\useoutertheme{technicolor} +\useinnertheme{technicolor} + + +\renewcommand{\titlepage}{% + \ifbeamer@inframe + \mj@error{Bad format}{Macro \noexpand\titlepage should be used + outside a frame environment.} + \else\maketitle\fi} + +\renewcommand{\maketitle}{% + \ifbeamer@inframe + \mj@error{Bad format}{Macro \noexpand\maketitle should be used + outside a frame environment.} + \else + \begingroup + % \frame{\usebeamertemplate{title page}} + \mj@firsttitlepagefalse + \ifmj@showsecondtp + \frame{\usebeamertemplate{title page}} + \addtocounter{framenumber}{-1} + \fi + \endgroup + \ifmj@outlinefp + \frame{\transsplitverticalin% + \frametitle{Outline} + \tableofcontents} + \fi + \fi} + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{% + \RequirePackage{pgfpages} + \pgfpagesuselayout{2 on 1}[a4paper,border shrink=5mm] + + % Remove the bookmarks + \def\@bookmarkopenstatus#1{} + \global\let\ReadBookmarks\relax + \global\let\WriteBookmarks\relax + % Don't use full-screen mode + %\def\@pdfpagemode{/UseNone} + \hypersetup{pdfpagemode=UseNone} + + % No numbering + \mj@numberingfalse +} + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode diff --git a/slides/stg-1.pdf b/slides/stg-1.pdf new file mode 100644 index 0000000..38d5ab0 Binary files /dev/null and b/slides/stg-1.pdf differ diff --git a/slides/stg-1.svg b/slides/stg-1.svg new file mode 100644 index 0000000..c392658 --- /dev/null +++ b/slides/stg-1.svg @@ -0,0 +1,3210 @@ + + + +image/svg+xml + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + + + + + + + + + +data + + + + + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + + +$$ + + + + +$ + + + + +$$$ + + + + +$ + + + + +$$ + + + + +$$$ + + + + +data + +data + +data + +Classification algorithm,Regression model,Recommender engine,etc. + +Data Mining + + \ No newline at end of file diff --git a/slides/stg-2.pdf b/slides/stg-2.pdf new file mode 100644 index 0000000..b4850f9 Binary files /dev/null and b/slides/stg-2.pdf differ diff --git a/slides/stg-2.svg b/slides/stg-2.svg new file mode 100644 index 0000000..5acba58 --- /dev/null +++ b/slides/stg-2.svg @@ -0,0 +1,3171 @@ + + + +image/svg+xml + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +data + + + + + + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + + + +$$ + + + + + +$ + + + + + +$$$ + + + + + +$ + + + + + +$$ + + + + + +$$$ + + + + + +data + + +data + + +data + + + + + + + \ No newline at end of file diff --git a/slides/stg-3.pdf b/slides/stg-3.pdf new file mode 100644 index 0000000..268b0aa Binary files /dev/null and b/slides/stg-3.pdf differ diff --git a/slides/stg-3.svg b/slides/stg-3.svg new file mode 100644 index 0000000..1fc23f1 --- /dev/null +++ b/slides/stg-3.svg @@ -0,0 +1,3065 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +$$ + + + + + + +$ + + + + + + +$$$ + + + + + + +$ + + + + + + +$$ + + + + + + +$$$ + + + + + + +data + + + +data + + + +data + + + + + + + + \ No newline at end of file diff --git a/slides/stg-4.pdf b/slides/stg-4.pdf new file mode 100644 index 0000000..70cab06 Binary files /dev/null and b/slides/stg-4.pdf differ diff --git a/slides/stg-4.svg b/slides/stg-4.svg new file mode 100644 index 0000000..76922e3 --- /dev/null +++ b/slides/stg-4.svg @@ -0,0 +1,3002 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +$$ + + + + +$ + + + + +$$$ + + + + + + + + + + + + + + + + +data + +data + +data + + + + \ No newline at end of file diff --git a/slides/stg-5.pdf b/slides/stg-5.pdf new file mode 100644 index 0000000..9b1d5d5 Binary files /dev/null and b/slides/stg-5.pdf differ diff --git a/slides/stg-5.svg b/slides/stg-5.svg new file mode 100644 index 0000000..5f6d67c --- /dev/null +++ b/slides/stg-5.svg @@ -0,0 +1,3003 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +$$ + + + + + + + +$ + + + + + + + +$$$ + + + + + + + + + + + + + + + + + + + + + + + + + + + + +data + + + + +data + + + + +data + + + + + + + + + \ No newline at end of file diff --git a/slides/stg-6.pdf b/slides/stg-6.pdf new file mode 100644 index 0000000..636bcca Binary files /dev/null and b/slides/stg-6.pdf differ diff --git a/slides/stg-6.svg b/slides/stg-6.svg new file mode 100644 index 0000000..abd7e74 --- /dev/null +++ b/slides/stg-6.svg @@ -0,0 +1,3057 @@ + + + +image/svg+xml + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + + + + + + + + + +data + + + + + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +data + +data + +data + +Classification algorithm,Regression model,Recommender engine,etc. + +Data Mining + + \ No newline at end of file diff --git a/slides/stg-7.pdf b/slides/stg-7.pdf new file mode 100644 index 0000000..a964ac3 Binary files /dev/null and b/slides/stg-7.pdf differ diff --git a/slides/stg-7.svg b/slides/stg-7.svg new file mode 100644 index 0000000..2e70b83 --- /dev/null +++ b/slides/stg-7.svg @@ -0,0 +1,2929 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +data + + + + + +data + + + + + +data + + + + + + + + + + \ No newline at end of file diff --git a/slides/stg-8.pdf b/slides/stg-8.pdf new file mode 100644 index 0000000..b781a27 Binary files /dev/null and b/slides/stg-8.pdf differ diff --git a/slides/stg-8.svg b/slides/stg-8.svg new file mode 100644 index 0000000..f050963 --- /dev/null +++ b/slides/stg-8.svg @@ -0,0 +1,2356 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +data + + + + + + +data + + + + + + +data + + + + + + + + + + + \ No newline at end of file diff --git a/slides/stg-9.pdf b/slides/stg-9.pdf new file mode 100644 index 0000000..e69de29 diff --git a/slides/stg31dd.svg b/slides/stg31dd.svg new file mode 100644 index 0000000..2954fb4 --- /dev/null +++ b/slides/stg31dd.svg @@ -0,0 +1,2824 @@ + + + +image/svg+xml + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +$$ + + + + +$ + + + + +$$$ + + + + + + + + + + + \ No newline at end of file diff --git a/slides/stgall.svg b/slides/stgall.svg new file mode 100644 index 0000000..ee86eb5 --- /dev/null +++ b/slides/stgall.svg @@ -0,0 +1,3232 @@ + + + +image/svg+xml + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + + + + + + + +data + + + + + + + + + + + + +data + + + + + + + + + + + + + + + + + + + +$$ + + + +$ + + + +$$$ + + + +$ + + + +$$ + + + +$$$ + + + +data +data +data +Classification algorithm,Regression model,Recommender engine,etc. +Data Mining + \ No newline at end of file -- cgit v1.2.3-70-g09d2