Scholarly Research Excellence

Godfried T Toussaint

Publications

2

Publications

2
5928
On Speeding Up Support Vector Machines: Proximity Graphs Versus Random Sampling for Pre-Selection Condensation
Abstract:
Support vector machines (SVMs) are considered to be the best machine learning algorithms for minimizing the predictive probability of misclassification. However, their drawback is that for large data sets the computation of the optimal decision boundary is a time consuming function of the size of the training set. Hence several methods have been proposed to speed up the SVM algorithm. Here three methods used to speed up the computation of the SVM classifiers are compared experimentally using a musical genre classification problem. The simplest method pre-selects a random sample of the data before the application of the SVM algorithm. Two additional methods use proximity graphs to pre-select data that are near the decision boundary. One uses k-Nearest Neighbor graphs and the other Relative Neighborhood Graphs to accomplish the task.
Keywords:
Machine learning, data mining, support vector machines, proximity graphs, relative-neighborhood graphs, k-nearestneighbor graphs, random sampling, training data condensation.
1
7701
Characterizations of Star-Shaped, L-Convex, and Convex Polygons
Abstract:
A chord of a simple polygon P is a line segment [xy] that intersects the boundary of P only at both endpoints x and y. A chord of P is called an interior chord provided the interior of [xy] lies in the interior of P. P is weakly visible from [xy] if for every point v in P there exists a point w in [xy] such that [vw] lies in P. In this paper star-shaped, L-convex, and convex polygons are characterized in terms of weak visibility properties from internal chords and starshaped subsets of P. A new Krasnoselskii-type characterization of isothetic star-shaped polygons is also presented.
Keywords:
Convex polygons, L-convex polygons, star-shaped polygons, chords, weak visibility, discrete and computational geometry