OpenRaiser/Intern-Atlas huggingface dataset:
Minimal Absent Words in Rooted and Unrooted Trees
Venue: arXiv cs.DS 2019
Year: 2019

We extend the theory of minimal absent words to (rooted and unrooted) trees, having edges labeled by letters from an alphabet $Σ$ of cardinality $σ$. We show that the set $\text{MAW}(T)$ of minimal absent words of a rooted (resp. unrooted) tree $T$ with $n$ nodes has cardinality $O(nσ)$ (resp. $O(n^{2}σ)$), and we show that these bounds are realized. Then, we exhibit algorithms to compute all minimal absent words in a rooted (resp. unrooted) tree in output-sensitive time $O(n+|\text{MAW}(T)|)$ (resp. $O(n^{2}+|\text{MAW}(T)|)$ assuming an integer alphabet of size polynomial in $n$.
Probabilistic Models of Relational Implication
Venue: arXiv cs.LG 2019
Year: 2019

Relational data in its most basic form is a static collection of known facts. However, by learning to infer and deduct additional information and structure, we can massively increase the usefulness of the underlying data. One common form of inferential reasoning in knowledge bases is implication discovery. Here, by learning when one relation implies another, we can extend our knowledge representation. There are several existing models for relational implication, however we argue they are motivated but not principled. To this end, we define a formal probabilistic model of relational implication. By using estimators based on the empirical distribution of our dataset, we demonstrate that our model outperforms existing approaches. While previous work achieves a best score of 0.7812 AUC on an evaluatory dataset, our ProbE model improves this to 0.7915. Furthermore, we demonstrate that our model can be improved substantially through the use of link prediction models and dense latent representations of the underlying argument and relations. This variant, denoted ProbL, improves the state of the art on our evaluation dataset to 0.8143. In addition to developing a new framework and providing novel scores of relational implication, we provide two pragmatic resources to assist future research. First, we motivate and develop an improved crowd framework for constructing labelled datasets of relational implication. Using this, we reannotate and make public a dataset comprised of 17,848 instances of labelled relational implication. We demonstrate that precision (as evaluated by expert consensus with the crowd labels) on the resulting dataset improves from 53% to 95%.
Fast Authentication and Progressive Authorization in Large-Scale IoT: How to Leverage AI for Security Enhancement?
Venue: arXiv cs.CR 2019
Year: 2019

Security provisioning has become the most important design consideration for large-scale Internet of Things (IoT) systems due to their critical roles to support diverse vertical applications by connecting heterogenous devices, machines and industry processes. Conventional authentication and authorization schemes are insufficient in dealing the emerging IoT security challenges due to their reliance on both static digital mechanisms and computational complexity for improving security level. Furthermore, the isolated security designs for different layers and link segments while ignoring the overall protection lead to cascaded security risks as well as growing communication latency and overhead. In this article, we envision new artificial intelligence (AI) enabled security provisioning approaches to overcome these issues while achieving fast authentication and progressive authorization. To be more specific, a lightweight intelligent authentication approach is developed by exploring machine learning at the gateway to identify the access time slots or frequencies of resource-constraint devices. Then we propose a holistic authentication and authorization approach, where online machine learning and trust management are adopted for analyzing the complex dynamic environment and achieving adaptive access control. These new AI enabled approaches establish the connections between transceivers quickly and enhance security progressively, so that communication latency can be reduced and security risks are well-controlled in large-scale IoT. Finally, we outline several areas for AI-enabled security provisioning for future researches.
Real-time Tracking-by-Detection of Human Motion in RGB-D Camera Networks
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents a novel real-time tracking system capable of improving body pose estimation algorithms in distributed camera networks. The first stage of our approach introduces a linear Kalman filter operating at the body joints level, used to fuse single-view body poses coming from different detection nodes of the network and to ensure temporal consistency between them. The second stage, instead, refines the Kalman filter estimates by fitting a hierarchical model of the human body having constrained link sizes in order to ensure the physical consistency of the tracking. The effectiveness of the proposed approach is demonstrated through a broad experimental validation, performed on a set of sequences whose ground truth references are generated by a commercial marker-based motion capture system. The obtained results show how the proposed system outperforms the considered state-of-the-art approaches, granting accurate and reliable estimates. Moreover, the developed methodology constrains neither the number of persons to track, nor the number, position, synchronization, frame-rate, and manufacturer of the RGB-D cameras used. Finally, the real-time performances of the system are of paramount importance for a large number of real-world applications.
Towards Optimizing Reiter's HS-Tree for Sequential Diagnosis
Venue: arXiv cs.AI 2019
Year: 2019

Reiter's HS-Tree is one of the most popular diagnostic search algorithms due to its desirable properties and general applicability. In sequential diagnosis, where the addressed diagnosis problem is subject to successive change through the acquisition of additional knowledge about the diagnosed system, HS-Tree is used in a stateless fashion. That is, the existing search tree is discarded when new knowledge is obtained, albeit often large parts of the tree are still relevant and have to be rebuilt in the next iteration, involving redundant operations and costly reasoner calls. As a remedy to this, we propose DynamicHS, a variant of HS-Tree that avoids these redundancy issues by maintaining state throughout sequential diagnosis while preserving all desirable properties of HS-Tree. Preliminary results of ongoing evaluations in a problem domain where HS-Tree is the state-of-the-art diagnostic method suggest significant time savings achieved by DynamicHS by reducing expensive reasoner calls.
Introducing Autarkies for DQCNF
Venue: arXiv cs.LO 2019
Year: 2019

Autarkies for SAT can be used for theoretical studies, pre-processing and inprocessing. They generalise satisfying assignments by allowing to leave some clauses "untouched" (no variable assigned). We introduce the natural generalisation to DQCNF (dependency-quantified boolean CNF), with the perspective of SAT translations for special cases. Finding an autarky for DQCNF is as hard as finding a satisfying assignment. Fortunately there are (many) natural autarky-systems, which allow restricting the range of autarkies to a more feasible domain, while still maintaining the good general properties of arbitrary autarkies. We discuss what seems the most fundamental autarky systems, and how the related reductions can be found by SAT solvers.
Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis
Venue: arXiv cs.LO 2019
Year: 2019

We propose "semantic labelling" as a novel ingredient for solving games in the context of LTL synthesis. It exploits recent advances in the automata-based approach, yielding more information for each state of the generated parity game than the game graph can capture. We utilize this extra information to improve standard approaches as follows. (i) Compared to strategy improvement (SI) with random initial strategy, a more informed initialization often yields a winning strategy directly without any computation. (ii) This initialization makes SI also yield smaller solutions. (iii) While Q-learning on the game graph turns out not too efficient, Q-learning with the semantic information becomes competitive to SI. Since already the simplest heuristics achieve significant improvements the experimental results demonstrate the utility of semantic labelling. This extra information opens the door to more advanced learning approaches both for initialization and improvement of strategies.
The Challenges of Investigating Cryptocurrencies and Blockchain Related Crime
Venue: arXiv cs.CY 2019
Year: 2019

We increasingly live in a world where there is a balance between the rights to privacy and the requirements for consent, and the rights of society to protect itself. Within this world, there is an ever-increasing requirement to protect the identities involved within financial transactions, but this makes things increasingly difficult for law enforcement agencies, especially in terms of financial fraud and money laundering. This paper reviews the state-of-the-art in terms of the methods of privacy that are being used within cryptocurrency transactions, and in the challenges that law enforcement face.
Multi-Granularity Fusion Network for Proposal and Activity Localization: Submission to ActivityNet Challenge 2019 Task 1 and Task 2
Venue: arXiv cs.CV 2019
Year: 2019

This technical report presents an overview of our solution used in the submission to ActivityNet Challenge 2019 Task 1 (\textbf{temporal action proposal generation}) and Task 2 (\textbf{temporal action localization/detection}). Temporal action proposal indicates the temporal intervals containing the actions and plays an important role in temporal action localization. Top-down and bottom-up methods are the two main categories used for proposal generation in the existing literature. In this paper, we devise a novel Multi-Granularity Fusion Network (MGFN) to combine the proposals generated from different frameworks for complementary filtering and confidence re-ranking. Specifically, we consider the diversity comprehensively from multiple perspectives, e.g. the characteristic aspect, the data aspect, the model aspect and the result aspect. Our MGFN achieves the state-of-the-art performance on the temporal action proposal task with 69.85 AUC score and the temporal action localization task with 38.90 mAP on the challenge testing set.
Regularizing Proxies with Multi-Adversarial Training for Unsupervised Domain-Adaptive Semantic Segmentation
Venue: arXiv cs.CV 2019
Year: 2019

Training a semantic segmentation model requires a large amount of pixel-level annotation, hampering its application at scale. With computer graphics, we can generate almost unlimited training data with precise annotation. However,a deep model trained with synthetic data usually cannot directly generalize well to realistic images due to domain shift. It has been observed that highly confident labels for the unlabeled real images may be predicted relying on the labeled synthetic data. To tackle the unsupervised domain adaptation problem, we explore the possibilities to generate high-quality labels as proxy labels to supervise the training on target data. Specifically, we propose a novel proxy-based method using multi-adversarial training. We first train the model using synthetic data (source domain). Multiple discriminators are used to align the features be-tween the source and target domain (real images) at different levels. Then we focus on obtaining and selecting high-quality proxy labels by incorporating both the confidence of the class predictor and that from the adversarial discriminators. Our discriminators not only work as a regularizer to encourage feature alignment but also provide an alternative confidence measure for generating proxy labels. Relying on the generated high-quality proxies, our model can be trained in a "supervised manner" on the target do-main. On two major tasks, GTA5->Cityscapes and SYNTHIA->Cityscapes, our method achieves state-of-the-art results, outperforming the previous by a large margin.
Parameterized Valiant's Classes
Venue: arXiv cs.CC 2019
Year: 2019

We define a theory of parameterized algebraic complexity classes in analogy to parameterized Boolean counting classes. We define the classes VFPT and VW[t], which mirror the Boolean counting classes #FPT and #W[t], and define appropriate reductions and completeness notions. Our main contribution is the VW[1]-completeness proof of the parameterized clique family. This proof is far more complicated than in the Boolean world. It requires some new concepts like composition theorems for bounded exponential sums and Boolean-arithmetic formulas. In addition, we also look at two polynomials linked to the permanent with vastly different parameterized complexity.
An Empirical Assessment on Affective Reactions of Novice Developers when Applying Test-Driven Development
Venue: arXiv cs.SE 2019
Year: 2019

We study whether and in which phase Test-Driven Development (TDD) influences affective states of novice developers in terms of pleasure, arousal, dominance, and liking. We performed a controlled experiment with 29 novice developers. Developers in the treatment group performed a development task using TDD, whereas those in the control group used a non-TDD development approach. We compared the affective reactions to the development approaches, as well as to the implementation and testing phases, exploiting a lightweight, powerful, and widely used tool, i.e., Self-Assessment Manikin. We observed that there is a difference between the two development approaches in terms of affective reactions. Therefore, it seems that affective reactions play an important role when applying TDD and their investigation could help researchers to better understand such a development approach
Capture Aware Sequential Waterfilling for LoraWAN Adaptive Data Rate
Venue: arXiv cs.NI 2019
Year: 2019

LoRaWAN (Long Range Wide Area Network) is emerging as an attractive network infrastructure for ultra low power Internet of Things devices. Even if the technology itself is quite mature and specified, the currently deployed wireless resource allocation strategies are still coarse and based on rough heuristics. This paper proposes an innovative "sequential waterfilling" strategy for assigning Spreading Factors (SF) to End-Devices (ED). Our design relies on three complementary approaches: i) equalize the Time-on-Air of the packets transmitted by the system's EDs in each spreading factor's group; ii) balance the spreading factors across multiple access gateways, and iii) keep into account the channel capture, which our experimental results show to be very substantial in LoRa. While retaining an extremely simple and scalable implementation, this strategy yields a significant improvement (up to 38%) in the network capacity over the legacy Adaptive Data Rate (ADR), and appears to be extremely robust to different operating/load conditions and network topology configurations.
Detecting Radical Text over Online Media using Deep Learning
Venue: arXiv cs.IR 2019
Year: 2019

Social Media has influenced the way people socially connect, interact and opinionize. The growth in technology has enhanced communication and dissemination of information. Unfortunately,many terror groups like jihadist communities have started consolidating a virtual community online for various purposes such as recruitment, online donations, targeting youth online and spread of extremist ideologies. Everyday a large number of articles, tweets, posts, posters, blogs, comments, views and news are posted online without a check which in turn imposes a threat to the security of any nation. However, different agencies are working on getting down this radical content from various online social media platforms. The aim of our paper is to utilise deep learning algorithm in detection of radicalization contrary to the existing works based on machine learning algorithms. An LSTM based feed forward neural network is employed to detect radical content. We collected total 61601 records from various online sources constituting news, articles and blogs. These records are annotated by domain experts into three categories: Radical(R), Non-Radical (NR) and Irrelevant(I) which are further applied to LSTM based network to classify radical content. A precision of 85.9% has been achieved with the proposed approach
Computing the Value of Data: Towards Applied Data Minimalism
Venue: arXiv cs.LG 2019
Year: 2019

We present an approach to compute the monetary value of individual data points, in context of an automated decision system. The proposed method enables us to explore and implement a paradigm of data minimalism for large-scale machine learning systems. Data minimalistic implementations enhance scalability, while maintaining or even optimizing a system's performance. Using two types of recommender systems, we first demonstrate how much data is ineffective in both settings. We then present a general account of computing data value via sensitivity analysis, and how, in theory, individual data points can be priced according to their informational contribution to automated decisions. We further exemplify this method to lab-scale recommender systems and outline further steps towards commercial data-minimalistic applications.
A new record of graph enumeration enabled by parallel processing
Venue: arXiv cs.DM 2019
Year: 2019

Using three supercomputers, we broke a record set in 2011, in the enumeration of non-isomorphic regular graphs by expanding the sequence of A006820 in Online Encyclopedia of Integer Sequences (OEIS), to achieve the number for 4-regular graphs of order 23 as 429,668,180,677,439, while discovering serval optimal regular graphs with minimum average shortest path lengths (ASPL) that can be used as interconnection networks for parallel computers. The number of 4-regular graphs and the optimal graphs, extremely time-consuming to calculate, result from a method we adapt from GENREG, a classical regular graph generator, to fit for supercomputers' strengths of using thousands of processor cores.
X-LineNet: Detecting Aircraft in Remote Sensing Images by a pair of Intersecting Line Segments
Venue: arXiv cs.CV 2019
Year: 2019

Motivated by the development of deep convolution neural networks (DCNNs), tremendous progress has been gained in the field of aircraft detection. These DCNNs based detectors mainly belong to top-down approaches, which first enumerate massive potential locations of objects with the form of rectangular regions, and then identify whether they are objects or not. Compared with these top-down approaches, this paper shows that aircraft detection via bottom-up approach still performs competitively in the era of deep learning. We present a novel one-stage and anchor-free aircraft detection model in a bottom-up manner, which formulates the task as detection of two intersecting line segments inside each target and grouping of them without any rectangular region classification. This model is named as X-LineNet. With simple post-processing, X-LineNet can simultaneously provide multiple representation forms of the detection result: the horizontal bounding box, the rotating bounding box, and the pentagonal mask. The pentagonal mask is a more accurate representation form which has less redundancy and can better represent aircraft than that of rectangular box. Experiments show that X-LineNet outperforms state-of-the-art one-stage object detectors and is competitive compared with advanced two-stage detectors on both UCAS-AOD and NWPU VHR-10 open dataset in the field of aircraft detection.
Diffusion Hypercontractivity via Generalized Density Manifold
Venue: arXiv cs.IT 2019
Year: 2019

We prove a one-parameter family of diffusion hypercontractivity and present the associated Log-Sobolev, Poincare and Talagrand inequalities. A mean-field type Bakry-Emery iterative calculus and volume measure based integration formula (Yano's formula) are presented. Our results are based on the interpolation among divergence functional, generalized diffusion process, and generalized optimal transport metric. As a result, an inequality among Pearson divergence (P), negative Sobolev metric H^-1 and generalized Fisher information functional (I), named PH^{-1}I inequality, is derived.
MoBiNet: A Mobile Binary Network for Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

MobileNet and Binary Neural Networks are two among the most widely used techniques to construct deep learning models for performing a variety of tasks on mobile and embedded platforms.In this paper, we present a simple yet efficient scheme to exploit MobileNet binarization at activation function and model weights. However, training a binary network from scratch with separable depth-wise and point-wise convolutions in case of MobileNet is not trivial and prone to divergence. To tackle this training issue, we propose a novel neural network architecture, namely MoBiNet - Mobile Binary Network in which skip connections are manipulated to prevent information loss and vanishing gradient, thus facilitate the training process. More importantly, while existing binary neural networks often make use of cumbersome backbones such as Alex-Net, ResNet, VGG-16 with float-type pre-trained weights initialization, our MoBiNet focuses on binarizing the already-compressed neural networks like MobileNet without the need of a pre-trained model to start with. Therefore, our proposal results in an effectively small model while keeping the accuracy comparable to existing ones. Experiments on ImageNet dataset show the potential of the MoBiNet as it achieves 54.40% top-1 accuracy and dramatically reduces the computational cost with binary operators.
Mapping road safety features from streetview imagery: A deep learning approach
Venue: arXiv cs.CV 2019
Year: 2019

Each year, around 6 million car accidents occur in the U.S. on average. Road safety features (e.g., concrete barriers, metal crash barriers, rumble strips) play an important role in preventing or mitigating vehicle crashes. Accurate maps of road safety features is an important component of safety management systems for federal or state transportation agencies, helping traffic engineers identify locations to invest on safety infrastructure. In current practice, mapping road safety features is largely done manually (e.g., observations on the road or visual interpretation of streetview imagery), which is both expensive and time consuming. In this paper, we propose a deep learning approach to automatically map road safety features from streetview imagery. Unlike existing Convolutional Neural Networks (CNNs) that classify each image individually, we propose to further add Recurrent Neural Network (Long Short Term Memory) to capture geographic context of images (spatial autocorrelation effect along linear road network paths). Evaluations on real world streetview imagery show that our proposed model outperforms several baseline methods.
Improving MPI Collective I/O Performance With Intra-node Request Aggregation
Venue: arXiv cs.DC 2019
Year: 2019

Two-phase I/O is a well-known strategy for implementing collective MPI-IO functions. It redistributes I/O requests among the calling processes into a form that minimizes the file access costs. As modern parallel computers continue to grow into the exascale era, the communication cost of such request redistribution can quickly overwhelm collective I/O performance. This effect has been observed from parallel jobs that run on multiple compute nodes with a high count of MPI processes on each node. To reduce the communication cost, we present a new design for collective I/O by adding an extra communication layer that performs request aggregation among processes within the same compute nodes. This approach can significantly reduce inter-node communication congestion when redistributing the I/O requests. We evaluate the performance and compare with the original two-phase I/O on a Cray XC40 parallel computer with Intel KNL processors. Using I/O patterns from two large-scale production applications and an I/O benchmark, we show the performance improvement of up to 29 times when running 16384 MPI processes on 256 compute nodes.