DIMACS - Graduate Student Combinatorics Seminar

Title: VC Dimension and Learning Theory

Speaker: Fengming Wang, Rutgers University

Date: Wednesday, April 7, 2010 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


Vapnik-Chervonenkis dimension (VC dimension) is an important combinatorial concept which measures the classification complexity of a set of boolean functions over any fixed domain. In this talk, we will introduces it by several interesting examples and demonstrate that this notion captures exactly the query complexity of any learning task within the PAC (Probably Approximately Correct) framework, one of the most popular models in computational learning theory.