OpenRaiser/Intern-Atlas huggingface dataset:
Exact isoholonomic motion of the planar Purcell's swimmer
Venue: arXiv cs.SY 2019
Year: 2019

In this article we present the discrete-time isoholonomic problem of the planar Purcell's swimmer and solve it using the Discrete-time Pontryagin maximum principle. The 3-link Purcell's swimmer is a locomotion system moving in a low Reynolds number environment. The kinematics of the system evolves on a principal fiber bundle. A structure preserving discrete-time kinematic model of the system is obtained in terms of the local form of a discrete connection. An adapted version of the Discrete Maximum Principle on matrix Lie groups is then employed to come up with the necessary optimality conditions for an optimal state transfer while minimizing the control effort. These necessary conditions appear as a two-point boundary value problem and are solved using a numerical technique. Results from numerical experiments are presented to illustrate the algorithm.
Towards Federated Learning at Scale: System Design
Venue: arXiv cs.LG 2019
Year: 2019

Federated Learning is a distributed machine learning approach which enables model training on a large corpus of decentralized data. We have built a scalable production system for Federated Learning in the domain of mobile devices, based on TensorFlow. In this paper, we describe the resulting high-level design, sketch some of the challenges and their solutions, and touch upon the open problems and future directions.
Regular Languages meet Prefix Sorting
Venue: arXiv cs.DS 2019
Year: 2019

Indexing strings via prefix (or suffix) sorting is, arguably, one of the most successful algorithmic techniques developed in the last decades. Can indexing be extended to languages? The main contribution of this paper is to initiate the study of the sub-class of regular languages accepted by an automaton whose states can be prefix-sorted. Starting from the recent notion of Wheeler graph [Gagie et al., TCS 2017]-which extends naturally the concept of prefix sorting to labeled graphs-we investigate the properties of Wheeler languages, that is, regular languages admitting an accepting Wheeler finite automaton. Interestingly, we characterize this family as the natural extension of regular languages endowed with the co-lexicographic ordering: when sorted, the strings belonging to a Wheeler language are partitioned into a finite number of co-lexicographic intervals, each formed by elements from a single Myhill-Nerode equivalence class. Moreover: (i) We show that every Wheeler NFA (WNFA) with $n$ states admits an equivalent Wheeler DFA (WDFA) with at most $2n-1-|Σ|$ states that can be computed in $O(n^3)$ time. This is in sharp contrast with general NFAs. (ii) We describe a quadratic algorithm to prefix-sort a proper superset of the WDFAs, a $O(n\log n)$-time online algorithm to sort acyclic WDFAs, and an optimal linear-time offline algorithm to sort general WDFAs. By contribution (i), our algorithms can also be used to index any WNFA at the moderate price of doubling the automaton's size. (iii) We provide a minimization theorem that characterizes the smallest WDFA recognizing the same language of any input WDFA. The corresponding constructive algorithm runs in optimal linear time in the acyclic case, and in $O(n\log n)$ time in the general case. (iv) We show how to compute the smallest WDFA equivalent to any acyclic DFA in nearly-optimal time.
YAFS: A simulator for IoT scenarios in fog computing
Venue: arXiv cs.NI 2019
Year: 2019

We propose a fog computing simulator for analysing the design and deployment of applications through customized and dynamical strategies. We model the relationships among deployed applications, network connections and infrastructure characteristics through complex network theory, enabling the integration of topological measures in dynamic and customizable strategies such as the placement of application modules, workload location, and path routing and scheduling of services. We present a comparative analysis of the efficiency and the convergence of results of our simulator with the most referenced entity, iFogSim. To highlight YAFS functionalities, we model three scenarios that, to the best of our knowledge, cannot be implemented with current fog simulators: dynamic allocation of new application modules, dynamic failures of network nodes and user mobility along the topology.
Advances in the Treatment of Trimmed CAD Models due to Isogeometric Analysis
Venue: arXiv cs.GR 2019
Year: 2019

Trimming is a core technique in geometric modeling. Unfortunately, the resulting objects do not take the requirements of numerical simulations into account and yield various problems. This paper outlines principal issues of trimmed models and highlights different analysis-suitable strategies to address them. It is discussed that these concepts not only provide important computational tools for isogeometric analysis, but can also improve the treatment of trimmed models in a design context.
A New Class of Searchable and Provably Highly Compressible String Transformations
Venue: arXiv cs.DS 2019
Year: 2019

The Burrows-Wheeler Transform is a string transformation that plays a fundamental role for the design of self-indexing compressed data structures. Over the years, researchers have successfully extended this transformation outside the domains of strings. However, efforts to find non-trivial alternatives of the original, now 25 years old, Burrows-Wheeler string transformation have met limited success. In this paper we bring new lymph to this area by introducing a whole new family of transformations that have all the myriad virtues of the BWT: they can be computed and inverted in linear time, they produce provably highly compressible strings, and they support linear time pattern search directly on the transformed string. This new family is a special case of a more general class of transformations based on context adaptive alphabet orderings, a concept introduced here. This more general class includes also the Alternating BWT, another invertible string transforms recently introduced in connection with a generalization of Lyndon words.
Declarative Data Analytics: a Survey
Venue: arXiv cs.DB 2019
Year: 2019

The area of declarative data analytics explores the application of the declarative paradigm on data science and machine learning. It proposes declarative languages for expressing data analysis tasks and develops systems which optimize programs written in those languages. The execution engine can be either centralized or distributed, as the declarative paradigm advocates independence from particular physical implementations. The survey explores a wide range of declarative data analysis frameworks by examining both the programming model and the optimization techniques used, in order to provide conclusions on the current state of the art in the area and identify open challenges.
When Exceptions are the Norm: Exploring the Role of Consent in HRI
Venue: arXiv cs.RO 2019
Year: 2019

HRI researchers have made major strides in developing robotic architectures that are capable of reading a limited set of social cues and producing behaviors that enhance their likeability and feeling of comfort amongst humans. However, the cues in these models are fairly direct and the interactions largely dyadic. To capture the normative qualities of interaction more robustly, we propose consent as a distinct, critical area for HRI research. Convening important insights in existing HRI work around topics like touch, proxemics, gaze, and moral norms, the notion of consent reveals key expectations that can shape how a robot acts in social space. By sorting various kinds of consent through social and legal doctrine, we delineate empirical and technical questions to meet consent challenges faced in major application domains and robotic roles. Attention to consent could show, for example, how extraordinary, norm-violating actions can be justified by agents and accepted by those around them. We argue that operationalizing ideas from legal scholarship can better guide how robotic systems might cultivate and sustain proper forms of consent.
Recommender Systems Notation: Proposed Common Notation for Teaching and Research
Venue: arXiv cs.IR 2019
Year: 2019

As the field of recommender systems has developed, authors have used a myriad of notations for describing the mathematical workings of recommendation algorithms. These notations ap-pear in research papers, books, lecture notes, blog posts, and software documentation. The dis-ciplinary diversity of the field has not contributed to consistency in notation; scholars whose home base is in information retrieval have different habits and expectations than those in ma-chine learning or human-computer interaction. In the course of years of teaching and research on recommender systems, we have seen the val-ue in adopting a consistent notation across our work. This has been particularly highlighted in our development of the Recommender Systems MOOC on Coursera (Konstan et al. 2015), as we need to explain a wide variety of algorithms and our learners are not well-served by changing notation between algorithms. In this paper, we describe the notation we have adopted in our work, along with its justification and some discussion of considered alternatives. We present this in hope that it will be useful to others writing and teaching about recommender systems. This notation has served us well for some time now, in research, online education, and traditional classroom instruction. We feel it is ready for broad use.
An Argument-Marker Model for Syntax-Agnostic Proto-Role Labeling
Venue: arXiv cs.CL 2019
Year: 2019

Semantic proto-role labeling (SPRL) is an alternative to semantic role labeling (SRL) that moves beyond a categorical definition of roles, following Dowty's feature-based view of proto-roles. This theory determines agenthood vs. patienthood based on a participant's instantiation of more or less typical agent vs. patient properties, such as, for example, volition in an event. To perform SPRL, we develop an ensemble of hierarchical models with self-attention and concurrently learned predicate-argument-markers. Our method is competitive with the state-of-the art, overall outperforming previous work in two formulations of the task (multi-label and multi-variate Likert scale prediction). In contrast to previous work, our results do not depend on gold argument heads derived from supplementary gold tree banks.
Evaluation of Multidisciplinary Effects of Artificial Intelligence with Optimization Perspective
Venue: arXiv cs.AI 2019
Year: 2019

Artificial Intelligence has an important place in the scientific community as a result of its successful outputs in terms of different fields. In time, the field of Artificial Intelligence has been divided into many sub-fields because of increasing number of different solution approaches, methods, and techniques. Machine Learning has the most remarkable role with its functions to learn from samples from the environment. On the other hand, intelligent optimization done by inspiring from nature and swarms had its own unique scientific literature, with effective solutions provided for optimization problems from different fields. Because intelligent optimization can be applied in different fields effectively, this study aims to provide a general discussion on multidisciplinary effects of Artificial Intelligence by considering its optimization oriented solutions. The study briefly focuses on background of the intelligent optimization briefly and then gives application examples of intelligent optimization from a multidisciplinary perspective.
Connecting the Unconnected: Towards Frugal 5G Network Architecture and Standardization
Venue: arXiv cs.NI 2019
Year: 2019

This article adopts a holistic approach to address the problem of poor broadband connectivity in rural areas by suggesting a novel wireless network architecture, also called the "Frugal 5G Network". To arrive at the Frugal 5G Network architecture, we take into consideration the rural connectivity needs and the characteristics specific to rural areas. As part of the proposed Frugal 5G Network, we define a heterogeneous Access Network wherein macro cells provide a carpet coverage while Wireless Local Area Networks (WLANs) provide additional capacity to serve the village clusters. WLAN is backhauled via a wireless network also called the wireless middle mile network. We define a Software Defined Networking (SDN) and Network Function Virtualization (NFV) based architecture to make the network flexible and scalable. The concepts of Fog computing have also been employed in the network architecture to bring intelligence to the edge, i.e., to the access network. Through a novel amalgamation of these technologies, we are able to address the connectivity requirements of rural areas. The proposed network architecture can serve as a potential solution towards IEEE P2061, a standardization project that aims to design an architecture to facilitate rural broadband communication.
Vignette: Perceptual Compression for Video Storage and Processing Systems
Venue: arXiv cs.MM 2019
Year: 2019

Compressed videos constitute 70% of Internet traffic, and video upload growth rates far outpace compute and storage improvement trends. Past work in leveraging perceptual cues like saliency, i.e., regions where viewers focus their perceptual attention, reduces compressed video size while maintaining perceptual quality, but requires significant changes to video codecs and ignores the data management of this perceptual information. In this paper, we propose Vignette, a compression technique and storage manager for perception-based video compression. Vignette complements off-the-shelf compression software and hardware codec implementations. Vignette's compression technique uses a neural network to predict saliency information used during transcoding, and its storage manager integrates perceptual information into the video storage system to support a perceptual compression feedback loop. Vignette's saliency-based optimizations reduce storage by up to 95% with minimal quality loss, and Vignette videos lead to power savings of 50% on mobile phones during video playback. Our results demonstrate the benefit of embedding information about the human visual system into the architecture of video storage systems.
Embodied Multimodal Multitask Learning
Venue: arXiv cs.LG 2019
Year: 2019

Recent efforts on training visual navigation agents conditioned on language using deep reinforcement learning have been successful in learning policies for different multimodal tasks, such as semantic goal navigation and embodied question answering. In this paper, we propose a multitask model capable of jointly learning these multimodal tasks, and transferring knowledge of words and their grounding in visual objects across the tasks. The proposed model uses a novel Dual-Attention unit to disentangle the knowledge of words in the textual representations and visual concepts in the visual representations, and align them with each other. This disentangled task-invariant alignment of representations facilitates grounding and knowledge transfer across both tasks. We show that the proposed model outperforms a range of baselines on both tasks in simulated 3D environments. We also show that this disentanglement of representations makes our model modular, interpretable, and allows for transfer to instructions containing new words by leveraging object detectors.
Very Long Term Field of View Prediction for 360-degree Video Streaming
Venue: arXiv cs.CV 2019
Year: 2019

360-degree videos have gained increasing popularity in recent years with the developments and advances in Virtual Reality (VR) and Augmented Reality (AR) technologies. In such applications, a user only watches a video scene within a field of view (FoV) centered in a certain direction. Predicting the future FoV in a long time horizon (more than seconds ahead) can help save bandwidth resources in on-demand video streaming while minimizing video freezing in networks with significant bandwidth variations. In this work, we treat the FoV prediction as a sequence learning problem, and propose to predict the target user's future FoV not only based on the user's own past FoV center trajectory but also other users' future FoV locations. We propose multiple prediction models based on two different FoV representations: one using FoV center trajectories and another using equirectangular heatmaps that represent the FoV center distributions. Extensive evaluations with two public datasets demonstrate that the proposed models can significantly outperform benchmark models, and other users' FoVs are very helpful for improving long-term predictions.
External Labeling Techniques: A Taxonomy and Survey
Venue: arXiv cs.CG 2019
Year: 2019

External labeling is frequently used for annotating features in graphical displays and visualizations, such as technical illustrations, anatomical drawings, or maps, with textual information. Such a labeling connects features within an illustration by thin leader lines with their labels, which are placed in the empty space surrounding the image. Over the last twenty years, a large body of literature in diverse areas of computer science has been published that investigates many different aspects, models, and algorithms for automatically placing external labels for a given set of features. This state-of-the-art report introduces a first unified taxonomy for categorizing the different results in the literature and then presents a comprehensive survey of the state of the art, a sketch of the most relevant algorithmic techniques for external labeling algorithms, as well as a list of open research challenges in this multidisciplinary research field.
Faster way to agony: Discovering hierarchies in directed graphs
Venue: arXiv cs.DS 2019
Year: 2019

Many real-world phenomena exhibit strong hierarchical structure. Consequently, in many real-world directed social networks vertices do not play equal role. Instead, vertices form a hierarchy such that the edges appear mainly from upper levels to lower levels. Discovering hierarchies from such graphs is a challenging problem that has gained attention. Formally, given a directed graph, we want to partition vertices into levels such that ideally there are only edges from upper levels to lower levels. From computational point of view, the ideal case is when the underlying directed graph is acyclic. In such case, we can partition the vertices into a hierarchy such that there are only edges from upper levels to lower edges. In practice, graphs are rarely acyclic, hence we need to penalize the edges that violate the hierarchy. One practical approach is agony, where each violating edge is penalized based on the severity of the violation. The fastest algorithm for computing agony requires $O(nm^2)$ time. In the paper we present an algorithm for computing agony that has better theoretical bound, namely $O(m^2)$. We also show that in practice the obtained bound is pessimistic and that we can use our algorithm to compute agony for large datasets. Moreover, our algorithm can be used as any-time algorithm.
Training on Synthetic Noise Improves Robustness to Natural Noise in Machine Translation
Venue: arXiv cs.CL 2019
Year: 2019

We consider the problem of making machine translation more robust to character-level variation at the source side, such as typos. Existing methods achieve greater coverage by applying subword models such as byte-pair encoding (BPE) and character-level encoders, but these methods are highly sensitive to spelling mistakes. We show how training on a mild amount of random synthetic noise can dramatically improve robustness to these variations, without diminishing performance on clean text. We focus on translation performance on natural noise, as captured by frequent corrections in Wikipedia edit logs, and show that robustness to such noise can be achieved using a balanced diet of simple synthetic noises at training time, without access to the natural noise data or distribution.
Perturbative GAN: GAN with Perturbation Layers
Venue: arXiv cs.LG 2019
Year: 2019

Perturbative GAN, which replaces convolution layers of existing convolutional GANs (DCGAN, WGAN-GP, BIGGAN, etc.) with perturbation layers that adds a fixed noise mask, is proposed. Compared with the convolu-tional GANs, the number of parameters to be trained is smaller, the convergence of training is faster, the incep-tion score of generated images is higher, and the overall training cost is reduced. Algorithmic generation of the noise masks is also proposed, with which the training, as well as the generation, can be boosted with hardware acceleration. Perturbative GAN is evaluated using con-ventional datasets (CIFAR10, LSUN, ImageNet), both in the cases when a perturbation layer is adopted only for Generators and when it is introduced to both Generator and Discriminator.
An Ensemble Dialogue System for Facts-Based Sentence Generation
Venue: arXiv cs.CL 2019
Year: 2019

This study aims to generate responses based on real-world facts by conditioning context and external facts extracted from information websites. Our system is an ensemble system that combines three modules: generated-based module, retrieval-based module, and reranking module. Therefore, this system can return diverse and meaningful responses from various perspectives. The experiments and evaluations are conducted with the sentence generation task in Dialog System Technology Challenges 7 (DSTC7-Task2). As a result, the proposed system performed significantly better than sole modules, and worked fine at the DSTC7-Task2, specifically on the objective evaluation.
Animated Drag and Drop Interaction for Dynamic Multidimensional Graphs
Venue: arXiv cs.HC 2019
Year: 2019

In this paper, we propose a new drag and drop interaction technique for graphs. We designed this interaction to support analysis in complex multidimensional and temporal graphs. The drag and drop interaction is enhanced with an intuitive and controllable animation, in support of comparison tasks.
Network Resilience Assessment via QoS Degradation Metrics: An Algorithmic Approach
Venue: arXiv cs.DS 2019
Year: 2019

This paper focuses on network resilience to perturbation of edge weight. Other than connectivity, many network applications nowadays rely upon some measure of network distance between a pair of connected nodes. In these systems, a metric related to network functionality is associated to each edge. A pair of nodes only being functional if the weighted, shortest-path distance between the pair is below a given threshold \texttt{T}. Consequently, a natural question is on which degree the change of edge weights can damage the network functionality? With this motivation, we study a new problem, \textit{Quality of Service Degradation}: given a set of pairs, find a minimum budget to increase the edge weights which ensures the distance between each pair exceeds $\mathtt{T}$. We introduce four algorithms with theoretical performance guarantees for this problem. Each of them has its own strength in trade-off between effectiveness and running time, which are illustrated both in theory and comprehensive experimental evaluation.
Deep Tree Transductions - A Short Survey
Venue: arXiv cs.LG 2019
Year: 2019

The paper surveys recent extensions of the Long-Short Term Memory networks to handle tree structures from the perspective of learning non-trivial forms of isomorph structured transductions. It provides a discussion of modern TreeLSTM models, showing the effect of the bias induced by the direction of tree processing. An empirical analysis is performed on real-world benchmarks, highlighting how there is no single model adequate to effectively approach all transduction problems.