OpenRaiser/Intern-Atlas huggingface dataset:
A Way to a Universal VR Accessibility Toolkit
Venue: arXiv cs.CY 2021
Year: 2021

Virtual Reality (VR) has become more and more popular with dropping prices for systems and a growing number of users. However, the issue of accessibility in VR has been hardly addressed so far and no uniform approach or standard exists at this time. In this position paper, we propose a customisable toolkit implemented at the system-level and discuss the potential benefits of this approach and challenges that will need to be overcome for a successful implementation.
Optimizing travel routes using temporal networks constructed from GPS data
Venue: arXiv cs.SI 2021
Year: 2021

Because of the complexity of urban transportation networks and the temporal changes in traffic conditions, it is difficult to assess real-time traffic situations. However, the development of information terminals has made it easier to obtain personal mobility information. In this study, we propose methods for evaluating the mobility of people in a city using global positioning system data. There are two main methods for evaluating movement. One is to create a temporal network from real data and check the change in travel time according to time zones or seasons. Temporal networks are difficult to evaluate because of their time complexity, and in this study, we proposed an evaluation method using the probability density function of travel time. The other method is to define a time-dependent traveling salesman problem and find an efficient traveling route by finding the shortest path. By creating a time-dependent traveling salesman problem in an existing city and solving it, a traveler can choose an efficient route by considering traffic conditions at different times of the day. We used 2 months of data from Kyoto City to conduct a traffic evaluation as a case study.
Experiments with graph convolutional networks for solving the vertex $p$-center problem
Venue: arXiv cs.LG 2021
Year: 2021

In the last few years, graph convolutional networks (GCN) have become a popular research direction in the machine learning community to tackle NP-hard combinatorial optimization problems (COPs) defined on graphs. While the obtained results are usually still not competitive with problem-specific solution approaches from the operations research community, GCNs often lead to improvements compared to previous machine learning approaches for classical COPs such as the traveling salesperson problem (TSP). In this work we present a preliminary study on using GCNs for solving the vertex p-center problem (PCP), which is another classic COP on graphs. In particular, we investigate whether a successful model based on end-to-end training for the TSP can be adapted to a PCP, which is defined on a similar 2D Euclidean graph input as the usually used version of the TSP. However, the objective of the PCP has a min-max structure which could lead to many symmetric optimal, i.e., ground-truth solutions and other potential difficulties for learning. Our obtained preliminary results show that indeed a direct transfer of network architecture ideas does not seem to work too well. Thus we think that the PCP could be an interesting benchmark problem for new ideas and developments in the area of GCNs.
Learning Football Body-Orientation as a Matter of Classification
Venue: arXiv cs.LG 2021
Year: 2021

Orientation is a crucial skill for football players that becomes a differential factor in a large set of events, especially the ones involving passes. However, existing orientation estimation methods, which are based on computer-vision techniques, still have a lot of room for improvement. To the best of our knowledge, this article presents the first deep learning model for estimating orientation directly from video footage. By approaching this challenge as a classification problem where classes correspond to orientation bins, and by introducing a cyclic loss function, a well-known convolutional network is refined to provide player orientation data. The model is trained by using ground-truth orientation data obtained from wearable EPTS devices, which are individually compensated with respect to the perceived orientation in the current frame. The obtained results outperform previous methods; in particular, the absolute median error is less than 12 degrees per player. An ablation study is included in order to show the potential generalization to any kind of football video footage.
Natural Statistics of Network Activations and Implications for Knowledge Distillation
Venue: arXiv cs.CV 2021
Year: 2021

In a matter that is analog to the study of natural image statistics, we study the natural statistics of the deep neural network activations at various layers. As we show, these statistics, similar to image statistics, follow a power law. We also show, both analytically and empirically, that with depth the exponent of this power law increases at a linear rate. As a direct implication of our discoveries, we present a method for performing Knowledge Distillation (KD). While classical KD methods consider the logits of the teacher network, more recent methods obtain a leap in performance by considering the activation maps. This, however, uses metrics that are suitable for comparing images. We propose to employ two additional loss terms that are based on the spectral properties of the intermediate activation maps. The proposed method obtains state of the art results on multiple image recognition KD benchmarks.
Rate-Splitting Multiple Access in Cache-Aided Cloud-Radio Access Networks
Venue: arXiv cs.IT 2021
Year: 2021

Rate-splitting multiple access (RSMA) has been recognized as a promising physical layer strategy for 6G. Motivated by ever increasing popularity of cache-enabled content delivery in wireless communications, this paper proposes an innovative multigroup multicast transmission scheme based on RSMA for cache-aided cloud-radio access networks (C-RAN). Our proposed scheme not only exploits the properties of content-centric communications and local caching at the base stations (BSs), but also incorporates RSMA to better manage interference in multigroup multicast transmission with statistical channel state information (CSI) known at the central processor (CP) and the BSs. At the RSMA-enabled cloud CP, the message of each multicast group is split into a private and a common part with the former private part being decoded by all users in the respective group and the latter common part being decoded by multiple users from other multicast groups. Common message decoding is done for the purpose of mitigating the interference. In this work, we jointly optimize the clustering of BSs and the precoding with the aim of maximizing the minimum rate among all multicast groups to guarantee fairness serving all groups. The problem is a mixed-integer non-linear stochastic program (MINLSP), which is solved by a practical algorithm we proposed including a heuristic clustering algorithm for assigning a set of BSs to serve each user followed by an efficient iterative algorithm that combines the sample average approximation (SAA) and weighted minimum mean square error (WMMSE) to solve the stochastic non-convex sub-problem of precoder design. Numerical results show the explicit max-min rate gain of our proposed transmission scheme compared to the state-of-the-art trivial interference processing methods. Therefore, we conclude that RSMA is a promising technique for cache-aided C-RAN.
Fault-Tolerant Labeling and Compact Routing Schemes
Venue: arXiv cs.DS 2021
Year: 2021

The paper presents fault-tolerant (FT) labeling schemes for general graphs, as well as, improved FT routing schemes. For a given $n$-vertex graph $G$ and a bound $f$ on the number of faults, an $f$-FT connectivity labeling scheme is a distributed data structure that assigns each of the graph edges and vertices a short label, such that given the labels of the vertices $s$ and $t$, and at most $f$ failing edges $F$, one can determine if $s$ and $t$ are connected in $G \setminus F$. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS '07], compact FT labeling schemes have been devised only for a limited collection of graph families. In this work, we fill in this gap by proposing two (independent) FT connectivity labeling schemes for general graphs, with a nearly optimal label length. This serves the basis for providing also FT approximate distance labeling schemes, and ultimately also routing schemes. Our main results for an $n$-vertex graph and a fault bound $f$ are: -- There is a randomized FT connectivity labeling scheme with a label length of $O(f+\log n)$ bits, hence optimal for $f=O(\log n)$. This scheme is based on the notion of cycle space sampling [Pritchard, Thurimella, TALG '11]. -- There is a randomized FT connectivity labeling scheme with a label length of $O(\log^3 n)$ bits (independent of the number of faults $f$). This scheme is based on the notion of linear sketches of [Ahn et al., SODA '12]. -- For $k\geq 1$, there is a randomized routing scheme that routes a message from $s$ to $t$ in the presence of a set $F$ of faulty edges, with stretch $O(|F|^2 k)$ and routing tables of size $\tilde{O}(f^3 n^{1/k})$. This significantly improves over the state-of-the-art bounds by [Chechik, ICALP '11], providing the first scheme with sub-linear FT labeling and routing schemes for general graphs.
Decision Concept Lattice vs. Decision Trees and Random Forests
Venue: arXiv cs.LG 2021
Year: 2021

Decision trees and their ensembles are very popular models of supervised machine learning. In this paper we merge the ideas underlying decision trees, their ensembles and FCA by proposing a new supervised machine learning model which can be constructed in polynomial time and is applicable for both classification and regression problems. Specifically, we first propose a polynomial-time algorithm for constructing a part of the concept lattice that is based on a decision tree. Second, we describe a prediction scheme based on a concept lattice for solving both classification and regression tasks with prediction quality comparable to that of state-of-the-art models.
Low-Complexity Symbol-Level Precoding for MU-MISO Downlink Systems with QAM Signals
Venue: arXiv cs.IT 2021
Year: 2021

This study proposes the construction of a transmit signal for large-scale antenna systems with cost-effective 1-bit digital-to-analog converters in the downlink. Under quadrature-amplitude-modulation constellations, it is still an open problem to overcome a severe error floor problem caused by its nature property. To this end, we first present a feasibility condition which guarantees that each user's noiseless signal is placed in the desired decision region. For robustness to additive noise, we formulate an optimization problem, we then transform the feasibility conditions to cascaded matrix form. We propose a low-complexity algorithm to generate a 1-bit transmit signal based on the proposed optimization problem formulated as a well-defined mixed-integer-linear-programming. Numerical results validate the superiority of the proposed method in terms of detection performance and computational complexity.
KGPool: Dynamic Knowledge Graph Context Selection for Relation Extraction
Venue: arXiv cs.CL 2021
Year: 2021

We present a novel method for relation extraction (RE) from a single sentence, mapping the sentence and two given entities to a canonical fact in a knowledge graph (KG). Especially in this presumed sentential RE setting, the context of a single sentence is often sparse. This paper introduces the KGPool method to address this sparsity, dynamically expanding the context with additional facts from the KG. It learns the representation of these facts (entity alias, entity descriptions, etc.) using neural methods, supplementing the sentential context. Unlike existing methods that statically use all expanded facts, KGPool conditions this expansion on the sentence. We study the efficacy of KGPool by evaluating it with different neural models and KGs (Wikidata and NYT Freebase). Our experimental evaluation on standard datasets shows that by feeding the KGPool representation into a Graph Neural Network, the overall method is significantly more accurate than state-of-the-art methods.
Detecting Anomalies in Semantic Segmentation with Prototypes
Venue: arXiv cs.CV 2021
Year: 2021

Traditional semantic segmentation methods can recognize at test time only the classes that are present in the training set. This is a significant limitation, especially for semantic segmentation algorithms mounted on intelligent autonomous systems, deployed in realistic settings. Regardless of how many classes the system has seen at training time, it is inevitable that unexpected, unknown objects will appear at test time. The failure in identifying such anomalies may lead to incorrect, even dangerous behaviors of the autonomous agent equipped with such segmentation model when deployed in the real world. Current state of the art of anomaly segmentation uses generative models, exploiting their incapability to reconstruct patterns unseen during training. However, training these models is expensive, and their generated artifacts may create false anomalies. In this paper we take a different route and we propose to address anomaly segmentation through prototype learning. Our intuition is that anomalous pixels are those that are dissimilar to all class prototypes known by the model. We extract class prototypes from the training data in a lightweight manner using a cosine similarity-based classifier. Experiments on StreetHazards show that our approach achieves the new state of the art, with a significant margin over previous works, despite the reduced computational overhead. Code is available at https://github.com/DarioFontanel/PAnS.
CIDER: Commonsense Inference for Dialogue Explanation and Reasoning
Venue: arXiv cs.CL 2021
Year: 2021

Commonsense inference to understand and explain human language is a fundamental research problem in natural language processing. Explaining human conversations poses a great challenge as it requires contextual understanding, planning, inference, and several aspects of reasoning including causal, temporal, and commonsense reasoning. In this work, we introduce CIDER -- a manually curated dataset that contains dyadic dialogue explanations in the form of implicit and explicit knowledge triplets inferred using contextual commonsense inference. Extracting such rich explanations from conversations can be conducive to improving several downstream applications. The annotated triplets are categorized by the type of commonsense knowledge present (e.g., causal, conditional, temporal). We set up three different tasks conditioned on the annotated dataset: Dialogue-level Natural Language Inference, Span Extraction, and Multi-choice Span Selection. Baseline results obtained with transformer-based models reveal that the tasks are difficult, paving the way for promising future research. The dataset and the baseline implementations are publicly available at https://cider-task.github.io/cider/.
Student Performance Prediction Using Dynamic Neural Models
Venue: arXiv cs.LG 2021
Year: 2021

We address the problem of predicting the correctness of the student's response on the next exam question based on their previous interactions in the course of their learning and evaluation process. We model the student performance as a dynamic problem and compare the two major classes of dynamic neural architectures for its solution, namely the finite-memory Time Delay Neural Networks (TDNN) and the potentially infinite-memory Recurrent Neural Networks (RNN). Since the next response is a function of the knowledge state of the student and this, in turn, is a function of their previous responses and the skills associated with the previous questions, we propose a two-part network architecture. The first part employs a dynamic neural network (either TDNN or RNN) to trace the student knowledge state. The second part applies on top of the dynamic part and it is a multi-layer feed-forward network which completes the classification task of predicting the student response based on our estimate of the student knowledge state. Both input skills and previous responses are encoded using different embeddings. Regarding the skill embeddings we tried two different initialization schemes using (a) random vectors and (b) pretrained vectors matching the textual descriptions of the skills. Our experiments show that the performance of the RNN approach is better compared to the TDNN approach in all datasets that we have used. Also, we show that our RNN architecture outperforms the state-of-the-art models in four out of five datasets. It is worth noting that the TDNN approach also outperforms the state of the art models in four out of five datasets, although it is slightly worse than our proposed RNN approach. Finally, contrary to our expectations, we find that the initialization of skill embeddings using pretrained vectors offers practically no advantage over random initialization.
MalPhase: Fine-Grained Malware Detection Using Network Flow Data
Venue: arXiv cs.CR 2021
Year: 2021

Economic incentives encourage malware authors to constantly develop new, increasingly complex malware to steal sensitive data or blackmail individuals and companies into paying large ransoms. In 2017, the worldwide economic impact of cyberattacks is estimated to be between 445 and 600 billion USD, or 0.8% of global GDP. Traditionally, one of the approaches used to defend against malware is network traffic analysis, which relies on network data to detect the presence of potentially malicious software. However, to keep up with increasing network speeds and amount of traffic, network analysis is generally limited to work on aggregated network data, which is traditionally challenging and yields mixed results. In this paper we present MalPhase, a system that was designed to cope with the limitations of aggregated flows. MalPhase features a multi-phase pipeline for malware detection, type and family classification. The use of an extended set of network flow features and a simultaneous multi-tier architecture facilitates a performance improvement for deep learning models, making them able to detect malicious flows (>98% F1) and categorize them to a respective malware type (>93% F1) and family (>91% F1). Furthermore, the use of robust features and denoising autoencoders allows MalPhase to perform well on samples with varying amounts of benign traffic mixed in. Finally, MalPhase detects unseen malware samples with performance comparable to that of known samples, even when interlaced with benign flows to reflect realistic network environments.
Counterfactual Invariance to Spurious Correlations: Why and How to Pass Stress Tests
Venue: arXiv cs.LG 2021
Year: 2021

Informally, a 'spurious correlation' is the dependence of a model on some aspect of the input data that an analyst thinks shouldn't matter. In machine learning, these have a know-it-when-you-see-it character; e.g., changing the gender of a sentence's subject changes a sentiment predictor's output. To check for spurious correlations, we can 'stress test' models by perturbing irrelevant parts of input data and seeing if model predictions change. In this paper, we study stress testing using the tools of causal inference. We introduce counterfactual invariance as a formalization of the requirement that changing irrelevant parts of the input shouldn't change model predictions. We connect counterfactual invariance to out-of-domain model performance, and provide practical schemes for learning (approximately) counterfactual invariant predictors (without access to counterfactual examples). It turns out that both the means and implications of counterfactual invariance depend fundamentally on the true underlying causal structure of the data -- in particular, whether the label causes the features or the features cause the label. Distinct causal structures require distinct regularization schemes to induce counterfactual invariance. Similarly, counterfactual invariance implies different domain shift guarantees depending on the underlying causal structure. This theory is supported by empirical results on text classification.
Towards Interpretable Attention Networks for Cervical Cancer Analysis
Venue: arXiv cs.CV 2021
Year: 2021

Recent advances in deep learning have enabled the development of automated frameworks for analysing medical images and signals, including analysis of cervical cancer. Many previous works focus on the analysis of isolated cervical cells, or do not offer sufficient methods to explain and understand how the proposed models reach their classification decisions on multi-cell images. Here, we evaluate various state-of-the-art deep learning models and attention-based frameworks for the classification of images of multiple cervical cells. As we aim to provide interpretable deep learning models to address this task, we also compare their explainability through the visualization of their gradients. We demonstrate the importance of using images that contain multiple cells over using isolated single-cell images. We show the effectiveness of the residual channel attention model for extracting important features from a group of cells, and demonstrate this model's efficiency for this classification task. This work highlights the benefits of channel attention mechanisms in analyzing multiple-cell images for potential relations and distributions within a group of cells. It also provides interpretable models to address the classification of cervical cells.
Triggerflow: Trigger-based Orchestration of Serverless Workflows
Venue: arXiv cs.DC 2021
Year: 2021

As more applications are being moved to the Cloud thanks to serverless computing, it is increasingly necessary to support the native life cycle execution of those applications in the data center. But existing cloud orchestration systems either focus on short-running workflows (like IBM Composer or Amazon Step Functions Express Workflows) or impose considerable overheads for synchronizing massively parallel jobs (Azure Durable Functions, Amazon Step Functions). None of them are open systems enabling extensible interception and optimization of custom workflows. We present Triggerflow: an extensible Trigger-based Orchestration architecture for serverless workflows. We demonstrate that Triggerflow is a novel serverless building block capable of constructing different reactive orchestrators (State Machines, Directed Acyclic Graphs, Workflow as code, Federated Learning orchestrator). We also validate that it can support high-volume event processing workloads, auto-scale on demand with scale down to zero when not used, and transparently guarantee fault tolerance and efficient resource usage when orchestrating long running scientific workflows.
Colonel Blotto Games with Favoritism: Competitions with Pre-allocations and Asymmetric Effectiveness
Venue: arXiv cs.GT 2021
Year: 2021

We introduce the Colonel Blotto game with favoritism, an extension of the famous Colonel Blotto game where the winner-determination rule is generalized to include pre-allocations and asymmetry of the players' resources effectiveness on each battlefield. Such favoritism is found in many classical applications of the Colonel Blotto game. We focus on the Nash equilibrium. First, we consider the closely related model of all-pay auctions with favoritism and completely characterize its equilibrium. Based on this result, we prove the existence of a set of optimal univariate distributions -- which serve as candidate marginals for an equilibrium -- of the Colonel Blotto game with favoritism and show an explicit construction thereof. In several particular cases, this directly leads to an equilibrium of the Colonel Blotto game with favoritism. In other cases, we use these optimal univariate distributions to derive an approximate equilibrium with well-controlled approximation error. Finally, we propose an algorithm -- based on the notion of winding number in parametric curves -- to efficiently compute an approximation of the proposed optimal univariate distributions with arbitrarily small error.