# Copyright 2026 CiviqHub SAS
# SPDX-License-Identifier: Apache-2.0
"""The latent block model: co-clustering where each voter belongs to one group.
It arranges each voter in one group and each item in one block, so that the cells of a
co-cluster look alike. See :class:`LatentBlockModel` for the definition.
"""
import math
from dataclasses import dataclass
from typing import Any, final
import numpy as np
from civiqhub_selene.blocks._arrays import FloatArray, IntArray
from civiqhub_selene.blocks._numerics import History, count_states, logsumexp
from civiqhub_selene.blocks.base import BlockModel
from civiqhub_selene.blocks.data import VoteMatrix
from civiqhub_selene.blocks.results import SingleCoclustering
__all__ = ["LatentBlockModel"]
_MIN_SHARE = 1e-300
@dataclass(frozen=True, eq=False)
class _HardState:
"""One state of the algorithm: an arrangement, its shares and its parameters.
Attributes:
group_index: Shape (M,): the group of each voter.
block_index: Shape (P,): the block of each item.
group_shares: Shape (Q,): the share of voters in each group.
block_shares: Shape (L,): the share of items in each block.
parameters: The parameters of the response model.
objective: The classified log-likelihood of this state.
"""
group_index: IntArray
block_index: IntArray
group_shares: FloatArray
block_shares: FloatArray
parameters: Any
objective: float
def _voter_scores(
states: FloatArray, logs: FloatArray, block_index: IntArray, group_shares: FloatArray
) -> FloatArray:
"""Return the score of each voter for each group, the blocks being fixed. Shape (M, Q)."""
by_cell = np.einsum("ijs,qjs->iq", states, logs[:, block_index, :])
scores: FloatArray = by_cell + np.log(np.maximum(group_shares, _MIN_SHARE))
return scores
def _item_scores(
states: FloatArray, logs: FloatArray, group_index: IntArray, block_shares: FloatArray
) -> FloatArray:
"""Return the score of each item for each block, the groups being fixed. Shape (P, L)."""
by_cell = np.einsum("ijs,ils->jl", states, logs[group_index])
scores: FloatArray = by_cell + np.log(np.maximum(block_shares, _MIN_SHARE))
return scores
def _sweep(index: IntArray, scores: FloatArray) -> IntArray:
"""Move each element to its best cluster, in order, without emptying a cluster.
The elements whose best cluster differs from their current one are visited in
increasing order. An element moves if its current cluster has more than one member
and if the score of its best cluster is strictly larger. Sizes are updated as
elements move: the last member of a cluster never leaves it.
"""
moved: IntArray = index.copy()
sizes = np.bincount(moved, minlength=scores.shape[1])
best = scores.argmax(axis=1)
for element in np.flatnonzero(best != moved):
current, target = moved[element], best[element]
if sizes[current] > 1 and scores[element, target] > scores[element, current]:
sizes[current] -= 1
sizes[target] += 1
moved[element] = target
return moved
def _softmax(scores: FloatArray) -> FloatArray:
memberships: FloatArray = np.exp(scores - logsumexp(scores, axis=1)[:, np.newaxis])
return memberships
[docs]
@final
@dataclass(frozen=True, kw_only=True)
class LatentBlockModel(BlockModel[_HardState, SingleCoclustering]):
"""Co-clustering where each voter belongs to one group and each item to one block.
Definition. With M voters, P items, Q groups and L blocks, the voter ``i`` has a
group ``R[i]`` and the item ``j`` a block ``C[j]``. Given the arrangement, the
shown cells are independent, and the state ``s`` of the cell ``(i, j)`` (shown
without a vote, or a vote at one rank) follows the response model of its
co-cluster, with probability ``p[R[i], C[j], s]``. Groups have shares
``group_shares`` and blocks have shares ``block_shares``. A cell that is not shown
carries no information and enters nowhere.
The model is estimated by classification expectation-maximisation: it maximises
the classified log-likelihood, where ``S`` is the indicator of the state of each
shown cell::
objective = sum_ij sum_s S[i, j, s] * log p[R[i], C[j], s]
+ sum_i log group_shares[R[i]] + sum_j log block_shares[C[j]]
Each iteration updates the parameters of the response model and the shares from
the current arrangement, then moves the voters to their best group, the blocks
being fixed, then the items to their best block. No group and no block ever
empties. Several random starts are run and the one with the largest objective is
kept.
The value carries the integrated completed likelihood, which compares shapes::
integrated_likelihood = objective - complexity_penalty of the response model
- 0.5 * (Q - 1) * log(M) - 0.5 * (L - 1) * log(P)
The memberships of the value are soft readings of the final arrangement: the
scores of each voter for each group, turned into shares that sum to 1.
References: Govaert and Nadif (2003), Clustering with block mixture models,
Pattern Recognition 36(2); Biernacki, Celeux and Govaert (2000), Assessing a
mixture model for clustering with the integrated completed likelihood, IEEE
Transactions on Pattern Analysis and Machine Intelligence 22(7); Corneli,
Bouveyron and Latouche (2020) for the ordinal response model.
The settings are those of :class:`~civiqhub_selene.blocks.base.BlockModel`.
"""
name = "latent_block_model"
version = "0.1.0"
reference = "Govaert and Nadif 2003; Corneli, Bouveyron, Latouche 2020"
membership = "single"
meaning = "each voter belongs to one group"
default_criterion = "integrated_likelihood"
def _start(self, votes: VoteMatrix, rng: np.random.Generator) -> _HardState:
n_voters, n_items = votes.shape
shape = (self.n_groups, self.n_blocks)
# A permutation modulo the number of clusters leaves no cluster empty.
group_index = (rng.permutation(n_voters) % self.n_groups).astype(np.int64)
block_index = (rng.permutation(n_items) % self.n_blocks).astype(np.int64)
return _HardState(
group_index,
block_index,
np.full(self.n_groups, 1.0 / self.n_groups),
np.full(self.n_blocks, 1.0 / self.n_blocks),
self.response_model.initial_parameters(shape, votes, rng),
-math.inf,
)
def _step(self, votes: VoteMatrix, state: _HardState) -> _HardState:
states = votes._states()
n_voters, n_items = votes.shape
shape = (self.n_groups, self.n_blocks)
counts = count_states(states, state.group_index, state.block_index, shape)
parameters = self.response_model.update(counts, state.parameters)
group_shares = np.bincount(state.group_index, minlength=self.n_groups) / n_voters
block_shares = np.bincount(state.block_index, minlength=self.n_blocks) / n_items
logs = self.response_model.log_probabilities(parameters)
group_index = _sweep(
state.group_index, _voter_scores(states, logs, state.block_index, group_shares)
)
block_index = _sweep(
state.block_index, _item_scores(states, logs, group_index, block_shares)
)
objective = (
float(np.einsum("ijs,ijs->", states, logs[group_index][:, block_index, :]))
+ float(np.log(np.maximum(group_shares[group_index], _MIN_SHARE)).sum())
+ float(np.log(np.maximum(block_shares[block_index], _MIN_SHARE)).sum())
)
return _HardState(
group_index, block_index, group_shares, block_shares, parameters, objective
)
def _finish(
self, votes: VoteMatrix, state: _HardState, history: History, computation: str
) -> SingleCoclustering:
states = votes._states()
n_voters, n_items = votes.shape
shape = (self.n_groups, self.n_blocks)
logs = self.response_model.log_probabilities(state.parameters)
voter_scores = _voter_scores(states, logs, state.block_index, state.group_shares)
item_scores = _item_scores(states, logs, state.group_index, state.block_shares)
counts = count_states(states, state.group_index, state.block_index, shape)
integrated_likelihood = (
state.objective
- self.response_model.complexity_penalty(shape, votes)
- 0.5 * (self.n_groups - 1) * math.log(max(n_voters, 1))
- 0.5 * (self.n_blocks - 1) * math.log(max(n_items, 1))
)
return SingleCoclustering(
computation=computation,
voters=votes.voters,
items=votes.items,
scale=votes.scale,
group_index=state.group_index,
block_index=state.block_index,
group_memberships=_softmax(voter_scores),
block_memberships=_softmax(item_scores),
coclusters=self.response_model.to_table(state.parameters, counts, votes.scale),
objective=state.objective,
history=history,
integrated_likelihood=integrated_likelihood,
)