OpenRaiser/Intern-Atlas huggingface dataset:
KBLRN : End-to-End Learning of Knowledge Base Representations with Latent, Relational, and Numerical Features
Venue: arXiv cs.AI 2018
Year: 2018

We present KBLRN, a framework for end-to-end learning of knowledge base representations from latent, relational, and numerical features. KBLRN integrates feature types with a novel combination of neural representation learning and probabilistic product of experts models. To the best of our knowledge, KBLRN is the first approach that learns representations of knowledge bases by integrating latent, relational, and numerical features. We show that instances of KBLRN outperform existing methods on a range of knowledge base completion tasks. We contribute a novel data sets enriching commonly used knowledge base completion benchmarks with numerical features. The data sets are available under a permissive BSD-3 license. We also investigate the impact numerical features have on the KB completion performance of KBLRN.
GREENER: A Tool for Improving Energy Efficiency of Register Files
Venue: arXiv cs.AR 2018
Year: 2018

Graphics Processing Units (GPUs) maintain a large register file to increase the thread level parallelism (TLP). To increase the TLP further, recent GPUs have increased the number of on-chip registers in every generation. However, with the increase in the register file size, the leakage power increases. Also, with the technology advances, the leakage power component has increased and has become an important consideration for the manufacturing process. The leakage power of a register file can be reduced by turning infrequently used registers into low power (drowsy or off) state after accessing them. A major challenge in doing so is the lack of runtime register access information. This paper proposes GREENER (GPU REgister file ENErgy Reducer): a system to minimize leakage energy of the register file of GPUs. GREENER employs a compile-time analysis to estimate the run-time register access information. The result of the analysis is used to determine the power state of the registers (ON, SLEEP, or OFF) after each instruction. We propose a power optimized assembly instruction set that allows GREENER to encode the power state of the registers in the executable itself. The modified assembly, along with a run-time optimization to update the power state of a register during execution, results in significant power reduction. We implemented GREENER in GPGPU-Sim simulator, and used GPUWattch framework to measure the register file's leakage power. Evaluation of GREENER on 21 kernels from CUDASDK, GPGPU-SIM, Parboil, and Rodinia benchmarks suites shows an average reduction of register leakage energy by 69.04% and maximum reduction of 87.95% with a negligible number of simulation cycles overhead (0.53% on average).
Validity-Guided Synthesis of Reactive Systems from Assume-Guarantee Contracts
Venue: arXiv cs.SE 2018
Year: 2018

Automated synthesis of reactive systems from specifications has been a topic of research for decades. Recently, a variety of approaches have been proposed to extend synthesis of reactive systems from proposi- tional specifications towards specifications over rich theories. We propose a novel, completely automated approach to program synthesis which reduces the problem to deciding the validity of a set of forall-exists formulas. In spirit of IC3 / PDR, our problem space is recursively refined by blocking out regions of unsafe states, aiming to discover a fixpoint that describes safe reactions. If such a fixpoint is found, we construct a witness that is directly translated into an implementation. We implemented the algorithm on top of the JKind model checker, and exercised it against contracts written using the Lustre specification language. Experimental results show how the new algorithm outperforms JKinds already existing synthesis procedure based on k-induction and addresses soundness issues in the k-inductive approach with respect to unrealizable results.
Synthesis of surveillance strategies via belief abstraction
Venue: arXiv cs.RO 2018
Year: 2018

We study the problem of synthesizing a controller for a robot with a surveillance objective, that is, the robot is required to maintain knowledge of the location of a moving, possibly adversarial target. We formulate this problem as a one-sided partial-information game in which the winning condition for the agent is specified as a temporal logic formula. The specification formalizes the surveillance requirement given by the user, including additional non-surveillance tasks. In order to synthesize a surveillance strategy that meets the specification, we transform the partial-information game into a perfect-information one, using abstraction to mitigate the exponential blow-up typically incurred by such transformations. This enables the use of off-the-shelf tools for reactive synthesis. We use counterexample-guided refinement to automatically achieve abstraction precision that is sufficient to synthesize a surveillance strategy. We evaluate the proposed method on two case-studies, demonstrating its applicability to large state-spaces and diverse requirements.
The Stochastic Geometry Analyses of Cellular Networks with α-Stable Self-Similarity
Venue: arXiv cs.IT 2018
Year: 2018

To understand the spatial deployment of base stations (BSs) is the first step to analyze the performance of cellular networks and further design efficient networking protocols. Poisson point process (PPP), which has been widely adopted to characterize the deployment of BSs and established the reputation to give tractable results in the stochastic geometry analyses, usually assumes a static BS deployment density in homogeneous PPP (HPPP) models or delicately designed location-dependent density functions in in-homogeneous PPP (IPPP) models. However, the simultaneous existence of attractiveness and repulsiveness among BSs practically deployed in a large-scale area defies such an assumption, and the $α$-stable distribution, one kind of heavy-tailed distributions, has recently demonstrated superior accuracy to statistically model the varying BS density in different areas. In this paper, we start with these new findings and investigate the intrinsic feature (i.e., the spatial self-similarity) embedded in the BSs. Afterwards, we refer to a generalized PPP setup with $α$-stable distributed density and theoretically derive the related coverage probability. In particular, we give an upper bound of the derived coverage probability for high signal-to-interference-plus-noise ratio (SINR) thresholds and show the monotonically decreasing property of this bound with respect to the variance of BS density. Besides, we prove that our model could reduce to the single-tier HPPP for some special cases, and demonstrate the superior accuracy of the $α$-stable model to approach the real environment.
Modeling Infrastructure Sharing in mmWave Networks with Shared Spectrum Licenses
Venue: arXiv cs.IT 2018
Year: 2018

Competing cellular operators aggressively share infrastructure in many major US markets. If operators also were to share spectrum in next-generation millimeter-wave (mmWave) networks, intra-cellular interference will become correlated with inter-cellular interference. We propose a mathematical framework to model a multi-operator mmWave cellular network with co-located base-stations (BSs). We then characterize the signal-to-interference-plus-noise ratio (SINR) distribution for an arbitrary network and derive its coverage probability. To understand how varying the spatial correlation between different networks affects coverage probability, we derive special results for the two-operator scenario, where we construct the operators' individual networks from a single network via probabilistic coupling. For external validation, we devise a method to quantify and estimate spatial correlation from actual base-station deployments. We compare our two-operator model against an actual macro-cell-dominated network and an actual network primarily comprising distributed-antenna-system (DAS) nodes. Using the actual deployment data to set the parameters of our model, we observe that coverage probabilities for the model and actual deployments not only compare very well to each other, but also match nearly perfectly for the case of the DAS-node-dominated deployment. Another interesting observation is that a network that shares spectrum and infrastructure has a lower rate coverage probability than a network of the same number of BSs that shares neither spectrum nor infrastructure, suggesting that the latter is more suitable for low-rate applications.
Towards matching user mobility traces in large-scale datasets
Venue: arXiv cs.SI 2018
Year: 2018

The problem of unicity and reidentifiability of records in large-scale databases has been studied in different contexts and approaches, with focus on preserving privacy or matching records from different data sources. With an increasing number of service providers nowadays routinely collecting location traces of their users on unprecedented scales, there is a pronounced interest in the possibility of matching records and datasets based on spatial trajectories. Extending previous work on reidentifiability of spatial data and trajectory matching, we present the first large-scale analysis of user matchability in real mobility datasets on realistic scales, i.e. among two datasets that consist of several million people's mobility traces, coming from a mobile network operator and transportation smart card usage. We extract the relevant statistical properties which influence the matching process and analyze their impact on the matchability of users. We show that for individuals with typical activity in the transportation system (those making 3-4 trips per day on average), a matching algorithm based on the co-occurrence of their activities is expected to achieve a 16.8% success only after a one-week long observation of their mobility traces, and over 55% after four weeks. We show that the main determinant of matchability is the expected number of co-occurring records in the two datasets. Finally, we discuss different scenarios in terms of data collection frequency and give estimates of matchability over time. We show that with higher frequency data collection becoming more common, we can expect much higher success rates in even shorter intervals.
Bounds on Binary Locally Repairable Codes Tolerating Multiple Erasures
Venue: arXiv cs.IT 2018
Year: 2018

Recently, locally repairable codes has gained significant interest for their potential applications in distributed storage systems. However, most constructions in existence are over fields with size that grows with the number of servers, which makes the systems computationally expensive and difficult to maintain. Here, we study linear locally repairable codes over the binary field, tolerating multiple local erasures. We derive bounds on the minimum distance on such codes, and give examples of LRCs achieving these bounds. Our main technical tools come from matroid theory, and as a byproduct of our proofs, we show that the lattice of cyclic flats of a simple binary matroid is atomic.
A Participatory Democratic Budgeting Algorithm
Venue: arXiv cs.GT 2018
Year: 2018

The budget is the key means for effecting policy in democracies, yet its preparation is typically an excluding, opaque, and arcane process. We aim to rectify this by providing for the democratic creation of complete budgets --- for cooperatives, cities, or states. Such budgets are typically (i) prepared, discussed, and voted upon by comparing and contrasting with last-year's budget, (ii) quantitative, in that items appear in quantities with potentially varying costs, and (iii) hierarchical, reflecting the organization's structure. Our process can be used by a budget committee, the legislature or the electorate at large. We allow great flexibility in vote elicitation, from perturbing last-year's budget to a complete ranked budget proposal. We present a polynomial-time algorithm which takes such votes, last-year's budget, and a budget limit as input and produces a budget that is provably "democratically optimal" (Condorcet-consistent), in that no proposed change to it has majority support among the votes.
Object Recognition from very few Training Examples for Enhancing Bicycle Maps
Venue: arXiv cs.CV 2018
Year: 2018

In recent years, data-driven methods have shown great success for extracting information about the infrastructure in urban areas. These algorithms are usually trained on large datasets consisting of thousands or millions of labeled training examples. While large datasets have been published regarding cars, for cyclists very few labeled data is available although appearance, point of view, and positioning of even relevant objects differ. Unfortunately, labeling data is costly and requires a huge amount of work. In this paper, we thus address the problem of learning with very few labels. The aim is to recognize particular traffic signs in crowdsourced data to collect information which is of interest to cyclists. We propose a system for object recognition that is trained with only 15 examples per class on average. To achieve this, we combine the advantages of convolutional neural networks and random forests to learn a patch-wise classifier. In the next step, we map the random forest to a neural network and transform the classifier to a fully convolutional network. Thereby, the processing of full images is significantly accelerated and bounding boxes can be predicted. Finally, we integrate data of the Global Positioning System (GPS) to localize the predictions on the map. In comparison to Faster R-CNN and other networks for object recognition or algorithms for transfer learning, we considerably reduce the required amount of labeled data. We demonstrate good performance on the recognition of traffic signs for cyclists as well as their localization in maps.
The shortest way to visit all metro lines in a city
Venue: arXiv cs.AI 2018
Year: 2018

What if $\{$a tourist, a train addict, Dr. Sheldon Cooper, somebody who likes to waste time$\}$ wants to visit all metro lines or carriages in a given network in a minimum number of steps? We study this problem with an application to the metro network of Paris and Tokyo, proposing optimal solutions thanks to mathematical programming tools. Quite surprisingly, it appears that you can visit all 16 Parisian metro lines in only 26 steps (we denote by a step the act of taking the metro from one station to an adjacent one). Perhaps even more surprisingly, adding the 5 RER lines to these 16 lines does not increase the size of the best solution. It is also possible to visit the 13 lines of (the dense network of) Tokyo with only 15 steps.
Video Object Segmentation Without Temporal Information
Venue: arXiv cs.CV 2018
Year: 2018

Video Object Segmentation, and video processing in general, has been historically dominated by methods that rely on the temporal consistency and redundancy in consecutive video frames. When the temporal smoothness is suddenly broken, such as when an object is occluded, or some frames are missing in a sequence, the result of these methods can deteriorate significantly or they may not even produce any result at all. This paper explores the orthogonal approach of processing each frame independently, i.e disregarding the temporal information. In particular, it tackles the task of semi-supervised video object segmentation: the separation of an object from the background in a video, given its mask in the first frame. We present Semantic One-Shot Video Object Segmentation (OSVOS-S), based on a fully-convolutional neural network architecture that is able to successively transfer generic semantic information, learned on ImageNet, to the task of foreground segmentation, and finally to learning the appearance of a single annotated object of the test sequence (hence one shot). We show that instance level semantic information, when combined effectively, can dramatically improve the results of our previous method, OSVOS. We perform experiments on two recent video segmentation databases, which show that OSVOS-S is both the fastest and most accurate method in the state of the art.
Local decoding and testing of polynomials over grids
Venue: arXiv cs.CC 2018
Year: 2018

The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate polynomials of total degree at most $d$ over grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \times A_n$, form error-correcting codes (of distance at least $2^{-d}$ provided $\min_i\{|A_i|\}\geq 2$). In this work we explore their local decodability and (tolerant) local testability. While these aspects have been studied extensively when $A_1 = \cdots = A_n = \mathbb{F}_q$ are the same finite field, the setting when $A_i$'s are not the full field does not seem to have been explored before. In this work we focus on the case $A_i = \{0,1\}$ for every $i$. We show that for every field (finite or otherwise) there is a test whose query complexity depends only on the degree (and not on the number of variables). In contrast we show that decodability is possible over fields of positive characteristic (with query complexity growing with the degree of the polynomial and the characteristic), but not over the reals, where the query complexity must grow with $n$. As a consequence we get a natural example of a code (one with a transitive group of symmetries) that is locally testable but not locally decodable. Classical results on local decoding and testing of polynomials have relied on the 2-transitive symmetries of the space of low-degree polynomials (under affine transformations). Grids do not possess this symmetry: So we introduce some new techniques to overcome this handicap and in particular use the hypercontractivity of the (constant weight) noise operator on the Hamming cube.
Target-adaptive CNN-based pansharpening
Venue: arXiv cs.CV 2018
Year: 2018

We recently proposed a convolutional neural network (CNN) for remote sensing image pansharpening obtaining a significant performance gain over the state of the art. In this paper, we explore a number of architectural and training variations to this baseline, achieving further performance gains with a lightweight network which trains very fast. Leveraging on this latter property, we propose a target-adaptive usage modality which ensures a very good performance also in the presence of a mismatch w.r.t. the training set, and even across different sensors. The proposed method, published online as an off-the-shelf software tool, allows users to perform fast and high-quality CNN-based pansharpening of their own target images on general-purpose hardware.
A Survey of Machine Learning for Big Code and Naturalness
Venue: arXiv cs.SE 2018
Year: 2018

Research at the intersection of machine learning, programming languages, and software engineering has recently taken important steps in proposing learnable probabilistic models of source code that exploit code's abundance of patterns. In this article, we survey this work. We contrast programming languages against natural languages and discuss how these similarities and differences drive the design of probabilistic models. We present a taxonomy based on the underlying design principles of each model and use it to navigate the literature. Then, we review how researchers have adapted these models to application areas and discuss cross-cutting and application-specific challenges and opportunities.
Rethink ReLU to Training Better CNNs
Venue: arXiv cs.CV 2018
Year: 2018

Most of convolutional neural networks share the same characteristic: each convolutional layer is followed by a nonlinear activation layer where Rectified Linear Unit (ReLU) is the most widely used. In this paper, we argue that the designed structure with the equal ratio between these two layers may not be the best choice since it could result in the poor generalization ability. Thus, we try to investigate a more suitable method on using ReLU to explore the better network architectures. Specifically, we propose a proportional module to keep the ratio between convolution and ReLU amount to be N:M (N>M). The proportional module can be applied in almost all networks with no extra computational cost to improve the performance. Comprehensive experimental results indicate that the proposed method achieves better performance on different benchmarks with different network architectures, thus verify the superiority of our work.
A Recorded Debating Dataset
Venue: arXiv cs.CL 2018
Year: 2018

This paper describes an English audio and textual dataset of debating speeches, a unique resource for the growing research field of computational argumentation and debating technologies. We detail the process of speech recording by professional debaters, the transcription of the speeches with an Automatic Speech Recognition (ASR) system, their consequent automatic processing to produce a text that is more "NLP-friendly", and in parallel -- the manual transcription of the speeches in order to produce gold-standard "reference" transcripts. We release 60 speeches on various controversial topics, each in five formats corresponding to the different stages in the production of the data. The intention is to allow utilizing this resource for multiple research purposes, be it the addition of in-domain training data for a debate-specific ASR system, or applying argumentation mining on either noisy or clean debate transcripts. We intend to make further releases of this data in the future.
PeerHunter: Detecting Peer-to-Peer Botnets through Community Behavior Analysis
Venue: arXiv cs.CR 2018
Year: 2018

Peer-to-peer (P2P) botnets have become one of the major threats in network security for serving as the infrastructure that responsible for various of cyber-crimes. Though a few existing work claimed to detect traditional botnets effectively, the problem of detecting P2P botnets involves more challenges. In this paper, we present PeerHunter, a community behavior analysis based method, which is capable of detecting botnets that communicate via a P2P structure. PeerHunter starts from a P2P hosts detection component. Then, it uses mutual contacts as the main feature to cluster bots into communities. Finally, it uses community behavior analysis to detect potential botnet communities and further identify bot candidates. Through extensive experiments with real and simulated network traces, PeerHunter can achieve very high detection rate and low false positives.
A Server-based Approach for Predictable GPU Access with Improved Analysis
Venue: arXiv cs.DC 2018
Year: 2018

We propose a server-based approach to manage a general-purpose graphics processing unit (GPU) in a predictable and efficient manner. Our proposed approach introduces a GPU server that is a dedicated task to handle GPU requests from other tasks on their behalf. The GPU server ensures bounded time to access the GPU, and allows other tasks to suspend during their GPU computation to save CPU cycles. By doing so, we address the two major limitations of the existing real-time synchronization-based GPU management approach: busy waiting and long priority inversion. We have implemented a prototype of the server-based approach on a real embedded platform. This case study demonstrates the practicality and effectiveness of the server-based approach. Experimental results indicate that the server-based approach yields significant improvements in task schedulability over the existing synchronization-based approach in most practical settings. Although we focus on a GPU in this paper, the server-based approach can also be used for other types of computational accelerators.