OpenRaiser/Intern-Atlas huggingface dataset:
Consistency of Property Specification Patterns with Boolean and Constrained Numerical Signals
Venue: arXiv cs.LO 2017
Year: 2017

Property Specification Patterns (PSPs) have been proposed to solve recurring specification needs, to ease the formalization of requirements, and enable automated verification thereof. In this paper, we extend PSPs by considering Boolean as well as atomic assertions from a constraint system. This extension enables us to reason about functional requirements which could not be captured by basic PSPs. We contribute an encoding from constrained PSPs to LTL formulas, and we show experimental results demonstrating that our approach scales on requirements of realistic size generated using an artificial probabilistic model. Finally, we show that our extension enables us to prove (in)consistency of requirements about an embedded controller for a robotic manipulator.
RLWS: A Reinforcement Learning based GPU Warp Scheduler
Venue: arXiv cs.DC 2017
Year: 2017

The Streaming Multiprocessors (SMs) of a Graphics Processing Unit (GPU) execute instructions from a group of consecutive threads, called warps. At each cycle, an SM schedules a warp from a group of active warps and can context switch among the active warps to hide various stalls. Hence the performance of warp scheduler is critical to the performance of GPU. Several heuristic warp scheduling algorithms have been proposed which work well only for the situations they are designed for. GPU workloads are becoming very diverse in nature and hence one heuristic may not work for all cases. To work well over a diverse range of workloads, which might exhibit hitherto unseen characteristics, a warp scheduling algorithm must be able to adapt on-line. We propose a Reinforcement Learning based Warp Scheduler (RLWS) which learns to schedule warps based on the current state of the core and the long-term benefits of scheduling actions, adapting not only to different types of workloads, but also to different execution phases in each workload. As the design space involving the state variables and the parameters (such as learning and exploration rates, reward and penalty values) used by RLWS is large, we use Genetic Algorithm to identify the useful subset of state variables and parameter values. We evaluated the proposed RLWS using the GPGPU-SIM simulator on a large number of workloads from the Rodinia, Parboil, CUDA-SDK and GPGPU-SIM benchmark suites and compared with other state-of-the-art warp scheduling methods. Our RL based implementation achieved either the best or very close to the best performance in 80\% of kernels with an average speedup of 1.06x over the Loose Round Robin strategy and 1.07x over the Two-Level strategy.
Real-time Text Analytics Pipeline Using Open-source Big Data Tools
Venue: arXiv cs.DC 2017
Year: 2017

Real-time text processing systems are required in many domains to quickly identify patterns, trends, sentiments, and insights. Nowadays, social networks, e-commerce stores, blogs, scientific experiments, and server logs are main sources generating huge text data. However, to process huge text data in real time requires building a data processing pipeline. The main challenge in building such pipeline is to minimize latency to process high-throughput data. In this paper, we explain and evaluate our proposed real-time text processing pipeline using open-source big data tools which minimize the latency to process data streams. Our proposed data processing pipeline is based on Apache Kafka for data ingestion, Apache Spark for in-memory data processing, Apache Cassandra for storing processed results, and D3 JavaScript library for visualization. We evaluate the effectiveness of the proposed pipeline under varying deployment scenarios to perform sentiment analysis using Twitter dataset. Our experimental evaluations show less than a minute latency to process $466,700$ Tweets in $10.7$ minutes when three virtual machines allocated to the proposed pipeline.
Image Registration for the Alignment of Digitized Historical Documents
Venue: arXiv cs.CV 2017
Year: 2017

In this work, we conducted a survey on different registration algorithms and investigated their suitability for hyperspectral historical image registration applications. After the evaluation of different algorithms, we choose an intensity based registration algorithm with a curved transformation model. For the transformation model, we select cubic B-splines since they should be capable to cope with all non-rigid deformations in our hyperspectral images. From a number of similarity measures, we found that residual complexity and localized mutual information are well suited for the task at hand. In our evaluation, both measures show an acceptable performance in handling all difficulties, e.g., capture range, non-stationary and spatially varying intensity distortions or multi-modality that occur in our application.
Hierarchical Bloom Filter Trees for Approximate Matching
Venue: arXiv cs.CR 2017
Year: 2017

Bytewise approximate matching algorithms have in recent years shown significant promise in de- tecting files that are similar at the byte level. This is very useful for digital forensic investigators, who are regularly faced with the problem of searching through a seized device for pertinent data. A common scenario is where an investigator is in possession of a collection of "known-illegal" files (e.g. a collection of child abuse material) and wishes to find whether copies of these are stored on the seized device. Approximate matching addresses shortcomings in traditional hashing, which can only find identical files, by also being able to deal with cases of merged files, embedded files, partial files, or if a file has been changed in any way. Most approximate matching algorithms work by comparing pairs of files, which is not a scalable approach when faced with large corpora. This paper demonstrates the effectiveness of using a "Hierarchical Bloom Filter Tree" (HBFT) data structure to reduce the running time of collection-against-collection matching, with a specific focus on the MRSH-v2 algorithm. Three experiments are discussed, which explore the effects of different configurations of HBFTs. The proposed approach dramatically reduces the number of pairwise comparisons required, and demonstrates substantial speed gains, while maintaining effectiveness.
Ellipsoid Method for Linear Programming made simple
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, ellipsoid method for linear programming is derived using only minimal knowledge of algebra and matrices. Unfortunately, most authors first describe the algorithm, then later prove its correctness, which requires a good knowledge of linear algebra.
Energy-Efficient Non-Orthogonal Transmission under Reliability and Finite Blocklength Constraints
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates an energy-efficient non-orthogonal transmission design problem for two downlink receivers that have strict reliability and finite blocklength (latency) constraints. The Shannon capacity formula widely used in traditional designs needs the assumption of infinite blocklength and thus is no longer appropriate. We adopt the newly finite blocklength coding capacity formula for explicitly specifying the trade-off between reliability and code blocklength. However, conventional successive interference cancellation (SIC) may become infeasible due to heterogeneous blocklengths. We thus consider several scenarios with different channel conditions and with/without SIC. By carefully examining the problem structure, we present in closed-form the optimal power and code blocklength for energy-efficient transmissions. Simulation results provide interesting insights into conditions for which non-orthogonal transmission is more energy efficient than the orthogonal transmission such as TDMA.
Mathematics of Deep Learning
Venue: arXiv cs.LG 2017
Year: 2017

Recently there has been a dramatic increase in the performance of recognition systems due to the introduction of deep architectures for representation learning and classification. However, the mathematical reasons for this success remain elusive. This tutorial will review recent work that aims to provide a mathematical justification for several properties of deep networks, such as global optimality, geometric stability, and invariance of the learned representations.
Error Performance of Wireless Powered Cognitive Relay Networks with Interference Alignment
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies a two-hop decode-and-forward underlay cognitive radio system with interference alignment technique. An energy-constrained relay node harvests the energy from the interference signals through a power-splitting (PS) relaying protocol. Firstly, the beamforming matrices design for the primary and secondary networks is demonstrated. Then, a bit error rate (BER) performance of the system under perfect and imperfect channel state information (CSI) scenarios for PS protocol is calculated. Finally, the impact of the CSI mismatch parameters on the BER performance is simulated.
On the Capacity of Wireless Powered Cognitive Relay Network with Interference Alignment
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, a two-hop decode-and-forward cognitive radio system with deployed interference alignment is considered. The relay node is energy-constrained and scavenges the energy from the interference signals. In the literature, there are two main energy harvesting protocols, namely, time-switching relaying and power-splitting relaying. We first demonstrate how to design the beamforming matrices for the considered primary and secondary networks. Then, the system capacity under perfect and imperfect channel state information scenarios, considering different portions of time-switching and power-splitting protocols, is estimated.
Reasoning in Systems with Elements that Randomly Switch Characteristics
Venue: arXiv cs.AI 2017
Year: 2017

We examine the issue of stability of probability in reasoning about complex systems with uncertainty in structure. Normally, propositions are viewed as probability functions on an abstract random graph where it is implicitly assumed that the nodes of the graph have stable properties. But what if some of the nodes change their characteristics? This is a situation that cannot be covered by abstractions of either static or dynamic sets when these changes take place at regular intervals. We propose the use of sets with elements that change, and modular forms are proposed to account for one type of such change. An expression for the dependence of the mean on the probability of the switching elements has been determined. The system is also analyzed from the perspective of decision between different hypotheses. Such sets are likely to be of use in complex system queries and in analysis of surveys.
FFT-Based Deep Learning Deployment in Embedded Systems
Venue: arXiv cs.LG 2017
Year: 2017

Deep learning has delivered its powerfulness in many application domains, especially in image and speech recognition. As the backbone of deep learning, deep neural networks (DNNs) consist of multiple layers of various types with hundreds to thousands of neurons. Embedded platforms are now becoming essential for deep learning deployment due to their portability, versatility, and energy efficiency. The large model size of DNNs, while providing excellent accuracy, also burdens the embedded platforms with intensive computation and storage. Researchers have investigated on reducing DNN model size with negligible accuracy loss. This work proposes a Fast Fourier Transform (FFT)-based DNN training and inference model suitable for embedded platforms with reduced asymptotic complexity of both computation and storage, making our approach distinguished from existing approaches. We develop the training and inference algorithms based on FFT as the computing kernel and deploy the FFT-based inference model on embedded platforms achieving extraordinary processing speed.
Enhanced Characterness for Text Detection in the Wild
Venue: arXiv cs.CV 2017
Year: 2017

Text spotting is an interesting research problem as text may appear at any random place and may occur in various forms. Moreover, ability to detect text opens the horizons for improving many advanced computer vision problems. In this paper, we propose a novel language agnostic text detection method utilizing edge enhanced Maximally Stable Extremal Regions in natural scenes by defining strong characterness measures. We show that a simple combination of characterness cues help in rejecting the non text regions. These regions are further fine-tuned for rejecting the non-textual neighbor regions. Comprehensive evaluation of the proposed scheme shows that it provides comparative to better generalization performance to the traditional methods for this task.
Cross-layer Design in Cognitive Radio Standards
Venue: arXiv cs.NI 2017
Year: 2017

The growing demand for wireless applications and services on the one hand, and limited available radio spectrum on the other hand have made cognitive radio (CR) a promising solution for future mobile networks. It has attracted considerable attention by academia and industry since its introduction in 1999 and several relevant standards have been developed within the last decade. Cognitive radio is based on four main functions, spanning across more than one layer of OSI model. Therefore, solutions based on cognitive radio technology require cross layer (CL) designs for optimum performance. This article briefly reviews the basics of cognitive radio technology as an introduction and highlights the need for cross layer design in systems deploying CR technology. Then some of the published standards with CL characteristics are outlined in a later section, and in the final section some research examples of cross layer design ideas based on the existing CR standards conclude this article.
Greedy spanners are optimal in doubling metrics
Venue: arXiv cs.CG 2017
Year: 2017

We show that the greedy spanner algorithm constructs a $(1+ε)$-spanner of weight $ε^{-O(d)}w(\mathrm{MST})$ for a point set in metrics of doubling dimension $d$, resolving an open problem posed by Gottlieb. Our result generalizes the result by Narasimhan and Smid who showed that a point set in $d$-dimension Euclidean space has a $(1+ε)$-spanner of weight at most $ε^{-O(d)}w(\mathrm{MST})$. Our proof only uses the packing property of doubling metrics and thus implies a much simpler proof for the same result in Euclidean space.
Learning to Navigate by Growing Deep Networks
Venue: arXiv cs.RO 2017
Year: 2017

Adaptability is central to autonomy. Intuitively, for high-dimensional learning problems such as navigating based on vision, internal models with higher complexity allow to accurately encode the information available. However, most learning methods rely on models with a fixed structure and complexity. In this paper, we present a self-supervised framework for robots to learn to navigate, without any prior knowledge of the environment, by incrementally building the structure of a deep network as new data becomes available. Our framework captures images from a monocular camera and self labels the images to continuously train and predict actions from a computationally efficient adaptive deep architecture based on Autoencoders (AE), in a self-supervised fashion. The deep architecture, named Reinforced Adaptive Denoising Autoencoders (RA-DAE), uses reinforcement learning to dynamically change the network structure by adding or removing neurons. Experiments were conducted in simulation and real-world indoor and outdoor environments to assess the potential of self-supervised navigation. RA-DAE demonstrates better performance than equivalent non-adaptive deep learning alternatives and can continue to expand its knowledge, trading-off past and present information.
Inequalities, Preferences and Rankings in US Sports Coach Hiring Networks
Venue: arXiv cs.SI 2017
Year: 2017

Hiring a head coach of a college sports team is vital which will definitely have a great influence on the later development of the team. However, a lot of attention has been focused on each coach's individual features. A systematic and quantitative analysis of the whole coach hiring market is lacking. In a coach hiring network, the coaches are actually voting with their feet. It is interesting to analyze what factors are affecting the "footprint" left by those head coaches. In this paper, we collect more than 12,000 head coach hiring records in two different popular sports from the NCAA. Using network-based methods, we build the coach hiring network in the NCAA men's basketball and football. We find that: (1).the coach hiring network is of great inequality in coach production with a Gini coefficient close to 0.60. (2).coaches prefer to work within the same geographical region and the same division to their alma maters'. (3).the coach production rankings we calculated using network-based methods are generally correlated to the authoritative rankings, but also show disaccord in specific time period. The results provide us a novel view and better understanding of the coach hiring market in the NCAA and shed new light on the coach hiring system.
Detection and Attention: Diagnosing Pulmonary Lung Cancer from CT by Imitating Physicians
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes a novel and efficient method to build a Computer-Aided Diagnoses (CAD) system for lung nodule detection based on Computed Tomography (CT). This task was treated as an Object Detection on Video (VID) problem by imitating how a radiologist reads CT scans. A lung nodule detector was trained to automatically learn nodule features from still images to detect lung nodule candidates with both high recall and accuracy. Unlike previous work which used 3-dimensional information around the nodule to reduce false positives, we propose two simple but efficient methods, Multi-slice propagation (MSP) and Motionless-guide suppression (MLGS), which analyze sequence information of CT scans to reduce false negatives and suppress false positives. We evaluated our method in open-source LUNA16 dataset which contains 888 CT scans, and obtained state-of-the-art result (Free-Response Receiver Operating Characteristic score of 0.892) with detection speed (end to end within 20 seconds per patient on a single NVidia GTX 1080) much higher than existing methods.
DLR : Toward a deep learned rhythmic representation for music content analysis
Venue: arXiv cs.SD 2017
Year: 2017

In the use of deep neural networks, it is crucial to provide appropriate input representations for the network to learn from. In this paper, we propose an approach to learn a representation that focus on rhythmic representation which is named as DLR (Deep Learning Rhythmic representation). The proposed approach aims to learn DLR from the raw audio signal and use it for other music informatics tasks. A 1-dimensional convolutional network is utilised in the learning of DLR. In the experiment, we present the results from the source task and the target task as well as visualisations of DLRs. The results reveals that DLR provides compact rhythmic information which can be used on multi-tagging task.
Passing the Brazilian OAB Exam: data preparation and some experiments
Venue: arXiv cs.CL 2017
Year: 2017

In Brazil, all legal professionals must demonstrate their knowledge of the law and its application by passing the OAB exams, the national bar exams. The OAB exams therefore provide an excellent benchmark for the performance of legal information systems since passing the exam would arguably signal that the system has acquired capacity of legal reasoning comparable to that of a human lawyer. This article describes the construction of a new data set and some preliminary experiments on it, treating the problem of finding the justification for the answers to questions. The results provide a baseline performance measure against which to evaluate future improvements. We discuss the reasons to the poor performance and propose next steps.
Optimized Interface Diversity for Ultra-Reliable Low Latency Communication (URLLC)
Venue: arXiv cs.IT 2017
Year: 2017

An important ingredient of the future 5G systems will be Ultra-Reliable Low-Latency Communication (URLLC). A way to offer URLLC without intervention in the baseband/PHY layer design is to use \emph{interface diversity} and integrate multiple communication interfaces, each interface based on a different technology. Our approach is to use coding to seamlessly distribute coded payload and redundancy data across multiple available communication interfaces. We formulate an optimization problem to find the payload allocation weights that maximize the reliability at specific target latency values. By considering different scenarios, we find that optimized strategies can significantly outperform $k$-out-of-$n$ strategies, where the latter do not account for the characteristics of the different interfaces. Our approach is supported by experimental results.
Rasa: Open Source Language Understanding and Dialogue Management
Venue: arXiv cs.CL 2017
Year: 2017

We introduce a pair of tools, Rasa NLU and Rasa Core, which are open source python libraries for building conversational software. Their purpose is to make machine-learning based dialogue management and language understanding accessible to non-specialist software developers. In terms of design philosophy, we aim for ease of use, and bootstrapping from minimal (or no) initial training data. Both packages are extensively documented and ship with a comprehensive suite of tests. The code is available at https://github.com/RasaHQ/
Cellular Automata Applications in Shortest Path Problem
Venue: arXiv cs.CG 2017
Year: 2017

Cellular Automata (CAs) are computational models that can capture the essential features of systems in which global behavior emerges from the collective effect of simple components, which interact locally. During the last decades, CAs have been extensively used for mimicking several natural processes and systems to find fine solutions in many complex hard to solve computer science and engineering problems. Among them, the shortest path problem is one of the most pronounced and highly studied problems that scientists have been trying to tackle by using a plethora of methodologies and even unconventional approaches. The proposed solutions are mainly justified by their ability to provide a correct solution in a better time complexity than the renowned Dijkstra's algorithm. Although there is a wide variety regarding the algorithmic complexity of the algorithms suggested, spanning from simplistic graph traversal algorithms to complex nature inspired and bio-mimicking algorithms, in this chapter we focus on the successful application of CAs to shortest path problem as found in various diverse disciplines like computer science, swarm robotics, computer networks, decision science and biomimicking of biological organisms' behaviour. In particular, an introduction on the first CA-based algorithm tackling the shortest path problem is provided in detail. After the short presentation of shortest path algorithms arriving from the relaxization of the CAs principles, the application of the CA-based shortest path definition on the coordinated motion of swarm robotics is also introduced. Moreover, the CA based application of shortest path finding in computer networks is presented in brief. Finally, a CA that models exactly the behavior of a biological organism, namely the Physarum's behavior, finding the minimum-length path between two points in a labyrinth is given.