6.6. Statistical Inference and Hierarchical Structure
Even search is performed on a tree (or graph) structure generally, the traditional search algorithms do not use the structural information, for example, in the best first search algorithm the node expansion only depends on the evaluation function of each single node. From granular computing point of view, only the finest grain-size information is used, i.e., the node evaluation functions. In statistical heuristic search, the hierarchical tree structure is used, since the search is carried through subtrees of a tree from top to down. While a subtree consists of a set of nodes and it is coarser than a single node. Therefore, SA is a multi-granular computing, since subtrees at different levels have different grain-sizes and compose a sequence of quotient spaces. So the statistical heuristic search is a perfect combination of statistical inference and hierarchically structural knowledge.
In web age, there is a huge amount of data with complex structures and strong noise. The statistical methods can handle big and noisy data effectively. While the quotient space model is a suitable model for representing complex structures. So the combination of both is in favor of processing big, noisy and complex data.
In fact, a tree corresponds to a sequence of monotonic quotient spaces. In SA search, when performing statistical inference on i-subtrees, each subtree is an equivalence class, the inference is implemented on a quotient space that composed by the subtrees, and the decision making does not depend on the single node evaluation function but the global evaluation function extracted from the whole nodes of each subtree. Due to the noise, incomplete knowledge, etc. uncertain factors, we are unable to make precise decisions generally. Statistical inference methods will ensure the decision-making reliability under a certain statistical sense.
∗ 8-Puzzle consists of eight numbered movable titles set in 
frame. One cell of the frame is always empty thus making it possible to move an adjacent title into the empty cell. Two configurations (initial and goal) of titles are given. Find an appropriate sequence of moves for changing the initial configuration into the goal configuration. The number of moves needed to reach the goal configuration is just the computational cost.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.