## A few questions about DGM directed and undirected edges

Semantic Image Segmentation with Conditional Random Fields
Yu Liu

### A few questions about DGM directed and undirected edges

Hi,
I'm studying CRFs recently, and I've read some codes of implementations of general CRFs such as CRF(Java), Mallet, CRFSuite. I found DGM is best for me, which is quite clearly in coding.
During studying the DGM source codes, I come across some questions:

1. When adding/setting arcs in building a graph, why the edge potential is square rooted?
(#186 and #196 in ./modules/DGM/Graph.cpp)
2. In message passing algorithms, why the new msg is double multiplied by edge potential?
(#80 in ./modules/DGM/MessagePassing.cpp)
I tried to search for clues that may help answering the questions, but found nothing. I hope you may give me some hints, and thank you.

Creator
Posts: 154
Joined: Tue Dec 16, 2008, 20:52
Location: Hannover, Germany
Contact:

### Re: A few questions about DGM directed and undirected edges

Thank you for interest to the DGM library.

1. The arc is the undirected edge in CRFs models. The DGM library emulates every undirected arc with two opposite-directed directed edges. Thus A -- B is represented with A -> B and A <- B. In the exact decoding, the potentials of every combination P(A, B) are calculated by multiplying node and edge potentials (please ref. to Demo 1D for more details). Thus, when we have 2 edges, representing 1 arc, the potentials will be multiplied 2 times, instead of 1. That is the reason, why we extract the square root of the arc potential in addArc() and setArc() functions, but leave the edge potential unchanged in addEdge() and setEdge() functions. This allows the usage of both arcs and edges in the same model (like A -- B <- C)
2. Since we work with potentials, which are not exact probabilities, we have a small degree of freedom here in interpreting the message passing algorithm. We calculate the square of the pairwise potentials (i.e. directed edges in DGM) in approximate message-passing algorithms in order to provide the back-compatibility with the exact inference/decoding algorithms.

Yu Liu

### Re: A few questions about DGM directed and undirected edges

I find the implementation of arc potential, which is square rooted, is quite clever to work with double multiplying the potential while calculating node potentials in MessagePassing->infer(). This approach fits directed graphs or undirected graphs or combinations of both, as you explained.
It seems that the two questions are about one same thing. XD

However, I feel uncertain about the scenario when edges are directed. The node potentials are not calculated correctly according to Koller's book (PGM: P & T) after transform the directed graph into undirected graph. But I'm currently not interested in directed graphs. It's just my uncertainty by now.

I'm both a newbie in PGM and git. A pull request to DGM has been made on GitHub, and there may be some mistakes of both the correction codes and git operations. (Another bother to you here.)

Creator
Posts: 154
Joined: Tue Dec 16, 2008, 20:52
Location: Hannover, Germany
Contact:

### Re: A few questions about DGM directed and undirected edges

The theme of the graph transformation is very interesting. The CGraphExt class is to derive from CGraphLayered class the operations of the marginalization, conditioning (partially implemented) and grouping on graph nodes. This operators are based on these two papers:
I did not read the book of Koller and Friedman, and did not hear about transforming a directed graph into an undirected one. If you have interest in implementing such operators in future, I will be glad to assist.

Yu Liu

### Re: A few questions about DGM directed and undirected edges

The processing of image seems interesting to me, too, for I've studied image processing for several months in my bachelor time. However for now, I'm learning and implementing CRF, kind of probabilistic graphical model (pgm), to complete my doctoral dissertation on user trust prediction in online social networks. So, I'm focusing on extending DGM to support more general graph building, such as graph with different kinds of nodes and edges, as well as training and testing a batch of images (or other graphs) with features by either SGD or L-BFGS.

My plan is to make my extending compatible with your codes after I've finished my research that, I guess, will be done in one or two months. I hope we can write a paper on DGM, a demo of pgm, together and submit to some conference, if my extending could be approved and you're agree on our collaboration.

I'll read the two papers you mentioned some time later. And questions, if any, will be posted in forum.