OpenRaiser/Intern-Atlas huggingface dataset:
Improved Approximation for Maximum Edge Colouring Problem
Venue: arXiv cs.DM 2019
Year: 2019

The anti-Ramsey number, $ar(G, H)$ is the minimum integer $k$ such that in any edge colouring of $G$ with $k$ colours there is a rainbow subgraph isomorphic to $H$, i.e., a copy of $H$ with each of its edges assigned a different colour. The notion was introduced by Erd{ö}s and Simonovits in 1973. Since then the parameter has been studied extensively in combinatorics, also the particular case when $H$ is a star graph. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge $q$-colouring problem. In this paper, we study the maximum edge $2$-colouring problem from the approximation algorithm point of view. The case $q=2$ is particularly interesting due to its application in real-life problems. Algorithmically, this problem is known to be NP-hard for $q\ge 2$. For the case of $q=2$, it is also known that no polynomial-time algorithm can approximate to a factor less than $3/2$ assuming the unique games conjecture. Feng et al. showed a $2$-approximation algorithm for this problem. Later Adamaszek and Popa presented a $5/3$-approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say $M$) and different colours to the connected components of $G \setminus M$. In this article, we give a new analysis of the aforementioned algorithm leading to an improved approximation bound for triangle-free graphs with perfect matching. We also show a new lower bound when the input graph is triangle-free. The contribution of the paper is a completely new, deeper and closer analysis of how the optimum achieves a higher number of colours than the matching based algorithm, mentioned above.
Toward a better trade-off between performance and fairness with kernel-based distribution matching
Venue: arXiv cs.LG 2019
Year: 2019

As recent literature has demonstrated how classifiers often carry unintended biases toward some subgroups, deploying machine learned models to users demands careful consideration of the social consequences. How should we address this problem in a real-world system? How should we balance core performance and fairness metrics? In this paper, we introduce a MinDiff framework for regularizing classifiers toward different fairness metrics and analyze a technique with kernel-based statistical dependency tests. We run a thorough study on an academic dataset to compare the Pareto frontier achieved by different regularization approaches, and apply our kernel-based method to two large-scale industrial systems demonstrating real-world improvements.
Measuring Conversational Fluidity in Automated Dialogue Agents
Venue: arXiv cs.CL 2019
Year: 2019

We present an automated evaluation method to measure fluidity in conversational dialogue systems. The method combines various state of the art Natural Language tools into a classifier, and human ratings on these dialogues to train an automated judgment model. Our experiments show that the results are an improvement on existing metrics for measuring fluidity.
LPRNet: Lightweight Deep Network by Low-rank Pointwise Residual Convolution
Venue: arXiv cs.CV 2019
Year: 2019

Deep learning has become popular in recent years primarily due to the powerful computing device such as GPUs. However, deploying these deep models to end-user devices, smart phones, or embedded systems with limited resources is challenging. To reduce the computation and memory costs, we propose a novel lightweight deep learning module by low-rank pointwise residual (LPR) convolution, called LPRNet. Essentially, LPR aims at using low-rank approximation in pointwise convolution to further reduce the module size, while keeping depthwise convolutions as the residual module to rectify the LPR module. This is critical when the low-rankness undermines the convolution process. We embody our design by replacing modules of identical input-output dimension in MobileNet and ShuffleNetv2. Experiments on visual recognition tasks including image classification and face alignment on popular benchmarks show that our LPRNet achieves competitive performance but with significant reduction of Flops and memory cost compared to the state-of-the-art deep models focusing on model compression.
User Data Sharing Frameworks: A Blockchain-Based Incentive Solution
Venue: arXiv cs.CR 2019
Year: 2019

Currently, there is no universal method to track who shared what, with whom, when and for what purposes in a verifiable way to create an individual incentive for data owners. A platform that allows data owners to control, delete, and get rewards from sharing their data would be an important enabler of user data-sharing. We propose a usable blockchain- and smart contracts-based framework that allows users to store research data locally and share without losing control and ownership of it. We have created smart contracts for building automatic verification of the conditions for data access that also naturally supports building up a verifiable record of the provenance, incentives for users to share their data and accountability of access. The paper presents a review of the existing work of research data sharing, the proposed blockchain-based framework and an evaluation of the framework by measuring the transaction cost for smart contracts deployment. The results show that nodes responded quickly in all tested cases with a befitting transaction cost.
Relay Policy Learning: Solving Long-Horizon Tasks via Imitation and Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

We present relay policy learning, a method for imitation and reinforcement learning that can solve multi-stage, long-horizon robotic tasks. This general and universally-applicable, two-phase approach consists of an imitation learning stage that produces goal-conditioned hierarchical policies, and a reinforcement learning phase that finetunes these policies for task performance. Our method, while not necessarily perfect at imitation learning, is very amenable to further improvement via environment interaction, allowing it to scale to challenging long-horizon tasks. We simplify the long-horizon policy learning problem by using a novel data-relabeling algorithm for learning goal-conditioned hierarchical policies, where the low-level only acts for a fixed number of steps, regardless of the goal achieved. While we rely on demonstration data to bootstrap policy learning, we do not assume access to demonstrations of every specific tasks that is being solved, and instead leverage unstructured and unsegmented demonstrations of semantically meaningful behaviors that are not only less burdensome to provide, but also can greatly facilitate further improvement using reinforcement learning. We demonstrate the effectiveness of our method on a number of multi-stage, long-horizon manipulation tasks in a challenging kitchen simulation environment. Videos are available at https://relay-policy-learning.github.io/
Attention for Inference Compilation
Venue: arXiv cs.LG 2019
Year: 2019

We present a new approach to automatic amortized inference in universal probabilistic programs which improves performance compared to current methods. Our approach is a variation of inference compilation (IC) which leverages deep neural networks to approximate a posterior distribution over latent variables in a probabilistic program. A challenge with existing IC network architectures is that they can fail to model long-range dependencies between latent variables. To address this, we introduce an attention mechanism that attends to the most salient variables previously sampled in the execution of a probabilistic program. We demonstrate that the addition of attention allows the proposal distributions to better match the true posterior, enhancing inference about latent variables in simulators.
Yall should read this! Identifying Plurality in Second-Person Personal Pronouns in English Texts
Venue: arXiv cs.CL 2019
Year: 2019

Distinguishing between singular and plural "you" in English is a challenging task which has potential for downstream applications, such as machine translation or coreference resolution. While formal written English does not distinguish between these cases, other languages (such as Spanish), as well as other dialects of English (via phrases such as "yall"), do make this distinction. We make use of this to obtain distantly-supervised labels for the task on a large-scale in two domains. Following, we train a model to distinguish between the single/plural you, finding that although in-domain training achieves reasonable accuracy (over 77%), there is still a lot of room for improvement, especially in the domain-transfer scenario, which proves extremely challenging. Our code and data are publicly available.
KETO: Learning Keypoint Representations for Tool Manipulation
Venue: arXiv cs.RO 2019
Year: 2019

We aim to develop an algorithm for robots to manipulate novel objects as tools for completing different task goals. An efficient and informative representation would facilitate the effectiveness and generalization of such algorithms. For this purpose, we present KETO, a framework of learning keypoint representations of tool-based manipulation. For each task, a set of task-specific keypoints is jointly predicted from 3D point clouds of the tool object by a deep neural network. These keypoints offer a concise and informative description of the object to determine grasps and subsequent manipulation actions. The model is learned from self-supervised robot interactions in the task environment without the need for explicit human annotations. We evaluate our framework in three manipulation tasks with tool use. Our model consistently outperforms state-of-the-art methods in terms of task success rates. Qualitative results of keypoint prediction and tool generation are shown to visualize the learned representations.
Mellotron: Multispeaker expressive voice synthesis by conditioning on rhythm, pitch and global style tokens
Venue: arXiv cs.SD 2019
Year: 2019

Mellotron is a multispeaker voice synthesis model based on Tacotron 2 GST that can make a voice emote and sing without emotive or singing training data. By explicitly conditioning on rhythm and continuous pitch contours from an audio signal or music score, Mellotron is able to generate speech in a variety of styles ranging from read speech to expressive speech, from slow drawls to rap and from monotonous voice to singing voice. Unlike other methods, we train Mellotron using only read speech data without alignments between text and audio. We evaluate our models using the LJSpeech and LibriTTS datasets. We provide F0 Frame Errors and synthesized samples that include style transfer from other speakers, singers and styles not seen during training, procedural manipulation of rhythm and pitch and choir synthesis.
D-Point Trigonometric Path Planning based on Q-Learning in Uncertain Environments
Venue: arXiv cs.AI 2019
Year: 2019

Finding the optimum path for a robot for moving from start to the goal position through obstacles is still a challenging issue. This paper presents a novel path planning method, named D-point trigonometric, based on Q-learning algorithm for dynamic and uncertain environments, in which all the obstacles and the target are moving. We define a new state, action and reward functions for the Q-learning by which the agent can find the best action in every state to reach the goal in the most appropriate path. The D-point approach minimizes the possible number of states. Moreover, the experiments in Unity3D confirmed the high convergence speed, the high hit rate, as well as the low dependency on environmental parameters of the proposed method compared with an opponent approach.
Deep Learning and Control Algorithms of Direct Perception for Autonomous Driving
Venue: arXiv cs.LG 2019
Year: 2019

Based on the direct perception paradigm of autonomous driving, we investigate and modify the CNNs (convolutional neural networks) AlexNet and GoogLeNet that map an input image to few perception indicators (heading angle, distances to preceding cars, and distance to road centerline) for estimating driving affordances in highway traffic. We also design a controller with these indicators and the short-range sensor information of TORCS (the open racing car simulator) for driving simulated cars to avoid collisions. We collect a set of images from a TORCS camera in various driving scenarios, train these CNNs using the dataset, test them in unseen traffics, and find that they perform better than earlier algorithms and controllers in terms of training efficiency and driving stability. Source code and data are available on our website.
Making Predictive Coding Networks Generative
Venue: arXiv cs.NE 2019
Year: 2019

Predictive coding (PC) networks are a biologically interesting class of neural networks. Their layered hierarchy mimics the reciprocal connectivity pattern observed in the mammalian cortex, and they can be trained using local learning rules that approximate backpropagation [Bogacz, 2017]. However, despite having feedback connections that enable information to flow down the network hierarchy, discriminative PC networks are not generative. Clamping the output class and running the network to equilibrium yields an input sample that typically does not resemble the training input. This paper studies this phenomenon, and proposes a simple solution that promotes the generation of input samples that resemble the training inputs. Simple decay, a technique already in wide use in neural networks, pushes the PC network toward a unique minimum 2-norm solution, and that unique solution provably (for linear networks) matches the training inputs. The method also vastly improves the samples generated for nonlinear networks, as we demonstrate on MNIST.
Small Memory Robust Simulation of Client-Server Interactive Protocols over Oblivious Noisy Channels
Venue: arXiv cs.IT 2019
Year: 2019

We revisit the problem of low-memory robust simulation of interactive protocols over noisy channels. Haeupler [FOCS 2014] considered robust simulation of two-party interactive protocols over oblivious, as well as adaptive, noisy channels. Since the simulation does not need to have fixed communication pattern, the achieved communication rates can circumvent the lower bound proved by Kol and Raz [STOC 2013]. However, a drawback of this approach is that each party needs to remember the whole history of the simulated transcript. In a subsequent manuscript, Haeupler and Resch considered low-memory simulation. The idea was to view the original protocol as a computational DAG and only the identities of the nodes are saved (as opposed to the whole transcript history) for backtracking to reduce memory usage. In this paper, we consider low-memory robust simulation of more general client-server interactive protocols, in which a leader communicates with other members/servers, who do not communicate among themselves; this setting can be applied to information-theoretic multi-server Private Information Retrieval (PIR) schemes. We propose an information-theoretic technique that converts any correct PIR protocol that assumes reliable channels, into a protocol which is both correct and private in the presence of a noisy channel while keeping the space complexity to a minimum. Despite the huge attention that PIR protocols have received in the literature, the existing works assume that the parties communicate using noiseless channels.
SoulMate: Short-text author linking through Multi-aspect temporal-textual embedding
Venue: arXiv cs.CL 2019
Year: 2019

Linking authors of short-text contents has important usages in many applications, including Named Entity Recognition (NER) and human community detection. However, certain challenges lie ahead. Firstly, the input short-text contents are noisy, ambiguous, and do not follow the grammatical rules. Secondly, traditional text mining methods fail to effectively extract concepts through words and phrases. Thirdly, the textual contents are temporally skewed, which can affect the semantic understanding by multiple time facets. Finally, using the complementary knowledge-bases makes the results biased to the content of the external database and deviates the understanding and interpretation away from the real nature of the given short text corpus. To overcome these challenges, we devise a neural network-based temporal-textual framework that generates the tightly connected author subgraphs from microblog short-text contents. Our approach, on the one hand, computes the relevance score (edge weight) between the authors through considering a portmanteau of contents and concepts, and on the other hand, employs a stack-wise graph cutting algorithm to extract the communities of the related authors. Experimental results show that compared to other knowledge-centered competitors, our multi-aspect vector space model can achieve a higher performance in linking short-text authors. Additionally, given the author linking task, the more comprehensive the dataset is, the higher the significance of the extracted concepts will be.
Immersive Insights: A Hybrid Analytics System for Collaborative Exploratory Data Analysis
Venue: arXiv cs.HC 2019
Year: 2019

In the past few years, augmented reality (AR) and virtual reality (VR) technologies have experienced terrific improvements in both accessibility and hardware capabilities, encouraging the application of these devices across various domains. While researchers have demonstrated the possible advantages of AR and VR for certain data science tasks, it is still unclear how these technologies would perform in the context of exploratory data analysis (EDA) at large. In particular, we believe it is important to better understand which level of immersion EDA would concretely benefit from, and to quantify the contribution of AR and VR with respect to standard analysis workflows. In this work, we leverage a Dataspace reconfigurable hybrid reality environment to study how data scientists might perform EDA in a co-located, collaborative context. Specifically, we propose the design and implementation of Immersive Insights, a hybrid analytics system combining high-resolution displays, table projections, and augmented reality (AR) visualizations of the data. We conducted a two-part user study with twelve data scientists, in which we evaluated how different levels of data immersion affect the EDA process and compared the performance of Immersive Insights with a state-of-the-art, non-immersive data analysis system.
A geometric interpretation of stochastic gradient descent using diffusion metrics
Venue: arXiv cs.LG 2019
Year: 2019

Stochastic gradient descent (SGD) is a key ingredient in the training of deep neural networks and yet its geometrical significance appears elusive. We study a deterministic model in which the trajectories of our dynamical systems are described via geodesics of a family of metrics arising from the diffusion matrix. These metrics encode information about the highly non-isotropic gradient noise in SGD. We establish a parallel with General Relativity models, where the role of the electromagnetic field is played by the gradient of the loss function. We compute an example of a two layer network.
Annual Interruption Rate as a KPI, its measurement and comparison
Venue: arXiv cs.DC 2019
Year: 2019

This article is divided into two chapters. The first chapter describes the failure rate as a KPI and studies its properties. The second one goes over ways to compare this KPI across two groups using the concepts of statistical hypothesis testing. In section 1., we will motivate the failure rate as a KPI (in Azure, it is dubbed `Annual Interruption Rate' or AIR. In section 3, we will discuss measuring failure rate from logs machines typically generate. In section 1.2, we will discuss the problem of measuring it from real-world data. In section 2.1, we will discuss the general concepts of hypothesis testing. In section 2.2, we will go over some general count distributions for modeling Azure reboots. In section 2.3, we will go over some experiments on applying various hypothesis tests to simulated data. In section 2.4, we will discuss some applications of this work like using these statistical methods to catch regressions in failure rate and how long we need to let changes to the system `bake' before we are reasonably sure they didn't regress failure rate.
Towards Extracting Highlights From Recorded Live Videos: An Implicit Crowdsourcing Approach
Venue: arXiv cs.DB 2019
Year: 2019

Live streaming platforms need to store a lot of recorded live videos on a daily basis. An important problem is how to automatically extract highlights (i.e., attractive short video clips) from these massive, long recorded live videos. One approach is to directly apply a highlight extraction algorithm to video content. However, algorithmic approaches are either domain-specific, which require experts to spend a long time to design, or resource-intensive, which require a lot of training data and/or computing resources. In this paper, we propose Lightor, a novel implicit crowdsourcing approach to overcome these limitations. The key insight is to collect users' natural interactions with a live streaming platform, and then leverage them to detect highlights. Lightor consists of two major components. Highlight Initializer collects time-stamped chat messages from a live video and then uses them to predict approximate highlight positions. Highlight Extractor keeps track of how users interact with these approximate highlight positions and then refines these positions iteratively. We find that the collected user chat and interaction data are very noisy, and propose effective techniques to deal with noise. Lightor can be easily deployed into existing live streaming platforms, or be implemented as a web browser extension. We recruit hundreds of users from Amazon Mechanical Turk, and evaluate the performance of Lightor using two popular games in Twitch. The results show that Lightor can achieve high extraction precision with a small set of training data and low computing resources.
Spectral Algorithm for Low-rank Multitask Regression
Venue: arXiv cs.LG 2019
Year: 2019

Multitask learning, i.e. taking advantage of the relatedness of individual tasks in order to improve performance on all of them, is a core challenge in the field of machine learning. We focus on matrix regression tasks where the rank of the weight matrix is constrained to reduce sample complexity. We introduce the common mechanism regression (CMR) model which assumes a shared left low-rank component across all tasks, but allows an individual per-task right low-rank component. This dramatically reduces the number of samples needed for accurate estimation. The problem of jointly recovering the common and the local components has a non-convex bi-linear structure. We overcome this hurdle and provide a provably beneficial non-iterative spectral algorithm. Appealingly, the solution has favorable behavior as a function of the number of related tasks and the small number of samples available for each one. We demonstrate the efficacy of our approach for the challenging task of remote river discharge estimation across multiple river sites, where data for each task is naturally scarce. In this scenario sharing a low-rank component between the tasks translates to a shared spectral reflection of the water, which is a true underlying physical model. We also show the benefit of the approach on the markedly different setting of image classification where the common component can be interpreted as the shared convolution filters.