OpenRaiser/Intern-Atlas huggingface dataset:
ACDC: Altering Control Dependence Chains for Automated Patch Generation
Venue: arXiv cs.SE 2017
Year: 2017

Once a failure is observed, the primary concern of the developer is to identify what caused it in order to repair the code that induced the incorrect behavior. Until a permanent repair is afforded, code repair patches are invaluable. The aim of this work is to devise an automated patch generation technique that proceeds as follows: Step1) It identifies a set of failure-causing control dependence chains that are minimal in terms of number and length. Step2) It identifies a set of predicates within the chains along with associated execution instances, such that negating the predicates at the given instances would exhibit correct behavior. Step3) For each candidate predicate, it creates a classifier that dictates when the predicate should be negated to yield correct program behavior. Step4) Prior to each candidate predicate, the faulty program is injected with a call to its corresponding classifier passing it the program state and getting a return value predictively indicating whether to negate the predicate or not. The role of the classifiers is to ensure that: 1) the predicates are not negated during passing runs; and 2) the predicates are negated at the appropriate instances within failing runs. We implemented our patch generation approach for the Java platform and evaluated our toolset using 148 defects from the Introclass and Siemens benchmarks. The toolset identified 56 full patches and another 46 partial patches, and the classification accuracy averaged 84%.
Multi-view Unsupervised Feature Selection by Cross-diffused Matrix Alignment
Venue: arXiv cs.LG 2017
Year: 2017

Multi-view high-dimensional data become increasingly popular in the big data era. Feature selection is a useful technique for alleviating the curse of dimensionality in multi-view learning. In this paper, we study unsupervised feature selection for multi-view data, as class labels are usually expensive to obtain. Traditional feature selection methods are mostly designed for single-view data and cannot fully exploit the rich information from multi-view data. Existing multi-view feature selection methods are usually based on noisy cluster labels which might not preserve sufficient information from multi-view data. To better utilize multi-view information, we propose a method, CDMA-FS, to select features for each view by performing alignment on a cross diffused matrix. We formulate it as a constrained optimization problem and solve it using Quasi-Newton based method. Experiments results on four real-world datasets show that the proposed method is more effective than the state-of-the-art methods in multi-view setting.
Talking Open Data
Venue: arXiv cs.IR 2017
Year: 2017

Enticing users into exploring Open Data remains an important challenge for the whole Open Data paradigm. Standard stock interfaces often used by Open Data portals are anything but inspiring even for tech-savvy users, let alone those without an articulated interest in data science. To address a broader range of citizens, we designed an open data search interface supporting natural language interactions via popular platforms like Facebook and Skype. Our data-aware chatbot answers search requests and suggests relevant open datasets, bringing fun factor and a potential of viral dissemination into Open Data exploration. The current system prototype is available for Facebook (https://m.me/OpenDataAssistant) and Skype (https://join.skype.com/bot/6db830ca-b365-44c4-9f4d-d423f728e741) users.
Towards Practical, Precise and Parametric Energy Analysis of IT Controlled Systems
Venue: arXiv cs.PL 2017
Year: 2017

Energy consumption analysis of IT-controlled systems can play a major role in minimising the overall energy consumption of such IT systems, during the development phase, or for optimisation in the field. Recently, a precise energy analysis was developed, with the property of being parametric in the hardware. In principle, this creates the opportunity to analyse which is the best software implementation for given hardware, or the other way around: choose the best hardware for a given algorithm. The precise analysis was introduced for a very limited language: ECA. In this paper, several important steps are taken towards practical energy analysis. The ECA language is extended with common programming language features. The application domain is further explored, and threats to the validity are identified and discussed. Altogether, this constitutes an important step towards analysing energy consumption of IT-controlled systems in practice.
The Problem of Coincidence in A Theory of Temporal Multiple Recurrence
Venue: arXiv cs.AI 2017
Year: 2017

Logical theories have been developed which have allowed temporal reasoning about eventualities (a la Galton) such as states, processes, actions, events, processes and complex eventualities such as sequences and recurrences of other eventualities. This paper presents the problem of coincidence within the framework of a first order logical theory formalising temporal multiple recurrence of two sequences of fixed duration eventualities and presents a solution to it The coincidence problem is described as: if two complex eventualities (or eventuality sequences) consisting respectively of component eventualities x0, x1,....,xr and y0, y1, ..,ys both recur over an interval k and all eventualities are of fixed durations, is there a sub-interval of k over which the incidence xt and yu for t between 0..r and s between 0..s coincide. The solution presented here formalises the intuition that a solution can be found by temporal projection over a cycle of the multiple recurrence of both sequences.
Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees
Venue: arXiv cs.DS 2017
Year: 2017

We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our analyses utilizes this combinatorial connection to bridge between statistical leverage scores / effective resistances and the analysis of random graphs by [Janson, Combinatorics, Probability and Computing `94]. This leads to a routine that in quadratic time, sparsifies a graph down to about $n^{1.5}$ edges in ways that preserve both the determinant and the distribution of spanning trees (provided the sparsified graph is viewed as a random object). Extending this algorithm to work with Schur complements and approximate Choleksy factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs. We give an algorithm that computes a $(1 \pm δ)$ approximation to the determinant of any SDDM matrix with constant probability in about $n^2 δ^{-2}$ time. This is the first routine for graphs that outperforms general-purpose routines for computing determinants of arbitrary matrices. We also give an algorithm that generates in about $n^2 δ^{-2}$ time a spanning tree of a weighted undirected graph from a distribution with total variation distance of $δ$ from the $w$-uniform distribution .
Dynamic Space Efficient Hashing
Venue: arXiv cs.DS 2017
Year: 2017

We consider space efficient hash tables that can grow and shrink dynamically and are always highly space efficient, i.e., their space consumption is always close to the lower bound even while growing and when taking into account storage that is only needed temporarily. None of the traditionally used hash tables have this property. We show how known approaches like linear probing and bucket cuckoo hashing can be adapted to this scenario by subdividing them into many subtables or using virtual memory overcommitting. However, these rather straightforward solutions suffer from slow amortized insertion times due to frequent reallocation in small increments. Our main result is DySECT ({\bf Dy}namic {\bf S}pace {\bf E}fficient {\bf C}uckoo {\bf T}able) which avoids these problems. DySECT consists of many subtables which grow by doubling their size. The resulting inhomogeneity in subtable sizes is equalized by the flexibility available in bucket cuckoo hashing where each element can go to several buckets each of which containing several cells. Experiments indicate that DySECT works well with load factors up to 98\%. With up to 2.7 times better performance than the next best solution.
Estimating the Information Rate of a Channel with Classical Input and Output and a Quantum State (Extended Version)
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of transmitting classical information over a time-invariant channel with memory. A popular class of time-invariant channels with memory are finite-state-machine channels, where a \emph{classical} state evolves over time and governs the relationship between the classical input and the classical output of the channel. For such channels, various techniques have been developed for estimating and bounding the information rate. In this paper we consider a class of time-invariant channels where a \emph{quantum} state evolves over time and governs the relationship between the classical input and the classical output of the channel. We propose algorithms for estimating and bounding the information rate of such channels. In particular, we discuss suitable graphical models for doing the relevant computations.
Entity Linking with people entity on Wikipedia
Venue: arXiv cs.CL 2017
Year: 2017

This paper introduces a new model that uses named entity recognition, coreference resolution, and entity linking techniques, to approach the task of linking people entities on Wikipedia people pages to their corresponding Wikipedia pages if applicable. Our task is different from general and traditional entity linking because we are working in a limited domain, namely, people entities, and we are including pronouns as entities, whereas in the past, pronouns were never considered as entities in entity linking. We have built 2 models, both outperforms our baseline model significantly. The purpose of our project is to build a model that could be use to generate cleaner data for future entity linking tasks. Our contribution include a clean data set consisting of 50Wikipedia people pages, and 2 entity linking models, specifically tuned for this domain.
An improved Ant Colony System for the Sequential Ordering Problem
Venue: arXiv cs.AI 2017
Year: 2017

It is not rare that the performance of one metaheuristic algorithm can be improved by incorporating ideas taken from another. In this article we present how Simulated Annealing (SA) can be used to improve the efficiency of the Ant Colony System (ACS) and Enhanced ACS when solving the Sequential Ordering Problem (SOP). Moreover, we show how the very same ideas can be applied to improve the convergence of a dedicated local search, i.e. the SOP-3-exchange algorithm. A statistical analysis of the proposed algorithms both in terms of finding suitable parameter values and the quality of the generated solutions is presented based on a series of computational experiments conducted on SOP instances from the well-known TSPLIB and SOPLIB2006 repositories. The proposed ACS-SA and EACS-SA algorithms often generate solutions of better quality than the ACS and EACS, respectively. Moreover, the EACS-SA algorithm combined with the proposed SOP-3-exchange-SA local search was able to find 10 new best solutions for the SOP instances from the SOPLIB2006 repository, thus improving the state-of-the-art results as known from the literature. Overall, the best known or improved solutions were found in 41 out of 48 cases.
The N-Tuple Bandit Evolutionary Algorithm for Automatic Game Improvement
Venue: arXiv cs.AI 2017
Year: 2017

This paper describes a new evolutionary algorithm that is especially well suited to AI-Assisted Game Design. The approach adopted in this paper is to use observations of AI agents playing the game to estimate the game's quality. Some of best agents for this purpose are General Video Game AI agents, since they can be deployed directly on a new game without game-specific tuning; these agents tend to be based on stochastic algorithms which give robust but noisy results and tend to be expensive to run. This motivates the main contribution of the paper: the development of the novel N-Tuple Bandit Evolutionary Algorithm, where a model is used to estimate the fitness of unsampled points and a bandit approach is used to balance exploration and exploitation of the search space. Initial results on optimising a Space Battle game variant suggest that the algorithm offers far more robust results than the Random Mutation Hill Climber and a Biased Mutation variant, which are themselves known to offer competitive performance across a range of problems. Subjective observations are also given by human players on the nature of the evolved games, which indicate a preference towards games generated by the N-Tuple algorithm.
The Power of Shared Randomness in Uncertain Communication
Venue: arXiv cs.IT 2017
Year: 2017

In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function $f$ and an input string $x$, and Bob is given a function $g$ and an input string $y$. The pair $(x,y)$ comes from a known distribution $μ$ and $f$ and $g$ are guaranteed to be close under this distribution. Alice and Bob wish to compute $g(x,y)$ with high probability. The previous work showed that any problem with one-way communication complexity $k$ in the standard model has public-coin communication $O(k(1+I))$ bits in the uncertain case, where $I$ is the mutual information between $x$ and $y$. A lower bound of $Ω(\sqrt{I})$ bits on the public-coin uncertain communication was also shown. An important question that was left open is the power that public randomness brings to uncertain communication. Can Alice and Bob achieve efficient communication amid uncertainty without using public randomness? How powerful are public-coin protocols in overcoming uncertainty? Motivated by these two questions: - We prove the first separation between private-coin uncertain communication and public-coin uncertain communication. We exhibit a function class for which the communication in the standard model and the public-coin uncertain communication are $O(1)$ while the private-coin uncertain communication is a growing function of the length $n$ of the inputs. - We improve the lower-bound of the previous work on public-coin uncertain communication. We exhibit a function class and a distribution (with $I \approx n$) for which the one-way certain communication is $k$ bits but the one-way public-coin uncertain communication is at least $Ω(\sqrt{k} \cdot \sqrt{I})$ bits.
Population protocols for leader election and exact majority with O(log^2 n) states and O(log^2 n) convergence time
Venue: arXiv cs.DC 2017
Year: 2017

We consider the model of population protocols, which can be viewed as a sequence of random pairwise interactions of $n$ agents (nodes). We show population protocols for two problems: the leader election and the exact majority voting. The leader election starts with all agents in the same initial state and the goal is to converge to the (global) state when exactly one agent is in a distinct state $L$. The exact majority voting starts with each agent in one of the two distinct states $A$ or $B$ and the goal is to make all nodes know which of these two states was the initial majority state, even if that majority was just by a single vote. Alistarh and Gelashvili [ICALP 2015] showed a leader-election protocol which converges in $O(\log^3 n)$ time w.h.p. and in expectation and needs $Θ(\log^3 n)$ states per agent. We present a protocol which elects the leader in $O(\log^2 n)$ time w.h.p. and in expectation and uses $Θ(\log^2 n)$ states per agent. For the exact majority voting, we show a population protocol with the same asymptotic performance: $O(\log^2 n)$ time and $Θ(\log^2 n)$ states per agent. The exact-majority protocol proposed by Alistarh et al. [PODC 2015] achieves expected $O(\log^2 n)$ time, but requires a relatively high initial imbalance between $A$'s and $B$'s or a large number of states per agent. More recently, Alistarh et al. [SODA 2017] showed $O(\log^2 n)$-state protocols for both problems, with the exact majority protocol converging in time $O(\log^3 n)$, and the leader election protocol converging in time $O(\log^{6.3} n)$ w.h.p. and $O(\log^{5.3} n)$ in expectation. Our leader election and exact majority protocols are based on the idea of agents counting their local interactions and rely on the probabilistic fact that the uniform random selection would limit the divergence of the individual counts.
Recovery of structure of looped jointed objects from multiframes
Venue: arXiv cs.CV 2017
Year: 2017

A method to recover structural parameters of looped jointed objects from multiframes is being developed. Each rigid part of the jointed body needs only to be traced at two (that is at junction) points. This method has been linearized for 4-part loops, with recovery from at least 19 frames.
Imagining Probabilistic Belief Change as Imaging (Technical Report)
Venue: arXiv cs.AI 2017
Year: 2017

Imaging is a form of probabilistic belief change which could be employed for both revision and update. In this paper, we propose a new framework for probabilistic belief change based on imaging, called Expected Distance Imaging (EDI). EDI is sufficiently general to define Bayesian conditioning and other forms of imaging previously defined in the literature. We argue that, and investigate how, EDI can be used for both revision and update. EDI's definition depends crucially on a weight function whose properties are studied and whose effect on belief change operations is analysed. Finally, four EDI instantiations are proposed, two for revision and two for update, and probabilistic rationality postulates are suggested for their analysis.
Analyzing Knowledge Transfer in Deep Q-Networks for Autonomously Handling Multiple Intersections
Venue: arXiv cs.LG 2017
Year: 2017

We analyze how the knowledge to autonomously handle one type of intersection, represented as a Deep Q-Network, translates to other types of intersections (tasks). We view intersection handling as a deep reinforcement learning problem, which approximates the state action Q function as a deep neural network. Using a traffic simulator, we show that directly copying a network trained for one type of intersection to another type of intersection decreases the success rate. We also show that when a network that is pre-trained on Task A and then is fine-tuned on a Task B, the resulting network not only performs better on the Task B than an network exclusively trained on Task A, but also retained knowledge on the Task A. Finally, we examine a lifelong learning setting, where we train a single network on five different types of intersections sequentially and show that the resulting network exhibited catastrophic forgetting of knowledge on previous tasks. This result suggests a need for a long-term memory component to preserve knowledge.
A Hybrid Architecture for Multi-Party Conversational Systems
Venue: arXiv cs.CL 2017
Year: 2017

Multi-party Conversational Systems are systems with natural language interaction between one or more people or systems. From the moment that an utterance is sent to a group, to the moment that it is replied in the group by a member, several activities must be done by the system: utterance understanding, information search, reasoning, among others. In this paper we present the challenges of designing and building multi-party conversational systems, the state of the art, our proposed hybrid architecture using both rules and machine learning and some insights after implementing and evaluating one on the finance domain.
Marine Animal Classification with Correntropy Loss Based Multi-view Learning
Venue: arXiv cs.CV 2017
Year: 2017

To analyze marine animals behavior, seasonal distribution and abundance, digital imagery can be acquired by visual or Lidar camera. Depending on the quantity and properties of acquired imagery, the animals are characterized as either features (shape, color, texture, etc.), or dissimilarity matrices derived from different shape analysis methods (shape context, internal distance shape context, etc.). For both cases, multi-view learning is critical in integrating more than one set of feature or dissimilarity matrix for higher classification accuracy. This paper adopts correntropy loss as cost function in multi-view learning, which has favorable statistical properties for rejecting noise. For the case of features, the correntropy loss-based multi-view learning and its entrywise variation are developed based on the multi-view intact space learning algorithm. For the case of dissimilarity matrices, the robust Euclidean embedding algorithm is extended to its multi-view form with the correntropy loss function. Results from simulated data and real-world marine animal imagery show that the proposed algorithms can effectively enhance classification rate, as well as suppress noise under different noise conditions.
Amobee at SemEval-2017 Task 4: Deep Learning System for Sentiment Detection on Twitter
Venue: arXiv cs.CL 2017
Year: 2017

This paper describes the Amobee sentiment analysis system, adapted to compete in SemEval 2017 task 4. The system consists of two parts: a supervised training of RNN models based on a Twitter sentiment treebank, and the use of feedforward NN, Naive Bayes and logistic regression classifiers to produce predictions for the different sub-tasks. The algorithm reached the 3rd place on the 5-label classification task (sub-task C).
Benefits of Mobile End User Network Switching and Multihoming
Venue: arXiv cs.NI 2017
Year: 2017

Mobile users have not been able to exploit spatio-temporal differences between individual mobile networks operators for a variety of reasons. End user network switching and multihoming are two promising mechanisms that could allow such exploitation. However these mechanisms have not been thoroughly explored at a general system level with QoE metrics. Therefore, in this work we analyze these mechanisms in a variety of diverse scenarios through a system level model based on an agent based modeling framework. In terms of results, we find that in all scenarios end user network switching provides significant benefits in terms of both throughput and mean opinion score as the number of available networks increases. However, contrastingly, end user multihoming in most scenarios does not provide significant benefits over network switching given the same number of available networks. The major reason is inefficient radio resource allocation resulting from individual networks not taking the multihoming nature of end users into account. Though, in low user density situations this inefficiency is not a problem and multihoming does provide increased throughput though not increased mean opinion scores. Finally, scenarios that vary the fraction of users adopting multihoming suggests that both early and late adopters will have similar gains over users not adopting multihoming. Thus the adoption dynamics of multihoming appear favorable. Overall, the results support the applicability of end user network switching for improving mobile user experience and the applicability of end user multihoming in more limited situations.