OpenRaiser/Intern-Atlas huggingface dataset:
On the Usefulness of Deep Ensemble Diversity for Out-of-Distribution Detection
Venue: arXiv cs.LG 2022
Year: 2022

The ability to detect Out-of-Distribution (OOD) data is important in safety-critical applications of deep learning. The aim is to separate In-Distribution (ID) data drawn from the training distribution from OOD data using a measure of uncertainty extracted from a deep neural network. Deep Ensembles are a well-established method of improving the quality of uncertainty estimates produced by deep neural networks, and have been shown to have superior OOD detection performance compared to single models. An existing intuition in the literature is that the diversity of Deep Ensemble predictions indicates distributional shift, and so measures of diversity such as Mutual Information (MI) should be used for OOD detection. We show experimentally that this intuition is not valid on ImageNet-scale OOD detection -- using MI leads to 30-40% worse %FPR@95 compared to single-model entropy on some OOD datasets. We suggest an alternative explanation for Deep Ensembles' better OOD detection performance -- OOD detection is binary classification and we are ensembling diverse classifiers. As such we show that practically, even better OOD detection performance can be achieved for Deep Ensembles by averaging task-specific detection scores such as Energy over the ensemble.
mAPN: Modeling, Analysis, and Exploration of Algorithmic and Parallelism Adaptivity
Venue: arXiv cs.DC 2022
Year: 2022

Using parallel embedded systems these days is increasing. They are getting more complex due to integrating multiple functionalities in one application or running numerous ones concurrently. This concerns a wide range of applications, including streaming applications, commonly used in embedded systems. These applications must implement adaptable and reliable algorithms to deliver the required performance under varying circumstances (e.g., running applications on the platform, input data, platform variety, etc.). Given the complexity of streaming applications, target systems, and adaptivity requirements, designing such systems with traditional programming models is daunting. This is why model-based strategies with an appropriate Model of Computation (MoC) have long been studied for embedded system design. This work provides algorithmic adaptivity on top of parallelism for dynamic dataflow to express larger sets of variants. We present a multi-Alternative Process Network (mAPN), a high-level abstract representation in which several variants of the same application coexist in the same graph expressing different implementations. We introduce mAPN properties and its formalism to describe various local implementation alternatives. Furthermore, mAPNs are enriched with metadata to Provide the alternatives with quantitative annotations in terms of a specific metric. To help the user analyze the rich space of variants, we propose a methodology to extract feasible variants under user and hardware constraints. At the core of the methodology is an algorithm for computing global metrics of an execution of different alternatives from a compact mAPN specification. We validate our approach by exploring several possible variants created for the Automatic Subtitling Application (ASA) on two hardware platforms.
Improved Algorithms for Recognizing Perfect Graphs and Finding Shortest Odd and Even Holes
Venue: arXiv cs.DS 2022
Year: 2022

Various classes of induced subgraphs are involved in the deepest results of graph theory and graph algorithms. A prominent example concerns the {\em perfection} of $G$ that the chromatic number of each induced subgraph $H$ of $G$ equals the clique number of $H$. The seminal Strong Perfect Graph Theorem confirms that the perfection of $G$ can be determined by detecting odd holes in $G$ and its complement. Chudnovsky et al. show in 2005 an $O(n^9)$ algorithm for recognizing perfect graphs, which can be implemented to run in $O(n^{6+ω})$ time for the exponent $ω<2.373$ of square-matrix multiplication. We show the following improved algorithms. 1. The tractability of detecting odd holes was open for decades until the major breakthrough of Chudnovsky et al. in 2020. Their $O(n^9)$ algorithm is later implemented by Lai et al. to run in $O(n^8)$ time, leading to the best formerly known algorithm for recognizing perfect graphs. Our first result is an $O(n^7)$ algorithm for detecting odd holes, implying an $O(n^7)$ algorithm for recognizing perfect graphs. 2. Chudnovsky et al. extend in 2021 the $O(n^9)$ algorithms for detecting odd holes (2020) and recognizing perfect graphs (2005) into the first polynomial algorithm for obtaining a shortest odd hole, which runs in $O(n^{14})$ time. We reduce the time for finding a shortest odd hole to $O(n^{13})$. 3. Conforti et al. show in 1997 the first polynomial algorithm for detecting even holes, running in about $O(n^{40})$ time. It then takes a line of intensive efforts in the literature to bring down the complexity to $O(n^{31})$, $O(n^{19})$, $O(n^{11})$, and finally $O(n^9)$. On the other hand, the tractability of finding a shortest even hole has been open for 16 years until the very recent $O(n^{31})$ algorithm of Cheong and Lu in 2022. We improve the time of finding a shortest even hole to $O(n^{23})$.
Fixed Points and Noetherian Topologies
Venue: arXiv cs.LO 2022
Year: 2022

This paper provides a canonical construction of a Noetherian least fixed point topology. While such least fixed point are not Noetherian in general, we prove that under a mild assumption, one can use a topological minimal bad sequence argument to prove that they are. We then apply this fixed point theorem to rebuild known Noetherian topologies with a uniform proof. In the case of spaces that are defined inductively (such as finite words and finite trees), we provide a uniform definition of a divisibility topology using our fixed point theorem. We then prove that the divisibility topology is a generalisation of the divisibility preorder introduced by Hasegawa in the case of well-quasi-orders.
ARShopping: In-Store Shopping Decision Support Through Augmented Reality and Immersive Visualization
Venue: arXiv cs.HC 2022
Year: 2022

Online shopping gives customers boundless options to choose from, backed by extensive product details and customer reviews, all from the comfort of home; yet, no amount of detailed, online information can outweigh the instant gratification and hands-on understanding of a product that is provided by physical stores. However, making purchasing decisions in physical stores can be challenging due to a large number of similar alternatives and limited accessibility of the relevant product information (e.g., features, ratings, and reviews). In this work, we present ARShopping: a web-based prototype to visually communicate detailed product information from an online setting on portable smart devices (e.g., phones, tablets, glasses), within the physical space at the point of purchase. This prototype uses augmented reality (AR) to identify products and display detailed information to help consumers make purchasing decisions that fulfill their needs while decreasing the decision-making time. In particular, we use a data fusion algorithm to improve the precision of the product detection; we then integrate AR visualizations into the scene to facilitate comparisons across multiple products and features. We designed our prototype based on interviews with 14 participants to better understand the utility and ease of use of the prototype.
Distributed Backlog-Aware D2D Communication for Heterogeneous IIoT Applications
Venue: arXiv cs.NI 2022
Year: 2022

Delay and Age-of-Information (AoI) are two crucial performance metrics for emerging time-sensitive applications in Industrial Internet of Things (IIoT). In order to achieve optimal performance, studying the inherent interplay between these two parameters in non-trivial task. In this work, we consider a Device-to-Device (D2D)-based heterogeneous IIoT network that supports two types of traffic flows, namely AoI-orientated. First, we introduce a distributed backlog-aware random access protocol that allows the AoI-orientated nodes to opportunistically access the channel based on the queue occupancy of the delay-oriented node. Then, we develop an analytical framework to evaluate the average delay and the average AoI, and formulate an optimization problem to minimize the AoI under a given delay constraint. Finally, we provide numerical results to demonstrate the impact of different network parameters on the performance in terms of the average delay and the average AoI. We also give the numerical solutions of the optimal parameters that minimize the AoI subject to a delay constraint.
FLIP: A Utility Preserving Privacy Mechanism for Time Series
Venue: arXiv cs.CR 2022
Year: 2022

Guaranteeing privacy in released data is an important goal for data-producing agencies. There has been extensive research on developing suitable privacy mechanisms in recent years. Particularly notable is the idea of noise addition with the guarantee of differential privacy. There are, however, concerns about compromising data utility when very stringent privacy mechanisms are applied. Such compromises can be quite stark in correlated data, such as time series data. Adding white noise to a stochastic process may significantly change the correlation structure, a facet of the process that is essential to optimal prediction. We propose the use of all-pass filtering as a privacy mechanism for regularly sampled time series data, showing that this procedure preserves utility while also providing sufficient privacy guarantees to entity-level time series.
Bootstrap State Representation using Style Transfer for Better Generalization in Deep Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

Deep Reinforcement Learning (RL) agents often overfit the training environment, leading to poor generalization performance. In this paper, we propose Thinker, a bootstrapping method to remove adversarial effects of confounding features from the observation in an unsupervised way, and thus, it improves RL agents' generalization. Thinker first clusters experience trajectories into several clusters. These trajectories are then bootstrapped by applying a style transfer generator, which translates the trajectories from one cluster's style to another while maintaining the content of the observations. The bootstrapped trajectories are then used for policy learning. Thinker has wide applicability among many RL settings. Experimental results reveal that Thinker leads to better generalization capability in the Procgen benchmark environments compared to base algorithms and several data augmentation techniques.
Curve Simplification and Clustering under Fréchet Distance
Venue: arXiv cs.CG 2022
Year: 2022

We present new approximation results on curve simplification and clustering under Fréchet distance. Let $T = \{τ_i : i \in [n] \}$ be polygonal curves in $R^d$ of $m$ vertices each. Let $l$ be any integer from $[m]$. We study a generalized curve simplification problem: given error bounds $δ_i > 0$ for $i \in [n]$, find a curve $σ$ of at most $l$ vertices such that $d_F(σ,τ_i) \le δ_i$ for $i \in [n]$. We present an algorithm that returns a null output or a curve $σ$ of at most $l$ vertices such that $d_F(σ,τ_i) \le δ_i + εδ_{\max}$ for $i \in [n]$, where $δ_{\max} = \max_{i \in [n]} δ_i$. If the output is null, there is no curve of at most $l$ vertices within a Fréchet distance of $δ_i$ from $τ_i$ for $i \in [n]$. The running time is $\tilde{O}\bigl(n^{O(l)} m^{O(l^2)} (dl/ε)^{O(dl)}\bigr)$. This algorithm yields the first polynomial-time bicriteria approximation scheme to simplify a curve $τ$ to another curve $σ$, where the vertices of $σ$ can be anywhere in $R^d$, so that $d_F(σ,τ) \le (1+ε)δ$ and $|σ| \le (1+α) \min\{|c| : d_F(c,τ) \le δ\}$ for any given $δ> 0$ and any fixed $α, ε\in (0,1)$. The running time is $\tilde{O}\bigl(m^{O(1/α)} (d/(αε))^{O(d/α)}\bigr)$. By combining our technique with some previous results in the literature, we obtain an approximation algorithm for $(k,l)$-median clustering. Given $T$, it computes a set $Σ$ of $k$ curves, each of $l$ vertices, such that $\sum_{i \in [n]} \min_{σ\in Σ} d_F(σ,τ_i)$ is within a factor $1+ε$ of the optimum with probability at least $1-μ$ for any given $μ, ε\in (0,1)$. The running time is $\tilde{O}\bigl(n m^{O(kl^2)} μ^{-O(kl)} (dkl/ε)^{O((dkl/ε)\log(1/μ))}\bigr)$.
Dynamic Bipedal Maneuvers through Sim-to-Real Reinforcement Learning
Venue: arXiv cs.RO 2022
Year: 2022

For legged robots to match the athletic capabilities of humans and animals, they must not only produce robust periodic walking and running, but also seamlessly switch between nominal locomotion gaits and more specialized transient maneuvers. Despite recent advancements in controls of bipedal robots, there has been little focus on producing highly dynamic behaviors. Recent work utilizing reinforcement learning to produce policies for control of legged robots have demonstrated success in producing robust walking behaviors. However, these learned policies have difficulty expressing a multitude of different behaviors on a single network. Inspired by conventional optimization-based control techniques for legged robots, this work applies a recurrent policy to execute four-step, 90 degree turns trained using reference data generated from optimized single rigid body model trajectories. We present a novel training framework using epilogue terminal rewards for learning specific behaviors from pre-computed trajectory data and demonstrate a successful transfer to hardware on the bipedal robot Cassie.
Multiscale Causal Structure Learning
Venue: arXiv cs.LG 2022
Year: 2022

The inference of causal structures from observed data plays a key role in unveiling the underlying dynamics of the system. This paper exposes a novel method, named Multiscale-Causal Structure Learning (MS-CASTLE), to estimate the structure of linear causal relationships occurring at different time scales. Differently from existing approaches, MS-CASTLE takes explicitly into account instantaneous and lagged inter-relations between multiple time series, represented at different scales, hinging on stationary wavelet transform and non-convex optimization. MS-CASTLE incorporates, as a special case, a single-scale version named SS-CASTLE, which compares favorably in terms of computational efficiency, performance and robustness with respect to the state of the art onto synthetic data. We used MS-CASTLE to study the multiscale causal structure of the risk of 15 global equity markets, during covid-19 pandemic, illustrating how MS-CASTLE can extract meaningful information thanks to its multiscale analysis, outperforming SS-CASTLE. We found that the most persistent and strongest interactions occur at mid-term time resolutions. Moreover, we identified the stock markets that drive the risk during the considered period: Brazil, Canada and Italy. The proposed approach can be exploited by financial investors who, depending to their investment horizon, can manage the risk within equity portfolios from a causal perspective.
A Nearly Tight Analysis of Greedy k-means++
Venue: arXiv cs.DS 2022
Year: 2022

The famous $k$-means++ algorithm of Arthur and Vassilvitskii [SODA 2007] is the most popular way of solving the $k$-means problem in practice. The algorithm is very simple: it samples the first center uniformly at random and each of the following $k-1$ centers is then always sampled proportional to its squared distance to the closest center so far. Afterward, Lloyd's iterative algorithm is run. The $k$-means++ algorithm is known to return a $Θ(\log k)$ approximate solution in expectation. In their seminal work, Arthur and Vassilvitskii [SODA 2007] asked about the guarantees for its following \emph{greedy} variant: in every step, we sample $\ell$ candidate centers instead of one and then pick the one that minimizes the new cost. This is also how $k$-means++ is implemented in e.g. the popular Scikit-learn library [Pedregosa et al.; JMLR 2011]. We present nearly matching lower and upper bounds for the greedy $k$-means++: We prove that it is an $O(\ell^3 \log^3 k)$-approximation algorithm. On the other hand, we prove a lower bound of $Ω(\ell^3 \log^3 k / \log^2(\ell\log k))$. Previously, only an $Ω(\ell \log k)$ lower bound was known [Bhattacharya, Eube, Röglin, Schmidt; ESA 2020] and there was no known upper bound.
A Comprehensive Vision on Cloud Computing Environment: Emerging Challenges and Future Research Directions
Venue: arXiv cs.DC 2022
Year: 2022

Cloud computing has become the backbone of the computing industry and offers subscription-based on-demand services. Through virtualization, which produces a virtual instance of a computer system running in an abstracted hardware layer, it has made it possible for us to share resources among many users. Contrary to early distributed computing models, it guarantees limitless computing resources through its expansive cloud datacenters, and it has been immensely popular in recent years because to its constantly expanding infrastructure, user base, and hosted data volume. These datacenters enormous and sophisticated workloads present a number of problems, including issues with resource use, power consumption, scalability, operational expense, security and many more. In this context, the article provides a comprehensive overview of the most prevalent problems with sharing and communication in organizations of all sizes. There is discussion of a taxonomy of security, load balancing, and the main difficulties encountered in protecting sensitive data. A complete examination of current state-of-the-art contributions, resource management analysis methodologies, load balancing solutions, empowering heuristics, and multi-objective learning-based approaches are required. In its final section, the paper examines, reviews, and suggests future research directions in the area of secure VM placements.
A Parallel Privacy-Preserving Shortest Path Protocol from a Path Algebra Problem
Venue: arXiv cs.CR 2022
Year: 2022

In this paper, we present a secure multiparty computation (SMC) protocol for single-source shortest distances (SSSD) in undirected graphs, where the location of edges is public, but their length is private. The protocol works in the Arithmetic Black Box (ABB) model on top of the separator tree of the graph, achieving good time complexity if the subgraphs of the graph have small separators (which is the case for e.g. planar graphs); the achievable parallelism is significantly higher than that of classical SSSD algorithms implemented on top of an ABB. We implement our protocol on top of the Sharemind MPC platform, and perform extensive benchmarking over different network environments. We compare our algorithm against the baseline picked from classical algorithms - privacy-preserving Bellman-Ford algorithm (with public edges).
Knowledge Guided Bidirectional Attention Network for Human-Object Interaction Detection
Venue: arXiv cs.CV 2022
Year: 2022

Human Object Interaction (HOI) detection is a challenging task that requires to distinguish the interaction between a human-object pair. Attention based relation parsing is a popular and effective strategy utilized in HOI. However, current methods execute relation parsing in a "bottom-up" manner. We argue that the independent use of the bottom-up parsing strategy in HOI is counter-intuitive and could lead to the diffusion of attention. Therefore, we introduce a novel knowledge-guided top-down attention into HOI, and propose to model the relation parsing as a "look and search" process: execute scene-context modeling (i.e. look), and then, given the knowledge of the target pair, search visual clues for the discrimination of the interaction between the pair. We implement the process via unifying the bottom-up and top-down attention in a single encoder-decoder based model. The experimental results show that our model achieves competitive performance on the V-COCO and HICO-DET datasets.
A tool for emulating neuromorphic architectures with memristive models and devices
Venue: arXiv cs.NE 2022
Year: 2022

Memristors have shown promising features for enhancing neuromorphic computing concepts and AI hardware accelerators. In this paper, we present a user-friendly software infrastructure that allows emulating a wide range of neuromorphic architectures with memristor models. This tool empowers studies that exploit memristors for online learning and online classification tasks, predicting memristor resistive state changes during the training process. The versatility of the tool is showcased through the capability for users to customise parameters in the employed memristor and neuronal models as well as the employed learning rules. This further allows users to validate concepts and their sensitivity across a wide range of parameters. We demonstrate the use of the tool via an MNIST classification task. Finally, we show how this tool can also be used to emulate the concepts under study in-silico with practical memristive devices via appropriate interfacing with commercially available characterisation tools.
No Grammar to Rule Them All: A Survey of JSON-style DSLs for Visualization
Venue: arXiv cs.HC 2022
Year: 2022

There has been substantial growth in the use of JSON-based grammars, as well as other standard data serialization languages, to create visualizations. Each of these grammars serves a purpose: some focus on particular computational tasks (such as animation), some are concerned with certain chart types (such as maps), and some target specific data domains (such as ML). Despite the prominence of this interface form, there has been little detailed analysis of the characteristics of these languages. In this study, we survey and analyze the design and implementation of 57 JSON-style DSLs for visualization. We analyze these languages supported by a collected corpus of examples for each DSL (consisting of 4395 instances) across a variety of axes organized into concerns related to domain, conceptual model, language relationships, affordances, and general practicalities. We identify tensions throughout these areas, such as between formal and colloquial specifications, among types of users, and within the composition of languages. Through this work, we seek to support language implementers by elucidating the choices, opportunities, and tradeoffs in visualization DSL design.
Distance-Geometric Graph Attention Network (DG-GAT) for 3D Molecular Geometry
Venue: arXiv cs.LG 2022
Year: 2022

Deep learning for molecular science has so far mainly focused on 2D molecular graphs. Recently, however, there has been work to extend it to 3D molecular geometry, due to its scientific significance and critical importance in real-world applications. The 3D distance-geometric graph representation (DG-GR) adopts a unified scheme (distance) for representing the geometry of 3D graphs. It is invariant to rotation and translation of the graph, and it reflects pair-wise node interactions and their generally local nature, particularly relevant for 3D molecular geometry. To facilitate the incorporation of 3D molecular geometry in deep learning for molecular science, we adopt the new graph attention network with dynamic attention (GATv2) for use with DG-GR and propose the 3D distance-geometric graph attention network (DG-GAT). GATv2 is a great fit for DG-GR since the attention can vary by node and by distance between nodes. Experimental results of DG-GAT for the ESOL and FreeSolv datasets show major improvement (31% and 38%, respectively) over those of the standard graph convolution network based on 2D molecular graphs. The same is true for the QM9 dataset. Our work demonstrates the utility and value of DG-GAT for deep learning based on 3D molecular geometry.