Rémi Cuingnet

Yannik Ladegaillerie

Jérôme Jossent

Aude Maitrot

Julien Chedal-Anglay

Williams Richard

Marine Bernard

Jake Woolfenden

Emmanuel Birot

Damien Chenu

Remi Cuingnet

PortiK: A computer vision based solution for real-time automatic solid waste characterization -Application to an aluminium stream

Keywords: material recovery facilities, MRF, solid waste characterization, deep-learning, deep neural network, computer vision AI artificial intelligence cdf

come   L'archive ouverte pluridisciplinaire

Introduction 1.Need for automatic characterization

In Materials Recovery Facilities (MRFs), solid waste materials collected from the kerbside are separated into different categories by a combination of automatic and manual sorting. These separation steps are generally (1) mechanical screenings, (2) magnetic separation, (3) optical sorting, (4) then manual sorting at the end of the process. The different categories of recycling materials and their expected level of purity are often defined in contractual Minimum Technical Requirements with the end buyers and local authorities. Usual categories are plastics, aluminium cans, ferrous metal cans, newspapers, pamphlets and magazines, mixed paper and cardboard.

To be efficient in a competitive, changing, tense environment, the sorting process has to ensure a good ratio between the purity of the sorted material and its processing cost. It should also be flexible to handle new waste and new types of recyclates. Finally, the sorting process and the quality of its outcome should be controlled to meet technical requirements.

Currently, controlling sorted recyclates' purity is achieved (i) quantitatively by manually sampling and sorting waste materials at the end of sorting lines, and (ii) qualitatively with visual inspections of the baled output materials. Hence, regular and frequent waste stream characterizations are impracticable. Besides being intrusive to the sorting process, this task is time consuming and results are obtained after the characterised waste has been baled. In a nutshell, there is no solution to know in real time the waste characterization at any point of the process.

Artificial Intelligence for waste recognition

In 2012, new machine learning algorithms based on deep learning, together with the arrival of powerful graphics processing units (GPU) led to breakthroughs in artificial intelligence (AI). In particular, outstanding results were obtained by [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] in computer vision for the automatic recognition of objects in images with deep convolutional neural networks [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF][START_REF] Goodfellow | Deep learning[END_REF]. They are now even performing as well as humans on specialised visual recognition tasks [START_REF] Liu | Progressive neural architecture search[END_REF][START_REF] Yang | Learning to navigate for fine-grained classification[END_REF].

These great advances in the field of artificial intelligence led different teams to propose new methods based on computer vision to automatically recognize waste. More specifically, standard near-infrared spectrometers measurements were replaced with hyperspectral images [START_REF] Lachaize | SVM Classifier fusion using belief functions: application to hyperspectral data classification[END_REF][START_REF] Zheng | A discrimination model in waste plastics sorting using NIR hyperspectral imaging system[END_REF][START_REF] Yang | A robust classification algorithm for separation of construction waste using NIR hyperspectral system[END_REF] or even with RGB images to analyse waste (e.g. [START_REF] Adedeji | Intelligent waste classification system using deep learning convolutional neural network[END_REF][START_REF] Srinilta | Municipal Solid Waste Segregation with CNN[END_REF]. While solutions based on near-infrared sensors efficiently discriminate between different materials [START_REF] Zheng | A discrimination model in waste plastics sorting using NIR hyperspectral imaging system[END_REF]), RGB cameras have been increasingly used. Their low costs and easy setups make them valuable alternatives, leading to some automation for waste collection [START_REF] Donati | An Energy Saving Road Sweeper Using Deep Vision for Garbage Detection[END_REF]Melinte et al. 2020) and waste sorting [START_REF] Gundupalli | A review on automated sorting of source-separated municipal solid waste for recycling[END_REF][START_REF] Strollo | An AI-Based Approach to Automatic Waste Sorting[END_REF] or even to new solutions such as the smart bins that control the type of waste brought in [START_REF] White | WasteNet: Waste Classification at the Edge for Smart Bins[END_REF][START_REF] Chen | iWaste: Video-Based Medical Waste Detection and Classification[END_REF] or automatically sort the pieces of waste into different compartments [START_REF] Sheng | An internet of things based smart waste management system using LoRa and tensorflow deep learning model[END_REF].

Most solutions based on RGB images considered waste analysis as a supervised image classification problem. It consists in automatically assigning a category (among a predefined set) to a given image [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]. The classification problem is named supervised when the assignment function is selected and calibrated on a set containing images together with their expected categories. To classify waste images, [START_REF] Chu | Multilayer hybrid deep-learning method for waste classification and recycling[END_REF], [START_REF] Adedeji | Intelligent waste classification system using deep learning convolutional neural network[END_REF] and [START_REF] Toğaçar | Waste classification using AutoEncoder network with integrated feature selection method in convolutional neural network models[END_REF] used pre-trained neural networks such as the AlexNet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF], GoogLeNet [START_REF] Szegedy | Going deeper with convolutions[END_REF] or ResNet-50 [START_REF] He | Deep residual learning for image recognition[END_REF] to extract features followed by classifiers such a multi-layer perceptron or support vector machine. Unlike previous approaches, [START_REF] White | WasteNet: Waste Classification at the Edge for Smart Bins[END_REF] and [START_REF] Mao | Recycling waste classification using optimized convolutional neural network[END_REF] used end-to-end convolutional neural networks. Since many neural network architectures for the image classification problem exist in the litterature [START_REF] Dhillon | Convolutional neural network: a review of models, methodologies and applications to object detection[END_REF], some authors compared the performances of some of them to classify waste images. More specifically, [START_REF] Aral | Classification of trashnet dataset based on deep learning models[END_REF] compared the Dense-Net [START_REF] Huang | Densely connected convolutional networks[END_REF], Res-Net, Mobile-Net [START_REF] Howard | Mobilenets: Efficient convolutional neural networks for mobile vision applications[END_REF][START_REF] Sandler | MobilenetV2: Inverted residuals and linear bottlenecks[END_REF], and the Xception [START_REF] Chollet | Xception: Deep learning with depthwise separable convolutions[END_REF] architectures for the classification of images from Trashnet dataset [START_REF] Yang | Classification of trash for recyclability status[END_REF]. They obtained the best accuracies (95% and 94%) with a Dense-Net and a ResNet respectively. [START_REF] Srinilta | Municipal Solid Waste Segregation with CNN[END_REF] compared the performances of different neural network architectures for the waste classification task of 9,200 municipal solid waste images. Among the VGG-16 (Simonyan and 5/37 Zisserman 2014), ResNet-50, MobileNet V2 and DenseNet-121, the best performances were obtained with the ResNet-50 architecture with 95% accuracy. Finally, on a different dataset, [START_REF] Thanawala | An Approach to Waste Segregation and Management Using Convolutional Neural Networks[END_REF] obtained the best performances (93% accuracy) with a Mobile-Net architecture compared to with a VGG-16, Dense-Net or Google-Net architecture to classify waste images.

While their results are very promising, classifying the whole image often leads to strong constraints on image acquisition. This limitation has been overcome using object recognition algorithms (Ren et al. 2015). They automatically identify both the categories and the positions of the different pieces of wastes in images. To monitor the waste brought into a bin in real time [START_REF] Chen | iWaste: Video-Based Medical Waste Detection and Classification[END_REF] detected the motion of falling waste using an Adaptive Gaussian mixture model. Once detected, the items were classified using a hybrid model based on MobileNetV2 [START_REF] Sandler | MobilenetV2: Inverted residuals and linear bottlenecks[END_REF]) and on the action recognition network R3D [START_REF] Tran | A closer look at spatiotemporal convolutions for action recognition[END_REF]. The detection and classification can be performed jointly with a dedicated neural network. [START_REF] Sheng | An internet of things based smart waste management system using LoRa and tensorflow deep learning model[END_REF] jointly detected and classified items in the bin with an SSD neural network [START_REF] Liu | SSD: Single shot multibox detector[END_REF]. The SSD neural network was also used to detect and identify waste on the ground (Melinte et al. 2020). [START_REF] Carolis | YOLO TrashNet: Garbage Detection in Video Streams[END_REF] used YOLO [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF], another object recognition neural network to identify waste in public city areas or in places outside of town. Unlike the previous approaches, [START_REF] Donati | An Energy Saving Road Sweeper Using Deep Vision for Garbage Detection[END_REF] considered the waste recognition problem as a semantic classification problem: it consists in assigning a (waste) category to each pixel in an image.

Although these new techniques will yield major innovations in the waste management sector, some limitations still need to be overcome [START_REF] Abdallah | Artificial intelligence applications in solid waste management: A systematic research review[END_REF]. First, insufficient field data is often a major obstacle affecting the implementation and evaluation of AI systems. To the best of our knowledge, none of the mentioned approaches has used actual data from MRF. According to [START_REF] Abdallah | Artificial intelligence applications in solid waste management: A systematic research review[END_REF], another limitation is that most studies were direct applications of AI models and more efforts should be made to adapt these technologies to SWM.

Paper outline

This paper describes PortiK, a solution for automatic waste analysis on conveyors. It automatically computes stream quality evolution based on image analysis. The contribution of this paper is threefold. First, an end-to-end solution is described with all the steps necessary for the system to operate, from hardware specifications and data collection to supervisory information. Then, the overall system was validated in an operational environment. Portik monitored an aluminium stream in a material recovery facility. To the best of our knowledge, no published solution has been evaluated on real data from material recovery facilities. Finally, PortiK computes some monitoring indicators dedicated to waste management such as mass purity.

6/37

The overall system is described in section 2.1. Conveyor images acquired in a material recovery facility are analysed in real time with an object detection algorithm (section 2.2). The detection results are then transformed into different performance indicators specific to waste sorting facilities (section 2.3). To be operative, the detection algorithm has to be calibrated on a specific dataset (section 2.4). Finally, the proposed system has been evaluated in an operational environment in a MRF (section 3). Results are discussed in section 4.

Methods

Overall system description

PortiK has been designed as a solution for continuous, real-time, non-intrusive measurement of the composition of waste streams. It relies on image based waste recognition by artificial intelligence. It is composed of two subsystems: an on-site system and a suite of cloud-based services.

PortiK on-site system (figure 1) is composed of a vision system on a mechanical structure, a monitoring console and a communicating computing unit. The vision system consists of a 2464x2056 resolution colour matrix camera (JAI GO 5100C-USB) and LED lighting ramps above the conveyor. For a good trade-off between the amount of data to analyse and the image quality, the proposed solution is based on image analysis rather than video analysis. The system has been set up with a 20 mm depth of field and a 1Hz image acquisition frequency to analyse a conveyor running at 0.4 m/s with a 50% overlap between the successive images. Once acquired, the raw images are analysed in real time with an industrial computer (Intel Core I7-7700 CPU, NVIDIA Geforce GTX 1080 GPU and 32 Go RAM) (sections 2.2 and 2.3). The results are displayed on the local interface (figure 2) and sent to the remote cloud system.

For the on-site system to operate, the overall solution relies on cloud-based services to handle all the back-end operations: data management, image annotations (section 2.4), machine learning pipelines (section 2.2) and operation services including model deployment and system performance monitoring (section 2.2.4). In the computer vision literature, the problem of detecting all occurrences and locations of some objects of interest and automatically assigning them a category is either called object recognition or instance segmentation depending on location accuracy. When the position in the image is coarsely defined, usually as axis-aligned bounding boxes surrounding the objects' instances, this is called object recognition (eg. Ren et al. 2015). On the other hand, for the fine delineation of objects, the term instance segmentation (e.g. [START_REF] Silberman | Instance segmentation of indoor scenes using a coverage loss[END_REF][START_REF] He | Mask R-CNN[END_REF]) is used instead. However, precise segmentation comes at the expense of greater computational resources, both for training and for inference. It also requires fine object delineation in the training and test sets, which is time consuming. Object recognition therefore seems a good trade-off. For object recognition to be used in waste characterization, the waste stream has to be assumed countable. It should be composed of countable and separately identifiable pieces of waste as in figure 2. Note that such hypotheses do not hold for very dense fibre streams.

Object recognition model

Modern object recognition detectors address this problem in two steps. First, a features extractor convolutional neural network (CNN) sometimes called backbone architecture takes image as input and makes pertinent information available through a features map. Some usual features extractors are the Resnet [START_REF] He | Deep residual learning for image recognition[END_REF], the VGGNet (Simonyan and Zisserman 2014), the GoogLeNet [START_REF] Szegedy | Going deeper with convolutions[END_REF], the AlexNet (Krizhevsky et al.2012), the DenseNet [START_REF] Huang | Densely connected convolutional networks[END_REF]) and the MobileNet [START_REF] Howard | Mobilenets: Efficient convolutional neural networks for mobile vision applications[END_REF]. Second, surrogate regression and classification problems are solved to detect, locate and assign a category for every object of interest. More specifically, based on the extracted feature map and a large set of position proposals, a classification block detects, for each proposal, whether there is an object or not at this location and assigns a category to it. A regression block adjusts this proposed position to predict the location. Depending on the methods, the position proposals are encoded as boxes (Ren et al. 2015;Cai et al. 2029), anchors position [START_REF] Liu | SSD: Single shot multibox detector[END_REF][START_REF] Lin | Focal loss for dense object detection[END_REF], pixel position [START_REF] Redmon | You only look once: Unified, real-time object detection[END_REF], or window centres [START_REF] Tian | Fcos: Fully convolutional one-stage object detection[END_REF]. Recently, [START_REF] Carion | End-to-end object detection with transformers[END_REF] proposed a different approach based on the transformer architecture [START_REF] Vaswani | Attention is all you need[END_REF] to avoid the surrogate classification and regression of position proposals.

9/37

Choosing an object detection model comes down to choosing a feature extractor CNN and a detection method. databases. Furthermore, to be used in real time, the inference should take less than one second per image with a standard GPU card (e.g. NVidia GTX1080 or Quadro P5000). As a matter of fact, the selected detection model was a Faster R-CNN model [START_REF] Ren | Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks[END_REF]) with a ResNet-101 from the ResNet family [START_REF] He | Deep residual learning for image recognition[END_REF]) as feature extractor.

Model training

Similarly to existing deep learning object recognition approaches detailed in section 1.2, our image analysis algorithm is based on supervised learning (section 2.2). To be operative, it has to be calibrated with annotated data. This training step set the model's numerous parameters for the detection and classification to get as close as possible to the expected results. To that end, a few hundred images were acquired with the local PortiK and manually annotated as described in section 2.4. On each image bounding boxes were manually drawn around each piece of waste. The pieces of waste were then assigned categories.

Most neural networks for image recognition can be described as a stack of simple parameterized modules that roughly mimics the human vision system [START_REF] Goodfellow | Deep learning[END_REF]. Their main drawbacks are the large number of required data to properly calibrate the numerous modules' parameters. Since operations computed in the first layers are low level image processing, one may assume that these operations could be shared between different recognition problems. This is the rationale behind most transfer learning strategies. Transfer learning focuses on how to use knowledge gained by solving a different but related problem [START_REF] Yosinski | How transferable are features in deep neural networks?[END_REF][START_REF] Newcombe | Learning and transferring mid-level image representations using convolutional neural networks[END_REF][START_REF] Newcombe | Learning and transferring mid-level image representations using convolutional neural networks[END_REF] showed that the first layers of a convolutional neural network trained on large-scale annotated datasets can be efficiently used for different visual recognition tasks with limited amount of training data. [START_REF] Yosinski | How transferable are features in deep neural networks?[END_REF] further studied the transferability of the different layers of a convolutional neural network. They reached the conclusion that rather than directly transferring convolutional layers, which might cause some issues, initialising a network with transferred features from almost any number of layers and fine-tuning them can produce a boost to performance generalisation.

In this study, transfer learning was then performed by fine-tuning a model pre-trained on MSCOCO Dataset [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] . Our model was trained with the default hyper-parameters 1 using data augmentation [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF].

When training a model, there is a risk that the optimised parameters values are too specific to a particular training set of data and thus fail to predict future observations reliably. This problem is called overfitting. Hence, to ensure that decision rules have been inferred properly, it is necessary to evaluate trained models on an independent set called the test set.

Model evaluation metrics

For an object recognition algorithm, both the accuracy of the position and of the classification is to be evaluated. In practice, this evaluation is transformed into the evaluations of binary detections by (i) considering the different categories independently and (ii) by binarizing the position estimation evaluations as either correct or incorrect. The latter is done by computing matching scores between detections and true positions. The scores are then thresholded, thus classifying the detections either as correct or incorrect. For bounding box detection, the intersection over union (IoU) thresholded at 50% is often used as it corresponds to a good match [START_REF] Everingham | The Pascal Visual Object Classes (VOC) challenge[END_REF]).

The metrics used for binary detections are the precision and recall. With TP and FP the number of true positive and false positive samples, the precision is defined by: . 𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 :

= 𝑇𝑃 𝑇𝑃 + 𝐹𝑃 (1)
It quantifies how many selected items are relevant. With FN the number of false negative samples, the recall is then defined by: . 𝑟𝑒𝑐𝑎𝑙𝑙 :

= 𝑇𝑃 𝑇𝑃 + 𝐹𝑁 (2)
It answers the question: how many relevant items were detected? A standard way to combine precision and recall is the average precision, AP. It is defined as the area under the precision-recall curve. In this report, unlike [START_REF] Everingham | The Pascal Visual Object Classes (VOC) challenge[END_REF], the raw precision-recall curve was used.

As aforementioned, the mass purity estimation is based on object recognition. As a matter of fact, only the numbers of detected objects per category are used to estimate the masses and the mass proportions (section 2.3). Thus, while precision and recall are efficient at assessing the model performance, they are too strict. Error in counting only comes from the difference between the number of false negatives and the number of false positives. In other words, they compensate for each-other. The counting error is given by:

𝐶𝑜𝑢𝑛𝑡𝑖𝑛𝑔 𝐸𝑟𝑟𝑜𝑟 : = 𝐹𝑃-𝐹𝑁 𝑇𝑃 + 𝐹𝑁 = 𝑟𝑒𝑐𝑎𝑙𝑙 𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 -1 (3)
2.3. From object recognition to waste sorting indicators

Object Rate and conveyor occupancy

The first indicator estimated from the object recognition is the object rate per waste category. While this indicator may seem straightforward to compute, there are some technical difficulties to take into account. First, to deal with image overlaps, the object rate is 12/37 computed per image and then averaged. Moreover, counting all the objects in the images would result in an overestimation of the object rate. Indeed truncated objects would be counted twice on average. A simple but robust way to unbias the estimation is to weight truncated objects by 0.5.

The object recognition results make it also possible to estimate the conveyor occupancy and the waste distribution over the conveyor width. These indicators are keys to monitor that the sorting machines operate in nominal conditions. It may also help prevent jamming and detect major dysfunctioning.

From vision to mass

So far, waste flows are estimated in terms of number of pieces of waste. To take another step forward, an easy to implement method is proposed to convert detection information into mass information. The goal is to (i) estimate the mass flow rate and the mass purity rate of solid waste, and to (ii) associate estimations with confidence intervals for reliability.

The only approach found in the literature that proposes to estimate the mass of an object from an image is by [START_REF] Standley | Image2Mass: Estimating the Mass of an Object from Its Image[END_REF]. In a nutshell, the mass is directly regressed on the image. Although such an approach might be very promising, it would require a large database of images of pieces of waste together with their corresponding weights. This is too important a limitation for it to be used in practice in material recovery facilities right now.

Rationale and hypotheses

The proposed process is both simple and efficient with only a slight additional cost in terms of data acquisition. For each category of interest, only the number of objects is assumed to be known. To be consistent with this hypothesis, the waste stream must be composed of countable and separately identifiable pieces of waste. Such information could result from an object recognition algorithm (section 2.2.2) or an image annotation task (section 2.4.4). The mass is then regressed on these numbers. Least square regression may seem a natural choice. However the underlying homoscedasticity assumption is not met. Therefore, an alternative based on mass statistical distribution analysis is used instead. It comes down computing a confidence interval on the mass knowing some information about its distribution. The number of pieces of waste per category being very large, their mass distributions are assumed to be normally distributed. Finally, categories are assumed to be independent.

Calibration

The first step consists in obtaining, for each waste category, information about its mass distribution: mean and standard deviation. As weighing each piece of waste individually is too cumbersome a process to be accepted by end-users in material recovery facilities, 13/37 objects were weighed by batches . The input data for calibration is S sample analyses (at least five) with, for each sample s, (i) the number n s of pieces of waste and (ii) the total mass w s per category. Categories are treated independently. To take into account the uncertainty about the estimations, a Bayesian approach detailed in (Cuingnet 2021) is followed. As a result, for a single category, given the sample analyses, with a Jeffrey's noninformative prior, the posterior predictive of the mass W of n (new) objects follows a non-standardized Student t-distribution with S degrees of freedom as defined in equation ( 4).

𝑊

where

𝑁 : = 𝑠=1 𝑆 ∑ 𝑛 𝑆 (5) µ : = 1 𝑁 𝑠=1 𝑆 ∑ 𝑤 𝑠 (6) 𝛽 𝑆 : = 1 2 𝑠=1 𝑆 ∑ 𝑤 𝑠 -𝑛 𝑠 •µ 𝑛 𝑠 ( ) 2 (7)
Note that ( is the mean and is the square of the scale parameter.

𝑛 • µ) 𝑛 𝛽 𝑠 𝑆/2 (1 + 𝑛/𝑁) ( )

Inference

The Bayesian approach allows for the computation of the posterior predictive distribution, the distribution of possible unobserved values conditional on calibration (equation ( 4)). Thus, predicting the mass from the number of pieces of waste (per category) comes down to estimating the quantile of the posterior predictive distribution. The 2.5 th and the 97.5 th percentiles give the 95% confidence interval. As for the stream composition or purity, it requires computing the quantile of the ratio distribution W c / W A between the mass of contaminants W C and the mass of aluminium cans W A . Estimating the quantile of ratio distribution can be carried out by inverting the cumulative distribution function (cdf) with numerical inversion such as the secant method. Similarly to [START_REF] Curtiss | On the distribution of the quotient of two chance variables[END_REF]

(0) = 1 2 - 1 π 0 ∞ ∫ 𝐼𝑚 φ 𝐶 𝑡 ( )•φ 𝐴 -𝑟𝑡 ( ) [ ] 𝑡 𝑑𝑡 (8)
where 𝜑 C and 𝜑 A are the characteristic functions of W C and W A respectively. This integral was numerically evaluated with Gauss-Kronrod quadrature formula implemented in the QUADPACK library [START_REF] Piessens | QUADPACK: A subroutine package for automatic integration[END_REF].

The width of the confidence interval comes from both the spread of the mass distribution and the lack of information on this distribution (uncertainties). The spread of the mass ratio distribution depends on several factors including the conveyor monitoring duration and the stream purity. The longer the monitoring is, the more accurate the estimation is. As for the stream purity, the closer it is to 100% (or 0%), the more concentrated the distribution is. The amount of information on the mass distribution mainly depends on the number of sample analyses used for calibration and on the sampling duration. Increasing the number of sample analyses improves the estimation of the mass variance. As for the sampling duration, the longer the sampling duration is, the more objects are sampled and weighed. As a result, the more accurate the estimation of the mean is.

In a nutshell, for each inference, it is necessary to (i) compute the parameters of the posterior predictive distribution (equation ( 4)) and (ii) approximate the 2.5 th and 97.5 th percentiles of the ratio distribution by numerically inverting equation ( 8) with the secant method.

Data collection 2.4.1. Image Annotation

PortiK is based on supervised object recognition. Thus, annotated image data are required both for training and evaluation (sections 2.2.3 and 2.2.4). In this context, image annotation consists in first drawing axis-aligned bounding boxes surrounding the pieces of waste. Then a category called label (for example: "aluminium can" or "contaminant") is assigned to each of them.

How many images?

A recurring question in applied supervised learning is about the amount of data needed. How fast a supervised system learns? In statistical learning, this is called the rate of convergence. Knowing the rate of convergence may be critical for sizing such a system. Unfortunately, as stated in [START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF]) (Theorem 7.2) universal rate of convergence guarantees do not exist: it depends both on the model and on the data.

Although there are no statistical means of sizing the training set, a commonly accepted heuristic is to consider that, given a model and a detection task (e.g. detecting aluminium 15/37 cans and contaminants), the required amount of data is quite stable. For image classification, a rule of thumb is to start with about 1,000 training images per label (Google AutoML Vision Documentation). The overall idea is to get a representative sample of all the possible appearances. Note that, in computer vision, the appearance also depends on the items' backgrounds. For object detection, one can adapt this heuristic and start with about 1,000 object occurrences for each label.

Once trained, the performances of object recognition models are estimated empirically on an independent test set. While the required size of training sets cannot be mathematically estimated, sizing test sets is possible. As described in section 2.2.4, most metrics used to assess the models' performances are calculated from the outcome of a series of independent success-failure experiments (Bernoulli trials). Therefore, methods for binomial proportion confidence interval estimation [START_REF] Newcombe | Learning and transferring mid-level image representations using convolutional neural networks[END_REF]) can be used to estimate the required size of the test set. For instance, based on the Wilson score interval with continuity correction, if the estimated probability is 90%, at least 3,556 sampled objects (resp. 913) will be required for the estimation error to be lower than 1% (resp 2%) with 95% of confidence (cf figure S1 in supplementary materials).

Mass information

To predict the mass related indicators from image analyses, detections of pieces of waste are converted into a mass estimation following the approach described in section 2.3.2. This approach requires some mass information for each waste category. To gather such information, the standard sampling and characterization process was adapted. In material recovery facilities, the current process consists in taking a sample of a waste stream from a conveyor then manually sorting the waste into different categories. Once sorted, the waste is then weighed category per category. The number of categories depends on the local legislation and/or contract; it ranges from a dozen to a few dozen. To get the required information, a counting step was added. Thus, before weighing the waste, the number of pieces were counted.

Experiments and results

To evaluate the solution in an operational environment, PortiK device has been installed in an MRF in the London area. More specifically, it monitored an aluminium can stream just before the picking room. For this waste stream, any items other than aluminium cans are considered as contaminants.

16/37

3.1. Materials

Annotated images

A first set of 678 images with 7,404 pieces of waste was acquired by the PortiK device in Decembre 2018. To ensure that the images were representative of the monitored flow, they were randomly selected and the position of the device was fixed throughout the experiments. Two categories were considered for detection: "aluminium can" (main stream) and "contaminant". Hence, the annotation tasks consist in drawing bounding boxes around each piece of waste and assigning it a binary category. These tasks were performed by waste characterization specialists. To assess the feasibility of having the annotation performed by non-specialists of waste characterization, an external company specialised in image annotation performed the same tasks on a subset of 100 images.

A second dataset composed of 99 images with 1,308 pieces of waste acquired in September 2019 was used as a test set to assess the evolution of the performances.

Waste samples

For the mass data acquisition, five one-minute samples were taken from the monitored conveyor and manually sorted in November 2019. Once sorted, the waste materials were counted and weighed category per category. This dataset was used to calibrate the mass estimation method (section 2.2.3). A second batch of seven other one-minute samples was taken between 22nd June and 2nd July 2020. Unlike the previous five samples, these were precisely timed so as to be compared with PortiK measurements. The waste composition estimated from these 12 samples is detailed in table 1.

Annotation

How long does it take?

Building datasets with ground truths is key to machine learning based approaches: they are required both for training and evaluation. In this study, a total of 8,712 pieces of waste from 777 images were both located using bounding boxes and labelled as either aluminium cans or contaminants. While drawing the bounding boxes arounds the pieces of waste took, on average, 7.9 seconds per item, assigning them a binary class took less than a second per item (0.95s). This corresponds to approximately 2h40 for 100 images. To assess the feasibility of having the annotations performed by non-specialists of waste characterization, the annotations performed by operators were compared to those done by an external company. When performed by the external company, the annotation tasks took much longer both for bounding box drawing (22 seconds per object) and object labelling (5.3 seconds per object). As for the annotations' quality, results are presented in table Table 2. Annotation errors can come from both the segmentation and labellisation. For the segmentation of 1,063 segmented objects, a precision level of 95% and recall level of 90% was achieved. When taking the labels into consideration as well, the scores dropped for most categories as they require more specific waste knowledge.

3.3. Object recognition for an aluminium stream 3.3.1. From standard detection performance to counting error Among the 678 annotated images, approximately 80% (535 images with 5,770 objects) were used to train the object detection model (section 2.2.2). The other 143 images were used to evaluate the performances. The inference time was 137 ± 6 ms per image. Object detection performances are summarised in Table 3. Figure 2 shows some sample results. For the aluminium cans, the precision and recall were 91.2% and 90.3% respectively, resulting in an underestimation of the number of aluminium cans by less than 1%. As for the contaminant group, the performances were lower. The precision and recall were 80.2% and 78.4% respectively. Since the precision and recall are close, false positives and false negatives offset each other, resulting in an underestimation of the number of contaminants by 2.2%. All the test images with overlaid detections compared to the ground truths are available in a video in the supplementary materials.

Influence of the number of training images

To assess the influence of the number of training images, the model was also trained on a smaller dataset of 242 images (2,797 objects). In the following p-values are computed with Pearson's chi-squared test.

For the "aluminium can" category, the average precision was 93.40%. The precision was 90.7% with a 95% confidence interval of [87.7% -93.1%]. The recall was 89.0% with a 95% confidence interval of [85.8% -91.6%]. This corresponds to a counting error of -1.9%. Compared to the model with the full dataset, the performance drop was not significant: p-values of 0.78 and 0.46 for precision and recall respectively. As for the "contaminant" category, the average precision was 75.9%. The precision and recall with their 95% confidence intervals were 76.8% [72.3% -80.7%] and 79.6% [75.3% -83.4%] respectively. This corresponds to a counting error of 3.8%. Compared to the model with the full dataset, the performance drop was not significant: p-values of 0.18 and 0.64 for precision and recall respectively.

19/37

Influence of the waste distribution on the belt

Object detection approaches are sensitive to occlusion, which happens in this case when objects are overlapping. To assess this dependence, the precision and recall were evaluated as a function of the mean intersection over union (IoU) between objects per image. Results are presented in figure 3. The recall significantly decreased when the mean IoU increased for both categories with a Spearman correlation R coefficient of -97.2% and -94.4% for the "aluminium can" and the "contaminant" respectively (p-value< 0.001) . While the precision of the contaminant also significantly decreased when the mean IoU increased (R = -88.8%, p-value < 0.001), the precision decrease for the aluminium can category was not significant (R = -10.5%, p-value = 0.25). Note that when correlating the performance with the number of objects per image, the correlation coefficients were lower. For the "aluminium category" the correlation coefficients were -61.2% with the precision and -46.1% with the recall. As for the contaminant category, the correlation coefficients were 26.6% for the precision and -57% for the recall.

21/37

Performance drift overtime

To assess the performance drift after several months, the model trained on the first dataset was evaluated on the second dataset consisting of 99 images acquired nine months later, in September 2019 (table 3). Let t 0 be the date of the first dataset and t 1 the date of the second dataset.

For the aluminium cans, the precision dropped from 91.2% at t 0 to 86.1% at t 1 (p-value = 0.004). The recall dropped from 90.3% at t 0 to 83.8% at t 1 (p-value < 0.001). This yielded an underestimation of the number of aluminium cans increasing from 1% to 2%. While the performance loss in terms of precision was significant, the impact on the counting error was rather low.

As for the contaminant group, the precision dropped from 80.2% to 75.1% precision (p-value = 0.043) and the recall dropped from 78.4% to 65.4% (p-value < 0.001) at t 1 . The precision remained stable while the recall dropped significantly. This yielded a 12.8% underestimation of the contaminants at t 1 while the underestimation at t 0 was 2.2%. The performance drift could be due to different factors such as (i) change in the waste stream composition, (ii) denser waste stream with more overlapping pieces of waste or (iii) a change in the object appearance with for instance change in packaging.

To assess any change in the waste composition, the contaminants' composition was analysed by classifying them into the following categories: "glass", "aluminium aerosol", "Tetra Pack", "aluminium foil", "plastic film", "metallized film", or "other". The evolution of the composition is presented in table 4. The maximum difference occurred for the "other contaminant" with a 5.3% decrease. According to the Chi-square goodness of fit test, the change in distribution was significant (p < 0.001). In a worst case scenario where categories with increasing proportions have null precisions and recalls, such a change in the distribution would have made precision drop from 82.0% to 75.4% and recall drop from 78.4 % to 70.4%. Hence, it is unlikely that the change in distribution alone was the cause of the drop in performance.

22/37

As mentioned earlier (section 3.3.3), the amount of overlap also has an impact on performance. As a matter of fact, the average mean intersection over union per image had slightly decreased between t 0 (average: 0.92%; standard deviation: 0.87%) and t 1 (average: 0.88%; standard deviation: 0.72%). The evolution of the overlapping rate between t 0 and t 1 cannot explain the performance drop. PortiK mass purity estimator was calibrated as described in section 2.2.3 with the first batch of five one-minute samples and evaluated on the second batch of seven one-minute samples. Results are presented in figure 4. The true values were always within the estimated confidence interval, which is promising regarding the validity of our approach. Note that the width of the confidence interval depends on different factors including the sample duration. This was confirmed by the aggregation of the seven sample analyses, which was equivalent to a single seven-minute sample. The 95% confidence interval width wass then much tighter. The width of the 95% confidence interval of the mass purity estimation of aluminium can is computed varying the stream purity and the conveyor analysis duration. Results are presented in figure 5. For instance, for a mass purity around 50%, the result of an analysis with PortiK calibrated with the five one-minute samples would be precise up to ±7% after 5 minutes of monitoring. The result gets more and more precise the longer the analysis lasts: up to ±5% after 8 hours. Note that the confidence of an estimation varies dramatically depending on the stream composition.

23/37

Based on the five original samples, sample analyses were simulated to estimate the influence of their numbers and of their sizes. To show the feasibility of such study, results are presented in the supplementary figures S2 and S3 (supplementary materials). Note that the intervals are wider than in figure 5 because of the uncertainty in the sample simulation. It shows that for small numbers, increasing the number of sample analyses dramatically improves the estimation. Similarly, when small, increasing the samples' sizes strongly reduces the width of the confidence interval.

24/37

Discussion

Computer vision for waste characterization in MRF

Different studies demonstrated that image information could be used to efficiently discriminate between different types of waste (section 1.2). These convincing proof-of-concepts' results paved the way for the development of computer vision based solutions for SWM.

In this study, an object recognition algorithm was used to monitor an aluminium can stream in an operational environment. Aluminium cans were detected with 91.2% precision and 90.3% recall, respectively, resulting in an underestimation of the number of cans by less than 1%. For contaminants, precision and recall were 80.2% and 78.4%, respectively, giving an 2.2% underestimation.

Based on five sample analyses where pieces of waste were counted and weighed per batch, the detection results were used to estimate the mass purity. A confidence level on the estimation was also given. In a nutshell, the purity was estimated with an error within ±7% after 5 minutes of monitoring and ±5% after 8 hours. This study showed that PortiK allows the operator to get a non-intrusive real time analysis of a waste stream. These performances are promising baselines and are expected to be outperformed by new image analysis solutions to come.

25/37 4.2. Factors affecting performance 4.4.1. Category to detect

The estimation accuracy depends on different factors. The proposed solution consists of a supervised object detection followed by some statistical analyses. The performance of the detection is affected by many factors. First of all, the category to detect has a major impact on the detection precision and recall. In this study, the "aluminium cans" were better detected than the "contaminants". This was probably due to a greater variability in appearance for the latter category.

Waste distribution over the belt

The relation between the number of objects to detect within an image and the detection performance is not straightforward. Nevertheless, this study showed that object detection significantly degrades as the overlap between objects increases. A solution to limit occlusion could be to modify the waste distribution over the belt either using a spreader or by increasing the belt speed. When increasing the belt speed, the image quality can be maintained by decreasing the exposure time and increasing the light power. However, an exhaustive analysis of the stream could then be limited by the image analysis duration. The latter was approximately 150 ms per image.

Size of the training set

Deep learning recognition parameters have a huge amount of parameters to estimate and therefore require a lot of training images when trained from scratch. In this study, a transfer learning strategy was followed by fine-tuning a model pre-trained on MSCOCO Dataset [START_REF] Lin | Microsoft coco: Common objects in context[END_REF]). Thus, overfitting was avoided even with quite a small number of images. As a matter of fact this was not very different from using the pretrained model as a feature extractor followed by linear classifiers. Nevertheless, a training dataset has to be large and representative enough for a model to capture all the possible variability. Reducing the number of images used for training from 535 to 242 made the performance lower especially for the "contaminant" class. However the decrease was not significant. Besides, with the chosen neural network architecture, more than the number of images, what matters is the number of objects. Indeed, in this study, the background being almost constant, two objects further away than the size of the receptive field could be considered as almost independent training samples.

Representativity of the training set and performance drift

Another factor that substantially affects the performance of the object detection is the representativity of the training set. This is often manifested by a performance drift over time.

In this study, at the nine-month post-training evaluation, the performances dropped significantly. The performance drift could be due to different factors such as (i) change in the 26/37 waste stream composition, (ii) denser waste stream with more overlapping pieces of waste or (iii) a change in the objects' appearances with, for instance, changes in packaging. Hence, following the evolution of the monitored waste could be of interest to detect any potential drop in performance. However such a connection is not straightforward. Therefore, monitoring the performance of the AI model is critical. Note that the representativity of the data set used for calibration is also critical for the statistical analyses part. As a matter of fact, the evolution of performances strongly depended on the category. While they remain quite stable for the "aluminium can" category, the degradation was more important for the "contaminant" category. This could be explained by the homogeneity of the aluminium cans category and the fact that it does not change much over time. On the contrary, the contaminants category is more heterogeneous and probably more subject to change in appearance over time.

Monitoring duration

The estimation error of the purity estimation comes from the counting errors, the number of samples analysis but also on the time window of the analysis. The more objects are monitored, the more accurate the purity estimation is.

Other factors such as the quality of the training/calibration data can also affect the performances of the detection.

A modular and more explainable model

As pointed out by [START_REF] Abdallah | Artificial intelligence applications in solid waste management: A systematic research review[END_REF], adoption of AI based solutions is partly slowed down by their black box nature. Indeed, the explainability of machine learning models is an active area of research (e.g. [START_REF] Guidotti | A survey of methods for explaining black box models[END_REF]. Therefore, a modular approach that limits its black box component to the object recognition model was proposed. Object recognition being a classic computer vision problem, one can benefit both from research on new models and on their explainability (e.g. [START_REF] Selvaraju | Grad-cam: Visual explanations from deep networks via gradient-based localization[END_REF]. In practice, splitting the overall approach in two different steps helped the adoption of PortiK for two main reasons. First, it helped understand the overall approach. Moreover, by displaying detection results, it allowed the end-users to qualitatively assess the solution performance. Besides acceptability, having a modular and explainable solution, also helped monitor its performance: object detection and mass estimation could thus be evaluated separately. Otherwise, the evaluation procedure would have been cumbersome and not feasible in MRF routine.

Overall cost

Adoption of new technologies in MRF is also driven by their costs. For the hardware, the main sources of costs are the camera, the lighting system and an industrial computer powerful enough to run convolution network inferences in real time. Adequate lighting must not be neglected since it strongly impacts the image quality. The most difficult costs to 27/37 estimate concerns the build, the maintenance and the performances' monitoring of the AI model. It requires building ground-truth datasets (section 2.4) both for the model calibration and for the performance evaluation. Sections 2.4.2 and 3.2 give some estimations of the required number of annotations and their durations. A few hundred images were used, which took a few hours to annotate. The model calibration usually requires a few days on a computer with a dedicated GPU. One should keep in mind that, since waste streams change with time, the calibration cannot be done once for all. Its update frequency depends on the waste streams to analyse. For the aluminium stream, the performances remained rather stable over six months.

4.5. Limitations and future work 4.5.1 Sensitivity to appearances of objects and background

The main limitation of such a computer based approach is that it is, by construction, sensitive to appearances of objects rather than to their chemical composition. Object detection consists in jointly discriminating objects from their background and labelling them based on their appearances. As a result, not only does the objects' appearances affect the performances but also the background. For instance, detecting a can over an empty conveyor is not the same problem as detecting a can in a dense news and pamphlets stream. As a result, a major limitation of such an approach is that, when changing the conveyor or the waste stream to monitor, one must at least re-evaluate the performance of the object detection and must probably retrain it.

Heavy tailed mass distribution

In this study, since the number of pieces of waste was large, the mass distribution of batches of objects was considered to follow a normal distribution. However, the masses of pieces of waste may have a heavy tailed distribution for some categories. This happens when the category of interest contains rare heavier objects. In this case, the convergence to the normal distribution is then very slow. An intuition for this slow convergence is given by the catastrophe principle: for a sum of n independent random variables X i with common distribution. Using subexponential one-tailed distributions such as the Log-normal distribution could be of interest.

Dense or Uncountable streams

The proposed approach has been designed for countable streams. It assumed that all pieces of waste on the conveyor could be counted. With some waste categories such as some paper 28/37 waste, the notion of pieces of waste are not well defined. For such cases, instead of detecting objects, semantic segmentation (e.g. [START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF]) should be used. It consists in assigning a (waste) category to each pixel. Then the second step would be either convert a surface to a mass or a surface purity to a mass purity. Note that assigning a mass estimation to each pixel of a given category is difficult since it requires knowing how much pixels' information is correlated. This is left for future work.

Conclusion

In a nutshell, this paper described an end-to-end solution based on computer vision to automatically provide the MRF operators with real time waste characterization. All the necessary steps to set-up and operate such a system were described. Information about the hardware specifications, the data collection and the automatic analysis were then given. The system was tested on an aluminium can stream. Aluminium cans were detected with 91.2% precision and 90.3% recall, respectively, resulting in an underestimation of the number of cans by less than 1%. Precision and recall obtained on the contaminants category were 80.2% and 78.4%, respectively, giving an 2.2% underestimation. Furthermore, efforts were made to transform results from off-the-shelf machine learning models into operation indicators dedicated to waste analyses such as mass purity. Based on five sample analyses where pieces of waste were counted and weighed per batch, the purity was estimated with an error within ±7% after 5 minutes of monitoring and ±5% after 8 hours. Finally the overall system and its integration were evaluated on actual data with a prototype running a facility.

Figure 1 -

 1 Figure 1 -PortiK prototype's local system and its local on-site interface as installed in a material recovery facility (London area) for purity analysis of the aluminium can stream at the entrance to the picking room. The interface showed the results of the object recognitionalgorithm together with dedicated indicators: conveyor speed, the occupancy rate, the distribution over belt, the object rate and the stream purity.

Figure 2 -

 2 Figure 2 -Results of the object recognition on two images from the aluminium stream in an MRF. Grey boxes indicate the detections of aluminium cans and red boxes the detections of contaminants.

  [START_REF] Srinilta | Municipal Solid Waste Segregation with CNN[END_REF] compared feature extractors for the waste classification task of 9,200 municipal solid waste images. Among the VGG-16 (Simonyan and Zisserman 2014), ResNet-50[START_REF] He | Deep residual learning for image recognition[END_REF], MobileNet V2[START_REF] Sandler | MobilenetV2: Inverted residuals and linear bottlenecks[END_REF]) and DenseNet-121[START_REF] Huang | Densely connected convolutional networks[END_REF], the best performances were obtained with the ResNet-50 architecture. Nevertheless, in machine learning, conclusions drawn from how a model behaves on a use case can difficulty predict precisely its behaviour on other use cases. In this study, the chosen criteria to pick a model were (i) an extensive use in the literature and state of the art performances on databases such as PASCAL VOC challenges[START_REF] Everingham | The Pascal Visual Object Classes (VOC) challenge[END_REF] and (ii) an out-of-the-shelf implementations in standard machine learning libraries (tensorflow and pytorch) with available weights from different training on standard 10/37

Figure 3 -

 3 Figure 3 -Precision and Recall as a function of the mean intersections over unions (IoU)between objects per image. The dotted line represents the 95% confidence interval.

Figure 4 -

 4 Figure 4 -Purity estimated by PortiK system (blue) for an aluminium stream upstream of the picking room compared to seven 1 minute samples manually sorted and weighed (orange). Bars in grey indicated the 95% confidence interval estimated by PortiK. The aggregation of the seven samples (SUM) is equivalent to a single sample that would have lasted 7 minutes.

Figure 5 -

 5 Figure 5 -75% quantile of the 95% confidence interval width for the aluminium mass proportion estimation as a function of the analysed time-frame duration for different target purities based on the 5 sample analyses.

Table 1 -

 1 Average waste composition of the 12 one-minute samples taken from the conveyor and manually sorted and weighed.

	Category	Mass	Quantity (count)
		kg / h	%	number / h	%
	Aluminium Cans	315.5 66.1 %	23,260 64.1 %
	Non Ferrous Metal (Non Can)	44.15 9.25 %	3,595 9.91 %
	Other Prohibited	23.75 4.98 %	2,645 7.29 %
	Aluminium Aerosols	21.00 4.40 %		1.31 %
	Glass	12.80 2.68 %		1.63 %
	Tetra Pak	12.60 2.64 %		1.10 %
	Mixed Paper	11.70 2.45 %	1,575 4.34 %
	Ferrous Metal (Non Can)	7.15	1.50 %		0.07 %
	Other Plastics	5.35	1.12 %		1.50 %
	Plastic Films (Non LDPE)	3.75	0.79 %		2.67 %
	OCC	2.85	0.60 %		0.34 %
	WEEE	2.65	0.56 %		0.04 %
	LDPE Films (Plastic Bags)	2.45	0.51 %		1.76 %
	Pots, tubs, trays & other plastic packaging	2.30	0.48 %		0.34 %
	Tissues	2.05	0.43 %		1.86 %
	News and Pams	1.10	0.23 %		0.39 %
	NPET Bottles	1.10	0.23 %		0.11 %
	Food Waste	0.85	0.18 %		0.22 %
	Wood	0.65	0.14 %		0.10 %
	Sanitary Ware	0.60	0.13 %		0.61 %
	Garden Waste	0.35	0.07 %		0.11 %
	CHDPE Bottles	0.30	0.06 %		0.04 %
	Steel Cans	0.25	0.05 %		0.01 %
	CPET Bottles	0.20	0.04 %		0.03 %
	Other paper & card	0.20	0.04 %		0.07 %
	Textiles	0.15	0.03 %		0.03 %
	NHDPE Bottles	0.10	0.02 %		0.01 %
	PP Bottles	0.05	0.01 %		0.01 %
	Steel Aerosols	0.00	0.00%		0.00 %
	PVC Bottles	0.00	0.00%		0.00 %
	Yoghurt Pots and Margarine Tubs 0.00	0.00%		0.00 %
	Soil and Rubble	0.00	0.00%		0.00 %
	Batteries	0.00	0.00%		0.00 %
	Fines less than 10mm	1.40	0.29 %		-
	Total Sample Weight (kg/min)	477.4		36,290
					18/37

Table 2 -

 2 Quality of outsourced annotation on 100 images.

	Category	Number of objects	True positives	False Negatives: missing segmentation	False Negatives: wrong label	False positive: improper segmentation	False positive: wrong label	Precision	Recall
	Segmentation only	1,063	952	111	-	45	-	95%	90%
	Aluminium cans	533	476	24	33	13	25	93%	89%
	Contaminants	530	418	87	25	32	33	87%	79%

Table 3 -

 3 Performances after nine months of a trained object detection model. The model was trained t 0 . A First evaluation was performed at t 0 and a second one was performed at t 1 . Performances are given in terms of precision, recall and counting errors.

Table 4 -

 4 Stream composition obtained from image annotations. Proportions are given in terms of number of pieces of waste.

	Category	December 2018 (t0)	September 2019 (t1)
		Overall	Proportion among	Overall	Proportion among
		proportion	contaminants	proportion	contaminants
	Glass	0.9%	2.0%	3.1%	5.9%
	Aluminium Aerosol	2.1%	4.6%	1.7%	3.2%
	Tetra Pack	2.6%	5.6%	2.1%	4.0%
	Aluminium foil	4.4%	9.4%	4.6%	8.8%
	Plastic film	4.6%	9.8%	5.6%	10.7%
	Metallized film	5.6%	12.0%	8.3%	16.0%
	Other contaminant	26.3%	56.7%	26.8%	51.4%
	Aluminium Cans	53.6%	-	47.9%	-
	3.4. Mass proportion estimation
	3.4.1. Comparison with 7 manual sample analyses

https://github.com/tensorflow/models/blob/master/research/object_detection/g3doc/tf1_detection_zoo.md 11/37

Supplementary Materials

Figure S1 -Minimum number of sample in a trial to get an estimation with a confidence interval smaller than or equal to ±1% (dashed), ±2% (dotted) and ±5% (plain).

36/37


Marie Lagrée

Antoine Mercier

Estelle Pujos-Guillot

Stéphanie Durand

Untargeted metabolomics on dried blood spots

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction Results

Mitras

Dried serum spot Serum

❖ 11% of annotated features with our databases: Amino acids and derivated, carnitines and derivated, dipeptides, phospholipids, carbohydrates.

❖ 87% of the ions detected on the DBS are common to the ions detected in the serum.

❖ Some metabolites are specifically observed in dried serum samples.

The experiment on human serum spotted on DBS cards shows that some metabolites are specifically measured in the dried serum samples => Drying the sample for 3 hours at room temperature did it change the observed metabolic profile?

Our results shows that fewer metabolites are extracted in dried serum sample, which is consistent with results from the literature [1] => Are the metabolites adsorbed on the DBS card ?

The dried blood spot is a promising novel method which required low blood volume for blood collection. This non-invasive sampling method has other advantages including feasability of patient self-sampling, collection of blood easily performed at home and facility of storage. The water/methanol extraction solvent seems to provide better results. However, the presence of macromolecules in the extracted samples could induce bias. The analysis of whole blood samples will open new opportunities for exploring intracellular metabolites present in red blood cells. This matrix provides better coverage of the metabolome compared to the plasma or serum samples [2] .

Next steps: Continue processing data acquired with VAMS & DBS sampling, continue storage stability studies at different temperatures, continue long-term storage stability studies…

Untargeted processing approach

❖ 11% of annotated features with our databases: Amino acids and derivated, carnitines and derivated, dipeptides, phospholipids, carbohydrates.

❖ 3/4 of the ions detected are common to all supports tested.

❖ the number of extracted ions is similar for all devices tested.

❖ With methanol extraction few ions are measured compared to the number of ions observed in a serum sample.

Targeted processing approach

Annotated ion peak area intensity comparaison

  Chromatograms from VAMS sampling, positive ion mode Extraction with Water/MeOH (20/80 v:v) Extraction with MeOH 100% multi charged ions (macromolecules) detected Chromatograms from DBS sampling, positive ion mode extracted samples, positive ion mode Annotated ion peak area intensity comparaison Comparaison of the extracted ions between the 2 modalities, serum and dried serum spot (Extraction A, 100 % MeOH) Comparaison of the extracted ions between the 2 modalities, VAMS and DBS (Extraction A, 100 % MeOH)

  percentage of high mass ions (m/z > 500) is measured in dried serum samples (43%) ❖ The ion m/z distribution is similar regardless of the extraction solvent (results not shown) ❖ metabolic profiles are similar whatever the extraction solvent ❖ The percentages of high mass ions (m/z > 500) measured are the same regardless of the devices (Extraction A, 100 % MeOH) ❖ Many multi-charged ions are extracted with extraction protocol B (results not shown) = > protein precipitation not effective ? ❖ As part of the targeted approach all metabolites are extracted and detected regardless of the support tested. ❖ VAMS devices show better extraction on the few targeted metabolites regardless of the extraction solvent. ❖ For the same support tested, it seems that the water-methanol extraction solvent is the most efficient ❖ The extraction yield depends on the metabolites. Carnitine is the best extracted among the target metabolites.❖ Freezing effect on the DBS cards was tested (RT vs -80°C): no significant difference was observed.❖ Similar results between the 2 extraction solvents, confirmed by the untargeted processing approach (results not shown)

This work is supported by the French Ministry of Research and National Research Agency as part of the French metabolomics and fluxomics infrastructure (MetaboHUB-ANR-INBS-0010).


Georg Ehling
email: gehling@risc.jku.at

Temur Kutsia
email: tkutsia@risc.jku.at

Matching in Quantitative Equational Theories

Quantitative equational reasoning, as introduced by Mardare, Panangaden, and Plotkin (2016), provides a framework that extends the equality predicate on terms to a notion of proximity. It allows to consider "indexed equations" s ≈ε t between terms with the idea of expressing that "s is within ε from t".

In this work-in-progress paper, we discuss matching in the setting of quantitative equational reasoning. We outline a matching algorithm for a special case and suggest possible generalizations.

Introduction

Extending the equality predicate to a relation that expresses similarity or proximity is a task that has been addressed in various ways. Among the more prominent approaches, fuzzy reasoning equips an equation with a real number between 0 and 1 that expresses the degree to which it holds true. Equational problems like matching and unification in the fuzzy setting have been studied [e.g. Ses02; JR15; Pau22; KP19; PK21].

In [START_REF] Mardare | Quantitative Algebraic Reasoning[END_REF], the authors introduce quantitative equational reasoning as a framework that extends the equality predicate to a notion of proximity in the sense of metric spaces. They consider "indexed equations" s ≈ ε t between terms with the idea of expressing that "s is within a distance of ε from t", where ε is a nonnegative rational number. They provide semantic interpretations as well as a set of inference rules for quantitative equational logic and prove a quantitative analogue of Birkhoff's theorem on the soundness and completeness of equational logic.

In this paper, we discuss matching in the setting of quantitative equational reasoning. We outline a matching algorithm for the special case where the theory is induced by a set of regular quantitative equations1 with strictly positive index, present several examples and suggest possible generalizations.

Notation and Assumptions

We assume the reader's familiarity with the basic notions of equational reasoning [e.g., see BN98]. The terminology and notation for quantitative equational reasoning used here is mostly guided by the one in [START_REF] Mardare | Quantitative Algebraic Reasoning[END_REF] and [START_REF] Bacci | Quantitative Equational Reasoning[END_REF].

To begin with, fix a signature Ω and a countably infinite set of variables X. We denote by T (Ω, X) the set of terms over Ω and X, and by Σ(X) the set of substitutions on X. Unless stated otherwise, we will use the letters a, b, c to denote constants, f, g, h for non-constant function symbols, l, r, s, t, u, v for terms and x, y, z for variables.

We will consider the quantitative equational theory U E axiomatized by a set of quantitative judgements E, as defined in [Bac+20, Section 10.4.1]. In this paper, we work under the running assumption that E is finite and unconditional, that is, that E contains exclusively judgements of the form ∅ ⊢ s ≈ ε t for s, t ∈ T (Ω, X) and ε ∈ Q ⩾0 . To keep the notation compact, we will write s

≈ ε t ∈ E instead of ∅ ⊢ s ≈ ε t ∈ E. Moreover, we will use the notation E ⊢ s ≈ ε t to express that ∅ ⊢ s ≈ ε t ∈ U E .
We collect equations from E in two separate sets, depending on whether their index is zero or positive:

E 0 = {s ≈ ε t ∈ E | ε = 0}, E + = {s ≈ ε t ∈ E | ε > 0}.
We sometimes refer to E 0 and E + as the crisp and quantitative part of E, respectively. For notational convenience, we moreover identify ≈ and ≈ 0 , i.e. we do not distinguish between E 0 and its non-quantitative counterpart

E ′ 0 = {s ≈ t | s ≈ 0 t ∈ E 0 }.
Analogous to the non-quantitative case, we say that a quantitative equation s ≈ ε t is regular if s and t contain the same variables.

Throughout the paper, we will refer to some of the rules defining quantitative algebraic theories, which can be found in [Bac+20, Section 10.4.1].

Remark 2.1. A first simple, yet important observation is that we can assume all indices of quantitative equations in our setting to be integers (since multiplying all indices by a suitable rational to cancel denominators yields a theory that behaves analogous to the original one). Thus, induction on the index is available for future proofs.

3 Matching in the Quantitative Setting

Problem Formulation

Let Ω, X and E be as above and let s, t ∈ T (Ω, X) be terms, ε a nonnegative rational number. The fixed-range quantitative matching problem s ≲ ? E,ε t (or simply s ≲ ? ε t, if E is clear from the context) consists in the following task:

(s ≲ ? E,ε t): Find a substitution σ ∈ Σ(X) such that E ⊢ sσ ≈ ε t (if such a σ exists).
A similar task, which will however not be studied in this paper, is presented by the unrestricted quantitative matching problem, where the distance is not fixed in advance:

(s ≲ ? E,? t): Find the least rational δ ⩾ 0 such that there exists a substitution σ satisfying E ⊢ sσ ≈ δ t.

First Steps Towards a Solution

In order to solve the (fixed-range) matching problem, it would be sufficient to compute all elements in the "ball" B ε (t) . . = {u ∈ T (Ω, X) | E ⊢ t ≈ ε u} and syntactically match s to each of them. However, B ε (t) need not be finite for two reasons, as illustrated by the example below:

Example 3.1. (1) Take E = {f (x) ≈ 1 g(x, y)} and t = f (a)
. Then E ⊢ f (a) ≈ 1 g(a, y) by the (Subst) rule, and thus, every instance of g(a, y) is in B 1 (f (a)), again by (Subst). In particular, B 1 (t) is infinite.

(2) Take E = {x ≈ 0 f (x)}, and let t = a be a constant. Then by the (Triang) rule, we have f n (a) ∈ B 0 (a) for every n, so B 0 (t) is infinite.

In the first example, the infinity of the ball is caused by the fact that E + allows to introduce new variables, which can be removed by imposing regularity of E + . In the second example, the problem lies in the nature of E 0 . We will see later (in Prop. 3.6) that all balls are finite if E 0 = ∅ and E + is regular. For the general case however, we should account for those problems by computing a compact representation of the ball, that is, one that is still finite but yet in some sense contains a representative of every relevant term. For the first type of problem, this means that the set we construct will only contain the non-ground generalization, but not its instances. For the second type of problem, it means that our set will only contain a representative of the term in the ball up to E 0 .

We define this compact representation of the ball as follows:

Definition 3.2. Let E = E 0 ∪ E + be such that E + is finite with integer indices and E 0 has finitary unification type. Moreover, assume that a unification algorithm for E 0 is given. Given a term t and a rational ε ⩾ 0, we define the set R ε (t) recursively by setting R ε (t) = {t} if t is a variable and

R ε (t) = {t} ∪ δ∈N, 0<δ⩽ε, t=f (t1,...,tn), si∈R δ (ti) R ε-δ (f (s 1 , . . . , s n )) ∪ l≊ δ r∈ Ē+, δ⩽ε, σ∈mcu E 0 (l,t) R ε-δ (rσ) (1)
otherwise, where "l ≊ δ r ∈ Ē+ " means that either l ≈ δ r or r ≈ δ l is a fresh variant of an equation in E + , and where mcu E0 (l, t) stands for a minimal complete set of E 0 -unifiers of l and t computed by the given algorithm.

Remark 3.3. (1) If t is ground, then R ε (t) is a finite set.
It is defined uniquely up to renaming of variables. Fixing a unification algorithm for E 0 serves the sole purpose of guaranteeing this uniqueness.

(2) As announced earlier, the idea of the above definition is to represent all terms that are ε-close to t. The first set in (1), the singleton {t}, guarantees that t itself is in the representation; this corresponds to the reflexivity rule (Refl) of quantitative equational theories. The second set makes sure that any term with the same head symbol as t whose arguments are close to those of t is close to t, reflecting the (NExp) rule. The union constituting the rest of the definition is inspired by term rewriting. Here, t is rewritten according to a rule from E + to some rσ, and we include elements that are (ε -δ)-close to rσ, since a distance of δ has been consumed by the rewriting process. We will illustrate in Example 3.5 why it makes sense to consider a unifier σ here instead of a matcher as in classical term rewriting. This part reflects the (Symm) and (Triang) rules.

Example 3.4. Consider E = {f (x, y) ≈ 0 f (y, x), f (x, y) ≈ 1 g(x, y)} and the matching problem

f (g(b, z), z) ≲ 1 f (f (a, b), a).
Let t be f (f (a, b), a) for short. We show the computation of R 1 (t) in full detail. Note that E 0 -unification between t and the right hand side of f (x, y) ≈ 1 g(x, y) fails, and for the left hand side, the minimal complete set of E 0 -unifiers depends on the choice of the E 0 -unification algorithm that was fixed beforehand. We choose here to compute R 1 (t) with respect to the unification algorithm that gives σ 1 = {x → a, y → f (a, b)} and σ 2 = {x → f (a, b), y → a} as the minimal complete set of unifiers of t and f (x, y). Then, we have

R 1 (t) = {t} ∪ u∈R1(f (a,b)) v∈R1(a) R 0 (f (u, v)) ∪ i∈{1,2}
R 0 (g(x, y)σ i ).

Since R 0 (s) = {s} holds for any term s, this simplifies to

R 1 (t) = {t} ∪ {f (u, v) | u ∈ R 1 (f (a, b)), v ∈ R 1 (a)} ∪ {g(a, f (a, b)), g(f (a, b), a)}.
We now need to compute the sets R 1 (f (a, b)) and R 1 (a). Since a cannot be unified modulo E 0 with a side of f (x, y) ≈ 1 g(x, y), we obtain R 1 (a) = {a}. As for the computation of R 1 (f (a, b)), note that the minimal complete set of unifiers of f (a, b) and f (x, y) is given by {{x → a, y → b}, {x → b, y → a}}, and we obtain

R 1 (f (a, b)) = {f (a, b)} ∪ u∈R1(a) v∈R1(b) R 0 (f (u, v)) ∪ R 0 (g(a, b)) ∪ R 0 (g(b, a)) = {f (a, b), g(a, b), g(b, a)}.
Hence, the computation gives

R 1 (t) = {t, f (g(a, b), a), f (g(b, a), a), g(a, f (a, b)), g(f (a, b), a)}.
The solution to the matching problem f (g(b, z), z)

≲ 1 f (f (a, b), a) is now found as the matcher τ = {z → a} of f (g(b, z), z) to f (g(b, a), a) ∈ R 1 (t). Example 3.5. Consider E = {f (x, y) ≈ 1 g(x), f (x, a) ≈ 1 h(x)} and the matching problem h(x) ≲ 2 g(b). We have R 2 (g(b)) = {g(b)} ∪ R 1 (f (b, y)) = {g(b), f (b, y), h(b)}
, and the solution {x → b} to the matching problem can be found as the syntactic matcher of h(x) to h(b).

Note that the presence of h(b) in R 2 (g(b)) hinges on the fact that unification was used in the definition of R ε (t): if matching had been used instead, h(b) would go missing because f (x, a) cannot be matched to f (b, y).

First Results

We now present some properties the compact representation R ε (t) of the ball of radius ε around t enjoys. Let r, s, t be terms, ε, δ nonnegative rationals. The following can be shown by wellfounded induction:

(a) R 0 (t) = {t} (b) If δ ⩽ ε, then R δ (t) ⊆ R ε (t). (c) Assume that E 0 = ∅, E + is regular and s, t are ground. Then s ∈ R ε (t) if and only if t ∈ R ε (s). Moreover, if r ∈ R δ (s) and s ∈ R ε (t), then r ∈ R δ+ε (t).
Note that these properties reflect some of the rules defining quantitative equational theories [cf. Bac+20, p. 347]. For instance, (c) reflects the (Symm) and (Triang) rules. Both conditions in (c) are necessary: For instance, if

E 0 = ∅ and E+ = {f (x) ≈ 1 g(x, y)}, then f (a) ∈ R 1 (g(a, b)), but g(a, b) ̸ ∈ R 1 (f (a)). On the other hand, if E 0 = {f (x, y) ≈ 0 f (y, x)} and E + = {g(x) ≈ 1 f (a, x)}, then g(b) ∈ R 1 (f (b, a)), but f (b, a) ̸ ∈ R 1 (g(b)).
The goal of introducing R ε (t) was to provide a compact representation of the ball B ε (t). More concretely, in the simplest scenario, this means the following: Proposition 3.6. Let E = E + be finite and regular, and let t be a ground term. Then B ε (t) = R ε (t).

Algorithm 1: Quantitative matching for empty E 0 and regular E + Input : A finite set E = E + of quantitative equations with positive index, terms s, t with t ground. Output: A complete set S of solutions to the matching problem s ≲ ?

E,ε t S ← ∅; compute R ε (t); for u ∈ R ε (t) do
S ← S ∪ {syntactic matchers of s to u} end return S Proposition 3.6 gives us an algorithm to solve the matching problem s ≲ ε t for regular E + and empty E 0 : Compute R ε (t), and syntactically match s to each of its elements.

The soundness and completeness of Algorithm 1 are direct consequences of Proposition 3.6. Note that in a practical implementation, the computation could be sped up by interlacing the computation of the representation of the ball and syntactical matching, e.g. to avoid computing elements of R ε (t) to which s cannot be matched.

Relaxing the assumptions

As seen in Example 3.1, Proposition 3.6 in general does not hold without the assumption of empty E 0 and regular E + . Let us investigate how Algorithm 1 could possibly be adapted in these cases. We examine first the case where E 0 is empty, but E + need not be regular. Recall that R ε (t) in general does not contain the ground instances of non-ground terms that arise from non-regularity. Thus, in Algorithm 1, syntactic unification needs to be employed when comparing s to the elements of R ε (t) rather than syntactic matching. This is illustrated by Example 3.7 below.

Example 3.7. Consider E = {f (x) ≈ 1 g(x, y)} and the matching problem g(x, b) ≲ ? E,1 f (a). Then R 1 (f (a)) = {f (a), g(a, y)}.

Syntactic matching of g(x, b) to elements of R 1 (f (a)) does not succeed. The solution σ = {x → a} can be found via syntactic unification of g(x, b) and g(a, y).

Considering now the case where E 0 need not be empty, recall that R ε (t) only records terms up to equality modulo E 0 . Thus, it should be expected that syntactic matching needs to be replaced by E 0 -unification in Algorithm 1:

Example 3.8. Consider E = {f (a, x) ≈ 1 g(x, a), a ≈ 0 b} and the problem f (b, y) ≲ 1 g(c, b). Then R 1 (g(c, b)) = {g(c, b), f (a, c)}.
The solution σ = {y → c} can be found as an E 0 -unifier of f (b, y) and f (a, c).

However, problems can occur in cases like the following:

Example 3.9. Take E = {f (a, x) ≈ 0 g(x), a ≈ 1 b}, and consider the matching problem f (b, y) ≲ 1 g(a). Since E ⊢ f (b, a) ≈ 1 f (a, a) ≈ 0 g(a), the substitution σ = {y → a} is a solution. However, no element of R 1 (g(a)) = {g(a), g(b)} is unifiable modulo E 0 with f (b, y).

To find the matcher, one would need to consider also R1 (f (b, y)) = {f (b, y), f (a, y)}, and note that σ is an E 0 -unifier of f (a, y) and g(a). Here, the notation R1 (f (b, y)) should express that it is not allowed to substitute for the variable y during the computation of the representation of the ball. This could be realized e.g. by first replacing y by a new free constant c y , then computing R 1 (f (b, c y )) and afterwards replacing every occurrence of c y by y again.

Outlook

While Proposition 3.6 only provides an algorithmic solution to the quantitative matching problem in the very restricted case that E 0 = ∅ and E + is regular, we hope that similar ideas can be used to solve the matching problem in a more general setting, as outlined in Subsection 3.4. Establishing the corresponding results is an obvious next step.

Possible further generalizations could include removing the restriction to unconditional equations which we imposed in this paper as well as investigating the unrestricted matching problem. Moreover, also different frameworks for quantitative equational reasoning could be considered, for instance the one that has been introduced recently by Gavazzo and Di Florio [START_REF] Gavazzo | Elements of Quantitative Rewriting[END_REF].

Acknowledgements

This contribution was written within the framework of the SQUEE project, which is supported by a grant from the Austrian Science Fund (FWF) under project P 35530. The authors wish to express their thanks to the anonymous reviewers, whose comments helped to improve the paper's quality.

An equation s ≈ε t is called regular if s and t have the same set of variables: var (s) = var (t).


Nikolai Kudasov
email: n.kudasov@innopolis.ru

Generalising Huet-style Projections in E-unification for Second-Order Abstract Syntax

Second-order abstract syntax (SOAS) provides a well-founded framework when working with languages that have arbitrary binders. E-unification for SOAS is powerful enough to encode both E-unification and higher-order unification (HOU). In a previous work, we have presented an E-unification procedure, drawing inspiration from both E-unification and HOU algorithms. In this paper, we present a work-in-progress on an more efficient version of the procedure, aiming to bring E-unification for SOAS to perform on par with HOU algorithms. More specifically, in this work we focus on a generalisation of Huet-style projections (also known as partial bindings in HOU literature), commonly used in HOU algorithms.

Introduction

Second-order abstract syntax (SOAS) [START_REF] Fiore | Second-Order Equational Logic (Extended Abstract)[END_REF] offers a mathematically sound approach to work with languages with binders. SOAS is an abstract syntax with variable bindings and parameterised metavariables. Fiore and Szamozvancev [START_REF] Fiore | Formal Metatheory of Second-Order Abstract Syntax[END_REF] have successfully used SOAS to generate metatheory in Agda for user-defined languages with variable bindings. SOAS has also been used by Makoto Hamana in his studies of second-order rewriting and Second-Order Laboratory [START_REF] Hamana | Theory and practice of second-order rewriting: Foundation, evolution, and SOL[END_REF].

In a previous work, the author [START_REF] Kudasov | Higher-order unification from e-unification with second-order equations and parametrised metavariables[END_REF][START_REF] Kudasov | E-unification for second-order abstract syntax[END_REF] has introduced E-unification for second-order abstract syntax, combining approaches from first-order E-unification [START_REF] Gallier | Complete sets of transformations for general E-unification[END_REF] and higher-order unification (HOU) [START_REF] Jensen | Mechanizing ω-order type theory through unification[END_REF][START_REF] Vukmirovic | Efficient Full Higher-Order Unification[END_REF]. Although the algorithm is sound and complete, it is not particularly efficient and several directions for improvements are outlined in the papers.

In another work, the author [START_REF] Kudasov | Functional Pearl: Dependent type inference via free higher-order unification[END_REF] has implemented a typechecking algorithm based on a (simplified) second-order abstract syntax. One of the heuristics used in that implementation resembles generalised Huet-style project bindings for untyped syntax. In this paper, we demonstrate a work-in-progress for improving the efficiency of E-unification procedure for SOAS, by attempting to generalise Huet-style projection bindings (used in many HOU algorithms [START_REF] Gérard | A unification algorithm for typed lambda-calculus[END_REF][START_REF] Miller | A logic programming language with lambda-abstraction, function variables, and simple unification[END_REF][START_REF] Duggan | Unification with extended patterns[END_REF][START_REF] Libal | Functions-as-Constructors Higher-Order Unification[END_REF][START_REF] Vukmirovic | Efficient Full Higher-Order Unification[END_REF]) in the simply-typed setting, use them to improve (project), (imitate), and (iterate) transition rules [10, Section 4.2] and cut down the search space for the unification procedure [START_REF] Kudasov | E-unification for second-order abstract syntax[END_REF]Definition 33].

x : τ ∈ Γ variables Θ | Γ ⊢ x : τ m : [σ 1 , . . . , σ n ]τ ∈ Θ for all i = 1, . . . , n Θ | Γ ⊢ t i : σ i metavariables Θ | Γ ⊢ m[t 1 , . . . , t n ] : τ F : (σ 1 .τ 1 , . . . , σ n .τ n ) → τ for all i = 1, . . . , n Θ | Γ, x i : σ i ⊢ t i : τ i operators Θ | Γ ⊢ F(x 1 .t 1 , . . . , x n .t n ) : τ
2 E-unification for Second-Order Abstract Syntax

Second-Order Abstract Syntax

Second-order abstract syntax [3, Section 2] consists of 1. A signature Σ, defining the set of types T and available operators. Each operator F has an arity (σ 1 .τ 1 , . . . , σ n .τ n ) → τ , that specifies a return type τ and, for each argument, types of bound variables σ i introduced in that argument, and the type τ i of the argument itself.

2. Typing contexts Ξ | Γ, where Ξ defines the types of parametrised metavariables and Γ specifies the types of regular variables. For each metavariable typing m : [σ]τ , we specify the types of all parameters σ as well as the return type τ .

3. Terms that are given by the rules in Fig. 1.

An equational presentation [3, Section 5] is a set of axioms each of which is a pair of terms in context. Example 1. A signature for simply-typed λ-calculus with pairs over a set of base types A consists of:

1. a set of types A ⇒,× given by

τ ∈ A τ ∈ A ⇒,× σ, τ ∈ A ⇒,× σ ⇒ τ ∈ A ⇒,× σ, τ ∈ A ⇒,× σ × τ ∈ A ⇒,×

a family of operators for all

σ, τ ∈ A ⇒,× abs σ,τ : σ.τ → (σ ⇒ τ ) (abstraction) app σ,τ : (σ ⇒ τ , σ) → τ (application) pair σ,τ : (σ, τ ) → σ × τ (pair constructor) fst σ,τ : σ × τ → σ (first projection) snd σ,τ : σ × τ → τ (second projection)
Example 2. The equational presentation of the simply-typed λ-calculus with pairs:

m : [σ]τ , n : []σ | • ⊢ app(abs(x.m[x]), n[]) ≡ m[n[]] : τ (β λ ) m : []σ, n : []τ | • ⊢ fst(pair(m[], n[])) ≡ m[] : σ (β π1 ) m : []σ, n : []τ | • ⊢ snd(pair(m[], n[])) ≡ n[] : τ (β π2 ) m : []σ ⇒ τ | • ⊢ abs(x.app(m[], x)) ≡ m[] : σ ⇒ τ (η λ ) m : []σ × τ | • ⊢ pair(fst(m[]), snd(m[])) ≡ m[] : σ × τ (η × )
2.2 E-unification procedure for SOAS E-unification problems for SOAS are about finding metavariable substitutions satisfying a collection of second-order constraints (i.e. equalities of second-order terms):

Definition 1 ([10, Definition 8]). Given an equational presentation E, an E-unification problem ⟨Θ, S⟩ is a finite set S of second-order constraints in a shared metavariable context Θ. We present an E-unification problem as a formula of the following form:

∃(m 1 : [σ 1 ]τ 1 , . . . , m n : [σ n ]τ n ).(∀(z 1 : ρ 1 ).s 1 ? = t 1 : τ 1 ) ∧ . . . ∧ (∀(z k : ρ k ).s k ? = t k : τ k )
Here is an example of E-unification problem for simply-typed λ-terms:

∃(m : [σ ⇒ τ , (σ ⇒ τ ) ⇒ τ ]τ ). ∀(g : σ ⇒ τ , y : σ). m[g, abs(x.app(x, y))] ? = app(g, y) : τ
An E-unification procedure introduced in a previous work [START_REF] Kudasov | E-unification for second-order abstract syntax[END_REF] consists of a collection of transition rules that are applied non-deterministically: Definition 2 ([10, Definition 33]). The E-unification procedure over an equational presentation E is defined by repeatedly applying the following transitions (non-deterministically) until a stop:

1. If no constraints are left, then stop (succeed).

2. If possible, apply (delete) rule.

3. If possible, apply (mutate) or (decompose) rule (non-det.).

4. If there is a constraint consisting of two non-metavariables and none of the above transitions apply, stop (fail). We refer the reader to [10, Section 4] for the full description and examples of the transition rules. Importantly, all of these rules rely on exact matching with axioms (in particular, computation rules of a given language), use type information superficially, resulting in a small-step advancements towards a solution. For example, constraint app(app(m[], t 1 ), t 2 ) ? = r will perform two (mutate) rules to first figure out substitution m[] → abs(x 1 .abs(x 2 .m 2 [x 1 , x 2 ])) and get to solving m 2 [t 1 , t 2 ] ? = r. Furthermore, without relying on the types of t 1 , t 2 , and r parameters, the procedure has to fallback to trial and error in figuring out how to use t 1 , t 2 to produce r. Huet-style projection [START_REF] Gérard | A unification algorithm for typed lambda-calculus[END_REF], explicitly avoided in the these transition rules, relies on the types of the arguments of a metavariable, to properly eliminate them in a single step. Instead, the procedure relies only on Jensen-Pietrzykowski-style (JP-style) [START_REF] Jensen | Mechanizing ω-order type theory through unification[END_REF], which simply selects the parameter to be used, but defers proper elimination (e.g. application to arguments) to other parts of the procedure.

3 Generalising Huet-style projection

Huet-style projection

We start with a formal definition of Huet-style projection bindings for first-order syntax: Definition 3. Let m : α 1 ⇒ . . . ⇒ α n ⇒ β and for some i, α i = γ 1 ⇒ . . . ⇒ γ m ⇒ β such that n > 0 and m ≥ 0. Then a first-order Huet-style projection binding is a substitution

m → λx.x i (h 1 x) . . . (h m x)
where the metavariables h are fresh and bound variables x are of appropriate types (note that i in x i and α i is the same).

In a higher-order unification procedure, this binding can be used whenever we want to use one of the parameters of a metavariable directly to produce the desired term. For example, consider the following unification problem:

m (λx.x y) f ? = f y H-project -→ (λx 1 x 2 .x 1 (h 1 x 1 x 2 )) (λx.x y) f ? = f y via [m → λx 1 x 2 .x 1 (h 1 x 1 x 2 )] -→ * β (h 1 (λx.x y) f ) y ? = f y decompose -→ (h 1 (λx.x y) f ) ? = f JP-project -→ ((λx 1 x 2 .x 2 ) (λx.x y) f ) ? = f via [h 1 → λx 1 x 2 .x 2 ] -→ * β f ? = f
Let us recognise the following components of Definition 3:

1. The type of i-th parameter (α i ) determines if this parameter can be used to extract the result of type β. Note that

γ 1 ⇒ γ 2 ⇒ β = γ 1 ⇒ (γ 2 ⇒ β)
, which means, that we may need to go deep into the structure of the type α i to understand if it contains the type β, moreover, if β appears in a position that is suitable for extraction (a positive position for function types).

2. The type of m specifies the parameters as well as the return type. The usual assumption is that β is not itself a function type. We use the parameter types to introduce as many parameters as needed using λ-abstration.

3. The structure of the type of i-th parameter tells us how to eliminate it using a proper number of arguments to extract a term of type β.

4. Each argument used in the elimination of x i : α i is a fresh metavariable with the same parameters as the original metavariable. The arguments are added using function application (represented by juxtaposition) which is the eliminator for function types.

Adding product types

Let us add product types, pairs of terms, and pair projections to the simply typed λ-calculus:

1. For all types σ, τ , we add the product type σ × τ .

2. If t 1 : σ and t 2 : τ are terms, then ⟨t 1 , t 2 ⟩ : σ × τ is a pair.

3. If t : σ × τ , then π 1 t : σ and π 2 t : τ are the first and second projections, respectively.

Consider the constraint m ⟨λx.x y, f ⟩ ? = f y Assuming f : σ ⇒ τ and y : σ, the type of the only parameter to m is (

(σ ⇒ τ ) ⇒ τ ) × (σ ⇒ τ ).
It is clear that we should can extract both components with π 1 or π 2 projections. In particular, a binding that will lead to a unifier for this constraint looks as follows:

m → λx 1 .π 1 x 1 (h 1 x 1 )
We observe the following from this example:

1. The type of a parameter to m determines whether it can be used to extract the result of appropriate type.

2. The structure of the parameter type tells us how to eliminate it. However, unlike the case of function types, we now have two eliminators: π 1 and π 2 .

To generalise Huet-style projection bindings to include product types, we define the set of possible formulas on the right hand side recursively over the type of i-th parameter of the metavariable.

1. rhs x,β (t, β) = {t} 2. rhs x,β (t, δ) = ∅ when δ ̸ = β and δ is not a function or product type

3. rhs x,β (t, γ ⇒ δ) = rhs x,β (t (h 1 x), δ) where h 1 : α 1 ⇒ . . . ⇒ α n ⇒ γ is fresh 4. rhs x,β (t, δ 1 × δ 2 ) = rhs x,β (π 1 t, δ 1 ) ∪ rhs x,β (π 2 t, δ 2 )
The set of possible Huet-style projection bindings for metavariable m :

α 1 ⇒ . . . α n ⇒ β at position i is defined as {[m → λx.s] | s ∈ rhs x,β (x i , α i )}
The cases 3 and 4 above stem from the canonical values for function and product types and the following computation rules for simply-typed λ-calculus with pairs:

(λx.m) n -→ [x → n]m (β λ ) π 1 ⟨m, n⟩ -→ m (β π1 ) π 2 ⟨m, n⟩ -→ n (β π2 )
This suggests that a generalisation of Huet-style bindings is possible based on the set of type constructors and the set of axioms E as given in Example 2.

Generalising to SOAS

We now consider a generalisation of Huet-style projection bindings for an arbitrary second-order abstract syntax. First, assume that m : [α 1 , . . . , α n ]β. Let x : α 1 , . . . , x n : α n . Then we define the set of right-hand side formulas rhs x,β recursively as follows:

1. rhs x,β (t, β) = {t} 2. rhs x,β (t, δ) = ⟨l,ξ⟩∈L rhs x,β ([y → t]ξl, ε) where L = {⟨l, ξ⟩ | ∃(Θ | • ⊢ s : δ).(Θ | • ⊢ [y → s]l ≡ r : ε) ∈ E}
and each l ̸ = y and each ξ instantiates l in the appropriate context by substituting each metavariable with a fresh one 3. rhs x,β (t, δ) = ∅ otherwise Intuitively, the set L in case 2 specifies all possible contexts where we could put a term of type δ such that one of the axioms (e.g. computation rules) will fire. Note that we are not looking at the term t to find such contexts, only its type. For example, if delta = σ ⇒ τ and we work in λ-calculus, then the first axiom in Example 2 has a proper subterm of this type, which means that rhs x,τ (t, σ ⇒ τ ) = {app(t, n[x])} where n : [α 1 , . . . , α n ]σ is a fresh metavariable.

The set of generalised Huet-style projection bindings for metavariable m : [α 1 , . . . , α n ]β at position i is defined as

{[m[x] → s] | s ∈ rhs x,β (x i , α i )}
Note that such sets of binding can be precomputed for a given set of types T and axioms E. Once computed, it is possible to use Huet-style bindings to cut down the search space for the E-unification procedure. In particular, the (project), (imitate), and (iterate) transition rules may be improved.

Intutively, the improvement comes from the fact that we perform a substitution that brings us as much as possible to the application of the (mutate) rule, instead of guessing which path will work.

Conclusion

We have described an approach to generalise Huet-style bindings and sketched a way those can be used to reduce the search space for the E-unification procedure for second-order syntax, making a step towards an efficient E-unification procedure. It remains to properly update the procedure, formalising conditions when Huet-style projections must be utilised (we expect it to be similar to full HOU procedure by Vukmirovic, Bentkamp, and Nummelin [START_REF] Vukmirovic | Efficient Full Higher-Order Unification[END_REF]). It would also be good to see the theoretical performance improvement confirmed with an implementation and benchmarking, especially in comparison with the existing implementations of HOU not based on SOAS.

Figure 1 :

 1 Figure 1: Second-order terms in context.