Learning with Relaxed Supervision

Jacob Steinhardt, Percy LiangNeurIPS 2015 · OpenReview

Training machine learning models often involves "intractable supervision." This occurs when the connection between hidden (latent) variables and the final observed output is governed by complex, hard-to-solve constraints. For example, in weakly-supervised semantic parsing, a model might see a question and its final answer, but the logical database query connecting them remains hidden.

The challenge is that the constraint—requiring the latent query to execute and produce the exact observed answer—is deterministic and incredibly difficult to satisfy. If the model makes even a tiny mistake in the query, the execution fails entirely, providing zero learning signal. Standard approaches either use crude approximations that might lead the model astray or get stuck in "intractable" regions where finding a valid latent variable is computationally infeasible.

This paper introduces a rigorous framework that starts with a "relaxed" version of these constraints and adaptively tightens them during training. This ensures the model remains computationally efficient while eventually converging to the true, consistent solution.

Relaxing the Supervision

Instead of enforcing a hard "pass/fail" constraint, the authors propose a parameterized family of relaxations, denoted by $q_\beta$, where $\beta$ controls how "exact" the supervision is. The methodology relies on several key steps:

  1. Relaxed Constraints: Complex constraints are decomposed into simpler, individual components. Rather than requiring a program to be 100% correct to receive any signal, the model is penalized based on how many parts of the output it gets right.
  2. Joint Optimization: The framework does not just train the model parameters ($\theta$); it jointly optimizes the relaxation parameters ($\beta$). As the model's accuracy improves, $\beta$ increases, making the supervision harsher and more exact.
  3. Tractability Constraints: To maintain fast training, the authors use rejection sampling for inference and formulate a mathematical constraint that prevents $\beta$ from growing too quickly.
Conceptual diagram showing the learning trajectory staying within the tractable region by balancing model accuracy and supervision exactness.

This approach ensures the model stays in a "tractable region" (as illustrated above), where it can still find valid samples without wasting millions of attempts. The authors employ an EM-like iterative algorithm that alternates between estimating the model's current performance and solving a constrained optimization problem to update both the model and the relaxation.

Key Insights: Consistency and Tractability

A fundamental tension exists between statistical accuracy (high $\beta$) and computational efficiency (low $\beta$). If the supervision is too harsh relative to the model's current accuracy, inference becomes impossible.

The most important theoretical insight of this work is asymptotic consistency. Even though the supervision is initially altered and relaxed, the global optimum of the relaxed objective remains the true model. The model isn't learning the wrong thing; it is simply taking an easier, guided path to the correct answer. Furthermore, this acts as a smarter version of simulated annealing. Instead of relying on a pre-defined "cooling schedule," the relaxation level is determined automatically by the model's actual progress and a defined computational budget.

Empirical Results

The paper evaluates the method on two synthetic tasks designed to mimic real-world intractability: Unordered Translation (learning a cipher given only a shuffled bag of words) and Conjunctive Semantic Parsing (mapping words to predicates given only the final intersection).

Accuracy vs. number of samples for adaptive and fixed relaxation methods across two tasks. Adaptive methods achieve high accuracy with significantly fewer samples.

The results demonstrate massive efficiency gains. In both tasks, the adaptive methods (which optimize $\beta$) achieved high accuracy using an order of magnitude fewer samples than methods using a fixed relaxation. The accuracy was also highly robust to the specific computational budget; as long as some budget existed, the adaptive optimization eventually found the maximum possible $\beta$, imposing exact supervision by the end of training. As the model improves, it naturally "earns" the right to be supervised by harsher constraints.

Limitations and Future Work

While highly effective, the current approach relies on rejection sampling. In extremely high-dimensional latent spaces, even a good proposal distribution might struggle, suggesting that future work could explore more sophisticated MCMC or variational methods within this framework. Additionally, applying this to massive, real-world semantic parsing or "inverse graphics" tasks will require more complex feature engineering. Finally, the framework currently assumes the user provides the logical decomposition of the constraints; automating the discovery of these simpler projections remains a promising next step.

Summary updated

Abstract

For weakly-supervised problems with deterministic constraints between the latent variables and observed output, learning necessitates performing inference over latent variables conditioned on the output, which can be intractable no matter how simple the model family is. Even finding a single latent variable setting that satisfies the constraints could be difficult; for instance, the observed output may be the result of a latent database query or graphics program which must be inferred. Here, the difficulty lies in not the model but the supervision, and poor approximations at this stage could lead to following the wrong learning signal entirely. In this paper, we develop a rigorous approach to relaxing the supervision, which yields asymptotically consistent parameter estimates despite altering the supervision. Our approach parameterizes a family of increasingly accurate relaxations, and jointly optimizes both the model and relaxation parameters, while formulating constraints between these parameters to ensure efficient inference. These efficiency constraints allow us to learn in otherwise intractable settings, while asymptotic consistency ensures that we always follow a valid learning signal.
BibTeX
@inproceedings{steinhardt2015learning,
  author = {Jacob Steinhardt and Percy Liang},
  title = {{Learning with Relaxed Supervision}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=B1WjOvb_bS},
}

Loading related content...

Figure