OpenRaiser/Intern-Atlas huggingface dataset:
Path Planning in Dynamic Environments with Adaptive Dimensionality
Venue: arXiv cs.RO 2016
Year: 2016

Path planning in the presence of dynamic obstacles is a challenging problem due to the added time dimension in search space. In approaches that ignore the time dimension and treat dynamic obstacles as static, frequent re-planning is unavoidable as the obstacles move, and their solutions are generally sub-optimal and can be incomplete. To achieve both optimality and completeness, it is necessary to consider the time dimension during planning. The notion of adaptive dimensionality has been successfully used in high-dimensional motion planning such as manipulation of robot arms, but has not been used in the context of path planning in dynamic environments. In this paper, we apply the idea of adaptive dimensionality to speed up path planning in dynamic environments for a robot with no assumptions on its dynamic model. Specifically, our approach considers the time dimension only in those regions of the environment where a potential collision may occur, and plans in a low-dimensional state-space elsewhere. We show that our approach is complete and is guaranteed to find a solution, if one exists, within a cost sub-optimality bound. We experimentally validate our method on the problem of 3D vehicle navigation (x, y, heading) in dynamic environments. Our results show that the presented approach achieves substantial speedups in planning time over 4D heuristic-based A*, especially when the resulting plan deviates significantly from the one suggested by the heuristic.
DLAU: A Scalable Deep Learning Accelerator Unit on FPGA
Venue: arXiv cs.LG 2016
Year: 2016

As the emerging field of machine learning, deep learning shows excellent ability in solving complex learning problems. However, the size of the networks becomes increasingly large scale due to the demands of the practical applications, which poses significant challenge to construct a high performance implementations of deep learning neural networks. In order to improve the performance as well to maintain the low power cost, in this paper we design DLAU, which is a scalable accelerator architecture for large-scale deep learning networks using FPGA as the hardware prototype. The DLAU accelerator employs three pipelined processing units to improve the throughput and utilizes tile techniques to explore locality for deep learning applications. Experimental results on the state-of-the-art Xilinx FPGA board demonstrate that the DLAU accelerator is able to achieve up to 36.1x speedup comparing to the Intel Core2 processors, with the power consumption at 234mW.
MDS Codes with Progressive Engagement Property for Cloud Storage Systems
Venue: arXiv cs.IT 2016
Year: 2016

Fast and efficient failure recovery is a new challenge for cloud storage systems with a large number of storage nodes. A pivotal recovery metric upon the failure of a storage node is repair bandwidth cost which refers to the amount of data that must be downloaded for regenerating the lost data. Since all the surviving nodes are not always accessible, we intend to introduce a class of maximum distance separable (MDS) codes that can be re-used when the number of selected nodes varies yet yields close to optimal repair bandwidth. Such codes provide flexibility in engaging more surviving nodes in favor of reducing the repair bandwidth without redesigning the code structure and changing the content of the existing nodes. We call this property of MDS codes progressive engagement. This name comes from the fact that if a failure occurs, it is shown that the best strategy is to incrementally engage the surviving nodes according to their accessing cost (delay, number of hops, traffic load or availability in general) until the repair-bandwidth or accessing cost constraints are met. We argue that the existing MDS codes fail to satisfy the progressive engagement property. We subsequently present a search algorithm to find a new set of codes named rotation codes that has both progressive engagement and MDS properties. Furthermore, we illustrate how the existing permutation codes can provide progressive engagement by modifying the original recovery scheme. Simulation results are presented to compare the repair bandwidth performance of such codes when the number of participating nodes varies as well as their speed of single failure recovery.
Elastic Solver: Balancing Solution Time and Energy Consumption
Venue: arXiv cs.AI 2016
Year: 2016

Combinatorial decision problems arise in many different domains such as scheduling, routing, packing, bioinformatics, and many more. Despite recent advances in developing scalable solvers, there are still many problems which are often very hard to solve. Typically the most advanced solvers include elements which are stochastic in nature. If a same instance is solved many times using different seeds then depending on the inherent characteristics of a problem instance and the solver, one can observe a highly-variant distribution of times spanning multiple orders of magnitude. Therefore, to solve a problem instance efficiently it is often useful to solve the same instance in parallel with different seeds. With the proliferation of cloud computing, it is natural to think about an elastic solver which can scale up by launching searches in parallel on thousands of machines (or cores). However, this could result in consuming a lot of energy. Moreover, not every instance would require thousands of machines. The challenge is to resolve the tradeoff between solution time and energy consumption optimally for a given problem instance. We analyse the impact of the number of machines (or cores) on not only solution time but also on energy consumption. We highlight that although solution time always drops as the number of machines increases, the relation between the number of machines and energy consumption is more complicated. In many cases, the optimal energy consumption may be achieved by a middle ground, we analyse this relationship in detail. The tradeoff between solution time and energy consumption is studied further, showing that the energy consumption of a solver can be reduced drastically if we increase the solution time marginally. We also develop a prediction model, demonstrating that such insights can be exploited to achieve faster solutions times in a more energy efficient manor.
Continuous Time Quantum Consensus & Quantum Synchronisation
Venue: arXiv cs.SY 2016
Year: 2016

Distributed consensus algorithm over networks of quantum systems has been the focus of recent studies in the context of quantum computing and distributed control. Most of the progress in this category have been on the convergence conditions and optimizing the convergence rate of the algorithm, for quantum networks with undirected underlying topology. This paper aims to address the extension of this problem over quantum networks with directed underlying graphs. In doing so, the convergence to two different stable states namely, consensus and synchronous states have been studied. Based on the intertwining relation between the eigenvalues, it is shown that for determining the convergence rate to the consensus state, all induced graphs should be considered while for the synchronous state only the underlying graph suffices. Furthermore, it is illustrated that for the range of weights that the Aldous' conjecture holds true, the convergence rate to both states are equal. Using the Pareto region for convergence rates of the algorithm, the global and Pareto optimal points for several topologies have been provided.
SONIK: Efficient In-situ All Item Rank Generation using Bit Operations
Venue: arXiv cs.DS 2016
Year: 2016

Sorting, a classical combinatorial process, forms the bedrock of numerous algorithms with varied applications. A related problem involves efficiently finding the corresponding ranks of all the elements - catering to rank queries, data partitioning and allocation, etc. Although, the element ranks can be subsequently obtained by initially sorting the elements, such procedures involve O(n log n) computations and might not be suitable with large input sizes for hard real-time systems or for applications with data re-ordering constraints. This paper proposes SONIK, a non-comparison linear time and space algorithm using bit operations inspired by radix sort for computing the ranks of all input integer elements, thereby providing implicit sorting. The element ranks are generated in-situ, i.e., directly at the corresponding element position without re-ordering or recourse to any other sorting mechanism.
On Restricted Nonnegative Matrix Factorization
Venue: arXiv cs.FL 2016
Year: 2016

Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative $n \times m$ matrix $M$ into a product of a nonnegative $n \times d$ matrix $W$ and a nonnegative $d \times m$ matrix $H$. Restricted NMF requires in addition that the column spaces of $M$ and $W$ coincide. Finding the minimal inner dimension $d$ is known to be NP-hard, both for NMF and restricted NMF. We show that restricted NMF is closely related to a question about the nature of minimal probabilistic automata, posed by Paz in his seminal 1971 textbook. We use this connection to answer Paz's question negatively, thus falsifying a positive answer claimed in 1974. Furthermore, we investigate whether a rational matrix $M$ always has a restricted NMF of minimal inner dimension whose factors $W$ and $H$ are also rational. We show that this holds for matrices $M$ of rank at most $3$ and we exhibit a rank-$4$ matrix for which $W$ and $H$ require irrational entries.
Generic Instance Search and Re-identification from One Example via Attributes and Categories
Venue: arXiv cs.CV 2016
Year: 2016

This paper aims for generic instance search from one example where the instance can be an arbitrary object like shoes, not just near-planar and one-sided instances like buildings and logos. First, we evaluate state-of-the-art instance search methods on this problem. We observe that what works for buildings loses its generality on shoes. Second, we propose to use automatically learned category-specific attributes to address the large appearance variations present in generic instance search. Searching among instances from the same category as the query, the category-specific attributes outperform existing approaches by a large margin on shoes and cars and perform on par with the state-of-the-art on buildings. Third, we treat person re-identification as a special case of generic instance search. On the popular VIPeR dataset, we reach state-of-the-art performance with the same method. Fourth, we extend our method to search objects without restriction to the specifically known category. We show that the combination of category-level information and the category-specific attributes is superior to the alternative method combining category-level information with low-level features such as Fisher vector.
Functional Forms of Optimum Spoofing Attacks for Vector Parameter Estimation in Quantized Sensor Networks
Venue: arXiv cs.IT 2016
Year: 2016

Estimation of an unknown deterministic vector from quantized sensor data is considered in the presence of spoofing attacks which alter the data presented to several sensors. Contrary to previous work, a generalized attack model is employed which manipulates the data using transformations with arbitrary functional forms determined by some attack parameters whose values are unknown to the attacked system. For the first time, necessary and sufficient conditions are provided under which the transformations provide a guaranteed attack performance in terms of Cramer-Rao Bound (CRB) regardless of the processing the estimation system employs, thus defining a highly desirable attack. Interestingly, these conditions imply that, for any such attack when the attacked sensors can be perfectly identified by the estimation system, either the Fisher Information Matrix (FIM) for jointly estimating the desired and attack parameters is singular or that the attacked system is unable to improve the CRB for the desired vector parameter through this joint estimation even though the joint FIM is nonsingular. It is shown that it is always possible to construct such a highly desirable attack by properly employing a sufficiently large dimension attack vector parameter relative to the number of quantization levels employed, which was not observed previously. To illustrate the theory in a concrete way, we also provide some numerical results which corroborate that under the highly desirable attack, attacked data is not useful in reducing the CRB.
EventNet Version 1.1 Technical Report
Venue: arXiv cs.CV 2016
Year: 2016

EventNet is a large-scale video corpus and event ontology consisting of 500 events associated with event-specific concepts. In order to improve the quality of the current EventNet, we conduct the following steps and introduce EventNet version 1.1: (1) manually verify the correctness of event labels for all videos; (2) remove the YouTube user bias by limiting the maximum number of videos in each event from the same YouTube user as 3; (3) remove the videos which are currently not accessible online; (4) remove the video belonging to multiple event categories. After the above procedure, some events may contain only a small number of videos, and therefore we crawl more videos for those events to ensure every event will contain more than 50 videos. Finally, EventNet version 1.1 contains 67,641 videos, 500 events, and 5,028 event-specific concepts. In addition, we train a Convolutional Neural Network (CNN) model for event classification via fine-tuning AlexNet using EventNet version 1.1. Then we use the trained CNN model to extract FC7 layer feature and train binary classifiers using linear SVM for each event-specific concept. We believe this new version of EventNet will significantly facilitate research in computer vision and multimedia, and will put it online for public downloading in the future.
Differences between Industrial Models of Autonomy and Systemic Models of Autonomy
Venue: arXiv cs.AI 2016
Year: 2016

This paper discusses the idea of levels of autonomy of systems - be this technical or organic - and compares the insights with models employed by industries used to describe maturity and capability of their products.
Cell planning for mobility management in heterogeneous cellular networks
Venue: arXiv cs.NI 2016
Year: 2016

In small cell networks, high mobility of users results in frequent handoff and thus severely restricts the data rate for mobile users. To alleviate this problem, we propose to use heterogeneous, two-tier network structure where static users are served by both macro and micro base stations, whereas the mobile (i.e., moving) users are served only by macro base stations having larger cells; the idea is to prevent frequent data outage for mobile users due to handoff. We use the classical two-tier Poisson network model with different transmit powers (cf [1]), assume independent Poisson process of static users and doubly stochastic Poisson process of mobile users moving at a constant speed along infinite straight lines generated by a Poisson line process. Using stochastic geometry, we calculate the average downlink data rate of the typical static and mobile (i.e., moving) users, the latter accounted for handoff outage periods. We consider also the average throughput of these two types of users defined as their average data rates divided by the mean total number of users co-served by the same base station. We find that if the density of a homogeneous network and/or the speed of mobile users is high, it is advantageous to let the mobile users connect only to some optimal fraction of BSs to reduce the frequency of handoffs during which the connection is not assured. If a heterogeneous structure of the network is allowed, one can further jointly optimize the mean throughput of mobile and static users by appropriately tuning the powers of micro and macro base stations subject to some aggregate power constraint ensuring unchanged mean data rates of static users via the network equivalence property (see [2]).
Unbeatable Set Consensus via Topological and Combinatorial Reasoning
Venue: arXiv cs.DC 2016
Year: 2016

The set consensus problem has played an important role in the study of distributed systems for over two decades. Indeed, the search for lower bounds and impossibility results for this problem spawned the topological approach to distributed computing, which has given rise to new techniques in the design and analysis of protocols. The design of efficient solutions to set consensus has also proven to be challenging. In the synchronous crash failure model, the literature contains a sequence of solutions to set consensus, each improving upon the previous ones. This paper presents an unbeatable protocol for nonuniform k-set consensus in the synchronous crash failure model. This is an efficient protocol whose decision times cannot be improved upon. Moreover, the description of our protocol is extremely succinct. Proving unbeatability of this protocol is a nontrivial challenge. We provide two proofs for its unbeatability: one is a subtle constructive combinatorial proof, and the other is a topological proof of a new style. These two proofs provide new insight into the connection between topological reasoning and combinatorial reasoning about protocols, which has long been a subject of interest. In particular, our topological proof reasons in a novel way about subcomplexes of the protocol complex, and sheds light on an open question posed by Guerraoui and Pochon (2009). Finally, using the machinery developed in the design of this unbeatable protocol, we propose a protocol for uniform k-set consensus that beats all known solutions by a large margin.
Consistency Analysis for the Doubly Stochastic Dirichlet Process
Venue: arXiv cs.IT 2016
Year: 2016

This technical report proves components consistency for the Doubly Stochastic Dirichlet Process with exponential convergence of posterior probability. We also present the fundamental properties for DSDP as well as inference algorithms. Simulation toy experiment and real-world experiment results for single and multi-cluster also support the consistency proof. This report is also a support document for the paper "Computationally Efficient Hyperspectral Data Learning Based on the Doubly Stochastic Dirichlet Process".
Experiments in Linear Template Combination using Genetic Algorithms
Venue: arXiv cs.CL 2016
Year: 2016

Natural Language Generation systems typically have two parts - strategic ('what to say') and tactical ('how to say'). We present our experiments in building an unsupervised corpus-driven template based tactical NLG system. We consider templates as a sequence of words containing gaps. Our idea is based on the observation that templates are grammatical locally (within their textual span). We posit the construction of a sentence as a highly restricted sequence of such templates. This work is an attempt to explore the resulting search space using Genetic Algorithms to arrive at acceptable solutions. We present a baseline implementation of this approach which outputs gapped text.
Phase recovery in NMF for audio source separation: an insightful benchmark
Venue: arXiv cs.SD 2016
Year: 2016

Nonnegative Matrix Factorization (NMF) is a powerful tool for decomposing mixtures of audio signals in the Time-Frequency (TF) domain. In applications such as source separation, the phase recovery for each extracted component is a major issue since it often leads to audible artifacts. In this paper, we present a methodology for evaluating various NMF-based source separation techniques involving phase reconstruction. For each model considered, a comparison between two approaches (blind separation without prior information and oracle separation with supervised model learning) is performed, in order to inquire about the room for improvement for the estimation methods. Experimental results show that the High Resolution NMF (HRNMF) model is particularly promising, because it is able to take phases and correlations over time into account with a great expressive power.
Robust phase retrieval with the swept approximate message passing (prSAMP) algorithm
Venue: arXiv cs.IT 2016
Year: 2016

In phase retrieval, the goal is to recover a complex signal from the magnitude of its linear measurements. While many well-known algorithms guarantee deterministic recovery of the unknown signal using i.i.d. random measurement matrices, they suffer serious convergence issues some ill-conditioned matrices. As an example, this happens in optical imagers using binary intensity-only spatial light modulators to shape the input wavefront. The problem of ill-conditioned measurement matrices has also been a topic of interest for compressed sensing researchers during the past decade. In this paper, using recent advances in generic compressed sensing, we propose a new phase retrieval algorithm that well-adopts for both Gaussian i.i.d. and binary matrices using both sparse and dense input signals. This algorithm is also robust to the strong noise levels found in some imaging applications.
Learning Purposeful Behaviour in the Absence of Rewards
Venue: arXiv cs.LG 2016
Year: 2016

Artificial intelligence is commonly defined as the ability to achieve goals in the world. In the reinforcement learning framework, goals are encoded as reward functions that guide agent behaviour, and the sum of observed rewards provide a notion of progress. However, some domains have no such reward signal, or have a reward signal so sparse as to appear absent. Without reward feedback, agent behaviour is typically random, often dithering aimlessly and lacking intentionality. In this paper we present an algorithm capable of learning purposeful behaviour in the absence of rewards. The algorithm proceeds by constructing temporally extended actions (options), through the identification of purposes that are "just out of reach" of the agent's current behaviour. These purposes establish intrinsic goals for the agent to learn, ultimately resulting in a suite of behaviours that encourage the agent to visit different parts of the state space. Moreover, the approach is particularly suited for settings where rewards are very sparse, and such behaviours can help in the exploration of the environment until reward is observed.
On model architecture for a children's speech recognition interactive dialog system
Venue: arXiv cs.HC 2016
Year: 2016

This report presents a general model of the architecture of information systems for the speech recognition of children. It presents a model of the speech data stream and how it works. The result of these studies and presented veins architectural model shows that research needs to be focused on acoustic-phonetic modeling in order to improve the quality of children's speech recognition and the sustainability of the systems to noise and changes in transmission environment. Another important aspect is the development of more accurate algorithms for modeling of spontaneous child speech.
iStar 2.0 Language Guide
Venue: arXiv cs.SE 2016
Year: 2016

The i* modeling language was introduced to fill the gap in the spectrum of conceptual modeling languages, focusing on the intentional (why?), social (who?), and strategic (how? how else?) dimensions. i* has been applied in many areas, e.g., healthcare, security analysis, eCommerce. Although i* has seen much academic application, the diversity of extensions and variations can make it difficult for novices to learn and use it in a consistent way. This document introduces the iStar 2.0 core language, evolving the basic concepts of i* into a consistent and clear set of core concepts, upon which to build future work and to base goal-oriented teaching materials. This document was built from a set of discussions and input from various members of the i* community. It is our intention to revisit, update and expand the document after collecting examples and concrete experiences with iStar 2.0.