OpenRaiser/Intern-Atlas huggingface dataset:
A New Ranking Principle for Multimedia Information Retrieval
Venue: arXiv cs.DL 1999
Year: 1999

A theoretic framework for multimedia information retrieval is introduced which guarantees optimal retrieval effectiveness. In particular, a Ranking Principle for Distributed Multimedia-Documents (RPDM) is described together with an algorithm that satisfies this principle. Finally, the RPDM is shown to be a generalization of the Probability Ranking principle (PRP) which guarantees optimal retrieval effectiveness in the case of text document retrieval. The PRP justifies theoretically the relevance ranking adopted by modern search engines. In contrast to the classical PRP, the new RPDM takes into account transmission and inspection time, and most importantly, aspectual recall rather than simple recall.
Autocatalytic Theory of Meaning
Venue: arXiv cs.CL 1999
Year: 1999

Recently it has been argued that autocatalytic theory could be applied to the origin of culture. Here possible application to a theory of meaning in the philosophy of language, called radical interpretation, is commented upon and compared to previous applications.
A Formal Framework for Linguistic Annotation
Venue: arXiv cs.CL 1999
Year: 1999

`Linguistic annotation' covers any descriptive or analytic notations applied to raw language data. The basic data may be in the form of time functions -- audio, video and/or physiological recordings -- or it may be textual. The added notations may include transcriptions of all sorts (from phonetic features to discourse structures), part-of-speech and sense tagging, syntactic analysis, `named entity' identification, co-reference annotation, and so on. While there are several ongoing efforts to provide formats and tools for such annotations and to publish annotated linguistic databases, the lack of widely accepted standards is becoming a critical problem. Proposed standards, to the extent they exist, have focussed on file formats. This paper focuses instead on the logical structure of linguistic annotations. We survey a wide variety of existing annotation formats and demonstrate a common conceptual core, the annotation graph. This provides a formal framework for constructing, maintaining and searching linguistic annotations, while remaining consistent with many alternative data structures and file formats.
Numeration systems on a regular language
Venue: arXiv cs.OH 1999
Year: 1999

Generalizations of linear numeration systems in which the set of natural numbers is recognizable by finite automata are obtained by describing an arbitrary infinite regular language following the lexicographic ordering. For these systems of numeration, we show that ultimately periodic sets are recognizable. We also study the translation and the multiplication by constants as well as the order dependence of the recognizability.
Space-Efficient Routing Tables for Almost All Networks and the Incompressibility Method
Venue: arXiv cs.DC 1999
Year: 1999

We use the incompressibility method based on Kolmogorov complexity to determine the total number of bits of routing information for almost all network topologies. In most models for routing, for almost all labeled graphs $Θ(n^2)$ bits are necessary and sufficient for shortest path routing. By `almost all graphs' we mean the Kolmogorov random graphs which constitute a fraction of $1-1/n^c$ of all graphs on $n$ nodes, where $c > 0$ is an arbitrary fixed constant. There is a model for which the average case lower bound rises to $Ω(n^2 \log n)$ and another model where the average case upper bound drops to $O(n \log^2 n)$. This clearly exposes the sensitivity of such bounds to the model under consideration. If paths have to be short, but need not be shortest (if the stretch factor may be larger than 1), then much less space is needed on average, even in the more demanding models. Full-information routing requires $Θ(n^3)$ bits on average. For worst-case static networks we prove a $Ω(n^2 \log n)$ lower bound for shortest path routing and all stretch factors $<2$ in some networks where free relabeling is not allowed.
Scholarly Communication and the Continuum of Electronic Publishing
Venue: arXiv cs.CY 1999
Year: 1999

Electronic publishing opportunities, manifested today in a variety of electronic journals and Web-based compendia, have captured the imagination of many scholars. These opportunities have also destabilized norms about the character of legitimate scholarly publishing in some fields. Unfortunately, much of the literature about scholarly e-publishing homogenizes the character of publishing. This article provides an analytical approach for evaluating disciplinary conventions and for proposing policies about scholarly e-publishing. We characterize three dimensions of scholarly publishing as a communicative practice -- publicity, access, and trustworthiness, and examine several forms of paper and electronic publications in this framework. This analysis shows how the common claim that e-publishing "substantially expands access" is over-simplified. It also indicates how peer-reviewing (whether in paper or electronically) provides valuable functions for scholarly communication that are not effectively replaced by self-posting articles in electronic media.
The Study on the Nonlinear Computations of the DQ and DC Methods
Venue: arXiv cs.CE 1999
Year: 1999

This paper points out that the differential quadrature (DQ) and differential cubature (DC) methods due to their global domain property are more efficient for nonlinear problems than the traditional numerical techniques such as finite element and finite difference methods. By introducing the Hadamard product of matrices, we obtain an explicit matrix formulation for the DQ and DC solutions of nonlinear differential and integro-differential equations. Due to its simplicity and flexibility, the present Hadamard product approach makes the DQ and DC methods much easier to be used. Many studies on the Hadamard product can be fully exploited for the DQ and DC nonlinear computations. Furthermore, we first present SJT product of matrix and vector to compute accurately and efficiently the Frechet derivative matrix in the Newton-Raphson method for the solution of the nonlinear formulations. We also propose a simple approach to simplify the DQ or DC formulations for some nonlinear differential operators and thus the computational efficiency of these methods is improved significantly. We give the matrix multiplication formulas to compute efficiently the weighting coefficient matrices of the DC method. The spherical harmonics are suggested as the test functions in the DC method to handle the nonlinear differential equations occurring in global and hemispheric weather forecasting problems. Some examples are analyzed to demonstrate the simplicity and efficiency of the presented techniques. It is emphasized that innovations presented are applicable to the nonlinear computations of the other numerical methods as well.
Transducers from Rewrite Rules with Backreferences
Venue: arXiv cs.CL 1999
Year: 1999

Context sensitive rewrite rules have been widely used in several areas of natural language processing, including syntax, morphology, phonology and speech processing. Kaplan and Kay, Karttunen, and Mohri & Sproat have given various algorithms to compile such rewrite rules into finite-state transducers. The present paper extends this work by allowing a limited form of backreferencing in such rules. The explicit use of backreferencing leads to more elegant and general solutions.
Bounds for Small-Error and Zero-Error Quantum Algorithms
Venue: arXiv cs.CC 1999
Year: 1999

We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-offs between the number of queries of quantum search algorithms, their error probability, the size of the search space, and the number of solutions in this space. Using this, we deduce new lower and upper bounds for quantum versions of amplification problems. Next, we establish nearly optimal quantum-classical separations for the query complexity of monotone functions in the zero-error model (where our quantum zero-error model is defined so as to be robust when the quantum gates are noisy). Also, we present a communication complexity problem related to a total function for which there is a quantum-classical communication complexity gap in the zero-error model. Finally, we prove separations for monotone graph properties in the zero-error and other error models which imply that the evasiveness conjecture for such properties does not hold for quantum computers.
General Principles of Learning-Based Multi-Agent Systems
Venue: arXiv cs.MA 1999
Year: 1999

We consider the problem of how to design large decentralized multi-agent systems (MAS's) in an automated fashion, with little or no hand-tuning. Our approach has each agent run a reinforcement learning algorithm. This converts the problem into one of how to automatically set/update the reward functions for each of the agents so that the global goal is achieved. In particular we do not want the agents to ``work at cross-purposes'' as far as the global goal is concerned. We use the term artificial COllective INtelligence (COIN) to refer to systems that embody solutions to this problem. In this paper we present a summary of a mathematical framework for COINs. We then investigate the real-world applicability of the core concepts of that framework via two computer experiments: we show that our COINs perform near optimally in a difficult variant of Arthur's bar problem (and in particular avoid the tragedy of the commons for that problem), and we also illustrate optimal performance for our COINs in the leader-follower problem.
On Bounded-Weight Error-Correcting Codes
Venue: arXiv cs.IT 1999
Year: 1999

This paper computationally obtains optimal bounded-weight, binary, error-correcting codes for a variety of distance bounds and dimensions. We compare the sizes of our codes to the sizes of optimal constant-weight, binary, error-correcting codes, and evaluate the differences.
Memory-Based Shallow Parsing
Venue: arXiv cs.CL 1999
Year: 1999

We present a memory-based learning (MBL) approach to shallow parsing in which POS tagging, chunking, and identification of syntactic relations are formulated as memory-based modules. The experiments reported in this paper show competitive results, the F-value for the Wall Street Journal (WSJ) treebank is: 93.8% for NP chunking, 94.7% for VP chunking, 77.1% for subject detection and 79.0% for object detection.
Automatically Selecting Useful Phrases for Dialogue Act Tagging
Venue: arXiv cs.AI 1999
Year: 1999

We present an empirical investigation of various ways to automatically identify phrases in a tagged corpus that are useful for dialogue act tagging. We found that a new method (which measures a phrase's deviation from an optimally-predictive phrase), enhanced with a lexical filtering mechanism, produces significantly better cues than manually-selected cue phrases, the exhaustive set of phrases in a training corpus, and phrases chosen by traditional metrics, like mutual information and information gain.
Zero-Parity Stabbing Information
Venue: arXiv cs.CG 1999
Year: 1999

Everett et al. introduced several varieties of stabbing information for the lines determined by pairs of vertices of a simple polygon P, and established their relationships to vertex visibility and other combinatorial data. In the same spirit, we define the ``zero-parity (ZP) stabbing information'' to be a natural weakening of their ``weak stabbing information,'' retaining only the distinction among {zero, odd, even>0} in the number of polygon edges stabbed. Whereas the weak stabbing information's relation to visibility remains an open problem, we completely settle the analogous questions for zero-parity information, with three results: (1) ZP information is insufficient to distinguish internal from external visibility graph edges; (2) but it does suffice for all polygons that avoid a certain complex substructure; and (3) the natural generalization of ZP information to the continuous case of smooth curves does distinguish internal from external visibility.
Computational Geometry Column 35
Venue: arXiv cs.CG 1999
Year: 1999

The subquadratic algorithm of Kapoor for finding shortest paths on a polyhedron is described.
Robust Grammatical Analysis for Spoken Dialogue Systems
Venue: arXiv cs.CL 1999
Year: 1999

We argue that grammatical analysis is a viable alternative to concept spotting for processing spoken input in a practical spoken dialogue system. We discuss the structure of the grammar, and a model for robust parsing which combines linguistic sources of information and statistical sources of information. We discuss test results suggesting that grammatical processing allows fast and accurate processing of spoken input.
Formal Modeling in a Commercial Setting: A Case Study
Venue: arXiv cs.SE 1999
Year: 1999

This paper describes a case study conducted in collaboration with Nortel to demonstrate the feasibility of applying formal modeling techniques to telecommunication systems. A formal description language, SDL, was chosen by our qualitative CASE tool evaluation to model a multimedia-messaging system described by an 80-page natural language specification. Our model was used to identify errors in the software requirements document and to derive test suites, shadowing the existing development process and keeping track of a variety of productivity data.
Annotation graphs as a framework for multidimensional linguistic data analysis
Venue: arXiv cs.CL 1999
Year: 1999

In recent work we have presented a formal framework for linguistic annotation based on labeled acyclic digraphs. These `annotation graphs' offer a simple yet powerful method for representing complex annotation structures incorporating hierarchy and overlap. Here, we motivate and illustrate our approach using discourse-level annotations of text and speech data drawn from the CALLHOME, COCONUT, MUC-7, DAMSL and TRAINS annotation schemes. With the help of domain specialists, we have constructed a hybrid multi-level annotation for a fragment of the Boston University Radio Speech Corpus which includes the following levels: segment, word, breath, ToBI, Tilt, Treebank, coreference and named entity. We show how annotation graphs can represent hybrid multi-level structures which derive from a diverse set of file formats. We also show how the approach facilitates substantive comparison of multiple annotations of a single signal based on different theoretical models. The discussion shows how annotation graphs open the door to wide-ranging integration of tools, formats and corpora.
Designing and Mining Multi-Terabyte Astronomy Archives: The Sloan Digital Sky Survey
Venue: arXiv cs.DB 1999
Year: 1999

The next-generation astronomy digital archives will cover most of the universe at fine resolution in many wave-lengths, from X-rays to ultraviolet, optical, and infrared. The archives will be stored at diverse geographical locations. One of the first of these projects, the Sloan Digital Sky Survey (SDSS) will create a 5-wavelength catalog over 10,000 square degrees of the sky (see http://www.sdss.org/). The 200 million objects in the multi-terabyte database will have mostly numerical attributes, defining a space of 100+ dimensions. Points in this space have highly correlated distributions. The archive will enable astronomers to explore the data interactively. Data access will be aided by a multidimensional spatial index and other indices. The data will be partitioned in many ways. Small tag objects consisting of the most popular attributes speed up frequent searches. Splitting the data among multiple servers enables parallel, scalable I/O and applies parallel processing to the data. Hashing techniques allow efficient clustering and pair-wise comparison algorithms that parallelize nicely. Randomly sampled subsets allow debugging otherwise large queries at the desktop. Central servers will operate a data pump that supports sweeping searches that touch most of the data. The anticipated queries require special operators related to angular distances and complex similarity tests of object properties, like shapes, colors, velocity vectors, or temporal behaviors. These issues pose interesting data management challenges.
Language Identification With Confidence Limits
Venue: arXiv cs.CL 1999
Year: 1999

A statistical classification algorithm and its application to language identification from noisy input are described. The main innovation is to compute confidence limits on the classification, so that the algorithm terminates when enough evidence to make a clear decision has been made, and so avoiding problems with categories that have similar characteristics. A second application, to genre identification, is briefly examined. The results show that some of the problems of other language identification techniques can be avoided, and illustrate a more important point: that a statistical language process can be used to provide feedback about its own success rate.
A Reasonable C++ Wrappered Java Native Interface
Venue: arXiv cs.SE 1999
Year: 1999

A reasonable C++ Java Native Interface (JNI) technique termed C++ Wrappered JNI (C++WJ) is presented. The technique simplifies current error-prone JNI development by wrappering JNI calls. Provided development is done with the aid of a C++ compiler, C++WJ offers type checking and behind the scenes caching. A tool (jH) patterned on javah automates the creation of C++WJ classes. The paper presents the rationale behind the choices that led to C++WJ. Handling of Java class and interface hierarchy including Java type downcasts is discussed. Efficiency considerations in the C++WJ lead to two flavors of C++ classes: jtypes and Jtypes. A jtype is a lightweight less than full wrapper of a JNI object reference. A Jtype is a heavyweight full wrapper of a JNI object reference.
Architectural Considerations for Conversational Systems -- The Verbmobil/INTARC Experience
Venue: arXiv cs.CL 1999
Year: 1999

The paper describes the speech to speech translation system INTARC, developed during the first phase of the Verbmobil project. The general design goals of the INTARC system architecture were time synchronous processing as well as incrementality and interactivity as a means to achieve a higher degree of robustness and scalability. Interactivity means that in addition to the bottom-up (in terms of processing levels) data flow the ability to process top-down restrictions considering the same signal segment for all processing levels. The construction of INTARC 2.0, which has been operational since fall 1996, followed an engineering approach focussing on the integration of symbolic (linguistic) and stochastic (recognition) techniques which led to a generalization of the concept of a ``one pass'' beam search.
Improved Incremental Randomized Delaunay Triangulation
Venue: arXiv cs.CG 1999
Year: 1999

We propose a new data structure to compute the Delaunay triangulation of a set of points in the plane. It combines good worst case complexity, fast behavior on real data, and small memory occupation. The location structure is organized into several levels. The lowest level just consists of the triangulation, then each level contains the triangulation of a small sample of the levels below. Point location is done by marching in a triangulation to determine the nearest neighbor of the query at that level, then the march restarts from that neighbor at the level below. Using a small sample (3%) allows a small memory occupation; the march and the use of the nearest neighbor to change levels quickly locate the query.
Easy Sets and Hard Certificate Schemes
Venue: arXiv cs.CC 1999
Year: 1999

Can easy sets only have easy certificate schemes? In this paper, we study the class of sets that, for all NP certificate schemes (i.e., NP machines), always have easy acceptance certificates (i.e., accepting paths) that can be computed in polynomial time. We also study the class of sets that, for all NP certificate schemes, infinitely often have easy acceptance certificates. In particular, we provide equivalent characterizations of these classes in terms of relative generalized Kolmogorov complexity, showing that they are robust. We also provide structural conditions---regarding immunity and class collapses---that put upper and lower bounds on the sizes of these two classes. Finally, we provide negative results showing that some of our positive claims are optimal with regard to being relativizable. Our negative results are proven using a novel observation: we show that the classical ``wide spacing'' oracle construction technique yields instant non-bi-immunity results. Furthermore, we establish a result that improves upon Baker, Gill, and Solovay's classical result that NP \neq P = NP \cap coNP holds in some relativized world.
Characterizations of the Existence of Partial and Total One-Way Permutations
Venue: arXiv cs.CC 1999
Year: 1999

In this note, we study the easy certificate classes introduced by Hemaspaandra, Rothe, and Wechsung, with regard to the question of whether or not surjective one-way functions exist. This is an important open question in cryptology. We show that the existence of partial one-way permutations can be characterized by separating P from the class of UP sets that, for all unambiguous polynomial-time Turing machines accepting them, always have easy (i.e., polynomial-time computable) certificates. This extends results of Grollmann and Selman. By Grädel's recent results about one-way functions, this also links statements about easy certificates of NP sets with statements in finite model theory. Similarly, there exist surjective poly-one one-way functions if and only if there is a set L in P such that not all FewP machines accepting L always have easy certificates. We also establish a condition necessary and sufficient for the existence of (total) one-way permutations.
A simple C++ library for manipulating scientific data sets as structured data
Venue: arXiv cs.CE 1999
Year: 1999

Representing scientific data sets efficiently on external storage usually involves converting them to a byte string representation using specialized reader/writer routines. The resulting storage files are frequently difficult to interpret without these specialized routines as they do not contain information about the logical structure of the data. Avoiding such problems usually involves heavy-weight data format libraries or data base systems. We present a simple C++ library that allows to create and access data files that store structured data. The structure of the data is described by a data type that can be built from elementary data types (integer and floating-point numbers, byte strings) and composite data types (arrays, structures, unions). An abstract data access class presents the data to the application. Different actual data file structures can be implemented under this layer. This method is particularly suited to applications that require complex data structures, e.g. molecular dynamics simulations. Extensions such as late type binding and object persistence are discussed.