OpenRaiser/Intern-Atlas huggingface dataset:
Gerrymandering: A Briber's Perspective
Venue: arXiv cs.GT 2019
Year: 2019

We initiate the study of bribery problem in the context of gerrymandering and reverse gerrymandering. In our most general problem, the input is a set of voters having votes over a set of alternatives, a graph on the voters, a partition of voters into connected districts, cost of every voter for changing her district, a budget for the briber, and a favorite alternative of the briber. The briber needs to compute if the given partition can be modified so that (i) the favorite alternative of the briber wins the resulting election, (ii) the modification is budget feasible, and (iii) every new district is connected. We study four natural variants of the above problem -- the graph on voter being arbitrary vs complete graph (corresponds to removing connectedness requirement for districts) and the cost of bribing every voter being uniform vs non-uniform. We show that all the four problems are NP-complete even under quite restrictive scenarios. Hence our results show that district based elections are quite resistant under this new kind of electoral attack. We complement our hardness results with polynomial time algorithms in some other cases.
HinDom: A Robust Malicious Domain Detection System based on Heterogeneous Information Network with Transductive Classification
Venue: arXiv cs.CR 2019
Year: 2019

Domain name system (DNS) is a crucial part of the Internet, yet has been widely exploited by cyber attackers. Apart from making static methods like blacklists or sinkholes infeasible, some weasel attackers can even bypass detection systems with machine learning based classifiers. As a solution to this problem, we propose a robust domain detection system named HinDom. Instead of relying on manually selected features, HinDom models the DNS scene as a Heterogeneous Information Network (HIN) consist of clients, domains, IP addresses and their diverse relationships. Besides, the metapath-based transductive classification method enables HinDom to detect malicious domains with only a small fraction of labeled samples. So far as we know, this is the first work to apply HIN in DNS analysis. We build a prototype of HinDom and evaluate it in CERNET2 and TUNET. The results reveal that HinDom is accurate, robust and can identify previously unknown malicious domains.
A Cost-Scaling Algorithm for Minimum-Cost Node-Capacitated Multiflow Problem
Venue: arXiv cs.DS 2019
Year: 2019

In this paper, we address the minimum-cost node-capacitated multiflow problem in an undirected network. For this problem, Babenko and Karzanov (2012) showed strongly polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial weakly polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in $O(m \log(nCD)\mathrm{SF}(kn, m, k))$ time, where $n$ is the number of nodes, $m$ is the number of edges, $k$ is the number of terminals, $C$ is the maximum node capacity, $D$ is the maximum edge cost, and $\mathrm{SF}(n', m', η)$ is the time complexity of solving the submodular flow problem in a network of $n'$ nodes, $m'$ edges, and a submodular function with $η$-time-computable exchange capacity. Our algorithm is built on discrete convex analysis on graph structures and the concept of reducible bisubmodular flows.
Modelling the Behavior Classification of Social News Aggregations Users
Venue: arXiv cs.CY 2019
Year: 2019

This paper deals with actual fuzzy logic approach for modelling the behavior classification of social news aggregations users. The peculiarities of the structure of informational content of communities on the basis of social news aggregations are explored. A formal model of social news aggregation model has been developed, which includes user of the social news aggregation on the basis of fuzzy measures of its characteristics. The method of behavioral classification of users and methods for structuring sections and discussions of social news aggregations are developed. The methods for determining the main characteristics of the users of the social news aggregation: activeness, creativeness, attractiveness, reactiveness, loyalty, is developed. Method for defining characteristics and classification of social news aggregations users is presented.
Knowledge distillation for optimization of quantized deep neural networks
Venue: arXiv cs.LG 2019
Year: 2019

Knowledge distillation (KD) is a very popular method for model size reduction. Recently, the technique is exploited for quantized deep neural networks (QDNNs) training as a way to restore the performance sacrificed by word-length reduction. KD, however, employs additional hyper-parameters, such as temperature, coefficient, and the size of teacher network for QDNN training. We analyze the effect of these hyper-parameters for QDNN optimization with KD. We find that these hyper-parameters are inter-related, and also introduce a simple and effective technique that reduces \textit{coefficient} during training. With KD employing the proposed hyper-parameters, we achieve the test accuracy of 92.7% and 67.0% on Resnet20 with 2-bit ternary weights for CIFAR-10 and CIFAR-100 data sets, respectively.
Explaining SDN Failures via Axiomatisations
Venue: arXiv cs.FL 2019
Year: 2019

This work introduces a concept of explanations with respect to the violation of safe behaviours within software defined networks (SDNs) expressible in NetKAT. The latter is a network programming language that is based on a well-studied mathematical structure, namely, Kleene Algebra with Tests (KAT). Amongst others, the mathematical foundation of NetKAT gave rise to a sound and complete equational theory. In our setting, a safe behaviour is characterised by a NetKAT policy which does not enable forwarding packets from ingress to an undesirable egress. Explanations for safety violations are derived in an equational fashion, based on a modification of the existing NetKAT axiomatisation.
Augmented Memory Networks for Streaming-Based Active One-Shot Learning
Venue: arXiv cs.LG 2019
Year: 2019

One of the major challenges in training deep architectures for predictive tasks is the scarcity and cost of labeled training data. Active Learning (AL) is one way of addressing this challenge. In stream-based AL, observations are continuously made available to the learner that have to decide whether to request a label or to make a prediction. The goal is to reduce the request rate while at the same time maximize prediction performance. In previous research, reinforcement learning has been used for learning the AL request/prediction strategy. In our work, we propose to equip a reinforcement learning process with memory augmented neural networks, to enhance the one-shot capabilities. Moreover, we introduce Class Margin Sampling (CMS) as an extension of the standard margin sampling to the reinforcement learning setting. This strategy aims to reduce training time and improve sample efficiency in the training process. We evaluate the proposed method on a classification task using empirical accuracy of label predictions and percentage of label requests. The results indicates that the proposed method, by making use of the memory augmented networks and CMS in the training process, outperforms existing baselines.
Epistemological Issues in Educational Data Mining
Venue: arXiv cs.CY 2019
Year: 2019

Educational Data Mining (EDM) shows interesting scientific results lately. However, little has been discussed about philosophical questions regarding the type of knowledge produced in this area. This paper aims to present two epistemological issues in EDM: (i) a question of ontological nature about the content of the knowledge obtained; and (ii) a question of deontological nature, about the guidelines and principles adopted by the researcher in education, to the detriment of the results of his own research. In the end, some considerations and guidelines are outlined as a result of the discussion of the issues raised.
A Deep, Forgetful Novelty-Seeking Movie Recommender Model
Venue: arXiv cs.IR 2019
Year: 2019

As more and more people shift their movie watching online, competition between movie viewing websites are getting more and more intense. Therefore, it has become incredibly important to accurately predict a given user's watching list to maximize the chances of keeping the user on the platform. Recent studies have suggested that the novelty-seeking propensity of users can impact their viewing behavior. In this paper, we aim to accurately model and describe this novelty-seeking trait across many users and timestamps driven by data, taking into consideration user forgetfulness. Compared to previous studies, we propose a more robust measure for novelty. Our model, termed Deep Forgetful Novelty-Seeking Model (DFNSM), leverages demographic information about users, genre information about movies, and novelty-seeking traits to predict the most likely next actions of a user. To evaluate the performance of our model, we conducted extensive experiments on a large movie rating dataset. The results reveal that DFNSM is very effective for movie recommendation.
Privacy with Surgical Robotics: Challenges in Applying Contextual Privacy Theory
Venue: arXiv cs.CR 2019
Year: 2019

The use of connected surgical robotics to automate medical procedures presents new privacy challenges. We argue that conventional patient consent protocols no longer work. Indeed robots that replace human surgeons take on an extraordinary level of responsibility. Surgeons undergo years of training and peer review in a strongly regulated environment, and derive trust via a patient's faith in the hospital system. Robots on the other hand derive trust differently, via the integrity of the software that governs their operation. From a privacy perspective, there are two fundamental shifts. First, the threat model has shifted from one where the humans involved were untrusted to one where the robotic software is untrusted. Second, the basic unit of privacy control is no longer a medical record, but is replaced by four new basic units: the subject on which the robot is taking action; the tools used by the robot; the sensors (i.e data) the robot can access; and, finally access to monitoring and calibration services which afford correct operation of the robot. We suggest that contextual privacy provides useful theoretical tools to solve the privacy problems posed by surgical robots. However, it also poses some challenges: not least that the complexity of the contextual-privacy policies, if rigorously specified to achieve verification and enforceability, will be exceedingly high to directly expose to humans that review contextual privacy policies. A medical robot works with both information and physical material. While informational norms allow for judgements about contextual integrity and the transmission principle governs the constraints applied on information transfer, nothing is said about material property. Certainly, contextual privacy provides an anchor for useful notions of privacy in this scenario and thus should be considered to be extended to cover both information and material flows.
Empirical Study of Diachronic Word Embeddings for Scarce Data
Venue: arXiv cs.CL 2019
Year: 2019

Word meaning change can be inferred from drifts of time-varying word embeddings. However, temporal data may be too sparse to build robust word embeddings and to discriminate significant drifts from noise. In this paper, we compare three models to learn diachronic word embeddings on scarce data: incremental updating of a Skip-Gram from Kim et al. (2014), dynamic filtering from Bamler and Mandt (2017), and dynamic Bernoulli embeddings from Rudolph and Blei (2018). In particular, we study the performance of different initialisation schemes and emphasise what characteristics of each model are more suitable to data scarcity, relying on the distribution of detected drifts. Finally, we regularise the loss of these models to better adapt to scarce data.
Parameterized Intractability of Even Set and Shortest Vector Problem
Venue: arXiv cs.CC 2019
Year: 2019

The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$, or in other words, whether there is a nonzero vector $\mathbf{x}$ such that $\mathbf A \mathbf{x}$ has at most $k$ nonzero coordinates. The question of whether $k$-Even Set is fixed parameter tractable (FPT) parameterized by the distance $k$ has been repeatedly raised in literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows (1999). In this work, we show that $k$-Even Set is W[1]-hard under randomized reductions. We also consider the parameterized $k$-Shortest Vector Problem (SVP), in which we are given a lattice whose basis vectors are integral and an integer $k$, and the goal is to determine whether the norm of the shortest vector (in the $\ell_p$ norm for some fixed $p$) is at most $k$. Similar to $k$-Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any $p > 1$, $k$-SVP is W[1]-hard to approximate (under randomized reductions) to some constant factor.
Poly-GAN: Multi-Conditioned GAN for Fashion Synthesis
Venue: arXiv cs.CV 2019
Year: 2019

We present Poly-GAN, a novel conditional GAN architecture that is motivated by Fashion Synthesis, an application where garments are automatically placed on images of human models at an arbitrary pose. Poly-GAN allows conditioning on multiple inputs and is suitable for many tasks, including image alignment, image stitching, and inpainting. Existing methods have a similar pipeline where three different networks are used to first align garments with the human pose, then perform stitching of the aligned garment and finally refine the results. Poly-GAN is the first instance where a common architecture is used to perform all three tasks. Our novel architecture enforces the conditions at all layers of the encoder and utilizes skip connections from the coarse layers of the encoder to the respective layers of the decoder. Poly-GAN is able to perform a spatial transformation of the garment based on the RGB skeleton of the model at an arbitrary pose. Additionally, Poly-GAN can perform image stitching, regardless of the garment orientation, and inpainting on the garment mask when it contains irregular holes. Our system achieves state-of-the-art quantitative results on Structural Similarity Index metric and Inception Score metric using the DeepFashion dataset.
Analysis and Optimization of Outage Probability in Multi-Intelligent Reflecting Surface-Assisted Systems
Venue: arXiv cs.IT 2019
Year: 2019

Intelligent reflecting surface (IRS) is envisioned to be a promising solution for designing spectral and energy efficient wireless systems. In this letter, we study a multi-IRS-assisted system under Rician fading where the phase shifts adapt to only the line of sight (LoS) components. First, we analyze and optimize the outage probability of the multi-IRS-assisted system in the slow fading scenario for the non-LoS (NLoS) components. We also show that the optimal outage probability decreases with the numbers of IRSs and elements of each IRS when the LoS components are stronger than the NLoS ones. Then, we characterize the asymptotically optimal outage probability in the high signal-to-noise ratio (SNR) regime, and show that it decreases with the powers of the LoS components. To the best of our knowledge, this is the first work that studies the outage probability in multi-IRS-assisted systems.
An Optimal Assistive Control Strategy based on User's Motor Goal Estimation
Venue: arXiv cs.RO 2019
Year: 2019

In this study, we propose an optimal assistive control strategy that uses estimated user's movement intention as the terminal cost function. We estimate the movement intention by observing human user's joint angle, angluar velocity, and muscle activities for very short period of time. A task-related low-dimensional feature space is extracted from the observed user's movement data. We assume that discrete number of optimal control laws associated to different target tasks are pre-computed. Then, the optimal assistive policy is derived by blending the pre-computed optimal control laws based on the linear Bellman combination method. Coefficients that determine how to blend the control laws are derived based on the low-dimensional feature value that represents the user's movement intention. To validate our proposed method, we conducted basketball throwing tasks. In these experiments, subjects were asked to throw a basketball into a hoop placed at different throwing distances. The distances from the throwing point to the hoop were estimated as the user's movement intention and the optimal control policies were derived by using our proposed method. The results showed that the basketball throwing performances of the subjects were mostly improved.
Understanding ML driven HPC: Applications and Infrastructure
Venue: arXiv cs.LG 2019
Year: 2019

We recently outlined the vision of "Learning Everywhere" which captures the possibility and impact of how learning methods and traditional HPC methods can be coupled together. A primary driver of such coupling is the promise that Machine Learning (ML) will give major performance improvements for traditional HPC simulations. Motivated by this potential, the ML around HPC class of integration is of particular significance. In a related follow-up paper, we provided an initial taxonomy for integrating learning around HPC methods. In this paper, which is part of the Learning Everywhere series, we discuss "how" learning methods and HPC simulations are being integrated to enhance effective performance of computations. This paper identifies several modes --- substitution, assimilation, and control, in which learning methods integrate with HPC simulations and provide representative applications in each mode. This paper discusses some open research questions and we hope will motivate and clear the ground for MLaroundHPC benchmarks.
Random Linear Network Coding on Programmable Switches
Venue: arXiv cs.NI 2019
Year: 2019

By extending the traditional store-and-forward mechanism, network coding has the capability to improve a network's throughput, robustness, and security. Given the fundamentally different packet processing required by this new paradigm and the inflexibility of hardware, existing solutions are based on software. As a result, they have limited performance and scalability, creating a barrier to its wide-spread adoption. By leveraging the recent advances in programmable networking hardware, in this paper we propose a random linear network coding data plane written in P4, as a first step towards a production-level platform. Our solution includes the ability to combine the payload of multiple packets and of executing the required Galois field operations, and shows promise to be practical even under the strict memory and processing constraints of switching hardware.
NimbRo Robots Winning RoboCup 2018 Humanoid AdultSize Soccer Competitions
Venue: arXiv cs.RO 2019
Year: 2019

Over the past few years, the Humanoid League rules have changed towards more realistic and challenging game environments, which encourage teams to advance their robot soccer performances. In this paper, we present the software and hardware designs that led our team NimbRo to win the competitions in the AdultSize league -- including the soccer tournament, the drop-in games, and the technical challenges at RoboCup 2018 in Montreal. Altogether, this resulted in NimbRo winning the Best Humanoid Award. In particular, we describe our deep-learning approaches for visual perception and our new fully 3D printed robot NimbRo-OP2X.
Evaluating Conformance Measures in Process Mining using Conformance Propositions (Extended version)
Venue: arXiv cs.AI 2019
Year: 2019

Process mining sheds new light on the relationship between process models and real-life processes. Process discovery can be used to learn process models from event logs. Conformance checking is concerned with quantifying the quality of a business process model in relation to event data that was logged during the execution of the business process. There exist different categories of conformance measures. Recall, also called fitness, is concerned with quantifying how much of the behavior that was observed in the event log fits the process model. Precision is concerned with quantifying how much behavior a process model allows for that was never observed in the event log. Generalization is concerned with quantifying how well a process model generalizes to behavior that is possible in the business process but was never observed in the event log. Many recall, precision, and generalization measures have been developed throughout the years, but they are often defined in an ad-hoc manner without formally defining the desired properties up front. To address these problems, we formulate 21 conformance propositions and we use these propositions to evaluate current and existing conformance measures. The goal is to trigger a discussion by clearly formulating the challenges and requirements (rather than proposing new measures). Additionally, this paper serves as an overview of the conformance checking measures that are available in the process mining area.
Utilizing Temporal Information in Deep Convolutional Network for Efficient Soccer Ball Detection and Tracking
Venue: arXiv cs.CV 2019
Year: 2019

Soccer ball detection is identified as one of the critical challenges in the RoboCup competition. It requires an efficient vision system capable of handling the task of detection with high precision and recall and providing robust and low inference time. In this work, we present a novel convolutional neural network (CNN) approach to detect the soccer ball in an image sequence. In contrast to the existing methods where only the current frame or an image is used for the detection, we make use of the history of frames. Using history allows to efficiently track the ball in situations where the ball disappears or gets partially occluded in some of the frames. Our approach exploits spatio-temporal correlation and detects the ball based on the trajectory of its movements. We present our results with three convolutional methods, namely temporal convolutional networks (TCN), ConvLSTM, and ConvGRU. We first solve the detection task for an image using fully convolutional encoder-decoder architecture, and later, we use it as an input to our temporal models and jointly learn the detection task in sequences of images. We evaluate all our experiments on a novel dataset prepared as a part of this work. Furthermore, we present empirical results to support the effectiveness of using the history of the ball in challenging scenarios.
Continuous-Time Trajectory Optimization for Decentralized Multi-Robot Navigation
Venue: arXiv cs.RO 2019
Year: 2019

Multi-robot systems have begun to permeate into a variety of different fields, but collision-free navigation in a decentralized manner is still an arduous task. Typically, the navigation of high speed multi-robot systems demands replanning of trajectories to avoid collisions with one another. This paper presents an online replanning algorithm for trajectory optimization in labeled multi-robot scenarios. With reliable communication of states among robots, each robot predicts a smooth continuous-time trajectory for every other remaining robots. Based on the knowledge of these predicted trajectories, each robot then plans a collision-free trajectory for itself. The collision-free trajectory optimization problem is cast as a non linear program (NLP) by exploiting polynomial based trajectory generation. The algorithm was tested in simulations on Gazebo with aerial robots.