OpenRaiser/Intern-Atlas huggingface dataset:
How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
Venue: arXiv cs.LG 2016
Year: 2016

We consider the problem of approximating partition functions for Ising models. We make use of recent tools in combinatorial optimization: the Sherali-Adams and Lasserre convex programming hierarchies, in combination with variational methods to get algorithms for calculating partition functions in these families. These techniques give new, non-trivial approximation guarantees for the partition function beyond the regime of correlation decay. They also generalize some classical results from statistical physics about the Curie-Weiss ferromagnetic Ising model, as well as provide a partition function counterpart of classical results about max-cut on dense graphs \cite{arora1995polynomial}. With this, we connect techniques from two apparently disparate research areas -- optimization and counting/partition function approximations. (i.e. \#-P type of problems). Furthermore, we design to the best of our knowledge the first provable, convex variational methods. Though in the literature there are a host of convex versions of variational methods \cite{wainwright2003tree, wainwright2005new, heskes2006convexity, meshi2009convexifying}, they come with no guarantees (apart from some extremely special cases, like e.g. the graph has a single cycle \cite{weiss2000correctness}). We consider dense and low threshold rank graphs, and interestingly, the reason our approach works on these types of graphs is because local correlations propagate to global correlations -- completely the opposite of algorithms based on correlation decay. In the process we design novel entropy approximations based on the low-order moments of a distribution. Our proof techniques are very simple and generic, and likely to be applicable to many other settings other than Ising models.
SCOR: Software-defined Constrained Optimal Routing Platform for SDN
Venue: arXiv cs.NI 2016
Year: 2016

A Software-defined Constrained Optimal Routing (SCOR) platform is introduced as a Northbound interface in SDN architecture. It is based on constraint programming techniques and is implemented in MiniZinc modelling language. Using constraint programming techniques in this Northbound interface has created an efficient tool for implementing complex Quality of Service routing applications in a few lines of code. The code includes only the problem statement and the solution is found by a general solver program. A routing framework is introduced based on SDN's architecture model which uses SCOR as its Northbound interface and an upper layer of applications implemented in SCOR. Performance of a few implemented routing applications are evaluated in different network topologies, network sizes and various number of concurrent flows.
Scheduling massively parallel multigrid for multilevel Monte Carlo methods
Venue: arXiv cs.CE 2016
Year: 2016

The computational complexity of naive, sampling-based uncertainty quantification for 3D partial differential equations is extremely high. Multilevel approaches, such as multilevel Monte Carlo (MLMC), can reduce the complexity significantly, but to exploit them fully in a parallel environment, sophisticated scheduling strategies are needed. Often fast algorithms that are executed in parallel are essential to compute fine level samples in 3D, whereas to compute individual coarse level samples only moderate numbers of processors can be employed efficiently. We make use of multiple instances of a parallel multigrid solver combined with advanced load balancing techniques. In particular, we optimize the concurrent execution across the three layers of the MLMC method: parallelization across levels, across samples, and across the spatial grid. The overall efficiency and performance of these methods will be analyzed. Here the scalability window of the multigrid solver is revealed as being essential, i.e., the property that the solution can be computed with a range of process numbers while maintaining good parallel efficiency. We evaluate the new scheduling strategies in a series of numerical tests, and conclude the paper demonstrating large 3D scaling experiments.
DeepBinaryMask: Learning a Binary Mask for Video Compressive Sensing
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a novel encoder-decoder neural network model referred to as DeepBinaryMask for video compressive sensing. In video compressive sensing one frame is acquired using a set of coded masks (sensing matrix) from which a number of video frames is reconstructed, equal to the number of coded masks. The proposed framework is an end-to-end model where the sensing matrix is trained along with the video reconstruction. The encoder learns the binary elements of the sensing matrix and the decoder is trained to recover the unknown video sequence. The reconstruction performance is found to improve when using the trained sensing mask from the network as compared to other mask designs such as random, across a wide variety of compressive sensing reconstruction algorithms. Finally, our analysis and discussion offers insights into understanding the characteristics of the trained mask designs that lead to the improved reconstruction quality.
Representing Strategies
Venue: arXiv cs.LO 2016
Year: 2016

Quite some work in the ATL-tradition uses the differences between various types of strategies (positional, uniform, perfect recall) to give alternative semantics to the same logical language. This paper contributes to another perspective on strategy types, one where we characterise the differences between them on the syntactic (object language) level. This is important for a more traditional knowledge representation view on strategic content. Leaving differences between strategy types implicit in the semantics is a sensible idea if the goal is to use the strategic formalism for model checking. But, for traditional knowledge representation in terms of object language level formulas, we need to extent the language. This paper introduces a strategic STIT syntax with explicit operators for knowledge that allows us to charaterise strategy types. This more expressive strategic language is interpreted on standard ATL-type concurrent epistemic game structures. We introduce rule-based strategies in our language and fruitfully apply them to the representation and characterisation of positional and uniform strategies. Our representations highlight crucial conditions to be met for strategy types. We demonstrate the usefulness of our work by showing that it leads to a critical reexamination of coalitional uniform strategies.
Human-Planned Robotic Grasp Ranges: Capture and Validation
Venue: arXiv cs.HC 2016
Year: 2016

Leveraging human grasping skills to teach a robot to perform a manipulation task is appealing, but there are several limitations to this approach: time-inefficient data capture procedures, limited generalization of the data to other grasps and objects, and inability to use that data to learn more about how humans perform and evaluate grasps. This paper presents a data capture protocol that partially addresses these deficiencies by asking participants to specify ranges over which a grasp is valid. The protocol is verified both qualitatively through online survey questions (where 95.38% of within-range grasps are identified correctly with the nearest extreme grasp) and quantitatively by showing that there is small variation in grasps ranges from different participants as measured by joint angles, contact points, and position. We demonstrate that these grasp ranges are valid through testing on a physical robot (93.75% of grasps interpolated from grasp ranges are successful).
Precision, Recall, and Sensitivity of Monitoring Partially Synchronous Distributed Systems
Venue: arXiv cs.DC 2016
Year: 2016

Runtime verification focuses on analyzing the execution of a given program by a monitor to determine if it is likely to violate its specifications. There is often an impedance mismatch between the assumptions/model of the monitor and that of the underlying program. This constitutes problems especially for distributed systems, where the concept of current time and state are inherently uncertain. A monitor designed with asynchronous system model assumptions may cause false-positives for a program executing in a partially synchronous system: the monitor may flag a global predicate that does not actually occur in the underlying system. A monitor designed with a partially synchronous system model assumption may cause false negatives as well as false positives for a program executing in an environment where the bounds on partial synchrony differ (albeit temporarily) from the monitor model assumptions. In this paper we analyze the effects of the impedance mismatch between the monitor and the underlying program for the detection of conjunctive predicates. We find that there is a small interval where the monitor assumptions are hypersensitive to the underlying program environment. We provide analytical derivations for this interval, and also provide simulation support for exploring the sensitivity of predicate detection to the impedance mismatch between the monitor and the program under a partially synchronous system.
An approximate message passing approach for compressive hyperspectral imaging using a simultaneous low-rank and joint-sparsity prior
Venue: arXiv cs.IT 2016
Year: 2016

This paper considers a compressive sensing (CS) approach for hyperspectral data acquisition, which results in a practical compression ratio substantially higher than the state-of-the-art. Applying simultaneous low-rank and joint-sparse (L&S) model to the hyperspectral data, we propose a novel algorithm to joint reconstruction of hyperspectral data based on loopy belief propagation that enables the exploitation of both structured sparsity and amplitude correlations in the data. Experimental results with real hyperspectral datasets demonstrate that the proposed algorithm outperforms the state-of-the-art CS-based solutions with substantial reductions in reconstruction error.
Multi-modal image retrieval with random walk on multi-layer graphs
Venue: arXiv cs.IR 2016
Year: 2016

The analysis of large collections of image data is still a challenging problem due to the difficulty of capturing the true concepts in visual data. The similarity between images could be computed using different and possibly multimodal features such as color or edge information or even text labels. This motivates the design of image analysis solutions that are able to effectively integrate the multi-view information provided by different feature sets. We therefore propose a new image retrieval solution that is able to sort images through a random walk on a multi-layer graph, where each layer corresponds to a different type of information about the image data. We study in depth the design of the image graph and propose in particular an effective method to select the edge weights for the multi-layer graph, such that the image ranking scores are optimised. We then provide extensive experiments in different real-world photo collections, which confirm the high performance of our new image retrieval algorithm that generally surpasses state-of-the-art solutions due to a more meaningful image similarity computation.
The usability canary in the security coal mine: A cognitive framework for evaluation and design of usable authentication solutions
Venue: arXiv cs.HC 2016
Year: 2016

Over the past 15 years, researchers have identified an increasing number of security mechanisms that are so unusable that the intended users either circumvent them or give up on a service rather than suffer the security. With hindsight, the reasons can be identified easily enough: either the security task itself is too cumbersome and/or time-consuming, or it creates high friction with the users` primary task. The aim of the research presented here is to equip designers who select and implement security mechanisms with a method for identifying the ``best fit`` security mechanism at the design stage. Since many usability problems have been identified with authentication, we focus on ``best fit`` authentication, and present a framework that allows security designers not only to model the workload associated with a particular authentication method, but more importantly to model it in the context of the user`s primary task. We draw on results from cognitive psychology to create a method that allows a designer to understand the impact of a particular authentication method on user productivity and satisfaction. In a validation study using a physical mockup of an airline check-in kiosk, we demonstrate that the model can predict user performance and satisfaction. Furthermore, design experts suggested personalized order recommendations which were similar to our model`s predictions. Our model is the first that supports identification of a holistic fit between the task of user authentication and the context in which it is performed. When applied to new systems, we believe it will help designers understand the usability impact of their security choices and thus develop solutions that maximize both.
DNA Image Pro -- A Tool for Generating Pixel Patterns using DNA Tile Assembly
Venue: arXiv cs.ET 2016
Year: 2016

Self-assembly is a process found everywhere in the Nature. In particular, it is known that DNA self-assembly is Turing universal. Thus one can do arbitrary computations or build nano-structures using DNA self-assembly. In order to understand the DNA self-assembly process, many mathematical models have been proposed in the literature. In particular, abstract Tile Assembly Model (aTAM) received much attention. In this work, we investigate pixel pattern generation using aTAM. For a given image, a tile assembly system is given which can generate the image by self-assembly process. We also consider image blocks with specific cyclic pixel patterns (uniform shift and non uniform shift) self assembly. A software, DNA Image Pro, for generating pixel patterns using DNA tile assembly is also given.
A Representation Theory Perspective on Simultaneous Alignment and Classification
Venue: arXiv cs.CV 2016
Year: 2016

One of the difficulties in 3D reconstruction of molecules from images in single particle Cryo-Electron Microscopy (Cryo-EM), in addition to high levels of noise and unknown image orientations, is heterogeneity in samples: in many cases, the samples contain a mixture of molecules, or multiple conformations of one molecule. Many algorithms for the reconstruction of molecules from images in heterogeneous Cryo-EM experiments are based on iterative approximations of the molecules in a non-convex optimization that is prone to reaching suboptimal local minima. Other algorithms require an alignment in order to perform classification, or vice versa. The recently introduced Non-Unique Games framework provides a representation theoretic approach to studying problems of alignment over compact groups, and offers convex relaxations for alignment problems which are formulated as semidefinite programs (SDPs) with certificates of global optimality under certain circumstances. In this manuscript, we propose to extend Non-Unique Games to the problem of simultaneous alignment and classification with the goal of simultaneously classifying Cryo-EM images and aligning them within their respective classes. Our proposed approach can also be extended to the case of continuous heterogeneity.
Natural brain-information interfaces: Recommending information by relevance inferred from human brain signals
Venue: arXiv cs.IR 2016
Year: 2016

Finding relevant information from large document collections such as the World Wide Web is a common task in our daily lives. Estimation of a user's interest or search intention is necessary to recommend and retrieve relevant information from these collections. We introduce a brain-information interface used for recommending information by relevance inferred directly from brain signals. In experiments, participants were asked to read Wikipedia documents about a selection of topics while their EEG was recorded. Based on the prediction of word relevance, the individual's search intent was modeled and successfully used for retrieving new, relevant documents from the whole English Wikipedia corpus. The results show that the users' interests towards digital content can be modeled from the brain signals evoked by reading. The introduced brain-relevance paradigm enables the recommendation of information without any explicit user interaction, and may be applied across diverse information-intensive applications.
Encoding and Indexing of Lattice Codes
Venue: arXiv cs.IT 2016
Year: 2016

Encoding and indexing of lattice codes is generalized from self-similar lattice codes to a broader class of lattices. If coding lattice $Λ_{\textrm{c}}$ and shaping lattice $Λ_{\textrm{s}}$ satisfy $Λ_{\textrm{s}} \subseteq Λ_{\textrm{c}}$, then $Λ_{\textrm{c}} / Λ_{\textrm{s}}$ is a quotient group that can be used to form a (nested) lattice code $\mathcal{C}$. Conway and Sloane's method of encoding and indexing does not apply when the lattices are not self-similar. Results are provided for two classes of lattices. (1) If $Λ_{\textrm{c}}$ and $Λ_{\textrm{s}}$ both have generator matrices in triangular form, then encoding is always possible. (2) When $Λ_{\textrm{c}}$ and $Λ_{\textrm{s}}$ are described by full generator matrices, if a solution to a linear diophantine equation exists, then encoding is possible. In addition, special cases where $\mathcal{C}$ is a cyclic code are also considered. A condition for the existence of a group homomorphism between the information and $\mathcal{C}$ is given. The results are applicable to a variety of coding lattices, including Construction A, Construction D and LDLCs. The $D_4$, $E_8$ and convolutional code lattices are shown to be good choices for the shaping lattice. Thus, a lattice code $\mathcal{C}$ can be designed by selecting $Λ_{\textrm{c}}$ and $Λ_{\textrm{s}}$ separately, avoiding competing design requirements of self-similar lattice codes.
A Unified Multicarrier Modulation Framework
Venue: arXiv cs.IT 2016
Year: 2016

Orthogonal frequency division multiplexing (OFDM) has been recently recognized as inadequate to meet the increased requirements of the next generation of communication systems. A number of alternative modulation solutions, based on the use of filter banks, have thus been proposed and are currently being considered as candidate waveforms for the envisaged air interface of the future networks. A unified view of these schemes would largely facilitate a systematic comparison of their pros and cons as well as the study of methods for related signal processing problems. To this end, a generic modulator is developed in this paper, following a structured matrix formulation. With appropriate parameter settings, existing modulation schemes can result as special cases. Three such popular examples are presented in detail.
A Hybrid Dynamical Extension of Averaging
Venue: arXiv cs.RO 2016
Year: 2016

We extend a smooth dynamical systems averaging technique to a class of hybrid systems with a limit cycle that is particularly relevant to the synthesis of stable legged gaits. After introducing a definition of hybrid averageability sufficient to recover the classical result, we provide a simple illustration of its applicability to legged locomotion and conclude with some rather more speculative remarks concerning the prospects for further generalization of these ideas.
On the Algebraic Representation of One-Tape Deterministic Turing Machine
Venue: arXiv cs.CC 2016
Year: 2016

An algebraic representation of the Turing machines is given, where the configurations of Turing machines are represented by 4 order tensors, and the transition functions by 8 order tensors. Two types of tensor product are defined, one is to model the evolution of the Turing machines, and the other is to model the compositions of transition functions. It is shown that the two types of tensor product are harmonic in the sense that the associate law is obeyed.
Distributed Clock Skew and Offset Estimation in Wireless Sensor Networks: Asynchronous Algorithm and Convergence Analysis
Venue: arXiv cs.DC 2016
Year: 2016

In this paper, we propose a fully distributed algorithm for joint clock skew and offset estimation in wireless sensor networks based on belief propagation. In the proposed algorithm, each node can estimate its clock skew and offset in a completely distributed and asynchronous way: some nodes may update their estimates more frequently than others using outdated message from neighboring nodes. In addition, the proposed algorithm is robust to random packet loss. Such algorithm does not require any centralized information processing or coordination, and is scalable with network size. The proposed algorithm represents a unified framework that encompasses both classes of synchronous and asynchronous algorithms for network-wide clock synchronization. It is shown analytically that the proposed asynchronous algorithm converges to the optimal estimates with estimation mean-square-error at each node approaching the centralized Cramér-Rao bound under any network topology. Simulation results further show that {the convergence speed is faster than that corresponding to a synchronous algorithm}.
Periodicity of identifying codes in strips
Venue: arXiv cs.DM 2016
Year: 2016

An identifying code in a graph is a subset of vertices having a nonempty and distinct intersection with the closed neighborhood of every vertex. We prove that the infimum density of any identifying code in $S_k$ (an infinite strip of $k$ rows in the square grid) can always be achieved by a periodic identifying code with pattern length at most $2^{4k}$. Assisted by a compute program implementing Karp's algorithm for minimum cycle mean, we find a periodic identifying code in $S_4$ with the minimum density $11/28$, and a periodic identifying code in $S_5$ with the minimum density $19/50$.
Practical optimization of Steiner Trees via the cavity method
Venue: arXiv cs.DS 2016
Year: 2016

The optimization version of the cavity method for single instances, called Max-Sum, has been applied in the past to the Minimum Steiner Tree Problem on Graphs and variants. Max-Sum has been shown experimentally to give asymptotically optimal results on certain types of weighted random graphs, and to give good solutions in short computation times for some types of real networks. However, the hypotheses behind the formulation and the cavity method itself limit substantially the class of instances on which the approach gives good results (or even converges). Moreover, in the standard model formulation, the diameter of the tree solution is limited by a predefined bound, that affects both computation time and convergence properties. In this work we describe two main enhancements to the Max-Sum equations to be able to cope with optimization of real-world instances. First, we develop an alternative 'flat' model formulation, that allows to reduce substantially the relevant configuration space, making the approach feasible on instances with large solution diameter, in particular when the number of terminal nodes is small. Second, we propose an integration between Max-Sum and three greedy heuristics. This integration allows to transform Max-Sum into a highly competitive self-contained algorithm, in which a feasible solution is given at each step of the iterative procedure. Part of this development participated on the 2014 DIMACS challenge on Steiner Problems, and we report the results here.