Simple MAP Inference via Low-Rank Relaxations
Authors: Roy Frostig, Sida Wang, Percy Liang, Christopher D. Manning
NeurIPS 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The second part of this paper explores the use of very low-rank relaxation and randomized rounding (R3) in practice. We use projected gradient and coordinate-wise ascent for solving the R3 relaxed problem (Section 4). In this paper, we study algorithms based on low-rank SDP relaxations which are both remarkably simple and capable of guaranteeing solution quality. 5 Experiments We compare the algorithms from Table 1 on three benchmark MRFs and an additional artificial MRF. |
| Researcher Affiliation | Academia | Roy Frostig , Sida I. Wang, Percy Liang, Christopher D. Manning Computer Science Department, Stanford University, Stanford, CA, 94305 {rf,sidaw,pliang}@cs.stanford.edu, manning@stanford.edu |
| Pseudocode | Yes | Algorithm 1: The full randomized relax-and-round (R3) procedure, given a weight matrix A; Sk( ) is row normalization and t is the step size in the t th iteration. |
| Open Source Code | No | The paper does not contain any explicit statement or link providing access to the source code for the methodology described. |
| Open Datasets | Yes | The sets seg, dbn, and grid40 are from the PASCAL 2011 Probabilistic Inference Challenge5 seg are small segmentation models (50 instances, average 230 variables, 622 edges), dbn are deep belief networks (108 instances, average 920 variables, 54160 edges), and grid40 are 40x40 grids (8 instances, 1600 variables, 6240 or 6400 edges) whose edge weights outweigh their unaries by an order of magnitude. The chain set comprises 300 randomly generated 20-node chain MRFs with no unary potentials and random unit-Gaussian edge weights it is principally an extension of the coupling two-node example (Figure 2), and serves as a structural obverse to grid40 in that it lacks cycles entirely. Among these, the dbn set comprises the largest and most edge-dense instances. (Footnote 5: http://www.cs.huji.ac.il/project/PASCAL/) |
| Dataset Splits | No | The paper mentions "These settings were tuned towards the benchmarks using a few arbitrary instances from each dataset," which implies a tuning process, but it does not specify explicit train/validation/test dataset splits with percentages, counts, or references to predefined splits for general model validation. |
| Hardware Specification | No | The paper discusses potential hardware use like "using GPUs for dense A" but does not provide specific hardware details (e.g., GPU models, CPU types, memory amounts) for the machines on which their experiments were conducted. |
| Software Dependencies | No | The paper describes algorithms and their implementation details (e.g., "using projected gradient ascent"), but it does not specify any software dependencies with version numbers (e.g., Python 3.8, PyTorch 1.9, CPLEX 12.4). |
| Experiment Setup | Yes | In all experiments, we use LRP4, i.e. the width-4 relaxation. The R3 gradient step size scheme is t = 1/ sqrt(t). In the parallel setting, mean-field updates are prone to large oscillations, so we smooth the update with the current point: x = (1 )x + tanh(Ax). Our experiments set = 0.5. Gibbs is annealed from an initial temperature of 10 down to 0.1. |