OpenRaiser/Intern-Atlas huggingface dataset:
A Survey on Trust Modeling from a Bayesian Perspective
Venue: arXiv cs.CR 2020
Year: 2020

In this paper, we are concerned with trust modeling for agents in networked computing systems. As trust is a subjective notion that is invisible, implicit and uncertain in nature, many attempts have been made to model trust with aid of Bayesian probability theory, while the field lacks a global comprehensive analysis for variants of Bayesian trust models. We present a study to fill in this gap by giving a comprehensive review of the literature. A generic Bayesian trust (GBT) modeling perspective is highlighted here. It is shown that all models under survey can cast into a GBT based computing paradigm as special cases. We discuss both capabilities and limitations of the GBT perspective and point out open questions to answer, with a hope to advance GBT to become a pragmatic infrastructure for analyzing intrinsic relationships among variants of trust models and developing novel tools for trust evaluation.
A Fast and Easy Regression Technique for k-NN Classification Without Using Negative Pairs
Venue: arXiv cs.LG 2020
Year: 2020

This paper proposes an inexpensive way to learn an effective dissimilarity function to be used for $k$-nearest neighbor ($k$-NN) classification. Unlike Mahalanobis metric learning methods that map both query (unlabeled) objects and labeled objects to new coordinates by a single transformation, our method learns a transformation of labeled objects to new points in the feature space whereas query objects are kept in their original coordinates. This method has several advantages over existing distance metric learning methods: (i) In experiments with large document and image datasets, it achieves $k$-NN classification accuracy better than or at least comparable to the state-of-the-art metric learning methods. (ii) The transformation can be learned efficiently by solving a standard ridge regression problem. For document and image datasets, training is often more than two orders of magnitude faster than the fastest metric learning methods tested. This speed-up is also due to the fact that the proposed method eliminates the optimization over "negative" object pairs, i.e., objects whose class labels are different. (iii) The formulation has a theoretical justification in terms of reducing hubness in data.
Aligned plane drawings of the generalized Delaunay-graphs for pseudo-disks
Venue: arXiv cs.CG 2020
Year: 2020

We study general Delaunay-graphs, which are natural generalizations of Delaunay triangulations to arbitrary families, in particular to pseudo-disks. We prove that for any finite pseudo-disk family and point set, there is a plane drawing of their Delaunay-graph such that every edge lies inside every pseudo-disk that contains its endpoints.
Delay-Free Concurrency on Faulty Persistent Memory
Venue: arXiv cs.DC 2020
Year: 2020

Non-volatile memory (NVM) promises persistent main memory that remains correct despite loss of power. This has sparked a line of research into algorithms that can recover from a system crash. Since caches are expected to remain volatile, concurrent data structures and algorithms must be redesigned to guarantee that they are left in a consistent state after a system crash, and that the execution can be continued upon recovery. However, the prospect of redesigning every concurrent data structure or algorithm before it can be used in NVM architectures is daunting. In this paper, we present a construction that takes any concurrent program with reads, writes and CASs to shared memory and makes it persistent, i.e., can be continued after one or more processes fault and have to restart. Importantly the converted algorithm has constant computational delay (preserves instruction counts on each process within a constant factor), as well as constant recovery delay (a process can recover from a fault in a constant number of instructions). We show this first for a simple transformation, and then present optimizations to make it more practical, allowing for a tradeoff for better constant factors in computational delay, for sometimes increased recovery delay. We also provide an optimized transformation that works for any normalized lock-free data structure, thus allowing more efficient constructions for a large class of concurrent algorithms. We experimentally evaluate our transformations by applying them to a queue.
Two-level preconditioning for Ridge Regression
Venue: arXiv cs.NA 2020
Year: 2020

Solving linear systems is often the computational bottleneck in real-life problems. Iterative solvers are the only option due to the complexity of direct algorithms or because the system matrix is not explicitly known. Here, we develop a two-level preconditioner for regularized least squares linear systems involving a feature or data matrix. Variants of this linear system may appear in machine learning applications, such as ridge regression, logistic regression, support vector machines and Bayesian regression. We use clustering algorithms to create a coarser level that preserves the principal components of the covariance or Gram matrix. This coarser level approximates the dominant eigenvectors and is used to build a subspace preconditioner accelerating the Conjugate Gradient method. We observed speed-ups for artificial and real-life data.
A Survey of Inverse Reinforcement Learning: Challenges, Methods and Progress
Venue: arXiv cs.LG 2020
Year: 2020

Inverse reinforcement learning (IRL) is the problem of inferring the reward function of an agent, given its policy or observed behavior. Analogous to RL, IRL is perceived both as a problem and as a class of methods. By categorically surveying the current literature in IRL, this article serves as a reference for researchers and practitioners of machine learning and beyond to understand the challenges of IRL and select the approaches best suited for the problem on hand. The survey formally introduces the IRL problem along with its central challenges such as the difficulty in performing accurate inference and its generalizability, its sensitivity to prior knowledge, and the disproportionate growth in solution complexity with problem size. The article elaborates how the current methods mitigate these challenges. We further discuss the extensions to traditional IRL methods for handling: inaccurate and incomplete perception, an incomplete model, multiple reward functions, and nonlinear reward functions. This survey concludes the discussion with some broad advances in the research area and currently open research questions.
Enclave Tasking for Discontinuous Galerkin Methods on Dynamically Adaptive Meshes
Venue: arXiv cs.MS 2020
Year: 2020

High-order Discontinuous Galerkin (DG) methods promise to be an excellent discretisation paradigm for partial differential equation solvers by combining high arithmetic intensity with localised data access. They also facilitate dynamic adaptivity without the need for conformal meshes. A parallel evaluation of DG's weak formulation within a mesh traversal is non-trivial, as dependency graphs over dynamically adaptive meshes change, as causal constraints along resolution transitions have to be preserved, and as data sends along MPI domain boundaries have to be triggered in the correct order. We propose to process mesh elements subject to constraints with high priority or, where needed, serially throughout a traversal. The remaining cells form enclaves and are spawned into a task system. This introduces concurrency, mixes memory-intensive DG integrations with compute-bound Riemann solves, and overlaps computation and communication. We discuss implications on MPI and show that MPI parallelisation improves by a factor of three through enclave tasking, while we obtain an additional factor of two from shared memory if grids are dynamically adaptive.
Design Considerations for Low Power Internet Protocols
Venue: arXiv cs.NI 2020
Year: 2020

Over the past 10 years, low-power wireless networks have transitioned to supporting IPv6 connectivity through 6LoWPAN, a set of standards which specify how to aggressively compress IPv6 packets over low-power wireless links such as 802.15.4. We find that different low-power IPv6 stacks are unable to communicate using 6LoWPAN, and therefore IP, due to design tradeoffs between code size and energy efficiency. We argue that applying traditional protocol design principles to low-power networks is responsible for these failures, in part because receivers must accommodate a wide range of senders. Based on these findings, we propose three design principles for Internet protocols on low-power networks. These principles are based around the importance of providing flexible tradeoffs between code size and energy efficiency. We apply these principles to 6LoWPAN and show that the resulting design of the protocol provides developers a wide range of tradeoff points while allowing implementations with different choices to seamlessly communicate.
Collective decision for open set recognition
Venue: arXiv cs.LG 2020
Year: 2020

In open set recognition (OSR), almost all existing methods are designed specially for recognizing individual instances, even these instances are collectively coming in batch. Recognizers in decision either reject or categorize them to some known class using empirically-set threshold. Thus the decision threshold plays a key role. However, the selection for it usually depends on the knowledge of known classes, inevitably incurring risks due to lacking available information from unknown classes. On the other hand, a more realistic OSR system should NOT just rest on a reject decision but should go further, especially for discovering the hidden unknown classes among the reject instances, whereas existing OSR methods do not pay special attention. In this paper, we introduce a novel collective/batch decision strategy with an aim to extend existing OSR for new class discovery while considering correlations among the testing instances. Specifically, a collective decision-based OSR framework (CD-OSR) is proposed by slightly modifying the Hierarchical Dirichlet process (HDP). Thanks to HDP, our CD-OSR does not need to define the decision threshold and can implement the open set recognition and new class discovery simultaneously. Finally, extensive experiments on benchmark datasets indicate the validity of CD-OSR.
A Comparative Study of Distributional and Symbolic Paradigms for Relational Learning
Venue: arXiv cs.AI 2020
Year: 2020

Many real-world domains can be expressed as graphs and, more generally, as multi-relational knowledge graphs. Though reasoning and learning with knowledge graphs has traditionally been addressed by symbolic approaches, recent methods in (deep) representation learning has shown promising results for specialized tasks such as knowledge base completion. These approaches abandon the traditional symbolic paradigm by replacing symbols with vectors in Euclidean space. With few exceptions, symbolic and distributional approaches are explored in different communities and little is known about their respective strengths and weaknesses. In this work, we compare representation learning and relational learning on various relational classification and clustering tasks and analyse the complexity of the rules used implicitly by these approaches. Preliminary results reveal possible indicators that could help in choosing one approach over the other for particular knowledge graphs.
Confidential Inference via Ternary Model Partitioning
Venue: arXiv cs.CR 2020
Year: 2020

Today's cloud vendors are competing to provide various offerings to simplify and accelerate AI service deployment. However, cloud users always have concerns about the confidentiality of their runtime data, which are supposed to be processed on third-party's compute infrastructures. Information disclosure of user-supplied data may jeopardize users' privacy and breach increasingly stringent data protection regulations. In this paper, we systematically investigate the life cycles of inference inputs in deep learning image classification pipelines and understand how the information could be leaked. Based on the discovered insights, we develop a Ternary Model Partitioning mechanism and bring trusted execution environments to mitigate the identified information leakages. Our research prototype consists of two co-operative components: (1) Model Assessment Framework, a local model evaluation and partitioning tool that assists cloud users in deployment preparation; (2) Infenclave, an enclave-based model serving system for online confidential inference in the cloud. We have conducted comprehensive security and performance evaluation on three representative ImageNet-level deep learning models with different network depths and architectural complexity. Our results demonstrate the feasibility of launching confidential inference services in the cloud with maximized confidentiality guarantees and low performance costs.
Reverse Prevention Sampling for Misinformation Mitigation in Social Networks
Venue: arXiv cs.SI 2020
Year: 2020

In this work, we consider misinformation propagating through a social network and study the problem of its prevention. In this problem, a "bad" campaign starts propagating from a set of seed nodes in the network and we use the notion of a limiting (or "good") campaign to counteract the effect of misinformation. The goal is to identify a set of $k$ users that need to be convinced to adopt the limiting campaign so as to minimize the number of people that adopt the "bad" campaign at the end of both propagation processes. This work presents \emph{RPS} (Reverse Prevention Sampling), an algorithm that provides a scalable solution to the misinformation mitigation problem. Our theoretical analysis shows that \emph{RPS} runs in $O((k + l)(n + m)(\frac{1}{1 - γ}) \log n / ε^2 )$ expected time and returns a $(1 - 1/e - ε)$-approximate solution with at least $1 - n^{-l}$ probability (where $γ$ is a typically small network parameter and $l$ is a confidence parameter). The time complexity of \emph{RPS} substantially improves upon the previously best-known algorithms that run in time $Ω(m n k \cdot POLY(ε^{-1}))$. We experimentally evaluate \emph{RPS} on large datasets and show that it outperforms the state-of-the-art solution by several orders of magnitude in terms of running time. This demonstrates that misinformation mitigation can be made practical while still offering strong theoretical guarantees.
RNNIDS: Enhancing Network Intrusion Detection Systems through Deep Learning
Venue: arXiv cs.CR 2020
Year: 2020

Security of information passing through the Internet is threatened by today's most advanced malware ranging from orchestrated botnets to simpler polymorphic worms. These threats, as examples of zero-day attacks, are able to change their behavior several times in the early phases of their existence to bypass the network intrusion detection systems (NIDS). In fact, even well-designed, and frequently-updated signature-based NIDS cannot detect the zero-day treats due to the lack of an adequate signature database, adaptive to intelligent attacks on the Internet. More importantly, having an NIDS, it should be tested on malicious traffic dataset that not only represents known attacks, but also can to some extent reflect the characteristics of unknown, zero-day attacks. Generating such traffic is identified in the literature as one of the main obstacles for evaluating the effectiveness of NIDS. To address these issues, we introduce RNNIDS that applies Recurrent Neural Networks (RNNs) to find complex patterns in attacks and generate similar ones. In this regard, for the first time, we demonstrate that RNNs are helpful to generate new, unseen mutants of attacks as well as synthetic signatures from the most advanced malware to improve the intrusion detection rate. Besides, to further enhance the design of an NIDS, RNNs can be employed to generate malicious datasets containing, e.g., unseen mutants of a malware. To evaluate the feasibility of our approaches, we conduct extensive experiments by incorporating publicly available datasets, where we show a considerable improvement in the detection rate of an off-the-shelf NIDS (up to 16.67%).
Adaptive Adversarial Attack on Scene Text Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Recent studies have shown that state-of-the-art deep learning models are vulnerable to the inputs with small perturbations (adversarial examples). We observe two critical obstacles in adversarial examples: (i) Strong adversarial attacks (e.g., C&W attack) require manually tuning hyper-parameters and take a long time to construct an adversarial example, making it impractical to attack real-time systems; (ii) Most of the studies focus on non-sequential tasks, such as image classification, yet only a few consider sequential tasks. In this work, we speed up adversarial attacks, especially on sequential learning tasks. By leveraging the uncertainty of each task, we directly learn the adaptive multi-task weightings, without manually searching hyper-parameters. A unified architecture is developed and evaluated for both non-sequential tasks and sequential ones. To validate the effectiveness, we take the scene text recognition task as a case study. To our best knowledge, our proposed method is the first attempt to adversarial attack for scene text recognition. Adaptive Attack achieves over 99.9\% success rate with 3-6X speedup compared to state-of-the-art adversarial attacks.
Handling Incomplete Heterogeneous Data using VAEs
Venue: arXiv cs.LG 2020
Year: 2020

Variational autoencoders (VAEs), as well as other generative models, have been shown to be efficient and accurate for capturing the latent structure of vast amounts of complex high-dimensional data. However, existing VAEs can still not directly handle data that are heterogenous (mixed continuous and discrete) or incomplete (with missing data at random), which is indeed common in real-world applications. In this paper, we propose a general framework to design VAEs suitable for fitting incomplete heterogenous data. The proposed HI-VAE includes likelihood models for real-valued, positive real valued, interval, categorical, ordinal and count data, and allows accurate estimation (and potentially imputation) of missing data. Furthermore, HI-VAE presents competitive predictive performance in supervised tasks, outperforming supervised models when trained on incomplete data.
On Catastrophic Forgetting and Mode Collapse in Generative Adversarial Networks
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we show that Generative Adversarial Networks (GANs) suffer from catastrophic forgetting even when they are trained to approximate a single target distribution. We show that GAN training is a continual learning problem in which the sequence of changing model distributions is the sequence of tasks to the discriminator. The level of mismatch between tasks in the sequence determines the level of forgetting. Catastrophic forgetting is interrelated to mode collapse and can make the training of GANs non-convergent. We investigate the landscape of the discriminator's output in different variants of GANs and find that when a GAN converges to a good equilibrium, real training datapoints are wide local maxima of the discriminator. We empirically show the relationship between the sharpness of local maxima and mode collapse and generalization in GANs. We show how catastrophic forgetting prevents the discriminator from making real datapoints local maxima, and thus causes non-convergence. Finally, we study methods for preventing catastrophic forgetting in GANs.
Metrical task systems on trees via mirror descent and unfair gluing
Venue: arXiv cs.DS 2020
Year: 2020

We consider metrical task systems on tree metrics, and present an $O(\mathrm{depth} \times \log n)$-competitive randomized algorithm based on the mirror descent framework introduced in our prior work on the $k$-server problem. For the special case of hierarchically separated trees (HSTs), we use mirror descent to refine the standard approach based on gluing unfair metrical task systems. This yields an $O(\log n)$-competitive algorithm for HSTs, thus removing an extraneous $\log\log n$ in the bound of Fiat and Mendel (2003). Combined with well-known HST embedding theorems, this also gives an $O((\log n)^2)$-competitive randomized algorithm for every $n$-point metric space.
A Dataset of Laryngeal Endoscopic Images with Comparative Study on Convolution Neural Network Based Semantic Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

Purpose Automated segmentation of anatomical structures in medical image analysis is a prerequisite for autonomous diagnosis as well as various computer and robot aided interventions. Recent methods based on deep convolutional neural networks (CNN) have outperformed former heuristic methods. However, those methods were primarily evaluated on rigid, real-world environments. In this study, existing segmentation methods were evaluated for their use on a new dataset of transoral endoscopic exploration. Methods Four machine learning based methods SegNet, UNet, ENet and ErfNet were trained with supervision on a novel 7-class dataset of the human larynx. The dataset contains 536 manually segmented images from two patients during laser incisions. The Intersection-over-Union (IoU) evaluation metric was used to measure the accuracy of each method. Data augmentation and network ensembling were employed to increase segmentation accuracy. Stochastic inference was used to show uncertainties of the individual models. Patient-to-patient transfer was investigated using patient-specific fine-tuning. Results In this study, a weighted average ensemble network of UNet and ErfNet was best suited for the segmentation of laryngeal soft tissue with a mean IoU of 84.7 %. The highest efficiency was achieved by ENet with a mean inference time of 9.22 ms per image. It is shown that 10 additional images from a new patient are sufficient for patient-specific fine-tuning. Conclusion CNN-based methods for semantic segmentation are applicable to endoscopic images of laryngeal soft tissue. The segmentation can be used for active constraints or to monitor morphological changes and autonomously detect pathologies. Further improvements could be achieved by using a larger dataset or training the models in a self-supervised manner on additional unlabeled data.
Formal verification of higher-order probabilistic programs
Venue: arXiv cs.LO 2020
Year: 2020

Probabilistic programming provides a convenient lingua franca for writing succinct and rigorous descriptions of probabilistic models and inference tasks. Several probabilistic programming languages, including Anglican, Church or Hakaru, derive their expressiveness from a powerful combination of continuous distributions, conditioning, and higher-order functions. Although very important for practical applications, these combined features raise fundamental challenges for program semantics and verification. Several recent works offer promising answers to these challenges, but their primary focus is on semantical issues. In this paper, we take a step further and we develop a set of program logics, named PPV, for proving properties of programs written in an expressive probabilistic higher-order language with continuous distributions and operators for conditioning distributions by real-valued functions. Pleasingly, our program logics retain the comfortable reasoning style of informal proofs thanks to carefully selected axiomatizations of key results from probability theory. The versatility of our logics is illustrated through the formal verification of several intricate examples from statistics, probabilistic inference, and machine learning. We further show the expressiveness of our logics by giving sound embeddings of existing logics. In particular, we do this in a parametric way by showing how the semantics idea of (unary and relational) TT-lifting can be internalized in our logics. The soundness of PPV follows by interpreting programs and assertions in quasi-Borel spaces (QBS), a recently proposed variant of Borel spaces with a good structure for interpreting higher order probabilistic programs.