Surprise and Coincidence - musings from the long tail

Buzzwords Keynote - Conclusion

2011-06-22T14:06:00.000-07:00

In the end, it is up to us to make things better. We need a way for non-Apache entities to interact with Apache productively. If we can't do that, then it is quite possible that all of the momentum and excitement that Hadoop now has will be lost.

Conclusion

The key is that we now have an eco-system, not just a community. We can make it work. Or we can elect to let it not work. Not working is the default state. We have to take positive action to avoid the default.

Apache can stay a strong voice for business friendly open source by remaining Apache. Trying to make Apache broad enough to include all of the players in Hadoop and Hadoop derivatives will simply debase the voice of Apache into the average of opposing viewpoints, i.e. into nothing.

There are, however, many other players who are not part of Apache and who should probably not be part of Apache. There needs to be a way for these others to engage with the Apache viewpoint. It can't just be on the level of individuals from Apache trying to informally spread the Apache way even though that is critical to have. It is likely to require a venue in which corporate entities can deal with something comparable to themselves. A good analogy is how Mozilla participation in W3C has made the web a better place.

But we can make our eco-system work. It isn’t what it was and it never will be again.

But it can be astonishing

Let's make it so.

Buzzwords Keynote - Part 3

2011-06-22T14:04:00.000-07:00

In the third part of my talk, I talked a bit about where Hadoop has come from and where it is going. Importantly, this involves a choice about where Hadoop and the related companies products and individuals might be able to take things.

Where we are and how we got here

My second section described the rough state of the Hadoop eco-system is a slightly provocative way. In particular, I described a time when I was on a British train and in partial compensation for delays the operators announced that "free beer would be on sale in the galley car". Free beer for sale is a wonderful analogy for the recent state of Hadoop and related software.

That said, there are serious problems brewing. The current world of Hadoop is largely based on the assumption that the current community is all that there is. This is a problem, however, because the current (Apache-based) community presumes interaction by individuals with a relatively common agenda. More and more, however, the presence of a fundable business opportunity means that this happy world of individuals building software for the greater good has been invaded by non-human, non-individual corporations. Corporations can't share the same agenda as the individuals involved in Apache and Apache is constitutively unable to allow corporate entities as members.

This means that the current community can no longer be the current world. What we now have is not just a community with shared values but is now an eco-system with different kinds of entities, multiple agendas, direct competition and conflicting goals. The Apache community is one piece of this eco-system.

Our choice of roads

Much as Dante once described his own situation, Hadoop now finds itself in the middle of the road of its life in a dark wood. The members of the Apache community have a large voice in the future of Hadoop and related software.

As a darker option, the community can pretend that the eco-system that now exists of human and corporate participants is really a community. If so, it is likely that the recent problems in moving Hadoop forward will continue and even get worse. Commit wars and factionalization are likely to increase as corporate entities, denied a direct voice in Apache affairs, will tend to gain influence indirectly. Paralysis in development will stall forward progress of Hadoop itself leading to death by a thousand forks. Such a dark world would let alternative frameworks such as Azure to gain footholds and possibly to dominate.

In this brighter alternative future, I think that there are ways to create a larger forum in which corporate voices can be heard in their true form rather than via conflicts of interest. In this scenario, Apache would be stronger because it really can be a strong voice of the open source community. Rather than being the average of conflicting views, Apache would be free to express the shared values of open source developers. Corporations would be able to express their goals, some shared, some not in a more direct form and would not need so much to pull the strings of Apache committers. Importantly, I would hope that Hadoop could become something analogous to a reference implementation and that commercial products derived from Hadoop would have a good way to honor their lineage without finding it difficult to differentiate themselves from the original. Hopefully in this world innovation would be welcomed, but users would be able to get a more predictable experience because they would be able to pick products offering whatever innovation rate/stability trade-off that they desire. Importantly, there would be many winners in such a world since different players would measure success in different terms.

We have a key task ahead of us to define just what kind of eco-system we want. It can be mercenary and driven entirely be corporate goals. This could easily happen if Apache doesn't somehow facilitate the creation of a forum for eco-system discussion. In such an eco-system, it is to be expected that the companies that have shown a strong talent at dominating standards processes and competing in often unethical ways will dominate. My first thought when I imagine such a company is Microsoft, but that is largely based on having been on the receiving end of their business practices. I have no illusions that talent for that kind of work is exclusively found in Redmond.

In my talk, I proposed some colorful cosmological metaphors for possible worlds, but the key question is how we can build a way for different kinds of entities to talk. It is important to recognize different values and viewpoints. Apache members need to understand that not everything is based on individual action, nor do corporation hold the same values. Companies need to take a strong stance to recognize the incredible debt owed to the Apache community for creating the opportunities we all see.

If we can do this, then Hadoop (and off-spring) really does have a potential to dominate business computing.

Buzzwords Keynote - Part 2

2011-06-22T14:02:00.000-07:00

In the first part of the talk, I made the case that Apache Hadoop has lots of head-room in terms of performance. This translates into lots of opportunity both for open source developers to make Hadoop itself better, but also for companies to build products that derive from Hadoop but improve it in various ways.

The $S$ score

In honor of Steve Jobs whose highest praise is reputedly to say "that doesn't suck", I proposed an $S$ score whose highest score is zero, but for all real systems is always negative. For a batch, data processing system like Hadoop, I proposed that a good definition of $S$ was the log base 10 of the ratio of the actual performance to the performance implied by hardware limits.

Not suprisingly, the overall score for Hadoop comes out to be somewhere between -5 to -2 depending on desired workload (i.e. Hadoop runs programs somewhere between 100 and 100,000 times slower than the hardware would allow). For some aspects, Hadoop's $S$ score can be as good as $-0.5$ but generally there are multiple choke-points and some of these are additive. This is hardly news and isn't even a mark of discredit to Hadoop since the developers of Hadoop have always prized getting things to work and to work at scale above getting things to work within an iota of the best the hardware can do at a particular scale. Another factor that drives $S$ down for Hadoop is the fact that the hardware we use has changed dramatically over the 6-7 year life of Hadoop.

In defining the value of $S$ for current Hadoop versions, I don't mean to include algorithm changes. Michael Stonebraker has become a bit famous for running down Hadoop for not doing database-like things with database-like algorithms, but I would like to stick to the question of how fast Hadoop could do what Hadoop is normally and currently used to do.

The key conclusion is that having such a low $S$ combined with high demand for Hadoop-like computation represents a lot of opportunity. This opportunity involves opportunities for the open source community to make things better. It also represents opportunities for commercial companies to make money. The latter kind of opportunity is what is going to shake up the currently cozy Hadoop community the most.

Buzzwords Keynote ... blog edition

2011-06-22T14:00:00.000-07:00

There has been a bit of demand for an expanded version of my Buzzwords keynote from a few weeks ago. This demand has been increased by a particular unfortunate mis-quote in a tweet that suggested that I thought that there was a need for a new organization "to supersede Apache". Of course, I suggested nothing of the sort so it is a good idea to walk through the ideas that I presented. The buzz words site has the video of my talk and pdf of my slides in case you want to follow along.

The talk was divided into several sections. The first one proposed the uncontroversial thesis that Hadoop performs at a level far below the potential offered by modern hardware. A second section pointed out difficulties with the current social structure surrounding the development of Hadoop and related software. I then examined what I see as possible futures while describing how I think we will be choosing between these alternative futures. I will post each section in a separate blog entry.

As I spoke, I encouraged the audience to tweet using the hash-tag #bbuzz and to keep communal notes on a shared Google document. The tweets are a bit hard to find as befits ephemeral media, but the shared notes are still accessible.

Sections:

The S Score
Possible Futures
Conclusion

Buzzwords Wrapup

2011-06-20T21:06:00.000-07:00

Well, Buzzwords is over and my primary conclusion is that I wish I had come last year as well as this year. Isabel and Simon are really making Buzzwords into a major open source conference and with the demise of the European ApacheCon, Buzzwords is probably the the first or second most important open source conference in Europe. If you only can choose one, I would strongly recommend geeking in Berlin. It isn't just the conference; there are bunches of related events such as informal dinners, bar camps and hackathons. Since Buzzwords makes such a strong effort to include North American participants you may even have a better chance of connecting globally by going to Europe than going to a conference in the US or Canada.

The conference itself consisted of two days of scheduled events anchored by keynotes each day. Doug Cutting gave the first keynote and covered a lot of the history and current state of Hadoop. As always, his talk was very well done and contained quite a bit of technical information which is refreshing in a keynote. I gave the second keynote and talked a bit about the state and future of Hadoop, related Apache projects and the burgeoning commercial marketplace. Some of what I said stirred up a bit of talk, which is good since my primary thesis that we aren't talking enough about how the world of Hadoop and related software is rapidly changing in ways that aren't well recognized. Stay tuned here for a blog edition of my talk.

There were quite a few excellent technical talks as well. Among the scheduled talks, Jonathan Gray gave a talk which his usual and customary dose of excellent technical information about how Facebook is using Hbase. A notable moment came when he was asked about the state of Cassandra at Facebook. Check out the upcoming video for details on his answer.

Dawid Weiss gave an excellent talk on finite state automata and the difference between deterministic and non-deterministic variants. The only defect I could see in his presentation was that we couldn't see the eagles on the coins. Based on the fact that the room was packed (I sat in the aisle on the floor) and the very eager audience questions, I would say that there is a surprisingly strong market place for information on foundational algorithms like finite state transformers.

The lightning talks at the end of day two also had some gems. Thomas Hall's northern accent blended charmingly with the frank assessment of some of his experiences with certain technical approaches. I can't possibly convey the tone and content so, yet again, you will need to refer to his slides and the video on the conference web-site.

Frank Scholten also had a lightning talk that contained a very nice walk-through of Mahout document clustering. What he showed is a work in progress, but already what he has provides a highly requested set of recipes to illustrate a lot of the software in Mahout.

Outside of the conference there was an (excellent) barcamp run by Nick Burch. I think I learned as much about how to run a barcamp by watching him as anybody did from any of the technical discussions and the technical discussions were pretty excellent.

I have to say that if you want to see me next year in early June, there is a high likelihood that you will have to be in Berlin to do it.

See http://berlinbuzzwords.de/wiki/linkstoslides to get slides from talks.

The Best Illustration of a probability Distribution

2011-06-08T16:04:00.000-07:00

Describing a probability distribution in the abstract to a novice is often difficult.

Here it is in concrete form. Note how some keys are more worn than others. This is in Germany so that the ground floor is labeled "0". Note the wear on the "door close" button!

Visit to DIMA at Technische Universitaet

2011-06-08T16:00:00.000-07:00

I had a great visit today at the DIMA laboratory at TU in Berlin. They are working on an interesting system called Stratosphere which provides an interesting generalization generalization of map-reduce. Of particular interest is the run-time flexibility for adapting how the flow partitions or transfers data.

They accomplish this by having a lower level abstraction layer that supports a larger repertoire of basic options beyond just map and reduce. These operations include match, cross product and co-group. Having a wider range of operations and retaining some additional flow information at that level allows them to do on-the-fly selection of the detailed algorithm for different operations based on the statistics of the data and the properties of the user-supplied functions.

Here's a pic of me answering questions about startups and log-likelihood ratio tests.

A Tour of the Multi-update For Zookeeper

2011-06-01T18:02:00.000-07:00

I have recently been working on some new features for Apache Zookeeper that represent probably the largest change in the Zookeeper client API in several years. Other recent changes such as observers and read-only clusters have changed the server-side semantics, but the client API is nearly unchanged since the original public release of Zookeeper several years ago. The JIRA covering the overall issue is Zookeeper-965 and you can look at the code as it is being refined into committable state in my fork of Zookeeper that I keep on github.

(related announcement)

The Problem

Almost from the beginning of the Zookeeper project, there have been repeated questions on the mailing about how to update several nodes at once. The answer has always been to consolidate the structures that you need to update atomically into the contents of a single znode and then update those contents atomically using standard methods. This update problem is often exacerbated by a desire to use ephemeral nodes so that state disappears correctly when a service crashes.

This is a pretty reasonable answer and it handle many important cases fairly well. For instance, in the common case of servers that are assigned certain roles and then in turn advertise which roles they have successfully taken on, this pattern can be used by giving each server a single file of assignments and a single file of advertised capabilities. Each of these files can be ephemerally created by the server so they will both vanish when the server disappears. Assignments can be added atomically and only the server ever modifies the advertised roles. Zookeeper works quite well in these cases.

Keeping track of a graph full of nodes with directional connections to other nodes is a good example of where Zookeeper's update model is not so nice. In this case, nodes have a list of connections to other nodes and a list of connections from other nodes. If any node has a list of outgoing connections that are not matched by the corresponding list of incoming connections on other nodes, then the graph is referentially inconsistent. Keeping the graph consistent under changes is not possible with normal Zookeeper updates unless you store the entire graph in a single file.

Lazy Operations

The new multi() method allows such a data structure to be updated with strong guarantees of consistency. This is done by currying the normal database mutation operators and then passing all of the resulting closures to Zookeeper at once for execution. Obviously this requires a bit of syntactic sugar in languages like Java and C which don't like to express closures directly.

The way that this works is that there is a new class call Op. There are sub-classes of Op called Op.Create, Op.SetData, Op.Check and Op.Delete that correspond to the operations normally invoked by calling the similarly named methods on a ZooKeeper object. In essence, these sub-classes of Op represent reified methods or closures that can be frozen at one point in time and then executed later. These sub-classes are instantiated using factory methods on Op class. The names and signatures of these factory methods mimic the corresponding methods on ZooKeeper.

Once you have all of the operations you would like to perform, you can execute them all in a single transaction using ZooKeeper.multi(). This will either execute all of the Op's or none of them.

An Example

I have placed an example program for doing a graph-based computation over on github. This program builds a graph consisting of 32 nodes in the form of a 5-dimensional hyper-cube and then uses a numerical technique called over-relaxation to solve for the voltages that would result if all the links in the hyper-cube were replaced by unit resistors. A picture of the graph is just to the right. In this graph, the voltage for node 0x1F is labeled as $V_5$ and the voltage for node 0x0 is labeled as $V_0$. There are lots of connections and solving this problem analytically is difficult unless you twig to the trick of using symmetry. Real-world networks generally don't exhibit such congenial properties and can be nearly impossible to solve analytically.

Normally, of course, we wouldn't actually use Zookeeper for this computation, but the point here isn't so much a realistic computation as a test-bed for the new multi() method and a demonstration of how the closure based style associated with multi-ops makes code easier to read and understand.

The Code

To read the code, start with the class ZGraphTest. This is a JUnit test that drives all the rest of the code. In this test, a graph is constructed (named zg in the code), nodes are connected in the pattern of a hyper-cube which means that nodes are labeled with integers from 0 to 31 and a node $n_1$ is connected to another node $n_2$ if $n_1$ and $n_2$ differ in exactly one bit.

In each iteration of the code, the ZGraph.reweight() method of the graph is called on a randomly selected node. This sets the value at that node to be the average of the values at the neighbors of that node. This computation converges geometrically to the correct value with errors decreasing by a factor of 5-10 with every 1000 iterations. As the actual computation proceeds the error versus the theoretically known correct values is shown every 1000 iterations and you can see the errors go to zero with 6 significant figures at about 7000 iterations.

Internally, a ZGraph keeps a connection to Zookeeper and the name of the root directory for all of the nodes in the graph. Methods like connect(), reweight() and update() all work by defining lazy update or version check operations on Node objects and then executing all of the update or version checks at one time in a transaction. For instance, in the reweight() method, this code gets the weight of all of the neighbors of node g1:

double mean = 0;

Set neighbors = g1.getIn();

List ops = Lists.newArrayList();

for (Integer neighbor : neighbors) {

Node n = getNode(neighbor);

ops.add(n.checkOp(root));

mean += n.getWeight();

}

As a side effect, we also collect a list of version check operations into the list ops. Then in this code we add one more operation to set the weight on g1 and add the update operation to the list ops:

// set up the update to the node itself

g1.setWeight(mean / neighbors.size());

ops.add(g1.updateOp(root));

Finally, multi() is called to actually do all of the version checks and updates that we have collected,

zk.multi(ops);

The essential point here is how the list of operations was collected a bit at a time and then executed all at once. The versions of the nodes that were inputs into the operation were collected in the form of check operations. When those check operations are executed along with the update of g1, we guarantee that g1's new weight will accurately reflect the average of its neighbors and if somebody changes the value of any of the neighbors in between the time that we read the value and the time we actually do the update, we will run the update again.

Similarly, and closer to the idea of maintaining referential integrity, the ZGraph.connect() collects update operations for the two nodes being connected and executes both updates together to avoid the possibility that anyone would see a situation where one node connects to a second but the second doesn't have the reverse connection. This code does the job,

Node g1 = Node.readNode(zk, root, id1);

Node g2 = Node.readNode(zk, root, id2);

g1.connectTo(id2);

g2.connectFrom(id1);

zk.multi(Arrays.asList(g1.updateOp(root), g2.updateOp(root)), results);

Again, the closure passing style makes this operation very easy.

One additional point to be noted is that having each Node return closures for updates that can be executed in any context the caller would like has the effect of removing all direct Zookeeper operations from the Node other than for reading or creating a node. It also removes all references to serialization of a Node from any outside code. This simplifies both the caller and the Node because the Node doesn't have to implement all plausible combinations of multiple updates and the caller doesn't have to worry about any aspect of serialization and can focus on the appropriate task of arranging the transactional semantics for updates.

Credit Where Credit is Due

Of course, this new Zookeeper capability wouldn't be possible if the Apache Zookeeper project team hadn't built Zookeeper in a very flexible way in the first place. Kudos to Ben Reed and Mahadev and the other early committers on the project.

Also, the actual Zookeeper-965 project would have stalled out if Marshall McMullen and Camille Fournier hadn't stepped in with a bit of extra momentum. I had completed the wire protocols and all of the client side work, but Marshall did all of server side work and Camille provided really excellent advice about how the changes should be done.

The final credit goes to MapR Technologies for supporting open source by allowing capabilities like multi to be contributed back.

Online algorithms for boxcar-ish moving averages

2011-05-29T11:51:00.000-07:00

One problem with exponentially weighted moving averages is that the weight that older samples decays sharply even for very recent samples.

The impulse response of such an average shows this clearly. In the graph to the right, the red line is the impulse response of the exponential weighted average is shown by the red line. The impulse response of a different kind of moving average derived by John Canny in the early 80's is shown by the black line.

The Canny filter puts higher weight on the events in the recent past which makes it preferable when you don't want to forget things right away, but do want to forget them before long and also want an on-line algorithm.

The cool thing about the Canny filter is that it is only twice as much work as a simple exponential moving average. The idea is that if you take the difference between two exponentially weighted averages with different time constants, you can engineer things to give you an impulse response of the sort that you would like.

The formula for such a difference looks like this
\begin{eqnarray*}
w(x) &=& k_1 e^{-x/\alpha} - k_2 e^{-x/\beta}
\end{eqnarray*}
Here $k_1$ and $k_2$ scale the two component filters in magnitude and $\alpha$ and $\beta$ are the time constants for the filters.

It is nice to set the magnitude of the filter at delay $0$ to be exactly 1. We can use this to get a value for $k_2$ in terms of $k_1$
\begin{eqnarray*}
w(0) &=& k_1 - k_2 = 1 \\
k_2 &=& k_1 -1
\end{eqnarray*}
Similarly, we can constrain the slope of the impulse response to be $0$ at delay $0$. This gives us $\beta$ in terms $\alpha$
\begin{eqnarray*}
w'(0) &=& {k_1 \over \alpha} - {k_2 \over \beta} = 0\\
{k_1 \over \alpha} &=& {k_1-1 \over \beta} \\
\beta &=& \alpha \frac{ k_1-1} { k_1}
\end{eqnarray*}
The final result is this impulse response
\begin{eqnarray*}
w(x) = k \exp \left(-{x \over \alpha}\right)-(k-1) \exp\left(-{k x\over \alpha (k-1)}\right)
\end{eqnarray*}
We can do a bit better if we note that as $k \to \infty$, the shape of the impulse quickly converges to a constant shape with mean of $w(x) \to \frac{3a}{2}$ and a total volume of $2a$.

Exponentially weighted averaging for rates

2011-03-24T12:24:00.000-07:00

In a previous post, I talked about how to produce exponentially weighted averages of time-embedded values. This is fine for cases where you really want averages, but it doesn't work for rates. Happily, the technique I presented for simple averages can be easily extended to work for rates as well.

To recap a bit, an on-line algorithm for computing a simple average works by accumulating the number of observations and the sum of the observations. There is no mention of time. For each observation $(x, t)$ we update our state $(s, w)$ according to
\begin{eqnarray*}
s_{n} &=& s_{n-1} + x \\
w_{n} &=& w_{n-1} + 1
\end{eqnarray*}
The exponentially weighted average approach that I mentioned before uses the time of each observation to discount the previous state based on the time of the previous observation. Thus, the state $(s,w,t)$ is updated according to
\begin{eqnarray*}
\pi &=& e^{-(t-t_{n-1})/\alpha} \\
s_{n} &=& \pi s_{n-1} + x \\
w_{n} &=& \pi w_{n-1} + 1 \\
t_{n} &=& t
\end{eqnarray*}
If we were to compute simple rates without discounting, then instead of interpreting $w$ as a count, we would interpret it as a time interval. Thus we would update state $(s,w,t)$ according to with an observation $(x, t)$ according to
\begin{eqnarray*}
s_{n} &=& s_{n-1} + x \\
w_{n} &=& w_{n-1} + (t - t_n) \\
t_n &=& t
\end{eqnarray*}
By analogy with the discounted version of the simple average, we can produce an exponentially weighted rate average by updating the state according to this
\begin{eqnarray*}
\pi &=& e^{-(t-t_{n-1})/\alpha} \\
s_{n} &=& \pi s_{n-1} + x \\
w_{n} &=& \pi w_{n-1} + (t-t_n) \\
t_{n} &=& t
\end{eqnarray*}
This approach has a defect in that each data pont should really be considered to be a report of events spread out in an uncertain way over the time since the last report. As such, the interval and the events should probably both be discounted as if they had been reported uniformly over the period in question. In practice, this correction does not matter much since the averaging time constant $\alpha$ is typically large compared to the average reporting interval. Another consideration comes up when multiple sources are reporting concurrently. If we want to do proper discounting of each observed number, then we have to keep track of the time since last report for each of the sources. Since this probably won't matter and since it considerably complicates the implementation, I would rather not do it.

See https://issues.apache.org/jira/browse/MAHOUT-634 for code. This will be in Mahout before long.

Update on exponential time-embedded averages

2011-03-24T10:25:00.000-07:00

I will be adding this code to Mahout shortly.

See https://issues.apache.org/jira/browse/MAHOUT-634 for status.

Also, if you are measuring rates, then it is common for rates to be reported from multiple sources independently. Such an average can be computed pretty easily using this same framework if the sources report often relative to the averaging time constant. This simple implementation just attributes each reported count as if they occurred in the interval since the most recent report from any reporter. If the time constant is relatively long, this can work out reasonably well as long as we are careful.

If reporting intervals are longer, then the averaging is a bit trickier because we really would like to attribute the reported counts over the entire interval from the last report from the same source. This means that we have to discount some of the counts because they are effectively kind of old.

More details shortly.

Exponential weighted averages with irregular sampling

2011-03-22T17:15:00.000-07:00

Ted Yu on the hbase list wants to compute an exponential weighted average for the number of queries per second or other statistics that characterize the performance or state of an hbase system.

The trick is that the measurements are only available at irregular intervals. If they were sampled regularly, then the standard mixing trick would work:
\[
m_{n+1} = \mu m_n + (1-\mu) x_{n+1}
\]
where $m$ is our current estimate of the mean, $x_n$ is the $n$-th sample and $\mu$ determines how much history to use.

With unequal sample times, things become a bit more complicated. If we get lots of measurements all at once, we want to give them nearly equal weight but if we have a long gap, we want to weight the very old samples much less.

In fact, we want to weight old samples according to how old they are with exponentially decreasing weight. If we sample values $\left \lbrace x_1 \ldots x_n \right \rbrace$ at times $t_1 \ldots t_n$ then we want the weighted mean defined by
\[
m_n = {\sum_{i=1}^n x_i e^{-(t_n - t_i)/\alpha} \over \sum_{i=1}^n e^{-(t_n - t_i)/\alpha} }
\]
Here $\alpha$ plays the same role as $\mu$ did before, but on a different scale. If the evenly sampled data comes at time intervals $\Delta t$ then $\mu = e^{\Delta t / \alpha}$.

Happily, there is a very simple recurrence relationship that allows us to keep only two intermediate values while computing the value of $m_1 \ldots m_n$ in an entirely on-line fashion as the $x_i$ values arrive.

To see this, define

\begin{eqnarray*}
\pi_n &=& e^{(t_{n+1}-t_n)/\alpha} \\
w_{n+1} &=&
\sum_{i=1}^{n+1} e^{-(t_{n+1} - t_i)/\alpha} =
1+e^{-(t_{n+1}-t_n)/\alpha} \sum_{i=1}^{n} e^{-(t_{n} - t_i)/\alpha} \\
& =& 1 + \pi w_n\\
s_{n+1} &=&
\sum_{i=1}^{n+1} x_i e^{-(t_{n+1} - t_i)/\alpha} =
x_{n+1}+e^{-(t_{n+1}-t_n)/\alpha} \sum_{i=1}^{n} x_i e^{-(t_{n} - t_i)/\alpha} \\
&=& x_{n+1} + \pi_n s_n
\end{eqnarray*}

Then note that
\[
m_{n+1} = {s_{n+1} \over w_{n+1}}
\]

This leads naturally to a procedure that has state consisting of $t, w, m$ which are updated with using new values of $t_n, x_n$ according to
\begin{eqnarray*}
\pi &=& e^{t_{n}-t} \\
w &=& 1 + \pi w \\
s &=& x_n + \pi s \\
m &=& {s \over w} \\
t &=& t_{n}
\end{eqnarray*}
Isn't that a kick!

To do this right, however, we need a test. Here are some data vectors computed for $\alpha=5$:

t x pi w s m
1 11.35718 1.5992071 1.0000000 1.000000 1.5992071 1.5992071
2 21.54637 -1.3577032 0.1303100 1.130310 -1.1493105 -1.0168100
3 28.91061 -0.3405638 0.2292718 1.259148 -0.6040683 -0.4797436
4 33.03586 0.7048632 0.4382129 1.551775 0.4401527 0.2836447
5 39.57767 0.3020558 0.2702621 1.419386 0.4210124 0.2966159

Writing a proper unit test is an exercise left to the reader. (but I will be happy to help)

Recent lecture on Mahout for SDForum

2010-11-04T19:59:00.000-07:00

I gave a lecture last night on recent additions to Mahout.

The slides are here: http://www.slideshare.net/tdunning/sdforum-11042010

I can amplify this post with answers to any questions that anybody puts in the comments.

Mahout 0.4 released!

2010-10-31T12:23:00.000-07:00

Go to the Apache Mahout site for more info. Here is the official announcement:

We are pleased to announce release 0.4 of Mahout. Virtually every corner of the project has changed, and significantly, since 0.3. Developers are invited to use and depend on version 0.4 even as yet more change is to be expected before the next release. Highlights include:

- Model refactoring and CLI changes to improve integration and consistency

- New ClusterEvaluator and CDbwClusterEvaluator offer new ways to evaluate clustering effectiveness

- New Spectral Clustering and MinHash Clustering (still experimental)

- New VectorModelClassifier allows any set of clusters to be used for classification

- Map/Reduce job to compute the pairwise similarities of the rows of a matrix using a customizable similarity measure

- Map/Reduce job to compute the item-item-similarities for item-based collaborative filtering

- RecommenderJob has been evolved to a fully distributed item-based recommender

- Distributed Lanczos SVD implementation

- More support for distributed operations on very large matrices

- Easier access to Mahout operations via the command line

- New HMM based sequence classification from GSoC (currently as sequential version only and still experimental)

- Sequential logistic regression training framework

- New SGD classifier

- Experimental new type of NB classifier, and feature reduction options for existing one

- New vector encoding framework for high speed vectorization without a pre-built dictionary

- Additional elements of supervised model evaluation framework

- Promoted several pieces of old Colt framework to tested status (QR decomposition, in particular)

- Can now save random forests and use it to classify new data

- Many, many small fixes, improvements, refactorings and cleanup

Details on what's included can be found in the release notes.

Downloads are available from the Apache Mirrors

New Mahout release coming

2010-10-25T11:53:00.000-07:00

The vote has started for the 0.4 Mahout release. Lots of new stuff, but the part that I am excited about is a fairly comprehensive implementation of logistic regression suitable for large scale training and high speed classification, but there is a whole lot more.

With the 0.4 release, Mahout is moving along strongly towards the fabled 1.0 release. At that point, we will start paying lots of attention to backwards compatibility. That will be good, but the current wild and wooly policy is pretty handy if you have something in mind that Mahout really, really needs because we can get new things in pretty readily right now.

See http://mahout.apache.org/ for the release when it arrives and watch my twitter feed for an announcement.

Why is the sum of two uniform randoms not uniform?

2010-10-13T07:09:00.000-07:00

Lance Norkog asks on the Mahout mailing list why adding two uniformly distributed random variables gives a pyramidal distributed value. I would normally answer on the mailing list, but here I can use lovely math notation. As I mentioned on-list, this is a very basic result that is related to the law of large numbers.

If we were to draw a picture of the joint distribution of these variables $x$ and $y$, we would get something that is 1 inside the $[0,1] \times [0,1]$ square and 0 outside that region.

For a given value $\alpha$ of the sum $x + y$, there is a diagonal line segment where $x+y=\alpha$ and $x$ and $y$ are in the square. Where $z \le 0$ or $z \ge 2$ that intersection vanishes and for $0 \lt z \lt 2$, that intersection varies in length. The probability of the sum having some particular value z is proportional to the length of that intersection. As you can imagine, the intersection varies in size linearly and it reaches a maximum where z = 1.

For the sum of three random variables, the situation is more complex to reason about geometrically because we need to worry about the intersection of a plane and a cube. For more variables, the geometry is not worth the trouble.

If we tackle the problem a bit more rigorously, then the easiest way to approach the problem is to compute the cumulative distribution of various values of sums. That leads to a convolution integral over the density functions involved. Since the densities are all 1, the integration limits are the key to the value and those limits have to broken down into cases. Actually doing these integrals is a pretty rare activity since the limit is approximated so well after just a few iterations.

Just how quickly that convergence happens is can be seen by looking at the empirical distribution of the sum of three uniform deviates. I used something very like this R code to produce the graph below:

   hist(runif(100000)+runif(100000)+runif(100000),
   breaks=50, prob=T)
   lines(seq(-1,4,by=0.01), dnorm(seq(-1,4,by=0.01),
   1.5, sqrt(1/4)))

In this graph, the red curve is the normal distribution with the same mean and standard deviation. As you can see, the peak is a tiny bit too high and the tails are just a skoshi too long for the normal to be a good description of the samples of the sum.

This is, however, just the sum of three random values. If you sum more values, the convergence to the normal distribution is very strong and by the time you are adding six uniform random values together, the difference between the distributions is no longer visible in a graph like this and can only be detected numerically using lots of data and clever things like a Kolmogorov-Smirnov test.

The moral here is that there isn't much way to avoid this regression to the normal distribution and distorting the data to avoid it is probably pointless.

But if you are like me, being just a little more normal always made it easier to get along.

Sadder things

2010-08-11T11:48:00.000-07:00

I spent this last weekend holding a hand that grew cold in the early hours of Sunday morning.

That hand helped me through much of my life. No longer. At least not in the flesh.

Nobody who reads this blog is likely to have known my father and given how little he talked about things he had done, few who knew him would know much of the many things he did. He lived a long life and a full one. Along the way he saw things few will ever see.

In his prime, he was simply extraordinary. He could see and he could hear better than anyone I have ever known. That could be torture, as it was the time when a cat walking in the next room woke him from a deep sleep but it was what let him fly the way he did. And fly he did in planes large and small. He checked out Gary Powers in the U-2, flew P-47's and P-38 in combat and flew with me in small aircraft. We fished and walked and camped across the western US and we lived in many places.

He didn't show off his mental abilities, but there too he could do things few others could match. He passed a graduate reading exam in French without ever studying any romance language. I saw him on several occasions understand spoken German also without having studied the language. He spoke of the shape and rate of physical processes in ways that only somebody with innate ability in math could possibly do.

These faculties declined in age as they must with all of us, but even thus dimmed his candle burned bright.

But it did not last. I saw it sputter and fade. Then, between one instant and the next, it was gone.

Word Count using Plume

2010-08-04T11:29:00.000-07:00

Plume is working for toy programs!

You can get the source code at http://github.com/tdunning/Plume

Here is a quick description of how to code up the perennial map-reduce demo program for counting words. The idea is that we have lines of text that we have to tokenize and then count the words. This example is to be found in the class WordCountTest in Plume.

So we start with PCollection lines for input. For each line, we split the line
into words and emit them as a separate record:


  PCollection words = lines
   .map(new DoFn() {
   @Override
   public void process(String x, EmitFn emitter) {
   for (String word : onNonWordChar.split(x)) {
   emitter.emit(word);
   }
   }
   }, collectionOf(strings()));

Then we emit each word as a key for a PTable with a count of 1. This is just the same as most word-count implementations except that we have separated the tokenization from the emission of the original counts. We could have put them together into a single map operation, but the optimizer will do that for us (when it exists) so keeping the functions modular is probably better.

  PTable wc = words
   .map(new DoFn>() {
   @Override
   public void process(String x,
   EmitFn> emitter) {
   emitter.emit(Pair.create(x, 1));
   }
   }, tableOf(strings(), integers()))

Then we group by word

  .groupByKey()

And do the counting. Note how we don't have to worry about the details of using a combiner or a reducer.

  .combine(new CombinerFn() {
   @Override
   public Integer combine(Iterable counts) {
   int sum = 0;
   for (Integer k : counts) {
   sum += k;
   }
   return sum;
   }
   });

In all, it takes 27 lines to implement a slightly more general word-count than the one in the Hadoop tutorial. If we were compare apples to apples, this could would probably be a few lines shorter. The original word-count demo was 210 lines to do the same thing.

The new grool

2010-07-30T13:41:00.000-07:00

A few years ago, I built a prototype system I called grool in Groovy to simplify map-reduce programming. My goal was to use Groovy to handle control flow and define operations but to execute large programs using Hadoop.

Grool foundered on the difficulty in transporting closures over the network. I used a clever trick to avoid the problem, but it depended on the ability to execute a script multiple times with different meanings each time. That is a difficult concept to convey to users and the result was that grool really didn't work that well for ordinary folks to use.

A bit later, the guys at Google developed FlumeJava which has many of the same goals and many of the same benefits as grool intended to provide. In Java, however, transporting functional objects it paradoxically much simpler than in Groovy. The difference is entirely because Java is statically compiled and thus state-less functional classes can be referred to by name in different JVM's with access to the same jar.

Flume also provide an optimizer which is made possible because Flume uses lazy evaluation. This makes FlumeJava programs nearly as efficient as well-optimized hand-written programs. Other systems like Pig and Cascading are able to re-write their logical plan, but Pig especially has problems because it has no real access to a Turing complete language.

In addition, Flume has some interesting choices in terms of API.

All in all, Flume-like systems are definitely worth playing with. In order to make that easier, I just implemented an eager, sequential version of an approximate clone of FlumeJava that I call Plume. The name is a presumptuous one, anticipating that if all goes well, we would be able to build a community and bring Plume into Apache where it would be Apache Plume. There it would provide some redress for the clear fauna bias in software names.

Check it out at http://wiki.github.com/tdunning/Plume/

Hadoop user group AKA Mahout Users Anonymous

2010-04-22T14:47:00.000-07:00

At the Hadoop User Group meeting last evening it was quite the Mahout love fest. First the Yahoo team described their spam fighting efforts which apparently are partially anchored by frequent item set mining using Mahout (thanks to Robin Anil's hard work as a GSoC student). Then later Ken Krugler demonstrated some of what you can do with web-mining and Mahout.

These are just two of a growing number of real-world uses of Mahout which is really beginning to grow up. Related to that growing up, the Apache board just decided to make Mahout a top level project. That will take a little while to make real, but the first steps are already happening.

You can find out more about how Mahout is being used by perusing the Mahout wiki.

Slide decks available here for the HUG presentations.

Interview on Mahout available

2010-04-20T12:51:00.000-07:00

I just had an interchange with Gilad Manor of InfoQ (as did Grant). The results are to be found in the article on Mahout status that resulted.

Sampling a Dirichlet Distribution (revised)

2010-04-10T11:35:00.000-07:00

Last year, I casually wrote a post about how to sample from a prior for Dirichlet distributions. There were recently a few comments on this blog and it now occurs to me that there is a massive simplification that is possible for the problem.

What I suggested back then was to sample the parameters of a Dirichlet distribution by sampling from a Dirichlet distribution and then multiplying that by a magnitude sampled from an exponential distribution. As it turns out, this is a special case of a much nicer general method.

The new method is to sample each parameter independently from a gamma distribution
\[\gamma_i \sim \mathrm{Gamma}(\alpha_i, \beta_i) \]
This can be related to my previous method where we had the parameters expressed as a magnitude $\alpha$ multiplied by a vector $\vec m$ whose components sum to 1. Expressed in terms of the new method
\[\alpha = \sum_i \gamma_i \]
and
\[ m_i = \gamma_i / \alpha \]
Moreover, if all of the $\beta_i$ are equal, then $\alpha$ is gamma distributed with shape parameter $\sum_i \alpha_i$. If this sum is 1, then we have an exponential distribution for $\alpha$ as in the original method.

I am pretty sure that this formulation also makes MCMC sampling from the posterior distribution easier as well because the products inside the expression for the joint probability will get glued together in a propitious fashion.

Sampling Dirichlet Distributions (chapter 2-b)

2010-04-06T16:28:00.000-07:00

In the previous post, I talked about how sampling in soft-max space can make Metropolis algorithms work better for Dirichlet distributions. Here are some pictures that show why. These pictures are of three parameter Dirichlet distributions with the simplex projected into two dimensions. Dirichlet distributions with different parameters can look like this:

or this

These were all generated using the standard algorithm for sampling from a Dirichlet distribution.

In R, that algorithm is this

rdirichlet = function(n, alpha) {
  k = length(alpha)
  r = matrix(0, nrow=n, ncol=k) 
  for (i in 1:k) {
    r[,i] = rgamma(n, alpha[i], 1)
  }
  r = matrix(mapply(function(r, s) {return (r/s)}, r, rowSums(r)), ncol=k)
  return (r)
}

That is, first sample using a gamma distribution

Then normalize to get the desired sample

In contrast, here are 30,000 samples computed using a simple Metropolis algorithm to draw samples from a Dirichlet distribution with . This should give a completely uniform impression but there is noticeable thinning in the corners where the acceptance rate of the sampling process drops.

The thinning is only apparent. In fact, what happens is that the samples in the corners are repeated, but that doesn't show up in this visual presentation. Thus the algorithm is correct, but it exhibits very different mixing behavior depending on where you look.

A particularly unfortunate aspect of this problem is that decreasing the size of the step distribution in order to increase the acceptance rate in the corners makes the sampler take much longer to traverse the region of interest and thus only partially helps the problem. Much of the problem is that when we have reached a point near the edge of the simplex or especially in a corner, many candidate steps will be off the simplex entirely and will thus be rejected. When many parameters are small, this is particularly a problem because steps that are not rejected due to being off the simplex are likely to be rejected because the probability density drops dramatically as we leave the edge of the simplex. Both of these problems become much, much worse in higher dimensions.

A much better alternative is to generate candidate points in soft-max space using a Gaussian step distribution. This gives us a symmetric candidate distribution that takes small steps near the edges and corners of the simplex and larger steps in the middle of the range. The sensitivity to the average step size (in soft-max space) is noticeably decreased and the chance of stepping out of the simplex is eliminated entirely.

This small cleverness leads to the solution of the question posed in a comment some time ago by Andrei about how to sample from the posterior distribution where we observe counts sampled from a multinomial

where that multinomial has a prior distribution defined by

More about that in my next post.

Sampling Dirichlet Distributions (chapter 2-a)

2010-04-06T13:52:00.000-07:00

In a previous post on sampling from Dirichlet distributions that related to a comment by Andrew Gelman on the same topic I talked a bit about how to sample the parameters of a Dirichlet (as opposed to sampling from a Dirichlet distribution with known parameters).

In responding to some questions and comments on my post, I went back and reread Andrew's thoughts and think that they should be amplified a bit.

Basically, what Andrew suggested is that when sampling from a Dirichlet, it is much easier to not sample from Dirichlet at all, but rather to sample from some unbounded distribution and then reduce that sample back to the unit simplex. The transformation that Andrew suggested is the same as the so-called soft-max basis that David Mackay also advocates for several purposes. This method is not well know, however, so it deserves a few more pixels.

The idea is that to sample from some distribution you instead sample

and then reduce to the sample you want

Clearly this gives you values on the unit simplex. What is not clear is that this distribution is anything that you want. In fact, if your original sample is from a normal distribution

then you can come pretty close to whatever desired Dirichlet distribution you like. More importantly in practice, this idea of normally sampling and then transforming gives a very nice prior serves as well as a real Dirichlet distribution in many applications.

Where this comes in wonderfully handy is in MCMC sampling where you don't really want to sample from the prior, but instead want to sample from the posterior. It isn't all that hard to use the Dirichlet distribution directly in these cases, but the results are likely to surprise you. For instance, if you take the trivial case of picking a uniformly distributed point on the simplex and then jumping around using Metropolis updates based on a Dirichlet distribution, you will definitely have the right distribution for your samples after just a bit of sampling. But if you plot those points, they won't look at all right if you are sampling from a distribution that has any significant density next to the boundaries of the simplex. What is happening is that the high probability of points near the boundaries is accounted for in the Metropolis algorithm by having a high probability of rejecting any jump if you are near the boundary. Thus, the samples near the boundary are actually repeated many times leading to the visual impression of low density where there should be high density.

On the other hand, if you were to do the Metropolis jumps in the soft-max basis, the problem is entirely avoided because there are no boundaries in soft-max space. You can even use the soft-max basis for the sole purpose of generating candidate points and do all probability calculations in terms on the simplex.

In my next post, I will provide a concrete example and even include some pictures.

Big Data and Big Problems

2010-04-04T13:53:00.000-07:00

In talks recently, I have mentioned an ACM paper that showed just how bad random access to various storage devices can be. About half the time I mention this paper, somebody asks for the reference which I never know off the top of my head. So here it is

The Pathologies of Big Data

Of course, the big deal is not that disks are faster when read sequentially. We all know that and most people I talk to know that the problem is worse than you would think. The news is that random access to memory is much, much worse than most people would imagine. In the slightly contrived example in this paper, for instance, sequential reads from a hard disk deliver data faster than randomized reads from RAM. That is truly horrifying.

Even though you can pick holes in the example, it shows by mere existence that the problem of random access is much worse than almost anybody has actually internalized.

Nice package of software an tutorials for corpus analysis

2010-02-07T09:36:00.000-08:00

I was about to try to provide some help in using the implementations that I use and give away for a graduate student trying to do some corpus analysis and I found this lovely site describing how to do corpus analysis using R. Marco Baroni and Stefan Evert have done a really lovely job there of describing how to do a large number of simple tasks. Kudos to them!

For not necessarily the most noble reasons, I was happy to see from their slide show on computing association measures that is still essentially on top as a measure of association after all of these years.

A call to action

2009-12-08T18:11:00.000-08:00

The Guardian and numerous other newspapers around the world published a simultaneous editorial about climate change and warming.

This call to action is urgent. We should heed it. This is both the greatest crisis and the greatest opportunity our species has ever faced. Sadly, failure is an option and many people are working to guarantee it by spreading rumors and lies.

The rest of us have to succeed in spite of that. For everyone's sake.

How to smooth rate estimates

2009-11-23T11:10:00.000-08:00

I mentioned in a previous posting that I recommend smoothing rate estimates using offsets on numerator (number of events) and denominator (time period). While it is possible to build a principled prior distribution and do very detailed rate estimation based on this, I find that for "top-100" lists and for "hot-100" lists, it is more useful to adjust the prior with larger strategic goals in mind.

In particular, what I like to do is set the ratio of the offsets to position an item with no data whatsoever (event count = 0, time = 0) so be somewhere in the top half of all items, but generally not in the top 10%. This expresses a general optimism about new items that allows them to achieve high rankings with a very modest burst of enthusiasm from the audience and forces them to provide some proof that they are dogs.

Once this ratio is set, it remains to set the actual magnitudes. This is done by deciding how much many events that you want an item to have or how long you want it to languish before the data overcome the prior. If you want the first 10 events to have equal weight to the prior, set the numerator offset to 10. Alternately, if you want the first day of data to have equal weight to the prior, set the denominator offset to 1 day.

Done. Works. Simple.

I have done the much more complex effort of building detailed prior models and actually estimating rates in a completely principled fashion but I have found two things:

a) business people have other agendas than pure estimation and they want a vote

b) the early estimates are pretty unreliable until the data dominate the prior (duh!). Thus, you may as well set up the prior to make (a) work.

Twitter and small counts

2009-11-22T20:03:00.000-08:00

I just got a very nice email from Slideshare that says

"Transactional Data Mining" is being tweeted more than any other document on SlideShare right now. So we've put it on the homepage of SlideShare.net (in the "Hot on Twitter" section).

That sounds sooo exciting. People magazine, here I come!

Of course, when you look into the matter, I really don't think that I am going to have to worry about dodging paparazzi any time soon. What they mean by "tweeted more" seems to be 3 times in a day. Sounds like they should have read my paper about surprise and coincidence!

In fact, for applications like popularity ranking it is often really important to have a robust idea about what is hot and what is not. There are two very common problems to solve, one is to find out which items are rapidly rising and the other is to put a reasonable rank onto things.

The problem of what is rising is surprisingly well well solved by ranking items by the log of the ratio of the number of hits/views/tweets in a recent period of time to the number of hits in a somewhat older (and typically longer) period of time. Well, not quite the ratio. In practice, it is better to offset both numerator and denominator by a constants which are well chosen by looking at the results, but which are actually well-founded in terms of MAP estimators for rates. The reason that this works so well is that popularities are typically distributed in a roughly Zipfian way so taking log of the rate is linearly related to the log of the rank.

A large change in the log-rank of an item is a great indicator of dramatically rising popularity, but rank itself is a pretty fuzzy measurement with small counts (the guys at SlideShare need to hear this). Log of the rate, however, is linearly related to the log of rank, so change in log-rank is proportional to change in log-rate. Moreover, the offset trick when computing the rate ratio largely deals with the small count problems that you have when something goes from no hits to one hit in a time period.

The second problem is computing what the rank of an item really is given bursty nasty data like hit counts. The problem is that you only have a nice tight estimate of the hit rate for the most popular items. Since you want recent rankings, you want to use a shorter period of time for your estimates so the problem of small counts is even worse. Conceptually, a very principled way to do deal with the problem is to embrace the uncertainty and sample the rates associated with each item given the data you have and rank the items. Do this a bunch of times and you have the posterior distribution of the ranks for each item. Moreover, you also have a lookup table that tells you what any particular observed rate means relative to what rank the item might have.

This sampling can be done in a few seconds in R. I think it is cooler to add dithering do the ranked list of items so that each time you look at the list, you get another sample from this distribution. This means that items that might plausibly be in the top 100 or 1000 actually get to be there some of the time and items that are definitely in the top few places are always where they should be. It also adds dynamism to your top-n list which is always good on the web.

Video of talk on transactional data

2009-11-01T22:59:00.000-08:00

If you want to see more about some the techniques I have used in projects take a look at this talk I gave to the Bay Area ACM chapter.

See "Transactional Data Mining"

Slides are available at here

Sampling Dirichlet Distributions

2009-04-29T12:20:00.000-07:00

[I just realized that this post from last year was only half the story. See this post about using the gamma distribution directly to sample Dirchlet distributions]

I just commented on a post by Andrew Gelman about methods for sampling Dirichlet distributions. Those comments were pretty non specific and deserve a bit of amplification.

First off, a Dirichlet distribution is a distribution of real-valued tuples,
\[(x_1 \ldots x_n) \sim \mathrm {Dir}(\pi_1 \ldots \pi_n) \]
such that $x_i \ge 1$ and $\sum_i x_i = 1$

The parameters $\pi_i$ are all non-negative.

The original question had to do with sampling the Dirichlet parameters, especially from a conjugate distribution. The one and true answer in mathematical terms is that there is, indeed, a continuous distribution which is the conjugate of a Dirichlet. In practical terms, however, that isn't the answer that you really want.

A much more practical answer is that the Dirichlet can be sampled from a prior that is characterized by $n+1$ non-negative real parameters using the following procedure
\[\begin{aligned}
\left(m_1 \ldots m_n \right) & \sim \mathrm {Dir} (\beta_1 \ldots \beta_n ) \\
\alpha & \sim \exp (\beta_0) \\
\pi_i & \sim \alpha m_i
\end{aligned}
\]
Alternative distributions for $\alpha$ include the gamma distribution and exponential normal, such as
\[ \log \alpha \sim \mathcal N (0, 2)\]

What would really help map-reduce programs?

2009-03-24T14:51:00.000-07:00

David Hall is touting a Scala package that he calls SMR (Scala for Map Reduce).

I built something like this quite some time ago using groovy. I called the resulting Groovy map-reduce facade grool because it was pretty thin. The results were even more impressive for toy programs than what SMR achieved. For instance, here is a fully hadoop compatible map-reduce version of word count:


  wc = mapReduce(
  {key, line, out, report -> line.split().each {w -> out.collect(w,1)}},
  {w, counts, out, report -> out.collect(w, counts.sum())}
 )

In this example, wc is a function that can then be applied to various inputs as in


  wc(["this is input text", "for the word-counter"])


  wc(new File("/local/input/file")

or even


  wc(functionUsingMapReduce(new HdfsFile("/existing/file")))

In spite of how pretty these tiny examples are, I eventually quit using it for day-to-day map-reduce coding.

The problem with things like grool that attempt to make writing map-reduce programs easier is that it doesn't really solve the problems that you face in writing map-reduce programs. It does make word-count much shorter (5-7 lines of code versus >200). It does involve a very cool hack so that the closures passed as arguments are available as map and reduce objects on the right machines. But I found in using grool for production code that it didn't solve the right problem.

The big problems involved in map-reduce programming are

map-reduce is just a tad too low-level for most problems.

debugging programs written using a facade like this is harder than for programs written using raw java + map-reduce.

the boilerplate of map-reduce isn't proportional to problem size so large programs exhibit much less improvement in grool than small programs do.

What I would much rather have is something that provides much higher-level semantics such as those provided by Pig, but which provides for better integration into real programming languages. The better integration that I need goes two directions. First, I want to be able to, for instance, compute every date in a date range, use those dates to form input paths and then do a computation on those input paths. Pig can't do that except via a very ugly argument substitution hack.

A second kind of better integration is what Chris Wenzel has been pushing for some time with Cascading. I would like it if I could write programs in what might be called PL/Pig (by analogy with PL/SQL) that would then be tightly integrated into a Cascading flow. Ideally, the PL/Pig program would expose its execution plan to Cascading for global optimization and scheduling.

Real-time decision making using map-reduce

2009-01-15T00:07:00.000-08:00

Recently Tim Bass described his happiness that the Mahout project has taken on some important tasks that are often applied to real-time decision making.

I think that Tim's joy is justified, although Mahout is still a very new project that is definitely not a finished work by any means. There are a number of important algorithms that are being worked on that could provide some very important capabilities for real-time decision makers.

The fact is, though, that map-reduce is no silver bullet. It won't make problems go away. It is an important technology for large-scale computing that lends it self to the batch training of real-time models if not quite to high availability real time decisioning. For that, I tend to add systems like zookeeper and to build systems in the style of the Katta framework.

In my mind the really important change that needs to happen is that designers of real-time decisioning systems need to embrace what I call scale-free computation.

Scale free computation is what you get when you don't let the software engineers include the scale of the process as a design parameter. Without that knowledge, they have to build systems that will not require changes when the scale changes. Map-reduce is a great example of this because the map and reduce functions are pure functions. The person who writes those functions has no idea how many machines will be used to compute them ... moreover, the framework is free to apply these functions more than once to data if it find a need.

Katta does something similar by allowing the manager of a search system to specify what should happen without specifying quite how. The master system uses Zookeeper to maintain state reliably and it examines the specification of what is desired and allocates tasks to search engines. The search engines detect changes in their to-do list and download index shards as necessary. Clients examine the state in Zookeeper and autonomously dispatch requests to search engines and combine results.

The overall effect again is that the person implementing a new katta search system has very little idea how many machines will be used to run the search. If the corpus is large, then many shards will be used. If throughput is required, then shards will be replicated many times. Neither requires change.

Scale free design patterns like this are required for modern, highly reliable decision systems. The change in mind-set required is non-trivial and dealing with legacy code will be prodigiously difficult. As usual with major changes in technology, the best results will come after the old code is retired. Hopefully that can happen before us old coders retire!

Students learn what they need, not what is assigned

2008-12-17T12:59:00.000-08:00

A friend recently wrote about her experience with the currently fashionable style of teaching where students are expected to reinvent mathematics.

She wrote:

So much attention is given as to why - and to having students figure out algorithms themselves. Some teachers feel this is a waste of time - time that could be used for the students to be practicing the algorithms and becoming more fluent.

I think that this is largely a waste as well. We cannot expect students of all abilities to recapitulate in 6 years the history of more than 2000 thousand years of thought by the best minds the earth has ever seen. To imagine that they can is simply ludicrous. To imagine that what they can invent in this short time and that they don't need the benefit of those great thoughts is similarly ludicrous.

At the risk of sounding self-contradictory, I also think that when the student owns the task of learning, they will learn enormously better than when the task is imposed. This does not imply that the student discover everything, however. It merely implies that they need to discover the need for the things that they learn. Students who need to learn something can learn from almost any source, even from something as currently unfashionable as, say, sitting quietly thorugh traditional lecture.

The last time I taught in the classroom was as a member of a two-person teaching team teaching a software engineering class on machine level programming. In the past, this had been done by lecture and assignment and was truly a stunningly boring class. On the first day, I turned the structure of the class upside-down and assigned the entire final exam. This consisted of a single question in the form of a task (to build a robot that would drive around as fast as possible following a line on the floor). I then passed out soldering irons, computer components and kits of lego parts and told them to get to work. For the record, I had never tried to build such a 'bot myself.

This tactic resulted, as you would expect, in panic. The students complained that they didn't know how to solder, that they didn't know anything about the computer I had given them and that they didn't know how to build robots. I told them that they would have to learn all this and much more and that I would try to help them find out all this information, but they would have to tell me what they wanted to learn. Early on, the questions were about soldering. Over time, the questions became more and more sophisticated. At the beginning of the class, we had a list of lectures that we wanted to give, but we held them back until somebody asked a related question. At that point we would have a vote among the class whether they would like to have a lecture on the subject or would rather continue work on the robots.

By the end of the semester, I was getting complaints from the department because my students were (voluntarily) spending so much time on my class that they were neglecting their other classes. Some were spending 40 hours or more in the computer lab and many had built remarkable contraptions little related to the impending exam. This enthusiasm translated into perfect line-following performance on sample lines.

But ...

What I hadn't told the students was that the final would (for the first time) involve a line that crossed itself. Essentially all of the robots would fail on this line because they hadn't been designed or programmed to deal with that case. The real exam was whether they could deal with the unexpected and redesign and reprogram their robots during the 3 hour exam period to succeed on the harder problem.

All students succeeded.

Moreover two thirds of the class came back a week after the official final to repeat it in front of a friend who flew down to see how the class had worked out. I think, but do not have much data to support the assertion that it is rare for students to ask to be allowed to put off summer vacation so that they can repeat a final exam.

The point of it all was that these students could learn vastly more than was expected of them if they just wanted to. They could learn this material almost effortlessly in a traditional setting where somebody (me) wrote illegibly on the blackboard on difficult and abstract topics. But previous classes with exactly the same lectures given by better teachers than me had failed abysmally. I think the difference was that my students felt that they absolutely needed to learn what was in the lecture ... indeed, they had to ask for the lecture before I would give it. They also felt very much the owners of their task.

In the end, the students felt that they had invented almost everything they needed. In fact, I had spoon-fed fed them almost all of the key material. I told them how to make motors turn, how to make lights turn on, how to assemble and load software and how to design a software project. That didn't matter because they didn't remember that. What they remembered was that they initiated their learning of all of the material. They owned the class. I was their assistant, not their master.

And they learned. A lot.

2008-12-16T11:02:00.000-08:00

So what about the question of why two negatives multiplied give a positive?

The short answer is that if this were not so, the world would not exist.

That is, the fundamental reason that multiplication works that way is because otherwise the definition would be broken. By broken, I mean that it would lead you to nonsensical conclusions if you followed it as far as you could. Any definition multiplication in a system with negative numbers has to work pretty much that way.

On Tue, Dec 16, 2008 at 6:42 AM, wrote:

Why does a negative number times a negative number equal a positive number?
How can you show that using a manipulative?

Let's take the concrete (but abstract) example of arithmetic on a 7 hour clock. Here is the addition table:

+ 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 3 4 5 6 0
2 2 3 4 5 6 0 1
3 3 4 5 6 0 1 2
4 4 5 6 0 1 2 3
5 5 6 0 1 2 3 4
6 6 0 1 2 3 4 5

OK. Now we can build multiplication on top of that. I will use * instead of x to indicate multiplication because I don't have really good fonts.

* 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1

OK. Not much to see here except that in the multiplication every row has all of the integers. Moreover, every row has these integers in a different order. This is a consequence of the fact that 7 is a prime number. It doesn't happen that way on the 12 hour clock.

But let's look again at the addition table. Note that 1 + 6 = 0 and that 2 + 5 = 0. Notice also that 0 only appears once in each row. That means that we can consider 6 to be a way of writing -1. Or perhaps -1 is a way to write 6. This lets us solve addition problems such as 3 + x = 5 by adding 4 (which is -3) to both sides.

But what happens when we multiply 3 * (-2)? Do we get -6?

Well, -2 = 5 so this should be the same as 3 * 5 which is 1. But 1 is also -6 !

And all of our properties like the distributive law should still work.

Thus 3 * (-2) + 3 * 4 = 1 + 5 = 6 should be 3 * (-2 + 4) which is 3 * 2 = 6. So that works.

What about (-3) * (-2) = 6?

Well, this should be (and is) the same as 4 * 5 = 6.

That's cool.

In a very limited and geeky dull kind of way.

What is more cools is that this is all just a very concrete example of how the laws or arithmetic imply a certain kind of order. We could test this out for all the different kinds of arithmetic that have the properties that we like about integers. I don't mind starting infinite tasks, but I do mind having to finish them.

SO

Let's do much better by reasoning from those properties directly.

For instance, assume that we have the following:

an additive unit, 0 such that x + 0 = 0 + x = x and thus 0 * x = 0
an additive inverse, -x = 0 - x
left distributive law, (a + b) * x = a * x + b * x
right distributive law, x * (a + b) = x * a + x * b

Now take x * (0 - y). This has to be equal to (x * 0) - (x * y) = 0 - (x * y) = - (x * y)

Or (0 - x) * (0 - y) = 0 - x * (0 - y) = 0 - (0 - x * y) = x * y

This means that ANY kind of arithmetic where multiplication and addition have an additive inverse and left and right distributive laws will follow the pattern that (-x) * (-y) = x * y

OR

if that system doesn't have that, then it won't have one or all of the properties mentioned.

This works for a spinning globe, for quantum mechanics, for clocks and rubik's cubes.

And THAT is why abstraction is cool. But not why it is useful. That comes next.

Mathematics as an article of faith

2008-12-16T10:31:00.000-08:00

A friend asked me a wonderful question recently.

She asked:
> I feel like math is so wonderful and useful to a certain point. (Like sixth grade.)
> Then it seems abstract... I can't see the purpose.

She was very much right that mathematics becomes abstract at that point.

And that is very much the point of it. It allows us to think abstractly. It allows us to find patterns in many different things that work the same way. That allows us to think a problem through in mathematically form and then recognize that form again and again.

One good example is modular arithmetic. We could call it clock arithmetic and talk about integral hours that wrap around the 12 hour clock. We could build an addition table that tells us everything there is to know about that kind of arithmetic. We could extend that addition table to be multiplication by repeated multiplication.

That is all well and good. But it only tells us about clock arithmetic on a 12 hour clock. It doesn't tell us as it stands about clock arithmetic on an 11 or 13 or 24 hour clock. It doesn't tell us about arithmetic on a clock where the time isn't just an integer, but can be between the hours. Maybe we don't care about those things because we don't have to tell time on a 17 hour clock very often.

But what about the fact that the original arithmetic that we started with on our 12 hour clock also works just fine for .... music on a western scale.

Should we spend the same amount of time reinventing all of what we learned about the 12 hour clock when it is exactly the same as for musical scales? Or should we re-use that knowledge?

Well, to re-use that knowledge, we have to stop a moment and erase all the places where we originally said "clock" or "hour" or "one day later" and replace them with the integers from 0 to 11 inclusive and replace "move clockwise one hour" with "add one, reduce by removing 12's". This abstracts the original system which can make it harder to learn, but it also makes it much more useful because we don't have to learn it again and again.

But what if somebody asks about pentatonic scales? Or about microtones? Or the 35 note scales that were talked about in the sixties?

Well, if we had started by abstracting away the number of hours on the clock and abstracting away whether the numbers were integers or real numbers, then we would be able to answer those questions instantly.

And if we had abstracted the idea of rotation a bit more, we would see that rotation around a circle can be generalized into rotation around a sphere or even more complex things. Now our clock arithmetic can solve navigational problems and get us home on a dark night.

But with just a bit more extension, that same clock arithmetic (now with 4 hours and 9 dimensions) could solve a Rubik's cube with about 5 minutes of thought.

None of the details here matter. For instance, the fact that 12 is not prime plays a big role in the nature of the arithmetic that we get on clocks, but that isn't the point of all of this.

Now, this abstraction is really frustrating because you can't always point to something and say that it is what you are talking about. In fact, the point of abstraction is that you aren't talking about something specific. This is exactly what makes it hard to teach abstraction using manipulatives. Manipulatives are all about grounding intuition in naive physics. Abstraction is all about UNgrounding your intuitions.

The point is that mathematics is all about abstraction. It is just a mechanism so that we can repeat what once appeared the work of genius without having ourselves to be genii.

So is it useful for most people to understand these wheels within wheels that turn behind the world we see?

To me, yes, it is useful and beautiful and wondrous. But I can't speak for others.

I do think that anybody with a spiritual tendency is turning away from the hand of god if they choose to not see all the kinds of order in the world.

natural language processing blog: Using machine learning to answer scientific questions

2008-11-04T22:29:00.000-08:00

Try this paper for some pretty interesting results on regression in a large variable space with interactions:

http://ideas.repec.org/p/wop/pennin/01-05.html

Death penalty and data modeling

2008-07-05T22:03:00.000-07:00

This article just appeared in the "International Journal of Law and Information Technology". It purports to show that the death penalty is arbitrary because whether or not somebody who is sentenced to death can be predicted without considering any substantive characteristic of the crime in question. If true, the conclusion certainly would indicate that the death penalty really is applied based more on who was sentenced rather than what they did.

Unfortunately, there are a number of defects in the analysis given in that paper that me somewhat leery of taking the results at face value. Some of these problems represent insufficient detail in the article, others indicate a lack of rigor in the data analysis itself.

First, the authors include without definition the following three variables:

7. Third most serious capital offence
8. Second most serious capital offence
9. First most serious capital offence

These variables sound related to the capital crime for which the prisoner was sentenced. Without definition, we cannot judge. Moreover, without knowing how these variables were encoded, we cannot tell whether the model was able to use this input or not.

Secondly, the authors include the following four time based variables:

15. Month of conviction for capital offense
16. Year of conviction for capital offense
17. Month of sentence for capital offense
18. Year of sentence for capital offense

I understand what these variables represent, but am curious how the authors encoded them. Normally in a model like this, time would be encoded as a continuous linear variable from some relatively recent epoch. Separating a time variable like this often leads to problems if you are looking for recency effects. The other common use of separated month variables is to look for seasonality affects. Typically, though, this would be done using 1 of (n-1) encoding which you clearly did not use given how few inputs you have.

While the encoding of these variables doesn't really bear much on the validity of the results, it does make it unlikely that the model could have used these variables for the purpose intended.

Thirdly, the issue of encoding also comes up the geographical variable:

2. State

Encoded as a single variable, this is almost certainly an integer code. This is a very poor encoding of state (1 of 50 encoding would be much better, several variables with different resolution would be even better).

Regarding the learning results themselves, the authors apparently did not assess which input variables were responsible for their results. They should have used any of the standard techniques such as step-wise variable selection or input randomization. They should have also measured how much value the non-linear classifier that they used mattered to the results. Typically, this would be done by comparing the results available from a linear classifier such as a ridged logistic regression. With the encodings in use by these authors, such a straight-forward comparison is probably not viable.

The authors also do not appear to have done anything to determine whether there is a target leak in the data. This can occur when there is some apparently independent input which is accidentally highly correlated with the desired output. In this case, it is possible that one state is responsible for a large majority of the executions. This might make the output more predictable without providing much ammunition for the original argument.

Finally, the authors do not have any reference in their article about public availability of their data. Without making their data easily available and given how incredibly easy it is for novices to screw up a modeling effort, these results should be considered no more than slightly provocative.

Why the long tail isn't as long as expected

2008-07-03T13:26:00.000-07:00

Several bloggers and authors are finding out (belatedly relative to people involved in the industry) that the economic returns in systems that are supposedly governed by long-tail distributions are unexpectedly concentrated in the highly popular items. See here for a blogger's commentary on this article.

In practice, the long tail model does predict certain kinds of consumption very well. I speak from experience analyzing view data at Veoh where, except for the very few top titles, a unit power law described number of views pretty well. This means that the number of views from sparsely watched videos is surprisingly large, adding to the woes of anybody trying to review submissions.

Economically speaking, though, you have to factor in a few kinds of friction. These are reasonably modeled as per unit sale costs and per unit of stock costs. The per unit sale costs don't affect the distribution of revenue and profit, but the per stock unit costs definitely do. If you draw the classic Zipf curve and assume that revenue is proportional to consumption for all items, then a per stock unit cost offsets the curve vertically. The resulting profit curve tells you pretty much immediately how things will fall out.

The graph to the right illustrates. The solid line is the classic long-tail distribution and the dashed lines represent different per stock unit costs. Wherever the solid line is above the dashed line, the model implies positive returns; where it is below, it implies loss. Clearly, the lower the stock unit costs, the deeper into the distribution you can go and still make money.

If we assume that you will only be stocking items that have non-negative return, then the percentage of profit that comes from a particular part of the distribution will vary with the threshold. For high thresholds, almost all of the profit will be from mega-hits but for very low thresholds, a much larger percentage will come from low consumption items.

This sort of situation is shown in this second graph which shows the percentage of total profit achieved for different thresholds and ranks. The concentration of profit in the low rank items for high thresholds is quite clear.

A good example of a per stock unit cost is given in p2p download schemes. The first few downloads of each item have to be paid for by the original source while additional downloads make use of sunk network resources that apply minimal marginal cost back to the source. For systems like bit-torrent, you need more than a hundred downloads before you get to high p2p efficiency which makes the system useful for mainstream content and less useful for body and tail content. The Veoh p2p system has a much lower threshold and is thus useful far down into the tail. Either system, though, leads to an economic return different from the theoretical zero-cost long-tail model.

None of these observations is earth-shaking and, as far as I know these are all common wisdom among anybody trying to make money out of the long tail. Why this is news to the Harvard Business Review is the real mystery to me.

Reading email

2008-04-16T15:37:00.000-07:00

And you thought that would be easy.

If you have ever written a program to receive email (not just pick it up from a POP server), you know just how painful that can be. If you wrote the program in Java, you know this even better.

The world just got better:

http://subethasmtp.tigris.org/

This package is just as simple as reading email should be. Your program decides whether to receive the email and then it gets it. The interface is tiny and it looks like they handle enough of the standards to really work.

Whew.

A random walk from eigenvectors to parallel page rank

2008-04-15T11:35:00.001-07:00

Power law algorithms are ideal for computing things like page rank. That isn't obvious, however.

The basic outline idea is that hub and authority style algorithms are intimately related to eigenvector or singular value decompositions (depending on whether the links are symmetrical). This also means that there is a close relationship to asymptotic beahavior of random walks on the graph. That probably still isn't obvious, so let's dig in.

If you represent the linkage in the web by a matrix that has columns representing source page and rows representing the target page and with a 1 where-ever the source page has a link pointing to the target page, then if you start with a vector with a single non-zero element equal to 1 as a representation of a single page, then multiplying by the linkage matrix will give you a vector with 1 in the positions corresponding to the pages the original page linked to. If you multiply again, you get all the pages that you can get to in two steps from the original page.

Mathematically, if we call the original vector x and the linkage matrix A, the pages that x links to are just Ax. The pages that are two steps from x are A(Ax) = A² x.

The eigenvector decomposition of A is just a way of writing A as a product of three matrices:

A = U S U'

U' is the transpose of U, and U has the special property that U'U = I (it is called ortho-normal because of this).

S is a diagonal matrix.

There is lots of deep mathematical machinery and beautiful symmetry available here, but for now we can just take this as given.

The set of pages n steps from x are

x_n = Aⁿ x = (U S U')ⁿ x = (U S U')^n-2 (U S U') (U S U') x
= (U S U')^n-2 (U S (U'U) S U') x = (U S U')^n-2 (U S² U') x
= U Sⁿ U' x

This is really cool because Sⁿ can be computed by just taking each diagonal element and raising it to a power.

Eigenvector decompositions have other, really deep connections. For instance, if you take the elements of S (call the i-th one s_i) then

_i s_iⁿ

is the number of paths that are n steps long.

Connected (or nearly connected) clusters of pages can also be derived from the eigenvector decomposition. This is the basis of so-called spectral clustering. For some very impressive examples of spectral clustering see this paper.

So eigenvectors are cool. But how can we compute them? And how can we compute them on BIG graphs in parallel?

First, note that if Aⁿ = U Sⁿ U' and if some of the s_i are bigger than others, the big ones will quickly dominate the others. That is pretty quickly, Aⁿ u₁ s₁ⁿ u₁'. This means that we can compute an approximation of u₁ by just doing Aⁿ x where x is some random vector. Moreover, we can compute u₂ by starting with a different random vector and iterating the same way, but with an additional step where we forbid the result from going towards u₁. With just a few additional wrinkles, this gives us what is called the Lanczos algorithm. Golub and van Loan's excellent book Matrix Computations gives a lot of information on these algorithms.

The cool thing here is that our random vector can represent a single page and we can approximate the final result by following links. Following links is just a (human-readable) way of saying sparse matrix multiplication. If we do this multiplication against lots of different random starting points, we can quickly build parallel algorithms to compute things like page rank.

Words at random, carefully chosen

2008-04-15T08:13:00.000-07:00

On comp.ai, Dmitry Kazakov reiterated the lonely cry of a frequentist against statistical natural language. This cry has been repeated many times over the years by many people who cannot abide the treatment of documents and language as if they were random.

Let's examine the situation more carefully.

On Apr 14, 5:28 am, "Dmitry A. Kazakov" wrote:
> ... It cannot be probability because the document is obviously not random ...

The statement "It cannot be probability ..." is essentially a tautology. It should read, "We cannot use the word probability to describe our state of knowledge because we have implicitly accepted the assumption that probability cannot be used to describe our state of knowledge".

The fact that an object has been constructed in its present state by non-random processes outside our ken is no different as far as we can tell than if the object were constructed at random (note that random does not equal uniform). What if the document were, in fact, written using the I Ching (as Philip K Dick is reputed to have written "The Man in the High Castle")? Is it reasonable to describe the text as having been randomly generated now that we know that?

Take the canonical and over-worked example of the coin being flipped. Before the coin is flipped a reasonable observer who knows the physics of the situation and who trusts the flipper would declare the probability of heads to be 100%. After the coin is flipped, but before it is revealed, the situation is actually no different. Yes, the coin now has a state whereas before the coin was only going to have a state, but, in fact, the only real difference is that the physics has become somewhat simpler, the most important factor in our answering the question of the probability has not changed. We still do not know the outcome.

Moreover, if the person flipping the coin looks at the coin, that does not and cannot change our answer.

When WE look at the coin, however, we now suddenly, miraculously declare that the probability is now 100% that the coin has come up heads. Nothing has changed physically, but our estimate has changed dramatically.

Moreover, if we now examine the coin and find that it has two heads, our previous answer of 50% is still valid in the original context. If we were to repeat the experiment, our correct interpretation is to give 100% as the probability before the flip. The only difference is our state of knowledge.

So philosophically speaking, probability is a statement of knowledge.

Moreover, by de Finetti's famous theorem, even if this philosophical argument is bogus, the mathematics all works our AS IF there were an underlying distribution on the parameters of the system. That means that we can profitably use this philosophical argument AS IF it were true.

The upshot is that even if you are a frequentist in your heart of hearts, it will still pay to behave as if you were a Bayesian. And I, as a Bayesian, will be able to behave as if you were rational because I will not know your secret.

How Not to Recommend

2008-03-28T10:04:00.000-07:00

A friend of mine pointed out The Netflix Prize: 300 Days Later this morning. The article points out how difficult it has been to make significant improvements on the Netflix rating prediction problem.

This article reinforces a lot of my own feelings. I continue to believe that recommendations based on ratings are inherently flawed. Among other things

predicting ratings from ratings is hard
predicting real user preferences from ratings is even harder
most people don’t rate things very much, if at all (makes #1 even harder)

All of these factors are eased considerably if you just get rid of the idea that you have to predict ratings. Observing real behavior and then predicting that same behavior is vastly easier.

The Power of Meta

2008-03-26T12:06:00.000-07:00

Evolutionary algorithms are oohhh so trendy, but they often provide very poor convergence rates. This occurs particularly when the population is in the neighborhood of a good solution, but the mutations being produced are far from that neighborhood because the mutation rate is too high.

Decreasing the mutation rate often doesn't help because then it takes forever to find the right neighborhood.

Changing the mutation rate externally can work, but you will usually get the annealing schedule wrong and have too much or too little mutation at some point.

One of the most effective ways to fix these problems is the technique known as meta-mutation. With meta-mutation, each member of the population has data about how dramatically it should be mutated. Then, when you are far from a good solution, members that take big steps can be big winners and their descendants will also take big steps. When you get close to a good solution, members with large mutation rates will step far from the best solution and will be mostly unable to improve the solution, but some descendants will have smaller mutation rates and these will able to find improved solutions. These calmer descendants will quickly dominate the population because they will be able to produce significant improvements.

Unfortunately, meta-mutation introduces the new problem of how you should mutate the mutation rate. (danger ... recursion alert)

I describe some methods that avoid all of these problems in my 1998 paper Recorded Step Mutation for Faster Convergence. The techniques are very simple and very effective. The paper is available from arxiv.

The real trick is that you can have the mutation rate encode the meta-mutation rate as well. One approach using a fixed distribution that is scaled by the current mutation rate. Another is to use the last step determine a directional component of the new mutation rate. Together, these approaches can improve convergence rate and final accuracy by many orders of magnitude relative to other approaches. Self-similar meta-mutation alone gives results that are nearly identical in symmetric Gaussian bowl problems to analytically determined optimal annealing schedules. When combined with directional mutation, results are near optimal for Gaussian bowls with low rank cross correlations.

Hello world for map-reduce

2008-03-25T09:20:00.000-07:00

There has been a surge of interest lately in map-reduce based parallel from many quarters. The public, non-google side of the that interest is largely focussed around an open source system of software known as Hadoop.

Lots of people are doing some very cool things with Hadoop. Yahoo is now running key parts of their web indexing infrastructure using Hadoop. Academics have described very impressive results in large scale machine translation developments. Facebook uses Hadoop for key parts of their metrics pipeline. IBM has developed a functional programming system on Hadoop. Imitators have been spawned.

But one key ingredient of any new computing technology is still missing.

What Hadoop has been missing to date is a good way to write a hello-world application in just a few lines of code. It has often been said that the ability to do simple things simply is a critical capability for a new technology. Hadoop, and map-reduce programming in general, does not lack a good hello-world example; the word-counting example provides that. What is missing is the ability to write this program in just a few lines of code. The word-count example that comes with the Hadoop distribution is over a hundred lines of code, most of which are impossible to motivate for a new user.

The basic idea is simple, the map phase tokenizes input lines and emits words as keys with (initial) counts of 1. The reduce phase takes all of the counts for a single word and sums them up. As a refinement, we can use a combiner to pre-reduce counts within the output of a single mapper.

So why is this more than 5 lines of code? The answer is that running a real world map-reduce cluster has some real complexity if you want the best possible results. Another reason is that in Java hiding complex implementations requires lots of noise tokens. It isn't that Java is bad, it is just that it isn't good for hiding complexity from naive users.

My answer to this problem is to move to Groovy, a language whose raison d'etre is specifically to hide the cruft in Java programs. Groovy isn't Java or an extension of Java, but Groovy programs inter-call with Java programs completely transparently and compile to the same byte codes.

So what should word-count look like? I think that it should look like functional programming. Our mapper should look like a function as should our reducer. They should be combined to produce a map-reduce program which should itself be a function that takes inputs and produces outputs. Those inputs should be any kind of input that we might like to use including lists of strings (for testing), local files and files stored in a distributed data store.

So our program really ought to look like this:

  wc = mapReduce(
  {key, line, out, report -> line.split().each {w -> out.collect(w,1)}},
  {w, counts, out, report -> out.collect(w, counts.sum())}
 )

and we should be able to use this program in a lot of different ways:

  wc(["this is input text", "for the word-counter"])
 wc(new File("/local/input/file")
 wc(findInterestingTextUsingMapReduce(new HdfsFile("/existing/distributed/file")

and we should be able to access the output very simply:

  wc(["this is input text"]).eachLine {
     println it
 }

Subject to some limitations in Groovy 1.5.4, this is exactly what my new system does. I call this new system grool because it is pretty thin porridge right now.

Send me email for a copy. I will get it onto a standard kind of open-source repository soon(ish), but you can try it sooner.

Surprise and Coincidence

2008-03-21T10:10:00.000-07:00

Some years ago, I wrote a simple paper, Accurate Methods for the Statistics of Surprise and Coincidence that has since seen quite a history of citation and use by others. The basic method was applied to get highly accurate language identification, species identification, author identification, document classification, musical recommendations, insurance risk assessment and video recommendations. It was eventually the core of my doctoral dissertation (ask me for a copy) and has been cited hundreds of times.

What hasn't been well described in the past is just how simple the method really is. In most of the applications above, it is important to find useful features in large amounts of data. The method at the heart of all of these algorithms is to use a score to analyze counts of events, particularly counts of when events occur together. The counts that you usually have in these situations are the number of times two events have occurred together, the number of times that they have occurred with or without each other and the number of times anything has occurred.

To compute the score, it is handy to restate these counts slightly as the number of times the events occurred together (let's call this k_11), the number of times each has occurred without the other (let's call these k_12 and k_21) and the number of times something has been observed that was neither of these events (let's call this k_22). In this notation, I am using row or column 1 to be the event of interest and row or column 2 to be everything else.

Here is the table we need

	Event A	Everything but A
Event B	A and B together (k_11)	B, but not A (k_12)
Everything but B	A without B (k_21)	Neither A nor B (k_22)

Once you have these counts, the hard part is over. Computing the log-likelihood ratio score (also known as G²) is very simple,

LLR = 2 sum(k) (H(k) - H(rowSums(k)) - H(colSums(k)))

where H is Shannon's entropy, computed as the sum of (k_ij / sum(k)) log (k_ij / sum(k)). In R, this function is defined as

H = function(k) {N = sum(k) ; return (sum(k/N * log(k/N + (k==0)))}

The trick with adding k==0 handles the case where some element of k is zero. Since we are multiplying by that same zero, we can drop those terms but it helps not to try to compute the log(0). The java or C versions of this (ask me for a copy) is almost as simple, but not quite as pretty.

So there you have it. Two lines of code and the world is your oyster.

Why the title?

2008-03-21T10:07:00.000-07:00

What kind of title, you may ask, is "Parallel and Uncertain".

If you were to ask, I would answer, "descriptive".

My main interests lately have to do with parallel processing and (automated) reasoning in the fact of uncertainty. Thus, these blog posts will be largely about these topics.

What more can I say?