OpenRaiser/Intern-Atlas huggingface dataset:
Path homology as a stronger analogue of cyclomatic complexity
Venue: arXiv cs.SE 2020
Year: 2020

Cyclomatic complexity is an incompletely specified but mathematically principled software metric that can be usefully applied to both source and binary code. We consider the application of path homology as a stronger analogue of cyclomatic complexity. We have implemented an algorithm to compute path homology in arbitrary dimension and applied it to several classes of relevant flow graphs, including randomly generated flow graphs representing structured and unstructured control flow. We also compared path homology and cyclomatic complexity on a set of disassembled binaries obtained from the grep utility. There exist control flow graphs realizable at the assembly level with nontrivial path homology in arbitrary dimension. We exhibit several classes of examples in this vein while also experimentally demonstrating that path homology gives identicial results to cyclomatic complexity for at least one detailed notion of structured control flow. We also experimentally demonstrate that the two notions differ on disassembled binaries, and we highlight an example of extreme disagreement. Path homology empirically generalizes cyclomatic complexity for an elementary notion of structured code and appears to identify more structurally relevant features of control flow in general. Path homology therefore has the potential to substantially improve upon cyclomatic complexity.
Evaluating Temporal Queries Over Video Feeds
Venue: arXiv cs.DB 2020
Year: 2020

Recent advances in Computer Vision and Deep Learning made possible the efficient extraction of a schema from frames of streaming video. As such, a stream of objects and their associated classes along with unique object identifiers derived via object tracking can be generated, providing unique objects as they are captured across frames. In this paper we initiate a study of temporal queries involving objects and their co-occurrences in video feeds. For example, queries that identify video segments during which the same two red cars and the same two humans appear jointly for five minutes are of interest to many applications ranging from law enforcement to security and safety. We take the first step and define such queries in a way that they incorporate certain physical aspects of video capture such as object occlusion. We present an architecture consisting of three layers, namely object detection/tracking, intermediate data generation and query evaluation. We propose two techniques,MFS and SSG, to organize all detected objects in the intermediate data generation layer, which effectively, given the queries, minimizes the number of objects and frames that have to be considered during query evaluation. We also introduce an algorithm called State Traversal (ST) that processes incoming frames against the SSG and efficiently prunes objects and frames unrelated to query evaluation, while maintaining all states required for succinct query evaluation. We present the results of a thorough experimental evaluation utilizing both real and synthetic data establishing the trade-offs between MFS and SSG. We stress various parameters of interest in our evaluation and demonstrate that the proposed query evaluation methodology coupled with the proposed algorithms is capable to evaluate temporal queries over video feeds efficiently, achieving orders of magnitude performance benefits.
Graphing Website Relationships for Risk Prediction: Identifying Derived Threats to Users Based on Known Indicators
Venue: arXiv cs.CR 2020
Year: 2020

The hypothesis for the study was that the relationship based on referrer links and the number of hops to a malicious site could indicate the risk to another website. We chose Receiver Operating Characteristics (ROC) analysis as the method of comparing true positive and false positive rates for captured web traffic to test the predictive capabilities of our model. Known threat indicators were used as designators, and the Neo4j graph database was leveraged to map the relationships between other websites based on referring links. Using the referring traffic, we mapped user visits across websites with a known relationship to track the rate at which users progressed from a non-malicious website to a known threat. The results were grouped by the hop distance from the known threat to calculate the predictive rate. The results of the model produced true positive rates between 58.59% and 63.45% and false positive rates between 7.42% to 37.50%, respectively. The true and false positive rates suggest an improved performance based on the closer proximity from the known threat, while an increased referring distance from the threat resulted in higher rates of false positives.
Learning from Positive and Unlabeled Data by Identifying the Annotation Process
Venue: arXiv cs.LG 2020
Year: 2020

In binary classification, Learning from Positive and Unlabeled data (LePU) is semi-supervised learning but with labeled elements from only one class. Most of the research on LePU relies on some form of independence between the selection process of annotated examples and the features of the annotated class, known as the Selected Completely At Random (SCAR) assumption. Yet the annotation process is an important part of the data collection, and in many cases it naturally depends on certain features of the data (e.g., the intensity of an image and the size of the object to be detected in the image). Without any constraints on the model for the annotation process, classification results in the LePU problem will be highly non-unique. So proper, flexible constraints are needed. In this work we incorporate more flexible and realistic models for the annotation process than SCAR, and more importantly, offer a solution for the challenging LePU problem. On the theory side, we establish the identifiability of the properties of the annotation process and the classification function, in light of the considered constraints on the data-generating process. We also propose an inference algorithm to learn the parameters of the model, with successful experimental results on both simulated and real data. We also propose a novel real-world dataset forLePU, as a benchmark dataset for future studies.
Unsupervised Domain Adaptation for Mammogram Image Classification: A Promising Tool for Model Generalization
Venue: arXiv cs.CV 2020
Year: 2020

Generalization is one of the key challenges in the clinical validation and application of deep learning models to medical images. Studies have shown that such models trained on publicly available datasets often do not work well on real-world clinical data due to the differences in patient population and image device configurations. Also, manually annotating clinical images is expensive. In this work, we propose an unsupervised domain adaptation (UDA) method using Cycle-GAN to improve the generalization ability of the model without using any additional manual annotations.
Selectivity considered harmful: evaluating the causal impact of class selectivity in DNNs
Venue: arXiv cs.LG 2020
Year: 2020

The properties of individual neurons are often analyzed in order to understand the biological and artificial neural networks in which they're embedded. Class selectivity-typically defined as how different a neuron's responses are across different classes of stimuli or data samples-is commonly used for this purpose. However, it remains an open question whether it is necessary and/or sufficient for deep neural networks (DNNs) to learn class selectivity in individual units. We investigated the causal impact of class selectivity on network function by directly regularizing for or against class selectivity. Using this regularizer to reduce class selectivity across units in convolutional neural networks increased test accuracy by over 2% for ResNet18 trained on Tiny ImageNet. For ResNet20 trained on CIFAR10 we could reduce class selectivity by a factor of 2.5 with no impact on test accuracy, and reduce it nearly to zero with only a small ($\sim$2%) drop in test accuracy. In contrast, regularizing to increase class selectivity significantly decreased test accuracy across all models and datasets. These results indicate that class selectivity in individual units is neither sufficient nor strictly necessary, and can even impair DNN performance. They also encourage caution when focusing on the properties of single units as representative of the mechanisms by which DNNs function.
Intelligent Base Station Association for UAV Cellular Users: A Supervised Learning Approach
Venue: arXiv cs.IT 2020
Year: 2020

Fifth Generation (5G) cellular networks are expected to provide cellular connectivity for vehicular users, including Unmanned Aerial Vehicles (UAVs). When flying in the air, these users experience strong, unobstructed channel conditions to a large number of Base Stations (BSs) on the ground. This creates very strong interference conditions for the UAV users, while at the same time offering them a large number of BSs to potentially associate with for cellular service. Therefore, to maximise the performance of the UAV-BS wireless link, the UAV user needs to be able to choose which BSs to connect to, based on the observed environmental conditions. This paper proposes a supervised learning-based association scheme, using which a UAV can intelligently associate with the most appropriate BS. We train a Neural Network (NN) to identify the most suitable BS from several candidate BSs, based on the received signal powers from the BSs, known distances to the BSs, as well as the known locations of potential interferers. We then compare the performance of the NN-based association scheme against strongest-signal and closest-neighbour association schemes, and demonstrate that the NN scheme significantly outperforms the simple heuristic schemes.
Accelerating Generalized Benders Decomposition for Wireless Resource Allocation
Venue: arXiv cs.IT 2020
Year: 2020

Generalized Benders decomposition (GBD) is a globally optimal algorithm for mixed integer nonlinear programming (MINLP) problems, which are NP-hard and can be widely found in the area of wireless resource allocation. The main idea of GBD is decomposing an MINLP problem into a primal problem and a master problem, which are iteratively solved until their solutions converge. However, a direct implementation of GBD is time- and memory-consuming. The main bottleneck is the high complexity of the master problem, which increases over the iterations. Therefore, we propose to leverage machine learning (ML) techniques to accelerate GBD aiming at decreasing the complexity of the master problem. Specifically, we utilize two different ML techniques, classification and regression, to deal with this acceleration task. In this way, a cut classifier and a cut regressor are learned, respectively, to distinguish between useful and useless cuts. Only useful cuts are added to the master problem and thus the complexity of the master problem is reduced. By using a resource allocation problem in device-to-device communication networks as an example, we validate that the proposed method can reduce the computational complexity of GBD without loss of optimality and has strong generalization ability. The proposed method is applicable for solving various MINLP problems in wireless networks since the designs are invariant for different problems.
Regression via Implicit Models and Optimal Transport Cost Minimization
Venue: arXiv cs.LG 2020
Year: 2020

This paper addresses the classic problem of regression, which involves the inductive learning of a map, $y=f(x,z)$, $z$ denoting noise, $f:\mathbb{R}^n\times \mathbb{R}^k \rightarrow \mathbb{R}^m$. Recently, Conditional GAN (CGAN) has been applied for regression and has shown to be advantageous over the other standard approaches like Gaussian Process Regression, given its ability to implicitly model complex noise forms. However, the current CGAN implementation for regression uses the classical generator-discriminator architecture with the minimax optimization approach, which is notorious for being difficult to train due to issues like training instability or failure to converge. In this paper, we take another step towards regression models that implicitly model the noise, and propose a solution which directly optimizes the optimal transport cost between the true probability distribution $p(y|x)$ and the estimated distribution $\hat{p}(y|x)$ and does not suffer from the issues associated with the minimax approach. On a variety of synthetic and real-world datasets, our proposed solution achieves state-of-the-art results. The code accompanying this paper is available at "https://github.com/gurdaspuriya/ot_regression".
Transfer Learning for Context-Aware Spoken Language Understanding
Venue: arXiv cs.CL 2020
Year: 2020

Spoken language understanding (SLU) is a key component of task-oriented dialogue systems. SLU parses natural language user utterances into semantic frames. Previous work has shown that incorporating context information significantly improves SLU performance for multi-turn dialogues. However, collecting a large-scale human-labeled multi-turn dialogue corpus for the target domains is complex and costly. To reduce dependency on the collection and annotation effort, we propose a Context Encoding Language Transformer (CELT) model facilitating exploiting various context information for SLU. We explore different transfer learning approaches to reduce dependency on data collection and annotation. In addition to unsupervised pre-training using large-scale general purpose unlabeled corpora, such as Wikipedia, we explore unsupervised and supervised adaptive training approaches for transfer learning to benefit from other in-domain and out-of-domain dialogue corpora. Experimental results demonstrate that the proposed model with the proposed transfer learning approaches achieves significant improvement on the SLU performance over state-of-the-art models on two large-scale single-turn dialogue benchmarks and one large-scale multi-turn dialogue benchmark.
Adaptive Federated Learning With Gradient Compression in Uplink NOMA
Venue: arXiv cs.NI 2020
Year: 2020

Federated learning (FL) is an emerging machine learning technique that aggregates model attributes from a large number of distributed devices. Several unique features such as energy saving and privacy preserving make FL a highly promising learning approach for power-limited and privacy sensitive devices. Although distributed computing can lower down the information amount that needs to be uploaded, model updates in FL can still experience performance bottleneck, especially for updates via wireless connections. In this work, we investigate the performance of FL update with mobile edge devices that are connected to the parameter server (PS) with practical wireless links, where uplink update from user to PS has very limited capacity. Different from the existing works, we apply non-orthogonal multiple access (NOMA) together with gradient compression in the wireless uplink. Simulation results show that our proposed scheme can significantly reduce aggregation latency while achieving similar accuracy.
DETECT: Deep Trajectory Clustering for Mobility-Behavior Analysis
Venue: arXiv cs.LG 2020
Year: 2020

Identifying mobility behaviors in rich trajectory data is of great economic and social interest to various applications including urban planning, marketing and intelligence. Existing work on trajectory clustering often relies on similarity measurements that utilize raw spatial and/or temporal information of trajectories. These measures are incapable of identifying similar moving behaviors that exhibit varying spatio-temporal scales of movement. In addition, the expense of labeling massive trajectory data is a barrier to supervised learning models. To address these challenges, we propose an unsupervised neural approach for mobility behavior clustering, called the Deep Embedded TrajEctory ClusTering network (DETECT). DETECT operates in three parts: first it transforms the trajectories by summarizing their critical parts and augmenting them with context derived from their geographical locality (e.g., using POIs from gazetteers). In the second part, it learns a powerful representation of trajectories in the latent space of behaviors, thus enabling a clustering function (such as $k$-means) to be applied. Finally, a clustering oriented loss is directly built on the embedded features to jointly perform feature refinement and cluster assignment, thus improving separability between mobility behaviors. Exhaustive quantitative and qualitative experiments on two real-world datasets demonstrate the effectiveness of our approach for mobility behavior analyses.
Improving the performance of heterogeneous data centers through redundancy
Venue: arXiv cs.NI 2020
Year: 2020

We analyze the performance of redundancy in a multi-type job and multi-type server system. We assume the job dispatcher is unaware of the servers' capacities, and we set out to study under which circumstances redundancy improves the performance. With redundancy an arriving job dispatches redundant copies to all its compatible servers, and departs as soon as one of its copies completes service. As a benchmark comparison, we take the non-redundant system in which a job arrival is routed to only one randomly selected compatible server. Service times are generally distributed and all copies of a job are identical, i.e., have the same service requirement. In our first main result, we characterize the sufficient and necessary stability conditions of the redundancy system. This condition coincides with that of a system where each job type only dispatches copies into its least-loaded servers, and those copies need to be fully served. In our second result, we compare the stability regions of the system under redundancy to that of no redundancy. We show that if the server's capacities are sufficiently heterogeneous, the stability region under redundancy can be much larger than that without redundancy. We apply the general solution to particular classes of systems, including redundancy-d and nested models, to derive simple conditions on the degree of heterogeneity required for redundancy to improve the stability. As such, our result is the first in showing that redundancy can improve the stability and hence performance of a system when copies are non-i.i.d..
CRATOS: Cognition of Reliable Algorithm for Time-series Optimal Solution
Venue: arXiv cs.LG 2020
Year: 2020

Anomaly detection of time series plays an important role in reliability systems engineering. However, in practical application, there is no precisely defined boundary between normal and anomalous behaviors in different application scenarios. Therefore, different anomaly detection algorithms and processes ought to be adopted for time series in different situation. Although such strategy improve the accuracy of anomaly detection, it takes a lot of time for practitioners to configure various algorithms to millions of series, which greatly increases the development and maintenance cost of anomaly detection processes. In this paper, we propose CRATOS which is a self-adapt algorithms that extract features from time series, and then cluster series with similar features into one group. For each group we utilize evolutionary algorithm to search the best anomaly detection methods and processes. Our methods can significantly reduce the cost of development and maintenance of anomaly detection. According to experiments, our clustering methods achieves the state-of-art results. The accuracy of the anomaly detection algorithms in this paper is 85.1%.
Understanding the Prediction Mechanism of Sentiments by XAI Visualization
Venue: arXiv cs.HC 2020
Year: 2020

People often rely on online reviews to make purchase decisions. The present work aimed to gain an understanding of a machine learning model's prediction mechanism by visualizing the effect of sentiments extracted from online hotel reviews with explainable AI (XAI) methodology. Study 1 used the extracted sentiments as features to predict the review ratings by five machine learning algorithms (knn, CART decision trees, support vector machines, random forests, gradient boosting machines) and identified random forests as best algorithm. Study 2 analyzed the random forests model by feature importance and revealed the sentiments joy, disgust, positive and negative as the most predictive features. Furthermore, the visualization of additive variable attributions and their prediction distribution showed correct prediction in direction and effect size for the 5-star rating but partially wrong direction and insufficient effect size for the 1-star rating. These prediction details were corroborated by a what-if analysis for the four top features. In conclusion, the prediction mechanism of a machine learning model can be uncovered by visualization of particular observations. Comparing instances of contrasting ground truth values can draw a differential picture of the prediction mechanism and inform decisions for model improvement.
XGPT: Cross-modal Generative Pre-Training for Image Captioning
Venue: arXiv cs.CL 2020
Year: 2020

While many BERT-based cross-modal pre-trained models produce excellent results on downstream understanding tasks like image-text retrieval and VQA, they cannot be applied to generation tasks directly. In this paper, we propose XGPT, a new method of Cross-modal Generative Pre-Training for Image Captioning that is designed to pre-train text-to-image caption generators through three novel generation tasks, including Image-conditioned Masked Language Modeling (IMLM), Image-conditioned Denoising Autoencoding (IDA), and Text-conditioned Image Feature Generation (TIFG). As a result, the pre-trained XGPT can be fine-tuned without any task-specific architecture modifications to create state-of-the-art models for image captioning. Experiments show that XGPT obtains new state-of-the-art results on the benchmark datasets, including COCO Captions and Flickr30k Captions. We also use XGPT to generate new image captions as data augmentation for the image retrieval task and achieve significant improvement on all recall metrics.
Modeling and Selection of Interdependent Software Requirements using Fuzzy Graphs
Venue: arXiv cs.SE 2020
Year: 2020

Software requirement selection is to find an optimal set of requirements that gives the highest value for a release of software while keeping the cost within the budget. However, value-related dependencies among software requirements may impact the value of an optimal set. Moreover, value-related dependencies can be of varying strengths. Hence, it is important to consider both the existence and the strengths of value-related dependencies during a requirement selection. The existing selection models however, either assume that software requirements are independent or they ignore strengths of requirement dependencies. This paper presents a cost-value optimization model that considers the impacts of value-related requirement dependencies on the value of selected requirements (optimal set). We have exploited algebraic structure of fuzzy graphs for modeling value-related requirement dependencies and their strengths. Validity and practicality of the work are verified through carrying out several simulations and studying a real world software project.