The first semi-serious answer I remember giving to the title question was “either a writer or a magician” (circa third grade, more about age 8-9).
Given this quote:
Any sufficiently advanced technology is indistinguishable from magic. –Arthur C. Clarke
and the fact that likely the most tangible record of my career are my publications, one might say that I did indeed become both a writer and a magician.
I’m planning to take the World Blogging Month (WoBloMo) challenge in March. Join me!
The goal is simple: blog at least every other day from March 1 to March 31. Post something — anything — on every odd day of the month and you win. Skip any day not divisible by 2 and you lose.
Many bloggers already write every day or nearly so. More power to them. For the rest of us, who blog infrequently and spend copious time arguing with their inner editors, ludicrous and artificial pretenses can be a good thing.
WoBloMo resembles the write-a-novel-in-a-month contest NaNoWriMo and other timed artistic challenges prefaced on the idea that quantity and quality can be friends. By suppressing the Spock-like perfectionist inside you, you can bring out your inner Kirk and “just do itâ€. Agonizing over details always has diminishing returns and sometimes, perversely, can make things worse. Or so the theory goes. You be the judge once (if) my WoBloMo fountain erupts.
Added 2009/02/26: Full disclosure.
The Last Analogs were born after commercial color TV (1953) and graduated high school before Mosaic (1993), roughly spanning from Steve Jobs to Larry Page.
Last Analogs like me grew up with VHS players, walkmans, card catalogs, newspapers, bunny ears, and film. We then watched as, inexorably, every last one of them winked from A to D. By 1993, the dawn of the digital age was ending, giving way to a blazing midday sun. Little did we know how thoroughly the Internet would shift the revolution into hyperlink drive.
Recently, a holiday card I sent to a friend was returned undelivered. He had moved and I had sent it to his old address.
It turns out I actually had the correct address filed away in an email folder — he had kindly sent it to me months earlier — and I had even tagged the email as “contact info”. Yet my address book failed to reflect it, mostly because my address book doesn’t read or process email, but rather expects me to do it.
This is an inherently Last Analog problem.
The new address books — the Facebooks and Plaxos of the world — solve the problem gracefully. On Facebook, I don’t keep my own separate copy my friend’s address; instead I keep a pointer to my friend and all his data and let him do the updating. My friend doesn’t need to email me and I don’t have to transcribe anything (or, in the early days, call and write), and repeat the same for all his friends. He updates his own information and everything else happens automatically.1
There are a ton of inherently Last Analog problems, including not knowing how much money you’ve spent in a month, how many calories you’ve burned or eaten, where your car or key or friend is, or where you are. A Last Analog could be living and working near an old college buddy and not even know it.
But perhaps the most unfortunate Last Analog problem is our impaired collective memory. Last Analogs grew up without the benefit of all the little digital trails that people now leave automatically as they go about their lives: the emails, twitters, geo-tagged photos, walls, groups, friendlists, and blogs that form a searchable, hyperlinked diary.2
For Last Analogs to catch up still requires considerable effort: for example, digging out old boxes of print photos and scanning and geo-tagging them by hand. Presumably even this process will become cheaper and easier, but in the meantime the online map view of my post-college European tour is fifteen years in waiting and counting, memories of metadata fading, and the slide show at my 20th high school reunion this spring will be only as complete as busy schedules allow.
Too bad the wayback machine doesn’t go that way back.
I guess its time to get over my First Digital envy and get to work scanning uphill both ways in the snow.
| 1Eventually, I shouldn’t have to bother with street names and zip codes either: I’ll just address the card to my friend’s unique identifier and the post office will take it to the right place. That’s assuming by then that I’m still sinfully sending cards through the postal mail. | |
| 2Even today, people delete too many gems. I encourage you to follow Randy Pausch’s advice and archive everything. |
Yahoo! Research just published its list of key scientific challenges facing the Internet industry.
It’s a great resource for students to learn about the area and find meaty research problems. There’s also a chance for graduate students to earn $5000 in seed funding, work with Yahoo! Research scientists and data, and attend a summit of like-minded students and scientists.
The challenges cover search, machine learning, data management, information extraction, economics, social science, statistics, multimedia, and computational advertising.
Here’s the list of challenges from the algorithmic economics group, my group. We hope it provides a clear picture of the goals of our group and the areas where progress is most needed.
We look forward to supporting students who love a challenge and would like to join us in building the next-generation Internet.
Well, geeks are certainly inheriting my earth.
On January 13, my company named Carol Bartz, a self-avowed math nerd and former punch-card carrying member of her college computer club, as its CEO. In her own words:
I was a real nerd. I love, love, love, love math. Back in the late ’60s, math meant being a teacher if you were a woman. I wasn’t interested in teaching. Then I took my first computer course. It was crazy. It was like math, only more fun. I switched to computer science.
Exactly one week later, on January 20, my country turned over executive control to Barack Obama, a CrackBerry addicted comic book geek. In his inauguration speech, Obama vowed to “restore science to its rightful place”, “wield technology’s wonders”, and even addressed “non-believers” — wording that in any sane universe should be entirely unremarkable, yet in ours appears to represent an unprecedented milestone.
I can’t recall a two-week span filled with so much geek pride and cautious optimism.
Back to the Carol Bartz quote. Reading it brings a smile to my face. It also reminds me of my mom, who, convinced it was her only option, taught middle school for a few years before returning to medical school to pursue her passion, enjoying a successful career as one of the first women radiologists.
I highly recommend Bartz’s essay, which mixes biography with prescience and insight. Bartz describes how technology and the Internet are transforming collaboration and improving productivity, at the same time ushering in an era of information overload, email bankruptcy, and misuse of the extra time technology affords. Remarkably, she wrote about these things in 1997!
It’s amazing to think how things have changed since 1997. My own first web experience, courtesy Mosaic, came in 1994, the same year Yahoo! was founded. In 1996, PayPal predecessor and public company First Virtual wrote their own keystroke-sniffing malware as a stunt to bolster their urgent call to “NEVER TYPE YOUR CREDIT CARD NUMBER INTO A COMPUTER”. Ebay was founded in 1995, PayPal in 1998. In 1997, Friendster had neither come nor gone, and Facebook CEO Mark Zuckerberg was 13.
Yet Bartz’s words seem more relevant than ever today.
As I alluded to previously, I seem to be getting “intelligent spam” on my blog: comments that pass the re-captcha test and seem on-topic, yet upon further inspection clearly constitute link spam: either the author URI or a link in the comment body is spam.
Here is one of the most clear cases, received on January 9 as a comment to my post on the CFTC’s call for proposals to regulate prediction markets:
Date: Fri, 9 Jan 2009 01:28:01 -0800
From: Matt.Herdy
New comment on your post #71 “A historic MayDay: The US
government’s call for help on regulating prediction markets”
Author : Matt.Herdy
Comment:
Thanks for that post. I’ll put a note in the post.1. It’s nothing new. The CFTC will just formalize the current
status quo.
2. We are prisoner of the CFTC regulations and the US Congress’
distaste of sports “gamblingâ€. As for the profitability of prediction
exchanges in that strict environment, I don’t see how you can deny that
HedgeStreet went bankrupt even though it was well funded. Isn’t that a
hard fact?
3. You’re right, but all “pragmatists†should follow a business
plan and make profits. See point #2. Pragmatists won’t make miracles.<a href=”http://www.stretch-marks-help.com/”>Removing stretch marks</a>
At first blush, the comments seems to come from a knowledgeable person: they refer to HedgeStreet, an extremely relevant yet mostly unknown company that’s not mentioned anywhere else in the post or other comments.
It turns out the comments seem intelligent because they are. In fact, they’re copied word for word from Chris Masse’s comments on his own blog.
Chris Masse’s page has a link to my page, so it could have been discovered with a “link:” query to a search engine.
Though now I understand what this spammer did, I remain puzzled exactly how they did it and especially why.
In any case, it seems an intriguing development in the spam arms race. Are other bloggers getting “intelligent spam”? Does anyone know how it’s done and why?
Update 2010/07: Oh, the irony. I got a number of intelligent seeming comments on this post about SEO, nofollow, economics of spam, etc. that were… promoting spammy links. I left them for humor value though disabled the links.
What exactly is a combinatorial prediction market?
2010 Update: Several of us at Yahoo! Labs, along with academic researchers, have theorized and written about combinatorial prediction markets for several years, as you’ll see below. But now we’ve gone beyond talking about them and actually built one. So the best way to answer the question is to see the market we built and play with it. It’s called Predictalot. The first version was based on the NCAA Men’s College Basketball tournament known as March Madness.
March Madness is the anything-can-happen-and-often-does tournament among the top 64 NCAA Men’s College Basketball teams. The “madness” of the games is rivaled only by the madness of fans competing to pick the winners. In Las Vegas, you can bet on many things, from individual games to the overall champion to more exotic “propositions” like which conference of teams will do best. Still, each gambling venue defines in advance exactly what you are allowed to bet on, offering an explicit list of usually no more than a few thousand choices.
So here is my informal definition: a combinatorial market is one where users can construct their own bets by mixing and matching options in myriad ways, sort of like ordering a Wendy’s hamburger. (Or highly customized insurance.)
Now I’ll try for a more precise definition.
Just to set the vocabulary straight, outcomes are all possible things that might happen: for example all five candidates in an election, all 30 teams in an NBA Championship market, all 3,628,800 (or 10!) finish orderings in a ten-horse race, or all 9.2 quintillion March Madness tournament results. Among the outcomes, in the end one and only one of them will actually occur; traders try to predict which.
Bids express what outcome(s) traders think will happen. Bids also contain the risk-reward ratio the trader is willing to accept: the amount she wins if correct and the amount she is willing to lose if incorrect.
There are two reasons why we might call a market “combinatorial”: either the bids are combinatorial or the outcomes are combinatorial. The latter poses a much harder computational problem. I’ll start with the former.
For comparison, a non-combinatorial bid is a bet on a single outcome, for example “candidate O will win the election”. The vast majority of fielded prediction markets handle only non-combinatorial bids.
What are examples of combinatorial bids besides Yoopick? Abe Othman built an interval betting interface similar to Yoopick (he came up with it on his own, proving that great minds think alike) to predict when the new CMU computer science building will finish construction. Additional examples include Bossaerts et al.’s concept of combined value trading and the parimutuel call market mechanism [Baron & Lange, Lange & Economides, Peters et al.]. 2010 Update: Predictalot is our latest example of a market featuring both combinatorial bids and outcomes.
A market with combinatorial outcomes is almost nonsensical without allowing combinatorial bids as well, since individual outcomes are like microbes on a needle on a cruise ship of hay in a universe-sized sea. No one wants to bet on these minuscule possibilities one at a time. Instead, traders bet on high-level properties of outcomes, like “Duke will advance further than UNC”, that encode sets of outcomes. Here are some example forms of combinatorics and corresponding bidding languages that seem natural:
We summarize some of these in a short article on Combinatorial betting and a more detailed book chapter on Computational aspects of prediction markets.
2009 Update: Gregory Goth writes an excellent and accessible summary in the March 2009 Communcations of the ACM, p.13.
So far, I’ve only talked about the form of bids from traders. Next I’ll discuss the actual mechanics of the marketplace, or how bids are processed. How does the market operator decide which bids to accept or reject? At what prices?
I’ll focus on two major possibilities: either the market operator acts as an auctioneer or he acts as an automated market maker.
An auctioneer only matches up willing traders with each other — the auctioneer never takes on any risk of his own. This is how most financial exchanges like the stock market operate, and how intrade and betfair operate. (A call market is a special case where the auctioneer collects many bids over a period of time, then processes them all together in a single batch.)
An automated market maker will quote a price for any bet whatsoever. Even lone traders can place their bet with the market maker as long as they accept the price, greatly enhancing liquidity. The liquidity comes at a cost though: an automated market maker can and often does lose money, though clever pricing algorithms can guarantee that losses won’t mount beyond a fixed amount set in advance. Hanson’s logarithmic market scoring rule market maker is far and away the most popular for prediction markets, and for good reason: it’s simple, has nice modularity properties, and behaves well in practice. We catalog a number of bounded-loss market makers in this paper. The dynamic parimutuel market used in the (now closed) Yahoo! Tech Buzz Game can be thought of as another type of automated market maker.
A market with combinatorial outcomes almost requires a market maker to function smoothly. When traders have such a mind-boggling array of choices, the chances that two or more of their bets will exactly counter each other seems remote. If trades are rarely filled, then traders won’t bother bidding at all, causing a no-chicken-no-egg spiral into failure.
One the other hand, a market maker allows anyone to get a price quote at any time on any bet, no matter how convoluted or specific, even if no other traders had thought about that particular possibility. Thus interacting with a combinatorial market maker can be highly satisfying: propose any obscure proposition, click “accept price”, and your bet is placed: no doubt and no waiting.
I’ll discuss one more technicality. An auctioneer must decide whether bids can be partially filled, giving traders both less risk and less reward than they requested, in the same ratio. This makes sense. If I’m willing to risk $100 to win $200, I’d almost surely risk $50 to win $100 instead. Allowing partial fills greatly simplifies life for the auctioneer too. If bids are divisible, or can be filled in part, the auctioneer can use efficient linear programming algorithms; if bids are indivisible, the auctioneer must use integer programming algorithms that may be intractable. For more on the divisible/indivisible distinction, see Bossaerts et al. and Fortnow et al. Allowing divisible bids seems the logical choice in most scenarios, since the market functions better and most traders won’t mind.
Why do we need or want combinatorial markets? Simply put, they allow for the collection of more information, the life-blood of every prediction market. Combinatorial outcomes allow traders to assess the correlations among base objects, not just their independent likelihoods, for example the correlation between Democrats winning in Ohio and Pennsylvania. Understanding correlations is key in many applications, including risk assessment: one might argue that the recent financial meltdown is partly attributable to an underestimation of correlation among firms and securities and the chances of cascading failures.
Although financial and betting exchanges, bookmakers, and racetracks are modernizing, turning their operations over to computers and moving online, their core logic for processing bids hasn’t changed much since auctioneers were people. For simplicity, they treat all bets like apples and oranges, processing them independently, even when they are more like hamburgers and cheeseburgers. For example, bets on a horse “to win” and “to finish in the top two” are managed separately at the racetrack, as are options to buy a stock at “strike price 30” and “strike price 20” on the CBOE. In both cases it’s a logical truism that the first is worth less than the second, yet the market pleads ignorance, leaving it to traders to enforce consistent pricing.
In a combinatorial market, a bet on “Duke will win the tournament” automatically increases the odds on “Duke will win in the first round”, as it logically should. Mindless mechanical tasks like this are handled automatically, by algorithms that are far better at it anyway, freeing up traders for the primary task a prediction market asks them to do: provide information. Traders are free to express their information in whatever form they find most natural, and it all flows into the same pool of liquidity.
I discuss the benefits of combinatorial bids further in this post, including one benefit I don’t mention here: smarter accounting, or making sure no more is reserved from a trader’s balance than necessary to cover their worst-case loss.
I would argue that there is virtually no disadvantage to allowing combinatorial bids. They are more flexible and natural for traders, and they eliminate redundancy and thus concentrate liquidity (again I refer the reader to this previous post). Allowing indivisible combinatorial bids can cause computational problems, but as I argue above, divisible bids make more sense anyway.
On the other hand, there can be disadvantages to markets with combinatorial outcomes. First, trader attention and liquidity may be severely fractured, since there are nearly limitless things to bet on.
Second, and perhaps more troublesome, running an auctioneer with combinatorial outcomes is computationally intractable (specifically, NP-hard, or as hard as solving SAT) and running a market maker is even harder (specifically, #P-hard, as hard as counting SAT), meaning that the amount of time needed to run is proportional to the number of outcomes, exponential in the number of objects.
It gets worse. Even if we place strict limits on what types of bets traders can make, the market may still be infeasible to run. For example, even if all bets are pairwise, like “Horse B will finish ahead of horse D”, the auctioneer and market maker problems for permutation betting remain NP-hard and #P-hard, respectively. Likewise, Boolean betting remains hard even if the most complicated bet allowed is joining two events, like “E will happen and F will not” [see Chen et al. and Fortnow et al.].
Now for some good news: in some cases, fast algorithms are possible. If all bets are subset bets of the form “Horse A will finish in position 1,2, or 10” or “Horse B,C, or E will finish in position 3”, then permutation betting with an auctioneer is feasible (using a combination of linear programming and maximum matching), even though the corresponding market maker problem is #P-hard. If all bets are of the form “Team B will advance to round k”, tournament betting with a market maker is feasible (using Bayesian network inference). Taxonomy betting with a market maker is feasible (using dynamic programming).
Finally, even better news: fast market maker approximation algorithms are not only possible and practical, they work without limiting what people can bet on, fulfilling the almost magical promise I made at the outset of constructing any bet you can imagine on the fly. Approximation works because people like to bet on things that have a decent chance of happening, say between a 1% and 99% chance. Standard sampling algorithms, including importance sampling and MCMC, are good at approximating prices for such reasonable events. For the extreme (e.g., 1-in-a-billion) events, sampling may fail, so the market maker will have to round off in its own favor to be safe.
Wrapping up, in my mind, the best way to implement a combinatorial-outcome prediction market is as follows:
2010 Update: Predictalot is our first pass at carrying through on this vision of how to build a combinatorial prediction market. In building it, we learned a great deal already, for example that sampling is much much trickier than I had initially imagined, and that it’s easy to accidentally create arbitrage loopholes if you’re not extremely careful with the math.
I glossed over a number of details. For example, care must be taken for the market maker to always round approximations in its own favor to avoid opening itself up to arbitrage attacks. Another difficulty is how to implement smart accounting to allow traders maximum leverage when they place many interrelated bets. The assumption that traders could lose all their bets is far too conservative — they might have bets that provably cannot simultaneously lose — but may serve as a reasonable starting point in practice.
My wife and I just finished watching Babel, a movie about people lost in foreign cultures struggling to communicate.
It turns out that when you pop in the DVD and hit play, by default there are no subtitles, despite the fact that the majority of dialog takes place in Moroccan, Japanese, sign language, and Spanish.
I suffered from English Lit Syndrome, thinking how cool it was how the filmmakers made you feel like you were lost along with the characters, recalling the spot-on memoryless feel of Memento.
My wife insisted that there must be something wrong. Perhaps we missed a setting or choice among the menu options for subtitles? As the Japanese storyline reached its close, with lengthy and intricate back and forth dialog between characters whose relationships I hadn’t the least clue about, I realized that maybe, just maybe, she was right.
When the movie ended, I dug back into the menu. Low and behold, there in a “settings” submenu was a choice for subtitles: English, Spanish, or none. Default on “none”.
My artistic elitism crumbled into simple annoyance.
Poking around online, it turns out I’m not the only one duped by the DVD bug or struck by ELS.
Just think of all the time wasted by people watching the movie in incomprehension, investigating the problem, getting irked, and most especially complaining about it online.
A classic Econ 101 lesson in efficiency lost.
But wait! The DVD spurred the disorganized masses to work together to produce a tower of criticism. How clever!
In October, Philip Polgreen, Yiling Chen, myself, and Forrest Nelson (representing University of Iowa, Harvard, and Yahoo!) published an article in the journal Clinical Infectious Diseases titled “Using Internet Searches for Influenza Surveillance”.
The paper describes how web search engines may be used to monitor and predict flu outbreaks. We studied four years of data from Yahoo! Search together with data on flu outbreaks and flu-related deaths in the United States. All three measures rise and fall as flu season progresses and dissipates, as you might expect. The surprising and promising finding is that web searches rise first, one to three weeks before confirmed flu cases, and five weeks before flu-related deaths. Thus web searches may serve as a valuable advance indicator for health officials to spot the onset of diseases like the flu, complementary to other indicators and forecasts.
On November 11, the New York Times broke a story about Google Flu Trends, along with an unusual announcement of a pending publication in the journal Nature.
I haven’t read the paper, but the article hints at nearly identical results:
Google … dug into its database, extracted five years of data on those queries and mapped it onto the C.D.C.’s reports of influenzalike illness. Google found a strong correlation between its data and the reports from the agency…
Tests of the new Web tool … suggest that it may be able to detect regional outbreaks of the flu a week to 10 days before they are reported by the Centers for Disease Control and Prevention.
To the reporter’s credit, he interviewed Phillip and the article does mention our work in passing, though I can’t say I’m thrilled with the way it was framed:
The premise behind Google Flu Trends … has been validated by an unrelated study indicating that the data collected by Yahoo … can also help with early detection of the flu.
giving (grudging) credit to Yahoo! data rather than Yahoo! people.
The story slashdigged around the blogomediasphere quickly and thoroughly, at one point reaching #1 on the nytimes.com most-emailed list. Articles and comments praise how novel, innovative, and outside-of-the-box the idea is. The editor in chief of Nature praised the “exceptional public health implications of [the Google] paper.”
I’m thrilled to see the attention given to the topic, and the Google team deserves a huge amount of credit, especially for launching a live web site as a companion to their publication, a fantastic service of great social value. That’s an idea we had but did not pursue.
In the business world, being first often means little. However in the world of science, being first means a great deal and can be the determining factor in whether a study gets published. The truth is, although the efforts were independent, ours was published first — and Clinical Infectious Diseases scooped Nature — a decent consolation prize amid the go-google din.
Update 2008/11/24: We spoke with the Google authors and the Nature editors and our paper is cited in the Google paper, which is now published, and given fair treatment in the associated Nature News item. One nice aspect of the Google study is that they identified relevant search terms automatically by regressing all of the 50 million most frequent search queries against the CDC flu data. Congratulations and many thanks to the Google/CDC authors and the Nature editors, and thanks everyone for your comments and encouragement.
Just in time for Election Day Tuesday November 4, 2008, here is an extremely un-useful mapping service to help you find exactly where not to go on election day in order to cast your vote.
Click here to find where your polling place isn’t for this election
For example, here is precisely where I would not go to vote if I lived where I work which I don’t:
Ok, what’s the point of this you ask?
Well, first, there is little point — it’s mostly a joke.
Beyond that, it’s meant as a satirical commentary on the inability of computers to understand satirical commentary.
Search engine algorithms and search advertising algorithms can’t distinguish well between “polling place is” and “polling place is not”.
Enough googlebombing and I’d wager the above link could rise in the ranks for search queries like polling place.
Enough money and a griefer serious about policing the Internet’s un-seriousness could advertise the link to people searching for their polling place in battleground zip codes, keeping the ad text perfectly factual with a few well placed negations, bypassing human editors at least for a few crucial hours.
In a way, it’s a thought experiment into our future as robots replace humans in the workforce, in this case librarians and editors.
The site is not meant to fool people, even foolish people, only computers.