Lune

ICML2023Top-tier venue

Exact Inference in High-order Structured Prediction

Chuyang Ke, Jean Honorio

Abstract

In this paper, we study the problem of inference in high-order structured prediction tasks. In the context of Markov random fields, the goal of a high-order inference task is to maximize a score function on the space of labels, and the score function can be decomposed into sum of unary and high-order potentials. We apply a generative model approach to study the problem of high-order inference, and provide a two-stage convex optimization algorithm for exact label recovery. We also provide a new class of hypergraph structural properties related to hyperedge expansion that drives the success in general high-order inference problems. Finally, we connect the performance of our algorithm and the hyperedge expansion property using a novel hypergraph Cheeger-type inequality.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Neural Temporal Point Processes for Forecasting Directional Relations in Evolving HypergraphsTony Gracious, Arman Gupta, Ambedkar DukkipatiAAAI 2025 · 5 citations
  2. Fairness constraints can help exact inference in structured predictionKevin Bello, Jean HonorioNeurIPS 2020 · 6 citations
  3. Hypergraph Joint Representation Learning for Hypervertices and Hyperedges via Cross ExpansionYuguang Yan, Yuanlin Chen, Shibo Wang, Hanrui Wu et al.AAAI 2024 · 20 citations
  4. From Graphs to Hypergraphs: Hypergraph Projection and its ReconstructionYanbang Wang, Jon M. KleinbergICLR 2024 · 7 citations
  5. Structured Mean-Field Variational Inference for Higher-Order Span-Based Semantic RoleWei Liu, Songlin Yang, Kewei TuACL Findings 2023
Dusk over the sea between two cliffs drawn in fine vertical lines