OpenRaiser/Intern-Atlas huggingface dataset:
Using Hierarchical Data Mining to Characterize Performance of Wireless System Configurations
Venue: arXiv cs.CE 2002
Year: 2002

This paper presents a statistical framework for assessing wireless systems performance using hierarchical data mining techniques. We consider WCDMA (wideband code division multiple access) systems with two-branch STTD (space time transmit diversity) and 1/2 rate convolutional coding (forward error correction codes). Monte Carlo simulation estimates the bit error probability (BEP) of the system across a wide range of signal-to-noise ratios (SNRs). A performance database of simulation runs is collected over a targeted space of system configurations. This database is then mined to obtain regions of the configuration space that exhibit acceptable average performance. The shape of the mined regions illustrates the joint influence of configuration parameters on system performance. The role of data mining in this application is to provide explainable and statistically valid design conclusions. The research issue is to define statistically meaningful aggregation of data in a manner that permits efficient and effective data mining algorithms. We achieve a good compromise between these goals and help establish the applicability of data mining for characterizing wireless systems performance.
A Novel Statistical Diagnosis of Clinical Data
Venue: arXiv cs.CE 2002
Year: 2002

In this paper, we present a diagnosis method of diseases from clinical data. The data are routine test such as urine test, hematology, chemistries etc. Though those tests have been done for people who check in medical institutes, how each item of the data interacts each other and which combination of them cause a disease are neither understood nor studied well. Here we attack the practically important problem by putting the data into mathematical setup and applying support vector machine. Finally we present simulation results for fatty liver, gastritis etc and discuss about their implications.
Question answering: from partitions to Prolog
Venue: arXiv cs.CL 2002
Year: 2002

We implement Groenendijk and Stokhof's partition semantics of questions in a simple question answering algorithm. The algorithm is sound, complete, and based on tableau theorem proving. The algorithm relies on a syntactic characterization of answerhood: Any answer to a question is equivalent to some formula built up only from instances of the question. We prove this characterization by translating the logic of interrogation to classical predicate logic and applying Craig's interpolation theorem.
An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures
Venue: arXiv cs.CG 2002
Year: 2002

We study algorithmic aspects of bending wires and sheet metal into a specified structure. Problems of this type are closely related to the question of deciding whether a simple non-self-intersecting wire structure (a carpenter's ruler) can be straightened, a problem that was open for several years and has only recently been solved in the affirmative. If we impose some of the constraints that are imposed by the manufacturing process, we obtain quite different results. In particular, we study the variant of the carpenter's ruler problem in which there is a restriction that only one joint can be modified at a time. For a linkage that does not self-intersect or self-touch, the recent results of Connelly et al. and Streinu imply that it can always be straightened, modifying one joint at a time. However, we show that for a linkage with even a single vertex degeneracy, it becomes NP-hard to decide if it can be straightened while altering only one joint at a time. If we add the restriction that each joint can be altered at most once, we show that the problem is NP-complete even without vertex degeneracies. In the special case, arising in wire forming manufacturing, that each joint can be altered at most once, and must be done sequentially from one or both ends of the linkage, we give an efficient algorithm to determine if a linkage can be straightened.
GridBank: A Grid Accounting Services Architecture (GASA) for Distributed Systems Sharing and Integration
Venue: arXiv cs.DC 2002
Year: 2002

Computational Grids are emerging as new infrastructure for Internet-based parallel and distributed computing. They enable the sharing, exchange, discovery, and aggregation of resources distributed across multiple administrative domains, organizations and enterprises. To accomplish this, Grids need infrastructure that supports various services: security, uniform access, resource management, scheduling, application composition, computational economy, and accountability. Many Grid projects have developed technologies that provide many of these services with an exception of accountability. To overcome this limitation, we propose a new infrastructure called Grid Bank that provides services for accounting. This paper presents requirements of Grid accountability and different models within which it can operate and proposes Grid Bank Services Architecture that meets them. The paper highlights implementation issues with detailed discussion on format for various records/database that the GridBank need to maintain. It also presents protocols for interaction between GridBank and various components within Grid computing environments.
A Random Structure for Optimum Cache Size Distributed hash table (DHT) Peer-to-Peer design
Venue: arXiv cs.NI 2002
Year: 2002

We propose a new and easily-realizable distributed hash table (DHT) peer-to-peer structure, incorporating a random caching strategy that allows for {\em polylogarithmic search time} while having only a {\em constant cache} size. We also show that a very large class of deterministic caching strategies, which covers almost all previously proposed DHT systems, can not achieve polylog search time with constant cache size. In general, the new scheme is the first known DHT structure with the following highly-desired properties: (a) Random caching strategy with constant cache size; (b) Average search time of $O(log^{2}(N))$; (c) Guaranteed search time of $O(log^{3}(N))$; (d) Truly local cache dynamics with constant overhead for node deletions and additions; (e) Self-organization from any initial network state towards the desired structure; and (f) Allows a seamless means for various trade-offs, e.g., search speed or anonymity at the expense of larger cache size.
User software for the next generation
Venue: arXiv cs.GR 2002
Year: 2002

New generations of neutron scattering sources and instrumentation are providing challenges in data handling for user software. Time-of-Flight instruments used at pulsed sources typically produce hundreds or thousands of channels of data for each detector segment. New instruments are being designed with thousands to hundreds of thousands of detector segments. High intensity neutron sources make possible parametric studies and texture studies which further increase data handling requirements. The Integrated Spectral Analysis Workbench (ISAW) software developed at Argonne handles large numbers of spectra simultaneously while providing operations to reduce, sort, combine and export the data. It includes viewers to inspect the data in detail in real time. ISAW uses existing software components and packages where feasible and takes advantage of the excellent support for user interface design and network communication in Java. The included scripting language simplifies repetitive operations for analyzing many files related to a given experiment. Recent additions to ISAW include a contour view, a time-slice table view, routines for finding and fitting peaks in data, and support for data from other facilities using the NeXus format. In this paper, I give an overview of features and planned improvements of ISAW. Details of some of the improvements are covered in other presentations at this conference.
An Algorithm for Pattern Discovery in Time Series
Venue: arXiv cs.LG 2002
Year: 2002

We present a new algorithm for discovering patterns in time series and other sequential data. We exhibit a reliable procedure for building the minimal set of hidden, Markovian states that is statistically capable of producing the behavior exhibited in the data -- the underlying process's causal states. Unlike conventional methods for fitting hidden Markov models (HMMs) to data, our algorithm makes no assumptions about the process's causal architecture (the number of hidden states and their transition structure), but rather infers it from the data. It starts with assumptions of minimal structure and introduces complexity only when the data demand it. Moreover, the causal states it infers have important predictive optimality properties that conventional HMM states lack. We introduce the algorithm, review the theory behind it, prove its asymptotic reliability, use large deviation theory to estimate its rate of convergence, and compare it to other algorithms which also construct HMMs from data. We also illustrate its behavior on an example process, and report selected numerical results from an implementation.
Encoding a Taxonomy of Web Attacks with Different-Length Vectors
Venue: arXiv cs.CR 2002
Year: 2002

Web attacks, i.e. attacks exclusively using the HTTP protocol, are rapidly becoming one of the fundamental threats for information systems connected to the Internet. When the attacks suffered by web servers through the years are analyzed, it is observed that most of them are very similar, using a reduced number of attacking techniques. It is generally agreed that classification can help designers and programmers to better understand attacks and build more secure applications. As an effort in this direction, a new taxonomy of web attacks is proposed in this paper, with the objective of obtaining a practically useful reference framework for security applications. The use of the taxonomy is illustrated by means of multiplatform real world web attack examples. Along with this taxonomy, important features of each attack category are discussed. A suitable semantic-dependent web attack encoding scheme is defined that uses different-length vectors. Possible applications are described, which might benefit from this taxonomy and encoding scheme, such as intrusion detection systems and application firewalls.
Approximating Incomplete Kernel Matrices by the em Algorithm
Venue: arXiv cs.LG 2002
Year: 2002

In biological data, it is often the case that observed data are available only for a subset of samples. When a kernel matrix is derived from such data, we have to leave the entries for unavailable samples as missing. In this paper, we make use of a parametric model of kernel matrices, and estimate missing entries by fitting the model to existing entries. The parametric model is created as a set of spectral variants of a complete kernel matrix derived from another information source. For model fitting, we adopt the em algorithm based on the information geometry of positive definite matrices. We will report promising results on bacteria clustering experiments using two marker sequences: 16S and gyrB.
Vanquishing the XCB Question: The Methodology Discovery of the Last Shortest Single Axiom for the Equivalential Calculus
Venue: arXiv cs.LO 2002
Year: 2002

With the inclusion of an effective methodology, this article answers in detail a question that, for a quarter of a century, remained open despite intense study by various researchers. Is the formula XCB = e(x,e(e(e(x,y),e(z,y)),z)) a single axiom for the classical equivalential calculus when the rules of inference consist of detachment (modus ponens) and substitution? Where the function e represents equivalence, this calculus can be axiomatized quite naturally with the formulas e(x,x), e(e(x,y),e(y,x)), and e(e(x,y),e(e(y,z),e(x,z))), which correspond to reflexivity, symmetry, and transitivity, respectively. (We note that e(x,x) is dependent on the other two axioms.) Heretofore, thirteen shortest single axioms for classical equivalence of length eleven had been discovered, and XCB was the only remaining formula of that length whose status was undetermined. To show that XCB is indeed such a single axiom, we focus on the rule of condensed detachment, a rule that captures detachment together with an appropriately general, but restricted, form of substitution. The proof we present in this paper consists of twenty-five applications of condensed detachment, completing with the deduction of transitivity followed by a deduction of symmetry. We also discuss some factors that may explain in part why XCB resisted relinquishing its treasure for so long. Our approach relied on diverse strategies applied by the automated reasoning program OTTER. Thus ends the search for shortest single axioms for the equivalential calculus.
Schedulers for Rule-based Constraint Programming
Venue: arXiv cs.DS 2002
Year: 2002

We study here schedulers for a class of rules that naturally arise in the context of rule-based constraint programming. We systematically derive a scheduler for them from a generic iteration algorithm of Apt [2000]. We apply this study to so-called membership rules of Apt and Monfroy [2001]. This leads to an implementation that yields for these rules a considerably better performance than their execution as standard CHR rules.
Sequent and Hypersequent Calculi for Abelian and Lukasiewicz Logics
Venue: arXiv cs.LO 2002
Year: 2002

We present two embeddings of infinite-valued Lukasiewicz logic L into Meyer and Slaney's abelian logic A, the logic of lattice-ordered abelian groups. We give new analytic proof systems for A and use the embeddings to derive corresponding systems for L. These include: hypersequent calculi for A and L and terminating versions of these calculi; labelled single sequent calculi for A and L of complexity co-NP; unlabelled single sequent calculi for A and L.
Thinking Adaptive: Towards a Behaviours Virtual Laboratory
Venue: arXiv cs.AI 2002
Year: 2002

In this paper we name some of the advantages of virtual laboratories; and propose that a Behaviours Virtual Laboratory should be useful for both biologists and AI researchers, offering a new perspective for understanding adaptive behaviour. We present our development of a Behaviours Virtual Laboratory, which at this stage is focused in action selection, and show some experiments to illustrate the properties of our proposal, which can be accessed via Internet.
Typical random 3-SAT formulae and the satisfiability threshold
Venue: arXiv cs.DM 2002
Year: 2002

We present a new structural (or syntatic) approach for estimating the satisfiability threshold of random 3-SAT formulae. We show its efficiency in obtaining a jump from the previous upper bounds, lowering them to 4.506. The method combines well with other techniques, and also applies to other problems, such as the 3-colourability of random graphs.
Retractions of Types with Many Atoms
Venue: arXiv cs.LO 2002
Year: 2002

We define a sound and complete proof system for affine beta-eta-retractions in simple types built over many atoms, and we state simple necessary conditions for arbitrary beta-eta-retractions in simple and polymorphic types.
Use of openMosix for parallel I/O balancing on storage in Linux cluster
Venue: arXiv cs.DC 2002
Year: 2002

In this paper I present some experiences made in the matter of I/O for Linux Clustering. In particular is illustrated the use of the package openMosix, a balancer of workload for processes running in a cluster of nodes. I describe some tests for balancing the load of I/O storage massive processes in a cluster with four components. This work is been written for the proceedings of the workshop Linux cluster: the openMosix approach held at CINECA, Bologna, Italy, on 28 november 2002.
Learning to Extract Keyphrases from Text
Venue: arXiv cs.LG 2002
Year: 2002

Many academic journals ask their authors to provide a list of about five to fifteen key words, to appear on the first page of each article. Since these key words are often phrases of two or more words, we prefer to call them keyphrases. There is a surprisingly wide variety of tasks for which keyphrases are useful, as we discuss in this paper. Recent commercial software, such as Microsoft's Word 97 and Verity's Search 97, includes algorithms that automatically extract keyphrases from documents. In this paper, we approach the problem of automatically extracting keyphrases from text as a supervised learning task. We treat a document as a set of phrases, which the learning algorithm must learn to classify as positive or negative examples of keyphrases. Our first set of experiments applies the C4.5 decision tree induction algorithm to this learning task. The second set of experiments applies the GenEx algorithm to the task. We developed the GenEx algorithm specifically for this task. The third set of experiments examines the performance of GenEx on the task of metadata generation, relative to the performance of Microsoft's Word 97. The fourth and final set of experiments investigates the performance of GenEx on the task of highlighting, relative to Verity's Search 97. The experimental results support the claim that a specialized learning algorithm (GenEx) can generate better keyphrases than a general-purpose learning algorithm (C4.5) and the non-learning algorithms that are used in commercial software (Word 97 and Search 97).
Searching for Plannable Domains can Speed up Reinforcement Learning
Venue: arXiv cs.AI 2002
Year: 2002

Reinforcement learning (RL) involves sequential decision making in uncertain environments. The aim of the decision-making agent is to maximize the benefit of acting in its environment over an extended period of time. Finding an optimal policy in RL may be very slow. To speed up learning, one often used solution is the integration of planning, for example, Sutton's Dyna algorithm, or various other methods using macro-actions. Here we suggest to separate plannable, i.e., close to deterministic parts of the world, and focus planning efforts in this domain. A novel reinforcement learning method called plannable RL (pRL) is proposed here. pRL builds a simple model, which is used to search for macro actions. The simplicity of the model makes planning computationally inexpensive. It is shown that pRL finds an optimal policy, and that plannable macro actions found by pRL are near-optimal. In turn, it is unnecessary to try large numbers of macro actions, which enables fast learning. The utility of pRL is demonstrated by computer simulations.
Technical Note: Bias and the Quantification of Stability
Venue: arXiv cs.LG 2002
Year: 2002

Research on bias in machine learning algorithms has generally been concerned with the impact of bias on predictive accuracy. We believe that there are other factors that should also play a role in the evaluation of bias. One such factor is the stability of the algorithm; in other words, the repeatability of the results. If we obtain two sets of data from the same phenomenon, with the same underlying probability distribution, then we would like our learning algorithm to induce approximately the same concepts from both sets of data. This paper introduces a method for quantifying stability, based on a measure of the agreement between concepts. We also discuss the relationships among stability, predictive accuracy, and bias.
A Theory of Cross-Validation Error
Venue: arXiv cs.LG 2002
Year: 2002

This paper presents a theory of error in cross-validation testing of algorithms for predicting real-valued attributes. The theory justifies the claim that predicting real-valued attributes requires balancing the conflicting demands of simplicity and accuracy. Furthermore, the theory indicates precisely how these conflicting demands must be balanced, in order to minimize cross-validation error. A general theory is presented, then it is developed in detail for linear regression and instance-based learning.
Contextual Normalization Applied to Aircraft Gas Turbine Engine Diagnosis
Venue: arXiv cs.LG 2002
Year: 2002

Diagnosing faults in aircraft gas turbine engines is a complex problem. It involves several tasks, including rapid and accurate interpretation of patterns in engine sensor data. We have investigated contextual normalization for the development of a software tool to help engine repair technicians with interpretation of sensor data. Contextual normalization is a new strategy for employing machine learning. It handles variation in data that is due to contextual factors, rather than the health of the engine. It does this by normalizing the data in a context-sensitive manner. This learning strategy was developed and tested using 242 observations of an aircraft gas turbine engine in a test cell, where each observation consists of roughly 12,000 numbers, gathered over a 12 second interval. There were eight classes of observations: seven deliberately implanted classes of faults and a healthy class. We compared two approaches to implementing our learning strategy: linear regression and instance-based learning. We have three main results. (1) For the given problem, instance-based learning works better than linear regression. (2) For this problem, contextual normalization works better than other common forms of normalization. (3) The algorithms described here can be the basis for a useful software tool for assisting technicians with the interpretation of sensor data.
The Identification of Context-Sensitive Features: A Formal Definition of Context for Concept Learning
Venue: arXiv cs.LG 2002
Year: 2002

A large body of research in machine learning is concerned with supervised learning from examples. The examples are typically represented as vectors in a multi-dimensional feature space (also known as attribute-value descriptions). A teacher partitions a set of training examples into a finite number of classes. The task of the learning algorithm is to induce a concept from the training examples. In this paper, we formally distinguish three types of features: primary, contextual, and irrelevant features. We also formally define what it means for one feature to be context-sensitive to another feature. Context-sensitive features complicate the task of the learner and potentially impair the learner's performance. Our formal definitions make it possible for a learner to automatically identify context-sensitive features. After context-sensitive features have been identified, there are several strategies that the learner can employ for managing the features; however, a discussion of these strategies is outside of the scope of this paper. The formal definitions presented here correct a flaw in previously proposed definitions. We discuss the relationship between our work and a formal definition of relevance.
Robust Classification with Context-Sensitive Features
Venue: arXiv cs.LG 2002
Year: 2002

This paper addresses the problem of classifying observations when features are context-sensitive, especially when the testing set involves a context that is different from the training set. The paper begins with a precise definition of the problem, then general strategies are presented for enhancing the performance of classification algorithms on this type of problem. These strategies are tested on three domains. The first domain is the diagnosis of gas turbine engines. The problem is to diagnose a faulty engine in one context, such as warm weather, when the fault has previously been seen only in another context, such as cold weather. The second domain is speech recognition. The context is given by the identity of the speaker. The problem is to recognize words spoken by a new speaker, not represented in the training set. The third domain is medical prognosis. The problem is to predict whether a patient with hepatitis will live or die. The context is the age of the patient. For all three domains, exploiting context results in substantially more accurate classification.