Prediction aggregation aims to combine information from multiple predictors into a more informative one. We study this question in the setting of calibrated predictors, where each prediction must equal the conditional expectation of the quantity being predicted given the predictor's signal. Given several calibrated input predictors and the feature distribution, but not the underlying Bayes probabilities, we ask when one can construct refined calibrated predictors that preserve the information in the original predictors and cannot be further refined using the available information. We formulate calibrated predictors as signaling schemes and define refinement through feature-independent garblings: a predictor refines another if its signal can simulate the other's signal. Constructibility is characterized through observable linear information: each signal corresponds to a vector over the feature space, and a new signal is constructible exactly when its vector lies in the linear span of the input signal vectors. Under this formulation, we establish a sharp algorithmic picture. For deterministic output predictors, bilateral refinement admits a polynomial-time algorithm based on a bipartite graph between the two input signal partitions, while refinement with an arbitrary number of input predictors is NP-hard. In contrast, when randomized output predictors are allowed, we give a polynomial-time algorithm for any number of input predictors by decomposing constructible signal vectors into extreme rays of the associated polyhedral cone.
Figures & tables
Figure 1: Illustration of Algorithm 1 . In this example, the two deterministic predictors f1 and f2 induce signal partitions over the feature set. We write each signal cell by the feature indices it contains: Πf1={A1,A2,A3} , where A1={x1,x2,x3,x4} , A2={x5} , and A3={x6} ; and Πf2={B1,B2,B3} , where B1={x1,x5} , B2={x2,x3} , and B3={x4,x6} . Figure 1(a) shows the overlap graph G , whose vertices are the signal cells of f1 and f2 , and where an edge indicates a nonempty intersection between two signal cells. The cell A1 is an articulation vertex. Figure 1(b) shows that G−A1 has three connected components: K1={A2,B1} , K2={B2} , and K3={A3,B3} . By Algorithm 1 , the cell A1 is therefore split into the branch pieces A1K1=A1∩B1={x1} , A1K2=A1∩B2={x2,x3} , and A1K3=A1∩B3={x4} . The remaining signal cells A2={x5} and A3={x6} are unchanged. Hence the finest constructible deterministic refinement of f1 is Π1={{x1},{x2,x3},{x4},{x5},{x6}} .