nils-herrmann/clean_scirepeval huggingface dataset:
Ambiguity and Constraint in Mathematical Expression Recognition

The problem of recognizing mathematical expressions differs significantly from the recognition of standard prose. While in prose significant constraints can be put on the interpretation of a character by the characters immediately preceding and following it, few such simple constraints are present in a mathematical expression. In order to make the problem tractable, effective methods of recognizing mathematical expressions will need to put intelligent constraints on the possible interpretations. The authors present preliminary results on a system for the recognition of both handwritten and typeset mathematical expressions. While previous systems perform character recognition out of context, the current system maintains ambiguity of the characters until context can be used to disambiguate the interpretation. In addition, the system limits the number of potentially valid interpretations by decomposing the expressions into a sequence of compatible convex regions. The system uses A-star to search for the best possible interpretation of an expression. We provide a new lower bound estimate on the cost to goal that improves performance significantly.
Restructuring Sparse High Dimensional Data for Effective Retrieval

The task in text retrieval is to find the subset of a collection of documents relevant to a user's information request, usually expressed as a set of words. Classically, documents and queries are represented as vectors of word counts. In its simplest form, relevance is defined to be the dot product between a document and a query vector-a measure of the number of common terms. A central difficulty in text retrieval is that the presence or absence of a word is not sufficient to determine relevance to a query. Linear dimensionality reduction has been proposed as a technique for extracting underlying structure from the document collection. In some domains (such as vision) dimensionality reduction reduces computational complexity. In text retrieval it is more often used to improve retrieval performance. We propose an alternative and novel technique that produces sparse representations constructed from sets of highly-related words. Documents and queries are represented by their distance to these sets, and relevance is measured by the number of common clusters. This technique significantly improves retrieval performance, is efficient to compute and shares properties with the optimal linear projection operator and the independent components of documents.
Structure Driven Image Database Retrieval

A new algorithm is presented which approximates the perceived visual similarity between images. The images are initially transformed into a feature space which captures visual structure, texture and color using a tree of filters. Similarity is the inverse of the distance in this perceptual feature space. Using this algorithm we have constructed an image database system which can perform example based retrieval on large image databases. Using carefully constructed target sets, which limit variation to only a single visual characteristic, retrieval rates are quantitatively compared to those of standard methods.
Bayesian Model of Surface Perception

Image intensity variations can result from several different object surface effects, including shading from 3-dimensional relief of the object, or paint on the surface itself. An essential problem in vision, which people solve naturally, is to attribute the proper physical cause, e.g. surface relief or paint, to an observed image. We addressed this problem with an approach combining psychophysical and Bayesian computational methods. 
 
We assessed human performance on a set of test images, and found that people made fairly consistent judgements of surface properties. Our computational model assigned simple prior probabilities to different relief or paint explanations for an image, and solved for the most probable interpretation in a Bayesian framework. The ratings of the test images by our algorithm compared surprisingly well with the mean ratings of our subjects.
A Non-Parametric Multi-Scale Statistical Model for Natural Images

The observed distribution of natural images is far from uniform. On the contrary, real images have complex and important structure that can be exploited for image processing, recognition and analysis. There have been many proposed approaches to the principled statistical modeling of images, but each has been limited in either the complexity of the models or the complexity of the images. We present a non-parametric multi-scale statistical model for images that can be used for recognition, image de-noising, and in a "generative mode" to synthesize high quality textures.
Alignment and Tracking using Graphics

This paper explores an optimized variant of mutual-information based alignment that uses graphics hardware to accelerate tracking of a 3D object in a video scene. It is designed for fast operation on computers that are equipped with graphics hardware. The algorithms described use a histogram-based method for computing the mutual information between object and scene. The gradient of mutual information is ascended in an eeort to estimate the pose parameters of the object within the scene. This method has linear cost in the number of pixels and the number of his-togram bins. The computer graphics techniques used to implement the registration algorithm are described. The general approach is to map the problem of computing three-dimensional scene information onto readily available computer graphics accelerator hardware. This increases the algorithm's performance signiicantly. Initial experiments are described where the experimental system is used to track moderate-speed manual motions of the test object in a high-contrast scene.
MIMIC: Finding Optima by Estimating Probability Densities

In many optimization problems, the structure of solutions reflects complex relationships between the different input parameters. For example, experience may tell us that certain parameters are closely related and should not be explored independently. Similarly, experience may establish that a subset of parameters must take on particular values. Any search of the cost landscape should take advantage of these relationships. We present MIMIC, a framework in which we analyze the global structure of the optimization landscape. A novel and efficient algorithm for the estimation of this structure is derived. We use knowledge of this structure to guide a randomized search through the solution space and, in turn, to refine our estimate ofthe structure. Our technique obtains significant speed gains over other randomized optimization procedures.
Complex Feature Recognition: A Bayesian Approach for Learning to Recognize Objects

We have developed a new Bayesian framework for visual object recognition which is based on the insight that images of objects can be modeled as a conjunction of local features. This framework can be used to both derive an object recognition algorithm and an algorithm for learning the features themselves. The overall approach, called complex feature recognition or CFR, is unique for several reasons: it is broadly applicable to a wide range of object types, it makes constructing object models easy, it is capable of identifying either the class or the identity of an object, and it is computationally efficient--requiring time proportional to the size of the image. Instead of a single simple feature such as an edge, CFR uses a large set of complex features that are learned from experience with model objects. The response of a single complex feature contains much more class information than does a single edge. This significantly reduces the number of possible correspondences between the model and the image. In addition, CFR takes advantage of a type of image processing called "oriented energy". Oriented energy is used to efficiently pre-process the image to eliminate some of the difficulties associated with changes in lighting and pose.
Image Guided Microscopic Surgery System Using Mutual-Information Based Registraion

We have developed an image guided microscopic surgery system for the navigation of surgical procedures that can overlay renderings of anatomical structures that are otherwise invisible. A new histogram-based mutual information maximization technique was applied for alignment of the scope view and three-dimensional computer graphics model. This technique doesn't require any pre-processing nor marker setting but is directly applied to the microscope view and the graphics rendering. Therefore, any special set up in image scanning or preoperative preparation is not necessary.
Alignment by maximization of mutual information

A new information-theoretic approach is presented for finding the pose of an object in an image. The technique does not require information about the surface properties of the object, besides its shape, and is robust with respect to variations of illumination. In our derivation, few assumptions are made about the nature of the imaging process. As a result, the algorithms are quite general and can foreseeably be used in a wide variety of imaging situations. Experiments are presented that demonstrate the approach in registering magnetic resonance images, aligning a complex 3D object model to real scenes including clutter and occlusion, tracking a human head in a video sequence and aligning a view-based 2D object model to real images. The method is based on a formulation of the mutual information between the model and the image. As applied in this paper, the technique is intensity-based, rather than feature-based. It works well in domains where edge or gradient-magnitude based methods have difficulty, yet it is more robust then traditional correlation. Additionally, it has an efficient implementation that is based on stochastic approximation.<<ETX>>
A Second-Order Perceptron Algorithm

Kernel-based linear-threshold algorithms, such as support vector machines and Perceptron-like algorithms, are among the best available techniques for solving pattern classification problems. In this paper, we describe an extension of the classical Perceptron algorithm, called second-order Perceptron, and analyze its performance within the mistake bound model of on-line learning. The bound achieved by our algorithm depends on the sensitivity to second-order data information and is the best known mistake bound for (efficient) kernel-based linear-threshold classifiers to date. This mistake bound, which strictly generalizes the well-known Perceptron bound, is expressed in terms of the eigenvalues of the empirical data correlation matrix and depends on a parameter controlling the sensitivity of the algorithm to the distribution of these eigenvalues. Since the optimal setting of this parameter is not known a priori, we also analyze two variants of the second-order Perceptron algorithm: one that adaptively sets the value of the parameter in terms of the number of mistakes made so far, and one that is parameterless, based on pseudoinverses.
The Robustness of the p-Norm Algorithms

We consider two on-line learning frameworks: binary classification through linear threshold functions and linear regression. We study a family of on-line algorithms, called p-norm algorithms, introduced by Grove, Littlestone and Schuurmans in the context of deterministic binary classification. We show how to adapt these algorithms for use in the regression setting, and prove worst-case bounds on the square loss, using a technique from Kivinen and Warmuth. As pointed out by Grove, et al., these algorithms can be made to approach a version of the classification algorithm Winnow as p goes to infinity; similarly they can be made to approach the corresponding regression algorithm EG in the limit. Winnow and EG are notable for having loss bounds that grow only logarithmically in the dimension of the instance space. Here we describe another way to use the p-norm algorithms to achieve this logarithmic behavior. With the way to use them that we propose, it is less critical than with Winnow and EG to retune the parameters of the algorithm as the learning task changes. Since the correct setting of the parameters depends on characteristics of the learning task that are not typically known a priori by the learner, this gives the p-norm algorithms a desireable robustness. Our elaborations yield various new loss bounds in these on-line settings. Some of these bounds improve or generalize known results. Others are incomparable.
New Preconditioners for KKT Systems of Network Flow Problems

We propose a new set of preconditioners for the iterative solution, via a preconditioned conjugate gradient (PCG) method, of the KKT systems that must be solved at each iteration of an interior point (IP) algorithm for the solution of linear min cost flow (MCF) problems. These preconditioners are based on the idea of extracting a proper triangulated subgraph of the original graph which strictly contains a spanning tree. We define a new class of triangulated graphs, called brother-connected trees (BCTs), and discuss some fast heuristics for finding BCTs of "large" weight. Computational experience shows that the new preconditioners can complement tree preconditioners, outperforming them both in iterations count and in running time on some classes of graphs.
A Polyhedral Approach for the Staff Rostering Problem

In this paper we formulate and efficiently solve staff scheduling problems for large organizations that provide continuous services to customers. We describe an integer programming approach for a class of such problems, where solutions have to obey a number of constraints related to workload balancing, shift compatibility, and distribution of days off. The formulation of the constraints is general and can be extended to different personnel management problems where staff members must cover shifts, and management must assign a fixed number of days off per week. The model maximizes staff satisfaction, expressed by positive weights for pairs of shifts in consecutive days. We consider the associated polytope and study its structure, determining some classes of inequalities that are facet inducing for special subproblems and other valid classes. We also identify a particular subproblem whose solution can be used to determine strong cuts for the complete problem. In addition, we design special branching rules that break the symmetries that arise in the solution space and have a large impact in the efficiency of the method. The validity of this approach has been ascertained by extensive computational tests; moreover, the operations research (OR) department of an airline has implemented the method to solve ground staff management problems.
Experiments with "extended crossover" approaches for network flow problems

Interior Point algorithms for Min-Cost Flow problems have been shown to be competitive with more established "combinatorial" approaches, at least on some problem classes and for very large instances. A fundamental contribution to the efficiency of these approaches is provided by the specialized crossover routines that can be implemented for this problem; they allow early termination of the IP approach, sparing it with the "nasty" iterations where the core linear systems become very difficult to solve by iterative algorithms. Because crossover procedures are nothing but one step of a combinatorial approach to MCF, we propose to extend this concept to that of extended crossover: use the initial part of an Interior Point algorithm to MCF to warm-start a "combinatorial" algorithm. We report our experiments along this line using, as "combinatorial companion" , a primal-dual algorithm for MCF that has a natural way for exploiting the information provided by the IP approach. Our results show that the efficiency of the combined approach critically depends on the accurate selection of a set of parameters among very many possible ones, for which designing accurate guidelines appears not to be an easy task; however, they also show that the combined approach can be competitive with the two original approaches in isolation, at least on some "difficult" instances.
On the Way to Perfection: Primal Operations for Stable Sets in Graphs

In this paper some operations are described that transform every graph into a perfect graph by replacing nodes with sets of new nodes. The transformation is done in such a way that every stable set in the perfect graph corresponds to a stable set in the original graph. These operations yield a purely combinatorial augmentation procedure for finding a maximum weighted stable set in a graph. Starting with a stable set in a given graph one defines a simplex type tableau whose associated basic feasible solution is the incidence vector of the stable set. In an iterative fashion, non-basic columns that would lead to pivoting into non-integral basic feasible solutions, are replaced by new columns that one can read off from special graph structures such as odd holes, odd antiholes, and various generalizations. Eventually, either a pivot leading to an integral basic feasible solution is performed, or the optimality of the current solution is proved.
On the generalization ability of on-line learning algorithms

In this paper, it is shown how to extract a hypothesis with small risk from the ensemble of hypotheses generated by an arbitrary on-line learning algorithm run on an independent and identically distributed (i.i.d.) sample of data. Using a simple large deviation argument, we prove tight data-dependent bounds for the risk of this hypothesis in terms of an easily computable statistic M/sub n/ associated with the on-line performance of the ensemble. Via sharp pointwise bounds on M/sub n/, we then obtain risk tail bounds for kernel perceptron algorithms in terms of the spectrum of the empirical kernel matrix. These bounds reveal that the linear hypotheses found via our approach achieve optimal tradeoffs between hinge loss and margin size over the class of all linear functions, an issue that was left open by previous results. A distinctive feature of our approach is that the key tools for our analysis come from the model of prediction of individual sequences; i.e., a model making no probabilistic assumptions on the source generating the data. In fact, these tools turn out to be so powerful that we only need very elementary statistical facts to obtain our final risk bounds.
Fast Feature Selection from Microarray Expression Data via Multiplicative Large Margin Algorithms

New feature selection algorithms for linear threshold functions are described which combine backward elimination with an adaptive regularization method. This makes them particularly suitable to the classification of microarray expression data, where the goal is to obtain accurate rules depending on few genes only. Our algorithms are fast and easy to implement, since they center on an incremental (large margin) algorithm which allows us to avoid linear, quadratic or higher-order programming methods. We report on preliminary experiments with five known DNA microarray datasets. These experiments suggest that multiplicative large margin algorithms tend to outperform additive algorithms (such as SVM) on feature selection tasks.
Margin-Based Algorithms for Information Filtering

In this work, we study an information filtering model where the relevance labels associated to a sequence of feature vectors are realizations of an unknown probabilistic linear function. Building on the analysis of a restricted version of our model, we derive a general filtering rule based on the margin of a ridge regression estimator. While our rule may observe the label of a vector only by classfying the vector as relevant, experiments on a real-world document filtering problem show that the performance of our rule is close to that of the on-line classifier which is allowed to observe all labels. These empirical results are complemented by a theoretical analysis where we consider a randomized variant of our rule and prove that its expected number of mistakes is never much larger than that of the optimal filtering rule which knows the hidden linear model.
A Primal Approach to the Stable Set Problem

We present a new "primal" algorithm for the stable set problem. It is based on a purely combinatorial construction that can transform every graph into a perfect graph by replacing nodes with sets of new nodes. The transformation is done in such a way that every stable set in the perfect graph corresponds to a stable set in the original graph. The algorithm keeps a formulation of the stable set problem in a simplex-type tableau whose associated basic feasible solution is the incidence vector of the best known stable set. The combinatorial graph transformations are performed by substitutions in the generators of the feasible region. Each substitution cuts off a fractional neighbor of the current basic feasible solution. We show that "dual-type" polynomial-time separation algorithms carry over to our "primal" setting. Eventually, either a nondegenerate pivot leading to an integral basic feasible solution is performed, or the optimality of the current solution is proved.
A New Approximate Maximal Margin Classification Algorithm

A new incremental learning algorithm is described which approximates the maximal margin hyperplane w.r.t. norm p ≥ 2 for a set of linearly separable data. Our algorithm, called ALMA_p (Approximate Large Margin algorithm w.r.t. norm p), takes O( (p-1) / (α2 γ2 ) ) corrections to separate the data with p-norm margin larger than (1-α)γ, where g is the (normalized) p-norm margin of the data. ALMA_p avoids quadratic (or higher-order) programming methods. It is very easy to implement and is as fast as on-line algorithms, such as Rosenblatt's Perceptron algorithm. We performed extensive experiments on both real-world and artificial datasets. We compared ALMA_2 (i.e., ALMA_p with p = 2) to standard Support vector Machines (SVM) and to two incremental algorithms: the Perceptron algorithm and Li and Long's ROMMA. The accuracy levels achieved by ALMA_2 are superior to those achieved by the Perceptron algorithm and ROMMA, but slightly inferior to SVM's. On the other hand, ALMA_2 is quite faster and easier to implement than standard SVM training algorithms. When learning sparse target vectors, ALMA_p with p > 2 largely outperforms Perceptron-like algorithms, such as ALMA_2.
Improved Lower Bounds for Learning from Noisy Examples: An Information-Theoretic Approach

This paper presents a general information-theoretic approach for obtaining lower bounds on the number of examples required for Probably Approximately Correct (PAC) learning in the presence of noise. This approach deals directly with the fundamental information quantities, avoiding a Bayesian analysis. The technique is applied to several different models, illustrating its generality and power. The resulting bounds add logarithmic factors to (or improve the constants in) previously known lower bounds.
Solving large MIP models in supply chain management by branch & cut

An assemblage of modular units are adapted to be positioned along a wall. Each of the modular units has piping at predetermined locations within the enclosure defined by the unit. The ends of the units are open and the piping extends approximately to the end of the unit where it can be coupled to the corresponding piping of another unit. Different units have different fixtures thereon as, for example, one unit has a faucet connected to the hot and cold water pipes, while another unit has gas outlets connected to the respective gas pipes, etc.