Reinventing Mail Search and Solving the Catch 22 Dilemma Between Precision and Recall
By Liane Lewin-Eytan and Yoelle Maarek
The Yahoo Mail Mining team in Haifa is publishing two research papers in the proceedings of the 26th International World Wide Web Conference in Perth, Australia this week. These publications, discussed in this blog post, will be presented in a track dedicated to the growing field of email and personal search. We would like to encourage the growth and adoption of research in this field by sharing some of our insights and spurring new ideas.
How many times have you tried to search for an email and not been able to find it? You might think that getting the right email search result is as easy as getting a good search result on the Web, where you often find what you’re looking for on the first try. Unfortunately, experience tells us otherwise. The reason? Mail search is, perhaps surprisingly, an entirely different animal. At Yahoo Research, we’ve been working hard at changing this situation.
When searching your mailbox, you are typically looking for a message that you have received and most probably read. You try to remember the name of the person who sent it to you or some distinctive words in the message. In other words, you try to re-find a given message, while in Web search, by contrast, you try to discover new information. In information retrieval, the computer science discipline behind search, this difference is reflected in two measures: recall (optimally “all the truth” – or in practice, the fraction of true instances that are retrieved), and precision (optimally “nothing but the truth” – or in practice, the fraction of retrieved instances that are true). One known mathematical evidence of these metrics is that increasing one automatically decreases the other. Web search targets precision as it draws from a large pool of potentially relevant results, and the searchers do not know and do not care if some relevant results are omitted as long as they get a sufficient answer. By contrast, mail search targets recall, as users know with certainty when the search results miss the messages they want.
Since users want to make sure they do not miss anything when performing a mail search, they expect their results to be sorted by time so as to scan all results in a systematic manner and maintain an illusion of perfect recall. Unfortunately, by doing so, they impose hard challenges on the search mechanism, which is forced to impose strict relevance constraints on the results returned to the user. This is necessary because otherwise, a remotely relevant, yet very recent message could be pushed to the top of the list. In other words, the time-sort view of results users expect imposes high precision constraints. This then negatively impacts recall, which is what users really care about. Catch 22!
By analyzing search behavior, we have discovered that mail users don’t use search as precisely as intended. We have seen that in 40% of the cases where a user performs a search, they don’t really search. Instead, they actually browse by issuing a “contact query” (i.e. a query that simply consists of a contact name) and then scanning the results. Even non-contact queries remain very vague, with an average length of 1.5 search terms. This again highlights the filtering/browsing behavior of Mail users. The two charts below represent search usage stats based on Yahoo Web Mail traffic.
Figure 1: Mail search stats
Given that email is critical to so many people, we feel it is important to make sure all of our 225M monthly active Yahoo Mail users are getting the best experience possible. With our users in mind, the Yahoo Mail Mining Research team has adopted two different approaches to achieve improved precision and recall, making email search more effective. The first focuses on search results and second on search queries.
Focusing on the results
We have developed a first of its kind ranking algorithm [1] that ranks results by relevance rather than by time sent or received. That way, users are able to efficiently find the messages they are searching for, even if they are not very recent. This relevance ranking algorithm is based on a varied set of features, taking into account every signal that could imply the relevance of a message to a query. Included in the features are those based on the query-message similarity, the message recency, and the message itself (its links, attachments, etc.). Additionally, our algorithm takes into account actions performed on a message. For example, if you “star” a message, it will increase its relevance. However, if you haven’t opened it at all, its relevance will be lessened.
The table below represents the increase obtained in mean reciprocal rank (a.k.a., MRR, one of the most popular metrics in search, based on the average rank of the clicked message), comparing relevance ranking to time ranking, as well as the influence of the different set of features.
Figure 2: Performance of relevance ranking vs. time ranking (lift %)
Our ranking algorithm can display search results in order of relevance, as opposed to reverse chronological order. Consequently, it greatly relaxes strict match constraints, thereby increasing recall by having the most-relevant results at the top and less relevant results – typically missed altogether in the sort-by-time paradigm – still included down the list.
However, we understand that most users may not immediately be open to this revolutionary shift, and will still expect results ranked by time to reinforce their perception of perfect recall. With this in mind, we recently released an intermediate step for presenting search results in which we promote a small number of the most-relevant results on top of the standard time-sorted results. We refer to the top results as heroes, and the research and algorithm supporting our method are detailed in our paper [2] at the 26th International World Wide Web Conference (WWW ‘17) in Perth, Australia. Heroes target precision while the traditional ranked-by-time results target recall; having these two types of results coexist allows us to solve our catch 22 dilemma.
Figure 3: Heroes (appearing as ‘Top results’ in Yahoo desktop mail)
The chart below is based on an online evaluation of the implementation of the heroes feature. Our evaluation demonstrates a lift of 12% in MRR in Yahoo Web mail.
Figure 4: Performance of heroes model vs. traditional time ranking
Focusing on the queries
If we want the quality of search results to improve, we first need users to issue more specific queries and stop entering one-word queries followed by browsing. With such underspecified queries, even the best relevance algorithm we can invent will bring only limited benefits. So we need to assist users in formulating queries and bring them the results they seek faster. The existing query-assistance mechanism in Yahoo Mail today does a beautiful job with contact suggestions (through our Xobni technology) and also leverages past queries from a user’s search history. However, this technology is not sufficient to increase the length of queries and make them more precise.
To improve this situation, we have developed a novel query auto-completion module that takes as input a few characters or words entered by users (a prefix) and offers a list of suggested queries that are generated from three sources: their query log (search history), the content of their mailbox, and the general query log of all users. Moreover, when generating queries based on the general query log, we take into account various demographic attributes of the user such as gender, age, and location, based on the intuition that queries from “users like me” have more of a chance to be relevant to my personal mailbox. For example, the query prefix “sch” typed by a 30-year-old professional from New York might refer to “schedule,” while the same prefix typed by a student from San Francisco might refer to “scholarship.” Or, when typing “Be,” the professional intended “Best Buy,” while the student had the intention of typing “Berkeley.” The algorithm we designed to surface suggestions allows a user to search in a perhaps more precise of a manner than they would have otherwise, thereby helping to exploit the full capacities of the mail search system. Our research paper on query auto-completion [3], including a thorough analysis of the demographics of mail search, will also be published at WWW ‘17.
The combination of all these signals improves the quality of the suggestions by up to 150% when considering the average rank of the clicked suggestion. When splitting the queries according to types (personal contacts, names of companies, general content), the contribution of the general query log is the highest for queries relating to companies/organizations. Examples of this include Amazon or United, where a user typically searches for their last Amazon purchase or upcoming United Airlines flight. The mail traffic originating from a company is usually formatted very similarly for all users; my Amazon purchase notification will look very similar to yours, and the same goes for our flight itineraries if we both booked with United. Thus, it follows that we probably also search for those items in a similar manner.
Figure 5: Word clouds of discriminative queries. Top: men (left) vs. women (right). Bottom: young (left) vs. senior citizens (right).
Both our results-focused and query-focused approaches improve search results and serve to encourage users to search better and more often. These improvements are critical for users to trust that they can retrieve the messages they are looking for since they won’t get lost under a pile of less-relevant search results. This is important, because using the search function is the most efficient way to retrieve data; active users have a large amount of important information in their mailbox they want to regularly retrieve, and most of them do not use folders or other means of organizing their messages. In fact, we know that only 30% of our users create folders, and of those people, only 10% actually use them. In other words, for most users, search is the only way to re-find a message.
As we move forward to improve this effort, we continue to look at all aspects of mail – both on the algorithmic side, by analyzing not only messages, but also attachments, links, photos, invites, and so on; and on the user experience side – to better understand our users’ behaviors and make sure we answer their true, rather than perceived, needs.
Acknowledgements:
This multiple-year work has been published at several top conferences in the last few years and we are grateful to all our co-authors who not only invested so much efforts in this research but published about it: David Carmel, Guy Halawi, Alex Libov, and Ariel Raviv.
A huge thanks to the entire Yahoo Mail engineering and product team. The list of our friends and colleagues there is too long to be fully listed here but nothing would not have happened without their extraordinary support and partnership.
References:
[1] David Carmel, Guy Halawi, Liane Lewin-Eytan, Yoelle Maarek and Ariel Raviv. Rank by time of by relevance? Revisiting Email Search. CIKM'2015, Melbourne Australia, Oct 2015.
[2] David Carmel, Liane Lewin-Eytan, Alexander Libov, Yoelle Maarek and Ariel Raviv. Promoting Relevant Results in Time-Ranked Mail Search. WWW’2017
[3] David Carmel, Liane Lewin-Eytan, Alexander Libov, Yoelle Maarek and Ariel Raviv. The Demographics of Mail Search and their Application to Query Suggestion. WWW’2017
