2022 08 25
Read chapter 3 of Probably Approximately Correct by Leslie Valiant and answer the following questions.
What does Valiant mean by the Turing triad? According to Valiant, why are these properties important?
What does Valiant mean by a model that is robust under variation? Give an example of a model robust under variation that is not discussed by Valiant.
Valiant writes “We are not interested in properties of arbitrary formalisms. We want some assurance that we have captured the characteristics of some real-world phenomenon. Robustness of models is the only known source of such assurance.” Do you agree or disagree? Explain.
What does it mean for an algorithm to take polynomial time? Exponential time? Nondeterministic polynomial time?
If you have any questions about the classes in Figure 3.5, please write them here.
According to Valiant, supervised learning algorithms operate in two phases. What are those phases?
Valiant writes that the perceptron algorithm “goes through each training example one by one, and if the example label is correctly predicted by the current hypothesis, then the hypothesis is not changed. If the example label is not predicted correctly, then the hypothesis is updated so as to be “more likely,” in a certain sense, to be correct on that same example if presented again later." This kind of “error-driven” learning is very common. (No question here)
What are the two most important reasons that Valiant considers the perceptron algorithm to be powerful?
Provide one or more additional reasons.
Valiant writes the following about the perceptron algorithm: “Learning is achieved in many steps that are plausible but innocuous when viewed one by one in isolation. These steps work because there is an overall algorithmic plan. In combination the steps achieve something, in particular, some kind of convergence.” How is the VZIA algorithm similar or different to the perceptron algorithm?