OpenRaiser/Intern-Atlas huggingface dataset:
Data Provenance via Differential Auditing
Venue: arXiv cs.CR 2022
Year: 2022

Auditing Data Provenance (ADP), i.e., auditing if a certain piece of data has been used to train a machine learning model, is an important problem in data provenance. The feasibility of the task has been demonstrated by existing auditing techniques, e.g., shadow auditing methods, under certain conditions such as the availability of label information and the knowledge of training protocols for the target model. Unfortunately, both of these conditions are often unavailable in real applications. In this paper, we introduce Data Provenance via Differential Auditing (DPDA), a practical framework for auditing data provenance with a different approach based on statistically significant differentials, i.e., after carefully designed transformation, perturbed input data from the target model's training set would result in much more drastic changes in the output than those from the model's non-training set. This framework allows auditors to distinguish training data from non-training ones without the need of training any shadow models with the help of labeled output data. Furthermore, we propose two effective auditing function implementations, an additive one and a multiplicative one. We report evaluations on real-world data sets demonstrating the effectiveness of our proposed auditing technique.
Algorithm for Finding an Exact Maximum Distance in E2 with Oexp(N) Complexity: Analysis and Experimental Results
Venue: arXiv cs.CG 2022
Year: 2022

This paper describes a novel and fast, simple and robust algorithm with O(N) expected complexity which enables to decrease run time needed to find the maximum distance of two points in E2. It can be easily modified for the E3 case in general. The proposed algorithm has been evaluated experimentally on larger different datasets in order to verify it and prove expected properties of it. Experiments proved the advantages of the proposed algorithm over the standard algorithms based on the Brute force, convex hull or convex hull diameters approaches. The proposed algorithm gives a significant speed-up to applications, when medium and large data sets are processed. It is over 10 000 times faster than the standard Brute force algorithm for 10 mil. points randomly distributed points in E2 and over 4 times faster than convex hull diameter computation. The speed-up of the proposed algorithm grows with the number of points processed.
Learning to Deceive in Multi-Agent Hidden Role Games
Venue: arXiv cs.MA 2022
Year: 2022

Deception is prevalent in human social settings. However, studies into the effect of deception on reinforcement learning algorithms have been limited to simplistic settings, restricting their applicability to complex real-world problems. This paper addresses this by introducing a new mixed competitive-cooperative multi-agent reinforcement learning (MARL) environment inspired by popular role-based deception games such as Werewolf, Avalon, and Among Us. The environment's unique challenge lies in the necessity to cooperate with other agents despite not knowing if they are friend or foe. Furthermore, we introduce a model of deception, which we call Bayesian belief manipulation (BBM) and demonstrate its effectiveness at deceiving other agents in this environment while also increasing the deceiving agent's performance.
The Approximate Degree of DNF and CNF Formulas
Venue: arXiv cs.CC 2022
Year: 2022

The approximate degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that approximates $f$ pointwise: $|f(x)-p(x)|\leq1/3$ for all $x\in\{0,1\}^n.$ For every $δ>0,$ we construct CNF and DNF formulas of polynomial size with approximate degree $Ω(n^{1-δ}),$ essentially matching the trivial upper bound of $n.$ This improves polynomially on previous lower bounds and fully resolves the approximate degree of constant-depth circuits ($\text{AC}^0$), a question that has seen extensive research over the past 10 years. Previously, an $Ω(n^{1-δ})$ lower bound was known only for $\text{AC}^0$ circuits of depth that grows with $1/δ$ (Bun and Thaler, FOCS 2017). Moreover, our CNF and DNF formulas are the simplest possible in that they have constant width. Our result holds even for one-sided approximation, and has the following further consequences. (i) We essentially settle the communication complexity of $\text{AC}^0$ circuits in the bounded-error quantum model, $k$-party number-on-the-forehead randomized model, and $k$-party number-on-the-forehead nondeterministic model: we prove that for every $δ>0$, these models require $Ω(n^{1-δ})$, $Ω(n/4^kk^2)^{1-δ}$, and $Ω(n/4^kk^2)^{1-δ}$, respectively, bits of communication even for polynomial-size constant-width CNF formulas. (ii) In particular, we show that the multiparty communication class $\text{coNP}_k$ can be separated essentially optimally from $\text{NP}_k$ and $\text{BPP}_k$ by a particularly simple function, a polynomial-size constant-width CNF. (iii) We give an essentially tight separation, of $O(1)$ versus $Ω(n^{1-δ})$, for the one-sided versus two-sided approximate degree of a function; and $O(1)$ versus $Ω(n^{1-δ})$ for the one-sided approximate degree of a function $f$ versus its negation $\neg f$.
ProBoost: a Boosting Method for Probabilistic Classifiers
Venue: arXiv cs.LG 2022
Year: 2022

ProBoost, a new boosting algorithm for probabilistic classifiers, is proposed in this work. This algorithm uses the epistemic uncertainty of each training sample to determine the most challenging/uncertain ones; the relevance of these samples is then increased for the next weak learner, producing a sequence that progressively focuses on the samples found to have the highest uncertainty. In the end, the weak learners' outputs are combined into a weighted ensemble of classifiers. Three methods are proposed to manipulate the training set: undersampling, oversampling, and weighting the training samples according to the uncertainty estimated by the weak learners. Furthermore, two approaches are studied regarding the ensemble combination. The weak learner herein considered is a standard convolutional neural network, and the probabilistic models underlying the uncertainty estimation use either variational inference or Monte Carlo dropout. The experimental evaluation carried out on MNIST benchmark datasets shows that ProBoost yields a significant performance improvement. The results are further highlighted by assessing the relative achievable improvement, a metric proposed in this work, which shows that a model with only four weak learners leads to an improvement exceeding 12% in this metric (for either accuracy, sensitivity, or specificity), in comparison to the model learned without ProBoost.
IoT Book Bot
Venue: arXiv cs.HC 2022
Year: 2022

In order to ease the process of library management many technologies have been adopted but most of them focus on inventory management. There has hardly been any progress of automation in the field of issuing and returning books to the library on time. In colleges and schools, hostellers often forget to timely return the issued books back to the library. To solve the above issue and to ensure timely submission of the issued books, this work develops a Book-Bot which solves these complexities. The bot can commute from point A to point B, scan and verify QR Codes and Barcodes. The bot will have a certain payload capacity for carrying books. The QR code and Barcode scanning will be enabled by a Pi Camera, OpenCV and Raspberry Pi, thus making the exchange of books safe and secure. The odometry maneuvers of the bot will be controlled manually via a Blynk App. This paper focuses on how human intervention can be reduced and automates the issue part of library management system with the help of a bot.
Exposure-Aware Recommendation using Contextual Bandits
Venue: arXiv cs.IR 2022
Year: 2022

Exposure bias is a well-known issue in recommender systems where items and suppliers are not equally represented in the recommendation results. This is especially problematic when bias is amplified over time as a few items (e.g., popular ones) are repeatedly over-represented in recommendation lists and users' interactions with those items will amplify bias towards those items over time resulting in a feedback loop. This issue has been extensively studied in the literature on model-based or neighborhood-based recommendation algorithms, but less work has been done on online recommendation models, such as those based on top-K contextual bandits, where recommendation models are dynamically updated with ongoing user feedback. In this paper, we study exposure bias in a class of well-known contextual bandit algorithms known as Linear Cascading Bandits. We analyze these algorithms on their ability to handle exposure bias and provide a fair representation for items in the recommendation results. Our analysis reveals that these algorithms tend to amplify exposure disparity among items over time. In particular, we observe that these algorithms do not properly adapt to the feedback provided by the users and frequently recommend certain items even when those items are not selected by users. To mitigate this bias, we propose an Exposure-Aware (EA) reward model that updates the model parameters based on two factors: 1) user feedback (i.e., clicked or not), and 2) position of the item in the recommendation list. This way, the proposed model controls the utility assigned to items based on their exposure in the recommendation list. Extensive experiments on two real-world datasets using three contextual bandit algorithms show that the proposed reward model reduces exposure bias amplification in long run while maintaining the recommendation accuracy.
SFS: Smart OS Scheduling for Serverless Functions
Venue: arXiv cs.OS 2022
Year: 2022

Serverless computing enables a new way of building and scaling cloud applications by allowing developers to write fine-grained serverless or cloud functions. The execution duration of a cloud function is typically short-ranging from a few milliseconds to hundreds of seconds. However, due to resource contentions caused by public clouds' deep consolidation, the function execution duration may get significantly prolonged and fail to accurately account for the function's true resource usage. We observe that the function duration can be highly unpredictable with huge amplification of more than 50x for an open-source FaaS platform (OpenLambda). Our experiments show that the OS scheduling policy of cloud functions' host server can have a crucial impact on performance. The default Linux scheduler, CFS (Completely Fair Scheduler), being oblivious to workloads, frequently context-switches short functions, causing a turnaround time that is much longer than their service time. We propose SFS (Smart Function Scheduler),which works entirely in the user space and carefully orchestrates existing Linux FIFO and CFS schedulers to approximate Shortest Remaining Time First (SRTF). SFS uses two-level scheduling that seamlessly combines a new FILTER policy with Linux CFS, to trade off increased duration of long functions for significant performance improvement for short functions. We implement {\proj} in the Linux user space and port it to OpenLambda. Evaluation results show that SFS significantly improves short functions' duration with a small impact on relatively longer functions, compared to CFS.
On the Horizon: Interactive and Compositional Deepfakes
Venue: arXiv cs.AI 2022
Year: 2022

Over a five-year period, computing methods for generating high-fidelity, fictional depictions of people and events moved from exotic demonstrations by computer science research teams into ongoing use as a tool of disinformation. The methods, referred to with the portmanteau of "deepfakes," have been used to create compelling audiovisual content. Here, I share challenges ahead with malevolent uses of two classes of deepfakes that we can expect to come into practice with costly implications for society: interactive and compositional deepfakes. Interactive deepfakes have the capability to impersonate people with realistic interactive behaviors, taking advantage of advances in multimodal interaction. Compositional deepfakes leverage synthetic content in larger disinformation plans that integrate sets of deepfakes over time with observed, expected, and engineered world events to create persuasive synthetic histories. Synthetic histories can be constructed manually but may one day be guided by adversarial generative explanation (AGE) techniques. In the absence of mitigations, interactive and compositional deepfakes threaten to move us closer to a post-epistemic world, where fact cannot be distinguished from fiction. I shall describe interactive and compositional deepfakes and reflect about cautions and potential mitigations to defend against them.
Prototype-Aware Heterogeneous Task for Point Cloud Completion
Venue: arXiv cs.CV 2022
Year: 2022

Point cloud completion, which aims at recovering original shape information from partial point clouds, has attracted attention on 3D vision community. Existing methods usually succeed in completion for standard shape, while failing to generate local details of point clouds for some non-standard shapes. To achieve desirable local details, guidance from global shape information is of critical importance. In this work, we design an effective way to distinguish standard/non-standard shapes with the help of intra-class shape prototypical representation, which can be calculated by the proposed supervised shape clustering pretext task, resulting in a heterogeneous component w.r.t completion network. The representative prototype, defined as feature centroid of shape categories, can provide global shape guidance, which is referred to as soft-perceptual prior, to inject into downstream completion network by the desired selective perceptual feature fusion module in a multi-scale manner. Moreover, for effective training, we consider difficulty-based sampling strategy to encourage the network to pay more attention to some partial point clouds with fewer geometric information. Experimental results show that our method outperforms other state-of-the-art methods and has strong ability on completing complex geometric shapes.
Using Consensual Biterms from Text Structures of Requirements and Code to Improve IR-Based Traceability Recovery
Venue: arXiv cs.SE 2022
Year: 2022

Traceability approves trace links among software artifacts based on whether two artifacts are related by system functionalities. The traces are valuable for software development, but are difficult to obtain manually. To cope with the costly and fallible manual recovery, automated approaches are proposed to recover traces through textual similarities among software artifacts, such as those based on Information Retrieval (IR). However, the low quality & quantity of artifact texts negatively impact the calculated IR values, thus greatly hindering the performance of IR-based approaches. In this study, we propose to extract co-occurred word pairs from the text structures of both requirements and code (i.e., consensual biterms) to improve IR-based traceability recovery. We first collect a set of biterms based on the part-of-speech of requirement texts, and then filter them through the code texts. We then use these consensual biterms to both enrich the input corpus for IR techniques and enhance the calculations of IR values. A nine-system-based evaluation shows that in general, when solely used to enhance IR techniques, our approach can outperform pure IR-based approaches and another baseline by 21.9% & 21.8% in AP, and 9.3% & 7.2% in MAP, respectively. Moreover, when used to collaborate with another enhancing strategy from different perspectives, it can outperform this baseline by 5.9% in AP and 4.8% in MAP.
SEFormer: Structure Embedding Transformer for 3D Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

Effectively preserving and encoding structure features from objects in irregular and sparse LiDAR points is a key challenge to 3D object detection on point cloud. Recently, Transformer has demonstrated promising performance on many 2D and even 3D vision tasks. Compared with the fixed and rigid convolution kernels, the self-attention mechanism in Transformer can adaptively exclude the unrelated or noisy points and thus suitable for preserving the local spatial structure in irregular LiDAR point cloud. However, Transformer only performs a simple sum on the point features, based on the self-attention mechanism, and all the points share the same transformation for value. Such isotropic operation lacks the ability to capture the direction-distance-oriented local structure which is important for 3D object detection. In this work, we propose a Structure-Embedding transFormer (SEFormer), which can not only preserve local structure as traditional Transformer but also have the ability to encode the local structure. Compared to the self-attention mechanism in traditional Transformer, SEFormer learns different feature transformations for value points based on the relative directions and distances to the query point. Then we propose a SEFormer based network for high-performance 3D object detection. Extensive experiments show that the proposed architecture can achieve SOTA results on Waymo Open Dataset, the largest 3D detection benchmark for autonomous driving. Specifically, SEFormer achieves 79.02% mAP, which is 1.2% higher than existing works. We will release the codes.
Exploring the Verifiability of Code Generated by GitHub Copilot
Venue: arXiv cs.SE 2022
Year: 2022

GitHub's Copilot generates code quickly. We investigate whether it generates good code. Our approach is to identify a set of problems, ask Copilot to generate solutions, and attempt to formally verify these solutions with Dafny. Our formal verification is with respect to hand-crafted specifications. We have carried out this process on 6 problems and succeeded in formally verifying 4 of the created solutions. We found evidence which corroborates the current consensus in the literature: Copilot is a powerful tool; however, it should not be "flying the plane" by itself.
LKD-Net: Large Kernel Convolution Network for Single Image Dehazing
Venue: arXiv cs.CV 2022
Year: 2022

The deep convolutional neural networks (CNNs)-based single image dehazing methods have achieved significant success. The previous methods are devoted to improving the network's performance by increasing the network's depth and width. The current methods focus on increasing the convolutional kernel size to enhance its performance by benefiting from the larger receptive field. However, directly increasing the size of the convolutional kernel introduces a massive amount of computational overhead and parameters. Thus, a novel Large Kernel Convolution Dehaze Block (LKD Block) consisting of the Decomposition deep-wise Large Kernel Convolution Block (DLKCB) and the Channel Enhanced Feed-forward Network (CEFN) is devised in this paper. The designed DLKCB can split the deep-wise large kernel convolution into a smaller depth-wise convolution and a depth-wise dilated convolution without introducing massive parameters and computational overhead. Meanwhile, the designed CEFN incorporates a channel attention mechanism into Feed-forward Network to exploit significant channels and enhance robustness. By combining multiple LKD Blocks and Up-Down sampling modules, the Large Kernel Convolution Dehaze Network (LKD-Net) is conducted. The evaluation results demonstrate the effectiveness of the designed DLKCB and CEFN, and our LKD-Net outperforms the state-of-the-art. On the SOTS indoor dataset, our LKD-Net dramatically outperforms the Transformer-based method Dehamer with only 1.79% #Param and 48.9% FLOPs. The source code of our LKD-Net is available at https://github.com/SWU-CS-MediaLab/LKD-Net.
Automatic Estimation of Self-Reported Pain by Trajectory Analysis in the Manifold of Fixed Rank Positive Semi-Definite Matrices
Venue: arXiv cs.CV 2022
Year: 2022

We propose an automatic method to estimate self-reported pain based on facial landmarks extracted from videos. For each video sequence, we decompose the face into four different regions and the pain intensity is measured by modeling the dynamics of facial movement using the landmarks of these regions. A formulation based on Gram matrices is used for representing the trajectory of landmarks on the Riemannian manifold of symmetric positive semi-definite matrices of fixed rank. A curve fitting algorithm is used to smooth the trajectories and temporal alignment is performed to compute the similarity between the trajectories on the manifold. A Support Vector Regression classifier is then trained to encode extracted trajectories into pain intensity levels consistent with self-reported pain intensity measurement. Finally, a late fusion of the estimation for each region is performed to obtain the final predicted pain level. The proposed approach is evaluated on two publicly available datasets, the UNBCMcMaster Shoulder Pain Archive and the Biovid Heat Pain dataset. We compared our method to the state-of-the-art on both datasets using different testing protocols, showing the competitiveness of the proposed approach.
SlateFree: a Model-Free Decomposition for Reinforcement Learning with Slate Actions
Venue: arXiv cs.LG 2022
Year: 2022

We consider the problem of sequential recommendations, where at each step an agent proposes some slate of $N$ distinct items to a user from a much larger catalog of size $K>>N$. The user has unknown preferences towards the recommendations and the agent takes sequential actions that optimise (in our case minimise) some user-related cost, with the help of Reinforcement Learning. The possible item combinations for a slate is $\binom{K}{N}$, an enormous number rendering value iteration methods intractable. We prove that the slate-MDP can actually be decomposed using just $K$ item-related $Q$ functions per state, which describe the problem in a more compact and efficient way. Based on this, we propose a novel model-free SARSA and Q-learning algorithm that performs $N$ parallel iterations per step, without any prior user knowledge. We call this method \texttt{SlateFree}, i.e. free-of-slates, and we show numerically that it converges very fast to the exact optimum for arbitrary user profiles, and that it outperforms alternatives from the literature.
Performance optimization and analysis of the unstructured Discontinuous Galerkin solver on multi-core and many-core architectures
Venue: arXiv cs.MS 2022
Year: 2022

The discontinuous Galerkin (DG) algorithm is a representative high order method in Computational Fluid Dynamics (CFD) area which possesses considerable mathematical advantages such as high resolution, low dissipation, and dispersion. However, DG is rather computationally intensive to demonstrate practical engineering problems. This paper discusses the implementation of our in-house practical DG application in three different programming models, as well as some optimization techniques, including grid renumbering and mixed precision to maximize the performance improvements in a single node system. The experiment on CPU and GPU shows that our CUDA, OpenACC, and OpenMP-based code obtains a maximum speedup of 42.9x, 35.3x, and 8.1x compared with serial execution by the original application, respectively. Besides, we systematically compare the programming models in two aspects: performance and productivity. Our empirical conclusions facilitate the programmers to select the right platform with a suitable programming model according to their target applications.