OpenRaiser/Intern-Atlas huggingface dataset:
Protecting Privacy of Users in Brain-Computer Interface Applications
Venue: arXiv cs.CR 2019
Year: 2019

Machine learning (ML) is revolutionizing research and industry. Many ML applications rely on the use of large amounts of personal data for training and inference. Among the most intimate exploited data sources is electroencephalogram (EEG) data, a kind of data that is so rich with information that application developers can easily gain knowledge beyond the professed scope from unprotected EEG signals, including passwords, ATM PINs, and other intimate data. The challenge we address is how to engage in meaningful ML with EEG data while protecting the privacy of users. Hence, we propose cryptographic protocols based on Secure Multiparty Computation (SMC) to perform linear regression over EEG signals from many users in a fully privacy-preserving (PP) fashion, i.e.~such that each individual's EEG signals are not revealed to anyone else. To illustrate the potential of our secure framework, we show how it allows estimating the drowsiness of drivers from their EEG signals as would be possible in the unencrypted case, and at a very reasonable computational cost. Our solution is the first application of commodity-based SMC to EEG data, as well as the largest documented experiment of secret sharing based SMC in general, namely with 15 players involved in all the computations.
Computing k-Modal Embeddings of Planar Digraphs
Venue: arXiv cs.DS 2019
Year: 2019

Given a planar digraph $G$ and a positive even integer $k$, an embedding of $G$ in the plane is k-modal, if every vertex of $G$ is incident to at most $k$ pairs of consecutive edges with opposite orientations, i.e., the incoming and the outgoing edges at each vertex are grouped by the embedding into at most k sets of consecutive edges with the same orientation. In this paper, we study the $k$-Modality problem, which asks for the existence of a $k$-modal embedding of a planar digraph. This combinatorial problem is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks.
Analyses of Multi-collection Corpora via Compound Topic Modeling
Venue: arXiv cs.IR 2019
Year: 2019

As electronically stored data grow in daily life, obtaining novel and relevant information becomes challenging in text mining. Thus people have sought statistical methods based on term frequency, matrix algebra, or topic modeling for text mining. Popular topic models have centered on one single text collection, which is deficient for comparative text analyses. We consider a setting where one can partition the corpus into subcollections. Each subcollection shares a common set of topics, but there exists relative variation in topic proportions among collections. Including any prior knowledge about the corpus (e.g. organization structure), we propose the compound latent Dirichlet allocation (cLDA) model, improving on previous work, encouraging generalizability, and depending less on user-input parameters. To identify the parameters of interest in cLDA, we study Markov chain Monte Carlo (MCMC) and variational inference approaches extensively, and suggest an efficient MCMC method. We evaluate cLDA qualitatively and quantitatively using both synthetic and real-world corpora. The usability study on some real-world corpora illustrates the superiority of cLDA to explore the underlying topics automatically but also model their connections and variations across multiple collections.
Quantifying Algorithmic Biases over Time
Venue: arXiv cs.CY 2019
Year: 2019

Algorithms now permeate multiple aspects of human lives and multiple recent results have reported that these algorithms may have biases pertaining to gender, race, and other demographic characteristics. The metrics used to quantify such biases have still focused on a static notion of algorithms. However, algorithms evolve over time. For instance, Tay (a conversational bot launched by Microsoft) was arguably not biased at its launch but quickly became biased, sexist, and racist over time. We suggest a set of intuitive metrics to study the variations in biases over time and present the results for a case study for genders represented in images resulting from a Twitter image search for #Nurse and #Doctor over a period of 21 days. Results indicate that biases vary significantly over time and the direction of bias could appear to be different on different days. Hence, one-shot measurements may not suffice for understanding algorithmic bias, thus motivating further work on studying biases in algorithms over time.
SkeletonNet: Shape Pixel to Skeleton Pixel
Venue: arXiv cs.CV 2019
Year: 2019

Deep Learning for Geometric Shape Understating has organized a challenge for extracting different kinds of skeletons from the images of different objects. This competition is organized in association with CVPR 2019. There are three different tracks of this competition. The present manuscript describes the method used to train the model for the dataset provided in the first track. The first track aims to extract skeleton pixels from the shape pixels of 89 different objects. For the purpose of extracting the skeleton, a U-net model which is comprised of an encoder-decoder structure has been used. In our proposed architecture, unlike the plain decoder in the traditional Unet, we have designed the decoder in the format of HED architecture, wherein we have introduced 4 side layers and fused them to one dilation convolutional layer to connect the broken links of the skeleton. Our proposed architecture achieved the F1 score of 0.77 on test data.
Recommendations on Designing Practical Interval Type-2 Fuzzy Systems
Venue: arXiv cs.AI 2019
Year: 2019

Interval type-2 (IT2) fuzzy systems have become increasingly popular in the last 20 years. They have demonstrated superior performance in many applications. However, the operation of an IT2 fuzzy system is more complex than that of its type-1 counterpart. There are many questions to be answered in designing an IT2 fuzzy system: Should singleton or non-singleton fuzzifier be used? How many membership functions (MFs) should be used for each input? Should Gaussian or piecewise linear MFs be used? Should Mamdani or Takagi-Sugeno-Kang (TSK) inference be used? Should minimum or product $t$-norm be used? Should type-reduction be used or not? How to optimize the IT2 fuzzy system? These questions may look overwhelming and confusing to IT2 beginners. In this paper we recommend some representative starting choices for an IT2 fuzzy system design, which hopefully will make IT2 fuzzy systems more accessible to IT2 fuzzy system designers.
Graph Embeddings at Scale
Venue: arXiv cs.LG 2019
Year: 2019

Graph embedding is a popular algorithmic approach for creating vector representations for individual vertices in networks. Training these algorithms at scale is important for creating embeddings that can be used for classification, ranking, recommendation and other common applications in industry. While industrial systems exist for training graph embeddings on large datasets, many of these distributed architectures are forced to partition copious amounts of data and model logic across many worker nodes. In this paper, we propose a distributed infrastructure that completely avoids graph partitioning, dynamically creates size constrained computational graphs across worker nodes, and uses highly efficient indexing operations for updating embeddings that allow the system to function at scale. We show that our system can scale an existing embeddings algorithm - skip-gram - to train on the open-source Friendster network (68 million vertices) and on an internal heterogeneous graph (50 million vertices). We measure the performance of our system on two key quantitative metrics: link-prediction accuracy and rate of convergence. We conclude this work by analyzing how a greater number of worker nodes actually improves our system's performance on the aforementioned metrics and discuss our next steps for rigorously evaluating the embedding vectors produced by our system.
What's decidable about parametric timed automata?
Venue: arXiv cs.LO 2019
Year: 2019

Parametric timed automata (PTAs) are a powerful formalism to reason, simulate and formally verify critical real-time systems. After 25 years of research on PTAs, it is now well-understood that any non-trivial problem studied is undecidable for general PTAs. We provide here a survey of decision and computation problems for PTAs. On the one hand, bounding time, bounding the number of parameters or the domain of the parameters does not (in general) lead to any decidability. On the other hand, restricting the number of clocks, the use of clocks (compared or not with the parameters), and the use of parameters (e.g. used only as upper or lower bounds) leads to decidability of some problems. We also put emphasis on open problems. We also discuss formalisms close to parametric timed automata (such as parametric hybrid automata or parametric interrupt timed automata), and we study tools dedicated to PTAs and their extensions.
Koalja: from Data Plumbing to Smart Workspaces in the Extended Cloud
Venue: arXiv cs.DC 2019
Year: 2019

Koalja describes a generalized data wiring or `pipeline' platform, built on top of Kubernetes, for plugin user code. Koalja makes the Kubernetes underlay transparent to users (for a `serverless' experience), and offers a breadboarding experience for development of data sharing circuitry, to commoditize its gradual promotion to a production system, with a minimum of infrastructure knowledge. Enterprise grade metadata are captured as data payloads flow through the circuitry, allowing full tracing of provenance and forensic reconstruction of transactional processes, down to the versions of software that led to each outcome. Koalja attends to optimizations for avoiding unwanted processing and transportation of data, that are rapidly becoming sustainability imperatives. Thus one can minimize energy expenditure and waste, and design with scaling in mind, especially with regard to edge computing, to accommodate an Internet of Things, Network Function Virtualization, and more.
Sensitivity of Legged Balance Control to Uncertainties and Sampling Period
Venue: arXiv cs.RO 2019
Year: 2019

We propose to quantify the effect of sensor and actuator uncertainties on the control of the center of mass and center of pressure in legged robots, since this is central for maintaining their balance with a limited support polygon. Our approach is based on robust control theory, considering uncertainties that can take any value between specified bounds. This provides a principled approach to deciding optimal feedback gains. Surprisingly, our main observation is that the sampling period can be as long as 200 ms with literally no impact on maximum tracking error and, as a result, on the guarantee that balance can be maintained safely. Our findings are validated in simulations and experiments with the torque-controlled humanoid robot Toro developed at DLR. The proposed mathematical derivations and results apply nevertheless equally to biped and quadruped robots.
Linear transformations between colorings in chordal graphs
Venue: arXiv cs.DM 2019
Year: 2019

Let $k$ and $d$ be such that $k \ge d+2$. Consider two $k$-colorings of a $d$-degenerate graph $G$. Can we transform one into the other by recoloring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. If $k=d+2$, we know that there exists graphs for which a quadratic number of recolorings is needed. And when $k=2d+2$, there always exists a linear transformation. In this paper, we prove that, as long as $k \ge d+4$, there exists a transformation of length at most $f(Δ) \cdot n$ between any pair of $k$-colorings of chordal graphs (where $Δ$ denotes the maximum degree of the graph). The proof is constructive and provides a linear time algorithm that, given two $k$-colorings $c_1,c_2$ computes a linear transformation between $c_1$ and $c_2$.
Chatbots as Unwitting Actors
Venue: arXiv cs.HC 2019
Year: 2019

Chatbots are popular for both task-oriented conversations and unstructured conversations with web users. Several different approaches to creating comedy and art exist across the field of computational creativity. Despite the popularity and ease of use of chatbots, there have not been any attempts by artists or comedians to use these systems for comedy performances. We present two initial attempts to do so from our comedy podcast and call for future work toward both designing chatbots for performance and for performing alongside chatbots.
Toward Real-Time Wireless Control of Mobile Platforms for Future Industrial Systems
Venue: arXiv cs.NI 2019
Year: 2019

The use of mobile platforms (MPs) is particularly attractive for various industrial applications. This demonstration highlights the importance of remote control of MPs and shows its viability over a high-performance wireless solution designed for closed-loop control. Further, it shows the viability of formation control of a network of MPs through a leader-follower approach underpinned by high-performance wireless.
Using Deep Learning to Count Albatrosses from Space
Venue: arXiv cs.CV 2019
Year: 2019

In this paper we test the use of a deep learning approach to automatically count Wandering Albatrosses in Very High Resolution (VHR) satellite imagery. We use a dataset of manually labelled imagery provided by the British Antarctic Survey to train and develop our methods. We employ a U-Net architecture, designed for image segmentation, to simultaneously classify and localise potential albatrosses. We aid training with the use of the Focal Loss criterion, to deal with extreme class imbalance in the dataset. Initial results achieve peak precision and recall values of approximately 80%. Finally we assess the model's performance in relation to inter-observer variation, by comparing errors against an image labelled by multiple observers. We conclude model accuracy falls within the range of human counters. We hope that the methods will streamline the analysis of VHR satellite images, enabling more frequent monitoring of a species which is of high conservation concern.
Spatially-Coupled Neural Network Architectures
Venue: arXiv cs.LG 2019
Year: 2019

In this work, we leverage advances in sparse coding techniques to reduce the number of trainable parameters in a fully connected neural network. While most of the works in literature impose $\ell_1$ regularization, DropOut or DropConnect techniques to induce sparsity, our scheme considers feature importance as a criterion to allocate the trainable parameters (resources) efficiently in the network. Even though sparsity is ensured, $\ell_1$ regularization requires training on all the resources in a deep neural network. The DropOut/DropConnect techniques reduce the number of trainable parameters in the training stage by dropping a random collection of neurons/edges in the hidden layers. However, both these techniques do not pay heed to the underlying structure in the data when dropping the neurons/edges. Moreover, these frameworks require a storage space equivalent to the number of parameters in a fully connected neural network. We address the above issues with a more structured architecture inspired from spatially-coupled sparse constructions. The proposed architecture is shown to have a performance akin to a conventional fully connected neural network with dropouts, and yet achieving a $94\%$ reduction in the training parameters. Extensive simulations are presented and the performance of the proposed scheme is compared against traditional neural network architectures.
Learning Multi-Party Turn-Taking Models from Dialogue Logs
Venue: arXiv cs.CL 2019
Year: 2019

This paper investigates the application of machine learning (ML) techniques to enable intelligent systems to learn multi-party turn-taking models from dialogue logs. The specific ML task consists of determining who speaks next, after each utterance of a dialogue, given who has spoken and what was said in the previous utterances. With this goal, this paper presents comparisons of the accuracy of different ML techniques such as Maximum Likelihood Estimation (MLE), Support Vector Machines (SVM), and Convolutional Neural Networks (CNN) architectures, with and without utterance data. We present three corpora: the first with dialogues from an American TV situated comedy (chit-chat), the second with logs from a financial advice multi-bot system and the third with a corpus created from the Multi-Domain Wizard-of-Oz dataset (both are topic-oriented). The results show: (i) the size of the corpus has a very positive impact on the accuracy for the content-based deep learning approaches and those models perform best in the larger datasets; and (ii) if the dialogue dataset is small and topic-oriented (but with few topics), it is sufficient to use an agent-only MLE or SVM models, although slightly higher accuracies can be achieved with the use of the content of the utterances with a CNN model.
NullAway: Practical Type-Based Null Safety for Java
Venue: arXiv cs.SE 2019
Year: 2019

NullPointerExceptions (NPEs) are a key source of crashes in modern Java programs. Previous work has shown how such errors can be prevented at compile time via code annotations and pluggable type checking. However, such systems have been difficult to deploy on large-scale software projects, due to significant build-time overhead and / or a high annotation burden. This paper presents NullAway, a new type-based null safety checker for Java that overcomes these issues. NullAway has been carefully engineered for low overhead, so it can run as part of every build. Further, NullAway reduces annotation burden through targeted unsound assumptions, aiming for no false negatives in practice on checked code. Our evaluation shows that NullAway has significantly lower build-time overhead (1.15X) than comparable tools (2.8-5.1X). Further, on a corpus of production crash data for widely-used Android apps built with NullAway, remaining NPEs were due to unchecked third-party libraries (64%), deliberate error suppressions (17%), or reflection and other forms of post-checking code modification (17%), never due to NullAway's unsound assumptions for checked code.
Analyzing the Cross-Sensor Portability of Neural Network Architectures for LiDAR-based Semantic Labeling
Venue: arXiv cs.CV 2019
Year: 2019

State-of-the-art approaches for the semantic labeling of LiDAR point clouds heavily rely on the use of deep Convolutional Neural Networks (CNNs). However, transferring network architectures across different LiDAR sensor types represents a significant challenge, especially due to sensor specific design choices with regard to network architecture as well as data representation. In this paper we propose a new CNN architecture for the point-wise semantic labeling of LiDAR data which achieves state-of-the-art results while increasing portability across sensor types. This represents a significant advantage given the fast-paced development of LiDAR hardware technology. We perform a thorough quantitative cross-sensor analysis of semantic labeling performance in comparison to a state-of-the-art reference method. Our evaluation shows that the proposed architecture is indeed highly portable, yielding an improvement of 10 percentage points in the Intersection-over-Union (IoU) score when compared to the reference approach. Further, the results indicate that the proposed network architecture can provide an efficient way for the automated generation of large-scale training data for novel LiDAR sensor types without the need for extensive manual annotation or multi-modal label transfer.
Wireless Network Slicing: Generalized Kelly Mechanism Based Resource Allocation
Venue: arXiv cs.NI 2019
Year: 2019

Wireless network slicing (i.e., network virtualization) is one of the potential technologies for addressing the issue of rapidly growing demand in mobile data services related to 5G cellular networks. It logically decouples the current cellular networks into two entities; infrastructure providers (InPs) and mobile virtual network operators (MVNOs). The resources of base stations (e.g., resource blocks, transmission power, antennas) which are owned by the InP are shared to multiple MVNOs who need resources for their mobile users. Specifically, the physical resources of an InP are abstracted into multiple isolated network slices, which are then allocated to MVNO's mobile users. In this paper, two-level allocation problem in network slicing is examined, whilst enabling efficient resource utilization, inter-slice isolation (i.e., no interference amongst slices), and intra-slice isolation (i.e., no interference between users in the same slice). A generalized Kelly mechanism (GKM) is also designed, based on which the upper level of the resource allocation issue (i.e., between the InP and MVNOs) is addressed. The benefit of using such a resource bidding and allocation framework is that the seller (InP) does not need to know the true valuation of the bidders (MVNOs). For solving the lower level of resource allocation issue (i.e., between MVNOs and their mobile users), the optimal resource allocation is derived from each MVNO to its mobile users by using KKT conditions. Then, bandwidth resources are allocated to the users of MVNOs. Finally, the results of simulation are presented to verify the theoretical analysis of our proposed two-level resource allocation problem in wireless network slicing.
Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
Venue: arXiv cs.DS 2019
Year: 2019

We give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in $\widetilde{O}(mn^{4/3}\log{W}/ε)$ total time (where the edge weights are from $[1,W]$) and explicitly maintains a $(1+ε)$-approximate distance matrix. For a fixed $ε>0$, this is the first deterministic partially dynamic algorithm for all-pairs shortest paths in directed graphs, whose update time is $o(n^2)$ regardless of the number of edges. Furthermore, we also show how to improve the state-of-the-art partially dynamic randomized algorithms for all-pairs shortest paths [Baswana et al. STOC'02, Bernstein STOC'13] from Monte Carlo randomized to Las Vegas randomized without increasing the running time bounds (with respect to the $\widetilde{O}(\cdot)$ notation). Our results are obtained by giving new algorithms for the problem of dynamically maintaining hubs, that is a set of $\widetilde{O}(n/d)$ vertices which hit a shortest path between each pair of vertices, provided it has hop-length $Ω(d)$. We give new subquadratic deterministic and Las Vegas algorithms for maintenance of hubs under either edge insertions or deletions.
Sharing and Learning Alloy on the Web
Venue: arXiv cs.CY 2019
Year: 2019

We present Alloy4Fun, a web application that enables online editing and sharing of Alloy models and instances, to be used mainly in an educational context. By introducing the notion of secret paragraphs and commands in the models, it also allows the distribution and automatic evaluation of simple specification challenges, a useful mechanism that enables students to learn relational logic at their own pace. Alloy4Fun stores all versions of shared and analyzed models, as well as derivation trees that depict how those models evolved over time: this wealth of information can be mined by researchers or tutors to identify, for example, learning breakdowns in the class or typical mistakes made by students and other Alloy users. A beta version of Alloy4Fun was already used in two formal methods courses, and we present some results of this preliminary evaluation.