Borges, Haskell, Euler

In one of my favorite Borges stories, he describes the imaginary people of Tlön who speak a language that has no nouns.  They have only impersonal verbs, adverbs, and prepositions.  Instead of saying, 'The moon rose above the river,' they would say something like, 'Upward, behind the onstreaming it mooned.'  The story explores the ways in which language shapes what we do and how we think.  Borges writes, 'For the people of Tlön, the world is not an amalgam of objects in space; it is a heterogeneous series of independent acts.'  This raises the question: how would your life be different if you didn't have a word for 'you' or 'I'?

You don't have to merely ponder this if you learn a functional language like Haskell (named after mathematician Haskell Curry).  I've taken a deep dive into Haskell, though I still feel like one of the early explorers trying to understand Tlön.  If you're used to thinking in terms of 'objects in space'--that is, if you mostly work in object-oriented languages--Haskell is very weird at first.  You'll have to start thinking in terms of functions.  Even basic units, like the number 5, are really functions that return the value 5 and which can then be passed to other functions.

Check out this implementation of the Quicksort algorithm, taken from Miran Lipovača's awesomely-named book Learn You a Haskell for Great Good!:

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted

This code declares a function quicksort, which takes a list and returns a list of things that can be ordered.  It recursively calls itself, so the base case is an empty list.  It grabs the first item from the list and uses it as the pivot to generate two other lists of all items greater and smaller that it.  Then it concatenates and returns the sorted sublists.  Voila!

You might wonder why it's useful to learn a language like Haskell.  I personally haven't seen any production Haskell code, though you can find some cases of it.  I wanted to learn Haskell because it is a purely functional language, and I thought it would help me better understand some of the ways functional programming is creeping into OOP.  For example, Java 8 will have closures, the Clojure language is gaining popularity, and C# makes heavy use of lambdas and extension methods in LINQ.

I have also heard that learning Haskell will make you a better programmer.  I do think it's hard to really know any language unless you know what else is out there, just like I think it's a bad idea to maintain a belief in something if you don't consider other beliefs, whether it's politics, religion, or anything else where reasonable people disagree.  However, I'm not sure what Haskell or other functional languages teach besides recursion.  You really have to be comfortable with recursion to do any amount of functional programming.  For example, you could write a function to check if a list or string of characters is a palindrome in the following way:

isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome ([]) = True
isPalindrome ([x]) = True
isPalindrome (x:y) = 
    if x == z && isPalindrome w then True else False
    where z = last y
          w = init y

Haskell is great for problems where you can break a task into a series of mathematical equivalences.  It's hard for me to imagine trying to solve Project Euler problems without Haskell.  I've done about 25 of these for practice, and I highly recommend poking around in them.  Problem 20, for example, asks you to sum the digits of 100!.  This can be done in one line of Haskell.  Problem 9, which asks you to find a Pythagorean triangle where a + b + c = 1000, can also be done in one line.  First you generate three lists of numbers (a, b, and c) from 1 to 500 or so.  Then you get a list where a² + b² = c².  Then you get a list where a + b + c = 1000.  Finally, you filter out all the items where a < b < c to get a unique tuple. 

I've written before that you have to be careful with functional languages because they abstract away the implementation from the code.  In the Pythagorean example above, for example, you do not have to write a series of for loops.  It's easy to write code that will take days or years to finish in Haskell.  I speak from experience.  (For fun, try running last [1..]).   But this kind of abstraction can be beneficial, as the logical nature of Haskell highlights the logic of your thought process.  One of the most important things I've learned in working with Haskell, especially on problems dealing with huge numbers, is just how important it is to have a good algorithm.  Because Haskell programming is nothing but functional logic, it's easy to concentrate on the essentials.

Logarithm Confessional

The truth is, I never really understood logarithms.  Like many students, I was just going through the motions--memorizing the rules but never having them really click.  Whenever I heard about people using logarithms and slide rules to multiply numbers in the days Before Calculators (BC), I was confused.  In college, I understood that algorithms with logarithmic growth or superlinear growth were better than quadratic ones, but I didn't have a good intuition about exactly how much better they were.

Does it matter?  I've come to think that it's essential for developers to have a good sense of logarithms and the other functions that describe algorithms.  Even if you're not writing many algorithms from scratch, it's important to know what's going on underneath the hood when you search through a database or use a hash table.  Even as computing power has become cheaper and cheaper, you can't always throw hardware at a problem.

I think an example helps.  Let's say you want to find a name in a phone book, and let's say there are 1,000,000 names in the phone book.  What if the names in the phone book were in random order?  In the worst case, you might have to look at all 1,000,000 names.  If it takes 1 second to look at 10 names, this could take around 28 hours.  In the best case, you only have to look at 1 name, but on average you'll have to look through 500,000.

Luckily in 1604 Robert Cawdrey invented alphabetical ordering.  If the phone book is in alphabetical order, how long would it take to find any name?  The answer is 2 seconds, if you flip to the middle of the book and keep dividing it in half until you find the name (and if you can still look at 10 in 1 second).  The first name you look at lets you ignore 500,000 other names.  The second name lets you cut out another 250,000.  Since we divide the number of names we're considering is cut in half each time, this is a logarithmic algorithm, and it will take 20 steps at most to find any name.  This can be shown by the fact that 2²⁰ = 1048576 or that log₂1048576 = 20.

What's amazing is that it hardly takes any more time to find a name as the phone book gets bigger and bigger.  It would take 3 seconds to look through 1,000,000,000 names and 4 seconds to look through 1,000,000,000,000.  Logarithms are the inverse of exponents.  Everyone knows that exponential growth is really fast growth.  Logarithmic growth is really slow growth.  In fact, it's almost constant.

This example shows why it's important to try to find algorithms that take a logarithmic amount of time to complete as data size increases.  The table below shows common algorithmic patterns.  For example, trying to compare all possible moves in a chess game could take longer than the history of the universe, since the number of boards increases exponentially.  It's hugely important to find an nlogn approach over an n² one.  How huge?  32 years if you're working with 1,000,000,000 data points.

Commit it to memory!  And read Steve Skiena's book

If you are like I once was, don't curse your pathetic existence.  Humans are simply not good at understanding exponential or logarithmic growth--just like we're not good at memorizing random sequences of numbers though we excel and remembering spatial information (mental athletes typically turn memorization problems into spatial ones).  It makes no sense that $1.00 compounded at 10% annual growth for 100 years somehow becomes $13,780.61.  We can work hard to develop an intuition for such things, but it's easy to forget.  What helps me is revisiting tables like these from time to time.

Bayes' Theorem Explained!

Holy shit!  I finally understand Bayes' theorem.  Thanks again, Nate Silver, you beautiful bastard.  Bayes' theorem provides an answer the question: what is the probability of an event occurring (given some other event and our prior knowledge of both)?  This is a bit abstract, so let's use Silver's example.

Let's say you find some suspicious underwear at home.  What is the probability that your significant other is cheating on you, given this evidence?  In statistical notation, we'll say the the probability your partner is cheating is P(A).  The probability of finding strange underwear in your house is P(B).  And the probability that your significant other is cheating given the evidence of the underwear is P(A|B).

To figure out this probability, you break the problem into three parts.  First, you estimate the chances that underwear is a sign of cheating, or P(B|A).  There probably aren't many good explanations for it, so let's say the probability is 75%.  Second, you estimate the chances that the underwear has nothing to do with cheating, or P(B|~A).  This is kind of hard to imagine, so let's assume the probability is 10%. Finally, you try to estimate the chances that your partner would cheat on you, before you found any panties, P(A).  According to studies, 4% of married spouses cheat in any given year, so we'll go with that.

Even though the underwear seems pretty damning, your prior estimation leads to a low probability of cheating.  Let's do the math.  Bayes formula is: P(A|B) = P(B|A) * P(A) / P(B).  That is, P(partner is cheating given the evidence of underwear) = P(partner leaves underwear around because they're cheating) * P(partner is cheating) / P(finding mysterious underwear in your house).  P(B) expands to P(B|A) * P(A) + P(B|~A) * P(~A), so we have (.75)*(.05)/((.75)*(.05) + (.10)*(.95)).  In the end, it's only 28%.

This answer may be surprising, given the high likelihood that underwear is a sign of cheating.  The reason for this is the very low estimation we gave to the chances of cheating prior to finding the underwear.  Of course, these were very rough estimates, but they help us ballpark a number.  They also show two important important things about Bayes' theorem.

First, Bayes' theorem is highly dependent on prior estimates and tests.  There is a school of statistics, usually called 'frequentist', which defines probability in terms of the frequency of an event in a large number of tests.  According to frequentists, probability doesn't refer to prior probabilities.  The assumption here is that there is a correct probability which can be found through a large enough sample size.  For Bayes, it's probabilities all the way down.  Any probability is based on prior estimates, which were based on prior estimates, etc.

If you don't get it, don't feel bad.  Try here.

Bayes' theorem also forces us to take heed of the possibility of false positives.  No test is 100% accurate.  For example, if a steroids test is right 95% of the time, it might provide false readings 15% of the time.  Given the fact that 10% of athletes use steroids, we cannot say that a positive test gives us anything like 95% probability of steroid use.  Instead, it's more like 40%.

Philosophically, what's interesting about Bayes' theorem is it provides a method for evaluating new knowledge.  The psychologist and philosopher William James generalized the way we evaluate new experiences in the following way:

The process here is always the same. The individual has a stock of old opinions already, but he meets a new experience that puts them to a strain. Somebody contradicts them; or in a reflective moment he discovers that they contradict each other; or he hears of facts with which they are incompatible; or desires arise in him which they cease to satisfy. The result is an inward trouble to which his mind till then had been a stranger, and from which he seeks to escape by modifying his previous mass of opinions. He saves as much of it as he can, for in this matter of belief we are all extreme conservatives. So he tries to change first this opinion, and then that (for they resist change very variously), until at last some new idea comes up which he can graft upon the ancient stock with a minimum of disturbance of the latter, some idea that mediates between the stock and the new experience and runs them into one another most felicitously and expediently. 

James here is describing the everyday process of learning new information.  But, as James knew better than anyone, we don't always do this well.  Sometimes we don't think about false positives; sometimes we want to believe things that are too good to be true; and sometimes we get caught up in the present moment and forget about past experience.

Even if you don't work out the probabilities every single time you learn something troubling to your understanding of the world, understanding Bayes' theorem can still be helpful.  At the very least, it warns us about making rash decisions when we learn something surprising.  Silver believes that if we all thought a bit more probabilistically about the world, it might be a better place.  We would understand the uncertainties of our forecasts and anticipate exceptions to our beliefs.  It's worth a shot, I guess.

You're Not That Smart

I'm used to feeling confused.  This is probably because of all the philosophy I've read.  Socrates said that the only thing he knew for sure was that he didn't know anything.  And nothing will make you more confused faster than dipping into a book by a German philosopher like Hegel or Heidegger.  Philosophy is all about getting comfortable with being confused.  This confusion is different from that which you might experience in a science class--if you're confused there, you simply need to turn to the next page or work through the homework.  Philosophy is fundamentally confusing, because no one has the answers to the Big Questions.

You might wonder what possible value being confused could have.  Philosophy majors have trouble justifying "what are they going to do with that."  The funny thing is that philosophy majors do better on standardized tests than any other majors.  They don't make as much money at the beginning of their career, but they tend to make more than other non-engineering majors later in life.  And philosophers pick up difficult fields like computer programming very quickly.  Perhaps there is something to being confused.

One of the main lessons I take from Nate Silver's new book is that there are many areas in which people think they are smarter than they really are.  Take poker, for example.  For a brief period of time in the early 2000's, Silver was a professional poker player.  Because of the poker boom, there were a lot of suckers that better players like him could thrive on.  The problem is that the skill set required to play poker follows a Pareto principle, or an 80-20 rule.  That is, with 20% effort, you can make the same decisions as the best players 80% of the time.  (Silver says: learn the probabilities, fold when your cards aren't good, and make some attempt to project what other players have).  It takes an incredible amount of effort to become very good.  So when the poker boom turned to bust, it suddenly became very difficult for average players to make any money.

Because of the amount of chance involved and our bias towards ourselves, it is nigh impossible to be objective about our own poker skills.  Most people who stick with poker start out doing very well--otherwise they would just give it up.  When they start to do badly, it could be the result of chance or their lack of skill.  Few have the patience to stick around and find out.

People also delude themselves on a habitual basis when it comes to investing.  Everyone thinks they have a rule to predict the market, or that their broker does.  Henry Blodget, CEO of Business Insider says: “‘Everybody thinks they have this supersmart mutual fund manager. He went to Harvard and has been doing it for twenty-five years. How can he not be smart enough to beat the market? The answer is: Because there are nine million of him and they all have a fifty-million-dollar budget and computers that are collocated in the New York Stock Exchange. How can you possible beat that?’”  No one seems to believe it, but there is no statistically significant relationship between a fund's performance one year and the next.  (Daniel Kahneman has a great explanation of this blindness).

Silver shows that a foolproof forecasting strategy is not enough, since transaction costs may eat up your earnings.  Furthermore, even if your strategy is sound, most people are psychologically unable to diverge from the herd to buy when everyone else is selling.  His advice is to follow the 80-20 rule and stick with indexed funds.  80% of the time, they're going to do as well as the very best traders could.  If you've come up with a set of heuristics to 'beat the market', you're probably kidding yourself. 

I recently took a Finance course through Venture-Lab.  Though the class was difficult and I was often confused, it was taught as if markets could be predicted with mathematical precision.  (The professor teaches in Stanford's school of Management Science and Engineering, after all!).  The implication was that if you're not making correct predictions about future returns, you just need a more complex equation.  If you can do the math, you're guaranteed to have an exciting and profitable career.  I don't buy it.

I'm more amenable to Silver's philosophy.  If you have good analytic skills, he says, look for the fields where the smart people are not flocking.  Wall Street is already flooded by ivy leaguers.  What are your chances of making it big?  Silver admits that he was lucky to get into baseball statistics, poker, and political prediction before the fields were dried up.  Look where it got him.  Rather than falling for any get-rich-quick schemes predicated on certainty, I'll stick with Socrates.

Is Statistics the Key to the Soul?

I've been brushing up on my statistics, since I was convinced I didn't learn anything practical in my two semesters of calculus-based 'statistics.' It turns out that I did learn a thing or two besides how to integrate Poisson distributions. What struck me most about statistics this time around is its objective power. I'm coming to believe that the history of human progress is the history of increasing abstraction--from markets, which abstract price from use value; to language, which substitutes abstract signs for the world's infinitude; to representative governments, which generate the will of the people from voter preferences; to information theory, which abstracts universally-understood 0's and 1's from meaning. Each new power of abstraction provides a new tool for humans to shape the world.

Borges' library has been found!

Of course, abstraction has its price. There's always something lost in the process of abstraction. Jorge Luis Borges (the author of the story for which this blog is named) writes at length about the experience of hitting the limits of abstraction, the real world. For example, if all knowledge was written down, we could never know anything, since we'd spend all our time sifting through an infinite number of books contained in an infinitely-forking library. If we remembered every experience we had in its minute detail, we'd never be able to live in the present or learn from the past. Similarly, the will of the minority loses out to the will of the majority, and statistics can never replicate lived experience.

Processes of abstraction can also be fetishized for their own sake. The operations of markets, the intricacies of language, the back-and-forth of the political process, the elegance of algorithms, or the endless march of statistical analyses are all deep, deep rabbit holes from which many never return. There's a point at which every student of philosophy--having been convinced by philosopher after philosopher--decides that it impossible to determine who is right and resolves, if only for a short time, to study philosophy solely for the beauty of its systems. There's even a perverse pleasure in the counter-intuitive nature of abstract thought, such as learning that rent control makes rent higher or that work = 0 when something is moved a great distance before returning to its origin.

One of the most interesting characteristics of processes of abstraction are the ambiguities inherent in them. Since abstractions miss something real, they are always equivocations. This happens in language when we can't decide what to call something. Is Pluto a planet or an asteroid? In statistics, ambiguity appears in the form of studies that contradict each other. Are eggs good for you or not, for chrissake? Statistical analyses are objective and help us overcome the biases of our thought processes, such as when they show us the irrationality of our fear of flying, sharks, and home invasion. But it's easy to slice the world into irreconcilable parts when those parts are so small in comparison to the actual, ever-changing world. Scientists often can't reproduce the results of their experiments. This means that either 1) the laws or regularities of the world are not the same now as they were at the time of the experiment or 2) there is some variable which they have not accounted for. And there are always variables that are not accounted for.

With the growing trend of personal data collection, from activity tracking to sleep monitoring to mental acuity quantification, we will soon be able to analyze ourselves with ever greater scrutiny. If you want to know exactly how far you've run in the last five years, you can do that. Does this make you a better runner? That is not clear, but the trend is. We'll soon be able to use the data mining techniques that advertisers like Google created on ourselves. In some ways, this is exciting. What better way to know thyself than with objective data? Conquering ourselves may be the next frontier of the powers of abstraction. But this path will be fraught with even greater dangers of experience lost, fetishization, and ambiguity.