OpenRaiser/Intern-Atlas huggingface dataset:
New Subgraph Isomorphism Algorithms: Vertex versus Path-at-a-time Matching
Venue: arXiv cs.DS 2019
Year: 2019

Graphs are widely used to model complicated data semantics in many application domains. In this paper, two novel and efficient algorithms Fast-ON and Fast-P are proposed for solving the subgraph isomorphism problem. The two algorithms are based on Ullman algorithm [Ullmann 1976], apply vertex-at-a-time matching manner and path-at-a-time matching manner respectively, and use effective heuristics to cut the search space. Comparing to the well-known algorithms, Fast-ON and Fast-P achieve up to 1-4 orders of magnitude speed-up for both dense and sparse graph data.
Behavioural Equivalence via Modalities for Algebraic Effects
Venue: arXiv cs.LO 2019
Year: 2019

The paper investigates behavioural equivalence between programs in a call-by-value functional language extended with a signature of (algebraic) effect-triggering operations. Two programs are considered as being behaviourally equivalent if they enjoy the same behavioural properties. To formulate this, we define a logic whose formulas specify behavioural properties. A crucial ingredient is a collection of modalities expressing effect-specific aspects of behaviour. We give a general theory of such modalities. If two conditions, openness and decomposability, are satisfied by the modalities then the logically specified behavioural equivalence coincides with a modality-defined notion of applicative bisimilarity, which can be proven to be a congruence by a generalisation of Howe's method. We show that the openness and decomposability conditions hold for several examples of algebraic effects: nondeterminism, probabilistic choice, global store and input/output.
The Simplest Thing That Can Possibly Work: Pseudo-Relevance Feedback Using Text Classification
Venue: arXiv cs.IR 2019
Year: 2019

Motivated by recent commentary that has questioned today's pursuit of ever-more complex models and mathematical formalisms in applied machine learning and whether meaningful empirical progress is actually being made, this paper tries to tackle the decades-old problem of pseudo-relevance feedback with "the simplest thing that can possibly work". I present a technique based on training a document relevance classifier for each information need using pseudo-labels from an initial ranked list and then applying the classifier to rerank the retrieved documents. Experiments demonstrate significant improvements across a number of newswire collections, with initial rankings supplied by "bag of words" BM25 as well as from a well-tuned query expansion model. While this simple technique draws elements from several well-known threads in the literature, to my knowledge this exact combination has not previously been proposed and evaluated.
Combating the Elsagate phenomenon: Deep learning architectures for disturbing cartoons
Venue: arXiv cs.CV 2019
Year: 2019

Watching cartoons can be useful for children's intellectual, social and emotional development. However, the most popular video sharing platform today provides many videos with Elsagate content. Elsagate is a phenomenon that depicts childhood characters in disturbing circumstances (e.g., gore, toilet humor, drinking urine, stealing). Even with this threat easily available for children, there is no work in the literature addressing the problem. As the first to explore disturbing content in cartoons, we proceed from the most recent pornography detection literature applying deep convolutional neural networks combined with static and motion information of the video. Our solution is compatible with mobile platforms and achieved 92.6% of accuracy. Our goal is not only to introduce the first solution but also to bring up the discussion around Elsagate.
Convex Graph Invariant Relaxations For Graph Edit Distance
Venue: arXiv cs.DS 2019
Year: 2019

The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to transform one graph to another. It is NP-hard to compute in general, and a large number of heuristics have been proposed for approximating this quantity. With few exceptions, these methods generally provide upper bounds on the edit distance between two graphs. In this paper, we propose a new family of computationally tractable convex relaxations for obtaining lower bounds on graph edit distance. These relaxations can be tailored to the structural properties of the particular graphs via convex graph invariants. Specific examples that we highlight in this paper include constraints on the graph spectrum as well as (tractable approximations of) the stability number and the maximum-cut values of graphs. We prove under suitable conditions that our relaxations are tight (i.e., exactly compute the graph edit distance) when one of the graphs consists of few eigenvalues. We also validate the utility of our framework on synthetic problems as well as real applications involving molecular structure comparison problems in chemistry.
Language Modeling through Long Term Memory Network
Venue: arXiv cs.CL 2019
Year: 2019

Recurrent Neural Networks (RNN), Long Short-Term Memory Networks (LSTM), and Memory Networks which contain memory are popularly used to learn patterns in sequential data. Sequential data has long sequences that hold relationships. RNN can handle long sequences but suffers from the vanishing and exploding gradient problems. While LSTM and other memory networks address this problem, they are not capable of handling long sequences (50 or more data points long sequence patterns). Language modelling requiring learning from longer sequences are affected by the need for more information in memory. This paper introduces Long Term Memory network (LTM), which can tackle the exploding and vanishing gradient problems and handles long sequences without forgetting. LTM is designed to scale data in the memory and gives a higher weight to the input in the sequence. LTM avoid overfitting by scaling the cell state after achieving the optimal results. The LTM is tested on Penn treebank dataset, and Text8 dataset and LTM achieves test perplexities of 83 and 82 respectively. 650 LTM cells achieved a test perplexity of 67 for Penn treebank, and 600 cells achieved a test perplexity of 77 for Text8. LTM achieves state of the art results by only using ten hidden LTM cells for both datasets.
On Acoustic Modeling for Broadband Beamforming
Venue: arXiv cs.SD 2019
Year: 2019

In this work, we describe limitations of the free-field propagation model for designing broadband beamformers for microphone arrays on a rigid surface. Towards this goal, we describe a general framework for quantifying the microphone array performance in a general wave-field by directly solving the acoustic wave equation. The model utilizes Finite-Element-Method (FEM) for evaluating the response of the microphone array surface to background 3D planar and spherical waves. The effectiveness of the framework is established by designing and evaluating a representative broadband beamformer under realistic acoustic conditions.
LATTE: Accelerating LiDAR Point Cloud Annotation via Sensor Fusion, One-Click Annotation, and Tracking
Venue: arXiv cs.CV 2019
Year: 2019

LiDAR (Light Detection And Ranging) is an essential and widely adopted sensor for autonomous vehicles, particularly for those vehicles operating at higher levels (L4-L5) of autonomy. Recent work has demonstrated the promise of deep-learning approaches for LiDAR-based detection. However, deep-learning algorithms are extremely data hungry, requiring large amounts of labeled point-cloud data for training and evaluation. Annotating LiDAR point cloud data is challenging due to the following issues: 1) A LiDAR point cloud is usually sparse and has low resolution, making it difficult for human annotators to recognize objects. 2) Compared to annotation on 2D images, the operation of drawing 3D bounding boxes or even point-wise labels on LiDAR point clouds is more complex and time-consuming. 3) LiDAR data are usually collected in sequences, so consecutive frames are highly correlated, leading to repeated annotations. To tackle these challenges, we propose LATTE, an open-sourced annotation tool for LiDAR point clouds. LATTE features the following innovations: 1) Sensor fusion: We utilize image-based detection algorithms to automatically pre-label a calibrated image, and transfer the labels to the point cloud. 2) One-click annotation: Instead of drawing 3D bounding boxes or point-wise labels, we simplify the annotation to just one click on the target object, and automatically generate the bounding box for the target. 3) Tracking: we integrate tracking into sequence annotation such that we can transfer labels from one frame to subsequent ones and therefore significantly reduce repeated labeling. Experiments show the proposed features accelerate the annotation speed by 6.2x and significantly improve label quality with 23.6% and 2.2% higher instance-level precision and recall, and 2.0% higher bounding box IoU. LATTE is open-sourced at https://github.com/bernwang/latte.
Deep Q Learning Driven CT Pancreas Segmentation with Geometry-Aware U-Net
Venue: arXiv cs.CV 2019
Year: 2019

Segmentation of pancreas is important for medical image analysis, yet it faces great challenges of class imbalance, background distractions and non-rigid geometrical features. To address these difficulties, we introduce a Deep Q Network(DQN) driven approach with deformable U-Net to accurately segment the pancreas by explicitly interacting with contextual information and extract anisotropic features from pancreas. The DQN based model learns a context-adaptive localization policy to produce a visually tightened and precise localization bounding box of the pancreas. Furthermore, deformable U-Net captures geometry-aware information of pancreas by learning geometrically deformable filters for feature extraction. Experiments on NIH dataset validate the effectiveness of the proposed framework in pancreas segmentation.
Visualizing the decision-making process in deep neural decision forest
Venue: arXiv cs.CV 2019
Year: 2019

Deep neural decision forest (NDF) achieved remarkable performance on various vision tasks via combining decision tree and deep representation learning. In this work, we first trace the decision-making process of this model and visualize saliency maps to understand which portion of the input influence it more for both classification and regression problems. We then apply NDF on a multi-task coordinate regression problem and demonstrate the distribution of routing probabilities, which is vital for interpreting NDF yet not shown for regression problems. The pre-trained model and code for visualization will be available at https://github.com/Nicholasli1995/VisualizingNDF
Linear Bounded Composition of Tree-Walking Tree Transducers: Linear Size Increase and Complexity
Venue: arXiv cs.FL 2019
Year: 2019

Compositions of tree-walking tree transducers form a hierarchy with respect to the number of transducers in the composition. As main technical result it is proved that any such composition can be realized as a linear bounded composition, which means that the sizes of the intermediate results can be chosen to be at most linear in the size of the output tree. This has consequences for the expressiveness and complexity of the translations in the hierarchy. First, if the computed translation is a function of linear size increase, i.e., the size of the output tree is at most linear in the size of the input tree, then it can be realized by just one, deterministic, tree-walking tree transducer. For compositions of deterministic transducers it is decidable whether or not the translation is of linear size increase. Second, every composition of deterministic transducers can be computed in deterministic linear time on a RAM and in deterministic linear space on a Turing machine, measured in the sum of the sizes of the input and output tree. Similarly, every composition of nondeterministic transducers can be computed in simultaneous polynomial time and linear space on a nondeterministic Turing machine. Their output tree languages are deterministic context-sensitive, i.e., can be recognized in deterministic linear space on a Turing machine. The membership problem for compositions of nondeterministic translations is nondeterministic polynomial time and deterministic linear space. The membership problem for the composition of a nondeterministic and a deterministic tree-walking tree translation (for a nondeterministic IO macro tree translation) is log-space reducible to a context-free language, whereas the membership problem for the composition of a deterministic and a nondeterministic tree-walking tree translation (for a nondeterministic OI macro tree translation) is possibly NP-complete.
Approximate Queries and Representations for Large Data Sequences
Venue: arXiv cs.DB 2019
Year: 2019

Many new database application domains such as experimental sciences and medicine are characterized by large sequences as their main form of data. Using approximate representation can significantly reduce the required storage and search space. A good choice of representation, can support a broad new class of approximate queries, needed in these domains. These queries are concerned with application dependent features of the data as opposed to the actual sampled points. We introduce a new notion of generalized approximate queries and a general divide and conquer approach that supports them. This approach uses families of real-valued functions as an approximate representation. We present an algorithm for realizing our technique, and the results of applying it to medical cardiology data. (Extended version is available in Tech Report CS-95-03, Dept of Computer Science, Brown University. http://cs.brown.edu/research/pubs/techreports/reports/CS-95-03.html)
Evaluation of IoT-Based Computational Intelligence Tools for DNA Sequence Analysis in Bioinformatics
Venue: arXiv cs.OH 2019
Year: 2019

In contemporary age, Computational Intelligence (CI) performs an essential role in the interpretation of big biological data considering that it could provide all of the molecular biology and DNA sequencing computations. For this purpose, many researchers have attempted to implement different tools in this field and have competed aggressively. Hence, determining the best of them among the enormous number of available tools is not an easy task, selecting the one which accomplishes big data in the concise time and with no error can significantly improve the scientist's contribution in the bioinformatics field. This study uses different analysis and methods such as Fuzzy, Dempster-Shafer, Murphy and Entropy Shannon to provide the most significant and reliable evaluation of IoT-based computational intelligence tools for DNA sequence analysis. The outcomes of this study can be advantageous to the bioinformatics community, researchers and experts in big biological data.
Model Predictive Control Framework for Improving Vehicle Cornering Performance Using Handling Characteristics
Venue: arXiv cs.SY 2019
Year: 2019

This paper proposes a new control strategy to improve vehicle cornering performance in a model predictive control framework. The most distinguishing feature of the proposed method is that the natural handling characteristics of the production vehicle is exploited to reduce the complexity of the conventional control methods. For safety s sake, most production vehicles are built to exhibit an understeer handling characteristics to some extent. By monitoring how much the vehicle is biased into the understeer state, the controller attempts to adjust this amount in a way that improves the vehicle cornering performance. With this particular strategy, an innovative controller can be designed without road friction information, which complicates the conventional control methods. In addition, unlike the conventional controllers, the reference yaw rate that is highly dependent on road friction need not be defined due to the proposed control structure. The optimal control problem is formulated in a model predictive control framework to handle the constraints efficiently, and simulations in various test scenarios illustrate the effectiveness of the proposed approach.
Compact Scene Graphs for Layout Composition and Patch Retrieval
Venue: arXiv cs.CV 2019
Year: 2019

Structured representations such as scene graphs serve as an efficient and compact representation that can be used for downstream rendering or retrieval tasks. However, existing efforts to generate realistic images from scene graphs perform poorly on scene composition for cluttered or complex scenes. We propose two contributions to improve the scene composition. First, we enhance the scene graph representation with heuristic-based relations, which add minimal storage overhead. Second, we use extreme points representation to supervise the learning of the scene composition network. These methods achieve significantly higher performance over existing work (69.0% vs 51.2% in relation score metric). We additionally demonstrate how scene graphs can be used to retrieve pose-constrained image patches that are semantically similar to the source query. Improving structured scene graph representations for rendering or retrieval is an important step towards realistic image generation.
Donkey and Smuggler Optimization Algorithm: A Collaborative Working Approach to Path Finding
Venue: arXiv cs.NE 2019
Year: 2019

Swarm Intelligence is a metaheuristic optimization approach that has become very predominant over the last few decades. These algorithms are inspired by animals' physical behaviors and their evolutionary perceptions. The simplicity of these algorithms allows researchers to simulate different natural phenomena to solve various real-world problems. This paper suggests a novel algorithm called Donkey and Smuggler Optimization Algorithm (DSO). The DSO is inspired by the searching behavior of donkeys. The algorithm imitates transportation behavior such as searching and selecting routes for movement by donkeys in the actual world. Two modes are established for implementing the search behavior and route-selection in this algorithm. These are the Smuggler and Donkeys. In the Smuggler mode, all the possible paths are discovered and the shortest path is then found. In the Donkeys mode, several donkey behaviors are utilized such as Run, Face & Suicide, and Face & Support. Real world data and applications are used to test the algorithm. The experimental results consisted of two parts, firstly, we used the standard benchmark test functions to evaluate the performance of the algorithm in respect to the most popular and the state of the art algorithms. Secondly, the DSO is adapted and implemented on three real-world applications namely; traveling salesman problem, packet routing, and ambulance routing. The experimental results of DSO on these real-world problems are very promising. The results exhibit that the suggested DSO is appropriate to tackle other unfamiliar search spaces and complex problems.
Identifying Points of Interest and Similar Individuals from Raw GPS Data
Venue: arXiv cs.LG 2019
Year: 2019

Smartphones and portable devices have become ubiquitous and part of everyone's life. Due to the fact of its portability, these devices are perfect to record individuals' traces and life-logging generating vast amounts of data at low costs. These data is emerging as a new source for studies in human mobility patterns raising the number of research projects and techniques aiming to analyze and retrieve useful information from it. The aim of this paper is to explore GPS raw data from different individuals in a community and apply data mining algorithms to identify meaningful places in a region and describe user's profiles and its similarities. We evaluate the proposed method with a real-world dataset. The experimental results show that the steps performed to identify points of interest (POIs) and further the similarity between the users are quite satisfactory serving as a supplement for urban planning and social networks.
Two-Timescale Voltage Control in Distribution Grids Using Deep Reinforcement Learning
Venue: arXiv cs.SY 2019
Year: 2019

Modern distribution grids are currently being challenged by frequent and sizable voltage fluctuations, due mainly to the increasing deployment of electric vehicles and renewable generators. Existing approaches to maintaining bus voltage magnitudes within the desired region can cope with either traditional utility-owned devices (e.g., shunt capacitors), or contemporary smart inverters that come with distributed generation units (e.g., photovoltaic plants). The discrete on-off commitment of capacitor units is often configured on an hourly or daily basis, yet smart inverters can be controlled within milliseconds, thus challenging joint control of these two types of assets. In this context, a novel two-timescale voltage regulation scheme is developed for distribution grids by judiciously coupling data-driven with physicsbased optimization. On a faster timescale, say every second, the optimal setpoints of smart inverters are obtained by minimizing instantaneous bus voltage deviations from their nominal values, based on either the exact alternating current power flow model or a linear approximant of it; whereas, on the slower timescale (e.g., every hour), shunt capacitors are configured to minimize the longterm discounted voltage deviations using a deep reinforcement learning algorithm. Extensive numerical tests on a real-world 47- bus distribution network as well as the IEEE 123-bus test feeder using real data corroborate the effectiveness of the novel scheme.
Language Models with Transformers
Venue: arXiv cs.CL 2019
Year: 2019

The Transformer architecture is superior to RNN-based models in computational efficiency. Recently, GPT and BERT demonstrate the efficacy of Transformer models on various NLP tasks using pre-trained language models on large-scale corpora. Surprisingly, these Transformer architectures are suboptimal for language model itself. Neither self-attention nor the positional encoding in the Transformer is able to efficiently incorporate the word-level sequential context crucial to language modeling. In this paper, we explore effective Transformer architectures for language model, including adding additional LSTM layers to better capture the sequential context while still keeping the computation efficient. We propose Coordinate Architecture Search (CAS) to find an effective architecture through iterative refinement of the model. Experimental results on the PTB, WikiText-2, and WikiText-103 show that CAS achieves perplexities between 20.42 and 34.11 on all problems, i.e. on average an improvement of 12.0 perplexity units compared to state-of-the-art LSTMs. The source code is publicly available.
An Analysis of 35+ Million Jobs of Travis CI
Venue: arXiv cs.SE 2019
Year: 2019

Travis CI handles automatically thousands of builds every day to, amongst other things, provide valuable feedback to thousands of open-source developers. In this paper, we investigate Travis CI to firstly understand who is using it, and when they start to use it. Secondly, we investigate how the developers use Travis CI and finally, how frequently the developers change the Travis CI configurations. We observed during our analysis that the main users of Travis CI are corporate users such as Microsoft. And the programming languages used in Travis CI by those users do not follow the same popularity trend than on GitHub, for example, Python is the most popular language on Travis CI, but it is only the third one on GitHub. We also observe that Travis CI is set up on average seven days after the creation of the repository and the jobs are still mainly used (60%) to run tests. And finally, we observe that 7.34% of the commits modify the Travis CI configuration. We share the biggest benchmark of Travis CI jobs (to our knowledge): it contains 35,793,144 jobs from 272,917 different GitHub projects.