OpenRaiser/Intern-Atlas huggingface dataset:
Subword Complexity and k-Synchronization
Venue: arXiv cs.FL 2012
Year: 2012

We show that the subword complexity function p_x(n), which counts the number of distinct factors of length n of a sequence x, is k-synchronized in the sense of Carpi if x is k-automatic. As an application, we generalize recent results of Goldstein. We give analogous results for the number of distinct factors of length n that are primitive words or powers. In contrast, we show that the function that counts the number of unbordered factors of length n is not necessarily k-synchronized for k-automatic sequences.
A Precise Information Flow Measure from Imprecise Probabilities
Venue: arXiv cs.CR 2012
Year: 2012

Dempster-Shafer theory of imprecise probabilities has proved useful to incorporate both nonspecificity and conflict uncertainties in an inference mechanism. The traditional Bayesian approach cannot differentiate between the two, and is unable to handle non-specific, ambiguous, and conflicting information without making strong assumptions. This paper presents a generalization of a recent Bayesian-based method of quantifying information flow in Dempster-Shafer theory. The generalization concretely enhances the original method removing all its weaknesses that are highlighted in this paper. In so many words, our generalized method can handle any number of secret inputs to a program, it enables the capturing of an attacker's beliefs in all kinds of sets (singleton or not), and it supports a new and precise quantitative information flow measure whose reported flow results are plausible in that they are bounded by the size of a program's secret input, and can be easily associated with the exhaustive search effort needed to uncover a program's secret information, unlike the results reported by the original metric.
On bilinear algorithms for multiplication in quaternion algebras
Venue: arXiv cs.CC 2012
Year: 2012

We show that the bilinear complexity of multiplication in a non-split quaternion algebra over a field of characteristic distinct from 2 is 8. This question is motivated by the problem of characterising algebras of almost minimal rank studied by Blaeser and de Voltaire in [1]. This paper is a translation of a report submitted by the author to the XI international seminar "Discrete mathematics and applications" (in Russian).
Optimization of Real, Hermitian Quadratic Forms: Real, Complex Hopfield-Amari Neural Network
Venue: arXiv cs.NE 2012
Year: 2012

In this research paper, the problem of optimization of quadratic forms associated with the dynamics of Hopfield-Amari neural network is considered. An elegant (and short) proof of the states at which local/global minima of quadratic form are attained is provided. A theorem associated with local/global minimization of quadratic energy function using the Hopfield-Amari neural network is discussed. The results are generalized to a "Complex Hopfield neural network" dynamics over the complex hypercube (using a "complex signum function"). It is also reasoned through two theorems that there is no loss of generality in assuming the threshold vector to be a zero vector in the case of real as well as a "Complex Hopfield neural network". Some structured quadratic forms like Toeplitz form and Complex Toeplitz form are discussed.
Geometric WOM codes and coding strategies for multilevel flash memories
Venue: arXiv cs.IT 2012
Year: 2012

This paper investigates the design and application of write-once memory (WOM) codes for flash memory storage. Using ideas from Merkx ('84), we present a construction of WOM codes based on finite Euclidean geometries over $\mathbb{F}_2$. This construction yields WOM codes with new parameters and provides insight into the criterion that incidence structures should satisfy to give rise to good codes. We also analyze methods of adapting binary WOM codes for use on multilevel flash cells. In particular, we give two strategies based on different rewrite objectives. A brief discussion of the average-write performance of these strategies, as well as concatenation methods for WOM codes is also provided.
Learning mixtures of spherical Gaussians: moment methods and spectral decompositions
Venue: arXiv cs.LG 2012
Year: 2012

This work provides a computationally efficient and statistically consistent moment-based estimator for mixtures of spherical Gaussians. Under the condition that component means are in general position, a simple spectral decomposition technique yields consistent parameter estimates from low-order observable moments, without additional minimum separation assumptions needed by previous computationally efficient estimation procedures. Thus computational and information-theoretic barriers to efficient estimation in mixture models are precluded when the mixture components have means in general position and spherical covariances. Some connections are made to estimation problems related to independent component analysis.
MAINWAVE: Multi Agents and Issues Negotiation for Web using Alliance Virtual Engine
Venue: arXiv cs.MA 2012
Year: 2012

This paper showcases an improved architecture for a complete negotiation system that permits multi party multi issue negotiation. The concepts of multithreading and concurrency has been utilized to perform parallel execution. The negotiation history has been implemented that stores all the records of the messages exchanged for every successful and rejected negotiation process and implements the concepts of artificial intelligence in determination of proper weights for a valid negotiation mechanism. The issues are arranged in a hierarchical pattern so as to simplify the representation and priorities are assigned to each issue, which amounts to its relative importance. There is refinement of utilities by consideration of the non-functional attributes. So as to avoid overloading of the system, a maximum number of parties are allowed to participate in the entire mechanism and if more parties arrive, they're put into a waiting queue in accordance to certain criteria such as the first come first serve or the relative priorities. This helps in fault tolerance. It also supports the formation of alliances among the various parties while carrying out a negotiation.
CAPIR: Collaborative Action Planning with Intention Recognition
Venue: arXiv cs.AI 2012
Year: 2012

We apply decision theoretic techniques to construct non-player characters that are able to assist a human player in collaborative games. The method is based on solving Markov decision processes, which can be difficult when the game state is described by many variables. To scale to more complex games, the method allows decomposition of a game task into subtasks, each of which can be modelled by a Markov decision process. Intention recognition is used to infer the subtask that the human is currently performing, allowing the helper to assist the human in performing the correct task. Experiments show that the method can be effective, giving near-human level performance in helping a human in a collaborative game.
An Additive Model View to Sparse Gaussian Process Classifier Design
Venue: arXiv cs.LG 2012
Year: 2012

We consider the problem of designing a sparse Gaussian process classifier (SGPC) that generalizes well. Viewing SGPC design as constructing an additive model like in boosting, we present an efficient and effective SGPC design method to perform a stage-wise optimization of a predictive loss function. We introduce new methods for two key components viz., site parameter estimation and basis vector selection in any SGPC design. The proposed adaptive sampling based basis vector selection method aids in achieving improved generalization performance at a reduced computational cost. This method can also be used in conjunction with any other site parameter estimation methods. It has similar computational and storage complexities as the well-known information vector machine and is suitable for large datasets. The hyperparameters can be determined by optimizing a predictive loss function. The experimental results show better generalization performance of the proposed basis vector selection method on several benchmark datasets, particularly for relatively smaller basis vector set sizes or on difficult datasets.
Directed Time Series Regression for Control
Venue: arXiv cs.LG 2012
Year: 2012

We propose directed time series regression, a new approach to estimating parameters of time-series models for use in certainty equivalent model predictive control. The approach combines merits of least squares regression and empirical optimization. Through a computational study involving a stochastic version of a well known inverted pendulum balancing problem, we demonstrate that directed time series regression can generate significant improvements in controller performance over either of the aforementioned alternatives.
The Social Will-Testing Game and its Solution
Venue: arXiv cs.GT 2012
Year: 2012

We examine a two-person game we call Will-Testing in which the strategy space for both players is a real number. It has no equilibrium. When an infinitely large set of players plays this in all possible pairings, there is an equilibrium for the distribution of strategies which requires all players to use different strategies. We conjecture this solution could underlie some phenomena (like pecking orders) observed in animals.
Outage Probability and Outage-Based Robust Beamforming for MIMO Interference Channels with Imperfect Channel State Information
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, the outage probability and outage-based beam design for multiple-input multiple-output (MIMO) interference channels are considered. First, closed-form expressions for the outage probability in MIMO interference channels are derived under the assumption of Gaussian-distributed channel state information (CSI) error, and the asymptotic behavior of the outage probability as a function of several system parameters is examined by using the Chernoff bound. It is shown that the outage probability decreases exponentially with respect to the quality of CSI measured by the inverse of the mean square error of CSI. Second, based on the derived outage probability expressions, an iterative beam design algorithm for maximizing the sum outage rate is proposed. Numerical results show that the proposed beam design algorithm yields better sum outage rate performance than conventional algorithms such as interference alignment developed under the assumption of perfect CSI.
Discrete Elastic Inner Vector Spaces with Application in Time Series and Sequence Mining
Venue: arXiv cs.LG 2012
Year: 2012

This paper proposes a framework dedicated to the construction of what we call discrete elastic inner product allowing one to embed sets of non-uniformly sampled multivariate time series or sequences of varying lengths into inner product space structures. This framework is based on a recursive definition that covers the case of multiple embedded time elastic dimensions. We prove that such inner products exist in our general framework and show how a simple instance of this inner product class operates on some prospective applications, while generalizing the Euclidean inner product. Classification experimentations on time series and symbolic sequences datasets demonstrate the benefits that we can expect by embedding time series or sequences into elastic inner spaces rather than into classical Euclidean spaces. These experiments show good accuracy when compared to the euclidean distance or even dynamic programming algorithms while maintaining a linear algorithmic complexity at exploitation stage, although a quadratic indexing phase beforehand is required.
Decentralized Data Fusion and Active Sensing with Mobile Sensors for Modeling and Predicting Spatiotemporal Traffic Phenomena
Venue: arXiv cs.LG 2012
Year: 2012

The problem of modeling and predicting spatiotemporal traffic phenomena over an urban road network is important to many traffic applications such as detecting and forecasting congestion hotspots. This paper presents a decentralized data fusion and active sensing (D2FAS) algorithm for mobile sensors to actively explore the road network to gather and assimilate the most informative data for predicting the traffic phenomenon. We analyze the time and communication complexity of D2FAS and demonstrate that it can scale well with a large number of observations and sensors. We provide a theoretical guarantee on its predictive performance to be equivalent to that of a sophisticated centralized sparse approximation for the Gaussian process (GP) model: The computation of such a sparse approximate GP model can thus be parallelized and distributed among the mobile sensors (in a Google-like MapReduce paradigm), thereby achieving efficient and scalable prediction. We also theoretically guarantee its active sensing performance that improves under various practical environmental conditions. Empirical evaluation on real-world urban road network data shows that our D2FAS algorithm is significantly more time-efficient and scalable than state-of-the-art centralized algorithms while achieving comparable predictive performance.
Data Collection through Vehicular Sensor Networks by using TCDGP
Venue: arXiv cs.NI 2012
Year: 2012

Now a days Many car manufacturers are planning to install wireless connectivity equipment in their vehicles to enable communications with "roadside base station" and also between vehicles, for the purposes of safety, driving assistance, and entertainment. One distinct feature is that vehicles are highly mobile, with speed up to 30 m/s, though their mobility patterns are more predictable than those of nodes in Mobile Ad-hoc Networks (MANET) due to the constraints imposed by road, speed limits, and commuting habits. Therefore, these networks require specific solutions and identify a novel research area, i.e., Vehicular Ad-hoc Networks (VANET). In this paper, we focus on a particular VSN architecture, where the ad hoc network is operated by a telecommunication/service provider to combine non-valuable individual sensed data and extract from them effective feedbacks about the situation of the road in a geographical area. In operated VSNs, providers tend to reduce the traffic load on their network, using the free-frequency communication medium (IEEE 802.11p, for example). To do so, we propose TCDGP (Tree Clustered Data Gathering Protocol), a cross layer protocol based on hierarchical and geographical data collection, aggregation and dissemination mechanisms. We analyze the performances of our solution using a simulation environment and realistic mobility models. We demonstrate the feasibility of such solution and show that TCDGP offers the operator precious information without overloading his network.
Collusion resistant self-healing key distribution in mobile wireless networks
Venue: arXiv cs.NI 2012
Year: 2012

A fundamental concern of any secure group communication system is key management and wireless environments create new challenges. One core requirement in these emerging networks is self-healing. In systems where users can be offline and miss updates, self-healing allows a user to recover lost session keys and get back into the secure communication without putting extra burden on the group manager. Clearly, self-healing must only be available to authorized users. This paper fixes the problem of collusion attack in an existing self-healing key distribution scheme and provides a highly efficient scheme as compared to the existing works. It is computationally secure, resists collusion attacks made between newly joined users and revoked users and achieves forward and backward secrecy. Our security analysis is in an appropriate security model. Unlike the existing constructions, our scheme does not forbid revoked users from rejoining in later sessions.
A New Scale for Attribute Dependency in Large Database Systems
Venue: arXiv cs.IR 2012
Year: 2012

Large, data centric applications are characterized by its different attributes. In modern day, a huge majority of the large data centric applications are based on relational model. The databases are collection of tables and every table consists of numbers of attributes. The data is accessed typically through SQL queries. The queries that are being executed could be analyzed for different types of optimizations. Analysis based on different attributes used in a set of query would guide the database administrators to enhance the speed of query execution. A better model in this context would help in predicting the nature of upcoming query set. An effective prediction model would guide in different applications of database, data warehouse, data mining etc. In this paper, a numeric scale has been proposed to enumerate the strength of associations between independent data attributes. The proposed scale is built based on some probabilistic analysis of the usage of the attributes in different queries. Thus this methodology aims to predict future usage of attributes based on the current usage.
Learning Parameterized Skills
Venue: arXiv cs.LG 2012
Year: 2012

We introduce a method for constructing skills capable of solving tasks drawn from a distribution of parameterized reinforcement learning problems. The method draws example tasks from a distribution of interest and uses the corresponding learned policies to estimate the topology of the lower-dimensional piecewise-smooth manifold on which the skill policies lie. This manifold models how policy parameters change as task parameters vary. The method identifies the number of charts that compose the manifold and then applies non-linear regression in each chart to construct a parameterized skill by predicting policy parameters from task parameters. We evaluate our method on an underactuated simulated robotic arm tasked with learning to accurately throw darts at a parameterized target location.
Deep Lambertian Networks
Venue: arXiv cs.CV 2012
Year: 2012

Visual perception is a challenging problem in part due to illumination variations. A possible solution is to first estimate an illumination invariant representation before using it for recognition. The object albedo and surface normals are examples of such representations. In this paper, we introduce a multilayer generative model where the latent variables include the albedo, surface normals, and the light source. Combining Deep Belief Nets with the Lambertian reflectance assumption, our model can learn good priors over the albedo from 2D images. Illumination variations can be explained by changing only the lighting latent variable in our model. By transferring learned knowledge from similar objects, albedo and surface normals estimation from a single image is possible in our model. Experiments demonstrate that our model is able to generalize as well as improve over standard baselines in one-shot face recognition.
Agglomerative Bregman Clustering
Venue: arXiv cs.LG 2012
Year: 2012

This manuscript develops the theory of agglomerative clustering with Bregman divergences. Geometric smoothing techniques are developed to deal with degenerate clusters. To allow for cluster models based on exponential families with overcomplete representations, Bregman divergences are developed for nondifferentiable convex functions.
A Sampling-based Tool for Plagiarism Detection in Student Texts
Venue: arXiv cs.CY 2012
Year: 2012

This paper introduces AntiPlag, an advanced plagiarism detection tool intended for use on student texts. It is capable of both hermetic detection that scrutinizes only local collections of documents (other students' texts and lecture materials, for example) and web plagiarism detection, in which the aim is at identifying instances of plagiarism that have been sourced from the Internet. The main feature of the system is the sampling-based web plagiarism detection, a novel approach to plagiarism detection that is based on combining web and hermetic search technologies. The system uses standard web search engines to locate documents on the Internet that might have been used as sources of plagiarism by the writer of a text. During this sampling phase, the suspected sources are downloaded, converted to ASCII text and saved to the local database so that they can be later processed by using the hermetic detection methods. We evaluated the system by using a test set that contained instances of verbatim copying as well as texts in which plagiarism was concealed by minor editing, replacing words with synonyms and by paraphrasing. We compared the results achieved by AntiPlag to an earlier evaluation study of four web plagiarism detection systems, SafeAssignment, TurnitIn, EVE2 and Plagiarism-Finder. AntiPlag performed better than any of these systems, achieving the accuracy 95.8% over all the test items.
Cutset Sampling with Likelihood Weighting
Venue: arXiv cs.AI 2012
Year: 2012

The paper analyzes theoretically and empirically the performance of likelihood weighting (LW) on a subset of nodes in Bayesian networks. The proposed scheme requires fewer samples to converge due to reduction in sampling variance. The method exploits the structure of the network to bound the complexity of exact inference used to compute sampling distributions, similar to Gibbs cutset sampling. Yet, the extension of the previosly proposed cutset sampling principles to likelihood weighting is non-trivial due to differences in the sampling processes of Gibbs sampler and LW. We demonstrate empirically that likelihood weighting on a cutset (LWLC) is effective time-wise and has a lower rejection rate than LW when applied to networks with many deterministic probabilities. Finally, we show that the performance of likelihood weighting on a cutset can be improved further by caching computed sampling distributions and, consequently, learning 'zeros' of the target distribution.
An Efficient Triplet-based Algorithm for Evidential Reasoning
Venue: arXiv cs.AI 2012
Year: 2012

Linear-time computational techniques have been developed for combining evidence which is available on a number of contending hypotheses. They offer a means of making the computation-intensive calculations involved more efficient in certain circumstances. Unfortunately, they restrict the orthogonal sum of evidential functions to the dichotomous structure applies only to elements and their complements. In this paper, we present a novel evidence structure in terms of a triplet and a set of algorithms for evidential reasoning. The merit of this structure is that it divides a set of evidence into three subsets, distinguishing trivial evidential elements from important ones focusing some particular elements. It avoids the deficits of the dichotomous structure in representing the preference of evidence and estimating the basic probability assignment of evidence. We have established a formalism for this structure and the general formulae for combining pieces of evidence in the form of the triplet, which have been theoretically justified.
Non-Minimal Triangulations for Mixed Stochastic/Deterministic Graphical Models
Venue: arXiv cs.AI 2012
Year: 2012

We observe that certain large-clique graph triangulations can be useful to reduce both computational and space requirements when making queries on mixed stochastic/deterministic graphical models. We demonstrate that many of these large-clique triangulations are non-minimal and are thus unattainable via the variable elimination algorithm. We introduce ancestral pairs as the basis for novel triangulation heuristics and prove that no more than the addition of edges between ancestral pairs need be considered when searching for state space optimal triangulations in such graphs. Empirical results on random and real world graphs show that the resulting triangulations that yield significant speedups are almost always non-minimal. We also give an algorithm and correctness proof for determining if a triangulation can be obtained via elimination, and we show that the decision problem associated with finding optimal state space triangulations in this mixed stochastic/deterministic setting is NP-complete.