Minimizing the error of linear separators on linearly inseparable data

DOI10.1016/J.DAM.2012.03.009MaRDI QIDQ427883zbMATH OpenOpenAlexFDO

Authors Boris Aronov, Delia Garijo, Yurai Núñez-Rodríguez, David Rappaport, J. Urrutia, Carlos Seara

Publication date 18 June 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.03.009

zbMATH Keywords

classifierserror minimizerslinearly inseparable

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Linear separation and approximation by minimizing the sum of concave functions of distances
• Max–min separability
• Robust separation of multiple sets.
• Empirical risk minimization and problems of constructing linear classifiers
• On the Difficulty of Designing Good Classifiers

Cites work

• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
• AN OPTIMAL ALGORITHM FOR COMPUTING (≤K)-LEVELS, WITH APPLICATIONS
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• Algorithms for weak and wide separation of sets
• An improved bound for \(k\)-sets in three dimensions
• An optimal convex hull algorithm in any fixed dimension
• Applications of random sampling in computational geometry. II
• Arbitrary-norm hyperplane separation by variable neighbourhood search
• Bichromatic separability with two boxes: A general approach
• COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS
• Computing circular separability
• Computing the intersection-depth to polyhedra
• Computing the width of a set
• Improved bounds for planar \(k\)-sets and related problems
• Linear Programming in Linear Time When the Dimension Is Fixed
• Low-Dimensional Linear Programming with Violations
• Maintenance of configurations in the plane
• New applications of random sampling in computational geometry
• On k-Hulls and Related Problems
• On Approximating the Depth and Related Problems
• On a class of \(O(n^ 2)\) problems in computational geometry
• On levels in arrangements of lines, segments, planes, and triangles
• On the complexity of working set selection
• Pattern classification.
• Penetration depth of two convex polytopes in 3D
• Point sets with many \(k\)-sets
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS
• Separating objects in the plane by wedges and strips
• Taking a walk in a planar arrangement
• Time bounds for selection
• \(k\)-sets in four dimensions
• \(k\)-violation linear programming

Cited in

(10)

• Integer programming models and polyhedral study for the geodesic classification problem on graphs
• Separability of imprecise points
• Finding the largest separating rectangle among two point sets
• PAC-learning in the presence of one-sided classification~noise
• Error Localization for Erroneous Data: Continuous Data, Linear Constraints
• On the Difficulty of Designing Good Classifiers
• Nonlinear separation of data via mixed 0-1 integer and linear programming
• Separating bichromatic point sets in the plane by restricted orientation convex hulls
• Algorithms for Radon partitions with tolerance
• Regularizing conjunctive features for classification

This page was built for publication: Minimizing the error of linear separators on linearly inseparable data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q427883)