# Maximum entropy inference for k-means clustering

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.

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.

• I am interested in this clustering approach, can you give me some bibliography?. Thank you
– user40816
Feb 24, 2014 at 19:13
• @Mark: I'm no longer have access to academic resources, so I can't give you a bibliography, but the search term "Maximum Entropy Inference for Vector Quantization" should get you a fairly good starting point. Does that help? Feb 24, 2014 at 19:21