Semisupervised Semidefinite Maximum Margin Clustering
Algorithms AIMech:SemisupervisedSemidefiniteMaximumMarginClustering DRAFT
Aliases: Xu2004 Semisupervised Maximum Margin Clustering
A semisupervised binary margin-learning procedure that adds observed-label pair constraints and labeled-to-unlabeled linkage constraints to the Xu2004 semidefinite label-matrix relaxation.
Identity Notes & Concept Scope
This is the explicit Section5 observed-label extension of Xu-Neufeld-Larson-Schuurmans2004. It jointly uses labeled and unlabeled training inputs. The observed-label constraints distinguish it from the wholly unlabeled SDP; the record does not represent generic supervised SVM training or every transductive SVM solver. Its additional linear constraints define a distinct complete learning procedure; a shared margin objective does not equate these methods. 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
6 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.
Mechanism
#observed-label-constraints
For n_labeled observed binary labels, fix M_ij=y_i*y_j for every pair of labeled observations. For each unlabeled j also require sum_{i labeled} M_ij>=2-n_labeled. In an integer label matrix the latter requires each unlabeled observation to share a class with at least one labeled observation. Add these linear constraints to the same semidefinite relaxation and margin objective. In the relaxed problem they constrain correlations; they do not directly assign a discrete class to each unlabeled datum.
Limitation
#label-orientation-and-decoding
Observed label relations fix a labeled block of M, while leading-eigenvector recovery approximates M by rank one. The matrix constraints alone do not guarantee usable labeled signs in that vector: an exact six-point mixture satisfying the balance and observed-label constraints has a unique leading soft vector (0,0,1,1,-1,-1), even though the first two observed labels are opposite. For a zero input kernel this feasible M can also be an SDP optimum. Orientation by observed labels therefore needs nonzero informative recovered scores or a separate decoding policy. Inconsistent labels or balance requirements can make the constrained problem infeasible.
⚠️ 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:Clustering
Clustering
|
related_match | This procedure groups labeled and unlabeled observations jointly. The general clustering task is related without forcing a purely supervised or purely unsupervised identity. SemiSupervisedLLM is an LLM pretraining/fine-tuning model in this pin, and SupportVectorMachine is a supervised network; neither is the complete constrained transductive algorithm. No equivalence or upstream subclass is asserted. |
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-12T07:02:17Z