Mind Change Efficient Learning Export

@incollection{citeulike:5923638, abstract = {This paper studies efficient learning with respect to mind changes. Our starting point is the idea that a learner that is efficient with respect to mind changes minimizes mind changes not only globally in the entire learning problem, but also locally in subproblems after receiving some evidence. Formalizing this idea leads to the notion of uniform mind change optimality. We characterize the structure of language classes that can be identified with at most α mind changes by some learner (not necessarily effective): A language class is identifiable with α mind changes iff the accumulation order of is at most α. Accumulation order is a classic concept from point-set topology. To aid the construction of learning algorithms, we show that the characteristic property of uniformly mind change optimal learners is that they output conjectures (languages) with maximal accumulation order. We illustrate the theory by describing mind change optimal learners for various problems such as identifying linear subspaces and one-variable patterns.}, author = {Luo, Wei and Schulte, Oliver}, citeulike-article-id = {5923638}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/11503415_27}, citeulike-linkout-1 = {http://www.springerlink.com/content/lwppl43dfva4ulg5}, doi = {10.1007/11503415_27}, journal = {Learning Theory}, keywords = {change, learning, mind, optimal}, pages = {398--412}, posted-at = {2009-10-12 06:08:27}, priority = {5}, title = {Mind Change Efficient Learning}, url = {http://dx.doi.org/10.1007/11503415_27}, year = {2005} }

TY - CHAP ID - citeulike:5923638 L3 - citeulike-article-id:5923638 N2 - This paper studies efficient learning with respect to mind changes. Our starting point is the idea that a learner that is efficient with respect to mind changes minimizes mind changes not only globally in the entire learning problem, but also locally in subproblems after receiving some evidence. Formalizing this idea leads to the notion of uniform mind change optimality. We characterize the structure of language classes that can be identified with at most α mind changes by some learner (not necessarily effective): A language class is identifiable with α mind changes iff the accumulation order of is at most α. Accumulation order is a classic concept from point-set topology. To aid the construction of learning algorithms, we show that the characteristic property of uniformly mind change optimal learners is that they output conjectures (languages) with maximal accumulation order. We illustrate the theory by describing mind change optimal learners for various problems such as identifying linear subspaces and one-variable patterns. JF - Learning Theory EP - 412 TI - Mind Change Efficient Learning SP - 398 KW - change KW - learning KW - mind KW - optimal AU - Luo, Wei AU - Schulte, Oliver PY - 2005/// UR - http://dx.doi.org/10.1007/11503415_27 ER -