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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2014
אירוע25th International Conference on Algorithmic Learning Theory, ALT 2014 - Bled, סלובניה
משך הזמן: 8 אוק׳ 201410 אוק׳ 2014

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך8776

כנס

כנס25th International Conference on Algorithmic Learning Theory, ALT 2014
מדינה/אזורסלובניה
עירBled
תקופה8/10/1410/10/14

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On exact learning monotone DNF from membership queries'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי