## Sunday, February 20, 2011

### Generalized Distributive Law

With regular distributive law you can do things like

$$\sum_{x_1,x_2,x_3} \exp(x_1 + x_2 + x_3)=\sum_{x_1} \exp x_1 \sum_{x_2} \exp x_2 \sum_{x_3} \exp x_3$$

This breaks the original large sum into 3 small sums which can be computed independently.

A more realistic scenario requires factorization into overlapping parts. For instance take the following

$$\sum_{x1,x2,x3,x_4,x_5} \exp(x_1 x_2 + x_2 x_3 + x_3 x_4+x_4 x_5)$$

You can't use directly apply distributive law here. Naive evaluation of the sum is exponential in the number of variables, however this problem can be solved in time linear in the number of variables.

Consider the following factorization
$$\sum_{x1,x2} \exp x_1 x_2 \left( \sum_{x_3} \exp x_2 x_3 \left( \sum_{x_4} \exp x_3 x_4 \left( \sum_{x_5} \exp x_4 x_5 \right) \right) \right)$$

Now note that when computing inner sums, naive approach results in same sum being recomputed many times. Save those shared pieces and you get an algorithm that's quadratic in number of variable values and linear in number of variables

Viterbi and Forward-Backward are specific names of this kind of dynamic programming for chain structured sums as above.

To consider tree-structured sum, take a problem of counting independent sets in a tree-structured graph. In this case we can use the following factorization

This is the first step of the recursion and you can repeat it until your pieces have tractable size.

Now for a general case of non-tree-structured graph, consider the sum below

$$\sum_{x1,x2,x3,x_4,x_5} \exp( x_1 x_2 + x_2 x_3 + x_3 x_4+x_4 x_5 + x_5 x_1 )$$

Here, variables form a loop, so regular tree recursion like Viterbi does not apply. However, this sum can be found efficiently, linear in the number of variables, and cubically in the number of variable values. I have more in depth explanation of decomposing problems like above in an answer on cstheory site but the basic idea is similar to the approach with independent sets -- fix some variables and recurse on subparts.

This kind of general factorization has been re-invented many times and is known as Generalized Distributive Law, tree-decomposition, junction tree, clique tree, partial k-tree, and probably a few other names.

Notebook

remo said...

THANKS FOR THE INFORMATION...
<a href="http://www.chloros.in/digital-marketing-internship.htmlhttp://www.chloros.in/digital-marketing-internship.html>Digital Marketing Internship Program in Bangalore</a>

draj said...

Excellent machine learning blog,thanks for sharing...
Seo Internship in Bangalore
Smo Internship in Bangalore
Digital Marketing Internship Program in Bangalore

Unknown said...

This entire post absolutely ROCKS! Thank you for all the hard work you put into it. It really shows. Click for more, Click for more, Click for solution, Click for solution, Click for solution.

Nenihwang said...

NAGAQQ | AGEN BANDARQ | BANDARQ ONLINE | ADUQ ONLINE | DOMINOQQ TERBAIK

Yang Merupakan Agen Bandarq, Domino 99, Dan Bandar Poker Online Terpercaya di asia hadir untuk anda semua dengan permainan permainan menarik dan bonus menarik untuk anda semua

Bonus yang diberikan NagaQQ :
* Bonus rollingan 0.5%,setiap senin di bagikannya
* Bonus Refferal 10% + 10%,seumur hidup
* Bonus Jackpot, yang dapat anda dapatkan dengan mudah
* Minimal Depo 15.000
* Minimal WD 20.000

Memegang Gelar atau title sebagai AGEN BANDARQ Terbaik di masanya

Games Yang di Hadirkan NagaQQ :
* Poker Online
* BandarQ
* Domino99
* Bandar Poker
* Bandar66(NEW GAMES)

Info Lebih lanjut Kunjungi :
Website : NAGAQQ
WHATSAPP : +855967014811
Line : Cs_nagaQQ
TELEGRAM :+855967014811

BACA JUGA BLOGSPORT KAMI YANG LAIN:
berita nagaqq/
agen bandarq online/
Kemenangan NagaQQ/

Cindy said...

RajaBandarQ
Adalah website yang paling digemari saat ini oleh para pecinta judi online
Dengan adanya 8 game terbaik yang disediakan oleh pihak website RajaBandarQ , akan banyak mengundang para pecinta judi poker online untuk bermain diwebsite RajaBandarQ

8 Game Yang disediakan oleh pihak RajaBandarQ diantaranya adalah :

* BandarQ
* Bandar Poker
* Bandar 66 ( New Games )
* Capsa Susun
* Domino QQ
* Poker
* Sakong

Keunggulan jika bergabung di website RajaBandarQ :

- Proses Deposit dan Withdraw Hanya 2 Menit
- 100% Mudah Menang & Fairplay Game
- Minimal Deposit & Withdraw Rp 20.000,-
- Bonus Rollingan 0.3% (Tanpa Syarat)
- Bonus Referral 20% (Seumur Hidup)
- Bonus Extra Refferal
- Sistem Keamanan Terbaru
- Support 6 Bank Local ( BCA , BNI , BRI , CIMB NIAGA , DANAMON , MANDIRI )

Kami Memberikan Bukti Bukan Janji !!!

- Blogger : Cerita Dewasa

- Blogger : Kisah Kehidupan

- Blogger : Panduan Judi Online

Tunggu apalagi ? Daftarkan diri anda segera juga dan menangkan jackpot jutaan rupiah hanya dengan modal Rp 20.000,-
Hanya Di RajaBandarQ

Join : >>DAFTAR RAJABANDARQ<<

Vaness Wie said...

PERMAINAN ONLINE TERBESAR DI INDONESIA

Website paling ternama dan paling terpercaya di Asia ^^
Sistem pelayanan 24 Jam Non-Stop bersama dengan CS Berpengalaman respon tercepat :)
Memiliki 8 Jenis game yang sangat digemari oleh seluruh peminat poker / domino

- Bandar Q
- Bandar Sakong
- Bandar Poker
- Poker
- Domino 99
- Capsa Susun
- BANDAR66 / ADU BALAK ( GAME TERBARU )

Permainan Judi online yang menggunakan uang asli dan mendapatkan uang asli ^^
* Minimal Deposit : 20.000
* Minimal Withdraw : 20.000
* Deposit dan Withdraw 24 jam Non stop ( Kecuali Bank offline / gangguan )
* Bonus REFFERAL 15 % Seumur hidup tanpa syarat
* Bonus ROLLINGAN 0.3 % Dibagikan 5 hari 1 kali
* Proses Deposit & Withdraw PALING CEPAT
* Sistem keamanan Terbaru & Terjamin
* Poker Online Terpercaya
* Live chat yang Responsive
* Support lebih banyak bank LOKAL

Website SahabatQQ
WA 1 : +85515769793
WA 2 : +855972076840
LINE : SAHABATQQ
YM : cs2_sahabatqq@yahoo.com
Kami Siap Melayani anda 24 jam Nonstop

Daftar SahabatQQ

Yasmin Akter said...
john said...
john said...
Pixel-Lovers said...
John said...

I think that service Coronavirusessay is the best in writing essay in this niche. Thank you!دانلود آهنگ قدیمی

دانلود آهنگ غمگین

mobito said...

با تبلیغات محیطی در اتوبان های پرتردد می توانید محصولات خود را به بخش بزرگی از افراد جامعه معرفی کنید.

Mark Spencer said...

This is a really decent site post. Not very numerous individuals would really, the way you simply did. I am truly inspired that there is such a great amount of data about this subject have been revealed buy marketing assignment online and you've put forth a valiant effort, with so much class. On the off chance that needed to know more about green smoke surveys, than by all methods come in and check our stuff.

Sherman Souto said...

Thank you for providing this blog really appreciate the efforts you have taken into curating this article if you want you can check out data science course in bangalore they have a lot to offer with regards to data science in terms of training and live projects.

hameedudhaaam said...

I believe this will help your website become more organized because you have decided to set a part on this site for the inquiries regarding tax and as well as the helpful discussions. To be honest, this is one of the few sites that are doing this kind of strategy. Also, I think that this will not only benefit your clients or the potential ones but you most help with assignment writing especially because you will be able to see the questions easier.

hameedudhaaam said...

If we are going to talk about murals, it is a harsh reality that there are people who do not appreciate artworks like this. I fell bad, but there is less that I can do; I want them to realize that murals are beautiful and worth appreciating. But I simply don't know where to start. Sometimes, I think of writing as my way to influence people to appraiser things that should be appreciated. I don't know if that is going to be effective, but I want to give it assignment crux uk a try.

periyannan said...

Thank you for the informative post. It was thoroughly helpful to me. Keep posting more such articles and enlighten us.
python internship | web development internship |internship for mechanical engineering students |mechanical engineering internships |java training in chennai |internship for 1st year engineering students |online internships for cse students |online internship for engineering students |internship for ece students |data science internships

ناواران said...
zahra said...