Performance and Capacity Considerations

Compare model quality with the cost of training and serving it. This lesson uses training, evaluation, and sample complexity to reason about model choice, then works through a search-ranking example in which a funnel limits the cost of an expensive model.

As we work on a machine learning-based system, our goal is generally to improve our metrics (engagement rate, etc.) while ensuring that we meet the capacity and performance requirements.

Major performance and capacity discussions come in during the following two phases of building a machine learning system:

Training time: How much training data and capacity is needed to build our predictor?
Evaluation time: What are the Service level agreement(SLA) that we have to meet while serving the model and capacity needs?

Use training and evaluation cost when choosing both the model and the surrounding architecture. A model that improves the task metric still has to fit the available training resources and the serving requirements.

Complexities consideration for an ML system

Machine learning algorithms have three different types of complexities:

Training complexity

The training complexity of a machine learning algorithm is the time taken by it to train the model for a given task.
Evaluation complexity

The evaluation complexity of a machine learning algorithm is the time taken by it to evaluate the input at testing time.
Sample complexity

The sample complexity of a machine learning algorithm is the total number of training samples required to learn a target function successfully.

Note: Sample complexity changes if the model capacity changes. For example, for a deep neural network, the number of training examples has to be considerably larger than decision trees and linear regression.

The measure of training and evaluation time complexity on a sample data in a ML system

Comparison of training and evaluation complexities

The comparison below separates the cost of learning a model from the cost of using it for one prediction. Keep that distinction explicit when explaining why a model fits the task and the available resources.

Assume that

$n$ is the number of the training samples
$f$ is the number of features
$n_{t r ees}$ is the number of trees (for tree-based algorithms)
$n_{l_{i}}$ is the number of neurons at $i^{t h}$ layer in a neural network
$e$ is the number of epochs
$d$ is the max depth of the tree

The training and prediction complexity can be approximated in terms of asymptotic analysis as follows:

Algorithm	Training time	Evaluation time
Linear/Logistic Regression (Batch)	$O (n f e)$	$O (f)$
Neural Network	Dense feed-forward network: training passes × examples × forward/backward computation per example; cost depends on layer dimensions	$O (f n_{l_{1}} + n_{l_{1}} n_{l_{2}} + ...)$
Multiple Additive Regression Trees (MART)	$O (n df n_{t r ees})$	$O (f d n_{t r ees})$

For the neural-network row, consider a dense multilayer perceptron trained by backpropagation. Its training cost depends on the number of examples, training iterations, and the matrix operations between layers. It is not generally exponential in depth. The scikit-learn documentation gives a scoped expression using input size, hidden-layer width and count, output size, and training iterations. Use those dimensions to estimate the cost of the network you actually propose. Primary reference: scikit-learn MLP complexity.

Analysis

The evaluation complexity of the linear regression algorithm is equal to the complexity of a single-layer neural network-based algorithm. Linear regression is the best choice if we want to save time on training and evaluation. Let’s assume the model evaluates one example in 5 $μ$ s. For 100k examples, it would take 100k x 5 $μ$ s = 500 ms execution time on a single machine.

Now suppose the ad-prediction requirement is to select relevant ads within 300 ms. The 500 ms calculation above exceeds that budget by 200 ms even for the fast model in this example. You therefore need to reduce the work per request or distribute it, as the later examples illustrate; choosing a linear model alone does not meet the stated budget.
Relatively deep neural network takes a lot more time in both training and evaluation. Its need for training data is also high. However, it’s ability to learn complex tasks such as image segmentation and language understanding, is much higher, and it gives more accurate predictions in comparison to other models. Therefore a deep neural network is a viable choice if it is well suited for the task at hand and capacity isn’t a problem.
MART is a tree-based algorithm that has a greater computation cost than linear models, but it is much faster than a deep neural network. Tree-based algorithms are able to generalize well using a moderately-sized training dataset. Therefore, if our training data is limited to a few million examples and capacity/performance is critical, they will be a good choice.

Performance and capacity considerations in large scale system

Consider that a search system(e.g., Google, Bing) gets a query “computer science” that matches 100 million web pages. The ML-based system wants to respond with the most relevant web pages for the searcher while meeting the system’s constraints. These constraints are generally referred to as Service level agreements (SLA). There can be many SLAs around availability and fault tolerance but for our discussion of designing ML systems, performance and capacity are the most important to think about when designing the system. Performance based SLA ensures that we return the results back within a given time frame (e.g. 500ms) for 99% of queries. Capacity refers to the load that our system can handle, e.g., the system can support 1000 QPS (queries per second).

If we evaluate every document using a relatively fast model such as tree-based or linear regression and it takes 1

μ

s, our simple model would still take 100s to run for 100 million documents that matched the query “computer science”.

In the example, distribute the scoring work for one query across 1000 machines. Dividing the stated 100 seconds of scoring work by 1000 gives 100 ms. This calculation describes the ideal division of the model work; use it to compare designs, rather than as a complete measurement of the request path.

Input query sent to multiple shards to distribute load

Let’s now consider the scenarios in which we decided that a deep learning model for search ranking is a much better choice and helps improve our search metrics. However, deep learning is significantly slow, assuming that it needs 1ms to evaluate an example. Even now with our 1000 shards, it would still take 100s to rank all the results using this model. Clearly, we are far from our performance SLAs.

Adding shards could reduce the scoring time in this example, but the design has a fixed capacity budget. Another option is to reserve the expensive model for a smaller set of documents. That changes how much work the system performs before deciding how to distribute it.

Layered/funnel based modeling approach

A funnel starts with a fast model over the largest candidate set, such as the 100 million documents matching “computer science” in this example. Each later stage receives fewer candidates and can spend more computation on each one. A linear model might serve the first stage and a deep neural network the final stage.

Using the existing assumptions, a deep model that takes 1 ms per document needs 500 ms to score the top 500 documents on one machine. Dividing that work across five shards gives about 100 ms. The reduction from 100 million candidates to 500 is what makes this final stage affordable in the example.

Design choice: A funnel is useful in the search, recommendation, and ad-prediction examples because it reserves more expensive scoring for fewer candidates. Explain the candidate count at each stage alongside the model you propose.

The next figure applies the funnel to search ranking: each stage reduces the candidate set before more expensive scoring.

Layered model approach for search ranking system

The ad-prediction case study uses the same funnel idea to narrow eligible ads before detailed scoring. The next figure shows that flow.

Funnel approach for an ad prediction system