TR#:  CS0773 
Class:  CS 
Title:  LOCALIZATIO vs. IDENTIFICATION OF SEMIALGEBRAIC SETS. 
Authors:  S. BenDavid and M. Lindenbaum 
Not Available  
Abstract: 
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 known 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 VCdimension of such `transformed class' and compare it to the VCdimension 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 \epsilonentropy of the relevant classes. Our analysis provides a mathematical ground to the intuition that Localization is indeed much easier than Identification.

Copyright  The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information 
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgibin/trinfo.cgi/1993/CS/CS0773), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1993
To the main CS technical reports page