OpenRaiser/Intern-Atlas huggingface dataset:
From Pragmatic to Systematic Software Process Improvement: An Evaluated Approach
Venue: arXiv cs.SE 2017
Year: 2017

Software processes improvement (SPI) is a challenging task, as many different stakeholders, project settings, and contexts and goals need to be considered. SPI projects are often operated in a complex and volatile environment and, thus, require a sound management that is resource-intensive requiring many stakeholders to contribute to the process assessment, analysis, design, realisation, and deployment. Although there exist many valuable SPI approaches, none address the needs of both process engineers and project managers. This article presents an Artefact-based Software Process Improvement & Management approach (ArSPI) that closes this gap. ArSPI was developed and tested across several SPI projects in large organisations in Germany and Eastern Europe. The approach further encompasses a template for initiating, performing, and managing SPI projects by defining a set of 5 key artefacts and 24 support artefacts. We present ArSPI and discus results of its validation indicating ArSPI to be a helpful instrument to set up and steer SPI projects.
On the Use of Variability Operations in the V-Modell XT Software Process Line
Venue: arXiv cs.SE 2017
Year: 2017

Software process lines provide a systematic approach to develop and manage software processes. It defines a reference process containing general process assets, whereas a well-defined customization approach allows process engineers to create new process variants, e.g., by extending or modifying process assets. Variability operations are an instrument to realize flexibility by explicitly declaring required modifications, which are applied to create a procedurally generated company-specific process. However, little is known about which variability operations are suitable in practice. In this article, we present a study on the feasibility of variability operations to support the development of software process lines in the context of the V-Modell XT. We analyze which variability operations are defined and practically used. We provide an initial catalog of variability operations as an improvement proposal for other process models. Our findings show that 69 variability operation types are defined across several metamodel versions of which, however, 25 remain unused. The found variability operations allow for systematically modifying the content of process model elements and the process documentation, and they allow for altering the structure of a process model and its description. Furthermore, we also find that variability operations can help process engineers to compensate process metamodel evolution.
Hypercube LSH for approximate near neighbors
Venue: arXiv cs.DS 2017
Year: 2017

A celebrated technique for finding near neighbors for the angular distance involves using a set of \textit{random} hyperplanes to partition the space into hash regions [Charikar, STOC 2002]. Experiments later showed that using a set of \textit{orthogonal} hyperplanes, thereby partitioning the space into the Voronoi regions induced by a hypercube, leads to even better results [Terasawa and Tanaka, WADS 2007]. However, no theoretical explanation for this improvement was ever given, and it remained unclear how the resulting hypercube hash method scales in high dimensions. In this work, we provide explicit asymptotics for the collision probabilities when using hypercubes to partition the space. For instance, two near-orthogonal vectors are expected to collide with probability $(\frac{1}π)^{d + o(d)}$ in dimension $d$, compared to $(\frac{1}{2})^d$ when using random hyperplanes. Vectors at angle $\fracπ{3}$ collide with probability $(\frac{\sqrt{3}}π)^{d + o(d)}$, compared to $(\frac{2}{3})^d$ for random hyperplanes, and near-parallel vectors collide with similar asymptotic probabilities in both cases. For $c$-approximate nearest neighbor searching, this translates to a decrease in the exponent $ρ$ of locality-sensitive hashing (LSH) methods of a factor up to $\log_2(π) \approx 1.652$ compared to hyperplane LSH. For $c = 2$, we obtain $ρ\approx 0.302 + o(1)$ for hypercube LSH, improving upon the $ρ\approx 0.377$ for hyperplane LSH. We further describe how to use hypercube LSH in practice, and we consider an example application in the area of lattice algorithms.
The Absent-Minded Driver Problem Redux
Venue: arXiv cs.AI 2017
Year: 2017

This paper reconsiders the problem of the absent-minded driver who must choose between alternatives with different payoff with imperfect recall and varying degrees of knowledge of the system. The classical absent-minded driver problem represents the case with limited information and it has bearing on the general area of communication and learning, social choice, mechanism design, auctions, theories of knowledge, belief, and rational agency. Within the framework of extensive games, this problem has applications to many artificial intelligence scenarios. It is obvious that the performance of the agent improves as information available increases. It is shown that a non-uniform assignment strategy for successive choices does better than a fixed probability strategy. We consider both classical and quantum approaches to the problem. We argue that the superior performance of quantum decisions with access to entanglement cannot be fairly compared to a classical algorithm. If the cognitive systems of agents are taken to have access to quantum resources, or have a quantum mechanical basis, then that can be leveraged into superior performance.
Harmonic Grammar, Optimality Theory, and Syntax Learnability: An Empirical Exploration of Czech Word Order
Venue: arXiv cs.CL 2017
Year: 2017

This work presents a systematic theoretical and empirical comparison of the major algorithms that have been proposed for learning Harmonic and Optimality Theory grammars (HG and OT, respectively). By comparing learning algorithms, we are also able to compare the closely related OT and HG frameworks themselves. Experimental results show that the additional expressivity of the HG framework over OT affords performance gains in the task of predicting the surface word order of Czech sentences. We compare the perceptron with the classic Gradual Learning Algorithm (GLA), which learns OT grammars, as well as the popular Maximum Entropy model. In addition to showing that the perceptron is theoretically appealing, our work shows that the performance of the HG model it learns approaches that of the upper bound in prediction accuracy on a held out test set and that it is capable of accurately modeling observed variation.
Precise Null Pointer Analysis Through Global Value Numbering
Venue: arXiv cs.PL 2017
Year: 2017

Precise analysis of pointer information plays an important role in many static analysis techniques and tools today. The precision, however, must be balanced against the scalability of the analysis. This paper focusses on improving the precision of standard context and flow insensitive alias analysis algorithms at a low scalability cost. In particular, we present a semantics-preserving program transformation that drastically improves the precision of existing analyses when deciding if a pointer can alias NULL. Our program transformation is based on Global Value Numbering, a scheme inspired from compiler optimizations literature. It allows even a flow-insensitive analysis to make use of branch conditions such as checking if a pointer is NULL and gain precision. We perform experiments on real-world code to measure the overhead in performing the transformation and the improvement in the precision of the analysis. We show that the precision improves from 86.56% to 98.05%, while the overhead is insignificant.
Post-edit Analysis of Collective Biography Generation
Venue: arXiv cs.CL 2017
Year: 2017

Text generation is increasingly common but often requires manual post-editing where high precision is critical to end users. However, manual editing is expensive so we want to ensure this effort is focused on high-value tasks. And we want to maintain stylistic consistency, a particular challenge in crowd settings. We present a case study, analysing human post-editing in the context of a template-based biography generation system. An edit flow visualisation combined with manual characterisation of edits helps identify and prioritise work for improving end-to-end efficiency and accuracy.
Sustainable Fair Division
Venue: arXiv cs.GT 2017
Year: 2017

In this paper, I summarize our work on online fair division. In particular, I present two models for online fair division: (1) one existing model for fair division in food banks and (2) one new model for fair division of deceased organs to patients. I further discuss simple mechanisms for these models that allocate the resources as they arrive to agents. In practice, agents are often risk-averse having imperfect information. Within this assumption, I report several interesting axiomatic and complexity results for these mechanisms and conclude with future work.
Robust Sparse Estimation Tasks in High Dimensions
Venue: arXiv cs.LG 2017
Year: 2017

In this paper we initiate the study of whether or not sparse estimation tasks can be performed efficiently in high dimensions, in the robust setting where an $\eps$-fraction of samples are corrupted adversarially. We study the natural robust version of two classical sparse estimation problems, namely, sparse mean estimation and sparse PCA in the spiked covariance model. For both of these problems, we provide the first efficient algorithms that provide non-trivial error guarantees in the presence of noise, using only a number of samples which is similar to the number required for these problems without noise. In particular, our sample complexities are sublinear in the ambient dimension $d$. Our work also suggests evidence for new computational-vs-statistical gaps for these problems (similar to those for sparse PCA without noise) which only arise in the presence of noise.
Semantic Compression for Edge-Assisted Systems
Venue: arXiv cs.NI 2017
Year: 2017

A novel semantic approach to data selection and compression is presented for the dynamic adaptation of IoT data processing and transmission within "wireless islands", where a set of sensing devices (sensors) are interconnected through one-hop wireless links to a computational resource via a local access point. The core of the proposed technique is a cooperative framework where local classifiers at the mobile nodes are dynamically crafted and updated based on the current state of the observed system, the global processing objective and the characteristics of the sensors and data streams. The edge processor plays a key role by establishing a link between content and operations within the distributed system. The local classifiers are designed to filter the data streams and provide only the needed information to the global classifier at the edge processor, thus minimizing bandwidth usage. However, the better the accuracy of these local classifiers, the larger the energy necessary to run them at the individual sensors. A formulation of the optimization problem for the dynamic construction of the classifiers under bandwidth and energy constraints is proposed and demonstrated on a synthetic example.
Reflection Separation Using Guided Annotation
Venue: arXiv cs.CV 2017
Year: 2017

Photographs taken through a glass surface often contain an approximately linear superposition of reflected and transmitted layers. Decomposing an image into these layers is generally an ill-posed task and the use of an additional image prior and user provided cues is presently necessary in order to obtain good results. Current annotation approaches rely on a strong sparsity assumption. For images with significant texture this assumption does not typically hold, thus rendering the annotation process unviable. In this paper we show that using a Gaussian Mixture Model patch prior, the correct local decomposition can almost always be found as one of 100 likely modes of the posterior. Thus, the user need only choose one of these modes in a sparse set of patches and the decomposition may then be completed automatically. We demonstrate the performance of our method using synthesized and real reflection images.
Kharita: Robust Map Inference using Graph Spanners
Venue: arXiv cs.OH 2017
Year: 2017

The widespread availability of GPS information in everyday devices such as cars, smartphones and smart watches make it possible to collect large amount of geospatial trajectory information. A particularly important, yet technically challenging, application of this data is to identify the underlying road network and keep it updated under various changes. In this paper, we propose efficient algorithms that can generate accurate maps in both batch and online settings. Our algorithms utilize techniques from graph spanners so that they produce maps can effectively handle a wide variety of road and intersection shapes. We conduct a rigorous evaluation of our algorithms over two real-world datasets and under a wide variety of performance metrics. Our experiments show a significant improvement over prior work. In particular, we observe an increase in Biagioni f-score of up to 20% when compared to the state of the art while reducing the execution time by an order of magnitude. We also make our source code open source for reproducibility and enable other researchers to build on our work.
Algebraic Laws for Weak Consistency (Extended Version)
Venue: arXiv cs.LO 2017
Year: 2017

Modern distributed systems often rely on so called weakly-consistent databases, which achieve scalability by sacrificing the consistency guarantee of distributed transaction processing. Such databases have been formalised in two different styles, one based on abstract executions and the other based on dependency graphs. The choice between these styles has been made according to intended applications: the former has been used to specify and verify the implementation of these databases, and the latter to prove properties of programs running on top of the databases. In this paper, we present a set of novel algebraic laws (i.e. inequations) that connect these two styles of specifications; the laws relate binary relations used in a specification based on abstract executions, to those used in a specification based on dependency graphs. We then show that this algebraic connection gives rise to so called robustness criteria, conditions which ensures that a program running on top of a weakly-consistent database does not exhibit anomalous behaviours due to this weak consistency. These criteria make it easy to reason about programs running on top of these databases, and may become a basis for dynamic or static program analyses. For a certain class of consistency models specifications, we prove a full abstraction result that connects the two styles of specifications.
Momentum Control of an Underactuated Flying Humanoid Robot
Venue: arXiv cs.RO 2017
Year: 2017

The paper takes the first step towards the de- velopment of a control framework for underactuated flying humanoid robots. These robots may thus have the capacities of flight, contact locomotion, and manipulation, and benefit from technologies and methods developed for Whole-Body Control and Aerial Manipulation. As in the case of quadrotors, we as- sume that the humanoid robot is powered by four thrust forces. For convenience, these forces are placed at the robot hands and feet. The control objective is defined as the asymptotic stabilization of the robot centroidal momentum. This objective allows us to track a desired trajectory for the robot center of mass and keep small errors between a reference orientation and the robot base frame. Stability and convergence of the robot momentum are shown to be in the sense of Lyapunov. Simulations carried out on a model of the humanoid robot iCub verify the soundness of the proposed approach.
Identifying high betweenness centrality nodes in large social networks
Venue: arXiv cs.DS 2017
Year: 2017

This paper proposes an alternative way to identify nodes with high betweenness centrality. It introduces a new metric, k-path centrality, and a randomized algorithm for estimating it, and shows empirically that nodes with high k-path centrality have high node betweenness centrality. The randomized algorithm runs in time $O(κ^{3}n^{2-2α}\log n)$ and outputs, for each vertex v, an estimate of its k-path centrality up to additive error of $\pm n^{1/2+ α}$ with probability $1-1/n^2$. Experimental evaluations on real and synthetic social networks show improved accuracy in detecting high betweenness centrality nodes and significantly reduced execution time when compared with existing randomized algorithms.
Role model detection using low rank similarity matrix
Venue: arXiv cs.SI 2017
Year: 2017

Computing meaningful clusters of nodes is crucial to analyse large networks. In this paper, we apply new clustering methods to improve the computational time. We use the properties of the adjacency matrix to obtain better role extraction. We also define a new non-recursive similarity measure and compare its results with the ones obtained with Browet's similarity measure. We will show the extraction of the different roles with a linear time complexity. Finally, we test our algorithm with real data structures and analyse the limit of our algorithm.
Con los juegos también se educa: un enfoque educativo de los juegos de la Oca y el Parchís
Venue: arXiv cs.CY 2017
Year: 2017

In this work, we have designed and implemented, based on traditional board games such as the game of the Goose or Parchis, an educational software that aim to reinforce the learning of children. The idea that we are going to develop to do this is very simple: the children play with the same rules as in the traditional game but we add the functionality that after throwing the dice the system asks a question randomly chosen from a predefined database that can be easily modified, and the game piece only moves in the case the question is answered correctly.
Efficient Dense Labeling of Human Activity Sequences from Wearables using Fully Convolutional Networks
Venue: arXiv cs.CV 2017
Year: 2017

Recognizing human activities in a sequence is a challenging area of research in ubiquitous computing. Most approaches use a fixed size sliding window over consecutive samples to extract features---either handcrafted or learned features---and predict a single label for all samples in the window. Two key problems emanate from this approach: i) the samples in one window may not always share the same label. Consequently, using one label for all samples within a window inevitably lead to loss of information; ii) the testing phase is constrained by the window size selected during training while the best window size is difficult to tune in practice. We propose an efficient algorithm that can predict the label of each sample, which we call dense labeling, in a sequence of human activities of arbitrary length using a fully convolutional network. In particular, our approach overcomes the problems posed by the sliding window step. Additionally, our algorithm learns both the features and classifier automatically. We release a new daily activity dataset based on a wearable sensor with hospitalized patients. We conduct extensive experiments and demonstrate that our proposed approach is able to outperform the state-of-the-arts in terms of classification and label misalignment measures on three challenging datasets: Opportunity, Hand Gesture, and our new dataset.
Noise Models in the Nonlinear Spectral Domain for Optical Fibre Communications
Venue: arXiv cs.IT 2017
Year: 2017

Existing works on building a soliton transmission system only encode information using the imaginary part of the eigenvalue, which fails to make full use of the signal degree-of-freedoms. Motivated by this observation, we make the first step of encoding information using (discrete) spectral amplitudes by proposing analytical noise models for the spectral amplitudes of $N$-solitons ($N\geq 1$). To our best knowledge, this is the first work in building an analytical noise model for spectral amplitudes, which leads to many interesting information theoretic questions, such as channel capacity analysis, and has a potential of increasing the transmission rate. The noise statistics of the spectral amplitude of a soliton are also obtained without the Gaussian approximation.
Learning to Generate Posters of Scientific Papers by Probabilistic Graphical Models
Venue: arXiv cs.CV 2017
Year: 2017

Researchers often summarize their work in the form of scientific posters. Posters provide a coherent and efficient way to convey core ideas expressed in scientific papers. Generating a good scientific poster, however, is a complex and time consuming cognitive task, since such posters need to be readable, informative, and visually aesthetic. In this paper, for the first time, we study the challenging problem of learning to generate posters from scientific papers. To this end, a data-driven framework, that utilizes graphical models, is proposed. Specifically, given content to display, the key elements of a good poster, including attributes of each panel and arrangements of graphical elements are learned and inferred from data. During the inference stage, an MAP inference framework is employed to incorporate some design principles. In order to bridge the gap between panel attributes and the composition within each panel, we also propose a recursive page splitting algorithm to generate the panel layout for a poster. To learn and validate our model, we collect and release a new benchmark dataset, called NJU-Fudan Paper-Poster dataset, which consists of scientific papers and corresponding posters with exhaustively labelled panels and attributes. Qualitative and quantitative results indicate the effectiveness of our approach.
Learning to generate one-sentence biographies from Wikidata
Venue: arXiv cs.CL 2017
Year: 2017

We investigate the generation of one-sentence Wikipedia biographies from facts derived from Wikidata slot-value pairs. We train a recurrent neural network sequence-to-sequence model with attention to select facts and generate textual summaries. Our model incorporates a novel secondary objective that helps ensure it generates sentences that contain the input facts. The model achieves a BLEU score of 41, improving significantly upon the vanilla sequence-to-sequence model and scoring roughly twice that of a simple template baseline. Human preference evaluation suggests the model is nearly as good as the Wikipedia reference. Manual analysis explores content selection, suggesting the model can trade the ability to infer knowledge against the risk of hallucinating incorrect information.
Information-Theoretic Perspectives on Brascamp-Lieb Inequality and Its Reverse
Venue: arXiv cs.IT 2017
Year: 2017

We introduce an inequality which may be viewed as a generalization of both the Brascamp-Lieb inequality and its reverse (Barthe's inequality), and prove its information-theoretic (i.e.\ entropic) formulation. This result leads to a unified approach to functional inequalities such as the variational formula of Rényi entropy, hypercontractivity and its reverse, strong data processing inequalities, and transportation-cost inequalities, whose utility in the proofs of various coding theorems has gained growing popularity recently. We show that our information-theoretic setting is convenient for proving properties such as data processing, tensorization, convexity (Riesz-Thorin interpolation) and Gaussian optimality. In particular, we elaborate on a "doubling trick" used by Lieb and Geng-Nair to prove several results on Gaussian optimality. Several applications are discussed, including a generalization of the Brascamp-Lieb inequality involving Gaussian random transformations, the determination of Wyner's common information of vector Gaussian sources, and the achievable rate region of certain key generation problems in the case of vector Gaussian sources.