ICML Conference 1993 Conference Paper
Decision Theoretic Subsampling for Induction on Large Databases
- Ron Musick
- Jason Catlett
- Stuart Russell 0001
Author name cluster
Ron Musick
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
3 papers
2 author rows
Possible papers
3UAI Conference 1993 Conference Paper
Minimal Assumption Distribution Propagation in Belief Networks
- Ron Musick
AAAI Conference 1992 Conference Paper
How Long Will It Take?
- Ron Musick
We present a method for approximating the expected number of steps required by a heuristic search algorithm to reach a goal from any initial state in a problem space. The method is based on a mapping from the original state space to an abstract space in which states are characterized only by a syntactic “ distance” from the nearest goal. Modeling the search algorithm as a Markov process in the abstract space yields a simple system of equations for the solution time for each state. We derive some insight into the behavior of search algorithms by examining some closed form solutions for these equations; we also show that many problem spaces have a clearly delineated “ easy zone”, inside which problems are trivial and outside which problems are impossible. The theory is borne out by experiments with both Markov and non-Markov search algorithms. Our results also bear on recent experimental data suggesting that heuristic repair algorithms can solve large constraint satisfaction problems easily, given a preprocessor that generates a sufficiently good initial state.