OpenRaiser/Intern-Atlas huggingface dataset:
Statistical Modelling of Information Sharing: Community, Membership and Content
Venue: arXiv cs.NI 2005
Year: 2005

File-sharing systems, like many online and traditional information sharing communities (e.g. newsgroups, BBS, forums, interest clubs), are dynamical systems in nature. As peers get in and out of the system, the information content made available by the prevailing membership varies continually in amount as well as composition, which in turn affects all peers' join/leave decisions. As a result, the dynamics of membership and information content are strongly coupled, suggesting interesting issues about growth, sustenance and stability. In this paper, we propose to study such communities with a simple statistical model of an information sharing club. Carrying their private payloads of information goods as potential supply to the club, peers join or leave on the basis of whether the information they demand is currently available. Information goods are chunked and typed, as in a file sharing system where peers contribute different files, or a forum where messages are grouped by topics or threads. Peers' demand and supply are then characterized by statistical distributions over the type domain. This model reveals interesting critical behaviour with multiple equilibria. A sharp growth threshold is derived: the club may grow towards a sustainable equilibrium only if the value of an order parameter is above the threshold, or shrink to emptiness otherwise. The order parameter is composite and comprises the peer population size, the level of their contributed supply, the club's efficiency in information search, the spread of supply and demand over the type domain, as well as the goodness of match between them.
Design of Block Transceivers with Decision Feedback Detection
Venue: arXiv cs.IT 2005
Year: 2005

This paper presents a method for jointly designing the transmitter-receiver pair in a block-by-block communication system that employs (intra-block) decision feedback detection. We provide closed-form expressions for transmitter-receiver pairs that simultaneously minimize the arithmetic mean squared error (MSE) at the decision point (assuming perfect feedback), the geometric MSE, and the bit error rate of a uniformly bit-loaded system at moderate-to-high signal-to-noise ratios. Separate expressions apply for the ``zero-forcing'' and ``minimum MSE'' (MMSE) decision feedback structures. In the MMSE case, the proposed design also maximizes the Gaussian mutual information and suggests that one can approach the capacity of the block transmission system using (independent instances of) the same (Gaussian) code for each element of the block. Our simulation studies indicate that the proposed transceivers perform significantly better than standard transceivers, and that they retain their performance advantages in the presence of error propagation.
Correlation Clustering with a Fixed Number of Clusters
Venue: arXiv cs.DS 2005
Year: 2005

We continue the investigation of problems concerning correlation clustering or clustering with qualitative information, which is a clustering formulation that has been studied recently. The basic setup here is that we are given as input a complete graph on n nodes (which correspond to nodes to be clustered) whose edges are labeled + (for similar pairs of items) and - (for dissimilar pairs of items). Thus we have only as input qualitative information on similarity and no quantitative distance measure between items. The quality of a clustering is measured in terms of its number of agreements, which is simply the number of edges it correctly classifies, that is the sum of number of - edges whose endpoints it places in different clusters plus the number of + edges both of whose endpoints it places within the same cluster. In this paper, we study the problem of finding clusterings that maximize the number of agreements, and the complementary minimization version where we seek clusterings that minimize the number of disagreements. We focus on the situation when the number of clusters is stipulated to be a small constant k. Our main result is that for every k, there is a polynomial time approximation scheme for both maximizing agreements and minimizing disagreements. (The problems are NP-hard for every k >= 2.) The main technical work is for the minimization version, as the PTAS for maximizing agreements follows along the lines of the property tester for Max k-CUT. In contrast, when the number of clusters is not specified, the problem of minimizing disagreements was shown to be APX-hard, even though the maximization version admits a PTAS.
Constraint-Based Qualitative Simulation
Venue: arXiv cs.AI 2005
Year: 2005

We consider qualitative simulation involving a finite set of qualitative relations in presence of complete knowledge about their interrelationship. We show how it can be naturally captured by means of constraints expressed in temporal logic and constraint satisfaction problems. The constraints relate at each stage the 'past' of a simulation with its 'future'. The benefit of this approach is that it readily leads to an implementation based on constraint technology that can be used to generate simulations and to answer queries about them.
Linear Datalog and Bounded Path Duality of Relational Structures
Venue: arXiv cs.LO 2005
Year: 2005

In this paper we systematically investigate the connections between logics with a finite number of variables, structures of bounded pathwidth, and linear Datalog Programs. We prove that, in the context of Constraint Satisfaction Problems, all these concepts correspond to different mathematical embodiments of a unique robust notion that we call bounded path duality. We also study the computational complexity implications of the notion of bounded path duality. We show that every constraint satisfaction problem $\csp(\best)$ with bounded path duality is solvable in NL and that this notion explains in a uniform way all families of CSPs known to be in NL. Finally, we use the results developed in the paper to identify new problems in NL.
Critical Point for Maximum Likelihood Decoding of Linear Block Codes
Venue: arXiv cs.IT 2005
Year: 2005

In this letter, the SNR value at which the error performance curve of a soft decision maximum likelihood decoder reaches the slope corresponding to the code minimum distance is determined for a random code. Based on this value, referred to as the critical point, new insight about soft bounded distance decoding of random-like codes (and particularly Reed-Solomon codes) is provided.
Experimental Comparison of Classification Uncertainty for Randomised and Bayesian Decision Tree Ensembles
Venue: arXiv cs.AI 2005
Year: 2005

In this paper we experimentally compare the classification uncertainty of the randomised Decision Tree (DT) ensemble technique and the Bayesian DT technique with a restarting strategy on a synthetic dataset as well as on some datasets commonly used in the machine learning community. For quantitative evaluation of classification uncertainty, we use an Uncertainty Envelope dealing with the class posterior distribution and a given confidence probability. Counting the classifier outcomes, this technique produces feasible evaluations of the classification uncertainty. Using this technique in our experiments, we found that the Bayesian DT technique is superior to the randomised DT ensemble technique.
Learning Multi-Class Neural-Network Models from Electroencephalograms
Venue: arXiv cs.NE 2005
Year: 2005

We describe a new algorithm for learning multi-class neural-network models from large-scale clinical electroencephalograms (EEGs). This algorithm trains hidden neurons separately to classify all the pairs of classes. To find best pairwise classifiers, our algorithm searches for input variables which are relevant to the classification problem. Despite patient variability and heavily overlapping classes, a 16-class model learnt from EEGs of 65 sleeping newborns correctly classified 80.8% of the training and 80.1% of the testing examples. Additionally, the neural-network model provides a probabilistic interpretation of decisions.
Universal Minimax Discrete Denoising under Channel Uncertainty
Venue: arXiv cs.IT 2005
Year: 2005

The goal of a denoising algorithm is to recover a signal from its noise-corrupted observations. Perfect recovery is seldom possible and performance is measured under a given single-letter fidelity criterion. For discrete signals corrupted by a known discrete memoryless channel, the DUDE was recently shown to perform this task asymptotically optimally, without knowledge of the statistical properties of the source. In the present work we address the scenario where, in addition to the lack of knowledge of the source statistics, there is also uncertainty in the channel characteristics. We propose a family of discrete denoisers and establish their asymptotic optimality under a minimax performance criterion which we argue is appropriate for this setting. As we show elsewhere, the proposed schemes can also be implemented computationally efficiently.
Summarization from Medical Documents: A Survey
Venue: arXiv cs.CL 2005
Year: 2005

Objective: The aim of this paper is to survey the recent work in medical documents summarization. Background: During the last decade, documents summarization got increasing attention by the AI research community. More recently it also attracted the interest of the medical research community as well, due to the enormous growth of information that is available to the physicians and researchers in medicine, through the large and growing number of published journals, conference proceedings, medical sites and portals on the World Wide Web, electronic medical records, etc. Methodology: This survey gives first a general background on documents summarization, presenting the factors that summarization depends upon, discussing evaluation issues and describing briefly the various types of summarization techniques. It then examines the characteristics of the medical domain through the different types of medical documents. Finally, it presents and discusses the summarization techniques used so far in the medical domain, referring to the corresponding systems and their characteristics. Discussion and conclusions: The paper discusses thoroughly the promising paths for future research in medical documents summarization. It mainly focuses on the issue of scaling to large collections of documents in various languages and from different media, on personalization issues, on portability to new sub-domains, and on the integration of summarization technology in practical applications
Neural-Network Techniques for Visual Mining Clinical Electroencephalograms
Venue: arXiv cs.AI 2005
Year: 2005

In this chapter we describe new neural-network techniques developed for visual mining clinical electroencephalograms (EEGs), the weak electrical potentials invoked by brain activity. These techniques exploit fruitful ideas of Group Method of Data Handling (GMDH). Section 2 briefly describes the standard neural-network techniques which are able to learn well-suited classification modes from data presented by relevant features. Section 3 introduces an evolving cascade neural network technique which adds new input nodes as well as new neurons to the network while the training error decreases. This algorithm is applied to recognize artifacts in the clinical EEGs. Section 4 presents the GMDH-type polynomial networks learnt from data. We applied this technique to distinguish the EEGs recorded from an Alzheimer and a healthy patient as well as recognize EEG artifacts. Section 5 describes the new neural-network technique developed to induce multi-class concepts from data. We used this technique for inducing a 16-class concept from the large-scale clinical EEG data. Finally we discuss perspectives of applying the neural-network techniques to clinical EEGs.
An Evolving Cascade Neural Network Technique for Cleaning Sleep Electroencephalograms
Venue: arXiv cs.NE 2005
Year: 2005

Evolving Cascade Neural Networks (ECNNs) and a new training algorithm capable of selecting informative features are described. The ECNN initially learns with one input node and then evolves by adding new inputs as well as new hidden neurons. The resultant ECNN has a near minimal number of hidden neurons and inputs. The algorithm is successfully used for training ECNN to recognise artefacts in sleep electroencephalograms (EEGs) which were visually labelled by EEG-viewers. In our experiments, the ECNN outperforms the standard neural-network as well as evolutionary techniques.
Coloring Artemis graphs
Venue: arXiv cs.DM 2005
Year: 2005

We consider the class A of graphs that contain no odd hole, no antihole, and no ``prism'' (a graph consisting of two disjoint triangles with three disjoint paths between them). We show that the coloring algorithm found by the second and fourth author can be implemented in time O(n^2m) for any graph in A with n vertices and m edges, thereby improving on the complexity proposed in the original paper.
Capacity per Unit Energy of Fading Channels with a Peak Constraint
Venue: arXiv cs.IT 2005
Year: 2005

A discrete-time single-user scalar channel with temporally correlated Rayleigh fading is analyzed. There is no side information at the transmitter or the receiver. A simple expression is given for the capacity per unit energy, in the presence of a peak constraint. The simple formula of Verdu for capacity per unit cost is adapted to a channel with memory, and is used in the proof. In addition to bounding the capacity of a channel with correlated fading, the result gives some insight into the relationship between the correlation in the fading process and the channel capacity. The results are extended to a channel with side information, showing that the capacity per unit energy is one nat per Joule, independently of the peak power constraint. A continuous-time version of the model is also considered. The capacity per unit energy subject to a peak constraint (but no bandwidth constraint) is given by an expression similar to that for discrete time, and is evaluated for Gauss-Markov and Clarke fading channels.
A New Remote User Authentication Scheme Using Smart Cards with Check Digits
Venue: arXiv cs.CR 2005
Year: 2005

Since 1981, when Lamport introduced the remote user authentication scheme using table, a plenty of schemes had been proposed with table and without table using. In 1993, Chang and Wu [5] introduced Remote password authentication scheme with smart cards. A number of remote authentication schemes with smart cards have been proposed since then. These schemes allow a valid user to login a remote server and access the services provided by the remote server. But still there is no scheme to authenticate the remote proxy user. In this paper we propose firstly, a protocol to authenticate a proxy user remotely using smartcards.
P-Selectivity, Immunity, and the Power of One Bit
Venue: arXiv cs.CC 2005
Year: 2005

We prove that P-sel, the class of all P-selective sets, is EXP-immune, but is not EXP/1-immune. That is, we prove that some infinite P-selective set has no infinite EXP-time subset, but we also prove that every infinite P-selective set has some infinite subset in EXP/1. Informally put, the immunity of P-sel is so fragile that it is pierced by a single bit of information. The above claims follow from broader results that we obtain about the immunity of the P-selective sets. In particular, we prove that for every recursive function f, P-sel is DTIME(f)-immune. Yet we also prove that P-sel is not Π_2^p/1-immune.
Spectral Orbits and Peak-to-Average Power Ratio of Boolean Functions with respect to the {I,H,N}^n Transform
Venue: arXiv cs.IT 2005
Year: 2005

We enumerate the inequivalent self-dual additive codes over GF(4) of blocklength n, thereby extending the sequence A090899 in The On-Line Encyclopedia of Integer Sequences from n = 9 to n = 12. These codes have a well-known interpretation as quantum codes. They can also be represented by graphs, where a simple graph operation generates the orbits of equivalent codes. We highlight the regularity and structure of some graphs that correspond to codes with high distance. The codes can also be interpreted as quadratic Boolean functions, where inequivalence takes on a spectral meaning. In this context we define PAR_IHN, peak-to-average power ratio with respect to the {I,H,N}^n transform set. We prove that PAR_IHN of a Boolean function is equivalent to the the size of the maximum independent set over the associated orbit of graphs. Finally we propose a construction technique to generate Boolean functions with low PAR_IHN and algebraic degree higher than 2.
Data Mining on Crash Simulation Data
Venue: arXiv cs.IR 2005
Year: 2005

The work presented in this paper is part of the cooperative research project AUTO-OPT carried out by twelve partners from the automotive industries. One major work package concerns the application of data mining methods in the area of automotive design. Suitable methods for data preparation and data analysis are developed. The objective of the work is the re-use of data stored in the crash-simulation department at BMW in order to gain deeper insight into the interrelations between the geometric variations of the car during its design and its performance in crash testing. In this paper a method for data analysis of finite element models and results from crash simulation is proposed and application to recent data from the industrial partner BMW is demonstrated. All necessary steps from data pre-processing to re-integration into the working environment of the engineer are covered.
Asymptotic Capacity Results for Non-Stationary Time-Variant Channels Using Subspace Projections
Venue: arXiv cs.IT 2005
Year: 2005

In this paper we deal with a single-antenna discrete-time flat-fading channel. The fading process is assumed to be stationary for the duration of a single data block. From block to block the fading process is allowed to be non-stationary. The number of scatterers bounds the rank of the channels covariance matrix. The signal-to-noise ratio (SNR), the user velocity, and the data block-length define the usable rank of the time-variant channel subspace. The usable channel subspace grows with the SNR. This growth in dimensionality must be taken into account for asymptotic capacity results in the high-SNR regime. Using results from the theory of time-concentrated and band-limited sequences we are able to define an SNR threshold below which the capacity grows logarithmically. Above this threshold the capacity grows double-logarithmically.
The Generic Multiple-Precision Floating-Point Addition With Exact Rounding (as in the MPFR Library)
Venue: arXiv cs.DS 2005
Year: 2005

We study the multiple-precision addition of two positive floating-point numbers in base 2, with exact rounding, as specified in the MPFR library, i.e. where each number has its own precision. We show how the best possible complexity (up to a constant factor that depends on the implementation) can be obtain.
A linear memory algorithm for Baum-Welch training
Venue: arXiv cs.LG 2005
Year: 2005

Background: Baum-Welch training is an expectation-maximisation algorithm for training the emission and transition probabilities of hidden Markov models in a fully automated way. Methods and results: We introduce a linear space algorithm for Baum-Welch training. For a hidden Markov model with M states, T free transition and E free emission parameters, and an input sequence of length L, our new algorithm requires O(M) memory and O(L M T_max (T + E)) time for one Baum-Welch iteration, where T_max is the maximum number of states that any state is connected to. The most memory efficient algorithm until now was the checkpointing algorithm with O(log(L) M) memory and O(log(L) L M T_max) time requirement. Our novel algorithm thus renders the memory requirement completely independent of the length of the training sequences. More generally, for an n-hidden Markov model and n input sequences of length L, the memory requirement of O(log(L) L^(n-1) M) is reduced to O(L^(n-1) M) memory while the running time is changed from O(log(L) L^n M T_max + L^n (T + E)) to O(L^n M T_max (T + E)). Conclusions: For the large class of hidden Markov models used for example in gene prediction, whose number of states does not scale with the length of the input sequence, our novel algorithm can thus be both faster and more memory-efficient than any of the existing algorithms.
Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes
Venue: arXiv cs.DS 2005
Year: 2005

We study practically efficient methods for performing combinatorial group testing. We present efficient non-adaptive and two-stage combinatorial group testing algorithms, which identify the at most d items out of a given set of n items that are defective, using fewer tests for all practical set sizes. For example, our two-stage algorithm matches the information theoretic lower bound for the number of tests in a combinatorial group testing regimen.
A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme
Venue: arXiv cs.CR 2005
Year: 2005

In this paper, firstly we propose two new concepts concerning the notion of key escrow encryption schemes: provable partiality and independency. Roughly speaking we say that a scheme has provable partiality if existing polynomial time algorithm for recovering the secret knowing escrowed information implies a polynomial time algorithm that can solve a well-known intractable problem. In addition, we say that a scheme is independent if the secret key and the escrowed information are independent. Finally, we propose a new verifiable partial key escrow, which has both of above criteria. The new scheme use McCurley encryption scheme as underlying scheme.
The Cyborg Astrobiologist: Scouting Red Beds for Uncommon Features with Geological Significance
Venue: arXiv cs.CV 2005
Year: 2005

The `Cyborg Astrobiologist' (CA) has undergone a second geological field trial, at a red sandstone site in northern Guadalajara, Spain, near Riba de Santiuste. The Cyborg Astrobiologist is a wearable computer and video camera system that has demonstrated a capability to find uncommon interest points in geological imagery in real-time in the field. The first (of three) geological structures that we studied was an outcrop of nearly homogeneous sandstone, which exhibits oxidized-iron impurities in red and and an absence of these iron impurities in white. The white areas in these ``red beds'' have turned white because the iron has been removed by chemical reduction, perhaps by a biological agent. The computer vision system found in one instance several (iron-free) white spots to be uncommon and therefore interesting, as well as several small and dark nodules. The second geological structure contained white, textured mineral deposits on the surface of the sandstone, which were found by the CA to be interesting. The third geological structure was a 50 cm thick paleosol layer, with fossilized root structures of some plants, which were found by the CA to be interesting. A quasi-blind comparison of the Cyborg Astrobiologist's interest points for these images with the interest points determined afterwards by a human geologist shows that the Cyborg Astrobiologist concurred with the human geologist 68% of the time (true positive rate), with a 32% false positive rate and a 32% false negative rate. (abstract has been abridged).
Consistent query answers on numerical databases under aggregate constraints
Venue: arXiv cs.DB 2005
Year: 2005

The problem of extracting consistent information from relational databases violating integrity constraints on numerical data is addressed. In particular, aggregate constraints defined as linear inequalities on aggregate-sum queries on input data are considered. The notion of repair as consistent set of updates at attribute-value level is exploited, and the characterization of several complexity issues related to repairing data and computing consistent query answers is provided.