1
$\begingroup$

The alpha-expansion algorithm described here (Probabilistic Graphical Models: Principles and Techniques By Daphne Koller, Nir Friedman, Page 593: algorithm 13.5), is designed for graphs where each vertex has the same set of labels. I am interested in a more general problem where each vertex can have different set of labels having different cardinalities.

Can the alpha-expansion algorithm be used in such cases?

For example, let the graph have 3 vertices. The first vertex can assume labels (a1, a2, a3). The second vertex can assume labels (b1, b2) and the third one can have (c1, c2, c3, c4, c5). The node and edge potentials are defined accordingly. Can alpha-expansion still help me in finding an optimal (approximate) label combination?

$\endgroup$
1
$\begingroup$

For the record, and with a hope that this would help someone like me:

I solved the problem by finding union of the sets of labels for each node. I then assigned this set for every node, and assigned a high cost node potential for labels which do not belong to that node.

Now, the alpha-expansion can run on this union set.

$\endgroup$

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.