  Self-supervised clustering methods have achieved increasing accuracy in
recent years but do not yet perform as well as supervised classification
methods. This contrasts with the situation for feature learning, where
self-supervised features have recently surpassed the performance of supervised
features on several important tasks. We hypothesize that the performance gap is
due to the difficulty of specifying, without supervision, which features
correspond to class differences that are semantic to humans. To reduce the
performance gap, we introduce the "single-noun" prior - which states that
semantic clusters tend to correspond to concepts that humans label by a
single-noun. By utilizing a pre-trained network that maps images and sentences
into a common space, we impose this prior obtaining a constrained optimization
task. We show that our formulation is a special case of the facility location
problem, and introduce a simple-yet-effective approach for solving this
optimization task at scale. We test our approach on several commonly reported
image clustering datasets and obtain significant accuracy gains over the best
existing approaches.
