Drat of the uniqueness section

1 files changed, 80 insertions, 25 deletions

diff --git a/uniqueness.tex b/uniqueness.tex
index 68d7d2d..0a7a1eb 100644
--- a/uniqueness.tex
+++ b/uniqueness.tex
@@ -8,22 +8,29 @@ them for people recognition?
 
 \subsection{Face recognition benchmark}
 
-A good way to understand the uniqueness of a metric is to look at the
-performance it gives for the \emph{pair-matching problem}. In this
-problem you are given two measurements of the metric and you want to
-decide whether they come from the same individual (matched pair) or
-from two different individuals (unmatched pair).
+A good way to understand the uniqueness of a metric is to look at how
+well an algorithm based on it performs in the \emph{pair-matching
+problem}. In this problem you are given two measurements of the metric
+and you want to decide whether they come from the same individual
+(matched pair) or from two different individuals (unmatched pair).
 
-The \emph{Labeled Faces in the wild} \cite{lfw} database is specifically suited
-to study the face pair matching problem and has been used to benchmark
-several face recognition algorithms. Raw data of this benchmark is
-publicly available and has been derived as follows: the database is
-split into 10 subsets. From each of these subsets, 300 matched pairs and 300
-unmatched pairs are randomly chosen. Each algorithm runs 10 separate leave-one-out cross
-validation experiments on these sets of pairs. Averaging the number of true positives
-and false positives across the 10 experiments for a
-given threshold then yields one point on the true-positive vs
-false-positive curve (also known as ROC). 
+The \emph{Labeled Faces in the wild} \cite{lfw} database is
+specifically suited to study the face pair matching problem and has
+been used to benchmark several face recognition algorithms. Raw data
+of this benchmark is publicly available and has been derived as
+follows: the database is split into 10 subsets. From each of these
+subsets, 300 matched pairs and 300 unmatched pairs are randomly
+chosen. Each algorithm runs 10 separate leave-one-out cross-validation
+experiments on these sets of pairs. Averaging the number of true
+positives and false positives across the 10 experiments for a given
+threshold then yields one point on the receiver operating
+characteristic curve (ROC curve: this is the curve of the
+true-positive rate vs. the false-positive rate as the threshold of the
+algorithm varies). Note that in this benchmark the identity
+information of the individuals appearing in the pairs is not
+available, which means that the algorithms cannot form additional
+images pair from the input data. This is referred to as the
+\emph{Image-restricted} setting in the LFW benchmark.
 
 \subsection{Experiment design}
 
@@ -35,24 +42,72 @@ these measurements the lengths of six bones (radius, humerus, femur,
 tibia, left coxae, right coxae). Because of missing values, this
 reduces the size of the dataset to 1191.
 
-From this data set, 1191 matched pairs and 1191 unmatched
-pairs are generated. The exact measurements of the bones are never directly
-accessible, but are always perturbed by a noise whose variance depends
-on the collection protocol. This is accounted for by adding
-independent random Gaussian noise to each constituents of the pairs.
+From this data set, 1191 matched pairs and 1191 unmatched pairs are
+generated. In practice, the exact measurements of the bones are never
+directly accessible, but are always perturbed by a noise whose
+variance depends on the collection protocol. This is accounted for by
+adding independent random Gaussian noise to each constituents of the
+pairs.
 
 \subsection{Results}
 
 The pair-matching problem is then solved by using a proximity
 threshold algorithm: for a given threshold, a pair will be classified
 as \emph{matched} if the Euclidean distance of its two constituents is
-lower than the threshold and \emph{unmatched} otherwise.
+lower than the threshold and \emph{unmatched} otherwise. Formally, let
+$(s_1,s_2)$ be an input pair of the algorithm
+($s_i\in\mathbf{R}_+^{6}$, these are the measurements of the six
+bones), the output of the algorithm for the threshold $\delta$ is
+defined as:
+\begin{displaymath}
+  A_\delta(s_1,s_2) = \begin{cases}
+    1 & \text{if $d(s_1,s_2) < \delta$}\\
+    0 & \text{otherwise}
+  \end{cases}
+\end{displaymath}
 
-This algorithm does not require any training, so it is run on the
-whole set of pairs without doing cross-validation. Figure
-\ref{fig:roc} shows the ROC of the proximity threshold algorithm for
-varying variance of the noise added to the data.
+\begin{figure}
+  \begin{center}
+    \includegraphics[width=10cm]{data/pair-matching/roc.pdf}
+  \end{center}
+  \caption{Receiver operating characteristic (true positive rate
+  vs. false positive rate) for several standard deviations of the
+  noise and for the state-of-the-art \emph{Associate-Predict} face
+  detection algorithm.}
+  \label{fig:roc}
+\end{figure}
 
+Figure \ref{fig:roc} shows the ROC curve of the proximity threshold
+algorithm for different values of the standard deviation of the noise,
+as well as the ROC of the best performing face detection algorithm in
+the Image-restricted LFW benchmark: \emph{Associate-Predict}
+\cite{associate}.
+
+The results show that with a standard deviation of 3mm, skeleton
+proximity thresholding performs quite similarly to face detection at
+low false-positive rate. At this noise level, the error is smaller
+than 1cm with 99.9\% probability smaller. Even with a standard
+deviation of 5mm, it is still possible to detect 90\% of the matched
+pairs with a false positive rate of 6\%.
+
+This experiment gives an idea of the noise variance level above which
+it is not possible to consistently distinguish skeletons. This noise
+level can be interpreted as follows in the person identification
+setting. For this problem, a classifier can be built be first learning
+a \emph{skeleton profile} for each individual from all the
+measurements in the training set. Then, given a new skeleton
+measurement, the algorithm classifies it to the individual whose
+skeleton profile is closest to the new measurement. In this case,
+there are two distinct sources of noise:
+\begin{itemize}
+\item the absolute deviation of the estimator: how far is the
+  estimated profile from the exact skeleton profile of the person.
+\item the noise of the new measurement: this comes from the device
+  doing the measurement.
+\end{itemize}
+
+We will come back in section \label{sec:kinect} on the structure of
+the noise and its relation to the noise represented on the ROC curves.
 
 %%% Local Variables: 
 %%% mode: latex