papers
As you like it: Localization via paired comparisons
journal
Andrew K. Massimino & Mark A. Davenport
Journal of Machine Learning Research.
abstract
Suppose that we wish to estimate a vector $\mathbf{x}$ from a set of binary paired comparisons of the form "$\mathbf{x}$ is closer to $\mathbf{p}$ than to $\mathbf{q}$" for various choices of vectors $\mathbf{p}$ and $\mathbf{q}$. The problem of estimating $\mathbf{x}$ from this type of observation arises in a variety of contexts, including nonmetric multidimensional scaling, "unfolding," and ranking problems, often because it provides a powerful and flexible model of preference. We describe theoretical bounds for how well we can expect to estimate $\mathbf{x}$ under a randomized model for $\mathbf{p}$ and $\mathbf{q}$. We also present results for the case where the comparisons are noisy and subject to some degree of error. Additionally, we show that under a randomized model for $\mathbf{p}$ and $\mathbf{q}$, a suitable number of binary paired comparisons yield a stable embedding of the space of target vectors. Finally, we also that we can achieve significant gains by adaptively changing the distribution for choosing $\mathbf{p}$ and $\mathbf{q}$.
Active Embedding Search via Noisy Paired Comparisons
conference
Gregory Canal, Andrew K. Massimino, Mark A. Davenport, & Christopher Rozell
Proc. Int. Conf. on Machine Learning (ICML). Long Beach, CA.
abstract
Suppose that we wish to estimate a user’s preference vector w from paired comparisons of the form “does user w prefer item p or item q?,” where both the user and items are embedded in a low-dimensional Euclidean space with distances that reflect user and item similarities. Such observations arise in numerous settings, including psychometrics and psychology experiments, search tasks, advertising, and recommender systems. In such tasks, queries can be extremely costly and subject to varying levels of response noise; thus, we aim to actively choose pairs that are most informative given the results of previous comparisons. We provide new theoretical insights into the benefits and challenges of greedy information maximization in this setting, and develop two novel heuristics that maximize lower bounds on information gain and are simpler to analyze and compute respectively. We use simulated responses from a real-world dataset to validate our heuristics through their similar performance to greedy information maximization, and their superior preference estimation over state-of-the-art selection methods as well as random queries.
Jun.
2019
pdf
Learning to adapt under practical sensing constraints
thesis
Andrew K. Massimino
Georgia Institute of Technology. Atlanta, GA.
abstract
The purpose of this work is to explore the capability of sensing systems to acquire information adaptively when they are subject to practical measurement constraints. By leveraging problem structure such as sparsity and probabilistic data models, intelligent sampling schemes have the potential to enable higher quality estimation with less sensing effort in diverse applications such as imaging, recommendation systems, information retrieval, and psychometric studies. Existing approaches to adaptive sensing are often limited in practice as they require the ability to take arbitrary measurements while in realistic situations, measurements must taken according to various limitations. Two representative constrained scenarios are considered: linear settings in which measurement rows are chosen from a fixed collection and where estimation may be performed only via sequentially chosen paired comparisons. Theoretical and empirical evidence are provided to suggest that adaptivity can result in substantial improvements in these constrained settings.
Dec.
2018
The geometry of random paired comparisons
conference
Andrew K. Massimino & Mark A. Davenport
Proc. IEEE Int. Conf Acoust Speech Signal Process (ICASSP). New Orleans, LA.
abstract
Suppose that we are able to obtain binary paired comparisons of the form "$x$ is closer to $p$ than to q" for various choices of vectors p and q. Such observations arise in a variety of contexts, including nonmetric multidimensional scaling, unfolding, and ranking problems, often because they provide a powerful and flexible model of preference. In this paper we give a theoretical bound for how well we can expect to estimate x under a randomized model for p and q. We also show that we can achieve significant gains by adaptively changing the distribution for choosing p and q.
Constrained Adaptive Sensing
journal
Mark A. Davenport, Andrew K. Massimino, Deanna Needell, & Tina Woolf
IEEE Transactions on Signal Processing.
(Pre-print available: arXiv:1506.05889)
abstract
Suppose that we wish to estimate a vector $\mathbf{x} \in \mathbb{C}^n$ from a small number of noisy linear measurements of the form $\mathbf{y} = \mathbf{A x} + \mathbf{z}$, where $\mathbf{z}$ represents measurement noise. When the vector $\mathbf{x}$ is sparse, meaning that it has only $s$ nonzeros with $s \ll n$, one can obtain a significantly more accurate estimate of $\mathbf{x}$ by adaptively selecting the rows of $\mathbf{A}$ based on the previous measurements provided that the signal-to-noise ratio (SNR) is sufficiently large. In this paper we consider the case where we wish to realize the potential of adaptivity but where the rows of $\mathbf{A}$ are subject to physical constraints. In particular, we examine the case where the rows of $\mathbf{A}$ are constrained to belong to a finite set of allowable measurement vectors. We demonstrate both the limitations and advantages of adaptive sensing in this constrained setting. We prove that for certain measurement ensembles, the benefits offered by adaptive designs fall far short of the improvements that are possible in the unconstrained adaptive setting. On the other hand, we also provide both theoretical and empirical evidence that in some scenarios adaptivity does still result in substantial improvements even in the constrained setting. To illustrate these potential gains, we propose practical algorithms for constrained adaptive sensing by exploiting connections to the theory of optimal experimental design and show that these algorithms exhibit promising performance in some representative applications.
Binary stable embedding via paired comparisons
conference
Andrew K. Massimino & Mark A. Davenport
Proc. IEEE Work. on Statistical Signal Processing (SSP). Palma de Mallorca, Spain.
abstract
Suppose that we wish to estimate a vector $\mathbf{x}$ from a set of binary paired comparisons of the form “$\mathbf{x}$ is closer to $\mathbf{p}$ than to $\mathbf{q}$” for various choices of vectors $\mathbf{p}$ and $\mathbf{q}$. The problem of estimating $\mathbf{x}$ from this type of observation arises in a variety of contexts, including nonmetric multidimensional scaling, “unfolding,” and ranking problems, often because it provides a powerful and flexible model of preference. The main contribution of this paper is to show that under a randomized model for $\mathbf{p}$ and $\mathbf{q}$, a suitable number of binary paired comparisons yield a stable embedding of the space of target vectors.
Randomized multi-pulse time-of-flight mass spectrometry
conference
Michael G. Moore, Andrew K. Massimino, & Mark A. Davenport
Proc. IEEE Int. Work. on Computational Advances in Multi-Sensor Adaptive Process. (CAMSAP). Cancun, Mexico.
abstract
Mass spectrometry is one of the primary methods for chemical analysis and serves as a fundamental tool in numerous scientific disciplines. In this paper we consider the design of time-of-flight mass spectrometers, which produce a stream of measurements which can be modeled by a convolution between the mass spectrum of interest and a specified pulsing pattern. Our goal is to reduce the total time necessary to analyze a sample to a given precision (or equivalently, given a fixed amount of time, to obtain a more precise estimate of the sample). We can do this by leveraging the structure that exists in typical mass spectra. In particular, since any given substance is usually composed of a relatively small number of distinct molecules, mass spectra tend to be relatively sparse. In this paper we perform an analysis of an idealized model of a time-of-flight mass spectrometer which uses a randomized pulsing pattern. Such an architecture has the potential to enable a new tradeoff between acquisition time and precision/dynamic range. We show that under certain natural conditions on the randomized scheme—namely, that the system does not pulse too often—this construction will lead to a system which satisfies certain desirable properties that are sufficient to ensure that sparse recovery is possible. In particular, we show that with high probability, the system will satisfy the conditions of a bipartite expander graph provided the pulsing rate is not too large. We then conclude with a range of simulations that support our theoretical analysis and demonstrate the practical viability of this approach.
Constrained adaptive sensing [conference version]
conference
Mark A. Davenport, Andrew K. Massimino, D. Needell, & T. Woolf
Proc. Work. on Signal Processing with Adaptive Sparse Structured Representations (SPARS). Cambridge, United Kingdom.
One-bit matrix completion for pairwise comparison matrices
conference
Andrew K. Massimino & Mark A. Davenport
Proc. Work. on Signal Processing with Adaptive Sparse Structured Representations (SPARS). Lausanne, Switzerland.
abstract
In this paper we consider the related problems of ranking and of recovering a matrix of pairwise comparisons from binary observations. We describe a naïve adaptation of the one-bit matrix completion framework, but then note that additional constraints that arise in the context of ranking allows us to replace nuclear norm minimization with a more direct approach. This ultimately leads to a novel viewpoint on a classic approach to the ranking problem.Both theoretical and experimental results show that this simplified approach to recovering a pairwise comparison matrix performs significantly better than the naïve approach.