Locality Sensitive Sampling (LSS) Split-Merge sampler for Bayesian nonparametric models. More...

#include <splitmerge_LSS.hpp>

Inheritance diagram for SplitMerge_LSS:

Public Member Functions
	SplitMerge_LSS (Data &d, utils_params &p, Likelihood &l, Process &pr, bool shuffle)
	Constructor for LSS (Locality Sensitive Sampling) Split-Merge sampler.
void	step () override
	Perform one iteration of the LSS Split-Merge algorithm.
int	get_accepted_split () const
	Get number of accepted split moves for diagnostics.
int	get_accepted_merge () const
	Get number of accepted merge moves for diagnostics.
int	get_accepted_shuffle () const
	Get number of accepted shuffle moves for diagnostics.
Public Member Functions inherited from Sampler
	Sampler (Data &d, const Likelihood &l, Process &pr)
	Constructor initializing sampler with required components.
virtual	~Sampler ()=default
	Virtual destructor for proper cleanup of derived classes.

Private Member Functions
void	choose_indeces (bool similarity=false)
	Randomly select two observations for split-merge proposal.
void	choose_clusters_shuffle ()
	Select clusters for shuffle move.
void	sequential_allocation (int iterations, bool only_probabilities=false, bool sequential=true)
	Generate proposal state via sequential allocation.
void	split_move ()
	Execute a split move using LSS.
double	compute_acceptance_ratio_split (double likelihood_old_cluster)
	Compute acceptance ratio for LSS split move.
void	merge_move ()
	Execute a merge move using LSS.
double	compute_acceptance_ratio_merge (double likelihood_old_clusters)
	Compute acceptance ratio for LSS merge move.
void	shuffle ()
	Execute a shuffle move using LSS.
double	compute_acceptance_ratio_shuffle (double likelihood_old_clusters, int old_ci_size, int old_cj_size)
	Compute acceptance ratio for LSS shuffle move.

Private Attributes
const utils_params &	params
std::mt19937	gen
	Mersenne Twister random number generator for sampling operations.
int	idx_i
	Index of first randomly chosen observation.
int	idx_j
	Index of second randomly chosen observation.
int	ci
	Cluster assignment of first observation.
int	cj
	Cluster assignment of second observation.
bool	shuffle_bool = false
	Flag to enable shuffle moves (Mena and Martinez, 2014).
Eigen::VectorXi	launch_state
	Launch state for sequential allocation.
Eigen::VectorXi	S
	Indices of observations in clusters ci and cj.
Eigen::VectorXi	original_allocations
	Original cluster assignments before move proposal.
double	log_split_gibbs_prob = 0
	Log probability of generating current state via sequential allocation (split direction).
double	log_merge_gibbs_prob = 0
	Log probability of generating current state via sequential allocation (merge direction).
int	accepted_split = 0
int	accepted_merge = 0
int	accepted_shuffle = 0

Additional Inherited Members
Protected Attributes inherited from Sampler
Data &	data
	Reference to the data object containing observations and current allocations.
const Likelihood &	likelihood
	Reference to the likelihood computation object for evaluating cluster assignments.
Process &	process
	Reference to the stochastic process object (DP, NGGP, DPW, NGGPW).
std::random_device	rd
	Random device for generating random numbers across sampling algorithms.

Detailed Description

Locality Sensitive Sampling (LSS) Split-Merge sampler for Bayesian nonparametric models.

This class implements the LSS Split-Merge algorithm, a variant of the split-merge sampler that uses locality sensitive sampling to select anchor points based on similarity information. LSS can be more efficient than standard split-merge for large datasets by focusing computational effort on similar observations.

Key differences from standard Split-Merge:

Locality Sensitive Sampling: Anchor points are selected based on similarity/distance
Sequential Allocation: Observations are allocated one by one in random order
Efficient Computation: Faster proposal generation leveraging data structure
Maintained Ergodicity: Preserves theoretical properties of split-merge

The algorithm maintains the same three types of moves (split, merge, shuffle) but uses locality sensitive sampling for anchor point selection and sequential allocation for generating proposals within each move type.

Note: reference Luo, C., Shrivastava, A. (2018). "Scaling-up Split-Merge MCMC with Locality Sensitive Sampling (LSS)" reference Dahl, D. B. and Newcomb, S. (2022). "Sequentially allocated merge-split samplers for conjugate Bayesian nonparametric models" reference Martinez, A. F. and Mena, R. H. (2014). "On a Nonparametric Change Point Detection Model in Markovian Regimes"; [IMPORTANT] since there is the LSS it only works with distance based models

See also: Sampler, SplitMerge

Constructor & Destructor Documentation

◆ SplitMerge_LSS()

SplitMerge_LSS::SplitMerge_LSS	(	Data &	d,
		utils_params &	p,
		Likelihood &	l,
		Process &	pr,
		bool	shuffle )

inline

Constructor for LSS (Locality Sensitive Sampling) Split-Merge sampler.

Parameters

d	Reference to Data object containing observations
p	Reference to utils_params object with hyperparameters
l	Reference to Likelihood object for probability computations
pr	Reference to Process object defining the prior
shuffle	Flag to enable shuffle moves in addition to split-merge

Initializes the LSS Split-Merge sampler, which uses locality sensitive sampling for anchor point selection and sequential allocation for generating proposals. This can provide computational advantages for large datasets.

Member Function Documentation

◆ choose_clusters_shuffle()

void SplitMerge_LSS::choose_clusters_shuffle ( )

private

Select clusters for shuffle move.

Determines cluster assignments and prepares for redistribution between two existing clusters.

Randomly choose two distinct clusters ci and cj from the current allocations. Update idx_i and idx_j to be random points from these clusters.

◆ choose_indeces()

void SplitMerge_LSS::choose_indeces ( bool similarity = false )

private

Randomly select two observations for split-merge proposal.

Uniformly samples two distinct observation indices that will determine the type of move and the clusters involved.

Parameters

similarity If true, select indices from similar clusters

Randomly choose two distinct indices i and j from the data points. Identify their clusters ci and cj. Prepare the launch_state and S vectors for the split-merge operation.

◆ compute_acceptance_ratio_merge()

double SplitMerge_LSS::compute_acceptance_ratio_merge ( double likelihood_old_clusters )

private

Compute acceptance ratio for LSS merge move.

Parameters

likelihood_old_clusters Joint likelihood of the two original clusters

Returns: Log acceptance ratio for the merge proposal

Compute the log acceptance ratio for a merge move.

Parameters

likelihood_old_clusters The joint log likelihood of clusters ci and cj before the merge.

Returns: The log acceptance ratio for the merge move.

◆ compute_acceptance_ratio_shuffle()

double SplitMerge_LSS::compute_acceptance_ratio_shuffle	(	double	likelihood_old_clusters,
		int	old_ci_size,
		int	old_cj_size )

private

Compute acceptance ratio for LSS shuffle move.

Parameters

likelihood_old_clusters	Joint likelihood of clusters before shuffle
old_ci_size	Size of first cluster before shuffle
old_cj_size	Size of second cluster before shuffle

Returns: Log acceptance ratio for the shuffle proposal

Compute the log acceptance ratio for a shuffle move.

Returns: The log acceptance ratio for the shuffle move.

◆ compute_acceptance_ratio_split()

double SplitMerge_LSS::compute_acceptance_ratio_split ( double likelihood_old_cluster )

private

Compute acceptance ratio for LSS split move.

Parameters

likelihood_old_cluster Likelihood of the original single cluster

Returns: Log acceptance ratio for the split proposal

Compute the log acceptance ratio for a split move.

Parameters

likelihood_old_cluster The log likelihood of the original cluster before the split.

Returns: The log acceptance ratio for the split move.

◆ get_accepted_merge()

int SplitMerge_LSS::get_accepted_merge ( ) const

inline

Get number of accepted merge moves for diagnostics.

Returns: Count of accepted merge moves

◆ get_accepted_shuffle()

int SplitMerge_LSS::get_accepted_shuffle ( ) const

inline

Get number of accepted shuffle moves for diagnostics.

Returns: Count of accepted shuffle moves

◆ get_accepted_split()

int SplitMerge_LSS::get_accepted_split ( ) const

inline

Get number of accepted split moves for diagnostics.

Returns: Count of accepted split moves

◆ merge_move()

void SplitMerge_LSS::merge_move ( )

private

Execute a merge move using LSS.

Attempts to merge two clusters into one using sequential allocation to determine the final unified assignment.

Propose a merge move by combining clusters ci and cj. Compute the acceptance ratio and decide whether to accept or reject the move.

◆ sequential_allocation()

void SplitMerge_LSS::sequential_allocation	(	int	iterations,
		bool	only_probabilities = false,
		bool	sequential = true )

private

Generate proposal state via sequential allocation.

Parameters

iterations	Number of allocation passes to perform
only_probabilities	If true, only compute proposal probabilities without updating state
sequential	If true, use sequential allocation; if false, use restricted Gibbs sampling

Implements the core SAMS algorithm by sequentially allocating observations to clusters. Unlike restricted Gibbs sampling, this approach processes observations one by one in random order, making allocation decisions based on current partial assignments.

Perform restricted Gibbs sampling on the points in S to propose new allocations for iter iterations.

Parameters

iterations	Number of Gibbs sampling iterations to perform.
only_probabilities	If true, only compute the probabilities without
sequential	If true, unallocate points before sampling (default true) changing allocations (used in merge move).

◆ shuffle()

void SplitMerge_LSS::shuffle ( )

private

Execute a shuffle move using LSS.

Redistributes observations between two clusters using sequential allocation while maintaining the two-cluster structure.

Perform a shuffle move to refine the allocations of points in S. This move helps to improve mixing by allowing points to switch clusters.

◆ split_move()

void SplitMerge_LSS::split_move ( )

private

Execute a split move using LSS.

Attempts to split a cluster using sequential allocation to generate the proposal state. The two anchor observations are placed in separate subclusters initially.

Propose a split move by dividing cluster ci into two clusters. Compute the acceptance ratio and decide whether to accept or reject the move.

◆ step()

void SplitMerge_LSS::step ( )

overridevirtual

Perform one iteration of the LSS Split-Merge algorithm.

Executes one step of the LSS Split-Merge sampler:

Select two observations as anchors using locality sensitive sampling
Determine move type based on their current assignments
Generate proposal using sequential allocation
Compute acceptance ratio and accept/reject the proposal

The locality sensitive sampling approach selects similar or dissimilar points based on distance information, while sequential allocation provides efficient proposal generation maintaining the theoretical properties of split-merge.

Perform a single split-merge MCMC step. Randomly choose two indices and decide whether to propose a split or merge move.

Implements Sampler.

Member Data Documentation

◆ accepted_merge

int SplitMerge_LSS::accepted_merge = 0

private

◆ accepted_shuffle

int SplitMerge_LSS::accepted_shuffle = 0

private

◆ accepted_split

int SplitMerge_LSS::accepted_split = 0

private

◆ ci

int SplitMerge_LSS::ci

private

Cluster assignment of first observation.

◆ cj

int SplitMerge_LSS::cj

private

Cluster assignment of second observation.

◆ gen

std::mt19937 SplitMerge_LSS::gen

mutableprivate

Mersenne Twister random number generator for sampling operations.

◆ idx_i

int SplitMerge_LSS::idx_i

private

Index of first randomly chosen observation.

◆ idx_j

int SplitMerge_LSS::idx_j

private

Index of second randomly chosen observation.

◆ launch_state

Eigen::VectorXi SplitMerge_LSS::launch_state

private

Launch state for sequential allocation.

◆ log_merge_gibbs_prob

double SplitMerge_LSS::log_merge_gibbs_prob = 0

private

Log probability of generating current state via sequential allocation (merge direction).

◆ log_split_gibbs_prob

double SplitMerge_LSS::log_split_gibbs_prob = 0

private

Log probability of generating current state via sequential allocation (split direction).

◆ original_allocations

Eigen::VectorXi SplitMerge_LSS::original_allocations

private

Original cluster assignments before move proposal.

◆ params

const utils_params& SplitMerge_LSS::params

private

◆ S

Eigen::VectorXi SplitMerge_LSS::S

private

Indices of observations in clusters ci and cj.

◆ shuffle_bool

bool SplitMerge_LSS::shuffle_bool = false

private

Flag to enable shuffle moves (Mena and Martinez, 2014).

The documentation for this class was generated from the following files:

BNPClust/samplers/splitmerge_LSS.hpp
BNPClust/samplers/splitmerge_LSS.cpp

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ SplitMerge_LSS()

Member Function Documentation

◆ choose_clusters_shuffle()

◆ choose_indeces()

◆ compute_acceptance_ratio_merge()

◆ compute_acceptance_ratio_shuffle()

◆ compute_acceptance_ratio_split()

◆ get_accepted_merge()

◆ get_accepted_shuffle()

◆ get_accepted_split()

◆ merge_move()

◆ sequential_allocation()

◆ shuffle()

◆ split_move()

◆ step()

Member Data Documentation

◆ accepted_merge

◆ accepted_shuffle

◆ accepted_split

◆ ci

◆ cj

◆ gen

◆ idx_i

◆ idx_j

◆ launch_state

◆ log_merge_gibbs_prob

◆ log_split_gibbs_prob

◆ original_allocations

◆ params

◆ S

◆ shuffle_bool