Speeding training of decision trees

New method reduces training time by up to 99%, with no loss in accuracy.

Gradient-boosted decision trees are a machine learning model commonly used in large-scale, online search applications because they combine high accuracy with high efficiency.

Maintaining that efficiency, however, means limiting the number of data features that gradient-boosted trees consider in making a decision. If the training data for a decision tree model has many possible features to choose from — say, thousands — and the model will end up using only a fraction of them — say, a couple hundred — then training can become inefficient, as most of the features the model evaluates will prove irrelevant.

In a paper accepted to the International Conference on Artificial Intelligence and Statistics, which was to be held last week but has been postponed until September, we present a new method for training gradient-boosted trees that is much more efficient than its most efficient predecessor in cases where the total feature set is larger than the necessary-feature set.

In tests, we compared our approach to three other implementations of gradient-boosted decision trees, using three popular benchmark data sets. Relative to the most efficient of its predecessors — a technique called gradient-boosted feature selection — our method reduced training time by 50% to 99%, while preserving the accuracy of the resulting models.

We also found that our approach is particularly well suited to multitask training, in which the machine learning model is trained to perform several tasks at once — identifying images of dogs, cats, and horses, for instance, instead of just one of the three.

In experiments, when our system was trained on three tasks simultaneously, it performed better on each of those tasks than when it was trained on a single task. We also compared it to the standard method of doing multitask training with gradient-boosted trees and found that it improved performance on all three tasks.

A decision tree is a binary tree — something like a flow chart — that presents a series of binary decisions. With each decision, the tree branches into two paths. Ultimately, every path through the tree reaches a terminal point known as a leaf. Each leaf has an associated number that represents its vote on some classification task: yes, I think this is a dog; no, I don’t think this song is a good match for the query.

DecisionTree-01.png
An example of a machine learning model that uses gradient-boosted decision trees. During training, the model builds trees in sequence; each new tree minimizes the residual error of the trees that preceded it. The output of each tree is its vote on a classification question, and the aggregated output of all the trees determines the final outcome.
Credit: Stacy Reilly

A model that uses gradient-boosted decision trees consists of multiple trees — possibly hundreds. During training, the model builds the trees in sequence. Each new tree is designed to minimize the residual error of the trees that preceded it: that’s the gradient boosting. The output of the model as a whole is the aggregate output of all the trees.

At each new decision point for each tree, the model has to select a decision criterion that will minimize the error rate of the model as a whole. That means evaluating every possible feature of the training data — in the case of a music track, artist, title, genre, date of release, bit rate, track number, and so on.

For each of those features, the model must find the best split point, the threshold value that determines whether the path branches left or right. If the data has 1,000 features, but only 100 of them will ultimately prove useful as decision criteria, most of that work is wasted.

Collective action

We address this problem by adapting the common binary-search algorithm. Before training, we normalize the values for each feature, so that they all fall within the range of 0 to 1. Then we randomly divide the features into two groups, creating two pseudo-features, whose values are simply the sums of the normalized values for the individual features. We repeat this process several times, producing several pairs of pseudo-features that evenly divide the feature set.

During training, at each decision point, we evaluate the tree using one pair of pseudo-features, selecting a split point for each in the ordinary fashion. We then take the pseudo-feature that leads to better prediction, randomly divide it into two new pseudo-features, and again test split points.

We repeat this process until we’ve converged on a single feature to serve as the criterion for that decision point. Rather than evaluate every feature, we evaluate a number of pseudo-features equal to the logarithm of the number of features.

This approach is only an approximation, but in the paper, we present a theoretical analysis showing that, given enough training data, the approximation should still converge on an optimal set of decision trees.

We also tested our approach empirically, on three standard benchmarks for machine learning research. One is a data set of handwritten numbers, and the goal is to identify the numbers; another is a data set of flight information, and the goal is to predict delays; and the third is an image recognition task. We compared our system’s performance to that of three other standard implementations of gradient-boosted trees.

In all cases, our system’s performance was within a fraction of a percentage point of the best-performing baseline’s — either ahead or behind — but its training time was much lower. The differences in training time varied depending on the systems’ target accuracy rate, but for the flight data set, the training time acceleration was consistently around twofold; for the handwriting recognition task, it was consistently around 10-fold; and for the image recognition task, it was consistently around 100-fold.

Related content

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, 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.
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, 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, 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, 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, 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.