Maximum entropy inference for k-means clustering

Question

I am taking a course on Maximum Entropy Inference (MEI), where its application to k-Means was discussed. I am confused about the problem setting.

As far as I understand, our goal is to find clustering solutions $c(\cdot)$ with small expected cost $\mathbb{E}[R^{km}(c)] \le R_{max}$. We are therefore interested in sampling from a distribution $p^*(c)$ over these solutions where good solutions have high probability and bad solutions have low probability. In order to be as 'agnostic' as possible, we ask for the distribution which maximizes the entropy, and we thus get:

$$ p^*(c) = \arg \max_{p(c)} {H(c)} \quad \text{ s.t. } \mathbb{E}_p[R^{km}(c)] \le R_{max} $$

Obviously, $c(\cdot)$ are random variables in this scenario. But what is the underlying proability space? If $p^*(c')$ is large, it tells that $c$ is a good clustering solution, but... for what problem? Is this for a specific dataset $\mathcal{X}$ or for a large variety of such datasets? In either case, where does this or do these datasets play into the above equations?

EDIT: I hope I am not being too vague here. Unfortunately I can't express myself very clearly as I don't understand the topic that well. However, I might be able to answer specific questions less ambiguously.

Answer 1

I think I figured it out:

If $p^*(c')$ is large, it tells that $c$ is a good clustering solution, but... for what problem? Is this for a specific dataset $\mathcal{X}$ or for a large variety of such datasets?

It is a good solution with respect to a specific dataset $\mathcal{X}$. The smaller we make $R_{max}$, the less solutions are acceptable. Eventually, only the empirical risk minimizers $c^{\bot} \in \arg \min_c \mathcal{R}(c)$ are contained in the set.

Where does this or do these datasets play into the above equations?

The term $\mathcal{R}(c)$ in the constraint stands for the empirical risk with respect to the fixed $\mathcal{X}$. The expectation is taken with respect to the distribution $p(x)$ and not with respect to some distribution over data.