Improving Amazon?

I want to surface a new comment thread on improving online shopping from one of my old posts. I would enjoy hearing other thoughts on it, so please comment if you have anything to add.

Chris Zaharias asked:

Where you think Amazon still has opportunities to improve their game?

I said:

Looking at the bigger picture, I think it is hard to say that Amazon is anywhere close to done. The experience of shopping at Amazon is hardly effortless, full of discovery, or even all that pleasant.

Going to Amazon should be like walking into your favorite store, the nearest shelves piled high with things you like, everything you don't need fading into the background.

When you walk up to an item, everything you need to quickly evaluate it and decide whether to buy it should float to your attention.

Buying should be effortless, a couple clicks at most, with no unpleasant surprises (such as hidden shipping charges, delays, or belated out of stock e-mails).

Amazon has taken some steps toward that vision, but is a long way from there.

What do you think? How do you think online shopping be improved? Are there things Amazon should be doing that they are not?

Read More

Learning forgiving hashes

Googlers Shumeet Baluja and Michele Covell had a paper at IJCAI 2007, "Learning 'Forgiving' Hash Functions: Algorithms and Large Scale Tests" (PDF).

The paper describes finding similar songs using very short audio snippets from the songs, a potential step toward building a music recommendation system. The similarity algorithm used is described as a variant of locality-sensitive hashing.

First, an excerpt from the paper describing LSH:

The general idea is to partition the feature vectors into subvectors and to hash each point into separate hash tables... Neighbors can be [found by] ... each hash casting votes for the entries of its indexed bin, and retaining the candidates that receive some minimum number of votes.

What is interesting (and a bit odd) about this work is that they used neural networks to learn the hash functions for LSH:

Our goal is to create a hash function that also groups "similar" points in the same bin, where similar is defined by the task. We call this a forgiving hash function in that it forgives differences that are small.

We train a neural network to take as input an audio spectrogram and to output a bin location where similar audio spectrograms will be hashed.

A curious detail is that initializing the training data by picking output bins randomly worked poorly, so instead they gradually change the output bins over time, allowing them to drift together.

The primary difficulty in training arises in finding suitable target outputs for each network.

Every snippet of a song is labeled with the same target output. The target output for each song is assigned randomly.

The drawback of this randomized target assignment is that different songs that sound similar may have entirely different output representations (large Hamming distance between their target outputs). If we force the network to learn these artificial distinctions, we may hinder or entirely prevent the network from being able to correctly perform the mapping.

Instead of statically assigning the outputs, the target outputs shift throughout training ... We ... dynamically reassign the target outputs for each song to the [bin] ... that is closest to the network's response, aggregated over that song's snippets.

By letting the network adapt its outputs in this manner, the outputs across training examples can be effectively reordered to avoid forcing artificial distinctions .... Without reordering ... performance was barely above random.

I have not quite been able to make up my mind about whether this is clever or a hack. On the one hand, reinitializing the target outputs to eliminate biases introduced by random initialization seems like a clever idea, perhaps even one that might have broad applicability. On the other hand, it seems like their learning model has a problem in that it does not automatically learn to shift the outputs from their initial settings, and the reordering step seems like a hack to force it to do so.

In the end, I leave this paper confused. Is this a good approach? Or are there ways to solve this problem more directly?

Perhaps part of my confusion is my lack of understanding of what the authors are using for their similarity metric. It never appears to be explicitly stated. Is it that songs should be considered similar if the difference between their snippets is small? If so, is it clear that is what the NNet is learning?

Moreover, as much as I want to like the authors idea, the evaluation only compares their approach to LSH, not to other classifiers. If the goal is to minimize the differences between snippets in the same bin while also minimizing the number of bins used for snippets of any given song, are there better tools to use for that task?

Read More

Universal action and the future of the desktop

In a Google engEdu tech talk, "Quicksilver: Universal Access and Action", Nicholas Jitkoff provides some thought-provoking ideas on the future of the desktop.

Starting at 03:52 in the talk, Nicholas begins describing how he thinks the desktop should work, listing four categories of user goals: Search, Summon, Browse, and Act.

Search is a fast, comprehensive, and easy-to-use desktop search tool, such as Google Desktop. This may not sound new but, amazingly, this has only recently begun to be a common part of the desktop experience.

Summon is using desktop search for navigation. You know something exists, you just want to get back to it immediately.

Browse may sound close to what the desktop does now, but Nicholas seems to mean browse not as navigating a folder hierarchy but as finding objects related to or near other objects. For example, you might not remember the name of the specific song you want, but you might be able to remember the artist who wrote it; getting to the first allows you to recall the second.

Act is when you want to immediately do a task (e.g. play a music track) without any intervening steps such as opening an application.

Note the deemphasis of the traditional file hierarchy, the focus on objects, and the shift away from applications and toward actions on objects.

The desktop should seek to satisfy our goals immediately. We should not have to start to adjust the lighting in a photo album by navigating an hierarchical menu, locating an application that allows you to edit photos, waiting for the application to load, and then opening the files using the open menu in that application. We should just ask to adjust the lightening in a photo album.

The next few minutes of the talk further break down some of the constraints on the desktop metaphor. Nicholas advocates fast, universal access that ignores the boundaries of the machine, reaching out to the network to whatever data and code is needed to act. The focus should be on the task -- getting work done -- using whatever resources are necessary, requiring as little effort as possible.

The vision is fantastic and inspiring. However, while Quicksilver is an interesting example, from what I saw, it appears to be only a baby step toward these lofty goals. The learning and automation appears primitive, and the effort required to customize severe, which may make Quicksilver closer to a geek tool than a realization of the broader ambition.

Even so, Nicholas is offering intriguing thoughts on where the desktop should go. It is well worth listening.

Read More

More interviews on search in 2010

Gord Hotchkiss at Search Engine Land continues his interviews on the future of search with his post, "Search In The Year 2010: Part Two".

Again, I would recommend reading the whole thing, but I here will focus on the parts on personalization.

In particular, there are a few tidbits on personalized advertising in this round of interviews. Some excerpts:

Chris Sherman: ... As they get to know you and your preferences, you know... "I never click on that video ad," they’ll gradually stop showing you [those] ads ... and maybe increase the ads ... that you do click on.

Larry Cornett: ... The more they understand about what a specific user is looking for in their context, the more intelligent they can be about what they're actually offering ... By being more targeted it will add more value for the users and hopefully, be a better experience for them as well .... Do [users] really want to spend time in the context where they're seeing a lot of stuff that’s not targeted and not appropriate and might even be annoying or would they rather ... [see ads that] could be beneficial for them.

[Gord Hotchkiss:] Personalization of advertising will happen incrementally and the ability to target accurately will improve over time. For many users, it will be a mixed environment, with some very well targeted, relevant ads in some locations that don’t even look like advertising and the more typical forms of untargeted advertising we're more familiar with.

The impression I got from this is that personalized advertising is now seen as inevitable. Privacy concerns may make it appear incrementally, but most seem to agree that it will happen.

On a different topic, usability guru Jakob Nielsen used his time to promote NLP over personalization and pick on Amazon.com's recommendations yet again. Gord asked me to respond.

On the one hand, I agree with Jakob about the long-term promise of natural language techniques (though I think he may be underestimating the challenges and overestimating the likelihood of rapid progress there) and his criticism of inaccuracies in personalization and recommendations (and they are inaccurate, no doubt).

On the other hand, I think Jakob is using an absolute measure of the effectiveness of personalization where a relative measure is more appropriate. Specifically, the metric should not be how often does personalized content accurately reflect your interests; it should be how much better does personalized content predict your interests than whatever unpersonalized content you otherwise would have to put in the space.

That is a much lower bar. Bestsellers and other unpersonalized content tend to be very poor predictors of individual interest. By knowing even a little bit about you, it is easy to do better.

Is personalization ever going to be perfect? No, but it does not have to be. It just has to be more useful than the alternative. Personalized content only has to be marginally more interesting than unpersonalized content to be helpful.

See also Gord's first post in this series, "Search In The Year 2010", which has some more on personalized search, and my comments on that post.

For more on personalized advertising, please see also my posts "What to advertise when there is no commercial intent?" and "Is personalized advertising evil?"

Read More

The power of branding in web search

Some research out of Penn State, "The Effect of Brand Awareness on the Evaluation of Search Engine Results" (PDF) puts some hard numbers on the hurdles for Google's web search competitors.

The study showed participants Google search results on all queries, but switched around branding elements at the top and bottom of the page to label the results as from Yahoo, Microsoft Live Search, a startup called AI²RS, and Google.

From the paper:

Based on average relevance ratings, there was a 25% difference between the most highly rated search engine and the lowest, even though search engine results were identical in both content and presentation.

The 25% difference was between the results branded with the AI²RS startup and the results branded as Yahoo.

Curiously, Yahoo was rated substantially higher than Google, despite the fact that these were Google's search results. Yahoo has failed to gain web search market share, but, if you believe this study, brand weakness is not the reason why.

It is true that this study is small, just 32 participants and across 4 different queries. It would be nice to see a broader study that confirms these results.

Even so, it probably is safe to say that the strength of the Google and Yahoo brands (and Microsoft's ownership of the defaults in Internet Explorer) make it very difficult for any web search startup. As Rich Skrenta once said, "A conventional attack against Google's search product will fail ... A copy of their product with your brand has no pull."

See also a lighter Penn State Live article on the study, "Branding matters -- even when searching".

[Found via Barry Schwartz]

Read More

Missing an opportunity in shopping metasearch

There is an interesting tidbit at the beginning of a Search Engine Land post, "Kicking The Tires On Shopping Search, Part Two: The Independents".

Compiling data from Hitwise, they shows that Google, Microsoft, and Yahoo now have a meager 15% market share in shopping search combined, down from nearly 50% combined three years ago.

Considering that a substantial percentage of web search queries are shopping-related (see "A taxonomy of web search" (PDF)) and the ease of extracting advertising revenue and revenue sharing where there is such strong purchase intent, I would think that Google, Yahoo, and Microsoft would be pursuing shopping metasearch more aggressively.

See also part one of the Search Engine Land series, "Analyzing the Major Shopping Search Services", which focuses mostly on design and usability of the shopping sites offered by Google, Yahoo, and Microsoft.

See also my earlier posts, "R.I.P. Froogle?" and "What should Google do next?".

Read More

HITS, PageRank, and keeping it simple

A SIGIR 2007 paper out of Microsoft Research, "HITS on the Web: How does it Compare?" by Marc Najork, Hugo Zaragoza, and Michael Taylor is a large-scale study of several ranking algorithms using a substantial web crawl and data from the MSN query logs.

The authors appear to have expected the HITS algorithm to outperform the others in their tests, but found instead that a combination of BM25F and simple in-degree link analysis outperformed everything else. From the paper:

We were quite surprised to find that HITS, a query-dependent feature, is about as effective as web page in-degree, the most simpleminded query-independent link-based feature.

As expected, BM25F outperforms all link-based features by a large margin. The link-based features are divided into two groups, with a noticeable performance drop between the groups. The better-performing group consists of the features that are based on the number and/or quality of incoming links (in-degree, PageRank, and HITS authority scores); and the worse-performing group consists of the features that are based on the number and/or quality of outgoing links (outdegree and HITS hub scores).

The combination of BM25F with ... id in-degree consistently outperforms the combination of BM25F with PageRank or HITS authority scores, and can be computed much easier and faster.

PageRank performed poorly in their tests. However, their explanation of why struck me as unconvincing. From the paper:

The fact that in-degree features outperform PageRank under all measures is quite surprising. A possible explanation is that link-spammers have been targeting the published PageRank algorithm for many years, and that this has led to anomalies in the web graph that affect PageRank.

This begs the question of whether they picked the right PageRank algorithm. In particular, there are variants of PageRank that they could have used that appear less sensitive to spam and may have performed much better. Unfortunately, without results for those variants, it is hard to know whether the criticisms in this paper of naive PageRank are applicable to the algorithms evolved from PageRank used by search engines today.

Even so, the results of the study are interesting, both for the overview of several relevance ranking algorithms and the conclusions about their effectiveness. Particularly intriguing is the evidence that computationally expensive algorithms such as the query-dependent HITS algorithm seem to hold no advantage over much simpler techniques.

Update: Marc Najork, one of the authors of the paper, expands on the PageRank algorithm issue and the performance of HITS in the comments for this post.

Read More