%PDF-1.3 1 0 obj << /Kids [ 4 0 R 5 0 R 6 0 R 7 0 R 8 0 R 9 0 R 10 0 R 11 0 R 12 0 R ] /Type /Pages /Count 9 >> endobj 2 0 obj << /Subject (Neural Information Processing Systems http\072\057\057nips\056cc\057) /Publisher (Curran Associates) /Language (en\055US) /Created (2012) /Description-Abstract (Sudderth\054 Wainwright\054 and Willsky conjectured that the Bethe approximation corresponding to any fixed point of the belief propagation algorithm over an attractive\054 pairwise binary graphical model provides a lower bound on the true partition function\056 In this work\054 we resolve this conjecture in the affirmative by demonstrating that\054 for any graphical model with binary variables whose potential functions \050not necessarily pairwise\051 are all log\055supermodular\054 the Bethe partition function always lower bounds the true partition function\056 The proof of this result follows from a new variant of the \215four functions\216 theorem that may be of independent interest\056) /Producer (Python PDF Library \055 http\072\057\057pybrary\056net\057pyPdf\057) /Title (The Bethe Partition Function of Log\055supermodular Graphical Models) /Date (2012) /Type (Conference Proceedings) /firstpage (117) /Book (Advances in Neural Information Processing Systems 25) /Description (Paper accepted and presented at the Neural Information Processing Systems Conference \050http\072\057\057nips\056cc\057\051) /Editors (F\056 Pereira and C\056J\056C\056 Burges and L\056 Bottou and K\056Q\056 Weinberger) /Author (Nicholas Ruozzi) /lastpage (125) >> endobj 3 0 obj << /Type /Catalog /Pages 1 0 R >> endobj 4 0 obj << /Contents 13 0 R /Parent 1 0 R /Type /Page /Resources 14 0 R /MediaBox [ 0 0 612 792 ] >> endobj 5 0 obj << /Contents 31 0 R /Parent 1 0 R /Type /Page /Resources 32 0 R /MediaBox [ 0 0 612 792 ] >> endobj 6 0 obj << /Contents 73 0 R /Parent 1 0 R /Type /Page /Resources 74 0 R /MediaBox [ 0 0 612 792 ] >> endobj 7 0 obj << /Contents 91 0 R /Parent 1 0 R /Type /Page /Resources 92 0 R /MediaBox [ 0 0 612 792 ] >> endobj 8 0 obj << /Contents 93 0 R /Parent 1 0 R /Type /Page /Resources 94 0 R /MediaBox [ 0 0 612 792 ] >> endobj 9 0 obj << /Contents 99 0 R /Parent 1 0 R /Type /Page /Resources 100 0 R /MediaBox [ 0 0 612 792 ] >> endobj 10 0 obj << /Contents 101 0 R /Parent 1 0 R /Type /Page /Resources 102 0 R /MediaBox [ 0 0 612 792 ] >> endobj 11 0 obj << /Contents 103 0 R /Parent 1 0 R /Type /Page /Resources 104 0 R /MediaBox [ 0 0 612 792 ] >> endobj 12 0 obj << /Contents 105 0 R /Parent 1 0 R /Type /Page /Resources 106 0 R /MediaBox [ 0 0 612 792 ] >> endobj 13 0 obj << /Length 2628 /Filter /FlateDecode >> stream xڅYK۸ϯ@9%vٛ:`ρ 1E2$n/s+h4;w~zW>N~$Ye*r!,q"/Kiχydz Iy<9ǫC廯`wn(^Ө9}sVwtna}yYdE^_z"x>Y{a';'L^>3ٍO;qvPl 3