OpenRaiser/Intern-Atlas huggingface dataset:
How really effective are Multimodal Hints in enhancing Visual Target Spotting? Some evidence from a usability study
Venue: arXiv cs.HC 2007
Year: 2007

The main aim of the work presented here is to contribute to computer science advances in the multimodal usability area, in-as-much as it addresses one of the major issues relating to the generation of effective oral system messages: how to design messages which effectively help users to locate specific graphical objects in information visualisations? An experimental study was carried out to determine whether oral messages including coarse information on the locations of graphical objects on the current display may facilitate target detection tasks sufficiently for making it worth while to integrate such messages in GUIs. The display spatial layout varied in order to test the influence of visual presentation structure on the contribution of these messages to facilitating visual search on crowded displays. Finally, three levels of task difficulty were defined, based mainly on the target visual complexity and the number of distractors in the scene. The findings suggest that spatial information messages improve participants' visual search performances significantly; they are more appropriate to radial structures than to matrix, random and elleptic structures; and, they are particularly useful for performing difficult visual search tasks.
Recursive Structure and Bandwidth of Hales-Numbered Hypercube
Venue: arXiv cs.DM 2007
Year: 2007

The Hales numbered $n$-dimensional hypercube and the corresponding adjacency matrix exhibit interesting recursive structures in $n$. These structures lead to a very simple proof of the well-known bandwidth formula for hypercube, whose proof was thought to be surprisingly difficult. A related problem called hypercube antibandwidth, for which Harper proposed an algorithm, is also reexamined in the light of the above recursive structures, and a close form solution is found.
Parametric Stiffness Analysis of the Orthoglide
Venue: arXiv cs.RO 2007
Year: 2007

This paper presents a parametric stiffness analysis of the Orthoglide, a 3-DOF translational Parallel Kinematic Machine. First, a compliant modeling of the Orthoglide is conducted based on an existing method. Then stiffness matrix is symbolically computed. This allows one to easily study the influence of the geometric design parameters on the matrix elements. Critical links are displayed. Cutting forces are then modeled so that static displacements of the Orthoglide tool during slot milling are symbolically computed. Influence of the geometric design parameters on the static displacements is checked as well. Other machining operations can be modeled. This parametric stiffness analysis can be applied to any parallel manipulator for which stiffness is a critical issue.
Pattern Matching in Trees and Strings
Venue: arXiv cs.DS 2007
Year: 2007

We study the design of efficient algorithms for combinatorial pattern matching. More concretely, we study algorithms for tree matching, string matching, and string matching in compressed texts.
Dualities Between Entropy Functions and Network Codes
Venue: arXiv cs.IT 2007
Year: 2007

This paper provides a new duality between entropy functions and network codes. Given a function $g\geq 0$ defined on all proper subsets of $N$ random variables, we provide a construction for a network multicast problem which is solvable if and only if $g$ is entropic. The underlying network topology is fixed and the multicast problem depends on $g$ only through edge capacities and source rates. Relaxing the requirement that the domain of $g$ be subsets of random variables, we obtain a similar duality between polymatroids and the linear programming bound. These duality results provide an alternative proof of the insufficiency of linear (and abelian) network codes, and demonstrate the utility of non-Shannon inequalities to tighten outer bounds on network coding capacity regions.
A system for the simulation of simultaneous moves between two noncolocational players
Venue: arXiv cs.GT 2007
Year: 2007

We describe a new system for the simulation of simultaneous moves between noncolocational players. This has applications in the burgeoning Rock-Paper-Scissors by mail movement.
Inferring Neuronal Network Connectivity using Time-constrained Episodes
Venue: arXiv cs.DB 2007
Year: 2007

Discovering frequent episodes in event sequences is an interesting data mining task. In this paper, we argue that this framework is very effective for analyzing multi-neuronal spike train data. Analyzing spike train data is an important problem in neuroscience though there are no data mining approaches reported for this. Motivated by this application, we introduce different temporal constraints on the occurrences of episodes. We present algorithms for discovering frequent episodes under temporal constraints. Through simulations, we show that our method is very effective for analyzing spike train data for unearthing underlying connectivity patterns.
Competition in Wireless Systems via Bayesian Interference Games
Venue: arXiv cs.GT 2007
Year: 2007

We study competition between wireless devices with incomplete information about their opponents. We model such interactions as Bayesian interference games. Each wireless device selects a power profile over the entire available bandwidth to maximize its data rate. Such competitive models represent situations in which several wireless devices share spectrum without any central authority or coordinated protocol. In contrast to games where devices have complete information about their opponents, we consider scenarios where the devices are unaware of the interference they cause to other devices. Such games, which are modeled as Bayesian games, can exhibit significantly different equilibria. We first consider a simple scenario of simultaneous move games, where we show that the unique Bayes-Nash equilibrium is where both devices spread their power equally across the entire bandwidth. We then extend this model to a two-tiered spectrum sharing case where users act sequentially. Here one of the devices, called the primary user, is the owner of the spectrum and it selects its power profile first. The second device (called the secondary user) then responds by choosing a power profile to maximize its Shannon capacity. In such sequential move games, we show that there exist equilibria in which the primary user obtains a higher data rate by using only a part of the bandwidth. In a repeated Bayesian interference game, we show the existence of reputation effects: an informed primary user can bluff to prevent spectrum usage by a secondary user who suffers from lack of information about the channel gains. The resulting equilibrium can be highly inefficient, suggesting that competitive spectrum sharing is highly suboptimal.
Rate Regions for the Partially-Cooperative Relay Broadcast Channel with Non-causal Side Information
Venue: arXiv cs.IT 2007
Year: 2007

In this work, we consider a partially cooperative relay broadcast channel (PC-RBC) controlled by random parameters. We provide rate regions for two different situations: 1) when side information (SI) S^n on the random parameters is non-causally known at both the source and the relay and, 2) when side information S^n is non-causally known at the source only. These achievable regions are derived for the general discrete memoryless case first and then extended to the case when the channel is degraded Gaussian and the SI is additive i.i.d. Gaussian. In this case, the source uses generalized dirty paper coding (GDPC), i.e., DPC combined with partial state cancellation, when only the source is informed, and DPC alone when both the source and the relay are informed. It appears that, even though it can not completely eliminate the effect of the SI (in contrast to the case of source and relay being informed), GDPC is particularly useful when only the source is informed.
Multi-Sensor Fusion Method using Dynamic Bayesian Network for Precise Vehicle Localization and Road Matching
Venue: arXiv cs.AI 2007
Year: 2007

This paper presents a multi-sensor fusion strategy for a novel road-matching method designed to support real-time navigational features within advanced driving-assistance systems. Managing multihypotheses is a useful strategy for the road-matching problem. The multi-sensor fusion and multi-modal estimation are realized using Dynamical Bayesian Network. Experimental results, using data from Antilock Braking System (ABS) sensors, a differential Global Positioning System (GPS) receiver and an accurate digital roadmap, illustrate the performances of this approach, especially in ambiguous situations.
Efficient Tabling Mechanisms for Transaction Logic Programs
Venue: arXiv cs.LO 2007
Year: 2007

In this paper we present efficient evaluation algorithms for the Horn Transaction Logic (a generalization of the regular Horn logic programs with state updates). We present two complementary methods for optimizing the implementation of Transaction Logic. The first method is based on tabling and we modified the proof theory to table calls and answers on states (practically, equivalent to dynamic programming). The call-answer table is indexed on the call and a signature of the state in which the call was made. The answer columns contain the answer unification and a signature of the state after the call was executed. The states are signed efficiently using a technique based on tries and counting. The second method is based on incremental evaluation and it applies when the data oracle contains derived relations. The deletions and insertions (executed in the transaction oracle) change the state of the database. Using the heuristic of inertia (only a part of the state changes in response to elementary updates), most of the time it is cheaper to compute only the changes in the state than to recompute the entire state from scratch. The two methods are complementary by the fact that the first method optimizes the evaluation when a call is repeated in the same state, and the second method optimizes the evaluation of a new state when a call-state pair is not found by the tabling mechanism (i.e. the first method). The proof theory of Transaction Logic with the application of tabling and incremental evaluation is sound and complete with respect to its model theory.
Bregman Voronoi Diagrams: Properties, Algorithms and Applications
Venue: arXiv cs.CG 2007
Year: 2007

The Voronoi diagram of a finite set of objects is a fundamental geometric structure that subdivides the embedding space into regions, each region consisting of the points that are closer to a given object than to the others. We may define many variants of Voronoi diagrams depending on the class of objects, the distance functions and the embedding space. In this paper, we investigate a framework for defining and building Voronoi diagrams for a broad class of distance functions called Bregman divergences. Bregman divergences include not only the traditional (squared) Euclidean distance but also various divergence measures based on entropic functions. Accordingly, Bregman Voronoi diagrams allow to define information-theoretic Voronoi diagrams in statistical parametric spaces based on the relative entropy of distributions. We define several types of Bregman diagrams, establish correspondences between those diagrams (using the Legendre transformation), and show how to compute them efficiently. We also introduce extensions of these diagrams, e.g. k-order and k-bag Bregman Voronoi diagrams, and introduce Bregman triangulations of a set of points and their connexion with Bregman Voronoi diagrams. We show that these triangulations capture many of the properties of the celebrated Delaunay triangulation. Finally, we give some applications of Bregman Voronoi diagrams which are of interest in the context of computational geometry and machine learning.
Autoencoder, Principal Component Analysis and Support Vector Regression for Data Imputation
Venue: arXiv cs.AI 2007
Year: 2007

Data collection often results in records that have missing values or variables. This investigation compares 3 different data imputation models and identifies their merits by using accuracy measures. Autoencoder Neural Networks, Principal components and Support Vector regression are used for prediction and combined with a genetic algorithm to then impute missing variables. The use of PCA improves the overall performance of the autoencoder network while the use of support vector regression shows promising potential for future investigation. Accuracies of up to 97.4 % on imputation of some of the variables were achieved.
Non-Blocking Signature of very large SOAP Messages
Venue: arXiv cs.DC 2007
Year: 2007

Data transfer and staging services are common components in Grid-based, or more generally, in service-oriented applications. Security mechanisms play a central role in such services, especially when they are deployed in sensitive application fields like e-health. The adoption of WS-Security and related standards to SOAP-based transfer services is, however, problematic as a straightforward adoption of SOAP with MTOM introduces considerable inefficiencies in the signature generation process when large data sets are involved. This paper proposes a non-blocking, signature generation approach enabling a stream-like processing with considerable performance enhancements.
Query Evaluation in P2P Systems of Taxonomy-based Sources: Algorithms, Complexity, and Optimizations
Venue: arXiv cs.DB 2007
Year: 2007

In this study, we address the problem of answering queries over a peer-to-peer system of taxonomy-based sources. A taxonomy states subsumption relationships between negation-free DNF formulas on terms and negation-free conjunctions of terms. To the end of laying the foundations of our study, we first consider the centralized case, deriving the complexity of the decision problem and of query evaluation. We conclude by presenting an algorithm that is efficient in data complexity and is based on hypergraphs. More expressive forms of taxonomies are also investigated, which however lead to intractability. We then move to the distributed case, and introduce a logical model of a network of taxonomy-based sources. On such network, a distributed version of the centralized algorithm is then presented, based on a message passing paradigm, and its correctness is proved. We finally discuss optimization issues, and relate our work to the literature.
Series which are both max-plus and min-plus rational are unambiguous
Venue: arXiv cs.DM 2007
Year: 2007

Consider partial maps from the free monoid into the field of real numbers with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure to build an unambiguous automaton from a max-plus automaton and a min-plus one that recognize the same series.
Weighted Matching in the Semi-Streaming Model
Venue: arXiv cs.DM 2007
Year: 2007

We reduce the best known approximation ratio for finding a weighted matching of a graph using a one-pass semi-streaming algorithm from 5.828 to 5.585. The semi-streaming model forbids random access to the input and restricts the memory to O(n*polylog(n)) bits. It was introduced by Muthukrishnan in 2003 and is appropriate when dealing with massive graphs.
Mutual information for the selection of relevant variables in spectrometric nonlinear modelling
Venue: arXiv cs.LG 2007
Year: 2007

Data from spectrophotometers form vectors of a large number of exploitable variables. Building quantitative models using these variables most often requires using a smaller set of variables than the initial one. Indeed, a too large number of input variables to a model results in a too large number of parameters, leading to overfitting and poor generalization abilities. In this paper, we suggest the use of the mutual information measure to select variables from the initial set. The mutual information measures the information content in input variables with respect to the model output, without making any assumption on the model that will be used; it is thus suitable for nonlinear modelling. In addition, it leads to the selection of variables among the initial set, and not to linear or nonlinear combinations of them. Without decreasing the model performances compared to other variable projection methods, it allows therefore a greater interpretability of the results.
Representation of Functional Data in Neural Networks
Venue: arXiv cs.NE 2007
Year: 2007

Functional Data Analysis (FDA) is an extension of traditional data analysis to functional data, for example spectra, temporal series, spatio-temporal images, gesture recognition data, etc. Functional data are rarely known in practice; usually a regular or irregular sampling is known. For this reason, some processing is needed in order to benefit from the smooth character of functional data in the analysis methods. This paper shows how to extend the Radial-Basis Function Networks (RBFN) and Multi-Layer Perceptron (MLP) models to functional data inputs, in particular when the latter are known through lists of input-output pairs. Various possibilities for functional processing are discussed, including the projection on smooth bases, Functional Principal Component Analysis, functional centering and reduction, and the use of differential operators. It is shown how to incorporate these functional processing into the RBFN and MLP models. The functional approach is illustrated on a benchmark of spectrometric data analysis.
Classification of Images Using Support Vector Machines
Venue: arXiv cs.LG 2007
Year: 2007

Support Vector Machines (SVMs) are a relatively new supervised classification technique to the land cover mapping community. They have their roots in Statistical Learning Theory and have gained prominence because they are robust, accurate and are effective even when using a small training sample. By their nature SVMs are essentially binary classifiers, however, they can be adopted to handle the multiple classification tasks common in remote sensing studies. The two approaches commonly used are the One-Against-One (1A1) and One-Against-All (1AA) techniques. In this paper, these approaches are evaluated in as far as their impact and implication for land cover mapping. The main finding from this research is that whereas the 1AA technique is more predisposed to yielding unclassified and mixed pixels, the resulting classification accuracy is not significantly different from 1A1 approach. It is the authors conclusions that ultimately the choice of technique adopted boils down to personal preference and the uniqueness of the dataset at hand.
Adaptive Investment Strategies For Periodic Environments
Venue: arXiv cs.CE 2007
Year: 2007

In this paper, we present an adaptive investment strategy for environments with periodic returns on investment. In our approach, we consider an investment model where the agent decides at every time step the proportion of wealth to invest in a risky asset, keeping the rest of the budget in a risk-free asset. Every investment is evaluated in the market via a stylized return on investment function (RoI), which is modeled by a stochastic process with unknown periodicities and levels of noise. For comparison reasons, we present two reference strategies which represent the case of agents with zero-knowledge and complete-knowledge of the dynamics of the returns. We consider also an investment strategy based on technical analysis to forecast the next return by fitting a trend line to previous received returns. To account for the performance of the different strategies, we perform some computer experiments to calculate the average budget that can be obtained with them over a certain number of time steps. To assure for fair comparisons, we first tune the parameters of each strategy. Afterwards, we compare the performance of these strategies for RoIs with different periodicities and levels of noise.
The Extended Edit Distance Metric
Venue: arXiv cs.IR 2007
Year: 2007

Similarity search is an important problem in information retrieval. This similarity is based on a distance. Symbolic representation of time series has attracted many researchers recently, since it reduces the dimensionality of these high dimensional data objects. We propose a new distance metric that is applied to symbolic data objects and we test it on time series data bases in a classification task. We compare it to other distances that are well known in the literature for symbolic data objects. We also prove, mathematically, that our distance is metric.
Z4-linear Hadamard and extended perfect codes
Venue: arXiv cs.IT 2007
Year: 2007

If $N=2^k > 8$ then there exist exactly $[(k-1)/2]$ pairwise nonequivalent $Z_4$-linear Hadamard $(N,2N,N/2)$-codes and $[(k+1)/2]$ pairwise nonequivalent $Z_4$-linear extended perfect $(N,2^N/2N,4)$-codes. A recurrent construction of $Z_4$-linear Hadamard codes is given.
Optimising the topology of complex neural networks
Venue: arXiv cs.NE 2007
Year: 2007

In this paper, we study instances of complex neural networks, i.e. neural netwo rks with complex topologies. We use Self-Organizing Map neural networks whose n eighbourhood relationships are defined by a complex network, to classify handwr itten digits. We show that topology has a small impact on performance and robus tness to neuron failures, at least at long learning times. Performance may howe ver be increased (by almost 10%) by artificial evolution of the network topo logy. In our experimental conditions, the evolved networks are more random than their parents, but display a more heterogeneous degree distribution.
On the role of autocorrelations in texts
Venue: arXiv cs.CL 2007
Year: 2007

The task of finding a criterion allowing to distinguish a text from an arbitrary set of words is rather relevant in itself, for instance, in the aspect of development of means for internet-content indexing or separating signals and noise in communication channels. The Zipf law is currently considered to be the most reliable criterion of this kind [3]. At any rate, conventional stochastic word sets do not meet this law. The present paper deals with one of possible criteria based on the determination of the degree of data compression.
On the fractal nature of mutual relevance sequences in the Internet news message flows
Venue: arXiv cs.CL 2007
Year: 2007

In the task of information retrieval the term relevance is taken to mean formal conformity of a document given by the retrieval system to user's information query. As a rule, the documents found by the retrieval system should be submitted to the user in a certain order. Therefore, a retrieval perceived as a selection of documents formally solving the user's query, should be supplemented with a certain procedure of processing a relevant set. It would be natural to introduce a quantitative measure of document conformity to query, i.e. the relevance measure. Since no single rule exists for the determination of the relevance measure, we shall consider two of them which are the simplest in our opinion. The proposed approach does not suppose any restrictions and can be applied to other relevance measures.
Constructing a uniform plane-filling path in the ternary heptagrid of the hyperbolic plane
Venue: arXiv cs.CG 2007
Year: 2007

In this paper, we distinguish two levels for the plane-filling property. We consider a simple and a strong one. In this paper, we give the construction which proves that the simple plane-filling property also holds for the hyperbolic plane. The plane-filling property was established for the Euclidean plane by J. Kari, in 1994, in the strong version.