OpenRaiser/Intern-Atlas huggingface dataset:
Algebraic Extension Ring Framework for Non-Commutative Asymmetric Cryptography
Venue: arXiv cs.CR 2020
Year: 2020

Post-Quantum Cryptography PQC attempts to find cryptographic protocols resistant to attacks using Shors polynomial time algorithm for numerical field problems or Grovers algorithm to find the unique input to a black-box function that produces a particular output value. The use of non-standard algebraic structures like non-commutative or non-associative structures, combined with one-way trapdoor functions derived from combinatorial group theory, are mainly unexplored choices for these new kinds of protocols and overlooked in current PQC solutions. In this paper, we develop an algebraic extension ring framework who could be applied to different asymmetric protocols, i.e. key exchange, key transport, enciphering, digital signature, zero-knowledge authentication, oblivious transfer, secret sharing etc.. A valuable feature is that there is no need for big number libraries as all arithmetic is performed in F256 extension field operations (precisely the AES field). We assume that the new framework is cryptographical secure against strong classical attacks like the sometimes-useful length-based attack, Romankovs linearization attacks and Tsabans algebraic span attack. This statement is based on the non-linear structure of the selected platform which proved to be useful protecting the AES protocol. Otherwise, it could resist post-quantum attacks Grover, Shor and be particularly useful for computational platforms with limited capabilities like USB cryptographic keys or smartcards. Semantic security IND-CCA2 could also be inferred for this new platform.
Decomposing Probabilistic Lambda-calculi
Venue: arXiv cs.LO 2020
Year: 2020

A notion of probabilistic lambda-calculus usually comes with a prescribed reduction strategy, typically call-by-name or call-by-value, as the calculus is non-confluent and these strategies yield different results. This is a break with one of the main advantages of lambda-calculus: confluence, which means results are independent from the choice of strategy. We present a probabilistic lambda-calculus where the probabilistic operator is decomposed into two syntactic constructs: a generator, which represents a probabilistic event; and a consumer, which acts on the term depending on a given event. The resulting calculus, the Probabilistic Event Lambda-Calculus, is confluent, and interprets the call-by-name and call-by-value strategies through different interpretations of the probabilistic operator into our generator and consumer constructs. We present two notions of reduction, one via fine-grained local rewrite steps, and one by generation and consumption of probabilistic events. Simple types for the calculus are essentially standard, and they convey strong normalization. We demonstrate how we can encode call-by-name and call-by-value probabilistic evaluation.
Interpretability of machine learning based prediction models in healthcare
Venue: arXiv cs.LG 2020
Year: 2020

There is a need of ensuring machine learning models that are interpretable. Higher interpretability of the model means easier comprehension and explanation of future predictions for end-users. Further, interpretable machine learning models allow healthcare experts to make reasonable and data-driven decisions to provide personalized decisions that can ultimately lead to higher quality of service in healthcare. Generally, we can classify interpretability approaches in two groups where the first focuses on personalized interpretation (local interpretability) while the second summarizes prediction models on a population level (global interpretability). Alternatively, we can group interpretability methods into model-specific techniques, which are designed to interpret predictions generated by a specific model, such as a neural network, and model-agnostic approaches, which provide easy-to-understand explanations of predictions made by any machine learning model. Here, we give an overview of interpretability approaches and provide examples of practical interpretability of machine learning in different areas of healthcare, including prediction of health-related outcomes, optimizing treatments or improving the efficiency of screening for specific conditions. Further, we outline future directions for interpretable machine learning and highlight the importance of developing algorithmic solutions that can enable machine-learning driven decision making in high-stakes healthcare problems.
Balancing Cost and Benefit with Tied-Multi Transformers
Venue: arXiv cs.CL 2020
Year: 2020

We propose and evaluate a novel procedure for training multiple Transformers with tied parameters which compresses multiple models into one enabling the dynamic choice of the number of encoder and decoder layers during decoding. In sequence-to-sequence modeling, typically, the output of the last layer of the N-layer encoder is fed to the M-layer decoder, and the output of the last decoder layer is used to compute loss. Instead, our method computes a single loss consisting of NxM losses, where each loss is computed from the output of one of the M decoder layers connected to one of the N encoder layers. Such a model subsumes NxM models with different number of encoder and decoder layers, and can be used for decoding with fewer than the maximum number of encoder and decoder layers. We then propose a mechanism to choose a priori the number of encoder and decoder layers for faster decoding, and also explore recurrent stacking of layers and knowledge distillation for model compression. We present a cost-benefit analysis of applying the proposed approaches for neural machine translation and show that they reduce decoding costs while preserving translation quality.
On polynomial recursive sequences
Venue: arXiv cs.FL 2020
Year: 2020

We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expressiveness results translate to class separations. A typical example of a polynomial recursive sequence is b_n=n!. Our main result is that the sequence u_n=n^n is not polynomial recursive.
From Stateless to Stateful Priorities: Technical Report
Venue: arXiv cs.LO 2020
Year: 2020

We present the notion of stateful priorities for imposing precise restrictions on system actions, in order to meet safety constraints. By using stateful priorities we are able to exclusively restrict erroneous system behavior as specified by the constraint, whereas safe system behavior remains unrestricted. Given a system modeled as a network of discrete automata and an error constraint, we present algorithms which use those inputs to synthesize stateful priorities. We present as well a network transformation which uses synthesized priorities for blocking all system actions leading to the input error. Our experiments with three real-world examples demonstrate the applicability of our approach.
Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
Venue: arXiv cs.DS 2020
Year: 2020

Given an undirected graph $G$ and integers $c$ and $k$, the Maximum Edge-Colorable Subgraph problem asks whether we can delete at most $k$ edges in $G$ to obtain a graph that has a proper edge coloring with at most $c$ colors. We show that Maximum Edge-Colorable Subgraph admits, for every fixed $c$, a linear-size problem kernel when parameterized by the edge deletion distance of $G$ to a graph with maximum degree $c-1$. This parameterization measures the distance to instances that, due to Vizing's famous theorem, are trivial yes-instances. For $c\le 4$, we also provide a linear-size kernel for the same parameterization for Multi Strong Triadic Closure, a related edge coloring problem with applications in social network analysis. We provide further results for Maximum Edge-Colorable Subgraph parameterized by the vertex deletion distance to graphs where every component has order at most $c$ and for the list-colored versions of both problems.
Roto-Translation Equivariant Convolutional Networks: Application to Histopathology Image Analysis
Venue: arXiv cs.CV 2020
Year: 2020

Rotation-invariance is a desired property of machine-learning models for medical image analysis and in particular for computational pathology applications. We propose a framework to encode the geometric structure of the special Euclidean motion group SE(2) in convolutional networks to yield translation and rotation equivariance via the introduction of SE(2)-group convolution layers. This structure enables models to learn feature representations with a discretized orientation dimension that guarantees that their outputs are invariant under a discrete set of rotations. Conventional approaches for rotation invariance rely mostly on data augmentation, but this does not guarantee the robustness of the output when the input is rotated. At that, trained conventional CNNs may require test-time rotation augmentation to reach their full capability. This study is focused on histopathology image analysis applications for which it is desirable that the arbitrary global orientation information of the imaged tissues is not captured by the machine learning models. The proposed framework is evaluated on three different histopathology image analysis tasks (mitosis detection, nuclei segmentation and tumor classification). We present a comparative analysis for each problem and show that consistent increase of performances can be achieved when using the proposed framework.
Bimodal Distribution Removal and Genetic Algorithm in Neural Network for Breast Cancer Diagnosis
Venue: arXiv cs.LG 2020
Year: 2020

Diagnosis of breast cancer has been well studied in the past. Multiple linear programming models have been devised to approximate the relationship between cell features and tumour malignancy. However, these models are less capable in handling non-linear correlations. Neural networks instead are powerful in processing complex non-linear correlations. It is thus certainly beneficial to approach this cancer diagnosis problem with a model based on neural network. Particularly, introducing bias to neural network training process is deemed as an important means to increase training efficiency. Out of a number of popular proposed methods for introducing artificial bias, Bimodal Distribution Removal (BDR) presents ideal efficiency improvement results and fair simplicity in implementation. However, this paper examines the effectiveness of BDR against the target cancer diagnosis classification problem and shows that BDR process in fact negatively impacts classification performance. In addition, this paper also explores genetic algorithm as an efficient tool for feature selection and produced significantly better results comparing to baseline model that without any feature selection in place
Optimizing Information Freshness in Wireless Networks: A Stochastic Geometry Approach
Venue: arXiv cs.IT 2020
Year: 2020

Optimization of information freshness in wireless networks has usually been performed based on queueing analysis that captures only the temporal traffic dynamics associated with the transmitters and receivers. However, the effect of interference, which is mainly dominated by the interferers' geographic locations, is not well understood. In this paper, we leverage a spatiotemporal model, which allows one to characterize the age of information (AoI) from a joint queueing-geometry perspective, for the design of a decentralized scheduling policy that exploits local observation to make transmission decisions that minimize the AoI. To quantify the performance, we also derive accurate and tractable expressions for the peak AoI. Numerical results reveal that: i) the packet arrival rate directly affects the service process due to queueing interactions, ii) the proposed scheme can adapt to traffic variations and largely reduce the peak AoI, and iii) the proposed scheme scales well as the network grows in size. This is done by adaptively adjusting the radio access probability at each transmitter to the change of the ambient environment.
Do you comply with AI? -- Personalized explanations of learning algorithms and their impact on employees' compliance behavior
Venue: arXiv cs.CY 2020
Year: 2020

Machine Learning algorithms are technological key enablers for artificial intelligence (AI). Due to the inherent complexity, these learning algorithms represent black boxes and are difficult to comprehend, therefore influencing compliance behavior. Hence, compliance with the recommendations of such artifacts, which can impact employees' task performance significantly, is still subject to research - and personalization of AI explanations seems to be a promising concept in this regard. In our work, we hypothesize that, based on varying backgrounds like training, domain knowledge and demographic characteristics, individuals have different understandings and hence mental models about the learning algorithm. Personalization of AI explanations, related to the individuals' mental models, may thus be an instrument to affect compliance and therefore employee task performance. Our preliminary results already indicate the importance of personalized explanations in industry settings and emphasize the importance of this research endeavor.
LibrettOS: A Dynamically Adaptable Multiserver-Library OS
Venue: arXiv cs.OS 2020
Year: 2020

We present LibrettOS, an OS design that fuses two paradigms to simultaneously address issues of isolation, performance, compatibility, failure recoverability, and run-time upgrades. LibrettOS acts as a microkernel OS that runs servers in an isolated manner. LibrettOS can also act as a library OS when, for better performance, selected applications are granted exclusive access to virtual hardware resources such as storage and networking. Furthermore, applications can switch between the two OS modes with no interruption at run-time. LibrettOS has a uniquely distinguishing advantage in that, the two paradigms seamlessly coexist in the same OS, enabling users to simultaneously exploit their respective strengths (i.e., greater isolation, high performance). Systems code, such as device drivers, network stacks, and file systems remain identical in the two modes, enabling dynamic mode switching and reducing development and maintenance costs. To illustrate these design principles, we implemented a prototype of LibrettOS using rump kernels, allowing us to reuse existent, hardened NetBSD device drivers and a large ecosystem of POSIX/BSD-compatible applications. We use hardware (VM) virtualization to strongly isolate different rump kernel instances from each other. Because the original rumprun unikernel targeted a much simpler model for uniprocessor systems, we redesigned it to support multicore systems. Unlike kernel-bypass libraries such as DPDK, applications need not be modified to benefit from direct hardware access. LibrettOS also supports indirect access through a network server that we have developed. Applications remain uninterrupted even when network components fail or need to be upgraded. Finally, to efficiently use hardware resources, applications can dynamically switch between the indirect and direct modes based on their I/O load at run-time. [full abstract is in the paper]
SpArch: Efficient Architecture for Sparse Matrix Multiplication
Venue: arXiv cs.AR 2020
Year: 2020

Generalized Sparse Matrix-Matrix Multiplication (SpGEMM) is a ubiquitous task in various engineering and scientific applications. However, inner product based SpGENN introduces redundant input fetches for mismatched nonzero operands, while outer product based approach suffers from poor output locality due to numerous partial product matrices. Inefficiency in the reuse of either inputs or outputs data leads to extensive and expensive DRAM access. To address this problem, this paper proposes an efficient sparse matrix multiplication accelerator architecture, SpArch, which jointly optimizes the data locality for both input and output matrices. We first design a highly parallelized streaming-based merger to pipeline the multiply and merge stage of partial matrices so that partial matrices are merged on chip immediately after produced. We then propose a condensed matrix representation that reduces the number of partial matrices by three orders of magnitude and thus reduces DRAM access by 5.4x. We further develop a Huffman tree scheduler to improve the scalability of the merger for larger sparse matrices, which reduces the DRAM access by another 1.8x. We also resolve the increased input matrix read induced by the new representation using a row prefetcher with near-optimal buffer replacement policy, further reducing the DRAM access by 1.5x. Evaluated on 20 benchmarks, SpArch reduces the total DRAM access by 2.8x over previous state-of-the-art. On average, SpArch achieves 4x, 19x, 18x, 17x, 1285x speedup and 6x, 164x, 435x, 307x, 62x energy savings over OuterSPACE, MKL, cuSPARSE, CUSP, and ARM Armadillo, respectively.
Toward An Interdisciplinary Methodology to Solve New (Old) Transportation Problems
Venue: arXiv cs.HC 2020
Year: 2020

The rising availability of digital traces provides a fertile ground for new solutions to both, new and old problems in cities. Even though a massive data set analyzed with Data Science methods may provide a powerful solution to a problem, its adoption by relevant stakeholders is not guaranteed, due to adoption blockers such as lack of interpretability and transparency. In this context, this paper proposes a preliminary methodology toward bridging two disciplines, Data Science and Transportation, to solve urban problems with methods that are suitable for adoption. The methodology is defined by four steps where people from both disciplines go from algorithm and model definition to the building of a potentially adoptable solution. As case study, we describe how this methodology was applied to define a model to infer commuting trips with mode of transportation from mobile phone data.
Seeker or Avoider? User Modeling for Inspiration Deployment in Large-Scale Ideation
Venue: arXiv cs.HC 2020
Year: 2020

People react differently to inspirations shown to them during brainstorming. Existing research on large-scale ideation systems has investigated this phenomenon through aspects of timing, inspiration similarity and inspiration integration. However, these approaches do not address people's individual preferences. In the research presented, we aim to address this lack with regards to inspirations. In a first step, we conducted a co-located brainstorming study with 15 participants, which allowed us to differentiate two types of ideators: Inspiration seekers and inspiration avoiders. These insights informed the study design of the second step, where we propose a user model for classifying people depending on their ideator types, which was translated into a rule-based and a random forest-based classifier. We evaluated the validity of our user model by conducting an online experiment with 380 participants. The results confirmed our proposed ideator types, showing that, while seekers benefit from the availability of inspiration, avoiders were influenced negatively. The random forest classifier enabled us to differentiate people with a 73 \% accuracy after only three minutes of ideation. These insights show that the proposed ideator types are a promising user model for large-scale ideation. In future work, this distinction may help to design more personalized large-scale ideation systems that recommend inspirations adaptively.
Simulation Of Reaction Systems By The Strictly Minimal Ones
Venue: arXiv cs.LO 2020
Year: 2020

Reaction systems, introduced by Ehrenfeucht and Rozenberg, are elementary computational models based on biochemical reactions transpiring within the living cells. Numerous studies focus on mathematical aspects of minimal reaction systems due to their simplicity and rich generative power. In 2014 Manzoni, Pocas, and Porreca showed that every reaction system can be simulated by some minimal reaction system over an extended background set. Motivated by their work, we introduce the concepts of strictly minimal and hybrid reaction systems. Using our new concepts, the result of Manzoni et al. is revisited and strengthened. We also show that extension of the background set by polynomially bounded many elements is not sufficient to guarantee the aforementioned simulation. Finally, an analogous result for strong simulation is obtained.
oIRL: Robust Adversarial Inverse Reinforcement Learning with Temporally Extended Actions
Venue: arXiv cs.LG 2020
Year: 2020

Explicit engineering of reward functions for given environments has been a major hindrance to reinforcement learning methods. While Inverse Reinforcement Learning (IRL) is a solution to recover reward functions from demonstrations only, these learned rewards are generally heavily \textit{entangled} with the dynamics of the environment and therefore not portable or \emph{robust} to changing environments. Modern adversarial methods have yielded some success in reducing reward entanglement in the IRL setting. In this work, we leverage one such method, Adversarial Inverse Reinforcement Learning (AIRL), to propose an algorithm that learns hierarchical disentangled rewards with a policy over options. We show that this method has the ability to learn \emph{generalizable} policies and reward functions in complex transfer learning tasks, while yielding results in continuous control benchmarks that are comparable to those of the state-of-the-art methods.
Facilitating SQL Query Composition and Analysis
Venue: arXiv cs.DB 2020
Year: 2020

Formulating efficient SQL queries requires several cycles of tuning and execution, particularly for inexperienced users. We examine methods that can accelerate and improve this interaction by providing insights about SQL queries prior to execution. We achieve this by predicting properties such as the query answer size, its run-time, and error class. Unlike existing approaches, our approach does not rely on any statistics from the database instance or query execution plans. This is particularly important in settings with limited access to the database instance. Our approach is based on using data-driven machine learning techniques that rely on large query workloads to model SQL queries and their properties. We evaluate the utility of neural network models and traditional machine learning models. We use two real-world query workloads: the Sloan Digital Sky Survey (SDSS) and the SQLShare query workload. Empirical results show that the neural network models are more accurate in predicting the query error class, achieving a higher F-measure on classes with fewer samples as well as performing better on other problems such as run-time and answer size prediction. These results are encouraging and confirm that SQL query workloads and data-driven machine learning methods can be leveraged to facilitate query composition and analysis.