OpenRaiser/Intern-Atlas huggingface dataset:
Particle Smoothing for Hidden Diffusion Processes: Adaptive Path Integral Smoother
Venue: arXiv cs.LG 2017
Year: 2017

Particle smoothing methods are used for inference of stochastic processes based on noisy observations. Typically, the estimation of the marginal posterior distribution given all observations is cumbersome and computational intensive. In this paper, we propose a simple algorithm based on path integral control theory to estimate the smoothing distribution of continuous-time diffusion processes with partial observations. In particular, we use an adaptive importance sampling method to improve the effective sampling size of the posterior over processes given the observations and the reliability of the estimation of the marginals. This is achieved by estimating a feedback controller to sample efficiently from the joint smoothing distributions. We compare the results with estimations obtained from the standard Forward Filter/Backward Simulator for two diffusion processes of different complexity. We show that the proposed method gives more reliable estimations than the standard FFBSi when the smoothing distribution is poorly represented by the filter distribution.
Performance of LDPC Decoders with Missing Connections
Venue: arXiv cs.IT 2017
Year: 2017

Due to process variation in nanoscale manufacturing, there may be permanently missing connections in information processing hardware. Due to timing errors in circuits, there may be missed messages in intra-chip communications, equivalent to transiently missing connections. In this work, we investigate the performance of message-passing LDPC decoders in the presence of missing connections. We prove concentration and convergence theorems that validate the use of density evolution performance analysis. Arbitrarily small error probability is not possible with missing connections, but we find suitably defined decoding thresholds for communication systems with binary erasure channels under peeling decoding, as well as binary symmetric channels under Gallager A and B decoding. We see that decoding is robust to missing wires, as decoding thresholds degrade smoothly. Moreover, there is a stochastic facilitation effect in Gallager B decoders with missing connections. We also compare the decoding sensitivity with respect to channel noise and missing wiring.
Determinantal sets, singularities and application to optimal control in medical imagery
Venue: arXiv cs.SC 2017
Year: 2017

Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast between two biological matters on the pictures. Geometric optimal control leads us here to analyze mero-morphic vector fields depending upon physical parameters , and having their singularities defined by a deter-minantal variety. The involved matrix has polynomial entries with respect to both the state variables and the parameters. Taking into account the physical constraints of the problem, one needs to classify, with respect to the parameters, the number of real singularities lying in some prescribed semi-algebraic set. We develop a dedicated algorithm for real root classification of the singularities of the rank defects of a polynomial matrix, cut with a given semi-algebraic set. The algorithm works under some genericity assumptions which are easy to check. These assumptions are not so restrictive and are satisfied in the aforementioned application. As more general strategies for real root classification do, our algorithm needs to compute the critical loci of some maps, intersections with the boundary of the semi-algebraic domain, etc. In order to compute these objects, the determinantal structure is exploited through a stratifi-cation by the rank of the polynomial matrix. This speeds up the computations by a factor 100. Furthermore, our implementation is able to solve the application in medical imagery, which was out of reach of more general algorithms for real root classification. For instance, computational results show that the contrast problem where one of the matters is water is partitioned into three distinct classes.
Universal Multiparty Data Exchange and Secret Key Agreement
Venue: arXiv cs.IT 2017
Year: 2017

Multiple parties observing correlated data seek to recover each other's data and attain omniscience. To that end, they communicate interactively over a noiseless broadcast channel - each bit transmitted over this channel is received by all the parties. We give a universal interactive communication protocol, termed the recursive data exchange protocol (RDE), which attains omniscience for any sequence of data observed by the parties and provide an individual sequence guarantee of performance. As a by-product, for observations of length $n$, we show the universal rate optimality of RDE up to an $\mathcal{O}\left(n^{-\frac 12}\sqrt{\log n}\right)$ term in a generative setting where the data sequence is independent and identically distributed (in time). Furthermore, drawing on the duality between omniscience and secret key agreement due to Csiszar and Narayan, we obtain a universal protocol for generating a multiparty secret key of rate at most $\mathcal{O}\left(n^{-\frac 12}\sqrt{\log n}\right)$ less than the maximum rate possible. A key feature of RDE is its recursive structure whereby when a subset $A$ of parties recover each-other's data, the rates appear as if the parties have been executing the protocol in an alternative model where the parties in $A$ are collocated.
The Resistance Perturbation Distance: A Metric for the Analysis of Dynamic Networks
Venue: arXiv cs.SI 2017
Year: 2017

To quantify the fundamental evolution of time-varying networks, and detect abnormal behavior, one needs a notion of temporal difference that captures significant organizational changes between two successive instants. In this work, we propose a family of distances that can be tuned to quantify structural changes occurring on a graph at different scales: from the local scale formed by the neighbors of each vertex, to the largest scale that quantifies the connections between clusters, or communities. Our approach results in the definition of a true distance, and not merely a notion of similarity. We propose fast (linear in the number of edges) randomized algorithms that can quickly compute an approximation to the graph metric. The third contribution involves a fast algorithm to increase the robustness of a network by optimally decreasing the Kirchhoff index. Finally, we conduct several experiments on synthetic graphs and real networks, and we demonstrate that we can detect configurational changes that are directly related to the hidden variables governing the evolution of dynamic networks.
Unconstrained Still/Video-Based Face Verification with Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Over the last five years, methods based on Deep Convolutional Neural Networks (DCNNs) have shown impressive performance improvements for object detection and recognition problems. This has been made possible due to the availability of large annotated datasets, a better understanding of the non-linear mapping between input images and class labels as well as the affordability of GPUs. In this paper, we present the design details of a deep learning system for unconstrained face recognition, including modules for face detection, association, alignment and face verification. The quantitative performance evaluation is conducted using the IARPA Janus Benchmark A (IJB-A), the JANUS Challenge Set 2 (JANUS CS2), and the LFW dataset. The IJB-A dataset includes real-world unconstrained faces of 500 subjects with significant pose and illumination variations which are much harder than the Labeled Faces in the Wild (LFW) and Youtube Face (YTF) datasets. JANUS CS2 is the extended version of IJB-A which contains not only all the images/frames of IJB-A but also includes the original videos for evaluating the video-based face verification system. Some open issues regarding DCNNs for face verification problems are then discussed.
Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
Venue: arXiv cs.LG 2017
Year: 2017

We propose a stochastic variance reduced optimization algorithm for solving sparse learning problems with cardinality constraints. Sufficient conditions are provided, under which the proposed algorithm enjoys strong linear convergence guarantees and optimal estimation accuracy in high dimensions. We further extend the proposed algorithm to an asynchronous parallel variant with a near linear speedup. Numerical experiments demonstrate the efficiency of our algorithm in terms of both parameter estimation and computational performance.
A constrained L1 minimization approach for estimating multiple Sparse Gaussian or Nonparanormal Graphical Models
Venue: arXiv cs.LG 2017
Year: 2017

Identifying context-specific entity networks from aggregated data is an important task, arising often in bioinformatics and neuroimaging. Computationally, this task can be formulated as jointly estimating multiple different, but related, sparse Undirected Graphical Models (UGM) from aggregated samples across several contexts. Previous joint-UGM studies have mostly focused on sparse Gaussian Graphical Models (sGGMs) and can't identify context-specific edge patterns directly. We, therefore, propose a novel approach, SIMULE (detecting Shared and Individual parts of MULtiple graphs Explicitly) to learn multi-UGM via a constrained L1 minimization. SIMULE automatically infers both specific edge patterns that are unique to each context and shared interactions preserved among all the contexts. Through the L1 constrained formulation, this problem is cast as multiple independent subtasks of linear programming that can be solved efficiently in parallel. In addition to Gaussian data, SIMULE can also handle multivariate Nonparanormal data that greatly relaxes the normality assumption that many real-world applications do not follow. We provide a novel theoretical proof showing that SIMULE achieves a consistent result at the rate O(log(Kp)/n_{tot}). On multiple synthetic datasets and two biomedical datasets, SIMULE shows significant improvement over state-of-the-art multi-sGGM and single-UGM baselines.
A Fault Tolerance Improved Majority Voter for TMR System Architectures
Venue: arXiv cs.AR 2017
Year: 2017

For digital system designs, triple modular redundancy (TMR), which is a 3-tuple version of N-modular redundancy is widely preferred for many mission-control and safety-critical applications. The TMR scheme involves two-times duplication of the simplex system hardware, with a majority voter ensuring correctness provided at least two out of three copies of the system remain operational. Thus the majority voter plays a pivotal role in ensuring the correct operation of the system. The fundamental assumption implicit in the TMR scheme is that the majority voter does not become faulty, which may not hold well for implementations based on latest technology nodes with dimensions of the order of just tens of nanometers. To overcome the drawbacks of the classical majority voter some new voter designs were put forward in the literature with the aim of enhancing the fault tolerance. However, these voter designs generally ensure the correct system operation in the presence of either a faulty function module or the faulty voter, considered only in isolation. Since multiple faults may no longer be excluded in the nanoelectronics regime, simultaneous fault occurrences on both the function module and the voter should be considered, and the fault tolerance of the voters have to be analyzed under such a scenario. In this context, this article proposes a new fault-tolerant majority voter which is found to be more robust to faults than the existing voters in the presence of faults occurring internally and/or externally to the voter. Moreover, the proposed voter features less power dissipation, delay, and area metrics based on the simulation results obtained by using a 32/28nm CMOS process.
Another Generalization of the Reed-Muller Codes
Venue: arXiv cs.IT 2017
Year: 2017

The punctured binary Reed-Muller code is cyclic and was generalized into the punctured generalized Reed-Muller code over $\gf(q)$ in the literature. The major objective of this paper is to present another generalization of the punctured binary Reed-Muller code. Another objective is to construct a family of reversible cyclic codes that are related to the newly generalized Reed-Muller codes.
With Whom Do I Interact? Detecting Social Interactions in Egocentric Photo-streams
Venue: arXiv cs.CV 2017
Year: 2017

Given a user wearing a low frame rate wearable camera during a day, this work aims to automatically detect the moments when the user gets engaged into a social interaction solely by reviewing the automatically captured photos by the worn camera. The proposed method, inspired by the sociological concept of F-formation, exploits distance and orientation of the appearing individuals -with respect to the user- in the scene from a bird-view perspective. As a result, the interaction pattern over the sequence can be understood as a two-dimensional time series that corresponds to the temporal evolution of the distance and orientation features over time. A Long-Short Term Memory-based Recurrent Neural Network is then trained to classify each time series. Experimental evaluation over a dataset of 30.000 images has shown promising results on the proposed method for social interaction detection in egocentric photo-streams.
Constrained Linear Representability of Polymatroids and Algorithms for Computing Achievability Proofs in Network Coding
Venue: arXiv cs.IT 2017
Year: 2017

The constrained linear representability problem (CLRP) for polymatroids determines whether there exists a polymatroid that is linear over a specified field while satisfying a collection of constraints on the rank function. Using a computer to test whether a certain rate vector is achievable with vector linear network codes for a multi-source network coding instance and whether there exists a multi-linear secret sharing scheme achieving a specified information ratio for a given secret sharing instance are shown to be special cases of CLRP. Methods for solving CLRP built from group theoretic techniques for combinatorial generation are developed and described. These techniques form the core of an information theoretic achievability prover, an implementation accompanies the article, and several computational experiments with interesting instances of network coding and secret sharing demonstrating the utility of the method are provided.
On the Gap Between Decentralized and Centralized Coded Caching Schemes
Venue: arXiv cs.IT 2017
Year: 2017

Caching is a promising solution to satisfy the ongoing explosive demands for multi-media traffics. Recently, Maddah-Ali and Niesen proposed both centralized and de-centralized coded caching schemes, which are able to attain significant performance gains over uncoded caching schemes. Particular, their work indicates that there exists a performance gap between the decentralized coded caching scheme and the centralized coded caching scheme. In this paper, we investigate this gap. As a result, we prove that the multiplicative gap (i.e., the ratio of their performances) is between 1 and 1:5. The upper bound tightens the original one of 12 by Maddah-Ali and Niesen, while the lower bound verifies the intuition that the centralized coded caching scheme always outperforms its decentralized counterpart. Notably, both bounds are achievable in some cases. Furthermore, we prove that the gap can be arbitrarily close to 1 if the number of users is large enough, which suggests the great potential in practical applications to use the less optimal but more practical decentralized coded caching scheme
Efficient Construction of Probabilistic Tree Embeddings
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we describe an algorithm that embeds a graph metric $(V,d_G)$ on an undirected weighted graph $G=(V,E)$ into a distribution of tree metrics $(T,D_T)$ such that for every pair $u,v\in V$, $d_G(u,v)\leq d_T(u,v)$ and ${\bf{E}}_{T}[d_T(u,v)]\leq O(\log n)\cdot d_G(u,v)$. Such embeddings have proved highly useful in designing fast approximation algorithms, as many hard problems on graphs are easy to solve on tree instances. For a graph with $n$ vertices and $m$ edges, our algorithm runs in $O(m\log n)$ time with high probability, which improves the previous upper bound of $O(m\log^3 n)$ shown by Mendel et al.\,in 2009. The key component of our algorithm is a new approximate single-source shortest-path algorithm, which implements the priority queue with a new data structure, the "bucket-tree structure". The algorithm has three properties: it only requires linear time in the number of edges in the input graph; the computed distances have a distance preserving property; and when computing the shortest-paths to the $k$-nearest vertices from the source, it only requires to visit these vertices and their edge lists. These properties are essential to guarantee the correctness and the stated time bound. Using this shortest-path algorithm, we show how to generate an intermediate structure, the approximate dominance sequences of the input graph, in $O(m \log n)$ time, and further propose a simple yet efficient algorithm to converted this sequence to a tree embedding in $O(n\log n)$ time, both with high probability. Combining the three subroutines gives the stated time bound of the algorithm. Then we show that this efficient construction can facilitate some applications. We proved that FRT trees (the generated tree embedding) are Ramsey partitions with asymptotically tight bound, so the construction of a series of distance oracles can be accelerated.
Pinpointing Delay and Forwarding Anomalies Using Large-Scale Traceroute Measurements
Venue: arXiv cs.NI 2017
Year: 2017

Understanding network health is essential to improve Internet reliability. For instance, detecting disruptions in peer and provider networks facilitates the identification of connectivity problems. Currently this task is time consuming for network operators. It involves a fair amount of manual observation because operators have little visibility into other networks. In this paper we leverage the RIPE Atlas measurement platform to monitor and analyze network conditions. We propose a set of complementary methods to detect network disruptions from traceroute measurements. A novel method of detecting changes in delays is used to identify congested links, and a packet forwarding model is employed to predict traffic paths and to identify faulty routers in case of packet loss. In addition, aggregating results from each method allows us to easily monitor a network and identify coordinated reports manifesting significant network disruptions, reducing uninteresting alarms. Our contributions consist of a statistical approach providing robust estimation for Internet delays and the study of hundreds of thousands link delays. We present three cases demonstrating that the proposed methods detect real disruptions and provide valuable insights, as well as surprising findings, on the location and impact of identified events.
Stealing PINs via Mobile Sensors: Actual Risk versus User Perception
Venue: arXiv cs.CR 2017
Year: 2017

In this paper, we present the actual risks of stealing user PINs by using mobile sensors versus the perceived risks by users. First, we propose PINlogger.js which is a JavaScript-based side channel attack revealing user PINs on an Android mobile phone. In this attack, once the user visits a website controlled by an attacker, the JavaScript code embedded in the web page starts listening to the motion and orientation sensor streams without needing any permission from the user. By analysing these streams, it infers the user's PIN using an artificial neural network. Based on a test set of fifty 4-digit PINs, PINlogger.js is able to correctly identify PINs in the first attempt with a success rate of 74% which increases to 86 and 94% in the second and third attempts, respectively. The high success rates of stealing user PINs on mobile devices via JavaScript indicate a serious threat to user security. With the technical understanding of the information leakage caused by mobile phone sensors, we then study users' perception of the risks associated with these sensors. We design user studies to measure the general familiarity with different sensors and their functionality, and to investigate how concerned users are about their PIN being discovered by an app that has access to all these sensors. Our studies show that there is significant disparity between the actual and perceived levels of threat with regard to the compromise of the user PIN. We confirm our results by interviewing our participants using two different approaches, within-subject and between-subject, and compare the results. We discuss how this observation, along with other factors, renders many academic and industry solutions ineffective in preventing such side channel attacks.
Random numbers as probabilities of machine behaviour
Venue: arXiv cs.CC 2017
Year: 2017

A fruitful way of obtaining meaningful, possibly concrete, algorithmically random numbers is to consider a potential behaviour of a Turing machine and its probability with respect to a measure (or semi-measure) on the input space of binary codes. For example, Chaitin's Omega is a well known Martin-Loef random number that is obtained by considering the halting probability of a universal prefix-free machine. In the last decade, similar examples have been obtained for higher forms of randomness, i.e. randomness relative to strong oracles. In this work we obtain characterizations of the algorithmically random reals in higher randomness classes, as probabilities of certain events that can happen when an oracle universal machine runs probabilistically on a random oracle. Moreover we apply our analysis to different machine models, including oracle Turing machines, prefix-free machines, and models for infinite online computation. We find that in many cases the arithmetical complexity of a property is directly reflected in the strength of the algorithmic randomness of the probability with which it occurs, on any given universal machine. On the other hand, we point to many examples where this does not happen and the probability is a number whose algorithmic randomness is not the maximum possible (with respect to its arithmetical complexity). Finally we find that, unlike the halting probability of a universal machine, the probabilities of more complex properties like totality, cofinality, computability or completeness do not necessarily have the same Turing degree when they are defined with respect to different universal machines.
Montre: A Tool for Monitoring Timed Regular Expressions
Venue: arXiv cs.FL 2017
Year: 2017

We present Montre, a monitoring tool to search patterns specified by timed regular expressions over real-time behaviors. We use timed regular expressions as a compact, natural, and highly-expressive pattern specification language for monitoring applications involving quantitative timing constraints. Our tool essentially incorporates online and offline timed pattern matching algorithms so it is capable of finding all occurrences of a given pattern over both logged and streaming behaviors. Furthermore, Montre is designed to work with other tools via standard interfaces to perform more complex and versatile tasks for analyzing and reasoning about cyber-physical systems. As the first of its kind, we believe Montre will enable a new line of inquiries and techniques in these fields.