OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Generation of Parallel Spin-images Using Dynamic Loop Scheduling
Venue: arXiv cs.DC 2018
Year: 2018

High performance computing (HPC) systems underwent a significant increase in their processing capabilities. Modern HPC systems combine large numbers of homogeneous and heterogeneous computing resources. Scalability is, therefore, an essential aspect of scientific applications to efficiently exploit the massive parallelism of modern HPC systems. This work introduces an efficient version of the parallel spin-image algorithm (PSIA), called EPSIA. The PSIA is a parallel version of the spin-image algorithm (SIA). The (P)SIA is used in various domains, such as 3D object recognition, categorization, and 3D face recognition. EPSIA refers to the extended version of the PSIA that integrates various well-known dynamic loop scheduling (DLS) techniques. The present work: (1) Proposes EPSIA, a novel flexible version of PSIA; (2) Showcases the benefits of applying DLS techniques for optimizing the performance of the PSIA; (3) Assesses the performance of the proposed EPSIA by conducting several scalability experiments. The performance results are promising and show that using well-known DLS techniques, the performance of the EPSIA outperforms the performance of the PSIA by a factor of 1.2 and 2 for homogeneous and heterogeneous computing resources, respectively.
Online Diverse Learning to Rank from Partial-Click Feedback
Venue: arXiv cs.IR 2018
Year: 2018

Learning to rank is an important problem in machine learning and recommender systems. In a recommender system, a user is typically recommended a list of items. Since the user is unlikely to examine the entire recommended list, partial feedback arises naturally. At the same time, diverse recommendations are important because it is challenging to model all tastes of the user in practice. In this paper, we propose the first algorithm for online learning to rank diverse items from partial-click feedback. We assume that the user examines the list of recommended items until the user is attracted by an item, which is clicked, and does not examine the rest of the items. This model of user behavior is known as the cascade model. We propose an online learning algorithm, cascadelsb, for solving our problem. The algorithm actively explores the tastes of the user with the objective of learning to recommend the optimal diverse list. We analyze the algorithm and prove a gap-free upper bound on its n-step regret. We evaluate cascadelsb on both synthetic and real-world datasets, compare it to various baselines, and show that it learns even when our modeling assumptions do not hold exactly.
CMI: An Online Multi-objective Genetic Autoscaler for Scientific and Engineering Workflows in Cloud Infrastructures with Unreliable Virtual Machines
Venue: arXiv cs.NE 2018
Year: 2018

Cloud Computing is becoming the leading paradigm for executing scientific and engineering workflows. The large-scale nature of the experiments they model and their variable workloads make clouds the ideal execution environment due to prompt and elastic access to huge amounts of computing resources. Autoscalers are middleware-level software components that allow scaling up and down the computing platform by acquiring or terminating virtual machines (VM) at the time that workflow's tasks are being scheduled. In this work we propose a novel online multi-objective autoscaler for workflows denominated Cloud Multi-objective Intelligence (CMI), that aims at the minimization of makespan, monetary cost and the potential impact of errors derived from unreliable VMs. In addition, this problem is subject to monetary budget constraints. CMI is responsible for periodically solving the autoscaling problems encountered along the execution of a workflow. Simulation experiments on four well-known workflows exhibit that CMI significantly outperforms a state-of-the-art autoscaler of similar characteristics called Spot Instances Aware Autoscaling (SIAA). These results convey a solid base for deepening in the study of other meta-heuristic methods for autoscaling workflow applications using cheap but unreliable infrastructures.
Building an Argument for the Use of Science Fiction in HCI Education
Venue: arXiv cs.HC 2018
Year: 2018

Science fiction literature, comics, cartoons and, in particular, audio-visual materials, such as science fiction movies and shows, can be a valuable addition in Human-computer interaction (HCI) Education. In this paper, we present an overview of research relative to future directions in HCI Education, distinct crossings of science fiction in HCI and Computer Science teaching and the Framework for 21st Century Learning. Next, we provide examples where science fiction can add to the future of HCI Education. In particular, we argue herein first that science fiction, as tangible and intangible cultural artifact, can serve as a trigger for creativity and innovation and thus, support us in exploring the design space. Second, science fiction, as a means to analyze yet-to-come HCI technologies, can assist us in developing an open-minded and reflective dialogue about technological futures, thus creating a singular base for critical thinking and problem solving. Provided that one is cognizant of its potential and limitations, we reason that science fiction can be a meaningful extension of selected aspects of HCI curricula and research.
Neural Machine Translation into Language Varieties
Venue: arXiv cs.CL 2018
Year: 2018

Both research and commercial machine translation have so far neglected the importance of properly handling the spelling, lexical and grammar divergences occurring among language varieties. Notable cases are standard national varieties such as Brazilian and European Portuguese, and Canadian and European French, which popular online machine translation services are not keeping distinct. We show that an evident side effect of modeling such varieties as unique classes is the generation of inconsistent translations. In this work, we investigate the problem of training neural machine translation from English to specific pairs of language varieties, assuming both labeled and unlabeled parallel texts, and low-resource conditions. We report experiments from English to two pairs of dialects, EuropeanBrazilian Portuguese and European-Canadian French, and two pairs of standardized varieties, Croatian-Serbian and Indonesian-Malay. We show significant BLEU score improvements over baseline systems when translation into similar languages is learned as a multilingual task with shared representations.
Transfer Learning in Multilingual Neural Machine Translation with Dynamic Vocabulary
Venue: arXiv cs.CL 2018
Year: 2018

We propose a method to transfer knowledge across neural machine translation (NMT) models by means of a shared dynamic vocabulary. Our approach allows to extend an initial model for a given language pair to cover new languages by adapting its vocabulary as long as new data become available (i.e., introducing new vocabulary items if they are not included in the initial model). The parameter transfer mechanism is evaluated in two scenarios: i) to adapt a trained single language NMT system to work with a new language pair and ii) to continuously add new language pairs to grow to a multilingual NMT system. In both the scenarios our goal is to improve the translation performance, while minimizing the training convergence time. Preliminary experiments spanning five languages with different training data sizes (i.e., 5k and 50k parallel sentences) show a significant performance gain ranging from +3.85 up to +13.63 BLEU in different language directions. Moreover, when compared with training an NMT model from scratch, our transfer-learning approach allows us to reach higher performance after training up to 4% of the total training steps.
Improved approximation algorithms for path vertex covers in regular graphs
Venue: arXiv cs.DS 2018
Year: 2018

Given a simple graph $G = (V, E)$ and a constant integer $k \ge 2$, the $k$-path vertex cover problem ({\sc P$k$VC}) asks for a minimum subset $F \subseteq V$ of vertices such that the induced subgraph $G[V - F]$ does not contain any path of order $k$. When $k = 2$, this turns out to be the classic vertex cover ({\sc VC}) problem, which admits a $\left(2 - {\rm Θ}\left(\frac 1{\log|V|}\right)\right)$-approximation. The general {\sc P$k$VC} admits a trivial $k$-approximation; when $k = 3$ and $k = 4$, the best known approximation results for {\sc P$3$VC} and {\sc P$4$VC} are a $2$-approximation and a $3$-approximation, respectively. On $d$-regular graphs, the approximation ratios can be reduced to $\min\left\{2 - \frac 5{d+3} + ε, 2 - \frac {(2 - o(1))\log\log d}{\log d}\right\}$ for {\sc VC} ({\it i.e.}, {\sc P$2$VC}), $2 - \frac 1d + \frac {4d - 2}{3d |V|}$ for {\sc P$3$VC}, $\frac {\lfloor d/2\rfloor (2d - 2)}{(\lfloor d/2\rfloor + 1) (d - 2)}$ for {\sc P$4$VC}, and $\frac {2d - k + 2}{d - k + 2}$ for {\sc P$k$VC} when $1 \le k-2 < d \le 2(k-2)$. By utilizing an existing algorithm for graph defective coloring, we first present a $\frac {\lfloor d/2\rfloor (2d - k + 2)}{(\lfloor d/2\rfloor + 1) (d - k + 2)}$-approximation for {\sc P$k$VC} on $d$-regular graphs when $1 \le k - 2 < d$. This beats all the best known approximation results for {\sc P$k$VC} on $d$-regular graphs for $k \ge 3$, except for {\sc P$4$VC} it ties with the best prior work and in particular they tie at $2$ on cubic graphs and $4$-regular graphs. We then propose a $1.875$-approximation and a $1.852$-approximation for {\sc P$4$VC} on cubic graphs and $4$-regular graphs, respectively. We also present a better approximation algorithm for {\sc P$4$VC} on $d$-regular bipartite graphs.
Unsupervised Identification of Study Descriptors in Toxicology Research: An Experimental Study
Venue: arXiv cs.CL 2018
Year: 2018

Identifying and extracting data elements such as study descriptors in publication full texts is a critical yet manual and labor-intensive step required in a number of tasks. In this paper we address the question of identifying data elements in an unsupervised manner. Specifically, provided a set of criteria describing specific study parameters, such as species, route of administration, and dosing regimen, we develop an unsupervised approach to identify text segments (sentences) relevant to the criteria. A binary classifier trained to identify publications that met the criteria performs better when trained on the candidate sentences than when trained on sentences randomly picked from the text, supporting the intuition that our method is able to accurately identify study descriptors.
Stability Analysis for Switched Systems with Sequence-based Average Dwell Time
Venue: arXiv cs.SY 2018
Year: 2018

This note investigates the stability of both linear and nonlinear switched systems with average dwell time. Two new analysis methods are proposed. Different from existing approaches, the proposed methods take into account the sequence in which the subsystems are switched. Depending on the predecessor or successor subsystems to be considered, sequence-based average preceding dwell time (SBAPDT) and sequence-based average subsequence dwell time (SBASDT) approaches are proposed and discussed for both continuous and discrete time systems. These proposed methods, when considering the switch sequence, have the potential to further reduce the conservativeness of the existing approaches. A comparative numerical example is also given to demonstrate the advantages of the proposed approaches.
Hardness of computing and approximating predicates and functions with leaderless population protocols
Venue: arXiv cs.DC 2018
Year: 2018

Population protocols are a distributed computing model appropriate for describing massive numbers of agents with limited computational power. A population protocol "has an initial leader" if every valid initial configuration contains a single agent in a special "leader" state that helps to coordinate the computation. Although the class of predicates and functions computable with probability 1 is the same whether or not there is an initial leader (semilinear functions and predicates), it is not known whether a leader is necessary for fast computation. Efficient population protocols are generally defined as those computing in polylogarithmic in $n$ (parallel) time. We consider leaderless population protocols, regarding the computation finished when a configuration is reached from which a different output is no longer reachable. In this setting we show that a wide class of functions and predicates computable by population protocols are not efficiently computable (they require at least linear time to stabilize on a correct answer), nor are some linear functions even efficiently approximable. For example, the widely studied parity, majority, and equality predicates cannot be computed in sublinear time. Moreover, it requires at least linear time for a population protocol even to approximate any linear function with a coefficient outside of $\mathbb{N}$: for sufficiently small $γ> 0$, the output of a sublinear time protocol can stabilize outside the interval $f(m) (1 \pm γ)$ on infinitely many inputs $m$. We also show that it requires linear time to exactly compute a wide range of semilinear functions (e.g., $f(m)=m$ if $m$ is even and $2m$ if $m$ is odd). Finally, we show that with a sufficiently large value of $γ$, a population protocol can approximate any linear $f$ with nonnegative rational coefficients, within approximation factor $γ$, in $O(\log n)$ time.
QuickXsort - A Fast Sorting Scheme in Theory and Practice
Venue: arXiv cs.DS 2018
Year: 2018

QuickXsort is a highly efficient in-place sequential sorting scheme that mixes Hoare's Quicksort algorithm with X, where X can be chosen from a wider range of other known sorting algorithms, like Heapsort, Insertionsort and Mergesort. Its major advantage is that QuickXsort can be in-place even if X is not. In this work we provide general transfer theorems expressing the number of comparisons of QuickXsort in terms of the number of comparisons of X. More specifically, if pivots are chosen as medians of (not too fast) growing size samples, the average number of comparisons of QuickXsort and X differ only by $o(n)$-terms. For median-of-$k$ pivot selection for some constant $k$, the difference is a linear term whose coefficient we compute precisely. For instance, median-of-three QuickMergesort uses at most $n \lg n - 0.8358n + O(\log n)$ comparisons. Furthermore, we examine the possibility of sorting base cases with some other algorithm using even less comparisons. By doing so the average-case number of comparisons can be reduced down to $n \lg n- 1.4106n + o(n)$ for a remaining gap of only $0.0321n$ comparisons to the known lower bound (while using only $O(\log n)$ additional space and $O(n \log n)$ time overall). Implementations of these sorting strategies show that the algorithms challenge well-established library implementations like Musser's Introsort.
Building a Winning Self-Driving Car in Six Months
Venue: arXiv cs.RO 2018
Year: 2018

The SAE AutoDrive Challenge is a three-year competition to develop a Level 4 autonomous vehicle by 2020. The first set of challenges were held in April of 2018 in Yuma, Arizona. Our team (aUToronto/Zeus) placed first. In this paper, we describe our complete system architecture and specialized algorithms that enabled us to win. We show that it is possible to develop a vehicle with basic autonomy features in just six months relying on simple, robust algorithms. We do not make use of a prior map. Instead, we have developed a multi-sensor visual localization solution. All of our algorithms run in real-time using CPUs only. We also highlight the closed-loop performance of our system in detail in several experiments.
Modeling Traffic Networks Using Integrated Route and Link Data
Venue: arXiv cs.SY 2018
Year: 2018

Real-time navigation services, such as Google Maps and Waze, are widely used in daily life. These services provide rich data resources in real-time traffic conditions and travel time predictions; however, they have not been fully applied in transportation modeling. This paper aims to use traffic data from Google Maps and applying cutting-edge technologies in maximum likelihood estimation to model traffic networks and travel time reliability. This paper integrates Google Maps travel time data for routes and traffic condition data for links to model the complexities of traffic networks. We then formulate the Fisher information matrix and apply the asymptotic normality to obtain the probability distribution of the travel time estimates for a random route within the network of interest. We also derive the travel time reliability by considering two levels of uncertainties, i.e., the uncertainty of the route's travel time and the uncertainty of its travel time estimates. The proposed method could provide a more realistic and precise travel time reliability estimate. The methodology is applied to a small network in the downtown Baltimore area, where we propose a link data collection strategy and provide empirical evidence to show data independence by following this strategy. We also show results for maximum likelihood estimates and travel time reliability measures for different routes within the network. Furthermore, we use the historical data from a different network to validate this approach, showing our method provides a more accurate and precise estimate compared to the sample mean of the empirical data.
An Analysis of Centrality Measures for Complex and Social Networks
Venue: arXiv cs.SI 2018
Year: 2018

Measures of complex network analysis, such as vertex centrality, have the potential to unveil existing network patterns and behaviors. They contribute to the understanding of networks and their components by analyzing their structural properties, which makes them useful in several computer science domains and applications. Unfortunately, there is a large number of distinct centrality measures and little is known about their common characteristics in practice. By means of an empirical analysis, we aim at a clear understanding of the main centrality measures available, unveiling their similarities and differences in a large number of distinct social networks. Our experiments show that the vertex centrality measures known as information, eigenvector, subgraph, walk betweenness and betweenness can distinguish vertices in all kinds of networks with a granularity performance at 95%, while other metrics achieved a considerably lower result. In addition, we demonstrate that several pairs of metrics evaluate the vertices in a very similar way, i.e. their correlation coefficient values are above 0.7. This was unexpected, considering that each metric presents a quite distinct theoretical and algorithmic foundation. Our work thus contributes towards the development of a methodology for principled network analysis and evaluation.
Exploring the Relation Between Two Levels of Scheduling Using a Novel Simulation Approach
Venue: arXiv cs.DC 2018
Year: 2018

Modern high performance computing (HPC) systems exhibit a rapid growth in size, both "horizontally" in the number of nodes, as well as "vertically" in the number of cores per node. As such, they offer additional levels of hardware parallelism. Each such level requires and employs algorithms for appropriately scheduling the computational work at the respective level. The present work explores the relation between two scheduling levels: batch and application. Understanding this relation is important for improving the performance of scientific applications, that are scheduled and executed in batches on HPC systems. The relation between batch and application level scheduling is understudied in the literature. Understanding the relation and interaction between these two scheduling levels requires their simultaneous analysis during operation. In this work, such an analysis is performed via simultaneous simulation of batch and application level scheduling for a number of scenarios. A generic simulation approach is presented that bridges two existing simulators from the two scheduling levels. A novel two-level simulator that implements the proposed approach is introduced. The two-level simulator is used to simulate all combinations of three batch scheduling and four application scheduling algorithms from the literature. These combinations are considered for allocating resources and executing the parallel jobs of two batches from two production HPC systems. The results of the scheduling experiments reveal the strong relation between the two scheduling levels and their mutual influence. Complementing the simulations, the two-level simulator produces standard parallel execution traces, which can visually be examined and which illustrate the execution of different jobs and, for each job, the execution of its tasks at node and core levels, respectively.
Semi-Supervised Confidence Network aided Gated Attention based Recurrent Neural Network for Clickbait Detection
Venue: arXiv cs.CL 2018
Year: 2018

Clickbaits are catchy headlines that are frequently used by social media outlets in order to allure its viewers into clicking them and thus leading them to dubious content. Such venal schemes thrive on exploiting the curiosity of naive social media users, directing traffic to web pages that won't be visited otherwise. In this paper, we propose a novel, semi-supervised classification based approach, that employs attentions sampled from a Gumbel-Softmax distribution to distill contexts that are fairly important in clickbait detection. An additional loss over the attention weights is used to encode prior knowledge. Furthermore, we propose a confidence network that enables learning over weak labels and improves robustness to noisy labels. We show that with merely 30% of strongly labeled samples we can achieve over 97% of the accuracy, of current state of the art methods in clickbait detection.
Measuring Software Performance on Linux
Venue: arXiv cs.PF 2018
Year: 2018

Measuring and analyzing the performance of software has reached a high complexity, caused by more advanced processor designs and the intricate interaction between user programs, the operating system, and the processor's microarchitecture. In this report, we summarize our experience about how performance characteristics of software should be measured when running on a Linux operating system and a modern processor. In particular, (1) We provide a general overview about hardware and operating system features that may have a significant impact on timing and how they interact, (2) we identify sources of errors that need to be controlled in order to obtain unbiased measurement results, and (3) we propose a measurement setup for Linux to minimize errors. Although not the focus of this report, we describe the measurement process using hardware performance counters, which can faithfully reflect the real bottlenecks on a given processor. Our experiments confirm that our measurement setup has a large impact on the results. More surprisingly, however, they also suggest that the setup can be negligible for certain analysis methods. Furthermore, we found that our setup maintains significantly better performance under background load conditions, which means it can be used to improve software in high-performance applications.