Archive for recommendations

Basic Recommenders

After adventuring my way up the Eastern Seaboard, I am finally settled into my swanky pad outside of Boston and beginning my summer with Project Aura. So far everyone seem quite friendly and they seem, by and large, to have their souls intact, so I’m hopeful that I’ll emerge from the summer not too deeply scarred from being an agent of the man.

I’m starting off with building a simple recommender, a collaborative filter, on top of the distributed datastore that they have been developing. Before delving into collaborative filters directly though, I wanted to consider some of the simpler forms of recommendations.

Perhaps the simplest recommendation is one that takes no preference into account at all. This is what I get when I put Amarok on random and set it playing. Not great on accuracy, but pretty much impossible to beat on speed.

A step up from that is a recommender system that incorporates preferences, but aggregates them — voting. Voting makes a lot of sense when the aggregate choice is going to be applied to everyone, say with a political candidate. It makes less sense when the choice is only for an individual. It is still used though: when you go to a website and it tells you the ten most popular products, those have effectively been chosen by a vote.

Not only are vote-based systems not personalized, they are also subject to some pretty serious mathematical problems. I’ll not go into them other than to mention that one vote plurality is just about the worst possible method if you’re concerned about picking the choice with the highest average preference. Similar choices will cloud the genuine group preference, as Ralph Nader and Ross Perot helped to demonstrate.

There are other vote-based systems that have better mathematical properties, but I’ll not go into them because all votes are about systems where a recommendation is being made for a group and Aura is concerned with making recommendations for an individual. (Well, it may be interested in making recommendations for groups of individuals for speed purposes or community generation purposes, but not at this point.)

Some of the earliest methods to consider individual preferences, which are standing the test of time, are pieces of software known as collaborative filters.

The first collaborative filters were user-based. If, when you and I are asked about ten movies we responded similarly, then there is a higher than average probability that our responses will be correlated for an eleventh film. This is a reasonable assumption and it does work, but it has some problems.

One that affects almost all recommender systems is “cold start” — if I’ve not rated anything (or only rated a couple things) then the system doesn’t really know who to compare me to for guessing my preferences.

Another is update cost. There’s not simply two users in the system; there are potentially millions. The system doesn’t generally look for one that has the exact preferences as me. Instead it compares my similarity to everyone and uses that similarity to weight the influences of the other preferences. This means that any time anyone in the system adds or changes a preference for something it affects the weight for everyone else who also has a preference for that item.

Collaborative filters are either active — explicitly asking the users to rate items, or passive — collecting incidental data such as time on a page to infer a user’s preference. Either way, a user will potentially generate a meaningful difference to their preference profile during a single visit.

A method pioneered by Amazon is based around identifying item similarity. Rather than comparing users to each other, take user preference data and generate a model for how related items are assuming that the more people are interested in two things, the more likely they are to be related. This helps with the previous issues in two ways:

Cold start — when a new user enters the system you know nothing about the user. With a new preference item, however, you have the item. Depending on the nature of the item you can examine its properties and attempt to fit it into a relatedness model. This type of work is the purpose behind autotagging music and documents — figure out what they’re related to without human intervention.

Update cost — it isn’t cheaper to update an item-based system, but the rate of change is generally slower, so the process doesn’t need to be as quickly reactive. It also helps that if a new user sees a slow reaction time you may never get another chance to collect more information from them whereas an item will likely hang around for a few days.

I have two problems with item relatedness. The concept was pioneered to some extent by Amazon and it makes sense within the context of people purchasing things. I often go shopping and buy a set of things for a project or I will tend to buy things related in an area. This is a measure of relatedness however and distinctly not similarity. In fact if I bought one book on growing tomatoes it makes it likely than average that I’m not going to buy another unless I’m really into tomatoes. So there’s a blank spot around each item where items are similar enough not to be purchased.

Amazon seems to fill this in with info about browsing because I am likely to look at two similar items to compare them. There’s also probably some time series considerations in there as well since the longer between when I bought two things the less likely they are to be related, I would think.

With preference there is also the danger of not having all the salient characteristics in the system. For instance, I’m listing to Garth Brooks’ The Hits right now. I listened to country in high school. I like ’90’s country songs because they remind me of that period. I don’t really listen to much modern country. Relatedness of items is individual to certain users and item-based similarity loses those distinctions.

Also, for something like blogs or music though there is a Heisenberg sort of effect. Liking a song may get me to like a genre or hearing too much of a song may turn me off. The sweet spot is to give me what I want, but not too much of it. Relatedness is not really going to give me that information.

Comments (1)

Recommending Meaning

I am a huge storytelling fan. I’m from Bristol, Tennessee which is a mere stones throw away from Jonesborough where each year of my youth we went to see the National Storytelling Festival.

I was down in Asheville these past few days visiting with the middle of the three Holcomb boys: Matt. (I’m the eldest.) We were there ostensibly for his birthday, and one of the events we went to see was the live simulcast of This American Life.

If you are unfamiliar with This American Life, I recommend you take a moment to listen to a piece or two from the archive. Every week they have a theme and collect three stories on that subject from someone. The stories can be simple or they can be topical. I blogged months ago about crying while listening to stories from Iraq.

Anyhow, scientist metacognician that as I am, after I got through watching the movie I was thinking about what made particular stories particularly touching to me. There was a topical piece where an Iraqi now living in the States went around with a little booth, ala Lucy Van Pelt, with a placard “Talk to an Iraqi”. He recorded the responses from everyone who came to talk to him and, with his own narrative, drew together a story.

The piece ultimately makes a compelling argument against the War in Iraq. My family was discussing the piece in the car. No one in the car is particularly fond of how the war is going, but despite our common opinion, we had a variety of perspectives on what was important. My father and I were interested in the piece as propaganda, my brother in the salient information for American policy, my mom in the lives of some of the speakers…

Much like with what I understand of music, different characteristics appealed to different people. It begs the question of if we can form a set of salient and discrete descriptors for a story (as we attempt to do with timbral characteristics of music) so that I could guess ahead of time how much someone is going to like a story.

Also it makes me wonder what you would attempt to measure about a person to try and help you build a model.

I’ve always thought it would be fascinating to have access to a data source like OkCupid where people have completed thousands of psychometric tests. I don’t know if feeding that data into a clustering algorithm along with preference data might help us build a better model of how personality and musical preference interact, but it would be so amazingly interesting to give it a shot.

(As I’ve mentioned, control of the data is already starting to shape scientific progress.)

Comments (3)

Viral Licenses

Matt reminded me of this and I wanted to mention it.

I mentioned I think we will be entering an area where the data that a company has collected about me rivals the actual functional characteristics of their software in a consumers investment in the product.

From a market perspective the best situation would be if the data were open and accessible to whichever competitor wanted to make the strongest product using it. What though is a company’s impetus to give up the competitive advantage of keeping data secret? Calling on companies to be noble enough to support the market is naive and expecting customers to invest in a company simply because it doesn’t lock them is unlikely given my understanding of the current users view of the market. People want stuff to work now and don’t think about the future all that much.

What if you did something like the GPL‘s viral licensing? I have some data and you can use it but only if you agree to give me any changes to that data and any additional data that you collect about this person.

What the structure would look like to support that exchange I’m uncertain. Some APIs and lots of XML I assume, but it’s a potential solution that could work well for the market overall.

Comments (1)

Thin Servers

Real quick because I ought to be doing my psychology homework…

I’ve been considering social feedback in increasing user loyalty and community involvement in online systems.

I was a Pandora listener for a while. I liked Pandora because it gave me interesting songs, but I like a really broad range of types of music and Pandora seemed to narrow for my tastes.

Jango is what I went to next because the interface was better for adding artists to my profile. It seems to stick to a genre for a while and then switch over and do another. I generally like it and I’ve gotten a couple of new songs from it. It gives some community feedback by having stations associated with individuals. You only stay within one person’s recommendations though. Maybe there’s community stations I just haven’t found yet.

Grooveshark seems to be really close, but I’m waiting to actually be approved to use it. I think that they’re dealing with the P2P issues and attempting to avoid the RIAA by being selective in their listenership.

I suspect though that they’re addressing a question that I’ve already had. I have a bunch of songs on my computer at home that I legitimately own. I have playlists there that I would like to have access to (and I would like to be able to create playlists while at work that I could listen to at home). Why, since I own this music, can’t I listen to it?

There’s a Y-Combinator startup reble.fm that allows streaming of songs. Streaming is legal even to other people so long as only one person is streaming at a time and the group is small.

The idea of thin servers solves four problems:

  1. I own a bunch of songs and I should be allowed to use interfaces that allow queuing and seeking those songs in whatever method I want.
  2. I have an awesome song from a great local band that isn’t in any of the recommender systems.
  3. My band has a great new song that we want other people to potentially have recommended to them.
  4. My huge server is completely swamped by 10,000 people all attempting to listen to music simultaneously.

Recommendation interfaces based around confederations of thin servers increase their potential network issues exponentially, but the state of broadband may well be such that this is a surmountable challenge. Music is nowhere near the bandwidth hog that video is. In exchange for those issues you allow anyone who wants to begin serving music, and you allow individuals access to the greatest source of songs that they are likely to like: their personal collection.

Leave a Comment

Griefers

I’ve been on the road the last few days working on various projects and making my way slowly (over a week and a half span) to Boston. Being carless, much of my transport and housing has relied on the generosity of others. As Matt carted me from Cookeville to Bristol, we discussed the problem of “griefers.” Griefers being those inevitable folks who, when presented with a system, will try to break it. Bruce Schneier defends many of their characteristics under the auspices of “hackers”.

We were discussing interesting A/B tests you could run if you had a successful recommender system. He mentioned Joel Splosky who writes on building communities in software from time to time. One of the things Joel supposedly does when deleting a post is to delete it for everyone except the original poster. So far as the poster is concerned, nothing has happened.

The idea of building communities online is one I want to explore and I hadn’t really considered the all the axes along which things can vary.

I know that the stuff I write about scientific determinism seems disjoint from the contemplations of recommender systems. The reason I keep coming back to it is the way science works is we design systems in terms of fundamental assumptions. If the assumptions are far enough away from the design they can seem disjoint, but I hold they aren’t.

Consider griefers. The traditional way to see them is as a problem to be eliminated. What they actually are is a population that has energy they are willing to devote to the system. As a population there is likely a trend in the motivations.

Read the rest of this entry »

Comments (2)

Building the Matrix

I made a snippy comment the other day to Jenni (my fiancée who’s doing her Ph.D. in public health at Johns Hopkins) about the difficulty of “soft” sciences like history and psychology versus “hard” sciences like physics and chemistry.

In the ensuing amicable discussion, she effectively proved her primary thesis — I was being an ass. ☺

Soft sciences represent the forefront of human knowledge. The models don’t lack precision because the people making them aren’t bright enough to make them. They lack precision because they’re so amazingly complex that the sum total of human knowledge hasn’t given us a precise model.

Consider the process of immunology. Long long ago we ate whatever the hell we wanted if it didn’t smell too funky. After a while people started to recognize a trend that certain things smell ok, but will still kill you. For example trichinosis can affect seemingly healthy pork. So, we come up with a model where God tells us to not eat pigs.

If you follow a religion that still doesn’t dig on swine, I’m cool with that, but most of the Western world has decided God’s ok with it. I blame bacon, how long could we be expected to hold out against that delicious temptation?

Read the rest of this entry »

Comments (4)

Dearest Overlord

Fading are the days when being born the son of a doctor means I’ll be a doctor. Or being born a woman means that I will be a homemaker. The increased freedom is wonderful, but even in this modern world these decisions have consequences and have to be considered in terms of the raw meat that backs behavior: the brain.

From an evolutionary psychology perspective, brains are complex structures with one job: keeping their genetic code in existence. Human brains do this in large part by connecting observations together and recognizing patterns that can be exploited. Maybe I notice that little trees start from around the area where bit trees drop nuts. I connect nuts to trees, abstract things out to other types of seeds and, voila, agriculture. This gives me a definite survival advantage over the squirrels that just see trees and nuts.

The problem though is that there’s simply a limit to how much our gray matter can handle. Studies on working memory have fairly consistently limited us to about 7 ± 2 (2.5 bits) of information in our head at a time.

Read the rest of this entry »

Leave a Comment

Survivor Bias and Recommendations

I have been discussing the idea of Survivor Bias from Taleb’s The Black Swan.

The basic idea of survivor bias is we generally abstract the characterisitics that make up a set only from the members of that set. The unknown component of the analysis is frequently the extent to which those characterisitics were present in elements that didn’t make it into the set.

The example he gave is a researcher who has been tasked with fortifying the planes going out to fight the Nazis in WWII. Simply adding more plating all over will make the planes unreasonably heavy, so he looked at all planes coming back from missions and put plating wherever those planes hadn’t been shot.

It may seem as though you want to take your planes and shore them up in the places they’re getting shot so they’ll be stronger. He realized though that he was working with the set of planes that had been shot in places unimportant enough to take them down.

The basic idea is that you study can’t tell you what caused someone to succeed. It can only probably tell you things that contributed to failure.

And it can only do that if there’s only one factor at play. Imagine that planes shot through one wing have a 5% chance of going down, planes shot through both have a 25% chance of going down and planes shot through both and the tail have a 75% chance of going down. The set of planes you look at are going to have holes in all those places and you might not shore up any one of them. The analysis necessary to see the trends increases expodentially with the number of factors you consider.

One of the themes of The Black Swan is because there are so many factors and our models are so limited there will always be “black swans” — events completely outside of reasonable expectations that change the ways of thinking.

How does this relate to recommendations? Well, I have some info on some songs and the sort of person I think likes them. The cold start problem is what to do when I either have a song I know nothing about or a person I know nothing about. The person is tricky, but with the song I can look at the auditory characterisitics of the song and compare them to other songs a person likes. This guess though is going to potentially be skewed because of survivor bias.

People like music for a variety of reasons: the song at my prom, the song I associate with my first infatuation, a song from a particularly awesome party, a song a sang in a choir — songs that have to do with the moment rather than the actual musical characteristics of the song. Using those songs to guess the characteristics of what I like musically isn’t going to work.

Pragmatically, this issue encourages a system that asks the question “how likely is someone to dislike this song?” as well as “how likely is someone to like this song?” It also reinforces the drive to incorporate external information sources that can help build a profile of the user that is independent from simply their listening profile.

Comments (1)

Blog Recommenders

On the subject of my previous post about economic modeled music recommendations — I think a really good application of this would also be to blogging.

Imagine an app something like Google Reader, but where instead of me manually adding in bunches of feeds by myself, I log in and the program gives me a feed of items I am likely to like.

It’s related to the service that Stumble is doing, but collected in one place and with a more visible data model. Since the entrance to creating blog entries is lower than with music, you’d have a new factor. You’d have your audience, your exemplars and, if the application was popular, the bloggers would start to react as well.

Thinking about it in terms of blogging made me realize an assumption I made about music geeks. I assumed that a music geek would just start to slowly wider their horizons and start to like new genres. That the set of optimal songs for a given genre though would stay the same.

That’s not necessarily the case though. Imagine that as someone expands their musical horizons they begin to recognize good musical form. Peppy but sloppy songs they used to like may fall out of favor. Musicianship doesn’t always correlate to popularity.

Mathematically what this means is that a song isn’t simply a member of a single cluster because depending on the cluster the quality of that song will differ. A song is essentially in every cluster simultaneously to a varying (and frequently very small) amount. It suggests a different method for finding clusters by looking at patterns across axes rather than something like k-centroids that looks at all of them as a whole.

Leave a Comment

Trading Songs

I’ve been considering a recommender system that attempts to identify individuals that are exemplars of a particular set of musical tastes. The data on clustering suggests that there are definite groupings of preference (which I’m betting map to genres). So, I’m hunting for the prototypical country listener or rap or whatever.

That idea has been done before to some extent. I know I’ve seen something on the idea of creating a sort of composite profile to represent a cluster, but I don’t know if I’ve read anything about attempting to identify an actual person who fits a cluster and then paying particular attention to that individual’s preferences.

In any case, I identify a set of exemplars. How many is a function of the data and how tight the clusters. With these people I create a system where these exemplars get positive social or emotional or financial feedback introducing new music to the system. Because their preference patterns are prototypical for the group, my reasoning is that the songs they pick will hit on whatever the key characteristics are and their recommendations will be “better” (as a function amount that a random user from the group will like the song).

Note that a convenient function of this system is that we aren’t trying to model what makes a song good even though our ultimate goal is to pick “good” songs to recommend. We are simply trying to model what makes a set of songs similar in human perception. Even if what actually makes a song good is not captured within the system, if that characteristic correlates to things that we are measuring then we can still get a correct grouping.

It’s a semantic point as much as anything, but it shifts the focus somewhat. It lends credence to the direction that Project Aura is headed because how much someone likes a song isn’t simply a function of the timbral or melodic characteristics. I know several feminists that don’t like rap. Honestly they have some pretty good arguments about misogyny and the objectification of women within that culture. A salient grouping characteristic though between a set of people and whether they like rap of not is going to be if they are feminists. That’s not the only axis, but it’s an example of a grouping that has nothing to do with the music itself that is useful if I am going to recommend a song to someone.

Read the rest of this entry »

Leave a Comment

« Newer Posts · Older Posts »