ICML-2003 Invited Talks

Abstract

It has been nearly two decades since the publication of Valiant's ``A Theory of the Learnable'', and 15 years since the first COLT conference. During this period, computational learning theory has matured dramatically, growing in mathematical depth and finding its natural connections to many other disciplines. The models and algorithms of the field have had widespread impact on the practice of machine learning.

This talk will be an eclectic history of the ideas, results and people of computational learning theory. I will survey the algorithms that have influenced applications, the models that have shaped the language of machine learning, and ideas that ultimately did neither but were still interesting. Connections with the simultaneous lines of thought in the practice of machine learning will be given, along with some amusing anecdotes.

Bio

Michael Kearns is a professor in the Computer and Information Science Department at the University of Pennsylvania, and the co-director of Penn's interdisciplinary Institute for Research in Cognitive Science. He also has a joint appointment in the Operations and Information Management (OPIM) department of the Wharton School.

Prof. Kearns did his undergraduate studies at the University of California at Berkeley in math and computer science, graduating in 1985. He received a Ph.D. in computer science from Harvard University in 1989; the title of his dissertation was The Computational Complexity of Machine Learning, under Prof. L.G. Valiant. Following postdoctoral positions at the Laboratory for Computer Science at M.I.T. and at the International Computer Science Institute in Berkeley, in 1991 he joined the research staff of AT&T Bell Labs.

His primary research interests are in artificial intelligence and machine learning, including computational learning theory, reinforcement learning, probabilistic inference and graphical models, and computational game theory. Prof. Kearns has worked on a variety of applications of AI to human-computer interaction, including spoken dialogue systems and software agents in MUDs. He also has interests in cryptography and network security, theoretical computer science, and computational finance.

Abstract

Applications play a variety of roles for the science of machine learning. Obviously, high-profile applications create excitement about the field, helping to attract research funding and high-caliber students.

Less obviously, applications provide important stimulus to the field and help to keep it vital and relevant. They highlight deficiencies in the state of the art and thereby steer research in new directions. I will examine a case study involving machine learning for fraud detection, and will show how this application revealed several topics requiring research attention. Applying machine learning to fraud detection reveals:

• multirelational data
• networked examples
• models that must monitor activity over time
• various kinds of costs
• unbalanced and changing class distributions.

Unfortunately, despite repeated calls for applications papers, few get submitted and almost none get published. I also will discuss why this is and what we as authors and reviewers might do about it.