diff options
| -rw-r--r-- | slides/BudgetFeasibleExperimentalDesignGoogle.tex | 68 |
1 files changed, 46 insertions, 22 deletions
diff --git a/slides/BudgetFeasibleExperimentalDesignGoogle.tex b/slides/BudgetFeasibleExperimentalDesignGoogle.tex index 3fcec7c..2ccb2b4 100644 --- a/slides/BudgetFeasibleExperimentalDesignGoogle.tex +++ b/slides/BudgetFeasibleExperimentalDesignGoogle.tex @@ -38,15 +38,16 @@ \section{Introduction} -\begin{frame}{Motivation: A Data Market} +\begin{frame}{Experimental Design} \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<1>[scale=0.4]{stg-8.pdf} + \includegraphics<2>[scale=0.4]{stg-7.pdf} + \includegraphics<3>[scale=0.4]{stg-6.pdf} + \includegraphics<4>[scale=0.4]{stg-5.pdf} + \includegraphics<5>[scale=0.4]{stg-4.pdf} + \includegraphics<6>[scale=0.4]{stg-3.pdf} + \includegraphics<7>[scale=0.4]{stg-2.pdf} + \includegraphics<8>[scale=0.4]{stg-1.pdf} % \includegraphics<8>[scale=0.4]{st31g.pdf} \end{center} @@ -57,27 +58,35 @@ % \end{center} \end{frame} -\begin{frame}{Challenges} +\begin{frame}{Motivation and Challenges} % \begin{overprint} \begin{itemize} - \item<1-> Value of data? - \visible<3-4>{\begin{itemize} - \item Experimental Design - \end{itemize}} + \item<1-> Applications + \begin{itemize} + \item Medicine/Sociology + \item Online surveys + \item A/B testing + \item Data markets + \end{itemize} \vspace*{1cm} - \item<2-> Strategic users? - \visible<4>{\begin{itemize} - \item Budget Feasible Auctions [Singer 2010] - \end{itemize}} + \item<2-> Challenges + \begin{itemize} + \item Which experiments are \alert{most valuable}? + \item What if agents are \alert{strategic}? + \end{itemize} \end{itemize} % \end{overprint} \end{frame} -\begin{frame}{Contributions} +\begin{frame}{Our Contributions} \pause \begin{itemize} \item Experimental design when users are strategic \pause + \begin{itemize} + \item Budget Feasible Mechanisms [Singer 2010] + \end{itemize} + \pause \vspace*{1cm} \item Linear Regression \pause @@ -197,7 +206,7 @@ Let $S\subset [N]$ be the set of experiments performed, and \end{frame} -\begin{frame}{Budget Feasible Mechanism Design [Singer 2010] (cont'd)} +\begin{frame}{Budget Feasible Mechanism Design [Singer 2010] } We seek mechanisms $\mathcal{M}=(S,p)$ that are: \pause \vspace{0.3cm} @@ -262,12 +271,27 @@ Information Gain/D-optimality Criterion: 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}{A Few Properties of the Value Function} +\begin{align*} +V(S)&= \frac{1}{2}\log\det (R^{-1}+\sum_{i\in S}x_ix_i^T) +\end{align*} +\visible<2->{\begin{align*}V(S\cup\{i\})-V(S) &= \log(1+x_i^TA_S^{-1}x_i ), \quad\text{where }\\A_S &= R^{-1}+\sum_{i\in S}x_ix_i^T\end{align*}} +\visible<3->{ +\begin{itemize} +\item<3-> Increase is greatest when $x_i$ \alert{spans a new direction} +\item<4-> Adding an experiment \alert{always helps} +\item<5-> $V$ is \alert{submodular}: +$$V(S\cup\{i\})-V(S) \geq V(S'\cup\{i\})-V(S'),\quad \text{ for }S\subseteq S'. $$ +\end{itemize} } \end{frame} + \begin{frame}{Full Information Setting} \onslide<2->{ \begin{block}{\textsc{Experimental Design Problem (EDP)} } @@ -279,7 +303,7 @@ V(S)&=H(\beta)-H(\beta\mid y_i,i\in S)\\ \end{block} } \begin{itemize} -\item<3->$R=I$: homotropic prior +\item<3->$R=I$: homotropic prior, $\lambda=1$ \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) |