OpenRaiser/Intern-Atlas huggingface dataset:
A New k-Shortest Path Search Approach based on Graph Reduction
Venue: arXiv cs.DS 2019
Year: 2019

We present a new approach called GR (Graph Reduction) algorithm for searching loop-less k-shortest paths (1st to k-th shortest paths) in a graph based on graph reduction. Let a source vertex and a target vertex of k-shortest paths be v_s and v_t respectively. First our approach computes shortest paths to every vertex from v_s and v_t respectively, and reduce a graph to a subgraph that contains all vertices and edges of loop-less k-shortest paths using the already computed shortest paths, and apply an existing k-shortest path search algorithm to the reduced graph. A graph can be reduced quickly after computing the shortest paths using them, therefore a very efficient search can be achieved. In an experiment using a hypercube graph which has 16384 vertices where k=128, the number of vertices is reduced to about 1/22, and a variant of Dijkstra algorithm for k-shortest path search were speeded up by about 365 times. We implemented a fast k-shortest path variant of bidirectional Dijkstra algorithm (k-biDij) which is the state-of-the-art algorithm and the fastest as long as we know, GR outperforms k-biDij in dense scale-free graphs. However, k-biDij outperforms GR in hypercube-shaped and sparse scale-free graphs, but even then GR can also speed up it by 12.3 and 2.0 times respectively by precomputing all-pairs shortest paths. We also show the graph reduction can be done in time complexity O(m + n log n). We also introduce our improvements to k-biDij simply.
Neural Network Based Undersampling Techniques
Venue: arXiv cs.LG 2019
Year: 2019

Class imbalance problem is commonly faced while developing machine learning models for real-life issues. Due to this problem, the fitted model tends to be biased towards the majority class data, which leads to lower precision, recall, AUC, F1, G-mean score. Several researches have been done to tackle this problem, most of which employed resampling, i.e. oversampling and undersampling techniques to bring the required balance in the data. In this paper, we propose neural network based algorithms for undersampling. Then we resampled several class imbalanced data using our algorithms and also some other popular resampling techniques. Afterwards we classified these undersampled data using some common classifier. We found out that our resampling approaches outperform most other resampling techniques in terms of both AUC, F1 and G-mean score.
API Misuse Correction: A Statistical Approach
Venue: arXiv cs.SE 2019
Year: 2019

Modern software development relies heavily on Application Programming Interface (API) libraries. However, there are often certain constraints on using API elements in such libraries. Failing to follow such constraints (API misuse) could lead to serious programming errors. Many approaches have been proposed to detect API misuses, but they still have low accuracy and cannot repair the detected misuses. In this paper, we propose SAM, a novel approach to detect and repair API misuses automatically. SAM uses statistical models to describe five factors involving in any API method call: related method calls, exceptions, pre-conditions, post-conditions, and values of arguments. These statistical models are trained from a large repository of high-quality production code. Then, given a piece of code, SAM verifies each of its method calls with the trained statistical models. If a factor has a sufficiently low probability, the corresponding call is considered as an API misuse. SAM performs an optimal search for editing operations to apply on the code until it has no API issue.
Recurrent Graph Syntax Encoder for Neural Machine Translation
Venue: arXiv cs.CL 2019
Year: 2019

Syntax-incorporated machine translation models have been proven successful in improving the model's reasoning and meaning preservation ability. In this paper, we propose a simple yet effective graph-structured encoder, the Recurrent Graph Syntax Encoder, dubbed \textbf{RGSE}, which enhances the ability to capture useful syntactic information. The RGSE is done over a standard encoder (recurrent or self-attention encoder), regarding recurrent network units as graph nodes and injects syntactic dependencies as edges, such that RGSE models syntactic dependencies and sequential information (\textit{i.e.}, word order) simultaneously. Our approach achieves considerable improvements over several syntax-aware NMT models in English$\Rightarrow$German and English$\Rightarrow$Czech translation tasks. And RGSE-equipped big model obtains competitive result compared with the state-of-the-art model in WMT14 En-De task. Extensive analysis further verifies that RGSE could benefit long sentence modeling, and produces better translations.
Revisiting Heterogeneous Defect Prediction: How Far Are We?
Venue: arXiv cs.SE 2019
Year: 2019

Until now, researchers have proposed several novel heterogeneous defect prediction HDP methods with promising performance. To the best of our knowledge, whether HDP methods can perform significantly better than unsupervised methods has not yet been thoroughly investigated. In this article, we perform a replication study to have a holistic look in this issue. In particular, we compare state-of-the-art five HDP methods with five unsupervised methods. Final results surprisingly show that these HDP methods do not perform significantly better than some of unsupervised methods (especially the simple unsupervised methods proposed by Zhou et al.) in terms of two non-effort-aware performance measures and four effort-aware performance measures. Then, we perform diversity analysis on defective modules via McNemar's test and find the prediction diversity is more obvious when the comparison is performed between the HDP methods and the unsupervised methods than the comparisons only between the HDP methods or between the unsupervised methods. This shows the HDP methods and the unsupervised methods are complementary to each other in identifying defective models to some extent. Finally, we investigate the feasibility of five HDP methods by considering two satisfactory criteria recommended by previous CPDP studies and find the satisfactory ratio of these HDP methods is still pessimistic. The above empirical results implicate there is still a long way for heterogeneous defect prediction to go. More effective HDP methods need to be designed and the unsupervised methods should be considered as baselines.
PolyGAN: High-Order Polynomial Generators
Venue: arXiv cs.LG 2019
Year: 2019

Generative Adversarial Networks (GANs) have become the gold standard when it comes to learning generative models for high-dimensional distributions. Since their advent, numerous variations of GANs have been introduced in the literature, primarily focusing on utilization of novel loss functions, optimization/regularization strategies and network architectures. In this paper, we turn our attention to the generator and investigate the use of high-order polynomials as an alternative class of universal function approximators. Concretely, we propose PolyGAN, where we model the data generator by means of a high-order polynomial whose unknown parameters are naturally represented by high-order tensors. We introduce two tensor decompositions that significantly reduce the number of parameters and show how they can be efficiently implemented by hierarchical neural networks that only employ linear/convolutional blocks. We exhibit for the first time that by using our approach a GAN generator can approximate the data distribution without using any activation functions. Thorough experimental evaluation on both synthetic and real data (images and 3D point clouds) demonstrates the merits of PolyGAN against the state of the art.
Audio query-based music source separation
Venue: arXiv cs.SD 2019
Year: 2019

In recent years, music source separation has been one of the most intensively studied research areas in music information retrieval. Improvements in deep learning lead to a big progress in music source separation performance. However, most of the previous studies are restricted to separating a few limited number of sources, such as vocals, drums, bass, and other. In this study, we propose a network for audio query-based music source separation that can explicitly encode the source information from a query signal regardless of the number and/or kind of target signals. The proposed method consists of a Query-net and a Separator: given a query and a mixture, the Query-net encodes the query into the latent space, and the Separator estimates masks conditioned by the latent vector, which is then applied to the mixture for separation. The Separator can also generate masks using the latent vector from the training samples, allowing separation in the absence of a query. We evaluate our method on the MUSDB18 dataset, and experimental results show that the proposed method can separate multiple sources with a single network. In addition, through further investigation of the latent space we demonstrate that our method can generate continuous outputs via latent vector interpolation.
Mitigating Multi-Stage Cascading Failure by Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

This paper proposes a cascading failure mitigation strategy based on Reinforcement Learning (RL) method. Firstly, the principles of RL are introduced. Then, the Multi-Stage Cascading Failure (MSCF) problem is presented and its challenges are investigated. The problem is then tackled by the RL based on DC-OPF (Optimal Power Flow). Designs of the key elements of the RL framework (rewards, states, etc.) are also discussed in detail. Experiments on the IEEE 118-bus system by both shallow and deep neural networks demonstrate promising results in terms of reduced system collapse rates.
Video synthesis of human upper body with realistic face
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents a generative adversarial learning-based human upper body video synthesis approach to generate an upper body video of target person that is consistent with the body motion, face expression, and pose of the person in source video. We use upper body keypoints, facial action units and poses as intermediate representations between source video and target video. Instead of directly transferring the source video to the target video, we firstly map the source person's facial action units and poses into the target person's facial landmarks, then combine the normalized upper body keypoints and generated facial landmarks with spatio-temporal smoothing to generate the corresponding target video's image. Experimental results demonstrated the effectiveness of our method.
Deep neural network or dermatologist?
Venue: arXiv cs.LG 2019
Year: 2019

Deep learning techniques have proven high accuracy for identifying melanoma in digitised dermoscopic images. A strength is that these methods are not constrained by features that are pre-defined by human semantics. A down-side is that it is difficult to understand the rationale of the model predictions and to identify potential failure modes. This is a major barrier to adoption of deep learning in clinical practice. In this paper we ask if two existing local interpretability methods, Grad-CAM and Kernel SHAP, can shed light on convolutional neural networks trained in the context of melanoma detection. Our contributions are (i) we first explore the domain space via a reproducible, end-to-end learning framework that creates a suite of 30 models, all trained on a publicly available data set (HAM10000), (ii) we next explore the reliability of GradCAM and Kernel SHAP in this context via some basic sanity check experiments (iii) finally, we investigate a random selection of models from our suite using GradCAM and Kernel SHAP. We show that despite high accuracy, the models will occasionally assign importance to features that are not relevant to the diagnostic task. We also show that models of similar accuracy will produce different explanations as measured by these methods. This work represents first steps in bridging the gap between model accuracy and interpretability in the domain of skin cancer classification.
Cache Subsidies for an Optimal Memory for Bandwidth Tradeoff in the Access Network
Venue: arXiv cs.NI 2019
Year: 2019

While the cost of the access network could be considerably reduced by the use of caching, this is not currently happening because content providers (CPs), who alone have the detailed demand data required for optimal content placement, have no natural incentive to use them to minimize access network operator (ANO) expenditure. We argue that ANOs should therefore provide such an incentive in the form of direct subsidies paid to the CPs in proportion to the realized savings. We apply coalition game theory to design the required subsidy framework and propose a distributed algorithm, based on Lagrangian decomposition, allowing ANOs and CPs to collectively realize the optimal memory for bandwidth tradeoff. The considered access network is a cache hierarchy with per-CP central office caches, accessed by all ANOs, at the apex, and per-ANO dedicated bandwidth and storage resources at the lower levels, including wireless base stations, that must be shared by multiple CPs.
Deep Weisfeiler-Lehman Assignment Kernels via Multiple Kernel Learning
Venue: arXiv cs.LG 2019
Year: 2019

Kernels for structured data are commonly obtained by decomposing objects into their parts and adding up the similarities between all pairs of parts measured by a base kernel. Assignment kernels are based on an optimal bijection between the parts and have proven to be an effective alternative to the established convolution kernels. We explore how the base kernel can be learned as part of the classification problem. We build on the theory of valid assignment kernels derived from hierarchies defined on the parts. We show that the weights of this hierarchy can be optimized via multiple kernel learning. We apply this result to learn vertex similarities for the Weisfeiler-Lehman optimal assignment kernel for graph classification. We present first experimental results which demonstrate the feasibility and effectiveness of the approach.
C-RPNs: Promoting Object Detection in real world via a Cascade Structure of Region Proposal Networks
Venue: arXiv cs.CV 2019
Year: 2019

Recently, significant progresses have been made in object detection on common benchmarks (i.e., Pascal VOC). However, object detection in real world is still challenging due to the serious data imbalance. Images in real world are dominated by easy samples like the wide range of background and some easily recognizable objects, for example. Although two-stage detectors like Faster R-CNN achieved big successes in object detection due to the strategy of extracting region proposals by region proposal network, they show their poor adaption in real-world object detection as a result of without considering mining hard samples during extracting region proposals. To address this issue, we propose a Cascade framework of Region Proposal Networks, referred to as C-RPNs. The essence of C-RPNs is adopting multiple stages to mine hard samples while extracting region proposals and learn stronger classifiers. Meanwhile, a feature chain and a score chain are proposed to help learning more discriminative representations for proposals. Moreover, a loss function of cascade stages is designed to train cascade classifiers through backpropagation. Our proposed method has been evaluated on Pascal VOC and several challenging datasets like BSBDV 2017, CityPersons, etc. Our method achieves competitive results compared with the current state-of-the-arts and all-sided improvements in error analysis, validating its efficacy for detection in real world.
In defense of OSVOS
Venue: arXiv cs.CV 2019
Year: 2019

As a milestone for video object segmentation, one-shot video object segmentation (OSVOS) has achieved a large margin compared to the conventional optical-flow based methods regarding to the segmentation accuracy. Its excellent performance mainly benefit from the three-step training mechanism, that are: (1) acquiring object features on the base dataset (i.e. ImageNet), (2) training the parent network on the training set of the target dataset (i.e. DAVIS-2016) to be capable of differentiating the object of interest from the background. (3) online fine-tuning the interested object on the first frame of the target test set to overfit its appearance, then the model can be utilized to segment the same object in the rest frames of that video. In this paper, we argue that for the step (2), OSVOS has the limitation to 'overemphasize' the generic semantic object information while 'dilute' the instance cues of the object(s), which largely block the whole training process. Through adding a common module, video loss, which we formulate with various forms of constraints (including weighted BCE loss, high-dimensional triplet loss, as well as a novel mixed instance-aware video loss), to train the parent network in the step (2), the network is then better prepared for the step (3), i.e. online fine-tuning on the target instance. Through extensive experiments using different network structures as the backbone, we show that the proposed video loss module can improve the segmentation performance significantly, compared to that of OSVOS. Meanwhile, since video loss is a common module, it can be generalized to other fine-tuning based methods and similar vision tasks such as depth estimation and saliency detection.
Robust and Efficient Fuzzy C-Means Clustering Constrained on Flexible Sparsity
Venue: arXiv cs.LG 2019
Year: 2019

Clustering is an effective technique in data mining to group a set of objects in terms of some attributes. Among various clustering approaches, the family of K-Means algorithms gains popularity due to simplicity and efficiency. However, most of existing K-Means based clustering algorithms cannot deal with outliers well and are difficult to efficiently solve the problem embedded the $L_0$-norm constraint. To address the above issues and improve the performance of clustering significantly, we propose a novel clustering algorithm, named REFCMFS, which develops a $L_{2,1}$-norm robust loss as the data-driven item and imposes a $L_0$-norm constraint on the membership matrix to make the model more robust and sparse flexibly. In particular, REFCMFS designs a new way to simplify and solve the $L_0$-norm constraint without any approximate transformation by absorbing $\|\cdot\|_0$ into the objective function through a ranking function. These improvements not only make REFCMFS efficiently obtain more promising performance but also provide a new tractable and skillful optimization method to solve the problem embedded the $L_0$-norm constraint. Theoretical analyses and extensive experiments on several public datasets demonstrate the effectiveness and rationality of our proposed REFCMFS method.
Adabot: Fault-Tolerant Java Decompiler
Venue: arXiv cs.SE 2019
Year: 2019

Reverse Engineering(RE) has been a fundamental task in software engineering. However, most of the traditional Java reverse engineering tools are strictly rule defined, thus are not fault-tolerant, which pose serious problem when noise and interference were introduced into the system. In this paper, we view reverse engineering as a statistical machine translation task instead of rule-based task, and propose a fault-tolerant Java decompiler based on machine translation models. Our model is based on attention-based Neural Machine Translation (NMT) and Transformer architectures. First, we measure the translation quality on both the redundant and purified datasets. Next, we evaluate the fault-tolerance(anti-noise ability) of our framework on test sets with different unit error probability (UEP). In addition, we compare the suitability of different word segmentation algorithms for decompilation task. Experimental results demonstrate that our model is more robust and fault-tolerant compared to traditional Abstract Syntax Tree (AST) based decompilers. Specifically, in terms of BLEU-4 and Word Error Rate (WER), our performance has reached 94.50% and 2.65% on the redundant test set; 92.30% and 3.48% on the purified test set.
Towards Efficient Discriminative Pattern Mining in Hybrid Domains
Venue: arXiv cs.DB 2019
Year: 2019

Discriminative pattern mining is a data mining task in which we find patterns that distinguish transactions in the class of interest from those in other classes, and is also called emerging pattern mining or subgroup discovery. One practical problem in discriminative pattern mining is how to handle numeric values in the input dataset. In this paper, we propose an algorithm for discriminative pattern mining that can deal with a transactional dataset in a hybrid domain, i.e. the one that includes both symbolic and numeric values. We also show the execution results of a prototype implementation of the proposed algorithm for two standard benchmark datasets.
A New Fast Unweighted All-pairs Shortest Path Search Algorithm Based on Pruning by Shortest Path Trees
Venue: arXiv cs.DS 2019
Year: 2019

We present a new fast all-pairs shortest path algorithm for unweighted graphs. In breadth-first search which is said to representative and fast in unweighted graphs, the average number of accesses to adjacent vertices (expressed by α) is about equal to the average degree of the graph. On the other hand, our algorithm utilizes the shortest path trees of adjacent vertices of each source vertex, and reduce α drastically. Roughly speaking α is reduced to the value close to 1, because the average degree of a tree is about 2, and one is used to come in and the other is used to go out, although that does not hold true when the depth of the shortest path trees is small. We compared our algorithm with breadth-first search algorithm, and our results showed that ours outperforms breadth-first search on speed and α.
The Strengths and Behavioral Quirks of Java Bytecode Decompilers
Venue: arXiv cs.SE 2019
Year: 2019

During compilation from Java source code to bytecode, some information is irreversibly lost. In other words, compilation and decompilation of Java code is not symmetric. Consequently, the decompilation process, which aims at producing source code from bytecode, must establish some strategies to reconstruct the information that has been lost. Modern Java decompilers tend to use distinct strategies to achieve proper decompilation. In this work, we hypothesize that the diverse ways in which bytecode can be decompiled has a direct impact on the quality of the source code produced by decompilers. We study the effectiveness of eight Java decompilers with respect to three quality indicators: syntactic correctness, syntactic distortion and semantic equivalence modulo inputs. This study relies on a benchmark set of 14 real-world open-source software projects to be decompiled (2041 classes in total). Our results show that no single modern decompiler is able to correctly handle the variety of bytecode structures coming from real-world programs. Even the highest ranking decompiler in this study produces syntactically correct output for 84% of classes of our dataset and semantically equivalent code output for 78% of classes.