OpenRaiser/Intern-Atlas huggingface dataset:
High dimensional expansion implies amplified local testability
Venue: arXiv cs.IT 2021
Year: 2021

In this work we show that high dimensional expansion implies locally testable code. Specifically, we define a notion that we call high-dimensional-expanding-system (HDE-system). This is a set system defined by incidence relations with certain high dimensional expansion relations between its sets. We say that a linear code is modelled over HDE-system, if the collection of linear constraints that the code satisfies could by described via the HDE-system. We show that a code that can be modelled over HDE-system is locally testable. This implies that high dimensional expansion phenomenon solely implies local testability of codes. Prior work had to rely to local notions of local testability to get some global forms of testability (e.g. co-systolic expansion from local one, global agreement from local one), while our work infers global testability directly from high dimensional expansion without relying on some local form of testability. The local testability result that we obtain from HDE-systems is, in fact, stronger than standard one, and we term it amplified local testability. We further show that most of the well studied locally testable codes as Reed-Muller codes and more generally affine invariant codes with single-orbit property fall into our framework. Namely, it is possible to show that they are modelled over an HDE-system, and hence the family of all p-ary affine invariant codes is amplified locally testable. This yields the strongest known testing results for affine invariant codes with single orbit, strengthening the work of Kaufman and Sudan.
Abstract Reasoning via Logic-guided Generation
Venue: arXiv cs.LG 2021
Year: 2021

Abstract reasoning, i.e., inferring complicated patterns from given observations, is a central building block of artificial general intelligence. While humans find the answer by either eliminating wrong candidates or first constructing the answer, prior deep neural network (DNN)-based methods focus on the former discriminative approach. This paper aims to design a framework for the latter approach and bridge the gap between artificial and human intelligence. To this end, we propose logic-guided generation (LoGe), a novel generative DNN framework that reduces abstract reasoning as an optimization problem in propositional logic. LoGe is composed of three steps: extract propositional variables from images, reason the answer variables with a logic layer, and reconstruct the answer image from the variables. We demonstrate that LoGe outperforms the black box DNN frameworks for generative abstract reasoning under the RAVEN benchmark, i.e., reconstructing answers based on capturing correct rules of various attributes from observations.
The Stationary Prophet Inequality Problem
Venue: arXiv cs.DS 2021
Year: 2021

We study a continuous and infinite time horizon counterpart to the classic prophet inequality, which we term the stationary prophet inequality problem. Here, copies of a good arrive and perish according to Poisson point processes. Buyers arrive similarly and make take-it-or-leave-it offers for unsold items. The objective is to maximize the (infinite) time average revenue of the seller. Our main results are pricing-based policies which (i) achieve a $1/2$-approximation of the optimal offline policy, which is best possible, and (ii) achieve a better than $(1-1/e)$-approximation of the optimal online policy. Result (i) improves upon bounds implied by recent work of Collina et al. (WINE'20), and is the first optimal prophet inequality for a stationary problem. Result (ii) improves upon a $1-1/e$ bound implied by recent work of Aouad and Saritaç (EC'20), and shows that this prevalent bound in online algorithms is not optimal for this problem.
Target-Oriented Fine-tuning for Zero-Resource Named Entity Recognition
Venue: arXiv cs.CL 2021
Year: 2021

Zero-resource named entity recognition (NER) severely suffers from data scarcity in a specific domain or language. Most studies on zero-resource NER transfer knowledge from various data by fine-tuning on different auxiliary tasks. However, how to properly select training data and fine-tuning tasks is still an open problem. In this paper, we tackle the problem by transferring knowledge from three aspects, i.e., domain, language and task, and strengthening connections among them. Specifically, we propose four practical guidelines to guide knowledge transfer and task fine-tuning. Based on these guidelines, we design a target-oriented fine-tuning (TOF) framework to exploit various data from three aspects in a unified training manner. Experimental results on six benchmarks show that our method yields consistent improvements over baselines in both cross-domain and cross-lingual scenarios. Particularly, we achieve new state-of-the-art performance on five benchmarks.
An Empirical Study on Code Comment Completion
Venue: arXiv cs.SE 2021
Year: 2021

Code comments play a prominent role in program comprehension activities. However, source code is not always documented and code and comments not always co-evolve. To deal with these issues, researchers have proposed techniques to automatically generate comments documenting a given code at hand. The most recent works in the area applied deep learning (DL) techniques to support such a task. Despite the achieved advances, the empirical evaluations of these approaches show that they are still far from a performance level that would make them valuable for developers. We tackle a simpler and related problem: Code comment completion. Instead of generating a comment for a given code from scratch, we investigate the extent to which state-of-the-art techniques can help developers in writing comments faster. We present a large-scale study in which we empirically assess how a simple n-gram model and the recently proposed Text-To-Text Transfer Transformer (T5) architecture can perform in autocompleting a code comment the developer is typing. The achieved results show the superiority of the T5 model, despite the n-gram model being a competitive solution.
Codeathon Activity: A Design Prototype for Real World Problems
Venue: arXiv cs.CY 2021
Year: 2021

Activity-based learning helps students to learn through participation. A virtual codeathon activity, as part of this learning scheme, was conducted for 180 undergraduate students to focus on analysis and design of solutions to crucial real-world problems in the existing Covid-19 pandemic situation. In this paper, an analysis is made to know the problem solving skills of students given a single problem statement. Evaluators can further collate these multiple solutions into one optimal solution. This Codeathon activity impacts their practical approach towards the analysis and design.
Towards Explaining Adversarial Examples Phenomenon in Artificial Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we study the adversarial examples existence and adversarial training from the standpoint of convergence and provide evidence that pointwise convergence in ANNs can explain these observations. The main contribution of our proposal is that it relates the objective of the evasion attacks and adversarial training with concepts already defined in learning theory. Also, we extend and unify some of the other proposals in the literature and provide alternative explanations on the observations made in those proposals. Through different experiments, we demonstrate that the framework is valuable in the study of the phenomenon and is applicable to real-world problems.
Evaluation of contextual embeddings on less-resourced languages
Venue: arXiv cs.CL 2021
Year: 2021

The current dominance of deep neural networks in natural language processing is based on contextual embeddings such as ELMo, BERT, and BERT derivatives. Most existing work focuses on English; in contrast, we present here the first multilingual empirical comparison of two ELMo and several monolingual and multilingual BERT models using 14 tasks in nine languages. In monolingual settings, our analysis shows that monolingual BERT models generally dominate, with a few exceptions such as the dependency parsing task, where they are not competitive with ELMo models trained on large corpora. In cross-lingual settings, BERT models trained on only a few languages mostly do best, closely followed by massively multilingual BERT models.
Rule-Based Classification of Hyperspectral Imaging Data
Venue: arXiv cs.CV 2021
Year: 2021

Due to its high spatial and spectral information content, hyperspectral imaging opens up new possibilities for a better understanding of data and scenes in a wide variety of applications. An essential part of this process of understanding is the classification part. In this article we present a general classification approach based on the shape of spectral signatures. In contrast to classical classification approaches (e.g. SVM, KNN), not only reflectance values are considered, but also parameters such as curvature points, curvature values, and the curvature behavior of spectral signatures are used to develop shape-describing rules in order to use them for classification by a rule-based procedure using IF-THEN queries. The flexibility and efficiency of the methodology is demonstrated using datasets from two different application fields and leads to convincing results with good performance.
Hash-Based Tree Similarity and Simplification in Genetic Programming for Symbolic Regression
Venue: arXiv cs.LG 2021
Year: 2021

We introduce in this paper a runtime-efficient tree hashing algorithm for the identification of isomorphic subtrees, with two important applications in genetic programming for symbolic regression: fast, online calculation of population diversity and algebraic simplification of symbolic expression trees. Based on this hashing approach, we propose a simple diversity-preservation mechanism with promising results on a collection of symbolic regression benchmark problems.
TagRec: Automated Tagging of Questions with Hierarchical Learning Taxonomy
Venue: arXiv cs.CL 2021
Year: 2021

Online educational platforms organize academic questions based on a hierarchical learning taxonomy (subject-chapter-topic). Automatically tagging new questions with existing taxonomy will help organize these questions into different classes of hierarchical taxonomy so that they can be searched based on the facets like chapter. This task can be formulated as a flat multi-class classification problem. Usually, flat classification based methods ignore the semantic relatedness between the terms in the hierarchical taxonomy and the questions. Some traditional methods also suffer from the class imbalance issues as they consider only the leaf nodes ignoring the hierarchy. Hence, we formulate the problem as a similarity-based retrieval task where we optimize the semantic relatedness between the taxonomy and the questions. We demonstrate that our method helps to handle the unseen labels and hence can be used for taxonomy tagging in the wild. In this method, we augment the question with its corresponding answer to capture more semantic information and then align the question-answer pair's contextualized embedding with the corresponding label (taxonomy) vector representations. The representations are aligned by fine-tuning a transformer based model with a loss function that is a combination of the cosine similarity and hinge rank loss. The loss function maximizes the similarity between the question-answer pair and the correct label representations and minimizes the similarity to unrelated labels. Finally, we perform experiments on two real-world datasets. We show that the proposed learning method outperforms representations learned using the multi-class classification method and other state of the art methods by 6% as measured by Recall@k. We also demonstrate the performance of the proposed method on unseen but related learning content like the learning objectives without re-training the network.
Semiparametric Latent Topic Modeling on Consumer-Generated Corpora
Venue: arXiv cs.CL 2021
Year: 2021

Legacy procedures for topic modelling have generally suffered problems of overfitting and a weakness towards reconstructing sparse topic structures. With motivation from a consumer-generated corpora, this paper proposes semiparametric topic model, a two-step approach utilizing nonnegative matrix factorization and semiparametric regression in topic modeling. The model enables the reconstruction of sparse topic structures in the corpus and provides a generative model for predicting topics in new documents entering the corpus. Assuming the presence of auxiliary information related to the topics, this approach exhibits better performance in discovering underlying topic structures in cases where the corpora are small and limited in vocabulary. In an actual consumer feedback corpus, the model also demonstrably provides interpretable and useful topic definitions comparable with those produced by other methods.
Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
Venue: arXiv cs.DS 2021
Year: 2021

Low-rank tensor decomposition generalizes low-rank matrix approximation and is a powerful technique for discovering low-dimensional structure in high-dimensional data. In this paper, we study Tucker decompositions and use tools from randomized numerical linear algebra called ridge leverage scores to accelerate the core tensor update step in the widely-used alternating least squares (ALS) algorithm. Updating the core tensor, a severe bottleneck in ALS, is a highly-structured ridge regression problem where the design matrix is a Kronecker product of the factor matrices. We show how to use approximate ridge leverage scores to construct a sketched instance for any ridge regression problem such that the solution vector for the sketched problem is a $(1+\varepsilon)$-approximation to the original instance. Moreover, we show that classical leverage scores suffice as an approximation, which then allows us to exploit the Kronecker structure and update the core tensor in time that depends predominantly on the rank and the sketching parameters (i.e., sublinear in the size of the input tensor). We also give upper bounds for ridge leverage scores as rows are removed from the design matrix (e.g., if the tensor has missing entries), and we demonstrate the effectiveness of our approximate ridge regressioni algorithm for large, low-rank Tucker decompositions on both synthetic and real-world data.
AnonySIGN: Novel Human Appearance Synthesis for Sign Language Video Anonymisation
Venue: arXiv cs.CV 2021
Year: 2021

The visual anonymisation of sign language data is an essential task to address privacy concerns raised by large-scale dataset collection. Previous anonymisation techniques have either significantly affected sign comprehension or required manual, labour-intensive work. In this paper, we formally introduce the task of Sign Language Video Anonymisation (SLVA) as an automatic method to anonymise the visual appearance of a sign language video whilst retaining the meaning of the original sign language sequence. To tackle SLVA, we propose AnonySign, a novel automatic approach for visual anonymisation of sign language data. We first extract pose information from the source video to remove the original signer appearance. We next generate a photo-realistic sign language video of a novel appearance from the pose sequence, using image-to-image translation methods in a conditional variational autoencoder framework. An approximate posterior style distribution is learnt, which can be sampled from to synthesise novel human appearances. In addition, we propose a novel \textit{style loss} that ensures style consistency in the anonymised sign language videos. We evaluate AnonySign for the SLVA task with extensive quantitative and qualitative experiments highlighting both realism and anonymity of our novel human appearance synthesis. In addition, we formalise an anonymity perceptual study as an evaluation criteria for the SLVA task and showcase that video anonymisation using AnonySign retains the original sign language content.
Cell-free Massive MIMO with Short Packets
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we adapt to cell-free Massive MIMO (multiple-input multiple-output) the finite-blocklength framework introduced by Östman et al. (2020) for the characterization of the packet error probability achievable with Massive MIMO, in the ultra-reliable low-latency communications (URLLC) regime. The framework considered in this paper encompasses a cell-free architecture with imperfect channel-state information, and arbitrary linear signal processing performed at a central-processing unit connected to the access points via fronthaul links. By means of numerical simulations, we show that, to achieve the high reliability requirements in URLLC, MMSE signal processing must be used. Comparisons are also made with both small-cell and Massive MIMO cellular networks. Both require a much larger number of antennas to achieve comparable performance to cell-free Massive MIMO.
DeltaCharger: Charging Robot with Inverted Delta Mechanism and CNN-driven High Fidelity Tactile Perception for Precise 3D Positioning
Venue: arXiv cs.RO 2021
Year: 2021

DeltaCharger is a novel charging robot with an Inverted Delta structure for 3D positioning of electrodes to achieve robust and safe transferring energy between two mobile robots. The embedded high-fidelity tactile sensors allow to estimate the angular, vertical and horizontal misalignments between electrodes on the charger mechanism and electrodes on the target robot using pressure data on the contact surfaces. This is crucial for preventing a short circuit. In this paper, the mechanism of the developed prototype and evaluation study of different machine learning models for misalignment prediction are presented. The experimental results showed that the proposed system can measure the angle, vertical and horizontal values of misalignment from pressure data with an accuracy of 95.46%, 98.2%, and 86.9%, respectively, using a Convolutional Neural Network (CNN). DeltaCharger can potentially bring a new level of charging systems and improve the prevalence of mobile autonomous robots.
Philosophical Specification of Empathetic Ethical Artificial Intelligence
Venue: arXiv cs.AI 2021
Year: 2021

In order to construct an ethical artificial intelligence (AI) two complex problems must be overcome. Firstly, humans do not consistently agree on what is or is not ethical. Second, contemporary AI and machine learning methods tend to be blunt instruments which either search for solutions within the bounds of predefined rules, or mimic behaviour. An ethical AI must be capable of inferring unspoken rules, interpreting nuance and context, possess and be able to infer intent, and explain not just its actions but its intent. Using enactivism, semiotics, perceptual symbol systems and symbol emergence, we specify an agent that learns not just arbitrary relations between signs but their meaning in terms of the perceptual states of its sensorimotor system. Subsequently it can learn what is meant by a sentence and infer the intent of others in terms of its own experiences. It has malleable intent because the meaning of symbols changes as it learns, and its intent is represented symbolically as a goal. As such it may learn a concept of what is most likely to be considered ethical by the majority within a population of humans, which may then be used as a goal. The meaning of abstract symbols is expressed using perceptual symbols of raw sensorimotor stimuli as the weakest (consistent with Ockham's Razor) necessary and sufficient concept, an intensional definition learned from an ostensive definition, from which the extensional definition or category of all ethical decisions may be obtained. Because these abstract symbols are the same for both situation and response, the same symbol is used when either performing or observing an action. This is akin to mirror neurons in the human brain. Mirror symbols may allow the agent to empathise, because its own experiences are associated with the symbol, which is also associated with the observation of another agent experiencing something that symbol represents.
A novel teleoperator testbed to understand the effects of master-slave dynamics on embodiment and kinesthetic perception *
Venue: arXiv cs.RO 2021
Year: 2021

With the rising popularity of telerobotic systems, the focus on transparency with regards to haptic perception is also increasing. Transparency, however, represents a theoretical ideal as most bilateral force-reflecting telerobots introduce dynamics (stiffness and damping) between the operator and the environment. To achieve true dexterity, it will be essential to understand how humans embody the dynamics of these telerobots and thereby distinguish them from the environment they are exploring. In this short manuscript, we introduce a novel single degree-of-freedom testbed designed to perform psychophysical and task performance assessments of kinesthetic perception during telerobotic exploration. The system is capable of being configured as a rigid mechanical teleoperator, a dynamic mechanical teleoperator, and an electromechanicaal teleoperator. We performed prefatory system identification and found that the system is capable of simulating telerobotic exploration necessary to understand the impact of master-slave dynamics on kinesthetic perception.
Recovering lost and absent information in temporal networks
Venue: arXiv cs.SI 2021
Year: 2021

The full range of activity in a temporal network is captured in its edge activity data -- time series encoding the tie strengths or on-off dynamics of each edge in the network. However, in many practical applications, edge-level data are unavailable, and the network analyses must rely instead on node activity data which aggregates the edge-activity data and thus is less informative. This raises the question: Is it possible to use the static network to recover the richer edge activities from the node activities? Here we show that recovery is possible, often with a surprising degree of accuracy given how much information is lost, and that the recovered data are useful for subsequent network analysis tasks. Recovery is more difficult when network density increases, either topologically or dynamically, but exploiting dynamical and topological sparsity enables effective solutions to the recovery problem. We formally characterize the difficulty of the recovery problem both theoretically and empirically, proving the conditions under which recovery errors can be bounded and showing that, even when these conditions are not met, good quality solutions can still be derived. Effective recovery carries both promise and peril, as it enables deeper scientific study of complex systems but in the context of social systems also raises privacy concerns when social information can be aggregated across multiple data sources.