On exact learning monotone DNF from membership queries

Hasan Abasi, Nader H. Bshouty, Hanna Mazzawi

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

ملخص

In this paper, we study the problem of learning a monotone DNF with at most s terms of size (number of variables in each term) at most r (s term r-MDNF) from membership queries. This problem is equivalent to the problem of learning a general hypergraph using hyperedge-detecting queries, a problem motivated by applications arising in chemical reactions and genome sequencing.

We first present new lower bounds for this problem and then present deterministic and randomized adaptive algorithms with query complexities that are almost optimal. All the algorithms we present in this paper run in time linear in the query complexity and the number of variables n. In addition, all of the algorithms we present in this paper are asymptotically tight for fixed r and/or s.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAlgorithmic Learning Theory - 25th International Conference, ALT 2014, Proceedings
المحررونPeter Auer, Alexander Clark, Thomas Zeugmann, Sandra Zilles
الصفحات111-124
عدد الصفحات14
رقم المعيار الدولي للكتب (الإلكتروني)9783319116617
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2014
الحدث25th International Conference on Algorithmic Learning Theory, ALT 2014 - Bled, سلوفينيا
المدة: ٨ أكتوبر ٢٠١٤١٠ أكتوبر ٢٠١٤

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

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت8776

!!Conference

!!Conference25th International Conference on Algorithmic Learning Theory, ALT 2014
الدولة/الإقليمسلوفينيا
المدينةBled
المدة٨/١٠/١٤١٠/١٠/١٤

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “On exact learning monotone DNF from membership queries'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا