OpenRaiser/Intern-Atlas huggingface dataset:
Compacting the Penn Treebank Grammar
Venue: arXiv cs.CL 1999
Year: 1999

Treebanks, such as the Penn Treebank (PTB), offer a simple approach to obtaining a broad coverage grammar: one can simply read the grammar off the parse trees in the treebank. While such a grammar is easy to obtain, a square-root rate of growth of the rule set with corpus size suggests that the derived grammar is far from complete and that much more treebanked text would be required to obtain a complete grammar, if one exists at some limit. However, we offer an alternative explanation in terms of the underspecification of structures within the treebank. This hypothesis is explored by applying an algorithm to compact the derived grammar by eliminating redundant rules -- rules whose right hand sides can be parsed by other rules. The size of the resulting compacted grammar, which is significantly less than that of the full treebank grammar, is shown to approach a limit. However, such a compacted grammar does not yield very good performance figures. A version of the compaction algorithm taking rule probabilities into account is proposed, which is argued to be more linguistically motivated. Combined with simple thresholding, this method can be used to give a 58% reduction in grammar size without significant change in parsing performance, and can produce a 69% reduction with some gain in recall, but a loss in precision.
Automatic Identification of Subjects for Textual Documents in Digital Libraries
Venue: arXiv cs.DL 1999
Year: 1999

The amount of electronic documents in the Internet grows very quickly. How to effectively identify subjects for documents becomes an important issue. In past, the researches focus on the behavior of nouns in documents. Although subjects are composed of nouns, the constituents that determine which nouns are subjects are not only nouns. Based on the assumption that texts are well-organized and event-driven, nouns and verbs together contribute the process of subject identification. This paper considers four factors: 1) word importance, 2) word frequency, 3) word co-occurrence, and 4) word distance and proposes a model to identify subjects for textual documents. The preliminary experiments show that the performance of the proposed model is close to that of human beings.
Multiparty computation unconditionally secure against Q^2 adversary structures
Venue: arXiv cs.CR 1999
Year: 1999

We present here a generalization of the work done by Rabin and Ben-Or. We give a protocol for multiparty computation which tolerates any Q^2 active adversary structure based on the existence of a broadcast channel, secure communication between each pair of participants, and a monotone span program with multiplication tolerating the structure. The secrecy achieved is unconditional although we allow an exponentially small probability of error. This is possible due to a protocol for computing the product of two values already shared by means of a homomorphic commitment scheme which appeared originally in a paper of Chaum, Evertse and van de Graaf.
Content-Based Book Recommending Using Learning for Text Categorization
Venue: arXiv cs.DL 1999
Year: 1999

Recommender systems improve access to relevant products and information by making personalized suggestions based on previous examples of a user's likes and dislikes. Most existing recommender systems use social filtering methods that base recommendations on other users' preferences. By contrast, content-based methods use information about an item itself to make suggestions. This approach has the advantage of being able to recommended previously unrated items to users with unique interests and to provide explanations for its recommendations. We describe a content-based book recommending system that utilizes information extraction and a machine-learning algorithm for text categorization. Initial experimental results demonstrate that this approach can produce accurate recommendations.
Using Query Mediators for Distributed Searching in Federated Digital Libraries
Venue: arXiv cs.DL 1999
Year: 1999

We describe an architecture and investigate the characteristics of distributed searching in federated digital libraries. We introduce the notion of a query mediator as a digital library service responsible for selecting among available search engines, routing queries to those search engines, and aggregating results. We examine operational data from the NCSTRL distributed digital library that reveals a number of characteristics of distributed resource discovery. These include availability and response time of indexers and the distinction between the query mediator view of these characteristics and the indexer view.
Visualization of Retrieved Documents using a Presentation Server
Venue: arXiv cs.DL 1999
Year: 1999

In any search-based digital library (DL) systems dealing with a non-trivial number of documents, users are often required to go through a long list of short document descriptions in order to identify what they are looking for. To tackle the problem, a variety of document organization algorithms and/or visualization techniques have been used to guide users in selecting relevant documents. Since these techniques require heavy computations, however, we developed a presentation server designed to serve as an intermediary between retrieval servers and clients equipped with a visualization interface. In addition, we designed our own visual interface by which users can view a set of documents from different perspectives through layers of document maps. We finally ran experiments to show that the visual interface, in conjunction with the presentation server, indeed helps users in selecting relevant documents from the retrieval results.
An Efficient Mean Field Approach to the Set Covering Problem
Venue: arXiv cs.NE 1999
Year: 1999

A mean field feedback artificial neural network algorithm is developed and explored for the set covering problem. A convenient encoding of the inequality constraints is achieved by means of a multilinear penalty function. An approximate energy minimum is obtained by iterating a set of mean field equations, in combination with annealing. The approach is numerically tested against a set of publicly available test problems with sizes ranging up to 5x10^3 rows and 10^6 columns. When comparing the performance with exact results for sizes where these are available, the approach yields results within a few percent from the optimal solutions. Comparisons with other approximate methods also come out well, in particular given the very low CPU consumption required -- typically a few seconds. Arbitrary problems can be processed using the algorithm via a public domain server.
Probabilistic Inductive Inference:a Survey
Venue: arXiv cs.LG 1999
Year: 1999

Inductive inference is a recursion-theoretic theory of learning, first developed by E. M. Gold (1967). This paper surveys developments in probabilistic inductive inference. We mainly focus on finite inference of recursive functions, since this simple paradigm has produced the most interesting (and most complex) results.
An Algebraic Programming Style for Numerical Software and its Optimization
Venue: arXiv cs.SE 1999
Year: 1999

The abstract mathematical theory of partial differential equations (PDEs) is formulated in terms of manifolds, scalar fields, tensors, and the like, but these algebraic structures are hardly recognizable in actual PDE solvers. The general aim of the Sophus programming style is to bridge the gap between theory and practice in the domain of PDE solvers. Its main ingredients are a library of abstract datatypes corresponding to the algebraic structures used in the mathematical theory and an algebraic expression style similar to the expression style used in the mathematical theory. Because of its emphasis on abstract datatypes, Sophus is most naturally combined with object-oriented languages or other languages supporting abstract datatypes. The resulting source code patterns are beyond the scope of current compiler optimizations, but are sufficiently specific for a dedicated source-to-source optimizer. The limited, domain-specific, character of Sophus is the key to success here. This kind of optimization has been tested on computationally intensive Sophus style code with promising results. The general approach may be useful for other styles and in other application domains as well.
Designing SAT for HCP
Venue: arXiv cs.LO 1999
Year: 1999

For arbitrary undirected graph $G$, we are designing SATISFIABILITY problem (SAT) for HCP, using tools of Boolean algebra only. The obtained SAT be the logic formulation of conditions for Hamiltonian cycle existence, and use $m$ Boolean variables, where $m$ is the number of graph edges. This Boolean expression is true if and only if an initial graph is Hamiltonian. That is, each satisfying assignment of the Boolean variables determines a Hamiltonian cycle of $G$, and each Hamiltonian cycle of $G$ corresponds to a satisfying assignment of the Boolean variables. In common case, the obtained Boolean expression may has an exponential length (the number of Boolean literals).
Formalization of the class of problems solvable by a nondeterministic Turing machine
Venue: arXiv cs.DS 1999
Year: 1999

The objective of this article is to formalize the definition of NP problems. We construct a mathematical model of discrete problems as independence systems with weighted elements. We introduce two auxiliary sets that characterize the solution of the problem: the adjoint set, which contains the elements from the original set none of which can be adjoined to the already chosen solution elements; and the residual set, in which every element can be adjoined to previously chosen solution elements. In a problem without lookahead, every adjoint set can be generated by the solution algorithm effectively, in polynomial time. The main result of the study is the assertion that the NP class is identical with the class of problems without lookahead. Hence it follows that if we fail to find an effective (polynomial-time) solution algorithm for a given problem, then we need to look for an alternative formulation of the problem in set of problems without lookahead.
Modeling Belief in Dynamic Systems, Part II: Revision and Update
Venue: arXiv cs.AI 1999
Year: 1999

The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. In a companion paper (Friedman & Halpern, 1997), we introduce a new framework to model belief change. This framework combines temporal and epistemic modalities with a notion of plausibility, allowing us to examine the change of beliefs over time. In this paper, we show how belief revision and belief update can be captured in our framework. This allows us to compare the assumptions made by each method, and to better understand the principles underlying them. In particular, it shows that Katsuno and Mendelzon's notion of belief update (Katsuno & Mendelzon, 1991a) depends on several strong assumptions that may limit its applicability in artificial intelligence. Finally, our analysis allow us to identify a notion of minimal change that underlies a broad range of belief change operations including revision and update.
The Structure of Weighting Coefficient Matrices of Harmonic Differential Quadrature and Its Applications
Venue: arXiv cs.CE 1999
Year: 1999

The structure of weighting coefficient matrices of Harmonic Differential Quadrature (HDQ) is found to be either centrosymmetric or skew centrosymmetric depending on the order of the corresponding derivatives. The properties of both matrices are briefly discussed in this paper. It is noted that the computational effort of the harmonic quadrature for some problems can be further reduced up to 75 per cent by using the properties of the above-mentioned matrices.
Jacobian matrix: a bridge between linear and nonlinear polynomial-only problems
Venue: arXiv cs.CE 1999
Year: 1999

By using the Hadamard matrix product concept, this paper introduces two generalized matrix formulation forms of numerical analogue of nonlinear differential operators. The SJT matrix-vector product approach is found to be a simple, efficient and accurate technique in the calculation of the Jacobian matrix of the nonlinear discretization by finite difference, finite volume, collocation, dual reciprocity BEM or radial functions based numerical methods. We also present and prove simple underlying relationship (theorem (3.1)) between general nonlinear analogue polynomials and their corresponding Jacobian matrices, which forms the basis of this paper. By means of theorem 3.1, stability analysis of numerical solutions of nonlinear initial value problems can be easily handled based on the well-known results for linear problems. Theorem 3.1 also leads naturally to the straightforward extension of various linear iterative algorithms such as the SOR, Gauss-Seidel and Jacobi methods to nonlinear algebraic equations. Since an exact alternative of the quasi-Newton equation is established via theorem 3.1, we derive a modified BFGS quasi-Newton method. A simple formula is also given to examine the deviation between the approximate and exact Jacobian matrices. Furthermore, in order to avoid the evaluation of the Jacobian matrix and its inverse, the pseudo-Jacobian matrix is introduced with a general applicability of any nonlinear systems of equations. It should be pointed out that a large class of real-world nonlinear problems can be modeled or numerically discretized polynomial-only algebraic system of equations. The results presented here are in general applicable for all these problems. This paper can be considered as a starting point in the research of nonlinear computation and analysis from an innovative viewpoint.
A Machine-Independent Debugger--Revisited
Venue: arXiv cs.PL 1999
Year: 1999

Most debuggers are notoriously machine-dependent, but some recent research prototypes achieve varying degrees of machine-independence with novel designs. Cdb, a simple source-level debugger for C, is completely independent of its target architecture. This independence is achieved by embedding symbol tables and debugging code in the target program, which costs both time and space. This paper describes a revised design and implementation of cdb that reduces the space cost by nearly one-half and the time cost by 13% by storing symbol tables in external files. A symbol table is defined by a 31-line grammar in the Abstract Syntax Description Language (ASDL). ASDL is a domain-specific language for specifying tree data structures. The ASDL tools accept an ASDL grammar and generate code to construct, read, and write these data structures. Using ASDL automates implementing parts of the debugger, and the grammar documents the symbol table concisely. Using ASDL also suggested simplifications to the interface between the debugger and the target program. Perhaps most important, ASDL emphasizes that symbol tables are data structures, not file formats. Many of the pitfalls of working with low-level file formats can be avoided by focusing instead on high-level data structures and automating the implementation details.
ODP channel objects that provide services transparently for distributing processing systems
Venue: arXiv cs.DC 1999
Year: 1999

This paper describes an architecture for a distributing processing system that would allow remote procedure calls to invoke other services as messages are passed between clients and servers. It proposes that an additional class of data processing objects be located in the software communications channel. The objects in this channel would then be used to enforce protocols on client-server applications without any additional effort by the application programmers. For example, services such as key-management, time-stamping, sequencing and encryption can be implemented at different levels of the software communications stack to provide a complete authentication service. A distributing processing environment could be used to control broadband network data delivery. Architectures and invocation semantics are discussed, Example classes and interfaces for channel objects are given in the Java programming language.
Collective Choice Theory in Collaborative Computing
Venue: arXiv cs.MA 1999
Year: 1999

This paper presents some fundamental collective choice theory for information system designers, particularly those working in the field of computer-supported cooperative work. This paper is focused on a presentation of Arrow's Possibility and Impossibility theorems which form the fundamental boundary on the efficacy of collective choice: voting and selection procedures. It restates the conditions that Arrow placed on collective choice functions in more rigorous second-order logic, which could be used as a set of test conditions for implementations, and a useful probabilistic result for analyzing votes on issue pairs. It also describes some simple collective choice functions. There is also some discussion of how enterprises should approach putting their resources under collective control: giving an outline of a superstructure of performative agents to carry out this function and what distributing processing technology would be needed.
The Design and Analysis of Virtual Network Configuration for a Wireless Mobile ATM Network
Venue: arXiv cs.NI 1999
Year: 1999

This research concentrates on the design and analysis of an algorithm referred to as Virtual Network Configuration (VNC) which uses predicted future states of a system for faster network configuration and management. VNC is applied to the configuration of a wireless mobile ATM network. VNC is built on techniques from parallel discrete event simulation merged with constraints from real-time systems and applied to mobile ATM configuration and handoff. Configuration in a mobile network is a dynamic and continuous process. Factors such as load, distance, capacity and topology are all constantly changing in a mobile environment. The VNC algorithm anticipates configuration changes and speeds the reconfiguration process by pre-computing and caching results. VNC propagates local prediction results throughout the VNC enhanced system. The Global Positioning System is an enabling technology for the use of VNC in mobile networks because it provides location information and accurate time for each node. This research has resulted in well defined structures for the encapsulation of physical processes within Logical Processes and a generic library for enhancing a system with VNC. Enhancing an existing system with VNC is straight forward assuming the existing physical processes do not have side effects. The benefit of prediction is gained at the cost of additional traffic and processing. This research includes an analysis of VNC and suggestions for optimization of the VNC algorithm and its parameters.
An Efficient, Probabilistically Sound Algorithm for Segmentation and Word Discovery
Venue: arXiv cs.CL 1999
Year: 1999

This paper presents a model-based, unsupervised algorithm for recovering word boundaries in a natural-language text from which they have been deleted. The algorithm is derived from a probability model of the source that generated the text. The fundamental structure of the model is specified abstractly so that the detailed component models of phonology, word-order, and word frequency can be replaced in a modular fashion. The model yields a language-independent, prior probability distribution on all possible sequences of all possible words over a given alphabet, based on the assumption that the input was generated by concatenating words from a fixed but unknown lexicon. The model is unusual in that it treats the generation of a complete corpus, regardless of length, as a single event in the probability space. Accordingly, the algorithm does not estimate a probability distribution on words; instead, it attempts to calculate the prior probabilities of various word sequences that could underlie the observed text. Experiments on phonemic transcripts of spontaneous speech by parents to young children suggest that this algorithm is more effective than other proposed algorithms, at least when utterance boundaries are given and the text includes a substantial number of short utterances. Keywords: Bayesian grammar induction, probability models, minimum description length (MDL), unsupervised learning, cognitive modeling, language acquisition, segmentation
Linear and Order Statistics Combiners for Pattern Classification
Venue: arXiv cs.NE 1999
Year: 1999

Several researchers have experimentally shown that substantial improvements can be obtained in difficult pattern recognition problems by combining or integrating the outputs of multiple classifiers. This chapter provides an analytical framework to quantify the improvements in classification results due to combining. The results apply to both linear combiners and order statistics combiners. We first show that to a first order approximation, the error rate obtained over and above the Bayes error rate, is directly proportional to the variance of the actual decision boundaries around the Bayes optimum boundary. Combining classifiers in output space reduces this variance, and hence reduces the "added" error. If N unbiased classifiers are combined by simple averaging, the added error rate can be reduced by a factor of N if the individual errors in approximating the decision boundaries are uncorrelated. Expressions are then derived for linear combiners which are biased or correlated, and the effect of output correlations on ensemble performance is quantified. For order statistics based non-linear combiners, we derive expressions that indicate how much the median, the maximum and in general the ith order statistic can improve classifier performance. The analysis presented here facilitates the understanding of the relationships among error rates, classifier boundary distributions, and combining in output space. Experimental results on several public domain data sets are provided to illustrate the benefits of combining and to support the analytical results.
Learning Efficient Disambiguation
Venue: arXiv cs.CL 1999
Year: 1999

This dissertation analyses the computational properties of current performance-models of natural language parsing, in particular Data Oriented Parsing (DOP), points out some of their major shortcomings and suggests suitable solutions. It provides proofs that various problems of probabilistic disambiguation are NP-Complete under instances of these performance-models, and it argues that none of these models accounts for attractive efficiency properties of human language processing in limited domains, e.g. that frequent inputs are usually processed faster than infrequent ones. The central hypothesis of this dissertation is that these shortcomings can be eliminated by specializing the performance-models to the limited domains. The dissertation addresses "grammar and model specialization" and presents a new framework, the Ambiguity-Reduction Specialization (ARS) framework, that formulates the necessary and sufficient conditions for successful specialization. The framework is instantiated into specialization algorithms and applied to specializing DOP. Novelties of these learning algorithms are 1) they limit the hypotheses-space to include only "safe" models, 2) are expressed as constrained optimization formulae that minimize the entropy of the training tree-bank given the specialized grammar, under the constraint that the size of the specialized model does not exceed a predefined maximum, and 3) they enable integrating the specialized model with the original one in a complementary manner. The dissertation provides experiments with initial implementations and compares the resulting Specialized DOP (SDOP) models to the original DOP models with encouraging results.