A theory for memory-based learning

ABSTRACT

A memory-based learning system is an extended memory management system that decomposes the input space either statically or dynamically into subregions for the purpose of storing and retrieving functional information. The main generalization techniques employed by memory-based learning systems are the nearest-neighbor search, space decomposition techniques, and clustering. Research on memory-based learning is still in its early stage. In particular, there are very few rigorous theoretical results regarding memory requirement, sample size, expected performance, and computational complexity. In this paper, we propose a model for memory-based learning and use it to analyze several methods— &egr;-covering, hashing, clustering, tree-structured clustering, and receptive-fields— for learning smooth functions. The sample size and system complexity are derived for each method. Our model is built upon the generalized PAC learning model of Haussler and is closely related to the method of vector quantization in data compression. Our main result is that we can build memory-based learning systems using new clustering algorithms [LiVb] to PAC-learn in polynomial time using only polynomial storage in typical situations.

REFERENCES

• Alba: James Sacra Albus, Brains, Behavior and Robotics, McGraw-Hill, Inc., New York, NY, 1981
• Albb: J. S. Albus, "A New Approach to Manipulator Control: The Cerebellar Model Articulation Controller (CMAC)," Journal of Dynamic Systems, Measurement, and Control(September 1975), 220-227.
• Albc: J. S. Albus, "Data Storage in the Cerebellar Model Articulation Controller (CMAC)," Journal of Dynamic Systems, Measurement, and Control (September 1975), 228-233.
• CAW: J. L. Carter and M. N. Wegman, "Universal Classes of Hash Functions," Journal of Computer System and Science 18 (April 1979), 143- 154.
• Chv: V. Chv~tal, "A Greedy Heuristic for the Set- Covering Problem," Mathematics of Operations Research 4(1979), 233-235.
• Dan: G. Dantzig, "Programming of Interdependent Activities, II, Mathematical Models," in Activity Analysis of Production and Allocation, John Wiley &; Sons, Inc, New York, 1951, 19-32.
• DeW: Thomas L. Dean , Michael P. Wellman, Planning and control, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• Dev: Luc Devroye, Automatic Pattern Recognition: A Study of the Probability of Error, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.4, p.530-543, July 1988 [doi>10.1109/34.3915]
• Duda: R. M. Dudley, "Central Limit Theorems for Empirical Measures," Annals of Probability 6 (1978), 899-929.
• Dudb: R. M. Dudley, "A Course on Empirical Processes,'' in Lecture Note in Mathematics 1097, 1984.
• Fri: J. H. Friedman, Multivariate Adaptive Regression Splines, Technical Report 102, Standford University, Lab for Computational Statistics, 1988.
• GaJ: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• Ger: A. Gersho, "On the Structure of Vector Quantizers," IEEE Transactions on Information Theory 28 (March 1982), 157-166.
• GeG: Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
• Gra: R. M. Gray, "Vector Quantization," IEEE ASSP Magazine (April 1984), 4-29.
• Haua: D. Haussler, "Generalizing the PAC Model: Sample Size Bounds from Metric Dimension- Based Uniform Convergence Results," in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, 40-45.
• Haub: D. Haussler, "Decision Theoretic Generalizations of the PAC Model for Neural Nets and Other Learning Applications," UCSC-CRL-89- 30, September 1989 (Revised December 1990, revised again January 1992).
• HKL: David Haussler , Michael Kearns , Nick Littlestone , Manfred K. Warmuth, Equivalence of models for polynomial learnability, Proceedings of the first annual workshop on Computational learning theory, p.42-55, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• HAL: David Haussler , Phil Long, A GENERALIZATION OF SAUER''S LEMMA, University of California at Santa Cruz, Santa Cruz, CA, 1990
• Joh: D. S. Johnson, "Approximation Algorithms for Combinatorial Problems," Journal of Computer and System Sciences 9 (1974), 256-278.
• KaH: O. Kariv and S. L. Hakimi, "An Algorithmic Approach to Network Location Problems. II: The p-Medians," SIAM Journal on Applied Mathematics (1979), 539-560.
• Kar: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• Kha: L. G. Khachiyan, "A Polynomial Algorithm in Linear Programming," Soviet Math. Doklady 20 (1979), 191-194.
• LiVa: J.-H. Lin and J. S. Vitter, "Nearly Optimal Vector Quantization via Linear Programming," in Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, March 1992, 22- 31.
• LiVb: Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
• Lov: L. Lov~sz, "On the Ratio of Optimal Integral and Fractional Covers," Discrete Mathematics 13 (1975), a83-390.
• MeS: N. Megiddo and K. J. Supowit, "On the Complexity of Some Common Geometric Location Problems," SIAM Journal on Computing 13 (1984), 182-196.
• Mil: W. T. Miller, "Sensor-Based Control of Robotic Manipulators Using a General Learning Algorithms," IEEE Journal of Robotics and Automation 3 (April 1987), 157-165.
• MGK: Thomas W. Miller, III , Filson H. Glanz , L. Gordon Kraft, III, Application of a general learning algorithm to the control of robotic manipulators, International Journal of Robotics Research, v.6 n.2, p.84-98, Summer 1987 [doi>10.1177/027836498700600207]
• Moo: John Moody, “Fast learning in multi-resolution hierarchies”, Advances in neural information processing systems 1, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• MoD: J. Moody and C. Darken, "Learning with Localized Receptive Fields," in Proceedings of the 1988 Connectionist Models Summer School, Morgan Kaufmann Publisher , 1988, 133-143.
• Mor: A. W. Moore, Acquisition of Dynamic Control Knowledge for Robotic Manipulator, Manuscript, 1989.
• Pap: C. H. Papadimitriou, "Worst-case and Probabilistic Analysis of a Geometric Location Problem,'' SIAM Journal on Computing 10(1981), 542-557.
• PoGa: Tomaso Poggio , Federico Girosi, A Theory of Networks for Approximation and Learning, Massachusetts Institute of Technology, Cambridge, MA, 1989
• PoGb: Tomaso Poggio , Federico Girosi, Extensions of a Theory of Networks for Approximation and Learning: Dimensionality Reduction and Clustering, Massachusetts Institute of Technology, Cambridge, MA, 1990
• Pola: D. Pollard, Convergence of Stochastic Processes, Springer-Verlag New York Inc, 1984.
• Polb: D. Pollard, Empirical Processes: Theory and Applications, NSF-CBMS Regional Conference Series in Probability and Statistics Volume 2, 1990.
• RaA: M. V. Ramakrishna and V. Awasthi, Manuscript, December 1991.
• Ris: Eve Ann Riskin , Robert M. Gray, Variable rate vector quantization of images, 1990
• Sau: N. Sauer, "On the Density of Families of Sets," Journal of Combinatorial Theory (.4) 13 (1972), 145-147.
• Sie: A. Siegel, Coalesced Hashing is Computably Good, Manuscript, 1991.
• Vap: Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• VaC: V. N. Vapnik and A. Ya. Chervonenkis, "On the Uniform Convergence of Relative Frequencies of Events to their Probabilities," Theory of Probability and its Applications (1971), 264- 280.
• ViC: Jeffrey S. Vitter , Wen-Chin Chen, The design and analysis of coalesced hashing, Oxford University Press, Inc., New York, NY, 1987

INDEX TERMS

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

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Theory, Verification