OpenRaiser/Intern-Atlas huggingface dataset:
Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming
Venue: arXiv cs.LG 2021
Year: 2021

In this work, we propose a deep reinforcement learning (DRL) model for finding a feasible solution for (mixed) integer programming (MIP) problems. Finding a feasible solution for MIP problems is critical because many successful heuristics rely on a known initial feasible solution. However, it is in general NP-hard. Inspired by the feasibility pump (FP), a well-known heuristic for searching feasible MIP solutions, we develop a smart feasibility pump (SFP) method using DRL. In addition to multi-layer perception (MLP), we propose a novel convolution neural network (CNN) structure for the policy network to capture the hidden information of the constraint matrix of the MIP problem. Numerical experiments on various problem instances show that SFP significantly outperforms the classic FP in terms of the number of steps required to reach the first feasible solution. Moreover, the CNN structure works without the projection of the current solution as the input, which saves the computational effort at each step of the FP algorithms to find projections. This highlights the representational power of the CNN structure.
Dialect Identification in Nuanced Arabic Tweets Using Farasa Segmentation and AraBERT
Venue: arXiv cs.CL 2021
Year: 2021

This paper presents our approach to address the EACL WANLP-2021 Shared Task 1: Nuanced Arabic Dialect Identification (NADI). The task is aimed at developing a system that identifies the geographical location(country/province) from where an Arabic tweet in the form of modern standard Arabic or dialect comes from. We solve the task in two parts. The first part involves pre-processing the provided dataset by cleaning, adding and segmenting various parts of the text. This is followed by carrying out experiments with different versions of two Transformer based models, AraBERT and AraELECTRA. Our final approach achieved macro F1-scores of 0.216, 0.235, 0.054, and 0.043 in the four subtasks, and we were ranked second in MSA identification subtasks and fourth in DA identification subtasks.
SEPAL: Towards a Large-scale Analysis of SEAndroid Policy Customization
Venue: arXiv cs.CR 2021
Year: 2021

To investigate the status quo of SEAndroid policy customization, we propose SEPAL, a universal tool to automatically retrieve and examine the customized policy rules. SEPAL applies the NLP technique and employs and trains a wide&deep model to quickly and precisely predict whether one rule is unregulated or not.Our evaluation shows SEPAL is effective, practical and scalable. We verify SEPAL outperforms the state of the art approach (i.e., EASEAndroid) by 15% accuracy rate on average. In our experiments, SEPAL successfully identifies 7,111 unregulated policy rules with a low false positive rate from 595,236 customized rules (extracted from 774 Android firmware images of 72 manufacturers). We further discover the policy customization problem is getting worse in newer Android versions (e.g., around 8% for Android 7 and nearly 20% for Android 9), even though more and more efforts are made. Then, we conduct a deep study and discuss why the unregulated rules are introduced and how they can compromise user devices. Last, we report some unregulated rules to seven vendors and so far four of them confirm our findings.
Characterizing and Mitigating Self-Admitted Technical Debt in Build Systems
Venue: arXiv cs.SE 2021
Year: 2021

Technical Debt is a metaphor used to describe the situation in which long-term software artifact quality is traded for short-term goals in software projects. In recent years, the concept of self-admitted technical debt (SATD) was proposed, which focuses on debt that is intentionally introduced and described by developers. Although prior work has made important observations about admitted technical debt in source code, little is known about SATD in build systems. In this paper, we set out to better understand the characteristics of SATD in build systems. To do so, through a qualitative analysis of 500 SATD comments in the Maven build system of 291 projects, we characterize SATD by location and rationale (reason and purpose). Our results show that limitations in tools and libraries, and complexities of dependency management are the most frequent causes, accounting for 50% and 24% of the comments. We also find that developers often document SATD as issues to be fixed later. As a first step towards the automatic detection of SATD rationale, we train classifiers to detect the two most frequently occurring reasons and the four most frequently occurring purposes of SATD in the content of comments in Maven build systems. The classifier performance is promising, achieving an F1-score of 0.71-0.79. Finally, within 16 identified 'ready-to-be-addressed' SATD instances, the three SATD submitted by pull requests and the five SATD submitted by issue reports were resolved after developers were made aware. Our work presents the first step towards understanding technical debt in build systems and opens up avenues for future work, such as tool support to track and manage SATD backlogs.
Hardness of Metric Dimension in Graphs of Constant Treewidth
Venue: arXiv cs.DS 2021
Year: 2021

The Metric Dimension problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph $G$. Here, a set $S \subseteq V(G)$ is resolving if no two distinct vertices of $G$ have the same distance vector to $S$. The complexity of Metric Dimension in graphs of bounded treewidth remained elusive in the past years. Recently, Bonnet and Purohit [IPEC 2019] showed that the problem is W[1]-hard under treewidth parameterization. In this work, we strengthen their lower bound to show that Metric Dimension is NP-hard in graphs of treewidth 24.
Construction of Side Channel Attacks Resistant S-boxes using Genetic Algorithms based on Coordinate Functions
Venue: arXiv cs.CR 2021
Year: 2021

Background and Objectives: Substitution-box (s-box) is one of the essential components to create confusion and nonlinear properties in cryptography. To strengthening a cipher against various attacks, including side channel attacks, these boxes need to have numerous security properties. In this paper, a novel method to generate s-boxes is introduced aimed at improving the resistance of s-boxes against side channel attacks. Methods: In the preprocessing phase of this approach, a suitable initial s-box which has some basic security properties is generated by adopting a fast algorithm. Then, in the main stage, using the initial s-box, we generate new s-boxes which not only have the properties of the initial S-box but also have been significantly improved under another set of security properties. To do this, new s-boxes are generated using a genetic algorithm on a particular subset of the linear combination set of coordinate functions of the initial s-box in the preprocessing stage. Results: The performed experiments demonstrate that the values of all security properties of these new s-boxes, especially the measures of transparency order, signal-to-noise ratio, confusion coefficient, bijection property, fixed point, and opposite fixed points, have been substantially improved. For example, our experiments indicate that 70, 220, 2071, 43, and 406 s-boxes are found better than the initial s-box, respectively, in the dimensions of 4x4 through 8x8 Conclusion: In this article, a new s-box construction method is introduced in which the properties related to side channel attacks are improved, without reducing other security properties. Besides, some results obtained from generated s-boxes in the dimensions of 4x4 through 8x8 demonstrated that the generated s-boxes are not only improved relative to the initial s-box, but in some cases, considerably better than some well-known s-boxes.
Defense against flooding attacks using probabilistic thresholds in the internet of things ecosystem
Venue: arXiv cs.CR 2021
Year: 2021

The Internet of Things (IoT) ecosystem allows communication between billions of devices worldwide that are collecting data autonomously. The vast amount of data generated by these devices must be controlled totally securely. The centralized solutions are not capable of responding to these concerns due to security challenges problems. Thus, the Average Packet Transmission RREQ (APT-RREQ) as an effective solution, has been employed to overcome these concerns to allow for entirely secure communication between devices. In this paper, an approach called LSFA-IoT is proposed that protects the AODV routing protocol as well as the IoT network against flooding. The proposed method is divided into two main phases; The first phase includes a physical layer intrusion and attack detection system used to detect attacks, and the second phase involves detecting incorrect events through APT-RREQ messages. The simulation results indicated the superiority of the proposed method in terms of False Positive Rate (FPR), False Negative Rate (FPR), Detection Rate (DR), and Packet Delivery Rate (PDR) compared to REATO and IRAD. Also, the simulation results show how the proposed approach can significantly increase the security of each thing and network security.
Back to Prior Knowledge: Joint Event Causality Extraction via Convolutional Semantic Infusion
Venue: arXiv cs.CL 2021
Year: 2021

Joint event and causality extraction is a challenging yet essential task in information retrieval and data mining. Recently, pre-trained language models (e.g., BERT) yield state-of-the-art results and dominate in a variety of NLP tasks. However, these models are incapable of imposing external knowledge in domain-specific extraction. Considering the prior knowledge of frequent n-grams that represent cause/effect events may benefit both event and causality extraction, in this paper, we propose convolutional knowledge infusion for frequent n-grams with different windows of length within a joint extraction framework. Knowledge infusion during convolutional filter initialization not only helps the model capture both intra-event (i.e., features in an event cluster) and inter-event (i.e., associations across event clusters) features but also boosts training convergence. Experimental results on the benchmark datasets show that our model significantly outperforms the strong BERT+CSNN baseline.
DemSelf, a Mobile App for Self-Administered Touch-Based Cognitive Screening: Participatory Design With Stakeholders
Venue: arXiv cs.HC 2021
Year: 2021

Early detection of mild cognitive impairment and dementia is vital as many therapeutic interventions are particularly effective at an early stage. A self-administered touch-based cognitive screening instrument, called DemSelf, was developed by adapting an examiner-administered paper-based instrument, the Quick Mild Cognitive Impairment (Qmci) screen. We conducted five semi-structured expert interviews including a think-aloud phase to evaluate usability problems. The extent to which the characteristics of the original subtests change by the adaption, as well as the conditions and appropriate context for practical application, were also in question. The participants had expertise in the domain of usability and human-machine interaction and/or in the domain of dementia and neuropsychological assessment. Participants identified usability issues in all components of the DemSelf prototype. For example, confirmation of answers was not consistent across subtests. Answers were sometimes logged directly when a button is tapped and cannot be corrected. This can lead to frustration and bias in test results, especially for people with vision or motor impairments. The direct adoption of time limits from the original paper-based instrument or the simultaneous verbal and textual item presentation also caused usability problems. DemSelf is a different test than Qmci and needs to be re-validated. Visual recognition instead of a free verbal recall is one of the main differences. Reading skill level seems to be an important confounding variable. Participants would generally prefer if the test is conducted in a medical office rather than at a patient's home so that someone is present for support and the result can be discussed directly.
A bi-level encoding scheme for the clustered shortest-path tree problem in multifactorial optimization
Venue: arXiv cs.AI 2021
Year: 2021

The Clustered Shortest-Path Tree Problem (CluSPT) plays an important role in various types of optimization problems in real-life. Recently, some Multifactorial Evolutionary Algorithm (MFEA) have been introduced to deal with the CluSPT, however these researches still have some shortcomings such as evolution operators only perform on complete graphs, huge resource consumption for finding the solution on large search spaces. To overcome these limitations, this paper describes a MFEA-based approach to solve the CluSPT. The proposed algorithm utilizes Dijkstra's algorithm to construct the spanning trees in clusters while using evolutionary operators for building the spanning tree connecting clusters. This approach takes advantage of both exact and approximate algorithms so it enables the algorithm to function efficiently on complete and sparse graphs alike. Furthermore, evolutionary operators such as individual encoding and decoding methods are also designed with great consideration regarding performance and memory usage. We have included a proof on the repairing method's efficacy in ensuring all solutions are valid. We have conducted tests on various types of Euclidean instances to assess the effectiveness of the proposed algorithm and methods. Experiment results point out the effectiveness of the proposed algorithm existing heuristic algorithms in most of the test cases. The impact of the proposed MFEA was analyzed and a possible influential factor that may be useful for further study was also pointed out.
Subjective Assessments of Legibility in Ancient Manuscript Images -- The SALAMI Dataset
Venue: arXiv cs.CV 2021
Year: 2021

The research field concerned with the digital restoration of degraded written heritage lacks a quantitative metric for evaluating its results, which prevents the comparison of relevant methods on large datasets. Thus, we introduce a novel dataset of Subjective Assessments of Legibility in Ancient Manuscript Images (SALAMI) to serve as a ground truth for the development of quantitative evaluation metrics in the field of digital text restoration. This dataset consists of 250 images of 50 manuscript regions with corresponding spatial maps of mean legibility and uncertainty, which are based on a study conducted with 20 experts of philology and paleography. As this study is the first of its kind, the validity and reliability of its design and the results obtained are motivated statistically: we report a high intra- and inter-rater agreement and show that the bulk of variation in the scores is introduced by the images regions observed and not by controlled or uncontrolled properties of participants and test environments, thus concluding that the legibility scores measured are valid attributes of the underlying images.
Temporal Gaussian Process Regression in Logarithmic Time
Venue: arXiv cs.LG 2021
Year: 2021

The aim of this article is to present a novel parallelization method for temporal Gaussian process (GP) regression problems. The method allows for solving GP regression problems in logarithmic O(log N) time, where N is the number of time steps. Our approach uses the state-space representation of GPs which in its original form allows for linear O(N) time GP regression by leveraging the Kalman filtering and smoothing methods. By using a recently proposed parallelization method for Bayesian filters and smoothers, we are able to reduce the linear computational complexity of the temporal GP regression problems into logarithmic span complexity. This ensures logarithmic time complexity when run on parallel hardware such as a graphics processing unit (GPU). We experimentally demonstrate the computational benefits on simulated and real datasets via our open-source implementation leveraging the GPflow framework.
Analyzing Curriculum Learning for Sentiment Analysis along Task Difficulty, Pacing and Visualization Axes
Venue: arXiv cs.CL 2021
Year: 2021

While Curriculum Learning (CL) has recently gained traction in Natural language Processing Tasks, it is still not adequately analyzed. Previous works only show their effectiveness but fail short to explain and interpret the internal workings fully. In this paper, we analyze curriculum learning in sentiment analysis along multiple axes. Some of these axes have been proposed by earlier works that need more in-depth study. Such analysis requires understanding where curriculum learning works and where it does not. Our axes of analysis include Task difficulty on CL, comparing CL pacing techniques, and qualitative analysis by visualizing the movement of attention scores in the model as curriculum phases progress. We find that curriculum learning works best for difficult tasks and may even lead to a decrement in performance for tasks with higher performance without curriculum learning. We see that One-Pass curriculum strategies suffer from catastrophic forgetting and attention movement visualization within curriculum pacing. This shows that curriculum learning breaks down the challenging main task into easier sub-tasks solved sequentially.
Using Transformer based Ensemble Learning to classify Scientific Articles
Venue: arXiv cs.CL 2021
Year: 2021

Many time reviewers fail to appreciate novel ideas of a researcher and provide generic feedback. Thus, proper assignment of reviewers based on their area of expertise is necessary. Moreover, reading each and every paper from end-to-end for assigning it to a reviewer is a tedious task. In this paper, we describe a system which our team FideLIPI submitted in the shared task of SDPRA-2021 [14]. It comprises four independent sub-systems capable of classifying abstracts of scientific literature to one of the given seven classes. The first one is a RoBERTa [10] based model built over these abstracts. Adding topic models / Latent dirichlet allocation (LDA) [2] based features to the first model results in the second sub-system. The third one is a sentence level RoBERTa [10] model. The fourth one is a Logistic Regression model built using Term Frequency Inverse Document Frequency (TF-IDF) features. We ensemble predictions of these four sub-systems using majority voting to develop the final system which gives a F1 score of 0.93 on the test and validation set. This outperforms the existing State Of The Art (SOTA) model SciBERT's [1] in terms of F1 score on the validation set.Our codebase is available at https://github.com/SDPRA-2021/shared-task/tree/main/FideLIPI
Social Network Analysis: From Graph Theory to Applications with Python
Venue: arXiv cs.SI 2021
Year: 2021

Social network analysis is the process of investigating social structures through the use of networks and graph theory. It combines a variety of techniques for analyzing the structure of social networks as well as theories that aim at explaining the underlying dynamics and patterns observed in these structures. It is an inherently interdisciplinary field which originally emerged from the fields of social psychology, statistics and graph theory. This talk will covers the theory of social network analysis, with a short introduction to graph theory and information spread. Then we will deep dive into Python code with NetworkX to get a better understanding of the network components, followed-up by constructing and implying social networks from real Pandas and textual datasets. Finally we will go over code examples of practical use-cases such as visualization with matplotlib, social-centrality analysis and influence maximization for information spread.
Neural Kalman Filtering
Venue: arXiv cs.NE 2021
Year: 2021

The Kalman filter is a fundamental filtering algorithm that fuses noisy sensory data, a previous state estimate, and a dynamics model to produce a principled estimate of the current state. It assumes, and is optimal for, linear models and white Gaussian noise. Due to its relative simplicity and general effectiveness, the Kalman filter is widely used in engineering applications. Since many sensory problems the brain faces are, at their core, filtering problems, it is possible that the brain possesses neural circuitry that implements equivalent computations to the Kalman filter. The standard approach to Kalman filtering requires complex matrix computations that are unlikely to be directly implementable in neural circuits. In this paper, we show that a gradient-descent approximation to the Kalman filter requires only local computations with variance weighted prediction errors. Moreover, we show that it is possible under the same scheme to adaptively learn the dynamics model with a learning rule that corresponds directly to Hebbian plasticity. We demonstrate the performance of our method on a simple Kalman filtering task, and propose a neural implementation of the required equations.
Pyserini: An Easy-to-Use Python Toolkit to Support Replicable IR Research with Sparse and Dense Representations
Venue: arXiv cs.IR 2021
Year: 2021

Pyserini is an easy-to-use Python toolkit that supports replicable IR research by providing effective first-stage retrieval in a multi-stage ranking architecture. Our toolkit is self-contained as a standard Python package and comes with queries, relevance judgments, pre-built indexes, and evaluation scripts for many commonly used IR test collections. We aim to support, out of the box, the entire research lifecycle of efforts aimed at improving ranking with modern neural approaches. In particular, Pyserini supports sparse retrieval (e.g., BM25 scoring using bag-of-words representations), dense retrieval (e.g., nearest-neighbor search on transformer-encoded representations), as well as hybrid retrieval that integrates both approaches. This paper provides an overview of toolkit features and presents empirical results that illustrate its effectiveness on two popular ranking tasks. We also describe how our group has built a culture of replicability through shared norms and tools that enable rigorous automated testing.
Formal Language Theory Meets Modern NLP
Venue: arXiv cs.CL 2021
Year: 2021

NLP is deeply intertwined with the formal study of language, both conceptually and historically. Arguably, this connection goes all the way back to Chomsky's Syntactic Structures in 1957. It also still holds true today, with a strand of recent works building formal analysis of modern neural networks methods in terms of formal languages. In this document, I aim to explain background about formal languages as they relate to this recent work. I will by necessity ignore large parts of the rich history of this field, instead focusing on concepts connecting to modern deep learning-based NLP.
Scaling up DNA digital data storage by efficiently predicting DNA hybridisation using deep learning
Venue: arXiv cs.LG 2021
Year: 2021

Deoxyribonucleic acid (DNA) has shown great promise in enabling computational applications, most notably in the fields of DNA digital data storage and DNA computing. Information is encoded as DNA strands, which will naturally bind in solution, thus enabling search and pattern-matching capabilities. Being able to control and predict the process of DNA hybridisation is crucial for the ambitious future of Hybrid Molecular-Electronic Computing. Current tools are, however, limited in terms of throughput and applicability to large-scale problems. We present the first comprehensive study of machine learning methods applied to the task of predicting DNA hybridisation. For this purpose, we introduce an in silico-generated hybridisation dataset of over 2.5 million data points, enabling the use of deep learning. Depending on hardware, we achieve a reduction in inference time ranging from one to over two orders of magnitude compared to the state-of-the-art, while retaining high fidelity. We then discuss the integration of our methods in modern, scalable workflows.