TY - GEN

T1 - Minimizing uncertainty in pipelines

AU - Dalvi, Nilesh

AU - Parameswaran, Aditya

AU - Rastogi, Vibhor

PY - 2012

Y1 - 2012

N2 - 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, 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.

AB - 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, 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.

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

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

M3 - Conference contribution

AN - SCOPUS:84877782547

SN - 9781627480031

T3 - Advances in Neural Information Processing Systems

SP - 2942

EP - 2950

BT - Advances in Neural Information Processing Systems 25

T2 - 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012

Y2 - 3 December 2012 through 6 December 2012

ER -