Multi-Label Zero-Shot Learning with Structured Knowledge Graphs

Introduction

Real-world machine learning applications such as image annotation, music categorization, or medical diagnosis require assigning more than one class label to each input instance. Take image annotation for example, the learning models have to predict multiple labels like sky, sea, or ship for a single input image. Different from traditional multi-class methods which only predict one class label for each instance, learning multi-label classification models typically require additional efforts. More specifically, we not only need to relate the images with their multiple labels, it is often desirable to exploit label correlation due to the co-occurrences of the labels of interest.

In general, binary relevance is the simplest solution to multi-label classification problems, which coverts the original task to multiple disjoint binary classification problems. However, it lacks the ability to model label co-occurrences, and thus might not be preferable. Approaches such as take cross-label correlation by assuming label priors, while label-embedding based methods project both input images and their labels onto a latent space to exploit label correlation. Methods that utilize deep neural networks have also been proposed. BP-MLL first proposed a loss function for modeling the dependency across labels, while other recent works proposed different loss functions or architectures to further improve performance.

Extending from multi-label classification, multi-label zero-shot learning (ML-ZSL) is a branch of zero-shot learning (ZSL), which require the prediction of unseen labels which are not defined during training. Traditional multi-label approaches such as binary relevance or label-prior based methods obviously cannot be directly applied to ML-ZSL, since such methods lack the ability to generalize to unseen class labels. In contrast, approaches that utilize label representations in the semantic space such as label-embedding methods can be more easily adapted to ML-ZSL, given label representations of the unseen classes. Generally, label representations are obtained from human-annotated attribute vectors that describe the labels of interest either in a specific domain, or via distributed word embeddings learned from linguistic resources.

Nevertheless, although recent ML-ZSL methods such as have been proposed, existing approaches typically do not take advantages of structured knowledge and reasoning. Humans recognize objects not only by appearance, but also by using knowledge of the world learned through experience. Inspired by the above observation, we focus on leveraging existing structural knowledge for ML-ZSL, with the goal of deriving proper dependencies between different label concepts for both seen and unseen ones. Figure 1 illustrates how knowledge graphs can help in this problem, where we can model the co-occurring and non-co-occurring concepts and extend this knowledge to unseen classes with an external structured knowledge graph. There has been work on multi-label problems utilizing structured knowledge. introduced a graph representation that enforces certain relations between label concepts. employed recurrent neural networks (RNN) to model positive and negative correlations between different concept layers. More recently, extended neural networks for graphs to efficiently learn a model that reasons about different types of relationships between class labels by propagating information in a knowledge graph.

However, to the best of our knowledge, none of existing work advances structured knowledge reasoning for ML-ZSL. In this paper, we propose a novel ML-ZSL approach to observe and incorporate associated structured knowledge. Labels are represented with semantic vectors and an information propagation mechanism is learned from the label relations observed in the semantic space. The propagation of such label relation information is then used to modify the initial beliefs for each class label. Once the propagation process is complete, multi-label classification (or ML-ZSL) can be performed accordingly. Our model incorporates structured knowledge graphs observed from WordNet into an end-to-end learning framework, while learning the label representations and information to be propagated in the semantic space. With this framework, we are able to achieve ZSL by assigning the unseen label embedding vector into our learning model. We will show the effectiveness of our model in advancing the structured knowledge for reasoning, which would benefit the task of ML-ZSL.

The main contributions of this work are highlighted as follows:

To the best of our knowledge, our model is among the first to advance structured information and knowledge graphs for ML-ZSL.

Our method advances a label propagation mechanism in the semantic space, enabling the reasoning of the learned model for predicting unseen labels.

With comparable performance on standard multi-label classification tasks, our method performs favorably against recent models for ML-ZSL.

Related Work

Remarkable developments on image classification has been observed over the past few years due to the availability of large-scale datasets like ImageNet and the development of deep convolutional neural networks .

Among image classification tasks, multi-label classification aims at predicting multiple labels for an input image, whcih can be achieved by the technique of binary relevance using neural networks. To further improve the performance, label co-occurrence and relations between labels are considered in recent works. Label embedding methods are among the popular techniques, which transform labels into embedded label vectors, so that the correlation between labels can be exploited . As non-linear embedding approaches, deep neural networks have also been utilized for multi-label classification .

Another way to determine the dependency between labels is via exploring explicit semantic relations between the labels. The Hierarchy and Exclusion (HEX) graph captures semantic relations: mutual exclusion, overlap and subsumption between any two labels, improving object classification by exploiting the label relations. The model is further extended to allow for soft or probabilistic relations between labels . Later, introduced Structured Inference Neural Network (SINN). Inspired by the idea of Recurrent Neural Network (RNN) , positive correlation and negative correlation between labels are derived for bidirectionally propagating information between concept layers, which further improves the classification performance; Focusing on single-label activity recognition, view both activity of input image and actions of each person in that image as a graph, and utilize RNN to update the observed graph for activity prediction. On the other hand, Graph Neural Networks , present architectures of Graph Gated Neural Networks (GGNN), which apply Gated Recurrent Units (GRU) and allow propagation on the graphs. As a modification of GGNN, Graph Search Neural Network (GSNN) is successfully applied for multi-label image classification to exploit explicit semantic relations in the form of structured knowledge graphs.

Different from multi-label classification, zero-shot learning (ZSL) is a challenging task, which needs to recognize test inputs as unseen categories. ZSL also attracts extensive attention from the vision community , which is typically addressed by relating semantic information like attributes and word vectors to the presence of visual content.

Extended from ZSL, multi-label zero-shot learning (ML-ZSL) further requires one to assign multiple unseen labels for each instance. To solve ML-ZSL tasks, COSTA assumes co-occurrence statistics and estimates classifiers for seen labels by weighted combinations of seen classes. achieves ML-ZSL by exhaustively listing all possible combinations of labels and treating it as a zero-shot classification problem. Recently, considers the separability of relevant and irrelevant tags, proposing a model that learns principal directions for images in the embedding space. Multiple Instance Visual-Semantic Embedding (MIVSE) is another joint embedding method, which uses a region-proposal method to discover meaningful subregions in images and then maps the subregions to their corresponding labels in the semantic embedding space. leverages co-occurrence statistics of seen and unseen labels and learns a graphical model that jointly models the label matrix and the co-occurrence matrix.

Our Proposed Approach

Our approach is illustrated in Figure 2. We take every label as a node with states in our structured knowledge graph. The initial belief states of these nodes $\mathbf{h}_{v}^{(0)}$ are first obtained through the input function $\mathbf{F}_{I}$, and the resulting information is propagated via the structured knowledge graph for updating the belief states. The propagation mechanism from each label node $u$ to a connecting node $v$ is governed by propagation weights $\mathbf{a}_{vu}$, which are produced from the relation function $\mathbf{F}^{k}_{R}$. We note that, this relation function takes the label representations $\mathbf{w}_{u}$ and $\mathbf{w}_{v}$ as inputs, where $k$ denotes the type of relation between nodes $u$ and $v$ as defined in the knowledge graph. The above propagation and interaction process would terminate after $T$ steps, followed by passing through a output function $\mathbf{F}_{O}$ to produce the final classification probabilities. In the following subsections, we will give details of how this model is used for ML-ZSL.

2 Structured Knowledge Graph Propagation in Neural Networks

For each class label node $v\in\mathcal{S}$, the propagation recurrence is as follows:

where $\mathbf{W}$, $\mathbf{U}$, and $\mathbf{b}$ are learned parameters.

For each time step $t$, the confidence for each label node is obtained by the output function $\mathbf{F}_{O}$:

which is implemented by a standard fully-connected neural network. After $T$ time steps for propagation, the final confidences $p_{v}^{(T)}$ would be obtained.

3 Learning of the Propagation Matrix

With the gated update mechanism for updating the belief state of each node in a graph, we now address a critical issue that how our model reasons and combines information from adjacent nodes lies in the matrix $\mathbf{A}_{v}$.

In (2), we see that the update vector $\mathbf{u}_{v}^{(t)}$ is a weighted combination of the belief states of all other nodes by the propagation parameters in $\mathbf{A}_{v}$, with each hidden dimension having its own weights. By constraining $\mathbf{A}_{v}$ to have non-zero weights for the elements that correspond to adjacent nodes and setting weights for non-adjacent nodes to zero, a node would combine information from only relevant nodes that are defined in the structured knowledge graph to obtain the update vector $\mathbf{u}_{v}^{(t)}$ for updating its own belief state.

In GSNN, the structured knowledge graph is defined with around 30 relation types. While the elements in $\mathbf{A}$ are learned, the edges of the same relation type are fixed in GSNN. This might limit its practical uses due to only a few relation types can be determined beforehand. In ML-ZSL, it is desirable to exploit finer relation between labels, so the propagation mechanism with the resulting knowledge graph would be sufficiently informative.

where $\mathbf{w}_{v}$ and $\mathbf{w}_{u}$ are the word vectors for the class label nodes $v$ and $u$. The mechanism for learning propagation weights is illustrated in Figure 3, in which each element of the matrix $\mathbf{a}_{vu}$ is determined by a unique bilinear form from joint embedding of the two associated labels. This allows our model to properly describe relationships between different nodes/relations.

As a final remark, for each edge type $k$, the function $\mathbf{F}_{R}^{k}$ learns a mapping from the semantic word embedding space to the propagation weights, so that the dependency between such relation edges can be modeled accordingly. More importantly, learning from the semantic space allows the aforementioned model to generalize to unseen class labels. Thus, the proposed scheme using relation functions $\mathbf{F}_{R}^{k}$ to determine the propagation weights $\mathbf{a}_{vu}$ would be especially preferable for ML-ZSL.

4 From ML to ML-ZSL

During training, the propagation weight matrix $\mathbf{A}$ can be obtained by forward passing through the relation networks $\mathbf{F}_{R}^{k}$, and is then used for information propagation described in (2) to (7). The loss function of our model is a weighted sum of the binary cross-entropy (BCE) of each label node, after the output of network $\mathbf{F}_{O}$ is observed at each time step. To be more precise, the loss $\mathcal{L}$ is defined as:

where the weights $\alpha(t)=1/(T-t+1)$ encourage accurate predictions as $t$ increases. During the inference stage of multi-label classification, the final confidences $p_{v}^{(T)}$ at time step $T$ are used as the predicted outputs.

Experiments

Before presenting the experimental results, we detail how we built the structured knowledge graph in our model. In our work, we consider WordNet as the source for constructing the knowledge graph, since it is easily accessible and contains rich semantic relationships between different concepts.

We defined $3$ types of label relations for the knowledge graph: super-subordinate, positive correlation, and negative correlation. Super-subordinate correlations, also called hyponymy, hypernomy, or ISA relation, is defined and can be directly extracted from WordNet. For positive and negative relations between class labels, label similarities are calculated by WUP similarity , followed by thresholding the soft similarities into positive and negative correlations. As for label pairs with similarities between the positive and negative thresholds, or pairs without similarities from WUP similarity, they are viewed as not having any direct relation between them.

In addition, if a pair of labels exhibit super-subordinate relation, we directly apply its resulting dependency in our graph and do not further calculate its positive/negative relation. In the following experiments, we fix the propagation steps on the structured knowledge graph to 5 ($T=5$).

2 Datasets and Settings

To evaluate the performance of our model, we consider the following datasets for experiments: NUS-WIDE and Microsoft COCO . For the multi-label classification task we perform experiments on both datasets, while NUS-WIDE is particularly applied for ML-ZSL evaluation.

NUS-WIDE is a web image dataset including 269,648 images and the associated tags from Flickr. For these images, it consists of 1000 noisy labels collected from the web with 81 dedicated ground-truth concepts. We denote these two sets of labels as NUS-1000 and NUS-81, respectively. After collecting all existing images and removing images that do not have any tags, we obtain 90,360 images. We extract 2048-dimensional ResNet-152 feature representations from the images and use them as inputs for the following tasks. We further split the dataset into 75,000 training images, 5,000 validation images and 10,360 test images.

Microsoft COCO (MS-COCO) is a large-scale dataset for object detection, segmentation, and image captioning. We follow the 2014 challenge for data split (i.e., 82783 and 40504 images for training and testing, respectively) with 80 distinct object tags. After removing images without any labels, we split the training set into 78081 training images and 4000 validation images, and the test set is with 40137 images. For all the methods considered in our experiments, we extract and fix 2048-dimensional image features are extracted from ResNet-152.

3 Multi-Label Classification

We fist consider the conventional multi-label classification tasks for evaluating our proposed model. For comparison, we consider WSABIE , WARP , and logistic regression (all with the above CNN features) as baseline approaches. We also implement Fast0Tag to compare against models that are designed to handle multi-label classification problems (and later the ML-ZSL tasks).

For testing, since WSABIE, WARP and Fast0Tag predict labels according to the ranking scores of the tags, we choose the top $K$ labels. Following conventional settings, we report results for $K=3$. As for logistics and our model, every label reports a final confidence for evaluation. Using the validation set, we select a proper probability threshold for predicting labels. Finally, the metrics of precision (P), recall (R) and F1-measure are considered, which are commonly used in previous work.

Table 1 lists and compares the results for the NUS-81 and MS-COCO datasets. We can see that our model produced comparable performances against baselines. It is worth noting that, since our model is not explicitly designed for solving multi-label but zero-shot learning, the above results sufficiently support the use of our model for multi-label classification. In addition, compared to Fast0Tag, which is designed for ML-ZSL and can also be used in the conventional multi-label setting, our model clearly achieved improved results on both datasets.

We also note that, although Fast0Tag reported higher scores on the recalls on NUS-81, it was not able to produce satisfactory results on the precisions. The discrepancy between precision and recall can also be observed from the results in . Similar remarks can be made for both WSABIE and WARP baselines. A possible explanation is that the number of tags in an image varies across the dataset, and thus simply choosing the top $K$ prediction in terms of ranking scores for every image would not be sufficiently informative. In contrast, logistics and our method applied a more flexible prediction method and were able to achieve more balanced results on precisions and recalls for both datasets.

4 ML-ZSL and Generalized ML-ZSL

We now report our empirical results on multi-label zero-shot learning (ML-ZSL) using the NUS-WIDE dataset. In order to perform ML-ZSL, we treat labels in NUS-WIDE 81 as the unseen label set $\mathcal{U}$, while the seen label set $\mathcal{S}$ is derived from NUS-1000 with 75 duplicated ones removed and thus results in 925 label classes.

We take Fast0Tag with the same $\mathcal{S}$ and $\mathcal{U}$ as the state-of-the-art ML-ZSL approach for comparisons. We report the results for ML-ZSL with $K=3$ for Fast0Tag. To further verify the effectiveness of the introduced components in our model, we also conduct controlled experiments in which we have a simplified version without updating the belief vectors via the structured knowledge graph (i.e., Ours w/o Prop.). In other words, for Ours w/o Prop., we set $T=0$.

Additionally, we consider the challenging task of generalized ML-ZSL task, for which models are trained on seen labels but are required to predict both seen and unseen labels during testing. The experiments are performed on the NUS-WIDE dataset following the ML-ZSL setting, and we report the results of predictions for the $|\mathcal{S}|+|\mathcal{U}|=1006$ labels. For Fast0Tag under this setting we report $K=10$, as $K=3$ will result in low recall due to a large number of tags predicted for each image.

Table 2 lists the results for both the ML-ZSL setting and the generalized ML-ZSL setting. From this table, we see that our model reported satisfactory performances and performed favorably against Fast0Tag. Also, from the ablation tests, we see that the full version of our model was preferable when applying propagation with the knowledge graph. This confirms the effectiveness of this mechanism introduced in our model.

5 Analysis of Propagation Mechanism

To further evaluate the effectiveness of our method, we visualize the propagation process of our structured knowledge graph in Figure 5, demonstrating how the information transferred in our constructed graph assists in the prediction process. We show the prediction probabilities $p_{v}^{(t)}$ of several label classes from $t=0$ to $t=5$ for the two examples shown in this figure (both are from MS-COCO). These probabilities are obtained from our multi-label classification model. The corresponding knowledge subgraphs are also shown in the figure. From the results, We observe that the first few propagation step affected the prediction probabilities the most, especially for the label nodes that had initial confidence that were closer to the probability threshold. Subsequent propagation steps simply further fine-tuned the probabilities for more accurate predictions.

We also made this similar observation when analyzing the performance of our model at different time steps. We use the probabilities $p_{v}^{(t)}$ at time step $t$ instead of time step $T$ to obtain predictions and measure the performance on the testing sets. The results for multi-label classification on MS-COCO and NUS-81 for $t=1$ to $t=5$ are shown in Figure 6. In Figures 7, we also observe similar trends for generalized ML-ZSL using NUS-WIDE 1000. In other words, both seen and unseen classes gained from such information propagation across labels, and showed the converged results in a few time steps.

Conclusion

In this paper, we proposed a unique deep learning framework to approach multi-label learning and multi-label zero-shot learning (ML-ZSL). By incorporating structured knowledge graphs into the learning process, our model leverages different relations defined in the constructed knowledge graph, which allow the exploitation of label dependencies between labels for ML-ZSL. This is similar to how humans utilize learned concept dependencies when recognizing seen and unseen objects of interest. In our experiments, we showed that our proposed model was able to produce satisfactory performance on the standard task of multi-label classification, and performed favorably against baseline and state-of-the-art approaches on the challenging problem of ML-ZSL.

Acknowledgments This work was supported in part by the Ministry of Science and Technology of Taiwan under grant MOST 107-2634-F-002-010.

References