OpenRaiser/Intern-Atlas huggingface dataset:
Sorted Range Reporting and Range Minima Queries
Venue: arXiv cs.DS 2023
Year: 2023

Given an array A[1: n] of n elements drawn from an ordered set, the sorted range selection problem is to build a data structure that can be used to answer the following type of queries efficiently: Given a pair of indices i, j $ (1\le i\le j \le n)$, and a positive integer k, report the k smallest elements from the sub-array A[i: j] in order. Brodal et al. (Brodal, G.S., Fagerberg, R., Greve, M., and L{ó}pez-Ortiz, A., Online sorted range reporting. Algorithms and Computation (2009) pp. 173--182) introduced the problem and gave an optimal solution. After O(n log n) time for preprocessing, the query time is O(k). The space used is O(n). In this paper, we propose the only other possible optimal trade-off for the problem. We present a linear space solution to the problem that takes O(k log k) time to answer a range selection query. The preprocessing time is O(n). Moreover, the proposed algorithm reports the output elements one by one in non-decreasing order. Our solution is simple and practical. We also describe an extremely simple method for range minima queries (most of whose parts are known) which takes al most (but not exactly) linear time. We believe that this method may be, in practice, faster and easier to implement in most cases.
Destroying Multicolored Paths and Cycles in Edge-Colored Graphs
Venue: arXiv cs.DS 2023
Year: 2023

We study the computational complexity of $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion. In these problems, one is given a $c$-edge-colored graph and wants to destroy all induced $c$-colored paths or cycles, respectively, on $\ell$ vertices by deleting at most $k$ edges. Herein, a path or cycle is $c$-colored if it contains edges of $c$ distinct colors. We show that $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion are NP-hard for each non-trivial combination of $c$ and $\ell$. We then analyze the parameterized complexity of these problems. We extend the notion of neighborhood diversity to edge-colored graphs and show that both problems are fixed-parameter tractable with respect to the colored neighborhood diversity of the input graph. We also provide hardness results to outline the limits of parameterization by the standard parameter solution size $k$. Finally, we consider bicolored input graphs and show a special case of $2$-Colored $P_4$ Deletion that can be solved in polynomial time.
Maximal and minimal dynamic Petri net slicing
Venue: arXiv cs.PL 2023
Year: 2023

Context: Petri net slicing is a technique to reduce the size of a Petri net to ease the analysis or understanding of the original Petri net. Objective: Presenting two new Petri net slicing algorithms to isolate those places and transitions of a Petri net (the slice) that may contribute tokens to one or more places given (the slicing criterion). Method: The two algorithms proposed are formalized. The maximality of the first algorithm and the minimality of the second algorithm are formally proven. Both algorithms, together with three other state-of-the-art algorithms, have been implemented and integrated into a single tool so that we have been able to carry out a fair empirical evaluation. Results: Besides the two new Petri net slicing algorithms, a public, free, and open-source implementation of five algorithms is reported. The results of an empirical evaluation of the new algorithms and the slices they produce are also presented. Conclusions: The first algorithm collects all places and transitions that may contribute tokens (in any computation) to the slicing criterion, while the second algorithm collects the places and transitions needed to fire the shortest transition sequence that contributes tokens to some place in the slicing criterion. Therefore, the net computed by the first algorithm can reproduce any computation that contributes tokens to any place of interest. In contrast, the second algorithm loses this possibility, but it often produces a much more reduced subnet (which still can reproduce some computations that contribute tokens to some places of interest). The first algorithm is proven maximal, and the second one is proven minimal.
SQN: Weakly-Supervised Semantic Segmentation of Large-Scale 3D Point Clouds
Venue: arXiv cs.CV 2023
Year: 2023

Labelling point clouds fully is highly time-consuming and costly. As larger point cloud datasets with billions of points become more common, we ask whether the full annotation is even necessary, demonstrating that existing baselines designed under a fully annotated assumption only degrade slightly even when faced with 1% random point annotations. However, beyond this point, e.g., at 0.1% annotations, segmentation accuracy is unacceptably low. We observe that, as point clouds are samples of the 3D world, the distribution of points in a local neighborhood is relatively homogeneous, exhibiting strong semantic similarity. Motivated by this, we propose a new weak supervision method to implicitly augment highly sparse supervision signals. Extensive experiments demonstrate the proposed Semantic Query Network (SQN) achieves promising performance on seven large-scale open datasets under weak supervision schemes, while requiring only 0.1% randomly annotated points for training, greatly reducing annotation cost and effort. The code is available at https://github.com/QingyongHu/SQN.
On the Interpretability and Significance of Bias Metrics in Texts: a PMI-based Approach
Venue: arXiv cs.CL 2023
Year: 2023

In recent years, word embeddings have been widely used to measure biases in texts. Even if they have proven to be effective in detecting a wide variety of biases, metrics based on word embeddings lack transparency and interpretability. We analyze an alternative PMI-based metric to quantify biases in texts. It can be expressed as a function of conditional probabilities, which provides a simple interpretation in terms of word co-occurrences. We also prove that it can be approximated by an odds ratio, which allows estimating confidence intervals and statistical significance of textual biases. This approach produces similar results to metrics based on word embeddings when capturing gender gaps of the real world embedded in large corpora.
Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution
Venue: arXiv cs.NE 2023
Year: 2023

Most evolutionary algorithms have multiple parameters and their values drastically affect the performance. Due to the often complicated interplay of the parameters, setting these values right for a particular problem (parameter tuning) is a challenging task. This task becomes even more complicated when the optimal parameter values change significantly during the run of the algorithm since then a dynamic parameter choice (parameter control) is necessary. In this work, we propose a lazy but effective solution, namely choosing all parameter values (where this makes sense) in each iteration randomly from a suitably scaled power-law distribution. To demonstrate the effectiveness of this approach, we perform runtime analyses of the $(1+(λ,λ))$ genetic algorithm with all three parameters chosen in this manner. We show that this algorithm on the one hand can imitate simple hill-climbers like the $(1+1)$ EA, giving the same asymptotic runtime on problems like OneMax, LeadingOnes, or Minimum Spanning Tree. On the other hand, this algorithm is also very efficient on jump functions, where the best static parameters are very different from those necessary to optimize simple problems. We prove a performance guarantee that is comparable to the best performance known for static parameters. For the most interesting case that the jump size $k$ is constant, we prove that our performance is asymptotically better than what can be obtained with any static parameter choice. We complement our theoretical results with a rigorous empirical study confirming what the asymptotic runtime results suggest.
KnowPrompt: Knowledge-aware Prompt-tuning with Synergistic Optimization for Relation Extraction
Venue: arXiv cs.CL 2023
Year: 2023

Recently, prompt-tuning has achieved promising results for specific few-shot classification tasks. The core idea of prompt-tuning is to insert text pieces (i.e., templates) into the input and transform a classification task into a masked language modeling problem. However, for relation extraction, determining an appropriate prompt template requires domain expertise, and it is cumbersome and time-consuming to obtain a suitable label word. Furthermore, there exists abundant semantic and prior knowledge among the relation labels that cannot be ignored. To this end, we focus on incorporating knowledge among relation labels into prompt-tuning for relation extraction and propose a Knowledge-aware Prompt-tuning approach with synergistic optimization (KnowPrompt). Specifically, we inject latent knowledge contained in relation labels into prompt construction with learnable virtual type words and answer words. Then, we synergistically optimize their representation with structured constraints. Extensive experimental results on five datasets with standard and low-resource settings demonstrate the effectiveness of our approach. Our code and datasets are available in https://github.com/zjunlp/KnowPrompt for reproducibility.
RoFormer: Enhanced Transformer with Rotary Position Embedding
Venue: arXiv cs.CL 2023
Year: 2023

Position encoding recently has shown effective in the transformer architecture. It enables valuable supervision for dependency modeling between elements at different positions of the sequence. In this paper, we first investigate various methods to integrate positional information into the learning process of transformer-based language models. Then, we propose a novel method named Rotary Position Embedding(RoPE) to effectively leverage the positional information. Specifically, the proposed RoPE encodes the absolute position with a rotation matrix and meanwhile incorporates the explicit relative position dependency in self-attention formulation. Notably, RoPE enables valuable properties, including the flexibility of sequence length, decaying inter-token dependency with increasing relative distances, and the capability of equipping the linear self-attention with relative position encoding. Finally, we evaluate the enhanced transformer with rotary position embedding, also called RoFormer, on various long text classification benchmark datasets. Our experiments show that it consistently overcomes its alternatives. Furthermore, we provide a theoretical analysis to explain some experimental results. RoFormer is already integrated into Huggingface: \url{https://huggingface.co/docs/transformers/model_doc/roformer}.
Optimal Transmit Beamforming for Integrated Sensing and Communication
Venue: arXiv cs.IT 2023
Year: 2023

This paper studies the transmit beamforming in a downlink integrated sensing and communication (ISAC) system, where a base station (BS) equipped with a uniform linear array (ULA) sends combined information-bearing and dedicated radar signals to simultaneously perform downlink multiuser communication and radar target sensing. Under this setup, we maximize the radar sensing performance (in terms of minimizing the beampattern matching errors or maximizing the minimum weighted beampattern gains), subject to the communication users' minimum signal-to-interference-plus-noise ratio (SINR) requirements and the BS's transmit power constraints. In particular, we consider two types of communication receivers, namely Type-I and Type-II receivers, which do not have and do have the capability of cancelling the interference from the {\emph{a-priori}} known dedicated radar signals, respectively. Under both Type-I and Type-II receivers, the beampattern matching and minimum weighted beampattern gain maximization problems are globally optimally solved via applying the semidefinite relaxation (SDR) technique together with the rigorous proof of the tightness of SDR for both Type-I and Type-II receivers under the two design criteria. It is shown that at the optimality, radar signals are not required with Type-I receivers under some specific conditions, while radar signals are always needed to enhance the performance with Type-II receivers. Numerical results show that the minimum weighted beampattern gain maximization leads to significantly higher beampattern gains at the worst-case sensing angles with a much lower computational complexity than the beampattern matching design. We show that by exploiting the capability of canceling the interference caused by the radar signals, the case with Type-II receivers results in better sensing performance than that with Type-I receivers and other conventional designs.
VCGAN: Video Colorization with Hybrid Generative Adversarial Network
Venue: arXiv cs.CV 2023
Year: 2023

We propose a hybrid recurrent Video Colorization with Hybrid Generative Adversarial Network (VCGAN), an improved approach to video colorization using end-to-end learning. The VCGAN addresses two prevalent issues in the video colorization domain: Temporal consistency and unification of colorization network and refinement network into a single architecture. To enhance colorization quality and spatiotemporal consistency, the mainstream of generator in VCGAN is assisted by two additional networks, i.e., global feature extractor and placeholder feature extractor, respectively. The global feature extractor encodes the global semantics of grayscale input to enhance colorization quality, whereas the placeholder feature extractor acts as a feedback connection to encode the semantics of the previous colorized frame in order to maintain spatiotemporal consistency. If changing the input for placeholder feature extractor as grayscale input, the hybrid VCGAN also has the potential to perform image colorization. To improve the consistency of far frames, we propose a dense long-term loss that smooths the temporal disparity of every two remote frames. Trained with colorization and temporal losses jointly, VCGAN strikes a good balance between color vividness and video continuity. Experimental results demonstrate that VCGAN produces higher-quality and temporally more consistent colorful videos than existing approaches.
Points2Sound: From mono to binaural audio using 3D point cloud scenes
Venue: arXiv cs.SD 2023
Year: 2023

For immersive applications, the generation of binaural sound that matches its visual counterpart is crucial to bring meaningful experiences to people in a virtual environment. Recent studies have shown the possibility of using neural networks for synthesizing binaural audio from mono audio by using 2D visual information as guidance. Extending this approach by guiding the audio with 3D visual information and operating in the waveform domain may allow for a more accurate auralization of a virtual audio scene. We propose Points2Sound, a multi-modal deep learning model which generates a binaural version from mono audio using 3D point cloud scenes. Specifically, Points2Sound consists of a vision network and an audio network. The vision network uses 3D sparse convolutions to extract a visual feature from the point cloud scene. Then, the visual feature conditions the audio network, which operates in the waveform domain, to synthesize the binaural version. Results show that 3D visual information can successfully guide multi-modal deep learning models for the task of binaural synthesis. We also investigate how 3D point cloud attributes, learning objectives, different reverberant conditions, and several types of mono mixture signals affect the binaural audio synthesis performance of Points2Sound for the different numbers of sound sources present in the scene.
Good Artists Copy, Great Artists Steal: Model Extraction Attacks Against Image Translation Models
Venue: arXiv cs.LG 2023
Year: 2023

Machine learning models are typically made available to potential client users via inference APIs. Model extraction attacks occur when a malicious client uses information gleaned from queries to the inference API of a victim model $F_V$ to build a surrogate model $F_A$ with comparable functionality. Recent research has shown successful model extraction of image classification, and natural language processing models. In this paper, we show the first model extraction attack against real-world generative adversarial network (GAN) image translation models. We present a framework for conducting such attacks, and show that an adversary can successfully extract functional surrogate models by querying $F_V$ using data from the same domain as the training data for $F_V$. The adversary need not know $F_V$'s architecture or any other information about it beyond its intended task. We evaluate the effectiveness of our attacks using three different instances of two popular categories of image translation: (1) Selfie-to-Anime and (2) Monet-to-Photo (image style transfer), and (3) Super-Resolution (super resolution). Using standard performance metrics for GANs, we show that our attacks are effective. Furthermore, we conducted a large scale (125 participants) user study on Selfie-to-Anime and Monet-to-Photo to show that human perception of the images produced by $F_V$ and $F_A$ can be considered equivalent, within an equivalence bound of Cohen's d = 0.3. Finally, we show that existing defenses against model extraction attacks (watermarking, adversarial examples, poisoning) do not extend to image translation models.
Fuzzy Expert Systems for Prediction of ICU Admission in Patients with COVID-19
Venue: arXiv cs.LG 2023
Year: 2023

The pandemic COVID-19 disease has had a dramatic impact on almost all countries around the world so that many hospitals have been overwhelmed with Covid-19 cases. As medical resources are limited, deciding on the proper allocation of these resources is a very crucial issue. Besides, uncertainty is a major factor that can affect decisions, especially in medical fields. To cope with this issue, we use fuzzy logic (FL) as one of the most suitable methods in modeling systems with high uncertainty and complexity. We intend to make use of the advantages of FL in decisions on cases that need to treat in ICU. In this study, an interval type-2 fuzzy expert system is proposed for prediction of ICU admission in COVID-19 patients. For this prediction task, we also developed an adaptive neuro-fuzzy inference system (ANFIS). Finally, the results of these fuzzy systems are compared to some well-known classification methods such as Naive Bayes (NB), Case-Based Reasoning (CBR), Decision Tree (DT), and K Nearest Neighbor (KNN). The results show that the type-2 fuzzy expert system and ANFIS models perform competitively in terms of accuracy and F-measure compared to the other system modeling techniques.
Segmentation-Based Bounding Box Generation for Omnidirectional Pedestrian Detection
Venue: arXiv cs.CV 2023
Year: 2023

We propose a segmentation-based bounding box generation method for omnidirectional pedestrian detection that enables detectors to tightly fit bounding boxes to pedestrians without omnidirectional images for training. Due to the wide angle of view, omnidirectional cameras are more cost-effective than standard cameras and hence suitable for large-scale monitoring. The problem of using omnidirectional cameras for pedestrian detection is that the performance of standard pedestrian detectors is likely to be substantially degraded because pedestrians' appearance in omnidirectional images may be rotated to any angle. Existing methods mitigate this issue by transforming images during inference. However, the transformation substantially degrades the detection accuracy and speed. A recently proposed method obviates the transformation by training detectors with omnidirectional images, which instead incurs huge annotation costs. To obviate both the transformation and annotation works, we leverage an existing large-scale object detection dataset. We train a detector with rotated images and tightly fitted bounding box annotations generated from the segmentation annotations in the dataset, resulting in detecting pedestrians in omnidirectional images with tightly fitted bounding boxes. We also develop pseudo-fisheye distortion augmentation, which further enhances the performance. Extensive analysis shows that our detector successfully fits bounding boxes to pedestrians and demonstrates substantial performance improvement.
Vehicular Teamwork: Collaborative localization of Autonomous Vehicles
Venue: arXiv cs.RO 2023
Year: 2023

This paper develops a distributed collaborative localization algorithm based on an extended kalman filter. This algorithm incorporates Ultra-Wideband (UWB) measurements for vehicle to vehicle ranging, and shows improvements in localization accuracy where GPS typically falls short. The algorithm was first tested in a newly created open-source simulation environment that emulates various numbers of vehicles and sensors while simultaneously testing multiple localization algorithms. Predicted error distributions for various algorithms are quickly producible using the Monte-Carlo method and optimization techniques within MatLab. The simulation results were validated experimentally in an outdoor, urban environment. Improvements of localization accuracy over a typical extended kalman filter ranged from 2.9% to 9.3% over 180 meter test runs. When GPS was denied, these improvements increased up to 83.3% over a standard kalman filter. In both simulation and experimentally, the DCL algorithm was shown to be a good approximation of a full state filter, while reducing required communication between vehicles. These results are promising in showing the efficacy of adding UWB ranging sensors to cars for collaborative and landmark localization, especially in GPS-denied environments. In the future, additional moving vehicles with additional tags will be tested in other challenging GPS denied environments.
Deep Insights of Deepfake Technology : A Review
Venue: arXiv cs.LG 2023
Year: 2023

Under the aegis of computer vision and deep learning technology, a new emerging techniques has introduced that anyone can make highly realistic but fake videos, images even can manipulates the voices. This technology is widely known as Deepfake Technology. Although it seems interesting techniques to make fake videos or image of something or some individuals but it could spread as misinformation via internet. Deepfake contents could be dangerous for individuals as well as for our communities, organizations, countries religions etc. As Deepfake content creation involve a high level expertise with combination of several algorithms of deep learning, it seems almost real and genuine and difficult to differentiate. In this paper, a wide range of articles have been examined to understand Deepfake technology more extensively. We have examined several articles to find some insights such as what is Deepfake, who are responsible for this, is there any benefits of Deepfake and what are the challenges of this technology. We have also examined several creation and detection techniques. Our study revealed that although Deepfake is a threat to our societies, proper measures and strict regulations could prevent this.
CSAT and CEQV for nilpotent Maltsev algebras of Fitting length > 2
Venue: arXiv cs.CC 2023
Year: 2023

The circuit satisfaction problem CSAT(A) of an algebra A is the problem of deciding whether an equation over A (encoded by two circuits) has a solution or not. While solving systems of equations over finite algebras is either in P or NP-complete, no such dichotomy result is known for CSAT(A). In fact, Idziak, Kawalek and Krzaczkowski constructed examples of nilpotent Maltsev algebras A, for which, under the assumption of ETH and an open conjecture in circuit theory, CSAT(A) can be solved in quasipolynomial, but not polynomial time. The same is true for the circuit equivalence problem CEQV(A). In this paper we generalize their result to all nilpotent Maltsev algebras of Fitting length >2. This not only advances the project of classifying the complexity of CSAT (and CEQV) for algebras from congruence modular varieties, but we also believe that the tools we developed are of independent interest in the study of nilpotent algebras.