OpenRaiser/Intern-Atlas huggingface dataset:
A New Error Correction Scheme for Physical Unclonable Functions
Venue: arXiv cs.CR 2016
Year: 2016

Error correction is an indispensable component when Physical Unclonable Functions (PUFs) are used in cryptographic applications. So far, there exist schemes that obtain helper data, which they need within the error correction process. We introduce a new scheme, which only uses an error correcting code without any further helper data. The main idea is to construct for each PUF instance an individual code which contains the initial PUF response as codeword. In this work we use LDPC codes, however other code classes are also possible. Our scheme allows a trade-off between code rate and cryptographic security. In addition, decoding with linear complexity is possible.
Log-time and Log-space Extreme Classification
Venue: arXiv cs.LG 2016
Year: 2016

We present LTLS, a technique for multiclass and multilabel prediction that can perform training and inference in logarithmic time and space. LTLS embeds large classification problems into simple structured prediction problems and relies on efficient dynamic programming algorithms for inference. We train LTLS with stochastic gradient descent on a number of multiclass and multilabel datasets and show that despite its small memory footprint it is often competitive with existing approaches.
An analysis of New South Wales electronic vote counting
Venue: arXiv cs.CR 2016
Year: 2016

We re-examine the 2012 local government elections in New South Wales, Australia. The count was conducted electronically using a randomised form of the Single Transferable Vote (STV). It was already well known that randomness does make a difference to outcomes in some seats. We describe how the process could be amended to include a demonstration that the randomness was chosen fairly. Second, and more significantly, we found an error in the official counting software, which caused a mistake in the count in the council of Griffith, where candidate Rina Mercuri narrowly missed out on a seat. We believe the software error incorrectly decreased Mercuri's winning probability to about 10%---according to our count she should have won with 91% probability. The NSW Electoral Commission (NSWEC) corrected their code when we pointed out the error, and made their own announcement. We have since investigated the 2016 local government election (held after correcting the error above) and found two new errors. We notified the NSWEC about these errors a few days after they posted the results.
Presenting a New Dataset for the Timeline Generation Problem
Venue: arXiv cs.CL 2016
Year: 2016

The timeline generation task summarises an entity's biography by selecting stories representing key events from a large pool of relevant documents. This paper addresses the lack of a standard dataset and evaluative methodology for the problem. We present and make publicly available a new dataset of 18,793 news articles covering 39 entities. For each entity, we provide a gold standard timeline and a set of entity-related articles. We propose ROUGE as an evaluation metric and validate our dataset by showing that top Google results outperform straw-man baselines.
Supervisory Output Prediction for Bilinear Systems by Reinforcement Learning
Venue: arXiv cs.SY 2016
Year: 2016

Online output prediction is an indispensable part of any model predictive control implementation, especially when simplifications of the underlying physical model have been considered and/or the operating conditions change quite often. Furthermore, the selection of an output prediction model is strongly related to the data available, while designing/altering the data collection process may not be an option. Thus, in several scenarios, selecting the most appropriate prediction model needs to be performed during runtime. To this end, this paper introduces a supervisory output prediction scheme, tailored specifically for input-output stable bilinear systems, that intends on automating the process of selecting the most appropriate prediction model during runtime. The selection process is based upon a reinforcement-learning scheme, where prediction models are selected according to their prior prediction performance. An additional selection process is concerned with appropriately partitioning the control-inputs' domain in order to also allow for switched-system approximations of the original bilinear dynamics. We show analytically that the proposed scheme converges (in probability) to the best model and partition. We finally demonstrate these properties through simulations of temperature prediction in residential buildings.
Data-driven Structured Realization
Venue: arXiv cs.SY 2016
Year: 2016

We present a framework for constructing structured realizations of linear dynamical systems having transfer functions of the form $C(\sum_{k=1}^K h_k(s)A_k)^{-1}B$ where $h_1,h_2,\ldots,h_K$ are prescribed functions that specify the surmised structure of the model. Our construction is data-driven in the sense that an interpolant is derived entirely from measurements of a transfer function. Our approach extends the Loewner realization framework to more general system structure that includes second-order (and higher) systems as well as systems with internal delays. Numerical examples demonstrate the advantages of this approach.
Dependence and Relevance: A probabilistic view
Venue: arXiv cs.AI 2016
Year: 2016

We examine three probabilistic concepts related to the sentence "two variables have no bearing on each other". We explore the relationships between these three concepts and establish their relevance to the process of constructing similarity networks---a tool for acquiring probabilistic knowledge from human experts. We also establish a precise relationship between connectedness in Bayesian networks and relevance in probability.
Parse Geometry from a Line: Monocular Depth Estimation with Partial Laser Observation
Venue: arXiv cs.CV 2016
Year: 2016

Many standard robotic platforms are equipped with at least a fixed 2D laser range finder and a monocular camera. Although those platforms do not have sensors for 3D depth sensing capability, knowledge of depth is an essential part in many robotics activities. Therefore, recently, there is an increasing interest in depth estimation using monocular images. As this task is inherently ambiguous, the data-driven estimated depth might be unreliable in robotics applications. In this paper, we have attempted to improve the precision of monocular depth estimation by introducing 2D planar observation from the remaining laser range finder without extra cost. Specifically, we construct a dense reference map from the sparse laser range data, redefining the depth estimation task as estimating the distance between the real and the reference depth. To solve the problem, we construct a novel residual of residual neural network, and tightly combine the classification and regression losses for continuous depth estimation. Experimental results suggest that our method achieves considerable promotion compared to the state-of-the-art methods on both NYUD2 and KITTI, validating the effectiveness of our method on leveraging the additional sensory information. We further demonstrate the potential usage of our method in obstacle avoidance where our methodology provides comprehensive depth information compared to the solution using monocular camera or 2D laser range finder alone.
Optimal Binary Autoencoding with Pairwise Correlations
Venue: arXiv cs.LG 2016
Year: 2016

We formulate learning of a binary autoencoder as a biconvex optimization problem which learns from the pairwise correlations between encoded and decoded bits. Among all possible algorithms that use this information, ours finds the autoencoder that reconstructs its inputs with worst-case optimal loss. The optimal decoder is a single layer of artificial neurons, emerging entirely from the minimax loss minimization, and with weights learned by convex optimization. All this is reflected in competitive experimental results, demonstrating that binary autoencoding can be done efficiently by conveying information in pairwise correlations in an optimal fashion.
Line failure probability bounds for power grids
Venue: arXiv cs.SY 2016
Year: 2016

We develop upper bounds for line failure probabilities in power grids, under the DC approximation and assuming Gaussian noise for the power injections. Our upper bounds are explicit, and lead to characterization of safe operational capacity regions that are convex and polyhedral, making our tools compatible with existing planning methods. Our probabilistic bounds are derived through the use of powerful concentration inequalities.
Non-Myopic Target Tracking Strategies for State-Dependent Noise
Venue: arXiv cs.RO 2016
Year: 2016

We study the problem of devising a closed-loop strategy to control the position of a robot that is tracking a possibly moving target. The robot is capable of obtaining noisy measurements of the target's position. The key idea in active target tracking is to choose control laws that drive the robot to measurement locations that will reduce the uncertainty in the target's position. The challenge is that measurement uncertainty often is a function of the (unknown) relative positions of the target and the robot. Consequently, a closed-loop control policy is desired which can map the current estimate of the target's position to an optimal control law for the robot. Our main contribution is to devise a closed-loop control policy for target tracking that plans for a sequence of control actions, instead of acting greedily. We consider scenarios where the noise in measurement is a function of the state of the target. We seek to minimize the maximum uncertainty (trace of the posterior covariance matrix) over all possible measurements. We exploit the structural properties of a Kalman Filter to build a policy tree that is orders of magnitude smaller than naive enumeration while still preserving optimality guarantees. We show how to obtain even more computational savings by relaxing the optimality guarantees. The resulting algorithms are evaluated through simulations.
PNP: Fast Path Ensemble Method for Movie Design
Venue: arXiv cs.SI 2016
Year: 2016

How can we design a product or movie that will attract, for example, the interest of Pennsylvania adolescents or liberal newspaper critics? What should be the genre of that movie and who should be in the cast? In this work, we seek to identify how we can design new movies with features tailored to a specific user population. We formulate the movie design as an optimization problem over the inference of user-feature scores and selection of the features that maximize the number of attracted users. Our approach, PNP, is based on a heterogeneous, tripartite graph of users, movies and features (e.g., actors, directors, genres), where users rate movies and features contribute to movies. We learn the preferences by leveraging user similarities defined through different types of relations, and show that our method outperforms state-of-the-art approaches, including matrix factorization and other heterogeneous graph-based analysis. We evaluate PNP on publicly available real-world data and show that it is highly scalable and effectively provides movie designs oriented towards different groups of users, including men, women, and adolescents.
Routing Centralization Across Domains via SDN: A Model and Emulation Framework for BGP Evolution
Venue: arXiv cs.NI 2016
Year: 2016

In this work, we propose a radical, incrementally-deployable Internet routing paradigm in which the control plane of multiple networks is centralized. This follows the Software Defined Networking (SDN) paradigm, although at the inter-domain level involving multiple Autonomous Systems (AS). Multi-domain SDN centralization can be realized by outsourcing routing functions to an external contractor, which provides inter-domain routing services facilitated through a multi-AS network controller. The proposed model promises to become a vehicle for evolving BGP and uses the bird's eye view over several networks to benefit aspects of inter-domain routing, such as convergence properties, policy conflict resolution, inter-domain troubleshooting, and collaborative security. In addition to the proposed paradigm, we introduce a publicly available emulation platform built on top of Mininet and the Quagga routing software, for experimenting in hybrid BGP-SDN AS-level networks. As a proof of concept we focus specifically on exploiting multi-domain centralization to improve BGP's slow convergence. We build and make publicly available a first multi-AS controller tailored to this use case and demonstrate experimentally that SDN centralization helps to linearly reduce BGP convergence times and churn rates with expanding SDN deployments.
Multidimensional Asymptotic Consensus in Dynamic Networks
Venue: arXiv cs.DC 2016
Year: 2016

We study the problem of asymptotic consensus as it occurs in a wide range of applications in both man-made and natural systems. In particular, we study systems with directed communication graphs that may change over time. We recently proposed a new family of convex combination algorithms in dimension one whose weights depend on the received values and not only on the communication topology. Here, we extend this approach to arbitrarily high dimensions by introducing two new algorithms: the ExtremePoint and the Centroid algorithm. Contrary to classical convex combination algorithms, both have component-wise contraction rates that are constant in the number of agents. Paired with a speed-up technique for convex combination algorithms, we get a convergence time linear in the number of agents, which is optimal. Besides their respective contraction rates, the two algorithms differ in the fact that the Centroid algorithm's update rule is independent of any coordinate system while the ExtremePoint algorithm implicitly assumes a common agreed-upon coordinate system among agents. The latter assumption may be realistic in some man-made multi-agent systems but is highly questionable in systems designed for the modelization of natural phenomena. Finally we prove that our new algorithms also achieve asymptotic consensus under very weak connectivity assumptions, provided that agent interactions are bidirectional.
UniFlex: Accelerating Networking Research and Experimentation through Software-Defined Wireless Networking
Venue: arXiv cs.NI 2016
Year: 2016

Classical control and management plane for computer networks is addressing individual parameters of protocol layers within an individual wireless network device. We argue that this is not sufficient in phase of increasing deployment of highly re-configurable systems, as well as heterogeneous wireless systems co-existing in the same radio spectrum which demand harmonized, frequently even coordinated adaptation of multiple parameters in different protocol layers (cross-layer) in multiple network devices (cross-node). We propose UniFlex, a framework enabling unified and flexible radio and network control. It provides an API enabling coordinated cross-layer control and management operation over multiple network nodes. The controller logic may be implemented either in a centralized or distributed manner. This allows to place time-sensitive control functions close to the controlled device (i.e., local control application), off-load more resource hungry network application to compute servers and make them work together to control entire network. The UniFlex framework was prototypically implemented and provided to the research community as open-source. We evaluated the the framework in a number of use-cases, what proved its usability.
Unit circle MVDR beamformer
Venue: arXiv cs.IT 2016
Year: 2016

The array polynomial is the z-transform of the array weights for a narrowband planewave beamformer using a uniform linear array (ULA). Evaluating the array polynomial on the unit circle in the complex plane yields the beampattern. The locations of the polynomial zeros on the unit circle indicate the nulls of the beampattern. For planewave signals measured with a ULA, the locations of the ensemble MVDR polynomial zeros are constrained on the unit circle. However, sample matrix inversion (SMI) MVDR polynomial zeros generally do not fall on the unit circle. The proposed unit circle MVDR (UC MVDR) projects the zeros of the SMI MVDR polynomial radially on the unit circle. This satisfies the constraint on the zeros of ensemble MVDR polynomial. Numerical simulations show that the UC MVDR beamformer suppresses interferers better than the SMI MVDR and the diagonal loaded MVDR beamformer and also improves the white noise gain (WNG).
RL$^2$: Fast Reinforcement Learning via Slow Reinforcement Learning
Venue: arXiv cs.AI 2016
Year: 2016

Deep reinforcement learning (deep RL) has been successful in learning sophisticated behaviors automatically; however, the learning process requires a huge number of trials. In contrast, animals can learn new tasks in just a few trials, benefiting from their prior knowledge about the world. This paper seeks to bridge this gap. Rather than designing a "fast" reinforcement learning algorithm, we propose to represent it as a recurrent neural network (RNN) and learn it from data. In our proposed method, RL$^2$, the algorithm is encoded in the weights of the RNN, which are learned slowly through a general-purpose ("slow") RL algorithm. The RNN receives all information a typical RL algorithm would receive, including observations, actions, rewards, and termination flags; and it retains its state across episodes in a given Markov Decision Process (MDP). The activations of the RNN store the state of the "fast" RL algorithm on the current (previously unseen) MDP. We evaluate RL$^2$ experimentally on both small-scale and large-scale problems. On the small-scale side, we train it to solve randomly generated multi-arm bandit problems and finite MDPs. After RL$^2$ is trained, its performance on new MDPs is close to human-designed algorithms with optimality guarantees. On the large-scale side, we test RL$^2$ on a vision-based navigation task and show that it scales up to high-dimensional problems.
Audio Visual Speech Recognition using Deep Recurrent Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

In this work, we propose a training algorithm for an audio-visual automatic speech recognition (AV-ASR) system using deep recurrent neural network (RNN).First, we train a deep RNN acoustic model with a Connectionist Temporal Classification (CTC) objective function. The frame labels obtained from the acoustic model are then used to perform a non-linear dimensionality reduction of the visual features using a deep bottleneck network. Audio and visual features are fused and used to train a fusion RNN. The use of bottleneck features for visual modality helps the model to converge properly during training. Our system is evaluated on GRID corpus. Our results show that presence of visual modality gives significant improvement in character error rate (CER) at various levels of noise even when the model is trained without noisy data. We also provide a comparison of two fusion methods: feature fusion and decision fusion.
Encoding monotonic multi-set preferences using CI-nets: preliminary report
Venue: arXiv cs.AI 2016
Year: 2016

CP-nets and their variants constitute one of the main AI approaches for specifying and reasoning about preferences. CI-nets, in particular, are a CP-inspired formalism for representing ordinal preferences over sets of goods, which are typically required to be monotonic. Considering also that goods often come in multi-sets rather than sets, a natural question is whether CI-nets can be used more or less directly to encode preferences over multi-sets. We here provide some initial ideas on how to achieve this, in the sense that at least a restricted form of reasoning on our framework, which we call "confined reasoning", can be efficiently reduced to reasoning on CI-nets. Our framework nevertheless allows for encoding preferences over multi-sets with unbounded multiplicities. We also show the extent to which it can be used to represent preferences where multiplicites of the goods are not stated explicitly ("purely qualitative preferences") as well as a potential use of our generalization of CI-nets as a component of a recent system for evidence aggregation.
Coming to Terms with Quantified Reasoning
Venue: arXiv cs.LO 2016
Year: 2016

The theory of finite term algebras provides a natural framework to describe the semantics of functional languages. The ability to efficiently reason about term algebras is essential to automate program analysis and verification for functional or imperative programs over algebraic data types such as lists and trees. However, as the theory of finite term algebras is not finitely axiomatizable, reasoning about quantified properties over term algebras is challenging. In this paper we address full first-order reasoning about properties of programs manipulating term algebras, and describe two approaches for doing so by using first-order theorem proving. Our first method is a conservative extension of the theory of term algebras using a finite number of statements, while our second method relies on extending the superposition calculus of first-order theorem provers with additional inference rules. We implemented our work in the first-order theorem prover Vampire and evaluated it on a large number of algebraic data type benchmarks, as well as game theory constraints. Our experimental results show that our methods are able to find proofs for many hard problems previously unsolved by state-of-the-art methods. We also show that Vampire implementing our methods outperforms existing SMT solvers able to deal with algebraic data types.
Automating Verification of Event-B Models
Venue: arXiv cs.SE 2016
Year: 2016

Event-B is one of more popular notations for model-based, proof driven specification. It offers a fairly high-level mathematical lan- guage based on FOL and ZF set theory and an economical yet expres- sive modelling notation. Model correctness is established by discharging proving a number conjectures constructed via a syntactic instantiation of schematic conditions. A large proportion of provable conjectures re- quires proof hints from a user. For larger models this becomes extremely onerous as identical or similar proofs have to be repeated over and over, especially after model refactoring stages. In the paper we briefly present a new Rodin Platform proof back-end based on the Why3 umbrella prover.
Authority-based Team Discovery in Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

Given a social network of experts, we address the problem of discovering a team of experts that collectively holds a set of skills required to complete a given project. Most prior work ranks possible solutions by communication cost, represented by edge weights in the expert network. Our contribution is to take experts authority into account, represented by node weights. We formulate several problems that combine communication cost and authority, we prove that they are NP-hard, and we propose and experimentally evaluate greedy algorithms to solve them.
Probabilistic Caching in Wireless D2D Networks: Cache Hit Optimal vs. Throughput Optimal
Venue: arXiv cs.NI 2016
Year: 2016

Departing from the conventional cache hit optimization in cache-enabled wireless networks, we consider an alternative optimization approach for the probabilistic caching placement in stochastic wireless D2D caching networks taking into account the reliability of D2D transmissions. Using tools from stochastic geometry, we provide a closed-form approximation of cache-aided throughput, which measures the density of successfully served requests by local device caches, and we obtain the optimal caching probabilities with numerical optimization. Compared to the cache-hit-optimal case, the optimal caching probabilities obtained by cache-aided throughput optimization show notable gain in terms of the density of successfully served user requests, particularly in dense user environments.