new intro

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)