Similarity as tractable transformation

Abstract

According to the transformational approach to similarity, two objects are judged to be more similar the simpler the transformation of one of the object representations into the other. This approach draws inspiration from the mathematical theory of Kolmogorov complexity, but otherwise remains an informal theory to this day. In this paper we investigate several different ways in which the informal theory of transformational similarity can be understood, providing a formalization for each possible reading. We then study the computational (in)tractability of each formalization for a variety of parameter settings. Our results have both theoretical and empirical implications for transformational approaches to similarity.