How might we teach machine learning systems about what wine tastes like, or how to appreciate the similarities in different kinds of artwork? On its face, this question seems absurd because these notions of similarity are impossible to characterize in meaningful ways. Our work explores what happens when we can embrace this ambiguity. We use new kinds of semi-supervision to learn abstract, intuitive notions of perceptual similarity when labels or dense similarity measures are not available. Before we can learn about perceptual similarity, we must first show how to capture intuitive notions of similarity from humans in an efficient and principled way that makes as few assumptions as possible about the data structure. Then, we outline ways to combine expensive human expertise with dense machine kernels to ease the human annotation burden. Finally, we will discuss our work on creating a large-scale dataset of artwork that the research community can use to explore these ideas.