Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World 1st Edition by Leslie Valiant (PDF)

Description

From a leading computer scientist, a unifying theory that will revolutionize our understanding of how life evolves and learns. How does life prosper in a complex and erratic world? While we know that nature follows patterns — such as the law of gravity — our everyday lives are beyond what known science can predict. We nevertheless muddle through even in the absence of theories of how to act. But how do we do it? In Probably Approximately Correct, computer scientist Leslie Valiant presents a masterful synthesis of learning and evolution to show how both individually and collectively we not only survive, but prosper in a world as complex as our own. The key is “probably approximately correct” algorithms, a concept Valiant developed to explain how effective behavior can be learned. The model shows that pragmatically coping with a problem can provide a satisfactory solution in the absence of any theory of the problem. After all, finding a mate does not require a theory of mating. Valiant’s theory reveals the shared computational nature of evolution and learning, and sheds light on perennial questions such as nature versus nurture and the limits of artificial intelligence. Offering a powerful and elegant model that encompasses life’s complexity, Probably Approximately Correct has profound implications for how we think about behavior, cognition, biological evolution, and the possibilities and limits of human and machine intelligence.

User’s Reviews

Reviews from Amazon users which were colected at the time this book was published on the website:

⭐Edit: This review is too long as I tried to summarize the main ideas in the book as well. This is in the middle of the review. If you are looking for a shorter review the first three and the last paragraphs should suffice.The punchline of this book is perhaps: “Changing or increasing functionality of circuits in biological evolution is a form of computational learning”; although it also speaks of topics other than evolution, the underlying framework is of the Probably Approximately Correct model from the theory of Machine Learning, from which the book gets its name.I had first heard of this explicit connection between Machine Learning and Evolution in 2010 and have been quite fascinated by it since. It must be noted, however, that similar ideas have appeared in the past. It won’t be incorrect to say that usually they have been in the form of metaphor. It is another matter that this metaphor has generally been avoided for various reasons in scientific discourse. When I first heard about the idea it immediately made sense and like all great ideas, in hindsight looks completely obvious. Ergo, I was quite excited to see this book and preordered it months in advance.This book is basically a popular science version and expansion of the ideas on the matter that appeared in a J-ACM article titled “Evolvability” in 2007. If you are looking for a technical coverage look elsewhere. Infact a monograph on the recently developing COLT based approaches to evolution does not exist yet (this gap needs to be filled!). I had been thinking that this book might be an informal plug into this gap and hence I have to say that I was rather disappointed that it wasn’t. Don’t get me wrong, the book is not bad, infact pretty good. Just that somebody with enough background in Learning might not be able to get enough out of it. It might however be a good starting book for those interested in these ideas but without much background in both subjects.—Before attempting to sketch a skiagram of the main content of the book: One of the main subthemes of the book, constantly emphasized is to look at computer science as a kind of an enabling tool to study natural science. This is oft ignored, perhaps because of the reason that CS curricula are rarely designed with any natural science component in them and hence there is no impetus for aspiring computer scientists to view them from the computational lens. On the other hand, the relation of computer science with mathematics has become quite well established. As a technology the impact of Computer Science has been tremendous. All this is quite remarkable given the fact that just about a century ago the notion of a computation was not even well defined. Unrelated to the book: More recently people have started taking the idea of digital physics (i.e. physics from a solely computable/digital perspective) seriously. But in the other natural sciences its usage is still woeful. Valiant draws upon the example of Alan Turing as a natural scientist and not just as a computer scientist to make this point. Alan Turing was more interested in natural phenomenon (intelligence, limits of mechanical calculation, pattern formation etc) and used tools from Computer Science to study them, a fact that is evident from his publications. That Turing was trying to understand natural phenomenon was remarked in his obituary by Max Neumann by summarizing the body of his work as: “the extent and the limitations of mechanistic explanations of nature”.–The book begins with a delightful and quite famous quote by John von Neumann (through this paragraph I also discovered the context to the quote). This paragraph also adequately summarizes the motivation for the book very well:”In 1947 John von Neumann, the famously gifted mathematician, was keynote speaker at the first annual meeting of the Association for Computng Machinery. In his address he said that future computers would get along with just a dozen instruction types, a number known to be adequate for expressing all of mathematics. He went on to say that one need not be surprised at this small number, since 1000 words were known to be adequate for most situations in real life, and mathematics was only a small part of life, and a very simple part at that. The audience responded with hilarity. This provoked von Neumann to respond: “If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is” Though counterintuitive, von Neumann’s quip contains an obvious truth. Einstein’s theory of general relativity is simple in the sense that one can write the essential content on one line as a single equation. Understanding its meaning, derivation, and consequences requires more extensive study and effort. However, this formal simplicity is striking and powerful. The power comes from the implied generality, that knowledge of one equation alone will allow one to make accurate predictions about a host of situations not even connected when the equation was first written down. Most aspects of life are not so simple. If you want to succeed in a job interview, or in making an investment, or in choosing a life partner, you can be quite sure that there is no equation that will guarantee you success. In these endeavors it will not be possible to limit the pieces of knowledge that might be relevant to any one definable source. And even if you had all the relevant knowledge, there may be no surefire way of combining it to yield the best decision. This book is predicated on taking this distinction seriously […]”In a way, aspects of life as mentioned above appear theoryless, in the sense that there seems to be no mathematical or scientific theory like relativity for them. Something which is quantitative, definitive and short. Note that these are generally not “theoryless” in the sense that there exists no theory at all since obviously people can do all the tasks mentioned in a complex world quite effectively. A specific example is of how organisms adapt and species evolve without having a theory of the environment as such. How can such coping mechanisms come into being in the first place is the main question asked in the book.Let’s stick to the specific example of biological evolution. Clearly, it is one of the central ideas in biology and perhaps one of the most important theories in science that changed the way we look at the world. But inspite of its importance, Valiant claims (and correctly in my opinion) that evolution is not understood well in a quantitative sense. Evidence that convinces us of its correctness is of the following sort: Biologists usually show a sequence of evolving objects; stages, where the one coming later is more complex than the previous. Since this is studied mostly via the fossil record there is always a lookout for missing links between successive stages. Darwin had remarked that numerous successive paths are necessary – that is, if it was not possible to trace a path from an earlier form to a more complicated form then it was hard to explain how it came about. But again, as Valiant stresses, this is not really an explanation of evolution. It is more of an “existence proof” and not a quantitative explanation. That is, even if there is evidence for the existence of a path, one can’t really say that a certain path is likely to be followed just because it exists.Related to this, one of the first questions that one might ask, and indeed was asked by Darwin himself: Why has evolution taken as much time as it has? How much time would have sufficed for all the complexity that we see around us to evolve? This question infact bothered Darwin a lot in his day. In On the Origins of Species he originally gave an estimate of the Earth’s age to be at least 300 million years, implying indirectly, that there was enough time. This estimate was immediately thrashed by Lord Kelvin, one of the pre-eminent British physicists of the time, who estimated the age of the Earth to be only about 24 million years. This caused Darwin to withdraw the estimate from his book. However, this estimate greatly worried Darwin as he thought 24 million years just wasn’t enough time. To motivate on the same theme Valiant writes the following: “[…] William Paley, in a highly influential book, Natural Theology (1802) , argued that life, as complex as it is, could not have come into being without the help of a designer. Numerous lines of evidence have become available in the two centuries since, through genetics and the fossil record, that persuade professional biologists that existing life forms on Earth are indeed related and have indeed evolved. This evidence contradicts Paley’s conclusion, but it does not directly address his argument. A convincing direct counterargument to Paley’s would need a specific evolution mechanism to be demonstrated capable of giving rise to the quantity and quality of the complexity now found in biology, within the time and resources believed to have been available. […]”A specific, albeit more limited version of this question might be: Consider the human genome, which has about 3 billion base pairs. Now, if evolution is a search problem, as it naturally appears to be, then why did the evolution of this genome not take exponential time? If it would have taken exponential time then clearly such evolution could not have happened in any time scale since the origin of the earth. Thus, a more pointed question to ask would be: What circuits could evolve in sub-exponential time (and on a related note, what circuits are evolvable only in exponential time?). Given the context, the idea of thinking about this in circuits might seem a little foreign. But on some more thought it is quite clear that the idea of a circuit is natural when it comes to modeling such systems (at least in principle). For example: One might think of the genome as a circuit, just as how one might think of the complex protein interaction networks and networks of neurons in the brain as circuits that update themselves in response to the environment.The last line is essentially the key idea of adaptation, that entities interact with the environment and update themselves (hopefully to cope better) in response. But the catch is that the world/environment is far too complex for simple entities (relatively speaking), with limited computational power, to have a theory for. Hence, somehow the entity will have to cope without really “understanding” the environment (it can only be partially modeled) and improve their functionality. The key thing to pay attention here is the interaction or the interface between the limited computational entity in question and the environment. The central idea in Valiant’s thesis is to think of and model this interaction as a form of computational learning. The entity will absorb information about the world and “learn” so that in the future it “can do better”. A lot of Biology can be thought of as the above: Complex behaviours in environments. Wherein by complex behaviours we mean that in different circumstances, we (or alternately our limited computational entity) might behave completely differently. Complicated in the sense that there can’t possibly be a look up table for modeling such complex interactions. Such interactions-responses can just be thought of as complicated functions e.g. how would a deer react could be seen as a function of some sensory inputs. Or for another example: Protein circuits. The human body has about 25000 proteins. How much of a certain protein is expressed is a function depending on the quantities of other proteins in the body. This function is quite complicated, certainly not something like a simple linear regression. Thus there are two main questions to be asked: One, how did these circuits come into being without there being a designer to actually design them? Two, How do such circuits maintain themselves? That is, each “node” in protein circuits is a function and as circumstances change it might be best to change the way they work. How could have such a thing evolved?Given the above, one might ask another question: At what rate can functionality increase or adapt under the Darwinian process? Valiant (like many others, such as Chaitin.) comes to the conclusion that the Darwinian evolution is a very elegant computational process. And since it is so, with the change in the environment there has to be a quantitative way of saying how much rate of change can be kept up with and what environments are unevolvable for the entity. It is not hard to see that this is essentially a question in computer science and no other discipline has the tools to deal with it.In so far that (biological) interactions-responses might be thought of as complicated functions and that the limited computational entity that is trying to cope has to do better in the future, this is just machine learning! This idea, that changing or increasing functionality of circuits in biological evoution is a form of computational learning, is perhaps very obvious in hindsight. This (changing functionality) is done in Machine Learning in the following sense: We want to acquire complicated functions without explicitly programming for them, from examples and labels (or “correct” answers). This looks at exactly at the question at how complex mechanisms can evolve without someone designing it (consider a simple perceptron learning algorithm for a toy example to illustrate this). In short: We generate a hypothesis and if it doesn’t match our expectations (in performance) then we update the hypothesis by a computational procedure. Just based on a single example one might be able to change the hypothesis. One could draw an analogy to evolution where “examples” could be experiences, and the genome is the circuit that is modified over a period of time. But note that this is not how it looks like in evolution because the above (especially drawing to the perceptron example) sounds more Lamarckian. What the Darwinian process says is that we don’t change the genome directly based on experiences. What instead happens is that we make a lot of copies of the genome which are then tested in the environment with the better one having a higher fitness. Supervised Machine Learning as drawn above is very lamarckian and not exactly Darwinian.Thus, there is something unsatisfying in the analogy to supervised learning. There is a clear notion of a target in the same. Then one might ask, what is the target of evolution? Evolution is thought of as an undirected process. Without a goal. This is true in a very important sense however this is incorrect. Evolution does not have a goal in the sense that it wants to evolve humans or elephants etc. But it certainly does have a target. This target is “good behaviour” (where behaviour is used very loosely) that would aid in the survival of the entity in an environment. Thus, this target is the “ideal” function (which might be quite complicated) that tells us how to behave in what situation. This is already incorporated in the study of evolution by notions such as fitness that encode that various functions are more beneficial. Thus evolution can be framed as a kind of machine learning problem based on the notion of Darwinian feedback. That is, make many copies of the “current genome” and let the one with good performance in the real world win. More specifically, this is a limited kind of PAC Learning. If you call your current hypothesis your genome, then your genome does not depend on your experiences. Variants to this genome are generated by a polynomial time randomized Turing Machine. To illuminate the difference with supervised learning, we come back to a point made earlier that PAC Learning is essentially Lamarckian i.e. we have a hidden function that we want to learn. One however has examples and labels corresponding to this hidden function, these could be considered “queries” to this function. We then process these example/label pairs and learn a “good estimate” of this hidden function in polynomial time. It is slightly different in Evolvability. Again, we have a hidden “ideal” function f(x). The examples are genomes. However, how we can find out more about the target is very limited, since one can empirically only observe the aggregate goodness of the genome (a performance function). The task then is to mutate the genome so that it’s functionality improves. So the main difference with the usual supervised learning is that one could query the hidden function in a very limited way: That is we can’t act on a single example and have to take aggregate statistics into account.Then one might ask what can one prove using this model? Valiant demonstrates some examples. For example, Parity functions are not evolvable for uniform distribution while monotone disjunctions are actually evolvable. This function is ofcourse very non biological but it does illustrate the main idea: That the ideal function together with the real world distribution imposes a fitness landscape and that in some settings we can show that some functions can evolve and some can not. This in turn illustrates that evolution is a computational process independent of substrate.In the same sense as above it can be shown that Boolean Conjunctions are not evolvable for all distributions. There has also been similar work on real valued functions off late which is not reported in detail in the book. Another recent work that is only mentioned in passing towards the end is the study of multidimensional space of actions that deal with sets of functions (not just one function) that might be evolvable together. This is an interesting line of work as it is pretty clear that biological evolution deals with the evolution of a set of functions together and not functions in isolation.—I think the book is pretty decent. Although it might be disappointing if you went in looking for a more technical treatment; especially if you come from a learning background. Like I mentioned at the onset of this (long) review: Clearly this book is aimed at the non expert/relatively uninitiated. To me personally, this recent area of work that studies evolution through the lens of computational learning is incredibly interesting and intellectually stimulating. Precisely for this reason, I had been hoping for more. On criticisms: I have noticed substantial critcism by some biologists of some of the main ideas in the book (not just writing style etc). Some of the criticism might be valid but quite some of it is phrased as: “Valiant needs to understand biology better”. I think remarks of this nature are more due to the fact that (most, not all) biologists do not have the computational and algorithmic lens to look at certain problems in an abstract setting. Yes, I am saying that the problem is with them and not Valiant. Criticisms about writing are another matter entirely and orthogonal to the critcisms of the nature mentioned above. In my opinion some of these ideas that started out in 2007 (incipient versions can be seen in the work of John Maynard Smith decades ago. see “Evolution of Sex”.), and also presented informally in this book will have a lasting impact. On other criticisms: I have had some arguments about the main ideas in the book over the past couple of years with some biologist friends who take the usage of “learning” to mean that what is implied is that evolution is a directed process. It would have been great if the book would have spent more time on this particular aspect. Also, the book explicitly states that it is about quantitative aspects of evolution and has nothing to do with speciation, population dynamics and other rich areas of study. It ONLY deals with what Valiant says is the essence of evolution, which is an elegant and abstract computational process. However, I have already seen some criticism of the book on this premise. So in this sense I believe that these criticisms are unfair.As far as I am concerned, as an admirer of Prof. Leslie Valiant’s range and quality of contributions, I would have preferred if the book went into more depth. Just to have a semi-formal monograph on the study of evolution using the tools of PAC Learning right from the person who initiated this area of study. However this is just a selfish consideration.

⭐Probably Approximately Correct is an attempt to explore what might go into the computation undertaken in evolutionary and learning processes. It is mathematical in nature and argument but this book is from a very high level and uses more symbolic arguments rather than specific mathematical ones. Though readable there is a lot of the material which is really tough to digest with the writing quite terse at times. I think there is a lot of depth in the book that can be appreciated by reading slowly and with consideration such that one can get a sense of what is going on in the study of intelligence and learning, from a formal computational standpoint and how it might relate to humanity. One also gets a sense of the true difficulty in the programming of intelligence and an appreciation of the breadth of the meaning of intelligence.The book assumes no prior knowledge but I think if you are unfamiliar with theories of computation it gets very difficult to follow very quickly. In any case the author starts out by describing prediction and adaptation and quickly gets into the theory of computation. He discusses computability from the perspective of Turing and goes into the completeness of the framework. It discusses P/NP issues and the need for his “ecorithm” concept to be in the space of polynomial time algorithms. This is required for the self evident reason that we’ve evolved on such a time scale. He ends with an introduction to the Perceptron Algorithm and discusses how the simple adaptive algorithm can have strong properties that translate to how people can learn.The author gets into learning and evolution in the two next chapters. Each are separate but ultimately very connected. Learning is considered more local in time and self adapting in nature such that the greater fitness of learning translates into the evolutionary timescale. The author discusses the concept of probably approximately correct algorithms and how they can function in a variable environment. The author discusses how algorithms can be seen as ways to enhance prediction by minimizing errors if there is regularity in the environment. This is all kind of fuzzy to be honest as its not formalized mathematically but its described as though it can be. The author discusses teaching and learning as well and how teaching is different from programming. A teacher can will have imperfect knowledge of the student but can still teach them whereas a programmer needs much more complete knowledge of the program to improve it). The author moves into evolution and discusses the computational needs for evolution to have arrived where we are today. In particular the author gets into some big picture ideas on computation within evolution and into the time scale and the fitness functions within the mathematical space that the author is considering. This is done in descriptive terms rather than in a formulaic sense.The author moves onto syllogism vs induction. Evolutionary learning is considered within the space of theoryless learning, ie we use heuristics to recognize patterns and act and adapt as a function of those heuristics rather than from a deduced bottom up construction of reality. With this backdrop the author argues our learning process is based on a largely theoryless base. The challenges of reasoning in the theoryless space include complexity, brittleness and semantics. The fact that we can only keep in our immediate short term memory/focus 7 ideas (+/- 2) is given to remind us of our limited field of vision we possess when considering problems in general.The author moves from setting the stage to formulating the thesis- humans are manifestations of these ecorithms that he has been describing. He discusses cognitive science and the biases we have and how our contextual truths will never translate perfectly. At the same time our innate ecorithm machinery means some does translate well between us and computer science/machine learning. Bridging the computational benefits of computers with human pattern recognition can enhance our functionality for a broad class of problem solving. Here we get a sense of the difficulty in programming intelligence. We don’t know the functional forms that go into the learning that we are able to do, hence to program them is currently unfeasible. At the same time progress has been made in narrow areas and those do give some insight into some basic forms of machine learning.All in all i got some interesting perspective from this book but its really tough to follow closely. I think if you know a lot about algorithms then talking about the algorithms alluded to and what they look like in functional form makes it easier to appreciate the space of outcomes that are possible with such algorithms. Seeing graphs of how learning algorithms can solve simple puzzles through trial and error might have been helpful rather than the 30k foot view. Through reading this, one gets a sense of human complexity but also on how maybe there is a simplicity to it as well. I recommend reading

⭐to get a sense of how complicated the brain is, as to appreciate the difficulty in writing algorithms to describe it. I’m no expert in either what the author does or what the author of Connectome does, so i might be talking apples to oranges. Either way, i recommend the book, but prepare to be confused in many places.

⭐In summary, I found this book to be full of powerful and exciting ideas, so worth the 5*’s. But it’s not a perfect book. I found it quite hard going. I felt that he had in mind as his audience someone rather like himself – a top mathematician who is totally versed in the subject. He rarely loosens up and engages with the laity, like me, so I had to do more work (not a bad thing, necessarily).Leslie Valiant sets out to show that it is computationally feasible for life to evolve its amazingly complex solutions to problems of survival, given the time (3.5bn years) and resource available. He shows, using a lot of maths concepts, that at the heart of evolution and learning there must be a relatively simple computation performed in a relatively simple processor that enables life to learn from examples and ultimately create sophisticated solutions that work (or persist). He explains that unlike computer-based computations, which are logical and algorithmic, life’s computations are ‘theory-less’ in that they cannot apply generally outside the domain they have been learned in; they work tolerably in those domains – well enough for survival; they get better (fewer errors) when needed by adding learning from more examples (they adapt) – so they are robust in that they can be improved if needed and fail gracefully; the solutions aren’t necessarily logical but they are powerful because the computation can powerfully chain solutions in a form of reasoning. This model can apply not just to evolution of persistent life forms but also to learning persistent ideas (knowledge). He calls these algorithms, ecorithms.Along the way he offers all sorts of delightful insights, such as that life works on problems as if it was ‘decrypting’ the key to the answer.Like many mathematicians, Valiant wants to show us the working before telling us the answer. I’d suggest reading this book back to front. Start with the Glossary to understand the language, then look at the notes to get an idea of the context, then go to section 7.7. where he finally reveals the exciting answer on how computation is done by evolution. Now you are ready to be told the story.

⭐Before going any further I must declare an interest as I went to school with the author, though that was 55 years ago and we have not kept in touch.Despite difficulties in understanding quite a bit of the book I have, in common with some other reviewers, given it 5 stars for the various fascinating parts that I could follow.The book covers a variety of topics including the Turing machine and complexity theory but I take the two main subjects to be computer learning (or Artificial Intelligence), and a theory of evolution based around genetic learning.Humans learn and can perform complex operations without having any knowledge of an underlying theory of how something works – we do not need defined algorithms. Computers however need defined rules before they can do anything. Professor Valiant’s method of PAC (see the book title) is a way of looking at learning without having an exact formula or algorithm to get to an answer. I broadly understood the concept of PAC but can’t say I got any idea of how it could actually be used for computer learning.Moving on from computers Professor Valiant applies PAC to the method of evolution.Darwin’s Natural Selection, i.e. the stronger of random mutations winning out, has been challenged by Intelligent Design where some external agent, whether alien or God has influenced the development of DNA.Professor Valiant maintains that the probability of the creation of DNA and subsequent evolution happening by chance is not mathematically justifiable.He proposes that the evolution of DNA is controlled neither by chance nor by external design but by a learning feedback method he calls ecorithms, and he applies PAC to this.

⭐Some of the comments which complain about style are probably fair. This is what can happen if a book is written by a professional, rather than a professional author. On the other hand, I found this to be one of the most stimulating books I’ve read all year. I do some machine learning for a living, but there’s a difference between understanding how some algorithms work, and understanding why it is even possible to learn in the first place. This book is great at generating “aha” moments. Books that do that are rare, hence my five stars. However, be prepared to go elsewhere if you want to follow up on those insights. This is not an exhaustive textbook on PAC theory.

⭐Recently an idea of computing nature started to take prominent place among philosophers and theoreticians of computing. This is a highly informative book by leading computer scientist framing the topic of computing nature into his central thesis of PAC (Probably Approximately True) learning algorithms. Learning (that is ability of adequate adaptation) is central idea and it is based on the awareness of the physical constraints learning system has – it is never infinite or equipped with perfect information.Valiant coined the term “ecorithms” for the computational rules which help a system to learn through interactions with the environment. The book relates adaptation with learning (PAC), evolution and cognition in a common naturalistic computational framework. Recommended to anyone interested in how nature works and how its functioning relies on computational strategies.

⭐Although the Author didn’t go into detail about all the advanced learning algorithms that we humans use, his theme that they were all Probably Approximately Correct came across very well. A very good case for soft AI, and soft computing by extension.

Keywords

Free Download Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World 1st Edition in PDF format
Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World 1st Edition PDF Free Download
Download Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World 1st Edition PDF Free
Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World 1st Edition PDF Free Download
Download Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World 1st Edition PDF
Free Download Ebook Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World 1st Edition