OpenRaiser/Intern-Atlas huggingface dataset:
The Schützenberger product for syntactic spaces
Venue: arXiv cs.LO 2016
Year: 2016

Starting from Boolean algebras of languages closed under quotients and using duality theoretic insights, we derive the notion of Boolean spaces with internal monoids as recognisers for arbitrary formal languages of finite words over finite alphabets. This leads to a setting that is well-suited for applying existing tools from Stone duality as applied in semantics. The main focus of the paper is the development of topo-algebraic constructions pertinent to the treatment of languages given by logic formulas. In particular, using the standard semantic view of quantification as projection, we derive a notion of Schützenberger product for Boolean spaces with internal monoids. This makes heavy use of the Vietoris construction, and its dual functor, which is central to the coalgebraic treatment of classical modal logic. We show that the unary Schützenberger product for spaces, when applied to a recogniser for the language associated to a formula with a free first-order variable, yields a recogniser for the language of all models of the corresponding existentially quantified formula. Further, we generalise global and local versions of the theorems of Schützenberger and Reutenauer characterising the languages recognised by the binary Schützenberger product. Finally, we provide an equational characterisation of Boolean algebras obtained by local Schützenberger product with the one element space based on an Egli-Milner type condition on generalised factorisations of ultrafilters on words.
A Stochastic Model for Quantitative Security Analyses of Networked Systems
Venue: arXiv cs.CR 2016
Year: 2016

Traditional security analyses are often geared towards cryptographic primitives or protocols. Although such analyses are necessary, they cannot address a defender's need for insight into {\em which aspects of a networked system having a significant impact on its security, and how to tune its configurations or parameters so as to improve security}. This question is known to be notoriously difficult to answer, and the state-of-the-art is that we know little about it. Towards ultimately addressing this question, this paper presents a stochastic model for quantifying security of networked systems. The resulting model captures two aspects of a networked system: (1) the strength of deployed security mechanisms such as intrusion detection systems, and (2) the underlying {\em vulnerability graph}, which reflects how attacks may proceed. The resulting model brings the following insights: (1) How should a defender "tune" system configurations (e.g., network topology) so as to improve security? (2) How should a defender "tune" system parameters (e.g., by upgrading which security mechanisms) so as to improve security? (3) Under what conditions is the steady-state number of compromised entities of interest below a given threshold with a high probability? Simulation studies are conducted to confirm the analytic results, and to show the tightness of the bounds of certain important metric that cannot be resolved analytically.
Distributed Fusion with Multi-Bernoulli Filter based on Generalized Covariance Intersection
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we propose a distributed multi-object tracking algorithm through the use of multi-Bernoulli (MB) filter based on generalized Covariance Intersection (G-CI). Our analyses show that the G-CI fusion with two MB posterior distributions does not admit an accurate closed-form expression. To solve this challenging problem, we firstly approximate the fused posterior as the unlabeled version of $δ$-generalized labeled multi-Bernoulli ($δ$-GLMB) distribution, referred to as generalized multi-Bernoulli (GMB) distribution. Then, to allow the subsequent fusion with another multi-Bernoulli posterior distribution, e.g., fusion with a third sensor node in the sensor network, or fusion in the feedback working mode, we further approximate the fused GMB posterior distribution as an MB distribution which matches its first-order statistical moment. The proposed fusion algorithm is implemented using sequential Monte Carlo technique and its performance is highlighted by numerical results.
A Note on the Computational Complexity of Unsmoothened Vertex Attack Tolerance
Venue: arXiv cs.CC 2016
Year: 2016

We have previously introduced vertex attack tolerance (VAT) and unsmoothened VAT (UVAT), denoted respectively as $τ(G) = \min_{S \subset V} \frac{|S|}{|V-S-C_{max}(V-S)|+1}$ and $\hatτ(G) = \min_{S \subset V} \frac{|S|}{|V-S-C_{max}(V-S)|}$, where $C_{max}(V-S)$ is the largest connected component in $V-S$, as appropriate mathematical measures of resilience in the face of targeted node attacks for arbitrary degree networks. Here we prove the hardness of approximating $\hatτ$ under various plausible computational complexity hypotheses.
Generalized Exponential Concentration Inequality for Rényi Divergence Estimation
Venue: arXiv cs.IT 2016
Year: 2016

Estimating divergences in a consistent way is of great importance in many machine learning tasks. Although this is a fundamental problem in nonparametric statistics, to the best of our knowledge there has been no finite sample exponential inequality convergence bound derived for any divergence estimators. The main contribution of our work is to provide such a bound for an estimator of Rényi-$α$ divergence for a smooth Hölder class of densities on the $d$-dimensional unit cube $[0, 1]^d$. We also illustrate our theoretical results with a numerical experiment.
Industrial Experiences with a Formal DSL Semantics to Check the Correctness of DSL Artifacts
Venue: arXiv cs.SE 2016
Year: 2016

A domain specific language (DSL) abstracts from implementation details and is aligned with the way domain experts reason about a software component. The development of DSLs is usually centered around a grammar and transformations that generate implementation code or analysis models. The semantics of the language is often defined implicitly and in terms of a transformation to implementation code. In the presence of multiple transformations from the DSL, the correctness of the generated artifacts with respect to the semantics of the DSL is a relevant issue. We show that a formal semantics is essential for checking the correctness of the generated artifacts. We exploit the formal semantics in an industrial project and use formal techniques based on equivalence checking and model-based testing for validating the correctness of the generated artifacts. We report about our experience with this approach in an industrial development project.
Regret Analysis of the Anytime Optimally Confident UCB Algorithm
Venue: arXiv cs.LG 2016
Year: 2016

I introduce and analyse an anytime version of the Optimally Confident UCB (OCUCB) algorithm designed for minimising the cumulative regret in finite-armed stochastic bandits with subgaussian noise. The new algorithm is simple, intuitive (in hindsight) and comes with the strongest finite-time regret guarantees for a horizon-free algorithm so far. I also show a finite-time lower bound that nearly matches the upper bound.
Niépce-Bell or Turing: How to Test Odor Reproduction?
Venue: arXiv cs.OH 2016
Year: 2016

In a 1950 article in Mind, decades before the existence of anything resembling an artificial intelligence system, Alan Turing addressed the question of how to test whether machines can think, or in modern terminology, whether a computer claimed to exhibit intelligence indeed does so. The current paper raises the analogous issue for olfaction: how to test the validity of a system claimed to reproduce arbitrary odors artificially, in a way recognizable to humans, in face of the unavailability of a general naming method for odors. Although odor reproduction systems are still far from being viable, the question of how to test candidates thereof is claimed to be interesting and nontrivial, and a novel method is proposed. To some extent, the method is inspired by Turing`s test for AI, in that it involves a human challenger and the real and artificial entities, yet it is very different: our test is conditional, requiring from the artificial no more than is required from the original, and it employs a novel method of immersion that takes advantage of the availability of near-perfect reproduction methods for sight and sound.
On the Impact of Localization Errors on HRTF-based Robust Least-Squares Beamforming
Venue: arXiv cs.SD 2016
Year: 2016

In this work, a recently proposed Head-Related Transfer Function (HRTF)-based Robust Least-Squares Frequency-Invariant (RLSFI) beamformer design is analyzed with respect to its robustness against localization errors, which lead to a mismatch between the HRTFs corresponding to the actual target source position and the HRTFs which have been used for the beamformer design. The impact of this mismatch on the performance of the HRTF-based RLSFI beamformer is evaluated, including a comparison to the free-field-based beamformer design, using signal-based measures and word error rates for an off-the-shelf speech recognizer.
Curve Networks for Surface Reconstruction
Venue: arXiv cs.GR 2016
Year: 2016

Man-made objects usually exhibit descriptive curved features (i.e., curve networks). The curve network of an object conveys its high-level geometric and topological structure. We present a framework for extracting feature curve networks from unstructured point cloud data. Our framework first generates a set of initial curved segments fitting highly curved regions. We then optimize these curved segments to respect both data fitting and structural regularities. Finally, the optimized curved segments are extended and connected into curve networks using a clustering method. To facilitate effectiveness in case of severe missing data and to resolve ambiguities, we develop a user interface for completing the curve networks. Experiments on various imperfect point cloud data validate the effectiveness of our curve network extraction framework. We demonstrate the usefulness of the extracted curve networks for surface reconstruction from incomplete point clouds.
Generalized Gray codes with prescribed ends
Venue: arXiv cs.DM 2016
Year: 2016

An $n$-bit Gray code is a sequence of all $n$-bit strings such that consecutive strings differ in a single bit. It is well-known that given $α,β\in\{0,1\}^n$, an $n$-bit Gray code between $α$ and $β$ exists iff the Hamming distance $d(α,β)$ of $α$ and $β$ is odd. We generalize this classical result to $k$ pairwise disjoint pairs $α_i, β_i\in\{0,1\}^n$: if $d(α_i,β_i)$ is odd for all $i$ and $k<n$, then the set of all $n$-bit strings can be partitioned into $k$ sequences such that the $i$-th sequence leads from $α_i$ to $β_i$ and consecutive strings differ in a single bit. This holds for every $n>1$ with one exception in the case when $n = k + 1 = 4$. Our result is optimal in the sense that for every $n>2$ there are $n$ pairwise disjoint pairs $α_i,β_i\in\{0,1\}^n$ with $d(α_i,β_i)$ odd for which such sequences do not exist.
On the Performance of Delay Aware Shared Access with Priorities
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we analyze a shared access network with a fixed primary node and randomly distributed secondary nodes whose distribution follows a Poisson point process (PPP). The secondaries use a random access protocol allowing them to access the channel with probabilities that depend on the queue size of the primary. Assuming a system with multipacket reception (MPR) receivers having bursty packet arrivals at the primary and saturation at the secondaries, our protocol can be tuned to alleviate congestion at the primary. We study the throughput of the secondary network and the primary average delay, as well as the impact of the secondary node access probability and transmit power. We formulate an optimization problem to maximize the throughput of the secondary network under delay constraints for the primary node, which in the case that no congestion control is performed has a closed form expression providing the optimal access probability. Our numerical results illustrate the impact of network operating parameters on the performance of the proposed priority-based shared access protocol.
Detecting weak changes in dynamic events over networks
Venue: arXiv cs.LG 2016
Year: 2016

Large volume of networked streaming event data are becoming increasingly available in a wide variety of applications, such as social network analysis, Internet traffic monitoring and healthcare analytics. Streaming event data are discrete observation occurred in continuous time, and the precise time interval between two events carries a great deal of information about the dynamics of the underlying systems. How to promptly detect changes in these dynamic systems using these streaming event data? In this paper, we propose a novel change-point detection framework for multi-dimensional event data over networks. We cast the problem into sequential hypothesis test, and derive the likelihood ratios for point processes, which are computed efficiently via an EM-like algorithm that is parameter-free and can be computed in a distributed fashion. We derive a highly accurate theoretical characterization of the false-alarm-rate, and show that it can achieve weak signal detection by aggregating local statistics over time and networks. Finally, we demonstrate the good performance of our algorithm on numerical examples and real-world datasets from twitter and Memetracker.
Experimental Evaluation of a Reconfigurable Antenna System for Blind Interference Alignment
Venue: arXiv cs.IT 2016
Year: 2016

In recent years, several experimental studies have come out to validate the theoretical findings of interference alignment (IA), but only a handful of studies have focused on blind interference alignment. Unlike IA and other interference mitigation techniques, blind IA does not require channel state information at the transmitter (CSIT). The key insight is that the transmitter uses the knowledge of channel coherence intervals and receivers utilize reconfigurable antennas to create channel fluctuations exploited by the transmitter. In this work, we present a novel experimental evaluation of a reconfigurable antenna system for achieving blind IA. We present a blind IA technique based on reconfigurable antennas for a 2-user multipleinput single-output (MISO) broadcast channel implemented on a software defined radio platform where each of the receivers is equipped with a reconfigurable antenna. We further compare this blind IA implementation with traditional TDMA scheme for benchmarking purposes. We show that the achievable rates for blind IA can be realized in practice using measured channels under practical channel conditions. Additionally, the average error vector magnitude and bit error rate (BER) performances are evaluated.
Towards Practical Bayesian Parameter and State Estimation
Venue: arXiv cs.AI 2016
Year: 2016

Joint state and parameter estimation is a core problem for dynamic Bayesian networks. Although modern probabilistic inference toolkits make it relatively easy to specify large and practically relevant probabilistic models, the silver bullet---an efficient and general online inference algorithm for such problems---remains elusive, forcing users to write special-purpose code for each application. We propose a novel blackbox algorithm -- a hybrid of particle filtering for state variables and assumed density filtering for parameter variables. It has following advantages: (a) it is efficient due to its online nature, and (b) it is applicable to both discrete and continuous parameter spaces . On a variety of toy and real models, our system is able to generate more accurate results within a fixed computation budget. This preliminary evidence indicates that the proposed approach is likely to be of practical use.
Dense Image Representation with Spatial Pyramid VLAD Coding of CNN for Locally Robust Captioning
Venue: arXiv cs.CV 2016
Year: 2016

The workflow of extracting features from images using convolutional neural networks (CNN) and generating captions with recurrent neural networks (RNN) has become a de-facto standard for image captioning task. However, since CNN features are originally designed for classification task, it is mostly concerned with the main conspicuous element of the image, and often fails to correctly convey information on local, secondary elements. We propose to incorporate coding with vector of locally aggregated descriptors (VLAD) on spatial pyramid for CNN features of sub-regions in order to generate image representations that better reflect the local information of the images. Our results show that our method of compact VLAD coding can match CNN features with as little as 3% of dimensionality and, when combined with spatial pyramid, it results in image captions that more accurately take local elements into account.
Succinctness of Order-Invariant Logics on Depth-Bounded Structures
Venue: arXiv cs.LO 2016
Year: 2016

We study the expressive power and succinctness of order-invariant sentences of first-order (FO) and monadic second-order (MSO) logic on structures of bounded tree-depth. Order- invariance is undecidable in general and, thus, one strives for logics with a decidable syntax that have the same expressive power as order-invariant sentences. We show that on structures of bounded tree-depth, order-invariant FO has the same expressive power as FO. Our proof technique allows for a fine-grained analysis of the succinctness of this translation. We show that for every order-invariant FO sentence there exists an FO sentence whose size is elementary in the size of the original sentence, and whose number of quantifier alternations is linear in the tree-depth. We obtain similar results for MSO. It is known that the expressive power of MSO and FO coincide on structures of bounded tree-depth. We provide a translation from MSO to FO and we show that this translation is essentially optimal regarding the formula size. As a further result, we show that order-invariant MSO has the same expressive power as FO with modulo-counting quantifiers on bounded tree-depth structures.
deepTarget: End-to-end Learning Framework for microRNA Target Prediction using Deep Recurrent Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

MicroRNAs (miRNAs) are short sequences of ribonucleic acids that control the expression of target messenger RNAs (mRNAs) by binding them. Robust prediction of miRNA-mRNA pairs is of utmost importance in deciphering gene regulations but has been challenging because of high false positive rates, despite a deluge of computational tools that normally require laborious manual feature extraction. This paper presents an end-to-end machine learning framework for miRNA target prediction. Leveraged by deep recurrent neural networks-based auto-encoding and sequence-sequence interaction learning, our approach not only delivers an unprecedented level of accuracy but also eliminates the need for manual feature extraction. The performance gap between the proposed method and existing alternatives is substantial (over 25% increase in F-measure), and deepTarget delivers a quantum leap in the long-standing challenge of robust miRNA target prediction.
Model Interpolation with Trans-dimensional Random Field Language Models for Speech Recognition
Venue: arXiv cs.CL 2016
Year: 2016

The dominant language models (LMs) such as n-gram and neural network (NN) models represent sentence probabilities in terms of conditionals. In contrast, a new trans-dimensional random field (TRF) LM has been recently introduced to show superior performances, where the whole sentence is modeled as a random field. In this paper, we examine how the TRF models can be interpolated with the NN models, and obtain 12.1\% and 17.9\% relative error rate reductions over 6-gram LMs for English and Chinese speech recognition respectively through log-linear combination.
Binary Quadratic Programing for Online Tracking of Hundreds of People in Extremely Crowded Scenes
Venue: arXiv cs.CV 2016
Year: 2016

Multi-object tracking has been studied for decades. However, when it comes to tracking pedestrians in extremely crowded scenes, we are limited to only few works. This is an important problem which gives rise to several challenges. Pre-trained object detectors fail to localize targets in crowded sequences. This consequently limits the use of data-association based multi-target tracking methods which rely on the outcome of an object detector. Additionally, the small apparent target size makes it challenging to extract features to discriminate targets from their surroundings. Finally, the large number of targets greatly increases computational complexity which in turn makes it hard to extend existing multi-target tracking approaches to high-density crowd scenarios. In this paper, we propose a tracker that addresses the aforementioned problems and is capable of tracking hundreds of people efficiently. We formulate online crowd tracking as Binary Quadratic Programing. Our formulation employs target's individual information in the form of appearance and motion as well as contextual cues in the form of neighborhood motion, spatial proximity and grouping constraints, and solves detection and data association simultaneously. In order to solve the proposed quadratic optimization efficiently, where state-of art commercial quadratic programing solvers fail to find the answer in a reasonable amount of time, we propose to use the most recent version of the Modified Frank Wolfe algorithm, which takes advantage of SWAP-steps to speed up the optimization. We show that the proposed formulation can track hundreds of targets efficiently and improves state-of-art results by significant margins on eleven challenging high density crowd sequences.
Distributed Learning in the Presence of Disturbances
Venue: arXiv cs.SY 2016
Year: 2016

We consider a problem where multiple agents must learn an action profile that maximises the sum of their utilities in a distributed manner. The agents are assumed to have no knowledge of either the utility functions or the actions and payoffs of other agents. These assumptions arise when modelling the interactions in a complex system and communicating between various components of the system are both difficult. In [1], a distributed algorithm was proposed, which learnt Pareto-efficient solutions in this problem setting. However, the approach assumes that all agents can choose their actions, which precludes disturbances. In this paper, we show that a modified version of this distributed learning algorithm can learn Pareto-efficient solutions, even in the presence of disturbances from a finite set. We apply our approach to the problem of ramp coordination in traffic control for different demand profiles.
Studies on Brutal Contraction and Severe Withdrawal: Preliminary Report
Venue: arXiv cs.LO 2016
Year: 2016

In this paper we study the class of brutal base contractions that are based on a bounded ensconcement and also the class of severe withdrawals which are based on bounded epistemic entrenchment relations that are defined by means of bounded ensconcements (using the procedure proposed by Mary-Anne Williams). We present axiomatic characterizations for each one of those classes of functions and investigate the interrelation among them.