OpenRaiser/Intern-Atlas huggingface dataset:
On context-tree prediction of individual sequences
Venue: arXiv cs.IT 2005
Year: 2005

Motivated by the evident success of context-tree based methods in lossless data compression, we explore, in this paper, methods of the same spirit in universal prediction of individual sequences. By context-tree prediction, we refer to a family of prediction schemes, where at each time instant $t$, after having observed all outcomes of the data sequence $x_1,...,x_{t-1}$, but not yet $x_t$, the prediction is based on a ``context'' (or a state) that consists of the $k$ most recent past outcomes $x_{t-k},...,x_{t-1}$, where the choice of $k$ may depend on the contents of a possibly longer, though limited, portion of the observed past, $x_{t-k_{\max}},...x_{t-1}$. This is different from the study reported in [1], where general finite-state predictors as well as ``Markov'' (finite-memory) predictors of fixed order, were studied in the regime of individual sequences. Another important difference between this study and [1] is the asymptotic regime. While in [1], the resources of the predictor (i.e., the number of states or the memory size) were kept fixed regardless of the length $N$ of the data sequence, here we investigate situations where the number of contexts or states is allowed to grow concurrently with $N$. We are primarily interested in the following fundamental question: What is the critical growth rate of the number of contexts, below which the performance of the best context-tree predictor is still universally achievable, but above which it is not? We show that this critical growth rate is linear in $N$. In particular, we propose a universal context-tree algorithm that essentially achieves optimum performance as long as the growth rate is sublinear, and show that, on the other hand, this is impossible in the linear case.
Combining Structured Corporate Data and Document Content to Improve Expertise Finding
Venue: arXiv cs.IR 2005
Year: 2005

In this paper, we present an algorithm for automatically building expertise evidence for finding experts within an organization by combining structured corporate information with different content. We also describe our test data collection and our evaluation method. Evaluation of the algorithm shows that using organizational structure leads to a significant improvement in the precision of finding an expert. Furthermore we evaluate the impact of using different data sources on the quality of the results and conclude that Expert Finding is not a "one engine fits all" solution. It requires an analysis of the information space into which a solution will be placed and the appropriate selection and weighting scheme of the data sources.
Clustering Mixed Numeric and Categorical Data: A Cluster Ensemble Approach
Venue: arXiv cs.AI 2005
Year: 2005

Clustering is a widely used technique in data mining applications for discovering patterns in underlying data. Most traditional clustering algorithms are limited to handling datasets that contain either numeric or categorical attributes. However, datasets with mixed types of attributes are common in real life data mining applications. In this paper, we propose a novel divide-and-conquer technique to solve this problem. First, the original mixed dataset is divided into two sub-datasets: the pure categorical dataset and the pure numeric dataset. Next, existing well established clustering algorithms designed for different types of datasets are employed to produce corresponding clusters. Last, the clustering results on the categorical and numeric dataset are combined as a categorical dataset, on which the categorical data clustering algorithm is used to get the final clusters. Our contribution in this paper is to provide an algorithm framework for the mixed attributes clustering problem, in which existing clustering algorithms can be easily integrated, the capabilities of different kinds of clustering algorithms and characteristics of different types of datasets could be fully exploited. Comparisons with other clustering algorithms on real life datasets illustrate the superiority of our approach.
Traders imprint themselves by adaptively updating their own avatar
Venue: arXiv cs.MA 2005
Year: 2005

Simulations of artificial stock markets were considered as early as 1964 and multi-agent ones were introduced as early as 1989. Starting the early 90's, collaborations of economists and physicists produced increasingly realistic simulation platforms. Currently, the market stylized facts are easily reproduced and one has now to address the realistic details of the Market Microstructure and of the Traders Behaviour. This calls for new methods and tools capable of bridging smoothly between simulations and experiments in economics. We propose here the following Avatar-Based Method (ABM). The subjects implement and maintain their Avatars (programs encoding their personal decision making procedures) on NatLab, a market simulation platform. Once these procedures are fed in a computer edible format, they can be operationally used as such without the need for belabouring, interpreting or conceptualising them. Thus ABM short-circuits the usual behavioural economics experiments that search for the psychological mechanisms underlying the subjects behaviour. Finally, ABM maintains a level of objectivity close to the classical behaviourism while extending its scope to subjects' decision making mechanisms. We report on experiments where Avatars designed and maintained by humans from different backgrounds (including real traders) compete in a continuous double-auction market. We hope this unbiased way of capturing the adaptive evolution of real subjects behaviour may lead to a new kind of behavioural economics experiments with a high degree of reliability, analysability and reproducibility.
Transitive Text Mining for Information Extraction and Hypothesis Generation
Venue: arXiv cs.IR 2005
Year: 2005

Transitive text mining - also named Swanson Linking (SL) after its primary and principal researcher - tries to establish meaningful links between literature sets which are virtually disjoint in the sense that each does not mention the main concept of the other. If successful, SL may give rise to the development of new hypotheses. In this communication we describe our approach to transitive text mining which employs co-occurrence analysis of the medical subject headings (MeSH), the descriptors assigned to papers indexed in PubMed. In addition, we will outline the current state of our web-based information system which will enable our users to perform literature-driven hypothesis building on their own.
On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing
Venue: arXiv cs.DS 2005
Year: 2005

The Sum of Squares algorithm for bin packing was defined in [2] and studied in great detail in [1], where it was proved that its worst case performance ratio is at most 3. In this note, we improve the asymptotic worst case bound to 2.7777...
N-free extensions of posets.Note on a theorem of P.A.Grillet
Venue: arXiv cs.DM 2005
Year: 2005

Let $S\_{N}(P)$ be the poset obtained by adding a dummy vertex on each diagonal edge of the $N$'s of a finite poset $P$. We show that $S\_{N}(S\_{N}(P))$ is $N$-free. It follows that this poset is the smallest $N$-free barycentric subdivision of the diagram of $P$, poset whose existence was proved by P.A. Grillet. This is also the poset obtained by the algorithm starting with $P\_0:=P$ and consisting at step $m$ of adding a dummy vertex on a diagonal edge of some $N$ in $P\_m$, proving that the result of this algorithm does not depend upon the particular choice of the diagonal edge choosen at each step. These results are linked to drawing of posets.
Coding for the feedback Gel'fand-Pinsker channel and the feedforward Wyner-Ziv source
Venue: arXiv cs.IT 2005
Year: 2005

We consider both channel coding and source coding, with perfect past feedback/feedforward, in the presence of side information. It is first observed that feedback does not increase the capacity of the Gel'fand-Pinsker channel, nor does feedforward improve the achievable rate-distortion performance in the Wyner-Ziv problem. We then focus on the Gaussian case showing that, as in the absence of side information, feedback/feedforward allows to efficiently attain the respective performance limits. In particular, we derive schemes via variations on that of Schalkwijk and Kailath. These variants, which are as simple as their origins and require no binning, are shown to achieve, respectively, the capacity of Costa's channel, and the Wyner-Ziv rate distortion function. Finally, we consider the finite-alphabet setting and derive schemes for both the channel and the source coding problems that attain the fundamental limits, using variations on schemes of Ahlswede and Ooi and Wornell, and of Martinian and Wornell, respectively.
Authoring case based training by document data extraction
Venue: arXiv cs.AI 2005
Year: 2005

In this paper, we propose an scalable approach to modeling based upon word processing documents, and we describe the tool Phoenix providing the technical infrastructure. For our training environment d3web.Train, we developed a tool to extract case knowledge from existing documents, usually dismissal records, extending Phoenix to d3web.CaseImporter. Independent authors used this tool to develop training systems, observing a significant decrease of time for setteling-in and a decrease of time necessary for developing a case.
Language embeddings that preserve staging and safety
Venue: arXiv cs.PL 2005
Year: 2005

We study embeddings of programming languages into one another that preserve what reductions take place at compile-time, i.e., staging. A certain condition -- what we call a `Turing complete kernel' -- is sufficient for a language to be stage-universal in the sense that any language may be embedded in it while preserving staging. A similar line of reasoning yields the notion of safety-preserving embeddings, and a useful characterization of safety-universality. Languages universal with respect to staging and safety are good candidates for realizing domain-specific embedded languages (DSELs) and `active libraries' that provide domain-specific optimizations and safety checks.
Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy Channels
Venue: arXiv cs.IT 2005
Year: 2005

We introduce a new family of concatenated codes with an outer low-density parity-check (LDPC) code and an inner low-density generator matrix (LDGM) code, and prove that these codes can achieve capacity under any memoryless binary-input output-symmetric (MBIOS) channel using maximum-likelihood (ML) decoding with bounded graphical complexity, i.e., the number of edges per information bit in their graphical representation is bounded. In particular, we also show that these codes can achieve capacity on the binary erasure channel (BEC) under belief propagation (BP) decoding with bounded decoding complexity per information bit per iteration for all erasure probabilities in (0, 1). By deriving and analyzing the average weight distribution (AWD) and the corresponding asymptotic growth rate of these codes with a rate-1 inner LDGM code, we also show that these codes achieve the Gilbert-Varshamov bound with asymptotically high probability. This result can be attributed to the presence of the inner rate-1 LDGM code, which is demonstrated to help eliminate high weight codewords in the LDPC code while maintaining a vanishingly small amount of low weight codewords.
Order Independence and Rationalizability
Venue: arXiv cs.GT 2005
Year: 2005

Two natural strategy elimination procedures have been studied for strategic games. The first one involves the notion of (strict, weak, etc) dominance and the second the notion of rationalizability. In the case of dominance the criterion of order independence allowed us to clarify which notions and under what circumstances are robust. In the case of rationalizability this criterion has not been considered. In this paper we investigate the problem of order independence for rationalizability by focusing on three naturally entailed reduction relations on games. These reduction relations are distinguished by the adopted reference point for the notion of a better response. Additionally, they are parametrized by the adopted system of beliefs. We show that for one reduction relation the outcome of its (possibly transfinite) iterations does not depend on the order of elimination of the strategies. This result does not hold for the other two reduction relations. However, under a natural assumption the iterations of all three reduction relations yield the same outcome. The obtained order independence results apply to the frameworks considered in Bernheim 84 and Pearce 84. For finite games the iterations of all three reduction relations coincide and the order independence holds for three natural systems of beliefs considered in the literature.
On joint coding for watermarking and encryption
Venue: arXiv cs.IT 2005
Year: 2005

In continuation to earlier works where the problem of joint information embedding and lossless compression (of the composite signal) was studied in the absence \cite{MM03} and in the presence \cite{MM04} of attacks, here we consider the additional ingredient of protecting the secrecy of the watermark against an unauthorized party, which has no access to a secret key shared by the legitimate parties. In other words, we study the problem of joint coding for three objectives: information embedding, compression, and encryption.Our main result is a coding theorem that provides a single--letter characterization of the best achievable tradeoffs among the following parameters: the distortion between the composite signal and the covertext, the distortion in reconstructing the watermark by the legitimate receiver, the compressibility of the composite signal (with and without the key), and the equivocation of the watermark, as well as its reconstructed version, given the composite signal. In the attack--free case, if the key is independent of the covertext, this coding theorem gives rise to a {\it threefold} separation principle that tells that asymptotically, for long block codes, no optimality is lost by first applying a rate--distortion code to the watermark source, then encrypting the compressed codeword, and finally, embedding it into the covertext using the embedding scheme of \cite{MM03}. In the more general case, however, this separation principle is no longer valid, as the key plays an additional role of side information used by the embedding unit.
Distance-Increasing Maps of All Length by Simple Mapping Algorithms
Venue: arXiv cs.IT 2005
Year: 2005

Distance-increasing maps from binary vectors to permutations, namely DIMs, are useful for the construction of permutation arrays. While a simple mapping algorithm defining DIMs of even length is known, existing DIMs of odd length are either recursively constructed by merging shorter DIMs or defined by much complicated mapping algorithms. In this paper, DIMs of all length defined by simple mapping algorithms are presented.
Capacity Limits of Cognitive Radio with Distributed and Dynamic Spectral Activity
Venue: arXiv cs.IT 2005
Year: 2005

We investigate the capacity of opportunistic communication in the presence of dynamic and distributed spectral activity, i.e. when the time varying spectral holes sensed by the cognitive transmitter are correlated but not identical to those sensed by the cognitive receiver. Using the information theoretic framework of communication with causal and non-causal side information at the transmitter and/or the receiver, we obtain analytical capacity expressions and the corresponding numerical results. We find that cognitive radio communication is robust to dynamic spectral environments even when the communication occurs in bursts of only 3-5 symbols. The value of handshake overhead is investigated for both lightly loaded and heavily loaded systems. We find that the capacity benefits of overhead information flow from the transmitter to the receiver is negligible while feedback information overhead in the opposite direction significantly improves capacity.
On Time-Variant Distortions in Multicarrier Transmission with Application to Frequency Offsets and Phase Noise
Venue: arXiv cs.IT 2005
Year: 2005

Phase noise and frequency offsets are due to their time-variant behavior one of the most limiting disturbances in practical OFDM designs and therefore intensively studied by many authors. In this paper we present a generalized framework for the prediction of uncoded system performance in the presence of time-variant distortions including the transmitter and receiver pulse shapes as well as the channel. Therefore, unlike existing studies, our approach can be employed for more general multicarrier schemes. To show the usefulness of our approach, we apply the results to OFDM in the context of frequency offset and Wiener phase noise, yielding improved bounds on the uncoded performance. In particular, we obtain exact formulas for the averaged performance in AWGN and time-invariant multipath channels.
Semantics of UML 2.0 Activity Diagram for Business Modeling by Means of Virtual Machine
Venue: arXiv cs.CE 2005
Year: 2005

The paper proposes a more formalized definition of UML 2.0 Activity Diagram semantics. A subset of activity diagram constructs relevant for business process modeling is considered. The semantics definition is based on the original token flow methodology, but a more constructive approach is used. The Activity Diagram Virtual machine is defined by means of a metamodel, with operations defined by a mix of pseudocode and OCL pre- and postconditions. A formal procedure is described which builds the virtual machine for any activity diagram. The relatively complicated original token movement rules in control nodes and edges are combined into paths from an action to action. A new approach is the use of different (push and pull) engines, which move tokens along the paths. Pull engines are used for paths containing join nodes, where the movement of several tokens must be coordinated. The proposed virtual machine approach makes the activity semantics definition more transparent where the token movement can be easily traced. However, the main benefit of the approach is the possibility to use the defined virtual machine as a basis for UML activity diagram based workflow or simulation engine.
Generalized ABBA Space-Time Block Codes
Venue: arXiv cs.IT 2005
Year: 2005

Linear space-time block codes (STBCs) of unitary rate and full diversity, systematically constructed over arbitrary constellations for any number of transmit antennas are introduced. The codes are obtained by generalizing the existing ABBA STBCs, a.k.a quasi-orthogonal STBCs (QO-STBCs). Furthermore, a fully orthogonal (symbol-by-symbol) decoder for the new generalized ABBA (GABBA) codes is provided. This remarkably low-complexity decoder relies on partition orthogonality properties of the code structure to decompose the received signal vector into lower-dimension tuples, each dependent only on certain subsets of the transmitted symbols. Orthogonal decodability results from the nested application of this technique, with no matrix inversion or iterative signal processing required. The exact bit-error-rate probability of GABBA codes over generalized fading channels with maximum likelihood (ML) decoding is evaluated analytically and compared against simulation results obtained with the proposed orthogonal decoder. The comparison reveals that the proposed GABBA solution, despite its very low complexity, achieves nearly the same performance of the bound corresponding to the ML-decoded system, especially in systems with large numbers of antennas.
From finite-system entropy to entropy rate for a Hidden Markov Process
Venue: arXiv cs.IT 2005
Year: 2005

A recent result presented the expansion for the entropy rate of a Hidden Markov Process (HMP) as a power series in the noise variable $\eps$. The coefficients of the expansion around the noiseless ($\eps = 0$) limit were calculated up to 11th order, using a conjecture that relates the entropy rate of a HMP to the entropy of a process of finite length (which is calculated analytically). In this communication we generalize and prove the validity of the conjecture, and discuss the theoretical and practical consequences of our new theorem.
Candidate One-Way Functions and One-Way Permutations Based on Quasigroup String Transformations
Venue: arXiv cs.CR 2005
Year: 2005

In this paper we propose a definition and construction of a new family of one-way candidate functions ${\cal R}_N:Q^N \to Q^N$, where $Q=\{0,1,...,s-1\}$ is an alphabet with $s$ elements. Special instances of these functions can have the additional property to be permutations (i.e. one-way permutations). These one-way functions have the property that for achieving the security level of $2^n$ computations in order to invert them, only $n$ bits of input are needed. The construction is based on quasigroup string transformations. Since quasigroups in general do not have algebraic properties such as associativity, commutativity, neutral elements, inverting these functions seems to require exponentially many readings from the lookup table that defines them (a Latin Square) in order to check the satisfiability for the initial conditions, thus making them natural candidates for one-way functions.
Secure and {\sl Practical} Identity-Based Encryption
Venue: arXiv cs.CR 2005
Year: 2005

In this paper, we present a variant of Waters' Identity-Based Encryption scheme with a much smaller public-key size (only a few kilobytes). We show that this variant is semantically secure against passive adversaries in the standard model.\smallskip In essence, the new scheme divides Waters' public key size by a factor $\ell$ at the cost of (negligibly) reducing security by $\ell$ bits. Therefore, our construction settles an open question asked by Waters and constitutes the first fully secure {\sl practical} Identity-Based Encryption scheme
Remarks on "Toward Compact Interdomain Routing"
Venue: arXiv cs.NI 2005
Year: 2005

This paper critically examines some propositions and arguments of cs.NI/0508021 regarding applicability of hierarchical routing and perspectives of compact routing. Arguments against the former are found to be inaccurate while the latter is found to be equivalent to well-known deployed solutions. Also, multiple (stacked) application of compact-routing solutions is found to be equivalent to hierarchical routing.
Towards a diagrammatic modeling of the LinBox C++ linear algebra library
Venue: arXiv cs.SC 2005
Year: 2005

We propose a new diagrammatic modeling language, DML. The paradigm used is that of the category theory and in particular of the pushout tool. We show that most of the object-oriented structures can be described with this tool and have many examples in C++, ranging from virtual inheritance and polymorphism to template genericity. With this powerful tool, we propose a quite simple description of the C++ LinBox library. This library has been designed for efficiency and genericity and therefore makes heavy usage of complex template and polymorphic mecanism. Be reverse engineering, we are able to describe in a simple manner the complex structure of archetypes in LinBox.