OpenRaiser/Intern-Atlas huggingface dataset:
Learning Deep Structured Models
Venue: arXiv cs.LG 2015
Year: 2015

Many problems in real-world applications involve predicting several random variables which are statistically related. Markov random fields (MRFs) are a great mathematical tool to encode such relationships. The goal of this paper is to combine MRFs with deep learning algorithms to estimate complex representations while taking into account the dependencies between the output random variables. Towards this goal, we propose a training algorithm that is able to learn structured models jointly with deep features that form the MRF potentials. Our approach is efficient as it blends learning and inference and makes use of GPU acceleration. We demonstrate the effectiveness of our algorithm in the tasks of predicting words from noisy images, as well as multi-class classification of Flickr photographs. We show that joint learning of the deep features and the MRF parameters results in significant performance gains.
Benchmarks for Parity Games (extended version)
Venue: arXiv cs.LO 2015
Year: 2015

We propose a benchmark suite for parity games that includes all benchmarks that have been used in the literature, and make it available online. We give an overview of the parity games, including a description of how they have been generated. We also describe structural properties of parity games, and using these properties we show that our benchmarks are representative. With this work we provide a starting point for further experimentation with parity games.
Lock-in Problem for Parallel Rotor-router Walks
Venue: arXiv cs.DM 2015
Year: 2015

The rotor-router model, also called the Propp machine, was introduced as a deterministic alternative to the random walk. In this model, a group of identical tokens are initially placed at nodes of the graph. Each node maintains a cyclic ordering of the outgoing arcs, and during consecutive turns the tokens are propagated along arcs chosen according to this ordering in round-robin fashion. The behavior of the model is fully deterministic. Yanovski et al.(2003) proved that a single rotor-router walk on any graph with m edges and diameter $D$ stabilizes to a traversal of an Eulerian circuit on the set of all 2m directed arcs on the edge set of the graph, and that such periodic behaviour of the system is achieved after an initial transient phase of at most 2mD steps. The case of multiple parallel rotor-routers was studied experimentally, leading Yanovski et al. to the conjecture that a system of $k \textgreater{} 1$ parallel walks also stabilizes with a period of length at most $2m$ steps. In this work we disprove this conjecture, showing that the period of parallel rotor-router walks can in fact, be superpolynomial in the size of graph. On the positive side, we provide a characterization of the periodic behavior of parallel router walks, in terms of a structural property of stable states called a subcycle decomposition. This property provides us the tools to efficiently detect whether a given system configuration corresponds to the transient or to the limit behavior of the system. Moreover, we provide polynomial upper bounds of $O(m^4 D^2 + mD \log k)$ and $O(m^5 k^2)$ on the number of steps it takes for the system to stabilize. Thus, we are able to predict any future behavior of the system using an algorithm that takes polynomial time and space. In addition, we show that there exists a separation between the stabilization time of the single-walk and multiple-walk rotor-router systems, and that for some graphs the latter can be asymptotically larger even for the case of $k = 2$ walks.
From Social Network to Semantic Social Network in Recommender System
Venue: arXiv cs.SI 2015
Year: 2015

Due the success of emerging Web 2.0, and different social network Web sites such as Amazon and movie lens, recommender systems are creating unprecedented opportunities to help people browsing the web when looking for relevant information, and making choices. Generally, these recommender systems are classified in three categories: content based, collaborative filtering, and hybrid based recommendation systems. Usually, these systems employ standard recommendation methods such as artificial neural networks, nearest neighbor, or Bayesian networks. However, these approaches are limited compared to methods based on web applications, such as social networks or semantic web. In this paper, we propose a novel approach for recommendation systems called semantic social recommendation systems that enhance the analysis of social networks exploiting the power of semantic social network analysis. Experiments on real-world data from Amazon examine the quality of our recommendation method as well as the performance of our recommendation algorithms.
Robots that can adapt like animals
Venue: arXiv cs.RO 2015
Year: 2015

As robots leave the controlled environments of factories to autonomously function in more complex, natural environments, they will have to respond to the inevitable fact that they will become damaged. However, while animals can quickly adapt to a wide variety of injuries, current robots cannot "think outside the box" to find a compensatory behavior when damaged: they are limited to their pre-specified self-sensing abilities, can diagnose only anticipated failure modes, and require a pre-programmed contingency plan for every type of potential damage, an impracticality for complex robots. Here we introduce an intelligent trial and error algorithm that allows robots to adapt to damage in less than two minutes, without requiring self-diagnosis or pre-specified contingency plans. Before deployment, a robot exploits a novel algorithm to create a detailed map of the space of high-performing behaviors: This map represents the robot's intuitions about what behaviors it can perform and their value. If the robot is damaged, it uses these intuitions to guide a trial-and-error learning algorithm that conducts intelligent experiments to rapidly discover a compensatory behavior that works in spite of the damage. Experiments reveal successful adaptations for a legged robot injured in five different ways, including damaged, broken, and missing legs, and for a robotic arm with joints broken in 14 different ways. This new technique will enable more robust, effective, autonomous robots, and suggests principles that animals may use to adapt to injury.
Strategy Synthesis for General Deductive Games Based on SAT Solving
Venue: arXiv cs.AI 2015
Year: 2015

We propose a general framework for modelling and solving deductive games, where one player selects a secret code and the other player strives to discover this code using a minimal number of allowed experiments that reveal some partial information about the code. The framework is implemented in a software tool Cobra, and its functionality is demonstrated by producing new results about existing deductive games.
Subjectivity, Bayesianism, and Causality
Venue: arXiv cs.AI 2015
Year: 2015

Bayesian probability theory is one of the most successful frameworks to model reasoning under uncertainty. Its defining property is the interpretation of probabilities as degrees of belief in propositions about the state of the world relative to an inquiring subject. This essay examines the notion of subjectivity by drawing parallels between Lacanian theory and Bayesian probability theory, and concludes that the latter must be enriched with causal interventions to model agency. The central contribution of this work is an abstract model of the subject that accommodates causal interventions in a measure-theoretic formalisation. This formalisation is obtained through a game-theoretic Ansatz based on modelling the inside and outside of the subject as an extensive-form game with imperfect information between two players. Finally, I illustrate the expressiveness of this model with an example of causal induction.
Raking the Cocktail Party
Venue: arXiv cs.SD 2015
Year: 2015

We present the concept of an acoustic rake receiver---a microphone beamformer that uses echoes to improve the noise and interference suppression. The rake idea is well-known in wireless communications; it involves constructively combining different multipath components that arrive at the receiver antennas. Unlike spread-spectrum signals used in wireless communications, speech signals are not orthogonal to their shifts. Therefore, we focus on the spatial structure, rather than temporal. Instead of explicitly estimating the channel, we create correspondences between early echoes in time and image sources in space. These multiple sources of the desired and the interfering signal offer additional spatial diversity that we can exploit in the beamformer design. We present several "intuitive" and optimal formulations of acoustic rake receivers, and show theoretically and numerically that the rake formulation of the maximum signal-to-interference-and-noise beamformer offers significant performance boosts in terms of noise and interference suppression. Beyond signal-to-noise ratio, we observe gains in terms of the \emph{perceptual evaluation of speech quality} (PESQ) metric for the speech quality. We accompany the paper by the complete simulation and processing chain written in Python. The code and the sound samples are available online at \url{http://lcav.github.io/AcousticRakeReceiver/}.
Privacy-Preserving Filtering for Event Streams
Venue: arXiv cs.SY 2015
Year: 2015

Many large-scale information systems such as intelligent transportation systems, smart grids or smart buildings collect data about the activities of their users to optimize their operations. To encourage participation and adoption of these systems, it is becoming increasingly important that the design process take privacy issues into consideration. In a typical scenario, signals originate from many sensors capturing events involving the users, and several statistics of interest need to be continuously published in real-time. This paper considers the problem of providing differential privacy guarantees for such multi-input multi-output systems processing event streams. We show how to construct and optimize various extensions of the zero-forcing equalization mechanism, which we previously proposed for single-input single-output systems. Some of these extensions can take a model of the input signals into account. We illustrate our privacy-preserving filter design methodology through the problem of privately monitoring and forecasting occupancy in a building equipped with multiple motion detection sensors.
Robust Distributed Averaging: When are Potential-Theoretic Strategies Optimal?
Venue: arXiv cs.SY 2015
Year: 2015

We study the interaction between a network designer and an adversary over a dynamical network. The network consists of nodes performing continuous-time distributed averaging. The adversary strategically disconnects a set of links to prevent the nodes from reaching consensus. Meanwhile, the network designer assists the nodes in reaching consensus by changing the weights of a limited number of links in the network. We formulate two Stackelberg games to describe this competition where the order in which the players act is reversed in the two problems. Although the canonical equations provided by the Pontryagin's maximum principle seem to be intractable, we provide an alternative characterization for the optimal strategies that makes connection to potential theory. Finally, we provide a sufficient condition for the existence of a saddle-point equilibrium for the underlying zero-sum game.
How the Voynich Manuscript was created
Venue: arXiv cs.CR 2015
Year: 2015

The Voynich manuscript is a medieval book written in an unknown script. This paper studies the relation between similarly spelled words in the Voynich manuscript. By means of a detailed analysis of similar spelled words it was possible to reveal the text generation method used for the Voynich manuscript.
Processing Social Media Messages in Mass Emergency: A Survey
Venue: arXiv cs.SI 2015
Year: 2015

Social media platforms provide active communication channels during mass convergence and emergency events such as disasters caused by natural hazards. As a result, first responders, decision makers, and the public can use this information to gain insight into the situation as it unfolds. In particular, many social media messages communicated during emergencies convey timely, actionable information. Processing social media messages to obtain such information, however, involves solving multiple challenges including: handling information overload, filtering credible information, and prioritizing different classes of messages. These challenges can be mapped to classical information processing operations such as filtering, classifying, ranking, aggregating, extracting, and summarizing. We survey the state of the art regarding computational methods to process social media messages, focusing on their application in emergency response scenarios. We examine the particularities of this setting, and then methodically examine a series of key sub-problems ranging from the detection of events to the creation of actionable and useful summaries.
Entropic one-class classifiers
Venue: arXiv cs.CV 2015
Year: 2015

The one-class classification problem is a well-known research endeavor in pattern recognition. The problem is also known under different names, such as outlier and novelty/anomaly detection. The core of the problem consists in modeling and recognizing patterns belonging only to a so-called target class. All other patterns are termed non-target, and therefore they should be recognized as such. In this paper, we propose a novel one-class classification system that is based on an interplay of different techniques. Primarily, we follow a dissimilarity representation based approach; we embed the input data into the dissimilarity space by means of an appropriate parametric dissimilarity measure. This step allows us to process virtually any type of data. The dissimilarity vectors are then represented through a weighted Euclidean graphs, which we use to (i) determine the entropy of the data distribution in the dissimilarity space, and at the same time (ii) derive effective decision regions that are modeled as clusters of vertices. Since the dissimilarity measure for the input data is parametric, we optimize its parameters by means of a global optimization scheme, which considers both mesoscopic and structural characteristics of the data represented through the graphs. The proposed one-class classifier is designed to provide both hard (Boolean) and soft decisions about the recognition of test patterns, allowing an accurate description of the classification process. We evaluate the performance of the system on different benchmarking datasets, containing either feature-based or structured patterns. Experimental results demonstrate the effectiveness of the proposed technique.
Secure aggregation of distributed information: How a team of agents can safely share secrets in front of a spy
Venue: arXiv cs.CR 2015
Year: 2015

We consider the generic problem of Secure Aggregation of Distributed Information (SADI), where several agents acting as a team have information distributed among them, modeled by means of a publicly known deck of cards distributed among the agents, so that each of them knows only her cards. The agents have to exchange and aggregate the information about how the cards are distributed among them by means of public announcements over insecure communication channels, intercepted by an adversary "eavesdropper", in such a way that the adversary does not learn who holds any of the cards. We present a combinatorial construction of protocols that provides a direct solution of a class of SADI problems and develop a technique of iterated reduction of SADI problems to smaller ones which are eventually solvable directly. We show that our methods provide a solution to a large class of SADI problems, including all SADI problems with sufficiently large size and sufficiently balanced card distributions.
Monotonic Preference Aggregation Mechanisms for Purchasing a Shareable Resource
Venue: arXiv cs.GT 2015
Year: 2015

Situations where a group of agents come together to jointly buy a resource that they individually cannot afford to buy are commonly observed in markets. For example in the US market for radio spectrum, a recent proposal invited small firms who would benefit from gaining additional access to spectrum to jointly submit bids for blocks of spectrum with the idea that its utilization could be shared. In such a scenario, the problem is to design a mechanism that truthfully elicits and aggregates the privately held preferences of these agents, and enables them to act as a single decision-making body in order to participate in the market. In this paper, we design a class of mechanisms called monotonic aggregation mechanisms that achieves this under a specific setting. We assume that the resource is being sold in a sealed-bid second-price auction that solicits bids for the entire resource. Our mechanism truthfully elicits utility functions from the buyers, prescribes a joint bid, and prescribes a division of the payment and the resource in the event that they win the resource in the auction. This mechanism further satisfies a popular notion of collusion-resistance known as coalition-strategyproofness. We give two explicit examples of this generic class for the case where the utility functions of the buyers are non-decreasing and concave.
Efficient Approximation of Channel Capacities
Venue: arXiv cs.IT 2015
Year: 2015

We propose an iterative method for approximately computing the capacity of discrete memoryless channels, possibly under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. The presented method requires $O(M^2 N \sqrt{\log N}/\varepsilon)$ to provide an estimate of the capacity to within $\varepsilon$, where $N$ and $M$ denote the input and output alphabet size; a single iteration has a complexity $O(M N)$. We also show how to approximately compute the capacity of memoryless channels having a bounded continuous input alphabet and a countable output alphabet under some mild assumptions on the decay rate of the channel's tail. It is shown that discrete-time Poisson channels fall into this problem class. As an example, we compute sharp upper and lower bounds for the capacity of a discrete-time Poisson channel with a peak-power input constraint.
Strict Self-Assembly of Fractals using Multiple Hands
Venue: arXiv cs.CG 2015
Year: 2015

In this paper we consider the problem of the strict self-assembly of infinite fractals within tile self-assembly. In particular, we provide tile assembly algorithms for the assembly of the discrete Sierpinski triangle and the discrete Sierpinski carpet within a class of models we term the \emph{$h$-handed assembly model} ($h$-HAM), which generalizes the 2-HAM to allow up to $h$ assemblies to combine in a single assembly step. Despite substantial consideration, no purely growth self-assembly model has yet been shown to strictly assemble an infinite fractal without significant modification to the fractal shape. In this paper we not only achieve this, but in the case of the Sierpinski carpet are able to achieve it within the 2-HAM, one of the most well studied tile assembly models in the literature. Our specific results are as follows. We provide a $6$-HAM construction for the Sierpinski triangle that works at scale factor 1, 30 tile types, and assembles the fractal in a \emph{near perfect} way in which all intermediate assemblies are finite-sized iterations of the recursive fractal. We further assemble the Sierpinski triangle within the $3$-HAM at scale factor 3 and 990 tile types. For the Sierpinski carpet, we present a $2$-HAM result that works at scale factor 3 and uses 1,216 tile types. We further include analysis showing that the aTAM is incapable of strictly assembling the non-tree Sierpinski triangle considered in this paper, and that multiple hands are needed for the near-perfect assembly of the Sierpinski triangle and the Sierpinski carpet.
New Results on Online Resource Minimization
Venue: arXiv cs.DS 2015
Year: 2015

We consider the online resource minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible schedule on a minimum number of machines. We rigorously study this problem and derive various algorithms with small constant competitive ratios for interesting restricted problem variants. As the most important special case, we consider scheduling jobs with agreeable deadlines. We provide the first constant ratio competitive algorithm for the non-preemptive setting, which is of particular interest with regard to the known strong lower bound of n for the general problem. For the preemptive setting, we show that the natural algorithm LLF achieves a constant ratio for agreeable jobs, while for general jobs it has a lower bound of Omega(n^(1/3)). We also give an O(log n)-competitive algorithm for the general preemptive problem, which improves upon the known O(p_max/p_min)-competitive algorithm. Our algorithm maintains a dynamic partition of the job set into loose and tight jobs and schedules each (temporal) subset individually on separate sets of machines. The key is a characterization of how the decrease in the relative laxity of jobs influences the optimum number of machines. To achieve this we derive a compact expression of the optimum value, which might be of independent interest. We complement the general algorithmic result by showing lower bounds that rule out that other known algorithms may yield a similar performance guarantee.
Alternative metrics in scientometrics: A meta-analysis of research into three altmetrics
Venue: arXiv cs.DL 2015
Year: 2015

Alternative metrics are currently one of the most popular research topics in scientometric research. This paper provides an overview of research into three of the most important altmetrics: microblogging (Twitter), online reference managers (Mendeley and CiteULike) and blogging. The literature is discussed in relation to the possible use of altmetrics in research evaluation. Since the research was particularly interested in the correlation between altmetrics counts and citation counts, this overview focuses particularly on this correlation. For each altmetric, a meta-analysis is calculated for its correlation with traditional citation counts. As the results of the meta-analyses show, the correlation with traditional citations for micro-blogging counts is negligible (pooled r=0.003), for blog counts it is small (pooled r=0.12) and for bookmark counts from online reference managers, medium to large (CiteULike pooled r=0.23; Mendeley pooled r=0.51).