OpenRaiser/Intern-Atlas huggingface dataset:
Privacy-Preserving Distributed Learning in the Analog Domain
Venue: arXiv cs.LG 2020
Year: 2020

We consider the critical problem of distributed learning over data while keeping it private from the computational servers. The state-of-the-art approaches to this problem rely on quantizing the data into a finite field, so that the cryptographic approaches for secure multiparty computing can then be employed. These approaches, however, can result in substantial accuracy losses due to fixed-point representation of the data and computation overflows. To address these critical issues, we propose a novel algorithm to solve the problem when data is in the analog domain, e.g., the field of real/complex numbers. We characterize the privacy of the data from both information-theoretic and cryptographic perspectives, while establishing a connection between the two notions in the analog domain. More specifically, the well-known connection between the distinguishing security (DS) and the mutual information security (MIS) metrics is extended from the discrete domain to the continues domain. This is then utilized to bound the amount of information about the data leaked to the servers in our protocol, in terms of the DS metric, using well-known results on the capacity of single-input multiple-output (SIMO) channel with correlated noise. It is shown how the proposed framework can be adopted to do computation tasks when data is represented using floating-point numbers. We then show that this leads to a fundamental trade-off between the privacy level of data and accuracy of the result. As an application, we also show how to train a machine learning model while keeping the data as well as the trained model private. Then numerical results are shown for experiments on the MNIST dataset. Furthermore, experimental advantages are shown comparing to fixed-point implementations over finite fields.
A Hölderian backtracking method for min-max and min-min problems
Venue: arXiv cs.LG 2020
Year: 2020

We present a new algorithm to solve min-max or min-min problems out of the convex world. We use rigidity assumptions, ubiquitous in learning, making our method applicable to many optimization problems. Our approach takes advantage of hidden regularity properties and allows us to devise a simple algorithm of ridge type. An original feature of our method is to come with automatic step size adaptation which departs from the usual overly cautious backtracking methods. In a general framework, we provide convergence theoretical guarantees and rates. We apply our findings on simple GAN problems obtaining promising numerical results.
Parameterized Complexity of Graph Burning
Venue: arXiv cs.DS 2020
Year: 2020

Graph Burning asks, given a graph $G = (V,E)$ and an integer $k$, whether there exists $(b_{0},\dots,b_{k-1}) \in V^{k}$ such that every vertex in $G$ has distance at most $i$ from some $b_{i}$. This problem is known to be NP-complete even on connected caterpillars of maximum degree $3$. We study the parameterized complexity of this problem and answer all questions arose by Kare and Reddy [IWOCA 2019] about parameterized complexity of the problem. We show that the problem is W[2]-complete parameterized by $k$ and that it does no admit a polynomial kernel parameterized by vertex cover number unless $\mathrm{NP} \subseteq \mathrm{coNP/poly}$. We also show that the problem is fixed-parameter tractable parameterized by clique-width plus the maximum diameter among all connected components. This implies the fixed-parameter tractability parameterized by modular-width, by treedepth, and by distance to cographs. Although the parameterization by distance to split graphs cannot be handled with the clique-width argument, we show that this is also tractable by a reduction to a generalized problem with a smaller solution size.
Two-stream Fusion Model for Dynamic Hand Gesture Recognition using 3D-CNN and 2D-CNN Optical Flow guided Motion Template
Venue: arXiv cs.CV 2020
Year: 2020

The use of hand gestures can be a useful tool for many applications in the human-computer interaction community. In a broad range of areas hand gesture techniques can be applied specifically in sign language recognition, robotic surgery, etc. In the process of hand gesture recognition, proper detection, and tracking of the moving hand become challenging due to the varied shape and size of the hand. Here the objective is to track the movement of the hand irrespective of the shape, size, and color of the hand. And, for this, a motion template guided by optical flow (OFMT) is proposed. OFMT is a compact representation of the motion information of a gesture encoded into a single image. In the experimentation, different datasets using bare hand with an open palm, and folded palm wearing green-glove are used, and in both cases, we could generate the OFMT images with equal precision. Recently, deep network-based techniques have shown impressive improvements as compared to conventional hand-crafted feature-based techniques. Moreover, in the literature, it is seen that the use of different streams with informative input data helps to increase the performance in the recognition accuracy. This work basically proposes a two-stream fusion model for hand gesture recognition and a compact yet efficient motion template based on optical flow. Specifically, the two-stream network consists of two layers: a 3D convolutional neural network (C3D) that takes gesture videos as input and a 2D-CNN that takes OFMT images as input. C3D has shown its efficiency in capturing spatio-temporal information of a video. Whereas OFMT helps to eliminate irrelevant gestures providing additional motion information. Though each stream can work independently, they are combined with a fusion scheme to boost the recognition results. We have shown the efficiency of the proposed two-stream network on two databases.
The Effect of Multiple Access Categories on the MAC Layer Performance of IEEE 802.11p
Venue: arXiv cs.NI 2020
Year: 2020

The enhanced distributed channel access (EDCA) mechanism enables IEEE 802.11p to accommodate differential quality of service (QoS) levels in vehicle-to-vehicle (V2V) communications, through four access categories (ACs). This paper presents multi-dimensional discrete-time Markov chain (DTMC) based model to study the effect of parallel operation of the ACs on the medium access control (MAC) layer performance of ITS-G5 IEEE 802.11p. The overall model consists of four queue models with their respective traffic generators, which are appropriately linked with the DTMCs modeling the operation of each AC. Closed-form solutions for the steady-state probabilities of the models are obtained, which are then utilized to derive expressions for key performance indicators at the MAC layer. An application for a highway scenario is presented to draw insights on the performance. The results show how the performance measures vary among ACs according to their priority levels, and emphasize the importance of analytical modeling of the parallel operation of all four ACs.
A Case Study on Video Color Transfer: Exploring User Motivations, Expectations, and Satisfaction
Venue: arXiv cs.HC 2020
Year: 2020

Multimedia and creativity software products are being used to edit and control various elements of creative media practices. These days, the technical affordances of mobile multimedia devices and the advent of high-speed 5G internet access mean that these abilities are simpler and more readily available to be harnessed by mobile applications. In this paper, using a prototype application, we discuss how potential users of such technology are motivated to use a video recoloring application and explore the role that user expectation and satisfaction play in this process. By exploring this topic and focusing on the human-computer interaction, we found that color transfer interactions are driven by several intrinsic motivations and that user expectations and satisfaction ratings can be maintained via clear visualizations of the processes to be undertaken. Furthermore, we reveal the specific language that users use to communicate video recoloring when regarding user motivations, expectations, and satisfaction. This research provides important information for developers of state-of-art recoloring processes and contributes to dialogues surrounding the users of mobile multimedia technology in practice.
A Review of Platforms for the Development of Agent Systems
Venue: arXiv cs.MA 2020
Year: 2020

Agent-based computing is an active field of research with the goal of building autonomous software of hardware entities. This task is often facilitated by the use of dedicated, specialized frameworks. For almost thirty years, many such agent platforms have been developed. Meanwhile, some of them have been abandoned, others continue their development and new platforms are released. This paper presents a up-to-date review of the existing agent platforms and also a historical perspective of this domain. It aims to serve as a reference point for people interested in developing agent systems. This work details the main characteristics of the included agent platforms, together with links to specific projects where they have been used. It distinguishes between the active platforms and those no longer under development or with unclear status. It also classifies the agent platforms as general purpose ones, free or commercial, and specialized ones, which can be used for particular types of applications.
Knowledge Distillation in Deep Learning and its Applications
Venue: arXiv cs.LG 2020
Year: 2020

Deep learning based models are relatively large, and it is hard to deploy such models on resource-limited devices such as mobile phones and embedded devices. One possible solution is knowledge distillation whereby a smaller model (student model) is trained by utilizing the information from a larger model (teacher model). In this paper, we present a survey of knowledge distillation techniques applied to deep learning models. To compare the performances of different techniques, we propose a new metric called distillation metric. Distillation metric compares different knowledge distillation algorithms based on sizes and accuracy scores. Based on the survey, some interesting conclusions are drawn and presented in this paper.
Preservation of DNA Privacy During the Large Scale Detection of COVID-19
Venue: arXiv cs.CR 2020
Year: 2020

As humanity struggles to contain the global COVID-19 pandemic, privacy concerns are emerging regarding confinement, tracing and testing. The scientific debate concerning privacy of the COVID-19 tracing efforts has been intense, especially focusing on the choice between centralised and decentralised tracing apps. The privacy concerns regarding COVID-19 testing, however, have not received as much attention even though the privacy at stake is arguably even higher. COVID-19 tests require the collection of samples. Those samples possibly contain viral material but inevitably also human DNA. Patient DNA is not necessary for the test but it is technically impossible to avoid collecting it. The unlawful preservation, or misuse, of such samples at a massive scale may hence disclose patient DNA information with far-reaching privacy consequences. Inspired by the cryptographic concept of "Indistinguishability under Chosen Plaintext Attack", this paper poses the blueprint of novel types of tests allowing to detect viral presence without leaving persisting traces of the patient's DNA. Authors are listed in alphabetical order.
Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words
Venue: arXiv cs.FL 2020
Year: 2020

We give a new characterization of primitive permutation groups tied to the notion of completely reachable automata. Also, we introduce sync-maximal permutation groups tied to the state complexity of the set of synchronizing words of certain associated automata and show that they are contained between the $2$-homogeneous and the primitive groups. Lastly, we define $k$-reachable groups in analogy with synchronizing groups and motivated by our characterization of primitive permutation groups. But the results show that a $k$-reachable permutation group of degree $n$ with $6 \le k \le n - 6$ is either the alternating or the symmetric group.
Scale Equivariance Improves Siamese Tracking
Venue: arXiv cs.CV 2020
Year: 2020

Siamese trackers turn tracking into similarity estimation between a template and the candidate regions in the frame. Mathematically, one of the key ingredients of success of the similarity function is translation equivariance. Non-translation-equivariant architectures induce a positional bias during training, so the location of the target will be hard to recover from the feature space. In real life scenarios, objects undergoe various transformations other than translation, such as rotation or scaling. Unless the model has an internal mechanism to handle them, the similarity may degrade. In this paper, we focus on scaling and we aim to equip the Siamese network with additional built-in scale equivariance to capture the natural variations of the target a priori. We develop the theory for scale-equivariant Siamese trackers, and provide a simple recipe for how to make a wide range of existing trackers scale-equivariant. We present SE-SiamFC, a scale-equivariant variant of SiamFC built according to the recipe. We conduct experiments on OTB and VOT benchmarks and on the synthetically generated T-MNIST and S-MNIST datasets. We demonstrate that a built-in additional scale equivariance is useful for visual object tracking.
Local information sources received the most attention from Puerto Ricans during the aftermath of Hurricane María
Venue: arXiv cs.SI 2020
Year: 2020

In September 2017, Hurricane María made landfall across the Caribbean region as a category 4 storm. In the aftermath, many residents of Puerto Rico were without power or clean running water for nearly a year. Using both English and Spanish tweets from September 16 to October 15 2017, we investigate discussion of María both on and off the island, constructing a proxy for the temporal network of communication between victims of the hurricane and others. We use information theoretic tools to compare the lexical divergence of different subgroups within the network. Lastly, we quantify temporal changes in user prominence throughout the event. We find at the global level that Spanish tweets more often contained messages of hope and a focus on those helping. At the local level, we find that information propagating among Puerto Ricans most often originated from sources local to the island, such as journalists and politicians. Critically, content from these accounts overshadows content from celebrities, global news networks, and the like for the large majority of the time period studied. Our findings reveal insight into ways social media campaigns could be deployed to disseminate relief information during similar events in the future.
Can we Estimate Truck Accident Risk from Telemetric Data using Machine Learning?
Venue: arXiv cs.LG 2020
Year: 2020

Road accidents have a high societal cost that could be reduced through improved risk predictions using machine learning. This study investigates whether telemetric data collected on long-distance trucks can be used to predict the risk of accidents associated with a driver. We use a dataset provided by a truck transportation company containing the driving data of 1,141 drivers for 18 months. We evaluate two different machine learning approaches to perform this task. In the first approach, features are extracted from the time series data using the FRESH algorithm and then used to estimate the risk using Random Forests. In the second approach, we use a convolutional neural network to directly estimate the risk from the time-series data. We find that neither approach is able to successfully estimate the risk of accidents on this dataset, in spite of many methodological attempts. We discuss the difficulties of using telemetric data for the estimation of the risk of accidents that could explain this negative result.
AutoCount: Unsupervised Segmentation and Counting of Organs in Field Images
Venue: arXiv cs.CV 2020
Year: 2020

Counting plant organs such as heads or tassels from outdoor imagery is a popular benchmark computer vision task in plant phenotyping, which has been previously investigated in the literature using state-of-the-art supervised deep learning techniques. However, the annotation of organs in field images is time-consuming and prone to errors. In this paper, we propose a fully unsupervised technique for counting dense objects such as plant organs. We use a convolutional network-based unsupervised segmentation method followed by two post-hoc optimization steps. The proposed technique is shown to provide competitive counting performance on a range of organ counting tasks in sorghum (S. bicolor) and wheat (T. aestivum) with no dataset-dependent tuning or modifications.
The Edit Distance to $k$-Subsequence Universality
Venue: arXiv cs.DS 2020
Year: 2020

A word $u$ is a subsequence of another word $w$ if $u$ can be obtained from $w$ by deleting some of its letters. The word $w$ with alph$(w)=Σ$ is called $k$-subsequence universal if the set of subsequences of length $k$ of $w$ contains all possible words of length $k$ over $Σ$. We propose a series of efficient algorithms computing the minimal number of edit operations (insertion, deletion, substitution) one needs to apply to a given word in order to reach the set of $k$-subsequence universal words.
Multi-robot Cooperative Object Transportation using Decentralized Deep Reinforcement Learning
Venue: arXiv cs.RO 2020
Year: 2020

Object transportation could be a challenging problem for a single robot due to the oversize and/or overweight issues. A multi-robot system can take the advantage of increased driving power and more flexible configuration to solve such a problem. However, increased number of individuals also changed the dynamics of the system which makes control of a multi-robot system more complicated. Even worse, if the whole system is sitting on a centralized decision making unit, the data flow could be easily overloaded due to the upscaling of the system. In this research, we propose a decentralized control scheme on a multi-robot system with each individual equipped with a deep Q-network (DQN) controller to perform an oversized object transportation task. DQN is a deep reinforcement learning algorithm thus does not require the knowledge of system dynamics, instead, it enables the robots to learn appropriate control strategies through trial-and-error style interactions within the task environment. Since analogous controllers are distributed on the individuals, the computational bottleneck is avoided systematically. We demonstrate such a system in a scenario of carrying an oversized rod through a doorway by a two-robot team. The presented multi-robot system learns abstract features of the task and cooperative behaviors are observed. The decentralized DQN-style controller is showing strong robustness against uncertainties. In addition, We propose a universal metric to assess the cooperation quantitatively.
Hierarchical Deep Reinforcement Learning Approach for Multi-Objective Scheduling With Varying Queue Sizes
Venue: arXiv cs.LG 2020
Year: 2020

Multi-objective task scheduling (MOTS) is the task scheduling while optimizing multiple and possibly contradicting constraints. A challenging extension of this problem occurs when every individual task is a multi-objective optimization problem by itself. While deep reinforcement learning (DRL) has been successfully applied to complex sequential problems, its application to the MOTS domain has been stymied by two challenges. The first challenge is the inability of the DRL algorithm to ensure that every item is processed identically regardless of its position in the queue. The second challenge is the need to manage large queues, which results in large neural architectures and long training times. In this study we present MERLIN, a robust, modular and near-optimal DRL-based approach for multi-objective task scheduling. MERLIN applies a hierarchical approach to the MOTS problem by creating one neural network for the processing of individual tasks and another for the scheduling of the overall queue. In addition to being smaller and with shorted training times, the resulting architecture ensures that an item is processed in the same manner regardless of its position in the queue. Additionally, we present a novel approach for efficiently applying DRL-based solutions on very large queues, and demonstrate how we effectively scale MERLIN to process queue sizes that are larger by orders of magnitude than those on which it was trained. Extensive evaluation on multiple queue sizes show that MERLIN outperforms multiple well-known baselines by a large margin (>22%).
Computing Blindfolded on Data Homomorphically Encrypted under Multiple Keys: An Extended Survey
Venue: arXiv cs.CR 2020
Year: 2020

New cryptographic techniques such as homomorphic encryption (HE) allow computations to be outsourced to and evaluated blindfolded in a resourceful cloud. These computations often require private data owned by multiple participants, engaging in joint evaluation of some functions. For example, Genome-Wide Association Study (GWAS) is becoming feasible because of recent proliferation of genome sequencing technology. Due to the sensitivity of genomic data, these data should be encrypted using different keys. However, supporting computation on ciphertexts encrypted under multiple keys is a non-trivial task. In this paper, we present a comprehensive survey on different state-of-the-art cryptographic techniques and schemes that are commonly used. We review techniques and schemes including Attribute-Based Encryption (ABE), Proxy Re-Encryption (PRE), Threshold Homomorphic Encryption (ThHE), and Multi-Key Homomorphic Encryption (MKHE). We analyze them based on different system and security models, and examine their complexities. We share lessons learned and draw observations for designing better schemes with reduced overheads.
An APX for the Maximum-Profit Routing Problem with Variable Supply
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we study the Maximum-Profit Routing Problem with Variable Supply (MPRP-VS). This is a more general version of the Maximum-Profit Public Transportation Route Planning Problem, or simply Maximum-Profit Routing Problem (MPRP), introduced in \cite{Armaselu-PETRA}. In this new version, the quantity $q_i(t)$ supplied at site $i$ is linearly increasing in time $t$, as opposed to \cite{Armaselu-PETRA}, where the quantity is constant in time. Our main result is a $5.5 \log{T} (1 + ε) (1 + \frac{1}{1 + \sqrt{m}})^2$ approximation algorithm, where $T$ is the latest time window and $m$ is the number of vehicles used. In addition, we improve upon the MPRP algorithm in \cite{Armaselu-PETRA} under certain conditions.
On regularization of gradient descent, layer imbalance and flat minima
Venue: arXiv cs.LG 2020
Year: 2020

We analyze the training dynamics for deep linear networks using a new metric - layer imbalance - which defines the flatness of a solution. We demonstrate that different regularization methods, such as weight decay or noise data augmentation, behave in a similar way. Training has two distinct phases: 1) optimization and 2) regularization. First, during the optimization phase, the loss function monotonically decreases, and the trajectory goes toward a minima manifold. Then, during the regularization phase, the layer imbalance decreases, and the trajectory goes along the minima manifold toward a flat area. Finally, we extend the analysis for stochastic gradient descent and show that SGD works similarly to noise regularization.