OpenRaiser/Intern-Atlas huggingface dataset:
Approximate Knowledge Graph Query Answering: From Ranking to Binary Classification
Venue: arXiv cs.DB 2021
Year: 2021

Large, heterogeneous datasets are characterized by missing or even erroneous information. This is more evident when they are the product of community effort or automatic fact extraction methods from external sources, such as text. A special case of the aforementioned phenomenon can be seen in knowledge graphs, where this mostly appears in the form of missing or incorrect edges and nodes. Structured querying on such incomplete graphs will result in incomplete sets of answers, even if the correct entities exist in the graph, since one or more edges needed to match the pattern are missing. To overcome this problem, several algorithms for approximate structured query answering have been proposed. Inspired by modern Information Retrieval metrics, these algorithms produce a ranking of all entities in the graph, and their performance is further evaluated based on how high in this ranking the correct answers appear. In this work we take a critical look at this way of evaluation. We argue that performing a ranking-based evaluation is not sufficient to assess methods for complex query answering. To solve this, we introduce Message Passing Query Boxes (MPQB), which takes binary classification metrics back into use and shows the effect this has on the recently proposed query embedding method MPQE.
Reinforcement Learning of Beam Codebooks in Millimeter Wave and Terahertz MIMO Systems
Venue: arXiv cs.IT 2021
Year: 2021

Millimeter wave (mmWave) and terahertz MIMO systems rely on pre-defined beamforming codebooks for both initial access and data transmission. Being pre-defined, however, these codebooks are commonly not optimized for specific environments, user distributions, and/or possible hardware impairments. This leads to large codebook sizes with high beam training overhead which increases the initial access/tracking latency and makes it hard for these systems to support highly mobile applications. To overcome these limitations, this paper develops a deep reinforcement learning framework that learns how to iteratively optimize the codebook beam patterns (shapes) relying only on the receive power measurements and without requiring any explicit channel knowledge. The developed model learns how to autonomously adapt the beam patterns to best match the surrounding environment, user distribution, hardware impairments, and array geometry. Further, this approach does not require any knowledge about the channel, array geometry, RF hardware, or user positions. To reduce the learning time, the proposed model designs a novel Wolpertinger-variant architecture that is capable of efficiently searching for an optimal policy in a large discrete action space, which is important for large antenna arrays with quantized phase shifters. This complex-valued neural network architecture design respects the practical RF hardware constraints such as the constant-modulus and quantized phase shifter constraints. Simulation results based on the publicly available DeepMIMO dataset confirm the ability of the developed framework to learn near-optimal beam patterns for both line-of-sight (LOS) and non-LOS scenarios and for arrays with hardware impairments without requiring any channel knowledge.
Optimal Prediction Intervals for Macroeconomic Time Series Using Chaos and NSGA II
Venue: arXiv cs.NE 2021
Year: 2021

In a first-of-its-kind study, this paper proposes the formulation of constructing prediction intervals (PIs) in a time series as a bi-objective optimization problem and solves it with the help of Nondominated Sorting Genetic Algorithm (NSGA-II). We also proposed modeling the chaos present in the time series as a preprocessor in order to model the deterministic uncertainty present in the time series. Even though the proposed models are general in purpose, they are used here for quantifying the uncertainty in macroeconomic time series forecasting. Ideal PIs should be as narrow as possible while capturing most of the data points. Based on these two objectives, we formulated a bi-objective optimization problem to generate PIs in 2-stages, wherein reconstructing the phase space using Chaos theory (stage-1) is followed by generating optimal point prediction using NSGA-II and these point predictions are in turn used to obtain PIs (stage-2). We also proposed a 3-stage hybrid, wherein the 3rd stage invokes NSGA-II too in order to solve the problem of constructing PIs from the point prediction obtained in 2nd stage. The proposed models when applied to the macroeconomic time series, yielded better results in terms of both prediction interval coverage probability (PICP) and prediction interval average width (PIAW) compared to the state-of-the-art Lower Upper Bound Estimation Method (LUBE) with Gradient Descent (GD). The 3-stage model yielded better PICP compared to the 2-stage model but showed similar performance in PIAW with added computation cost of running NSGA-II second time.
MUSBO: Model-based Uncertainty Regularized and Sample Efficient Batch Optimization for Deployment Constrained Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

In many contemporary applications such as healthcare, finance, robotics, and recommendation systems, continuous deployment of new policies for data collection and online learning is either cost ineffective or impractical. We consider a setting that lies between pure offline reinforcement learning (RL) and pure online RL called deployment constrained RL in which the number of policy deployments for data sampling is limited. To solve this challenging task, we propose a new algorithmic learning framework called Model-based Uncertainty regularized and Sample Efficient Batch Optimization (MUSBO). Our framework discovers novel and high quality samples for each deployment to enable efficient data collection. During each offline training session, we bootstrap the policy update by quantifying the amount of uncertainty within our collected data. In the high support region (low uncertainty), we encourage our policy by taking an aggressive update. In the low support region (high uncertainty) when the policy bootstraps into the out-of-distribution region, we downweight it by our estimated uncertainty quantification. Experimental results show that MUSBO achieves state-of-the-art performance in the deployment constrained RL setting.
Structural Similarity of Boundary Conditions and an Efficient Local Search Algorithm for Goal Conflict Identification
Venue: arXiv cs.SE 2021
Year: 2021

In goal-oriented requirements engineering, goal conflict identification is of fundamental importance for requirements analysis. The task aims to find the feasible situations which make the goals diverge within the domain, called boundary conditions (BCs). However, the existing approaches for goal conflict identification fail to find sufficient BCs and general BCs which cover more combinations of circumstances. From the BCs found by these existing approaches, we have observed an interesting phenomenon that there are some pairs of BCs are similar in formula structure, which occurs frequently in the experimental cases. In other words, once a BC is found, a new BC may be discovered quickly by slightly changing the former. It inspires us to develop a local search algorithm named LOGION to find BCs, in which the structural similarity is captured by the neighborhood relation of formulae. Based on structural similarity, LOGION can find a lot of BCs in a short time. Moreover, due to the large number of BCs identified, it potentially selects more general BCs from them. By taking experiments on a set of cases, we show that LOGION effectively exploits the structural similarity of BCs. We also compare our algorithm against the two state-of-the-art approaches. The experimental results show that LOGION produces one order of magnitude more BCs than the state-of-the-art approaches and confirm that LOGION finds out more general BCs thanks to a large number of BCs.
V2W-BERT: A Framework for Effective Hierarchical Multiclass Classification of Software Vulnerabilities
Venue: arXiv cs.LG 2021
Year: 2021

Weaknesses in computer systems such as faults, bugs and errors in the architecture, design or implementation of software provide vulnerabilities that can be exploited by attackers to compromise the security of a system. Common Weakness Enumerations (CWE) are a hierarchically designed dictionary of software weaknesses that provide a means to understand software flaws, potential impact of their exploitation, and means to mitigate these flaws. Common Vulnerabilities and Exposures (CVE) are brief low-level descriptions that uniquely identify vulnerabilities in a specific product or protocol. Classifying or mapping of CVEs to CWEs provides a means to understand the impact and mitigate the vulnerabilities. Since manual mapping of CVEs is not a viable option, automated approaches are desirable but challenging. We present a novel Transformer-based learning framework (V2W-BERT) in this paper. By using ideas from natural language processing, link prediction and transfer learning, our method outperforms previous approaches not only for CWE instances with abundant data to train, but also rare CWE classes with little or no data to train. Our approach also shows significant improvements in using historical data to predict links for future instances of CVEs, and therefore, provides a viable approach for practical applications. Using data from MITRE and National Vulnerability Database, we achieve up to 97% prediction accuracy for randomly partitioned data and up to 94% prediction accuracy in temporally partitioned data. We believe that our work will influence the design of better methods and training models, as well as applications to solve increasingly harder problems in cybersecurity.
MSR Mining Challenge: The SmartSHARK Repository Mining Data
Venue: arXiv cs.SE 2021
Year: 2021

The SmartSHARK repository mining data is a collection of rich and detailed information about the evolution of software projects. The data is unique in its diversity and contains detailed information about each change, issue tracking data, continuous integration data, as well as pull request and code review data. Moreover, the data does not contain only raw data scraped from repositories, but also annotations in form of labels determined through a combination of manual analysis and heuristics, as well as links between the different parts of the data set. The SmartSHARK data set provides a rich source of data that enables us to explore research questions that require data from different sources and/or longitudinal data over time.
Toward Speeding up Mutation Analysis by Memoizing Expensive Methods
Venue: arXiv cs.SE 2021
Year: 2021

Mutation analysis has many applications, such as assessing the quality of test cases, fault localization, test input generation, security analysis, etc. Such applications involve running test suite against a large number of program mutants leading to poor scalability. Much research has been aimed at speeding up this process, focusing on reducing the number of mutants, the number of executed tests, or the execution time of the mutants. This paper presents a novel approach, named MeMu, for reducing the execution time of the mutants, by memoizing the most expensive methods in the system. Memoization is an optimization technique that allows bypassing the execution of expensive methods, when repeated inputs are detected. MeMu can be used in conjunction with existing acceleration techniques. We implemented MeMu on top of PITest, a well-known JVM bytecode-level mutation analysis system, and obtained, on average, an 18.15% speed-up over PITest, in the execution time of the mutants for 12 real-world programs. These promising results and the fact that MeMu could also be used for other applications that involve repeated execution of tests (e.g., automatic program repair and regression testing), strongly support future research for improving its efficiency.
Robust and Transferable Anomaly Detection in Log Data using Pre-Trained Language Models
Venue: arXiv cs.AI 2021
Year: 2021

Anomalies or failures in large computer systems, such as the cloud, have an impact on a large number of users that communicate, compute, and store information. Therefore, timely and accurate anomaly detection is necessary for reliability, security, safe operation, and mitigation of losses in these increasingly important systems. Recently, the evolution of the software industry opens up several problems that need to be tackled including (1) addressing the software evolution due software upgrades, and (2) solving the cold-start problem, where data from the system of interest is not available. In this paper, we propose a framework for anomaly detection in log data, as a major troubleshooting source of system information. To that end, we utilize pre-trained general-purpose language models to preserve the semantics of log messages and map them into log vector embeddings. The key idea is that these representations for the logs are robust and less invariant to changes in the logs, and therefore, result in a better generalization of the anomaly detection models. We perform several experiments on a cloud dataset evaluating different language models for obtaining numerical log representations such as BERT, GPT-2, and XL. The robustness is evaluated by gradually altering log messages, to simulate a change in semantics. Our results show that the proposed approach achieves high performance and robustness, which opens up possibilities for future research in this direction.
Assessing the Readability of Policy Documents on the Digital Single Market of the European Union
Venue: arXiv cs.CY 2021
Year: 2021

Today, literature skills are necessary. Engineering and other technical professions are not an exception from this requirement. Traditionally, technical reading and writing have been framed with a limited scope, containing documentation, specifications, standards, and related text types. Nowadays, however, the scope covers also other text types, including legal, policy, and related documents. Given this motivation, this paper evaluates the readability of 201 legislations and related policy documents in the European Union (EU). The digital single market (DSM) provides the context. Five classical readability indices provide the methods; these are quantitative measures of a text's readability. The empirical results indicate that (i) generally a Ph.D. level education is required to comprehend the DSM laws and policy documents. Although (ii) the results vary across the five indices used, (iii) readability has slightly improved over time.
Learning to Fairly Classify the Quality of Wireless Links
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning (ML) has been used to develop increasingly accurate link quality estimators for wireless networks. However, more in-depth questions regarding the most suitable class of models, most suitable metrics and model performance on imbalanced datasets remain open. In this paper, we propose a new tree-based link quality classifier that meets high performance and fairly classifies the minority class and, at the same time, incurs low training cost. We compare the tree-based model, to a multilayer perceptron (MLP) non-linear model and two linear models, namely logistic regression (LR) and SVM, on a selected imbalanced dataset and evaluate their results using five different performance metrics. Our study shows that 1) non-linear models perform slightly better than linear models in general, 2) the proposed non-linear tree-based model yields the best performance trade-off considering F1, training time and fairness, 3) single metric aggregated evaluations based only on accuracy can hide poor, unfair performance especially on minority classes, and 4) it is possible to improve the performance on minority classes, by over 40% through feature selection and by over 20% through resampling, therefore leading to fairer classification results.
Design and Integration of a Drone based Passive Manipulator for Capturing Flying Targets
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we present a novel passive single Degree-of-Freedom (DoF) manipulator design and its integration on an autonomous drone to capture a moving target. The end-effector is designed to be passive, to disengage the moving target from a flying UAV and capture it efficiently in the presence of disturbances, with minimal energy usage. It is also designed to handle target sway and the effect of downwash. The passive manipulator is integrated with the drone through a single Degree of Freedom (DoF) arm, and experiments are carried out in an outdoor environment. The rack-and-pinion mechanism incorporated for this manipulator ensures safety by extending the manipulator beyond the body of the drone to capture the target. The autonomous capturing experiments are conducted using a red ball hanging from a stationary drone and subsequently from a moving drone. The experiments show that the manipulator captures the target with a success rate of 70\% even under environmental/measurement uncertainties and errors.
A System for 3D Reconstruction Of Comminuted Tibial Plafond Bone Fractures
Venue: arXiv cs.CV 2021
Year: 2021

High energy impacts at joint locations often generate highly fragmented, or comminuted, bone fractures. Current approaches for treatment require physicians to decide how to classify the fracture within a hierarchy fracture severity categories. Each category then provides a best-practice treatment scenario to obtain the best possible prognosis for the patient. This article identifies shortcomings associated with qualitative-only evaluation of fracture severity and provides new quantitative metrics that serve to address these shortcomings. We propose a system to semi-automatically extract quantitative metrics that are major indicators of fracture severity. These include: (i) fracture surface area, i.e., how much surface area was generated when the bone broke apart, and (ii) dispersion, i.e., how far the fragments have rotated and translated from their original anatomic positions. This article describes new computational tools to extract these metrics by computationally reconstructing 3D bone anatomy from CT images with a focus on tibial plafond fracture cases where difficult qualitative fracture severity cases are more prevalent. Reconstruction is accomplished within a single system that integrates several novel algorithms that identify, extract and piece-together fractured fragments in a virtual environment. Doing so provides objective quantitative measures for these fracture severity indicators. The availability of such measures provides new tools for fracture severity assessment which may lead to improved fracture treatment. This paper describes the system, the underlying algorithms and the metrics of the reconstruction results by quantitatively analyzing six clinical tibial plafond fracture cases.
Inferring temporal dynamics from cross-sectional data using Langevin dynamics
Venue: arXiv cs.CE 2021
Year: 2021

Cross-sectional studies are widely prevalent since they are more feasible to conduct compared to longitudinal studies. However, cross-sectional data lack the temporal information required to study the evolution of the underlying processes. Nevertheless, this is essential to develop predictive computational models which is the first step towards causal modelling. We propose a method for inferring computational models from cross-sectional data using Langevin dynamics. This method can be applied to any system that can be described as effectively following a free energy landscape, such as protein folding, stem cell differentiation and reprogramming, and social systems involving human interaction and social norms. A crucial assumption in our method is that the data-points are gathered from a system in (local) equilibrium. The result is a set of stochastic differential equations which capture the temporal dynamics, by assuming that groups of data-points are subject to the same free energy landscape and amount of noise. Our method is a 'baseline' method which initiates the development of computational models which can be iteratively enhanced through the inclusion of expert knowledge. We validate the proposed method against two population-based longitudinal datasets and observe significant predictive power in comparison with random choice algorithms. We also show how the predictive power of our 'baseline' model can be enhanced by incorporating domain expert knowledge. Our method addresses an important obstacle for model development in fields dominated by cross-sectional datasets.
MultiWalk: A Framework to Generate Node Embeddings Based on an Ensemble of Walk Methods
Venue: arXiv cs.SI 2021
Year: 2021

Graph embeddings are low dimensional representations of nodes, edges or whole graphs. Such representations allow for data in a network format to be used along with machine learning models for a variety of tasks (e.g., node classification), where using a similarity matrix would be impractical. In recent years, many methods for graph embedding generation have been created based on the idea of random walks. We propose MultiWalk, a framework that uses an ensemble of these methods to generate the embeddings. Our experiments show that the proposed framework, using an ensemble composed of two state-of-the-art methods, can generate embeddings that perform better in classification tasks than each method in isolation.
Deep Policy Dynamic Programming for Vehicle Routing Problems
Venue: arXiv cs.LG 2021
Year: 2021

Routing problems are a class of combinatorial problems with many practical applications. Recently, end-to-end deep learning methods have been proposed to learn approximate solution heuristics for such problems. In contrast, classical dynamic programming (DP) algorithms guarantee optimal solutions, but scale badly with the problem size. We propose Deep Policy Dynamic Programming (DPDP), which aims to combine the strengths of learned neural heuristics with those of DP algorithms. DPDP prioritizes and restricts the DP state space using a policy derived from a deep neural network, which is trained to predict edges from example solutions. We evaluate our framework on the travelling salesman problem (TSP), the vehicle routing problem (VRP) and TSP with time windows (TSPTW) and show that the neural policy improves the performance of (restricted) DP algorithms, making them competitive to strong alternatives such as LKH, while also outperforming most other 'neural approaches' for solving TSPs, VRPs and TSPTWs with 100 nodes.
Inferring Agents Preferences as Priors for Probabilistic Goal Recognition
Venue: arXiv cs.AI 2021
Year: 2021

Recent approaches to goal recognition have leveraged planning landmarks to achieve high-accuracy with low runtime cost. These approaches, however, lack a probabilistic interpretation. Furthermore, while most probabilistic models to goal recognition assume that the recognizer has access to a prior probability representing, for example, an agent's preferences, virtually no goal recognition approach actually uses the prior in practice, simply assuming a uniform prior. In this paper, we provide a model to both extend landmark-based goal recognition with a probabilistic interpretation and allow the estimation of such prior probability and its usage to compute posterior probabilities after repeated interactions of observed agents. We empirically show that our model can not only recognize goals effectively but also successfully infer the correct prior probability distribution representing an agent's preferences.