OpenRaiser/Intern-Atlas huggingface dataset:
An ascription-based approach to speech acts
Venue: arXiv cs.CL 1999
Year: 1999

The two principal areas of natural language processing research in pragmatics are belief modelling and speech act processing. Belief modelling is the development of techniques to represent the mental attitudes of a dialogue participant. The latter approach, speech act processing, based on speech act theory, involves viewing dialogue in planning terms. Utterances in a dialogue are modelled as steps in a plan where understanding an utterance involves deriving the complete plan a speaker is attempting to achieve. However, previous speech act based approaches have been limited by a reliance upon relatively simplistic belief modelling techniques and their relationship to planning and plan recognition. In particular, such techniques assume precomputed nested belief structures. In this paper, we will present an approach to speech act processing based on novel belief modelling techniques where nested beliefs are propagated on demand.
A Control and Management Network for Wireless ATM Systems
Venue: arXiv cs.NI 1999
Year: 1999

This paper describes the design of a control and management network (orderwire) for a mobile wireless Asynchronous Transfer Mode (ATM) network. This mobile wireless ATM network is part of the Rapidly Deployable Radio Network (RDRN). The orderwire system consists of a packet radio network which overlays the mobile wireless ATM network, each network element in this network uses Global Positioning System (GPS) information to control a beamforming antenna subsystem which provides for spatial reuse. This paper also proposes a novel Virtual Network Configuration (VNC) algorithm for predictive network configuration. A mobile ATM Private Network-Network Interface (PNNI) based on VNC is also discussed. Finally, as a prelude to the system implementation, results of a Maisie simulation of the orderwire system are discussed.
Ensembles of Radial Basis Function Networks for Spectroscopic Detection of Cervical Pre-Cancer
Venue: arXiv cs.NE 1999
Year: 1999

The mortality related to cervical cancer can be substantially reduced through early detection and treatment. However, current detection techniques, such as Pap smear and colposcopy, fail to achieve a concurrently high sensitivity and specificity. In vivo fluorescence spectroscopy is a technique which quickly, non-invasively and quantitatively probes the biochemical and morphological changes that occur in pre-cancerous tissue. A multivariate statistical algorithm was used to extract clinically useful information from tissue spectra acquired from 361 cervical sites from 95 patients at 337, 380 and 460 nm excitation wavelengths. The multivariate statistical analysis was also employed to reduce the number of fluorescence excitation-emission wavelength pairs required to discriminate healthy tissue samples from pre-cancerous tissue samples. The use of connectionist methods such as multi layered perceptrons, radial basis function networks, and ensembles of such networks was investigated. RBF ensemble algorithms based on fluorescence spectra potentially provide automated, and near real-time implementation of pre-cancer detection in the hands of non-experts. The results are more reliable, direct and accurate than those achieved by either human experts or multivariate statistical algorithms.
Robust Combining of Disparate Classifiers through Order Statistics
Venue: arXiv cs.LG 1999
Year: 1999

Integrating the outputs of multiple classifiers via combiners or meta-learners has led to substantial improvements in several difficult pattern recognition problems. In the typical setting investigated till now, each classifier is trained on data taken or resampled from a common data set, or (almost) randomly selected subsets thereof, and thus experiences similar quality of training data. However, in certain situations where data is acquired and analyzed on-line at several geographically distributed locations, the quality of data may vary substantially, leading to large discrepancies in performance of individual classifiers. In this article we introduce and investigate a family of classifiers based on order statistics, for robust handling of such cases. Based on a mathematical modeling of how the decision boundaries are affected by order statistic combiners, we derive expressions for the reductions in error expected when such combiners are used. We show analytically that the selection of the median, the maximum and in general, the $i^{th}$ order statistic improves classification performance. Furthermore, we introduce the trim and spread combiners, both based on linear combinations of the ordered classifier outputs, and show that they are quite beneficial in presence of outliers or uneven classifier performance. Experimental results on several public domain data sets corroborate these findings.
SCR3: towards usability of formal methods
Venue: arXiv cs.SE 1999
Year: 1999

This paper gives an overview of SCR3 -- a toolset designed to increase the usability of formal methods for software development. Formal requirements are specified in SCR3 in an easy to use and review format, and then used in checking requirements for correctness and in verifying consistency between annotated code and requirements. In this paper we discuss motivations behind this work, describe several tools which are part of SCR3, and illustrate their operation on an example of a Cruise Control system.
A Bootstrap Approach to Automatically Generating Lexical Transfer Rules
Venue: arXiv cs.CL 1999
Year: 1999

We describe a method for automatically generating Lexical Transfer Rules (LTRs) from word equivalences using transfer rule templates. Templates are skeletal LTRs, unspecified for words. New LTRs are created by instantiating a template with words, provided that the words belong to the appropriate lexical categories required by the template. We define two methods for creating an inventory of templates and using them to generate new LTRs. A simpler method consists of extracting a finite set of templates from a sample of hand coded LTRs and directly using them in the generation process. A further method consists of abstracting over the initial finite set of templates to define higher level templates, where bilingual equivalences are defined in terms of correspondences involving phrasal categories. Phrasal templates are then mapped onto sets of lexical templates with the aid of grammars. In this way an infinite set of lexical templates is recursively defined. New LTRs are created by parsing input words, matching a template at the phrasal level and using the corresponding lexical categories to instantiate the lexical template. The definition of an infinite set of templates enables the automatic creation of LTRs for multi-word, non-compositional word equivalences of any cardinality.
Weak length induction and slow growing depth boolean circuits
Venue: arXiv cs.LO 1999
Year: 1999

We define a hierarchy of circuit complexity classes LD^i, whose depth are the inverse of a function in Ackermann hierarchy. Then we introduce extremely weak versions of length induction and construct a bounded arithmetic theory L^i_2 whose provably total functions exactly correspond to functions computable by LD^i circuits. Finally, we prove a non-conservation result between L^i_2 and a weaker theory AC^0CA which corresponds to the class AC^0. Our proof utilizes KPT witnessing theorem.
Further Results on Arithmetic Filters for Geometric Predicates
Venue: arXiv cs.CG 1999
Year: 1999

An efficient technique to solve precision problems consists in using exact computations. For geometric predicates, using systematically expensive exact computations can be avoided by the use of filters. The predicate is first evaluated using rounding computations, and an error estimation gives a certificate of the validity of the result. In this note, we studies the statistical efficiency of filters for cosphericity predicate with an assumption of regular distribution of the points. We prove that the expected value of the polynomial corresponding to the in sphere test is greater than epsilon with probability O(epsilon log 1/epsilon) improving the results of a previous paper by the same authors.
Beta-Skeletons have Unbounded Dilation
Venue: arXiv cs.CG 1999
Year: 1999

A fractal construction shows that, for any beta>0, the beta-skeleton of a point set can have arbitrarily large dilation. In particular this applies to the Gabriel graph.
Computational Geometry Column 37
Venue: arXiv cs.CG 1999
Year: 1999

Open problems from the 15th Annual ACM Symposium on Computational Geometry.
Safe Deals Between Strangers
Venue: arXiv cs.CR 1999
Year: 1999

E-business, information serving, and ubiquitous computing will create heavy request traffic from strangers or even incognitos. Such requests must be managed automatically. Two ways of doing this are well known: giving every incognito consumer the same treatment, and rendering service in return for money. However, different behavior will be often wanted, e.g., for a university library with different access policies for undergraduates, graduate students, faculty, alumni, citizens of the same state, and everyone else. For a data or process server contacted by client machines on behalf of users not previously known, we show how to provide reliable automatic access administration conforming to service agreements. Implementations scale well from very small collections of consumers and producers to immense client/server networks. Servers can deliver information, effect state changes, and control external equipment. Consumer privacy is easily addressed by the same protocol. We support consumer privacy, but allow servers to deny their resources to incognitos. A protocol variant even protects against statistical attacks by consortia of service organizations. One e-commerce application would put the consumer's tokens on a smart card whose readers are in vending kiosks. In e-business we can simplify supply chain administration. Our method can also be used in sensitive networks without introducing new security loopholes.
Collective Intelligence for Control of Distributed Dynamical Systems
Venue: arXiv cs.LG 1999
Year: 1999

We consider the El Farol bar problem, also known as the minority game (W. B. Arthur, ``The American Economic Review'', 84(2): 406--411 (1994), D. Challet and Y.C. Zhang, ``Physica A'', 256:514 (1998)). We view it as an instance of the general problem of how to configure the nodal elements of a distributed dynamical system so that they do not ``work at cross purposes'', in that their collective dynamics avoids frustration and thereby achieves a provided global goal. We summarize a mathematical theory for such configuration applicable when (as in the bar problem) the global goal can be expressed as minimizing a global energy function and the nodes can be expressed as minimizers of local free energy functions. We show that a system designed with that theory performs nearly optimally for the bar problem.
Distributed Algorithms in Multihop Broadcast Networks
Venue: arXiv cs.DC 1999
Year: 1999

Broadcast networks are often used in modern communication systems. A common broadcast network is a single hop shared media system, where a transmitted message is heard by all neighbors, such as some LAN networks. In this work we consider a more complex environment, in which a transmitted message is heard only by a group of neighbors, such as Ad-Hoc networks, satellite and radio networks, as well as wireless multistation backbone system for mobile communication. It is important to design efficient algorithms for such environments. Our main result is a new Leader Election algorithm, with O(n) time complexity and O(n*lg(n)) message transmission complexity. Our distributed solution uses a propagation of information with feedback (PIF) building block tuned to the broadcast media, and a special counting and joining approach for the election procedure phase. The latter is required for achieving the linear time. It is demonstrated that the broadcast model requires solutions which are different from the known point-to-point model.
Certificate Revocation Paradigms
Venue: arXiv cs.CR 1999
Year: 1999

Research in the field of electronic signature confirmation has been active for some 20 years now. Unfortunately present certificate-based solutions also come from that age when no-one knew about online data transmission. The official standardized X.509 framework also depends heavily on offline operations, one of the most complicated ones being certificate revocation handling. This is done via huge Certificate Revocation Lists which are both inconvenient and expencive. Several improvements to these lists are proposed and in this report we try to analyze them briefly. We conclude that although it is possible to do better than in the original X.509 setting, none of the solutions presented this far is good enough.
A decision-theoretic approach to reliable message delivery
Venue: arXiv cs.DC 1999
Year: 1999

We argue that the tools of decision theory need to be taken more seriously in the specification and analysis of systems. We illustrate this by considering a simple problem involving reliable communication, showing how considerations of utility and probability can be used to decide when it is worth sending heartbeat messages and, if they are sent, how often they should be sent.
An Introduction to Query Order
Venue: arXiv cs.CC 1999
Year: 1999

Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] raised the following questions: If one is allowed one question to each of two different information sources, does the order in which one asks the questions affect the class of problems that one can solve with the given access? If so, which order yields the greater computational power? The answers to these questions have been learned-inasfar as they can be learned without resolving whether or not the polynomial hierarchy collapses-for both the polynomial hierarchy and the boolean hierarchy. In the polynomial hierarchy, query order never matters. In the boolean hierarchy, query order sometimes does not matter and, unless the polynomial hierarchy collapses, sometimes does matter. Furthermore, the study of query order has yielded dividends in seemingly unrelated areas, such as bottleneck computations and downward translation of equality. In this article, we present some of the central results on query order. The article is written in such a way as to encourage the reader to try his or her own hand at proving some of these results. We also give literature pointers to the quickly growing set of related results and applications.
Consistent Checkpointing in Distributed Databases: Towards a Formal Approach
Venue: arXiv cs.DB 1999
Year: 1999

Whether it is for audit or for recovery purposes, data checkpointing is an important problem of distributed database systems. Actually, transactions establish dependence relations on data checkpoints taken by data object managers. So, given an arbitrary set of data checkpoints (including at least a single data checkpoint from a data manager, and at most a data checkpoint from each data manager), an important question is the following one: ``Can these data checkpoints be members of a same consistent global checkpoint?''. This paper answers this question by providing a necessary and sufficient condition suited for database systems. Moreover, to show the usefulness of this condition, two {\em non-intrusive} data checkpointing protocols are derived from this condition. It is also interesting to note that this paper, by exhibiting ``correspondences'', establishes a bridge between the data object/transaction model and the process/message-passing model.
Efficient and Extensible Algorithms for Multi Query Optimization
Venue: arXiv cs.DB 1999
Year: 1999

Complex queries are becoming commonplace, with the growing use of decision support systems. These complex queries often have a lot of common sub-expressions, either within a single query, or across multiple such queries run as a batch. Multi-query optimization aims at exploiting common sub-expressions to reduce evaluation cost. Multi-query optimization has hither-to been viewed as impractical, since earlier algorithms were exhaustive, and explore a doubly exponential search space. In this paper we demonstrate that multi-query optimization using heuristics is practical, and provides significant benefits. We propose three cost-based heuristic algorithms: Volcano-SH and Volcano-RU, which are based on simple modifications to the Volcano search strategy, and a greedy heuristic. Our greedy heuristic incorporates novel optimizations that improve efficiency greatly. Our algorithms are designed to be easily added to existing optimizers. We present a performance study comparing the algorithms, using workloads consisting of queries from the TPC-D benchmark. The study shows that our algorithms provide significant benefits over traditional optimization, at a very acceptable overhead in optimization time.
Semantics of Programming Languages: A Tool-Oriented Approach
Venue: arXiv cs.PL 1999
Year: 1999

By paying more attention to semantics-based tool generation, programming language semantics can significantly increase its impact. Ultimately, this may lead to ``Language Design Assistants'' incorporating substantial amounts of semantic knowledge.
One-Level Prosodic Morphology
Venue: arXiv cs.CL 1999
Year: 1999

Recent developments in theoretical linguistics have lead to a widespread acceptance of constraint-based analyses of prosodic morphology phenomena such as truncation, infixation, floating morphemes and reduplication. Of these, reduplication 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 argue for certain extensions to the one-level model of phonology and morphology (Bird & Ellison 1994) to cover the computational aspects of prosodic morphology using finite-state methods. In a nutshell, enriched lexical representations provide additional automaton arcs to repeat or skip sounds and also to allow insertion of additional material. A kind of resource consciousness is introduced to control this additional freedom, distinguishing between producer and consumer arcs. The non-finite-state copying aspect of reduplication is mapped to automata intersection, itself a non-finite-state operation. Bounded local optimization prunes certain automaton arcs that fail to contribute to linguistic optimisation criteria. The paper then presents implemented case studies of Ulwa construct state infixation, German hypocoristic truncation and Tagalog over-applying reduplication that illustrate the expressive power of this approach, before its merits and limitations are discussed and possible extensions are sketched. I conclude that the one-level approach to prosodic morphology presents an attractive way of extending finite-state techniques to difficult phenomena that hitherto resisted elegant computational analyses.
The phase transition in random Horn satisfiability and its algorithmic implications
Venue: arXiv cs.DS 1999
Year: 1999

Let c>0 be a constant, and $Φ$ be a random Horn formula with n variables and $m=c\cdot 2^{n}$ clauses, chosen uniformly at random (with repetition) from the set of all nonempty Horn clauses in the given variables. By analyzing \PUR, a natural implementation of positive unit resolution, we show that $\lim_{n\goesto \infty} \PR ({$Φ$ is satisfiable})= 1-F(e^{-c})$, where $F(x)=(1-x)(1-x^2)(1-x^4)(1-x^8)... $. Our method also yields as a byproduct an average-case analysis of this algorithm.
Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs
Venue: arXiv cs.DS 1999
Year: 1999

We develop data structures for dynamic closest pair problems with arbitrary distance functions, that do not necessarily come from any geometric structure on the objects. Based on a technique previously used by the author for Euclidean closest pairs, we show how to insert and delete objects from an n-object set, maintaining the closest pair, in O(n log^2 n) time per update and O(n) space. With quadratic space, we can instead use a quadtree-like structure to achieve an optimal time bound, O(n) per update. We apply these data structures to hierarchical clustering, greedy matching, and TSP heuristics, and discuss other potential applications in machine learning, Groebner bases, and local improvement algorithms for partition and placement problems. Experiments show our new methods to be faster in practice than previously used heuristics.
Multiplicative Algorithm for Orthgonal Groups and Independent Component Analysis
Venue: arXiv cs.LG 2000
Year: 2000

The multiplicative Newton-like method developed by the author et al. is extended to the situation where the dynamics is restricted to the orthogonal group. A general framework is constructed without specifying the cost function. Though the restriction to the orthogonal groups makes the problem somewhat complicated, an explicit expression for the amount of individual jumps is obtained. This algorithm is exactly second-order-convergent. The global instability inherent in the Newton method is remedied by a Levenberg-Marquardt-type variation. The method thus constructed can readily be applied to the independent component analysis. Its remarkable performance is illustrated by a numerical simulation.
Adaptive simulated annealing (ASA): Lessons learned
Venue: arXiv cs.MS 2000
Year: 2000

Adaptive simulated annealing (ASA) is a global optimization algorithm based on an associated proof that the parameter space can be sampled much more efficiently than by using other previous simulated annealing algorithms. The author's ASA code has been publicly available for over two years. During this time the author has volunteered to help people via e-mail, and the feedback obtained has been used to further develop the code. Some lessons learned, in particular some which are relevant to other simulated annealing algorithms, are described.
Refinement of a Structured Language Model
Venue: arXiv cs.CL 2000
Year: 2000

A new language model for speech recognition inspired by linguistic analysis is presented. The model develops hidden hierarchical structure incrementally and uses it to extract meaningful information from the word history - thus enabling the use of extended distance dependencies - in an attempt to complement the locality of currently used n-gram Markov models. The model, its probabilistic parametrization, a reestimation algorithm for the model parameters and a set of experiments meant to evaluate its potential for speech recognition are presented.
Recognition Performance of a Structured Language Model
Venue: arXiv cs.CL 2000
Year: 2000

A new language model for speech recognition inspired by linguistic analysis is presented. The model develops hidden hierarchical structure incrementally and uses it to extract meaningful information from the word history - thus enabling the use of extended distance dependencies - in an attempt to complement the locality of currently used trigram models. The structured language model, its probabilistic parameterization and performance in a two-pass speech recognizer are presented. Experiments on the SWITCHBOARD corpus show an improvement in both perplexity and word error rate over conventional trigram models.
Structured Language Modeling for Speech Recognition
Venue: arXiv cs.CL 2000
Year: 2000

A new language model for speech recognition is presented. The model develops hidden hierarchical syntactic-like structure incrementally and uses it to extract meaningful information from the word history, thus complementing the locality of currently used trigram models. The structured language model (SLM) and its performance in a two-pass speech recognizer --- lattice decoding --- are presented. Experiments on the WSJ corpus show an improvement in both perplexity (PPL) and word error rate (WER) over conventional trigram models.