Physical Sciences and Mathematics Commons^™

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 …