OpenRaiser/Intern-Atlas huggingface dataset:
Probabilistic Inference from Arbitrary Uncertainty using Mixtures of Factorized Generalized Gaussians
Venue: arXiv cs.AI 2011
Year: 2011

This paper presents a general and efficient framework for probabilistic inference and learning from arbitrary uncertain information. It exploits the calculation properties of finite mixture models, conjugate families and factorization. Both the joint probability density of the variables and the likelihood function of the (objective or subjective) observation are approximated by a special mixture model, in such a way that any desired conditional distribution can be directly obtained without numerical integration. We have developed an extended version of the expectation maximization (EM) algorithm to estimate the parameters of mixture models from uncertain training examples (indirect observations). As a consequence, any piece of exact or uncertain information about both input and output values is consistently handled in the inference and learning stages. This ability, extremely useful in certain situations, is not found in most alternative methods. The proposed framework is formally justified from standard probabilistic principles and illustrative examples are provided in the fields of nonparametric pattern classification, nonlinear regression and pattern completion. Finally, experiments on a real application and comparative results over standard databases provide empirical evidence of the utility of the method in a wide range of applications.
Emergent velocity agreement in robot networks
Venue: arXiv cs.NI 2011
Year: 2011

In this paper we propose and prove correct a new self-stabilizing velocity agreement (flocking) algorithm for oblivious and asynchronous robot networks. Our algorithm allows a flock of uniform robots to follow a flock head emergent during the computation whatever its direction in plane. Robots are asynchronous, oblivious and do not share a common coordinate system. Our solution includes three modules architectured as follows: creation of a common coordinate system that also allows the emergence of a flock-head, setting up the flock pattern and moving the flock. The novelty of our approach steams in identifying the necessary conditions on the flock pattern placement and the velocity of the flock-head (rotation, translation or speed) that allow the flock to both follow the exact same head and to preserve the flock pattern. Additionally, our system is self-healing and self-stabilizing. In the event of the head leave (the leading robot disappears or is damaged and cannot be recognized by the other robots) the flock agrees on another head and follows the trajectory of the new head. Also, robots are oblivious (they do not recall the result of their previous computations) and we make no assumption on their initial position. The step complexity of our solution is O(n).
Efficient Diversification of Web Search Results
Venue: arXiv cs.IR 2011
Year: 2011

In this paper we analyze the efficiency of various search results diversification methods. While efficacy of diversification approaches has been deeply investigated in the past, response time and scalability issues have been rarely addressed. A unified framework for studying performance and feasibility of result diversification solutions is thus proposed. First we define a new methodology for detecting when, and how, query results need to be diversified. To this purpose, we rely on the concept of "query refinement" to estimate the probability of a query to be ambiguous. Then, relying on this novel ambiguity detection method, we deploy and compare on a standard test set, three different diversification methods: IASelect, xQuAD, and OptSelect. While the first two are recent state-of-the-art proposals, the latter is an original algorithm introduced in this paper. We evaluate both the efficiency and the effectiveness of our approach against its competitors by using the standard TREC Web diversification track testbed. Results shown that OptSelect is able to run two orders of magnitude faster than the two other state-of-the-art approaches and to obtain comparable figures in diversification effectiveness.
Outage Probability of Diversity Combining Receivers in Arbitrarily Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

We propose a simple and accurate method to evaluate the outage probability at the output of arbitrarily fading L-branch diversity combining receiver. The method is based on the saddlepoint approximation, which only requires the knowledge of the moment generating functions of the signal-to-noise ratio at the output of each diversity branch. In addition, we show that the obtained results reduce to closed-form expressions in many particular cases of practical interest. Numerical results illustrate a very high accuracy of the proposed method for practical outage values and for a large mixture of fading and system parameters.
Preprocessing for Automating Early Detection of Cervical Cancer
Venue: arXiv cs.CV 2011
Year: 2011

Uterine Cervical Cancer is one of the most common forms of cancer in women worldwide. Most cases of cervical cancer can be prevented through screening programs aimed at detecting precancerous lesions. During Digital Colposcopy, colposcopic images or cervigrams are acquired in raw form. They contain specular reflections which appear as bright spots heavily saturated with white light and occur due to the presence of moisture on the uneven cervix surface and. The cervix region occupies about half of the raw cervigram image. Other parts of the image contain irrelevant information, such as equipment, frames, text and non-cervix tissues. This irrelevant information can confuse automatic identification of the tissues within the cervix. Therefore we focus on the cervical borders, so that we have a geometric boundary on the relevant image area. Our novel technique eliminates the SR, identifies the region of interest and makes the cervigram ready for segmentation algorithms.
GutenTag: A Multi-Term Caching Optimized Tag Query Processor for Key-Value Based NoSQL Storage Systems
Venue: arXiv cs.IR 2011
Year: 2011

NoSQL systems are more and more deployed as back-end infrastructure for large-scale distributed online platforms like Google, Amazon or Facebook. Their applicability results from the fact that most services of online platforms access the stored data objects via their primary key. However, NoSQL systems do not efficiently support services referring more than one data object, e.g. the term-based search for data objects. To address this issue we propose our architecture based on an inverted index on top of a NoSQL system. For queries comprising more than one term, distributed indices yield a limited performance in large distributed systems. We propose two extensions to cope with this challenge. Firstly, we store index entries not only for single term but also for a selected set of term combinations depending on their popularity derived from a query history. Secondly, we additionally cache popular keys on gateway nodes, which are a common concept in real-world systems, acting as interface for services when accessing data objects in the back end. Our results show that we can significantly reduces the bandwidth consumption for processing queries, with an acceptable, marginal increase in the load of the gateway nodes.
Explicit formula for the generating series of diagonal 3D rook paths
Venue: arXiv cs.SC 2011
Year: 2011

Let $a_n$ denote the number of ways in which a chess rook can move from a corner cell to the opposite corner cell of an $n \times n \times n$ three-dimensional chessboard, assuming that the piece moves closer to the goal cell at each step. We describe the computer-driven \emph{discovery and proof} of the fact that the generating series $G(x)= \sum_{n \geq 0} a_n x^n$ admits the following explicit expression in terms of a Gaussian hypergeometric function: \[ G(x) = 1 + 6 \cdot \int_0^x \frac{\,\pFq21{1/3}{2/3}{2} {\frac{27 w(2-3w)}{(1-4w)^3}}}{(1-4w)(1-64w)} \, dw.\]
Perception of Personality and Naturalness through Dialogues by Native Speakers of American English and Arabic
Venue: arXiv cs.CL 2011
Year: 2011

Linguistic markers of personality traits have been studied extensively, but few cross-cultural studies exist. In this paper, we evaluate how native speakers of American English and Arabic perceive personality traits and naturalness of English utterances that vary along the dimensions of verbosity, hedging, lexical and syntactic alignment, and formality. The utterances are the turns within dialogue fragments that are presented as text transcripts to the workers of Amazon's Mechanical Turk. The results of the study suggest that all four dimensions can be used as linguistic markers of all personality traits by both language communities. A further comparative analysis shows cross-cultural differences for some combinations of measures of personality traits and naturalness, the dimensions of linguistic variability and dialogue acts.
Exploiting Conceptual Knowledge for Querying Information Systems
Venue: arXiv cs.IR 2011
Year: 2011

Whereas today's information systems are well-equipped for efficient query handling, their strict mathematical foundations hamper their use for everyday tasks. In daily life, people expect information to be offered in a personalized and focused way. But currently, personalization in digital systems still only takes explicit knowledge into account and does not yet process conceptual information often naturally implied by users. We discuss how to bridge the gap between users and today's systems, building on results from cognitive psychology.
Incremental Refinement using a Gaussian Test Channel
Venue: arXiv cs.IT 2011
Year: 2011

The additive rate-distortion function (ARDF) was developed in order to universally bound the rate loss in the Wyner-Ziv problem, and has since then been instrumental in e.g., bounding the rate loss in successive refinements, universal quantization, and other multi-terminal source coding settings. The ARDF is defined as the minimum mutual information over an additive test channel followed by estimation. In the limit of high resolution, the ADRF coincides with the true RDF for many sources and fidelity criterions. In the other extreme, i.e., the limit of low resolutions, the behavior of the ARDF has not previously been rigorously addressed. In this work, we consider the special case of quadratic distortion and where the noise in the test channel is Gaussian distributed. We first establish a link to the I-MMSE relation of Guo et al. and use this to show that for any source the slope of the ARDF near zero rate, converges to the slope of the Gaussian RDF near zero rate. We then consider the multiplicative rate loss of the ARDF, and show that for bursty sources it may be unbounded, contrary to the additive rate loss, which is upper bounded by 1/2 bit for all sources. We finally show that unconditional incremental refinement, i.e., where each refinement is encoded independently of the other refinements, is ARDF optimal in the limit of low resolution, independently of the source distribution. Our results also reveal under which conditions linear estimation is ARDF optimal in the low rate regime.
Misleading Stars: What Cannot Be Measured in the Internet?
Venue: arXiv cs.NI 2011
Year: 2011

Traceroute measurements are one of our main instruments to shed light onto the structure and properties of today's complex networks such as the Internet. This paper studies the feasibility and infeasibility of inferring the network topology given traceroute data from a worst-case perspective, i.e., without any probabilistic assumptions on, e.g., the nodes' degree distribution. We attend to a scenario where some of the routers are anonymous, and propose two fundamental axioms that model two basic assumptions on the traceroute data: (1) each trace corresponds to a real path in the network, and (2) the routing paths are at most a factor 1/alpha off the shortest paths, for some parameter alpha in (0,1]. In contrast to existing literature that focuses on the cardinality of the set of (often only minimal) inferrable topologies, we argue that a large number of possible topologies alone is often unproblematic, as long as the networks have a similar structure. We hence seek to characterize the set of topologies inferred with our axioms. We introduce the notion of star graphs whose colorings capture the differences among inferred topologies; it also allows us to construct inferred topologies explicitly. We find that in general, inferrable topologies can differ significantly in many important aspects, such as the nodes' distances or the number of triangles. These negative results are complemented by a discussion of a scenario where the trace set is best possible, i.e., "complete". It turns out that while some properties such as the node degrees are still hard to measure, a complete trace set can help to determine global properties such as the connectivity.
Quantum Communication Complexity of Quantum Authentication Protocols
Venue: arXiv cs.IT 2011
Year: 2011

In order to perform Quantum Cryptography procedures it is often essencial to ensure that the parties of the communication are authentic. Such task is accomplished by quantum authentication protocols which are distributed algorithms based on the intrinsic properties of Quantum Mechanics. The choice of an authentication protocol must consider that quantum states are very delicate and that the channel is subject to eavesdropping. However, even in face of the various existing definitions of quantum authentication protocols in the literature, little is known about them in this perspective, and this lack of knowledge may unfavor comparisons and wise choices. In the attempt to overcome this limitation, in the present work we aim at showing an approach to evaluate quantum authentication protocols based on the determination of their quantum communication complexity. Based on our investigation, no similar methods to analyze quantum authentication protocols were found in the literature. Pursuing this further, our approach has advantages that need to be highlighted: it characterizes a systematic procedure to evaluate quantum authentication protocols; its evaluation is intuitive, based only on the protocol execution; the resulting measure is a concise notation of what resources a quantum authentication protocol demands and how many communications are performed; it allows comparisons between protocols; it makes possible to analyze the communication effort when an eavesdropping occurs; and, lastly, it is likely to be applied in almost any quantum authentication protocol. To illustrate the proposed approach, we also bring results about its application in ten existing quantum authentication protocols (data origin authentication and identity authentication). Such evaluations increase the knowledge about the existing protocols, presenting its advantages, limitations and contrasts.
The capacity region of classes of product broadcast channels
Venue: arXiv cs.IT 2011
Year: 2011

We establish a new outer bound for the capacity region of product broadcast channels. This outer bound matches Marton's inner bound for a variety of classes of product broadcast channels whose capacity regions were previously unknown. These classes include product of reversely semi-deterministic and product of reversely more-capable channels. A significant consequence of this new outer bound is that it establishes, via an example, that the previously best known outer-bound is strictly suboptimal for the general broadcast channel. Our example is comprised of a product broadcast channel with two semi-deterministic components in reverse orientation.
Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
Venue: arXiv cs.AI 2011
Year: 2011

Planning under uncertainty is a central problem in the study of automated sequential decision making, and has been addressed by researchers in many different fields, including AI planning, decision analysis, operations research, control theory and economics. While the assumptions and perspectives adopted in these areas often differ in substantial ways, many planning problems of interest to researchers in these fields can be modeled as Markov decision processes (MDPs) and analyzed using the techniques of decision theory. This paper presents an overview and synthesis of MDP-related methods, showing how they provide a unifying framework for modeling many classes of planning problems studied in AI. It also describes structural properties of MDPs that, when exhibited by particular classes of problems, can be exploited in the construction of optimal or approximately optimal policies or plans. Planning problems commonly possess structure in the reward and value functions used to describe performance criteria, in the functions used to describe state transitions and observations, and in the relationships among features used to describe states, actions, rewards, and observations. Specialized representations, and algorithms employing these representations, can achieve computational leverage by exploiting these various forms of structure. Certain AI techniques -- in particular those based on the use of structured, intensional representations -- can be viewed in this way. This paper surveys several types of representations for both classical and decision-theoretic planning problems, and planning algorithms that exploit these representations in a number of different ways to ease the computational burden of constructing policies or plans. It focuses primarily on abstraction, aggregation and decomposition techniques based on AI-style representations.
Extensible Knowledge Representation: the Case of Description Reasoners
Venue: arXiv cs.AI 2011
Year: 2011

This paper offers an approach to extensible knowledge representation and reasoning for a family of formalisms known as Description Logics. The approach is based on the notion of adding new concept constructors, and includes a heuristic methodology for specifying the desired extensions, as well as a modularized software architecture that supports implementing extensions. The architecture detailed here falls in the normalize-compared paradigm, and supports both intentional reasoning (subsumption) involving concepts, and extensional reasoning involving individuals after incremental updates to the knowledge base. The resulting approach can be used to extend the reasoner with specialized notions that are motivated by specific problems or application areas, such as reasoning about dates, plans, etc. In addition, it provides an opportunity to implement constructors that are not currently yet sufficiently well understood theoretically, but are needed in practice. Also, for constructors that are provably hard to reason with (e.g., ones whose presence would lead to undecidability), it allows the implementation of incomplete reasoners where the incompleteness is tailored to be acceptable for the application at hand.
Issues in Stacked Generalization
Venue: arXiv cs.AI 2011
Year: 2011

Stacked generalization is a general method of using a high-level model to combine lower-level models to achieve greater predictive accuracy. In this paper we address two crucial issues which have been considered to be a `black art' in classification tasks ever since the introduction of stacked generalization in 1992 by Wolpert: the type of generalizer that is suitable to derive the higher-level model, and the kind of attributes that should be used as its input. We find that best results are obtained when the higher-level model combines the confidence (and not just the predictions) of the lower-level ones. We demonstrate the effectiveness of stacked generalization for combining three different types of learning algorithms for classification tasks. We also compare the performance of stacked generalization with majority vote and published results of arcing and bagging.
Design and Analysis of SD_DWCA - A Mobility based clustering of Homogeneous MANETs
Venue: arXiv cs.DM 2011
Year: 2011

This paper deals with the design and analysis of the distributed weighted clustering algorithm SD_DWCA proposed for homogeneous mobile ad hoc networks. It is a connectivity, mobility and energy based clustering algorithm which is suitable for scalable ad hoc networks. The algorithm uses a new graph parameter called strong degree defined based on the quality of neighbours of a node. The parameters are so chosen to ensure high connectivity, cluster stability and energy efficient communication among nodes of high dynamic nature. This paper also includes the experimental results of the algorithm implemented using the network simulator NS2. The experimental results show that the algorithm is suitable for high speed networks and generate stable clusters with less maintenance overhead.
Finite First Hitting Time versus Stochastic Convergence in Particle Swarm Optimisation
Venue: arXiv cs.NE 2011
Year: 2011

We reconsider stochastic convergence analyses of particle swarm optimisation, and point out that previously obtained parameter conditions are not always sufficient to guarantee mean square convergence to a local optimum. We show that stagnation can in fact occur for non-trivial configurations in non-optimal parts of the search space, even for simple functions like SPHERE. The convergence properties of the basic PSO may in these situations be detrimental to the goal of optimisation, to discover a sufficiently good solution within reasonable time. To characterise optimisation ability of algorithms, we suggest the expected first hitting time (FHT), i.e., the time until a search point in the vicinity of the optimum is visited. It is shown that a basic PSO may have infinite expected FHT, while an algorithm introduced here, the Noisy PSO, has finite expected FHT on some functions.
A Frequency-domain Compensation Scheme for IQ-Imbalance in OFDM Receivers
Venue: arXiv cs.NI 2011
Year: 2011

A pilot pattern across two OFDM symbols with special structure is devised for channel estimation in OFDM systems with IQ imbalance at receiver. Based on this pilot pattern, a high-efficiency time-domain (TD) least square (LS) channel estimator is proposed to significantly suppress channel noise by a factor N/(L+1) in comparison with the frequency-domain LS one in [1] where N and L+1 are the total number of subcarriers and the length of cyclic prefix, respectively. Following this, a low-complexity frequency-domain (FD) Gaussian elimination (GE) equalizer is proposed to eliminate IQ distortion by using only 2N complex multiplications per OFDM symbol. From simulation, the proposed scheme TD-LS/FD-GE using only two pilot OFDM symbols achieves the same bit error rate (BER) performance under ideal channel knowledge and no IQ imbalances at low and medium signal-to-noise ratio (SNR) regions whereas these compensation schemes including FD-LS/Post-FFT LS, FD-LS/Pre-FFT Corr, and SPP/Pre-FFT Corr in [1] require about twenty OFDM training symbols to reach the same performance where A/B denotes compensation scheme with A being channel estimator and B being equalizer.
Scale-Invariant Local Descriptor for Event Recognition in 1D Sensor Signals
Venue: arXiv cs.MM 2011
Year: 2011

In this paper, we introduce a shape-based, time-scale invariant feature descriptor for 1-D sensor signals. The time-scale invariance of the feature allows us to use feature from one training event to describe events of the same semantic class which may take place over varying time scales such as walking slow and walking fast. Therefore it requires less training set. The descriptor takes advantage of the invariant location detection in the scale space theory and employs a high level shape encoding scheme to capture invariant local features of events. Based on this descriptor, a scale-invariant classifier with "R" metric (SIC-R) is designed to recognize multi-scale events of human activities. The R metric combines the number of matches of keypoint in scale space with the Dynamic Time Warping score. SICR is tested on various types of 1-D sensors data from passive infrared, accelerometer and seismic sensors with more than 90% classification accuracy.