Journée Mathematical Foundations of Learning Theory
< précédent | suivant >
|Complexity of Sign Matrices and its Many Aspects|
Nathan Linial (The Hebrew University of Jerusalem)
3 juin 2006
Consider a matrix of +1/-1 as a family of concepts to be learned. Various measures can be associated with this matrix in an attempt to quantify how hard it is to learn this concept class. Among the better known measures are the VC dimension and the margin. In joint work with Adi Shraibman we are putting these notions in a broader framework of complexity measures of sign matrices. The simplest complexity measure is the rank, and many other natural concepts arise which are related to various other fields such as Banach Space Theory, communication complexity and discrepance theory. We are investigating these different concepts and their mutual relationships.