OpenRaiser/Intern-Atlas huggingface dataset:
The Ariadne's Clew Algorithm
Venue: arXiv cs.AI 2011
Year: 2011

We present a new approach to path planning, called the "Ariadne's clew algorithm". It is designed to find paths in high-dimensional continuous spaces and applies to robots with many degrees of freedom in static, as well as dynamic environments - ones where obstacles may move. The Ariadne's clew algorithm comprises two sub-algorithms, called Search and Explore, applied in an interleaved manner. Explore builds a representation of the accessible space while Search looks for the target. Both are posed as optimization problems. We describe a real implementation of the algorithm to plan paths for a six degrees of freedom arm in a dynamic environment where another six degrees of freedom arm is used as a moving obstacle. Experimental results show that a path is found in about one second without any pre-processing.
Semantic Similarity in a Taxonomy: An Information-Based Measure and its Application to Problems of Ambiguity in Natural Language
Venue: arXiv cs.AI 2011
Year: 2011

This article presents a measure of semantic similarity in an IS-A taxonomy based on the notion of shared information content. Experimental evaluation against a benchmark set of human similarity judgments demonstrates that the measure performs better than the traditional edge-counting approach. The article presents algorithms that take advantage of taxonomic similarity in resolving syntactic and semantic ambiguity, along with experimental results demonstrating their effectiveness.
A Counter Example to Theorems of Cox and Fine
Venue: arXiv cs.AI 2011
Year: 2011

Cox's well-known theorem justifying the use of probability is shown not to hold in finite domains. The counterexample also suggests that Cox's assumptions are insufficient to prove the result even in infinite domains. The same counterexample is used to disprove a result of Fine on comparative conditional probability.
Variational Probabilistic Inference and the QMR-DT Network
Venue: arXiv cs.AI 2011
Year: 2011

We describe a variational approximation method for efficient inference in large-scale probabilistic models. Variational methods are deterministic procedures that provide approximations to marginal and conditional probabilities of interest. They provide alternatives to approximate inference methods based on stochastic sampling or search. We describe a variational approach to the problem of diagnostic inference in the `Quick Medical Reference' (QMR) network. The QMR network is a large-scale probabilistic graphical model built on statistical and expert knowledge. Exact probabilistic inference is infeasible in this model for all but a small set of cases. We evaluate our variational inference algorithm on a large set of diagnostic test cases, comparing the algorithm to a state-of-the-art stochastic sampling method.
Hybrid Trust Model for Internet Routing
Venue: arXiv cs.NI 2011
Year: 2011

The current Internet is based on a fundamental assumption of reliability and good intent among actors in the network. Unfortunately, unreliable and malicious behaviour is becoming a major obstacle for Internet communication. In order to improve the trustworthiness and reliability of the network infrastructure, we propose a novel trust model to be incorporated into BGP routing. In our approach, trust model is defined by combining voting and recommendation to direct trust estimation for neighbour routers located in different autonomous systems. We illustrate the impact of our approach with cases that demonstrate the indication of distrusted paths beyond the nearest neighbours and the detection of a distrusted neighbour advertising a trusted path. We simulated the impact of weighting voted and direct trust in a rectangular grid of 15*15 nodes (autonomous systems) with a randomly connected topology.
Quality of Service Provisioning in Manet Using a Cross-Layer Approach for Routing
Venue: arXiv cs.NI 2011
Year: 2011

Deployment of multimedia applications warrants provisioning of Quality of Service (QoS) in MANET. However, limited battery power, other resource constraints and mobility of nodes make QoS provisioning difficult to achieve in MANET. This difficulty can be overcome by using a cross-layer approach for routing. In [1] Patil et al., proposed a cross-layer routing protocol named Cost Based Power Aware Cross Layer - AODV (CPACL-AODV) which overcomes the limitation of battery power of nodes. Though many similar energy efficient and cross-layer routing protocols have been proposed for MANET, none of them handles QoS. A novel MANET routing protocol, Type of Service, Power and Bandwidth Aware AODV (TSPBA-AODV), which overcomes resource constraints and simultaneously provides QoS guarantees using a cross-layer approach, is proposed in this paper. In addition the effect of variation in nodes' mobility on performance of TSPBA-AODV is compared with that of CPACL-AODV [1] for two different types of network traffic. As shown by the results of simulations performed, TSPBA-AODV performs better than CPACL-AODV for MANET in which nodes move with small speeds (speeds up to 40 Km/hr approx.). In addition the effect of variation in data sending rate of nodes on performance of the protocols is also studied. As shown by the results of simulations performed, TSPBA-AODV performs better than CPACL-AODV for all variations in data sending rate of nodes.
Time-Dependent 2-D Vector Field Topology: An Approach Inspired by Lagrangian Coherent Structures
Venue: arXiv cs.GR 2011
Year: 2011

This paper presents an approach to a time-dependent variant of the concept of vector field topology for 2-D vector fields. Vector field topology is defined for steady vector fields and aims at discriminating the domain of a vector field into regions of qualitatively different behaviour. The presented approach represents a generalization for saddle-type critical points and their separatrices to unsteady vector fields based on generalized streak lines, with the classical vector field topology as its special case for steady vector fields. The concept is closely related to that of Lagrangian coherent structures obtained as ridges in the finite-time Lyapunov exponent field. The proposed approach is evaluated on both 2-D time-dependent synthetic and vector fields from computational fluid dynamics.
Network Codes with Overlapping Chunks over Line Networks: A Case for Linear-Time Codes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, the problem of designing network codes that are both communicationally and computationally efficient over packet line networks with worst-case schedules is considered. In this context, random linear network codes (dense codes) are asymptotically capacity-achieving, but require highly complex coding operations. To reduce the coding complexity, Maymounkov et al. proposed chunked codes (CC). Chunked codes operate by splitting the message into non-overlapping chunks and send a randomly chosen chunk at each transmission time by a dense code. The complexity, that is linear in the chunk size, is thus reduced compared to dense codes. In this paper, the existing analysis of CC is revised, and tighter bounds on the performance of CC are derived. As a result, we prove that (i) CC with sufficiently large chunks are asymptotically capacity-achieving, but with a slower speed of convergence compared to dense codes; and (ii) CC with relatively smaller chunks approach the capacity with an arbitrarily small but non-zero constant gap. To improve the speed of convergence of CC, while maintaining their advantage in reducing the computational complexity, we propose and analyze a new CC scheme with overlapping chunks, referred to as overlapped chunked codes (OCC). We prove that for smaller chunks, which are advantageous due to lower computational complexity, OCC with larger overlaps provide a better tradeoff between the speed of convergence and the message or packet error rate. This implies that for smaller chunks, and with the same computational complexity, OCC outperform CC in terms of the speed of approaching the capacity for sufficiently small target error rate. In fact, we design linear-time OCC with very small chunks (constant in the message size) that are both computationally and communicationally efficient, and that outperform linear-time CC.
On Real Time Coding with Limited Lookahead
Venue: arXiv cs.IT 2011
Year: 2011

A real time coding system with lookahead consists of a memoryless source, a memoryless channel, an encoder, which encodes the source symbols sequentially with knowledge of future source symbols upto a fixed finite lookahead, d, with or without feedback of the past channel output symbols and a decoder, which sequentially constructs the source symbols using the channel output. The objective is to minimize the expected per-symbol distortion. For a fixed finite lookahead d>=1 we invoke the theory of controlled markov chains to obtain an average cost optimality equation (ACOE), the solution of which, denoted by D(d), is the minimum expected per-symbol distortion. With increasing d, D(d) bridges the gap between causal encoding, d=0, where symbol by symbol encoding-decoding is optimal and the infinite lookahead case, d=\infty, where Shannon Theoretic arguments show that separation is optimal. We extend the analysis to a system with finite state decoders, with or without noise-free feedback. For a Bernoulli source and binary symmetric channel, under hamming loss, we compute the optimal distortion for various source and channel parameters, and thus obtain computable bounds on D(d). We also identify regions of source and channel parameters where symbol by symbol encoding-decoding is suboptimal. Finally, we demonstrate the wide applicability of our approach by applying it in additional coding scenarios, such as the case where the sequential decoder can take cost constrained actions affecting the quality or availability of side information about the source.
Grassmannian Predictive Coding for Limited Feedback in Multiple Antenna Wireless Systems
Venue: arXiv cs.IT 2011
Year: 2011

Limited feedback is a paradigm for the feedback of channel state information in wireless systems. In multiple antenna wireless systems, limited feedback usually entails quantizing a source that lives on the Grassmann manifold. Most work on limited feedback beamforming considered single-shot quantization. In wireless systems, however, the channel is temporally correlated, which can be used to reduce feedback requirements. Unfortunately, conventional predictive quantization does not incorporate the non-Euclidean structure of the Grassmann manifold. In this paper, we propose a Grassmannian predictive coding algorithm where the differential geometric structure of the Grassmann manifold is used to formulate a predictive vector quantization encoder and decoder. We analyze the quantization error and derive bounds on the distortion attained by the proposed algorithm. We apply the algorithm to a multiuser multiple-input multiple-output wireless system and show that it improves the achievable sum rate as the temporal correlation of the channel increases.
Sequences of Inequalities among Differences of Gini Means and Divergence Measures
Venue: arXiv cs.IT 2011
Year: 2011

In 1938, Gini studied a mean having two parameters. Later, many authors studied properties of this mean. In particular, it contains the famous means as harmonic, geometric, arithmetic, etc. Here we considered a sequence of inequalities arising due to particular values of each parameter of Gini's mean. This sequence generates many nonnegative differences. Not all of them are convex. We have studied here convexity of these differences and again established new sequences of inequalities of these differences. Considering in terms of probability distributions these differences, we have made connections with some of well known divergence measures.
Revealing digital documents. Concealed structures in data
Venue: arXiv cs.DL 2011
Year: 2011

This short paper gives an introduction to a research project to analyze how digital documents are structured and described. Using a phenomenological approach, this research will reveal common patterns that are used in data, independent from the particular technology in which the data is available. The ability to identify these patterns, on different levels of description, is important for several applications in digital libraries. A better understanding of data structuring will not only help to better capture singular characteristics of data by metadata, but will also recover intended structures of digital objects, beyond long term preservation.
Percolation and Connectivity on the Signal to Interference Ratio Graph
Venue: arXiv cs.IT 2011
Year: 2011

A wireless communication network is considered where any two nodes are connected if the signal-to-interference ratio (SIR) between them is greater than a threshold. Assuming that the nodes of the wireless network are distributed as a Poisson point process (PPP), percolation (unbounded connected cluster) on the resulting SIR graph is studied as a function of the density of the PPP. For both the path-loss as well as path-loss plus fading model of signal propagation, it is shown that for a small enough threshold, there exists a closed interval of densities for which percolation happens with non-zero probability. Conversely, for the path-loss model of signal propagation, it is shown that for a large enough threshold, there exists a closed interval of densities for which the probability of percolation is zero. Restricting all nodes to lie in an unit square, connectivity properties of the SIR graph are also studied. Assigning separate frequency bands or time-slots proportional to the logarithm of the number of nodes to different nodes for transmission/reception is sufficient to guarantee connectivity in the SIR graph.
Reconstruction of Fractional Brownian Motion Signals From Its Sparse Samples Based on Compressive Sampling
Venue: arXiv cs.NA 2011
Year: 2011

This paper proposes a new fBm (fractional Brownian motion) interpolation/reconstruction method from partially known samples based on CS (Compressive Sampling). Since 1/f property implies power law decay of the fBm spectrum, the fBm signals should be sparse in frequency domain. This property motivates the adoption of CS in the development of the reconstruction method. Hurst parameter H that occurs in the power law determines the sparsity level, therefore the CS reconstruction quality of an fBm signal for a given number of known subsamples will depend on H. However, the proposed method does not require the information of H to reconstruct the fBm signal from its partial samples. The method employs DFT (Discrete Fourier Transform) as the sparsity basis and a random matrix derived from known samples positions as the projection basis. Simulated fBm signals with various values of H are used to show the relationship between the Hurst parameter and the reconstruction quality. Additionally, US-DJIA (Dow Jones Industrial Average) stock index monthly values time-series are also used to show the applicability of the proposed method to reconstruct a real-world data.
Multiple Access Channel with States Known Noncausally at One Encoder and Only Strictly Causally at the Other Encoder
Venue: arXiv cs.IT 2011
Year: 2011

We consider a two-user state-dependent multiaccess channel in which the states of the channel are known non-causally to one of the encoders and only strictly causally to the other encoder. Both encoders transmit a common message and, in addition, the encoder that knows the states non-causally transmits an individual message. We study the capacity region of this communication model. In the discrete memoryless case, we establish inner and outer bounds on the capacity region. Although the encoder that sends both messages knows the states fully, we show that the strictly causal knowledge of these states at the other encoder can be beneficial for this encoder, and in general enlarges the capacity region. Furthermore, we find an explicit characterization of the capacity in the case in which the two encoders transmit only the common message. In the Gaussian case, we characterize the capacity region for the model with individual message as well. Our converse proof in this case shows that, for this model, strictly causal knowledge of the state at one of the encoders does not increase capacity if the other is informed non-causally, a result which sheds more light on the utility of conveying a compressed version of the state to the decoder in recent results by Lapidoth and Steinberg on a multiacess model with only strictly causal state at both encoders and independent messages.
Neural Networks for Emotion Classification
Venue: arXiv cs.CV 2011
Year: 2011

It is argued that for the computer to be able to interact with humans, it needs to have the communication skills of humans. One of these skills is the ability to understand the emotional state of the person. This thesis describes a neural network-based approach for emotion classification. We learn a classifier that can recognize six basic emotions with an average accuracy of 77% over the Cohn-Kanade database. The novelty of this work is that instead of empirically selecting the parameters of the neural network, i.e. the learning rate, activation function parameter, momentum number, the number of nodes in one layer, etc. we developed a strategy that can automatically select comparatively better combination of these parameters. We also introduce another way to perform back propagation. Instead of using the partial differential of the error function, we use optimal algorithm; namely Powell's direction set to minimize the error function. We were also interested in construction an authentic emotion databases. This is a very important task because nowadays there is no such database available. Finally, we perform several experiments and show that our neural network approach can be successfully used for emotion recognition.
Parallel Performance of MPI Sorting Algorithms on Dual-Core Processor Windows-Based Systems
Venue: arXiv cs.DC 2011
Year: 2011

Message Passing Interface (MPI) is widely used to implement parallel programs. Although Windowsbased architectures provide the facilities of parallel execution and multi-threading, little attention has been focused on using MPI on these platforms. In this paper we use the dual core Window-based platform to study the effect of parallel processes number and also the number of cores on the performance of three MPI parallel implementations for some sorting algorithms.
Mapping Relational Operations onto Hypergraph Model
Venue: arXiv cs.DB 2011
Year: 2011

The relational model is the most commonly used data model for storing large datasets, perhaps due to the simplicity of the tabular format which had revolutionized database management systems. However, many real world objects are recursive and associative in nature which makes storage in the relational model difficult. The hypergraph model is a generalization of a graph model, where each hypernode can be made up of other nodes or graphs and each hyperedge can be made up of one or more edges. It may address the recursive and associative limitations of relational model. However, the hypergraph model is non-tabular; thus, loses the simplicity of the relational model. In this study, we consider the means to convert a relational model into a hypergraph model in two layers. At the bottom layer, each relational tuple can be considered as a star graph centered where the primary key node is surrounded by non-primary key attributes. At the top layer, each tuple is a hypernode, and a relation is a set of hypernodes. We presented a reference implementation of relational operators (project, rename, select, inner join, natural join, left join, right join, outer join and Cartesian join) on a hypergraph model. Using a simple example, we demonstrate that a relation and relational operators can be implemented on this hypergraph model.
Construction of fuzzy automata from fuzzy regular expressions
Venue: arXiv cs.FL 2011
Year: 2011

Li and Pedrycz [Y. M. Li, W. Pedrycz, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice ordered monoids, Fuzzy Sets and Systems 156 (2005) 68--92] have proved fundamental results that provide different equivalent ways to represent fuzzy languages with membership values in a lattice-ordered monoid, and generalize the well-known results of the classical theory of formal languages. In particular, they have shown that a fuzzy language over an integral lattice-ordered monoid can be represented by a fuzzy regular expression if and only if it can be recognized by a fuzzy finite automaton. However, they did not give any effective method for constructing an equivalent fuzzy finite automaton from a given fuzzy regular expression. In this paper we provide such an effective method. Transforming scalars appearing in a fuzzy regular expression α into letters of the new extended alphabet, we convert the fuzzy regular expression α to an ordinary regular expression α_{R}. Then, starting from an arbitrary nondeterministic finite automaton A that recognizes the language ||α_R|| represented by the regular expression α_R, we construct fuzzy finite automata A_α and A_α^r with the same or even less number of states than the automaton A, which recognize the fuzzy language ||α|| represented by the fuzzy regular expression α. The starting nondeterministic finite automaton A can be obtained from α_R using any of the well-known constructions for converting regular expressions to nondeterministic finite automata, such as Glushkov-McNaughton-Yamada's position automaton, Brzozowski's derivative automaton, Antimirov's partial derivative automaton, or Ilie-Yu's follow automaton.
Using Context to Improve the Evaluation of Information Retrieval Systems
Venue: arXiv cs.IR 2011
Year: 2011

The crucial role of the evaluation in the development of the information retrieval tools is useful evidence to improve the performance of these tools and the quality of results that they return. However, the classic evaluation approaches have limitations and shortcomings especially regarding to the user consideration, the measure of the adequacy between the query and the returned documents and the consideration of characteristics, specifications and behaviors of the search tool. Therefore, we believe that the exploitation of contextual elements could be a very good way to evaluate the search tools. So, this paper presents a new approach that takes into account the context during the evaluation process at three complementary levels. The experiments gives at the end of this article has shown the applicability of the proposed approach to real research tools. The tests were performed with the most popular searching engine (i.e. Google, Bing and Yahoo) selected in particular for their high selectivity. The obtained results revealed that the ability of these engines to rejecting dead links, redundant results and parasites pages depends strongly to how queries are formulated, and to the political of sites offering this information to present their content. The relevance evaluation of results provided by these engines, using the user's judgments, then using an automatic manner to take into account the query context has also shown a general decline in the perceived relevance according to the number of the considered results.