OpenRaiser/Intern-Atlas huggingface dataset:
Mobile Reconfigurable Intelligent Surfaces for NOMA Networks: Federated Learning Approaches
Venue: arXiv cs.NI 2021
Year: 2021

A novel framework of reconfigurable intelligent surfaces (RISs)-enhanced indoor wireless networks is proposed, where an RIS mounted on the robot is invoked to enable mobility of the RIS and enhance the service quality for mobile users. Meanwhile, non-orthogonal multiple access (NOMA) techniques are adopted to further increase the spectrum efficiency since RISs are capable to provide NOMA with artificial controlled channel conditions, which can be seen as a beneficial operation condition to obtain NOMA gains. To optimize the sum rate of all users, a deep deterministic policy gradient (DDPG) algorithm is invoked to optimize the deployment and phase shifts of the mobile RIS as well as the power allocation policy. In order to improve the efficiency and effectiveness of agent training for the DDPG agents, a federated learning (FL) concept is adopted to enable multiple agents to simultaneously explore similar environments and exchange experiences. We also proved that with the same random exploring policy, the FL armed deep reinforcement learning (DRL) agents can theoretically obtain a reward gain compare to the independent agents. Our simulation results indicate that the mobile RIS scheme can significantly outperform the fixed RIS paradigm, which provides about three times data rate gain compare to the fixed RIS paradigm. Moreover, the NOMA scheme is capable to achieve a gain of 42% in contrast with the OMA scheme in terms of sum rate. Finally, the multi-cell simulation proved that the FL enhanced DDPG algorithm has a superior convergence rate and optimization performance than the independent training framework.
Projection matrices and related viewing frustums: new ways to create and apply
Venue: arXiv cs.GR 2021
Year: 2021

In computer graphics, the field of view of a camera is represented by a viewing frustum and a corresponding projection matrix, the properties of which, in the absence of restrictions on rectangular shape of the near plane and its parallelism to the far plane are currently not fully explored and structured. This study aims to consider the properties of arbitrary affine frustums, as well as various techniques for their transformation for practical use in devices with limited resources. Additionally, this article explores the methods of working with the visible volume as an arbitrary frustum that is not associated with the projection matrix. To study the properties of affine frustums, the dependencies between its planes and formulas for obtaining key points from the inverse projection matrix were derived. Methods of constructing frustum by key points and given planes were also considered. Moreover, frustum transformation formulas were obtained to simulate the effects of reflection, refraction and cropping in devices with limited resources. In conclusion, a method was proposed for applying an arbitrary frustum, which does not have a corresponding projection matrix, to limit the visible volume and then transform the points into NDC space.
Interactive Query Formulation using Query By Navigation
Venue: arXiv cs.IR 2021
Year: 2021

Effective information disclosure in the context of databases with a large conceptual schema is known to be a non-trivial problem. In particular the formulation of ad-hoc queries is a major problem in such contexts. Existing approaches for tackling this problem include graphical query interfaces, query by navigation, query by construction, and point to point queries. In this report we propose an adoption of the query by navigation mechanism that is especially geared towards the InfoAssistant product. Query by navigation is based on ideas from the information retrieval world, in particular on the stratified hypermedia architecture. When using our approach to the formulations of queries, a user will first formulate a number of simple queries corresponding to linear paths through the information structure. The formulation of the linear paths is the result of the {\em explorative phase} of the query formulation. Once users have specified a number of these linear paths, they may combine them to form more complex queries. Examples of such combinations are: concatenation, union, intersection and selection. This last process is referred to as {\em query by construction}, and is the {\em constructive phase} of the query formulation process.
Dual-side Sparse Tensor Core
Venue: arXiv cs.AR 2021
Year: 2021

Leveraging sparsity in deep neural network (DNN) models is promising for accelerating model inference. Yet existing GPUs can only leverage the sparsity from weights but not activations, which are dynamic, unpredictable, and hence challenging to exploit. In this work, we propose a novel architecture to efficiently harness the dual-side sparsity (i.e., weight and activation sparsity). We take a systematic approach to understand the (dis)advantages of previous sparsity-related architectures and propose a novel, unexplored paradigm that combines outer-product computation primitive and bitmap-based encoding format. We demonstrate the feasibility of our design with minimal changes to the existing production-scale inner-product-based Tensor Core. We propose a set of novel ISA extensions and co-design the matrix-matrix multiplication and convolution algorithms, which are the two dominant computation patterns in today's DNN models, to exploit our new dual-side sparse Tensor Core. Our evaluation shows that our design can fully unleash the dual-side DNN sparsity and improve the performance by up to one order of magnitude with \hl{small} hardware overhead.
(Sub)linear kernels for edge modification problems towards structured graph classes
Venue: arXiv cs.DS 2021
Year: 2021

In a (parameterized) graph edge modification problem, we are given a graph $G$, an integer $k$ and a (usually well-structured) class of graphs $\mathcal{G}$, and ask whether it is possible to transform $G$ into a graph $G' \in \mathcal{G}$ by adding and/or removing at most $k$ edges. Parameterized graph edge modification problems received considerable attention in the last decades. In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if this problem admits a $2k$ kernel [Cao, 2012], this kernel does not reduce the size of most instances. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graphs are very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size $O(k/\log k)$. We also obtain small kernels for several other edge modification problems. We prove that Split Addition (and the equivalent Split Deletion) admits a linear kernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al., 2015]. We complement this result by proving that Trivially Perfect Addition admits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under ETH.
BigCQ: A large-scale synthetic dataset of competency question patterns formalized into SPARQL-OWL query templates
Venue: arXiv cs.AI 2021
Year: 2021

Competency Questions (CQs) are used in many ontology engineering methodologies to collect requirements and track the completeness and correctness of an ontology being constructed. Although they are frequently suggested by ontology engineering methodologies, the publicly available datasets of CQs and their formalizations in ontology query languages are very scarce. Since first efforts to automate processes utilizing CQs are being made, it is of high importance to provide large and diverse datasets to fuel these solutions. In this paper, we present BigCQ, the biggest dataset of CQ templates with their formalizations into SPARQL-OWL query templates. BigCQ is created automatically from a dataset of frequently used axiom shapes. These pairs of CQ templates and query templates can be then materialized as actual CQs and SPARQL-OWL queries if filled with resource labels and IRIs from a given ontology. We describe the dataset in detail, provide a description of the process leading to the creation of the dataset and analyze how well the dataset covers real-world examples. We also publish the dataset as well as scripts transforming axiom shapes into pairs of CQ patterns and SPARQL-OWL templates, to make engineers able to adapt the process to their particular needs.
ThundeRiNG: Generating Multiple Independent Random Number Sequences on FPGAs
Venue: arXiv cs.DC 2021
Year: 2021

In this paper, we propose ThundeRiNG, a resource-efficient and high-throughput system for generating multiple independent sequences of random numbers (MISRN) on FPGAs. Generating MISRN can be a time-consuming step in many applications such as numeric computation and approximate computing. Despite that decades of studies on generating a single sequence of random numbers on FPGAs have achieved very high throughput and high quality of randomness, existing MISRN approaches either suffer from heavy resource consumption or fail to achieve statistical independence among sequences. In contrast, ThundeRiNG resolves the dependence by using a resource-efficient decorrelator among multiple sequences, guaranteeing a high statistical quality of randomness. Moreover, ThundeRiNG develops a novel state sharing among a massive number of pseudo-random number generator instances on FPGAs. The experimental results show that ThundeRiNG successfully passes the widely used statistical test, TestU01, only consumes a constant number of DSPs (less than 1\% of the FPGA resource capacity) for generating any number of sequences, and achieves a throughput of 655 billion random numbers per second. Compared to the state-of-the-art GPU library, ThundeRiNG demonstrates a $10.62\times$ speedup on MISRN and delivers up to $9.15\times$ performance and $26.63\times$ power efficiency improvement on two applications ($π$ estimation and Monte Carlo option pricing). This work is open-sourced on Github at https://github.com/Xtra-Computing/ThundeRiNG
See, Hear, Read: Leveraging Multimodality with Guided Attention for Abstractive Text Summarization
Venue: arXiv cs.LG 2021
Year: 2021

In recent years, abstractive text summarization with multimodal inputs has started drawing attention due to its ability to accumulate information from different source modalities and generate a fluent textual summary. However, existing methods use short videos as the visual modality and short summary as the ground-truth, therefore, perform poorly on lengthy videos and long ground-truth summary. Additionally, there exists no benchmark dataset to generalize this task on videos of varying lengths. In this paper, we introduce AVIATE, the first large-scale dataset for abstractive text summarization with videos of diverse duration, compiled from presentations in well-known academic conferences like NDSS, ICML, NeurIPS, etc. We use the abstract of corresponding research papers as the reference summaries, which ensure adequate quality and uniformity of the ground-truth. We then propose FLORAL, a factorized multi-modal Transformer based decoder-only language model, which inherently captures the intra-modal and inter-modal dynamics within various input modalities for the text summarization task. FLORAL utilizes an increasing number of self-attentions to capture multimodality and performs significantly better than traditional encoder-decoder based networks. Extensive experiments illustrate that FLORAL achieves significant improvement over the baselines in both qualitative and quantitative evaluations on the existing How2 dataset for short videos and newly introduced AVIATE dataset for videos with diverse duration, beating the best baseline on the two datasets by $1.39$ and $2.74$ ROUGE-L points respectively.
Characterization of Super-stable Matchings
Venue: arXiv cs.DM 2021
Year: 2021

An instance of the super-stable matching problem with incomplete lists and ties is an undirected bipartite graph $G = (A \cup B, E)$, with an adjacency list being a linearly ordered list of ties. Ties are subsets of vertices equally good for a given vertex. An edge $(x,y) \in E \backslash M$ is a blocking edge for a matching $M$ if by getting matched to each other neither of the vertices $x$ and $y$ would become worse off. Thus, there is no disadvantage if the two vertices would like to match up. A matching $M$ is super-stable if there is no blocking edge with respect to $M$. It has previously been shown that super-stable matchings form a distributive lattice and the number of super-stable matchings can be exponential in the number of vertices. We give two compact representations of size $O(m)$ that can be used to construct all super-stable matchings, where $m$ denotes the number of edges in the graph. The construction of the second representation takes $O(mn)$ time, where $n$ denotes the number of vertices in the graph, and gives an explicit rotation poset similar to the rotation poset in the classical stable marriage problem. We also give a polyhedral characterisation of the set of all super-stable matchings and prove that the super-stable matching polytope is integral, thus solving an open problem stated in the book by Gusfield and Irving .
Enabling News Consumers to View and Understand Biased News Coverage: A Study on the Perception and Visualization of Media Bias
Venue: arXiv cs.CY 2021
Year: 2021

Traditional media outlets are known to report political news in a biased way, potentially affecting the political beliefs of the audience and even altering their voting behaviors. Many researchers focus on automatically detecting and identifying media bias in the news, but only very few studies exist that systematically analyze how theses biases can be best visualized and communicated. We create three manually annotated datasets and test varying visualization strategies. The results show no strong effects of becoming aware of the bias of the treatment groups compared to the control group, although a visualization of hand-annotated bias communicated bias instances more effectively than a framing visualization. Showing participants an overview page, which opposes different viewpoints on the same topic, does not yield differences in respondents' bias perception. Using a multilevel model, we find that perceived journalist bias is significantly related to perceived political extremeness and impartiality of the article.
Towards Detecting Need for Empathetic Response in Motivational Interviewing
Venue: arXiv cs.CL 2021
Year: 2021

Empathetic response from the therapist is key to the success of clinical psychotherapy, especially motivational interviewing. Previous work on computational modelling of empathy in motivational interviewing has focused on offline, session-level assessment of therapist empathy, where empathy captures all efforts that the therapist makes to understand the client's perspective and convey that understanding to the client. In this position paper, we propose a novel task of turn-level detection of client need for empathy. Concretely, we propose to leverage pre-trained language models and empathy-related general conversation corpora in a unique labeller-detector framework, where the labeller automatically annotates a motivational interviewing conversation corpus with empathy labels to train the detector that determines the need for therapist empathy. We also lay out our strategies of extending the detector with additional-input and multi-task setups to improve its detection and explainability.
Educational Robotics in Online Distance Learning: An Experience from Primary School
Venue: arXiv cs.CY 2021
Year: 2021

Temporary school closures caused by the Covid-19 pandemic have posed new challenges for many teachers and students worldwide. Especially the abrupt shift to online distance learning posed many obstacles to be overcome and it particularly complicated the implementation of Educational Robotics activities. Such activities usually comprise a variety of different learning artifacts, which were not accessible to many students during the period of school closure. Moreover, online distance learning considerably limits the possibilities for students to interact with their peers and teachers. In an attempt to address these issues, this work presents the development of an Educational Robotics activity particularly conceived for online distance learning in primary school. The devised activities are based on pen and paper approaches that are complemented by commonly used social media to facilitate communication and collaboration. They were proposed to 13 students, as a way to continue ER activities in online distance learning over the time period of four weeks.
Personalized Counterfactual Fairness in Recommendation
Venue: arXiv cs.IR 2021
Year: 2021

Recommender systems are gaining increasing and critical impacts on human and society since a growing number of users use them for information seeking and decision making. Therefore, it is crucial to address the potential unfairness problems in recommendations. Just like users have personalized preferences on items, users' demands for fairness are also personalized in many scenarios. Therefore, it is important to provide personalized fair recommendations for users to satisfy their personalized fairness demands. Besides, previous works on fair recommendation mainly focus on association-based fairness. However, it is important to advance from associative fairness notions to causal fairness notions for assessing fairness more properly in recommender systems. Based on the above considerations, this paper focuses on achieving personalized counterfactual fairness for users in recommender systems. To this end, we introduce a framework for achieving counterfactually fair recommendations through adversary learning by generating feature-independent user embeddings for recommendation. The framework allows recommender systems to achieve personalized fairness for users while also covering non-personalized situations. Experiments on two real-world datasets with shallow and deep recommendation algorithms show that our method can generate fairer recommendations for users with a desirable recommendation performance.
Flexible Compositional Learning of Structured Visual Concepts
Venue: arXiv cs.CV 2021
Year: 2021

Humans are highly efficient learners, with the ability to grasp the meaning of a new concept from just a few examples. Unlike popular computer vision systems, humans can flexibly leverage the compositional structure of the visual world, understanding new concepts as combinations of existing concepts. In the current paper, we study how people learn different types of visual compositions, using abstract visual forms with rich relational structure. We find that people can make meaningful compositional generalizations from just a few examples in a variety of scenarios, and we develop a Bayesian program induction model that provides a close fit to the behavioral data. Unlike past work examining special cases of compositionality, our work shows how a single computational approach can account for many distinct types of compositional generalization.
Classification of Urban Morphology with Deep Learning: Application on Urban Vitality
Venue: arXiv cs.CV 2021
Year: 2021

There is a prevailing trend to study urban morphology quantitatively thanks to the growing accessibility to various forms of spatial big data, increasing computing power, and use cases benefiting from such information. The methods developed up to now measure urban morphology with numerical indices describing density, proportion, and mixture, but they do not directly represent morphological features from the human's visual and intuitive perspective. We take the first step to bridge the gap by proposing a deep learning-based technique to automatically classify road networks into four classes on a visual basis. The method is implemented by generating an image of the street network (Colored Road Hierarchy Diagram), which we introduce in this paper, and classifying it using a deep convolutional neural network (ResNet-34). The model achieves an overall classification accuracy of 0.875. Nine cities around the world are selected as the study areas with their road networks acquired from OpenStreetMap. Latent subgroups among the cities are uncovered through clustering on the percentage of each road network category. In the subsequent part of the paper, we focus on the usability of such classification: we apply our method in a case study of urban vitality prediction. An advanced tree-based regression model (LightGBM) is for the first time designated to establish the relationship between morphological indices and vitality indicators. The effect of road network classification is found to be small but positively associated with urban vitality. This work expands the toolkit of quantitative urban morphology study with new techniques, supporting further studies in the future.
Computing the Fréchet Distance Between Uncertain Curves in One Dimension
Venue: arXiv cs.CG 2021
Year: 2021

We consider the problem of computing the Fréchet distance between two curves for which the exact locations of the vertices are unknown. Each vertex may be placed in a given uncertainty region for that vertex, and the objective is to place vertices so as to minimise the Fréchet distance. This problem was recently shown to be NP-hard in 2D, and it is unclear how to compute an optimal vertex placement at all. We present the first general algorithmic framework for this problem. We prove that it results in a polynomial-time algorithm for curves in 1D with intervals as uncertainty regions. In contrast, we show that the problem is NP-hard in 1D in the case that vertices are placed to maximise the Fréchet distance. We also study the weak Fréchet distance between uncertain curves. While finding the optimal placement of vertices seems more difficult than the regular Fréchet distance -- and indeed we can easily prove that the problem is NP-hard in 2D -- the optimal placement of vertices in 1D can be computed in polynomial time. Finally, we investigate the discrete weak Fréchet distance, for which, somewhat surprisingly, the problem is NP-hard already in 1D.
Wide & Deep neural network model for patch aggregation in CNN-based prostate cancer detection systems
Venue: arXiv cs.LG 2021
Year: 2021

Prostate cancer (PCa) is one of the most commonly diagnosed cancer and one of the leading causes of death among men, with almost 1.41 million new cases and around 375,000 deaths in 2020. Artificial Intelligence algorithms have had a huge impact in medical image analysis, including digital histopathology, where Convolutional Neural Networks (CNNs) are used to provide a fast and accurate diagnosis, supporting experts in this task. To perform an automatic diagnosis, prostate tissue samples are first digitized into gigapixel-resolution whole-slide images. Due to the size of these images, neural networks cannot use them as input and, therefore, small subimages called patches are extracted and predicted, obtaining a patch-level classification. In this work, a novel patch aggregation method based on a custom Wide & Deep neural network model is presented, which performs a slide-level classification using the patch-level classes obtained from a CNN. The malignant tissue ratio, a 10-bin malignant probability histogram, the least squares regression line of the histogram, and the number of malignant connected components are used by the proposed model to perform the classification. An accuracy of 94.24% and a sensitivity of 98.87% were achieved, proving that the proposed system could aid pathologists by speeding up the screening process and, thus, contribute to the fight against PCa.