Perceptual adjustment queries and an inverted measurement paradigm for
  low-rank metric learning
Austin Xu Andrew D. McRae Jingyan Wang Mark A. Davenport Ashwin Pananjady
We introduce a new type of query mechanism for collecting human feedback,
called the perceptual adjustment query ( PAQ). Being both informative and
cognitively lightweight, the PAQ adopts an inverted measurement scheme, and
combines advantages from both cardinal and ordinal queries. We showcase the PAQ
in the metric learning problem, where we collect PAQ measurements to learn an
unknown Mahalanobis distance. This gives rise to a high-dimensional, low-rank
matrix estimation problem to which standard matrix estimators cannot be
applied. Consequently, we develop a two-stage estimator for metric learning
from PAQs, and provide sample complexity guarantees for this estimator. We
present numerical simulations demonstrating the performance of the estimator
and its notable properties.