Cutting Plane Multiclass Maximum Margin Clustering
Algorithms AIMech:CuttingPlaneMulticlassMaximumMarginClustering DRAFT
Aliases: CPM3C
A fixed-kernel multiclass clustering procedure that fits latent winning-class margins by adding violated aggregate constraints and repeatedly solving quadratic programs with frozen class winners.
Identity Notes & Concept Scope
This is Zhao-Wang-Zhang2008 CPM3C, with a supplied feature map or kernel and supplied class count. Its scalar beta is regularization, not learned kernel-combination weights. It differs from the later multiple-kernel procedure, the binary intercept-bearing CPMMC solver, semidefinite label-matrix relaxations and supervised structured-output training. 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
#fixed-kernel-score-objective
For supplied k classes and feature vectors x_i, use intercept-free scores g_ip=w_p^T*x_i and regularization beta>0. Fit beta/2*sum_p ||w_p||^2+mean_i xi_i with latent winner-versus-competitor margins. For a unique winner p_i and runner-up r_i, the optimal slack at fixed scores is max(0,1-(g_i,p_i-g_i,r_i)). Impose |sum_i(g_ip-g_iq)|<=ell for every class pair; these aggregate score bounds do not impose class-count balance or ensure every class is occupied. Kernel-PCA coordinates are one suggested representation of a supplied kernel, not learned multiple-kernel weights.
Mechanism
#cutting-plane-and-quadratic-fit
Aggregate slacks into a shared xi using masks c_i in {0,e_1,...,e_k}. Under a unique winner, the most violated constraint selects the runner-up one-hot vector when the top-runner gap is below 1 and the zero vector otherwise. Starting with an empty working set, fit its constraints, add the most violated mask and stop when violation is at most epsilon. Within a restricted fit, freeze previous winning-class indicators and solve the quadratic program with those indicators and the score-balance constraints; repeat under the stopping rule. The source uses a relative objective-change threshold of 0.01 percent in its experiments.
Limitation
#indicator-and-convexity-limits
The strict winner product makes every indicator zero at a tied maximum, yielding label 0 outside {1,...,k}; tie handling is not fully specified. Moreover, the source claimed convex term includes a winner-dependent indicator and need not be convex: for one observation, mask e_1 and scores (x,0), it is max(x,0)+I[x>0]. At x=-0.2 and 0.2, a 3/4 mixture gives x=0.1 with value 1.1, exceeding the convex interpolation bound 0.9. These points have unique winners. Thus convexity of the frozen-indicator QP does not justify an unconditional global constrained concave-convex convergence or monotonicity claim for the printed nonconvex procedure.
Limitation
#tolerance-and-runtime-scope
With correct constraint separation and a feasible restricted solution, the epsilon test permits feasibility for all masks after increasing the shared slack by epsilon. This does not itself bound misclassification error or the gap to a global optimum. The stated per-iteration scaling assumes a constant working-set size and supplied feature sparsity; the source iteration-count and linear-runtime theorems explicitly concern k=2, while multiclass scaling is empirical. Nonconvex restricted fitting, feature construction and stopping assumptions prevent an unconditional end-to-end linear-time or optimality guarantee.
⚠️ Curated Limitations & Negative Results
- This record describes the printed working-set and frozen-winner procedure with explicit tie and nonconvexity limits. No unmentioned tie repair, globally optimal restricted solver, global optimum or universal convergence guarantee is silently supplied.
- The class count, fixed kernel/features, regularization beta, score-balance bound and epsilon are supplied choices. Pairwise score balance is not class-count balance; the displayed formulation has no intercept.
- All eight paper pages, tables and figures were read. Experiments supply true class counts, use selected datasets and kernel tuning, and assess majority-label accuracy per cluster and Rand index. The tables include accuracy and runtime cases favoring comparators, so no universal superiority is asserted. No historical implementation or benchmark was reproduced.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:UnsupervisedClustering
Unsupervised Clustering
|
related_match | CPM3C groups unlabeled observations through latent multiclass margins, so UnsupervisedClustering is the related task. The algorithm is not an equivalent supervised multiclass classification task or supervised SVM network, and its kernel coordinates do not identify it with PCA. No upstream subclass is asserted. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
cp-source
|
Bin Zhao, Fei Wang, Changshui Zhang
|
primary paper
full_text
|
ID: doi:10.1145/1390156.1390313
sha256:db9db473e6a0…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-12T06:54:11Z
Updated: 2026-10-12T06:54:11Z