Blog | Archive for the ‘Uncategorized’ Category

Calculating Pearson's correlation coefficient in SQL

By david | Sunday, November 23rd, 2008

Apparently I’m crazy.

Well, it’s not the first time this accusation has been levelled. But it’s one of the more amusing ones.

My colleague Jan Berkel was at Ruby Manor, where one of the talks was on acts_as_recommendable. Here’s what he had to say on the subject:

a plugin for rails to generate recommendations. lets you do things like user.similar_users / books.similar_books etc. it’s based on pearson correlation. the guy mentioned he ran into memory problems using large datasets for doing the computation (load all objects , calculate, store objects). i asked whether they tried performing the calculation on SQL level to avoid runtrips to the db (the way david implemented it). he first didn’t understand what i was saying, then someone from the audience said “you’d have to be crazy to do that”… i guess this elegant solution is not the ruby way.. anyway.

This entertained me, as one of the things I introduced recently to our theme extraction process is using pearson’s coefficient to rate similarity of themes. It never even occurred to me that loading it all to the client side doing it in Ruby and then saving it back might be considered an option.

Pearsons is very far from being the most powerful metric in the world, but remarkably useful for all that: It gives a decent scaled measure of similarity and is cheap and easy to calculate.

Ok. Well. Easy to calculate. And cheap to calculate if you don’t do clever things like loading the entire data set into memory. Anyway…

All joking aside, it wasn’t entirely trivial to do, and clearly this is something which is of interest to more people than us, so this post is an explanation of how it works.

The Pearson product-moment corellation coefficient of two distributions is a measurement of their similarity. Given random variables X, Y we define the covariance of the two to be:

Cov(X, Y) = E(XY) – E(X) E(Y)

The reason for this slightly strange looking expression is that random variables have the nice property that for two independent random variables E(XY) = E(X) E(Y). So if X and Y are independent then Cov(X, Y) = E(XY) – E(X) E(Y) = E(X) E(Y) – E(X) E(Y) = 0. The converse isn’t generally true (it’s true under some circumstances), but nevertheless we can use Cov(X, Y) as a cheap measure of degree of independents.

It has some other nice properties: Suppose Y = aX. Then Cov(X, Y) = a Var(X). So if Y is a positive multiple of X then the covariance is positive, if Y is a negative multiple of X the covariance is negative.

This also shows us that there’s no inherent significance to the size of the covariance. It depends on the variance of both X and Y – in fact, scaling either will increase the covariance proportionately.

However it does have the following nice property:

|Cov(X, Y)| <= StdDev(X) StdDev(Y)

(When one is a multiple of the other, equality is achieved).

This allows us to define the pearson’s coefficient (normally written rho):

rho(X, Y) = Cov(X, Y) / (StdDev(X) * StdDev(Y))

Which by the above property takes values between -1 and 1 (it will take value 1 when one is a positive multiple of the other and value -1 when one is a negative multiple of the other).

That’s all there is to it. It’s a nice scaled measure of how similar the two distributions are.

So, why do we care and how do we use this?

Well, the details of how we actually use this are cunning and proprietary. So I can’t really tell you those (I’m hoping that we may be able to disclose some of them at some point, but not just yet). So let’s pretend we’re trying to win the netflix challenge (I think some solutions actually do use this, but this example has the nice property of having absolutely nothing to do with how we use it in SONAR). We have movies, we have people, we have ratings of movies by people. Given two movies we want to determine how similar they are, based on the people who liked them.

Sound interesting now?

We can do this by considering the ratings of each movie as a random variable. A person is a sample of this rating space. So by considering the set of all people as a sample we can calculate the pearsons corellation over this sample (I know I only explained how it works for random variables, but it carries over in the obvious way for samples).

So we’ve got a setup: People, movies, ratings. We’re going to calculate the correlation between movies and store the results in the database (I’d like to use views for this, but MySQL does horrible bad things to view join performance).

Before I proceed, there are a few subtle points:

• Not everyone has rated every movie. I’m going to treat movies which have not been rated as implicitly having a rating of 0. This is sortof justified: Not watching a movie is often a stance about what sort of movie you like. Mostly it just makes the maths convenient.
• I’m going to ignore pairs of movies which have no rating in common. These have a corellation which is easy to work out (rho(x, y) = – mean(x) * mean(y) / (std_dev(x), std_dev(y))), and there tend to be a lot of them. This simplifies calculations and reduces storage overhead. Heavily anticorrelated movies also tend to be more because of holes in the data than interesting facts.

So let’s imagine our schema is set up as follows:

create table people(
  id int primary key
)

create table movies(
  id int primary key
)

create table ratings(
  person int references people (id),
  movie int references movies (id),
  rating float not null,
  unique key (person, movie)
)

We start out by computing mean and standard deviations for movies. Normally we’d use the built in functions for this, but unfortunately because we’ve got all those implicit 0 ratings floating around we have to do it ourselves.

Here’s the table in which we’ll store per movie stats:

  create table movie_statistics(
    movie int primary key references movies(id),
    mean float,
    stddev float
  )

We’ll only actually include stats for movies which have been rated at some point.

First we’ll calculate the mean:

  insert into movie_statistics (movie, mean)
  select movie, sum(rating) / (select count(*) from people) mean
  from ratings
  group by movie

Then the standard deviation:

  update movie_statistics
  set stddev = (
    select sqrt(
            sum(rating * rating) / (select count(*) from people)
            - mean * mean
           ) stddev
    from ratings
    where ratings.movie = movie_statistics.movie
    group by ratings.movie)

All perfectly straightforward, if a little annoyingly wordy.

Now we get to the actual interesting bit: Calculating correlations. First we create a table in which to store the results:

create table movie_correlations(

movie1 int references movies(id),

movie2 int references movies(id),
rho float,
unique key (movie1, movie2),
key (movie1),
key (movie2)
)
Now we need to populate it. This will proceed in essentially three parts. First, we need to calculate E(XY), so for every pair of co-occurring movies we’ll get a sum of their products over all people who have rated them. That’s Sum(XY). We then divide by the number of people to get the average value of XY (implicit 0s again). Then we’ll use our already calculated statistics to give us the covariance (E(XY) – E(X) * E(Y)), and then the correlation (divide by standard deviations).Or, to put it altogether in one massive great big query:

  insert into movie_correlations (
    movie1,
    movie2,
    rho
  )
  select sf.m1,
         sf.m2,
         (sf.sum / (select count(*) from people)
          - stats1.mean * stats2.mean
         ) -- covariance
         / (stats1.stddev * stats2.stddev)
  from (
    select r1.movie m1,
           r2.movie m2,
           sum(r1.rating * r2.rating) sum
    from ratings r1
    join ratings r2
    on r1.person = r2.person
    group by m1, m2
  ) sf
  join movie_statistics stats1
  on stats1.movie = sf.m1
  join movie_statistics stats2
  on stats2.movie = sf.m2

There, that wasn’t so bad was it? The inner query does the summing: By joining the ratings table to itself on the people we get all pairs of movies where we have a rating for both. We group by pairs of movies, thus summing over all the people who rated them. It’s then a simple matter to calculate the covariance and thus the correlation.

Or maybe I am crazy to look at a 23 line SQL query and say “that wasn’t so bad, was it?”. But at least I’m a crazy person whose code doesn’t run out of memory nearly as soon.

Here’s some code that ties all of this together: http://code.trampolinesystems.com/pearsons.rb

Posted in Uncategorized | 2 Comments »

Produce a members report for all your Mailman lists

By jon | Tuesday, October 14th, 2008

I recently had cause to produce a report on the membership of all our Mailman mailing lists, so rather than doing it manually I knocked together the following handy bash script…change mailman location and output file as desired

OUTPUTFILE="/tmp/mailman_report"

CURRMONTH=`date +%m-%Y`

LISTS=`/usr/local/mailman/bin/list_lists  | awk '{print $1}' | grep -v [!0-9]`

rm ${OUTPUTFILE}

echo "Mailman Report for ${CURRMONTH}" > ${OUTPUTFILE}

echo >> ${OUTPUTFILE}

for x in ${LISTS}

do

        echo "Members of List ${x}:" >> ${OUTPUTFILE}

        LIST_MEMBERS=`/usr/local/mailman/bin/list_members ${x}`

        for mems in ${LIST_MEMBERS}

        do

                echo ${mems} >> ${OUTPUTFILE}

        done

echo >> ${OUTPUTFILE}

done

/bin/mail -s "Mailman_Report_for_${CURRMONTH}" foo@foo.com -c blah@blah.com < ${OUTPUTFILE}

Posted in Uncategorized | No Comments »

The Hub FTW! Enterprise 2.0 in Boston Starts in a Week!

By peter | Monday, June 2nd, 2008

Trampoline will be in Boston in force in a week’s time (starting Monday 8 June) for Enterprise 2.0.

There are some great sessions, but the very best one will be the one where we buy you drinks – that’s Tuesday night. It says “smart dress is appreciated” but what we’d really like is if you show up wearing a cool hat. We love hats.

We have been pondering the almost obligatory references to the Boston Tea Party. If you have any suggestions for ways we can mine that particular cultural reference, please let us know.

The last post I made I referenced Spain and Spanish, and that produced an instantaneous onslaught of localized Spanish spam in our comments (all of which WordPress very precisely blocked). As blatant spam-bait, I am now going to attempt to reproduce this effect, except only with Boston English, hoping that the spam-bots are so good they will give me not only Boston-themed spam, but also spam written in Bostonian:

“Come across the rivah and inta town fuh the wicked pissa kegga we aw havin’ Toozday night! We ah down by the hawbah, therall be potty plattas, sgunna be killa!”

Posted in Uncategorized | No Comments »

Gartner Top 10 Disruptive Technologies in 2008

By peter | Tuesday, May 13th, 2008

Gartner is showing their top 10 disruptive technologies for 2008 right now here in Barcelona, and there’s some great stuff in here for us. I’m going to stick with the top 5 as we have plenty to think about there, and frankly the bottom 5 are a bit less clear so there’s not as much in there which says “do something now!!!!”. (List is ranked in importance by Gartner.)

Link to pic.

1. Multi-core – we’ve already factored SONAR for multi-threading, so we are in good shape to take advantage of multi-core solutions, provided of course we are on top of any OS that supports multi-core well. I think for Debian 64 we are pretty solid at least up to the number of cores we’re likely to see in the near future.
2. Virtualization – as you’ve seen in some of our other posts, we view virtualization as a great way to manage a complete SONAR install. It’s not the only way, of course – eg a VM is vastly larger (and often somewhat slower) than a native solution, however virtualization lets us build a complete working OS, JVM and SONAR solution here in the Trampery without having to worry about the underlying OS or Enterprise environment. VMWare FTW! (Hypervisors, as it turns out, are really important. Who knew?)
3. Social Networks and Social Software – w007! SONAR FTW!!! Nice to see Gartner putting this as number 3!
4. Cloud Computing and Cloud/Web Platforms – Gartner is basically saying that IT needs to just get over the whole “my stuff can’t run on a computer with their stuff” thing. Gartner note that Enterprises should know they can survive this because any enterprise which doesn’t actively BLOCK Google is sharing significant computing with, well, everyone else using google, and yet still everyone uses google and nothing bad seems to happen. We would love to run a hosted environment for customers on a third party like Amazon, however so far we’ve found that the security and overall risk-management concerns have prevented this. I look forward to trying this out – it could really free us up in some ways that could be quite handy for both us and for our customers.
5. Web Mashups – this is something we are, quite recently, seeing a lot more interest in, primarily from other Enterprise-serving vendors who see SONAR as providing them with some great capabilities they would have to work really hard to build themselves. We’ve started work on a meta-data framework and API which we think will radically improve what we can do in a mash-up environment, so stay tuned for more information on that.

All in all, it’s pretty cool to be either directly providing or directly supporting so much here.

Posted in Uncategorized | No Comments »

Habla Espanol? Gartner Symposium/ITxpo 2008, Barcelona

By peter | Friday, May 9th, 2008

I will be in Spain next week at the Gartner Symposium/ITxpo 2008, representin’ Trampoline. There are some cool sounding sessions, and evidently there is also a concurrent Gartner event (why oh why do people run two events at once in the same place? it’s hard enough with 5+ tracks in one event!) for us plucky new-comers to the enterprise scene. I will be at both. My interest is in where Gartner sees Enterprise computing heading over the coming months/years, connecting with technology providers, checking out our competition, and meeting with customers.

It should be interesting as I don’t speak Spanish. Much as I delight in saying “Berthaylona”.

I begged my 12 year old son to ‘splain to me how I might go about ordering food, or even just bottled water, when my vocabulary consists of cerveza, a few Mexican food names, and por favor. (I speak Simplified American Taco-Truck quite well, thank you very much). He said he’d try to send me a few sentences in email, which means that evidently some 12 year-olds know of this old-fashioned thing called “email”. Not very many. Like maybe 2. That’s a trend right there! I’m sure Gartner is all over it.

And yes, I do know about the interweb and it’s language-ness, and translation books. It’s just been a few years since I was last in-country where I don’t speak the language AND I’m travelling on my own. I’ve become wussier in my old age. In China, Germany, France, Japan and even the UK, where they speak something called “English”, I have or had the benefit of translators…

Anyway, if you are at either show, please let me know. We can drink some, er, agua and eat some, er, frittata? : ) If you speak Spanish and will be there then hey, you are my new BFF! Peter (at) trampolinesystems (dot) com

Posted in Uncategorized | No Comments »

Companies are for-profit Communities

By peter | Wednesday, April 30th, 2008

I’ve seen a few comments on blogs about the intersection of social networking and business which questions the idea that an enterprise is a social network at all. Some have simply made the assertion that social networks and businesses are totally different – eg on the SONAR tech-crunch posting, Phil Dewey commented: “Does “enterprise social network” = social networking for a******s? Seems like “enterprise” and “social” are mutually exclusive…”

Companies are for-profit communities, and as such share many, if not all, of the characteristics we associate with any other type of community. Enterprises are most certainly social.

Posted in Uncategorized | 1 Comment »

Trampoline and the economy

By peter | Monday, April 14th, 2008

It’s super important that we think about how Trampoline should act in a flat or recessionary economy.

From this http://blog.hbs.edu/faculty/amcafee/index.php/faculty_amcafee_v3/recession_tech/ posting:

“Third and finally, as business slows down workers often have more slack in their weeks. When this is the case it’s easier for them to find time and energy to participate in Enterprise 2.0. So lean economic times might be the right times to launch an effort to build an emergent social software platform.”

Recessions are most likely to bring MORE work for fewer IT people, not less. So let’s think about how a recession could affect us.

It departments have been under the efficiency grinder for quite awhile now. The days of bored IT people sitting around doing nothing are well over. After the inevitable fat is trimmed, usually some meat gets lost as well, and so some departments, unhappy that they now have to wait around for 3 days to get email turned back on by IT, will staff up with a few folks who manage mundane things like printers not working, etc. In some cases these people have so much work that they grow to resemble small IT organizations unto themselves. These people may be contractors or full timers.

Whereas in the past, IT might resent this intrusion into their domain, they may well actually like these guys now because it means that someone other than IT sucks up first-line issues that the It department essentially gets credit for. In other words, the “efficiencies” that exec management forced onto IT after the dot-com bubble burst seem to be working because the accounting system doesn’t count people in departments as “IT”. So like magic, fewer people seem to be doing more work.

Now comes a recession and real downsizing. There are a few ways of cutting staff – I’ll focus on 3: Peanut buttering, early retirement, and targeted re-structuring.

Peanut-buttering is the most common, unfortunately. In this model, every group is given a target – say an 8% reduction. Every department gets to do this however they want. A bell curve of competence means that at least half the company will do this poorly, unfortunately, so it can appear to be completely random. Even when done right, it’s not perfect because it’s hard to say how this supports overall strategic imperatives. Hopefully the first people to get cut here by will be “overhead”, meaning contractors (easy to lose) and people who aren’t part of a core business, like the co-located, non-IT, IT people above. (In the good old 90s you could get away with cutting FTE and then immediately replace them with contractors, often paying more for the same people you just downsized, because accounting tricks let you do this. I don’t think that this happens much anymore.)

So first off, there’s an issue of downsizing of departmental (co-located) IT staff, which reduces the overall capacity of the entire company to manage IT. This immediately means MORE work for IT, not less. IT won’t be given more staff, of course, because the rest of the company is belt-tightening, there’s no way that IT can get more people. So with departments now completely beholden to IT again, there’s more work heading into IT.

Then comes staff reductions through early retirement or cutting off low performers. In both cases those people are encouraged to quit through a variety of means. For IT, off-boarding requires IT work more, just like on-boarding does. Accounts must be deleted, physical assets tracked, documents archived, etc. So, more work for IT. Oh, and in these cases it’s rare that the actual HIRING slows down significantly because no company wants to be in a position where, when the recession is over, the best and brightest all work somewhere else. So again, more work for IT.

In targeted re-structuring (IMUNVHO the best way of managing this) the exec staff make a decision about what the most important bets are for the c
ompany, and then they a) move the very best 5-10% of people in any group not working on these things to the important bets (meaning that, even in a recession, the big bets get an increase in funding!), and then cut the living crap out of other groups. Hopefully in some cases this means getting out of businesses altogether.

All this means, you guessed it, more work for IT.

What does this mean for us?

Easier technology is certainly better. Going with a VM-based solution is a good plan and gets better here, provided of course that we can get the perf we need. We will do our own SONAR installs on VMs from now on to prove to ourselves that they work and so we are dogfooding.

Why full VMs and not just the JVM? While much bigger, fatter and somewhat slower than systems with less abstraction, full VM’s are also the most portable solution, so if things change departmentally underneath us, then a VM is our best bet for picking a server up and moving it somewhere else. They also mean that we don’t have to care about things like the underlying OS or hardware as much. Every enterprise kinda sorta looks the same at least for this part of the stack. We can dogfood our solutions essentially the same as our customers much more easily.

Clearly we have some selling opptys that “old school” SW may not have. We should focus on empowering besieged employees to do more with less and to enjoy their jobs more. Another selling oppty will be linking into CRM and the sales pipeline – the best time to steal customers from your competitors is when they are facing downsizing, so talking about how we make that work, and how we make defending existing customers work, is very good.

IT will have to start cutting into some projects. I think that big, “re-do the entire enterprise so it sucks less” things will get postponed. After all the company has found a way to do what they do with the existing suckage, so they can assume they can afford to wait. Low-risk new projects are going to be higher pri than high-risk, as no one wants to be called up for breaking something critical in a down economy. Not fun. So our “stay out of the way of critical infrastructure” architecture is important.

Our heterogeneity is critical, as companies with more than one architecture will wait out homogenizing things. We hear that people are planning on deploying things like SharePoint and Exchange, but any wholesale move to just MSFT or any one company should be years out, at best. And our ability to easily integrate new data sources means that we can just say “bring it on” whenever a customer comes up with a new plan for a wiki, blogs, IM or something else.

Also we don’t require massive work to get up and running, in spite of the bumps and bruises we are involved in right now with pilots. We aren’t spreading the work out around the entire enterprise and we don’t require massive training. Frankly we’re pretty painless compared to something like a CRM system which involves lots of hand-wringing and holding and which inserts something into a business process, making its failure far more risky.

Lastly, we have a lot of flexibility in how and when we monetize, which is very good, and we aren’t reliant on the overall health of third parties (eg advertisers) to make money. It would suck to be totally beholden on both our enterprise customers and also an entirely separate segment of the economy.

All in all, I think our pluckiness and positioning should serve us well, even when things are a bit hairier as budgets disappear and people don’t return calls because they are busy dealing with the latest crisis.

Posted in Uncategorized | 3 Comments »