Home / Curated / Algorithms / Core vector machine

Core vector machine

Algorithms AIMech:CoreVectorMachine DRAFT

Aliases: CVM

An approximate kernel training algorithm that reformulates supported constant-diagonal simplex quadratic programs as minimum enclosing balls and repeatedly enlarges a core subset with a violating point while reoptimizing its ball.

Identity Notes & Concept Scope This record denotes the original Tsang-Kwok-Cheung CVM procedure and its stated L2 SVM reformulation, with exhaustive and practical sampled-search distinctions. It does not conflate every SVM loss, generalized CVM, core vector regression, core vector data description or BVM. Compared all 442 pinned AIO IDs, labels and scoped synonyms with all 513 preceding native IDs, names and aliases. No normalized identity collision was found for either candidate. Whole-word fixed-string searches of both checkouts included ignored and hidden files, expanded names, CVM/BVM acronyms and primary-source identifiers. All 22 matches per checkout were inspected in 14 distinct text windows at 44 locations: prior queries and unresolved discovery notes, not existing records. All 93 semantic AIO rows and 35 native name/definition matches were read. Twelve annotated AIO CLASS nodes and outgoing edges and 17 contextual YAMLs were inspected or reused after unchanged-byte checks. This is a bounded local corpus assessment.

Claims & Grounded Evidence

8 Claims

Mechanism #constant-diagonal-reduction

For feature vectors with a positive-semidefinite kernel, the minimum-enclosing-ball dual maximizes sum_i alpha_i*K_ii-alpha^T*K*alpha over nonnegative coefficients summing to one. Its center is the feature combination defined by alpha. If K_ii is constant kappa, this differs from maximizing -alpha^T*K*alpha only by kappa. Dropping the diagonal term for a nonconstant-diagonal kernel changes the optimization. Kernel normalization additionally requires positive self-similarities and changes the feature geometry.

supports Source: Core Vector Machines: Fast SVM Training on Very Large Data Sets · Locator: Sections 2-4.1, printed pp365-372 / PDF pp3-10, Equations 1-19 and CVM iteration

Mechanism #specific-l2-svm

The binary formulation minimizes ||w||²+b²-2*rho+C*sum_i xi_i² subject to y_i*(w^T*phi(x_i)+b)>=rho-xi_i, with C>0 and labels +/-1. Its transformed kernel is Ktilde_ij=y_i*y_j*(k_ij+1)+delta_ij/C, with constant diagonal kappa+1+1/C when k_ii=kappa. The simplex dual maximizes -alpha^T*Ktilde*alpha. Recover w=sum_i alpha_i*y_i*phi(x_i), b=sum_i alpha_i*y_i and xi_i=alpha_i/C. This uses squared slack loss and penalized bias; it is not every L1-hinge or unpenalized-bias SVM. The source also derives an L2 one-class formulation, which has a different transformed kernel.

supports Source: Core Vector Machines: Fast SVM Training on Very Large Data Sets · Locator: Sections 3.2.1-3.2.2, printed pp368-370 / PDF pp6-8; binary formulation and recovery in Equations 12-17 and following transformed-feature display

Mechanism #growing-core-reoptimization

For 0<epsilon<=1, maintain a subset of transformed observations and its exact minimum enclosing ball. If any training feature lies farther than (1+epsilon) times the current radius, add a farthest such feature and recompute the subset MEB; stop only when all features satisfy the bound. Kernel expansions compute distances without explicit feature coordinates. Added core observations are not deleted, although their optimized coefficients can become zero; core membership is not identical to final support-vector membership. The practical implementation uses warm-started SMO for the inner problem.

supports Source: Core Vector Machines: Fast SVM Training on Very Large Data Sets · Locator: Sections 2-4.1, printed pp365-372 / PDF pp3-10, Equations 1-19 and CVM iteration

Limitation #radius-and-shifted-objective-guarantee

With exact subset optimization and exhaustive outside-point checking, the final core radius R satisfies R<=R_star<=(1+epsilon)*R. For the stated simplex quadratic program, the corresponding relative approximation is on the shifted objective p_star+kappa_tilde=R_star². It is not a relative guarantee on the unshifted SVM objective, classifier labels or test accuracy. Finite inner-solver and outer termination tolerances must be distinguished.

supports Source: Core Vector Machines: Fast SVM Training on Very Large Data Sets · Locator: Section 4.2, printed pp372-374 / PDF pp10-12, Equations 21-25
supports Source: Comments on the "Core Vector Machines: Fast SVM Training on Very Large Data Sets" · Locator: Section 3, printed pp295-298 / PDF pp5-8

Limitation #sampled-search-is-not-global-certification

The implementation samples 59 observations to approximate the farthest-point search and repeats probabilistic checks near termination. Under independent sampling with replacement, 59 draws hit the farthest 5 percent with probability about 0.9515, but miss a single violating observation among 1000 with probability about 0.9427. These curator calculations distinguish a rank-sampling statement from a certificate that every point is enclosed; they do not diagnose the historical random generator or reproduce the implementation.

supports Source: Core Vector Machines: Fast SVM Training on Very Large Data Sets · Locator: Section 4.1.2, printed p371 / PDF p9; Section 6 introduction and footnote 5, printed p376 / PDF p14; curator calculations in research/discovery/core-ball-vector-boundaries.py

Limitation #qualified-computational-cost

The paper derives O(n/epsilon²+1/epsilon^4) work for full farthest-point scans with its stated core-size and inner-QP cost model, treating kernel evaluations as constant cost. Its O(1/epsilon²) auxiliary QP workspace bound excludes the input dataset. Practical implementations store the input and may use caches; approximate sampling and numerical solves alter what is certified. Fixed-epsilon bounds do not establish unconditional sample-size-independent total runtime or memory.

supports Source: Core Vector Machines: Fast SVM Training on Very Large Data Sets · Locator: Section 4.3, printed pp374-375 / PDF pp12-13; Section 6 introduction, printed pp376-377 / PDF pp14-15

Limitation #historical-critique-and-disagreement

Loosli and Canu report sensitivity and reproduction difficulties for selected checkers experiments using the CVM v1.1 Linux binary downloaded in April 2006, alongside specific LIBSVM and SimpleSVM comparisons. Their analysis discusses inner and outer stopping rules and makes an equivalence assumption for part of the derivation. The authors’ reply is retained as abstract-only context: it disputes parts of the stopping analysis and attributes some behavior to historical sampling. Neither account is treated as a universal verdict on every CVM implementation, and the reply’s full derivation was unavailable here.

supports Source: Comments on the "Core Vector Machines: Fast SVM Training on Very Large Data Sets" · Locator: Sections 2-4, printed pp292-298 / PDF pp2-8, especially p297 inner-criterion assumption
context Source: Authors’ Reply to the “Comments on the Core Vector Machines: Fast SVM Training on Very Large Data Sets” · Locator: Abstract; no full reply equations or experiments inspected

Scope #identity-and-empirical-boundary

CVM is an approximate training procedure for supported kernel quadratic programs, not a synonym for generic SVM, a learned classifier instance, support-vector data description or BVM. BVM replaces repeated core MEB optimization with fixed-radius center movement and optional radius refinement. The original and critique experiments involve selected datasets, regularization, kernels, software, tolerances and hardware; no universal runtime or accuracy advantage, current implementation validation or reproduced benchmark is asserted.

supports Source: Core Vector Machines: Fast SVM Training on Very Large Data Sets · Locator: Sections 2-4.1, printed pp365-372 / PDF pp3-10, Equations 1-19 and CVM iteration
supports Source: Simpler Core Vector Machines with Enclosing Balls · Locator: Sections 2-3, printed pp912-915 / PDF pp2-5
supports Source: Core Vector Machines: Fast SVM Training on Very Large Data Sets · Locator: Section 6, printed pp376-389 / PDF pp14-27
supports Source: Comments on the "Core Vector Machines: Fast SVM Training on Very Large Data Sets" · Locator: Sections 2-4, printed pp292-300 / PDF pp2-10

⚠️ Curated Limitations & Negative Results

Kernel validity and normalization, regularization, numerical tolerances, violation-search policy and data geometry affect guarantees and costs. A geometric approximation is not a calibrated uncertainty estimate or a generalization guarantee.
All 30 CVM and eight BVM primary PDF pages were visually read; the CVM critique’s 11 pages were also read for that record. The reply remains abstract-only context and its software diagnosis was not independently verified.
Exact rational formula and boundary checks were executed. No historical binary, full optimizer, trained model or benchmark was executed. Original software access links failed; current implementation behavior is not asserted.
This maintained native record remains DRAFT, with a local related AIO mapping. Generalized solvers, data-description variants and other discovered source leads remain unresolved.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:SupportVectorMachine` Support Vector Machine	related_match	The algorithm trains a particular support-vector formulation, making AIO:SupportVectorMachine a related model-family target. The pinned target is a Network with layer relations and supervised classification/regression scope; it is not identical to this training algorithm. Related matching asserts neither equivalence nor subclassing. BinaryClassification, Classification, SupervisedLearning and UnsupervisedLearning are tasks, not the specific solver; encoding labels in a feature map does not make binary training unsupervised. KernelLayer is a component, TrainingStrategy is described as preprocessing, and DataPreparation or SelectionAndSamplingBias do not identify the procedure. Native SVDD fits a support boundary, SVC adds component labeling, kernel PCA extracts variance directions, and margin clustering infers labels. Shared kernels or enclosing spheres do not establish identity.

Evidence Sources & Primary Literature

4 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`tsang2005`	Core Vector Machines: Fast SVM Training on Very Large Data Sets Ivor W. Tsang, James T. Kwok, Pak-Ming Cheung	primary paper full_text	sha256:8ba1804ac233…
`loosli2007`	Comments on the "Core Vector Machines: Fast SVM Training on Very Large Data Sets" Gaëlle Loosli, Stéphane Canu	primary paper full_text	sha256:13b6dd2ef91f…
`tsang2007`	Simpler Core Vector Machines with Enclosing Balls Ivor W. Tsang, Andras Kocsor, James T. Kwok	primary paper full_text	sha256:3bb017075a61…
`tsang-reply-context`	Authors’ Reply to the “Comments on the Core Vector Machines: Fast SVM Training on Very Large Data Sets” Ivor W. Tsang, James T. Kwok	author technical report abstract_only

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-12T09:31:37Z

Updated: 2026-10-12T09:40:04Z

Source File: data/curated/CoreVectorMachine.yaml