Nov 2, 12:00, WeH 1327
NP-Completeness of Searches for Smallest Consistent Feature Sets
Scott Davies (*)
In many learning problems, the learning system is presented with
values for features that are actually irrelevant to the concept it is
trying to learn. The FOCUS algorithm, due to Almuallim and
Dietterich, performs an explicit search for the smallest possible
input feature set S that permits a consistent mapping from the
features in S to the output feature. The FOCUS algorithm has
superpolynomial runtime, but Almuallim and Dietterich leave open the
question of tractability of the underlying problem. We will show that
the underlying problem is NP-complete. We will also describe briefly
some experiments that demonstrate the benefits of using smallest
possible feature sets.
(*) joint work with Stuart Russell