nils-herrmann/clean_scirepeval huggingface dataset:
Approximate Dimension Equalization in Vector-based Information Retrieval

Vector-based information retrieval methods such as the vector space model (VSM), latent semantic indexing (LSI), and the generalized vector space model (GVSM) represent both queries and documents by high-dimensional vectors learned from analyzing a training corpus of text. VSM scales well to large collections, but cannot represent term–term correlations, which prevents it from being used in translingual retrieval. GVSM and LSI can represent term–term correlations, but do not scale well to very large retrieval collections. We present a novel method we call approximate dimension equalization (ADE) that combines ideas from VSM, LSI, and GVSM to produce a method that performs well on large collections, scales well computationally, and can represent term–term correlations. We compare the performance of ADE to the other methods on both large and small collections of both monolingual and bilingual text. ADE outperforms all other methods on large bilingual collections, and performs close to the best in all other cases.
Matrix computations for query expansion in information retrieval

Information retrieval (IR) is the task of identifying information items (documents) that are relevant to a user query from a collection. The most popular IR research technique, the vector space model (VSM), is a word-matching approach: it uses the words in common between the query and the document as a basic way of determining their similarity. Because the same concept can be expressed in the query and document using very different vocabularies, synonymy can cause a document to be judged as irrelevant by VSM. 
Query-expansion methods deal with this problem by automatically supplying the query with additional words that are related to those already in it. Latent semantic indexing (LSI) is a statistical method that derives term associations through a reduced dimensional singular value decomposition (SVD) of a matrix formed from the collection. LSI has equaled or outperformed VSM on many relatively small retrieval collections. But, with the growing size of modern information repositories, LSI has failed to demonstrate its advantage over traditional word-matching methods on some of these large corpora. 
In this work, I provide evidence that LSI is not reaching its potential for large collections because existing SVD implementations are not able to compute a sufficiently large number of dimensions. I establish a unified framework of vector-based information retrieval called dimension equalization . Through this, I present approximate dimension equalization (ADE), a method that “extrapolates” the result of a high-dimensional SVD based on a relatively small number of computed dimensions. Experiments indicate that ADE improves retrieval performance over LSI and has great utility in cross-language applications. 
I also investigate sampling approaches to reducing LSI computation, which use only a subset of the document collection to build LSI term-associations. My focus is on local LSI, a variation of the ever-popular local feedback approaches in the IR community. This method computes an SVD on a subset of documents that are related to the query. Experiments show that local LSI outperforms not only the global sampling methods but also the baseline VSM or LSI without sampling. I extend the existing local LSI approach to cross-language retrieval and present its high-quality results.
Algorithm Selection using Reinforcement Learning

Many computational problems can be solved by multiple algorithms, with different algorithms fastest for different problem sizes, input distributions, and hardware characteristics. We consider the problem of algorithm selection: dynamically choose an algorithm to attack an instance of a problem with the goal of minimizing the overall execution time. We formulate the problem as a kind of Markov decision process (MDP), and use ideas from reinforcement learning to solve it. This paper introduces a kind of MDP that models the algorithm selection problem by allowing multiple state transitions. The well known Q-learning algorithm is adapted for this case in a way that combines both Monte-Carlo and Temporal Difference methods. Also, this work uses, and extends in a way to control problems, the Least-Squares Temporal Difference algorithm (LSTD(0)) of Boyan. The experimental study focuses on the classic problems of order statistic selection and sorting. The encouraging results reveal the potential of applying learning methods to traditional computational problems.
A Comparison of Two Corpus-Based Methods for Translingual Information Retrieval

In translingual information retrieval (TIR), ad hoc queries in any of a set of languages can be used to retrieve documents in any of a set of languages. Classical informationretrieval methods such as the vector-space model cannot be applied to TIR because they base similarity on the overlap of terms between queries and documents|this is typically zero in TIR. The generalized vector-space model (GVSM) and latent semantic indexing (LSI) are two variations of the vector-space model that make comparisons outside of term space. For this reason, both can be and have been applied to TIR. In this paper, we report on a series of experiments comparing the performance of GVSM and LSI on monolingual and translingual retrieval tasks. We nd that the performance of both methods depends crucially on parameter settings, that LSI performs better, and that GVSM runs more quickly.
Reinforcement Learning for Algorithm Selection

Many computational problems can be solved by multiple algorithms, with different algorithms fastest for different problem sizes, input distributions, and hardware characteristics. We consider the problem of algorithm selection: dynamically choose an algorithm to attack an instance or subinstances (due to recursive calls) of a problem with the goal of minimizing the overall execution time. We formulate the problem as a kind of Markov Decision Process (MDP), and use ideas from reinforcement learning (RL) to solve it. The process’ state consists of a set of instance features, such as problem size. Actions are the different algorithms we can choose from. Non-recursive algorithms are terminal in that they solve the problem completely (terminal state). Recursive algorithms create subproblems and therefore cause transitions to other states, making the task a sequential decision task. The immediate cost of a decision is the real time taken for executing the selected algorithm on the current instance, excluding time taken in recursive calls. Thus, the total (undiscounted) cost during an episode is the time taken to solve the problem. The goal is a policy that minimizes the total cost/time. This process differs from a standard MDP as it allows one-to-many state transitions (multiple recursive calls at one level). Our initial experiments focus on the problem of order statistic selection: given an array of (unordered) numbers and some index , select the number that would rank -th if the array were sorted. We picked two algorithms such that neither is best in all cases, otherwise learning would not help. DETERMINISTIC SELECT ( )i s an recursive algorithm and HEAP SELECT ( )i s an algorithm
The AAAI Fall Symposia

The Association for the Advancement of Artificial Intelligence (AAAI) held its 1998 Fall Symposium Series on 23 to 25 October at the Omni Rosen Hotel in Orlando,  This article contains summaries of seven of the symposia that were conducted: (1) Cognitive Robotics; (2) Distributed, Continual Planning; (3) Emotional and Intelligent: The Tangled Knot of Cognition; (4) Integrated Planning for Autonomous Agent Architectures; (5) Planning with Partially Observable Markov Decision Processes; (6) Reasoning with Visual and Diagrammatic Representations; and (7)  Developing Connections.
robabilistic Propositional Planning : Representations and Complexity

Many representations for probabilistic propositional planning problems have been studied. This paper reviews several such representations and shows that, in spite of superficial differences between the represent at ions, they are “expressively equivalent ,” meaning that planning problems specified in one representation can be converted to equivalent planning problems in any of the other representations with at most a polynomial factor increase in the size of the resulting representation and the number of steps needed to reach the goal with sufficient probability. The paper proves that the computational complexity of determining whether a successful plan exists for planning problems expressed in any of these representations is EXPTIME-complete and PSPACE-complete when plans are restricted to take a polynomial number of
Proverb: the Probabilistic Cruciverbalist Proverb: the Probabilistic Cruciverbalist

We attacked the problem of solving crossword puzzles by computer: given a set of clues and a crossword grid, try to maximize the number of words correctly lled in. After an analysis of a large collection of puzzles, we decided to use an open architecture in which independent programs specialize in solving speciic types of clues, drawing on ideas from information retrieval, database search, and machine learning. Each expert module generates a (possibly empty) candidate list for each clue, and the lists are merged together and placed into the grid by a centralized solver. We used a probabilistic representation throughout the system as a common interchange language between subsystems and to drive the search for an optimal solution. Proverb, the complete system, averages 95.3% words correct and 98.1% letters correct in under 15 minutes per puzzle on a sample of 370 puzzles taken from the New York Times and several other puzzle sources. This corresponds to missing roughly 3 words or 4 letters on a daily 15 15 puzzle, making Proverb a better-than-average cruciverbalist (crossword solver).
A Unified Analysis of Value-Function-Based Reinforcement-Learning Algorithms

Reinforcement learning is the problem of generating optimal behavior in a sequential decision-making environment given the opportunity of interacting with it. Many algorithms for solving reinforcement-learning problems work by computing improved estimates of the optimal value function. We extend prior analyses of reinforcement-learning algorithms and present a powerful new theorem that can provide a unified analysis of such value-function-based reinforcement-learning algorithms. The usefulness of the theorem lies in how it allows the convergence of a complex asynchronous reinforcement-learning algorithm to be proved by verifying that a simpler synchronous algorithm converges. We illustrate the application of the theorem by analyzing the convergence of Q-learning, model-based reinforcement learning, Q-learning with multistate updates, Q-learning for Markov games, and risk-sensitive reinforcement learning.
Solving Crosswords with PROVERB

We attacked the problem of solving crossword puzzles by computer: Given a set of clues and a crossword grid, try to maximize the number of words correctly filled in. PROVERB, the probabilistic crueiverbalist, separates the problem into two, more familiar subproblems: candidate generation and grid filling. In candidate generation, each clue is treated as a type of query to an information retrieval system, and relevant words of the correct length are returned along with confidence scores. In grid filling, the candidate words are fit into the puzzle grid to maximize an overall confidence score using a combination of ideas from belief network inference and constraint satisfaction. For our demonstration, we will have an interactive version of the candidate-generation process available via the web, and will also give people an opportunity to go head-to-head against PROVERB in solving complete puzzles.
Constraint Satisfaction withProbabilistic Preferences on Variable

Crossword puzzle solving is a classic constraint satisfaction problem, but, when solving a real puzzle, the mapping from clues to variable domains is not perfectly crisp. At best, clues induce a probability distribution over viable targets, which must somehow be respected along with the constraints of the puzzle. Motivated by this type of problem, we provide a formal model of constraint satisfaction with probabilistic preferences on variable values. Two natural optimization problems are deened for this model: maximizing the probability of a correct solution, and maximizing the number of correct words (variable values) in the solution. We provide an eecient iterative approximation for the latter based on dynamic programming and present very encouraging results on a collection of real and artiicial crossword puzzles.
Initial Experiments in Stochastic Satisfiability

This paper looks at the rich intersection between satisfiability problems and probabilistic models, opening the door for the use of satisfiability approaches in probabilistic domains. A generic stochastic satisfiability problem is examined, which can function for probabilistic domains as SAT does for deterministic domains. The paper defines a Davis-Putnam-Logemann-Loveland-style procedure for solving stochastic satisfiability problems, and reports on a preliminary empirical exploration of the complexity of the algorithm for a collection of randomly generated probabilistic problems. The results exhibit the familiar easyhardest-hard pattern for the difficulty of random SAT formulae. Special cases of the stochastic satisfiability problem lie in different complexity classes, and one counterintuitive result is that the computational complexity and the empirical complexity of the problems examined do not track each other exactly-problems in the hardest complexity class are not the hardest to solve.
Constraint Satisfaction with Probabilistic Preferences on Variable Values

Crossword puzzle solving is a classic constraint satisfaction problem, but, when solving a real puzzle, the mapping from clues to variable domains is not perfectly crisp. At best, clues induce a probability distribution over viable targets, which must somehow be respected along with the constraints of the puzzle. Motivated by this type of problem, we provide a formal model of constraint satisfaction with probabilistic preferences on variable values. Two natural optimization problems are de ned for this model: maximizing the probability of a correct solution, and maximizing the number of correct words (variable values) in the solution. We provide an e cient iterative approximation for the latter based on dynamic programming and present very encouraging results on a collection of real and arti cial crossword puzzles.
PROVERB: The Probabilistic Cruciverbalist

We attacked the problem of solving crossword puzzles by computer: given a set of clues and a crossword grid, try to maximize the number of words correctly filled in. In our system, "expert modules" specialize in solving specific types of clues, drawing on ideas from information retrieval, database search, and machine learning. Each expert module generates a (possibly empty) candidate list for each clue, and the lists are merged together and placed into the grid by a centralized solver. We used a probabilistic representation throughout the system as a common interchange language between subsystems and to drive the search for an optimal solution. PROVERB, the complete system, averages 95.3% words correct and 98.1 % letters correct in under 15 minutes per puzzle on a sample of 370 puzzles taken from the New York Times and several other puzzle sources. This corresponds to missing roughly 3 words or 4 letters on a daily 15 × 15 puzzle, making PROVERB a better-than-average cruciverbalist (crossword solver).
Solving Crossword Puzzles as Probabilistic Constraint Satisfaction

Crossword puzzle solving is a classic constraint satisfaction problem, but, when solving a real puzzle, the mapping from clues to variable domains is not perfectly crisp. At best, clues induce a probability distribution over viable targets, which must somehow be respected along with the constraints of the puzzle. Motivated by this type of problem, we describe a formal model of constraint satisfaction with probabilistic preferences on variable values. Two natural optimization problems are defined for this model: maximizing the probability of a correct solution, and maximizing the number of correct words (variable values) in the solution. To the latter, we apply an efficient iterative approximation equivalent to turbo decoding and present results on a collection of real and artificial crossword puzzles.
MAXPLAN: A New Approach to Probabilistic Planning

Classical artificial intelligence planning techniques can operate in large domains but traditionally assume a deterministic universe. Operations research planning techniques can operate in probabilistic domains but break when the domains approach realistic sizes, MAX-PLAN is a new probabilistic planning technique that aims at combining the best of these two worlds, MAX-PLAN converts a planning instance into an E-MAJSAT instance, and then draws on techniques from Boolean satisfiability and dynamic programming to solve the E-MAJSAT instance. E-MAJSAT is an NPPP-complete problem that is essentially a probabilistic version of SAT. MAXPLAN performs as much as an order of magnitude better on some standard stochastic test problems than BURIDAN—a state-of-the-art probabilistic planner—and scales better on one test problem than two algorithms based on dynamic programming.
Automatic Cross-Language Information Retrieval Using Latent Semantic Indexing

We describe a method for fully automated cross-language document retrieval in which no query translation is required. Queries in one language can retrieve documents in other languages (as well as the original language). This is accomplished by a method that automatically constructs a multi-lingual semantic space using Latent Semantic Indexing (LSI). We present strong preliminary test results for our cross-language LSI (CL-LSI) method for a French-English collection. We also provide some evidence that this automatic method performs comparably to a retrieval method based on machine translation (MT-LSI).
XGvis: Interactive Data Visualization with Multidimensional Scaling

We discuss interactive techniques for multidimensional scaling (MDS) and a system, named \XGvis", that implements these techniques. MDS is a method for visualizing proximity data, that is, data where objects are characterized by dissimilarity values for all pairs of objects. MDS constructs maps of these objects in IR k by interpreting the dissimilarities as distances. MDS in its conventional batch implementations is prone to uncertainties with regard to 1) local minima in the underlying optimization, 2) sensitivity to the choice of the optimization criterion, 3) artifacts in point conngurations, and 4) local inadequacy of the point conngurations. These uncertainties will be addressed by the following interactive techniques: 1) algorithm animation, random restarts, and manual editing of conngurations, 2) interactive control over parameters that determine the criterion and its minimization, 3) diagnostics for pinning down artifactual point conngurations, and 4) restricting MDS to subsets of objects and subsets of pairs of objects. MDS was originally developed for the social sciences, but it is now also used for laying out graphs. Graph layout is usually done in 2D, but we allow layouts in arbitrary dimensions. We permit missing values, which can be used to implement multidimensional unfolding. We show applications to the mapping of computer usage data, to the dimension reduction of marketing segmentation data, to the layout of mathematical graphs and social network graphs, and nally to the reconstruction of molecules in nano technology. 1 XGvis uses the XGobi system for visualizing point conngurations. The XGvis system, which implements these techniques, is freely available with the XGobi distribution from
Learning a Language-Independent Representation for Terms from a Partially Aligned Corpus

Cross-language latent semantic indexing is a method that learns useful language-independent vector representations of terms through a statistical analysis of a document-aligned text. This is accomplished by taking a collection of, say, English paragraphs and their translations in Spanish and processing them by singular value decomposition to yield a high-dimensional vector representation for each term in the collection. These term vectors have the property that semantically similar terms have vectors with high cosine measure, regardless of their source language. In the present work, we extend this approach to the case in which English-Spanish translations are not available, but instead, translations for documents in both languages are available in a third \bridge" language, say, French. Thus, although no aligned English-Spanish documents are used, our method creates a representation in which English and Spanish terms can be compared. The resulting vector representation of terms can be useful in natural language applications such as cross-language information retrieval and machine translation.
The Computational Complexity of Probabilistic Planning

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NPPP, co-NPPP, and PSPACE. In the process of proving that certain planning problems are complete for NPPP, we introduce a new basic NPPP -complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.
Using Caching to Solve Larger Probabilistic Planning Problems

Probabilistic planning algorithms seek effective plans for large, stochastic domains. MAXPLAN is a recently developed algorithm that converts a planning problem into an E-MAJSAT problem, an NpPP-complete problem that is essentially a probabilistic version of SAT, and draws on techniques from Boolean satisfiability and dynamic programming to solve the E-MAJSAT problem. This solution method is able to solve planning problems at state-of-the-art speeds, but it depends on the ability to store a value for each CNF subformula encountered in the solution process and is therefore quite memory intensive; searching for moderate-size plans even on simple problems can exhaust memory. This paper presents two techniques, based on caching, that overcome this problem without significant performance degradation. The first technique uses an LRU cache to store a fixed number of subformula values. The second technique uses a heuristic based on a measure of subformula difficulty to selectively save the values of only those subformulas whose values are sufficiently difficult to compute and are likely to be reused later in the solution process. We report results for both techniques on a stochastic test problem.
Large-Scale Planning Under Uncertainty : A Survey

Our research area is planning under uncertainty, that is, making sequences of decisions in the face of imperfect information. We are particularly concerned with developing planning algorithms that perform well in large, real-world domains. This paper is a brief introduction to this area of research, which draws upon results from operations research (Markov decision processes), machine learning (reinforcement learning), and artiicial intelligence (planning). Although techniques for planning under uncertainty are extremely promising for tackling real-world problems, there is a real need at this stage to look at large-scale applications to provide direction to future development and analysis.