OpenRaiser/Intern-Atlas huggingface dataset:
The Generalized Universal Law of Generalization
Venue: arXiv cs.CV 2001
Year: 2001

It has been argued by Shepard that there is a robust psychological law that relates the distance between a pair of items in psychological space and the probability that they will be confused with each other. Specifically, the probability of confusion is a negative exponential function of the distance between the pair of items. In experimental contexts, distance is typically defined in terms of a multidimensional Euclidean space-but this assumption seems unlikely to hold for complex stimuli. We show that, nonetheless, the Universal Law of Generalization can be derived in the more complex setting of arbitrary stimuli, using a much more universal measure of distance. This universal distance is defined as the length of the shortest program that transforms the representations of the two items of interest into one another: the algorithmic information distance. It is universal in the sense that it minorizes every computable distance: it is the smallest computable distance. We show that the universal law of generalization holds with probability going to one-provided the confusion probabilities are computable. We also give a mathematically more appealing form
Common-Face Embeddings of Planar Graphs
Venue: arXiv cs.DS 2001
Year: 2001

Given a planar graph G and a sequence C_1,...,C_q, where each C_i is a family of vertex subsets of G, we wish to find a plane embedding of G, if any exists, such that for each i in {1,...,q}, there is a face F_i in the embedding whose boundary contains at least one vertex from each set in C_i. This problem has applications to the recovery of topological information from geographical data and the design of constrained layouts in VLSI. Let I be the input size, i.e., the total number of vertices and edges in G and the families C_i, counting multiplicity. We show that this problem is NP-complete in general. We also show that it is solvable in O(I log I) time for the special case where for each input family C_i, each set in C_i induces a connected subgraph of the input graph G. Note that the classical problem of simply finding a planar embedding is a further special case of this case with q=0. Therefore, the processing of the additional constraints C_1,...,C_q only incurs a logarithmic factor of overhead.
Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets
Venue: arXiv cs.CE 2001
Year: 2001

In a multiple-object auction, every bidder tries to win as many objects as possible with a bidding algorithm. This paper studies position-randomized auctions, which form a special class of multiple-object auctions where a bidding algorithm consists of an initial bid sequence and an algorithm for randomly permuting the sequence. We are especially concerned with situations where some bidders know the bidding algorithms of others. For the case of only two bidders, we give an optimal bidding algorithm for the disadvantaged bidder. Our result generalizes previous work by allowing the bidders to have unequal budgets. One might naturally anticipate that the optimal expected numbers of objects won by the bidders would be proportional to their budgets. Surprisingly, this is not true. Our new algorithm runs in optimal O(n) time in a straightforward manner. The case with more than two bidders is open.
Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time
Venue: arXiv cs.DS 2001
Year: 2001

A graph is componentwise biconnected if every connected component either is an isolated vertex or is biconnected. We present a linear-time algorithm for the problem of adding the smallest number of edges to make a bipartite graph componentwise biconnected while preserving its bipartiteness. This algorithm has immediate applications for protecting sensitive information in statistical tables.
Computer based Information Systems and Managers' Work
Venue: arXiv cs.CY 2001
Year: 2001

This paper identifies three categories of model: the Technology Impact Model; the Social Impact Model and the Integrationist Model, which imply different views of the "impact" of Information Technology on work organisation. These models are used to structure data from case studies conducted by the authors to explore the implications of the use of computer-based information systems for managers' work. The paper argues that the "impact" of information systems is not a single stable and predictable outcome but a non-linear ongoing process that changes and evolves over time. It also argues that the actions of individuals and groups within an organisation are not wholly determined by outside forces: people can and do react to, and shape, systems in different ways. In this sense, the "impact" of computer-based information systems on managers' work reflects decisions made by managers themselves about how the technology is used.
Learning Policies with External Memory
Venue: arXiv cs.LG 2001
Year: 2001

In order for an agent to perform well in partially observable domains, it is usually necessary for actions to depend on the history of observations. In this paper, we explore a {\it stigmergic} approach, in which the agent's actions include the ability to set and clear bits in an external memory, and the external memory is included as part of the input to the agent. In this case, we need to learn a reactive policy in a highly non-Markovian domain. We explore two algorithms: SARSA(λ), which has had empirical success in partially observable domains, and VAPS, a new algorithm due to Baird and Moore, with convergence guarantees in partially observable domains. We compare the performance of these two algorithms on benchmark problems.
Meaning Sort - Three examples: dictionary construction, tagged corpus construction, and information presentation system
Venue: arXiv cs.CL 2001
Year: 2001

It is often useful to sort words into an order that reflects relations among their meanings as obtained by using a thesaurus. In this paper, we introduce a method of arranging words semantically by using several types of `{\sf is-a}' thesauri and a multi-dimensional thesaurus. We also describe three major applications where a meaning sort is useful and show the effectiveness of a meaning sort. Since there is no doubt that a word list in meaning-order is easier to use than a word list in some random order, a meaning sort, which can easily produce a word list in meaning-order, must be useful and effective.
CRL at Ntcir2
Venue: arXiv cs.CL 2001
Year: 2001

We have developed systems of two types for NTCIR2. One is an enhenced version of the system we developed for NTCIR1 and IREX. It submitted retrieval results for JJ and CC tasks. A variety of parameters were tried with the system. It used such characteristics of newspapers as locational information in the CC tasks. The system got good results for both of the tasks. The other system is a portable system which avoids free parameters as much as possible. The system submitted retrieval results for JJ, JE, EE, EJ, and CC tasks. The system automatically determined the number of top documents and the weight of the original query used in automatic-feedback retrieval. It also determined relevant terms quite robustly. For EJ and JE tasks, it used document expansion to augment the initial queries. It achieved good results, except on the CC tasks.
On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs
Venue: arXiv cs.GT 2001
Year: 2001

Consider a very simple class of (finite) games: after an initial move by nature, each player makes one move. Moreover, the players have common interests: at each node, all the players get the same payoff. We show that the problem of determining whether there exists a joint strategy where each player has an expected payoff of at least r is NP-complete as a function of the number of nodes in the extensive-form representation of the game.
Belief Revision: A Critique
Venue: arXiv cs.AI 2001
Year: 2001

We examine carefully the rationale underlying the approaches to belief change taken in the literature, and highlight what we view as methodological problems. We argue that to study belief change carefully, we must be quite explicit about the ``ontology'' or scenario underlying the belief change process. This is something that has been missing in previous work, with its focus on postulates. Our analysis shows that we must pay particular attention to two issues that have often been taken for granted: The first is how we model the agent's epistemic state. (Do we use a set of beliefs, or a richer structure, such as an ordering on worlds? And if we use a set of beliefs, in what language are these beliefs are expressed?) We show that even postulates that have been called ``beyond controversy'' are unreasonable when the agent's beliefs include beliefs about her own epistemic state as well as the external world. The second is the status of observations. (Are observations known to be true, or just believed? In the latter case, how firm is the belief?) Issues regarding the status of observations arise particularly when we consider iterated belief revision, and we must confront the possibility of revising by p and then by not-p.
Bootstrapping Syntax and Recursion using Alignment-Based Learning
Venue: arXiv cs.LG 2001
Year: 2001

This paper introduces a new type of unsupervised learning algorithm, based on the alignment of sentences and Harris's (1951) notion of interchangeability. The algorithm is applied to an untagged, unstructured corpus of natural language sentences, resulting in a labelled, bracketed version of the corpus. Firstly, the algorithm aligns all sentences in the corpus in pairs, resulting in a partition of the sentences consisting of parts of the sentences that are similar in both sentences and parts that are dissimilar. This information is used to find (possibly overlapping) constituents. Next, the algorithm selects (non-overlapping) constituents. Several instances of the algorithm are applied to the ATIS corpus (Marcus et al., 1993) and the OVIS (Openbaar Vervoer Informatie Systeem (OVIS) stands for Public Transport Information System.) corpus (Bonnema et al., 1997). Apart from the promising numerical results, the most striking result is that even the simplest algorithm based on alignment learns recursion.
Analysis of Polymorphically Typed Logic Programs Using ACI-Unification
Venue: arXiv cs.LO 2001
Year: 2001

Analysis of (partial) groundness is an important application of abstract interpretation. There are several proposals for improving the precision of such an analysis by exploiting type information, icluding our own work with Hill and King, where we had shown how the information present in the type declarations of a program can be used to characterise the degree of instantiation of a term in a precise and yet inherently finite way. This approach worked for polymorphically typed programs as in Goedel or HAL. Here, we recast this approach following works by Codish, Lagoon and Stuckey. To formalise which properties of terms we want to characterise, we use labelling functions, which are functions that extract subterms from a term along certain paths. An abstract term collects the results of all labelling functions of a term. For the analysis, programs are executed on abstract terms instead of the concrete ones, and usual unification is replaced by unification modulo an equality theory which includes the well-known ACI-theory. Thus we generalise the works by Codish, Lagoon and Stuckey w.r.t. the type systems considered and relate the works among each other.
Using Dependence Analysis to Support Software Architecture Understanding
Venue: arXiv cs.SE 2001
Year: 2001

Software architecture is receiving increasingly attention as a critical design level for software systems. As software architecture design resources (in the form of architectural descriptions) are going to be accumulated, the development of techniques and tools to support architectural understanding, testing, reengineering, maintaining, and reusing will become an important issue. In this paper we introduce a new dependence analysis technique, named architectural dependence analysis to support software architecture development. In contrast to traditional dependence analysis, architectural dependence analysis is designed to operate on an architectural description of a software system, rather than the source code of a conventional program. Architectural dependence analysis provides knowledge of dependences for the high-level architecture of a software system, rather than the low-level implementation details of a conventional program.
On Assessing the Complexity of Software Architectures
Venue: arXiv cs.SE 2001
Year: 2001

This paper proposes some new architectural metrics which are appropriate for evaluating the architectural attributes of a software system. The main feature of our approach is to assess the complexity of a software architecture by analyzing various types of architectural dependences in the architecture.
Multi-Channel Parallel Adaptation Theory for Rule Discovery
Venue: arXiv cs.AI 2001
Year: 2001

In this paper, we introduce a new machine learning theory based on multi-channel parallel adaptation for rule discovery. This theory is distinguished from the familiar parallel-distributed adaptation theory of neural networks in terms of channel-based convergence to the target rules. We show how to realize this theory in a learning system named CFRule. CFRule is a parallel weight-based model, but it departs from traditional neural computing in that its internal knowledge is comprehensible. Furthermore, when the model converges upon training, each channel converges to a target rule. The model adaptation rule is derived by multi-level parallel weight optimization based on gradient descent. Since, however, gradient descent only guarantees local optimization, a multi-channel regression-based optimization strategy is developed to effectively deal with this problem. Formally, we prove that the CFRule model can explicitly and precisely encode any given rule set. Also, we prove a property related to asynchronous parallel convergence, which is a critical element of the multi-channel parallel adaptation theory for rule learning. Thanks to the quantizability nature of the CFRule model, rules can be extracted completely and soundly via a threshold-based mechanism. Finally, the practical application of the theory is demonstrated in DNA promoter recognition and hepatitis prognosis prediction.
When being Weak is Brave: Privacy in Recommender Systems
Venue: arXiv cs.CR 2001
Year: 2001

We explore the conflict between personalization and privacy that arises from the existence of weak ties. A weak tie is an unexpected connection that provides serendipitous recommendations. However, information about weak ties could be used in conjunction with other sources of data to uncover identities and reveal other personal information. In this article, we use a graph-theoretic model to study the benefit and risk from weak ties.
A Constraint-Driven System for Contract Assembly
Venue: arXiv cs.AI 2001
Year: 2001

We present an approach for modelling the structure and coarse content of legal documents with a view to providing automated support for the drafting of contracts and contract database retrieval. The approach is designed to be applicable where contract drafting is based on model-form contracts or on existing examples of a similar type. The main features of the approach are: (1) the representation addresses the structure and the interrelationships between the constituent parts of contracts, but not the text of the document itself; (2) the representation of documents is separated from the mechanisms that manipulate it; and (3) the drafting process is subject to a collection of explicitly stated constraints that govern the structure of the documents. We describe the representation of document instances and of 'generic documents', which are data structures used to drive the creation of new document instances, and we show extracts from a sample session to illustrate the features of a prototype system implemented in MacProlog.
Computing Functional and Relational Box Consistency by Structured Propagation in Atomic Constraint Systems
Venue: arXiv cs.PL 2001
Year: 2001

Box consistency has been observed to yield exponentially better performance than chaotic constraint propagation in the interval constraint system obtained by decomposing the original expression into primitive constraints. The claim was made that the improvement is due to avoiding decomposition. In this paper we argue that the improvement is due to replacing chaotic iteration by a more structured alternative. To this end we distinguish the existing notion of box consistency from relational box consistency. We show that from a computational point of view it is important to maintain the functional structure in constraint systems that are associated with a system of equations. So far, it has only been considered computationally important that constraint propagation be fair. With the additional structure of functional constraint systems, one can define and implement computationally effective, structured, truncated constraint propagations. The existing algorithm for box consistency is one such. Our results suggest that there are others worth investigating.
Object-oriented tools for advanced applications
Venue: arXiv cs.LO 2001
Year: 2001

This paper contains a brief discussion of the Application Development Environment (ADE) that is used to build database applications involving the graphical user interface (GUI). ADE computing separates the database access and the user interface. The variety of applications may be generated that communicate with different and distinct desktop databases. The advanced techniques allows to involve remote or stored procedures retrieval and call.
Event Driven Computations for Relational Query Language
Venue: arXiv cs.LO 2001
Year: 2001

This paper deals with an extended model of computations which uses the parameterized families of entities for data objects and reflects a preliminary outline of this problem. Some topics are selected out, briefly analyzed and arranged to cover a general problem. The authors intended more to discuss the particular topics, their interconnection and computational meaning as a panel proposal, so that this paper is not yet to be evaluated as a closed journal paper. To save space all the technical and implementation features are left for the future paper. Data object is a schematic entity and modelled by the partial function. A notion of type is extended by the variable domains which depend on events and types. A variable domain is built from the potential and schematic individuals and generates the valid families of types depending on a sequence of events. Each valid type consists of the actual individuals which are actual relatively the event or script. In case when a type depends on the script then corresponding view for data objects is attached, otherwise a snapshot is generated. The type thus determined gives an upper range for typed variables so that the local ranges are event driven resulting is the families of actual individuals. An expressive power of the query language is extended using the extensional and intentional relations.
Iterative Residual Rescaling: An Analysis and Generalization of LSI
Venue: arXiv cs.CL 2001
Year: 2001

We consider the problem of creating document representations in which inter-document similarity measurements correspond to semantic similarity. We first present a novel subspace-based framework for formalizing this task. Using this framework, we derive a new analysis of Latent Semantic Indexing (LSI), showing a precise relationship between its performance and the uniformity of the underlying distribution of documents over topics. This analysis helps explain the improvements gained by Ando's (2000) Iterative Residual Rescaling (IRR) algorithm: IRR can compensate for distributional non-uniformity. A further benefit of our framework is that it provides a well-motivated, effective method for automatically determining the rescaling factor IRR depends on, leading to further improvements. A series of experiments over various settings and with several evaluation metrics validates our claims.
CHR as grammar formalism. A first report
Venue: arXiv cs.PL 2001
Year: 2001

Grammars written as Constraint Handling Rules (CHR) can be executed as efficient and robust bottom-up parsers that provide a straightforward, non-backtracking treatment of ambiguity. Abduction with integrity constraints as well as other dynamic hypothesis generation techniques fit naturally into such grammars and are exemplified for anaphora resolution, coordination and text interpretation.
Three-Stage Quantitative Neural Network Model of the Tip-of-the-Tongue Phenomenon
Venue: arXiv cs.CL 2001
Year: 2001

A new three-stage computer artificial neural network model of the tip-of-the-tongue phenomenon is shortly described, and its stochastic nature was demonstrated. A way to calculate strength and appearance probability of tip-of-the-tongue states, neural network mechanism of feeling-of-knowing phenomenon are proposed. The model synthesizes memory, psycholinguistic, and metamemory approaches, bridges speech errors and naming chronometry research traditions. A model analysis of a tip-of-the-tongue case from Anton Chekhov's short story 'A Horsey Name' is performed. A new 'throw-up-one's-arms effect' is defined.
Enumerating Foldings and Unfoldings between Polygons and Polytopes
Venue: arXiv cs.CG 2001
Year: 2001

We pose and answer several questions concerning the number of ways to fold a polygon to a polytope, and how many polytopes can be obtained from one polygon; and the analogous questions for unfolding polytopes to polygons. Our answers are, roughly: exponentially many, or nondenumerably infinite.
The Complexity of Clickomania
Venue: arXiv cs.CC 2001
Year: 2001

We study a popular puzzle game known variously as Clickomania and Same Game. Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes a chosen connected monochromatic group of at least two square blocks, and any blocks above it fall down. We show that one-column puzzles can be solved, i.e., the maximum possible number of blocks can be removed, in linear time for two colors, and in polynomial time for an arbitrary number of colors. On the other hand, deciding whether a puzzle is solvable (all blocks can be removed) is NP-complete for two columns and five colors, or five columns and three colors.
A Bit of Progress in Language Modeling
Venue: arXiv cs.CL 2001
Year: 2001

In the past several years, a number of different language modeling improvements over simple trigram models have been found, including caching, higher-order n-grams, skipping, interpolated Kneser-Ney smoothing, and clustering. We present explorations of variations on, or of the limits of, each of these techniques, including showing that sentence mixture models may have more potential. While all of these techniques have been studied separately, they have rarely been studied in combination. We find some significant interactions, especially with smoothing and clustering techniques. We compare a combination of all techniques together to a Katz smoothed trigram model with no count cutoffs. We achieve perplexity reductions between 38% and 50% (1 bit of entropy), depending on training data size, as well as a word error rate reduction of 8.9%. Our perplexity reductions are perhaps the highest reported compared to a fair baseline. This is the extended version of the paper; it contains additional details and proofs, and is designed to be a good introduction to the state of the art in language modeling.