Slavica Jonić
email: slavica.jonic@impmc.upmc.fr

Computational methods for analyzing conformational variability of macromolecular complexes from cryo-electron microscopy images

Keywords: Cryo-EM conformational variability analysis methods Structure, dynamics, macromolecular complexes, cryo-electron microscopy, conformational changes, single-particle analysis

Computational methods for analyzing conformational variability of macromolecular complexes from cryo-electron microscopy images

INTRODUCTION

Cryo-electron microscopy (cryo-EM) image collection and analysis technique referred to as single-particle analysis is based on the principle of reconstructing a 3D average structure from images (2D parallel-beam projections) of many copies of the same macromolecular complex (particle) at unknown random orientations and positions in a thin layer of vitreous ice untilted in the microscope [START_REF] Frank | Three-Dimensional Electron Microscopy of Macromolecular Assemblies: Visualization of Biological Molecules in Their Native State[END_REF]. The 3D reconstruction requires extracting particles into individual images (often referred to as single-particle images) and determining the particle orientation (three Euler angles) and position (in-plane coordinates of the particle centre) for each singleparticle image. For a high resolution of the reconstruction, images should be sorted in the way to obtain a 3D average structure by combining only images of identical particle structures.

Thanks to recent instrumental and methodological developments for cryo-EM, near-atomic resolution of EM density maps is now more frequent [START_REF] Zhang | Near-atomic resolution using electron cryomicroscopy and single-particle reconstruction[END_REF][START_REF] Yu | 3.88 A structure of cytoplasmic polyhedrosis virus by cryo-electron microscopy[END_REF][START_REF] Liao | Structure of the TRPV1 ion channel determined by electron cryomicroscopy[END_REF][START_REF] Bai | An atomic structure of human gamma-secretase[END_REF][START_REF] Bartesaghi | 2 A resolution cryo-EM structure of beta-galactosidase in complex with a cell-permeant inhibitor[END_REF] and studying conformational dynamics of macromolecular complexes is allowed [START_REF] Jin | Iterative elastic 3D-to-2D alignment method using normal modes for studying structural dynamics of large macromolecular complexes[END_REF][START_REF] Dashti | Trajectories of the ribosome as a Brownian nanomachine[END_REF][START_REF] Behrmann | Structural snapshots of actively translating human ribosomes[END_REF][START_REF] Banerjee | 2.3 A resolution cryo-EM structure of human p97 and mechanism of allosteric inhibition[END_REF]. The term "multiparticle reconstruction" is sometimes used to refer to the reconstruction of multiple different structures coexisting in a sample. The multiparticle reconstruction involves a strategy of sorting the mixed population of images into groups (classes) such that each class ideally contains images of only one structure. The majority of available computational methods simplify the problem of structural heterogeneity by assuming that the number of different structures in the sample is small (typically, smaller than 10), and rely on reducing this number by optimized biochemical specimen preparation protocols [START_REF] Elad | Detection and separation of heterogeneity in molecular complexes by statistical analysis of their two-dimensional projections[END_REF][START_REF] Elmlund | Ab initio structure determination from electron microscopic images of single molecules coexisting in different functional states[END_REF][START_REF] Fu | Unsupervised classification of single particles by cluster tracking in multidimensional space[END_REF][14][15][16][17]. However, as macromolecular complexes are not rigid but flexible entities, the obtained classes may not be perfectly homogeneous (particles assigned to the same class will rarely, if ever, have perfectly identical structures). This flexibility is usually referred to as conformational flexibility.

The class heterogeneity can also be partly explained by small errors made in determining the unknown parameters (orientation, position, and conformational state of each particle) due to a low signal-to-noise ratio (SNR) of cryo-EM images. Experimental techniques based on tilting the specimen have been proposed to reduce the number of unknown parameters [START_REF] Radermacher | Three-dimensional reconstruction from a single-exposure, random conical tilt series applied to the 50S ribosomal subunit of Escherichia coli[END_REF][START_REF] Leschziner | The orthogonal tilt reconstruction method: an approach to generating single-class volumes with no missing cone for ab initio reconstruction of asymmetric particles[END_REF][START_REF] Penczek | The ribosome at improved resolution: new techniques for merging and orientation refinement in 3D cryo-electron microscopy of biological particles[END_REF], but a low quality of tilted data often makes the particle sorting as difficult as when using only untilted images. Thus, this review will be focused on computational methods for analyzing conformational variability of particles without tilting the specimen.

For a long time, specimen heterogeneity had a completely negative connotation and was only seen as a factor limiting the resolution of 3D reconstruction. However, it has recently been shown that the identification of conformational transitions from heterogeneous samples can be useful for studying molecular mechanism of action of complexes [START_REF] Jin | Iterative elastic 3D-to-2D alignment method using normal modes for studying structural dynamics of large macromolecular complexes[END_REF][START_REF] Dashti | Trajectories of the ribosome as a Brownian nanomachine[END_REF][START_REF] Behrmann | Structural snapshots of actively translating human ribosomes[END_REF][START_REF] Banerjee | 2.3 A resolution cryo-EM structure of human p97 and mechanism of allosteric inhibition[END_REF][START_REF] Abeyrathne | Ensemble cryo-EM uncovers inchworm-like translocation of a viral IRES through the ribosome[END_REF][START_REF] Zhou | Structure and conformational states of the bovine mitochondrial ATP synthase by cryo-EM[END_REF]. These findings have changed our regard about specimen heterogeneity. In particular, they opened doors to studying continuous conformational changes (a continuum of conformational states rather than a few discrete states). The development of methods that explicitly address continuous conformational changes is currently in progress [START_REF] Jin | Iterative elastic 3D-to-2D alignment method using normal modes for studying structural dynamics of large macromolecular complexes[END_REF][START_REF] Dashti | Trajectories of the ribosome as a Brownian nanomachine[END_REF].

Standard, class-based methods assuming a few discrete states will here be referred to as discrete-state methods while those exploring continuous conformational changes will be referred to as continuous-state methods. Among discrete-state methods, those performing the conformational variability analysis in 2D use either no prior structural information (ab initio methods) [START_REF] Elad | Detection and separation of heterogeneity in molecular complexes by statistical analysis of their two-dimensional projections[END_REF][START_REF] Elmlund | Ab initio structure determination from electron microscopic images of single molecules coexisting in different functional states[END_REF][START_REF] Orlova | Methods for three-dimensional reconstruction of heterogeneous assemblies[END_REF][START_REF] Elmlund | Cryogenic electron microscopy and single-particle analysis[END_REF] or a 3D preliminary model to orient images [START_REF] Fu | Unsupervised classification of single particles by cluster tracking in multidimensional space[END_REF][START_REF] Hall | Cross-correlation of common lines: a novel approach for single-particle reconstruction of a structure containing a flexible domain[END_REF][START_REF] Shatsky | Automated multi-model reconstruction from single-particle electron microscopy data[END_REF][START_REF] Clare | Novel Inter-Subunit Contacts in Barley Stripe Mosaic Virus Revealed by Cryo-Electron Microscopy[END_REF]. Ab initio methods have a low robustness for low SNR data and have only been demonstrated in the context of separating images in two classes (e.g., small and large particles, ligand bound and unbound complexes, open and closed states). The main problem with methods using 3D preliminary models is that labeling of clusters in each projection direction, for their combination in multiple 3D reconstructions, may be relatively easy in the special, two-state case of presence and absence of an additional mass (e.g., bound and unbound ligand), but it is generally a difficult task. For these reasons, discrete-state methods performing conformational variability in 3D are currently more popular and will be reviewed here together with the latest developments for studying continuous conformational changes.

DISCRETE-STATE METHODS BASED ON CONFORMATIONAL VARIABILITY ANALYSIS IN 3D

Discrete-state methods that analyze conformational variability in 3D can be classified in the following three groups: multireference classification, maximum likelihood (ML) classification, and classification based on statistical analysis (Fig. 1).

Multireference classification

Supervised multireference classification approaches require good prior knowledge of all conformational states coexisting in the sample. They use 3D references with expected features (also referred to as templates) to assign, to each particle image, the conformational state of the most similar 2D projection of 3D templates [START_REF] Valle | Cryo-EM reveals an active role for aminoacyl-tRNA in the accommodation process[END_REF][START_REF] Gao | Dynamics of EF-G interaction with the ribosome explored by classification of a heterogeneous cryo-EM dataset[END_REF]. The main problem with these approaches is a bias towards the 3D templates as they are usually chosen subjectively.

Approaches that iteratively refine alignment, reconstruction, and classification help reduce supervision and bias. They belong to the class of K-means clustering algorithms, with a first approach of this type (developed for 2D classification) dating back to 1985 [START_REF] Van Heel | Characteristic views of E. coli and B. stearothermophilus 30S ribosomal subunits in the electron microscope[END_REF]. In each iteration of 3D iterative multireference classification approaches, each image is assigned the conformational state, orientation, and translation parameters of the most similar 2D projection of 3D references and a 3D reconstruction is computed from each class of images (determined by the assigned conformational state) to update the 3D references for the next iteration [START_REF] Heymann | Dynamics of herpes simplex virus capsid maturation visualized by time-lapse cryo-electron microscopy[END_REF][START_REF] Lukoyanova | Conformational changes during pore formation by the perforin-related protein pleurotolysin[END_REF]. Iterations are performed until obtaining stable 3D references. A good initial guess and a small number of necessary 3D references are required for a good performance of these methods. An approach adding 3D references incrementally has also been proposed [START_REF] Loerke | Multiparticle cryo-EM of ribosomes[END_REF], which makes the competition of 3D references for particles stronger and reduces the initial reference bias. This bias can alternatively be reduced by combining multireference classification with ML methods (discussed next), as shown in [START_REF] Fischer | Structure of the E. coli ribosome-EF-Tu complex at <3 A resolution by Cs-corrected cryo-EM[END_REF].

ML classification

ML methods estimate a set of density maps that best describe the given heterogeneous set of images while assuming independence among data pixels and Gaussian white noise model in real space or reciprocal space [14,15, [START_REF] Scheres | Disentangling conformational states of macromolecules in 3D-EM through likelihood optimization[END_REF][START_REF] Scheres | Modeling experimental image formation for likelihood-based classification of electron microscopy data[END_REF][START_REF] Scheres | A Bayesian view on cryo-EM structure determination[END_REF]. In a simplified form, they can be seen as multireference classification methods where the discrete assignments of image orientation, translation, and class membership (to one of a fixed number of classes) are replaced by probability-weighted integrations over all possible assignments. Each image contributes to all orientations and translations, and to all classes with some weight. These methods are less susceptible to initial model bias and overrefinement, especially with low SNR data. Several variants of the ML approach are available in EM software such as XMIPP [START_REF] De La Rosa-Trevin | Xmipp 3.0: an improved software suite for image processing in electron microscopy[END_REF], RELION [14], and FREALIGN [15]. Among them, implementations in RELION and FREALIGN are currently most popular [START_REF] Banerjee | 2.3 A resolution cryo-EM structure of human p97 and mechanism of allosteric inhibition[END_REF][START_REF] Abeyrathne | Ensemble cryo-EM uncovers inchworm-like translocation of a viral IRES through the ribosome[END_REF][START_REF] Zhou | Structure and conformational states of the bovine mitochondrial ATP synthase by cryo-EM[END_REF][START_REF] Bai | Sampling the conformational space of the catalytic subunit of human gamma-secretase[END_REF][START_REF] Nguyen | Cryo-EM structure of the yeast U4/U6.U5 tri-snRNP at 3.7 A resolution[END_REF]. While the FREALIGN approach assumes independence of real-space pixels (allowing to easily mask noise around the particle), the RELION approach assumes independence of reciprocal-space pixels (allowing to easily take into account the contrast transfer function of the microscope). Finally, a zero-mean Gaussian prior on reciprocal-space pixels, in RELION, makes a smoothing effect that mitigates accumulation of noise in the 3D reconstruction during the refinement process.

ML methods are local multireference refinement methods, meaning that their results depend on initial 3D references. Incorrect initial references may lead to incorrect results. The initial references can be obtained by performing an iteration of ML optimization for randomly drawn subsets of data [START_REF] Scheres | Disentangling conformational states of macromolecules in 3D-EM through likelihood optimization[END_REF][START_REF] Scheres | A Bayesian view on cryo-EM structure determination[END_REF], by calculating reconstructions from random subsets of data as in the bootstrap approach (discussed next) [START_REF] Penczek | Estimation of variance in single-particle reconstruction using the bootstrap technique[END_REF], or by using known templates as in supervised multireference classification [START_REF] Valle | Cryo-EM reveals an active role for aminoacyl-tRNA in the accommodation process[END_REF]. A low-pass filtering of initial references to 40-80 Å is normally recommended to reduce bias. Also, as the convergence of ML methods is not guaranteed, several rounds of them are usually required, following a hierarchical scheme using heuristic criteria. The requirement for an initial setting (guessing) of the number of classes and the assumption of discrete conformational changes are the main limitations of ML methods. Different numbers of classes should be tested to find the largest number that produces classes with new features [START_REF] Scheres | Classification of structural heterogeneity by maximum-likelihood methods[END_REF]. When the underlying changes are continuous, discrete classes cannot be meaningfully defined, even if the number of classes is increased at the price of higher computational cost, due to random fluctuations in the sampled density of states [START_REF] Frank | Continuous changes in structure mapped by manifold embedding of single-particle data in cryo-EM[END_REF].

Classification based on statistical analysis

Random resampling of a set of images allows estimating a global 3D variability from the variability of subsets. The global 3D voxel-by-voxel variance can be calculated based on a posteriori analysis of a large series of 3D reconstructions from sets of images obtained by random, bootstrap resampling of the given set of images [START_REF] Penczek | Estimation of variance in single-particle reconstruction using the bootstrap technique[END_REF]. The new sets, of the same size as the given set, are generated using a combination of duplication and removal of images randomly selected from the given set of images. Another approach to compute the 3D variance is by 3D reconstruction from 2D variance images calculated from particle images assigned to the same projection directions, where the projection-direction assignment is done by image alignment with a low-resolution preliminary model [START_REF] Behrmann | Structural snapshots of actively translating human ribosomes[END_REF]. Penczek and collaborators have showed that 3D variance can be used to localize variable areas in the initial 3D reconstruction (obtained by combining all images) and sort particles in two classes corresponding to ligand binding and unbinding, which is referred to as focused classification [16]. Data classification based on eigenvector analysis (principal component analysis (PCA) or multivariate statistical analysis (MSA)) of a series of 3D reconstructions from randomly selected subsets of images has also been proposed [17,[START_REF] Klaholz | Structure sorting of multiple macromolecular states in heterogeneous cryo-EM samples by 3D multivariate statistical analysis[END_REF].

Resampling-based methods do not require a prior knowledge of conformers, but rely on a preliminary model (usually obtained by combining all images) to assign orientation and translation parameters to each image. While multireference and ML classification methods require that the number of classes is set before the data analysis (ideally, the number of classes should be known a priori), resampling-based methods allow setting this number at a later step (the number of classes can be determined after the 3D variance analysis, by making a balance between intraclass and interclass variances, which is less arbitrary than the setting of this number in the case of multireference and ML classification methods).

Interestingly enough, methods based on eigenvector analysis allow mapping of the entire set of images onto a common low-dimensional space determined by the most important eigenvectors [17,45]. Such map of images can reveal whether the underlying conformational change is discrete or continuous, if the image mapping space is determined using eigenvectors of the actual covariance matrix. However, an efficient estimation of the covariance matrix is currently limited to images of small sizes [45] or image regions [46]. Alternatively, eigenvectors of this matrix can be estimated without the matrix estimation [17,47]. While the method proposed in [17] estimates the eigenvectors using a series of 3D reconstructions from random subsets of images, the method proposed in [47] estimates the eigenvectors directly from images using a likelihood-based approach to PCA. The covariance matrix can be assembled from the estimated eigenvectors, but its accuracy is not guaranteed due to the estimation errors.

CONTINUOUS-STATE METHODS

While discrete-state methods assume a few distinct conformational states coexisting in the sample, continuous-state methods assume a continuum of conformational states i.e. continuous conformational changes and are under development. Currently, only two approaches consider continuous conformational changes explicitly. They are usually referred to as HEMNMA (Hybrid Electron Microscopy Normal Mode Analysis) [7,48] and manifold embedding [START_REF] Dashti | Trajectories of the ribosome as a Brownian nanomachine[END_REF][START_REF] Frank | Continuous changes in structure mapped by manifold embedding of single-particle data in cryo-EM[END_REF]. These two approaches are presented in Figure 2 and discussed here. They represent images in a low-dimensional space specifically suited to the continuous nature of conformational changes and allow a 3D visualization of conformational changes along trajectories in this space.

Manifold embedding

The manifold embedding approach [START_REF] Dashti | Trajectories of the ribosome as a Brownian nanomachine[END_REF] analyzes conformational variability in 2D space determined by one projection direction (using images with virtually the same orientations) and, then, combines the conformational variability information obtained in different projection directions to visualize it in 3D space. In each projection direction, it maps images onto a low-dimensional space using the diffusion map technique, which is a nonlinear dimensionality reduction technique based on computing eigenvectors and eigenvalues of a diffusion operator on the data. The manifold embedding approach requires that the image orientation is determined first. It assumes that effects of orientational changes dominate those of conformational changes, meaning that heterogeneity is not excessive so that each image can be associated with the correct projection direction using standard methods that do not take into account conformational heterogeneity (e.g., projection matching with a density map reconstructed from the entire, heterogeneous set of images).

HEMNMA HEMNMA [7] analyzes and visualizes conformational variability directly in 3D space. It first iteratively computes the parameters of orientation, translation, and conformation for each image. More precisely, a reference (pseudo)atomic structure (an input atomic structure or a pseudoatomic structure computed from an input EM density map [49]) is elastically deformed using normal modes, the deformed structure is converted into a density map, and 2D projections of that map are compared with each image until the best matching 2D projection (the best matching density map) is found for this image, which determines its optimal Euler angles, in-plane translations, and conformational parameters (M displacement amplitudes along M normal modes). HEMNMA minimizes the risk of initial model bias by using large populations of different test density maps for different images (the density maps generated by deforming the reference (pseudo)atomic structure). The conformational parameters determined for the ensemble of images are then analyzed by PCA or other linear dimensionality reduction method to map images onto a low-dimensional space. Trajectories of conformational changes may be identified by exploring the most densely populated regions in the low-dimensional space and the reference (pseudo)atomic structure can then be displaced along the trajectories to visualize the changes in 3D. Also, density maps can be reconstructed along the trajectories from images with similar conformations. A user-friendly HEMNMA graphical interface is available in Xmipp and Scipion [48]. The graphical interface additionally allows low-dimensional image mapping using nonlinear dimensionality reduction methods, but the trajectory animation is unavailable when using nonlinear methods (the conversion into the original displacement space cannot be done in such cases) [48].

Combining continuous-state methods with discrete-state methods

The 3D density maps reconstructed along a trajectory obtained with a continuous-state method can be regarded as discrete samples of a continuous trajectory. Extrapolation of continuous trajectories from their discrete, unordered samples obtained by discrete-state methods has also been addressed. In this context, the method referred to as StructMap projects a set of 3D density maps obtained by discrete-state methods onto a low-dimensional space of their conformational distances [50]. StructMap models each density map by elastic deformations (using normal modes) of other density maps and performs a statistical analysis of their differences to project the maps onto a common low-dimensional space. Distances among density maps in the low-dimensional space can be analyzed to select maps that would later be used to finely extrapolate continuous trajectories by analyzing images with HEMNMA or with manifold embedding [50]. The selected maps would be used to compute the reference pseudoatomic structures for HEMNMA or to orient images for manifold embedding via projection matching [50]. An illustration of combining discrete-state and continuous-state methods is shown in Figure 3.

DISCUSSION AND CONCLUSION

More often than to study conformational transitions, discrete-state classification methods are used to obtain high-resolution reconstruction of single conformations. Within the highresolution reconstruction strategies, classification methods are used to select a subset of images containing particles with most consistent views and conformations (i.e. only those assigned to the classes of highest resolution), and the 3D reconstruction is then computed using only that image subset. In this context, many particle images are thrown away without fully understanding reasons for their inconsistence with other particles. For instance, a 3D reconstruction at near-atomic resolution is sometimes obtained by collecting ~1 million particle images, but retaining only one half after a 2D classification and less than one fourth for the final 3D reconstruction [51].

However, the classes of lower resolution could come from a mixture of particles with different (possibly unique) conformations that are difficult to represent with the given, usually small number of classes. Discrete-state methods may provide a limited view of data heterogeneity due to the use of a small number of classes. Also, different discrete-state methods may produce different density maps using the same heterogeneous set of images, as in the case of a publicly available set of images of different states of EF-G binding to the 70S E. coli ribosome (a table showing the results obtained with this data set and different discretestate methods is provided in [START_REF] Elmlund | Cryogenic electron microscopy and single-particle analysis[END_REF]). Continuous-state methods can provide a broader view of data heterogeneity than discrete-state methods, which was shown in [7] using the mentioned set of images of mixed states of EF-G binding to the 70S E. coli ribosome and other test data sets. Also, they can help identify trajectories of conformational changes. Furthermore, the 3D reconstruction at high resolution is possible from subsets of images along the trajectories, but requires enough large and homogeneous image subsets. Continuous-state methods are under active development and are expected to have high impact on studies of dynamics of macromolecular complexes.

Figure 1 :

 1 Figure 1: Discrete conformational analysis methods reviewed here, referred to as discretestate methods.

Figure 2 :

 2 Figure 2: Continuous conformational analysis methods reviewed here, referred to as continuous-state methods.

Figure 3 :

 3 Figure 3: HEMNMA initialized with StructMap in the context of combining discrete-state and continuous-state methods. (A) StructMap projects a set of EM density maps obtained by a discrete-state method (here, ML classification method proposed in[START_REF] Scheres | Disentangling conformational states of macromolecules in 3D-EM through likelihood optimization[END_REF]) onto a lowdimensional (here, 1D) density-map distance space (in this space, each density map is marked

implementation of a Bayesian approach to cryo-EM structure determination

  The author thanks GENCI-CINES/IDRIS for HPC resources[x2014072174, x2015072174, x2016072174]; This is the author's version of an article that has been published in Current Opinion in Structural Biology. Changes were made to this version by the publisher prior to publication. The final version is available at http://dx.doi.org/ 10.1016/j.sbi.2016.12.011 since 11 January 2017. This article introduces RELION software and shows how empirical Bayes method can be used for a high-resolution density map refinement.

	series of 3D reconstructions from randomly selected subsets of images, used already in 2008,
	was described and demonstrated in more details.
	 45. Katsevich E, Katsevich A, Singer A: Covariance Matrix Estimation for the Cryo-EM
	Heterogeneity Problem. SIAM J Imaging Sci 2015, 8:126-185. This article describes a
	methodology for estimating the entire actual covariance matrix from a heterogeneous set of
	particle images.
	 46. Liao HY, Hashem Y, Frank J: Efficient
	 15. Lyumkis D, Brilot AF, Theobald DL, Grigorieff N: Likelihood-based classification of cryo-EM
	images using FREALIGN. J Struct Biol 2013, 183:377-388. This article describes the likelihood-
	based method combining 3D multiconformation alignment, classification, and refinement
	that is available in FREALIGN. The authors point out that both variants of maximum-
	likelihood approach, the one of FREALIGN and the one of RELION, are extended likelihood or
	empirical Bayes methods as both of them estimate hyperparameters of hierarchical prior
	distributions from the data using variants of maximum-likelihood methodology. However,
	the article shows that slightly better results may be obtained with RELION in some data
	cases.
	16. Penczek PA, Frank J, Spahn CM: A method of focused classification, based on the bootstrap 3D
	variance analysis, and its application to EF-G-dependent translocation. J Struct Biol 2006,
	154:184-194.
	 17. Penczek PA, Kimmel M, Spahn CM: Identifying conformational states of macromolecules by
	eigen-analysis of resampled cryo-EM images. Structure 2011, 19:1582-1590. This article
	describes a statistical analysis approach to 3D reconstruction of multiple conformational
	states from a heterogeneous set of images that is based on estimating eigenvectors of the
	covariance matrix without estimating this matrix. The eigenvectors are computed by
	principal component analysis of a series of 3D reconstructions from randomly selected
	subsets of images, and the images are classified after their projection onto a low-dimensional
	space determined by the most important eigenvectors, which allows a posterior
	determination of the number of classes.

 14. Scheres SH: RELION: . J Struct Biol 2012, 180:519-530.

estimation of three-dimensional covariance and its application in the analysis of heterogeneous samples in cryo-electron microscopy.

  Structure 2015, 23:1129-1137. Rather than estimating the entire covariance matrix, from a heterogeneous set of particle images, this article proposes the estimation in regions of interest to make it more efficient. 262. This article describes a likelihood-based approach to principal component analysis of a heterogeneous set of particle images. This approach computes eigenvectors of the covariance matrix directly from images without estimating this matrix.

 47. Tagare HD, Kucukelbir A, Sigworth FJ, Wang H, Rao M: Directly reconstructing principal components of heterogeneous particles from cryo-EM images. J Struct Biol 2015, 191:245- 48. Sorzano CO, de la Rosa-Trevin JM, Tama F, Jonic S: Hybrid Electron Microscopy Normal Mode Analysis graphical interface and protocol. J Struct Biol 2014, 188:134-141. This article describes a user-friendly graphical interface and a detailed protocol for analyzing continuous conformational changes with HEMNMA, which was out of scope of the article where HEMNMA was introduced. 49. Jonic S, Sorzano COS: Coarse-

graining of volumes for modeling of structure and dynamics in electron microscopy: Algorithm to automatically control accuracy of approximation

. IEEE Journal of Selected Topics in Signal Processing 2016, 10:161 -173.  50. Sanchez Sorzano CO, Alvarez-Cabrera AL, Kazemi M, Carazo JM, Jonic S: StructMap

: Elastic Distance Analysis of Electron Microscopy Maps for Studying Conformational Changes. Biophys J 2016, 110:1753-1765.

  This article describes the StructMap method that projects a given set of EM density maps, obtained by a discrete-state method, onto a low-dimensional space of structural differences (distance space) and that can be combined with HEMNMA. Also, the article addresses extrapolation of continuous trajectories from their discrete, unordered samples obtained by discrete-state methods. This is the author's version of an article that has been published in Current Opinion in Structural Biology. Changes were made to this version by the publisher prior to publication. The final version is available at http://dx.doi.org/ 10.1016/j.sbi.2016.12.011 since 11 January 2017.

	51. Walls AC, Tortorici MA, Bosch BJ, Frenz B, Rottier PJ, DiMaio F, Rey FA, Veesler D: Cryo-electron
	microscopy structure of a coronavirus spike glycoprotein trimer. Nature 2016, 531:114-117.

FIGURES

ACKNOWLEDGMENTS

This is the author's version of an article that has been published in Current Opinion in Structural Biology. Changes were made to this version by the publisher prior to publication. The final version is available at http://dx.doi.org/ 10.1016/j.sbi.2016.12.011 since 11 January 2017.

This is the author's version of an article that has been published in Current Opinion in Structural Biology. Changes were made to this version by the publisher prior to publication. The final version is available at http://dx.doi.org/ 10.1016/j.sbi.2016.12.011 since 11 January 2017.


Student Member, IEEE Lilei Zheng

Stefan Duffner

Khalid Idrissi

Christophe Garcia

Atilla Baskurt

Pairwise Identity Verification via Linear Concentrative Metric Learning

Keywords: metric learning, siamese neural networks, face verification, speaker verification, identity verification, pairwise metric !

This paper presents a study of metric learning systems on pairwise identity verification, including pairwise face verification and pairwise speaker verification, respectively. These problems are challenging because the individuals in training and testing are mutually exclusive, and also due to the probable setting of limited training data. For such pairwise verification problems, we present a general framework of metric learning systems and employ the stochastic gradient descent algorithm as the optimization solution. We have studied both similarity metric learning and distance metric learning systems, of either a linear or shallow nonlinear model under both restricted and unrestricted training settings. Extensive experiments demonstrate that with limited training pairs, learning a linear system on similar pairs only is preferable due to its simplicity and superiority, i.e. it generally achieves competitive performance on both the LFW face dataset and the NIST speaker dataset. It is also found that a pre-trained deep nonlinear model helps to improve the face verification results significantly.

INTRODUCTION

T HE task of pairwise identity verification is to verify whether a pair of biometric identity samples corresponds to the same person or not, where the identity samples can be face images, speech utterances or any other biometric information from individuals. Formally, in such pairwise verification problems, two identity samples of the same person are called a similar pair, and two samples of two different persons are called a dissimilar pair or a different pair.

Compared with the traditional identity classification task in which a decision of acceptance or rejection is made by comparing an identity sample to models (or templates) of each individual [START_REF] Matas | Comparison of face verification results on the XM2VTFS database[END_REF], [START_REF] Reynolds | Speaker identification and verification using gaussian mixture speaker models[END_REF], [START_REF] Tao | Person reidentification by minimum classification error-based kiss metric learning[END_REF], pairwise identity verification is more challenging because of the impossibility of building robust identity models with enough training data [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF] for all the individuals. Actually, there may be only one identity sample available for some individuals in pairwise identity verification. Besides, individuals in training and testing should be mutually exclusive, i.e. the testing set comprises only samples from unknown persons that are not part of the training set.

Face images or speech utterances may be the most accessible and widely used identity information. As a result, face verification [START_REF] Matas | Comparison of face verification results on the XM2VTFS database[END_REF] and speaker verification [START_REF] Reynolds | Speaker identification and verification using gaussian mixture speaker models[END_REF] has been well studied over the last two decades. Especially, pairwise face verification has drawn much attention in recent years thanks to the popularity of the dataset 'Labeled Faces in the Wild' (LFW) [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF]. Originally, the LFW dataset proposed a restricted training protocol where only a few specified data pairs are allowed for training, a challenging setting for

• All the authors are with Université de Lyon, CNRS, INSA-Lyon, LIRIS, UMR5205, F-69621, France (e-mail: lilei.zheng@liris.cnrs.fr; lzheng@nwpu-aslp.org; stefan.duffner@liris.cnrs.fr; khalid.idrissi@liris.cnrs.fr; christophe.garcia@liris.cnrs.fr; atilla.baskurt@liris.cnrs.fr).

Manuscript received April 19, XXXX; revised September 17, XXXX.

effective learning algorithms to discover principles from a small number of training examples, just like the human beings [START_REF] Learned-Miller | Labeled faces in the wild: A survey[END_REF]. On the other hand, in the NIST Speaker Recognition Evaluations (SREs) since 1996, various speaker verification protocols have been investigated [START_REF] Martin | The NIST 2010 speaker recognition evaluation[END_REF], [START_REF] Greenberg | The NIST 2014 speaker recognition i-vector machine learning challenge[END_REF]. In order to follow the pair generation scheme in the LFW standard protocol, we establish the pairwise speaker verification protocol based on the data from the NIST 2014 i-Vector Machine Learning Challenge [START_REF] Greenberg | The NIST 2014 speaker recognition i-vector machine learning challenge[END_REF].

The definition of pairwise identity verification reveals the need of measuring the difference or similarity between a pair of samples, which naturally leads us to the study of metric learning [START_REF] Bellet | A survey on metric learning for feature vectors and structured data[END_REF], i.e. methods that automatically learn a metric from a set of data pairs. A metric learning framework is implemented with a siamese architecture [START_REF] Bromley | Signature verification using a Siamese time delay neural network[END_REF] which consists of two identical sub-systems sharing the same set of parameters. For a given input data pair, the two samples are processed by the two sub-systems respectively. The overall system includes a cost function parameterizing the pairwise relationship between data and a mapping function allowing the system to learn high-level features from the training data.

In terms of the cost function, one can divide metric learning methods into distance metric learning and similarity metric learning, where the cost function is defined based on a distance metric and a similarity measurement, respectively. The objective of such a cost function is to increase the similarity value or to decrease the distance between a similar pair, and to reduce the similarity value or to increase the distance between two dissimilar data samples. In this paper, we investigate two kinds of metric learning methods, namely, Triangular Similarity Metric Learning (TSML) [START_REF] Zheng | Triangular similarity metric learning for face verification[END_REF] and Discriminative Distance Metric Learning (DDML) [START_REF] Hu | Discriminative deep metric learning for face verification in the wild[END_REF].

In terms of the mapping function, one can divide metric learning methods into two main families: linear metric learning and nonlinear metric learning. Up to now, work in metric learning has focused on linear methods because they are more convenient to optimize and less prone to over-fitting. For instance, the best approaches such as the Within Class Covariance Normalization (WCCN) and Cosine Similarity Metric Learning (CSML), have shown their effectiveness on the problem of pairwise face verification [START_REF] Hieu | Cosine similarity metric learning for face verification[END_REF], [START_REF] Barkan | Fast high dimensional vector multiplication face recognition[END_REF]. Also, a few approaches have investigated nonlinear metric learning and have shown competitive performance on some classification problems [START_REF] Hu | Discriminative deep metric learning for face verification in the wild[END_REF], [START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF], [START_REF] Kedem | Non-linear metric learning[END_REF]. Moreover, comparing linear systems with their nonlinear variants on a common ground helps to study the effect of nonlinearity on pairwise verification. For example, the nonlinear transformation -Diffusion Maps (DM) -has been introduced to face verification [START_REF] Barkan | Fast high dimensional vector multiplication face recognition[END_REF] and speaker verification [START_REF] Barkan | Diffusion maps for PLDAbased speaker verification[END_REF], respectively. However, no clear evidence in the comparisons validated the universal effectiveness of DM over the linear systems [START_REF] Barkan | Fast high dimensional vector multiplication face recognition[END_REF]. Analogously, we present the TSML and DDML methods in both linear and nonlinear formulations for the sake of a thorough evaluation. Note that the nonlinear formulations are developed on the linear ones by adding nonlinear activation functions or stacking one more layer of transformation, thus the implemented nonlinearity is shallow.

Overall, on the problem of pairwise identity verification via metric learning, this paper presents a comprehensive study including two kinds of verification applications (i.e. face verification and speaker verification), two kinds of training settings (i.e. data-restricted and data-unrestricted), two kinds of metric learning cost functions (i.e. TSML and DDML), and three kinds of mapping functions (i.e. linear function, single-layer nonlinear function and multi-layer nonlinear function).

We will show that under the setting of limited training data, a linear metric learning system trained on similar pairs only generally yields competitive verification results. Either linear TSML or linear DDML achieves the state-of-the-art performance on both the LFW image dataset and the NIST speaker dataset.

The contributions of this paper with respect to previous works are the following:

• we establish a pairwise speaker verification protocol based on the data from the NIST 2014 i-Vector machine learning challenge, which has mutually exclusive training and test sets of speakers. Both the pairwise face verification protocol of the LFW dataset and this speaker verification task aim at verifying identity information by individuals' biometric features. Another objective of using the two datasets is to show the effectiveness of the proposed metric learning systems on different kinds of data, i.e. images and speech.

• we present the TSML and DDML methods in both linear and nonlinear formulations for pairwise identity verification problems. A thorough evaluation comparing the different formulations has shown that with limited training data, the linear models are preferable due to its superior performance and its simplicity.

• we study the influence of limited training data. Generally, compared with unlimited training, the limited case suffers from over-fitting. However, we find that training the linear models on similar pairs only considerably reduces the effect of over-fitting to limited training data.

• we also integrate the proposed linear and shallow nonlinear metric learning models with a pre-trained deep Convolutional Neural Network (CNN) model to improve the performance of pairwise face verification. We find that the linear model serves as an effective verification layer stacked to the deep CNN.

The remainder of this paper is organized as follows: Section 2 briefly summarizes the related work on metric learning and feature representations for images and speech. Section 3 presents the objective of metric learning by illustrating the cost functions of TSML and DDML. Section 4 introduces the linear and nonlinear formulations and explains the details of our stochastic gradient descent algorithm for optimization. Section 5 describes the datasets and experiments for pairwise face verification and pairwise speaker verification. Finally, we draw our conclusions in Section 6.

RELATED WORK

Metric Learning and Siamese Neural Networks

Most of linear metric learning methods employ two types of metrics: the Mahalanobis distance or a more general similarity metric. In both of the two cases, a linear transformation matrix W is learnt to project input features into a target space. Typically, distance metric learning concerns the Mahalanobis distance [START_REF] Xing | Distance metric learning with application to clustering with side-information[END_REF], [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF]: d W (x, y) = (x -y) T W (x -y), where x and y are two sample vectors, and W is the matrix that needs to be learnt. Note that when W is the identity matrix, d W (x, y) is the Euclidean distance. In contrast, similarity metric learning methods learn a function of the following form: s W (x, y) = x T W y/N (x, y), where N (x, y) is a normalization term [START_REF] Qamar | Similarity learning for nearest neighbor classification[END_REF]. Specifically, when N (x, y) = 1, s W (x, y) is the bilinear similarity function [START_REF] Chechik | Large scale online learning of image similarity through ranking[END_REF]; when N (x, y) = √

x T W x y T W y, s W (x, y) is the generalized cosine similarity function [START_REF] Hieu | Cosine similarity metric learning for face verification[END_REF].

Nonlinear metric learning methods are constructed by simply substituting the above linear projection with a nonlinear transformation [START_REF] Hu | Discriminative deep metric learning for face verification in the wild[END_REF], [START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF], [START_REF] Kedem | Non-linear metric learning[END_REF], [START_REF] Yu | Deep multimodal distance metric learning using click constraints for image ranking[END_REF]. For example, [START_REF] Hu | Discriminative deep metric learning for face verification in the wild[END_REF] and [START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF] employed neural networks to accomplish the nonlinear transformation. These nonlinear methods are subject to local optima and more inclined to over-fit to the training data but have the potential to outperform linear methods on some problems [START_REF] Bellet | A survey on metric learning for feature vectors and structured data[END_REF], [START_REF] Kedem | Non-linear metric learning[END_REF]. Compared with linear models, nonlinear models are usually preferred on a redundant training set to well capture the underlying distribution of the data [START_REF] Lecun | Efficient backprop[END_REF].

Since neural networks are the most commonly used nonlinear models, nonlinear metric learning has a natural connection with siamese neural networks [START_REF] Bromley | Signature verification using a Siamese time delay neural network[END_REF], [START_REF] Chopra | Learning a similarity metric discriminatively, with application to face verification[END_REF]. Actually, siamese neural networks can also be linear if the neurons have a linear activation function. From this point of view, siamese neural networks and metric learning denote the same technique of optimizing a metric-based cost function via a linear or nonlinear mapping. The difference exists in their names: "siamese neural networks" concern the symmetric structure of neural networks used for data mapping but the term "metric learning" emphasizes the pairwise relationship (i.e. the metric) in the data space.

For readers interested in a broader scope on metric learning in the literature, we recommend a recent survey which has provided an up-to-date and critical review of existing metric learning methods [START_REF] Bellet | A survey on metric learning for feature vectors and structured data[END_REF]. For those who prefer experimental analysis, an overview and empirical comparison is given in [START_REF] Moutafis | An overview and empirical comparison of distance metric learning methods[END_REF].

Feature Representation for Face and Speaker

For face recognition, tremendous efforts have been put on developing robust face descriptors [START_REF] Barkan | Fast high dimensional vector multiplication face recognition[END_REF], [START_REF] Ma | Face recognition using eigenfaces[END_REF], [START_REF] Ahonen | Face recognition with local binary patterns[END_REF], [START_REF] Ke | PCA-SIFT: A more distinctive representation for local image descriptors[END_REF], [START_REF] Daugman | Complete discrete 2-D gabor transforms by neural networks for image analysis and compression[END_REF], [START_REF] Wolf | Descriptor based methods in the wild[END_REF], [START_REF] Hussain | Face recognition using local quantized patterns[END_REF], [START_REF] Simonyan | Fisher vector faces in the wild[END_REF], [START_REF] Chen | Blessing of dimensionality: High-dimensional feature and its efficient compression for face verification[END_REF], [START_REF] Chuan-Xian Ren | Enhanced local gradient order features and discriminant analysis for face recognition[END_REF]. Popular face descriptors include eigenfaces [START_REF] Ma | Face recognition using eigenfaces[END_REF], Gabor wavelets [START_REF] Daugman | Complete discrete 2-D gabor transforms by neural networks for image analysis and compression[END_REF], SIFT [START_REF] Ke | PCA-SIFT: A more distinctive representation for local image descriptors[END_REF], Local Binary Patterns (LBP) [START_REF] Ahonen | Face recognition with local binary patterns[END_REF], etc. Especially, LBP and its variants, such as center-symmetric LBP (CSLBP) [START_REF] Heikkilä | Description of interest regions with center-symmetric local binary patterns[END_REF], multi-block LBP (M-LLBP) [START_REF] Zhang | Face detection based on multi-block lbp representation[END_REF], three patch LBP (TPLBP) [START_REF] Wolf | Descriptor based methods in the wild[END_REF] and over-complete LBP (OCLBP) [START_REF] Barkan | Fast high dimensional vector multiplication face recognition[END_REF], have been proven to be effective at describing facial texture. Especially, the high-dimensional variants usually perform better, for example, OCLBP [START_REF] Barkan | Fast high dimensional vector multiplication face recognition[END_REF]. Recently, another high-dimensional candidate, Fisher Vector (FV) face, which combines dense feature sampling with improved Fisher Vector encoding, has achieved striking results on pairwise face verification [START_REF] Simonyan | Fisher vector faces in the wild[END_REF]. Besides, compared with the above handcrafted descriptors, automatical feature learning using Convolutional Neural Networks (CNN) has attracted a lot of interest in Computer Vision during the past decade [START_REF] Taigman | Deepface: Closing the gap to human-level performance in face verification[END_REF], [START_REF] Sun | Deep learning face representation by joint identification-verification[END_REF], [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF]. In contrast to the handcrafted features, these CNN-based approaches usually rely on large training data to learn a lot of parameters, but they have substantially raised the state-of-the-art records on almost all the challenges in Computer Vision [START_REF] Yann A Lecun | Deep learning[END_REF].

For speaker recognition, the most popular features are developed on generative models such as Gaussian Mixture Model-Universal Background Model (GMM-UBM) [START_REF] Reynolds | Speaker verification using adapted Gaussian mixture models[END_REF]. Building on the success of GMM-UBM, Joint Factor Analysis (JFA) proposes powerful tools to model the inter-speaker variability and to compensate for channel/session variability in the context of GMMs [START_REF] Kenny | A study of interspeaker variability in speaker verification[END_REF]. Moreover, inspired by JFA, a new feature called i-vector is developed [START_REF] Dehak | Front-end factor analysis for speaker verification[END_REF], [START_REF] Garcia | Analysis of ivector length normalization in speaker recognition systems[END_REF], [START_REF] Lei | A novel scheme for speaker recognition using a phoneticallyaware deep neural network[END_REF]. JFA models the speaker variability in the high-dimensional space of GMM supervectors, whereas i-vectors are extracted in a low-dimensional space named total variability space. Taking advantage of the low dimensionality of the total variability space, many machine learning techniques can be applied to speaker verification [START_REF] Larcher | Text-dependent speaker verification: Classifiers, databases and RSR2015[END_REF]. Probabilistic Linear Discriminant Analysis (PLDA) [START_REF] Simon | Probabilistic linear discriminant analysis for inferences about identity[END_REF] is one of the most popular techniques used for speaker verification: different variants such as the Gaussian PLDA (G-PLDA) [START_REF] Barkan | Diffusion maps for PLDAbased speaker verification[END_REF], [START_REF] Yaman | Using polynomial kernel support vector machines for speaker verification[END_REF], Heavy-Tailed PLDA (HT-PLDA) [START_REF] Kenny | Bayesian speaker verification with heavy-tailed priors[END_REF], [START_REF] Burget | Discriminatively trained probabilistic linear discriminant analysis for speaker verification[END_REF], [START_REF] Matějka | Full-covariance UBM and heavy-tailed PLDA in ivector speaker verification[END_REF] and Nonlinear PL-DA [START_REF] Novoselov | Non-linear PLDA for i-vector speaker verification[END_REF] have been studied. In addition, Pairwise Support Vector Machines (PSVM) [START_REF] Cumani | Fast discriminative speaker verification in the i-vector space[END_REF], [START_REF] Cumani | Large-scale training of pairwise support vector machines for speaker recognition[END_REF] have been proposed to verify utterance pairs of different speakers; and fusing PSVM with PLDA can further improve the verification performance [START_REF] Yaman | Using polynomial kernel support vector machines for speaker verification[END_REF]. Recently, the metric learning framework DDML [START_REF] Hu | Discriminative deep metric learning for face verification in the wild[END_REF] was also shown to be helpful for PLDA-based speaker verification [START_REF] Novoselov | Non-linear PLDA for i-vector speaker verification[END_REF].

In our experiments, instead of studying the CNN for face verification or the PLDA for speaker verification, we focus on investigating the same metric learning models on the Mapping function

) (⋅ f Mapping function ) (⋅ f W i x Cost function Attract similar pairs Separate dissimilar pairs i y ) , ( a W x f i i = ) , ( b W y f i i = ) (⋅ J Fig. 1.
The siamese structure used in metric learning approaches. The objective is to find an optimal mapping, making a similar pair to be more closer and a dissimilar pair further apart. two verification tasks. In terms of feature representations, we choose Fisher Vector faces as the face descriptors and i-vectors as the speech utterance descriptors.

METRIC LEARNING OBJECTIVES

Metric learning algorithms usually employ the siamese architecture [START_REF] Bromley | Signature verification using a Siamese time delay neural network[END_REF] to compare a pair of data inputs. Figure 1 shows the principal approach. A pair of data is given at the input, and two outputs are produced respectively with the current mapping function f (•). These outputs are constrained by a metric-based cost function J(•). By minimizing this cost function, we can achieve the objective of attracting similar pairs and separating dissimilar pairs. Concretely, if the pair of inputs are similar (i.e. from the same individual), the objective is to make the outputs more similar than the inputs; otherwise, the objective is to make the outputs more dissimilar/different. Popular choices of the measurement on the output vectors include the Euclidean distance [START_REF] Hu | Discriminative deep metric learning for face verification in the wild[END_REF], [START_REF] Weinberger | Distance metric learning for large margin nearest neighbor classification[END_REF] and the Cosine Similarity [START_REF] Hieu | Cosine similarity metric learning for face verification[END_REF], [START_REF] Chechik | Large scale online learning of image similarity through ranking[END_REF]. Therefore, we apply a distance metric learning method DDML [START_REF] Hu | Discriminative deep metric learning for face verification in the wild[END_REF] and a similarity metric learning method TSML [START_REF] Zheng | Triangular similarity metric learning for face verification[END_REF] for the problem of pairwise identity verification.

By representing the face images or speech utterances as numerical vectors, we use a triplet (x i , y i , s i ) to represent a pair of training input instances, where x i and y i are two vectors, and s i = 1 (respectively s i = -1) means that the two vectors are similar (respectively dissimilar). Taking a projection f (z, W ) on the inputs, we obtain a new pair (a i , b i ) in the target space, where a i = f (x i , W ) and b i = f (y i , W ). Then, the TSML or DDML cost function is constructed to define the pairwise relationship between a i and b i . Finally, the procedure of learning the metric is carried out by minimizing the cost on a set of training pairs.

Triangular Similarity Metric Learning

TSML concerns the Triangular Similarity which is equivalent to the Cosine Similarity [START_REF] Zheng | Triangular Similarity Metric Learning: a Siamese Architecture Approach[END_REF]. On the two outputs a i and b i , the cost function of TSML is defined as:

-1 1 -1 1 i a i b 1  i s i i i i i i b a b s a c     i a i b 1   i s i i i i i i b a b s a c       i a i b 1  i s i i i i i c c s c c  i a i b 1   i s   i i c c i i i c c s -1 1 -1 1 1  i s 1   i s i a i b 1  i s i i i i i c c s c c  i a i b 1   i s   i i c c i i i c c s (a) (b)
J i = 1 2 a i 2 + 1 2 b i 2 -c i + 1, (1)
where c i = a i + s i b i : c i can be regarded as one of the two diagonals of the parallelogram formed by a i and b i (Fig. 2(a)). Moreover, this cost function can be rewritten as:

J i = 1 2 ( a i -1) 2 + 1 2 ( b i -1) 2 + a i + b i -c i .
(2) We can see that minimizing the first part aims to make the vectors a i and b i having unit length 1; the second part concerns the well-known triangle inequality theorem: the sum of the lengths of two sides of a triangle must always be greater than the length of the third side, i.e. a i + b i -c i > 0. More interestingly, with the length constraints by the first part, minimizing the second part is equivalent to minimizing the angle θ inside a similar pair (s i = 1) or maximizing the angle θ inside a dissimilar pair (s i = -1), in other words, minimizing the Cosine Similarity between a i and s i b i :

cos(a i , s i b i ) = s i a T i b i a i b i . (3)
The gradient of the cost function (Equation ( 1)) with respect to the parameters W is:

∂J i ∂W = (a i - c i c i ) T ∂a i ∂W + (b i - s i c i c i ) T ∂b i ∂W . (4)
We can obtain the optimal cost at the zero gradient: a i -ci ci = 0 and b i -sici ci = 0. In other words, the gradient function has ci ci and sici ci as targets for a i and b i , respectively. Fig. 2(b) illustrates that: for a similar pair, a i and b i are mapped to the same target vector along the diagonal (the red solid line); for a dissimilar pair, a i and b i are mapped to opposite unit vectors along the other diagonal (the blue solid line). This perfectly reveals the objective of attracting similar pairs and separating dissimilar pairs.

Discriminative Distance Metric Learning

In contrast, DDML focuses on the pairwise distance between feature vectors. Unlike the Cosine Similarity naturally defines a minimum of -1 and a maximum of 1, the Euclidean distance has only a minimum of 0 and no maximum. Hence a margin is usually defined in distance metric learning to assume that two vectors with a distance larger than the margin are well separated. Typically, for a pair of outputs a i and b i , DDML defines the cost function as:

J i = 1 2 g(1 -s i (1 -(a i -b i ) 2 )), (5)
where g(z) = 1 T log(1 + exp(T z)) is the generalized logistic loss function [START_REF] Mignon | Pcca: A new approach for distance learning from sparse pairwise constraints[END_REF], T is a sharpness parameter usually set to 10. Minimizing the logistic loss function means to minimize the value of

z i = 1 -s i (1 -(a i -b i ) 2 ). (6)
Specifically, for a similar pair (s i = 1), z i can be simplified as (a i -b i ) 2 , and minimizing z i requires a i and b i to be identical; for a dissimilar pair (s i = -1), the equation suggests maximizing

-z i = (a i -b i ) 2 -2,
that is to separate a dissimilar pair with a distance of √ 2. An illustration of the objective is shown in Fig. 3.

The gradient of the DDML cost function (Equation ( 5)) with respect to the parameters W is:

∂J i ∂W = s i (a i -b i ) 1 + exp(-T (1 -s i + s i (a i -b i ) 2 )) ∂(a i -b i ) ∂W . (7)

Cost and Gradient for Batch Training

In practice, we may consider a few data pairs as a small batch in each training iteration, thus the overall cost and gradient of a batch is simply the average from all the training pairs in the batch:

J = 1 n n i=1 J i , (8a)
∂J ∂W = 1 n n i=1 ∂J i ∂W , ( 8b
)
where n is the number of training pairs in a batch, J i is the TSML cost in Equation ( 1) or the DDML cost in Equation ( 5), the corresponding gradient ∂Ji ∂W is calculated by Equation (4) or Equation [START_REF] Greenberg | The NIST 2014 speaker recognition i-vector machine learning challenge[END_REF]. Finally, the gradient can be used in the Backpropagation algorithm [START_REF] David E Rumelhart | Learning internal representations by error propagation[END_REF] to perform gradient descent and search an optimal solution.

LINEAR AND NONLINEAR MAPPINGS

When a cost function defines the pairwise relationship between data in the target space, a mapping function represents the system's ability of learning to achieve the goal of the cost function. From the point of view of neural networks, different mapping functions can be considered as different combinations of neurons in network layers. We study three kinds of mapping functions here:

Single layer of linear neurons

The simplest neurons are the linear neurons without bias term which only involve a parameter matrix W . For a given input z ∈ R d , the output is simply f (z, W ) = W z. For instance, the TSML gradient of the i th pair with respect to the parameter matrix W is:

∂J i ∂W = (a i - c i c i )x T i + (b i -s i c i c i )y T i . (9)

Single layer of nonlinear neurons

Besides the parameter matrix W , nonlinear neurons involve a bias term, and a nonlinear activation function, e.g. the tanh function [START_REF] Lecun | Efficient backprop[END_REF]. For a given input z ∈ R d , the output is:

f (z, W ) = tanh(W z + h), (10)
where h denotes the bias term of the neurons. This equation can be rewritten as:

f (z , W ) = tanh(W z ), (11)
where z = [z; 1] and W = [W h]. Remind that derivative of the tanh function is tanh (z) = 1 -tanh 2 (z). Based on the linear case in Equation ( 9), the derivative of the TSML cost function with respect to the parameters W : {W, h} is:

∂J i ∂W = (a i - c i c i ) ∂a i ∂W + (b i - s i c i c i ) ∂b i ∂W = [(1 -a i a i ) (a i - c i c i )[x i ; 1] T + (1 -b i b i ) (b i - s i c i c i )[y i ; 1] T ], (12)
where the notation means element-wise multiplication. The derivation of this equation can be easily obtained with the chain rule used in the Backpropagation algorithm [START_REF] Lecun | Efficient backprop[END_REF].

Multiple layers of nonlinear neurons

By combining several interconnected nonlinear neurons together, Multi-Layer Perceptrons (MLP) are able to approximate arbitrary nonlinear mappings and thus have been the most popular kind of neural networks since the 1980's [START_REF] David E Rumelhart | Learning internal representations by error propagation[END_REF]. We adopt a 3-layer MLP, containing one input layer and two layers of nonlinear neurons, to realize the nonlinear mapping.

Similar with Equation ( 12) and according to the Backpropagation chain rule, we can calculate derivatives with respect to each parameter of the MLP for a given training pair.

For the DDML cost function, we can obtain derivatives with respect to the weights of neuron layers in the same way with the TSML method. For all the linear and shallow nonlinear systems, we employ the same stochastic gradient descent optimization to update their weights until reaching an optimal solution.

Stochastic Gradient Descent

Since all the three types of mapping functions have similar cost and gradient functions, we employ the same algorithm to perform optimization. The proposed method is based on stochastic gradient descent and is summarized in Algorithm 1. More advanced optimization algorithms such as conjugate gradient descent, L-BFGS [START_REF] Zheng | Triangular similarity metric learning for face verification[END_REF], [START_REF] Liu | On the limited memory BFGS method for large scale optimization[END_REF] could be used as well but their analysis would go beyond the scope of this paper. We adopt early-stopping [START_REF] Prechelt | Early stopping -but when?[END_REF] to prevent the over-fitting problem. Thus a small set is separated from the training data for validation, and the model with the best performance on the validation set is retained for evaluation on the test set. In addition, we use a momentum [START_REF] Lecun | Efficient backprop[END_REF] term to speed up training. The momentum λ is empirically set to be 0.99 for all the experiments. Following [START_REF] Simonyan | Fisher vector faces in the wild[END_REF], [START_REF] Cao | Similarity metric learning for face recognition[END_REF], the input vectors will be passed through L2 normalization before training, i.e. the length of input vectors are normalized to 1.

Initializing the weights

For the linear mapping, like in [START_REF] Zheng | Triangular similarity metric learning for face verification[END_REF], [START_REF] Hieu | Cosine similarity metric learning for face verification[END_REF], [START_REF] Cao | Similarity metric learning for face recognition[END_REF], we initialize the transformation matrix with the identity matrix. For the nonlinear mappings, we use the normalized random initialization [START_REF] Glorot | Understanding the difficulty of training deep feedforward neural networks[END_REF] that is considered to be helpful for the tanh networks. Concretely, weights of each layer are initialized with an uniform distribution as:

{W (j) , h (j) } ∼ U [- √ 6 √ n j + n j+1 , √ 6 √ n j + n j+1 ], (13)
where {W (j) , h (j) } denotes the parameters between the j th and (j + 1) th layers; n j and n j+1 represent the number of nodes in the two layers, respectively.

EXPERIMENTS AND ANALYSIS

Datasets

In order to validate the generality of the proposed approaches, we carried out pairwise identity verification experiments on two datasets in different domains: the LFW image dataset for pairwise face verification [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF] and the NIST i-vector dataset for pairwise speaker verification [START_REF] Greenberg | The NIST 2014 speaker recognition i-vector machine learning challenge[END_REF]. % output the best matrix on the validation set W ← the W t gives the best result on the validation set; return W .

LFW dataset

The LFW dataset contains numerous annotated images from the web. For all the images, we used the cropped 150 × 150 'funneled' version of LFW [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF]. We only used the View 2 subset of LFW for performance evaluation. In View 2, to do 10-fold cross validation, all the 5749 persons in the dataset are divided into 10 subsets where the individuals are mutually exclusive. The total number of images for all the persons is 13,233, however, the number of images for each individual varies from 1 to 530. Table 1 summarizes the data distribution of individuals and images in the 10 subsets.

We used Fisher Vector faces as vector representation of face images, where data of the vectors are directly provided by [START_REF] Simonyan | Fisher vector faces in the wild[END_REF] 1 (Data for the setting 3), and the dimension of a Fisher Vector face is 67,584. However, directly taking the original facial vectors for learning causes computational problems, i.e. the time required for multiplications of the 67,584-d vectors would be unacceptable. Therefore, following [START_REF] Hieu | Cosine similarity metric learning for face verification[END_REF], [START_REF] Barkan | Fast high dimensional vector multiplication face recognition[END_REF], we apply Whitened Principal Component Analysis (WPCA) to reduce the vector dimension to 500.

NIST i-vector dataset

We used the data of the NIST 2014 Speaker i-Vector Challenge [START_REF] Greenberg | The NIST 2014 speaker recognition i-vector machine learning challenge[END_REF], which consist of i-vectors derived from conversational telephone speech data in the NIST speaker recognition evaluations from 2004 to 2012. Each i-vector, the identity vector, is a vector of 600 components. Along with each i-vector, the amount of speech (in seconds) used to compute the i-vector is supplied as metadata. Segment durations were sampled from a log normal distribution with a mean of 39.58 seconds. This dataset consists of a development set for building models and a test set for evaluation.

We only used the development data of this Challenge and established an experimental protocol of pairwise speaker verification. There are 36,572 speech utterances in total in this experiment, belonging to 4958 different speakers. The number of utterances for a single speaker varies from 1 to 75. Like in LFW, we also split the data into 10 subsets to do 10-fold cross validation. Table 2 shows the distribution of individuals and speech utterances in the 10 subsets.

Experimental Setup

On both of the two datasets, we performed cross-validation on the 10 folds: there are overall 10 experiments, in each repetition, sample pairs from 9 folds are used for training, and sample pairs from the remaining fold are used for testing. As we have announced in Section 4.1, some training data are separated as an independent validation set to do early-stopping.

Fixed testing

To perform evaluation on the test set for each experiment, it is better to fix the sample pairs in each fold so that we can fairly compare different approaches on the same test data. Specifically, 600 image pairs are provided in each fold of the 1. http://www.robots.ox.ac.uk/˜vgg/software/face desc/ LFW dataset, where 300 are similar and the other 300 are dissimilar [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF]. In the NIST i-vector dataset, there are more samples for each individual than in the LFW dataset, so we generate more sample pairs for each fold, namely, 1200 similar pairs and 1200 dissimilar pairs.

Restricted and unrestricted training

Following [START_REF] Huang | Labeled faces in the wild: A database for studying face recognition in unconstrained environments[END_REF], we defined two training settings in our experiments: the restricted setting in which only the fixed sample pairs in each fold can be collected for training, e.g. the specified 300 similar and 300 dissimilar pairs in each fold of the LFW dataset; in contrast, the unrestricted setting allows to generate more sample pairs for training by using the identity information of all the samples. As mentioned previously, the test sample pairs are the same for both restricted and unrestricted settings.

Maximal decision accuracy

Like the minimal Decision Cost Function (minDCF) in [START_REF] Greenberg | The NIST 2014 speaker recognition i-vector machine learning challenge[END_REF], we define a Decision Accuracy (DA) function to measure the overall verification performance on a set of data pairs:

DA(γ) = number of right decisions (γ) total number of pairs , ( 14
)
where the threshold γ is used to make a decision on the final distance or similarity values: for the TSML system, cos(a, b) > γ means (a, b) is a similar pair, otherwise it is dissimilar; for the DDML system, (a -b) 2 < γ denotes a similar pair, otherwise it is dissimilar. The maximal DA (maxDA) over all possible threshold values is the final score recorded. We report the mean maxDA scores (±standard error of the mean) of the 10 experiments. For the speaker verification results, we also measure the mean Equal Error Rate (EER) as it is commonly used in the speaker recognition field [START_REF] Kenny | Bayesian speaker verification with heavy-tailed priors[END_REF], [START_REF] Cumani | Large-scale training of pairwise support vector machines for speaker recognition[END_REF].

Experimental Results

At the beginning, we directly calculated maxDA scores on the whitened feature vectors, i.e. the 500-dimensional FV vectors for the LFW dataset and 600-dimensional i-vectors for the NIST i-vector dataset. We consider this evaluation as the baseline. According to the different neuron models defined in Section 4, we evaluated three kinds of metric learning approaches in the experiments:

• TSML-Linear and DDML-Linear: using a single layer of linear neurons without bias term;

• TSML-Nonlinear and DDML-Nonlinear: using a single layer of nonlinear neurons with a bias term;

• TSML-MLP and DDML-MLP: using two layers of nonlinear neurons with bias terms;

All these models are trained on both similar and dissimilar pairs. Results on the LFW-funneled dataset and the NIST i-vector dataset are summarized in Tables 3456. We also reimplement the state-of-the-art WCCN method [START_REF] Barkan | Fast high dimensional vector multiplication face recognition[END_REF], [START_REF] Cao | Similarity metric learning for face recognition[END_REF] as a comparison.

Learning on Similar Pairs Only: comparing WCCN with the proposed six metric learning models, we find that WCCN achieves better performance under the restricted training. The major difference between WCCN and the other models is that WCCN concerns only intra-personal variance but ignores the inter-personal information [START_REF] Barkan | Fast high dimensional vector multiplication face recognition[END_REF], [START_REF] Cao | Similarity metric learning for face recognition[END_REF]. In other words, WCCN performs learning on similar pairs only but the current TSML and DSML systems take into account both similar and dissimilar pairs. To clarify this issue, we train the proposed models on similar pairs only as six new models: TSML-Linear-Sim, TSML-Nonlinear-Sim and TSML-MLP-Sim; DDML-Linear-Sim, DDML-Nonlinear-Sim and DDML-MLP-Sim. The results are also shown in Tables 3456.

More training data

The first phenomenon we can observe is that unrestricted training produces better results than restricted training.

More training data generally bring up an accuracy improvement to each model. We have known since mid-seventies [START_REF] Learned-Miller | Labeled faces in the wild: A survey[END_REF], [START_REF] Yann A Lecun | Deep learning[END_REF], [START_REF] Charles | Consistent nonparametric regression[END_REF] that many methods increase in accuracy with increasing training data until they reach optimal performance. Indeed, more training data better capture the underlying distribution of the whole dataset and thus reduce the overfitting gap between training and test. Especially for the pairwise verification problem that requires learning on data pairs, compared with restricted training only allows to use a few specified training pairs in a dataset, unrestricted training covers enough data pairs and thus protect the models from over-fitting to a small portion of training data.

Linear vs. nonlinear

The second observation is that the linear models generally perform better than the shallow nonlinear models. Specifically, more parameters (i.e. additional bias terms or/and more layers of neurons) and the nonlinearity make the nonlinear models more powerful to adapt themselves to the training data. However, without any additional techniques to prevent over-fitting, generalization to the test data is not guaranteed. Figure 4 shows the learning curves of TSML-Linear, TSML-Nonlinear and TSML-MLP in restricted training, we can see that all of them easily fit the training data. Especially, with the most parameters, TSML-MLP is the strongest learning machine that reaches the accuracy of 100% on the training data with the fewest iterations, but it performs the worst on the test data. More regularization techniques, such as weight decay [START_REF] Lecun | Efficient backprop[END_REF] and dropout [START_REF] Srivastava | Dropout: A simple way to prevent neural networks from overfitting[END_REF], can be introduced to reduce the risk of over-fitting for such slightly deeper nonlinear model, but their analysis would go beyond the scope of this paper. In contrast, with the same experimental setting, linearity naturally indicates the property of generalization and thus makes TSML-Linear better fit to the unseen data, i.e. the validation and test sets.

Concentrative training on limited data pairs

Figure 5 compares the performance of the linear models of both TSML and DDML on the LFW-funneled dataset and the NIST i-vector datset, respectively. In general, under the restricted training, the models trained on similar pairs only, i.e. TSML-Linear-Sim and DDML-Linear-Sim, yield significantly better results; under the unrestricted training, all the linear models perform comparably well.

In general, a linear concentrative model 2 should be adopted for restricted training because of its superior per-2. We use the term "concentrative" to indicate learning on similar pairs only since it concerns closing a similar pair rather than separating a dissimilar pair. formance. Moreover, it should be also preferred for unrestricted training due to faster training. Compared with models trained on both similar and dissimilar pairs, the linear concentrative models only take into account half of the training data but yield comparable verification results.

Concretely, the setting of equal quantity of similar and dissimilar pairs is problematic for restricted training. As-suming a n-class problem with two samples in each class, the number of all possible similar pairs is n. But the number of all possible dissimilar pairs is 2n(n -1), which is much larger than the number of similar pairs. However, the restricted configuration requires the number of dissimilar pairs is the same as the number of similar pairs. For example, only 300 similar pairs and 300 dissimilar pairs are provided in each subset of the LFW dataset. As a consequence, learning on such limited number of dissimilar pairs causes serious over-fitting problems to the normal models, that is why they perform worse than the linear concentrative models. In contrast, when the training is unrestricted, enough dissimilar pairs can be covered during training and the risk of over-fitting is reduced. Hence the normal models trained on both similar and dissimilar pairs perform well in unrestricted training.

In short, restricted training on equal quantity of similar and dissimilar pairs does not accord with the ratio of similar and dissimilar pairs in practice. The similar pairs indeed deliver more positive contributions for learning a better metric. Apart from our suggestion of learning on similar pairs only, this goal can be achieved by other techniques such as shifting the Cosine Similarity boundary [START_REF] Zheng | Logistic similarity metric learning for face verification[END_REF], using hinge loss functions to filter invalid gradient descent from dissimilar pairs [START_REF] Hu | Discriminative deep metric learning for face verification in the wild[END_REF] or weighting the gradient contributions from similar and dissimilar pairs [START_REF] Hieu | Cosine similarity metric learning for face verification[END_REF], [START_REF] Hu | Deep transfer metric learning[END_REF]. Overall, our proposed concentrative training is a competitive choice due to its simplicity.

TSML vs. DDML

Comparing the two metric learning methods, TSML and DDML, we find comparable performance records in Tables 3 -6. This is reasonable because the Euclidean distance is naturally related to the Cosine Similarity. For the square of the Euclidean distance between two vectors, we have That means in our situation, minimizing the distance between data pairs is equivalent to maximizing the pairwise similarity value.

Comparison with the State-of-the-Art

We compared the proposed TSML-Linear-Sim method with several state-of-the-art methods on the LFW dataset under the image-restricted configuration with no outside data [START_REF] Huang | Labeled faces in the wild: Updates and new reporting procedures[END_REF]. The comparison is summarized in Table 7, and the corresponding ROC curves are shown in Fig. 6. The curves of MRF-MLBP [START_REF] Arashloo | Efficient processing of MRFs for unconstrained-pose face recognition[END_REF] and MRF-Fusion-CSKDA [START_REF] Rahimzadeh | Class-specific kernel fusion of multiple descriptors for face verification using multiscale binarised statistical image features[END_REF] are missing because the curve data are not provided on the public result page 3 . We can see that MRF-Fusion-CSKDA occupies the first place and the proposed TSML-Linear-Sim takes the second one with a relatively large gap (91.90% vs. 95.89%). This is because MRF-Fusion-CSKDA employed multi-scale binarized statistical image features and made a fusion on multiple features [START_REF] Rahimzadeh | Class-specific kernel fusion of multiple descriptors for face verification using multiscale binarised statistical image features[END_REF]. However, the proposed TSML-Linear-Sim method is much simpler as it has only utilized a single feature, the FV vectors. under the restricted configuration with no outside data on LFW-funneled.

Method Accuracy

V1-like/MKL [START_REF] Pinto | How far can you get with a modern face recognition test set using only simple features?[END_REF] 79.35±0.55 APEM (fusion) [START_REF] Li | Probabilistic elastic matching for pose variant face verification[END_REF] 79.06±1.51 MRF-MLBP [START_REF] Arashloo | Efficient processing of MRFs for unconstrained-pose face recognition[END_REF] (no ROC) 79.08±0.14 SVM-Fisher vector faces [START_REF] Simonyan | Fisher vector faces in the wild[END_REF] 87.47±1.49 Eigen-PEP (fusion) [START_REF] Li | Eigen-pep for video face recognition[END_REF] 88.97±1.32 Hierarchical-PEP (fusion) [START_REF] Li | Hierarchical-PEP model for real-world face recognition[END_REF] 91.10±1.47 MRF-Fusion-CSKDA [START_REF] Rahimzadeh | Class-specific kernel fusion of multiple descriptors for face verification using multiscale binarised statistical image features[END_REF] Thus we collected the results of methods using a single feature in Table 8. Especially, we also applied another stateof-the-art approach WCCN [START_REF] Barkan | Fast high dimensional vector multiplication face recognition[END_REF] on the FV vectors as a comparison. We can see that the proposed TSML-Linear-Sim method achieves the best performance (91.90%) among all the methods using a single feature. Especially, TSML-Linear-Sim significantly surpasses the conventional Support Vector Machines (SVM) method [START_REF] Simonyan | Fisher vector faces in the wild[END_REF] on the FV vectors by 4.43% points (from 87.47% to 91.90%).

Stacked to Pre-trained Deep Nonlinearity

As we have mentioned, the proposed shallow nonlinearity was constrained due to lack of proper generalization strategies and more training data. At present, the success of deep learning in speech recognition and visual object recognition shows that the deep nonlinearity is able to learn discriminative representations of data [START_REF] Yann A Lecun | Deep learning[END_REF]. To release the power of nonlinearity, deep learning approaches require large datasets and perform training in a supervised way [START_REF] Taigman | Deepface: Closing the gap to human-level performance in face verification[END_REF], [START_REF] Sun | Deep learning face representation by joint identification-verification[END_REF], [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF]. However, it is difficult to directly train a deep metric learning system on a large dataset having hundred thousands of or even millions of data samples [START_REF] Taigman | Deepface: Closing the gap to human-level performance in face verification[END_REF], [START_REF] Wu | A lightened CNN for deep face representation[END_REF] because the number of sample pairs will be dramatically raised. Actually training semi-supervised siamese neural networks is much slower than training supervised neural networks [START_REF] Zheng | Triangular Similarity Metric Learning: a Siamese Architecture Approach[END_REF]. Recent empirical work showed that training siamese neural networks on carefully chosen triplets instead of data pairs is helpful for fast convergence [START_REF] Schroff | Facenet: A unified embedding for face recognition and clustering[END_REF], [START_REF] Omkar M Parkhi | Deep face recognition[END_REF].

Besides, it was also found that even a simple classifier can make good decision on the features produced by the learned deep models [START_REF] Taigman | Deepface: Closing the gap to human-level performance in face verification[END_REF], [START_REF] Sun | Deep learning face representation by joint identification-verification[END_REF], [START_REF] Wu | A lightened CNN for deep face representation[END_REF]. Therefore we stack the proposed linear and nonlinear metric learning models to a pre-trained deep CNN [START_REF] Wu | A lightened CNN for deep face representation[END_REF] trained on the CASIS-Webface dataset [START_REF] Yi | Learning face representation from scratch[END_REF]. There are 493,456 labeled images of 10,575 identities in the CASIS-Webface. [START_REF] Wu | A lightened CNN for deep face representation[END_REF] provides two deep models trained on these data. We use the model A to extract features from each face image in the LFW dataset, resulting in a 256-dimensional vector. Then the process of metric learning is similar with that on the Fisher Vectors under the unrestricted training setting. All the TSML and DDML models are tested.

Table 9 summarizes the results of the deep CNN model and the stacked models. It is not surprising that the deep CNN brings significant verification improvement to our shallow models. By the learned discriminative feature representations from the CASIS-Webface face images, the deep CNN itself achieves the accuracy of 97.93%. We can see that the linear models, TSML-Linear and DDML-Linear, further improve the verification performance to 98.25% and 98.18%. This improvement is guaranteed by the identity initialization and early stopping applied to the linear models: the deep CNN results are taken as initial status for metric learning; and early stopping marks the best record on the validation set. In contrast, the shallow nonlinear metric learning models obtain slightly worse results because they take random initialization and degrade the good deep CNN baseline. A probable reason is that we have restricted the input/output size of the nonlinear models to the size of the linear models, and it might be possible to improve the nonlinear models by tuning the size of layers, trying different initialization methods or adding regularization techniques. However, the simple linear metric learning model is indeed a good and quick option that demands less effort on hyperparameter tuning than the shallow nonlinear ones. Thus we suggest the deep nonlinearity for robust feature learning on large datasets and the shallow linearity for classification [START_REF] Chatfield | Return of the devil in the details: Delving deep into convolutional nets[END_REF].

CONCLUSION

In this paper, we have evaluated two metric learning methods -TSML and DDML -for pairwise face verification on the LFW dataset and pairwise speaker verification on the NIST i-vector dataset. Under the setting of limited training pairs, we found that learning a linear model on similar pairs only is a simple but effective solution for identify verification. When labeled outside data are available, a pre-trained deep CNN model helps the linear TSML and DDML systems to reach competitive performance on face verification.

We presented several strategies and confirmed their effectiveness on reducing the risk of over-fitting. These strategies include using more training pairs; using a linear model to keep generalization; learning on similar pairs only for restricted training; separating a validation set to perform early stopping; introducing a deep CNN model pre-trained on a large dataset. With these strategies, the nature of learning a good metric of the TSML and DDML methods makes themselves effective on the two different pairwise verification tasks.

The defined pairwise verification task is not limited to only human identities, the objects can be documents, audio, images or individuals in any other categories. For any pairwise verification problems with objects that can be represented as numerical vectors, we believe that the proposed methods are applicable, and the observed phenomena are repeatable.

Fig. 2 .

 2 Fig. 2. Geometrical interpretation of the TSML cost and gradient. (a) Minimizing the cost means to make similar vectors parallel and make dissimilar vectors opposite. (b)The gradient function suggests unit vectors on the diagonals as targets for a i and b i : the same target vector for a similar pair (s i = 1); or the opposite target vectors for a dissimilar pair (s i = -1).

Fig. 3 .

 3 Fig.3. Illustration of the DDML cost function, whose objective is to find an optimal mapping to make a similar pair closer and to separate a dissimilar pair with a distance margin of √ 2.

Fig. 4 .

 4 Fig.4. Learning curves of different TSML models. Curves on the training, validation and test sets are represented by black, blue and red lines, respectively. All the models are trained on the LFW data under the restricted setting. According to early stopping, the vertical line indicates the model having the best performance on the validation set. Without any additional regularization techniques, the more complex the learning model is, i.e. having more parameters, the larger the over-fitting gap is.

Fig. 5 .

 5 Fig. 5. Performance comparison of the linear models on the LFWfunneled dataset and the NIST i-vector dataset.

  (a -b) 2 = (a -b) T (a -b) = a 2 + b 2 -2a T b. When the vectors are normalized to unit length, i.e. a 2 = b 2 = 1, the previous equation can be written as (a-b) 2 = 2-2cos(a, b).

Fig. 6 .

 6 Fig.6. ROC curves of Linear-TSML-Sim (red dashed line) and other state-of-the-art methods on the LFW dataset under the restricted configuration with no outside data.

TABLE 1

 1 Distribution of individuals and images in the 10 subsets, where the individuals are mutually exclusive.

	Index	1	2	3	4	5	6	7	8	9	10	Total
	Number of individuals	601	555	552	560	567	527	597	601	580	609	5749
	Number of images	1369 1367 1089 1324 1016 1166 1690 1222 1207 1783 13233

TABLE 2

 2 Distribution of individuals and speech utterances in the 10 subsets, where the individuals are mutually exclusive.

	Index	1	2	3	4	5	6	7	8	9	10	Total
	Number of individuals	496	496	496	496	496	496	496	496	496	494	4958
	Number of utterances	3660 3664 3568 3741 3702 3566 3605 3636 3744 3686 36572
	Algorithm 1: Stochastic Gradient Descent for TSML
	input : Training set; Validation set;
	output: Parameter set W
	paramters: Learning rate α = 10 -4 ; Momentum
	λ = 0.99; Iterative tolerance P t = 4 × 10 5 ; Validation frequency F t = 10 3 ;
	% initialization
	if linear mapping then
	W 0 ← I; % I is the identity matrix
	if nonlinear mapping then
	randomly initialize W 0 according to Equation (13);
	∆W 0 ← 0;
	Perform L2 normalization on the training set;
	Perform L2 normalization on the validation set;
	% optimization by Backpropagation
	for t = 1, 2, . . . , P t do
	% select training data for each epoch
	Randomly select a similar pair and a dissimilar
	pair from the training set;
	% forward propagation
	Calculate the cost J on the selected training pairs;
	% back propagation
	Calculate the corresponding gradient ∂J ∂Wt-1 ;
	% updating using momentum
	∆W t = λ∆W t-1 + ∂J ∂Wt-1 ;
	W t ← W t-1 + α∆W t ;
	% checking on the validation set regularly
	if (P t mod F t ) == 0 then
	compute the Decision Accuracy according to
	Equation (14);

TABLE 3

 3 Mean maxDA scores (±standard error of the mean) of pairwise face verification by the TSML systems on the LFW-funneled image dataset. '-Sim' means learning on similar pairs only.

	Approaches	Restricted Training Unrestricted Training
	Baseline	84.83±0.38
	WCCN	91.10±0.45	91.17±0.36
	TSML-Linear	87.95±0.40	92.03±0.38
	TSML-Nonlinear	86.23±0.39	91.43±0.52
	TSML-MLP	84.10±0.45	89.30±0.73
	TSML-Linear-Sim	91.90±0.52	92.40±0.48
	TSML-Nonlinear-Sim	90.58±0.52	91.47±0.37
	TSML-MLP-Sim	88.98±0.64	89.03±0.58

TABLE 4

 4 Mean maxDA scores (±standard error of the mean) and mean EER of pairwise speaker verification by the TSML systems on the NIST i-vector speaker dataset. '-Sim' means learning on similar pairs only.

	Approaches	Restricted Training	Unrestricted Training
	Baseline	87.78±0.39 / 0.1335
	WCCN	91.69±0.29 / 0.0900	91.97±0.33 / 0.0853
	TSML-Linear	89.78±0.25 / 0.1108	93.97±0.20 / 0.0648
	TSML-Nonlinear	87.43±0.31 / 0.1340	93.11±0.20 / 0.0733
	TSML-MLP	84.88±0.24 / 0.1592	90.21±0.36 / 0.1023
	TSML-Linear-Sim	92.94±0.15 / 0.0785	93.99±0.24 / 0.0662
	TSML-Nonlinear-Sim 91.29±0.25 / 0.0918	93.43±0.23 / 0.0690
	TSML-MLP-Sim	89.59±0.45 / 0.1093	90.83±0.30 / 0.0967

TABLE 5

 5 Mean maxDA scores (±standard error of the mean) of pairwise face verification by the DDML systems on the LFW-funneled image dataset. '-Sim' means learning on similar pairs only.

	Approaches	Restricted Training Unrestricted Training
	Baseline	84.83±0.38
	WCCN	91.10±0.45	91.17±0.36
	DDML-Linear	88.27±0.53	92.48±0.35
	DDML-Nonlinear	88.12±0.70	92.23±0.36
	DDML-MLP	88.60±0.90	91.53±0.42
	DDML-Linear-Sim	91.03±0.61	91.80±0.29
	DDML-Nonlinear-Sim	90.82±0.45	91.42±0.40
	DDML-MLP-Sim	89.57±0.45	89.53±0.44

TABLE 6

 6 Mean maxDA scores (±standard error of the mean) and mean EER of pairwise speaker verification by the DDML systems on the NIST i-vector speaker dataset. '-Sim' means learning on similar pairs only.

	Approaches	Restricted Training	Unrestricted Training
	Baseline	87.78±0.39 / 0.1335
	WCCN	91.69±0.29 / 0.0900	91.97±0.33 / 0.0853
	DDML-Linear	89.77±0.21 / 0.1127	94.32±0.23 / 0.0612
	DDML-Nonlinear	87.98±0.29 / 0.1262	93.36±0.23 / 0.0703
	DDML-MLP	89.11±0.27 / 0.1143	92.39±0.25 / 0.0807
	DDML-Linear-Sim	92.95±0.29 / 0.0748	94.42±0.24 / 0.0590
	DDML-Nonlinear-Sim 91.98±0.25 / 0.0850	93.74±0.22 / 0.0662
	DDML-MLP-Sim	89.08±0.27 / 0.1133	89.69±0.36 / 0.1075

TABLE 7

 7 Comparison of TSML-Linear-Sim with other state-of-the-art results

3. http://vis-www.cs.umass.edu/lfw/results.html#ImageRestrictedNo

TABLE 9

 9 Mean maxDA scores (±standard error of the mean) of pairwise face verification by stacking the metric learning systems to the pre-trained deep CNN model on the LFW-funneled image dataset.

	Approaches		Accuracy
	Deep CNN		97.93±0.22
		-Linear	-Nonlinear	-MLP
	Deep CNN-TSML	98.25±0.19 97.50±0.21 97.15±0.22
	Deep CNN-DDML 98.18±0.22 97.78±0.26 97.20±0.26

ACKNOWLEDGMENTS

Thanks to the China Scholarship Council (CSC) and the Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS) for supporting this work.