Automatic Code Summarization: A Systematic Literature Review

Background: During software maintenance and development, the comprehension of program code is key to success. High-quality comments can help us better understand programs, but they're often missing or outmoded in today's programs. Automatic code summarization is proposed to solve these problems. During the last decade, huge progress has been made in this field, but there is a lack of an up-to-date survey. Aims: We studied publications concerning code summarization in the field of program comprehension to investigate state-of-the-art approaches. By reading and analyzing relevant articles, we aim at obtaining a comprehensive understanding of the current status of automatic code summarization. Method: In this paper, we performed a systematic literature review over the automatic source code summarization field. Furthermore, we synthesized the obtained data and investigated different approaches. Results: We successfully collected and analyzed 41 selected studies from the different research communities. We exhaustively investigated and described the data extraction techniques, description generation methods, evaluation methods and relevant artifacts of those works. Conclusions: Our systematic review provides an overview of the state of the art, and we also discuss further research directions. By fully elaborating current approaches in the field, our work sheds light on future research directions of program comprehension and comment generation.

I. Introduction
With the rapid development of scale and complexity of software systems, developers spend about 59% of their time in program comprehension [1]. However, reading and understanding other peoples' code without good comments can be extremely difficult for software developers. Good program comments can be quite useful in helping developers cooperate or modify others' code, but for various reasons, high-quality comments are often absent in many software. What's worse, even if a code snippet is well documented, it also needs to be carefully maintained and renewed.
To address these problems, people propose and design automatic code summarization methods to generate humanreadable comments, summaries, commit messages, release notes, etc. These tasks need techniques to abstract high-level actions in code, identify the roles and responsibilities of software units and generate the natural language descriptions.
In this paper, we conducted a systematic literature review in the field of automatic source code summarization using the approach proposed by Kitchenham and Charters (2007) [2]. A few previous studies of this area have been proposed [3], [4]. Our review differs from these studies in the following ways: • Timeframes: Our review is the most contemporary research [3] ering primary studies from January 2010 to January 2019. Nazar et al. [3] conducted a review of studies up to April 2016. Moreno and Marcus [4] didn't report their timeframe but their selected articles were up to 2016. The difference of timeframe is significant in the field of automatic code summarization, since the first application of artificial neural network to automatic code summarization was published by Iyer et al. in August 2016 [S27]. After Iyer's work, seven more neuralnetwork-based studies were carried out in the last two years, and they have shown huge potential and efficacy of the deep-learning approach in this area. Nazar's and Moreno's survey didn't capture these neural-networkbased studies, which is one of the reasons that motivate us to conduct this review. • Systematic approach: We followed Kitchenham's original and strict methods [2] to conduct this systematic literature review, while Moreno didn't apply the same process. Nazar et al. defined their research guidelines based on Kitchenham's approach to conducting their survey. However, we choose to follow the Kitchenham's path rigorously which has been used widely and proven to be efficient. • Focus: We focus our attention on text-to-code summarization, which means generate human-oriented summaries from source code artifacts, while Moreno's and Nazar's work included text-to-text summarization and code-tocode summarization such as summarizing mailing list and bug reports. What's more, we concentrated on the technical process of code summarization, while Nazar et al. also paid attention to the applications and tools of their selected studies.
The main contributions of this paper are: (i) An analysis of 41 studies focusing on source code summarization from January 2010 to January 2019. Researchers can use these studies to better understand the progress in this field; (ii) A comparison of different approaches of existing researches on summarizing source code; (iii) A synthesis of the current state-of-the-art over source code summarization in our primary studies; (iv) A discussion of the findings in this area and a picture of future research directions.
The rest of the article is organized as follows. First, in Section II we design the process of the study and elaborate our research methodology. In Section III we analyze the extracted data and answer the research questions. Other findings and future research directions are discussed in Section IV. In Section V we summarize and draw the conclusion.

II. Research Methodology
Our systematic literature review was conducted following the guidelines of Kitchenham(2007) [2], which structures the activities included in a systematic literature review into three phases: (1) planning, (2) conducting the review, and (3) reporting. The individual tasks performed in each activity are described in the following subsections. Figure 1 shows the approach we employ to carry out this review.

A. Specify research questions
Rastkar [5] summarizes that there are two main approaches in generating descriptions of software concerns. The first step is knowledge extraction and deduction, while the second one is the generation of natural language summary. Although software summarization techniques are evolving quickly, those two steps are still suitable for today's summarization. What's more, researchers need evaluation techniques to assess the effectiveness of the proposed summarization approaches. Meanwhile, with the development of version control systems, summarizing program change such generating commit messages is an emerging field and also needs prospecting.
To further understand the progresses as mentioned earlier and identify different approaches, the following research questions (RQs) are raised: • RQ1: Which specific techniques are used for extracting information in summarizing source code? • RQ2: How to generate natural language descriptions and what kind of summaries can be automatically generated from summarizing source code? • RQ3: What evaluating procedures have been used to assess the result in each paper? • RQ4: How can we categorize source code artifacts from which we can generate natural language descriptions?

B. Development and validation of the review protocol
The review protocol defines the main activities to conduct the literature review. It consists of four stages: 1. Collecting studies, 2. Selecting primary studies, 3. Analyzing and synthesizing the results, and 4. Reporting the review.
The following digital libraries were searched to collect studies: We also used Google Scholar to search for more studies. The search terms included code summarization, summarize code, code mining, automatic document source code, comment generation and summarizing source code change. The time frame of the search was limited within the last nine years (2010-2019), in which software summarization has grown quickly. We explicitly determined the article inclusion/exclusion criteria in Table I.

C. Identification and selection of primary studies
Besides the previously described automatic search, we also followed Wohlin's (2014) snowballing procedure [6] to identify more relevant studies. In the first step, we searched the databases with predetermined keywords as given in the last subsection and then deleted the duplicate records. Our research with the search queries got more than 200 hits, which built up our start set. Then we examined the article title, keywords, abstract and conclusions to filter out irrelevant studies and got 62 articles. We used the snowballing procedure to go through the reference lists of articles in data set to find more relevant ones. We also carried out forward snowballing to identify new papers which cited the paper we have examined, by the tools provided by Google Scholar. After conducting the snowballing procedures, we discovered 33 more relevant papers, so now we had 95 papers altogether. Finally, after using the inclusion/exclusion criteria, 41 studies remained that built up our primary studies.

D. Extraction of data
To extract information answering the research questions, we created a data extraction form. First, we classified the articles according to the target software artifacts: source code, program

E. Information analysis and synthesis
We analyzed 41 selected articles and synthesized the common-used approaches. We recorded the difference and consistency between papers. The result is presented in the next section.

III. Results
In the following subsections, we will answer the four research questions separately by analyzing the primary studies.
A. RQ1: Which specific techniques are used for extracting information in summarizing source code?
The analysis of the 41 studies of summarizing source code identified several specific data extracting techniques used for getting information from source code. The data extracting processes are mainly based on information retrieval, pattern identification, external description mining, natural language process, and machine learning. Table II summarizes our findings of the main distribution of different data extraction techniques. In the following subsections, we will discuss how different methods are used in extracting information.

1) Information Retrieval
Information Retrieval is widely used to obtain proper information from source code to automatically generate natural language descriptions. In this section, we will discuss different kinds of information retrieval technologies and how they are applied to extract information from source code.
Keyword identification approaches aim to find a keyword list to represent key information of target source code segments. Generally, keyword identification techniques employ text retrieval techniques such as vector space model (VSM) [7], latent Dirichlet allocation(LDA) [8], latent semantic indexing(LSI) [9] or simply lead terms. Haiduc et al. [S1] used VSM, LSI and lead models to build the keyword list. They evaluated the performance of different techniques and their combinations and found out that the combination of lead and VSM summaries got the highest score. In another article, Haiduc et al. [S2] improved their work, combining text retrieval techniques with structural information in the source code. Rodeghero et al. [S3] further improved the traditional VSM and TF-IDF approach by their eye-tracking study. Using eye-tracking technique, they found out that tested developers spent much more time reading method signatures than method invocations, and spent a bit more time reading method invocation than control flow. So other than basic TF-IDF weight, researchers also weighted the terms based on where they occur, thus achieved a better result than traditional efforts.
Eddy et al. [S4] replicated and expanded the work of Haiduc et al. [S1] They introduced a new topic modeling technique named hierarchical PAM (hPAM) [10] for automatic generation of source code summaries. Then they evaluated the quality of their summaries and compared their work with the work by Haiduc [S1], only to find out hPAM is not as good as the VSM methods.
Some works employ simple static analysis techniques [5], which choose useful information inside classes or methods to generate natural language descriptions. Hammad et al. [S5] extracted information of methods such as the name of local variables and methods invoked. They combined methods' descriptions to get classes' description and combined classes' description to get packages description. Dawood et al. [S34] first converted JAVA program to Abstract Syntax Tree with predefined natural language text Template (AST-W-PDT), and then visited nodes of the tree to obtain information to fill in predefined templates. Kamimura et al. [S6] classified method invocations, compared differences between test cases and identified key facts about the test cases to generate an abstract summary of them.
Topic model can help discover the general topics occurring in the document, which are clusters of similar words. McBurney et al. [S33] represented a software as a call graph and then preprocessed the call graph for the topic model. After that, they used a kind of topic model to deal with the call graph and finally displayed the hierarchical structure of the topics in a web interface. Movshovitz-Attias et al. [S7] used Latent Dirichlet allocation (LDA) and n-gram models for predicting class comments. They creatively exploited code and text tokens in the code to improve the performance of topic model. Fowkes et al. [S8] also used LDA to build a topic model to help automatically fold source code.
2) Stereotype Identification Stereotypes are abstractions of methods' or classes' types and roles in software systems. For example, a method whose responsibility is to construct a class is categorized as constructors.
Moreno et al. [S9] proposed a novel approach called JSummarizer which identified the stereotype of a class by adapting the rules considering the distribution of the methods and their stereotypes in the class. They defined different text templates for different kinds of classes and methods to generate summaries. In another effort [S10] to automatically generate release notes, Moreno et al. reused Jsummarizer [S9] to generate descriptions for newly created classes.
What's more, Abid et al. [S11] created a summary template for each method stereotype. Then they extracted main components for the method and identified the method's stereotype to fill in templates. Li et al. [S12] also identified methods' stereotypes to help summarize unit test cases. Cortés-Coy et al. [S13] proposed a new method ChangeScribe to detect the changed methods' responsibility using stereotypes, and generate commit message accordingly.
Some works use micro-patterns to generate descriptions. Micro-patterns are abstractions of method's function, but a method can be mapped to several micro-patterns. Malhotra et al. [S14] filtered out classes with few dependency relationships and then employed micro-pattern to generate descriptions. Rai et al. [S15] converted source code to XML and identified micro-pattern for methods. They collected method-level information from XML code and used a predefined set of text templates to generate summaries.

3) External Description Usage
External description usage is the way that some researchers use external natural language descriptions and their corresponding source code segments to generate summaries for target source code.
Wong et al. [S16] is the first to use external dataset to facilitate automatic summary generation. They crawled code segments together with their descriptions from a programming Question and Answer site named StackOverflow, which is quite famous among programmers. Then they developed AutoComment to extract code-description mappings and generated descriptions for similar code comment. After that, they developed another approach CloCom [S17], which analyzed existing software repositories. They applied code clone detection techniques to discover similar code segments and used the comments from some code segments to describe the other similar code segments. Then they used NLP to select relevant comment sentences to generate descriptions for the target code segments.
Badihi et al. [S18] used crowdsourcing to collect codedescription mappings. They designed a game to motivate people to write summaries for the given code segments. The game also engaged developers to rank others' summaries. They used NLP techniques to handle those code-description mappings and found the most relevant one to generate summary for the target code segments. Huang et al. [S19] mined version control systems to collect commit-comment pairs. For an input commit, their program will search the database to find a similar commit and fetch the corresponding comment. Then the comment can be used to generate a summary.

4) Natural Language Process
Natural Language Process (NLP) is a technology which can analyze natural language data, identify different components in a sentence and extract structural information from documents. In source code analysis, it's efficient to use NLP to help understand what does the identifier or the sentence imply.
Sridhara et al. [S20] is the first, by using NLP, to exploit both structural and linguistic clues in the method to summarize the main actions of an arbitrary Java method. Given the signature and body of a method, their automatic comment generator will first preprocess the code segment, by using a novel Software Word Usage Model (SWUM) [11]. SWUM can capture not only the occurrences of words in code, but also their linguistic and structural relationships. Then the generator selected important code segments to generate natural language summaries. They were also the first one to generate comments for Java method parameters automatically [S21]. They found all relevant code segments of an arbitrary parameter. Then they used SWUM to extract information from those appropriate segments. After that, they combined the data to generate comment for the parameter. In another effort, Sridhara et al. [S22] used a novel technique to identify code segments which can learn high-level abstractions of actions and express them as a natural language description. After prepossessing, they used NLP techniques to identify and describe high-level abstract actions of a code sequence. Finally, they generated descriptions from those high-level actions detected.
McBurney et al. [S23] used PageRank algorithm [12] to discover the most important methods in the given method's context. They also predefined natural language sentence templates and then used the output of SWUM to fill in these templates.
Wang et al. [S24] utilized an abstract syntax tree(AST) and operations performed on related objects to identify objectrelated action units in the method. Then they identified the statement that represents the main action of the action unit, which is called the focal statement. After that, they used NLP techniques to convert the focal statement into natural language phrases.

5) Machine learning and Artificial Neural Network
Machine learning can be distinguished into two classes: supervised learning and unsupervised learning. For a large corpus, crowdsourcing can be used to help label data in supervised summarization. Nazar et al. [S25] first built a suitable corpus of source code segments, and then they invited four students to annotate code segments to extract good summaries. After that, they employed crowdsourcing method to label source code fragment with 21 features. At last, they trained two classifiers: support vector machines (SVM) and Naive Bayes on code fragments to generate summaries with predicted features. Rastkar et al. [S26] identified a set of eight sentence-level features to locate the most relevant sentences to the target change code segments. They further ranked the relevant sentences using an SVM classifier based on the values of these features and then produced a summary by extracting the highest-ranked sentences.
In contrast to supervised learning, unsupervised learning doesn't need human annotation and can find the knowledge that we don't know in advance. Fowkes et al. [S8] used topic model, unsupervised learning and natural language process to build a novel autofolding method called TASSAL (Tree-based Autofolding Software Summarization Algorithm), which focuses on optimizing the similarity between the summary and the source code. Autofolding is a technique to automatically create a code summary by folding less informative code regions.
Artificial neural network(ANN) and deep learning are new approaches that emerged recently and has achieved outstanding performance in natural language summarization. Artificial Neural Network has many popular variants, which may achieve a totally different result, like Long short-term memory (LSTM), Convolutional neural networks(CNN) and recurrent neural networks(RNN).
Recurrent neural network is most commonly used in code summarization, and Long short-term memory is a special kind of RNN. Iyer et al. [S27] presented a new model CODE-NN, using LSTM and attention procedure to produce highlevel summaries that describe C# code snippets and SQL queries. The model was trained on a dataset which is crawled from StackOverflow. Their evaluation showed that their model significantly outperformed information retrieval-based studies. Hu et al. [S28] proposed a new approach named DeepCom, which applies Natural Language Processing (NLP) techniques to learn from a massive code corpus and generates comments from learned features. Then they used RNN and LSTM in order to analyze structural information of Java methods for better comments generation. They compared their work with CODE-NN and found out their model outperformed CODE-NN by qualitative analysis. In another effort, Hu et al. [S29] presented a novel RNN-based model TL-CodeSum, which successfully exploited API knowledge together with source code in generating code summarization.
Zheng et al. [S30] used a novel RNN-based attention module called Code Attention to translate code segments to comments, combining domain features of code snippets, such as symbols and identifiers. By focusing on these specific features, Code Attention can understand the structure of code snippets. Liang et al. [S31] made use of RNN to encapsulate the critical structural information of the source code and produce natural language comment. In terms of summarizing program changes, Jiang et al. [S36][S40] has built successful models that can make short commit messages using neural machine translation (NMT).
Convolutional neural network has achieved great success in computer vision field, but is not widely used in code summarization field. Allamanis et al. [S32] introduced a novel convolutional attentional network that successfully performed extreme summarization of source code, where 'extreme' means generating extremely concise messages.
B. RQ2: How to generate natural language descriptions and what kind of summary can be automatically generated from summarizing source code?
Once we can extract or deduct information from source code, we should turn to focus on generating natural language description from known facts. According to Haiduc et al. [S1], a summary can be distinguished into two categories: abstractive and extractive, and these two kinds of summary are often combined to achieve a better description. The Extractive summary consists of unprocessed units such as single word, phrase or code segment. Abstractive information is a kind of high-level, summarized information which isn't a part of the original document.
We noticed data extracting techniques and summary generating approaches are somehow related. In the following subsections, we'd like to discuss what kind of summary generation technology may be used and what sort of summary will be created. Table III describes the distribution of natural language description generation methods. We will discuss each of them in the following subsections.

1) Term-based Summarization
Term-based summarization is to generate a summary that contains the most relevant terms for a specific software unit. Most of term-based summarization methods are connected with information retrieval techniques.
Haiduc et al. [S1][S2], Rodeghero et al. [S3] and McBurney et al. [S33] used information retrieval techniques to extract information and then generated keyword list from it in diverse approaches. The generated keyword list captures source code semantics on which developers focus most of the attention.
2) Template-based Summarization Template-based summarization is the most common natural language summary generation method, and it can use all kinds of extracted intermediate information. In template-based summarization, researchers predefine a set of summary templates and fill in the templates based on the type of the target code segment and other information.
Dawood et al. [S34] and Hammad et al. [S5] just filled in the predefined template with program structural information such as the number of interfaces in a package or what kind of parameter does a method use. Wang et al. [S24] used NLP to identify actions, themes and secondary arguments to fill in templates together with some basic information. McBurney et al. [S23] employed and expanded a Natural Language Generation (NLG) systems proposed by Reiter and Dale [13]. NLG is an architecture to translate a set of facts to humanreadable natural language sentences.
The Software Word Usage Model (SWUM) is a prevalent model to convert Java method calls into natural language statements [11]. Sridhara [S15] identified methods' or classes' stereotype based on their property and chose templates accordingly. They filled in the template with other messages such as method signature and return type.
In unit test case summarization, template-based technique is often employed. For example, Li et al. [S12] and Kamimura et al. [S6] all employed a predefined format to generate a textual summary. 3

) External-description-based Summarization
External-description-based summarization uses external data such as comment-code mappings in other repositories or website forums.
Wong et al. [S16] collected comment-code mappings from StackOverflow and found the most relevant ones to target code segment. Then they filtered and pruned the description from relevant comment-code mappings. At last, they selected the most suitable comment for target code. In another effort, they turned to use comment-code mappings from open source projects in GitHub [S17]. For a target code snippet, they sequentially found most similar code-comment mappings, pruned them, extracted and selected comments. After that, they ranked all matched comments(because the repository database is enormous and there are many similar code segments) and generated the description of target source code. Huang et al. [S19] chose to directly apply the comment of the most similar commit to the input commit.

4) Machine-learning-based Summarization
In early works, supervised learning and unsupervised learning have been used to generate natural language description, but it turns out that machine translation techniques and neural network based natural language generators are more prevalent and efficient.
As a machine translation model, statistical machine translation (SMT) generates translations by statistical models whose parameters are derived from bilingual text corpora. Oda et al. [S35] expanded SMT to automatically discover the relationship between source code and natural language and used the connection to convert source code into pseudo code. With a source code/pseudo-code parallel corpus, they used the SMT model to train and generate pseudo code from source code.
Neural network was first used by Iyer et al. [S27] in this area. They developed a novel approach named CODE-NN, which exploited an RNN with attention and directly distributed the comments' words to code tokens. CODE-NN can successfully recommend natural language descriptions using source code snippets collected from StackOverflow. Allamanis et al. [S32] proposed a convolutional neural network to extract translation-invariant features from source code. Unlike common natural language summarization, their approach concentrated on extreme summarization, which means their output summary will be very small (3-terms on average).
Neural machine translation (NMT) is a machine translation model which uses artificial neural network to carry out translation task. In practice, we use sequence-to-sequence (Seq2Seq) model to build language models for both source language and target language. It has achieved great success in machine translation and is now getting increasing attention in source code summarization field. The model consists of an encoder, a decoder, and an attention component, in which the Encoder and Decoder are both RNNs. Hu et al. [S28][S29] and Zheng et al. [S30] employed Seq2Seq Model to translate source code into natural language descriptions. Liang et al. [S31] proposed a new model called Code-GRU, which consists of two RNNs and an intermediate vector and is a kind of variant of Seq2Seq model. It also took structural information into consideration. Jiang et al. [S36] and Loyola et al. [S37] both adopt NMT to translate diff files into short summaries, thus automatically generating commit messages.
C. RQ3: What evaluating procedures have been used to assess the result in each paper?
How to assess a software summarization process remains the primary challenge in this field. Moreno et al. [4] have categorized evaluation strategies to different aspects. According to them, evaluation methods can be categorized into online and offline procedures according to whether human is involved in the process. They can also be categorized into extrinsic and intrinsic ones where extrinsic evaluation assesses the impact of the summary on human task performance such as program comprehension and the intrinsic one assesses the inherent quality or performance of summarization output.
In recent studies, different kinds of evaluation have been combined and used. For different types of summary or different purposes, researchers may use different evaluation methods. In Table IV, each evaluation method and its distribution are displayed. In the subsections below, we will discuss different kinds of evaluation and demonstrate the application of them.

1) Manual Evaluation
Manual Evaluation is the simplest but most commonly used method to assess many properties of summaries. As an intrinsic and online method, manual evaluation is to invite some software practitioners or students to read and rate the summaries in different dimensions and standards. Dimensions include precision, accuracy, compactness, comprehensibility and so on.
Haiduc et al. [S1] employed four students majoring in computer science to evaluate automatically generated summaries. The participants were asked to rate the generated keyword with four levels, from strongly agree to strongly disagree in only a single dimension. Then the researchers took an average score to evaluate the generated summaries. In order to compare results with Haiduc el al. [S1], Eddy et al. [S4] used a similar approach to assess their results.
Sridhara et al. [S20] invited thirteen participants to rate summaries' accuracy, content adequacy (whether some information is missing) and conciseness (how much unnecessary information is included). In a later work, Sridhara et al. [S21] employed nine human evaluators to judge the generated summaries on accuracy, utility-standalone (whether generated summaries can help understand the role of method parameter), utility-integrated (summaries help understand the intent of the method), necessity.
Similarly, Moreno et al. [S9] asked participants to evaluate content adequacy, conciseness, and understandability. Rai et al. [S15] concentrated on correctness, completeness, nonredundancy, and conciseness, while Dawood et al. [S34] evaluated summaries' usefulness and closeness to the source code. Wong et al. [S16] concentrated on accuracy, adequacy, conciseness, and usefulness. In a later work of automatic comment generation, Wong et al. [S17] claimed that the current evaluation criteria could be too fine-grained for determining if a comment will be committed and used by developers. They chose to use a more straightforward evaluation approach, which asked participants to rate the generated comments in just three levels: good, fix and bad. Shen et al. [S38] employed human evaluator to compare the performance among primitive commit, other summary and the generated summary of source code change.
It's interesting that the quantity of levels in rating dimensions is diversified. While most of researchers use a threelevel or five-level score, Haiduc et al. [S1] employed a fourlevel rating, which is called a four-level Likert Scale [14]. They abandoned the middle neutral option in order to exclude the situation of central tendency in the answers due to noncommittal answers.
2) Gold Standard Summary Comparison Gold standard summary refers to a human created summary for reference. For a keyword list generated by a trained model, a human-selected keyword list can act as a gold standard summary. Then comparison from the automatic generated summary to gold standard summary measures the effectiveness of the summary generator.
For example, Haiduc et al. [S2] collected six developers' summaries and used pyramid score [15] to measure similarity among the developers' summaries and automatically generated summary. Rodeghero et al. [S3] invited human experts to read the Java method and ranked the top five most-relevant keywords from the method. They computed the minimizing Kendall tau distance between the lists and carried out a Mann-Whitney statistical [16] test for further evaluation. In Wang et al.'s effort [S24], the gold standard summary was not only used to evaluate system-generated descriptions of the source code, but also employed to measure the intermediate result of their generator. Ponzanelli et al. [S39] also used gold standard summary to assess their summaries for various software entities. Kamimura et al. [S6] employed participants to grab key facts in the test case and compared them with automatically grabbed facts.

3) Extrinsic Evaluation
Extrinsic strategies evaluate the influence of the generated summaries when readers perform a particular task. It may directly measure the ability of a summary to improve program comprehension, reading speed, comment typing speed, etc.
Oda et al. [S35] carried out extrinsic research on how their automatically generated summaries help code understanding. They showed unexperienced developers with a function definition and corresponding pseudo-code. Then those participants assigned a 6-level score indicating their impression of how well they understood the code for each sample. Similarly, Mcburney et al. [S23] asked participants to rate for how the summary contains information that helps comprehension.
In contrast, Movshovitz-Attias et al. [S7] used an offline extrinsic evaluation, which successfully minimized its subjectivity. Because their study aimed at reducing programmers' type-in characters when writing comments, they used a character saving metric so as to quantify the percentage of characters saved by using the model in a word-completion setting, similar to standard code completion tools built inside code editors. Then they used the average percentage of saved characters per comment to assess the model's efficiency. The result showed that their model successfully saved up to 47.1% characters.

4) Statistical Analysis
Statistical analysis includes different statistical measures such as precision, recall, F-score, pyramid precision, etc. In most statistical evaluation, those measures of automatically generated summaries are commonly compared with a reference summary, which may be a human-written summary or summary generated by another model. This reference model or system is usually called baseline.
Accuracy, precision, recall, and F-score are simple but efficient ways to quantitatively evaluate the performance of natural language summary generator. Badihi et al. [S18] asked experts to write down lists of keywords for the target method and compared it with the generated keyword list. They used the two sets of lists to calculate accuracy, precision, recall, and F-score and compared these indicators with Rodeghero et al.'s eye-tracking approach [S3], finding out their result is better than eye-tracking approach's in every index.
Fowkes et al. [S8] asked human annotators to manually fold the source code and used the four index mentioned above to compare their methods and three artificial baselines with the manually annotated result. In Nazar et al.'s supervised learning based study [S25], they used some most common measures by comparing their classifier against random and existing classifier. What's more, they used precision, recall, and F-score to evaluate the effectiveness of their classifiers.
Besides using precision measure, Sridhara et al. [S22] used specific measures to evaluate their summary generator's ability to abstract high-level action. They measured the frequency of code fragments in which high-level actions can be identified, claiming that their measured frequency is high enough to demonstrate the broad applicability of their algorithm. They also counted the number of statements that were captured by generated description and the number of phrases in the resulting description, thus calculating the potential reduction in reading detail.
In artificial-neural-network-based studies, machine translation (MT) metrics is the most commonly used evaluation method. Hu et al. [S28][S29], Iyer et al. [S27] and Zheng et al. [S30] used two MT metrics BLEU(Bilingual Evaluation Understudy) score and METEOR (Metric for Evaluation of Translation with Explicit ORdering) to measure the accuracy of automatically generated summaries. Some studies also combined statistical analysis with other evaluation methods. For example, Zheng et al. [S30] also employed a human evaluation to assess the understandability and similarity between generated comments with human-written ones and interpretability. D. RQ4: How can we categorize source code artifacts from which we can generate natural language descriptions?
On different levels can developers generate natural language descriptions of code artifact. To answer this research question, we produce a distribution form shown in Table V and list the kinds of target artifacts with a few examples in this section.
Variables: Sridhara et al. [S21] generated parameters' names and integrated them with method summaries.
Code segments: For an input code segment, Wong et al. [S16] utilized similar code blocks' descriptions on Stack-Overflow. Wang et al. [S24] detected object-related statement sequences and described its high-level action.
Methods/Functions: McBurney et al. [S23] generated natural language summary for a method based on its context. Rai et al. [S15] detected methods' nano-patterns and generated summaries based on them.
Classes: Moreno et al. [S9] generated summaries for JAVA classes based on their contents, responsibilities, and roles. Malhotra and Chhabra [S14] used micro patterns and dependencies to create summaries.
Packages: Hammad et al. [S5] summarized the services of JAVA packages using template-based techniques.  IV. Discussion

A. Principle Findings
Table VI synthesizes the principal findings of our studies. Besides answering the research questions, we also list some other findings below.
• Source code summarization has been developing very fast in the last decade. In the early 2010s, most of the studies were based on term-based and templatebased summarizations. After Iyer et al.(2016) [S27] first employed artificial neural network in this field, many researchers started to use ANN to learn the hidden relationship between structural source code and natural language description, which has been proven surprisingly effective in the automatic code summarization field. • Some automatic summary generators rely heavily on the naming quality of identifiers, parameters, methods, and classes. If the source code contains too many local language representations (such as Chinese or Korean transcription), spelling mistakes, or abbreviations, the quality of the generated description may be severely affected.
In extensive and finely-supervised software system, this phenomenon may not be an impediment, but it may be a stumbling block in a small-scale system or a legacy system. • External data sources in online Q&A websites, opensource code repositories and version control systems, etc., have been used widely in this field. Exploiting existing human-written comment of code will significantly benefit the natural language description generation. • Over half of the studies use manual evaluation techniques to rate the conciseness, understandability, expressiveness, etc. However, this evaluation techniques is far from objective to assess the ability of natural language generator. The judgment of participants significantly depends on their program ability, experiences, personality and mood. So, offline evaluation and extrinsic evaluation need to be applied in evaluating the summarization. Therefore, the community should build a benchmark or a uniform standard for evaluating natural language summarization.

B. Challenges and Future research directions
Although software summarization techniques have received a lot of attention over the last decade and significant progress has been made in this field so far, future research still needs to be carried out. In the following, we list some possible future research directions which should can be interesting to the community.
Neural-network-based and deep-learning-based Study: Nowadays, although artificial neural network and deep learning have achieved great success in many other fields, structural information is still hard to be properly used in neural-networkbased source code summarization. Different from natural language translation, neural machine translation in source code translation should find a way to exploit the advantage of the code structure.
Cross-language United Model: With the development of large-scale software systems, exploiting multiple programming languages is common in a software system or an organization. But if we apply different program summarization techniques for different languages, confusions and inconsistency may arise. Few approaches can handle multiple languages at the same time. Therefore we envision a united model to generate natural language descriptions for various kinds of programming languages.
Multi-role-oriented Model: The information requested by different kinds of readers may be different. For example, authors tend to focus on the responsibility and role description of a method, which can quickly bring their memory back.
Software test engineers may need to know the control flow inside the program to employ branch testing, while the method invoker may care about the information regarding how to use the method correctly. How to synthesize different kinds of information remains unanswered.
Adaptive Description Generation System: Comment writing habit and word usage are very personal, which may vary from developer to developer or organization to organization. However, present natural language summarization fails to consider personal typing habit or company's comment regulation. So, it's crucial to adapt the system to suit users' habit. What's better, an incremental adaptive natural language summarization system for source code may be designed, which will automatically improve its performance after analyzing users' coding behavior.

V. Conclusions
Software summarization is an area which has been growing throughout the last decade. Due to the development of software industry and increase of the software complexity, program comprehension is more and more important, and thus the need for automatic code summarization techniques is growing.
In this paper, we present the result of a systematic literature review in the field which involves 41 different studies. The result provides useful information for researchers investigating this area to improve code summarization techniques for program comprehension. We hope this review and the proposed future directions can be useful to the community.


Usability evaluation to approve an information system design (case study: Immunization monitoring interface design)

. Prototyping is a useful technique to support the development process of building a software application. It is beneficial particularly when the developer focuses on the user. However, in the requirements phase, the developer has problems to give visualization about the task that should be done when the user interacts with the information system. So, this paper aims to demonstrate that with the usability evaluation in the requirements phase, it can help the IS developer to achieve approval from the potential user of the IS. This paper employs a case study in the process of developing Immunization Monitoring Information System (IMIS) at the Srondol Community Health Centre ( Pusat kesehatan Masyarakat / PUSKESMAS), Semarang, Indonesia. For the experiment, this paper only uses two potential IMIS users. The IMIS interface will be tested for its usefulness with variable effectiveness, efficiency, and easy use. The output generated from the experiment was an effective, efficient and easy-to-use interface design for IMIS from the perceptions of child guardians and the perspective of Community Health Centre staff. This paper provides recommendations, that in the requirement process, usability tests can be used to get approval and recommendations from potential user of information systems.

Introduction
Employing the principle of good design, it gives an assumption that systems should be easy to learn, can increase user productivity and satisfaction, can increase user acceptance, decrease user errors, and decrease user training time [1]. It is mentioned, that software developers of health information systems often ignore interface features, user duties, user preferences, and usability problems [2]. It can lead to systems that reduce health care staff productivity.
A number of factors could be attributed to the bad design of systems such as limitations of the developer about the knowledge of user-centred design. In U.S, shows only 61% of health care system projects that fulfill the specifications of the customer [3].
Recently, the health care providers (or community health care centre) are being challenged to present and handle data effectively with the use of the technology. They need technology that can embrace and enforce the data on their ease of use.
Information technology is altering the way patient data is collected and collected and can affect clinicians ' decision-making procedures. There are several valid usercentred design methodologies, however, none address the requirement in the process of design. This paper aim is to show the process of designing user-centred interfaces using usability evaluation to get user approval in the health information system.

Literature Review
User interface design is associated with designing a system to perform tasks that fit together, suit the context in which the system is used, and meet the task aims of the user, and as a response, human-computer interaction task analysis should be concerned with describing and evaluating the task environment of the user.
Usability testing is a technique to understand all functions that can work within an interface of a system, that focus on user that will be using the system [4]. When applying the concept of usability to sustainable behavior, it could say that the user-centre of a sustainability solution can be assessed by evaluating how efficiently the side effects of the use of a product are lowered, what the expenses are (money, time, effort) and how satisfied the user group [5]

User Task Analysis
The aim of the task analysis is to gather enough data about the task set to be supported by the user interface to allow user interface design. Task analysis is used in three distinct ways within Human-Computer Interaction, each happening at a particular stage in the design process [7].
The first and most popular knowledge of task evaluation at the beginning of the design phase is the description of the tasks and task setting of the user, the existing task condition. Task assessment (appropriate) is the subject of this section in this sense [8].
The second interpretation of the task analysis relates to the assessment within the fresh model of the suggested user assignments. In this sense, task analysis relates to ongoing reflection on the effects of design decisions and should be referred to as simple design or task design [8].
Third, task analysis can also involve analyzing the duties as they are or should be conducted with a specific user interface. In this sense, task analysis relates to the assessment of user interface elements and should be called user interface assessment [8].
User interface design is associated with designing a system to perform tasks that fit together, suit the context in which the system is used, and meet the task aims of the user, and as a response, human-computer interaction task analysis should be concerned with describing and evaluating the task environment of the user. To create the user task this paper used the structure of the navigation system.

The importance of selecting respondents for Usability testing
The selection of respondents is very important in an evaluation of usability. The chosen respondents are expected to be able to represent the entire population of users because testing carried out with respondents who do not represent the user population will not be of any use [6].
According to Rubin [9], research respondents must be taken from those who actually use the product so that the results obtained are valid and can be justified. The number of respondents 4 or 5 already represents all existing users to find 80% of the deficiencies of a product. However, if there is enough time and resources to do the testing with more than 4 or 5 participants it is better to do it because there will be a possibility of finding another 20% errors.
Whereas according to [10] the best number of respondents in each usability test is 5 people, respondents who number 5 are considered able to represent most usability problems without involving many resources.

Usability variable
According to Kirwan [8], a product can be said to be efficient if the user can use the product by specific time to meet their objectives accurately and completely when using the system. According to [11] usability is the level of usability of a product from the user's perspective to achieve an objective effectively, efficiently, and satisfactorily. Usability evaluation needs to be done to ensure that a product can be run without giving confusion to the user.

Method
To get approval for good design, this study following steps : First, identify the user's characteristic that potential used the system. Then, defining the user task by using the navigation structure of the web. Next is defining the usability variable. Then finally, measuring the usability of the IMIS to get approval from the user.

Understand the user that potential used the system
In this stage, it is necessary to know the characteristics of the user according to their duties in the system. In the Srondol community health centre, those who will use IMIS are health workers and parents. The two users above are users who play an active role in the continuation of immunization monitoring. To understand the ease of use and user satisfaction. The user recognized based on the education level.

Define the User Task
Preparing the user's task is essential, so, in the requirements, process can be identified what will be user should do by using the system. According to Dix et al. [6], the design object is not just a computer system or device, but overall technical intervention. System navigation is defined as a page in a system and how they are interconnected. Navigation in the information system must be able to explain what will happen when a button is pressed so that users can understand where they are in the interaction that occurs.
According to Dix et al. [6] there are two structures in a web namely local structure and global structure which are explained as local structure is a comprehensive explanation of a page to achieve the desired goal of the user. The task of IMIS users created using the local structure or navigation. The local structure of health care staff and children guardian is in Figure 1 and Figure 2.

Preparing the Dashboard
The health care staff dashboard page contains a summary of information in the information system. The admin dashboard page contains child data, parent data, health worker data, and monthly immunization delivery charts. The administrator dashboard page can be seen in Figure  3. The parent dashboard page contains a summary of the information Children guardian needs in the information system. This page contains data on the child's gender, child's age, the number of immunizations the child has received, height, weight, and head circumference of the child. The Children's guardian dashboard page can be seen in Figure 4.

Define the Usability Variable
First, Effectiveness or effectiveness describes how well users can use the system to achieve the goals they want. Effectiveness is measured based on the level of user success in completing a given task.
To know the aspects of effectiveness is based on the level of success of respondents in carrying out a list of tasks on each menu ( Table 2 ). In the effectiveness calculation, the usability matrix is used with the success rate measure proposed by [12] because this matrix is easier to measure. The assessment is not only absolute on the success and failure but also used the condition of halfsuccessful or when the user is only able to complete part of the given task. The success rate is defined as the percentage of tasks completed by the respondent correctly. Following is the success rate formula [12]: The process of evaluating task completion is based on the criteria for success in carrying out the assignment, referring to the Sample Success Criteria for Scoring Scenarios, which can be seen in Table 4.

Value
Criteria Success − Respondents complete the task with minimal effort − Respondents reach their goals for a maximum of 2 attempts − Respondents did not receive help from researchers − Respondents did not ask the researcher − Respondents did not find an error message (error message) − Respondents did not give expressions of confusion / frustration Half Succes − Respondents complete the task with moderate effort − Respondents reach the goal a maximum of 3 attempts − Respondents received 1 assistance from the researcher − Respondents found 1 to 2 error messages − Respondents expressed little confusion / frustration Fail − Respondents did not complete the task or complete the task with difficulty − Respondents reach the goal in 4 or more trials − Respondents receive 2 or more help from researchers − Respondents found more than 2 error messages − Respondents express confusion / frustration − Respondents revealed that the task was completed when the actual task had not been completed.
Second, efficiency describes the resources needed by users to achieve the goals they want. The resources in question can be in the form of mental, physical, time, and cost. In this research, time will be used as a measure of efficiency. Third, satisfaction is the level of user satisfaction in using information systems. Satisfaction here includes both appearance and functionality. Satisfaction refers to the user's perceptions and opinions about the product both in terms of appearance and functionality. In measuring the aspect of satisfaction, questionnaires are in the form of written and oral questions. According to [13] to determine the value of the satisfaction aspect can be seen from the comparison between the actual score and the ideal score. The actual score is obtained through the calculation of all respondents' opinions according to the given weight classification. While the ideal score is obtained by multiplying the number of questionnaire respondents with the highest weight. Here is the formula for obtaining a total score.
(2) After finding the results of the calculation of values in each of the aspects obtained then carried out a comparison with Table 5 about the criteria for the interpretation of values.

Usability Testing on Health Care's User
The usability test results on the group of administrator respondents on aspects of effectiveness, efficiency, satisfaction, and ease of use are shown in Figure 5. The effectiveness value obtained is 92.9%, based on observations made, respondents feel less familiar with the use of date picker when entering data in the form of dates. Respondents feel more familiar if you enter it manually.
Based on the time of completion of the task, it obtained an efficiency value of 87.4%. From the results of observations made, the most time was spent by respondents to fill in vaccine data forms.
From the aspect of satisfaction, the value was 86.7%. Based on observations, respondents were satisfied with the whole system, but on the recapitulation page, it was better to differentiate immunization according to sex.

Usability Test Children Guardian based on age
The usability test results on the group of parent respondents based on age in the aspects of effectiveness, efficiency, and satisfaction are shown in Figure 6.

Fig. 6. Result Usability Test Children Guardian Based on Age
The effectiveness aspect of children's guardian user groups based on age has the highest value in the age group of 31 to 40 years. This is because respondents are at a productive age and understand the use of the system well. While the lowest value is under the age of 20 years because respondents are not accustomed to using computers.
Based on the time of completion of the task, obtained the highest value of efficiency of parents respondents at the age of 31 to 40 years. Respondents felt they could use the system properly without needing help. The lowest value for the aspect of efficiency is at the age of fewer than 20 years because respondents are not accustomed to using computers.
The highest aspect value of respondents' satisfaction was at the age of fewer than 20 years because respondents were satisfied with the features offered by IMIS. While the lowest satisfaction aspect value is at the age of 31 to 40 years. Respondents felt the need to add a guide to the use of the system.

Usability Test Children Guardian based on education level
The results of usability testing in the group of parents respondents based on education on the aspects of effectiveness, efficiency, and satisfaction are shown in Figure 7.

Fig. 7. Result Usability Test Children Guardian Based on Education Level
The effectiveness aspect of children's guardian user groups based on education has the highest value in D3 educated parents. This is because respondents are at a productive age and understand the use of the system well. The value drops in parents with a Bachelor's education because some of the respondents are elderly and have difficulty using a computer. While the lowest scores were parents with a junior high school education of 81.3%.
Based on the time of completion of the task, obtained the highest efficiency value of parent respondents was in parents with D3 education. Respondents felt they could use the system properly without needing help. The value drops in parents with a Bachelor's education because some of the respondents are elderly and have difficulty using a computer. While the lowest value for the efficiency aspect is in parents with junior high school education because respondents are not accustomed to using computers.
In filling out the questionnaire, the highest aspect value of the respondents' satisfaction was among parents with junior high school education because the respondent was satisfied with the features offered by SIMUN. While the lowest satisfaction aspect value is in parents with elementary education with a value of 84.2%.

Conclusion
From usability test of each respondent has been conducted shows the usability value of IMIS is very feasible to be used. IMIS has achieved its objectives effectively, efficiently and satisfactorily. From the usability testing the IS developer received the feedback about the Immunization monitoring interface design. From the experiments, we suggest that the usability evaluation should be conducted in the requirements phase to received a feedback when prototyping was used in the process developing of IS.


Bias-Aware Heapified Policy for Active Learning

The data efficiency of learning-based algorithms is more and more important since high-quality and clean data is expensive as well as hard to collect. In order to achieve high model performance with the least number of samples, active learning is a technique that queries the most important subset of data from the original dataset. In active learning domain, one of the mainstream research is the heuristic uncertainty-based method which is useful for the learning-based system. Recently, a few works propose to apply policy reinforcement learning (PRL) for querying important data. It seems more general than heuristic uncertainty-based method owing that PRL method depends on data feature which is reliable than human prior. However, there have two problems - sample inefficiency of policy learning and overconfidence, when applying PRL on active learning. To be more precise, sample inefficiency of policy learning occurs when sampling within a large action space, in the meanwhile, class imbalance can lead to the overconfidence. In this paper, we propose a bias-aware policy network called Heapified Active Learning (HAL), which prevents overconfidence, and improves sample efficiency of policy learning by heapified structure without ignoring global inforamtion(overview of the whole unlabeled set). In our experiment, HAL outperforms other baseline methods on MNIST dataset and duplicated MNIST. Last but not least, we investigate the generalization of the HAL policy learned on MNIST dataset by directly applying it on MNIST-M. We show that the agent can generalize and outperform directly-learned policy under constrained labeled sets.

Introduction
Nowadays, deep learning has been widely used in several fields, like medical field or automatic driving. However, to reach the whole potential of deep learning, we still struggle to prepare tons of annotated data for training. The progress of collecting such amount of data is obviously a tedious and laborious work. Thus, it is a critical bottleneck to obtain adequate data for training an accurate model. To solve the problem, simply collecting more data may be the most intuitive idea, yet it is highly time-consuming and expensive in certain domains such as cancer detection, Natural Language Copyright c 2019, National Tsing Hua University. All rights reserved.

… … …
Uncertainty Strategy Other Strategy Policy Figure 1: For selecting the most acceptable image from the unlabeled set, we construct a heap for comparing the whole data two by two which is determined by policy individually. The policy will observe bias-aware feature (Fig. 3) to avoid using uncertainty-based sampling strategy. After the whole comparison, the final image will be annotated and sent to the training set. This process will be repeated until the budget is exhausted.
Processing tasks, etc. Thus, active learning comes in handy to minimize the cost by querying important data in order to improve accuracy by labeling as few data as possible.
As to the methodology of active learning, there have been quite a few heuristic methods querying data according to uncertainty (Shannon 2001;Zhou and Sun 2014;Tang et al. 2017), diversity (Sener and Savarese 2018;Wang et al. 2017), etc. Additionally, some work carries out active learning by virtue of multi-heuristic methods such as RALF (Ebert, Fritz, and Schiele 2012) which tries to manage different methods with hybrid strategies according to the time, considering that exploration/exploitation criteria should be balanced in different moment.
Nevertheless, imbalanced data is the one that possesses stronger relation to the strategy rather than time, which brings about overconfidence, quite problematic as querying data. To cope with it, many works (Sener and Savarese 2018;Wang et al. 2019;Geirhos et al. 2019;Bachem, Lucic, and Krause 2017;Lakshminarayanan, Pritzel, and Blundell 2017;Pop and Fulop 2018) intend to eliminate the overconfidence effect. One of the approaches is to query by commit-tee (QBC) (Lakshminarayanan, Pritzel, and Blundell 2017;Pop and Fulop 2018), using the ensemble idea to avoid overconfidence on one single model through multi-models, sacrificing computational cost for training stability. Another approach is to query by disagreement (QBD), directly learning from errors which are probably disagreement samples, including unseen samples and in-class potential uncertainty samples, which are predicted incorrectly but possess high confidence from the classification model. However, it is a chicken-egg problem that it is hard to identify if the sample is an error before the annotation. Thus, some works (Gissin and Shalev-Shwartz 2019; Su et al. 2019) propose using meta-heuristic method to approximate the idea. More specifically (Gissin and Shalev-Shwartz 2019) queries data that is likely to be unseen. (unlike the labeled set distribution.) However, it is not general enough to model the behavior of in-class potential uncertain samples.
Considering the generalization of methods, they are not general enough that in every different case, algorithms should be customized. What if we can guide the model with a general agent that shares the experience of querying data? Recently, there are a few works (Bachman, Sordoni, and Trischler 2017;Pang et al. 2018;Konyushkova, Sznitman, and Fua 2017;Fang, Li, and Cohn 2017;Chen et al. 2018) focusing on ways of "learning to active learn". Through similar features of data between different datasets, the agent is capable of sharing the experience that is transferred from other datasets. For example, a stream-based reinforcement learning (Fang, Li, and Cohn 2017) on prediction of part of the speech, the agent's selection depends on the grammatical architecture of a sentence, which can be applied on both Spanish and Dutch. Additionally, Chen et al. (Chen et al. 2018) propose to take video motion as feature to share experience. However, in spite of the avoidance of time-consuming by using stream-based active learning, the stability is influenced by order of the stream.
To sum up, the low generalization of current methods for active learning is a critical problem that can result in high cost for designing customized algorithm, and also about how we avoid overconfidence that obstacles uncertainty querying is what we should solve urgently. In this paper, we propose a bias-aware heapified active learning method for pooling based active learning called heapified active learning (HAL). It can observe the whole data and spend low computing time with a heapified structure, which is not influenced by the problem of ordering in stream-based reinforcement learning. Additionally, during querying, we design a bias-aware feature which contributes to the switching of strategy. Learning with prior of images, the experiences can be transferred to other target domains and remain high performance. In short, our HAL enables the agent to make use of features of the training dataset as to query data with the best strategy, avoiding bias which skews the labeled domain. In the experiments, our model outperforms other baseline methods on MNIST dataset and synthetic duplicated MNIST dataset which mimics properties in static surveillance videos. Moreover, our policy trained on MNIST achieves the best results on MNIST-M. This demonstrates the great generalization of our method across datasets.

Contribution:
• The policy of our methods for querying data is formulated generally which possesses high generalization between datasets. • Our pool based policy agent queries data more efficiently with low time consumption through heapified structure. • Through using bias aware feature, the policy will be able to avoid overconfidence which makes uncertainty based query method inefficiently. In the following sections, we first describe related work in Sec. 2. Then, we introduce our main technical contribution in Sec. 3, including feature designing, policy setting and so on. Finally, we report our experimental results in Sec. 4.

Related Work
To improve the efficiency of data sampling, many works tend to use uncertainty-based method and select more sparsing data at the same time in batch mode selection. However, this kind of methods cannot solve the overconfidence problem. In order to deal with it, in recently, there are three main research directions on active learning related to ours. One is learning with other experts(query by committee, QBC (Pop and Fulop 2018;Gal, Islam, and Ghahramani 2017;Rosales, Krishnamurthy, and Bharat Rao 2008)). Another is learning from disagreement(query by disagreement, QBD (Gissin and Shalev-Shwartz 2019; Kane et al. 2017;Zhang and Chaudhuri 2014;Ducoffe and Precioso 2018)). The other is to manage different criteria and combine the strategies (Pang et al. 2018;Konyushkova, Sznitman, and Fua 2017;Fang, Li, and Cohn 2017;Chen et al. 2018). Query By Committee. The QBC method is to make use of mutual information from multiple models and enable certain sample to be more confident. For instance, DBAL (Gal, Islam, and Ghahramani 2017) generates different outputs through Bayesian network with noises called MC-dropout. However, the outputs generated from different noisy models are not ideal. DEBAL (Pop and Fulop 2018) , following the previous method, proposes the concept of ensembling to solve the problem above. The difference between our method and the ensemble idea is that we use features of labeled data to let the policy model conscious of the situation of overconfidence. Query By Disagreement. To query by disagreement, we should know which sort of data belong to disagreement cases, thus meta-heuristic exploring strategies are required, like DAL (Gissin and Shalev-Shwartz 2019) which selects data predicted unlabeled by a discriminator trained with labeled and unlabeled data and DFAL (Ducoffe and Precioso 2018) using adversarial image to build up an image decision boundary, finding its nearby unlabeled sample as uncertain data. However, those meta-heuristic strategies can not be general enough. Our method uses data-driven policy to learn switching strategy for disagreement samples instead, which can be more general in other cases. Learning to Active learning. Instead of designing the algorithm for selecting unlabeled data heuristically, some adopt stream-based learning (Fang, Li, and Cohn 2017)  comparison.(E l , Eu is labeled/unlabeled set embedding feature ∈ R fn ) In every single comparison with heapified policy, π θ , the agent will choose a preferable data. After a series of comparison, the data which is estimated as the most valuable will be annotated and added to the training set D l . By training the prediction model f φ with the new labeled set D l and evaluating by validation set, D val , we can obtain the performance growth of f φ which can be used as the reward for the agent π θ .
(RL). Through training on Deep Q Network (DQN), it can learn the selecting policy and choose informative data that enable the model to be more robust to certain types of errors. As the number of selected data reaches the budget, the Markov Decision Process (MDP) terminates. The state for the agent is composed of the content, marginals and the confidence of prediction. By doing so, the agent can give consideration to both the uncertainty of every word class prediction and the architecture of every sentence which can avoid the bias in the prediction model. At last, taking the performance growth as reward can enable the model to predict the reward of every selection precisely as to make great progress on the performance of the prediction model. However, they trade off time consuming and performance by just reviewing a subset of data and missing more important data in early steps. As for our method, we use pool-based active learning, selecting the most valuable one in the dataset and using heap structure to reduce the time complexity.

Method
In the following, first, we overview our active learning pipeline in Sec. 3.1. Second, we describe the design of the observation features for policy learning and introduce each of them individually in Sec. 3.2. Third, in Sec. 3.3, we propose a new structure of policy which is "heapified" as querying data, and each policy is learned with offline policy gradient. Before that, we define some common notations below. Notation : We have three sets, labeled set, validation set, and unlabeled set, which are denoted as is image, we assume there are L classes and denote y i ∈ {1, 2, ..., L} as labels. Besides, we have two models; one is a classification model f φ with parameter φ, and the other is an agent π θ with parameter θ. In the classification model, we extract embedding feature which is denoted as f E φ (.) ∈ R fn .

Overview
As illustrated in Fig. 2, in our active learning procedure we have a prediction model f φ supervised by D l . Next, our agent π θ will repeatedly pick two random samples from D u and compare which unlabeled data has more impact on classification model f φ until the whole D u has already been compared. After iterating the comparisons, a final image will be determined and annotated by annotators, and then we add it to D l for the training of the prediction model f φ . Finally, the reward can be calculated by evaluating the marginal performance of the task with the evaluation set D val , offering the agent π θ to learn. Through the steps mentioned above, the agent π θ is able to learn a querying policy from the data.

Observation Feature Designing
As the objective of active learning, we aim to find out the hard samples and the disagreement samples. The disagree-  Figure 3: Bias-aware concept. It's riskier to fall in overconfidence condition that the eigenspace contribution highly depends on principal eigenvectors, leading to non-continuous distribution of data described by only specific dimensions such as the (V1, V2) eigenspace, which have large eigenvalue. Thus, we need to reduce the dependence on principal eigenvectors and get to obtain continuous distribution like the space such as the (V3, V4) eigenspace, which have small eigenvalue. ment samples include unseen samples and the in-class potential uncertain samples. The unseen samples are the data far from labeled set distribution. The in-class potential uncertain samples are predicted incorrectly but possess high confidence from the classification model. Therefore, feature design can be divided into three parts, bias-aware feature, uncertainty to deal with hard samples, and the disagreement sample learning, respectively.
Bias-aware: maximum component suppression During query procedure, imbalanced data usually results in overconfidence of certain labels, which introduces bias on them. Thus, we design bias-aware feature, enabling the agent to observe the distribution of each class for the query policy. As shown in Fig. 3, overconfidence usually occurs as the real data distribution is non-continuous. Additionally, the blue region in Fig. 3 is where some samples are predicted incorrectly but possess high confidence from the classification model, we called that in-class potential uncertainty sample. Therefore, in this case, selecting samples with high uncertainty is not an optimal policy. In contrast, if the data distribution is continuous, selecting samples located at the boundary area benefits the training of the classification model.
Every data in the dataset can be represented by their own embedding features f E φ (.) which is extracted from the classification model, indicating that they can be mapped to a multidimensional space. In each class, through the calculation of the eigenvalues, we can observe the degree of the dominance of each vector. By taking the largest eigenvalue, the bias-aware feature offers information about the degree of how simply a certain class of data are described. In our design, we select the value oppositely as the feature BA(.) shown in Eq. 1, we called it as maximum component suppression. Lower value implies the oversimplification of feature description, causing overconfidence on the unlabeled set D u . As a result, the bias-aware feature can be served as a signal enabling the agent to observe the distribution of labeled data D l for switching different strategies. Here, we define bias-aware feature as follow: where BA(.) ∈ R L is the feature of bias aware, is the set of class-wise eigenvalues of labeled set's embedding features and this criterion describes how confident can the embedding feature represent the data without main eigenvector.
Uncertainty In order to boost the performance of the classification model f φ trained on rough data at the beginning of selecting data, we need to find out hard samples located in ambiguous regions near the decision boundary. Here, we model it by MC-dropout (Gal, Islam, and Ghahramani 2017) which outperforms Shannon entropy. We perturb the model by dropout and compare it with the unperturbed model so as to find out how uncertain is the data. That is, the higher the uncertainty of the data, the more it is worth to be selected. The MC-dropout method is formulated as follow: where the H(x; φ) = − L i=1 P (ŷ i |x; φ)log(P (ŷ i |x; φ)) , y i is the probability distribution, φ is the parameters of active model and φ is the parameters with noise by dropout which is done n times.
However, depending merely on information of uncertainty limits the growth of performance resulting by overconfidence, so we need to solve it by disagreement samples.
Disagreement sample learning In order to solve the overconfidence samples, we try to use the concept of QBD to learn from disagreement samples , which are unseen samples and in-class potential uncertain samples clearly defined in Sec. 3.2. To find out unseen sample, inspiring by DAL (Gissin and Shalev-Shwartz 2019), we query samples that are far from class-wise labeled set distribution. We formulate the calculation of the distance shown as follow: where the diversity feature is defined as the distance between unlabeled data and the labeled set representation of each class distribution. The Dist(.) is defined as follow: where the x is input image sample, φ is model parameters, f E φ (X D l y=yi ) ∈ R fn is the mean of embedding features in each class of labeled set and f n is the length of the embedding feature. We have ablation study about labeled set representation in table 1. In the Eq. 4, we calculate the distance between the unlabeled data D u and the labeled data D l to represent whether data is seen or not for the classification Here we use memory replay to achieve reward collection efficiently. In every single episode, the agent is required to choose only K images as budget for labeling to the training set D l . In each data query, the agent will go through unlabeled set Duwhich have M images, and the certain path of the final winner of the whole comparison (dark blue path shown above in the figure) is the most related reward's experience. Policy learns from the path and we show up detail of the decision process with agent network in double box. model f φ . In addition, we normalize the distance for each class owing that every class distribution is quite different.
On the other hand, searching in-class potential uncertain samples for sampling is quite tricky unless we provide handcraft features (e.g. SIFT (Lowe 2004), SURF (Bay et al. 2008), HOG (Dalal and Triggs 2005), BoVW (Chandra, Kumar, and Jawahar 2012)) as prior and information of labeled set D l as constraint.
As designing the feature we observe the model prediction, embedding feature of the unlabeled set D u and some analysis of the labeled set D l .The feature of a single data can be represented as follow: O = {I(x; φ), D(x; φ, D l ), P rior(x), BA(φ, D l )}, (5) using the uncertainty approach of mutual information Eq. 2 as the value of uncertainty for exploiting the mainstream data. To explore unseen case in labeled set D l , we use Eq. 3 to model it. In addition, as to in-class potential uncertain sample which provides a conditional prior, we add a handcraft feature to describe the image statistic information for the active modelf φ to explore more efficiently. Finally, we express the bias-aware feature with D l by Eq. 1 in order to prevent overconfidence which means that in a few classes, misclassification occurs which is caused by low complexity of class features description.

Heapified Policy
Our policy π θ is a maximum-heap like pooling based query method, so the action space(A) is quite large. Thus, to learn experience more efficiently, we adopt off-policy policy gradient method. As shown in Fig. 4 , our single episode is limited by budget K and our heapified policy will select the most valuable image from M unlabeled set images. Then, we break the task into as many sub-policies, which only compare two features of images, and the better one advances to the next round. We analyze the time complexity of Monte Carlo experience collection and maximum heapified like sub-policies. The time complexity of maximum heapified collection is O(logM ) less than Monte Carlo collection which is O(M ) . In Monte Carlo sampling method, in order to select the best item, we need to compare pair item M − 1 times. On the other hands, maximum heapified collection uses logM times to achieve the goal of the most influential of classification model performance unlabeled data selection. In this setting, even if the action space is reduced, the global information(overview of the whole unlabeled set) still remains. Sub-Policy model. Our sub policy agent a = π θ (s) tries to compare which one is better based on two image's features, O define in Eq. 5, where a ∈ {0, 1}, s = (O 1 ,O 2 ). After two comparisons are done, the two winner data will form the next state, noted as the sub transition T (s t+1 |a top tion task with prediction model φ as r = Acc(D val , φ ) − Acc(D val , φ), where φ is trained model parameters and the φ is original parameters before training. Offline policy gradient. The reward collection is not efficient and single collection cost much time by reward designed as the increase of performance. Therefore, we learn from previous sampling reward and decision. Then we compute offline-policy gradient to update model as follow: logπ θ (a i,j,t |s i,j,t ) * r * corr . (6) where N is episode of game and the K is limited of budget.
M is the number of totally unlabeled set images. π θ (.) is now noted as probability estimate.The corr term is to correct the reward which remained from previous policy action probability. The correction term of reward is noted as π θ (ai,j |si,j ) π θ (ai,j |si,j ) , it will maintain the present behavior if identical to previous experience, where π θ (.) is previous probability estimate, and the π θ (.) is nowstaged probability estimate. The agent will update their gradient direction more stably with previous experience.

Experiments
We conduct experiments to validate the proposed biasaware learning to learn policy in cross modalities setting and image duplicated setting. Firstly, in Sec. 4.1 , the result of ablation study shows that our method using bias aware feature and mean representation of labeled set as diversity hint obtain the best result with a few labeled data in the beginning and the experiment is in train model from scratch setting. Secondly, in Sec. 4.2, we get better result comparing with other baselines in finetune setting. Finally, we validate the transferability of our query policy across datasets in Sec. 4.3. We report average (15 times) performance of all experiments.
Implementation detail. We train classification model LeNet5 (Lecun et al. 1998) with two datasets. One is MNIST (LeCun and Cortes 2010) , and the other one is MNIST-M (Ganin and Lempitsky 2015) which blend background with color photos from BSDS500. Firstly, we split MNIST, MNIST-M in three subset -labeled, unlabeled and validation set (D l , D u , D val ), which amounts to (50, 60000, 10000) training pairs with balanced number of class. Secondly, we use Adam optimizer (Kingma and Ba 2015) with learning rate 0.001 to train our policy agent in 800 episodes. Each episode has 10 steps and each step samples 10 images. The discount factor of policy gradient is set as 0.9998. Finally, we use the accuracy to plot a learning curve with the size of images and ALC norm = ALC−A rand Amax−A rand which is mentioned in the active learning challenge (Guyon et al. 2011). Moreover, ALC is the performance of the classification model by proposed query method. A rand is performance of the classification model by random query. A max is performance of the classification model by fully D u with label which will be used in table 1.

Ablation Study
Diversity feature. In the design of the diversity feature, we calculate the distance between the representation of unlabeled set and the labeled set. There are different kinds of statistic method to represent the diversity feature. We compare these methods, including mean, median, mode, maximum and minimum in table 1 by average ALC norm on MNIST. As table 1 shown, we use average ALC norm as an indicator and we can find out mean representation of the class-wise labeled set feature is the best choice. Thus, we apply mean representation method to represent labeled data and calculate the diversity feature of unlabeled data by Eq. 3. Bias aware feature. We design the bias aware feature to avoid overconfidence condition in query data procedure. In order to simulate the dilemma, we train classification model from scratch with little labeled data. Because of imbalanced data (mode collapse (Pop and Fulop 2018) have mentioned), the effect is more extreme on a small dataset, resulting in overconfidence. As Fig. 5 shown, we can see that heapified active learning w/ bias feature can get better performance than w/o bias feature in the interval from 50 to 100 images. The uncertainty approach-DBAL, due to incomplete data understanding, faces overconfidence in the beginning. Thus, we know the importance of bias aware feature to avoid overconfidence at the beginning of the query procedure.

Compare Previous Works
Here, we compare different types of query methods on MNIST and duplicated MNIST which has many redundant and noise information. From the results, we show that our HAL is outstanding both dataset. Before that, we introduce the baseline methods as following: w/ bias aware wo/ bias aware DBAL Figure 5: The ablation study of bias aware feature: w/, w/o bias aware comparison. Bias is easily be generated while training from scratch, resulting in uncertainty approach-DBAL will not be useful. Thus, with bias aware feature, overconfidence can be prevented.  figure, we can find out that our HAL only needs less than 100 images to achieve over 85% of accuracy compared to other methods on average. On the right figure, even in a repeated and noised dataset, HAL can achieve over 85% of accuracy with less than 75 images; on the contrast, other methods need over 100 images to reach this criterion.
• Random: Sample data uniformly from D u .
• Entropy (Shannon 2001): Sample maximum value of chaotic prediction from D u . • DBAL (Gal, Islam, and Ghahramani 2017): Apply MC-dropout in the model to produce noises, and then query data with Eq. 2 from D u with maximum value. • K-center (Sener and Savarese 2018): It will compute the minimum Euclidean distance d of an unlabeled data by kcenter(x i ) = min(x i , x j ), where x j ∈D l . Then, it will query data with the maximum distance. • Stream-based policy network (Fang, Li, and Cohn 2017): Through Deep Q Learning (DQN), the agent learns the strategy of choosing images.With the arrival of every batch of images, the agent will decide if the batch of data is necessary to be added to the training set by observing the feature of the batch with the length of action space len(A) = 2. As the budget is exhausted, the selection process will be terminated. As shown in Fig. 6, our method queries data more efficiently than the other method in the whole training procedure. Instead of the uncertainty based method, they are unstable in the beginning and fall in the overconfidence condition. Specifically, we outperform the stream-based agent on average that it misses many important data in early steps. On the other hand, we create a special dataset to test the ability to perform generally among repeated and noised dataset.
Synthetic dataset: In real world application, there may be a lot of redundant data and make the model bias easily. For example, image data from surveillance camera, it may completely capture the same street view for hours. In this scenario, the capability to avoid duplicate information is essential. Therefore, we create a synthetic dataset -Duplicate M N IST with 60000 images. In the set, we have 48000 class-uniformly repeated image (80 percent of the total dataset) with random Gaussian noise. In the right figure of Fig. 6, our method is general enough that it is able to achieve high performance in few amounts of data when encountering repeated and noised images.

Generalization
Our method learns how to query from meta-experience with image spatial texture structure as prior by HoG, so we can adopt the experience in cross-domain setting which is Gray(MNIST) v.s. RGB(MNIST-M) scale and outperform with 5% through querying procedure on average. In this setting, we train the agent in MNIST and directly apply as a query method in MNIST-M. We obtain a better result than training from scratch randomly shown in Fig. 7. In this setting, we realize that our HAL is a general method can adopt query experience to other works that have similar prior.

Conclusion
We proposed a bias-aware policy network called heapified active learning (HAL), which prevents data sample bias due to overly confident model prediction. Moreover, our policy model trades off the query time complexity and global information by heapified structure in pooling based active learning setting. In addition, in our experiment, HAL outperforms other baseline methods on MNIST dataset and duplicated MNIST. From the results, we can show that our method is able to reach high generalization on different dataset which share similar features.

HAL (Our) Train from scratch
Figure 7: The generalization of query method, HAL . Using our HAL query data directly is more efficiently than training from scratch randomly by about 5% performance is Gray(MNIST)→ RGB(MNIST-M) dataset