Algorithms to live by

Christian, Brian, and Tom Griffiths.

The word “algorithm” comes from the name of Persian mathematician al- Khwrizm, author of a ninth- century book of techniques for doing mathematics by hand. His book was called al-Jabr wa’l- Muqbala— and the “al- jabr” of the title in turn provides the source of our word “algebra.”)

1. Optimal Stopping: When to Stop Looking

How do you make an informed decision when the very act of informing it jeopardizes the outcome? You must .. establish a standard, then take whatever satisfies the standard you’ve established. What balence between new experiences and favored ones makes for the most fulfilling life?

1: Look- Then- Leap Rule:

Any yardstick that provides full information on where an applicant stands relative to the population at large will change the solution from the Look- Then- Leap Rule to the Threshold Rule and will dramatically boost your chances of finding the single best applicant in the group. page 20

2. Explore/Exploit: The Latest vs. the Greatest

The Gittins index, then, provides a formal, rigorous justification for preferring the unknown, provided we have some opportunity to exploit the results of what we learn from exploring. The old adage tells us that “the grass is always greener on the other side of the fence,” but the math tells us why: the unknown has a chance of being better, even if we actually expect it to be no different, or if it’s just as likely to be worse. The untested rookie is worth more (early in the season, anyway) than the veteran of seemingly equal ability, precisely because we know less about him. Exploration in itself has value, since trying new things increases our chances of finding the best. So taking the future into account, rather than focusing just on the present, drives us toward novelty. ...The success of Upper Confidence Bound algorithms offers a formal justification for the benefit of the doubt. Following the advice of these algorithms, you should be excited to meet new people and try new things— to assume the best about them, in the absence of evidence to the contrary. In the long run, optimism is the best prevention for regret. Page 45

A/ B testing works as follows: a company drafts several different versions of a particular webpage. Perhaps they try different colors or images, or different headlines for a news article, or different arrangements of items on the screen. Then they randomly assign incoming users to these various pages, usually in equal numbers. One user may see a red button, while another user may see a blue one; one may see DONATE and another may see CONTRIBUTE. The relevant metrics (e.g., click- through rate or average revenue per visitor) are then monitored. After a period of time, if statistically significant effects are observed, the “winning” version is typically locked into place— or becomes the control for another round of experiments. Page 46

Big tech firms such as Amazon and Google began carrying out live A/ B tests on their users starting in about 2000, and over the following years the Internet has become the world’s largest controlled experiment.Page 56

It’s actually rational to emphasize exploration— the new rather than the best, the exciting rather than the safe, the random rather than the considered— for many of those choices, particularly earlier in life. We think of the young as stereotypically fickle; the old, stereotypically set in their ways. In fact, both are behaving completely appropriately with respect to their intervals. Page 57

3. Sorting: Making Order

The effort expended on sorting materials is just a preemptive strike against the effort it’ll take to search through them later. Err on the side of messiness. As the cost of searching drops, sorting becomes less valuable.

5. Scheduling: First Things First

Computers themselves do something like this: they wait until some fixed interval and check everything, instead of context- switching to handle separate, uncoordinated interrupts from their various subcomponents.

6. Bayes’s Rule: Predicting the Future

Want to calculate the chance your bus is late? The chance your softball team will win? Count the number of times it has happened in the past plus one, then divide by the number of opportunities plus tw Good predictions require good priors. This has a number of important implications. Our judgments betray our expectations, and our expectations betray our experience.

7. Overfitting: When to Think Less

So one of the deepest truths of machine learning is that, in fact, it’s not always better to use a more complex model, one that takes a greater number of factors into account. As a consequence, considering more and more factors and expending more effort to model them can lead us into the error of optimizing for the wrong thing— Page 157

Sam Altman, president of the startup incubator Y Combinator, echoes Jobs’s words of caution: “It really is true that the company will build whatever the CEO decides to measure.” [Try] to come up with incentives or measurements that do not have some kind of perverse effect.[Avoid] the ruthless and clever optimization of the wrong thing. Page 159

Cross- Validation. Simply put, Cross- Validation means assessing not only how well a model fits the data it’s given, but how well it generalizes to data it hasn’t seen. Page 159 The use of proxy metrics— taste as a proxy for nutrition, number of cases solved as a proxy for investigator diligence— can also lead to overfitting.

As a species, being constrained by the past makes us less perfectly adjusted to the present we know but helps keep us robust for the future we don’t. ... A bit of conservatism, a certain bias in favor of history, can buffer us against the boom- and- bust cycle of fads. That doesn’t mean we ought to ignore the latest data either, of course. Jump toward the bandwagon, by all means— but not necessarily on it. ... When you’re truly in the dark, the best- laid plans will be the simplest. ...the further ahead they need to brainstorm, the thicker the pen Page 167

8. Relaxation: Let It Slide

One of the simplest forms of relaxation in computer science is known as Constraint Relaxation. In this technique, researchers remove some of the problem’s constraints and set about solving the problem they wish they had. Then, after they’ve made a certain amount of headway, they try to add the constraints back in [,]. where some impossibilities are downgraded to penalties, the inconceivable to the undesirable— enables Page 180

Of the various ways that computational questions present themselves to us, optimization problems — one part goals, one part rules — are arguably the most common.

There are many ways to relax a problem, and we’ve seen three of the most important. The first, Constraint Relaxation, simply removes some constraints altogether and makes progress on a looser form of the problem before coming back to reality. The second, Continuous Relaxation, turns discrete or binary choices into continua: when deciding between iced tea and lemonade, first imagine a 50– 50 “Arnold Palmer” blend and then round it up or down. The third, Lagrangian Relaxation, turns impossibilities into mere penalties, teaching the art of bending the rules (or breaking them and accepting the consequences).

. Randomness: When to Leave It to Chance

So- called greedy algorithm, which you can also think of as a “myopic algorithm”: one that shortsightedly takes the best thing available every step of the way. ... Again looking for the best local improvement. This is an algorithm known as Hill Climbing. You may have found only a so-called “local maximum,” not the global maximum of all the possibilities. Sometimes it’s best not to get too attached to an initial direction that shows promise, and simply start over from scratch 197

Use a little bit of randomness every time you make a decision. Being randomly jittered, thrown out of the frame and focused on a larger scale, provides a way to leave what might be locally good and get back to the pursuit of what might be globally optimal. ... Wikipedia, for instance, offers a “Random article” link, and Tom has been using it as his browser’s default homepage for several years, seeing a randomly selected Wikipedia entry each time he opens a new window.