OpenRaiser/Intern-Atlas huggingface dataset:
Capturing Evidence From Wireless Internet Services Development
Venue: arXiv cs.SE 2014
Year: 2014

The merging of the Internet with the Wireless services domain has created a potential market whose characteristics are new technologies and time-to-market pressure. The lack of knowledge about new technologies and the need to be competitive in a short time demand that software organizations learn quickly about this domain and its characteristics. Additionally, the effects of development techniques in this context need to be understood. Learning from previous experiences in such a changing environment demands a clear understanding of the evidence to be captured, and how it could be used in the future. This article presents definitions of quantitative and qualitative evidence, and templates for capturing such evidence in a systematic way. Such templates were used in the context of two pilot projects dealing with the development of Wireless Internet Services.
Statistical Analysis based Hypothesis Testing Method in Biological Knowledge Discovery
Venue: arXiv cs.IR 2014
Year: 2014

The correlation and interactions among different biological entities comprise the biological system. Although already revealed interactions contribute to the understanding of different existing systems, researchers face many questions everyday regarding inter-relationships among entities. Their queries have potential role in exploring new relations which may open up a new area of investigation. In this paper, we introduce a text mining based method for answering the biological queries in terms of statistical computation such that researchers can come up with new knowledge discovery. It facilitates user to submit their query in natural linguistic form which can be treated as hypothesis. Our proposed approach analyzes the hypothesis and measures the p-value of the hypothesis with respect to the existing literature. Based on the measured value, the system either accepts or rejects the hypothesis from statistical point of view. Moreover, even it does not find any direct relationship among the entities of the hypothesis, it presents a network to give an integral overview of all the entities through which the entities might be related. This is also congenial for the researchers to widen their view and thus think of new hypothesis for further investigation. It assists researcher to get a quantitative evaluation of their assumptions such that they can reach a logical conclusion and thus aids in relevant re-searches of biological knowledge discovery. The system also provides the researchers a graphical interactive interface to submit their hypothesis for assessment in a more convenient way.
A reduced semantics for deciding trace equivalence using constraint systems
Venue: arXiv cs.CR 2014
Year: 2014

Many privacy-type properties of security protocols can be modelled using trace equivalence properties in suitable process algebras. It has been shown that such properties can be decided for interesting classes of finite processes (i.e., without replication) by means of symbolic execution and constraint solving. However, this does not suffice to obtain practical tools. Current prototypes suffer from a classical combinatorial explosion problem caused by the exploration of many interleavings in the behaviour of processes. Mödersheim et al. have tackled this problem for reachability properties using partial order reduction techniques. We revisit their work, generalize it and adapt it for equivalence checking. We obtain an optimization in the form of a reduced symbolic semantics that eliminates redundant interleavings on the fly.
Tensor Representation and Manifold Learning Methods for Remote Sensing Images
Venue: arXiv cs.CV 2014
Year: 2014

One of the main purposes of earth observation is to extract interested information and knowledge from remote sensing (RS) images with high efficiency and accuracy. However, with the development of RS technologies, RS system provide images with higher spatial and temporal resolution and more spectral channels than before, and it is inefficient and almost impossible to manually interpret these images. Thus, it is of great interests to explore automatic and intelligent algorithms to quickly process such massive RS data with high accuracy. This thesis targets to develop some efficient information extraction algorithms for RS images, by relying on the advanced technologies in machine learning. More precisely, we adopt the manifold learning algorithms as the mainline and unify the regularization theory, tensor-based method, sparse learning and transfer learning into the same framework. The main contributions of this thesis are as follows.
A tight lower bound instance for k-means++ in constant dimension
Venue: arXiv cs.DS 2014
Year: 2014

The k-means++ seeding algorithm is one of the most popular algorithms that is used for finding the initial $k$ centers when using the k-means heuristic. The algorithm is a simple sampling procedure and can be described as follows: Pick the first center randomly from the given points. For $i > 1$, pick a point to be the $i^{th}$ center with probability proportional to the square of the Euclidean distance of this point to the closest previously $(i-1)$ chosen centers. The k-means++ seeding algorithm is not only simple and fast but also gives an $O(\log{k})$ approximation in expectation as shown by Arthur and Vassilvitskii. There are datasets on which this seeding algorithm gives an approximation factor of $Ω(\log{k})$ in expectation. However, it is not clear from these results if the algorithm achieves good approximation factor with reasonably high probability (say $1/poly(k)$). Brunsch and Röglin gave a dataset where the k-means++ seeding algorithm achieves an $O(\log{k})$ approximation ratio with probability that is exponentially small in $k$. However, this and all other known lower-bound examples are high dimensional. So, an open problem was to understand the behavior of the algorithm on low dimensional datasets. In this work, we give a simple two dimensional dataset on which the seeding algorithm achieves an $O(\log{k})$ approximation ratio with probability exponentially small in $k$. This solves open problems posed by Mahajan et al. and by Brunsch and Röglin.
Software Tool Combining Fault Masking with User-Defined Recovery Strategies
Venue: arXiv cs.DC 2014
Year: 2014

We describe the voting farm, a tool which implements a distributed software voting mechanism for a number of parallel message passing systems. The tool, developed in the framework of EFTOS (Embedded Fault-Tolerant Supercomputing), can be used in stand-alone mode or in conjunction with other EFTOS fault tolerance tools. In the former case, we describe how the mechanism can be exploited, e.g., to implement restoring organs ($N\!$-modular redundancy systems with $N\!$-replicated voters); in the latter case, we show how it is possible for the user to implement in an easy and effective way a number of different recovery strategies via a custom, high-level language. Combining such strategies with the basic fault masking capabilities of the voting tool makes it possible to set up complex fault-tolerant systems such as, for instance, $N$-and-$M$-spare systems or gracefully degrading voting farms. We also report about the impact that our tool can have on reliability, and we show how, besides structural design goals like fault transparency, our tool achieves replication transparency, a high degree of flexibility and ease-of-use, and good performance.
Lines Missing Every Random Point
Venue: arXiv cs.CC 2014
Year: 2014

We prove that there is, in every direction in Euclidean space, a line that misses every computably random point. We also prove that there exist, in every direction in Euclidean space, arbitrarily long line segments missing every double exponential time random point.
Cancellation of Power Amplifier Induced Nonlinear Self-Interference in Full-Duplex Transceivers
Venue: arXiv cs.IT 2014
Year: 2014

Recently, full-duplex (FD) communications with simultaneous transmission and reception on the same channel has been proposed. The FD receiver, however, suffers from inevitable self-interference (SI) from the much more powerful transmit signal. Analogue radio-frequency (RF) and baseband, as well as digital baseband, cancellation techniques have been proposed for suppressing the SI, but so far most of the studies have failed to take into account the inherent nonlinearities of the transmitter and receiver front-ends. To fill this gap, this article proposes a novel digital nonlinear interference cancellation technique to mitigate the power amplifier (PA) induced nonlinear SI in a FD transceiver. The technique is based on modeling the nonlinear SI channel, which is comprised of the nonlinear PA, the linear multipath SI channel, and the RF SI canceller, with a parallel Hammerstein nonlinearity. Stemming from the modeling, and appropriate parameter estimation, the known transmit data is then processed with the developed nonlinear parallel Hammerstein structure and suppressed from the receiver path at digital baseband. The results illustrate that with a given IIP3 figure for the PA, the proposed technique enables higher transmit power to be used compared to existing linear SI cancellation methods. Alternatively, for a given maximum transmit power level, a lower-quality PA (i.e., lower IIP3) can be used.
Synthesis of Sequential Extended Regular Expressions for Verification
Venue: arXiv cs.FL 2014
Year: 2014

Synthesis techniques take realizable Linear Temporal Logic specifications and produce correct cir- cuits that implement the specifications. The generated circuits can be used directly, or as miters that check the correctness of a logic design. Typically, those techniques generate non-deterministic finite state automata, which can be determinized at a possibly exponential cost. Recent results show multiple advantages of using deterministic automata in symbolic and bounded model checking of LTL safety properties. In this paper, we present a technique with a supporting tool that takes a sequential extended regular expression specification Φ, and a logic design implementation S, and generates a sequential circuit C, expressed as an And-Inverted-Graph, that checks whether S satisfies Φ. The technique passes the generated circuit C to ABC, a bounded model checker, to validate correctness. We use free input variables to encode the non- determinism in Φ and we obtain a number of states in miter linear in the size of Φ. Our technique succeeds to generate the input to the model checker while other techniques fail because of the exponential blowup, and in most cases, ABC succeeds to either find defects in the design that was otherwise uncheckable, or validate the design. We evaluated our technique against several industrial benchmarks including the IBM arbiter, a load balancer, and a traffic light system, and compared our results with the NuSMV framework. Our method found defects and validated systems NuSMV could not validate.
Comments on "Optimal Utilization of a Cognitive Shared Channel with a Rechargeable Primary Source Node"
Venue: arXiv cs.IT 2014
Year: 2014

In a recent paper [1], the authors investigated the maximum stable throughput region of a network composed of a rechargeable primary user and a secondary user plugged to a reliable power supply. The authors studied the cases of an infinite and a finite energy queue at the primary transmitter. However, the results of the finite case are incorrect. We show that under the proposed energy queue model (a decoupled ${\rm M/D/1}$ queueing system with Bernoulli arrivals and the consumption of one energy packet per time slot), the energy queue capacity does not affect the stability region of the network.
Separation Property for wB- and wS-regular Languages
Venue: arXiv cs.FL 2014
Year: 2014

In this paper we show that ωB- and ωS-regular languages satisfy the following separation-type theorem If L1,L2 are disjoint languages of ω-words both recognised by ωB- (resp. ωS)-automata then there exists an ω-regular language Lsep that contains L1, and whose complement contains L2. In particular, if a language and its complement are recognised by ωB- (resp. ωS)-automata then the language is ω-regular. The result is especially interesting because, as shown by Bojańczyk and Colcombet, ωB-regular languages are complements of ωS-regular languages. Therefore, the above theorem shows that these are two mutually dual classes that both have the separation property. Usually (e.g. in descriptive set theory or recursion theory) exactly one class from a pair C, Cc has the separation property. The proof technique reduces the separation property for ω-word languages to profinite languages using Ramsey's theorem and topological methods. After that reduction, the analysis of the separation property in the profinite monoid is relatively simple. The whole construction is technically not complicated, moreover it seems to be quite extensible. The paper uses a framework for the analysis of B- and S-regular languages in the context of the profinite monoid that was proposed by Toruńczyk.
Performance Evaluation of ECC in Single and Multi Processor Architectures on FPGA Based Embedded System
Venue: arXiv cs.AR 2014
Year: 2014

Cryptographic algorithms are computationally costly and the challenge is more if we need to execute them in resource constrained embedded systems. Field Programmable Gate Arrays (FPGAs) having programmable logic de- vices and processing cores, have proven to be highly feasible implementation platforms for embedded systems providing lesser design time and reconfig- urability. Design parameters like throughput, resource utilization and power requirements are the key issues. The popular Elliptic Curve Cryptography (ECC), which is superior over other public-key crypto-systems like RSA in many ways, such as providing greater security for a smaller key size, is cho- sen in this work and the possibilities of its implementation in FPGA based embedded systems for both single and dual processor core architectures in- volving task parallelization have been explored. This exploration, which is first of its kind considering the other existing works, is a needed activity for evaluating the best possible architectural environment for ECC implementa- tion on FPGA (Virtex4 XC4VFX12, FF668, -10) based embedded platform.
Optimal Strategies for Simultaneous Vickrey Auctions with Perfect Substitutes
Venue: arXiv cs.GT 2014
Year: 2014

We derive optimal strategies for a bidding agent that participates in multiple, simultaneous second-price auctions with perfect substitutes. We prove that, if everyone else bids locally in a single auction, the global bidder should always place non-zero bids in all available auctions, provided there are no budget constraints. With a budget, however, the optimal strategy is to bid locally if this budget is equal or less than the valuation. Furthermore, for a wide range of valuation distributions, we prove that the problem of finding the optimal bids reduces to two dimensions if all auctions are identical. Finally, we address markets with both sequential and simultaneous auctions, non-identical auctions, and the allocative efficiency of the market.
Adaptive Stochastic Resource Control: A Machine Learning Approach
Venue: arXiv cs.LG 2014
Year: 2014

The paper investigates stochastic resource allocation problems with scarce, reusable resources and non-preemtive, time-dependent, interconnected tasks. This approach is a natural generalization of several standard resource management problems, such as scheduling and transportation problems. First, reactive solutions are considered and defined as control policies of suitably reformulated Markov decision processes (MDPs). We argue that this reformulation has several favorable properties, such as it has finite state and action spaces, it is aperiodic, hence all policies are proper and the space of control policies can be safely restricted. Next, approximate dynamic programming (ADP) methods, such as fitted Q-learning, are suggested for computing an efficient control policy. In order to compactly maintain the cost-to-go function, two representations are studied: hash tables and support vector regression (SVR), particularly, nu-SVRs. Several additional improvements, such as the application of limited-lookahead rollout algorithms in the initial phases, action space decomposition, task clustering and distributed sampling are investigated, too. Finally, experimental results on both benchmark and industry-related data are presented.
Amino Acid Interaction Network Prediction using Multi-objective Optimization
Venue: arXiv cs.CE 2014
Year: 2014

Protein can be represented by amino acid interaction network. This network is a graph whose vertices are the proteins amino acids and whose edges are the interactions between them. This interaction network is the first step of proteins three-dimensional structure prediction. In this paper we present a multi-objective evolutionary algorithm for interaction prediction and ant colony probabilistic optimization algorithm is used to confirm the interaction.
The Computational Complexity of Dominance and Consistency in CP-Nets
Venue: arXiv cs.AI 2014
Year: 2014

We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.
A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamics
Venue: arXiv cs.LG 2014
Year: 2014

Several multiagent reinforcement learning (MARL) algorithms have been proposed to optimize agents decisions. Due to the complexity of the problem, the majority of the previously developed MARL algorithms assumed agents either had some knowledge of the underlying game (such as Nash equilibria) and/or observed other agents actions and the rewards they received. We introduce a new MARL algorithm called the Weighted Policy Learner (WPL), which allows agents to reach a Nash Equilibrium (NE) in benchmark 2-player-2-action games with minimum knowledge. Using WPL, the only feedback an agent needs is its own local reward (the agent does not observe other agents actions or rewards). Furthermore, WPL does not assume that agents know the underlying game or the corresponding Nash Equilibrium a priori. We experimentally show that our algorithm converges in benchmark two-player-two-action games. We also show that our algorithm converges in the challenging Shapleys game where previous MARL algorithms failed to converge without knowing the underlying game or the NE. Furthermore, we show that WPL outperforms the state-of-the-art algorithms in a more realistic setting of 100 agents interacting and learning concurrently. An important aspect of understanding the behavior of a MARL algorithm is analyzing the dynamics of the algorithm: how the policies of multiple learning agents evolve over time as agents interact with one another. Such an analysis not only verifies whether agents using a given MARL algorithm will eventually converge, but also reveals the behavior of the MARL algorithm prior to convergence. We analyze our algorithm in two-player-two-action games and show that symbolically proving WPLs convergence is difficult, because of the non-linear nature of WPLs dynamics, unlike previous MARL algorithms that had either linear or piece-wise-linear dynamics. Instead, we numerically solve WPLs dynamics differential equations and compare the solution to the dynamics of previous MARL algorithms.
Generic Preferences over Subsets of Structured Objects
Venue: arXiv cs.AI 2014
Year: 2014

Various tasks in decision making and decision support systems require selecting a preferred subset of a given set of items. Here we focus on problems where the individual items are described using a set of characterizing attributes, and a generic preference specification is required, that is, a specification that can work with an arbitrary set of items. For example, preferences over the content of an online newspaper should have this form: At each viewing, the newspaper contains a subset of the set of articles currently available. Our preference specification over this subset should be provided offline, but we should be able to use it to select a subset of any currently available set of articles, e.g., based on their tags. We present a general approach for lifting formalisms for specifying preferences over objects with multiple attributes into ones that specify preferences over subsets of such objects. We also show how we can compute an optimal subset given such a specification in a relatively efficient manner. We provide an empirical evaluation of the approach as well as some worst-case complexity results.
Efficient Informative Sensing using Multiple Robots
Venue: arXiv cs.RO 2014
Year: 2014

The need for efficient monitoring of spatio-temporal dynamics in large environmental applications, such as the water quality monitoring in rivers and lakes, motivates the use of robotic sensors in order to achieve sufficient spatial coverage. Typically, these robots have bounded resources, such as limited battery or limited amounts of time to obtain measurements. Thus, careful coordination of their paths is required in order to maximize the amount of information collected, while respecting the resource constraints. In this paper, we present an efficient approach for near-optimally solving the NP-hard optimization problem of planning such informative paths. In particular, we first develop eSIP (efficient Single-robot Informative Path planning), an approximation algorithm for optimizing the path of a single robot. Hereby, we use a Gaussian Process to model the underlying phenomenon, and use the mutual information between the visited locations and remainder of the space to quantify the amount of information collected. We prove that the mutual information collected using paths obtained by using eSIP is close to the information obtained by an optimal solution. We then provide a general technique, sequential allocation, which can be used to extend any single robot planning algorithm, such as eSIP, for the multi-robot problem. This procedure approximately generalizes any guarantees for the single-robot problem to the multi-robot case. We extensively evaluate the effectiveness of our approach on several experiments performed in-field for two important environmental sensing applications, lake and river monitoring, and simulation experiments performed using several real world sensor network data sets.