OpenRaiser/Intern-Atlas huggingface dataset:
On the computational tractability of a geographic clustering problem arising in redistricting
Venue: arXiv cs.DS 2020
Year: 2020

Redistricting is the problem of dividing a state into a number $k$ of regions, called districts. Voters in each district elect a representative. The primary criteria are: each district is connected, district populations are equal (or nearly equal), and districts are "compact". There are multiple competing definitions of compactness, usually minimizing some quantity. One measure that has been recently promoted by Duchin and others is number of cut edges. In redistricting, one is given atomic regions out of which each district must be built. The populations of the atomic regions are given. Consider the graph with one vertex per atomic region (with weight equal to the region's population) and an edge between atomic regions that share a boundary. A districting plan is a partition of vertices into $k$ parts, each connnected, of nearly equal weight. The districts are considered compact to the extent that the plan minimizes the number of edges crossing between different parts. Consider two problems: find the most compact districting plan, and sample districting plans under a compactness constraint uniformly at random. Both problems are NP-hard so we restrict the input graph to have branchwidth at most $w$. (A planar graph's branchwidth is bounded by its diameter.) If both $k$ and $w$ are bounded by constants, the problems are solvable in polynomial time. Assume vertices have weight~1. One would like algorithms whose running times are of the form $O(f(k,w) n^c)$ for some constant $c$ independent of $k$ and $w$, in which case the problems are said to be fixed-parameter tractable with respect to $k$ and $w$). We show that, under a complexity-theoretic assumption, no such algorithms exist. However, we do give algorithms with running time $O(c^wn^{k+1})$. Thus if the diameter of the graph is moderately small and the number of districts is very small, our algorithm is useable.
Personalization in Human Activity Recognition
Venue: arXiv cs.CV 2020
Year: 2020

In the recent years there has been a growing interest in techniques able to automatically recognize activities performed by people. This field is known as Human Activity recognition (HAR). HAR can be crucial in monitoring the wellbeing of the people, with special regard to the elder population and those people affected by degenerative conditions. One of the main challenges concerns the diversity of the population and how the same activities can be performed in different ways due to physical characteristics and life-style. In this paper we explore the possibility of exploiting physical characteristics and signal similarity to achieve better results with respect to deep learning classifiers that do not rely on this information.
On resistive spiking of fungi
Venue: arXiv cs.ET 2020
Year: 2020

We study long-term electrical resistance dynamics in mycelium and fruit bodies of oyster fungi P. ostreatus. A nearly homogeneous sheet of mycelium on the surface of a growth substrate exhibits trains of resistance spikes. The average width of spikes is c.~23~min and the average amplitude is c.~1~kOhm. The distance between neighbouring spikes in a train of spikes is c.~30~min. Typically there are 4-6 spikes in a train of spikes. Two types of resistance spikes trains are found in fruit bodies: low frequency and high amplitude (28~min spike width, 1.6~kOhm amplitude, 57~min distance between spikes) and high frequency and low amplitude (10~min width, 0.6~kOhm amplitude, 44~min distance between spikes). The findings could be applied in monitoring of physiological states of fungi and future development of living electronic devices and sensors.
Developing Constrained Neural Units Over Time
Venue: arXiv cs.LG 2020
Year: 2020

In this paper we present a foundational study on a constrained method that defines learning problems with Neural Networks in the context of the principle of least cognitive action, which very much resembles the principle of least action in mechanics. Starting from a general approach to enforce constraints into the dynamical laws of learning, this work focuses on an alternative way of defining Neural Networks, that is different from the majority of existing approaches. In particular, the structure of the neural architecture is defined by means of a special class of constraints that are extended also to the interaction with data, leading to "architectural" and "input-related" constraints, respectively. The proposed theory is cast into the time domain, in which data are presented to the network in an ordered manner, that makes this study an important step toward alternative ways of processing continuous streams of data with Neural Networks. The connection with the classic Backpropagation-based update rule of the weights of networks is discussed, showing that there are conditions under which our approach degenerates to Backpropagation. Moreover, the theory is experimentally evaluated on a simple problem that allows us to deeply study several aspects of the theory itself and to show the soundness of the model.
Multi-channel Transformers for Multi-articulatory Sign Language Translation
Venue: arXiv cs.CV 2020
Year: 2020

Sign languages use multiple asynchronous information channels (articulators), not just the hands but also the face and body, which computational approaches often ignore. In this paper we tackle the multi-articulatory sign language translation task and propose a novel multi-channel transformer architecture. The proposed architecture allows both the inter and intra contextual relationships between different sign articulators to be modelled within the transformer network itself, while also maintaining channel specific information. We evaluate our approach on the RWTH-PHOENIX-Weather-2014T dataset and report competitive translation performance. Importantly, we overcome the reliance on gloss annotations which underpin other state-of-the-art approaches, thereby removing future need for expensive curated datasets.
Generalized Zero-Shot Learning via VAE-Conditioned Generative Flow
Venue: arXiv cs.CV 2020
Year: 2020

Generalized zero-shot learning (GZSL) aims to recognize both seen and unseen classes by transferring knowledge from semantic descriptions to visual representations. Recent generative methods formulate GZSL as a missing data problem, which mainly adopts GANs or VAEs to generate visual features for unseen classes. However, GANs often suffer from instability, and VAEs can only optimize the lower bound on the log-likelihood of observed data. To overcome the above limitations, we resort to generative flows, a family of generative models with the advantage of accurate likelihood estimation. More specifically, we propose a conditional version of generative flows for GZSL, i.e., VAE-Conditioned Generative Flow (VAE-cFlow). By using VAE, the semantic descriptions are firstly encoded into tractable latent distributions, conditioned on that the generative flow optimizes the exact log-likelihood of the observed visual features. We ensure the conditional latent distribution to be both semantic meaningful and inter-class discriminative by i) adopting the VAE reconstruction objective, ii) releasing the zero-mean constraint in VAE posterior regularization, and iii) adding a classification regularization on the latent variables. Our method achieves state-of-the-art GZSL results on five well-known benchmark datasets, especially for the significant improvement in the large-scale setting. Code is released at https://github.com/guyuchao/VAE-cFlow-ZSL.
How Visualization PhD Students Cope with Paper Rejections
Venue: arXiv cs.HC 2020
Year: 2020

We conducted a questionnaire study aimed towards PhD students in the field of visualization research to understand how they cope with paper rejections. We collected responses from 24 participants and performed a qualitative analysis of the data in relation to the provided support by collaborators, resubmission strategies, handling multiple rejects, and personal impression of the reviews. The results indicate that the PhD students in the visualization community generally cope well with the negative reviews and, with experience, learn how to act accordingly to improve and resubmit their work. Our results reveal the main coping strategies that can be applied for constructively handling rejected visualization papers. The most prominent strategies include: discussing reviews with collaborators and making a resubmission plan, doing a major revision to improve the work, shortening the work, and seeing rejection as a positive learning experience.
Machine Reasoning Explainability
Venue: arXiv cs.AI 2020
Year: 2020

As a field of AI, Machine Reasoning (MR) uses largely symbolic means to formalize and emulate abstract reasoning. Studies in early MR have notably started inquiries into Explainable AI (XAI) -- arguably one of the biggest concerns today for the AI community. Work on explainable MR as well as on MR approaches to explainability in other areas of AI has continued ever since. It is especially potent in modern MR branches, such as argumentation, constraint and logic programming, planning. We hereby aim to provide a selective overview of MR explainability techniques and studies in hopes that insights from this long track of research will complement well the current XAI landscape. This document reports our work in-progress on MR explainability.
From Clicks to Conversions: Recommendation for long-term reward
Venue: arXiv cs.IR 2020
Year: 2020

Recommender systems are often optimised for short-term reward: a recommendation is considered successful if a reward (e.g. a click) can be observed immediately after the recommendation. The advantage of this framework is that with some reasonable (although questionable) assumptions, it allows familiar supervised learning tools to be used for the recommendation task. However, it means that long-term business metrics, e.g. sales or retention are ignored. In this paper we introduce a framework for modeling long-term rewards in the RecoGym simulation environment. We use this newly introduced functionality to showcase problems introduced by the last-click attribution scheme in the case of conversion-optimized recommendations and propose a simple extension that leads to state-of-the-art results.
Improved Weighted Random Forest for Classification Problems
Venue: arXiv cs.LG 2020
Year: 2020

Several studies have shown that combining machine learning models in an appropriate way will introduce improvements in the individual predictions made by the base models. The key to make well-performing ensemble model is in the diversity of the base models. Of the most common solutions for introducing diversity into the decision trees are bagging and random forest. Bagging enhances the diversity by sampling with replacement and generating many training data sets, while random forest adds selecting a random number of features as well. This has made the random forest a winning candidate for many machine learning applications. However, assuming equal weights for all base decision trees does not seem reasonable as the randomization of sampling and input feature selection may lead to different levels of decision-making abilities across base decision trees. Therefore, we propose several algorithms that intend to modify the weighting strategy of regular random forest and consequently make better predictions. The designed weighting frameworks include optimal weighted random forest based on ac-curacy, optimal weighted random forest based on the area under the curve (AUC), performance-based weighted random forest, and several stacking-based weighted random forest models. The numerical results show that the proposed models are able to introduce significant improvements compared to regular random forest.
Performance-Agnostic Fusion of Probabilistic Classifier Outputs
Venue: arXiv cs.LG 2020
Year: 2020

We propose a method for combining probabilistic outputs of classifiers to make a single consensus class prediction when no further information about the individual classifiers is available, beyond that they have been trained for the same task. The lack of relevant prior information rules out typical applications of Bayesian or Dempster-Shafer methods, and the default approach here would be methods based on the principle of indifference, such as the sum or product rule, which essentially weight all classifiers equally. In contrast, our approach considers the diversity between the outputs of the various classifiers, iteratively updating predictions based on their correspondence with other predictions until the predictions converge to a consensus decision. The intuition behind this approach is that classifiers trained for the same task should typically exhibit regularities in their outputs on a new task; the predictions of classifiers which differ significantly from those of others are thus given less credence using our approach. The approach implicitly assumes a symmetric loss function, in that the relative cost of various prediction errors are not taken into account. Performance of the model is demonstrated on different benchmark datasets. Our proposed method works well in situations where accuracy is the performance metric; however, it does not output calibrated probabilities, so it is not suitable in situations where such probabilities are required for further processing.
A Deep 2-Dimensional Dynamical Spiking Neuronal Network for Temporal Encoding trained with STDP
Venue: arXiv cs.NE 2020
Year: 2020

The brain is known to be a highly complex, asynchronous dynamical system that is highly tailored to encode temporal information. However, recent deep learning approaches to not take advantage of this temporal coding. Spiking Neural Networks (SNNs) can be trained using biologically-realistic learning mechanisms, and can have neuronal activation rules that are biologically relevant. This type of network is also structured fundamentally around accepting temporal information through a time-decaying voltage update, a kind of input that current rate-encoding networks have difficulty with. Here we show that a large, deep layered SNN with dynamical, chaotic activity mimicking the mammalian cortex with biologically-inspired learning rules, such as STDP, is capable of encoding information from temporal data. We argue that the randomness inherent in the network weights allow the neurons to form groups that encode the temporal data being inputted after self-organizing with STDP. We aim to show that precise timing of input stimulus is critical in forming synchronous neural groups in a layered network. We analyze the network in terms of network entropy as a metric of information transfer. We hope to tackle two problems at once: the creation of artificial temporal neural systems for artificial intelligence, as well as solving coding mechanisms in the brain.
Characterizing Erasable Accounts in Ethereum
Venue: arXiv cs.CR 2020
Year: 2020

Being the most popular permissionless blockchain that supports smart contracts, Ethereum allows any user to create accounts on it. However, not all accounts matter. For example, the accounts due to attacks can be removed. In this paper, we conduct the first investigation on erasable accounts that can be removed to save system resources and even users' money (i.e., ETH or gas). In particular, we propose and develop a novel tool named GLASER, which analyzes the State DataBase of Ethereum to discover five kinds of erasable accounts. The experimental results show that GLASER can accurately reveal 508,482 erasable accounts and these accounts lead to users wasting more than 106 million dollars. GLASER can help stop further economic loss caused by these detected accounts. Moreover, GLASER characterizes the attacks/behaviors related to detected erasable accounts through graph analysis.
Applying a random projection algorithm to optimize machine learning model for predicting peritoneal metastasis in gastric cancer patients using CT images
Venue: arXiv cs.LG 2020
Year: 2020

Background and Objective: Non-invasively predicting the risk of cancer metastasis before surgery plays an essential role in determining optimal treatment methods for cancer patients (including who can benefit from neoadjuvant chemotherapy). Although developing radiomics based machine learning (ML) models has attracted broad research interest for this purpose, it often faces a challenge of how to build a highly performed and robust ML model using small and imbalanced image datasets. Methods: In this study, we explore a new approach to build an optimal ML model. A retrospective dataset involving abdominal computed tomography (CT) images acquired from 159 patients diagnosed with gastric cancer is assembled. Among them, 121 cases have peritoneal metastasis (PM), while 38 cases do not have PM. A computer-aided detection (CAD) scheme is first applied to segment primary gastric tumor volumes and initially computes 315 image features. Then, two Gradient Boosting Machine (GBM) models embedded with two different feature dimensionality reduction methods, namely, the principal component analysis (PCA) and a random projection algorithm (RPA) and a synthetic minority oversampling technique, are built to predict the risk of the patients having PM. All GBM models are trained and tested using a leave-one-case-out cross-validation method. Results: Results show that the GBM embedded with RPA yielded a significantly higher prediction accuracy (71.2%) than using PCA (65.2%) (p<0.05). Conclusions: The study demonstrated that CT images of the primary gastric tumors contain discriminatory information to predict the risk of PM, and RPA is a promising method to generate optimal feature vector, improving the performance of ML models of medical images.
Single-RF MIMO: From Spatial Modulation to Metasurface-Based Modulation
Venue: arXiv cs.IT 2020
Year: 2020

In multiple-input multiple-output (MIMO), multiple radio frequency (RF) chains are usually required to simultaneously transmit multiple data streams. As a special MIMO technology, spatial modulation (SM) activates one transmit antenna with one RF chain and exploits the index of the active antenna for information transfer at each time slot. Recently, reconfigurable metasurfaces have emerged as a promising technology that is able to reconfigure the wireless propagation environment by altering the amplitude and/or phase of the incident signal. In this article, we aim for the implementation of single-RF MIMO by shifting the focus from SM to metasurface-based modulation. Specifically, the principles of SM and metasurfaces are first presented. After reviewing the evolution of SM, we elaborate on the idea of metasurface-aided single-RF MIMO and discuss some implementations for it in line with notable variants of SM. A comparison between antenna-based and metasurface-based modulation is made to highlight the advantages of using metasurfaces. We finally investigate the research challenges and opportunities in the context of metasurface-based modulation.
Estimating the Brittleness of AI: Safety Integrity Levels and the Need for Testing Out-Of-Distribution Performance
Venue: arXiv cs.LG 2020
Year: 2020

Test, Evaluation, Verification, and Validation (TEVV) for Artificial Intelligence (AI) is a challenge that threatens to limit the economic and societal rewards that AI researchers have devoted themselves to producing. A central task of TEVV for AI is estimating brittleness, where brittleness implies that the system functions well within some bounds and poorly outside of those bounds. This paper argues that neither of those criteria are certain of Deep Neural Networks. First, highly touted AI successes (eg. image classification and speech recognition) are orders of magnitude more failure-prone than are typically certified in critical systems even within design bounds (perfectly in-distribution sampling). Second, performance falls off only gradually as inputs become further Out-Of-Distribution (OOD). Enhanced emphasis is needed on designing systems that are resilient despite failure-prone AI components as well as on evaluating and improving OOD performance in order to get AI to where it can clear the challenging hurdles of TEVV and certification.
Convolutional Nonlinear Dictionary with Cascaded Structure Filter Banks
Venue: arXiv cs.CV 2020
Year: 2020

This study proposes a convolutional nonlinear dictionary (CNLD) for image restoration using cascaded filter banks. Generally, convolutional neural networks (CNN) demonstrate their practicality in image restoration applications; however, existing CNNs are constructed without considering the relationship among atomic images (convolution kernels). As a result, there remains room for discussing the role of design spaces. To provide a framework for constructing an effective and structured convolutional network, this study proposes the CNLD. The backpropagation learning procedure is derived from certain image restoration experiments, and thereby the significance of CNLD is verified. It is demonstrated that the number of parameters is reduced while preserving the restoration performance.
Retaining Image Feature Matching Performance Under Low Light Conditions
Venue: arXiv cs.CV 2020
Year: 2020

Poor image quality in low light images may result in a reduced number of feature matching between images. In this paper, we investigate the performance of feature extraction algorithms in low light environments. To find an optimal setting to retain feature matching performance in low light images, we look into the effect of changing feature acceptance threshold for feature detector and adding pre-processing in the form of Low Light Image Enhancement (LLIE) prior to feature detection. We observe that even in low light images, feature matching using traditional hand-crafted feature detectors still performs reasonably well by lowering the threshold parameter. We also show that applying Low Light Image Enhancement (LLIE) algorithms can improve feature matching even more when paired with the right feature extraction algorithm.
Homotopy techniques for solving sparse column support determinantal polynomial systems
Venue: arXiv cs.SC 2020
Year: 2020

Let $\mathbf{K}$ be a field of characteristic zero with $\overline{\mathbf{K}}$ its algebraic closure. Given a sequence of polynomials $\mathbf{g} = (g_1, \ldots, g_s) \in \mathbf{K}[x_1, \ldots , x_n]^s$ and a polynomial matrix $\mathbf{F} = [f_{i,j}] \in \mathbf{K}[x_1, \ldots, x_n]^{p \times q}$, with $p \leq q$, we are interested in determining the isolated points of $V_p(\mathbf{F},\mathbf{g})$, the algebraic set of points in $\overline{\mathbf{K}}$ at which all polynomials in $\mathbf{g}$ and all $p$-minors of $\mathbf{F}$ vanish, under the assumption $n = q - p + s + 1$. Such polynomial systems arise in a variety of applications including for example polynomial optimization and computational geometry. We design a randomized sparse homotopy algorithm for computing the isolated points in $V_p(\mathbf{F},\mathbf{g})$ which takes advantage of the determinantal structure of the system defining $V_p(\mathbf{F}, \mathbf{g})$. Its complexity is polynomial in the maximum number of isolated solutions to such systems sharing the same sparsity pattern and in some combinatorial quantities attached to the structure of such systems. It is the first algorithm which takes advantage both on the determinantal structure and sparsity of input polynomials. We also derive complexity bounds for the particular but important case where $\mathbf{g}$ and the columns of $\mathbf{F}$ satisfy weighted degree constraints. Such systems arise naturally in the computation of critical points of maps restricted to algebraic sets when both are invariant by the action of the symmetric group.