OpenRaiser/Intern-Atlas huggingface dataset:
Learning-based Formal Synthesis of Cooperative Multi-agent Systems
Venue: arXiv cs.SY 2017
Year: 2017

We propose a formal design framework for synthesizing coordination and control policies for cooperative multi-agent systems to accomplish a global mission. The global performance requirements are specified as regular languages while dynamics of each agent as well as the shared environment are characterized by finite automata, upon on which a formal design approach is carried out via divide-and-conquer. Specifically, the global mission is decomposed into local tasks; and local mission supervisors are designed to accomplish these local tasks while maintaining the multi-agent performance by integrating supervisor synthesis with compositional verification techniques; finally, motion plans are automatically synthesized based on the obtained mission plans. We present three modifications of the L* learning algorithm such that they are adapted for the synthesis of the local mission supervisors, the compositional verification and the synthesis of local motion plans, to guarantee that the collective behavior of the agents will ensure the satisfaction of the global specification. Furthermore, the effectiveness of the proposed framework is demonstrated by a detailed experimental study based on the implementation of a multi-robot coordination scenario. The proposed hardware-software architecture, with each robot's communication and localization capabilities, is exploited to examine the automatic supervisor synthesis with inter-robot communication.
Robust Tracking Using Region Proposal Networks
Venue: arXiv cs.CV 2017
Year: 2017

Recent advances in visual tracking showed that deep Convolutional Neural Networks (CNN) trained for image classification can be strong feature extractors for discriminative trackers. However, due to the drastic difference between image classification and tracking, extra treatments such as model ensemble and feature engineering must be carried out to bridge the two domains. Such procedures are either time consuming or hard to generalize well across datasets. In this paper we discovered that the internal structure of Region Proposal Network (RPN)'s top layer feature can be utilized for robust visual tracking. We showed that such property has to be unleashed by a novel loss function which simultaneously considers classification accuracy and bounding box quality. Without ensemble and any extra treatment on feature maps, our proposed method achieved state-of-the-art results on several large scale benchmarks including OTB50, OTB100 and VOT2016. We will make our code publicly available.
A Faster Construction of Greedy Consensus Trees
Venue: arXiv cs.DS 2017
Year: 2017

A consensus tree is a phylogenetic tree that captures the similarity between a set of conflicting phylogenetic trees. The problem of computing a consensus tree is a major step in phylogenetic tree reconstruction. It also finds applications in predicting a species tree from a set of gene trees. This paper focuses on two of the most well-known and widely used oconsensus tree methods: the greedy consensus tree and the frequency difference consensus tree. Given $k$ conflicting trees each with $n$ leaves, the previous fastest algorithms for these problems were $O(k n^2)$ for the greedy consensus tree [J. ACM 2016] and $\tilde O(\min \{ k n^2, k^2n\})$ for the frequency difference consensus tree [ACM TCBB 2016]. We improve these running times to $\tilde O(k n^{1.5})$ and $\tilde O(k n)$ respectively.
Distributed Matrix Factorization using Asynchrounous Communication
Venue: arXiv cs.DC 2017
Year: 2017

Using the matrix factorization technique in machine learning is very common mainly in areas like recommender systems. Despite its high prediction accuracy and its ability to avoid over-fitting of the data, the Bayesian Probabilistic Matrix Factorization algorithm (BPMF) has not been widely used on large scale data because of the prohibitive cost. In this paper, we propose a distributed high-performance parallel implementation of the BPMF using Gibbs sampling on shared and distributed architectures. We show by using efficient load balancing using work stealing on a single node, and by using asynchronous communication in the distributed version we beat state of the art implementations.
Grammatical Inference as a Satisfiability Modulo Theories Problem
Venue: arXiv cs.FL 2017
Year: 2017

The problem of learning a minimal consistent model from a set of labeled sequences of symbols is addressed from a satisfiability modulo theories perspective. We present two encodings for deterministic finite automata and extend one of these for Moore and Mealy machines. Our experimental results show that these encodings improve upon the state-of-the-art, and are useful in practice for learning small models.
Pumping Lemma for Higher-order Languages
Venue: arXiv cs.FL 2017
Year: 2017

We study a pumping lemma for the word/tree languages generated by higher-order grammars. Pumping lemmas are known up to order-2 word languages (i.e., for regular/context-free/indexed languages), and have been used to show that a given language does not belong to the classes of regular/context-free/indexed languages. We prove a pumping lemma for word/tree languages of arbitrary orders, modulo a conjecture that a higher-order version of Kruskal's tree theorem holds. We also show that the conjecture indeed holds for the order-2 case, which yields a pumping lemma for order-2 tree languages and order-3 word languages.
Towards an ASM thesis for reflective sequential algorithms
Venue: arXiv cs.LO 2017
Year: 2017

Starting from Gurevich's thesis for sequential algorithms (the so-called "sequential ASM thesis"), we propose a characterization of the behaviour of sequential algorithms enriched with reflection. That is, we present a set of postulates which we conjecture capture the fundamental properties of reflective sequential algorithms (RSAs). Then we look at the plausibility of an ASM thesis for the class of RSAs, defining a model of abstract state machine (which we call reflective ASM) that we conjecture captures the class of RSAs as defined by our postulates.
Low Impact Artificial Intelligences
Venue: arXiv cs.AI 2017
Year: 2017

There are many goals for an AI that could become dangerous if the AI becomes superintelligent or otherwise powerful. Much work on the AI control problem has been focused on constructing AI goals that are safe even for such AIs. This paper looks at an alternative approach: defining a general concept of `low impact'. The aim is to ensure that a powerful AI which implements low impact will not modify the world extensively, even if it is given a simple or dangerous goal. The paper proposes various ways of defining and grounding low impact, and discusses methods for ensuring that the AI can still be allowed to have a (desired) impact despite the restriction. The end of the paper addresses known issues with this approach and avenues for future research.
A Multi-Layer K-means Approach for Multi-Sensor Data Pattern Recognition in Multi-Target Localization
Venue: arXiv cs.SY 2017
Year: 2017

Data-target association is an important step in multi-target localization for the intelligent operation of un- manned systems in numerous applications such as search and rescue, traffic management and surveillance. The objective of this paper is to present an innovative data association learning approach named multi-layer K-means (MLKM) based on leveraging the advantages of some existing machine learning approaches, including K-means, K-means++, and deep neural networks. To enable the accurate data association from different sensors for efficient target localization, MLKM relies on the clustering capabilities of K-means++ structured in a multi-layer framework with the error correction feature that is motivated by the backpropogation that is well-known in deep learning research. To show the effectiveness of the MLKM method, numerous simulation examples are conducted to compare its performance with K-means, K-means++, and deep neural networks.
Accelerating Neural Architecture Search using Performance Prediction
Venue: arXiv cs.LG 2017
Year: 2017

Methods for neural network hyperparameter optimization and meta-modeling are computationally expensive due to the need to train a large number of model configurations. In this paper, we show that standard frequentist regression models can predict the final performance of partially trained model configurations using features based on network architectures, hyperparameters, and time-series validation performance data. We empirically show that our performance prediction models are much more effective than prominent Bayesian counterparts, are simpler to implement, and are faster to train. Our models can predict final performance in both visual classification and language modeling domains, are effective for predicting performance of drastically varying model architectures, and can even generalize between model classes. Using these prediction models, we also propose an early stopping method for hyperparameter optimization and meta-modeling, which obtains a speedup of a factor up to 6x in both hyperparameter optimization and meta-modeling. Finally, we empirically show that our early stopping method can be seamlessly incorporated into both reinforcement learning-based architecture selection algorithms and bandit based search methods. Through extensive experimentation, we empirically show our performance prediction models and early stopping algorithm are state-of-the-art in terms of prediction accuracy and speedup achieved while still identifying the optimal model configurations.
Estimating Human Intent for Physical Human-Robot Co-Manipulation
Venue: arXiv cs.RO 2017
Year: 2017

Human teams can be exceptionally efficient at adapting and collaborating during manipulation tasks using shared mental models. However, the same shared mental models that can be used by humans to perform robust low-level force and motion control during collaborative manipulation tasks are non-existent for robots. For robots to perform collaborative tasks with people naturally and efficiently, understanding and predicting human intent is necessary. However, humans are difficult to predict and model. We have completed an exploratory study recording motion and force for 20 human dyads moving an object in tandem in order to better understand how they move and how their movement can be predicted. In this paper, we show how past motion data can be used to predict human intent. In order to predict human intent, which we equate with the human team's velocity for a short time horizon, we used a neural network. Using the previous 150 time steps at a rate of 200 Hz, human intent can be predicted for the next 50 time steps with a mean squared error of 0.02 (m/s)^2. We also show that human intent can be estimated in a human-robot dyad. This work is an important first step in enabling future work of integrating human intent estimation on a robot controller to execute a short-term collaborative trajectory.
Weakly supervised 3D Reconstruction with Adversarial Constraint
Venue: arXiv cs.CV 2017
Year: 2017

Supervised 3D reconstruction has witnessed a significant progress through the use of deep neural networks. However, this increase in performance requires large scale annotations of 2D/3D data. In this paper, we explore inexpensive 2D supervision as an alternative for expensive 3D CAD annotation. Specifically, we use foreground masks as weak supervision through a raytrace pooling layer that enables perspective projection and backpropagation. Additionally, since the 3D reconstruction from masks is an ill posed problem, we propose to constrain the 3D reconstruction to the manifold of unlabeled realistic 3D shapes that match mask observations. We demonstrate that learning a log-barrier solution to this constrained optimization problem resembles the GAN objective, enabling the use of existing tools for training GANs. We evaluate and analyze the manifold constrained reconstruction on various datasets for single and multi-view reconstruction of both synthetic and real images.
Design of Deep Neural Networks as Add-on Blocks for Improving Impromptu Trajectory Tracking
Venue: arXiv cs.RO 2017
Year: 2017

This paper introduces deep neural networks (DNNs) as add-on blocks to baseline feedback control systems to enhance tracking performance of arbitrary desired trajectories. The DNNs are trained to adapt the reference signals to the feedback control loop. The goal is to achieve a unity map between the desired and the actual outputs. In previous work, the efficacy of this approach was demonstrated on quadrotors; on 30 unseen test trajectories, the proposed DNN approach achieved an average impromptu tracking error reduction of 43% as compared to the baseline feedback controller. Motivated by these results, this work aims to provide platform-independent design guidelines for the proposed DNN-enhanced control architecture. In particular, we provide specific guidelines for the DNN feature selection, derive conditions for when the proposed approach is effective, and show in which cases the training efficiency can be further increased.
Effective Target Aware Visual Navigation for UAVs
Venue: arXiv cs.RO 2017
Year: 2017

In this paper we propose an effective vision-based navigation method that allows a multirotor vehicle to simultaneously reach a desired goal pose in the environment while constantly facing a target object or landmark. Standard techniques such as Position-Based Visual Servoing (PBVS) and Image-Based Visual Servoing (IBVS) in some cases (e.g., while the multirotor is performing fast maneuvers) do not allow to constantly maintain the line of sight with a target of interest. Instead, we compute the optimal trajectory by solving a non-linear optimization problem that minimizes the target re-projection error while meeting the UAV's dynamic constraints. The desired trajectory is then tracked by means of a real-time Non-linear Model Predictive Controller (NMPC): this implicitly allows the multirotor to satisfy both the required constraints. We successfully evaluate the proposed approach in many real and simulated experiments, making an exhaustive comparison with a standard approach.
Succinct Partial Sums and Fenwick Trees
Venue: arXiv cs.DS 2017
Year: 2017

We consider the well-studied partial sums problem in succint space where one is to maintain an array of n k-bit integers subject to updates such that partial sums queries can be efficiently answered. We present two succint versions of the Fenwick Tree - which is known for its simplicity and practicality. Our results hold in the encoding model where one is allowed to reuse the space from the input data. Our main result is the first that only requires nk + o(n) bits of space while still supporting sum/update in O(log_b n) / O(b log_b n) time where 2 <= b <= log^O(1) n. The second result shows how optimal time for sum/update can be achieved while only slightly increasing the space usage to nk + o(nk) bits. Beyond Fenwick Trees, the results are primarily based on bit-packing and sampling - making them very practical - and they also allow for simple optimal parallelization.
Neuron Segmentation Using Deep Complete Bipartite Networks
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we consider the problem of automatically segmenting neuronal cells in dual-color confocal microscopy images. This problem is a key task in various quantitative analysis applications in neuroscience, such as tracing cell genesis in Danio rerio (zebrafish) brains. Deep learning, especially using fully convolutional networks (FCN), has profoundly changed segmentation research in biomedical imaging. We face two major challenges in this problem. First, neuronal cells may form dense clusters, making it difficult to correctly identify all individual cells (even to human experts). Consequently, segmentation results of the known FCN-type models are not accurate enough. Second, pixel-wise ground truth is difficult to obtain. Only a limited amount of approximate instance-wise annotation can be collected, which makes the training of FCN models quite cumbersome. We propose a new FCN-type deep learning model, called deep complete bipartite networks (CB-Net), and a new scheme for leveraging approximate instance-wise annotation to train our pixel-wise prediction model. Evaluated using seven real datasets, our proposed new CB-Net model outperforms the state-of-the-art FCN models and produces neuron segmentation results of remarkable quality
On One Generalization of LRC Codes with Availability
Venue: arXiv cs.IT 2017
Year: 2017

We investigate one possible generalization of locally recoverable codes (LRC) with all-symbol locality and availability when recovering sets can intersect in a small number of coordinates. This feature allows us to increase the achievable code rate and still meet load balancing requirements. In this paper we derive an upper bound for the rate of such codes and give explicit constructions of codes with such a property. These constructions utilize LRC codes developed by Wang et al.
Mining Frequent Learning Pathways from a Large Educational Dataset
Venue: arXiv cs.CY 2017
Year: 2017

In this paper, we describe data mining techniques used to extract frequent learning pathways from a large educational dataset. These pathways were extracted as a directed graph that encoded student learning processes. Our dataset contains more than 800 million interactions of over 3 million anonymized students in an online learning platform. Performing process mining on large and complex datasets regularly yields incomprehensible process models. Although, if we cluster data and obtain groups following similar processes, we can greatly improve process mining results. To this end, we developed a sequence clustering algorithm that let us group students who followed similar learning pathways. To extract frequent learning pathways from these clusters of data, we developed a graph-based process discovery algorithm that revealed to us the sequences of learning activities that many students followed. These sequences represented highways of student learning.
Multirobot Cliff Climbing on Low-Gravity Environments
Venue: arXiv cs.RO 2017
Year: 2017

Exploration of extreme environments, including caves, canyons and cliffs on low-gravity surfaces such as the Moon, Mars and asteroids can provide insight into the geological history of the solar system, origins of water, life and prospect for future habitation and resource exploitation. Current methods of exploration utilize large rovers that are unsuitable for exploring these extreme environments. In this work, we analyze the feasibility of small, low-cost, reconfigurable multirobot systems to climb steep cliffs and canyon walls. Each robot is a 30-cm sphere covered in microspines for gripping onto rugged surfaces and attaches to several robots using a spring-tether. Even if one robot were to slip and fall, the system would be held up with multiple attachment points much like a professional alpine climber. We analyzed and performed detailed simulations of the design configuration space to identify an optimal system design that trades off climbing performance with risk of falling. Our results identify a system of 4 robots is best suited when enabling single-robot climbs, while a system of 6 robots are suited when two robots climb simultaneously. The results show a pathway towards demonstration of the system on real robots.
Are distributional representations ready for the real world? Evaluating word vectors for grounded perceptual meaning
Venue: arXiv cs.CL 2017
Year: 2017

Distributional word representation methods exploit word co-occurrences to build compact vector encodings of words. While these representations enjoy widespread use in modern natural language processing, it is unclear whether they accurately encode all necessary facets of conceptual meaning. In this paper, we evaluate how well these representations can predict perceptual and conceptual features of concrete concepts, drawing on two semantic norm datasets sourced from human participants. We find that several standard word representations fail to encode many salient perceptual features of concepts, and show that these deficits correlate with word-word similarity prediction errors. Our analyses provide motivation for grounded and embodied language learning approaches, which may help to remedy these deficits.
AirScript - Creating Documents in Air
Venue: arXiv cs.HC 2017
Year: 2017

This paper presents a novel approach, called AirScript, for creating, recognizing and visualizing documents in air. We present a novel algorithm, called 2-DifViz, that converts the hand movements in air (captured by a Myo-armband worn by a user) into a sequence of x, y coordinates on a 2D Cartesian plane, and visualizes them on a canvas. Existing sensor-based approaches either do not provide visual feedback or represent the recognized characters using prefixed templates. In contrast, AirScript stands out by giving freedom of movement to the user, as well as by providing a real-time visual feedback of the written characters, making the interaction natural. AirScript provides a recognition module to predict the content of the document created in air. To do so, we present a novel approach based on deep learning, which uses the sensor data and the visualizations created by 2-DifViz. The recognition module consists of a Convolutional Neural Network (CNN) and two Gated Recurrent Unit (GRU) Networks. The output from these three networks is fused to get the final prediction about the characters written in air. AirScript can be used in highly sophisticated environments like a smart classroom, a smart factory or a smart laboratory, where it would enable people to annotate pieces of texts wherever they want without any reference surface. We have evaluated AirScript against various well-known learning models (HMM, KNN, SVM, etc.) on the data of 12 participants. Evaluation results show that the recognition module of AirScript largely outperforms all of these models by achieving an accuracy of 91.7% in a person independent evaluation and a 96.7% accuracy in a person dependent evaluation.
U-Phylogeny: Undirected Provenance Graph Construction in the Wild
Venue: arXiv cs.CV 2017
Year: 2017

Deriving relationships between images and tracing back their history of modifications are at the core of Multimedia Phylogeny solutions, which aim to combat misinformation through doctored visual media. Nonetheless, most recent image phylogeny solutions cannot properly address cases of forged composite images with multiple donors, an area known as multiple parenting phylogeny (MPP). This paper presents a preliminary undirected graph construction solution for MPP, without any strict assumptions. The algorithm is underpinned by robust image representative keypoints and different geometric consistency checks among matching regions in both images to provide regions of interest for direct comparison. The paper introduces a novel technique to geometrically filter the most promising matches as well as to aid in the shared region localization task. The strength of the approach is corroborated by experiments with real-world cases, with and without image distractors (unrelated cases).