Convex polyhedron learning and its applications
G. Takács · 2009
From a possible engineer’s point of view learning can be considered as discovering the relationship between the features of a phenomenon. Machine learning (data mining) is a variant of learning, in which the observations about the phenomenon are available as data, and the connection between the features is discovered by a program. In the case of classification the phenomenon is modeled by a random pair (X, Y ), where the d-dimensional continuous X is called input, and the discrete (often binary) Y is called label. In the case of collaborative filtering the phenomenon is modeled by a random triplet (U, I,R), where the discrete U is called user identifier, the discrete I is called item identifier, and the continuous R is called rating value. Unbalanced problems i.e. in which one class label occurs much more frequently than the other form an interesting subset among binary classification problems. In practice such problems often arise for example in the field of medical and technical diagnostics. A convex polyhedron classifier is a function g : R 7→ {+1,−1} with the property that the decision region {x ∈ R : g(x) = 1} is a convex polyhedron. At classifying an input x ∈ R, we have to substitute x into the linear functions defining the polyhedron. If any of the substitutions gives a negative number, then we can stop the computation immediately, since the class label will be necessarily −1 in this case. As a consequence, convex polyhedron classifiers fit well to unbalanced problems. The convex polyhedron based approach has its analogous variant for collaborative filtering too. In this case the utility of the approach is that it gives a unique solution of the problem that can be a useful component of a blended solution involving many different models. A related problem to classification is determining the convex separability of point sets. Let us assume that P and Q are finite sets in R. The task is to decide whether there exist a convex polyhedron S that contains all element of P, but no elements from Q. In a practical data mining project typically many experiments are run and many models are built. It is non-trivial to decide which of them should be used for prediction in the final system. Obviously, if two models achieve the same accuracy on the training set, then it is reasonable to choose the simpler one. The Vapnik–Chervonenkis dimension is a widely accepted model complexity measure in the case of binary classification. The first chapter of the thesis (Introduction) briefly introduces the field of machine learning and locates convex polyhedron learning in it. Then, without completeness it overviews a set known learning algorithms. The part dealing with collaborative filtering contains novel results too. The second chapter of the thesis (Algorithms) is about algorithms that use convex polyhedrons for solving various machine learning problems. The first part of the chapter deals with the problem of linear and convex separation. The second part of the chapter gives algorithms for training convex polyhedron classifiers. The third part of the chapter introduces a convex polyhedron based algorithm for collaborative filtering. The third chapter of the thesis (Model complexity) collects the known facts about the Vapnik– Chervonenkis dimension of convex polyhedron classifiers and proves new results. The fourth chapter (Applications) presents the experiments performed with the proposed algorithms.