ICML-98 Submission #154

	Classification Using $\Phi$-Machines and Constructive
	Function Approximation

	Doina Precup 
	Paul E. Utgoff

	Department of Computer Science
	Lederle Graduate Research Center
	University of Massachusetts
	Amherst, MA 01003-4610

ABSTRACT

The classification algorithm CLEF combines a version of a linear
machine known as a $\Phi$-machine with a non-linear function
approximator that constructs its own features. The algorithm finds
non-linear decision boundaries by constructing features that are
needed to learn the necessary discriminant functions. The CLEF
algorithm is proven to separate all consistently labelled training
instances, even when they are not linearly separable in the input
variables. The algorithm is illustrated on a variety of tasks, showing
a significant improvement over C4.5, a state-of-art decision tree
learning algorithm.

KEYWORDS: Classification, constructive induction, linear
	machine, $\Phi$-machine, non-linear discrimination

E-MAIL:	dprecup@cs.umass.edu

PHONE:	413-545-1596 
FAX:	413-545-1249