OpenRaiser/Intern-Atlas huggingface dataset:
Fourier bounds and pseudorandom generators for product tests
Venue: arXiv cs.CC 2019
Year: 2019

We study the Fourier spectrum of functions $f\colon \{0,1\}^{mk} \to \{-1,0,1\}$ which can be written as a product of $k$ Boolean functions $f_i$ on disjoint $m$-bit inputs. We prove that for every positive integer $d$, \[ \sum_{S \subseteq [mk]: |S|=d} |\hat{f_S}| = O(m)^d . \] Our upper bound is tight up to a constant factor in the $O(\cdot)$. Our proof builds on a new `level-$d$ inequality' that bounds above $\sum_{|S|=d} \hat{f_S}^2$ for any $[0,1]$-valued function $f$ in terms of its expectation, which may be of independent interest. As a result, we construct pseudorandom generators for such functions with seed length $\tilde O(m + \log(k/\varepsilon))$, which is optimal up to polynomial factors in $\log m$, $\log\log k$ and $\log\log(1/\varepsilon)$. Our generator in particular works for the well-studied class of combinatorial rectangles, where in addition we allow the bits to be read in any order. Even for this special case, previous generators have an extra $\tilde O(\log(1/\varepsilon))$ factor in their seed lengths. Using Schur-convexity, we also extend our results to functions $f_i$ whose range is $[-1,1]$.
How Different Are Different diff Algorithms in Git?
Venue: arXiv cs.SE 2019
Year: 2019

Automatic identification of the differences between two versions of a file is a common and basic task in several applications of mining code repositories. Git, a version control system, has a diff utility and users can select algorithms of diff from the default algorithm Myers to the advanced Histogram algorithm. From our systematic mapping, we identified three popular applications of diff in recent studies. On the impact on code churn metrics in 14 Java projects, we obtained different values in 1.7% to 8.2% commits based on the different diff algorithms. Regarding bug-introducing change identification, we found 6.0% and 13.3% in the identified bug-fix commits had different results of bug-introducing changes from 10 Java projects. For patch application, we found that the Histogram is more suitable than Myers for providing the changes of code, from our manual analysis. Thus, we strongly recommend using the Histogram algorithm when mining Git repositories to consider differences in source code.
CHIP: Channel-wise Disentangled Interpretation of Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

With the widespread applications of deep convolutional neural networks (DCNNs), it becomes increasingly important for DCNNs not only to make accurate predictions but also to explain how they make their decisions. In this work, we propose a CHannel-wise disentangled InterPretation (CHIP) model to give the visual interpretation to the predictions of DCNNs. The proposed model distills the class-discriminative importance of channels in networks by utilizing the sparse regularization. Here, we first introduce the network perturbation technique to learn the model. The proposed model is capable to not only distill the global perspective knowledge from networks but also present the class-discriminative visual interpretation for specific predictions of networks. It is noteworthy that the proposed model is able to interpret different layers of networks without re-training. By combining the distilled interpretation knowledge in different layers, we further propose the Refined CHIP visual interpretation that is both high-resolution and class-discriminative. Experimental results on the standard dataset demonstrate that the proposed model provides promising visual interpretation for the predictions of networks in image classification task compared with existing visual interpretation methods. Besides, the proposed method outperforms related approaches in the application of ILSVRC 2015 weakly-supervised localization task.
On interface conditions for flows in coupled free-porous media
Venue: arXiv cs.CE 2019
Year: 2019

Many processes in nature (e.g., physical and biogeochemical processes in hyporheic zones, and arterial mass transport) occur near the interface of free-porous media. A firm understanding of these processes needs an accurate prescription of flow dynamics near the interface which (in turn) hinges on an appropriate description of interface conditions along the interface of free-porous media. Although the conditions for the flow dynamics at the interface of free-porous media have received considerable attention, many of these studies were empirical and lacked a firm theoretical underpinning. In this paper, we derive a complete and self-consistent set of conditions for flow dynamics at the interface of free-porous media. We first propose a principle of virtual power by incorporating the virtual power expended at the interface of free-porous media. Then by appealing to the calculus of variations, we obtain a complete set of interface conditions for flows in coupled free-porous media. A noteworthy feature of our approach is that the derived interface conditions apply to a wide variety of porous media models. We also show that the two most popular interface conditions -- the Beavers-Joseph condition and the Beavers-Joseph-Saffman condition -- are special cases of the approach presented in this paper. The proposed principle of virtual power also provides a minimum power theorem for a class of flows in coupled free-porous media, which has a similar mathematical structure as the ones enjoyed by flows in uncoupled free and porous media.
Going Far From Degeneracy
Venue: arXiv cs.DS 2019
Year: 2019

An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erdős and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least d+1. The proof of Erdős and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least d+1. But can we decide in polynomial time whether a graph contains a cycle of length at least d+2? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: deciding whether a graph has a cycle of length at least d+2 is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether G contains a cycle of length at least d+k can be done in time 2^{O(k)}|V(G)|^{O(1)}. In other words, deciding whether a 2-connected n-vertex G contains a cycle of length at least d+log n can be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at least d+1 is NP-complete. However, we prove that if graph G is connected, then deciding whether G contains a path of length at least d+k can be done in time 2^{O(k)}n^{O(1)}. We complement these results by showing that the choice of degeneracy as the `above guarantee parameterization' is optimal in the following sense: For any ε>0 it is NP-complete to decide whether a connected (2-connected) graph of degeneracy d has a path (cycle) of length at least (1+ε)d.
Crowdsourcing open citations with CROCI -- An analysis of the current status of open citations, and a proposal
Venue: arXiv cs.DL 2019
Year: 2019

In this paper, we analyse the current availability of open citations data in one particular dataset, namely COCI (the OpenCitations Index of Crossref open DOI-to-DOI citations; http://opencitations.net/index/coci) provided by OpenCitations. The results of these analyses show a persistent gap in the coverage of the currently available open citation data. In order to address this specific issue, we propose a strategy whereby the community (e.g. scholars and publishers) can directly involve themselves in crowdsourcing open citations, by uploading their citation data via the OpenCitations infrastructure into our new index, CROCI, the Crowdsourced Open Citations Index.
Response Time and Availability Study of RAFT Consensus in Distributed SDN Control Plane
Venue: arXiv cs.NI 2019
Year: 2019

Software defined networking (SDN) promises unprecedented flexibility and ease of network operations. While flexibility is an important factor when leveraging advantages of a new technology, critical infrastructure networks also have stringent requirements on network robustness and control plane delays. Robustness in the SDN control plane is realized by deploying multiple distributed controllers, formed into clusters for durability and fast-failover purposes. However, the effect of the controller clustering on the total system response time is not well investigated in current literature. Hence, in this work we provide a detailed analytical study of the distributed consensus algorithm RAFT, implemented in OpenDaylight and ONOS SDN controller platforms. In those controllers, RAFT implements the data-store replication, leader election after controller failures and controller state recovery on successful repairs. To evaluate its performance, we introduce a framework for numerical analysis of various SDN cluster organizations w.r.t. their response time and availability metrics. We use Stochastic Activity Networks for modeling the RAFT operations, failure injection and cluster recovery processes, and using real-world experiments, we collect the rate parameters to provide realistic inputs for a representative cluster recovery model. We also show how a fast rejuvenation mechanism for the treatment of failures induced by software errors can minimize the total response time experienced by the controller clients, while guaranteeing a higher system availability in the long-term.
VirtuWind - An SDN- and NFV-based Architecture for Softwarized Industrial Networks
Venue: arXiv cs.NI 2019
Year: 2019

VirtuWind proposes the application of Software Defined Networking (SDN) and Network Functions Virtualization (NFV) in critical infrastructure networks. We aim at introducing network programmability, reconfigurability and multi-tenant capability both inside isolated and inter-connected industrial networks. Henceforth, we present the design of the VirtuWind architecture that addresses the requirements of industrial communications: granular Quality of Service (QoS) guarantees, system modularity and secure and isolated per-tenant network access. We present the functional components of our architecture and provide an overview of the appropriate realization mechanisms. Finally, we map two exemplary industrial system use-cases to the designed architecture to showcase its applicability in an exemplary industrial wind park network.
EMaaS: Energy Measurements as a Service for Mobile Applications
Venue: arXiv cs.SE 2019
Year: 2019

Measuring energy consumption is a challenging task faced by developers when building mobile apps. This paper presents EMaaS: a system that provides reliable energy measurements for mobile applications, without requiring a complex setup. It combines estimations from an energy model with --- typically more reliable, but also expensive --- hardware-based measurements. On a per scenario basis, it decides whether the energy model is able to provide a reliable estimation of energy consumption. Otherwise, hardware-based measurements are provided. In addition, the system is accessible to the community of mobile software practitioners/researchers in the form of a Software as a Service. With this service, we aim at solving current problems in the field of energy efficiency in mobile software engineering: the complexity of hardware-based power monitor tools, the reliability of energy models, and the continuous need of data to build energy models.
Bounds for the VC Dimension of 1NN Prototype Sets
Venue: arXiv cs.LG 2019
Year: 2019

In Statistical Learning, the Vapnik-Chervonenkis (VC) dimension is an important combinatorial property of classifiers. To our knowledge, no theoretical results yet exist for the VC dimension of edited nearest-neighbour (1NN) classifiers with reference set of fixed size. Related theoretical results are scattered in the literature and their implications have not been made explicit. We collect some relevant results and use them to provide explicit lower and upper bounds for the VC dimension of 1NN classifiers with a prototype set of fixed size. We discuss the implications of these bounds for the size of training set needed to learn such a classifier to a given accuracy. Further, we provide a new lower bound for the two-dimensional case, based on a new geometrical argument.
Neural Network for NILM Based on Operational State Change Classification
Venue: arXiv cs.LG 2019
Year: 2019

Energy disaggregation in a non-intrusive way estimates appliance level electricity consumption from a single meter that measures the whole house electricity demand. Recently, with the ongoing increment of energy data, there are many data-driven deep learning architectures being applied to solve the non-intrusive energy disaggregation problem. However, most proposed methods try to estimate the on-off state or the power consumption of appliance, which need not only large amount of parameters, but also hyper-parameter optimization prior to training and even preprocessing of energy data for a specified appliance. In this paper, instead of estimating on-off state or power consumption, we adapt a neural network to estimate the operational state change of appliance. Our proposed solution is more feasible across various appliances and lower complexity comparing to previous methods. The simulated experiments in the low sample rate dataset REDD show the competitive performance of the designed method, with respect to other two benchmark methods, Hidden Markov Model-based and Graph Signal processing-based approaches.
StampNet: unsupervised multi-class object discovery
Venue: arXiv cs.CV 2019
Year: 2019

Unsupervised object discovery in images involves uncovering recurring patterns that define objects and discriminates them against the background. This is more challenging than image clustering as the size and the location of the objects are not known: this adds additional degrees of freedom and increases the problem complexity. In this work, we propose StampNet, a novel autoencoding neural network that localizes shapes (objects) over a simple background in images and categorizes them simultaneously. StampNet consists of a discrete latent space that is used to categorize objects and to determine the location of the objects. The object categories are formed during the training, resulting in the discovery of a fixed set of objects. We present a set of experiments that demonstrate that StampNet is able to localize and cluster multiple overlapping shapes with varying complexity including the digits from the MNIST dataset. We also present an application of StampNet in the localization of pedestrians in overhead depth-maps.
Structural Invariants for Parametric Verification of Systems with Almost Linear Architectures
Venue: arXiv cs.FL 2019
Year: 2019

We consider concurrent systems consisting of a finite but unknown number of components, that are replicated instances of a given set of finite state automata. The components communicate by executing interactions which are simultaneous atomic state changes of a set of components. We specify both the type of interactions (e.g.\ rendez-vous, broadcast) and the topology (i.e.\ architecture) of the system (e.g.\ pipeline, ring) via a decidable interaction logic, which is embedded in the classical weak sequential calculus of one successor (WS1S). Proving correctness of such system for safety properties, such as deadlock freedom or mutual exclusion, requires the inference of an inductive invariant that subsumes the set of reachable states and avoids the unsafe states. Our method synthesizes such invariants directly from the formula describing the interactions, without costly fixed point iterations. We applied our technique to the verification of several textbook examples, such as dining philosophers, mutual exclusion protocols and concurrent systems with preemption and priorities.
A Network-centric Framework for Auditing Recommendation Systems
Venue: arXiv cs.IR 2019
Year: 2019

To improve the experience of consumers, all social media, commerce and entertainment sites deploy Recommendation Systems (RSs) that aim to help users locate interesting content. These RSs are black-boxes - the way a chunk of information is filtered out and served to a user from a large information base is mostly opaque. No one except the parent company generally has access to the entire information required for auditing these systems - neither the details of the algorithm nor the user-item interactions are ever made publicly available for third-party auditors. Hence auditing RSs remains an important challenge, especially with the recent concerns about how RSs are affecting the views of the society at large with new technical jargons like "echo chambers", "confirmation biases", "filter bubbles" etc. in place. Many prior works have evaluated different properties of RSs such as diversity, novelty, etc. However, most of these have focused on evaluating static snapshots of RSs. Today, auditors are not only interested in these static evaluations on a snapshot of the system, but also interested in how these systems are affecting the society in course of time. In this work, we propose a novel network-centric framework which is not only able to quantify various static properties of RSs, but also is able to quantify dynamic properties such as how likely RSs are to lead to polarization or segregation of information among their users. We apply the framework to several popular movie RSs to demonstrate its utility.
Variational Recurrent Neural Networks for Graph Classification
Venue: arXiv cs.LG 2019
Year: 2019

We address the problem of graph classification based only on structural information. Inspired by natural language processing techniques (NLP), our model sequentially embeds information to estimate class membership probabilities. Besides, we experiment with NLP-like variational regularization techniques, making the model predict the next node in the sequence as it reads it. We experimentally show that our model achieves state-of-the-art classification results on several standard molecular datasets. Finally, we perform a qualitative analysis and give some insights on whether the node prediction helps the model better classify graphs.
Red Bots Do It Better: Comparative Analysis of Social Bot Partisan Behavior
Venue: arXiv cs.SI 2019
Year: 2019

Recent research brought awareness of the issue of bots on social media and the significant risks of mass manipulation of public opinion in the context of political discussion. In this work, we leverage Twitter to study the discourse during the 2018 US midterm elections and analyze social bot activity and interactions with humans. We collected 2.6 million tweets for 42 days around the election day from nearly 1 million users. We use the collected tweets to answer three research questions: (i) Do social bots lean and behave according to a political ideology? (ii) Can we observe different strategies among liberal and conservative bots? (iii) How effective are bot strategies? We show that social bots can be accurately classified according to their political leaning and behave accordingly. Conservative bots share most of the topics of discussion with their human counterparts, while liberal bots show less overlap and a more inflammatory attitude. We studied bot interactions with humans and observed different strategies. Finally, we measured bots embeddedness in the social network and the effectiveness of their activities. Results show that conservative bots are more deeply embedded in the social network and more effective than liberal bots at exerting influence on humans.
FDDB-360: Face Detection in 360-degree Fisheye Images
Venue: arXiv cs.CV 2019
Year: 2019

360-degree cameras offer the possibility to cover a large area, for example an entire room, without using multiple distributed vision sensors. However, geometric distortions introduced by their lenses make computer vision problems more challenging. In this paper we address face detection in 360-degree fisheye images. We show how a face detector trained on regular images can be re-trained for this purpose, and we also provide a 360-degree fisheye-like version of the popular FDDB face detection dataset, which we call FDDB-360.
Evaluating Crowd Density Estimators via Their Uncertainty Bounds
Venue: arXiv cs.CV 2019
Year: 2019

In this work, we use the Belief Function Theory which extends the probabilistic framework in order to provide uncertainty bounds to different categories of crowd density estimators. Our method allows us to compare the multi-scale performance of the estimators, and also to characterize their reliability for crowd monitoring applications requiring varying degrees of prudence.
Using Deep Q-learning To Prolong the Lifetime of Correlated Internet of Things Devices
Venue: arXiv cs.NI 2019
Year: 2019

Battery-powered sensors deployed in the Internet of Things (IoT) require energy-efficient solutions to prolong their lifetime. When these sensors observe a physical phenomenon distributed in space and evolving in time, the collected observations are expected to be correlated. We take advantage of the exhibited correlation and propose an updating mechanism that employs deep Q-learning. Our mechanism is capable of determining the frequency with which sensors should transmit their updates while taking into the consideration an ever-changing environment. We evaluate our solution using observations obtained in a real deployment, and show that our proposed mechanism is capable of significantly extending battery-powered sensors' lifetime without compromising the accuracy of the observations provided to the IoT service.
EYEORG: A Platform For Crowdsourcing Web Quality Of Experience Measurements
Venue: arXiv cs.NI 2019
Year: 2019

Tremendous effort has gone into the ongoing battle to make webpages load faster. This effort has culminated in new protocols (QUIC, SPDY, and HTTP/2) as well as novel content delivery mechanisms. In addition, companies like Google and SpeedCurve investigated how to measure "page load time" (PLT) in a way that captures human perception. In this paper we present Eyeorg, a platform for crowdsourcing web quality of experience measurements. Eyeorg overcomes the scaling and automation challenges of recruiting users and collecting consistent user-perceived quality measurements. We validate Eyeorg's capabilities via a set of 100 trusted participants. Next, we showcase its functionalities via three measurement campaigns, each involving 1,000 paid participants, to 1) study the quality of several PLT metrics, 2) compare HTTP/1.1 and HTTP/2 performance, and 3) assess the impact of online advertisements and ad blockers on user experience. We find that commonly used, and even novel and sophisticated PLT metrics fail to represent actual human perception of PLT, that the performance gains from HTTP/2 are imperceivable in some circumstances, and that not all ad blockers are created equal.
Deep execution monitor for robot assistive tasks
Venue: arXiv cs.AI 2019
Year: 2019

We consider a novel approach to high-level robot task execution for a robot assistive task. In this work we explore the problem of learning to predict the next subtask by introducing a deep model for both sequencing goals and for visually evaluating the state of a task. We show that deep learning for monitoring robot tasks execution very well supports the interconnection between task-level planning and robot operations. These solutions can also cope with the natural non-determinism of the execution monitor. We show that a deep execution monitor leverages robot performance. We measure the improvement taking into account some robot helping tasks performed at a warehouse.