OpenRaiser/Intern-Atlas huggingface dataset:
The use of AR elements in the study of foreign languages at the university
Venue: arXiv cs.CY 2022
Year: 2022

The article deals with the analysis of the impact of the using AR technology in the study of a foreign language by university students. It is stated out that AR technology can be a good tool for learning a foreign language. The use of elements of AR in the course of studying a foreign language, in particular in the form of virtual excursions, is proposed. Advantages of using AR technology in the study of the German language are identified, namely: the possibility of involvement of different channels of information perception, the integrity of the representation of the studied object, the faster and better memorization of new vocabulary, the development of communicative foreign language skills. The ease and accessibility of using QR codes to obtain information about the object of study from open Internet sources is shown. The results of a survey of students after virtual tours are presented. A reorientation of methodological support for the study of a foreign language at universities is proposed. Attention is drawn to the use of AR elements in order to support students with different learning styles (audio, visual, kinesthetic).
Space4HGNN: A Novel, Modularized and Reproducible Platform to Evaluate Heterogeneous Graph Neural Network
Venue: arXiv cs.LG 2022
Year: 2022

Heterogeneous Graph Neural Network (HGNN) has been successfully employed in various tasks, but we cannot accurately know the importance of different design dimensions of HGNNs due to diverse architectures and applied scenarios. Besides, in the research community of HGNNs, implementing and evaluating various tasks still need much human effort. To mitigate these issues, we first propose a unified framework covering most HGNNs, consisting of three components: heterogeneous linear transformation, heterogeneous graph transformation, and heterogeneous message passing layer. Then we build a platform Space4HGNN by defining a design space for HGNNs based on the unified framework, which offers modularized components, reproducible implementations, and standardized evaluation for HGNNs. Finally, we conduct experiments to analyze the effect of different designs. With the insights found, we distill a condensed design space and verify its effectiveness.
Improving AoI via Learning-based Distributed MAC in Wireless Networks
Venue: arXiv cs.NI 2022
Year: 2022

In this work, we consider a remote monitoring scenario in which multiple sensors share a wireless channel to deliver their status updates to a process monitor via an access point (AP). Moreover, we consider that the sensors randomly arrive and depart from the network as they become active and inactive. The goal of the sensors is to devise a medium access strategy to collectively minimize the long-term mean network \ac{AoI} of their respective processes at the remote monitor. For this purpose, we propose specific modifications to ALOHA-QT algorithm, a distributed medium access algorithm that employs a policy tree (PT) and reinforcement learning (RL) to achieve high throughput. We provide the upper bound on the mean network Age of Information (AoI) for the proposed algorithm along with pointers for selecting its key parameter. The results reveal that the proposed algorithm reduces mean network \ac{AoI} by more than 50 percent for state of the art stationary randomized policies while successfully adjusting to a changing number of active users in the network. The algorithm needs less memory and computation than ALOHA-QT while performing better in terms of AoI.
Faster change of order algorithm for Gröbner bases under shape and stability assumptions
Venue: arXiv cs.SC 2022
Year: 2022

Solving zero-dimensional polynomial systems using Gröbner bases is usually done by, first, computing a Gröbner basis for the degree reverse lexicographic order, and next computing the lexicographic Gröbner basis with a change of order algorithm. Currently, the change of order now takes a significant part of the whole solving time for many generic instances. Like the fastest known change of order algorithms, this work focuses on the situation where the ideal defined by the system satisfies natural properties which can be recovered in generic coordinates. First, the ideal has a \emph{shape} lexicographic Gröbner basis. Second, the set of leading terms with respect to the degree reverse lexicographic order has a \emph{stability} property; in particular, the multiplication matrix can be read on the input Gröbner basis. The current fastest algorithms rely on the sparsity of this matrix. Actually, this sparsity is a consequence of an algebraic structure, which can be exploited to represent the matrix concisely as a univariate polynomial matrix. We show that the Hermite normal form of that matrix yields the sought lexicographic Gröbner basis, under assumptions which cover the shape position case. Under some mild assumption implying $n \le t$, the arithmetic complexity of our algorithm is $O\tilde{~}(t^{ω-1}D)$, where $n$ is the number of variables, $t$ is a sparsity indicator of the aforementioned matrix, $D$ is the degree of the zero-dimensional ideal under consideration, and $ω$ is the exponent of matrix multiplication. This improves upon both state-of-the-art complexity bounds $O\tilde{~}(tD^2)$ and $O\tilde{~}(D^ω)$, since $ω< 3$ and $t\le D$. Practical experiments, based on the libraries msolve and PML, confirm the high practical benefit.
United Monoids: Finding Simplicial Sets and Labelled Algebraic Graphs in Trees
Venue: arXiv cs.PL 2022
Year: 2022

Graphs and various graph-like combinatorial structures, such as preorders and hypergraphs, are ubiquitous in programming. This paper focuses on representing graphs in a purely functional programming language like Haskell. There are several existing approaches; one of the most recently developed ones is the "algebraic graphs" approach (2017). It uses an algebraic data type to represent graphs and has attracted users, including from industry, due to its emphasis on equational reasoning and making a common class of bugs impossible by eliminating internal invariants. The previous formulation of algebraic graphs did not support edge labels, which was a serious practical limitation. In this paper, we redesign the main algebraic data type and remove this limitation. We follow a fairly standard approach of parameterising a data structure with a semiring of edge labels. The new formulation is both more general and simpler: the two operations for composing graphs used in the previous work can now be obtained from a single operation by fixing the semiring parameter to zero and one, respectively. By instantiating the new data type with different semirings, and working out laws for interpreting the resulting expression trees, we discover an unusual algebraic structure, which we call "united monoids", that is, a pair of monoids whose unit elements coincide. We believe that it is worth studying united monoids in their full generality, going beyond the graphs which prompted their discovery. To that end, we characterise united monoids with a minimal set of axioms, prove a few basic theorems, and discuss several notable examples. We validate the presented approach by implementing it in the open-source *algebraic-graphs* library. Our theoretical contributions are supported by proofs that are included in the paper and have also been machine-checked in Agda. By extending algebraic graphs with support for edge labels, we make them suitable for a much larger class of possible applications. By studying united monoids, we provide a theoretical foundation for further research in this area.
On the Secrecy Gain of Formally Unimodular Construction $\text{A}_4$ Lattices
Venue: arXiv cs.IT 2022
Year: 2022

Lattice coding for the Gaussian wiretap channel is considered, where the goal is to ensure reliable communication between two authorized parties while preventing an eavesdropper from learning the transmitted messages. Recently, a measure called secrecy gain was proposed as a design criterion to quantify the secrecy-goodness of the applied lattice code. In this paper, the theta series of the so-called formally unimodular lattices obtained by Construction $\text{A}_4$ from codes over $\mathbb{Z}_4$ is derived, and we provide a universal approach to determine their secrecy gains. Initial results indicate that Construction $\text{A}_4$ lattices can achieve a higher secrecy gain than the best-known formally unimodular lattices from the literature. Furthermore, a new code construction of formally self-dual $\mathbb{Z}_4$-linear codes is presented.
Enhanced Behavioral Cloning with Environmental Losses for Self-Driving Vehicles
Venue: arXiv cs.RO 2022
Year: 2022

Learned path planners have attracted research interest due to their ability to model human driving behavior and rapid inference. Recent works on behavioral cloning show that simple imitation of expert observations is not sufficient to handle complex driving scenarios. Besides, predictions that land outside drivable areas can lead to potentially dangerous situations. This paper proposes a set of loss functions, namely Social loss and Road loss, which account for modelling risky social interactions in path planning. These losses act as a repulsive scalar field that surrounds non-drivable areas. Predictions that land near these regions incur in a higher training cost, which is minimized using backpropagation. This methodology provides additional environment feedback to the traditional supervised learning set up. We validated this approach on a large-scale urban driving dataset. The results show the agent learns to imitate human driving while exhibiting better safety metrics. Furthermore, the proposed methodology has positive effects on inference without the need to artificially generate unsafe driving examples. The explanability study suggests that the benefits obtained are associated with a higher relevance of non-drivable areas in the agent's decisions compared to classical behavioral cloning.
Rethinking Pareto Frontier for Performance Evaluation of Deep Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Performance optimization of deep learning models is conducted either manually or through automatic architecture search, or a combination of both. On the other hand, their performance strongly depends on the target hardware and how successfully the models were trained. We propose to use a multi-dimensional Pareto frontier to re-define the efficiency measure of candidate deep learning models, where several variables such as training cost, inference latency, and accuracy play a relative role in defining a dominant model. Furthermore, a random version of the multi-dimensional Pareto frontier is introduced to mitigate the uncertainty of accuracy, latency, and throughput of deep learning models in different experimental setups. These two complementary methods can be combined to perform objective benchmarking of deep learning models. Our proposed method is applied to a wide range of deep image classification models trained on ImageNet data. Our method combines competing variables with stochastic nature in a single relative efficiency measure. This allows ranking deep learning models that run efficiently on different hardware, and combining inference efficiency with training efficiency objectively.
Illuminating the Space of Dungeon Maps, Locked-door Missions and Enemy Placement Through MAP-Elites
Venue: arXiv cs.AI 2022
Year: 2022

Procedural Content Generation (PCG) methods are valuable tools to speed up the game development process. Moreover, PCG may also present in games as features, such as the procedural dungeon generation (PDG) in Moonlighter (Digital Sun, 2018). This paper introduces an extended version of an evolutionary dungeon generator by incorporating a MAP-Elites population. Our dungeon levels are discretized with rooms that may have locked-door missions and enemies within them. We encoded the dungeons through a tree structure to ensure the feasibility of missions. We performed computational and user feedback experiments to evaluate our PDG approach. They show that our approach accurately converges almost the whole MAP-Elite population for most executions. Finally, players' feedback indicates that they enjoyed the generated levels, and they could not indicate an algorithm as a level generator.
Masked prediction tasks: a parameter identifiability view
Venue: arXiv cs.LG 2022
Year: 2022

The vast majority of work in self-supervised learning, both theoretical and empirical (though mostly the latter), have largely focused on recovering good features for downstream tasks, with the definition of "good" often being intricately tied to the downstream task itself. This lens is undoubtedly very interesting, but suffers from the problem that there isn't a "canonical" set of downstream tasks to focus on -- in practice, this problem is usually resolved by competing on the benchmark dataset du jour. In this paper, we present an alternative lens: one of parameter identifiability. More precisely, we consider data coming from a parametric probabilistic model, and train a self-supervised learning predictor with a suitably chosen parametric form. Then, we ask whether we can read off the ground truth parameters of the probabilistic model from the optimal predictor. We focus on the widely used self-supervised learning method of predicting masked tokens, which is popular for both natural languages and visual data. While incarnations of this approach have already been successfully used for simpler probabilistic models (e.g. learning fully-observed undirected graphical models), we focus instead on latent-variable models capturing sequential structures -- namely Hidden Markov Models with both discrete and conditionally Gaussian observations. We show that there is a rich landscape of possibilities, out of which some prediction tasks yield identifiability, while others do not. Our results, borne of a theoretical grounding of self-supervised learning, could thus potentially beneficially inform practice. Moreover, we uncover close connections with uniqueness of tensor rank decompositions -- a widely used tool in studying identifiability through the lens of the method of moments.
Signal Decomposition Using Masked Proximal Operators
Venue: arXiv cs.LG 2022
Year: 2022

We consider the well-studied problem of decomposing a vector time series signal into components with different characteristics, such as smooth, periodic, nonnegative, or sparse. We describe a simple and general framework in which the components are defined by loss functions (which include constraints), and the signal decomposition is carried out by minimizing the sum of losses of the components (subject to the constraints). When each loss function is the negative log-likelihood of a density for the signal component, this framework coincides with maximum a posteriori probability (MAP) estimation; but it also includes many other interesting cases. Summarizing and clarifying prior results, we give two distributed optimization methods for computing the decomposition, which find the optimal decomposition when the component class loss functions are convex, and are good heuristics when they are not. Both methods require only the masked proximal operator of each of the component loss functions, a generalization of the well-known proximal operator that handles missing entries in its argument. Both methods are distributed, i.e., handle each component separately. We derive tractable methods for evaluating the masked proximal operators of some loss functions that, to our knowledge, have not appeared in the literature.
Towards the Combination of Model Checking and Runtime Verification on Multi-Agent Systems
Venue: arXiv cs.LO 2022
Year: 2022

Multi-Agent Systems (MAS) are notoriously complex and hard to verify. In fact, it is not trivial to model a MAS, and even when a model is built, it is not always possible to verify, in a formal way, that it is actually behaving as we expect. Usually, it is relevant to know whether an agent is capable of fulfilling its own goals. One possible way to check this is through Model Checking. Specifically, by verifying Alternating-time Temporal Logic (ATL) properties, where the notion of strategies for achieving goals can be described. Unfortunately, the resulting model checking problem is not decidable in general. In this paper, we present a verification procedure based on combining Model Checking and Runtime Verification, where sub-models of the MAS model belonging to decidable fragments are verified by a model checker, and runtime monitors are used to verify the rest. Furthermore, we implement our technique and show experimental results.
Counterfactual Analysis of the Impact of the IMF Program on Child Poverty in the Global-South Region using Causal-Graphical Normalizing Flows
Venue: arXiv cs.AI 2022
Year: 2022

This work demonstrates the application of a particular branch of causal inference and deep learning models: \emph{causal-Graphical Normalizing Flows (c-GNFs)}. In a recent contribution, scholars showed that normalizing flows carry certain properties, making them particularly suitable for causal and counterfactual analysis. However, c-GNFs have only been tested in a simulated data setting and no contribution to date have evaluated the application of c-GNFs on large-scale real-world data. Focusing on the \emph{AI for social good}, our study provides a counterfactual analysis of the impact of the International Monetary Fund (IMF) program on child poverty using c-GNFs. The analysis relies on a large-scale real-world observational data: 1,941,734 children under the age of 18, cared for by 567,344 families residing in the 67 countries from the Global-South. While the primary objective of the IMF is to support governments in achieving economic stability, our results find that an IMF program reduces child poverty as a positive side-effect by about 1.2$\pm$0.24 degree (`0' equals no poverty and `7' is maximum poverty). Thus, our article shows how c-GNFs further the use of deep learning and causal inference in AI for social good. It shows how learning algorithms can be used for addressing the untapped potential for a significant social impact through counterfactual inference at population level (ACE), sub-population level (CACE), and individual level (ICE). In contrast to most works that model ACE or CACE but not ICE, c-GNFs enable personalization using \emph{`The First Law of Causal Inference'}.
Graph Reparameterizations for Enabling 1000+ Monte Carlo Iterations in Bayesian Deep Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

Uncertainty estimation in deep models is essential in many real-world applications and has benefited from developments over the last several years. Recent evidence suggests that existing solutions dependent on simple Gaussian formulations may not be sufficient. However, moving to other distributions necessitates Monte Carlo (MC) sampling to estimate quantities such as the KL divergence: it could be expensive and scales poorly as the dimensions of both the input data and the model grow. This is directly related to the structure of the computation graph, which can grow linearly as a function of the number of MC samples needed. Here, we construct a framework to describe these computation graphs, and identify probability families where the graph size can be independent or only weakly dependent on the number of MC samples. These families correspond directly to large classes of distributions. Empirically, we can run a much larger number of iterations for MC approximations for larger architectures used in computer vision with gains in performance measured in confident accuracy, stability of training, memory and training time.
A Probabilistic Programming Idiom for Active Knowledge Search
Venue: arXiv cs.RO 2022
Year: 2022

In this paper, we derive and implement a probabilistic programming idiom for the problem of acquiring new knowledge about an environment. The idiom is implemented utilizing a modern probabilistic programming language. We demonstrate the utility of this idiom by implementing an algorithm for the specific problem of active mapping and robot exploration. Finally, we evaluate the functionality of the implementation through an extensive simulation study utilizing the HouseExpo dataset.
STAR-RIS-NOMA Networks: An Error Performance Perspective
Venue: arXiv cs.IT 2022
Year: 2022

This letter investigates the bit error rate (BER) performance of simultaneous transmitting and reflecting reconfigurable intelligent surfaces (STAR-RISs) in non-orthogonal multiple access (NOMA) networks. In the investigated network, a STAR-RIS serves multiple non-orthogonal users located on either side of the surface by utilizing the mode switching protocol. We derive the closed-form BER expressions in perfect and imperfect successive interference cancellation cases. Furthermore, asymptotic analyses are also conducted to provide further insights into the BER behavior in the high signal-to-noise ratio region. Finally, the accuracy of our theoretical analysis is validated through Monte Carlo simulations. The obtained results reveal that the BER performance of STAR-RIS-NOMA outperforms that of the classical NOMA system, and STAR-RIS might be a promising NOMA 2.0 solution.
Device Identification in Blockchain-Based Internet of Things
Venue: arXiv cs.CR 2022
Year: 2022

In recent years blockchain technology has received tremendous attention. Blockchain users are known by a changeable Public Key (PK) that introduces a level of anonymity, however, studies have shown that anonymized transactions can be linked to deanonymize the users. Most of the existing studies on user de-anonymization focus on monetary applications, however, blockchain has received extensive attention in non-monetary applications like IoT. In this paper we study the impact of de-anonymization on IoT-based blockchain. We populate a blockchain with data of smart home devices and then apply machine learning algorithms in an attempt to classify transactions to a particular device that in turn risks the privacy of the users. Two types of attack models are defined: (i) informed attacks: where attackers know the type of devices installed in a smart home, and (ii) blind attacks: where attackers do not have this information. We show that machine learning algorithms can successfully classify the transactions with 90% accuracy. To enhance the anonymity of the users, we introduce multiple obfuscation methods which include combining multiple packets into a transaction, merging ledgers of multiple devices, and delaying transactions. The implementation results show that these obfuscation methods significantly reduce the attack success rates to 20% to 30% and thus enhance user privacy.
MixKG: Mixing for harder negative samples in knowledge graph
Venue: arXiv cs.AI 2022
Year: 2022

Knowledge graph embedding~(KGE) aims to represent entities and relations into low-dimensional vectors for many real-world applications. The representations of entities and relations are learned via contrasting the positive and negative triplets. Thus, high-quality negative samples are extremely important in KGE. However, the present KGE models either rely on simple negative sampling methods, which makes it difficult to obtain informative negative triplets; or employ complex adversarial methods, which requires more training data and strategies. In addition, these methods can only construct negative triplets using the existing entities, which limits the potential to explore harder negative triplets. To address these issues, we adopt mixing operation in generating harder negative samples for knowledge graphs and introduce an inexpensive but effective method called MixKG. Technically, MixKG first proposes two kinds of criteria to filter hard negative triplets among the sampled negatives: based on scoring function and based on correct entity similarity. Then, MixKG synthesizes harder negative samples via the convex combinations of the paired selected hard negatives. Experiments on two public datasets and four classical KGE methods show MixKG is superior to previous negative sampling algorithms.