Algorithms to Live By - Book Review
Learned so much, about a bunch of different topics
List of practical algorithms (most of which I gleaned from this book): 202006031201
Outline of notes:
…
I find that the three major administrative problems on a campus are sex for the students, athletics for the alumni, and parking for the faculty. — Clark Kerr, President of UC Berkeley, 1958 - 1967
…
Shoup’s solution involves installing digital parking meters that are capable of adaptive prices that rise with demand (This has now been implemented in downtown San Francisco).
Reason why parking is so hard to find in San Francisco - the policies in place encourage extremely high occupancy rates. (Parking is an optimal stopping problem - every time you’re trying to find parking, you’re deciding between taking a parking that you see, or going a bit closer and pushing your luck.) The adaptive parking policy in San Francisco 202006071540 encourages an 85% occupancy rate, which is 33% better than an occupancy rate of even 90%.
…
The overall rate at which people found the best possible applicant was pretty good: about 31%, not far from the optimal 37%. Most people acted in a way that was consistent with the Look-Then-Leap rule 202006071543, but they leapt sooner than they should have more than four-fifths of the time.
I think I have a similar problem - I generally leap too soon 202006071544.
…
multi-armed bandits problem
Always wanted to learn more about this! Now I have the chance. Multi-armed bandits problem 202006071550
…
For every slot machine we know little or nothing about, there is some guaranteed payout rate which, if offered to us in lieu of that machine, will make us quite content never to pull its handle again. This number, which Gittins called the “dynamic allocation index,”, and which the world now knows as the Gittins index—suggests an obvious strategy on the casino floor: always play the arm with the highest index.
Understanding the Gittins index 202006071552
…
For one, the Gittins index is optimal only under some strong assumptions. It’s based on geometric discounting of future reward, valuing each pull at a constant fraction of the previous one, which is something that a variety of experiments in behavioral economics and psychologists suggest people don’t do. And if there’s a cost to switching among options, the Gittins strategy is no longer optimal either. Perhaps even more importantly, it’s hard to compute the Gittins index on the fly.
Adding this quote to the Gittins index note 202006071552 for some more context
…
The recommendations given by Upper Confidence Bound algorithms will be similar to those provided by the Gittins index, but they are significantly easier to compute, and they don’t require the assumption fo geometric discounting.
Note about Upper Confidence Bound algorithms 202006071602
…
The success of Upper Confidence Bound algorithms offer 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.
Very excited to hear that there is a formal justification for this! Meeting new people and trying new things 202006071608 is something that I’ve been shifting towards for a while.
…
What followed the public outcry [to the Tuskeegee syphilis experiment 202006071617 ], and the subsequent congressional hearing, was an initiative to formalize the principles and standards of medical ethics. A commission heat at the pastoral Belmont Conference Center in Maryland resulted in a 1979 document known as the Belmont Report. The Belmont Report lays out a foundation for the ethical practice of medical experiments, so that the Tuskegee experiment—an egregious, unambiguously inappropriate breach of the health proession’s duty to its patients—might never be repeated. But it also notes the difficulty, in many other cases, of determining exactly where the line should be drawn.
Reaction to and impact of the Tuskegee experiment 202006071617
…
And a growing community of doctors and statisticians think that we’re doing it wrong: that we should be treating the selection of treatments as a multi-armed bandit problem, and trying to get the better treatments to people even while an experiment is in progress.
Read more about Adaptive trials 202006110140
…
“Lawn Tennis Tournaments: The True Method of Assigning Prizes with a Proof of the Fallacy of the Present Method.”
Lol, it’s pretty cool that Lewis Carroll was writing papers about the structure of tennis tournaments.
…
But in fact it isn’t Bubble Sort that emerges as the single best algorithms in the face of a noisy comparator. The winner of that particular honor is an algorithm called Comparison Counting Sort 202006110147. In this algorithm, each item is compared to a ll the others, generating a tally of how many items it is bigger than. This number can then be used directly as the item’s rank. Since it compares all pairs, Comparison Counting Sort is a quadratic-time algorithm, like Bubble Sort. Thus it’s not a popular choice in traditional computer science applications, but it’s exceptionally fault-tolerant.
Pretty cool how the round-robin format is the most fault-tolerant sorting algorithm. 202006110147
…
When we think about the factors that make large-scale human societies possible, it’s easy to focus on technologies, agriculture, metals, machinery. But the cultural practice of measuring status with quantifiable metrics might be just as important.
Explored more here: Cardinal rankings are essential for society 202006110153
…
Linearithmic numbers of fights might work fine for small-scale groups; they do in nature. But in a world where status is established through pairwise comparisons—whether they involve exchanging rhetoric or gunfire—the amount of confrontation quickly spirals out of control as society grows. Operating at industrial scale, with many thousands millions of individuals sharing the same space, requires a leap beyond. A leap from ordinal to cardinal. Much as we bemoan the daily rat race, the act that it’s a race rather than a fight is a key part of what sets us apart from the monkeys, the chickens—and for that matter, the rats.
More explanation for why cardinal numbers are needed in society 202006110153
…
Deep within the underground Gardner Stacks at the University of California, Berkeley, behind a locked door nd a prominent “Staff Only” notice, totally off-limits to patrons, is one of the jewels of the UC library system. Cormac McCarthy, Thomas Pynchon, Elizabeth Bishop, and J.D. Salinger; Anaïs Din, Susan Sontag, Junot Díaz, and Michael Chabon; Annie Proulx, Mark Strand, and Philip K. Dick; William Carlos Williams, Chuck Palahniuk, and Toni Morrison; Denis Johnson, Juliana Spahr, Jorie Graham, and David Sedaris; Sylvia Plath, David Mamet, David Foster Wallace, and Neil Gaiman … It isn’t the library’s rare book collection; it’s its cache.
This is just one of several references to UC Berkeley in this book. Pretty cool that there are so many, not just in reference to literature produced, but to buildings like Moffitt and Main Stacks as well.
…
Rik Belew of UC San Diego, who studies search engines from a cognitive perspective, recommended the use of a valet stand. Though you don’t see too many of them these days, a valet stand is essentially a one-outfit closet, a compound hanger for jacket, tie, and slacks—the perfect piece of hardware for your domestic caching needs. Which just goes to show that computer scientists won’t only save you time; they might also save your marriage.
Pretty cool that valet stands 202006110209 exist. The discussion was in the context of LRU caches, and how they’re applicable to daily scenarios.
…
“I think the most important tangible thing seniors can do is to try to get a handle on the idea that their minds are natural information procession devices,” he writes. “Some things that might seem frustrating as we grow older (like remembering names!) are a function of the amount of stuff we have to sift though .. and are not a necessary a sign of a failing mind.” As he puts it, “A lot of what is currently called decline is simply learning.” Caching gives us the language to understand what’s happening. We say “brain fart” when we should really say “cache miss.” The disproportional occasional lags in information are just a reminder of how much we benefit most of the time by having what we need at the front of our minds.
This is a really interesting to think about mental decline while aging
uid: 202005302204 tags: #literature #programming #outline #writeup