OpenRaiser/Intern-Atlas huggingface dataset:
Axiomatizing Causal Reasoning
Venue: arXiv cs.AI 2000
Year: 2000

Causal models defined in terms of a collection of equations, as defined by Pearl, are axiomatized here. Axiomatizations are provided for three successively more general classes of causal models: (1) the class of recursive theories (those without feedback), (2) the class of theories where the solutions to the equations are unique, (3) arbitrary theories (where the equations may not have solutions and, if they do, they are not necessarily unique). It is shown that to reason about causality in the most general third class, we must extend the language used by Galles and Pearl. In addition, the complexity of the decision procedures is characterized for all the languages and classes of models considered.
A Note on "Optimal Static Load Balancing in Distributed Computer Systems"
Venue: arXiv cs.DC 2000
Year: 2000

The problem of minimizing mean response time of generic jobs submitted to a heterogenous distributed computer systems is considered in this paper. A static load balancing strategy, in which decision of redistribution of loads does not depend on the state of the system, is used for this purpose. The article is closely related to a previous article on the same topic. The present article points out number of inconsistencies in the previous article, provides a new formulation, and discusses the impact of new findings, based on the improved formulation, on the results of the previous article.
An evaluation of Naive Bayesian anti-spam filtering
Venue: arXiv cs.CL 2000
Year: 2000

It has recently been argued that a Naive Bayesian classifier can be used to filter unsolicited bulk e-mail ("spam"). We conduct a thorough evaluation of this proposal on a corpus that we make publicly available, contributing towards standard benchmarks. At the same time we investigate the effect of attribute-set size, training-corpus size, lemmatization, and stop-lists on the filter's performance, issues that had not been previously explored. After introducing appropriate cost-sensitive evaluation measures, we reach the conclusion that additional safety nets are needed for the Naive Bayesian anti-spam filter to be viable in practice.
Solaris System Resource Manager: All I Ever Wanted Was My Unfair Advantage (And Why You Can't Have It!)
Venue: arXiv cs.PF 2000
Year: 2000

Traditional UNIX time-share schedulers attempt to be fair to all users by employing a round-robin style algorithm for allocating CPU time. Unfortunately, a loophole exists whereby the scheduler can be biased in favor of a greedy user running many short CPU-time processes. This loophole is not a defect but an intrinsic property of the round-robin scheduler that ensures responsiveness to the short CPU demands associated with multiple interactive users. A new generation of UNIX system resource management software constrains the scheduler to be equitable to all users regardless of the number of processes each may be running. This "fair-share" scheduling draws on the concept of pro rating resource "shares" across users and groups and then dynamically adjusting CPU usage to meet those share proportions. The simple notion of statically allocating these shares, however, belies the potential consequences for performance as measured by user response time and service level targets. We demonstrate this point by modeling several simple share allocation scenarios and analyzing the corresponding performance effects. A brief comparison of commercial system resource management implementations from HP, IBM, and SUN is also given.
The X-Files: Investigating Alien Performance in a Thin-client World
Venue: arXiv cs.PF 2000
Year: 2000

Many scientific applications use the X11 window environment; an open source windows GUI standard employing a client/server architecture. X11 promotes: distributed computing, thin-client functionality, cheap desktop displays, compatibility with heterogeneous servers, remote services and administration, and greater maturity than newer web technologies. This paper details the author's investigations into close encounters with alien performance in X11-based seismic applications running on a 200-node cluster, backed by 2 TB of mass storage. End-users cited two significant UFOs (Unidentified Faulty Operations) i) long application launch times and ii) poor interactive response times. The paper is divided into three major sections describing Close Encounters of the 1st Kind: citings of UFO experiences, the 2nd Kind: recording evidence of a UFO, and the 3rd Kind: contact and analysis. UFOs do exist and this investigation presents a real case study for evaluating workload analysis and other diagnostic tools.
Boosting Applied to Word Sense Disambiguation
Venue: arXiv cs.CL 2000
Year: 2000

In this paper Schapire and Singer's AdaBoost.MH boosting algorithm is applied to the Word Sense Disambiguation (WSD) problem. Initial experiments on a set of 15 selected polysemous words show that the boosting approach surpasses Naive Bayes and Exemplar-based approaches, which represent state-of-the-art accuracy on supervised WSD. In order to make boosting practical for a real learning domain of thousands of words, several ways of accelerating the algorithm by reducing the feature space are studied. The best variant, which we call LazyBoosting, is tested on the largest sense-tagged corpus available containing 192,800 examples of the 191 most frequent and ambiguous English words. Again, boosting compares favourably to the other benchmark algorithms.
Fuzzy data: XML may handle it
Venue: arXiv cs.IR 2000
Year: 2000

Data modeling is one of the most difficult tasks in application engineering. The engineer must be aware of the use cases and the required application services and at a certain point of time he has to fix the data model which forms the base for the application services. However, once the data model has been fixed it is difficult to consider changing needs. This might be a problem in specific domains, which are as dynamic as the healthcare domain. With fuzzy data we address all those data that are difficult to organize in a single database. In this paper we discuss a gradual and pragmatic approach that uses the XML technology to conquer more model flexibility. XML may provide the clue between unstructured text data and structured database solutions and shift the paradigm from "organizing the data along a given model" towards "organizing the data along user requirements".
Knowledge on Treelike Spaces
Venue: arXiv cs.LO 2000
Year: 2000

This paper presents a bimodal logic for reasoning about knowledge during knowledge acquisition. One of the modalities represents (effort during) non-deterministic time and the other represents knowledge. The semantics of this logic are tree-like spaces which are a generalization of semantics used for modeling branching time and historical necessity. A finite system of axiom schemes is shown to be canonically complete for the formentioned spaces. A characterization of the satisfaction relation implies the small model property and decidability for this system.
Language identification of controlled systems: Modelling, control and anomaly detection
Venue: arXiv cs.CL 2000
Year: 2000

Formal language techniques have been used in the past to study autonomous dynamical systems. However, for controlled systems, new features are needed to distinguish between information generated by the system and input control. We show how the modelling framework for controlled dynamical systems leads naturally to a formulation in terms of context-dependent grammars. A learning algorithm is proposed for on-line generation of the grammar productions, this formulation being then used for modelling, control and anomaly detection. Practical applications are described for electromechanical drives. Grammatical interpolation techniques yield accurate results and the pattern detection capabilities of the language-based formulation makes it a promising technique for the early detection of anomalies or faulty behaviour.
Ordering-based Representations of Rational Inference
Venue: arXiv cs.LO 2000
Year: 2000

Rational inference relations were introduced by Lehmann and Magidor as the ideal systems for drawing conclusions from a conditional base. However, there has been no simple characterization of these relations, other than its original representation by preferential models. In this paper, we shall characterize them with a class of total preorders of formulas by improving and extending Gardenfors and Makinson's results for expectation inference relations. A second representation is application-oriented and is obtained by considering a class of consequence operators that grade sets of defaults according to our reliance on them. The finitary fragment of this class of consequence operators has been employed by recent default logic formalisms based on maxiconsistency.
Relevance as Deduction: A Logical View of Information Retrieval
Venue: arXiv cs.IR 2000
Year: 2000

The problem of Information Retrieval is, given a set of documents D and a query q, providing an algorithm for retrieving all documents in D relevant to q. However, retrieval should depend and be updated whenever the user is able to provide as an input a preferred set of relevant documents; this process is known as em relevance feedback. Recent work in IR has been paying great attention to models which employ a logical approach; the advantage being that one can have a simple computable characterization of retrieval on the basis of a pure logical analysis of retrieval. Most of the logical models make use of probabilities or similar belief functions in order to introduce the inductive component whereby uncertainty is treated. Their general paradigm is the following: em find the nature of conditional $d\imp q$ and then define a probability on the top of it. We just reverse this point of view; first use the numerical information, frequencies or probabilities, then define your own logical consequence. More generally, we claim that retrieval is a form of deduction. We introduce a simple but powerful logical framework of relevance feedback, derived from the well founded area of nonmonotonic logic. This description can help us evaluate, describe and compare from a theoretical point of view previous approaches based on conditionals or probabilities.
Metonymy Interpretation Using X NO Y Examples
Venue: arXiv cs.CL 2000
Year: 2000

We developed on example-based method of metonymy interpretation. One advantages of this method is that a hand-built database of metonymy is not necessary because it instead uses examples in the form ``Noun X no Noun Y (Noun Y of Noun X).'' Another advantage is that we will be able to interpret newly-coined metonymic sentences by using a new corpus. We experimented with metonymy interpretation and obtained a precision rate of 66% when using this method.
Modeling Ambiguity in a Multi-Agent System
Venue: arXiv cs.CL 2000
Year: 2000

This paper investigates the formal pragmatics of ambiguous expressions by modeling ambiguity in a multi-agent system. Such a framework allows us to give a more refined notion of the kind of information that is conveyed by ambiguous expressions. We analyze how ambiguity affects the knowledge of the dialog participants and, especially, what they know about each other after an ambiguous sentence has been uttered. The agents communicate with each other by means of a TELL-function, whose application is constrained by an implementation of some of Grice's maxims. The information states of the multi-agent system itself are represented as a Kripke structures and TELL is an update function on those structures. This framework enables us to distinguish between the information conveyed by ambiguous sentences vs. the information conveyed by disjunctions, and between semantic ambiguity vs. perceived ambiguity.
A Resolution Calculus for Dynamic Semantics
Venue: arXiv cs.CL 2000
Year: 2000

This paper applies resolution theorem proving to natural language semantics. The aim is to circumvent the computational complexity triggered by natural language ambiguities like pronoun binding, by interleaving pronoun binding with resolution deduction. Therefore disambiguation is only applied to expression that actually occur during derivations.
Cluster Computing: A High-Performance Contender
Venue: arXiv cs.DC 2000
Year: 2000

When you first heard people speak of Piles of PCs, the first thing that came to mind may have been a cluttered computer room with processors, monitors, and snarls of cables all around. Collections of computers have undoubtedly become more sophisticated than in the early days of shared drives and modem connections. No matter what you call them, Clusters of Workstations (COW), Networks of Workstations (NOW), Workstation Clusters (WCs), Clusters of PCs (CoPs), clusters of computers are now filling the processing niche once occupied by more powerful stand-alone machines. This article discusses the need for cluster computing technology, Technologies, Components, and Applications, Supercluster Systems and Issues, The Need for a New Task Force, and Cluster Computing Educational Resources.
Low Ambiguity in Strong, Total, Associative, One-Way Functions
Venue: arXiv cs.CC 2000
Year: 2000

Rabi and Sherman present a cryptographic paradigm based on associative, one-way functions that are strong (i.e., hard to invert even if one of their arguments is given) and total. Hemaspaandra and Rothe proved that such powerful one-way functions exist exactly if (standard) one-way functions exist, thus showing that the associative one-way function approach is as plausible as previous approaches. In the present paper, we study the degree of ambiguity of one-way functions. Rabiand Sherman showed that no associative one-way function (over a universe having at least two elements) can be unambiguous (i.e., one-to-one). Nonetheless, we prove that if standard, unambiguous, one-way functions exist, then there exist strong, total, associative, one-way functions that are $\mathcal{O}(n)$-to-one. This puts a reasonable upper bound on the ambiguity.
On a cepstrum-based speech detector robust to white noise
Venue: arXiv cs.CL 2000
Year: 2000

We study effects of additive white noise on the cepstral representation of speech signals. Distribution of each individual cepstrum coefficient of speech is shown to depend strongly on noise and to overlap significantly with the cepstrum distribution of noise. Based on these studies, we suggest a scalar quantity, V, equal to the sum of weighted cepstral coefficients, which is able to classify frames containing speech against noise-like frames. The distributions of V for speech and noise frames are reasonably well separated above SNR = 5 dB, demonstrating the feasibility of robust speech detector based on V.
Towards Understanding the Predictability of Stock Markets from the Perspective of Computational Complexity
Venue: arXiv cs.CE 2000
Year: 2000

This paper initiates a study into the century-old issue of market predictability from the perspective of computational complexity. We develop a simple agent-based model for a stock market where the agents are traders equipped with simple trading strategies, and their trades together determine the stock prices. Computer simulations show that a basic case of this model is already capable of generating price graphs which are visually similar to the recent price movements of high tech stocks. In the general model, we prove that if there are a large number of traders but they employ a relatively small number of strategies, then there is a polynomial-time algorithm for predicting future price movements with high accuracy. On the other hand, if the number of strategies is large, market prediction becomes complete in two new computational complexity classes CPP and BCPP, which are between P^NP[O(log n)] and PP. These computational completeness results open up a novel possibility that the price graph of an actual stock could be sufficiently deterministic for various prediction goals but appear random to all polynomial-time prediction algorithms.
Exploring automatic word sense disambiguation with decision lists and the Web
Venue: arXiv cs.CL 2000
Year: 2000

The most effective paradigm for word sense disambiguation, supervised learning, seems to be stuck because of the knowledge acquisition bottleneck. In this paper we take an in-depth study of the performance of decision lists on two publicly available corpora and an additional corpus automatically acquired from the Web, using the fine-grained highly polysemous senses in WordNet. Decision lists are shown a versatile state-of-the-art technique. The experiments reveal, among other facts, that SemCor can be an acceptable (0.7 precision for polysemous words) starting point for an all-words system. The results on the DSO corpus show that for some highly polysemous words 0.7 precision seems to be the current state-of-the-art limit. On the other hand, independently constructed hand-tagged corpora are not mutually useful, and a corpus automatically acquired from the Web is shown to fail.
Formal Properties of XML Grammars and Languages
Venue: arXiv cs.DM 2000
Year: 2000

XML documents are described by a document type definition (DTD). An XML-grammar is a formal grammar that captures the syntactic features of a DTD. We investigate properties of this family of grammars. We show that every XML-language basically has a unique XML-grammar. We give two characterizations of languages generated by XML-grammars, one is set-theoretic, the other is by a kind of saturation property. We investigate decidability problems and prove that some properties that are undecidable for general context-free languages become decidable for XML-languages. We also characterize those XML-grammars that generate regular XML-languages.
Apache web server execution tracing using Third Eye
Venue: arXiv cs.SE 2000
Year: 2000

Testing of modern software systems that integrate many components developed by different teams is a difficult task. Third Eye is a framework for tracing and validating software systems using application domain events. We use formal descriptions of the constraints between events to identify violations in execution traces. Third Eye is a flexible and modular framework that can be used in different products. We present the validation of the Apache Web Server access policy implementation. The results indicate that our tool is a helpful addition to software development infrastructure.
Termination analysis of logic programs using acceptability with general term orders
Venue: arXiv cs.PL 2000
Year: 2000

We present a new approach to termination analysis of logic programs. The essence of the approach is that we make use of general term-orderings (instead of level mappings), like it is done in transformational approaches to logic program termination analysis, but that we apply these orderings directly to the logic program and not to the term-rewrite system obtained through some transformation. We define some variants of acceptability, based on general term-orderings, and show how they are equivalent to LD-termination. We develop a demand driven, constraint-based approach to verify these acceptability-variants. The advantage of the approach over standard acceptability is that in some cases, where complex level mappings are needed, fairly simple term-orderings may be easily generated. The advantage over transformational approaches is that it avoids the transformation step all together.
Extended Abstract - Model-Based Debugging of Java Programs
Venue: arXiv cs.SE 2000
Year: 2000

Model-based reasoning is a central concept in current research into intelligent diagnostic systems. It is based on the assumption that sources of incorrect behavior in technical devices can be located and identified via the existence of a model describing the basic properties of components of a certain application domain. When actual data concerning the misbehavior of a system composed from such components is available, a domain-independent diagnosis engine can be used to infer which parts of the system contribute to the observed behavior. This paper describes the application of the model-based approach to the debugging of Java programs written in a subset of Java. We show how a simple dependency model can be derived from a program, demonstrate the use of the model for debugging and reducing the required user interactions, give a comparison of the functional dependency model with program slicing, and finally discuss some current research issues.
Logic Programming Approaches for Representing and Solving Constraint Satisfaction Problems: A Comparison
Venue: arXiv cs.AI 2000
Year: 2000

Many logic programming based approaches can be used to describe and solve combinatorial search problems. On the one hand there is constraint logic programming which computes a solution as an answer substitution to a query containing the variables of the constraint satisfaction problem. On the other hand there are systems based on stable model semantics, abductive systems, and first order logic model generators which compute solutions as models of some theory. This paper compares these different approaches from the point of view of knowledge representation (how declarative are the programs) and from the point of view of performance (how good are they at solving typical problems).
Semantic interpretation of temporal information by abductive inference
Venue: arXiv cs.CL 2000
Year: 2000

Besides temporal information explicitly available in verbs and adjuncts, the temporal interpretation of a text also depends on general world knowledge and default assumptions. We will present a theory for describing the relation between, on the one hand, verbs, their tenses and adjuncts and, on the other, the eventualities and periods of time they represent and their relative temporal locations. The theory is formulated in logic and is a practical implementation of the concepts described in Ness Schelkens et al. We will show how an abductive resolution procedure can be used on this representation to extract temporal information from texts.
Automatic Termination Analysis of Programs Containing Arithmetic Predicates
Venue: arXiv cs.PL 2000
Year: 2000

For logic programs with arithmetic predicates, showing termination is not easy, since the usual order for the integers is not well-founded. A new method, easily incorporated in the TermiLog system for automatic termination analysis, is presented for showing termination in this case. The method consists of the following steps: First, a finite abstract domain for representing the range of integers is deduced automatically. Based on this abstraction, abstract interpretation is applied to the program. The result is a finite number of atoms abstracting answers to queries which are used to extend the technique of query-mapping pairs. For each query-mapping pair that is potentially non-terminating, a bounded (integer-valued) termination function is guessed. If traversing the pair decreases the value of the termination function, then termination is established. Simple functions often suffice for each query-mapping pair, and that gives our approach an edge over the classical approach of using a single termination function for all loops, which must inevitably be more complicated and harder to guess automatically. It is worth noting that the termination of McCarthy's 91 function can be shown automatically using our method. In summary, the proposed approach is based on combining a finite abstraction of the integers with the technique of the query-mapping pairs, and is essentially capable of dividing a termination proof into several cases, such that a simple termination function suffices for each case. Consequently, the whole process of proving termination can be done automatically in the framework of TermiLog and similar systems.