Maxime Bucher

Stéphane Herbin

Frédéric Jurie

Zero-Shot Classification by Generating Artificial Visual Features

This paper addresses the task of learning an image classifier when some categories are defined by semantic descriptions only (visual attributes) while the others are also defined by exemplar images. This task is often referred to as Zero-Shot classification (ZSC). Most of the previous methods rely on learning a common embedding space allowing to compare visual features of unknown categories with semantic descriptions. This paper argues that these approaches are limited as i) efficient discriminative classifiers can't be used and ii) classification tasks with seen and unseen categories (Generalized Zero-Shot Classification or GZSC) can't be addressed efficiently. This paper suggests to address ZSC and GZSC by i) learning a conditional generator using seen classes ii) generate artificial training examples for the categories without exemplars. ZSC is therefore turned into a standard supervised learning problem. Experiments with 4 generative models and 6 datasets experimentally validate the approach, giving state-of-the-art results on both ZSC and GZSC.

Introduction and related works

Zero-Shot Classification (ZSC) [START_REF] Christoph H Lampert | Attribute-Based Classification for Zero-Shot Visual Object Categorization[END_REF] addresses classification problems where not all the classes are represented in the training examples. ZSC can be made possible by defining a high-level description of the categories, relating the new classes (the unseen classes) to classes for which training examples are available (seen classes). Learning is usually done by leveraging an intermediate level of representation, the attributes, that provide semantic information about the categories to classify. As pointed out by [START_REF] Romera | An embarrassingly simple approach to zero-shot learning[END_REF] this paradigm can be compared to how human can identify a new object from a description of it, leveraging similarities between its description and previously learned concepts. Recent ZSC algorithms ( [START_REF] Akata | Multi-cue Zero-Shot Learning with Strong Supervision[END_REF][START_REF] Bucher | Improving semantic embedding consistency by metric learning for zero-shot classiffication[END_REF]) do the classification by defining a zero-shot prediction function that outputs the class y having the maximum compatibility score with the image x: f (x) = arg max y S(x, y). The compatibility function, for its part, is often defined as S(x, y; W ) = θ(x) t W φ(y) where θ and φ are two projections and W is a bilinear function relating the two in a common embedding. There are different variants in the recent litera- ture on how the projections or the similarity measure are computed [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF][START_REF] Changpinyo | Synthesized classifiers for zero-shot learning[END_REF][START_REF] Frome | DeViSE: A Deep Visual-Semantic Embedding Model[END_REF][START_REF] Norouzi | Zero-shot learning by convex combination of semantic embeddings[END_REF][START_REF] Romera | An embarrassingly simple approach to zero-shot learning[END_REF][START_REF] Weston | Wsabie: scaling up to large vocabulary image annotation[END_REF][START_REF] Xian | Latent embeddings for zero-shot classification[END_REF][START_REF] Zhang | Zero-Shot Learning via Semantic Similarity Embedding[END_REF], but in all cases the class is chosen as the one maximizing the compatibility score. This embedding and maximal compatibility approach, however, does not exploit, in the learning phase, the information potentially contained in the semantic representation of the unseen categories. The only step where a discriminating capability is exploited is in the final label selection which uses an arg max y decision scheme, but not in the setting of the compatibility score itself.

A parallel can be easily done between the aforementioned approaches and generative models such as defined in the machine learning community. Generative models estimate the joint distribution p(y, x) of images and classes, often by learning the class prior probability p(y) and the class-conditional density p(x|y) separately. However, as it has been observed for a long time [START_REF] Ulusoy | Generative versus Discriminative Methods for Object Recognition[END_REF], discriminative approaches trained for predicting directly the class label have better performance than model-based approaches as long as the learning database reliably samples the target distribution. Despite one can expect discriminative methods to give better performance [START_REF] Ulusoy | Generative versus Discriminative Methods for Object Recognition[END_REF], they can't be used directly in the case of ZSC for obvious reasons: as no images are available for some categories, discriminative classifiers cannot be learned out-of-the-box. This paper proposes to overcome this difficulty by generating training features for the unseen classes, in such a way that standard discriminative classifiers can be learned (Fig. 1). Generating data for machine learning tasks has been studied in the literature, [START_REF] Guo | Learning from imbalanced data sets with boosting and data generation -the DataBoost-IM approach[END_REF] or [START_REF] Bahy Bader-El-Den | Hierarchical classification for dealing with the Class imbalance problem[END_REF] to compensate for imbalanced training sets. Generating novel training examples from the existing ones is also at the heart of the technique called Data Augmentation, frequently used for training deep neural networks [START_REF] Lecun | Gradientbased learning applied to document recognition[END_REF]. When there is no training data at all for some categories, some underlying parametric transformation can be used to generate missing training data, assuming a mapping from the underlying transformation to the image space. [START_REF] Eggert | On the Benefit of Synthetic Data for Company Logo Detection[END_REF] generated images by applying warping and other geometric / photometric transformations to prototypical logo exemplars. A similar idea was also presented in [START_REF] Jaderberg | Reading Text in the Wild with Convolutional Neural Networks[END_REF] for text spotting in images. [START_REF] Maria | Embodied gesture learning from one-shot[END_REF] capture what they call The Gist of a Gesture by recording human gestures, representing them by a model and use this model to generate a large set of realistic gestures. We build in this direction, in the context of ZSC, the underlying representation being an attribute or text based description of the unseen categories. The transformation from attributes to image features is learned from examples of seen classes. A relevant way to learn this transformation is to use generative models such as denoising auto encoders [START_REF] Bengio | Generalized denoising auto-encoders as generative models[END_REF] and generative adversarial nets (GAN) [START_REF] Goodfellow | Generative adversarial nets[END_REF] or their variants [START_REF] Tong Che | Mode Regularized Generative Adversarial Networks[END_REF][START_REF] Makhzani | Adversarial autoencoders[END_REF]. GANs consist in estimating generative models via an adversarial process simultaneously learning two models, a generative model that captures the data distribution, and a discriminative model that estimates the probability that a sample came from the training data rather than the generator. The Conditional Generative Adversarial Nets of [START_REF] Mirza | Conditional Generative Adversarial Nets[END_REF] is a very relevant variant adapted to our problem. In addition to the advantage of using discriminative classifiers -which is expected to give better performance -our approach, by nature, can address the more realistic task of Generalized Zero-Shot Classification (GZSC). This problem, introduced in [START_REF] Chao | An empirical study and analysis of generalized zeroshot learning for object recognition in the wild[END_REF], assumes that both seen and unseen categories are present at test time, making the traditional approaches suffering from a decision bias towards seen classes, i.e. they are predominantly chosen. In contrast, the proposed approach uses (artificial) training examples of both seen and unseen classes during training, avoiding the aforementioned issues. Another reason to perform classification inference directly in the visual feature space rather than in an abstract attribute or embedding space is that data are usually more easily separated in the former, especially when using dis- criminant deep features that are now commonly available. Fig. 2 displays a 2D projection of the two kinds of representations and justifies this intuition. It can therefore be expected that a reliable conditional visual feature generator will be able to translate ZSC into a well separated supervised classification problem. This paper experimentally validates the proposed strategy on 5 standard Zero-Shot classification datasets (Animals with Attributes 1 (AWA1) [START_REF] Christoph H Lampert | Attribute-Based Classification for Zero-Shot Visual Object Categorization[END_REF], Animals with Attributes 2 (AWA2) [START_REF] Xian | Zero-shot learning-the good, the bad and the ugly[END_REF], SUN attributes (SUN) [START_REF] Patterson | Sun attribute database: Discovering, annotating, and recognizing scene attributes[END_REF], Apas-cal&Ayahoo (aP&Y) [START_REF] Farhadi | Describing objects by their attributes[END_REF] and Caltech-UCSD Birds-200-2011 (CUB) [START_REF] Wah | The caltech-ucsd birds-200-2011 dataset[END_REF]), and gives insight on how the approach scales on large datasets such as ImageNet [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF]. It shows state-of-the-art performance on all datasets for both ZSC and GZSC. This paper builds on [START_REF] Bucher | Generating visual representations for zero-shot classification[END_REF] and updates the evaluation to comply with the de facto evaluation standard on ZSC described in [START_REF] Xian | Zero-shot learning-the good, the bad and the ugly[END_REF]. We also compare our approach with papers that will be published soon [START_REF] Arora | Generalized zero-shot learning via synthesized examples[END_REF][START_REF] Xian | Feature generating networks for zero-shot learning[END_REF] and that exploit the same artificial feature generation idea that we previously proposed in [START_REF] Bucher | Generating visual representations for zero-shot classification[END_REF].

2 Approach

Zero shot classification

As motivated in the introduction, we address in this paper the problem of learning a classifier capable of discriminating between a given set of classes where empirical data is only available for a subset of it, the so-called seen classes.

In the vocabulary of zero-shot classification, the problem is usually qualified as inductive -we do not have access to any data from the unseen classes -as opposed to transductive where the unseen data is available but not the associated labels. We do not address in this paper the transductive setting, considering that the availability of target data is a big constraint in practice.

The learning dataset D s is defined by a series of triplets {x s i , a s i , y s i } Ns i=1 where x s i ∈ X is the raw data (image or features), y s i ∈ Y s is the associated class label and a s i is a rich semantic representation of the class (attributes, word vector or text) belonging to A s . This semantic repre-sentation is expected to i) contain enough information to discriminate between classes by itself, ii) be predictable from raw data and iii) infer unambiguously the class label y = l(a).

In an inductive ZSC problem, all that is known regarding the new target domain is the set of semantic class representations A u of the unseen classes. The goal is to use this information and the structure of the semantic representation space to design a classification function f able to predict the class label ŷ = f (x; A u , D s ). The classification function f is usually parametric and settled by the optimization of an empirical learning criterion.

Discriminative approach for ZSC

In ZSC, the main problem is precisely the fact that no data is available for the unseen classes. The approach taken in this paper is to artificially generate data for the unseen classes given that seen classes and their semantic representations provide enough information to do so, and then apply a discriminative approach to learn the class predictor.

The availability of data for the unseen classes has two main advantages: it can make the classification of seen and unseen classes as a single homogeneous process, allowing to address Generalized Zero Shot Classification as a single supervised classification problem; it potentially allows a larger number of unseen classes, which is for instance required for datasets such ImageNet [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF].

Let D u = {x u i , a u i , y u i }
Nu i=1 be a database generated to account for the unseen semantic class representation a u ∈ A u . The ZSC classification function becomes: ŷ = f D (x; D u , D s ) and can be used in association with the seen data D s , to learn a homogeneous supervised problem.

Generating unseen data

Our generators of unseen data build on the recently proposed approaches for conditional data generation as presented in section 1. The idea is to learn globally a parametric random generative process G using a differentiable criterion able to compare, as a whole, a target data distribution and a generated one. Given z a random sample from a fixed multivariate prior distribution, typically uniform or Gaussian, and w the set of parameters, new sample data consistent with the semantic description a are generated by applying the function: x = G(a, z; w). A simple way to generate conditional x data is to concatenate the semantic representation a and the random prior z as the input of a multi-layer network, as shown in Fig. 3. We now present 4 different strategies to design such a conditional data generator, the functional structure of the generator being common to all the described approaches.

Generative Moment Matching Network A first approach is to adapt the Generative Moment Matching Network (GMMN) proposed in [START_REF] Li | Generative moment matching networks[END_REF] to conditioning. The generative process will be considered as good if for each semantic description a two random populations X (a) from D s and X (a; w) sampled from the generator have low maximum mean discrepancy which is a probability divergence measure between two distributions. This divergence can be approximated using a Hilbert kernel based statistics [START_REF] Gretton | A kernel two-sample test[END_REF] -typically a linear combination of Gaussian functions with various widths -which has the big advantage of being differentiable and may be thus exploited as a machine learning cost. Network parameters w are then obtained by optimizing the differentiable statistics by stochastic gradient descent, using batches of generated and real data conditioned by the semantic description a.

Conditional Generative adversarial models Our second model builds on the principles of the generative adversarial networks (GAN), which is to learn a discrepancy measure between a true and a generated distributionsthe Discriminator -simultaneously with the data generator. One extension allowing to produce conditional distributions is the AC-GAN [START_REF] Odena | Conditional image synthesis with auxiliary classifier gans[END_REF] (Fig. 3) where the generated and the true distributions are compared using a binary classifier, and the quality of the conditional generation is controlled by the performance of this auxiliary task. This model bears similarities with the GMMN model, the key difference being that in the GMMN distributions of true and generated data are compared using the kernel based empirical statistics while in the AC-GAN case it is measured by a learned discriminative parametric model.

Denoising Auto-Encoder Our third generator relies on the work presented in [START_REF] Bengio | Generalized denoising auto-encoders as generative models[END_REF], where an encoder/decoder structure is proposed to design a data generator, the latent code playing the role of the random prior z used to generate the data. A simple extension able to introduce a conditional data generation control has been developed by concatenating the semantic representation a to the code that is fed to the decoder (Fig. 3).

In practice, this model is learned as a standard autoencoder, except that i) some noise is added to the input and ii) the semantic representation a is concatenated to the code in the hidden layer. For generating novel examples, only the decoder part, the head of the network using z and a as input to produce x is used.

Adversarial Auto-Encoder Our fourth generator is inspired by [START_REF] Makhzani | Adversarial autoencoders[END_REF], which is an extension of the denoising autoencoder. It introduces an adversarial criterion to control the latent code produced by the encoder part, so that the code distribution matches a fixed prior distribution. This extra constraint is expected to ensure that all parts of the sampling prior space will produce meaningful data.

During training, both the auto-encoder and the discriminator are learned simultaneously. For generating novel examples, as for the denoising auto-encoder, only the decoder part is used.

Implementing the generators

We implemented our 4 generative models with neural networks, whose architectures are illustrated Fig. 3. Hidden layers are fully connected (FC) with leaky-relu nonlinearity [START_REF] Andrew L Maas | Rectifier nonlinearities improve neural network acoustic models[END_REF] (leakage coefficient of 0.2). For the models using a classifier (the AC-GAN and the Adversarial autoencoder), the classifier is a linear classifier (fully connected layer + Softmax activation function). The loss used to measure the quality of the reconstruction in the two autoencoders is the L2 norm.

Regarding how to sample the noise z, we did not observe any difference between sampling it from a Gaussian distribution or from a uniform distribution.

Experiments

This section presents the datasets and the experimental settings, compares the different generative models described in the previous section, shows how our approach can be used for the Generalized Zero-shot Classification Taskwhich is one of the key contributions of the paper -, provides some experiments on a large Zero-Shot classification task, and, finally, compares our approach with state-of-the art Zero-Shot approaches on the regular Zero-shot Classification Task.

Datasets and Settings

The experimental evaluation is done on 5 standard publicly available ZSC benchmarks: Animals with Attributes 1 (AWA1) [START_REF] Christoph H Lampert | Attribute-Based Classification for Zero-Shot Visual Object Categorization[END_REF], Animals with Attributes 2 (AWA2) [START_REF] Xian | Zero-shot learning-the good, the bad and the ugly[END_REF], SUN attributes (SUN) [START_REF] Patterson | Sun attribute database: Discovering, annotating, and recognizing scene attributes[END_REF], Apascal&Ayahoo (aP&Y) [START_REF] Farhadi | Describing objects by their attributes[END_REF] and Caltech-UCSD Birds-200-2011 (CUB) [START_REF] Wah | The caltech-ucsd birds-200-2011 dataset[END_REF]. These benchmarks exhibit a great diversity of concepts: SUN and CUB are for fine-Grained categorization and include respectively birds and scenes images; AwA1 and AWA2 contain images of animals from 50 different categories; finally, aP&Y has broader concepts, from cars to animals. For each dataset, attributes descriptions are given, either at the class level or at image level. aP&Y, CUB and SUN have per image binary attributes that we average to produce per class real valued representations. In order to make comparisons with other works possible, we follow the same training/testing splits as [START_REF] Xian | Zero-shot learning-the good, the bad and the ugly[END_REF]. Image features are computed using the 2048-dim top-layer hidden unit activations of a 101-layered ResNet [START_REF] He | Deep residual learning for image recognition[END_REF]. We keep the weights learned on ImageNet fixed and don't apply any fine-tuning. The classifiers are obtained by adding a standard Fully Connected with Softmax layer to the pre-trained networks.

We purposively chose a simple classifier to better observe the behavior of the generators. In all our experiments we generated 500 artificial image features per class, which we consider to be a reasonable trade-off between accuracy and training time; we have not observed any significant improvement when adding more images. Each architecture has its own set of hyper-parameters (typically the number of units per layer, the number of hidden layers, the learning rate, etc.). They are obtained trough a 'Zero-shot' cross-validation procedure. In this procedure, 20% of the seen classes are considered as unseen (hence used as validation set), allowing to choose the hyper-parameters maximizing the accuracy on this soobtained validation set. In practice, typical values for the number of neurons (resp. the number of hidden layers) are in the range of [500-2000] (resp. 1 or 2). Model parameters are initialized according to a centered Gaussian distribution (σ = 0.02). They are optimized with the Adam solver [START_REF] Kingma | A method for stochastic optimization[END_REF] with a cross-validated learning rate (typically of 10 -4 ), using mini-batches of size 128 except for the GMMN where each batch contains all the training images of one class, to make the estimation of the statistics more reliable. In order to avoid over-fitting, we used dropout [START_REF] Srivastava | Dropout: a simple way to prevent neural networks from overfitting[END_REF] at every layer (probability of drop of 0.2 for the inputs layers and of 0.5 for the hidden layers). Input data (both image features and w2c vectors) are scaled to [0,1] by applying an affine transformation. With the Ten-sorFlow framework [START_REF] Abadi | TensorFlow: Large-scale machine learning on heterogeneous systems[END_REF] running on a Nvidia Titan X pascal GPU, the learning stage takes around 10 minutes for a given set of hyper-parameters.

Comparing the different generative models

Our first round of experiments consists in comparing the performance of the 4 generative models described in Section 2.3, on the regular and Generalized Zero-shot classification tasks. Performance is reported in Table 1 and Table 3. We can see that the GMMN model outperforms the 3 other ones, on average. Its optimization is also computationally more stable than the adversarial versions. We consequently chose this generator for the large scale Zero-Shot classification case. In order to have a better understanding of the behavior of the 4 models, we visualized the generated data, after projecting them in 2D with a T-SNE projection [START_REF] Van Der Maaten | Visualizing data using t-sne[END_REF]. The pro- jections are given Fig. 4). For each model, 10 images per class are generated and compared to 10 real images taken from unseen classes. As we can see, the GMMN model produced clusters that are, on average, very similar to the real data clusters.

We explain the superiority of the GMMN model by the fact it aligns the distributions by using an explicit model of the divergence of the distributions while the adversarial autoencoder and the AC-GAN have to learn it. For its part, the denoising autoencoder doesn't have any guaranty that the distributions are aligned.

Generalized Zero-Shot Classification task

In this section, we follow the Generalized Zero-Shot Learning (GZSC) protocol introduced by Chao et al [START_REF] Chao | An empirical study and analysis of generalized zeroshot learning for object recognition in the wild[END_REF]. In this protocol, test data are from any classes, seen or unseen. This task is more realistic and harder, as the number of class candidates is larger. We follow the notations of [START_REF] Xian | Zero-shot learning-the good, the bad and the ugly[END_REF]: u is the classification accuracy of test images from unseen classes, s is the classification accuracy of test images from seen classes and H denotes the harmonic mean between u and s.

In the two cases, the classifier is learned with training data combining image feature generated for unseen classes and real feature for seen classes. Most of the recent ZSC works, [START_REF] Akata | Evaluation of Output Embeddings for Fine-Grained Image Classification[END_REF][START_REF] Bucher | Hard negative mining for metric learning based zero-shot classification[END_REF][START_REF] Bucher | Improving semantic embedding consistency by metric learning for zero-shot classiffication[END_REF][START_REF] Romera | An embarrassingly simple approach to zero-shot learning[END_REF] are focused on improving the embedding or the scoring function. However, [START_REF] Chao | An empirical study and analysis of generalized zeroshot learning for object recognition in the wild[END_REF] has shown that this type of approach is unpractical with GZSC. Indeed the scoring function is in this case biased toward seen classes, leading to very low accuracy on the unseen classes. This can be seen on Table 1 (u column), where the accuracy drops significantly compared to regular ZSC performance. The data distribution of the ZSC datasets are strongly subject to this bias, as unseen classes are very similar to seen classes both in terms of visual appearance and attribute description. When seen and unseen classes are candidates, it becomes much harder to distinguish between them. For example, the horse (seen) and the zebra classes (unseen) of the AwA dataset cannot be distinguished by standard ZSC methods. Table 1 shows that the generative approach outperforms by a large margin all the other approaches that rely on a common semantic embedding. This gain can be explained by the fact that the discrimination step doesn't suffer from the bias induced by only learning from seen data. Two very recent works [START_REF] Arora | Generalized zero-shot learning via synthesized examples[END_REF][START_REF] Xian | Feature generating networks for zero-shot learning[END_REF] (to be published at CVPR'2018) that describe very similar approaches to the one we previously described in [START_REF] Bucher | Generating visual representations for zero-shot classification[END_REF] but with slight variations on the generative network, confirm the advantage of using generated data to solve the ZSC problem. We compared our approach with state-of-the-art methods on a large-scale Zero-Shot classification task. These experiences mirror those presented in [START_REF] Frome | DeViSE: A Deep Visual-Semantic Embedding Model[END_REF]: 1000 classes from those of the ImageNet 2012 1K set [START_REF] Russakovsky | Imagenet large scale visual recognition challenge[END_REF] are chosen for training (seen classes) while 20,345 others are considered to be unseen classes with no image available. Image features are computed with the GoogLeNet network [START_REF] Szegedy | Going deeper with convolutions[END_REF].

Large Scale Zero-Shot Classification

In contrast with ZSC datasets, no attributes are provided for defining unseen classes. We represent those categories using a skip-gram language model [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]. This model is learned on a dump of the Wikipedia corpus (≈3 billion words). Skip-gram is a language model learned to pre- dict context from words. The neural network has 1 input layer, 1 hidden layer and 1 output layer having the size of the vocabulary (same size as the input layer). The hidden layer has 500 neurons in our implementation. In the literature, the hidden layer has been reported to be an interesting embedding space for representing word. Consequently, We use this hidden layer to describe each class label by embedding the class name into this 500-dimensional space. Some classes cannot be represented as their name is not contained in the vocabulary established by parsing the Wikipedia corpus. Such classes are ignored, bringing the number of classes from 20,842 to 20,345 classes. For fair comparison, we take the same language model as [START_REF] Changpinyo | Synthesized classifiers for zero-shot learning[END_REF] with the same classes excluded.

As in [START_REF] Changpinyo | Synthesized classifiers for zero-shot learning[END_REF][START_REF] Frome | DeViSE: A Deep Visual-Semantic Embedding Model[END_REF] our model is evaluated on three different scenarios, with an increasing number of unseen classes: i) 2-hop: 1,509 classes ii) 3-hop: 7,678 classes, iii) All: all unseen categories.

For this task we use the Flat-Hit@K metric, the percentage of test images for which the model returns the true labels in the top K prediction scores.

Table 2 summarizes the performance on the 3 hops. As one can see, our model gets state-of the art performance for each configuration. As it can be observed from these experiments, our generative model is very suitable for this large scale GZSC problem, our approach improves by 5% best competitors for the Flat-Hit 1 metric on the 2-hop sce-nario.

Classical Zero-Shot Classification task

In this last section, we follow the protocol of the standard ZSC task: during training, only data from seen classes are available while at test time new images (from unseen classes only) have to be assigned to one of the unseen classes.

As explained in the introduction, the recent ZSC literature ( [START_REF] Akata | Evaluation of Output Embeddings for Fine-Grained Image Classification[END_REF][START_REF] Bucher | Hard negative mining for metric learning based zero-shot classification[END_REF][START_REF] Bucher | Improving semantic embedding consistency by metric learning for zero-shot classiffication[END_REF][START_REF] Romera | An embarrassingly simple approach to zero-shot learning[END_REF], etc) mostly focuses on developing a good embedding for comparing attributes and images. One of our motivations for generating training images was to make the training of discriminative classifiers possible, assuming it would result in better performance. This section aims at validating this hypothesis on the regular ZSC task. Table 3 summarizes our experiments, reporting the accuracy obtained by state of the art methods on the 5 ZSC datasets, with image features extracted from the 101layered ResNet [START_REF] He | Deep residual learning for image recognition[END_REF] network. Each entry is the mean accuracy computed on 5 different runs. Our method exhibits performances above state-of-the-art on each dataset (compared to embedding methods), with a noticeable mean improvement of more than 5%.

Conclusions

This paper introduces a novel way to address Zero-Shot Classification and Generalized Zero-Shot Classification [START_REF] Socher | Zero-Shot Learning Through Cross-Modal Transfer[END_REF] 34.6 28.0 39.9 39.5 37.9 36.0 SSE [START_REF] Zhang | Zero-Shot Learning via Semantic Similarity Embedding[END_REF] 43.9 34.0 51.5 60.1 61.0 50.1 LATEM [START_REF] Xian | Latent embeddings for zero-shot classification[END_REF] 49.3 35.2 55.3 55.1 55.8 50.1 ALE [START_REF] Akata | Label-Embedding for Image Classification[END_REF] 54.9 39.7 58.1 59.9 62.5 55.0 DEVISE [START_REF] Frome | DeViSE: A Deep Visual-Semantic Embedding Model[END_REF] 52.0 39.8 56.5 54.2 59.7 52.4 SJE [START_REF] Akata | Evaluation of Output Embeddings for Fine-Grained Image Classification[END_REF] 53.9 32.9 53.7 65.6 61.9 53.6 ESZSL [START_REF] Romera | An embarrassingly simple approach to zero-shot learning[END_REF] 53.9 38.3 54.5 58.2 58.6 52.7 SYNC [START_REF] Changpinyo | Synthesized classifiers for zero-shot learning[END_REF] 55. [START_REF] Bengio | Generalized denoising auto-encoders as generative models[END_REF]

Figure 1 :

 1 Figure 1: On opposite to traditional embedding approaches, our method consists in i) learning an image feature generator capable of generating artificial image representations from given attributes ii) learning a discriminative classifier from the artificially generated training data.

Figure 2 :

 2 Figure 2: CUB dataset: T-SNE visualization of feature vectors in (a) attribute space and (b) visual feature space. Data seem visually better separated in visual feature space.

Figure 3 :

 3 Figure 3: Architecture of the different generative models studied. z and a are respectively sample noise and semantic representation. F C + lrelu represents fully connected layer with leaky-relu non-linearity. x stands for real feature sample, x a generated one.

Figure 4 :

 4 Figure 4: AwA1 dataset: T-SNE visualization of artificial image representations generated by the GMMN, AC-GAN, ADV AE (Adversarial Auto-encoder), AE (Denoising Auto-encoder) and TRUE (real data). Best viewed on a computer screen with strong zoom factor.

Table 2 :

 2 Zero-shot and Generalized ZSC on ImageNet.

	Flat	Hit	@K

Our model is evaluated on three different scenarios: i) 2hop: 1,509 classes ii) 3-hop: 7,678 classes, iii) All: all unseen categories. (+1K) stands for the generalized case.

Table 1 :

 1 Generalized Zero-Shot classification accuracy. Image features are obtained with the 101-layered ResNet[START_REF] He | Deep residual learning for image recognition[END_REF] network. We follow the notations of[START_REF] Xian | Zero-shot learning-the good, the bad and the ugly[END_REF]: u is the classification accuracy of test images from unseen classes, s is the classification accuracy of test images from seen classes and H denotes the harmonic mean between u and s.

		Generalized Zero-Shot Learning
		CUB			P&Y			SUN			AWA1			AWA2
	Method	u	s	H	u	s	H	u	s	H	u	s	H	u	s	H
	DAP [26]	1.7 67.9 3.3	4.8 78.3 9.0	4.2 25.1 7.2	0.0	88.7 0.0	0.0 84.7 0.0
	IAP [26]	0.2	72.8 0.4	5.7 65.6 10.4 1.0 37.8 1.8	2.1 78.2 4.1	0.9 87.6 1.8
	CONSE [35]	1.6 72.2 3.1	0.0 91.2 0.0	6.8 39.9 11.6 0.4 88.6 0.8	0.5 90.6 1.0
	CMT [40]	7.2 49.8 12.6 1.4 85.2 2.8	8.1 21.8 11.8 0.9 87.6 1.8	0.5 90.0 1.0
	CMT* [40]	4.7 60.1 8.7	10.9 74.2 19.0 8.7 28.0 13.3 8.4 86.9 15.3 8.7 89.0 15.6
	SSE [49]	8.5 46.9 14.4 0.2 78.9 0.4	2.1 36.4 4.0	7.0 80.5 12.9 8.1 82.5 14.8
	LATEM [46]	15.2 57.3 24.0 0.1 73.0 0.2	14.7 28.8 19.5 7.3 71.7 13.3 11.5 77.3 20.0
	ALE [2]				4.6 73.7 8.7	21.8 33.1 26.3 16.8 76.1 27.5 14.0 81.8 23.9
	DEVISE [18]	23.8 53.0 32.8 4.9 76.9 9.2	16.9 27.4 20.9 13.4 68.7 22.4 17.1 74.7 27.8
	SJE [3]	23.5 59.2 33.6 3.7 55.7 6.9	14.7 30.5 19.8 11.3 74.6 19.6 8.0 73.9 14.4
	ESZSL [38]	12.6 63.8 21.0 2.4 70.1 4.6	11.0 27.9 15.8 6.6 75.6 12.1 5.9 77.8 11.0
	SYNC [11]	11.5 70.9 19.8 7.4 66.3 13.3 7.9 43.3 13.4 8.9 87.3 16.2 10.0 90.5 18.0
	MLZSL [7, 8]	22.9 60.0 33.2 3.4 77.9 6.5	19.6 45.0 27.3 16.5 78.6 27.3 15.8 79.2 26.3
	SAE [25]	7.8 54.0 13.6 0.4 80.9 0.9	8.8 18.0 11.8 1.8 77.1 3.5	1.1 82.2 2.2
	f-CLSWGAN [47] 43.7 57.7 49.7 -	-	-	42.6 36.6 39.4 57.9 61.4 59.6 -	-	-
	RG-GZSL [4]	31.9 -	40.0 -	-	-	32.9 -	25.5 42.2 -	54.1 56.7 -	65.1
	GMMN	49.1 55.9 52.3 28.5 64.4 39.5 39.7 37.7 38.7 51.5 70.1 59.3 46.3 77.3 57.9
	AE	16.3 31.6 21.5 24.8 38.9 29.6 9.1 22.0 12.9 49.3 52.8 51.0 49.5 63.3 55.7
	Ad. AE	17.3 51.9 25.9 28.0 60.4 38.2 11.2 27.1 15.8 56.6 67.0 61.3 50.8 76.6 61.0
	AC-GAN	18.3 37.2 24.5 6.9 75.7 12.6 22.9 20.6 21.7 0.45 81.9 0.9	2.4 89.8 4.7

Table 3 :

 3 Zero-shot classification accuracy. We report results image features extracted from the 101-layered ResNet[START_REF] He | Deep residual learning for image recognition[END_REF] network.

		Standard Zero-Shot Learning
	Method	CUB P&Y SUN AWA1 AWA2 Avg.
	DAP [26]	40.0 33.8 39.9 44.1	46.1	40.8
	IAP [26]	24.0 36.6 19.4 35.9	35.9	30.4
	CONSE [35]	34.3 26.9 38.8 45.6	44.5	38.0
	CMT

  tasks by learning a conditional generator from seen data and generating artificial training examples for the categories without exemplars, turning ZSC into a standard supervised learning problem. This novel formulation addresses the two main limitation of previous ZSC method, their intrinsic bias for Generalized Zero-Shot Classification tasks and their limitations discriminative classifiers in the deep image feature space. Our experiments with 4 generative models and 6 datasets experimentally validate the approach and give state-of-the-art performance.

		23.9 56.3 54.0	46.6	47.3
	MLZSL [7, 8]	53.5 39.5 57.6 58.1	61.1	54.0
	SAE [25]	33.3 8.3 40.3 53.0	54.1	37.8
	f-CLSWGAN [47] 57.3 -	60.8 68.2	-	-
	RG-GZSL [4]	59.6 -	63.3 69.5	69.2	-
	GMMN	59.4 41.7 60.1 70.7	69.9	60.4
	AE	53.7 33.9 54.2 69.4	69.4	56.1
	Ad. AE	53.4 37.9 58.5 68.2	70.3	57.7
	AC-GAN	38.7 38.1 47.2 59.4	57.7	48.2

Acknowledgements

Maxime Bucher is supported by a scholarship from the Région Normandie and from ONERA.


Joshua A Dijksman

Lenka Kovalcinova

Jie Ren

Robert P Behringer

Miroslav Kramár

Konstantin Mischaikow

Lou Kondic

Miroslav Kramar

Characterizing Granular Networks Using Topological Metrics

published or not. The documents may come   L'archive ouverte pluridisciplinaire

An important class of particulate systems includes granular materials, colloids, foams and molecular glass formers.

These materials can become "rigid", or "jammed", in the absence of long range spatial order. Jammed states are solids in mechanical equilibrium, with non-zero elastic moduli [1,2]. In order to be in mechanical equilibrium, forces must be transferred from particle to particle, creating self-organized networks of contacts and forces. These networks undergo rearrangements when shear induced deformation of the materials occurs. The networks are typically spatially heterogeneous [START_REF]Micromechanics of Granular Materials[END_REF], and during deformation, they are temporally intermittent, with avalanches, slip events, fracture and elasto-plastic failure modes. Finding the microscopic metrics responsible for this broad spectrum of mechanical behaviors across the solid-liquid transition has been challenging, since many of the conventional tools for characterizing ordered thermal systems do not apply.

Understanding how granular materials self-organize into mechanically stable states requires consideration of the structure of force networks. Figure 1 shows examples of typical force networks found in the experiments and simulations. A full description of the force network requires a high dimensional space that reports on microscopic features and does not directly reveal its mesoscopic structure. In order to understand this structure, we need statistical tools for their characterization that are sensitive, systematic, unbiased, minimal, and consistent with macroscopic properties, such as the system-wide stresses. These tools must also be able to distinguish different states of the system, based on force networks.

To demonstrate the need for mesoscopic description of Examples of an experimental (a) and numerical (b) force network. Experimental and numerical examples are generated at the same strain amplitude γ = 14.9% and φ = 0.8036. The color scale represents the total force at each contact, normalized by the concurrent mean force. As described in the text, the simulation results in this and all the following figures include additional noise of amplitude 0.01 N, except if specified differently.

the force network we will consider the granular response to quasi-static shear strain, γ, which is analogous to time in a more conventional dynamical system. The structure of the network as a granular system is strained shows a sensitive dependence on the initial conditions. We show that simple topological measures detect the variability in force networks formed in response to shear in quasitwo-dimensional granular systems. These metrics capture features that are missed by conventional measures, such as stresses or contact force distributions.

In this article, we consider two realizations of a particular granular system: experimental and computational. The studies of these realizations show the importance of the fraction of non-rattler particles, f N R , defined as particles with at least two contacts, as a relevant state variable. In particular, the considered metrics fall onto master curves when expressed as functions of f N R . These metrics include traditional measures, such as contact numbers, stresses, and contact force probability distribution functions which identify system-wide as well as microscopic features. We observe a good match between the experimental and computational systems at these scales.

However, at the mesoscale, there are clear differences identified using topological metrics. We conjecture that the differences arise from small imperfections and noise in the experiments that are absent in the simulations. The topological metrics that we employ are sensitive to the force noise in the experimental data sets and capture these differences. Our conjecture is reinforced by the fact that by introducing appropriate random noise in the simulations we can generate a reasonable match between the statistics of the topological networks in simulations and experiments. This finding suggests that the considered topological measures may have an important utility in quantifying the properties of intrinsic noise that is always involved in the experiments. As a consequence, topological techniques provide new opportunities for identifying the scale of the experimental noise, and distinguishing noise from intrinsic fluctuations.

Topological metrics Although there exists a number of tools to extract network information, see [START_REF] Albert | [END_REF]5] for reviews, recent work [6][7][8][9][10][11][12][13] demonstrates that topological methods are well suited to characterize force networks in granular packings. In this Letter, we use the Betti numbers β 0 and β 1 to quantify the topology of a network, where β 0 indicates the number of clusters or connected components of the network, and β 1 characterizes the number of loops. Thus, in a rough sense, β 0 is a measure of force network segments, and β 1 is related to their interconnectivity. Computations were performed using software Perseus [14]. In particular, we are interested in the properties of the (simplicial complex) network that describes the force interactions between the particles with force magnitude larger than f c . We pick f c = 1.0 |f| in our analysis (here |f| is the average force), and note that results are not very sensitive to this choice of threshold. This network is constructed in the following manner. Every particle, p i , is represented by a vertex, v i . The edge < v i , v j > belongs to the network if the magnitude of the force interaction, between the corresponding particles p i and p j , is larger than f c . In our construction, we decided to fill in the loops formed by three interacting particles, i.e. we include the triangle < v i , v j , v k > if the pairwise force interactions between the particles exceed f c . Therefore the boundary of the loops detected by β 1 must contain at least four edges.

While more elaborate tools from algebraic topology

FIG. 2.
The evolution of the fraction of particles with contact number Z2,3,4,5 as a function of the fraction of nonrattlers fNR, for both experiments (•) and simulations ( ) for a range of φ's (color scale). Numerical data color coding has been increased by 0.015 in this and all the following figures as discussed in the text.

have been used to quantify force networks in simulations [15,16], in the present work we restrict ourselves to the simple measures described above. The reasons for this choice are twofold: (i) This method allows for a direct comparison of the statistical properties of force networks between simulations and experiments. To our knowledge, such comparison has not been attempted so far. (ii) These methods show potential for assessing the type and size of the noise present in the data [START_REF] Bobrowski | To appear in: Topology in Statistical Inference[END_REF].

Experimental Details The experiments involve shear of constant-density two dimensional packings of ∼ 1000 photoelastic bidisperse disks, starting from a stress free state. The packing density is given in terms of the packing fraction, φ. The particles interact via force laws that include friction, and the result is that the applied strain shear-jams the packing [27]. This protocol allows one to probe a large range of mechanically distinct states, from very loose to highly jammed packings. In particular, we use experimental data obtained in a simple shear geometry described in [START_REF] Ren | American Physical Society, Topical Group on Statistical and Nonlinear Physics[END_REF][START_REF] Ren | [END_REF] -see the Appendix for details. The particles rest on a co-moving, articulated base, that through its boundaries induces a linear shear profile, suppressing shear bands and other large scale inhomogeneities. We prepare packing fractions from 0.75 ≤ φ ≤ 0.825. We consider results for packings in the range 0.77 ≤ φ ≤ 0.825, where φ = 0.77 is the lowest packing fraction for which we achieve shear jammed states with this apparatus. We then quasi-statically shear the system by a sequence of 100 strain steps of 0.27% each, for a maximum strain of γ = 27% [START_REF] Ren | American Physical Society, Topical Group on Statistical and Nonlinear Physics[END_REF], and extract the information about all the forces the particles experience [START_REF] Ren | [END_REF]. The force extraction algorithm is applied to each particle individually. Hence, every contact between two particles yields two force vectors. In the topological analysis we use the average of the norms. Note that this approach has its limitations. First, there exists a lower force threshold below which we cannot detect contacts. By examining the best contact number dynamics match with the numerics for a range of thresholds, we estimate this threshold to be ≈ 0.001N . Second, for larger pressures, P , we reach a force level such that deformations at contacts become large. We note that the force inverse algorithm assumes small deformations at contacts to make the process more efficient and becomes increasingly inaccurate when f N R > 0.95 where deformations are large, so we omit this (small) data set from the analysis where forces are involved. The exact value of this cutoff is not crucial for the present purposes. Furthermore, this is not an intrinsic limitation on the technique; however, since we are mostly interested in behavior near jamming where forces are moderate, amending current algorithms is not necessary.

Simulation Details Despite the simplicity of the numerical scheme, it is highly nontrivial to select the right packing preparation protocol. This sensitivity of granular mechanics to initial preparation is well known even for frictionless systems [21] yet makes a direct comparison between numerical and experimental results very nontrivial. Note that regardless of the preparation protocol chosen, the qualitative behavior observed was always similar; notably the collapse of all data sets as a function of f N R is particularly robust. Two features however required protocol fine tuning: the density range and offset in which the shear jamming was observed and the network anisotropy. The contact number dynamics and pressure dynamics were not dependent on preparation.

The simulations use a soft-particle non-linear force model and reproduce the experimental settings as closely as possible. The shear geometry, particle sizes and numbers, friction coefficients, density and elastic moduli used in the numerical simulations match the experimental values as taken from the current data or previous work [START_REF] Ren | [END_REF]27]. The inelasticity of the particles is modeled through a coefficient of restitution, frictional interaction between the particles using the Cundall-Strack model [22]. We also simulate a moving base, including translational and rotational friction between the base and the particles. The details of implementation can be found in the Appendix. The simulations reported here are carried out for the same values as for which we have experimental data. We show below that simulations produce results that are comparable to experiments.x As we will discuss in more detail later, we add random noise to simulation data: all the figures in the paper include this additional noise, unless otherwise specified. Importantly, the essential results shown in Figs. 123are insensitive to the noise addition.

Common features of experiments and simulations We extract particle positions and inter-particle forces for each particle at every 0.27% strain step, and we com- pute the local stress tensor σ using the Irving-Kirkwood method [23]. This provides the pressure from the sum of its eigenvalues P = (σ 1 + σ 2 )/2 the shear stress, τ = (σ 2 -σ 1 )/2 and the stress anisotropy, τ /P . At each φ, we carry out five realizations in both numerics and experiments, and average the results.

To illustrate the degree of agreement between experiments and simulations when conventional measures are considered, we start by exploring the average number of contacts per particle, Z. This is an important quantity since there is a minimum or isostatic value of Z, Z iso for marginal stability. For frictional particles, Z iso = N + 1, where N is the system dimension, e.g. Z iso = 3 for 2D frictional disks. If a system is sheared from zero stress into a shear jammed state, Z must reach at least Z iso = 3 when the system becomes jammed. However, the parts of the force network that first form during the shear jamming process contain a number of particles with only two contacts. Hence, it is relevant to consider not only Z, but also Z n (φ, γ), the fraction of particles with n contacts.

A key finding in [27] is that many properties such as stresses and Z depend on f N R , in a universal way. Here we show that f N R also determines the dynamics of Z n (φ, γ). Figure 2 shows data for Z 2,3,4,5 vs. f N R . There are two outstanding features in this data: (i) the dynamics of each Z n collapses on a single curve, independent of φ; and(ii) the agreement between experiments and simulations is quantitative. We thus conclude that the simulations reproduce the experiments very well, and that f N R can be used as an apparently universal state variable to describe the state of the system.

Figure 3 shows other conventional measures comparing the experimental and the numerical data: in Fig. 3a we see that the experimental pressure data for all φ's collapse to a single curve. Furthermore, we find power law scaling for P vs. 1 -f N R . Intuitively, the inverse relation between P and f N R makes qualitative sense: the larger the fraction of rattlers, 1 -f N R , the smaller the pressure. However, the power law nature of this relation is not trivial. For the simulations, we also find an excellent collapse of P vs. 1 -f N R , via a power-law, although the dynamics deviates from power law scaling at large nonrattler fractions, and note a small deviation in the overall pressure scale. A quantitative magnitude agreement in particular in the pressure is sensitive to the choice of inclusion of rattlers, the force law used in the numerics and the area normalization choice in the Irving-Kirkwood formalism, and hence more challenging to get consistent among the experimental and numerical data sets. However, the trends of f N R collapse and P (f N R ) are mostly insensitive to this.

Figure 3b shows the stress anisotropy, given by τ /P . We find an initial rapid increase of τ from the randomly prepared nominally isotropic stress-free initial state. After this transient, the anisotropy shows only a modest decrease with f N R for both experiments and simulations, while it remains nonzero. The decreasing trend is consistent with the observation that shear jammed states initially have a very anisotropic network, that evolves towards a more isotropic one with increasing strain. The agreement between experiments and simulations is only qualitative, but even though there is modest scatter in the numerical data, the collapse with f N R is obvious.

Force Probability Distribution -A useful microscopic measure is the probability distribution function (PDF) of the norm of the contact forces P (|f|). Much work has been devoted to characterizing and understanding this distribution [24,25] although isotropically compressed packings have been the primary focus of past work. Here we examine P (|f|) vs. f N R , and contrast the experimental P (|f|) and numerical data. Figure 3c shows the probability of finding a contact force of a certain magnitude in the entire data set at φ = 0.7863. The numerical and experimental histograms are again very similar; the only difference is most likely due to the use of a linear force law in the numerics, where the particles have a much more non-linear interaction. Regardless, the probability distribution function again shows a good collapse with f N R . In Figure 3d we show the bin with force range 1.1 -1.2 |f| . Two features are prominent: First, in both experimental and numerical data, there are good collapses with f N R . Second, experimental and numerical data are in quantitative agreement. The collapse with f N R is observed for other force bins; for example, we have verified that the same feature are observed for force bin centered on 0.5 |f| and 1.5 |f| (see Appendix).

The previous metrics have addressed either macro- scale or micro-scale structural properties, but do not provide detailed information about the structure of force networks, such as those shown in Fig. 1. We now use topological metrics to analyze the properties of the network that describes the force interactions between the particles with force magnitude larger than f c = 1.0 |f| . Figure 4a shows the resulting Betti number dynamics for the experiments. β 0 shows a plateau around 100 and subsequently a decrease. Simulations without added noise (Figure 4c) however, show very different results with much smaller values of β 0 : they are essentially independent of f N R . This observation is in a sharp contrast to the findings for more conventional measures, for which experimental and numerical simulations showed at least a qualitative agreement. We see a similar difference in the β 1 dynamics in Figure 4b,d: the numerical data do not seem to asymptote to β 1 = 0 in the limit of f N R → 0.

The question is: what causes such a dramatic difference in the numerical and experimental network properties? To explain the larger number of the connected components present in the experimental data we propose the following mechanism. Consider the part of the contact network at which the particle interactions are a little below f c . A slight increase of a single interaction in this region will introduce a new connected component. On the other hand a slight decrease of single interaction, at the region where the interactions are just a little above f c might result in breaking a connected component into two pieces. Noise will thus affect topological features in the network. To explore this possibility, we add random noise to the simulations results. The random noise that we use is chosen from a flat distribution within the range of [0, 0.01]N that is consistent with the expected level of error in the experiments -see Fig. 3c. Note that after the noise is added to the contact forces, a small force inbalance may result on the particles. The non-zero mean of the added noise is motivated by the fact that we consider here a (positive definite) norm of the force vector.

After noise addition, the agreement between experimental and simulations improves significantly for both β 0 and β 1 . Figures 4e shows a monotonically decreasing behavior of β 0 , much more in line with experimental data. For β 1 we observe quantitative agreement between experiments and simulations. Again, for both β 0 and β 1 we see a good collapse when we consider these quantities as functions of f N R .

Conclusions -In this paper, we have presented one of the first attempts to directly compare microscopic contact force level data from experiments and simulations of dense granular systems. We perform the comparison with metrics across the scales that range from micro to meso and macro. The comparison of micro and macro measures is mostly satisfactory. In particular, we find for both experiments and simulations that, when we express the contact number, pressure, anisotropy, or probability density function of the normal forces as a function of the non-rattler fraction, f N R , we obtain collapse onto master curves, capturing the dynamics over a wide range of conditions.

After finding good agreement for the quantities specified above, it is perhaps surprising to see that the force network in the experiments and simulations, described by Betti numbers, are qualitatively different when raw data from simulations are considered. We argue that contact force noise can be of significant influence on mesoscopic network features, and test this by including adding artificial noise to simulation results. We find that after adding noise of small magnitude, the mesoscopic Betti number dynamics is very similar between experiments and numerics.

On the one hand, the fact that noise influences the properties of force networks, but not classical micro and macro measures listed above is encouraging, since it suggests that the quantities that are commonly observable in granular experiments should not be influenced by typical (experimental) noise. On the other hand, the fact that noise had to be added to simulation results to reach agreement with experiments suggests that direct comparison of the force network properties may be difficult to reach. However, sensitivity of the force networks' properties to noise opens the door towards the use of topological measures to quantify the experimental noise level and its properties, and to distinguish intrinsic fluctuations from experimental noise. Our future work should consider additional measures to provide even better understanding of the properties of force networks and their connection to macroscopic response of particulate-based systems.

Appendix Methods: Experiments -We discuss here experimental data obtained in a setup described in detail elsewhere [START_REF] Ren | American Physical Society, Topical Group on Statistical and Nonlinear Physics[END_REF][START_REF] Ren | [END_REF]. We expose ∼ 1000 bi-disperse photoelastic particles in a linear shear cell with articulated bottom. The articulated bottom shear induces linear shear profile, suppressing shear bands other inhomogeneities. We extract the local particle stress by either a nonlinear pattern-fitting algorithm discussed previously [26][27][28] that yields the complete contact network, particle forces, and stress tensor (e.g. P and τ ), or via G 2 , the local squared intensity gradient of the photoelastic response, averaged on each particle. G 2 is a one-to-one function of P on the particle level, and provides an easy measure for P . For small data sets, we use the former approach; for larger data sets, we use the latter approach to get only P . In addition to P and τ , we can probe the contact number dynamics with great accuracy: due to the photoelastic response of the disks, we can determine contacts with much more sensitivity than typical distance based metrics [11]. We can thus measure the fraction of particles with n contacts, which we describe with Z n . We thus also have access to the number of non-rattlers f N R , the particles that are in a force bearing network. Recent work showed [27] showed that this was an important microstructural metric. We probe these structural metrics and force networks in shear jammed states by shearing the system. We prepared packings in a stress free initial state, for 0.75 ≤ φ ≤ 0.825. We then quasi-statically shear the system by 100 small strain steps of 0.27%, up to a total strain of γ = 27% [START_REF] Ren | American Physical Society, Topical Group on Statistical and Nonlinear Physics[END_REF]. For the larger φ's considered here, we could not apply the full 27% strain because P became so large that the layer of disks was unstable to out-of-plane buckling. If buckling occurs, we terminate the shear experiment. At each packing fraction, we carried out the same shear experiments five times for reproducibility. Beyond a compression level of about 10 N/m or, equivalently, f N R = 0.95, the compression of the disks is such that the visibly deform, and hence the force inversion method breaks down. We measure the quality of force extraction by calculating the total image difference between the original photoelastic images and their reconstructed equivalents, where the reconstructed image is based on the fitted contact forces. We show the results in Fig. 7. At large f N R we can clearly see that the image reconstruction becomes significantly different from the image as taken during the experiment, so we omit all data from f N R > 0.95.

Methods: Numerics -We perform discrete element simulations using a set of circular disks confined in an initially rectangular domain. The number of the particles ranges from 910 up to 1050, depending on the packing fraction and is set exactly to the number of particles in the experiments. The walls are composed of monodisperse disks. The domain is rectangular, and the length and width of the rectangle are 54 and 27 particle diameters, respectively. System particles are bidisperse and the ratio of the diameters of the large and small particles is ≈ 15.9/12.7. The exact positions and particle radii for all packing fractions and different realizations are taken from the initial conditions in the experiments. Particles are soft and interact via normal and tangential forces during collision, with static friction and viscous damping.

The force model used in the simulations is non-lienar; normal force between particles i and j is (see [START_REF] Kondic | Dynamics of spherical particles on a surface: Collision-induced sliding and other effects[END_REF] for more details)

F n i,j = k n x δ n -γ n x 0.5 mv n i,j (1)
r i,j = |r i,j |, r i,j = r i -r j , n = r i,j /r i,j k n = 2Y 3(1 -σ 2 ) d 1-β
ave where 1 + β = δ, v n i,j is set to the relative normal velocity and Y and σ are Young's modulus and Poisson ratio, respectively. The amount of compression is x = d i,j -r i,j , where d i,j = (d i + d j )/2; d i and d j are the diameters of the particles i and j and d ave is the average particle diameter. Here, r i , r j are the vectors pointing from the centers of particles i, j towards the point of contact.

The exponent δ in the force model is chosen to match the experimental calibration curve measuring the amount of compression of the photoelastic disk particle pressed by a steel plate with a given force. Figure 6 shows the experimental calibration curve and k n x δ curves for chosen values of δ with k n (dependent on δ, as specified in the set of Equations 1) and Y = 3.45 GPa and σ = 0.5 set to match the experiments. We find that choosing δ = 1.625 yields the least square difference between k n x δ and experimental calibration curve and therefore we use this value of δ in the force model for particle-particle interaction in the simulations.

Here, the characteristic lenghtscale is d ave , the average particle mass, m, is the mass scale and the binary particle collision time τ c is the time scale. The value of τ c is set to [START_REF] Kondic | Dynamics of spherical particles on a surface: Collision-induced sliding and other effects[END_REF] τ c = α(1 + 0.5β)

1 2+β m 3(1 -σ 2 ) 2Y d (1-β) ave 1 2+β v -β 2+β 0 (2)
where v 0 = 0.01423 ms -1 is a characteristic magnitude of velocity in the system (shearing speed); prefactor α and damping coefficient γ n is obtained as reported in [START_REF] Kondic | Dynamics of spherical particles on a surface: Collision-induced sliding and other effects[END_REF].

We implement the commonly used Cundall-Strack model for static friction [22], where a tangential spring is introduced between particles for each new contact that forms at time t = t 0 . Due to the relative motion of the particles, the spring length, ξ, evolves as ξ = t t0 v t i,j (t ) dt , where v t i,j = v i,j -v n i,j . For long lasting contacts, ξ may not remain parallel to the current tangential direction defined by t = v t i,j /|v t i,j | (see, e.g,. [START_REF] Brendel | Physics of Dry Granular Media[END_REF]); we therefore define the corrected ξ = ξn(n • ξ) and introduce the test force

F t * = -k t x β ξ -γ t x 0.5 mv t i,j (3)
where k t = 6/7k n (close to the value used in [START_REF] Goldenberg | Friction enhances elasticity in granular solids[END_REF]), γ t is the coefficient of viscous damping in the tangential direction (with γ t = γ n ). The value of µ = 0.7 is set to the inter-particle friction from the experiments. To ensure that the magnitude of the tangential force remains below the Coulomb threshold, we constrain the tangential force to be

F t = min(µ|F n |, |F t * |)F t * /|F t * | (4)
and redefine ξ if appropriate.

In the force model, we include interaction with the base. The force between the particle and the base has a translational and a rotational component and the particle-base friction coefficient is µ b = 0.4, corresponding to the reported experimental value. The magnitude of the deceleration of the particle in translational direction due to the friction with base is µ b |g| where g is the gravitational acceleration. The rotational deceleration of i-th particle due to friction with base

|α i | = 4 3 µ b |g| r i (5)
is computed by integrating torque arising from friction with the base and using the moment of inertia of the disk, I = (m i r 2 i )/2, where m i , r i are the values of mass and radius of the i-th particle, consecutively. For simplicity, we use r i = 1/3d ave for both small and large particles.

  FIG. 1.Examples of an experimental (a) and numerical (b) force network. Experimental and numerical examples are generated at the same strain amplitude γ = 14.9% and φ = 0.8036. The color scale represents the total force at each contact, normalized by the concurrent mean force. As described in the text, the simulation results in this and all the following figures include additional noise of amplitude 0.01 N, except if specified differently.

FIG. 3 .

 3 FIG. 3. (a) Pressure evolution versus 1-fNR for both experiments (•) and simulations ( ). (b) Normalized anisotropy τ /P evolution as a function of fNR. (c) histogram of contact force magnitudes |f | for all contacts in the five runs at φ = 0.7863 for both numerics and experiments. The dashed line indicates the force noise added after the numerical runs were completed. (d) The probability distribution function of the norm of the contact forces P (|f|) as a function of fNR for both experiments (•) and simulations ( ) for the force bin centered around 1.2 |f| .

FIG. 4 .

 4 FIG. 4. Betti numbers, β0 (left) and β1 (right), as a function of fNR for both experiments (a,b: •) and simulations (c-f, ). (a,b) show original numerical data; (c,d) show the numerical data with 0.01N noise added.

FIG. 5 .

 5 FIG.5. Integrated image difference Σ for the averaged experimental runs at different densities (color coding, same as main paper). There is a constant background difference due to pixel level noise and other artifacts. The dashed line at fNR = 0.95 represents the cutoff we impose in the data selection in the main paper.

FIG. 7 .

 7 FIG. 7. Probability distribution function of contact forces for a force magnitude bin of 1.2 |f|

Acknowledgments *JAD and LK contributed equally to this work. This work was partially supported by NSF-DMS-0835621, 0915019, 1125174, AFOSR Grant Nos. FA9550-09-1-0148, FA9550-10-1-0436 and DARPA (M.K., and K.M) HR0011-16-2-0033 (K.M, L.K, R.P.B) and NSF Grant No. DMS-0835611, and DTRA Grant No.

1-10-1-0021; NSF Grants DMR-12063251 and DMS1248071 and NASA grants NNX10AU01G and NNX15AD38G. MK was also supported by ERC project GUDHI (Geometric Understanding in Higher Dimensions).

We integrate Newton's equations of motion for both the translation and rotational degrees of freedom using a 4th order predictor-corrector method with time step ∆t = 0.02τ c .

From the initial configuration taken from the experiments, the system is sheared by moving the left wall in positive and the right wall in the negative direction. Shearing speed used in the simulations, expressed in the units of d ave /τ c , is v 0 = 2.5 × 10 -5 . Relaxation is interjected after each strain step of 0.27%. The maximum strain amplitude is 27%.

Consistency checks -In this section we present consistency checks; specifically, we focus on the distribution of the forces measured in both experiments and simulations for a different force bin than in the main body of the paper. Then we show that the particle-particle and particle-base friction is essential if we want to achieve a quantitative agreement between simulations and experiments.

In Figure 3d we show the probability distribution function of contact forces for a force magnitude bin of 1.2 |f| . In Figure 7 we show that the f N R collapse and consistency between experimental and numerical data is retained for the force bin around 0.5 |f| (a) and 1.5 |f| (b). Thus we conclude that our results comparing force distribution is not sensitive to the choice of the bin.

To demonstrate the importance of having a non-zero friction coefficient, we consider the dynamics of pressure and anisotropy for a few single runs with µ = 0.0 and µ b = 0.0 at various packing fractions around the jamming point as observed in our protocol. Figure 8 shows P and τ /P as a function of f nr for frictionless systems. Evidently, our numerical protocol does not produce the same f N R dynamics as the experiments, even though the pressure and anisotropy values remain within a similar range in jammed systems (especially for large f N R ).