Online Graph Completion: Multivariate Signal Recovery in Computer Vision
[pdf]
Abstract. The adoption of "human-in-the-loop" paradigms in
computer vision and machine learning is leading to various
applications where the actual data acquisition (e.g., human
supervision) and the underlying inference algorithms are
closely interwined. While classical work in active learning
provides effective solutions when the learning module
involves classification and regression tasks, many practical
issues such as partially observed measurements, financial
constraints and even additional distributional or structural
aspects of the data typically fall outside the scope of this
treatment. For instance, with sequential acquisition of partial
measurements of data that manifest as a matrix (or tensor),
novel strategies for completion (or collaborative filtering)
of the remaining entries have only been studied recently.
Motivated by vision problems where we seek to annotate
a large dataset of images via a crowdsourced platform
or alternatively, complement results from a state-of-the-art object detector using human feedback, we study the
“completion” problem defined on graphs, where requests
for additional measurements must be made sequentially. We
design the optimization model in the Fourier domain of the
graph describing how ideas based on adaptive submodularity
provide algorithms that work well in practice. On a
large set of images collected from Imgur, we see promising
results on images that are otherwise difficult to categorize.
We also show applications to an experimental design problem
in neuroimaging.
Figure: An example of graph completion on Armadillo mesh, given
edge weights based on curvature. Left: noisy signal on the mesh, Middle:
partial observation on the signal, Right: recovery of the signal on the mesh.
Figure: Various results on object label estimation from our Imgur experiment. YOLO did not confidently assign any labels on these images (i.e., below
40% confidence) using our 75 categories. However, our framework suggested that there were some objects in these image. The images represent nodes and
the lines denote edges in our framework, and there are strong relationships between images with same object labels.
References:
[1] Won Hwa Kim, Mona Jalal, Seong Jae Hwang, Sterling C. Johnson, Vikas Singh,
"Online Graph Completion: Multivariate Signal Recovery in Computer Vision",
Computer Vision and Pattern Recognition (CVPR), 2017.
[pdf]
Acknowledgment:
This research was supported by NIH grants AG040396,
AG021155, EB022883, NSF CAREER award 1252725,
UW ADRC AG033514, UW CIBM 5T15LM007359-14,
and UW CPCP AI117924.