OpenRaiser/Intern-Atlas huggingface dataset:
Using Skip Graphs for Increased NUMA Locality
Venue: arXiv cs.DC 2020
Year: 2020

We present a data partitioning technique performed over skip graphs that promotes significant quantitative and qualitative improvements on NUMA locality in concurrent data structures, as well as reduced contention. We build on previous techniques of thread-local indexing and laziness, and, at a high level, our design consists of a partitioned skip graph, well-integrated with thread-local sequential maps, operating without contention. As a proof-of-concept, we implemented map and relaxed priority queue ADTs using our technique. Maps were conceived using lazy and non-lazy approaches to insertions and removals, and our implementations are shown to be competitive with state-of-the-art maps. We observe a 6x higher CAS locality, a 68.6% reduction on the number of remote CAS operations, and a increase from 88.3% to 99% CAS success rate when using a lazy skip graph as compared to a control skip list (subject to the same codebase, optimizations, and implementation practices). Qualitatively speaking, remote memory accesses are not only reduced in number, but the larger the NUMA distance between threads, the larger the reduction is. We consider two alternative implementations of relaxed priority queues that further take advantage of our data partitioning over skip graphs: (a) using ``spraying'', a well-known random-walk technique usually performed over skip lists, but now performed over skip graphs; and (b) a custom protocol that traverses the skip graph deterministically, marking elements along this traversal. We provide formal arguments indicating that the first approach is more \emph{relaxed}, that is, that the span of removed keys is larger, while the second approach has smaller contention. Experimental results indicate that the approach based on spraying performs better on skip graphs, yet both seem to scale appropriately.
DEDPUL: Difference-of-Estimated-Densities-based Positive-Unlabeled Learning
Venue: arXiv cs.LG 2020
Year: 2020

Positive-Unlabeled (PU) learning is an analog to supervised binary classification for the case when only the positive sample is clean, while the negative sample is contaminated with latent instances of positive class and hence can be considered as an unlabeled mixture. The objectives are to classify the unlabeled sample and train an unbiased PN classifier, which generally requires to identify the mixing proportions of positives and negatives first. Recently, unbiased risk estimation framework has achieved state-of-the-art performance in PU learning. This approach, however, exhibits two major bottlenecks. First, the mixing proportions are assumed to be identified, i.e. known in the domain or estimated with additional methods. Second, the approach relies on the classifier being a neural network. In this paper, we propose DEDPUL, a method that solves PU Learning without the aforementioned issues. The mechanism behind DEDPUL is to apply a computationally cheap post-processing procedure to the predictions of any classifier trained to distinguish positive and unlabeled data. Instead of assuming the proportions to be identified, DEDPUL estimates them alongside with classifying unlabeled sample. Experiments show that DEDPUL outperforms the current state-of-the-art in both proportion estimation and PU Classification.
Taking-and-merging games as rewrite games
Venue: arXiv cs.FL 2020
Year: 2020

This work is a contribution to the study of rewrite games. Positions are finite words, and the possible moves are defined by a finite number of local rewriting rules. We introduce and investigate taking-and-merging games, that is, where each rule is of the form a^k->epsilon. We give sufficient conditions for a game to be such that the losing positions (resp. the positions with a given Grundy value) form a regular language or a context-free language. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games. Finally we show that more general rewrite games quickly lead to undecidable problems. Namely, it is undecidable whether there exists a winning position in a given regular language, even if we restrict to games where each move strictly reduces the length of the current position. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games.
A Walk-based Model on Entity Graphs for Relation Extraction
Venue: arXiv cs.CL 2020
Year: 2020

We present a novel graph-based neural network model for relation extraction. Our model treats multiple pairs in a sentence simultaneously and considers interactions among them. All the entities in a sentence are placed as nodes in a fully-connected graph structure. The edges are represented with position-aware contexts around the entity pairs. In order to consider different relation paths between two entities, we construct up to l-length walks between each pair. The resulting walks are merged and iteratively used to update the edge representations into longer walks representations. We show that the model achieves performance comparable to the state-of-the-art systems on the ACE 2005 dataset without using any external tools.
Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols
Venue: arXiv cs.DC 2020
Year: 2020

Gossip protocols are widely used to disseminate information in massive peer-to-peer networks. These protocols are often claimed to guarantee privacy because of the uncertainty they introduce on the node that started the dissemination. But is that claim really true? Can the source of a gossip safely hide in the crowd? This paper examines, for the first time, gossip protocols through a rigorous mathematical framework based on differential privacy to determine the extent to which the source of a gossip can be traceable. Considering the case of a complete graph in which a subset of the nodes are curious, we study a family of gossip protocols parameterized by a ``muting'' parameter $s$: nodes stop emitting after each communication with a fixed probability $1-s$. We first prove that the standard push protocol, corresponding to the case $s=1$, does not satisfy differential privacy for large graphs. In contrast, the protocol with $s=0$ achieves optimal privacy guarantees but at the cost of a drastic increase in the spreading time compared to standard push, revealing an interesting tension between privacy and spreading time. Yet, surprisingly, we show that some choices of the muting parameter $s$ lead to protocols that achieve an optimal order of magnitude in both privacy and speed. We also confirm empirically that, with appropriate choices of $s$, we indeed obtain protocols that are very robust against concrete source location attacks while spreading the information almost as fast as the standard (and non-private) push protocol.
Algebraic aspects of solving Ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm
Venue: arXiv cs.CR 2020
Year: 2020

We provide a reduction of the Ring-LWE problem to Ring-LWE problems in subrings, in the presence of samples of a restricted form (i.e. $(a,b)$ such that $a$ is restricted to a multiplicative coset of the subring). To create and exploit such restricted samples, we propose Ring-BKW, a version of the Blum-Kalai-Wasserman algorithm which respects the ring structure. Off-the-shelf BKW dimension reduction (including coded-BKW and sieving) can be used for the reduction phase. Its primary advantage is that there is no need for back-substitution, and the solving/hypothesis-testing phase can be parallelized. We also present a method to exploit symmetry to reduce table sizes, samples needed, and runtime during the reduction phase. The results apply to two-power cyclotomic Ring-LWE with parameters proposed for practical use (including all splitting types).
Personalized On-line Adaptation of Kinematic Synergies for Human-Prosthesis Interfaces
Venue: arXiv cs.RO 2020
Year: 2020

Synergies have been adopted in prosthetic limb applications to reduce complexity of design, but typically involve a single synergy setting for a population and ignore individual preference or adaptation capacity. However, personalization of the synergy setting is necessary for the effective operation of the prosthetic device. Two major challenges hinder the personalization of synergies in human-prosthesis interfaces. The first is related to the process of human motor adaptation and the second to the variation in motor learning dynamics of individuals. In this paper, a systematic personalization of kinematic synergies for human-prosthesis interfaces using on-line measurements from each individual is proposed. The task of reaching using the upper-limb is described by an objective function and the interface is parameterized by a kinematic synergy. Consequently, personalizing the interface for a given individual can be formulated as finding an optimal personalized parameter. A structure to model the observed motor behavior that allows for the personalized traits of motor preference and motor learning is proposed, and subsequently used in an on-line optimization scheme to identify the synergies for an individual. The knowledge of the common features contained in the model enables on-line adaptation of the human-prosthesis interface to happen concurrently to human motor adaptation without the need to re-tune the personalization algorithm for each individual. Human-in-the-loop experimental results with able-bodied subjects, performed in a virtual reality environment to emulate amputation and prosthesis use, show that the proposed personalization algorithm was effective in obtaining optimal synergies with a fast uniform convergence speed across a group of individuals.
A Joint Deep Learning Approach for Automated Liver and Tumor Segmentation
Venue: arXiv cs.CV 2020
Year: 2020

Hepatocellular carcinoma (HCC) is the most common type of primary liver cancer in adults, and the most common cause of death of people suffering from cirrhosis. The segmentation of liver lesions in CT images allows assessment of tumor load, treatment planning, prognosis and monitoring of treatment response. Manual segmentation is a very time-consuming task and in many cases, prone to inaccuracies and automatic tools for tumor detection and segmentation are desirable. In this paper, we compare two network architectures, one that is composed of one neural network and manages the segmentation task in one step and one that consists of two consecutive fully convolutional neural networks. The first network segments the liver whereas the second network segments the actual tumor inside the liver. Our networks are trained on a subset of the LiTS (Liver Tumor Segmentation) Challenge and evaluated on data.
Multiple-image encryption and hiding with an optical diffractive neural network
Venue: arXiv cs.CV 2020
Year: 2020

A cascaded phase-only mask architecture (or an optical diffractive neural network) can be employed for different optical information processing tasks such as pattern recognition, orbital angular momentum (OAM) mode conversion, image salience detection and image encryption. However, for optical encryption and watermarking applications, such a system usually cannot process multiple pairs of input images and output images simultaneously. In our proposed scheme, multiple input images can be simultaneously fed to an optical diffractive neural network (DNN) system and each corresponding output image will be displayed in a non-overlap sub-region in the output imaging plane. Each input image undergoes a different optical transform in an independent channel within the same system. The multiple cascaded phase masks in the system can be effectively optimized by a wavefront matching algorithm. Similar to recent optical pattern recognition and mode conversion works, the orthogonality property is employed to design a multiplexed DNN.
Efficient Private Algorithms for Learning Large-Margin Halfspaces
Venue: arXiv cs.LG 2020
Year: 2020

We present new differentially private algorithms for learning a large-margin halfspace. In contrast to previous algorithms, which are based on either differentially private simulations of the statistical query model or on private convex optimization, the sample complexity of our algorithms depends only on the margin of the data, and not on the dimension. We complement our results with a lower bound, showing that the dependence of our upper bounds on the margin is optimal.
CityJSON: a compact and easy-to-use encoding of the CityGML data model
Venue: arXiv cs.DB 2020
Year: 2020

The international standard CityGML is both a data model and an exchange format to store digital 3D models of cities. While the data model is used by several cities, companies, and governments, in this paper we argue that its XML-based exchange format has several drawbacks. These drawbacks mean that it is difficult for developers to implement parsers for CityGML, and that practitioners have, as a consequence, to convert their data to other formats if they want to exchange them with others. We present CityJSON, a new JSON-based exchange format for the CityGML data model (version 2.0.0). CityJSON was designed with programmers in mind, so that software and APIs supporting it can be quickly built. It was also designed to be compact (a compression factor of around six with real-world datasets), and to be friendly for web and mobile development. We argue that it is considerably easier to use than the CityGML format, both for reading and for creating datasets. We discuss in this paper the main features of CityJSON, briefly present the different software packages to parse/view/edit/create files (including one to automatically convert between the JSON and GML encodings), analyse how real-world datasets compare to those of CityGML, and we also introduce \emph{Extensions}, which allow us to extend the core data model in a documented manner.
Resource-constrained multi-project scheduling with activity and time flexibility
Venue: arXiv cs.AI 2020
Year: 2020

Project scheduling in manufacturing environments often requires flexibility in terms of the selection and the exact length of alternative production activities. Moreover, the simultaneous scheduling of multiple lots is mandatory in many production planning applications. To meet these requirements, a new resource-constrained project scheduling problem (RCPSP) is introduced where both decisions (activity flexibility and time flexibility) are integrated. Besides the minimization of makespan, two new alternative objectives are presented: maximization of balanced length of selected activities (time balance) and maximization of balanced resource utilization (resource balance). New mixed integer and constraint programming (CP) models are proposed for the developed integrated flexible project scheduling problem. Benchmark instances on an already existing flexible RCPSP and the newly developed problem are solved to optimality. The real-world applicability of the suggested CP models is shown by additionally solving a large industry case.
Blockchain and its Role in the Internet of Things (IoT)
Venue: arXiv cs.NI 2020
Year: 2020

Blockchain (BC) in the Internet of Things (IoT) is a novel technology that acts with decentralized, distributed, public and real-time ledger to store transactions among IoT nodes. A blockchain is a series of blocks, each block is linked to its previous blocks. Every block has the cryptographic hash code, previous block hash, and its data. The transactions in BC are the basic units that are used to transfer data between IoT nodes. The IoT nodes are different kind of physical but smart devices with embedded sensors, actuators, programs and able to communicate with other IoT nodes. The role of BC in IoT is to provide a procedure to process secured records of data through IoT nodes. BC is a secured technology that can be used publicly and openly. IoT requires this kind of technology to allow secure communication among IoT nodes in heterogeneous environment. The transactions in BC could be traced and explored through anyone who are authenticated to communicate within the IoT. The BC in IoT may help to improve the communication security. In this paper, I explored this approach, its opportunities and challenges.
A conformance relation and complete test suites for I/O systems
Venue: arXiv cs.SE 2020
Year: 2020

Model based testing is a well-established approach to verify implementations modeled by I/O labeled transition systems (IOLTSs). One of the challenges stemming from model based testing is the conformance checking and the generation of test suites, specially when completeness is a required property. In order to check whether an implementation under test is in compliance with its respective specification one resorts to some form of conformance relation that guarantees the expected behavior of the implementations, given the behavior of the specification. The ioco conformance relation is an example of such a relation, specially suited for asynchronous models. In this work we study a more general conformance relation, show how to generate finite and complete test suites, and discuss the complexity of the test generation mechanism under this more general conformance relation. We also show that ioco conformance is a special case of this new conformance relation, and we investigate the complexity of classical ioco-complete test suites. Further, we relate our contributions to more recent works, accommodating the restrictions of their classes of fault models within our more general approach as special cases, and expose the complexity of generating any complete test suite that must satisfy their restrictions.
Tensor Dropout for Robust Learning
Venue: arXiv cs.LG 2020
Year: 2020

CNNs achieve remarkable performance by leveraging deep, over-parametrized architectures, trained on large datasets. However, they have limited generalization ability to data outside the training domain, and a lack of robustness to noise and adversarial attacks. By building better inductive biases, we can improve robustness and also obtain smaller networks that are more memory and computationally efficient. While standard CNNs use matrix computations, we study tensor layers that involve higher-order computations and provide better inductive bias. Specifically, we impose low-rank tensor structures on the weights of tensor regression layers to obtain compact networks, and propose tensor dropout, a randomization in the tensor rank for robustness. We show that our approach outperforms other methods for large-scale image classification on ImageNet and CIFAR-100. We establish a new state-of-the-art accuracy for phenotypic trait prediction on the largest dataset of brain MRI, the UK Biobank brain MRI dataset, where multi-linear structure is paramount. In all cases, we demonstrate superior performance and significantly improved robustness, both to noisy inputs and to adversarial attacks. We rigorously validate the theoretical validity of our approach by establishing the link between our randomized decomposition and non-linear dropout.
From Cubes to Twisted Cubes via Graph Morphisms in Type Theory
Venue: arXiv cs.LO 2020
Year: 2020

Cube categories are used to encode higher-dimensional categorical structures. They have recently gained significant attention in the community of homotopy type theory and univalent foundations, where types carry the structure of such higher groupoids. Bezem, Coquand, and Huber have presented a constructive model of univalence using a specific cube category, which we call the BCH category. The higher categories encoded with the BCH category have the property that all morphisms are invertible, mirroring the fact that equality is symmetric. This might not always be desirable: the field of directed type theory considers a notion of equality that is not necessarily invertible. This motivates us to suggest a category of twisted cubes which avoids built-in invertibility. Our strategy is to first develop several alternative (but equivalent) presentations of the BCH category using morphisms between suitably defined graphs. Starting from there, a minor modification allows us to define our category of twisted cubes. We prove several first results about this category, and our work suggests that twisted cubes combine properties of cubes with properties of globes and simplices (tetrahedra).
A lattice-based approach to the expressivity of deep ReLU neural networks
Venue: arXiv cs.LG 2020
Year: 2020

We present new families of continuous piecewise linear (CPWL) functions in Rn having a number of affine pieces growing exponentially in $n$. We show that these functions can be seen as the high-dimensional generalization of the triangle wave function used by Telgarsky in 2016. We prove that they can be computed by ReLU networks with quadratic depth and linear width in the space dimension. We also investigate the approximation error of one of these functions by shallower networks and prove a separation result. The main difference between our functions and other constructions is their practical interest: they arise in the scope of channel coding. Hence, computing such functions amounts to performing a decoding operation.
Relational Differential Dynamic Logic
Venue: arXiv cs.LO 2020
Year: 2020

In the field of quality assurance of hybrid systems (that combine continuous physical dynamics and discrete digital control), Platzer's differential dynamic logic (dL) is widely recognized as a deductive verification method with solid mathematical foundations and sophisticated tool support. Motivated by benchmarks provided by our industry partner, we study a relational extension of dL, aiming to formally prove statements such as "an earlier deployment of the emergency brake decreases the collision speed." A main technical challenge here is to relate two states of two dynamics at different time points. Our main contribution is a theory of suitable simulations (a relational extension of differential invariants that are central proof methods in dL), and a derived technique of time stretching. The latter features particularly high applicability, since the user does not have to synthesize a simulation out of the air. We derive new inference rules for dL from these notions, and demonstrate their use over a couple of automotive case studies.
Bounding and Estimating the Classical Information Rate of Quantum Channels with Memory
Venue: arXiv cs.IT 2020
Year: 2020

We consider the scenario of classical communication over a finite-dimensional quantum channel with memory using a separable-state input ensemble and local output measurements. We propose algorithms for estimating the information rate of such communication setups, along with algorithms for bounding the information rate based on so-called auxiliary channels. Some of the algorithms are extensions of their counterparts for (classical) finite-state-machine channels. Notably, we discuss suitable graphical models for doing the relevant computations. Moreover, the auxiliary channels are learned in a data-driven approach; i.e., only input/output sequences of the true channel are needed, but not the channel model of the true channel.
Aggregating explanation methods for stable and robust explainability
Venue: arXiv cs.LG 2020
Year: 2020

Despite a growing literature on explaining neural networks, no consensus has been reached on how to explain a neural network decision or how to evaluate an explanation. Our contributions in this paper are twofold. First, we investigate schemes to combine explanation methods and reduce model uncertainty to obtain a single aggregated explanation. We provide evidence that the aggregation is better at identifying important features, than on individual methods. Adversarial attacks on explanations is a recent active research topic. As our second contribution, we present evidence that aggregate explanations are much more robust to attacks than individual explanation methods.