Localization vs. identification of semi-algebraic sets

摘要

How difficult is it to find the position of a known object using random samples? We study this question, which is central to Computer Vision and Robotics, in a formal way. We compare the information complexity of two types of tasks: the task of identification, in which all the student knows is a description of a natural class to which the object belongs, and the task of localization in which he knows that the target is a transformed image of some given object. We model localization as the task of learning the class of transformed instances of the given object. We apply some fundamental results from Algebraic Geometry to bound the VC-dimension of such `transformed class' and compare it to the VC-dimension of some natural library classes to which the objects belong. We carry on the comparison to the scenario of learning under the uniform distribution, which leads us to calculating the ffl-entropy of relevant classes. Our analysis provides a mathematical ground to the intuition that Local...