Nate Kohl's Publications

Sorted by DateClassified by Publication TypeClassified by Research Category


Learning in Fractured Problems for Constructive Neural Network Algorithms

Learning in Fractured Problems for Constructive Neural Network Algorithms. Nate Kohl. Ph.D. Thesis, Department of Computer Sciences, University of Texas at Austin, 2009.

Download

[PDF]1.6MB  

Abstract

Evolution of neural networks, or neuroevolution, has been a successful approach to many low-level control problems such as pole balancing, vehicle control, and collision warning. However, certain types of problems --- such as those involving strategic decision-making --- have remained difficult to solve. This dissertation proposes the hypothesis that such problems are difficult because they are fractured: The correct action varies discontinuously as the agent moves from state to state. To evaluate this hypothesis, a method for measuring fracture using the concept of function variation of optimal policies is proposed. This metric is used to evaluate a popular neuroevolution algorithm, NEAT, empirically on a set of fractured problems. The results show that (1) NEAT does not usually perform well on such problems, and (2) the reason is that NEAT does not usually generate local decision regions, which would be useful in constructing a fractured decision boundary. To address this issue, two neuroevolution algorithms that model local decision regions are proposed: RBF-NEAT, which biases structural search by adding basis-function nodes, and Cascade-NEAT, which constrains structural search by constructing cascaded topologies. These algorithms are compared to NEAT on a set of fractured problems, demonstrating that this approach can improve performance significantly. A meta-level algorithm, SNAP-NEAT, is then developed to combine the strengths of NEAT, RBF-NEAT, and Cascade-NEAT. An evaluation in a set of benchmark problems shows that it is possible to achieve good performance even when it is not known a priori whether a problem is fractured or not. A final empirical comparison of these methods demonstrates that they can scale up to real-world tasks like keepaway and half-field soccer. These results shed new light on why constructive neuroevolution algorithms have difficulty in certain domains and illustrate how bias and constraint can be used to improve performance. Thus, this dissertation shows how neuroevolution can be scaled up from learning low-level control to learning strategic decision-making problems.

BibTeX Entry

@PhdThesis{kohl:thesis09,
  author = "Nate Kohl",
  title = "Learning in Fractured Problems for Constructive Neural Network Algorithms",
  school = "Department of Computer Sciences, University of Texas at Austin",
  month = "August",
  year = "2009",
  abstract = {
Evolution of neural networks, or neuroevolution, has been a successful 
approach to many low-level control problems such as pole balancing, 
vehicle control, and collision warning.  However, certain types of 
problems --- such as those involving strategic decision-making --- 
have remained difficult to solve.  This dissertation proposes the 
hypothesis that such problems are difficult because they are 
fractured: The correct action varies discontinuously as the agent 
moves from state to state. 
To evaluate this hypothesis, a method for measuring fracture using the 
concept of function variation of optimal policies is proposed.  This 
metric is used to evaluate a popular neuroevolution algorithm, NEAT, 
empirically on a set of fractured problems.  The results show that (1) 
NEAT does not usually perform well on such problems, and (2) the 
reason is that NEAT does not usually generate local decision regions, 
which would be useful in constructing a fractured decision boundary. 
To address this issue, two neuroevolution algorithms that model local 
decision regions are proposed: RBF-NEAT, which biases structural 
search by adding basis-function nodes, and Cascade-NEAT, which 
constrains structural search by constructing cascaded topologies. 
These algorithms are compared to NEAT on a set of fractured problems, 
demonstrating that this approach can improve performance 
significantly.  A meta-level algorithm, SNAP-NEAT, is then developed 
to combine the strengths of NEAT, RBF-NEAT, and Cascade-NEAT.  An 
evaluation in a set of benchmark problems shows that it is possible to 
achieve good performance even when it is not known a priori whether a 
problem is fractured or not.  A final empirical comparison of these 
methods demonstrates that they can scale up to real-world tasks like 
keepaway and half-field soccer.  These results shed new light on why 
constructive neuroevolution algorithms have difficulty in certain 
domains and illustrate how bias and constraint can be used to improve 
performance.  Thus, this dissertation shows how neuroevolution can be 
scaled up from learning low-level control to learning strategic 
decision-making problems. 
  },
  bib2html_pubtype = {Dissertation},
  bib2html_rescat = {Machine Learning}
}

Generated by bib2html.pl (written by Patrick Riley ) on Sun May 15, 2011 08:27:15