Learning from examples with unspecified attribute values (extended abstract)
1 INTRODUCTION We introduce the UAV learning model in which some of the attributes in the examples are un-specified. In our model. an example 2 is classified positive (resp., negative) if all possible assignments for the unspecified attributes result in a positive (resp., negative) classification. Otherwise the classification given to z is 'l'? " (for unknown). Given an example z in which some attributes are unspecified, the oracle UA\y-MQ responds with the classification of 2. Given a hypothesis h, the oracle UAV-EQ returns an example r (that could have unsper-ified at,tributes) for which h(z) is incorrect. We show that any class learnable in the exact model using the MQ and EQ oracles is also learnable in the U.4V model using the MQ and IJA\'-EQ oracles as long as the counterexamples provided by the UAV-EQ oracle have a logarithmic number of unspecified attributes. We also show that any class learnable in the exact, model using the MQ and EQ oracles is also learnable in the UA\' model using the UAV-MC) and UA4V-EQ oracles as well as an oracle t,o evaluate a given boolean formula on an example with unspecified attributes. (For some hypothesis classes such as decision trees and unate formulas the evaluation can be done in polynomial time without an oracle.) We also study the learnability of a universal class of decision trees under the UAV model and of DNF formulas under a representation-dependent variation of t,he CJAV model. Most theoretical work on learning boolean functions assumes that the examples are drawn from (0, l}n and each example is classified as positive (" + ") or negative ("-") by the unknown target concept f. However, consider the situation of trying to predict whether or not an individual will default on a loan. There are a large number of attributes that one might consider (some about the individual and some about t,he individ-ual's employer). Using standard approaches to learning boolean functions, a learning algorithm could consider each loan application as an example from (0, l}* where n is the number of attributes under consideration for loan applications. Let's assume that if we had correct data for all of the attributes, then such an algorithm could make a very good prediction as t,o whether or not the individual will default on the loan. However, in practice some attributes' values will not be provided (or specified). For example: some states may prohibit the …