Name
Title | ||
|---|---|---|
Bernoulli's principle of insufficient reason and conservation of information in computer search |
Abstract | ||
|---|---|---|
Conservation of information (COI) popularized by the no free lunch theorem is a great leveler of search algorithms, showing that on average no search outperforms any other. Yet in practice some searches appear to outperform others. In consequence, some have questioned the significance of COI to the performance of search algorithms. An underlying foundation of COI is Bernoulli's Principle of Insufficient Reason(PrOIR) which imposes of a uniform distribution on a search space in the absence of all prior knowledge about the search target or the search space structure. The assumption is conserved under mapping. If the probability of finding a target in a search space is p, then the problem of finding the target in any subset of the search space is p. More generally, all some-to-many mappings of a uniform search space result in a new search space where the chance of doing better than p is 50-50. Consequently the chance of doing worse is 50-50. This result can be viewed as a confirming property of COI. To properly assess the significance of the COI for search, one must completely identify the precise sources of information that affect search performance. This discussion leads to resolution of the seeming conflict between COI and the observation that some search algorithms perform well on a large class of problems. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/ICSMC.2009.5346119 | SMC'09 Proceedings of the 2009 IEEE international conference on Systems, Man and Cybernetics |
Keywords | Field | DocType |
search algorithm,search space,new search space,search performance,search space structure,search target,uniform search space result,uniform distribution,Insufficient Reason,free lunch theorem,computer search,insufficient reason | Incremental heuristic search,Search algorithm,No free lunch theorem,Computer science,Uniform distribution (continuous),Artificial intelligence,Principle of indifference,Computer search,Machine learning,Bernoulli's principle,Black hole information paradox | Conference |
ISSN | ISBN | Citations |
1062-922X | 978-1-4244-2794-9 | 0 |
PageRank | References | Authors |
0.34 | 20 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| William A. Dembski | 1 | 18 | 2.88 |
| Robert Jackson Marks | 2 | 0 | 0.68 |
| Marks, R.J., II | 3 | 165 | 46.04 |