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 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