OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Inference in Crowdsourced Classification via Belief Propagation
Venue: arXiv cs.LG 2017
Year: 2017

Crowdsourcing systems are popular for solving large-scale labelling tasks with low-paid workers. We study the problem of recovering the true labels from the possibly erroneous crowdsourced labels under the popular Dawid-Skene model. To address this inference problem, several algorithms have recently been proposed, but the best known guarantee is still significantly larger than the fundamental limit. We close this gap by introducing a tighter lower bound on the fundamental limit and proving that Belief Propagation (BP) exactly matches this lower bound. The guaranteed optimality of BP is the strongest in the sense that it is information-theoretically impossible for any other algorithm to correctly label a larger fraction of the tasks. Experimental results suggest that BP is close to optimal for all regimes considered and improves upon competing state-of-the-art algorithms.
A complexity trichotomy for approximately counting list H-colourings
Venue: arXiv cs.CC 2017
Year: 2017

We examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is trivially in polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph or a reflexive proper interval graph then approximately counting list H-colourings is equivalent to #BIS, the problem of approximately counting independent sets in a bipartite graph. This is a well-studied problem which is believed to be of intermediate complexity -- it is believed that it does not have an FPRAS, but that it is not as difficult as approximating the most difficult counting problems in #P. For every other graph H, approximately counting list H-colourings is complete for #P with respect to approximation-preserving reductions (so there is no FPRAS unless NP=RP). Two pleasing features of the trichotomy are (i) it has a natural formulation in terms of hereditary graph classes, and (ii) the proof is largely self-contained and does not require any universal algebra (unlike similar dichotomies in the weighted case). We are able to extend the hardness results to the bounded-degree setting, showing that all hardness results apply to input graphs with maximum degree at most 6.
Diffusion leaky LMS algorithm: analysis and implementation
Venue: arXiv cs.SY 2017
Year: 2017

The diffusion least-mean square (dLMS) algorithms have attracted much attention owing to its robustness for distributed estimation problems. However, the performance of such filters may change when they are implemented for suppressing noises from speech signals. To overcome this problem, a diffusion leaky dLMS algorithm is proposed in this work, which is characterized by its numerical stability and small misadjustment for noisy speech signals when the unknown system is a lowpass filter. Finally, two implementations of the leaky dLMS are introduced. It is demonstrated that the leaky dLMS can be effectively introduced into a noise reduction network for speech signals.
Tracking Influential Nodes in Dynamic Networks
Venue: arXiv cs.SI 2017
Year: 2017

In this paper, we tackle a challenging problem inherent in a series of applications: tracking the influential nodes in dynamic networks. Specifically, we model a dynamic network as a stream of edge weight updates. This general model embraces many practical scenarios as special cases, such as edge and node insertions, deletions as well as evolving weighted graphs. Under the popularly adopted linear threshold model and independent cascade model, we consider two essential versions of the problem: finding the nodes whose influences passing a user specified threshold and finding the top-$k$ most influential nodes. Our key idea is to use the polling-based methods and maintain a sample of random RR sets so that we can approximate the influence of nodes with provable quality guarantees. We develop an efficient algorithm that incrementally updates the sample random RR sets against network changes. We also design methods to determine the proper sample sizes for the two versions of the problem so that we can provide strong quality guarantees and, at the same time, be efficient in both space and time. In addition to the thorough theoretical results, our experimental results on $5$ real network data sets clearly demonstrate the effectiveness and efficiency of our algorithms.
Equilibrium Propagation: Bridging the Gap Between Energy-Based Models and Backpropagation
Venue: arXiv cs.LG 2017
Year: 2017

We introduce Equilibrium Propagation, a learning framework for energy-based models. It involves only one kind of neural computation, performed in both the first phase (when the prediction is made) and the second phase of training (after the target or prediction error is revealed). Although this algorithm computes the gradient of an objective function just like Backpropagation, it does not need a special computation or circuit for the second phase, where errors are implicitly propagated. Equilibrium Propagation shares similarities with Contrastive Hebbian Learning and Contrastive Divergence while solving the theoretical issues of both algorithms: our algorithm computes the gradient of a well defined objective function. Because the objective function is defined in terms of local perturbations, the second phase of Equilibrium Propagation corresponds to only nudging the prediction (fixed point, or stationary distribution) towards a configuration that reduces prediction error. In the case of a recurrent multi-layer supervised network, the output units are slightly nudged towards their target in the second phase, and the perturbation introduced at the output layer propagates backward in the hidden layers. We show that the signal 'back-propagated' during this second phase corresponds to the propagation of error derivatives and encodes the gradient of the objective function, when the synaptic update corresponds to a standard form of spike-timing dependent plasticity. This work makes it more plausible that a mechanism similar to Backpropagation could be implemented by brains, since leaky integrator neural computation performs both inference and error back-propagation in our model. The only local difference between the two phases is whether synaptic changes are allowed or not.
Cooperative Channel Estimation for Coordinated Transmission with Limited Backhaul
Venue: arXiv cs.IT 2017
Year: 2017

Obtaining accurate global channel state information (CSI) at multiple transmitter devices is critical to the performance of many coordinated transmission schemes. Practical CSI local feedback often leads to noisy and partial CSI estimates at each transmitter. With rate-limited bi-directional backhaul, transmitters have the opportunity to exchange few CSI-related bits to establish global channel state information at transmitter (CSIT). This work investigates possible strategies towards this goal. We propose a novel decentralized algorithm that produces minimum mean square error (MMSE)-optimal global channel estimates at each device from combining local feedback and information exchanged through backhauls. The method adapts to arbitrary initial information topologies and feedback noise statistics and can do that with a combination of closed-form and convex approaches. Simulations for coordinated multi-point (CoMP) transmission systems with two or three transmitters exhibit the advantage of the proposed algorithm over conventional CSI exchange mechanisms when the coordination backhauls are limited.
Loongson IoT Gateway: A Technical Review
Venue: arXiv cs.OH 2017
Year: 2017

A prototype of Loongson IoT (Internet of Things) ZigBee gateway is already designed and implemented. However, this prototype is not perfect enough because of the lack of a number of functions. And a lot of things should be done to improve this prototype, such as adding widely used IEEE 802.11 function, using a fully open source ZigBee protocol stack to get rid of proprietary implement or using a fully open source embedded operating system to support 6LoWPAN, and implementing multiple interfaces.
A topological view on algebraic computation models
Venue: arXiv cs.LO 2017
Year: 2017

We investigate the topological aspects of some algebraic computation models, in particular the BSS-model. Our results can be seen as bounds on how different BSS-computability and computability in the sense of computable analysis can be. The framework for this is Weihrauch reducibility. As a consequence of our characterizations, we establish that the solvability complexity index is (mostly) independent of the computational model, and that there thus is common ground in the study of non-computability between the BSS and TTE setting.
Joint Scheduling and Power-Control for Delay Guarantees in Heterogeneous Cognitive Radios
Venue: arXiv cs.IT 2017
Year: 2017

An uplink multi secondary user (SU) cognitive radio system having average delay constraints as well as an interference constraint to the primary user (PU) is considered. If the interference channels between the SUs and the PU are statistically heterogeneous due to the different physical locations of the different SUs, the SUs will experience different delay performances. This is because SUs located closer to the PU transmit with lower power levels. Two dynamic scheduling-and-power-allocation policies that can provide the required average delay guarantees to all SUs irrespective of their locations are proposed. The first policy solves the problem when the interference constraint is an instantaneous one, while the second is for problems with long-term average interference constraints. We show that although the average interference problem is an extension to the instantaneous interference one, the solution is totally different. The two policies, derived using the Lyapunov optimization technique, are shown to be asymptotically delay optimal while satisfying the delay and interference constraints. Our findings are supported by extensive system simulations and shown to outperform existing policies as well as shown to be robust to channel estimation errors.
Characterization of threshold functions: state of the art, some new contributions and open problems
Venue: arXiv cs.GT 2017
Year: 2017

This paper has a twofold scope. The first one is to clarify and put in evidence the isomorphic character of two theories developed in quite different fields: on one side, threshold logic, on the other side, simple games. One of the main purposes in both theories is to determine when a simple game is representable as a weighted game, which allows a very compact and easily comprehensible representation. Deep results were found in threshold logic in the sixties and seventies for this problem. However, game theory has taken the lead and some new results have been obtained for the problem in the last two decades. The second and main goal of this paper is to provide some new results on this problem and propose several open questions and conjectures for future research. The results we obtain depend on two significant parameters of the game: the number of types of equivalent players and the number of types of shift-minimal winning coalitions.
Efficiently characterizing games consistent with perturbed equilibrium observations
Venue: arXiv cs.GT 2017
Year: 2017

We study the problem of characterizing the set of games that are consistent with observed equilibrium play. Our contribution is to develop and analyze a new methodology based on convex optimization to address this problem for many classes of games and observation models of interest. Our approach provides a sharp, computationally efficient characterization of the extent to which a particular set of observations constrains the space of games that could have generated them. This allows us to solve a number of variants of this problem as well as to quantify the power of games from particular classes (e.g., zero-sum, potential, linearly parameterized) to explain player behavior. We illustrate our approach with numerical simulations.
High precision grasp pose detection in dense clutter
Venue: arXiv cs.RO 2017
Year: 2017

This paper considers the problem of grasp pose detection in point clouds. We follow a general algorithmic structure that first generates a large set of 6-DOF grasp candidates and then classifies each of them as a good or a bad grasp. Our focus in this paper is on improving the second step by using depth sensor scans from large online datasets to train a convolutional neural network. We propose two new representations of grasp candidates, and we quantify the effect of using prior knowledge of two forms: instance or category knowledge of the object to be grasped, and pretraining the network on simulated depth data obtained from idealized CAD models. Our analysis shows that a more informative grasp candidate representation as well as pretraining and prior knowledge significantly improve grasp detection. We evaluate our approach on a Baxter Research Robot and demonstrate an average grasp success rate of 93% in dense clutter. This is a 20% improvement compared to our prior work.
Single Image Restoration for Participating Media Based on Prior Fusion
Venue: arXiv cs.CV 2017
Year: 2017

This paper describes a method to restore degraded images captured in a participating media -- fog, turbid water, sand storm, etc. Differently from the related work that only deal with a medium, we obtain generality by using an image formation model and a fusion of new image priors. The model considers the image color variation produced by the medium. The proposed restoration method is based on the fusion of these priors and supported by statistics collected on images acquired in both non-participating and participating media. The key of the method is to fuse two complementary measures --- local contrast and color data. The obtained results on underwater and foggy images demonstrate the capabilities of the proposed method. Moreover, we evaluated our method using a special dataset for which a ground-truth image is available.
Hanabi is NP-hard, Even for Cheaters who Look at Their Cards
Venue: arXiv cs.DM 2017
Year: 2017

In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among $c$ colors and a number between $1$ and $n$. The aim is to make, for each color, a pile of cards of that color with all increasing numbers from $1$ to $n$. At each time during the game, each player holds $h$ cards in hand. Cards are drawn sequentially from a deck and the players should decide whether to play, discard or store them for future use. One of the features of the game is that the players can see their partners' cards but not their own and information must be shared through hints. We introduce a single-player, perfect-information model and show that the game is intractable even for this simplified version where we forego both the hidden information and the multiplayer aspect of the game, even when the player can only hold two cards in her hand. On the positive side, we show that the decision version of the problem---to decide whether or not numbers from $1$ through $n$ can be played for every color---can be solved in (almost) linear time for some restricted cases.
Mining Hierarchical Temporal Roles with Multiple Metrics
Venue: arXiv cs.CR 2017
Year: 2017

Temporal role-based access control (TRBAC) extends role-based access control to limit the times at which roles are enabled. This paper presents a new algorithm for mining high-quality TRBAC policies from timed ACLs (i.e., ACLs with time limits in the entries) and optionally user attribute information. Such algorithms have potential to significantly reduce the cost of migration from timed ACLs to TRBAC. The algorithm is parameterized by the policy quality metric. We consider multiple quality metrics, including number of roles, weighted structural complexity (a generalization of policy size), and (when user attribute information is available) interpretability, i.e., how well role membership can be characterized in terms of user attributes. Ours is the first TRBAC policy mining algorithm that produces hierarchical policies, and the first that optimizes weighted structural complexity or interpretability. In experiments with datasets based on real-world ACL policies, our algorithm is more effective than previous algorithms at optimizing policy quality.
Pose for Action - Action for Pose
Venue: arXiv cs.CV 2017
Year: 2017

In this work we propose to utilize information about human actions to improve pose estimation in monocular videos. To this end, we present a pictorial structure model that exploits high-level information about activities to incorporate higher-order part dependencies by modeling action specific appearance models and pose priors. However, instead of using an additional expensive action recognition framework, the action priors are efficiently estimated by our pose estimation framework. This is achieved by starting with a uniform action prior and updating the action prior during pose estimation. We also show that learning the right amount of appearance sharing among action classes improves the pose estimation. We demonstrate the effectiveness of the proposed method on two challenging datasets for pose estimation and action recognition with over 80,000 test images.
Performance Analysis of Source Image Estimators in Blind Source Separation
Venue: arXiv cs.SD 2017
Year: 2017

Blind methods often separate or identify signals or signal subspaces up to an unknown scaling factor. Sometimes it is necessary to cope with the scaling ambiguity, which can be done through reconstructing signals as they are received by sensors, because scales of the sensor responses (images) have known physical interpretations. In this paper, we analyze two approaches that are widely used for computing the sensor responses, especially, in Frequency-Domain Independent Component Analysis. One approach is the least-squares projection, while the other one assumes a regular mixing matrix and computes its inverse. Both estimators are invariant to the unknown scaling. Although frequently used, their differences were not studied yet. A goal of this work is to fill this gap. The estimators are compared through a theoretical study, perturbation analysis and simulations. We point to the fact that the estimators are equivalent when the separated signal subspaces are orthogonal, and vice versa. Two applications are shown, one of which demonstrates a case where the estimators yield substantially different results.
Stationary Graph Processes and Spectral Estimation
Venue: arXiv cs.SY 2017
Year: 2017

Stationarity is a cornerstone property that facilitates the analysis and processing of random signals in the time domain. Although time-varying signals are abundant in nature, in many practical scenarios the information of interest resides in more irregular graph domains. This lack of regularity hampers the generalization of the classical notion of stationarity to graph signals. The contribution in this paper is twofold. Firstly, we propose a definition of weak stationarity for random graph signals that takes into account the structure of the graph where the random process takes place, while inheriting many of the meaningful properties of the classical definition in the time domain. Our definition requires that stationary graph processes can be modeled as the output of a linear graph filter applied to a white input. We will show that this is equivalent to requiring the correlation matrix to be diagonalized by the graph Fourier transform. Secondly, we analyze the properties of the power spectral density and propose a number of methods to estimate it. We start with nonparametric approaches, including periodograms, window-based average periodograms, and filter banks. We then shift the focus to parametric approaches, discussing the estimation of moving-average (MA), autoregressive (AR) and ARMA processes. Finally, we illustrate the power spectral density estimation in synthetic and real-world graphs.
On the Whittle Index for Restless Multi-armed Hidden Markov Bandits
Venue: arXiv cs.SY 2017
Year: 2017

We consider a restless multi-armed bandit in which each arm can be in one of two states. When an arm is sampled, the state of the arm is not available to the sampler. Instead, a binary signal with a known randomness that depends on the state of the arm is available. No signal is available if the arm is not sampled. An arm-dependent reward is accrued from each sampling. In each time step, each arm changes state according to known transition probabilities which in turn depend on whether the arm is sampled or not sampled. Since the state of the arm is never visible and has to be inferred from the current belief and a possible binary signal, we call this the hidden Markov bandit. Our interest is in a policy to select the arm(s) in each time step that maximizes the infinite horizon discounted reward. Specifically, we seek the use of Whittle's index in selecting the arms. We first analyze the single-armed bandit and show that in general, it admits an approximate threshold-type optimal policy when there is a positive reward for the `no-sample' action. We also identify several special cases for which the threshold policy is indeed the optimal policy. Next, we show that such a single-armed bandit also satisfies an approximate-indexability property. For the case when the single-armed bandit admits a threshold-type optimal policy, we perform the calculation of the Whittle index for each arm. Numerical examples illustrate the analytical results.
Safe Learning of Regions of Attraction for Uncertain, Nonlinear Systems with Gaussian Processes
Venue: arXiv cs.SY 2017
Year: 2017

Control theory can provide useful insights into the properties of controlled, dynamic systems. One important property of nonlinear systems is the region of attraction (ROA), a safe subset of the state space in which a given controller renders an equilibrium point asymptotically stable. The ROA is typically estimated based on a model of the system. However, since models are only an approximation of the real world, the resulting estimated safe region can contain states outside the ROA of the real system. This is not acceptable in safety-critical applications. In this paper, we consider an approach that learns the ROA from experiments on a real system, without ever leaving the true ROA and, thus, without risking safety-critical failures. Based on regularity assumptions on the model errors in terms of a Gaussian process prior, we use an underlying Lyapunov function in order to determine a region in which an equilibrium point is asymptotically stable with high probability. Moreover, we provide an algorithm to actively and safely explore the state space in order to expand the ROA estimate. We demonstrate the effectiveness of this method in simulation.