OpenRaiser/Intern-Atlas huggingface dataset:
Uncertainty based Class Activation Maps for Visual Question Answering
Venue: arXiv cs.CV 2020
Year: 2020

Understanding and explaining deep learning models is an imperative task. Towards this, we propose a method that obtains gradient-based certainty estimates that also provide visual attention maps. Particularly, we solve for visual question answering task. We incorporate modern probabilistic deep learning methods that we further improve by using the gradients for these estimates. These have two-fold benefits: a) improvement in obtaining the certainty estimates that correlate better with misclassified samples and b) improved attention maps that provide state-of-the-art results in terms of correlation with human attention regions. The improved attention maps result in consistent improvement for various methods for visual question answering. Therefore, the proposed technique can be thought of as a recipe for obtaining improved certainty estimates and explanations for deep learning models. We provide detailed empirical analysis for the visual question answering task on all standard benchmarks and comparison with state of the art methods.
Spatial-Temporal Moving Target Defense: A Markov Stackelberg Game Model
Venue: arXiv cs.GT 2020
Year: 2020

Moving target defense has emerged as a critical paradigm of protecting a vulnerable system against persistent and stealthy attacks. To protect a system, a defender proactively changes the system configurations to limit the exposure of security vulnerabilities to potential attackers. In doing so, the defender creates asymmetric uncertainty and complexity for the attackers, making it much harder for them to compromise the system. In practice, the defender incurs a switching cost for each migration of the system configurations. The switching cost usually depends on both the current configuration and the following configuration. Besides, different system configurations typically require a different amount of time for an attacker to exploit and attack. Therefore, a defender must simultaneously decide both the optimal sequences of system configurations and the optimal timing for switching. In this paper, we propose a Markov Stackelberg Game framework to precisely characterize the defender's spatial and temporal decision-making in the face of advanced attackers. We introduce a relative value iteration algorithm that computes the defender's optimal moving target defense strategies. Empirical evaluation on real-world problems demonstrates the advantages of the Markov Stackelberg game model for spatial-temporal moving target defense.
Boosting rare benthic macroinvertebrates taxa identification with one-class classification
Venue: arXiv cs.CV 2020
Year: 2020

Insect monitoring is crucial for understanding the consequences of rapid ecological changes, but taxa identification currently requires tedious manual expert work and cannot be scaled-up efficiently. Deep convolutional neural networks (CNNs), provide a viable way to significantly increase the biomonitoring volumes. However, taxa abundances are typically very imbalanced and the amounts of training images for the rarest classes are simply too low for deep CNNs. As a result, the samples from the rare classes are often completely missed, while detecting them has biological importance. In this paper, we propose combining the trained deep CNN with one-class classifiers to improve the rare species identification. One-class classification models are traditionally trained with much fewer samples and they can provide a mechanism to indicate samples potentially belonging to the rare classes for human inspection. Our experiments confirm that the proposed approach may indeed support moving towards partial automation of the taxa identification task.
Deep Nearest Neighbor Anomaly Detection
Venue: arXiv cs.LG 2020
Year: 2020

Nearest neighbors is a successful and long-standing technique for anomaly detection. Significant progress has been recently achieved by self-supervised deep methods (e.g. RotNet). Self-supervised features however typically under-perform Imagenet pre-trained features. In this work, we investigate whether the recent progress can indeed outperform nearest-neighbor methods operating on an Imagenet pretrained feature space. The simple nearest-neighbor based-approach is experimentally shown to outperform self-supervised methods in: accuracy, few shot generalization, training time and noise robustness while making fewer assumptions on image distributions.
Optimisation of Body-ground Contact for Augmenting Whole-Body Loco-manipulation of Quadruped Robots
Venue: arXiv cs.RO 2020
Year: 2020

Legged robots have great potential to perform loco-manipulation tasks, yet it is challenging to keep the robot balanced while it interacts with the environment. In this paper we study the use of additional contact points for maximising the robustness of loco-manipulation motions. Specifically, body-ground contact is studied for enhancing robustness and manipulation capabilities of quadrupedal robots. We propose to equip the robot with prongs: small legs rigidly attached to the body which ensure body-ground contact occurs in controllable point-contacts. The effect of these prongs on robustness is quantified by computing the Smallest Unrejectable Force (SUF), a measure of robustness related to Feasible Wrench Polytopes. We apply the SUF to assess the robustness of the system, and propose an effective approximation of the SUF that can be computed at near-real-time speed. We design a hierarchical quadratic programming based whole-body controller that controls stable interaction when the prongs are in contact with the ground. This novel concept of using prongs and the resulting control framework are all implemented on hardware to validate the effectiveness of the increased robustness and newly enabled loco-manipulation tasks, such as obstacle clearance and manipulation of a large object.
Three Approaches for Personalization with Applications to Federated Learning
Venue: arXiv cs.LG 2020
Year: 2020

The standard objective in machine learning is to train a single model for all users. However, in many learning scenarios, such as cloud computing and federated learning, it is possible to learn a personalized model per user. In this work, we present a systematic learning-theoretic study of personalization. We propose and analyze three approaches: user clustering, data interpolation, and model interpolation. For all three approaches, we provide learning-theoretic guarantees and efficient algorithms for which we also demonstrate the performance empirically. All of our algorithms are model-agnostic and work for any hypothesis class.
The Power of Many Samples in Query Complexity
Venue: arXiv cs.CC 2020
Year: 2020

The randomized query complexity $R(f)$ of a boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution $D_0$ over $0$-inputs from a distribution $D_1$ over $1$-inputs, maximized over all pairs $(D_0,D_1)$. We ask: Does this task become easier if we allow query access to infinitely many samples from either $D_0$ or $D_1$? We show the answer is no: There exists a hard pair $(D_0,D_1)$ such that distinguishing $D_0^\infty$ from $D_1^\infty$ requires $Θ(R(f))$ many queries. As an application, we show that for any composed function $f\circ g$ we have $R(f\circ g) \geq Ω(\mathrm{fbs}(f)R(g))$ where $\mathrm{fbs}$ denotes fractional block sensitivity.
Fair and Truthful Mechanisms for Dichotomous Valuations
Venue: arXiv cs.GT 2020
Year: 2020

We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations. To gauge the robustness of our positive results, we also study $ε$-dichotomous valuations, in which the added value of any item to a set is either non-positive, or in the range $[1, 1 + ε]$. We show several impossibility results in this setting, and also a positive result: for players that have additive $ε$-dichotomous valuations with sufficiently small $ε$, we design a randomized truthful mechanism with strong ex-post guarantees. For $ρ= \frac{1}{1 + ε}$, the allocations that it produces generate at least a $ρ$-fraction of the maximum welfare, and enjoy $ρ$-approximations for various fairness properties, such as being envy-free up to one item (EF1), and giving each player at least her maximin share.
LoRa beyond ALOHA: An Investigation of Alternative Random Access Protocols
Venue: arXiv cs.IT 2020
Year: 2020

We present a stochastic geometry-based model to investigate alternative medium access choices for LoRaWAN---a widely adopted low-power wide-area networking (LPWAN) technology for the Internet-of-things (IoT). LoRaWAN adoption is driven by its simplified network architecture, air interface, and medium access. The physical layer, known as LoRa, provides quasi-orthogonal virtual channels through spreading factors (SFs) and time-power capture gains. However, the adopted pure ALOHA access mechanism suffers, in terms of scalability, under the same-channel same-SF transmissions from a large number of devices. In this paper, our objective is to explore access mechanisms beyond-ALOHA for LoRaWAN. Using recent results on time- and power-capture effects of LoRa, we develop a unified model for the comparative study of other choices, i.e., slotted ALOHA and carrier-sense multiple access (CSMA). The model includes the necessary design parameters of these access mechanisms, such as guard time and synchronization accuracy for slotted ALOHA, carrier sensing threshold for CSMA. It also accounts for the spatial interaction of devices in annular-shaped regions, characteristic of LoRa, for CSMA. The performance derived from the model in terms of coverage probability, channel throughput, and energy efficiency are validated using Monte-Carlo simulations. Our analysis shows that slotted ALOHA indeed has higher reliability than pure ALOHA but at the cost of lower energy efficiency for low device densities. Whereas, CSMA outperforms slotted ALOHA at smaller SFs in terms of reliability and energy efficiency, with its performance degrading to pure ALOHA at higher SFs.
Binary-level Directed Fuzzing for Use-After-Free Vulnerabilities
Venue: arXiv cs.CR 2020
Year: 2020

Directed fuzzing focuses on automatically testing specific parts of the code by taking advantage of additional information such as (partial) bug stack trace, patches or risky operations. Key applications include bug reproduction, patch testing and static analysis report verification. Although directed fuzzing has received a lot of attention recently, hard-to-detect vulnerabilities such as Use-After-Free (UAF) are still not well addressed, especially at the binary level. We propose UAFuzz, the first (binary-level) directed greybox fuzzer dedicated to UAF bugs. The technique features a fuzzing engine tailored to UAF specifics, a lightweight code instrumentation and an efficient bug triage step. Experimental evaluation for bug reproduction on real cases demonstrates that UAFuzz significantly outperforms state-of-the-art directed fuzzers in terms of fault detection rate, time to exposure and bug triaging. UAFuzz has also been proven effective in patch testing, leading to the discovery of 30 new bugs (7 CVEs) in programs such as Perl, GPAC and GNU Patch. Finally, we provide to the community a large fuzzing benchmark dedicated to UAF, built on both real codes and real bugs.
Network-Density-Controlled Decentralized Parallel Stochastic Gradient Descent in Wireless Systems
Venue: arXiv cs.NI 2020
Year: 2020

This paper proposes a communication strategy for decentralized learning on wireless systems. Our discussion is based on the decentralized parallel stochastic gradient descent (D-PSGD), which is one of the state-of-the-art algorithms for decentralized learning. The main contribution of this paper is to raise a novel open question for decentralized learning on wireless systems: there is a possibility that the density of a network topology significantly influences the runtime performance of D-PSGD. In general, it is difficult to guarantee delay-free communications without any communication deterioration in real wireless network systems because of path loss and multi-path fading. These factors significantly degrade the runtime performance of D-PSGD. To alleviate such problems, we first analyze the runtime performance of D-PSGD by considering real wireless systems. This analysis yields the key insights that dense network topology (1) does not significantly gain the training accuracy of D-PSGD compared to sparse one, and (2) strongly degrades the runtime performance because this setting generally requires to utilize a low-rate transmission. Based on these findings, we propose a novel communication strategy, in which each node estimates optimal transmission rates such that communication time during the D-PSGD optimization is minimized under the constraint of network density, which is characterized by radio propagation property. The proposed strategy enables to improve the runtime performance of D-PSGD in wireless systems. Numerical simulations reveal that the proposed strategy is capable of enhancing the runtime performance of D-PSGD.
Sequence-to-Sequence Imputation of Missing Sensor Data
Venue: arXiv cs.LG 2020
Year: 2020

Although the sequence-to-sequence (encoder-decoder) model is considered the state-of-the-art in deep learning sequence models, there is little research into using this model for recovering missing sensor data. The key challenge is that the missing sensor data problem typically comprises three sequences (a sequence of observed samples, followed by a sequence of missing samples, followed by another sequence of observed samples) whereas, the sequence-to-sequence model only considers two sequences (an input sequence and an output sequence). We address this problem by formulating a sequence-to-sequence in a novel way. A forward RNN encodes the data observed before the missing sequence and a backward RNN encodes the data observed after the missing sequence. A decoder decodes the two encoders in a novel way to predict the missing data. We demonstrate that this model produces the lowest errors in 12% more cases than the current state-of-the-art.
Label-guided Learning for Text Classification
Venue: arXiv cs.CL 2020
Year: 2020

Text classification is one of the most important and fundamental tasks in natural language processing. Performance of this task mainly dependents on text representation learning. Currently, most existing learning frameworks mainly focus on encoding local contextual information between words. These methods always neglect to exploit global clues, such as label information, for encoding text information. In this study, we propose a label-guided learning framework LguidedLearn for text representation and classification. Our method is novel but simple that we only insert a label-guided encoding layer into the commonly used text representation learning schemas. That label-guided layer performs label-based attentive encoding to map the universal text embedding (encoded by a contextual information learner) into different label spaces, resulting in label-wise embeddings. In our proposed framework, the label-guided layer can be easily and directly applied with a contextual encoding method to perform jointly learning. Text information is encoded based on both the local contextual information and the global label clues. Therefore, the obtained text embeddings are more robust and discriminative for text classification. Extensive experiments are conducted on benchmark datasets to illustrate the effectiveness of our proposed method.
Comparison Study for Multi-vendor Versus Single-vendor for Enterprise Computer Networks
Venue: arXiv cs.NI 2020
Year: 2020

One of the topics that concerns the way computer networks are designed, is the single-vendor and multi-vendor solutions. Where the performance and operation of your network depends on which model you choose for your enterprise, and the future risks aligned with such models. This study outlines the strengths and average price ranges of multiple vendors in the past 2 years (2018 and 2019), practical cases in which each model works, a case study done by Gartner, and finally, recommendations that can help push the design practices when it comes to network design.
Abstractive Snippet Generation
Venue: arXiv cs.IR 2020
Year: 2020

An abstractive snippet is an originally created piece of text to summarize a web page on a search engine results page. Compared to the conventional extractive snippets, which are generated by extracting phrases and sentences verbatim from a web page, abstractive snippets circumvent copyright issues; even more interesting is the fact that they open the door for personalization. Abstractive snippets have been evaluated as equally powerful in terms of user acceptance and expressiveness---but the key question remains: Can abstractive snippets be automatically generated with sufficient quality? This paper introduces a new approach to abstractive snippet generation: We identify the first two large-scale sources for distant supervision, namely anchor contexts and web directories. By mining the entire ClueWeb09 and ClueWeb12 for anchor contexts and by utilizing the DMOZ Open Directory Project, we compile the Webis Abstractive Snippet Corpus 2020, comprising more than 3.5 million triples of the form $\langle$query, snippet, document$\rangle$ as training examples, where the snippet is either an anchor context or a web directory description in lieu of a genuine query-biased abstractive snippet of the web document. We propose a bidirectional abstractive snippet generation model and assess the quality of both our corpus and the generated abstractive snippets with standard measures, crowdsourcing, and in comparison to the state of the art. The evaluation shows that our novel data sources along with the proposed model allow for producing usable query-biased abstractive snippets while minimizing text reuse.
Near Optimal Task Graph Scheduling with Priced Timed Automata and Priced Timed Markov Decision Processes
Venue: arXiv cs.DC 2020
Year: 2020

Task graph scheduling is a relevant problem in computer science with application to diverse real world domains. Task graph scheduling suffers from a combinatorial explosion and thus finding optimal schedulers is a difficult task. In this paper we present a methodology for computing near-optimal preemptive and non-preemptive schedulers for task graphs. The task graph scheduling problem is reduced to location reachability via the fastest path in Priced Timed Automata (PTA) and Priced Timed Markov Decision Processes (PTMDP). Additionally, we explore the effect of using chains to reduce the computation time for finding schedules. We have implemented our models in UPPAAL CORA and UPPAAL STRATEGO. We conduct an exhaustive experimental evaluation where we compare our resulting schedules with the best-known schedules of a state of the art tool. A significant number of our resulting schedules are shown to be shorter than or equal to the best-known schedules.
Learning Queuing Networks by Recurrent Neural Networks
Venue: arXiv cs.PF 2020
Year: 2020

It is well known that building analytical performance models in practice is difficult because it requires a considerable degree of proficiency in the underlying mathematics. In this paper, we propose a machine-learning approach to derive performance models from data. We focus on queuing networks, and crucially exploit a deterministic approximation of their average dynamics in terms of a compact system of ordinary differential equations. We encode these equations into a recurrent neural network whose weights can be directly related to model parameters. This allows for an interpretable structure of the neural network, which can be trained from system measurements to yield a white-box parameterized model that can be used for prediction purposes such as what-if analyses and capacity planning. Using synthetic models as well as a real case study of a load-balancing system, we show the effectiveness of our technique in yielding models with high predictive power.
An Assignment Problem Formulation for Dominance Move Indicator
Venue: arXiv cs.NE 2020
Year: 2020

Dominance move (DoM) is a binary quality indicator to compare solution sets in multiobjective optimization. The indicator allows a more natural and intuitive relation when comparing solution sets. It is Pareto compliant and does not demand any parameters or reference sets. In spite of its advantages, the combinatorial calculation nature is a limitation. The original formulation presents an efficient method to calculate it in a biobjective case only. This work presents an assignment formulation to calculate DoM in problems with three objectives or more. Some initial experiments, in the biobjective space, were done to present the model correctness. Next, other experiments, using three dimensions, were also done to show how DoM could be compared with other indicators: inverted generational distance (IGD) and hypervolume (HV). Results show the assignment formulation for DoM is valid for more than three objectives. However, there are some strengths and weaknesses, which are discussed and detailed. Some notes, considerations, and future research paths conclude this work.
Security Wrappers for Information-Flow Control in Active Object Languages with Futures
Venue: arXiv cs.PL 2020
Year: 2020

This paper introduces a run-time mechanism for preventing leakage of secure information in distributed systems. We consider a general concurrency language model, where concurrent objects interact by asynchronous method calls and futures. The aim is to prevent leakage of confidential information to low-level viewers. The approach is based on the notion of a security wrapper, which encloses an object or a component and controls its interactions with the environment. A wrapper is a mechanism added by the run-time system to provide protection of an insecure component according to some security policies. The security policies of a wrapper are formalized based on a notion of security levels. At run-time, future components will be wrapped upon need, while only objects of unsafe classes will be wrapped, using static checking to limit the number of unsafe classes and thereby reducing run-time overhead. We define an operational semantics and prove that non-interference is satisfied. A service provider may use wrappers to protect its services in an insecure environment, and vice-versa: a system platform may use wrappers to protect itself from insecure service providers.
Integer Plane Multiflow Maximisation : Flow-Cut Gap and One-Quarter-Approximation
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one of value at least half of the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing again at most half of the value, in polynomial time, achieving a $1/4$-approximation algorithm for maximum integer multiflows in the plane, and an integer-flow-cut gap of $8$.