Given your original description I'm not so sure if what you're doing should actually be called a nearest neighbor method. It may be more like a decision tree... This said, the curse of dimensionality is a general problem which can come up with all similarity/distance based approaches using finite datasets. IMO the biggest problem with nearest neighbour methods in particular is that, regardless of dimensionality, they will not converge to the optimal Bayes solution but instead only to a proportional classifier. This is only acceptable if you don't have overlapping classes.
Erik On 3/13/07, Peter Drake <[EMAIL PROTECTED]> wrote:
Hmmm -- p. 735 of Russell & Norvig's AI text contains a strong argument that "nearest-neighbor methods cannot be trusted for high- dimensional data". Peter Drake http://www.lclark.edu/~drake/ On Mar 7, 2007, at 9:38 PM, Peter Drake wrote: > First, a general hypothesis on heuristics: one should apply > heuristics to the first few moves beyond the fringe of the UCT > tree, and not later. It's important that these early moves be good, > but not worth the time to make later moves good. Thoughts? Is > anyone already using this idea? > > Now, a specific heuristic I'd like to try. If anyone can point out > anything horribly wrong with it before I go to the trouble to > implement it, that'd be nice. :-) > > Maintain a set of if-then rules, perhaps 1000 of them. Each rule > consists of a board configuration and a suggested move. > (Originally, they're all identically [<empty board> => E5] for > 9x9.) As the game progresses, this population of rules will change. > > When it's time to heuristically choose a move, compare the current > board configuration against the "if" part of each rule. Play the > move from the closest match (nearest neighbor). There's room for > creativity in the definition of nearness, but something like > Hamming distance might suffice. > > The population of rules is updated during the game. We might do > this, for example, whenever a move becomes the best move from its > UCT node. (Note that I'm using "best" here to mean "most likely to > win" and not "highest UCT value".) When this happens, ask the > population what it would do given this board configuration. If the > answer is the move in question, do nothing. Otherwise, overwrite > the oldest rule with a new rule suggesting this move for this > configuration. > > My hope is that this heuristic will suggest the move that has been > most effective on similar boards. > > Peter Drake > http://www.lclark.edu/~drake/ > > > > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
