summaries: The paper provides good baselines for predicting edits in a text (evaluated on source code) learned from a history of changes. This is an interesting problem that has not beed systematically studied in literature, with the exception of several sporadic works from the software engineering community. Fully predicting the code text writing process as opposed to the code itself is an interesting task with possible big impact, IF the accuracy of this edit model manages to significantly outperform simple left-to-right code text prediction techniques.

summaries: The authors study building models for edits in source code. The application is obvious: a system to accurately predict what the next edit should be would be very valuable for developers. Here, edits are modeled by two types of sequences: one that tracks the state of all edits at each time step (and is thus very long), and one that contains the initial step and a changelist that contains the minimal information required to derive the state at any time. The authors train models on top of both of these representations, with the idea being to match the performance of the explicit (heavy) model with the implicit model. This is shown to be challenging, but a clever model is introduced that achieves this, and is thus the best of both worlds. There are synthetic and real-world code (text) edit experiments.

abstractText: Programming languages are emerging as a challenging and interesting domain for machine learning. A core task, which has received significant attention in recent years, is building generative models of source code. However, to our knowledge, previous generative models have always been framed in terms of generating static snapshots of code. In this work, we instead treat source code as a dynamic object and tackle the problem of modeling the edits that software developers make to source code files. This requires extracting intent from previous edits and leveraging it to generate subsequent edits. We develop several neural networks and use synthetic data to test their ability to learn challenging edit patterns that require strong generalization. We then collect and train our models on a large-scale dataset consisting of millions of fine-grained edits from thousands of Python developers. From the modeling perspective, our main conclusion is that a new composition of attentional and pointer network components provides the best overall performance and scalability. From the application perspective, our results provide preliminary evidence of the feasibility of developing tools that learn to predict future edits.

authors:
Miltiadis Allamanis
Charles Sutton

title: Mining source code repositories at massive scale using language modeling

venue: In Proceedings of the 10th Working Conference on Mining Software Repositories,

title: Mining idioms from source code

venue: In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering,

authors:
Miltiadis Allamanis
Earl T. Barr
Premkumar Devanbu
Charles Sutton

title: A survey of machine learning for big code and naturalness

venue: arXiv preprint arXiv:1709.06182,

authors:
Dzmitry Bahdanau
Kyunghyun Cho
Yoshua Bengio

title: Neural machine translation by jointly learning to align and translate

authors:
Avishkar Bhoopchand
Tim Rocktäschel
Earl Barr
Sebastian Riedel

title: Learning python code suggestion with a sparse pointer network

venue: arXiv preprint arXiv:1611.08307,

authors:
Pavol Bielik
Veselin Raychev
Martin Vechev

title: PHOG: probabilistic model for code

venue: In International Conference on Machine Learning,

authors:
Emily L Denton
Soumith Chintala
Arthur Szlam
Rob Fergus

title: Deep generative image models using a laplacian pyramid of adversarial networks

venue: In Advances in neural information processing systems,

authors:
Karol Gregor
Ivo Danihelka
Alex Graves
Danilo Rezende
Daan Wierstra

title: DRAW: A recurrent neural network for image generation

authors:
Rahul Gupta
Soham Pal
Aditya Kanade
Shirish Shevade

title: Deepfix: Fixing common c language errors by deep learning

authors:
Vincent J Hellendoorn
Premkumar Devanbu

title: Are deep neural networks the best choice for modeling source code

venue: In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering,

authors:
Abram Hindle
Earl T. Barr
Zhendong Su
Mark Gabel
Premkumar Devanbu

title: On the naturalness of software

venue: In International Conference on Software Engineering,

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

authors:
Diane Hu
Laurens Maaten
Youngmin Cho
Sorin Lerner
Lawrence K Saul

title: Latent variable models for predicting file dependencies in large-scale software development

venue: In Advances in Neural Information Processing Systems,

authors:
Tero Karras
Timo Aila
Samuli Laine
Jaakko Lehtinen

title: Progressive growing of gans for improved quality, stability, and variation

venue: In International Conference on Learning Representations,

authors:
Jason Lee
Elman Mansimov
Kyunghyun Cho

title: Deterministic non-autoregressive neural sequence modeling by iterative refinement

venue: arXiv preprint arXiv:1802.06901,

authors:
Aodong Li
Shiyue Zhang
Dong Wang
Thomas Fang Zheng

title: Enhanced neural machine translation by learning from draft

venue: arXiv preprint arXiv:1710.01789,

authors:
Wang Ling
Edward Grefenstette
Karl Moritz Hermann
Tomáš Kočiskỳ
Andrew Senior
Fumin Wang
Phil Blunsom

title: Latent predictor networks for code generation

venue: arXiv preprint arXiv:1603.06744,

authors:
Chris Maddison
Daniel Tarlow

title: Structured generative models of natural source code

authors:
Anh Tuan Nguyen
Michael Hilton
Mihai Codoban
Hoan Anh Nguyen
Lily Mast
Eli Rademacher
Tien N Nguyen
Danny Dig

title: Api code recommendation using statistical learning from finegrained changes

venue: In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering,

authors:
Jan Niehues
Eunah Cho
Thanh-Le Ha
Alexander H. Waibel

title: Pre-translation for neural machine translation

venue: In COLING,

authors:
Roman Novak
Michael Auli
David Grangier

title: Iterative refinement for machine translation

venue: arXiv preprint arXiv:1610.06602,

authors:
Rumen Paletov
Petar Tsankov
Veselin Raychev
Martin Vechev

title: Inferring crypto api rules from code changes

venue: In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation,

authors:
Veselin Raychev
Martin Vechev
Eran Yahav

title: Code completion with statistical language models

venue: In Acm Sigplan Notices,

authors:
Veselin Raychev
Pavol Bielik
Martin Vechev

title: Probabilistic model for code with decision trees

venue: In ACM SIGPLAN Notices,

authors:
Mohammad Raza
Sumit Gulwani
Natasa Milic-Frayling

title: Programming by example using least general generalizations

authors:
Tim Rocktäschel
Edward Grefenstette
Karl Moritz Hermann
Tomas Kocisky
Phil Blunsom

title: Reasoning about entailment with neural attention

authors:
Alexander M Rush
Sumit Chopra
Jason Weston

title: A neural attention model for abstractive sentence summarization

venue: In Association for Computational Linguistics,

authors:
Allen Schmaltz
Yoon Kim
Alexander Rush
Stuart Shieber

title: Adapting sequence models for sentence correction

venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,

authors:
Iulian Vlad Serban
Alessandro Sordoni
Yoshua Bengio
Aaron C Courville
Joelle Pineau

title: Building end-to-end dialogue systems using generative hierarchical neural network models

authors:
Richard Shin
Dawn Song
Illia Polosukhin

title: Towards specification-directed program repair

venue: In Workshop Track at International Conference on Learning Representations,

authors:
Ilya Sutskever
Oriol Vinyals
Quoc V Le

title: Sequence to sequence learning with neural networks. In Advances in neural information processing

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Martin White
Christopher Vendome
Mario Linares-Vásquez
Denys Poshyvanyk

title: Toward deep learning software repositories

venue: In Mining Software Repositories (MSR), 2015 IEEE/ACM 12th Working Conference on,

authors:
2019 Pengcheng Yin
Graham Neubig

title: A syntactic neural model for general-purpose code generation. In The 55th Annual Meeting of the Association for Computational Linguistics (ACL), Vancouver, Canada, July 2017

venue: et. One design constraint

title: A queries matrix Q ∈ RD×N

venue: Deviating slightly from Vaswani et al

heading: 1 INTRODUCTION

text:
Source code repositories are in a state of continuous change, as new features are implemented, bugs are fixed, and refactorings are made. At any given time, a developer will approach a code base and make changes with one or more intents in mind. The main question in this work is how to observe a past sequence of edits and then predict what future edits will be made. This is an important problem because a core challenge in building better developer tools is understanding the intent behind a developer’s actions. It is also an interesting research challenge, because edit patterns cannot be understood only in terms of the content of the edits (what was inserted or deleted) or the result of the edit (the state of the code after applying the edit). An edit needs to be understood in terms of the relationship of the change to the state where it was made, and accurately modeling a sequence of edits requires learning a representation of the past edits that allows the model to generalize the pattern and predict future edits.
As an example, consider Figure 1. We show two possible edit sequences, denoted as History A and History B. Both sequences have the same state of code after two edits (State 2), but History A is in the process of adding an extra argument to the foo function, and History B is in the process of removing the second argument from the foo function. Based on observing the initial state (State 0) and the sequence of edits (Edits 1 & 2), we would like our models to be able to predict Edit 3. In the case of History A, the specific value to insert is ambiguous, but the fact that there is an insertion at that location should come with reasonably high confidence.
The main challenge in modeling sequences of edits is in how to develop good representations that will both capture the required information about intent, as well as scale gracefully with the length of the sequence. We consider two representations of edits that we call explicit and implicit representations. The explicit representation explicitly instantiates the state resulting from each edit in the sequence, while the implicit representation instantiates a full initial state and then subsequent edits in a more compact diff-like representation. On the explicit representation we consider a hierarchical recurrent pointer network model as a strong but computationally expensive baseline. On the implicit representation, we consider a vanilla sequence-to-sequence model, and a two-headed attention-based model with a pointer network head for producing edit positions and a content head for producing edit
contents. These models demonstrate tradeoffs that arise from different problem formulations and inform design decisions for future models of edit sequences.
On carefully designed synthetic data and a large-scale dataset of fine-grained edits to Python source code, we evaluate the scalability and accuracy of the models on their ability to observe a sequence of past edits and then predict future edits. We show that the two-headed attention model is particularly well-suited to achieving high accuracy, well-calibrated confidence, and good scalability on the real data, which makes us optimistic about future prospects of developer tools that learn to extract intent from developers as they make edits to large, real code bases. In total, this work formalizes the problem of learning from and predicting edit sequences, provides an initial exploration of model space, and demonstrates applicability to the real-world problem of learning from edits that developers make to source code.

heading: 2 PROBLEM FORMULATION

text:
Implicit vs. Explicit Data Representation. The first question is how to represent edit sequence data. We define two data formats having different tradeoffs. The explicit format (Figure 2 (a)) represents an edit sequence as a sequence of sequences of tokens in a 2D grid. The inner sequences index over tokens in a file, and the outer sequence indexes over time. The task is to consume the first t rows and predict the position and content of the edit made at time t. The implicit format (Figure 2 (b)) represents the initial state as a sequence of tokens and the edits as a sequence of (position, content) pairs.
The explicit representation is conceptually simple and is relatively easy to build accurate models on top of. The downside is that processing full sequences at each timestep is expensive and leads to poor scaling. Conversely, it is easy to build scalable models on the implicit representation, but it is challenging to recognize more complicated patterns of edits and generalize well. We show experimentally in Section 6 that baseline explicit models do not scale well to large datasets of long sequences and baseline implicit models are not able to generalize well on more challenging edit sequences. Ideally we would like a model that operates on the implicit data format but generalizes well. In Section 4 we develop such a model, and in Section 6 we show that it achieves the best of both worlds in terms of scalability and generalization ability.
Notation. A state s is a sequence of discrete tokens s = (s0, . . . , sM ) with sm ∈ V , and V is a given vocabulary. An edit e(t) = (p(t), c(t)) is a pair of position p(t) ∈ N and content c(t) ∈ {DELETE} ∪ V . An edit sequence (which we also call an instance) is an initial state s(0) along with a sequence of edits e = (e(1), . . . , e(T )). We can also refer to the implied sequence of states (s(0), . . . , s(T )), where s(t) is the state that results from applying e(t) to s(t−1).
There are two representations for position. In the explicit representation, p(t) = p(t)e is the index of the token in s(t−1) that c(t) should be inserted after. If c(t) is a DELETE symbol, then p(t)e is the index of the token in s(t−1) that should be deleted. In the implicit representation, we assign indices 0, . . . ,M to tokens in the initial state and indices M + 1, . . . ,M + T to the edits that are made; i.e., if a token is inserted by e(t) then it is given an index of M + t. The position p(t) = p(t)i is the index of the token that the edit should happen after. For example, see Figure 2 (b). The second edit is to
insert a B after the B that was inserted in the first edit. The index of the first B is 6, and the position p (7) i = 6, denoting that the second B should be inserted after the first B.
Problem Statement. We can now state the learning problems. The goal in the explicit problem is to learn a model that maximizes the likelihood of e(t) given s(0), . . . , s(t−1) and the implicit problem is to learn a model that maximizes the likelihood of e(t) given s(0), e(1), . . . , e(t−1) for all t.

heading: 3 BASELINE MODELS

text:
Baseline Explicit Model. The baseline explicit model is a two-level Long Short-Term Memory (LSTM) neural network (Hochreiter & Schmidhuber, 1997) similar to hierarchical RNN models like in Serban et al. (2016). We refer to the hidden vector for the mth token in timestep t as h(t,m) ∈ RD. In the simplest version of the model, the first level LSTM encodes each state sequence s(t) in parallel and produces hidden states h(t,0), . . . ,h(t,M). The second level LSTM takes as input the sequence of h(0,M), . . . ,h(T,M) and produces hidden state h̃(t) ∈ RD and output state o(t) ∈ RD for each time step. We predict the distribution over c(t+1) as softmax(W (out)o(t)), where W (out) ∈ R(|V|+1)×D. To predict p(t+1)e , we use a pointer network construction (Vinyals et al., 2015) where α(t,m) = 〈 o(t),h(t,m) 〉 and P (p(t+1)e = m) ∝ expα(t,m). A useful elaboration is to provide a second path of context for the first level LSTM by concatenating the previous value of the token in the same position as an input. That is, we provide (s(t−1)m , s (t) m ) as input at position (t,m), letting s(−1)m be a special padding symbol. See Figure 3 (a) for an illustration.
Baseline Implicit Model. The natural application of the sequence-to-sequence framework is to consume the initial state s(0) in the encoder and produce the sequence of (p(t)i , c
(t)) pairs in the decoder. The encoder is a standard LSTM. The decoder is slightly non-standard because each action is a pair. To deal with pairs as inputs, we concatenate an embedding of p(t)i with an embedding of c(t). To produce pairs as outputs, we predict position and then content given position.
Formally, for position inputs, we embed each integer m ∈ {0, . . . ,M + T − 1} by taking the mth column of a learned matrix W (p-in) ∈ RD×(M+T ). These are concatenated with content embeddings to produce inputs to the decoder, yielding hidden state h(t) at step t of the decoder. To predict position, we use a matrix W (p-out) ∈ R(M+T )×D and define the distribution over position p(t+1)i as softmax(W (p-out)h(t)). Content is predicted by concatenating h(t) with W (p-in)
:,p(t+1) , the embedding
of the ground truth position, to get h̃(t), and then the predicted distribution over content c(t+1) is softmax(W (c-out)h̃(t)) where W (c-out) ∈ R(|V|+1)×D maps hidden states to content logits.

heading: 4 IMPLICIT ATTENTION MODEL

text:
Here we develop a model that operates on the implicit representation but is better able to capture the sequence of the relationship of edit content to the context in which edits were made. The model is heavily inspired by Vaswani et al. (2017). At training time, the full sequence of edits is predicted in a single forward pass. There is an encoder that computes hidden representations of the initial state and all edits, then two decoder heads: the first decodes the position of each edit, and the second
decodes the content of each edit given the position. The cross-time operations are implemented via the positional encoding and attention operations of Vaswani et al. (2017) with masking structure so that information cannot flow backward from future edits to past edits. Here, we give an overview of the model, focusing on the intuition and overall structure. An illustration appears in Figure 3 (b, c). Further details are in the Appendix, and we refer the reader to Vaswani et al. (2017) for full description of positional encodings, multi-head attention (MHA), and masked attention operations.
Encode Initial State and Edits. The first step is to encode the initial state s = (s0, . . . , sM ) and the edits e = ((p(1)i , c (1)), . . . , (p (T ) i , c
(T ))) into a matrix of hidden states H̃ ∈ RD×(M+T ). We embed tokens and edits independently and then exchange information across the initial sequence and edits by MHA operations. After this step, we hope H̃ includes all of the relevant context about each initial position and edit position. A diagram of the encoder structure appears in Figure 3 (b).
Assemble the Chosen Contexts. The decoder first gathers a matrix of ‘contexts’ U ∈ RD×T where U:,t = H̃:,p(t)i
. Intuitively, this step assembles hidden representations of the contexts in which previous edits were made into a new, more compact and more relevant subsequence.
Predict the Next Positions. The first head of the decoder looks for patterns in the sequence of columns of U . It predicts a query vector ũt from U:,<t that can be interpreted as a prediction of what context is expected to be edited next given the previous contexts that have been edited. The query vector is compared via inner product against each column of H̃ as in Pointer networks (Vinyals et al., 2015) to get a probability distribution over next edit positions: p(p(t)i = m) ∝ exp ũ>t H̃:,m. As an example, consider an edit sequence that appends B after each A in left-to-right order. If the encoder just preserves the identity and position of the corresponding content in H̃ , then the sequence of vectors in U will just be encodings of A with ascending positions. From this, it should be easy to learn to produce a ũt with content of A at a position beyond where the last edit was made.
Predict the Next Contents. The second head of the decoder predicts the content c(t) given all previous edits and the current position p(t)i . It first embeds the contents of all of the edits (c(1), . . . , c(T )) into a matrix of embeddings V ∈ RD×T . Let V̄ be a shifted version of V ; i.e., V̄:,t = V:,t−1 with V:,−1 = 0. In the vanilla decoder, we let A = V̄ +U , which is the simplest way of combining information about previous content embeddings with current position embeddings. We pass A through a masked MHA operation to get Ã. Each column t of Ã is passed through a dense layer and softmax to get predicted logits for c(t).
The analogical decoder (see Figure 3 (c)) is motivated by the intuition that V −U can be thought of as a matrix of analogies, because V encodes the content that was produced at each timestep, and U encodes the context. Intuitively, we might hope that V:,t encodes “insert B” while the corresponding U:,t encodes “there’s a B and then an A,” and the difference encodes “insert whatever comes before A”. If so, then it might be easier to predict patterns in these analogies. To implement this, we let Ū be a shifted version of U and Ā = V̄ − Ū , then we predict the next analogies Ã using MHA operations over Ā. The predicted analogies are added to the unshifted current contexts Ã+U , which
is intuitively the predicted analogy applied to the context of the position where the current edit is about to be made. From this, we apply a dense layer and softmax to predict logits for c(t).

heading: 5 SYNTHETIC DATASETS

text:
To study the ability of the various models to learn specific edit patterns and to isolate the ability to strongly generalize, we developed a suite of synthetic datasets based on regular expression replacements. The datasets are inspired by the kinds of edits we might see in real data, but they are simplified to allow clearer interpretation of results.
The datasets are based on generating a uniformly random initial string s of length L from a vocabulary V of size V . Each dataset is defined by a pattern and replacement. The pattern defines a criterion for matching a position in s and the replacement defines what the pattern should be replaced with. Both pattern and replacement are sequences of characters from V (denoted by A, B, . . .) and meta characters (denoted by x, y, z), plus additional regular expression syntax: parentheses define groups in the pattern, and \N can be used in the replacement to refer to the sequence that was matched in the Nth group. Meta characters will be replaced by different characters from V in each edit sequence. For example, let the pattern be ‘(.)x’ and replacement be ‘\1x\1\1’. We might sample two initial strings BACA and DBBA, and sample x to be replaced with A and B respectively. This would yield edit sequences with the following start and end states: BACA→ BABBCACC and DBBA→ DBDDBA.1
We define a snapshot to be the initial state and each intermediate state where a pattern has been replaced with a full replacement. We require that each synthetic instance be composed of at least four snapshots; otherwise the instance is rejected and we try again with a different random draw of initial state and meta character replacements. In the first example above, the snapshots would be [BACA, BABBCA, BABBCACC]. The full edit sequence is shown in Figure 2 (a). To create the edit sequences, we compute diffs between successive snapshots and apply the edits in the diff one token at a time from left to right. The set of edits that comprise a diff between two snapshots is not unique, and we use Python’s built-in diff library to disambiguate between possible sets of edits. For each synthetic dataset, some number of edits need to be observed before the pattern becomes unambiguous. We call this the number of conditioning steps and give this many edits to the models before including their predictions in the total loss. We also create a “MultiTask” dataset that combines instances from all the above datasets, which is more challenging. A full list of the patterns and replacements that define the datasets appears in the Appendix.

heading: 6 EXPERIMENTS

text: The goal of the experiments is to understand the capabilities and limitations of the models discussed above, and to evaluate them on real data. Two main factors are how accurately the models can learn to recognize patterns in sequences of edits, and how well the models scale to large data. In our first set of experiments we study these questions in a simple setting; in the second set of experiments we evaluate on real data. In this section we evaluate three methods: the explicit model abbreviated as E, the implicit RNN model abbreviated as IR, and the implicit attention model from Section 4 with the analogical decoder abbreviated as IA. In the Appendix we evaluate variants of the implicit attention model that use the vanilla decoder and different update functions inside the MHA operations.

heading: 6.1 EXPERIMENTS ON SYNTHETIC DATA

text:
Accuracy. The first question is how well the various models perform in terms of accuracy. For each of the synthetic tasks described in the Appendix we generated datasets of size 10k/1k/1k instances for train/dev/test, respectively. Initial sequences are of length L = 30, and the vocab size is V = 10. For all meta problems, we give the model conditional steps to let it recognize the meta character for each example. For evaluation, we measure average accuracy for each edit conditional on given past edits, where both position and content must be correct for an edit to be considered correct.
1The semantics are chosen to align with Python’s re library. import re; re.sub(‘(.)B’, r‘\1B \1\1’, ‘DBBA’) yields ‘DBDDBA’.
To better understand how strong of generalization is required, we develop the Position-Oracle MatchPattern (POMP) baseline. POMP assumes an oracle identifies the position where an edit needs to be made and marks the pattern part of the current state (using terminology from Section 5). Predictions for the changes needed to turn the pattern into the replacement are then done via pattern matching. If a test pattern appears anywhere in the training data, POMP is assumed to get all predictions correct; otherwise it guesses uniformly at random. We report the expected performance of POMP. In the cases where POMP achieves low accuracy, few of the patterns seen at test time appeared at training time, which shows that these tasks require a strong form of generalization. We can also interpret POMP as an upper bound on performance of any model based on counts of (pattern, replacement) pairs seen in training data, as would happen if we tried to adapt n-gram models to this task.
In Table 1 we report test performance for the hyperparameter setting and step that yield best dev performance. The explicit model and the improved implicit model can solve nearly all the tasks, even those that involve meta characters and relatively long sequences of replacements. Note that the POMP accuracy for many of these tasks is near chance-level performance, indicating that most test replacements were never seen at training time. In the Appendix, we provide more statistics about the synthetic datasets that give additional explanation for the varying performance across tasks.
Evaluating Scalability. Here we explore questions of scalability as the length of the state and the number of edits grow. We use a simple dataset where the pattern is a single character and the replacement comes from a randomly sampled n-gram language model. In all cases we use n = 3 and set the number of insertions to one of {10, 50, 100}. Note that this simultaneously increases the size of the explicit state (M ) and the number of edits (T ). The scalability metric is the average time required to run training on 128 sequences on a single P100 GPU, averaged over 1000 training steps.
As shown in Figure 4, the explicit model is consistently more expensive than the implicit models, and the gap grows as the size of the data increases. The length-100 insertion sequences are ten times smaller than the sequences in the real dataset, but already there is an order of magnitude difference in runtime. The attention models generally take 50% to 75% of the time of the implicit RNN models.

heading: 6.2 EXPERIMENTS ON REAL DATA

text:
We have obtained a large-scale dataset of code edits in Python. Each time a developer saved a file, a snapshot was recorded, making the dataset much more fine-grained than other collection methods like Git commits. First, we converted source code into tokens using Python’s built-in tokenization library and then converted tokens into subword tokens using the subword tokenizer of Vaswani et al. (2017) with a target subword vocabulary size of 4096. This yields sequences of snapshots of subword tokens that we process into sequences of edits as described in Section 5. In total the dataset includes 8 million edits from 5700 software developers. We set the number of conditioning steps to 0 for real data. We grouped snapshots into instances involving about 100 edits each, and we pruned instances that included states with more than 1k subword tokens. We divided instances randomly into train, dev, and test with proportions 80%/10%/10%.
For this experiment, we evaluate the performance of the E, IR, and IA models. The subtoken-level test accuracies are 51% for the explicit baseline (E), 55.5% for the implicit baseline (IR), and 61.1% for the improved implicit model (IA). These numbers are calculated using parameters from the step and hyperparameter setting that achieved the best subtoken-level accuracy on the dev set. Our main take-away from these experiments is that the IA model provides a good tradeoff. It achieves the best accuracy, and it had less issue with memory constraints than the explicit model. As we move towards training on larger datasets with longer initial states, we are optimistic about building on the IA model.
Finally, we evaluate the models on their ability to auto-regressively predict a sequence of subtokens up to the next token boundary. We are particularly interested in the setting where models only make predictions when they are confident, which could be important for usability of an eventual edit suggestion system. To decode we use a greedy decoding strategy of generating the most likely next subtoken at each step until reaching the end of a token. As a confidence measure, we use the log probability assigned to the sequence of subtoken predictions.
In Figure 4d, we sort predictions based upon their confidence, and then for each possible confidence threshold we report results. The x-axis denotes the percentile of confidence scores on which we make predictions (so at confidence percentile 75%, we make predictions on the 25% of instances where the model is most confident), and the y-axis shows the average accuracy amongst the instances where a prediction is made. The IA model outperforms the other models across confidence thresholds and when the model is confident, accuracy is correspondingly high. This suggests that the model’s confidence could be useful for deciding when to trigger suggestions in, e.g., an edit suggestion tool.

heading: 7 RELATED WORK

text:
Sequence to Sequence and Attention Models. Modeling sequences of edits could be approached via minor modifications to the sequence-to-sequence paradigm (Sutskever et al., 2014) as in our implicit baseline. For explicit data, we can apply hierarchical recurrent neural network-like models (Serban et al., 2016) to encode sequences of sequences. The baseline explicit model is an elaboration on this idea.
Attention mechanisms (Bahdanau et al., 2015) are widely used for machine translation (Bahdanau et al., 2015), summarization (Rush et al., 2016), and recognizing textual entailment (Rocktäschel et al., 2016). Recently, Vaswani et al. (2017) showed that a combination of attention and positional encodings can obviate the need for standard recurrent connections in autoregressive neural networks. Pointer networks (Vinyals et al., 2015) use an attention-like mechanism to select positions in an input sequence. These are important components for the model in Section 4.
Generation by Iterative Refinement. There are several works that generate structured objects via iterative refinement. The structured objects could be images (Gregor et al., 2015; Denton et al., 2015; Karras et al., 2018), translations (Li et al., 2017; Novak et al., 2016; Niehues et al., 2016; Lee et al., 2018), or source code (Gupta et al., 2017; Shin et al., 2018). These methods produce “draft” objects
that are refined via one or more steps of edits. Of these, the most similar to our work is DeepFix (Gupta et al., 2017), which iteratively predicts line numbers and replacement lines to fix errors in student programming assignments. However, like other iterative refinement methods, the refinement is aimed towards a pre-defined end goal (fix all the errors), and thus is not concerned with deriving intent from the past edits. In DeepFix, for example, the only information about past edits that is propagated forward is the resulting state after applying the edits, which will not generally contain enough information to disambiguate the intent of the edit sequence. Schmaltz et al. (2017) studies the problem of grammar correction. While the use of diff-like concepts is superficially similar, like the above, the problem is phrased as mapping from an incorrect source sentence to a corrected target sentence. There is no concept of extracting intent from earlier edits in order to predict future edits.
To emphasize the difference, note that all the approaches would fail on our Meta problems, because the goal only reveals itself after some edits are observed. Any task or method that has only initial and final states would suffer from the same issues.
Software Engineering and Document Editing. Some work in software engineering has modeled edits to code, but it operates at a coarser level of granularity. For example, Ying et al. (2004); Zimmermann et al. (2005); Hu et al. (2010) look at development histories and identify files that are commonly changed together. Our work is more fine-grained and considers the temporal sequence of edits. There is a large body of work on statistical models of source code (see Allamanis et al. (2017)). There are source code models based on n-grams (Hindle et al., 2012; Allamanis & Sutton, 2013), grammars (Allamanis & Sutton, 2014), neural networks (Raychev et al., 2014; White et al., 2015; Ling et al., 2016; Bhoopchand et al., 2016), and combinations of the two (Maddison & Tarlow, 2014; Yin & Neubig, 2017). Other notable models include Bielik et al. (2016), Raychev et al. (2016), and Hellendoorn & Devanbu (2017). All of these model a single snapshot of code.
Our formulation, in contrast, models the process of constructing code as it happens in the real world. The benefit is there are patterns available in edit histories that are not be present in a static snapshot, and the models are trained to make predictions in realistic contexts. A limitation of our work is that we treat code as a sequence of tokens rather than as tree-structured data with rich semantics like some of the above. However, source code representation is mostly orthogonal to the edits-based formulation. In future work it would be worth exploring edits to tree- or graph-based code representations.
There are few works we know of that infers intent from a history of edits. One such example is Raza et al. (2014). Given past edits to a presentation document, the task is to predict the analogous next edit. A major difference is that they create a high-level domain specific language for edits, and predictions are made with a non-learned heuristic. In contrast, we define a general space of possible edits and learn the patterns, which is better suited to noisy real-world settings. Other such works include Nguyen et al. (2016) and Zimmermann et al. (2005). In comparison to our work, which tries to infer both position and content from full edit histories, Nguyen et al. (2016) predicts only the content, in the form of a method call from an API, given the location. Zimmermann et al. (2005) instead predicts the location of the next change, given the location of the previous change. Both approaches rely on frequency counts to determine correlations between edit pairs in order to produce a ranking, and work at a coarser granularity than tokens. In concurrent work, Paletov et al. (2018) studies the problem of deriving rules for usage of cryptography APIs from changes in code, which is similar in spirit to our work in trying to derive intent from a history of changes to code.

heading: 8 DISCUSSION

text:
In this work, we have formulated the problem of learning from past edits in order to predict future edits, developed models of edit sequences that are capable of strong generalization, and demonstrated the applicability of the formulation to large-scale source code edits data.
An unrealistic assumption that we have made is that the edits between snapshots are performed in left-to-right order. An alternative formulation that could be worth exploring is to frame this as learning from weak supervision. One could imagine a formulation where the order of edits between snapshots is a latent variable that must be inferred during the learning process.
There are a variety of possible application extensions. In the context of developer tools, we are particularly interested in conditioning on past edits to make other kinds of predictions. For example, we could also condition on a cursor position and study how edit histories can be used to improve
traditional autocomplete systems that ignore edit histories. Another example is predicting what code search queries a developer will issue next given their recent edits. In general, there are many things that we may want to predict about what a developer will do next. We believe edit histories contain significant useful information, and the formulation and models proposed in this work are a good starting point for learning to use this information.

heading: Appendix

heading: OVERVIEW

text: • Section A gives more information on the synthetic datasets. • Section B gives additional details for the synthetic data experiments. • Section C gives additional details for the real data experiments. • Section D gives a more detailed description of the IA models and its variants. • Section E gives more details on the variant of multihead attention used in the IA models. • Section F provides additional experiments on the IA model variants.

heading: A ADDITIONAL SYNTHETIC DATASET INFORMATION

text:
The regular expression patterns and replacements that define the synthetic datasets are listed in
Table 2. In this table we also show additional computed properties of the synthetic datasets.
The number of edits per replacement (EPR) helps to explain why some problems are harder than others. Problems that only repeat their context-based action a single time, rather than multiple times, are harder and have correspondingly lower accuracies. For example, MetaContextAppend11 is harder than MetaContextAppend13. This is because accuracy is measured in a setting where the model conditions on ground truth for past edits, so previous correct instances of the action are available for predicting future instances of the action. This is visible in the higher accuracies for those problems with multiple wildcards in their pattern and higher EPR, corresponding to multiple actions.
A higher average context displacement (ACD) also is indicative of harder problems, and correlates with lower accuracies from models E, IA-ag, and IR. ACD measures the distance between characters in the regex patterns and where they are used in the replacement.
We also observe a moderate correlation between accuracy of E, IA-ag, and IR and the accuracy of POMP on the non-meta problems. This suggests the problems where fewer of the test time patterns appeared at training time are harder than those where more of the test time patterns appeared at training time. The IR model in particular tends to have lower accuracy for the problems that have more novel patterns at test time.
D at
as et
Pa tt
er n
R ep
la ce
m en
t E
PR A
C D
PO M
P E
IA -a
g IR
A pp
en d1
A A B
1 0
10 0.
0 10
0. 0
99 .9
10 0. 0 C on te xt A pp en d1 1 (.) A \1 A \1 1 2 10 0. 0 10 0. 0 99 .9 98 .6 C on te xt A pp en d1 3 (.) A \1 A \1 \1 \1 3 3 10 0. 0 10 0. 0 10 0. 0 98 .6 C on te xt A pp en d3 1 (.. .)A \1 A \1 3 4 10 0. 0 99 .5 98 .5 76 .9 C on te xt A pp en d3 3 (.. .)A \1 A \1 \1 \1 9 7 99 .7 99 .6 98 .9 76 .3 C on te xt A pp en d5 2 (.. ... )A \1 A \1 \1 10 8. 5 37 .6 99 .2 99 .3 74 .6 C on te xt R ev er se 31 (.) (.) (.) A \1 \2 \3 A \3 \2 \1 3 4 10 0. 0 99 .4 98 .1 72 .6 C on te xt R ev er se 51 (.) (.) (.) (.) (.) A \1 \2 \3 \4 \5 A \5 \4 \3 \2 \1 5 6 37 .6 99 .0 95 .2 59 .5 D el et e2 A A 2 0 10 0. 0 10 0. 0 99 .9 99 .9 Fl ip 11 (.) A (.) \2 \1 A \2 \1 2 3 10 0. 0 99 .7 98 .8 82 .8 Fl ip 33 (.. .)A (.. .) \2 \2 \2 \1 A \2 \1 \1 \1 18 10 11 .8 98 .7 98 .3 76 .8 R ep la ce 2 A A B B 4 0 10 0. 0 10 0. 0 10 0. 0 99 .7 Su rr ou nd 11 (.) A (.) \1 \1 A \2 \2 2 1 10 0. 0 10 0. 0 99 .8 91 .2 Su rr ou nd 33 (.. .)A (.. .) \1 \1 \1 \1 A \2 \2 \2 \2 18 6 11 .8 99 .6 99 .6 79 .5 M et aA pp en d1 x x y 1 0 10 0. 0 99 .9 83 .0 13 .9 M et aC on te xt A pp en d1 1 (.) x \1 x \1 1 2 10 0. 0 99 .5 96 .3 2. 5 M et aC on te xt A pp en d1 3 (.) x \1 x \1 \1 \1 3 3 10 0. 0 10 0. 0 98 .9 73 .5 M et aC on te xt A pp en d3 1 (.. .)x \1 x \1 3 4 95 .9 95 .7 94 .3 18 .0 M et aC on te xt A pp en d3 3 (.. .)x \1 x \1 \1 \1 9 7 95 .9 99 .3 97 .5 73 .3 M et aC on te xt A pp en d5 2 (.. ... )x \1 x \1 \1 10 8. 5 11 .9 97 .2 97 .5 63 .0 M et aC on te xt R ev er se 31 (.) (.) (.) x \1 \2 \3 x \3 \2 \1 3 4 95 .9 95 .3 94 .4 14 .4 M et aC on te xt R ev er se 51 (.) (.) (.) (.) (.) x \1 \2 \3 \4 \5 x \5 \4 \3 \2 \1 5 6 11 .9 94 .7 92 .4 22 .6 M et aD el et e2 x x 2 0 10 0. 0 10 0. 0 99 .8 94 .9 M et aF lip 11 (.) x (.) \2 \1 x \2 \1 2 3 10 0. 0 99 .1 92 .4 10 .0 M et aF lip 33 (.. .)x (.. .) \2 \2 \2 \1 x \2 \1 \1 \1 18 10 9. 2 97 .5 96 .3 73 .9 M et aR ep la ce 2 x x y y 4 0 10 0. 0 99 .8 98 .5 93 .7 M et aS ur ro un d1 1 (.) x (.) \1 \1 x \2 \2 2 1 10 0. 0 99 .6 98 .5 12 .1 M et aS ur ro un d3 3 (.. .)x (.. .) \1 \1 \1 \1 x \2 \2 \2 \2 18 6 9. 2 99 .1 99 .0 74 .9
Ta bl
e 2:
R eg
ul ar
ex pr
es si
on s
us ed
to ge
ne ra
te th
e sy
nt he
tic da
ta se
ts ,a
nd pr
op er
tie s
of th
e sy
nt he
tic da
ta se
ts .E
di ts
pe rr
ep la
ce m
en t(
E PR
)i s
th e
nu m
be ro
fe di ts re qu ir ed fo ra ty pi ca lr ep la ce m en to ft he pa tte rn w ith th e re pl ac em en t. A ve ra ge co nt ex td is pl ac em en t( A C D )m ea su re s th e av er ag e di st an ce be tw ee n a re ge x ca pt ur e gr ou p in th e pa tte rn an d w he re th e ch ar ac te rs in th at ca pt ur e gr ou p ap pe ar in th e re pl ac em en t.

heading: B SYNTHETIC DATA EXPERIMENTS

heading: B.1 ADDITIONAL EXPERIMENT DETAILS

text: For the synthetic dataset experiments, for each method, we performed a grid search over learning rate (.005, .001, .0005, .0001) and hidden size (128, 256, 512). We use the ADAM optimization algorithm with default Tensorflow settings for other parameters. We clip gradients at 1.0 by global gradients norm.

heading: B.2 ADDITIONAL SCALABILITY EXPERIMENT DETAILS

text: We test all models on hidden sizes (128, 256, 512) with batch size 64. The metric we use for scalability is the average time required to run training on 128 sequences on a single P100 GPU, averaged over 1000 training steps. Under this metric, the explicit model pays an additional cost for its high memory usage. On the larger datasets (and in the code edits dataset), it is not possible to fit a batch size of 64 in memory for hidden size 512, so we need to run several training steps with batch size 32. While this may appear to unfairly penalize the explicit model, this is the tradeoff that we had to face when running experiments on the real data, so we believe it to be an accurate reflection of the practical ability to scale up each type of model.

heading: B.3 ANALYZING ERRORS

text: In Figure 5 we examine the performance of two illustrative synthetic problems at each of the timesteps of prediction. The plots show combined position and content accuracies averaged over validation examples. For all models, this accuracy dips when the target position changes non-trivially between consecutive timesteps, which occurs when a pattern is complete and the model must decide where to edit next. This shows the cross-pattern jumps are the most challenging predictions. For the best performing models, the accuracy stays near 1 when the position merely increments by 1 between timesteps, and decreases for the cross-pattern jumps. In these examples the substitution pattern is of fixed size, so there is regularity on when the cross-pattern jumps happen, and hence also regularity in the dips.

heading: C REAL DATA EXPERIMENTS

heading: C.1 ADDITIONAL EXPERIMENT DETAILS

text:
In this experiment, we evaluate the performance of the E, IR, and IA models on the code edits dataset. For each of these models, we performed a grid search over the hyperparameter space. We evaluate the learning rates .005, .001, .0005, and .0001. For the implicit models, we evaluate the hidden sizes 128, 256, and 512, and batch size 64. For the explicit models, we evaluate hidden sizes 32 and 64 (with batch size 10), 128 (with batch size 5), and 256 and 512 (with batch size 1). We decrease the batch size considered as we increase the hidden size so that the model fits in memory. We trained each model variant on a single P100 GPU for 48 hours.
D IMPLICIT ATTENTIONAL MODEL - LONGER DESCRIPTION

heading: D.1 ENCODER

text:
In contrast to before, here the task of the encoder is to convert the M initial state tokens and the T edits into a matrix of hidden states H̃ ∈ RD×(M+T ). The first M columns represent the context around each position in the initial state, and these embeddings must only depend on s(0). The last T columns represent the context around each token produced by the edit sequence e. The tth of these columns can only depend on s(0) and edits e1, . . . , et.
One design constraint imposed by Vaswani et al. (2017) is that there should be no sequential dependence in the encoder, and we would like to impose the same constraint on our models to aid in scalability. That is, given embeddings of each of the inputs and edits, the hidden states for each of the inputs and edits can be computed in parallel. However, this raises a challenge of how to compute a positional embedding of the tokens generated by edits. Suppose we have an initial sequence ABC and then insert XY after A. How should we encode the position of X and Y such that attention operations in the encoder can produce a hidden representation of Y encoding the information that Y comes one position after X and two positions after A?
Our approach to this problem is to compute the embedding of an edit as a sum of three terms: an embedding of the content, a positional encoding of the explicit position, and a shared learned embedding to represent that the content was produced by an edit (as opposed to being present in the initial state). Note that using the explicit position means that multiple tokens may have the same position; however, the justification is that relative positions still make sense, and the third component of the sum can be used to disambiguate between positions in the initial state and those produced by edits. From the embeddings of initial state and edit sequence, we apply a sequence of MHA operations illustrated in Figure 6 (a) to produce the encoder output H̃ .

heading: D.2 DECODER

text:
Given H̃ , we can use the implicit position indexing illustrated in Figure 6 (b) to reference the hidden state at the position of edit t as H̃
:,p (t) i
. Thus we can assemble a matrix of “contexts” U ∈ RD×T
where U:,t = H̃:,p(t)i for each t. We can also assemble a matrix of “contents” of each edit V ∈ RD×T , where V:,t is an embedding of c(t). Intuitively, we hope the context vectors to capture the relevant context around the position that was chosen (e.g., it is after a B), while the content vectors represent the content of the edit (e.g., in that context, insert a B).
To predict position, we first shift U forward in time to get Ū where Ū:,t = U:,t−1 (letting U:,−1 = 0). We then apply a masked MHA operation to get Ũ = MHA(Ū). The result is used as keys for a pointer network-like construction for predicting position. Specifically, we let αt,m = 〈 Ũ:,t, H̃:,m 〉 be the compatibility between the predicted context Ũ:,t and the mth context in H̃ , and then define
the predicted distribution for position to be P (p(t)i = m) = expαt,m∑
m′ expαt,m′ . See the left column of
Figure 6 (b) and (c) for an illustration of the position prediction component of the decoder.
To predict content c(t), we also condition on p(t)i because of our chosen convention to predict position and then content given position. We consider two content decoders. The “Vanilla" decoder (see Figure 6 (b)) takes the un-shifted contexts matrix U used in the position decoder. Recall that the tth column has an encoding of the context where the tth edit was made. This matrix is added to a shifted version of the content matrix V̄ (i.e., V̄:,t = V:,t−1). Thus, the tth column of the result has information about the content of the previous edit and the context of the current edit. This summed matrix is passed through a separate masked MHA module that passes information only forward in time to yield Ṽ , which incorporates information about previous contents and previous plus current contexts. From this, we predict the distribution over c(t) as softmax(W (c-out)Ṽ:,t).
The “Analogical" decoder (see Figure 6 (c)) is motivated by the intuition that V −U can be thought of as a matrix of analogies, because V encodes the content that was produced at each timestep, and U encodes the context. We might hope that V:,t encodes “insert B” while the corresponding U:,t encodes “there’s a B and then an A,” and the difference encodes “insert whatever comes before A”. If so, then it might be easier to predict patterns in these analogies. To implement this, we construct previous analogies Ā = V̄ − Ū , then we predict the next analogies as Ã = MHA(Ā). The next analogies are added to the unshifted current contexts Ã + U , which is intuitively the predicted analogy applied to the context of the position where the current edit is about to be made. From this, we apply a dense layer and softmax to predict the distribution over c(t).
High level pseudocode is provided below. s2s_mha denotes exchanging information between tokens within the initial state; s2e_mha denotes passing information from tokens in the initial state to edits; e2e_mha denotes exchanging information between edits and applies masking to avoid passing information backward in time.
# Encoder state_embeddings = embed_tokens(initial_state_tokens) state_hiddens = s2s_mha(state_embeddings)
edit_embeddings = embed_edits(edit_positions, edit_contents) edit_hiddens = e2e_mha(edit_embeddings) edit_hiddens = s2e_mha(state_hiddens, edit_hiddens)
H = concat(state_hiddens, edit_hiddens)
# Decoder U = gather(H, target_positions)
# Predict position prev_U = shift_forward_in_time(U) + timing_signal(U) predicted_U = e2e_mha(prev_U) position_logits = pointer_probs(query=predicted_U, keys=H)
# Predict content V = embed_tokens(target_contents) if vanilla_decoder:
prev_V = shift_forward_in_time(V) + timing_signal(V) predicted_V = e2e_mha(U + prev_V)
else: prev_V = shift_forward_in_time(V) + timing_signal(V) predicted_V = e2e_mha(prev_V - prev_U) + U

heading: E ADDITIONAL MULTIHEAD ATTENTION MODULE DETAILS

text:
In its most general form, a multihead attention (MHA) module described in the main text takes as input three matrices:
• A keys matrix K ∈ RD×M , • A values matrix V ∈ RD×M , and • A queries matrix Q ∈ RD×N .
If only one matrix is provided, then it is used as K, V , and Q. If two matrices are provided, the first is used as Q, and the second is used as K and V .
Deviating slightly from Vaswani et al. (2017) by grouping together surrounding operations, the module is composed of the following operations:
• Add positional encoding to Q, • Apply attention to get a result matrix R ∈ RD×N , • Apply an aggregation operation Agg(Q,R) and return the result.
The positional encoding is the same as in Vaswani et al. (2017); we add their sinusoidal positional embedding of integer n to the nth column of Q. The attention operation is the multihead attention operation as described in Vaswani et al. (2017), where we use 8 heads throughout. The aggregation operation is either a simple sum Q + R or a GRU operation. That is, we treat Q as a matrix of previous hidden states and R as inputs, and then we apply the update that a GRU would use to compute the current hidden states. The potential benefit of this construction is that there is a learned gating function that can decide how much to use Q and how much to use R in the final output of the module in an instance-dependent way.
When we use GRU aggregation, we append a g to the method name, and when we use a sum aggregation we do not append a character. Paired with the Vanilla (v) and Analogical (a) decoders described in the main text, this describes all the implicit model variants:
• IA-v: vanilla decoder, sum aggregation, • IA-vg: vanilla decoder, GRU aggregation, • IA-a: analogical decoder, sum aggregation, • IA-ag: analogical decoder, GRU aggregation,

heading: F ADDITIONAL IMPROVED IMPLICIT MODEL EXPERIMENTS

text: We repeated the synthetic experiments from the main paper but on all the implicit attentional model variants. Results appear in Table 3.


summaries: This paper proposed how to learn multi-class classifiers without multi-class labels. The main idea is shown in Figure 2, to regard the multi-class labels as hidden variables and optimize the likelihood of the input variables and the binary similarity labels. The difference from existing approaches is also illustrated in Figure 1, namely existing methods have binary classifiers inside multi-class classifiers while the proposed method has multi-class classifiers inside binary classifiers. The application of this technique to three general problem settings is discussed, see Figure 3.

summaries: The work is a special case of density estimation problems in Statistics, with a use of conditional independence assumptions to learn the joint distribution of nodes. While the work appears to be impressive, such ideas have typically been used in Statistics and machine learning very widely over the years(Belief Propagation,  Topic modeling with anchor words assumptions etc...). This work could be easily extended to multi-class classifications where each node belongs to multiple classes. It would be interesting to know the authors' thoughts on that. The hard classification rule in the paper seems to be too restrictive to be of use in practical scenarios, and soft classification would be a useful pragmatic alternative.

abstractText: This work presents a new strategy for multi-class classification that requires no class-specific labels, but instead leverages pairwise similarity between examples, which is a weaker form of annotation. The proposed method, meta classification learning, optimizes a binary classifier for pairwise similarity prediction and through this process learns a multi-class classifier as a submodule. We formulate this approach, present a probabilistic graphical model for it, and derive a surprisingly simple loss function that can be used to learn neural network-based models. We then demonstrate that this same framework generalizes to the supervised, unsupervised cross-task, and semi-supervised settings. Our method is evaluated against state of the art in all three learning paradigms and shows a superior or comparable accuracy, providing evidence that learning multi-class classification without multi-class labels is a viable learning option.

authors:
Erin L Allwein
Robert E Schapire
Yoram Singer

title: Reducing multiclass to binary: A unifying approach for margin classifiers

venue: Journal of machine learning research,

authors:
Ehsan Amid
Aristides Gionis
Antti Ukkonen

title: Semi-supervised kernel metric learning using relative comparisons

venue: arXiv preprint arXiv:1612.00086,

authors:
Rangachari Anand
Kishan Mehrotra
Chilukuri K Mohan
Sanjay Ranka

title: Efficient classification for multiclass problems using modular neural networks

venue: IEEE Transactions on Neural Networks,

authors:
Saket Anand
Sushil Mittal
Oncel Tuzel
Peter Meer

title: Semi-supervised kernel mean shift clustering

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Violaine Antoine
Benjamin Quost
M-H Masson
Thierry Denoeux

title: Cecm: Constrained evidential c-means algorithm

venue: Computational Statistics & Data Analysis,

authors:
Han Bao
Gang Niu
Masashi Sugiyama

title: Classification from pairwise similarity and unlabeled data

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

authors:
Mikhail Bilenko
Sugato Basu
Raymond J Mooney

title: Integrating constraints and metric learning in semi-supervised clustering

venue: In Proceedings of the twenty-first international conference on Machine learning,

authors:
Deng Cai
Xiaofei He
Xuanhui Wang
Hujun Bao
Jiawei Han

title: Locality preserving nonnegative matrix factorization

venue: In IJCAI,

authors:
Xinlei Chen
Deng Cai

title: Large scale spectral clustering with landmark-based representation

venue: In AAAI,

authors:
Jason V Davis
Brian Kulis
Prateek Jain
Suvrit Sra
Inderjit S Dhillon

title: Information-theoretic metric learning

venue: In Proceedings of the 24th international conference on Machine learning,

authors:
J. Deng
W. Dong
R. Socher
L.-J. Li
K. Li
L. Fei-Fei

title: ImageNet: A Large-Scale Hierarchical Image Database

venue: In CVPR,

authors:
Yoav Freund
Robert E Schapire

title: A decision-theoretic generalization of on-line learning and an application to boosting

venue: Journal of computer and system sciences,

authors:
Mikel Galar
Alberto Fernández
Edurne Barrenechea
Humberto Bustince
Francisco Herrera

title: An overview of ensemble methods for binary classifiers in multi-class problems: Experimental study on one-vs-one and one-vs-all schemes

venue: Pattern Recognition,

authors:
Ian J Goodfellow
Oriol Vinyals
Andrew M Saxe

title: Qualitatively characterizing neural network optimization problems

venue: arXiv preprint arXiv:1412.6544,

authors:
Trevor Hastie
Robert Tibshirani

title: Classification by pairwise coupling

venue: In Advances in neural information processing systems,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

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

title: Identity mappings in deep residual networks

venue: In European Conference on Computer Vision,

authors:
Yen-Chang Hsu
Zsolt Kira

title: Neural network-based clustering using pairwise constraints

venue: International Conference on Learning Representations (ICLR) workshop,

authors:
Yen-Chang Hsu
Zhaoyang Lv
Zsolt Kira

title: Learning to cluster in order to transfer across domains and tasks

venue: In International Conference on Learning Representations (ICLR),

authors:
Daniel Jiwoong Im
Michael Tao
Kristin Branson

title: An empirical analysis of deep network loss

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Stefan Knerr
Léon Personnaz
Gérard Dreyfus

title: Single-layer learning revisited: a stepwise procedure for building and training a neural network

venue: In Neurocomputing,

title: Learning multiple layers of features from tiny images

title: The hungarian method for the assignment problem

venue: Naval research logistics quarterly,

authors:
Samuli Laine
Timo Aila

title: Temporal ensembling for semi-supervised learning

venue: International Conference on Learning Representations,

authors:
Brenden M. Lake
Ruslan Salakhutdinov
Joshua B. Tenenbaum

title: Human-level concept learning through probabilistic program induction

title: The mnist database of handwritten digits

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

title: Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks

authors:
Hao Li
Zheng Xu
Gavin Taylor
Tom Goldstein

title: Visualizing the loss landscape of neural nets

venue: arXiv preprint arXiv:1712.09913,

title: Some methods for classification and analysis of multivariate observations

venue: In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability,

authors:
Takeru Miyato
Shin-ichi Maeda
Shin Ishii
Masanori Koyama

title: Virtual adversarial training: a regularization method for supervised and semi-supervised learning

authors:
Avital Oliver
Augustus Odena
Colin Raffel
Ekin D Cubuk
Ian J Goodfellow

title: Realistic evaluation of deep semi-supervised learning algorithms

venue: arXiv preprint arXiv:1804.09170,

authors:
Syama Sundar Rangapuram
Matthias Hein

title: Constrained 1-spectral clustering

venue: In AISTATS,

authors:
Ryan Rifkin
Aldebaro Klautau

title: In defense of one-vs-all classification

authors:
Mehdi Sajjadi
Mehran Javanmardi
Tolga Tasdizen

title: Regularization with stochastic transformations and perturbations for deep semi-supervised learning

venue: In Advances in Neural Information Processing Systems,

authors:
Robert E Schapire
Yoram Singer

title: Improved boosting algorithms using confidence-rated predictions

venue: Machine learning,

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

authors:
Alexander Strehl
Joydeep Ghosh

title: Cluster ensembles—a knowledge reuse framework for combining multiple partitions

authors:
Antti Tarvainen
Harri Valpola

title: Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results

authors:
Oriol Vinyals
Charles Blundell
Timothy Lillicrap
Koray Kavukcuoglu
Daan Wierstra

title: Matching networks for one shot learning

authors:
Xiang Wang
Buyue Qian
Ian Davidson

title: On constrained spectral clustering and its applications

venue: Data Mining and Knowledge Discovery,

authors:
Jason Weston
Chris Watkins

title: Multi-class support vector machines

venue: Technical report, Citeseer,

authors:
Ting-Fan Wu
Chih-Jen Lin
Ruby C Weng

title: Probability estimates for multi-class classification by pairwise coupling

venue: Journal of Machine Learning Research,

authors:
Eric P Xing
Michael I Jordan
Stuart J Russell
Andrew Y Ng

title: Distance metric learning with application to clustering with side-information

authors:
Yi Yang
Dong Xu
Feiping Nie
Shuicheng Yan
Yueting Zhuang

title: Image clustering using local discriminant models and global integration

venue: IEEE Transactions on Image Processing,

title: 2017) which shows a nice convexity with a not-too-deep neural network (ResNet18). The solutions of MCL and KCL are both surrounded by a plateau of high loss, but MCL has a wider concave region. The same wide concavity can be seen in the mutual projection (Figure 4b). This is a possible explanation for why MCL still converges to a good local minimum with a randomly initialized network. Besides, the mutual projection shows that the geometry of MCL’s loss

title: The ADif represents average difference (Hsu et al., 2018)

venue: Alphabet #class SKMS KCL MCL Angelic

heading: 1 INTRODUCTION

text:
One of the most common settings for machine learning is classification, which involves learning a function f to map the input data x to a class label y ∈ {1, 2, .., C}. The most successful method for learning such a function is deep neural networks, owing its popularity to its capability to approximate a complex nonlinear mapping between high-dimensional data (e.g. images) and the classes. Despite the success of deep learning, a neural network demands a large amount of class-specific labels for learning a discriminative model, i.e. P (y|x). This type of labeling can be expensive to collect, requires a-priori knowledge of all classes, and limits the form of supervision required. For example, the classes may be ambiguous or non-expert human annotators may be able to more easily provide information about whether two instances are of the same class or not, rather than identifying the specific class. A final problem is that different methods are necessary depending on what type of data is available, ranging from supervised learning (known classes) to cross-task unsupervised learning (unknown classes in the target domain) and semi-supervised learning (mix of labeled and unlabeled with known classes). Unsupervised learning with unknown classes is especially difficult to support.
To relax these limitations, we propose to reduce the problem of classification to a meta problem that underlies a set of learning problems. Instead of solving the target task directly (learning a multi-class discriminative model such as a neural network), we instead learn a model that does not require explicit class label y but rather a weaker form of information. In the context of classification, the meta problem that we use is a binary decision problem. Note that such a conversion to a different task (e.g. binary) is called a problem reduction method (Allwein et al., 2000) which has had a long history in the literature, especially in ensemble methods and binarization techniques (Galar et al., 2011). The most well-known strategies are "one-vs-all" (Anand et al., 1995; Rifkin & Klautau, 2004) and "one-vs-one" (Knerr et al., 1990; Hastie & Tibshirani, 1998; Wu et al., 2004). Although they have varied ensembling strategies, all of them share the same task encapsulating scheme, as illustrated in Figure 1a; specifically the binary classifiers are the sub-modules of a multi-class classifier (i.e. the multi-class classifier consists of multiple binary classifiers). These schemes still require that the class
The demo code is available at https://github.com/GT-RIPL/L2C
label y be available to create the inputs for each binary classifier, and therefore these strategies do not relax the labeling requirements mentioned earlier.
In this work, we propose a novel strategy to address the above limitations. Our method reverses the task encapsulation order so that a multi-class classifier becomes a sub-module of a binary classifier, as illustrated in Figure 1b. The connection between the two classifiers is elucidated in Section 3. There are two highlights in Figure 1b. First, class labels yi are not required in the learning stage. Instead, our method uses pairs of data (xi, xj) as input and pairwise similarity sij for the supervision. Second, there is only one binary classifier in the scheme and it is present only during the training stage. In other words, the ephemeral binary task assists the learning of a multi-class classifier without being involved in the inference. When using a neural network with softmax outputs for the multi-class classifier, the proposed scheme can learn a discriminative model with only pairwise information.
We specifically make the following contributions: 1) We analyze the problem setting and show that the loss we can use for this encapsulation can be easily derived, and we present an intuitive probabilistic graphical model interpretation for doing so, 2) We evaluate its performance compared to vanilla supervised learning of neural networks which uses multi-class labels, and visualize the loss landscape to better understand the underlying optimization difficulty, and 3) We demonstrate support for learning classifiers in more challenging problem domains, e.g. in unsupervised cross-task transfer and semi-supervised learning. We show how our meta classification framework can support all three learning paradigms, and evaluate it against several state-of-the-art methods. The experimental results show that the same meta classification approach is superior or comparable to state of the art across the three problem domains (supervised learning, unsupervised cross-task learning, and semi-supervised learning), demonstrating flexibility to support even unknown types and numbers of classes.

heading: 2 RELATED WORK

text:
Supervised learning and problem reduction: Allwein et al. (2000) presents a unifying framework for multi-class classification by reducing it to multiple binary problems. The concepts for achieving such reduction, one-vs-all and one-vs-one, have been widely adopted and analyzed (Galar et al., 2011). The two strategies have been used to create several popular algorithms, such as variants of support vector machine (Weston & Watkins, 1998), AdaBoost (Freund & Schapire, 1997; Schapire & Singer, 1999), and decision trees (Fürnkranz, 2003). Despite the long history of reduction, our proposed scheme (Figure 1b) has not been explored. Furthermore, the scheme can be deployed easily by replacing the learning objective, which is fully compatible with deep neural networks for classification, a desirable property for broad applicability.
Unsupervised cross-task transfer learning: This learning scheme is proposed by Hsu et al. (2018). The method transfers the pairwise similarity as the meta knowledge to an unlabeled dataset of different classes. It then uses a constrained clustering algorithm with predicted pairwise constraints
(binarized pairwise similarity) to discover the unseen classes. This learning scheme shares the same supervision (pairwise similarity) as ours, and therefore relates our method to constrained clustering algorithms. One class of such approaches uses the constraints to learn a distance metric, and then applies a generic clustering algorithm such as K-means or hierarchical clustering to obtain the cluster assignments. This includes DML (Xing et al., 2003), ITML (Davis et al., 2007), SKMS (Anand et al., 2014), SKKm (Anand et al., 2014; Amid et al., 2016), and SKLR (Amid et al., 2016). The second class of methods incorporates the constraints into the cluster assignment objective. Some constrained spectral clustering algorithms, e.g. CSP (Wang et al., 2014) and COSC (Rangapuram & Hein, 2012) use this strategy. There are also approaches combine both distance metric learning and a clustering objective jointly, such as MPCKMeans (Bilenko et al., 2004), CECM (Antoine et al., 2012), and Kullback–Leibler divergence based contrastive loss (KCL) (Hsu & Kira, 2016; Hsu et al., 2018). Our new learning objective for Figure 1b can replace the above objectives in the cross-task transfer learning scheme.
Semi-supervised learning: Our meta classification strategy can easily plug into a semi-supervised learning scheme. Our comparison focuses on state-of-the-art methods which solely involve adding a consistency regularization (Laine & Aila, 2017; Sajjadi et al., 2016; Miyato et al., 2018; Tarvainen & Valpola, 2017) or Pseudo-Labeling (Lee, 2013) for training a neural network. Another line of strategy combines weak supervision, such as similar pairs, and unlabeled data to learn a binary classifier (Bao et al., 2018). We present a new method by augmenting Figure 1b with the Pseudo-Labeling strategy.

heading: 3 META CLASSIFICATION LEARNING

text:
A natural way to analyze problems with observed and unobserved information is through a probabilistic graphical model. In figure 2, we show the graphical model for our problem, where classspecific labels Y are latent while pairwise similarities S are observed. Specifically, we denote X = {X1, .., Xn}, Y = {Y1, .., Yn}, and S = {Sij}1≤i,j≤n to represent the nodes for samples, class labels, and pairwise similarities, respectively. In the model, we have Yi ∈ {1, 2, .., C} and Sij ∈ {0, 1}. Then we have P(Sij = 1|Yi, Yj) = 1 when Yi = Yj and zero probability otherwise; similarly, P(Sij = 0|Yi, Yj) = 1 when Yi 6= Yj . The output of a discriminative classifier with parameters θ is f(xi; θ) = P(Yi|xi; θ), where f(xi; θ) outputs a categorical distribution. Now we describe the likelihood that the model explains the observed labeling (either with class labeling or pairwise labeling).
L(θ;X,Y,S) = P(X,Y,S; θ) = P(S|Y)P(Y|X; θ)P(X) (1)
When S is fully observed while Y is unknown, calculating the likelihood requires marginalizing Y by computing ∑ Y P(S|Y)P(Y|X; θ), which is intractable. The pairwise term P(S|Y) =∏
i,j P(Sij |Yi, Yj) makes all Yi dependent on each other and prohibits efficient factorization. Thus, we approximate the computation by imposing additional independences such that Sij ⊥ S\{Sij}|Xi, Xj (see Appendix D for a discussion of these). Now we can compute the likelihood with the observed nodes Xi = xi and Sij = sij :
L(θ;X,S) ≈ ∑ Y P(S|Y)P(Y|X; θ) (2)
≈ ∏ i,j ( ∑ Yi=Yj 1[sij = 1]P(Yi|xi; θ)P(Yj |xj ; θ)+
∑ Yi 6=Yj 1[sij = 0]P(Yi|xi; θ)P(Yj |xj ; θ) ) . (3)
Equation (2) omits the P(X) since X are observed leaf nodes. It is straightforward to take a negative logarithm on equation 3 and derive a loss function:
Lmeta(θ) = − ∑ i,j log ( ∑
Yi=Yj
1[sij = 1]P(Yi|xi; θ)P(Yj |xj ; θ)+
∑ Yi 6=Yj 1[sij = 0]P(Yi|xi; θ)P(Yj |xj ; θ) )
(4)
= − ∑ i,j sij log(f(xi; θ) T f(xj ; θ)) + (1− sij) log(1− f(xi; θ)T f(xj ; θ)). (5)
Then we define the function g by the probability of having the same class label, which is calculated by the inner product between two categorical distributions:
g(xi, xj , f(·, θ)) = f(xi; θ)T f(xj ; θ) = ŝij (6)
Here we use ŝij to denote the predicted similarity (as opposed to ground truth similarity sij). By plugging equation 6 into equation 5, Lmeta has the form of a binary cross-entropy loss:
Lmeta = − ∑ i,j sij log ŝij + (1− sij) log(1− ŝij). (7)
In Figure 1b, the multi-class classifier corresponds to f while the binary classifier corresponds to g. In other words, it is surprisingly simple to wrap a multi-class classifier by a binary classifier as described above. Since there are no learnable parameters in g, the weights optimized with the meta criterion Lmeta are all in the neural network f . To minimize Lmeta, f(xi; θ) and f(xj ; θ) must output a sharply peaked distribution with the peak happening only at the same output node when sij = 1. In the case of sij = 0, the two distributions must have as little overlap as possible to minimize the loss. In the latter case, the two samples are pushed to be activated at the output nodes of different classes. Both properties of f ’s output distribution are typical characteristics of a classifier learned with class labels and using multi-class cross-entropy. The properties also illustrate the intuition of why minimizing Lmeta helps f learn outputs similar to a multi-class classifier.
Lastly, because of the likelihood nature of Lmeta, we call the learning criterion a Meta Classification Likelihood (MCL) in the rest of the paper.

heading: 4 LEARNING PARADIGMS

text: The supervision used in MCL is the pairwise labeling S. Due to its weaker form compared to class labels, we have the flexibility to collect it in a supervised, cross-task transfer, or semi-supervised manner. The collection method determines the learning paradigms. In the first two learning paradigms, other methods (see Related Work Section) have also used pair-wise constraints similarly; our novelty is the derivation of our new learning objective, MCL, which can replace the other objectives. In the semi-supervised learning scenario, the proposed Pseudo-MCL is a new method. Details are elaborated below.

heading: 4.1 SUPERVISED LEARNING

text: Supervised pairwise labeling can be directly collected from humans, or converted from existing class labeling by having S = {sij}1≤i,j≤n, where sij = 1 if xi and xj belong to the same class, otherwise sij = 0. In our experiments, we use the latter setting to enable comparison to other supervised algorithms. Figure 3a illustrates the training process.

heading: 4.2 UNSUPERVISED LEARNING

text:
Pairwise labeling can come from several natural cues, such as spatial and temporal proximity. For example, the patches in an image can be similar because of their spatial closeness, and the frames of video in a short time usually have similar content. Additionally, useful pairwise information can be found in the edges in social networks or in the network of academic citations. All of the above are potential applications of this work.
Another strategy that is unsupervised in the target domain is to collect pairwise labels through transfer learning. Hsu et al. (2018) proposes a method in which a similarity prediction network (SPN) can be learned from a labeled auxiliary dataset. Then the SPN is applied on the unlabeled target dataset to predict S (the probability of being in the same class). In the last step, the predicted S is fed into a network (in that case optimized via Kullback–Leibler divergence based contrastive loss) to discover the categories in the unlabeled target dataset. Figure 3b illustrates above process. Note that the classes between the auxiliary dataset and target dataset may have an overlap (cross-domain transfer) or not (cross-task transfer) (Hsu et al., 2018). In both cases, the predicted pairwise similarity is noisy (especially in the latter case); therefore the transfer learning strategy creates a challenging scenario for learning classifiers. Its difficulty makes it a good benchmark to evaluate the robustness of our methods and is used in our experiments.

heading: 4.3 SEMI-SUPERVISED LEARNING

text:
We propose a new strategy to obtain the S for semi-supervised learning. Figure 3c illustrates the method under the typical semi-supervised learning setting, which takes a common dataset D used for
supervised learning and discards the labels for most of the dataset. The labeled and unlabeled portions in D are DL = (XL, YL) and DUL = XUL correspondingly. The main idea is to create a pseudosimilarity SL+UL for the meta classifier (similar to Pseudo-Labeling (Lee, 2013)) by binarizing the predicted ŜL+UL at probability 0.5. We call the method Pseudo-MCL, and we note that here interestingly g is not static as it iteratively improves as f improves. Another way to create similarity is data augmentation, inspired by the Π-model (Laine & Aila, 2017) or Stochastic Perturbations (Sajjadi et al., 2016). An image perturbed in different ways naturally belong to the same class, and thus provides free ground-truth similarity. The similarity from both methods can be easily combined to SL+UL by having a logical-OR operation for the two binarized similarities. The learning objective is the sum of the multi-class cross-entropy and Pseudo-MCL, so the mapping between output nodes and classes are automatically decided by the supervised part of learning.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL SETUP AND NETWORK OPTIMIZATION

text:
In all experiments, we use a standard gradient-based method for training a neural network by optimizing the learning criterion. For example, with stochastic gradient descent, we calculate MCL within a mini-batch of data. In that case, the i and j correspond to the index of data in a mini-batch b. The outputs of f(·; θ) are enumerated in |b|(|b| − 1)/2 pairs in a mini-batch before calculation of MCL. Our empirical finding is that this enumeration introduces a negligible overhead to the training time. We also note that for large datasets, this only samples from the full set of pairwise information.
One limitation of learning a classifier without class labels is losing the mapping (the identifiability) between the output nodes and the semantic class. A simple method to obtain the mapping is by using a part of the training data with class labels and assigning the output nodes to the dominant class which activates the node (here we obtain the optimal assignment by the Hungarian algorithm (Kuhn, 1955), which is commonly used in evaluating the clustering accuracy (Yang et al., 2010)). Note, however, that for unsupervised problems we do not need to do this except to quantitatively evaluate our method; otherwise the outputs can be seen as arbitrary clusters.

heading: 5.2 SUPERVISED LEARNING WITH WEAK LABELS

text: This section empirically compares MCL to multi-class cross-entropy (CE) and the strong baseline using pairwise similarity (Kullback–Leibler divergence based contrastive loss (KCL) (Hsu & Kira, 2016; Hsu et al., 2018)), in a supervised learning setting. Specifically, we would like to demonstrate that we can achieve similar classification rates as cross-entropy (the standard objective for multi-class classification) using only pairwise similarity, and show that the previous pairwise criterion cannot do this likely due to a poor loss landscape. We compare the classification accuracy of these criteria with varied network depths and varied dataset difficulty. The visualization of loss landscape is provided in Appendix A. The formulation of KCL and how it relates to MCL is available in Appendix B.

heading: 5.2.1 QUANTITATIVE ANALYSIS

text:
We compare the classification accuracy on three image datasets: MNIST (LeCun, 1998) is a 10-class handwritten digit dataset with 60000 images for training, and 10000 for testing; CIFAR10 and CIFAR100 (Krizhevsky, 2009) instances are colored 32× 32 images of objects such as cat, dog, and ship. They both have 50000 images for training and 10000 for testing.
Network Architectures: We use convolution neural networks with a varied number of layers: LeNet (LeCun et al., 1998) and VGG (Simonyan & Zisserman, 2014). We add VGG8, which only has one convolution layer before each pooling layer, as the supplement between LeNet and VGG11. The list of architectures also includes ResNet (He et al., 2016a) with pre-activation (He et al., 2016b)). The number of output nodes K in the last fully connected layer is set to the true number of categories for this section. Since the learning objectives KCL and MCL both work on pairs of inputs, we have a pairwise enumeration layer (Hsu et al., 2018) between the network outputs and the loss function.
Training Configurations: All networks in this section are trained from scratch with randomly initialized weights. By default, we use Adam (Kingma & Ba, 2014) to optimize the three criterion
with mini-batch size 100 and initial learning rate 0.001. On MNIST the learning rate was dropped every 10 epochs by a factor of 0.1 with 30 epochs in total. On CIFAR10/100 we use the same setting except that the learning rate is dropped at 80 and 120 epochs with 140 epochs in total. For CIFAR100, the mini-batch size was 1000 and the learning rate dropped at epoch 100 and 150 with 180 epochs in total. In the experiments with ResNet, we use SGD instead of Adam since SGD converges to a higher accuracy when keeping other settings the same as above. The learning rate for SGD starts with 0.1 and decays with a factor of 0.1 at the number of epochs described above.
Results and discussion: The results in Table 1 show that MCL achieves similar classification performance as CE with different network depths and three datasets. In contrast, KCL has degenerate performance when the networks are deeper or the dataset is more difficult. This might be due to a limitation of using KL-divergence, specifically that when two probability distributions are the same, the divergence will be zero no matter what the values are. This property may introduce bad local minima or small gradients for learning. To investigate such a perspective, we apply two strategies. First, we use a large learning rate (0.2) with SGD to avoid bad local minima and make the training schedule 10 times longer for exploring the parameter space. This setting helps KCL with VGG11, in that the error rate drops from 72.2% to 10.4%, but not with VGG16 (from 81.1% to 76.8%). In the second strategy, we select the worst conditions (the values with * notion) in Table 1 for KCL and pre-train the networks with only 4k labels with CE to initialize the networks. Then we use KCL with the full training set to finish the training. With a better initialization, KCL can reach a performance close to CE and MCL. The performance is shown with parenthesis in Table 1. The results of both strategies indicate that KCL has bad local minima or plateaus in its loss surface (see Section A in Appendix). Unlike KCL, MCL can converge to a performance close to CE with random initialization in all of our experiments. Furthermore, MCL outperforms CE with a deeper network (error rate 5.6% versus 6.5% with ResNet101). Such a result indicates that MCL is less prone to overfitting (in the Table 1, all ResNets achieve a training error less than 0.1%).

heading: 5.3 UNSUPERVISED CROSS-TASK TRANSFER LEARNING

text:
The second experiment follows the transfer learning scenario proposed by Hsu et al. (2018) and is summarized in Section 4.2. This scenario has two settings. The first is when the number of output nodes K equal to the number of ground truth classes C in a dataset. This setting is the same as a multi-class classification task, except no labels (both class labels or similarity labels) are provided in the target dataset. The second setting is having an unknown C, which is closer to a clustering
problem. One strategy to address the unknown C is to set a large K, and we rely on the clustering algorithm to use only a necessary number of clusters to describe the dataset while leaving the extra clusters empty.
We use constrained clustering algorithms as the baselines since they can use the pairwise inputs from a similarity prediction network (SPN) (Hsu et al., 2018). In this section, the same set of binarized pairwise similarity prediction is provided to all algorithms for a fair comparison. The metric in this section is still the classification accuracy. The mapping between output nodes and classes is calculated by the Hungarian algorithm, in which each class only matches to one output node. The unmapped output nodes are all subject to the classification error. We also include the normalized mutual information (NMI) (Strehl & Ghosh, 2002) metric. We use two datasets in the evaluation.
Omniglot (Lake et al., 2015): This dataset has 20 images for each of 1623 different handwritten characters. The characters are from 50 different alphabets and were separated into 30 background sets (Omniglotbg) and 20 evaluation sets (Omnigloteval) by the dataset author. The procedure uses the Omniglotbg set (964 characters in total) to learn the similarity function and applies it to the cross-task transfer learning on the 20 evaluation sets (this same input is used for all compared algorithms). In this test, the backbone network for classification has four convolution layers and has weights randomly initialized. Both MCL and KCL are optimized by Adam with mini-batch size 100.
ImageNet (Deng et al., 2009): The 1000-class dataset is separated into 882-class and 118-class subsets as the random split in Vinyals et al. (2016). The procedure uses ImageNet882 for learning the similarity prediction function and randomly samples 30 classes (∼39k images) from ImageNet118 for the unlabeled target data. In this test, the backbone classification network is Resnet-18 and has weights initialized by classification on ImageNet882. Both learning objectives (KCL and MCL) are optimized by SGD with mini-batch size 100.
Results and Discussion: We follow the evaluation procedure (including network architectures) used in Hsu et al. (2018), therefore the results can be directly compared. The results shown in Table 2 and 3 demonstrate a clear advantage for MCL over other methods. KCL also performs well, but MCL beats its performance with a larger gap when C is unknown (ACC with K=100). MCL also estimates the number of classes in a dataset better than KCL (Appendix Table 5). The advantage of MCL over KCL in this section is not due to the ease of optimization, since the network is shallow in the Omniglot experiment and the network is pre-trained in the ImageNet experiment. The advantage may due to the fact that MCL is free of hyper-parameters and so performs better than KCL which uses a heuristic threshold (σ = 2) (Hsu & Kira, 2016) for its margin.

heading: 5.4 SEMI-SUPERVISED LEARNING

text:
We evaluate the semi-supervised learning performance of the Pseudo-MCL on the standard benchmark dataset CIFAR-10. The Pseudo-MCL is compared to two state-of-the-art methods, which are VAT (Miyato et al., 2018) and Π-Model (Laine & Aila, 2017; Sajjadi et al., 2016). Our list of baselines additionally includes Pseudo-Labeling (Lee, 2013) and SPN-MCL since they share a similar strategy with Pseudo-MCL. The SPN-MCL uses the same strategy presented in the Section 4.2 for unsupervised learning, except that the SPN is trained with only the labeled portion (e.g. 4k labeled data) of CIFAR10 in this section. We also note that the SPN serves as a static function to provide the similarity for optimizing the regular MCL objective.
Experiment Setting: To construct the DL, four thousand labeled data are randomly sampled from the training set (50k images) of CIFAR10. This leaves 46k unlabeled data for DUL. We use 5 random DL/DUL splits to calculate the average performance. The images are augmented by the standard procedure which includes random cropping, random horizontal flipping, and normalization to zero mean with unit variance. The model for all method is the ResNet-18 (pre-activation version, He et al. (2016b)), which has no dropout as in a standard model. We use Adam to optimize the objective functions of all methods. The procedure begins with learning the supervised model with only the 4k labeled data; then all other methods have a fine-tuning withDL+DUL based on the learned supervised model. The supervised model (with only 4k data) is trained with initial learning rate 0.001 and a decay with factor 0.1 at epochs 80 and 120 for a total of 140 epochs. All the semi-supervised methods are trained with initial learning rate 0.001 and have a decay with factor 0.1 at epoch 150 and 250 for a total of 300 epochs. We use a shared implementation among all methods so that the major difference between methods is the regularization term in the learning objective. Appendix C.1 provides the description for hyperparameter tuning.
Results and Discussion:
Table 4 presents the comparison and shows that Pseudo-MCL is on-par with the state-of-the-art method VAT (Miyato et al., 2018). The performance difference between SPN-MCL and Pseudo-MCL clearly demonstrates the benefits of having the binary classifier and the multi-class classifier optimized together. Note that comparing our Table 4 and a recent review (Oliver et al., 2018), we have a lower
baseline performance due to a lighter regularization (no dropout) and no extra data augmentation (such as adding Gaussian noise), but the relative ranking between methods is consistent. Therefore we confirm the effectiveness of Pseudo-MCL. Lastly, Pseudo-MCL is free of hyperparameter, which is a very appealing characteristic for learning with few data.

heading: 6 CONCLUSION

text: We presented a new strategy to learn a multi-class classification via a binary decision problem. We formulate the problem setting via a probabilistic graphical model and derive a simple likelihood objective that can be effectively optimized via neural networks. We show how this same framework can be used for three learning paradigms: supervised learning, unsupervised cross-task transfer learning, and semi-supervised learning. Results show comparable or improved results over state of the art, especially in the challenging unsupervised cross-task setting. This demonstrates the power of using pairwise similarity as weak labels to relax the requirement of class-specific labeling. We hope the presented perspective of meta classification inspires additional approaches to learning with fewer labeled data (e.g. domain adaptation and few-shot learning) as well as application to domains where weak labels are easier to obtain.

heading: ACKNOWLEDGMENTS

text: This work was supported by the National Science Foundation and National Robotics Initiative (grant # IIS-1426998) and DARPA’s Lifelong Learning Machines (L2M) program, under Cooperative Agreement HR0011-18-2-001.

heading: B KCL VERSUS MCL

text:
From the view of optimization objective, the KLD-based Contrastive Loss (KCL) has a form close to our MCL although it is originally designed for clustering. In the KCL paper (Hsu & Kira, 2016; Hsu et al., 2018), it interprets the softmax output of a neural network as outputting a probability distribution over cluster assignments. Then a contrastive loss function is defined using KL-divergence to measure the distance between two distributions ŷi = f(xi; θ) and ŷj = f(xj ; θ). The cost between a similar pair (xi, xj), in which sij = 1, is given by:
L+KCL(xi, xj) = DKL(ŷi||ŷj) +DKL(ŷj ||ŷi). (9)
If (xi, xj) is a dissimilar pair (sij = 0), then ŷi and ŷj are expected to be different distributions, which is described by a hinge-loss function with a hyper-parameter σ for the margin.
L−KCL(xi, xj) = Lh(DKL(ŷi||ŷj), σ) + Lh(DKL(ŷj ||ŷi), σ), where Lh(e, σ) = max(0, σ − e).
(10)
Then the total contrastive loss (KCL) has the form:
LKCL = ∑ i,j sijL + KCL(xi, xj) + (1− sij)L − KCL(xi, xj). (11)
In comparing KCL and MCL, we find that they are similar in using pairwise similarity and have no requirement on the number of output nodes K no matter what the true number of classes C is. They can also be plugged into the training of neural networks in the same way, in that switching MCL to KCL can easily be done by replacing the learning criterion. Although they are similar in terms of usage, their formulation has a fundamental difference. KCL is inspired by metric learning, in that KL-divergence is the metric for evaluating the pairwise distance. Our MCL is inspired by the concept of meta classification learning and explained by a maximum likelihood estimation. The most significant difference is that MCL is free of hyperparameter. Therefore MCL does not require cross-validation for hyperparameter tuning. This property is crucial for unsupervised learning or when only a few instances of labeled data are available.

heading: C EXPERIMENTAL SETTING

text:
C.1 HYPERPARAMETER TUNING FOR SEMI-SUPERVISED LEARNING
All the semi-supervised learning objectives LSSL here can be represented as a weighted sum of a supervised term Lsup and an unsupervised regularization term Lreg:
LSSL = αLsup(XL, YL) + βLreg(XL ∪XUL) (12)
For a fair comparison, one should give the same budget for tuning the hyperparameters, such as α and β. One strategy is applying an exhaustive grid search in the hyperparameter space. Such searching requires doing cross-validation and may not be applicable when the number of labeled data is small. We adopt another strategy that gives zero tuning budget for all. We decide the α and β by natural statistics, which is the ratio between the amount of data be seen by the Lsup and Lreg. Specifically:
α = |DL|
|D|+ |DL| , β = |D| |D|+ |DL|
(13)
One method, VAT (Miyato et al., 2018), has extra hyperparameters (e.g. the ) in its design. In that case, we use the values decided in the original paper for this dataset.

heading: D ASSUMPTIONS IN META CLASSIFICATION LIKELIHOOD

text:
D.1 SIMPLIFIED LIKELIHOOD
In section 3, the original likelihood (eq. 2) relies on an additional independence assumption to simplify its negative logarithm form to a binary cross-entropy. Such an simplification raises the
question of whether equation (3) is over-simplified. For the supervised learning case (Section 4.1 with results in Section 5.2), where the constraints are ground truth, the global solution of our likelihood is also the solution for the original likelihood. This is because if an instance is misclassified, then it will break some pair-wise constraints in both likelihoods and no longer be optimal.
Of course, in practice, there could be two issues. First, the optimization methods for more complex models (e.g. stochastic gradient descent) may find local minima. Although it is hard to show theory for this in the general case, where local optima may be found, in such cases our visualization of the loss landscape (see Appendix A) provides some evidence that our method has a landscape that reduces poor local minima compared to prior work (KCL, Hsu et al. (2018)). The second potential issue is when constraints may be noisy. In such cases, for example, if the noise is high and there is a dependency structure to be leveraged, jointly optimizing across many or all constraints with the original likelihood may provide additional performance (at the expense of tractability). In practice, noisy constraints actually occur in our cross-task transfer learning experiments where our similarity prediction has significant errors (e.g. in Table 3 ImageNet experiments the similar pair precision, similar pair recall, dissimilar pair precision, and dissimilar pair recall are 0.812, 0.655, 0.982, and 0.992 respectively). The strong performance in terms of classification accuracy for the cross-task transfer experiments (Tables 2 and 3) shows that our simplification is robust to noise.
Overall, the fact that we have demonstrated our method on five image datasets and three application scenarios (Section 5.2 for supervised learning, 5.3 for unsupervised cross-task transfer learning, and 5.4 for semi-supervised learning) empirically support that the proposed likelihood can overcome these two issues. It would be interesting future work to develop methods that can incorporate constraints jointly, however.
D.2 SEPARABILITY ASSUMPTIONS
Note that we assume separability of semantic categories in a dataset. This means that when the constraints are given (supervised learning), there is sufficient information (in the features) to separate or to group the samples. In the case of no given constraints (unsupervised or semi-supervised learning), there is also sufficient information to estimate the pairwise similarity. However, these are common assumptions that are inherent in discriminative models.