OpenRaiser/Intern-Atlas huggingface dataset:
A Real-Time Model-Based Reinforcement Learning Architecture for Robot Control
Venue: arXiv cs.AI 2011
Year: 2011

Reinforcement Learning (RL) is a method for learning decision-making tasks that could enable robots to learn and adapt to their situation on-line. For an RL algorithm to be practical for robotic control tasks, it must learn in very few actions, while continually taking those actions in real-time. Existing model-based RL methods learn in relatively few actions, but typically take too much time between each action for practical on-line learning. In this paper, we present a novel parallel architecture for model-based RL that runs in real-time by 1) taking advantage of sample-based approximate planning methods and 2) parallelizing the acting, model learning, and planning processes such that the acting process is sufficiently fast for typical robot control cycles. We demonstrate that algorithms using this architecture perform nearly as well as methods using the typical sequential architecture when both are given unlimited time, and greatly out-perform these methods on tasks that require real-time actions such as controlling an autonomous vehicle.
Dissecting a Small InfiniBand Application Using the Verbs API
Venue: arXiv cs.DC 2011
Year: 2011

InfiniBand is a switched fabric interconnect. The InfiniBand specification does not define an API. However the OFED package, libibverbs, has become the default API on Linux and Solaris systems. Sparse documentation exists for the verbs API. The simplest InfiniBand program provided by OFED, ibv_rc_pingpong, is about 800 lines long. The semantics of using the verbs API for this program is not obvious to the first time reader. This paper will dissect the ibv_rc_pingpong program in an attempt to make clear to users how to interact with verbs.
Asymptotic Analysis of Double-Scattering Channels
Venue: arXiv cs.IT 2011
Year: 2011

We consider a multiple-input multiple-output (MIMO) multiple access channel (MAC), where the channel between each transmitter and the receiver is modeled by the doubly-scattering channel model. Based on novel techniques from random matrix theory, we derive deterministic approximations of the mutual information, the signal-to-noise-plus-interference-ratio (SINR) at the output of the minimum-mean-square-error (MMSE) detector and the sum-rate with MMSE detection which are almost surely tight in the large system limit. Moreover, we derive the asymptotically optimal transmit covariance matrices. Our simulation results show that the asymptotic analysis provides very close approximations for realistic system dimensions.
Classification and Evaluation the Privacy Preserving Data Mining Techniques by using a Data Modification-based Framework
Venue: arXiv cs.CR 2011
Year: 2011

In recent years, the data mining techniques have met a serious challenge due to the increased concerning and worries of the privacy, that is, protecting the privacy of the critical and sensitive data. Different techniques and algorithms have been already presented for Privacy Preserving data mining, which could be classified in three common approaches: Data modification approach, Data sanitization approach and Secure Multi-party Computation approach. This paper presents a Data modification- based Framework for classification and evaluation of the privacy preserving data mining techniques. Based on our framework the techniques are divided into two major groups, namely perturbation approach and anonymization approach. Also in proposed framework, eight functional criteria will be used to analyze and analogically assessment of the techniques in these two major groups. The proposed framework provides a good basis for more accurate comparison of the given techniques to privacy preserving data mining. In addition, this framework allows recognizing the overlapping amount for different approaches and identifying modern approaches in this field.
An analytical framework for data stream mining techniques based on challenges and requirements
Venue: arXiv cs.DB 2011
Year: 2011

A growing number of applications that generate massive streams of data need intelligent data processing and online analysis. Real-time surveillance systems, telecommunication systems, sensor networks and other dynamic environments are such examples. The imminent need for turning such data into useful information and knowledge augments the development of systems, algorithms and frameworks that address streaming challenges. The storage, querying and mining of such data sets are highly computationally challenging tasks. Mining data streams is concerned with extracting knowledge structures represented in models and patterns in non stopping streams of information. Generally, two main challenges are designing fast mining methods for data streams and need to promptly detect changing concepts and data distribution because of highly dynamic nature of data streams. The goal of this article is to analyze and classify the application of diverse data mining techniques in different challenges of data stream mining. In this paper, we present the theoretical foundations of data stream analysis and propose an analytical framework for data stream mining techniques.
An algebraic look into MAC-DMT of lattice space-time codes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we are concentrating on the diversity-multiplexing gain trade-off (DMT) of some space-time lattice codes. First we give a DMT bound for lattice codes having restricted dimension. We then recover the well known results of the DMT of algebraic number field codes and the Alamouti code by using the union bound and see that these codes do achieve the previously mentioned bound. During our analysis interesting connections to the Dedekind's zeta-function and to the unit group of algebraic number fields are revealed. Finally we prove that both the number field codes and Alamouti code are in some sense optimal codes in the multiple access channel (MAC).
On the Limitations of Provenance for Queries With Difference
Venue: arXiv cs.DB 2011
Year: 2011

The annotation of the results of database transformations was shown to be very effective for various applications. Until recently, most works in this context focused on positive query languages. The provenance semirings is a particular approach that was proven effective for these languages, and it was shown that when propagating provenance with semirings, the expected equivalence axioms of the corresponding query languages are satisfied. There have been several attempts to extend the framework to account for relational algebra queries with difference. We show here that these suggestions fail to satisfy some expected equivalence axioms (that in particular hold for queries on "standard" set and bag databases). Interestingly, we show that this is not a pitfall of these particular attempts, but rather every such attempt is bound to fail in satisfying these axioms, for some semirings. Finally, we show particular semirings for which an extension for supporting difference is (im)possible.
Hierarchical Complexity: Measures of High Level Modularity
Venue: arXiv cs.SE 2011
Year: 2011

Software is among the most complex endeavors of the human mind; large scale systems can have tens of millions of lines of source code. However, seldom is complexity measured above the lowest level of code, and sometimes source code files or low level modules. In this paper a hierarchical approach is explored in order to find a set of metrics that can measure higher levels of organization. These metrics are then used on a few popular free software packages (totaling more than 25 million lines of code) to check their efficiency and coherency.
PAC-Bayesian Analysis of Martingales and Multiarmed Bandits
Venue: arXiv cs.LG 2011
Year: 2011

We present two alternative ways to apply PAC-Bayesian analysis to sequences of dependent random variables. The first is based on a new lemma that enables to bound expectations of convex functions of certain dependent random variables by expectations of the same functions of independent Bernoulli random variables. This lemma provides an alternative tool to Hoeffding-Azuma inequality to bound concentration of martingale values. Our second approach is based on integration of Hoeffding-Azuma inequality with PAC-Bayesian analysis. We also introduce a way to apply PAC-Bayesian analysis in situation of limited feedback. We combine the new tools to derive PAC-Bayesian generalization and regret bounds for the multiarmed bandit problem. Although our regret bound is not yet as tight as state-of-the-art regret bounds based on other well-established techniques, our results significantly expand the range of potential applications of PAC-Bayesian analysis and introduce a new analysis tool to reinforcement learning and many other fields, where martingales and limited feedback are encountered.
TRX: A Formally Verified Parser Interpreter
Venue: arXiv cs.LO 2011
Year: 2011

Parsing is an important problem in computer science and yet surprisingly little attention has been devoted to its formal verification. In this paper, we present TRX: a parser interpreter formally developed in the proof assistant Coq, capable of producing formally correct parsers. We are using parsing expression grammars (PEGs), a formalism essentially representing recursive descent parsing, which we consider an attractive alternative to context-free grammars (CFGs). From this formalization we can extract a parser for an arbitrary PEG grammar with the warranty of total correctness, i.e., the resulting parser is terminating and correct with respect to its grammar and the semantics of PEGs; both properties formally proven in Coq.
Generalized Symmetric Divergence Measures and Metric Spaces
Venue: arXiv cs.IT 2011
Year: 2011

Recently, Taneja studied two one parameter generalizations of J-divergence, Jensen-Shannon divergence and Arithmetic-Geometric divergence. These two generalizations in particular contain measures like: Hellinger discrimination, symmetric chi-square divergence, and triangular discrimination. These measures are well known in the literature of Statistics and Information theory. In this paper our aim is to prove metric space properties for square root of these two symmetric generalized divergence measures.
A Foundational View on Integration Problems
Venue: arXiv cs.LO 2011
Year: 2011

The integration of reasoning and computation services across system and language boundaries is a challenging problem of computer science. In this paper, we use integration for the scenario where we have two systems that we integrate by moving problems and solutions between them. While this scenario is often approached from an engineering perspective, we take a foundational view. Based on the generic declarative language MMT, we develop a theoretical framework for system integration using theories and partial theory morphisms. Because MMT permits representations of the meta-logical foundations themselves, this includes integration across logics. We discuss safe and unsafe integration schemes and devise a general form of safe integration.
$p$-ary sequences with six-valued cross-correlation function: a new decimation of Niho type
Venue: arXiv cs.IT 2011
Year: 2011

For an odd prime $p$ and $n=2m$, a new decimation $d=\frac{(p^{m}-1)^{2}}{2}+1$ of Niho type of $m$-sequences is presented. Using generalized Niho's Theorem, we show that the cross-correlation function between a $p$-ary $m$-sequence of period $p^{n}-1$ and its decimated sequence by the above $d$ is at most six-valued and we can easily know that the magnitude of the cross correlation is upper bounded by $4\sqrt{p^{n}}-1$.
Error Correction for Index Coding with Side Information
Venue: arXiv cs.IT 2011
Year: 2011

A problem of index coding with side information was first considered by Y. Birk and T. Kol (IEEE INFOCOM, 1998). In the present work, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols $δ$, what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest-length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the $α$-bound and the $κ$-bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with an MDS classical code, is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another implicit bound on the length of an optimal linear ECIC. Further, the problem of error-correcting decoding by a linear ECIC is studied. It is shown that in order to decode correctly the desired symbol, the decoder is required to find one of the vectors, belonging to an affine space containing the actual error vector. The syndrome decoding is shown to produce the correct output if the weight of the error pattern is less or equal to the error-correcting capability of the corresponding ECIC. Finally, the notion of static ECIC, which is suitable for use with a family of instances of an index coding problem, is introduced.
Semantic Vector Machines
Venue: arXiv cs.LG 2011
Year: 2011

We first present our work in machine translation, during which we used aligned sentences to train a neural network to embed n-grams of different languages into an $d$-dimensional space, such that n-grams that are the translation of each other are close with respect to some metric. Good n-grams to n-grams translation results were achieved, but full sentences translation is still problematic. We realized that learning semantics of sentences and documents was the key for solving a lot of natural language processing problems, and thus moved to the second part of our work: sentence compression. We introduce a flexible neural network architecture for learning embeddings of words and sentences that extract their semantics, propose an efficient implementation in the Torch framework and present embedding results comparable to the ones obtained with classical neural language models, while being more powerful.
Lassoing Line Outages in the Smart Power Grid
Venue: arXiv cs.SY 2011
Year: 2011

Fast and accurate unveiling of power line outages is of paramount importance not only for preventing faults that may lead to blackouts, but also for routine monitoring and control tasks of the smart grid, including state estimation and optimal power flow. Existing approaches are either challenged by the \emph{combinatorial complexity} issues involved, and are thus limited to identifying single- and double-line outages; or, they invoke less pragmatic assumptions such as \emph{conditionally independent} phasor angle measurements available across the grid. Using only a subset of voltage phasor angle data, the present paper develops a near real-time algorithm for identifying multiple line outages at the affordable complexity of solving a quadratic program via block coordinate descent iterations. The novel approach relies on reformulating the DC linear power flow model as a \emph{sparse} overcomplete expansion, and leveraging contemporary advances in compressive sampling and variable selection using the least-absolute shrinkage and selection operator (Lasso). Analysis and simulated tests on the standard IEEE 118-bus system confirm the effectiveness of lassoing line changes in the smart power grid.
Unleashing the Power of Mobile Cloud Computing using ThinkAir
Venue: arXiv cs.DC 2011
Year: 2011

Smartphones have exploded in popularity in recent years, becoming ever more sophisticated and capable. As a result, developers worldwide are building increasingly complex applications that require ever increasing amounts of computational power and energy. In this paper we propose ThinkAir, a framework that makes it simple for developers to migrate their smartphone applications to the cloud. ThinkAir exploits the concept of smartphone virtualization in the cloud and provides method level computation offloading. Advancing on previous works, it focuses on the elasticity and scalability of the server side and enhances the power of mobile cloud computing by parallelizing method execution using multiple Virtual Machine (VM) images. We evaluate the system using a range of benchmarks starting from simple micro-benchmarks to more complex applications. First, we show that the execution time and energy consumption decrease two orders of magnitude for the N-queens puzzle and one order of magnitude for a face detection and a virus scan application, using cloud offloading. We then show that if a task is parallelizable, the user can request more than one VM to execute it, and these VMs will be provided dynamically. In fact, by exploiting parallelization, we achieve a greater reduction on the execution time and energy consumption for the previous applications. Finally, we use a memory-hungry image combiner tool to demonstrate that applications can dynamically request VMs with more computational power in order to meet their computational requirements.
Double Blind Comparisons: A New Approach to the Database Aggregation Problem
Venue: arXiv cs.CR 2011
Year: 2011

The Data Aggregation Problem occurs when a large collection of data takes on a higher security level than any of its individual component records. Traditional approaches of breaking up the data and restricting access on a "need to know" basis take away one of the great advantages of collecting the data in the first place. This paper introduces a new cryptographic primitive, Double Blind Comparisons, which allows two co-operating users, who each have an encrypted secret, to determine the equality or inequality of those two secrets, even though neither user can discover any information about what the secret is. This paper also introduces a new problem in bilinear groups, conjectured to be a hard problem. Assuming this conjecture, it is shown that neither user can discover any information about whether the secrets are equal, without the other user's co-operation. We then look at how Double Blind Comparisons can be used to mitigate the Data Aggregation Problem. Finally, the paper concludes with some suggested possibilities for future research and some other potential uses for Double Blind Comparisons.
Implementation of Physical-layer Network Coding
Venue: arXiv cs.NI 2011
Year: 2011

This paper presents the first implementation of a two-way relay network based on the principle of physical-layer network coding. To date, only a simplified version of physical-layer network coding (PNC) method, called analog network coding (ANC), has been successfully implemented. The advantage of ANC is that it is simple to implement; the disadvantage, on the other hand, is that the relay amplifies the noise along with the signal before forwarding the signal. PNC systems in which the relay performs XOR or other denoising PNC mappings of the received signal have the potential for significantly better performance. However, the implementation of such PNC systems poses many challenges. For example, the relay must be able to deal with symbol and carrier-phase asynchronies of the simultaneous signals received from the two end nodes, and the relay must perform channel estimation before detecting the signals. We investigate a PNC implementation in the frequency domain, referred to as FPNC, to tackle these challenges. FPNC is based on OFDM. In FPNC, XOR mapping is performed on the OFDM samples in each subcarrier rather than on the samples in the time domain. We implement FPNC on the universal soft radio peripheral (USRP) platform. Our implementation requires only moderate modifications of the packet preamble design of 802.11a/g OFDM PHY. With the help of the cyclic prefix (CP) in OFDM, symbol asynchrony and the multi-path fading effects can be dealt with in a similar fashion. Our experimental results show that symbol-synchronous and symbol-asynchronous FPNC have essentially the same BER performance, for both channel-coded and unchannel-coded FPNC.
Substructuring domain decomposition scheme for unsteady problems
Venue: arXiv cs.NA 2011
Year: 2011

Domain decomposition methods are used for approximate solving boundary problems for partial differential equations on parallel computing systems. Specific features of unsteady problems are taken into account in the most complete way in iteration-free schemes of domain decomposition. Regionally-additive schemes are based on different classes of splitting schemes. In this paper we highlight a class of domain decomposition schemes which is based on the partition of the initial domain into subdomains with common boundary nodes. Using the partition of unit we have constructed and studied unconditionally stable schemes of domain decomposition based on two-component splitting: the problem within subdomain and the problem at their boundaries. As an example there is considered the Cauchy problem for evolutionary equations of first and second order with non-negative self-adjoint operator in a finite Hilbert space. The theoretical consideration is supplemented with numerical solving a model problem for the two-dimensional parabolic equation.
Analyzing the Persistence of Referenced Web Resources with Memento
Venue: arXiv cs.DL 2011
Year: 2011

In this paper we present the results of a study into the persistence and availability of web resources referenced from papers in scholarly repositories. Two repositories with different characteristics, arXiv and the UNT digital library, are studied to determine if the nature of the repository, or of its content, has a bearing on the availability of the web resources cited by that content. Memento makes it possible to automate discovery of archived resources and to consider the time between the publication of the research and the archiving of the referenced URLs. This automation allows us to process more than 160000 URLs, the largest known such study, and the repository metadata allows consideration of the results by discipline. The results are startling: 45% (66096) of the URLs referenced from arXiv still exist, but are not preserved for future generations, and 28% of resources referenced by UNT papers have been lost. Moving forwards, we provide some initial recommendations, including that repositories should publish URL lists extracted from papers that could be used as seeds for web archiving systems.
First-order query evaluation on structures of bounded degree
Venue: arXiv cs.LO 2011
Year: 2011

We consider the enumeration problem of first-order queries over structures of bounded degree. It was shown that this problem is in the Constant-Delaylin class. An enumeration problem belongs to Constant-Delaylin if for an input of size n it can be solved by: - an O(n) precomputation phase building an index structure, - followed by a phase enumerating the answers with no repetition and a constant delay between two consecutive outputs. In this article we give a different proof of this result based on Gaifman's locality theorem for first-order logic. Moreover, the constants we obtain yield a total evaluation time that is triply exponential in the size of the input formula, matching the complexity of the best known evaluation algorithms.