OpenRaiser/Intern-Atlas huggingface dataset:
cuTT: A High-Performance Tensor Transpose Library for CUDA Compatible GPUs
Venue: arXiv cs.MS 2017
Year: 2017

We introduce the CUDA Tensor Transpose (cuTT) library that implements high-performance tensor transposes for NVIDIA GPUs with Kepler and above architectures. cuTT achieves high performance by (a) utilizing two GPU-optimized transpose algorithms that both use a shared memory buffer in order to reduce global memory access scatter, and by (b) computing memory positions of tensor elements using a thread-parallel algorithm. We evaluate the performance of cuTT on a variety of benchmarks with tensor ranks ranging from 2 to 12 and show that cuTT performance is independent of the tensor rank and that it performs no worse than an approach based on code generation. We develop a heuristic scheme for choosing the optimal parameters for tensor transpose algorithms by implementing an analytical GPU performance model that can be used at runtime without need for performance measurements or profiling. Finally, by integrating cuTT into the tensor algebra library TAL-SH, we significantly reduce the tensor transpose overhead in tensor contractions, achieving as low as just one percent overhead for arithmetically intensive tensor contractions.
Compressing DMA Engine: Leveraging Activation Sparsity for Training Deep Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Popular deep learning frameworks require users to fine-tune their memory usage so that the training data of a deep neural network (DNN) fits within the GPU physical memory. Prior work tries to address this restriction by virtualizing the memory usage of DNNs, enabling both CPU and GPU memory to be utilized for memory allocations. Despite its merits, virtualizing memory can incur significant performance overheads when the time needed to copy data back and forth from CPU memory is higher than the latency to perform the computations required for DNN forward and backward propagation. We introduce a high-performance virtualization strategy based on a "compressing DMA engine" (cDMA) that drastically reduces the size of the data structures that are targeted for CPU-side allocations. The cDMA engine offers an average 2.6x (maximum 13.8x) compression ratio by exploiting the sparsity inherent in offloaded data, improving the performance of virtualized DNNs by an average 32% (maximum 61%).
Learning Hierarchical Shape Segmentation and Labeling from Online Repositories
Venue: arXiv cs.GR 2017
Year: 2017

We propose a method for converting geometric shapes into hierarchically segmented parts with part labels. Our key idea is to train category-specific models from the scene graphs and part names that accompany 3D shapes in public repositories. These freely-available annotations represent an enormous, untapped source of information on geometry. However, because the models and corresponding scene graphs are created by a wide range of modelers with different levels of expertise, modeling tools, and objectives, these models have very inconsistent segmentations and hierarchies with sparse and noisy textual tags. Our method involves two analysis steps. First, we perform a joint optimization to simultaneously cluster and label parts in the database while also inferring a canonical tag dictionary and part hierarchy. We then use this labeled data to train a method for hierarchical segmentation and labeling of new 3D shapes. We demonstrate that our method can mine complex information, detecting hierarchies in man-made objects and their constituent parts, obtaining finer scale details than existing alternatives. We also show that, by performing domain transfer using a few supervised examples, our technique outperforms fully-supervised techniques that require hundreds of manually-labeled models.
On the Necessity of Superparametric Geometry Representation for Discontinuous Galerkin Methods on Domains with Curved Boundaries
Venue: arXiv cs.NA 2017
Year: 2017

We provide numerical evidence demonstrating the necessity of employing a superparametric geometry representation in order to obtain optimal convergence orders on two-dimensional domains with curved boundaries when solving the Euler equations using Discontinuous Galerkin methods. However, concerning the obtention of optimal convergence orders for the Navier-Stokes equations, we demonstrate numerically that the use of isoparametric geometry representation is sufficient for the case considered here.
Dissipation of stop-and-go waves via control of autonomous vehicles: Field experiments
Venue: arXiv cs.SY 2017
Year: 2017

Traffic waves are phenomena that emerge when the vehicular density exceeds a critical threshold. Considering the presence of increasingly automated vehicles in the traffic stream, a number of research activities have focused on the influence of automated vehicles on the bulk traffic flow. In the present article, we demonstrate experimentally that intelligent control of an autonomous vehicle is able to dampen stop-and-go waves that can arise even in the absence of geometric or lane changing triggers. Precisely, our experiments on a circular track with more than 20 vehicles show that traffic waves emerge consistently, and that they can be dampened by controlling the velocity of a single vehicle in the flow. We compare metrics for velocity, braking events, and fuel economy across experiments. These experimental findings suggest a paradigm shift in traffic management: flow control will be possible via a few mobile actuators (less than 5%) long before a majority of vehicles have autonomous capabilities.
Near-optimal linear decision trees for k-SUM and related problems
Venue: arXiv cs.CG 2017
Year: 2017

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry. For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries. Moreover, the queries we use are comparison queries, which compare the sums of two $k$-subsets; when viewed as linear queries, comparison queries are $2k$-sparse and have only $\{-1,0,1\}$ coefficients. We give similar constructions for sorting sumsets $A+B$ and for solving the SUBSET-SUM problem, both with optimal number of queries, up to poly-logarithmic terms. Our constructions are based on the notion of "inference dimension", recently introduced by the authors in the context of active classification with comparison queries. This can be viewed as another contribution to the fruitful link between machine learning and discrete geometry, which goes back to the discovery of the VC dimension.
Evolutionary learning of fire fighting strategies
Venue: arXiv cs.NE 2017
Year: 2017

The dynamic problem of enclosing an expanding fire can be modelled by a discrete variant in a grid graph. While the fire expands to all neighbouring cells in any time step, the fire fighter is allowed to block $c$ cells in the average outside the fire in the same time interval. It was shown that the success of the fire fighter is guaranteed for $c>1.5$ but no strategy can enclose the fire for $c\leq 1.5$. For achieving such a critical threshold the correctness (sometimes even optimality) of strategies and lower bounds have been shown by integer programming or by direct but often very sophisticated arguments. We investigate the problem whether it is possible to find or to approach such a threshold and/or optimal strategies by means of evolutionary algorithms, i.e., we just try to learn successful strategies for different constants $c$ and have a look at the outcome. The main general idea is that this approach might give some insight in the power of evolutionary strategies for similar geometrically motivated threshold questions. We investigate the variant of protecting a highway with still unknown threshold and found interesting strategic paradigms. Keywords: Dynamic environments, fire fighting, evolutionary strategies, threshold approximation
Fast k-means based on KNN Graph
Venue: arXiv cs.LG 2017
Year: 2017

In the era of big data, k-means clustering has been widely adopted as a basic processing tool in various contexts. However, its computational cost could be prohibitively high as the data size and the cluster number are large. It is well known that the processing bottleneck of k-means lies in the operation of seeking closest centroid in each iteration. In this paper, a novel solution towards the scalability issue of k-means is presented. In the proposal, k-means is supported by an approximate k-nearest neighbors graph. In the k-means iteration, each data sample is only compared to clusters that its nearest neighbors reside. Since the number of nearest neighbors we consider is much less than k, the processing cost in this step becomes minor and irrelevant to k. The processing bottleneck is therefore overcome. The most interesting thing is that k-nearest neighbor graph is constructed by iteratively calling the fast $k$-means itself. Comparing with existing fast k-means variants, the proposed algorithm achieves hundreds to thousands times speed-up while maintaining high clustering quality. As it is tested on 10 million 512-dimensional data, it takes only 5.2 hours to produce 1 million clusters. In contrast, to fulfill the same scale of clustering, it would take 3 years for traditional k-means.
A Finite State and Rule-based Akshara to Prosodeme (A2P) Converter in Hindi
Venue: arXiv cs.CL 2017
Year: 2017

This article describes a software module called Akshara to Prosodeme (A2P) converter in Hindi. It converts an input grapheme into prosedeme (sequence of phonemes with the specification of syllable boundaries and prosodic labels). The software is based on two proposed finite state machines\textemdash one for the syllabification and another for the syllable labeling. In addition to that, it also uses a set of nonlinear phonological rules proposed for foot formation in Hindi, which encompass solutions to schwa-deletion in simple, compound, derived and inflected words. The nonlinear phonological rules are based on metrical phonology with the provision of recursive foot structure. A software module is implemented in Python. The testing of the software for syllabification, syllable labeling, schwa deletion and prosodic labeling yield an accuracy of more than 99% on a lexicon of size 28664 words.
Holistic Cyber-Physical Management for Dependable Wireless Control Systems
Venue: arXiv cs.SY 2017
Year: 2017

Wireless sensor-actuator networks (WSANs) are gaining momentum in industrial process automation as a communication infrastructure for lowering deployment and maintenance costs. In traditional wireless control systems the plant controller and the network manager operate in isolation, which ignore the significant influence of network reliability on plant control performance. To enhance the dependability of industrial wireless control, we propose a holistic cyber-physical management framework that employs run-time coordination between the plant control and network management. Our design includes a holistic controller that generates actuation signals to physical plants and reconfigures the WSAN to maintain desired control performance while saving wireless resources. As a concrete example of holistic control, we design a holistic manager that dynamically reconfigures the number of transmissions in the WSAN based on online observations of physical and cyber variables. We have implemented the holistic management framework in the Wireless Cyber-Physical Simulator (WCPS). A systematic case study has been presented based on two 5-state plants sharing a 16-node WSAN. Simulation results show that the holistic management design has significantly enhanced the resilience of the system against both wireless interferences and physical disturbances, while effectively reducing the number of wireless transmissions.
An Active Learning Approach to the Falsification of Black Box Cyber-Physical Systems
Venue: arXiv cs.LO 2017
Year: 2017

Search-based testing is widely used to find bugs in models of complex Cyber-Physical Systems. Latest research efforts have improved this approach by casting it as a falsification procedure of formally specified temporal properties, exploiting the robustness semantics of Signal Temporal Logic. The scaling of this approach to highly complex engineering systems requires efficient falsification procedures, which should be applicable also to black box models. Falsification is also exacerbated by the fact that inputs are often time-dependent functions. We tackle the falsification of formal properties of complex black box models of Cyber-Physical Systems, leveraging machine learning techniques from the area of Active Learning. Tailoring these techniques to the falsification problem with time-dependent, functional inputs, we show a considerable gain in computational effort, by reducing the number of model simulations needed. The goodness of the proposed approach is discussed on a challenging industrial-level benchmark from automotive.
MOBILITY21: Strategic Investments for Transportation Infrastructure & Technology
Venue: arXiv cs.CY 2017
Year: 2017

America's transportation infrastructure is the backbone of our economy. A strong infrastructure means a strong America - an America that competes globally, supports local and regional economic development, and creates jobs. Strategic investments in our transportation infrastructure are vital to our national security, economic growth, transportation safety and our technology leadership. This document outlines critical needs for our transportation infrastructure, identifies new technology drivers and proposes strategic investments for safe and efficient air, ground, rail and marine mobility of people and goods.
Malware Detection on General-Purpose Computers Using Power Consumption Monitoring: A Proof of Concept and Case Study
Venue: arXiv cs.CR 2017
Year: 2017

Malware detection is challenging when faced with automatically generated and polymorphic malware, as well as with rootkits, which are exceptionally hard to detect. In an attempt to contribute towards addressing these challenges, we conducted a proof of concept study that explored the use of power consumption for detection of malware presence in a general-purpose computer. The results of our experiments indicate that malware indeed leaves a signal on the power consumption of a general-purpose computer. Specifically, for the case study based on two different rootkits, the data collected at the +12V rails on the motherboard showed the most noticeable increment of the power consumption after the computer was infected. Our future work includes experimenting with more malware examples and workloads, and developing data analytics approach for automatic malware detection based on power consumption.
On Identifying Disaster-Related Tweets: Matching-based or Learning-based?
Venue: arXiv cs.IR 2017
Year: 2017

Social media such as tweets are emerging as platforms contributing to situational awareness during disasters. Information shared on Twitter by both affected population (e.g., requesting assistance, warning) and those outside the impact zone (e.g., providing assistance) would help first responders, decision makers, and the public to understand the situation first-hand. Effective use of such information requires timely selection and analysis of tweets that are relevant to a particular disaster. Even though abundant tweets are promising as a data source, it is challenging to automatically identify relevant messages since tweet are short and unstructured, resulting to unsatisfactory classification performance of conventional learning-based approaches. Thus, we propose a simple yet effective algorithm to identify relevant messages based on matching keywords and hashtags, and provide a comparison between matching-based and learning-based approaches. To evaluate the two approaches, we put them into a framework specifically proposed for analyzing disaster-related tweets. Analysis results on eleven datasets with various disaster types show that our technique provides relevant tweets of higher quality and more interpretable results of sentiment analysis tasks when compared to learning approach.
Distributed Formation Control for Autonomous Robots in Dynamic Environments
Venue: arXiv cs.RO 2017
Year: 2017

In this paper, we propose a novel and distributed formation control method for autonomous robots to follow the desired formation while tracking a moving target in dynamic environments. In our approach, the desired formations, which include the virtual nodes arranged into specific shapes, are first generated. Then, autonomous robots are controlled by the proposed artificial force fields in order to converge to these virtual nodes without collisions. The stability analysis based on the Lyapunov approach is given. Moreover, a new combination of rotational force field and repulsive force field in designing an obstacle avoidance controller allows the robot to avoid and escape the convex and nonconvex obstacle shapes. The V-shape and circular shape formations with their advantages are utilized to test the effectiveness of the proposed method.
False Data Injection Attacks on Phasor Measurements That Bypass Low-rank Decomposition
Venue: arXiv cs.SY 2017
Year: 2017

This paper studies the vulnerability of phasor measurement units (PMUs) to false data injection (FDI) attacks. Prior work demonstrated that unobservable FDI attacks that can bypass traditional bad data detectors based on measurement residuals can be identified by detector based on low-rank decomposition (LD). In this work, a class of more sophisticated FDI attacks that captures the temporal correlation of PMU data is introduced. Such attacks are designed with a convex optimization problem and can always bypass the LD detector. The vulnerability of this attack model is illustrated on both the IEEE 24-bus RTS and the IEEE 118-bus systems.
Optimal Power Control and Scheduling under Hard Deadline Constraints for Continuous Fading Channels
Venue: arXiv cs.IT 2017
Year: 2017

We consider a joint scheduling-and-power-allocation problem of a downlink cellular system. The system consists of two groups of users: real-time (RT) and non-real-time (NRT) users. Given an average power constraint on the base station, the problem is to find an algorithm that satisfies the RT hard deadline constraint and NRT queue stability constraint. We propose a sum-rate-maximizing algorithm that satisfies these constraints. We also show, through simulations, that the proposed algorithm has an average complexity that is close-to-linear in the number of RT users. The power allocation policy in the proposed algorithm has a closed-form expression for the two groups of users. However, interestingly, the power policy of the RT users differ in structure from that of the NRT users. We also show the superiority of the proposed algorithms over existing approaches using extensive simulations.
Joint RNN Model for Argument Component Boundary Detection
Venue: arXiv cs.CL 2017
Year: 2017

Argument Component Boundary Detection (ACBD) is an important sub-task in argumentation mining; it aims at identifying the word sequences that constitute argument components, and is usually considered as the first sub-task in the argumentation mining pipeline. Existing ACBD methods heavily depend on task-specific knowledge, and require considerable human efforts on feature-engineering. To tackle these problems, in this work, we formulate ACBD as a sequence labeling problem and propose a variety of Recurrent Neural Network (RNN) based methods, which do not use domain specific or handcrafted features beyond the relative position of the sentence in the document. In particular, we propose a novel joint RNN model that can predict whether sentences are argumentative or not, and use the predicted results to more precisely detect the argument component boundaries. We evaluate our techniques on two corpora from two different genres; results suggest that our joint RNN model obtain the state-of-the-art performance on both datasets.
Bridging between Computer and Robot Vision through Data Augmentation: a Case Study on Object Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Despite the impressive progress brought by deep network in visual object recognition, robot vision is still far from being a solved problem. The most successful convolutional architectures are developed starting from ImageNet, a large scale collection of images of object categories downloaded from the Web. This kind of images is very different from the situated and embodied visual experience of robots deployed in unconstrained settings. To reduce the gap between these two visual experiences, this paper proposes a simple yet effective data augmentation layer that zooms on the object of interest and simulates the object detection outcome of a robot vision system. The layer, that can be used with any convolutional deep architecture, brings to an increase in object recognition performance of up to 7\%, in experiments performed over three different benchmark databases. Upon acceptance of the paper, our robot data augmentation layer will be made publicly available.
Shrinking Horizon Model Predictive Control with Signal Temporal Logic Constraints under Stochastic Disturbances
Venue: arXiv cs.SY 2017
Year: 2017

We present Shrinking Horizon Model Predictive Control (SHMPC) for discrete-time linear systems with Signal Temporal Logic (STL) specification constraints under stochastic disturbances. The control objective is to maximize an optimization function under the restriction that a given STL specification is satisfied with high probability against stochastic uncertainties. We formulate a general solution, which does not require precise knowledge of the probability distributions of the (possibly dependent) stochastic disturbances; only the bounded support intervals of the density functions and moment intervals are used. For the specific case of disturbances that are independent and normally distributed, we optimize the controllers further by utilizing knowledge of the disturbance probability distributions. We show that in both cases, the control law can be obtained by solving optimization problems with linear constraints at each step. We experimentally demonstrate effectiveness of this approach by synthesizing a controller for an HVAC system.
Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps
Venue: arXiv cs.DM 2017
Year: 2017

In the absence of horizontal gene transfer it is possible to reconstruct the history of gene families from empirically determined orthology relations, which are equivalent to event-labeled gene trees. Knowledge of the event labels considerably simplifies the problem of reconciling a gene tree T with a species trees S, relative to the reconciliation problem without prior knowledge of the event types. It is well-known that optimal reconciliations in the unlabeled case may violate time-consistency and thus are not biologically feasible. Here we investigate the mathematical structure of the event labeled reconciliation problem with horizontal transfer. We investigate the issue of time-consistency for the event-labeled version of the reconciliation problem, provide a convenient axiomatic framework, and derive a complete characterization of time-consistent reconciliations. This characterization depends on certain weak conditions on the event-labeled gene trees that reflect conditions under which evolutionary events are observable at least in principle. We give an O(|V(T)|log(|V(S)|))-time algorithm to decide whether a time-consistent reconciliation map exists. It does not require the construction of explicit timing maps, but relies entirely on the comparably easy task of checking whether a small auxiliary graph is acyclic. The combinatorial characterization of time consistency and thus biologically feasible reconciliation is an important step towards the inference of gene family histories with horizontal transfer from orthology data, i.e., without presupposed gene and species trees. The fast algorithm to decide time consistency is useful in a broader context because it constitutes an attractive component for all tools that address tree reconciliation problems.