OpenRaiser/Intern-Atlas huggingface dataset:
Minimal unique palindromic substrings after single-character substitution
Venue: arXiv cs.DS 2021
Year: 2021

A palindrome is a string that reads the same forward and backward. A palindromic substring $w$ of a string $T$ is called a minimal unique palindromic substring (MUPS) of $T$ if $w$ occurs only once in $T$ and any proper palindromic substring of $w$ occurs at least twice in $T$. MUPSs are utilized for answering the shortest unique palindromic substring problem, which is motivated by molecular biology [Inoue et al., 2018]. Given a string $T$ of length $n$, all MUPSs of $T$ can be computed in $O(n)$ time. In this paper, we study the problem of updating the set of MUPSs when a character in the input string $T$ is substituted by another character. We first analyze the number $d$ of changes of MUPSs when a character is substituted, and show that $d$ is in $O(\log n)$. Further, we present an algorithm that uses $O(n)$ time and space for preprocessing, and updates the set of MUPSs in $O(\logσ+ (\log\log n)^2 + d)$ time where $σ$ is the alphabet size. We also propose a variant of the algorithm, which runs in optimal $O(1+d)$ time when the alphabet size is constant.
PyTorch, Explain! A Python library for Logic Explained Networks
Venue: arXiv cs.LG 2021
Year: 2021

"PyTorch, Explain!" is a Python module integrating a variety of state-of-the-art approaches to provide logic explanations from neural networks. This package focuses on bringing these methods to non-specialists. It has minimal dependencies and it is distributed under the Apache 2.0 licence allowing both academic and commercial use. Source code and documentation can be downloaded from the github repository: https://github.com/pietrobarbiero/pytorch_explain.
The Topology of Randomized Symmetry-Breaking Distributed Computing
Venue: arXiv cs.DC 2021
Year: 2021

Studying distributed computing through the lens of algebraic topology has been the source of many significant breakthroughs during the last two decades, especially in the design of lower bounds or impossibility results for deterministic algorithms. This paper aims at studying randomized synchronous distributed computing through the lens of algebraic topology. We do so by studying the wide class of (input-free) symmetry-breaking tasks, e.g., leader election, in synchronous fault-free anonymous systems. We show that it is possible to redefine solvability of a task "locally", i.e., for each simplex of the protocol complex individually, without requiring any global consistency. However, this approach has a drawback: it eliminates the topological aspect of the computation, since a single facet has a trivial topological structure. To overcome this issue, we introduce a "projection" $π$ of both protocol and output complexes, where every simplex $σ$ is mapped to a complex $π(σ)$; the later has a rich structure that replaces the structure we lost by considering one single facet at a time. To show the significance and applicability of our topological approach, we derive necessary and sufficient conditions for solving leader election in synchronous fault-free anonymous shared-memory and message-passing models. In both models, we consider scenarios in which there might be correlations between the random values provided to the nodes. In particular, different parties might have access to the same randomness source so their randomness is not independent but equal. Interestingly, we find that solvability of leader election relates to the number of parties that possess correlated randomness, either directly or via their greatest common divisor, depending on the specific communication model.
'They're all about pushing the products and shiny things rather than fundamental security' Mapping Socio-technical Challenges in Securing the Smart Home
Venue: arXiv cs.CR 2021
Year: 2021

Insecure connected devices can cause serious threats not just to smart home owners, but also the underlying infrastructural network as well. There has been increasing academic and regulatory interest in addressing cybersecurity risks from both the standpoint of Internet of Things (IoT) vendors and that of end-users. In addition to the current data protection and network security legal frameworks, for example, the UK government has initiated the 'Secure by Design' campaign. While there has been work on how organisations and individuals manage their own cybersecurity risks, it remains unclear to what extent IoT vendors are supporting end-users to perform day-to-day management of such risks in a usable way, and what is stopping the vendors from improving such support. We interviewed 13 experts in the field of IoT and identified three main categories of barriers to making IoT products usably secure: technical, legal and organisational. In this paper we further discuss the policymaking implications of these findings and make some recommendations.
Towards open-ended evolutionary simulator for developing novel tumour drug delivery systems
Venue: arXiv cs.MA 2021
Year: 2021

Tumours behave as moving targets that can evade chemotherapeutic treatments by rapidly acquiring resistance via various mechanisms. In Balaz et al. (2021, Biosystems; 199:104290) we initiated the development of the agent-based open-ended evolutionary simulator of novel drug delivery systems (DDS). It is an agent-based simulator where evolvable agents can change their perception of the environment and thus adapt to tumour mutations. Here we mapped the parameters of evolvable agent properties to the realistic biochemical boundaries and test their efficacy by simulating their behaviour at the cell scale using the stochastic simulator, STEPS. We show that the shape of the parameter space evolved in our simulator is comparable to those obtained by the rational design.
Dynamic Semantic Graph Construction and Reasoning for Explainable Multi-hop Science Question Answering
Venue: arXiv cs.CL 2021
Year: 2021

Knowledge retrieval and reasoning are two key stages in multi-hop question answering (QA) at web scale. Existing approaches suffer from low confidence when retrieving evidence facts to fill the knowledge gap and lack transparent reasoning process. In this paper, we propose a new framework to exploit more valid facts while obtaining explainability for multi-hop QA by dynamically constructing a semantic graph and reasoning over it. We employ Abstract Meaning Representation (AMR) as semantic graph representation. Our framework contains three new ideas: (a) {\tt AMR-SG}, an AMR-based Semantic Graph, constructed by candidate fact AMRs to uncover any hop relations among question, answer and multiple facts. (b) A novel path-based fact analytics approach exploiting {\tt AMR-SG} to extract active facts from a large fact pool to answer questions. (c) A fact-level relation modeling leveraging graph convolution network (GCN) to guide the reasoning process. Results on two scientific multi-hop QA datasets show that we can surpass recent approaches including those using additional knowledge graphs while maintaining high explainability on OpenBookQA and achieve a new state-of-the-art result on ARC-Challenge in a computationally practicable setting.
Millimeter-Wave Beamforming with Continuous Coverage for Mobile Interactive Virtual Reality
Venue: arXiv cs.NI 2021
Year: 2021

Contemporary Virtual Reality (VR) setups commonly consist of a Head-Mounted Display (HMD) tethered to a content-generating server. "Cutting the wire" in such setups and going truly wireless will require a wireless network capable of delivering enormous amounts of video data at an extremely low latency. Higher frequencies, such as the millimeter-wave (mmWave) band, can support these requirements. Due to high attenuation and path loss in the mmWave frequencies, beamforming is essential. For VR setups, beamforming must adapt in real-time to the user's head rotations, but can rely on the HMD's built-in sensors providing accurate orientation estimates. In this work, we present coVRage, a beamforming solution tailored for VR HMDs. Based on past and current head orientations, the HMD predicts how the Angle of Arrival (AoA) from the access point will change in the near future, and covers this AoA trajectory with a dynamically shaped beam, synthesized using sub-arrays. We show that this solution can cover such trajectories with consistently high gain, unlike regular single-beam solutions.
Extending the Abstraction of Personality Types based on MBTI with Machine Learning and Natural Language Processing
Venue: arXiv cs.CL 2021
Year: 2021

A data-centric approach with Natural Language Processing (NLP) to predict personality types based on the MBTI (an introspective self-assessment questionnaire that indicates different psychological preferences about how people perceive the world and make decisions) through systematic enrichment of text representation, based on the domain of the area, under the generation of features based on three types of analysis: sentimental, grammatical and aspects. The experimentation had a robust baseline of stacked models, with premature optimization of hyperparameters through grid search, with gradual feedback, for each of the four classifiers (dichotomies) of MBTI. The results showed that attention to the data iteration loop focused on quality, explanatory power and representativeness for the abstraction of more relevant/important resources for the studied phenomenon made it possible to improve the evaluation metrics results more quickly and less costly than complex models such as the LSTM or state of the art ones as BERT, as well as the importance of these results by comparisons made from various perspectives. In addition, the study demonstrated a broad spectrum for the evolution and deepening of the task and possible approaches for a greater extension of the abstraction of personality types.
A Generalised Inverse Reinforcement Learning Framework
Venue: arXiv cs.LG 2021
Year: 2021

The gloabal objective of inverse Reinforcement Learning (IRL) is to estimate the unknown cost function of some MDP base on observed trajectories generated by (approximate) optimal policies. The classical approach consists in tuning this cost function so that associated optimal trajectories (that minimise the cumulative discounted cost, i.e. the classical RL loss) are 'similar' to the observed ones. Prior contributions focused on penalising degenerate solutions and improving algorithmic scalability. Quite orthogonally to them, we question the pertinence of characterising optimality with respect to the cumulative discounted cost as it induces an implicit bias against policies with longer mixing times. State of the art value based RL algorithms circumvent this issue by solving for the fixed point of the Bellman optimality operator, a stronger criterion that is not well defined for the inverse problem. To alleviate this bias in IRL, we introduce an alternative training loss that puts more weights on future states which yields a reformulation of the (maximum entropy) IRL problem. The algorithms we devised exhibit enhanced performances (and similar tractability) than off-the-shelf ones in multiple OpenAI gym environments.
Simulation, Model Checking, and Execution of Activity Models
Venue: arXiv cs.SE 2021
Year: 2021

This paper presents our findings for using activity modeling for simulation (validation), model checking (verification), and execution purposes. Each is needed to tackle system complexity and further research into behavioral modeling. We argue different models implicate different understandings and expectations. We emphasize some distinctions with demonstrations using the Discrete Event System Specification with an exemplary model. In particular, the continuous-time base in models helps observe some inherent limitations and strengths in acquiring each capability. The temporal characterization of input, output, and state, or the lack thereof, is at the core of developing behavioral specifications. We use DEVS to arrive at the capability of validating simulations for activity models. We use Constrained-DEVS for the verification of activity models. We show how some executions can be derived, whether from the specification itself or with considerations for simulation and model checking.
Spectrum Correction: Acoustic Scene Classification with Mismatched Recording Devices
Venue: arXiv cs.SD 2021
Year: 2021

Machine learning algorithms, when trained on audio recordings from a limited set of devices, may not generalize well to samples recorded using other devices with different frequency responses. In this work, a relatively straightforward method is introduced to address this problem. Two variants of the approach are presented. First requires aligned examples from multiple devices, the second approach alleviates this requirement. This method works for both time and frequency domain representations of audio recordings. Further, a relation to standardization and Cepstral Mean Subtraction is analysed. The proposed approach becomes effective even when very few examples are provided. This method was developed during the Detection and Classification of Acoustic Scenes and Events (DCASE) 2019 challenge and won the 1st place in the scenario with mis-matched recording devices with the accuracy of 75%. Source code for the experiments can be found online.
Unsupervised Sentiment Analysis by Transferring Multi-source Knowledge
Venue: arXiv cs.CL 2021
Year: 2021

Sentiment analysis (SA) is an important research area in cognitive computation-thus in-depth studies of patterns of sentiment analysis are necessary. At present, rich resource data-based SA has been well developed, while the more challenging and practical multi-source unsupervised SA (i.e. a target domain SA by transferring from multiple source domains) is seldom studied. The challenges behind this problem mainly locate in the lack of supervision information, the semantic gaps among domains (i.e., domain shifts), and the loss of knowledge. However, existing methods either lack the distinguishable capacity of the semantic gaps among domains or lose private knowledge. To alleviate these problems, we propose a two-stage domain adaptation framework. In the first stage, a multi-task methodology-based shared-private architecture is employed to explicitly model the domain common features and the domain-specific features for the labeled source domains. In the second stage, two elaborate mechanisms are embedded in the shared private architecture to transfer knowledge from multiple source domains. The first mechanism is a selective domain adaptation (SDA) method, which transfers knowledge from the closest source domain. And the second mechanism is a target-oriented ensemble (TOE) method, in which knowledge is transferred through a well-designed ensemble method. Extensive experiment evaluations verify that the performance of the proposed framework outperforms unsupervised state-of-the-art competitors. What can be concluded from the experiments is that transferring from very different distributed source domains may degrade the target-domain performance, and it is crucial to choose the proper source domains to transfer from.
MBIC -- A Media Bias Annotation Dataset Including Annotator Characteristics
Venue: arXiv cs.CL 2021
Year: 2021

Many people consider news articles to be a reliable source of information on current events. However, due to the range of factors influencing news agencies, such coverage may not always be impartial. Media bias, or slanted news coverage, can have a substantial impact on public perception of events, and, accordingly, can potentially alter the beliefs and views of the public. The main data gap in current research on media bias detection is a robust, representative, and diverse dataset containing annotations of biased words and sentences. In particular, existing datasets do not control for the individual background of annotators, which may affect their assessment and, thus, represents critical information for contextualizing their annotations. In this poster, we present a matrix-based methodology to crowdsource such data using a self-developed annotation platform. We also present MBIC (Media Bias Including Characteristics) - the first sample of 1,700 statements representing various media bias instances. The statements were reviewed by ten annotators each and contain labels for media bias identification both on the word and sentence level. MBIC is the first available dataset about media bias reporting detailed information on annotator characteristics and their individual background. The current dataset already significantly extends existing data in this domain providing unique and more reliable insights into the perception of bias. In future, we will further extend it both with respect to the number of articles and annotators per article.
Automata Learning for Automated Test Generation of Real Time Localization Systems
Venue: arXiv cs.FL 2021
Year: 2021

Cyber Physical Systems (CPSs) are often black box systems for which no exact model exists. Automata learning allows to build abstract models of CPSs and is used in several scenarios, i.e. simulation, monitoring, and test case generation. Real time localization systems (RTLSs) are an example of particularly complex and often safety critical CPSs. We present a procedure for automatic test case generation with automata learning and apply this approach in a case study to a localization system.
Theory and Design of Super-resolution Haptic Skins
Venue: arXiv cs.RO 2021
Year: 2021

Haptic feedback is important to make robots more dexterous and effective in unstructured environments. High-resolution haptic sensors are still not widely available, and their application is often bound by the resolution-robustness dilemma. A route towards high-resolution and robust skin embeds a few sensor units (taxels) into a flexible surface material and uses signal processing to achieve sensing with super-resolution accuracy. We propose a theory for geometric super-resolution to guide the development of haptic sensors of this kind and link it to machine learning techniques for signal processing. This theory is based on sensor isolines and allows us to predict force sensitivity and accuracy in contact position and force magnitude as a spatial quantity. We evaluate the influence of different factors, such as elastic properties of the material, structure design, and transduction methods, using finite element simulations and by implementing real sensors. We empirically determine sensor isolines and validate the theory in two custom-built sensors with barometric units for 1D and 2D measurement surfaces. Using machine learning methods for the inference of contact information, our sensors obtain an unparalleled average super-resolution factor of over 100 and 1200, respectively. Our theory can guide future haptic sensor designs and inform various design choices.
Execution of NVRAM Programs with Persistent Stack
Venue: arXiv cs.DC 2021
Year: 2021

Non-Volatile Random Access Memory (NVRAM) is a novel type of hardware that combines the benefits of traditional persistent memory (persistency of data over hardware failures) and DRAM (fast random access). In this work, we describe an algorithm that can be used to execute NVRAM programs and recover the system after a hardware failure while taking the architecture of real-world NVRAM systems into account. Moreover, the algorithm can be used to execute NVRAM-destined programs on commodity persistent hardware, such as hard drives. That allows us to test NVRAM algorithms using only cheap hardware, without having access to the NVRAM. We report the usage of our algorithm to implement and test NVRAM CAS algorithm.
Hierarchical Subspace Learning for Dimensionality Reduction to Improve Classification Accuracy in Large Data Sets
Venue: arXiv cs.LG 2021
Year: 2021

Manifold learning is used for dimensionality reduction, with the goal of finding a projection subspace to increase and decrease the inter- and intraclass variances, respectively. However, a bottleneck for subspace learning methods often arises from the high dimensionality of datasets. In this paper, a hierarchical approach is proposed to scale subspace learning methods, with the goal of improving classification in large datasets by a range of 3% to 10%. Different combinations of methods are studied. We assess the proposed method on five publicly available large datasets, for different eigen-value based subspace learning methods such as linear discriminant analysis, principal component analysis, generalized discriminant analysis, and reconstruction independent component analysis. To further examine the effect of the proposed method on various classification methods, we fed the generated result to linear discriminant analysis, quadratic linear analysis, k-nearest neighbor, and random forest classifiers. The resulting classification accuracies are compared to show the effectiveness of the hierarchical approach, reporting results of an average of 5% increase in classification accuracy.
Providing Meaningful Data Summarizations Using Exemplar-based Clustering in Industry 4.0
Venue: arXiv cs.DC 2021
Year: 2021

Data summarizations are a valuable tool to derive knowledge from large data streams and have proven their usefulness in a great number of applications. Summaries can be found by optimizing submodular functions. These functions map subsets of data to real values, which indicate their "representativeness" and which should be maximized to find a diverse summary of the underlying data. In this paper, we studied Exemplar-based clustering as a submodular function and provide a GPU algorithm to cope with its high computational complexity. We show, that our GPU implementation provides speedups of up to 72x using single-precision and up to 452x using half-precision computation compared to conventional CPU algorithms. We also show, that the GPU algorithm not only provides remarkable runtime benefits with workstation-grade GPUs but also with low-power embedded computation units for which speedups of up to 35x are possible. Furthermore, we apply our algorithm to real-world data from injection molding manufacturing processes and discuss how found summaries help with steering this specific process to cut costs and reduce the manufacturing of bad parts. Beyond pure speedup considerations, we show, that our approach can provide summaries within reasonable time frames for this kind of industrial, real-world data.
Real-time Monocular Depth Estimation with Sparse Supervision on Mobile
Venue: arXiv cs.CV 2021
Year: 2021

Monocular (relative or metric) depth estimation is a critical task for various applications, such as autonomous vehicles, augmented reality and image editing. In recent years, with the increasing availability of mobile devices, accurate and mobile-friendly depth models have gained importance. Increasingly accurate models typically require more computational resources, which inhibits the use of such models on mobile devices. The mobile use case is arguably the most unrestricted one, which requires highly accurate yet mobile-friendly architectures. Therefore, we try to answer the following question: How can we improve a model without adding further complexity (i.e. parameters)? Towards this end, we systematically explore the design space of a relative depth estimation model from various dimensions and we show, with key design choices and ablation studies, even an existing architecture can reach highly competitive performance to the state of the art, with a fraction of the complexity. Our study spans an in-depth backbone model selection process, knowledge distillation, intermediate predictions, model pruning and loss rebalancing. We show that our model, using only DIW as the supervisory dataset, achieves 0.1156 WHDR on DIW with 2.6M parameters and reaches 37 FPS on a mobile GPU, without pruning or hardware-specific optimization. A pruned version of our model achieves 0.1208 WHDR on DIW with 1M parameters and reaches 44 FPS on a mobile GPU.