title: Representation results for defeasible logic

abstract:
  The importance of transformations and normal forms in logic programming, and
generally in computer science, is well documented. This paper investigates
transformations and normal forms in the context of Defeasible Logic, a simple
but efficient formalism for nonmonotonic reasoning based on rules and
priorities. The transformations described in this paper have two main benefits:
on one hand they can be used as a theoretical tool that leads to a deeper
understanding of the formalism, and on the other hand they have been used in
the development of an efficient implementation of defeasible logic.


title: Advances in domain independent linear text segmentation

abstract:
  This paper describes a method for linear text segmentation which is twice as
accurate and over seven times as fast as the state-of-the-art (Reynar, 1998).
Inter-sentence similarity is replaced by rank in the local context. Boundary
locations are discovered by divisive clustering.


title: Information Extraction from Broadcast News

abstract:
  This paper discusses the development of trainable statistical models for
extracting content from television and radio news broadcasts. In particular we
concentrate on statistical finite state models for identifying proper names and
other named entities in broadcast speech. Two models are presented: the first
represents name class information as a word attribute; the second represents
both word-word and class-class transitions explicitly. A common n-gram based
formulation is used for both models. The task of named entity identification is
characterized by relatively sparse training data and issues related to
smoothing are discussed. Experiments are reported using the DARPA/NIST Hub-4E
evaluation for North American Broadcast News.


title:
A Theory of Universal Artificial Intelligence based on Algorithmic
  Complexity

abstract:
  Decision theory formally solves the problem of rational agents in uncertain
worlds if the true environmental prior probability distribution is known.
Solomonoff's theory of universal induction formally solves the problem of
sequence prediction for unknown prior distribution. We combine both ideas and
get a parameterless theory of universal Artificial Intelligence. We give strong
arguments that the resulting AIXI model is the most intelligent unbiased agent
possible. We outline for a number of problem classes, including sequence
prediction, strategic games, function minimization, reinforcement and
supervised learning, how the AIXI model can formally solve them. The major
drawback of the AIXI model is that it is uncomputable. To overcome this
problem, we construct a modified algorithm AIXI-tl, which is still effectively
more intelligent than any other time t and space l bounded agent. The
computation time of AIXI-tl is of the order tx2^l. Other discussed topics are
formal definitions of intelligence order relations, the horizon problem and
relations of the AIXI theory to other AI approaches.


title:
Programming in Alma-0, or Imperative and Declarative Programming
  Reconciled

abstract:
  In (Apt et al, TOPLAS 1998) we introduced the imperative programming language
Alma-0 that supports declarative programming. In this paper we illustrate the
hybrid programming style of Alma-0 by means of various examples that complement
those presented in (Apt et al, TOPLAS 1998). The presented Alma-0 programs
illustrate the versatility of the language and show that ``don't know''
nondeterminism can be naturally combined with assignment.


title: Searching for Spaceships

abstract:
  We describe software that searches for spaceships in Conway's Game of Life
and related two-dimensional cellular automata. Our program searches through a
state space related to the de Bruijn graph of the automaton, using a method
that combines features of breadth first and iterative deepening search, and
includes fast bit-parallel graph reachability and path enumeration algorithms
for finding the successors of each state. Successful results include a new 2c/7
spaceship in Life, found by searching a space with 2^126 states.


title: Mathematical Software: Past, Present, and Future

abstract:
  This paper provides some reflections on the field of mathematical software on
the occasion of John Rice's 65th birthday. I describe some of the common themes
of research in this field and recall some significant events in its evolution.
Finally, I raise a number of issues that are of concern to future developments.


title: Exact Phase Transitions in Random Constraint Satisfaction Problems

abstract:
  In this paper we propose a new type of random CSP model, called Model RB,
which is a revision to the standard Model B. It is proved that phase
transitions from a region where almost all problems are satisfiable to a region
where almost all problems are unsatisfiable do exist for Model RB as the number
of variables approaches infinity. Moreover, the critical values at which the
phase transitions occur are also known exactly. By relating the hardness of
Model RB to Model B, it is shown that there exist a lot of hard instances in
Model RB.


title: On Redundancy Elimination Tolerant Scheduling Rules

abstract:
  In (Ferrucci, Pacini and Sessa, 1995) an extended form of resolution, called
Reduced SLD resolution (RSLD), is introduced. In essence, an RSLD derivation is
an SLD derivation such that redundancy elimination from resolvents is performed
after each rewriting step. It is intuitive that redundancy elimination may have
positive effects on derivation process. However, undesiderable effects are also
possible. In particular, as shown in this paper, program termination as well as
completeness of loop checking mechanisms via a given selection rule may be
lost. The study of such effects has led us to an analysis of selection rule
basic concepts, so that we have found convenient to move the attention from
rules of atom selection to rules of atom scheduling. A priority mechanism for
atom scheduling is built, where a priority is assigned to each atom in a
resolvent, and primary importance is given to the event of arrival of new atoms
from the body of the applied clause at rewriting time. This new computational
model proves able to address the study of redundancy elimination effects,
giving at the same time interesting insights into general properties of
selection rules. As a matter of fact, a class of scheduling rules, namely the
specialisation independent ones, is defined in the paper by using not trivial
semantic arguments. As a quite surprising result, specialisation independent
scheduling rules turn out to coincide with a class of rules which have an
immediate structural characterisation (named stack-queue rules). Then we prove
that such scheduling rules are tolerant to redundancy elimination, in the sense
that neither program termination nor completeness of equality loop check is
lost passing from SLD to RSLD.


title: Deciding first-order properties of locally tree-decomposable structures

abstract:
  We introduce the concept of a class of graphs, or more generally, relational
structures, being locally tree-decomposable. There are numerous examples of
locally tree-decomposable classes, among them the class of planar graphs and
all classes of bounded valence or of bounded tree-width. We also consider a
slightly more general concept of a class of structures having bounded local
tree-width.
  We show that for each property P of structures that is definable in
first-order logic and for each locally tree-decomposable class C of graphs,
there is a linear time algorithm deciding whether a given structure A in C has
property P. For classes C of bounded local tree-width, we show that for every
k\ge 1 there is an algorithm that solves the same problem in time
O(n^{1+(1/k)}) (where n is the cardinality of the input structure).


title:
How to Evaluate your Question Answering System Every Day and Still Get
  Real Work Done

abstract:
  In this paper, we report on Qaviar, an experimental automated evaluation
system for question answering applications. The goal of our research was to
find an automatically calculated measure that correlates well with human
judges' assessment of answer correctness in the context of question answering
tasks. Qaviar judges the response by computing recall against the stemmed
content words in the human-generated answer key. It counts the answer correct
if it exceeds agiven recall threshold. We determined that the answer
correctness predicted by Qaviar agreed with the human 93% to 95% of the time.
41 question-answering systems were ranked by both Qaviar and human assessors,
and these rankings correlated with a Kendall's Tau measure of 0.920, compared
to a correlation of 0.956 between human assessors on the same data.


title: Separating the complexity classes NL and NP

abstract:
  Withdrawn since -order- was overlooked. First order reductions without order
are much too weak to separate.


title: Design and Evaluation of Mechanisms for a Multicomputer Object Store

abstract:
  Multicomputers have traditionally been viewed as powerful compute engines. It
is from this perspective that they have been applied to various problems in
order to achieve significant performance gains. There are many applications for
which this compute intensive approach is only a partial solution. CAD, virtual
reality, simulation, document management and analysis all require timely access
to large amounts of data. This thesis investigates the use of the object store
paradigm to harness the large distributed memories found on multicomputers. The
design, implementation, and evaluation of a distributed object server on the
Fujitsu AP1000 is described. The performance of the distributed object server
under example applications, mainly physical simulation problems, is used to
evaluate solutions to the problems of client space recovery, object migration,
and coherence maintenance.
  The distributed object server follows the client-server model, allows object
replication, and uses binary semaphores as a concurrency control measure.
Instrumentation of the server under these applications supports several
conclusions: client space recovery should be dynamically controlled by the
application, predictively prefetching object replicas yields benefits in
restricted circumstances, object migration by storage unit (segment) is not
generally suitable where there are many objects per storage unit, and binary
semaphores are an expensive concurrency control measure in this environment.


title: Task Frames

abstract:
  Forty years ago Dijkstra introduced the current conventional execution of
routines. It places activation frames onto a stack. Each frame is the internal
state of an executing routine. The resulting application execution is not
easily helped by an external system. This presentation proposes an alternative
execution of routines. It places task frames onto the stack. A task frame is
the call of a routine to be executed. The feasibility of the alternative
execution is demonstrated by a crude implementation. As described elsewhere, an
application which executes in terms of tasks can be provided by an external
system with a transparent reliable, distributed, heterogeneous, adaptive,
dynamic, real-time, parallel, secure or other execution. By extending the crude
implementation, this presentation outlines a simple transparent parallel
execution.


title:
Assisted Video Sequences Indexing : Motion Analysis Based on Interest
  Points

abstract:
  This work deals with content-based video indexing. Our viewpoint is
semi-automatic analysis of compressed video. We consider the possible
applications of motion analysis and moving object detection : assisting moving
object indexing, summarising videos, and allowing image and motion queries. We
propose an approach based on interest points. As first results, we test and
compare the stability of different types of interest point detectors in
compressed sequences.


title: Sorting Integers on the AP1000

abstract:
  Sorting is one of the classic problems of computer science. Whilst well
understood on sequential machines, the diversity of architectures amongst
parallel systems means that algorithms do not perform uniformly on all
platforms. This document describes the implementation of a radix based
algorithm for sorting positive integers on a Fujitsu AP1000 Supercomputer,
which was constructed as an entry in the Joint Symposium on Parallel Processing
(JSPP) 1994 Parallel Software Contest (PSC94). Brief consideration is also
given to a full radix sort conducted in parallel across the machine.


title: Cluster Computing White Paper

abstract:
  Cluster computing is not a new area of computing. It is, however, evident
that there is a growing interest in its usage in all areas where applications
have traditionally used parallel or distributed computing platforms. The
growing interest has been fuelled in part by the availability of powerful
microprocessors and high-speed networks as off-the-shelf commodity components
as well as in part by the rapidly maturing software components available to
support high performance and high availability applications.
  This White Paper has been broken down into eleven sections, each of which has
been put together by academics and industrial researchers who are both experts
in their fields and where willing to volunteer their time and effort to put
together this White Paper. The status of this paper is draft and we are at the
stage of publicizing its presence and making a Request For Comments (RFC).


title:
Introduction to the GiNaC Framework for Symbolic Computation within the
  C++ Programming Language

abstract:
  The traditional split-up into a low level language and a high level language
in the design of computer algebra systems may become obsolete with the advent
of more versatile computer languages. We describe GiNaC, a special-purpose
system that deliberately denies the need for such a distinction. It is entirely
written in C++ and the user can interact with it directly in that language. It
was designed to provide efficient handling of multivariate polynomials,
algebras and special functions that are needed for loop calculations in
theoretical quantum field theory. It also bears some potential to become a more
general purpose symbolic package.


title: Looking at discourse in a corpus: The role of lexical cohesion

abstract:
  This paper is aimed at reporting on the development and application of a
computer model for discourse analysis through segmentation. Segmentation refers
to the principled division of texts into contiguous constituents. Other studies
have looked at the application of a number of models to the analysis of
discourse by computer. The segmentation procedure developed for the present
investigation is called LSM ('Link Set Median'). It was applied to three corpus
of 300 texts from three different genres. The results obtained by application
of the LSM procedure on the corpus were then compared to segmentation carried
out at random. Statistical analyses suggested that LSM significantly
outperformed random segmentation, thus indicating that the segmentation was
meaningful.


title: Robustness of Regional Matching Scheme over Global Matching Scheme

abstract:
  The paper has established and verified the theory prevailing widely among
image and pattern recognition specialists that the bottom-up indirect regional
matching process is the more stable and the more robust than the global
matching process against concentrated types of noise represented by clutter,
outlier or occlusion in the imagery. We have demonstrated this by analyzing the
effect of concentrated noise on a typical decision making process of a
simplified two candidate voting model where our theorem establishes the lower
bounds to a critical breakdown point of election (or decision) result by the
bottom-up matching process are greater than the exact bound of the global
matching process implying that the former regional process is capable of
accommodating a higher level of noise than the latter global process before the
result of decision overturns. We present a convincing experimental verification
supporting not only the theory by a white-black flag recognition problem in the
presence of localized noise but also the validity of the conjecture by a facial
recognition problem that the theorem remains valid for other decision making
processes involving an important dimension-reducing transform such as principal
component analysis or a Gabor transform.


title:
Application Software, Domain-Specific Languages, and Language Design
  Assistants

abstract:
  While application software does the real work, domain-specific languages
(DSLs) are tools to help produce it efficiently, and language design assistants
in turn are meta-tools to help produce DSLs quickly. DSLs are already in wide
use (HTML for web pages, Excel macros for spreadsheet applications, VHDL for
hardware design, ...), but many more will be needed for both new as well as
existing application domains. Language design assistants to help develop them
currently exist only in the basic form of language development systems. After a
quick look at domain-specific languages, and especially their relationship to
application libraries, we survey existing language development systems and give
an outline of future language design assistants.


title: CoRR: A Computing Research Repository

abstract:
  Discusses how CoRR was set up and some policy issues involved with setting up
such a repository.


title: A response to the commentaries on CoRR

abstract:
  This is a response to the commentaries on "CoRR: A Computing Research
Repository".


title: Connectivity Compression for Irregular Quadrilateral Meshes

abstract:
  Applications that require Internet access to remote 3D datasets are often
limited by the storage costs of 3D models. Several compression methods are
available to address these limits for objects represented by triangle meshes.
Many CAD and VRML models, however, are represented as quadrilateral meshes or
mixed triangle/quadrilateral meshes, and these models may also require
compression. We present an algorithm for encoding the connectivity of such
quadrilateral meshes, and we demonstrate that by preserving and exploiting the
original quad structure, our approach achieves encodings 30 - 80% smaller than
an approach based on randomly splitting quads into triangles. We present both a
code with a proven worst-case cost of 3 bits per vertex (or 2.75 bits per
vertex for meshes without valence-two vertices) and entropy-coding results for
typical meshes ranging from 0.3 to 0.9 bits per vertex, depending on the
regularity of the mesh. Our method may be implemented by a rule for a
particular splitting of quads into triangles and by using the compression and
decompression algorithms introduced in [Rossignac99] and
[Rossignac&Szymczak99]. We also present extensions to the algorithm to compress
meshes with holes and handles and meshes containing triangles and other
polygons as well as quads.


title:
A Simple Approach to Building Ensembles of Naive Bayesian Classifiers
  for Word Sense Disambiguation

abstract:
  This paper presents a corpus-based approach to word sense disambiguation that
builds an ensemble of Naive Bayesian classifiers, each of which is based on
lexical features that represent co--occurring words in varying sized windows of
context. Despite the simplicity of this approach, empirical results
disambiguating the widely studied nouns line and interest show that such an
ensemble achieves accuracy rivaling the best previously published results.


title:
Scientific Collaboratories as Socio-Technical Interaction Networks: A
  Theoretical Approach

abstract:
  Collaboratories refer to laboratories where scientists can work together
while they are in distant locations from each other and from key equipment.
They have captured the interest both of CSCW researchers and of science funders
who wish to optimize the use of rare scientific equipment and expertise. We
examine the kind of CSCW conceptions that help us best understand the character
of working relationships in these scientific collaboratories. Our model,
inspired by actor-network theory, considers technologies as Socio-technical
Interaction Networks (STINs). This model provides a rich understanding of the
scientific collaboratories, and also a more complete understanding of the
conditions and activities that support collaborative work in them. We
illustrate the significance of STIN models with several cases drawn from the
fields of high energy physics and materials science.


title: A Denotational Semantics for First-Order Logic

abstract:
  In Apt and Bezem [AB99] (see cs.LO/9811017) we provided a computational
interpretation of first-order formulas over arbitrary interpretations. Here we
complement this work by introducing a denotational semantics for first-order
logic. Additionally, by allowing an assignment of a non-ground term to a
variable we introduce in this framework logical variables.
  The semantics combines a number of well-known ideas from the areas of
semantics of imperative programming languages and logic programming. In the
resulting computational view conjunction corresponds to sequential composition,
disjunction to ``don't know'' nondeterminism, existential quantification to
declaration of a local variable, and negation to the ``negation as finite
failure'' rule. The soundness result shows correctness of the semantics with
respect to the notion of truth. The proof resembles in some aspects the proof
of the soundness of the SLDNF-resolution.


title: PSPACE Reasoning for Graded Modal Logics

abstract:
  We present a PSPACE algorithm that decides satisfiability of the graded modal
logic Gr(K_R)---a natural extension of propositional modal logic K_R by
counting expressions---which plays an important role in the area of knowledge
representation. The algorithm employs a tableaux approach and is the first
known algorithm which meets the lower bound for the complexity of the problem.
Thus, we exactly fix the complexity of the problem and refute an
ExpTime-hardness conjecture. We extend the results to the logic Gr(K_(R \cap
I)), which augments Gr(K_R) with inverse relations and intersection of
accessibility relations. This establishes a kind of ``theoretical benchmark''
that all algorithmic approaches can be measured against.


title: Extending and Implementing the Stable Model Semantics

abstract:
  An algorithm for computing the stable model semantics of logic programs is
developed. It is shown that one can extend the semantics and the algorithm to
handle new and more expressive types of rules. Emphasis is placed on the use of
efficient implementation techniques. In particular, an implementation of
lookahead that safely avoids testing every literal for failure and that makes
the use of lookahead feasible is presented. In addition, a good heuristic is
derived from the principle that the search space should be minimized.
  Due to the lack of competitive algorithms and implementations for the
computation of stable models, the system is compared with three satisfiability
solvers. This shows that the heuristic can be improved by breaking ties, but
leaves open the question of how to break them. It also demonstrates that the
more expressive rules of the stable model semantics make the semantics clearly
preferable over propositional logic when a problem has a more compact logic
program representation. Conjunctive normal form representations are never more
compact than logic program ones.


title:
An Average Analysis of Backtracking on Random Constraint Satisfaction
  Problems

abstract:
  In this paper we propose a random CSP model, called Model GB, which is a
natural generalization of standard Model B. It is proved that Model GB in which
each constraint is easy to satisfy exhibits non-trivial behaviour (not
trivially satisfiable or unsatisfiable) as the number of variables approaches
infinity. A detailed analysis to obtain an asymptotic estimate (good to 1+o(1))
of the average number of nodes in a search tree used by the backtracking
algorithm on Model GB is also presented. It is shown that the average number of
nodes required for finding all solutions or proving that no solution exists
grows exponentially with the number of variables. So this model might be an
interesting distribution for studying the nature of hard instances and
evaluating the performance of CSP algorithms. In addition, we further
investigate the behaviour of the average number of nodes as r (the ratio of
constraints to variables) varies. The results indicate that as r increases,
random CSP instances get easier and easier to solve, and the base for the
average number of nodes that is exponential in r tends to 1 as r approaches
infinity. Therefore, although the average number of nodes used by the
backtracking algorithm on random CSP is exponential, many CSP instances will be
very easy to solve when r is sufficiently large.


title: Reasoning with Axioms: Theory and Pratice

abstract:
  When reasoning in description, modal or temporal logics it is often useful to
consider axioms representing universal truths in the domain of discourse.
Reasoning with respect to an arbitrary set of axioms is hard, even for
relatively inexpressive logics, and it is essential to deal with such axioms in
an efficient manner if implemented systems are to be effective in real
applications. This is particularly relevant to Description Logics, where
subsumption reasoning with respect to a terminology is a fundamental problem.
Two optimisation techniques that have proved to be particularly effective in
dealing with terminologies are lazy unfolding and absorption. In this paper we
seek to improve our theoretical understanding of these important techniques. We
define a formal framework that allows the techniques to be precisely described,
establish conditions under which they can be safely applied, and prove that,
provided these conditions are respected, subsumption testing algorithms will
still function correctly. These results are used to show that the procedures
used in the FaCT system are correct and, moreover, to show how efficiency can
be significantly improved, while still retaining the guarantee of correctness,
by relaxing the safety conditions for absorption.


title: Practical Reasoning for Very Expressive Description Logics

abstract:
  Description Logics (DLs) are a family of knowledge representation formalisms
mainly characterised by constructors to build complex concepts and roles from
atomic ones. Expressive role constructors are important in many applications,
but can be computationally problematical. We present an algorithm that decides
satisfiability of the DL ALC extended with transitive and inverse roles and
functional restrictions with respect to general concept inclusion axioms and
role hierarchies; early experiments indicate that this algorithm is well-suited
for implementation. Additionally, we show that ALC extended with just
transitive and inverse roles is still in PSPACE. We investigate the limits of
decidability for this family of DLs, showing that relaxing the constraints
placed on the kinds of roles used in number restrictions leads to the
undecidability of all inference problems. Finally, we describe a number of
optimisation techniques that are crucial in obtaining implementations of the
decision procedures, which, despite the worst-case complexity of the problem,
exhibit good performance with real-life problems.


title: Practical Reasoning for Expressive Description Logics

abstract:
  Description Logics (DLs) are a family of knowledge representation formalisms
mainly characterised by constructors to build complex concepts and roles from
atomic ones. Expressive role constructors are important in many applications,
but can be computationally problematical. We present an algorithm that decides
satisfiability of the DL ALC extended with transitive and inverse roles, role
hierarchies, and qualifying number restrictions. Early experiments indicate
that this algorithm is well-suited for implementation. Additionally, we show
that ALC extended with just transitive and inverse roles is still in PSPACE.
Finally, we investigate the limits of decidability for this family of DLs.


title: Noun Phrase Recognition by System Combination

abstract:
  The performance of machine learning algorithms can be improved by combining
the output of different systems. In this paper we apply this idea to the
recognition of noun phrases.We generate different classifiers by using
different representations of the data. By combining the results with voting
techniques described in (Van Halteren et.al. 1998) we manage to improve the
best reported performances on standard data sets for base noun phrases and
arbitrary noun phrases.


title: Improving Testsuites via Instrumentation

abstract:
  This paper explores the usefulness of a technique from software engineering,
namely code instrumentation, for the development of large-scale natural
language grammars. Information about the usage of grammar rules in test
sentences is used to detect untested rules, redundant test sentences, and
likely causes of overgeneration. Results show that less than half of a
large-coverage grammar for German is actually tested by two large testsuites,
and that 10-30% of testing time is redundant. The methodology applied can be
seen as a re-use of grammar writing knowledge for testsuite compilation.


title: Reasoning with Individuals for the Description Logic SHIQ

abstract:
  While there has been a great deal of work on the development of reasoning
algorithms for expressive description logics, in most cases only Tbox reasoning
is considered. In this paper we present an algorithm for combined Tbox and Abox
reasoning in the SHIQ description logic. This algorithm is of particular
interest as it can be used to decide the problem of (database) conjunctive
query containment w.r.t. a schema. Moreover, the realisation of an efficient
implementation should be relatively straightforward as it can be based on an
existing highly optimised implementation of the Tbox algorithm in the FaCT
system.


title: On Modular Termination Proofs of General Logic Programs

abstract:
  We propose a modular method for proving termination of general logic programs
(i.e., logic programs with negation). It is based on the notion of acceptable
programs, but it allows us to prove termination in a truly modular way. We
consider programs consisting of a hierarchy of modules and supply a general
result for proving termination by dealing with each module separately. For
programs which are in a certain sense well-behaved, namely well-moded or
well-typed programs, we derive both a simple verification technique and an
iterative proof method. Some examples show how our system allows for greatly
simplified proofs.


title: On the Scalability of the Answer Extraction System "ExtrAns"

abstract:
  This paper reports on the scalability of the answer extraction system
ExtrAns. An answer extraction system locates the exact phrases in the documents
that contain the explicit answers to the user queries. Answer extraction
systems are therefore more convenient than document retrieval systems in
situations where the user wants to find specific information in limited time.
  ExtrAns performs answer extraction over UNIX manpages. It has been
constructed by combining available linguistic resources and implementing only a
few modules from scratch. A resolution procedure between the minimal logical
form of the user query and the minimal logical forms of the manpage sentences
finds the answers to the queries. These answers are displayed to the user,
together with pointers to the respective manpages, and the exact phrases that
contribute to the answer are highlighted.
  This paper shows that the increase in response times is not a big issue when
scaling the system up from 30 to 500 documents, and that the response times for
500 documents are still acceptable for a real-time answer extraction system.


title:
Centroid-based summarization of multiple documents: sentence extraction,
  utility-based evaluation, and user studies

abstract:
  We present a multi-document summarizer, called MEAD, which generates
summaries using cluster centroids produced by a topic detection and tracking
system. We also describe two new techniques, based on sentence utility and
subsumption, which we have applied to the evaluation of both single and
multiple document summaries. Finally, we describe two user studies that test
our models of multi-document summarization.


title: Modeling the Uncertainty in Complex Engineering Systems

abstract:
  Existing procedures for model validation have been deemed inadequate for many
engineering systems. The reason of this inadequacy is due to the high degree of
complexity of the mechanisms that govern these systems. It is proposed in this
paper to shift the attention from modeling the engineering system itself to
modeling the uncertainty that underlies its behavior. A mathematical framework
for modeling the uncertainty in complex engineering systems is developed. This
framework uses the results of computational learning theory. It is based on the
premise that a system model is a learning machine.


title: Fractionally-addressed delay lines

abstract:
  While traditional implementations of variable-length digital delay lines are
based on a circular buffer accessed by two pointers, we propose an
implementation where a single fractional pointer is used both for read and
write operations. On modern general-purpose architectures, the proposed method
is nearly as efficient as the popularinterpolated circular buffer, and it
behaves well for delay-length modulations commonly found in digital audio
effects. The physical interpretation of the new implementation shows that it is
suitable for simulating tension or density modulations in wave-propagating
media.


title:
C++ programming language for an abstract massively parallel SIMD
  architecture

abstract:
  The aim of this work is to define and implement an extended C++ language to
support the SIMD programming paradigm. The C++ programming language has been
extended to express all the potentiality of an abstract SIMD machine consisting
of a central Control Processor and a N-dimensional toroidal array of Numeric
Processors. Very few extensions have been added to the standard C++ with the
goal of minimising the effort for the programmer in learning a new language and
to keep very high the performance of the compiled code. The proposed language
has been implemented as a porting of the GNU C++ Compiler on a SIMD
supercomputer.


title: The SAT Phase Transition

abstract:
  Phase transition is an important feature of SAT problem. For random k-SAT
model, it is proved that as r (ratio of clauses to variables) increases, the
structure of solutions will undergo a sudden change like satisfiability phase
transition when r reaches a threshold point. This phenomenon shows that the
satisfying truth assignments suddenly shift from being relatively different
from each other to being very similar to each other.


title: Finite-State Reduplication in One-Level Prosodic Morphology

abstract:
  Reduplication, a central instance of prosodic morphology, is particularly
challenging for state-of-the-art computational morphology, since it involves
copying of some part of a phonological string. In this paper I advocate a
finite-state method that combines enriched lexical representations via
intersection to implement the copying. The proposal includes a
resource-conscious variant of automata and can benefit from the existence of
lazy algorithms. Finally, the implementation of a complex case from Koasati is
presented.


title:
A One-Time Pad based Cipher for Data Protection in Distributed
  Environments

abstract:
  A one-time pad (OTP) based cipher to insure both data protection and
integrity when mobile code arrives to a remote host is presented. Data
protection is required when a mobile agent could retrieve confidential
information that would be encrypted in untrusted nodes of the network; in this
case, information management could not rely on carrying an encryption key. Data
integrity is a prerequisite because mobile code must be protected against
malicious hosts that, by counterfeiting or removing collected data, could cover
information to the server that has sent the agent. The algorithm described in
this article seems to be simple enough, so as to be easily implemented. This
scheme is based on a non-interactive protocol and allows a remote host to
change its own data on-the-fly and, at the same time, protecting information
against handling by other hosts.


title: A Bayesian Reflection on Surfaces

abstract:
  The topic of this paper is a novel Bayesian continuous-basis field
representation and inference framework. Within this paper several problems are
solved: The maximally informative inference of continuous-basis fields, that is
where the basis for the field is itself a continuous object and not
representable in a finite manner; the tradeoff between accuracy of
representation in terms of information learned, and memory or storage capacity
in bits; the approximation of probability distributions so that a maximal
amount of information about the object being inferred is preserved; an
information theoretic justification for multigrid methodology. The maximally
informative field inference framework is described in full generality and
denoted the Generalized Kalman Filter. The Generalized Kalman Filter allows the
update of field knowledge from previous knowledge at any scale, and new data,
to new knowledge at any other scale. An application example instance, the
inference of continuous surfaces from measurements (for example, camera image
data), is presented.

categories: cs.CV cs.DS cs.LG math.PR nlin.AO physics.data-an


title:
A method for command identification, using modified collision free
  hashing with addition & rotation iterative hash functions (part 1)

abstract:
  This paper proposes a method for identification of a user`s fixed string set
(which can be a command/instruction set for a terminal or microprocessor). This
method is fast and has very small memory requirements, compared to a
traditional full string storage and compare method. The user feeds characters
into a microcontroller via a keyboard or another microprocessor sends commands
and the microcontroller hashes the input in order to identify valid commands,
ensuring no collisions between hashed valid strings, while applying further
criteria to narrow collision between random and valid strings. The method
proposed narrows the possibility of the latter kind of collision, achieving
small code and memory-size utilization and very fast execution. Hashing is
achieved using additive & rotating hash functions in an iterative form, which
can be very easily implemented in simple microcontrollers and microprocessors.
Such hash functions are presented and compared according to their efficiency
for a given string/command set, using the program found in the appendix.


title:
Ranking suspected answers to natural language questions using predictive
  annotation

abstract:
  In this paper, we describe a system to rank suspected answers to natural
language questions. We process both corpus and query using a new technique,
predictive annotation, which augments phrases in texts with labels anticipating
their being targets of certain kinds of questions. Given a natural language
question, an IR system returns a set of matching passages, which are then
analyzed and ranked according to various criteria described in this paper. We
provide an evaluation of the techniques based on results from the TREC Q&A
evaluation in which our system participated.


title: Axiomatizing Causal Reasoning

abstract:
  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.


title: Conditional Plausibility Measures and Bayesian Networks

abstract:
  A general notion of algebraic conditional plausibility measures is defined.
Probability measures, ranking functions, possibility measures, and (under the
appropriate definitions) sets of probability measures can all be viewed as
defining algebraic conditional plausibility measures. It is shown that
algebraic conditional plausibility measures can be represented using Bayesian
networks.


title: Computational Complexity and Phase Transitions

abstract:
  Phase transitions in combinatorial problems have recently been shown to be
useful in locating "hard" instances of combinatorial problems. The connection
between computational complexity and the existence of phase transitions has
been addressed in Statistical Mechanics and Artificial Intelligence, but not
studied rigorously.
  We take a step in this direction by investigating the existence of sharp
thresholds for the class of generalized satisfiability problems defined by
Schaefer. In the case when all constraints are clauses we give a complete
characterization of such problems that have a sharp threshold.
  While NP-completeness does not imply (even in this restricted case) the
existence of a sharp threshold, it "almost implies" this, since clausal
generalized satisfiability problems that lack a sharp threshold are either
  1. polynomial time solvable, or
  2. predicted, with success probability lower bounded by some positive
constant by across all the probability range, by a single, trivial procedure.


title:
Multimethods and separate static typechecking in a language with
  C++-like object model

abstract:
  The goal of this paper is the description and analysis of multimethod
implementation in a new object-oriented, class-based programming language
called OOLANG. The implementation of the multimethod typecheck and selection,
deeply analyzed in the paper, is performed in two phases in order to allow
static typechecking and separate compilation of modules. The first phase is
performed at compile time, while the second is executed at link time and does
not require the modules' source code. OOLANG has syntax similar to C++; the
main differences are the absence of pointers and the realization of
polymorphism through subsumption. It adopts the C++ object model and supports
multiple inheritance as well as virtual base classes. For this reason, it has
been necessary to define techniques for realigning argument and return value
addresses when performing multimethod invocations.


title: Boosting the Differences: A fast Bayesian classifier neural network

abstract:
  A Bayesian classifier that up-weights the differences in the attribute values
is discussed. Using four popular datasets from the UCI repository, some
interesting features of the network are illustrated. The network is suitable
for classification problems.


title:
Distorted English Alphabet Identification : An application of Difference
  Boosting Algorithm

abstract:
  The difference-boosting algorithm is used on letters dataset from the UCI
repository to classify distorted raster images of English alphabets. In
contrast to rather complex networks, the difference-boosting is found to
produce comparable or better classification efficiency on this complex problem.


title: Exploiting Diversity in Natural Language Processing: Combining Parsers

abstract:
  Three state-of-the-art statistical parsers are combined to produce more
accurate parses, as well as new bounds on achievable Treebank parsing accuracy.
Two general approaches are presented and two combination techniques are
described for each approach. Both parametric and non-parametric models are
explored. The resulting parsers surpass the best previously published
performance results for the Penn Treebank.


title:
A Note on "Optimal Static Load Balancing in Distributed Computer
  Systems"

abstract:
  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.


title: Novelty Detection for Robot Neotaxis

abstract:
  The ability of a robot to detect and respond to changes in its environment is
potentially very useful, as it draws attention to new and potentially important
features. We describe an algorithm for learning to filter out previously
experienced stimuli to allow further concentration on novel features. The
algorithm uses a model of habituation, a biological process which causes a
decrement in response with repeated presentation. Experiments with a mobile
robot are presented in which the robot detects the most novel stimulus and
turns towards it (`neotaxis').


title: A Real-Time Novelty Detector for a Mobile Robot

abstract:
  Recognising new or unusual features of an environment is an ability which is
potentially very useful to a robot. This paper demonstrates an algorithm which
achieves this task by learning an internal representation of `normality' from
sonar scans taken as a robot explores the environment. This model of the
environment is used to evaluate the novelty of each sonar scan presented to it
with relation to the model. Stimuli which have not been seen before, and
therefore have more novelty, are highlighted by the filter. The filter has the
ability to forget about features which have been learned, so that stimuli which
are seen only rarely recover their response over time. A number of robot
experiments are presented which demonstrate the operation of the filter.


title: Novelty Detection on a Mobile Robot Using Habituation

abstract:
  In this paper a novelty filter is introduced which allows a robot operating
in an un structured environment to produce a self-organised model of its
surroundings and to detect deviations from the learned model. The environment
is perceived using the rob ot's 16 sonar sensors. The algorithm produces a
novelty measure for each sensor scan relative to the model it has learned. This
means that it highlights stimuli which h ave not been previously experienced.
The novelty filter proposed uses a model of hab ituation. Habituation is a
decrement in behavioural response when a stimulus is pre sented repeatedly.
Robot experiments are presented which demonstrate the reliable o peration of
the filter in a number of environments.


title: Performing work efficiently in the presence of faults

abstract:
  We consider a system of t synchronous processes that communicate only by
sending messages to one another, and that together must perform $n$ independent
units of work. Processes may fail by crashing; we want to guarantee that in
every execution of the protocol in which at least one process survives, all n
units of work will be performed. We consider three parameters: the number of
messages sent, the total number of units of work performed (including
multiplicities), and time. We present three protocols for solving the problem.
All three are work-optimal, doing O(n+t) work. The first has moderate costs in
the remaining two parameters, sending O(t\sqrt{t}) messages, and taking O(n+t)
time. This protocol can be easily modified to run in any completely
asynchronous system equipped with a failure detection mechanism. The second
sends only O(t log{t}) messages, but its running time is large (exponential in
n and t). The third is essentially time-optimal in the (usual) case in which
there are no failures, and its time complexity degrades gracefully as the
number of failures increases.


title: Knowledge and common knowledge in a distributed environment

abstract:
  Reasoning about knowledge seems to play a fundamental role in distributed
systems. Indeed, such reasoning is a central part of the informal intuitive
arguments used in the design of distributed protocols. Communication in a
distributed system can be viewed as the act of transforming the system's state
of knowledge. This paper presents a general framework for formalizing and
reasoning about knowledge in distributed systems. We argue that states of
knowledge of groups of processors are useful concepts for the design and
analysis of distributed protocols. In particular, distributed knowledge
corresponds to knowledge that is ``distributed'' among the members of the
group, while common knowledge corresponds to a fact being ``publicly known''.
The relationship between common knowledge and a variety of desirable actions in
a distributed system is illustrated. Furthermore, it is shown that, formally
speaking, in practical systems common knowledge cannot be attained. A number of
weaker variants of common knowledge that are attainable in many cases of
interest are introduced and investigated.


title:
Light Affine Logic (Proof Nets, Programming Notation, P-Time Correctness
  and Completeness)

abstract:
  This paper is a structured introduction to Light Affine Logic, and to its
intuitionistic fragment. Light Affine Logic has a polynomially costing cut
elimination (P-Time correctness), and encodes all P-Time Turing machines
(P-Time completeness). P-Time correctness is proved by introducing the Proof
nets for Intuitionistic Light Affine Logic. P-Time completeness is demonstrated
in full details thanks to a very compact program notation. On one side, the
proof of P-Time correctness describes how the complexity of cut elimination is
controlled, thanks to a suitable cut elimination strategy that exploits
structural properties of the Proof nets. This allows to have a good catch on
the meaning of the ``paragraph'' modality, which is a peculiarity of light
logics. On the other side, the proof of P-Time completeness, together with a
lot of programming examples, gives a flavor of the non trivial task of
programming with resource limitations, using Intuitionistic Light Affine Logic
derivations as programs.


title: Bagging and Boosting a Treebank Parser

abstract:
  Bagging and boosting, two effective machine learning techniques, are applied
to natural language parsing. Experiments using these techniques with a
trainable statistical parser are described. The best resulting system provides
roughly as large of a gain in F-measure as doubling the corpus size. Error
analysis of the result of the boosting technique reveals some inconsistent
annotations in the Penn Treebank, suggesting a semi-automatic method for
finding inconsistent treebank annotations.


title: Exploiting Diversity for Natural Language Parsing

abstract:
  The popularity of applying machine learning methods to computational
linguistics problems has produced a large supply of trainable natural language
processing systems. Most problems of interest have an array of off-the-shelf
products or downloadable code implementing solutions using various techniques.
Where these solutions are developed independently, it is observed that their
errors tend to be independently distributed. This thesis is concerned with
approaches for capitalizing on this situation in a sample problem domain, Penn
Treebank-style parsing.
  The machine learning community provides techniques for combining outputs of
classifiers, but parser output is more structured and interdependent than
classifications. To address this discrepancy, two novel strategies for
combining parsers are used: learning to control a switch between parsers and
constructing a hybrid parse from multiple parsers' outputs.
  Off-the-shelf parsers are not developed with an intention to perform well in
a collaborative ensemble. Two techniques are presented for producing an
ensemble of parsers that collaborate. All of the ensemble members are created
using the same underlying parser induction algorithm, and the method for
producing complementary parsers is only loosely constrained by that chosen
algorithm.


title: An evaluation of Naive Bayesian anti-spam filtering

abstract:
  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.


title:
Solaris System Resource Manager: All I Ever Wanted Was My Unfair
  Advantage (And Why You Can't Have It!)

abstract:
  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.


title: UNIX Resource Managers: Capacity Planning and Resource Issues

abstract:
  The latest implementations of commercial UNIX to offer mainframe style
capacity management on enterprise servers include: AIX Workload Manager (WLM),
HP-UX Process Resource Manager (PRM), Solaris Resource Manager (SRM), as well
as SGI and Compaq. The ability to manage server capacity is achieved by making
significant modifications to the standard UNIX operating system so that
processes are inherently tied to specific users. Those users, in turn, are
granted only a certain fraction of system resources. Resource usage is
monitored and compared with each users grant to ensure that the assigned
entitlement constraints are met. In this paper, we begin by clearing up some of
the confusion that has surrounded the motivation and the terminology behind the
new technology. The common theme across each of the commercial implementations
is the introduction of the fair-share scheduler. After reviewing some potential
performance pitfalls, we present capacity planning guidelines for migrating to
automated UNIX resource management.


title: The X-Files: Investigating Alien Performance in a Thin-client World

abstract:
  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.


title: Turning Speech Into Scripts

abstract:
  We describe an architecture for implementing spoken natural language dialogue
interfaces to semi-autonomous systems, in which the central idea is to
transform the input speech signal through successive levels of representation
corresponding roughly to linguistic knowledge, dialogue knowledge, and domain
knowledge. The final representation is an executable program in a simple
scripting language equivalent to a subset of Cshell. At each stage of the
translation process, an input is transformed into an output, producing as a
byproduct a "meta-output" which describes the nature of the transformation
performed. We show how consistent use of the output/meta-output distinction
permits a simple and perspicuous treatment of apparently diverse topics
including resolution of pronouns, correction of user misconceptions, and
optimization of scripts. The methods described have been concretely realized in
a prototype speech interface to a simulation of the Personal Satellite
Assistant.


title: Accuracy, Coverage, and Speed: What Do They Mean to Users?

abstract:
  Speech is becoming increasingly popular as an interface modality, especially
in hands- and eyes-busy situations where the use of a keyboard or mouse is
difficult. However, despite the fact that many have hailed speech as being
inherently usable (since everyone already knows how to talk), most users of
speech input are left feeling disappointed by the quality of the interaction.
Clearly, there is much work to be done on the design of usable spoken
interfaces. We believe that there are two major problems in the design of
speech interfaces, namely, (a) the people who are currently working on the
design of speech interfaces are, for the most part, not interface designers and
therefore do not have as much experience with usability issues as we in the CHI
community do, and (b) speech, as an interface modality, has vastly different
properties than other modalities, and therefore requires different usability
measures.


title:
A Compact Architecture for Dialogue Management Based on Scripts and
  Meta-Outputs

abstract:
  We describe an architecture for spoken dialogue interfaces to semi-autonomous
systems that transforms speech signals through successive representations of
linguistic, dialogue, and domain knowledge. Each step produces an output, and a
meta-output describing the transformation, with an executable program in a
simple scripting language as the final result. The output/meta-output
distinction permits perspicuous treatment of diverse tasks such as resolving
pronouns, correcting user misconceptions, and optimizing scripts.


title: A Comparison of the XTAG and CLE Grammars for English

abstract:
  When people develop something intended as a large broad-coverage grammar,
they usually have a more specific goal in mind. Sometimes this goal is covering
a corpus; sometimes the developers have theoretical ideas they wish to
investigate; most often, work is driven by a combination of these two main
types of goal. What tends to happen after a while is that the community of
people working with the grammar starts thinking of some phenomena as
``central'', and makes serious efforts to deal with them; other phenomena are
labelled ``marginal'', and ignored. Before long, the distinction between
``central'' and ``marginal'' becomes so ingrained that it is automatic, and
people virtually stop thinking about the ``marginal'' phenomena. In practice,
the only way to bring the marginal things back into focus is to look at what
other people are doing and compare it with one's own work. In this paper, we
will take two large grammars, XTAG and the CLE, and examine each of them from
the other's point of view. We will find in both cases not only that important
things are missing, but that the perspective offered by the other grammar
suggests simple and practical ways of filling in the holes. It turns out that
there is a pleasing symmetry to the picture. XTAG has a very good treatment of
complement structure, which the CLE to some extent lacks; conversely, the CLE
offers a powerful and general account of adjuncts, which the XTAG grammar does
not fully duplicate. If we examine the way in which each grammar does the thing
it is good at, we find that the relevant methods are quite easy to port to the
other framework, and in fact only involve generalization and systematization of
existing mechanisms.


title:
Compiling Language Models from a Linguistically Motivated Unification
  Grammar

abstract:
  Systems now exist which are able to compile unification grammars into
language models that can be included in a speech recognizer, but it is so far
unclear whether non-trivial linguistically principled grammars can be used for
this purpose. We describe a series of experiments which investigate the
question empirically, by incrementally constructing a grammar and discovering
what problems emerge when successively larger versions are compiled into finite
state graph representations and used as language models for a medium-vocabulary
recognition task.


title:
Multicast-based Architecture for IP Mobility: Simulation Analysis and
  Comparison with Basic Mobile IP

abstract:
  With the introduction of a newer generation of wireless devices and
technologies, the need for an efficient architecture for IP mobility is
becoming more apparent. Several architectures have been proposed to support IP
mobility. Most studies, however, show that current architectures, in general,
fall short from satisfying the performance requirements for wireless
applications, mainly audio. Other studies have shown performance improvement by
using multicast to reduce latency and packet loss during handoff. In this
study, we propose a multicast-based architecture to support IP mobility. We
evaluate our approach through simulation, and we compare it to mainstream
approaches for IP mobility, mainly, the Mobile IP protocol. Comparison is
performed according to the required performance criteria, such as smooth
handoff and efficient routing.
  Our simulation results show significant improvement for the proposed
architecture. On average, basic Mobile IP consumes almost twice as much network
bandwidth, and experiences more than twice as much end-to-end and handoff
delays, as does our proposed architecture. Furthermore, we propose an extension
to Mobile IP to support our architecture with minimal modification.


title:
Dialogue Act Modeling for Automatic Tagging and Recognition of
  Conversational Speech

abstract:
  We describe a statistical approach for modeling dialogue acts in
conversational speech, i.e., speech-act-like units such as Statement, Question,
Backchannel, Agreement, Disagreement, and Apology. Our model detects and
predicts dialogue acts based on lexical, collocational, and prosodic cues, as
well as on the discourse coherence of the dialogue act sequence. The dialogue
model is based on treating the discourse structure of a conversation as a
hidden Markov model and the individual dialogue acts as observations emanating
from the model states. Constraints on the likely sequence of dialogue acts are
modeled via a dialogue act n-gram. The statistical dialogue grammar is combined
with word n-grams, decision trees, and neural networks modeling the
idiosyncratic lexical and prosodic manifestations of each dialogue act. We
develop a probabilistic integration of speech recognition with dialogue
modeling, to improve both speech recognition and dialogue act classification
accuracy. Models are trained and evaluated using a large hand-labeled database
of 1,155 conversations from the Switchboard corpus of spontaneous
human-to-human telephone speech. We achieved good dialogue act labeling
accuracy (65% based on errorful, automatically recognized words and prosody,
and 71% based on word transcripts, compared to a chance baseline accuracy of
35% and human accuracy of 84%) and a small reduction in word recognition error.


title:
Can Prosody Aid the Automatic Classification of Dialog Acts in
  Conversational Speech?

abstract:
  Identifying whether an utterance is a statement, question, greeting, and so
forth is integral to effective automatic understanding of natural dialog.
Little is known, however, about how such dialog acts (DAs) can be automatically
classified in truly natural conversation. This study asks whether current
approaches, which use mainly word information, could be improved by adding
prosodic information. The study is based on more than 1000 conversations from
the Switchboard corpus. DAs were hand-annotated, and prosodic features
(duration, pause, F0, energy, and speaking rate) were automatically extracted
for each DA. In training, decision trees based on these features were inferred;
trees were then applied to unseen test data to evaluate performance.
Performance was evaluated for prosody models alone, and after combining the
prosody models with word information -- either from true words or from the
output of an automatic speech recognizer. For an overall classification task,
as well as three subtasks, prosody made significant contributions to
classification. Feature-specific analyses further revealed that although
canonical features (such as F0 for questions) were important, less obvious
features could compensate if canonical features were removed. Finally, in each
task, integrating the prosodic model with a DA-specific statistical language
model improved performance over that of the language model alone, especially
for the case of recognized words. Results suggest that DAs are redundantly
marked in natural conversation, and that a variety of automatically extractable
prosodic features could aid dialog processing in speech applications.


title: Entropy-based Pruning of Backoff Language Models

abstract:
  A criterion for pruning parameters from N-gram backoff language models is
developed, based on the relative entropy between the original and the pruned
model. It is shown that the relative entropy resulting from pruning a single
N-gram can be computed exactly and efficiently for backoff models. The relative
entropy measure can be expressed as a relative change in training set
perplexity. This leads to a simple pruning criterion whereby all N-grams that
change perplexity by less than a threshold are removed from the model.
Experiments show that a production-quality Hub4 LM can be reduced to 26% its
original size without increasing recognition error. We also compare the
approach to a heuristic pruning criterion by Seymore and Rosenfeld (1996), and
show that their approach can be interpreted as an approximation to the relative
entropy criterion. Experimentally, both approaches select similar sets of
N-grams (about 85% overlap), with the exact relative entropy criterion giving
marginally better performance.


title: Online Correction of Dispersion Error in 2D Waveguide Meshes

abstract:
  An elastic ideal 2D propagation medium, i.e., a membrane, can be simulated by
models discretizing the wave equation on the time-space grid (finite difference
methods), or locally discretizing the solution of the wave equation (waveguide
meshes). The two approaches provide equivalent computational structures, and
introduce numerical dispersion that induces a misalignment of the modes from
their theoretical positions. Prior literature shows that dispersion can be
arbitrarily reduced by oversizing and oversampling the mesh, or by adpting
offline warping techniques. In this paper we propose to reduce numerical
dispersion by embedding warping elements, i.e., properly tuned allpass filters,
in the structure. The resulting model exhibits a significant reduction in
dispersion, and requires less computational resources than a regular mesh
structure having comparable accuracy.


title: Verbal Interactions in Virtual Worlds

abstract:
  We first discuss respective advantages of language interaction in virtual
worlds and of using 3D images in dialogue systems. Then, we describe an example
of a verbal interaction system in virtual reality: Ulysse. Ulysse is a
conversational agent that helps a user navigate in virtual worlds. It has been
designed to be embedded in the representation of a participant of a virtual
conference and it responds positively to motion orders. Ulysse navigates the
user's viewpoint on his/her behalf in the virtual world. On tests we carried
out, we discovered that users, novices as well as experienced ones have
difficulties moving in a 3D environment. Agents such as Ulysse enable a user to
carry out navigation motions that would have been impossible with classical
interaction devices. From the whole Ulysse system, we have stripped off a
skeleton architecture that we have ported to VRML, Java, and Prolog. We hope
this skeleton helps the design of language applications in virtual worlds.


title: Trainable Methods for Surface Natural Language Generation

abstract:
  We present three systems for surface natural language generation that are
trainable from annotated corpora. The first two systems, called NLG1 and NLG2,
require a corpus marked only with domain-specific semantic attributes, while
the last system, called NLG3, requires a corpus marked with both semantic
attributes and syntactic dependency information. All systems attempt to produce
a grammatical natural language phrase from a domain-specific semantic
representation. NLG1 serves a baseline system and uses phrase frequencies to
generate a whole phrase in one step, while NLG2 and NLG3 use maximum entropy
probability models to individually generate each word in the phrase. The
systems NLG2 and NLG3 learn to determine both the word choice and the word
order of the phrase. We present experiments in which we generate phrases to
describe flights in the air travel domain.


title: Systematic Performance Evaluation of Multipoint Protocols

abstract:
  The advent of multipoint (multicast-based) applications and the growth and
complexity of the Internet has complicated network protocol design and
evaluation.
  In this paper, we present a method for automatic synthesis of worst and best
case scenarios for multipoint protocol performance evaluation.
  Our method uses a fault-oriented test generation (FOTG) algorithm for
searching the protocol and system state space to synthesize these scenarios.
The algorithm is based on a global finite state machine (FSM) model. We extend
the algorithm with timing semantics to handle end-to-end delays and address
performance criteria. We introduce the notion of a virtual LAN to represent
delays of the underlying multicast distribution tree.
  As a case study, we use our method to evaluate variants of the timer
suppression mechanism, used in various multipoint protocols, with respect to
two performance criteria: overhead of response messages and response time.
Simulation results for reliable multicast protocols show that our method
provides a scalable way for synthesizing worst-case scenarios automatically. We
expect our method to serve as a model for applying systematic scenario
generation to other multipoint protocols.


title: Multiagent Control of Self-reconfigurable Robots

abstract:
  We demonstrate how multiagent systems provide useful control techniques for
modular self-reconfigurable (metamorphic) robots. Such robots consist of many
modules that can move relative to each other, thereby changing the overall
shape of the robot to suit different tasks. Multiagent control is particularly
well-suited for tasks involving uncertain and changing environments. We
illustrate this approach through simulation experiments of Proteo, a
metamorphic robot system currently under development.


title: Verifying Termination of General Logic Programs with Concrete Queries

abstract:
  We introduce a method of verifying termination of logic programs with respect
to concrete queries (instead of abstract query patterns). A necessary and
sufficient condition is established and an algorithm for automatic verification
is developed. In contrast to existing query pattern-based approaches, our
method has the following features: (1) It applies to all general logic programs
with non-floundering queries. (2) It is very easy to automate because it does
not need to search for a level mapping or a model, nor does it need to compute
an interargument relation based on additional mode or type information. (3) It
bridges termination analysis with loop checking, the two problems that have
been studied separately in the past despite their close technical relation with
each other.


title: Estimation of English and non-English Language Use on the WWW

abstract:
  The World Wide Web has grown so big, in such an anarchic fashion, that it is
difficult to describe. One of the evident intrinsic characteristics of the
World Wide Web is its multilinguality. Here, we present a technique for
estimating the size of a language-specific corpus given the frequency of
commonly occurring words in the corpus. We apply this technique to estimating
the number of words available through Web browsers for given languages.
Comparing data from 1996 to data from 1999 and 2000, we calculate the growth of
a number of European languages on the Web. As expected, non-English languages
are growing at a faster pace than English, though the position of English is
still dominant.


title:
Verifying Termination and Error-Freedom of Logic Programs with block
  Declarations

abstract:
  We present verification methods for logic programs with delay declarations.
The verified properties are termination and freedom from errors related to
built-ins. Concerning termination, we present two approaches. The first
approach tries to eliminate the well-known problem of speculative output
bindings. The second approach is based on identifying the predicates for which
the textual position of an atom using this predicate is irrelevant with respect
to termination. Three features are distinctive of this work: it allows for
predicates to be used in several modes; it shows that block declarations, which
are a very simple delay construct, are sufficient to ensure the desired
properties; it takes the selection rule into account, assuming it to be as in
most Prolog implementations. The methods can be used to verify existing
programs and assist in writing new programs.


title: Type Classes and Constraint Handling Rules

abstract:
  Type classes are an elegant extension to traditional, Hindley-Milner based
typing systems. They are used in modern, typed languages such as Haskell to
support controlled overloading of symbols. Haskell 98 supports only
single-parameter and constructor type classes. Other extensions such as
multi-parameter type classes are highly desired but are still not officially
supported by Haskell. Subtle issues arise with extensions, which may lead to a
loss of feasible type inference or ambiguous programs. A proper logical basis
for type class systems seems to be missing. Such a basis would allow extensions
to be characterised and studied rigorously. We propose to employ Constraint
Handling Rules as a tool to study and develop type class systems in a uniform
way.


title: On the Development of the Intersection of a Plane with a Polytope

abstract:
  Define a ``slice'' curve as the intersection of a plane with the surface of a
polytope, i.e., a convex polyhedron in three dimensions. We prove that a slice
curve develops on a plane without self-intersection. The key tool used is a
generalization of Cauchy's arm lemma to permit nonconvex ``openings'' of a
planar convex chain.


title: Prosody-Based Automatic Segmentation of Speech into Sentences and Topics

abstract:
  A crucial step in processing speech audio data for information extraction,
topic detection, or browsing/playback is to segment the input into sentence and
topic units. Speech segmentation is challenging, since the cues typically
present for segmenting text (headers, paragraphs, punctuation) are absent in
spoken language. We investigate the use of prosody (information gleaned from
the timing and melody of speech) for these tasks. Using decision tree and
hidden Markov modeling techniques, we combine prosodic cues with word-based
approaches, and evaluate performance on two speech corpora, Broadcast News and
Switchboard. Results show that the prosodic model alone performs on par with,
or better than, word-based statistical language models -- for both true and
automatically recognized words in news speech. The prosodic model achieves
comparable performance with significantly less training data, and requires no
hand-labeling of prosodic events. Across tasks and corpora, we obtain a
significant improvement over word-only models using a probabilistic combination
of prosodic and lexical information. Inspection reveals that the prosodic
models capture language-independent boundary indicators described in the
literature. Finally, cue usage is task and corpus dependent. For example, pause
and pitch features are highly informative for segmenting news speech, whereas
pause, duration and word-based cues dominate for natural conversation.


title:
A Decision-Theoretic Approach to Resource Allocation in Wireless
  Multimedia Networks

abstract:
  The allocation of scarce spectral resources to support as many user
applications as possible while maintaining reasonable quality of service is a
fundamental problem in wireless communication. We argue that the problem is
best formulated in terms of decision theory. We propose a scheme that takes
decision-theoretic concerns (like preferences) into account and discuss the
difficulties and subtleties involved in applying standard techniques from the
theory of Markov Decision Processes (MDPs) in constructing an algorithm that is
decision-theoretically optimal. As an example of the proposed framework, we
construct such an algorithm under some simplifying assumptions. Additionally,
we present analysis and simulation results that show that our algorithm meets
its design goals. Finally, we investigate how far from optimal one well-known
heuristic is. The main contribution of our results is in providing insight and
guidance for the design of near-optimal admission-control policies.


title: Approximation and Exactness in Finite State Optimality Theory

abstract:
  Previous work (Frank and Satta 1998; Karttunen, 1998) has shown that
Optimality Theory with gradient constraints generally is not finite state. A
new finite-state treatment of gradient constraints is presented which improves
upon the approximation of Karttunen (1998). The method turns out to be exact,
and very compact, for the syllabification analysis of Prince and Smolensky
(1993).


title:
Orthogonal Least Squares Algorithm for the Approximation of a Map and
  its Derivatives with a RBF Network

abstract:
  Radial Basis Function Networks (RBFNs) are used primarily to solve
curve-fitting problems and for non-linear system modeling. Several algorithms
are known for the approximation of a non-linear curve from a sparse data set by
means of RBFNs. However, there are no procedures that permit to define
constrains on the derivatives of the curve. In this paper, the Orthogonal Least
Squares algorithm for the identification of RBFNs is modified to provide the
approximation of a non-linear 1-in 1-out map along with its derivatives, given
a set of training data. The interest on the derivatives of non-linear functions
concerns many identification and control tasks where the study of system
stability and robustness is addressed. The effectiveness of the proposed
algorithm is demonstrated by a study on the stability of a single loop feedback
system.


title:
Correlation over Decomposed Signals: A Non-Linear Approach to Fast and
  Effective Sequences Comparison

abstract:
  A novel non-linear approach to fast and effective comparison of sequences is
presented, compared to the traditional cross-correlation operator, and
illustrated with respect to DNA sequences.


title: Using a Diathesis Model for Semantic Parsing

abstract:
  This paper presents a semantic parsing approach for unrestricted texts.
Semantic parsing is one of the major bottlenecks of Natural Language
Understanding (NLU) systems and usually requires building expensive resources
not easily portable to other domains. Our approach obtains a case-role
analysis, in which the semantic roles of the verb are identified. In order to
cover all the possible syntactic realisations of a verb, our system combines
their argument structure with a set of general semantic labelled diatheses
models. Combining them, the system builds a set of syntactic-semantic patterns
with their own role-case representation. Once the patterns are build, we use an
approximate tree pattern-matching algorithm to identify the most reliable
pattern for a sentence. The pattern matching is performed between the
syntactic-semantic patterns and the feature-structure tree representing the
morphological, syntactical and semantic information of the analysed sentence.
For sentences assigned to the correct model, the semantic parsing system we are
presenting identifies correctly more than 73% of possible semantic case-roles.


title: Semantic Parsing based on Verbal Subcategorization

abstract:
  The aim of this work is to explore new methodologies on Semantic Parsing for
unrestricted texts. Our approach follows the current trends in Information
Extraction (IE) and is based on the application of a verbal subcategorization
lexicon (LEXPIR) by means of complex pattern recognition techniques. LEXPIR is
framed on the theoretical model of the verbal subcategorization developed in
the Pirapides project.


title:
Constraint compiling into rules formalism constraint compiling into
  rules formalism for dynamic CSPs computing

abstract:
  In this paper we present a rule based formalism for filtering variables
domains of constraints. This formalism is well adapted for solving dynamic CSP.
We take diagnosis as an instance problem to illustrate the use of these rules.
A diagnosis problem is seen like finding all the minimal sets of constraints to
be relaxed in the constraint network that models the device to be diagnosed


title: Finite-State Non-Concatenative Morphotactics

abstract:
  Finite-state morphology in the general tradition of the Two-Level and Xerox
implementations has proved very successful in the production of robust
morphological analyzer-generators, including many large-scale commercial
systems. However, it has long been recognized that these implementations have
serious limitations in handling non-concatenative phenomena. We describe a new
technique for constructing finite-state transducers that involves reapplying
the regular-expression compiler to its own output. Implemented in an algorithm
called compile-replace, this technique has proved useful for handling
non-concatenative phenomena; and we demonstrate it on Malay full-stem
reduplication and Arabic stem interdigitation.


title: Security Policy Consistency

abstract:
  With the advent of wide security platforms able to express simultaneously all
the policies comprising an organization's global security policy, the problem
of inconsistencies within security policies become harder and more relevant.
  We have defined a tool based on the CHR language which is able to detect
several types of inconsistencies within and between security policies and other
specifications, namely workflow specifications.
  Although the problem of security conflicts has been addressed by several
authors, to our knowledge none has addressed the general problem of security
inconsistencies, on its several definitions and target specifications.


title: 3-Coloring in Time O(1.3289^n)

abstract:
  We consider worst case time bounds for NP-complete problems including 3-SAT,
3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a
constraint satisfaction (CSP) formulation of these problems. 3-SAT is
equivalent to (2,3)-CSP while the other problems above are special cases of
(3,2)-CSP; there is also a natural duality transformation from (a,b)-CSP to
(b,a)-CSP. We give a fast algorithm for (3,2)-CSP and use it to improve the
time bounds for solving the other problems listed above. Our techniques involve
a mixture of Davis-Putnam-style backtracking with more sophisticated matching
and network flow based ideas.


title: Geometric Morphology of Granular Materials

abstract:
  We present a new method to transform the spectral pixel information of a
micrograph into an affine geometric description, which allows us to analyze the
morphology of granular materials. We use spectral and pulse-coupled neural
network based segmentation techniques to generate blobs, and a newly developed
algorithm to extract dilated contours. A constrained Delaunay tesselation of
the contour points results in a triangular mesh. This mesh is the basic
ingredient of the Chodal Axis Transform, which provides a morphological
decomposition of shapes. Such decomposition allows for grain separation and the
efficient computation of the statistical features of granular materials.


title: Constraint Exploration and Envelope of Simulation Trajectories

abstract:
  The implicit theory that a simulation represents is precisely not in the
individual choices but rather in the 'envelope' of possible trajectories - what
is important is the shape of the whole envelope. Typically a huge amount of
computation is required when experimenting with factors bearing on the dynamics
of a simulation to tease out what affects the shape of this envelope. In this
paper we present a methodology aimed at systematically exploring this envelope.
We propose a method for searching for tendencies and proving their necessity
relative to a range of parameterisations of the model and agents' choices, and
to the logic of the simulation language. The exploration consists of a forward
chaining generation of the trajectories associated to and constrained by such a
range of parameterisations and choices. Additionally, we propose a
computational procedure that helps implement this exploration by translating a
Multi Agent System simulation into a constraint-based search over possible
trajectories by 'compiling' the simulation rules into a more specific form,
namely by partitioning the simulation rules using appropriate modularity in the
simulation. An example of this procedure is exhibited.
  Keywords: Constraint Search, Constraint Logic Programming, Proof, Emergence,
Tendencies


title: Interval Constraint Solving for Camera Control and Motion Planning

abstract:
  Many problems in robust control and motion planning can be reduced to either
find a sound approximation of the solution space determined by a set of
nonlinear inequalities, or to the ``guaranteed tuning problem'' as defined by
Jaulin and Walter, which amounts to finding a value for some tuning parameter
such that a set of inequalities be verified for all the possible values of some
perturbation vector. A classical approach to solve these problems, which
satisfies the strong soundness requirement, involves some quantifier
elimination procedure such as Collins' Cylindrical Algebraic Decomposition
symbolic method. Sound numerical methods using interval arithmetic and local
consistency enforcement to prune the search space are presented in this paper
as much faster alternatives for both soundly solving systems of nonlinear
inequalities, and addressing the guaranteed tuning problem whenever the
perturbation vector has dimension one. The use of these methods in camera
control is investigated, and experiments with the prototype of a declarative
modeller to express camera motion using a cinematic language are reported and
commented.


title: Using compression to identify acronyms in text

abstract:
  Text mining is about looking for patterns in natural language text, and may
be defined as the process of analyzing text to extract information from it for
particular purposes. In previous work, we claimed that compression is a key
technology for text mining, and backed this up with a study that showed how
particular kinds of lexical tokens---names, dates, locations, etc.---can be
identified and located in running text, using compression models to provide the
leverage necessary to distinguish different token types (Witten et al., 1999)


title: Brainstorm/J: a Java Framework for Intelligent Agents

abstract:
  Despite the effort of many researchers in the area of multi-agent systems
(MAS) for designing and programming agents, a few years ago the research
community began to take into account that common features among different MAS
exists. Based on these common features, several tools have tackled the problem
of agent development on specific application domains or specific types of
agents. As a consequence, their scope is restricted to a subset of the huge
application domain of MAS. In this paper we propose a generic infrastructure
for programming agents whose name is Brainstorm/J. The infrastructure has been
implemented as an object oriented framework. As a consequence, our approach
supports a broader scope of MAS applications than previous efforts, being
flexible and reusable.


title:
Systematic Testing of Multicast Routing Protocols: Analysis of Forward
  and Backward Search Techniques

abstract:
  In this paper, we present a new methodology for developing systematic and
automatic test generation algorithms for multipoint protocols. These algorithms
attempt to synthesize network topologies and sequences of events that stress
the protocol's correctness or performance. This problem can be viewed as a
domain-specific search problem that suffers from the state space explosion
problem. One goal of this work is to circumvent the state space explosion
problem utilizing knowledge of network and fault modeling, and multipoint
protocols. The two approaches investigated in this study are based on forward
and backward search techniques. We use an extended finite state machine (FSM)
model of the protocol. The first algorithm uses forward search to perform
reduced reachability analysis. Using domain-specific information for multicast
routing over LANs, the algorithm complexity is reduced from exponential to
polynomial in the number of routers. This approach, however, does not fully
automate topology synthesis. The second algorithm, the fault-oriented test
generation, uses backward search for topology synthesis and uses backtracking
to generate event sequences instead of searching forward from initial states.
Using these algorithms, we have conducted studies for correctness of the
multicast routing protocol PIM. We propose to extend these algorithms to study
end-to-end multipoint protocols using a virtual LAN that represents delays of
the underlying multicast distribution tree.


title: DISCO: An object-oriented system for music composition and sound design

abstract:
  This paper describes an object-oriented approach to music composition and
sound design. The approach unifies the processes of music making and instrument
building by using similar logic, objects, and procedures. The composition
modules use an abstract representation of musical data, which can be easily
mapped onto different synthesis languages or a traditionally notated score. An
abstract base class is used to derive classes on different time scales. Objects
can be related to act across time scales, as well as across an entire piece,
and relationships between similar objects can replicate traditional music
operations or introduce new ones. The DISCO (Digital Instrument for
Sonification and Composition) system is an open-ended work in progress.


title: Data sonification and sound visualization

abstract:
  This article describes a collaborative project between researchers in the
Mathematics and Computer Science Division at Argonne National Laboratory and
the Computer Music Project of the University of Illinois at Urbana-Champaign.
The project focuses on the use of sound for the exploration and analysis of
complex data sets in scientific computing. The article addresses digital sound
synthesis in the context of DIASS (Digital Instrument for Additive Sound
Synthesis) and sound visualization in a virtual-reality environment by means of
M4CAVE. It describes the procedures and preliminary results of some experiments
in scientific sonification and sound visualization.


title: Compiling Language Definitions: The ASF+SDF Compiler

abstract:
  The ASF+SDF Meta-Environment is an interactive language development
environment whose main application areas are definition of domain-specific
languages, generation of program analysis and transformation tools, production
of software renovation tools, and general specification and prototyping. It
uses conditional rewrite rules to define the dynamic semantics and other
tool-oriented aspects of languages, so the effectiveness of the generated tools
is critically dependent on the quality of the rewrite rule implementation.
  The ASF+SDF rewrite rule compiler generates C code, thus taking advantage of
C's portability and the sophisticated optimization capabilities of current C
compilers as well as avoiding potential abstract machine interface bottlenecks.
It can handle large (10 000+ rule) language definitions and uses an efficient
run-time storage scheme capable of handling large (1 000 000+ node) terms. Term
storage uses maximal subterm sharing (hash-consing), which turns out to be more
effective in the case of ASF+SDF than in Lisp or SML. Extensive benchmarking
has shown the time and space performance of the generated code to be as good as
or better than that of the best current rewrite rule and functional language
compilers.


title: Incremental construction of minimal acyclic finite-state automata

abstract:
  In this paper, we describe a new method for constructing minimal,
deterministic, acyclic finite-state automata from a set of strings. Traditional
methods consist of two phases: the first to construct a trie, the second one to
minimize it. Our approach is to construct a minimal automaton in a single phase
by adding new strings one by one and minimizing the resulting automaton
on-the-fly. We present a general algorithm as well as a specialization that
relies upon the lexicographical ordering of the input strings.


title: Boosting Applied to Word Sense Disambiguation

abstract:
  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.


title:
Naive Bayes and Exemplar-Based approaches to Word Sense Disambiguation
  Revisited

abstract:
  This paper describes an experimental comparison between two standard
supervised learning methods, namely Naive Bayes and Exemplar-based
classification, on the Word Sense Disambiguation (WSD) problem. The aim of the
work is twofold. Firstly, it attempts to contribute to clarify some confusing
information about the comparison between both methods appearing in the related
literature. In doing so, several directions have been explored, including:
testing several modifications of the basic learning algorithms and varying the
feature space. Secondly, an improvement of both algorithms is proposed, in
order to deal with large attribute sets. This modification, which basically
consists in using only the positive information appearing in the examples,
allows to improve greatly the efficiency of the methods, with no loss in
accuracy. The experiments have been performed on the largest sense-tagged
corpus available containing the most frequent and ambiguous English words.
Results show that the Exemplar-based approach to WSD is generally superior to
the Bayesian approach, especially when a specific metric for dealing with
symbolic attributes is used.


title: Using Learning-based Filters to Detect Rule-based Filtering Obsolescence

abstract:
  For years, Caisse des Depots et Consignations has produced information
filtering applications. To be operational, these applications require high
filtering performances which are achieved by using rule-based filters. With
this technique, an administrator has to tune a set of rules for each topic.
However, filters become obsolescent over time. The decrease of their
performances is due to diachronic polysemy of terms that involves a loss of
precision and to diachronic polymorphism of concepts that involves a loss of
recall.
  To help the administrator to maintain his filters, we have developed a method
which automatically detects filtering obsolescence. It consists in making a
learning-based control filter using a set of documents which have already been
categorised as relevant or not relevant by the rule-based filter. The idea is
to supervise this filter by processing a differential comparison of its
outcomes with those of the control one.
  This method has many advantages. It is simple to implement since the training
set used by the learning is supplied by the rule-based filter. Thus, both the
making and the use of the control filter are fully automatic. With automatic
detection of obsolescence, learning-based filtering finds a rich application
which offers interesting prospects.