NDLI: Learning functions represented as multiplicity automata

Content Provider	ACM Digital Library
Author	Beimel, Amos Bergadano, Francesco Bshouty, Nader H. Kushilevitz, Eyal Varricchio, Stefano
Copyright Year	2000
Abstract	We study the learnability of multiplicity automata in Angluin's exact learning model, and we investigate its applications. Our starting point is a known theorem from automata theory relating the number of states in a minimal multiplicity automaton for a function to the rank of its Hankel matrix. With this theorem in hand, we present a new simple algorithm for learning multiplicity automata with improved time and query complexity, and we prove the learnability of various concept classes. These include (among others): -The class of disjoint DNF, and more generally $satisfy-\textit{O}(1)$ DNF.-The class of polynomials over finite fields.-The class of bounded-degree polynomials over infinite fields.-The class of XOR of terms.-Certain classes of boxes in high dimensions.In addition, we obtain the best query complexity for several classes known to be learnable by other methods such as decision trees and polynomials over GF(2).While multiplicity automata are shown to be useful to prove the learnability of some subclasses of DNF formulae and various other classes, we study the limitations of this method. We prove that this method cannot be used to resolve the learnability of some other open problems such as the learnability of general DNF formulas or even $\textit{k}-term$ DNF for $\textit{k}$ = ω(log $\textit{n})$ or $satisfy-\textit{s}$ DNF formulas for $\textit{s}$ = ω(1). These results are proven by exhibiting functions in the above classes that require multiplicity automata with super-polynomial number of states.
Starting Page	506
Ending Page	530
Page Count	25
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/337244.337257
Journal	Journal of the ACM (JACM)
Volume Number	47
Issue Number	3
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2000-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	DNF Computational learning Learning disjoint Learning polynomials Multiplicity automata
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Structure and Transition-Preserving Functions of Finite Automata

Group-Type Automata

Nested Stack Automata

Halting Stack Automata

One-way stack automata

Tape Sets and Automata

Stack automata and compiling

Isomorphism Groups of Automata

Input-Error-Limiting Automata

Learning functions represented as multiplicity automata

Similar Documents

Structure and Transition-Preserving Functions of Finite Automata

Group-Type Automata

Nested Stack Automata

Halting Stack Automata

One-way stack automata

Tape Sets and Automata

Stack automata and compiling

Isomorphism Groups of Automata

Input-Error-Limiting Automata

Learning functions represented as multiplicity automata