OpenRaiser/Intern-Atlas huggingface dataset:
Interpolating between Random Walks and Shortest Paths: a Path Functional Approach
Venue: arXiv cs.SI 2012
Year: 2012

General models of network navigation must contain a deterministic or drift component, encouraging the agent to follow routes of least cost, as well as a random or diffusive component, enabling free wandering. This paper proposes a thermodynamic formalism involving two path functionals, namely an energy functional governing the drift and an entropy functional governing the diffusion. A freely adjustable parameter, the temperature, arbitrates between the conflicting objectives of minimising travel costs and maximising spatial exploration. The theory is illustrated on various graphs and various temperatures. The resulting optimal paths, together with presumably new associated edges and nodes centrality indices, are analytically and numerically investigated.
UPPAAL-SMC: Statistical Model Checking for Priced Timed Automata
Venue: arXiv cs.LO 2012
Year: 2012

This paper offers a survey of uppaalsmc, a major extension of the real-time verification tool uppaal. uppaalsmc allows for the efficient analysis of performance properties of networks of priced timed automata under a natural stochastic semantics. In particular, uppaalsmc relies on a series of extensions of the statistical model checking approach generalized to handle real-time systems and estimate undecidable problems. uppaalsmc comes together with a friendly user interface that allows a user to specify complex problems in an efficient manner as well as to get feedback in the form of probability distributions and compare probabilities to analyze performance aspects of systems. The focus of the survey is on the evolution of the tool - including modeling and specification formalisms as well as techniques applied - together with applications of the tool to case studies.
Prediction, Expectation, and Surprise: Methods, Designs, and Study of a Deployed Traffic Forecasting Service
Venue: arXiv cs.AI 2012
Year: 2012

We present research on developing models that forecast traffic flow and congestion in the Greater Seattle area. The research has led to the deployment of a service named JamBayes, that is being actively used by over 2,500 users via smartphones and desktop versions of the system. We review the modeling effort and describe experiments probing the predictive accuracy of the models. Finally, we present research on building models that can identify current and future surprises, via efforts on modeling and forecasting unexpected situations.
Common Voting Rules as Maximum Likelihood Estimators
Venue: arXiv cs.GT 2012
Year: 2012

Voting is a very general method of preference aggregation. A voting rule takes as input every voter's vote (typically, a ranking of the alternatives), and produces as output either just the winning alternative or a ranking of the alternatives. One potential view of voting is the following. There exists a 'correct' outcome (winner/ranking), and each voter's vote corresponds to a noisy perception of this correct outcome. If we are given the noise model, then for any vector of votes, we can
Hybrid Bayesian Networks with Linear Deterministic Variables
Venue: arXiv cs.AI 2012
Year: 2012

When a hybrid Bayesian network has conditionally deterministic variables with continuous parents, the joint density function for the continuous variables does not exist. Conditional linear Gaussian distributions can handle such cases when the continuous variables have a multi-variate normal distribution and the discrete variables do not have continuous parents. In this paper, operations required for performing inference with conditionally deterministic variables in hybrid Bayesian networks are developed. These methods allow inference in networks with deterministic variables where continuous variables may be non-Gaussian, and their density functions can be approximated by mixtures of truncated exponentials. There are no constraints on the placement of continuous and discrete nodes in the network.
Use of Dempster-Shafer Conflict Metric to Detect Interpretation Inconsistency
Venue: arXiv cs.AI 2012
Year: 2012

A model of the world built from sensor data may be incorrect even if the sensors are functioning correctly. Possible causes include the use of inappropriate sensors (e.g. a laser looking through glass walls), sensor inaccuracies accumulate (e.g. localization errors), the a priori models are wrong, or the internal representation does not match the world (e.g. a static occupancy grid used with dynamically moving objects). We are interested in the case where the constructed model of the world is flawed, but there is no access to the ground truth that would allow the system to see the discrepancy, such as a robot entering an unknown environment. This paper considers the problem of determining when something is wrong using only the sensor data used to construct the world model. It proposes 11 interpretation inconsistency indicators based on the Dempster-Shafer conflict metric, Con, and evaluates these indicators according to three criteria: ability to distinguish true inconsistency from sensor noise (classification), estimate the magnitude of discrepancies (estimation), and determine the source(s) (if any) of sensing problems in the environment (isolation). The evaluation is conducted using data from a mobile robot with sonar and laser range sensors navigating indoor environments under controlled conditions. The evaluation shows that the Gambino indicator performed best in terms of estimation (at best 0.77 correlation), isolation, and classification of the sensing situation as degraded (7% false negative rate) or normal (0% false positive rate).
Bounding the Uncertainty of Graphical Games: The Complexity of Simple Requirements, Pareto and Strong Nash Equilibria
Venue: arXiv cs.GT 2012
Year: 2012

We investigate the complexity of bounding the uncertainty of graphical games, and we provide new insight into the intrinsic difficulty of computing Nash equilibria. In particular, we show that, if one adds very simple and natural additional requirements to a graphical game, the existence of Nash equilibria is no longer guaranteed, and computing an equilibrium is an intractable problem. Moreover, if stronger equilibrium conditions are required for the game, we get hardness results for the second level of the polynomial hierarchy. Our results offer a clear picture of the complexity of mixed Nash equilibria in graphical games, and answer some open research questions posed by Conitzer and Sandholm (2003).
Near-optimal Nonmyopic Value of Information in Graphical Models
Venue: arXiv cs.AI 2012
Year: 2012

A fundamental issue in real-world systems, such as sensor networks, is the selection of observations which most effectively reduce uncertainty. More specifically, we address the long standing problem of nonmyopically selecting the most informative subset of variables in a graphical model. We present the first efficient randomized algorithm providing a constant factor (1-1/e-epsilon) approximation guarantee for any epsilon > 0 with high confidence. The algorithm leverages the theory of submodular functions, in combination with a polynomial bound on sample complexity. We furthermore prove that no polynomial time algorithm can provide a constant factor approximation better than (1 - 1/e) unless P = NP. Finally, we provide extensive evidence of the effectiveness of our method on two complex real-world datasets.
A submodular-supermodular procedure with applications to discriminative structure learning
Venue: arXiv cs.LG 2012
Year: 2012

In this paper, we present an algorithm for minimizing the difference between two submodular functions using a variational framework which is based on (an extension of) the concave-convex procedure [17]. Because several commonly used metrics in machine learning, like mutual information and conditional mutual information, are submodular, the problem of minimizing the difference of two submodular problems arises naturally in many machine learning applications. Two such applications are learning discriminatively structured graphical models and feature selection under computational complexity constraints. A commonly used metric for measuring discriminative capacity is the EAR measure which is the difference between two conditional mutual information terms. Feature selection taking complexity considerations into account also fall into this framework because both the information that a set of features provide and the cost of computing and using the features can be modeled as submodular functions. This problem is NP-hard, and we give a polynomial time heuristic for it. We also present results on synthetic data to show that classifiers based on discriminative graphical models using this algorithm can significantly outperform classifiers based on generative graphical models.
A Conditional Random Field for Discriminatively-trained Finite-state String Edit Distance
Venue: arXiv cs.LG 2012
Year: 2012

The need to measure sequence similarity arises in information extraction, object identity, data mining, biological sequence analysis, and other domains. This paper presents discriminative string-edit CRFs, a finitestate conditional random field model for edit sequences between strings. Conditional random fields have advantages over generative approaches to this problem, such as pair HMMs or the work of Ristad and Yianilos, because as conditionally-trained methods, they enable the use of complex, arbitrary actions and features of the input strings. As in generative models, the training data does not have to specify the edit sequences between the given string pairs. Unlike generative models, however, our model is trained on both positive and negative instances of string pairs. We present positive experimental results on several data sets.
Approximate Linear Programming for First-order MDPs
Venue: arXiv cs.AI 2012
Year: 2012

We introduce a new approximate solution technique for first-order Markov decision processes (FOMDPs). Representing the value function linearly w.r.t. a set of first-order basis functions, we compute suitable weights by casting the corresponding optimization as a first-order linear program and show how off-the-shelf theorem prover and LP software can be effectively used. This technique allows one to solve FOMDPs independent of a specific domain instantiation; furthermore, it allows one to determine bounds on approximation error that apply equally to all domain instantiations. We apply this solution technique to the task of elevator scheduling with a rich feature space and multi-criteria additive reward, and demonstrate that it outperforms a number of intuitive, heuristicallyguided policies.
The DLR Hierarchy of Approximate Inference
Venue: arXiv cs.LG 2012
Year: 2012

We propose a hierarchy for approximate inference based on the Dobrushin, Lanford, Ruelle (DLR) equations. This hierarchy includes existing algorithms, such as belief propagation, and also motivates novel algorithms such as factorized neighbors (FN) algorithms and variants of mean field (MF) algorithms. In particular, we show that extrema of the Bethe free energy correspond to approximate solutions of the DLR equations. In addition, we demonstrate a close connection between these approximate algorithms and Gibbs sampling. Finally, we compare and contrast various of the algorithms in the DLR hierarchy on spin-glass problems. The experiments show that algorithms higher up in the hierarchy give more accurate results when they converge but tend to be less stable.
A Transformational Characterization of Markov Equivalence for Directed Acyclic Graphs with Latent Variables
Venue: arXiv cs.AI 2012
Year: 2012

Different directed acyclic graphs (DAGs) may be Markov equivalent in the sense that they entail the same conditional independence relations among the observed variables. Chickering (1995) provided a transformational characterization of Markov equivalence for DAGs (with no latent variables), which is useful in deriving properties shared by Markov equivalent DAGs, and, with certain generalization, is needed to prove the asymptotic correctness of a search procedure over Markov equivalence classes, known as the GES algorithm. For DAG models with latent variables, maximal ancestral graphs (MAGs) provide a neat representation that facilitates model search. However, no transformational characterization -- analogous to Chickering's -- of Markov equivalent MAGs is yet available. This paper establishes such a characterization for directed MAGs, which we expect will have similar uses as it does for DAGs.
Qualitative Decision Making Under Possibilistic Uncertainty: Toward more discriminating criteria
Venue: arXiv cs.AI 2012
Year: 2012

The aim of this paper is to propose a generalization of previous approaches in qualitative decision making. Our work is based on the binary possibilistic utility (PU), which is a possibilistic counterpart of Expected Utility (EU).We first provide a new axiomatization of PU and study its relation with the lexicographic aggregation of pessimistic and optimistic utilities. Then we explain the reasons of the coarseness of qualitative decision criteria. Finally, thanks to a redefinition of possibilistic lotteries and mixtures, we present the refined binary possibilistic utility, which is more discriminating than previously proposed criteria.
A Model for Reasoning with Uncertain Rules in Event Composition Systems
Venue: arXiv cs.AI 2012
Year: 2012

In recent years, there has been an increased need for the use of active systems - systems required to act automatically based on events, or changes in the environment. Such systems span many areas, from active databases to applications that drive the core business processes of today's enterprises. However, in many cases, the events to which the system must respond are not generated by monitoring tools, but must be inferred from other events based on complex temporal predicates. In addition, in many applications, such inference is inherently uncertain. In this paper, we introduce a formal framework for knowledge representation and reasoning enabling such event inference. Based on probability theory, we define the representation of the associated uncertainty. In addition, we formally define the probability space, and show how the relevant probabilities can be calculated by dynamically constructing a Bayesian network. To the best of our knowledge, this is the first work that enables taking such uncertainty into account in the context of active systems. herefore, our contribution is twofold: We formally define the representation and semantics of event composition for probabilistic settings, and show how to apply these extensions to the quantification of the occurrence probability of events. These results enable any active system to handle such uncertainty.
Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks
Venue: arXiv cs.LG 2012
Year: 2012

One of the basic tasks for Bayesian networks (BNs) is that of learning a network structure from data. The BN-learning problem is NP-hard, so the standard solution is heuristic search. Many approaches have been proposed for this task, but only a very small number outperform the baseline of greedy hill-climbing with tabu lists; moreover, many of the proposed algorithms are quite complex and hard to implement. In this paper, we propose a very simple and easy-to-implement method for addressing this task. Our approach is based on the well-known fact that the best network (of bounded in-degree) consistent with a given node ordering can be found very efficiently. We therefore propose a search not over the space of structures, but over the space of orderings, selecting for each ordering the best network consistent with it. This search space is much smaller, makes more global search steps, has a lower branching factor, and avoids costly acyclicity checks. We present results for this algorithm on both synthetic and real data sets, evaluating both the score of the network found and in the running time. We show that ordering-based search outperforms the standard baseline, and is competitive with recent algorithms that are much harder to implement.
Cramer-Rao Bounds for Joint RSS/DoA-Based Primary-User Localization in Cognitive Radio Networks
Venue: arXiv cs.PF 2012
Year: 2012

Knowledge about the location of licensed primary-users (PU) could enable several key features in cognitive radio (CR) networks including improved spatio-temporal sensing, intelligent location-aware routing, as well as aiding spectrum policy enforcement. In this paper we consider the achievable accuracy of PU localization algorithms that jointly utilize received-signal-strength (RSS) and direction-of-arrival (DoA) measurements by evaluating the Cramer-Rao Bound (CRB). Previous works evaluate the CRB for RSS-only and DoA-only localization algorithms separately and assume DoA estimation error variance is a fixed constant or rather independent of RSS. We derive the CRB for joint RSS/DoA-based PU localization algorithms based on the mathematical model of DoA estimation error variance as a function of RSS, for a given CR placement. The bound is compared with practical localization algorithms and the impact of several key parameters, such as number of nodes, number of antennas and samples, channel shadowing variance and correlation distance, on the achievable accuracy are thoroughly analyzed and discussed. We also derive the closed-form asymptotic CRB for uniform random CR placement, and perform theoretical and numerical studies on the required number of CRs such that the asymptotic CRB tightly approximates the numerical integration of the CRB for a given placement.
Multimodal similarity-preserving hashing
Venue: arXiv cs.CV 2012
Year: 2012

We introduce an efficient computational framework for hashing data belonging to multiple modalities into a single representation space where they become mutually comparable. The proposed approach is based on a novel coupled siamese neural network architecture and allows unified treatment of intra- and inter-modality similarity learning. Unlike existing cross-modality similarity learning approaches, our hashing functions are not limited to binarized linear projections and can assume arbitrarily complex forms. We show experimentally that our method significantly outperforms state-of-the-art hashing approaches on multimedia retrieval tasks.
Framework of SQL Injection Attack
Venue: arXiv cs.NI 2012
Year: 2012

With the changing demographics of globalization, the emergence and prevalence of web application have acquired a central and pivotal role in the domains of technology and advancements. It thus becomes imperative to probe deeply into the architecture, significance and different facets of usages. Web applications enclose the functioning between a user and the services provided by the server, which contains a database as its backend. The user can access the required information through sending a request in the form of text to the web server, which is interpreted by the server side script to construct an SQL. The query is sent to the database which responds in order to generate an HTML page that is sent back to the user. Since the functioning of web application is a dynamic and complicated matter, certain threats to the database security have been registered. One such alarming threat is the prevalence of SQL Injection Attack. Hence a dynamic algorithm is given in this paper for preventing SQL Injection Attacks which is based on context free grammars and compiler parsing techniques. The paper attempts to present the notation of a SQLI Prevent Parser for the prevention of SQL Injection Attacks. This Parser determines the structure of queries and compares whether the queries are functionally equivalent or not. This parser has been used on a sample web application and the results have come out to be positive majors to prevent SQL Injection Attacks.
Velocity/Position Integration Formula (I): Application to In-flight Coarse Alignment
Venue: arXiv cs.RO 2012
Year: 2012

The in-flight alignment is a critical stage for airborne INS/GPS applications. The alignment task is usually carried out by the Kalman filtering technique that necessitates a good initial attitude to obtain satisfying performance. Due to the airborne dynamics, the in-flight alignment is much difficult than alignment on the ground. This paper proposes an optimization-based coarse alignment approach using GPS position/velocity as input, founded on the newly-derived velocity/position integration formulae. Simulation and flight test results show that, with the GPS lever arm well handled, it is potentially able to yield the initial heading up to one degree accuracy in ten seconds. It can serve as a nice coarse in-flight alignment without any prior attitude information for the subsequent fine Kalman alignment. The approach can also be applied to other applications that require aligning the INS on the run.
An Innovative Skin Detection Approach Using Color Based Image Retrieval Technique
Venue: arXiv cs.CV 2012
Year: 2012

From The late 90th, "Skin Detection" becomes one of the major problems in image processing. If "Skin Detection" will be done in high accuracy, it can be used in many cases as face recognition, Human Tracking and etc. Until now so many methods were presented for solving this problem. In most of these methods, color space was used to extract feature vector for classifying pixels, but the most of them have not good accuracy in detecting types of skin. The proposed approach in this paper is based on "Color based image retrieval" (CBIR) technique. In this method, first by means of CBIR method and image tiling and considering the relation between pixel and its neighbors, a feature vector would be defined and then with using a training step, detecting the skin in the test stage. The result shows that the presenting approach, in addition to its high accuracy in detecting type of skin, has no sensitivity to illumination intensity and moving face orientation.
Complete PISO and SIMPLE solvers on Graphics Processing Units
Venue: arXiv cs.DC 2012
Year: 2012

We implemented the pressure-implicit with splitting of operators (PISO) and semi-implicit method for pressure-linked equations (SIMPLE) solvers of the Navier-Stokes equations on Fermi-class graphics processing units (GPUs) using the CUDA technology. We also introduced a new format of sparse matrices optimized for performing elementary CFD operations, like gradient or divergence discretization, on GPUs. We verified the validity of the implementation on several standard, steady and unsteady problems. Computational effciency of the GPU implementation was examined by comparing its double precision run times with those of essentially the same algorithms implemented in OpenFOAM. The results show that a GPU (Tesla C2070) can outperform a server-class 6-core, 12-thread CPU (Intel Xeon X5670) by a factor of 4.2.
The SeqBin Constraint Revisited
Venue: arXiv cs.AI 2012
Year: 2012

We revisit the SeqBin constraint. This meta-constraint subsumes a number of important global constraints like Change, Smooth and IncreasingNValue. We show that the previously proposed filtering algorithm for SeqBin has two drawbacks even under strong restrictions: it does not detect bounds disentailment and it is not idempotent. We identify the cause for these problems, and propose a new propagator that overcomes both issues. Our algorithm is based on a connection to the problem of finding a path of a given cost in a restricted $n$-partite graph. Our propagator enforces domain consistency in O(nd^2) and, for special cases of SeqBin that include Change, Smooth and IncreasingNValue, in O(nd) time.