Permutive

permutive

Authors:
(1) Sebastian Dziadzio, University of Tübingen (sebastian.dziadzio@uni-tuebingen.de);
(2) Çagatay Yıldız, University of Tübingen;
(3) Gido M. van de Ven, KU Leuven;
(4) Tomasz Trzcinski, IDEAS NCBR, Warsaw University of Technology, Tooploox;
(5) Tinne Tuytelaars, KU Leuven;
(6) Matthias Bethge, University of Tübingen. Table of Links Abstract and 1. Introduction 2. Two problems with the current approach to class-incremental continual learning 3. Methods and 3.1. Infinite dSprites 3.2. Disentangled learning 4. Related work 4.1. Continual learning and 4.2. Benchmarking continual learning 5. Experiments 5.1. Regularization methods and 5.2. Replay-based methods 5.3. Do we need equivariance? 5.4. One-shot generalization and 5.5. Open-set classification 5.6. Online vs. offline Conclusion, Acknowledgments and References Supplementary Material 4. Related work 4.1. Continual learning Continual learning literature typically focuses on catastrophic forgetting in supervised classification. Parameter isolation methods use dedicated parameters for each task by periodically extending the architecture while freezing already trained parameters [33] or by relying on isolated subnetworks [6]. Regularization approaches aim to preserve existing knowledge by limiting the plasticity of the network. Functional regularization methods constrain the network output through knowledge distillation [17] or by using a small set of anchor points to build a functional prior [26, 36]. Weight regularization methods [39] directly constrain network parameters according to their estimated importance for previous tasks. In particular, Variational Continual Learning (VCL) [25] derives the importance estimate by framing continual learning as sequential approximate Bayesian inference. Most methods incorporate regularization into the objective function, but it is also possible to implement it using constrained optimization [2, 10, 13, 22]. Finally, replay methods [4, 12, 30, 32] retain knowledge through rehearsal. When learning a new task, the network is trained with a mix of new samples from the training stream and previously seen samples drawn from the memory buffer. A specific case of this strategy is generative replay [3, 34], where the rehearsal samples are produced by a generative model trained to approximate the data distribution for each class. Many continual learning methods are hybrid systems that mix and match the above techniques. 4.2. Benchmarking continual learning Established continual learning benchmarks primarily involve splitting existing computer vision datasets into discrete, nonoverlapping segments to study continual supervised classification. Notable examples in this domain include split MNIST [39], split CIFAR [39], and split MiniImageNet [1, 4], along with their augmented counterparts, such as rotated MNIST [22], and permuted MNIST [15]. More recently, contributions from Lomonaco and Maltoni [20], Verwimp et al. [38] and Roady et al. [31] have enriched the field with dataset designed specifically for continual learning, such as CORe50, CLAD, and Stream-51, which comprise temporally correlated images with diverse backgrounds and environments. This paper is available on arxiv under CC 4.0 license. Authors: (1) Sebastian Dziadzio, University of Tübingen (sebastian.dziadzio@uni-tuebingen.de); (2) Çagatay Yıldız, University of Tübingen; (3) Gido M. van de Ven, KU Leuven; (4) Tomasz Trzcinski, IDEAS NCBR, Warsaw University of Technology, Tooploox; (5) Tinne Tuytelaars, KU Leuven; (6) Matthias Bethge, University of Tübingen. Authors: Authors: (1) Sebastian Dziadzio, University of Tübingen (sebastian.dziadzio@uni-tuebingen.de); (2) Çagatay Yıldız, University of Tübingen; (3) Gido M. van de Ven, KU Leuven; (4) Tomasz Trzcinski, IDEAS NCBR, Warsaw University of Technology, Tooploox; (5) Tinne Tuytelaars, KU Leuven; (6) Matthias Bethge, University of Tübingen. Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 2. Two problems with the current approach to class-incremental continual learning 2. Two problems with the current approach to class-incremental continual learning 3. Methods and 3.1. Infinite dSprites 3. Methods and 3.1. Infinite dSprites 3.2. Disentangled learning 3.2. Disentangled learning 4. Related work 4. Related work 4.1. Continual learning and 4.2. Benchmarking continual learning 4.1. Continual learning and 4.2. Benchmarking continual learning 5. Experiments 5. Experiments 5.1. Regularization methods and 5.2. Replay-based methods 5.1. Regularization methods and 5.2. Replay-based methods 5.3. Do we need equivariance? 5.3. Do we need equivariance? 5.4. One-shot generalization and 5.5. Open-set classification 5.4. One-shot generalization and 5.5. Open-set classification 5.6. Online vs. offline 5.6. Online vs. offline Conclusion, Acknowledgments and References Conclusion, Acknowledgments and References Supplementary Material Supplementary Material 4. Related work 4.1. Continual learning Continual learning literature typically focuses on catastrophic forgetting in supervised classification. Parameter isolation methods use dedicated parameters for each task by periodically extending the architecture while freezing already trained parameters [33] or by relying on isolated subnetworks [6]. Regularization approaches aim to preserve existing knowledge by limiting the plasticity of the network. Functional regularization methods constrain the network output through knowledge distillation [17] or by using a small set of anchor points to build a functional prior [26, 36]. Weight regularization methods [39] directly constrain network parameters according to their estimated importance for previous tasks. In particular, Variational Continual Learning (VCL) [25] derives the importance estimate by framing continual learning as sequential approximate Bayesian inference. Most methods incorporate regularization into the objective function, but it is also possible to implement it using constrained optimization [2, 10, 13, 22]. Finally, replay methods [4, 12, 30, 32] retain knowledge through rehearsal. When learning a new task, the network is trained with a mix of new samples from the training stream and previously seen samples drawn from the memory buffer. A specific case of this strategy is generative replay [3, 34], where the rehearsal samples are produced by a generative model trained to approximate the data distribution for each class. Many continual learning methods are hybrid systems that mix and match the above techniques. 4.2. Benchmarking continual learning Established continual learning benchmarks primarily involve splitting existing computer vision datasets into discrete, nonoverlapping segments to study continual supervised classification. Notable examples in this domain include split MNIST [39], split CIFAR [39], and split MiniImageNet [1, 4], along with their augmented counterparts, such as rotated MNIST [22], and permuted MNIST [15]. More recently, contributions from Lomonaco and Maltoni [20], Verwimp et al. [38] and Roady et al. [31] have enriched the field with dataset designed specifically for continual learning, such as CORe50, CLAD, and Stream-51, which comprise temporally correlated images with diverse backgrounds and environments. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Continual learning and Benchmarking continual learning

Table of Links Abstract and 1. Introduction 2. Methods 2.1. Modeling Panspermia and Terraformation 2.2. Identifying the Presence of Terraformed Planets and 2.3. Software and Availability 3. Results 3.1. Panspermia can increase the correlation between planets’ compositions and positions 3.2. Likely terraformed planets can be identified from clustering 4. Summary and Discussion 5. Acknowledgements and References APPENDIX A. Appendix 2.2. Identifying the Presence of Terraformed Planets 2.2.1. Summary We hypothesize that the process of panspermia and terraformation in our model will lead to a population of planets with anomalously high positive correlations between their spatial locations and compositions, compared to random permutations of these planets’ compositions. We quantify this using the Mantel test—a statistical test common in ecological science (Sec. 2.2.2). By clustering on the planet compositions, we can begin to pin down clusters of planets driving these correlations (Sec. 2.2.3). From these initial clusters, we select those localized in space (via their interquartile range, IQR), because we hypothesize that life would not only change the distribution of planetary compositions, but would also do so in a relatively compact portion of the galaxy. We further select clusters which, when removed, cause a decrease in the Mantel coefficient of the residual space of planets (Sec. 2.2.4). Finally, we attempt to evaluate how well our clusters reflect the presence of truly terraformed planets (Sec. 2.2.5). 2.2.2. Mantel Test The Mantel test is a measure of correlation between two distance matrices. The resulting value is called the Mantel coefficient, and is reported alongside a p-value calculated from an approximate permutation test (indicating the proportion of randomly permuted distance matrices which have correlations greater or equal to the correlation between the non-permuted distance matrices). Simply put, the p-value indicates how unlikely this correlation is compared to random permutations of the data. We wrote the Mantel test in Julia, with the algorithm and code adapted from Python’s scikit-bio (The scikit-bio development team 2020; Rideout et al. 2023). Here we used the Mantel test to measure the Pearson correlation between a distance matrix of all planet positions, and a distance matrix of all planet compositions. For each Mantel coefficient calculation, the p-value was generated using 99 permutations with a 2-sided alternative hypothesis. This is approximately equal to 2.5σ confidence. Because the p-value quantifies how anomalous an observed composition/position association is, given the assumptions of the model that correlations should only occur from panspermia and terraformation, we treat the p-value as one measure of confidence in the space containing a biosignature. To get an idea of how sensitive the Mantel coefficient corresponding to a 2.5σ detection is, we plotted how it varies based on number of planets observed (Fig. A3). We find that the sensitivity of the Mantel coefficient to number of planets observed decreases exponentially, and 1000 planets seems like a reasonable choice to reflect the balance of the challenge of realistically observing planets, with the need for those planets to exhibit potentially small correlations in composition-position space. The exact shape of this plot will vary by model parameters, but is especially dependent on the distribution of planet compositions and positions (e.g., planets being evenly distributed in composition or position space, vs. extremely heterogeneous). 2.2.3. Clustering We clustered planets in each iteration of the simulation based only on their compositions, using the DBSCAN algorithm implemented in R (Hahsler et al. 2019). Briefly, compared to other clustering algorithms, DBSCAN does not require the number of clusters to be predefined, can identify clusters of varying shapes and sizes based on the density of data points in the feature space, and separates points as belonging to clusters or noise. Arguments were chosen based on advice in the documentation, with minPts = 11 (the dimensionality of the data + 1), and eps was chosen dynamically at each iteration based on the location of the elbow in the k-nearest neighbor distance plot. Because the location of the elbow is not always obvious, we used the R implementation of the Kneedle algorithm (Satopaa et al. 2011), with sensitivity parameter = 1, empirically determined based on visual examination of the elbow placement on the nearest neighbor curves (Fig. A4). Note that the sensitivity should be adjusted to the specific data being analyzed, and in our case the data changes at each time step. This results in the Kneedle sensitivity being appropriate for only part of the time steps in our simulation. We chose to focus on the early steps of the simulation, but the sensitivity should be adjusted if finding the curves’ elbows in later time steps. DBSCAN classifies each point (planet) as either being part of a particular cluster, or noise (meaning it does not meet the criteria to fall into a cluster based on our chosen arguments). 2.2.4. Selecting clusters We first sought to select clusters for their likelihood of containing terraformed planets, without the aid of ground truth labels (i.e., without using our knowledge of which planets were truly terraformed in the model). We selected them by measuring their spatial spread, and by analyzing how the Mantel coefficient of the residual space of planets changes when removing clusters of planets. We created a threshold for the spatial spread of the planets in the clusters by taking the average of the interquartile range (IQR, where the middle 50% of planets fall) of all planets across each of the x, y, z dimensions, 2.2.5. Evaluating clustering We evaluated selected clusters meeting our criteria (IQR ≤ 25.2 ∧ MC ≥ 0) for how well they identified terraformed/non-terraformed planets, based on the true labels of each planet throughout our simulation. At each iteration, for each selected cluster, we calculated the ratio of planets in the cluster which were terraformed (true positives, TP) and non-terraformed (false positives, FP), as well as the ratio of planets outside the cluster which were non-terraformed (true negatives, TN) and terraformed (false negatives, FN) (Fig. A13). For example, if 100 of 1000 planets are terraformed, and a single selected cluster is identified with 80 planets, only 75 of which are terraformed, then the ratios for each metric in this cluster are: TP = 75/80, FP = 5/80, TN = 895/920, FN = 25/920. To simplify how this information is conveyed, we report the summary statistics of sensitivity, specificity, and accuracy. • Sensitivity is the proportion of all terraformed planets correctly selected by the cluster, TP/(TP+FN). This is 75/(75 + 25) in our example. • Specificity is the proportion of all non-terraformed planets correctly not selected by the cluster, TN/(TN+FP). This is 895/(895 + 5) in our example. • Accuracy is the proportion of all planets correctly classified, TP+TN/(TP+FP+TN+FN). This is (75 + 895)/1000 in our example. We believe a reliable biosignature must minimize false positives (i.e., must not misclassify non-terraformed planets), even at the expense of producing false negatives (i.e., missing terraformed planets). We thus consider our evaluation to be successful in validating our approach if specificity is high, even if sensitivity is low. 2.3. Software and Availability The code necessary to run the simulations and analyses is available on Github at https://github.com/ hbsmith/SmithSinapayen2024. Simulations were built in Julia, and analyses were carried out in Julia, Python, and R. Authors:
(1) Harrison B. Smith, Earth-Life Science Institute, Tokyo Institute of Technology, Ookayama, Meguro-ku, Tokyo, Japan, and Blue Marble Space Institute of Science, Seattle, Washington, USA (hbs@elsi.jp);
(2) Lana Sinapayen, Sony Computer Science Laboratories, Kyoto, Japan and National Institute for Basic Biology, Okazaki, Japan (lana.sinapayen@gmail.com). This paper is available on arxiv under CC BY-NC-ND 4.0 Deed license. [6] Though the extent we chose for an IQR threshold is arbitrary, it reflects the relative size of our model space and the presumption that looking for life that is still relatively spatially localized is of greater interest than looking for life which has already spread over the galaxy (the latter implying there might be other easier ways to look for life). This choice, like others, could be modified depending on other assumptions or objectives. Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 2. Methods 2.1. Modeling Panspermia and Terraformation 2.1. Modeling Panspermia and Terraformation 2.2. Identifying the Presence of Terraformed Planets and 2.3. Software and Availability 2.2. Identifying the Presence of Terraformed Planets and 2.3. Software and Availability 3. Results 3.1. Panspermia can increase the correlation between planets’ compositions and positions 3.1. Panspermia can increase the correlation between planets’ compositions and positions 3.2. Likely terraformed planets can be identified from clustering 3.2. Likely terraformed planets can be identified from clustering 4. Summary and Discussion 4. Summary and Discussion 5. Acknowledgements and References 5. Acknowledgements and References APPENDIX APPENDIX A. Appendix A. Appendix 2.2. Identifying the Presence of Terraformed Planets 2.2.1. Summary 2.2.1. Summary We hypothesize that the process of panspermia and terraformation in our model will lead to a population of planets with anomalously high positive correlations between their spatial locations and compositions, compared to random permutations of these planets’ compositions. We quantify this using the Mantel test—a statistical test common in ecological science (Sec. 2.2.2). By clustering on the planet compositions, we can begin to pin down clusters of planets driving these correlations (Sec. 2.2.3). From these initial clusters, we select those localized in space (via their interquartile range, IQR), because we hypothesize that life would not only change the distribution of planetary compositions, but would also do so in a relatively compact portion of the galaxy. We further select clusters which, when removed, cause a decrease in the Mantel coefficient of the residual space of planets (Sec. 2.2.4). Finally, we attempt to evaluate how well our clusters reflect the presence of truly terraformed planets (Sec. 2.2.5). 2.2.2. Mantel Test 2.2.2. Mantel Test The Mantel test is a measure of correlation between two distance matrices. The resulting value is called the Mantel coefficient, and is reported alongside a p-value calculated from an approximate permutation test (indicating the proportion of randomly permuted distance matrices which have correlations greater or equal to the correlation between the non-permuted distance matrices). Simply put, the p-value indicates how unlikely this correlation is compared to random permutations of the data. We wrote the Mantel test in Julia, with the algorithm and code adapted from Python’s scikit-bio (The scikit-bio development team 2020; Rideout et al. 2023). Here we used the Mantel test to measure the Pearson correlation between a distance matrix of all planet positions, and a distance matrix of all planet compositions. For each Mantel coefficient calculation, the p-value was generated using 99 permutations with a 2-sided alternative hypothesis. This is approximately equal to 2.5σ confidence. Because the p-value quantifies how anomalous an observed composition/position association is, given the assumptions of the model that correlations should only occur from panspermia and terraformation, we treat the p-value as one measure of confidence in the space containing a biosignature. To get an idea of how sensitive the Mantel coefficient corresponding to a 2.5σ detection is, we plotted how it varies based on number of planets observed (Fig. A3). We find that the sensitivity of the Mantel coefficient to number of planets observed decreases exponentially, and 1000 planets seems like a reasonable choice to reflect the balance of the challenge of realistically observing planets, with the need for those planets to exhibit potentially small correlations in composition-position space. The exact shape of this plot will vary by model parameters, but is especially dependent on the distribution of planet compositions and positions (e.g., planets being evenly distributed in composition or position space, vs. extremely heterogeneous). 2.2.3. Clustering 2.2.3. Clustering We clustered planets in each iteration of the simulation based only on their compositions, using the DBSCAN algorithm implemented in R (Hahsler et al. 2019). Briefly, compared to other clustering algorithms, DBSCAN does not require the number of clusters to be predefined, can identify clusters of varying shapes and sizes based on the density of data points in the feature space, and separates points as belonging to clusters or noise. Arguments were chosen based on advice in the documentation, with minPts = 11 (the dimensionality of the data + 1), and eps was chosen dynamically at each iteration based on the location of the elbow in the k-nearest neighbor distance plot. Because the location of the elbow is not always obvious, we used the R implementation of the Kneedle algorithm (Satopaa et al. 2011), with sensitivity parameter = 1, empirically determined based on visual examination of the elbow placement on the nearest neighbor curves (Fig. A4). Note that the sensitivity should be adjusted to the specific data being analyzed, and in our case the data changes at each time step. This results in the Kneedle sensitivity being appropriate for only part of the time steps in our simulation. We chose to focus on the early steps of the simulation, but the sensitivity should be adjusted if finding the curves’ elbows in later time steps. DBSCAN classifies each point (planet) as either being part of a particular cluster, or noise (meaning it does not meet the criteria to fall into a cluster based on our chosen arguments). 2.2.4. Selecting clusters 2.2.4. Selecting clusters We first sought to select clusters for their likelihood of containing terraformed planets, without the aid of ground truth labels (i.e., without using our knowledge of which planets were truly terraformed in the model). We selected them by measuring their spatial spread, and by analyzing how the Mantel coefficient of the residual space of planets changes when removing clusters of planets. We created a threshold for the spatial spread of the planets in the clusters by taking the average of the interquartile range (IQR, where the middle 50% of planets fall) of all planets across each of the x, y, z dimensions, 2.2.5. Evaluating clustering 2.2.5. Evaluating clustering We evaluated selected clusters meeting our criteria (IQR ≤ 25.2 ∧ MC ≥ 0) for how well they identified terraformed/non-terraformed planets, based on the true labels of each planet throughout our simulation. At each iteration, for each selected cluster, we calculated the ratio of planets in the cluster which were terraformed (true positives, TP) and non-terraformed (false positives, FP), as well as the ratio of planets outside the cluster which were non-terraformed (true negatives, TN) and terraformed (false negatives, FN) (Fig. A13). For example, if 100 of 1000 planets are terraformed, and a single selected cluster is identified with 80 planets, only 75 of which are terraformed, then the ratios for each metric in this cluster are: TP = 75/80, FP = 5/80, TN = 895/920, FN = 25/920. To simplify how this information is conveyed, we report the summary statistics of sensitivity, specificity, and accuracy. • Sensitivity is the proportion of all terraformed planets correctly selected by the cluster, TP/(TP+FN). This is 75/(75 + 25) in our example. • Specificity is the proportion of all non-terraformed planets correctly not selected by the cluster, TN/(TN+FP). This is 895/(895 + 5) in our example. • Accuracy is the proportion of all planets correctly classified, TP+TN/(TP+FP+TN+FN). This is (75 + 895)/1000 in our example. We believe a reliable biosignature must minimize false positives (i.e., must not misclassify non-terraformed planets), even at the expense of producing false negatives (i.e., missing terraformed planets). We thus consider our evaluation to be successful in validating our approach if specificity is high, even if sensitivity is low. 2.3. Software and Availability The code necessary to run the simulations and analyses is available on Github at https://github.com/ hbsmith/SmithSinapayen2024. Simulations were built in Julia, and analyses were carried out in Julia, Python, and R. Authors: (1) Harrison B. Smith, Earth-Life Science Institute, Tokyo Institute of Technology, Ookayama, Meguro-ku, Tokyo, Japan, and Blue Marble Space Institute of Science, Seattle, Washington, USA (hbs@elsi.jp); (2) Lana Sinapayen, Sony Computer Science Laboratories, Kyoto, Japan and National Institute for Basic Biology, Okazaki, Japan (lana.sinapayen@gmail.com). Authors: Authors: (1) Harrison B. Smith, Earth-Life Science Institute, Tokyo Institute of Technology, Ookayama, Meguro-ku, Tokyo, Japan, and Blue Marble Space Institute of Science, Seattle, Washington, USA ( hbs@elsi.jp ); hbs@elsi.jp (2) Lana Sinapayen, Sony Computer Science Laboratories, Kyoto, Japan and National Institute for Basic Biology, Okazaki, Japan ( lana.sinapayen@gmail.com ). lana.sinapayen@gmail.com This paper is available on arxiv under CC BY-NC-ND 4.0 Deed license. This paper is available on arxiv under CC BY-NC-ND 4.0 Deed license. available on arxiv [6] Though the extent we chose for an IQR threshold is arbitrary, it reflects the relative size of our model space and the presumption that looking for life that is still relatively spatially localized is of greater interest than looking for life which has already spread over the galaxy (the latter implying there might be other easier ways to look for life). This choice, like others, could be modified depending on other assumptions or objectives.

A Biosignature Based on Modeling Panspermia and Terraformation: Identifying Terraformed Planets

10 LeetCode Patterns to Solve 1000 LeetCode Problems

Author:
(1) David Novoa-Paradela, Universidade da Coruña, CITIC, Campus de Elviña s/n, 15008, A Coruña, Spain & Corresponding author (Email: david.novoa@udc.es);
(2) Oscar Fontenla-Romero, Universidade da Coruña, CITIC, Campus de Elviña s/n, 15008, A Coruña, Spain (Email: oscar.fontenla@udc.es);
(3) Bertha Guijarro-Berdiñas, Universidade da Coruña, CITIC, Campus de Elviña s/n, 15008, A Coruña, Spain (Email: berta.guijarro@udc.es). Table of Links Abstract and Introduction Related work The proposed pipeline Evaluation Conclusion & Acknowledgements References & Appendix 3. The proposed pipeline The purpose of the proposed pipeline is, given the text reviews of an Amazon product, to classify them as normal if they refer to it, and as anomalous if they describe different products or if they are so generic that they do not provide useful information to consumers. These classifications will be accompanied by a normality score and explanations that justify them. Figure 1 shows the modules that are part of the proposed pipeline to solve this task. In the first phase, we encode the text reviews of the target product using the pretrained MPNet transformer [25]. In the second phase, a DAEF [26] autoencoder is trained using these embeddings. Using the reconstruction errors issued by the network and a predefined threshold error, we can classify reviews as normal (error greater than the threshold) or anomalous (error less than the threshold). For the last phase, we propose a method based on the most frequent normal terms to generate an explanation associated with each classification. Therefore, the proposed pipeline is composed of three main modules: (1) Text encoding; (2) Anomaly detection; (3) Explainability. The following sections describe each of them in detail. 3.1. Text encoding Although there are models capable of dealing directly with images or text, machine learning models are usually designed to be trained using numerical vectors that represent the sample data (tabular data). This input format of the data is the usual one for classic anomaly detection methods. In the NLP area, there are multiple techniques to represent texts using vectors of real numbers, which are known as embeddings. These techniques allow the generation of vector spaces that try to represent the relationships and semantic similarities of the language, so that, for example, two synonymous words will be found at a shorter distance in the vector space than two unrelated words. Embeddings can be calculated independently for each word of the language (word embeddings), which led to models such as word2vec [27] or Global Vectors (GloVe) [28]. The representation of a sentence (sentence embedding) or a document (document embedding) will therefore be the sum of all the individual representations of the terms that make it up. To obtain representations of fixed length, it is usual to perform operations such as the mean. In certain cases, these operations between embeddings can worsen or even invalidate the final embedding, so specific models have been developed capable of understanding and representing a text as a whole, instead of just encoding it word by word. Among these models are those based on transformers [29], such as BERT [30], XLNet [31], GPT-3 [32] or GPT-4 [33], which have been trained over large-scale datasets and can solve different tasks, including sentence embedding. Since it inherits the advantages of the BERT and XLNet models while overcoming their limitations, we will use the pre-trained MPNet [25] model to calculate the embeddings of the reviews. MPNet combines Masked Language Modeling (MLM) and Permuted Language Modeling (PLM) to predict token dependencies, using auxiliary position information as input to enable the model to view a complete sentence and reduce position differences. Models like GPT-3 or GPT-4 are more advanced, but in addition to not being open source, they demand much higher computational resources, unaffordable for a significant part of the scientific community, as is our particular case. MPNet maps sentences and paragraphs to a 768 dimensional dense vector space e ∈ R 768×1 , providing fast and quality encodings. Computing time is a critical aspect in the area in which this work is framed, since in e-commerce platforms (and online reviews in general) we can find a huge number of products and reviews to deal with. Therefore, the proposed pipeline uses MPNet to calculate the embeddings of the reviews, which allows them to be represented as numeric vectors of fixed size. This model and others are available in the Hugging Face repository [34]. 3.2. Anomaly detection Anomaly detection is a field with a large number of algorithms that solve the problem of distinguishing between normal and anomalous instances in a wide variety of ways [4, 35]. Depending on the assumptions made and the processes they employ, we can distinguish between five main types of methods: probabilistic, distance-based, information theory-based, boundarybased, and reconstruction-based methods. Among the latter are autoencoder networks (AE) [36], one of the most widely used models. AE are a type of self-associative neural network whose output layer seeks to reproduce the data presented to the input layer after having gone through a dimensional compression phase. In this way, they manage to obtain a representation of the input data in a space with a dimension smaller than the original, learning a compact representation of the data, retaining the important information, and compressing the redundant one. One of the requirements of our proposed pipeline is to generate a normality score for each review. This score will allow us, among other things, to order the different reviews by their level of normality. When AE networks are used in anomaly detection scenarios, the classification is usually carried out based on the reconstruction error that they emit to reproduce in its output the embeddings of the reviews it receives as inputs, which represents the level of normality of the evaluated instance. This reconstruction error can be used as the normality score we are looking for. Due to the speed of its training, we have decided to use DAEF (Deep Autoencoder for Federated learning) [26] as our anomaly detection model. Unlike traditional neural networks, DAEF trains a deep AE network in a non-iterative way, which drastically reduces its training time without losing the performance of traditional (iterative) AEs. The proposed pipeline uses DAEF to calculate the embeddings of the reviews, being able to issue a normality score associated with each of the review classifications. 3.3. Explainability As black-box ML models are mainly being employed to make important predictions in critical contexts, the demand for transparency is increasing. The danger is in creating and using decisions that are not justifiable, legitimate, or that do not allow obtaining detailed explanations of their behaviour. Explanations supporting the output of a model are crucial, moreover in fields such as medicine, autonomous vehicles, security, or finance. When ML models do not meet any of the criteria imposed to declare them explainable, a separate method must be applied to the model to explain its decisions. This is the purpose of post-hoc explainability techniques [37], which aim at communicating understandable information about how an already developed model produces its predictions for any given input. Within these techniques, the so-called model-agnostic techniques are those designed to be plugged into any model with the intent of extracting some information from its prediction procedure. To generate the explanations we have implemented an approach based on a statistical analysis of the dataset. Based on the definitions of normal and anomalous review presented in Section 2, Our hypothesis assumes that normal reviews will always refer directly or indirectly to the target product so that there will be a list of terms used very frequently among normal texts. The appearance of one or more of these “normal” terms in a review would justify its classification by the system as normal. In the same way, anomalous reviews may be justified with the non-presence of said terms. The original text reviews classified as normal using the AD model will be processed (tokenization, lemmatization and stopword removal) and analyzed to obtain the list of the top-n most frequent terms. This list of terms will be compared with the lists of frequent terms of other products in order to remove the terms they have in common, so that the final list for a product does not contain generic terms. This final list of terms will be used to generate the explanations. New reviews classified as normal will be searched for the presence of any of these terms. To make this search more flexible, it will also be analyzed if there are terms in the review semantically close to any of the words on the list. To quantify the closeness of two words, the cosine similarity emitted by the MPNet transformer model itself will be used as a measure of distance. Reviews classified as anomalous will be explained by the non-occurrence of terms from the list. Figure 2 represents an overall view of the pipeline considering the product “chocolate bars” as the normal class. In summary, in this work, we propose the use of this statistical analysis of the terms to generate the explanations associated with the classification of the reviews. This paper is available on arxiv under CC 4.0 license. Author: (1) David Novoa-Paradela, Universidade da Coruña, CITIC, Campus de Elviña s/n, 15008, A Coruña, Spain & Corresponding author (Email: david.novoa@udc.es); (2) Oscar Fontenla-Romero, Universidade da Coruña, CITIC, Campus de Elviña s/n, 15008, A Coruña, Spain (Email: oscar.fontenla@udc.es); (3) Bertha Guijarro-Berdiñas, Universidade da Coruña, CITIC, Campus de Elviña s/n, 15008, A Coruña, Spain (Email: berta.guijarro@udc.es). Author: Author: (1) David Novoa-Paradela, Universidade da Coruña, CITIC, Campus de Elviña s/n, 15008, A Coruña, Spain & Corresponding author (Email: david.novoa@udc.es); (2) Oscar Fontenla-Romero, Universidade da Coruña, CITIC, Campus de Elviña s/n, 15008, A Coruña, Spain (Email: oscar.fontenla@udc.es); (3) Bertha Guijarro-Berdiñas, Universidade da Coruña, CITIC, Campus de Elviña s/n, 15008, A Coruña, Spain (Email: berta.guijarro@udc.es). Table of Links Abstract and Introduction Abstract and Introduction Related work Related work The proposed pipeline The proposed pipeline Evaluation Evaluation Conclusion & Acknowledgements Conclusion & Acknowledgements References & Appendix References & Appendix 3. The proposed pipeline The purpose of the proposed pipeline is, given the text reviews of an Amazon product, to classify them as normal if they refer to it, and as anomalous if they describe different products or if they are so generic that they do not provide useful information to consumers. These classifications will be accompanied by a normality score and explanations that justify them. Figure 1 shows the modules that are part of the proposed pipeline to solve this task. In the first phase, we encode the text reviews of the target product using the pretrained MPNet transformer [25]. In the second phase, a DAEF [26] autoencoder is trained using these embeddings. Using the reconstruction errors issued by the network and a predefined threshold error, we can classify reviews as normal (error greater than the threshold) or anomalous (error less than the threshold). For the last phase, we propose a method based on the most frequent normal terms to generate an explanation associated with each classification. Therefore, the proposed pipeline is composed of three main modules: (1) Text encoding; (2) Anomaly detection; (3) Explainability. The following sections describe each of them in detail. 3.1. Text encoding 3.1. Text encoding Although there are models capable of dealing directly with images or text, machine learning models are usually designed to be trained using numerical vectors that represent the sample data (tabular data). This input format of the data is the usual one for classic anomaly detection methods. In the NLP area, there are multiple techniques to represent texts using vectors of real numbers, which are known as embeddings. These techniques allow the generation of vector spaces that try to represent the relationships and semantic similarities of the language, so that, for example, two synonymous words will be found at a shorter distance in the vector space than two unrelated words. Embeddings can be calculated independently for each word of the language (word embeddings), which led to models such as word2vec [27] or Global Vectors (GloVe) [28]. The representation of a sentence (sentence embedding) or a document (document embedding) will therefore be the sum of all the individual representations of the terms that make it up. To obtain representations of fixed length, it is usual to perform operations such as the mean. In certain cases, these operations between embeddings can worsen or even invalidate the final embedding, so specific models have been developed capable of understanding and representing a text as a whole, instead of just encoding it word by word. Among these models are those based on transformers [29], such as BERT [30], XLNet [31], GPT-3 [32] or GPT-4 [33], which have been trained over large-scale datasets and can solve different tasks, including sentence embedding. Since it inherits the advantages of the BERT and XLNet models while overcoming their limitations, we will use the pre-trained MPNet [25] model to calculate the embeddings of the reviews. MPNet combines Masked Language Modeling (MLM) and Permuted Language Modeling (PLM) to predict token dependencies, using auxiliary position information as input to enable the model to view a complete sentence and reduce position differences. Models like GPT-3 or GPT-4 are more advanced, but in addition to not being open source, they demand much higher computational resources, unaffordable for a significant part of the scientific community, as is our particular case. MPNet maps sentences and paragraphs to a 768 dimensional dense vector space e ∈ R 768×1 , providing fast and quality encodings. Computing time is a critical aspect in the area in which this work is framed, since in e-commerce platforms (and online reviews in general) we can find a huge number of products and reviews to deal with. Therefore, the proposed pipeline uses MPNet to calculate the embeddings of the reviews, which allows them to be represented as numeric vectors of fixed size. This model and others are available in the Hugging Face repository [34]. 3.2. Anomaly detection 3.2. Anomaly detection Anomaly detection is a field with a large number of algorithms that solve the problem of distinguishing between normal and anomalous instances in a wide variety of ways [4, 35]. Depending on the assumptions made and the processes they employ, we can distinguish between five main types of methods: probabilistic, distance-based, information theory-based, boundarybased, and reconstruction-based methods. Among the latter are autoencoder networks (AE) [36], one of the most widely used models. AE are a type of self-associative neural network whose output layer seeks to reproduce the data presented to the input layer after having gone through a dimensional compression phase. In this way, they manage to obtain a representation of the input data in a space with a dimension smaller than the original, learning a compact representation of the data, retaining the important information, and compressing the redundant one. One of the requirements of our proposed pipeline is to generate a normality score for each review. This score will allow us, among other things, to order the different reviews by their level of normality. When AE networks are used in anomaly detection scenarios, the classification is usually carried out based on the reconstruction error that they emit to reproduce in its output the embeddings of the reviews it receives as inputs, which represents the level of normality of the evaluated instance. This reconstruction error can be used as the normality score we are looking for. Due to the speed of its training, we have decided to use DAEF (Deep Autoencoder for Federated learning) [26] as our anomaly detection model. Unlike traditional neural networks, DAEF trains a deep AE network in a non-iterative way, which drastically reduces its training time without losing the performance of traditional (iterative) AEs. The proposed pipeline uses DAEF to calculate the embeddings of the reviews, being able to issue a normality score associated with each of the review classifications. 3.3. Explainability 3.3. Explainability As black-box ML models are mainly being employed to make important predictions in critical contexts, the demand for transparency is increasing. The danger is in creating and using decisions that are not justifiable, legitimate, or that do not allow obtaining detailed explanations of their behaviour. Explanations supporting the output of a model are crucial, moreover in fields such as medicine, autonomous vehicles, security, or finance. When ML models do not meet any of the criteria imposed to declare them explainable, a separate method must be applied to the model to explain its decisions. This is the purpose of post-hoc explainability techniques [37], which aim at communicating understandable information about how an already developed model produces its predictions for any given input. Within these techniques, the so-called model-agnostic techniques are those designed to be plugged into any model with the intent of extracting some information from its prediction procedure. To generate the explanations we have implemented an approach based on a statistical analysis of the dataset. Based on the definitions of normal and anomalous review presented in Section 2, Our hypothesis assumes that normal reviews will always refer directly or indirectly to the target product so that there will be a list of terms used very frequently among normal texts. The appearance of one or more of these “normal” terms in a review would justify its classification by the system as normal. In the same way, anomalous reviews may be justified with the non-presence of said terms. The original text reviews classified as normal using the AD model will be processed (tokenization, lemmatization and stopword removal) and analyzed to obtain the list of the top-n most frequent terms. This list of terms will be compared with the lists of frequent terms of other products in order to remove the terms they have in common, so that the final list for a product does not contain generic terms. This final list of terms will be used to generate the explanations. New reviews classified as normal will be searched for the presence of any of these terms. To make this search more flexible, it will also be analyzed if there are terms in the review semantically close to any of the words on the list. To quantify the closeness of two words, the cosine similarity emitted by the MPNet transformer model itself will be used as a measure of distance. Reviews classified as anomalous will be explained by the non-occurrence of terms from the list. Figure 2 represents an overall view of the pipeline considering the product “chocolate bars” as the normal class. In summary, in this work, we propose the use of this statistical analysis of the terms to generate the explanations associated with the classification of the reviews. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Explainable AI in Action: Generating Insights from Review Anomalies

Effective Anomaly Detection Pipeline for Amazon Reviews: References & Appendix

Authors:
(1) Nhat A. Nghiem, Department of Physics and Astronomy, State University of New York (email: nhatanh.nghiemvu@stonybrook.edu);
(2) Tzu-Chieh Wei, Department of Physics and Astronomy, State University of New York and C. N. Yang Institute for Theoretical Physics, State University of New York. Table of Links Main Procedure Applications Discussion and Conclusion Acknowledgements, Declarations, Data Availability Statement, and References Appendix II. APPLICATIONS In this section, we highlight some interesting applications of the above simple procedure for matrix multiplication. We will soon appreciate a very remarkable efficiency that the above method yields. A. Accelerating Eigenvalues Finding where |Garbage⟩ is some unimportant state (not properly normalized). Combining such a procedure with the Hadamard test, the largest eigenvalue of A can be estimated. As mentioned in Theorem 1 of [5], the running time of the quantum power method is where n is the dimension of A, s is the sparsity of A, κ is the conditional number of A, k is the number of iterations, and ϵ is the error tolerance (the additive approximation to the true largest eigenvalue). While the speedup with respect to n is remarkable, we shall see that the improved matrix application 1 can improve the scaling on κ and ϵ. The crucial step in such a quantum power method is the HHL-like procedure, where the eigenvalues of A are extracted via quantum phase estimation, followed by rotation of ancilla controlled by the phase register. As can be seen from Theorem 1, matrix multiplication can be done very efficiently with the Chebyshev method [2]. The dependence on dimension n and conditional number κ and even tolerance error ϵ are all polylogarithmic. With such an improvement in performing matrix multiplication, we establish the following faster routine for quantum power method: Theorem 2 Given coherent access to a Hermitian matrix A, its largest eigenvalue could be estimate to additive accuracy ϵ with running time For simplicity purpose, if we neglect the contribution of logarithmic terms (compared to the polynomial terms), then we the faster QPW method has the same scaling on dimension n and sparsity s, almost quadratically better dependence on κ and a minor improvement on error ϵ. B. Estimating Trace of a Matrix We remark that the adaptive method in [4] has the same running time as the original HHL [1], which is quadratic in κ and polynomial in sparsity s. In our aforementioned result, the dependence on κ and s are polylogarithmic, which is thus highly efficient. It demonstrates the surprising utility of the Chebyshev series method introduced in [2]. As we have mentioned three examples above that rely on matrix multiplication, we foresee that matrix multiplication will be employed in other algorithms. The polylogarithmic dependence on all factors highlights that even if it is being used as a subroutine in a larger algorithm, the cost induced would be very modest. To exploit further the surprising efficiency of the above method, we now provide an alternative solution to the trace estimation problem of some given matrix. This problem has occured in [10], as estimating trace of kernel matrix is a necessary step of building (quantum) support vector machine. Additionally, this problem is also finds its application the DQC-1 model of quantum computation [11, 12], which can, e.g., efficiently estimate the values of Jones polynomials. We shall see that, in a similar fashion to the Chebyshev method [2], our method to estimate trace of a matrix would not make use of Hamiltonian subroutine, e.g., as in [10]. Then reverse the CNOT layers to return the old index. We obtain the following: Effectively, the modified blackbox P ′ A would ‘return’ the new matrix that has entries in a different order compared to A. However, the first column of, say, A′ is exactly the diagonal entries of A. We remark that what we describe above is just a simple way to relocate the entries of given matrix A. Basically, one can opt to relocate, or permute entries of A in different ways, as long as the first column of the new matrix is the diagonal of A. Now we are ready to describe our main algorithm. We note the following simple matrix multiplication identity: • The first state is (see Lemma 1 for definition of U(A′ ) and m = log(2N) + 1) • The second state is We have noted that this problem can be done easily using classical algorithm. We just simply need to query the matrix to get the diangonal entries and perform the summation, which can be done in logarithmic time using parallel algorithm. Therefore, classical computer can perform better in regards of time complexity. However, classical algorithm requires as much as N queries to matrix A in order to obtain diagonal entries. Meanwhile, in order to perform matrix multiplication, O(1) queries to matrix A is sufficient [2]. We remark that the above quantum running time is highly efficient w.r.t all parameters N, κ, s, as long as when κ and s grows polynomially as a function of N. For completeness, we restate the above quantum algorithm in the following theorem with the condition that the matrix A is not too ill-conditioned. Theorem 3 Given coherent access to some Hermitian matrix A, then its trace can be estimated to additive accuracy δ in time where the highest order of polylog(N) is about 2. The inner product of the above two states is By using Hadamard test, we can estimate the real and complex part of Tr(A), or more precisely, of Tr(A)/(sN). C. Estimating Trace of Product of Two Matrices In the above method, we use the simple trick to relocate those diagonal entries of given matrix A. However, that trick is not convenient to use when dealing with the problem of estimating Tr(A · B) where A and B are two matrices of size N × N (we assume the same condition on the bound of their spectrum, as well as Hermitian property as in the previous section). Before diving into the quantum algorithm, we quickly review the computation of trace. Let C = A · B, then Theorem 4 Given access to entries of two matrix A and B, the trace of AB could be estiamted to additive accuracy δ in time In order to compute Tr(AB), matrix multiplication needs to be done before summing over the diagonal entries. There are many classical algorithms for matrix multiplication, but none are known for achieving such task within polylogarithmic time. Therefore, the quantum algorithm outlined above yields exponential speedup with respect to dimension N of given matrix. D. Estimating Frobenius Norm Given a Hermitian matrix A of size N × N, its Frobenius norm is computed as: where {λi} are eigenvalues of A (note that since A is Hermitian then all eigenvalues are real). Revealing the full spectrum of A is apparently a daunting task. However, by definition, we have: Hence, as straightforward as it seems, the square of Frobenius norm is a direct result of previous section, since we are able to apply the matrix A and A†. The running time is similar to equation (23). As an alternative solution, now we describe how to compute such Frobenius norm with matrix application technique combined with quantum phase estimation. We first prepare the completely mixed state: This paper is available on arxiv under CC 4.0 license. Authors: (1) Nhat A. Nghiem, Department of Physics and Astronomy, State University of New York (email: nhatanh.nghiemvu@stonybrook.edu); (2) Tzu-Chieh Wei, Department of Physics and Astronomy, State University of New York and C. N. Yang Institute for Theoretical Physics, State University of New York. Authors: Authors: (1) Nhat A. Nghiem, Department of Physics and Astronomy, State University of New York (email: nhatanh.nghiemvu@stonybrook.edu); (2) Tzu-Chieh Wei, Department of Physics and Astronomy, State University of New York and C. N. Yang Institute for Theoretical Physics, State University of New York. Table of Links Main Procedure Main Procedure Applications Applications Discussion and Conclusion Discussion and Conclusion Acknowledgements, Declarations, Data Availability Statement, and References Acknowledgements, Declarations, Data Availability Statement, and References Appendix Appendix II. APPLICATIONS In this section, we highlight some interesting applications of the above simple procedure for matrix multiplication. We will soon appreciate a very remarkable efficiency that the above method yields. A. Accelerating Eigenvalues Finding where | Garbage ⟩ is some unimportant state (not properly normalized). Combining such a procedure with the Hadamard test, the largest eigenvalue of A can be estimated. As mentioned in Theorem 1 of [5], the running time of the quantum power method is Garbage where n is the dimension of A, s is the sparsity of A, κ is the conditional number of A, k is the number of iterations, and ϵ is the error tolerance (the additive approximation to the true largest eigenvalue). While the speedup with respect to n is remarkable, we shall see that the improved matrix application 1 can improve the scaling on κ and ϵ. The crucial step in such a quantum power method is the HHL-like procedure, where the eigenvalues of A are extracted via quantum phase estimation, followed by rotation of ancilla controlled by the phase register. As can be seen from Theorem 1, matrix multiplication can be done very efficiently with the Chebyshev method [2]. The dependence on dimension n and conditional number κ and even tolerance error ϵ are all polylogarithmic. With such an improvement in performing matrix multiplication, we establish the following faster routine for quantum power method: Theorem 2 Given coherent access to a Hermitian matrix A, its largest eigenvalue could be estimate to additive accuracy ϵ with running time Theorem 2 Given coherent access to a Hermitian matrix A, its largest eigenvalue could be estimate to additive accuracy ϵ with running time For simplicity purpose, if we neglect the contribution of logarithmic terms (compared to the polynomial terms), then we the faster QPW method has the same scaling on dimension n and sparsity s, almost quadratically better dependence on κ and a minor improvement on error ϵ. B. Estimating Trace of a Matrix We remark that the adaptive method in [4] has the same running time as the original HHL [1], which is quadratic in κ and polynomial in sparsity s. In our aforementioned result, the dependence on κ and s are polylogarithmic, which is thus highly efficient. It demonstrates the surprising utility of the Chebyshev series method introduced in [2]. As we have mentioned three examples above that rely on matrix multiplication, we foresee that matrix multiplication will be employed in other algorithms. The polylogarithmic dependence on all factors highlights that even if it is being used as a subroutine in a larger algorithm, the cost induced would be very modest. To exploit further the surprising efficiency of the above method, we now provide an alternative solution to the trace estimation problem of some given matrix. This problem has occured in [10], as estimating trace of kernel matrix is a necessary step of building (quantum) support vector machine. Additionally, this problem is also finds its application the DQC-1 model of quantum computation [11, 12], which can, e.g., efficiently estimate the values of Jones polynomials. We shall see that, in a similar fashion to the Chebyshev method [2], our method to estimate trace of a matrix would not make use of Hamiltonian subroutine, e.g., as in [10]. Then reverse the CNOT layers to return the old index. We obtain the following: Effectively, the modified blackbox P ′ A would ‘return’ the new matrix that has entries in a different order compared to A. However, the first column of, say, A′ is exactly the diagonal entries of A. We remark that what we describe above is just a simple way to relocate the entries of given matrix A. Basically, one can opt to relocate, or permute entries of A in different ways, as long as the first column of the new matrix is the diagonal of A. Now we are ready to describe our main algorithm. We note the following simple matrix multiplication identity: • The first state is (see Lemma 1 for definition of U(A′ ) and m = log(2N) + 1) • The second state is We have noted that this problem can be done easily using classical algorithm. We just simply need to query the matrix to get the diangonal entries and perform the summation, which can be done in logarithmic time using parallel algorithm. Therefore, classical computer can perform better in regards of time complexity. However, classical algorithm requires as much as N queries to matrix A in order to obtain diagonal entries. Meanwhile, in order to perform matrix multiplication, O(1) queries to matrix A is sufficient [2]. We remark that the above quantum running time is highly efficient w.r.t all parameters N, κ, s, as long as when κ and s grows polynomially as a function of N. For completeness, we restate the above quantum algorithm in the following theorem with the condition that the matrix A is not too ill-conditioned. Theorem 3 Given coherent access to some Hermitian matrix A, then its trace can be estimated to additive accuracy δ in time Theorem 3 Given coherent access to some Hermitian matrix A, then its trace can be estimated to additive accuracy δ in time where the highest order of polylog(N) is about 2. where the highest order of polylog(N) is about 2. The inner product of the above two states is By using Hadamard test, we can estimate the real and complex part of Tr(A), or more precisely, of Tr(A)/(sN). C. Estimating Trace of Product of Two Matrices In the above method, we use the simple trick to relocate those diagonal entries of given matrix A. However, that trick is not convenient to use when dealing with the problem of estimating Tr(A · B) where A and B are two matrices of size N × N (we assume the same condition on the bound of their spectrum, as well as Hermitian property as in the previous section). Before diving into the quantum algorithm, we quickly review the computation of trace. Let C = A · B, then Theorem 4 Given access to entries of two matrix A and B, the trace of AB could be estiamted to additive accuracy δ in time Theorem 4 Given access to entries of two matrix A and B, the trace of AB could be estiamted to additive accuracy δ in time In order to compute Tr(AB), matrix multiplication needs to be done before summing over the diagonal entries. There are many classical algorithms for matrix multiplication, but none are known for achieving such task within polylogarithmic time. Therefore, the quantum algorithm outlined above yields exponential speedup with respect to dimension N of given matrix. D. Estimating Frobenius Norm Given a Hermitian matrix A of size N × N, its Frobenius norm is computed as: where {λi} are eigenvalues of A (note that since A is Hermitian then all eigenvalues are real). Revealing the full spectrum of A is apparently a daunting task. However, by definition, we have: Hence, as straightforward as it seems, the square of Frobenius norm is a direct result of previous section, since we are able to apply the matrix A and A†. The running time is similar to equation (23). As an alternative solution, now we describe how to compute such Frobenius norm with matrix application technique combined with quantum phase estimation. We first prepare the completely mixed state: This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

An Improved Method for Quantum Matrix Multiplication: Applications

Authors:
(1) Kexun Zhang, UC Santa Barbara and Equal contribution;
(2) Hongqiao Chen, Northwood High School and Equal contribution;
(3) Lei Li, Carnegie Mellon University;
(4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro
Related Work
ToolDec: LLM Tool Use via Finite-State Decoding
Experiment: ToolDec Eliminates Syntax Errors
Experiment: ToolDec Enables Generalizable Tool Selection
Conclusion and References
Appendix 5. EXPERIMENT II: TOOLDEC ENABLES GENERALIZABLE TOOL SELECTION In Experiment II, we show how TOOLDEC generalizes to unseen tools without additional training data and tool documentation. We compare TOOLDEC with two strong baselines—ToolkenGPT (Hao et al., 2023) as a representative fine-tuning approach, and RestGPT (Song et al., 2023) as a representative in-context learning approach. We conducted experiments on three benchmarks— FuncQA (Hao et al., 2023) and KAMEL (Kalo & Fichtel, 2022), and RestBench (Song et al., 2023). These benchmarks require diverse tool sets from very different domains, including math reasoning, knowledge question answering and real-world web services. In all three domains, our results show that TOOLDEC is able to efficiently generalize to new tools without fine-tuning on extra data. 5.1 FINE-TUNING BASELINE: TOOLKENGPT ToolkenGPT is a fine-tuning approach to tool use that learns a special token for every tool. To generalize to new tools, ToolkenGPT still needs additional data and extra fine-tuning involving the use of new tools. We demonstrate that TOOLDEC, once fine-tuned on a given set of seen tools, doesn’t need additional data and further fine-tuning to adopt unseen tools. We compare TOOLDEC and the baselines by tuning them on the same subset of tools, denoted as “seen tools”, and then evaluate their performance on “unseen tools”. To guarantee a fair comparison, We mimic ToolkenGPT’s planning method to solve the “when to use tools” problem. Specifically, we fine-tune the embedding of a single special token <T>  to represent all tools, reducing the size of extra vocabulary to 1. Once <T> is generated, a tool call begins. We prompt LLM to generate a tool name. The generation of this tool name is guided by an FSM constructed from a list of all available tools. This tool name is then plugged back into the context to start the generation of arguments. We show an example of this process in Appendix A.2. We selected a small subset of “seen tools” out of all available tools and tuned the embedding only with demonstrations of the tools in the selected subset. We fine-tuned the baseline using the same subset. Then, we evaluated our method and the baselines on tasks that involve unseen tools in the subset to demonstrate TOOLDEC’s generalization ability. Benchmark on Math Functions. We use FuncQA multi-hop questions to evaluate our method. Tools in FuncQA, such as permutate, gcd, power are mathematical functions that strictly limits on their arguments to be numbers in certain ranges. We select 4 out of 13 tools as the seen subset to tune the baseline and evaluate different approaches on the remaining 9 unseen tools. Benchmark on Knowledge Graph Relations. To further investigate TOOLDEC’s generalizability on a larger set of tools, we also evaluate on KAMEL (Kalo & Fichtel, 2022), a question-answering dataset containing a total of 234 knowledge relations that resemble the characteristics of APIs (e.g. number of children). More examples can be found in Appendix A.4. The tools in KAMEL are many more than those in FuncQA. They are also more complex and diverse because the number of arguments to their tools varies from 1 to 3, and their types include strings, locations, dates, numbers and other ad-hoc types. We select 30 out of 234 tools as the seen subset and evaluate on 4 different evaluation sets, with 30, 60, 100, and 234 tools, respectively. Following Hao et al. (2023), we use prompting, few-shot, and zero-shot as extra baselines. (1) Prompting relies on the internal knowledge of LLM, since no tool was provided. (2) Few-shot demonstrates tool use through few-shot examples. (3) Zero-shot provides descriptions of all available tools in context. Since the KAMEL’s training and evaluation dataset share the same question template for every tool, which is often not true in real-world settings, we compare TOOLDEC only to ToolkenGPT trained on the synthetic dataset proposed by the original study. We use the accuracy of tool calls as a metric, which is determined by the proportion of responses that invoke the correct knowledge relation. 5.2 IN-CONTEXT LEARNING BASELINE: RESTGPT RestGPT (Song et al., 2023) is an in-context learning approach that learns tool use from in-context tool documentation. We demonstrate the generalization ability of TOOLDEC-enhanced RestGPT by showing that RestGPT with TOOLDEC can achieve better accuracy without in-context documentation than the RestGPT baseline with documentation. Since TOOLDEC needs access to the next token distribution, we use Vicuna-based (Zheng et al., 2023) RestGPT as the baseline. For our method, we remove all tool documentation from the prompt, leaving only the instructions for reasoning. Benchmark on APIs for Real-World Web Services. We evaluate on RestBench (Song et al., 2023). It consists of tasks in real-world scenarios including TMDB, a website for movie information, and Spotify, an online music player. These tasks directly come from real-user instructions and require multiple tools in the form of RESTful APIs to solve. RESTful APIs are the de facto standard for web services (Li et al., 2016) that use HTTP methods to manipulate resources. The ground truth solutions are annotated by humans in the form of tool call chains. We evaluate our method and the baseline on TMDB, which consists of 55 RESTful APIs. Since HTTP methods such as GET and POST have a format different from the tool call, tool arguments format of TOOLDEC. We rewrote these APIs to follow this format. We use the correct path rate (CP%) proposed by the original paper as the metric to measure accuracy. Correct path rate is the proportion of model outputs that contain the correct tool call path annotated by humans. 5.3 EXPERIMENT RESULTS Generalization to Unseen Math Functions. In Figure 5a, we present the results on FuncQA. While ToolkenGPT and TOOLDEC achieved similar accuracies on tasks that involved only seen tools, ToolkenGPT failed to generalize to unseen tools, resulting in a significant performance drop. On the other hand, TOOLDEC was able to maintain a comparable accuracy even on unseen tools and achieve 8x better accuracy on multi-hop problems, underscoring its generalizability. Consequently, TOOLDEC significantly outperformed ToolkenGPT on total accuracy. Generalization to Unseen Knowledge Graph Functions. We present our results on KAMEL in Figure 5b. As the number of available tools increased, the two ICL methods suffered from the context length limit (Hao et al., 2023) and experienced a significant drop in accuracy. ToolkenGPT, fine-tuned on the first 30 tools, was also unable to generalize to more tools. Prompting kept a stable low accuracy because it did not rely on in-context tool documentation. On the other hand, TOOLDEC was able to maintain its accuracy even when the amount of unseen tools reached 204. Generalization to Unseen Web Services. The results on RestBench are reported in Table 5. TOOLDEC enabled the model to use web-service APIs without in-context documentation, reducing the prompt size from 1974 tokens to only 880 tokens. Nevertheless, TOOLDEC still significantly outperformed the baseline in terms of correctness indicated by correct path ratio (CP%), raising it by 8 points. These results suggest that TOOLDEC can also improve the generalizability of in-context learning tool use in real-world web applications. Results from all three settings indicate that not only does TOOLDEC help fine-tuning tool LLMs generalize without extra training data, it also helps in-context learning tool LLMs generalize without in-context documentation. This capability of TOOLDEC has been proven in three different domains. This paper is available on arxiv under CC 4.0 DEED license. Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Authors: Authors: (1) Kexun Zhang, UC Santa Barbara and Equal contribution; (2) Hongqiao Chen, Northwood High School and Equal contribution; (3) Lei Li, Carnegie Mellon University; (4) William Yang Wang,UC Santa Barbara. Table of Links Abstract and Intro Related Work ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Appendix Abstract and Intro Abstract and Intro Related Work Related Work ToolDec: LLM Tool Use via Finite-State Decoding ToolDec: LLM Tool Use via Finite-State Decoding Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Eliminates Syntax Errors Experiment: ToolDec Enables Generalizable Tool Selection Experiment: ToolDec Enables Generalizable Tool Selection Conclusion and References Conclusion and References Appendix Appendix 5. EXPERIMENT II: TOOLDEC ENABLES GENERALIZABLE TOOL SELECTION In Experiment II, we show how TOOLDEC generalizes to unseen tools without additional training data and tool documentation. We compare TOOLDEC with two strong baselines—ToolkenGPT (Hao et al., 2023) as a representative fine-tuning approach, and RestGPT (Song et al., 2023) as a representative in-context learning approach. We conducted experiments on three benchmarks— FuncQA (Hao et al., 2023) and KAMEL (Kalo & Fichtel, 2022), and RestBench (Song et al., 2023). These benchmarks require diverse tool sets from very different domains, including math reasoning, knowledge question answering and real-world web services. In all three domains, our results show that TOOLDEC is able to efficiently generalize to new tools without fine-tuning on extra data. 5.1 FINE-TUNING BASELINE: TOOLKENGPT ToolkenGPT is a fine-tuning approach to tool use that learns a special token for every tool. To generalize to new tools, ToolkenGPT still needs additional data and extra fine-tuning involving the use of new tools. We demonstrate that TOOLDEC, once fine-tuned on a given set of seen tools, doesn’t need additional data and further fine-tuning to adopt unseen tools. We compare TOOLDEC and the baselines by tuning them on the same subset of tools, denoted as “seen tools”, and then evaluate their performance on “unseen tools”. To guarantee a fair comparison, We mimic ToolkenGPT’s planning method to solve the “when to use tools” problem. Specifically, we fine-tune the embedding of a single special token <T>  to represent all tools, reducing the size of extra vocabulary to 1. Once <T> is generated, a tool call begins. We prompt LLM to generate a tool name. The generation of this tool name is guided by an FSM constructed from a list of all available tools. This tool name is then plugged back into the context to start the generation of arguments. We show an example of this process in Appendix A.2. We selected a small subset of “seen tools” out of all available tools and tuned the embedding only with demonstrations of the tools in the selected subset. We fine-tuned the baseline using the same subset. Then, we evaluated our method and the baselines on tasks that involve unseen tools in the subset to demonstrate TOOLDEC’s generalization ability. Benchmark on Math Functions. We use FuncQA multi-hop questions to evaluate our method. Tools in FuncQA, such as permutate, gcd, power are mathematical functions that strictly limits on their arguments to be numbers in certain ranges. We select 4 out of 13 tools as the seen subset to tune the baseline and evaluate different approaches on the remaining 9 unseen tools. Benchmark on Math Functions. Benchmark on Knowledge Graph Relations. To further investigate TOOLDEC’s generalizability on a larger set of tools, we also evaluate on KAMEL (Kalo & Fichtel, 2022), a question-answering dataset containing a total of 234 knowledge relations that resemble the characteristics of APIs (e.g. number of children). More examples can be found in Appendix A.4. The tools in KAMEL are many more than those in FuncQA. They are also more complex and diverse because the number of arguments to their tools varies from 1 to 3, and their types include strings, locations, dates, numbers and other ad-hoc types. We select 30 out of 234 tools as the seen subset and evaluate on 4 different evaluation sets, with 30, 60, 100, and 234 tools, respectively. Following Hao et al. (2023), we use prompting, few-shot, and zero-shot as extra baselines. (1) Prompting relies on the internal knowledge of LLM, since no tool was provided. (2) Few-shot demonstrates tool use through few-shot examples. (3) Zero-shot provides descriptions of all available tools in context. Since the KAMEL’s training and evaluation dataset share the same question template for every tool, which is often not true in real-world settings, we compare TOOLDEC only to ToolkenGPT trained on the synthetic dataset proposed by the original study. We use the accuracy of tool calls as a metric, which is determined by the proportion of responses that invoke the correct knowledge relation. Benchmark on Knowledge Graph Relations. 5.2 IN-CONTEXT LEARNING BASELINE: RESTGPT RestGPT (Song et al., 2023) is an in-context learning approach that learns tool use from in-context tool documentation. We demonstrate the generalization ability of TOOLDEC-enhanced RestGPT by showing that RestGPT with TOOLDEC can achieve better accuracy without in-context documentation than the RestGPT baseline with documentation. Since TOOLDEC needs access to the next token distribution, we use Vicuna-based (Zheng et al., 2023) RestGPT as the baseline. For our method, we remove all tool documentation from the prompt, leaving only the instructions for reasoning. Benchmark on APIs for Real-World Web Services. We evaluate on RestBench (Song et al., 2023). It consists of tasks in real-world scenarios including TMDB, a website for movie information, and Spotify, an online music player. These tasks directly come from real-user instructions and require multiple tools in the form of RESTful APIs to solve. RESTful APIs are the de facto standard for web services (Li et al., 2016) that use HTTP methods to manipulate resources. The ground truth solutions are annotated by humans in the form of tool call chains. We evaluate our method and the baseline on TMDB, which consists of 55 RESTful APIs. Since HTTP methods such as GET and POST have a format different from the tool call, tool arguments format of TOOLDEC. We rewrote these APIs to follow this format. We use the correct path rate (CP%) proposed by the original paper as the metric to measure accuracy. Correct path rate is the proportion of model outputs that contain the correct tool call path annotated by humans. Benchmark on APIs for Real-World Web Services. 5.3 EXPERIMENT RESULTS Generalization to Unseen Math Functions. In Figure 5a, we present the results on FuncQA. While ToolkenGPT and TOOLDEC achieved similar accuracies on tasks that involved only seen tools, ToolkenGPT failed to generalize to unseen tools, resulting in a significant performance drop. On the other hand, TOOLDEC was able to maintain a comparable accuracy even on unseen tools and achieve 8x better accuracy on multi-hop problems, underscoring its generalizability. Consequently, TOOLDEC significantly outperformed ToolkenGPT on total accuracy. Generalization to Unseen Math Functions. Generalization to Unseen Knowledge Graph Functions. We present our results on KAMEL in Figure 5b. As the number of available tools increased, the two ICL methods suffered from the context length limit (Hao et al., 2023) and experienced a significant drop in accuracy. ToolkenGPT, fine-tuned on the first 30 tools, was also unable to generalize to more tools. Prompting kept a stable low accuracy because it did not rely on in-context tool documentation. On the other hand, TOOLDEC was able to maintain its accuracy even when the amount of unseen tools reached 204. Generalization to Unseen Knowledge Graph Functions. Generalization to Unseen Web Services. The results on RestBench are reported in Table 5. TOOLDEC enabled the model to use web-service APIs without in-context documentation, reducing the prompt size from 1974 tokens to only 880 tokens. Nevertheless, TOOLDEC still significantly outperformed the baseline in terms of correctness indicated by correct path ratio (CP%), raising it by 8 points. These results suggest that TOOLDEC can also improve the generalizability of in-context learning tool use in real-world web applications. Generalization to Unseen Web Services. Results from all three settings indicate that not only does TOOLDEC help fine-tuning tool LLMs generalize without extra training data, it also helps in-context learning tool LLMs generalize without in-context documentation. This capability of TOOLDEC has been proven in three different domains. This paper is available on arxiv under CC 4.0 DEED license. This paper is available on arxiv under CC 4.0 DEED license. available on arxiv

Syntax Error-Free and Generalizable Tool Use for LLMs: ToolDec Enables Generalizable Tool Selection

সিনট্যাক্স ত্রুটি-মুক্ত এবং LLM-এর জন্য সাধারণীকরণযোগ্য টুল ব্যবহার: ToolDec সাধারণীকরণযোগ্য টুল নির্বাচন সক্ষম করে

Syntaxfehlerfreier und verallgemeinerbarer Werkzeugeinsatz für LLMs: ToolDec ermöglicht verallgemeinerbare Werkzeugauswahl

Uso de herramientas generalizables y sin errores de sintaxis para LLM: ToolDec permite la selección de herramientas generalizables

Utilisation d'outils de syntaxe sans erreur et généralisables pour les LLM : ToolDec permet la sélection d'outils généralisables

LLM के लिए वाक्यविन्यास त्रुटि-रहित और सामान्यीकरण योग्य टूल का उपयोग: ToolDec सामान्यीकरण योग्य टूल चयन को सक्षम करता है

LLM 向けの構文エラーのない一般化可能なツールの使用: ToolDec により一般化可能なツール選択が可能

LLM을 위한 구문 오류가 없고 일반화 가능한 도구 사용: ToolDec을 통해 일반화 가능한 도구 선택 가능

Uso de ferramenta generalizável e livre de erros de sintaxe para LLMs: ToolDec permite seleção de ferramenta generalizável

Без синтаксических ошибок и универсальное использование инструментов для LLM: ToolDec обеспечивает универсальный выбор инструментов

Yüksek Lisans'lar için Sözdizimi Hatasız ve Genelleştirilebilir Araç Kullanımı: ToolDec Genelleştirilebilir Araç Seçimini Etkinleştirir

Sử dụng công cụ không có lỗi và có thể khái quát hóa cho LLM: ToolDec cho phép lựa chọn công cụ có thể khái quát hóa

语法无错误且可通用的 LLM 工具使用：ToolDec 支持通用工具选择

Transductive Learning for Textual Few-Shot: Limitations, Acknowledgements, & References

Authors: (1) Dominic Petrak, UKP Lab, Department of Computer Science, Technical University of Darmstadt, Germany; (2) Nafise Sadat Moosavi, Department of Computer Science, The University of Sheffield, United Kingdom; (3) Ye Tian, Wluper, London, United Kingdom; (4) Nikolai Rozanov, Wluper, London, United Kingdom; (5) Iryna Gurevych, UKP Lab, Department of Computer Science, Technical University of Darmstadt, Germany. Table of Links Abstract & Introduction Related Work Datasets Examined Manual Error Type Analysis and Taxonomies Automatic Filtering for Potentially Relevant Dialogs Statistical Analysis Evaluation and Experiments Discussion Conclusion, Limitation, Acknowledgments, and References A Integrated Error Taxonomy – Details B Error-Indicating Sentences And Phrases C Automatic Filtering – Implementation D Automatic Filtering – Sentence-Level Analysis E Task-Oriented Dialogs – Examples F Effectiveness Of Automatic Filtering – A Detailed Analysis G Inter-Annotator Agreement – Detailed Analysis H Annotation Guidelines I Hyperparameters and Baseline Experiments J Human-Human Dialogs – Examples 9 Conclusion In this work, we examined the dialogs of six datasets from various types, including MultiWoZ, SGD, BABI, PersonaChat, Wizards-of-Wikipedia, and the human-bot split from the Self-Feeding Chatbot, for errors in system utterances and the types of subsequent user responses to assess their extendibility with annotations for learning from free-text human feedback. Our results show that this largely depends on whether the dialogs are human-human or human-bot, and whether they are task-oriented, open-domain, or knowledgegrounded. We found that human-bot dialogs, contain more errors in system utterances that are addressed with free-text human feedback in subsequent user responses, especially in the case of opendomain and knowledge-grounded dialogs. Therefore, it might be feasible to extend these datasets with the needed annotations to support research into methods for learning from free-text human feedback, e.g., by taking advantage of the recent developments in synthetic data generation. We also used the insights gained during this process to propose a new user response type taxonomy and a modified Integrated Error Taxonomy for the annotation of free-text human feedback. Our experiments show that including errors from system utterances and subsequent user responses has a positive impact in response generation. 10 Limitations The majority of our evaluation was done manually. Therefore, with respect to the original dataset sizes, we only consider a small fraction of the data in our study. It might be possible that our results would have been clearer when we would have considered more dialogs for the collection of error-indicating sentences. However, our analysis shows that errors found in the randomly selected dialogs are mostly ignored by the user, i.e., the user does not provide free-text human feedback that could be used for learning. Thus, as far as we are concerned, this does not limit the meaningfulness of our results. Regarding dataset selection, our corpus study (and its results) have only limited expressiveness for knowledge-grounded dialog datasets, since we only consider one of such datasets in our study, Wizards-of-Wikipedia (Dinan et al., 2019). However, this does not affect the relevance of our work, as there are already free-text human feedback annotated datasets available, e.g., FITS (Xu et al., 2023), and we considered a representative number of datasets from other dialog types for which there is a lack of publicly available feedback-annotated datasets, such as task-oriented dialogs. The taxonomies used in this work are also subject to limitations. In the case of the modified Integrated Error Taxonomy, our results show that it improves agreement across different dialog types. However, its abstract error types might limit application for specific use cases, e.g., for a more fine-grained consideration of different types of social errors. Moreover, it reflects only error types observed in the datasets examined. The same applies to the user response type taxonomy. 11 Acknowledgments This work has been funded by the LOEWE Distinguished Chair Ubiquitous Knowledge Processing (LOEWE initiative, Hesse, Germany) and the European Union under the Horizon Europe grant № 101070351 (SERMAS). References Antoine Bordes, Y-Lan Boureau, and Jason Weston. 2017. Learning end-to-end goal-oriented dialog. In International Conference on Learning Representations. Paweł Budzianowski, Tsung-Hsien Wen, Bo-Hsiang Tseng, Iñigo Casanueva, Stefan Ultes, Osman Ramadan, and Milica Gašic. 2018. ´ MultiWOZ - a largescale multi-domain Wizard-of-Oz dataset for taskoriented dialogue modelling. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 5016–5026, Brussels, Belgium. Association for Computational Linguistics. Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017. Deep Reinforcement Learning from Human Preferences. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc. Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping Huang, Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. 2022. Scaling instruction-finetuned language models. Emily Dinan, Stephen Roller, Kurt Shuster, Angela Fan, Michael Auli, and Jason Weston. 2019. Wizard of wikipedia: Knowledge-powered conversational agents. In International Conference on Learning Representations. Laila Dybkjaer, Niels Ole Bernsen, and Hans Dybkjaer. 1996. Grice incorporated: Cooperativity in spoken dialogue. In COLING 1996 Volume 1: The 16th International Conference on Computational Linguistics. Braden Hancock, Antoine Bordes, Pierre-Emmanuel Mazare, and Jason Weston. 2019. Learning from dialogue after deployment: Feed yourself, chatbot! In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3667– 3684, Florence, Italy. Association for Computational Linguistics. Matthew Henderson, Paweł Budzianowski, Iñigo Casanueva, Sam Coope, Daniela Gerz, Girish Kumar, Nikola Mrkšic, Georgios Spithourakis, Pei-Hao Su, ´ Ivan Vulic, and Tsung-Hsien Wen. 2019. ´ A repository of conversational datasets. In Proceedings of the First Workshop on NLP for Conversational AI, pages 1–10, Florence, Italy. Association for Computational Linguistics. Ryuichiro Higashinaka, Masahiro Araki, Hiroshi Tsukahara, and Masahiro Mizukami. 2021. Integrated taxonomy of errors in chat-oriented dialogue systems. In Proceedings of the 22nd Annual Meeting of the Special Interest Group on Discourse and Dialogue, pages 89–98, Singapore and Online. Association for Computational Linguistics. Ryuichiro Higashinaka, Masahiro Araki, Hiroshi Tsukahara, and Masahiro Mizukami. 2021. Integrated taxonomy of errors in chat-oriented dialogue systems. In Proceedings of the 22nd Annual Meeting of the Special Interest Group on Discourse and Dialogue, pages 89–98, Singapore and Online. Association for Computational Linguistics. Hyunwoo Kim, Jack Hessel, Liwei Jiang, Ximing Lu, Youngjae Yu, Pei Zhou, Ronan Le Bras, Malihe Alikhani, Gunhee Kim, Maarten Sap, and Yejin Choi. 2022. Soda: Million-scale dialogue distillation with social commonsense contextualization. Klaus Krippendorff. 2004. Reliability in content analysis. Human Communication Research, 30(3):411– 433. Ilya Loshchilov and Frank Hutter. 2019. Decoupled weight decay regularization. In International Conference on Learning Representations. Sebastian Möller, Klaus-Peter Engelbrecht, and Antti Oulasvirta. 2007. Analysis of communication failures for spoken dialogue systems. In INTERSPEECH 2007, International Speech Communication Association (ISCA). Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F Christiano, Jan Leike, and Ryan Lowe. 2022. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, volume 35, pages 27730–27744. Curran Associates, Inc. Kishore Papineni, Salim Roukos, Todd Ward, and WeiJing Zhu. 2002. Bleu: A method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, ACL ’02, page 311–318, USA. Association for Computational Linguistics. Sunghyun Park, Han Li, Ameen Patel, Sidharth Mudgal, Sungjin Lee, Young-Bum Kim, Spyros Matsoukas, and Ruhi Sarikaya. 2021. A scalable framework for learning from implicit user feedback to improve natural language understanding in large-scale conversational AI systems. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 6054–6063, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics. Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. Pytorch: An imperative style, high-performance deep learning library. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9. Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghav Gupta, and Pranav Khaitan. 2020. Towards scalable multi-domain conversational agents: The schema-guided dialogue dataset. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05):8689–8696. Nils Reimers and Iryna Gurevych. 2019. SentenceBERT: Sentence embeddings using Siamese BERTnetworks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 3982–3992, Hong Kong, China. Association for Computational Linguistics. Abigail See and Christopher Manning. 2021. Understanding and predicting user dissatisfaction in a neural generative chatbot. In Proceedings of the 22nd Annual Meeting of the Special Interest Group on Discourse and Dialogue, pages 1–12, Singapore and Online. Association for Computational Linguistics. Kurt Shuster, Jing Xu, Mojtaba Komeili, Da Ju, Eric Michael Smith, Stephen Roller, Megan Ung, Moya Chen, Kushal Arora, Joshua Lane, Morteza Behrooz, William Ngan, Spencer Poff, Naman Goyal, Arthur Szlam, Y-Lan Boureau, Melanie Kambadur, and Jason Weston. 2022. Blenderbot 3: a deployed conversational agent that continually learns to responsibly engage. Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and TieYan Liu. 2020. MPNet: Masked and Permuted Pretraining for Language Understanding. In Advances in Neural Information Processing Systems, volume 33, pages 16857–16867. Curran Associates, Inc. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023. Llama: Open and efficient foundation language models. Megan Ung, Jing Xu, and Y-Lan Boureau. 2022. SaFeRDialogues: Taking feedback gracefully after conversational safety failures. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 6462– 6481, Dublin, Ireland. Association for Computational Linguistics. Mathilde Veron, Sophie Rosset, Olivier Galibert, and Guillaume Bernard. 2021. Evaluate on-the-job learning dialogue systems and a case study for natural language understanding. Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020. Transformers: State-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38–45, Online. Association for Computational Linguistics. Jing Xu, Megan Ung, Mojtaba Komeili, Kushal Arora, Y-Lan Boureau, and Jason Weston. 2023. Learning new skills after deployment: Improving open-domain internet-driven dialogue with human feedback. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 13557–13572, Toronto, Canada. Association for Computational Linguistics. Saizheng Zhang, Emily Dinan, Jack Urbanek, Arthur Szlam, Douwe Kiela, and Jason Weston. 2018. Personalizing dialogue agents: I have a dog, do you have pets too? In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2204–2213, Melbourne, Australia. Association for Computational Linguistics. Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015. Character-level convolutional networks for text classification. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc. Chujie Zheng, Sahand Sabour, Jiaxin Wen, and Minlie Huang. 2022. Augesc: Large-scale data augmentation for emotional support conversation with pretrained language models. This paper is under CC BY-NC-SA 4.0 DEED license. available on arxiv

Conclusion and Beyond: Navigating the Landscape of Errors and Feedback in AI Conversations

This paper is under CC 4.0 license. available on arxiv Authors: (1) Tariq Bontekoe, University of Groningen; (2) Dimka Karastoyanova, University of Groningen; (3) Fatih Turkmen, University of Groningen. Table of Links Abstract & Introduction Preliminaries Zero-knowledge proofs and verifiable computing Privacy-preserving computations Requirements: an application’s perspective Verifiable, privacy-preserving computing Open challenges and future directions Conclusion & References 4. Privacy-preserving computations There are different PETs that can be used to construct solutions for privacy-preserving computations. Two of them are specifically suitable for our setting: MPC and HE. Both are well-established PETs, providing flexibility and offering strong privacy guarantees, which make them excellent building blocks for verifiable privacy-preserving computations. Below we discuss both building blocks, and provide an intuitive answer to . RQ1 4.1. Secure multi-party computation MPC is a collection of techniques that allows for performing joint computations over distributed data, while keeping all input data private and revealing nothing but the computation output. Generally, there are n parties that participate in an MPC computation, and any participating party contributes to the collaboration with their respective private inputs. All n parties execute an interactive protocol to compute the joint function output from their private inputs. An MPC protocol must therefore be resistant to the fact that some participating parties may be corrupted by an adversary. As discussed in Section 2.2, there exist different security models. However, any secure MPC protocol should at least satisfy the following (informal) requirements [14], given the constraints of the used adversarial model: • Input privacy: No party should learn anything other than the function output it is assigned. Specifically, no party should learn anything about other parties’ inputs, other than what can be derived from its assigned output. • Correctness: Every party that receives a (partial) output, obtains a value that is correct with respect to the protocol specification and input data. • Independence of inputs: Corrupted parties must pick their inputs independently of the honest parties’ private inputs. There are several ways to construct an MPC protocol or framework. Below, we present the two most common constructions: secret sharing and garbled circuits. In a secret sharing approach, private data is split over multiple parties. Information is split in such a way that only predefined sets of parties can reconstruct the full information, while other (sub)sets cannot even deduce partial information. Most secret sharing schemes divide a secret s among n parties in such a way that only subsets with t or more parties can reconstruct s. Such a scheme is called a t-out-of-n-threshold scheme. Secret Sharing. Finally, we note that shares from an LSSS can be multiplied efficiently using so called Beaver’s multiplication triplets [30]. These triplets are input/function-independent and can thus be generated in a so called offline preprocessing phase. Using this approach, the remaining computations can be performed in a very efficient online phase. Many popular, modern secret sharing schemes make use of linear shares in combination with Beaver triplets or oblivious transfer. Example schemes using secret sharing are: Shamir’s secret sharing (SSS) [31] or, in the online phase, SPDZ [32] and MASCOT [33]. For an up-to-date overview on existing schemes with implementations we refer to the MP-SPDZ library [34]. Yao’s garbled circuits (GCs) [35] are a way to enable two distrusting parties to securely evaluate a function on their private input data. It requires that the underlying function is expressed as a boolean circuit consisting of 1-out-2-in gates. Garbled Circuits. One party, the garbler, generates a garbled version of the entire circuit, by garbling the individual gates. In the original implementation, a gate is garbled by assigning a unique, random label to the possible values (true, false) of each input wire, and doubly encrypting the four possible output values, under the corresponding input labels. The garbler randomly permutes the encrypted outputs and shares these with the evaluator accompanied by the random labels corresponding to the private inputs of the garbler. The evaluator then participates in an oblivious transfer (OT) protocol [36] to obtain the labels corresponding to their private inputs, without revealing those. Having received both input labels, the evaluator can correctly decrypt exactly one of the garbled outputs, thereby obtaining the true output bit(s). When a gate output is used as input to another gate, the true output will not be a bit, but rather a new random label that is used in the decryption of this other gate. An alternative construction to Yao’s GCs is the BMR framework [37]. Implementations of both and other frameworks can be found in, e.g., MP-SPDZ [34], ABY [38], or ABY 3 [39]. Most MPC frameworks are applied in a fully decentralized setting, where all parties communicate with one another directly. Many MPC schemes guarantee privacy for a given threat model, under the assumption of a certain number of honest parties, ranging from a strict majority to only one. Therefore, one might say that correctness is a largely solved problem. RQ1a: Why should we verify MPC? However, none of the above takes into account the use case in which parties that did not participate in the computation want to verify the results. In this situation, the results could be incorrect when all computing parties are colluding. The schemes are thus not publicly verifiable or publicly auditable [40], making the results untrustworthy for external parties. Another issue regarding (public) verifiability, that is often overlooked, is verification of data authenticity. Correctness of results is often only guaranteed given the assumption that input data is provided honestly. This especially plays a role when input data of parties should be the same over multiple computations, e.g., for reproducibility, or when input data should be authenticated, e.g., signed by an expert authority. In practice, both external and computation parties that want verifiably correct results, will require verification of computation and data authenticity. 4.2. Homomorphic encryption HE is a term used to denote a collection of (asymmetric) encryption schemes that allow users to perform operations on encrypted data without decrypting it first. More formally, and following [41], an HE scheme is described by four (probabilistic) polynomial-time algorithms (KeyGen, Enc, Dec, Eval): • KeyGen(1κ ) → (sk, pk, evk) is the key generation algorithm. It takes a unary representation of the security parameter κ as input and outputs a secret decryption key sk, public encryption key pk, and public evaluation key evk. While there are different ways to represent the function f in HE schemes, most constructions prefer a translation to an arithmetic circuit Cf over M. Notably, not all homomorphic encryption schemes can be used to evaluate arbitrary arithmetic circuits. Therefore, we distinguish, following [42], several types of homomorphic schemes in increasing order of evaluation capabilities. PHE is a type of homomorphic encryption that is only additively or only multiplicatively homomorphic, implying that it can only evaluate arithmetic circuits consisting solely of addition, respectively multiplication gates. In general, partially homomorphic schemes have the lowest computational cost and stable ciphertext size. Partially homomorphic encryption. SWHE constructions can evaluate arithmetic circuits consisting of both addition and multiplication gates. However, the circuits that can be evaluated may be limited in the number of operations (of either type), for example a scheme that can only evaluate circuits with a maximum multiplication depth of 2. Moreover, for SWHE there is no requirement that prevents exponential blowup of the ciphertext size.. Somewhat homomorphic encryption. LHE resembles SWHE in that it can evaluate circuits that are limited in depth d. However, since d is provided as input to KeyGen, the scheme parameters may be a function of d. Next to this, the length of the ciphertext output of the Eval algorithm may not depend on the depth d, meaning that ciphertexts do not blow up exponentially. Notice that the key sizes may still depend on the depth d and can get impractically large. Leveled homomorphic encryption. FHE schemes can evaluate arbitrary arithmetic circuits, without the schemes parameters depending upon any circuit property. This generality often comes at the cost of expensive bootstrapping algorithms after a certain number of multiplications [43]. Fully homomorphic encryption. HE is often used in a setting where one (cloud) server or central entity performs the majority of computations, for example in an outsourcing scenario. A frequently observed scenario is where all data owners use a distributed, or threshold, key generation protocol to obtain a public-private key pair where the private key is shared over all data owners [44], [45]. To perform a computation, all data owners encrypt their data under the same public key and let the central server perform the actual computation on the received ciphertexts. Due to the high computational cost of operations on homomorphically encrypted data, it is often preferred to have a single, central computing server with sufficient computational resources. RQ1b: Why should we verify HE? In most cases all parties are assumed to behave semihonestly. This assumption, however, is unrealistic in most real-world scenarios and raises significant integrity and verifiability issues. Integrity issues arise from the possibility of key-recovery attacks [46], [47], [48], whereas verifiability issues stem from the fact that the server can deviate from the requested computation. Another issue regarding verifiability, is whether external parties can verify the results of a computation that uses HE. These guarantees may be warranted in cases where external auditing is required or when results are of interest to a larger community. Therefore, verifiable solutions should provide guarantees even in the case where all data owners and the central computation server(s) are colluding. Next to this, external parties may also require guarantees concerning the integrity and authenticity of input data, which is in general not considered in existing work.

Stories, News & Mentions about PERMUTIVE

Permutive’s Stories on HackerNoon