On the Intrinsic Dimensionality of Image Representations
Sixue Gong Vishnu Naresh Boddeti Anil K. Jain







On the Intrinsic Dimensionality of Image Representations
    Sixue Gong    Vishnu Naresh Boddeti    Anil K. Jain

Michigan State University, East Lansing MI 48824

{gongsixu, vishnu, jain}@msu.edu

    
============================================================================================================================================

empty




This paper addresses the following questions pertaining to the intrinsic dimensionality of any given image representation: (i) estimate its intrinsic dimensionality, (ii) develop a deep neural network based non-linear mapping, dubbed DeepMDS, that transforms the ambient representation to the minimal intrinsic space, and (iii) validate the veracity of the mapping through image matching in the intrinsic space. Experiments on benchmark image datasets (LFW, IJB-C and ImageNet-100) reveal that the intrinsic dimensionality of deep neural network representations is significantly lower than the dimensionality of the ambient features. For instance, SphereFace's <cit.> 512-dim face representation and ResNet's <cit.> 512-dim image representation have an intrinsic dimensionality of 16 and 19 respectively. Further, the DeepMDS mapping is able to obtain a representation of significantly lower dimensionality while maintaining discriminative ability to a large extent, 59.75% TAR @ 0.1% FAR in 16-dim vs 71.26% TAR in 512-dim on IJB-C <cit.> and a Top-1 accuracy of 77.0% at 19-dim vs 83.4% at 512-dim on ImageNet-100.




§ INTRODUCTION



An image representation is an embedding function that transforms the raw pixel representation of the image to a point in a high-dimensional vector space. Learning or estimating such a mapping is motivated by two goals: (a) the compactness of the representation, and (2) the effectiveness of the mapping for the task at hand. While the latter topic has received substantial attention, ranging from PCA based Eigenfaces <cit.> to deep neural network (DNN) based feature representations, there has been relatively little focus on the dimensionality of the representation itself. The dimensionality of image representations has ranged from hundreds to thousands of dimensions. For instance, current state-of-the-art image representations have 128, 512, 1024 and 4096 dimensions for FaceNet <cit.>, ResNet <cit.>, SphereFace <cit.> and VGG <cit.>, respectively. The choice of dimensionality is often determined by practical considerations, such as, ease of learning the embedding function <cit.>, constraints on system memory, etc. instead of the effective dimensionality necessary for image representation. This naturally raises the following fundamental but related questions, How compact can the representation be without any loss in recognition performance? In other words, what is the intrinsic dimensionality of the representation? And, how can one obtain such a compact representation? Addressing these questions is the primary goal of this paper.

The intrinsic dimensionality (ID) of a representation refers to the minimum number of parameters (or degrees of freedom) necessary to capture the entire information present in the representation <cit.>. Equivalently, it refers to the dimensionality of the m-dimensional manifold ℳ embedded within the d-dimensional ambient (representation) space 𝒫 where m ≤ d. This notion of intrinsic dimensionality is notably different from common linear dimensionality estimates obtained through e.g., principal component analysis (PCA). This linear dimension corresponds to the best linear subspace necessary to retain a desired fraction of the variations in the data. In principle, linear dimensionality can be as large as the ambient dimension if the variation factors are highly entangled with each other. An illustration of these concepts is provided in Fig. <ref>. 

The ability to estimate the intrinsic dimensionality of a given image representation is useful in a number of ways. At a fundamental level, the ID determines the true capacity and complexity of variations in the data captured by the representation, through the embedding function. In fact, the ID can be used to gauge the information content in the representation, due to its linear relation with Shannon entropy <cit.>. Also, it provides an estimate of the amount of redundancy built into the representation which relates to its generalization capability. On a practical level, knowledge of the ID is crucial for devising optimal unsupervised strategies to obtain image features that are minimally redundant, while retaining its full ability to categorize images into different classes. Recognition in the intrinsic space can provide significant savings, both in memory requirements as well as processing time, across downstream tasks like large-scale face matching in the encrypted domain <cit.>, image matching and retrieval, etc. Lastly, gap between the ambient and intrinsic dimensionalities of a representation can serve as a useful indicator to drive the development of algorithms that can directly learn highly compact embeddings.

Estimating the ID of given data representation however is a challenging task. Such estimates are crucially dependent on the density variations in the representation, which in itself is difficult to estimate as images often lie on a topologically complex curved manifold <cit.>. More importantly, given an estimate of ID, how do we verify that it truly represents the dimensionality of the complex high-dimensional representation space? An indirect validation of the ID is possible through a mapping that transforms the ambient representation space to the intrinsic representation space while preserving its discriminative ability. However, there is no certainty that such a mapping can be found efficiently. In practice, finding such mappings can be considerably harder than estimating the ID itself.

We overcome both of these challenges by (1) adopting a topological dimensionality estimation technique based on the geodesic distance between points on the manifold, and (2) relying on the ability of DNNs to approximate the complex mapping function from the ambient space to the intrinsic space. The latter enables validation of the ID estimates through image matching experiments on the corresponding low-dimensional intrinsic representation of feature vectors.

The key contributions and findings of this paper are:

– The first attempt to estimate the intrinsic dimensionality of DNN based image representations.

– An unsupervised DNN based dimensionality reduction method under the framework of multidimensional scaling, called DeepMDS.

– Numerical experiments yield an ID estimate of, 12 and 16 for FaceNet <cit.> and SphereFace <cit.> face representations, respectively, and 19 for ResNet-34 <cit.> image representation. The estimates are significantly lower than their respective ambient dimensionalities, 128-dim for FaceNet and 512-dim for the others.

– DeepMDS mapping is significantly better than other dimensionality reduction approaches in terms of its discriminative capability.



§ RELATED WORK

Image Representation:  The quest to develop image representations that are simultaneously robust and discriminative have led to extensive research on this topic. Amongst the earliest learning based approaches, Turk and Pentland proposed Eigenfaces <cit.> that relied on principal component analysis (PCA) of data. Later on, integrated and high-dimensional spatially local features became prevalent for image recognition, notable examples include local binary patterns (LBP) <cit.>, scale-invariant feature transform (SIFT) <cit.> and histogram of oriented gradients (HoG) <cit.>. In contrast to these hand-designed representations, the past decade has witnessed the development of end-to-end representation learning systems. Convolutional neural network based features now typify the state-of-the-art image representations <cit.>. All of these representations are however characterized by features that range from hundreds to thousands of dimensions. While more compact representations are desirable, difficulties with optimizing DNNs with narrow bottlenecks <cit.> have proven to be the primary barrier towards realizing this goal.



Intrinsic Dimensionality:  Existing approaches for estimating intrinsic dimensionality can be broadly classified into two groups: projection methods and geometric methods. The projection methods <cit.> determine the dimensionality by principal component analysis on local subregions of the data and estimating the number of dominant eigenvalues. These approaches have classically been used in the context of modeling facial appearance under different illumination conditions <cit.> and object recognition with varying pose <cit.>. While they serve as an efficient heuristic, they do not provide reliable estimates of intrinsic dimension. Geometric methods <cit.> on the other hand model the intrinsic topological geometry of the data and are based on the assumption that the volume of a m-dimensional set scales with its size ϵ as ϵ^m and hence the number of neighbors less than ϵ also behaves the same way. Our approach in this paper is based on the topological notion of correlation dimension <cit.>, the most popular type of fractal dimensions. The correlation dimension implicitly uses nearest-neighbor distance, typically based on the Euclidean distance. However, Granata et.al. <cit.> observe that leveraging the manifold structure of the data, in the form of geodesic distances induced by a neighborhood graph of the data, provides more realistic estimates of the ID. Building upon this observation we base our ID estimates on the geodesic distance between points. We believe that estimating the intrinsic dimensionality would serve as the first step towards understanding the bound on the minimal required dimensionality for representing images and aid in the development of novel algorithms that can achieve this limit.



Dimensionality Reduction:  There is a tremendous body of work on the topic of estimating low-dimensional approximations of data manifolds lying in high-dimensional space. These include linear approaches such as Principal Component Analysis <cit.>, Multidimensional Scaling (MDS) <cit.> and Laplacian Eigenmaps <cit.> and their corresponding non-linear spectral extensions, Locally Linear Embedding <cit.>, Isomap <cit.> and Diffusion Maps <cit.>. Another class of dimensionality reduction algorithms leverage the ability of deep neural networks to learn complex non-linear mappings of data including deep autoencoders <cit.>, denoising autoencoders <cit.> and learning invariant mappings either with the contrastive loss <cit.> or with the triplet loss <cit.>. While the autoencoders can learn a compact representation of data, such a representation is not explicitly designed to retain discriminative ability. Both the contrastive loss and the triplet loss have a number of limitations; (1) require similarity and dissimilarity labels from some source and cannot be trained in a purely unsupervised setting, (2) require an additional hyper-parameter, maximum margin of separation, which is difficult to pre-determine, especially for an arbitrary representation, and (3) do not maintain the manifold structure in the low-dimensional space. In this paper, we too leverage DNNs to approximate the non-linear mapping from the ambient to the intrinsic space. However, we consider an unsupervised setting (i.e., no similarity or dissimilarity labels) and cast the learning problem within the framework of MDS i.e., preserving the ambient graph induced geodesic distance between points in the intrinsic space.



§ APPROACH


Our goal in this paper is to compress a given image representation space. We achieve this in two stages[Traditional single-stage dimensionality reduction methods use visual aids to arrive at the final ID and intrinsic space, e.g., plotting the projection error against the ID values and looking for a “knee" in the curve.]: (1) estimate the intrinsic dimensionality of the ambient image representation, and (2) learn the DeepMDS model to map the ambient representation space 𝒫∈ℝ^d to the intrinsic representation space ℳ∈ℝ^m (m ≤ d). The ID estimates are based on the one presented by <cit.> which relies on two key ideas, (1) using graph induced geodesic distances to estimate the correlation dimension of the image representation topology, and (2) the similarity of the distribution of geodesic distances across different topological structures with the same intrinsic dimensionality. The DeepMDS model is optimized to preserve the interpoint geodesic distances between the feature vectors in the ambient and intrinsic space, and is trained in a stage-wise manner that progressively reduces the dimensionality of the representation. Basing the projection method on DNNs, instead of spectral approaches like Isomap, addresses the scalability and out-of-sample-extension problems suffered by spectral methods. Specifically, DeepMDS is trained in a stochastic fashion, which allows it to scale. Furthermore, once trained, DeepMDS provides a mapping function in the form of a feed-forward network that maps the ambient feature vector to its corresponding intrinsic feature vector. Such as map can easily be applied to new test data.



 §.§ Estimating Intrinsic Dimension

We define the notion of intrinsic dimension through the classical concept of topological dimension of the support of a distribution. This is a generalization of the concept of dimension of a linear space [Linear dimension is the minimum number of independent vectors necessary to represent any given point in this space as a linear combination.] to a non-linear manifold. Methods for estimating the topological dimension are all based on the assumption that the behavior of the number of neighbors of a given point on an m-dimensional manifold embedded within a d-dimensional space scales with its size ϵ as ϵ^m. In other words, the density of points within an ϵ-ball (ϵ→ 0) in the ambient space is independent of the ambient dimension d and varies only according to its intrinsic dimensionality m. Given a collection of points X={x_1,…,x_n}, where x_i∈ℝ^d, the cumulative distribution of the pairwise distances C(r) between the n points can be estimated as,

    C(r) = 2/n(n-1)∑_i<j=1^n H(r - x_i-x_j) =  ∫_0^r p(r)dr

where H(·) is the Heaviside function and p(r) is the probability distribution of the pairwise distances. In this paper, we choose the correlation dimension <cit.>, a particular type of topological dimension, to represent the intrinsic dimension of the image representation. It is is defined as,

    m=lim_r→ 0ln C(r)/ln rlim_r→ 0 C(r) ∝ r^m

Therefore, the intrinsic dimension is crucially dependent on the accuracy with which the probability distribution can be estimated at very small length-scales (distances), i.e., r→ 0. Significant efforts have been devoted to estimating the intrinsic dimension through line fitting in the ln C(r) vs ln r space around the region where r→ 0 i.e.,

    m = lim_(r_2-r_1) →0ln C(r_2) - ln C(r_1)/ln r_2 - ln r_1
    
        = lim_r→0d ln C(r)/d ln r = lim_r→0p(r)/C(r)r = lim_r→ 0 m(r)



The main drawback with this approach is the need for reliable estimates of p(r) at very small length scales, which is precisely where the estimates are most unreliable when data is limited, especially in very high-dimensional spaces. Granata et al. <cit.> present an elegant solution to this problem through three observations, (i) estimates of m(r) can be stable even as r→0 if the distance between points is computed as the graph induced shortest path between points instead of the euclidean distance, as is commonly the case, (ii) the probability distribution p(r) at intermediate length-scales around the mode of p(r) i.e., (r_max - 2σ) ≤ r ≤ r_max can be conveniently used to obtain reliable estimates of ID, and (iii) the distributions p(r) of different topological geometries are similar to each other as long as the intrinsic dimensionality is the same, or in other words the distribution p(r) depends only on the intrinsic dimensionality and not on the geometric support of the manifolds.

Figure <ref> provides an illustration of these observations. Consider two different manifolds, faces and the surface of a (m+1)-dimensional unitary hypersphere (henceforth referred to as m-hypersphere 𝒮^m), with intrinsic dimensionality of m=2 but embedded within 3-dim Euclidean space. Beyond the nearest neighbor, the distance r between any pair of points in the manifold is computed as the shortest path between the points as induced by the graph connecting all the points in the representation. Figure <ref> shows the distribution of logp(r)/p(r_max) vs logr/r_max in the range r_max - 2σ≤ r ≤ r_max, where σ is the standard deviation of p(r) and r_max=_r p(r) corresponds to the radius of the mode of p(r). Interestingly, different topological geometries, namely, a face representation of ID two, a 2-hypersphere and a 2-dim Gaussian, all embedded within 3-dim Euclidean space have almost identical distributions. More generally, the distribution of logp(r)/p(r_max) vs logr/r_max in the range r_max - 2σ≤ r ≤ r_max is empirically observed to depend only on the intrinsic dimensionality, rather than the geometrical support of the manifold.

The intrinsic dimensionality of the representation manifold can thus be estimated by comparing the empirical distribution of the pairwise distances p̂_ℳ(r) on the manifold to that of a known distribution, such as the m-hypersphere in the range r_max-σ≤ r ≤ r_max (see appendix for Gaussian example). The distribution of the geodesic distance p_𝒮^m(r) of m-hypersphere can be analytically expressed as, p_𝒮^m(r)=csin^m-1(r), where c is a constant and m is the ID. Given p̂_ℳ(r), we minimize the Root Mean Squared Error (RMSE) between the distributions as,

    min_c, m∫_r_max-2σ^r_maxlogp̂_ℳ(r)-log(c) - (m-1)log(sin[r])^2

which upon simplification yields,

    min_m∫_r_max-2σ^r_maxlogp̂_ℳ(r)/p̂_ℳ(r_max) - (m-1)log(sin[π r/2r_max])^2


The above optimization problem can be solved via a least-squares fit after estimating the standard deviation, σ, of p(r) (see appendix for details). Such a procedure could, in principle, result in a fractional estimate of dimension. If one only requires integer solutions, the optimal value of m can be estimated by rounding-off the least squares fit solution.



 §.§ Estimating Intrinsic Space


The intrinsic dimensionality estimates obtained in the previous subsection alludes to the existence of a mapping, that can transform the ambient representation to the intrinsic space, but does not provide any solutions to find said mapping. The mapping itself could potentially be very complex and our goal of estimating it is practically challenging.
concat = [rectangle, draw, fill=yellow!20, text width=1.0em, minimum height=1.0em, text centered, drop shadow]
conv = [rectangle, draw, fill=blue!20, text width=2.0em, text centered, minimum height=6em, drop shadow]
batchnorm = [rectangle, draw, fill=green!20, text width=2.0em, text centered, minimum height=6em, drop shadow]
relu = [rectangle, draw, fill=red!20, text width=2.0em, text centered, minimum height=6em, drop shadow]
circ = [draw,circle,fill=teal!20,node distance=2cm, drop shadow]
block = [rectangle, draw, fill=gray!20, text width=20em, text centered, rounded corners, minimum height=5em]


We base our solution to estimate a mapping from the ambient to the intrinsic space on Multidimensional scaling (MDS) <cit.>, a classical mapping technique that attempts to preserve the distances (similarities) between points after embedding them in a low-dimensional space. Given data points X={x_1,…,x_n} in the ambient space and Y={y_1,…,y_n} the corresponding points in the intrinsic low-dimensional space, the MDS problem is formulated as,

    min∑_i < j(d_H(x_i,x_j) - d_L(y_i,y_j))^2

where d_H(·) and d_L(·) are distance (similarity) metrics in the ambient and intrinsic space, respectively. Different choices of the metric, leads to different dimensionality reduction algorithms. For instance, classical metric MDS is based on Euclidean distance between the points while using the geodesic distance induced by a neighborhood graph leads to Isomap <cit.>. Similarly, many different distance metrics have been proposed corresponding to non-linear mappings between the ambient space and the intrinsic space. A majority of these approaches are based on spectral decompositions and suffer many drawbacks, (i) computational complexity scales as 𝒪(n^3) for n data points, (ii) ambiguity in the choice of the correct non-linear function, and (iii) collapsed embeddings on more complex data <cit.>.

To overcome these limitations, we employ a DNN to approximate the non-linear mapping that transforms the ambient representation, x, to the intrinsic space, y by a parametric function y=f(x; θ) with parameters θ. We learn the parameters of the mapping within the MDS framework,


    min_θ∑_i=1^n ∑_i=1^n[d_H(x_i,x_j) - d_L(f(x_i;θ),f(x_j;θ))]^2 + λθ_2^2

where the second term is a regularizer with a hyperparameter λ. Figure <ref> shows an illustration of the DNN based mapping. 

In practice, directly learning the mapping from the ambient to the intrinsic space is very challenging, especially for disentangling a complex manifold under high levels of compression. We adopt a curriculum learning <cit.> approach to overcome this challenge and progressively reduce the dimensionality of the mapping in multiple stages. We start with easier sub-tasks and progressively increase the difficulty of the tasks. For example, a direct mapping from ℝ^512→ℝ^15 is instead decomposed into multiple mapping functions ℝ^512→ℝ^256→ℝ^128→ℝ^64→ℝ^32→ℝ^15. We formulate the learning problem for L mapping functions (y^l=f_l(x;θ)) as:


    min_θ_1,…,θ_L∑_i=1^n ∑_j=1^n ∑_l=1^L    α_l[d_H(x_i,x_j) - d_L(y_i^l,y^l_j)]^2 + λθ_l_2^2

where θ_l are the parameters of the l-th mapping. Appropriately scheduling the α_l weights enables us to set it up as a curriculum learning problem.



§ EXPERIMENTS

In this section, first we will estimate the intrinsic dimensionality of multiple image representations over multiple datasets of varying complexity. Then, we will evaluate the efficacy of the proposed DeepMDS model in finding the mapping from the ambient to the intrinsic space while maintaining its discriminative ability.


 §.§ Datasets

We choose two different domains of classification problems for our experiments, face verification and image classification. We consider two different face datasets for the former and the ImageNet ILSVRC-2012 for the latter. Recall that DeepMDS is an unsupervised method, so category information associated with the objects or faces is neither used for intrinsic dimensionality estimation nor for learning the mapping from the ambient to intrinsic space.



LFW <cit.>: 13,233 face images of 5,749 subjects, downloaded from the web. These images exhibit limited variations in pose, illumination, and expression, since only faces that could be detected by the Viola-Jones face detector <cit.> were included in the dataset.



IJB-C <cit.>: IARPA Janus Benchmark-C (IJB-C) dataset consists of 3,531 subjects with a total of 31,334 (21,294 face and 10,040 non-face) still images and 11,779 videos (117,542 frames), an average of 39 images per subject. This dataset emphasizes faces with full pose variations, occlusions and diversity of subject occupation and geographic origin. Images in this dataset are labeled with ground truth bounding boxes and other covariate meta-data such as occlusions, facial hair and skin tone.



ImageNet <cit.>: The ImageNet ILSVRC-2012 classification dataset consists of 1000 classes, with 1.28 million images for training and 50K images for validation. We use a subset of this dataset by randomly selecting 100 classes with the largest number of images, for a total of 130K training images and 5K testing images.



 §.§ Representation Models

For the face-verification task, we consider multiple publicly available state-of-the-art face embedding models, namely, 128-dim FaceNet <cit.> representation and 512-dim SphereFace <cit.> representation. In addition, we also evaluate a 512-dim variant of FaceNet[https://github.com/davidsandberg/facenet] that outperforms the 128-dim version. All of these representations are learned from the CASIA WebFace <cit.> dataset, consisting of 494,414 images across 10,575 subjects. For image classification on the ImageNet dataset, we choose a pre-trained 34 layer version of the ResNet <cit.> architecture.



 §.§ Baseline Methods

Intrinsic Dimensionality:  We select two different algorithms for estimating the intrinsic dimensionality of a given representation, a classical k-nearest neighbor based estimator <cit.> and “Intrinsic Dimensionality Estimation Algorithm" (IDEA) <cit.>.



Dimensionality Reduction:  We compare DeepMDS against three dimensionality reduction algorithms, principal component analysis (PCA) for linear dimensionality reduction, Isomap <cit.> and denoising autoencoders <cit.> (DAE).



 §.§ Intrinsic Dimensions



Implementation Details: The ID estimates for all the methods we evaluate are dependent on the number of neighbors k. For the baselines, k is used to compute the parameters of the probability density. For our method, k parameterizes the construction of the neighborhood graph. For the latter, the choice of k is constrained by three factors; (1) k should be small enough to avoid shortcuts between points that are close to each other in the Euclidean space, but are potentially far away in the corresponding intrinsic manifold due to highly complicated local curvatures. (2) On the other hand, k should also be large enough to result in a connected graph i.e., there are no isolated data samples., and (3) k that best matches the geodesic distance distribution of a hypersphere of the same ID i.e., k that minimizes the RMSE. Figure <ref> shows the distance distributions for SphereFace with k=15, a 16-hypersphere and a 16-dim Gaussian. The close similarity of the pairwise distance distributions of these manifolds in the graph induced geodesic distance space suggests that the ID of SphereFace (512-dim ambient space) is 16. Figure <ref> shows the optimal RMSE for SphereFace[Similar curves for other representations and datasets can be found in the appendix.] at different values of m. For all the approaches we select the k-nearest neighbors using cosine similarity for SphereFace, Euclidean distance for ResNet and arc-length, d(x_1,x_2)=cos^-1(x_1^Tx_2/x_1x_2), for FaceNet features, as the latter are normalized to reside on the surface of a unitary hypersphere. Finally, for simplicity, we round the ID estimates to the nearest integer for all the methods.




Experimental Results: Table <ref> reports the ID estimates from the graph method for different values of k[* denotes final ID estimate that satisfies all constraints on k.] and for different representation models across different datasets. Due to lack of space we report the ID estimates of the baselines in the appendix. We make a number of observations from our results: (1) Surprisingly, the ID estimates across all the datasets, feature representations and ID methods are significantly lower than the dimensionality of the ambient space, between 10 and 20, suggesting that image representations could, in principle, be almost 10× to 50× more compact. (2) Both[Reported in appendix due to space constraints.] the k-NN based estimator <cit.> and the IDEA estimator <cit.> are less sensitive to the number of nearest neighbors in comparison to the graph distance based method <cit.>, but are known to underestimate ID for sets with high intrinsic dimensionality <cit.>. 



 §.§ Dimensionality Reduction

Given the estimates of the dimensionality of the intrinsic space, we learn the mapping from the ambient space to a plausible intrinsic space with the goal of retaining the discriminative ability of the representation. The true intrinsic representation (ID and space) is unknown and therefore not feasible to validate directly. However, verifying its discriminate power can serve to indirectly validate both the ID estimate and the learned intrinsic space.



Implementation Details: We first extract image features through the representations i.e., FaceNet-128, FaceNet-512 and SphereFace for face images and ResNet-34 for ImageNet-100. The architecture of the proposed DeepMDS model is based on the idea of skip connection laden residual units <cit.>. We train the mapping from the ambient to intrinsic space in multiple stages with each stage comprising of two residual units. Once the individual stages are trained, all the L projection models are jointly fine-tuned to maintain the pairwise distances in the intrinsic space. We adopt a similar network structure (residual units) and training strategy (stagewise training and fine-tuning) for the stacked denoising autoencoder baseline. From an optimization perspective, training the autoencoder is more computationally efficient than the DeepMDS model, 𝒪(n) vs 𝒪(n^2).

The parameters of the network are learned using the Adam <cit.> optimizer with a learning rate of 3×10^-4 and the regularization parameter λ=3×10^-4. We observed that using the cosine-annealing scheduler <cit.> was critical to learning an effective mapping. To facilitate classification on ImageNet in the intrinsic space, after learning the projection, we separately learn a linear as well as a k-nearest neighbor (k-NN) classifier on the projected feature vectors of the training set.




Experimental Results: We evaluate the efficacy of the learned projections, namely PCA, Isomap and DeepMDS, in the learned intrinsic space and compare their respective performance in the ambient space. Face representations are evaluated in terms of verification (TAR @ FAR) performance and classification on ImageNet-100 in terms of accuracy (Top-1 and Top-5). Given the ID estimate, designing an appropriate scheme for mapping the intrinsic manifold is much more challenging than the ID estimation itself. To show how dimensionality of the intrinsic space influences the performance of image representations, we evaluate and compare their performance at multiple intermediate spaces.

Face verification is performed on the IJB-C dataset following its verification protocol and on the LFW dataset following the BLUFR <cit.> protocol. Due to space constraints we only show results on the DeepMDS model here, corresponding results for the baseline dimensionality reduction methods can be found in the appendix. Figure <ref> shows the ROC curves for the IJB-C dataset and the precision-recall curves for a image retrieval task on ImageNet-100. Table <ref> reports the verification rate at FAR of 0.1% on the LFW dataset. Similarly, Table <ref> shows the Top-1 and Top-5 accuracy on ImageNet-100 for a pre-trained ResNet-34 representation via a parametric (linear) as well as a non-parametric (k-NN) classifier.


We make the following observations from these results: (1) for all the tasks the performance of the DeepMDS features up to 32 dimensions (for faces) is comparable to the original 128-dim and 512-dim features. The 10-dim space of DeepMDS on LFW, consisting largely of frontal face images with minimal pose variations and facial occlusions, achieves a TAR of 92.33% at 0.1% FAR, a loss of about 4.5% compared to the ambient space. The 12-dim space of DeepMDS on IJB-C, with full pose variations, occlusions and diveristy of subject, achieves a TAR of 62.25% at 0.1% FAR, compared to 69.32% in the ambient space. (2) the proposed DeepMDS model is able to learn a low-dimensional space up to the ID with a performance penalty of 5%-10% for compression factors of 30× to 40× for 512-dim representations, underscoring the fact that learning a mapping from ambient to intrinsic space is more challenging than estimating the ID itself. (3) In both tasks, we observe that the DeepMDS model is able to retain significantly more discriminative ability compared to the baseline approaches even at high levels of compression. Although DAE achieves comparative results on ImageNet-100 classification, DeepMDS significantly outperforms DAE for image retrieval tasks. While Isomap is more competitive than the other baselines it suffers from some  drawbacks: (i) Due to its iterative nature, it does not provide an explicit mapping function for new (unseen) data samples, while the autoencoder and DeepMDS models can map such data samples. Therefore, Isomap cannot be utilized to evaluate classification accuracy on the validation/test set of ImageNet-100 dataset, and (ii) Computational complexity of Isomap is 𝒪(n^3) and hence does not scale well to large datasets (IJB-C, ImageNet) and needs approximations, such as Nyström approximation <cit.>, for tractability.




Ablation Study: Here we demonstrate the efficacy of the stagewise learning process for training the DeepMDS model. All models have the same capacity. We consider four variants: (1) Direct mapping from the ambient to intrinsic space, (2) Direct+IS: direct mapping from ambient to intrinsic space with intermediate supervision at each stage i.e., optimize aggregate intermediate losses, (3) Stagewise learning of the mapping, and (4) Stagewise+Fine-Tune: the projection model trained stagewise and then fine-tuned. Table <ref> compares the results of these variations on the LFW dataset (BLUFR protocol). Our results suggest that stagewise learning of the non-linear projection models is more effective at progressively disentangling the ambient representation. Similar trend was observed on larger datasets (IJB-C and ImageNet). In fact, stagewise training with fine-tuning was critical in learning an effective projection, both for DeepMDS as well as DAE.



§ CONCLUDING REMARKS

This paper addressed two questions, given a DNN based image representation, what is the minimum degrees of freedom in the representation i.e., its intrinsic dimension and can we find a mapping between the ambient and intrinsic space while maintaining the discriminative capability of the representation? Contributions of the paper include, (i) a graph induced geodesic distance based approach to estimate the intrinsic dimension, and (ii) DeepMDS, a non-linear projection to transform the ambient space to the intrinsic space. Experiments on multiple DNN based image representations yielded ID estimates of 9 to 20, which are significantly lower than the ambient dimension (10× to 40 ×). The DeepMDS model was able to learn a projection from ambient to the intrinsic space while preserving its discriminative ability, to a large extent, on the LFW, IJB-C and ImageNet-100 datasets. Our findings in this paper suggest that image representations could be significantly more compact and call for the development of algorithms that can directly learn more compact image representations.



§ APPENDIX


In this supplementary material we include; (1) Section <ref>: direct training of low-dimensional representations, (2) Section <ref>: intrinsic dimensionality estimates from the baseline approaches <cit.>, (3) Section <ref>: evaluation of the baseline dimensionality reduction techniques on the LFW and IJB-C datasets, (4) Section <ref>: derivations of the intrinsic dimensionality estimation process, (5) Section <ref>: RMSE and fitting plots for the graph distance based approach <cit.>, and (6) Section <ref> intrinsic dimensionality estimation and learning and visualizing the learned projections on the Swiss Roll dataset.



 §.§ Direct Training 

Our findings in this paper, that many current DNN representations can be significantly compressed, naturally begs the question: can we directly learn embedding functions that yield compact and discriminative embeddings in the first place? Taigman et al. <cit.> study this problem in the context of learning face embeddings, and noted that a compact feature space creates a bottleneck in the information flow to the classification layer and hence increases the difficulty of optimizing the network when training from scratch. Given the significant developments in network architectures and optimization tools since then, we attempt to learn highly compact embedding directly from raw-data, using current best-practices, while circumventing the chicken-and-egg problem of not knowing the target intrinsic dimensionality before learning the embedding function. 

We train[We build off of the publicly available implementation at <https://github.com/davidsandberg/facenet>] the Inception ResNet V1 <cit.> on the CASIA-WebFace <cit.> for embeddings of different sizes. Figure <ref> shows the ROC curves on the LFW and IJB-C datasets. The models suffer significant loss in performance as we decrease the dimensionality of the embeddings. In comparison the proposed DeepMDS based dimensionality reduction retains its discriminative ability even at high levels of compression. These results call for the development of algorithms that can directly learn compact and effective image representations.




 §.§ Intrinsic Dimensionality Estimation 

Table <ref> and Table <ref> reports the ID estimates from the k-nearest neighbor approach <cit.> and IDEA <cit.>, respectively, for different representation models across different datasets that we consider. These approaches are known to underestimate the intrinsic dimensionality <cit.>. We observe the same as our ID estimates for the baselines are lower than the estimates of the graph distance based approach that we use.





 §.§ Intrinsic Dimension Mapping 

In this section we present results of DeepMDS on LFW (BLUFR) dataset and the baseline dimensionality reduction methods for mapping from the ambient to the intrinsic space. Figure <ref> show the face verification ROC curves of DeepMDS on LFW dataset for FaceNet-128, FaceNet-512 and SphereFace representation models. Figure <ref> show the face verification ROC curves of Principal Component Analysis on the IJB-C and LFW (BLUFR) datasets for all the three representation models. Similarly, Fig. <ref> and Fig. <ref> show the face verification ROC curves of the Isomap and Denoising Autoencoder baselines, respectively.








 §.§ Intrinsic Dimensionality Estimation (Derivations) 

We first show the derivation for estimating the intrinsic dimensionality m that minimizes the RMSE with respect to a m-hypersphere,

    min_m∫_r_max-2σ^r_maxlogp̂_ℳ(r)/p̂_ℳ(r_max) - (m-1)log(sin[π r/2r_max])^2


First we estimate σ for the m-hypersphere by approximating the distribution p̂_ℳ(r) by a univariate Gaussian distribution around the mode of p_ℳ(r). So, given samples S={r_1,…,r_T} from the distribution p(r), the variance around the mode can be estimated as, σ^2 = 1/T∑_t=1^T (r_t-r_max)^2, where r_max is the radius at the mode of p̂_ℳ(r). Then, we estimate the distribution logp̂_ℳ(r)/p̂_ℳ(r_max) vs log(sin[π r/2r_max]) and solve the following least-squares fit problem:

    min_m∑_S ∩  r_max -2σ≤ r_i ≤ r_max(y_i - (m-1)x_i)^2

where y_i=logp̂_ℳ(r_i)/p̂_ℳ(r_max) and x_i=log(sin[π r/2r_max]).

In the case of comparison to a Gaussian distribution, the intrinsic dimensionality can also be estimated by comparing to the geodesic distance distribution for points sampled from a Gaussian distribution as,

    min_d∫_r_max-2σ^r_maxlogp(r)/p(r_max) + (d-1)r^2/4σ^2_2^2

The solution of this optimization problem can be found following the same procedure described above for a m-hypersphere.



 §.§ Intrinsic Dimensionality Estimation Fitting 

Figure <ref> shows the distribution of geodesic distances p(r) for each of the datasets and representation models. Figure <ref> shows the plot of logp̂_ℳ(r)/p̂_ℳ(r_max) vs logr/r_max, as we vary the number of neighbors k, for the SphereFace representation model on the LFW and IJB-C datasets and ResNet-34 on the ImageNet dataset.





 §.§ Swiss Roll 

In this section we consider the swiss roll dataset, as a means of providing visual validation of the estimated intrinsic space on a known dataset. First we estimate the intrinsic dimensionality of the swiss roll dataset and then we learn a low-dimensional mapping from the ambient 3-dim space to the intrinsic space. We sample 2000 points from the swiss roll dataset and use these points for the experiments. For this dataset, the intrinsic dimensionality estimate is 2 dimensions (see Figure <ref>, which is indeed the ground truth intrinsic dimensionality of swiss-roll.





ieee


