Speed up inference (and ensure ergodicity) in the presence of ENSURE DEPENDENT

[axch]

by block proposing the dependent column cliques.

Apparently the current implementation strategy for ENSURE DEPENDENT is to still propose column moves one at a time, but zero out the probability of any that violate the constraints. This means that a column that is DEPENDENT on another can never change views.

• If there is only one connected component of such columns, this merely slows convergence (I think)
• If there is more than one, inference becomes non-ergodic, because the two components will get stuck either dependent or independent during initialization, and never be able to change.

The better proposal mechanism is conceptually simple: just propose moving such a collection of columns as a group. Actual implementation difficulty is unknown.

[fsaad]

Looking into this issue. Thoughts:

Adjusting the CRP probabilities

• For ENSURE DEPENDENT: the CRP probabilities associated with each view should be based on the number of constrained "column cliques" in the view, and not the raw number of columns. One can formalize this choice by considering each column clique to e a single "multivariate" column, which receives a single table assignment in the CRP prior

• or ENSURE INDEPENDENT: the CRP prior is not longer exchangeable, and bad things start to happen using the vanilla CRP probabilities, zeroing-out any tables with a customer that violates an independence constraint, and then making sure the table probabilities are normalized.

Consider the following example with three customer c1, c2, and c3 with the constraint ensure independent (c1,c2):

Scenario A: sample in the order (c1, c2, c3)

Pr[c1=1] = 1
sample -> [[c1 =1]]

Pr[c2=1 | c1] = 0 (by independence constraint)
Pr[c2=2 | c1] = 1 (probabilities are normalized)
sample --> [[c2=2]]

Pr[c3=1 | c1,c2] = 1/(2+a)
Pr[c3=2 | c1,c2] = 1/(2+a)
Pr[c3=3 | c1, c2] = a/(2+a)
sample --> [[c3=3]]

==> Implies that the probability all customers are on separate tables is a/(2+a).

Scenario B: sample in the order (c3, c1, c2)

Pr[c3=1] = 1
sample --> [[c3=1]]

Pr[c2=1 | c3] = 1/(1+a)
Pr[c2=2 | c3] = a/(1+a)
sample --> [[c2=2]]

Pr[c1=1 | c2, c3] \propto 1
Pr[c1=2 | c2, c3] = 0 (by independence constraint)
Pr[c1=3 | c2, c3] \propto a
sample --> [[c1=3]]

==> Implies the probability all customers on separate tables = a/(1+a) * a/(1+a)

Someone interested in modeling can develop a ``constrained CRP'' model which tries to formalize independence constraints, but for the time being (and due to the title of this ticket) it makes sense to worry about the ENSURE DEPENDENT case which has a straightforward resolution.

Patching the inference kernel for block proposals

The heavy lifting will happen in State.cpp.

crosscat/cpp_code/src/State.cpp

Lines 236 to 244 in 25fad43

	double State::transition_feature_gibbs(int feature_idx,
	const vector<double>& feature_data) {
	double score_delta = 0;
	View *p_singleton_view;
	score_delta += remove_feature(feature_idx, feature_data, p_singleton_view);
	View &singleton_view = *p_singleton_view;
	score_delta += sample_insert_feature(feature_idx, feature_data, singleton_view);
	return score_delta;
	}

[fsaad]

Resolved by 3873eee