Feature discovery for problem solving systems

Since Samuel's work on checkers over thirty years ago, much effort has been devoted to learning evaluation functions automatically from examples. Many methods have been developed that, given examples of problem states paired with their desired evaluations, can induce an evaluation function from them. However, all such methods are sensitive to the set of features chosen to represent the examples. If the features do not capture those aspects of the examples that are significant for problem solving, the learned evaluation function may be inaccurate or inconsistent. Typically, good feature sets are handcrafted carefully, and a great deal of time and effort goes into refining and tuning them. Very little work has been done on automatically generating sets of features for problem solving domains, or on explaining why known features are useful. This dissertation presents a method for generating features for problem solving domains. It employs both a declarative problem specification and examples of state evaluations, and so combines aspects of both analytical and empirical learning. The feature set is developed iteratively: features are generated, then evaluated, and this information is used to develop new features in turn. Both the contribution of a feature and its computational expense are considered in determining whether and how to develop it further. This method has been applied to two problem solving domains: the Othello board game and the real-world domain of telecommunications network management. Empirical results show that the method is able to generate many known features, several novel features, and to improve concept accuracy in both domains.