
%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is the LaTeX source for the instructions to authors using
% the LaTeX document class 'llncs.cls' for contributions to
% the Lecture Notes in Computer Sciences series.
% http://www.springer.com/lncs       Springer Heidelberg 2006/05/04
%
% It may be used as a template for your own input - copy it
% to a new file with a new name and use it as the basis
% for your article.
%
% NB: the document class 'llncs' has its own and detailed documentation, see
% ftp://ftp.springer.de/data/pubftp/pub/tex/latex/llncs/latex2e/llncsdoc.pdf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[twocolumn,english]{article}

\usepackage[width=17cm,height=22cm]{geometry}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{authblk}
%\usepackage{hyperref}   % The package hyperref provides LaTeX the ability to create hyperlinks within the document

\bibliographystyle{alpha}


\usepackage{amsmath}
\usepackage{amssymb}
\setcounter{tocdepth}{3}
\usepackage{graphicx}
\usepackage{xcolor}

\usepackage{array}
\usepackage{multirow}

\newcommand{\Prob}{\textbf{\textsf{\textup{P}}}}  % Probability over a set
\newcommand{\prob}{\textbf{\textsf{\textup{p}}}}  % Probability density
\newcommand{\Reel}{\mathbb{R}}                           % l'ensemble des reels

\usepackage[english,algoruled,vlined]{myalgorithm2e}   % style défini par Cedric Wemmert

\newenvironment{myalgo}[2] {
  \begin{algorithm}[english,algoruled]
  \caption{#1}\label{#2}
  \SetKw{KwA}{to}
  \DontPrintSemicolon
}
{\end{algorithm}}

\newenvironment{myalgo_nonfloat}[2] {
  \begin{algorithmic}[english,algoruled]
  \caption{#1}\label{#2}
  \SetKw{KwA}{to}
  \DontPrintSemicolon
}
{\end{algorithmic}}


\usepackage{url}
\urldef{\mailsa}\path|{antoine.cornuejols, christine.martin}@agroparistech.fr|    
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}

\title{Unsupervised one class identification \\
by selecting and combining ranking functions}

\author[1]{Antoine Cornu\'ejols}%
%\thanks{Please note that the LNCS Editorial assumes that all authors have used
%the western naming convention, with given names preceding surnames. This determines
%the structure of the names in the running heads and the author index.}%
\author[1]{Christine Martin}

\affil[1]{AgroParisTech, d\'epartement MMIP et INRA UMR-518\\
    16, rue Claude Bernard \\
    F-75231 Paris Cedex 5 (France)}
    
\renewcommand\Authands{, et }
\renewcommand\Authand{ et }


\begin{document}

\maketitle


% ------------------------------------------------------------------------------------------------
\begin{abstract}
We study the problem of identifying a class of interest in an unsupervised data set. Assuming that a set ${\cal F}$ of score functions is available, of unknown performance for the task at hand, we propose a method in order to \textit{select useful functions} from the set. Each of these functions induces a ranking over the data set. 

We then show how to \textit{combine the base rankings} thus obtained. Experimental results demonstrate that the combined performance is almost as good, or better, than the performance of the best, but unknown, score function in ${\cal F}$. In addition, we show, under some simplifying assumptions, how a proper combination of the base rankings allows one to end up with DNF formulas involving the selected score functions that converge to optimal precision and recall with respect to the target concept, if the capacity of ${\cal F}$ permits it. Such formulas, easily interpretable, are very desirable in the exploratory context of data mining. 

\end{abstract}
% ------------------------------------------------------------------------------------------------

\medskip

\noindent\textbf{Mots-clef}: Unsupervised learning, Ensemble methods.


% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------
\section{Introduction}
% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------

Data exploration aimed at discovering interesting classes of patterns is an essential part of scientific discovery or, more mundanely, of data mining. For instance, in bioinformatics, many research works look for the identification of genes that respond to some conditions in the environment, or for finding proteins that could potentially interact with some given target drugs. In a different context, the IRS (Internal Revenue Service) would like to identify the most likely tax evaders. More generally, fraud detection is a growing application area. In each case, there is one class of interest that gathers objects the expert is looking for against the other data points. 

In this exploratory setting, it is difficult to come up with informative functions good at distinguishing between the interesting data points versus the non interesting ones. While it might be easy to get candidate evaluation functions from experts or from libraries of functions commonly used in statistics or in Machine Learning, or even to generate such functions automatically, it is difficult in an unsupervised context to assess their merit. Therefore one is left guessing which one(s) of these functions to rely on. Additionally, for many application domains, and especially those where data is described by a large number of features, it is highly desirable that the class of interest be described in an interpretable way. This means that the class of interest should be expressed as much as possible using understandable features. For most experts, understanding and the capacity for reasoning imply descriptions that use combinations of predicates like disjunctive normal forms (DNF). This allows him/her to gain insight in what makes the class of interest apart and how this can be related to the current domain theory, possibly stimulating some revision of the theory. 

\smallskip
In this work, we study the following problem. We suppose that there exists a set ${\cal S}$ of $m$ data points from the input space ${\cal X}$ with no labels: ${\cal S} = \{{\mathbf x}_1, \ldots, {\mathbf x}_m\}$ that has been generated by an unknown mixture of distributions of which some components, belonging to $\Prob_{\cal X}^+$, correspond to the class of interest that we call ${\cal S}^+$, and the other components, $\Prob_{\cal X}^-$, correspond to the set of the remaining data points ${\cal S}^-$. The sets ${\cal S}^+$ and ${\cal S}^-$, such that ${\cal S}^+ \cup {\cal S}^- = {\cal S}$, are unknown and must be identified as well as possible.

In addition, we suppose that a set ${\cal F}$ of evaluation functions (or score functions) is available, each function associating a score to a data point: $f_i : {\cal X} \rightarrow \Reel$. Nothing is assumed \textit{a priori} about the usefulness of each function $f_i \in {\cal F}$, and in particular, one does not know if any given function is ``aligned'' with the target concept, that is if it tends to put the data points of the class of interest toward the top of the induced ranking over the data set ${\cal S}$. 

We propose a method for identifying useful score functions in ${\cal F}$, if some exist, in this completely unsupervised setting. The basic idea is to look at the correlation between the rankings induced by the score functions over ${\cal S}$ and to select functions with a particular property. We explain how one can use the base rankings in order to get a combined ranking of the data points in ${\cal S}$ with good performances. 
%Specifically, experiments show that the resulting ranking is almost as good as the one of the best, but \textit{unknown}, score function, and sometimes even better. 

We end up by demonstrating, under some simplifying assumptions, how a proper combination of the base rankings allows one to end up with DNF formulas that converges to optimal precision and recall with respect to the target concept, if the capacity of ${\cal F}$ permits it. 



% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------
\section{The selection of useful evaluation functions}
% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------

% ------------------------------------------------------------------------------------------------
\subsection{Principle of the method}
% ------------------------------------------------------------------------------------------------

In supervised learning \ldots


% ------------------------------------------------------------------------------------------------
\subsection{Correlation measures}
% ------------------------------------------------------------------------------------------------

A measure of correlation between rankings \ldots

\begin{figure*}[t]
\centering
\includegraphics[width=10.5cm]{FIG/fig-cbe-roc-3.pdf}
\caption{The curve $|\cap_n^{i,j}|/n$ function of $n$. Two independent draws should approximately result in the diagonal law. (Left) Two maximally correlated draws give $|\cap_n^{i,j}|/n=1 \;\; (\forall n)$. Two draws maximally inversely correlated give the red curve at the bottom. All possible behaviors fall between these two extreme curves. (Right) The characteristic curve for two rankings from uncorrelated but perfectly informed evaluation functions.}
\label{fig-correlation-curves}
\end{figure*}

In the proposed method, \ldots

Figure \ref{fig-curves} depicts a typical difference. Here the evaluation functions are ANOVA and {\sc Relief} \cite{kononenko1994estimating} and the data corresponds to 6,400 genes. The task was to find out if some genes were sensitive to low radioactivity levels. The upper curve $|\cap_n^{i,j}|$ shows the correlation over the data, while the lower curve with confidence intervals is obtained by computing the intersections $|\cap_n^{i,j}|$ over random samples ${\cal S}_0$ (here 100). 


The difference in \ldots

\begin{figure}
\centering
\includegraphics[width=0.45\linewidth]{FIG/Fig-variation-v2.pdf}
\hspace{0.2cm}
\includegraphics[width=0.45\linewidth]{FIG/Fig-variation-p-bis-v2.pdf}
\caption{Correlation curves between rankings of an artificial data set of 1,000 elements for various numbers of elements of class `$+$', here 50, 200 and 400. The peaks are accentuated on the right graph which corresponds to an easier problem.}
\label{fig-correlation-curves-artificial}
\end{figure}



%We are looking for a correlation measure between rankings in order to detect pairs of evaluation functions that give rankings significantly more correlated on the data set $\cal S$ than on random data sets (that we will denote ${\cal S}_0$ by reference to the null hypothesis). Several such measures have been proposed, such as the \textit{Pearson correlation coefficient} which takes the scores $f_i^l$ of object $l$ by the function $f_i$ as inputs (instead of the ranks):
%\begin{equation*}
%S(f_i, f_j) \; = \; \frac{\sum_l(f_i^l -\mu_{f_i}) (f_j^l - \mu_{f_j})}{\sqrt{\sum_l(f_i^l -\mu_{f_i})^2 (f_j^l - \mu_{f_j})^2}}
%\end{equation*}
%
%\noindent
%or the \textit{the Spearman Rank-Order Correlation}: 
%\begin{equation*}
%S(f_i, f_j) \; = \; 1 - 6 \sum_l \frac{(f_i^l - f_j^l)^2}{m (m^2-1)}
%\end{equation*}
%where  denotes the rank of object $l$ in the ranking of the $f_i$ function.
%
%Another possibility 


% ------------------------------------------------------------------------------------------------
\subsection{A theoretical analysis}
\label{sec-combi-2fcts-inter-n}
% ------------------------------------------------------------------------------------------------

In this section, we develop a simple model in order to allow us (in Section \ref{sec-interpretable-combinations}) to devise a strategy for discovering interpretable expressions of the hidden regularities in the data. 

We start by assuming that the evaluation functions are characterized by a positive (or negative) propensity to put the elements of class `$+$' at the top of their ranking. This propensity can be modeled by a ROC curve \cite{flach2012machine}. 
 
(\ldots)

In the simple analysis reported here, we suppose that we consider two evaluation functions $f_i$ and $f_j$ of the same strength (defined by $\varepsilon_x$ and $\varepsilon_y$), that is they share a common ROC curve. The theoretical study with functions exhibiting different ROC curves does not change qualitatively the results. 

Let us compute the size of the intersection of the top$_n$ elements: $|\cap_n^{i,j}|$. Let $x$ be the number of false positive elements. Therefore, $x$ varies on the FP axis. Let $m^+$ be the number of positive elements in $\cal S$ and $m^-$ be the number of negative elements. Then, we have two phases to consider.

\begin{enumerate}
   \item 1st phase: $x \leq \varepsilon_x$. One finds: 
   \begin{equation}
   \left\lbrace
      \begin{array}{cl}
      \vspace{0.3cm}
   n &= \; x \, m^{-} + \frac{1 - \varepsilon_y}{\varepsilon_x} \, x \, m^{+} \\
   |\cap_n^{i,j}| &= \; x^2 \, m^{-} \, + \, \bigl(\frac{1 - \varepsilon_y}{\varepsilon_x}\bigr)^2 \, x^2 \, m^{+}
      \end{array}
   \right.
   \end{equation}
   giving, for the first part of the curve, the equation:
   \begin{align}
   \frac{|\cap_n^{i,j}|}{n} \; &= \; \frac{x^2 \, m^{-} \, + \, \bigl(\frac{1 - \varepsilon_y}{\varepsilon_x}\bigr)^2 \, x^2 \, m^{+}}
   {x \, m^{-} + \frac{1 - \varepsilon_y}{\varepsilon_x} \, x \, m^{+}} \nonumber \\
   \; &= \; x\; \frac{m^{-} \, + \, \bigl(\frac{1 - \varepsilon_y}{\varepsilon_x}\bigr)^2 \, m^{+}}
   {m^{-} + \frac{1 - \varepsilon_y}{\varepsilon_x} \, m^{+}}
   \end{align}
   
   For the special value $x = \varepsilon_x$ (point $P$), we get: 
   \begin{equation}
   \left\lbrace
      \begin{array}{cl}
      \vspace{0.3cm}
   n &= \; \varepsilon_x \, m^{-} + (1 - \varepsilon_y) \, m^{+} \\
   |\cap_n^{i,j}| &= \; \varepsilon_x^2 \, m^{-} \, + \, ({1 - \varepsilon_y})^2 \,  m^{+}
      \end{array}
   \right.
   \end{equation}
   corresponding to the value on the $y$-axis: 
   \begin{equation}
   \frac{|\cap_n^{i,j}|}{n} \; = \; \frac{\varepsilon_x^2 \, m^{-} \, + \, ({1 - \varepsilon_y})^2 \,  m^{+}}
   {\varepsilon_x \, m^{-} + (1 - \varepsilon_y) \, m^{+}}
   \end{equation}

   \item 2nd phase: $\varepsilon_x < x$. 
   \begin{equation}
   \left\lbrace
      \begin{array}{cl}
      \vspace{0.3cm}
   n &= \; x \, m^{-} + \bigl[(1 - \varepsilon_y) + \frac{\varepsilon_y}{1 - \varepsilon_x} (x - \varepsilon_x) \bigr] \, m^{+} \\
   |\cap_n^{i,j}| &= \; x^2 \, m^{-} \, + \, \bigl[({1 - \varepsilon_y}) + \frac{\varepsilon_y}{1 - \varepsilon_x} (x - \varepsilon_x) \bigr]^2 \,  m^{+}
      \end{array}
   \right.
   \end{equation}
   giving, for the second part of the curve, the equation:
   \begin{equation}
   \frac{|\cap_n^{i,j}|}{n} \; = \; \frac{x^2 \, m^{-} \, + \, \bigl[({1 - \varepsilon_y}) + \frac{\varepsilon_y}{1 - \varepsilon_x} (x - \varepsilon_x) \bigr]^2 \,  m^{+}}
   {x \, m^{-} + \bigl[(1 - \varepsilon_y) + \frac{\varepsilon_y}{1 - \varepsilon_x} (x - \varepsilon_x) \bigr] \, m^{+}}
   \end{equation}
   
\end{enumerate}

These equations give the most probable value for $\frac{|\cap_n^{i,j}|}{n}$, as shown on the right hand side of Figure \ref{fig-cbe-roc}. While computed from an idealized model, this curve is in good accordance with empirical observations. 


% XXX say something about the case with a priori correlation.


% ------------------------------------------------------------------------------------------------
\subsection{The algorithm}
% ------------------------------------------------------------------------------------------------

The selection of the useful base scoring functions is done according to algorithm\ref{alg:selection}. \ldots 

\begin{myalgo}{Selection of ``good enough'' base scoring functions}{alg:selection}
  
	\Input{The data set $\cal S$ \\
	\hspace{1.0cm} The set $\cal F$ of the base scoring functions}
	\Output{A subset ${\cal F}'' \in {\cal F}$ of base functions}
	
	%% computation of the operators
	\vspace{0.2cm}
	\textbf{Generation} of $N$ random samples ${\cal S}_0$; \\
	
	\vspace{0.2cm}
	\ForAll{pairs of scoring functions $(f_i, f_j)_{(i \neq j)}$ $\in {\cal F}$}{
		\textbf{compute the over-correlation} of $(f_i, f_j)$ on $\cal S$ compared to the mean correlation on the samples ${\cal S}_0$ }
	{end forall} \\
	
	\vspace{0.2cm}
	\textbf{Select} the scoring functions $f_i \in {\cal F}$ with over-correlation $\geq \tau_{\text{min\_overcor}}$:   producing ${\cal F}'$\; 
	\vspace{0.2cm}
	Initialization : ${\cal F}'' = \emptyset$ \\
	
	\vspace{0.2cm}
	\ForAll{$f_i \in {\cal F}'$}{
			\If{$\sum_{j \neq i} overcorr(f_i,f_j) \geq \tau_{\text{sum\_overcorr}}$}{
		Put $f_i$ in ${\cal F}''$ \;
		}
		}
	{end forall} \\
	  
\end{myalgo}


% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------
\section{Experimental studies}
% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------

These experiments address the question as to which extent the proposed method is able to select relevant evaluation functions in $\cal F$, \ldots 

In order to test for this, we have realized experiments with artificial data. The data where generated using two probability distributions over the input space $\Reel^d$ (here $d = 20$): distribution $\Prob_{\cal X}^+$ for the `$+$' instances and distribution $\Prob_{\cal X}^-$ for the `$+$' instances. In the experiments reported here we have used two Gaussian distributions with means separated by a euclidian distance of 3. The difficulty of the task was controlled by adding noise of varying standard deviation $\sigma$ to the data points ($\sigma =$ 1.5, 2.5, 3.5 and 4.5).

(\ldots)

Table \ref{tab-results} reports the minimal AUC (auc$_m$) and the maximum AUC (auc$^M$) for the functions in $\cal F$. Likewise, it reports the minimal AUC (auc$_m$), the maximal AUC (auc$^M$) and the mean AUC ($\overline{auc}$) for the functions selected by the method: in ${\cal F}''$. Finally, the last column gives the AUC obtained by combining the results of the evaluation functions selected in ${\cal F}''$ (see Section \ref{sec-combinations} for an explanation). 

\begin{table*}[ht]
 \begin{center}
%   \tabcolsep = 2\tabcolsep
   \begin{tabular}{|cc|cc|ccc|c|}
   \hline\hline
   	& 	& \multicolumn{2}{c|}{Before selection} & \multicolumn{4}{c|}{After selection} \\
	
    \raisebox{1.5ex}[0cm]{$\sigma$} &    \raisebox{1.5ex}[0cm]{$\frac{m^+}{m}$}      & auc$_m$ & auc$^M$ &  auc$_m$ & auc$^M$ & $\overline{auc}$ & AUC comb \\
   \hline
   \multirow{3}{5mm}{1.5}
    	& $\frac{40}{320}$ & $0 \pm 0$        & $1 \pm 0$       
           & $\mathbf{0.92} \pm 0.03$		& $1 \pm 0$        & $0.98 \pm 0.01$	& $\mathbf{1} \pm 0$        \\
   	 	& $\frac{80}{320}$ & $0 \pm 0$        & $1 \pm 0$        
           & $\mathbf{0.87} \pm 0.06$		& $1 \pm 0$        & $0.97 \pm 0.01$	& $\mathbf{1} \pm 0$        \\

    	& $\frac{120}{320}$ & $0 \pm 0$        & $1 \pm 0$        
           & $\mathbf{0.84} \pm 0.07$		& $1 \pm 0$        & $0.95 \pm 0.01$	& $\mathbf{1} \pm 0$        \\

           \hline
   \multirow{4}{3mm}{2.5}

   	 	& $\frac{40}{320}$ & $~0.02 \pm 0.01~~$        & $0.98 \pm 0.01~$       
           & $\mathbf{0.94} \pm 0.03~$		& $0.98 \pm 0.00~$        & $0.96 \pm 0.02$	& $\mathbf{~0.98} \pm 0.01$        \\

   	 	& $\frac{80}{320}$ & $0.03 \pm 0.01$        & $0.98 \pm 0.01$       
           & $\mathbf{0.85} \pm 0.05$		& $0.98 \pm 0.01$        & $0.91 \pm 0.02$	& $\mathbf{0.97} \pm 0.01$        \\

    	& $\frac{120}{320}$ & $0.03 \pm 0.01$        & $0.98 \pm 0.01$        
           & $\mathbf{0.76} \pm 0.03$		& $0.98 \pm 0.01$        & $0.88 \pm 0.02$	& $\mathbf{0.97} \pm 0.01$        \\

    	& $\frac{160}{320}$ & $0.03 \pm 0.01$        & $0.98 \pm 0.01$        
           & $\mathbf{0.73} \pm 0.04$		& $0.97 \pm 0.01$        & $0.85 \pm 0.02$	& $\mathbf{0.95} \pm 0.01$        \\

           \hline
   \multirow{4}{3mm}{3.5}

   	 	& $\frac{40}{320}$ & $0.09 \pm 0.02$        & $0.91 \pm 0.02$       
           & $\mathbf{0.75} \pm 0.06$		& $0.90 \pm 0.03$        & $0.83 \pm 0.01$	& $\mathbf{0.90} \pm 0.03$        \\

   	 	& $\frac{80}{320}$ & $0.09 \pm 0.02$        & $0.92 \pm 0.02$        
           & $\mathbf{0.65} \pm 0.05$		& $0.92 \pm 0.02$        & $0.79 \pm 0.02$	& $\mathbf{0.90} \pm 0.02$        \\

   	 	& $\frac{120}{320}$ & $0.09 \pm 0.02$        & $0.91 \pm 0.01$      
           & $\mathbf{0.64} \pm 0.04$		& $0.91 \pm 0.01$        & $0.77 \pm 0.02$	& $\mathbf{0.89} \pm 0.02$        \\

   	 	& $\frac{160}{320}$  & $0.10 \pm 0.01$        & $0.91 \pm 0.02$      
           & $\mathbf{0.63} \pm 0.03$		& $0.91 \pm 0.02$        & $0.76 \pm 0.02$	& $\mathbf{0.88} \pm 0.02$        \\

           \hline
   \multirow{4}{3mm}{4.5}

   	 	& $\frac{40}{320}$ & $0.13 \pm 0.02$        & $0.86 \pm 0.02$       
           & $\mathbf{0.67} \pm 0.03$		& $0.86 \pm 0.02$        & $0.76 \pm 0.02$	& $\mathbf{0.86} \pm 0.02$        \\

   	 	& $\frac{80}{320}$  & $0.15 \pm 0.02$        & $0.85 \pm 0.02$        
           & $\mathbf{0.65} \pm 0.03$		& $0.84 \pm 0.03$        & $0.75 \pm 0.02$	& $\mathbf{0.84} \pm 0.03$        \\

   	 	& $\frac{120}{320}$ & $0.15 \pm 0.02$        & $0.84 \pm 0.02$      
           & $\mathbf{0.62} \pm 0.06$		& $0.84 \pm 0.02$        & $0.73 \pm 0.03$	& $\mathbf{0.84} \pm 0.02$        \\

   	 	& $\frac{160}{320}$ & $0.15 \pm 0.01$        & $0.85 \pm 0.01$      
           & $\mathbf{0.61} \pm 0.03$		& $0.85 \pm 0.01$        & $0.72 \pm 0.02$	& $\mathbf{0.83} \pm 0.03$        \\

   \hline
   \end{tabular}
\vspace{.3cm}
\caption{Experimental results in function of the noise parameter $\sigma$ and the proportion of the class `$+$'.} 
\label{tab-results}
 \end{center}
\end{table*}

(\ldots)


% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------
\section{A method for combining results}
\label{sec-combinations}
% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------

(\ldots)


% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------
\section{Towards interpretable combinations of  selected features}
\label{sec-interpretable-combinations}
% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------

Assuming that there exists a class of $m^+$ objects of interest from a distribution $\Prob_{\cal X}^+$  and a class of $m^- $ other objects in the data set $\cal S$ from a distribution $\Prob_{\cal X}^-$, is there any hope of identifying the objects of the class `$+$'? It all depends on the number and properties of the evaluation functions contained in $\cal F$. 

(\ldots)

%\begin{figure}
%\centering
%\includegraphics[width=0.80\linewidth]{FIG/fig-cbe-roc-v2.pdf}
%\caption{(Left) The simple model of the ROC curve used in the theoretical analyses. (Right) The resulting curve of the most probable correlation size $\frac{|\cap_n^{i,j}|}{n}$. }
%\label{fig-cbe-roc}
%\end{figure}

One can compute the ROC curve obtained when considering the intersection $\frac{|\cap_n^{i,j}|}{n}$ of the top$_n$ of each function. 

Using the equations of Section \ref{sec-combi-2fcts-inter-n}, one obtains:

\smallskip
For $x \leq \varepsilon_x$:
\begin{equation}
|\cap_n^{i,j}| \; = \underbrace{\;  x^2 m^-_{~}}_{FP} \; + \; \underbrace{\biggl[\frac{1-\varepsilon_y}{\varepsilon_x}\biggr]^2 \, x^2 m^+}_{TP}
\end{equation}

and for $x > \varepsilon_x$:
\begin{equation}
|\cap_n^{i,j}| \; = \underbrace{\;  x^2 m^-_{~}}_{FP} \; + \; \underbrace{\biggl[(1-\varepsilon_y) + \frac{\varepsilon_y}{1-\varepsilon_x} (x-\varepsilon_x)\biggr]^2 \,  m^+}_{TP}
\end{equation}

(\ldots)

What is interesting is that while the AUC of the function $\frac{|\cap_n^{i,j}|}{n}$ is not much larger than the AUC of each base function, its slope in the left part of the curve is much steeper. That means that the precision in this part seems very much improved. Does the theoretical analysis confirms this? Let us see how the precision and recall evolve when one goes from a random selection of objects in $\cal S$ (stage 0), to using the base score function (stage 1), up to using the function $|\cap_n^{i,j}|$ (stage 2).

\begin{enumerate}
   \item \textit{Stage 0}. We suppose that a fraction $\eta$ of the $m$ objects are randomly selected in $\cal S$ and are assigned to the class `$+$'.    We let: $m^- = \alpha \, m^+$, with $\alpha \geq 0$ and $\varepsilon_x = \beta \, (1-\varepsilon_y)$ with $0 \leq \beta < 1$ (note that $0 \leq \beta < 1$ entails an AUC $> 0.5$ while $\beta > 1$ entails an AUC $< 0.5$). Then, we get the precision ($prec.$) and recall:

   \begin{align*}
   \text{prec.} \; &= \; \frac{\text{TP}}{\text{TP} + \text{FP}} \; = \; \frac{\eta \, m^+}{\eta (m^+ + m^-)} \; 
%   = \; \frac{m^+}{(m^+ + \alpha \, m^+)}  \; 
   = \; \frac{1}{1 + \alpha} \\
   \text{recall} \; &= \; \frac{\text{TP}}{\text{TP} + \text{FN}} \; = \; \frac{\eta \, m^+}{m^+} \; = \; \eta
   \end{align*}
   
   
\vspace{0.3cm}   
   \item \textit{Stage 1}. We look at the point on the ROC curve that maximizes precision and recall: $x = \varepsilon_x$ on Figure \ref{fig-cbe-roc}.
      \begin{align*}
   \text{prec.} \; &= \; \frac{(1 - \varepsilon_y) \, m^+}{(1 - \varepsilon_y) \, m^+ + \varepsilon_x \, \alpha \, m^+}
   \\
   &= \;  \frac{1 - \varepsilon_y}{1 - \varepsilon_y + \alpha \, \beta \, (1 - \varepsilon_y)} 
%   \; = \; \frac{1}{1 \, + \, \frac{\alpha \, \varepsilon_x}{1 - \varepsilon_y}} 
   \; = \; \frac{1}{1 + \alpha \, \beta}\\
   \text{recall} \; &= \;  \frac{(1-\varepsilon_y) \, m^+}{m^+} \; = \; 1 - \varepsilon_y
   \end{align*}

\vspace{0.3cm}   
   \item \textit{Stage 2}. We now use the function  $|\cap_n^{i,j}|$, again at the point with best precision and recall.
         \begin{align*}
   \text{prec.} \; &= \; \frac{(1 - \varepsilon_y)^2 \, m^+}{(1 - \varepsilon_y)^2 \, m^+ + {\varepsilon_x}^2 \, \alpha \, m^+}
   \\
   &= \;  \frac{(1 - \varepsilon_y)^2}{(1 - \varepsilon_y)^2 + \alpha \, \beta^2 \, (1 - \varepsilon_y)^2} 
   \; = \;  \frac{1}{1 + \alpha \, \beta^2 } \\
   \text{recall} \; &= \;  \frac{(1-\varepsilon_y)^2 \, m^+}{m^+} \; = \; (1 - \varepsilon_y)^2
   \end{align*}
   
\end{enumerate}

It is apparent that at each stage one looses on the recall, meaning that a smaller part of the class `$+$' gets recognized. At the same time, \ldots

\begin{align*}
   \text{prec.} \; &= \; \frac{(1 - \varepsilon_y)^k \, m^+}{(1 - \varepsilon_y)^k \, m^+ + {\varepsilon_x}^k \, \alpha \, m^+} 
   \; &= \;  \frac{1}{1 + \alpha \, \beta^k } \\
   \text{recall} \; &= \;  \frac{(1-\varepsilon_y)^k \, m^+}{m^+} \; &= \; (1 - \varepsilon_y)^k
\end{align*}

(\ldots)


The method is therefore in principle able to ``invent'' new predicates and to produces expressions, DNF, that are conducive to easier interpretation.

However, \ldots 


%XXX
%\vspace{1cm}
%{\color{red} Two questions (at least): 
%\begin{itemize}
%   \item How to retrieve the optimal point on the ROC curves?
%   \item What if there is a priori correlation?
%\end{itemize}
%}

% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------
\section{Related works}
% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------

Ensemble methods have first been studied in the context of supervised learning 
%(e.g. in \textit{learning from expert advice} (\cite{freund1997decision}), the \textit{weighted majority algorithm} (\cite{littlestone1994weighted}), or for \textit{on-line learning} (\cite{CBL:06}) 
(see \cite{schapire2012boosting,zhou2012ensemble} for comprehensive studies). It is indeed \ldots




% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------
\section{Conclusion and future works}
% ------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------

In this paper, we addressed \ldots


\bigskip
\noindent
\textbf{Acknowledgments.} Part of this work has been supported by the French ANR project ``Coclico'' (2013-2016). 

\bibliographystyle{splncs}
\bibliography{biblio_exemple}



%\begin{thebibliography}{4}

%\bibitem{jour} Smith, T.F., Waterman, M.S.: Identification of Common Molecular
%Subsequences. J. Mol. Biol. 147, 195--197 (1981)
%
%\bibitem{lncschap} May, P., Ehrlich, H.C., Steinke, T.: ZIB Structure Prediction Pipeline:
%Composing a Complex Biological Workflow through Web Services. In: Nagel,
%W.E., Walter, W.V., Lehner, W. (eds.) Euro-Par 2006. LNCS, vol. 4128,
%pp. 1148--1158. Springer, Heidelberg (2006)
%
%\bibitem{book} Foster, I., Kesselman, C.: The Grid: Blueprint for a New Computing
%Infrastructure. Morgan Kaufmann, San Francisco (1999)
%
%\bibitem{proceeding1} Czajkowski, K., Fitzgerald, S., Foster, I., Kesselman, C.: Grid
%Information Services for Distributed Resource Sharing. In: 10th IEEE
%International Symposium on High Performance Distributed Computing, pp.
%181--184. IEEE Press, New York (2001)
%
%\bibitem{proceeding2} Foster, I., Kesselman, C., Nick, J., Tuecke, S.: The Physiology of the
%Grid: an Open Grid Services Architecture for Distributed Systems
%Integration. Technical report, Global Grid Forum (2002)
%
%\bibitem{url} National Center for Biotechnology Information, \url{http://www.ncbi.nlm.nih.gov}

%\end{thebibliography}


\end{document}




\section*{Appendix: Springer-Author Discount}

LNCS authors are entitled to a 33.3\% discount off all Springer
publications. Before placing an order, the author should send an email, 
giving full details of his or her Springer publication,
to \url{orders-HD-individuals@springer.com} to obtain a so-called token. This token is a
number, which must be entered when placing an order via the Internet, in
order to obtain the discount.

\section{Checklist of Items to be Sent to Volume Editors}
Here is a checklist of everything the volume editor requires from you:


\begin{itemize}
\settowidth{\leftmargin}{{\Large$\square$}}\advance\leftmargin\labelsep
\itemsep8pt\relax
\renewcommand\labelitemi{{\lower1.5pt\hbox{\Large$\square$}}}

\item The final \LaTeX{} source files
\item A final PDF file
\item A copyright form, signed by one author on behalf of all of the
authors of the paper.
\item A readme giving the name and email address of the
corresponding author.
\end{itemize}
\end{document}
