OpenRaiser/Intern-Atlas huggingface dataset:
Integrals over Gaussians under Linear Domain Constraints
Venue: arXiv cs.LG 2020
Year: 2020

Integrals of linearly constrained multivariate Gaussian densities are a frequent problem in machine learning and statistics, arising in tasks like generalized linear models and Bayesian optimization. Yet they are notoriously hard to compute, and to further complicate matters, the numerical values of such integrals may be very small. We present an efficient black-box algorithm that exploits geometry for the estimation of integrals over a small, truncated Gaussian volume, and to simulate therefrom. Our algorithm uses the Holmes-Diaconis-Ross (HDR) method combined with an analytic version of elliptical slice sampling (ESS). Adapted to the linear setting, ESS allows for rejection-free sampling, because intersections of ellipses and domain boundaries have closed-form solutions. The key idea of HDR is to decompose the integral into easier-to-compute conditional probabilities by using a sequence of nested domains. Remarkably, it allows for direct computation of the logarithm of the integral value and thus enables the computation of extremely small probability masses. We demonstrate the effectiveness of our tailored combination of HDR and ESS on high-dimensional integrals and on entropy search for Bayesian optimization.
A Decision-Theoretic Approach for Model Interpretability in Bayesian Framework
Venue: arXiv cs.LG 2020
Year: 2020

A salient approach to interpretable machine learning is to restrict modeling to simple models. In the Bayesian framework, this can be pursued by restricting the model structure and prior to favor interpretable models. Fundamentally, however, interpretability is about users' preferences, not the data generation mechanism; it is more natural to formulate interpretability as a utility function. In this work, we propose an interpretability utility, which explicates the trade-off between explanation fidelity and interpretability in the Bayesian framework. The method consists of two steps. First, a reference model, possibly a black-box Bayesian predictive model which does not compromise accuracy, is fitted to the training data. Second, a proxy model from an interpretable model family that best mimics the predictive behaviour of the reference model is found by optimizing the interpretability utility function. The approach is model agnostic -- neither the interpretable model nor the reference model are restricted to a certain class of models -- and the optimization problem can be solved using standard tools. Through experiments on real-word data sets, using decision trees as interpretable models and Bayesian additive regression models as reference models, we show that for the same level of interpretability, our approach generates more accurate models than the alternative of restricting the prior. We also propose a systematic way to measure stability of interpretabile models constructed by different interpretability approaches and show that our proposed approach generates more stable models.
On Well-Founded and Recursive Coalgebras
Venue: arXiv cs.LO 2020
Year: 2020

This paper studies fundamental questions concerning category-theoretic models of induction and recursion. We are concerned with the relationship between well-founded and recursive coalgebras for an endofunctor. For monomorphism preserving endofunctors on complete and well-powered categories every coalgebra has a well-founded part, and we provide a new, shorter proof that this is the coreflection in the category of all well-founded coalgebras. We present a new more general proof of Taylor's General Recursion Theorem that every well-founded coalgebra is recursive, and we study under which hypothesis the converse holds. In addition, we present a new equivalent characterization of well-foundedness: a coalgebra is well-founded iff it admits a coalgebra-to-algebra morphism to the initial algebra.
Improving Vehicle Re-Identification using CNN Latent Spaces: Metrics Comparison and Track-to-track Extension
Venue: arXiv cs.CV 2020
Year: 2020

This paper addresses the problem of vehicle re-identification using distance comparison of images in CNN latent spaces. Firstly, we study the impact of the distance metrics, comparing performances obtained with different metrics: the minimal Euclidean distance (MED), the minimal cosine distance (MCD), and the residue of the sparse coding reconstruction (RSCR). These metrics are applied using features extracted from five different CNN architectures, namely ResNet18, AlexNet, VGG16, InceptionV3 and DenseNet201. We use the specific vehicle re-identification dataset VeRi to fine-tune these CNNs and evaluate results. In overall, independently of the CNN used, MCD outperforms MED, commonly used in the literature. These results are confirmed on other vehicle retrieval datasets. Secondly, we extend the state-of-the-art image-to-track process (I2TP) to a track-to-track process (T2TP). The three distance metrics are extended to measure distance between tracks, enabling T2TP. We compared T2TP with I2TP using the same CNN models. Results show that T2TP outperforms I2TP for MCD and RSCR. T2TP combining DenseNet201 and MCD-based metrics exhibits the best performances, outperforming the state-of-the-art I2TP-based models. Finally, experiments highlight two main results: i) the impact of metric choice in vehicle re-identification, and ii) T2TP improves the performances compared to I2TP, especially when coupled with MCD-based metrics.
On Predictive Information in RNNs
Venue: arXiv cs.LG 2020
Year: 2020

Certain biological neurons demonstrate a remarkable capability to optimally compress the history of sensory inputs while being maximally informative about the future. In this work, we investigate if the same can be said of artificial neurons in recurrent neural networks (RNNs) trained with maximum likelihood. Empirically, we find that RNNs are suboptimal in the information plane. Instead of optimally compressing past information, they extract additional information that is not relevant for predicting the future. We show that constraining past information by injecting noise into the hidden state can improve RNNs in several ways: optimality in the predictive information plane, sample quality, heldout likelihood, and downstream classification performance.
The Effects of Information Overload on Online Conversation Dynamics
Venue: arXiv cs.SI 2020
Year: 2020

The inhibiting effects of information overload on the behavior of online social media users, can affect the population-level characteristics of information dissemination through online conversations. We introduce a mechanistic, agent-based model of information overload and investigate the effects of information overload threshold and rate of information loss on observed online phenomena. We find that conversation volume and participation are lowest under high information overload thresholds and mid-range rates of information loss. Calibrating the model to user responsiveness data on Twitter, we replicate and explain several observed phenomena: 1) Responsiveness is sensitive to information overload threshold at high rates of information loss; 2) Information overload threshold and rate of information loss are Pareto-optimal and users may experience overload at inflows exceeding 30 notifications per hour; 3) Local abundance of small cascades of modest global popularity and local scarcity of larger cascades of high global popularity explains why overloaded users receive, but do not respond to large, highly popular cascades; 4) Users typically work with 7 notifications per hour; 5) Over-exposure to information can suppress the likelihood of response by overloading users, contrary to analogies to biologically-inspired viral spread. Reconceptualizing information spread with the mechanisms of information overload creates a richer representation of online conversation dynamics, enabling a deeper understanding of how (dis)information is transmitted over social media.
The Security Reference Architecture for Blockchains: Towards a Standardized Model for Studying Vulnerabilities, Threats, and Defenses
Venue: arXiv cs.CR 2020
Year: 2020

Blockchains are distributed systems, in which security is a critical factor for their success. However, despite their increasing popularity and adoption, there is a lack of standardized models that study blockchain-related security threats. To fill this gap, the main focus of our work is to systematize and extend the knowledge about the security and privacy aspects of blockchains and contribute to the standardization of this domain. We propose the security reference architecture (SRA) for blockchains, which adopts a stacked model (similar to the ISO/OSI) describing the nature and hierarchy of various security and privacy aspects. The SRA contains four layers: (1) the network layer, (2) the consensus layer, (3) the replicated state machine layer, and (4) the application layer. At each of these layers, we identify known security threats, their origin, and countermeasures, while we also analyze several cross-layer dependencies. Next, to enable better reasoning about security aspects of blockchains by the practitioners, we propose a blockchain-specific version of the threat-risk assessment standard ISO/IEC 15408 by embedding the stacked model into this standard. Finally, we provide designers of blockchain platforms and applications with a design methodology following the model of SRA and its hierarchy.
Simplification of networks via conservation of path diversity and minimisation of the search information
Venue: arXiv cs.SI 2020
Year: 2020

Alternative paths in a network play an important role in its functionality as they can maintain the information flow under node/link failures. In this paper we explore the navigation of a network taking into account the alternative paths and in particular how can we describe this navigation in a concise way. Our approach is to simplify the network by aggregating into groups the nodes that do not contribute to alternative paths. We refer to these groups as super-nodes, and describe the post-aggregation network with super-nodes as the skeleton network. We present a method to describe with the least amount of information the paths in the super--nodes and skeleton network. Applying our method to several real networks we observed that there is scaling behaviour between the information required to describe all the paths in a network and the minimal information to describe the paths of its skeleton. We show how from this scaling we can evaluate the information of the paths for large networks with less computational cost.
Fast and Automatic Periacetabular Osteotomy Fragment Pose Estimation Using Intraoperatively Implanted Fiducials and Single-View Fluoroscopy
Venue: arXiv cs.CV 2020
Year: 2020

Accurate and consistent mental interpretation of fluoroscopy to determine the position and orientation of acetabular bone fragments in 3D space is difficult. We propose a computer assisted approach that uses a single fluoroscopic view and quickly reports the pose of an acetabular fragment without any user input or initialization. Intraoperatively, but prior to any osteotomies, two constellations of metallic ball-bearings (BBs) are injected into the wing of a patient's ilium and lateral superior pubic ramus. One constellation is located on the expected acetabular fragment, and the other is located on the remaining, larger, pelvis fragment. The 3D locations of each BB are reconstructed using three fluoroscopic views and 2D/3D registrations to a preoperative CT scan of the pelvis. The relative pose of the fragment is established by estimating the movement of the two BB constellations using a single fluoroscopic view taken after osteotomy and fragment relocation. BB detection and inter-view correspondences are automatically computed throughout the processing pipeline. The proposed method was evaluated on a multitude of fluoroscopic images collected from six cadaveric surgeries performed bilaterally on three specimens. Mean fragment rotation error was 2.4 +/- 1.0 degrees, mean translation error was 2.1 +/- 0.6 mm, and mean 3D lateral center edge angle error was 1.0 +/- 0.5 degrees. The average runtime of the single-view pose estimation was 0.7 +/- 0.2 seconds. The proposed method demonstrates accuracy similar to other state of the art systems which require optical tracking systems or multiple-view 2D/3D registrations with manual input. The errors reported on fragment poses and lateral center edge angles are within the margins required for accurate intraoperative evaluation of femoral head coverage.
Using Markov Decision Process to Model Deception for Robotic and Interactive Game Applications
Venue: arXiv cs.HC 2020
Year: 2020

This paper investigates deception in the context of motion using a simulated mobile robot. We analyze some previously designed deceptive strategies on a mobile robot simulator. We then present a novel approach to adaptively choose target-oriented deceptive trajectories to deceive humans for multiple interactions. Additionally, we propose a new metric to evaluate deception on data collected from the users when interacting with the mobile robot simulator. We performed a user study to test our proposed adaptive deceptive algorithm, which shows that our algorithm deceives humans even for multiple interactions and it is more effective than random choice of deceptive strategies.
Parameterized Coloring Problems on Threshold Graphs
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we study several coloring problems on graphs from the viewpoint of parameterized complexity. We show that Precoloring Extension is fixed-parameter tractable (FPT) parameterized by distance to clique and Equitable Coloring is FPT parameterized by the distance to threshold graphs. We also study the List k-Coloring and show that the problem is NP-complete on split graphs and it is FPT parameterized by solution size on split graphs.
Resolution of the Burrows-Wheeler Transform Conjecture
Venue: arXiv cs.DS 2020
Year: 2020

The Burrows-Wheeler Transform (BWT) is an invertible text transformation that permutes symbols of a text according to the lexicographical order of its suffixes. BWT is the main component of popular lossless compression programs (such as bzip2) as well as recent powerful compressed indexes (such as $r$-index [Gagie et al., J. ACM, 2020]), central in modern bioinformatics. The compression ratio of BWT is quantified by the number $r$ of equal-letter runs. Despite the practical significance of BWT, no non-trivial bound on the value of $r$ is known. This is in contrast to nearly all other known compression methods, whose sizes have been shown to be either always within a ${\rm polylog}\,n$ factor (where $n$ is the length of text) from $z$, the size of Lempel-Ziv (LZ77) parsing of the text, or significantly larger in the worst case (by a $n^{\varepsilon}$ factor for $\varepsilon > 0$). In this paper, we show that $r = \mathcal{O}(z \log^2n)$ holds for every text. This result has numerous implications for text indexing and data compression; for example: (1) it proves that many results related to BWT automatically apply to methods based on LZ77, e.g., it is possible to obtain functionality of the suffix tree in $\mathcal{O}(z\,{\rm polylog}\,n)$ space; (2) it shows that many text processing tasks can be solved in the optimal time assuming the text is compressible using LZ77 by a sufficiently large ${\rm polylog}\,n$ factor; (3) it implies the first non-trivial relation between the number of runs in the BWT of the text and its reverse. In addition, we provide an $\mathcal{O}(z\,{\rm polylog}\,n)$-time algorithm converting the LZ77 parsing into the run-length compressed BWT. To achieve this, we develop a number of new data structures and techniques of independent interest.
A Comparative Study of Multilateration Methods for Single-Source Localization in Distributed Audio
Venue: arXiv cs.SD 2020
Year: 2020

In this article we analyze the state-of-the-art in multilateration - the family of localization methods enabled by the range difference observations. These methods are computationally efficient, signal-independent, and flexible with regards to the number of sensing nodes and their spatial arrangement. However, the multilateration problem does not admit a closed-form solution in the general case, and the localization performance is conditioned on the accuracy of range difference estimates. For that reason, we consider a simplified use case where multiple distributed microphones capture the signal coming from a near field sound source, and discuss their robustness to the estimation errors. In addition to surveying the relevant bibliography, we present the results of a small-scale benchmark of few "mainstream" multilateration algorithms, based on an in-house Room Impulse Response dataset.
Reciprocal Collision Avoidance for General Nonlinear Agents using Reinforcement Learning
Venue: arXiv cs.RO 2020
Year: 2020

Finding feasible and collision-free paths for multiple nonlinear agents is challenging in the decentralized scenarios due to limited available information of other agents and complex dynamics constraints. In this paper, we propose a fast multi-agent collision avoidance algorithm for general nonlinear agents with continuous action space, where each agent observes only positions and velocities of nearby agents. To reduce online computation, we first decompose the multi-agent scenario and solve a two agents collision avoidance problem using reinforcement learning (RL). When extending the trained policy to a multi-agent problem, safety is ensured by introducing the optimal reciprocal collision avoidance (ORCA) as linear constraints and the overall collision avoidance action could be found through simple convex optimization. Most existing RL-based multi-agent collision avoidance algorithms rely on the direct control of agent velocities. In sharp contrasts, our approach is applicable to general nonlinear agents. Realistic simulations based on nonlinear bicycle agent models are performed with various challenging scenarios, indicating a competitive performance of the proposed method in avoiding collisions, congestion and deadlock with smooth trajectories.
Word-level Deep Sign Language Recognition from Video: A New Large-scale Dataset and Methods Comparison
Venue: arXiv cs.CV 2020
Year: 2020

Vision-based sign language recognition aims at helping deaf people to communicate with others. However, most existing sign language datasets are limited to a small number of words. Due to the limited vocabulary size, models learned from those datasets cannot be applied in practice. In this paper, we introduce a new large-scale Word-Level American Sign Language (WLASL) video dataset, containing more than 2000 words performed by over 100 signers. This dataset will be made publicly available to the research community. To our knowledge, it is by far the largest public ASL dataset to facilitate word-level sign recognition research. Based on this new large-scale dataset, we are able to experiment with several deep learning methods for word-level sign recognition and evaluate their performances in large scale scenarios. Specifically we implement and compare two different models,i.e., (i) holistic visual appearance-based approach, and (ii) 2D human pose based approach. Both models are valuable baselines that will benefit the community for method benchmarking. Moreover, we also propose a novel pose-based temporal graph convolution networks (Pose-TGCN) that models spatial and temporal dependencies in human pose trajectories simultaneously, which has further boosted the performance of the pose-based method. Our results show that pose-based and appearance-based models achieve comparable performances up to 66% at top-10 accuracy on 2,000 words/glosses, demonstrating the validity and challenges of our dataset. Our dataset and baseline deep models are available at \url{https://dxli94.github.io/WLASL/}.
Multi-label Co-regularization for Semi-supervised Facial Action Unit Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Facial action units (AUs) recognition is essential for emotion analysis and has been widely applied in mental state analysis. Existing work on AU recognition usually requires big face dataset with AU labels; however, manual AU annotation requires expertise and can be time-consuming. In this work, we propose a semi-supervised approach for AU recognition utilizing a large number of web face images without AU labels and a relatively small face dataset with AU annotations inspired by the co-training methods. Unlike traditional co-training methods that require provided multi-view features and model re-training, we propose a novel co-training method, namely multi-label co-regularization, for semi-supervised facial AU recognition. Two deep neural networks are utilized to generate multi-view features for both labeled and unlabeled face images, and a multi-view loss is designed to enforce the two feature generators to get conditional independent representations. In order to constrain the prediction consistency of the two views, we further propose a multi-label co-regularization loss by minimizing the distance of the predicted AU probability distributions of two views. In addition, prior knowledge of the relationship between individual AUs is embedded through a graph convolutional network (GCN) for exploiting useful information from the big unlabeled dataset. Experiments on several benchmarks show that the proposed approach can effectively leverage large datasets of face images without AU labels to improve the AU recognition accuracy and outperform the state-of-the-art semi-supervised AU recognition methods.
Predicting In-game Actions from Interviews of NBA Players
Venue: arXiv cs.CL 2020
Year: 2020

Sports competitions are widely researched in computer and social science, with the goal of understanding how players act under uncertainty. While there is an abundance of computational work on player metrics prediction based on past performance, very few attempts to incorporate out-of-game signals have been made. Specifically, it was previously unclear whether linguistic signals gathered from players' interviews can add information which does not appear in performance metrics. To bridge that gap, we define text classification tasks of predicting deviations from mean in NBA players' in-game actions, which are associated with strategic choices, player behavior and risk, using their choice of language prior to the game. We collected a dataset of transcripts from key NBA players' pre-game interviews and their in-game performance metrics, totalling in 5,226 interview-metric pairs. We design neural models for players' action prediction based on increasingly more complex aspects of the language signals in their open-ended interviews. Our models can make their predictions based on the textual signal alone, or on a combination with signals from past-performance metrics. Our text-based models outperform strong baselines trained on performance metrics only, demonstrating the importance of language usage for action prediction. Moreover, the models that employ both textual input and past-performance metrics produced the best results. Finally, as neural networks are notoriously difficult to interpret, we propose a method for gaining further insight into what our models have learned. Particularly, we present an LDA-based analysis, where we interpret model predictions in terms of correlated topics. We find that our best performing textual model is most associated with topics that are intuitively related to each prediction task and that better models yield higher correlation with more informative topics.