OpenRaiser/Intern-Atlas huggingface dataset:
On the Core of Dynamic Cooperative Games
Venue: arXiv cs.GT 2012
Year: 2012

We consider dynamic cooperative games, where the worth of coalitions varies over time according to the history of allocations. When defining the core of a dynamic game, we allow the possibility for coalitions to deviate at any time and thereby to give rise to a new environment. A coalition that considers a deviation needs to take the consequences into account because from the deviation point on, the game is no longer played with the original set of players. The deviating coalition becomes the new grand coalition which, in turn, induces a new dynamic game. The stage games of the new dynamical game depend on all previous allocation including those that have materialized from the deviating time on. We define three types of core solutions: fair core, stable core and credible core. We characterize the first two in case where the instantaneous game depends on the last allocation (rather than on the whole history of allocations) and the third in the general case. The analysis and the results resembles to a great extent the theory of non-cooperative dynamic games.
Syntactic Complexity of Finite/Cofinite, Definite, and Reverse Definite Languages
Venue: arXiv cs.FL 2012
Year: 2012

We study the syntactic complexity of finite/cofinite, definite and reverse definite languages. The syntactic complexity of a class of languages is defined as the maximal size of syntactic semigroups of languages from the class, taken as a function of the state complexity n of the languages. We prove that (n-1)! is a tight upper bound for finite/cofinite languages and that it can be reached only if the alphabet size is greater than or equal to (n-1)!-(n-2)!. We prove that the bound is also (n-1)! for reverse definite languages, but the minimal alphabet size is (n-1)!-2(n-2)!. We show that \lfloor e\cdot (n-1)!\rfloor is a lower bound on the syntactic complexity of definite languages, and conjecture that this is also an upper bound, and that the alphabet size required to meet this bound is \floor{e \cdot (n-1)!} - \floor{e \cdot (n-2)!}. We prove the conjecture for n\le 4.
Decorated proofs for computational effects: Exceptions
Venue: arXiv cs.LO 2012
Year: 2012

We define a proof system for exceptions which is close to the syntax for exceptions, in the sense that the exceptions do not appear explicitly in the type of any expression. This proof system is sound with respect to the intended denotational semantics of exceptions. With this inference system we prove several properties of exceptions.
On the Parameterized Intractability of Monadic Second-Order Logic
Venue: arXiv cs.LO 2012
Year: 2012

One of Courcelle's celebrated results states that if C is a class of graphs of bounded tree-width, then model-checking for monadic second order logic (MSO_2) is fixed-parameter tractable (fpt) on C by linear time parameterized algorithms, where the parameter is the tree-width plus the size of the formula. An immediate question is whether this is best possible or whether the result can be extended to classes of unbounded tree-width. In this paper we show that in terms of tree-width, the theorem cannot be extended much further. More specifically, we show that if C is a class of graphs which is closed under colourings and satisfies certain constructibility conditions and is such that the tree-width of C is not bounded by \log^{84} n then MSO_2-model checking is not fpt unless SAT can be solved in sub-exponential time. If the tree-width of C is not poly-logarithmically bounded, then MSO_2-model checking is not fpt unless all problems in the polynomial-time hierarchy can be solved in sub-exponential time.
A Game Theoretic Model for the Gaussian Broadcast Channel
Venue: arXiv cs.IT 2012
Year: 2012

The behavior of rational and selfish players (receivers) over a multiple-input multiple-output Gaussian broadcast channel is investigated using the framework of noncooperative game theory. In contrast to the game-theoretic model of the Gaussian multiple access channel where the set of feasible actions for each player is independent of other players' actions, the strategies of the players in the broadcast channel are mutually coupled, usually by a sum power or joint covariance constraint, and hence cannot be treated using traditional Nash equilibrium solution concepts. To characterize the strategic behavior of receivers connected to a single transmitter, this paper models the broadcast channel as a generalized Nash equilibrium problem with coupled constraints. The concept of normalized equilibrium (NoE) is used to characterize the equilibrium points and the existence and uniqueness of the NoE are proven for key scenarios.
Reconstruction error in a motion capture system
Venue: arXiv cs.CV 2012
Year: 2012

Marker-based motion capture (MoCap) systems can be composed by several dozens of cameras with the purpose of reconstructing the trajectories of hundreds of targets. With a large amount of cameras it becomes interesting to determine the optimal reconstruction strategy. For such aim it is of fundamental importance to understand the information provided by different camera measurements and how they are combined, i.e. how the reconstruction error changes by considering different cameras. In this work, first, an approximation of the reconstruction error variance is derived. The results obtained in some simulations suggest that the proposed strategy allows to obtain a good approximation of the real error variance with significant reduction of the computational time.
QoE-aware Media Streaming in Technology and Cost Heterogeneous Networks
Venue: arXiv cs.SY 2012
Year: 2012

We present a framework for studying the problem of media streaming in technology and cost heterogeneous environments. We first address the problem of efficient streaming in a technology-heterogeneous setting. We employ random linear network coding to simplify the packet selection strategies and alleviate issues such as duplicate packet reception. Then, we study the problem of media streaming from multiple cost-heterogeneous access networks. Our objective is to characterize analytically the trade-off between access cost and user experience. We model the Quality of user Experience (QoE) as the probability of interruption in playback as well as the initial waiting time. We design and characterize various control policies, and formulate the optimal control problem using a Markov Decision Process (MDP) with a probabilistic constraint. We present a characterization of the optimal policy using the Hamilton-Jacobi-Bellman (HJB) equation. For a fluid approximation model, we provide an exact and explicit characterization of a threshold policy and prove its optimality using the HJB equation. Our simulation results show that under properly designed control policy, the existence of alternative access technology as a complement for a primary access network can significantly improve the user experience without any bandwidth over-provisioning.
Cost-Effective Integration of MKM Semantic Services into Editing Environments
Venue: arXiv cs.HC 2012
Year: 2012

Integration of MKM services into editors has been of big interest in both formal as well as informal areas of MKM. Until now, most of the efforts to integrate MKM services into editing environments are done on an individual basis which results in high creation and maintenance costs. In this paper, I propose an architecture which allows editing environments and MKM services to be integrated in a more efficient way. This is accomplished by integrating editors and services only once with a real-time document synchronization and service broker. Doing so, simplifies the development of services as well as of editor integrations. My experience suggests that integrating new services into an arbitrary number of already integrated editors can take as little as 3-4 hours of work.
Possibilistic Answer Set Programming Revisited
Venue: arXiv cs.AI 2012
Year: 2012

Possibilistic answer set programming (PASP) extends answer set programming (ASP) by attaching to each rule a degree of certainty. While such an extension is important from an application point of view, existing semantics are not well-motivated, and do not always yield intuitive results. To develop a more suitable semantics, we first introduce a characterization of answer sets of classical ASP programs in terms of possibilistic logic where an ASP program specifies a set of constraints on possibility distributions. This characterization is then naturally generalized to define answer sets of PASP programs. We furthermore provide a syntactic counterpart, leading to a possibilistic generalization of the well-known Gelfond-Lifschitz reduct, and we show how our framework can readily be implemented using standard ASP solvers.
Solving Hybrid Influence Diagrams with Deterministic Variables
Venue: arXiv cs.AI 2012
Year: 2012

We describe a framework and an algorithm for solving hybrid influence diagrams with discrete, continuous, and deterministic chance variables, and discrete and continuous decision variables. A continuous chance variable in an influence diagram is said to be deterministic if its conditional distributions have zero variances. The solution algorithm is an extension of Shenoy's fusion algorithm for discrete influence diagrams. We describe an extended Shenoy-Shafer architecture for propagation of discrete, continuous, and utility potentials in hybrid influence diagrams that include deterministic chance variables. The algorithm and framework are illustrated by solving two small examples.
Parameter-Free Spectral Kernel Learning
Venue: arXiv cs.LG 2012
Year: 2012

Due to the growing ubiquity of unlabeled data, learning with unlabeled data is attracting increasing attention in machine learning. In this paper, we propose a novel semi-supervised kernel learning method which can seamlessly combine manifold structure of unlabeled data and Regularized Least-Squares (RLS) to learn a new kernel. Interestingly, the new kernel matrix can be obtained analytically with the use of spectral decomposition of graph Laplacian matrix. Hence, the proposed algorithm does not require any numerical optimization solvers. Moreover, by maximizing kernel target alignment on labeled data, we can also learn model parameters automatically with a closed-form solution. For a given graph Laplacian matrix, our proposed method does not need to tune any model parameter including the tradeoff parameter in RLS and the balance parameter for unlabeled data. Extensive experiments on ten benchmark datasets show that our proposed two-stage parameter-free spectral kernel learning algorithm can obtain comparable performance with fine-tuned manifold regularization methods in transductive setting, and outperform multiple kernel learning in supervised setting.
Maximizing the Spread of Cascades Using Network Design
Venue: arXiv cs.SI 2012
Year: 2012

We introduce a new optimization framework to maximize the expected spread of cascades in networks. Our model allows a rich set of actions that directly manipulate cascade dynamics by adding nodes or edges to the network. Our motivating application is one in spatial conservation planning, where a cascade models the dispersal of wild animals through a fragmented landscape. We propose a mixed integer programming (MIP) formulation that combines elements from network design and stochastic optimization. Our approach results in solutions with stochastic optimality guarantees and points to conservation strategies that are fundamentally different from naive approaches.
Risk Sensitive Path Integral Control
Venue: arXiv cs.SY 2012
Year: 2012

Recently path integral methods have been developed for stochastic optimal control for a wide class of models with non-linear dynamics in continuous space-time. Path integral methods find the control that minimizes the expected cost-to-go. In this paper we show that under the same assumptions, path integral methods generalize directly to risk sensitive stochastic optimal control. Here the method minimizes in expectation an exponentially weighted cost-to-go. Depending on the exponential weight, risk seeking or risk averse behaviour is obtained. We demonstrate the approach on risk sensitive stochastic optimal control problems beyond the linear-quadratic case, showing the intricate interaction of multi-modal control with risk sensitivity.
Learning Why Things Change: The Difference-Based Causality Learner
Venue: arXiv cs.AI 2012
Year: 2012

In this paper, we present the Difference- Based Causality Learner (DBCL), an algorithm for learning a class of discrete-time dynamic models that represents all causation across time by means of difference equations driving change in a system. We motivate this representation with real-world mechanical systems and prove DBCL's correctness for learning structure from time series data, an endeavour that is complicated by the existence of latent derivatives that have to be detected. We also prove that, under common assumptions for causal discovery, DBCL will identify the presence or absence of feedback loops, making the model more useful for predicting the effects of manipulating variables when the system is in equilibrium. We argue analytically and show empirically the advantages of DBCL over vector autoregression (VAR) and Granger causality models as well as modified forms of Bayesian and constraintbased structure discovery algorithms. Finally, we show that our algorithm can discover causal directions of alpha rhythms in human brains from EEG data.
Hybrid Generative/Discriminative Learning for Automatic Image Annotation
Venue: arXiv cs.LG 2012
Year: 2012

Automatic image annotation (AIA) raises tremendous challenges to machine learning as it requires modeling of data that are both ambiguous in input and output, e.g., images containing multiple objects and labeled with multiple semantic tags. Even more challenging is that the number of candidate tags is usually huge (as large as the vocabulary size) yet each image is only related to a few of them. This paper presents a hybrid generative-discriminative classifier to simultaneously address the extreme data-ambiguity and overfitting-vulnerability issues in tasks such as AIA. Particularly: (1) an Exponential-Multinomial Mixture (EMM) model is established to capture both the input and output ambiguity and in the meanwhile to encourage prediction sparsity; and (2) the prediction ability of the EMM model is explicitly maximized through discriminative learning that integrates variational inference of graphical models and the pairwise formulation of ordinal regression. Experiments show that our approach achieves both superior annotation performance and better tag scalability.
Solving Multistage Influence Diagrams using Branch-and-Bound Search
Venue: arXiv cs.AI 2012
Year: 2012

A branch-and-bound approach to solving influ- ence diagrams has been previously proposed in the literature, but appears to have never been implemented and evaluated - apparently due to the difficulties of computing effective bounds for the branch-and-bound search. In this paper, we describe how to efficiently compute effective bounds, and we develop a practical implementa- tion of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solving influence diagrams with multiple stages.
Invariant Gaussian Process Latent Variable Models and Application in Causal Discovery
Venue: arXiv cs.LG 2012
Year: 2012

In nonlinear latent variable models or dynamic models, if we consider the latent variables as confounders (common causes), the noise dependencies imply further relations between the observed variables. Such models are then closely related to causal discovery in the presence of nonlinear confounders, which is a challenging problem. However, generally in such models the observation noise is assumed to be independent across data dimensions, and consequently the noise dependencies are ignored. In this paper we focus on the Gaussian process latent variable model (GPLVM), from which we develop an extended model called invariant GPLVM (IGPLVM), which can adapt to arbitrary noise covariances. With the Gaussian process prior put on a particular transformation of the latent nonlinear functions, instead of the original ones, the algorithm for IGPLVM involves almost the same computational loads as that for the original GPLVM. Besides its potential application in causal discovery, IGPLVM has the advantage that its estimated latent nonlinear manifold is invariant to any nonsingular linear transformation of the data. Experimental results on both synthetic and realworld data show its encouraging performance in nonlinear manifold learning and causal discovery.
A Sensitive Attribute based Clustering Method for kanonymization
Venue: arXiv cs.CR 2012
Year: 2012

In medical organizations large amount of personal data are collected and analyzed by the data miner or researcher, for further perusal. However, the data collected may contain sensitive information such as specific disease of a patient and should be kept confidential. Hence, the analysis of such data must ensure due checks that ensure protection against threats to the individual privacy. In this context, greater emphasis has now been given to the privacy preservation algorithms in data mining research. One of the approaches is anonymization approach that is able to protect private information; however, valuable information can be lost. Therefore, the main challenge is how to minimize the information loss during an anonymization process. The proposed method is grouping similar data together based on sensitive attribute and then anonymizes them. Our experimental results show the proposed method offers better outcomes with respect to information loss and execution time.
An Improved Traffic Matrix Decomposition Method with Frequency-Domain Regularization
Venue: arXiv cs.NI 2012
Year: 2012

We propose a novel network traffic matrix decomposition method named Stable Principal Component Pursuit with Frequency-Domain Regularization (SPCP-FDR), which improves the Stable Principal Component Pursuit (SPCP) method by using a frequency-domain noise regularization function. An experiment demonstrates the feasibility of this new decomposition method.
Theory and Applications of Compressed Sensing
Venue: arXiv cs.IT 2012
Year: 2012

Compressed sensing is a novel research area, which was introduced in 2006, and since then has already become a key concept in various areas of applied mathematics, computer science, and electrical engineering. It surprisingly predicts that high-dimensional signals, which allow a sparse representation by a suitable basis or, more generally, a frame, can be recovered from what was previously considered highly incomplete linear measurements by using efficient algorithms. This article shall serve as an introduction to and a survey about compressed sensing.
Decentralized Probabilistic Auto-Scaling for Heterogeneous Systems
Venue: arXiv cs.DC 2012
Year: 2012

The DEPAS (Decentralized Probabilistic Auto-Scaling) algorithm assumes an overlay network of computing nodes where each node probabilistically decides to shut down, allocate one or more other nodes or do nothing. DEPAS was formulated, tested, and theoretically analyzed for the simplified case of homogenous systems. In this paper, we extend DEPAS to heterogeneous systems.
Preserving Co-Location Privacy in Geo-Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

The number of people on social networks has grown exponentially. Users share very large volumes of personal informations and content every days. This content could be tagged with geo-spatial and temporal coordinates that may be considered sensitive for some users. While there is clearly a demand for users to share this information with each other, there is also substantial demand for greater control over the conditions under which their information is shared. Content published in a geo-aware social networks (GeoSN) often involves multiple users and it is often accessible to multiple users, without the publisher being aware of the privacy preferences of those users. This makes difficult for GeoSN users to control which information about them is available and to whom it is available. Thus, the lack of means to protect users privacy scares people bothered about privacy issues. This paper addresses a particular privacy threats that occur in GeoSNs: the Co-location privacy threat. It concerns the availability of information about the presence of multiple users in a same locations at given times, against their will. The challenge addressed is that of supporting privacy while still enabling useful services.
Your Facebook Deactivated Friend or a Cloaked Spy (Extended Abstract)
Venue: arXiv cs.SI 2012
Year: 2012

With over 750 million active users, Facebook is the most famous social networking website. One particular aspect of Facebook widely discussed in the news and heavily researched in academic circles is the privacy of its users. In this paper we introduce a zero day privacy loophole in Facebook. We call this the deactivated friend attack. The concept of the attack is very similar to cloaking in Star Trek while its seriousness could be estimated from the fact that once the attacker is a friend of the victim, it is highly probable the attacker has indefinite access to the victims private information in a cloaked way. We demonstrate the impact of the attack by showing the ease of gaining trust of Facebook users and being befriended online. With targeted friend requests we were able to add over 4300 users and maintain access to their Facebook profile information for at least 261 days. No user was able to unfriend us during this time due to cloaking and short de-cloaking sessions. The short de-cloaking sessions were enough to get updates about the victims. We also provide several solutions for the loophole, which range from mitigation to a permanent solution
Irida: A real-time Wireless Sensor Network visualization feedback protocol
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we describe the implementation of a real time visualization and feedback system for Wireless Sensor Network algorithms. The system is based on a fixed hardware testbed, which is deployed on a vertical flat surface and a feedback loop system that takes information about the current state of the network and projects this state, in a visual way, on the surface itself using a video projector. The protocol used is open and simple to use, and can be easily adapted for different hardware configurations. We call our system Irida.
Robust Filtering and Smoothing with Gaussian Processes
Venue: arXiv cs.SY 2012
Year: 2012

We propose a principled algorithm for robust Bayesian filtering and smoothing in nonlinear stochastic dynamic systems when both the transition function and the measurement function are described by non-parametric Gaussian process (GP) models. GPs are gaining increasing importance in signal processing, machine learning, robotics, and control for representing unknown system functions by posterior probability distributions. This modern way of "system identification" is more robust than finding point estimates of a parametric function representation. In this article, we present a principled algorithm for robust analytic smoothing in GP dynamic systems, which are increasingly used in robotics and control. Our numerical evaluations demonstrate the robustness of the proposed approach in situations where other state-of-the-art Gaussian filters and smoothers can fail.