OpenRaiser/Intern-Atlas huggingface dataset:
Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks
Venue: arXiv cs.AI 2017
Year: 2017

The multi-agent path-finding (MAPF) problem has recently received a lot of attention. However, it does not capture important characteristics of many real-world domains, such as automated warehouses, where agents are constantly engaged with new tasks. In this paper, we therefore study a lifelong version of the MAPF problem, called the multi-agent pickup and delivery (MAPD) problem. In the MAPD problem, agents have to attend to a stream of delivery tasks in an online setting. One agent has to be assigned to each delivery task. This agent has to first move to a given pickup location and then to a given delivery location while avoiding collisions with other agents. We present two decoupled MAPD algorithms, Token Passing (TP) and Token Passing with Task Swaps (TPTS). Theoretically, we show that they solve all well-formed MAPD instances, a realistic subclass of MAPD instances. Experimentally, we compare them against a centralized strawman MAPD algorithm without this guarantee in a simulated warehouse system. TP can easily be extended to a fully distributed MAPD algorithm and is the best choice when real-time computation is of primary concern since it remains efficient for MAPD instances with hundreds of agents and tasks. TPTS requires limited communication among agents and balances well between TP and the centralized MAPD algorithm.
High Dimensional Structured Superposition Models
Venue: arXiv cs.LG 2017
Year: 2017

High dimensional superposition models characterize observations using parameters which can be written as a sum of multiple component parameters, each with its own structure, e.g., sum of low rank and sparse matrices, sum of sparse and rotated sparse vectors, etc. In this paper, we consider general superposition models which allow sum of any number of component parameters, and each component structure can be characterized by any norm. We present a simple estimator for such models, give a geometric condition under which the components can be accurately estimated, characterize sample complexity of the estimator, and give high probability non-asymptotic bounds on the componentwise estimation error. We use tools from empirical processes and generic chaining for the statistical analysis, and our results, which substantially generalize prior work on superposition models, are in terms of Gaussian widths of suitable sets.
Real-Time Robot Localization, Vision, and Speech Recognition on Nvidia Jetson TX1
Venue: arXiv cs.RO 2017
Year: 2017

Robotics systems are complex, often consisted of basic services including SLAM for localization and mapping, Convolution Neural Networks for scene understanding, and Speech Recognition for user interaction, etc. Meanwhile, robots are mobile and usually have tight energy constraints, integrating these services onto an embedded platform with around 10 W of power consumption is critical to the proliferation of mobile robots. In this paper, we present a case study on integrating real-time localization, vision, and speech recognition services on a mobile SoC, Nvidia Jetson TX1, within about 10 W of power envelope. In addition, we explore whether offloading some of the services to cloud platform can lead to further energy efficiency while meeting the real-time requirements
Maximum-Area Triangle in a Convex Polygon, Revisited
Venue: arXiv cs.CG 2017
Year: 2017

We revisit the following problem: Given a convex polygon $P$, find the largest-area inscribed triangle. We show by example that the linear-time algorithm presented in 1979 by Dobkin and Snyder for solving this problem fails. We then proceed to show that with a small adaptation, their approach does lead to a quadratic-time algorithm. We also present a more involved $O(n\log n)$ time divide-and-conquer algorithm. Also we show by example that the algorithm presented in 1979 by Dobkin and Snyder for finding the largest-area $k$-gon that is inscribed in a convex polygon fails to find the optimal solution for $k=4$. Finally, we discuss the implications of our discoveries on the literature.
Coexistence of Outdoor Wi-Fi and Radar at 3.5 GHz
Venue: arXiv cs.NI 2017
Year: 2017

Coexistence between radar and outdoor Wireless Fidelity (Wi-Fi) needs thorough study since the IEEE 802.11 Working Group (WG) opposed the latest rules in 3550-3700 MHz (the 3.5 GHz band) that require "exclusion zones." This letter proposes a method that suppresses Wi-Fi-to-radar (WtR) interference, in which a Wi-Fi transmitter (TX) is selected to avoid beam angles toward the victim radar. It is distinguished from prior schemes since it ensures that the Wi-Fi remains operable while suppressing the WtR interference.
Communication-aware Motion Planning for Multi-agent Systems from Signal Temporal Logic Specifications
Venue: arXiv cs.SY 2017
Year: 2017

We propose a mathematical framework for synthesizing motion plans for multi-agent systems that fulfill complex, high-level and formal local specifications in the presence of inter-agent communication. The proposed synthesis framework consists of desired motion specifications in temporal logic (STL) formulas and a local motion controller that ensures the underlying agent not only to accomplish the local specifications but also to avoid collisions with other agents or possible obstacles, while maintaining an optimized communication quality of service (QoS) among the agents. Utilizing a Gaussian fading model for wireless communication channels, the framework synthesizes the desired motion controller by solving a joint optimization problem on motion planning and wireless communication, in which both the STL specifications and the wireless communication conditions are encoded as mixed integer-linear constraints on the variables of the agents' dynamical states and communication channel status. The overall framework is demonstrated by a case study of communication-aware multi-robot motion planning and the effectiveness of the framework is validated by simulation results.
Optimal placement of mix zones in road networks
Venue: arXiv cs.OH 2017
Year: 2017

The road networks, vehicle users could enjoy numerous kind of services such as location based service in vehicle users can connected to Internet and communication of different users. Therefore, in order to acquire adequate privacy level and quality of service, one must have to wisely place mix zones to connect vehicle users to internet or some other internetwork. According to this research, we have analyzed the problem of optimal placement mix zones over road network. To enhance the coverage capacity of vehicles, in order to reduce the cost and communication delay. Further, it has also been discovered to minimize the cost of mix zone placement. Moreover, it has also been shown that, as the best deployment mix zones get minimized cost while at the same time the average capacity of mix zone can be maximized also privacy level increased because of optimal placement and high traffic environment.
The Role of Data Analysis in the Development of Intelligent Energy Networks
Venue: arXiv cs.OH 2017
Year: 2017

Data analysis plays an important role in the development of intelligent energy networks (IENs). This article reviews and discusses the application of data analysis methods for energy big data. The installation of smart energy meters has provided a huge volume of data at different time resolutions, suggesting data analysis is required for clustering, demand forecasting, energy generation optimization, energy pricing, monitoring and diagnostics. The currently adopted data analysis technologies for IENs include pattern recognition, machine learning, data mining, statistics methods, etc. However, existing methods for data analysis cannot fully meet the requirements for processing the big data produced by the IENs and, therefore, more comprehensive data analysis methods are needed to handle the increasing amount of data and to mine more valuable information.
A lower bound on the order of the largest induced linear forest in triangle-free planar graphs
Venue: arXiv cs.DM 2017
Year: 2017

We prove that every triangle-free planar graph of order $n$ and size $m$ has an induced linear forest with at least $\frac{9n - 2m}{11}$ vertices, and thus at least $\frac{5n + 8}{11}$ vertices. Furthermore, we show that there are triangle-free planar graphs on $n$ vertices whose largest induced linear forest has order $\lceil \frac{n}{2} \rceil + 1$.
Reinforcement Learning for Learning Rate Control
Venue: arXiv cs.LG 2017
Year: 2017

Stochastic gradient descent (SGD), which updates the model parameters by adding a local gradient times a learning rate at each step, is widely used in model training of machine learning algorithms such as neural networks. It is observed that the models trained by SGD are sensitive to learning rates and good learning rates are problem specific. We propose an algorithm to automatically learn learning rates using neural network based actor-critic methods from deep reinforcement learning (RL).In particular, we train a policy network called actor to decide the learning rate at each step during training, and a value network called critic to give feedback about quality of the decision (e.g., the goodness of the learning rate outputted by the actor) that the actor made. The introduction of auxiliary actor and critic networks helps the main network achieve better performance. Experiments on different datasets and network architectures show that our approach leads to better convergence of SGD than human-designed competitors.
Biased Importance Sampling for Deep Neural Network Training
Venue: arXiv cs.LG 2017
Year: 2017

Importance sampling has been successfully used to accelerate stochastic optimization in many convex problems. However, the lack of an efficient way to calculate the importance still hinders its application to Deep Learning. In this paper, we show that the loss value can be used as an alternative importance metric, and propose a way to efficiently approximate it for a deep model, using a small model trained for that purpose in parallel. This method allows in particular to utilize a biased gradient estimate that implicitly optimizes a soft max-loss, and leads to better generalization performance. While such method suffers from a prohibitively high variance of the gradient estimate when using a standard stochastic optimizer, we show that when it is combined with our sampling mechanism, it results in a reliable procedure. We showcase the generality of our method by testing it on both image classification and language modeling tasks using deep convolutional and recurrent neural networks. In particular, our method results in 30% faster training of a CNN for CIFAR10 than when using uniform sampling.
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube
Venue: arXiv cs.CC 2017
Year: 2017

A Boolean function $f:\{0,1\}^d \mapsto \{0,1\}$ is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadaptive, one-sided error unateness tester must make $Ω(\frac{d}{\log d})$ queries. This result improves upon the $Ω(\frac{d}{\log^2 d})$ lower bound for the same class of testers due to Chen et al. (STOC, 2017).
Descriptions of Objectives and Processes of Mechanical Learning
Venue: arXiv cs.AI 2017
Year: 2017

In [1], we introduced mechanical learning and proposed 2 approaches to mechanical learning. Here, we follow one such approach to well describe the objects and the processes of learning. We discuss 2 kinds of patterns: objective and subjective pattern. Subjective pattern is crucial for learning machine. We prove that for any objective pattern we can find a proper subjective pattern based upon least base patterns to express the objective pattern well. X-form is algebraic expression for subjective pattern. Collection of X-forms form internal representation space, which is center of learning machine. We discuss learning by teaching and without teaching. We define data sufficiency by X-form. We then discussed some learning strategies. We show, in each strategy, with sufficient data, and with certain capabilities, learning machine indeed can learn any pattern (universal learning machine). In appendix, with knowledge of learning machine, we try to view deep learning from a different angle, i.e. its internal representation space and its learning dynamics.
Putting a Face to the Voice: Fusing Audio and Visual Signals Across a Video to Determine Speakers
Venue: arXiv cs.MM 2017
Year: 2017

In this paper, we present a system that associates faces with voices in a video by fusing information from the audio and visual signals. The thesis underlying our work is that an extremely simple approach to generating (weak) speech clusters can be combined with visual signals to effectively associate faces and voices by aggregating statistics across a video. This approach does not need any training data specific to this task and leverages the natural coherence of information in the audio and visual streams. It is particularly applicable to tracking speakers in videos on the web where a priori information about the environment (e.g., number of speakers, spatial signals for beamforming) is not available. We performed experiments on a real-world dataset using this analysis framework to determine the speaker in a video. Given a ground truth labeling determined by human rater consensus, our approach had ~71% accuracy.
Semantic Refinement GRU-based Neural Language Generation for Spoken Dialogue Systems
Venue: arXiv cs.CL 2017
Year: 2017

Natural language generation (NLG) plays a critical role in spoken dialogue systems. This paper presents a new approach to NLG by using recurrent neural networks (RNN), in which a gating mechanism is applied before RNN computation. This allows the proposed model to generate appropriate sentences. The RNN-based generator can be learned from unaligned data by jointly training sentence planning and surface realization to produce natural language responses. The model was extensively evaluated on four different NLG domains. The results show that the proposed generator achieved better performance on all the NLG domains compared to previous generators.
Using Cognitive Dimensions Questionnaire to Evaluate the Usability of Security APIs
Venue: arXiv cs.CR 2017
Year: 2017

Usability issues that exist in security APIs cause programmers to embed those security APIs incorrectly to the applications they develop. This results in introduction of security vulnerabilities to those applications. One of the main reasons for security APIs to be not usable is currently there is no proper method by which the usability issues of security APIs can be identified. We conducted a study to assess the effectiveness of the cognitive dimensions questionnaire based usability evaluation methodology in evaluating the usability of security APIs. We used a cognitive dimensions based generic questionnaire to collect feedback from programmers who participated in the study. Results revealed interesting facts about the prevailing usability issues in four commonly used security APIs and the capability of the methodology to identify those issues.
Order preserving pattern matching on trees and DAGs
Venue: arXiv cs.DS 2017
Year: 2017

The order preserving pattern matching (OPPM) problem is, given a pattern string $p$ and a text string $t$, find all substrings of $t$ which have the same relative orders as $p$. In this paper, we consider two variants of the OPPM problem where a set of text strings is given as a tree or a DAG. We show that the OPPM problem for a single pattern $p$ of length $m$ and a text tree $T$ of size $N$ can be solved in $O(m+N)$ time if the characters of $p$ are drawn from an integer alphabet of polynomial size. The time complexity becomes $O(m \log m + N)$ if the pattern $p$ is over a general ordered alphabet. We then show that the OPPM problem for a single pattern and a text DAG is NP-complete.
Shared Autonomy via Hindsight Optimization for Teleoperation and Teaming
Venue: arXiv cs.RO 2017
Year: 2017

In shared autonomy, a user and autonomous system work together to achieve shared goals. To collaborate effectively, the autonomous system must know the user's goal. As such, most prior works follow a predict-then-act model, first predicting the user's goal with high confidence, then assisting given that goal. Unfortunately, confidently predicting the user's goal may not be possible until they have nearly achieved it, causing predict-then-act methods to provide little assistance. However, the system can often provide useful assistance even when confidence for any single goal is low (e.g. move towards multiple goals). In this work, we formalize this insight by modelling shared autonomy as a Partially Observable Markov Decision Process (POMDP), providing assistance that minimizes the expected cost-to-go with an unknown goal. As solving this POMDP optimally is intractable, we use hindsight optimization to approximate. We apply our framework to both shared-control teleoperation and human-robot teaming. Compared to predict-then-act methods, our method achieves goals faster, requires less user input, decreases user idling time, and results in fewer user-robot collisions.
Statistical Analysis and Parameter Selection for Mapper
Venue: arXiv cs.CG 2017
Year: 2017

In this article, we study the question of the statistical convergence of the 1-dimensional Mapper to its continuous analogue, the Reeb graph. We show that the Mapper is an optimal estimator of the Reeb graph, which gives, as a byproduct, a method to automatically tune its parameters and compute confidence regions on its topological features, such as its loops and flares. This allows to circumvent the issue of testing a large grid of parameters and keeping the most stable ones in the brute-force setting, which is widely used in visualization, clustering and feature selection with the Mapper.
Item-Item Music Recommendations With Side Information
Venue: arXiv cs.IR 2017
Year: 2017

Online music services have tens of millions of tracks. The content itself is broad and covers various musical genres as well as non-musical audio content such as radio plays and podcasts. The sheer scale and diversity of content makes it difficult for a user to find relevant tracks. Relevant recommendations are therefore crucial for a good user experience. Here we present a method to compute track-track similarities using collaborative filtering signals with side information. On a data set from music streaming service SoundCloud, the method here outperforms the widely adopted implicit matrix factorization technique. The implementation of our method is open sourced and can be applied to related item-item recommendation tasks with side information.
Automatic Differentiation using Constraint Handling Rules in Prolog
Venue: arXiv cs.MS 2017
Year: 2017

Automatic differentiation is a technique which allows a programmer to define a numerical computation via compositions of a broad range of numeric and computational primitives and have the underlying system support the computation of partial derivatives of the result with respect to any of its inputs, without making any finite difference approximations, and without manipulating large symbolic expressions representing the computation. This note describes a novel approach to reverse mode automatic differentiation using constraint logic programmming, specifically, the constraint handling rules (CHR) library of SWI Prolog, resulting in a very small (50 lines of code) implementation. When applied to a differentiation-based implementation of the inside-outside algorithm for parameter learning in probabilistic grammars, the CHR based implementations outperformed two well-known frameworks for optimising differentiable functions, Theano and TensorFlow, by a large margin.
Polish Read Speech Corpus for Speech Tools and Services
Venue: arXiv cs.CL 2017
Year: 2017

This paper describes the speech processing activities conducted at the Polish consortium of the CLARIN project. The purpose of this segment of the project was to develop specific tools that would allow for automatic and semi-automatic processing of large quantities of acoustic speech data. The tools include the following: grapheme-to-phoneme conversion, speech-to-text alignment, voice activity detection, speaker diarization, keyword spotting and automatic speech transcription. Furthermore, in order to develop these tools, a large high-quality studio speech corpus was recorded and released under an open license, to encourage development in the area of Polish speech research. Another purpose of the corpus was to serve as a reference for studies in phonetics and pronunciation. All the tools and resources were released on the the Polish CLARIN website. This paper discusses the current status and future plans for the project.
Transfer Learning for Speech Recognition on a Budget
Venue: arXiv cs.LG 2017
Year: 2017

End-to-end training of automated speech recognition (ASR) systems requires massive data and compute resources. We explore transfer learning based on model adaptation as an approach for training ASR models under constrained GPU memory, throughput and training data. We conduct several systematic experiments adapting a Wav2Letter convolutional neural network originally trained for English ASR to the German language. We show that this technique allows faster training on consumer-grade resources while requiring less training data in order to achieve the same accuracy, thereby lowering the cost of training ASR models in other languages. Model introspection revealed that small adaptations to the network's weights were sufficient for good performance, especially for inner layers.
Enhancing workflow-nets with data for trace completion
Venue: arXiv cs.AI 2017
Year: 2017

The growing adoption of IT-systems for modeling and executing (business) processes or services has thrust the scientific investigation towards techniques and tools which support more complex forms of process analysis. Many of them, such as conformance checking, process alignment, mining and enhancement, rely on complete observation of past (tracked and logged) executions. In many real cases, however, the lack of human or IT-support on all the steps of process execution, as well as information hiding and abstraction of model and data, result in incomplete log information of both data and activities. This paper tackles the issue of automatically repairing traces with missing information by notably considering not only activities but also data manipulated by them. Our technique recasts such a problem in a reachability problem and provides an encoding in an action language which allows to virtually use any state-of-the-art planning to return solutions.