Applying PECOS to product retrieval and text autocompletion

Two KDD papers demonstrate the power and flexibility of Amazon’s framework for “extreme multilabel ranking”.

In April, our research team at Amazon open-sourced our PECOS framework for extreme multilabel ranking (XMR), which is the general problem of classifying an input when you have an enormous space of candidate classes. PECOS presents a way to solve XMR problems that is both accurate and efficient enough for real-time use.

At this year’s Knowledge Discovery and Data Mining Conference (KDD), members of our team presented two papers that demonstrate both the power and flexibility of the PECOS framework.

Retrieved products.png
A comparison of the top ten products returned by the PECOS-based product retrieval system and two predecessors for the query "rose of jericho plant". Products outlined in green were purchased by at least one customer performing that search; products outlined in red were not purchased.

One applies PECOS to the problem of product retrieval, a use case very familiar to customers at the Amazon Store. The other is a less obvious application: session-aware query autocompletion, in which an autocompletion model — which predicts what a customer is going to type — bases its predictions on the customer’s last few text inputs, as well as on statistics for customers at large.

In both cases, we tailor PECOS’s default models to the tasks at hand and, in comparisons with several strong benchmarks, show that PECOS offers the best combination of accuracy and speed.

The PECOS model

The classic case of XMR would be the classification of a document according to a handful of topics, where there are hundreds of thousands of topics to choose from.

We generalize the idea, however, to any problem that, for a given input, finds a few matches from among a large set of candidates. In product retrieval, for instance, the names of products would be “labels” we apply to a query: “Echo Dot”, “Echo Studio”, and other such names would be labels applied to the query “Smart speaker”.

PECOS adopts a three-step solution to the XMR problem. First is the indexing step, in which PECOS groups labels according to topic. Next is the matching step, which matches an input to a topic (which significantly shrinks the space of candidates). Last comes the ranking step, which reranks the labels in the matched topic, based on features of the input.

PECOS-framework.png
The three-stage PECOS model.
Credit: Stacy Reilly

PECOS comes with default models for each of these steps, which we described in a blog post about the April code release. But users can modify those models as necessary, or create their own and integrate them into the PECOS framework.

Product retrieval

For the product retrieval problem, we adapt one of the matching models that comes standard with PECOS: XR-Linear. Details are in the earlier blog post (and in our KDD paper), but XR-Linear reduces computation time by using B-ary trees — a generalization of binary trees to trees whose nodes have B descendants each. The top node of the tree represents the full label set; the next layer down represents B partitions of the full set; the next layer represents B partitions of each partition in the previous layer, and so on.

Connections between nodes of the trees have associated weights, which are multiplied by features of the input query to produce a probability score. Matching is the process of tracing the most-probable routes through the tree and retrieving the topics at the most-probable leaf nodes. To make this process efficient, we use beam search: i.e., at each layer, we limit the number of nodes whose descendants we consider, a limit known as the beam width.

Beam search.gif
An example of linear ranking with a beam width of two. At each level of the tree, two nodes (green) are selected for further exploration. Each of their descendant nodes is evaluated (orange), and two of those are selected for further exploration.
Credit: Giana Bucchino

In our KDD paper on product retrieval, we vary this general model through weight pruning; i.e., we delete edges whose weights fall below some threshold, reducing the number of options the matching algorithm has to consider as it explores the tree. In the paper, we report experiments with several different weight thresholds and beam widths.

We also experimented with several different sets of input features. One was n-grams of query words. For instance, the query “Echo with screen” would produce the 1-grams “Echo”, “with”, “screen”, the 2-grams “Echo with” and “with screen”, and the 3-gram “Echo with screen”. This sensitizes the matching model to phrases that may carry more information than their constituent words.

Similarly, we used n-grams of input characters. If we use the token “#” to denote the end of a word, the same query would produce the character trigrams “Ech”, “cho”, “ho#”, “with”, “ith”, and so on. Character n-grams helps the model deal with typos or word variants.

Finally, we also used TF-IDF (term frequency–inverse document frequency) features, which normalize the frequency of a word in a given text by its frequency across all texts (which filters out common words like “the”). We found that our model performed best when we used all three sets of features.

As benchmarks in our experiments, we used the state-of-the-art linear model and the state-of-the-art neural model and found that our linear approach outperformed both, with a recall@10 — that is, the number of correct labels among the top ten — that was more than double the neural model’s and almost quadruple the linear model’s. At the same time, our model took about one-sixth as long to train as the neural model.

We also found that our model took an average of only 1.25 milliseconds to complete each query, which is fast enough for deployment in a real-time system like the Amazon Store.

Session-aware query autocompletion

Session-aware query autocompletion uses the history of a customer’s recent queries — not just general statistics for the customer base — to complete new queries. The added contextual information means that it can often complete queries accurately after the customer has typed only one or two letters.

To frame this task as an XMR problem, we consider the case in which the input is a combination of the customer’s previous query and the beginning — perhaps just a few characters — of a new query. The labels are queries that an information retrieval system has seen before.

In this case, PECOS didn’t work well out of the box, and we deduced that the problem was the indexing scheme used to cluster labels by topic. PECOS’s default indexing model embeds inputs, or converts them into vectors, then clusters labels according to proximity in the vector space.

We suspected that this was ineffective when the inputs to the autocompletion model were partial phrases — fragments of words that a user is typing in. So we experimented with an indexing model that instead used data structures known as tries(a variation on “tree” that borrows part of the word “retrieve”).

A trie is a tree whose nodes represent strings of letters, where each descendant node extends its parent node’s string by one letter. So if the top node of the trie represents the letter “P”, its descendants might represent the strings “PA” and “PE”; their descendants might represent the strings “PAN”, “PAD”, “PEN”, “PET”, and so on. With a trie, all the nodes that descend from a common parent constitute a cluster.

Clustering using tries dramatically improved the performance of our model, but it also slowed it down: the strings encoded by tries can get very long, which means that tracing a path through the trie can get very time consuming.

So we adopted a hybrid clustering technique that combines tries with embeddings. The top few layers of the hybrid tree constitute a trie, but the nodes that descend from the lowest of these layers represent strings whose embeddings are near that of the parent node in the vector space.

Tree, Trie, Trie-tree hybrid.cloned.png
Three different ways of clustering the eight strings "a", "ab", "abc", "abd", "abfgh", "abfgi", "bcde", and "bcdf". At left is a conventional tree; in the center is a trie; and at right is a trie-tree hybrid.

To ensure that the embeddings in the hybrid tree preserve some of the sequential information encoded by tries, we varied the standard TF-IDF approach. First we applied it at the character level, rather than at the word level, so that it measured the relative frequency of particular strings of letters, not just words.

Then we weighted the frequency statistics, overcounting character strings that occurred at the beginning of words, relative to those that occurred later. This forced the embedding to mimic the string extension logic of the tries.

Once we’d adopted this indexing scheme, we found that the PECOS model outperformed both the state-of-the-art linear model and the state-of-the art neural model, when measured by both mean reciprocal rank and the BLEU metric used to evaluate machine translation models.

The use of tries still came with a performance penalty: our model took significantly longer to process inputs than the earlier linear model did. But its execution time was still below the threshold for real-time application and significantly lower than the neural model’s.

Related content

US, WA, Seattle
Job summaryEmployer: Amazon.com Services LLCPosition: Data Scientist IILocation: Seattle WAMultiple Positions Available:1. Perform analytical tasks on vast amounts of structured and unstructured data to extract actionable business insights2. Develop algorithms using advanced mathematical and statistical techniques including machine learning to predict business outcomes and recommend optimal actions to management3. Use advanced algorithms to solve business problems, and transform one-off models into automated systems4. Analyze and validate data to ensure high data quality and reliable insights5. Run analytical experiments in a methodical manner to find opportunities for product and process optimization6. Communicate analytical output and business insights to management using visualization techniques and data storytelling7. Write concise documents communicating results to stakeholders and visualize data to drive decision making#0000
US, VA, Arlington
Job summaryAmazon is looking for a passionate, talented, and inventive Research Scientists with a strong machine learning background to help build industry-leading Speech and Language technology. This includes delivering innovative HR experiences for our employees. To get there, we need exceptionally talented, bright, and driven people. The Employee Services Technology (ES Tech) is growing rapidly and is looking for a talented senior research scientist to create massive scale and powerful new solutions that our customers need to be successful. In this role, you will work to establish world class data science, analytics and reporting for Amazonians as part of building the Personalization Engine for myHR. This key role will work closely with internal partners to assist in developing and managing solutions for ES Tech. We are looking for candidates who want to invent the future for employee engagement.This role will play critical part in forecasting initiatives, responsible for building models and prototypes for ES Tech division, and will require close collaboration with other scientists on the team that are developing state-of-the-art optimization algorithms to scale. This team plays a significant role in various stages of the innovation pipeline from identifying employee needs, developing new algorithms, prototyping/simulation, to implementation by working closely with colleagues in engineering, product management and employee benefits.We are seeking a Senior Research Scientist with expertise in mixed-methods research, preferably in social science and behavioral research. In this role, you will lead and support research efforts within the Recruiting, Talent Management, and Leadership & Development space.You will help set the direction for science and research in the organization. You will be a thought leader on the team, partnering with a diverse set of stakeholders to identify and develop impactful areas for novel research about talent and recruiting outcomes, mechanisms, and programs. You will mentor and provide scientific expertise/peer review to other scientists and analysts on the team.The ideal candidate should have strong problem solving skills, excellent business acumen, as well as an expertise in both qualitative and quantitative methods. This role will need to navigate complex and ambiguous business challenges by asking the right questions, understanding what methodologies to employ, and communicating results to multiple audiences (e.g., technical peers, functional teams, business leaders). Translating business and stakeholder needs into realistic and actionable scientific research will be a regular challenge in this role.Responsibilities include:· Leading scientific direction, providing consult, mentorship, and peer review.· Partnering closely and driving effective collaborations across multi-disciplinary science, analytics, HR, and business teams. Reviewing and scoping research requests, and recommending appropriate scientific methodologies.· Designing, developing, and executing qualitative and quantitative data collection, research, and experimentation. Strong experience with statistical analysis required. Experience with survey development and experimental design (including quasi-experimental) preferred.· Communicating findings and business impact effectively (written and verbally) with both technical and non-technical stakeholders
US, VA, Arlington
Job summaryAmazon is looking for a passionate, talented, and inventive Research Scientists with a strong machine learning background to help build industry-leading Speech and Language technology. This includes delivering innovative HR experiences for our employees. To get there, we need exceptionally talented, bright, and driven people. The Employee Services Technology (ES Tech) is growing rapidly and is looking for a talented senior research scientist to create massive scale and powerful new solutions that our customers need to be successful. In this role, you will work to establish world class data science, analytics and reporting for Amazonians as part of building the Personalization Engine for myHR. This key role will work closely with internal partners to assist in developing and managing solutions for ES Tech. We are looking for candidates who want to invent the future for employee engagement.This role will play critical part in forecasting initiatives, responsible for building models and prototypes for ES Tech division, and will require close collaboration with other scientists on the team that are developing state-of-the-art optimization algorithms to scale. This team plays a significant role in various stages of the innovation pipeline from identifying employee needs, developing new algorithms, prototyping/simulation, to implementation by working closely with colleagues in engineering, product management and employee benefits.We are seeking a Senior Research Scientist with expertise in mixed-methods research, preferably in social science and behavioral research. In this role, you will lead and support research efforts within the Recruiting, Talent Management, and Leadership & Development space.You will help set the direction for science and research in the organization. You will be a thought leader on the team, partnering with a diverse set of stakeholders to identify and develop impactful areas for novel research about talent and recruiting outcomes, mechanisms, and programs. You will mentor and provide scientific expertise/peer review to other scientists and analysts on the team.The ideal candidate should have strong problem solving skills, excellent business acumen, as well as an expertise in both qualitative and quantitative methods. This role will need to navigate complex and ambiguous business challenges by asking the right questions, understanding what methodologies to employ, and communicating results to multiple audiences (e.g., technical peers, functional teams, business leaders). Translating business and stakeholder needs into realistic and actionable scientific research will be a regular challenge in this role.Responsibilities include:· Leading scientific direction, providing consult, mentorship, and peer review.· Partnering closely and driving effective collaborations across multi-disciplinary science, analytics, HR, and business teams. Reviewing and scoping research requests, and recommending appropriate scientific methodologies.· Designing, developing, and executing qualitative and quantitative data collection, research, and experimentation. Strong experience with statistical analysis required. Experience with survey development and experimental design (including quasi-experimental) preferred.· Communicating findings and business impact effectively (written and verbally) with both technical and non-technical stakeholders
US, CA, San Francisco
Job summaryAbout Us:Launched in 2011, Twitch is a global community that comes together each day to create multiplayer entertainment: unique, live, unpredictable experiences created by the interactions of millions. We bring the joy of co-op to everything, from casual gaming to world-class esports to anime marathons, music, and art streams. Twitch also hosts TwitchCon, where we bring everyone together to celebrate, learn, and grow their personal interests and passions. We're always live at Twitch. Stay up to date on all things Twitch on Linkedin, Twitter and on our Blog.About the Role:Amazon Interactive Video Service (IVS) is a managed live video service, within Amazon Web Services (AWS), built on top of Twitch Video. It has one of the world's largest live video networks. IVS powers the many companies that are using live video to uniquely engage and build communities, just as it does for Twitch, where more than a billion hours are streamed live each month.The IVS Video Intelligence team, a central data team for all of IVS, is looking for a principal applied scientist to create a strategic impact for the entire IVS business. As part of the team, you will shape the data and science strategy for the whole of IVS. You will both invent new solutions and bring your knowledge of ML ops best practices to establish cross-company standards. You will oversee our novel end-to-end predictive simulation of our video streaming infrastructure to test product hypotheses, forecast demand and capacity needs, and cover failure scenarios. You will report to the Video Intelligence team lead.If you are experienced in predictive analytics and have a passion for deep technical problems at consumer web scale, come help us grow an enterprise cloud service. You will work in our San Francisco office, but we will also consider other locations including Seattle (WA), Salt Lake City (UT), or US-Virtual.You Will:• Create the organizational science strategy.• Invent new technologies to give live video broadcasters and viewers a better overall experience.• Become a domain expert real-time video streaming tracking and measurement, building trust with your product and infrastructure partners.• Mentor junior team members and promote analytics and experimentation best practices throughout the company.
US, WA, Bellevue
Job summaryAt Amazon, we're working to be the most customer-centric company on earth. To get there, we need exceptionally talented, bright, result oriented, and driven people. Amazon is seeking a Simulation Engineer to assist in designing and optimizing the middle mile concepts and process improvements using discrete event simulations. Successful candidates will be natural self-starters who have the drive to design, model, and simulate new concepts and processes. The Simulation Engineer will be expected to deep dive problems and drive relentlessly towards creative solutions. This individual needs to be comfortable interfacing and driving various functional teams and individuals at all levels of the organization in order to be successful. Perform process modelling and simulation using discrete event simulation software’s, process optimization, statistical data analysis, and Design of Experiments (DOE) etc. to drive decisions on process and designs. Need based remote work option is available.Responsibilities:· Lead system level complex Discrete Event Simulation (DES) projects to build , simulate, and optimize the fulfillment center operational process flow models using FlexSim, Demo 3D, AnyLogic or any other Discrete Event Simulation (DES) software packages· Understand process flows , analyze data, perform Design of Experiments and effectively represent in simulation model to achieve better correlation and process improvements· Manage multiple DES simulation projects and tasks simultaneously and effectively influence, negotiate, and communicate with internal and external business partners, contractors and vendors.· Facilitate process improvement initiatives among site operations, engineering, and corporate systems groups.· Utilize code (python or another object oriented language) for data analysis and modeling algorithms· Analyze historical data to identify trends and support decision making using Statistical Techniques· Lead and coordinate simulation efforts between internal teams and outside vendors to develop optimal solutions for the network, including equipment specification, material flow, process design, and site layout.· Deliver results according to project schedules and quality· Provide written and verbal presentations to share insights and recommendations to audiences of varying levels of technical sophistication.· Make technical trade-offs for long term/short-term needs considering challenges in business area by applying relevant data science disciplines, and interactions among systems.
US, PA, Pittsburgh
Job summaryAmazon is looking for passionate Applied Scientists with expertise in Machine Translation and Information retrieval to help us expand our MT and NLP technology for search.Amazon’s International Search team owns defining and delivering Amazon’s cutting-edge Search and Machine Translation initiatives to customers and cultures across multiple regions. We do this by developing our own customer-facing features, services and platforms based on customer needs, and through partnerships with Amazon technical teams around the world including Central organizations.You will work with the largest online retail search application in the world, both in terms of users, catalogue size, and computing resources, and your work will directly impact millions of our customers. You will collaborate with recognized experts in business, science and engineering.Our mission is to enable a superior experience for all of Amazon’s customers in their native language by developing and deploying state-of-the art technology and applications in Machine Translation (MT), Natural Language Processing (NLP) and Machine Learning (ML). The global scale of Amazon means true big data problems, big data opportunities, and building for global customers. Machine Translation allows Amazon to reach people in their preferred language. We are a team tackling the tough language problems that general-purpose MT cannot solve.As part of our MT research & development team, you will work on developing, deploying, maintaining and supporting our fleet of Machine Translation systems, particularly focused on Search. You will collaborate with recognized experts in science and engineering to develop novel algorithms and modeling techniques to advance the state-of-the-art in MT, search and information retrieval. You will partner closely with our engineering teams, publish scientific papers and apply for patents for your inventions. Your work will directly impact millions of our customers in the form of products and services that make use of our MT and NLP technology. You will gain hands-on experience with Amazon’s heterogeneous language data sources and large-scale computing resources to accelerate advances in MT and NLP.Key job responsibilities* Drive scientific exploration and innovation for MT improvements and evaluation techniques* Train and evaluate neural MT models using Amazon's proprietary MT technology* Analyze the accuracy and performance of MT models for search* Assist in deploying, maintaining, and supporting Amazon's fleet of dedicated MT systems in production* Design and implement software to collect, analyze and prepare large natural language data sets
DE, BY, Munich
Job summaryGlobal Workforce Staffing (WFS), a division of Amazon’s Worldwide Operations People Experience and Technology (PxT, aka Human Resources in other companies), manages Amazon’s Tier 1 talent supply chain. We attract, hire, and onboard the associates who, by fulfilling orders at the frontlines of the company, make Amazon a global leader in delivery and logistics. The Market Intelligence ensures that Amazon can deliver an industry leading customer delivery experience while raising the bar for its largest candidate and employee population--Tier 1 Associates. We ensure that Amazon can take scale globally in a consistent manner, accounting for the specific regional needs and characteristics of European countries.We are seeking a Manager, Data Science, with a heavy focus on quantitative data analysis and evaluation, and a deep focus on understanding European labor markets. You will be responsible for leading a new global expansion team from the ground up, develop research roadmaps, run experiments, and drive business impact through your research at global scale.The ideal candidate should be well versed in quantitative methods, including classical statistics and machine learning approaches. Competitive candidates will be very comfortable with at least one computational language (e.g., Python, R). Candidates should be comfortable selecting and leading their team through deployment of the best fit computational models and machine learning algorithms for analyzing their output.Candidates should have demonstrated experience leading data science and analytics projects related to labor market research and analysis, including research on wage sensitivity and elasticity, addressable workforce sizing, competition, and other factors.A day in the lifeYou will lead a team of Data Scientists and BI Engineers, and partner with Data and Software Engineers in scaling intelligence by country pertaining to market presence (site selection), launch risk, and hiring risk. You will build strong trusting relationships with key business partners to influence and drive success in their operations. You will continually coach and mentor a team to be successful in agile research iterations, working hand-in-hand with subject matter experts as humans-in-the-loop refining and ensuring the adoption of your models and products.
GB, MLN, Edinburgh
Job summaryAre you a MS or PhD student interested in a 2022 Applied Science Internship in the fields of Speech, Robotics, Computer Vision, or Machine Learning/Deep Learning?Do you enjoy diving deep into hard technical problems and coming up with solutions that enable successful products that improve the lives of people in a meaningful way?If this describes you, come join our research teams at Amazon. As an Applied Science Intern, you will have access to large datasets with billions of images and video to build large-scale machine learning systems. Additionally, you will analyze and model terabytes of text, images, and other types of data to solve real-world problems and translate business and functional requirements into quick prototypes or proofs of concept.We are looking for smart scientists capable of using a variety of domain expertise combined with machine learning and statistical techniques to invent, design, evangelize, and implement state-of-the-art solutions for never-before-solved problems.Machine Learning Science:Amazon has multiple positions available for Applied Scientists in Berlin, Munich, Tuebingen, Cambridge, Edinburgh, London, Iasi and Barcelona..A few of the teams that are hiring include:· Core AI· · Amazon Search· · AWS AI· · Advertising Technologies· · Community Shopping· · Prime VideoSpeech and Language Technology:We are hiring in all areas of spoken language understanding: ASR, NLP, NLU, text-to-speech (TTS), and Dialog Management. Amazon has multiple positions available for Speech Scientists in Aachen, Barcelona, Berlin, Cambridge, Edinburgh, Gdansk, Haifa, Tel Aviv and Turin.A few of the teams that are hiring currently include:· Alexa ML· · Alexa Brain· · Alexa Shopping· · Amazon Search· · CS TechnologyComputer Vision:Amazon has multiple positions available for Computer Vision Scientists in locations such as Berlin, Barcelona, Tuebingen, Haifa and Tel Aviv.We are currently hiring for multiple teams including:· Visual Search· Amazon AI (AWS Rekognition)· Amazon Go· Lab126
TW, TPE, Taipei
Job summaryThere is nothing COOLER than thinking and developing a brand-new IoT protocol like Sidewalk.Amazon Sidewalk is looking for a Sr. Data Scientist to help build and maintain analytics platforms in Sidewalk Network Health and Analytics team.About the RoleAs a Sr. Data Scientist, you will work closely with internal teams to improve and solve large scale analytics. You will leverage your analytical skills to provide insights on the end-to-end architecture and drive optimization. You must be willing to own, you will be responsive, flexible and able to succeed within an open collaborative peer environment. You must also be able and willing to multi-task and open to learn new technologies quickly. You are comfortable with proactive outward communication and technical leadership and you never shy away from a challenge.Ideally, you have hands-on experience with python and jupyter notebooks, you have familiarity with AWS infrastructure and running cloud operations.A successful candidate will need excellent communication skills and the ability to interact with software developers and managers that will be contributing and leveraging the analytics platform. If you are interested on building and managing large scale platforms, this position will provide you with a unique opportunity to deploy analytics at scale in a platform for real-time operations.About the team : Amazon SidewalkAmazon Sidewalk is a new long-term effort to greatly extend the working range of low-bandwidth, low-power, smart lights, sensors, and other low-cost devices customers install at the edge of their home network. We believe customers shouldn’t have to settle for connected devices that lose functionality past the front door. With Amazon Sidewalk, customers will be able to place smart devices anywhere on their property and know the devices will work, even in dead spots where Wi-Fi and Bluetooth don’t reach, helping bridge the connectivity gaps around our homes!Key job responsibilities· Broad cross-functional engineering interaction to deliver analytics real-time for Amazon Sidewalk· Strong analytical and quantitative data-analysis; use hard data and metrics to back up assumptions, recommendations, and drive actions· Drive system level integration of telemetry and analytics.
IT, Turin
Job summaryAmazon is looking for a Data Scientist with a passion for languages to join our Alexa AI - Natural Understanding Turin team. We are seeking a candidate with strong analytical skills and Natural Language Processing (NLP) experience to help us develop language components for a variety of Alexa products. Come join the Alexa team, building the speech and language solutions behind Alexa, Amazon Echo and other Amazon products and services! You will help us invent the future. As a NLP Data Scientist of the Alexa AI - NU Team, you will work close with Language Engineers to build and releases NLU models in production and improve them. You will gain hands-on experience with Amazon’s heterogeneous structured data sources; as well as large-scale computing resources to accelerate advances in training deep neural networks for natural language understanding. You will take lead on solving highly visible and impactful business problems in areas of automation, self-service solution and quality improvement to continue delight Alexa customers and help driving Amazon business performance. The ideal candidate is clearly passionate about delivering experiences that delight customers and creating solutions that are robust. Creating reliable, scalable and high performance products requires exceptional technical expertise, and a sound understanding of the fundamentals of Machine Learning, NLP, Linguistic and Problem solving. This role requires working closely with business, engineering and other scientists within the team and across Amazon to raise the bar in operational excellence, improving tools and automating workflows. You will lead high visibility and high impact programs collaborating with various teams across Amazon. You will focus on deliver results with the right quality and in a timely fashion. Your bias for action will be critical to move quickly on projects, with calculated risk taking.