Teaching computers to answer complex questions

Computerized question-answering systems usually take one of two approaches. Either they do a text search and try to infer the semantic relationships between entities named in the text, or they explore a hand-curated knowledge graph, a data structure that directly encodes relationships among entities.

With complex questions, however — such as “Which Nolan films won an Oscar but missed a Golden Globe?” — both of these approaches run into difficulties. Text search would require a single document to contain all of the information required to satisfy the question, which is highly unlikely. But even if the knowledge graph was up to date, it would have to explicitly represent all the connections established by the question, which is also unlikely.

In a paper we presented last week at the ACM’s SIGIR Conference on Research and Development in Information Retrieval, my colleagues and I describe a new approach to answering complex questions that, in tests, demonstrated clear improvements over several competing approaches.

In a way, our technique combines the two standard approaches. On the basis of the input question, we first do a text search, retrieving the 10 or so documents that the search algorithm ranks highest. Then, on the fly, we construct a knowledge graph that integrates data distributed across the documents.

Because that knowledge graph is produced algorithmically — not carefully curated, the way most knowledge graphs are — it includes a lot of noise, or spurious inferred relationships. We choose to err on the side of completeness, ensuring that our graph represents most of the relationships described in a text, even at the cost of a lot of noise. Then we rely on clever algorithms to filter out the noise when constructing a response to a question.

In evaluating our approach, we used two different types of baselines: an alternative system and alternative algorithms. The alternative system was a state-of-the-art neural network that learns to answer questions from a large body of training data. The alternative algorithms were state-of-the-art graph search algorithms, which we applied to our ad hoc knowledge graph.

In 36 tests using two different data sets and three different performance metrics, our system outperformed all three baselines on 34, finishing a close second on the other two. The average improvement over the best-performing baseline was 25%, with a high of 80%.

Our system begins with an ordinary web search, using the full text of the question as a search string. In our experiments, we used several different search engines, to ensure that search engine quality doesn’t bias the results. We retrieve the ten top-ranked documents and use standard algorithms to identify named entities and parts of speech within each.

Then we use an information extraction algorithm of our own devising to extract subject-predicate-object triples from the text. Predicates are established either by verbs — as in the triple <Nolan, directed, Inception> — or prepositions — as in <The Social Network, winner of, Best Screenplay>. We also assign each triple a confidence score, based on how close to each other the words are in the text.

Then, from all the triples extracted from all the documents, we assemble a graph.

Baseline_graph.jpg._CB439534692_.jpg
The baseline graph

Using syntactic clues — such as “A and other X’s” or “X’s such as A” — and data from existing knowledge graphs, we then add nodes to our graph that indicate the types of the named entities. We also use existing lexicons and embeddings, which capture information about words’ meanings, to decide which names in the graph refer to the same entities. Like the relationships encoded in the data triples, the name alignments are assigned confidence scores.

Types_and_name_alignment.jpg._CB439548959_.jpg
Graph with types added (left) and entity names aligned (right).

The graph itself is now complete. Our search algorithm’s first step is to identify cornerstones in the graph. These are words that very closely match individual words in the search string.

Graph with cornerstones in yellow

Our assumption is that the answers to questions lie on paths connecting cornerstones. Each path through the graph is evaluated according to two criteria: its length (shorter paths are better) and its weights (the confidence scores from the data triples and the name alignments). We then eliminate all but the shortest, highest-confidence paths.

Highest-scoring_paths.jpg._CB439534991_.jpg
Highest-scoring paths between cornerstones

Next, we remove all the cornerstones from the graph, on the assumption that they can’t be answers to the question, along with all the nodes that are not named entities.

Cornerstones_and_non-entities_removed.jpg._CB439534989_.jpg
High-scoring paths with cornerstones and non-entities removed.

From the initial query, an algorithm that we reported previously predicts the lexical type of the answer. If the question begins “Which films won … ”, for instance, the algorithm will predict that the answer to the question should be of the type “film”. We then excise all entities that do not match the predicted type. In this case, that leaves us with two entities: Inception and The Social Network.

Finally, our algorithm ranks the remaining entities according to several criteria, such as the weights of the paths that connect them to cornerstones, their distance from cornerstones, the number of paths through the network that lead through them, and so on. In this case, that leaves us with one entity, Inception, which the algorithm returns as the answer to the search question.

Although our system significantly outperforms state-of-the-art baselines, there is still room for improvement. One avenue of future research that we consider promising is the integration of the ad hoc knowledge graphs with existing, curated knowledge graphs and the adaptation of the search algorithm accordingly.

Acknowledgments: Xiaolu Lu, Soumajit Pramanik, Rishiraj Saha Roy, Yafang Wang, Gerhard Weikum

Related content

US, CA, Santa Clara
Job summaryAmazon is looking for a passionate, talented, and inventive Applied Scientist with a strong machine learning background to help build industry-leading language technology.Our mission is to provide a delightful experience to Amazon’s customers by pushing the envelope in Natural Language Processing (NLP), Natural Language Understanding (NLU), Dialog management, conversational AI and Machine Learning (ML).As part of our AI team in Amazon AWS, you will work alongside internationally recognized experts to develop novel algorithms and modeling techniques to advance the state-of-the-art in human language technology. Your work will directly impact millions of our customers in the form of products and services, as well as contributing to the wider research community. You will gain hands on experience with Amazon’s heterogeneous text and structured data sources, and large-scale computing resources to accelerate advances in language understanding.We are hiring primarily in Conversational AI / Dialog System Development areas: NLP, NLU, Dialog Management, NLG.This role can be based in NYC, Seattle or Palo Alto.Inclusive Team CultureHere at AWS, we embrace our differences. We are committed to furthering our culture of inclusion. We have ten employee-led affinity groups, reaching 40,000 employees in over 190 chapters globally. We have innovative benefit offerings, and host annual and ongoing learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences.Work/Life BalanceOur team puts a high value on work-life balance. It isn’t about how many hours you spend at home or at work; it’s about the flow you establish that brings energy to both parts of your life. We believe striking the right balance between your personal and professional life is critical to life-long happiness and fulfillment. We offer flexibility in working hours and encourage you to find your own balance between your work and personal lives.Mentorship & Career GrowthOur team is dedicated to supporting new members. We have a broad mix of experience levels and tenures, and we’re building an environment that celebrates knowledge sharing and mentorship. Our senior members enjoy one-on-one mentoring and thorough, but kind, code reviews. We care about your career growth and strive to assign projects based on what will help each team member develop into a better-rounded engineer and enable them to take on more complex tasks in the future.
IN, TS, Hyderabad
Job summaryAre you excited about driving business growth for millions of sellers by applying Machine Learning? Do you thrive in a fast-moving, large-scale environment that values data-driven decision making and sound scientific practices? We are looking for experienced data scientists to build sophisticated decision making systems that help Amazon Marketplace Sellers to grow their businesses.Amazon Marketplace enables sellers to reach hundreds of millions of customers and provides sellers the tools and services needed to make e-commerce simple, efficient and successful. Our team builds the core intelligence, insights, and algorithms that power a range of products used by millions of sellers. We are tackling large-scale, challenging problems such as helping sellers to prioritise business tasks by bringing together petabytes of data from sources across Amazon.You will be proficient with creating value out of data by formulating questions, analysing vast amounts of data, and communicating insights effectively to audience of varied backgrounds. In addition, you'll contribute to online experiments, build machine learning pipelines and personalised data products.To know more about Amazon science, Please visit https://www.amazon.scienceKey job responsibilities· Collaborate with domain experts, formulate questions, gather, process and analyse petabytes of data to unearth reliable insights· Design & execute experiments and analyze experimental results· Communicate insights effectively to audience of a wide range of backgrounds· Formulate relevant prediction problems and solve them by developing machine learning models· Partner with data engineering teams to improve quality of data assets, metrics and insights· Leverage industry best practices to establish repeatable science practices, principles & processes
US, WA, Seattle
Job summaryAmazon Sub-Same-Day Supply Chain team is looking for an experienced and motivated Senior Data Scientist to generate data-driven insights influencing the long term SSD supply chain strategy, build the necessary predictive models, optimization algorithms and customer behavioral segments allowing us to discover and build the roadmap for SSD to enable operational efficiency and scale.Key job responsibilitiesWork with product managers, engineers, other scientists, and leadership to identify and prioritize complex problems.Translate business problems into specific analytical questions and form hypotheses that can be answered with available data using scientific methods or identify additional data needed in the master datasets to fill any gapsDesign, develop, and evaluate highly innovative statistics and ML modelsGuide and establish scalable, efficient, automated processes for large scale data analyses, model development, model validation and model implementationProactively seek to identify business opportunities and insights and provide solutions to shape key business processes and policies based on a broad and deep knowledge of Amazon data, industry best-practices, and work done by other teams.A day in the lifeIn this role, you will be a technical expert with significant scope and impact. You will work with Product Managers, Business Engineers, and other Scientists, to deeply understand SSDs current optimization strategy while benchmarking against industry best practices and standards to gain insights that will drive our roadmap. A successful Data Scientist will have extreme bias for action needed in a startup environment, with outstanding leadership skills, proven ability to build and manage medium-scale modeling projects, identify data requirements, build methodology and tools that are statistically grounded. It will be a person who enjoys diving deep into data, doing analysis, discovering root causes, and designing long-term scientific solutions. We are seeking someone who can thrive in a fast-paced, high-energy and fun work environment where we deliver value incrementally and frequently. We value highly technical people who know their subject matter deeply and are willing to learn new areas. We look for individuals who know how to deliver results and show a desire to develop themselves, their colleagues, and their career.About the teamAmazon's Sub-Same Day (SSD) delivery program is designed to get customers their items as fast as possible – currently in as quickly as five hours. With ultra-fast delivery becoming increasingly important, we are looking for an experienced Senior Data Scientist to help us benchmark against industry standards to uncover insights to improve and optimize the long term supply chain strategy for Amazons Sub-Same-Day business.
US, NY, New York
Job summaryJob summaryAmazon is looking for a passionate, talented, and inventive Applied Scientist with a strong machine learning background to help build industry-leading language technology.Our mission is to provide a delightful experience to Amazon’s customers by pushing the envelope in Natural Language Processing (NLP), Natural Language Understanding (NLU), Dialog management, conversational AI and Machine Learning (ML).As part of our AI team in Amazon AWS, you will work alongside internationally recognized experts to develop novel algorithms and modeling techniques to advance the state-of-the-art in human language technology. Your work will directly impact millions of our customers in the form of products and services, as well as contributing to the wider research community. You will gain hands on experience with Amazon’s heterogeneous text and structured data sources, and large-scale computing resources to accelerate advances in language understanding.We are hiring primarily in Conversational AI / Dialog System Development areas: NLP, NLU, Dialog Management, NLG.This role can be based in NYC, Seattle or Palo Alto.Inclusive Team CultureHere at AWS, we embrace our differences. We are committed to furthering our culture of inclusion. We have ten employee-led affinity groups, reaching 40,000 employees in over 190 chapters globally. We have innovative benefit offerings, and host annual and ongoing learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences.Work/Life BalanceOur team puts a high value on work-life balance. It isn’t about how many hours you spend at home or at work; it’s about the flow you establish that brings energy to both parts of your life. We believe striking the right balance between your personal and professional life is critical to life-long happiness and fulfillment. We offer flexibility in working hours and encourage you to find your own balance between your work and personal lives.Mentorship & Career GrowthOur team is dedicated to supporting new members. We have a broad mix of experience levels and tenures, and we’re building an environment that celebrates knowledge sharing and mentorship. Our senior members enjoy one-on-one mentoring and thorough, but kind, code reviews. We care about your career growth and strive to assign projects based on what will help each team member develop into a better-rounded engineer and enable them to take on more complex tasks in the future.
US, VA, Arlington
Job summaryAmazon is investing heavily in building a world class advertising business and we are responsible for defining and delivering a collection of self-service performance advertising products that drive discovery and sales. Our products are strategically important to our Retail and Marketplace businesses driving long term growth. We deliver billions of ad impressions and millions of clicks daily and are breaking fresh ground to create world-class products. We are highly motivated, collaborative and fun-loving with an entrepreneurial spirit and bias for action. With a broad mandate to experiment and innovate, we are growing at an unprecedented rate with a seemingly endless range of new opportunities.Sponsored Products helps merchants, retail vendors, and brand owners succeed via native advertising that grows incremental sales of their products sold through Amazon. The Sponsored Products Ad Marketplace organization optimizes the systems and ad placements to match advertiser demand with publisher supply using a combination of machine learning, big data analytics, ultra-low latency high-volume engineering systems, and quantitative product focus. Our goals are to help buyers discover new products they love, be the most efficient way for advertisers to meet their business objectives, and to build a major, sustainable business that helps Amazon continuously innovate on behalf of all customers.We are seeking a Sr. Applied Science Manager who has a solid background in applied Machine Learning and AI, deep passion for building data-driven products, ability to communicate data insights and scientific vision, and has a proven track record of leading both applied scientists and software engineers to execute complex projects and deliver business impacts.In this team, Machine Learning and Deep Learning technologies including Semantic Retrieval, Natural Language Processing (NLP), Information Extraction, Image Understanding, Learning to Rank are used to match shoppers' search queries to ads with per impression prediction models that run in real-time with tight latency budgets. Models are trained using self-supervised techniques, transfer learning, and supervised training using labeled datasets. Knowledge distillation and model compression techniques are used to optimize model performance for production serving.The Senior Manager role will lead science and engineering efforts in these areas for Amazon Search pages WW. The person in this role is responsible for: maintaining the consistent and long term reliability for the models and the delivery services that power them, managing diverse teams across multiple domains, and collaborating cross-functional with other senior decision makers. Our critical LPs for this role are Think Big, Are Right A lot, and Earns Trust. What is key is that the leader will need a dynamic mindset to build systems that are flexible and will scale.In this role, you will:· Lead a group of both applied scientists and software engineers to deliver machine-learning and AI solutions to production.· Advance team's engineering craftsmanship and drive continued scientific innovation as a thought leader and practitioner.· Develop science and engineering roadmap, run Sprint/quarter and annual planning, and foster cross-team collaboration to execute complex projects.· Perform hands-on data analysis, build machine-learning models, run regular A/B tests, and communicate the impact to senior management.· Hire and develop top talents, provide technical and career development guidance to both scientists and engineers in the organization.Locations: Seattle, WA; New York, NY; Arlington, VA
US, WA, Seattle
Job summaryWorkforce Staffing (WFS) brings together the workforce powering Amazon’s ability to delight customers: the Amazon Associate. With over 1M hires, WFS supports sourcing, hiring, and developing the best talent to work in our fulfillment centers, sortation centers, delivery stations, shopping sites, Prime Air locations, and more.WFS' Funnel Science and Analytics team is looking for a Research Scientist. This individual will be responsible for conducting experiments and evaluating the impact of interventions when conducting experiments is not feasible. The perfect candidate will have the applied experience and the theoretical knowledge of policy evaluation and conducting field studies.Key job responsibilitiesAs a Research Scientist (RS), you will do causal inference, design studies and experiments, leverage data science workflows, build predictive models, conduct simulations, create visualizations, and influence science and analytics practice across the organization.Provide insights by analyzing historical data from databases (Redshift, SQL Server, Oracle DW, and Salesforce).Identify useful research avenues for increasing candidate conversion, test, and create well written documents to communicate to technical and non-technical audiences.About the teamFunnel Science and Analytics team finds ways to maximize the conversion and early retention of every candidate who wants to be an Amazon Associate. By focusing on our candidates, we improve candidate and business outcomes, and Amazon takes a step closer to being Earth’s Best Employer.
US, NY, New York
Job summaryAmazon is looking for a passionate, talented, and inventive Applied Scientist with a strong machine learning background to help build industry-leading language technology.Our mission is to provide a delightful experience to Amazon’s customers by pushing the envelope in Natural Language Processing (NLP), Natural Language Understanding (NLU), Dialog management, conversational AI and Machine Learning (ML).As part of our AI team in Amazon AWS, you will work alongside internationally recognized experts to develop novel algorithms and modeling techniques to advance the state-of-the-art in human language technology. Your work will directly impact millions of our customers in the form of products and services, as well as contributing to the wider research community. You will gain hands on experience with Amazon’s heterogeneous text and structured data sources, and large-scale computing resources to accelerate advances in language understanding.We are hiring primarily in Conversational AI / Dialog System Development areas: NLP, NLU, Dialog Management, NLG.This role can be based in NYC, Seattle or Palo Alto.Inclusive Team CultureHere at AWS, we embrace our differences. We are committed to furthering our culture of inclusion. We have ten employee-led affinity groups, reaching 40,000 employees in over 190 chapters globally. We have innovative benefit offerings, and host annual and ongoing learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences.Work/Life BalanceOur team puts a high value on work-life balance. It isn’t about how many hours you spend at home or at work; it’s about the flow you establish that brings energy to both parts of your life. We believe striking the right balance between your personal and professional life is critical to life-long happiness and fulfillment. We offer flexibility in working hours and encourage you to find your own balance between your work and personal lives.Mentorship & Career GrowthOur team is dedicated to supporting new members. We have a broad mix of experience levels and tenures, and we’re building an environment that celebrates knowledge sharing and mentorship. Our senior members enjoy one-on-one mentoring and thorough, but kind, code reviews. We care about your career growth and strive to assign projects based on what will help each team member develop into a better-rounded engineer and enable them to take on more complex tasks in the future.
US, WA, Seattle
Job summaryAmazon's Weblab team enables experimentation at massive scale to help Amazon build better products for customers. A/B testing is in Amazon's DNA and we're at the core of how Amazon innovates on behalf of customers. We are seeking a skilled Applied Scientist to help us build the future of experimentation systems at Amazon.About you:You have an entrepreneurial spirit and want to make a big impact on Amazon and its customers. You are excited about cutting-edge research on unsupervised learning, graph algorithms, and causal inference in the intersection between Machine Learning, Statistics, and Econometrics. You enjoy building massive scale and high performance systems but also have a bias for delivering simple solutions to complex problems. You're looking for a career where you'll be able to build, to deliver, and to impress. You challenge yourself and others to come up with better solutions. You develop strong working relationships and thrive in a collaborative team environment.About us together:We're going to help Amazon make better long term decisions by designing and delivering A/B-testing systems for long-term experiments, and by using these systems to figure out how near term behavior impacts long term growth and profitability. Our work will inform some of the biggest decisions at Amazon. Along the way, we're going to face seemingly insurmountable challenges. We're going to argue about how to solve them, and we'll work together to find a solution that is better than each of the proposals we came in with. We'll make tough decisions, but we'll all understand why. We'll be the dream team.We have decades of combined experience on the team in many areas science and engineering so it's a great environment in which to learn and grow. A/B testing is one of the hottest areas of research and development in the world today and this is a chance to learn how it works in the company known for pioneering its use.
US, CA, Santa Clara
Job summaryAWS AI/ML is looking for world class scientists and engineers to join its AI Research and Education group working on building automated ML solutions for planetary-scale sustainability and geospatial applications. Our team's mission is to develop ready-to-use and automated solutions that solve important sustainability and geospatial problems. We live in a time wherein geospatial data, such as climate, agricultural crop yield, weather, landcover, etc., has become ubiquitous. Cloud computing has made it easy to gather and process the data that describes the earth system and are generated by satellites, mobile devices, and IoT devices. Our vision is to bring the best ML/AI algorithms to solve practical environmental and sustainability-related R&D problems at scale. Building these solutions require a solid foundation in machine learning infrastructure and deep learning technologies. The team specializes in developing popular open source software libraries like AutoGluon, GluonCV, GluonNLP, DGL, Apache/MXNet (incubating). Our strategy is to bring the best of ML based automation to the geospatial and sustainability area.We are seeking an experienced Applied Scientist for the team. This is a role that combines science knowledge (around machine learning, computer vision, earth science), technical strength, and product focus. It will be your job to develop ML system and solutions and work closely with the engineering team to ship them to our customers. You will interact closely with our customers and with the academic and research communities. You will be at the heart of a growing and exciting focus area for AWS and work with other acclaimed engineers and world famous scientists. You are also expected to work closely with other applied scientists and demonstrate Amazon Leadership Principles (https://www.amazon.jobs/en/principles).Strong technical skills and experience with machine learning and computer vision are required. Experience working with earth science, mapping, and geospatial data is a plus. Our customers are extremely technical and the solutions we build for them are strongly coupled to technical feasibility.About the teamInclusive Team CultureAt AWS, we embrace our differences. We are committed to furthering our culture of inclusion. We have ten employee-led affinity groups, reaching 40,000 employees in over 190 chapters globally. We have innovative benefit offerings, and host annual and ongoing learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences. Amazon’s culture of inclusion is reinforced within our 14 Leadership Principles, which remind team members to seek diverse perspectives, learn and be curious, and earn trust.Work/Life BalanceOur team puts a high value on work-life balance. It isn’t about how many hours you spend at home or at work; it’s about the flow you establish that brings energy to both parts of your life. We believe striking the right balance between your personal and professional life is critical to life-long happiness and fulfillment. We offer flexibility in working hours and encourage you to find your own balance between your work and personal lives.Mentorship & Career GrowthOur team is dedicated to supporting new members. We have a broad mix of experience levels and tenures, and we’re building an environment that celebrates knowledge sharing and mentorship. Our senior members enjoy one-on-one mentoring. We care about your career growth and strive to assign projects based on what will help each team member develop into a better-rounded scientist and enable them to take on more complex tasks in the future.Interested in this role? Reach out to the recruiting team with questions or apply directly via amazon.jobs.
US, CA, Santa Clara
Job summaryAWS AI/ML is looking for world class scientists and engineers to join its AI Research and Education group working on building automated ML solutions for planetary-scale sustainability and geospatial applications. Our team's mission is to develop ready-to-use and automated solutions that solve important sustainability and geospatial problems. We live in a time wherein geospatial data, such as climate, agricultural crop yield, weather, landcover, etc., has become ubiquitous. Cloud computing has made it easy to gather and process the data that describes the earth system and are generated by satellites, mobile devices, and IoT devices. Our vision is to bring the best ML/AI algorithms to solve practical environmental and sustainability-related R&D problems at scale. Building these solutions require a solid foundation in machine learning infrastructure and deep learning technologies. The team specializes in developing popular open source software libraries like AutoGluon, GluonCV, GluonNLP, DGL, Apache/MXNet (incubating). Our strategy is to bring the best of ML based automation to the geospatial and sustainability area.We are seeking an experienced Applied Scientist for the team. This is a role that combines science knowledge (around machine learning, computer vision, earth science), technical strength, and product focus. It will be your job to develop ML system and solutions and work closely with the engineering team to ship them to our customers. You will interact closely with our customers and with the academic and research communities. You will be at the heart of a growing and exciting focus area for AWS and work with other acclaimed engineers and world famous scientists. You are also expected to work closely with other applied scientists and demonstrate Amazon Leadership Principles (https://www.amazon.jobs/en/principles).Strong technical skills and experience with machine learning and computer vision are required. Experience working with earth science, mapping, and geospatial data is a plus. Our customers are extremely technical and the solutions we build for them are strongly coupled to technical feasibility.About the teamInclusive Team CultureAt AWS, we embrace our differences. We are committed to furthering our culture of inclusion. We have ten employee-led affinity groups, reaching 40,000 employees in over 190 chapters globally. We have innovative benefit offerings, and host annual and ongoing learning experiences, including our Conversations on Race and Ethnicity (CORE) and AmazeCon (gender diversity) conferences. Amazon’s culture of inclusion is reinforced within our 14 Leadership Principles, which remind team members to seek diverse perspectives, learn and be curious, and earn trust.Work/Life BalanceOur team puts a high value on work-life balance. It isn’t about how many hours you spend at home or at work; it’s about the flow you establish that brings energy to both parts of your life. We believe striking the right balance between your personal and professional life is critical to life-long happiness and fulfillment. We offer flexibility in working hours and encourage you to find your own balance between your work and personal lives.Mentorship & Career GrowthOur team is dedicated to supporting new members. We have a broad mix of experience levels and tenures, and we’re building an environment that celebrates knowledge sharing and mentorship. Our senior members enjoy one-on-one mentoring. We care about your career growth and strive to assign projects based on what will help each team member develop into a better-rounded scientist and enable them to take on more complex tasks in the future.Interested in this role? Reach out to the recruiting team with questions or apply directly via amazon.jobs.