Learning Internal Representations Probably the most important problem in machine learning is the preliminary biasing of a learneru0027s hypothesis space so that it is small enough to ensure good generalisation from reasonable training sets, yet large enough that it contains a good solution to the problem being learnt. In this paper a mechanism for em automatically learning or biasing the learneru0027s hypothesis space is introduced. It works by first learning an appropriate em internal representation for a learning environment and then using that representation to bias the learneru0027s hypothesis space for the learning of future tasks drawn from the same environment.  internal representation :98,must be learnt by sampling from em many similar tasks, not just a single task as occurs in ordinary machine learning. It is proved that the number of examples m em per task required to ensure good generalisation from a representation learner obeys m  O(abn) where n is the number of tasks being learnt and a and b are constants. If the tasks are learnt independently (em i.e. without a common representation) then mO(ab). It is argued that for learning environments such as speech and character recognition bgg a and hence representation learning in these environments can potentially yield a drastic reduction in the number of examples required per task. It is also proved that if n  O(b) (with mO(abn)) then the representation learnt will be good for learning novel tasks from the same environment, and that the number of examples required to generalise well on a novel task will be reduced to O(a) (as opposed to O(ab) if no representation is used).  is :266,shown that gradient descent can be used to train neural network representations and experiment results are reported providing strong qualitative support for the theoretical results.

Topdown induction of decision trees: rigorous guarantees and inherent limitations Consider the following heuristic for building a decision tree for a function f : 0,1n to pm 1. Place the most influential variable x_i of f at the root, and recurse on the subfunctions f_x_i0 and f_x_i1 on the left and right subtrees respectively; terminate once the tree is an varepsilonapproximation of f. We analyze the quality of this heuristic, obtaining nearmatching upper and lower bounds:  :66,93,Upper bound: For every f with decision tree size s and every varepsilon in (0,frac12), this heuristic builds a decision tree of size at most sO(log(svarepsilon)log(1varepsilon)).  Lower bound: For every varepsilon in (0,frac12) and s le 2tildeO(sqrtn), there is an f with decision tree size s such that this heuristic builds a decision tree of size stildeOmega(log s).  :126,also obtain upper and lower bounds for monotone functions: sO(sqrtlog svarepsilon) and stildeOmega(sqrt4log s  ) respectively. The lower bound disproves conjectures of Fiat and Pechyony (2004) and Lee (2009).  upper bounds :157,yield new algorithms for properly learning decision trees under the uniform distribution. We show that these algorithmswhich are motivated by widely employed and empirically successful topdown decision tree learning heuristics such as ID3, C4.5, and CARTachieve provable guarantees that compare favorably with those of the current fastest algorithm (Ehrenfeucht and Haussler, 1989). Our lower bounds shed new light on the limitations of these heuristics.  :224,we revisit the classic work of Ehrenfeucht and Haussler. We extend it to give the first uniformdistribution proper learning algorithm that achieves polynomial sample and memory complexity, while matching its stateoftheart quasipolynomial runtime.