OpenRaiser/Intern-Atlas huggingface dataset:
Random Forests for Adaptive Nearest Neighbor Estimation of Information-Theoretic Quantities
Venue: arXiv cs.LG 2021
Year: 2021

Information-theoretic quantities, such as conditional entropy and mutual information, are critical data summaries for quantifying uncertainty. Current widely used approaches for computing such quantities rely on nearest neighbor methods and exhibit both strong performance and theoretical guarantees in certain simple scenarios. However, existing approaches fail in high-dimensional settings and when different features are measured on different scales.We propose decision forest-based adaptive nearest neighbor estimators and show that they are able to effectively estimate posterior probabilities, conditional entropies, and mutual information even in the aforementioned settings.We provide an extensive study of efficacy for classification and posterior probability estimation, and prove certain forest-based approaches to be consistent estimators of the true posteriors and derived information-theoretic quantities under certain assumptions. In a real-world connectome application, we quantify the uncertainty about neuron type given various cellular features in the Drosophila larva mushroom body, a key challenge for modern neuroscience.
A Sound Algorithm for Asynchronous Session Subtyping and its Implementation
Venue: arXiv cs.PL 2021
Year: 2021

Session types, types for structuring communication between endpoints in distributed systems, are recently being integrated into mainstream programming languages. In practice, a very important notion for dealing with such types is that of subtyping, since it allows for typing larger classes of system, where a program has not precisely the expected behaviour but a similar one. Unfortunately, recent work has shown that subtyping for session types in an asynchronous setting is undecidable. To cope with this negative result, the only approaches we are aware of either restrict the syntax of session types or limit communication (by considering forms of bounded asynchrony). Both approaches are too restrictive in practice, hence we proceed differently by presenting an algorithm for checking subtyping which is sound, but not complete (in some cases it terminates without returning a decisive verdict). The algorithm is based on a tree representation of the coinductive definition of asynchronous subtyping; this tree could be infinite, and the algorithm checks for the presence of finite witnesses of infinite successful subtrees. Furthermore, we provide a tool that implements our algorithm. We use this tool to test our algorithm on many examples that cannot be managed with the previous approaches, and to provide an empirical evaluation of the time and space cost of the algorithm.
BERTphone: Phonetically-Aware Encoder Representations for Utterance-Level Speaker and Language Recognition
Venue: arXiv cs.CL 2021
Year: 2021

We introduce BERTphone, a Transformer encoder trained on large speech corpora that outputs phonetically-aware contextual representation vectors that can be used for both speaker and language recognition. This is accomplished by training on two objectives: the first, inspired by adapting BERT to the continuous domain, involves masking spans of input frames and reconstructing the whole sequence for acoustic representation learning; the second, inspired by the success of bottleneck features from ASR, is a sequence-level CTC loss applied to phoneme labels for phonetic representation learning. We pretrain two BERTphone models (one on Fisher and one on TED-LIUM) and use them as feature extractors into x-vector-style DNNs for both tasks. We attain a state-of-the-art $C_{\text{avg}}$ of 6.16 on the challenging LRE07 3sec closed-set language recognition task. On Fisher and VoxCeleb speaker recognition tasks, we see an 18% relative reduction in speaker EER when training on BERTphone vectors instead of MFCCs. In general, BERTphone outperforms previous phonetic pretraining approaches on the same data. We release our code and models at https://github.com/awslabs/speech-representations.
Discourse Understanding and Factual Consistency in Abstractive Summarization
Venue: arXiv cs.CL 2021
Year: 2021

We introduce a general framework for abstractive summarization with factual consistency and distinct modeling of the narrative flow in an output summary. Our work addresses current limitations of models for abstractive summarization that often hallucinate information or generate summaries with coherence issues. To generate abstractive summaries with factual consistency and narrative flow, we propose Cooperative Generator -- Discriminator Networks (Co-opNet), a novel transformer-based framework where a generator works with a discriminator architecture to compose coherent long-form summaries. We explore four different discriminator objectives which each capture a different aspect of coherence, including whether salient spans of generated abstracts are hallucinated or appear in the input context, and the likelihood of sentence adjacency in generated abstracts. We measure the ability of Co-opNet to learn these objectives with arXiv scientific papers, using the abstracts as a proxy for gold long-form scientific article summaries. Empirical results from automatic and human evaluations demonstrate that Co-opNet learns to summarize with considerably improved global coherence compared to competitive baselines.
Computing Probabilistic Bisimilarity Distances for Probabilistic Automata
Venue: arXiv cs.FL 2021
Year: 2021

The probabilistic bisimilarity distance of Deng et al. has been proposed as a robust quantitative generalization of Segala and Lynch's probabilistic bisimilarity for probabilistic automata. In this paper, we present a characterization of the bisimilarity distance as the solution of a simple stochastic game. The characterization gives us an algorithm to compute the distances by applying Condon's simple policy iteration on these games. The correctness of Condon's approach, however, relies on the assumption that the games are stopping. Our games may be non-stopping in general, yet we are able to prove termination for this extended class of games. Already other algorithms have been proposed in the literature to compute these distances, with complexity in $\textbf{UP} \cap \textbf{coUP}$ and \textbf{PPAD}. Despite the theoretical relevance, these algorithms are inefficient in practice. To the best of our knowledge, our algorithm is the first practical solution. The characterization of the probabilistic bisimilarity distance mentioned above crucially uses a dual presentation of the Hausdorff distance due to Mémoli. As an additional contribution, in this paper we show that Mémoli's result can be used also to prove that the bisimilarity distance bounds the difference in the maximal (or minimal) probability of two states to satisfying arbitrary $ω$-regular properties, expressed, eg., as LTL formulas.
Exploiting Prunability for Person Re-Identification
Venue: arXiv cs.CV 2021
Year: 2021

Recent years have witnessed a substantial increase in the deep learning (DL)architectures proposed for visual recognition tasks like person re-identification,where individuals must be recognized over multiple distributed cameras. Althoughthese architectures have greatly improved the state-of-the-art accuracy, thecomputational complexity of the CNNs commonly used for feature extractionremains an issue, hindering their deployment on platforms with limited resources,or in applications with real-time constraints. There is an obvious advantage toaccelerating and compressing DL models without significantly decreasing theiraccuracy. However, the source (pruning) domain differs from operational (target)domains, and the domain shift between image data captured with differentnon-overlapping camera viewpoints leads to lower recognition accuracy. In thispaper, we investigate the prunability of these architectures under different designscenarios. This paper first revisits pruning techniques that are suitable forreducing the computational complexity of deep CNN networks applied to personre-identification. Then, these techniques are analysed according to their pruningcriteria and strategy, and according to different scenarios for exploiting pruningmethods to fine-tuning networks to target domains. Experimental resultsobtained using DL models with ResNet feature extractors, and multiplebenchmarks re-identification datasets, indicate that pruning can considerablyreduce network complexity while maintaining a high level of accuracy. Inscenarios where pruning is performed with large pre-training or fine-tuningdatasets, the number of FLOPS required by ResNet architectures is reduced byhalf, while maintaining a comparable rank-1 accuracy (within 1% of the originalmodel). Pruning while training a larger CNNs can also provide a significantlybetter performance than fine-tuning smaller ones.
Towards Enhancing Fault Tolerance in Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

Deep Learning Accelerators are prone to faults which manifest in the form of errors in Neural Networks. Fault Tolerance in Neural Networks is crucial in real-time safety critical applications requiring computation for long durations. Neural Networks with high regularisation exhibit superior fault tolerance, however, at the cost of classification accuracy. In the view of difference in functionality, a Neural Network is modelled as two separate networks, i.e, the Feature Extractor with unsupervised learning objective and the Classifier with a supervised learning objective. Traditional approaches of training the entire network using a single supervised learning objective is insufficient to achieve the objectives of the individual components optimally. In this work, a novel multi-criteria objective function, combining unsupervised training of the Feature Extractor followed by supervised tuning with Classifier Network is proposed. The unsupervised training solves two games simultaneously in the presence of adversary neural networks with conflicting objectives to the Feature Extractor. The first game minimises the loss in reconstructing the input image for indistinguishability given the features from the Extractor, in the presence of a generative decoder. The second game solves a minimax constraint optimisation for distributional smoothening of feature space to match a prior distribution, in the presence of a Discriminator network. The resultant strongly regularised Feature Extractor is combined with the Classifier Network for supervised fine-tuning. The proposed Adversarial Fault Tolerant Neural Network Training is scalable to large networks and is independent of the architecture. The evaluation on benchmarking datasets: FashionMNIST and CIFAR10, indicates that the resultant networks have high accuracy with superior tolerance to stuck at "0" faults compared to widely used regularisers.
General Control Functions for Causal Effect Estimation from Instrumental Variables
Venue: arXiv cs.LG 2021
Year: 2021

Causal effect estimation relies on separating the variation in the outcome into parts due to the treatment and due to the confounders. To achieve this separation, practitioners often use external sources of randomness that only influence the treatment called instrumental variables (IVs). We study variables constructed from treatment and IV that help estimate effects, called control functions. We characterize general control functions for effect estimation in a meta-identification result. Then, we show that structural assumptions on the treatment process allow the construction of general control functions, thereby guaranteeing identification. To construct general control functions and estimate effects, we develop the general control function method (GCFN). GCFN's first stage called variational decoupling (VDE) constructs general control functions by recovering the residual variation in the treatment given the IV. Using VDE's control function, GCFN's second stage estimates effects via regression. Further, we develop semi-supervised GCFN to construct general control functions using subsets of data that have both IV and confounders observed as supervision; this needs no structural treatment process assumptions. We evaluate GCFN on low and high dimensional simulated data and on recovering the causal effect of slave export on modern community trust.
RoboWalk: Explicit Augmented Human-Robot Dynamics Modeling for Design Optimization
Venue: arXiv cs.RO 2021
Year: 2021

Utilizing orthoses and exoskeleton technology in various applications and medical industries, particularly to help elderly and ordinary people in their daily activities is a new growing field for research institutes. In this paper, after introducing an assistive lower limb exoskeleton (RoboWalk), the dynamics models of both multi-body kinematic tree structure human and robot is derived separately, using Newton's method. The obtained models are then verified by comparing the results with those of the Recursive Newton-Euler Algorithms (RNEA). These models are then augmented to investigate the RoboWalk joint torques, and those of the human body, and also the floor reaction force of the complete system. Since RoboWalk is an under-actuated robot, despite the assistive force, an undesirable disturbing force exerts to the human. So, optimization strategies are proposed to find an optimal design to maximize the assistive behavior of RoboWalk and reduce joint torques of the human body as a result. To this end, a human-in-the-loop optimization algorithm will be used. The solution of this optimization problem is carried out by Particle Swarm Optimization (PSO) method. The designed analysis and the optimization results demonstrate the effectiveness of the proposed approaches, leading to the elimination of disturbing forces, lower torque demand for RoboWalk motors and lower weights.
Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in $\ell_p$ norm
Venue: arXiv cs.DS 2021
Year: 2021

In this work, we give provable sieving algorithms for the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices in $\ell_p$ norm ($1\leq p\leq\infty$). The running time we obtain is better than existing provable sieving algorithms. We give a new linear sieving procedure that works for all $\ell_p$ norm ($1\leq p\leq\infty$). The main idea is to divide the space into hypercubes such that each vector can be mapped efficiently to a sub-region. We achieve a time complexity of $2^{2.751n+o(n)}$, which is much less than the $2^{3.849n+o(n)}$ complexity of the previous best algorithm. We also introduce a mixed sieving procedure, where a point is mapped to a hypercube within a ball and then a quadratic sieve is performed within each hypercube. This improves the running time, especially in the $\ell_2$ norm, where we achieve a time complexity of $2^{2.25n+o(n)}$, while the List Sieve Birthday algorithm has a running time of $2^{2.465n+o(n)}$. We adopt our sieving techniques to approximation algorithms for SVP and CVP in $\ell_p$ norm ($1\leq p\leq\infty$) and show that our algorithm has a running time of $2^{2.001n+o(n)}$, while previous algorithms have a time complexity of $2^{3.169n+o(n)}$.
PhysGAN: Generating Physical-World-Resilient Adversarial Examples for Autonomous Driving
Venue: arXiv cs.CV 2021
Year: 2021

Although Deep neural networks (DNNs) are being pervasively used in vision-based autonomous driving systems, they are found vulnerable to adversarial attacks where small-magnitude perturbations into the inputs during test time cause dramatic changes to the outputs. While most of the recent attack methods target at digital-world adversarial scenarios, it is unclear how they perform in the physical world, and more importantly, the generated perturbations under such methods would cover a whole driving scene including those fixed background imagery such as the sky, making them inapplicable to physical world implementation. We present PhysGAN, which generates physical-world-resilient adversarial examples for mislead-ing autonomous driving systems in a continuous manner. We show the effectiveness and robustness of PhysGAN via extensive digital and real-world evaluations. Digital experiments show that PhysGAN is effective for various steer-ing models and scenes, which misleads the average steer-ing angle by up to 23.06 degrees under various scenarios. The real-world studies further demonstrate that PhysGAN is sufficiently resilient in practice, which misleads the average steering angle by up to 19.17 degrees. We compare PhysGAN with a set of state-of-the-art baseline methods including several of our self-designed ones, which further demonstrate the robustness and efficacy of our approach. We also show that PhysGAN outperforms state-of-the-art baseline methods To the best of our knowledge, PhysGANis probably the first technique of generating realistic and physical-world-resilient adversarial examples for attacking common autonomous driving scenarios.
Preferences Prediction using a Gallery of Mobile Device based on Scene Recognition and Object Detection
Venue: arXiv cs.CV 2021
Year: 2021

In this paper user modeling task is examined by processing a gallery of photos and videos on a mobile device. We propose novel engine for user preference prediction based on scene recognition, object detection and facial analysis. At first, all faces in a gallery are clustered and all private photos and videos with faces from large clusters are processed on the embedded system in offline mode. Other photos may be sent to the remote server to be analyzed by very deep models. The visual features of each photo are obtained from scene recognition and object detection models. These features are aggregated into a single user descriptor in the neural attention block. The proposed pipeline is implemented for the Android mobile platform. Experimental results with a subset of Photo Event Collection, Web Image Dataset for Event Recognition and Amazon Fashion datasets demonstrate the possibility to process images very efficiently without significant accuracy degradation. The source code of Android mobile application is publicly available at https://github.com/HSE-asavchenko/mobile-visual-preferences.
Identifying Linear Models in Multi-Resolution Population Data using Minimum Description Length Principle to Predict Household Income
Venue: arXiv cs.LG 2021
Year: 2021

One shirt size cannot fit everybody, while we cannot make a unique shirt that fits perfectly for everyone because of resource limitation. This analogy is true for the policy making. Policy makers cannot establish a single policy to solve all problems for all regions because each region has its own unique issue. In the other extreme, policy makers also cannot create a policy for each small village due to the resource limitation. Would it be better if we can find a set of largest regions such that the population of each region within this set has common issues and we can establish a single policy for them? In this work, we propose a framework using regression analysis and minimum description length (MDL) to find a set of largest areas that have common indicators, which can be used to predict household incomes efficiently. Given a set of household features, and a multi-resolution partition that represents administrative divisions, our framework reports a set C* of largest subdivisions that have a common model for population-income prediction. We formalize a problem of finding C* and propose the algorithm as a solution. We use both simulation datasets as well as a real-world dataset of Thailand's population household information to demonstrate our framework performance and application. The results show that our framework performance is better than the baseline methods. We show the results of our method can be used to find indicators of income prediction for many areas in Thailand. By increasing these indicator values, we expect people in these areas to gain more incomes. Hence, the policy makers can plan to establish the policies by using these indicators in our results as a guideline to solve low-income issues. Our framework can be used to support policy makers to establish policies regarding any other dependent variable beyond incomes in order to combat poverty and other issues.
Multiscale Principle of Relevant Information for Hyperspectral Image Classification
Venue: arXiv cs.LG 2021
Year: 2021

This paper proposes a novel architecture, termed multiscale principle of relevant information (MPRI), to learn discriminative spectral-spatial features for hyperspectral image (HSI) classification. MPRI inherits the merits of the principle of relevant information (PRI) to effectively extract multiscale information embedded in the given data, and also takes advantage of the multilayer structure to learn representations in a coarse-to-fine manner. Specifically, MPRI performs spectral-spatial pixel characterization (using PRI) and feature dimensionality reduction (using regularized linear discriminant analysis) iteratively and successively. Extensive experiments on three benchmark data sets demonstrate that MPRI outperforms existing state-of-the-art methods (including deep learning based ones) qualitatively and quantitatively, especially in the scenario of limited training samples. Code of MPRI is available at \url{http://bit.ly/MPRI_HSI}.
Query complexity of generalized Simon's problem
Venue: arXiv cs.CC 2021
Year: 2021

Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric cryptosystems. Generalized Simon's problem, denoted by $\mathsf{GSP}(p,n,k)$, is a natural extension of Simon's problem. In this paper we consider the query complexity of $\mathsf{GSP}(p,n,k)$. First, it is not difficult to design a quantum algorithm solving the above problem with query complexity of $O(n-k)$. However, so far it is not clear what is the classical query complexity of the problem, and revealing this complexity is necessary for clarifying the computational power gap between quantum and classical computing on the problem. To tackle this problem, we prove that any classical (deterministic or randomized) algorithm for $\mathsf{GSP}(p,n,k)$ has to query at least $Ω\left(\max\{k, \sqrt{p^{n-k}}\}\right)$ values and any classical nonadaptive deterministic algorithm for $\mathsf{GSP}(p,n,k)$ has to query at least $Ω\left(\max\{k, \sqrt{k \cdot p^{n-k}}\}\right)$ values. Hence, we clearly show the classical computing model is less powerful than the quantum counterpart, in terms of query complexity for the generalized Simon's problem. Moreover, we obtain an upper bound $O\left(\max\{k, \sqrt{k \cdot p^{n-k}}\}\right)$ on the classical deterministic query complexity of $\mathsf{GSP}(p,n,k)$, by devising a subtle classical algorithm based on group theory and the divide-and-conquer approach. Therefore, we have an almost full characterization of the classical deterministic query complexity of the generalized Simon's problem.