Making Flexible Recommendations in CourseRank (Posted by Georgia Koutrika)

Some background on CourseRank

CourseRank is a social tool for course planning that we are developing at the InfoLab. CourseRank helps Stanford students make informed decisions about classes. It displays official university information and statistics, such as bulletin course descriptions, grade distributions, and results of official course evaluations. Students can anonymously rank courses they have taken, add comments, and rank the accuracy of each others' comments. They can also shop for classes, get personalized recommendations, and organize their classes into a quarterly schedule or devise a four-year plan.

CourseRank also functions as a feedback tool for faculty and administrators, ensuring that information is as accurate as possible. Faculty can modify or add comments to their courses, and can see how their class compares to other classes.

A year after its launch, the system is already being used by more than 6,200 Stanford students, out of a total of about 14,000 students. The vast majority of CourseRank users are undergraduates, and there are only about 7,000 undergraduates at Stanford. Thus, CourseRank is already used by a very large fraction of Stanford undergraduates.

Recommendations the Classical Way

Recommendations comprise an integral part of the system functionality. In order to generate recommendations for students, we initially adopted existing recommendation approaches (see Adomavicius and Tuzhilin for a good survey). However, although the initial version of CourseRank has been very popular with students (see editorial in the Stanford student paper), we soon had first-hand experience with the limitations of classical recommendation systems.

Limitation: Inflexible, canned recommendations

Similarly to most commercial recommendation systems, our initial version offered no choices, just a fixed list of recommended courses for the student to consider. However, users may expect different recommendations under different circumstances, and we received many requests, from students and administrators, for more flexible recommendations. For example, students want to specify the type of course they are interested in (e.g., a biology class, something that satisfies Stanford's writing requirement). They also want to request recommendations based on a peer group they select (e.g., students in their major, or freshmen only) and based on different criteria (e.g., students in their major with similar grades or with similar ratings). For example, a student may want recommendations for CS courses from CS students with similar grades (i.e., with similar performance) and for dance classes from students with similar ratings (i.e., with similar tastes). In some cases, students want to see the recommendations the system would give their best friend, not themselves.

Limitation: Hard-wired recommendations

The recommendation algorithm is typically embedded in the system code, not expressed declaratively. From the designer viewpoint, this fact makes it hard to modify the algorithm, or to experiment with different approaches. However, we (the CourseRank implementers) want to experiment with different recommendation approaches: Would approach X be more effective than approach Y in our environment? What are the right weights for blending two recommendations (e.g., one based on what students like, and another based on what courses are more critical for completing a major)? What is the best way to predict, not good courses, but likely grades a student will obtain in future courses?

To accommodate our end-users’ requests and also to meet our own research and development goals, we were faced with the prospects of implementing many different recommendation approaches and their variants. Therefore, we decided we needed to have more flexible recommendations, i.e., recommendations that could be easily described, customized, and executed by a single engine.

The idea of Flexible Recommendations (FlexRecs)

So, we designed FlexRecs, a framework for flexible recommendations over relational data. The general idea of FlexRecs can be described as follows:

• A given recommendation approach is expressed declaratively as a high-level workflow. Imagine that such a workflow comprises a series of interconnected operators that describe how a recommendation is computed. In a workflow, sets of objects flow from one operator to the next, and are filtered, ranked, etc. in the process. The workflow is a “high-level” description in the sense that it does not contain actual code, but rather, it describes what code (operators) to call upon. These descriptions can also handle parameters, so that end-users can at run time personalize their recommendations, e.g., by choosing the peer group of students to provide recommendations, or by weighting recommendations that are blended.
• A designer can easily express multiple workflows for different types of recommendations, as well as new types that the designer may think of. The end user can select from them, depending on her information needs. This selection is done through a GUI, which also allows the user to enter parameters for workflows in order to get more accurate and personalized recommendations. For instance, the user may specify that her recommendations be based on what courses students in her major are taking. Such functionality is essentially similar to advanced searches: a designer builds a set of parameterized queries. End users can transparently execute these queries with parameter values and receive different results through an advanced search interface.
  

Our framework describes how a recommendation workflow can specifically be defined for relational data, using traditional relational operators such as select, project and join, plus new recommendation operators that generate or combine recommendations. The recommendation operators may call upon functions in a library that implement common tasks for generating recommendations, such as computing the Jaccard or Pearson similarity of two sets of objects. The system can execute a workflow by "compiling" it into a sequence of SQL calls, which are executed by a conventional DBMS. When possible, library functions are compiled into the SQL statements themselves; in other cases we can rely on external functions that are called by the SQL statements.

We have built a flexible recommendation engine for compiling and executing FlexRecs workflows as part of CourseRank. The FlexRecs framework has indeed made it possible to define many recommendation strategies (at least all of the ones we have been able to think of to date). The new version of CourseRank, to be released September 2008, will let end-users tailor their recommendations. Although the end-users will only see choices from simple menus, and select values from sliders, they will actually be selecting what workflow to run, and with what parameters.

Thoughts on ECML PKDD Discovery Challenge (RSDC'08) (Posted by Paul Heymann)

Over the past few years, I have looked into a variety of problems in collaborative tagging systems, like whether they can be better organized, whether they can help web search, and how to avoid spam. Most recently, I have been looking at tag prediction; I will be presenting a paper called "Social Tag Prediction" at SIGIR'08 next month (more details on that in a later blog post). As such, I am very curious to see the outcome of the ECML PKDD Discovery Challenge (RSDC'08). (These are my initial thoughts as a non-participant, so if you have any complaints or find any errors, do leave a comment!)

BibSonomy and the University of Kassel

The Challenge is being put on by four members of the Knowledge and Data Engineering team at the University of Kassel:

• Andreas Hotho
• Dominik Benz
• Robert Jäschke
• Beate Krause

This team, along with about ten other project members is behind BibSonomy. BibSonomy is one of the three (or so) major collaborative tagging systems for academic publications (the others that I know of being CiteULike and Connotea). BibSonomy supports bookmarking URLs as well as publications, but its main sell over something like del.icio.us is that it helps academics organize and share publications. One particularly nice thing about BibSonomy is that they have always been willing to share their data with the academic community (see the FAQ for more details, CiteULike shares some data in an anonymized form).

Dataset

Most collaborative tagging systems focus on a single object type: e.g., URLs, books, products. BibSonomy is different in that users post two distinct object types: academic publications and URL bookmarks. Furthermore, the dataset (at least for the discovery challenge) has about equal numbers of (non-spam) unique publications and URLs (approximately 200,000 each). The dataset also denotes whether each user is a spammer or not, but here things are a bit less balanced. There are about ten times as many spam bookmarks as ham bookmarks, but almost no one seems to have bothered to spam academic publications. The full dataset statistics are:

• (tag,user,object) triples {ham: 816197, spam: 13258759}
• URL bookmark objects {ham: 181833, spam: 2059991}
• academic publication objects {ham: 219417, spam: 716}
• users {ham: 2467, spam: 29248}

See the dataset page for more details about the Challenge dataset.

Tasks: Tag Recommendation and Tag Spam

The Challenge consists of two tasks, tag recommendation and tag spam detection.

Tag Recommendation

Tag recommendation seems to be equivalent to what other researchers call tag suggestion, but slightly different from what I call "tag prediction." In a tag recommendation or tag suggestion task, the goal is to assist in the tagging process. As the user is typing in tags describing a particular object, the system also provides the user with a list of helpful suggestions.

In the Challenge, the "ideal" recommendation is assumed to be whatever tag the user ended up choosing, though one could imagine different definitions for what makes a recommendation "good."

For example, suppose most users in the system tag articles about music with "music", but a particular user tags such articles with "audio". A good recommendation in a real world system might be to recommend that such articles be tagged with "music" in the future so that the user has the same labels as other users in the system (enhancing discoverability of the resources in the system), but this would be a bad strategy in the Challenge.

By contrast, when I set up a "tag prediction" task, the gold standard was to detect all tags that could be applied to a particular object, rather than particular tags that particular users chose to apply to a particular object.

• Tag Recommendation (Suggestion): Given (user,object) try to guess tag.
• Tag Prediction: Given (object) try to guess all potential tags that could occur in (tag,user,object) triples in the future.

Thus, the goal of "tag recommendation" is to assist and speed up tagging by users, while the goal of "tag prediction" is to guess all of the tags that could be applied to a particular object. One helps the users add tagging metadata, while the other adds tagging metadata directly.

Neither is necessarily a better or worse task, but I am struck by how even for a relatively specific goal like "predict tags in a tagging system" relatively minor details can have a huge impact on the design and applicability of solutions to the problem.

Tag Spam Detection

The spam detection task seems similar to previous spam detection tasks. The goal is to guess which users are spammers, based on previous spammers labeled by BibSonomy. (This is different from our previous work, which looked primarily at methods for prevention, ranking, and ways to simulate spam in tagging systems.)

The traditional difficulty with such tasks is defining what exactly constitutes "spam content" and how much spam content constitutes a "spammer." However, it seems likely that even if some spammers go unlabeled, or if some legitimate users are mislabeled as spammers, the relative ordering of the spam detection algorithms will be approximately the same.

The bigger issue that I am worried about with this challenge is that most of the spam signals will actually be too easy to identify. Unlike the web or e-mail where spammers have been competing against spam detection algorithms for a decade or more, tag spam is relatively new.

As a result, it seems like certain really obvious signals might catch most spam, because tag spammers are not really trying that hard, yet. For example, a quick glance at the Challenge dataset shows that BibSonomy got about 56 legitimate URLs in China (.cn) and about 127,000 spam URLs in China (.cn). So you can eliminate about 6 percent of spam URLs by just ignoring all of China. Another top level domain constitutes about 20 percent of the spam URLs and just about 1 percent of the legitimate URLs.

In fact, about 40 percent of the legitimate URLs in the dataset come from ".net", ".hu", ".org", ".edu", or ".de" while only about 9 percent of the illegitimate URLs come from those domains. In other words, there appears to be a lot of signal in the top level domains alone.

Likewise, of the 2,467 legitimate users in the dataset, about half of them (1,211) post academic publications, while only 113 of the spammers bother to do so. As a result, it looks like the difficulty in the task will be finding the legitimate users who are just posting URLs (as opposed to academic publications).

Factors That Might Impact The Challenge

There are three factors that I think will have a big impact on the Challenge:

1. Compared to some other systems (e.g., del.icio.us), BibSonomy is relatively small. For example, the data in the dataset is equivalent to about two to four days worth of del.icio.us bookmarks postings. I wonder if this will end up having a big impact on the types of algorithms that will do well, in that they will have less data to work with. One of my favorite simple algorithms, association rules, might not do as well when there is less data to be had.
2. For the tag recommendation task, it seems like there might be big differences between predicting tags for academic publications and predicting them for URLs. In the former case, the dataset seems to have more text data, but on the other hand, the tags might be much more specific and sparse (e.g., "neuralnetworks" versus "funny"). Likewise, URLs may have easier tags to predict, but less text to predict them based on. With more text, it might make more sense to use algorithms that look more like text categorization, whereas with less text, it might make sense to use algorithms that look more like collaborative filtering. (Our previous work looks at predicting tags based on text and tags based on other tags in the context of tag prediction, Zhichen Xu et al. looked at tag suggestion in a more collaborative filtering style way in "Towards the Semantic Web: Collaborative Tag Suggestions.")
3. It also seems as though the setup of the task will force the best teams to model the user, as opposed to just the objects. Because a system does not get credit for recommending "rubyonrails" when the user chose "RoR", it seems that it will be likely to be important to model not just what the object is about, but what the user is likely to say the object is about. (Incidentally, machine translation also faces this problem: if two systems translate a piece of text, and their translations are both different from a gold standard, which one is better?) Furthermore, if the users tagging objects are themselves seeing BibSonomy's tag recommender, one may need to (directly or indirectly) model the user, the tag recommender, and the user's reaction to the recommender!
   

Ultimately, all of these reflect necessary choices made to setup the Challenge, but it will be interesting to see what impact they have on the winning systems. Good luck to all the teams!

Update (2008-06-20): A small clarification, it looks like the tag recommendation task will be somewhere in between predicting tags based on (user, object) and predicting tags based on (object). The tag recommendation submissions will be in the form (object, tag1, tag2, tag3...) so systems will not really be predicting tags for a particular user. On the other hand, none of the objects seem to have really complete coverage of all of the tags that could apply to them, so the task is not exactly tag prediction either.

Update (2008-06-23): Actually, contrary to the previous update, it looks like the tag recommendation task will be based on (user, object) after all. The confusion is that content_id is actually a combination of both user and object as opposed to object. This mailing list posting gives a few more details.

Simrank++: Putting together 3 simple ideas (Posted by Ioannis Antonellis)

Two ideas that really pushed web search further came from two completely different directions.

Two ideas

The first one, link analysis, came into play as a tool for improving the quality of search results. The idea as people express it today is simple, yet its power has been proven invaluable. The more web pages that link to your web page, the more popular your web page becomes.

The second idea, sponsored search, allowed search engines to make revenue, grow and keep providing their service for free. The idea again is simple: The search engine sells each keyword to up to 10 advertisers and it displays their ads to the users that issue a query with that keyword. Since the keywords are not real goods that you can easily set a price for, the search engines rely on auctions to determine the price for each keyword. (Had the search engines been able to set fixed keyword prices, many Ph.D. students, including myself, would have no thesis topic to work on...)

Another idea: The wisdom of Crowds

But, my favorite simple idea that has started flooding around recently is that of exploiting the wisdom of the crowds; the information that the billions of web users provide in all its forms. The most concrete and recent example of a successful application that is based on this idea is Wikipedia. Now that this large repository of knowledge has been created, many researchers have started to think about using it to improve existing data mining methods.

Another, still under development and immature, set of techniques that are based on the wisdom of the crowds uses click logs as a source of implicit information that web search users provide.

The paper

In our paper "Simrank++: Query Rewriting through link analysis of the Click Graph", which will be presented at Auckland, New Zealand in the coming VLDB 2008 conference, we are trying to put all these three ideas into play together. Specifically, we develop a link analysis technique for click graphs that can be used to increase the revenue of a sponsored search engine.

So, what is a click graph, how exactly do we analyze its link structure and how does this improve the revenue of a search engine?

Click graph

The click graph is a bipartite graph with query nodes on one side, ad nodes on the other and an edge between a query and an ad when a user that issued the query clicked on the ad. In addition, each edge between a query and an ad has associated with it a weight that corresponds to the number of clicks the query brought to the ad.

How to increase search engine revenue

The potential for revenue increase comes from queries that no advertiser has bid on. Since the search engine has no indication which ads are relevant to those queries, there are no ads it can display. Given such a query, if there was a way to guess which ads are relevant (but for some reason the associated advertisers decided not to bid on it), we could display the relevant ads and keep both the advertisers and the search engine happy.

The solution comes from the click graph: the wisdom of the crowds. Given a query, we use the click graph to generate a list of query rewrites, i.e., of other queries that are "similar" to it. For example, for the query "camera," the queries "digital camera" and "photography" may be useful because the user may also be interested in ads for those related queries. The query "battery" may also be useful because users that want a camera may also be in the market for a spare battery. Both the query and its rewrites can then be used to find ads.

The schemes we present analyze the connections in the click graph to identify rewrites that may be useful. Our techniques identify not only queries that are directly connected by an ad (e.g., users that submit either "mp3" or "i-tunes" click on ad an for "iPod") but also queries that are more indirectly related.

Simrank++

The intuition of our solution, Simrank++, is the following:

• two queries are similar if they are connected to similar ads and two ads are similar if they are connected to similar queries.
  

Sounds confusing, but it reveals the power of recursion. Initially each query/ad is only similar to itself, but by continuously applying these two rules, you end up with a similarity score for each pair of queries.

Are these scores always correct? How can we even define what a correct score is? And how does everything change when you try to take into account the edge weights of the click graph in the computation of the similarity scores?

The answers to these more detailed questions are in the paper...