OpenRaiser/Intern-Atlas huggingface dataset:
Self-Optimizing and Pareto-Optimal Policies in General Environments based on Bayes-Mixtures
Venue: arXiv cs.AI 2002
Year: 2002

The problem of making sequential decisions in unknown probabilistic environments is studied. In cycle $t$ action $y_t$ results in perception $x_t$ and reward $r_t$, where all quantities in general may depend on the complete history. The perception $x_t$ and reward $r_t$ are sampled from the (reactive) environmental probability distribution $μ$. This very general setting includes, but is not limited to, (partial observable, k-th order) Markov decision processes. Sequential decision theory tells us how to act in order to maximize the total expected reward, called value, if $μ$ is known. Reinforcement learning is usually used if $μ$ is unknown. In the Bayesian approach one defines a mixture distribution $ξ$ as a weighted sum of distributions $ν\in\M$, where $\M$ is any class of distributions including the true environment $μ$. We show that the Bayes-optimal policy $p^ξ$ based on the mixture $ξ$ is self-optimizing in the sense that the average value converges asymptotically for all $μ\in\M$ to the optimal value achieved by the (infeasible) Bayes-optimal policy $p^μ$ which knows $μ$ in advance. We show that the necessary condition that $\M$ admits self-optimizing policies at all, is also sufficient. No other structural assumptions are made on $\M$. As an example application, we discuss ergodic Markov decision processes, which allow for self-optimizing policies. Furthermore, we show that $p^ξ$ is Pareto-optimal in the sense that there is no other policy yielding higher or equal value in {\em all} environments $ν\in\M$ and a strictly higher value in at least one.
Computing Homotopic Shortest Paths Efficiently
Venue: arXiv cs.CG 2002
Year: 2002

This paper addresses the problem of finding shortest paths homotopic to a given disjoint set of paths that wind amongst point obstacles in the plane. We present a faster algorithm than previously known.
Required sample size for learning sparse Bayesian networks with many variables
Venue: arXiv cs.LG 2002
Year: 2002

Learning joint probability distributions on n random variables requires exponential sample size in the generic case. Here we consider the case that a temporal (or causal) order of the variables is known and that the (unknown) graph of causal dependencies has bounded in-degree Delta. Then the joint measure is uniquely determined by the probabilities of all (2 Delta+1)-tuples. Upper bounds on the sample size required for estimating their probabilities can be given in terms of the VC-dimension of the set of corresponding cylinder sets. The sample size grows less than linearly with n.
Instabilities of Robot Motion
Venue: arXiv cs.RO 2002
Year: 2002

Instabilities of robot motion are caused by topological reasons. In this paper we find a relation between the topological properties of a configuration space (the structure of its cohomology algebra) and the character of instabilities, which are unavoidable in any motion planning algorithm. More specifically, let $X$ denote the space of all admissible configurations of a mechanical system. A {\it motion planner} is given by a splitting $X\times X = F_1\cup F_2\cup ... \cup F_k$ (where $F_1, ..., F_k$ are pairwise disjoint ENRs, see below) and by continuous maps $s_j: F_j \to PX,$ such that $E\circ s_j =1_{F_j}$. Here $PX$ denotes the space of all continuous paths in $X$ (admissible motions of the system) and $E: PX\to X\times X$ denotes the map which assigns to a path the pair of its initial -- end points. Any motion planner determines an algorithm of motion planning for the system. In this paper we apply methods of algebraic topology to study the minimal number of sets $F_j$ in any motion planner in $X$. We also introduce a new notion of {\it order of instability} of a motion planner; it describes the number of essentially distinct motions which may occur as a result of small perturbations of the input data. We find the minimal order of instability, which may have motion planners on a given configuration space $X$. We study a number of specific problems: motion of a rigid body in $\R^3$, a robot arm, motion in $\R^3$ in the presence of obstacles, and others.
Low-Degree Spanning Trees of Small Weight
Venue: arXiv cs.DS 2002
Year: 2002

The degree-d spanning tree problem asks for a minimum-weight spanning tree in which the degree of each vertex is at most d. When d=2 the problem is TSP, and in this case, the well-known Christofides algorithm provides a 1.5-approximation algorithm (assuming the edge weights satisfy the triangle inequality). In 1984, Christos Papadimitriou and Umesh Vazirani posed the challenge of finding an algorithm with performance guarantee less than 2 for Euclidean graphs (points in R^n) and d > 2. This paper gives the first answer to that challenge, presenting an algorithm to compute a degree-3 spanning tree of cost at most 5/3 times the MST. For points in the plane, the ratio improves to 3/2 and the algorithm can also find a degree-4 spanning tree of cost at most 5/4 times the MST.
Balancing Minimum Spanning and Shortest Path Trees
Venue: arXiv cs.DS 2002
Year: 2002

This paper give a simple linear-time algorithm that, given a weighted digraph, finds a spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree. The algorithm provides a continuous trade-off: given the two trees and epsilon > 0, the algorithm returns a spanning tree in which the distance between any vertex and the root of the shortest-path tree is at most 1+epsilon times the shortest-path distance, and yet the total weight of the tree is at most 1+2/epsilon times the weight of a minimum spanning tree. This is the best tradeoff possible. The paper also describes a fast parallel implementation.
Three-Tiered Specification of Micro-Architectures
Venue: arXiv cs.SE 2002
Year: 2002

A three-tiered specification approach is developed to formally specify collections of collaborating objects, say micro-architectures. (i) The structural properties to be maintained in the collaboration are specified in the lowest tier. (ii) The behaviour of the object methods in the classes is specified in the middle tier. (iii) The interaction of the objects in the micro-architecture is specified in the third tier. The specification approach is based on Larch and accompanying notations and tools. The approach enables the unambiguous and complete specification of reusable collections of collaborating objects. The layered, formal approach is compared to other approaches including the mainstream UML approach.
Content Distribution in Unicast Replica Meshes
Venue: arXiv cs.NI 2002
Year: 2002

We propose centralized algorithm of data distribution in the unicast p2p network. Good example of such networks are meshes of WWW and FTP mirrors. Simulation of data propogation for different network topologies is performed and it is shown that proposed method performs up to 200% better then common apporaches
Using the Annotated Bibliography as a Resource for Indicative Summarization
Venue: arXiv cs.CL 2002
Year: 2002

We report on a language resource consisting of 2000 annotated bibliography entries, which is being analyzed as part of our research on indicative document summarization. We show how annotated bibliographies cover certain aspects of summarization that have not been well-covered by other summary corpora, and motivate why they constitute an important form to study for information retrieval. We detail our methodology for collecting the corpus, and overview our document feature markup that we introduced to facilitate summary analysis. We present the characteristics of the corpus, methods of collection, and show its use in finding the distribution of types of information included in indicative summaries and their relative ordering within the summaries.
Implementation and complexity of the watershed-from-markers algorithm computed as a minimal cost forest
Venue: arXiv cs.DS 2002
Year: 2002

The watershed algorithm belongs to classical algorithms in mathematical morphology. Lotufo et al. published a principle of the watershed computation by means of an Image Foresting Transform (IFT), which computes a shortest path forest from given markers. The algorithm itself was described for a 2D case (image) without a detailed discussion of its computation and memory demands for real datasets. As IFT cleverly solves the problem of plateaus and as it gives precise results when thin objects have to be segmented, it is obvious to use this algorithm for 3D datasets taking in mind the minimizing of a higher memory consumption for the 3D case without loosing low asymptotical time complexity of O(m+C) (and also the real computation speed). The main goal of this paper is an implementation of the IFT algorithm with a priority queue with buckets and careful tuning of this implementation to reach as minimal memory consumption as possible. The paper presents five possible modifications and methods of implementation of the IFT algorithm. All presented implementations keep the time complexity of the standard priority queue with buckets but the best one minimizes the costly memory allocation and needs only 19-45% of memory for typical 3D medical imaging datasets. Memory saving was reached by an IFT algorithm simplification, which stores more elements in temporary structures but these elements are simpler and thus need less memory. The best presented modification allows segmentation of large 3D medical datasets (up to 512x512x680 voxels) with 12-or 16-bits per voxel on currently available PC based workstations.
The analysis of the IFPUG method sensitivity
Venue: arXiv cs.SE 2002
Year: 2002

J. Albrecht`s Function Point Analysis (FPA) is a method to determine the functional size of software products. An organization called International Function Point Users Group (IPFUG), considers the FPA as a standard in the software functional size measurement. The Albrechts method is followed by IPFUG method which includes some modifications in order to improve it. A limitation of the method refers to the fact that FPA is not sensitive enough to differentiate the functional size in small enhancements. That affects the productivity analysis, where the software product functional size is required. To provide more power to the functional size measurement, A. Abran, M. Maya and H. Nguyeckim have proposed some modifications to improve it. The IPFUG v 4.1 method which includes these modifications is named IFPUG v 4.1 extended. In this work we set the conditions to delimiting granular from non granular functions and we calculate the static calibration and sensitivity graphs for the measurements of a set of projects with a high percentage of granular functions, all of then measured with the IFPUG v 4.1 method and the IFPUG v 4.1 extended. Finally, we introduce a statistic analysis in order to determine whether significant differences exist between both methods or not.
Relational Association Rules: getting WARMeR
Venue: arXiv cs.DB 2002
Year: 2002

In recent years, the problem of association rule mining in transactional data has been well studied. We propose to extend the discovery of classical association rules to the discovery of association rules of conjunctive queries in arbitrary relational data, inspired by the WARMR algorithm, developed by Dehaspe and Toivonen, that discovers association rules over a limited set of conjunctive queries. Conjunctive query evaluation in relational databases is well understood, but still poses some great challenges when approached from a discovery viewpoint in which patterns are generated and evaluated with respect to some well defined search space and pruning operators.
Speech-Driven Text Retrieval: Using Target IR Collections for Statistical Language Model Adaptation in Speech Recognition
Venue: arXiv cs.CL 2002
Year: 2002

Speech recognition has of late become a practical technology for real world applications. Aiming at speech-driven text retrieval, which facilitates retrieving information with spoken queries, we propose a method to integrate speech recognition and retrieval methods. Since users speak contents related to a target collection, we adapt statistical language models used for speech recognition based on the target collection, so as to improve both the recognition and retrieval accuracy. Experiments using existing test collections combined with dictated queries showed the effectiveness of our method.
Using eigenvectors of the bigram graph to infer morpheme identity
Venue: arXiv cs.CL 2002
Year: 2002

This paper describes the results of some experiments exploring statistical methods to infer syntactic behavior of words and morphemes from a raw corpus in an unsupervised fashion. It shares certain points in common with Brown et al (1992) and work that has grown out of that: it employs statistical techniques to analyze syntactic behavior based on what words occur adjacent to a given word. However, we use an eigenvector decomposition of a nearest-neighbor graph to produce a two-dimensional rendering of the words of a corpus in which words of the same syntactic category tend to form neighborhoods. We exploit this technique for extending the value of automatic learning of morphology. In particular, we look at the suffixes derived from a corpus by unsupervised learning of morphology, and we ask which of these suffixes have a consistent syntactic function (e.g., in English, -tion is primarily a mark of nouns, but -s marks both noun plurals and 3rd person present on verbs), and we determine that this method works well for this task.
Evolutionary Circuit Design: Information Theory Perspective on Signal Propagation
Venue: arXiv cs.OH 2002
Year: 2002

This paper presents case-study results on the application of information theoretic approach to gate-level evolutionary circuit design. We introduce information measures to provide better estimates of synthesis criteria of digital circuits. For example, the analysis of signal propagation during evolving gate-level synthesis can be improved by using information theoretic measures that will make it possible to find the most effective geometry and therefore predict the cost of the final design solution. The problem is considered from the information engine point of view. That is, the process of evolutionary gate-level circuit design is presented via such measures as entropy, logical work and information vitality. Some examples of geometry driven synthesis are provided to prove the above idea.
On the Information Engine of Circuit Design
Venue: arXiv cs.AR 2002
Year: 2002

This paper addresses a new approach to find a spectrum of information measures for the process of digital circuit synthesis. We consider the problem from the information engine point of view. The circuit synthesis as a whole and different steps of the design process (an example of decision diagram is given) are presented via such measurements as entropy, logical work and information vitality. We also introduce new information measures to provide better estimates of synthesis criteria. We show that the basic properties of information engine, such as the conservation law of information flow and the equilibrium law of information can be formulated.
Linear-Time Algorithms for Computing Maximum-Density Sequence Segments with Bioinformatics Applications
Venue: arXiv cs.DS 2002
Year: 2002

We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A of pairs (a_i,w_i) for i = 1,..,n and w_i>0, a segment A(i,j) is a consecutive subsequence of A starting with index i and ending with index j. The width of A(i,j) is w(i,j) = sum_{i <= k <= j} w_k, and the density is (sum_{i<= k <= j} a_k)/ w(i,j). The maximum-density segment problem takes A and two values L and U as input and asks for a segment of A with the largest possible density among those of width at least L and at most U. When U is unbounded, we provide a relatively simple, O(n)-time algorithm, improving upon the O(n \log L)-time algorithm by Lin, Jiang and Chao. When both L and U are specified, there are no previous nontrivial results. We solve the problem in O(n) time if w_i=1 for all i, and more generally in O(n+n\log(U-L+1)) time when w_i>=1 for all i.
Alternative Characterizations for Strong Equivalence of Logic Programs
Venue: arXiv cs.AI 2002
Year: 2002

In this work we present additional results related to the property of strong equivalence of logic programs. This property asserts that two programs share the same set of stable models, even under the addition of new rules. As shown in a recent work by Lifschitz, Pearce and Valverde, strong equivalence can be simply reduced to equivalence in the logic of Here-and-There (HT). In this paper we provide two alternatives respectively based on classical logic and 3-valued logic. The former is applicable to general rules, but not for nested expressions, whereas the latter is applicable for nested expressions but, when moving to an unrestricted syntax, it generally yields different results from HT.
Well-Founded Argumentation Semantics for Extended Logic Programming
Venue: arXiv cs.LO 2002
Year: 2002

This paper defines an argumentation semantics for extended logic programming and shows its equivalence to the well-founded semantics with explicit negation. We set up a general framework in which we extensively compare this semantics to other argumentation semantics, including those of Dung, and Prakken and Sartor. We present a general dialectical proof theory for these argumentation semantics.
Compilation of Propositional Weighted Bases
Venue: arXiv cs.AI 2002
Year: 2002

In this paper, we investigate the extent to which knowledge compilation can be used to improve inference from propositional weighted bases. We present a general notion of compilation of a weighted base that is parametrized by any equivalence--preserving compilation function. Both negative and positive results are presented. On the one hand, complexity results are identified, showing that the inference problem from a compiled weighted base is as difficult as in the general case, when the prime implicates, Horn cover or renamable Horn cover classes are targeted. On the other hand, we show that the inference problem becomes tractable whenever DNNF-compilations are used and clausal queries are considered. Moreover, we show that the set of all preferred models of a DNNF-compilation of a weighted base can be computed in time polynomial in the output size. Finally, we sketch how our results can be used in model-based diagnosis in order to compute the most probable diagnoses of a system.
Exporting Prolog source code
Venue: arXiv cs.SE 2002
Year: 2002

In this paper we present a simple source code configuration tool. ExLibris operates on libraries and can be used to extract from local libraries all code relevant to a particular project. Our approach is not designed to address problems arising in code production lines, but rather, to support the needs of individual or small teams of researchers who wish to communicate their Prolog programs. In the process, we also wish to accommodate and encourage the writing of reusable code. Moreover, we support and propose ways of dealing with issues arising in the development of code that can be run on a variety of like-minded Prolog systems. With consideration to these aims we have made the following decisions: (i) support file-based source development, (ii) require minimal program transformation, (iii) target simplicity of usage, and (iv) introduce minimum number of new primitives.
Polynomial Time Data Reduction for Dominating Set
Venue: arXiv cs.DS 2002
Year: 2002

Dealing with the NP-complete Dominating Set problem on undirected graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that Dominating Set restricted to planar graphs has a so-called problem kernel of linear size, achieved by two simple and easy to implement reduction rules. Moreover, having implemented our reduction rules, first experiments indicate the impressive practical potential of these rules. Thus, this work seems to open up a new and prospective way how to cope with one of the most important problems in graph theory and combinatorial optimization.
Libra: An Economy driven Job Scheduling System for Clusters
Venue: arXiv cs.DC 2002
Year: 2002

Clusters of computers have emerged as mainstream parallel and distributed platforms for high-performance, high-throughput and high-availability computing. To enable effective resource management on clusters, numerous cluster managements systems and schedulers have been designed. However, their focus has essentially been on maximizing CPU performance, but not on improving the value of utility delivered to the user and quality of services. This paper presents a new computational economy driven scheduling system called Libra, which has been designed to support allocation of resources based on the users? quality of service (QoS) requirements. It is intended to work as an add-on to the existing queuing and resource management system. The first version has been implemented as a plugin scheduler to the PBS (Portable Batch System) system. The scheduler offers market-based economy driven service for managing batch jobs on clusters by scheduling CPU time according to user utility as determined by their budget and deadline rather than system performance considerations. The Libra scheduler ensures that both these constraints are met within an O(n) run-time. The Libra scheduler has been simulated using the GridSim toolkit to carry out a detailed performance analysis. Results show that the deadline and budget based proportional resource allocation strategy improves the utility of the system and user satisfaction as compared to system-centric scheduling strategies.
Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
Venue: arXiv cs.DS 2002
Year: 2002

We improve on random sampling techniques for approximately solving problems that involve cuts and flows in graphs. We give a near-linear-time construction that transforms any graph on n vertices into an O(n\log n)-edge graph on the same vertices whose cuts have approximately the same value as the original graph's. In this new graph, for example, we can run the O(m^{3/2})-time maximum flow algorithm of Goldberg and Rao to find an s--t minimum cut in O(n^{3/2}) time. This corresponds to a (1+epsilon)-times minimum s--t cut in the original graph. In a similar way, we can approximate a sparsest cut to within O(log n) in O(n^2) time using a previous O(mn)-time algorithm. A related approach leads to a randomized divide and conquer algorithm producing an approximately maximum flow in O(m sqrt{n}) time.
On non-abelian homomorphic public-key cryptosystems
Venue: arXiv cs.CR 2002
Year: 2002

An important problem of modern cryptography concerns secret public-key computations in algebraic structures. We construct homomorphic cryptosystems being (secret) epimorphisms f:G --> H, where G, H are (publically known) groups and H is finite. A letter of a message to be encrypted is an element h element of H, while its encryption g element of G is such that f(g)=h. A homomorphic cryptosystem allows one to perform computations (operating in a group G) with encrypted information (without knowing the original message over H). In this paper certain homomorphic cryptosystems are constructed for the first time for non-abelian groups H (earlier, homomorphic cryptosystems were known only in the Abelian case). In fact, we present such a system for any solvable (fixed) group H.
A Model-Theoretic Semantics for Defeasible Logic
Venue: arXiv cs.LO 2002
Year: 2002

Defeasible logic is an efficient logic for defeasible reasoning. It is defined through a proof theory and, until now, has had no model theory. In this paper a model-theoretic semantics is given for defeasible logic. The logic is sound and complete with respect to the semantics. We also briefly outline how this approach extends to a wide range of defeasible logics.