OpenRaiser/Intern-Atlas huggingface dataset:
Types of Cost in Inductive Concept Learning
Venue: arXiv cs.LG 2002
Year: 2002

Inductive concept learning is the task of learning to assign cases to a discrete set of classes. In real-world applications of concept learning, there are many different types of cost involved. The majority of the machine learning literature ignores all types of cost (unless accuracy is interpreted as a type of cost measure). A few papers have investigated the cost of misclassification errors. Very few papers have examined the many other types of cost. In this paper, we attempt to create a taxonomy of the different types of cost that are involved in inductive concept learning. This taxonomy may help to organize the literature on cost-sensitive learning. We hope that it will inspire researchers to investigate all types of cost in inductive concept learning in more depth.
Exploiting Context When Learning to Classify
Venue: arXiv cs.LG 2002
Year: 2002

This paper addresses the problem of classifying observations when features are context-sensitive, specifically when the testing set involves a context that is different from the training set. The paper begins with a precise definition of the problem, then general strategies are presented for enhancing the performance of classification algorithms on this type of problem. These strategies are tested on two domains. The first domain is the diagnosis of gas turbine engines. The problem is to diagnose a faulty engine in one context, such as warm weather, when the fault has previously been seen only in another context, such as cold weather. The second domain is speech recognition. The problem is to recognize words spoken by a new speaker, not represented in the training set. For both domains, exploiting context results in substantially more accurate classification.
Low Size-Complexity Inductive Logic Programming: The East-West Challenge Considered as a Problem in Cost-Sensitive Classification
Venue: arXiv cs.LG 2002
Year: 2002

The Inductive Logic Programming community has considered proof-complexity and model-complexity, but, until recently, size-complexity has received little attention. Recently a challenge was issued "to the international computing community" to discover low size-complexity Prolog programs for classifying trains. The challenge was based on a problem first proposed by Ryszard Michalski, 20 years ago. We interpreted the challenge as a problem in cost-sensitive classification and we applied a recently developed cost-sensitive classifier to the competition. Our algorithm was relatively successful (we won a prize). This paper presents our algorithm and analyzes the results of the competition.
Local Community Identification through User Access Patterns
Venue: arXiv cs.IR 2002
Year: 2002

Community identification algorithms have been used to enhance the quality of the services perceived by its users. Although algorithms for community have a widespread use in the Web, their application to portals or specific subsets of the Web has not been much studied. In this paper, we propose a technique for local community identification that takes into account user access behavior derived from access logs of servers in the Web. The technique takes a departure from the existing community algorithms since it changes the focus of in terest, moving from authors to users. Our approach does not use relations imposed by authors (e.g. hyperlinks in the case of Web pages). It uses information derived from user accesses to a service in order to infer relationships. The communities identified are of great interest to content providers since they can be used to improve quality of their services. We also propose an evaluation methodology for analyzing the results obtained by the algorithm. We present two case studies based on actual data from two services: an online bookstore and an online radio. The case of the online radio is particularly relevant, because it emphasizes the contribution of the proposed algorithm to find out communities in an environment (i.e., streaming media service) without links, that represent the relations imposed by authors (e.g. hyperlinks in the case of Web pages).
Strategic polymorphism requires just two combinators!
Venue: arXiv cs.PL 2002
Year: 2002

In previous work, we introduced the notion of functional strategies: first-class generic functions that can traverse terms of any type while mixing uniform and type-specific behaviour. Functional strategies transpose the notion of term rewriting strategies (with coverage of traversal) to the functional programming paradigm. Meanwhile, a number of Haskell-based models and combinator suites were proposed to support generic programming with functional strategies. In the present paper, we provide a compact and matured reconstruction of functional strategies. We capture strategic polymorphism by just two primitive combinators. This is done without commitment to a specific functional language. We analyse the design space for implementational models of functional strategies. For completeness, we also provide an operational reference model for implementing functional strategies (in Haskell). We demonstrate the generality of our approach by reconstructing representative fragments of the Strafunski library for functional strategies.
An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database Theory
Venue: arXiv cs.LO 2002
Year: 2002

We present a new Ehrenfeucht-Fraisse game approach to collapse results in database theory and we show that, in principle, this approach suffices to prove every natural generic collapse result. Following this approach we can deal with certain infinite databases where previous, highly involved methods fail. We prove the natural generic collapse for Z-embeddable databases over any linearly ordered context structure with arbitrary monadic predicates, and for N-embeddable databases over the context structure (R,<,+,Mon_Q,Groups). Here, N, Z, R, denote the sets of natural numbers, integers, and real numbers, respectively. Groups is the collection of all subgroups of (R,+) that contain Z, and Mon_Q is the collection of all subsets of a particular infinite subset Q of N. Restricting the complexity of the formulas that may be used to formulate queries to Boolean combinations of purely existential first-order formulas, we even obtain the collapse for N-embeddable databases over any linearly ordered context structure with arbitrary predicates. Finally, we develop the notion of N-representable databases, which is a natural generalization of the classical notion of finitely representable databases. We show that natural generic collapse results for N-embeddable databases can be lifted to the larger class of N-representable databases. To obtain, in particular, the collapse result for (N,<,+,Mon_Q), we explicitly construct a winning strategy for the duplicator in the presence of the built-in addition relation +. This, as a side product, also leads to an Ehrenfeucht-Fraisse game proof of the theorem of Ginsburg and Spanier, stating that the spectra of FO(<,+)-sentences are semi-linear.
The Tale of One-way Functions
Venue: arXiv cs.CR 2003
Year: 2003

The existence of one-way functions is arguably the most important problem in computer theory. The article discusses and refines a number of concepts relevant to this problem. For instance, it gives the first combinatorial complete owf, i.e., a function which is one-way if any function is. There are surprisingly many subtleties in basic definitions. Some of these subtleties are discussed or hinted at in the literature and some are overlooked. Here, a unified approach is attempted.
Toward an architecture for quantum programming
Venue: arXiv cs.PL 2003
Year: 2003

It is becoming increasingly clear that, if a useful device for quantum computation will ever be built, it will be embodied by a classical computing machine with control over a truly quantum subsystem, this apparatus performing a mixture of classical and quantum computation. This paper investigates a possible approach to the problem of programming such machines: a template high level quantum language is presented which complements a generic general purpose classical language with a set of quantum primitives. The underlying scheme involves a run-time environment which calculates the byte-code for the quantum operations and pipes it to a quantum device controller or to a simulator. This language can compactly express existing quantum algorithms and reduce them to sequences of elementary operations; it also easily lends itself to automatic, hardware independent, circuit simplification. A publicly available preliminary implementation of the proposed ideas has been realized using the C++ language.
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
Venue: arXiv cs.DS 2003
Year: 2003

The multiway-cut problem is, given a weighted graph and k >= 2 terminal nodes, to find a minimum-weight set of edges whose removal separates all the terminals. The problem is NP-hard, and even NP-hard to approximate within 1+delta for some small delta > 0. Calinescu, Karloff, and Rabani (1998) gave an algorithm with performance guarantee 3/2-1/k, based on a geometric relaxation of the problem. In this paper, we give improved randomized rounding schemes for their relaxation, yielding a 12/11-approximation algorithm for k=3 and a 1.3438-approximation algorithm in general. Our approach hinges on the observation that the problem of designing a randomized rounding scheme for a geometric relaxation is itself a linear programming problem. The paper explores computational solutions to this problem, and gives a proof that for a general class of geometric relaxations, there are always randomized rounding schemes that match the integrality gap.
Physical Traces: Quantum vs. Classical Information Processing
Venue: arXiv cs.CG 2003
Year: 2003

Within the Geometry of Interaction (GoI) paradigm, we present a setting that enables qualitative differences between classical and quantum processes to be explored. The key construction is the physical interpretation/realization of the traced monoidal categories of finite-dimensional vector spaces with tensor product as monoidal structure and of finite sets and relations with Cartesian product as monoidal structure, both of them providing a so-called wave-style GoI. The developments in this paper reveal that envisioning state update due to quantum measurement as a process provides a powerful tool for developing high-level approaches to quantum information processing.
Effective Strong Dimension, Algorithmic Information, and Computational Complexity
Venue: arXiv cs.CC 2003
Year: 2003

The two most important notions of fractal dimension are {\it Hausdorff dimension}, developed by Hausdorff (1919), and {\it packing dimension}, developed by Tricot (1982). Lutz (2000) has recently proven a simple characterization of Hausdorff dimension in terms of {\it gales}, which are betting strategies that generalize martingales. Imposing various computability and complexity constraints on these gales produces a spectrum of effective versions of Hausdorff dimension. In this paper we show that packing dimension can also be characterized in terms of gales. Moreover, even though the usual definition of packing dimension is considerably more complex than that of Hausdorff dimension, our gale characterization of packing dimension is an exact dual of -- and every bit as simple as -- the gale characterization of Hausdorff dimension. Effectivizing our gale characterization of packing dimension produces a variety of {\it effective strong dimensions}, which are exact duals of the effective dimensions mentioned above. We develop the basic properties of effective strong dimensions and prove a number of results relating them to fundamental aspects of randomness, Kolmogorov complexity, prediction, Boolean circuit-size complexity, polynomial-time degrees, and data compression.
Open Problems from CCCG 2002
Venue: arXiv cs.CG 2003
Year: 2003

A list of the problems presented on August 12, 2002 at the open-problem session of the 14th Canadian Conference on Computational Geometry held in Lethbridge, Alberta, Canada.
Flavor: A Language for Media Representation
Venue: arXiv cs.PL 2003
Year: 2003

Flavor (Formal Language for Audio-Visual Object Representation) has been created as a language for describing coded multimedia bitstreams in a formal way so that the code for reading and writing bitstreams can be automatically generated. It is an extension of C++ and Java, in which the typing system incorporates bitstream representation semantics. This allows describing in a single place both the in-memory representation of data as well as their bitstream-level (compressed) representation. Flavor also comes with a translator that automatically generates standard C++ or Java code from the Flavor source code so that direct access to compressed multimedia information by application developers can be achieved with essentially zero programming. Flavor has gone through many enhancements and this paper fully describes the latest version of the language and the translator. The software has been made into an open source project as of Version 4.1, and the latest downloadable Flavor package is available at http://flavor.sourceforge.net.
Comparisons and Computation of Well-founded Semantics for Disjunctive Logic Programs
Venue: arXiv cs.AI 2003
Year: 2003

Much work has been done on extending the well-founded semantics to general disjunctive logic programs and various approaches have been proposed. However, these semantics are different from each other and no consensus is reached about which semantics is the most intended. In this paper we look at disjunctive well-founded reasoning from different angles. We show that there is an intuitive form of the well-founded reasoning in disjunctive logic programming which can be characterized by slightly modifying some exisitng approaches to defining disjunctive well-founded semantics, including program transformations, argumentation, unfounded sets (and resolution-like procedure). We also provide a bottom-up procedure for this semantics. The significance of our work is not only in clarifying the relationship among different approaches, but also shed some light on what is an intended well-founded semantics for disjunctive logic programs.
Differential Fault Analysis on A.E.S
Venue: arXiv cs.CR 2003
Year: 2003

We explain how a differential fault analysis (DFA) works on AES 128, 192 or 256 bits.
Computational Grids in Action: The Natinal Fusion Collaboratory
Venue: arXiv cs.DC 2003
Year: 2003

The National Fusion Collaboratory (NFC) project was created to advance scientific understanding and innovation in magnetic fusion research by enabling more efficient use of existing experimental facilities through more effective integration of experiment, theory, and modeling. To achieve this objective, NFC introduced the concept of "network services", which build on top of computational Grids, and provide Fusion codes, together with their maintenance and hardware resources as a service to the community. This mode of operation requires the development of new authorization and enforcement capabilities. In addition, the nature of Fusion experiments places strident quality of service requirements on codes run during the experimental cycle. In this paper, we describe Grid computing requirements of the Fusion community, and present our first experiments in meeting those requirements.
On the Complexity of Buffer Allocation in Message Passing Systems
Venue: arXiv cs.DC 2003
Year: 2003

Message passing programs commonly use buffers to avoid unnecessary synchronizations and to improve performance by overlapping communication with computation. Unfortunately, using buffers makes the program no longer portable, potentially unable to complete on systems without a sufficient number of buffers. Effective buffer use entails that the minimum number needed for a safe execution be allocated. We explore a variety of problems related to buffer allocation for safe and efficient execution of message passing programs. We show that determining the minimum number of buffers or verifying a buffer assignment are intractable problems. However, we give a polynomial time algorithm to determine the minimum number of buffers needed to allow for asynchronous execution. We extend these results to several different buffering schemes, which in some cases make the problems tractable.
Optimizing GoTools' Search Heuristics using Genetic Algorithms
Venue: arXiv cs.NE 2003
Year: 2003

GoTools is a program which solves life & death problems in the game of Go. This paper describes experiments using a Genetic Algorithm to optimize heuristic weights used by GoTools' tree-search. The complete set of heuristic weights is composed of different subgroups, each of which can be optimized with a suitable fitness function. As a useful side product, an MPI interface for FreePascal was implemented to allow the use of a parallelized fitness function running on a Beowulf cluster. The aim of this exercise is to optimize the current version of GoTools, and to make tools available in preparation of an extension of GoTools for solving open boundary life & death problems, which will introduce more heuristic parameters to be fine tuned.
Grid Market Directory: A Web Services based Grid Service Publication Directory
Venue: arXiv cs.DC 2003
Year: 2003

As Grids are emerging as the next generation service-oriented computing platforms, they need to support Grid economy that helps in the management of supply and demand for resources and offers an economic incentive for Grid resource providers. To enable this Grid economy, a market-like Grid environment including an infrastructure that supports the publication of services and their discovery is needed. As part of the Gridbus project, we proposed and have developed a Grid Market Directory (GMD) that serves as a registry for high-level service publication and discovery in Virtual Organisations.
Data-sharing relationships in the Web
Venue: arXiv cs.NI 2003
Year: 2003

We propose a novel structure, the data-sharing graph, for characterizing sharing patterns in large-scale data distribution systems. We analyze this structure in two such systems and uncover small-world patterns for data-sharing relationships. Using the data-sharing graph for system characterization has potential both for basic science, because we can identify new structures emerging in real, dynamic networks; and for system design, because we can exploit these structures when designing data location and delivery mechanisms. We conjecture that similar patterns arise in other large-scale systems and that these patterns can be exploited for mechanism design.
A Proposal to Separate Handles from Names on the Internet
Venue: arXiv cs.NI 2003
Year: 2003

Networked communications inherently depend on the ability of the sender of a message to indicate through some token how the message should be delivered to a particular recipient. The tokens that refer messages to recipients are variously known as routes, addresses,handles, and names} ordered by their relative nearness to network topology vs. human meaning. All four sorts of token refer in some way to a recipient, but they are controlled by different authorities and their meanings depend on different contextual parameters. Today's global Internet employs dynamically determined routes, IP addresses, and domain names. Domain names combine the functions of handles and names. The high value of domain names as names leads to substantial social and legal dispute about their assignment, degrading their value as handles. The time has come to provide a distinct open network handle system (ONHS), using handles that are not meaningful in natural language and are therefore not subject to the disputes surrounding the use of names. A handle service may be deployed easily as a handle domain within the current Domain Name System. In order to minimize the administrative load, and maximize their own autonomy, netizens may use public-key cryptography to assign their own handles.
Guided Google: A Meta Search Engine and its Implementation using the Google Distributed Web Services
Venue: arXiv cs.DC 2003
Year: 2003

With the advent of the Internet, search engines have begun sprouting like mushrooms after a rainfall. Only in recent years, have developers become more innovative, and came up with guided searching facilities online. The goals of these applications are to help ease and guide the searching efforts of a novice web user toward their desired objectives. A number of implementations of such services are emerging. This paper proposes a guided meta-search engine, called "Guided Google", as it serves as an interface to the actual Google.com search engine, using the Google Web Services.
Building an Open Language Archives Community on the OAI Foundation
Venue: arXiv cs.CL 2003
Year: 2003

The Open Language Archives Community (OLAC) is an international partnership of institutions and individuals who are creating a worldwide virtual library of language resources. The Dublin Core (DC) Element Set and the OAI Protocol have provided a solid foundation for the OLAC framework. However, we need more precision in community-specific aspects of resource description than is offered by DC. Furthermore, many of the institutions and individuals who might participate in OLAC do not have the technical resources to support the OAI protocol. This paper presents our solutions to these two problems. To address the first, we have developed an extensible application profile for language resource metadata. To address the second, we have implemented Vida (the virtual data provider) and Viser (the virtual service provider), which permit community members to provide data and services without having to implement the OAI protocol. These solutions are generic and could be adopted by other specialized subcommunities.
Relaxed Scheduling in Dynamic Skin Triangulation
Venue: arXiv cs.CG 2003
Year: 2003

We introduce relaxed scheduling as a paradigm for mesh maintenance and demonstrate its applicability to triangulating a skin surface in $\Rspace^3$.
Kalman-filtering using local interactions
Venue: arXiv cs.AI 2003
Year: 2003

There is a growing interest in using Kalman-filter models for brain modelling. In turn, it is of considerable importance to represent Kalman-filter in connectionist forms with local Hebbian learning rules. To our best knowledge, Kalman-filter has not been given such local representation. It seems that the main obstacle is the dynamic adaptation of the Kalman-gain. Here, a connectionist representation is presented, which is derived by means of the recursive prediction error method. We show that this method gives rise to attractive local learning rules and can adapt the Kalman-gain.
Extending the code generation capabilities of the Together CASE tool to support Data Definition languages
Venue: arXiv cs.SE 2003
Year: 2003

Together is the recommended software development tool in the Atlas collaboration. The programmatic API, which provides the capability to use and augment Together's internal functionality, is comprised of three major components - IDE, RWI and SCI. IDE is a read-only interface used to generate custom outputs based on the information contained in a Together model. RWI allows to both extract and write information to a Together model. SCI is the Source Code Interface, as the name implies it allows to work at the level of the source code. Together is extended by writing modules (java classes) extensively making use of the relevant API. We exploited Together extensibility to add support for the Atlas Dictionary Language. ADL is an extended subset of OMG IDL. The implemented module (ADLModule) makes Together to support ADL keywords, enables options and generate ADL object descriptions directly from UML Class diagrams. The module thoroughly accesses a Together reverse engineered C++ project - and/or design only class diagrams - and it is general enough to allow for possibly additional HEP-specific Together tool tailoring.