Year: 2019

Abstract:
Visual relationship recognition models are limited in the ability to generalize from finite seen predicates to unseen ones. We propose a new problem setting named predicate zero-shot learning (PZSL): learning to recognize the predicates without training data. It is unlike the previous zero-shot learning problem on visual relationship recognition which learns to recognize the unseen relationship triplets (<subject, predicate, object>) but requires all components (subject, predicate, and object) to be seen in the training set. For the PZSL problem, however, the models are expected to recognize the diverse even unseen predicates, which is meaningful for many downstream high-level tasks, like visual question answering, to handle complex scenes and open questions. The PZSL is a very challenging task since the predicates are very abstract and follow an extreme long-tail distribution. To address the PZSL problem, we present a model that performs compatibility learning leveraging the linguistic priors from the corpus and knowledge base. An unbalanced sampled-softmax is further developed to tackle the extreme long-tail distribution of predicates. Finally, the experiments are conducted to analyze the problem and verify the effectiveness of our methods. The dataset and source code will be released for further study.

heading: 1 INTRODUCTION
text: Visual relationship recognition (Johnson et al., 2015; Lu et al., 2016; Xu et al., 2017) aims to estimate the relationships between pairs of localized entities, i.e., performing the recognition of triplets <subject, predicate, object>. It structurally describes images, which provides rich semantic information of an image to many applications including visual question answering (VQA) (Li et al., 2018), image captioning (Yang et al., 2019) and image retrieval (Johnson et al., 2015). The relationship recognition methods are mainly supervised to recognize the entities and then combine various entities in pairs to identify predicates between them. There is an increasing interest in relationship zero-shot learning (ZSL) that learns to recognize the unseen relationship triplets, where the studies (Lu et al., 2016; Yu et al., 2017) on this ZSL problem setting assume the components (subject, predicate, and object) of the relationship triplet are seen. However, almost all of them only focus on dozens of frequent predicates and do not study the generalization of the seen predicates to the unseen ones.
In this work, we propose the predicate zero-shot learning (PZSL) problem setting focusing on recognizing the unseen predicates (no manual annotations or image samples). For example, given no instance of chew in the training data, the model is expected to recognize it during testing. Recognizing diverse even unseen predicates is significant for providing very rich relationship information, describing the complex scenes, and analogizing the known abstract concepts to the novel ones. The solution of the PZSL problem will greatly promote many downstream tasks, such as generating image caption with vivid predicates which are even unseen in the description corpus (image captioning) and answering the open questions (with novel predicates) on the complex scene (VQA).
Although zero-shot learning in image classification has received increasing attention (Larochelle et al., 2008), PZSL is not explored. Furthermore, the PZSL problem is more challenging in the following aspects. a) Recognizing predicates is difficult since predicates are often abstract not as specific as objects. Analogizing the seen abstract predicates to the unseen ones further escalates the difficulty. Many object ZSL methods (Lampert et al., 2014; 2009) adopt the pre-defined attributes of
objects to recognize the unseen object. However, it is difficult to define the attributes of predicates. b) Predicates of existing datasets follow an extreme long-tail distribution (92.26% predicates with the number of instances lower than 10 in Visual Genome (Krishna et al., 2017)). The statistics of the dataset (VG-Zero) in this work are shown in Fig. 4. Under this distribution, the model tends to collapse to output few frequent predicates. Note that if the infrequent predicates are not recognized, the unseen predicates are more unlikely to be recognized.
To address the PZSL problem, we introduce a basic model to perform compatibility learning (Frome et al., 2013; Akata et al., 2016; 2015) (Fig. 1), leveraging the linguistic priors from the corpus and knowledge base (Wang et al., 2018; Kampffmeyer et al., 2018). To represent the abstract predicates, we adopt the pre-trained word (sentence) vectors to initialize the predicates, connect them with linguistic relations defined in knowledge bases, and map them into a semantic embedding space (middle of Fig.1). A visual module is then applied to map paired image regions (left of Fig. 1) into a visual feature space. The visual feature and semantic embedding spaces fall in the common space (top of Fig. 1). During training, the visual feature and semantic embedding space are aligned with the seen predicates as anchors, i.e., a visual feature and semantic embedding labeled with the same predicate fall onto the same point/area in the common space. During testing, the samples in the test set are mapped into the visual feature space and matched with the nearest neighbor semantic embeddings of predicates (like chew). Furthermore, to tackle the long-tail distribution, an unbalanced sampled-softmax is developed to adjust the gradient penalty of the infrequent predicates.
The main contributions include: a) We define the predicate zero-shot learning (PZSL) problem and introduce the corresponding dataset (based on Visual Genome). b) We propose a basic model to address the PZSL problem by compatibility learning leveraging the linguistic priors from the corpus and knowledge base. c) We develop an unbalanced sampled-softmax for handling the extreme long-tail distribution of predicates. d) The dataset and source code of this work will be released.

heading: 2 RELATED WORK
text: Visual relationships have been studied from various aspects including statistical motifs (Zellers et al., 2018), entity-relationship dependencies (Xu et al., 2017), spatial priors (Dai et al., 2017), language statistics (Li et al., 2017). Almost all of them focus on recognizing dozens of the most frequent predicates. By contrast, our work explores to train a model with about 1000 predicates and test it with about 100 unseen predicates. The two most relevant problem settings are relationship zero-shot learning setting (Lu et al., 2016) and open vocabulary setting (Zhang et al., 2018). Lu et al. (2016) try to recognize the unseen relationships (e.g., <elephant, stand on, street>) by
transferring knowledge from similar relationships (e.g., <dog, stand on, street>). Note that all the test predicates and entities are seen in the training set. By contrast, the main difficulty in our problem setting is that all test predicates are unseen in the training set. Zhang et al. (2018) perform visual relationship recognition with an open vocabulary setting focusing on large-scale recognition problem without study on ZSL. The most relevant approach in visual relationship recognition is Graph R-CNN (Yang et al., 2018) which adopts a graph convolutional network (GCN) (Kipf & Welling, 2016) to capture contextual information between visual objects and relations. By contrast, we utilize GCNs to leverage the relations of categories to generate meaningful semantic embeddings.
Zero-shot learning (ZSL). To recognize unseen objects, compatibility learning frameworks (Frome et al., 2013; Fu et al., 2015; Fu & Sigal, 2016) map visual and semantic features into the common space and align the visual and semantic manifolds with the seen categories. During testing, these methods recognize the given visual feature by performing a nearest neighbor search on the semantic embeddings of the categories. Recent works (Wang et al., 2018; Kampffmeyer et al., 2018) utilize the linguistic relations between seen and unseen categories in a knowledge graph (KG) for ZSL. Wang et al. (2018) propose to train a GCN supervised by the classifier’s weights of neural network. Our method can be considered as a hybrid of compatibility learning frameworks and knowledge graph based methods. The node embedding of KG is mapped into the same space with the visual feature.
External knowledge bases (KB), such as Wikipedia and ConceptNet (Speer & Havasi, 2013), has been introduced in visual relationship recognition to provide linguistic and commonsense priors. Yu et al. (2017) extract the <subject, predicate, object> triplets from Wikipedia and leverage the statistics P(pred|sub, obj) to help recognizing the unseen relationship triplets. Baier et al. (2017) train a semantic model from a KB to improve the performance. Gu et al. (2019) takes the detected objects to retrieve on the ConceptNet to obtain a set of triplets to enhance the visual features. Unlike the prior works essentially using the statistics of <subject, predicate, object> from the external KB, our work leverages the linguistic relations of predicates defined in WordNet (Miller, 1992) to explicitly connect the predicates, such as <attack, is a hyponym of, fight>, for recognizing the unseen predicates.

heading: 3 PROBLEM SETUP
text: Setting: Let the full predicate vocabulary as Vpred = Vtrpred ∪ Vtepred and entity vocabulary as Ven, where Vtrpred and Vtepred are the training and test predicate vocabulary respectively, and “entity” refers to “subject” and “object”. The training and test predicates are disjoint, i.e., Vtrpred ∩ Vtepred = φ. The dataset is denoted as D = {(Ii, 〈bsij , sij ; pij ; boij , oij〉)} , where sij , oij ∈ Ven denote subject and object labels of the j-th relationship in i-th image Ii (the green box in Fig. 2 (A)), bsij , b o ij are the corresponding boxes of the subject and object, and pij ∈ Vtrpred∪Vtepred is the corresponding predicate label. Any image that contains a test predicate p ∈ Vtepred is assigned to the test set Dte, and only the regions with test predicate p ∈ Vtepred are used for evaluation. The rest data is split into the training set Dtr and validation set Dval. During testing, given an image and pair of subject and object boxes from the test set Dte, the model (trained on Dtr) recognizes a triplet <subject, predicate, object>, where the accuracy of predicates is in concern.
Assumption: We assume that, for any test predicate pte ∈ Vtepred, there exists training predicate ptr ∈ Vtrpred having semantic association with pte. For example, if chew is a test predicate, the predicates meaning an action using teeth (like bite) or intaking food (like eat) is expected to be included in the training set. Let the visual features and semantic embedding of bite are aligned, so does that of eat. As a result, the visual feature of chew, visual similar to that of bite and eat, is able to match to the predicates likes bite and eat in the semantic embedding space. To satisfy this assumption, the training predicates should be in large-scale to cover as much semantics as possible.

heading: 4 APPROACH
text: In this section, we first present the pipeline of our basic model, then the Simplified PinSage (a fast graph convolutional network) for propagating on the large-scale knowledge graph, and finally unbalanced sampled-softmax to handle the extreme long-tail distribution.

heading: 4.1 PIPELINE
text: The pipeline of our method consists of visual and knowledge modules, refer to Fig.2. They are modeled by a Faster R-CNN (Ren et al., 2017) and two GCNs (Kipf & Welling, 2016) respectively.
Visual module aims to extract visual features of entity and predicate. Given an image as input, the corresponding features of the subject, object and context region are cropped out, where context region refers to the union of subject and object regions. All these feature regions are ROI aligned (He et al., 2017) as ROI features with fixed size (7×7). The ROI features of subjects (blue) and objects (yellow) are then mapped into visual entity features Vs and Vo by the same multilayer perceptron MLPen. Furthermore, the ROI feature of context region (green box) is fed to MLPp and the output of which is fused with Vs and Vo to generate visual predicate feature Vp. All these features Vs, Vo and Vp will be aligned with the corresponding semantic embeddings Es, Eo and Ep.
Knowledge module aims to generate the meaningful semantic embeddings of the categories (including predicates and entities). To introduce the language prior and implicit association of the categories, the embeddings of the categories are initialized with word (sentence) vectors pre-trained on a large-scale corpus (like GloVe (Pennington et al., 2014)). The categories are then connected by the linguistic relations (defined by a KB, WordNet) to build a knowledge graph. Note that many categories are not directly connected, but can be indirectly connected through categories within the KB outside the dataset. Thus the knowledge graph contains a huge number of nodes and provides rich linguistic information. Taking the knowledge graph as input, the semantic embeddings of predicate Ep and entity Een are generated by graph convolutional networks GCNp, GCNen respectively. For this part, the Simplified PinSage is introduced for fast processing on the large-scale graph, refer to § 4.2.
Loss function is defined as a summation of the entity and predicate terms as follows: L = Lentity + Lpredicate, (1)
where Lpredicate is designed with the proposed unbalanced sampled-softmax for tackling the long-tail distribution of predicates, refer to § 4.3, while Lentity is a negative log likelihood with softmax:
Lentity = E(Vc,c)[−log exp(Vc · Ec)∑
k∈Ven exp(Vc · Ek) ], (2)
where c ∈ Ven is the label of the visual entity feature Vc.

heading: 4.2 SIMPLIFIED PINSAGE
text: Simplified PinSage is adopted to map the knowledge graph into an embedding space for PZSL, see Fig.2 (B). Inspired by PinSage (Ying et al., 2018), the propagation algorithm is divided into three steps: message passing, skip shortcut and normalization. We denote FCW,B ◦ x =Wx+B, and the process of graph propagation is formulated as follows:
zk−1u = 1 |N (u)| ∑
v∈N (u)
ReLU(FCWtk ,Btk ◦ h k−1 v ), (3)
h̃ku = ReLU(FCWck ,Bck ◦ [z k−1 u , h k−1 u ]), (4)
hku = h̃ k u/‖h̃ku‖2, (5)
where Eq. (3), (4) and (5) indicate message passing, skip shortcut and normalization respectively, N (u) in Eq. (3) denotes the neighbor set of u (u also falls into N (u)), [·, ·] in Eq. (4) means “concatenate”, h0u is the initial embedding, and h k u is output of k-th graph propagation layer. For n-layer GCN, FWout,Bout takes h n u as input to get the final embedding E lying in the same space with the visual feature V . Note that the main computation in forward propagation is related to the number of edges (Eq. (3)). It is too computation and space consuming to perform propagation on the whole knowledge graph with about 2.2 billion edges. The graph sampling technology in web-scale recommender system (Ying et al., 2018; Eksombatchai et al., 2018) is introduced as an solution.
On-demand sampling. For generating embeddings of mini-batch categories, we only need to sample a necessary sub-graph as input to GCN (GCNp or GCNen), avoiding propagating on the whole knowledge graph. Take 2-layer GCN as an example. Only first and second-order neighbors are needed to compute the final embedding of the target nodes. Refer to Fig. 2 (B), to get the embedding of u (deep blue), the second layer of GCN needs the embeddings (outputs of the first layer) of neighbors (blue) of u for message passing, i.e., N (u). To get the embeddings of N (u) in the first layer, the neighbors of the node setN (u) are needed (light blue), i.e.,N 2(u). Hence, we only sample a sub-graph containing the node set N (u) ∪ N 2(u). In general, to get final embeddings of nodes batch U for n-layer GCN, only 1st to n-th order neighbors are needed, i.e., ∪ni=1N i(U). Neighbor-limit sampling. Many nodes of the knowledge graph contain a large number of neighbors, which makes computation and space consumption uncontrollable. To further reduce the consumption, we limit the number of neighbors per node to a threshold τ , i.e., randomly sampling τ neighbors. Refer to Fig. 2 (B), the unsampled neighbors (gray) do not contribute to the propagation. For testing, all neighbors are sampled to calculate the final embeddings, and we only need to propagate once to obtain the final semantic embeddings. The experiments in § 5 show that neighbor-limit sampling can be considered as a dropout-like operation for greatly avoiding overfitting.
Thus, to obtain embedding of k predicates from n-layer GCN, the number of edges are not greater than a relaxed upper bound kτn, where k, τ ≤ 100 and n ≤ 3. Thus we have kτn ≤ 108 2.2× 1010.

heading: 4.3 UNBALANCED SAMPLED-SOFTMAX
text: A variant softmax function is proposed to measure the similarity between visual features and semantic embeddings, inspired by sampled softmax (Jean et al., 2014) in machine translation. For training of predicate recognition, if all elements of training vocabulary are sampled as negative embeddings, such as standard softmax, the visual features may always match the few most frequent predicate embeddings since the long-tail distribution of the predicates in the dataset. The impact of this distribution on zero-shot learning is devastating. To tackle this problem, we propose an unbalanced sampled-softmax (USS):
Si = exp(Vp · Ei)∑
k∈Bn exp(Vp · Ek) ,Bn ∼ Ppred, (6)
where Vp is the visual feature whose predicate category is p, Ei is the corresponding semantic embedding of predicate i. Unlike sampled softmax that adopts the pre-divided sub-vocabulary as negative categories, the negative predicates Bn ⊂ Vtr is sampled from the predicate distribution
Ppred. It is possible that Bn includes the GT predicate p. Finally, the loss function of predicate recognition is in the form of
Lpredicate = E(Vp,p)[−log(Sp)]. (7)
The sampling method is vital for Eq. (7). The uniform sampling, degrading into an estimated version of softmax, does not help with long-tail distribution. We design a sampling method to ensure the recognition of predicates with fewer samples so that the model can be further generalized to recognize unseen predicate categories. The idea is that the fewer categories appear as positive categories, the less they are sampled as negative categories. We adopt the frequency of predicates as the probability Ppred to sample the negative predicates, see Fig. 2 (C). This sampling method handles the long-tail distribution problem by adjusting the gradient of the infrequent predicates.
Let hi = V · Ei, the gradient of Sp w.r.t hi is discussed as follows:
∂Sp ∂hi = { Sp(1(p = i)− Si) if i ∈ Bn 1(p = i)Si if i /∈ Bn.
(8)
Frequent predicates often fall into the first case in Eq. (8), which is the same as standard softmax. To the opposite, infrequent predicates always fall into the second case that the reward is increased when it is GT (p = i) and that there is no punishment when it is a negative predicate (p 6= i).

heading: 5 EXPERIMENTS
text: In this section, we start by discussing the datasets, knowledge graph, and implementation details. We then perform the ablation studies to verify the components of our model and visualize our results.
VG-zero dataset. We introduce a new dataset based on the latest released Visual Genome dataset (VG v1.4) (Krishna et al., 2017) which contains 108,077 images with 21 relationships (triplets) on average per image. We manually cleaned up the box annotations in the same way with Xu et al. (2017). Since the original annotation is noisy, 1155 synsets in WordNet are used to replace the original predicate categories as regularization, where the correspondence between the original categories and synsets is provided in the VG dataset. About 10% of predicates (105 predicates) are selected as test vocabulary. The frequency of the selected predicates falls in a range from 10 to 300, where the lower bound 10 is set to guarantee the quality of test set for the infrequent labels are noisy, and the upper bound 300 follows the rule that categories in test set should be least populated or rare (Xian et al., 2017) in zero-shot learning. Images annotated with predicates in test vocabulary are selected as the test set (containing 4350 images). We then randomly select 5000 images as the validation set with the rest as the training set. Similar to predicates, the entity categories are also replaced by 7k+ synsets. In addition, we use hypernym relationships to cluster entity categories into 96 categories since the entity synsets are still so specific that include numerous names and object recognition is not our focus. For example, categories like woman, father are clustered into the person category.
Knowledge graph. The knowledge graph G(V, E) is built from WordNet (Miller, 1992), where V and E are nodes set and edges set respectively. Synsets (synonym set) in WordNet are nodes in G. Edge 〈u, v〉 is added into E if u and v have one of the following relationships: hypernym, hyponym, part meronym, part holonym, substance meronym, substance holonym, entailment, substance holonym and sharing lemmas. Notice that the self-loop will be included by the “sharing lemmas” relationship. Finally, the resulted knowledge graph contains 101,260 nodes and about 2.2 billion edges.
Implementation details. For all experiments, the model is trained for 150k iterations with batch size set to 4. We set the learning rate as 2e−3 and is reduced by 0.1 times at the 100k and 130k, respectively. We adopt the warmup strategy (Goyal et al., 2017) at the beginning. ResNet50 (He et al., 2016) is used as a backbone network with weights pre-trained on COCO (Lin et al., 2014), which is fixed during training. Images are resized such that their short edge is 800 pixels. For the knowledge graph, we use the definitions of synsets as the input of off-the-shelf language models to generate the initial embeddings. More specifically, we use the word (GloVe) and sentence (InferSent (Conneau et al., 2017)) embedding methods to get the initial embeddings. For the word embedding method, we take every word of the definition as a token to GloVe and average all the word embeddings to get the 300-D embedding. For the sentence embedding method, the whole definition is used as the input of InferSent to get the 4096-D embedding. The common space and hidden features in GCN are 512-D.

heading: 5.1 ABLATION STUDY
text: We evaluate methods with Hit@k on generalized and traditional setting (Tab. 1 and 2 ): Given any test region pair, we check whether the GT label falls within predicted categories with top k score. If yes, the sample is counted as a Hit. The Hit@k is #Hit#Test region pair . The methods are only required to Hit the unseen predicates ignoring the subjects and objects in Tab 1, while they are required to Hit the full relationship triplets in Tab 2. For the generalized setting, the methods search on the seen and unseen predicates vocabulary Vtr ∪ Vte for inferrence. For the traditional setting, the methods only search on the unseen predicates vocabulary Vte. Note that the generalized setting is more challenging since the search space of the generalized setting is significantly larger than that of the traditional one. Observing Tab. 1 and 2, we can draw the following conclusions.
Knowledge graph prior is critical to our algorithm. As shown in the first row of the Tab. 1, a simple 2-layer MLP for semantic embedding, which neglects the relationship of predicates, cannot identify the unseen predicates in the generalized setting (0 accuracies) and can only obtain a lower recognition rate on the traditional setting. An 1-layer GCN that simply considers node relationships can already deliver significant performance gains (row 2 of Tab. 1), with a large margin (10.6 (%)) on Hit@20 traditional setting. The results show that by modeling the explicit connection between predicates, the knowledge can be effectively transferred from seen categories to unseen ones, which results in a performance boost on the unseen predicate. The same conclusion can be obtained from Tab. 2.
The unbalanced sampled-softmax effectively tackles the long-tail distribution problem. Refer to row 5 in Tab. 1, adopting the softmax loss function results in the worst performance since the outputs collapse into few frequent predicates and could not be generalized to novel predicates. By contrast, adopting the frequency of predicates as sampling probability has obvious advantages with a 15.7 (%) increase on Hit@20 traditional setting (comparing row 3 and 5 in Tab. 1). The same conclusion can be made by comparing row 2 and 3 in Tab. 2.
The number of negative categories should be moderate (row 3 and 6∼9). Note that the larger |Bn|, the higher probability that the infrequent predicates fall into Bn, e.g., if |Bn| = |Vtr ∪ Vte|, the USS degenerates to softmax. When |Bn| < 100, the performance of models with different |Bn| become similar, while setting with |Bn| = 20 approach the best accuracy (49.5 (%) on Hit@20 traditional setting). However, the performance of the version with |Bn| = 100 drops significantly (46.2 (%)). Embedding initialization is necessary, but the impact of different embedding methods on performance is minor. Refer to row 14 in Tab.1, we adopt noise following normal distribution to initialize node embeddings, whose results are almost the same as random guessing (row 16). The initial embedding method clusters the semantically similar categories, which implicitly connects seen and unseen categories. These implicit connections are helpful for zero-shot learning. While using different embedding methods results in little difference: the InferSent method enjoys advantages over the GloVe method on the traditional setting with Hit@5∼20 but with no advantage in other evaluations. The numbers of neighbors and layers result in negligible performance. For traditional setting, observing row 10∼13 in Tab. 1, the impact of τ is limited. Similarly, GCNs with different layers achieve almost equal accuracies, refer to row 2∼4. For the generalized setting, row 4 (3-layer GCN) and 13 (with 100 neighbors) achieve relatively low accuracy, reducing 2.9 (%) on Hit@20 generalized setting. It can be interpreted that a large number of training parameters and complete neighborhood information in the knowledge module make the model overfit the training vocabulary.

heading: 5.2 QUALITATIVE RESULTS
text: Fig.3 shows the results of our method, where output is in the form of <subject, predicate, object>. The recognition of predicates includes generalized and traditional settings shown at row 1 and 2 (blue/yellow font represent correct/wrong), while the ground truth triplets are displayed in the last row. The case a is completely correct in both settings. In case b, our method makes a mistake in the generalized setting while the result of the recognition (swing.v.01) is close to the ground truth (slug.v.01). This case shows that predicate zero-shot learning in the generalized setting is hard for semantically similar categories across training and test vocabularies. The case c is so confusing that even humans can make misjudgment. In case d, our method determines the predicate as chew.v.01 and outputs a more appropriate answer than the ground truth on the recognition of the object. In conclusion, the predicate zero-shot learning is challenging, but our method is effective.

heading: 6 CONCLUSIONS & FUTURE WORK
text: In this work, we define a predicate zero-shot learning problem and propose a solution by mapping visual features and semantic embeddings (in knowledge graph) into the common space. Furthermore, graph sampling strategies are introduced for accelerating graph propagation, and an unbalanced sampled-softmax is proposed for tackling the long-tail distribution. Finally, we plan to explore the following future work for this problem. a) Consistency of differences of visual feature and semantic embedding space can be considered to model the cross-modal analogy. b) A semantic-aware negative sampling of predicate categories is a solution worth exploring. c) Learning the visual predicate as a translation vector (Bordes et al., 2013; Wang et al., 2014; Lin et al., 2015) from subject to object such as VtransE (Zhang et al., 2017) deserve attempted.

Review summaries:
This paper creates a new task for zero-shot learning of predicates (specifically in cases where the individual predicate components have never been seen in the training, rather than the more traditional setting where the full s-v-o relationship is unseen but each component is).  They create a new subset of the Visual Genome dataset specifically targeted towards predicting unseen predicates.  They also provide results using a knowledge graph (in this case WordNet), to integrate linguistic and visual features for prediction.  Interestingly, their pipeline introduces a new softmax variant, the unbalanced sampled softmax, which addresses the problem of over-predicting common predicates.