Booth Id:
ROBO010
Category:
Year:
2016
Finalist Names:
Litt, Michael
Abstract:
This project develops a new machine learning algorithm based on computational geometry. The algorithm is able to sort and classify multi-valued inputs, and return a determination of whether or not the input vector belongs to the given set. It achieves this by identifying regions in the multidimensional input space in which the condition is known to be true, eliminating regions where it is not. It uses a supervised learning approach, in which it is trained on a set of true and a set of false data. The algorithm builds a series of convex hulls around the true data, avoiding the false data. Multiple discrete sets with complex, non-convex shapes can be modeled in this way. Once the set is modeled, the input is checked to determine membership. Convex hulls are used to model the set because of the relative ease with which they can be decomposed into volumes that the input vector can be checked against. Connected or partially overlapping convex hulls enable the creation of non-convex shapes from convex ones. The algorithm does not require linear separability between the positive and negative result, which makes it superior to linear classifiers such as the perceptron. This discriminator provides a crisp result, but multiple classifiers of this type can be combined to determine varying likelihood of membership.