Главная

Yusuke Watanabe

  1. Loopy Belief Propagation, Bethe Free Energy and Graph Zeta Function.

    Пт, 03/04/2011 - 16:01 — SomNambul
    Authors: Kenji Fukumizu, Yusuke Watanabe
    Subjects: Artificial Intelligence
    Abstract

    We propose a new approach to the theoretical analysis of Loopy Belief
    Propagation (LBP) and the Bethe free energy (BFE) by establishing a formula to
    connect LBP and BFE with a graph zeta function. The proposed approach is
    applicable to a wide class of models including multinomial and Gaussian types.
    The connection derives a number of new theoretical results on LBP and BFE. This
    paper focuses two of such topics.

  2. Graph Zeta Function in the Bethe Free Energy and Loopy Belief Propagation.

    Чт, 02/18/2010 - 16:01 — SomNambul
    Authors: Kenji Fukumizu, Yusuke Watanabe
    Subjects: Artificial Intelligence
    Abstract

    We propose a new approach to the analysis of Loopy Belief Propagation (LBP)
    by establishing a formula that connects the Hessian of the Bethe free energy
    with the edge zeta function. The formula has a number of theoretical
    implications on LBP. It is applied to give a sufficient condition that the
    Hessian of the Bethe free energy is positive definite, which shows
    non-convexity for graphs with multiple cycles. The formula clarifies the
    relation between the local stability of a fixed point of LBP and local minima
    of the Bethe free energy.

  3. Belief Propagation and Loop Calculus for Permanent of a Non-Negative Matrix.

    Втр, 11/10/2009 - 16:01 — SomNambul
    Authors: Yusuke Watanabe, Michael Chertkov
    Subjects: Data Structures and Algorithms
    Abstract

    We consider computation of permanent of a positive N times N non-negative
    matrix, $P=((p_i^j)^{1/T})$, or equivalently the problem of weighted counting
    of perfect matchings (evaluation of the Partition Function) over a fully
    connected bipartite graph, $K_{N,N}$. The problem is known to be #P hard.
    Stated as a graphical model, this problem allows exact Loop Calculus
    representation [Chertkov, Chernyak '06] in terms of a minimum of the Bethe Free
    Energy functional over $N^2$ marginal beliefs.

  4. New graph polynomials from the Bethe approximation of the Ising partition function.

    Чт, 08/27/2009 - 13:23 — SomNambul
    Authors: Kenji Fukumizu, Yusuke Watanabe
    Subjects: Combinatorics
    Abstract

    We introduce two graph polynomials and discuss their properties. The one is a
    polynomial of two variables, motivated by performance analysis of the Bethe
    approximation of the Ising partition function. The other polynomial of one
    variable is obtained by its specialization. It is shown that these polynomials
    satisfy deletion-contraction relations and are essentially new examples of
    V-function, which is introduced by Tutte (1947, Proc. Cambridge Philos. Soc.
    43, 26-40).

  5. New graph polynomials from the Bethe approximation of the Ising partition function.

    Чт, 08/27/2009 - 13:23 — SomNambul
    Authors: Kenji Fukumizu, Yusuke Watanabe
    Subjects: Combinatorics
    Abstract

    We introduce two graph polynomials and discuss their properties. The one is a
    polynomial of two variables, motivated by performance analysis of the Bethe
    approximation of the Ising partition function. The other polynomial of one
    variable is obtained by its specialization. It is shown that these polynomials
    satisfy deletion-contraction relations and are essentially new examples of
    V-function, which is introduced by Tutte (1947, Proc. Cambridge Philos. Soc.
    43, 26-40).

Math-arch

RSS-материал