Geometrical concept learning and convex polytopes

ABSTRACT

We consider exact identification of geometrical objects over the domain {0,1,…,n−1}d, d≥1 fixed. We give efficient implementations of the general incremental scheme “identify the target concept by constructing its convex hull” for learning convex concepts. This approach is of interest for intersections of half-spaces over the considered domain, as the convex hull of a concept of this type is known to have “few” vertices. In this case we obtain positive results on learning intersections of halfspaces with superset/disjointedness queries, and on learning single halfspaces with membership queries. We believe that the presented paradigm may become important for neural networks with a fixed number of discrete inputs.

REFERENCES

• 1: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 2: Martin Anthony , Graham Brightwell , Dave Cohen , John Shawe-Taylor, On exact specification by examples, Proceedings of the fifth annual workshop on Computational learning theory, p.311-318, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130420]
• 3: I. B~rlny, R. Howe and L. Lov~sz, "On Integer Points in Polyhedra: a Lower Bound", Combinatorica 12(2) (1992) 135-142.
• 4: Avrim L. Blum , Ronald L. Rivest, Training a 3-node neural network is NP-complete, Neural Networks, v.5 n.1, p.117-127, 1992 [doi>10.1016/S0893-6080(05)80010-3]
• 5: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• 6: N. H. Bshouty and R. Cleve, "On the Exact Learning of Formulas in Parallel", in: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS'9~), IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 513-522.
• 7: M. Budinich and E. Milotti, "Feed-Forward Neural Networks: a Geometrical Perspective", Journal of Physics A 24 (1991) 881-888.
• 8: William J. Bultman , Wolfgang Maass, Fast identification of geometric objects with membership queries, Proceedings of the fourth annual workshop on Computational learning theory, p.337-353, August 05-07, 1991, Santa Cruz, California, United States
• 9: Zhixiang Chen , Wolfgang Maass, On-line learning of rectangles, Proceedings of the fifth annual workshop on Computational learning theory, p.16-28, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130387]
• 10: W. Cook, M. Hartmann, R. Kannan and C. MeDiarmid, "On Integer Points in Polyhedra", Combinatorica 12(1) (1992) 27-37.
• 11: Sally A. Goldman , Michael J. Kearns, On the complexity of teaching, Proceedings of the fourth annual workshop on Computational learning theory, p.303-314, August 05-07, 1991, Santa Cruz, California, United States
• 12: Sally A. Goldman , H. David Mathias, Teaching a smart learner, Proceedings of the sixth annual conference on Computational learning theory, p.67-76, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168313]
• 13: G. Hansel, "Sur le Nombre des Fonctions Booldennes Monotones de n Variables", Comptes Rendus de l'Acaddmie des Sciences Paris 262(20) (1966) 1088-1090.
• 14: A. C. Hayes and D. G. Larman, "The Vertices of the Knapsack Polytope", Discrete Applied Mathematics 6(1983) 135-138.
• 15: Tibor Hegedűs, On training simple neural networks and small-weight neurons, Proceedings of the first European conference on Computational learning theory, p.69-82, October 1994, Royal Holloway, Univ. of London, United Kingdom
• 16: H. W. Lenstra, Jr., "Integer Programming with a Fixed Number of Variables", Mathematics of Operations Research 8 (1983) 538-548.
• 17: W. Maass, "On the Complexity of Learning on Feed- Forward Neural Nets", Lecture notes for a short course at the Advanced School on Computational Learning and Cryptography of the EATCS, Vietri sul Mare, Italy, September 1993.
• 18: W. Maass and Gy. Turin, "On the Complexity of Learning from Counterexamples", in: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS'89), IEEE Computer Society Press, Los Angeles, CA, 1989, pp. 262-267.
• 19: W. Maass and Gy. Turin, "On the Complexity of Learning from Counterexamples and Membership Queries", in: Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS'90), IEEE Computer Society Press, Washington, DC, 1990, pp. 203- 210.
• 20: W. Maass and Gy. Turin, "Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts", Report 316, IIG-Report Series, Graz University of Technology, 1991.
• 21: W. Maass and Gy. Turin, "How Fast can a Threshold Gate Learn?", Report 321, IIG-Report Series, Graz University of Technology, 1991.
• 22: Wolfgang Maass , György Turán, Lower Bound Methods and Separation Results for On-Line Learning Models, Machine Learning, v.9 n.2-3, p.107-145, July 1992 [doi>10.1007/BF00992674]
• 23: P. McMullen and G. C. Shephard, Convex Polytopes and the Upper Bound Conjecture, Cambridge University Press, Cambridge, 1971.
• 24: D. A. Morgan, "Upper and Lower Bound Results on the Convex Hull of Integer Points in Polyhedra", Mathematika 38 (1991) 321-328.
• 25: D. S. Rubin, "On the Unlimited Number of Faces in Integer Hulls of Linear Programs with a Single Constraint", Operations Research 18 (1970) 940-946.
• 26: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 27: V. N. Shevchenko, "On the Number of Extremal Points in Integer Programming", Kibernetika (2) (1981) 133-134 (in Russian).
• 28: V. N. Shevchenko, "An Algebraic Approach to Integer Programming", Kibernetika (4) (1984) 36-41 (in Russian), English translation: Cybernetics 20(4) (1984) 508- 515.
• 29: V. N. Shevchenko, "On Some Functions of Many-Vaiued Logic Connected with Integer Programming", Metody Diskretnogo Analiza 42 (1985) 99-108 (in Russian).
• 30: V. N. Shevchenko, "On Deciphering a Threshold Function of Many-Valued Logic", in: Combinatorial-Algebraic Methods and their Applications, Gorkii State University, 1987, pp. 155-163 (in Russian).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms, Performance, Theory, Verification