Minimizing the error of linear separators on linearly inseparable data

DOI10.1016/J.DAM.2012.03.009zbMATH Open1243.68158OpenAlexW2048831243MaRDI QIDQ427883FDOQ427883

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

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

zbMATH Keywords

classifierserror minimizerslinearly inseparable

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

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

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)