nils-herrmann/clean_scirepeval huggingface dataset:
On the Complexity of Optimal Multisplitting

Dynamic programming has been studied extensively, e.g., in computational geometry and string matching. It has recently found a new application in the optimal multisplitting of numerical attribute value domains.We reflect the results obtained earlier to this problem and study whether they help to shed a new light on the inherent complexity of this time-critical subtask of machine learning and data mining programs. The concept of monotonicity has come up in earlier research. It helps to explain the different asymptotic time requirements of optimal multisplitting with respect to different attribute evaluation functions. As case studies we examine Training Set Error and Average Class Entropy functions. The former has a linear-time optimization algorithm, while the latter--like most well-known attribute evaluation functions--takes a quadratic time to optimize. It is shown that neither of them fulfills the strict monotonicity condition, but computing optimal Training Set Error values can be decomposed into monotone subproblems.
Efficient Multisplitting on Numerical Data

Numerical data poses a problem to symbolic learning methods, since numerical value ranges inherently need to be partitioned into intervals for representation and handling. An evaluation function is used to approximate the goodness of different partition candidates. Most existing methods for multisplitting on numerical attributes are based on heuristics, because of the apparent efficiency advantages. We characterize a class of well-behaved cumulative evaluation functions for which efficient discovery of the optimal multisplit is possible by dynamic programming. A single pass through the data suffices to evaluate multisplits of all arities. This class contains many important attribute evaluation functions familiar from symbolic machine learning research. Our empirical experiments convey that there is no significant differences in efficiency between the method that produces optimal partitions and those that are based on heuristics. Moreover, we demonstrate that optimal multisplitting can be beneficial in decision tree learning in contrast to using the much applied binarization of numerical attributes or heuristical multisplitting.
Qualitative Knowledge to Support Reasoning About Cases

Our recipe planner for bioprocesses, Sophist, uses a semi-qualitative model to reason about cases. The model represents qualitative knowledge about the possible effects of differences between cases and about the possible causes of observed problems. Hence, the model is a crucial resource of adaptation knowledge. The model representation has been developed specifically to support CBR tasks. The essential notion in this representation is that of an influence. Representation of domain knowledge in an influence graph and a mapping of case-features onto nodes of such a graph, enable a variety of interesting reasoning tasks. Examples of such task illustrate how qualitative reasoning and case-based reasoning support each other in complex planning tasks.
On the Well-Behavedness of Important Attribute Evaluation Functions

The class of well-behaved evaluation functions simplifies and makes efficient the handling of numerical attributes; for them it suffices to concentrate on the boundary points in searching for the optimal partition. This holds always for binary partitions and also for multisplits if only the function is cumulative in addition to being well-behaved. The class of well-behaved evaluation functions is a proper superclass of convex evaluation functions. Thus, a large proportion of the most important attribute evaluation functions are wellbehaved. This paper explores the extent and boundaries of well-behaved functions. In particular, we examine C4.5’s default attribute evaluation function gain ratio, which has been known to have problems with numerical attributes. We show that gain ratio is not convex, but is still well-behaved with respect to binary partitioning. However, it cannot handle higher arity partitioning well. Our empirical experiments show that a very simple cumulative rectification to the poor bias of information gain significantly outperforms gain ratio.
Well-Behaved Evaluation Functions for Numerical Attributes

The class of well-behaved evaluation functions simplifies and makes efficient the handling of numerical attributes; for them it suffices to concentrate on the boundary points in searching for the optimal partition. This holds always for binary partitions and also for multisplits if only the function is cumulative in addition to being well-behaved. A large portion of the most important attribute evaluation functions are well-behaved. This paper surveys the class of well-behaved functions. As a case study, we examine the properties of C4.5's attribute evaluation functions. Our empirical experiments show that a very simple cumulative rectification to the poor bias of information gain significantly outperforms gain ratio.
Finding Optimal Multi-Splits for Numerical Attributes in Decision Tree Learning

Handling continuous attribute ranges remains a deeciency of top-down induction of decision trees. They require special treatment and do not t the learning scheme as well as one could hope for. Nevertheless, they are common in practical tasks and, therefore, need to be taken into account. This topic has attracted abundant attention in recent years. In particular , Fayyad and Irani showed how optimal binary partitions can be found eeciently. Later, they based a greedy heuristic multipartitioning algorithm on these results. Recently, Fulton, Kasif, and Salzberg attempted to develop algorithms for nding the optimal multi-split for a numerical attribute in one phase. We prove that, similarly as in the binary partitioning, only boundary points need to be inspected in order to nd the optimal multipartition of a numerical value range. We develop eecient algorithms for nding the optimal splitting into more than two intervals. The resulting partition is guaranteed to be optimal w.r.t. the function that is used to evaluate the attributes' utility in class prediction. We contrast our method with alternative approaches in initial empirical experiments. They show that the new method surpasses the greedy heuristic approach of Fayyad and Irani constantly in the goodness of the produced multi-split, but, with small data sets, cannot quite attain the ef-ciency of the greedy approach. Furthermore, our experiments reveal that one of the techniques proposed by Fulton, Kasif, and Salzberg is of scarce use in practical tasks, since its time consumption falls short of all demands. In addition, it categorically fails in nding the optimal multi-split because of an error in the rationale of the method.
Adaptation Cost as a Criterion for Solution Evaluation

In most case-based systems, the best case is selected by calculating similarities between the surface features of the cases. Sometimes, the most similar case is not the one that is the easiest to adapt. On the other hand, judging the adaptation effort can be tedious. In this paper, we propose case-adaptability to be used as an evaluation criterion as opposed to using it in the case-retrieval phase. Our method can be seen to combine the computational effectiveness of similarity-based retrieval with the better quality solutions of adaptation-guided retrieval.
Towards CBR for Bioprocess Planning

We present the current status of a recipe planner for bioprocesses. This case-based reasoner adapts previously successful recipes for each batch of the process. In this domain, recipe planning is difficult as actual numerical values of recipe parameters are crucial but quantitative information is scarce. However, adaptation, although far from trivial, is less complicated than planning from scratch. Like other case-based reasoners the system learns from experience, whenever the casebase grows. Therefore we expect that planners will automatically tune themselves to different plants. Case adaptation is fully automatic; process operators were never trained for this task. For adaptation, the case-based reasoner calls upon a semi-qualitative model of the process. The model, casebase and index are integrated and allow for indexing on inferences made by the model. All the software is implemented in an object-oriented framework that can be rapidly instantiated for different processes.
From Ranking to Classification: A Statistical View

In applications related to information retrieval, the goal is not only to build a classifier for deciding whether a document x among a list χ is relevant or not, but to learn a scoring function s : χ → ℝ for ranking all possible documents with respect to their relevancy. Here we show how the bipartite ranking problem boils down to binary classification with dependent data when accuracy is measured by the A U C criterion. The natural estimate of the risk being of the form of a U-statistic, consistency of methods based on empirical risk minimization is studied using the theory of U-processes. Taking advantage of this specific form, we prove that fast rates of convergence may be achieved under general noise assumptions.
Recursive Aggregation of Estimators by the Mirror Descent Algorithm with Averaging

AbstractWe consider a recursive algorithm to construct an aggregated estimator from a finite number of base decision rules in the classification problem. The estimator approximately minimizes a convex risk functional under the ℓ1-constraint. It is defined by a stochastic version of the mirror descent algorithm which performs descent of the gradient type in the dual space with an additional averaging. The main result of the paper is an upper bound for the expected accuracy of the proposed estimator. This bound is of the order 
$$C\sqrt {(\log M)/t}$$
 with an explicit and small constant factor C, where M is the dimension of the problem and t stands for the sample size. A similar bound is proved for a more general setting, which covers, in particular, the regression model with squared loss.
Generalization Error Bounds for Aggregation by Mirror Descent with Averaging

We consider the problem of constructing an aggregated estimator from a finite class of base functions which approximately minimizes a convex risk functional under the l1 constraint. For this purpose, we propose a stochastic procedure, the mirror descent, which performs gradient descent in the dual space. The generated estimates are additionally averaged in a recursive fashion with specific weights. Mirror descent algorithms have been developed in different contexts and they are known to be particularly efficient in high dimensional problems. Moreover their implementation is adapted to the online setting. The main result of the paper is the upper bound on the convergence rate for the generalization error.
Ranking and Scoring Using Empirical Risk Minimization

A general model is proposed for studying ranking problems. We investigate learning methods based on empirical minimization of the natural estimates of the ranking risk. The empirical estimates are of the form of a U-statistic. Inequalities from the theory of U-statistics and U-processes are used to obtain performance bounds for the empirical risk minimizers. Convex risk minimization methods are also studied to give a theoretical framework for ranking algorithms based on boosting and support vector machines. Just like in binary classification, fast rates of convergence are achieved under certain noise assumption. General sufficient conditions are proposed in several special cases that guarantee fast rates of convergence.
On the Bayes-risk consistency of regularized boosting methods

The probability of error of classification methods based on convex combinations of simple base classifiers by boosting algorithms is investigated. The main result of the paper is that certain regularized boosting algorithms provide Bayes-risk consistent classifiers under the sole assumption that the Bayes classifier may be approximated by a convex combination of the base classifiers. Nonasymptotic distribution-free bounds are also developed which offer interesting new insight into how boosting works and help explain its success in practical classification problems.
A Consistent Strategy for Boosting Algorithms

The probability of error of classification methods based on convex combinations of simple base classifiers by "boosting" algorithms is investigated. The main result of the paper is that certain regularized boosting algorithms provide Bayes-risk consistent classifiers under the only assumption that the Bayes classifier may be approximated by a convex combination of the base classifiers. Non-asymptotic distribution-free bounds are also developed which offer interesting new insight into how boosting works and help explain their success in practical classification problems.
Bayes-risk Consistency of Boosting

The probability of error of classification methods based on convex combinations of simple base classifiers by “boosting” algorithms is investigated. We show in this talk that certain regularized boosting algorithms provide Bayes-risk consistent classifiers under the only assumption that the Bayes classifier may be approximated by a convex combination of the base classifiers. Non-asymptotic distribution-free bounds are also developed which offer interesting new insight into how boosting works and help explain their success in practical classification problems.
The Role of Critical Sets in Vapnik-Chervonenkis Theory

In the present paper, we present the theoretical basis, as well as an empirical validation, of a protocol designed to obtain effective VC dimension estimations in the case of a simple pattern recognition issue. We first formulate particular (distributiondependent) VC bounds in which a special attention has been given to the exact exponential rate of convergence. We show indeed that the most significant contribution in such bounds is due to the “worst” elements of the model class (designated as the critical sets). We then explain how these results can lead to a rigorous framework for computer simulations involving speed-up techniques for rare event simulation (importance sampling) as well as parameter estimation (linear regression). We thus obtain accurate empirical estimates of the complexity measure and of the multiplicative constant in VC bounds. In particular, we develop the idea of alocal complexity characterization associated to every critical set.
Distribution-Dependent Vapnik-Chervonenkis Bounds

Vapnik-Chervonenkis (VC) bounds play an important role in statistical learning theory as they are the fundamental result which explains the generalization ability of learning machines. There have been consequent mathematical works on the improvement of VC rates of convergence of empirical means to their expectations over the years. The result obtained by Talagrand in 1994 seems to provide more or less the final word to this issue as far as universal bounds are concerned. Though for fixed distributions, this bound can be practically outperformed. We show indeed that it is possible to replace the 2∈2 under the exponential of the deviation term by the corresponding CramEr transform as shown by large deviations theorems. Then, we formulate rigorous distributionsensitive VC bounds and we also explain why these theoretical results on such bounds can lead to practical estimates of the effective VC dimension of learning structures.
Large Deviations Bounds for Empirical Processes

Vapnik-Chervonenkis bounds on speeds of convergence of empirical means to their expectations have been continuously improved over the years. The result obtained by M. Talagrand in 1994 11] seems to provide the nal word as far as universal bounds are concerned. However, for xed families of underlying probability distributions, the exponential rate in the deviation term can be fairly improved by the more adequate Cram er transform, as shown by large deviations theorems. Dans ce qui suit, on note ? une famille d'ensembles mesurables C et V la VC dimension de ?. On rappelle que V est un indice de complexit e combinatoire qui caract erise la capacit e de la famille d'ensembles a pulv eriser un ensemble de points. n variables al eatoires sur (R d ; B), ind ependantes et identiquement distribu ees, de m^ eme loi .
Risk Bounds and Model Selection for Regularized Least Squares

A central problem in learning theory is a quantitative assessment of the inference property of a learning algorithm ensuring consistency. A number of seminal works show that the essential feature of an algorithm should be its capacity of controlling the complexity of the solution, this is usually realized introducing a parametric family of learning algorithms in which the parameters control the generalization properties. We focus on a particularly simple algorithm, the regularized least squares. In this context the central problem is in fact the optimal choice of the regularization parameter as a function of the number of available examples, the used kernel and the a priori knowledge about the searched regression function.
Analysis of the compatibility conditions for the radon projections, with an application to seismology

In the context of the Radon approach to tomographic imaging, we face the problem of ascertaining whether or not a set of functions can be considered a set of reliable projections of an unknown function. We first review some results about the singular system of the Radon operator. Then, we define a set of parameters that allows us to evaluate the degree of compatibility of a set of projections. We apply our analysis to the seismic source imaging problem. In particular, we show that the compatibility conditions can be used for the empirical Green function retrieval.
Tomographic imaging of the earthquake source: Numerical validation in two‐dimensional approximation

We use numerical methods to solve the two-dimensional tomographic source problem, and we investigate the accuracy of the slip velocity reconstruction achieved. We perform the inversions of the source time functions (STFs) considering both the effect of errors in the source-station azimuths and the uncertainties introduced by using an empirical Green function scheme as a method for computing the STF. We also investigate the dependence of the results on the number and arrangement of the stations. We adopt two different iterative schemes to invert the Radon transform. The numerical tests show that even small errors in the data can have significant effect on the results, pointing out the ill-posedness of the considered inverse problem. The results also show that the introduction in the algorithm of a priori information, such as positivity or boundary for the reconstruction domain, improves the quality of the reconstructions and allows retrieval of qualitative information about the rupture process even in the case of poor azimuthal coverage. We test our method on two recorded earthquakes. The first one occurred in southern California on May 1, 1985 (ML = 2.4), and our results show good agreement with earlier studies. The second one, which occurred in northwestern Italy on August 23, 1996 (MD = 2.9), appears to involve a more complex, possibly bilateral rupture. The inability of the Radon approach to resolve the bilateral rupture, as we show using a synthetic test, does not allow us to draw any definitive conclusion about this earthquake.
Tomography with a finite set of projections: singular value decomposition and resolution

The problem of tomography with a finite set of projections has been the object of many investigations. In particular the formulae for the generalized solution and the singular values have been obtained in the case of equispaced projections. These results imply that the problem of determining the generalized solution is well-posed even if it may be ill-conditioned. In this paper we derive several properties of the singular values and singular functions both in the general case and in the case of equispaced projections. We use these results to identify the singular functions related to the aliasing effects in the generalized solution and to estimate the resolution achievable when these effects have been eliminated by means of a suitable filtering. It turns out that the resolution essentially depends on the number of projections and not on the noise, if the number of projections is smaller than a certain upper limit (depending on the noise), which can be quite large. In the case of equispaced projections, the resolution coincides with that estimated by the asymptotic theory even when the number of projections is rather small.
Improving Statistical MT through Morphological Analysis

In statistical machine translation, estimating word-to-word alignment probabilities for the translation model can be difficult due to the problem of sparse data: most words in a given corpus occur at most a handful of times. With a highly inflected language such as Czech, this problem can be particularly severe. In addition, much of the morphological variation seen in Czech words is not reflected in either the morphology or syntax of a language like English. In this work, we show that using morphological analysis to modify the Czech input can improve a Czech-English machine translation system. We investigate several different methods of incorporating morphological information, and show that a system that combines these methods yields the best results. Our final system achieves a BLEU score of .333, as compared to .270 for the baseline word-to-word system.
Explorer Improving Statistical MT through Morphological Analysis

In statistical machine translation, estimating word-to-word alignment probabilities for the translation model can be difficult due to the problem of sparse data: most words in a given corpus occur at most a handful of times. With a highly inflected language such as Czech, this problem can be particularly severe. In addition, much of the morphological variation seen in Czech words is not reflected in either the morphology or syntax of a language like English. In this work, we show that using morphological analysis to modify the Czech input can improve a Czech-English machine translation system. We investigate several different methods of incorporating morphological information, and show that a system that combines these methods yields the best results. Our final system achieves a BLEU score of .333, as compared to .270 for the baseline word-to-word system.
Learning OT constraint rankings using a maximum entropy model

A weakness of standard Optimality Theory is its inability to account for grammars with free variation. We describe here the Maximum Entropy model, a general statistical model, and show how it can be applied in a constraint-based linguistic framework to model and learn grammars with free variation, as well as categorical grammars. We report the results of using the MaxEnt model for learning two different grammars: one with variation, and one without. Our results are as good as those of a previous probabilistic version of OT, the Gradual Learning Algorithm (Boersma, 1997), and we argue that our model is more general and mathematically well-motivated.
A type system for statically detecting spreadsheet errors

We describe a methodology for detecting user errors in spreadsheets, using the notion of units as our basic elements of checking. We define the concept of a header and discuss two types of relationships between headers, namely is-a and has-a relationships. With these, we develop a set of rules to assign units to cells in the spreadsheet. We check for errors by ensuring that every cell has a well-formed unit. We describe an implementation of the system that allows the user to check Microsoft Excel spreadsheets. We have run our system on practical examples, and even found errors in published spreadsheets.