OpenRaiser/Intern-Atlas huggingface dataset:
Reasoning about strategies on collapsible pushdown arenas with imperfect information
Venue: arXiv cs.LO 2020
Year: 2020

Strategy Logic with imperfect information (SLiR) is a very expressive logic designed to express complex properties of strategic abilities in distributed systems. Previous work on SLiR focused on finite systems, and showed that the model-checking problem is decidable when information on the control states of the system is hierarchical among the players or components of the system, meaning that the players or components can be totally ordered according to their respective knowledge of the state. We show that moving from finite to infinite systems generated by collapsible (higher-order) pushdown systems preserves decidability, under the natural restriction that the stack content is visible. The proof follows the same lines as in the case of finite systems, but requires to use (collapsible) alternating pushdown tree automata. Such automata are undecidable, but semi-alternating pushdown tree automata were introduced and proved decidable, to study a strategic problem on pushdown systems with two players. In order to tackle multiple players with hierarchical information, we refine further these automata: we define direction-guided (collapsible) pushdown tree automata, and show that they are stable under projection, nondeterminisation and narrowing. For the latter operation, used to deal with imperfect information, stability holds under some assumption that is satisfied when used for systems with visible stack. We then use these automata to prove our main result.
Learning from Few Samples: A Survey
Venue: arXiv cs.CV 2020
Year: 2020

Deep neural networks have been able to outperform humans in some cases like image recognition and image classification. However, with the emergence of various novel categories, the ability to continuously widen the learning capability of such networks from limited samples, still remains a challenge. Techniques like Meta-Learning and/or few-shot learning showed promising results, where they can learn or generalize to a novel category/task based on prior knowledge. In this paper, we perform a study of the existing few-shot meta-learning techniques in the computer vision domain based on their method and evaluation metrics. We provide a taxonomy for the techniques and categorize them as data-augmentation, embedding, optimization and semantics based learning for few-shot, one-shot and zero-shot settings. We then describe the seminal work done in each category and discuss their approach towards solving the predicament of learning from few samples. Lastly we provide a comparison of these techniques on the commonly used benchmark datasets: Omniglot, and MiniImagenet, along with a discussion towards the future direction of improving the performance of these techniques towards the final goal of outperforming humans.
FC-GAGA: Fully Connected Gated Graph Architecture for Spatio-Temporal Traffic Forecasting
Venue: arXiv cs.LG 2020
Year: 2020

Forecasting of multivariate time-series is an important problem that has applications in traffic management, cellular network configuration, and quantitative finance. A special case of the problem arises when there is a graph available that captures the relationships between the time-series. In this paper we propose a novel learning architecture that achieves performance competitive with or better than the best existing algorithms, without requiring knowledge of the graph. The key element of our proposed architecture is the learnable fully connected hard graph gating mechanism that enables the use of the state-of-the-art and highly computationally efficient fully connected time-series forecasting architecture in traffic forecasting applications. Experimental results for two public traffic network datasets illustrate the value of our approach, and ablation studies confirm the importance of each element of the architecture. The code is available here: https://github.com/boreshkinai/fc-gaga.
How Work From Home Affects Collaboration: A Large-Scale Study of Information Workers in a Natural Experiment During COVID-19
Venue: arXiv cs.CY 2020
Year: 2020

The COVID-19 pandemic has had a wide-ranging impact on information workers such as higher stress levels, increased workloads, new workstreams, and more caregiving responsibilities during lockdown. COVID-19 also caused the overwhelming majority of information workers to rapidly shift to working from home (WFH). The central question this work addresses is: can we isolate the effects of WFH on information workers' collaboration activities from all other factors, especially the other effects of COVID-19? This is important because in the future, WFH will likely to be more common than it was prior to the pandemic. We use difference-in-differences (DiD), a causal identification strategy commonly used in the social sciences, to control for unobserved confounding factors and estimate the causal effect of WFH. Our analysis relies on measuring the difference in changes between those who WFH prior to COVID-19 and those who did not. Our preliminary results suggest that on average, people spent more time on collaboration in April (Post WFH mandate) than in February (Pre WFH mandate), but this is primarily due to factors other than WFH, such as lockdowns during the pandemic. The change attributable to WFH specifically is in the opposite direction: less time on collaboration and more focus time. This reversal shows the importance of using causal inference: a simple analysis would have resulted in the wrong conclusion. We further find that the effect of WFH is moderated by individual remote collaboration experience prior to WFH. Meanwhile, the medium for collaboration has also shifted due to WFH: instant messages were used more, whereas scheduled meetings were used less. We discuss design implications -- how future WFH may affect focused work, collaborative work, and creative work.
Mix Dimension in Poincaré Geometry for 3D Skeleton-based Action Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Graph Convolutional Networks (GCNs) have already demonstrated their powerful ability to model the irregular data, e.g., skeletal data in human action recognition, providing an exciting new way to fuse rich structural information for nodes residing in different parts of a graph. In human action recognition, current works introduce a dynamic graph generation mechanism to better capture the underlying semantic skeleton connections and thus improves the performance. In this paper, we provide an orthogonal way to explore the underlying connections. Instead of introducing an expensive dynamic graph generation paradigm, we build a more efficient GCN on a Riemann manifold, which we think is a more suitable space to model the graph data, to make the extracted representations fit the embedding matrix. Specifically, we present a novel spatial-temporal GCN (ST-GCN) architecture which is defined via the Poincaré geometry such that it is able to better model the latent anatomy of the structure data. To further explore the optimal projection dimension in the Riemann space, we mix different dimensions on the manifold and provide an efficient way to explore the dimension for each ST-GCN layer. With the final resulted architecture, we evaluate our method on two current largest scale 3D datasets, i.e., NTU RGB+D and NTU RGB+D 120. The comparison results show that the model could achieve a superior performance under any given evaluation metrics with only 40\% model size when compared with the previous best GCN method, which proves the effectiveness of our model.
Description of the UPPAAL Models for SRP and CSRP and Verification of their Termination and Consistency Properties
Venue: arXiv cs.NI 2020
Year: 2020

The IEEE Audio Video Bridging (AVB) Task Group (TG) was created to provide Ethernet with soft real-time guarantees. Later on, the TG was renamed to Time-Sensitive Networking (TSN) and its scope broadened to support hard real-time and critical applications. The Stream Reservation Protocol (SRP) is a key work of the TGs as it allows reserving resources in the network, guaranteeing the required quality of service (QoS). AVB's SRP is based on a distributed architecture, while TSN's is based on centralized ones. The distributed version of SRP is supported and used in TSN. Nevertheless, it was not designed to provide properties that are important for critical applications. Therefore, we propose a new version of SRP with enhanced services called Consistent Stream Reservation Protocol (CSRP). In this document we describe the SRP and CSRP UPPAAL models we developed and the queries we used to verify their termination and consistency properties.
Is there something I'm missing? Topic Modeling in eDiscovery
Venue: arXiv cs.IR 2020
Year: 2020

In legal eDiscovery, the parties are required to search through their electronically stored information to find documents that are relevant to a specific case. Negotiations over the scope of these searches are often based on a fear that something will be missed. This paper continues an argument that discovery should be based on identifying the facts of a case. If a search process is less than complete (if it has Recall less than 100%), it may still be complete in presenting all of the relevant available topics. In this study, Latent Dirichlet Allocation was used to identify 100 topics from all of the known relevant documents. The documents were then categorized to about 80% Recall (i.e., 80% of the relevant documents were found by the categorizer, designated the hit set and 20% were missed, designated the missed set). Despite the fact that less than all of the relevant documents were identified by the categorizer, the documents that were identified contained all of the topics derived from the full set of documents. This same pattern held whether the categorizer was a naïve Bayes categorizer trained on a random selection of documents or a Support Vector Machine trained with Continuous Active Learning (which focuses evaluation on the most-likely-to-be-relevant documents). No topics were identified in either categorizer's missed set that were not already seen in the hit set. Not only is a computer-assisted search process reasonable (as required by the Federal Rules of Civil Procedure), it is also complete when measured by topics.
The Program with a Personality: Analysis of Elk Cloner, the First Personal Computer Virus
Venue: arXiv cs.CR 2020
Year: 2020

Although self-replicating programs and viruses have existed since the 1960s and 70s, Elk Cloner was the first virus to circulate among personal computers in the wild. Despite its historical significance, it received comparatively little attention when it first appeared in 1982. In this paper, we: present the first detailed examination of the operation and structure of Elk Cloner; discuss the effect of environmental characteristics on its virulence; and provide supporting evidence for several hypotheses about why its release was largely ignored in the early 1980s.
New Results in Sona Drawing: Hardness and TSP Separation
Venue: arXiv cs.CG 2020
Year: 2020

Given a set of point sites, a sona drawing is a single closed curve, disjoint from the sites and intersecting itself only in simple crossings, so that each bounded region of its complement contains exactly one of the sites. We prove that it is NP-hard to find a minimum-length sona drawing for $n$ given points, and that such a curve can be longer than the TSP tour of the same points by a factor $> 1.5487875$. When restricted to tours that lie on the edges of a square grid, with points in the grid cells, we prove that it is NP-hard even to decide whether such a tour exists. These results answer questions posed at CCCG 2006.
Denoising individual bias for a fairer binary submatrix detection
Venue: arXiv cs.LG 2020
Year: 2020

Low rank representation of binary matrix is powerful in disentangling sparse individual-attribute associations, and has received wide applications. Existing binary matrix factorization (BMF) or co-clustering (CC) methods often assume i.i.d background noise. However, this assumption could be easily violated in real data, where heterogeneous row- or column-wise probability of binary entries results in disparate element-wise background distribution, and paralyzes the rationality of existing methods. We propose a binary data denoising framework, namely BIND, which optimizes the detection of true patterns by estimating the row- or column-wise mixture distribution of patterns and disparate background, and eliminating the binary attributes that are more likely from the background. BIND is supported by thoroughly derived mathematical property of the row- and column-wise mixture distributions. Our experiment on synthetic and real-world data demonstrated BIND effectively removes background noise and drastically increases the fairness and accuracy of state-of-the arts BMF and CC methods.
TEAM: We Need More Powerful Adversarial Examples for DNNs
Venue: arXiv cs.LG 2020
Year: 2020

Although deep neural networks (DNNs) have achieved success in many application fields, it is still vulnerable to imperceptible adversarial examples that can lead to misclassification of DNNs easily. To overcome this challenge, many defensive methods are proposed. Indeed, a powerful adversarial example is a key benchmark to measure these defensive mechanisms. In this paper, we propose a novel method (TEAM, Taylor Expansion-Based Adversarial Methods) to generate more powerful adversarial examples than previous methods. The main idea is to craft adversarial examples by minimizing the confidence of the ground-truth class under untargeted attacks or maximizing the confidence of the target class under targeted attacks. Specifically, we define the new objective functions that approximate DNNs by using the second-order Taylor expansion within a tiny neighborhood of the input. Then the Lagrangian multiplier method is used to obtain the optimize perturbations for these objective functions. To decrease the amount of computation, we further introduce the Gauss-Newton (GN) method to speed it up. Finally, the experimental result shows that our method can reliably produce adversarial examples with 100% attack success rate (ASR) while only by smaller perturbations. In addition, the adversarial example generated with our method can defeat defensive distillation based on gradient masking.
Towards Deep Robot Learning with Optimizer applicable to Non-stationary Problems
Venue: arXiv cs.LG 2020
Year: 2020

This paper proposes a new optimizer for deep learning, named d-AmsGrad. In the real-world data, noise and outliers cannot be excluded from dataset to be used for learning robot skills. This problem is especially striking for robots that learn by collecting data in real time, which cannot be sorted manually. Several noise-robust optimizers have therefore been developed to resolve this problem, and one of them, named AmsGrad, which is a variant of Adam optimizer, has a proof of its convergence. However, in practice, it does not improve learning performance in robotics scenarios. This reason is hypothesized that most of robot learning problems are non-stationary, but AmsGrad assumes the maximum second momentum during learning to be stationarily given. In order to adapt to the non-stationary problems, an improved version, which slowly decays the maximum second momentum, is proposed. The proposed optimizer has the same capability of reaching the global optimum as baselines, and its performance outperformed that of the baselines in robotics problems.
Neural Style Transfer for Remote Sensing
Venue: arXiv cs.CV 2020
Year: 2020

The well-known technique outlined in the paper of Leon A. Gatys et al., A Neural Algorithm of Artistic Style, has become a trending topic both in academic literature and industrial applications. Neural Style Transfer (NST) constitutes an essential tool for a wide range of applications, such as artistic stylization of 2D images, user-assisted creation tools and production tools for entertainment applications. The purpose of this study is to present a method for creating artistic maps from satellite images, based on the NST algorithm. This method includes three basic steps (i) application of semantic image segmentation on the original satellite image, dividing its content into classes (i.e. land, water), (ii) application of neural style transfer for each class and (iii) creation of a collage, i.e. an artistic image consisting of a combination of the two stylized image generated on the previous step.
Turbo Coded Single User Massive MIMO with Precoding
Venue: arXiv cs.IT 2020
Year: 2020

Precoding is a method of compensating the channel at the transmitter. This work presents a novel method of data detection in turbo coded single user massive multiple input multiple output (MIMO) systems using precoding. We show via computer simulations that, when precoding is used, re-transmitting the data does not result in significant reduction in bit-error-rate (BER), thus increasing the spectral efficiency, compared to the case without precoding. Moreover, increasing the number of transmit and receive antennas results in improved BER.
Genetic Improvement @ ICSE 2020
Venue: arXiv cs.SE 2020
Year: 2020

Following Prof. Mark Harman of Facebook's keynote and formal presentations (which are recorded in the proceedings) there was a wide ranging discussion at the eighth international Genetic Improvement workshop, GI-2020 @ ICSE (held as part of the 42nd ACM/IEEE International Conference on Software Engineering on Friday 3rd July 2020). Topics included industry take up, human factors, explainabiloity (explainability, justifyability, exploitability) and GI benchmarks. We also contrast various recent online approaches (e.g. SBST 2020) to holding virtual computer science conferences and workshops via the WWW on the Internet without face-2-face interaction. Finally we speculate on how the Coronavirus Covid-19 Pandemic will affect research next year and into the future.
Hierarchical BiGraph Neural Network as Recommendation Systems
Venue: arXiv cs.LG 2020
Year: 2020

Graph neural networks emerge as a promising modeling method for applications dealing with datasets that are best represented in the graph domain. In specific, developing recommendation systems often require addressing sparse structured data which often lacks the feature richness in either the user and/or item side and requires processing within the correct context for optimal performance. These datasets intuitively can be mapped to and represented as networks or graphs. In this paper, we propose the Hierarchical BiGraph Neural Network (HBGNN), a hierarchical approach of using GNNs as recommendation systems and structuring the user-item features using a bigraph framework. Our experimental results show competitive performance with current recommendation system methods and transferability.
Word Embeddings: Stability and Semantic Change
Venue: arXiv cs.CL 2020
Year: 2020

Word embeddings are computed by a class of techniques within natural language processing (NLP), that create continuous vector representations of words in a language from a large text corpus. The stochastic nature of the training process of most embedding techniques can lead to surprisingly strong instability, i.e. subsequently applying the same technique to the same data twice, can produce entirely different results. In this work, we present an experimental study on the instability of the training process of three of the most influential embedding techniques of the last decade: word2vec, GloVe and fastText. Based on the experimental results, we propose a statistical model to describe the instability of embedding techniques and introduce a novel metric to measure the instability of the representation of an individual word. Finally, we propose a method to minimize the instability - by computing a modified average over multiple runs - and apply it to a specific linguistic problem: The detection and quantification of semantic change, i.e. measuring changes in the meaning and usage of words over time.
Exclusion and Inclusion -- A model agnostic approach to feature importance in DNNs
Venue: arXiv cs.CL 2020
Year: 2020

Deep Neural Networks in NLP have enabled systems to learn complex non-linear relationships. One of the major bottlenecks towards being able to use DNNs for real world applications is their characterization as black boxes. To solve this problem, we introduce a model agnostic algorithm which calculates phrase-wise importance of input features. We contend that our method is generalizable to a diverse set of tasks, by carrying out experiments for both Regression and Classification. We also observe that our approach is robust to outliers, implying that it only captures the essential aspects of the input.
Quasi-Cyclic Codes
Venue: arXiv cs.IT 2020
Year: 2020

Quasi-cyclic codes form an important class of algebraic codes that includes cyclic codes as a special subclass. This chapter focuses on the algebraic structure of quasi-cyclic codes, first. Based on these structural properties, some asymptotic results, a few minimum distance bounds and further applications such as the trace representation and characterization of certain subfamilies of quasi-cyclic codes are elaborated. This survey will appear as a chapter in "A Concise Encyclopedia of Coding Theory" to be published by CRC Press.
SimulEval: An Evaluation Toolkit for Simultaneous Translation
Venue: arXiv cs.CL 2020
Year: 2020

Simultaneous translation on both text and speech focuses on a real-time and low-latency scenario where the model starts translating before reading the complete source input. Evaluating simultaneous translation models is more complex than offline models because the latency is another factor to consider in addition to translation quality. The research community, despite its growing focus on novel modeling approaches to simultaneous translation, currently lacks a universal evaluation procedure. Therefore, we present SimulEval, an easy-to-use and general evaluation toolkit for both simultaneous text and speech translation. A server-client scheme is introduced to create a simultaneous translation scenario, where the server sends source input and receives predictions for evaluation and the client executes customized policies. Given a policy, it automatically performs simultaneous decoding and collectively reports several popular latency metrics. We also adapt latency metrics from text simultaneous translation to the speech task. Additionally, SimulEval is equipped with a visualization interface to provide better understanding of the simultaneous decoding process of a system. SimulEval has already been extensively used for the IWSLT 2020 shared task on simultaneous speech translation. Code will be released upon publication.
Process of Efficiently Parallelizing a Protein Structure Determination Algorithm
Venue: arXiv cs.DC 2020
Year: 2020

Computational protein structure determination involves optimization in a problem space much too large to exhaustively search. Existing approaches include optimization algorithms such as gradient descent and simulated annealing, but these typically only find local minima. One novel approach implemented in REDcRAFT is to instead of folding a protein all at the same time, fold it residue by residue. This simulates a protein folding as each residue exits from the generating ribosome. While REDcRAFT exponentially reduces the problem space so it can be explored in polynomial time, it is still extremely computationally demanding. This algorithm does have the advantage that most of the execution time is spent in inherently parallelizable code. However, preliminary results from parallel execution indicate that approximately two-thirds of execution time is dedicated to system overhead. Additionally, by carefully analyzing and timing the structure of the program the major bottlenecks can be identified. After addressing these issues, REDcRAFT becomes a scalable parallel application with nearly two orders of magnitude improvement.