\documentclass[11pt]{article}  %twoside
%\usepackage{epsf,epsfig}
\usepackage{graphics}
\usepackage{isolatin1}
\usepackage[utf8]{inputenc}

\pagestyle{empty}
\setlength{\unitlength}{2mm}
\sloppy
\def\RR{{\rm I\hspace{-0.50ex}R}}
\def\TITRE{Un-normalized Distribution} 
\def\ENTET{
\noindent\underline{\sc Supervisor}: Aur\'elien Decelle \& Mich\`ele Sebag\\
\underline{\sc Labs}: TAU $-$ CNRS $-$ INRIA $-$ Paris-Sud\\
\underline{\sc Mail}: decelle, sebag@lri.fr\\
\underline{\sc URL}: {\tt http://www.lri.fr/\string~sebag/Stages/Stage\_NoZ\_19.pdf}\\
}
\textwidth 17cm
\hoffset -2.5cm
\voffset -3cm
\textheight 26cm
\begin{document}
\begin{center}
{\Large Internship 2018 }\\~\\
{\Large\bf \TITRE}\\~\\
\end{center}
\ENTET~\\
\noindent\underline{\sc Abstract} :\\
Identifying the joint distribution underlying a finite sample set has many applications, ranging from generative learning to feature selection. 
Among the most prominent approaches are Restricted Boltzman Machines \cite{RBM}, defined as a bipartite graph involving visible features $v_i$ and hidden features $h_j$, with:
\[ P(v_1, \ldots v_D) = \frac{1}{Z} \sum_{(h_1,\ldots, h_d)} exp \left (- \sum_{i,j} W_{i,j} h_i v_j - \sum_i A_i v_i - \sum_j B_j H_j \right ) \]
where $Z$ is the normalization term ensuring that $P$ actually is a probability (summing to 1), involving a double summation on the $v$ and the $h$.
A main source of difficulty for training an RBM is to take into account the $Z$ term. Contrastive divergence \cite{CD} and its many variants aim to address this difficulty. \\

\section*{Goal}
The goal of the internship is to to train RBMs while side-stepping the $Z$ factor, in the case where: i) the ground truth distribution is known; ii) only a sample of high probability is known. through 

\section*{Proposed approach}
The proposed approach takes inspiration from Energy-based learning \cite{LeCun}, conjecturing that in many cases a 
is considered.

\paragraph{Surrogate distribution}
A first step consists of defining auxiliary optimization problems in small dimensions. Letting the primary optimization problem read: 
\[ {\cal F}: \RR^D \mapsto \RR \]
An auxiliary optimization problem is built from a random projection $\pi$:
\[ \pi: \RR^D \mapsto \RR^d, d \ll D \]
The population of solutions in the primary space is mapped onto the auxiliary space using $\pi$ and a Gaussian distribution in the auxiliary space noted ${\cal D}_\pi$ is built accordingly.

\paragraph{Enforced selection based on a surrogate distribution} A second step consists of running a diagonal CMA-ES in the high dimensional space, with ${\cal D}_D$ the associated distribution. The proposed approach, called Surrogate Distribution-based CMA-ES (SUMA), uses ${\cal D}_\pi$ to refine the selection of the offspring generated from ${\cal D}_D$. Formally, the $\kappa \times \lambda$ generated offspring being stratified according to their probability after ${\cal D}_D$, in each of the $\kappa$ slices the offspring with highest probability after ${\cal D}_\pi$ is retained. ${\cal D}_\pi$ thus is used as ``surrogate distribution'', to filter the offspring after these have been generated from ${\cal D}_D$ but before they are actually evaluated by $\cal F$.

\paragraph{Mixture of surrogate distributions} A third step is concerned with maintaining an ensemble of random projections $\pi_1 \ldots \pi_K$ and updating the mixture of distributions $({\cal D}_{\pi_i}, p_i)$. The importance $p_i$ of distribution ${\cal D}_{\pi_i}$ reflects the agreement between the true ranking of offspring (after fitness $\cal F$)
and the ranking of their projections by $\pi_i$, after probability ${\cal D}_{\pi_i}$. The $p_i$ are used during the enforced selection to draw the surrogate distribution ${\cal D}_{\pi_i}$ used to conduct the enforced selection in each slice.\\

\section*{Milestones}
A first sanity check for the proposed approach has been obtained by replacing the enforced selection based on ${\cal D}_\pi$, by an oracle selection based on $\cal F$ itself; this approach (increasing the number of fitness computations by a factor $\kappa$) significantly outperforms the diagonal CMA-ES (according to a fair comparison, i.e. for a same number of fitness computations). 

The issues to be addressed in the internship are the following:
\begin{itemize}
\item In each epoch, the distribution ${\cal D}_\pi$ is updated from the projections of the best offspring; however, these offspring have not been generated from ${\cal D}_\pi$, as opposed to the original CMA-ES. The update of the covariance matrix of the distribution might thus need to be reconsidered. 
\item The enforced selection (step 2) generates $\kappa$ more offspring than the original CMA-ES, to enable the filter through the auxiliary distribution. This hyper-parameter will be empirically and theoretically investigated.
\item The $p_i$s put on the different auxiliary problems/distributions mimic an importance sampling scheme on the surrogate distributions. Different mechanisms will be considered to update these weights: exponentially weighted average; discarding an auxiliary problem $\pi$ based on a Mann-Whitney Wilcoxon test of the probability after $({\cal D}_{\pi}$ of the projection after $\pi$ of the best and worst offspring.
\end{itemize}


The internship requires excellent programming skills (C++ or Python, based on existing libraries) and excellent mathematical understanding of the formal background (random projections, statistical tests, calibration).\\



\noindent{\bf References}\\
(1)  Hansen and Ostermeier. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation, 9(2), pp. 159-195.\\
(2) Ollivier, Arnold, Auger and Hansen. Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles. J. of Machine Learning Research (2017).\\
(3) Wang, Zoghi, Hutter, Matheson, de Freitas. Bayesian Optimization in High Dimensions via Random Embeddings. IJCAI 2013: 1778-1784

\end{document}
