OpenRaiser/Intern-Atlas huggingface dataset:
Component twin-width as a parameter for BINARY-CSP and its semiring generalisations
Venue: arXiv cs.CC 2022
Year: 2022

We investigate the fine-grained and the parameterized complexity of several generalizations of binary constraint satisfaction problems (BINARY-CSPs), that subsume variants of graph colouring problems. Our starting point is the observation that several algorithmic approaches that resulted in complexity upper bounds for these problems, share a common structure. We thus explore an algebraic approach relying on semirings that unifies different generalizations of BINARY-CSPs (such as the counting, the list, and the weighted versions), and that facilitates a general algorithmic approach to efficiently solving them. The latter is inspired by the (component) twin-width parameter introduced by Bonnet et al., which we generalize via edge-labelled graphs in order to formulate it to arbitrary binary constraints. We consider input instances with bounded component twin-width, as well as constraint templates of bounded component twin-width, and obtain an FPT algorithm as well as an improved, exponential-time algorithm, for broad classes of binary constraints. We illustrate the advantages of this framework by instantiating our general algorithmic approach on several classes of problems (e.g., the $H$-coloring problem and its variants), and showing that it improves the best complexity upper bounds in the literature for several well-known problems.
Secure Service Implementation with Slice Isolation and WireGuard
Venue: arXiv cs.NI 2022
Year: 2022

Network slicing enables the provision of services for different verticals over a shared infrastructure. Nevertheless, security is still one of the main challenges when sharing resources. In this paper, we study how WireGuard can provide an encrypted Virtual Private Network (VPN) tunnel as a service between network functions in 5G setting. The open source management and orchestration entity deploys and orchestrates the network functions into network services and slices. We create multiple scenarios emulating a real-life cellular network deploying VPN-as-a-Service between the different network functions to secure and isolate network slices. The performance measurements demonstrate from 0.8 Gbps to 2.5 Gbps throughput and below 1ms delay between network functions using WireGuard. The performance evaluation results are aligned with 5G key performance indicators, making WireGuard suited to provide security in slice isolation in future generations of cellular networks.
Bayesian tensor factorization for predicting clinical outcomes using integrated human genetics evidence
Venue: arXiv cs.LG 2022
Year: 2022

The approval success rate of drug candidates is very low with the majority of failure due to safety and efficacy. Increasingly available high dimensional information on targets, drug molecules and indications provides an opportunity for ML methods to integrate multiple data modalities and better predict clinically promising drug targets. Notably, drug targets with human genetics evidence are shown to have better odds to succeed. However, a recent tensor factorization-based approach found that additional information on targets and indications might not necessarily improve the predictive accuracy. Here we revisit this approach by integrating different types of human genetics evidence collated from publicly available sources to support each target-indication pair. We use Bayesian tensor factorization to show that models incorporating all available human genetics evidence (rare disease, gene burden, common disease) modestly improves the clinical outcome prediction over models using single line of genetics evidence. We provide additional insight into the relative predictive power of different types of human genetics evidence for predicting the success of clinical outcomes.
On Deep Holes of Elliptic Curve Codes
Venue: arXiv cs.IT 2022
Year: 2022

We give a method to construct deep holes for elliptic curve codes. For long elliptic curve codes, we conjecture that our construction is complete in the sense that it gives all deep holes. Some evidence and heuristics on the completeness are provided via the connection with problems and results in finite geometry.
Bilateral Self-unbiased Learning from Biased Implicit Feedback
Venue: arXiv cs.IR 2022
Year: 2022

Implicit feedback has been widely used to build commercial recommender systems. Because observed feedback represents users' click logs, there is a semantic gap between true relevance and observed feedback. More importantly, observed feedback is usually biased towards popular items, thereby overestimating the actual relevance of popular items. Although existing studies have developed unbiased learning methods using inverse propensity weighting (IPW) or causal reasoning, they solely focus on eliminating the popularity bias of items. In this paper, we propose a novel unbiased recommender learning model, namely BIlateral SElf-unbiased Recommender (BISER), to eliminate the exposure bias of items caused by recommender models. Specifically, BISER consists of two key components: (i) self-inverse propensity weighting (SIPW) to gradually mitigate the bias of items without incurring high computational costs; and (ii) bilateral unbiased learning (BU) to bridge the gap between two complementary models in model predictions, i.e., user- and item-based autoencoders, alleviating the high variance of SIPW. Extensive experiments show that BISER consistently outperforms state-of-the-art unbiased recommender models over several datasets, including Coat, Yahoo! R3, MovieLens, and CiteULike.
Teaching Functional Programmers Logic and Metatheory
Venue: arXiv cs.PL 2022
Year: 2022

We present a novel approach for teaching logic and the metatheory of logic to students who have some experience with functional programming. We define concepts in logic as a series of functional programs in the language of the proof assistant Isabelle/HOL. This allows us to make notions which are often unclear in textbooks precise, to experiment with definitions by executing them, and to prove metatheoretical theorems in full detail. We have surveyed student perceptions of our teaching approach to determine its usefulness and found that students felt that our formalizations helped them understand concepts in logic, and that they experimented with them as a learning tool. However, the approach was not enough to make students feel confident in their abilities to design and implement their own formal systems. Further studies are needed to confirm and generalize the results of our survey, but our initial results seem promising.
Engaging, Large-Scale Functional Programming Education in Physical and Virtual Space
Venue: arXiv cs.CY 2022
Year: 2022

Worldwide, computer science departments have experienced a dramatic increase in the number of student enrolments. Moreover, the ongoing COVID-19 pandemic requires institutions to radically replace the traditional way of on-site teaching, moving interaction from physical to virtual space. We report on our strategies and experience tackling these issues as part of a Haskell-based functional programming and verification course, accommodating over 2000 students in the course of two semesters. Among other things, we fostered engagement with weekly programming competitions and creative homework projects, workshops with industry partners, and collaborative pair-programming tutorials. To offer such an extensive programme to hundreds of students, we automated feedback for programming as well as inductive proof exercises. We explain and share our tools and exercises so that they can be reused by other educators.
Implementing the Comparison-Based External Sort
Venue: arXiv cs.DB 2022
Year: 2022

In the age of big data, sorting is an indispensable operation for DBMSes and similar systems. Having data sorted can help produce query plans with significantly lower run times. It also can provide other benefits like having non-blocking operators which will produce data steadily (without bursts), or operators with reduced memory footprint. Sorting may be required on any step of query processing, i.e., be it source data or intermediate results. At the same time, the data to be sorted may not fit into main memory. In this case, an external sort operator, which writes intermediate results to disk, should be used. In this paper we consider an external sort operator of the comparison-based sort type. We discuss its implementation and describe related design decisions. Our aim is to study the impact on performance of a data structure used on the merge step. For this, we have experimentally evaluated three data structures implemented inside a DBMS. Results have shown that it is worthwhile to make an effort to implement an efficient data structure for run merging, even on modern commodity computers which are usually disk-bound. Moreover, we demonstrated that using a loser tree is a more efficient approach than both the naive approach and the heap-based one.
An Automated News Bias Classifier Using Caenorhabditis Elegans Inspired Recursive Feedback Network Architecture
Venue: arXiv cs.NE 2022
Year: 2022

Traditional approaches to classify the political bias of news articles have failed to generate accurate, generalizable results. Existing networks premised on CNNs and DNNs lack a model to identify and extrapolate subtle indicators of bias like word choice, context, and presentation. In this paper, we propose a network architecture that achieves human-level accuracy in assigning bias classifications to articles. The underlying model is based on a novel Mesh Neural Network (MNN),this structure enables feedback and feedforward synaptic connections between any two neurons in the mesh. The MNN ontains six network configurations that utilize Bernoulli based random sampling, pre-trained DNNs, and a network modelled after the C. Elegans nematode. The model is trained on over ten-thousand articles scraped from AllSides.com which are labelled to indicate political bias. The parameters of the network are then evolved using a genetic algorithm suited to the feedback neural structure. Finally, the best performing model is applied to five popular news sources in the United States over a fifty-day trial to quantify political biases in the articles they display. We hope our project can spur research into biological solutions for NLP tasks and provide accurate tools for citizens to understand subtle biases in the articles they consume.
SPAIC: A Spike-based Artificial Intelligence Computing Framework
Venue: arXiv cs.NE 2022
Year: 2022

Neuromorphic computing is an emerging research field that aims to develop new intelligent systems by integrating theories and technologies from multi-disciplines such as neuroscience and deep learning. Currently, there have been various software frameworks developed for the related fields, but there is a lack of an efficient framework dedicated for spike-based computing models and algorithms. In this work, we present a Python based spiking neural network (SNN) simulation and training framework, aka SPAIC that aims to support brain-inspired model and algorithm researches integrated with features from both deep learning and neuroscience. To integrate different methodologies from the two overwhelming disciplines, and balance between flexibility and efficiency, SPAIC is designed with neuroscience-style frontend and deep learning backend structure. We provide a wide range of examples including neural circuits Simulation, deep SNN learning and neuromorphic applications, demonstrating the concise coding style and wide usability of our framework. The SPAIC is a dedicated spike-based artificial intelligence computing platform, which will significantly facilitate the design, prototype and validation of new models, theories and applications. Being user-friendly, flexible and high-performance, it will help accelerate the rapid growth and wide applicability of neuromorphic computing research.
Training Effective Neural Sentence Encoders from Automatically Mined Paraphrases
Venue: arXiv cs.CL 2022
Year: 2022

Sentence embeddings are commonly used in text clustering and semantic retrieval tasks. State-of-the-art sentence representation methods are based on artificial neural networks fine-tuned on large collections of manually labeled sentence pairs. Sufficient amount of annotated data is available for high-resource languages such as English or Chinese. In less popular languages, multilingual models have to be used, which offer lower performance. In this publication, we address this problem by proposing a method for training effective language-specific sentence encoders without manually labeled data. Our approach is to automatically construct a dataset of paraphrase pairs from sentence-aligned bilingual text corpora. We then use the collected data to fine-tune a Transformer language model with an additional recurrent pooling layer. Our sentence encoder can be trained in less than a day on a single graphics card, achieving high performance on a diverse set of sentence-level tasks. We evaluate our method on eight linguistic tasks in Polish, comparing it with the best available multilingual sentence encoders.
The Human in the Infinite Loop: A Case Study on Revealing and Explaining Human-AI Interaction Loop Failures
Venue: arXiv cs.HC 2022
Year: 2022

Interactive AI systems increasingly employ a human-in-the-loop strategy. This creates new challenges for the HCI community when designing such systems. We reveal and investigate some of these challenges in a case study with an industry partner, and developed a prototype human-in-the-loop system for preference-guided 3D model processing. Two 3D artists used it in their daily work for 3 months. We found that the human-AI loop often did not converge towards a satisfactory result and designed a lab study (N=20) to investigate this further. We analyze interaction data and user feedback through the lens of theories of human judgment to explain the observed human-in-the-loop failures with two key insights: 1) optimization using preferential choices lacks mechanisms to deal with inconsistent and contradictory human judgments; 2) machine outcomes, in turn, influence future user inputs via heuristic biases and loss aversion. To mitigate these problems, we propose descriptive UI design guidelines. Our case study draws attention to challenging and practically relevant imperfections in human-AI loops that need to be considered when designing human-in-the-loop systems.
Clustering Object-Centric Event Logs
Venue: arXiv cs.AI 2022
Year: 2022

Process mining provides various algorithms to analyze process executions based on event data. Process discovery, the most prominent category of process mining techniques, aims to discover process models from event logs, however, it leads to spaghetti models when working with real-life data. Therefore, several clustering techniques have been proposed on top of traditional event logs (i.e., event logs with a single case notion) to reduce the complexity of process models and discover homogeneous subsets of cases. Nevertheless, in real-life processes, particularly in the context of Business-to-Business (B2B) processes, multiple objects are involved in a process. Recently, Object-Centric Event Logs (OCELs) have been introduced to capture the information of such processes, and several process discovery techniques have been developed on top of OCELs. Yet, the output of the proposed discovery techniques on real OCELs leads to more informative but also more complex models. In this paper, we propose a clustering-based approach to cluster similar objects in OCELs to simplify the obtained process models. Using a case study of a real B2B process, we demonstrate that our approach reduces the complexity of the process models and generates coherent subsets of objects which help the end-users gain insights into the process.
Visualization Design Practices in a Crisis: Behind the Scenes with COVID-19 Dashboard Creators
Venue: arXiv cs.HC 2022
Year: 2022

During the COVID-19 pandemic, a number of data visualizations were created to inform the public about the rapidly evolving crisis. Data dashboards, a form of information dissemination used during the pandemic, have facilitated this process by visualizing statistics regarding the number of COVID-19 cases over time. In this research, we conducted a qualitative interview study among dashboard creators from federal agencies, state health departments, mainstream news media outlets, and other organizations that created (often widely-used) COVID-19 dashboards to answer the following questions: how did visualization creators engage in COVID-19 dashboard design, and what tensions, conflicts, and challenges arose during this process? Our findings detail the trajectory of design practices -- from creation to expansion, maintenance, and termination -- that are shaped by the complex interplay between design goals, tools and technologies, labor, emerging crisis contexts, and public engagement. We particularly examined the tensions between designers and the general public involved in these processes. These conflicts, which often materialized due to a divergence between public demands and standing policies, centered around the type and amount of information to be visualized, how public perceptions shape and are shaped by visualization design, and the strategies utilized to deal with (potential) misinterpretations and misuse of visualizations. Our findings and lessons learned shed light on new ways of thinking in visualization design, focusing on the bundled activities that are invariably involved in human and nonhuman participation throughout the entire trajectory of design practice.
Generalized Probabilistic U-Net for medical image segementation
Venue: arXiv cs.CV 2022
Year: 2022

We propose the Generalized Probabilistic U-Net, which extends the Probabilistic U-Net by allowing more general forms of the Gaussian distribution as the latent space distribution that can better approximate the uncertainty in the reference segmentations. We study the effect the choice of latent space distribution has on capturing the uncertainty in the reference segmentations using the LIDC-IDRI dataset. We show that the choice of distribution affects the sample diversity of the predictions and their overlap with respect to the reference segmentations. For the LIDC-IDRI dataset, we show that using a mixture of Gaussians results in a statistically significant improvement in the generalized energy distance (GED) metric with respect to the standard Probabilistic U-Net. We have made our implementation available at https://github.com/ishaanb92/GeneralizedProbabilisticUNet
LaKo: Knowledge-driven Visual Question Answering via Late Knowledge-to-Text Injection
Venue: arXiv cs.CV 2022
Year: 2022

Visual question answering (VQA) often requires an understanding of visual concepts and language semantics, which relies on external knowledge. Most existing methods exploit pre-trained language models or/and unstructured text, but the knowledge in these resources are often incomplete and noisy. Some other methods prefer to use knowledge graphs (KGs) which often have intensive structured knowledge, but the research is still quite preliminary. In this paper, we propose LaKo, a knowledge-driven VQA method via Late Knowledge-to-text Injection. To effectively incorporate an external KG, we transfer triples into textual format and propose a late injection mechanism for knowledge fusion. Finally we address VQA as a text generation task with an effective encoder-decoder paradigm, which achieves state-of-the-art results on OKVQA dataset.
Playback-centric visualisations of video usage using weighted interactions to guide where to watch in an educational context
Venue: arXiv cs.MM 2022
Year: 2022

The increase in use of online educational tools has led to a large amount of educational video materials made available for students. Finding the right video content is usually supported by the overarching learning management system and its interface that organises video items by course, categories and weeks, and makes them searchable. However, once a video is found, students are left without further guidance as to what parts in that video they should focus on. In this article, an additional timeline visualisation to augment the conventional playback timeline is introduced which employs a novel playback weighting strategy in which the history of different video interactions generate scores based on the context of each playback. The resultant scores are presented on the additional timeline, making it in effect a playback-centric usage graph nuanced by how each playback was executed. Students can selectively watch those portions which the contour of the usage visualisation suggests. The visualisation was implemented and deployed in an undergraduate course at a university for two full semesters. 270 students used the system throughout both semesters watching 52 videos, guided by visualisations on what to watch. Analysis of playback logs revealed students selectively watched corresponding to the most important portions of the videos as assessed by the instructor who created the videos. The characteristics of this as a way of guiding students as to where to watch as well as a complementary tool for playback analysis, are discussed. Further insights into the potential values of this visualisation and its underlying playback weighting strategy are also discussed.
Maximum Weight Convex Polytope
Venue: arXiv cs.CG 2022
Year: 2022

We study the maximum weight convex polytope problem, in which the goal is to find a convex polytope maximizing the total weight of enclosed points. Prior to this work, the only known result for this problem was an $O(n^3)$ algorithm for the case of $2$ dimensions due to Bautista et al. We show that the problem becomes $\mathcal{NP}$-hard to solve exactly in $3$ dimensions, and $\mathcal{NP}$-hard to approximate within $n^{1/2-ε}$ for any $ε> 0$ in $4$ or more dimensions. %\polyAPX-complete in $4$ dimensions even with binary weights. We also give a new algorithm for $2$ dimensions, albeit with the same $O(n^3)$ running time complexity as that of the algorithm of Bautsita et al.
Semantic Segmentation for Autonomous Driving: Model Evaluation, Dataset Generation, Perspective Comparison, and Real-Time Capability
Venue: arXiv cs.CV 2022
Year: 2022

Environmental perception is an important aspect within the field of autonomous vehicles that provides crucial information about the driving domain, including but not limited to identifying clear driving areas and surrounding obstacles. Semantic segmentation is a widely used perception method for self-driving cars that associates each pixel of an image with a predefined class. In this context, several segmentation models are evaluated regarding accuracy and efficiency. Experimental results on the generated dataset confirm that the segmentation model FasterSeg is fast enough to be used in realtime on lowpower computational (embedded) devices in self-driving cars. A simple method is also introduced to generate synthetic training data for the model. Moreover, the accuracy of the first-person perspective and the bird's eye view perspective are compared. For a $320 \times 256$ input in the first-person perspective, FasterSeg achieves $65.44\,\%$ mean Intersection over Union (mIoU), and for a $320 \times 256$ input from the bird's eye view perspective, FasterSeg achieves $64.08\,\%$ mIoU. Both perspectives achieve a frame rate of $247.11$ Frames per Second (FPS) on the NVIDIA Jetson AGX Xavier. Lastly, the frame rate and the accuracy with respect to the arithmetic 16-bit Floating Point (FP16) and 32-bit Floating Point (FP32) of both perspectives are measured and compared on the target hardware.