greedythickthinning, what is it exactly?

morphos7 · Post by **morphos7** » Mon Jun 15, 2009 2:04 pm

Hello,

I would like to know what exactly is greedythickthinning ?
I found on the forum that's this algo is based on heckerman's tutorial.
But when I look at this paper, i don't find any references about greedythickthinning ! No paragraph explicitly talks about greedythickthinning.

So, I would like to understand what greedythickthinning is exactly.

Thank you

mark · Post by **mark** » Mon Jun 15, 2009 5:03 pm

Does this answer your question? http://genie.sis.pitt.edu/forum/viewtopic.php?t=182

morphos7 · Post by **morphos7** » Tue Jun 16, 2009 8:37 am

hello,

thank you for your help, but i think this response is insufficient:
i cite " GreedyThickThinning starts with an empty network, then first greedily thickens it and finally thins it. "

Could you give me a precise description of the algorithm? Thank you

mark · Post by **mark** » Tue Jun 16, 2009 8:00 pm

Greedily adding means that it adds (or reverses) the edge that increases the score as much as possible. This process is repeated until there is no operation that increases the score anymore. In the second stage it removes (or reverses) edges that, again, increase the score as much as possible. Learning is done when the score cannot be increased anymore. I hope this description helps.

morphos7 · Post by **morphos7** » Thu Jun 18, 2009 4:16 pm

hello,

I think you well reply to my question.
If i well understood, it is very very similar with Greedy search algorithm?
but adding and deleting edges are made in 2 differents steps.

Thanks

mark · Post by **mark** » Thu Jun 18, 2009 5:14 pm

Yes, it's a greedy search algorithm that works in two stages.

morphos7 · Post by **morphos7** » Fri Jun 19, 2009 8:19 am

Why is the search made in 2 stages?
Is it faster than classic Greedy Search?

mark · Post by **mark** » Fri Jun 19, 2009 8:31 am

For standard greedy search you need a random starting position, this is not necessary for GreedyThickThinning.