nils-herrmann/clean_scirepeval huggingface dataset:
Asymptotic Conditional Probabilities: The Non-Unary Case

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences φ and θ, we consider the structures with domain {1, . . . , N} that satisfy θ, and compute the fraction of them in which φ is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogon’kĭı [Lio69], if there is a non-unary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogon’kĭı also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this limit: deciding whether it is well defined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to be highly undecidable. ∗Some of this research was done while all three authors were at IBM Almaden Research Center. During this work, the first author was at Stanford University, and was supported by an IBM Graduate Fellowship. This research was sponsored in part by the Air Force Office of Scientific Research (AFSC), under Contract F4962091-C-0080. The United States Government is authorized to reproduce and distribute reprints for governmental purposes. Some of this research appeared in preliminary form in a paper entitled “Asymptotic conditional probabilities for first-order logic”, which appears in  1992, pages 294–305. This paper appears in the Journal of Symbolic Logic.
Asymptotic Conditional Probabilities: The Unary Case

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences $\phi$ and $\theta$, we consider the structures with domain $\{1,\ldots, N\}$ that satisfy $\theta$, and compute the fraction of them in which $\phi$ is true. We then consider what happens to this fraction as $N$ gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogon'kii 1969), pp.\ 856--861] and by Grove, Halpern, and Koller [Res. Rep. RJ 9564, IBM Almaden Research Center, San Jose, CA, 1993], in the general case, asymptotic conditional probabilities do not always exist, and most questions relating to this issue are highly undecidable. These results, however, all depend on the assumption that $\theta$ can use a nonunary predicate symbol. Liogonkii\ 1969), pp.\ 856--861] shows that if we condition on formulas $\theta$ involving unary predicate symbols only (but no equality or constant symbols), then the asymptotic conditional probability does exist and can be effectively computed. This is the case even if we place no corresponding restrictions on $\phi$. We extend this result here to the case where $\theta$ involves equality and constants. We show that the complexity of computing the limit depends on various factors, such as the depth of quantifier nesting, or whether the vocabulary is finite or infinite. We completely characterize the complexity of the problem in the different cases, and show related results for the associated approximation problem.
The role of AI in digital libraries

The World Wide Web's growing popularity is changing the nature of libraries. Digital libraries offer a huge range of multimedia information-everything from movies, speeches, images, and photos to sounds, text, and beyond. The amount of on-line material is exploding, and the infrastructure for locating and accessing material improves almost daily. With so much and such a wide variety of information available, the problem is changing from simply locating related information to locating the most relevant information efficiently and cost effectively. In building the next generation of digital libraries, artificial intelligence will play several important roles. First, the multimedia nature of digital libraries will require moving beyond simple keyword lookup of information to much more advanced document-processing capabilities in which the system analyzes the content through text analysis, image processing, and speech recognition. Second, the availability of such a huge amount of information will require advances in the infrastructure for organizing and accessing information. A promising approach to this problem is the development of information agents. These agents can provide a variety of services-such as searching, retrieving, filtering, and negotiating-that reduce the burden on the information user or provider. Researchers from several of the major digital library projects present their vision of AI's role in building digital libraries.
Context-Specific Independence in Bayesian Networks

Bayesian networks provide a language for qualitatively representing the conditional independence properties of a distribution, This allows a natural and compact representation of the distribution, eases knowledge acquisition, and supports effective inference algorithms. It is well-known, however, that there are certain independencies that we cannot capture qualitatively within the Bayesian network structure: independencies that hold only in certain contexts, i.e., given a specific assignment of values to certain variables, In this paper, we propose a formal notion of context-specific independence (CSI), based on regularities in the conditional probability tables (CPTs) at a node. We present a technique, analogous to (and based on) d-separation, for determining when such independence holds in a given network. We then focus on a particular qualitative representation scheme--tree-structured CPTs-- for capturing CSI. We suggest ways in which this representation can be used to support effective inference algorithms, in particular, we present a structural decomposition of the resulting network which can improve the performance of clustering algorithms, and an alternative algorithm based on outset conditioning.
Toward Optimal Feature Selection

In this paper, we examine a method for feature subset selection based on Information Theory. Initially, a framework for defining the theoretically optimal, but computationally intractable, method for feature subset selection is presented. We show that our goal should be to eliminate a feature if it gives us little or no additional information beyond that subsumed by the remaining features. In particular, this will be the case for both irrelevant and redundant features. We then give an efficient algorithm for feature selection which computes an approximation to the optimal feature selection criterion. The conditions under which the approximate algorithm is successful are examined. Empirical results are given on a number of data sets, showing that the algorithm effectively handles datasets with a very large number of features.
Irrelevance and Conditioning in First-Order Probabilistic Logic

First-order probabilistic logic is a powerful knowledge representation language. Unfortunately, deductive reasoning based on the standard semantics for this logic does not support certain desirable patterns of reasoning, such as indifference to irrelevant information or substitution of constants into universal rules. We show that both these patterns rely on a first-order version of probabilistic independence, and provide semantic conditions to capture them. The resulting insight enables us to understand the effect of conditioning on independence, and allows us to describe a procedure for determining when independencies are preserved under conditioning. We apply this procedure in the context of a sound and powerful inference algorithm for reasoning from statistical knowledge bases.
Local Learning in Probabilistic Networks with Hidden Variables

Probabilistic networks which provide compact descriptions of complex stochastic relationships among several random variables are rapidly becoming the tool of choice for uncertain reasoning in artificial intelligence. We show that networks with fixed structure containing hidden variables can be learned automatically from data using a gradient-descent mechanism similar to that used in neural networks We also extend the method to networks with intensionally represented distributions, including networks with continuous variables and dynamic probabilistic networks Because probabilistic networks provide explicit representations of causal structure human experts can easily contribute pnor knowledge to the training process, thereby significantly improving the learning rate Adaptive probabilistic networks (APNs) may soon compete directly with neural networks as models in computational neuroscience as well as in industrial and financial applications.
Stochastic simulation algorithms for dynamic probabilistic networks

Stochastic simulation algorithms such as likelihood weighting often give fast, accurate approximations to posterior probabilities in probabilistic networks, and are the methods bf choice for very large networks. Unfortunately, the special characteristics of dynamic probabilistic networks (DPNs), which are used to represent stochastic temporal processes, mean that standard simulation algorithms perform very poorly. In essence, the simulation trials diverge further and further from reality as the process is observed over time. In this paper, we present simulation algorithms that use the evidence observed at each time step to push the set of trials back towards reality. The first algorithm, "evidence reversal" (ER) restructures each time slice of the DPN so that the evidence nodes for the slice become ancestors of the state variables. The second algorithm, called "survival of the fittest" sampling (SOF), "repopulates" the set of trials at each time step using a stochastic reproduction rate weighted by the likelihood of the evidence according to each trial. We compare the performance of each algorithm with likelihood weighting on the original network, and also investigate the benefits of combining the ER and SOF methods. The ER/SOF combination appears to maintain bounded error independent of the number of time steps in the simulation.
Representation Dependence in Probabilistic Inference

Non-deductive reasoning systems are often representation dependent: representing the same situation in two different ways may cause such a system to return two different answers. Some have viewed this as a significant problem. For example, the principle of maximum entropy has been subjected to much criticism due to its representation dependence. There has, however, been almost no work investigating representation dependence. In this paper, we formalize this notion and show that it is not a problem specific to maximum entropy. In fact, we show that any representation-independent probabilistic inference procedure that ignores irrelevant information is essentially entailment, in a precise sense. Moreover, we show that representation independence is incompatible with even a weak default assumption of independence. We then show that invariance under a restricted class of representation changes can form a reasonable compromise between representation independence and other desiderata, and provide a construction of a family of inference procedures that provides such restricted representation independence, using relative entropy.
An integrated stereo-based approach to automatic vehicle guidance

Proposes a new approach for vision-based longitudinal and lateral vehicle control. The novel feature of this approach is the use of binocular vision. We integrate two modules consisting of a new, domain-specific, efficient binocular stereo algorithm, and a lane marker detection algorithm, and show that the integration results in a improved performance for each of the modules. Longitudinal control is supported by detecting and measuring the distances to leading vehicles using binocular stereo. The knowledge of the camera geometry with respect to the locally planar road is used to map the images of the road plane in the two camera views into alignment. This allows us to separate image features into those lying in the road plane, e.g. lane markers, and those due to other objects which are dynamically integrated into an obstacle map. Therefore, in contrast with the previous work, we can cope with the difficulties arising from occlusion of lane markers by other vehicles. The detection and measurement of the lane markers provides us with the positional parameters and the road curvature which are needed for lateral vehicle control. Moreover, this information is also used to update the camera geometry with respect to the road, therefore allowing us to cope with the problem of vibrations and road inclination to obtain consistent results from binocular stereo.<<ETX>>
A game-theoretic classification of interactive complexity classes

Game-theoretic characterisations of complexity classes have often proved useful in understanding the power and limitations of these classes. One well-known example tells us that PSPACE can be characterized by two-person, perfect-information games in which the length of a played game is polynomial in the length of the description of the initial position [by Chandra et al., see Journal of the ACM, vol. 28, p. 114-33 (1981)]. In this paper, we investigate the connection between game theory and interactive computation. We formalize the notion of a polynomially definable game system for the language L, which, informally, consists of two arbitrarily powerful players P/sub 1/ and P/sub 2/ and a polynomial-time referee V with a common input w. Player P/sub 1/ claims that w/spl isin/L, and player P/sub 2/ claims that w/spl isin/L; the referee's job is to decide which of these two claims is true. In general, we wish to study the following question: What is the effect of varying the system's game-theoretic properties on the class of languages recognizable by polynomially definable game systems? There are many possible game-theoretic properties that we could investigate in this context. The focus of this paper is the question of what happens when one or both of the players P/sub 1/ and P/sub 2/ have imperfect information or imperfect recall. We use polynomially definable game systems to derive new characterizations of the complexity classes NEXP and coNEXP.
Constructing Flexible Dynamic Belief Networks from First-Order Probalistic Knowledge Bases

This paper investigates the power of first-order probabilistic logic (FOPL) as a representation language for complex dynamic situations. We introduce a sublanguage of FOPL and use it to provide a first-order version of dynamic belief networks. We show that this language is expressive enough to enable reasoning over time and to allow procedural representations of conditional probability tables. In particular, we define decision tree representations of conditional probability tables that can be used to decrease the size of the created belief networks. We provide an inference algorithm for our sublanguage using the paradigm of knowledge-based model construction. Given a FOPL knowledge base and a particular situation, our algorithm constructs a propositional dynamic belief network, which can be solved using standard belief network inference algorithms. In contrast to common dynamic belief networks, the structure of our networks is more flexible and better adapted to the given situation. We demonstrate the expressive power of our language and the flexibility of the resulting belief networks using a simple knowledge base modeling the propagation of infectious diseases.
Generating and Solving Imperfect Information Games

Work on game playing in AI has typically ignored games of imperfect information such as poker. In this paper we present a framework for dealing with such games. We point out several important issues that arise only in the context of imperfect information games particularly the insufficiency of a simple game tree model to represent the players information state and the need for randomization in the players optimal strategies. We describe Gala an implemented system that provides the user with a very natural and expressive language for describing games. From a game description Gala creates an augmented game tree with information sets which can be used by various algorithms in order to find optimal strategies for that game. In particular Gala implements the first practical algorithm for finding optimal randomized strategies in two player imperfect information competitive games [Koller et al 1994]. The running time of this algorithm is palinomial in the size of the game tree whereas previous algorithms were exponential. We present experimental results showing that this algorithm is also efficient in practice and can therefore form the basis for a game playing system.
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length

We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name Probabilistic Suffix Automata (PSA). Though hardness results are known for learning distributions generated by general probabilistic automata, we prove that the algorithm we present can efficiently learn distributions generated by PSAs. In particular, we show that for any target PSA, the KL-divergence between the distribution generated by the target and the distribution generated by the hypothesis the learning algorithm outputs, can be made small with high confidence in polynomial time and sample complexity. The learning algorithm is motivated by applications in human-machine interaction. Here we present two applications of the algorithm. In the first one we apply the algorithm in order to construct a model of the English language, and use this model to correct corrupted text. In the second application we construct a simple stochastic model for E. coli DNA.
Phoneme Alignment using Large Margin Techniques

We propose an alignment method which is based on recent advances in kernel machines and large margin classifiers for sequences [13, 12], which in turn build on the pioneering work of Vapnik and colleagues [15, 4]. The alignment function we devise is based on mapping the speech signal and its phoneme representation along with the target alignment into an abstract vector-space. Building on techniques used for learning SVMs, our alignment function distills to a classifier in this vector-space which is aimed at separating correct alignments from incorrect ones. We describe a simple iterative algorithm for learning the alignment function and discuss its formal properties. Experiments with the TIMIT corpus show that our method outperforms the best performing HMM-based approach .
Spikernels: Predicting Arm Movements by Embedding Population Spike Rate Patterns in Inner-Product Spaces

Inner-product operators, often referred to as kernels in statistical learning, define a mapping from some input space into a feature space. The focus of this letter is the construction of biologically motivated kernels for cortical activities. The kernels we derive, termed Spikernels, map spike count sequences into an abstract vector space in which we can perform various prediction tasks. We discuss in detail the derivation of Spikernels and describe an efficient algorithm for computing their value on any two sequences of neural population spike counts. We demonstrate the merits of our modeling approach by comparing the Spikernel to various standard kernels in the task of predicting hand movement velocities from cortical recordings. All of the kernels that we tested in our experiments outperform the standard scalar product used in linear regression, with the Spikernel consistently achieving the best performance.
Data-Driven Online to Batch Conversions

Online learning algorithms are typically fast, memory efficient, and simple to implement. However, many common learning problems fit more naturally in the batch learning setting. The power of online learning algorithms can be exploited in batch settings by using online-to-batch conversions techniques which build a new batch algorithm from an existing online algorithm. We first give a unified overview of three existing online-to-batch conversion techniques which do not use training data in the conversion process. We then build upon these data-independent conversions to derive and analyze data-driven conversions. Our conversions find hypotheses with a small risk by explicitly minimizing data-dependent generalization bounds. We experimentally demonstrate the usefulness of our approach and in particular show that the data-driven conversions consistently outperform the data-independent conversions.
Online Ranking by Projecting

We discuss the problem of ranking instances. In our framework, each instance is associated with a rank or a rating, which is an integer in 1 to k. Our goal is to find a rank-prediction rule that assigns each instance a rank that is as close as possible to the instance's true rank. We discuss a group of closely related online algorithms, analyze their performance in the mistake-bound model, and prove their correctness. We describe two sets of experiments, with synthetic data and with the Each Movie data set for collaborative filtering. In the experiments we performed, our algorithms outperform online algorithms for regression and classification applied to ranking.
Phoneme alignment based on discriminative learning

We propose a new paradigm for aligning a phoneme sequence of a speech utterance with its acoustical signal counterpart. In contrast to common HMM-based approaches, our method employs a discriminative learning procedure in which the learning phase is tightly coupled with the alignment task at hand. The alignment function we devise is based on mapping the input acousticsymbolic representations of the speech utterance along with the target alignment into an abstract vector space. We suggest a specific mapping into the abstract vector-space which utilizes standard speech features (e.g. spectral distances) as well as confidence outputs of a framewise phoneme classifier. Building on techniques used for large margin methods for predicting whole sequences, our alignment function distills to a classifier in the abstract vector-space which separates correct alignments from incorrect ones. We describe a simple iterative algorithm for learning the alignment function and discuss its formal properties. Experiments with the TIMIT corpus show that our method outperforms the current state-of-the-art approaches.
Loss Bounds for Online Category Ranking

Category ranking is the task of ordering labels with respect to their relevance to an input instance. In this paper we describe and analyze several algorithms for online category ranking where the instances are revealed in a sequential manner. We describe additive and multiplicative updates which constitute the core of the learning algorithms. The updates are derived by casting a constrained optimization problem for each new instance. We derive loss bounds for the algorithms by using the properties of the dual solution while imposing additional constraints on the dual form. Finally, we outline and analyze the convergence of a general update that can be employed with any Bregman divergence.
A New Perspective on an Old Perceptron Algorithm

We present a generalization of the Perceptron algorithm. The new algorithm performs a Perceptron-style update whenever the margin of an example is smaller than a predefined value. We derive worst case mistake bounds for our algorithm. As a byproduct we obtain a new mistake bound for the Perceptron algorithm in the inseparable case. We describe a multiclass extension of the algorithm. This extension is used in an experimental evaluation in which we compare the proposed algorithm to the Perceptron algorithm.