summaries: This work contributes to introducing a problem called Online Continual Compression. This problem requires to avoid catastrophic forgetting and learn in an online way. Generative methods should be one of the popular ways to do continual learning. This work’s model can be categorized into this clue since it also aims to save samples from old tasks by learning a generative model. In this way, the generator plays a similar role Experience Replay (ER) (here is called Generative Replay). The main core of this work should be the stacked quantization modules (SQM) which can be regarded as a hierarchical variant of the VQ-VAE model. In their SQM, hidden encodings z_q^i will be encoded and its input is z_q^{i-1} which is from previous layer.

summaries: This paper presented a Stacked Quantization Modules (SQM) for the problem of Online Continual Compression, based on the VQ-VAE framework by van den Oord et al. (2017). Experiments were conducted on online continual image classification benchmarks to show the effectiveness of the proposed SQM. In general, the novelty of the paper is a little bit limited and the writing of the paper is not very easy to follow.

summaries: The study tackled the problem of limited storage for ever-growing data for a long-term learning scenario. The authors proposed to stack Quantization Modules while separating them during training to obtain an online compression system that has multiple resolutions, different memory horizons, and reduced catastrophic forgetting. They also proposed a modified reservoir sampling to accommodate this architecture.

abstractText: We introduce and study the problem of Online Continual Compression, where one attempts to learn to compress and store a representative dataset from a non i.i.d data stream, while only observing each sample once. This problem is highly relevant for downstream online continual learning tasks, as well as standard learning methods under resource constrained data collection. To address this we propose a new architecture which Stacks Quantization Modules (SQM), consisting of a series of discrete autoencoders, each equipped with their own memory. Every added module is trained to reconstruct the latent space of the previous module using fewer bits, allowing the learned representation to become more compact as training progresses. This modularity has several advantages: 1) moderate compressions are quickly available early in training, which is crucial for remembering the early tasks, 2) as more data needs to be stored, earlier data becomes more compressed, freeing memory, 3) unlike previous methods, our approach does not require pretraining, even on challenging datasets. We show several potential applications of this method. We first replace the episodic memory used in Experience Replay with SQM, leading to significant gains on standard continual learning benchmarks using a fixed memory budget. We then apply our method to online compression of larger images like those from Imagenet, and show that it is also effective with other modalities, such as LiDAR data.

authors:
Rahaf Aljundi
Min Lin
Baptiste Goujaud
Yoshua Bengio

title: Online continual learning with no task boundaries

venue: In arXiv,

authors:
Rahaf Aljundi
Lucas Caccia
Eugene Belilovsky
Massimo Caccia
Laurent Charlin
Tinne Tuytelaars

title: Online continual learning with maximally interfered retrieval

venue: In Advances in Neural Information Processing (NeurIPS),

authors:
Johannes Ballé
Valero Laparra
Eero P Simoncelli

title: End-to-end optimization of nonlinear transform codes for perceptual quality

venue: In 2016 Picture Coding Symposium (PCS),

authors:
Eugene Belilovsky
Michael Eickenberg
Edouard Oyallon

title: Decoupled greedy learning of cnns

venue: arXiv preprint arXiv:1901.08164,

authors:
Lucas Caccia
Herke van Hoof
Aaron Courville
Joelle Pineau

title: Deep generative modeling of lidar data

venue: arXiv preprint arXiv:1812.01180,

authors:
Arslan Chaudhry
Marc’Aurelio Ranzato
Marcus Rohrbach
Mohamed Elhoseiny

title: Efficient lifelong learning with a-gem

authors:
Arslan Chaudhry
Puneet K Dokania
Thalaiyasingam Ajanthan
Philip HS Torr

title: Riemannian walk for incremental learning: Understanding forgetting and intransigence

venue: arXiv preprint arXiv:1801.10112,

authors:
Arslan Chaudhry
Marcus Rohrbach
Mohamed Elhoseiny
Thalaiyasingam Ajanthan
Puneet K Dokania
Philip HS Torr
Marc’Aurelio Ranzato

title: Continual learning with tiny episodic memories

authors:
Sebastian Farquhar
Yarin Gal

title: Towards robust evaluations of continual learning

venue: arXiv preprint arXiv:1805.09733,

authors:
Chrisantha Fernando
Dylan Banarse
Charles Blundell
Yori Zwols
David Ha
Andrei A Rusu
Alexander Pritzel
Daan Wierstra

title: Pathnet: Evolution channels gradient descent in super neural networks

venue: arXiv preprint arXiv:1701.08734,

authors:
Andreas Geiger
Philip Lenz
Christoph Stiller
Raquel Urtasun

title: Vision meets robotics: The kitti dataset

venue: The International Journal of Robotics Research,

authors:
Lionel Gueguen
Alex Sergeev
Ben Kadlec
Rosanne Liu
Jason Yosinski

title: Faster neural networks straight from jpeg

authors:
Wenpeng Hu
Zhou Lin
Bing Liu
Chongyang Tao
Zhengwei Tao
Jinwen Ma
Dongyan Zhao
Rui Yan

title: Overcoming catastrophic forgetting for continual learning via model adaptation

title: On quadratic penalties in elastic weight consolidation

venue: arXiv preprint arXiv:1712.03847,

authors:
Eric Jang
Shixiang Gu
Ben Poole

title: Categorical reparameterization with gumbel-softmax

venue: arXiv preprint arXiv:1611.01144,

authors:
Nick Johnston
Damien Vincent
David Minnen
Michele Covell
Saurabh Singh
Troy Chinen
Sung Jin Hwang
Joel Shor
George Toderici

title: Improved lossy image compression with priming and spatially adaptive bit rates for recurrent networks

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

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: arXiv preprint arXiv:1312.6114,

authors:
James Kirkpatrick
Razvan Pascanu
Neil Rabinowitz
Joel Veness
Guillaume Desjardins
Andrei A Rusu
Kieran Milan
John Quan
Tiago Ramalho
Agnieszka Grabska-Barwinska

title: Overcoming catastrophic forgetting in neural networks

venue: Proceedings of the national academy of sciences,

authors:
Timothée Lesort
Hugo Caselles-Dupré
Michael Garcia-Ortiz
Andrei Stoian
David Filliat

title: Generative models from the perspective of continual learning

venue: arXiv preprint arXiv:1812.09111,

authors:
Timothée Lesort
Alexander Gepperth
Andrei Stoian
David Filliat

title: Marginal replay vs conditional replay for continual learning

venue: In International Conference on Artificial Neural Networks,

authors:
Zhizhong Li
Derek Hoiem

title: Learning without forgetting

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

title: Reinforcement learning for robots using neural networks

venue: Technical report, CarnegieMellon Univ Pittsburgh PA School of Computer Science,

title: Gradient episodic memory for continual learning

venue: In Advances in Neural Information Processing Systems,

authors:
Cuong V Nguyen
Yingzhen Li
Thang D Bui
Richard E Turner

title: Variational continual learning

venue: arXiv preprint arXiv:1710.10628,

authors:
Arild Nøkland
Lars Hiller Eidnes

title: Training neural networks with local error signals

venue: arXiv preprint arXiv:1901.06656,

authors:
Edouard Oyallon
Eugene Belilovsky
Sergey Zagoruyko
Michal Valko

title: Compressing the input for cnns with the first-order scattering transform

venue: In The European Conference on Computer Vision (ECCV),

authors:
Jason Ramapuram
Magda Gregorova
Alexandros Kalousis

title: Lifelong generative modeling

venue: arXiv preprint arXiv:1705.09847,

authors:
Ali Razavi
Aaron van den Oord
Oriol Vinyals

title: Generating diverse high-fidelity images with vq-vae-2

venue: arXiv preprint arXiv:1906.00446,

authors:
Sylvestre-Alvise Rebuffi
Alexander Kolesnikov
Georg Sperl
Christoph H Lampert

title: icarl: Incremental classifier and representation learning

venue: In Proc. CVPR,

authors:
Matthew Riemer
Michele Franceschini
Tim Klinger

title: Generation and consolidation of recollections for efficient deep lifelong learning

authors:
Matthew Riemer
Ignacio Cases
Robert Ajemian
Miao Liu
Irina Rish
Yuhai Tu
Gerald Tesauro

title: Learning to learn without forgetting by maximizing transfer and minimizing interference

authors:
David Rolnick
Arun Ahuja
Jonathan Schwarz
Timothy P. Lillicrap
Greg Wayne

title: Experience replay for continual learning, 2018

authors:
Hanul Shin
Jung Kwon Lee
Jaehong Kim
Jiwon Kim

title: Continual learning with deep generative replay

authors:
Lucas Theis
Wenzhe Shi
Andrew Cunningham
Ferenc Huszár

title: Lossy image compression with compressive autoencoders

venue: arXiv preprint arXiv:1703.00395,

authors:
Sebastian Thrun
Tom M Mitchell

title: Lifelong robot learning

venue: Robotics and autonomous systems,

authors:
Róbert Torfason
Fabian Mentzer
Eirı́kur Ágústsson
Michael Tschannen
Radu Timofte
Luc Van Gool

title: Towards image understanding from deep compression without decoding

authors:
Chenxi Tu
Eijiro Takeuchi
Alexander Carballo
Kazuya Takeda

title: Point cloud compression for 3d lidar sensor using recurrent neural network with residual blocks

venue: In 2019 International Conference on Robotics and Automation (ICRA),

authors:
Aaron van den Oord
Oriol Vinyals

title: Neural discrete representation learning

authors:
Friedemann Zenke
Ben Poole
Surya Ganguli

title: Continual learning through synaptic intelligence

venue: arXiv preprint arXiv:1703.04200,

authors:
Mengyao Zhai
Lei Chen
Fung Tung
Jiawei He
Megha Nawhal
Greg Mori

title: Lifelong gan: Continual learning for conditional image

venue: generation. ArXiv,

authors:
Ji Zhang
Sanjiv Singh

title: Loam: Lidar odometry and mapping in real-time

venue: In Robotics: Science and Systems,

title: Figure 4: Bottom row: random buffer reconstructions using Riemer et al

venue: (2018). Middle row: random buffer reconstructions using SQM. Top row: corresponding original image. Columns are ordered w.r.t their entry time in the buffer, from oldest to newest. All samples above were obtained from the disjoint CIFAR-10 task, and are 12× smaller than their original image.

heading: 1 INTRODUCTION

text:
Interest in machine learning in recent years has been fueled by the plethora of data being generated on a regular basis. Effectively storing and using this data is critical for many applications, especially those involving continual learning. In general, compression techniques can greatly improve data storage capacity, and, if done well, reduce the memory and compute usage in downstream machine learning tasks (Gueguen et al., 2018; Oyallon et al., 2018). Thus, learned compression has become a topic of great interest (Theis et al., 2017; Ballé et al., 2016; Johnston et al., 2018). Yet its application in reducing the size of datasets bound for machine learning applications has been limited.
This work focuses on the following familiar setting: new training data arrives continuously for a learning algorithm to exploit, however this data might not be iid, and furthermore there is insufficient storage capacity to preserve all the data uncompressed. We may want to train classifiers, reinforcement learning policies, or other models continuously from this data, or use samples randomly drawn from it at a later point for a downstream task. For example, an autonomous vehicle (with bounded memory) collects large amounts of high-dimensional training data (video, 3D lidar) in a non-stationary environment (e.g. changing traffic patterns), and overtime applies an ML algorithm to improve its behavior using this data. This data might be transferred at a later point for use in downstream supervised learning. Current standard learned compression algorithms, e.g. Torfason et al. (2018), are not well designed to deal with this case, as their convergence speed is too slow to be usable in an online setting.
In the field of continual/lifelong learning (Thrun & Mitchell, 1995), which has for now largely focused on classification, approaches based on storing memories for later use have emerged as some of the most effective in online settings (Lopez-Paz et al., 2017; Aljundi et al., 2018; Chaudhry et al.; 2019; Aljundi et al., 2019). These memories can be stored as is, or via a generative model (Shin et al., 2017). Then, they can either be used for rehearsal (Chaudhry et al., 2019; Aljundi et al., 2019) or for constrained optimization (Lopez-Paz et al., 2017; Chaudhry et al.; Aljundi et al., 2018).
Indeed many continual learning applications would be nearly solved with replay approaches if one could afford to store all samples. These approaches are however inherently limited by the amount of data that can be stored1.
Learning a generative model to compress the previous data stream thus seems like an appealing idea. However, learning generative models, particularly in the online (possibly non-stationary) setting, continues to be challenging, and can greatly increase the complexity of the continual learning task. Furthermore, such models are susceptible to catastrophic forgetting Aljundi et al. (2019). An alternate approach is to simply learn a compressed representation of the data; this is typically faster and more stable than learning to generate the whole data distribution. While the learned compression may itself exhibit forgetting and representation drift, causing challenges for continual and online cases, a learned compression method that can learn continuously and online would allow the storing of far larger amount of samples for replay.
In this work we investigate the use of quantized autoencoders, specifically the VQ-VAE framework (van den Oord et al., 2017), observing that these can learn continuously and online with minimal forgetting, particularly when augmented with their own internal rehearsal mechanisms. We propose a multi-level stacked model that allows the compressor to adaptively store samples at different compression scales, based on the amount of data, storage capacity, and effectiveness of the model in compressing samples. Furthermore, the learned compressed representation allows multiple continual learning models to be trained from the same data.
The main contributions in this work are as follows: (a) we introduce and highlight the importance of the online continual learned compression problem; (b) we demonstrate how Multi-level VQVAE, combined with internal replay, can effectively learn compressed representations of online data, (c) we show online learned compression can yield state-of-the-art performance in standard online continual image classification benchmarks.

heading: 2 RELATED WORK

text:
Learned compression has been recently studied for the specific case of image compression. Work by Theis et al. (2017); Ballé et al. (2016); Johnston et al. (2018) have shown learned compressions can outperform standard compression algorithms like JPEG. Some of these methods however are challenging to train, thus in our work we focus on the VQ-VAE approach van den Oord et al. (2017); Razavi et al. (2019) which allows us to address online continual learning settings and permit a multilevel storage.
Continual Learning research currently focuses on overcoming catastrophic forgetting (CF) in the supervised learning setting, with some limited work in the generative modeling and reinforcement learning settings. Most continual learning methods can be grouped into three major families.
Some algorithms dynamically change the model’s architecture to incorporate learning from each task separately. Popular methods are Rusu et al. (2016), Li & Hoiem (2018) and Fernando et al. (2017). Although these methods can perform well in practice, their introduction of task-specific weights requires growing compute and memory costs which are problematic for the online setting. Another set of techniques employ regularization to constrain weights updates in the hope of maintaining knowledge from previous tasks. Notable methods in this class include (Kirkpatrick et al., 2017; Huszár, 2017; Zenke et al., 2017; Nguyen et al., 2017; Chaudhry et al., 2018). This set of approaches is inefficient in the online setting Chaudhry et al. (2019).
The last family of methods encapsulates all that have a mechanism to store information about the previous data distributions. This memory then serves as a tool for the continual learner to rehearse previous tasks. The simplest instantiation of this method is to keep and sample from a buffer of old data to retrain the model after every update (Chaudhry et al., 2019). This approach is widely used in RL where it is known as Experience Replay (ER) (Lin, 1993). Another method, known as Generative Replay (GR) (Shin et al., 2017), uses generative modeling to store past tasks distributions. The continual learner then trains on generated samples to alleviate CF. Other notable examples are Gradient Episodic Memory (GEM) (Lopez-Paz et al., 2017), iCarl (Rebuffi et al., 2017), and Maximally Interfered Retrieval (MIR) Aljundi et al. (2019), as well as (Aljundi et al., 2018; Hu et al.,
1This is typically not feasible for on-device machine learning. And while many ML services currently run on the cloud, the move towards increasingly higher data privacy standards is likely to push many ML algorithms to run locally on device.
2018). Most closely related to our work Riemer et al. (2017) consider compressing memories for use in the continual classification task. They also employ a discrete latent variable model but with the Gumbel approximation which shows to be far less effective than our approach. Most notably a separate offline iid pre-training step for the learned compression is required in order to surpass the ER baseline, distinctly different from the online continual compression we consider.
Lidar compression is considered in Tu et al. (2019) and Caccia et al. (2018). Both approaches use a similar projection from 3D (x, y, z) coordinates to 2D cylindrical coordinates, and leverage deep generative models to compress the data. However, neither method was designed to account for potential distribution shift, nor for online learning. In this work we show that reusing this 2D projection in conjunction with out model allows us to mitigate the two issues above for lidar data.
Algorithm 1: SQM Replay Input: Learning rates αcls, αae
1 Initialize: MemoryM; θae 2 for t ∈ 1..T do 3 % Fetch data from current task 4 for Binc ∼ Dt do 5 for n ∈ 1..N do 6 B ← Binc 7 if t > 1 then 8 % Fetch data from buffer 9 Bre ∼ SAMPLE(M)
10 B ← (Binc, Bre) 11 end 12 % Train Compressor Network 13 θgen ← ADAM(Lvq, B, αae) 14 if t > 1 then
UPDATEBUFFERREP(M, θae)
15 %Save current indices 16 ADDTOMEMORY(M,Binc, θae) 17 end 18 end 19 end
Algorithm 2: AdaptiveCompress Input: datapoint x, SQM with L modules, distortion
threshold dth 1 Initialize: MemoryM; θae 2 % Compute hidden rep. for all
blocks 3 ENCODE(SQM , x)
4 % Iterate over blocks, from most compressed to least 5 for i ∈ L..1 do 6 % Fetch latent indices and hidden rep. computed in forward pass 7 argmini, zq = ARGMIN(modulei)
8 % Decode to output space 9 for j ∈ i...1 do zq = DECODE(modulej , zq)
10 % Test reconstruction error
11 if MSE(x, zq) < dth then return argmini, i 12 end 13 % If no compression is good enough,
return original image 14 return x, 0

heading: 3 METHODOLOGY

text: In this section we outline our approach to the online continual compression problem. Our learned compression network consists of a set of Multi-resolution VQ-VAE blocks. These blocks only communicate information forward and are not learned jointly unlike the architecture presented in Razavi et al. (2019). Memories are compressed using an adaptive scheme that controls what resolution the sample is stored, and therefore how compressed the sample should be. Furthermore memories can be revisited and further compressed as the learned compression module improves. Finally a rehearsal phase that utilizes the stored memory is used to minimize forgetting and update representations stored in the memory.

heading: 3.1 PROBLEM SETTING

text:
We consider the problem setting where a stream of samples x ∼ Dt arrives from different distributions Dt changing over time t = 1 . . . T . We have a fixed storage capacity of C bytes where we would like to store the most representative information from all data distributions D1, ...DT . There is notably a trade-off in quality of information versus samples stored. We propose to use a learned compression model, and most crucially, this model must also be stored within the C bytes, to encode and decode the data samples. Another critical requirement is that at anytime t the content of the storage (data and/or compression model) be usable for downstream applications. A key challenge is that the learned compression module will change over time, while we still need to be able to decode the memories in storage.
The high level training of the online learned compression is described in Algo 1. Random memories are decoded and used to train the current compression module, at the same time this also allows us to re-encode those memories using the update weights. The approach also incorporates a form of
replay to reduce forgetting and address drift, whereby the memories’ quality degrade away from their original values. In the rest of this section we discuss the architecture, objective and storage we propose.
3.2 VECTOR QUANTIZED VAE
Variational Autoencoders (VAE) (Kingma & Welling, 2013) consist of two parts: the encoder network parameterizes the posterior distribution q(z|x) and the decoder network p(x|z) aims to reconstruct the original input x from the inferred latent variables z. In a standard VAE the prior and posterior distributions are usually Gaussian with diagonal covariance. On the other hand Vector Quantized Autoencoders (VQ-VAE) use a discrete latent representation instead (van den Oord et al., 2017). This model additionally keeps an embedding table E ∈ RK×D, consisting of K vectors of size D. Given an input (e.g. an RGB image), the encoder first encodes it as a Hh×Wh×D tensor, where Hh and Wh denote the height and width of the latent representation. Then, every D dimensional vector goes through a discretization bottleneck using a nearest-neighbor lookup on the embedding table. Specifically, zij = argmine∈E ||enc(x)ij − e||2. The output of the discretization step is then fed through the decoder. The gradient of this non-differentiable step is approximated using the straight-through estimator. A key property to notice is that to reconstruct the input, only the Hh × Wh indices are required, thus yielding very powerful compression (van den Oord et al., 2017). The full VQ-VAE objective, Lvq is given in van den Oord et al. (2017).

heading: 3.3 STACKED QUANTIZATION MODULES

text:
To ensure adaptivity of the compression model, we adopt a Stacked Quantization Modules (SQM). Each module contains a VQ-AE and a corresponding index buffer of adaptive capacity. Its input is the z(i−1)q from the previous layer. A full diagram of the Stacked Quantization Modules (SQM) is given in Figure 1. Each module reconstructs its input from latent representation ziq , where BITS(ziq) < BITS(z (i−1) q ). Here BITS denotes the memory in bits used by the encoding. The compression rate at a given block is given by
H ×W × C × log2 (256) Nc ×Hhi ×Whi × log2 (Ki)
Thus the compression rate is controlled by: Ki, the number of embeddings in the codebooks of block i, the spatial dimension of the latent rep (Hhi, Whi) and the number of codebooks Nci.
VQVAE-2 (Razavi et al., 2019) also uses a multi-scale hierarchical organization, where unlike our SQM the top level models global information such as shape, while the bottom level, conditioned on the top one, models local information. While this architecture is tailored for generative modeling, it is less attractive for compression, as both the bottom and top quantized representations must be stored for high quality reconstructions.
Notably unlike VQVAE-2 (Razavi et al., 2019), each module is learned greedily without backward communication between modules using the current estimate of z(i−1)q similar to Belilovsky et al.
(2019); Nøkland & Eidnes (2019). This formulation is important for allowing the modules to each converge as quickly as possible at their respective resolution. In other words a subsequent block is not required to build representations which account for all levels of compression, thus minimizing interference across resolutions. This rapid convergence is particularly important for the case of online continual learning.

heading: 3.4 MULTI-LEVEL STORAGE

text:
Our aim is to store the maximum number of samples in the allotted C bytes of storage, while assuring their quality, and our ability to reconstruct them. The SQM allows us to implement a Multi-Level storage, wherein each module stores samples at its respective scale. Samples are stored at different levels based on the compressors’ current ability to compress them. When replay occurs, a sample may be able to propogate into a lower level (and thus permit more samples to enter the storage). This process is summarized in Algorithm 2. In practice, both the SQM training and the sample recompression are done in a single forward pass, allowing for fast training.
Such an approach is particularly helpful in the online continual learning setting and allows knowledge retention before the compressor network has learned a valid representations. Note that as per Algorithm 2, samples can be completely uncompressed until the first module is able to effectively encode them. This can be crucial in some cases, if the compressor has not yet converged, to avoid storing poorly compressed representations. Further taking into account that compression difficulty is not the same for all datapoints, this allows use of more capacity for harder data, and fewer for data.
We also note, since we maintain stored samples at each module and the modules are decoupled, that such an approach allows to distribute training the individual modules in parallel and in an asynchronous manner (Belilovsky et al., 2019).

heading: 3.5 MULTI-LEVEL RESERVOIR SAMPLING

text:
Reservoir Sampling (RS) is a critical component of selecting a representative set of samples in continual classification Chaudhry et al. (2019). Its popularity is due to two reasons. First, it gives in expectation a sample representative of the whole data stream. Second, it is a conceptually simple algorithm, easy to implement, and gives strong empirical results. Indeed more sophisticated approaches can often be outperformed by basic RS in Chaudhry et al. (2019).
With this motivation, we need to adapt RS to a multi-level storage settings. There a few challenges. First, in our model the capacity in terms of samples is not fixed. RS adds a new point with prob. p = buffer capacitypoints seen so far . However in practice, the buffer capacity actually increases as the compressor network gets better. We therefore estimate it using the current capacity at the time of buffer addition. In the same vein, one could argue that in practice the compressor network’s sample capacity is actually bigger than the amount of samples it is currently storing since old samples were added when the buffer was less performant. However, since the points get re-compressed during rehearsal, this issue is mostly resolved.
Sample selection for deletion and sampling is also more complex than in standard RS. While it would be more advantageous to remove datapoints from the least compressed representation level, doing so introduces a bias; some classes may be harder to compress, and removing them more frequently would result in more forgetting of said class. To address this issue, we perform all buffer deletion (and insertion) agnostic to the level of the sample. When memory must be freed, samples are deleted from every block such that their relative memory consumption does not change.

heading: 3.6 PUTTING IT ALL TOGETHER - ONLINE COMPRESSION SQM

text:
The online continual compression is overall summarized in Algorithm 1. Incoming data is added to memory as described in Algorithm 4 and along with randomly sampled data from storage is used to update the current SQM model. The randomly sampled data also updates its representation in storage as per Algorithm 3. Algorithm 2 describes the multilevel compression scheme. Note that Algorithm 1 can be run on its own or concurrently with a downstream application (e.g. online continual classification) which would use the same batch order as well as independently during a data collection phase.
Algorithm 3: UpdateBufferRep Input: MemoryM, Autoencoder AE with L
levels, data D, distortion threshold dth 1 for x ∈ D do 2 hidx, blockid = AdaptCompress(x, AE, dth)
3 % Delete Old Repr. 4 DELETE(M[x]) 5 % Add new one 6 ADD(M, hidx) 7 end
Algorithm 4: AddToMemory Input: MemoryM with capacity C (bytes), sample x
1 Nreg = CBY TES(x) 2 capacity = max( Nreg , NUM SAMPLES (M) ) 3 %Probability of adding x 4 add ∼ B( capacitySAMPLE AMT SEEN SO FAR ) %Bernoulli 5 if add then 6 hidx, blockid = AdaptCompress(x, AE, dth) 7 while BITS(hidx) - FREE SPACE(M) > 0 do 8 DELETE RANDOM(M) 9 end
10 end

heading: 4 EXPERIMENTS

text: We evaluate the efficacy of the proposed methods on a suite of canonical and new experiments. In Section 4.1 we present results on standard supervised continual learning benchmarks on CIFAR10. In Section 4.2 we evaluate other downstream tasks such as standard iid training applied on the storage at the end of online continual compression. For this evaluation we consider larger images from Imagenet, as well as on lidar data.

heading: 4.1 ONLINE CONTINUAL CLASSIFICATION

text:
Although CL has been studied in generative modeling (Ramapuram et al., 2017; Lesort et al., 2018; Zhai et al., 2019; Lesort et al., 2019) and reinforcement learning (Kirkpatrick et al., 2017; Fernando et al., 2017; Riemer et al., 2018), supervised learning is still the standard for evaluation of new methods. Thus, we focus on the online continual classification of images for which our approach can provide a complement to experience replay. In this setting, a new task consists of new image classes that the classifier must learn, while not forgetting the previous ones. The model is only allowed one pass through the data (Lopez-Paz et al., 2017; Chaudhry et al.; Aljundi et al., 2019; Chaudhry et al., 2019). The online compression here takes the role of replay buffer in replay based methods such as Chaudhry et al. (2019); Aljundi et al. (2019). In short, we apply Algorithm 1, with an additional online classifier being updated at line 13.
Here we consider the more challenging continual classification setting often referred to as using a shared-head (Aljundi et al., 2019; Farquhar & Gal, 2018; Aljundi et al., 2018). Here the model is not informed of the task (and thereby the subset of classes within it) at test time. This is in contrast to other (less realistic) CL classification scenarios where the task, and therefore subset of classes, is provided explicitly to the learner (Farquhar & Gal, 2018; Aljundi et al., 2019).
For this set of experiments, we primarily report accuracy, i.e. 1
T
∑T i=1 RT,i, and forgetting, i.e.
1 T − 1 ∑T−1
i=1 max(R:,i)−RT,i with R ∈ RTxT representing the accuracy matrix where Ri,j is the test classification accuracy on task j when task i is completed.
Baselines A basic baseline for continual supervised learning is Experience Replay (ER). It consists of storing old data in a buffer to replay old memories. Due to its very simple nature, this baseline was often omitted in continual learning papers. However, recent research made it clear that it is a critical baseline to consider, and in some settings is actually state-of-the-art (Chaudhry et al., 2019; Aljundi et al., 2019; Rolnick et al., 2018). SQM can be viewed as an add-on to ER that incorporates online continual compression. In addition we consider the following baselines. iid online (upper-bound) trains the model with a single-pass through the data on the same set of samples, but sampled iid. iid offline (upper-bound) evaluates the model using multiple passes through the data, sampled iid. We use 5 epochs in all the experiments for this baseline. fine-tuning trains continuously upon arrival of new tasks without any forgetting avoidance strategy. iCarl (Rebuffi et al., 2017) incrementally classifies using a nearest neighbor algorithm, and prevents catastrophic forgetting by using an stored samples. GEM (Lopez-Paz et al., 2017) uses stored samples to avoid
increasing the loss on previous task through constrained optimization. It has been shown to be a strong baseline in the online setting. It gives similar results to the recent A-GEM Chaudhry et al.. ER-MIR (Aljundi et al., 2019) controls the sampling of the replays to bias sampling towards samples that will be forgotten. We note that the ER-MIR critera is orthogonal to SQM, and both can be applied jointly. We leave this as future work.
We evaluate with the standard CIFAR-10 split (Aljundi et al., 2018), where 5 tasks are presented sequentially, each adding two new classes. Evaluations are shown in Table 1. Due to our improved storage of previous data, we observe significant improvements over the other methods and baselines at various memory sizes. This is despite the drifting representation and decoder model. We can contrast SQM’s performance with ER’s to understand the net impact of our compression scheme. Specifically, SQM improves over ER by 12.4% and 13.1% in the M=20 and M=50 case, highlighting the effectiveness of online compression. Our approach only lags ER-MIR in forgetting in the M=50 setting. However, this method is orthogonal to ours and could thus be used jointly.
We also implemented the baseline of Riemer et al. (2018) that uses a discrete autoencoder with gumbel softmax (Jang et al., 2016). To compare directly to the other authors setup we benchmarked our implementation on the Incremental CIFAR-100 multi-head experiment Lopez-Paz et al. (2017). By using our (more sophisticated) architecture, we were able to get 60.3 vs the reported 43.7 using a buffer of size 200. While SQM performs similarly in this setting (65.1), its compressed representations incur significantly less drift compared to Riemer et al. (2018). In the single head setting, this distortion becomes much more problematic as the classifier learns to assign old labels to blurry images, leading to poor performance. We show an example of this drift in Fig. 4 in the Appendix.
The CIFAR-10 dataset has a low resolution (3 × 32 × 32) and uses a lot of data per task (10K samples). These two characteristics might leave the online compression problem easier than in a real-life scenario. Specifically, if the first tasks are long enough and the compression rate is not too large, the model can quickly converge and thus not incur too much representation drift. Indeed, we found that using a single module worked best for this task, as adding more modules was not worth the additional storage cost. For these reasons, we study the adaptive instantiation of our proposed method (A-SQM) in more challenging settings presented in the next section.

heading: 4.2 OFFLINE EVALUATION ON LARGER IMAGES AND LIDAR

text:
Besides the standard continual classification setup, we propose several other evaluations to determine the effectiveness of the stored data and compression module after learning online compression.
Offline training on Imagenet We compare the effectiveness of the stored memories of SQM after a certain amount of online continual compression. We do this by training in a standard iid way an offline classification model using only reconstructions obtained from the storage sampled after online continual compression has progressed for a period of time. In each case we would have the same sized storage available. We remind the reader that simply having more stored memories does not amount to better performance as their quality may be severely degraded and affected by drift.
We use the mini-imagenet dataset, but resized to 128 × 128, larger than the typical size used as we aim to emphasize the utility of this methods for larger inputs. Online continual compression arrives
using the standard split-minimagenet from Chaudhry et al. (2019), which yields 20 different tasks and 100 classes total. After all samples have been seen and stored as best as possible in storage size C by Algorithm 1, we train a Resnet18 model (similar to the one used in Chaudhry et al. (2019) adjusted for larger input size) using the stored samples. We train with SGD and a learning rate of 0.1, with early stopping using a validation set. The storage size C is equivalent to 1000 uncompressed samples. Results of this evaluation are shown in Table 2.
Using this evaluation we first compare a standard reservoir sampling approach on uncompressed data to a 2 module A-SQM using the same size storage. We observe that performance is drastically increased using the compressed samples. We then use this to perform a series of ablations to demonstrate each component of our proposal is important. First we ablate the modular training, meaning the model is trained end-to-end instead of greedily, which is unable to perform well online. Indeed, we observe that the convergence speed is slower, resulting in fewer samples being stored for the early tasks. Secondly we consider not using the adaptive compression scheme described in Sec 3.4, thus all samples are compressed at the bottom level. This greatly decreases performance, for two reasons: the compressions stored early on are very poor since the model has not converged yet, and the model cannot allocate more capacity to more challenging samples.. We then consider removing the 2nd Module showing that multiple levels aid in performance. We additionally illustrate the change in the amount of samples stored at each level by adaptive storage in Figure 2.
LiDAR Range data can be very large and storage inefficient, it is also often collected by vehicles in potentially changing environments. Efficient storage can be important for having more representative data in downstream applications. Here we show qualitatively several examples of applying this. For this experiment we use the Kitti Dataset (Geiger et al., 2013), which contains 61 LiDAR scan recordings, each belonging to either the “residential”, “road”, “city” environments. The online compression is presented one by one with scans from each environment, we present all the recordings from one environment, before moving on to another. The data is processed as in Caccia et al. (2018), where points from the same elevation angle are sorted in increasing order of azimuth angle along the same row. This yield a 2D grid, making it compatible with the same architecture used in the previous experiments.
We first show qualitative results in Figure 3, using a 3 Block SQM, observe that we are able to effectively reconstruct the LiDAR samples. and that we can easily tradeoff quality with compression. We note that reconstruction quality has been previously linked to performance on downstream tasks such as SLAM Zhang & Singh (2014). Note SQM can also be adapted to use task relevant criteria besides MSE(algo 2 line 9)
We now proceed with a quantitative evaluation of the LIDAR compression. We compare SQM with a 2-Block version of the Gumbel Autoencoder used in Riemer et al. (2017). We note that this baseline is stronger than in the original paper. We used our more sophisticated architecture, along with adaptive compression, which turned out to be essential to make the baseline competitive. In the challenging online continual compression setting, it is crucial that the stored representations remain valid as the model is updated. In Figure 2, We first look at representation drift incurred in the buffered samples. That is, after every task we decode every compressed representation and monitor the distortion with the true lidar scan (Fig. 2). The performance gap is quite stricking: SQM operates with drift values similar to the distortion observed at test time, throughout the whole 50 training task sequence. On the other hand, the representations learned from the Gumbel AE quickly stray away from their original and become unusable. We then analyse the stackability of blocks in SQM. For lidar datasets such as (Geiger et al., 2013), there is a high variance in the complexity of scans, therefore having multiple compression levels enables better storage allocation. In Fig 2, we observe that the difference in recontruction loss between blocks in SQM is small and well-behaved, which is not the case for the Gumbel baseline.

heading: 5 CONCLUSION

text: We have introduced online continual compression. We have shown how replay combined with a novel Multi-level quantization module can allow for the compression model to be learned online and yield a large decodable dataset despite representation and model drift. We have shown effectiveness of this online compression approach on standard continual classification benchmarks, as well as for compressing larger images and lidar data. We believe future work can consider dealing with temporal correlations for video and reinforcement learning tasks, as well as improved prioritization of samples for storage.

heading: A FURTHER DETAILS OF EXPERIMENTS

text:
We include here further details regarding the models used in the Imagenet and CIFAR-10 experiments. For all our experiments, we set D the size of the embedding table equal to 100. For CIFAR10, we use a 1 block SQM, latent size (16 x 16 x 1) where the last index represents the number of codebooks. The codebook here contains 128 embeddings, giving a compression factor of 13.7. For Imagenet, we use a 2 block SQM. The first block has a latent size (32 x 32 x 2), and the second block has a latent size (32 x 32 x 1). All the codebooks have 128 embeddings, giving compression factors of 27.4 and 54.9 respectively.
B VISUAL COMPARISONS
Below we show an example of the image quality of our approach compared to Riemer et al. (2018).

title: STACKED QUANTIZATION MODULES


summaries: The paper addresses the problem of multi-label prediction.  It proposes a method that uses a co-embedding of instances and labels into a joint embedding space in a way that related instances and labels fall close by and unrelated ones fall far away.  For this purpose, embeddings from input space and label space to a common space are learned from training data. At the prediction time, KNN to the embedding of the test instance in the co-embedding space is used to predict relevant labels.

summaries: This paper aims to solve multi-label problems via learning a share embedding space for instances and its label sets. Specifically, the author considers deep neural networks F(x) as an encoder for the instance (either raw input or features) and a shallow MLPs G(y) as an encoder for the label outputs. In the training stage, the instance embedding and its label embedding are forced to be close. An additional constraint is instances with different labels should be far from each other. After training, the inference can be done in the embedding space by looking up the labels of the query’s kNN instances.

summaries: This paper presents a metric learning approach for the multi-label classification problem. It basically maps the input features and the output labels into the same space and then uses k-NN to find the closest labels for each inputs. During training, it minimizes the squared Euclidean distance between the input embedding and label embedding. In the experiments, some image datasets and text datasets are used to compare with several multi-label learning algorithms.

abstractText: Multi-Label Learning task simultaneously predicting multiple labels has attracted researchers’ interest for its wide application. Metric Learning crucially determines the performance of the k nearest neighbor algorithms, the most popular framework handling the multi-label problem. However, the existing advanced multiple-label metric learning suffers the inferior capacity and application restriction. We propose an extendable and end-to-end deep representation approach for metric learning on multi-label data set that is based on neural networks able to operate on feature data or directly on raw image data. We motivate the choice of our network architecture via a Bidirectional Representation learning where the label dependency is also integrated and deep convolutional networks that handle image data. In multi-label metric learning, instances with the more different labels will be dragged the more far away, but ones with identical labels will concentrate together. Our model scales linearly in the number of instances and trains deep neural networks that encode both input data and output labels, then, obtains a metric space for testing data. In a number of experiments on multi-labels tasks, we demonstrate that our approach is better than related methods based on the systematic metric and its extendability.

authors:
Emily M Hand
Carlos Castillo
Rama Chellappa

title: Doing the best we can with what we have: Multi-label balancing with selective learning for attribute prediction

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Chen Huang
Yining Li
Chen Change Loy
Xiaoou Tang

title: Learning deep representation for imbalanced classification

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
James T Kwok
Ivor W Tsang

title: Learning with idealized kernels

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

authors:
Weiwei Liu
Ivor W Tsang

title: Large margin metric learning for multi-label prediction

venue: In TwentyNinth AAAI Conference on Artificial Intelligence,

authors:
Weiwei Liu
Donna Xu
Ivor W Tsang
Wenjie Zhang

title: Metric learning for multi-output tasks

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Jiwen Lu
Gang Wang
Weihong Deng
Pierre Moulin
Jie Zhou

title: Multi-manifold deep metric learning for image set classification

authors:
Qi Mao
Ivor Wai-Hung Tsang
Shenghua Gao

title: Objective-guided image annotation

venue: IEEE Transactions on Image Processing,

authors:
Marc Niethammer
Roland Kwitt
Francois-Xavier Vialard

title: Metric learning for image registration

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

title: Survey of nearest neighbor techniques

authors:
Hyun Oh Song
Yu Xiang
Stefanie Jegelka
Silvio Savarese

title: Deep metric learning via lifted structured feature embedding

authors:
Shibin Parameswaran
Kilian Q Weinberger

title: Large margin multi-task metric learning

venue: In Advances in neural information processing systems,

authors:
Xiaobo Shen
Weiwei Liu
Ivor W Tsang
Quan-Sen Sun
Yew-Soon Ong

title: Compact multi-label learning

authors:
Farbound Tai
Hsuan-Tien Lin

title: Multilabel classification with principal label space transformation

venue: Neural Computation,

authors:
Xinshao Wang
Yang Hua
Elyor Kodirov
Guosheng Hu
Neil M Robertson

title: Deep metric learning by online soft mining and class-aware attention

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Kilian Q Weinberger
Lawrence K Saul

title: Distance metric learning for large margin nearest neighbor classification

venue: Journal of Machine Learning Research,

authors:
Min-Ling Zhang
Zhi-Hua Zhou

title: Ml-knn: A lazy learning approach to multi-label learning

venue: Pattern recognition,

authors:
Yi Zhang
Jeff Schneider

title: Multi-label output codes using canonical correlation analysis

venue: In Proceedings of the fourteenth international conference on artificial intelligence and statistics,

title: Maximum margin output coding

authors:
Fang Zhao
Yongzhen Huang
Liang Wang
Tieniu Tan

title: Deep semantic ranking based hashing for multi-label image retrieval

authors:
Zhi-Hua Zhou
Min-Ling Zhang

title: Multi-instance multi-label learning with application to scene classification

venue: In Proceedings of the 19th International Conference on Neural Information Processing Systems,

heading: 1 INTRODUCTION

text:
We consider the problem of multi-label classification, because it wide application. For example, in document classification, one document can cover different topics; in computer vision, one scene image can contain multiple semantic classes like mountain, beach and sea. We address the problem via metric learning approach, where instances with the more different labels move the further away. After the metric learning is completed, the problem is reduced as easy memory-based learning. Thus, the k nearest neighbor (KNN), one of popular and simple methods, can easily handle the multi-label classification. For a new testing instance xtest, the predicted labels are:
y = labels with most instances in{f(xi)Ki=1}, i ∈ Nei(F (xtest)) (1)
f(·) can be a linear mapping, a non-linear RKHS mapping, or neural network-like differentiable function. The performance of kNN significantly relies on the learning of distance metric that computes latent distance between different instances and classes. Kwok and Tsang (Kwok & Tsang, 2003) show that in a single-label prediction task, via pushing two origin nearby instances of different classes further apart with a large margin in RKHS, performance of kNN can be greatly improved. Multi-labels prediction setting, however, restricts the capacity of existing advanced metric learning techniques like the popular LMNN Weinberger & Saul (2009), as different classes can range from a few to hundred different labels, but the appropriate distance metric could not be provided. The recent work of multi-label metric learning (Liu et al., 2018) gave a systematic studies on advanced methods and proposed a new paradigm with better performance, but still suffers following limitations: 1) inferior capacity: the metric learning is based on linear projection, it doesn’t learn flexible representation with non-linearity. 2) application restriction: they only handle the hand-craft feature data, but cannon deal with raw image or audio data, or requires pre-processing techniques that may lost key information of the raw data before learning the representation. Therefore, it is non-trivial to break the limitations of existing work and develop capable and extendable framework for solving multi-output learning tasks.
In this work, during training, we project the feature data or directly raw image data into the metric space using neural networks model and incorporate labels information in a bidirectional way. Incorporating labels will exploit the label dependency during learning the metric representation f(·), instead of treating them as independent ones. Integrating F (·) and G(·) in a bidirectional way will allow the model concentrate the instances with identical label and will enable it to get the metric representation of testing data without labels.
Our contributions are two-fold. First, we introduce a simple and well-behaved neural network framework for multi-output task and show how it can motivate via output representation and deep neural networks. Secondly, we demonstrate how this form of neural network framework can be used for scalable and extendable multi-label classification tasks and propose how it extend to other multioutput tasks. Experiments on a number of data sets demonstrate that our model compares favorably both in multi-labels classification performance (micro-F1, example-based F1, precision and accuracy) and extendability (able to modify to more and complex tasks) against state-of-the-art methods for multi-label learning.

heading: 2 METRIC SPACE WITH BIDIRECTIONAL REPRESENTATION

text:
In this section, we provide motivation for a specific neural network model that we will use in the rest of this paper. We consider a basic and simple neural networks framework with the following propagation:
H = σ(WhX + bh) (2)
Mx = WxH + bx (3) My = WyY + by (4)
Here, X and Y are the input features and output labels, respectively. The W s and bs are the weights and bias of corresponding layers. σ(·) denotes an activation function, that incorporate the non-linear propagation, such as the ReLU(·) = max(0, ·). Mx and My have the same shapes, i.e. X and Y are mapped to the same metric space via non-linear multi-layer and single-layer networks. In the following, we show that this basic framework is motivated via outputs representation, and deep convolutional network for visual recognition on multi-label data set.

heading: 2.1 OUTPUTS REPRESENTATION FOR METRIC LEARNING

text:
We consider a metric spaceM in the network embedding defined as mX ∈ Rd (a vector in metric space corresponding to an instance X in input space) with a mapping F (X) parameterized by the networks, i.e.: mX = F (X) (5) Another important component of the proposed framework is to model the relationship between metric space and the outputs set Y ∈ Rq . Since mapping of outputs to metric space are generally unknown in advance, we proposed a new representation, namely Reversed Embedding, In order to leverage the G(Y ) to bridge the connection between metric spaceM and corresponding data X in input space. mY = G(Y ) (6) Specifically, our intuition is that if the output labels of any two instances yi, yj are the same then two corresponding xi, xj in the input space should map very closed to each other in the metric space. To capture this intuition, we minimize the following objective function as an bidirectional representations in the same metric space, given by
min F,G ‖mY −mX‖22 (7)
In a good metric learning, the model should promote discriminative and predictable representation. To obtain a discriminative representation, the instances of the same outputs will not be confused with ones of different outputs. As for a predictable representation, the above approach provides an opportunity to exploit the dependency between input data and outputs in the metric space.

heading: 2.2 NEURAL NETWORK FOR DEEP REPRESENTATION

text:
In the last subsection, we mention that the predictable representation requires dependency between input and outputs. However, in real-world application, two instances for the identical outputs may be very distinct in the input space, while the ones with different outputs may sometime look confusing originally, especially for raw image data. This raised issue lights the challenge to learn the MX = F (X) with sufficient representation capacity. A neural networks model can therefore be built by stacking multiple layers based on the form of Eq 2, where the hidden layer can optionally followed by a point-wise non-linearity. Now, imagine we have to learn an xor mapping from input to metric space, that is non-linear separability, and therefore the non-linear activation like sigmoid or ReLU is applied right after linear mapping to handle it.
Our framework is also extendable, since in this way, we can also learn the unstructured data like image and audio by replacing the linear mapping layer with convolutional layer.
Additionally, for a fixed computational budget, the batch-wise feeding allows us to build a scalable models, a practice that is known to train on a large number of data set. Unlike MMOC and ML-KNN (Zhang & Schneider, 2012; Zhang & Zhou, 2007), there are no quadratic or exponential computational costs during training with respect to the number of instances.

heading: 3 DEEP METRIC LEARNING FOR MULTI-LABEL CLASSIFICATION

text: Having introduced a basic, yet extendable framework for efficient information propagation and integration on both input data and outputs, now we can be back to the multi-label classification task. As outlined in the introduction, we project input training data with integration of output label during metric learning, but in a bidirectional way, then get the metric representation of testing data without labels, finally a simple KNN will obtain the predicted labels. The overall model, a Bidirectional Representation Deep Neural Networks (BiRD-NN) for multi-label metric learning, is schematically depicted in Figure 1

heading: 3.1 SIMPLE EXAMPLE FOR FEATURE INPUT DATA

text:
In the following, we consider F (X) as a two-layer representation network for input X ∈ Rp×n, i.e. n instances of p-feature data. We incorporate the non-linearity σ(·) in the hidden layer of F (x), then the forward representation takes this simple form:
F (X) = Wx(σ(WhX + bh) + bx) (8)
Here,Wh ∈ Rh×p is an input to hidden weights matrix for a hidden layer of h features. Wx ∈ Rd×h is a hidden-to-metric weight matrix and d is the dimension of metric space. bh ∈ Rh and bx ∈ Rd are the corresponding bias vectors. The non-linear activation is defined as σ(·) = ReLU(·) = max(0, ·). For metric learning, we reversely represent the q-labels of each instance, and pull the inputs of the same labels together:
G(Y ) = WyY + by (9)
min G,F n∑ i=1 ‖F (Xi)−G(Yi)‖22 (10)
where Wy ∈ Rd×p, Y ∈ Rp×m and by ∈ Rd, so with F (X), G(Y ) ∈ Rn×d and we can calculate the instance-wise L2 distance. As there are instances with the identical labels mapping to identical G(Y ), their inputs move closed indirectly via F (X) and the minimizing distance objective. The neural network weights W s and bias bs are trained using gradient descent. In this work, we can perform batch gradient descent training the full data-set, which is a viable option as long as data sets fit in memory. Using a instance-wise L2 distance, time requirement is O(n), i.e. linear in the number of instance.
Another constraint for metric learning is that the instances with different labels should move far away in the metric space. In the multi-labels setting, the difference between two instances can be a few labels to hundred labels. Therefore, we can define how far away are two instance in the metric space according to the difference in the labels space. Following Liu et al. (2018)’s work, we define it as ∆(Yi, Yj) using the euclidean metric to measure the distance between instances Xj and Xj and then learn a new distance metric space, which improves the performance of discriminative classification. To let different instances have a margin of ∆(Yi, Yj) in the learning metric space, we have the following objective function.
min F n∑ i max(0,∆(Yi, Yj)− ‖F (Xi)− F (Xj)‖22), j ∈ Nei(F (Xi)),∀j (11)
Here, Nei(F (Xi)) is the k neighbor instance of F (xi). Note here searching the k nearest instance of F (xi) has a time computational cost of O(n2), but with mini-batch stochastic gradient descent training of neural network, we can search neighbors in each mini-batch instead of the whole data set. Let nmini be the number of each mini-batch, then the kNN time cost is O(n2mini), with n/nmini times of kNN for the whole data set. Therefore the time cost of mini-batch kNN is O(nminin). If we set a small nmini, computational complexity is also linear to the number of instances in training stage (In the testing stage, we utilize ball-tree k-NN Nitin Bhatia (2010)).
We leave efficient-mini-batch and dynamic margin extensions for future work.

heading: 3.2 EXTENSION FOR UNSTRUCTURED INPUT DATA

text:
The aforementioned simple example is a shallow model and the training data are hand-crafted feature instead of original data. Fortunately, our framework can be easily extended to more complex application that is involved with unstructured original data like image. Convolutional Neural Networks (CNN) are designed to conduct a task where training inputs are two-dimensional images for computer vision tasks. CNNs can be directly applied in our framework to implement the F (X). Stacking a bunch of convolution layers to learn representation, it is generally call deep representation learning.
Deep representation learning (Goodfellow et al., 2016) has achieved great success due to it high representation capacity and end-to-end learning manner, i.e. the raw images data are fed to the deep neural networks directly without the hand-crafted feature extraction as a pre-processing. There are batch of image pre-processing methods such as such as SE, SIFT and PCA, converting an image to a feature vector, but they are not about learning and might lose key information of the original image, which is inferior to deep representation method based its richer feature learning capacity.

heading: 3.2.1 COMPARISON WITH RECENT DEEP MULTI-LABEL LEARNING

text: In our extended model and the last experimental comparison with a deep multi-label learning model AttCNN (Hand et al., 2018), we implement their convolutional component via 4 stacking convolutional network blocks, each of which contains a 3x3 Convolutional Kernel, BatchNormalization, ReLU and a 2x2 max pool. On the top of the convolutional blocks is 2 layers of full connection networks. This is a tailored and modified version of VGG, but the last layer is changed to make the AttCNN and BiRDNN. 1) the last layer is replaced by a multiple-label(attribution) layer and this model act as a baseline. 2) the last layer is changed to map to a metric space that is shared with the reversed embedding of BiR and the model is call Bidirectional Representation Deep Neural Networks (BiRDNN) for multi-label metric learning. Limitation of AttCNN: it learns multiple labels at simultaneously, but it treats them as independent ones, and dose not exploit the label dependency during learn the representation as BiRDNN does. AttCNN also was affected by the global skewed data distribution, while BiRDNN predicts multiple labels by local information in the metric space.

heading: 4 RELATED WORKS

text: The fields of conventional multi-output metric learning and recent works on neural network earning deep representation inspire us to propose out model. In what follows, we provide brief overview on related works of both fields.

heading: 4.1 CONVENTIONAL MULTI-OUTPUT METRIC LEARNING

text:
A number of approaches for multi-output metric learning have been proposed in the past decades, most of which only handle hand-crafted feature data and involve two main approaches: encodingdecoding projection and large margin constraints. Prominent examples for encoding-decoding projection variant include out encoding (Zhang & Schneider, 2012), and canonical correlation analysis (Zhang & Schneider, 2011). Liu & Tsang (2015) and Parameswaran & Weinberger (2010) designed large margin constraints for metric learning on multi-out data.
Recently, attention has shifted to models that can be applied to large-scales data sets. CoHasing (Shen et al., 2018) compressed input and output to compact binary embedding, thus align the input and output space, and the prediction is very efficient. LMMO-kNN (Liu et al., 2018) proposed several strategies to speed up the training and testing time after a systematic review is given. For all these methods, however, a multi-step pipeline is required where each step has to be optimized separately, and most of them only handle hand-crafted feature data.

heading: 4.2 DEEP METRIC LEARNING OR DEEP MULTI-LABEL LEARNING

text:
Deep networks that not only map from representation to output but also learn representation itself have recently proposed. Learned representation often result in better performance than that can be obtained with hand-designed representation or hand-crafted features. In the context of metric learning on multi-label data set, there are recent researches on the single field of them: deep metric learning or deep multi-label learning.
For deep metric learning, Multi-Manifold Deep Metric Learning (MMDML) (Lu et al., 2015) learn multiple sets of non-linearly map of multi-class images to a shared feature space, under which the margin of different class manifold is maximized. A deep metric learning variant (Niethammer et al., 2019) was proposed to address the image registration in medical image analysis. The sample mining methods for deep metric learning are reviewed and (Online Soft Mining) OSM is proposed in Wang et al. (2019) Lifted Structured Feature Embedding (Oh Song et al., 2016) is proposed to improve the deep metric learning in terms of F1 and NMI measures for clustering task and recall@K score for retrieval tasks.
For deep multi-label learning, SH+CNN (Zhao et al., 2015) is a deep semantic ranking based method image retrieval via learning hash functions on multi-label images, breaking the bottleneck of early ones that only handle the simple binary similarity. LMLE (Huang et al., 2016) and CRL (Dong et al., 2018) are proposed to rectify the class skew distribution when learning on multi-label image data set, but their work treat each label as independent one and process them one by one. Recently, MultiAttribute CNN (AttCNN) (Hand et al., 2018) in proposed for multi-attribution image classification
where 40 labels of image are trained and test simultaneously in a deep CNN architecture. In this paper, we will use the last one as a baseline in the multi-label image classification task. From the best of our knowledge, we are the first attempt on deep multi-label metric learning that also considers the output dependency during learning the representation.

heading: 5 EXPERIMENTS

text: We test our model in a variety of real-world multi-label experiments: We first compare a simple implement of our BiR with several state-of-the-art multi-label metric prediction methods on the a series of conventional feature data. Then we compare our deep representation implement, BiRDNN, with the recent deep multi-label learning on a raw image data set.

heading: 5.1 DATA SETS

text:
For the simple implement example, we closely follow the experimental setup in Liu et al. (2018). Data set statistics are summarized in Tabel 1. All data are available on the website1.
For the deep deep representation implement BiRDNN, we use the raw image dataset, called scene 2000, that is available online2 with both processed and raw data set. The data set consists of 2,000 natural scene images each of which that contain one or more of the following objects: desert, mountains, sea, sunset, and trees. Several typical images of this data set has been showed in the Figure 1

heading: 5.2 EXPERIMENTAL SETUPS

text:
For a simple example, we train a shallow BiR as described in Section 3.1 and systematically evaluate performance by the micro-F1 measure and example-based-F1 measures. These two measures are described and analyzed in Mao et al. (2012) and applied on the same data set and baselines in Liu et al. (2018). 10-fold cross validation is conducted to get the mean and standard deviation.
For the BiRDNN, to make a fair comparison, we implement an identical CNN architecture with that of our baseline AttCNN as the bottom part BiRDNN’s F (X). We train both models for a maximum of 200 epochs (training iterations) using Adam (Kingma & Ba, 2014) with a learning rate of 0.001. We initialize weights using the xavier uniform distribution for Full-Connection layers and the normal distribution for Convolution layers. We prevent the models from over-fitting with a Dropout rate of 0.5 in the Full-Connection layers.

heading: 5.3 BASELINES

text:
We compare our simple implement of BiR against the same baseline methods and the proposed one in Liu et al. (2018), i.e. PLST (Tai & Lin, 2012), MMOC (Zhang & Schneider, 2012), kNN,MLkNN (Zhang & Zhou, 2007), and LMMO-kNN (Liu et al., 2018).
We further compare our deep representation implement BiRDNN against a recent deep multi-label neural networks, AttCNN, proposed in Hand et al. (2018) over a multi-label image data set. To make a fair comparison, we tailed the AttCNN for these experiments, and implemented AttCNN and BiRDNN with the same convolutional component: 4 convolutional network blocks is stacking,
1http://mulan.sourceforge.net 2http://lamda.nju.edu.cn/files/miml-image-data.rar
and each of them contain a 3x3 convolutional filter, BatchNormalization, ReLU and a 2x2 max pool. The input image is (128, 128, 3) of (width,height,channel), and the numbers of output channels in the convolutional filters are 192, 256, 512, and 1024, respectively. Although it may not the best tailed implement, but it is capable to demonstrate our work. On the top of the convolutional blocks is 2 layers of full connection networks. The output layer of AttCNN contains 5 node that is same as the number of labels in these experiments.
By the way, we cite the result of original work, MIML (Zhou & Zhang, 2006) who published this dataset. MIML trained its model after a hand-crated pre-processing to extract feature vectors, which is different from the above 2 deep networks that learns directly on the raw image in an end-to-end manner. Nevertheless, comparing their result in detail helps us get a insight to discuss our model and feature work.

heading: 6 RESULT

heading: 6.1 SIMPLE EXAMPLE FOR FEATURE INPUT DATA

text:
Results of the simple example of BiR are summarized in Table 2 and 3. For the feature input dataset, we report the Micro-F1 and example-based-F1 with the 10-fold validation on each dataset. The reason with using these measures was analyzed in Mao et al. (2012). Result for all other baseline method are taken from the paper Liu et al. (2018).
Here, the basic and simple example of our model merely acts as shallow and nonlinear projection from hand-crafted feature to metric space. Nevertheless, it addressed these multi-label metric learning problems and outperformed the baseline in most of the data sets.

heading: 6.2 BIDIRECTIONAL REPRESENTATION DEEP NEURAL NETWORKS

text:
We compare deep natural network implementation out model (BiRDNN) with AttCNN Hand et al. (2018) with identical convolutional network paper on raw scene image dataset. We also take the
result of MIML from the previous work Zhou & Zhang (2006) that learning the pre-processed feature on the same dataset instead of the raw data. Results are summarized in the Tables 4.
Because in the scene image data, there are much more negative samples than positive samples in all labels/tags, so AttCNN tends to mis-classify positive to negative, but tends not to mis-classify negative to positive. Therefore, false negative(fn) samples is more than false positive(fp) samples, so precision(tp/(tp + fp)) is greater than accuracy (tp + tn)/(tp + tn + fp + fn). MIML is likely not affected by the positive and negative distribution. BiRDNN uses the identical convolution component with AttCNN, but with the bidirectional representation it obtained better performance, and the metric learning predicts label via local information, the global skewed data distribution does not degenerate the result much.

heading: 7 DISCUSSION

heading: 7.1 MULTI-LABEL CLASSIFICATION MODEL

text: In the experiment demonstrate here, our simple example method for multi-label classification outperforms recent methods. Method based on output coding (Zhang & Schneider, 2012; Zhang & Zhou, 2007; Liu et al., 2018) are most likely limited to the capability of the feature mapping, or let say representation learning. The AttCNN (Hand et al., 2018) on the other hand is limited by the fact that it ignore the label dependency. Our proposed framework can overcome both limitations. In the framework of BiR, first we can implement the non-linear mapping easily just via 2 full-connection layers with an activation in the hidden layer. Moreover, the input and output representation share the same embedding when learning the metric space, thus the label dependency is exploited. For extensions, we can replace the full-connection networks by the more deeper convolutional to learn the representation for image data directly.

heading: 7.2 EXTENDIBILITY TO OTHER MULTI-OUT TASK

text: We have proposed and demonstrate a capable and extendable metric learning framework for multilabel classification(MLC). Our framework can extend to multi-target regression (MTR) where the binary label is replaced by real value as well as the multi-concept retrieval(MCR).

heading: 7.3 LIMITATION AND FUTURE WORKS

text:
Here, we outline several limitations of our current work and how these might be overcome in future work.
(1) Testing time: After learning the discriminative and predictive metric space, we found the test stage is still not ideally fast enough using the on-the-shelf kNN tools. (2) Larger data set: Due the limited computational resource we can handle currently, we complete the experiment on the scene dataset with 2000 raw images that is not really large data set like the CelebA. Our future work will be conducted in larger and challenging data sets.

heading: 8 CONCLUSION

text: We have proposed a novel framework, BiR, for metric learning on multi-label data in including hand-crafted features and raw images. Our BiR frame uses an efficient bidirectional representation that incorporates label information when learning the discriminative and predictive metric space where input data are projected into. Experiments on a number of multi-label data sets suggest that the proposed BiR framework is capable of learning the representation for multi-label classification. In this setting, our model outperforms several recently proposed methods by a significant margin, while being extendable for more multi-output learning tasks and more complex applications.