Minimizing Uncertainty in Pipelines
Abstract
In this paper, we consider the problem of debugging large pipelines by human labeling. We represent the execution of a pipeline using a directed acyclic graph of AND and OR nodes, where each node represents a data item produced by some operator in the pipeline. We assume that each operator assigns a confidence to each of its output data. We want to reduce the uncertainty in the output by issuing queries to a human expert, where a query consists of checking if a given data item is correct. In this paper, we consider the problem of asking the optimal set of queries to minimize the resulting output uncertainty. We perform a detailed evaluation of the complexity of the problem for various classes of graphs. We give efficient algorithms for the problem for trees, and show that, for a general dag, the problem is intractable.
Cite
Text
Dalvi et al. "Minimizing Uncertainty in Pipelines." Neural Information Processing Systems, 2012.Markdown
[Dalvi et al. "Minimizing Uncertainty in Pipelines." Neural Information Processing Systems, 2012.](https://mlanthology.org/neurips/2012/dalvi2012neurips-minimizing/)BibTeX
@inproceedings{dalvi2012neurips-minimizing,
title = {{Minimizing Uncertainty in Pipelines}},
author = {Dalvi, Nilesh and Parameswaran, Aditya and Rastogi, Vibhor},
booktitle = {Neural Information Processing Systems},
year = {2012},
pages = {2942-2950},
url = {https://mlanthology.org/neurips/2012/dalvi2012neurips-minimizing/}
}