Math prerequisites for understanding LW stuff

cousin_it4 Oct 2010 11:30 UTC

26 points

Scholarship & Learning Logic & Mathematics

I just got a PM with this question: “What would be the minimum intellectual investment necessary to be able to fruitfully take part in the discussion of decision theory on LW?” This is not the first time I’ve been asked that. Our new discussion section looks like the perfect place to post my answer:

1) Learn enough game theory to correctly find Nash equilibria in 2x2 games all by yourself.

2) Learn enough probability theory to correctly solve Monty Hall, Monty Fall, Monty Crawl all by yourself.

3) Learn enough programming to write a working quine (in any language of your choice) all by yourself.

4) Learn enough logic to correctly solve the closing puzzle from Eliezer’s cartoon guide.

Then you’re all set. Should take you a few days if you’ve studied math before, a few weeks if you haven’t. No special texts needed beyond Wikipedia and Google.

What links here?

cousin_it4 Oct 2010 11:30 UTC

26 points

16 comments LW link Archive

Scholarship & Learning Logic & Mathematics

XiXiDu 4 Oct 2010 12:28 UTC
28 points
A list capturing all background knowledge you might ever need for LW.

(Updated: 2010-10-08)

This list assumes a previous level of education above elementary schooling but less than secondary school. If you start with Khan Academy followed by BetterExplained then with the help of Google and Wikipedia you should be able to reach a level of education that allows you to start reading the LessWrong Sequences.

Nevertheless, before you start off you should read and memorize the Twelve Virtues of Rationality. Not only is scholarship just one virtue but you’ll also be given a list of important fields of knowledge that anyone who takes LessWrong seriously should study:

It is especially important to eat math and science which impinges upon rationality: Evolutionary psychology, heuristics and biases, social psychology, probability theory, decision theory.

Mathematics:

Basics
- The Khan Academy (World-class education for free (1800+ videos).)
- Just Math Tutotrials (FREE math videos for the world!)
- BetterExplained (There’s always a better way to explain a topic.)
- Interactive Mathematics Miscellany and Puzzles
- Free Mathematics eBooks
- A Guide to Bayes’ Theorem – A few links (An extensive list of links to tutorials on Bayesian probability.)
- Steven Strogatz on the Elements of Math (A very basic introduction to mathematics.)
- http://math.stackexchange.com/ (Q&A for people studying math at any level)
- http://www.wolframalpha.com (Check your math!)
Logic
Game Theory
- http://en.wikipedia.org/wiki/Game_theory
- http://en.wikipedia.org/wiki/Nash_equilibrium
Foundations
Programming:

Programming knowledge is not mandatory for LessWrong but you should however be able to interpret the most basic pseudo code as you will come across various snippets of code in discussions and top-level posts outside of the main sequences.

Python
- http://python.org/
- http://learnpythonthehardway.org/home (Free)
- A Byte of Python (Free)
- Python for Software Design
- Learning Python, 3rd Edition
Haskell
- http://www.haskell.org/
- http://hackage.haskell.org/platform/
- http://www.haskell.org/haskellwiki/Learn_Haskell_in_10_minutes
- http://learnyouahaskell.com/chapters
- The Haskell Road to Logic, Maths and Programming
General
- Structure and Interpretation of Computer Programs
- How to Design Programs (An Introduction to Computing and Programming)
- http://projecteuler.net/ (Learn programming and math by solving problems)
- The FTP Site (Functional Programming)
Computer sciences (General Introduction):

One of the fundamental premises on LessWrong is that a universal computing device can simulate every physical process and that we therefore should be able to reverse engineer the human brain as it is fundamentally computable. That is, intelligence and consciousness are substrate independent.
- Marvin Minsky, Computation Finite and Infinite Machines
- Michael Sipser, Introduction to the Theory of Computation
- Charles Petzold, The Hidden Language of Computer Hardware and Software
- Michael L. Scott, Programming Language Pragmatics
Machine Learning:

Not essential but an valuable addition for anyone who’s more than superficially interested in AI and machine learning.
Miscellaneous:

Not essential but a good preliminary to reading LessWrong and in some cases mandatory to be able to make valuable contributions in the comments. Many of the concepts in the following works are often mentioned on LessWrong or the subject of frequent discussions.
- An Introduction to Kolmogorov Complexity and Its Applications
- Bayesian Reasoning and Machine Learning (Free)
- Darwin’s Dangerous Idea, Daniel Dennett (Evolution)
- The Language Instinct, Steven Pinker (Linguistics)
- The Road to Reality (Physics)
- Good and Real (Rationality & Decision Theory)
- A New Kind of Science (Cellular automaton) (Note: I was told to be careful about this book. Rather than reading it as an introduction to cellular automata you might just check out the Wikipedia page on Conway’s Game of Life)
- Gödel, Escher, Bach: An Eternal Golden Braid
Keywords:

Concepts and other fields of knowledge you should at least have a rough grasp of to be able to follow subsequent discussions in the comments on LessWrong.
- Cognitive biases, common misconceptions, and fallacies.
- Kolmogorov complexity
- Solomonoff induction
- Utility theory
- Utilitarianism
- Decision Theory (Timeless Decision Theory)
- Bayesian Probability Theory (Bayesian approach) vs. Frequentist Probability Theory (Frequentist approach)
- AI-Foom Debate
- Paperclip maximizer
- Catastrophic risks from artificial intelligence
- Coherent Extrapolated Volition (CEV)
- Simulation Argument
- Anthropic Principle
The Quantum Physics Sequence

Complex Numbers:
Complex Numbers @ Khan Academy:
Note: This list is a work in progress. I will try to constantly update and refine it.
What links here?
- jsalvatier's comment on Learning the foundations of math by jsalvatier (24 Oct 2010 19:40 UTC; 1 point)
- satt 5 Oct 2010 0:20 UTC
  4 points
  Parent
  A disclaimer on Wolfram’s A New Kind of Science: quite a few of the scientists who reviewed it weren’t particularly enthusiastic. See for example Cosma Shalizi’s review (of special interest to Less Wrong readers, perhaps, for the side comment on Jaynes towards the end! Edit: or maybe not; Shalizi’s linked arXiv paper is probably wrong as p4wnc6 explains below). This webpage collects a lot of other reviews of the book as well.
  What links here?
  - XiXiDu's comment on Math prerequisites for understanding LW stuff by cousin_it (4 Oct 2010 12:28 UTC; 28 points)
  - How to better understand and participate on LW by XiXiDu (8 Oct 2010 16:11 UTC; 8 points)
  - [deleted] 7 May 2012 2:46 UTC
    3 points
    Parent
    It seems Shalizi’s comments on Jaynes have been somewhat refuted. The paper claiming that subjective Bayes induces a backward arrow of time fails to account for the entropy generation inside the mind of the agent forming beliefs about the world. It requires energy to convert observations into states of belief, and hence increases entropy. Shalizi’s argument does not account for this and (like many puffed-up “rebuttals” of Jaynes) fails for an essentially trivial reason. Shalizi is a great writer and thoughtful researcher, but just got things very very wrong on that occasion.
  - XiXiDu 5 Oct 2010 8:22 UTC
    0 points
    Parent
    Thanks, I read it does a good job on cellular automata. And since that topic is mentioned quite often on LW I thought it would be a good addition to a extensive list capturing all background knowledge you might ever need for LW.
    
    ETA Updated
- cousin_it 4 Oct 2010 12:52 UTC
  3 points
  Parent
  Add a backslash before the closing paren in the last link, Markdown choked on it. I’ll delete my comment afterward.
- XiXiDu 4 Oct 2010 13:33 UTC
  2 points
  Parent
  I added a logic section now. For what I have no links is Game Theory. At least I don’t know of any introductory works, free or else...but do you really need that for LW? What I noticed that is missing from the OP is knowledge of complex numbers since you’ll need that to understand the The Quantum Physics Sequence.
  
  Complex Numbers:
  Complex Numbers @ Khan Academy:
Vladimir_M 6 Oct 2010 0:27 UTC
13 points

Should take you a few days if you’ve studied math before, a few weeks if you haven’t.

Do you seriously believe that someone who has never studied math before can understand Loeb’s theorem and start solving puzzles in mathematical logic after a few weeks of study?! I can imagine that someone very smart could figure out (1)-(3) from scratch fairly quickly, but (4) strikes me as a much harder step. Also, mathy LW discussions often touch on quantum mechanics, various things in computability theory, and sundry other stuff where I don’t see any easy way up (especially for QM).

In any case, here’s a neat test for those who’d like to tackle step (1):
http://www.rasmusen.org/GI/_stest1/selftest1.htm
- cousin_it 7 Oct 2010 12:45 UTC
  0 points
  Parent
  I don’t think (4) is much harder than (3). Someone who’s never programmed before will find (3) very hard. Still, a few weeks of dedicated work should do it. From my experience teaching math to kids, I think it’s actually more difficult to go from zero to (1) and (2) than to go from those to (4), because the hard part is learning how to think rigorously at all.
  
  There is no serious descussion of quantum mechanics (or physics in general) on LW. I’d be glad if there was. Likewise, there’s almost no serious discussion of statistical inference (frequentism, Bayesianism and related topics), though we do have a handful of people who understand it.
  - Vladimir_M 7 Oct 2010 19:27 UTC
    6 points
    Parent
    cousin_it:
    
    From my experience teaching math to kids, I think it’s actually more difficult to go from zero to (1) and (2) than to go from those to (4), because the hard part is learning how to think rigorously at all.
    
    That sure depends on what we consider to be “zero”!
    
    I do know some very smart people for whom (1)-(3) would be a breeze, but who couldn’t prove a theorem if their lives depended on it. (In my experience, lots of such people can be found among programmers and engineers.) I have the impression that quite a few people on LW are in a not too dissimilar position, in the sense that they could easily harness their general intelligence to develop the right intuitions for solving problems of the sorts (1)-(3) reliably, but training themselves for formal math would be a much harder step.
    
    Maybe I’m also biased due to my own position. I can easily pass the tests (1)-(3) (out of curiosity, I just tried writing a quine in C—I thought of the basic idea in about 5 minutes, and it took me 10-15 min. more to sort out the mess with the escape characters). But although I had a decent knowledge of the basics of math foundations some years ago (to the point where I was proving theorems in exams in graduate courses), scraping the rust off of it to the point where I could constructively contribute to the discussions here would require a significant time investment (which I still hope to do as time permits).
    
    There is no serious descussion of quantum mechanics (or physics in general) on LW. I’d be glad if there was.
    
    Lots of discussions here touch on MWI and make MWI-related assumptions. While one can grasp the basic idea of MWI without knowing the actual math of the quantum theory, such knowledge is pretty pointless, since it basically involves taking a controversial view on pure faith. (I am familiar with the basics of QM, but I don’t think my knowledge is still anywhere near the level where it would make sense to stick my head out with judgments about such things.)
    
    By the way, there is an interesting ongoing physics discussion, just in case you missed it:
    http://lesswrong.com/lw/2sl/the_irrationality_game/2qiu
    - cousin_it 8 Oct 2010 8:32 UTC
      0 points
      Parent
      Thanks for the link! Of course, I can’t understand any of it :-)
    - XiXiDu 8 Oct 2010 12:13 UTC
      −1 points
      Parent
      
      While one can grasp the basic idea of MWI without knowing the actual math of the quantum theory, such knowledge is pretty pointless, since it basically involves taking a controversial view on pure faith.
      
      Are you going to claim that you believe into AI going FOOM based on the actual math? Why would you care about how founded MWI is if you accept the basic premise of risk from AI to an extent that you donate to some institute with Singularity in its name when not even gravitational singularities are proven beyond the point that people would ground a movement around them...
Vladimir_M 6 Oct 2010 0:52 UTC
9 points
Also, here are some excellent online resources for those wiling to plunge into mathematical logic, math foundations, and computability theory:
- A two-part online text by Karlis Podnieks: Introduction to Mathematical Logic and What is Mathematics: Gödel’s Theorem and Around. Written in ugly plain text, and with some bits still incomplete, but on the upside, extremely well-written and probably as readable as a rigorous text on this topic could ever hope to be. (The text is also peppered with the author’s philosophical opinions, but you can skip those if you don’t like them.)
- Stephen Cook’s lecture notes in computability and logic. A rigorous build-up to Goedel’s incompleteness theorems with minimal background knowledge assumed, which introduces the basics of mathematical logic and computability theory on the way. The text is very readable and surprisingly short considering the whole range of topics covered.
This could take a while to go through, but despite cousin_it’s optimistic estimates, I would say that working through at least one of these texts would be necessary before you can discuss topics such as Loeb’s theorem with any real understanding. If you’ve never studied math, or if you’ve studied it only in a very applied and non-theoretical way, the greatest problem will be getting used to the necessary way of thinking.
- cousin_it 8 Oct 2010 0:45 UTC
  3 points
  Parent
  I usually recommend Gödel Without Tears. At least one person has used it to learn logic by my suggestion. Took them a couple weeks.
XiXiDu 4 Oct 2010 12:25 UTC
1 point
Learn mathematics online for free:
Programming: Python
- http://python.org/
- http://learnpythonthehardway.org/home
Haskell
General
Computer sciences (General Introduction):
- Marvin Minsky, Computation Finite and Infinite Machines
- Michael Sipser, Introduction to the Theory of Computation
- Charles Petzold, The Hidden Language of Computer Hardware and Software
- Michael L. Scott, Programming Language Pragmatics
Machine Learning:
Miscellaneous:
- An Introduction to Kolmogorov Complexity and Its Applications
- Bayesian Reasoning and Machine Learning (Free)
- Darwin’s Dangerous Idea, Daniel Dennett
- The Language Instinct, Steven Pinker
Keywords: Kolmogorov complexity Solomonoff induction Utility theory Decision Theory#Sequence) (Timeless Decision Theory)
Stuart_Armstrong 5 Jan 2011 12:31 UTC
0 points
Thanks for this list, it’s most useful.

But one tricky thing about

4) Learn enough logic to correctly solve the closing puzzle from Eliezer’s cartoon guide. is that he is asking one to find a flaw in a proof of a true statement. The proof is indeed flawed (one of the derivability conditions doesn’t have the required properties), but statements such as “there is no proof of X” imply “PA is consistent” and hence “X”.
xamdam 7 Oct 2010 20:57 UTC
0 points
Good post, would be nice to know which posts/sequences each topic is related to, so they can be read after