Book notes: Algorithms to Live By

by Brian Christian and Tom Griffiths

Optimal Stopping

37% Rule / The Secretary Problem / Marriage Problem
The optimal stopping rule prescribes always rejecting the first 37% of applicants after the interview and then stopping at the first applicant who is better than every applicant interviewed so far (or continuing to the last applicant if this never occurs). You will get the best candidate 37% of the time following this algorithm.


Merge Sort and Binary Search


Caching

Least Recently Used (LRU) Caching adaptations in the real world

  • Noguchi Filing System
  • Valet stand for most often used clothing
  • Library front book display area

Computational Kindness / Load (don’t make me think!)

  • Car parking starting from closest to store – first available space is the best (instead of using 37% rule)
  • Pick a few restaurants to choose from
  • Choose a few date/times for meetings
  • Bus stop with next bus arrival time sign
  • Block vs Spin: Restaurant wait-list vs open seating policy

pp. 259-261


Scheduling

  • Washing clothes: shortest washing times at the start, and shortest drying times at the end

Bayes’s Rule

Laplace’s law – estimate probability of future event based on previous results. The expectation is the number of previous wins plus one, divided by the number of attempts plus two:

(w)ins + 1
———————————

(n)umber of attempts + 2

Example: you flip heads 4 times out of 7 attempts. So 4 + 1 divided by 7 + 2 equals 5/9 or 56% chance. The more previous attempts, the more accurate the prediction.

This can be used to calculate the chance that the bus is late, baseball team will win, or things with much more previous results like chance baby is boy or girl or the sun will rise.

Copernican Principle or Mediocrity Principle (Bayes’ Rule without priors) – unless we know better (from priors) we can expect to have shown up precisely halfway into the the duration of any given phenomenon.

E.g., USA will most likely last another 250 years or so; Google until 2032; 7 days since last accident on the job, 7 days until next accident; bear activity in campground 10 days ago, bear again in 10 days. Looking at serial number on tram, double the number to make best estimate of number of trams

  • Normal distribution curve – lifespan of humans
  • Use Average Rule

  • Power-law distribution curve – average mean income in US
  • Use Multiplicative Rule

  • Erlang distribution curve – amount of time politicians stay in office
  • Use Additive Rule


Overfitting

Occam’s Razor – all things being equal, the simplest possible hypothesis is probably the correct one

Regularization solves the problem when things aren’t completely equal.

Regularization – introduce an additional term to your calculations that penalizes more complex solutions

Early Stopping is a form or regularization that forces you to stop thinking so much by limiting the number of variables that over-complicate things

E.g., Use a thick pen when designing something on paper at first so you don’t put in unnecessary details.

Darwin’s pro / con list got too detailed with too many pros and cons. He could have settled for just a few of the most important ones and made a good decision there.

How to stop a pro/con list? Perhaps by the of the page.


Relaxation

The perfect is the enemy of the good. —Voltaire

Constraint Relaxation – remove some of the problem’s constraints and set about solving the problem you wish you had. Then, after making a certain amount of headway, try to add the constraints back in.

For example, in the traveling salesman problem, allow salesman visit same town more than once or let him retrace his steps.

Relax constraints to get a good enough solution for solving life’s most vexing questions:

  • What would you do if you weren’t afraid?
  • What would you do if you won the lottery?
  • What would you do if all jobs paid the same?
  • What would you do ifyou could not fail?

Continuous Relaxation – most are discrete optimization problmes. No smooth continuum among its solutions. No shades of gray. Possible solution is to convert discrete to a continuous optimization. Instead of sending 100 invitations, send 50 to those with most connections who will everyone else. You turn whole numbers into fractions and do lots of rounding.

Lagrangian Relaxation – an optimization problems has two parts: Rules and Scorekeeping. Take some of the problem’s constraints and bake them into the scoring system instead. That is, we take the impossible and downgrade it to costly. Allows you to color outside the lines at some cost.

E.g., sports scheduling, overfilling wedding tables,


Randomization

Three Tradeoffs: time, space, and CERTAINTY

Bloom filters – comes up with an answer which saves time and space but trades off error probablility

E.g., check to see if URL already one of 70 trillion cached URLs before caching. Bloom filter will give fast result with a 2% to 3% chance that it’s wrong


Networking

Exponential Backoff – increasing the average delay after every successive failure. maximum delay length forms an exponential progression


Game Theory

Recursion – part of bluffing; you know that they know that you know; but make sure to play only one level above your opponent

Advertisements
Book notes: Algorithms to Live By

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s