OpenRaiser/Intern-Atlas huggingface dataset:
Extraction and Analysis of Dynamic Conversational Networks from TV Series
Venue: arXiv cs.MM 2018
Year: 2018

Identifying and characterizing the dynamics of modern tv series subplots is an open problem. One way is to study the underlying social network of interactions between the characters. Standard dynamic network extraction methods rely on temporal integration, either over the whole considered period, or as a sequence of several time-slices. However, they turn out to be inappropriate in the case of tv series, because the scenes shown onscreen alternatively focus on parallel storylines, and do not necessarily respect a traditional chronology. In this article, we introduce Narrative Smoothing, a novel network extraction method taking advantage of the plot properties to solve some of their limitations. We apply our method to a corpus of 3 popular series, and compare it to both standard approaches. Narrative smoothing leads to more relevant observations when it comes to the characterization of the protagonists and their relationships, confirming its appropriateness to model the intertwined storylines constituting the plots.
Dependability in a Multi-tenant Multi-framework Deep Learning as-a-Service Platform
Venue: arXiv cs.DC 2018
Year: 2018

Deep learning (DL), a form of machine learning, is becoming increasingly popular in several application domains. As a result, cloud-based Deep Learning as a Service (DLaaS) platforms have become an essential infrastructure in many organizations. These systems accept, schedule, manage and execute DL training jobs at scale. This paper explores dependability in the context of a DLaaS platform used in IBM. We begin by explaining how DL training workloads are different, and what features ensure dependability in this context. We then describe the architecture, design and implementation of a cloud-based orchestration system for DL training. We show how this system has been architected with dependability in mind while also being horizontally scalable, elastic, flexible and efficient. We also present an initial empirical evaluation of the overheads introduced by our platform, and discuss tradeoffs between efficiency and dependability.
Cellular Network Multi-Access Measurements on the Roads of Värmland, Sweden
Venue: arXiv cs.NI 2018
Year: 2018

Cooperative Intelligent Transport Systems (C-ITS) make road traffic safer and more efficient, but require the mobile networks to handle time-critical applications. While some applications may need new dedicated communications technologies such as IEEE 802.11p or 5G, other applications can use current cellular networks. This study evaluates the performance that connected vehicles can expect from existing networks, and estimates the potential gain of multi-access by simultaneously transmitting over several operators. We upload time-critical warning messages from buses in Sweden, and characterise transaction times and network availability. We conduct the experiments with different protocols: UDP, TCP, and HTTPS. Our results show that when using UDP, the median transaction time for sending a typical warning message is 135 ms. We also show that multi-access can bring this value down to 73 ms. For time-critical applications requiring transaction times under 200 ms, multi-access can increase availability of the network from to 57.4% to 92.0%.
External memory BWT and LCP computation for sequence collections with applications
Venue: arXiv cs.DS 2018
Year: 2018

We propose an external memory algorithm for the computation of the BWT and LCP array for a collection of sequences. Our algorithm takes the amount of available memory as an input parameter, and tries to make the best use of it by splitting the input collection into subcollections sufficiently small that it can compute their BWT in RAM using an optimal linear time algorithm. Next, it merges the partial BWTs in external memory and in the process it also computes the LCP values. We prove that our algorithm performs O(n AveLcp) sequential I/Os, where n is the total length of the collection, and AveLcp is the average Longest Common Prefix of the collection. This bound is an improvement over the known algorithms for the same task. The experimental results show that our algorithm outperforms the current best algorithm for collections of sequences with different lengths and for collections with relatively small average Longest Common Prefix. In the second part of the paper, we show that our algorithm can be modified to output two additional arrays that, used with the BWT and LCP arrays, provide simple, scan based, external memory algorithms for three well known problems in bioinformatics: the computation of maximal repeats, the all pairs suffix-prefix overlaps, and the construction of succinct de Bruijn graphs. To our knowledge, there are no other known external memory algorithms for these problems.
Design Identification of Curve Patterns on Cultural Heritage Objects: Combining Template Matching and CNN-based Re-Ranking
Venue: arXiv cs.LG 2018
Year: 2018

The surfaces of many cultural heritage objects were embellished with various patterns, especially curve patterns. In practice, most of the unearthed cultural heritage objects are highly fragmented, e.g., sherds of potteries or vessels, and each of them only shows a very small portion of the underlying full design, with noise and deformations. The goal of this paper is to address the challenging problem of automatically identifying the underlying full design of curve patterns from such a sherd. Specifically, we formulate this problem as template matching: curve structure segmented from the sherd is matched to each location with each possible orientation of each known full design. In this paper, we propose a new two-stage matching algorithm, with a different matching cost in each stage. In Stage 1, we use a traditional template matching, which is highly computationally efficient, over the whole search space and identify a small set of candidate matchings. In Stage 2, we derive a new matching cost by training a dual-source Convolutional Neural Network (CNN) and apply it to re-rank the candidate matchings identified in Stage 1. We collect 600 pottery sherds with 98 full designs from the Woodland Period in Southeastern North America for experiments and the performance of the proposed algorithm is very competitive.
Resource allocation under uncertainty: an algebraic and qualitative treatment
Venue: arXiv cs.AI 2018
Year: 2018

We use an algebraic viewpoint, namely a matrix framework to deal with the problem of resource allocation under uncertainty in the context of a qualitative approach. Our basic qualitative data are a plausibility relation over the resources, a hierarchical relation over the agents and of course the preference that the agents have over the resources. With this data we propose a qualitative binary relation $\unrhd$ between allocations such that $\mathcal{F}\unrhd \mathcal{G}$ has the following intended meaning: the allocation $\mathcal{F}$ produces more or equal social welfare than the allocation $\mathcal{G}$. We prove that there is a family of allocations which are maximal with respect to $\unrhd$. We prove also that there is a notion of simple deal such that optimal allocations can be reached by sequences of simple deals. Finally, we introduce some mechanism for discriminating {optimal} allocations.
A Forest Mixture Bound for Block-Free Parallel Inference
Venue: arXiv cs.LG 2018
Year: 2018

Coordinate ascent variational inference is an important algorithm for inference in probabilistic models, but it is slow because it updates only a single variable at a time. Block coordinate methods perform inference faster by updating blocks of variables in parallel. However, the speed and stability of these algorithms depends on how the variables are partitioned into blocks. In this paper, we give a stable parallel algorithm for inference in deep exponential families that doesn't require the variables to be partitioned into blocks. We achieve this by lower bounding the ELBO by a new objective we call the forest mixture bound (FM bound) that separates the inference problem for variables within a hidden layer. We apply this to the simple case when all random variables are Gaussian and show empirically that the algorithm converges faster for models that are inherently more forest-like.
Practical Algorithms for STV and Ranked Pairs with Parallel Universes Tiebreaking
Venue: arXiv cs.AI 2018
Year: 2018

STV and ranked pairs (RP) are two well-studied voting rules for group decision-making. They proceed in multiple rounds, and are affected by how ties are broken in each round. However, the literature is surprisingly vague about how ties should be broken. We propose the first algorithms for computing the set of alternatives that are winners under some tiebreaking mechanism under STV and RP, which is also known as parallel-universes tiebreaking (PUT). Unfortunately, PUT-winners are NP-complete to compute under STV and RP, and standard search algorithms from AI do not apply. We propose multiple DFS-based algorithms along with pruning strategies and heuristics to prioritize search direction to significantly improve the performance using machine learning. We also propose novel ILP formulations for PUT-winners under STV and RP, respectively. Experiments on synthetic and real-world data show that our algorithms are overall significantly faster than ILP, while there are a few cases where ILP is significantly faster for RP.
Short Combinatorial Proof that the DFJ Polytope is contained in the MTZ Polytope for the Asymmetric Traveling Salesman Problem
Venue: arXiv cs.DM 2018
Year: 2018

For the Asymmetric Traveling Salesman Problem (ATSP), it is known that the Dantzig-Fulkerson-Johnson (DFJ) polytope is contained in the Miller-Tucker-Zemlin (MTZ) polytope. The analytic proofs of this fact are quite long. Here, we present a proof which is combinatorial and significantly shorter by relating the formulation to distances in a modified graph.
Multifunction Cognitive Radar Task Scheduling Using Monte Carlo Tree Search and Policy Networks
Venue: arXiv cs.AI 2018
Year: 2018

A modern radar may be designed to perform multiple functions, such as surveillance, tracking, and fire control. Each function requires the radar to execute a number of transmit-receive tasks. A radar resource management (RRM) module makes decisions on parameter selection, prioritization, and scheduling of such tasks. RRM becomes especially challenging in overload situations, where some tasks may need to be delayed or even dropped. In general, task scheduling is an NP-hard problem. In this work, we develop the branch-and-bound (B&B) method which obtains the optimal solution but at exponential computational complexity. On the other hand, heuristic methods have low complexity but provide relatively poor performance. We resort to machine learning-based techniques to address this issue; specifically we propose an approximate algorithm based on the Monte Carlo tree search method. Along with using bound and dominance rules to eliminate nodes from the search tree, we use a policy network to help to reduce the width of the search. Such a network can be trained using solutions obtained by running the B&B method offline on problems with feasible complexity. We show that the proposed method provides near-optimal performance, but with computational complexity orders of magnitude smaller than the B&B algorithm.
Security Vulnerabilities Against Fingerprint Biometric System
Venue: arXiv cs.CR 2018
Year: 2018

The biometric system is an automatic identification and authentication system that uses unique biological traits, such as fingerprint, face, iris, voice, retina, etc. of an individual. Of all these systems, fingerprint biometric system is the most widely used because of its low cost, high matching speed, and relatively high matching accuracy. Due to the high efficiency of fingerprint biometric system in verifying a legitimate user, numerous government and private organizations are using this system for security purpose. This paper provides an overview of the fingerprint biometric system and gives details about various current security aspects related to the system. The security concerns that we address include multiple attacks on the system, associated threat models, biometric cryptosystems, current issues, challenges, opportunities, and open problems that exist in present day fingerprint biometric systems
Combining Advanced Methods in Japanese-Vietnamese Neural Machine Translation
Venue: arXiv cs.CL 2018
Year: 2018

Neural machine translation (NMT) systems have recently obtained state-of-the art in many machine translation systems between popular language pairs because of the availability of data. For low-resourced language pairs, there are few researches in this field due to the lack of bilingual data. In this paper, we attempt to build the first NMT systems for a low-resourced language pairs:Japanese-Vietnamese. We have also shown significant improvements when combining advanced methods to reduce the adverse impacts of data sparsity and improve the quality of NMT systems. In addition, we proposed a variant of Byte-Pair Encoding algorithm to perform effective word segmentation for Vietnamese texts and alleviate the rare-word problem that persists in NMT systems.
Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth
Venue: arXiv cs.DS 2018
Year: 2018

We show that the eccentricities, diameter, radius, and Wiener index of an undirected $n$-vertex graph with nonnegative edge lengths can be computed in time $O(n\cdot \binom{k+\lceil\log n\rceil}{k} \cdot 2^k k^2 \log n)$, where $k$ is the treewidth of the graph. For every $ε>0$, this bound is $n^{1+ε}\exp O(k)$, which matches a hardness result of Abboud, Vassilevska Williams, and Wang (SODA 2015) and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of Cabello and Knauer (Comp. Geom., 2009) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form $\log^d n$ to $\binom{d+\lceil\log n\rceil}{d}$, as originally observed by Monier (J. Alg. 1980). We also investigate the parameterization by vertex cover number.
Partial Cartesian Graph Product
Venue: arXiv cs.PL 2018
Year: 2018

In this paper we define a new product-like binary operation on directed graphs, and we discuss some of its properties. We also briefly discuss its application in constructing the subtyping relation in generic nominally-typed object-oriented programming languages.
Deep Reinforcement Learning based Resource Allocation for V2V Communications
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we develop a decentralized resource allocation mechanism for vehicle-to-vehicle (V2V) communications based on deep reinforcement learning, which can be applied to both unicast and broadcast scenarios. According to the decentralized resource allocation mechanism, an autonomous agent', a V2V link or a vehicle, makes its decisions to find the optimal sub-band and power level for transmission without requiring or having to wait for global information. Since the proposed method is decentralized, it incurs only limited transmission overhead. From the simulation results, each agent can effectively learn to satisfy the stringent latency constraints on V2V links while minimizing the interference to vehicle-to-infrastructure (V2I) communications.
Fast approximation of centrality and distances in hyperbolic graphs
Venue: arXiv cs.DS 2018
Year: 2018

We show that the eccentricities (and thus the centrality indices) of all vertices of a $δ$-hyperbolic graph $G=(V,E)$ can be computed in linear time with an additive one-sided error of at most $cδ$, i.e., after a linear time preprocessing, for every vertex $v$ of $G$ one can compute in $O(1)$ time an estimate $\hat{e}(v)$ of its eccentricity $ecc_G(v)$ such that $ecc_G(v)\leq \hat{e}(v)\leq ecc_G(v)+ cδ$ for a small constant $c$. We prove that every $δ$-hyperbolic graph $G$ has a shortest path tree, constructible in linear time, such that for every vertex $v$ of $G$, $ecc_G(v)\leq ecc_T(v)\leq ecc_G(v)+ cδ$. These results are based on an interesting monotonicity property of the eccentricity function of hyperbolic graphs: the closer a vertex is to the center of $G$, the smaller its eccentricity is. We also show that the distance matrix of $G$ with an additive one-sided error of at most $c'δ$ can be computed in $O(|V|^2\log^2|V|)$ time, where $c'< c$ is a small constant. Recent empirical studies show that many real-world graphs (including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others) have small hyperbolicity. So, we analyze the performance of our algorithms for approximating centrality and distance matrix on a number of real-world networks. Our experimental results show that the obtained estimates are even better than the theoretical bounds.
Safety of human-robot interaction through tactile sensors and peripersonal space representations
Venue: arXiv cs.RO 2018
Year: 2018

Human-robot collaboration including close physical human-robot interaction (pHRI) is a current trend in industry and also science. The safety guidelines prescribe two modes of safety: (i) power and force limitation and (ii) speed and separation monitoring. We examine the potential of robots equipped with artificial sensitive skin and a protective safety zone around it (peripersonal space) to safe pHRI.
Parallelizing Bisection Root-Finding: A Case for Accelerating Serial Algorithms in Multicore Substrates
Venue: arXiv cs.DC 2018
Year: 2018

Multicore architectures dominate today's processor market. Even though the number of cores and threads are pretty high and continues to grow, inherently serial algorithms do not benefit from the abundance of cores and threads. In this paper, we propose Runahead Computing, a technique which uses idle threads in a multi-threaded architecture for accelerating the execution time of serial algorithms. Through detailed evaluations targeting both CPU and GPU platforms and a specific serial algorithm, our approach reduces the execution latency up to 9x in our experiments.
Learning 3D Shape Completion under Weak Supervision
Venue: arXiv cs.CV 2018
Year: 2018

We address the problem of 3D shape completion from sparse and noisy point clouds, a fundamental problem in computer vision and robotics. Recent approaches are either data-driven or learning-based: Data-driven approaches rely on a shape model whose parameters are optimized to fit the observations; Learning-based approaches, in contrast, avoid the expensive optimization step by learning to directly predict complete shapes from incomplete observations in a fully-supervised setting. However, full supervision is often not available in practice. In this work, we propose a weakly-supervised learning-based approach to 3D shape completion which neither requires slow optimization nor direct supervision. While we also learn a shape prior on synthetic data, we amortize, i.e., learn, maximum likelihood fitting using deep neural networks resulting in efficient shape completion without sacrificing accuracy. On synthetic benchmarks based on ShapeNet and ModelNet as well as on real robotics data from KITTI and Kinect, we demonstrate that the proposed amortized maximum likelihood approach is able to compete with recent fully supervised baselines and outperforms data-driven approaches, while requiring less supervision and being significantly faster.
Stop memorizing: A data-dependent regularization framework for intrinsic pattern learning
Venue: arXiv cs.CV 2018
Year: 2018

Deep neural networks (DNNs) typically have enough capacity to fit random data by brute force even when conventional data-dependent regularizations focusing on the geometry of the features are imposed. We find out that the reason for this is the inconsistency between the enforced geometry and the standard softmax cross entropy loss. To resolve this, we propose a new framework for data-dependent DNN regularization, the Geometrically-Regularized-Self-Validating neural Networks (GRSVNet). During training, the geometry enforced on one batch of features is simultaneously validated on a separate batch using a validation loss consistent with the geometry. We study a particular case of GRSVNet, the Orthogonal-Low-rank Embedding (OLE)-GRSVNet, which is capable of producing highly discriminative features residing in orthogonal low-rank subspaces. Numerical experiments show that OLE-GRSVNet outperforms DNNs with conventional regularization when trained on real data. More importantly, unlike conventional DNNs, OLE-GRSVNet refuses to memorize random data or random labels, suggesting it only learns intrinsic patterns by reducing the memorizing capacity of the baseline DNN.
ALVEC: Auto-scaling by Lotka Volterra Elastic Cloud: A QoS aware Non Linear Dynamical Allocation Model
Venue: arXiv cs.NI 2018
Year: 2018

Elasticity in resource allocation is still a relevant problem in cloud computing. There are many academic and white papers which have investigated the problem and offered solutions.\textbf{Unfortunately, there are scant evidence of determining scaling number dynamically.} Elasticity is defined as the ability to adapt with the changing workloads by provisioning and de-provisioning Cloud resources. We propose ALVEC, a novel model of resource allocation in Cloud data centers, inspired by population dynamics and Mathematical Biology, which addresses dynamic allocation by auto-tuning model parameters. The proposed model, governed by a coupled differential equation known as Lotka Volterra (LV), fares better in Service level agreement (SLA) management and Quality of Services (QoS). We show evidence of true elasticity, in theory and empirical comparisons. Additionally, ALVEC is able to predict the future load and allocate VM's accordingly. The proposed model, ALVEC is the first example of unsupervised resource allocation scheme.
Review of Cyber-Physical Attacks and Counter Defense Mechanisms for Advanced Metering Infrastructure in Smart Grid
Venue: arXiv cs.CR 2018
Year: 2018

The Advanced Metering Infrastructure (AMI) is a vital element in the current development of the smart grid. AMI technologies provide electric utilities with an effective way of continuous monitoring and remote control of smart grid components. However, owing to its increasing scale and cyber-physical nature, the AMI has been faced with security threats in both cyber and physical domains. This paper provides a comprehensive review of the crucial cyber-physical attacks and counter defense mechanisms in the AMI. First, two attack surfaces are surveyed in the AMI including the communication network and smart meters. The potential cyber-physical attacks are then reviewed for each attack surface. Next, the attack models and their cyber and physical impacts on the smart grid are studied for comparison. Counter defense mechanisms that help mitigate these security threats are discussed. Finally, several mathematical tools which may help in analysis and implementation of security solutions are summarized.