OpenRaiser/Intern-Atlas huggingface dataset:
ExTra: Transfer-guided Exploration
Venue: arXiv cs.LG 2020
Year: 2020

In this work we present a novel approach for transfer-guided exploration in reinforcement learning that is inspired by the human tendency to leverage experiences from similar encounters in the past while navigating a new task. Given an optimal policy in a related task-environment, we show that its bisimulation distance from the current task-environment gives a lower bound on the optimal advantage of state-action pairs in the current task-environment. Transfer-guided Exploration (ExTra) samples actions from a Softmax distribution over these lower bounds. In this way, actions with potentially higher optimum advantage are sampled more frequently. In our experiments on gridworld environments, we demonstrate that given access to an optimal policy in a related task-environment, ExTra can outperform popular domain-specific exploration strategies viz. epsilon greedy, Model-Based Interval Estimation - Exploration Bonus (MBIE-EB), Pursuit and Boltzmann in rate of convergence. We further show that ExTra is robust to choices of source task and shows a graceful degradation of performance as the dissimilarity of the source task increases. We also demonstrate that ExTra, when used alongside traditional exploration algorithms, improves their rate of convergence. Thus it is capable of complementing the efficacy of traditional exploration algorithms.
Stolen Memories: Leveraging Model Memorization for Calibrated White-Box Membership Inference
Venue: arXiv cs.LG 2020
Year: 2020

Membership inference (MI) attacks exploit the fact that machine learning algorithms sometimes leak information about their training data through the learned model. In this work, we study membership inference in the white-box setting in order to exploit the internals of a model, which have not been effectively utilized by previous work. Leveraging new insights about how overfitting occurs in deep neural networks, we show how a model's idiosyncratic use of features can provide evidence for membership to white-box attackers---even when the model's black-box behavior appears to generalize well---and demonstrate that this attack outperforms prior black-box methods. Taking the position that an effective attack should have the ability to provide confident positive inferences, we find that previous attacks do not often provide a meaningful basis for confidently inferring membership, whereas our attack can be effectively calibrated for high precision. Finally, we examine popular defenses against MI attacks, finding that (1) smaller generalization error is not sufficient to prevent attacks on real models, and (2) while small-$ε$-differential privacy reduces the attack's effectiveness, this often comes at a significant cost to the model's accuracy; and for larger $ε$ that are sometimes used in practice (e.g., $ε=16$), the attack can achieve nearly the same accuracy as on the unprotected model.
CLAREL: Classification via retrieval loss for zero-shot learning
Venue: arXiv cs.CV 2020
Year: 2020

We address the problem of learning fine-grained cross-modal representations. We propose an instance-based deep metric learning approach in joint visual and textual space. The key novelty of this paper is that it shows that using per-image semantic supervision leads to substantial improvement in zero-shot performance over using class-only supervision. On top of that, we provide a probabilistic justification for a metric rescaling approach that solves a very common problem in the generalized zero-shot learning setting, i.e., classifying test images from unseen classes as one of the classes seen during training. We evaluate our approach on two fine-grained zero-shot learning datasets: CUB and FLOWERS. We find that on the generalized zero-shot classification task CLAREL consistently outperforms the existing approaches on both datasets.
Intersection Graphs of Non-crossing Paths
Venue: arXiv cs.DM 2020
Year: 2020

We study graph classes modeled by families of non-crossing (NC) connected sets. Two classic graph classes in this context are disk graphs and proper interval graphs. We focus on the cases when the sets are paths and the host is a tree (generalizing proper interval graphs). Forbidden induced subgraph characterizations and linear time certifying recognition algorithms are given for intersection graphs of NC paths of a tree (and related subclasses). A direct consequence of our certifying algorithms is a linear time algorithm certifying the presence/absence of an induced claw $(K_{1,3})$ in a chordal graph. For the intersection graphs of NC paths of a tree, we characterize the minimum connected dominating sets (leading to a linear time algorithm to compute one). We further observe that there is always an independent dominating set which is a minimum dominating set, leading to the dominating set problem being solvable in linear time. Finally, each such graph $G$ is shown to have a Hamiltonian cycle if and only if it is 2-connected, and when $G$ is not 2-connected, a minimum-leaf spanning tree of $G$ has $\ell$ leaves if and only if $G$'s block-cutpoint tree has exactly $\ell$ leaves (e.g., implying that the block-cutpoint tree is a path if and only if the graph has a Hamiltonian path).
A weighted finite difference method for subdiffusive Black Scholes Model
Venue: arXiv cs.CE 2020
Year: 2020

In this paper we focus on the subdiffusive Black Scholes model. The main part of our work consists of the finite difference method as a numerical approach to the option pricing in the considered model. We derive the governing fractional differential equation and the related weighted numerical scheme being a generalization of the classical Crank-Nicolson scheme. The proposed method has $2-α$ order of accuracy with respect to time where $α\in(0,1)$ is the subdiffusion parameter, and $2$ with respect to space. Further, we provide the stability and convergence analysis. Finally, we present some numerical results.
On the Sample Complexity of HGR Maximal Correlation Functions for Large Datasets
Venue: arXiv cs.IT 2020
Year: 2020

The Hirschfeld-Gebelein-Rényi (HGR) maximal correlation and the corresponding functions have been shown useful in many machine learning scenarios. In this paper, we study the sample complexity of estimating the HGR maximal correlation functions by the alternating conditional expectation (ACE) algorithm using training samples from large datasets. Specifically, we develop a mathematical framework to characterize the learning errors between the maximal correlation functions computed from the true distribution, and the functions estimated from the ACE algorithm. For both supervised and semi-supervised learning scenarios, we establish the analytical expressions for the error exponents of the learning errors. Furthermore, we demonstrate that for large datasets, the upper bounds for the sample complexity of learning the HGR maximal correlation functions by the ACE algorithm can be expressed using the established error exponents. Moreover, with our theoretical results, we investigate the sampling strategy for different types of samples in semi-supervised learning with a total sampling budget constraint, and an optimal sampling strategy is developed to maximize the error exponent of the learning error. Finally, the numerical simulations are presented to support our theoretical results.
Learning to Blindly Assess Image Quality in the Laboratory and Wild
Venue: arXiv cs.CV 2020
Year: 2020

Computational models for blind image quality assessment (BIQA) are typically trained in well-controlled laboratory environments with limited generalizability to realistically distorted images. Similarly, BIQA models optimized for images captured in the wild cannot adequately handle synthetically distorted images. To face the cross-distortion-scenario challenge, we develop a BIQA model and an approach of training it on multiple IQA databases (of different distortion scenarios) simultaneously. A key step in our approach is to create and combine image pairs within individual databases as the training set, which effectively bypasses the issue of perceptual scale realignment. We compute a continuous quality annotation for each pair from the corresponding human opinions, indicating the probability of one image having better perceptual quality. We train a deep neural network for BIQA over the training set of massive image pairs by minimizing the fidelity loss. Experiments on six IQA databases demonstrate that the optimized model by the proposed training strategy is effective in blindly assessing image quality in the laboratory and wild, outperforming previous BIQA methods by a large margin.
Katecheo: A Portable and Modular System for Multi-Topic Question Answering
Venue: arXiv cs.CL 2020
Year: 2020

We introduce a modular system that can be deployed on any Kubernetes cluster for question answering via REST API. This system, called Katecheo, includes three configurable modules that collectively enable identification of questions, classification of those questions into topics, document search, and reading comprehension. We demonstrate the system using publicly available knowledge base articles extracted from Stack Exchange sites. However, users can extend the system to any number of topics, or domains, without the need to modify any of the model serving code or train their own models. All components of the system are open source and available under a permissive Apache 2 License.
Serial Quantization for Sparse Time Sequences
Venue: arXiv cs.IT 2020
Year: 2020

Sparse signals are encountered in a broad range of applications. In order to process these signals using digital hardware, they must be first sampled and quantized using an analog-to-digital convertor (ADC), which typically operates in a serial scalar manner. In this work, we propose a method for serial quantization of sparse time sequences (SQuaTS) inspired by group testing theory, which is designed to reliably and accurately quantize sparse signals acquired in a sequential manner using serial scalar ADCs. Unlike previously proposed approaches which combine quantization and compressed sensing (CS), our SQuaTS scheme updates its representation on each incoming analog sample and does not require the complete signal to be observed and stored in analog prior to quantization. We characterize the asymptotic tradeoff between accuracy and quantization rate of SQuaTS as well as its computational burden. We also propose a variation of SQuaTS, which trades rate for computational efficiency. Next, we show how SQuaTS can be naturally extended to distributed quantization scenarios, where a set of jointly sparse time sequences are acquired individually and processed jointly. Our numerical results demonstrate that SQuaTS is capable of achieving substantially improved representation accuracy over previous CS-based schemes without requiring the complete set of analog signal samples to be observed prior to its quantization, making it an attractive approach for acquiring sparse time sequences.
Interference Avoidance Position Planning in Dual-hop and Multi-hop UAV Relay Networks
Venue: arXiv cs.NI 2020
Year: 2020

We consider unmanned aerial vehicle (UAV)-assisted wireless communication employing UAVs as relay nodes to increase the throughput between a pair of transmitter and receiver. We focus on developing effective methods to position the UAV(s) in the sky in the presence of interference in the environment, the existence of which makes the problem non-trivial and our methodology different from the current art. We study the optimal position planning, which aims to maximize the (average) signal-to-interference-ratio (SIR) of the system, in the presence of: i) one major source of interference, ii) stochastic interference. For each scenario, we first consider utilizing a single UAV in the dual-hop relay mode and determine its optimal position. Afterward, multiple UAVs in the multi-hop relay mode are considered, for which we investigate two novel problems concerned with determining the optimal number of required UAVs and developing an optimal fully distributed position alignment method. Subsequently, we propose a cost-effective method that simultaneously minimizes the number of UAVs and determines their optimal positions to guarantee a certain (average) SIR of the system. Alternatively, for a given number of UAVs, we develop a fully distributed placement algorithm along with its performance guarantee. Numerical simulations are provided to evaluate the performance of our proposed methods.
Pricing in Resource Allocation Games Based on Lagrangean Duality and Convexification
Venue: arXiv cs.GT 2020
Year: 2020

We consider a basic resource allocation game, where the players' strategy spaces are subsets of $R^m$ and cost/utility functions are parameterized by some common vector $u\in R^m$ and, otherwise, only depend on the own strategy choice. A strategy of a player can be interpreted as a vector of resource consumption and a joint strategy profile naturally leads to an aggregate consumption vector. Resources can be priced, that is, the game is augmented by a price vector $λ\in R^m_+$ and players have quasi-linear overall costs/utilities meaning that in addition to the original costs/utilities, a player needs to pay the corresponding price per consumed unit. We investigate the following question: for which aggregated consumption vectors $u$ can we find prices $λ$ that induce an equilibrium realizing the targeted consumption profile? For answering this question, we revisit a well-known duality-based framework and derive several characterizations of the existence of such $u$ and $λ$ using convexification techniques. We show that for finite strategy spaces or certain concave games, the equilibrium existence problem reduces to solving a well-structured LP. We then consider a class of monotone aggregative games having the property that the cost/utility functions of players may depend on the induced load of a strategy profile. For this class, we show a sufficient condition of enforceability based on the previous characterizations. We demonstrate that this framework can help to unify parts of four largely independent streams in the literature: tolls in transportation systems, Walrasian market equilibria, trading networks and congestion control in communication networks.
Truncating the Y-Axis: Threat or Menace?
Venue: arXiv cs.HC 2020
Year: 2020

Bar charts with y-axes that don't begin at zero can visually exaggerate effect sizes. However, advice for whether or not to truncate the y-axis can be equivocal for other visualization types. In this paper we present examples of visualizations where this y-axis truncation can be beneficial as well as harmful, depending on the communicative and analytic intent. We also present the results of a series of crowd-sourced experiments in which we examine how y-axis truncation impacts subjective effect size across visualization types, and we explore alternative designs that more directly alert viewers to this truncation. We find that the subjective impact of axis truncation is persistent across visualizations designs, even for designs with explicit visual cues that indicate truncation has taken place. We suggest that designers consider the scale of the meaningful effect sizes and variation they intend to communicate, regardless of the visual encoding.
Fast Video Crowd Counting with a Temporal Aware Network
Venue: arXiv cs.CV 2020
Year: 2020

Crowd counting aims to count the number of instantaneous people in a crowded space, and many promising solutions have been proposed for single image crowd counting. With the ubiquitous video capture devices in public safety field, how to effectively apply the crowd counting technique to video content has become an urgent problem. In this paper, we introduce a novel framework based on temporal aware modeling of the relationship between video frames. The proposed network contains a few dilated residual blocks, and each of them consists of the layers that compute the temporal convolutions of features from the adjacent frames to improve the prediction. To alleviate the expensive computation and satisfy the demand of fast video crowd counting, we also introduce a lightweight network to balance the computational cost with representation ability. We conduct experiments on the crowd counting benchmarks and demonstrate its superiority in terms of effectiveness and efficiency over previous video-based approaches.
Head-Driven Phrase Structure Grammar Parsing on Penn Treebank
Venue: arXiv cs.CL 2020
Year: 2020

Head-driven phrase structure grammar (HPSG) enjoys a uniform formalism representing rich contextual syntactic and even semantic meanings. This paper makes the first attempt to formulate a simplified HPSG by integrating constituent and dependency formal representations into head-driven phrase structure. Then two parsing algorithms are respectively proposed for two converted tree representations, division span and joint span. As HPSG encodes both constituent and dependency structure information, the proposed HPSG parsers may be regarded as a sort of joint decoder for both types of structures and thus are evaluated in terms of extracted or converted constituent and dependency parsing trees. Our parser achieves new state-of-the-art performance for both parsing tasks on Penn Treebank (PTB) and Chinese Penn Treebank, verifying the effectiveness of joint learning constituent and dependency structures. In details, we report 96.33 F1 of constituent parsing and 97.20\% UAS of dependency parsing on PTB.
Revisiting Metric Learning for Few-Shot Image Classification
Venue: arXiv cs.CV 2020
Year: 2020

The goal of few-shot learning is to recognize new visual concepts with just a few amount of labeled samples in each class. Recent effective metric-based few-shot approaches employ neural networks to learn a feature similarity comparison between query and support examples. However, the importance of feature embedding, i.e., exploring the relationship among training samples, is neglected. In this work, we present a simple yet powerful baseline for few-shot classification by emphasizing the importance of feature embedding. Specifically, we revisit the classical triplet network from deep metric learning, and extend it into a deep K-tuplet network for few-shot learning, utilizing the relationship among the input samples to learn a general representation learning via episode-training. Once trained, our network is able to extract discriminative features for unseen novel categories and can be seamlessly incorporated with a non-linear distance metric function to facilitate the few-shot classification. Our result on the miniImageNet benchmark outperforms other metric-based few-shot classification methods. More importantly, when evaluated on completely different datasets (Caltech-101, CUB-200, Stanford Dogs and Cars) using the model trained with miniImageNet, our method significantly outperforms prior methods, demonstrating its superior capability to generalize to unseen classes.
A Review of Robot Learning for Manipulation: Challenges, Representations, and Algorithms
Venue: arXiv cs.RO 2020
Year: 2020

A key challenge in intelligent robotics is creating robots that are capable of directly interacting with the world around them to achieve their goals. The last decade has seen substantial growth in research on the problem of robot manipulation, which aims to exploit the increasing availability of affordable robot arms and grippers to create robots capable of directly interacting with the world to achieve their goals. Learning will be central to such autonomous systems, as the real world contains too much variation for a robot to expect to have an accurate model of its environment, the objects in it, or the skills required to manipulate them, in advance. We aim to survey a representative subset of that research which uses machine learning for manipulation. We describe a formalization of the robot manipulation learning problem that synthesizes existing research into a single coherent framework and highlight the many remaining research opportunities and challenges.
A generic finite element framework on parallel tree-based adaptive meshes
Venue: arXiv cs.MS 2020
Year: 2020

In this work we formally derive and prove the correctness of the algorithms and data structures in a parallel, distributed-memory, generic finite element framework that supports h-adaptivity on computational domains represented as forest-of-trees. The framework is grounded on a rich representation of the adaptive mesh suitable for generic finite elements that is built on top of a low-level, light-weight forest-of-trees data structure handled by a specialized, highly parallel adaptive meshing engine, for which we have identified the requirements it must fulfill to be coupled into our framework. Atop this two-layered mesh representation, we build the rest of data structures required for the numerical integration and assembly of the discrete system of linear equations. We consider algorithms that are suitable for both subassembled and fully-assembled distributed data layouts of linear system matrices. The proposed framework has been implemented within the FEMPAR scientific software library, using p4est as a practical forest-of-octrees demonstrator. A strong scaling study of this implementation when applied to Poisson and Maxwell problems reveals remarkable scalability up to 32.2K CPU cores and 482.2M degrees of freedom. Besides, a comparative performance study of FEMPAR and the state-of-the-art deal.ii finite element software shows at least comparative performance, and at most factor 2-3 improvements in the h-adaptive approximation of a Poisson problem with first- and second-order Lagrangian finite elements, respectively.
Norms for Beneficial A.I.: A Computational Analysis of the Societal Value Alignment Problem
Venue: arXiv cs.CY 2020
Year: 2020

The rise of artificial intelligence (A.I.) based systems is already offering substantial benefits to the society as a whole. However, these systems may also enclose potential conflicts and unintended consequences. Notably, people will tend to adopt an A.I. system if it confers them an advantage, at which point non-adopters might push for a strong regulation if that advantage for adopters is at a cost for them. Here we propose an agent-based game-theoretical model for these conflicts, where agents may decide to resort to A.I. to use and acquire additional information on the payoffs of a stochastic game, striving to bring insights from simulation to what has been, hitherto, a mostly philosophical discussion. We frame our results under the current discussion on ethical A.I. and the conflict between individual and societal gains: the societal value alignment problem. We test the arising equilibria in the adoption of A.I. technology under different norms followed by artificial agents, their ensuing benefits, and the emergent levels of wealth inequality. We show that without any regulation, purely selfish A.I. systems will have the strongest advantage, even when a utilitarian A.I. provides significant benefits for the individual and the society. Nevertheless, we show that it is possible to develop A.I. systems following human conscious policies that, when introduced in society, lead to an equilibrium where the gains for the adopters are not at a cost for non-adopters, thus increasing the overall wealth of the population and lowering inequality. However, as shown, a self-organised adoption of such policies would require external regulation.