Quadratic programming relaxations for metric labeling and markov random field MAP estimation

Pradeep Ravikumar, John Lafferty

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    16 Citations (Scopus)

    Abstract

    Quadratic program relaxations are proposed as an alternative to linear program relaxations and tree reweighted belief propagation for the metric labeling or MAP estimation problem. An additional convex relaxation of the quadratic approximation is shown to have additive approximation guarantees that apply even when the graph weights have mixed sign or do not come from a metric. The approximations are extended in a manner that allows tight variational relaxations of the MAP problem, although they generally involve non-convex optimization. Experiments carried out on synthetic data show that the quadratic approximations can be more accurate and computationally efficient than the linear programming and propagation based alternatives.

    Original languageEnglish (US)
    Title of host publicationACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006
    Pages737-744
    Number of pages8
    DOIs
    StatePublished - Dec 1 2006
    Event23rd International Conference on Machine Learning, ICML 2006 - Pittsburgh, PA, United States
    Duration: Jun 25 2006Jun 29 2006

    Publication series

    NameACM International Conference Proceeding Series
    Volume148

    Conference

    Conference23rd International Conference on Machine Learning, ICML 2006
    CountryUnited States
    CityPittsburgh, PA
    Period6/25/066/29/06

    Fingerprint

    Quadratic programming
    Linear programming
    Labeling
    Experiments

    ASJC Scopus subject areas

    • Human-Computer Interaction

    Cite this

    Ravikumar, P., & Lafferty, J. (2006). Quadratic programming relaxations for metric labeling and markov random field MAP estimation. In ACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006 (pp. 737-744). (ACM International Conference Proceeding Series; Vol. 148). https://doi.org/10.1145/1143844.1143937

    Quadratic programming relaxations for metric labeling and markov random field MAP estimation. / Ravikumar, Pradeep; Lafferty, John.

    ACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006. 2006. p. 737-744 (ACM International Conference Proceeding Series; Vol. 148).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Ravikumar, P & Lafferty, J 2006, Quadratic programming relaxations for metric labeling and markov random field MAP estimation. in ACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006. ACM International Conference Proceeding Series, vol. 148, pp. 737-744, 23rd International Conference on Machine Learning, ICML 2006, Pittsburgh, PA, United States, 6/25/06. https://doi.org/10.1145/1143844.1143937
    Ravikumar P, Lafferty J. Quadratic programming relaxations for metric labeling and markov random field MAP estimation. In ACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006. 2006. p. 737-744. (ACM International Conference Proceeding Series). https://doi.org/10.1145/1143844.1143937
    Ravikumar, Pradeep ; Lafferty, John. / Quadratic programming relaxations for metric labeling and markov random field MAP estimation. ACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006. 2006. pp. 737-744 (ACM International Conference Proceeding Series).
    @inproceedings{0c0bfba05b744817a13f9b8cbd297f58,
    title = "Quadratic programming relaxations for metric labeling and markov random field MAP estimation",
    abstract = "Quadratic program relaxations are proposed as an alternative to linear program relaxations and tree reweighted belief propagation for the metric labeling or MAP estimation problem. An additional convex relaxation of the quadratic approximation is shown to have additive approximation guarantees that apply even when the graph weights have mixed sign or do not come from a metric. The approximations are extended in a manner that allows tight variational relaxations of the MAP problem, although they generally involve non-convex optimization. Experiments carried out on synthetic data show that the quadratic approximations can be more accurate and computationally efficient than the linear programming and propagation based alternatives.",
    author = "Pradeep Ravikumar and John Lafferty",
    year = "2006",
    month = "12",
    day = "1",
    doi = "10.1145/1143844.1143937",
    language = "English (US)",
    isbn = "1595933832",
    series = "ACM International Conference Proceeding Series",
    pages = "737--744",
    booktitle = "ACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006",

    }

    TY - GEN

    T1 - Quadratic programming relaxations for metric labeling and markov random field MAP estimation

    AU - Ravikumar, Pradeep

    AU - Lafferty, John

    PY - 2006/12/1

    Y1 - 2006/12/1

    N2 - Quadratic program relaxations are proposed as an alternative to linear program relaxations and tree reweighted belief propagation for the metric labeling or MAP estimation problem. An additional convex relaxation of the quadratic approximation is shown to have additive approximation guarantees that apply even when the graph weights have mixed sign or do not come from a metric. The approximations are extended in a manner that allows tight variational relaxations of the MAP problem, although they generally involve non-convex optimization. Experiments carried out on synthetic data show that the quadratic approximations can be more accurate and computationally efficient than the linear programming and propagation based alternatives.

    AB - Quadratic program relaxations are proposed as an alternative to linear program relaxations and tree reweighted belief propagation for the metric labeling or MAP estimation problem. An additional convex relaxation of the quadratic approximation is shown to have additive approximation guarantees that apply even when the graph weights have mixed sign or do not come from a metric. The approximations are extended in a manner that allows tight variational relaxations of the MAP problem, although they generally involve non-convex optimization. Experiments carried out on synthetic data show that the quadratic approximations can be more accurate and computationally efficient than the linear programming and propagation based alternatives.

    UR - http://www.scopus.com/inward/record.url?scp=34250753342&partnerID=8YFLogxK

    UR - http://www.scopus.com/inward/citedby.url?scp=34250753342&partnerID=8YFLogxK

    U2 - 10.1145/1143844.1143937

    DO - 10.1145/1143844.1143937

    M3 - Conference contribution

    SN - 1595933832

    SN - 9781595933836

    T3 - ACM International Conference Proceeding Series

    SP - 737

    EP - 744

    BT - ACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006

    ER -