OpenRaiser/Intern-Atlas huggingface dataset:
A Simple Linear Ranking Algorithm Using Query Dependent Intercept Variables
Venue: arXiv cs.IR 2008
Year: 2008

The LETOR website contains three information retrieval datasets used as a benchmark for testing machine learning ideas for ranking. Algorithms participating in the challenge are required to assign score values to search results for a collection of queries, and are measured using standard IR ranking measures (NDCG, precision, MAP) that depend only the relative score-induced order of the results. Similarly to many of the ideas proposed in the participating algorithms, we train a linear classifier. In contrast with other participating algorithms, we define an additional free variable (intercept, or benchmark) for each query. This allows expressing the fact that results for different queries are incomparable for the purpose of determining relevance. The cost of this idea is the addition of relatively few nuisance parameters. Our approach is simple, and we used a standard logistic regression library to test it. The results beat the reported participating algorithms. Hence, it seems promising to combine our approach with other more complex ideas.
On Power Control and Frequency Reuse in the Two User Cognitive Channel
Venue: arXiv cs.IT 2008
Year: 2008

This paper considers the generalized cognitive radio channel where the secondary user is allowed to reuse the frequency during both the idle and active periods of the primary user, as long as the primary rate remains the same. In this setting, the optimal power allocation policy with single-input single-output (SISO) primary and secondary channels is explored. Interestingly, the offered gain resulting from the frequency reuse during the active periods of the spectrum is shown to disappear in both the low and high signal-to-noise ratio (SNR) regimes. We then argue that this drawback in the high SNR region can be avoided by equipping both the primary and secondary transmitters with multiple antennas. Finally, the scenario consisting of SISO primary and multi-input multi-output (MIMO) secondary channels is investigated. Here, a simple Zero-Forcing approach is shown to significantly outperform the celebrated Decoding-Forwarding-Dirty Paper Coding strategy (especially in the high SNR regime).
Detect overlapping and hierarchical community structure in networks
Venue: arXiv cs.CY 2008
Year: 2008

Clustering and community structure is crucial for many network systems and the related dynamic processes. It has been shown that communities are usually overlapping and hierarchical. However, previous methods investigate these two properties of community structure separately. This paper proposes an algorithm (EAGLE) to detect both the overlapping and hierarchical properties of complex community structure together. This algorithm deals with the set of maximal cliques and adopts an agglomerative framework. The quality function of modularity is extended to evaluate the goodness of a cover. The examples of application to real world networks give excellent results.
A Distributed Platform for Mechanism Design
Venue: arXiv cs.GT 2008
Year: 2008

We describe a structured system for distributed mechanism design. It consists of a sequence of layers. The lower layers deal with the operations relevant for distributed computing only, while the upper layers are concerned only with communication among players, including broadcasting and multicasting, and distributed decision making. This yields a highly flexible distributed system whose specific applications are realized as instances of its top layer. This design supports fault-tolerance, prevents manipulations and makes it possible to implement distributed policing. The system is implemented in Java. We illustrate it by discussing a number of implemented examples.
The Fundamental Problem with the Building Block Hypothesis
Venue: arXiv cs.NE 2008
Year: 2008

Skepticism of the building block hypothesis (BBH) has previously been expressed on account of the weak theoretical foundations of this hypothesis and the anomalies in the empirical record of the simple genetic algorithm. In this paper we hone in on a more fundamental cause for skepticism--the extraordinary strength of some of the assumptions that undergird the BBH. Specifically, we focus on assumptions made about the distribution of fitness over the genome set, and argue that these assumptions are unacceptably strong. As most of these assumptions have been embraced by the designers of so-called "competent" genetic algorithms, our critique is relevant to an appraisal of such algorithms as well.
Detecting the Most Unusual Part of a Digital Image
Venue: arXiv cs.CV 2008
Year: 2008

The purpose of this paper is to introduce an algorithm that can detect the most unusual part of a digital image. The most unusual part of a given shape is defined as a part of the image that has the maximal distance to all non intersecting shapes with the same form. The method can be used to scan image databases with no clear model of the interesting part or large image databases, as for example medical databases.
A Call-Graph Profiler for GNU Octave
Venue: arXiv cs.PF 2008
Year: 2008

We report the design and implementation of a call-graph profiler for GNU Octave, a numerical computing platform. GNU Octave simplifies matrix computation for use in modeling or simulation. Our work provides a call-graph profiler, which is an improvement on the flat profiler. We elaborate design constraints of building a profiler for numerical computation, and benchmark the profiler by comparing it to the rudimentary timer start-stop (tic-toc) measurements, for a similar set of programs. The profiler code provides clean interfaces to internals of GNU Octave, for other (newer) profiling tools on GNU Octave.
A Study of NK Landscapes' Basins and Local Optima Networks
Venue: arXiv cs.NE 2008
Year: 2008

We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces (Doye, 2002). We use the well-known family of $NK$ landscapes as an example. In our case the inherent network is the graph where the vertices are all the local maxima and edges mean basin adjacency between two maxima. We exhaustively extract such networks on representative small NK landscape instances, and show that they are 'small-worlds'. However, the maxima graphs are not random, since their clustering coefficients are much larger than those of corresponding random graphs. Furthermore, the degree distributions are close to exponential instead of Poissonian. We also describe the nature of the basins of attraction and their relationship with the local maxima network.
The Poisson Channel at Low Input Powers
Venue: arXiv cs.IT 2008
Year: 2008

The asymptotic capacity at low input powers of an average-power limited or an average- and peak-power limited discrete-time Poisson channel is considered. For a Poisson channel whose dark current is zero or decays to zero linearly with its average input power $E$, capacity scales like $E\log\frac{1}{E}$ for small $E$. For a Poisson channel whose dark current is a nonzero constant, capacity scales, to within a constant, like $E\log\log\frac{1}{E}$ for small $E$.
Experimental Study of Application Specific Source Coding for Wireless Sensor Networks
Venue: arXiv cs.NI 2008
Year: 2008

The energy bottleneck in Wireless Sensor Network(WSN) can be reduced by limiting communication overhead. Application specific source coding schemes for the sensor networks provide fewer bits to represent the same amount of information exploiting the redundancy present in the source model, network architecture and the physical process. This paper reports the performance of representative codes from various families of source coding schemes (lossless, lossy, constant bit-rate, variable bit-rate, distributed and joint encoding/decoding) in terms of energy consumed, bit-rate achieved, quantization-error/reconstruction-error, latency and complexity of encoder-decoder(codec). A reusable frame work for testing source codes is provided. Finally we propose a set of possible applications and suitable source codes in terms of these parameters.
A new distance for high level RNA secondary structure comparison
Venue: arXiv cs.DS 2008
Year: 2008

We describe an algorithm for comparing two RNA secondary structures coded in the form of trees that introduces two new operations, called node fusion and edge fusion, besides the tree edit operations of deletion, insertion, and relabeling classically used in the literature. This allows us to address some serious limitations of the more traditional tree edit operations when the trees represent RNAs and what is searched for is a common structural core of two RNAs. Although the algorithm complexity has an exponential term, this term depends only on the number of successive fusions that may be applied to a same node, not on the total number of fusions. The algorithm remains therefore efficient in practice and is used for illustrative purposes on ribosomal as well as on other types of RNAs.
Network Coding-based Protection Strategies Against a Single Link Failure in Optical Networks
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we develop network protection strategies against a single link failure in optical networks. The motivation behind this work is the fact that $%70$ of all available links in an optical network suffers from a single link failure. In the proposed protection strategies, denoted NPS-I and NPS-II, we deploy network coding and reduced capacity on the working paths to provide a backup protection path that will carry encoded data from all sources. In addition, we provide implementation aspects and how to deploy the proposed strategies in case of an optical network with $n$ disjoint working paths.
Interval Semantics for Standard Floating-Point Arithmetic
Venue: arXiv cs.NA 2008
Year: 2008

If the non-zero finite floating-point numbers are interpreted as point intervals, then the effect of rounding can be interpreted as computing one of the bounds of the result according to interval arithmetic. We give an interval interpretation for the signed zeros and infinities, so that the undefined operations 0*inf, inf - inf, inf/inf, and 0/0 become defined. In this way no operation remains that gives rise to an error condition. Mathematically questionable features of the floating-point standard become well-defined sets of reals. Interval semantics provides a basis for the verification of numerical algorithms. We derive the results of the newly defined operations and consider the implications for hardware implementation.
Ogden's Lemma for Regular Tree Languages
Venue: arXiv cs.CC 2008
Year: 2008

We motivate and prove a strong pumping lemma for regular tree languages. The new lemma can be seen as the natural correspondent of Ogden's lemma for context-free string languages.
Non binary LDPC codes over the binary erasure channel: density evolution analysis
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we present a thorough analysis of non binary LDPC codes over the binary erasure channel. First, the decoding of non binary LDPC codes is investigated. The proposed algorithm performs on-the-fly decoding, i.e. it starts decoding as soon as the first symbols are received, which generalizes the erasure decoding of binary LDPC codes. Next, we evaluate the asymptotical performance of ensembles of non binary LDPC codes, by using the density evolution method. Density evolution equations are derived by taking into consideration both the irregularity of the bipartite graph and the probability distribution of the graph edge labels. Finally, infinite-length performance of some ensembles of non binary LDPC codes for different edge label distributions are shown.
Assembling Actor-based Mind-Maps from Text Stream
Venue: arXiv cs.CL 2008
Year: 2008

For human beings, the processing of text streams of unknown size leads generally to problems because e.g. noise must be selected out, information be tested for its relevance or redundancy, and linguistic phenomenon like ambiguity or the resolution of pronouns be advanced. Putting this into simulation by using an artificial mind-map is a challenge, which offers the gate for a wide field of applications like automatic text summarization or punctual retrieval. In this work we present a framework that is a first step towards an automatic intellect. It aims at assembling a mind-map based on incoming text streams and on a subject-verb-object strategy, having the verb as an interconnection between the adjacent nouns. The mind-map's performance is enriched by a pronoun resolution engine that bases on the work of D. Klein, and C. D. Manning.
A watermarking algorithm satisfying topological chaos properties
Venue: arXiv cs.CR 2008
Year: 2008

A new watermarking algorithm is given, it is based on the so-called chaotic iterations and on the choice of some coefficients which are deduced from the description of the carrier medium. After defining these coefficients, chaotic discrete iterations are used to encrypt the watermark and to embed it in the carrier medium. This procedure generates a topological chaos and ensures that the required properties of a watermarking algorithm are satisfied. Key-words: Watermarking, Encryption, Chaotic iterations, Topological chaos, Information hiding
New completely regular q-ary codes based on Kronecker products
Venue: arXiv cs.IT 2008
Year: 2008

For any integer $ρ\geq 1$ and for any prime power q, the explicit construction of a infinite family of completely regular (and completely transitive) q-ary codes with d=3 and with covering radius $ρ$ is given. The intersection array is also computed. Under the same conditions, the explicit construction of an infinite family of q-ary uniformly packed codes (in the wide sense) with covering radius $ρ$, which are not completely regular, is also given. In both constructions the Kronecker product is the basic tool that has been used.
Automatic structures of bounded degree revisited
Venue: arXiv cs.LO 2008
Year: 2008

The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar results also for tree automatic structures. These findings close the gaps left open in a previous paper of the second author by improving both, the lower and the upper bounds.
Quasi-metrics, Similarities and Searches: aspects of geometry of protein datasets
Venue: arXiv cs.IR 2008
Year: 2008

A quasi-metric is a distance function which satisfies the triangle inequality but is not symmetric: it can be thought of as an asymmetric metric. The central result of this thesis, developed in Chapter 3, is that a natural correspondence exists between similarity measures between biological (nucleotide or protein) sequences and quasi-metrics. Chapter 2 presents basic concepts of the theory of quasi-metric spaces and introduces a new examples of them: the universal countable rational quasi-metric space and its bicompletion, the universal bicomplete separable quasi-metric space. Chapter 4 is dedicated to development of a notion of the quasi-metric space with Borel probability measure, or pq-space. The main result of this chapter indicates that `a high dimensional quasi-metric space is close to being a metric space'. Chapter 5 investigates the geometric aspects of the theory of database similarity search in the context of quasi-metrics. The results about $pq$-spaces are used to produce novel theoretical bounds on performance of indexing schemes. Finally, the thesis presents some biological applications. Chapter 6 introduces FSIndex, an indexing scheme that significantly accelerates similarity searches of short protein fragment datasets. Chapter 7 presents the prototype of the system for discovery of short functional protein motifs called PFMFind, which relies on FSIndex for similarity searches.
Effective Complexity and its Relation to Logical Depth
Venue: arXiv cs.IT 2008
Year: 2008

Effective complexity measures the information content of the regularities of an object. It has been introduced by M. Gell-Mann and S. Lloyd to avoid some of the disadvantages of Kolmogorov complexity, also known as algorithmic information content. In this paper, we give a precise formal definition of effective complexity and rigorous proofs of its basic properties. In particular, we show that incompressible binary strings are effectively simple, and we prove the existence of strings that have effective complexity close to their lengths. Furthermore, we show that effective complexity is related to Bennett's logical depth: If the effective complexity of a string $x$ exceeds a certain explicit threshold then that string must have astronomically large depth; otherwise, the depth can be arbitrarily small.
On the Conditional Independence Implication Problem: A Lattice-Theoretic Approach
Venue: arXiv cs.AI 2008
Year: 2008

A lattice-theoretic framework is introduced that permits the study of the conditional independence (CI) implication problem relative to the class of discrete probability measures. Semi-lattices are associated with CI statements and a finite, sound and complete inference system relative to semi-lattice inclusions is presented. This system is shown to be (1) sound and complete for saturated CI statements, (2) complete for general CI statements, and (3) sound and complete for stable CI statements. These results yield a criterion that can be used to falsify instances of the implication problem and several heuristics are derived that approximate this "lattice-exclusion" criterion in polynomial time. Finally, we provide experimental results that relate our work to results obtained from other existing inference algorithms.
Conversion/Preference Games
Venue: arXiv cs.GT 2008
Year: 2008

We introduce the concept of Conversion/Preference Games, or CP games for short. CP games generalize the standard notion of strategic games. First we exemplify the use of CP games. Second we formally introduce and define the CP-games formalism. Then we sketch two `real-life' applications, namely a connection between CP games and gene regulation networks, and the use of CP games to formalize implied information in Chinese Wall security. We end with a study of a particular fixed-point construction over CP games and of the resulting existence of equilibria in possibly infinite games.
A Deterministic Model for Analyzing the Dynamics of Ant System Algorithm and Performance Amelioration through a New Pheromone Deposition Approach
Venue: arXiv cs.OH 2008
Year: 2008

Ant Colony Optimization (ACO) is a metaheuristic for solving difficult discrete optimization problems. This paper presents a deterministic model based on differential equation to analyze the dynamics of basic Ant System algorithm. Traditionally, the deposition of pheromone on different parts of the tour of a particular ant is always kept unvarying. Thus the pheromone concentration remains uniform throughout the entire path of an ant. This article introduces an exponentially increasing pheromone deposition approach by artificial ants to improve the performance of basic Ant System algorithm. The idea here is to introduce an additional attracting force to guide the ants towards destination more easily by constructing an artificial potential field identified by increasing pheromone concentration towards the goal. Apart from carrying out analysis of Ant System dynamics with both traditional and the newly proposed deposition rules, the paper presents an exhaustive set of experiments performed to find out suitable parameter ranges for best performance of Ant System with the proposed deposition approach. Simulations reveal that the proposed deposition rule outperforms the traditional one by a large extent both in terms of solution quality and algorithm convergence. Thus, the contributions of the article can be presented as follows: i) it introduces differential equation and explores a novel method of analyzing the dynamics of ant system algorithms, ii) it initiates an exponentially increasing pheromone deposition approach by artificial ants to improve the performance of algorithm in terms of solution quality and convergence time, iii) exhaustive experimentation performed facilitates the discovery of an algebraic relationship between the parameter set of the algorithm and feature of the problem environment.
A computational model of affects
Venue: arXiv cs.AI 2008
Year: 2008

This article provides a simple logical structure, in which affective concepts (i.e. concepts related to emotions and feelings) can be defined. The set of affects defined is similar to the set of emotions covered in the OCC model (Ortony A., Collins A., and Clore G. L.: The Cognitive Structure of Emotions. Cambridge University Press, 1988), but the model presented in this article is fully computationally defined.
A Novel Approach for Complete Identification of Dynamic Fractional Order Systems Using Stochastic Optimization Algorithms and Fractional Calculus
Venue: arXiv cs.OH 2008
Year: 2008

This contribution deals with identification of fractional-order dynamical systems. System identification, which refers to estimation of process parameters, is a necessity in control theory. Real processes are usually of fractional order as opposed to the ideal integral order models. A simple and elegant scheme of estimating the parameters for such a fractional order process is proposed. This method employs fractional calculus theory to find equations relating the parameters that are to be estimated, and then estimates the process parameters after solving the simultaneous equations. The said simultaneous equations are generated and updated using particle swarm optimization (PSO) technique, the fitness function being the sum of squared deviations from the actual set of observations. The data used for the calculations are intentionally corrupted to simulate real-life conditions. Results show that the proposed scheme offers a very high degree of accuracy even for erroneous data.
Energy Benefit of Network Coding for Multiple Unicast in Wireless Networks
Venue: arXiv cs.IT 2008
Year: 2008

We show that the maximum possible energy benefit of network coding for multiple unicast on wireless networks is at least 3. This improves the previously known lower bound of 2.4 from [1].
On the dynamics of Social Balance on general networks (with an application to XOR-SAT)
Venue: arXiv cs.DM 2008
Year: 2008

We study nondeterministic and probabilistic versions of a discrete dynamical system (due to T. Antal, P. L. Krapivsky, and S. Redner) inspired by Heider's social balance theory. We investigate the convergence time of this dynamics on several classes of graphs. Our contributions include: 1. We point out the connection between the triad dynamics and a generalization of annihilating walks to hypergraphs. In particular, this connection allows us to completely characterize the recurrent states in graphs where each edge belongs to at most two triangles. 2. We also solve the case of hypergraphs that do not contain edges consisting of one or two vertices. 3. We show that on the so-called "triadic cycle" graph, the convergence time is linear. 4. We obtain a cubic upper bound on the convergence time on 2-regular triadic simplexes G. This bound can be further improved to a quantity that depends on the Cheeger constant of G. In particular this provides some rigorous counterparts to previous experimental observations. We also point out an application to the analysis of the random walk algorithm on certain instances of the 3-XOR-SAT problem.