OpenRaiser/Intern-Atlas huggingface dataset:
Dual Averaging on Compactly-Supported Distributions And Application to No-Regret Learning on a Continuum
Venue: arXiv cs.LG 2015
Year: 2015

We consider an online learning problem on a continuum. A decision maker is given a compact feasible set $S$, and is faced with the following sequential problem: at iteration~$t$, the decision maker chooses a distribution $x^{(t)} \in Δ(S)$, then a loss function $\ell^{(t)} : S \to \mathbb{R}_+$ is revealed, and the decision maker incurs expected loss $\langle \ell^{(t)}, x^{(t)} \rangle = \mathbb{E}_{s \sim x^{(t)}} \ell^{(t)}(s)$. We view the problem as an online convex optimization problem on the space $Δ(S)$ of Lebesgue-continnuous distributions on $S$. We prove a general regret bound for the Dual Averaging method on $L^2(S)$, then prove that dual averaging with $ω$-potentials (a class of strongly convex regularizers) achieves sublinear regret when $S$ is uniformly fat (a condition weaker than convexity).
Skew cyclic codes over $\mathbb{F}_{q}+v\mathbb{F}_{q}+v^{2}\mathbb{F}_{q}$
Venue: arXiv cs.IT 2015
Year: 2015

In this article, we study skew cyclic codes over ring $R=\mathbb{F}_{q}+v\mathbb{F}_{q}+v^{2}\mathbb{F}_{q}$, where $q=p^{m}$, $p$ is an odd prime and $v^{3}=v$. We describe generator polynomials of skew cyclic codes over this ring and investigate the structural properties of skew cyclic codes over $R$ by a decomposition theorem. We also describe the generator polynomials of the duals of skew cyclic codes. Moreover, the idempotent generators of skew cyclic codes over $\mathbb{F}_{q}$ and $R$ are considered.
Anonymous On-line Communication Between Program Analyses
Venue: arXiv cs.PL 2015
Year: 2015

We propose a light-weight client-server model of communication between existing implementations of different program analyses. The communication is on-line and anonymous which means that all analyses simultaneously analyse the same program and an analysis does not know what other analyses participate in the communication. The anonymity and model's strong emphasis on independence of analyses allow to preserve almost everything in existing implementations. An analysis only has to add an implementation of a proposed communication protocol, determine places in its code where information from others would help, and then check whether there is no communication scenario, which would corrupt its result. We demonstrate functionality and effectiveness of the proposed communication model in a detailed case study with three analyses: two abstract interpreters and the classic symbolic execution. Results of the evaluation on SV-COMP benchmarks show impressive improvements in computed invariants and increased counts of successfully analysed benchmarks.
ASTROMLSKIT: A New Statistical Machine Learning Toolkit: A Platform for Data Analytics in Astronomy
Venue: arXiv cs.CE 2015
Year: 2015

Astroinformatics is a new impact area in the world of astronomy, occasionally called the final frontier, where several astrophysicists, statisticians and computer scientists work together to tackle various data intensive astronomical problems. Exponential growth in the data volume and increased complexity of the data augments difficult questions to the existing challenges. Classical problems in Astronomy are compounded by accumulation of astronomical volume of complex data, rendering the task of classification and interpretation incredibly laborious. The presence of noise in the data makes analysis and interpretation even more arduous. Machine learning algorithms and data analytic techniques provide the right platform for the challenges posed by these problems. A diverse range of open problem like star-galaxy separation, detection and classification of exoplanets, classification of supernovae is discussed. The focus of the paper is the applicability and efficacy of various machine learning algorithms like K Nearest Neighbor (KNN), random forest (RF), decision tree (DT), Support Vector Machine (SVM), Naïve Bayes and Linear Discriminant Analysis (LDA) in analysis and inference of the decision theoretic problems in Astronomy. The machine learning algorithms, integrated into ASTROMLSKIT, a toolkit developed in the course of the work, have been used to analyze HabCat data and supernovae data. Accuracy has been found to be appreciably good.
Improved repeatability measures for evaluating performance of feature detectors
Venue: arXiv cs.CV 2015
Year: 2015

The most frequently employed measure for performance characterisation of local feature detectors is repeatability, but it has been observed that this does not necessarily mirror actual performance. Presented are improved repeatability formulations which correlate much better with the true performance of feature detectors. Comparative results for several state-of-the-art feature detectors are presented using these measures; it is found that Hessian-based detectors are generally superior at identifying features when images are subject to various geometric and photometric transformations.
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
Venue: arXiv cs.DS 2015
Year: 2015

Given an undirected graph with edge costs and node weights, the minimum bisection problem asks for a partition of the nodes into two parts of equal weight such that the sum of edge costs between the parts is minimized. We give a polynomial time bicriteria approximation scheme for bisection on planar graphs. Specifically, let $W$ be the total weight of all nodes in a planar graph $G$. For any constant $\varepsilon > 0$, our algorithm outputs a bipartition of the nodes such that each part weighs at most $W/2 + \varepsilon$ and the total cost of edges crossing the partition is at most $(1+\varepsilon)$ times the total cost of the optimal bisection. The previously best known approximation for planar minimum bisection, even with unit node weights, was $O(\log n)$. Our algorithm actually solves a more general problem where the input may include a target weight for the smaller side of the bipartition.
Streaming Algorithms for Submodular Function Maximization
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of maximizing a nonnegative submodular set function $f:2^{\mathcal{N}} \rightarrow \mathbb{R}^+$ subject to a $p$-matchoid constraint in the single-pass streaming setting. Previous work in this context has considered streaming algorithms for modular functions and monotone submodular functions. The main result is for submodular functions that are {\em non-monotone}. We describe deterministic and randomized algorithms that obtain a $Ω(\frac{1}{p})$-approximation using $O(k \log k)$-space, where $k$ is an upper bound on the cardinality of the desired set. The model assumes value oracle access to $f$ and membership oracles for the matroids defining the $p$-matchoid constraint.
Trust, but Verify: Two-Phase Typing for Dynamic Languages
Venue: arXiv cs.PL 2015
Year: 2015

A key challenge when statically typing so-called dynamic languages is the ubiquity of value-based overloading, where a given function can dynamically reflect upon and behave according to the types of its arguments. Thus, to establish basic types, the analysis must reason precisely about values, but in the presence of higher-order functions and polymorphism, this reasoning itself can require basic types. In this paper we address this chicken-and-egg problem by introducing the framework of two-phased typing. The first "trust" phase performs classical, i.e. flow-, path- and value-insensitive type checking to assign basic types to various program expressions. When the check inevitably runs into "errors" due to value-insensitivity, it wraps problematic expressions with DEAD-casts, which explicate the trust obligations that must be discharged by the second phase. The second phase uses refinement typing, a flow- and path-sensitive analysis, that decorates the first phase's types with logical predicates to track value relationships and thereby verify the casts and establish other correctness properties for dynamically typed languages.
Efectividad de técnicas de prueba de software aplicadas por sujetos novicios de pregrado
Venue: arXiv cs.SE 2015
Year: 2015

The main objective of this work is to examine possible effects of using freshman student subjects in software engineering experiments. Particularly in this work we report the effectiveness measured as percentage of observed and observable defects of two software testing techniques: Black-box and white-box. Regarding observed defects, both techniques show an effectiveness around of 4%. With respect of observable defects by test cases, black-box testing is slightly more effective (21%) than white-box testing (16%), although this difference is not significant. We observe a considerable lack of technical skills of subjects for applying both software testing techniques. Due to observed findings, we suggest to employ students with more technical skills for carrying out software engineering experiments. ----- El objetivo de este trabajo se centra en investigar los efectos que conlleva realizar experimentos en ingeniería de software (IS) empleando como sujetos experimentales a estudiantes de pregrado cursando su primer año de estudios de la carrera en ingeniería de software. De manera particular en este trabajo se investiga la efectividad medida en porcentaje de defectos observados y observables de las técnicas de prueba de software funcional (caja negra) y estructural (caja blanca). Con respecto a los defectos observados por los sujetos, ambas técnicas obtuvieron una efectividad del 4%. Con respecto a los defectos observables por los casos de prueba, la técnica funcional es ligeramente superior (21%) que la técnica estructural (16%), aunque esta diferencia no es significativa. Se observa un nivel de inexperiencia considerable en los sujetos para aplicar las técnicas. Dado los hallazgos encontrados, se sugiere emplear sujetos de pregrado con un nivel mayor de experiencia.
Monte Carlo Motion Planning for Robot Trajectory Optimization Under Uncertainty
Venue: arXiv cs.RO 2015
Year: 2015

This article presents a novel approach, named MCMP (Monte Carlo Motion Planning), to the problem of motion planning under uncertainty, i.e., to the problem of computing a low-cost path that fulfills probabilistic collision avoidance constraints. MCMP estimates the collision probability (CP) of a given path by sampling via Monte Carlo the execution of a reference tracking controller (in this paper we consider LQG). The key algorithmic contribution of this paper is the design of statistical variance-reduction techniques, namely control variates and importance sampling, to make such a sampling procedure amenable to real-time implementation. MCMP applies this CP estimation procedure to motion planning by iteratively (i) computing an (approximately) optimal path for the deterministic version of the problem (here, using the FMT* algorithm), (ii) computing the CP of this path, and (iii) inflating or deflating the obstacles by a common factor depending on whether the CP is higher or lower than a target value. The advantages of MCMP are threefold: (i) asymptotic correctness of CP estimation, as opposed to most current approximations, which, as shown in this paper, can be off by large multiples and hinder the computation of feasible plans; (ii) speed and parallelizability, and (iii) generality, i.e., the approach is applicable to virtually any planning problem provided that a path tracking controller and a notion of distance to obstacles in the configuration space are available. Numerical results illustrate the correctness (in terms of feasibility), efficiency (in terms of path cost), and computational speed of MCMP.
Verification of Generalized Inconsistency-Aware Knowledge and Action Bases (Extended Version)
Venue: arXiv cs.AI 2015
Year: 2015

Knowledge and Action Bases (KABs) have been put forward as a semantically rich representation of a domain, using a DL KB to account for its static aspects, and actions to evolve its extensional part over time, possibly introducing new objects. Recently, KABs have been extended to manage inconsistency, with ad-hoc verification techniques geared towards specific semantics. This work provides a twofold contribution along this line of research. On the one hand, we enrich KABs with a high-level, compact action language inspired by Golog, obtaining so called Golog-KABs (GKABs). On the other hand, we introduce a parametric execution semantics for GKABs, so as to elegantly accomodate a plethora of inconsistency-aware semantics based on the notion of repair. We then provide several reductions for the verification of sophisticated first-order temporal properties over inconsistency-aware GKABs, and show that it can be addressed using known techniques, developed for standard KABs.
Parameterized Algorithms for Deletion to (r,l)-graphs
Venue: arXiv cs.CC 2015
Year: 2015

For fixed integers $r,\ell \geq 0$, a graph $G$ is called an {\em $(r,\ell)$-graph} if the vertex set $V(G)$ can be partitioned into $r$ independent sets and $\ell$ cliques. This brings us to the following natural parameterized questions: {\sc Vertex $(r,\ell)$-Partization} and {\sc Edge $(r,\ell)$-Partization}. An input to these problems consist of a graph $G$ and a positive integer $k$ and the objective is to decide whether there exists a set $S\subseteq V(G)$ ($S\subseteq E(G)$) such that the deletion of $S$ from $G$ results in an $(r,\ell)$-graph. These problems generalize well studied problems such as {\sc Odd Cycle Transversal}, {\sc Edge Odd Cycle Transversal}, {\sc Split Vertex Deletion} and {\sc Split Edge Deletion}. We do not hope to get parameterized algorithms for either {\sc Vertex $(r,\ell)$-Partization} or {\sc Edge $(r,\ell)$-Partization} when either of $r$ or $\ell$ is at least $3$ as the recognition problem itself is NP-complete. This leaves the case of $r,\ell \in \{1,2\}$. We almost complete the parameterized complexity dichotomy for these problems. Only the parameterized complexity of {\sc Edge $(2,2)$-Partization} remains open. We also give an approximation algorithm and a Turing kernelization for {\sc Vertex $(r,\ell)$-Partization}. We use an interesting finite forbidden induced graph characterization, for a class of graphs known as $(r,\ell)$-split graphs, properly containing the class of $(r,\ell)$-graphs. This approach to obtain approximation algorithms could be of an independent interest.
Some connections between binary block codes and Hilbert algebras
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we will study some connections between Hilbert al- gebras and binary block-codes.With these codes, we can eassy obtain orders which determine suplimentary properties on these algebras. We will try to emphasize how, using binary block-codes, we can provide examples of classes of Hilbert algebras with some properties, in our case, classes of semisimple Hilbert algebras and classes of local Hilbert algebras.
Evaluation of recommender systems in streaming environments
Venue: arXiv cs.IR 2015
Year: 2015

Evaluation of recommender systems is typically done with finite datasets. This means that conventional evaluation methodologies are only applicable in offline experiments, where data and models are stationary. However, in real world systems, user feedback is continuously generated, at unpredictable rates. Given this setting, one important issue is how to evaluate algorithms in such a streaming data environment. In this paper we propose a prequential evaluation protocol for recommender systems, suitable for streaming data environments, but also applicable in stationary settings. Using this protocol we are able to monitor the evolution of algorithms' accuracy over time. Furthermore, we are able to perform reliable comparative assessments of algorithms by computing significance tests over a sliding window. We argue that besides being suitable for streaming data, prequential evaluation allows the detection of phenomena that would otherwise remain unnoticed in the evaluation of both offline and online recommender systems.
A Metropolis Approach for Mesh Router Nodes placement in Rural Wireless Mesh Networks
Venue: arXiv cs.NI 2015
Year: 2015

Wireless mesh networks appear as an appealing solution to reduce the digital divide between rural and urban regions. However the placement of router nodes is still a critical issue when planning this type of network, especially in rural regions where we usually observe low density and sparse population. In this paper, we firstly provide a network model tied to rural regions by considering the area to cover as decomposed into a set of elementary areas which can be required or optional in terms of coverage and where a node can be placed or not. Afterwards, we try to determine an optimal number and positions of mesh router nodes while maximizing the coverage of areas of interest, minimizing the coverage of optional areas and ensuring connectivity of all mesh router nodes. For that we propose a particularized algorithm based on Metropolis approach to ensure an optimal coverage and connectivity with an optimal number of routers. The proposed algorithm is evaluated on different region instances. We obtained a required coverage between 94% and 97% and a coverage percentage of optional areas less than 16% with an optimal number of routers nr_max2 =1.3*nr_min , (nr_min being the minimum number of router which is the ratio between the total area requiring coverage and the area which can be covered by a router).
Lateral Connections in Denoising Autoencoders Support Supervised Learning
Venue: arXiv cs.LG 2015
Year: 2015

We show how a deep denoising autoencoder with lateral connections can be used as an auxiliary unsupervised learning task to support supervised learning. The proposed model is trained to minimize simultaneously the sum of supervised and unsupervised cost functions by back-propagation, avoiding the need for layer-wise pretraining. It improves the state of the art significantly in the permutation-invariant MNIST classification task.
Towards Query Optimization for SPARQL Property Paths
Venue: arXiv cs.DB 2015
Year: 2015

The extension of SPARQL in version 1.1 with property paths offers a type of regular path query for RDF graph databases. Such queries are difficult to optimize and evaluate efficiently, however. We have embarked on a project, Waveguide, to build a cost-based optimizer for SPARQL queries with property paths. Waveguide builds a query plan - a waveguide plan (WGP) - which guides the query evaluation. There are numerous choices in the construction of a plan, and a number of optimization methods, meaning the space of plans for a query can be quite large. Execution costs of plans for the same query can vary by orders of magnitude. We illustrate the types of optimizations this approach affords and the performance gains that can be obtained. A WGP's costs can be estimated, which opens the way to cost-based optimization.
Overlapping and Non-overlapping Camera Layouts for Robot Pose Estimation
Venue: arXiv cs.CV 2015
Year: 2015

We study the use of overlapping and non-overlapping camera layouts in estimating the ego-motion of a moving robot. To estimate the location and orientation of the robot, we investigate using four cameras as non-overlapping individuals, and as two stereo pairs. The pros and cons of the two approaches are elucidated. The cameras work independently and can have larger field of view in the non-overlapping layout. However, a scale factor ambiguity should be dealt with. On the other hand, stereo systems provide more accuracy but require establishing feature correspondence with more computational demand. For both approaches, the extended Kalman filter is used as a real-time recursive estimator. The approaches studied are verified with synthetic and real experiments alike.
CloudTree: A Library to Extend Cloud Services for Trees
Venue: arXiv cs.DC 2015
Year: 2015

In this work, we propose a library that enables on a cloud the creation and management of tree data structures from a cloud client. As a proof of concept, we implement a new cloud service CloudTree. With CloudTree, users are able to organize big data into tree data structures of their choice that are physically stored in a cloud. We use caching, prefetching, and aggregation techniques in the design and implementation of CloudTree to enhance performance. We have implemented the services of Binary Search Trees (BST) and Prefix Trees as current members in CloudTree and have benchmarked their performance using the Amazon Cloud. The idea and techniques in the design and implementation of a BST and prefix tree is generic and thus can also be used for other types of trees such as B-tree, and other link-based data structures such as linked lists and graphs. Preliminary experimental results show that CloudTree is useful and efficient for various big data applications.
Bijective Deformations in $\mathbb{R}^n$ via Integral Curve Coordinates
Venue: arXiv cs.GR 2015
Year: 2015

We introduce Integral Curve Coordinates, which identify each point in a bounded domain with a parameter along an integral curve of the gradient of a function $f$ on that domain; suitable functions have exactly one critical point, a maximum, in the domain, and the gradient of the function on the boundary points inward. Because every integral curve intersects the boundary exactly once, Integral Curve Coordinates provide a natural bijective mapping from one domain to another given a bijection of the boundary. Our approach can be applied to shapes in any dimension, provided that the boundary of the shape (or cage) is topologically equivalent to an $n$-sphere. We present a simple algorithm for generating a suitable function space for $f$ in any dimension. We demonstrate our approach in 2D and describe a practical (simple and robust) algorithm for tracing integral curves on a (piecewise-linear) triangulated regular grid.
Fast and Accurate Bilateral Filtering using Gauss-Polynomial Decomposition
Venue: arXiv cs.CV 2015
Year: 2015

The bilateral filter is a versatile non-linear filter that has found diverse applications in image processing, computer vision, computer graphics, and computational photography. A widely-used form of the filter is the Gaussian bilateral filter in which both the spatial and range kernels are Gaussian. A direct implementation of this filter requires $O(σ^2)$ operations per pixel, where $σ$ is the standard deviation of the spatial Gaussian. In this paper, we propose an accurate approximation algorithm that can cut down the computational complexity to $O(1)$ per pixel for any arbitrary $σ$ (constant-time implementation). This is based on the observation that the range kernel operates via the translations of a fixed Gaussian over the range space, and that these translated Gaussians can be accurately approximated using the so-called Gauss-polynomials. The overall algorithm emerging from this approximation involves a series of spatial Gaussian filtering, which can be implemented in constant-time using separability and recursion. We present some preliminary results to demonstrate that the proposed algorithm compares favorably with some of the existing fast algorithms in terms of speed and accuracy.
PDE Approaches to Graph Analysis
Venue: arXiv cs.DM 2015
Year: 2015

This paper surveys and discusses recent work adapting partial differential equation (PDE) models to discrete structures.