Learning of Visual Relations: The Devil is in the Tails

Several works have addressed the generation of scene graphs for images [46, 42, 47, 14, 38, 41, 48, 43, 25, 9, 3, 32, 17, 49, 7]. Most approaches focus on either sophisticated architecture design or contextual feature fusion strategies, such as message passing and recurrent neural networks [48, 32], to optimize SGG performance on the Visual Genome dataset [22] under the Recall@K metric. While these approaches achieved gains for highly populated classes, underrepresented classes tend to have much poorer performance. Recently, [3, 31, 42, 37, 23] started to address the learning bias induced by the dataset statistics, by using a more suitable evaluation metric, mRecall@K, which averages recall values across classes. To address the dataset bias, TDE [31] employed causal inference in the prediction stage , whereas [37] used a pseudo-siamese network to extract balanced visual features, and PCPL [42] harnessed implicit correlations among predicate classes and used a complex graph encoding module consisting of a number of stacked encoders and attention heads. A concurrent work [23] introduces confidence-based gating with bi-level data resampling to mitigate the training bias. These methods considered, at most, the long-tailed distribution of either predicates or entities and do not disentangle the gains of sampling from those of complex architectures. For example, [42] proposed a contextual feature generator via graph encoding with 6 stacked encoders, each with 12 attention heads and a feed-forward network. We argue that long-tailed distributions should be considered for both entities and predicates and show that, when this is done, better results can be achieved with a much simpler architecture.

Prior work addresses the long-tailed issue in 3 directions: data re-sampling, cost-sensitive loss and transfer learning.

Data resampling [12, 10, 51, 11, 8, 2] is a popular strategy to oversample tail (underrepresented) classes and undersample head (populated) classes. Oversampling is achieved either by duplicating samples or by synthesizing data [10, 51, 2]. While producing a more uniform training distribution, recent works [21, 50] argue that this strategy is unsuitable for deep representation learning like CNN. [21] decouples the representation learning from the classifier learning, adopting different sampling strategies in the two stages, whereas [50] proposes a two-stream model with a mixed sampling strategy. The proposed method lies in this direction, since we consider different distributions of entity and predicate classes, and adopt different sampling strategies for training different model components.

Cost-sensitive losses [6, 5, 1, 27] assign different costs to the incorrect prediction of different samples, according to class frequency [5, 1] or difficulty [6, 27]. This is implemented by assigning higher weights or enforcing larger margins for classes with fewer samples. Weights can be proportional to inverse class frequency or effective number [5] and can be estimated by meta-learning [18]. This re-weighting strategy was recently applied to the scene graph literature [42] to overcome long-tailed distributions.

Transfer learning methods transfer information from head to tail classes. [35, 36] learns to predict few-shot model parameters from many-shot model parameters, and  [28] proposes a meta-memory for knowledge sharing. [39] leverages a hierarchical classifier to share knowledge among classes. [40] learn an expert model for each class popularity, and combine them by knowledge distillation.

The inference of the visual relationships in a scene is usually formulated as a three stage process. The objects/entities in the scene are detected, classified, and the relationships between each pair of entities, in the form of predicates, are finally inferred. [20] formulated these stages with a Scene Graph. Let $C$ and $P$ be the set of entity and predicate classes, respectively. Each entity $e=(e^{b},e^{c})\in\mathcal{E}$ is composed by a bounding box $e^{b}\in\mathbb{R}^{4}$ and a class label $e^{c}\in C$. A relation $r=(s,p,o)$ is a three-tuple, connecting a subject $s$ and an object $o$ identities ($s,o\in\mathcal{E}$), through a predicate $p\in P$. For example, person-riding-bike. The scene graph $G=(E,R)$ of an image $I$ contains a set of entities $E=\{e_{i}\}_{i=1}^{m}$ and a set of relations $R=\{r_{j}\}_{j=1}^{n}$ extracted from the image. This can be further decomposed into a set of bounding boxes $B=\{e^{b}_{i}\}_{i=1}^{m}$, a set of class labels $Y=\{e^{c}_{i}\}_{i=1}^{m}$, and a set of relations $R$.

The generation of a scene graph $G$ from an image $I$ is naturally mapped into the probabilistic model

where $Pr(B|I)$ is a bounding box prediction model, $Pr(Y|B,I)$ an entity class model and $Pr(R|B,Y,I)$ is a predicate class model. Joint inference of the three tasks is referred to as Scene Graph Detection (SGDet). However, because bounding box prediction has been widely studied in object detection [30], it is possible to simply adopt an off-the-shelf detector. This motivates two other tasks: Predicate classification (PredCls), where both bounding boxes and entity classes are given, and Scene Graph Classification (SGCls), where only bounding boxes are known.

Long-tailed distributions are a staple of the natural world, where different classes occur with very different frequencies. For example, while some entity classes (e.g. chair) occur very frequently, others (e.g donkey) are much less frequent. Long tails are problematic because, under standard loss functions and evaluation metrics, they encourage machine learning systems to overfit on a few head classes and ignore a large number of tail classes. Recent works [28, 5, 50, 21] have shown that sampling techniques which de-emphasize popular classes, giving more weight to rare ones, can induce very large recognition gains when distributions are long-tailed. However, the issue has not been thoroughly considered in the visual relations literature.

This is somewhat surprising, given the combinatorial dependence of visual relationships on entities and predicates. Since entities are long-tailed, relationships between pairs of entities have even more skewed distributions. For example, because the entity classes “donkey” and “cliff” are less frequent than “chair” and “leg”, the relation “donkey-on-cliff” is much less frequent than “chair-has-leg”. This, however, is not the only source of skew, since predicates can be rare even when associated entity classes are popular, e.g. playing is much less popular than has. Finally, relationships can be rare even when involving frequent entities and predicates, e.g. the relation “car-has-wheel” is much more likely than “car-has-camera”. For all these reasons, very long tails are unavoidable for visual relations. This is quite visible in the widely used Visual Genome [22] dataset. As shown in Figure 2, both the distribution of entity and predicate classes are long-tailed. For entities, the most populated class is ${35\times}$ larger than the least populated. For predicates, the former is ${12,000\times}$ larger than the latter (${5,000\times}$ if the least frequent predicate class is discarded). Note that this is much larger than the square of the ratio between entity classes ($1,225$) suggested by the factorial nature of relationships.

The long-tailed problem is exacerbated by the evaluation protocol, based on the Recall@K (R@K) measure, adopted in most of the scene graphs literature. This measures the average percentage of ground truth relation triplets that appear in the top $K$ predictions and, like any average, is dominated by the most frequent relationship classes. Hence, it does not penalize solutions that simply ignore infrequent relationship classes. Since most works, e.g. [32, 7, 3], focus on designing ever more complex network architectures to optimize R@K performance, it is unclear whether all that is being accomplished is stronger overfitting to a few dominant classes (e.g. “on”). This is undesirable for two reasons. First, the number of infrequent relations is much larger than that of dominant relationships. Second, while dominant relations include many obvious contextual relationships (e.g.“car-has-wheels”), infrequent ones are potentially more informative (e.g. “monkey-playing-ball”) of the scene content. In summary, the focus on optimizing R@K could lead to systems that are only capable of detecting a few relationships of relatively low information content.

This problem has been recognized in the recent literature, where some works [3, 31] have started to adopt the mRecall@K (mR@K) metric, which first averages the recall of triplets within the same predicate class and then averages the class recalls over all the predicate classes. While this is a step in the right direction, it is not sufficient to account for class imbalance only at the evaluation stage. Instead, the learning algorithm should explicitly address this imbalance. This leads to an alternative hypothesis that we explore in this work: Is the devil in the tails? Or, in other words, can a simple model designed explicitly to cope with the long-tailed nature of visual relations outperform existing models, which are much more complex but ignore this property? To investigate this hypothesis, we introduce a solution that uses a model much simpler than recently proposed architectures, but is much more sophisticated in its use of sampling techniques that target the long-tailed nature of visual relationship.

For a relation tuple $r_{j}=(s_{j},p_{j},o_{j})$ in image $I$, $p_{j}$ is the ground truth predicate class, while $s_{j}=(s_{j}^{b},s_{j}^{c})$ and $o_{j}=(o_{j}^{b},o_{j}^{c})$ are the subject and object entities, composed of its associated bounding box coordinates (e.g. $s_{j}^{b}$) and ground truth entity class (e.g. $s_{j}^{c}$). The bounding boxes of an entity can be either the ground truth coordinates or the predictions from a detection model, depending on the task of interest (i.e. SGCls or SGDet). With the bounding boxes, the corresponding image patch $I_{j}^{s}$ and $I_{j}^{o}$ for the subject and object can be cropped from the image $I$.

In addition, we define $\rho$ as a probability vector at the output of the softmax function with temperature $\tau$, and its $i^{th}$ entry is formulated as

where $f\in\mathcal{R}^{d}$ is a feature vector, ${\bf W}\in\mathcal{R}^{d\times k}$ is the matrix of $k$ weight parameters $\mathbf{w}_{k}\in\mathcal{R}^{d}$.

Figure 3 summarizes the architecture of the Decoupled Training for Devil in the Tails (DT2) model. This combines an entity encoder $F$, as shown in the right part of Figure 3, and a predicate classifier $H$. DT2 takes the bounding box coordinates $s_{j}^{b}$, $o_{j}^{b}$ [4] and the corresponding cropped image patches $I_{j}^{s}$ and $I_{j}^{o}$ as input. The entity encoder $F$ is then applied to both $I_{j}^{s}$ and $I_{j}^{o}$, to extract a pair of subject-object feature vectors $f_{s}^{\{a,s\}},f_{o}^{\{a,s\}}$ that represent both the appearance and semantics of entities $s_{j}$ and $o_{j}$. These are then concatenated with an embedding of the bounding box coordinates $s_{j}^{b}$ and $o_{j}^{b}$, and fed to a predicate classifier $H$. Implementation details of the entity encoder and the predicate classifier are elaborated below.

Entity encoder $F$ first maps image patch $I^{e}$ of entity $e$ through a feature extractor, implemented with the first three convolutional blocks of a pretrained ResNet101 [13]. We use a faster R-CNN pre-trained for object detection on Visual Genome under regular sampling (all images are sampled uniformly). The resulting feature vector $f_{e}$ is then mapped to two feature vectors, $f_{e}^{s}$ and $f_{e}^{a}$, that encode semantics and appearance information respectively, through two different branches sharing identical architecture. The semantic branch $F^{s}(\cdot;\theta)$ of parameter $\theta$ is implemented with a stack of convolution layers (the last convolutional block of ResNet101). Its output is then fed to a softmax layer that predicts the probability $\bar{e}^{c}\in[0,1]^{C}$ of the class of the entity $e$, i.e.

where ${\bf W}^{e}$ is the matrix of the entity classifier weights and $\tau$ of $\rho$ in (2) is set to 1. The one-hot encoding $\hat{e}^{c}$ can be generated by taking the argmax of $\bar{e}^{c}$, which is then mapped into a semantic feature vector $f_{e}^{s}\in\mathbb{R}^{128}$ with a single fully connected layer.

While the semantic branch would be, in principle, sufficient to convey the entity identity to the remainder of the network, this does not suffice to infer visual relationships. For example, the detection of the “people” and “bike” entities in Figure 3 is not enough to infer whether the relationship is “person-standing by-bike” or “person-riding-bike”. This problem is addressed by introducing the appearance branch $F^{a}(\cdot;\phi)$ of parameter $\phi$, which outputs a feature vector $f_{e}^{a}\in\mathbb{R}^{128}$ with no pre-defined semantics, simply encoding entity appearance. Finally, the feature vectors $f_{e}^{a}$ and $f_{e}^{s}$ are concatenated into a vector $f_{e}^{\{a,s\}}\in\mathbb{R}^{256}$ that represents both the appearance and semantics of entity $e$.

Predicate classifier takes the subject $f_{s}^{\{a,s\}}$ and object $f_{o}^{\{a,s\}}$ feature vectors as input. These vectors are then concatenated with an embedding of subject $s^{b}$ and object $o^{b}$ bounding boxes produced by a fully-connected layer, to create a joint encoding $f_{\{s,o\}}^{\{a,s,b\}}\in\mathbb{R}^{520}$ of the semantics, appearance, and location of the subject-object patches $I^{s}$ and $I^{o}$. The predicate classifier $H$ is implemented with a small feature extractor $H(.,\psi)$, consisting of three layers that perform dimension reduction. The input $f_{\{s,o\}}^{\{a,s,b\}}\in\mathbb{R}^{520}$ is first transformed into a $256$-dimension vector with a fully connected layer, followed by a batch normalization and a ReLU layer, the output of which is finally passed through a fully connected layer with a tanh non-linearity, to produce a final feature vector $f_{s,o}\in\mathbb{R}^{128}$. This is fed to a softmax layer to produce the probability of the predicate class

where ${\bf W}^{p}$ is the weight matrix of the predicate classifier.

DT2 is trained with standard cross-entropy losses targeted on entity and predicate classification. The former is defined as

where $L_{ce}$ denotes the cross-entropy loss, $\bar{e}_{k}^{c}$ is the output probability prediction of (3) and $e_{k}^{c}$ is the ground truth one-hot code of the $k^{th}$ entity in the set $E_{i}$ from image $I_{i}$. This is complemented by a predicate classification loss

where $\bar{p}_{k}$ is the output probability of (4) and $p_{k}$ the ground truth one-hot code for the $k^{th}$ predicate in the set $R_{i}$ of visual relations in image $I_{i}$. Both (5) and (6) are important to guarantee that the network can learn from both entities and predicate relationships.

While encapsulating both semantics and appearance information, the proposed training loss in Sec. 4.3 requires a complementary sampling strategy tailored for long-tailed data. This long-tailed problem has been studied mostly in the object recognition literature, where an image patch is fed to a feature extractor with the parameter $\varphi$ and the softmax layer $\rho$ of (2) with weight matrix ${\bf W}$. A popular training strategy is to use different sampling strategies to train the two network components [21]. The intuition is that, because the bulk of the network parameters are in the feature extractor ($\varphi$), this should be learned with the largest possible amount of data. Hence, the entire network is first trained with Standard Random Sampling (SRS), which samples images uniformly, independent of their class labels.

While this produces a good feature extractor, the resulting classifier usually overfits to the head classes, which are represented by many more images and have a larger weight on the cost function. The problem is addressed by fine-tuning the network on a balanced distribution, obtained with Class Balanced Sampling (CBS). This consists of sampling uniformly over classes, rather than images, and guarantees that all classes are represented with equal frequencies. However, because images from tail classes are resampled more frequently than those of head classes, it carries some risk of overfitting to the former. To avoid overfitting, the fine-tuning is restricted to the weights $\bf W$ of the softmax layer. In summary, the network is trained in two stages. First, the parameters $\varphi$ and $\bf W$ are jointly learned with SRS. Second, the feature extractor ($\varphi$) is fixed and the softmax layer parameters $\bf W$ are relearned with CBS.

Similar to long-tailed object recognition, it is sensible to train a model for visual relations in two stages. In the first stage, the goal is to learn the parameters $\theta,\phi,\psi$ of the feature extractors (see Sec. 4.2), which are the overwhelming majority of the network parameters. As in object recognition, the network should be trained with SRS. In the second stage, the goal is to fine-tune the softmax parameters ${\bf W}^{e}$ and ${\bf W}^{p}$ to avoid overfitting to head classes. However, unlike long-tailed object recognition, Figure 2 shows that predicates and entities can have very different distributions, which makes the learning of long-tailed visual relations a distinct problem. This indicates that two class-balanced sampling strategies are required to accommodate the distribution difference between predicate and entity classes.

A straightforward solution is to introduce a 2-step iterative training procedure, namely entity-optimization step (E-step) and predicate-optimization step (P-step), to optimize the weight of ${\bf W}^{e}$ and ${\bf W}^{p}$ respectively. In E-step, images are sampled from a distribution ${\cal P}_{e}$ that is uniform with respect to entity classes, which is denoted as Entity-CBS. While in P-step, they are sampled from a distribution ${\cal P}_{p}$ uniform with respect to predicate classes, denoted as Predicate-CBS. However, since the uniform sampling of ${\cal P}_{p}$ is not class-balanced for entity classes, P-step would lead to the overfitting of the entity classification parameters ${\bf W}^{e}$.

To address this problem, we propose a novel sampling strategy, Alternating CBS (ACBS), tailored for long-tailed visual relations. ACBS contains a memory mechanism to maintain the entity predictions of the P-step, making sure that what was learned is not forgotten in the E-step. It is implemented with distillation [15] between the P-step and E-step and an auxiliary teacher entity classifier of weight matrix ${\bf W}^{t}$. The teacher entity classifier is inserted in parallel with the entity classifier of weight matrix ${\bf W}^{e}$ in (3), which is its student, and produces a second set of entity prediction probabilities as

With the introduction of the teacher entity classifier, we rewrite (5) into $L_{ent}^{stu}$ and $L_{ent}^{tea}$, where the former operates on $\bar{e}^{c}$ of (3) and the latter operates on $\bar{e}^{t}$. Furthermore, to distill knowledge from the teacher entity classifier, a Kullback-Leibler divergence (KL) loss ($L_{kd}$) is defined as

where the two inputs to $L_{kd}$ are the smooth version of (3) and (7) with temperature $\tau_{s}$.

In summary, the P-step updates parameters ${\bf W}^{p}$ of the predicate classifier and ${\bf W}^{t}$ of the teacher with (6) and $L_{ent}^{tea}$ respectively, while the student parameters ${\bf W}^{e}$ are kept fixed. In the E-step, ${\bf W}^{p}$ and ${\bf W}^{t}$ (teacher) are kept fixed, and ${\bf W}^{e}$ (student) is optimized with $L_{ent}^{stu}$ and (8). This implements learning without forgetting [26] between the two steps, encouraging the student classifier to mimic the predictions of the teacher classifier, and enabling the network to learn the new parameters for one distribution, e.g. ${\bf W}^{e}$, without forgetting the one, e.g. ${\bf W}^{t}$, previously learned for the other. The training procedure is detailed in Algorithm 1.

Visual Genome (VG) [22] is composed of 108k images across 75k object categories and 37k predicate categories, but $92\%$ of the predicates have less than 10 instances. Following prior works, we use the original splits of the popular subset (i.e. VG150) for training and evaluation. It contains the most frequent 150 object classes and 50 predicate classes. The distribution remains highly long-tailed. To perform balanced sampling during training, predicate classes with less than 5 instances, e.g. “flying in,” are ignored.

To validate our hypothesis, we compare DT2-ACBS with the state-of-the-art methods on PredCls, SGCls and SGDet task on the popular subset VG150 of VG [22], under the mRecall@K metric. As shown in Table 1, compared baselines include 1) simple frequency-based method [48], 2) sophisticated architecture design for contextual representation learning [41, 3, 32, 46] and 3) recent works that tackle the long-tailed bias of predicate classes [31, 42]. Several observations can be made. First, DT2-ACBS outperforms all baselines in the first two groups by a large margin (mR@100 gain larger than $15.7\%$) on the PredCls task, where entity bounding boxes and categories are given. The baselines in the third group [31, 42], which address the long-tailed bias of the predicate distribution, are similar in spirit to DT2-ACBS. However, the latter relies on a simpler model design and a more sophisticated decoupled training scheme to overcome overfitting. This enables a $1.9\%$ improvement on mR@100 ($5\%$ relative improvement), showing the efficacy of the proposed sampling mechanism for tackling the long-tailed problem in predicates distribution.

Next, when predicting both predicate and entity class given the ground truth bounding boxes (SGCls task), DT2-ACBS outperforms all existing methods by a larger mR@100 margin ($1.9\%$ on PredCls vs $7.9\%$ on SGCls, equivalently relative improvement of 5% in PredCls vs 40% in SGCls). This significant improvement in SGCls performance can be ascribed to the decoupled training of ACBS, which better captures the interplay between the different distributions of entities and predicates.

Finally, we also ran DT2-ACBS on proposal boxes generated by a pre-trained Faster-RCNN for the SGDet task.Table 1 shows that DT2-ACBS outperforms existing methods by a significantly larger mR@100 margin of $12.7\%$ ($>100\%$ relative improvement) on the SGDet task.

SGCls performance is affected by the intertwined entity and predicate distributions. In this section, we conduct ablation studies in Table 3 on 1) single-stage vs two-stage training and 2) different sampling schemes. The first half of the table shows the performances of single-stage training, where the representation and the classifier are learned together. This clearly under-performs the two-stage training, which is listed in the second half of the table, where we compare different sampling strategies in the second stage of DT2. For the predicate classifier, it can be trained based on either SRS or class-balanced sampling for predicates (Predicate-CBS). Since each relation comes with a subject and an object, it is possible to train the entity classifier with respect to Predicate-CBS, indicating the entity classifier can be trained based on SRS, Predicate-CBS or class-balanced sampling for entities (Entity-CBS). Note that the predicate classifier can not be trained with Entity-CBS, since an entity does not always belong to a visual relation tuple. From the second half of the table, we find that considering the distribution differences in predicates and entities is important, because DT2-Predicate CBS (i.e. Predicate-CBS for both entity and predicate classifier) does not perform as well as DT2-Indep. CBS (i.e. Entity-CBS for the entity classifier and Predicate-CBS for the predicate classifier). The observation that DT2-Indep. CBS already performs better than existing methods (Table 1) supports our claim that visual relations can be effectively modeled with a simple architecture if the long-tailed aspect of the problem is considered. Nevertheless, the proposed ACBS further improves the SGCls performance by distilling the knowledge between P-step and E-step (see Algorithm 1).

Figure 6 presents qualitative results of DT2-ACBS. In PredCls task, DT2-ACBS can correctly predict populated predicate classes (has & wearing) as well as non-populated predicate classes (walking on). Not only robust to long-tailed predicate classes, DT2-ACBS is also able to classify entities ranging from more populated classes (boy) to tail classes (sneaker). We can observe that while the predicted predicates can be different from the ground truth, the relation can still be reasonable (e.g. a subclass or a synonym of the ground truth). For example, the predicted predicate “walking on” is actually a subclass of the ground truth predicate “on”. These examples show that DT2-ACBS is able to predict more fine-grained predicates in tail classes and provide more exciting descriptions of the scene.