Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
On The Impact Of Forgetting On Learning Machines, Rūsiņš Freivalds, Efim Kinber, Carl H. Smith
On The Impact Of Forgetting On Learning Machines, Rūsiņš Freivalds, Efim Kinber, Carl H. Smith
School of Computer Science & Engineering Faculty Publications
People tend not to have perfect memories when it comes to learning, or to anything else for that matter. Most formal studies of learning, however, assume a perfect memory. Some approaches have restricted the number of items that could be retained. We introduce a complexity theoretic accounting of memory utilization by learning machines. In our new model, memory is measured in bits as a function of the size of the input. There is a hierarchy of learnability based on increasing memory allotment. The lower bound results are proved using an unusual combination of pumping and mutual recursion theorem arguments. For …
Frequency Computation And Bounded Queries (Conference Paper), William I. Gasarch, Efim Kinber
Frequency Computation And Bounded Queries (Conference Paper), William I. Gasarch, Efim Kinber
School of Computer Science & Engineering Faculty Publications
There have been several papers over the last ten years that consider the number of queries needed to compute a function as a measure of its complexity. The following function has been studied extensively in that light: FaA(x1, …, xa)=A(x1)···A(xa). We are interested in the complexity (in terms of the number of queries) of approximating FaA. Let b⩽a and let f be any function such that FaA(x1, …, x a) and f(x1, …, xa) agree on at least b bits. For a general set A we have matching upper and lower bounds that depend on coding theory. These are applied …
Learning Via Queries With Teams And Anomalies, William I. Gasarch, Efim Kinber, Mark G. Pleszkoch, Carl H. Smith, Thomas Zeugmann
Learning Via Queries With Teams And Anomalies, William I. Gasarch, Efim Kinber, Mark G. Pleszkoch, Carl H. Smith, Thomas Zeugmann
School of Computer Science & Engineering Faculty Publications
Most work in the field of inductive inference regards the learning machine to be a passive recipient of data. In a prior paper the passive approach was compared to an active form of learning where the machine is allowed to ask questions. In this paper we continue the study of machines that ask questions by comparing such machines to teams of passive machines. This yields, via work of Pitt and Smith, a comparison of active learning with probabilistic learning. Also considered are query inference machines that learn an approximation of what is desired. The approximation differs from the desired result …