nils-herrmann/clean_scirepeval huggingface dataset:
P-CLASSIC: A traCtabk escription logic

Knowledge representation languages invariably reflect a trade-off between expressivity and tractability. Evidence suggests that the compromise chosen by description logits is a particularly successful one. However, description logic (as for all variants of first-order logic) is severely limited in its ability to express uncertainty. In this paper, we present P-CLASSIC, a probabilistic version of the description logic CLASSIC. In addition to terminological knowledge, the language utilizes Bayesian networks to express uncertainty about the basic properties of an individual, the number of fillers for its roles, and the properties of these fillers. We provide a semantics for P-CLASSIC and an effective inference procedure for probabilistic subsumption: computing the probability that a random individual in class C is also in class D. The effectiveness of the algorithm relies on independence assumptions and on our ability to execute lifted inference: reasoning about similar individuals as a group rather than as separate ground terms. We show that the complexity of the inference algorithm is the best that can be hoped for in a language that combines description logic with Bayesian networks. In particular, if we restrict to Bayesian networks that support polynomial time inference, the complexity of our inference procedure is also polynomial time.
Probabilistic reasoning for complex systems

Reasoning under uncertainty is a central issue in artificial intelligence. Real-world agents must deal with noisy sensor information, non-deterministic effects of actions, and unpredictable exogenous events. Probabilistic reasoning methods, and Bayesian networks (BNs) in particular, have emerged as an effective and principled method for reasoning under uncertainty. BNs exploit conditional independence relationships to create natural and compact domain models, thereby supporting useful reasoning patterns, and providing effective probabilistic inference and learning algorithms. However, BNs are inherently limited by their attribute-based nature, making it difficult to apply them to large, complex domains. 
This thesis addresses the issue of representing and reasoning about probabilistic models of complex systems. We believe that the key to reasoning effectively about complex systems is to provide a language that supports the expression of system structure. We present a powerful object-based representation language, that integrates logical and probabilistic representations. Our language provides the ability to create structured, modular probabilistic models. The language maintains the key advantages of BNs, exploiting conditional independence relationships. In addition, it is capable of representing other aspects of system structure not represented in BNs. In particular, it supports the decomposition of complex systems into weakly interacting subsystems, and the reuse of models for many different components of a system. 
Another key benefit of our language is that it is very flexible. The same probabilistic representations can be applied in many different situations, with very different configurations. In fact, our language can even represent uncertainty over the system configuration itself, and integrate that uncertainty directly with uncertainty over the basic properties of objects in the system. Our framework also supports the representation of powerful recursive probability models. 
We present inference algorithms for our language that exploit the structure that can be expressed in it—not only the conditional independence structure normally exploited by BN algorithms, but also encapsulation, reuse of computation and symmetry resulting from the object-based representation. We describe an implemented system that supports representation and reasoning with models in our language, and provide experimental results demonstrating the advantages of exploiting structure in inference.
Probabilistic Relational Models

Probabilistic models provide a sound and coherent foundation for dealing with the noise and uncertainty encountered in most real-world domains. Bayesian networks are a language for representing complex probabilistic models in a compact and natural way. A Bayesian network can be used to reason about any attribute in the domain, given any set of observations. It can thus be used for a variety tasks, including prediction, explanation, and decision making. The probabilistic semantics also gives a strong foundation for the task of learning models from data. Techniques currently exist for learning both the structure and the parameters, for dealing with missing data and hidden variables, and for discovering causal structure. 
 
One of the main limitations of Bayesian networks is that they represent the world in terms of a fixed set of "attributes". Like propositional logic, they are incapable of reasoning explicitly about entities, and thus cannot represent models over domains where the set of entities and the relations between them are not fixed in advance. As a consequence, Bayesian networks are limited in their ability to model large and complex domains. Probabilistic relational models are a language for describing probabilistic models based on the significantly more expressive basis of relational logic. They allow the domain to be represented in terms of entities, their properties, and the relations between them. These models represent the uncertainty over the properties of an entity, representing its probabilistic dependence both on other properties of that entity and on properties of related entities. They can even represent uncertainty over the relational structure itself. Some of the techniques for Bayesian network learning can be generalized to this setting, but the learning problem is far from solved. Probabilistic relational models provide a new framework, and new challenges, for the endeavor of learning relational models for real-world domains.
Reinforcement Learning Using Approximate Belief States

The problem of developing good policies for partially observable Markov decision problems (POMDPs) remains one of the most challenging areas of research in stochastic planning. One line of research in this area involves the use of reinforcement learning with belief states, probability distributions over the underlying model states. This is a promising method for small problems, but its application is limited by the intractability of computing or representing a full belief state for large problems. Recent work shows that, in many settings, we can maintain an approximate belief state, which is fairly close to the true belief state. In particular, great success has been shown with approximate belief states that marginalize out correlations between state variables. In this paper, we investigate two methods of full belief state reinforcement learning and one novel method for reinforcement learning using factored approximate belief states. We compare the performance of these algorithms on several well-known problem from the literature. Our results demonstrate the importance of approximate belief state representations for large problems.
Learning the Structure of Utility Functions

Utility functions are defined over a space which is exponential in the number of variables on which the utility depends. More compact representations of the utility are possible if we make certain assumptions about additive independence among the variables. These assumptions allow the function to be decomposed into smaller components, thus reducing the number of parameters needed to specify it completely. Decomposable utility functions support more efficient inference and are easier to elicit from people. However, it can be difficult to know which decomposition is appropriate in a given setting. We hypothesize that there is some commonality to the utilities exhibited by a population of users; more precisely, we assume that the population is divided (in an unknown way) into subpopulations, each of which is statistically coherent. We can view the problem of discovering the structure of this distribution over utilities in a population as a statistical learning task. We show how we can apply Bayesian learning techniques to learn the distribution over factored utility functions from a set of fully specified utility functions elicited from a population of users. Our approach can be used for a wide range of independence types, including conditional additive independenceandgeneralized additive independence . We show how to choose a utility decomposition appropriate to a large subpopulation by performing statistical model selection, using an approximation to the Bayesian score. The factorization of the utilities in the learned model facilitates utility elicitation by allowing fully specified utility functions to be assessed using a significantly smaller number of questions. The generalization obtained from learning a model for a population of similar people allows smoother estimates of the utility function, thereby reducing the noise unavoidable in utility assessment.
Discovering the Hidden Structure of Complex Dynamic Systems

Dynamic Bayesian networks provide a compact and natural representation for complex dynamic systems. However, in many cases, there is no expert available from whom a model can be elicited. Learning provides an alternative approach for constructing models of dynamic systems. In this paper, we address some of the crucial computational aspects of learning the structure of dynamic systems, particularly those where some relevant variables are partially observed or even entirely unknown. Our approach is based on the Structural Expectation Maximization (SEM) algorithm. The main computational cost of the SEM algorithm is the gathering of expected sufficient statistics. We propose a novel approximation scheme that allows these sufficient statistics to be computed efficiently. We also investigate the fundamental problem of discovering the existence of hidden variables without exhaustive and expensive search. Our approach is based on the observation that, in dynamic systems, ignoring a hidden variable typically results in a violation of the Markov property. Thus, our algorithm searches for such violations in the data, and introduces hidden variables to explain them. We provide empirical results showing that the algorithm is able to learn the dynamics of complex systems in a computationally tractable way.
Sensors & Symbols: An Integrated Framework

The goal of this effort was to provide a unified probabilistic framework that integrates symbolic and sensory reasoning. Such a framework would allow sensor data to be analyzed in terms of high-level symbolic models. It will also allow the results of high-level analysis to guide the low-level sensor interpretation task and to help in resolving ambiguities in the sensor data. Our approach was based on the framework of probabilistic graphical models, which allows us to build systems that learn and reason with complex models, encompassing both low-level continuous sensor data and high-level symbolic concepts. Over the five years of the project, we explored two main thrusts: Inference and learning in hybrid and temporal Bayesian networks Mapping and modeling of 3D physical environments. Our progress on each of these two directions is detailed in the attached report.
Efficient Reinforcement Learning in Factored MDPs

We present a provably efficient and near-optimal algorithm for reinforcement learning in Markov decision processes (MDPs) whose transition model can be factored as a dynamic Bayesian network (DBN). Our algorithm generalizes the recent E3 algorithm of Kearns and Singh, and assumes that we are given both an algorithm for approximate planning, and the graphical structure (but not the parameters) of the DBN. Unlike the original E algorithm, our new algorithm exploits the DBN structure to achieve a running time that scales polynomially in the number of parameters of the DBN, which may be exponentially smaller than the number of global states.
Exploiting the Architecture of Dynamic Systems

Consider the problem of monitoring the state of a complex dynamic system, and predicting its future evolution. Exact algorithms for this task typically maintain a belief state, or distribution over the states at some point in time. Unfortunately, these algorithms fail when applied to complex processes such as those represented as dynamic Bayesian networks (DBNs), as the representation of the belief state grows exponentially with the size of the process. In (Boyen & Koller 1998), we recently proposed an efficient approximate tracking algorithm that maintains an approximate belief state that has a compact representation as a set of independent factors. Its performance depends on the error introduced by approximating a belief state of this process by a factored one. We informally argued that this error is low if the interaction between variables in the processes is "weak". In this paper, we give formal information-theoretic definitions for notions such as weak interaction and sparse interaction of processes. We use these notions to analyze the conditions under which the error induced by this type of approximation is small. We demonstrate several cases where our results formally support intuitions about strength of interaction.
Policy Search via Density Estimation

We propose a new approach to the problem of searching a space of stochastic controllers for a Markov decision process (MDP) or a partially observable Markov decision process (POMDP). Following several other authors, our approach is based on searching in parameterized families of policies (for example, via gradient descent) to optimize solution quality. However, rather than trying to estimate the values and derivatives of a policy directly, we do so indirectly using estimates for the probability densities that the policy induces on states at the different points in time. This enables our algorithms to exploit the many techniques for efficient and robust approximate density propagation in stochastic systems. We show how our techniques can be applied both to deterministic propagation schemes (where the MDP's dynamics are given explicitly in compact form,) and to stochastic propagation schemes (where we have access only to a generative model, or simulator, of the MDP). We present empirical results for both of these variants on complex problems.
SPOOK: A system for probabilistic object-oriented knowledge representation

In previous work, we pointed out the limitations of standard Bayesian networks as a modeling framework for large, complex domains. We proposed a new, richly structured modeling language, Object-oriented Bayesian Networks, that we argued would be able to deal with such domains. However, it turns out that OOBNs are not expressive enough to model many interesting aspects of complex domains: the existence of specific named objects, arbitrary relations between objects, and uncertainty over domain structure. These aspects are crucial in real-world domains such as battlefield awareness. In this paper, we present SPOOK, an implemented system that addresses these limitations. SPOOK implements a more expressive language that allows it to represent the battlespace domain naturally and compactly. We present a new inference algorithm that utilizes the model structure in a fundamental way, and show empirically that it achieves orders of magnitude speedup over existing approaches.
Structured Representation of Complex Stochastic Systems

This paper considers the problem of representing complex systems that evolve stochastically over time. Dynamic Bayesian networks provide a compact representation for stochastic processes. Unfortunately, they are often unwieldy since they cannot explicitly model the complex organizational structure of many real life systems: the fact that processes are typically composed of several interacting subprocesses, each of which can, in tum, be further decomposed. We propose a hierarchically structured representation language which extends both dynamic Bayesian networks and the object-oriented Bayesian network framework of [9], and show that our language allows us to describe such systems in a natural and modular way. Our language supports a natural representation for certain system characteristics that are hard to capture using more traditional frameworks. For example, it allows us to represent systems where some processes evolve at a different rate than others, or systems where the processes interact only intermittently. We provide a simple inference mechanism for our representation via translation to Bayesian networks, and suggest ways in which the inference algorithm can exploit the additional structure encoded in our representation.
Structured Probabilistic Models: Bayesian Networks and Beyond

For many years, probabilistic models were largely neglected within the AI community. Now they play a fundamental role in many areas in AI, including diagnosis, planning, and learning. One of the crucial reasons for this transition is the use of structured model-based representations such as Bayesian networks. Building on this idea, we can extend the success of probabilistic modeling to much more complex domains, ones involving many components that interact and evolve ove time. These domains are significantly beyond the scope of traditional Bayesian networks. I describe a broad class of structured probabilistic representations that extend Bayesian networks to deal with these new challenges. I argue that these representations can form the basis for agents that reason and act in complex uncertain environments.
Title: Hierarchically Classifying Documents Using Very Few Words Authors: Hierarchically Classifying Documents Using Very Few Words

The proliferation of topic hierarchies for text documents has resulted in a need for tools that automatically classify new documents within such hierarchies. One can use existing classi ers by ignoring the hierarchical structure, treating the topics as separate classes. Unfortunately, in the context of text categorization, we are faced with a large number of classes and a huge number of relevant features needed to distinguish between them. Consequently, we are restricted to using only very simple classi ers, both because of computational cost and the tendency of complex models to over t. We propose an approach that utilizes the hierarchical topic structure to decompose the classi cation task into a set of simpler problems, one at each node in the classi cation tree. As we show, each of these smaller problems can be solved accurately by focusing only on a very small set of features, those relevant to the task at hand. This set of relevant features varies widely throughout the hierarchy, so that, while the overall relevant feature set may be large, each classi er only examines a small subset. The use of reduced feature sets allows us to utilize more complex (probabilistic) models, without encountering the computational and robustness di culties described above.
Tractable Inference for Complex Stochastic Processes

The monitoring and control of any dynamic system depends crucially on the ability to reason about its current status and its future trajectory. In the case of a stochastic system, these tasks typically involve the use of a belief state--a probability distribution over the state of the process at a given point in time. Unfortunately, the state spaces of complex processes are very large, making an explicit representation of a belief state intractable. Even in dynamic Bayesian networks (DBNs), where the process itself can be represented compactly, the representation of the belief state is intractable. We investigate the idea of maintaining a compact approximation to the true belief state, and analyze the conditions under which the errors due to the approximations taken over the lifetime of the process do not accumulate to make our answers completely irrelevant. We show that the error in a belief state contracts exponentially as the process evolves. Thus, even with multiple approximations, the error in our process remains bounded indefinitely. We show how the additional structure of a DBN can be used to design our approximation scheme, improving its performance significantly. We demonstrate the applicability of our ideas in the context of a monitoring task, showing that orders of magnitude faster inference can be achieved with only a small degradation in accuracy.
Using machine learning to improve information access

The explosion of on-line information has given rise to many query-based search engines (such as Alta Vista) and manually constructed topic hierarchies (such as Yahoo!). But with the current growth rate in the amount of information, query results grow incomprehensibly large and manual classification in topic hierarchies creates an immense information bottleneck. Therefore, these tools are rapidly becoming inadequate for addressing users' information needs. 
In this dissertation, we address these problems with a system for topical information space navigation that combines the query-based and taxonomic approaches. Our system, named SONIA (Service for Organizing Networked Information Autonomously), is implemented as part of the Stanford Digital Libraries testbed. It enables the creation of dynamic hierarchical document categorizations based on the full-text of articles. Using probability theory as a formal foundation, we develop several Machine Learning methods to allow document collections to be automatically organized at a topical level. First, to generate such topical hierarchies, we employ a novel probabilistic clustering scheme that outperforms traditional methods used in both Information Retrieval and Probabilistic Reasoning. Furthermore, we develop methods for classifying new articles into such automatically generated, or existing manually generated, hierarchies. In contrast to standard classification approaches which do not make use of the taxonomic relations in a topic hierarchy, our method explicitly uses the existing hierarchical relationships between topics, leading to improvements in classification accuracy. Much of this improvement is derived from the fact that the classification decisions in such a hierarchy can be made by considering only the presence (or absence) of a small number of features (words) in each document. The choice of relevant words is made using a novel information theoretic algorithm for feature selection. Many of the components developed as part of SONIA are also general enough that they have been successfully applied to data mining problems in different domains than text. 
The integration of hierarchical clustering and classification will allow large amounts of information to be organized and presented to users in a individualized and comprehensible way. By alleviating the information bottleneck, we hope to help users with the problems of information access on the Internet.