Motivation
Ordinary competitive learning moves the prototype that best matches an arriving observation. If too few prototypes were allocated, distinct groups must share one representative. If too many were allocated, several may occupy one group. Choosing a number of prototypes before fitting is therefore already a model-selection decision, even when an algorithm describes itself only as unsupervised learning.
Rival penalized competitive learning, abbreviated RPCL, changes the adaptation rule: a winner learns from the input while a rival is moved away. The intended mechanism is to reduce redundant representation, allowing surplus prototypes to move away from well represented data. To understand this idea we must specify how competition is scored. The rival in the original frequency-sensitive rule is not necessarily the second nearest prototype in Euclidean distance.
We will analyze the local geometry exactly, then separate it from stronger statistical claims. Finally we give a fully stated, separate procedure in which adding or deleting a prototype is explicitly judged by a penalized objective. Comparing these mechanisms helps clarify what “selection during learning” can mean. A changing effective number of useful prototypes is different from an algorithm that literally deletes model parameters, and both differ from consistently estimating an unknown population structure.
Definitions
Definition 7.1.1
(Frequency-sensitive competition and the original RPCL step)
Take prototypes and positive winner counts . Let . For an input , compute scores . Select minimizing , and then minimizing over , using a fixed tie rule. With , update
leave other prototypes unchanged, and increment the winner's count. Scores and both movements use the pre-update state.
The frequency-weighted selection and opposing learning rules are verified in Section III.A, equations (3a)–(3b), of Xu, Krzyzak and Oja's 1993 original paper. The paper uses cumulative winning frequencies. Initializing every count positively and resolving ties by index are explicit implementation conventions adopted here to avoid an undefined initial ratio; they are not additional claims about the paper's experiments.
A frequently winning prototype has a larger multiplier, so it must be geometrically closer to win against an infrequent one. This is a frequency-sensitive competition rule, not a posterior probability or a mixture weight update. The prototype is still moved along an ordinary Euclidean displacement. Replacing the score by raw distance defines a related rival-penalization variant, but should not be silently substituted into this rule.
Definition 7.1.2
(Allocated and effective model size)
The allocated size is the number of stored prototypes. An effective size is defined only after an activity criterion has been specified, such as the number receiving at least a declared fraction of wins during a fixed evaluation window. A prototype far from the sample can remain allocated while contributing little to prediction. Removing it is a separate operation with consequences for later adaptation.
There is no universal activity threshold. A rare legitimate group can have few wins, and a remote prototype can occasionally win because of a low frequency multiplier. Counts accumulated over the entire history may respond slowly to a changed distribution. Windowed counts or exponential forgetting change the algorithm and require their own stated conventions. Inspecting current geometry and recent assignments alongside cumulative counts is therefore more informative than reporting a bare effective size.
Theorem/Proposition
Theorem 7.1.3
(Exact local attraction and repulsion)
For one RPCL step with winner and rival selected from the old state,
If a prototype is repeatedly the rival to the same fixed input, never wins, and has constant , its displacement from that input grows by after such steps. These are conditional trajectory statements, not assertions that the winner and rival remain the same under the actual changing competition.
Theorem 7.1.4
(Accepted structural moves for penalized distortion)
For a nonempty set of prototypes , define
Adding a candidate decreases exactly when its distortion gain
exceeds . Removing while holding other centers fixed decreases exactly when its distortion increase is smaller than . Subsequent Lloyd assignment and nonempty-cluster mean updates cannot increase .
This is a separate, explicitly penalized procedure, not a formula attributed to RPCL. Its hypotheses include squared Euclidean distortion, a fixed sample and a stated complexity penalty. A Gaussian likelihood, a streaming distribution or a different distance would require different move calculations.
Proof sketch or proof idea
Proof
(The geometry of a single rival step)
Subtract each updated prototype from . For the winner, ; for the rival, . Squaring norms proves both identities. Repeating the second linear recurrence at a fixed input gives . If the input or rival identity changes, this recurrence no longer applies.
The two movements also correspond to gradient descent on the local signed expression with the two selected indices frozen and unit step. Its negative quadratic in the rival is unbounded below. Moreover the indices and frequency weights change between inputs. Thus this observation does not provide a bounded global objective or a convergence proof for the actual learning process.
Proof X-ray
What the local proof deliberately leaves open
Attraction to the current sample and repulsion of the rival follow by exact vector algebra. Whether the repelled prototype becomes redundant, moves toward another useful group, or destabilizes a boundary depends on future inputs and competition. No statement about the correct population cluster count follows from these two norm identities. Statistical recovery needs a data-generating model and a theorem with explicit assumptions.
Proof
(Why structural acceptance tests decrease a declared objective)
Write . After adding , the new residual is , so the total distortion drops by exactly . The penalty increases by , giving . If the candidate duplicates an existing center, its gain is zero and it cannot be accepted at positive penalty.
For deletion, compare the old nearest distance with the nearest distance among remaining centers for every observation. Their nonnegative increases sum to . The penalty drops by , so the change is . Under unique old assignments only points assigned to need contribute; computing the minimum over all points also handles ties correctly. One must never delete the last prototype in this definition.
With fixed assignments, a nonempty group's sum of squared distances is minimized at its mean, by the centroid identity. With centers fixed, nearest assignments minimize every individual residual. These Lloyd steps do not raise distortion and keep the number of nonempty prototypes fixed, or reduce it if an explicitly removed empty center is counted in the penalty. Therefore any accepted structural change followed by such refitting remains a strict improvement.
One concrete learning procedure starts with a nonempty, fully refitted partition. Test birth candidates at observed data locations and deletion candidates among current centers. Accept a move only under the strict inequality above, refit with deterministic tie handling, and repeat until no tested move passes. Empty groups are removed explicitly. This is implementable without knowing a population count; its output still depends on initialization, candidate set and .
Each Lloyd refit also terminates under deterministic ties and nonempty clusters. There are finitely many sample assignments. A mean update that changes a center strictly reduces squared error for its assigned nonempty cluster. If an iteration has equal objective values, every center therefore stays fixed; deterministic reassignment then repeats the same assignment and the refit stops. This rules out a nontrivial repeated state as well as infinite strict descent among finitely many completed states.
If every completed refit assigns nonempty groups and replaces centers by their means, there are only finitely many sample partitions and hence finitely many possible completed objective values. Strict improvement between completed states rules out cycles and yields finite termination of accepted structural moves. The result is only local with respect to the tested operations. A failed fixed-center deletion test does not rule out a beneficial deletion followed by substantial reoptimization. More extensive merge or split proposals may find improvements this procedure misses.
Worked examples
Worked example 7.1.5
(One winner, one rival, and one unchanged prototype)
In one dimension take prototypes , equal positive counts and input . Weighted scores have the same ordering as squared distances , so the winner is zero and rival three. With and , the new prototypes are . The winner's distance to the input shrinks from one to , while the rival's grows from two to . If initial counts are , updated frequencies are . They will affect the next competition; they do not retroactively change this step's indices.
Worked example 7.1.6
(Frequency-sensitive competition can increase nearest-center loss)
Let , , , and frequencies . The scores are and , so prototype one wins despite being farther away. With , , the updated centers are and . Ordinary nearest-center squared error increases from one to . The winner improved its own fit, but the previously nearest prototype was repelled. Thus the k-means descent theorem cannot be transferred to this RPCL rule.
Worked example 7.1.7
(A birth justified by an explicit penalty)
For observations , begin with one center at the mean five. Distortion is . At , the penalized score is 109. Propose a center at ten. Only points nine and eleven improve, by and , so . After birth the score is . Reassigning and updating group means produces centers zero and ten, distortion four and score fourteen. Deleting center ten while holding zero fixed raises distortion by , so that fixed-center deletion is rejected. These arithmetic checks justify this fitted structure under the declared moves and penalty, without declaring that two is a universal true cluster count.
Common mistakes
Counterexample mode
A failed deletion probe is not a global certificate
Keep the last four-point sample and the fitted centers zero and ten, but use . Its score is . A fixed-center deletion raises distortion by 200, larger than the penalty saving 150, so our simple test rejects it. Yet the refitted single center five has score , which is better. The move test is exact for fixed remaining centers and sufficient for improvement after refitting; it is not necessary for every beneficial refitted merge. A stronger search could score fully refitted deletion proposals directly.
Common mistake
(Automatic selection still contains modeling choices)
RPCL's learning rates and initial allocation influence which prototypes remain useful. Penalized birth–death uses a complexity price and candidate set. An effective-size report uses an activity threshold and window. Each can automate part of a workflow, but none removes the need to state the task and tune decisions without test leakage. A distant outlier may justify another center in squared error while representing noise rather than a meaningful new population.
History of an idea
The original problem was surplus representation
Xu, Krzyzak and Oja's 1993 paper studies competitive learning when the allocated number of units is unsuitable, and introduces a smaller rival de-learning step alongside winner learning. Its discussion distinguishes spare units from units representing data. This motivates checking allocation and activity separately; it does not justify claiming a general consistency theorem for arbitrary samples.
Summary
The original frequency-sensitive RPCL step ranks both winner and rival by weighted distances, then attracts one and repels the other. Exact local formulas explain the mechanism while revealing why ordinary distortion descent is unavailable. A separate penalized birth–death procedure makes structural acceptance auditable, but even its monotone finite search yields only the optimum supported by its stated moves and choices.
Exercises
Quick check
(With input zero, prototypes one and three, and equal frequencies, perform one RPCL step with winner rate and rival rate . Verify both distance identities.)
Use the old prototypes to select the two indices.
Solution · Answer
Prototype one wins and prototype three is the rival. The new values are and . Their distances from zero are and . Squared distances equal times the old winner square one, and times the old rival square nine. The rival moves away, so a plus learning sign there would implement a different rule.
Quick check
(A prototype begins at distance two from a fixed input and is a rival for three successive steps with rate . Find its distance. State why the calculation is conditional.)
Apply the same displacement multiplier three times.
Solution · Answer
The distance is . This assumes the same fixed input, constant rate, and that this prototype is always the rival and never the winner during those three steps. Actual frequency scores and prototype geometry change, so the assumed sequence of roles must be checked rather than inferred from the recurrence.
Quick check
(For observations minus one and one with a single center zero, compute the gain from adding a center at one. Determine when a positive penalty accepts the birth.)
Only one observation obtains a shorter nearest-center distance.
Solution · Answer
Initially both residual squares are one. Adding a center at one leaves the point minus one at distance one from zero and reduces the other point's distance to zero. Thus . A strict birth is accepted exactly for , rejected for , and tied at one; our strict policy does not accept a tie. Further refitting could improve the two-center fit, illustrating again that the fixed-center test is sufficient rather than a complete search over all refitted proposals.
Quick check
(Explain the difference between allocated size, effective size, and a literal deletion. Give a concrete risk of deleting every prototype with few cumulative wins.)
Consider a small but legitimate subgroup or a changing input distribution.
Solution · Answer
Allocated size counts all stored prototypes. Effective size counts those passing a declared activity rule and can change without changing storage. Literal deletion removes parameters and alters future competition and adaptation. A rare genuine subgroup may have few cumulative wins despite a useful prototype; a recently arrived subgroup may also have little historical activity. Deleting solely from that count can erase a useful representation. Report the threshold and window and assess the resulting prediction or clustering behavior under an appropriate validation design.