OpenRaiser/Intern-Atlas huggingface dataset:
Sharp Thresholds of the Information Cascade Fragility Under a Mismatched Model
Venue: arXiv cs.LG 2020
Year: 2020

We analyze a sequential decision making model in which decision makers (or, players) take their decisions based on their own private information as well as the actions of previous decision makers. Such decision making processes often lead to what is known as the \emph{information cascade} or \emph{herding} phenomenon. Specifically, a cascade develops when it seems rational for some players to abandon their own private information and imitate the actions of earlier players. The risk, however, is that if the initial decisions were wrong, then the whole cascade will be wrong. Nonetheless, information cascade are known to be fragile: there exists a sequence of \emph{revealing} probabilities $\{p_{\ell}\}_{\ell\geq1}$, such that if with probability $p_{\ell}$ player $\ell$ ignores the decisions of previous players, and rely on his private information only, then wrong cascades can be avoided. Previous related papers which study the fragility of information cascades always assume that the revealing probabilities are known to all players perfectly, which might be unrealistic in practice. Accordingly, in this paper we study a mismatch model where players believe that the revealing probabilities are $\{q_\ell\}_{\ell\in\mathbb{N}}$ when they truly are $\{p_\ell\}_{\ell\in\mathbb{N}}$, and study the effect of this mismatch on information cascades. We consider both adversarial and probabilistic sequential decision making models, and derive closed-form expressions for the optimal learning rates at which the error probability associated with a certain decision maker goes to zero. We prove several novel phase transitions in the behaviour of the asymptotic learning rate.
BUDS: Balancing Utility and Differential Privacy by Shuffling
Venue: arXiv cs.LG 2020
Year: 2020

Balancing utility and differential privacy by shuffling or \textit{BUDS} is an approach towards crowd-sourced, statistical databases, with strong privacy and utility balance using differential privacy theory. Here, a novel algorithm is proposed using one-hot encoding and iterative shuffling with the loss estimation and risk minimization techniques, to balance both the utility and privacy. In this work, after collecting one-hot encoded data from different sources and clients, a step of novel attribute shuffling technique using iterative shuffling (based on the query asked by the analyst) and loss estimation with an updation function and risk minimization produces a utility and privacy balanced differential private report. During empirical test of balanced utility and privacy, BUDS produces $ε= 0.02$ which is a very promising result. Our algorithm maintains a privacy bound of $ε= ln [t/((n_1 - 1)^S)]$ and loss bound of $c' \bigg|e^{ln[t/((n_1 - 1)^S)]} - 1\bigg|$.
ADMP: An Adversarial Double Masks Based Pruning Framework For Unsupervised Cross-Domain Compression
Venue: arXiv cs.CV 2020
Year: 2020

Despite the recent progress of network pruning, directly applying it to the Internet of Things (IoT) applications still faces two challenges, i.e. the distribution divergence between end and cloud data and the missing of data label on end devices. One straightforward solution is to combine the unsupervised domain adaptation (UDA) technique and pruning. For example, the model is first pruned on the cloud and then transferred from cloud to end by UDA. However, such a naive combination faces high performance degradation. Hence this work proposes an Adversarial Double Masks based Pruning (ADMP) for such cross-domain compression. In ADMP, we construct a Knowledge Distillation framework not only to produce pseudo labels but also to provide a measurement of domain divergence as the output difference between the full-size teacher and the pruned student. Unlike existing mask-based pruning works, two adversarial masks, i.e. soft and hard masks, are adopted in ADMP. So ADMP can prune the model effectively while still allowing the model to extract strong domain-invariant features and robust classification boundaries. During training, the Alternating Direction Multiplier Method is used to overcome the binary constraint of {0,1}-masks. On Office31 and ImageCLEF-DA datasets, the proposed ADMP can prune 60% channels with only 0.2% and 0.3% average accuracy loss respectively. Compared with the state of art, we can achieve about 1.63x parameters reduction and 4.1% and 5.1% accuracy improvement.
Realistic text replacement with non-uniform style conditioning
Venue: arXiv cs.CV 2020
Year: 2020

In this work, we study the possibility of realistic text replacement, the goal of which is to replace text present in the image with user-supplied text. The replacement should be performed in a way that will not allow distinguishing the resulting image from the original one. We achieve this goal by developing a novel non-uniform style conditioning layer and apply it to an encoder-decoder ResNet based architecture. The resulting model is a single-stage model, with no post-processing. The proposed model achieves realistic text replacement and outperforms existing approaches on ICDAR MLT.
Distributed-Memory Vertex-Centric Network Embedding for Large-Scale Graphs
Venue: arXiv cs.DC 2020
Year: 2020

Network embedding is an important step in many different computations based on graph data. However, existing approaches are limited to small or middle size graphs with fewer than a million edges. In practice, web or social network graphs are orders of magnitude larger, thus making most current methods impractical for very large graphs. To address this problem, we introduce a new distributed-memory parallel network embedding method based on Apache Spark and GraphX. We demonstrate the scalability of our method as well as its ability to generate meaningful embeddings for vertex classification and link prediction on both real-world and synthetic graphs.
AdaLAM: Revisiting Handcrafted Outlier Detection
Venue: arXiv cs.CV 2020
Year: 2020

Local feature matching is a critical component of many computer vision pipelines, including among others Structure-from-Motion, SLAM, and Visual Localization. However, due to limitations in the descriptors, raw matches are often contaminated by a majority of outliers. As a result, outlier detection is a fundamental problem in computer vision, and a wide range of approaches have been proposed over the last decades. In this paper we revisit handcrafted approaches to outlier filtering. Based on best practices, we propose a hierarchical pipeline for effective outlier detection as well as integrate novel ideas which in sum lead to AdaLAM, an efficient and competitive approach to outlier rejection. AdaLAM is designed to effectively exploit modern parallel hardware, resulting in a very fast, yet very accurate, outlier filter. We validate AdaLAM on multiple large and diverse datasets, and we submit to the Image Matching Challenge (CVPR2020), obtaining competitive results with simple baseline descriptors. We show that AdaLAM is more than competitive to current state of the art, both in terms of efficiency and effectiveness.
Connecting User and Item Perspectives in Popularity Debiasing for Collaborative Recommendation
Venue: arXiv cs.IR 2020
Year: 2020

Recommender systems learn from historical users' feedback that is often non-uniformly distributed across items. As a consequence, these systems may end up suggesting popular items more than niche items progressively, even when the latter would be of interest for users. This can hamper several core qualities of the recommended lists (e.g., novelty, coverage, diversity), impacting on the future success of the underlying platform itself. In this paper, we formalize two novel metrics that quantify how much a recommender system equally treats items along the popularity tail. The first one encourages equal probability of being recommended across items, while the second one encourages true positive rates for items to be equal. We characterize the recommendations of representative algorithms by means of the proposed metrics, and we show that the item probability of being recommended and the item true positive rate are biased against the item popularity. To promote a more equal treatment of items along the popularity tail, we propose an in-processing approach aimed at minimizing the biased correlation between user-item relevance and item popularity. Extensive experiments show that, with small losses in accuracy, our popularity-mitigation approach leads to important gains in beyond-accuracy recommendation quality.
Equality of Learning Opportunity via Individual Fairness in Personalized Recommendations
Venue: arXiv cs.IR 2020
Year: 2020

Online educational platforms are playing a primary role in mediating the success of individuals' careers. Therefore, while building overlying content recommendation services, it becomes essential to guarantee that learners are provided with equal recommended learning opportunities, according to the platform values, context, and pedagogy. Though the importance of ensuring equality of learning opportunities has been well investigated in traditional institutions, how this equality can be operationalized in online learning ecosystems through recommender systems is still under-explored. In this paper, we formalize educational principles that model recommendations' learning properties, and a novel fairness metric that combines them in order to monitor the equality of recommended learning opportunities among learners. Then, we envision a scenario wherein an educational platform should be arranged in such a way that the generated recommendations meet each principle to a certain degree for all learners, constrained to their individual preferences. Under this view, we explore the learning opportunities provided by recommender systems in a large-scale course platform, uncovering systematic inequalities. To reduce this effect, we propose a novel post-processing approach that balances personalization and equality of recommended opportunities. Experiments show that our approach leads to higher equality, with a negligible loss in personalization. Our study moves a step forward in operationalizing the ethics of human learning in recommendations, a core unit of intelligent educational systems.
Multi-step Estimation for Gradient-based Meta-learning
Venue: arXiv cs.LG 2020
Year: 2020

Gradient-based meta-learning approaches have been successful in few-shot learning, transfer learning, and a wide range of other domains. Despite its efficacy and simplicity, the burden of calculating the Hessian matrix with large memory footprints is the critical challenge in large-scale applications. To tackle this issue, we propose a simple yet straightforward method to reduce the cost by reusing the same gradient in a window of inner steps. We describe the dynamics of the multi-step estimation in the Lagrangian formalism and discuss how to reduce evaluating second-order derivatives estimating the dynamics. To validate our method, we experiment on meta-transfer learning and few-shot learning tasks for multiple settings. The experiment on meta-transfer emphasizes the applicability of training meta-networks, where other approximations are limited. For few-shot learning, we evaluate time and memory complexities compared with popular baselines. We show that our method significantly reduces training time and memory usage, maintaining competitive accuracies, or even outperforming in some cases.
On smooth or 0/1 designs of the fixed-mesh element-based topology optimization
Venue: arXiv cs.CE 2020
Year: 2020

The traditional element-based topology optimization based on material penalization typically aims at a 0/1 design. Our numerical experiments reveal that the compliance of a smooth design is overestimated when material properties of boundary intermediate elements under the fixed-mesh finite element analysis are interpolated with a material penalization model. This paper proposes a floating projection topology optimization (FPTO) method for seeking a smooth design using the ersatz material model or a 0/1 design using a material penalization model. The proposed floating projection constraint combining with the upper and lower bounds heuristically simulates 0/1 constraints of design variables in the original discrete optimization problem. Numerical examples demonstrate the capability of the proposed element-based topology optimization approach in obtaining 0/1 or smooth designs for 2D and 3D compliance minimization problems. The proposed topology optimization approach can be easily implemented under the framework of the fixed-mesh finite element analysis and provides an alternative way to form explicit topologies of structures, especially when the ersatz material model is adopted.
Toward Scalable Algorithms for the Unsplittable Shortest Path Routing Problem
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we consider the Delay Constrained Unsplittable Shortest Path Routing problem which arises in the field of traffic engineering for IP networks. This problem consists, given a directed graph and a set of commodities, to compute a set of routing paths and the associated administrative weights such that each commodity is routed along the unique shortest path between its origin and its destination, according to these weights. We present a compact MILP formulation for the problem, extending the work in (A. Bley, 2010) along with some valid inequalities to strengthen its linear relaxation. This formulation is used as the bulding block of an iterative approach that we develop to tackle large scale instances. We further propose a dynamic programming algorithm based on a tree decomposition of the graph. To the best of our knowledge, this is the first exact combinatorial algorithm for the problem. Finally, we assess the efficiency of our approaches through a set of experiments on state-of-the-art instances.
AutoMat -- Automatic Differentiation for Generalized Standard Materials on GPUs
Venue: arXiv cs.CE 2020
Year: 2020

We propose a universal method for the evaluation of generalized standard materials that greatly simplifies the material law implementation process. By means of automatic differentiation and a numerical integration scheme, AutoMat reduces the implementation effort to two potential functions. By moving AutoMat to the GPU, we close the performance gap to conventional evaluation routines and demonstrate in detail that the expression level reverse mode of automatic differentiation as well as its extension to second order derivatives can be applied inside CUDA kernels. We underline the effectiveness and the applicability of AutoMat by integrating it into the FFT-based homogenization scheme of Moulinec and Suquet and discuss the benefits of using AutoMat with respect to runtime and solution accuracy for an elasto-viscoplastic example.
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Venue: arXiv cs.DS 2020
Year: 2020

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.
OpenSHC: A Versatile Multilegged Robot Controller
Venue: arXiv cs.RO 2020
Year: 2020

Multilegged robots have the ability to perform stable locomotion on relatively rough terrain. However, the complexity of legged robots over wheeled or tracked robots make them difficult to control. This paper presents OpenSHC (Open-source Syropod High-level Controller), a versatile high-level controller {capable of generating gaits and poses for quasi-static multilegged robots, both simulated and with real hardware implementations. With full Robot Operating System (ROS) integration, the controller can be quickly deployed on robots with different actuators and sensor payloads}. The flexibility of OpenSHC is demonstrated on the 30 degrees of freedom hexapod Bullet, analysing the energetic performance of various leg configurations, kinematic arrangements and gaits over different locomotion speeds. With OpenSHC being easily configured to different physical and locomotion specifications, a hardware-based parameter space search for optimal locomotion parameters is conducted. The experimental evaluation shows that the mammalian configuration offers lower power consumption across a range of step frequencies; with the insectoid configuration providing performance advantages at higher body velocities and increased stability at low step frequencies. OpenSHC is open-source and able to be configured for various number of joints and legs.
On Universalized Adversarial and Invariant Perturbations
Venue: arXiv cs.LG 2020
Year: 2020

Convolutional neural networks or standard CNNs (StdCNNs) are translation-equivariant models that achieve translation invariance when trained on data augmented with sufficient translations. Recent work on equivariant models for a given group of transformations (e.g., rotations) has lead to group-equivariant convolutional neural networks (GCNNs). GCNNs trained on data augmented with sufficient rotations achieve rotation invariance. Recent work by authors arXiv:2002.11318 studies a trade-off between invariance and robustness to adversarial attacks. In another related work arXiv:2005.08632, given any model and any input-dependent attack that satisfies a certain spectral property, the authors propose a universalization technique called SVD-Universal to produce a universal adversarial perturbation by looking at very few test examples. In this paper, we study the effectiveness of SVD-Universal on GCNNs as they gain rotation invariance through higher degree of training augmentation. We empirically observe that as GCNNs gain rotation invariance through training augmented with larger rotations, the fooling rate of SVD-Universal gets better. To understand this phenomenon, we introduce universal invariant directions and study their relation to the universal adversarial direction produced by SVD-Universal.
Differentiable Neural Input Search for Recommender Systems
Venue: arXiv cs.LG 2020
Year: 2020

Latent factor models are the driving forces of the state-of-the-art recommender systems, with an important insight of vectorizing raw input features into dense embeddings. The dimensions of different feature embeddings are often set to a same value empirically, which limits the predictive performance of latent factor models. Existing works have proposed heuristic or reinforcement learning-based methods to search for mixed feature embedding dimensions. For efficiency concern, these methods typically choose embedding dimensions from a restricted set of candidate dimensions. However, this restriction will hurt the flexibility of dimension selection, leading to suboptimal performance of search results. In this paper, we propose Differentiable Neural Input Search (DNIS), a method that searches for mixed feature embedding dimensions in a more flexible space through continuous relaxation and differentiable optimization. The key idea is to introduce a soft selection layer that controls the significance of each embedding dimension, and optimize this layer according to model's validation performance. DNIS is model-agnostic and thus can be seamlessly incorporated with existing latent factor models for recommendation. We conduct experiments with various architectures of latent factor models on three public real-world datasets for rating prediction, Click-Through-Rate (CTR) prediction, and top-k item recommendation. The results demonstrate that our method achieves the best predictive performance compared with existing neural input search approaches with fewer embedding parameters and less time cost.
IterefinE: Iterative KG Refinement Embeddings using Symbolic Knowledge
Venue: arXiv cs.AI 2020
Year: 2020

Knowledge Graphs (KGs) extracted from text sources are often noisy and lead to poor performance in downstream application tasks such as KG-based question answering.While much of the recent activity is focused on addressing the sparsity of KGs by using embeddings for inferring new facts, the issue of cleaning up of noise in KGs through KG refinement task is not as actively studied. Most successful techniques for KG refinement make use of inference rules and reasoning over ontologies. Barring a few exceptions, embeddings do not make use of ontological information, and their performance in KG refinement task is not well understood. In this paper, we present a KG refinement framework called IterefinE which iteratively combines the two techniques - one which uses ontological information and inferences rules, PSL-KGI, and the KG embeddings such as ComplEx and ConvE which do not. As a result, IterefinE is able to exploit not only the ontological information to improve the quality of predictions, but also the power of KG embeddings which (implicitly) perform longer chains of reasoning. The IterefinE framework, operates in a co-training mode and results in explicit type-supervised embedding of the refined KG from PSL-KGI which we call as TypeE-X. Our experiments over a range of KG benchmarks show that the embeddings that we produce are able to reject noisy facts from KG and at the same time infer higher quality new facts resulting in up to 9% improvement of overall weighted F1 score
Contact Tracing: Beyond the Apps
Venue: arXiv cs.CY 2020
Year: 2020

As pandemic wide spread results in locking down vital facilities, digital contact tracing is deemed as a key for re-opening. However, current efforts in digital contact tracing, running as mobile apps on users' smartphones, fall short in being effective. This paper lays out the vision and guidelines for the next era of digital contact tracing, where the contact tracing functionality is moved from being personal responsibility to be the responsibility of facilities that users visit daily. A privacy-preserving architecture is proposed, which can be mandated as a prerequisite for any facility to re-open during or after the pandemic.
WaveNODE: A Continuous Normalizing Flow for Speech Synthesis
Venue: arXiv cs.SD 2020
Year: 2020

In recent years, various flow-based generative models have been proposed to generate high-fidelity waveforms in real-time. However, these models require either a well-trained teacher network or a number of flow steps making them memory-inefficient. In this paper, we propose a novel generative model called WaveNODE which exploits a continuous normalizing flow for speech synthesis. Unlike the conventional models, WaveNODE places no constraint on the function used for flow operation, thus allowing the usage of more flexible and complex functions. Moreover, WaveNODE can be optimized to maximize the likelihood without requiring any teacher network or auxiliary loss terms. We experimentally show that WaveNODE achieves comparable performance with fewer parameters compared to the conventional flow-based vocoders.