Training and Cross-Validating Machine Learning Pipelines with Limited Memory

Authors: martin  hirzel
kiran  kate
louis  mandel
avraham  shinnar
Venue: automl_cc_AutoML_2024_Conference
Published: 2024-02-26 22:05:19

Abstract: While automated machine learning (AutoML) can save human labor in finding well-performing pipelines, it often suffers from two problems: overfitting and using excessive resources.  Unfortunately, the solutions are often at odds: cross-validation helps reduce overfitting at the expense of more resources; conversely, preprocessing on a separate compute cluster and then cross-validating only the final predictor saves resources at the expense of more overfitting.  This paper shows how to train and cross-validate entire pipelines on a single moderate machine with limited memory by using monoids, which are associative, thus providing a flexible way for handling large data one batch at a time.  To facilitate AutoML, our approach is designed to support the common sklearn APIs used by many AutoML systems for pipelines, training, cross-validation, and several operators.  Abstracted behind those APIs, our approach uses task graphs to extend the benefits of monoids from operators to pipelines, and provides a multi-backend implementation.  Overall, our approach lets users train and cross-validate pipelines on simple and inexpensive compute infrastructure.

Main paper: 
 introduction: 
 This paper tackles the problem of training and cross-validating machine-learning pipelines on large datasets while only needing limited memory. This enables the use of a moderately-sized cloud compute node, thus avoiding the cost of upgrading to a more powerful machine and the complexity of upgrading to a cluster. It even lets data scientists use a laptop, thus simplifying debugging, avoiding data transfer, and reducing competition for compute resources.Automated machine learning (AutoML) can jointly select algorithms and tune hyperparameters across an entire pipeline, including both data preprocessing and modeling [18, 46] . A pipeline is a directed acyclic graph of operators, where operators are data transformers (e.g., encoders, scalers) and predictors (e.g., classifiers, regressors). A pipeline edge 𝑃 → 𝑆 means that intermediate data transformed by a predecessor operator 𝑃 becomes the input to a successor operator 𝑆. As the most popular library for defining such pipelines today is sklearn [8] , this paper adopts sklearn terminology, but its concepts apply more broadly. Many AutoML systems expect sklearn APIs [16, 18, 25, 36] , and many third-party libraries conform to sklearn APIs [5, 10, 9, 14, 21, 24, 28] . We have extended the sklearn-compatible AutoML framework Lale [4] with our operators and algorithms.Operators have two execution modes, training (fit in sklearn) and application (transform or predict). Training a pipeline requires both execution modes. To train an operator 𝑆 of a pipeline, the input data of 𝑆 must be transformed by its predecessors, which in turn must be already trained. 1 for each operator 𝑆 in pipeline.topological_order: Here, out maps from operators to their intermediate transformed collection of output data, as well as the input data at the start of the pipeline. Unfortunately, this naive algorithm uses excessive memory, since it retains all non-batched intermediate data in out.One approach that avoids holding the entire training data in memory is deep learning [27] . Unlike general machine learning, deep learning uses an execution regime we call partial transform: a partially-fitted predecessor layer 𝑃 transforms data for a successor layer 𝑆 so a batch passes all the way through the network without the predecessor being fully trained first. Unfortunately, partial transform does not work for all data preparation operators. For instance, the OneHotEncoder operator encodes categorical features as a one-hot numeric array; training this operator on additional batches can discover new categories, thus invalidating encodings of earlier batches. Hence, data preprocessing for deep learning usually happens separately, not in a single combined pipeline.To enable training and cross-validating sklearn-style pipelines on large data without requiring partial transform, this paper uses monoids to support batching at the pipeline level. A monoid is simply a set with a binary associative combine operation and an identity element [7, 23, 45] . We express the training of several common operators as monoids, so they can train on each batch independently before combining learned coefficients from different batches. Next, we express the training of a pipeline of operators using a task graph with tasks for lifting batches to monoids, combining monoids, and applying operators. Using monoids in task graphs maximizes flexibility for reuse and scheduling, enabling us to minimize spilling to disk via a resource-aware schedule. Specifically, the associativity of monoids allows batches to be processed and combined in a more efficient order while guaranteeing equivalent end results to those of doing the work sequentially. Importantly for AutoML, monoids even let us eliminate some spurious work during cross-validation. This is because the associativity of monoids lets us do some computations only once per fold and then combine these reusable partial results into multiple sets of folds.Our task-graph framework is general enough to faithfully emulate common machine-learning pipeline semantics. We express our monoidal operators via relational algebra to decouple them from backends. We implement the relational algebra operators on two backends, pandas [30] and Spark SQL [2] . The Spark SQL backend scales to large data and is distributed. The pandas backend also scales to large data thanks to our batching and spilling implementation but is not distributed and has lower framework overhead. This paper makes the following novel contributions: • A monoidal framework to express the training of data preprocessing operators (Section 2).• Algorithms for batched training or cross-validation of pipelines via task graphs that leverage monoids for resource-aware scheduling and spilling (Section 3). • A generic implementation of the approach on top of relational algebra operators and two backends targeting pandas and Spark SQL (Section 4). Our implementation is open-source: https://github.com/IBM/lale/tree/master/lale/lib/rasl. 
monoids: 
 To train in limited memory, we want batch-wise training, but unlike in deep learning, we cannot pass a batch through the entire pipeline. Instead, we need to hold on to intermediate tranformed data whose size can exceed the memory budget, necessitating spilling. Since spilling is expensive, we want to minimize it by processing batches as independently as possible, without "harmful" [44] sequential dependencies on their predecessor. Fortunately, there is a very simple abstraction that supports exactly that: a monoid, which is a set with an associative operator. Besides enabling flexible schedules, monoids also enable us to eliminate some duplicate effort in cross-validation.A core insight of this paper is that several common machine-learning operators are monoidal, which we define as being expressible via the following three operations: • to_monoid : BatchXy → Monoid, for lifting a batch to the monoid of the operator's learned coefficients; • combine : Monoid × Monoid → Monoid, for combining learned coefficients from different batches; and • from_monoid : Monoid → TrainedOp, for lowering learned coefficients from their monoidal form into a form suitable for the operator to be applied. We express the training (fit in sklearn) of a monoidal machine-learning operator by applying the to_monoid operation to each batch and then applying the combine operation. And we express the application (transform or predict) by applying the from_monoid operation and using its results. x: 2, , 3x: 3, 1, 5x: , 4,  n x : 2, s x : 5 n x : 3, s x : 9 n x : 1, s x : 4 n x : 6, s x : 18x: 2, 3, 3x: 3, 1, 5x: 3, 4, 3 to_monoid(X) combine(a, b) transform(X)fit(X, y)Filter(x )>> Agg(n x : |x|, s x : x) Map(n x : a.n x +b.n x , s x : a.s x +b.s x ) Map(x: replace(x, {: The edges coming out of scan tasks are annotated with the values for an example column, 𝑥, that contains either numbers or a missing value, denoted ⊥. The to_monoid operation filters non-missing values and computes their count 𝑛 𝑥 and sum 𝑠 𝑥 . (The >> combinator denotes function composition.) The edges coming out of to_monoid tasks are annotated with combinable learned coefficients. For instance, in 𝑥 : 2, ⊥, 3, the number of non-missing values is 𝑛 𝑥 : 2 and their sum is 𝑠 𝑥 : 5. The combine task applies the monoid's operation; being associative, it can freely choose how to arrange the binary operations to combine multiple (here three) pieces. In this case, combine sums 𝑛 𝑥 and 𝑠 𝑥 from its predecessors. Finally, transform uses from_monoid to compute the arithmetic mean 𝑠 𝑥 𝑛 𝑥 , here 18 6 = 3, and replaces missing values with that number. For illustration purposes, the example shows only 3 rows, 1 column, and 3 batches; with more rows, columns, and batches, the monoidal data per column and batch is still small, comprising just the count 𝑛 𝑥 and the sum 𝑠 𝑥 .s x n x }))We can express several common preprocessing operators via monoids. For instance, Standard-Scaler scales values by subtracting the mean and dividing by the standard deviation. Its monoid stores, for each column 𝑥 of a dataset 𝑋 , the count 𝑛 𝑥 of rows without missing value, the sum of the values in the column 𝑠 𝑥 = 𝑥, and the sum of squares sq 𝑥 = 𝑥 2 𝑖 . Then, transform calls from_monoid to lower these into the concrete mean and standard deviation, which it uses to scale data. The monoidal approach is not limited to preprocessing. For instance, BatchedBaggingClassifier is an ensemble where the monoid holds a list of base classifiers trained on separate batches [23] . The appendix provides the monoidal formulations of ten operators (MinMax-and StandardScaler, SimpleImputer, Project, OneHot-, Ordinal-, Target-, and HashingEncoder, SelectKBest, and Batched-BaggingClassifier) and six metrics (accuracy, 𝐹 1 , 𝑅 2 , DI [17] , symmetric DI, and accuracy-and-DI).Alternatives to Monoids. Not all machine-learning operators are monoidal, but some exhibit other properties that can also be useful towards batch-wise training. Section 3 will leverage the property of being monoidal and other alternative properties to give formal guarantees.• An incremental operator has a method partial_fit : TrainableOp × BatchXy → TrainedOp. The method is designed to be invoked repeatedly on the same operator, with each call modifying the object by updating its learned coefficients. The first call changes it from trainable to trained. For example, in sklearn, MinMaxScaler and SGDClassifier have partial_fit. • A convergent operator 𝑆 is one where, after fitting on different batches 𝑑 1 , 𝑑 2 , transforming a third batch 𝑑 3 yields similar results: 𝑆.fit(𝑑 1 ).transform(𝑑 3 )≈𝑆.fit(𝑑 2 ).transform(𝑑 3 ). Unlike being monoidal or incremental, which are algebraic properties, being convergent is an approximate property. However, deep learning universally assumes it for all layers. Likewise, stacking ensembles assume that their base predictors are convergent across folds. TargetEncoder [31] is convergent but OneHotEncoder is non-convergent. One core insight of this paper is that batch-wise training does not require convergence; that said, for completeness, we will also show experiments that leverage convergence. • A pretrained operator implements training (i.e., fit) as a no-op. It can be viewed as trivially incremental, monoidal, and convergent. An example is a frozen embedding such as BERT [13] if used in a pipeline without fine-tuning [9] . We also implemented HashingEncoder, a categorical encoder that lacks learned coefficients and is thus pretrained. 
task graphs: 
 This paper shows how to use batching to train a pipeline on a large dataset without using too much memory at any one time. The goal is to define an algorithm that takes as input a trainable pipeline and an iterator over batches of the training dataset, and outputs a trained pipeline. To train on large datasets, assuming that all operators in the pipeline implement an incremental training method partial_fit, we could extend the naive algorithm from Section 1 by adding an inner loop and a cache. We refer to this as the nested-loops algorithm and show it in Figure 3 .1 for each operator 𝑆 in pipeline.topological_order: Unfortunately, its rigid structure of repeated full passes over all data batches causes wasteful spilling and loading. The root cause of the inflexibility is that partial_fit is intrinsically sequential [44] . Besides limiting scheduling flexibility and thus wastefully spilling, partial_fit yields a computation with a long critical path [6] . Furthermore, in cross-validation, it reduces opportunities for computation reuse [23] . This paper introduces an alternative algorithm based on monoids and task graphs. Definitions. Like a pipeline, a task graph is a directed acyclic graph. But unlike pipeline nodes, task graph nodes are not operators but tasks. As defined in Figure 4 , each task (node) is given by an operation, a step, one or more batches, and an optional holdout. For example, the task graph in Figure 2 contains a task 'combine SIM(d0,d1,d2)', where the operation is combine, the step is SIM = SimpleImputer, and the batches are (d0,d1,d2). There are two kinds of tasks based on their operation: apply tasks (angular nodes in Figure 2 ) produce data and train tasks (rounded nodes in Figure 2 ) produce learned coefficients. The step is one of INP = input, SCR = score, or a pipeline operator. Since Figure 2 shows an example for training without cross-validation, all tasks have a batch belonging to the same fold (d), and none specify a holdout.1 create first scan task and goal tasks 2 while any tasks ready: Algorithm. Figure 5 shows our algorithm for batchwise training or cross-validating machine-learning pipelines. The initial phase, in L1, translates the trainable pipeline to an initial task graph, with a task scan INP(d 0 ) to read the first batch (d 0 ) of the input dataset (INP) and a goal task for each operator 𝑆 of the pipeline. A goal task is a task that, when completed, contributes directly to the output of the algorithm. For example, 'combine SIM(d0,d1,d2)' in Figure 2 is a goal task that computes the learned coefficients for the SimpleImputer operator on all batches.The main phase, in L2-L8 of Figure 5 , is a worklist algorithm that executes tasks as they become ready. A task is ready when all its predecessors are done. L3 can pick any ready task, and can be configured with different priorities; for instance, to minimize spilling, our resource-aware scheduler prioritizes tasks whose input batches are resident. L4 checks if there is enough memory for the task T, spilling batches if needed and loading any previously spilled input batches for T. L5 executes task T, performing its associated operation and storing the result with the task. L6 checks whether T was a scan task that actually returned a new batch, as opposed to having reached the end of the input iterator. In that case, L7 adds a new scan task node to the task graph for scanning the next batch of input. L8 performs backward chaining, starting from goal tasks to create their required recursive predecessors (see below for detailed rules). The final phase, in L9, reads the desired outputs from goal tasks. For example, in Figure 2 , it would read the learned coefficients from 'combine SIM(d0,d1,d2)' and create a trained SimpleImputer from them in the trained pipeline. Batched training with the full-transform regime. Our first regime works in limited memory by batching, and is faithful to the usual semantics of general (non-deep) machine learning pipelines by waiting for operators to be fully trained before applying them. Figure 6 shows an example. Let 𝑃 ∈ preds(𝑆) and 𝑛 be the number of batches. Figure 7 shows the backward chaining rules (R). Backward chaining moves in the opposite direction of task graph edges, back from successor tasks to predecessor tasks. While there are fresh tasks, it attempts to match a fresh task against the right pattern of all rules. If the match succeeds, it finds or creates the left part indicated in the rule. For example, in Figure 6 , R1 matches transform B(d0), creates transform A(d0), and creates the edge between them. The following formal guarantees (FG) hold for this regime. FG1: All schedules behave equivalently. Regardless of the schedule used by L3 of Figure 5 , the final trained pipeline has the same learned coefficients, because R3 trains an operator on all batches and R4 applies such a fully-trained operator. FG2: This regime yields the same result as sklearn. Thanks to FG1, if suffices to show this for one schedule. Let PrioStep be a scheduling priority that favors tasks for earlier operators, or, if the operator matches, favors tasks for earlier batches. PrioStep recovers the nested-loops algorithm in Figure 3 . To reduce spilling and loading, we also define PrioResourceAware that favors tasks with less non-resident input data; thanks to FG1, it is equivalent. (R1 and R2 from Figure 7 ) Batched training with the partial-transform regime. Our second regime supports incremental training by applying operators even when they are not yet fully trained. This approach is uncommon in general machine-learning but common in deep learning [27] . Figure 8 shows an example and Figure 9 shows the rules. To get the most out of the partial-transform regime, we define a scheduling priority PrioBatch that favors tasks for earlier batches, or if the batch matches, favors tasks for earlier steps. This regime guarantees the following: FG3: With PrioBatch, all operators are trained up to batch 𝑖 before scanning batch 𝑖 + 1. In other words, it trains a pipeline incrementally, which can for instance be used to monitor a learning curve or for early stopping [29, 40] . Compared to the full-transform regime, the partial-transform regime is more restrictive (requiring convergent operators) and offers weaker guarantees (lacking FG1); fortunately, our approach supports both regimes. A(d0) scan INP(d0) combine A(d0,d1,d2) scan INP(d1) scan INP(d2) to_monoid A(d1) to_monoid A(d2) transform A(d1) transform A(d2) transform A(d0) to_monoid B(d0) combine B(d0,d1,d2) to_monoid B(d1) to_monoid B(d2) transform B(d1) transform B(d2) transform B(d0) to_monoid C(d0) combine C(d0,d1,d2) to_monoid C(d1) to_monoid C(d2)transform A(d0) to_monoid A(d0) scan INP(d0) to_monoid C(d0) combine A(d0,d1) scan INP(d1) scan INP(d2) to_monoid A(d1) to_monoid A(d2) to_monoid B(d0) transform B(d0) transform A(d1) combine B(d0,d1) to_monoid B(d1) transform B(d1) combine C(d0,d1) to_monoid C(d1) combine A(d0,d1,d2) transform A(d2) to_monoid B(d2) combine B(d0,d1,d2) transform B(d2) combine C(d0,d1,d2) to_monoid C(d2)R5: to_monoid 𝑆 (d 0 ) → apply 𝑆 (d 0 ) R6: combine 𝑆 (d 0 , ..., d 𝑖 ) → apply 𝑆 (d 𝑖 ) R7: combine 𝑆 (d 0 , ..., d 𝑖 ) → combine 𝑆 (d 0 , ..., d 𝑖+1 ) R8: to_monoid 𝑆 (d 𝑖+1 ) → combine 𝑆 (d 0 , ..., d 𝑖+1 )scan Cross-validation with the in-fold regime. Our third regime performs 𝑘-fold cross-validation with the usual semantics: for each of 𝑘 folds (denoted e, f, g, ...), hold out one fold ℎ and train the pipeline on the remaining 𝑘 -1 folds (denoted d\ℎ), scoring on the held-out fold ℎ. Let 𝑓 𝑖 denote fold 𝑓 at batch index 𝑖, e.g., e 0 . The resulting task graph may contain multiple different tasks 'apply 𝑆 (𝑓 𝑖 )' for trained copies of the same operator 𝑆 on the same batch 𝑓 𝑖 that differ only in which fold was held out for training them. To disambiguate, let T\ℎ be a task T with a holdout fold ℎ. Figure 10 shows an example and Figure 11 shows the rules. Since the total number of batches is a priori unknown and may not be a multiple of the number of folds, we must split each batch into folds when it arrives. This is handled by explicit split tasks and rule R9. Tasks for source operators (preds(𝑆) = {INP}) can share work, since their left-hand side is still fold-agnostic, as expressed by rules R10-R12. This work sharing does not occur in non-source operators, see R13-R15. Given 𝑘 folds and 𝑛 batches, this regime makes the following formal guarantees. FG4: This regime yields the same result as sklearn's cross_val_score. FG5: A source operator has 𝑘𝑛 to_monoid tasks, a non-source operator has (𝑘 -1)𝑘𝑛 to_monoid tasks, and all operators have (𝑘 -1)𝑘𝑛 apply tasks. It saves a factor of 𝑘 -1 to_monoid tasks for source operators. For space reasons, Figure 10 only illustrates the case with a single batch; see Figure 23 in the appendix for an example with multiple batches. (R9 from Figure 11 ) R16:INP(d 𝑖 ) → split INP( 𝑓 𝑖 ) R10: split INP( 𝑓 𝑖 ) → apply 𝑆 (𝑓 𝑖 )\ℎ R11: split INP (𝑓 𝑖 ) → to_monoid 𝑆 (𝑓 𝑖 ) R12: to_monoid 𝑆 (𝑓 𝑖 ) → combine 𝑆 (d 𝑖 \ℎ)\ℎ R13: apply 𝑃 (𝑓 𝑖 )\ℎ → apply 𝑆 (𝑓 𝑖 )\ℎ R14: apply 𝑃 (𝑓 𝑖 )\ℎ → to_monoid 𝑆 (𝑓 𝑖 )\ℎ R15: to_monoid 𝑆 (𝑓 𝑖 ) → combine 𝑆 (d 𝑖 \ℎ)\ℎapply 𝑃 (𝑓 𝑖 ) → apply 𝑆 (𝑓 𝑖 ) R17: Cross-validation with the out-of-fold regime. Our fourth regime performs 𝑘-fold crossvalidation with alternative semantics. It depends on all operators being convergent. Figure 12 shows an example and Figure 13 shows the rules. In the out-of-fold regime, training 𝑆 always uses only data resulting from out-offold applications of its predecessors 𝑃, and to_monoid tasks are never qualified by a holdout. This leads to more sharing. Let 𝑘 and 𝑛 be the number of folds and batches as before. FG6: Each operator has 𝑘𝑛 to_monoid tasks and apply tasks. The out-of-fold regime unlocks the reuse enabled by monoids to save a factor of 𝑘 -1 to_monoid and transform tasks for all operators, not just for source operators. But it lacks FG4: it may yield a different result than sklearn. For space reasons, Figure 12 only illustrates the case with 1 batch; see Figure 24 in the appendix for an example with multiple batches.apply 𝑃 (𝑓 𝑖 ) → to_monoid 𝑆 (𝑓 𝑖 ) R18: to_monoid 𝑆 (𝑓 𝑖 ) → combine 𝑆 (d 𝑖 \ℎ) if 𝑓 ≠ ℎ 
implementation: 
 Except for BatchedBaggingClassifier, we define all monoidal operators using a relational algebra to abstract over backends. Our algebra has three kinds of operators (c.f. Table 4 in the appendix):• Unary (operators with signature Our relational operators mostly follow text-book semantics, with a few deviations. As usual in dataframe systems including pandas [30] and Spark SQL [2] , Grouped data is not normalized. A Table is a two-dimensional data structure with a fixed set of named columns and an ordered sequence of rows. In addition, unlike classical relational algebra, each Table has a name and an index. The table name is used by 𝑛-ary operators to identify one of their inputs, as doing so positionally would be less intuitive [3] . An index comprises one or more special columns of unique values that keep track of row order and identity but are separate from the payload data columns. Indexes support a common pattern in preprocessing pipelines: first preprocess different sets of columns separately (e.g., categorical encoding vs. numeric scaling), then concatenate columns belonging to the same row. To support this, each sub-pipeline must preserve row order and identity. Most of our relational operators (e.g. Map) preserve the index, and thus so do monoidal operators built with them.Each of our relational operators has two equivalent implementations, one on pandas [30] and the other on Spark SQL [2] . Both backend libraries provide their own dataframe types, which have some differences that we needed to work around. While pandas dataframes come with an index, Spark SQL dataframes do not, so we had to implement our own index support over Spark SQL dataframes. We did that by repurposing some regular columns, and attaching metadata to each dataframe for keeping track of which columns are index vs. payload. For table names, the situation was reversed: while Spark SQL dataframes can carry a table name, pandas dataframes do not, so we had to add one as metadata. Another difference is that whereas pandas expressions execute eagerly, Spark SQL expressions lazily build up query plans for later execution. Our implementation lets Spark SQL grow these query plans across multiple tasks in a task graph and only forces execution when necessary. That gives Spark SQL's query plan optimizer the opportunity to optimize across tasks and even across operators in a machine-learning pipeline. Our monoidal operators are oblivious of the backend, since they use our relational operators. Relational operators pick a backend by checking the type of their input data, so the same pipeline can work on both backends. 
results: 
 This section describes our experiments to answer six research questions (RQs). RQ1. Can batching enable fitting pipelines on larger data without Spark SQL? We compared our batched full-transform training regime with our pandas backend against the training of an equivalent sklearn pipeline. The pipeline comprised a SimpleImputer, OrdinalEncoder, SelectKBest, and SGDClassifier or SGDRegressor depending on the dataset. To create a limited memory setting, we controlled the memory allotted to the Python process starting from 64GB going down in steps of 2GB. We noted the value at which sklearn training fails and ran the batched training with that memory size with a batch size of 10,000. Table 1 shows the result on four large datasets. Batched training worked successfully with the memory limit, confirming that our approach enables training pipelines on datasets too large for sklearn pipelines to process. We reran the experiment on a cloud VM with only 8GB of physical memory and its default system swap space of 2GB. The result was the same: sklearn ran out of memory while our batched training succeeded. RQ2. When should users use the pandas backend and when the Spark SQL backend? This experiment compared the computational performance (speed) of the pandas and Spark SQL implementations of our operators. (We also checked the predictive performance of the two backends and found them to be identical as seen in Table 9 .) We record the time to train a classification pipeline on 10 OpenML [47] datasets. We upsample each dataset to observe how each of the backends performs as the data size increases. Figure 14 shows the results of this comparison. We used Spark SQL in local mode so the hardware resources are the same for the two backend runs. While neither backend is a clear winner, providing two backends enables users to choose the faster one for their circumstances, which can obtain a substantial speedup over the other.RQ3. Do the pandas and Spark SQL backends yield identical results to sklearn? We used monoids to reimplement six operators from sklearn (MinMaxScaler, StandardScaler, OneHotEncoder, Ordi-nalEncoder, SelectKBest, and SimpleImputer) plus two operators from scikit-learn-contrib (Hashing-Encoder and TargetEncoder). To check if they behave the same as the original implementation, we extracted examples from the documentation (https://scikit-learn.org/stable/modules/classes.html and http://contrib.scikit-learn.org/category_encoders/) and executed them with our implementation. We obtained the same results. In addition, we implemented tests that systematically compare the output and public state of our operators with the reference implementation. They do not always produce equal results but very similar ones (< 10 -7 difference). Table 5 in the appendix provides a detailed summary of the experiments.RQ4. Does batched execution yield identical results as non-batched? This experiment verifies that the batched task graph execution with the full-transform regime on our pandas backend generates the same outputs as a sklearn-style non-batched execution using our monoidal preprocessing operators. The pipeline for this experiment comprises a SimpleImputer, OrdinalEncoder, SelectKBest, and RandomForestClassifier. RandomForestClassifier does not support partial_fit, ensuring that any accuracy differences would only be due to the preprocessing prefix of the pipeline. We control the random seeds for the train-test splits. The mean accuracy and standard deviation over 5 random 80%-20% train-test splits of 10 OpenML [47] datasets was identical for the two cases (see appendix). RQ5. How much accuracy does partialtransform training lose? Figure 15 shows the results from an experiment with 10 OpenML [47] datasets and 10 incremental classifiers. In each experiment, the classifier is the final operator in a pipeline with convergent preprocessing operators (SimpleImputer, MinMaxScaler, Hashing-Encoder). We repeated each run with 5 different random 80%-20% splits. The nonincremental regimes (non-inc-sklearn and non-inc-rasl) use a single fit call, and differ in whether they use sklearn preprocessing operators directly or our monoidal reimplementations. The incremental regimes (partial-fit and partial-transform) split the training set into 5 batches. Here, partial-fit refers to the case of only transforming data with preprocessing operators after they have been trained on all batches. Each bar averages the accuracy from 5 holdout splits, then normalizes to non-inc-sklearn, and finally averages over 10 datasets. While the non-incremental regimes tend to perform better (especially for MLPClassifier, where fit makes multiple passes over the data), the two non-incremental regimes perform similarly to each other and the two incremental regimes perform similarly to each other. For incremental training, partial-transform loses very little accuracy compared to partial-fit. RQ6. How effective is out-of-fold cross-validation at picking models? To quantify how good a cross-validation regime is, we let it pick the model that has the best accuracy according to the regime, and then check where that model ranks on the holdout set. The out-of-fold regime yields a smaller task graph but also reduces isolation between training on different folds. This ranking experiment used the same 10 classifiers and 10 datasets as in RQ5. Let inf_cv𝑘 and oof_cv𝑘 denote the in-fold and outof-fold cross-validation regimes, where 𝑘 is the number of folds, and let holdout𝑘 denote batched training followed by evaluation on the holdout set, where 𝑘 is the number of batches. Both ranks and slow-downs are relative to holdout3 and averaged across 10 datasets, with error bars showing standard deviations; for both, lower is better. All configurations attempt 10 classifiers and the rank is computed by finding the configuration's best classifier on the rank list according to holdout3. All configurations used monoidal preprocessing operators but non-incremental fit for the final classifier. Figure 16 shows the results. Being the baseline, by definition, holdout3 has rank 1 with zero standard deviation. Since there are 10 classifiers, random picking would yield an expected rank of 5.5. The out-of-fold regime is faster than in-fold thanks to the smaller task graph. The results for ranks are less clear due to the large error bars. Given that the out-of-fold regime may leak information between folds, it might do worse on ranking.We discuss prior work related to each of the three contributions of our paper listed in Section 1.Monoids. Izbicki [23] defines monoidal operators including variants of Bayes classifiers, decision trees, and ensembling. He motivates these with uses for cross-validation, parallelization, and online training. Mergeable summaries [1] are monoidal approximate algorithms for frequency estimation, quantile summary, etc. In MapReduce [12] , reduce operations do not have to be associative, but they often are [49] , in which case they unlock more optimizations. In a streaming setting, monoids are essential to efficient incremental sliding window aggregation [20] . Steele observes that, in contrast to the linear accumulator mindset prevalent in functional programming, monoids enable binary decomposition algorithms [44] . Associative aggregation has also been at the core of data warehousing [19] . In contrast to the above-listed papers, we show how to express common sklearn operators as monoids in the context of an end-to-end machine learning pipeline.Task graphs. Dask implements partial_fit methods to enable batching for several sklearn operators, and provides a parallel engine for "dask graphs" [39] . Like our work, Dask connects to pandas and sklearn; but unlike our work, Dask does not use monoids, nor does it tackle end-to-end pipelines. Paramo uses a task graph for cross-validation and algorithm selection of a learning pipeline on Hadoop [34] . KeystoneML provides a joint pipeline abstraction across data preparation and machine learning in Spark, with parallelism and intra-pipeline caching [43] . Helix goes one step further with inter-pipeline caching across trials [48] . Cilk defines task graphs for work stealing approach with asymptotically optimal parallel speedup [6] . Ray provides task graphs for distribution and lets users interleave training with serving [33] . In contrast to these systems, our task graphs leverage monoids for computation reuse and scheduling flexibility, contributing backward chaining rules for sklearn compatible and novel regimes.Machine learning and relational algebra. We published a non-archival workshop paper on RASL [41] with an early version of most of the relational algebra operators used here, but none of the monoids built on top and no task graphs. Modin is a pandas alternative based on a dataframe algebra with a relational core [38] . We use a similar data model and similar operators, but use pandas as a backend instead of supplanting it. Several papers have melded linear algebra with relational algebra, including SparkNet [32] , LaraDB [22] , Weld [37] , and Lara [26] . Unlike these, we use relational algebra as an intermediate layer to implement monoids usable in task graphs.This paper presents techniques for training or cross-validating machine-learning pipelines in limited memory. The main idea is to process data one batch at a time, and to express operators with monoids for flexibility and reuse. Our implementation enables AutoML tools to use common sklearn APIs for end-to-end pipelines over large datasets with a single modest compute node.After careful reflection, the authors have determined that this work presents no notable negative impacts to society or the environment.(c) Did you ensure sufficient code quality and documentation so that someone else can execute and understand your code? [Yes] (d) Did you include the raw results of running your experiments with the given code, data, and instructions? [Yes] The rasl_experiments directory in the supplemental material has two sub-directories with raw results.(e) Did you include the code, additional data, and instructions needed to generate the figures and tables in your paper based on the raw results? [Yes] The supplemental material includes notebooks which generate some of the figures in the paper. (b) Did you discuss whether and how consent was obtained from people whose data you're using/curating if the license requires it? [N/A] The license does not require it.(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] The data does not contain personally identifiable information or offensive content.5. If you created/released new assets (e.g., code, data, models). . . pretrained: no fit (e.g., ConcatFeatures, Project with fixed columns) convergent: partial_fit and to_monoid (e.g., MinMaxScaler, SimpleImputer with mean) incremental: partial_fit (e.g., SGDClassifier, MLPClassifier) associative: to_monoid (e.g., OrdinalEncoder, OneHotEncoder) non-incremental (e.g., RandomForestClassifier, SimpleImputer with mode)Figure 17 : Taxonomy for operator properties from Section 2. The properites form a lattice, where each property subsumes all properties reachable by following lines "down". For instance, every convergent operator is also both incremental and associative. >> Aggregate(columns={"n": count(it.y), "y": sum(it.y), "y2": sum(it.y2), "e2": sum(it.e2)})) 4 for implementing operators and metrics, they can also be used directly, as this example illustrates. GaussianNB sklearn [8] MultinomialNB sklearn [8] Perceptron sklearn [8] SGDClassifier sklearn [8] PassiveAggressiveClassifier sklearn [8] MLPClassifier Lale [4] BatchedBaggingClassifier Snap ML [14] BatchedTreeEnsembleClassifier LightGBM [24] LGBMClassifier XGBoost [10] XGBClassifier AutoML 2024© 2024 the authors, released under CC BY 4.0 
 
 Appendix:  


Decision: When it comes to the quality of the work, the reviewers seem to be in agreement. 

However, I would like to raise the following important point. AutoML is one of the conferences that sets a clear standard when it comes to reproducibility and code availability (see the call for papers). Open science is not optional. The reproducibility reviewer has flagged that this paper is not accompanied by the proper code. In their reply, the authors stated that they would release their code upon the acceptance of the paper. By adhering to such (closed science) practice, they have bypassed the reproducibility review process, and not offered the reproducibility reviewer the chance to review this paper. While clearly stated by the reproducibility reviewer, the authors did not correct this during the discussion phase. The call for papers also clearly points towards the anonymized Git platform anon-github, further facilitating and explaining the emphasis on open science. 

As such, based on the call for papers, this paper can not be accepted to the main track of the AutoML conference, but should rather be submitted to the workshop track. However, I would also suggest take into consideration the following matters: 
*) The current scientific system is unfortunately not yet fully geared towards open science, and at many other conferences authors get away by keeping their code and datasets closed
*) The authors do state that they intend to release the code as part of the camera-ready copy
*) This situation could be a genuine misunderstanding because of the ambitious (and correct) goals that the AutoML conference sets

I am willing to give the authors the benefit of the doubt, and will advice to accept this paper for the main track of the conference under the absolute condition that the code will be made available as part of the library for the CRC copy, as they promise in the paper. This does have the unfortunate consequence that the reproducibility review has been bypassed, and as such I would impress upon the authors to be more responsible on future occasions and follow the call for papers. 

===== Reference to the call for papers of the main track: =====
> We strongly value reproducibility as an integral part of scientific quality assurance. Therefore, we require that all submissions are accompanied by a link to an open-source repository providing an implementation (if empirical results are part of the paper).

===== Reference to the call for papers for the workshop track: =====
> We strongly encourage you also to submit the reproducibility checklist and open up your source code and data. However, this is not required for this track. Nevertheless, we will give reproducibility badges to all accepted submissions with a reproducibility checklist, open-source code and open-access data.

Reviews: review: paper_summary: paper_summary: The work discusses how to use monoids to allow batch training of classical machine learning pipelines. Different modes are discussed of how the proposed framework can be implemented and how those relate to the classical sklearn pipelines. The performance, in terms of reduced memory requirements, is validated on a few tasks, showing that the proposed framework is capable of drastically reducing memory requirements while largely preserving model accuracy.
main_review: main_review: The paper proposes an interesting change to classical ML pipelines that could be beneficial to the larger AutoML community, besides allowing for memory-efficient cross-validation. For example, the work might also have stronger implications for multi-fidelity AutoML, though the work does not discuss any AutoML related work.
review_summary: review_summary: A very dense paper, that is difficult to follow but could be of interest to the broader AutoML community.
paper_summary: paper_summary: The authors address the challenge of training and cross-validating machine learning pipelines on large datasets while limited by memory resources. By leveraging monoids and task graphs, the authors propose a method allowing efficient batch-wise data processing, thereby reducing memory overhead without significantly sacrificing performance. The approach is compatible with the scikit-learn library, making it broadly usable for the AutoML community. Experiments aim to demonstrate the method's effectiveness from various angles, showing its ability to handle large datasets on low-resource hardware setups.
main_review: main_review: Pros:
- The concept of monoids, originating from abstract algebra, is applied innovatively in the context of machine learning pipelines to enable batch-wise data processing. The associative property of monoids ensures that the final aggregation of batch results is consistent and that distributed computational resources can be leveraged efficiently due to parallelization.
- The paper is well-organized and has a clear and concise writing style.
- Ten OpenML datasets were used for evaluation. The implications of the Pandas and Spark SQL backends and partial-transform training regarding performance were sufficiently evaluated.

Cons:
- A more direct comparison with state-of-the-art methods in terms of efficiency and accuracy could further highlight the contributions of this work.
- The paper asserts compatibility with the scikit-learn API. However, detailed insights into the integration process with existing AutoML frameworks are limited. The same holds for other types of data-preprocessing operators.
review_summary: review_summary: The paper presents a novel and technically sound approach to address the challenge of training and cross-validating machine learning pipelines on large datasets within the constraints of limited memory resources. By applying monoidal frameworks alongside task graphs for efficient batch-wise data processing, the authors offer a solution that mitigates memory overhead and retains compatibility with widely used ML libraries, thus ensuring applicability within the AutoML community. The experimental evaluation is sufficient to support the author's claims regarding performance. All in all, regarding the effectiveness and relevance of the approach, I recommend accepting the paper.
paper_summary: paper_summary: The main contributions of the paper are (1) a theoretical framework based on monoids to represent the (training) operations for a collection of preprocessing methods, (2) one batched algorithm with four formal task graphs based on the framework mentioned above to optimize scheduling w.r.t. memory, (3) an open-source implementation of the algorithm, and (4) results showcasing their algorithm and the different task graphs.
main_review: main_review: The positive aspects of the paper are: (1) a sound and strong theoretical framework that is worth sharing with the community, (2) an open-source and readily usable implementation of the framework that is reliable, as shown in RQ1-RQ4, (3) contributions to an important research direction for making (Auto)ML more accessible.   

The negative aspects of the paper are: (1) some clarity issues as outlined above and (2) weak and imprecise experiments compared to what could have been possible to verify the worth of the contributions.
review_summary: review_summary: In summary, the paper has a solid theoretical foundation but weak experiments.  

Yet, I believe that the experiments (if given more space for their presentation and some additional thought for the setup) would reach the same conclusion while being much more convincing.   

Hence, I recommend accepting the paper, as most of my concerns can be resolved and are not about the proposed contribution itself.