OpenRaiser/Intern-Atlas huggingface dataset:
Targeted Synthesis for Programming with Data Invariants
Venue: arXiv cs.PL 2019
Year: 2019

Programmers frequently maintain implicit data invariants, which are relations between different data structures in a program. Traditionally, such invariants are manually enforced and checked by programmers. This ad-hoc practice is difficult because the programmer must manually account for all the locations and configurations that break an invariant. Moreover, implicit invariants are brittle under code-evolution: when the invariants and data structures change, the programmer must repeat the process of manually repairing all of the code locations where invariants are violated. A much better approach is to introduce data invariants as a language feature and rely on language support to maintain invariants. To handle this challenge, we introduce Targeted Synthesis, a technique for integrating data invariants with invariant-agnostic imperative code at compile-time. This technique is nontrivial due to the complex structure of both invariant specifications, as well as general imperative code. The key insight is to take a language co-design approach involving both the language of data invariants, as well as the imperative language. We leverage this insight to produce two high-level results: first, we support a language with iterators without requiring general quantified reasoning, and second, we infer complicated invariant-preserving patches. We evaluate these claims through a language termed Spyder, a core calculus of data invariants over imperative iterator programs. We evaluate the expressiveness and performance of Spyder on a variety of programs inspired by web applications, and we find that Spyder efficiently compiles and maintains data invariants.
Improved bounds for the excluded-minor approximation of treedepth
Venue: arXiv cs.DM 2019
Year: 2019

Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant $C$ such that for every positive integers $a,b$ and a graph $G$, if the treedepth of $G$ is at least $Cab$, then the treewidth of $G$ is at least $a$ or $G$ contains a subcubic (i.e., of maximum degree at most $3$) tree of treedepth at least $b$ as a subgraph. As a direct corollary, we obtain that every graph of treedepth $Ω(k^3)$ is either of treewidth at least $k$, contains a subdivision of full binary tree of depth $k$, or contains a path of length $2^k$. This improves the bound of $Ω(k^5 \log^2 k)$ of Kawarabayashi and Rossman [SODA 2018]. We also show an application of our techniques for approximation algorithms of treedepth: given a graph $G$ of treedepth $k$ and treewidth $t$, one can in polynomial time compute a treedepth decomposition of $G$ of width $\mathcal{O}(kt \log^{3/2} t)$. This improves upon a bound of $\mathcal{O}(kt^2 \log t)$ stemming from a tradeoff between known results. The main technical ingredient in our result is a proof that every tree of treedepth $d$ contains a subcubic subtree of treedepth at least $d \cdot \log_3 ((1+\sqrt{5})/2)$.
Anomaly Detection in Traffic Scenes via Spatial-aware Motion Reconstruction
Venue: arXiv cs.CV 2019
Year: 2019

Anomaly detection from a driver's perspective when driving is important to autonomous vehicles. As a part of Advanced Driver Assistance Systems (ADAS), it can remind the driver about dangers timely. Compared with traditional studied scenes such as the university campus and market surveillance videos, it is difficult to detect abnormal event from a driver's perspective due to camera waggle, abidingly moving background, drastic change of vehicle velocity, etc. To tackle these specific problems, this paper proposes a spatial localization constrained sparse coding approach for anomaly detection in traffic scenes, which firstly measures the abnormality of motion orientation and magnitude respectively and then fuses these two aspects to obtain a robust detection result. The main contributions are threefold: 1) This work describes the motion orientation and magnitude of the object respectively in a new way, which is demonstrated to be better than the traditional motion descriptors. 2) The spatial localization of object is taken into account of the sparse reconstruction framework, which utilizes the scene's structural information and outperforms the conventional sparse coding methods. 3) Results of motion orientation and magnitude are adaptively weighted and fused by a Bayesian model, which makes the proposed method more robust and handle more kinds of abnormal events. The efficiency and effectiveness of the proposed method are validated by testing on nine difficult video sequences captured by ourselves. Observed from the experimental results, the proposed method is more effective and efficient than the popular competitors, and yields a higher performance.
Latency Bounds of Packet-Based Fronthaul for Cloud-RAN with Functionality Split
Venue: arXiv cs.NI 2019
Year: 2019

The emerging Cloud-RAN architecture within the fifth generation (5G) of wireless networks plays a vital role in enabling higher flexibility and granularity. On the other hand, Cloud-RAN architecture introduces an additional link between the central, cloudified unit and the distributed radio unit, namely fronthaul (FH). Therefore, the foreseen reliability and latency for 5G services should also be provisioned over the FH link. In this paper, focusing on Ethernet as FH, we present a reliable packet-based FH communication and demonstrate the upper and lower bounds of latency that can be offered. These bounds yield insights into the trade-off between reliability and latency, and enable the architecture design through choice of splitting point, focusing on high layer split between PDCP and RLC and low layer split between MAC and PHY, under different FH bandwidth and traffic properties. Presented model is then analyzed both numerically and through simulation, with two classes of 5G services that are ultra reliable low latency (URLL) and enhanced mobile broadband (eMBB).
Physical Layer Performance Evaluation of Wireless Infrared-based LiFi Uplink
Venue: arXiv cs.IT 2019
Year: 2019

LiFi (light-fidelity) is recognised as a promising technology for the next generation wireless access network. However, little research effort has been spent on the uplink transmission system in LiFi networks. In this paper, an analytical framework for the performance analysis of an wireless infrared-based LiFi uplink at system level is presented. This work focuses on the performance of a single user who is randomly located in a network. Many important factors in practice are taken into account, such as front-end characteristics, channel path loss, link blockage and user device random orientations. In particular, accurate analytical expressions for the statistics of optical channel path loss has been derived. Based on this path loss statistics, the distribution of signal-to-noise ratio (SNR) and the average achievable data rate are evaluated. A channel factor is defined as a quantity which only depends on the used devices, optical channel and noise power spectral density function (PSD). The result shows that with commercial front-end elements, an average data rate of up to 250 Mbps is achievable.
Learning Restricted Regular Expressions with Interleaving
Venue: arXiv cs.DB 2019
Year: 2019

The advantages for the presence of an XML schema for XML documents are numerous. However, many XML documents in practice are not accompanied by a schema or by a valid schema. Relax NG is a popular and powerful schema language, which supports the unconstrained interleaving operator. Focusing on the inference of Relax NG, we propose a new subclass of regular expressions with interleaving and design a polynomial inference algorithm. Then we conducted a series of experiments based on large-scale real data and on three XML data corpora, and experimental results show that our subclass has a better practicality than previous ones, and the regular expressions inferred by our algorithm are more precise.
Fine-grained Entity Recognition with Reduced False Negatives and Large Type Coverage
Venue: arXiv cs.CL 2019
Year: 2019

Fine-grained Entity Recognition (FgER) is the task of detecting and classifying entity mentions to a large set of types spanning diverse domains such as biomedical, finance and sports. We observe that when the type set spans several domains, detection of entity mention becomes a limitation for supervised learning models. The primary reason being lack of dataset where entity boundaries are properly annotated while covering a large spectrum of entity types. Our work directly addresses this issue. We propose Heuristics Allied with Distant Supervision (HAnDS) framework to automatically construct a quality dataset suitable for the FgER task. HAnDS framework exploits the high interlink among Wikipedia and Freebase in a pipelined manner, reducing annotation errors introduced by naively using distant supervision approach. Using HAnDS framework, we create two datasets, one suitable for building FgER systems recognizing up to 118 entity types based on the FIGER type hierarchy and another for up to 1115 entity types based on the TypeNet hierarchy. Our extensive empirical experimentation warrants the quality of the generated datasets. Along with this, we also provide a manually annotated dataset for benchmarking FgER systems.
On the Construction of $G_N$-coset Codes for Parallel Decoding
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we propose a type of $G_N$-coset codes for a highly parallel stage-permuted turbo-like decoder. The decoder exploits the equivalence between two stage-permuted factor graphs of $G_N$-coset codes. Specifically, the inner codes of a $G_N$-coset code consist of independent component codes, thus are decoded in parallel. The extrinsic information of the code bits is obtained and iteratively exchanged between the two graphs until convergence. Accordingly, we explore a heuristic and flexible code construction method (information set selection) for various information lengths and coding rates. Simulations show that the proposed $G_N$-coset codes could achieve a coding performance comparable with polar codes but enjoy higher decoding parallelism.
Test Selection for Deep Learning Systems
Venue: arXiv cs.LG 2019
Year: 2019

Testing of deep learning models is challenging due to the excessive number and complexity of computations involved. As a result, test data selection is performed manually and in an ad hoc way. This raises the question of how we can automatically select candidate test data to test deep learning models. Recent research has focused on adapting test selection metrics from code-based software testing (such as coverage) to deep learning. However, deep learning models have different attributes from code such as spread of computations across the entire network reflecting training data properties, balance of neuron weights and redundancy (use of many more neurons than needed). Such differences make code-based metrics inappropriate to select data that can challenge the models (can trigger misclassification). We thus propose a set of test selection metrics based on the notion of model uncertainty (model confidence on specific inputs). Intuitively, the more uncertain we are about a candidate sample, the more likely it is that this sample triggers a misclassification. Similarly, the samples for which we are the most uncertain, are the most informative and should be used to improve the model by retraining. We evaluate these metrics on two widely-used image classification problems involving real and artificial (adversarial) data. We show that uncertainty-based metrics have a strong ability to select data that are misclassified and lead to major improvement in classification accuracy during retraining: up to 80% more gain than random selection and other state-of-the-art metrics on one dataset and up to 29% on the other.
Automatic Emotion Recognition (AER) System based on Two-Level Ensemble of Lightweight Deep CNN Models
Venue: arXiv cs.LG 2019
Year: 2019

Emotions play a crucial role in human interaction, health care and security investigations and monitoring. Automatic emotion recognition (AER) using electroencephalogram (EEG) signals is an effective method for decoding the real emotions, which are independent of body gestures, but it is a challenging problem. Several automatic emotion recognition systems have been proposed, which are based on traditional hand-engineered approaches and their performances are very poor. Motivated by the outstanding performance of deep learning (DL) in many recognition tasks, we introduce an AER system (Deep-AER) based on EEG brain signals using DL. A DL model involves a large number of learnable parameters, and its training needs a large dataset of EEG signals, which is difficult to acquire for AER problem. To overcome this problem, we proposed a lightweight pyramidal one-dimensional convolutional neural network (LP-1D-CNN) model, which involves a small number of learnable parameters. Using LP-1D-CNN, we build a two level ensemble model. In the first level of the ensemble, each channel is scanned incrementally by LP-1D-CNN to generate predictions, which are fused using majority vote. The second level of the ensemble combines the predictions of all channels of an EEG signal using majority vote for detecting the emotion state. We validated the effectiveness and robustness of Deep-AER using DEAP, a benchmark dataset for emotion recognition research. The results indicate that FRONT plays dominant role in AER and over this region, Deep-AER achieved the accuracies of 98.43% and 97.65% for two AER problems, i.e., high valence vs low valence (HV vs LV) and high arousal vs low arousal (HA vs LA), respectively. The comparison reveals that Deep-AER outperforms the state-of-the-art systems with large margin. The Deep-AER system will be helpful in monitoring for health care and security investigations.
Multimodal Classification of Urban Micro-Events
Venue: arXiv cs.LG 2019
Year: 2019

In this paper we seek methods to effectively detect urban micro-events. Urban micro-events are events which occur in cities, have limited geographical coverage and typically affect only a small group of citizens. Because of their scale these are difficult to identify in most data sources. However, by using citizen sensing to gather data, detecting them becomes feasible. The data gathered by citizen sensing is often multimodal and, as a consequence, the information required to detect urban micro-events is distributed over multiple modalities. This makes it essential to have a classifier capable of combining them. In this paper we explore several methods of creating such a classifier, including early, late, hybrid fusion and representation learning using multimodal graphs. We evaluate performance on a real world dataset obtained from a live citizen reporting system. We show that a multimodal approach yields higher performance than unimodal alternatives. Furthermore, we demonstrate that our hybrid combination of early and late fusion with multimodal embeddings performs best in classification of urban micro-events.
How to Find New Characteristic-Dependent Linear Rank Inequalities using Binary Matrices as a Guide
Venue: arXiv cs.IT 2019
Year: 2019

In Linear Algebra over finite fields, a characteristic-dependent linear rank inequality is a linear inequality that holds by ranks of subspaces of a vector space over a finite field of determined characteristic, and does not in general hold over other characteristics. In this paper, we show a method to produce these inequalities using binary matrices with suitable ranks over different fields. In particular, for each $n\geq7$, we produce $2\left\lfloor \frac{n-1}{2}\right\rfloor -4$ characteristic-dependent linear rank inequalities over $n$ variables. Many of the inequalities obtained are new but some of them imply the inequalities presented in [1,9].
Predicting How to Distribute Work Between Algorithms and Humans to Segment an Image Batch
Venue: arXiv cs.CV 2019
Year: 2019

Foreground object segmentation is a critical step for many image analysis tasks. While automated methods can produce high-quality results, their failures disappoint users in need of practical solutions. We propose a resource allocation framework for predicting how best to allocate a fixed budget of human annotation effort in order to collect higher quality segmentations for a given batch of images and automated methods. The framework is based on a prediction module that estimates the quality of given algorithm-drawn segmentations. We demonstrate the value of the framework for two novel tasks related to predicting how to distribute annotation efforts between algorithms and humans. Specifically, we develop two systems that automatically decide, for a batch of images, when to recruit humans versus computers to create 1) coarse segmentations required to initialize segmentation tools and 2) final, fine-grained segmentations. Experiments demonstrate the advantage of relying on a mix of human and computer efforts over relying on either resource alone for segmenting objects in images coming from three diverse modalities (visible, phase contrast microscopy, and fluorescence microscopy).
On the Use of ArXiv as a Dataset
Venue: arXiv cs.IR 2019
Year: 2019

The arXiv has collected 1.5 million pre-print articles over 28 years, hosting literature from scientific fields including Physics, Mathematics, and Computer Science. Each pre-print features text, figures, authors, citations, categories, and other metadata. These rich, multi-modal features, combined with the natural graph structure---created by citation, affiliation, and co-authorship---makes the arXiv an exciting candidate for benchmarking next-generation models. Here we take the first necessary steps toward this goal, by providing a pipeline which standardizes and simplifies access to the arXiv's publicly available data. We use this pipeline to extract and analyze a 6.7 million edge citation graph, with an 11 billion word corpus of full-text research articles. We present some baseline classification results, and motivate application of more exciting generative graph models.
FastContext: an efficient and scalable implementation of the ConText algorithm
Venue: arXiv cs.CL 2019
Year: 2019

Objective: To develop and evaluate FastContext, an efficient, scalable implementation of the ConText algorithm suitable for very large-scale clinical natural language processing. Background: The ConText algorithm performs with state-of-art accuracy in detecting the experiencer, negation status, and temporality of concept mentions in clinical narratives. However, the speed limitation of its current implementations hinders its use in big data processing. Methods: We developed FastContext through hashing the ConText's rules, then compared its speed and accuracy with JavaConText and GeneralConText, two widely used Java implementations. Results: FastContext ran two orders of magnitude faster and was less decelerated by rule increase than the other two implementations used in this study for comparison. Additionally, FastContext consistently gained accuracy improvement as the rules increased (the desired outcome of adding new rules), while the other two implementations did not. Conclusions: FastContext is an efficient, scalable implementation of the popular ConText algorithm, suitable for natural language applications on very large clinical corpora.
Separate Chaining Meets Compact Hashing
Venue: arXiv cs.DS 2019
Year: 2019

While separate chaining is a common strategy for resolving collisions in a hash table taught in most textbooks, compact hashing is a less common technique for saving space when hashing integers whose domain is relatively small with respect to the problem size. It is widely believed that hash tables waste a considerable amount of memory, as they either leave allocated space untouched (open addressing) or store additional pointers (separate chaining). For the former, Cleary introduced the compact hashing technique that stores only a part of a key to save space. However, as can be seen by the line of research focusing on compact hash tables with open addressing, there is additional information, called displacement, required for restoring a key. There are several representations of this displacement information with different space and time trade-offs. In this article, we introduce a separate chaining hash table that applies the compact hashing technique without the need for the displacement information. Practical evaluations reveal that insertions in this hash table are faster or use less space than all previously known compact hash tables on modern computer architectures when storing sufficiently large satellite data.
Surface Type Classification for Autonomous Robot Indoor Navigation
Venue: arXiv cs.LG 2019
Year: 2019

In this work we describe the preparation of a time series dataset of inertial measurements for determining the surface type under a wheeled robot. The data consists of over 7600 labeled time series samples, with the corresponding surface type annotation. This data was used in two public competitions with over 1500 participant in total. Additionally, we describe the performance of state-of-art deep learning models for time series classification, as well as propose a baseline model based on an ensemble of machine learning methods. The baseline achieves an accuracy of over 68% with our nine-category dataset.
Characterizing Code Clones in the Ethereum Smart Contract Ecosystem
Venue: arXiv cs.CR 2019
Year: 2019

In this paper, we present the first large-scale and systematic study to characterize the code reuse practice in the Ethereum smart contract ecosystem. We first performed a detailed similarity comparison study on a dataset of 10 million contracts we had harvested, and then we further conducted a qualitative analysis to characterize the diversity of the ecosystem, understand the correlation between code reuse and vulnerabilities, and detect the plagiarist DApps. Our analysis revealed that over 96% of the contracts had duplicates, while a large number of them were similar, which suggests that the ecosystem is highly homogeneous. Our results also suggested that roughly 9.7% of the similar contract pairs have exactly the same vulnerabilities, which we assume were introduced by code clones. In addition, we identified 41 DApps clusters, involving 73 plagiarized DApps which had caused huge financial loss to the original creators, accounting for 1/3 of the original market volume.