OpenRaiser/Intern-Atlas huggingface dataset:
Robust Shortest Path Planning and Semicontractive Dynamic Programming
Venue: arXiv cs.DS 2016
Year: 2016

In this paper we consider shortest path problems in a directed graph where the transitions between nodes are subject to uncertainty. We use a minimax formulation, where the objective is to guarantee that a special destination state is reached with a minimum cost path under the worst possible instance of the uncertainty. Problems of this type arise, among others, in planning and pursuit-evasion contexts, and in model predictive control. Our analysis makes use of the recently developed theory of abstract semicontractive dynamic programming models. We investigate questions of existence and uniqueness of solution of the optimality equation, existence of optimal paths, and the validity of various algorithms patterned after the classical methods of value and policy iteration, as well as a Dijkstra-like algorithm for problems with nonnegative arc lengths.
Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center
Venue: arXiv cs.DS 2016
Year: 2016

In the k-center problem, given a metric space V and a positive integer k, one wants to select k elements (centers) of V and an assignment from V to centers, minimizing the maximum distance between an element of V and its assigned center. One of the most general variants is the capacitated α-fault-tolerant k-center, where centers have a limit on the number of assigned elements, and, if α centers fail, there is a reassignment from V to non-faulty centers. In this paper, we present a new approach to tackle fault tolerance, by selecting and pre-opening a set of backup centers, then solving the obtained residual instance. For the {0,L}-capacitated case, we give approximations with factor 6 for the basic problem, and 7 for the so called conservative variant, when only clients whose centers failed may be reassigned. Our algorithms improve on the previously best known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming α is constant, our method leads to the first approximations for this case. We also derive approximations for the capacitated fault- tolerant k-supplier problem.
The Evolutionary Process of Image Transition in Conjunction with Box and Strip Mutation
Venue: arXiv cs.NE 2016
Year: 2016

Evolutionary algorithms have been used in many ways to generate digital art. We study how evolutionary processes are used for evolutionary art and present a new approach to the transition of images. Our main idea is to define evolutionary processes for digital image transition, combining different variants of mutation and evolutionary mechanisms. We introduce box and strip mutation operators which are specifically designed for image transition. Our experimental results show that the process of an evolutionary algorithm in combination with these mutation operators can be used as a valuable way to produce unique generative art.
A Small-Scale Prototype to Study the Take-Off of Tethered Rigid Aircrafts for Airborne Wind Energy
Venue: arXiv cs.SY 2016
Year: 2016

The design of a prototype to carry out take-off and flight tests with tethered aircrafts is presented. The system features a ground station equipped with a winch and a linear motion system. The motion of these two components is regulated by an automatic control system, whose goal is to accelerate a tethered aircraft to take-off speed using the linear motion system, while reeling-out the tether from the winch with low pulling force and avoiding entanglement. The mechanical, electrical, measurement and control aspects of the prototype are described in detail. Experimental results with a manually-piloted aircraft are presented, showing a good matching with previous theoretical findings.
Increased Mobility in Presence of Multiple Contacts - Identifying Contact Configurations that Enable Arbitrary Acceleration of CoM
Venue: arXiv cs.RO 2016
Year: 2016

Planning of any motion starts by planning the trajectory of the CoM. It is of the highest importance to ensure that the robot will be able to perform planned trajectory. With increasing capabilities of the humanoid robots, the case when contacts are spatially distributed should be considered. In this paper, it is shown that there are some contact configurations in which any acceleration of the center of mass (CoM) is feasible. The procedure for identifying such a configurations is presented, as well as its physical meaning. On the other hand, for the configurations in which the constraint on CoM movement exists, it will be shown how to find that linear constraint, which defines the space of feasible motion. The proposed algorithm has a low complexity and to speed up the procedure even further, it will be shown that the whole procedure needs to be run only once when contact configuration changes. As the CoM moves, the new constraints can be calculated from the initial one, thus yielding significant computation speedup. The methods are illustrated in two simulated scenarios.
Who Wants to Self-Track Anyway? Measuring the Relation between Self-Tracking Behavior and Personality Traits
Venue: arXiv cs.CY 2016
Year: 2016

We describe an empirical study of the usage of a mobility self-tracking app, SensibleJournal 2014, which provides personal mobility information to N=796 participants as part of a large mobile sensing study. Specifically, we report on the app design, as well as deployment, uptake and usage of the app. The latter analysis is based on logging of user interactions as well as answers gathered from a questionnaire provided to the participants. During the study enrollment process, participants were asked to fill out a questionnaire including a Big Five inventory and Narcissism NAR-Q personality tests. A comparison of personality traits was conducted to understand potential differences among the users and non-users of the app. We found a relation between self-tracking and conscientiousness, but contrary to the view in popular media, we found no relation between self-tracking behavior and narcissism.
Resolving Out-of-Vocabulary Words with Bilingual Embeddings in Machine Translation
Venue: arXiv cs.CL 2016
Year: 2016

Out-of-vocabulary words account for a large proportion of errors in machine translation systems, especially when the system is used on a different domain than the one where it was trained. In order to alleviate the problem, we propose to use a log-bilinear softmax-based model for vocabulary expansion, such that given an out-of-vocabulary source word, the model generates a probabilistic list of possible translations in the target language. Our model uses only word embeddings trained on significantly large unlabelled monolingual corpora and trains over a fairly small, word-to-word bilingual dictionary. We input this probabilistic list into a standard phrase-based statistical machine translation system and obtain consistent improvements in translation quality on the English-Spanish language pair. Especially, we get an improvement of 3.9 BLEU points when tested over an out-of-domain test set.
Daala: Building A Next-Generation Video Codec From Unconventional Technology
Venue: arXiv cs.MM 2016
Year: 2016

Daala is a new royalty-free video codec that attempts to compete with state-of-the-art royalty-bearing codecs. To do so, it must achieve good compression while avoiding all of their patented techniques. We use technology that is as different as possible from traditional approaches to achieve this. This paper describes the technology behind Daala and discusses where it fits in the newly created AV1 codec from the Alliance for Open Media. We show that Daala is approaching the performance level of more mature, state-of-the art video codecs and can contribute to improving AV1.
Text authorship identified using the dynamics of word co-occurrence networks
Venue: arXiv cs.CL 2016
Year: 2016

The identification of authorship in disputed documents still requires human expertise, which is now unfeasible for many tasks owing to the large volumes of text and authors in practical applications. In this study, we introduce a methodology based on the dynamics of word co-occurrence networks representing written texts to classify a corpus of 80 texts by 8 authors. The texts were divided into sections with equal number of linguistic tokens, from which time series were created for 12 topological metrics. The series were proven to be stationary (p-value>0.05), which permits to use distribution moments as learning attributes. With an optimized supervised learning procedure using a Radial Basis Function Network, 68 out of 80 texts were correctly classified, i.e. a remarkable 85% author matching success rate. Therefore, fluctuations in purely dynamic network metrics were found to characterize authorship, thus opening the way for the description of texts in terms of small evolving networks. Moreover, the approach introduced allows for comparison of texts with diverse characteristics in a simple, fast fashion.
R-connectivity Augmentation in Trees
Venue: arXiv cs.DM 2016
Year: 2016

A \emph{vertex separator} of a connected graph $G$ is a set of vertices removing which will result in two or more connected components and a \emph{minimum vertex separator} is a set which contains the minimum number of such vertices, i.e., the cardinality of this set is least among all possible vertex separator sets. The cardinality of the minimum vertex separator refers to the connectivity of the graph G. A connected graph is said to be $k-connected$ if removing exactly $k$ vertices, $ k\geq 1$, from the graph, will result in two or more connected components and on removing any $(k-1)$ vertices, the graph is still connected. A \emph{connectivity augmentation} set is a set of edges which when augmented to a $k$-connected graph $G$ will increase the connectivity of $G$ by $r$, $r \geq 1$, making the graph $(k+r)$-$connected$ and a \emph{minimum connectivity augmentation} set is such a set which contains a minimum number of edges required to increase the connectivity by $r$. In this paper, we shall investigate a $r$-$connectivity$ augmentation in trees, $r \geq 2$. As part of lower bound study, we show that any minimum $r$-connectivity augmentation set in trees requires at least $ \lceil\frac{1}{2} \sum\limits_{i=1}^{r-1} (r-i) \times l_{i} \rceil $ edges, where $l_i$ is the number of vertices with degree $i$. Further, we shall present an algorithm that will augment a minimum number of edges to make a tree $(k+r)$-connected.
Communication-Efficient Parallel Block Minimization for Kernel Machines
Venue: arXiv cs.LG 2016
Year: 2016

Kernel machines often yield superior predictive performance on various tasks; however, they suffer from severe computational challenges. In this paper, we show how to overcome the important challenge of speeding up kernel machines. In particular, we develop a parallel block minimization framework for solving kernel machines, including kernel SVM and kernel logistic regression. Our framework proceeds by dividing the problem into smaller subproblems by forming a block-diagonal approximation of the Hessian matrix. The subproblems are then solved approximately in parallel. After that, a communication efficient line search procedure is developed to ensure sufficient reduction of the objective function value at each iteration. We prove global linear convergence rate of the proposed method with a wide class of subproblem solvers, and our analysis covers strongly convex and some non-strongly convex functions. We apply our algorithm to solve large-scale kernel SVM problems on distributed systems, and show a significant improvement over existing parallel solvers. As an example, on the covtype dataset with half-a-million samples, our algorithm can obtain an approximate solution with 96% accuracy in 20 seconds using 32 machines, while all the other parallel kernel SVM solvers require more than 2000 seconds to achieve a solution with 95% accuracy. Moreover, our algorithm can scale to very large data sets, such as the kdd algebra dataset with 8 million samples and 20 million features.
Desiderata for Vector-Space Word Representations
Venue: arXiv cs.CL 2016
Year: 2016

A plethora of vector-space representations for words is currently available, which is growing. These consist of fixed-length vectors containing real values, which represent a word. The result is a representation upon which the power of many conventional information processing and data mining techniques can be brought to bear, as long as the representations are designed with some forethought and fit certain constraints. This paper details desiderata for the design of vector space representations of words.
Spoofing 2D Face Detection: Machines See People Who Aren't There
Venue: arXiv cs.CR 2016
Year: 2016

Machine learning is increasingly used to make sense of the physical world yet may suffer from adversarial manipulation. We examine the Viola-Jones 2D face detection algorithm to study whether images can be created that humans do not notice as faces yet the algorithm detects as faces. We show that it is possible to construct images that Viola-Jones recognizes as containing faces yet no human would consider a face. Moreover, we show that it is possible to construct images that fool facial detection even when they are printed and then photographed.
True Rigidity: Interpenetration-free Multi-Body Simulation with Polytopic Contact
Venue: arXiv cs.RO 2016
Year: 2016

An effective paradigm for simulating the dynamics of robots that locomote and manipulate is multi-rigid body simulation with rigid contact. This paradigm provides reasonable tradeoffs between accuracy, running time, and simplicity of parameter selection and identification. The Stewart-Trinkle/Anitescu-Potra time stepping approach is the basis of many existing implementations. It successfully treats inconsistent (Painleve-type) contact configurations, efficiently handles many contact events occurring in short time intervals, and provably converges to the solution of the continuous time differential algebraic equations (DAEs) as the integration step size tends to zero. However, there is currently no means to determine when the solution has largely converged, i.e., when smaller integration steps would result in only small increases in accuracy. The present work describes an approach that computes the event times (when the set of active equations in a DAE changes) of all contact/impact events for a multi-body simulation, toward using integration techniques with error control to compute a solution with desired accuracy. We also describe a first-order, variable integration approach that ensures that rigid bodies with convex polytopic geometries never interpenetrate. This approach permits taking large steps when possible and takes small steps when contact is complex.
Robust High-Dimensional Linear Regression
Venue: arXiv cs.LG 2016
Year: 2016

The effectiveness of supervised learning techniques has made them ubiquitous in research and practice. In high-dimensional settings, supervised learning commonly relies on dimensionality reduction to improve performance and identify the most important factors in predicting outcomes. However, the economic importance of learning has made it a natural target for adversarial manipulation of training data, which we term poisoning attacks. Prior approaches to dealing with robust supervised learning rely on strong assumptions about the nature of the feature matrix, such as feature independence and sub-Gaussian noise with low variance. We propose an integrated method for robust regression that relaxes these assumptions, assuming only that the feature matrix can be well approximated by a low-rank matrix. Our techniques integrate improved robust low-rank matrix approximation and robust principle component regression, and yield strong performance guarantees. Moreover, we experimentally show that our methods significantly outperform state of the art both in running time and prediction error.
Decentralized Biconnectivity Conditions in Multi-robot Systems
Venue: arXiv cs.RO 2016
Year: 2016

The network connectivity in a group of cooperative robots can be easily broken if one of them loses its connectivity with the rest of the group. In case of having robustness with respect to one-robot-fail, the communication network is termed biconnected. In simple words, to have a biconnected network graph, we need to prove that there exists no articulation point. We propose a decentralized approach that provides sufficient conditions for biconnectivity of the network, and we prove that these conditions are related to the third smallest eigenvalue of the Laplacian matrix. Data exchange among the robots is supposed to be neighbor-to-neighbor.
Delta Epsilon Alpha Star: A PAC-Admissible Search Algorithm
Venue: arXiv cs.AI 2016
Year: 2016

Delta Epsilon Alpha Star is a minimal coverage, real-time robotic search algorithm that yields a moderately aggressive search path with minimal backtracking. Search performance is bounded by a placing a combinatorial bound, epsilon and delta, on the maximum deviation from the theoretical shortest path and the probability at which further deviations can occur. Additionally, we formally define the notion of PAC-admissibility -- a relaxed admissibility criteria for algorithms, and show that PAC-admissible algorithms are better suited to robotic search situations than epsilon-admissible or strict algorithms.
A note on the Survivable Network Design Problem
Venue: arXiv cs.DS 2016
Year: 2016

In this note we consider the survivable network design problem (SNDP) in undirected graphs. We make two contributions. The first is a new counting argument in the iterated rounding based 2-approximation for edge-connectivity SNDP (EC-SNDP) originally due to Jain. The second is to make some additional connections between hypergraphic version of SNDP introduced by Zhao, Nagamochi and Ibaraki and edge and node-weighted versions of EC-SNDP and element-connectivity SNDP (Elem-SNDP). One useful consequence of this connection is a 2-approximation for Elem-SNDP that avoids the use of set-pair based relaxation and analysis.
Semantic Code Browsing
Venue: arXiv cs.PL 2016
Year: 2016

Programmers currently enjoy access to a very high number of code repositories and libraries of ever increasing size. The ensuing potential for reuse is however hampered by the fact that searching within all this code becomes an increasingly difficult task. Most code search engines are based on syntactic techniques such as signature matching or keyword extraction. However, these techniques are inaccurate (because they basically rely on documentation) and at the same time do not offer very expressive code query languages. We propose a novel approach that focuses on querying for semantic characteristics of code obtained automatically from the code itself. Program units are pre-processed using static analysis techniques, based on abstract interpretation, obtaining safe semantic approximations. A novel, assertion-based code query language is used to express desired semantic characteristics of the code as partial specifications. Relevant code is found by comparing such partial specifications with the inferred semantics for program elements. Our approach is fully automatic and does not rely on user annotations or documentation. It is more powerful and flexible than signature matching because it is parametric on the abstract domain and properties, and does not require type definitions. Also, it reasons with relations between properties, such as implication and abstraction, rather than just equality. It is also more resilient to syntactic code differences. We describe the approach and report on a prototype implementation within the Ciao system. Under consideration for acceptance in TPLP.
OptMark: A Toolkit for Benchmarking Query Optimizers
Venue: arXiv cs.DB 2016
Year: 2016

Query optimizers have long been considered as among the most complex components of a database engine, while the assessment of an optimizer's quality remains a challenging task. Indeed, existing performance benchmarks for database engines (like TPC benchmarks) produce a performance assessment of the query runtime system rather than its query optimizer. To address this challenge, this paper introduces OptMark, a toolkit for evaluating the quality of a query optimizer. OptMark is designed to offer a number of desirable properties. First, it decouples the quality of an optimizer from the quality of its underlying execution engine. Second it evaluates independently both the effectiveness of an optimizer (i.e., quality of the chosen plans) and its efficiency (i.e., optimization time). OptMark includes also a generic benchmarking toolkit that is minimum invasive to the DBMS that wishes to use it. Any DBMS can provide a system-specific implementation of a simple API that allows OptMark to run and generate benchmark scores for the specific system. This paper discusses the metrics we propose for evaluating an optimizer's quality, the benchmark's design and the toolkit's API and functionality. We have implemented OptMark on the open-source MySQL engine as well as two commercial database systems. Using these implementations we are able to assess the quality of the optimizers on these three systems based on the TPC-DS benchmark queries.
Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we proposed a new efficient sorting algorithm based on insertion sort concept. The proposed algorithm called Bidirectional Conditional Insertion Sort (BCIS). It is in-place sorting algorithm and it has remarkably efficient average case time complexity when compared with classical insertion sort (IS). By comparing our new proposed algorithm with the Quicksort algorithm, BCIS indicated faster average case time for relatively small size arrays up to 1500 elements. Furthermore, BCIS was observed to be faster than Quicksort within high rate of duplicated elements even for large size array.
A deep language model for software code
Venue: arXiv cs.SE 2016
Year: 2016

Existing language models such as n-grams for software code often fail to capture a long context where dependent code elements scatter far apart. In this paper, we propose a novel approach to build a language model for software code to address this particular issue. Our language model, partly inspired by human memory, is built upon the powerful deep learning-based Long Short Term Memory architecture that is capable of learning long-term dependencies which occur frequently in software code. Results from our intrinsic evaluation on a corpus of Java projects have demonstrated the effectiveness of our language model. This work contributes to realizing our vision for DeepSoft, an end-to-end, generic deep learning-based framework for modeling software and its development process.
Advertising Competitions in Social Networks
Venue: arXiv cs.GT 2016
Year: 2016

In the present work, we study the advertising competition of several marketing campaigns who need to determine how many resources to allocate to potential customers to advertise their products through direct marketing while taking into account that competing marketing campaigns are trying to do the same. Potential customers rank marketing campaigns according to the offers, promotions or discounts made to them. Taking into account the intrinsic value of potential customers as well as the peer influence that they exert over other potential customers we consider the network value as a measure of their importance in the market and we find an analytical expression for it.We analyze the marketing campaigns competition from a game theory point of view, finding a closed form expression of the symmetric equilibrium offer strategy for the marketing campaigns from which no campaign has any incentive to deviate. We also present several scenarios, such as Winner-takes-all and Borda, but not the only possible ones for which our results allow us to retrieve in a simple way the corresponding equilibrium strategy.