Semidefinite Maximum Margin Clustering
Algorithms AIMech:SemidefiniteMaximumMarginClustering DRAFT
Aliases: Xu2004 Maximum Margin Clustering
A binary clustering procedure that relaxes latent label-equivalence matrices to a convex semidefinite program for a fixed-kernel soft-margin objective and recovers soft assignments from the leading matrix eigenvector.
Identity Notes & Concept Scope
This is the Xu-Neufeld-Larson-Schuurmans2004 unlabeled semidefinite procedure, not every method called maximum-margin clustering. Its label matrix and convex relaxation differ from direct nonconvex cutting-plane fits, multiple-kernel weight learning, kernel k-means and the same paper variant with observed-label constraints. The general MMC acronym is therefore not a unique alias. Compared all 442 pinned AIO IDs, labels and scoped synonyms with all 498 prior native IDs, names and aliases; no normalized identity collision. Full searches of both checkouts include ignored and hidden files, returning 57 worktree and 57 main matched lines. All 41 distinct matched texts were inspected as multiple-kernel neighbors, bibliographic/query/frontier references or their rendered copies. Fifteen annotated AIO nodes and outgoing edges, fifteen generated YAMLs and six native neighbors were examined. Thirteen annotated targets, their generated records, all 442 class labels and 152 semantic rows reuse byte-verified prior readings; two additional annotated targets and one new semantic row were read (153 rows total). Absence is bounded to this pin and corpus.
Claims & Grounded Evidence
4 Claims
Mechanism
#label-matrix-relaxation
For N observations with fixed PSD kernel matrix K, the hard binary label matrix is M=y*y^T with y_i in {-1,+1}. Replace its integer entries by a symmetric PSD matrix with diagonal 1 and entries in [-1,1], retaining m_ik>=m_ij+m_jk-1 and m_jk>=-m_ij-m_ik-1 for every triple, and |sum_i m_ij|<=ell for every column. The first two linear families preserve constraints satisfied by binary equivalence relations; PSD and these constraints do not force rank one after relaxation. In the integer case the column bound equals a bound on the difference in class counts; ell<N excludes assigning everything to one class, subject to feasibility.
Mechanism
#semidefinite-margin-objective
Minimize over the feasible label matrix M the convex objective max_{0<=lambda_i<=C} [2*sum_i lambda_i-lambda^T*(K elementwise M)*lambda], with C>0. The paper equivalent SDP minimizes delta over M, delta and nonnegative mu,nu, requiring the block matrix with upper-left K elementwise M, off-diagonal 1+mu-nu and bottom-right delta-2*C*sum_i nu_i to be PSD. This optimizes a relaxation for a fixed input kernel; it does not learn a combination of input kernels. The derivation fixes the classifier intercept to zero, which centering does not make identical to freely optimizing an intercept.
Limitation
#spectral-recovery-boundary
The stated recovery is the soft vector sqrt(lambda_max(M))*v_max(M), not necessarily a binary partition or probabilities. A global SDP solution need not solve the discrete clustering problem. The source mentions randomized rounding without specifying a complete rounding policy or balance certificate. A feasible convex mixture of three balanced six-point label matrices can have a unique leading eigenvector whose signs split the data 4-to-2 despite zero column sums. These matrix constraints therefore do not alone guarantee count balance after sign rounding. Eigenvector sign, zero entries and repeated top eigenvalues require conventions.
Limitation
#soft-margin-normalization
The record uses the displayed dual and SDP convention. The printed Equation3 norm-squared primal has slack coefficient C, but its displayed dual bound lambda<=C corresponds to slack coefficient 2*C under alpha=2*lambda. With two zero-feature observations of opposite labels and C=1, the displayed primal optimum is 2 while the printed dual optimum is 4. Thus those displays should not be treated as numerically identical with the same C. A soft-margin regularized objective with nonzero slacks is also not simply the reciprocal squared geometric margin.
⚠️ Curated Limitations & Negative Results
- The method targets binary clustering with a supplied PSD kernel, penalty and feasible balance constraints, and fixes the classifier intercept to zero. The continuous matrix problem is convex; its rounded discrete output has no asserted global-optimality or approximation guarantee.
- The formulation maintains an N-by-N label matrix and constraints indexed by triples, in addition to conic constraints. Kernel construction, solver tolerances and recovery policies affect cost and results. No unconditional linear-time or large-scale efficiency claim is made.
- All eight source pages, figures and tables were read. The clustering experiments use selected RBF widths, C=100 and majority labels per cluster. The semisupervised experiments are transductive: unlabeled input points participate in fitting while their labels are withheld. The finite comparisons do not establish universal superiority or inductive generalization. No historical code, benchmark or model training was executed.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:UnsupervisedClustering
Unsupervised Clustering
|
related_match | The algorithm performs the inspected unlabeled clustering task through a label-matrix relaxation. This is a related task mapping, not algorithm-task equivalence or an upstream subclass. Supervised SVM, kernel layers, PCA projections and generic model terms have different scopes. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
sdp-source
|
Linli Xu, James Neufeld, Bryce Larson, Dale Schuurmans
|
primary paper
full_text
|
sha256:015d9811484d…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-12T06:54:11Z
Updated: 2026-10-12T06:54:11Z