summaries: The article proposes to address attribute detection with a small data constraint in the training phase (few-shot approach). The experimental protocol is divided in a series of episodes, each defined by a support set that specifies the attributes to be predicted and a query set used to evaluate the prediction. The generic algorithmic structure to solve this problem is divided in two steps: a common pre-training phase that combines self-supervised representation learning and supervised fine-tuning, followed by a supervised learning phase to solve each episode task. A training dataset containing image samples with attributes is used to learn the pre-trained representation space. The pre-training phase is compared to other approaches on three benchmarks implementing few-shot attribute prediction episodes. An indicator computed from a logistic regression between attribute values is proposed as a way to predict transferability between the learning dataset and the few-shot problem.

summaries: This paper proposes the problem of few-shot attribute learning (FSAL) that follows the standard few-shot/meta-learning paradigm but focuses on attributes instead of object classes. The authors argue in Section 2 that the multi-label nature of attributes (smiling & wearing eyeglasses can be present simultaneously) makes this problem different; the context of each positive example in each episode can drastically change what the model is asked to learn.   This paper also proposes three benchmark datasets to study this problem, based on Celeb-A, Zappos50K, and ImageNet-with-Attributes. The paper evaluates multiple existing approaches on these benchmarks as well as improves upon them further.

summaries: The authors consider the problem of few-shot attribute learning. Contrary to most past approaches on learning with attributes, including classical zero-shot learning, the authors deal with the case where the attributes seen at test-time are previously unseen. As a result, few samples must be used to quickly adapt the learning algorithm to new attributes. The approach works in 3 stages. The first uses a classical representation learning algorithm to learn a visual representation, SimCLR. Following this, the network is given supervised training to fine-tune the representation. In the last step, the authors adapt a previously devised few-shot learning strategy that consists in training a linear classifier.

summaries: This paper investigates a new and interesting topic, few-shot attribute learning (FSAL), where the model is trained with base attributes with abundant samples and tested with novel attributes with only a few samples. Experiments were performed on three benchmark datasets with attribute annotation. The paper found that self-supervised learning helps to train a backbone that generalizes well to novel attributes, compared to training the backbone with only base attributes. The author also compares several few-shot learning models, e.g., MatchingNEt, MAML, ProtoNet, in this FSAL setting and found that the logistic regression layer works the best.

abstractText: Semantic concepts are frequently defined by combinations of underlying attributes. As mappings from attributes to classes are often simple, attribute-based representations facilitate novel concept learning with zero or few examples. A significant limitation of existing attribute-based learning paradigms, such as zeroshot learning, is that the attributes are assumed to be known and fixed. In this work we study the rapid learning of attributes that were not previously labeled. Compared to standard few-shot learning of semantic classes, in which novel classes may be defined by attributes that were relevant at training time, learning new attributes imposes a stiffer challenge. We found that supervised learning with training attributes does not generalize well to new test attributes, whereas selfsupervised pre-training brings significant improvement. We further experimented with random splits of the attribute space and found that predictability of test attributes provides an informative estimate of a model’s generalization ability.

authors:
Zeynep Akata
Florent Perronnin
Zaı̈d Harchaoui
Cordelia Schmid

title: Label-embedding for attribute-based classification

venue: In IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Zeynep Akata
Scott E. Reed
Daniel Walter
Honglak Lee
Bernt Schiele

title: Evaluation of output embeddings for fine-grained image classification

authors:
Amit Alfassy
Leonid Karlinsky
Amit Aides
Joseph Shtok
Sivan Harary
Rogério Schmidt Feris
Raja Giryes
Alexander M. Bronstein

title: Laso: Label-set operations networks for multi-label few-shot learning

authors:
Ron Amit
Ron Meir

title: Meta-learning by adjusting priors based on extended pac-bayes theory

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
Sébastien M.R. Arnold
Fei Sha

title: Embedding adaptation is still needed for few-shot learning

authors:
Lei Jimmy Ba
Kevin Swersky
Sanja Fidler
Ruslan Salakhutdinov

title: Predicting deep zero-shot convolutional neural networks using textual descriptions

venue: In IEEE International Conference on Computer Vision, ICCV,

title: A model of inductive bias learning

venue: Journal of artificial intelligence research,

authors:
Shai Ben-David
Reba Schuller Borbely

title: A notion of task relatedness yielding provable multipletask learning guarantees

venue: Machine learning,

authors:
Shai Ben-David
John Blitzer
Koby Crammer
Alex Kulesza
Fernando Pereira
Jennifer Wortman Vaughan

title: A theory of learning from different domains

authors:
Ting Chen
Simon Kornblith
Mohammad Norouzi
Geoffrey E. Hinton

title: A simple framework for contrastive learning of visual representations

authors:
Wei-Yu Chen
Yen-Cheng Liu
Zsolt Kira
Yu-Chiang Frank Wang
Jia-Bin Huang

title: A closer look at few-shot classification

venue: In Proceedings of the 7th International Conference on Learning Representations,

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

authors:
Ali Farhadi
Ian Endres
Derek Hoiem
David A. Forsyth

title: Describing objects by their attributes

authors:
Ali Farhadi
Ian Endres
Derek Hoiem

title: Attribute-centric recognition for cross-category generalization

authors:
Li Fei-Fei
Rob Fergus
Pietro Perona

title: One-shot learning of object categories

venue: IEEE TPAMI,

authors:
Vittorio Ferrari
Andrew Zisserman

title: Learning visual attributes

venue: In Advances in Neural Information Processing Systems 20,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In Proceedings of the 34th International Conference on Machine Learning,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Pang Wei Koh
Thao Nguyen
Yew Siang Tang
Stephen Mussmann
Emma Pierson
Been Kim
Percy Liang

title: Concept bottleneck models

venue: In Proceedings of the 37th International Conference on Machine Learning,

authors:
Brenden M. Lake
Ruslan Salakhutdinov
Jason Gross
Joshua B. Tenenbaum

title: One shot learning of simple visual concepts

venue: In Proceedings of the 33th Annual Meeting of the Cognitive Science Society, CogSci,

authors:
Christoph H. Lampert
Hannes Nickisch
Stefan Harmeling

title: Attribute-based classification for zero-shot visual object categorization

venue: IEEE Trans. Pattern Anal. Mach. Intell.,

authors:
Zeqian Li
Michael Mozer
Jacob Whitehill

title: Compositional embeddings for multi-label one-shot learning

venue: In IEEE Winter Conference on Applications of Computer Vision, WACV,

authors:
Ziwei Liu
Ping Luo
Xiaogang Wang
Xiaoou Tang

title: Deep learning face attributes in the wild

venue: In Proceedings of International Conference on Computer Vision, ICCV,

authors:
James Lucas
Mengye Ren
Irene Kameni
Toniann Pitassi
Richard S. Zemel

title: Theoretical bounds on estimation error for meta-learning

authors:
Ishan Misra
Abhinav Gupta
Martial Hebert

title: From red wine to red tomato: Composition with context

authors:
Boris N. Oreshkin
Pau Rodrı́guez López
Alexandre Lacoste

title: TADAM: task dependent adaptive metric for improved few-shot learning

venue: In Advances in Neural Information Processing Systems

authors:
Mark Palatucci
Dean Pomerleau
Geoffrey E. Hinton
Tom M. Mitchell

title: Zero-shot learning with semantic output codes

authors:
Genevieve Patterson
James Hays

title: COCO attributes: Attributes for people, animals, and objects

venue: 14th European Conference Computer Vision, ECCV,

authors:
Anastasia Pentina
Christoph H. Lampert

title: A pac-bayesian bound for lifelong learning

venue: In Proceedings of the 31th International Conference on Machine Learning,

authors:
Khoi Pham
Kushal Kafle
Zhe Lin
Zhihong Ding
Scott Cohen
Quan Tran
Abhinav Shrivastava

title: Learning to predict visual attributes in the wild

authors:
Senthil Purushwalkam
Maximilian Nickel
Abhinav Gupta
Marc’Aurelio Ranzato

title: Task-driven modular networks for zero-shot compositional learning

venue: In IEEE/CVF International Conference on Computer Vision, ICCV,

authors:
Aniruddh Raghu
Maithra Raghu
Samy Bengio
Oriol Vinyals

title: Rapid learning or feature reuse? towards understanding the effectiveness of MAML

venue: In 8th International Conference on Learning Representations,

authors:
Mengye Ren
Eleni Triantafillou
Sachin Ravi
Jake Snell
Kevin Swersky
Joshua B. Tenenbaum
Hugo Larochelle
Richard S. Zemel

title: Meta-learning for semi-supervised few-shot classification

venue: In Proceedings of 6th International Conference on Learning Representations,

authors:
Bernardino Romera-Paredes
Philip H.S. Torr

title: An embarrassingly simple approach to zero-shot learning

venue: In Proceedings of the 32nd International Conference on Machine Learning,

authors:
Eleanor Rosch
Carolyn B Mervis

title: Family resemblances: Studies in the internal structure of categories

venue: Cognitive psychology,

authors:
Mert Bülent Sariyildiz
Yannis Kalantidis
Diane Larlus
Karteek Alahari

title: Concept generalization in visual representation learning

authors:
Jake Snell
Kevin Swersky
Richard S. Zemel

title: Prototypical networks for few-shot learning

title: Lifelong learning algorithms

venue: In Learning to learn,

authors:
Eleni Triantafillou
Tyler Zhu
Vincent Dumoulin
Pascal Lamblin
Kelvin Xu
Ross Goroshin
Carles Gelada
Kevin Swersky
Pierre-Antoine Manzagol
Hugo Larochelle

title: Meta-dataset: A dataset of datasets for learning to learn from few examples

authors:
Gido M Van de Ven
Andreas S Tolias

title: Three scenarios for continual learning

venue: arXiv preprint arXiv:1904.07734,

authors:
Oriol Vinyals
Charles Blundell
Tim Lillicrap
Koray Kavukcuoglu
Daan Wierstra

title: Matching networks for one shot learning

authors:
Wei Wang
Vincent W Zheng
Han Yu
Chunyan Miao

title: A survey of zero-shot learning: Settings, methods, and applications

venue: ACM Transactions on Intelligent Systems and Technology, TIST,

authors:
Xin Wang
Fisher Yu
Trevor Darrell
Joseph E. Gonzalez

title: Task-aware feature generation for zero-shot compositional learning

authors:
Xin Wang
Fisher Yu
Ruth Wang
Trevor Darrell
Joseph E. Gonzalez

title: Tafe-net: Task-aware feature embeddings for low shot learning

authors:
Yang Wang
Greg Mori

title: A discriminative latent model of object classes and attributes

venue: In 11th European Conference on Computer Vision, ECCV,

authors:
Peter Welinder
Steve Branson
Takeshi Mita
Catherine Wah
Florian Schroff
Serge Belongie
Pietro Perona

title: Caltech-ucsd birds

authors:
Yongqin Xian
Christoph H. Lampert
Bernt Schiele
Zeynep Akata

title: Zero-shot learning - A comprehensive evaluation of the good, the bad and the ugly

authors:
Liuyu Xiang
Xiaoming Jin
Guiguang Ding
Jungong Han
Leida Li

title: Incremental few-shot learning for pedestrian attribute recognition

venue: In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence,

authors:
Muli Yang
Cheng Deng
Junchi Yan
Xianglong Liu
Dacheng Tao

title: Learning unseen concepts via hierarchical decomposition and composition

venue: In IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Aron Yu
Kristen Grauman

title: Fine-grained visual comparisons with local learning

authors:
Bolei Zhou
Aditya Khosla
Àgata Lapedriza
Aude Oliva
Antonio Torralba

title: Learning deep features for discriminative localization

heading: 1 INTRODUCTION

text:
Formation of class concepts is one of the most fundamental processes in machine perception. Although class concepts are often defined based on their attribute information, e.g., birds are warmblooded vertebrates that lay eggs and have feathers, attributes are rarely considered in a typical machine perception system that directly maps from input signals to output classes. Humans also leverage similarity in the attribute space to recognize classes, which are “information-rich bundles of attributes that form natural discontinuities” (Rosch & Mervis, 1975). The acquisition of attribute knowledge therefore helps us build a more compact and efficient representation that is useful for the perception of classes.
Another distinct advantage of using attribute information is that it facilitates learning new classes with few or even zero examples, which has been leveraged in studies of zero-shot learning (ZSL) (Palatucci et al., 2009; Lampert et al., 2014; Misra et al., 2017). Other models use attributes as direct outputs before the classes for improved modularity and interpretability (Farhadi et al., 2009; Koh et al., 2020). However, all of these attribute-based models rely on a pre-defined set of attributes, that are shared among all classes. Consider a learning agent deployed in the wild. Although the agent may learn new classes by composing some of the existing attributes, its learning capability would be greatly improved if it can expand its attribute vocabulary.
Motivated by this learning scenario, we are interested in the problem of learning new attributes that are previously not labeled in the dataset. This is a step towards continual learning (Van de Ven & Tolias, 2019), where the reward function evolves and the system must adapt if the reward becomes dependent on previously irrelevant input attributes. In particular, we focus on a few-shot learning (FSL) setup (Lake et al., 2011; Vinyals et al., 2016), where only a few positive and negative examples of the target attributes are available, to model the rapid adaptation task.
Considering few-shot attribute learning has an extra benefit, in that it can provide manipulable factors to study generalization. In standard few-shot learning, object semantic classes are split into training and test; however, there is still a lack of understanding of when models transfer their knowledge from training classes to test ones. Since semantic classes can often be defined with a set of attributes, a split in the attribute space therefore provides us a finer control on the degree to which training classes are related to test ones. By studying the transfer performance on novel attributes, we expect our work can generate insight into the generalization performance on semantic classes in standard few-shot learning.
To study this challenging task of few-shot attribute learning (FSAL), we contribute new benchmark datasets consisting of images of faces (Celeb-A) (Liu et al., 2015), shoes (Zappos50K) (Yu & Grauman, 2014), and general objects (ImageNet-with-Attributes) (Deng et al., 2009). Unlike in standard few-shot learning where supervised pre-training generally helps learning, surprisingly we found that directly supervising the model with a set of training attributes does not generalize well on the test attributes, whereas self-supervised pre-training brings significant improvement. We further ran experiments with random splits of the attribute space and discovered that the predictability of attributes provides an informative estimate of a model’s ability to generalize. The few-shot attribute learning paradigm proposed in this paper will facilitate more efficient and flexible continual learning and shed a light on the practical understanding on generalization of novel concepts.

heading: 2 FEW-SHOT ATTRIBUTE LEARNING

text:
In this section, we define our few-shot attribute learning (FSAL) paradigm and highlight the additional challenges of FSAL compared to the standard few-shot learning of semantic classes.
Similar to standard few-shot learning, at test time, the learner is presented with an episode of data. The support set consists of N positive and negative examples of the target attributes
S = {(xS+1 , 1), . . . , (x S+ N , 1), (x S− 1 , 0), . . . , (x S− N , 0)}, (1)
where the + or − superscript suffix denotes whether the input is a positive or negative example. After rapid learning on the support set, the model is then evaluated on the binary classification performance of the query set:
Q = {(xQ+1 , 1), . . . , (x Q+ M , 1), (x Q− 1 , 0), . . . , (x Q− M , 0)}. (2)
At test time, the target binary label may concern a novel attribute that was previously unlabeled in the training set. For example, in one test episode, a smiling face with eyeglasses is positively labeled alongside other faces with eyeglasses. The task here is to learn the attribute of “wearing eyeglasses”. However, while the learner might have seen training images with eyeglasses, it was never a relevant feature for the purpose of predicting the positively labeled instances.
Furthermore, suppose that in another test episode, the same smiling face is positively labeled alongside other smiling faces. The target attribute here has now changed from “wearing eyeglasses” to “smiling.” This highlights a critical difference between few-shot attribute learning and standard few-shot learning of semantic classes: in standard FSL, each instance can belong to only one class regardless of the episode. In FSAL, due to the multi-label nature of the attribute space, one instance could have different labels depending on the context of the support set examples. Furthermore, there may be a large amount of ambiguity when the support set is small. Figure 1 shows a few examples of our attribute learning episodes. Note that in order to create task diversity, we allow both unary and binary attributes, where binary attributes are conjunctions of two unary attributes.
In order to solve the FSAL task, the learner must correctly determine the context. Just like in zero-shot learning, one natural way to solve this problem would be to learn to predict the underlying attributes of each image. Given the attributes, you could then estimate the context in each episode (Lampert et al., 2014). However, methods that accurately predict attributes relevant to training episodes may not generalize well, since at test time FSAL introduces novel attributes. Instead, we explore methods that allow more general representations to be learned.

heading: 3 METHODOLOGY

text:
In this section, we present our proposed approach to tackle the problem of few-shot attribute learning. Two classes of approaches are frequently considered in standard few-shot learning. First,
episodic approaches train methods directly from a set of few-shot episodes. This class of methods can be naturally applied to our learning setting. Second, pre-training approaches train a network to directly classify a set of training classes, and at test time, the embedding network is transferred to solve the test task by training another classifier on top. If absolute attribute IDs are provided to the learner, then one natural approach is to instead train an attribute classifier. After the attribute classifier network is learned, we can then transfer the representations to recognize test attributes.
We explored both of these approaches in our experiments, but we found that they tend to learn good representations only for the training attributes but not for test ones. To address the generalization issues of these standard approaches, we propose a new algorithm that preserves more general features.
Our proposed method follows the pre-training paradigm and contains three stages. The first stage is pre-training the representation network using an unsupervised (contrastive) learning objective. The second stage is fine-tuning using supervision based either on attribute or episode information. Lastly, we learn a sparse linear classifier at test-time to solve a new episode. We describe each stage of learning below.

heading: 3.1 STAGE I: UNSUPERVISED REPRESENTATION PRE-TRAINING

text:
Our proposed few-shot attribute learning tasks require a strongly generalizable learner. We hypothesized that learning general-purpose features that capture varying aspects of objects would be helpful to enable this desired capability. We therefore considered unsupervised representation learning, and we hypothesize that it can learn general semantic features. We chose SimCLR (Chen et al., 2020) as a representative from this category due to its empirical success. In general, contrastive learning approaches aim to build invariant representations between a pair of inputs {x,x′} that are produced by applying random data augmentations (e.g. cropping) to an input image. It is likely to preserve more general semantic features since all image attributes are useful towards identifying another random crop of the same image.
We first obtain the embedding output h from the CNN, and then following SimCLR, we project h to z using a multi-layered perceptron (MLP): h = CNN(x), z = MLP1(h). With a batch of image pairs denoted by {xi}, {x′i}, we can obtain their features {zi}, {z′i}, and the contrastive loss function is defined similar to the cross entropy function:
L1 = − ∑ i log exp(zi · z′i/τ)∑ j exp(zi · z′j/τ) , (3)
where τ is an extra temperature hyperparameter.

heading: 3.2 STAGE II: REPRESENTATION FINE-TUNING

text:
In the second stage, we aim to utilize some labels from the training set to supervise the network. We consider using two different modes of supervision: 1) the FSAL binary episodic labels, or 2) the underlying binary attribute IDs. To prevent overwriting the representations and making them overly sensitive to training attributes, we add another projection MLP that learns more specific representations for finetuning on training attributes: g = MLP2(h). The fine-tuning objectives we consider are as follows.
• Unsupervised-then-FineTune-on-Episodes (UFTE). We adopt the Prototypical Networks (Snell et al., 2017) formulation, where the network solves a learning episode of N positive and negative support examples by using prototypes p: p+ = 1N ∑ i g + i ;p − = 1N ∑ i g − i . With query example
gq , we can make a binary prediction:
ŷq = exp(−d(gq,p+))
exp(−d(gq,p+)) + exp(−d(gq,p−)) , (4)
where d is some dissimilarity score, e.g. Euclidean distance or cosine dissimilarity, and the training objective is to minimize the classification loss between the prediction ŷq and the label yq:
L2E = ∑ j −yj log ŷqj − (1− y q j ) log(1− ŷ q j ), (5)
where j is the index of query examples.
• Unsupervised-then-FineTune-on-Attributes (UFTA). With persistent attribute information, we can train a linear classifier with sigmoid activation to directly predict the absolute attribute labels a: â =WAg + bA, with the loss being
L2A = ∑ k −ak log âk − (1− ak) log(1− âk), (6)
where k is the index of attributes.

heading: 3.3 STAGE III: FEW-SHOT LEARNING

text:
Once representations are learned, it remains to be decided how to use the small support set of each given test episode in order to make predictions for the associated query set. We consider three alternative approaches. MatchingNet (Vinyals et al., 2016) uses a nearest neighbor (NN) classifier, whereas ProtoNet (Snell et al., 2017) uses the nearest centroid (NC). Following Chen et al. (2019), we propose to directly learn a logistic regression (LR) on top of the representation. This approach learns a weight coefficient for each feature dimension, thus performing some level of feature selection, unlike the NC or NN variants. Still, the weights need to be properly regularized to encourage high-fidelity selection. This is important since each episode only focuses on a new classification criteria using a subset of features. For this, we apply an L1 regularizer on the weights to encourage sparsity. In this way, the learning of a classifier is essentially done at the same time as the selection of feature dimensions. The overall objective of the classifier is:
argmin w,b
−y log(ŷ)− (1− y) log(1− ŷ) + λ‖w‖1, (7)
where ŷ = σ(w>h+ b), and h is the representation vector extracted from the CNN backbone. Note that in this stage we discard the projection MLPs that are defined in previous stages since they are trained towards training attributes and we found that they do not transfer well to novel attributes.

heading: 4 RELATED WORK

text:
Few-shot learning: Few-shot learning (FSL) (Fei-Fei et al., 2006; Lake et al., 2011; Vinyals et al., 2016) entails learning new tasks with only a few examples. With an abundance of training data, FSL is closely related to the general meta-learning or learning to learn paradigm (Thrun, 1998), as a few-shot learning algorithm can be developed on training tasks and run on novel tasks at test time. In standard few-shot classification, each image only has a single unambiguous class label, whereas in our few-shot attribute learning, the target attributes can vary depending on how the support set is presented. We show in this paper that this is a more challenging problem as it requires the model to be more flexible and generalizable. In early benchmarks, a set of semantic classes was randomly split into a training and test set. We hypothesize that this often leads to a common set of attributes that span (most of) the training and test classes, thus causing high transferability between these two sets, which allows simple solutions based on feature re-use (Chen et al., 2019; Raghu et al., 2020) to work well. Later benchmarks explicitly attempt to vary the separation between train and test classes, based on varying the distances in the underlying WordNet classes (tiered-ImageNet (Ren et al., 2018)), or in different image domains (Meta-Dataset (Triantafillou et al., 2020)). However, we argue that reasoning about the underlying attributes directly offers a more systematic framework to measure the relatedness and transferability between the train and test set. We expect our analysis to open the door to such studies in the future. Few-shot attribute learning is also related to multilabel few-shot learning (Alfassy et al., 2019; Li et al., 2021). These prior works emphasize on the compositional aspect, whereas we propose models that address the transferability of the learned representations. Additionally, Xiang et al. (2019) explored combining incremental few-shot learning and attribute learning for pedestrian images.
Attribute learning: In the past, there have been a number of works that aim to predict attribute information from raw inputs Ferrari & Zisserman (2007); Farhadi et al. (2009; 2010); Wang &
Mori (2010). A related model is later proposed by Koh et al. (2020) to achieve better causal interpretability. There have also been a number of datasets that have been collected with visual attributes annotated (Liu et al., 2015; Yu & Grauman, 2014; Welinder et al., 2010; Patterson & Hays, 2016; Pham et al., 2021). One key difference between our work and these attribute learning approaches is that at test time we aim to learn a classifier on novel attributes that are previously not labeled in the training set, and this brings additional challenges of transfer learning and learning with limited labeled data.
Zero-shot learning: In zero-shot learning (ZSL) (Farhadi et al., 2009; Akata et al., 2013; Xian et al., 2019; Lampert et al., 2014; Romera-Paredes & Torr, 2015; Akata et al., 2015), a model is asked to recognize classes not present in the training set, supervised only by some auxiliary description (Ba et al., 2015) or attribute values (Farhadi et al., 2009) (see Wang et al. (2019a) for a survey). Lampert et al. (2014) studied the direct attribute prediction method, similar to the Supervised Attribute baseline described in Section 5.2. Compositional ZSL aims at learning classes (Misra et al., 2017; Purushwalkam et al., 2019; Wang et al., 2019b; Yang et al., 2020) defined by a novel composition of labeled attributes and object classes. An important distinction between ZSL and our few-shot attribute learning task is that ZSL uses the same set of attributes for both training and testing; by contrast, our task asks the model to learn attributes for which there are no labels during training, and they may not be relevant to any of the training attributes or episodes. We summarize the relationships between ZSL, FSL and our task in Table 1.
Generalization to novel tasks: One key component of our work is an attempt to understand the generalization behavior of learning novel concepts at test time. Relevant theoretical studies consider novel task generalization, casting it in a transfer learning and learning to learn framework (Baxter, 2000; Ben-David & Borbely, 2008; Ben-David et al., 2010; Pentina & Lampert, 2014; Amit & Meir, 2018; Lucas et al., 2021). A common theme in these studies is in characterizing task relatedness, and the role that it plays in generalization to novel tasks. Arnold & Sha (2021) studied task clustering for few-shot learning in the embedding space and found class splits that are of different difficulty levels. Sariyildiz et al. (2021) use the WordNet hierarchy to compute semantic distances. In our paper, we instead split the data in the attribute space, and if we assume that semantic classes are combinations of attributes, then a disjoint attribute split will imply further semantic distances. In our work, we investigate the role of task relatedness empirically by investigating generalization performance under different splits of the attribute space.

heading: 5 EXPERIMENTS

text: In this section, we evaluate our proposed UFTE and UFTA approaches on several FSAL tasks.

heading: 5.1 DATASETS

text:
We consider the following three datasets: • Celeb-A (Liu et al., 2015) contains over 200K images of celebrities’ faces. Each image is anno-
tated with binary attributes, detailing hair color, facial expressions, and other descriptors. We split 14 attributes for training and 13 for test.
• Zappos-50K (Yu & Grauman, 2014) contains just under 50K images of shoes annotated with attribute values. We split these into 40 attribute values for training, and 39 for testing. • ImageNet-with-Attributes is a small subset of the ImageNet dataset (Deng et al., 2009) with attribute annotations. It has 9.6K images. We used 11 attributes for training and 10 for testing.
In all of the datasets above, there is no overlap between training and test attributes. Additional split details can be found in the supplementary materials.
Episode construction: For each episode, we randomly select one or two attributes and look for positive examples belonging to these attributes simultaneously. We also sample an equal number of negative examples that don’t match the selected attributes. This will construct a support set of positive and negative samples, and then we repeat the same process for the corresponding query set as well. Sample episodes are shown in Figure 1.

heading: 5.2 METHODS FOR COMPARISON

text:
We first consider a set of classic few-shot learning methods for comparison. These methods are directly trained on FSAL episodes of training attributes.
• MatchingNet (Vinyals et al., 2016) is a soft version of 1-nearest-neighbor. At test time, it will retrieve the label of the support example that is the closest in the feature space. • MAML (Finn et al., 2017) performs several gradient descent steps in an episode and learns the parameter initialization. For simplicity, we used the ANIL variant (Raghu et al., 2020) that only learns the last layer in the inner loop. • ProtoNet (Snell et al., 2017) computes an average “prototype” for each class and retrieves the closest one. • TAFENet (Wang et al., 2019c) learns a meta-network that can output task-conditioned classifier parameters. • TADAM (Oreshkin et al., 2018) predicts the batch normalization parameters by using the average features of the episode. For our task we found that conditioning on the positive examples only works the best.
In addition to the approaches above, we consider the following representation learning baselines for comparison.
• ID trains a network to perform the auxiliary task of face identity classification (Celeb-A only). • SA, or supervised attribute, resembles the “Baseline” approach in the FSL literature (Chen et al.,
2019). The network learns representations by predicting the training attributes associated with each image. • U denotes unsupervised representation learning (SimCLR). We train separate models on the Celeb-A and Zappos datasets. For ImageNet, we utilize the off-the-shelf model checkpoint trained on the full ImageNet-1K. Compared to our approach, this baseline skips the finetuning stage (Stage II).
We also provide two oracle approaches to study the upper bound to generalization to novel attributes.
• Oracle SA* learns its representations by predicting all binary attributes including both training and test ones.
• Oracle GT directly uses the ground-truth binary attribute values as input features, and the readout is performed by training a logistic regression. It still needs to select the active attributes that are used in each episode.
For representation learning baselines, we mainly use logistic regression (LR) in few-shot episodes, but we also report results using the nearest neighbor (NN) and nearest centroid (NC) classifiers.
Implementation details: For Celeb-A and Zappos, images were cropped and resized to 84×84. We used ResNet-12 (He et al., 2016; Oreshkin et al., 2018) as the CNN backbone. The projection MLPs have 512-512-128 units. We train SimCLR entirely on Celeb-A/Zappos images, i.e. not using pre-trained ImageNet checkpoints for fair comparison. For ImageNet-with-Attributes, we utilize the off-the-self SimCLR model from ImageNet-1k, which has access to more unlabeled images. The image dimensions are 224×224. We include additional experimental details in the Appendix.

heading: 5.3 MAIN RESULTS

text:
Table 2 shows our main results on Celeb-A and Zappos-50K with 5- and 20-shot episodes. Table 3 explores different combinations of representations and few-shot learners. Overall, the standard episodic meta-learners performed relatively poorly. Also, supervised attribute (SA) learning and learning via the auxiliary task of class facial identification (ID) were not helpful for representation learning either. Interestingly, U attained relatively better test performance, suggesting that the training objective in contrastive learning indeed preserves more general features—not just for semantic classification tasks as shown in prior work, but also for the flexibly-defined attribute classes in our FSAL paradigm.
Our proposed UFTA and UFTE approaches obtained significant gains in performance, suggesting that a combination of unsupervised features with some supervised information is indeed beneficial for this task. Lastly, our methods are able to reduce the generalization gap between SA and the oracle SA*, in fact almost closing it entirely on Zappos-50K.
Results on ImageNet-with-Attributes are reported separately for clarity, because U, UFTE, and UFTA had access to additional unlabeled examples. As shown in Table 6, both UFTE and UFTA outperformed other methods substantially. Because of the additional unlabeled data available in this setting, even U achieved a substantially better accuracy than SA and MAML. Results in Table 7 show that UFTE and UFTA work well when combined with different few-shot learners.
Visualizing few-shot classifiers: To understand and interpret the decision made by few-shot linear classifiers, we visualize the classifier weights by using CAM (Zhou et al., 2016), and plot the heatmap over the 11×11 spatial feature map in Figure 2. SA sometimes shows incorrect localization as it is not trained to classify those novel test attributes. SA* shows bigger but less precise heatmaps since the training objective encourages the propagation of attribute information spatially. In contrast, our proposed method produces surprisingly accurate and localized heatmaps that pinpoint the location of the attributes (e.g. mustache or cheekbone); this is impressive since no labeled information concerning these attributes was available during representation learning. This result supports the hypothesis that local features can be good descriptors that match different views of the same instance during contrastive learning, and finetuning further establishes a positive transfer between training and test attributes.
Number of shots and task ambiguity: Since we have a flexible target attribute class in each episode, it could be the case that the support examples are ambiguous. For example, by presenting only a smiling face with eyeglasses in the support set, it is unclear whether the positive set is determined by “smiling” or “wearing eyeglasses”. Figure 3a show several approaches evaluated using LR with varying numbers of support examples per class in Celeb-A and Zappos-50K episodes, respectively. The oracle GT gradually approached 100% accuracy as the number of shots approached 20. This demonstrates that FSAL tasks potentially require more support examples than standard FSL to resolve ambiguity. Again here, UFTA and UFTE consistently outperformed U, SA, and ID baselines across different number of shots. Figure 3b shows the correlation between readout performance of attributes and few-shot learning accuracy, using UFTA. With a larger number of shots, there is a higher correlation between the two, but there is still a large amount of variance that is due to the ambiguity of the task itself. More details are included in the Appendix.
Ablation studies: Table 5 studies the effect of the projection MLP for attribute classification finetuning. Adding MLP projection layers was found to be beneficial for unsupervised learning in prior work (Chen et al., 2020). Here we found that adding MLP layers is also critical in our representation finetuning stage as well. Finetuning directly on the backbone (depth=0), and keeping the MLP during test (Discard=no) both led to significant drop in performance. In the Appendix, we also report on studies of the effect of adding the L1 regularizer on LR.

heading: 5.4 ANALYSIS ON FEW-SHOT GENERALIZATION

text:
In Tables 4 and 8, we study the performance gap between training attributes and test attributes. Notably, SA performs very well on test episodes defined using training attributes, but there is a large generalization gap between training and test attributes. Our methods show significant improvements in terms of reducing the generalization gap between training and test attributes. Moreover, we find that self-supervised pre-training generally preserves informative features and is more general than supervised pre-training.
Investigating the cause of generalization issues: We hypothesize that the weak performance of episodic learners and SA on our benchmarks is because their training objectives essentially encourage ignoring attributes that are not useful at training time, but may still be useful at test time. In Appendix G, we study a synthetic problem to further analyze these generalization issues. We explore training a ProtoNet model on data from a linear generative model, where each FSAL episode presents ambiguity in identifying the relevant attributes. In this setting, the network is forced to discard information that is useful for test tasks in order to solve the training tasks effectively, and thus fails to generalize.
Transferability score: Up to this point, we have only studied one particular split of training/test attributes. We would like to examine whether our conclusions generalize over different splits. More
importantly, we aim to predict the transferability between training and test splits by analyzing the training vs. test attributes. Each image has a complete attribute vector, describing the values of each attribute in the image. Some of these attributes are in the training set, and others in the test set. To quantify the transferability, we leverage the idea of mutual information. More concretely, we learn a logistic regression model that takes the training attribute vector in a particular image as input and predicts the value of one of the test attributes in that image. Each logistic regression model will generate an AUC score on held-out images, and we average them across the relevant test attributes in each episode, and we define this AUC score as the “transferability score.” Our hypothesis is that more mutual information between the attribute label distributions will translate to higher transfer performance when the model is supervised on the training attributes and tested on the test attributes.
In Figure 4, we ran experiments using 100 random splits of training and test attributes. The results verify our hypothesis. We see positive correlation between the transfer performance and our transferability score: When subtracting U as a baseline, both UFTA and UFTE models get better when there is higher transferability (subtraction reduces the effect of per-episode variability). The same conclusion can be drawn when we subtract SA* from SA. By plotting the relation between U and SA, we show that supervised learning is more helpful when there is higher transferability in the label space whereas self-supervised learning is more flexible at adapting to novel target tasks.

heading: 6 CONCLUSION

text: Acquiring knowledge of new attributes is one of the most basic learning skills of an intelligent agent. In this paper, we propose few-shot attribute learning to enable this core functionality. We developed benchmarks using the Celeb-A, Zappos-50K, and ImageNet datasets to create learning episodes using existing attribute labels. This setting presents a strong generalization challenge, since the split in attribute space can make the training and test tasks less similar. Consequently standard supervised representation learning performs poorly on the test set, unlike recent benchmark results in few-shot learning of semantic classes. We found that unsupervised contrastive learning preserved more general features, and further finetuning yielded strong performance. We also discovered that the similarity in the attribute label space can roughly predict the gain obtained by supervised training and finetuning, which could provide some insight into the generalization behavior of representation learning algorithms when dealing with novel tasks at test time.

heading: A ATTRIBUTE READOUT

text: In Tab. 9 and 11, we provide attribute readout performance with different learned representations. This is a similar task that measures the generalizability, but it does not evaluate the rapid learning aspect brought by few-shot learning.

heading: B ABLATION STUDIES

text: Table 10 studies the effect of the L1 regularization. The benefit is especially noticeable on SA* and GT, since it allows the few-shot learner to have a sparse selection of disentangled feature dimensions.

heading: C ADDITIONAL HEATMAP VISUALIZATION

text: We provide additional visualization results in Figure 5, 6, and 7, and we plot the heat map to visualize the LR classifier weights. Figure 5 includes SA*, U, and UFTE which are omitted in the main paper due to space limitations. Figure 6 and 7 visualize more information including both support and query examples in the episode, and some of the episodes are challenging to solve given just a few examples.

heading: D ATTRIBUTE SPLITS OF CELEB-A

text: We include the attribute split for Celeb-A in Table 12. There are 14 attributes in training and 13 attributes in val/test. We discarded the rest of the 13 attributes in the original datasets since they are either hard to classify with the oracle classifier (e.g. big lips, oval face) or simply ambiguous (e.g. young, attractive).

heading: E ATTRIBUTE SPLITS OF ZAPPOS-50K

text:
The Zappos-50K dataset annotates images with different values relating to the following aspects of shoes: ‘Category’, ‘Subcategory’, ‘HeelHeight’, ‘Insole’, ‘Closure’, ‘Gender’, ‘Material’ and ‘Toestyle’.
We discarded the ‘Insole’ values, since those refer to the inside part of the shoe which isn’t visible in the images. We also discarded some ‘Material’ values that we deemed hard to recognize visually. We also modified the values of ‘HeelHeight’ which originally was different ranges of cm of the height of the heel of each shoe. Instead, we divided those values into only two groups: ‘short heel’ and ‘high heel’, to avoid having to perform very fine-grained heel height recognition which we deemed was too difficult.
These modifications leave us with a total of 79 values (across all higher-level categories). Not all images are tagged with a value from each category, while some are even tagged with more than one value from the same category (e.g. two different materials used in different parts of the shoe). We split these values into 40 ‘training attributes’ and 39 ‘val/test attributes’.
We include the complete list of attributes in Table 13. The format we use is ‘X-Y’ where X stands for the category (e.g. ‘Material’) and Y stands for the value of that category (e.g. ‘Wool’). We do this to avoid ambiguity, since it may happen that different categories have some value names in common, e.g. ‘Short Heel’ is a value of both ‘SubCategory’ and ‘HeelHeight’.

heading: F ATTRIBUTE SPLITS OF IMAGENET-WITH-ATTRIBUTES

text: We include the attribute split for ImageNet-with-Attributes in Table 14. There are 11 attributes in training and 10 attributes in val/test. We discarded the rest of the 4 attributes in the “shape” category (long, round, rectangular and square), since they are difficult to predict from the images.

heading: G FEW-SHOT ATTRIBUTE LEARNING TOY PROBLEM

text:
In this section, we present a toy problem that illustrates the challenges introduced by the FSAL setting and the failures of existing approaches on this task. This simple problem captures the core elements of our FSAL tasks, including ambiguity, introducing novel attributes at test time, and the role of learning good representations. The primary limitation of this model is the fact that it is fully linear and the attribute values are independent—in a more realistic FSAL task recovering a good representation from the data is significantly more challenging, and the data points will have a more complex relationship with the attributes as in our benchmark datasets.
Problem setup We define a FSAL problem where the data points x ∈ Rm are generated from binary attribute strings, z ∈ {0, 1}d, with x = Az+ ζ for some matrix A ∈ Rm×d with full column rank and noise source ζ. Thus, each data point x is a sum of columns ofA with some additive noise.
In each episode, examples are labelled as positive when two designated entries of the attribute strings are both 1-valued, and negative otherwise. For the training episodes, the labels depend only on the first d1 < d entries of z. At test time, the labels depend on the remaining d − d1 attributes. The training and test episodes are generated by choosing two of the attributes in the respective sets. Then k data points are sampled with positive labels (the two attributes are 1-valued) and k with negative labels (at least one of the attributes is 0-valued).
Linear prototypical network Now, consider training a prototypical network on this data with a linear embedding network, g(x) = Wx. Within each episode, the prototypical network computes the prototypes for the positive and negative examples,
cj = 1
k ∑ xi∈Sj g(xi) = 1 k ∑ xi∈Sj d∑ l=1 zilWal, for j ∈ {0, 1},
where Sj is the set of data points in the episode with label j, and al is the lth column of the matrix A. Further, the prototypical network likelihood is given by,
p(y = 0|x) = exp
{ −‖Wx− c0‖22 } exp {−‖Wx− c0‖22}+ exp {−‖Wx− c1‖22} .
The goal of the prototypical network is thus to learn weights W that lead to small distances between data points in the same class and large distances otherwise. In the FSAL tasks, there is an addi-
tional challenge in that class boundaries shift between episodes. The context (the choice of attribute entries) defining the boundary is unknown and must be inferred from the episode. However, with few shots (small k) there is ambiguity in the correct context — with a high probability that several possible contexts provide valid explanations for the observed data.
Fitting the prototypical network Notice that under our generative model, with x =Wz+ ζ and for j ∈ {0, 1} we have,
Wx− cj =WA(z− 1
k ∑ zi∈Sj zi) + 1 k ∑ i Wζi +Wζ.
Notice that if vj(z) = A(z− 1k ∑
zi∈Sj zi) ∈ Ker(W ), the kernel of W , then the entire first term is zero. Further, if z ∈ Sj (the same class as the prototype) then there is no contribution from the positive attribute features in this term. Otherwise, this term is guaranteed to have some contribution from the positive attribute features.
Therefore, if W projects to the linear space spanned by the positive attribute features then Wvj(z) is zero when z ∈ Sj and non-zero otherwise. This means that the model will be able to solve the episode without contextual ambiguity. Then the optimal weights are those that project to the set of features used in the training set—destroying all information about the test attributes which would otherwise introduce ambiguity.
We observed this effect empirically in Figure 8, where we have plotted the matrix abs(WA). Each column of these plots represents a column of A mapped to the prototypical network’s embedding space. The first 5 columns correspond to attributes used at training time, and the remaining 5 to those used at test time.
In the FSAL task described above, as our analysis suggests, the learned prototypical feature weights project out the features used at test time (the last 5 columns). As a result, the model achieved 100% training accuracy but only 51% test accuracy (chance is 50%).
We also compared against an equivalent problem set up that resembles the standard few-shot learning setting. In the FSL problem, the binary attribute strings may have only a single non-zero entry and each episode is a binary classification problem where the learner must distinguish between two classes. Now the vector z is a one-hot encoding and the comparison to the prototypes occurs only over a single feature column of A, thus there is no benefit to projecting out the test features. As
expected, the model we learned (Figure 8 B) is not forced to throw away test-time information and achieves 100% training accuracy and 99% test accuracy.
Settings for Figure 8 We use 10 attributes, 5 of which are used for training and 5 for testing. We use a uniformly random sampled A ∈ R30×10 and the prototypical network learns W ∈ R10×30. We use additive Gaussian noise when sampling data points with a standard deviation of 0.1. The models are trained with the Adam optimizer using default settings over a total of 30000 random episodes, and evaluated on an additional 1000 test episodes. We used k = 20 to produce these plots, but found that the result was consistent over different shot counts.


summaries: The paper suggests a method for approximating the 2-Wasserstein gradient flow for the relative entropy. The proposed particle-based method uses a neural network function approximation-based approach to estimating the necessary density ratios. Experiments verify reasonable performance compared to MALA and ULA.

summaries: This paper considers the problem of sampling from an unnormalized distribution. The unnormalized target distribution can be regarded as a stationary point of the Wasserstein gradient flow of the corresponding relative entropy functional, which can be equivalently identified from a microscopic perspective by defining a time-varying velocity field of the particles. While the exact time-varying velocity field is not exactly available, the authors propose to estimate such a quantity by approximating the corresponding logarithmic density ratio through minimizing the Bregman score. Such an approximation requires only samples from the variable distribution which can obtain by simulating particles following the estimated velocity field.

summaries: The paper proposes a novel way to sample from unnormalized distributions. This is helpful when calculating or estimating the normalizing constant is untractable.  The main idea is to track the gradient flow of the relative entropy in the Wasserstein space of probability distributions. It is known that the flow converges to the target distribution and the paper introduces a variational characterization of the discretized steps. The main benefit of this characterization is that it bypasses the need to know the normalizing constant as well as being amenable to estimation by using a combined particle evolution.  The benefits of the new algorithm are demonstrated through several numerical simulations.

summaries: The paper addresses the issue of sampling from an unnormalized distribution. The sampling problem is cast as the numerical simulation of the gradient flow associated with the KL divergence between the target unnormalized distribution and the approximating distribution. The challenging part is to estimate the density ratio that appears in the gradient term. The authors propose to use a deep neural network to estimate the density ratio. Numerical results show the usefulness of the proposed method.

abstractText: We propose a relative entropy gradient sampler (REGS) for sampling from unnormalized distributions. REGS is a particle method that seeks a sequence of simple nonlinear transforms iteratively pushing the initial samples from a reference distribution into the samples from an unnormalized target distribution. To determine the nonlinear transforms at each iteration, we consider the Wasserstein gradient flow of relative entropy. This gradient flow determines a path of probability distributions that interpolates the reference distribution and the target distribution. It is characterized by an ODE system with velocity fields depending on the density ratios of the density of evolving particles and the unnormalized target density. To sample with REGS, we need to estimate the density ratios and simulate the ODE system with particle evolution. We propose a novel nonparametric approach to estimating the logarithmic density ratio using neural networks. Extensive simulation studies on challenging multimodal 1D and 2D mixture distributions and Bayesian logistic regression on real datasets demonstrate that the REGS outperforms the state-of-the-art sampling methods included in the comparison.

authors:
Luigi Ambrosio
Nicola Gigli
Giuseppe Savaré

title: Gradient Flows: in Metric Spaces and in the Space of Probability Measures

venue: Springer Science & Business Media,

authors:
Christophe Andrieu
Nando de Freitas
Arnaud Doucet
Michael I. Jordan

title: An introduction to MCMC for machine learning

venue: Machine Learning,

title: Variational Algorithms for Approximate Bayesian Inference

venue: PhD thesis,

authors:
David M. Blei
Alp Kucukelbir
Jon D. McAuliffe

title: Variational inference: A review for statisticians

venue: Journal of the American Statistical Association,

authors:
Steve Brooks
Andrew Gelman
Galin L. Jones
Xiao-Li Meng

title: Handbook of Markov Chain Monte Carlo

authors:
Changyou Chen
Ruiyi Zhang
Wenlin Wang
Bai Li
Liqun Chen

title: A unified particle-optimization framework for scalable bayesian sampling

authors:
Tianqi Chen
Emily Fox
Carlos Guestrin

title: Stochastic gradient Hamiltonian Monte Carlo

venue: Proceedings of the 31st International Conference on Machine Learning,

title: The geometry of proper scoring rules

venue: Annals of the Institute of Statistical Mathematics,

authors:
Simon Duane
A.D. Kennedy
Brian J. Pendleton
Duncan Roweth

title: Hybrid Monte Carlo

venue: Physics Letters B,

authors:
Andrew Duncan
Nikolas Nüsken
Lukasz Szpruch

title: On the geometry of Stein variational gradient descent

venue: arXiv preprint arXiv:1912.00894,

authors:
Yuan Gao
Yuling Jiao
Yang Wang
Yao Wang
Can Yang
Shunkang Zhang

title: Deep generative learning via variational gradient flow

venue: Proceedings of the 36th International Conference on Machine Learning,

authors:
Yuan Gao
Jian Huang
Yuling Jiao
Jin Liu
Xiliang Lu
Zhijian Yang

title: Deep generative learning with Euler particle transport

venue: In Proceedings of Machine Learning Research

authors:
S. Gershman
M. Hoffman
D. Blei

title: Nonparametric variational inference

authors:
Tilmann Gneiting
Adrian E Raftery

title: Strictly proper scoring rules, prediction, and estimation

venue: Journal of the American statistical Association,

title: Monte Carlo sampling methods using Markov chains and their applications

authors:
Matthew D. Hoffman
Andrew Gelman

title: The No-U-Turn Sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo

venue: Journal of Machine Learning Research,

authors:
Richard Jordan
David Kinderlehrer
Felix Otto

title: The variational formulation of the Fokker–Planck equation

venue: SIAM Journal on Mathematical Analysis,

authors:
Takafumi Kanamori
Masashi Sugiyama

title: Statistical analysis of distance estimators with density differences and density

venue: ratios. Entropy,

authors:
Anna Korba
Adil Salim
Michael Arbel
Giulia Luise
Arthur Gretton

title: A non-asymptotic analysis for stein variational gradient descent

venue: Advances in Neural Information Processing Systems,

title: Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-state and Time-dependent Problems, volume 98

authors:
Chang Liu
Jingwei Zhuo
Pengyu Cheng
Ruiyi Zhang
Jun Zhu

title: Understanding and accelerating particle-based variational inference

authors:
Chang Liu
Jingwei Zhuo
Jun Zhu

title: Understanding MCMC dynamics as flows on the Wasserstein space

title: Stein variational gradient descent as gradient flow

authors:
Qiang Liu
Dilin Wang

title: Stein variational gradient descent: A general purpose bayesian inference algorithm

authors:
Jianfeng Lu
Yulong Lu
James Nolen

title: Scaling limit of the Stein variational gradient descent: The mean field regime

authors:
Nicholas Metropolis
Arianna W Rosenbluth
Marshall N Rosenbluth
Augusta H Teller
Edward Teller

title: Equation of state calculations by fast computing machines

venue: The journal of Chemical Physics,

title: MCMC Using Hamiltonian Dynamics, chapter 5

venue: CRC Press,

authors:
Gareth O Roberts
Osnat Stramer

title: Langevin diffusions and Metropolis-Hastings algorithms

venue: Methodology and computing in applied probability,

authors:
Gareth O. Roberts
Richard L. Tweedie

title: Exponential convergence of Langevin distributions and their discrete approximations

authors:
Adil Salim
Anna Korba
Giulia Luise

title: The wasserstein proximal gradient algorithm

venue: arXiv preprint arXiv:2002.03035,

authors:
Adil Salim
Lukang Sun
Peter Richtárik

title: Complexity analysis of stein variational gradient descent under talagrand’s inequality t1

venue: arXiv preprint arXiv:2106.03076,

title: Markov Chains for exploring posterior distributions

venue: The Annals of Statistics,

title: Optimal Transport: Old and New, volume 338

authors:
Martin J. Wainwright
Michael I. Jordan

title: Graphical models, exponential families, and variational inference

venue: Foundations and Trends in Machine Learning,

authors:
Max Welling
Yee Whye Teh

title: Bayesian learning via stochastic gradient Langevin dynamics

venue: In Proceedings of the 28th international conference on machine learning,

authors:
Michael Zhu
Chang Liu
Jun Zhu

title: Variance reduction and quasi-Newton for particle-based variational inference

venue: Proceedings of the 37th International Conference on Machine Learning,

authors:
Jingwei Zhuo
Chang Liu
Jiaxin Shi
Jun Zhu
Ning Chen
Bo Zhang

title: Message passing Stein variational gradient descent

venue: Proceedings of the 35th International Conference on Machine Learning,

heading: 1 INTRODUCTION

text:
Sampling from unnormalized distributions plays a fundamental role in statistical inference and machine learning. This problem is frequently encountered in Bayesian statistics. Conducting Bayesian analysis requires evaluation of multi-dimensional integrals where analytical expressions for unnormalized posterior distributions are usually not available. Consequently, sampling is necessary for Monte Carlo approximation of these integrals. In this work, we propose a general purpose sampling algorithm for unnormalized distributions.
Markov chain Monte Carlo (MCMC) methods (Andrieu et al., 2003; Brooks et al., 2011) are widely used to sample from unnormalized distributions. Sampling with MCMC relies on defining an appropriate transition kernel to construct a Markov chain whose equilibrium distribution is precisely the target distribution. Based on rejection sampling, the Metropolis–Hastings algorithm (Metropolis et al., 1953; Hastings, 1970; Tierney, 1994; Dunson & Johndrow, 2019) provides a flexible framework for general MCMC sampling. To implement a Metropolis–Hastings algorithm, one needs to specify a proposal density and an acceptance policy. However, without a careful design of these two aspects, the Metropolis–Hastings algorithm can be inefficient due to strong correlations, slow mixing, or low acceptance rates, especially in the large-scale and high-dimensional settings. Moreover, proposals through discretizing some continuous processes like Langevin diffusion and Hamiltonian dynamics are introduced (Roberts & Tweedie, 1996; Roberts & Stramer, 2002; Duane et al., 1987; Neal, 2011; Hoffman & Gelman, 2014) and further enhanced by stochastic gradient estimation (Welling & Teh, 2011; Chen et al., 2014).
Variational Bayesian inference (Beal, 2003), often simply referred to as variational inference (VI) (Wainwright & Jordan, 2008; Blei et al., 2017), is another prominent approach to sampling from unnormalized distributions. VI approximates the unnormalized posterior distribution with a restricted parametric variational posterior distribution by minimizing the Kullback-Leibler (KL) divergence between them. Since the true posterior distribution is intractable, VI turns to maximize a surrogate variational objective called the evidence lower bound (ELBO). However, one is required to trade off the parameterization flexibility of variational posteriors against the optimization complexity of ELBO in practice.
In the spirit of VI, particle-based variational inference (ParVI) (Liu & Wang, 2016; Chen et al., 2018; Zhu et al., 2020) iteratively optimizes a set of particles to mimic a functional gradient descent for minimizing the KL divergence. ParVI seeks to move a variational distribution towards the unnormalized target distribution, along a steepest descent direction of the KL divergence. In a continuous view, these movements of variational distributions can be understood as a gradient flow in probability measure spaces (Liu et al., 2019a;b). A key part of ParVI is how to estimate the desired steepest descent direction (i.e., functional gradient) from the evolving random particles. An elegant approach is the Stein variational gradient descent (SVGD) Liu & Wang (2016). In SVGD , the functional gradient descent is embedded in a reproducing kernel Hilbert space (RKHS), which is further recognized as a gradient flow under the Stein geometry (Liu, 2017; Lu et al., 2019; Duncan et al., 2019). A drawback of SVGD is that it tends to collapse at part of the modes of the target, due to a negative correlation between the data dimensionality and the repulsive force in the RKHS (Zhuo et al., 2018).
In this work, we propose a relative entropy gradient sampler (REGS) for sampling from unnormalized target distributions. To approximate a target distribution, we consider the Wasserstein gradient flow of relative entropy (or KL divergence), named relative entropy gradient flow. The relative entropy gradient flow represents a path of probability distributions that follows the functional gradient descent direction of relative entropy. There exists an ODE system of random particles that uniquely determines the spatial and temporal dynamics of the relative entropy gradient flow. Therefore, to sample with REGS, we only need to simulate the ODE system with particle evolution. Evaluating the velocity fields of this ODE system can be transformed into estimating the logarithmic density ratio between the density of evolving particles and the unnormalized target density. Based on this observation, we propose a novel logarithmic density ratio estimation method for unnormalized distributions. By alternating between particle evolution and velocity field estimation, we can collect a set of stable particles which are approximately distributed as the target distribution. Our contributions can be summarized as follows:
(1) Building upon the relative entropy gradient flow, we propose the relative entropy gradient sampler (REGS) for unnormalized target distributions. REGS preserves high efficiency and strong stability with respect to increasing singularity in mixtures of Gaussians, when the number of components increases (as shown in Figure 1), the variance of each component decreases, and the distance between any two components increases.
(2) We propose to directly estimate velocity fields of the relative entropy gradient flow as gradients of logarithmic density ratios, that is computationally stable and efficient.
(3) We develop a nonparametric approach to estimating the density ratio between an unnormalized density and an underlying density represented by samples, which is of independent interest.
(4) We present experimental comparisons on varieties of multi-mode synthetic data and benchmark data and demonstrate that REGS is a more accurate sampler than the popular samplers including ULA, MALA and SVGD.
Related work The proposed REGS is most related to sampling methods based on the relative entropy gradient flow, in particular, the recently proposed SVGD (Liu & Wang, 2016; Liu, 2017), which estimates the velocity fields of the relative entropy gradient flow in a reproducing kernel Hilbert space. See also Korba et al. (2020); Salim et al. (2021; 2020) for theoretical analysis of SVGD. In contrast, REGS approximates the velocity fields based on a novel logarithmic density ratio estimation approach with deep neural networks. The undesirable mode collapse feature of SVGD is not inevitable for
REGS since the approximation and expressive powers of deep neural networks is known to surpass those of kernel methods.
MCMC algorithms constructed from overdamped Langevin diffusion can be studied as discretization of the relative entropy gradient flow (Jordan et al., 1998). Based on the Euler-Maruyama discretization of overdamped Langevin diffusion, unadjusted Langevin algorithm (ULA) (Roberts & Tweedie, 1996) aims at generating samples from an approximation of the unnormalized target, but is biased for fixed step size. When a Metropolis-Hastings step is included, Metropolis-adjusted Langevin algorithm (MALA) (Roberts & Tweedie, 1996) is capable of correcting the bias, but leaves a large number of intermediate samples rejected. In REGS, one only needs to estimate the deterministic velocity fields of the relative entropy gradient flow, which differs from running ULA and MALA with randomness from diffusion processes. All particles produced by REGS are generated from an approximation of the target distribution.
Another line of work (Gao et al., 2019; 2021) uses Wasserstein gradient flows of f -divergences for generative learning with samples from the underlying target distribution. In their work, evaluating velocity fields of gradient flows also boils down to estimating density ratios. However, our current problem is to sample from an unnormalized target density. Furthermore, we propose a novel density ratio estimation procedure when the target distribution is only known up to a normalizing constant.
Notation Let P2(X ) be the space of Borel probability measures on a support space X ⊂ Rd with a finite second moment, and let Pa2 (X ) be a subspace of P2(X ) whose measures are absolutely continuous w.r.t. the Lebesgue measure. All probability measures we considered thereinafter are assumed to belong to Pa2 (X ). To ease the notation, we use probability density functions such as q(x), p(x),x ∈ X to express probability distributions in Pa2 (X ). Let (Pa2 (X ),W2) denote the metric space Pa2 (X ) endowed with the 2-Wasserstein distance W2, which is referred to as the quadratic Wasserstein space. We use ∇ and Div to denote the gradient operator and the divergence operator, respectively.

heading: 2 PROBLEM FORMULATION

text:
Consider an unnormalized probability density function u : X → [0,∞), where X ⊆ Rd is the support of u. Suppose u has an intractable normalizing constant Z = ∫ X u(x)dx <∞. Our goal is to generate random samples from the underlying distribution p ∈ Pa2 (X ), whose probability density function is only known up to proportionality, i.e., p(x) = u(x)/Z,x ∈ X . The basic idea is to gradually optimize samples from a given distribution q ∈ Pa2 (X ) to approximate samples from p, where it is easy to sample from q. Optimizing samples leads to functional optimization of distributions. We then introduce the classical relative entropy as the functional optimization objective. The relative entropy, a.k.a., the Kullback–Leibler divergence, for q, p ∈ Pa2 (X ) is the average logarithmic density ratio, which is defined as
Dre(q‖p) = ∫ X q(x) log ( q(x) p(x) ) dx. (1)
It holds that Dre(q‖p) ≥ 0 and Dre(q‖p) = 0 iff q(x) = p(x) a.e. x ∈ X . Moreover, we denote the relative entropy functional as
F [·] := Dre(·‖p) : Pa2 (X )→ [0,∞]. (2) To sample from the unnormalized density u = pZ, we consider the functional minimization problem
min q∈Pa2 (X )
F [q], (3)
where F [q] is always minimized at the underlying target distribution p, i.e., q(x) = p(x) a.e. x ∈ X . In a nutshell, problem (3) is an energy functional minimization problem in a metric space. To minimize the energy functional F , it suffices to move along the corresponding gradient flow in a metric space until the flow converges. For example, a gradient flow in the Euclidean space refers to a curve whose tangent space contains the steepest descent direction of a given function. Analogously, a gradient flow in the space of probability measures means a curve that points in the steepest descent direction of a given energy functional. When equipped with the 2-Wasserstein distance, minimization of the energy functional F naturally corresponds to a continuous path on the quadratic Wasserstein space of distributions, which is commonly known as a Wasserstein gradient flow of the relative entropy. We call this flow a relative entropy gradient flow for briefness.

heading: 3 RELATIVE ENTROPY GRADIENT FLOW

text:
In this section, we briefly review the formulation of relative entropy gradient flow and its connections to differential equations. We consider the properties of gradient flows in the quadratic Wasserstein space (Pa2 (X ),W2). Recall that F in (2) is the relative entropy functional defined on (Pa2 (X ),W2). One can show that a curve {qt}t≥0 in (Pa2 (X ),W2) is a relative entropy gradient flow of F if it satisfies the continuity equation (Ambrosio et al. (2008), page 295 and Villani (2008), page 631),
∂tqt = Div ( qt∇
δF [qt] δqt
) , (4)
where qt(x) = q(t,x) evolves over time, δF [qt] δqt = log qtp is the first variation of the energy functional F at qt, and∇ δF [qt]δqt is the Euclidean gradient of δF [qt] δqt
. Here, we identify the gradient as the relative entropy gradient, which is defined by
∇W2F [qt] := ∇ δF [qt] δqt = ∇ log qt p . (5)
Moreover, the relative entropy F dissipates along the relative entropy gradient flow {qt}t≥0 at the rate (Ambrosio et al. (2008), page 295)
∂tF [qt] = −Eqt [‖∇W2F [qt]‖2]. (6) Therefore, the relative entropy gradient flow {qt}t≥0 eventually converges to the target distribution p as t→∞. As pointed out in Ambrosio et al. (2008) (Page 175), under mild conditions the continuity equation (4) concerning {qt}t≥0 determines a time-inhomogeneous Markov process {Xt}t≥0 that starts at a random particle X0 ∼ q0 and follows the particle evolution dynamics
dXt dt = vt(Xt), Xt ∼ qt, t ≥ 0. (7)
Note that the velocity fields
vt = −∇W2F [qt] = ∇ log p
qt , t ≥ 0 (8)
drive the evolution of the particle Xt in the Euclidian space, which results in the transport of qt in (Pa2 (X ),W2). An important observation is that
vt = ∇ log p qt = ∇ log u qt , t ≥ 0. (9)
Therefore, the velocity fields do not involve the unknown normalizing constant Z. This is the key motivation for us to use the relative entropy gradient flow in the proposed method.

heading: 4 SAMPLING AS PARTICLE EVOLUTION

text:
As indicated by the energy dissipation of relative entropy F in (6), running the relative entropy gradient flow {qt}t≥0 dynamics can provide a nice approximate solution to the functional minimization problem (3) when time t is large enough. Therefore, to sample from the target distribution p, it is appropriate to simulate the relative entropy gradient flow {qt}t∈[0,T ] with the time horizon T sufficiently large. A natural strategy is to discretize the particle evolution form of relative entropy gradient flow in (7) with forward Euler iterations (LeVeque, 2007) as follows,
Xk+1 = Xk + svk(Xk), X0 ∼ q0, k = 0, 1, . . . ,K − 1, (10) with the velocity field at step k
vk = −∇W2F [qk] = ∇ log p
qk , (11)
where s > 0 is a tunable small step size, K = bT/sc is the number of iterations and qk is the corresponding discretized gradient flow at step k, i.e., Xk ∼ qk. Combining the expressions in (10) and (11), we have that the iterations progress according to
Xk+1 = Xk + s∇ log p
qk , X0 ∼ q0, k = 0, 1, . . . ,K − 1. (12)
In principle, it is necessary to evaluate the velocity field vk = ∇ log(p/qk) each iteration in (12). By (9), the velocity field of the relative entropy gradient flow can be simplified to
vk = ∇ log p qk = ∇ log u qk , k = 0, 1, . . . ,K − 1, (13)
where u = Zp is the given unnormalized density of the target distribution p. Then only the density qk remains unknown for evaluating the velocity field. Ideally, qk can be estimated by evolving a large number of particles {Xik}Ni=1. However, direct estimation of qk is difficult due to the curse of dimensionality and the potential expensive computation cost for different ks. Our solution is to approximate the velocity field (13) as a whole.
Assuming a nice approximation v̂k of the velocity field (13) is provided, then one can implement the following iterations for approximately sampling from qK with no effort,
X̃k+1 = X̃k + sv̂k(X̃k), X̃0 ∼ q0, k = 0, 1, . . . ,K − 1. (14)
Through the iterations above, we can collect X̃k ∼ q̃k ≈ qk, k = 1, 2, . . . ,K. We will discuss approximation of the velocity field vk = ∇ log(u/qk) from the perspective of estimating the logarithmic density ratio log(u/qk) in the next section.

heading: 5 LOGARITHMIC DENSITY RATIO ESTIMATION AND THE RELATIVE ENTROPY GRADIENT SAMPLER

text:
In this section, we first propose a novel estimation procedure of the logarithmic density ratio log(u/q) based on an unnormalized density u and random samples from q.
We use a model ratio R : X → [0,∞) to fit the true ratio R?uq = u/q between a density q and an unnormalized density u. Let g : R → R be a differentiable and strictly convex function. A Bregman score (Dawid, 2007; Gneiting & Raftery, 2007; Kanamori & Sugiyama, 2014) with the base probability measure q ∈ Pa2 (X ) to measure the discrepancy between R and R?uq is defined by
B(R) = EX∼q[g′(R(X))R(X)− g(R(X))]− EX∼w [ u(X)
w(X) g′(R(X))
] ,
where w ∈ Pa2 (X ) is an introduced and reference distribution for calculating the integral involving u. It should be easy to sample from w and the support of u should be included in the support of w. Additionally, B(R) ≥ B(R?uq), where the equality holds iff R(x) = R?uq(x) (q, u)-a.e. x ∈ X .
In this work, we take g(x) = x log(x)− x. We use this function for two reasons: (a) convexity, this is to satisfy the basic requirement of the Bregman score; (b) cancellation of the unknown normalizing constant Z of u. Simple calculation shows that B(R) can be written as
B(R) = EX∼q[R(X)]− EX∼w [ u(X)
w(X) log(R(X))
] . (15)
Recall that the true density ratio R?uq can be factorized as R ? uq = u/q = Z(p/q). Thus the numerical scale of the true density ratio R?uq hinges on two factors, i.e., the normalizing constant Z of u and the standard density ratio p/q. Since numerical scales of these factors are difficult to determine in applications, the induced numerical instability can deteriorate the density ratio estimate. In order to prevent the density ratio estimation from such instability, we consider the model ratio R on the logarithmic scale. This will also release the nonnegative constraint on R as a byproduct.
From now on, we denote D?uq = log(R ? uq), D = log(R) : X → R. Then B(D) can be rewritten as B(D) = EX∼q[exp(D(X))]− EX∼w [ u(X)
w(X) D(X)
] . (16)
It can be shown that the logarithmic density ratio D?uq is identifiable at the population level by minimizing (16) with respect to D. Theorem 1. For B(D) defined in (16), we haveD?uq ∈ arg minDB(D). In addition, for anyD with EX∼w [ u(X) w(X)D(X) ] <∞, B(D) ≥ B(D?uq), with equality iffD(x) = D?uq(x) (q, u)-a.e. x ∈ X .
Algorithm 1: REGS: Relative entropy gradient sampler Input: u = Zp // unnormalized target density step size s > 0, an integer K > 0, // step size, maximum loop count X̃i0 ∼ q0, i = 1, 2, . . . , n // initial particles w ∈ Pa2 (X ) // reference distribution k ← 0 while k < K do
Y ik ∼ w, i = 1, 2, . . . , n // reference samples D̂φk ∈ argminDφ 1 n ∑n i=1 [ exp(Dφ(X̃ i k))− u(Y ik )
w(Y i k ) Dφ(Y
i k ) ]
// log density ratio
v̂k(x) = ∇D̂φk (x) // velocity field X̃ik+1 = X̃ i k + sv̂k(X̃ i k), i = 1, 2, . . . , n // update particles
k ← k + 1 end Output: X̃iK ∼ q̃K ≈ p, i = 1, 2, . . . , n // output particles
Based on Theorem 1, we can estimate the unknown logarithmic density ratio D?uqk = log(u/qk) with a deep neural network Dφ with parameter φ through the sample version of (16). Let {X̃ik}ni=1 be i.i.d. samples from q̃k ≈ qk and {Y ik}ni=1 be i.i.d. samples from a reference distribution w. We solve the following deep nonparametric estimation problem via stochastic gradient descent (SGD) for D̂φk
D̂φk ∈ arg min Dφ
B̂(Dφ) = 1
n n∑ i=1 [ exp(Dφ(X̃ i k))− u(Y ik ) w(Y ik ) Dφ(Y i k ) ] . (17)
With the logarithmic density ratio estimator D̂φk , the velocity field vk in (13) can be approximately computed by v̂k = ∇D̂φk . By considering sampling as a particle evolution process discussed in Section 4, REGS updates the initial particles {X̃i0}ni=1 with iterations in (14) as follows:
X̃ik+1 = X̃ i k + sv̂k(X̃ i k), X̃ i 0 ∼ q0, i = 1, 2, . . . , n, k = 0, 1, . . . ,K − 1. (18)
We summarize the proposed REGS for sampling from an unnormalized density in Algorithm 1.

heading: 6 NUMERICAL EXPERIMENTS

text: We evaluate REGS on a large number of 1D and 2D mixture distributions and test its stability in the high-dimensional setting with multivariate Gaussian distributions. We also use REGS to perform Bayesian logistic regression on benchmark datasets. For comparison, we consider three existing methods including SVGD (Liu & Wang, 2016), ULA (Roberts & Tweedie, 1996) and MALA (Roberts & Tweedie, 1996). All experiments are done using a NVIDIA Tesla K80 GPU and common CPU computing resources. The neural network architecture, hyperparameter values, dataset descriptions, and additional experimental results are given in the appendix. The python code of REGS is available at https://github.com/anonymous/REGS.

heading: 6.1 MIXTURE DISTRIBUTIONS

text:
We run REGS and SVGD, ULA and MALA to generate 2000 particles for mixtures of 2, 8 and 9 Gaussians (see Scenarios 4, 5, 6 in Appendix B), and 5000 particles for a mixture of 25 Gaussians (see Scenario 9 in Appendix B). The sampling qualities of these algorithms are compared by scatter plots with density contours of target mixture distributions. We classify all scatter points with labels according to the nearest mode, and plot the histograms of the label counts.
Gaussian mixtures with equal weights Figure 2 shows the scatter plots and histograms of samples generated by (a) REGS, (b) SVGD, (c) ULA with 50 chains, and (d) MALA with 50 chains from mixtures of 8 Gaussians with equal weights. It shows that REGS is able to explore all the components in the mixture distribution nearly equally. However, SVGD is only able to find part of the modes, as indicated in Figures 2(b). Figures 2(c) and 2(d) show that MALA and ULA with 50 chains find all modes but with unequal weights, especially as the variance of each component decreases.
Gaussian mixtures with unequal weights Figure 3 shows the scatter plots and histograms of samples generated by (a) REGS, (b) SVGD, (c) ULA with 50 chains, and (d) MALA with 50 chains from mixtures of 8 Gaussians with unequal weights (1, 1, 1, 1, 3, 3, 3, 3)/16. Figure 3(a) shows that the samples generated by REGS have the correct weights. Figures 3(c) and 3(d) indicate that ULA
and MALA assign particles to modes with incorrect weights. Moreover, the quality of the samples generated by SVGD, ULA and MALA deteriorates as the number of modes increases, while the performance of REGS remains stable. We also included the results from ULA and MALA with a single chain in Figures 7 and 10 in Appendix D, which show that these samplers have difficulty with multimodal distributions if only a single chain is used.
To further analyze the performance, we report the Monte Carlo estimates of E[h(X)] using a test function h in Table 1, where h(x) = αTx, (αTx)2, and 10 cos(αTx+ 1/2) with α ∈ R2, ‖α‖2 = 1, and X is distributed as various Gaussian mixtures with unequal weights. By comparing the Monte Carlo estimates of E[h(X)] using the samplers with the values based on target samples, we see that REGS performs better and is more stable than SVGD, ULA and MALA, especially when h(x) = 10 cos(αTx+ 1/2). We include additional numerical results including more scatter plots and histograms (Figure 6-10) and Monte Carlo estimates with equal wieights (Table 6) in Appendix D.

heading: 6.2 MULTIVARIATE GAUSSIAN DISTRIBUTION

text: Let the target distribution be a d-dimensional Gaussian distribution with mean µ = (1, 1, · · · , 1) ∈ Rd and covariance matrix Σ ∈ Rd×d,Σi,j = ρ|i−j| with ρ = 0.7. We consider four test functions h(x), i.e., h(x) = αTx (the first moment), h(x) = (αTx)2 (the second moment), h(x) = exp(αTx) (the moment generating function), and h(x) = 10 cos(αTx + 1/2) with α ∈ Rd satisfying ‖α‖2 = 1. For reference, we provide the Monte Carlo estimates of E[h(X)] using target samples. We compare REGS with SVGD, ULA_1, MALA_1, ULA_50, MALA_50 in Figure 4, the number of particles is 5000 for each sampler, where ULA_k and MALA_k denote the ULA and MALA with k chians. For ULA and MALA, because of large variations of the estimates, we repeat the process 10 times and compute the average as the final estimate. Figure 4 presents these Monte Carlo estimates as d increases from 10 to 300 with step size 10. The logarithm of the estimated E[exp(αTX)] is shown. As shown in Figure 4, the estimates using REGS and SVGD have smaller fluctuations than those using ULA and MALA, although all four methods can estimate E[αTX] and E[(αTX)2] well. Moreover, the third and the fourth panels in Figure 4 show that REGS outperforms SVGD, ULA and MALA when h(x) = exp(αTx) or 10 cos(αTx+ 1/2).

heading: 6.3 BAYESIAN LOGISTIC REGRESSION

text: We apply REGS to Bayesian logistic regression for binary classification on five datasets, including Banana, German, Image, Ringnorm, and Covertype. These datasets were analyzed in Liu & Wang (2016) and the first four datasets had been analyzed in Gershman et al. (2012). We consider a similar setting to that in (Liu & Wang, 2016; Gershman et al., 2012), which assigns a Gaussian prior π(β|α) = N (0, α−1I) to the regression coefficient β (including the intercept). We specify the prior of α as π(α) = Gamma(1, 0.01). For comparison, we consider SVGD, ULA and MALA. The inference is based on the posterior π(β|data). These datasets are partitioned randomly into two parts, the training sets (80%) and the test sets (20%). We repeats the random partition 10 times. We evaluate the classification accuracy on test data with 5000 particles from the posterior. Table 2 lists the averages and standard errors (in parenhteses) of test accuracy. From Table 2 we can see that REGS is comparable with SVGD, ULA and MALA. For the Covertype dataset, MALA failed to converge, so no results from it are included in Table 2.

heading: 6.4 DISCUSSION OF THE EXPERIMENTAL RESULTS

text: The experimental results reported above and in the appendix indicate that REGS is capable of generating better quality samples than SVGD, ULA and MALA from Gaussian mixture distributions. Also, the results suggest that particles generated by REGS can cross valleys in the landscape of a multimodal distribution even if they are initialized in a different regions. An intuitive explanation is as follows. The movement of the REGS particles is determined by the velocity field. If the velocity field is not zero at a particle, the particle will continue to evolve towards the target distribution. Moreover, all particles interact with each other through the velocity field, which is beneficial in sampling from multimodal distributions. For ULA and MALA, there are no interactions among particles or incentives for particles to cross valleys between two modes, thus it is more difficult for these methods to sample from multimodal distributions. A possible remedy is to use multiple chains as we did in the above experiments. To some extend, this alleviates the problem encountered in sampling from multimodal distributions. However, the success of this strategy depends on the initial samples being near the modes as well as having the correct proportions of the initial samples being close to each mode. In comparison, REGS uses a principled way to move particles from an initial reference distribution to a multimodal distribution, albeit with a higher computational cost.

heading: 7 CONCLUSION

text:
We have introduced REGS, a novel gradient flow based method for sampling from unnormalized distributions. Extensive numerical experiments demonstrate that REGS performs better than several existing popular sampling methods in the setting of challenging multimodal mixture distributions. In future work, we hope to establish the convergence properties of REGS generated sampling distributions as the numbers of iterations and particles increase.
As with any sampling algorithms, there is a trade-off between sampling quality and computational efficiency. On one hand, as our numerical experiments demonstrate, REGS can generate samples with better quality than the three existing methods we considered in the challenging mixture model settings. On the other hand, REGS is computationally more expensive, as it involves neural network training in the iterations, compared with existing methods such as ULA and MALA that can be implemented more quickly. As computational power continues to increase rapidly, REGS can be a useful addition to the toolkit of sampling methods for multimodal distributions.

heading: A APPENDIX

text: In this appendix, we prove Theorem 1, give a detailed description of the models in the numerical experiments, the neural network architecture used in implementing REGS, and additional numerical results.

heading: B PROOF OF THEOREM 1

text:
Proof. By the definition of Bregman score B(R) between u and q, it is easy to check
R?uq ∈ arg min R B(R),
B(R) ≥ B(R?uq) with equality iff R(x) = R?uq(x) (q, u)-a.e. x ∈ X .
Since D?uq = log(R ? uq), D = log(R),B(R) = B(D), when EX∼w [ u(X) w(X)D(X) ] <∞, we have
D?uq ∈ arg min D B(D),
B(D) ≥ B(D?uq) with equality iff D(x) = D?uq(x) (q, u)-a.e. x ∈ X .

heading: C GAUSSIAN MIXTURE DISTRIBUTIONS

text:
Let the density of a d-dimensional multivariate Gaussian distribution with mean µ ∈ Rd and covariance matrix Σ ∈ Rd×d be
f(x;µ,Σ) = 1
(2π) d 2 √ det(Σ) exp
{ −1
2 (x− µ)TΣ−1(x− µ)
} .
We consider several scenarios below for the unnormalized density function u(x).
Scenario 1. 2Gaussians_1d1. One-dimensional mixture of 2 Gaussians,
u(x) = 1
3 f(x;µ1, σ
2 1) +
2 3 f(x;µ2, σ 2 2),
where µ1 = 1, µ2 = −2, and σ21 = 0.25, σ22 = 2; Scenario 2. 2Gaussians_1d2. One-dimensional mixture of 2 Gaussians,
u(x) = 1
3 f(x;µ1, σ
2 1) +
2 3 f(x;µ2, σ 2 2),
where µ1 = 3, µ2 = −3, and σ21 = 0.25, σ22 = 2; Scenario 3. 2Gaussians_1d3. One-dimensional mixture of 2 Gaussians,
u(x) = 1
3 f(x;µ1, σ
2 1) +
2 3 f(x;µ2, σ 2 2),
where µ1 = 3, µ2 = −3, and σ21 = 0.03, σ22 = 0.03; Scenario 4. 2Gaussians. Two-dimensional mixture of 2 Gaussians,
u(x) = f(x;µ1,Σ1) + f(x;µ2,Σ2),
where µ1 = (r, 0)T, µ2 = (−r, 0)T, and Σ1 = Σ2 = σ2I. Scenario 5. 8Gaussians. Two-dimensional mixture of 8 Gaussians,
u(x) = 8∑ j=1 f(x;µj ,Σj),
where µj = r(sin(2(j − 1)π/8), cos(2(j − 1)π/8))T, and Σj = σ2I for j = 1, · · · , 8.
Scenario 6. 9Gaussians. Two-dimensional mixture of 9 Gaussians,
u(x) = 3∑ j=1 3∑ k=1 f(x;µjk,Σjk),
where µjk = 4(j − 2, k − 2)T, Σjk = σ2I for j = 1, 2, 3 and k = 1, 2, 3. Scenario 7. 16Gaussians_1c. Two-dimensional mixture of 16 Gaussians,
u(x) = 16∑ j=1 f(x;µj ,Σj),
where µj = 4(sin(2(j − 1)π/16), cos(2(j − 1)π/16))T, and Σj = 0.03I for j = 1, · · · , 16.
Scenario 8. 16Gaussians_2c. Two-dimensional mixture of 16 Gaussians,
u(x) = 8∑ j=1 f(x;µj ,Σj) + 8∑ k=1 f(x;µk,Σk),
where µj = 4(sin(2(j − 1)π/8), cos(2(j − 1)π/8))T, µk = 2(sin(2(j − 1)π/8), cos(2(j − 1)π/8))T, and Σj = Σk = 0.03I for j = 1, · · · , 8 and k = 1, · · · , 8.
Scenario 9. 25Gaussians. Two-dimensional mixture of 25 Gaussians,
u(x) = 5∑ j=1 5∑ k=1 f(x;µjk,Σjk),
where µjk = 2(j − 3, k − 3)T, Σjk = σ2I for j = 1, · · · , 5 and k = 1, · · · , 5. Scenario 10. 49Gaussians. Two-dimensional mixture of 49 Gaussians,
u(x) = 7∑ j=1 7∑ k=1 f(x;µjk,Σjk),
where µjk = 32 (j − 4, k − 4) T, Σjk = 0.03I for j = 1, · · · , 7 and k = 1, · · · , 7.
Scenario 11. 81Gaussians. Two-dimensional mixture of 81 Gaussians,
u(x) = 9∑ j=1 9∑ k=1 f(x;µjk,Σjk),
where µjk = 32 (j − 5, k − 5) T, Σjk = 0.03I for j = 1, · · · , 9 and k = 1, · · · , 9.
Scenario 12. 1circle. Let µi = 4(cos(2iπ/N), sin(2iπ/N))T, i = 0, 1, · · · , N − 1 with N = 400. Consider three noise to be added to each point µi, including the uniform distribution U(µi, 1/30) on a disc with center at µi and radius 1/30, Gaussian distribution N(µi, 0.03I), and mixed these two distributions. Scenario 13. 2circles. Let µ1i = 2(cos(2iπ/N), sin(2iπ/N))T and µ2i = 4(cos(2iπ/N), sin(2iπ/N))T, i = 0, 1, · · · , N − 1 with N = 200. Consider three noise to be added to each point µki including uniform distribution U(µki, 1/30) on a disc with center at µki and radius 1/30, Gaussian distribution N(µki, 0.03I), and mixed these two distributions, k = 1, 2.
Scenario 14. 1spiral. Let µi = 4iπN cos(4iπ/N), sin(4iπ/N)) T, i = 0, 1, · · · , N − 1 with N = 400.
Consider three noise to be added to each point µi, including the uniform distribution U(µi, 1/30) on a disc with center at µi and radius 1/30, Gaussian distribution N(µi, 0.03I), and mixed these two distributions.
Scenario 15. 2spirals. Let µ1i = 3iπN (cos(3iπ/N), sin(3iπ/N)) T and µ2i =
− 3iπN (cos(3iπ/N), sin(3iπ/N)) T, i = 0, 1, · · · , N − 1 with N = 200. Consider three noise to be added to each point µki including uniform distribution U(µki, 1/30) on a disc with center at µki and radius 1/30, Gaussian distribution N(µki, 0.03I), and mixed these two distributions, k = 1, 2.
Scenario 16. moons. Let µ1i = (8i/N − 6, 4 sin(iπ/N))T and µ2i = (8i/N − 2, 4 sin(iπ/N))T, i = 0, 1, · · · , N − 1 with N = 200. Consider three noise to be added to each point µki including uniform distribution U(µki, 1/30) on a disc with center at µki and radius 1/30, Gaussian distribution N(µki, 0.03I), and mixed these two distributions, k = 1, 2.

heading: D EXPERIMENTAL SETTING

text:
D.1 HYPERPARAMETER
We burn in the first 1000 particles for ULA and MALA in all experiments. We initialize the particles in SVGD, ULA and MALA as zeros or random samples from Gaussians. We provide the step size settings in Table 3. For SVGD, we use RBF kernel k(x, x′) = exp(− 1h‖x − x
′‖22) and set the bandwidth as h = med2/ log n, where med is the median of pairwise distances between the particles {xi}ni=1. We set the learning rate of neural networks as 5e-4 for density ratio estimation in REGS. The network structures are presented in Table 4. The initial particles in REGS are sampled from Gaussian distributions.
D.2 NEURAL NETWORK ARCHITECTURE
Covertype: https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ binary.html Banana, German, Image, Ringnorm: http://theoval.cmp.uea.ac.uk/ matlab/default.html
E ADDITIONAL NUMERICAL RESULTS