Generalization of the PAC-model for learning with partial information:(Extended abstract)

Joel Ratsaby, Vitaly Maiorov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

The PAC model of learning and its extension to real valued function classes provides a well accepted theoretical framework for representing the problem of machine learning using randomly drawn examples. Quite often in practice some form of a priori partial information about the target is available in addition to randomly drawn examples. In this paper we extend the PAC model to a scenario of learning with partial information in addition to randomly drawn examples. According to this model partial information effectively reduces the complexity of the hypothesis class used to learn the target thereby reducing the sample complexity of the learning problem. This leads to a clear quantitative tradeoff between the amount of partial information and the sample complexity of the problem. The underlying framework is based on a combination of information-based complexity theory (cf. Traub et. al. [18]) and Vapnik-Chervonenkis theory. A new quantity I n,d(F) which plays an important role in determining the worth of partial information is introduced. It measures the minimal approximation error of a target in a class F by the family of all function classes of pseudo-dimension d under a given partial information which consists of any nmeasurements which may be expressed as linear operators. As an application, we consider the problem of learning a Sobolev target class. The tradeoff between the amount of partial information and the sample complexity is calculated and by obtaining fairly tight upper and lower bounds on I n,d we identify an almost optimal way of providing partial information.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفComputational Learning Theory - 3rd European Conference, EuroCOLT 1997, Proceedings
المحررونShai Ben-David
الصفحات51-65
عدد الصفحات15
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1997
منشور خارجيًانعم
الحدث3rd European Conference on Computational Learning Theory, EuroCOLT 1997 - Jerusalem, إسرائيل
المدة: ١٧ مارس ١٩٩٧١٩ مارس ١٩٩٧

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت1208
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference3rd European Conference on Computational Learning Theory, EuroCOLT 1997
الدولة/الإقليمإسرائيل
المدينةJerusalem
المدة١٧/٠٣/٩٧١٩/٠٣/٩٧

بصمة

أدرس بدقة موضوعات البحث “Generalization of the PAC-model for learning with partial information:(Extended abstract)'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا