Entries Tagged 'recommendations' ↓

I’m home again after my time in Boston with Project Aura. As I look back over my summer I am certainly nowhere near where I expected to be at the outset.

One part of the difference is simply that once I took the concrete step of saying “I don’t like robots and am going to actively pursue finding something I really do like,” it shifted how I see the world significantly. That process has largely been internal, but the external experience of working for Sun and being an intern was also significantly different than I expected it to be.

HR sent around an intern survey to ask us about how much we enjoyed our work experience and how we would rate the organization and whatnot. I filled in the blanks and was not looking to make any serious commentary. At the end, however, the survey wouldn’t let me finish without putting something into the blank for “What would you recommend that management do to make this a better place to work?”

The problem is the question is not a simple one to answer, so as is my wont, I gave them likely far more information than they wanted:

I’ve been thinking about the upcoming end of my internship and heading back to school and the direction of my life and my upcoming marriage and my health and my meditation practice and after a bit I think I burned out the clutch on my brain.

Instead of the 800 important things I had on my plate for the evening, I spent the last five hours reformatting chunks of a 600 page compendium of interesting literature.

I’ve been attempting to thieve some background reading on sociology to get ready for the ASA meeting, but it turns out that the thieves have tens of thousands of books of which nines of thousands are science fiction.

After screwing around for a while, I happened upon a reading list on Scribd (which has about as many books as the IRC channel) that is a combination of book lists from Harvard, Oxfam and a couple other places. The rote cleaning and proofing turned out to be much more relaxing than actually dealing with stuff I needed to do.

My hours of cleaning got the XML to validate, but not much more. Of the couple sections I did finish, I thought my many fecund friends might enjoy the selection of children’s literature. (The adventurous might also be interested in the ALA’s 100 most challenged books.)

There’s about 60 suggestions total, so I’ll just include a few as a sample:

Continue reading →

Item to item similarity is a method popularized by Amazon for computing the similarity of items in its catalog. The reasoning is that item similarities are more static than user similarities and so in situations where finding the similarity requires extensive computation they have an advantage in robustness to infrequent updates.

One of the possibilities that Aura is exploring is to leverage an existing TF-IDF implementation in minion.

I’ve been considering tags and what exactly it means when I “tag” a song. It has a different meaning than rating, and I think I have an idea of how to design a collaborative filter using tags, but I lack the vocabulary to really work out the idea.

I think the terms in need exist in the field of semiotics. This post is to define them so I can use them. To be precise, this is a combination of selected definitions with some additional interpretation. Semiotics is large, complex and controversial, and this is in no way authoritative.

Semotics attempts define a terminology to take complex inferences underlying interactions and make them explicit. The primary thesis is that interaction are significantly more complex than they seem at first glance, and as a result semtiotic writings frequently end up taking something seemingly simple and describing it in excruciating detail.

The basic building block of semiotics is the “sign:”

Continue reading →

One of the arguments put forth in the Herlocker survey is that if you ask a person to rate a song several times over the course of a few months, they are highly unlikely to give the same answer every time.

They describe this as a “natural variability” in human preference that perhaps represents a hard limit to how effective recommender systems can be.

While I do agree that preference is the product of a chaotic system influenced by variables many of which are unavailable to the computer system, it is true that much of the variability is encompassed by simple and easy to capture information. For example, I sometimes listen to dub when I’m writing code, because I can ignore it, but it would be completely inappropriate for working out. If the computer knew the types of music I liked while coding it could do a better job of pulling stuff for that category.

François is working on stuff to address the problem by allowing an explicit weighting of tags. Paul mentioned automatic characterization of tags such that I might have a “coding music” tag that is recognized as being situational rather than genre or mood, and specifically that the computer will figure out the category of that tag rather than me specifying it.

Another tact that I think will ultimately be necessary is to model preference as a time series characteristic rather than something static. What I like today is simply not the same thing that I will like tomorrow. The plasticity of the mind is undeniable (though there is certainly a neophyte / neophobe continuum along which most people lie).

I would not at all be surprised if there are characteristics common to songs that I have continued to like over the course of years and other characteristics common to songs that I liked for bit but have fallen out of favor. The changes are not just noise, they are important predictive data.

Maybe I’ll tackle that. Right after, I manage to write a baby collaborative filter. Who am I to let a complete lack of knowledge prevent me from doing something. ☺

Hoare’s Dictum: Premature optimization is the root of all evil.

— C.A.R. Hoare

I’ve been spending the last couple days reading about collaborative filters again. I got sidetracked for a bit trying to load some data into the distributed data store. I’ve been spending the last couple days wandering through papers about collaborative filtering. In particular Herlocker’s Evaluating Collaborative Filtering Recommender Systems is an excellent summary of the issues surrounding writing a collaborative filter.

One of the things I’ve been realizing is I simply don’t know enough about the field to design a general purpose framework. I’ve looked at the structure of systems like Taste, Cofi and CoFE, but I don’t really have the background other than in a broad systems design sense to evaluate what they’ve done.

The reason I’ve been thinking about Hoare’s Dictum is the ideal computer program would run instantaneously using no resources and do everything. Premature optimization is frequently discussed only in terms of execution time or resource allocation, but if I attempt to create a general model for collaborative filtering before I really understand the field I am optimizing the axis of flexibility before I really have the conceptual background to do so.

I’m a programmer. The way I get a conceptual background in something is to write a program. I’m not going to say I’m going to write a throwaway program (since people debate that most throwaway programs aren’t [thrown away]), but secretly that’s what I want.

Because I’m not shooting for a general framework and rather a specific program for the purpose of learning, it allows me to make a specific demonstrable goal which is much more manageable from a research perspective. So, what is a good program for a collaborative filter?

I figure a good choice would be something that is already being done by Project Aura so that we can compare their text mining techniques with a collaborative filter. So, what is Project Aura doing? Here’s what I know of from my month (has it been a month?!?) here:

• Document Similarity Based Recommendations:
  • Tagomendations — Finding artists that are similar to each other based on the tags provided by last.fm. The tags are “cleaned” prior to clustering so that distinctive tags will be more influential.
  • User-Based Recommendations — Instead of using the tags as the criteria for determining if artists are similar, use the listeners who enjoy a particular artist.
• Aardvark — Generating blog recommendations based a RSS feed of entries. The RSS feed is generally generated from Google Reader’s shared items.
• Tastebroker:
  • Generating APML from a user profile on Last.fm, Pandora or del.icio.us.
  • Making tagomendations based on an individual’s APML profile.
• GUI Visualizations — Populating 3D interfaces with similarities of both blogs and music using dimensionality reductions and color and size to represent some of the characteristics.

It seems like a good initial project is simply take a last.fm user profile and recommend an artist to them based on the tag space. Been done before, but that’s fine for a learning project.

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.

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.)

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.