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

@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}, comment = {Kelly points to this theory as an alternative to SRM to explain reliable reasoning at the end of his and Mayo-Wilson's 'review':http://ndpr.nd.edu/review.cfm?id=12684 of Harman and Kulkarni's "Reliable Reasoning" book. }, doi = {10.1016/j.tcs.2007.04.009}, journal = {Theoretical Computer Science}, keywords = {efficiency, induction, ockhams\_razor, philosophy}, month = {September}, number = {2-3}, pages = {270--289}, posted-at = {2008-05-07 00:20:27}, priority = {2}, 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 TI - Ockham's razor, empirical complexity, and truth-finding efficiency T2 - Complexity of Algorithms and Computations JF - Theoretical Computer Science VL - 383 IS - 2-3 SP - 270 EP - 289 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. KW - efficiency KW - induction KW - ockhams_razor KW - philosophy N1 - Kelly points to this theory as an alternative to SRM to explain reliable reasoning at the end of his and Mayo-Wilson's 'review':http://ndpr.nd.edu/review.cfm?id=12684 of Harman and Kulkarni's "Reliable Reasoning" book. AU - Kelly, Kevin PY - 2007/09/18/ UR - http://dx.doi.org/10.1016/j.tcs.2007.04.009 ER -