Multi-Label Active Learning from Crowds

Multi-label active learning is a hot topic in reducing the label cost by optimally choosing the most valuable instance to query its label from an oracle. In this paper, we consider the poolbased multi-label active learning under the crowdsourcing setting, where during the active query process, instead of resorting to a high cost oracle for the ground-truth, multiple low cost imperfect annotators with various expertise are available for labeling. To deal with this problem, we propose the MAC (Multi-label Active learning from Crowds) approach which incorporate the local influence of label correlations to build a probabilistic model over the multi-label classifier and annotators. Based on this model, we can estimate the labels for instances as well as the expertise of each annotator. Then we propose the instance selection and annotator selection criteria that consider the uncertainty/diversity of instances and the reliability of annotators, such that the most reliable annotator will be queried for the most valuable instances. Experimental results demonstrate the effectiveness of the proposed approach.

Parameter Database : Data-centric Synchronization for Scalable Machine Learning

We propose a new data-centric synchronization framework for carrying out of machine learning (ML) tasks in a distributed environment. Our framework exploits the iterative nature of ML algorithms and relaxes the application agnostic bulk synchronization parallel (BSP) paradigm that has previously been used for distributed machine learning. Data-centric synchronization complements function-centric synchronization based on using stale updates to increase the throughput of distributed ML computations. Experiments to validate our framework suggest that we can attain substantial improvement over BSP while guaranteeing sequential correctness of ML tasks.

Perceptron like Algorithms for Online Learning to Rank

Perceptron is a classic online algorithm for learning a classification function. We provide the first extension of the perceptron algorithm to the learning to rank problem under popular performance measures such as NDCG and MAP. A modern perspective on perceptron in classification is to interpret it as online gradient descent (OGD), during mistake rounds, on the hinge loss function. Motivated by this interpretation, we propose a novel family of \emph{listwise} large margin ranking surrogates. Members of this family can be thought of as analogues of the hinge loss. Using the proposed family, we provide a guaranteed upper bound on the cumulative NDCG (or MAP) induced loss incurred by our perceptron like algorithm. In a guarantee reminiscent of Novikoff’s convergence theorem for the classic perceptron, we show that if there exists an oracle ranker which can correctly rank each instance in an online sequence of ranking data, our perceptron algorithm makes no more than a finite number of mistakes on that sequence. We provide empirical results on large commercial datasets to corroborate our theoretical results.

Qualitative Decision Methods for Multi-Attribute Decision Making

The fundamental problem underlying all multi-criteria decision analysis (MCDA) problems is that of dominance between any two alternatives: ‘Given two alternatives A and B, each described by a set criteria, is A preferred to B with respect to a set of decision maker (DM) preferences over the criteria?’. Depending on the application in which MCDA is performed, the alternatives may represent strategies and policies for business, potential locations for setting up new facilities, designs of buildings, etc. The general objective of MCDA is to enable the DM to order all alternatives in order of the stated preferences, and choose the ones that are best, i.e., optimal with respect to the preferences over the criteria. This article presents and summarizes a recently developed MCDA framework that orders the set of alternatives when the relative importance preferences are incomplete, imprecise, or qualitative in nature.

The k-mismatch problem revisited

We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and every m-length substring of a text of length n, as long as that Hamming distance is at most k. Where the Hamming distance is greater than k at some alignment of the pattern and text, we simply output ‘No’. We study this problem in both the standard offline setting and also as a streaming problem. In the streaming k-mismatch problem the text arrives one symbol at a time and we must give an output before processing any future symbols. Our main results are as follows: 1) Our first result is a deterministic O(n k^2\log{k} / m+n \text{polylog} m) time offline algorithm for k-mismatch on a text of length n. This is a factor of k improvement over the fastest previous result of this form from SODA 2000 by Amihood Amir et al. 2) We then give a randomised and online algorithm which runs in the same time complexity but requires only O(k^2\text{polylog} {m}) space in total. 3) Next we give a randomised (1+\epsilon)-approximation algorithm for the streaming k-mismatch problem which uses O(k^2\text{polylog} m / \epsilon^2) space and runs in O(\text{polylog} m / \epsilon^2) worst-case time per arriving symbol. 4) Finally we combine our new results to derive a randomised O(k^2\text{polylog} {m}) space algorithm for the streaming k-mismatch problem which runs in O(\sqrt{k}\log{k} + \text{polylog} {m}) worst-case time per arriving symbol. This improves the best previous space complexity for streaming k-mismatch from FOCS 2009 by Benny Porat and Ely Porat by a factor of k. We also improve the time complexity of this previous result by an even greater factor to match the fastest known offline algorithm (up to logarithmic factors).

Adaptivity and Computation-Statistics Tradeoffs for Kernel and Distance based High Dimensional Two Sample Testing

An extension of Hewitt’s inversion formula and its application to fluctuation theory

Anchored boundary conditions for locally isostatic networks

Asynchronous stochastic convex optimization

Bayesian mixtures of spatial spline regressions

Bayesian Nonparameteric Multiresolution Estimation for the American Community Survey

Bayesian Nonparametric Functional Mixture Estimation for Time-Series Data, With Application to Estimation of State Employment Totals

Combinatorial Hopf algebras and topological Tutte polynomials

Control Problem on Space of Random Variables and Master Equation

Decompositions of complete multigraphs into cycles of varying lengths

Deterministic Differential Search Algorithm for Distributed Sensor/Relay Networks

Difference operators for partitions and some applications

Dynamics of fully coupled rotators with unimodal and bimodal frequency distribution

Excluding hooks and their complements

Factor Graphs for Quantum Probabilities

Fast Consensus under Eventually Stabilizing Message Adversaries

Fixed-point algorithms for determinantal point processes

Hankel determinants of random moment sequences

Identifying Avatar Aliases in Starcraft 2

Lattices related to extensions of presentations of transversal matroids

Negaperiodic Golay pairs and Hadamard matrices

Non-commutative Edmonds’ problem and matrix semi-invariants

On beta distributed limits of iterated linear random functions

One-dimensional infinite memory imitation models with noise

Predicting respiratory motion for real-time tumour tracking in radiotherapy

Quasi-invariant Gaussian measures for the cubic fourth order nonlinear Schrödinger equation

Regularity of Gaussian Processes on Dirichlet spaces

Sparse PCA via Bipartite Matchings

Stabilization and Fault-Tolerance in Presence of Unchangeable Environment Actions

Staged Multi-armed Bandits

Stochastic Ising model with flipping sets of spins and fast decreasing temperature

Synchronization of qubit ensemble under optimized $π$-pulse driving

The $λ$-Martin entrance boundary of subcritical Bienaymé–Galton–Watson processes

Trans-Dimensional Bayesian Inference for Gravitational Lens Substructures

Travelling wave solutions to the KPP equation with branching noise arising from initial conditions with compact support

Variations of the Power-Conditional-Expected-Posterior Prior for Bayesian Variable Selection in Generalized Linear Models