OpenRaiser/Intern-Atlas huggingface dataset:
Blind Adaptive Constrained Constant-Modulus Reduced-Rank Interference Suppression Algorithms Based on Interpolation, Switched Decimation and Filtering
Venue: arXiv cs.IT 2013
Year: 2013

This work proposes a blind adaptive reduced-rank scheme and constrained constant-modulus (CCM) adaptive algorithms for interference suppression in wireless communications systems. The proposed scheme and algorithms are based on a two-stage processing framework that consists of a transformation matrix that performs dimensionality reduction followed by a reduced-rank estimator. The complex structure of the transformation matrix of existing methods motivates the development of a blind adaptive reduced-rank constrained (BARC) scheme along with a low-complexity reduced-rank decomposition. The proposed BARC scheme and a reduced-rank decomposition based on the concept of joint interpolation, switched decimation and reduced-rank estimation subject to a set of constraints are then detailed. The proposed set of constraints ensures that the multi-path components of the channel are combined prior to dimensionality reduction. In order to cost-effectively design the BARC scheme, we develop low-complexity decimation techniques, stochastic gradient and recursive least squares reduced-rank estimation algorithms. A model-order selection algorithm for adjusting the length of the estimators is devised along with techniques for determining the required number of switching branches to attain a predefined performance. An analysis of the convergence properties and issues of the proposed optimization and algorithms is carried out, and the key features of the optimization problem are discussed. We consider the application of the proposed algorithms to interference suppression in DS-CDMA systems. The results show that the proposed algorithms outperform the best known reduced-rank schemes, while requiring lower complexity.
Computing Quantiles in Markov Reward Models
Venue: arXiv cs.LO 2013
Year: 2013

Probabilistic model checking mainly concentrates on techniques for reasoning about the probabilities of certain path properties or expected values of certain random variables. For the quantitative system analysis, however, there is also another type of interesting performance measure, namely quantiles. A typical quantile query takes as input a lower probability bound p and a reachability property. The task is then to compute the minimal reward bound r such that with probability at least p the target set will be reached before the accumulated reward exceeds r. Quantiles are well-known from mathematical statistics, but to the best of our knowledge they have not been addressed by the model checking community so far. In this paper, we study the complexity of quantile queries for until properties in discrete-time finite-state Markov decision processes with non-negative rewards on states. We show that qualitative quantile queries can be evaluated in polynomial time and present an exponential algorithm for the evaluation of quantitative quantile queries. For the special case of Markov chains, we show that quantitative quantile queries can be evaluated in time polynomial in the size of the chain and the maximum reward.
The forest consensus theorem
Venue: arXiv cs.MA 2013
Year: 2013

We show that the limiting state vector in the differential model of consensus seeking with an arbitrary communication digraph is obtained by multiplying the eigenprojection of the Laplacian matrix of the model by the vector of initial states. Furthermore, the eigenprojection coincides with the stochastic matrix of maximum out-forests of the weighted communication digraph. These statements make the forests consensus theorem. A similar result for DeGroot's iterative pooling model requires the Cesaro (time-average) limit in the general case. The forests consensus theorem is useful for the analysis of consensus protocols.
Application of entropy compression in pattern avoidance
Venue: arXiv cs.DM 2013
Year: 2013

In combinatorics on words, a word $w$ over an alphabet $Σ$ is said to avoid a pattern $p$ over an alphabet $Δ$ if there is no factor $f$ of $w$ such that $f= (p)$ where $h: Δ^*\toΣ^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$-avoidable if there exists an infinite word over a $k$-letter alphabet that avoids $p$. We give a positive answer to Problem 3.3.2 in Lothaire's book "Algebraic combinatorics on words", that is, every pattern with $k$ variables of length at least $2^k$ (resp. $3\times2^{k-1}$) is 3-avoidable (resp. 2-avoidable). This improves previous bounds due to Bell and Goh, and Rampersad.
An Information System to Support and Monitor Clinical Trial Process
Venue: arXiv cs.SE 2013
Year: 2013

The demand of transparency of clinical research results, the need of accelerating the process of transferring innovation in the daily medical practice as well as assuring patient safety and product efficacy make it necessary to extend the functionality of traditional trial registries. These new systems should combine different functionalities to track the information exchange, support collaborative work, manage regulatory documents and monitor the entire clinical investigation (CIV) lifecycle. This is the approach used to develop MEDIS, a Medical Device Information System, described in this paper under the perspective of the business process, and the underlining architecture. Moreover, MEDIS was designed on the basis of Health Level 7 (HL7) v.3 standards and methodology to make it interoperable with similar registries, but also to facilitate information exchange between different health information systems.
Cloud Penetration Testing
Venue: arXiv cs.CR 2013
Year: 2013

This paper presents the results of a series of penetration tests performed on the OpenStack Essex Cloud Management Software. Several different types of penetration tests were performed including network protocol and command line fuzzing, session hijacking and credential theft. Using these techniques exploitable vulnerabilities were discovered that could enable an attacker to gain access to restricted information contained on the OpenStack server, or to gain full administrative privileges on the server. Key recommendations to address these vulnerabilities are to use a secure protocol, such as HTTPS, for communications between a cloud user and the OpenStack Horizon Dashboard, to encrypt all files that store user or administrative login credentials, and to correct a software bug found in the OpenStack Cinder typedelete command.
Error Correction in Learning using SVMs
Venue: arXiv cs.LG 2013
Year: 2013

This paper is concerned with learning binary classifiers under adversarial label-noise. We introduce the problem of error-correction in learning where the goal is to recover the original clean data from a label-manipulated version of it, given (i) no constraints on the adversary other than an upper-bound on the number of errors, and (ii) some regularity properties for the original data. We present a simple and practical error-correction algorithm called SubSVMs that learns individual SVMs on several small-size (log-size), class-balanced, random subsets of the data and then reclassifies the training points using a majority vote. Our analysis reveals the need for the two main ingredients of SubSVMs, namely class-balanced sampling and subsampled bagging. Experimental results on synthetic as well as benchmark UCI data demonstrate the effectiveness of our approach. In addition to noise-tolerance, log-size subsampled bagging also yields significant run-time benefits over standard SVMs.
Training Effective Node Classifiers for Cascade Classification
Venue: arXiv cs.CV 2013
Year: 2013

Cascade classifiers are widely used in real-time object detection. Different from conventional classifiers that are designed for a low overall classification error rate, a classifier in each node of the cascade is required to achieve an extremely high detection rate and moderate false positive rate. Although there are a few reported methods addressing this requirement in the context of object detection, there is no principled feature selection method that explicitly takes into account this asymmetric node learning objective. We provide such an algorithm here. We show that a special case of the biased minimax probability machine has the same formulation as the linear asymmetric classifier (LAC) of Wu et al (2005). We then design a new boosting algorithm that directly optimizes the cost function of LAC. The resulting totally-corrective boosting algorithm is implemented by the column generation technique in convex optimization. Experimental results on object detection verify the effectiveness of the proposed boosting algorithm as a node classifier in cascade object detection, and show performance better than that of the current state-of-the-art.
API Blender: A Uniform Interface to Social Platform APIs
Venue: arXiv cs.SE 2013
Year: 2013

With the growing success of the social Web, most Web developers have to interact with at least one social Web platform, which implies studying the related API specifications. These are often only informally described, may contain errors, lack harmonization, and generally speaking make the developer's work difficult. Most attempts to solve this problem, proposing formal description languages for Web service APIs, have had limited success outside of B2B applications; we believe it is due to their top-down nature. In addition, a programmer dealing with one or several of these APIs has to deal with a number of related tasks such as data integration, requests chaining, or policy management, that are cumbersome to implement. Inspired by the SPORE project, we present API Blender, an open-source solution to describe, interact with, and integrate the most common social Web APIs. In this perspective, we first introduce two new lightweight description formats for requests and services and demonstrate their relevance with respect to current platform APIs. We present our Python implementation of API Blender and its features regarding authentication, policy management and multi-platform data integration.
A Visual Grammar Approach for TV Program Identification
Venue: arXiv cs.MM 2013
Year: 2013

Automatic identification of TV programs within TV streams is an important task for archive exploitation. This paper proposes a new spatial-temporal approach to identify programs in TV streams in two main steps: First, a reference catalogue for video grammars of visual jingles is constructed. We exploit visual grammars characterizing instances of the same program type in order to identify the various program types in the TV stream. The role of video grammar is to represent the visual invariants for each visual jingle using a set of descriptors appropriate for each TV program. Secondly, programs in TV streams are identified by examining the similarity of the video signal to the visual grammars in the catalogue. The main idea of identification process consists in comparing the visual similarity of the video signal signature in TV stream to the catalogue elements. After presenting the proposed approach, the paper overviews the encouraging experimental results on several streams extracted from different channels and composed of several programs.
User Profile-Driven Data Warehouse Summary for Adaptive OLAP Queries
Venue: arXiv cs.DB 2013
Year: 2013

Data warehousing is an essential element of decision support systems. It aims at enabling the user knowledge to make better and faster daily business decisions. To improve this decision support system and to give more and more relevant information to the user, the need to integrate user's profiles into the data warehouse process becomes crucial. In this paper, we propose to exploit users' preferences as a basis for adapting OLAP (On-Line Analytical Processing) queries to the user. For this, we present a user profile-driven data warehouse approach that allows dening user's profile composed by his/her identifier and a set of his/her preferences. Our approach is based on a general data warehouse architecture and an adaptive OLAP analysis system. Our main idea consists in creating a data warehouse materialized view for each user with respect to his/her profile. This task is performed off-line when the user defines his/her profile for the first time. Then, when a user query is submitted to the data warehouse, the system deals with his/her data warehouse materialized view instead of the whole data warehouse. In other words, the data warehouse view summaries the data warehouse content for the user by taking into account his/her preferences. Moreover, we are implementing our data warehouse personalization approach under the SQL Server 2005 DBMS (DataBase Management System).
UCP-Networks: A Directed Graphical Representation of Conditional Utilities
Venue: arXiv cs.AI 2013
Year: 2013

We propose a new directed graphical representation of utility functions, called UCP-networks, that combines aspects of two existing graphical models: generalized additive models and CP-networks. The network decomposes a utility function into a number of additive factors, with the directionality of the arcs reflecting conditional dependence of preference statements - in the underlying (qualitative) preference ordering - under a {em ceteris paribus} (all else being equal) interpretation. This representation is arguably natural in many settings. Furthermore, the strong CP-semantics ensures that computation of optimization and dominance queries is very efficient. We also demonstrate the value of this representation in decision making. Finally, we describe an interactive elicitation procedure that takes advantage of the linear nature of the constraints on "`tradeoff weights" imposed by a UCP-network. This procedure allows the network to be refined until the regret of the decision with minimax regret (with respect to the incompletely specified utility function) falls below a specified threshold (e.g., the cost of further questioning.
Confidence Inference in Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

We present two sampling algorithms for probabilistic confidence inference in Bayesian networks. These two algorithms (we call them AIS-BN-mu and AIS-BN-sigma algorithms) guarantee that estimates of posterior probabilities are with a given probability within a desired precision bound. Our algorithms are based on recent advances in sampling algorithms for (1) estimating the mean of bounded random variables and (2) adaptive importance sampling in Bayesian networks. In addition to a simple stopping rule for sampling that they provide, the AIS-BN-mu and AIS-BN-sigma algorithms are capable of guiding the learning process in the AIS-BN algorithm. An empirical evaluation of the proposed algorithms shows excellent performance, even for very unlikely evidence.
Hybrid Processing of Beliefs and Constraints
Venue: arXiv cs.AI 2013
Year: 2013

This paper explores algorithms for processing probabilistic and deterministic information when the former is represented as a belief network and the latter as a set of boolean clauses. The motivating tasks are 1. evaluating beliefs networks having a large number of deterministic relationships and2. evaluating probabilities of complex boolean querie over a belief network. We propose a parameterized family of variable elimination algorithms that exploit both types of information, and that allows varying levels of constraint propagation inferences. The complexity of the scheme is controlled by the induced-width of the graph {em augmented} by the dependencies introduced by the boolean constraints. Preliminary empirical evaluation demonstrate the effect of constraint propagation on probabilistic computation.
Enumerating Markov Equivalence Classes of Acyclic Digraph Models
Venue: arXiv cs.AI 2013
Year: 2013

Graphical Markov models determined by acyclic digraphs (ADGs), also called directed acyclic graphs (DAGs), are widely studied in statistics, computer science (as Bayesian networks), operations research (as influence diagrams), and many related fields. Because different ADGs may determine the same Markov equivalence class, it long has been of interest to determine the efficiency gained in model specification and search by working directly with Markov equivalence classes of ADGs rather than with ADGs themselves. A computer program was written to enumerate the equivalence classes of ADG models as specified by Pearl & Verma's equivalence criterion. The program counted equivalence classes for models up to and including 10 vertices. The ratio of number of classes to ADGs appears to approach an asymptote of about 0.267. Classes were analyzed according to number of edges and class size. By edges, the distribution of number of classes approaches a Gaussian shape. By class size, classes of size 1 are most common, with the proportions for larger sizes initially decreasing but then following a more irregular pattern. The maximum number of classes generated by any undirected graph was found to increase approximately factorially. The program also includes a new variation of orderly algorithm for generating undirected graphs.
Similarity Measures on Preference Structures, Part II: Utility Functions
Venue: arXiv cs.AI 2013
Year: 2013

In previous work cite{Ha98:Towards} we presented a case-based approach to eliciting and reasoning with preferences. A key issue in this approach is the definition of similarity between user preferences. We introduced the probabilistic distance as a measure of similarity on user preferences, and provided an algorithm to compute the distance between two partially specified {em value} functions. This is for the case of decision making under {em certainty}. In this paper we address the more challenging issue of computing the probabilistic distance in the case of decision making under{em uncertainty}. We provide an algorithm to compute the probabilistic distance between two partially specified {em utility} functions. We demonstrate the use of this algorithm with a medical data set of partially specified patient preferences,where none of the other existing distancemeasures appear definable. Using this data set, we also demonstrate that the case-based approach to preference elicitation isapplicable in domains with uncertainty. Finally, we provide a comprehensive analytical comparison of the probabilistic distance with some existing distance measures on preferences.
A Dynamic Programming Model for Determining Bidding Strategies in Sequential Auctions: Quasi-linear Utility and Budget Constraints
Venue: arXiv cs.GT 2013
Year: 2013

In this paper, we develop a new method for finding an optimal biddingstrategy in sequential auctions, using a dynamic programming technique. Theexisting method assumes that the utility of a user is represented in anadditive form. Thus, the remaining endowment of money must be explicitlyrepresented in each state, and the calculation of the optimal biddingstrategy becomes time-consuming when the initial endowment of money mbecomes large.In this paper, we develop a new problem formalization that avoids explicitlyrepresenting the remaining endowment, by assuming the utility of a user canbe represented in a quasi-linear form, and representing the payment as astate-transition cost. Experimental evaluations show that we can obtainmore than an m-fold speed-up in the computation time. Furthermore, we havedeveloped a method for obtaining a semi-optimal bidding strategy underbudget constraints, and have experimentally confirmed the efficacy of thismethod.
Improved learning of Bayesian networks
Venue: arXiv cs.LG 2013
Year: 2013

The search space of Bayesian Network structures is usually defined as Acyclic Directed Graphs (DAGs) and the search is done by local transformations of DAGs. But the space of Bayesian Networks is ordered by DAG Markov model inclusion and it is natural to consider that a good search policy should take this into account. First attempt to do this (Chickering 1996) was using equivalence classes of DAGs instead of DAGs itself. This approach produces better results but it is significantly slower. We present a compromise between these two approaches. It uses DAGs to search the space in such a way that the ordering by inclusion is taken into account. This is achieved by repetitive usage of local moves within the equivalence class of DAGs. We show that this new approach produces better results than the original DAGs approach without substantial change in time complexity. We present empirical results, within the framework of heuristic search and Markov Chain Monte Carlo, provided through the Alarm dataset.
Recognition Networks for Approximate Inference in BN20 Networks
Venue: arXiv cs.AI 2013
Year: 2013

We propose using recognition networks for approximate inference inBayesian networks (BNs). A recognition network is a multilayerperception (MLP) trained to predict posterior marginals given observedevidence in a particular BN. The input to the MLP is a vector of thestates of the evidential nodes. The activity of an output unit isinterpreted as a prediction of the posterior marginal of thecorresponding variable. The MLP is trained using samples generated fromthe corresponding BN.We evaluate a recognition network that was trained to do inference ina large Bayesian network, similar in structure and complexity to theQuick Medical Reference, Decision Theoretic (QMR-DT). Our networkis a binary, two-layer, noisy-OR network containing over 4000 potentially observable nodes and over 600 unobservable, hidden nodes. Inreal medical diagnosis, most observables are unavailable, and there isa complex and unknown bias that selects which ones are provided. Weincorporate a very basic type of selection bias in our network: a knownpreference that available observables are positive rather than negative.Even this simple bias has a significant effect on the posterior. We compare the performance of our recognition network tostate-of-the-art approximate inference algorithms on a large set oftest cases. In order to evaluate the effect of our simplistic modelof the selection bias, we evaluate algorithms using a variety ofincorrectly modeled observation biases. Recognition networks performwell using both correct and incorrect observation biases.
Analysing Sensitivity Data from Probabilistic Networks
Venue: arXiv cs.AI 2013
Year: 2013

With the advance of efficient analytical methods for sensitivity analysis ofprobabilistic networks, the interest in the sensitivities revealed by real-life networks is rekindled. As the amount of data resulting from a sensitivity analysis of even a moderately-sized network is alreadyoverwhelming, methods for extracting relevant information are called for. One such methodis to study the derivative of the sensitivity functions yielded for a network's parameters. We further propose to build upon the concept of admissible deviation, that is, the extent to which a parameter can deviate from the true value without inducing a change in the most likely outcome. We illustrate these concepts by means of a sensitivity analysis of a real-life probabilistic network in oncology.
New digital signature protocol based on elliptic curves
Venue: arXiv cs.CR 2013
Year: 2013

In this work, a new digital signature based on elliptic curves is presented. We established its efficiency and security. The method, derived from a variant of ElGamal signature scheme, can be seen as a secure alternative protocol if known systems are completely broken.