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 of an unknown object from labeled examples input, and the task of localization in which the identity of the target is known and its location in some background scene has to be determined.
We carry out the comparison of these tasks using two measuring rods for the complexity of classes of sets; The Vapnik-Chervonenkis dimension and the ∈-entropy of relevant classes. The VC-dimension analysis yields bounds on the sample complexity of performing these tasks in the PAC-learning scenario whereas the ∈-entropy parameter reflects the complexity of the relevant learning tasks when the examples are generated by the uniform distribution (over the background scene). Our analysis provides a mathematical ground to the intuition that localization is indeed much easier than identification.
Our upper-bounds on the hardness of localization are established by applying a new, algebraic-geometry based, general tool for the calculation of the VC-dimension of classes of algebraically defined objects. This technique was independently discovered by Goldberg and Jerrum. We believe that our techniques will prove useful for further VC-dimension estimation problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ben-David, S., & Lindenbaum, M. (1993). Localization vs. identification of semi-algebraic sets. Proc. of COLT93 (pp. 327–336). ACM Press.
Benedek, G.M., & Itai, A. (1988). Learnability by fixed distributions. Proc. of COLT88 (pp. 80–90). Theoretical Computer Science (to appear).
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M.K. (1989). Learnability and the Vapnik-Chervonenkis dimension. JACM, 36(4), 929–965.
Cover, T.M. (1965). Geometrical and statistical properties of systems of linear equations with applications in pattern recognition. IEEE Trans. Electron. Comput., 326–334.
Dudley, R.M. (1984). A course on empirical processes. Lecture Notes in Mathematics, 1097, 2–142.
Goldberg, P.W. (1992). PAC-learning geometrical figures, Ph.D. thesis, Department of Computer Science, University of Edinburgh, UK.
Goldberg, P., & Jerrum, M. (1995). Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning, 18, 131–148.
Keren, D., Cooper, D., & Subrahmonia, J. (1992). Describing complicated objects by implicit polynomials. IEEE Transaction on Patt. Anal. Mach. Intell. (accepted for publication).
Kolmogorov, A.N., & Tichomirov, V.M. (1961). ∈-entropy and ∈-capacity of sets in functional spaces. Amer. Amth. Soc. Translations (Ser. 2), 17, 277–364.
Lindenbaum, M. (1995). Bounds on shape recognition performance. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-17(7), 666–680.
Milnor, J. (1964). On the Betti numbers of real varieties. Proc. Amer. Math. Soc., 15, 275–280.
Pach, J., & Woeginger, G. (1990). Some new bounds on ∈-nets. Proc. 6th Int. Symp. on Comp. Geometry (pp. 10–15).
Sauer, N. (1972). On the density of family of sets. Journal of Combinatorial Theory (Series A), 13, 145–147.
Terzopoulos, D., Platt, J., Barr., & Fleischer, K. (1987). Elastically deformable models. ACM Computer Graphics, 21, 205–214.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ben-David, S., Lindenbaum, M. Localization vs. Identification of Semi-Algebraic Sets. Machine Learning 32, 207–224 (1998). https://doi.org/10.1023/A:1007447530834
Issue Date:
DOI: https://doi.org/10.1023/A:1007447530834