Ockham's razor, empirical complexity, and truth-finding efficiency Export

@article{citeulike:1597737, abstract = {The nature of empirical simplicity and its relationship to scientific truth are long-standing puzzles. In this paper, empirical simplicity is explicated in terms of empirical effects, which are defined in terms of the structure of the inference problem addressed. Problem instances are classified according to the number of empirical effects they present. Simple answers are satisfied by simple worlds. An efficient solution achieves the optimum worst-case cost over each complexity class with respect to such costs as the number of retractions or errors prior to convergence and elapsed time to convergence. It is shown that always choosing the simplest theory compatible with experience and hanging on to it while it remains the simplest is both necessary and sufficient for efficiency.}, author = {Kelly, Kevin T.}, booktitle = {Complexity of Algorithms and Computations}, citeulike-article-id = {1597737}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.tcs.2007.04.009}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6V1G-4NGKWGF-8/2/8416ffcc45ba2606ef99bbf9f6778bb0}, day = {18}, doi = {10.1016/j.tcs.2007.04.009}, journal = {Theoretical Computer Science}, keywords = {learning, pac-learning}, month = {September}, number = {2-3}, pages = {270--289}, posted-at = {2007-08-28 03:56:27}, priority = {5}, title = {Ockham's razor, empirical complexity, and truth-finding efficiency}, url = {http://dx.doi.org/10.1016/j.tcs.2007.04.009}, volume = {383}, year = {2007} }

TY - JOUR ID - citeulike:1597737 L3 - citeulike-article-id:1597737 N2 - The nature of empirical simplicity and its relationship to scientific truth are long-standing puzzles. In this paper, empirical simplicity is explicated in terms of empirical effects, which are defined in terms of the structure of the inference problem addressed. Problem instances are classified according to the number of empirical effects they present. Simple answers are satisfied by simple worlds. An efficient solution achieves the optimum worst-case cost over each complexity class with respect to such costs as the number of retractions or errors prior to convergence and elapsed time to convergence. It is shown that always choosing the simplest theory compatible with experience and hanging on to it while it remains the simplest is both necessary and sufficient for efficiency. IS - 2-3 JF - Theoretical Computer Science EP - 289 TI - Ockham's razor, empirical complexity, and truth-finding efficiency VL - 383 T2 - Complexity of Algorithms and Computations SP - 270 KW - learning KW - pac-learning AU - Kelly, Kevin PY - 2007/09/18/ UR - http://dx.doi.org/10.1016/j.tcs.2007.04.009 ER -