Learnability HW04

Jeffrey Heinz

2022 09 28

  1. Give one difference and one similarity between a PAC learning algorithm and an Occam algorithm.
  2. Valiant writes “I believe that the primary stumbling block that prevents humans from being able to learn more complex concepts at a time than they can, is the computational difficulty of extracting regularities from moderate amounts of data, rather than the need for inordinate amounts of data.” Do you agree or disagree? Explain.
  3. What does Valiant mean by computational limits on learning?
  4. What is the significance of the proof “that any algorithm for PAC learning regular languages would imply a method for breaking the RSA cryptosystem”?
  5. Valiant writes “Any reader not convinced that there are real computational impediments to generalization should take as a challenge this simpler goal of finding a PAC learning algorithm to categorize the output of a lattice automaton as words or not-words in polynomial time.” I agree with Valiant. If you don’t, work on this challenge! But there is also a simpler argument to be made. The regular languages includes the finite languages. What is the VC dimension of the class of finite languages?
  6. Explain why a teacher can enhance learning, according to Valiant?
  7. The last section is titled “PAC Learning as a Basis of Cognition”. This is pretty ambitious! Explain what the computational limits on learning have to say about Algorithm A and concept class C and how that may inform a theory of cognition.