eBay Tech Blog

Personalized Search at eBay, part II

by David Goldberg on 11/04/2011

in Machine Learning,Search Science

In the first part of this blog posting, I talked about how to estimate a buyer’s propensity to purchase an auction over a fixed price item. I gave the Empirical Bayes formula f = (a+k)/(a + b+ n) for the auction propensity f which is a compromise between the buyer’s shopping history k/n and the propensity of his peer group a/(a+b). In this posting I will explain where the formula comes from, and how to compute the numbers a and b.

Since the method is called Empirical Bayes, it won’t surprise you to learn that it uses Bayes Theorem

The specific form I’ll use is

In this formula, p is the probability of buying an auction, n is the number of purchases that a shopper has made, and k is the number of those purchases that were auctions. The left-hand side is what I’d like to know: the probability (propensity) of an auction given that the buyer has previously purchased k/n auctions. As usual, the reason to use Bayes formula is that it relates the unknown left-hand side to the computable right-hand side.

The pleasure of Bayes formula is the first term on the right-hand side. This is the textbook formula we’ve seen before:

The pain of Bayes formula is the second term, the prior Pr(p). This is the estimate of p before (prior to) learning there were k/n auction purchases. Much time has been spent debating what value to use for the prior. This is where empirical Bayes comes in. I will use the data itself to estimate Pr(p). I do it by assuming that Pr(p) follows a Beta probability distribution

and all I need to do is specify the two parameters a and b. Why this distribution? It’s general enough to fit most data, but simple enough to make explicit calculations possible. I’ll do those calculations in a moment. The following figure from Wikipedia shows the first point. By varying the parameters a and b (α and β in the figure) you can get a large range of distributions.

Now for the details of how to compute a and b. The probability of purchasing k/n auctions is

If I don’t know a precise value for p, but do know it varies via some probability distribution Prob(p) then pk is an average over those p, expressed as the integral

As I mentioned above, I’ll assume that Prob(p) is a beta distribution

Now plug this value of Prob(p) into the formula for pk which I’ve written as pk(a, b) to emphasize the dependence on a and b.

If you’re following along in detail, you’ll see that I did some simplifications after the plug-in. The important thing is this: the value of pk depends on the known k, n and the unknown a, b, and my job is to pick those a, b so that

is minimized. In other words, I want to make the computed pk as close as possible to the observed fraction, which I’ve written with a hat. For example p2 (a,b) is the computed fraction of people in the peer group that bought 2 auctions assuming the prior is Beta(a, b), while p2 with a hat is the observed fraction of users who bought two auctions.

Here’s an illustration. Suppose the peer group is users who’ve purchased 21 items. Then the best values of a and b are 1.16 and 2.22 which gives this beta distribution:

Once I have a and b I can compute the pk (a,b) and see how closely they approximate

The match is excellent. The red predicted curve has only two parameters and yet it has a very good fit to all 22 points.

Now that I’ve explained how to compute a and b, I can explain where the formula f = (a+k)/(a + b+ n) comes from. Use Bayes formula

and substitute the beta distribution Ba,b for Pr(p) as follows:

I’ve been a little pedantic and used â to show that it is an estimate of a derived from the peer group (and similarly for b). The calculations above show that when you plug the formula for Ba,b(p) into Bayes formula you get out another beta distribution! This is the explanation for my earlier statement that beta was chosen to make explicit calculations possible.

My goal is to estimate the auction propensity for a buyer who has purchased k/n auctions. What I have so far is a probability distribution for this propensity, specifically a beta distribution. If I want a single probability, the natural choice is the average of that beta distribution. The average of Beta(a,b) is a/(a+b). So if I want to get a single number for the auction propensity, I take the average of

which is (a+k)/(a+b+n). This is the formula that I have used many times in this posting.

So much for the calculations. I want to end by discussing whether personalization is desirable. Some have argued that it isn’t a good idea to show users only what they’ve seen before. I think these arguments are often attacking a straw man. A good personalization system doesn’t eliminate all variety, it merely tailors it. Suppose our Mr. X has purchased 20 items, all of them at fixed price. But his friend Ms. Y has done the opposite: all her purchases were made by auction. I find it hard to believe that anyone would seriously argue that X and Y should see the same search results. Just as bad as showing X a pile of auctions would be to never show him any auctions. A good personalization system should be nuanced. Methods like those shown in this posting provide principled estimates of user’s preferences. But how these preferences are used requires some finesse.

{ 10 comments… read them below or add one }

John Glassmyer November 5, 2011 at 11:26AM

A good personalization system should be nuanced. A great personalization system should explain to the user in an understandable way all of the factors that went into customizing his search, and give him controls to tune the personalization in case it’s not exactly what he wanted.

Reply

Vincent November 15, 2011 at 1:57PM

So true. Too few people understand the impact of personnalization on UX.

Reply

Dillon Prime November 10, 2011 at 7:03AM

Hi David,

Loved this series of posts.

Is there any level of personalisation already built into the eBay Best Match algorithm? Perhaps if a buyer is logged in their purchase and viewing history is factored in?

Regards,

Dillon

Reply

David Goldberg November 16, 2011 at 8:18PM

Hi Dillon, the current Best Match does not do any personalization, but we hope to add it in next year.

-David

Reply

Dillon Prime November 21, 2011 at 8:12AM

Hi David,

eBay acquiring Hunch could well make personalisation very strong in eBay search!

Dillon

Reply

Devarajan Swami April 17, 2012 at 3:54PM

Hi David,
How do you estimate a and b to minimize the sum of square errors problem you defined?
Since there is no closed form solution, I would be interested in learning about what approach you took.

Reply

David Goldberg April 25, 2012 at 5:03PM

In my experiments, I computed a and b using the gsl_multimin routines from the Gnu Scientific Library.

Reply

Devarajan Swami April 26, 2012 at 11:29PM

Thanks a lot, David!

Reply

Ebayer November 22, 2012 at 11:01PM

“Just because ebay can doesn’t mean ebay should.” I’ll agree that this technology is “really cool”, interesting and challenging; HOWEVER, when I search, I search specifically so the results will return those items I want to see. I control for misspellings, exclude things, and the like. This means that I want to see ALL results that meet MY the parameters in MY search string that I have intentially and purposefully constructed, NOT only those items that some software determines I’d prefer to see based on my past searches or anything other than my literal search. And, sometimes I WANT to see things that are vastly DIFFERENT than what I’ve looked at before! Many ebay users need the results of literal or wildcarded searches because they source their business supplies with ebay purchases that can only be found through literal or wildcarded searches or because their customers source their business supplies with ebay merchandise in the same way. Searches that return too many results are overkill while searches that return too few results are ineffective — both will only serve to drive away users. While changing the fundamental way the searches work in favor of newer technology may seem like a “good” thing, it changes the entire way the site is, and can be, used and has the potential to ruin many users’ businesses that are based on utilization of the existing paradigm.

Reply

Bill Gillooly November 22, 2012 at 11:10PM

I like your example of the two searches. However, what you left out is CONTROL. Mr. X should have the ability to shut off all the auction results, IF HE WANTS TO. Ms Y should have the same control.

Having the search engine, much like Big Brother, making the decision for your is insulting.

Maybe you should query the searcher, “Would you like us to help you with your search, or are you a boolean search animal who needs no help at all, but needs many more than 100 characters to do a truly nuanced search?”

Reply

Leave a Comment

{ 1 trackback }

Previous post:

Next post:

Copyright © 2011 eBay Inc. All Rights Reserved - User Agreement - Privacy Policy - Comment Policy