3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am interested in this clustering approach, can you give me some bibliography?. Thank you $\endgroup$ – user40816 Feb 24 '14 at 19:13
  • 1
    $\begingroup$ @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? $\endgroup$ – blubb Feb 24 '14 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.