Search Quality at Yandex

Yandex::The search engine used most in Russia. Here are some of its statistics and information ::

 

Russian Search Market

- Yandex has 60+% market share

- It's all about small attention to details about the search

A Yandex overview

- started in 1997

- no 7 search engine in the world by # of queries

- 150 million queries per day

Variety of Markets

- 15 countries with cyrillic alphabet

- 77 regions in Russia

-> different culture, standard of living, average income, for example: Moscow, Magadan

-> large semi-autonomous ethnic groups (tatar, chech, bashkir)

-> neighbouring bilingual markets

Geo-specific queries

- Relevant result sets very significantly across regions and countries

pFound

- a probablistic measure of user satisfaction

- optimization goal at Yandex sinces 2007

- Similar to ERR, Chapelle 2009 --> hopefully someone can fill in the exact formula

- pFound, pBreak, pRel

Geo-specific Ranking

query -> query + user's region

- may need to build a specific formula for countries/region because of the variance and missing/lacking features in some of them.

Alternatives in Regionalization

- separate local indices or unified indx with geo-coded pages

- one query or region specific query

- query based local intent detection vs. results based local intent detection

- single ranking function vs. co-ranking and re-ranking of local results

- train one formula or train many formulas on local pools

Why use MLR?

Machine learning as a conveyor

- Some query classes require specific ranking

- many features

MatrixNet

A learning method

- boosted decision tree, "oblivious" trees.

- optimize for pFound

- solve regression tasks, train classifiers

Complexity of ranking formulas

20 bytes - 2006

14 kb - 2008

220 kb - 2009

120 MB - 2010

A sequence of More and More complex rankers

- pruning with the static rank (static features)

- use of simply dynamic features (such as bm25)

- complex formula that uses all the features available

- potentially up to million of matrices/trees for the very top documents

- see camazoglu, 2010 early exit optimization

Geo-dependent queries: pFound

- a big jump in 2009 in Quality

- 3x more local results than competitors in Russia, than #2 player

Lessons

- MLR is the only to regional search: it provides us the possiblity of tuning many geo-specific models at the same time.

Challenges

Complexity of the models is increasingly rapidly

-> don't fit into memory!

MLR is in its current setting does not fit well to time-specific queries

-> features of the fresh content are very sparse and temporal

Opacity of results of the MLR

- The backside of ML

Number of featuers grows faster than the number of judgments

-> hard to train ranking

Learning from clicks and user behavior is hard

Tens of GB of data per day!

Yandex and IR

- Participation and Support

- Yandex MLR at IR context

Microsoft Releases Learning to Rank Datasets

Microsoft Research announced that it is releasing a new MS LTR dataset
         After the Recent Learn to Rank Contest held by Yahoo! , Microsoft has presented a similar Dataset :: I am presenting both the dataset's statistics ::

Yahoo! ::. The first dataset had:
29,921 queries
744,692 URLs
519 features

Microsoft :: Released two large scale datasets for research on learning to rank: MSLR-WEB30k with   more than 30,000 queries and a random sampling of it MSLR-WEB10K with 10,000 queries.136 features have been extracted for each query-url pair.The dataset is a retired dataset. What makes this quite interesting is that the features have been released.

You can see the feature list.

See also the Y! LTR datasets.

Lessons and Challenges from Product Search

Lessons and Challenges from Product Search

Daniel Rose, A9

Different Domains, Different Solutions

- Traditional IR,

- Enterprise search

- Web search

- Product Search

How are the issues different? Let's go back to user goals...

The Goals of Web Search

- Understsanding user goals in web search paper

Why do people search on Amazon?

- When they want to buy something?

Even ignoring the non-buying issues..

The Goals of the product Search

- Depends on where you are in the buying funnel.

-- Top: awareness, then Desire, then Interest, finally Action

St. Elmo Lewis, 1898

- Provide the right tools at the right stage in the process.

[roller coaster]

- toys and games

- sort by average customer review

- sort by price (is actually hard: new vs. used, amazon vs. third-party, etc...)

Different Tools for Different Stages

- Product search shows more fluid movement between searching and browsing behavior (relying on faceted metadata)

- Because of the nature of the search task?

- Because of the interfaces?

What Amazon Queries Look Like

- [which old testament book best represent the chronological structure]

- [shipping rates for amazon]

- [long black underbust corset] - still looking

- vs ISBN number -> about to buy it

Context is King

- Some facets for Dresses vs. Digital Cameras

- The problem of facet selection

- Not a one size fits all UI solution for different facet types

- We can interpret your query in a smarter way: [timberland] boots inside shoes is a brand

- Timberland in music -> Timbaland the band

Amazon is a MarketPlace...

- So search must be realtime

-- new products

-- new merchants

-- prices being changed all the time

Structured Data: "It's a gift... and a curse"

- Unlike the web search, we know the semantics of different bits of text

- We know what fields are important for customers (e.g. brand)

- A large degree of quality control (less adversarial problems)

- We don't have to do sentiment analysis to know if a review is positive/negative

A Curse

- Search engine needs to have both DBMS-like "right answer" behavior and IR-like "best answer" behavior

- Tradiontional IR mechanisms don't always work well for structured data

-- e.g. naive tf x idf

What happens when one of the fields is order of magnitudes bigger than others?

-- Search inside the book vs. brand name

- What happens when you don't have all the fields all the time? (missing data)

-- ratings, reviews correlate with user satisfaction, but it may not be there

Using Behavioral Data

- Powerful source of information for any search engine

- When is using behavioural data an invasion of privacy (or just plain creep), and when is it better for users?

- Customers of a business seem more comfortable with that business learning from past behavior.

Interpreting Behavioral Signals

Example: Are search result clicks good and bad?

- How many clicks are best?

-- 1: the customer found what their are looking for right away

-- many: comparison shopping and are looking around at multiple items

-- zero: the search result contained all the information necessary

Also, some items are inherently "click attractive", e.g. a book with a sexy cover

Why is web search so hard... to evaluation? 2004

Evaluating Product Search Relevance

Common argument

-- Customers to to a shopping site to buy stuff

-- if a search engine change leads to customers buying mor stuff, they must have had their search need met more effectively.

-- Therefore, relevance can be measured by how much customers buy.

What's wrong with this argument?

-- besides ignoring the rest of the buying funnel, and that someone is ready to buy.

The A/B Test Mystery

- Compare ranking algorithms A and B

- Assign half of users A and half to B

- And the end the avg. revenue is higher in A than B.

-> algorithm A could be better than B, or Algorithm A could be recommending higher priced items than B

-> Algorithm A could be recommending completely unrelated, but very popular items.

Lessons from IR

One idea: Generalizing the buying funnel

- The information seeking funnel

- Wandering: no information seeking goal in mind

- Exploring: have a general goal, but not a plan on achieving

-Seeking: have started to identify info needs that must be satisfied, but needs are open-ended

-Asking: have a very specific information need corresping to a closed class question

Published in: The information seeking funnel, 2008.

Summary

- Start thinking about how to meet user needs before user knows she has a need

- Offer different interaction mechanisms for different parts of the information seeking process

- Let type of content influence the way search works

- Design for realtime

- Interpret behavioral data carefully

- Exploit Structure when have it

- Exploit context when you have it