OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Sensor Scheduling for Multiple Linear Dynamical Systems
Venue: arXiv cs.SY 2016
Year: 2016

We consider the design of an optimal collision-free sensor schedule for a number of sensors which monitor different linear dynamical systems correspondingly. At each time, only one of all the sensors can send its local estimate to the remote estimator. A preliminary work for the two-sensor scheduling case has been studied in the literature. The generalization into multiple-sensor scheduling case is shown to be nontrivial. We first find a necessary condition of the optimal solution provided that the spectral radii of any two system matrices are not equal, which can significantly reduce the feasible optimal solution space without loss of performance. By modelling a finite-state Markov decision process (MDP) problem, we can numerically search an asymptotic periodic schedule which is proven to be optimal. From a practical viewpoint, the computational complexity is formidable for some special system models, e.g., the spectral radii of some certain system matrices are far from others'. Some simple but effective suboptimal schedules for any systems are proposed. We also find a lower bound of the optimal cost, which enables us to quantify the performance gap between any suboptimal schedule and the optimal one.
Query-Based Entailment and Inseparability for ALC Ontologies (Full Version)
Venue: arXiv cs.LO 2016
Year: 2016

We investigate the problem whether two ALC knowledge bases are indistinguishable by queries over a given vocabulary. We give model-theoretic criteria in terms of (partial) homomorphisms and products and prove that this problem is undecidable for conjunctive queries (CQs) but 2EXPTIME-complete for UCQs (unions of CQs). The same results hold if CQs are replaced by rooted CQs. We also consider the problem whether two ALC TBoxes give the same answers to any query in a given vocabulary over all ABoxes, and show that for CQs this problem is undecidable, too, but becomes decidable and 2EXPTIME-complete in Horn-ALC, and even EXPTIME-complete in Horn-ALC when restricted to (unions of) rooted CQs.
Advances in Run-Time Performance and Interoperability for the Adapteva Epiphany Coprocessor
Venue: arXiv cs.DC 2016
Year: 2016

The energy-efficient Adapteva Epiphany architecture exhibits massive many-core scalability in a physically compact 2D array of RISC cores with a fast network-on-chip (NoC). The architecture presents many features and constraints which contribute to software design challenges for the application developer. Addressing these challenges within the software stack that supports application development is critical to improving productivity and expanding the range of applications for the architecture. We report here on advances that have been made in the COPRTHR-2 software stack targeting the Epiphany architecture that address critical issues identified in previous work. Specifically, we describe improvements that bring greater control and precision to the design of compact compiled binary programs in the context of the limited per-core local memory of the architecture. We describe a new design for run-time support that has been implemented to dramatically improve the program load and execute performance and capabilities. Finally, we describe developments that advance host-coprocessor interoperability to expand the functionality available to the application developer.
Fast Two-Robot Disk Evacuation with Wireless Communication
Venue: arXiv cs.DC 2016
Year: 2016

In the fast evacuation problem, we study the path planning problem for two robots who want to minimize the worst-case evacuation time on the unit disk. The robots are initially placed at the center of the disk. In order to evacuate, they need to reach an unknown point, the exit, on the boundary of the disk. Once one of the robots finds the exit, it will instantaneously notify the other agent, who will make a beeline to it. The problem has been studied for robots with the same speed~\cite{s1}. We study a more general case where one robot has speed $1$ and the other has speed $s \geq 1$. We provide optimal evacuation strategies in the case that $s \geq c_{2.75} \approx 2.75$ by showing matching upper and lower bounds on the worst-case evacuation time. For $1\leq s < c_{2.75}$, we show (non-matching) upper and lower bounds on the evacuation time with a ratio less than $1.22$. Moreover, we demonstrate that a generalization of the two-robot search strategy from~\cite{s1} is outperformed by our proposed strategies for any $s \geq c_{1.71} \approx 1.71$.
Efficient Reduced-Rank DOA Estimation Algorithms Using Alternating Low-Rank Decompositions
Venue: arXiv cs.IT 2016
Year: 2016

In this work, we propose an alternating low-rank decomposition (ALRD) approach and novel subspace algorithms for direction-of-arrival (DOA) estimation. In the ALRD scheme, the decomposition matrix for rank reduction is composed of a set of basis vectors. A low-rank auxiliary parameter vector is then employed to compute the output power spectrum. Alternating optimization strategies based on recursive least squares (RLS), denoted as ALRD-RLS and modified ALRD-RLS (MARLD-RLS), are devised to compute the basis vectors and the auxiliary parameter vector. Simulations for large sensor arrays with both uncorrelated and correlated sources are presented, showing that the proposed algorithms are superior to existing techniques.
Latent Model Ensemble with Auto-localization
Venue: arXiv cs.CV 2016
Year: 2016

Deep Convolutional Neural Networks (CNN) have exhibited superior performance in many visual recognition tasks including image classification, object detection, and scene label- ing, due to their large learning capacity and resistance to overfit. For the image classification task, most of the current deep CNN- based approaches take the whole size-normalized image as input and have achieved quite promising results. Compared with the previously dominating approaches based on feature extraction, pooling, and classification, the deep CNN-based approaches mainly rely on the learning capability of deep CNN to achieve superior results: the burden of minimizing intra-class variation while maximizing inter-class difference is entirely dependent on the implicit feature learning component of deep CNN; we rely upon the implicitly learned filters and pooling component to select the discriminative regions, which correspond to the activated neurons. However, if the irrelevant regions constitute a large portion of the image of interest, the classification performance of the deep CNN, which takes the whole image as input, can be heavily affected. To solve this issue, we propose a novel latent CNN framework, which treats the most discriminate region as a latent variable. We can jointly learn the global CNN with the latent CNN to avoid the aforementioned big irrelevant region issue, and our experimental results show the evident advantage of the proposed latent CNN over traditional deep CNN: latent CNN outperforms the state-of-the-art performance of deep CNN on standard benchmark datasets including the CIFAR-10, CIFAR- 100, MNIST and PASCAL VOC 2007 Classification dataset.
Construction of de Bruijn Sequences from Product of Two Irreducible Polynomials
Venue: arXiv cs.IT 2016
Year: 2016

We study a class of Linear Feedback Shift Registers (LFSRs) with characteristic polynomial $f(x)=p(x)q(x)$ where $p(x)$ and $q(x)$ are distinct irreducible polynomials in $\F_2[x]$. Important properties of the LFSRs, such as the cycle structure and the adjacency graph, are derived. A method to determine a state belonging to each cycle and a generic algorithm to find all conjugate pairs shared by any pair of cycles are given. The process explicitly determines the edges and their labels in the adjacency graph. The results are then combined with the cycle joining method to efficiently construct a new class of de Bruijn sequences. An estimate of the number of resulting sequences is given. In some cases, using cyclotomic numbers, we can determine the number exactly.
Composition of Deep and Spiking Neural Networks for Very Low Bit Rate Speech Coding
Venue: arXiv cs.SD 2016
Year: 2016

Most current very low bit rate (VLBR) speech coding systems use hidden Markov model (HMM) based speech recognition/synthesis techniques. This allows transmission of information (such as phonemes) segment by segment that decreases the bit rate. However, the encoder based on a phoneme speech recognition may create bursts of segmental errors. Segmental errors are further propagated to optional suprasegmental (such as syllable) information coding. Together with the errors of voicing detection in pitch parametrization, HMM-based speech coding creates speech discontinuities and unnatural speech sound artefacts. In this paper, we propose a novel VLBR speech coding framework based on neural networks (NNs) for end-to-end speech analysis and synthesis without HMMs. The speech coding framework relies on phonological (sub-phonetic) representation of speech, and it is designed as a composition of deep and spiking NNs: a bank of phonological analysers at the transmitter, and a phonological synthesizer at the receiver, both realised as deep NNs, and a spiking NN as an incremental and robust encoder of syllable boundaries for coding of continuous fundamental frequency (F0). A combination of phonological features defines much more sound patterns than phonetic features defined by HMM-based speech coders, and the finer analysis/synthesis code contributes into smoother encoded speech. Listeners significantly prefer the NN-based approach due to fewer discontinuities and speech artefacts of the encoded speech. A single forward pass is required during the speech encoding and decoding. The proposed VLBR speech coding operates at a bit rate of approximately 360 bits/s.
Bayesian linear regression with Student-t assumptions
Venue: arXiv cs.LG 2016
Year: 2016

As an automatic method of determining model complexity using the training data alone, Bayesian linear regression provides us a principled way to select hyperparameters. But one often needs approximation inference if distribution assumption is beyond Gaussian distribution. In this paper, we propose a Bayesian linear regression model with Student-t assumptions (BLRS), which can be inferred exactly. In this framework, both conjugate prior and expectation maximization (EM) algorithm are generalized. Meanwhile, we prove that the maximum likelihood solution is equivalent to the standard Bayesian linear regression with Gaussian assumptions (BLRG). The $q$-EM algorithm for BLRS is nearly identical to the EM algorithm for BLRG. It is showed that $q$-EM for BLRS can converge faster than EM for BLRG for the task of predicting online news popularity.
Iterative computational identification of a spacewise dependent the source in a parabolic equations
Venue: arXiv cs.NA 2016
Year: 2016

Coefficient inverse problems related to identifying the right-hand side of an equation with use of additional information is of interest among inverse problems for partial differential equations. When considering non-stationary problems, tasks of recovering the dependence of the right-hand side on time and spatial variables can be treated as independent. These tasks relate to a class of linear inverse problems, which sufficiently simplifies their study. This work is devoted to a finding the dependence of right-hand side of multidimensional parabolic equation on spatial variables using additional observations of the solution at the final point of time - the final overdetermination. More general problems are associated with some integral observation of the solution on time - the integral overdetermination. The first method of numerical solution of inverse problems is based on iterative solution of boundary value problem for time derivative with non-local acceleration. The second method is based on the known approach with iterative refinement of desired dependence of the right-hand side on spacial variables. Capabilities of proposed methods are illustrated by numerical examples for model two-dimensional problem of identifying the right-hand side of a parabolic equation. The standard finite-element approximation on space is used, the time discretization is based on fully implicit two-level schemes.
Delta divergence: A novel decision cognizant measure of classifier incongruence
Venue: arXiv cs.LG 2016
Year: 2016

Disagreement between two classifiers regarding the class membership of an observation in pattern recognition can be indicative of an anomaly and its nuance. As in general classifiers base their decision on class aposteriori probabilities, the most natural approach to detecting classifier incongruence is to use divergence. However, existing divergences are not particularly suitable to gauge classifier incongruence. In this paper, we postulate the properties that a divergence measure should satisfy and propose a novel divergence measure, referred to as Delta divergence. In contrast to existing measures, it is decision cognizant. The focus in Delta divergence on the dominant hypotheses has a clutter reducing property, the significance of which grows with increasing number of classes. The proposed measure satisfies other important properties such as symmetry, and independence of classifier confidence. The relationship of the proposed divergence to some baseline measures is demonstrated experimentally, showing its superiority.
Do the Contemporary Cubature and Unscented Kalman Filtering Methods Outperform Always the Traditional Extended Kalman Filter?
Venue: arXiv cs.SY 2016
Year: 2016

This brief technical note elaborates three well-known state estimators, which are used extensively in practice. These are the rather old-fashioned extended Kalman filter (EKF) and the recently-designed cubature Kalman filtering (CKF) and unscented Kalman filtering (UKF) algorithms. Nowadays, it is commonly accepted that the contemporary techniques outperform always the traditional EKF in the accuracy of state estimation because of the higher-order approximation of the mean of propagated Gaussian density in the time- and measurement-update steps of the listed filters. However, the present paper specifies this commonly accepted opinion and shows that despite the mentioned theoretical fact the EKF may outperform the CKF and UKF methods in the accuracy of state estimation when the stochastic system under consideration exposes a stiff behavior. That is why stiff stochastic models are difficult to deal with and require effective state estimation techniques to be designed yet.
Extracting Patterns of Urban Activity from Geotagged Social Data
Venue: arXiv cs.CY 2016
Year: 2016

Data generated on location-based social networks provide rich information on the whereabouts of urban dwellers. Specifically, such data reveal who spends time where, when, and on what type of activity (e.g., shopping at a mall, or dining at a restaurant). That information can, in turn, be used to describe city regions in terms of activity that takes place therein. For example, the data might reveal that citizens visit one region mainly for shopping in the morning, while another for dining in the evening. Furthermore, once such a description is available, one can ask more elaborate questions: What are the features that distinguish one region from another -- is it simply the type of venues they host or is it the visitors they attract? What regions are similar across cities? In this paper, we attempt to answer these questions using publicly shared Foursquare data. In contrast with previous work, our method makes use of a probabilistic model with minimal assumptions about the data and thus relieves us from having to make arbitrary decisions in our analysis (e.g., regarding the granularity of discovered regions or the importance of different features). We perform an empirical comparison with previous work and discuss insights obtained through our findings.
Two Pairwise Iterative Schemes For High Dimensional Blind Source Separation
Venue: arXiv cs.SD 2016
Year: 2016

This paper addresses the high dimensionality problem in blind source separation (BSS), where the number of sources is greater than two. Two pairwise iterative schemes are proposed to tackle this high dimensionality problem. The two pairwise schemes realize nonparametric independent component analysis (ICA) algorithms based on a new high-performance Convex CauchySchwarz Divergence (CCSDIV). These two schemes enable fast and efficient demixing of sources in real-world high dimensional source applications. Finally, the performance superiority of the proposed schemes is demonstrated in metric-comparison with FastICA, RobustICA, convex ICA (CICA), and other leading existing algorithms.
Radon Features and Barcodes for Medical Image Retrieval via SVM
Venue: arXiv cs.CV 2016
Year: 2016

For more than two decades, research has been performed on content-based image retrieval (CBIR). By combining Radon projections and the support vector machines (SVM), a content-based medical image retrieval method is presented in this work. The proposed approach employs the normalized Radon projections with corresponding image category labels to build an SVM classifier, and the Radon barcode database which encodes every image in a binary format is also generated simultaneously to tag all images. To retrieve similar images when a query image is given, Radon projections and the barcode of the query image are generated. Subsequently, the k-nearest neighbor search method is applied to find the images with minimum Hamming distance of the Radon barcode within the same class predicted by the trained SVM classifier that uses Radon features. The performance of the proposed method is validated by using the IRMA 2009 dataset with 14,410 x-ray images in 57 categories. The results demonstrate that our method has the capacity to retrieve similar responses for the correctly identified query image and even for those mistakenly classified by SVM. The approach further is very fast and has low memory requirement.
Hacking in the Blind: (Almost) Invisible Runtime UI Attacks on Safety-Critical Terminals
Venue: arXiv cs.CR 2016
Year: 2016

Many terminals are used in safety-critical operations in which humans, through terminal user interfaces, become a part of the system control loop (e.g., medical and industrial systems). These terminals are typically embedded, single-purpose devices with restricted functionality, sometimes air-gapped and increasingly hardened. We describe a new way of attacking such terminals in which an adversary has only temporary, non-invasive, physical access to the terminal. In this attack, the adversary attaches a small device to the interface that connects user input peripherals to the terminal. The device executes the attack when the authorized user is performing safety-critical operations, by modifying or blocking user input, or injecting new input events. Given that the attacker has access to user input, the execution of this attack might seem trivial. However, to succeed, the attacker needs to overcome a number of challenges including the inability to directly observe the user interface and avoid being detected by the users. We present techniques that allow user interface state and input tracking. We evaluate these techniques and show that they can be implemented efficiently. We further evaluate the effectiveness of our attack through an online user study and find input modification attacks that are hard for the users to detect and would therefore lead to serious violations of the input integrity.
Intra-Team Strategies for Teams Negotiating Against Competitor, Matchers, and Conceders
Venue: arXiv cs.MA 2016
Year: 2016

Under some circumstances, a group of individuals may need to negotiate together as a negotiation team against another party. Unlike bilateral negotiation between two individuals, this type of negotiations entails to adopt an intra-team strategy for negotiation teams in order to make team decisions and accordingly negotiate with the opponent. It is crucial to be able to negotiate successfully with heterogeneous opponents since opponents' negotiation strategy and behavior may vary in an open environment. While one opponent might collaborate and concede over time, another may not be inclined to concede. This paper analyzes the performance of recently proposed intra-team strategies for negotiation teams against different categories of opponents: competitors, matchers, and conceders. Furthermore, it provides an extension of the negotiation tool Genius for negotiation teams in bilateral settings. Consequently, this work facilitates research in negotiation teams.
Abstract Graph Machine
Venue: arXiv cs.DC 2016
Year: 2016

An Abstract Graph Machine(AGM) is an abstract model for distributed memory parallel stabilizing graph algorithms. A stabilizing algorithm starts from a particular initial state and goes through series of different state changes until it converges. The AGM adds work dependency to the stabilizing algorithm. The work is processed within the processing function. All processes in the system execute the same processing function. Before feeding work into the processing function, work is ordered using a strict weak ordering relation. The strict weak ordering relation divides work into equivalence classes, hence work within a single equivalence class can be processed in parallel, but work in different equivalence classes must be executed in the order they appear in equivalence classes. The paper presents the AGM model, semantics and AGM models for several existing distributed memory parallel graph algorithms.
Robust Monocular Flight in Cluttered Outdoor Environments
Venue: arXiv cs.RO 2016
Year: 2016

Recently, there have been numerous advances in the development of biologically inspired lightweight Micro Aerial Vehicles (MAVs). While autonomous navigation is fairly straight-forward for large UAVs as expensive sensors and monitoring devices can be employed, robust methods for obstacle avoidance remains a challenging task for MAVs which operate at low altitude in cluttered unstructured environments. Due to payload and power constraints, it is necessary for such systems to have autonomous navigation and flight capabilities using mostly passive sensors such as cameras. In this paper, we describe a robust system that enables autonomous navigation of small agile quad-rotors at low altitude through natural forest environments. We present a direct depth estimation approach that is capable of producing accurate, semi-dense depth-maps in real time. Furthermore, a novel wind-resistant control scheme is presented that enables stable way-point tracking even in the presence of strong winds. We demonstrate the performance of our system through extensive experiments on real images and field tests in a cluttered outdoor environment.