NDLI: The Bethe approximation of the pattern maximum likelihood distribution

Content Provider	IEEE Xplore Digital Library
Author	Vontobel, P.O.
Copyright Year	2012
Description	Author affiliation: Hewlett-Packard Laboratories, 1501 Page Mill Road Palo Alto, CA 94304, USA (Vontobel, P.O.)
Abstract	Among all memoryless source distributions, the pattern maximum likelihood (PML) distribution is the distribution which maximizes the probability that a memoryless source produces a string with a given pattern. Equivalently, the PML distribution maximizes the permanent of a certain non-negative matrix. We reformulate this maximization problem as a double minimization problem of a suitable Gibbs free energy function. Because finding the minimum of this function appears intractable for practically relevant problem sizes, one must look for tractable approximations. One approach is to approximately find a minimum (or at least a local minimum) of the Gibbs free energy function by applying an alternating minimization algorithm where the steps are based on quantities that are obtained by Markov chain Monte Carlo sampling. One can show that this approach is equivalent to an algorithm that was proposed by Orlitsky et al. An alternative approach is to replace the Gibbs free energy function by a tractable approximation like the Bethe free energy function and to apply an alternating minimization algorithm to this function. As it turns out, empirically, this latter approach gives very good approximations to the PML distribution (or at least a locally optimal PML distribution), and, for the same level of accuracy, is two to three orders of magnitude faster than the former approach for practically relevant problem sizes. Moreover, the above free energy framework allows us to simplify some earlier proofs of properties of the PML distribution and to derive some new properties of the PML distribution, along with obtaining similar results for its Bethe approximation.
Starting Page	2012
Ending Page	2016
File Size	186402
Page Count	5
File Format	PDF
ISBN	9781467325806
ISSN	21578117
e-ISBN	9781467325790
e-ISBN	9781467325783
DOI	10.1109/ISIT.2012.6283654
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-07-01
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Approximation methods Approximation algorithms Minimization Vectors Maximum likelihood estimation Graphical models Mercury (metals)
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Bethe and Sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the Valiant-Valiant estimate

Maximum persistency via iterative relaxed inference with graphical models

A phase transition for the uniform distribution in the pattern maximum likelihood problem

Phase Transitions for the Uniform Distribution in the Pattern Maximum Likelihood Problem and its Bethe Approximation

Recursive Prediction Error Methods for Adaptive Estimation

Approximate least squares parameter estimation with structured observations

Optimisation of the Maximum Likelihood Method Using Bias Minimisation

Efficient Bingham filtering based on saddlepoint approximations

Toroidal information fusion based on the bivariate von Mises distribution

The Bethe approximation of the pattern maximum likelihood distribution

Similar Documents

The Bethe and Sinkhorn approximations of the pattern maximum likelihood estimate and their connections to the Valiant-Valiant estimate

Maximum persistency via iterative relaxed inference with graphical models

A phase transition for the uniform distribution in the pattern maximum likelihood problem

Phase Transitions for the Uniform Distribution in the Pattern Maximum Likelihood Problem and its Bethe Approximation

Recursive Prediction Error Methods for Adaptive Estimation

Approximate least squares parameter estimation with structured observations

Optimisation of the Maximum Likelihood Method Using Bias Minimisation

Efficient Bingham filtering based on saddlepoint approximations

Toroidal information fusion based on the bivariate von Mises distribution

The Bethe approximation of the pattern maximum likelihood distribution