OpenRaiser/Intern-Atlas huggingface dataset:
Incrementally Learned Mixture Models for GNSS Localization
Venue: arXiv cs.RO 2020
Year: 2020

GNSS localization is an important part of today's autonomous systems, although it suffers from non-Gaussian errors caused by non-line-of-sight effects. Recent methods are able to mitigate these effects by including the corresponding distributions in the sensor fusion algorithm. However, these approaches require prior knowledge about the sensor's distribution, which is often not available. We introduce a novel sensor fusion algorithm based on variational Bayesian inference, that is able to approximate the true distribution with a Gaussian mixture model and to learn its parametrization online. The proposed Incremental Variational Mixture algorithm automatically adapts the number of mixture components to the complexity of the measurement's error distribution. We compare the proposed algorithm against current state-of-the-art approaches using a collection of open access real world datasets and demonstrate its superior localization accuracy.
Fast hashing with Strong Concentration Bounds
Venue: arXiv cs.DS 2020
Year: 2020

Previous work on tabulation hashing by Patrascu and Thorup from STOC'11 on simple tabulation and from SODA'13 on twisted tabulation offered Chernoff-style concentration bounds on hash based sums, e.g., the number of balls/keys hashing to a given bin, but under some quite severe restrictions on the expected values of these sums. The basic idea in tabulation hashing is to view a key as consisting of $c=O(1)$ characters, e.g., a 64-bit key as $c=8$ characters of 8-bits. The character domain $Σ$ should be small enough that character tables of size $|Σ|$ fit in fast cache. The schemes then use $O(1)$ tables of this size, so the space of tabulation hashing is $O(|Σ|)$. However, the concentration bounds by Patrascu and Thorup only apply if the expected sums are $\ll |Σ|$. To see the problem, consider the very simple case where we use tabulation hashing to throw $n$ balls into $m$ bins and want to analyse the number of balls in a given bin. With their concentration bounds, we are fine if $n=m$, for then the expected value is $1$. However, if $m=2$, as when tossing $n$ unbiased coins, the expected value $n/2$ is $\gg |Σ|$ for large data sets, e.g., data sets that do not fit in fast cache. To handle expectations that go beyond the limits of our small space, we need a much more advanced analysis of simple tabulation, plus a new tabulation technique that we call \emph{tabulation-permutation} hashing which is at most twice as slow as simple tabulation. No other hashing scheme of comparable speed offers similar Chernoff-style concentration bounds.
A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
Venue: arXiv cs.FL 2020
Year: 2020

We introduce MSO graph storage types, and call a storage type MSO-expressible if it is isomorphic to some MSO graph storage type. An MSO graph storage type has MSO-definable sets of graphs as storage configurations and as storage transformations. We consider sequential automata with MSO graph storage and associate with each such automaton a string language (in the usual way) and a graph language; a graph is accepted by the automaton if it represents a correct sequence of storage configurations for a given input string. For each MSO graph storage type, we define an MSO logic which is a subset of the usual MSO logic on graphs. We prove a Büchi-Elgot-Trakhtenbrot theorem, both for the string case and the graph case. Moreover, we prove that (i) each MSO graph transduction can be used as storage transformation in an MSO graph storage type, (ii) every automatic storage type is MSO-expressible, and (iii) the pushdown operator on storage types preserves the property of MSO-expressibility. Thus, the iterated pushdown storage types are MSO-expressible.
Face Identification using Local Ternary Tree Pattern based Spatial Structural Components
Venue: arXiv cs.CV 2020
Year: 2020

This paper reports a face identification system which makes use of a novel local descriptor called Local Ternary Tree Pattern (LTTP). Exploiting and extracting distinctive local descriptor from a face image plays a crucial role in face identification task in the presence of a variety of face images including constrained, unconstrained and plastic surgery images. LTTP has been used to extract robust and useful spatial features which use to describe the various structural components on a face. To extract the features, a ternary tree is formed for each pixel with its eight neighbors in each block. LTTP pattern can be generated in four forms such as LTTP Left Depth (LTTP LD), LTTP Left Breadth (LTTP LB), LTTP Right Depth (LTTP RD) and LTTP Right Breadth (LTTP RB). The encoding schemes of these patterns are very simple and efficient in terms of computational as well as time complexity. The proposed face identification system is tested on six face databases, namely, the UMIST, the JAFFE, the extended Yale face B, the Plastic Surgery, the LFW and the UFI. The experimental evaluation demonstrates the most promising results considering a variety of faces captured under different environments. The proposed LTTP based system is also compared with some local descriptors under identical conditions.
Mimic Learning to Generate a Shareable Network Intrusion Detection Model
Venue: arXiv cs.CR 2020
Year: 2020

Purveyors of malicious network attacks continue to increase the complexity and the sophistication of their techniques, and their ability to evade detection continues to improve as well. Hence, intrusion detection systems must also evolve to meet these increasingly challenging threats. Machine learning is often used to support this needed improvement. However, training a good prediction model can require a large set of labelled training data. Such datasets are difficult to obtain because privacy concerns prevent the majority of intrusion detection agencies from sharing their sensitive data. In this paper, we propose the use of mimic learning to enable the transfer of intrusion detection knowledge through a teacher model trained on private data to a student model. This student model provides a mean of publicly sharing knowledge extracted from private data without sharing the data itself. Our results confirm that the proposed scheme can produce a student intrusion detection model that mimics the teacher model without requiring access to the original dataset.
Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask
Venue: arXiv cs.LG 2020
Year: 2020

The recent "Lottery Ticket Hypothesis" paper by Frankle & Carbin showed that a simple approach to creating sparse networks (keeping the large weights) results in models that are trainable from scratch, but only when starting from the same initial weights. The performance of these networks often exceeds the performance of the non-sparse base model, but for reasons that were not well understood. In this paper we study the three critical components of the Lottery Ticket (LT) algorithm, showing that each may be varied significantly without impacting the overall results. Ablating these factors leads to new insights for why LT networks perform as well as they do. We show why setting weights to zero is important, how signs are all you need to make the reinitialized network train, and why masking behaves like training. Finally, we discover the existence of Supermasks, masks that can be applied to an untrained, randomly initialized network to produce a model with performance far better than chance (86% on MNIST, 41% on CIFAR-10).
Deep Residual Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

We revisit residual algorithms in both model-free and model-based reinforcement learning settings. We propose the bidirectional target network technique to stabilize residual algorithms, yielding a residual version of DDPG that significantly outperforms vanilla DDPG in the DeepMind Control Suite benchmark. Moreover, we find the residual algorithm an effective approach to the distribution mismatch problem in model-based planning. Compared with the existing TD($k$) method, our residual-based method makes weaker assumptions about the model and yields a greater performance boost.
Real Differences between OT and CRDT in Correctness and Complexity for Consistency Maintenance in Co-Editors
Venue: arXiv cs.DC 2020
Year: 2020

OT (Operational Transformation) was invented for supporting real-time co-editors in the late 1980s and has evolved to become core techniques widely used in today's working co-editors and adopted in industrial products. CRDT (Commutative Replicated Data Type) for co-editors was first proposed around 2006, under the name of WOOT (WithOut Operational Transformation). Follow-up CRDT variations are commonly labeled as "post-OT" techniques capable of making concurrent operations natively commutative in co-editors. On top of that, CRDT solutions have made broad claims of superiority over OT solutions, and often portrayed OT as an incorrect and inefficient technique. Over one decade later, however, CRDT is rarely found in working co-editors; OT remains the choice for building the vast majority of today's co-editors. Contradictions between the reality and CRDT's purported advantages have been the source of much confusion and debate among co-editing researcher sand developers. To seek truth from facts, we set out to conduct a comprehensive and critical review on representative OT and CRDT solutions and co-editors based on them. From this work, we have made important discoveries about OT and CRDT, and revealed facts and evidences that refute CRDT claims over OT on all accounts. These discoveries help explain the underlying reasons for the choice between OT and CRDT in the real world. We report these results in a series of three articles. In the second article of this series, we reveal the differences between OT and CRDT in their basic approaches to realizing the same general transformation and how such differences had resulted in different challenges and consequential correctness and complexity issues. Moreover, we reveal hidden complexity and algorithmic flaws with representative CRDT solutions, and discuss common myths and facts related to correctness and complexity of OT and CRDT.
Real Differences between OT and CRDT in Building Co-Editing Systems and Real World Applications
Venue: arXiv cs.DC 2020
Year: 2020

OT (Operational Transformation) was invented for supporting real-time co-editors in the late 1980s and has evolved to become a core technique used in today's working co-editors and adopted in major industrial products. CRDT (Commutative Replicated Data Type) for co-editors was first proposed around 2006, under the name of WOOT (WithOut Operational Transformation). Follow-up CRDT variations are commonly labeled as "post-OT" techniques and have made broad claims of superiority over OT solutions, in terms of correctness, time and space complexity, simplicity, etc. Over one decade later, however, OT remains the choice for building the vast majority of co-editors, whereas CRDT is rarely found in working co-editors. Why? To seek truth from facts, we set out to conduct a comprehensive and critical review of representative OT and CRDT solutions and working co-editors based on them. From this work, we have made important discoveries about OT and CRDT, and revealed facts and evidences that refute CRDT claims over OT on all accounts. We present our discoveries in three related and complementary articles. In prior two articles, we have revealed the similarities of OT and CRDT in following the same general transformation approach in co-editors, and their real differences in correctness and complexity. In this article, we examine the role of building working co-editors in shaping OT and CRDT research and solutions, and consequential differences in the choice between OT and CRDT in real world co-editors and industry products. In particular, we review the evolution of co-editors from research vehicles to real world applications, and discuss representative OT-based co-editors and alternative approaches in industry products and open source projects. Moreover, we evaluate CRDT-based co-editors in relation to published CRDT solutions, and clarify some myths surrounding "peer-to-peer" co-editing.
Real Differences between OT and CRDT under a General Transformation Framework for Consistency Maintenance in Co-Editors
Venue: arXiv cs.DC 2020
Year: 2020

OT (Operational Transformation) was invented for supporting real-time co-editors in the late 1980s and has evolved to become a core technique used in today's working co-editors and adopted in major industrial products. CRDT (Commutative Replicated Data Type) for co-editors was first proposed around 2006, under the name of WOOT (WithOut Operational Transformation). Follow-up CRDT variations are commonly labeled as "post-OT" techniques capable of making concurrent operations natively commutative in co-editors. On top of that, CRDT solutions have made broad claims of superiority over OT solutions, and routinely portrayed OT as an incorrect, complex and inefficient technique. Over one decade later, however, OT remains the choice for building the vast majority of co-editors, whereas CRDT is rarely found in working co-editors. Contradictions between the reality and CRDT's purported advantages have been the source of much confusion and debate in co-editing communities. Have the vast majority of co-editors been unfortunate in choosing the faulty and inferior OT, or those CRDT claims are false? What are the real differences between OT and CRDT for co-editors? What are the key factors and underlying reasons behind the choices between OT and CRDT in the real world? To seek truth from facts, we set out to conduct a comprehensive and critical review on representative OT and CRDT solutions and working co-editors based on them. From this work, we have made important discoveries about OT and CRDT, and revealed facts and evidences that refute CRDT claims over OT on all accounts. We report our discoveries in a series of three articles and the current article is the first one in this series. We hope the discoveries from this work help clear up common misconceptions and confusions surrounding OT and CRDT, and accelerate progress in co-editing technology for real world applications.
LP-based Approximation for Personalized Reserve Prices
Venue: arXiv cs.GT 2020
Year: 2020

We study the problem of computing data-driven personalized reserve prices in eager second price auctions without having any assumption on valuation distributions. Here, the input is a data-set that contains the submitted bids of $n$ buyers in a set of auctions and the problem is to return personalized reserve prices $\textbf r$ that maximize the revenue earned on these auctions by running eager second price auctions with reserve $\textbf r$. For this problem, which is known to be APX-hard, we present a novel LP formulation and a rounding procedure which achieves a $(1+2(\sqrt{2}-1)e^{\sqrt{2}-2})^{-1} \approx 0.684$-approximation. This improves over the $\frac{1}{2}$-approximation algorithm due to Roughgarden and Wang. We show that our analysis is tight for this rounding procedure. We also bound the integrality gap of the LP, which shows that it is impossible to design an algorithm that yields an approximation factor larger than $0.828$ with respect to this LP.
Optimal Beamforming for Hybrid Satellite Terrestrial Networks with Nonlinear PA and Imperfect CSIT
Venue: arXiv cs.NI 2020
Year: 2020

In hybrid satellite-terrestrial networks (HSTNs), spectrum sharing is crucial to alleviate the "spectrum scarcity" problem. Therein, the transmit beams should be carefully designed to mitigate the inter-satellite-terrestrial interference. Different from previous studies, this work considers the impact of both nonlinear power amplifier (PA) and large-scale channel state information at the transmitter (CSIT) on beamforming. These phenomena are usually inevitable in a practical HSTN. Based on the Saleh model of PA nonlinearity and the large-scale multi-beam satellite channel parameters, we formulate a beamforming optimization problem to maximize the achievable rate of the satellite system while ensuring that the inter-satellite-terrestrial interference is below a given threshold. The optimal amplitude and phase of desired beams are derived in a decoupled manner. Simulation results demonstrate the superiority of the proposed beamforming scheme.
Better Data Labelling with EMBLEM (and how that Impacts Defect Prediction)
Venue: arXiv cs.SE 2020
Year: 2020

Standard automatic methods for recognizing problematic development commits can be greatly improved via the incremental application of human+artificial expertise. In this approach, called EMBLEM, an AI tool first explore the software development process to label commits that are most problematic. Humans then apply their expertise to check those labels (perhaps resulting in the AI updating the support vectors within their SVM learner). We recommend this human+AI partnership, for several reasons. When a new domain is encountered, EMBLEM can learn better ways to label which comments refer to real problems. Also, in studies with 9 open source software projects, labelling via EMBLEM's incremental application of human+AI is at least an order of magnitude cheaper than existing methods ($\approx$ eight times). Further, EMBLEM is very effective. For the data sets explored here, EMBLEM better labelling methods significantly improved $P_{opt}20$ and G-scores performance in nearly all the projects studied here.
A Comparison of LPV Gain Scheduling and Control Contraction Metrics for Nonlinear Control
Venue: arXiv cs.SY 2020
Year: 2020

Gain-scheduled control based on linear parameter-varying (LPV) models derived from local linearizations is a widespread nonlinear technique for tracking time-varying setpoints. Recently, a nonlinear control scheme based on Control Contraction Metrics (CCMs) has been developed to track arbitrary admissible trajectories. This paper presents a comparison study of these two approaches. We show that the CCM based approach is an extended gain-scheduled control scheme which achieves global reference-independent stability and performance through an exact control realization which integrates a series of local LPV controllers on a particular path between the current and reference states.
The distortion of distributed voting
Venue: arXiv cs.GT 2020
Year: 2020

Voting can abstractly model any decision-making scenario and as such it has been extensively studied over the decades. Recently, the related literature has focused on quantifying the impact of utilizing only limited information in the voting process on the societal welfare for the outcome, by bounding the distortion of voting rules. Even though there has been significant progress towards this goal, all previous works have so far neglected the fact that in many scenarios (like presidential elections) voting is actually a distributed procedure. In this paper, we consider a setting in which the voters are partitioned into disjoint districts and vote locally therein to elect local winning alternatives using a voting rule; the final outcome is then chosen from the set of these alternatives. We prove tight bounds on the distortion of well-known voting rules for such distributed elections both from a worst-case perspective as well as from a best-case one. Our results indicate that the partition of voters into districts leads to considerably higher distortion, a phenomenon which we also experimentally showcase using real-world data.
Poly-encoders: Transformer Architectures and Pre-training Strategies for Fast and Accurate Multi-sentence Scoring
Venue: arXiv cs.CL 2020
Year: 2020

The use of deep pre-trained bidirectional transformers has led to remarkable progress in a number of applications (Devlin et al., 2018). For tasks that make pairwise comparisons between sequences, matching a given input with a corresponding label, two approaches are common: Cross-encoders performing full self-attention over the pair and Bi-encoders encoding the pair separately. The former often performs better, but is too slow for practical use. In this work, we develop a new transformer architecture, the Poly-encoder, that learns global rather than token level self-attention features. We perform a detailed comparison of all three approaches, including what pre-training and fine-tuning strategies work best. We show our models achieve state-of-the-art results on three existing tasks; that Poly-encoders are faster than Cross-encoders and more accurate than Bi-encoders; and that the best results are obtained by pre-training on large datasets similar to the downstream tasks.
Deep Learning for Sequential Recommendation: Algorithms, Influential Factors, and Evaluations
Venue: arXiv cs.IR 2020
Year: 2020

In the field of sequential recommendation, deep learning (DL)-based methods have received a lot of attention in the past few years and surpassed traditional models such as Markov chain-based and factorization-based ones. However, there is little systematic study on DL-based methods, especially regarding to how to design an effective DL model for sequential recommendation. In this view, this survey focuses on DL-based sequential recommender systems by taking the aforementioned issues into consideration. Specifically,we illustrate the concept of sequential recommendation, propose a categorization of existing algorithms in terms of three types of behavioral sequence, summarize the key factors affecting the performance of DL-based models, and conduct corresponding evaluations to demonstrate the effects of these factors. We conclude this survey by systematically outlining future directions and challenges in this field.
A Dynamic and Incentive Policy for Selecting D2D Mobile Relays
Venue: arXiv cs.IT 2020
Year: 2020

User-to-network relaying enabled via Device-to-Device communications (D2D) is a promising technique for improving the performance of cellular networks. Since in practice relays are in mobility, a dynamic relay selection scheme is unavoidable. In this paper, we propose a dynamic relay selection policy that maximizes the performance of cellular networks (e.g. throughput, reliability, coverage) under cost constraints (e.g. transmission power, power budget). We represent the relays' dynamics as a Markov Decision Process (MDP) and assume that only the locations of the selected relays are observable. Therefore, the dynamic relay selection process is modeled as a Constrained Partially Observed Markov Decision Process (CPOMDP). Since the exact solution of such framework is intractable to find, we develop a point-based value iteration solution and evaluate its performance. In addition, we prove the submodularity property of both the reward and cost value functions and deduce a greedy solution which is scalable with the number of discovered relays. For the muti-user scenario, a distributed approach is introduced in order to reduce the complexity and the overhead of the proposed solution. We illustrate the numerical results of the scenario where throughput is maximized under energy constraint and evaluate the gain that the proposed relay selection policy achieves compared to a traditional cellular network.