Binary Multiple Kernel Maximum Margin Clustering
Algorithms AIMech:BinaryMultipleKernelMaximumMarginClustering DRAFT
Aliases: Two-Class Multiple Kernel Clustering
A two-class unsupervised clustering procedure that jointly fits a nonnegative multiple-kernel combination and absolute-margin classifier using cutting-plane constraints and constrained concave-convex updates.
Identity Notes & Concept Scope
This record denotes the binary Zhao-Kwok-Zhang2009 procedure with an intercept and aggregate score balancing. It differs from the same paper multiclass winner-versus-runner-up procedure, supervised multiple-kernel SVM training, fixed-kernel maximum-margin solvers and variance-minimizing multiview kernel k-means. The paper uses MKC for both variants, so that ambiguous acronym is not a unique alias. Compared all 442 pinned AIO IDs, labels and scoped synonyms with all 496 prior native IDs, names and aliases; no normalized identity collision. Full searches of both checkouts include ignored and hidden files, returning 16 worktree and 16 main matched lines. All 11 distinct matched texts were inspected as bibliographic, query or frontier references, not existing identities. Thirteen annotated AIO nodes and outgoing edges, thirteen generated YAMLs and five native neighbors were examined. Nine unchanged annotated targets, their generated records, all 442 class labels and 147 semantic rows reuse byte-verified earlier readings; four additional annotated targets and five new semantic rows were read (152 rows total). Absence is bounded to this pin and corpus.
Claims & Grounded Evidence
5 Claims
Mechanism
#kernel-weight-geometry
Given supplied PSD base kernels K_k and feature maps Phi_k, learn nonnegative weights beta_k with sum_k beta_k^2<=1, not a simplex constraint. The resulting mixed kernel is sum_k beta_k*K_k, consistently represented by concatenated sqrt(beta_k)*Phi_k blocks. The paper introductory sum of feature maps must not be read as an arbitrary vector sum that adds cross terms, especially when feature dimensions differ. Its reparameterization v_k=beta_k*w_k gives a quadratic-over-linear regularizer. At beta_k=0 the closed perspective has cost zero for v_k=0 and infinite cost otherwise. Kernel scaling affects the optimization.
Mechanism
#binary-objective
Let f_i=sum_k v_k^T*Phi_k(x_i)+b. Minimize 0.5*sum_k ||v_k||^2/beta_k+(C/n)*sum_i xi_i with |f_i|>=1-xi_i, xi_i>=0, nonnegative L2-bounded beta and |sum_i f_i|<=l. Assign labels by the sign of the fitted scores under an explicit zero-score convention. This optimizes an absolute-margin relaxation of latent-label clustering, not supervised fitting to given labels.
Mechanism
#working-set-and-inner-fit
Replace individual slacks by a shared xi with all binary masks c in {0,1}^n constrained by mean_i c_i*|f_i|>=mean_i c_i-xi. The maximal violation selects c_i=1 where |f_i|<1 and zero otherwise, giving mean_i max(0,1-|f_i|). Starting with an empty working set, alternate restricted fitting and adding this most violated constraint until its violation is at most epsilon. Within a restricted fit, freeze z_i as an absolute-value subgradient at the previous score, replace |f_i| by z_i*f_i and solve the convex perspective problem as an SOCP; repeat subject to the chosen stopping rule. For each kernel its epigraph is ||(2*v_k,t_k-beta_k)||<=t_k+beta_k.
Limitation
#balance-is-a-relaxation
The source replaces |sum_i y_i|<=l with |sum_i f_i|<=l. The latter does not guarantee the former despite nearby equivalence language: with four zero-feature observations, l=1 and b=1/4, all scores are positive and sum to 1, while all predicted labels are +1 and sum to 4. With C=1 this feasible relaxed solution has objective 3/4, whereas every count-balanced labeling has minimum objective 1. Thus the score-balanced formulation and the original hard count-balanced objective are not generally equivalent.
Limitation
#stopping-and-guarantee-boundary
The epsilon test bounds omitted constraint violation: increasing the shared slack by epsilon makes the current score solution feasible for the full mask set. It does not bound label error or distance from a global optimum. At zero scores, choosing the valid subgradient zero can make the inner problem return the same zero-scoring point, even though a small feasible bias lowers the actual hinge objective; initialization and tie conventions therefore qualify local-optimum language. The source complexity discussion treats an empirically small CCCP iteration count as constant and contains a linear beta-sum term in Equation 3.21 despite the squared beta constraint in the stated primal. No unconditional end-to-end linear-time or convergence certificate is asserted here.
⚠️ Curated Limitations & Negative Results
- The full problem is nonconvex. Solving convex second-order cone subproblems does not establish a globally optimal kernel combination, globally optimal labels or universal local-optimum behavior. Initialization, score ties, numeric tolerances and stopping conventions matter.
- Nonnegative kernel weights preserve PSD when the supplied base kernels are PSD. Feature construction, kernel choice and scaling, regularization C, balance limit l and cutting-plane tolerance epsilon remain supplied choices. No class-count balance or nonempty-cluster guarantee follows solely from aggregate score constraints.
- All twelve source pages, including experiments and references, were read. The reported comparisons use selected datasets, known class counts, chosen kernels and tuning; their per-cluster majority-label accuracy is not stated as one-to-one cluster matching. The source whole-dataset generalization evaluation includes the fitting subset. No universal performance, independent held-out guarantee, historical implementation or benchmark reproduction is asserted.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:UnsupervisedClustering
Unsupervised Clustering
|
related_match | The inspected procedure performs unlabeled clustering; the AIO target is the related task, not an equivalent algorithm identity or asserted superclass. In this pin SupportVectorMachine is scoped as a supervised classification/regression network, and BinaryClassification and MulticlassClassification inherit supervised task scope. Shared margin terminology does not establish those identities. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
mkc-source
|
Bin Zhao, James T. Kwok, Changshui Zhang
|
primary paper
full_text
|
ID: doi:10.1137/1.9781611972795.55
sha256:1d46873539fe…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-12T06:37:49Z
Updated: 2026-10-12T06:37:49Z