OpenRaiser/Intern-Atlas huggingface dataset:
Dyna-Style Planning with Linear Function Approximation and Prioritized Sweeping
Venue: arXiv cs.AI 2012
Year: 2012

We consider the problem of efficiently learning optimal control policies and value functions over large state spaces in an online setting in which estimates must be available after each interaction with the world. This paper develops an explicitly model-based approach extending the Dyna architecture to linear function approximation. Dynastyle planning proceeds by generating imaginary experience from the world model and then applying model-free reinforcement learning algorithms to the imagined state transitions. Our main results are to prove that linear Dyna-style planning converges to a unique solution independent of the generating distribution, under natural conditions. In the policy evaluation setting, we prove that the limit point is the least-squares (LSTD) solution. An implication of our results is that prioritized-sweeping can be soundly extended to the linear approximation case, backing up to preceding features rather than to preceding states. We introduce two versions of prioritized sweeping with linear Dyna and briefly illustrate their performance empirically on the Mountain Car and Boyan Chain problems.
A two-step Recommendation Algorithm via Iterative Local Least Squares
Venue: arXiv cs.IR 2012
Year: 2012

Recommender systems can change our life a lot and help us select suitable and favorite items much more conveniently and easily. As a consequence, various kinds of algorithms have been proposed in last few years to improve the performance. However, all of them face one critical problem: data sparsity. In this paper, we proposed a two-step recommendation algorithm via iterative local least squares (ILLS). Firstly, we obtain the ratings matrix which is constructed via users' behavioral records, and it is normally very sparse. Secondly, we preprocess the "ratings" matrix through ProbS which can convert the sparse data to a dense one. Then we use ILLS to estimate those missing values. Finally, the recommendation list is generated. Experimental results on the three datasets: MovieLens, Netflix, RYM, suggest that the proposed method can enhance the algorithmic accuracy of AUC. Especially, it performs much better in dense datasets. Furthermore, since this methods can improve those missing value more accurately via iteration which might show light in discovering those inactive users' purchasing intention and eventually solving cold-start problem.
A Complete Axiomatization of Quantified Differential Dynamic Logic for Distributed Hybrid Systems
Venue: arXiv cs.LO 2012
Year: 2012

We address a fundamental mismatch between the combinations of dynamics that occur in cyber-physical systems and the limited kinds of dynamics supported in analysis. Modern applications combine communication, computation, and control. They may even form dynamic distributed networks, where neither structure nor dimension stay the same while the system follows hybrid dynamics, i.e., mixed discrete and continuous dynamics. We provide the logical foundations for closing this analytic gap. We develop a formal model for distributed hybrid systems. It combines quantified differential equations with quantified assignments and dynamic dimensionality-changes. We introduce a dynamic logic for verifying distributed hybrid systems and present a proof calculus for this logic. This is the first formal verification approach for distributed hybrid systems. We prove that our calculus is a sound and complete axiomatization of the behavior of distributed hybrid systems relative to quantified differential equations. In our calculus we have proven collision freedom in distributed car control even when an unbounded number of new cars may appear dynamically on the road.
Performance Improvement of VOD System by Policy Based Traffic Handle
Venue: arXiv cs.NI 2012
Year: 2012

The distributed system use to enhance the performance of all types of multimedia service in the next generation network. The packet loss occurs in the video on demand system due to delay and huge traffic load from the both sides of client request and server response. It's bring a real challenge to the researcher how to minimize the traffic load in the video on demand system to provide better utilization of the available bandwidth in the very race situation. The normal client server type architecture can't solve the huge client requirement. In this work, I have used number of remote servers that partly shears the total load in the video on demand system on behalf of the total system load. This work presents the scenario of controlling the traffic load in the localization wise sub domain that gives good impact to control the traffic in the whole distributed system. The user increased rapidly in the network it posed heavy load to the video servers. The requested clients, servers are all distributed in nature and the data stream delivered according to client request. In this work presents the performance of the video on demand server by policy based traffic handle, at real time with respect to incoming multi rate traffic pattern.
Computation of Difference Groebner Bases
Venue: arXiv cs.SC 2012
Year: 2012

To compute difference Groebner bases of ideals generated by linear polynomials we adopt to difference polynomial rings the involutive algorithm based on Janet-like division. The algorithm has been implemented in Maple in the form of the package LDA (Linear Difference Algebra) and we describe the main features of the package. Its applications are illustrated by generation of finite difference approximations to linear partial differential equations and by reduction of Feynman integrals. We also present the algorithm for an ideal generated by a finite set of nonlinear difference polynomials. If the algorithm terminates, then it constructs a Groebner basis of the ideal.
A Novel Approach for Protein Structure Prediction
Venue: arXiv cs.LG 2012
Year: 2012

The idea of this project is to study the protein structure and sequence relationship using the hidden markov model and artificial neural network. In this context we have assumed two hidden markov models. In first model we have taken protein secondary structures as hidden and protein sequences as observed. In second model we have taken protein sequences as hidden and protein structures as observed. The efficiencies for both the hidden markov models have been calculated. The results show that the efficiencies of first model is greater that the second one .These efficiencies are cross validated using artificial neural network. This signifies the importance of protein secondary structures as the main hidden controlling factors due to which we observe a particular amino acid sequence. This also signifies that protein secondary structure is more conserved in comparison to amino acid sequence.
Functional Currents : a new mathematical tool to model and analyse functional shapes
Venue: arXiv cs.CG 2012
Year: 2012

This paper introduces the concept of functional current as a mathematical framework to represent and treat functional shapes, i.e. sub-manifold supported signals. It is motivated by the growing occurrence, in medical imaging and computational anatomy, of what can be described as geometrico-functional data, that is a data structure that involves a deformable shape (roughly a finite dimensional sub manifold) together with a function defined on this shape taking value in another manifold. Indeed, if mathematical currents have already proved to be very efficient theoretically and numerically to model and process shapes as curves or surfaces, they are limited to the manipulation of purely geometrical objects. We show that the introduction of the concept of functional currents offers a genuine solution to the simultaneous processing of the geometric and signal information of any functional shape. We explain how functional currents can be equipped with a Hilbertian norm mixing geometrical and functional content of functional shapes nicely behaving under geometrical and functional perturbations and paving the way to various processing algorithms. We illustrate this potential on two problems: the redundancy reduction of functional shapes representations through matching pursuit schemes on functional currents and the simultaneous geometric and functional registration of functional shapes under diffeomorphic transport.
On the Complexity of Existential Positive Queries
Venue: arXiv cs.LO 2012
Year: 2012

We systematically investigate the complexity of model checking the existential positive fragment of first-order logic. In particular, for a set of existential positive sentences, we consider model checking where the sentence is restricted to fall into the set; a natural question is then to classify which sentence sets are tractable and which are intractable. With respect to fixed-parameter tractability, we give a general theorem that reduces this classification question to the corresponding question for primitive positive logic, for a variety of representations of structures. This general theorem allows us to deduce that an existential positive sentence set having bounded arity is fixed-parameter tractable if and only if each sentence is equivalent to one in bounded-variable logic. We then use the lens of classical complexity to study these fixed-parameter tractable sentence sets. We show that such a set can be NP-complete, and consider the length needed by a translation from sentences in such a set to bounded-variable logic; we prove superpolynomial lower bounds on this length using the theory of compilability, obtaining an interesting type of formula size lower bound. Overall, the tools, concepts, and results of this article set the stage for the future consideration of the complexity of model checking on more expressive logics.
Small-world topology of functional connectivity in randomly connected dynamical systems
Venue: arXiv cs.SI 2012
Year: 2012

Characterization of real-world complex systems increasingly involves the study of their topological structure using graph theory. Among global network properties, small-world property, consisting in existence of relatively short paths together with high clustering of the network, is one of the most discussed and studied. When dealing with coupled dynamical systems, links among units of the system are commonly quantified by a measure of pairwise statistical dependence of observed time series (functional connectivity). We argue that the functional connectivity approach leads to upwardly biased estimates of small-world characteristics (with respect to commonly used random graph models) due to partial transitivity of the accepted functional connectivity measures such as the correlation coefficient. In particular, this may lead to observation of small-world characteristics in connectivity graphs estimated from generic randomly connected dynamical systems. The ubiquity and robustness of the phenomenon is documented by an extensive parameter study of its manifestation in a multivariate linear autoregressive process, with discussion of the potential relevance for nonlinear processes and measures.
On the Bivariate Nakagami-$m$ Cumulative Distribution Function: Closed-form Expression and Applications
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we derive exact closed-form expressions for the bivariate Nakagami-$m$ cumulative distribution function (CDF) with positive integer fading severity index $m$ in terms of a class of hypergeometric functions. Particularly, we show that the bivariate Nakagami-$m$ CDF can be expressed as a finite sum of elementary functions and bivariate confluent hypergeometric $Φ_3$ functions. Direct applications which arise from the proposed closed-form expression are the outage probability (OP) analysis of a dual-branch selection combiner in correlated Nakagami-$m$ fading, or the calculation of the level crossing rate (LCR) and average fade duration (AFD) of a sampled Nakagami-$m$ fading envelope.
Data Hiding Techniques using number decompositions
Venue: arXiv cs.CR 2012
Year: 2012

Data hiding is the art of embedding data into digital media in a way such that the existence of data remains concealed from everyone except the intended recipient. In this paper, we discuss the various Least Significant Bit (LSB) data hiding techniques. We first look at the classical LSB data hiding technique and the method to embed secret data into cover media by bit manipulation. We also take a look at the data hiding technique by bit plane decomposition based on Fibonacci numbers. This method generates more bit planes which allows users to embed more data into the cover image without causing significant distortion. We also discuss the data hiding technique based on bit plane decomposition by prime numbers and natural numbers. These methods are based on mapping the sequence of image bit size to the decomposed bit number to hide the intended information. Finally we present a comparative analysis of these data hiding techniques.
On Epsilon-Nets, Distance Oracles, and Metric Embeddings
Venue: arXiv cs.DS 2012
Year: 2012

We give two new applications of an observation from \cite{ADFGW11}. The first is an almost linear sized constant time data structure for reporting very large distances in undirected graphs. The second is a generic transformation of results about $\ell_1$-embeddability of metrics to a setting, where we are interested in preservation of large distances only.
Succinct Representations for Abstract Interpretation
Venue: arXiv cs.PL 2012
Year: 2012

Abstract interpretation techniques can be made more precise by distinguishing paths inside loops, at the expense of possibly exponential complexity. SMT-solving techniques and sparse representations of paths and sets of paths avoid this pitfall. We improve previously proposed techniques for guided static analysis and the generation of disjunctive invariants by combining them with techniques for succinct representations of paths and symbolic representations for transitions based on static single assignment. Because of the non-monotonicity of the results of abstract interpretation with widening operators, it is difficult to conclude that some abstraction is more precise than another based on theoretical local precision results. We thus conducted extensive comparisons between our new techniques and previous ones, on a variety of open-source packages.
Joint Transmit Precoding for the Relay Interference Broadcast Channel
Venue: arXiv cs.IT 2012
Year: 2012

Relays in cellular systems are interference limited. The highest end-to-end sum rates are achieved when the relays are jointly optimized with the transmit strategy. Unfortunately, interference couples the links together making joint optimization challenging. Further, the end-to-end multi-hop performance is sensitive to rate mismatch, when some links have a dominant first link while others have a dominant second link. This paper proposes an algorithm for designing the linear transmit precoders at the transmitters and relays of the relay interference broadcast channel, a generic model for relay-based cellular systems, to maximize the end-to-end sum-rates. First, the relays are designed to maximize the second-hop sum-rates. Next, approximate end-to-end rates that depend on the time-sharing fraction and the second-hop rates are used to formulate a sum-utility maximization problem for designing the transmitters. This problem is solved by iteratively minimizing the weighted sum of mean square errors. Finally, the norms of the transmit precoders at the transmitters are adjusted to eliminate rate mismatch. The proposed algorithm allows for distributed implementation and has fast convergence. Numerical results show that the proposed algorithm outperforms a reasonable application of single-hop interference management strategies separately on two hops.
Pricing of insurance policies against cloud storage price rises
Venue: arXiv cs.OH 2012
Year: 2012

When a company migrates to cloud storage, the way back is neither easy nor cheap. The company is then locked up in the storage contract and exposed to upward market prices, which reduce the company's profit and may even bring it below zero. We propose a protection means based on an insurance contract, by which the cloud purchaser is indemnified when the current storage price exceeds a pre-defined threshold. By applying the financial options theory, we provide a formula for the insurance price (the premium). By using historical data on market prices for disks, we apply the formula in realistic scenarios. We show that the premium grows nearly quadratically with the length of the coverage period as long as this is below one year, but grows more slowly, though faster than linearly, over longer coverage periods.
An Improved Gauss-Newtons Method based Back-propagation Algorithm for Fast Convergence
Venue: arXiv cs.AI 2012
Year: 2012

The present work deals with an improved back-propagation algorithm based on Gauss-Newton numerical optimization method for fast convergence. The steepest descent method is used for the back-propagation. The algorithm is tested using various datasets and compared with the steepest descent back-propagation algorithm. In the system, optimization is carried out using multilayer neural network. The efficacy of the proposed method is observed during the training period as it converges quickly for the dataset used in test. The requirement of memory for computing the steps of algorithm is also analyzed.
Gray Image extraction using Fuzzy Logic
Venue: arXiv cs.CV 2012
Year: 2012

Fuzzy systems concern fundamental methodology to represent and process uncertainty and imprecision in the linguistic information. The fuzzy systems that use fuzzy rules to represent the domain knowledge of the problem are known as Fuzzy Rule Base Systems (FRBS). On the other hand image segmentation and subsequent extraction from a noise-affected background, with the help of various soft computing methods, are relatively new and quite popular due to various reasons. These methods include various Artificial Neural Network (ANN) models (primarily supervised in nature), Genetic Algorithm (GA) based techniques, intensity histogram based methods etc. providing an extraction solution working in unsupervised mode happens to be even more interesting problem. Literature suggests that effort in this respect appears to be quite rudimentary. In the present article, we propose a fuzzy rule guided novel technique that is functional devoid of any external intervention during execution. Experimental results suggest that this approach is an efficient one in comparison to different other techniques extensively addressed in literature. In order to justify the supremacy of performance of our proposed technique in respect of its competitors, we take recourse to effective metrics like Mean Squared Error (MSE), Mean Absolute Error (MAE), Peak Signal to Noise Ratio (PSNR).
Generalized Craig Interpolation for Stochastic Boolean Satisfiability Problems with Applications to Probabilistic State Reachability and Region Stability
Venue: arXiv cs.LO 2012
Year: 2012

The stochastic Boolean satisfiability (SSAT) problem has been introduced by Papadimitriou in 1985 when adding a probabilistic model of uncertainty to propositional satisfiability through randomized quantification. SSAT has many applications, among them probabilistic bounded model checking (PBMC) of symbolically represented Markov decision processes. This article identifies a notion of Craig interpolant for the SSAT framework and develops an algorithm for computing such interpolants based on a resolution calculus for SSAT. As a potential application area of this novel concept of Craig interpolation, we address the symbolic analysis of probabilistic systems. We first investigate the use of interpolation in probabilistic state reachability analysis, turning the falsification procedure employing PBMC into a verification technique for probabilistic safety properties. We furthermore propose an interpolation-based approach to probabilistic region stability, being able to verify that the probability of stabilizing within some region is sufficiently large.
An Evolutionary Approach to Drug-Design Using Quantam Binary Particle Swarm Optimization Algorithm
Venue: arXiv cs.NE 2012
Year: 2012

The present work provides a new approach to evolve ligand structures which represent possible drug to be docked to the active site of the target protein. The structure is represented as a tree where each non-empty node represents a functional group. It is assumed that the active site configuration of the target protein is known with position of the essential residues. In this paper the interaction energy of the ligands with the protein target is minimized. Moreover, the size of the tree is difficult to obtain and it will be different for different active sites. To overcome the difficulty, a variable tree size configuration is used for designing ligands. The optimization is done using a quantum discrete PSO. The result using fixed length and variable length configuration are compared.
Robust Multiple Manifolds Structure Learning
Venue: arXiv cs.LG 2012
Year: 2012

We present a robust multiple manifolds structure learning (RMMSL) scheme to robustly estimate data structures under the multiple low intrinsic dimensional manifolds assumption. In the local learning stage, RMMSL efficiently estimates local tangent space by weighted low-rank matrix factorization. In the global learning stage, we propose a robust manifold clustering method based on local structure learning results. The proposed clustering method is designed to get the flattest manifolds clusters by introducing a novel curved-level similarity function. Our approach is evaluated and compared to state-of-the-art methods on synthetic data, handwritten digit images, human motion capture data and motorbike videos. We demonstrate the effectiveness of the proposed approach, which yields higher clustering accuracy, and produces promising results for challenging tasks of human motion segmentation and motion flow learning from videos.
An empirical analysis of the use of alphabetical authorship in scientific publishing
Venue: arXiv cs.DL 2012
Year: 2012

There are different ways in which the authors of a scientific publication can determine the order in which their names are listed. Sometimes author names are simply listed alphabetically. In other cases, authorship order is determined based on the contribution authors have made to a publication. Contribution-based authorship can facilitate proper credit assignment, for instance by giving most credits to the first author. In the case of alphabetical authorship, nothing can be inferred about the relative contribution made by the different authors of a publication. In this paper, we present an empirical analysis of the use of alphabetical authorship in scientific publishing. Our analysis covers all fields of science. We find that the use of alphabetical authorship is declining over time. In 2011, the authors of less than 4% of all publications intentionally chose to list their names alphabetically. The use of alphabetical authorship is most common in mathematics, economics (including finance), and high energy physics. Also, the use of alphabetical authorship is relatively more common in the case of publications with either a small or a large number of authors.
The Biased Sampling Profit Extraction Auction
Venue: arXiv cs.GT 2012
Year: 2012

We give an auction for downward-closed environments that generalizes the random sampling profit extraction auction for digital goods of Fiat et al. (2002). The mechanism divides the agents in to a market and a sample using a biased coin and attempts to extract the optimal revenue from the sample from the market. The latter step is done with the downward-closed profit extractor of Ha and Hartline (2012). The auction is a 11-approximation to the envyfree benchmark in downward-closed permutation environments. This is an improvement on the previously best known results of 12.5 for matroid and 30.4 for downward-closed permutation environments that are due to Devanur et al. (2012) and Ha and Hartline (2012), respectively.