OpenRaiser/Intern-Atlas huggingface dataset:
Capturing Homomorphism-Closed Decidable Queries with Existential Rules
Venue: arXiv cs.LO 2021
Year: 2021

Existential rules are a very popular ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward that existential rule queries exhibiting chase termination are decidable and can only recognize properties that are preserved under homomorphisms. In this paper, we show the converse: every decidable query that is closed under homomorphism can be expressed by an existential rule set for which the standard chase universally terminates. Membership in this fragment is not decidable, but we show via a diagonalisation argument that this is unavoidable.
Progressive Deep Video Dehazing without Explicit Alignment Estimation
Venue: arXiv cs.CV 2021
Year: 2021

To solve the issue of video dehazing, there are two main tasks to attain: how to align adjacent frames to the reference frame; how to restore the reference frame. Some papers adopt explicit approaches (e.g., the Markov random field, optical flow, deformable convolution, 3D convolution) to align neighboring frames with the reference frame in feature space or image space, they then use various restoration methods to achieve the final dehazing results. In this paper, we propose a progressive alignment and restoration method for video dehazing. The alignment process aligns consecutive neighboring frames stage by stage without using the optical flow estimation. The restoration process is not only implemented under the alignment process but also uses a refinement network to improve the dehazing performance of the whole network. The proposed networks include four fusion networks and one refinement network. To decrease the parameters of networks, three fusion networks in the first fusion stage share the same parameters. Extensive experiments demonstrate that the proposed video dehazing method achieves outstanding performance against the-state-of-art methods.
Park4U Mate: Context-Aware Digital Assistant for Personalized Autonomous Parking
Venue: arXiv cs.HC 2021
Year: 2021

People park their vehicle depending on interior and exterior contexts. They do it naturally, even unconsciously. For instance, with a baby seat on the rear, the driver might leave more space on one side to be able to get the baby out easily; or when grocery shopping, s/he may position the vehicle to remain the trunk accessible. Autonomous vehicles are becoming technically effective at driving from A to B and parking in a proper spot, with a default way. However, in order to satisfy users' expectations and to become trustworthy, they will also need to park or make a temporary stop, appropriate to the given situation. In addition, users want to understand better the capabilities of their driving assistance features, such as automated parking systems. A voice-based interface can help with this and even ease the adoption of these features. Therefore, we developed a voice-based in-car assistant (Park4U Mate), that is aware of interior and exterior contexts (thanks to a variety of sensors), and that is able to park autonomously in a smart way (with a constraints minimization strategy). The solution was demonstrated to thirty-five users in test-drives and their feedback was collected on the system's decision-making capability as well as on the human-machine-interaction. The results show that: (1) the proposed optimization algorithm is efficient at deciding the best parking strategy; hence, autonomous vehicles can adopt it; (2) a voice-based digital assistant for autonomous parking is perceived as a clear and effective interaction method. However, the interaction speed remained the most important criterion for users. In addition, they clearly wish not to be limited on only voice-interaction, to use the automated parking function and rather appreciate a multi-modal interaction.
MODRL/D-EL: Multiobjective Deep Reinforcement Learning with Evolutionary Learning for Multiobjective Optimization
Venue: arXiv cs.NE 2021
Year: 2021

Learning-based heuristics for solving combinatorial optimization problems has recently attracted much academic attention. While most of the existing works only consider the single objective problem with simple constraints, many real-world problems have the multiobjective perspective and contain a rich set of constraints. This paper proposes a multiobjective deep reinforcement learning with evolutionary learning algorithm for a typical complex problem called the multiobjective vehicle routing problem with time windows (MO-VRPTW). In the proposed algorithm, the decomposition strategy is applied to generate subproblems for a set of attention models. The comprehensive context information is introduced to further enhance the attention models. The evolutionary learning is also employed to fine-tune the parameters of the models. The experimental results on MO-VRPTW instances demonstrate the superiority of the proposed algorithm over other learning-based and iterative-based approaches.
In-Bed Person Monitoring Using Thermal Infrared Sensors
Venue: arXiv cs.HC 2021
Year: 2021

The world is expecting an aging population and shortage of healthcare professionals. This poses the problem of providing a safe and dignified life for the elderly. Technological solutions involving cameras can contribute to safety, comfort and efficient emergency responses, but they are invasive of privacy. We use 'Griddy', a prototype with a Panasonic Grid-EYE, a low-resolution infrared thermopile array sensor, which offers more privacy. Mounted over a bed, it can determine if the user is on the bed or not without human interaction. For this purpose, two datasets were captured, one (480 images) under constant conditions, and a second one (200 images) under different variations such as use of a duvet, sleeping with a pet, or increased room temperature. We test three machine learning algorithms: Support Vector Machines (SVM), k-Nearest Neighbors (k-NN) and Neural Network (NN). With 10-fold cross validation, the highest accuracy in the main dataset is for both SVM and k-NN (99%). The results with variable data show a lower reliability under certain circumstances, highlighting the need of extra work to meet the challenge of variations in the environment.
Decentralized Multi-Agent Reinforcement Learning for Task Offloading Under Uncertainty
Venue: arXiv cs.LG 2021
Year: 2021

Multi-Agent Reinforcement Learning (MARL) is a challenging subarea of Reinforcement Learning due to the non-stationarity of the environments and the large dimensionality of the combined action space. Deep MARL algorithms have been applied to solve different task offloading problems. However, in real-world applications, information required by the agents (i.e. rewards and states) are subject to noise and alterations. The stability and the robustness of deep MARL to practical challenges is still an open research problem. In this work, we apply state-of-the art MARL algorithms to solve task offloading with reward uncertainty. We show that perturbations in the reward signal can induce decrease in the performance compared to learning with perfect rewards. We expect this paper to stimulate more research in studying and addressing the practical challenges of deploying deep MARL solutions in wireless communications systems.
The Law of Large Documents: Understanding the Structure of Legal Contracts Using Visual Cues
Venue: arXiv cs.CL 2021
Year: 2021

Large, pre-trained transformer models like BERT have achieved state-of-the-art results on document understanding tasks, but most implementations can only consider 512 tokens at a time. For many real-world applications, documents can be much longer, and the segmentation strategies typically used on longer documents miss out on document structure and contextual information, hurting their results on downstream tasks. In our work on legal agreements, we find that visual cues such as layout, style, and placement of text in a document are strong features that are crucial to achieving an acceptable level of accuracy on long documents. We measure the impact of incorporating such visual cues, obtained via computer vision methods, on the accuracy of document understanding tasks including document segmentation, entity extraction, and attribute classification. Our method of segmenting documents based on structural metadata out-performs existing methods on four long-document understanding tasks as measured on the Contract Understanding Atticus Dataset.
CoCo: Online Mixed-Integer Control via Supervised Learning
Venue: arXiv cs.RO 2021
Year: 2021

Many robotics problems, from robot motion planning to object manipulation, can be modeled as mixed-integer convex programs (MICPs). However, state-of-the-art algorithms are still unable to solve MICPs for control problems quickly enough for online use and existing heuristics can typically only find suboptimal solutions that might degrade robot performance. In this work, we turn to data-driven methods and present the Combinatorial Offline, Convex Online (CoCo) algorithm for quickly finding high quality solutions for MICPs. CoCo consists of a two-stage approach. In the offline phase, we train a neural network classifier that maps the problem parameters to a (logical strategy), which we define as the discrete arguments and relaxed big-M constraints associated with the optimal solution for that problem. Online, the classifier is applied to select a candidate logical strategy given new problem parameters; applying this logical strategy allows us to solve the original MICP as a convex optimization problem. We show through numerical experiments how CoCo finds near optimal solutions to MICPs arising in robot planning and control with 1 to 2 orders of magnitude solution speedup compared to other data-driven approaches and solvers.
Declarative Machine Learning Systems
Venue: arXiv cs.LG 2021
Year: 2021

In the last years machine learning (ML) has moved from a academic endeavor to a pervasive technology adopted in almost every aspect of computing. ML-powered products are now embedded in our digital lives: from recommendations of what to watch, to divining our search intent, to powering virtual assistants in consumer and enterprise settings. Recent successes in applying ML in natural sciences revealed that ML can be used to tackle some of the hardest real-world problems humanity faces today. For these reasons ML has become central in the strategy of tech companies and has gathered even more attention from academia than ever before. Despite these successes, what we have witnessed so far is just the beginning. Right now the people training and using ML models are expert developers working within large organizations, but we believe the next wave of ML systems will allow a larger amount of people, potentially without coding skills, to perform the same tasks. These new ML systems will not require users to fully understand all the details of how models are trained and utilized for obtaining predictions. Declarative interfaces are well suited for this goal, by hiding complexity and favouring separation of interests, and can lead to increased productivity. We worked on such abstract interfaces by developing two declarative ML systems, Overton and Ludwig, that require users to declare only their data schema (names and types of inputs) and tasks rather then writing low level ML code. In this article we will describe how ML systems are currently structured, highlight important factors for their success and adoption, what are the issues current ML systems are facing and how the systems we developed addressed them. Finally we will talk about learnings from the development of ML systems throughout the years and how we believe the next generation of ML systems will look like.
Reliability and User-Plane Latency Analysis of mmWave Massive MIMO for Grant-Free URLLC Applications
Venue: arXiv cs.IT 2021
Year: 2021

5G cellular networks are designed to support a new range of applications not supported by previous standards. Among these, ultra-reliable low-latency communication (URLLC) applications are arguably the most challenging. URLLC service requires the user equipment (UE) to be able to transmit its data under strict latency constraints with high reliability. To address these requirements, new technologies, such as mini-slots, semi-persistent scheduling and grant-free access were introduced in 5G standards. In this work, we formulate a spatiotemporal mathematical model to evaluate the user-plane latency and reliability performance of millimetre wave (mmWave) massive multiple-input multiple-output (MIMO) URLLC with reactive and K-repetition hybrid automatic repeat request (HARQ) protocols. We derive closed-form approximate expressions for the latent access failure probability and validate them using numerical simulations. The results show that, under certain conditions, mmWave massive MIMO can reduce the failure probability by a factor of 32. Moreover, we identify that beyond a certain number of antennas there is no significant improvement in reliability. Finally, we conclude that mmWave massive MIMO alone is not enough to provide the performance guarantees required by the most stringent URLLC applications.
Assessing Support for Industry Standards in Reference Medical Software Architectures
Venue: arXiv cs.SE 2021
Year: 2021

Industrial standards for developing medical device software provide requirements that conforming devices must meet. A number of reference software architectures have been proposed to develop such software. The ISO/IEC 25010:2011 family of standards provides a comprehensive software product quality model, including characteristics that are highly desirable in medical devices. Furthermore, frameworks like 4+1 Views provide a robust framework to develop the software architecture or high level design for any software, including for medical devices. However, the alignment between industrial standards and reference architectures for medical device software, on one hand, and ISO/IEC 25010:2011 and 4+1 Views, on the other, is not well understood. This paper aims to explore how ISO/IEC 25010:2011 and 4+1 Views are supported by current standards, namely ISO 13485:2016, ISO 14971:2012, IEC 62304:2006 and IEC 62366:2015, and current reference architectures for medical device software. We classified requirements from medical devices standards into qualities from ISO/IEC 25010:2011 and architectural views from 4+1 Views. A systematic literature review (SLR) method was followed to review current references software architectures and a mapping of their support for the identified ISO/IEC 25010:2011 qualities in the previous step was carried out. Our results show that ISO/IEC 25010:2011 qualities like functional suitability, portability, maintainability, usability, security, reliability and compatibility are highly emphasised in medical device standards. Furthermore, we show that current reference architectures only partially support these qualities. This paper can help medical device developers identify focus areas for developing standards-compliant software. A wider study involving under-development medical devices can help improve the accuracy of our findings in the future.
Co-Teaching: An Ark to Unsupervised Stereo Matching
Venue: arXiv cs.CV 2021
Year: 2021

Stereo matching is a key component of autonomous driving perception. Recent unsupervised stereo matching approaches have received adequate attention due to their advantage of not requiring disparity ground truth. These approaches, however, perform poorly near occlusions. To overcome this drawback, in this paper, we propose CoT-Stereo, a novel unsupervised stereo matching approach. Specifically, we adopt a co-teaching framework where two networks interactively teach each other about the occlusions in an unsupervised fashion, which greatly improves the robustness of unsupervised stereo matching. Extensive experiments on the KITTI Stereo benchmarks demonstrate the superior performance of CoT-Stereo over all other state-of-the-art unsupervised stereo matching approaches in terms of both accuracy and speed. Our project webpage is https://sites.google.com/view/cot-stereo.
M2Lens: Visualizing and Explaining Multimodal Models for Sentiment Analysis
Venue: arXiv cs.LG 2021
Year: 2021

Multimodal sentiment analysis aims to recognize people's attitudes from multiple communication channels such as verbal content (i.e., text), voice, and facial expressions. It has become a vibrant and important research topic in natural language processing. Much research focuses on modeling the complex intra- and inter-modal interactions between different communication channels. However, current multimodal models with strong performance are often deep-learning-based techniques and work like black boxes. It is not clear how models utilize multimodal information for sentiment predictions. Despite recent advances in techniques for enhancing the explainability of machine learning models, they often target unimodal scenarios (e.g., images, sentences), and little research has been done on explaining multimodal models. In this paper, we present an interactive visual analytics system, M2Lens, to visualize and explain multimodal models for sentiment analysis. M2Lens provides explanations on intra- and inter-modal interactions at the global, subset, and local levels. Specifically, it summarizes the influence of three typical interaction types (i.e., dominance, complement, and conflict) on the model predictions. Moreover, M2Lens identifies frequent and influential multimodal features and supports the multi-faceted exploration of model behaviors from language, acoustic, and visual modalities. Through two case studies and expert interviews, we demonstrate our system can help users gain deep insights into the multimodal models for sentiment analysis.
Throughput Maximization of UAV Networks
Venue: arXiv cs.DC 2021
Year: 2021

In this paper we study the deployment of multiple unmanned aerial vehicles (UAVs) to form a temporal UAV network for the provisioning of emergent communications to affected people in a disaster zone, where each UAV is equipped with a lightweight base station device and thus can act as an aerial base station for users. Unlike most existing studies that assumed that a UAV can serve all users in its communication range, we observe that both computation and communication capabilities of a single lightweight UAV are very limited, due to various constraints on its size, weight, and power supply. Thus, a single UAV can only provide communication services to a limited number of users. We study a novel problem of deploying $K$ UAVs in the top of a disaster area such that the sum of the data rates of users served by the UAVs is maximized, subject to that (i) the number of users served by each UAV is no greater than its service capacity; and (ii) the communication network induced by the $K$ UAVs is connected. We then propose a $\frac{1-1/e}{\lfloor \sqrt{K} \rfloor}$-approximation algorithm for the problem, improving the current best result of the problem by five times (the best approximation ratio so far is $\frac{1-1/e}{5( \sqrt{K} +1)}$), where $e$ is the base of the natural logarithm. We finally evaluate the algorithm performance via simulation experiments. Experimental results show that the proposed algorithm is very promising. Especially, the solution delivered by the proposed algorithm is up to 12% better than those by existing algorithms.
On the Kernel and Related Problems in Interval Digraphs
Venue: arXiv cs.DM 2021
Year: 2021

Given a digraph $G$, a set $X\subseteq V(G)$ is said to be absorbing set (resp. dominating set) if every vertex in the graph is either in $X$ or is an in-neighbour (resp. out-neighbour) of a vertex in $X$. A set $S\subseteq V(G)$ is said to be an independent set if no two vertices in $S$ are adjacent in $G$. A kernel (resp. solution) of $G$ is an independent and absorbing (resp. dominating) set in $G$. We explore the algorithmic complexity of these problems in the well known class of interval digraphs. A digraph $G$ is an interval digraph if a pair of intervals $(S_u,T_u)$ can be assigned to each vertex $u$ of $G$ such that $(u,v)\in E(G)$ if and only if $S_u\cap T_v\neq\emptyset$. Many different subclasses of interval digraphs have been defined and studied in the literature by restricting the kinds of pairs of intervals that can be assigned to the vertices. We observe that several of these classes, like interval catch digraphs, interval nest digraphs, adjusted interval digraphs and chronological interval digraphs, are subclasses of the more general class of reflexive interval digraphs -- which arise when we require that the two intervals assigned to a vertex have to intersect. We show that all the problems mentioned above are efficiently solvable, in most of the cases even linear-time solvable, in the class of reflexive interval digraphs, but are APX-hard on even the very restricted class of interval digraphs called point-point digraphs, where the two intervals assigned to each vertex are required to be degenerate, i.e. they consist of a single point each. The results we obtain improve and generalize several existing algorithms and structural results for subclasses of reflexive interval digraphs.
Anonymous Blockchain-based System for Consortium
Venue: arXiv cs.CR 2021
Year: 2021

Blockchain brings various advantages to online transactions. However, the total transparency of these transactions may leakage users' sensitive information. Requirements on both cooperation and anonymity for companies/organizations become necessary. In this paper, we propose a Multi-center Anonymous Blockchain-based (MAB) system, with joint management for the consortium and privacy protection for the participants. To achieve that, we formalize the syntax used by the MAB system and present a general construction based on a modular design. By applying cryptographic primitives to each module, we instantiate our scheme with anonymity and decentralization. Furthermore, we carry out a comprehensive formal analysis of the proposed solution. The results demonstrate our constructed scheme is secure and efficient.
Anti Tai Mapping for Unordered Labeled Trees
Venue: arXiv cs.DS 2021
Year: 2021

The well-studied Tai mapping between two rooted labeled trees $T_1(V_1, E_1)$ and $T_2(V_2, E_2)$ defines a one-to-one mapping between nodes in $T_1$ and $T_2$ that preserves ancestor relationship. For unordered trees the problem of finding a maximum-weight Tai mapping is known to be NP-complete. In this work, we define an anti Tai mapping $M\subseteq V_1\times V_2$ as a binary relation between two unordered labeled trees such that any two $(x,y), (x', y')\in M$ violate ancestor relationship and thus cannot be part of the same Tai mapping, i.e. $(x\le x' \iff y\not \le y') \vee (x'\le x \iff y'\not \le y)$, given an ancestor order $x<x'$ meaning that $x$ is an ancestor of $x'$. Finding a maximum-weight anti Tai mapping arises in the cutting plane method for solving the maximum-weight Tai mapping problem via integer programming. We give an efficient polynomial-time algorithm for finding a maximum-weight anti Tai mapping for the case when one of the two trees is a path and further show how to extend this result in order to provide a polynomially computable lower bound on the optimal anti Tai mapping for two unordered labeled trees. The latter result stems from the special class of anti Tai mapping defined by the more restricted condition $x\sim x' \iff y\not\sim y'$, where $\sim$ denotes that two nodes belong to the same root-to-leaf path. For this class, we give an efficient algorithm that solves the problem directly on two unordered trees in $O(|V_1|^2|V_2|^2)$.