Year: 2021

Abstract:
We propose a reinforcement learning based approach to query object localization, for which an agent is trained to localize objects of interest specified by a small exemplary set. We learn a transferable reward signal formulated using the exemplary set by ordinal metric learning. Our proposed method enables test-time policy adaptation to new environments where the reward signals are not readily available, and outperforms fine-tuning approaches that are limited to annotated images. In addition, the transferable reward allows repurposing the trained agent from one specific class to another class. Experiments on a corrupted MNIST, the CU-Birds, and the COCO datasets demonstrate the effectiveness of our approach.

text: We propose a reinforcement learning based approach to query object localization, for which an agent is trained to localize objects of interest specified by a small exemplary set. We learn a transferable reward signal formulated using the exemplary set by ordinal metric learning. Our proposed method enables test-time policy adaptation to new environments where the reward signals are not readily available, and outperforms fine-tuning approaches that are limited to annotated images. In addition, the transferable reward allows repurposing the trained agent from one specific class to another class. Experiments on a corrupted MNIST, the CU-Birds, and the COCO datasets demonstrate the effectiveness of our approach.

heading: 1 INTRODUCTION
text: There is increasing interest in designing machine learning models that can be adapted to unseen environments or repurposed for new tasks, with only minimal human guidance (Vinyals et al., 2016; Snell et al., 2017; Finn et al., 2017; Sun et al., 2020; Hansen et al., 2021). To this end, a small set of examples can not only serve the purpose of implicitly generalizing a trained model to a new environment during training time, but also enable the learner to update its learning objectives during test time.
In this paper, we focus on a reinforcement learning (RL) formulation to the problem of query object localization, in which an agent is trained to localize the target object specified by a small set of exemplary images. Instead of using fixed bounding box proposals, our vision-based agent can be viewed as a proactive information gatherer (Guo, 2003), which actively interacts with an image environment; Furthermore, it follows a class-specific localization policy, and thus is more suitable for aerial imagery (Xia et al., 2018), robotic manipulation (Kalashnikov et al., 2018), or embodied AI (Savva et al., 2019) tasks.
During the test time of query object localization, the queried object class to localize may be novel, or the background environment may undergo substantial changes, hindering the applicability of class-agnostic agents with a fixed policy. In addition, in standard RL settings for object localization, the reward signal is often available, so fine-tuning methods (Julian et al., 2020) can effectively adapt agents to new environments and yield improved performance; On the contrary, in query object localization, the reward signal is not available at test time, because the bounding box annotations are to be found by the localization agent on test images.
To address these problems, we propose an ordinal metric learning based framework for learning an implicitly transferable reward signal defined with a small exemplary set. An ordinal embedding network is pre-trained with data augmentation under a loss function designed to be relevant to the RL task. The reward signal allows explicit updates of the controller in the policy network with continual training during test time. Compared to fine-tuning approaches, the agents can get exposed to new environments more extensively with unlimited usage of test images. Informed by the exemplary set precisely, the agent is adapted to the changes of the localization target.
Our contributions in this paper are summarized as follows: (1) We propose a novel ordinal metric learning based RL framework to learn a transferable reward signal defined with a small exemplary set for query object localization; (2) Our RL framework enables test-time policy adaptation to new environments where there is no readily available reward signal; (3) Our learned transferable
reward allows repurposing a trained agent from localizing one specific class to another; (4) Extensive experiments on several datasets demonstrate the effectiveness of our proposed approach.

heading: 2 RELATED WORK

heading: 2.1 OBJECT LOCALIZATION
text: Compared to bounding-box regression approaches (Redmon et al., 2016; Ren et al., 2016), deep RL based object localization approaches (Caicedo & Lazebnik, 2015; Jie et al., 2016) have the advantage of being region-proposal free, with customized search paths for each image environment. The specificity of an agent purely depends on the classes of bounding-boxes used in the reward. They can be made class-specific (Caicedo & Lazebnik, 2015), but the agent for each class would need to be trained separately.
Despite the rise of crowdsourcing platforms, obtaining ample amount of bounding-box annotations remains costly and error-prone. Furthermore, the quality of annotations often varies, and precise annotations for certain object class may require special expertise from annotators. The emergence of weakly supervised object localization (WSOL) (Song et al., 2014; Oquab et al., 2015; Zhou et al., 2016) methods alleviates the situation, in which image class labels are used to derive bounding box annotations. It is known that WSOL methods have drawbacks of overly relying on inter-class discriminative features and failing to generalize to classes unseen during the training phase.
We argue that intra-class similarity is a more natural objective for the problem of localizing objects belonging to a target class. "Query object localization" emphasizes more about the class-specific nature of a localization task, with the relevance defined by the similarity to query images. A similar problem is image co-localization (Tang et al., 2014; Wei et al., 2017), in which the task is to identify the common objects within a set of images. Co-localization approaches exploit the common characteristics across images to localize objects. Being unsupervised, co-localization approaches could suffer from ambiguity if there exist multiple common objects or parts, e.g., bird head and body (Jaderberg et al., 2015), which may provide unwanted common objects as output.

heading: 2.2 POLICY ADAPTATION
text: There seems to be a contradiction between the goals of training an agent with high task-specificity and better generalization performance to new situations at the same time. The key to reconcile these two goals lies in the usage of a small set of examples. There has been a paradigm shift from training static models defined with parameters to ones defined together with a support set (Vinyals et al., 2016; Snell et al., 2017), proved to be very effective in few-shot classification.
Besides the efforts of employing meta learning to adjust models, fine-tuning on a pretrained model (Oquab et al., 2014; Finn et al., 2017; Julian et al., 2020) has also been widely used in transferring knowledge from data-abundant to data-scarce tasks. When reward signal is not available, Hansen et al. (2021) proposed a policy adaptation approach, in which the intermediate representation is fine-tuned via optimizing a self-supervised auxiliary loss while the controller is kept fixed. Our work shares the same motivation of test-time training (Sun et al., 2020), but we focus instead on the settings where the controller needs to be adapted or even repurposed for new tasks.

heading: 3 LEARNING TRANSFERABLE REWARD FOR LOCALIZING QUERY OBJECTS

heading: 3.1 RL FORMULATION FOR QUERY OBJECT LOCALIZATION
text: Given a set of images I with known class labels, the task of query object localization is to find the location b of the bounding box most relevant to the query object, specified in a small set of exemplary images E . Following the Markov Decision Process (MDP) framework for object localization (Caicedo & Lazebnik, 2015; Jie et al., 2016), this task can be formulated as a RL problem. In the training phase, a localization agent learns to take actions of moving the bounding box to maximize a reward function reflecting localization accuracy. In the test phase, the agent is informed by a small test exemplary set about a new task objective. Figure 1 shows an overview of the query object localization problem and the RL formulation, with components listed as follows.
• Environment: Raw pixels of a single image Ii, without candidate proposal boxes. • Action: Discrete actions facilitating a top-down search, including five scaling: scale towards
top left/right, bottom left/right, center; eight translation transformations: move left/right/up/down, enlarge width/height, reduce width/heigh; plus one stay action.
• State: Pooled features from the current box and an internal state within RNN that encodes information from history observations.
• Reward: Improvements the agent made in localizing the query images (in different tasks).

heading: 3.2 PRETRAINING ORDINAL REWARD SIGNAL
text: For training an agent to localize different objects according to queries, the reward function needs to be transferable. Existing deep RL approaches for object localization (Caicedo & Lazebnik, 2015; Jie et al., 2016) use its ground-truth object bounding box gi as the reward signal,
R = sign(IoU(bt, gi)− IoU(bt−1, gi)), (1) where IoU(bt, gi) denotes the Intersection-over-Union (IoU) between the current window bt and the corresponding ground-truth box gi1, and IoU(b, g) = area(b ∩ g)/area(b ∪ g). Similar to the bounding box regression approaches which learns a mapping φ : I 7→ g, the image and box must be paired. However, annotated image-box pairs (I, g) may be scarce in both the training and testing phases. The reward signal defined in Eq. 1 is instance-wise, which is not transferable across images.
To address this problem, a natural idea is to define the reward signal based on learned representations of the cropped images by current window bt and the ground-truth window g. Given their M - dimensional representations bt and g produced by an embedding function f : RD 7→ RM from D- dimensional image feature vectors, a distance function d : RM × RM 7→ [0,+∞) returns the embedding distance d(bt,g). However, an embedding distance based on off-the-shelf pretrained networks is not adequate, since it may not decrease monotonically as the agent approaches to the ground-truth box g. As a result, the embedding distance based reward signal may be less effective than Eq. 1. Therefore, an embedding function customized for the downstream RL-based localization task is needed.
Ordinal metric learning. We propose to use an ordinal embedding based reward signal. For any two perturbed boxes bj , bk from ground truth g, embeddings bj,bk,g are learned, such that the relative preferences between any pair of boxes are preserved in the Euclidean space,
ρj > ρk ⇔ ||bj − g|| < ||bk − g||, ∀j, k ∈ C, (2) where ρj and ρk denote the preference (derived from either IoU to ground-truth box or ordinal feedbacks from user), and C is an ordinal constraint set constructed by sampling box pairs around g. This problem is originally posed as non-metric multidimensional scaling (Agarwal et al., 2007; Jamieson & Nowak, 2011). Although we apply a very simple pairwise-based approach, there exist other extensions such as the listwise-based (Cao et al., 2007), quadruplet-based (Terada & Luxburg, 2014) and landmark-based (Anderton & Aslam, 2019; Ghosh et al., 2019) approaches.
1Notation: bounding box are denoted by lowercase lightface letters, e.g., g, while embedding vectors are denoted by boldface letters, e.g., g ∈ Rd is a d-dimensional vector.
Loss function. In this paper, we define preference ρ as the IoU of box b to the ground-truth box g, i.e., ρ = IoU(b, g). We choose to optimize a triplet loss (Hermans et al., 2017) for learning the desired embeddings,
Ltriplet = ∑
anchor, ordinal pairs
max ( m+ d(a,p)− d(a,n), 0 ) , (3)
where a is the “anchor" embedding that will be discussed in detail later, p,n are the “positive" and “negative" embeddings for boxes with larger and smaller IoUs with ground truth box g, respectively, m is a margin hyperparameter. We learn an embedding space consistent with local ordinal constraints on positive and negative data obtained via data augmentation such as box perturbation.
Box Perturbation Assuming the training exemplary set Etrain contains both image I and box g, we adopt a tailored data augmentation scheme - box perturbation, in which a pair of boxes are randomly sampled from I with different IoUs to g. We compare the efficiency of sampling schemes on generating augmented bounding box pairs, (a) Random sampling, where the pair of boxes are generated completely randomly, and (b) Group-based sampling, where dense boxes with variant scales are first generated, and then divided into M = 10 groups according to the IoU with groundtruth box. Each group has an IoU interval of 1/M . The sampling is first done on the group level, i.e., 2 out of M , then sample one box from each group. Thus, the sampled boxes are likely to cover more diverse cases comparing to random sampling. We have found that using IoU-based partition scheme is more effective than random sampling.
The choice of anchor. The anchor embedding a in Eq. 3 is not restricted to the cropped image from the same image. For example, it could be replaced by the prototype embedding (Snell et al., 2017) of the exemplary set E , c = 1/|E| ∑ i∈E gi, where gi is the embedding of the cropped image Ii by ground-truth box gi. If images from multiple classes are available, the prototype can be further made to be class-dependent, or clustering-based. A prototype as the anchor enables test-time policy adaptation without image-box pairs in the exemplary set Etest. In comparison, supervised methods such as faster-RCNN would require image-box pairs for fine-tuning on new tasks. We find that using prototype-based embedding as the anchor leads to better generalization performance than using g in some experiments. It is also interesting to explore other treatment on the exemplary set, such as permutation-invariant architectures (Zaheer et al., 2017; Ilse et al., 2018; Lee et al., 2019).

heading: 3.3 LOCALIZATION AGENT TRAINING
text: As discussed in Section 3.2, we use the ordinal embedding rather than the bounding box coordinates to quantify the improvement that an agent makes, and the continuous-valued reward for the agent moving from state s′ to s takes the following form,
R(s, s′) = ||bt − c|| − ||bt−1 − c||, (4) where c is the protoptype embedding, bt is the embedding of the cropped region at step t. We expect positive reward if the embedding distance between cropped image bt and query image a is decreased.
State representation. Note that a good representation for defining reward may not necessarily be a good state representation at the same time - it may not contain enough information guiding the agent taking the right actions. Chen et al. (2020) suggests that adding a projection head between the representation and the contrastive loss substantially improves the quality of the learned representation. We find that the use of projection head is crucial in balancing the two objectives in our task. The network architecture is shown in Figure 2(a), in which an MLP projection head is attached after an (Region of Interest) RoI encoder. The ROIAlign module handles boxes of different sizes.
Policy network. Starting from a whole image as input, the agent is trained to select actions to transform the current box at each step, maximizing the total discounted reward. We use policy gradient based on a recurrent neural network (RNN) (Mnih et al., 2014) with a vector of history actions and states. More detailed architecture can be found in Figure 2(b) and Appendix Figure 7. For all experiments, we apply policy gradient (REINFORCE) (Williams, 1992) with entropy loss regularization to encourage exploration. The main algorithm is outlined in Algorithm 1.
Algorithm 1: Training localization agent using the proposed ordinal reward signal. Require : initial policy πθ , batch size N , pretrained RoI encoder e and projection head h, learning rate α Output :policy network πθ for sampled minibatch {xk}Nk=1 do
for k=1,...N do Construct an exemplary set Ebatch gj ← h(e(xk, gj)) // compute the ordinal embedding in Figure 2(a) ck ← 1|Ebatch| ∑ j∈Ebatch gj // compute the prototype vector
τk ← { s1, a1, ...sT , aT } by running policy πθ // sample trajectory bt ← take action at, and compute embedding h(e(xk, bt)) for current window bt Rtk ← ‖bt−1 − ck‖ − ‖bt − ck‖ // compute reward in equation 4
end θ ← θ + α∇θ ∑N k=1 [ log πθ (∑T t′=t γ t′−tRtk ) − λ · πθ log πθ ] // policy update
end

heading: 3.4 TEST-TIME ADAPTATION
text: During test time„ the agent has the option of further updating the policy network using the received reward from Eq. 4. To match test conditions, the training batch is split into two groups, and c is computed on a small subset that does not overlap with the training images to localize;During test adaptation, c becomes the prototype of the test exemplary set Etest. Different from Etrain, only cropped images are needed in Etest as shown in Figure 1. Figure 3 shows an illustrative example of query object localization with task adaptation. Given two common objects coexisting in the image environment, the agent is trained to pick up one from the two during training, while quickly adapt to pick another one during testing. Different from unsupervised co-localization approaches (Wei et al., 2017) relying on low-level images clues to distinguish foreground and background, our learning objectives can be specified explicitly by switching the train/test exemplary sets. With test-time adaptation, our agent can handle even partially conflicting learning objectives.

heading: 4 EXPERIMENTAL RESULTS
text: In this section, we evaluate the generalization ability of the ordinal embedding as well as the performance of the trained localization agent on both source and target domains. The embedding-based reward not only improves the RL training, but also enables test-time adaptation of the learned policy. Experimental results demonstrate the effectiveness of our approach, with empirical comparisons to generic RL-based object localization, co-localization and few-shot object detection baselines.
Evaluation protocol. To evaluate the learned ordinal embedding, we use OrdAcc defined as the percentage of images within which the preference between a pair of perturbed boxes is correctly
predicted. To evaluate object localization performance, we use the Correct Localization (CorLoc) (Deselaers et al., 2012) metric, which is defined as the percentage of images correctly localized according to the criterion IoU(bp, g) ≥ 0.5, where bp is the predicted box and g is the ground-truth box. Mean and standard deviation ( displayed as subscript) are reported from 10 independent runs.
Implementation. We evaluate our approach on distorted versions of the MNIST handwriting, the CUB-200-2011 birds (Wah et al., 2011), and the COCO (Lin et al., 2014) dataset. For MNIST, we use three convolutional layers with ReLU activation after each layer as image encoder, while the same but mirrored structure as decoder to learn an autoencoder, and then attach RoI alignment layer followed by two fully connected (fc) layers as projection head for ordinal reward learning. For the CUB and the COCO datasets, we adopt layers before conv5_3 of VGG-16 pretrained on ImageNet as encoder. The projection head uses the same structure as before but with more units for each fc layer. All of our models were trained with the Adam optimizer (Kingma & Ba, 2015). We set margin m = 60 in all the experiments heuristically. All the models take less than one hour to finish training, implemented on PyTorch on a single NVIDIA A100 GPU.

heading: 4.1 ABLATION STUDIES
text: We first study the effectiveness of ordinal embedding and learned reward as well as a few other design choices.
Setting and main results. We analyze the effectiveness of using ordinal embedding in terms of representation and reward first on synthetic datasets of corrupted MNIST digits under cluttered, random patch, Gaussian, or impulse noises (see Figure 8 in Appendix for examples). We want to find the answers to two main questions listed below:
1. Is the embedding distance based reward signal as effective as the IoU counterpart? 2. Does the ordinal triplet loss benefit the state representation learning?
Accordingly, we consider baselines in which embeddings are trained with only autoencoder or jointly with the ordinal projection head. Besides, we also compare our embedding distance based reward against the IoU based reward used in Caicedo & Lazebnik (2015). Without loss of generality, the agent is trained on images of digit 4, and tested on images from all rest classes. In particular, we are interested in evaluating the sample efficiency of different approaches. The results under different training set sizes are shown in Figure 4. To distract the localization agent, cluttered noises with random 6× 6 crops of digits are added to the background. All comparisons are based on the policy gradient (PG) method. With ordinal embedding present in both the representation and reward (“AE+Ord+Embed"), our model performance is consistently better than other settings, especially when the training set size is small. The benefit of a triplet loss is demonstrated by the comparison between “AE+Ord+IoU" and “AE+IoU". Intuitively, the similarity to a queried object is also a more natural goal than objectives defined by bounding boxes IoU, which is used in both generic object detection or localization and previous RL-based approaches.
Signed reward or not. Another intriguing question is that other than benefiting state representation learning, whether the embedding-based reward itself can bring any additional benefits than the IoU-
based reward. From Figure 4, there is a large gap between “AE+Ord+Embed" and “AE+Ord+IoU", especially when the training set size is small. This is counter-intuitive as the ordinal reward is trained with supervision from IoU in embedding space, supposably it shall not bring any additional information. To further analyze this phenomenon, we take the sign operation off in Eq. 1 and retrain the agent. In an experiment with 50 training images, without sign operation, the localization accuracy increases from 90.92% to 94.36% on test digit 4, and from 82.43% to 88.64% on other digit test set. Perhaps, this improvement can be attributed to more informative feedback provided by the continuous-valued, unsigned reward.
On policy vs. off policy. Many deep RL approaches are in favor of using deep Q-Network (DQN) to train an agent. Different from Caicedo & Lazebnik (2015) and Jie et al. (2016), we apply Policy Gradient (PG) to optimize it. Besides, we adopt a top-down search strategy through a RNN, while they used a vector of history actions to encode memory. We evaluate these design choices with four baselines, with "AE+IoU" setting, and trained on the same 600 sampled cluttered digit 4 images. As Table 1 shows, the agent achieves the best performance with "PG+RNN". We find that empirically, with history action vectors the accuracy becomes worse when the agent is trained by DQN.

heading: 4.2 POLICY ADAPTATION DURING TEST-TIME
text: We further demonstrate the performance improvement with test-time policy adaptation. Through all the experiments, we assume source domain contains abundant data annotations, and target domain annotations are only available in an exemplary set of size 5. We compared our policy adaptation scheme with a standard fine-tuning scheme on the pre-trained policy network.
Results on the corrupted MNIST dataset. We use 50 “digit 4 under random patch background noises" to train the ordinal embedding and the localization agent. During test time, either the class of the foreground object or the background changes. The results on policy adaptation to new digits are shown in Table 2. Row 1 illustrates the transferability of the ordinal embedding reward, trained prototype embedding of a subgroup without the training instance, and evaluated using instance embedding from the same test image (“Ord Ins"). Rows 2 to 4 list the resulting localization accuracy after direct generalization (“Before"), fine-tuning on the exemplary set (“Finetune"), and adaptation using all test images (“Adapt"), respectively. Our policy adaptation approach produces a substantial improvement over direct generalization, while fine-tuning approach experiences overfitting on the limited exemplary set. For the background adaptation experiment, we train on 50 digit-3 images and test on digit-2 images. The localization accuracy on both source background and new backgrounds
environment are shown in Table 3, significant improvements are achieved using our policy adaptation scheme.
Results on the CUB dataset. We also evaluate the policy adaptation performance on the CUB dataset. The localization agent is trained on 15 species from the “Warbler" class, and adapted to different classes of “Warbler" (5 new species), “Wren", “Sparrow", “Oriole", “Kingfisher", “Vireo", and “Gull". Each test class contains a single bird class. We also implement deep descriptor transforming (DDT) (Wei et al., 2017), a deep learning based co-localization approach, and add it to the comparison.

heading: 4.3 COMPARISON TO FEW-SHOT OBJECT DETECTORS
text: Given a target domain that one would like to deploy models to, a natural question is whether one should collect labeled data from an abundant number of source domains or from one specific class with potential lower data collection cost. On the COCO dataset, we train on one of the five classes: cat, cow, dog, horse, zebra, then adapt to another four classes. The results are shown in Figure 5. The models perform best using ordinal embedding reward with adaptation (see “ours-adapt"). It shows that, although an agent is trained in a highly specialized way on only one-source tasks, it can still be flexibly generalized to different target tasks. One interesting observation is that, it is easy to transfer from other four classes to zebra, but not vice versa. A possible explanation might be that, the embedding net is biased on textures, and texture information is less adaptable than shape information.
Few-shot object detection (Kang et al., 2019; Yan et al., 2019; Wang et al., 2019; 2020) methods are similar to our work in adapting models to a new test case with the help of limited annotations, but they have a different requirement on the number of training classes. Being different in the generalization mechanism, they usually require multiple classes in both stages of training and fine-tuning. On the COCO dataset, we compared the performance of our methods with TFA (Wang et al., 2020), and Meta-RCNN (Yan et al., 2019), on the same one-way 5-shot test setting. TFA adopts two-stage finetuning of object detector, while Meta-RCNN incorporates additional meta-learner to acquire class-level meta knowledge for generalization to novel classes. These two few-shot baselines are trained on 60 base classes and fine-tuned on all 80 classes, while our model is trained from one single class of the 5 classes randomly selected from the base classes set: elephant, sheep, giraffe, laptop and suitcase. Table 5 shows that with ordinal embedding, our agent achieves better performance even without adaptation, and the performance can be further improved after adaptation.
Co rL
oc (%
)

heading: 5 CONCLUSION AND FUTURE WORK
text: We propose an ordinal representation learning based reward, for training a localization agent to search queried objects of interest. In particular, we use a small exemplary set as a guidance signal for delivering learning objectives without ambiguity. Meanwhile, we use test image environments to inform the agent about the domain shifts, without requiring image-box pairs during test time.
Instead of jointly training a localization and classification model, we learn box annotations from image class labels, in a similar spirit to weakly-supervised learning. Empirically, we focus extensively on the transfer learning setting from one single data abundant training task to data-scarce (one-way few-shot) test tasks. To make a trained RL agent generalizable to new unseen test cases, one can either expose the agent to as many cases as possible during training, or make the agent more specific but adaptable upon changed scenarios. Our approach belongs to the latter.
The transferability of our reward signal from training to test crucially relies on the generalization ability of the learned ordinal representation. If the ordinal preference does not hold in the test domain, the proposed test-time policy adaptation scheme will not work. By adapting the representation with self-supervised objectives (Hansen et al., 2021), this issue might be remedied.
Although our work focuses on the generalization ability of a single object localizer, extensions to multiple objects can possibly be done by applying it multiple times and marking the found regions, in a similar manner as (Caicedo & Lazebnik, 2015). Curriculum learning with a designed sequence of targets in the exemplary set may guide the agent toward solving challenging localization tasks. We leave those extensions for future study.

heading: REPRODUCIBILITY STATEMENT
text: Code is available at:
https://anonymous.4open.science/r/Localization-by-Ordinal-Embedd ing-2F24
More implementation details and experiment results can be found in Appendix.

heading: A APPENDIX: IMPLEMENTATION DETAILS

heading: A.1 ALGORITHM PIPELINE
text: General supervised training methods are usually class-agnostic and require exposure to a large number of training classes, box-image pairs, and foreground and background variations in order to generalize well. In contrast, we allow specialized agent to be trained, with the ability of adaptation to changes during the test time. Our approach is based on the feature similarity with query images, which departs from previous bounding-box regression and RL approaches based on objectiveness. Compared to general supervised training or fine-tuning methods, our approach is able to flexibly make use of various types of data in these phases. This is summarized in Table 6.
Our agent can take both human feedback in terms of the exemplary set and perform test-time policy adaptation using unlabeled test data. It includes three stages: ordinal representation pre-training, RL agent training, and test-time adaptation. Details are as follows:
Stage 1: Pretrain ordinal embedding for state representation and reward In this stage, we assume pairs of groundtruth bounding box and training image are available. We train the ordinal embedding by attaching a projection head after RoI encoder, as Figure 6 shows. RoI encoder is composed of image encoder and an RoI alignment layer (He et al., 2017). It extracts corresponding bounding box feature directly from image feature output by image encoder. After training, all the modules are fixed. The output of RoI Encoder then becomes the state for agent, and output of projection head is then used for reward computation.
On Corrupted MNIST (cMNIST) dataset, We attach a decoder in order to train the encoder, but discard it during inference. The loss function is defined as
L = Lreconstruct + λ1 · Ltriplet, (5)
where we set λ1 = 0.1, and Lreconstruct is mean square error loss to measure the reconstruction ability of the autoencoder. On CUB and COCO dataset, we adopt the pretrained ImageNet encoder, thus no additional decoder is needed. The triplet loss Ltriplet is optimized, such that the embedding of positive bounding boxes to be closer to the embedding of anchor than negative boxes. Different from traditional definition of triplet loss, our positive and negative boxes are not fixed. When comparing two perturbed boxes, the positive box is always the one with larger IoU. Thus, a box with IoU=0.2 could be positive box if the negative box has even smaller IoU. The anchor box is not restricted to ground truth box of the image instance. For example, we use the mean vector of ordinal embeddings in this paper, computed from groundtruth boxes of images from the exemplary set.
Stage 2: Localization agent training In this stage, we assume the groundtruth bounding box is available for each training image. All the models are trained and tested on the same datasets as stage 1. We fix all the layers in RoI encoder and projection head. The adopted RNN model is shown in Figure 7. In each step, the agent takes the RoI encoder output eroi and the hidden state of RNN ht−1, concatenated as the state representation. Then it predicts the action for next step by sampling according to the logits. The loss is defined as
Lagent = Lpolicy + λ2 · Lentropy, Lentropy = −π log π, Lpolicy = −(R− R̄) · log π (6)
where Lentropy prevents the agent from being stuck in the local minimum, π is the policy, and R is the reward defined in Eq. 4.
Stage 3: Test-time adaptation To adapt to new class, we make use of a limited number of groundtruth box cropped images in the test exemplary set. We leverage abundant unlabelled images and this exemplary set to update the agent. We fix the RoI encoder and projection head, and only update the agent. The process is almost the same as stage 2, except that c in reward (Eq. 4) is the prototype of the test exemplary set.
In summary, the configuration of different model components and how they are updated is listed in Table 7. The losses for each dataset and training stage is in Table 8.

heading: A.2 EXPERIMENTS DETAILS
text: We list experiment details for the datasets used in Section 4 as follows.
Corrupted MNIST Dataset. Examples of the four types of corrupted MNIST (cMNIST) images are shown in Figure 8. In stage 1 and 2, we randomly sample 50 images of one class in original MNIST training set, and add noise as our training set. During testing, the models are evaluated on all the corrupted MNIST test set. In stage 3, to adapt to a new digit, we annotate a limited number of images as exemplary set for adaptation and use all the (corrupted) MNIST training set from that digit. We then test the agent on all (corrupted) MNIST test set of the same digit. There is no overlap between the training and test set used in stage 3.
CUB Dataset. In stage 1 and 2, we train on 15 warbler classes with class id between 158 and 172. There are 896 images in total. Then test the models on 5 new warbler classes with class id between 178 and 182, resulting in 294 images in total. In stage 3, the number and class ids of images for each class are presented in Table 9. We also randomly select limited number of images as exemplary set and use all unlabled data for adaptation. The CorLoc is calculated using all the images of this class.
COCO Dataset. For the results of Figure 5, we train on one of the five classes: cat, cow, dog, horse, zebra, then adapt to another four classes. The detailed number of each class for training and testing in stage 1 and 2 is shown in Table 10.
In stage 3, the agent is tested on new class in target domain, within which we annotate limited number of images for adaptation. In comparison with few-shot object detection experiment, the models in stage 1 and 2 are trained using one single class of the 5 classes: elephant, sheep, giraffe, laptop and suitcase. Then being adapted to the four classes in Table 5. Note that the five classes are in the base classes, and the four classes are in the novel classes used in other methods. Thus, it’s harder to transfer from one single class to another due to scarcity of training data and training class. Table 5 reports the average CorLoc from the five classes to each target class. We also provide the results of each source class in Table 11. From this table, we can see that transferring from related classes with target class usually performs better. For example, the CorLoc from laptop and suitcase are lower than other three animal classes, especially before adaptation. After adaptation, the gap becomes smaller.
Selective localization. We investigate the agent’s ability in localizing the object specified by the query set, when the set of images have two common objects. We use random patched MNIST, where each image has digit 3 and digit 4. First, the RoI encoder and projection head is trained with an additional contrastive loss to enlarge the distance between the two digits in embedding space,
lossembed = lossrec + λtrip · losstrip + λcontr · losscontr, (7)
where losstrip = losstrip3 + losstrip4 , learning two local ordinal structure around each class center in embedding space. We set the margin for both triplet losses as 10, and the margin for contrastive loss as 320 heuristically. We found that the larger the gap between the two margins, the better the performance. Detailed results can be found in Table 17 and its related discussion. After learning the RoI encoder and projection head, we train the agent with the reward defined with Eq. 4 in Sect. 3.3, where c is the prototype embedding of the targeted digit exemplary set. Figure 3 in Sect. 4 shows an example where the exemplary size is 5.

heading: B ADDITIONAL EXPERIMENTS

heading: B.1 ABLATION OF ORDINAL EMBEDDING AND RL
text: We analyze the effectiveness of ordinal embedding and RL component separately. First, we remove RL, and substitute it with a simple linear search approach. Specifically, we adopt selective search (Uijlings et al., 2013) for candidate boxes generation. The candidate boxes are ranked according to their embedding distances to the prototype, and the one with the smallest embedding distance is returned as the final output. We considered two backbone networks as the embedding, including ImageNet pretrained VGG-16 and faster-RCNN VGG-16 trained locally on COCO. We also compare both with and without the ordinal component, making it a 2× 2 ablation study. It can be seen from the blue and green bars from Figure 9 and Figure 10 that with ordinal structure, the ranking method performs much more better. We found that pre-training with the proposed ordinal loss significantly improves the rank consistency of these backbone networks.
To further demonstrate the effectiveness of ordinal embedding, we compute the Spearman’s Rho rank correlation between embedding distance to the prototype and IoU to the groundtruth. The results are shown in Figure 11. Here we also add CLIP (Radford et al., 2021) pretrained ViT as backbone for comparison. The rank correlation is smaller than −0.7 on all backbones with ordinal embedding, exhibiting ordinal embedding preserves the IoU order, thus is better for the ranking purpose. Although pretty effective, embedding distance is still not a perfect indicator of the ranking of IoU. Thus, directly formulate the object localization problem as a search problem leads to suboptimal localization accuracy.
In contrast, being able to learn across different images, the RL localization agent shows more tolerance for the defects of the reward function. We analyze the benefits of RL component. For both Figure 9
and Figure 10, when using ordinal embedding, the model with RL is generally better than ranking, especially after adaptation.
Ordinal component is necessary for several possible reasons. First, the ordinal component makes the generic pre-trained network more specific to the downstream object localization task. Second, it helps remove the dataset bias if the pre-trained network is non-native. Third, ordinal pretraining encourages the reward signal to reflect step-by-step improvements.
Encouraged by the strong baseline performance of Faster RCNN on both source and target domain (detailed in Table 13 and Table 14), we investigate whether it is adequate to use Faster RCNN embedding in the RL reward function, without ordinal pre-training. Since Faster RCNN emebdding is also trained for object localization on the COCO dataset, it can better separate out the effects of the ordinal pretraining component. Result is shown in Table 12. Comparing to the second row of Table 15, it can be seen that without ordinal pretraining the performance degrades significantly, where the CorLoc is much lower even in source domain.

heading: B.2 COMPARE WITH SUPERVISED BASELINE - FASTER RCNN
text: We compare our framework with a strong supervised object localiztion baseline, Faster RCNN (Ren et al., 2016). Both methods are trained in one class (foreground vs. background as the classification labels in Faster RCNN) and adapted to a different class. We use VGG-16 model pretrained on ImageNet, and finetune and test on each of the five classes: cow, cat, dog, horse, zebra. The results on source domain are shown in Table 13. It shows that Faster RCNN can also be made into a
class-specific model and it still yields superior performance on source domain. On the target domain, we finetune Faster RCNN using only support set for each target class. The results are shown in Table 14. It can be seen that our method works better on new classes with test-time adaptation over the traditional fine-tuning of Faster RCNN. Note that fine-tuning requires image-box pairs in the target domain while our policy adaptation approach does not.

heading: B.3 COMPARE DIFFERENT OFF-THE-SHELF NETWORKS AS THE BACKBONE
text: It is interesting to study the choices of off-the-shelf pre-trained networks as the backbone, such as CLIP or supervised embedding provided by Faster RCNN or a classification network. Since these networks have been exposed to large-scale dataset, it is interesting to see whether policy adaptation is still needed. We compare different backbones on both source domain and target domain using our method. Table 15 reports the CorLoc of training and testing on source domain. The large-scale pretraind ViT backbone consistently performs the best, comparing to the other two VGG-16 models.
Table 16 compares the backbones on target domain with new classes. The test-time adaptation still brings a large margin of improvement. Interestingly, we also found that the Faster-RCNN embedding offers the best performance on the target domain before adaptation, while the ViT network trained on CLIP dataset provides the best performance after adaptation, indicating different generalization mechanisms. They both outperform the ImageNet backbone intially considered.

heading: B.4 THE EFFECTS OF MARGIN
text: The margin in triplet loss is selected heuristically. It is not sensitive except in the selective localization experiment (Figure 3), where there are two different digits in each image. For this experiment, we trained two ordinal structures around each digit using triplet loss with margin m1, and add additional contrastive loss with margin m2 to separate the centers of the two different digits as far as possible. And we found out that the model works best when m2 m1. In our experiment, we set m1 = 10,m2 = 320. The results of using different set of m1 and m2 are presented in Table 17.

heading: B.5 SIZE OF TRAINING SET
text: In this experiment, we train on class giraffe in stage 1 and 2, then adapt to cat, cow, dog and horse. We set the training set size as [200, 500, 700, 1146], exemplary set size as 5. We compare our after adaptation results with TFA w/ fc (Wang et al., 2020) one-way 5-shot setting, where their model is trained on all 60 base classes, while ours is only trained on one of the base classes. Figure 12 shows the results, in which the dotted lines are the results of TFA w/ fc. Ours performs much more better than their method. Except cat class, ours is better than theirs with only 200 images for training.

heading: B.6 SIZE OF EXEMPLARY SET
text: We also compare the effect of different size of exemplary set during training and adaptation on CUB-warbler dataset. During training stage, we use shuffle proto training strategy, and set exemplary set size as 2, 5, 15, 25. The results without adaptation on test set are in Table 18. Both OrdAcc and CorLoc increase with exemplary set size. For adaptation stage, the range of exemplary set size is from 2 to 200. And the results are in Table 19. The test performance does not increase much with the exemplary set size. One possible explanation is that the data points in embedding space are compact, thus prototype doesn’t change much when increasing exemplary set size. We will analyze the influence of multiple protoptypes per class in future experiments.

heading: B.7 PROTOTYPE SELECTION
text: We further evaluate the choice of anchor in the triplet loss for both the pretraining of state represtation and the ordinal reward for the training of agent. We study (i) whether ordinal embedding can be trained in reference to an anchor from a different image instances, (ii) whether it is advantageous to use the proptotype embedding of an exemplary set, rather than instance embeddings, and (iii) whether mimicking the test condition in training yields any improvement.
We use the CUB-Warbler dataset with more foreground background variations than the corrupted MNIST dataset. The train and test set contains 15 and 5 disjoint fine-grained classes respectively, resulting 896 images for training (viewed as a single class) and 294 for testing. Table 20 shows the OrdAcc and CorLoc in four settings. “Self", use the embedding from images cropped by the ground-truth box from the same instance; “Shuffle self", use the ground-truth box cropped image emebedding from a different instance; Similarly, “Proto", use the prototype of a subgroup containing the training instance within the same batch; “Shuffle proto (SP)", use the prototype of a subgroup
from a different batch without the training instance. Results suggest that this training strategy brings compactness to the training set, constructing an ordinal structure around the cluster. For “Shuffle proto", while the OrdAcc is lower than others, its CorLoc is the best with large margin. Matching the condition between training and testing indeed improves generalization to new classes on this dataset.

heading: B.8 ANNOTATION REFINEMENT
text: Annotation collection plays an important role in building machine learning systems. It is one task that could benefit greatly from automation, especially in cost-sensitive applications.The human labeling efforts can be reduced, not only in terms of the number of annotate samples per class, number of annotate classes (one-class at the minimum), but also the level of accuracy required. We explore the direction of iterative refinement of annotation quality with minimal human guidance. Given an agent trained extensively with inexact human annotations, can we adapt it to refine the annotation with a few well-annotated examples? We purposefully enlarge the ground truth bounding boxes in the corrupted MNIST and CUB datasets, and adapt the trained agent using the original ground truth box in an exemplary set of size 5.
For corrupted MNIST dataset, the agent, RoI encoder and projection head are first trained with 50 digit 3 images with loose (38×38 ) bounding box annotation. Then the agent is adapted to digit 1 images, where the exemplary size=5, and the ground-truth boxes are 28×28. For CUB dataset, during training, the ground-truth box in each resized 224×224 image is expanded 10 pixels each side. During adaptation we use the original ground-truth boxes. In adaptation from entire body to head experiment on CUB dataset, we train on original entire body ground-truth bounding box. During adaptation, 15 randomly sampled exemplar images are annotated with head bounding box. The agent is trained to adapt to localize head by minimizing the distance between embedding of predicted box and prototype of head embeddings. The results are shown in Figure 13 (left panel). Preliminary results with agent trained on the entire bird body and adapt to bird head are shown in Figure 13 (right panel), with a few successful cases on the first row and failure cases on the second row.

heading: B.9 FEW-SHOT LOCALIZATION ON OMNIGLOT
text: The proposed ordinal reward signal also makes our approach amenable to few-shot training, when only a small subset of training images per class are annotated. Different from the transfer learning setting, in few-shot setting limited annotations across multiple classes are available during training. The ordinal reward can be viewed as meta information. We evaluate our method under few-shot setting on corrupted Omniglot dataset (Lake et al., 2015) and CUB-warbler dataset. For Omniglot, We put each 28×28 character in 84×84 random patch background. The train and test set contains 25
different classes respectively, thus 500 images for each set. We randomly sample 100 iterations for training and testing. For CUB-warbler datset, as we did in Sect. 4.2 we train on the same 15 species from the “Warbler" class, and adapted to 5 new species of “Warbler", thus 896 and 294 images respectively. We randomly sample 100 and 50 iterations for training and testing. We use 5-shot 5-way, set exemplary set size as 5, and use proto training strategy for both dataset. The results are shown in Table 21. As an implicit meta learning method, our approach achieves 99.94% and 90.52% CorLoc on the two datasets. We can also leverage explicit meta learning method, such as MAML (Finn et al., 2017) to further improve the results. We will leave this part as future work. Although initial results are promising, more efforts are needed to validate whether the proposed RL approach can achieve state-of-the-art performance, but it is beyond the scope of this work.
C INTERMEDIATE RESULTS
The agent tends to predict expected actions to transform the box so that it can finally get to the target location. It can also be observed from Figure 14 that the embedding distance between predicted boxes and ground-truth boxes is in agreement with the corresponding IoU. This further demonstrates the effectiveness of the localization agent.

Review summaries:
This paper proposes a new method for the task of query object localization. It learns an embedding network such that the image crop that is closer to the query object will have a closer embedding distance as well, and the improvement of the embedding distance will be used as the reward function. The RL agent is then employed to maximize the reward. The paper found that the proposed approach compares favorably to DDT on object location on CUB and FTA on few-shot object detection on COCO.

The paper proposes a reinforcement learning approach for localization in images. The idea is to consider and environment where the states are crops of an image, the actions are changes in the current coordinates of the current crops starting at the full image. The method consists of learning both a reward function and a policy that maximizes that reward function. The policy is learnt with REINFORCE with entropy regularisation. The manner in which the reward function is formulated and learnt is quite appealing. To allow for more flexibility at test time, the reward function is made conditional on some exemplars and learnt in a few shot manner based on state features. Using a triplet loss to ensure the reward function is increasing as the overlap is increasing is quite good.  The experiments are quite extensive and I find compelling for the most part. Ablation of the elements of the method is well executed and benefits of few short learning are compelling enough in my opinion. The results on COCO are a bit limited but I would be willing to overlook that.   

This paper presents a new metric learning method on the RL formulation of query object localization. The metric learning method is based on a contrastive learning formulation of ordinal embeddings, which are pretrained with data augmentations and a loss formulation that respects IoU orderings. The experiment results have demonstrated that the proposed embedding metric increased the task performance compared with the baseline metric (IoU), and shown better generalization behavior on novel image categories. 

This paper extends works performing RL-based object localization by: 1. Conditioning the localization on a exemplary set of images, instead of more classical hardcoded finite set of classes 2. Introducing a new reward signal which doesn’t explicitly use IoU but instead enforces a rank-preserving metric space (where distances reflect how well 2 bounding boxes match up).  This is shown on multi-MNIST data, CUB and COCO. They are targeting rather challenging generalisation setups, where a policy is only trained to localize 1 digit class (in the MNIST case say) and extrapolates to all other ones.