  Mutual information has been successfully adopted in filter feature-selection
methods to assess both the relevancy of a subset of features in predicting the
target variable and the redundancy with respect to other variables. However,
existing algorithms are mostly heuristic and do not offer any guarantee on the
proposed solution. In this paper, we provide novel theoretical results showing
that conditional mutual information naturally arises when bounding the ideal
regression/classification errors achieved by different subsets of features.
Leveraging on these insights, we propose a novel stopping condition for
backward and forward greedy methods which ensures that the ideal prediction
error using the selected feature subset remains bounded by a user-specified
threshold. We provide numerical simulations to support our theoretical claims
and compare to common heuristic methods.
