Ethan Herdrick

Interest in Spark waning lately? (April 2013)

Spark is far easier to work with than Hadoop, and better for rapid development. Excellent! But the community of Hadoop users is probably two orders of magnitude bigger. That’s bad for Spark. But is the Spark community growing fast enough to make that soon irrelevant?

I counted new topics on the Spark users Google Group by time period.

I was loving that growth until April. It may be that this group didn’t became the home of the community until February, meaning that March is the first full month that can be measured. Whether that’s true or not, as of April 22, April is on track to see fewer new threads than March.

New questions on StackOverflow with Hadoop or Hadoop family tags are at ~135 in the past seven days, a monthly rate of 540. So far there are zero Spark or Shark questions on SO.

(Actually it’s much worse than that. There are some questions on SO about other Shark projects, especially a new Flash/Flex framework by that name. This illustrates the awfulness of the name ‘Spark’. BDAS really blew it in giving their project a name that is a common English word. But that is another post.)

So I am not yet seeing exponential growth in the Spark community. Let’s hope that changes.

The boat engine is worth 33,500 Egyptian slaves

In 1998 Google was worth 1,838,389 workers I proposed measuring the worth of innovations by estimating the equivalent amount of labor ‘saved’ by using them. But how about the great rapid transportation innovations of the 20th century? Surely those can’t be reduced to human power. Much like you can’t make a baby in one month with nine women, no amount of people can make a vehicle go faster than a running human, right? No. You can do it, and with that insight I’ll show you what the human labor equivalent of a 5 horsepower Evinrude boat engine would be in ancient Egypt. In America, pulling a canal barge with horses or mules on the banks was how midwest grain and beef got from the Great Lakes (and so the entire upper midwest) to the Atlantic. But in some sad times and places, labor was so cheap that humans were riverside draft animals ¹. There’s even a name for that job in Russian: Burlak.

Lots of burlaks meant you could haul lots of freight. But with a rope gear - just two spools of different radii ganged together - on an anchored axle you could “gear up” to convert their slow, strong force to a fast weak one. A series of these rigs on the banks of a river, could, with coordination, pull a long, shallow draft boat quickly and continuously. How many burlaks would you need? Let’s say you’ll need 5 horsepower, sustained. I’m pretty sure I could get a long slim, light riverboat with a light load to 20 knots with a 5-horse Evinrude. A person can produce, in a short burst, 1.2 horsepower. Friction between the spool and the axle would eat up some of that, but then the boat engine loses a lot of power to turbulance around the prop, too. So let’s say we need four burlaks pulling at maximum effort at all times. The ancient Egyptians were fine rope-makers - it looks like they could make 100 meter rope strong enough. ² Experience suggests that 5 knots (~5 mph or 8 kph) is about the ideal speed for a human to generate maximum power - think of a footbal or rugby player driving an opponent backward. That’s 1/4 the speed we want our boat to go, so the right gearing would have our burlaks surge forward only 25 meters while the boat they are pulling covers 100 meters. Our rig will need 125 meters of rope - call it 150 meters just in case. We’ll need one of these rigs (a large double spool anchored into the ground, 150 meters of rope, and 5 burlaks) every 100 meters of the trip - about 6700 of them over the 667 kilometers between Luxor and Alexandria. That’s 33500 burlaks. ³

So if we waive the manufacturing costs of the outboard engine and the rope-spool-axle system (and the work needed to supply gasoline for the motor and food for the burlaks), the 5 horsepower outboard engine ⁴, when plopped down into ancient Egypt, does the work of about 33,500 slaves. ⁵

Google was worth 1,838,389 workers in 1998, maybe

What is an innovation worth? I’m not asking how much money it makes, because that’s just part of it. To take an extreme example, if you give an invention away to the public it can still provide value to people, it’s just that you’re not getting any of it, or no more than anyone else. But the cash value of the uncaptured part is notoriously hard to quantify. How about a different approach?

Human labor has always been a fundamental good. And lots of new technologies have been called “labor saving devices”. If we can figure out a way to calculate an innovation’s equivalent in human work, we’d have a measure that works across history, even prehistory. Plus we wouldn’t care if the invention was ‘monetizable’, ex. whether it appeared in a period with a legal system defending private property and maybe patents. ¹ Maybe best of all we don’t have to worry about the value of various currencies over time, and in fact can value innovations that predate money itself.

The value of some new ideas seems well captured by measuring how much human work they replace. Manufacturing and hanging drywall needs much less effort than lath and plaster. Dynamite and bulldozers remove rock with much less effort than picks and shovels. ² But what labor is saved by the jet engine? All the laborers in the world couldn’t get you from San Francisco to New York in six hours. ³

Google’s search engine seems to be like that - not a labor saver but something that does what was before impossible. Is it though? Could you measure the value of Google by how much labor it would take to replace it? I think you can. What if, instead of Google’s new software, you just had people? Could you build such a system that could rival, if not today’s Google, then the first Google search engine, from 1998? Google was searching over only 26 million pages at the time. Couldn’t you fulfill a query over those pages given enough ‘librarians’? If we can value even Google this way, then maybe we’ve got a useful scale for innovation.

How about if you divided up the web among your librarians? Before reporting for duty, each would read each page in his or her balliwick and remember, more or less, what they say. It’s not so unrealistic if you assign people to pages pertaining to things they already know something about. Of course most pages weren’t really about anything, then perhaps more than now. The blog hadn’t been formally invented ⁴ but ‘home pages’ seemed to make up a majority of the web and few of them were about anything other than the author and his interests. Here’s a surviving example that exemplifies the species: http://jerrypournelle.com/ Notice the multiple sections, “Books and Movie reviews”, “What’s new”, “Reader email”, etc. Remembering what was mentioned in one of those pages wouldn’t be easy.

We can make it easier. Let’s give each librarian the software from one of the existing, crummy pre-Google search engines (or maybe just grep) and set it up so search only their 100 pages. That will give the librarian a good quick start, jog his or her memory, and help a lot with the kind of things that unsophisticated software is good at, like finding exact matches of sentence fragments.

If we assign 100 web pages to each person and their search engine, we’d have the 26 million pages covered by 260,000 librarians. But what if you search for something common, like bill clinton and most of those 260,000 librarians have results? How to pick among them? This is really what the search engine that Google launched in 1998 did that was so great. Its results were ordered in a way that seemed like magic. You searched for that sherlock holmes story with the snake and the first result was The Adventure of the Speckeled Band. To replicate that we’re going to need more people to sort out the work of those first 260k people. We need editors.

Let’s start with a layer of editors above the librarians. We assigned 100 pages to each librarian, so why not 100 librarians per editor? That’d be 2600 editors. When a dump of those bill clinton results comes in to an editor, he or she picks the 10 best, in order, and passes them on, declaring them the best 10 results from the 100 librarians he edits. Each of those are assigned 100 web pages, so the the editor’s top 10 results are the best from the 10,000 pages his librarians cover. Now we’ve got 10 results each of our 2600 editors. We need to whittle these down to 10 results to show to the user, who is still staring at the screen, waiting. You can see that all we need are more layers of editors. log base 100 of 260,000 is 2.7 so a total of three layers of these editors is enough. That’ll give us 260,000 librarians, 2,600 first level editors, 26 second level ones, and 1 chief editor: 262,627 workers. If it takes a minute for each layer to do its work, which seems reasonable, then a user gets a result back in three minutes, and the system can handle one query per minute. ⁵ That’s not much. Luckily this system is easily parallelized. To get another query per minute we simply add another 262,627 workers searching over the same 26 million pages. Apparently Google was doing 10,000 searches per day in 1998. That’s about 7 per minute. ⁶ To handle that at a steady state, we’ll need 262,627 * 7 = 1,838,389 workers. ⁷

There you go. On the day Google launched they were providing, free of charge and with less than 1/120th the latency, what you’d need 1,838,389 smart workers to do the day before.

Does this technique work as a scale of innovation? Well, it’s got the nice advantages I mention above. But it can only give you an upper limit on the value of the innovation, since if it paid to do it the labor intensive way, that would have been happening. ⁸ It needs improvement. What do you think?

Tweet

Follow me on Twitter

Facebook checkin to become the new price for free wifi

Just showing up at Coupa Cafe and connecting to their wifi now automatically does a Facebook checkin there. Good idea for the local business. And when this spreads to embaressing locations it’ll make your Facebook feed a lot more interesting, so it’s good for Facebook too!

Seriously, I think it only checks you in if you’ve already accepted thier TOS once. So the loss of privacy is probably in the ‘one more step’ sweet spot. I predict ubiquity.

My newest hack (with Dave Brushinski)

http://endrank.com/crunchbase

“The Crunchranked.  The 217,000 most important companies, financial firms, and people in the startup world, according to an impartial algorithm.”

Comments: http://news.ycombinator.com/item?id=3805555

Display git branch and ‘dirty’ status in fish shell prompt

Dissatisfaction with the bash shell, and the feature list and humorous promotion of the new fish shell fork (“Finally, a command line shell for the 90s… You’ll have an astonishing 256 colors available for use!”) spurred me to try fish out for a few days. It’ll have to be a lot better than bash to make worthwhile leaving the large bash community and its google-able answers. We’ll see.

The customization in my bash .profile I can’t live without [1] is showing the current git branch in the command prompt. Googling this feature for fish got me most of the way there, with the code found here: https://wiki.archlinux.org/index.php/Fish#Configuration_Suggestions . But it didn’t quite work.  Below is what I got to work. As it also shows if you have staged or unstaged changes I like it better than what I had in bash.

set fish_git_dirty_color red

function parse_git_dirty 

         git diff —quiet HEAD ^&-

         if test $status = 1

            echo (set_color $fish_git_dirty_color)”Δ”(set_color normal)

         end

end

function parse_git_branch

         # git branch outputs lines, the current branch is prefixed with a *

         set -l branch (git branch 2> /dev/null | sed -e ‘/^[^*]/d’ -e ‘s/* \(.*\)/\1/’) 

         echo $branch (parse_git_dirty)     

end

function fish_prompt

         if test -z (git branch —quiet 2>| awk ‘/fatal:/ {print “no git”}’)

            printf ‘%s@%s %s%s%s (%s) $ ’ (whoami) (hostname|cut -d . -f 1) (set_color $fish_color_cwd) (prompt_pwd) (set_color normal) (parse_git_branch)            

         else

            printf ‘%s@%s %s%s%s $ ’  (whoami) (hostname|cut -d . -f 1) (set_color $fish_color_cwd) (prompt_pwd) (set_color normal)

         end 

end

[1] Actually the best customization is changing the maximum size and count of the .bash_history file to be really big so that I can keep a lifetime of shell work.

Professor Sebastian Thrun quits Stanford to teach people

One of the most amazing things I’ve ever done in my life is to teach a class to 160,000 students. In the Fall of 2011, Peter Norvig and I decided to offer our class “Introduction to Artificial Intelligence” to the world online, free of charge. We spent endless nights recording ourselves on video, and interacting with tens of thousands of students. Volunteer students translated some of our classes into over 40 languages; and in the end we graduated over 23,000 students from 190 countries. In fact, Peter and I taught more students AI, than all AI professors in the world combined. This one class had more educational impact than my entire career. Just watch this video.

Now that I saw the true power of education, there is no turning back. It’s like a drug. I won’t be able to teach 200 students again, in a conventional classroom setting. I’ve just peeked through a window into an entire new world, and I am determined to get there.

(and yes, I gave up my tenured position at Stanford)

Kill hashtables, get shorter code

Driving late at night two months ago I wondered, why do we return hashtables from functions?  Isn’t a hashtable like a function?  Instead of calling some function to get a hashtable, then looking up values on that hashtable with keys, why not simply call the function directly each time I want a value?  Just make the ‘key’ the last argument of the new function.  So I tried it on the code from my last post, where I explained hierarchical document clustering and showed some Clojure that does it.  In this post I’ll show how I eliminated hashtables in that code and got a shorter codebase, comparing the already pretty short original to the new code.  

The best way to show the change will be to walk you through what happens in a call to euclidean, which calculates the euclidean distance of two documents or an arbitrarily deep tree of documents, based on their word frequencies.    

In the original, ordinary version, I get a hashtable of the word frequencies of a tree of documents with a call to freq, which recursively combines the frequencies (hashtables) of the branches of the tree, ultimately calling freq-files on each leaf, which is a document, of the tree. freq-files returns a hashtable of frequencies for that a document.  We will pass the hashtable we get back from freq into euclidean.

In contrast, in this new version, we just call euclidean before getting any frequencies. euclidean calls freq once for each word in the corpus.  Each call to freq calculates the frequency for just that one word, again by recursively combining the frequency of that word of each of the branches, and ultimately calling freq-files on each document in the tree, which calculates just that word’s frequency for that document.  

This is a little weird.  Do you see what has happened here?  That data now is no longer represented with a hashtable - instead it’s not represented at all.

Doing all those function calls sounds grossly inefficient but it shouldn’t.  For one thing, who cares?  It’s just performance.  We can always profile and deal with problems like that later.  But second, it isn’t really any less efficient than getting the whole document worth of frequencies all at once, because now I’m memoizing - caching function return values.  I’ve wrapped all of the functions in that chain of calls down to and including freq-files (and beyond) in memoize [1].  For example, it looks like I’m reading files from disk every time I call freq-files.  But memoizing to-words prevents that, so following a first call, every time freq-files is called with the same file tree (but probably a different word) the memozied to-words returns a cached word list. frequencies-m (the memoized version of frequencies), is in turn called with that word list as its argument, a call which would be somewhat computationally costly but since it has a cached value associated with that argument it simply returns that.  This frequency needs to be relative, so we’ve got to divide by the word count of the doc.  I’ve got count wrapped in memoize too, calling it count-m, which I call on the results of calling to-words again, which again returns a cached value.  

The really cool thing is that that data is still there.  It’s just that you don’t see it or manipulate it in the code anymore.  It’s implicit.  

This change chops the code down by about 20%, from 55 non-comment lines of code to 44 (or 39, not counting the boilerplate function memoization, which would be a 30% reduction) [2]. 

This style of programming has downsides.  For me, wrapping functions in memoize means my editor / IDE can’t tell what arguments my functions take any more (a common problem when you have first class functions).  That sort of sucks.  Further, it makes some functions, like euclidean, hopelessly non-general, since euclidean now has to know what function to call to get a frequency [3].  It makes it harder to track down bugs.  When you get all the values you want from each function in a chain of functions, always passing the entire hashtable of them up the chain, it’s easier to figure out where a problem has come up than if you ask about a single value all the way down the call chain.  But the main disadvantage to this technique is that it doesn’t match the way I code.  I like to program very interactively.  For example, the first thing I did when I started coding this stuff up was to slurp up the documents in question and call frequencies on them.  With the resulting hashtables in hand I wrote code to find the distance between two document “vectors”.  With these distances I wrote the code to find the shortest ones, and so forth.  Calling the entire function chain to get each value is only possible after you’ve written that chain of functions.  While you’re building them it’s easier to pass all the data from each step to the next step.  But I haven’t really tried coding in this style from scratch yet, so who knows?  Maybe it’s got some other hidden advantage I don’t know about. 

But it’s hard to argue with brevity.  And by the way, there’s nothing inherently lisp-ish about this technique.  You can do it in any language with first class functions, like Python or Ruby, just as easily.

Comment on this post at News.YC.

In the Bay Area and need help with your machine learning project? Contact me at info@reatlas.com or twitter.com/herdrick  

[1]  And we’ve been doing some of that all along anyway, since we often call freq with the same arguments, over multiple calls to euclidean.

[2]  There’s actually another related change here that isn’t so interesting, but definitely helped.  In the original version, the word-list - the list of all words that appear somewhere in the documents - is calculated immediately upon calling cluster, and passed into each subsequent recursive call to cluster.  From there it’s passed into best-pairing, which passes it into euclidean, the only place where it is actually used. I did this because getting this list requires some file reading and computation and it seems ineffiecient to recalculate it every time I call euclidean, which is a lot. But that was the wrong way to think about this problem. When I went ahead and did the inefficent thing, the right fix became clear: memoization, again.  best-pairing’s argument is a list of file-trees in which every file in our corpus is represented, so we can calculate our list of words from that - so I did.  Now every call to euclidean makes a call to word-list.  But this isn’t such a problem because word-list and most of the functions it calls are memoized.  So the only additional cost of calling that function are several memo lookups - negligible - and flattening and sorting a file tree.  Which isn’t nothing but I don’t think it’s a big deal.  I should profile it to find out.

[3] Actually I could make euclidean more general by just sticking with the original version.  Because Clojure hashtables can be called as functions, I can just call euclidean like this: (euclidean (partial freq pof1) (partial freq pof2) (word-list pofs)), using closures created with partial function application as the frequency arguments.  Seemed a little harder to explain though, so I skipped it.

Cluster (with Clojure)

I was watching a video of Berkeley professor Michael Jordan lecturing on the Chinese Restaurant process and for a moment he showed a slide of a tree of documents that were matched up by word frequencies.  It seemed cool so I coded up my own version of it, mostly to learn about the topic and to get some practice with Clojure.  It turned out there’s a name for this:  hierarchical clustering.  I went with the ‘agglomerative’ version of it, which is repeatedly pairing up things and pairs of those things until you have a single pairing that, beneath it, contains everything you started with.  Usually you choose pairings based on similarity - you pair up the two available things that are most similar. 

To make documents into something you can easily compare, I’m converting each into a hashtable of the relative frequencies of the words it contains, like this:  {"purple" 0.0015, "it" 0.0023, "this" 0.0083  ...}  etc.  The code finds the two most similar docs based on those frequencies, and matches them up, making a new hashtable like that by averaging the frequencies of those two docs [1]. This “pairing” is now on the same footing with all the other documents.  So we again find the two most similar docs (allowing this new pairing to be treated as a doc), repeating that process until we’re left with only a single pairing.  It contains every pairing we made, and ultimately every document we started with.  This is our finished product, a hierarchical cluster.

You can see the code on my GitHub.

I turned it loose on some text files got the following (plotted with the Protoviz Javascript toolkit) [3]

The blue nodes are the documents and the green nodes are pairings.  From top to bottom, the docs are: 

-the German Wikipedia article on the lambda calculus,
-the first several hundred words of a German novel, Wilhelm Meister’s Apprenticeship by Johann Wolfgang von Goethe,
-an exerpt from Shakespeare’s King Lear,
-the scifi short story, “They’re Made out of Meat”,
-the English Wikipedia article on the lambda calculus,
-the English Wikipedia article on “The Buzzer” or UVB-76,
-the Sherlock Holmes story, “The Red Headed League”,
-the Sherlock Holmes story, “A Scandal in Bohemia”,
-the scifi short story, “The Long Watch” by Robert Heinlein,
-Shakespeare’s first and second sonnets,
-Shakespeare’s third and fourth sonnets,
-the Spanish poems, “Candor” and “Reto” from Julio Flórez,
-the Spanish Wikipedia article on the lambda calculus,
-the Spanish Wikipedia article on functional programming,
-the Dutch Wikipedia article on the lambda calculus,

Notice that each pairing shows three words.  Those are the most ‘interesting words’: those whose frequencies do the most to make that pairing stand out from the average.  For example, if you’ve got a document that uses the word “mooloolaba” a few times, that’s probably going to be one of its interesting words because it’s so rare elsewhere.  But a word could also be interesting for not showing up, ex. if the word “the” never shows up in a document or only a few times in a long text.  In that case the word is in parens.

It seems to have done an OK job here.  It strongly leans toward matching up docs (and pairings) in the same language when possible.  I was hoping that it would be able to pull out the two science fiction stories, but that isn’t happening.  It’s not smart enough for that.  I’m pleased that it grouped the Spanish functional programming and lambda calculus articles before inluding the Spanish poetry.  It put Shakespeare’s sonnets together, but failed to associate them very closely with the exerpt from King Lear.  [4] 

I was also hoping the Dutch and German articles would clusted together before being joined with the Spanish or English docs, but this didn’t happen.  It might be that “de” is a common word in Dutch and Spanish, whereas “is” and “in” are common in Dutch and English.  So the classifier might see Dutch documents as partway between English and Spanish ones (even though the opposite is closer to the truth).  

Interesting.  I think this could be improved by using a statistical distance to measure the distance between vectors, instead of unscaled distance of relative frequencies as I’m doing now.

In playing with this code I stumbled on a interesting way to refactor it.  I’ll talk about that in the next post.

[1] This is called the vector space model, declaring each word to be a dimension, and each document a point, or vector, in that word-space.  Identifying docs by the words they contain and not worrying about word order is in general called using the “bag of words”.  I’m comparing those frequencies using Euclidean distance.  It’s often said to be better to use the cosine of the two vectors but that doesn’t matter here since the dimensions of any document vector sum to 1 (is there a name for such a vector?), and I’m only looking for a ranking of distance.

[2] I omitted the thirty lines of code to translate the s-expression result to the JSON needed for Protovis.

[3] I found in trial runs over all of Shakespeare’s sonnets that it did a pretty good job of sorting out the earlier sonnets from the later ones.

[4] The regular expression I used for extracting words is poor for non-English languages, but the algorithim can probably handle it anyway, as the fragments it creates will be unique to the words they came from.

In the Bay Area and need help with your machine learning project? Contact me at info@reatlas.com or twitter.com/herdrick