Generalization and Generalizability Measures
Pages 175 - 186
Abstract
In this paper, we define the generalization problem, summarize various approaches in generalization, identify the credit assignment problem, and present the problem and some solutions in measuring generalizability. We discuss anomalies in the ordering of hypotheses in a subdomain when performance is normalized and averaged, and show conditions under which anomalies can be eliminated. To generalize performance across subdomains, we present a measure called probability of win that measures the probability whether one hypothesis is better than another. Finally, we discuss some limitations in using probabilities of win and illustrate their application in finding new parameter values for TimberWolf, a package for VLSI cell placement and routing.
References
[1]
A. Barr and E.A. Feigenbaum, The Handbook of Artificial Intelligence, vols. 1-3, William Kaufmann, Los Altos, Calif., 1981.
[2]
A.R. Barron, "Approximation and Estimation Bounds for Artificial Neural Networks," Proc. Fourth Ann. Workshop Computational Learning Theory, pp. 243-249, Morgan Kaufmann, Palo Alto, Calif., 1991.
[3]
E.B. Baum and D. Haussler, "What Size Net Gives Valid Generalization?" D.Z. Anderson, ed., Proc. Neural Information Processing Systems, pp. 81-90, American Inst. of Physics, New York, 1988.
[4]
A. Blumer A. Ehrenfeucht D. Haussler and M. Warmuth, "Classifying Learnable Geometric Concepts with the Vapnik-Chervonenkis Dimension," Proc. 18th Symp. Theory Computing, pp. 273-282, ACM, 1986.
[5]
L.B. Booker D.E. Goldberg and J.H. Holland, "Classifier Systems and Genetic Algorithms," Artificial Intelligence, vol. 40, no. 1, pp. 235-282, 1989.
[6]
Encyclopaedia Britannica CD '95, Encyclopaedia Britannica Inc., 1995.
[7]
W.W. Cohen, "Generalizing Number and Learning from Multiple Examples in Explanation Based Learning," Machine Learning, pp. 256-269, 1988.
[8]
G.F. DeJong and R.J. Mooney, "Explanation-Based Learning: An Alternative View," Machine Learning, vol. 1, no. 2, pp. 145- 176, 1986.
[9]
J.L. Devore, Probability and Statistics for Eng. and the Sciences, Brooks/Cole, Monterey, Calif., 1982.
[10]
A. Ehrenfeucht D. Haussler M. Kearns and L. Valiant, "A General Lower Bound on The Number of Examples Needed for Learning," D. Haussler and L. Pitt, eds., Proc. Workshop Computational Learning Theory, pp. 139-154, Morgan Kaufmann, Palo Alto, Calif., 1988.
[11]
J.J. Grefenstette, "Credit Assignment in Rule Discovery Systems Based on Genetic Algorithms," Machine Learning, vol. 3, nos. 2-3, pp. 225-246, Oct. 1988.
[12]
D. Haussler, "Generalizing the PAC Model: Sample Size Bounds from Metric Dimension-Based Uniform Convergence Results," Proc. 30th Ann. Symp. Foundations Computer Science, pp. 40-45. IEEE CS Press, 1989.
[13]
J.H. Holland, Adaptation in Natural and Artificial Systems. Univ. of Michigan Press, Ann Arbor, 1975.
[14]
J.H. Holland, "Properties of the Bucket Brigade Algorithm," J.J. Grefenstette, ed., Proc. Int'l Conf. Genetic Algorithms and Their Applications, pp. 1-7, Robotics Inst. of Carnegie Mellon Univ., Pittsburgh, Pa., 1985.
[15]
A. Ieumwananonthachai and B.W. Wah, "Statistical Generalization of Performance-Related Heuristics for Knowledge-Lean Applications," Int'l J. Artificial Intelligence Tools, vol. 5, nos. 1-2, pp. 61-79, June 1996.
[16]
A. Ieumwananonthachai and B.W. Wah, "Statistical Generalization of Performance-Related Heuristics for Knowledge-Lean Applications," D. Dasgupta and Z. Michalewicz, eds., Evolutionary Algorithms in Eng. Applications, pp. 293-313, Springer-Verlag, New York, 1997.
[17]
M. Kearns M. Li L. Pitt and L. Valiant, "Recent Results on Boolean Concept Learning," Machine Learning, pp. 337-352, 1987.
[18]
M. Kearns M. Li L. Pitt and L.G. Valiant, "Recent Results on Boolean Concept Learning," Proc. Fourth Int'l Workshop Machine Learning, Morgan Kaufmann, Palo Alto, Calif., 1987.
[19]
S. Kirkpatrick Jr. C.D. Gelatt and M.P. Vecchi, "Optimization By Simulated Annealing," Science, vol. 220, no. 4, 598, pp. 671-680, May 1983.
[20]
J.R. Koza, Genetic Programming, MIT Press, Cambridge, Mass., 1992.
[21]
"VLSI Layout and Synthesis Benchmarks," Proc. Int'l Workshop Layout Synthesis, 1992.
[22]
J.L. McClelland and D.E. Rumelhart, Parallel Distributed Processing: Explorations in the Microstructure of Cognition, vol. 1 on foundations, Bradford Books (MIT Press), Cambridge, Mass., 1985.
[23]
Artificial Neural Networks: Concepts and Theory, P. Mehra and B.W. Wah, eds., IEEE CSPress, Los Alamitos, Calif., 1992.
[24]
P. Mehra and B.W. Wah, "A Systematic Method for Automated Learning of Load-Balancing Strategies in Distributed Systems," Int'l J. Systems Sciences, 1997.
[25]
T.M. Mitchell, "Generalization As Search," Artificial Intelligence, vol. 18, pp. 203-226, 1982.
[26]
T.M. Mitchell R.M. Keller and S.T. Kedar-Cabelli, "Explanation-Based Generalization: A Unifying View," Machine Learning, vol. 1, no. 1, pp. 47-80, 1986.
[27]
D. Nguyen and B. Widrow, "The Truck Backer-Upper: An Example of Self-Learning in Neural Networks," Proc. Int'l Joint Conf. Neural Networks, vol. II, pp. 357-363, IEEE, 1989.
[28]
N.J. Nilsson, The Math. Foundations of Learning Machines, Morgan Kaufmann, Palo Alto, Calif., 1990.
[29]
N. Sauer, "On the Density of Families of Sets," J. Combinatorial Theory, vol. 13, pp. 145-147, 1972.
[30]
C. Sechen, VLSI Placement and Global Routing Using Simulated Annealing, Kluwer, Boston, 1988.
[31]
H.A. Simon and G. Lea, "Problem Solving and Rule Induction: A Unified View," Knowledge and Cognition, L.W. Gregg, ed., pp. 105-127, Erlbaum, Potomac, Md., 1974.
[32]
S.F. Smith, "Flexible Learning of Problem Solving Heuristics Through Adaptive Search," Proc. Int'l Joint Conf. Artificial Intelligence, pp. 422-425, Morgan Kaufmann, 1983.
[33]
R.S. Sutton, "Temporal Credit Assignment in Reinforcement Learning," PhD thesis, Univ. of Massachusetts, Amherst, Feb. 1984.
[34]
C.-C. Teng and B.W. Wah, "Automated Learning of the Minimal Configuration of A Feed Forward Neural Network," IEEE Trans. Neural Networks, vol. 7, no. 5, pp. 1,072-1,085, Sept. 1996.
[35]
L.G. Valiant, "A Theory of The Learnable," Comm. ACM, vol. 27, no. 11, pp. 1,134-1,142, Nov. 1984.
[36]
V.N. Vapnik and A.Y. Chervonenkis, "On The Uniform Convergence of Relative Frequencies of Events to Their Probabilities," Theoretical Probability and its Applications, vol. XVI, no. 2, pp. 264-280, 1971.
[37]
B.W. Wah, "Population-Based Learning: A New Method for Learning from Examples Under Resource Constraints," IEEE Trans. Knowledge and Data Eng., vol. 4, no. 5, pp. 454-474, Oct. 1992.
[38]
B.W. Wah and A. Ieumwananonthachai, "Teacher: A Genetics-Based System for Learning and for Generalizing Heuristics," X. Yao, ed., Evolutionary Computation, World Scientific, 1998.
[39]
B.W. Wah A. Ieumwananonthachai L.C. Chu and A. Aizawa, "Genetics-Based Learning of New Heuristics: Rational Scheduling of Experiments and Generalization. IEEE Trans. Knowledge and Data Eng., vol. 7, no. 5, pp. 763-785, Oct. 1995.
[40]
B.W. Wah A. Ieumwananonthachai and Y.C. Li, "Generalization of Heuristics Learned in Genetics Based Learning," S.K. Pal and P. Wang, eds., Genetic Algorithms and Pattern Recognition, pp. 87-126, CRC Press, 1996.
[41]
B.W. Wah A. Ieumwananonthachai and T. Yu, "Genetics- Based Learning and Statistical Generalization," S. Tzafestas, ed., Knowledge-Based Systems: Advanced Concepts, Tools, and Applications, pp. 319-347, World Scientific, 1997.
[42]
D.A. Waterman, "Generalization Learning Techniques for Automating the Learning of Heuristics," Artificial Intelligence, vol. 1, nos. 1-2, pp. 121-170, 1970.
Index Terms
- Generalization and Generalizability Measures
Recommendations
Statistical generalization of performance-related heuristics for knowledge-lean applications
TAI '95: Proceedings of the Seventh International Conference on Tools with Artificial IntelligenceWe present new results on the automated generalization of performance-related heuristics learned for knowledge-lean applications. We study methods to statistically generalize new heuristics learned for some small subsets of a problem space (using methods ...
Routability Optimization for Industrial Designs at Sub-14nm Process Nodes Using Machine Learning
ISPD '17: Proceedings of the 2017 ACM on International Symposium on Physical DesignDesign rule check (DRC) violations after detailed routing prevent a design from being taped out. To solve this problem, state-of-the-art commercial EDA tools global-route the design to produce a global-route congestion map; this map is used by the ...
Statistical generalization: theory and applications
ICCD '95: Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and ProcessorsIn this paper, we discuss a new approach to generalize heuristic methods (HMs) to new test cases of an application, and conditions under which such generalization is possible. Generalization is difficult when performance values of HMs are characterized ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 1999 IEEE. All Rights Reserved.
Publisher
IEEE Educational Activities Department
United States
Publication History
Published: 01 January 1999
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Dec 2024