OpenRaiser/Intern-Atlas huggingface dataset:
A Partial Information Decomposition Based on Causal Tensors
Venue: arXiv cs.IT 2020
Year: 2020

We propose a partial information decomposition based on the newly introduced framework of causal tensors, i.e., multilinear stochastic maps that transform source data into destination data. This framework enables us to express an indirect association in terms of the constituting, direct associations. This is not possible when using average measures like mutual information or transfer entropy. From this, an intuitive definition of redundant and unique information arises. The proposed redundancy satisfies the three axioms stated by introduced by Williams and Beer. The symmetry and self-redundancy properties follow directly from our definition. The Data Processing Inequality ensures that the monotonicity axiom is satisfied. Additional, two other proposed axioms are satisfied: the identity property, and the left monotonicity axiom. Because causal tensors can describe both mutual information as transfer entropy, the proposed partial information decomposition applies to both measures. Results show that the decomposition closely resembles the decomposition of another approach that expresses associations in terms of mutual information a posteriori. It is furthermore demonstrated that negative contributions can arise when our assumptions about completeness of the data set, or what should be included as a source, are incorrect.
InfiniCache: Exploiting Ephemeral Serverless Functions to Build a Cost-Effective Memory Cache
Venue: arXiv cs.DC 2020
Year: 2020

Internet-scale web applications are becoming increasingly storage-intensive and rely heavily on in-memory object caching to attain required I/O performance. We argue that the emerging serverless computing paradigm provides a well-suited, cost-effective platform for object caching. We present InfiniCache, a first-of-its-kind in-memory object caching system that is completely built and deployed atop ephemeral serverless functions. InfiniCache exploits and orchestrates serverless functions' memory resources to enable elastic pay-per-use caching. InfiniCache's design combines erasure coding, intelligent billed duration control, and an efficient data backup mechanism to maximize data availability and cost-effectiveness while balancing the risk of losing cached state and performance. We implement InfiniCache on AWS Lambda and show that it: (1) achieves 31 -- 96X tenant-side cost savings compared to AWS ElastiCache for a large-object-only production workload, (2) can effectively provide 95.4% data availability for each one hour window, and (3) enables comparative performance seen in a typical in-memory cache.
Segmentation and Recovery of Superquadric Models using Convolutional Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

In this paper we address the problem of representing 3D visual data with parameterized volumetric shape primitives. Specifically, we present a (two-stage) approach built around convolutional neural networks (CNNs) capable of segmenting complex depth scenes into the simpler geometric structures that can be represented with superquadric models. In the first stage, our approach uses a Mask RCNN model to identify superquadric-like structures in depth scenes and then fits superquadric models to the segmented structures using a specially designed CNN regressor. Using our approach we are able to describe complex structures with a small number of interpretable parameters. We evaluated the proposed approach on synthetic as well as real-world depth data and show that our solution does not only result in competitive performance in comparison to the state-of-the-art, but is able to decompose scenes into a number of superquadric models at a fraction of the time required by competing approaches. We make all data and models used in the paper available from https://lmi.fe.uni-lj.si/en/research/resources/sq-seg.
Automatic weak imposition of free slip boundary conditions via Nitsche's method: application to nonlinear problems in geodynamics
Venue: arXiv cs.CE 2020
Year: 2020

Imposition of free slip boundary conditions in science and engineering simulations presents a challenge when the simulation domain is non-trivial. Inspired by recent progress in symbolic computation of discontinuous Galerkin finite element methods, we present a symmetric interior penalty form of Nitsche's method to weakly impose these slip boundary conditions and present examples of its use in the Stokes subsystem motivated by problems in geodynamics. We compare numerical results with well established benchmark problems. We also examine performance of the method with iterative solvers.
The Rockerverse: Packages and Applications for Containerization with R
Venue: arXiv cs.SE 2020
Year: 2020

The Rocker Project provides widely used Docker images for R across different application scenarios. This article surveys downstream projects that build upon the Rocker Project images and presents the current state of R packages for managing Docker images and controlling containers. These use cases cover diverse topics such as package development, reproducible research, collaborative work, cloud-based data processing, and production deployment of services. The variety of applications demonstrates the power of the Rocker Project specifically and containerisation in general. Across the diverse ways to use containers, we identified common themes: reproducible environments, scalability and efficiency, and portability across clouds. We conclude that the current growth and diversification of use cases is likely to continue its positive impact, but see the need for consolidating the Rockerverse ecosystem of packages, developing common practices for applications, and exploring alternative containerisation software.
Extreme Algorithm Selection With Dyadic Feature Representation
Venue: arXiv cs.LG 2020
Year: 2020

Algorithm selection (AS) deals with selecting an algorithm from a fixed set of candidate algorithms most suitable for a specific instance of an algorithmic problem, e.g., choosing solvers for SAT problems. Benchmark suites for AS usually comprise candidate sets consisting of at most tens of algorithms, whereas in combined algorithm selection and hyperparameter optimization problems the number of candidates becomes intractable, impeding to learn effective meta-models and thus requiring costly online performance evaluations. Therefore, here we propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms, facilitating meta learning. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation in which both problem instances and algorithms are described. We find the latter to improve significantly over the current state of the art in various metrics.
Comparison of scanned administrative document images
Venue: arXiv cs.CV 2020
Year: 2020

In this work the methods of comparison of digitized copies of administrative documents were considered. This problem arises, for example, when comparing two copies of documents signed by two parties in order to find possible modifications made by one party, in the banking sector at the conclusion of contracts in paper form. The proposed method of document image comparison is based on a combination of several ways of image comparison of words that are descriptors of text feature points. Testing was conducted on public Payslip Dataset (French). The results showed the high quality and the reliability of finding differences in two images that are versions of the same document.
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
Venue: arXiv cs.DS 2020
Year: 2020

Given a directed weighted graph $G=(V,E)$ undergoing vertex insertions \emph{and} deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that processes updates efficiently and returns after each update the distance matrix to the current version of $G$. In two breakthrough results, Italiano and Demetrescu [STOC '03] presented an algorithm that requires $\tilde{O}(n^2)$ \emph{amortized} update time, and Thorup showed in [STOC '05] that \emph{worst-case} update time $\tilde{O}(n^{2+3/4})$ can be achieved. In this article, we make substantial progress on the problem. We present the following new results: (1) We present the first deterministic data structure that breaks the $\tilde{O}(n^{2+3/4})$ worst-case update time bound by Thorup which has been standing for almost 15 years. We improve the worst-case update time to $\tilde{O}(n^{2+5/7}) = \tilde{O}(n^{2.71..})$ and to $\tilde{O}(n^{2+3/5}) = \tilde{O}(n^{2.6})$ for unweighted graphs. (2) We present a simple deterministic algorithm with $\tilde{O}(n^{2+3/4})$ worst-case update time ($\tilde{O}(n^{2+2/3})$ for unweighted graphs), and a simple Las-Vegas algorithm with worst-case update time $\tilde{O}(n^{2+2/3})$ ($\tilde{O}(n^{2 + 1/2})$ for unweighted graphs) that works against a non-oblivious adversary. Both data structures require space $\tilde{O}(n^2)$. These are the first exact dynamic algorithms with truly-subcubic update time \emph{and} space usage. This makes significant progress on an open question posed in multiple articles [COCOON'01, STOC '03, ICALP'04, Encyclopedia of Algorithms '08] and is critical to algorithms in practice [TALG '06] where large space usage is prohibitive. Moreover, they match the worst-case update time of the best previous algorithms and the second algorithm improves upon a Monte-Carlo algorithm in a weaker adversary model with the same running time [SODA '17].
Multisequences with high joint nonlinear complexity from function fields
Venue: arXiv cs.IT 2020
Year: 2020

Multisequences over finite fields play a pushing role in the applications that relate to parallelization, such as word-based stream ciphers and pseudorandom vector generation. It is interesting to study the complexity measures for multisequences. In this paper, we propose three constructions of multisequences over finite fields from rational function fields and Hermitian function fields. We also analyze the joint nonlinear complexity of these multisequences. Moreover, the length and dimension of these multisequences are flexible.
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
Venue: arXiv cs.DS 2020
Year: 2020

In the decremental $(1+ε)$-approximate Single-Source Shortest Path (SSSP) problem, we are given a graph $G=(V,E)$ with $n = |V|, m = |E|$, undergoing edge deletions, and a distinguished source $s \in V$, and we are asked to process edge deletions efficiently and answer queries for distance estimates $\widetilde{\mathbf{dist}}_G(s,v)$ for each $v \in V$, at any stage, such that $\mathbf{dist}_G(s,v) \leq \widetilde{\mathbf{dist}}_G(s,v) \leq (1+ ε)\mathbf{dist}_G(s,v)$. In the decremental $(1+ε)$-approximate All-Pairs Shortest Path (APSP) problem, we are asked to answer queries for distance estimates $\widetilde{\mathbf{dist}}_G(u,v)$ for every $u,v \in V$. In this article, we consider the problems for undirected, unweighted graphs. We present a new \emph{deterministic} algorithm for the decremental $(1+ε)$-approximate SSSP problem that takes total update time $O(mn^{0.5 + o(1)})$. Our algorithm improves on the currently best algorithm for dense graphs by Chechik and Bernstein [STOC 2016] with total update time $\tilde{O}(n^2)$ and the best existing algorithm for sparse graphs with running time $\tilde{O}(n^{1.25}\sqrt{m})$ [SODA 2017] whenever $m = O(n^{1.5 - o(1)})$. In order to obtain this new algorithm, we develop several new techniques including improved decremental cover data structures for graphs, a more efficient notion of the heavy/light decomposition framework introduced by Chechik and Bernstein and the first clustering technique to maintain a dynamic \emph{sparse} emulator in the deterministic setting. As a by-product, we also obtain a new simple deterministic algorithm for the decremental $(1+ε)$-approximate APSP problem with near-optimal total running time $\tilde{O}(mn /ε)$ matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
Venue: arXiv cs.DS 2020
Year: 2020

Given a dynamic digraph $G = (V,E)$ undergoing edge deletions and given $s\in V$ and $ε>0$, we consider the problem of maintaining $(1+ε)$-approximate shortest path distances from $s$ to all vertices in $G$ over the sequence of deletions. Even and Shiloach (J.~ACM'$81$) give a deterministic data structure for the exact version of the problem with total update time $O(mn)$. Henzinger et al. (STOC'$14$, ICALP'$15$) give a Monte Carlo data structure for the approximate version with improved total update time $ O(mn^{0.9 + o(1)}\log W)$ where $W$ is the ratio between the largest and smallest edge weight. A drawback of their data structure is that they only work against an oblivious adversary, meaning that the sequence of deletions needs to be fixed in advance. This limits its application as a black box inside algorithms. We present the following $(1+ε)$-approximate data structures: (1) the first data structure is Las Vegas and works against an adaptive adversary; it has total expected update time $\tilde O(m^{2/3}n^{4/3})$ for unweighted graphs and $\tilde O(m^{3/4}n^{5/4}\log W)$ for weighted graphs, (2) the second data structure is Las Vegas and assumes an oblivious adversary; it has total expected update time $\tilde O(\sqrt m n^{3/2})$ for unweighted graphs and $\tilde O(m^{2/3}n^{4/3}\log W)$ for weighted graphs, (3) the third data structure is Monte Carlo and is correct w.h.p.~against an oblivious adversary; it has total expected update time $\tilde O((mn)^{7/8}\log W) = \tilde O(mn^{3/4}\log W)$. Each of our data structures can be queried at any stage of $G$ in constant worst-case time; if the adversary is oblivious, a query can be extended to also report such a path in time proportional to its length. Our update times are faster than those of Henzinger et al.~for all graph densities.
Reconfigurable Intelligent Surface for MISO Systems with Proportional Rate Constraints
Venue: arXiv cs.IT 2020
Year: 2020

This paper investigates the system spectral efficiency (SE) in reconfigurable intelligent surface (RIS)-aided multiuser multiple-input single-output (MISO) systems, where RIS can reconfigure the propagation environment via a large number of controllable and intelligent phase shifters. In order to explore the system SE performance behavior with user proportional fairness for such a system, an optimization problem is formulated to maximize the SE by jointly considering the power allocation at the base station (BS) and phase shift at the RIS, under nonlinear proportional rate fairness constraints. To solve the nonconvex optimization problem, an effective solution is developed, which capitalizes on an iterative algorithm with closed-form expressions, i.e., alternatively optimizing the transmit power at the BS and the reflecting phase shift at the RIS. Numerical simulations are provided to validate the theoretical analysis and assess the performance of the proposed alternative algorithm.
Smart Resource Management for Data Streaming using an Online Bin-packing Strategy
Venue: arXiv cs.DC 2020
Year: 2020

Data stream processing frameworks provide reliable and efficient mechanisms for executing complex workflows over large datasets. A common challenge for the majority of currently available streaming frameworks is efficient utilization of resources. Most frameworks use static or semi-static settings for resource utilization that work well for established use cases but lead to marginal improvements for unseen scenarios. Another pressing issue is the efficient processing of large individual objects such as images and matrices typical for scientific datasets. HarmonicIO has proven to be a good solution for streams of relatively large individual objects, as demonstrated in a benchmark comparison with the Spark and Kafka streaming frameworks. We here present an extension of the HarmonicIO framework based on the online bin-packing algorithm, to allow for efficient utilization of resources. Based on a real world use case from large-scale microscopy pipelines, we compare results of the new system to Spark's auto-scaling mechanism.
On the Impact of Phase Shifting Designs on IRS-NOMA
Venue: arXiv cs.IT 2020
Year: 2020

In this letter, the impact of two phase shifting designs, namely random phase shifting and coherent phase shifting, on the performance of intelligent reflecting surface (IRS) assisted non-orthogonal multiple access (NOMA) is studied. Analytical results are developed to show that the two designs achieve different tradeoffs between reliability and complexity. Simulation results are provided to compare IRS-NOMA to conventional relaying and IRS assisted orthogonal multiple access, and also to verify the accuracy of the obtained analytical results.
AMR Similarity Metrics from Principles
Venue: arXiv cs.CL 2020
Year: 2020

Different metrics have been proposed to compare Abstract Meaning Representation (AMR) graphs. The canonical Smatch metric (Cai and Knight, 2013) aligns the variables of two graphs and assesses triple matches. The recent SemBleu metric (Song and Gildea, 2019) is based on the machine-translation metric Bleu (Papineni et al., 2002) and increases computational efficiency by ablating the variable-alignment. In this paper, i) we establish criteria that enable researchers to perform a principled assessment of metrics comparing meaning representations like AMR; ii) we undertake a thorough analysis of Smatch and SemBleu where we show that the latter exhibits some undesirable properties. For example, it does not conform to the identity of indiscernibles rule and introduces biases that are hard to control; iii) we propose a novel metric S$^2$match that is more benevolent to only very slight meaning deviations and targets the fulfilment of all established criteria. We assess its suitability and show its advantages over Smatch and SemBleu.
Examining the Benefits of Capsule Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Capsule networks are a recently developed class of neural networks that potentially address some of the deficiencies with traditional convolutional neural networks. By replacing the standard scalar activations with vectors, and by connecting the artificial neurons in a new way, capsule networks aim to be the next great development for computer vision applications. However, in order to determine whether these networks truly operate differently than traditional networks, one must look at the differences in the capsule features. To this end, we perform several analyses with the purpose of elucidating capsule features and determining whether they perform as described in the initial publication. First, we perform a deep visualization analysis to visually compare capsule features and convolutional neural network features. Then, we look at the ability for capsule features to encode information across the vector components and address what changes in the capsule architecture provides the most benefit. Finally, we look at how well the capsule features are able to encode instantiation parameters of class objects via visual transformations.
The Case for Bayesian Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

The key distinguishing property of a Bayesian approach is marginalization instead of optimization, not the prior, or Bayes rule. Bayesian inference is especially compelling for deep neural networks. (1) Neural networks are typically underspecified by the data, and can represent many different but high performing models corresponding to different settings of parameters, which is exactly when marginalization will make the biggest difference for both calibration and accuracy. (2) Deep ensembles have been mistaken as competing approaches to Bayesian methods, but can be seen as approximate Bayesian marginalization. (3) The structure of neural networks gives rise to a structured prior in function space, which reflects the inductive biases of neural networks that help them generalize. (4) The observed correlation between parameters in flat regions of the loss and a diversity of solutions that provide good generalization is further conducive to Bayesian marginalization, as flat regions occupy a large volume in a high dimensional space, and each different solution will make a good contribution to a Bayesian model average. (5) Recent practical advances for Bayesian deep learning provide improvements in accuracy and calibration compared to standard training, while retaining scalability.
Partial Updates: Losing Information for Freshness
Venue: arXiv cs.IT 2020
Year: 2020

We consider an information updating system where a source produces updates as requested by a transmitter. The transmitter further processes these updates in order to generate $partial$ $updates$, which have smaller information compared to the original updates, to be sent to a receiver. We study the problem of generating partial updates, and finding their corresponding real-valued codeword lengths, in order to minimize the average age experienced by the receiver, while maintaining a desired level of mutual information between the original and partial updates. This problem is NP hard. We relax the problem and develop an alternating minimization based iterative algorithm that generates a pmf for the partial updates, and the corresponding age-optimal real-valued codeword length for each update. We observe that there is a tradeoff between the attained average age and the mutual information between the original and partial updates.
Infodemiological Study Using Google Trends on Coronavirus Epidemic in Wuhan, China
Venue: arXiv cs.IR 2020
Year: 2020

The recent emergence of a new coronavirus (COVID-19) has gained a high cover in public media and worldwide news. The virus has caused a viral pneumonia in tens of thousands of people in Wuhan, a central city of China. This short paper gives a brief introduction on how the demand for information on this new epidemic is reported through Google Trends. The reported period is 31 December 2020 to 20 March 2020. The authors draw conclusions on current infodemiological data on COVID-19 using three main search keywords: coronavirus, SARS and MERS. Two approaches are set. First is the worldwide perspective, second - the Chinese one, which reveals that in China this disease in the first days was more often referred to SARS then to general coronaviruses, whereas worldwide, since the beginning, it is more often referred to coronaviruses.