OpenRaiser/Intern-Atlas huggingface dataset:
PalFM-index: FM-index for Palindrome Pattern Matching
Venue: arXiv cs.DS 2023
Year: 2023

The palindrome pattern matching (pal-matching) is a kind of generalized pattern matching, in which two strings $x$ and $y$ of same length are considered to match (pal-match) if they have the same palindromic structures, i.e., for any possible $1 \le i < j \le |x| = |y|$, $x[i..j]$ is a palindrome if and only if $y[i..j]$ is a palindrome. The pal-matching problem is the problem of searching for, in a text, the occurrences of the substrings that pal-match with a pattern. Given a text $T$ of length $n$ over an alphabet of size $σ$, an index for pal-matching is to support, given a pattern $P$ of length $m$, the counting queries that compute the number $\mathsf{occ}$ of occurrences of $P$ and the locating queries that compute the occurrences of $P$. The authors in~[I et al., Theor. Comput. Sci., 2013] proposed an $O(n \lg n)$-bit data structure to support the counting queries in $O(m \lg σ)$ time and the locating queries in $O(m \lg σ+ \mathsf{occ})$ time. In this paper, we propose an FM-index type index for the pal-matching problem, which we call the PalFM-index, that occupies $2n \lg \min(σ, \lg n) + 2n + o(n)$ bits of space and supports the counting queries in $O(m)$ time. The PalFM-indexes can support the locating queries in $O(m + Δ\mathsf{occ})$ time by adding $\frac{n}Δ \lg n + n + o(n)$ bits of space, where $Δ$ is a parameter chosen from $\{1, 2, \dots, n\}$ in the preprocessing phase.
Bayesian Optimization Over Iterative Learners with Structured Responses: A Budget-aware Planning Approach
Venue: arXiv cs.LG 2023
Year: 2023

The rising growth of deep neural networks (DNNs) and datasets in size motivates the need for efficient solutions for simultaneous model selection and training. Many methods for hyperparameter optimization (HPO) of iterative learners, including DNNs, attempt to solve this problem by querying and learning a response surface while searching for the optimum of that surface. However, many of these methods make myopic queries, do not consider prior knowledge about the response structure, and/or perform a biased cost-aware search, all of which exacerbate identifying the best-performing model when a total cost budget is specified. This paper proposes a novel approach referred to as {\bf B}udget-{\bf A}ware {\bf P}lanning for {\bf I}terative Learners (BAPI) to solve HPO problems under a constrained cost budget. BAPI is an efficient non-myopic Bayesian optimization solution that accounts for the budget and leverages the prior knowledge about the objective function and cost function to select better configurations and to take more informed decisions during the evaluation (training). Experiments on diverse HPO benchmarks for iterative learners show that BAPI performs better than state-of-the-art baselines in most cases.
Explainable and High-Performance Hate and Offensive Speech Detection
Venue: arXiv cs.CL 2023
Year: 2023

The spread of information through social media platforms can create environments possibly hostile to vulnerable communities and silence certain groups in society. To mitigate such instances, several models have been developed to detect hate and offensive speech. Since detecting hate and offensive speech in social media platforms could incorrectly exclude individuals from social media platforms, which can reduce trust, there is a need to create explainable and interpretable models. Thus, we build an explainable and interpretable high performance model based on the XGBoost algorithm, trained on Twitter data. For unbalanced Twitter data, XGboost outperformed the LSTM, AutoGluon, and ULMFiT models on hate speech detection with an F1 score of 0.75 compared to 0.38 and 0.37, and 0.38 respectively. When we down-sampled the data to three separate classes of approximately 5000 tweets, XGBoost performed better than LSTM, AutoGluon, and ULMFiT; with F1 scores for hate speech detection of 0.79 vs 0.69, 0.77, and 0.66 respectively. XGBoost also performed better than LSTM, AutoGluon, and ULMFiT in the down-sampled version for offensive speech detection with F1 score of 0.83 vs 0.88, 0.82, and 0.79 respectively. We use Shapley Additive Explanations (SHAP) on our XGBoost models' outputs to makes it explainable and interpretable compared to LSTM, AutoGluon and ULMFiT that are black-box models.
Active TLS Stack Fingerprinting: Characterizing TLS Server Deployments at Scale
Venue: arXiv cs.NI 2023
Year: 2023

Active measurements can be used to collect server characteristics on a large scale. This kind of metadata can help discovering hidden relations and commonalities among server deployments offering new possibilities to cluster and classify them. As an example, identifying a previously-unknown cybercriminal infrastructures can be a valuable source for cyber-threat intelligence. We propose herein an active measurement-based methodology for acquiring Transport Layer Security (TLS) metadata from servers and leverage it for their fingerprinting. Our fingerprints capture the characteristic behavior of the TLS stack primarily caused by the implementation, configuration, and hardware support of the underlying server. Using an empirical optimization strategy that maximizes information gain from every handshake to minimize measurement costs, we generated 10 general-purpose Client Hellos used as scanning probes to create a large database of TLS configurations used for classifying servers. We fingerprinted 28 million servers from the Alexa and Majestic toplists and two Command and Control (C2) blocklists over a period of 30 weeks with weekly snapshots as foundation for two long-term case studies: classification of Content Delivery Network and C2 servers. The proposed methodology shows a precision of more than 99 % and enables a stable identification of new servers over time. This study describes a new opportunity for active measurements to provide valuable insights into the Internet that can be used in security-relevant use cases.
Intractable Group-theoretic Problems Around Zero-knowledge Proofs
Venue: arXiv cs.CR 2023
Year: 2023

While the amount of data produced and accumulated continues to advance at unprecedented rates, protection and concealment of data increase its prominence as a field of scientific study that requires more action. It is essential to protect privacy-sensitive data at every phase; at rest, at run, and while computations are executed on data. The zero-knowledge proof (ZKP) schemes are a cryptographic tool toward this aim. ZKP allows a party to securely ensure the data's authenticity and precision without revealing confidential or privacy-sensitive information during communication or computation. The power of zero-knowledge protocols is based on intractable problems. There is a requirement to design more secure and efficient zero-knowledge proofs. This demand raises the necessity of determining appropriate intractable problems to develop novel ZKP schemes. In this paper, we present a brief outline of ZKP schemes, the connection of these structures to group-theoretic intractable problems, and annotate a list of intractable problems in group theory that can be employed to devise new ZKP schemes.
Adaptive Decoding Mechanisms for UAV-enabled Double-Uplink Coordinated NOMA
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we propose a novel adaptive decoding mechanism (ADM) for the unmanned aerial vehicle (UAV)-enabled uplink (UL) non-orthogonal multiple access (NOMA) communications. Specifically, considering a harsh UAV environment, where ground-to-ground links are regularly unavailable, the proposed ADM overcomes the challenging problem of conventional UL-NOMA systems whose performance is sensitive to the transmitter's statistical channel state information and the receiver's decoding order. To evaluate the performance of the ADM, we derive closed-form expressions for the system outage probability (OP) and system throughput. In the performance analysis section, we provide novel expressions for practical air-to-ground and ground-to-air channels, while taking into account the practical implementation of imperfect successive interference cancellation (SIC) in UL-NOMA. Moreover, the obtained expression can be adopted to characterize the OP of various systems under a Mixture of Gamma (MG) distribution-based fading channels. Next, we propose a sub-optimal Gradient Descent-based algorithm to obtain the power allocation coefficients that result in maximum throughput with respect to each location on UAV's trajectory. To determine the significance of the proposed ADM in nonstationary environments, we consider the ground users and the UAV to move according to the Random Waypoint Mobility (RWM) and Reference Point Group Mobility (RPGM) models, respectively. Accurate formulas for the distance distributions are also provided. Numerical solutions demonstrate that the ADM-enhanced NOMA not only outperforms Orthogonal Multiple Access (OMA), but also improves the performance of UAV-enabled UL-NOMA even in mobile environments.
Generalized Two Color Map Theorem -- Complete Theorem of Robust Gait Plan for a Tilt-rotor
Venue: arXiv cs.RO 2023
Year: 2023

Gait plan is a procedure that is typically applied on the ground robots, e.g., quadrupedal robots; the tilt-rotor, a novel type of quadrotor with eight inputs, is not one of them. While controlling the tilt-rotor relying on feedback linearization, the tilting angles (inputs) are expected to change over-intensively, which may not be expected in the application. To help suppress the intensive change in the tilting angles, a gait plan procedure is introduced to the tilt-rotor before feedback linearization. The tilting angles are specified with time in advance by users rather than given by the control rule. However, based on this scenario, the decoupling matrix in feedback linearization can be singular for some attitudes, combinations of roll angle and pitch angle. It hinders the further application of the feedback linearization. With this concern, Two Color Map Theorem is established to maximize the acceptable attitude region, where the combinations of roll and pitch will give an invertible decoupling matrix. That theorem, however, over-restricts the choice of the tilting angles, which can rule out some feasible robust gaits. This paper gives the generalized Two Color Map Theorem; all the robust gaits can be found based on this generalized theorem. The robustness of three gaits that satisfy this generalized Two Color Map Theorem (while violating Two Color Map Theorem) are analyzed. The results show that Generalized Two Color Map Theorem completes the search for the robust gaits for a tilt-rotor.
Interpretable Hidden Markov Model-Based Deep Reinforcement Learning Hierarchical Framework for Predictive Maintenance of Turbofan Engines
Venue: arXiv cs.LG 2023
Year: 2023

An open research question in deep reinforcement learning is how to focus the policy learning of key decisions within a sparse domain. This paper emphasizes combining the advantages of inputoutput hidden Markov models and reinforcement learning towards interpretable maintenance decisions. We propose a novel hierarchical-modeling methodology that, at a high level, detects and interprets the root cause of a failure as well as the health degradation of the turbofan engine, while, at a low level, it provides the optimal replacement policy. It outperforms the baseline performance of deep reinforcement learning methods applied directly to the raw data or when using a hidden Markov model without such a specialized hierarchy. It also provides comparable performance to prior work, however, with the additional benefit of interpretability.
FedIIC: Towards Robust Federated Learning for Class-Imbalanced Medical Image Classification
Venue: arXiv cs.CV 2023
Year: 2023

Federated learning (FL), training deep models from decentralized data without privacy leakage, has shown great potential in medical image computing recently. However, considering the ubiquitous class imbalance in medical data, FL can exhibit performance degradation, especially for minority classes (e.g. rare diseases). Existing methods towards this problem mainly focus on training a balanced classifier to eliminate class prior bias among classes, but neglect to explore better representation to facilitate classification performance. In this paper, we present a privacy-preserving FL method named FedIIC to combat class imbalance from two perspectives: feature learning and classifier learning. In feature learning, two levels of contrastive learning are designed to extract better class-specific features with imbalanced data in FL. In classifier learning, per-class margins are dynamically set according to real-time difficulty and class priors, which helps the model learn classes equally. Experimental results on publicly-available datasets demonstrate the superior performance of FedIIC in dealing with both real-world and simulated multi-source medical imaging data under class imbalance. Code is available at https://github.com/wnn2000/FedIIC.
Which arithmetic operations can be performed in constant time in the RAM model with addition?
Venue: arXiv cs.CC 2023
Year: 2023

In the literature of algorithms, the specific computation model is often not explicit as it is assumed that the model of computation is the RAM (Random Access Machine) model. However, the RAM model itself is ill-founded in the literature, with disparate definitions and no unified results. The ambition of this paper is to found the RAM model from scratch by exhibiting a RAM model that enjoys interesting algorithmic properties and the robustness of its complexity classes, notably LIN, the class of linear-time computable problems, or the now well-known CONST-DELAY-lin class of enumeration problems computable with constant delay after linear-time preprocessing, The computation model that we define is a RAM whose contents and addresses of registers are $O(N)$, where $N$ is the size (number of registers) of the input, and where the time cost of each instruction is 1 (unit cost criterion). The key to the foundation of our RAM model will be to prove that even if addition is the only primitive operation, such a RAM can still compute all the basic arithmetic operations in constant time after a linear-time preprocessing. Moreover, while the RAM handles only $O(N)$ integers in each register, we will show that our RAM can handle $O(N^d)$ integers, for any fixed d, by storing them on $O(d)$ registers and we will have surprising algorithms that computes many operations acting on these "polynomial" integers -- addition, subtraction, multiplication, division, exponential, integer logarithm, integer square root (or $c$-th root, for any integer $c$), bitwise logical operations, and, more generally, any operation computable in linear time on a cellular automaton -- in constant time after a linear-time preprocessing.
Get Your Memory Right: The Crispy Resource Allocation Assistant for Large-Scale Data Processing
Venue: arXiv cs.DC 2023
Year: 2023

Distributed dataflow systems like Apache Spark and Apache Hadoop enable data-parallel processing of large datasets on clusters. Yet, selecting appropriate computational resources for dataflow jobs -- that neither lead to bottlenecks nor to low resource utilization -- is often challenging, even for expert users such as data engineers. Further, existing automated approaches to resource selection rely on the assumption that a job is recurring to learn from previous runs or to warrant the cost of full test runs to learn from. However, this assumption often does not hold since many jobs are too unique. Therefore, we present Crispy, a method for optimizing data processing cluster configurations based on job profiling runs with small samples of the dataset on just a single machine. Crispy attempts to extrapolate the memory usage for the full dataset to then choose a cluster configuration with enough total memory. In our evaluation on a dataset with 1031 Spark and Hadoop jobs, we see a reduction of job execution costs by 56% compared to the baseline, while on average spending less than ten minutes on profiling runs per job on a consumer-grade laptop.
Let the paintings play
Venue: arXiv cs.MM 2023
Year: 2023

In this paper, we introduce a mathematical method to extract similarities between paintings and musical tracks. Our approach is based on the digitalization of both paintings and musical tracks by means of finite expansions in terms of orthogonal basis functions (with both Fourier and wavelet bases). The best fit between a specific painting and a sample of musical tracks from a given composer is achieved via an $L^2$ projection upon a finite-dimensional subspace. Several examples are provided for the analysis of a collection of works of art by the Italian artist Marcello Morandini. Finally, we have developed an original applet that implements the process above and which can be freely downloaded from the site https://github.com/pgerva/playing-paintings.git
Masked World Models for Visual Control
Venue: arXiv cs.RO 2023
Year: 2023

Visual model-based reinforcement learning (RL) has the potential to enable sample-efficient robot learning from visual observations. Yet the current approaches typically train a single model end-to-end for learning both visual representations and dynamics, making it difficult to accurately model the interaction between robots and small objects. In this work, we introduce a visual model-based RL framework that decouples visual representation learning and dynamics learning. Specifically, we train an autoencoder with convolutional layers and vision transformers (ViT) to reconstruct pixels given masked convolutional features, and learn a latent dynamics model that operates on the representations from the autoencoder. Moreover, to encode task-relevant information, we introduce an auxiliary reward prediction objective for the autoencoder. We continually update both autoencoder and dynamics model using online samples collected from environment interaction. We demonstrate that our decoupling approach achieves state-of-the-art performance on a variety of visual robotic tasks from Meta-world and RLBench, e.g., we achieve 81.7% success rate on 50 visual robotic manipulation tasks from Meta-world, while the baseline achieves 67.9%. Code is available on the project website: https://sites.google.com/view/mwm-rl.
BertNet: Harvesting Knowledge Graphs with Arbitrary Relations from Pretrained Language Models
Venue: arXiv cs.CL 2023
Year: 2023

It is crucial to automatically construct knowledge graphs (KGs) of diverse new relations to support knowledge discovery and broad applications. Previous KG construction methods, based on either crowdsourcing or text mining, are often limited to a small predefined set of relations due to manual cost or restrictions in text corpus. Recent research proposed to use pretrained language models (LMs) as implicit knowledge bases that accept knowledge queries with prompts. Yet, the implicit knowledge lacks many desirable properties of a full-scale symbolic KG, such as easy access, navigation, editing, and quality assurance. In this paper, we propose a new approach of harvesting massive KGs of arbitrary relations from pretrained LMs. With minimal input of a relation definition (a prompt and a few shot of example entity pairs), the approach efficiently searches in the vast entity pair space to extract diverse accurate knowledge of the desired relation. We develop an effective search-and-rescore mechanism for improved efficiency and accuracy. We deploy the approach to harvest KGs of over 400 new relations from different LMs. Extensive human and automatic evaluations show our approach manages to extract diverse accurate knowledge, including tuples of complex relations (e.g., "A is capable of but not good at B"). The resulting KGs as a symbolic interpretation of the source LMs also reveal new insights into the LMs' knowledge capacities.
Competence-based Multimodal Curriculum Learning for Medical Report Generation
Venue: arXiv cs.CL 2023
Year: 2023

Medical report generation task, which targets to produce long and coherent descriptions of medical images, has attracted growing research interests recently. Different from the general image captioning tasks, medical report generation is more challenging for data-driven neural models. This is mainly due to 1) the serious data bias and 2) the limited medical data. To alleviate the data bias and make best use of available data, we propose a Competence-based Multimodal Curriculum Learning framework (CMCL). Specifically, CMCL simulates the learning process of radiologists and optimizes the model in a step by step manner. Firstly, CMCL estimates the difficulty of each training instance and evaluates the competence of current model; Secondly, CMCL selects the most suitable batch of training instances considering current model competence. By iterating above two steps, CMCL can gradually improve the model's performance. The experiments on the public IU-Xray and MIMIC-CXR datasets show that CMCL can be incorporated into existing models to improve their performance.
Mining Seasonal Temporal Patterns in Time Series
Venue: arXiv cs.DB 2023
Year: 2023

Very large time series are increasingly available from an ever wider range of IoT-enabled sensors, from which significant insights can be obtained through mining temporal patterns from them. A useful type of patterns found in many real-world applications exhibits periodic occurrences, and is thus called seasonal temporal pattern (STP). Compared to regular patterns, mining seasonal temporal patterns is more challenging since traditional measures such as support and confidence do not capture the seasonality characteristics. Further, the anti-monotonicity property does not hold for STPs, and thus, resulting in an exponential search space. This paper presents our Frequent Seasonal Temporal Pattern Mining from Time Series (FreqSTPfTS) solution providing: (1) The first solution for seasonal temporal pattern mining (STPM) from time series that can mine STP at different data granularities. (2) The STPM algorithm that uses efficient data structures and two pruning techniques to reduce the search space and speed up the mining process. (3) An approximate version of STPM that uses mutual information, a measure of data correlation, to prune unpromising time series from the search space. (4) An extensive experimental evaluation showing that STPM outperforms the baseline in runtime and memory consumption, and can scale to big datasets. The approximate STPM is up to an order of magnitude faster and less memory consuming than the baseline, while maintaining high accuracy.
Discrete Langevin Sampler via Wasserstein Gradient Flow
Venue: arXiv cs.LG 2023
Year: 2023

It is known that gradient-based MCMC samplers for continuous spaces, such as Langevin Monte Carlo (LMC), can be derived as particle versions of a gradient flow that minimizes KL divergence on a Wasserstein manifold. The superior efficiency of such samplers has motivated several recent attempts to generalize LMC to discrete spaces. However, a fully principled extension of Langevin dynamics to discrete spaces has yet to be achieved, due to the lack of well-defined gradients in the sample space. In this work, we show how the Wasserstein gradient flow can be generalized naturally to discrete spaces. Given the proposed formulation, we demonstrate how a discrete analogue of Langevin dynamics can subsequently be developed. With this new understanding, we reveal how recent gradient-based samplers in discrete spaces can be obtained as special cases by choosing particular discretizations. More importantly, the framework also allows for the derivation of novel algorithms, one of which, \textit{Discrete Langevin Monte Carlo} (DLMC), is obtained by a factorized estimate of the transition matrix. The DLMC method admits a convenient parallel implementation and time-uniform sampling that achieves larger jump distances. We demonstrate the advantages of DLMC on various binary and categorical distributions.