OpenRaiser/Intern-Atlas huggingface dataset:
On the Relationship between Shy and Warded Datalog+/-
Venue: arXiv cs.LO 2022
Year: 2022

Datalog^E is the extension of Datalog with existential quantification. While its high expressive power, underpinned by a simple syntax and the support for full recursion, renders it particularly suitable for modern applications on knowledge graphs, query answering (QA) over such language is known to be undecidable in general. For this reason, different fragments have emerged, introducing syntactic limitations to Datalog^E that strike a balance between its expressive power and the computational complexity of QA, to achieve decidability. In this short paper, we focus on two promising tractable candidates, namely Shy and Warded Datalog+/-. Reacting to an explicit interest from the community, we shed light on the relationship between these fragments. Moreover, we carry out an experimental analysis of the systems implementing Shy and Warded, respectively DLV^E and Vadalog.
Stability Problems in Symbolic Integration
Venue: arXiv cs.SC 2022
Year: 2022

This paper aims to initialize a dynamical aspect of symbolic integration by studying stability problems in differential fields. We present some basic properties of stable elementary functions and D-finite power series that enable us to characterize three special families of stable elementary functions involving rational functions, logarithmic functions, and exponential functions. Some problems for future studies are proposed towards deeper dynamical studies in differential and difference algebra.
Omnifont Persian OCR System Using Primitives
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we introduce a model-based omnifont Persian OCR system. The system uses a set of 8 primitive elements as structural features for recognition. First, the scanned document is preprocessed. After normalizing the preprocessed image, text rows and sub-words are separated and then thinned. After recognition of dots in sub-words, strokes are extracted and primitive elements of each sub-word are recognized using the strokes. Finally, the primitives are compared with a predefined set of character identification vectors in order to identify sub-word characters. The separation and recognition steps of the system are concurrent, eliminating unavoidable errors of independent separation of letters. The system has been tested on documents with 14 standard Persian fonts in 6 sizes. The achieved precision is 97.06%.
Beyond Worst-Case Analysis for Root Isolation Algorithms
Venue: arXiv cs.CC 2022
Year: 2022

Isolating the real roots of univariate polynomials is a fundamental problem in symbolic computation and it is arguably one of the most important problems in computational mathematics. The problem has a long history decorated with numerous ingenious algorithms and furnishes an active area of research. However, the worst-case analysis of root-finding algorithms does not correlate with their practical performance. We develop a smoothed analysis framework for polynomials with integer coefficients to bridge the gap between the complexity estimates and the practical performance. In this setting, we derive that the expected bit complexity of DESCARTES solver to isolate the real roots of a polynomial, with coefficients uniformly distributed, is $\widetilde{\mathcal{O}}_B(d^2 + d τ)$, where $d$ is the degree of the polynomial and $τ$ the bitsize of the coefficients.
Measuring "Why" in Recommender Systems: a Comprehensive Survey on the Evaluation of Explainable Recommendation
Venue: arXiv cs.IR 2022
Year: 2022

Explainable recommendation has shown its great advantages for improving recommendation persuasiveness, user satisfaction, system transparency, among others. A fundamental problem of explainable recommendation is how to evaluate the explanations. In the past few years, various evaluation strategies have been proposed. However, they are scattered in different papers, and there lacks a systematic and detailed comparison between them. To bridge this gap, in this paper, we comprehensively review the previous work, and provide different taxonomies for them according to the evaluation perspectives and evaluation methods. Beyond summarizing the previous work, we also analyze the (dis)advantages of existing evaluation methods and provide a series of guidelines on how to select them. The contents of this survey are based on more than 100 papers from top-tier conferences like IJCAI, AAAI, TheWebConf, Recsys, UMAP, and IUI, and their complete summarization are presented at https://shimo.im/sheets/VKrpYTcwVH6KXgdy/MODOC/. With this survey, we finally aim to provide a clear and comprehensive review on the evaluation of explainable recommendation.
Semantic Communication Meets Edge Intelligence
Venue: arXiv cs.NI 2022
Year: 2022

The development of emerging applications, such as autonomous transportation systems, are expected to result in an explosive growth in mobile data traffic. As the available spectrum resource becomes more and more scarce, there is a growing need for a paradigm shift from Shannon's Classical Information Theory (CIT) to semantic communication (SemCom). Specifically, the former adopts a "transmit-before-understanding" approach while the latter leverages artificial intelligence (AI) techniques to "understand-before-transmit", thereby alleviating bandwidth pressure by reducing the amount of data to be exchanged without negating the semantic effectiveness of the transmitted symbols. However, the semantic extraction (SE) procedure incurs costly computation and storage overheads. In this article, we introduce an edge-driven training, maintenance, and execution of SE. We further investigate how edge intelligence can be enhanced with SemCom through improving the generalization capabilities of intelligent agents at lower computation overheads and reducing the communication overhead of information exchange. Finally, we present a case study involving semantic-aware resource optimization for the wireless powered Internet of Things (IoT).
Extracting Label-specific Key Input Features for Neural Code Intelligence Models
Venue: arXiv cs.SE 2022
Year: 2022

The code intelligence (CI) models are often black-box and do not offer any insights on the input features that they learn for making correct predictions. This opacity may lead to distrust in their prediction and hamper their wider adoption in safety-critical applications. In recent, the program reduction technique is widely being used to identify key input features in order to explain the prediction of CI models. The approach removes irrelevant parts from an input program and keeps the minimal snippets that a CI model needs to maintain its prediction. However, the state-of-the-art approaches mainly use a syntax-unaware program reduction technique that does not follow the syntax of programs, which adds significant overhead to the reduction of input programs and explainability of models. In this paper, we apply a syntax-guided program reduction technique that follows the syntax of input programs during reduction. Our experiments on multiple models across different types of input programs show that the syntax-guided program reduction technique significantly outperforms the syntax-unaware program reduction technique in reducing the size of input programs. Extracting key input features from reduced programs reveals that the syntax-guided reduced programs contain more label-specific key input features and are more vulnerable to adversarial transformation when renaming the key tokens in programs. These label-specific key input features may help to understand the reasoning of models' prediction from different perspectives and increase the trustworthiness to correct classification given by CI models.
PR-PL: A Novel Transfer Learning Framework with Prototypical Representation based Pairwise Learning for EEG-Based Emotion Recognition
Venue: arXiv cs.HC 2022
Year: 2022

Affective brain-computer interfaces based on electroencephalography (EEG) is an important branch in the field of affective computing. However, individual differences and noisy labels seriously limit the effectiveness and generalizability of EEG-based emotion recognition models. In this paper, we propose a novel transfer learning framework with Prototypical Representation based Pairwise Learning (PR-PL) to learn discriminative and generalized prototypical representations for emotion revealing across individuals and formulate emotion recognition as pairwise learning for alleviating the reliance on precise label information. Extensive experiments are conducted on two benchmark databases under four cross-validation evaluation protocols (cross-subject cross-session, cross-subject within-session, within-subject cross-session, and within-subject within-session). The experimental results demonstrate the superiority of the proposed PR-PL against the state-of-the-arts under all four evaluation protocols, which shows the effectiveness and generalizability of PR-PL in dealing with the ambiguity of EEG responses in affective studies. The source code is available at https://github.com/KAZABANA/PR-PL.
Mixing and Shifting: Exploiting Global and Local Dependencies in Vision MLPs
Venue: arXiv cs.CV 2022
Year: 2022

Token-mixing multi-layer perceptron (MLP) models have shown competitive performance in computer vision tasks with a simple architecture and relatively small computational cost. Their success in maintaining computation efficiency is mainly attributed to avoiding the use of self-attention that is often computationally heavy, yet this is at the expense of not being able to mix tokens both globally and locally. In this paper, to exploit both global and local dependencies without self-attention, we present Mix-Shift-MLP (MS-MLP) which makes the size of the local receptive field used for mixing increase with respect to the amount of spatial shifting. In addition to conventional mixing and shifting techniques, MS-MLP mixes both neighboring and distant tokens from fine- to coarse-grained levels and then gathers them via a shifting operation. This directly contributes to the interactions between global and local tokens. Being simple to implement, MS-MLP achieves competitive performance in multiple vision benchmarks. For example, an MS-MLP with 85 million parameters achieves 83.8% top-1 classification accuracy on ImageNet-1K. Moreover, by combining MS-MLP with state-of-the-art Vision Transformers such as the Swin Transformer, we show MS-MLP achieves further improvements on three different model scales, e.g., by 0.5% on ImageNet-1K classification with Swin-B. The code is available at: https://github.com/JegZheng/MS-MLP.
Context-Preserving Instance-Level Augmentation and Deformable Convolution Networks for SAR Ship Detection
Venue: arXiv cs.CV 2022
Year: 2022

Shape deformation of targets in SAR image due to random orientation and partial information loss caused by occlusion of the radar signal, is an essential challenge in SAR ship detection. In this paper, we propose a data augmentation method to train a deep network that is robust to partial information loss within the targets. Taking advantage of ground-truth annotations for bounding box and instance segmentation mask, we present a simple and effective pipeline to simulate information loss on targets in instance-level, while preserving contextual information. Furthermore, we adopt deformable convolutional network to adaptively extract shape-invariant deep features from geometrically translated targets. By learning sampling offset to the grid of standard convolution, the network can robustly extract the features from targets with shape variations for SAR ship detection. Experiments on the HRSID dataset including comparisons with other deep networks and augmentation methods, as well as ablation study, demonstrate the effectiveness of our proposed method.
Video2IMU: Realistic IMU features and signals from videos
Venue: arXiv cs.CV 2022
Year: 2022

Human Activity Recognition (HAR) from wearable sensor data identifies movements or activities in unconstrained environments. HAR is a challenging problem as it presents great variability across subjects. Obtaining large amounts of labelled data is not straightforward, since wearable sensor signals are not easy to label upon simple human inspection. In our work, we propose the use of neural networks for the generation of realistic signals and features using human activity monocular videos. We show how these generated features and signals can be utilized, instead of their real counterparts, to train HAR models that can recognize activities using signals obtained with wearable sensors. To prove the validity of our methods, we perform experiments on an activity recognition dataset created for the improvement of industrial work safety. We show that our model is able to realistically generate virtual sensor signals and features usable to train a HAR classifier with comparable performance as the one trained using real sensor data. Our results enable the use of available, labelled video data for training HAR models to classify signals from wearable sensors.
Ergodic Achievable Rate Analysis and Optimization of RIS-assisted Millimeter-Wave MIMO Communication Systems
Venue: arXiv cs.IT 2022
Year: 2022

Reconfigurable intelligent surfaces (RISs) have emerged as a prospective technology for next-generation wireless networks due to their potential in coverage and capacity enhancement. Previous works on achievable rate analysis of RIS-assisted communication systems have mainly focused on the rich-scattering environment where Rayleigh and Rician channel models can be applied. This work studies the ergodic achievable rate of RIS-assisted multiple-input multiple-output communication systems in millimeter-wave band with limited scattering under the Saleh-Valenzuela channel model. Firstly, we derive an upper bound of the ergodic achievable rate by means of majorization theory and Jensen's inequality. The upper bound shows that the ergodic achievable rate increases logarithmically with the number of antennas at the base station (BS) and user, the number of the reflection units at the RIS, and the eigenvalues of the steering matrices associated with the BS, user and RIS. Then, we aim to maximize the ergodic achievable rate by jointly optimizing the transmit covariance matrix at the BS and the reflection coefficients at the RIS. Specifically, the transmit covariance matrix is optimized by the water-filling algorithm and the reflection coefficients are optimized using the Riemannian conjugate gradient algorithm. Simulation results validate the effectiveness of the proposed optimization algorithms.
Hybrid Soft Robots Incorporating Soft and Stiff Elements
Venue: arXiv cs.RO 2022
Year: 2022

Soft robots are inherently compliant and have a strong potential to realize human-friendly and safe robots. Despite continued research highlighting the potential of soft robots, they remain largely confined to laboratory settings. In this work, inspired by spider monkeys' tails, we propose a hybrid soft robot (HSR) design. We detail the design objectives and methodology to improve the controllable stiffness range and achieve independent stiffness and shape control. We extend the curve parametric approach to We experimentally demonstrate that the proposed HSR has about a 100% stiffness range increase than a previous soft robot design with identical physical dimensions. In addition, we empirically map HSR's bending shape-pressure-stiffness and present an application example - a soft robotic gripper - to demonstrate the decoupled nature of stiffness and shape variations. Experimental results show that proposed HSR can be successfully used in applications where independent stiffness and shape control is desired.
Modeling Population Human Mobility with Dynamic Mode Decomposition
Venue: arXiv cs.SI 2022
Year: 2022

Human mobility research concerns spatiotemporal individual and population movement. Accurate modeling and prediction of human mobility can provide opportunities to monitor, manage and optimize human movement for improved social-economic benefit. In this paper, we adopt the dynamic mode decomposition algorithm to model population human mobility using visitor flow data between different states in the United States from 2019 to 2021 [1]. We train multiple DMD models with different low rank structures, and evaluate their modeling accuracy and predictability on novel testing data.
Routing Schemes and Distance Oracles in the Hybrid Model
Venue: arXiv cs.DC 2022
Year: 2022

The $\mathsf{HYBRID}$ model was introduced as a means for theoretical study of distributed networks that use various communication modes. Conceptually, it is a synchronous message passing model with a local communication mode, where in each round each node can send large messages to all its neighbors in a local network (a graph), and a global communication mode, where each node is allotted limited (polylogarithmic) bandwidth per round which it can use to communicate with any node in the network. Prior work has often focused on shortest paths problems in the local network, as their global nature makes these an interesting case study how combining communication modes in the $\mathsf{HYBRID}$ model can overcome the individual lower bounds of either mode. In this work we consider a similar problem, namely computation of distance oracles and routing schemes. In the former, all nodes have to compute local tables, which allows them to look up the distance (estimates) to any target node in the local network when provided with the label of the target. In the latter, it suffices that nodes give the next node on an (approximately) shortest path to the target. Our goal is to compute these local tables as fast as possible with labels as small as possible. We show that this can be done exactly in $\widetilde O(n^{1/3})$ communication rounds and labels of size $Θ(n^{2/3})$ bits. For constant stretch approximations we achieve labels of size $O(\log n)$ in the same time. Further, as our main technical contribution, we provide computational lower bounds for a variety of problem parameters. For instance, we show that computing solutions with stretch below a certain constant takes $\widetilde Ω(n^{1/3})$ rounds even for labels of size $O(n^{2/3})$.
Short-lived Datacenter
Venue: arXiv cs.DC 2022
Year: 2022

Serverless platforms have attracted attention due to their promise of elasticity, low cost, and fast deployment. Instead of using a fixed virtual machine (VM) infrastructure, which can incur considerable costs to operate and run, serverless platforms support short computations, triggered on demand, with cost proportional to fine-grain function execution time. However, serverless platforms offer a restricted execution environment. For example, functions have limited execution times, limited resources, and no support for networking between functions. In this paper, we explore what it takes to treat serverless platforms as short-lived, general purpose data-centers which can execute unmodified existing applications. As a first step in this quest, we have developed Boxer, a system providing an execution environment on top of existing functions-as-a-service platforms that allows users to seamlessly migrate conventional VM-based cloud services to serverless platforms. Boxer allows generic applications to benefit from the fine-grain elasticity of serverless platforms without having to modify applications to adopt a restrictive event-triggered programming model or orchestrate auxiliary systems for data communication. We implement Boxer on top of AWS Lambda and extend it to transparently provide standard network interfaces. We describe its implementation and demonstrate how it can be used to run off-the-shelf cloud applications with a degree of fine-grained elasticity not available on traditional VM-based platforms.
Convolutional Neural Network with Convolutional Block Attention Module for Finger Vein Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Convolutional neural networks have become a popular research in the field of finger vein recognition because of their powerful image feature representation. However, most researchers focus on improving the performance of the network by increasing the CNN depth and width, which often requires high computational effort. Moreover, we can notice that not only the importance of pixels in different channels is different, but also the importance of pixels in different positions of the same channel is different. To reduce the computational effort and to take into account the different importance of pixels, we propose a lightweight convolutional neural network with a convolutional block attention module (CBAM) for finger vein recognition, which can achieve a more accurate capture of visual structures through an attention mechanism. First, image sequences are fed into a lightweight convolutional neural network we designed to improve visual features. Afterwards, it learns to assign feature weights in an adaptive manner with the help of a convolutional block attention module. The experiments are carried out on two publicly available databases and the results demonstrate that the proposed method achieves a stable, highly accurate, and robust performance in multimodal finger recognition.
Can Machines Help Us Answering Question 16 in Datasheets, and In Turn Reflecting on Inappropriate Content?
Venue: arXiv cs.AI 2022
Year: 2022

Large datasets underlying much of current machine learning raise serious issues concerning inappropriate content such as offensive, insulting, threatening, or might otherwise cause anxiety. This calls for increased dataset documentation, e.g., using datasheets. They, among other topics, encourage to reflect on the composition of the datasets. So far, this documentation, however, is done manually and therefore can be tedious and error-prone, especially for large image datasets. Here we ask the arguably "circular" question of whether a machine can help us reflect on inappropriate content, answering Question 16 in Datasheets. To this end, we propose to use the information stored in pre-trained transformer models to assist us in the documentation process. Specifically, prompt-tuning based on a dataset of socio-moral values steers CLIP to identify potentially inappropriate content, therefore reducing human labor. We then document the inappropriate images found using word clouds, based on captions generated using a vision-language model. The documentations of two popular, large-scale computer vision datasets -- ImageNet and OpenImages -- produced this way suggest that machines can indeed help dataset creators to answer Question 16 on inappropriate image content.
Liveness and Latency of Byzantine State-Machine Replication (Extended Version)
Venue: arXiv cs.DC 2022
Year: 2022

Byzantine state-machine replication (SMR) ensures the consistency of replicated state in the presence of malicious replicas and lies at the heart of the modern blockchain technology. Byzantine SMR protocols often guarantee safety under all circumstances and liveness only under synchrony. However, guaranteeing liveness even under this assumption is nontrivial. So far we have lacked systematic ways of incorporating liveness mechanisms into Byzantine SMR protocols, which often led to subtle bugs. To close this gap, we introduce a modular framework to facilitate the design of provably live and efficient Byzantine SMR protocols. Our framework relies on a view abstraction generated by a special SMR synchronizer primitive to drive the agreement on command ordering. We present a simple formal specification of an SMR synchronizer and its bounded-space implementation under partial synchrony. We also apply our specification to prove liveness and analyze the latency of three Byzantine SMR protocols via a uniform methodology. In particular, one of these results yields what we believe is the first rigorous liveness proof for the algorithmic core of the seminal PBFT protocol.