OpenRaiser/Intern-Atlas huggingface dataset:
InitialGAN: A Language GAN with Completely Random Initialization
Venue: arXiv cs.CL 2023
Year: 2023

Text generative models trained via Maximum Likelihood Estimation (MLE) suffer from the notorious exposure bias problem, and Generative Adversarial Networks (GANs) are shown to have potential to tackle this problem. Existing language GANs adopt estimators like REINFORCE or continuous relaxations to model word probabilities. The inherent limitations of such estimators lead current models to rely on pre-training techniques (MLE pre-training or pre-trained embeddings). Representation modeling methods which are free from those limitations, however, are seldomly explored because of their poor performance in previous attempts. Our analyses reveal that invalid sampling methods and unhealthy gradients are the main contributors to such unsatisfactory performance. In this work, we present two techniques to tackle these problems: dropout sampling and fully normalized LSTM. Based on these two techniques, we propose InitialGAN whose parameters are randomly initialized in full. Besides, we introduce a new evaluation metric, Least Coverage Rate, to better evaluate the quality of generated samples. The experimental results demonstrate that InitialGAN outperforms both MLE and other compared models. To the best of our knowledge, it is the first time a language GAN can outperform MLE without using any pre-training techniques.
Infinite Separation between General and Chromatic Memory
Venue: arXiv cs.GT 2023
Year: 2023

In this paper, we construct a winning condition $W$ over a finite set of colors such that, first, every finite arena has a strategy with 2 states of general memory which is optimal w.r.t.~$W$, and second, there exists no $k$ such that every finite arena has a strategy with $k$ states of chromatic memory which is optimal w.r.t.~$W$.
Relict landslide detection using Deep-Learning architectures for image segmentation in rainforest areas: A new framework
Venue: arXiv cs.CV 2023
Year: 2023

Landslides are destructive and recurrent natural disasters on steep slopes and represent a risk to lives and properties. Knowledge of relict landslides location is vital to understand their mechanisms, update inventory maps and improve risk assessment. However, relict landslide mapping is complex in tropical regions covered with rainforest vegetation. A new CNN framework is proposed for semi-automatic detection of relict landslides, which uses a dataset generated by a k-means clustering algorithm and has a pre-training step. The weights computed in the pre-training are used to fine-tune the CNN training process. A comparison between the proposed and the standard framework is performed using CBERS-04A WPM images. Three CNNs for semantic segmentation are used (Unet, FPN, Linknet) with two augmented datasets. A total of 42 combinations of CNNs are tested. Values of precision and recall were very similar between the combinations tested. Recall was higher than 75% for every combination, but precision values were usually smaller than 20%. False positives (FP) samples were addressed as the cause for these low precision values. Predictions of the proposed framework were more accurate and correctly detected more landslides. This work demonstrates that there are limitations for detecting relict landslides in areas covered with rainforest, mainly related to similarities between the spectral response of pastures and deforested areas with Gleichenella sp. ferns, commonly used as an indicator of landslide scars.
Spectral Universality of Regularized Linear Regression with Nearly Deterministic Sensing Matrices
Venue: arXiv cs.IT 2023
Year: 2023

It has been observed that the performances of many high-dimensional estimation problems are universal with respect to underlying sensing (or design) matrices. Specifically, matrices with markedly different constructions seem to achieve identical performance if they share the same spectral distribution and have ``generic'' singular vectors. We prove this universality phenomenon for the case of convex regularized least squares (RLS) estimators under a linear regression model with additive Gaussian noise. Our main contributions are two-fold: (1) We introduce a notion of universality classes for sensing matrices, defined through a set of deterministic conditions that fix the spectrum of the sensing matrix and precisely capture the previously heuristic notion of generic singular vectors; (2) We show that for all sensing matrices that lie in the same universality class, the dynamics of the proximal gradient descent algorithm for solving the regression problem, as well as the performance of RLS estimators themselves (under additional strong convexity conditions) are asymptotically identical. In addition to including i.i.d. Gaussian and rotational invariant matrices as special cases, our universality class also contains highly structured, strongly correlated, or even (nearly) deterministic matrices. Examples of the latter include randomly signed versions of incoherent tight frames and randomly subsampled Hadamard transforms. As a consequence of this universality principle, the asymptotic performance of regularized linear regression on many structured matrices constructed with limited randomness can be characterized by using the rotationally invariant ensemble as an equivalent yet mathematically more tractable surrogate.
OpenCon: Open-world Contrastive Learning
Venue: arXiv cs.LG 2023
Year: 2023

Machine learning models deployed in the wild naturally encounter unlabeled samples from both known and novel classes. Challenges arise in learning from both the labeled and unlabeled data, in an open-world semi-supervised manner. In this paper, we introduce a new learning framework, open-world contrastive learning (OpenCon). OpenCon tackles the challenges of learning compact representations for both known and novel classes and facilitates novelty discovery along the way. We demonstrate the effectiveness of OpenCon on challenging benchmark datasets and establish competitive performance. On the ImageNet dataset, OpenCon significantly outperforms the current best method by 11.9% and 7.4% on novel and overall classification accuracy, respectively. Theoretically, OpenCon can be rigorously interpreted from an EM algorithm perspective--minimizing our contrastive loss partially maximizes the likelihood by clustering similar samples in the embedding space. The code is available at https://github.com/deeplearning-wisc/opencon.
Trust based attachment
Venue: arXiv cs.SI 2023
Year: 2023

In social systems subject to indirect reciprocity, a positive reputation is key for increasing one's likelihood of future positive interactions. The flow of gossip can amplify the impact of a person's actions on their reputation depending on how widely it spreads across the social network, which leads to a percolation problem. To quantify this notion, we calculate the expected number of individuals, the "audience", who find out about a particular interaction. For a potential donor, a larger audience constitutes higher reputational stakes, and thus a higher incentive, to perform "good" actions in line with current social norms. For a receiver, a larger audience therefore increases the trust that the partner will be cooperative. This idea can be used for an algorithm that generates social networks, which we call trust based attachment (TBA). TBA produces graphs that share crucial quantitative properties with real-world networks, such as high clustering, small-world behavior, and power law degree distributions. We also show that TBA can be approximated by simple friend-of-friend routines based on triadic closure, which are known to be highly effective at generating realistic social network structures. Therefore, our work provides a new justification for triadic closure in social contexts based on notions of trust, gossip, and social information spread. These factors are thus identified as potential significant influences on how humans form social ties.
Fast detection of specific fragments against a set of sequences
Venue: arXiv cs.DS 2023
Year: 2023

We design alignment-free techniques for comparing a sequence or word, called a target, against a set of words, called a reference. A target-specific factor of a target $T$ against a reference $R$ is a factor $w$ of a word in $T$ which is not a factor of a word of $R$ and such that any proper factor of $w$ is a factor of a word of $R$. We first address the computation of the set of target-specific factors of a target $T$ against a reference $R$, where $T$ and $R$ are finite sets of sequences. The result is the construction of an automaton accepting the set of all considered target-specific factors. The construction algorithm runs in linear time according to the size of $T\cup R$. The second result consists of the design of an algorithm to compute all the occurrences in a single sequence $T$ of its target-specific factors against a reference $R$. The algorithm runs in real-time on the target sequence, independently of the number of occurrences of target-specific factors.
On Fast Simulation of Dynamical System with Neural Vector Enhanced Numerical Solver
Venue: arXiv cs.CE 2023
Year: 2023

The large-scale simulation of dynamical systems is critical in numerous scientific and engineering disciplines. However, traditional numerical solvers are limited by the choice of step sizes when estimating integration, resulting in a trade-off between accuracy and computational efficiency. To address this challenge, we introduce a deep learning-based corrector called Neural Vector (NeurVec), which can compensate for integration errors and enable larger time step sizes in simulations. Our extensive experiments on a variety of complex dynamical system benchmarks demonstrate that NeurVec exhibits remarkable generalization capability on a continuous phase space, even when trained using limited and discrete data. NeurVec significantly accelerates traditional solvers, achieving speeds tens to hundreds of times faster while maintaining high levels of accuracy and stability. Moreover, NeurVec's simple-yet-effective design, combined with its ease of implementation, has the potential to establish a new paradigm for fast-solving differential equations based on deep learning.
Rate Splitting Multiple Access for Next Generation Cognitive Radio Enabled LEO Satellite Networks
Venue: arXiv cs.IT 2023
Year: 2023

This paper proposes a cognitive radio enabled LEO SatCom using RSMA radio access technique with the coexistence of GEO SatCom network. In particular, this work aims to maximize the sum rate of LEO SatCom by simultaneously optimizing the power budget over different beams, RSMA power allocation for users over each beam, and subcarrier user assignment while restricting the interference temperature to GEO SatCom. The problem of sum rate maximization is formulated as non-convex, where the global optimal solution is challenging to obtain. Thus, an efficient solution can be obtained in three steps: first we employ a successive convex approximation technique to reduce the complexity and make the problem more tractable. Second, for any given resource block user assignment, we adopt KKT conditions to calculate the transmit power over different beams and RSMA power allocation of users over each beam. Third, using the allocated power, we design an efficient algorithm based on the greedy approach for resource block user assignment. Numerical results demonstrate the benefits of the proposed optimization scheme compared to the benchmark schemes.
Optimal scheduling of entropy regulariser for continuous-time linear-quadratic reinforcement learning
Venue: arXiv cs.LG 2023
Year: 2023

This work uses the entropy-regularised relaxed stochastic control perspective as a principled framework for designing reinforcement learning (RL) algorithms. Herein agent interacts with the environment by generating noisy controls distributed according to the optimal relaxed policy. The noisy policies on the one hand, explore the space and hence facilitate learning but, on the other hand, introduce bias by assigning a positive probability to non-optimal actions. This exploration-exploitation trade-off is determined by the strength of entropy regularisation. We study algorithms resulting from two entropy regularisation formulations: the exploratory control approach, where entropy is added to the cost objective, and the proximal policy update approach, where entropy penalises policy divergence between consecutive episodes. We focus on the finite horizon continuous-time linear-quadratic (LQ) RL problem, where a linear dynamics with unknown drift coefficients is controlled subject to quadratic costs. In this setting, both algorithms yield a Gaussian relaxed policy. We quantify the precise difference between the value functions of a Gaussian policy and its noisy evaluation and show that the execution noise must be independent across time. By tuning the frequency of sampling from relaxed policies and the parameter governing the strength of entropy regularisation, we prove that the regret, for both learning algorithms, is of the order $\mathcal{O}(\sqrt{N}) $ (up to a logarithmic factor) over $N$ episodes, matching the best known result from the literature.
E2EG: End-to-End Node Classification Using Graph Topology and Text-based Node Attributes
Venue: arXiv cs.LG 2023
Year: 2023

Node classification utilizing text-based node attributes has many real-world applications, ranging from prediction of paper topics in academic citation graphs to classification of user characteristics in social media networks. State-of-the-art node classification frameworks, such as GIANT, use a two-stage pipeline: first embedding the text attributes of graph nodes then feeding the resulting embeddings into a node classification model. In this paper, we eliminate these two stages and develop an end-to-end node classification model that builds upon GIANT, called End-to-End-GIANT (E2EG). The tandem utilization of a main and an auxiliary classification objectives in our approach results in a more robust model, enabling the BERT backbone to be switched out for a distilled encoder with a 25% - 40% reduction in the number of parameters. Moreover, the model's end-to-end nature increases ease of use, as it avoids the need of chaining multiple models for node classification. Compared to a GIANT+MLP baseline on the ogbn-arxiv and ogbn-products datasets, E2EG obtains slightly better accuracy in the transductive setting (+0.5%), while reducing model training time by up to 40%. Our model is also applicable in the inductive setting, outperforming GIANT+MLP by up to +2.23%.
3D Tomographic Phase Retrieval and Unwrapping
Venue: arXiv cs.IT 2023
Year: 2023

This paper develops uniqueness theory for 3D phase retrieval with finite, discrete measurement data for strong phase objects and weak phase objects, including: (i) {\em Unique determination of (phase) projections from diffraction patterns} -- General measurement schemes with coded and uncoded apertures are proposed and shown to ensure unique reduction of diffraction patterns to the phase projection for a strong phase object (respectively, the projection for a weak phase object) in each direction separately without the knowledge of relative orientations and locations. (ii) {\em Uniqueness for 3D phase unwrapping} -- General conditions for unique determination of a 3D strong phase object from its phase projection data are established, including, but not limited to, random tilt schemes densely sampled from a spherical triangle of vertexes in three orthogonal directions and other deterministic tilt schemes. (iii) {\em Uniqueness for projection tomography} -- Unique determination of an object of $n^3$ voxels from generic $n$ projections or $n+1$ coded diffraction patterns is proved. This approach of reducing 3D phase retrieval to the problem of (phase) projection tomography has the practical implication of enabling classification and alignment, when relative orientations are unknown, to be carried out in terms of (phase) projections, instead of diffraction patterns. The applications with the measurement schemes such as single-axis tilt, conical tilt, dual-axis tilt, random conical tilt and general random tilt are discussed.
Explainable prediction of Qcodes for NOTAMs using column generation
Venue: arXiv cs.LG 2023
Year: 2023

A NOtice To AirMen (NOTAM) contains important flight route related information. To search and filter them, NOTAMs are grouped into categories called QCodes. In this paper, we develop a tool to predict, with some explanations, a Qcode for a NOTAM. We present a way to extend the interpretable binary classification using column generation proposed in Dash, Gunluk, and Wei (2018) to a multiclass text classification method. We describe the techniques used to tackle the issues related to one vs-rest classification, such as multiple outputs and class imbalances. Furthermore, we introduce some heuristics, including the use of a CP-SAT solver for the subproblems, to reduce the training time. Finally, we show that our approach compares favorably with state-of-the-art machine learning algorithms like Linear SVM and small neural networks while adding the needed interpretability component.
Cross-chain between a Parent Chain and Multiple Side Chains
Venue: arXiv cs.CR 2023
Year: 2023

In certain Blockchain systems, multiple Blockchains are required to operate cooperatively for security, performance, and capacity considerations. This invention defines a cross-chain mechanism where a main Blockchain issues the tokens, which can then be transferred and used in multiple side Blockchains to drive their operations. A set of witnesses are created to securely manage the token exchange across the main chain and multiple side chains. The system decouples the consensus algorithms between the main chain and side chains. We also discuss the coexistence of the main tokens and the native tokens in the side chains.
Universal Address Sequence Generator for Memory Built-in Self-test
Venue: arXiv cs.AR 2023
Year: 2023

This paper presents the universal address sequence generator (UASG) for memory built-in-self-test. The studies are based on the proposed universal method for generating address sequences with the desired properties for multirun march memory tests. As a mathematical model, a modification of the recursive relation for quasi-random sequence generation is used. For this model, a structural diagram of the hardware implementation is given, of which the basis is a storage device for storing so-called direction numbers of the generation matrix. The form of the generation matrix determines the basic properties of the generated address sequences. The proposed UASG generates a wide spectrum of different address sequences, including the standard ones, such as linear, address complement, gray code, worst-case gate delay, $2^i$, next address, and pseudorandom. Examples of the use of the proposed methods are considered. The result of the practical implementation of the UASG is presented, and the main characteristics are evaluated.
Attention-aware Resource Allocation and QoE Analysis for Metaverse xURLLC Services
Venue: arXiv cs.AI 2023
Year: 2023

Metaverse encapsulates our expectations of the next-generation Internet, while bringing new key performance indicators (KPIs). Although conventional ultra-reliable and low-latency communications (URLLC) can satisfy objective KPIs, it is difficult to provide a personalized immersive experience that is a distinctive feature of the Metaverse. Since the quality of experience (QoE) can be regarded as a comprehensive KPI, the URLLC is evolved towards the next generation URLLC (xURLLC) with a personalized resource allocation scheme to achieve higher QoE. To deploy Metaverse xURLLC services, we study the interaction between the Metaverse service provider (MSP) and the network infrastructure provider (InP), and provide an optimal contract design framework. Specifically, the utility of the MSP, defined as a function of Metaverse users' QoE, is to be maximized, while ensuring the incentives of the InP. To model the QoE mathematically, we propose a novel metric named Meta-Immersion that incorporates both the objective KPIs and subjective feelings of Metaverse users. Furthermore, we develop an attention-aware rendering capacity allocation scheme to improve QoE in xURLLC. Using a user-object-attention level dataset, we validate that the xURLLC can achieve an average of 20.1% QoE improvement compared to the conventional URLLC with a uniform resource allocation scheme. The code for this paper is available at https://github.com/HongyangDu/AttentionQoE
Augmented Driver Behavior Models for High-Fidelity Simulation Study of Crash Detection Algorithms
Venue: arXiv cs.MA 2023
Year: 2023

Developing safety and efficiency applications for Connected and Automated Vehicles (CAVs) require a great deal of testing and evaluation. The need for the operation of these systems in critical and dangerous situations makes the burden of their evaluation very costly, possibly dangerous, and time-consuming. As an alternative, researchers attempt to study and evaluate their algorithms and designs using simulation platforms. Modeling the behavior of drivers or human operators in CAVs or other vehicles interacting with them is one of the main challenges of such simulations. While developing a perfect model for human behavior is a challenging task and an open problem, we present a significant augmentation of the current models used in simulators for driver behavior. In this paper, we present a simulation platform for a hybrid transportation system that includes both human-driven and automated vehicles. In addition, we decompose the human driving task and offer a modular approach to simulating a large-scale traffic scenario, allowing for a thorough investigation of automated and active safety systems. Such representation through Interconnected modules offers a human-interpretable system that can be tuned to represent different classes of drivers. Additionally, we analyze a large driving dataset to extract expressive parameters that would best describe different driving characteristics. Finally, we recreate a similarly dense traffic scenario within our simulator and conduct a thorough analysis of various human-specific and system-specific factors, studying their effect on traffic network performance and safety.
Finding Reusable Machine Learning Components to Build Programming Language Processing Pipelines
Venue: arXiv cs.LG 2023
Year: 2023

Programming Language Processing (PLP) using machine learning has made vast improvements in the past few years. Increasingly more people are interested in exploring this promising field. However, it is challenging for new researchers and developers to find the right components to construct their own machine learning pipelines, given the diverse PLP tasks to be solved, the large number of datasets and models being released, and the set of complex compilers or tools involved. To improve the findability, accessibility, interoperability and reusability (FAIRness) of machine learning components, we collect and analyze a set of representative papers in the domain of machine learning-based PLP. We then identify and characterize key concepts including PLP tasks, model architectures and supportive tools. Finally, we show some example use cases of leveraging the reusable components to construct machine learning pipelines to solve a set of PLP tasks.