OpenRaiser/Intern-Atlas huggingface dataset:
Unfairness Discovery and Prevention For Few-Shot Regression
Venue: arXiv cs.LG 2020
Year: 2020

We study fairness in supervised few-shot meta-learning models that are sensitive to discrimination (or bias) in historical data. A machine learning model trained based on biased data tends to make unfair predictions for users from minority groups. Although this problem has been studied before, existing methods mainly aim to detect and control the dependency effect of the protected variables (e.g. race, gender) on target prediction based on a large amount of training data. These approaches carry two major drawbacks that (1) lacking showing a global cause-effect visualization for all variables; (2) lacking generalization of both accuracy and fairness to unseen tasks. In this work, we first discover discrimination from data using a causal Bayesian knowledge graph which not only demonstrates the dependency of the protected variable on target but also indicates causal effects between all variables. Next, we develop a novel algorithm based on risk difference in order to quantify the discriminatory influence for each protected variable in the graph. Furthermore, to protect prediction from unfairness, a fast-adapted bias-control approach in meta-learning is proposed, which efficiently mitigates statistical disparity for each task and it thus ensures independence of protected attributes on predictions based on biased and few-shot data samples. Distinct from existing meta-learning models, group unfairness of tasks are efficiently reduced by leveraging the mean difference between (un)protected groups for regression problems. Through extensive experiments on both synthetic and real-world data sets, we demonstrate that our proposed unfairness discovery and prevention approaches efficiently detect discrimination and mitigate biases on model output as well as generalize both accuracy and fairness to unseen tasks with a limited amount of training samples.
Algorithms for a Topology-aware Massively Parallel Computation Model
Venue: arXiv cs.DB 2020
Year: 2020

Most of the prior work in massively parallel data processing assumes homogeneity, i.e., every computing unit has the same computational capability, and can communicate with every other unit with the same latency and bandwidth. However, this strong assumption of a uniform topology rarely holds in practical settings, where computing units are connected through complex networks. To address this issue, Blanas et al. recently proposed a topology-aware massively parallel computation model that integrates the network structure and heterogeneity in the modeling cost. The network is modeled as a directed graph, where each edge is associated with a cost function that depends on the data transferred between the two endpoints. The computation proceeds in synchronous rounds, and the cost of each round is measured as the maximum cost over all the edges in the network. In this work, we take the first step into investigating three fundamental data processing tasks in this topology-aware parallel model: set intersection, cartesian product, and sorting. We focus on network topologies that are tree topologies, and present both lower bounds, as well as (asymptotically) matching upper bounds. The optimality of our algorithms is with respect to the initial data distribution among the network nodes, instead of assuming worst-case distribution as in previous results. Apart from the theoretical optimality of our results, our protocols are simple, use a constant number of rounds, and we believe can be implemented in practical settings as well.
Theoretical Analysis of the Advantage of Deepening Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

We propose two new criteria to understand the advantage of deepening neural networks. It is important to know the expressivity of functions computable by deep neural networks in order to understand the advantage of deepening neural networks. Unless deep neural networks have enough expressivity, they cannot have good performance even though learning is successful. In this situation, the proposed criteria contribute to understanding the advantage of deepening neural networks since they can evaluate the expressivity independently from the efficiency of learning. The first criterion shows the approximation accuracy of deep neural networks to the target function. This criterion has the background that the goal of deep learning is approximating the target function by deep neural networks. The second criterion shows the property of linear regions of functions computable by deep neural networks. This criterion has the background that deep neural networks whose activation functions are piecewise linear are also piecewise linear. Furthermore, by the two criteria, we show that to increase layers is more effective than to increase units at each layer on improving the expressivity of deep neural networks.
Understanding Fairness of Gender Classification Algorithms Across Gender-Race Groups
Venue: arXiv cs.CV 2020
Year: 2020

Automated gender classification has important applications in many domains, such as demographic research, law enforcement, online advertising, as well as human-computer interaction. Recent research has questioned the fairness of this technology across gender and race. Specifically, the majority of the studies raised the concern of higher error rates of the face-based gender classification system for darker-skinned people like African-American and for women. However, to date, the majority of existing studies were limited to African-American and Caucasian only. The aim of this paper is to investigate the differential performance of the gender classification algorithms across gender-race groups. To this aim, we investigate the impact of (a) architectural differences in the deep learning algorithms and (b) training set imbalance, as a potential source of bias causing differential performance across gender and race. Experimental investigations are conducted on two latest large-scale publicly available facial attribute datasets, namely, UTKFace and FairFace. The experimental results suggested that the algorithms with architectural differences varied in performance with consistency towards specific gender-race groups. For instance, for all the algorithms used, Black females (Black race in general) always obtained the least accuracy rates. Middle Eastern males and Latino females obtained higher accuracy rates most of the time. Training set imbalance further widens the gap in the unequal accuracy rates across all gender-race groups. Further investigations using facial landmarks suggested that facial morphological differences due to the bone structure influenced by genetic and environmental factors could be the cause of the least performance of Black females and Black race, in general.
On One-way Functions and Kolmogorov Complexity
Venue: arXiv cs.CC 2020
Year: 2020

We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial $t(n)\geq (1+\varepsilon)n, \varepsilon>0$, the following are equivalent: - One-way functions exists (which in turn is equivalent to the existence of secure private-key encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more); - $t$-time bounded Kolmogorov Complexity, $K^t$, is mildly hard-on-average (i.e., there exists a polynomial $p(n)>0$ such that no PPT algorithm can compute $K^t$, for more than a $1-\frac{1}{p(n)}$ fraction of $n$-bit strings). In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography.
Practical Aspect of Privacy-Preserving Data Publishing in Process Mining
Venue: arXiv cs.CR 2020
Year: 2020

Process mining techniques such as process discovery and conformance checking provide insights into actual processes by analyzing event data that are widely available in information systems. These data are very valuable, but often contain sensitive information, and process analysts need to balance confidentiality and utility. Privacy issues in process mining are recently receiving more attention from researchers which should be complemented by a tool to integrate the solutions and make them available in the real world. In this paper, we introduce a Python-based infrastructure implementing state-of-the-art privacy preservation techniques in process mining. The infrastructure provides a hierarchy of usages from single techniques to the collection of techniques, integrated as web-based tools. Our infrastructure manages both standard and non-standard event data resulting from privacy preservation techniques. It also stores explicit privacy metadata to track the modifications applied to protect sensitive data.
Best Practices for Managing Data Annotation Projects
Venue: arXiv cs.CY 2020
Year: 2020

Annotation is the labeling of data by human effort. Annotation is critical to modern machine learning, and Bloomberg has developed years of experience of annotation at scale. This report captures a wealth of wisdom for applied annotation projects, collected from more than 30 experienced annotation project managers in Bloomberg's Global Data department.
Timbre Space Representation of a Subtractive Synthesizer
Venue: arXiv cs.SD 2020
Year: 2020

In this study, we produce a geometrically scaled perceptual timbre space from dissimilarity ratings of subtractive synthesized sounds and correlate the resulting dimensions with a set of acoustic descriptors. We curate a set of 15 sounds, produced by a synthesis model that uses varying source waveforms, frequency modulation (FM) and a lowpass filter with an enveloped cutoff frequency. Pairwise dissimilarity ratings were collected within an online browser-based experiment. We hypothesized that a varied waveform input source and enveloped filter would act as the main vehicles for timbral variation, providing novel acoustic correlates for the perception of synthesized timbres.
Deep Neural Networks with Short Circuits for Improved Gradient Learning
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks have achieved great success both in computer vision and natural language processing tasks. However, mostly state-of-art methods highly rely on external training or computing to improve the performance. To alleviate the external reliance, we proposed a gradient enhancement approach, conducted by the short circuit neural connections, to improve the gradient learning of deep neural networks. The proposed short circuit is a unidirectional connection that single back propagates the sensitive from the deep layer to the shallows. Moreover, the short circuit formulates to be a gradient truncation of its crossing layers which can plug into the backbone deep neural networks without introducing external training parameters. Extensive experiments demonstrate deep neural networks with our short circuit gain a large margin over the baselines on both computer vision and natural language processing tasks.
Evaluation of an indoor localization system for a mobile robot
Venue: arXiv cs.RO 2020
Year: 2020

Although indoor localization has been a wide researched topic, obtained results may not fit the requirements that some domains need. Most approaches are not able to precisely localize a fast moving object even with a complex installation, which makes their implementation in the automated driving domain complicated. In this publication, common technologies were analyzed and a commercial product, called Marvelmind Indoor GPS, was chosen for our use case in which both ultrasound and radio frequency communications are used. The evaluation is given in a first moment on small indoor scenarios with static and moving objects. Further tests were done on wider areas, where the system is integrated within our Robotics Operating System (ROS)-based self-developed 'Smart PhysIcal Demonstration and evaluation Robot (SPIDER)' and the results of these outdoor tests are compared with the obtained localization by the installed GPS on the robot. Finally, the next steps to improve the results in further developments are discussed.
Anatomy of a Rumour: Social media and the suicide of Sushant Singh Rajput
Venue: arXiv cs.SI 2020
Year: 2020

The suicide of Indian actor Sushant Singh Rajput in the midst of the COVID-19 lockdown triggered a media frenzy of prime time coverage that lasted several months and became a political hot button issue. Using data from Twitter, YouTube, and an archive of debunked misinformation stories, we found two important patterns. First, that retweet rates on Twitter clearly suggest that commentators benefited from talking about the case, which got higher engagement than other topics. Second, that politicians, in particular, were instrumental in changing the course of the discourse by referring to the case as 'murder', rather than 'suicide'. In conclusion, we consider the effects of Rajput's outsider status as a small-town implant in the film industry within the broader narrative of systemic injustice, as well as the gendered aspects of mob justice that have taken aim at his former partner in the months since.
Uncovering the fragility of large-scale engineering project networks
Venue: arXiv cs.SI 2020
Year: 2020

Engineering projects are notoriously hard to complete on-time, with project delays often theorised to propagate across interdependent activities. Here, we use a novel dataset consisting of activity networks from 14 diverse, large-scale engineering projects to uncover network properties that impact timely project completion. We provide the first empirical evidence of the infectious nature of activity deviations, where perturbations in the delivery of a single activity can impact up to 4 activities downstream, leading to large perturbation cascades. We further show that perturbation clustering significantly affects project overall delays. Finally, we find that poorly performing projects have their highest perturbations in high reach nodes, which can lead to largest cascades, while well performing projects have perturbations in low reach nodes, resulting in localised cascades. Altogether, these findings pave the way for a network-science framework that can materially enhance the delivery of large-scale engineering projects.
Generating Commonsense Explanation by Extracting Bridge Concepts from Reasoning Paths
Venue: arXiv cs.CL 2020
Year: 2020

Commonsense explanation generation aims to empower the machine's sense-making capability by generating plausible explanations to statements against commonsense. While this task is easy to human, the machine still struggles to generate reasonable and informative explanations. In this work, we propose a method that first extracts the underlying concepts which are served as \textit{bridges} in the reasoning chain and then integrates these concepts to generate the final explanation. To facilitate the reasoning process, we utilize external commonsense knowledge to build the connection between a statement and the bridge concepts by extracting and pruning multi-hop paths to build a subgraph. We design a bridge concept extraction model that first scores the triples, routes the paths in the subgraph, and further selects bridge concepts with weak supervision at both the triple level and the concept level. We conduct experiments on the commonsense explanation generation task and our model outperforms the state-of-the-art baselines in both automatic and human evaluation.
Scalable Recommendation of Wikipedia Articles to Editors Using Representation Learning
Venue: arXiv cs.IR 2020
Year: 2020

Wikipedia is edited by volunteer editors around the world. Considering the large amount of existing content (e.g. over 5M articles in English Wikipedia), deciding what to edit next can be difficult, both for experienced users that usually have a huge backlog of articles to prioritize, as well as for newcomers who that might need guidance in selecting the next article to contribute. Therefore, helping editors to find relevant articles should improve their performance and help in the retention of new editors. In this paper, we address the problem of recommending relevant articles to editors. To do this, we develop a scalable system on top of Graph Convolutional Networks and Doc2Vec, learning how to represent Wikipedia articles and deliver personalized recommendations for editors. We test our model on editors' histories, predicting their most recent edits based on their prior edits. We outperform competitive implicit-feedback collaborative-filtering methods such as WMRF based on ALS, as well as a traditional IR-method such as content-based filtering based on BM25. All of the data used on this paper is publicly available, including graph embeddings for Wikipedia articles, and we release our code to support replication of our experiments. Moreover, we contribute with a scalable implementation of a state-of-art graph embedding algorithm as current ones cannot efficiently handle the sheer size of the Wikipedia graph.
On the Parameterized Complexity of \textsc{Maximum Degree Contraction} Problem
Venue: arXiv cs.DS 2020
Year: 2020

In the \textsc{Maximum Degree Contraction} problem, input is a graph $G$ on $n$ vertices, and integers $k, d$, and the objective is to check whether $G$ can be transformed into a graph of maximum degree at most $d$, using at most $k$ edge contractions. A simple brute-force algorithm that checks all possible sets of edges for a solution runs in time $n^{\mathcal{O}(k)}$. As our first result, we prove that this algorithm is asymptotically optimal, upto constants in the exponents, under Exponential Time Hypothesis (Ð). Belmonte, Golovach, van't Hof, and Paulusma studied the problem in the realm of Parameterized Complexity and proved, among other things, that it admits an \FPT\ algorithm running in time $(d + k)^{2k} \cdot n^{\mathcal{O}(1)} = 2^{\mathcal{O}(k \log (k+d) )} \cdot n^{\mathcal{O}(1)}$, and remains \NP-hard for every constant $d \ge 2$ (Acta Informatica $(2014)$). We present a different \FPT\ algorithm that runs in time $2^{\mathcal{O}(dk)} \cdot n^{\mathcal{O}(1)}$. In particular, our algorithm runs in time $2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)}$, for every fixed $d$. In the same article, the authors asked whether the problem admits a polynomial kernel, when parameterized by $k + d$. We answer this question in the negative and prove that it does not admit a polynomial compression unless $\NP \subseteq \coNP/poly$.
Design and Evaluation of a Receiver for Wired Nano-Communication Networks
Venue: arXiv cs.ET 2020
Year: 2020

In this paper, we propose a bio-inspired receiver, which detects the electrons transmitted through a nanowire, then, it converts the detected information into a blue light using bioluminescence. Using light allows the designed receiver to also act as a relay for the nearest gateway (photo-detector). We simulate the construction of the nanowire, present its electrical characteristics and calculate its maximum throughput for a better design of the receiver. The designed receiver contains two parts, a part that detects the transmitted electrons, which we model by using an equivalent circuit, and a part that converts the detected electrons into a blue light. We derive the analytical expressions of the equivalent circuit's components, and we calculate the emitted photons for each electrical pulse detected. We also propose modulation techniques that guaranty an effective decoding of the information. We send a binary message and we follow the electron detection process of the proposed receiver until light emission and we calculate the Bit Error Rate (BER) to evaluate the performance of the designed receiver. The results of this study show that the designed receiver can accurately detect the electrons sent through a conductive nanowire in wired nano-communication networks, and that it can also act as a relay for the nearest gateway.
Novel Keyword Extraction and Language Detection Approaches
Venue: arXiv cs.CL 2020
Year: 2020

Fuzzy string matching and language classification are important tools in Natural Language Processing pipelines, this paper provides advances in both areas. We propose a fast novel approach to string tokenisation for fuzzy language matching and experimentally demonstrate an 83.6% decrease in processing time with an estimated improvement in recall of 3.1% at the cost of a 2.6% decrease in precision. This approach is able to work even where keywords are subdivided into multiple words, without needing to scan character-to-character. So far there has been little work considering using metadata to enhance language classification algorithms. We provide observational data and find the Accept-Language header is 14% more likely to match the classification than the IP Address.
PK-GCN: Prior Knowledge Assisted Image Classification using Graph Convolution Networks
Venue: arXiv cs.CV 2020
Year: 2020

Deep learning has gained great success in various classification tasks. Typically, deep learning models learn underlying features directly from data, and no underlying relationship between classes are included. Similarity between classes can influence the performance of classification. In this article, we propose a method that incorporates class similarity knowledge into convolutional neural networks models using a graph convolution layer. We evaluate our method on two benchmark image datasets: MNIST and CIFAR10, and analyze the results on different data and model sizes. Experimental results show that our model can improve classification accuracy, especially when the amount of available data is small.
A New Approach for Tactical Decision Making in Lane Changing: Sample Efficient Deep Q Learning with a Safety Feedback Reward
Venue: arXiv cs.AI 2020
Year: 2020

Automated lane change is one of the most challenging task to be solved of highly automated vehicles due to its safety-critical, uncertain and multi-agent nature. This paper presents the novel deployment of the state of art Q learning method, namely Rainbow DQN, that uses a new safety driven rewarding scheme to tackle the issues in an dynamic and uncertain simulation environment. We present various comparative results to show that our novel approach of having reward feedback from the safety layer dramatically increases both the agent's performance and sample efficiency. Furthermore, through the novel deployment of Rainbow DQN, it is shown that more intuition about the agent's actions is extracted by examining the distributions of generated Q values of the agents. The proposed algorithm shows superior performance to the baseline algorithm in the challenging scenarios with only 200000 training steps (i.e. equivalent to 55 hours driving).
On the signed chromatic number of some classes of graphs
Venue: arXiv cs.DM 2020
Year: 2020

A signed graph $(G, σ)$ is a graph $G$ along with a function $σ: E(G) \to \{+,-\}$. A closed walk of a signed graph is positive (resp., negative) if it has an even (resp., odd) number of negative edges, counting repetitions. A homomorphism of a (simple) signed graph to another signed graph is a vertex-mapping that preserves adjacencies and signs of closed walks. The signed chromatic number of a signed graph $(G, σ)$ is the minimum number of vertices $|V(H)|$ of a signed graph $(H, π)$ to which $(G, σ)$ admits a homomorphism.Homomorphisms of signed graphs have been attracting growing attention in the last decades, especially due to their strong connections to the theories of graph coloring and graph minors. These homomorphisms have been particularly studied through the scope of the signed chromatic number. In this work, we provide new results and bounds on the signed chromatic number of several families of signed graphs (planar graphs, triangle-free planar graphs, $K_n$-minor-free graphs, and bounded-degree graphs).