OpenRaiser/Intern-Atlas huggingface dataset:
PPP-Completeness and Extremal Combinatorics
Venue: arXiv cs.CC 2022
Year: 2022

Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erdős-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard; here "implici" means that the collection is represented by a poly-sized circuit inducing an exponentially large number of objects. We show that several other well-known theorems from extremal combinatorics - including Erdős-Ko-Rado, Sperner, and Cayley's formula - give rise to complete problems for PWPP and PPP. This is in contrast to the Ramsey and Erdős-Rado problems, for which establishing inclusion in PWPP has remained elusive. Besides significantly expanding the set of problems that are complete for PWPP and PPP, our work identifies some key properties of combinatorial proofs of existence that can give rise to completeness for these classes. Our completeness results rely on efficient encodings for which finding collisions allows extracting the desired substructure. These encodings are made possible by the tightness of the bounds for the problems at hand (tighter than what is known for Ramsey's theorem and the sunflower lemma). Previous techniques for proving bounds in TFNP invariably made use of structured algorithms. Such algorithms are not known to exist for the theorems considered in this work, as their proofs "from the book" are non-constructive.
Joint Activity Detection and Channel Estimation for Massive IoT Access Based on Millimeter-Wave/Terahertz Multi-Panel Massive MIMO
Venue: arXiv cs.IT 2022
Year: 2022

The multi-panel array, as a state-of-the-art antenna-in-package technology, is very suitable for millimeter-wave (mmWave)/terahertz (THz) systems, due to its low-cost deployment and scalable configuration. But in the context of nonuniform array structures it leads to intractable signal processing. Based on such an array structure at the base station, this paper investigates a joint active user detection (AUD) and channel estimation (CE) scheme based on compressive sensing (CS) for application to the massive Internet of Things (IoT). Specifically, by exploiting the structured sparsity of mmWave/THz massive IoT access channels, we firstly formulate the multi-panel massive multiple-input multiple-output (mMIMO)-based joint AUD and CE problem as a multiple measurement vector (MMV)-CS problem. Then, we harness the expectation maximization (EM) algorithm to learn the prior parameters (i.e., the noise variance and the sparsity ratio) and an orthogonal approximate message passing (OAMP)-EM-MMV algorithm is developed to solve this problem. Our simulation results verify the improved AUD and CE performance of the proposed scheme compared to conventional CS-based algorithms.
Formal Semantics of the Kconfig Language
Venue: arXiv cs.SE 2022
Year: 2022

The Kconfig language defines a set of symbols that are assigned a value in a configuration. We describe the semantics of the Kconfig language according to the behavior exhibited in the xconfig configurator. We assume an abstract syntax representation for concepts in the Kconfig language and delegate the details of the translation from concrete to abstract syntaxes to a later document.
Multi-modal Streaming 3D Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

Modern autonomous vehicles rely heavily on mechanical LiDARs for perception. Current perception methods generally require 360° point clouds, collected sequentially as the LiDAR scans the azimuth and acquires consecutive wedge-shaped slices. The acquisition latency of a full scan (~ 100ms) may lead to outdated perception which is detrimental to safe operation. Recent streaming perception works proposed directly processing LiDAR slices and compensating for the narrow field of view (FOV) of a slice by reusing features from preceding slices. These works, however, are all based on a single modality and require past information which may be outdated. Meanwhile, images from high-frequency cameras can support streaming models as they provide a larger FoV compared to a LiDAR slice. However, this difference in FoV complicates sensor fusion. To address this research gap, we propose an innovative camera-LiDAR streaming 3D object detection framework that uses camera images instead of past LiDAR slices to provide an up-to-date, dense, and wide context for streaming perception. The proposed method outperforms prior streaming models on the challenging NuScenes benchmark. It also outperforms powerful full-scan detectors while being much faster. Our method is shown to be robust to missing camera images, narrow LiDAR slices, and small camera-LiDAR miscalibration.
Embracing AI in 5G-Advanced Towards 6G: A Joint 3GPP and O-RAN Perspective
Venue: arXiv cs.NI 2022
Year: 2022

Artificial intelligence (AI) has emerged as a powerful technology that improves system performance and enables new features in 5G and beyond. Standardization, defining functionality and interfaces, is essential for driving the industry alignment required to deliver the mass adoption of AI in 5G-Advanced and 6G. However, fragmented efforts in different standards bodies, such as the third generation partnership project (3GPP) and the open radio access network (O-RAN) Alliance, can lead to confusion and uncertainty about which standards to follow and which aspects of the standards to embrace. This article provides a joint 3GPP and O-RAN perspective on the state of the art in AI adoption in mobile communication systems, including the fundamentals of 5G architecture and its evolution towards openness and intelligence, AI for 5G-Advanced evolution, and a case study on AI-enabled traffic steering. We also identify several areas for future exploration to accelerate AI adoption on the path towards 6G.
Joint Upper & Lower Bound Normalization for IR Evaluation
Venue: arXiv cs.IR 2022
Year: 2022

In this paper, we present a novel perspective towards IR evaluation by proposing a new family of evaluation metrics where the existing popular metrics (e.g., nDCG, MAP) are customized by introducing a query-specific lower-bound (LB) normalization term. While original nDCG, MAP etc. metrics are normalized in terms of their upper bounds based on an ideal ranked list, a corresponding LB normalization for them has not yet been studied. Specifically, we introduce two different variants of the proposed LB normalization, where the lower bound is estimated from a randomized ranking of the corresponding documents present in the evaluation set. We next conducted two case-studies by instantiating the new framework for two popular IR evaluation metric (with two variants, e.g., DCG_UL_V1,2 and MSP_UL_V1,2 ) and then comparing against the traditional metric without the proposed LB normalization. Experiments on two different data-sets with eight Learning-to-Rank (LETOR) methods demonstrate the following properties of the new LB normalized metric: 1) Statistically significant differences (between two methods) in terms of original metric no longer remain statistically significant in terms of Upper Lower (UL) Bound normalized version and vice-versa, especially for uninformative query-sets. 2) When compared against the original metric, our proposed UL normalized metrics demonstrate higher Discriminatory Power and better Consistency across different data-sets. These findings suggest that the IR community should consider UL normalization seriously when computing nDCG and MAP and more in-depth study of UL normalization for general IR evaluation is warranted.
Innovative ideas for teaching supports: Application to Graph theory
Venue: arXiv cs.DM 2022
Year: 2022

Teaching graph theory with the most adequate tools requires time and ideas. We present how an open community of teachers shares contents and ideas on an innovative platform. The objective is to get the students autonomous in their training with activities that give them immediate feedback on their understanding. Beyond learning, the very large collection of exercises of various levels can also be used to evaluate the student's level. The proposed activities can be algorithm's code in classical programming languages (e.g. Java, Python) that the student can test with predefined tests proposed by the teacher or collections of generated questions.
Explaining Predictions from Machine Learning Models: Algorithms, Users, and Pedagogy
Venue: arXiv cs.LG 2022
Year: 2022

Model explainability has become an important problem in machine learning (ML) due to the increased effect that algorithmic predictions have on humans. Explanations can help users understand not only why ML models make certain predictions, but also how these predictions can be changed. In this thesis, we examine the explainability of ML models from three vantage points: algorithms, users, and pedagogy, and contribute several novel solutions to the explainability problem.
Bridging between LegalRuleML and TPTP for Automated Normative Reasoning (extended version)
Venue: arXiv cs.AI 2022
Year: 2022

LegalRuleML is a comprehensive XML-based representation framework for modeling and exchanging normative rules. The TPTP input and output formats, on the other hand, are general-purpose standards for the interaction with automated reasoning systems. In this paper we provide a bridge between the two communities by (i) defining a logic-pluralistic normative reasoning language based on the TPTP format, (ii) providing a translation scheme between relevant fragments of LegalRuleML and this language, and (iii) proposing a flexible architecture for automated normative reasoning based on this translation. We exemplarily instantiate and demonstrate the approach with three different normative logics.
FBG-Based Online Learning and 3-D Shape Control of Unmodeled Continuum and Soft Robots in Unstructured Environments
Venue: arXiv cs.RO 2022
Year: 2022

In this paper, we present a novel and generic data-driven method to servo-control the 3-D shape of continuum and soft robots embedded with fiber Bragg grating (FBG) sensors. Developments of 3-D shape perception and control technologies are crucial for continuum robots to perform the tasks autonomously in surgical interventions. However, owing to the nonlinear properties of continuum robots, one main difficulty lies in the modeling of them, especially for soft robots with variable stiffness. To address this problem, we propose a versatile learning-based adaptive controller by leveraging FBG shape feedback that can online estimate the unknown model of continuum robot against unexpected disturbances and exhibit an adaptive behavior to the unmodeled system without priori data exploration. Based on a new composite adaptation algorithm, the asymptotic convergences of the closed-loop system with learning parameters have been proven by Lyapunov theory. To validate the proposed method, we present a comprehensive experimental study by using two continuum robots both integrated with multi-core FBGs, including a robotic-assisted colonoscope and multi-section extensible soft manipulators. The results demonstrate the feasibility, adaptability, and superiority of our controller in various unstructured environments as well as phantom experiments.
On finding short reconfiguration sequences between independent sets
Venue: arXiv cs.CC 2022
Year: 2022

Assume we are given a graph $G$, two independent sets $S$ and $T$ in $G$ of size $k \geq 1$, and a positive integer $\ell \geq 1$. The goal is to decide whether there exists a sequence $\langle I_0, I_1, ..., I_\ell \rangle$ of independent sets such that for all $j \in \{0,\ldots,\ell-1\}$ the set $I_j$ is an independent set of size $k$, $I_0 = S$, $I_\ell = T$, and $I_{j+1}$ is obtained from $I_j$ by a predetermined reconfiguration rule. We consider two reconfiguration rules. Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the Token Sliding Optimization (TSO) problem asks whether there exists a sequence of at most $\ell$ steps that transforms $S$ into $T$, where at each step we are allowed to slide one token from a vertex to an unoccupied neighboring vertex. In the Token Jumping Optimization (TJO) problem, at each step, we are allowed to jump one token from a vertex to any other unoccupied vertex of the graph. Both TSO and TJO are known to be fixed-parameter tractable when parameterized by $\ell$ on nowhere dense classes of graphs. In this work, we show that both problems are fixed-parameter tractable for parameter $k + \ell + d$ on $d$-degenerate graphs as well as for parameter $|M| + \ell + Δ$ on graphs having a modulator $M$ whose deletion leaves a graph of maximum degree $Δ$. We complement these result by showing that for parameter $\ell$ alone both problems become W[1]-hard already on $2$-degenerate graphs. Our positive result makes use of the notion of independence covering families introduced by Lokshtanov et al. Finally, we show that using such families one can obtain a simpler and unified algorithm for the standard Token Jumping Reachability problem parameterized by $k$ on both degenerate and nowhere dense classes of graphs.
Resource Allocation to Agents with Restrictions: Maximizing Likelihood with Minimum Compromise
Venue: arXiv cs.AI 2022
Year: 2022

Many scenarios where agents with restrictions compete for resources can be cast as maximum matching problems on bipartite graphs. Our focus is on resource allocation problems where agents may have restrictions that make them incompatible with some resources. We assume that a Principle chooses a maximum matching randomly so that each agent is matched to a resource with some probability. Agents would like to improve their chances of being matched by modifying their restrictions within certain limits. The Principle's goal is to advise an unsatisfied agent to relax its restrictions so that the total cost of relaxation is within a budget (chosen by the agent) and the increase in the probability of being assigned a resource is maximized. We establish hardness results for some variants of this budget-constrained maximization problem and present algorithmic results for other variants. We experimentally evaluate our methods on synthetic datasets as well as on two novel real-world datasets: a vacation activities dataset and a classrooms dataset.
Learning Obstacle-Avoiding Lattice Paths using Swarm Heuristics: Exploring the Bijection to Ordered Trees
Venue: arXiv cs.RO 2022
Year: 2022

Lattice paths are functional entities that model efficient navigation in discrete/grid maps. This paper presents a new scheme to generate collision-free lattice paths with utmost efficiency using the bijective property to rooted ordered trees, rendering a one-dimensional search problem. Our computational studies using ten state-of-the-art and relevant nature-inspired swarm heuristics in navigation scenarios with obstacles with convex and non-convex geometry show the practical feasibility and efficiency in rendering collision-free lattice paths. We believe our scheme may find use in devising fast algorithms for planning and combinatorial optimization in discrete maps.
Deep Reinforcement Learning for Online Latency Aware Workload Offloading in Mobile Edge Computing
Venue: arXiv cs.DC 2022
Year: 2022

Owing to the resource-constrained feature of Internet of Things (IoT) devices, offloading tasks from IoT devices to the nearby mobile edge computing (MEC) servers can not only save the energy of IoT devices but also reduce the response time of executing the tasks. However, offloading a task to the nearest MEC server may not be the optimal solution due to the limited computing resources of the MEC server. Thus, jointly optimizing the offloading decision and resource management is critical, but yet to be explored. Here, offloading decision refers to where to offload a task and resource management implies how much computing resource in an MEC server is allocated to a task. By considering the waiting time of a task in the communication and computing queues (which are ignored by most of the existing works) as well as tasks priorities, we propose the \ul{D}eep reinforcement l\ul{E}arning based offloading de\ul{C}ision and r\ul{E}source manageme\ul{NT} (DECENT) algorithm, which leverages the advantage actor critic method to optimize the offloading decision and computing resource allocation for each arriving task in real-time such that the cumulative weighted response time can be minimized. The performance of DECENT is demonstrated via different experiments.
SmartKex: Machine Learning Assisted SSH Keys Extraction From The Heap Dump
Venue: arXiv cs.CR 2022
Year: 2022

Digital forensics is the process of extracting, preserving, and documenting evidence in digital devices. A commonly used method in digital forensics is to extract data from the main memory of a digital device. However, the main challenge is identifying the important data to be extracted. Several pieces of crucial information reside in the main memory, like usernames, passwords, and cryptographic keys such as SSH session keys. In this paper, we propose SmartKex, a machine-learning assisted method to extract session keys from heap memory snapshots of an OpenSSH process. In addition, we release an openly available dataset and the corresponding toolchain for creating additional data. Finally, we compare SmartKex with naive brute-force methods and empirically show that SmartKex can extract the session keys with high accuracy and high throughput. With the provided resources, we intend to strengthen the research on the intersection between digital forensics, cybersecurity, and machine learning.
ErgoExplorer: Interactive Ergonomic Risk Assessment from Video Collections
Venue: arXiv cs.CV 2022
Year: 2022

Ergonomic risk assessment is now, due to an increased awareness, carried out more often than in the past. The conventional risk assessment evaluation, based on expert-assisted observation of the workplaces and manually filling in score tables, is still predominant. Data analysis is usually done with a focus on critical moments, although without the support of contextual information and changes over time. In this paper we introduce ErgoExplorer, a system for the interactive visual analysis of risk assessment data. In contrast to the current practice, we focus on data that span across multiple actions and multiple workers while keeping all contextual information. Data is automatically extracted from video streams. Based on carefully investigated analysis tasks, we introduce new views and their corresponding interactions. These views also incorporate domain-specific score tables to guarantee an easy adoption by domain experts. All views are integrated into ErgoExplorer, which relies on coordinated multiple views to facilitate analysis through interaction. ErgoExplorer makes it possible for the first time to examine complex relationships between risk assessments of individual body parts over long sessions that span multiple operations. The newly introduced approach supports analysis and exploration at several levels of detail, ranging from a general overview, down to inspecting individual frames in the video stream, if necessary. We illustrate the usefulness of the newly proposed approach applying it to several datasets.
TruVR: Trustworthy Cybersickness Detection using Explainable Machine Learning
Venue: arXiv cs.HC 2022
Year: 2022

Cybersickness can be characterized by nausea, vertigo, headache, eye strain, and other discomforts when using virtual reality (VR) systems. The previously reported machine learning (ML) and deep learning (DL) algorithms for detecting (classification) and predicting (regression) VR cybersickness use black-box models; thus, they lack explainability. Moreover, VR sensors generate a massive amount of data, resulting in complex and large models. Therefore, having inherent explainability in cybersickness detection models can significantly improve the model's trustworthiness and provide insight into why and how the ML/DL model arrived at a specific decision. To address this issue, we present three explainable machine learning (xML) models to detect and predict cybersickness: 1) explainable boosting machine (EBM), 2) decision tree (DT), and 3) logistic regression (LR). We evaluate xML-based models with publicly available physiological and gameplay datasets for cybersickness. The results show that the EBM can detect cybersickness with an accuracy of 99.75% and 94.10% for the physiological and gameplay datasets, respectively. On the other hand, while predicting the cybersickness, EBM resulted in a Root Mean Square Error (RMSE) of 0.071 for the physiological dataset and 0.27 for the gameplay dataset. Furthermore, the EBM-based global explanation reveals exposure length, rotation, and acceleration as key features causing cybersickness in the gameplay dataset. In contrast, galvanic skin responses and heart rate are most significant in the physiological dataset. Our results also suggest that EBM-based local explanation can identify cybersickness-causing factors for individual samples. We believe the proposed xML-based cybersickness detection method can help future researchers understand, analyze, and design simpler cybersickness detection and reduction models.
Modular Representations for Weak Disentanglement
Venue: arXiv cs.LG 2022
Year: 2022

The recently introduced weakly disentangled representations proposed to relax some constraints of the previous definitions of disentanglement, in exchange for more flexibility. However, at the moment, weak disentanglement can only be achieved by increasing the amount of supervision as the number of factors of variations of the data increase. In this paper, we introduce modular representations for weak disentanglement, a novel method that allows to keep the amount of supervised information constant with respect the number of generative factors. The experiments shows that models using modular representations can increase their performance with respect to previous work without the need of additional supervision.
Efficient query evaluation techniques over large amount of distributed linked data
Venue: arXiv cs.DB 2022
Year: 2022

As RDF becomes more widely established and the amount of linked data is rapidly increasing, the efficient querying of large amount of data becomes a significant challenge. In this paper, we propose a family of algorithms for querying large amount of linked data in a distributed manner. These query evaluation algorithms are independent of the way the data is stored, as well as of the particular implementation of the query evaluation. We then use the MapReduce paradigm to present a distributed implementation of these algorithms and experimentally evaluate them, although the algorithms could be straightforwardly translated into other distributed processing frameworks. We also investigate and propose multiple query decomposition approaches of Basic Graph Patterns (subclass of SPARQL queries) that are used to improve the overall performance of the distributed query answering. A deep analysis of the effectiveness of these decomposition algorithms is also provided.
On Faithfulness and Coherence of Language Explanations for Recommendation Systems
Venue: arXiv cs.IR 2022
Year: 2022

Reviews contain rich information about product characteristics and user interests and thus are commonly used to boost recommender system performance. Specifically, previous work show that jointly learning to perform review generation improves rating prediction performance. Meanwhile, these model-produced reviews serve as recommendation explanations, providing the user with insights on predicted ratings. However, while existing models could generate fluent, human-like reviews, it is unclear to what degree the reviews fully uncover the rationale behind the jointly predicted rating. In this work, we perform a series of evaluations that probes state-of-the-art models and their review generation component. We show that the generated explanations are brittle and need further evaluation before being taken as literal rationales for the estimated ratings.