Portal sentry turret

Cristina and I put a motion sensor on an Arduino and made a Portal sentry turret:

We bought a motion sensor and Arduino ethernet shield at RadioShack, with no particular goal in mind, and wanted to figure out a way to combine them.

The Arduino is acting as a mini web server, and it serves a single page that refreshes itself every 2 seconds. If the motion sensor has recently started (or stopped) detecting motion, it will embed an appropriate sound clip in the page.

For the next version, it'd be simpler to hook a speaker up to the Arduino directly, and cut out the web server ... but for today, the whole point was find a use for the ethernet shield.

[ Code ]

Expecting more from Yelp

Yelp has the best database of business reviews. I frequently rely on those ratings to make decisions, and very rarely use other sites. Although the quality of the data keeps me coming back to Yelp, it's insulating them from being required to innovate on product features.  There's a lot they could do to make me much happier as a customer.

Search

"25% [of Yelp's traffic] is people qualifying ‘Yelp’ as one of the keywords in their [Google] search" - Yelp CEO, Jeremy Stoppelman

I do this all the time too, and it's because Yelp's search isn't very good.

Yelp's site is slow. When I go to http://www.yelp.com, it takes about 1.4s for the home page to load, and 1.6s for the search-results page to load after doing a query. (It's significantly slower if you count rendering time, which is more realistic, but harder to measure).  Compare that to Google, where the home page loads in .1s and (even turning off Google Instant) the result page loads in about .6s.  That might not sound like a big difference, but on the web it totally is.

Yelp's rankings, which you'd expect to be their bread and butter, are a let down.  Try searching for "Pizza" near "New York, NY".  "Rosario's Deli" in Astoria (the current top result) is probably not what you were looking for. Maybe 1 or 2 of the results on the first page would qualify as top pizza joints in New York.  Anecdotally, I usually look at somewhere between 20 and 50 results before I feel satisfied.

Yelp's search is too difficult to use, even when you know what you're looking for. If I search for "apa Ginos" near "Boston, MA" in Yelp, I get no results.  Google on the other hand (even without the Boston, MA hint) figures out that I made a small typo and returns: "Showing results for papa gino's."

If Yelp doesn't fix search, people will continue to use Google to get to Yelp.  And there's a real risk that eventually they'll stop searching for "Papa Ginos yelp" and start just searching for "Papa Ginos" or even "Papa Ginos [some other site]".


Personalization

NetFlix gets personalization right. I've rated 350 movies on netflix.com, so they know my tastes.  When I log in the first thing I get are "Top 10 Recommendations for Matthew".  When I look at a single movie, I do still see the naive "Average of 521,325 ratings", but the big rating on the page is "Our best guess for Matthew".  I love seeing movies where the second score is much higher, it means there's something unique about that movie that might appeal specially to me!

Yelp doesn't do this.

The first problem is that you can't rate a place on Yelp without reviewing it.  I don't have the time or interest to actually *review* 350 movies or restaurants or gas stations, but I don't have any problem quickly reviewing things as I interact with them. For Yelp to be able to be able to personalize things, they need to start by letting people rate things without reviewing them (even if those review-less ratings don't affect the overall business score).

Imagine what Yelp could do with that data. Search results would be significantly more useful by being tailored (they could know I prefer New York pizza to Neapolitan, and rank things accordingly). As a result, the mobile experience would become much better (you could do less typing if the recommendations were better to begin with).  In general, users would be delighted to find special restaurants particularly suited to their tastes.

That's just be beginning though. Most people eat in a group when they go out. So, when you're picking a restaurant, you're not picking just for yourself, but for a many people.  The multi-person task is way more challenging, but luckily even more ripe for personalization.  When picking a place for, say, four people, it's hard to keep everyone's tastes in mind.  If you could tell Yelp who you're going to dinner with, and get results personalized for all four of you, *that* would be really cool.


Mobile App

Mobile is where Yelp should shine.  However, I use Yelp on-the-go all the time, and am disappointed by the experience (at least on Android, maybe it's better on other platforms).

There's a lot Yelp could do to optimize their app, without fundamentally changing it: Showing suggestions on the landing page without making you click two more times ("Nearby" -> "Resaurants"). Or at least predicting that you're going to click that, and pre-loading it in the background so you're not left waiting once you get there. Incorporating your saved bookmarks into search results. Highlighting places that are currently closed more obviously. Making the suggestions and search results better (see above). Just making the results load faster.

There are even more opportunities exposed by re-thinking the ways people interact with the app.  For example: I've already bookmarked 182 establishments on Yelp, but I always forget to eat or drink at them.  The Yelp app should buzz and remind you when you walk near a bookmark ... especially if the time of day was appropriate (e.g. reminding me about a dinner spot at 7pm is more useful than at 10am).

Or what about a Yelp "continuous" mode when you're in a new city or neighborhood: You tell it that you're looking for lunch in the next hour or so, and who you're with and then you can just start exploring or going about your business.  Yelp can take over the task of searching for places, and just let you know whenever you walk near a place it thinks your group would particularly like.

Conclusion

I really want Yelp to succeed since I think they have awesome data, and I love many of the places I've found using it.  However, to retain their top spot in the world of restaurant recommendations they need to get better at using that data to solve my problems.

Music: k-os - I Wish I Knew Natalie Portman

The Diving Bell and the Linear Search

I watched The Diving Bell and the Butterfly recently. (Note: This isn’t much of a spoiler, but if you don’t like even little spoilers then stop reading.)

In the move, the editor of Elle magazine, Jean-Dominique Bauby, has a stroke and wakes up unable to speak or move any part of his body except for one eye. A speech therapist helps him to communicate by reading the letters of the French alphabet one-by-one. If he blinks his eye during a letter, she writes it down and starts the process over again. Together they slowly spell out words. Using this technique he is eventually able to dictate a book (which inspired the movie).
From wikipedia (unsourced, of course):

"The book took about 200,000 blinks to write and an average word took approximately two minutes"

Two minutes per word? Algorithms could have changed this man’s life!

The approach they used (often called linear search) is inefficient because each operation (the interpreter reading a letter, followed by Jean-Dominique either blinking or not blinking) only rules out at most 1 letter. Using a simple linear search, without sorting for frequency, you’d need 13.5 operations per letter (sometimes just 1, sometimes 26). The speech therapist, however, sorts the list by frequency (putting ‘e’ first) which helps a lot: reducing it to 7.5 operations per letter on average. Check my math here.

However, we can do better by ruling out more than 1 letter with each operation. The best approach is to rule out half of the remaining letters each time. Such a technique might look like this: The interpreter asks: “Blink if the letter is between A and M (inclusive).” Whichever option is chosen, 13 letters are eliminated. Say (for example) it’s a blink for ‘yes,’ we repeat the process on the remaining letters: “Blink if the letter is between A and G,” say there is no blink (meaning ‘no’). Now: “Blink if the letter is between H and J” (yes), “H and I?” (yes), “H?” (no) results in producing an “I” in 5 operations. In fact every letter is reachable in (at most) 5 operations. This is a 33% savings. If you trust Wikipedia, we’ve cut the 2 minute average per word down to 1 minute and 20 seconds. You might notice that as long as you use the same splits every time, the series of blinks and not-blinks will be the same for ever letter every time: A will always be YYYYY, B: YYYYN, etc. Substituting ‘1’s for Y and ‘0’s for N results in a technique that is similar to ASCII codes. ASCII is a very common format for storing text in a computer because it allows letters to be (fairly) efficiently represented in a simple 1 and 0 format.

If all letters were equally common, this would be the best we could do. However, as with linear search we can use letter frequency to our advantage. For example: since ‘e’ is the most common letter, we would like to make it reachable in less than 5 operations, even if that means ‘z’ will take more than 5 operations. In 1954, David Huffman developed a technique which provably produces the most efficient codes (in terms of operations per letter) for a given distribution of letters (the technique is known as Huffman coding). The technique is actually quite simple [1], the proof of optimality is a little more complicated (it’s section 16.3 of CLRS). I wrote a little bit of JavaScript to generate Huffman Codes for English here. The codes I found come out to an expected length of 4.2 operations per letter. Note these codes use Morse Code format (- for a long blink, . for a short blink), since asking questions would be a lot more complicated with these codes. Instead you’d memorize the codes (which seems difficult, but many telegraph operators get quite fast with it). Morse Code, of course, would be another good alternative: It’s slightly less optimal than Huffman codes, but it’s close and people might already be familiar with it). 4.2 operations is a 44% speedup over the baseline, which would get us down to 1 minute 8 seconds per word. Capitalizing on unequal distributions to save space using Huffman codes forms the basis of the zip file format.

It’s possible that the difficulty of dictation was an essential aspect of the book. (Neal Stehpenson writes his books (including the 900+ page Anathem) with a fountain pen to force himself to think about every sentence before he writes it down.) However, it seems unquestionable that this would have aided day-to-day communications.

---

[1] To create Huffman codes for a distribution:
- Begin by listing all the possible letters, with their probabilities
- Repeatedly merge the two smallest remaining probabilities, into a new hybrid node. The node will have a left child and a right child (the old nodes) and a probability equal to their sum. Repeat this process until there is only one node (which will have all other nodes as children).
- To intepret the resulting tree: Assign ‘0′ to left children and ‘1′ to right children. Any letter’s code is the path to get to it (in terms of 0’s and 1’s) starting from the root node.

Music: I don’t need no sample … gotta girl with a banjo

Way more interesting than the Lil Wayne version:

From his page:

• The whole thing is one take
• Audio recorded at the same time its filmed

Thanks to http://twitter.com/davidsiegel for finding it.