OpenRaiser/Intern-Atlas huggingface dataset:
The Capacity of Symmetric Private Information Retrieval under Arbitrary Collusion and Eavesdropping Patterns
Venue: arXiv cs.IT 2020
Year: 2020

We study the symmetric private information retrieval (SPIR) problem under arbitrary collusion and eavesdropping patterns for replicated databases. We find its capacity, which is the same as the capacity of the original SPIR problem with the number of databases $N$ replaced by a number $F^*$. The number $F^*$ is the optimal solution to a linear programming problem that is a function of the joint pattern, which is the union of the collusion and eavesdropping pattern. This is the first result that shows how two arbitrary patterns collectively affect the capacity of the PIR problem. We draw the conclusion that for SPIR problems, the collusion and eavesdropping constraints are interchangeable in terms of capacity. As special cases of our result, the capacity of the SPIR problem under arbitrary collusion patterns and the capacity of the PIR problem under arbitrary eavesdropping patterns are also found.
Real-Time Face & Eye Tracking and Blink Detection using Event Cameras
Venue: arXiv cs.CV 2020
Year: 2020

Event cameras contain emerging, neuromorphic vision sensors that capture local light intensity changes at each pixel, generating a stream of asynchronous events. This way of acquiring visual information constitutes a departure from traditional frame based cameras and offers several significant advantages: low energy consumption, high temporal resolution, high dynamic range and low latency. Driver monitoring systems (DMS) are in-cabin safety systems designed to sense and understand a drivers physical and cognitive state. Event cameras are particularly suited to DMS due to their inherent advantages. This paper proposes a novel method to simultaneously detect and track faces and eyes for driver monitoring. A unique, fully convolutional recurrent neural network architecture is presented. To train this network, a synthetic event-based dataset is simulated with accurate bounding box annotations, called Neuromorphic HELEN. Additionally, a method to detect and analyse drivers eye blinks is proposed, exploiting the high temporal resolution of event cameras. Behaviour of blinking provides greater insights into a driver level of fatigue or drowsiness. We show that blinks have a unique temporal signature that can be better captured by event cameras.
General Semantic Construction of Dependent Refinement Type Systems, Categorically
Venue: arXiv cs.LO 2020
Year: 2020

Refinement types are types equipped with predicates that specify preconditions and postconditions of underlying functional languages. We propose a general semantic construction of dependent refinement type systems from underlying type systems and predicate logic, that is, a construction of liftings of closed comprehension categories from given (underlying) closed comprehension categories and posetal fibrations for predicate logic. We give sufficient conditions to lift structures such as dependent products, dependent sums, computational effects, and recursion from the underlying type systems to refinement type systems. We demonstrate the usage of our construction by giving semantics to a refinement type system and proving soundness.
In Depth Bayesian Semantic Scene Completion
Venue: arXiv cs.CV 2020
Year: 2020

This work studies Semantic Scene Completion which aims to predict a 3D semantic segmentation of our surroundings, even though some areas are occluded. For this we construct a Bayesian Convolutional Neural Network (BCNN), which is not only able to perform the segmentation, but also predict model uncertainty. This is an important feature not present in standard CNNs. We show on the MNIST dataset that the Bayesian approach performs equal or better to the standard CNN when processing digits unseen in the training phase when looking at accuracy, precision and recall. With the added benefit of having better calibrated scores and the ability to express model uncertainty. We then show results for the Semantic Scene Completion task where a category is introduced at test time on the SUNCG dataset. In this more complex task the Bayesian approach outperforms the standard CNN. Showing better Intersection over Union score and excels in Average Precision and separation scores.
Fundamental Properties of the Layer Below a Payment Channel Network (Extended Version)
Venue: arXiv cs.CR 2020
Year: 2020

Payment channel networks are a highly discussed approach for improving scalability of cryptocurrencies such as Bitcoin. As they allow processing transactions off-chain, payment channel networks are referred to as second layer technology, while the blockchain is the first layer. We uncouple payment channel networks from blockchains and look at them as first-class citizens. This brings up the question what model payment channel networks require as first layer. In response, we formalize a model (called RFL Model) for a first layer below a payment channel network. While transactions are globally made available by a blockchain, the RFL Model only provides the reduced property that a transaction is delivered to the users being affected by a transaction. We show that the reduced model's properties still suffice to implement payment channels. By showing that the RFL Model can not only be instantiated by the Bitcoin blockchain but also by trusted third parties like banks, we show that the reduction widens the design space for the first layer. Further, we show that the stronger property provided by blockchains allows for optimizations that can be used to reduce the time for locking collateral during payments over multiple hops in a payment channel network.
Vector-Vector-Matrix Architecture: A Novel Hardware-Aware Framework for Low-Latency Inference in NLP Applications
Venue: arXiv cs.CL 2020
Year: 2020

Deep neural networks have become the standard approach to building reliable Natural Language Processing (NLP) applications, ranging from Neural Machine Translation (NMT) to dialogue systems. However, improving accuracy by increasing the model size requires a large number of hardware computations, which can slow down NLP applications significantly at inference time. To address this issue, we propose a novel vector-vector-matrix architecture (VVMA), which greatly reduces the latency at inference time for NMT. This architecture takes advantage of specialized hardware that has low-latency vector-vector operations and higher-latency vector-matrix operations. It also reduces the number of parameters and FLOPs for virtually all models that rely on efficient matrix multipliers without significantly impacting accuracy. We present empirical results suggesting that our framework can reduce the latency of sequence-to-sequence and Transformer models used for NMT by a factor of four. Finally, we show evidence suggesting that our VVMA extends to other domains, and we discuss novel hardware for its efficient use.
Measuring Behavioural Similarity of Cellular Automata
Venue: arXiv cs.NE 2020
Year: 2020

Conway's Game of Life is the best-known cellular automaton. It is a classic model of emergence and self-organization, it is Turing-complete, and it can simulate a universal constructor. The Game of Life belongs to the set of semi-totalistic cellular automata, a family with 262,144 members. Many of these automata may deserve as much attention as the Game of Life, if not more. The challenge we address here is to provide a structure for organizing this large family, to make it easier to find interesting automata, and to understand the relations between automata. Packard and Wolfram (1985) divided the family into four classes, based on the observed behaviours of the rules. Eppstein (2010) proposed an alternative four-class system, based on the forms of the rules. Instead of a class-based organization, we propose a continuous high-dimensional vector space, where each automaton is represented by a point in the space. The distance between two automata in this space corresponds to the differences in their behavioural characteristics. Nearest neighbours in the space have similar behaviours. This space should make it easier for researchers to see the structure of the family of semi-totalistic rules and to find the hidden gems in the family.
An efficient representation of chronological events in medical texts
Venue: arXiv cs.CL 2020
Year: 2020

In this work we addressed the problem of capturing sequential information contained in longitudinal electronic health records (EHRs). Clinical notes, which is a particular type of EHR data, are a rich source of information and practitioners often develop clever solutions how to maximise the sequential information contained in free-texts. We proposed a systematic methodology for learning from chronological events available in clinical notes. The proposed methodological {\it path signature} framework creates a non-parametric hierarchical representation of sequential events of any type and can be used as features for downstream statistical learning tasks. The methodology was developed and externally validated using the largest in the UK secondary care mental health EHR data on a specific task of predicting survival risk of patients diagnosed with Alzheimer's disease. The signature-based model was compared to a common survival random forest model. Our results showed a 15.4$\%$ increase of risk prediction AUC at the time point of 20 months after the first admission to a specialist memory clinic and the signature method outperformed the baseline mixed-effects model by 13.2 $\%$.
AAMDRL: Augmented Asset Management with Deep Reinforcement Learning
Venue: arXiv cs.LG 2020
Year: 2020

Can an agent learn efficiently in a noisy and self adapting environment with sequential, non-stationary and non-homogeneous observations? Through trading bots, we illustrate how Deep Reinforcement Learning (DRL) can tackle this challenge. Our contributions are threefold: (i) the use of contextual information also referred to as augmented state in DRL, (ii) the impact of a one period lag between observations and actions that is more realistic for an asset management environment, (iii) the implementation of a new repetitive train test method called walk forward analysis, similar in spirit to cross validation for time series. Although our experiment is on trading bots, it can easily be translated to other bot environments that operate in sequential environment with regime changes and noisy data. Our experiment for an augmented asset manager interested in finding the best portfolio for hedging strategies shows that AAMDRL achieves superior returns and lower risk.
Predicting Biomedical Interactions with Higher-Order Graph Convolutional Networks
Venue: arXiv cs.LG 2020
Year: 2020

Biomedical interaction networks have incredible potential to be useful in the prediction of biologically meaningful interactions, identification of network biomarkers of disease, and the discovery of putative drug targets. Recently, graph neural networks have been proposed to effectively learn representations for biomedical entities and achieved state-of-the-art results in biomedical interaction prediction. These methods only consider information from immediate neighbors but cannot learn a general mixing of features from neighbors at various distances. In this paper, we present a higher-order graph convolutional network (HOGCN) to aggregate information from the higher-order neighborhood for biomedical interaction prediction. Specifically, HOGCN collects feature representations of neighbors at various distances and learns their linear mixing to obtain informative representations of biomedical entities. Experiments on four interaction networks, including protein-protein, drug-drug, drug-target, and gene-disease interactions, show that HOGCN achieves more accurate and calibrated predictions. HOGCN performs well on noisy, sparse interaction networks when feature representations of neighbors at various distances are considered. Moreover, a set of novel interaction predictions are validated by literature-based case studies.
Underpinning Theories of Software Engineering: Dynamism in Physical Sources of the Shannon Weaver Communication Model
Venue: arXiv cs.SE 2020
Year: 2020

This paper aims to contribute to further understanding of dynamism (the dynamic behavior of system models) in the mathematical and conceptual modeling of systems. This study is conducted in the context of the claim that software engineering lacks underpinning scientific theories, both for the software it produces and the processes by which it does so. The research literature proposes that information theory can provide such a benefit for software engineering. We explore the dynamism expressive power of conceptual modeling as a software engineering tool that can represent physical systems in the Shannon Weaver communication model (SWCM). Specifically, the modeled source in the SWCM is a physical phenomenon (a change that can occur in the world, e.g., tossing a coin) resulting in generating observable events and data of unaddressed information. The resultant model reflects the feasibility of extending the SWCM to be applied in conceptual modeling in software engineering.
A Conglomerate of Multiple OCR Table Detection and Extraction
Venue: arXiv cs.IR 2020
Year: 2020

Information representation as tables are compact and concise method that eases searching, indexing, and storage requirements. Extracting and cloning tables from parsable documents is easier and widely used, however industry still faces challenge in detecting and extracting tables from OCR documents or images. This paper proposes an algorithm that detects and extracts multiple tables from OCR document. The algorithm uses a combination of image processing techniques, text recognition and procedural coding to identify distinct tables in same image and map the text to appropriate corresponding cell in dataframe which can be stored as Comma-separated values, Database, Excel and multiple other usable formats.
Evaluating Attribution Methods using White-Box LSTMs
Venue: arXiv cs.LG 2020
Year: 2020

Interpretability methods for neural networks are difficult to evaluate because we do not understand the black-box models typically used to test them. This paper proposes a framework in which interpretability methods are evaluated using manually constructed networks, which we call white-box networks, whose behavior is understood a priori. We evaluate five methods for producing attribution heatmaps by applying them to white-box LSTM classifiers for tasks based on formal languages. Although our white-box classifiers solve their tasks perfectly and transparently, we find that all five attribution methods fail to produce the expected model explanations.
Substance over Style: Document-Level Targeted Content Transfer
Venue: arXiv cs.CL 2020
Year: 2020

Existing language models excel at writing from scratch, but many real-world scenarios require rewriting an existing document to fit a set of constraints. Although sentence-level rewriting has been fairly well-studied, little work has addressed the challenge of rewriting an entire document coherently. In this work, we introduce the task of document-level targeted content transfer and address it in the recipe domain, with a recipe as the document and a dietary restriction (such as vegan or dairy-free) as the targeted constraint. We propose a novel model for this task based on the generative pre-trained language model (GPT-2) and train on a large number of roughly-aligned recipe pairs (https://github.com/microsoft/document-level-targeted-content-transfer). Both automatic and human evaluations show that our model out-performs existing methods by generating coherent and diverse rewrites that obey the constraint while remaining close to the original document. Finally, we analyze our model's rewrites to assess progress toward the goal of making language generation more attuned to constraints that are substantive rather than stylistic.
Sliding-Window QPS (SW-QPS): A Perfect Parallel Iterative Switching Algorithm for Input-Queued Switches
Venue: arXiv cs.NI 2020
Year: 2020

In this work, we first propose a parallel batch switching algorithm called Small-Batch Queue-Proportional Sampling (SB-QPS). Compared to other batch switching algorithms, SB-QPS significantly reduces the batch size without sacrificing the throughput performance and hence has much lower delay when traffic load is light to moderate. It also achieves the lowest possible time complexity of $O(1)$ per matching computation per port, via parallelization. We then propose another algorithm called Sliding-Window QPS (SW-QPS). SW-QPS retains and enhances all benefits of SB-QPS, and reduces the batching delay to zero via a novel switching framework called sliding-window switching. In addition, SW-QPS computes matchings of much higher qualities, as measured by the resulting throughput and delay performances, than QPS-1, the state-of-the-art regular switching algorithm that builds upon the same underlying bipartite matching algorithm.
Incorporate Semantic Structures into Machine Translation Evaluation via UCCA
Venue: arXiv cs.CL 2020
Year: 2020

Copying mechanism has been commonly used in neural paraphrasing networks and other text generation tasks, in which some important words in the input sequence are preserved in the output sequence. Similarly, in machine translation, we notice that there are certain words or phrases appearing in all good translations of one source text, and these words tend to convey important semantic information. Therefore, in this work, we define words carrying important semantic meanings in sentences as semantic core words. Moreover, we propose an MT evaluation approach named Semantically Weighted Sentence Similarity (SWSS). It leverages the power of UCCA to identify semantic core words, and then calculates sentence similarity scores on the overlap of semantic core words. Experimental results show that SWSS can consistently improve the performance of popular MT evaluation metrics which are based on lexical similarity.
Generating Large Convex Polytopes Directly on Point Clouds
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we present a method to efficiently generate large, free, and guaranteed convex space among arbitrarily cluttered obstacles. Our method operates directly on point clouds, avoids expensive calculations, and processes thousands of points within a few milliseconds, which extremely suits embedded platforms. The base stone of our method is sphere flipping, a one-one invertible nonlinear transformation, which maps a set of unordered points to a nonlinear space. With these wrapped points, we obtain a collision-free star convex polytope. Then, utilizing the star convexity, we efficiently modify the polytope to convex and guarantee its free of obstacles. Extensive quantitative evaluations show that our method significantly outperforms state-of-the-art works in efficiency. We also present practical applications with our method in 3D, including large-scale deformable topological mapping and quadrotor optimal trajectory planning, to validate its capability and efficiency. The source code of our method will be released for the reference of the community.
The role of interactive super-computing in using HPC for urgent decision making
Venue: arXiv cs.DC 2020
Year: 2020

Technological advances are creating exciting new opportunities that have the potential to move HPC well beyond traditional computational workloads. In this paper we focus on the potential for HPC to be instrumental in responding to disasters such as wildfires, hurricanes, extreme flooding, earthquakes, tsunamis, winter weather conditions, and accidents. Driven by the VESTEC EU funded H2020 project, our research looks to prove HPC as a tool not only capable of simulating disasters once they have happened, but also one which is able to operate in a responsive mode, supporting disaster response teams making urgent decisions in real-time. Whilst this has the potential to revolutionise disaster response, it requires the ability to drive HPC interactively, both from the user's perspective and also based upon the arrival of data. As such interactivity is a critical component in enabling HPC to be exploited in the role of supporting disaster response teams so that urgent decision makers can make the correct decision first time, every time.
iPregel: Vertex-centric programmability vs memory efficiency and performance, why choose?
Venue: arXiv cs.DC 2020
Year: 2020

The vertex-centric programming model, designed to improve the programmability in graph processing application writing, has attracted great attention over the years. However, shared memory frameworks that implement the vertex-centric interface all expose a common tradeoff: programmability against memory efficiency and performance. Our approach, iPregel, preserves vertex-centric programmability, while implementing optimisations for performance, and designing these so they are transparent to a user's application code, hence not impacting programmability. In this paper, we evaluate iPregel against FemtoGraph, whose characteristics are identical, an asynchronous counterpart GraphChi and the vertex-subset-centric framework Ligra. Our experiments include three of the most popular vertex-centric benchmark applications over 4 real-world publicly accessible graphs, which cover orders of magnitude between a million to a billion edges, measuring execution time and peak memory usage. Finally, we evaluate the programmability of each framework by comparing against Google's original Pregel framework. Experiments demonstrate that iPregel, like FemtoGraph, does not sacrifice vertex-centric programmability for additional performance and memory efficiency optimisations, which contrasts against GraphChi and Ligra. Sacrificing vertex-centric programmability allowed the latter to benefit from substantial performance and memory efficiency gains. We demonstrate that iPregel is up to 2300 times faster than FemtoGraph, as well as generating a memory footprint up to 100 times smaller. Ligra and GraphChi are up to 17000 and 700 times faster than FemtoGraph but, when comparing against iPregel, this maximum speed-up drops to 10. Furthermore, with PageRank, iPregel is the fastest overall. For memory efficiency, iPregel provides the same memory efficiency as Ligra and 3 to 6 times lighter than GraphChi on average.
Lazy Search Trees
Venue: arXiv cs.DS 2020
Year: 2020

We introduce the lazy search tree data structure. The lazy search tree is a comparison-based data structure on the pointer machine that supports order-based operations such as rank, select, membership, predecessor, successor, minimum, and maximum while providing dynamic operations insert, delete, change-key, split, and merge. We analyze the performance of our data structure based on a partition of current elements into a set of gaps $\{Δ_i\}$ based on rank. A query falls into a particular gap and splits the gap into two new gaps at a rank $r$ associated with the query operation. If we define $B = \sum_i |Δ_i| \log_2(n/|Δ_i|)$, our performance over a sequence of $n$ insertions and $q$ distinct queries is $O(B + \min(n \log \log n, n \log q))$. We show $B$ is a lower bound. Effectively, we reduce the insertion time of binary search trees from $Θ(\log n)$ to $O(\min(\log(n/|Δ_i|) + \log \log |Δ_i|, \; \log q))$, where $Δ_i$ is the gap in which the inserted element falls. Over a sequence of $n$ insertions and $q$ queries, a time bound of $O(n \log q + q \log n)$ holds; better bounds are possible when queries are non-uniformly distributed. As an extreme case of non-uniformity, if all queries are for the minimum element, the lazy search tree performs as a priority queue with $O(\log \log n)$ time insert and decrease-key operations. The same data structure supports queries for any rank, interpolating between binary search trees and efficient priority queues. Lazy search trees can be implemented to operate mostly on arrays, requiring only $O(\min(q, n))$ pointers. Via direct reduction, our data structure also supports the efficient access theorems of the splay tree, providing a powerful data structure for non-uniform element access, both when the number of accesses is small and large.