L EARNABLE C ONCEPTS Some simple concepts cannot be represented compactly in DTs Parity(x) = X 1 xor X 2 xor … xor X n Majority(x) = 1 if most of X i 's are 1, 0 otherwise Exponential size in # of attributes Need exponential # of examples to learn exactly The ease of learning is dependent on shrewdly (or luckily) chosen attributes that correlate with CONCEPT
{}