OpenRaiser/Intern-Atlas huggingface dataset:
Maximizing submodular functions using probabilistic graphical models
Venue: arXiv cs.LG 2013
Year: 2013

We consider the problem of maximizing submodular functions; while this problem is known to be NP-hard, several numerically efficient local search techniques with approximation guarantees are available. In this paper, we propose a novel convex relaxation which is based on the relationship between submodular functions, entropies and probabilistic graphical models. In a graphical model, the entropy of the joint distribution decomposes as a sum of marginal entropies of subsets of variables; moreover, for any distribution, the entropy of the closest distribution factorizing in the graphical model provides an bound on the entropy. For directed graphical models, this last property turns out to be a direct consequence of the submodularity of the entropy function, and allows the generalization of graphical-model-based upper bounds to any submodular functions. These upper bounds may then be jointly maximized with respect to a set, while minimized with respect to the graph, leading to a convex variational inference scheme for maximizing submodular functions, based on outer approximations of the marginal polytope and maximum likelihood bounded treewidth structures. By considering graphs of increasing treewidths, we may then explore the trade-off between computational complexity and tightness of the relaxation. We also present extensions to constrained problems and maximizing the difference of submodular functions, which include all possible set functions.
CrowdPlanner: A Crowd-Based Route Recommendation System
Venue: arXiv cs.DB 2013
Year: 2013

CrowdPlanner -- a novel crowd-based route recommendation system has been developed, which requests human workers to evaluate candidates routes recommended by different sources and methods, and determine the best route based on the feedbacks of these workers. Our system addresses two critical issues in its core components: a) task generation component generates a series of informative and concise questions with optimized ordering for a given candidate route set so that workers feel comfortable and easy to answer; and b) worker selection component utilizes a set of selection criteria and an efficient algorithm to find the most eligible workers to answer the questions with high accuracy.
Energt Efficient MAC Protocols for Wireless Sensor Network: A Survey
Venue: arXiv cs.IT 2013
Year: 2013

Wireless Sensor Network (WSN) is an attractive choice for a variety of applications as no wired infrastructure is needed. Other wireless networks are not as energy constrained as WSNs, because they may be plugged into the mains supply or equipped with batteries that are rechargeable and replaceable. Among others, one of the main sources of energy depletion in WSN is communications controlled by the Medium Access Control (MAC) protocols. An extensive survey of energy efficient MAC protocols is presented in this article. We categorise WSN MAC protocols in the following categories: controlled access (CA), random access (RA), slotted protocols (SP) and hybrid protocols (HP). We further discuss how energy efficient MAC protocols have developed from fixed sleep/wake cycles through adaptive to dynamic cycles, thus becoming more responsive to traffic load variations. Finally we present open research questions on MAC layer design for WSNs in terms of energy efficiency
What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives
Venue: arXiv cs.LO 2013
Year: 2013

We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages extends regular languages to infinite strings and provides a robust specification language to express all properties used in verification, and parity objectives are canonical forms to express ω-regular conditions. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satis- fied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite- memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives.
Rigorous high-precision computation of the Hurwitz zeta function and its derivatives
Venue: arXiv cs.SC 2013
Year: 2013

We study the use of the Euler-Maclaurin formula to numerically evaluate the Hurwitz zeta function $ζ(s,a)$ for $s, a \in \mathbb{C}$, along with an arbitrary number of derivatives with respect to $s$, to arbitrary precision with rigorous error bounds. Techniques that lead to a fast implementation are discussed. We present new record computations of Stieltjes constants, Keiper-Li coefficients and the first nontrivial zero of the Riemann zeta function, obtained using an open source implementation of the algorithms described in this paper.
Convex relaxations of structured matrix factorizations
Venue: arXiv cs.LG 2013
Year: 2013

We consider the factorization of a rectangular matrix $X $ into a positive linear combination of rank-one factors of the form $u v^\top$, where $u$ and $v$ belongs to certain sets $\mathcal{U}$ and $\mathcal{V}$, that may encode specific structures regarding the factors, such as positivity or sparsity. In this paper, we show that computing the optimal decomposition is equivalent to computing a certain gauge function of $X$ and we provide a detailed analysis of these gauge functions and their polars. Since these gauge functions are typically hard to compute, we present semi-definite relaxations and several algorithms that may recover approximate decompositions with approximation guarantees. We illustrate our results with simulations on finding decompositions with elements in $\{0,1\}$. As side contributions, we present a detailed analysis of variational quadratic representations of norms as well as a new iterative basis pursuit algorithm that can deal with inexact first-order oracles.
A method for nose-tip based 3D face registration using maximum intensity algorithm
Venue: arXiv cs.CV 2013
Year: 2013

In this paper we present a novel technique of registering 3D images across pose. In this context, we have taken into account the images which are aligned across X, Y and Z axes. We have first determined the angle across which the image is rotated with respect to X, Y and Z axes and then translation is performed on the images. After testing the proposed method on 472 images from the FRAV3D database, the method correctly registers 358 images thus giving a performance rate of 75.84%.
On Determining Deep Holes of Generalized Reed-Solomon Codes
Venue: arXiv cs.IT 2013
Year: 2013

For a linear code, deep holes are defined to be vectors that are further away from codewords than all other vectors. The problem of deciding whether a received word is a deep hole for generalized Reed-Solomon codes is proved to be co-NP-complete. For the extended Reed-Solomon codes $RS_q(\F_q,k)$, a conjecture was made to classify deep holes by Cheng and Murray in 2007. Since then a lot of effort has been made to prove the conjecture, or its various forms. In this paper, we classify deep holes completely for generalized Reed-Solomon codes $RS_p (D,k)$, where $p$ is a prime, $|D| > k \geqslant \frac{p-1}{2}$. Our techniques are built on the idea of deep hole trees, and several results concerning the Erd{ö}s-Heilbronn conjecture.
Ultrametric Component Analysis with Application to Analysis of Text and of Emotion
Venue: arXiv cs.AI 2013
Year: 2013

We review the theory and practice of determining what parts of a data set are ultrametric. It is assumed that the data set, to begin with, is endowed with a metric, and we include discussion of how this can be brought about if a dissimilarity, only, holds. The basis for part of the metric-endowed data set being ultrametric is to consider triplets of the observables (vectors). We develop a novel consensus of hierarchical clusterings. We do this in order to have a framework (including visualization and supporting interpretation) for the parts of the data that are determined to be ultrametric. Furthermore a major objective is to determine locally ultrametric relationships as opposed to non-local ultrametric relationships. As part of this work, we also study a particular property of our ultrametricity coefficient, namely, it being a function of the difference of angles of the base angles of the isosceles triangle. This work is completed by a review of related work, on consensus hierarchies, and of a major new application, namely quantifying and interpreting the emotional content of narrative.
Automatically Extracting Instances of Code Change Patterns with AST Analysis
Venue: arXiv cs.SE 2013
Year: 2013

A code change pattern represents a kind of recurrent modification in software. For instance, a known code change pattern consists of the change of the conditional expression of an if statement. Previous work has identified different change patterns. Complementary to the identification and definition of change patterns, the automatic extraction of pattern instances is essential to measure their empirical importance. For example, it enables one to count and compare the number of conditional expression changes in the history of different projects. In this paper we present a novel approach for search patterns instances from software history. Our technique is based on the analysis of Abstract Syntax Trees (AST) files within a given commit. We validate our approach by counting instances of 18 change patterns in 6 open-source Java projects.
Exploring Image Virality in Google Plus
Venue: arXiv cs.SI 2013
Year: 2013

Reactions to posts in an online social network show different dynamics depending on several textual features of the corresponding content. Do similar dynamics exist when images are posted? Exploiting a novel dataset of posts, gathered from the most popular Google+ users, we try to give an answer to such a question. We describe several virality phenomena that emerge when taking into account visual characteristics of images (such as orientation, mean saturation, etc.). We also provide hypotheses and potential explanations for the dynamics behind them, and include cases for which common-sense expectations do not hold true in our experiments.
SafeJS: Hermetic Sandboxing for JavaScript
Venue: arXiv cs.PL 2013
Year: 2013

Isolating programs is an important mechanism to support more secure applications. Isolating program in dynamic languages such as JavaScript is even more challenging since reflective operations can circumvent simple mechanisms that could protect program parts. In this article we present SafeJS, an approach and implementation that offers isolation based on separate sandboxes and control of information exchanged between them. In SafeJS, sandboxes based on web workers do not share any data. Data exchanged between sandboxes is solely based on strings. Using different policies, this infrastructure supports the isolation of the different scripts that usually populate web pages. A foreign component cannot modify the main DOM tree in unexpected manner. Our SafeJS implementation is currently being used in an industrial setting in the context of the Resilience FUI 12 project.
Computational Methods for Probabilistic Inference of Sector Congestion in Air Traffic Management
Venue: arXiv cs.AI 2013
Year: 2013

This article addresses the issue of computing the expected cost functions from a probabilistic model of the air traffic flow and capacity management. The Clenshaw-Curtis quadrature is compared to Monte-Carlo algorithms defined specifically for this problem. By tailoring the algorithms to this model, we reduce the computational burden in order to simulate real instances. The study shows that the Monte-Carlo algorithm is more sensible to the amount of uncertainty in the system, but has the advantage to return a result with the associated accuracy on demand. The performances for both approaches are comparable for the computation of the expected cost of delay and the expected cost of congestion. Finally, this study shows some evidences that the simulation of the proposed probabilistic model is tractable for realistic instances.
An Investigation of Data Privacy and Utility Preservation using KNN Classification as a Gauge
Venue: arXiv cs.CR 2013
Year: 2013

It is obligatory that organizations by law safeguard the privacy of individuals when handling data sets containing personal identifiable information (PII). Nevertheless, during the process of data privatization, the utility or usefulness of the privatized data diminishes. Yet achieving the optimal balance between data privacy and utility needs has been documented as an NP-hard challenge. In this study, we investigate data privacy and utility preservation using KNN machine learning classification as a gauge.
Learning a Loopy Model For Semantic Segmentation Exactly
Venue: arXiv cs.LG 2013
Year: 2013

Learning structured models using maximum margin techniques has become an indispensable tool for com- puter vision researchers, as many computer vision applications can be cast naturally as an image labeling problem. Pixel-based or superpixel-based conditional random fields are particularly popular examples. Typ- ically, neighborhood graphs, which contain a large number of cycles, are used. As exact inference in loopy graphs is NP-hard in general, learning these models without approximations is usually deemed infeasible. In this work we show that, despite the theoretical hardness, it is possible to learn loopy models exactly in practical applications. To this end, we analyze the use of multiple approximate inference techniques together with cutting plane training of structural SVMs. We show that our proposed method yields exact solutions with an optimality guarantees in a computer vision application, for little additional computational cost. We also propose a dynamic caching scheme to accelerate training further, yielding runtimes that are comparable with approximate methods. We hope that this insight can lead to a reconsideration of the tractability of loopy models in computer vision.
Compression via Compressive Sensing : A Low-Power Framework for the Telemonitoring of Multi-Channel Physiological Signals
Venue: arXiv cs.IT 2013
Year: 2013

Telehealth and wearable equipment can deliver personal healthcare and necessary treatment remotely. One major challenge is transmitting large amount of biosignals through wireless networks. The limited battery life calls for low-power data compressors. Compressive Sensing (CS) has proved to be a low-power compressor. In this study, we apply CS on the compression of multichannel biosignals. We firstly develop an efficient CS algorithm from the Block Sparse Bayesian Learning (BSBL) framework. It is based on a combination of the block sparse model and multiple measurement vector model. Experiments on real-life Fetal ECGs showed that the proposed algorithm has high fidelity and efficiency. Implemented in hardware, the proposed algorithm was compared to a Discrete Wavelet Transform (DWT) based algorithm, verifying the proposed one has low power consumption and occupies less computational resources.
Report: GPU Based Massive Parallel Kawasaki Kinetics In Monte Carlo Modelling of Lipid Microdomains
Venue: arXiv cs.DC 2013
Year: 2013

This paper introduces novel method of simulation of lipid biomembranes based on Metropolis Hastings algorithm and Graphic Processing Unit computational power. Method gives up to 55 times computational boost in comparison to classical computations. Extensive study of algorithm correctness is provided. Analysis of simulation results and results obtained with classical simulation methodologies are presented.
Energy Aware Error Control in Cooperative Communication in Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Due to small size of sensor nodes deployed in Wireless Sensor Networks (WSNs), energy utilization is a key issue. Poor channel conditions lead to retransmissions and hence, result in energy wastage. Error control strategies are usually utilized to accommodate channel impairments like noise and fading in order to optimize energy consumption for network lifetime enhancement. Meanwhile, cooperative communication also emerges to be an appropriate candidate to combat the effects of channel fading. Energy efficiency of cooperative scheme when applied with Automatic Repeat Request (ARQ), Hybrid-ARQ (HARQ) and Forward Error Correction (FEC) is investigated in this work. Moreover, the expressions for energy efficiency of Direct Transmission, Single Relay Cooperation and Multi Relay Cooperation are also derived. In all, our work is focused towards energy optimal communication in WSNs. Our results show that error control strategies with cooperative schemes can significantly enhance system performance in form of energy optimization.
Faster Fair Solution for the Reader-Writer Problem
Venue: arXiv cs.DC 2013
Year: 2013

A fast fair solution for Reader-Writer Problem is presented.
Further results on "Velocity-position integration formula, part I-Application to in-flight alignment"
Venue: arXiv cs.RO 2013
Year: 2013

This note improves our above-mentioned recent work by effectively depressing the adverse effect of the lever arm on attitude estimation.
Four-Pose Synthesis of Angle-Symmetric 6R Linkages
Venue: arXiv cs.RO 2013
Year: 2013

We use the recently introduced factorization theory of motion polynomials over the dual quaternions for the synthesis of closed kinematic loops with six revolute joints that visit four prescribed poses. Our approach admits either no or a one-parametric family of solutions. We suggest strategies for picking good solutions from this family.
HOL(y)Hammer: Online ATP Service for HOL Light
Venue: arXiv cs.AI 2013
Year: 2013

HOL(y)Hammer is an online AI/ATP service for formal (computer-understandable) mathematics encoded in the HOL Light system. The service allows its users to upload and automatically process an arbitrary formal development (project) based on HOL Light, and to attack arbitrary conjectures that use the concepts defined in some of the uploaded projects. For that, the service uses several automated reasoning systems combined with several premise selection methods trained on all the project proofs. The projects that are readily available on the server for such query answering include the recent versions of the Flyspeck, Multivariate Analysis and Complex Analysis libraries. The service runs on a 48-CPU server, currently employing in parallel for each task 7 AI/ATP combinations and 4 decision procedures that contribute to its overall performance. The system is also available for local installation by interested users, who can customize it for their own proof development. An Emacs interface allowing parallel asynchronous queries to the service is also provided. The overall structure of the service is outlined, problems that arise and their solutions are discussed, and an initial account of using the system is given.
A Comparative Analysis of Ensemble Classifiers: Case Studies in Genomics
Venue: arXiv cs.LG 2013
Year: 2013

The combination of multiple classifiers using ensemble methods is increasingly important for making progress in a variety of difficult prediction problems. We present a comparative analysis of several ensemble methods through two case studies in genomics, namely the prediction of genetic interactions and protein functions, to demonstrate their efficacy on real-world datasets and draw useful conclusions about their behavior. These methods include simple aggregation, meta-learning, cluster-based meta-learning, and ensemble selection using heterogeneous classifiers trained on resampled data to improve the diversity of their predictions. We present a detailed analysis of these methods across 4 genomics datasets and find the best of these methods offer statistically significant improvements over the state of the art in their respective domains. In addition, we establish a novel connection between ensemble selection and meta-learning, demonstrating how both of these disparate methods establish a balance between ensemble diversity and performance.
Abstract interpretation-based approaches to Security - A Survey on Abstract Non-Interference and its Challenging Applications
Venue: arXiv cs.PL 2013
Year: 2013

In this paper we provide a survey on the framework of abstract non-interference. In particular, we describe a general formalization of abstract non-interference by means of three dimensions (observation, protection and semantics) that can be instantiated in order to obtain well known or even new weakened non-interference properties. Then, we show that the notions of abstract non-interference introduced in language-based security are instances of this more general framework which allows to better understand the different components of a non-interference policy. Finally, we consider two challenging research fields concerning security where abstract non-interference seems a promising approach providing new perspectives and new solutions to open problems: Code injection and code obfuscation.
Cryptanalysis of Wu and Xu's authentication scheme for Telecare Medicine Information Systems
Venue: arXiv cs.CR 2013
Year: 2013

Remote user authentication is desirable for a Telecare medicine information system (TMIS) to verify the correctness of remote users. In 2013, Jiang et al. proposed privacy preserving authentication scheme for TMIS. Recently, Wu and Xu analyzed Jiang's scheme and identify serious security flaws in their scheme, namely, user impersonation attack, DoS attack and off-line password guessing attack. In this article, we analyze Wu and Xu's scheme and show that their scheme is also vulnerable to off-line password guessing attack and does not protect user anonymity. Moreover, we identify the inefficiency of incorrect input detection of the login phase in Wu and Xu's scheme, where the smart card executes the login session in-spite of wrong input.
Speeding up Deciphering by Hypergraph Ordering
Venue: arXiv cs.CR 2013
Year: 2013

The "Gluing Algorithm" of Semaev [Des.\ Codes Cryptogr.\ 49 (2008), 47--60] --- that finds all solutions of a sparse system of linear equations over the Galois field $GF(q)$ --- has average running time $O(mq^{\max \left\vert \cup_{1}^{k}X_{j}\right\vert -k}), $ where $m$ is the total number of equations, and $\cup_{1}^{k}X_{j}$ is the set of all unknowns actively occurring in the first $k$ equations. Our goal here is to minimize the exponent of $q$ in the case where every equation contains at most three unknowns. %Applying hypergraph-theoretic methods we prove The main result states that if the total number $\left\vert \cup_{1}^{m}X_{j}\right\vert$ of unknowns is equal to $m$, then the best achievable exponent is between $c_1m$ and $c_2m$ for some positive constants $c_1$ and $c_2.$