OpenRaiser/Intern-Atlas huggingface dataset:
A Subquadratic Time Algorithm for the Weighted $k$-Center Problem on Cactus Graphs
Venue: arXiv cs.DS 2023
Year: 2023

The weighted $k$-center problem in graphs is a classical facility location problem where we place $k$ centers on the graph, which minimize the maximum weighted distance of a vertex to its nearest center. We study this problem when the underlying graph is a cactus with $n$ vertices and present an $O(n \log^2 n)$ time algorithm for the same. This time complexity improves upon the $O(n^2)$ time algorithm by Ben-Moshe et al. [TCS 2007], which is the current state-of-the-art.
A Method for Emerging Empirical Age Structures in Agent-Based Models with Exogenous Survival Probabilities
Venue: arXiv cs.MA 2023
Year: 2023

For many applications of agent-based models (ABMs), an agent's age influences important decisions (e.g. their contribution to/withdrawal from pension funds, their level of risk aversion in decision-making, etc.) and outcomes in their life cycle (e.g. their susceptibility to disease). These considerations make it crucial to accurately capture the age distribution of the population being considered. Often, empirical survival probabilities cannot be used in ABMs to generate the observed age structure due to discrepancies between samples or models (between the ABM and the survival statistical model used to produce empirical rates). In these cases, imputing empirical survival probabilities will not generate the observed age structure of the population, and assumptions such as exogenous agent inflows are necessary (but not necessarily empirically valid). In this paper, we propose a method that allows for the preservation of agent age-structure without the exogenous influx of agents, even when only a subset of the population is being modelled. We demonstrate the flexibility and accuracy of our methodology by performing simulations of several real-world age distributions. This method is a useful tool for those developing ABMs across a broad range of applications.
Topics in the Haystack: Extracting and Evaluating Topics beyond Coherence
Venue: arXiv cs.CL 2023
Year: 2023

Extracting and identifying latent topics in large text corpora has gained increasing importance in Natural Language Processing (NLP). Most models, whether probabilistic models similar to Latent Dirichlet Allocation (LDA) or neural topic models, follow the same underlying approach of topic interpretability and topic extraction. We propose a method that incorporates a deeper understanding of both sentence and document themes, and goes beyond simply analyzing word frequencies in the data. This allows our model to detect latent topics that may include uncommon words or neologisms, as well as words not present in the documents themselves. Additionally, we propose several new evaluation metrics based on intruder words and similarity measures in the semantic space. We present correlation coefficients with human identification of intruder words and achieve near-human level results at the word-intrusion task. We demonstrate the competitive performance of our method with a large benchmark study, and achieve superior results compared to state-of-the-art topic modeling and document clustering models.
Author-Unification: Name-, Institution-, and Career-Sharing Co-authors
Venue: arXiv cs.DL 2023
Year: 2023

In this work, we investigate the phenomenon of Author-UnificAtion (AUA), which describes the high structural similarity of two co-authoring engineers that share the same forename, surname, institution, and academic career without being related by blood. So far, prior work has only explored similar surnames and institutions. On top of that, we elaborate on the additional author similarity of sharing the same academic career as a Ph.D. candidate with the same starting day and month included in the university contract. We show that our work outperforms previous state-of-the-art investigations, among others by providing a higher Structural Similarity Index Measure (SSIM) of the letters in our names and in our institution. Lastly, we prove the duality of our identities through a qualitative evaluation.
GAT-COBO: Cost-Sensitive Graph Neural Network for Telecom Fraud Detection
Venue: arXiv cs.LG 2023
Year: 2023

Along with the rapid evolution of mobile communication technologies, such as 5G, there has been a drastically increase in telecom fraud, which significantly dissipates individual fortune and social wealth. In recent years, graph mining techniques are gradually becoming a mainstream solution for detecting telecom fraud. However, the graph imbalance problem, caused by the Pareto principle, brings severe challenges to graph data mining. This is a new and challenging problem, but little previous work has been noticed. In this paper, we propose a Graph ATtention network with COst-sensitive BOosting (GAT-COBO) for the graph imbalance problem. First, we design a GAT-based base classifier to learn the embeddings of all nodes in the graph. Then, we feed the embeddings into a well-designed cost-sensitive learner for imbalanced learning. Next, we update the weights according to the misclassification cost to make the model focus more on the minority class. Finally, we sum the node embeddings obtained by multiple cost-sensitive learners to obtain a comprehensive node representation, which is used for the downstream anomaly detection task. Extensive experiments on two real-world telecom fraud detection datasets demonstrate that our proposed method is effective for the graph imbalance problem, outperforming the state-of-the-art GNNs and GNN-based fraud detectors. In addition, our model is also helpful for solving the widespread over-smoothing problem in GNNs. The GAT-COBO code and datasets are available at https://github.com/xxhu94/GAT-COBO.
Not Yet Another Digital ID: Privacy-preserving Humanitarian Aid Distribution
Venue: arXiv cs.CR 2023
Year: 2023

Humanitarian aid-distribution programs help bring physical goods to people in need. Traditional paper-based solutions to support aid distribution do not scale to large populations and are hard to secure. Existing digital solutions solve these issues, at the cost of collecting large amount of personal information. This lack of privacy can endanger recipients' safety and harm their dignity. In collaboration with the International Committee of the Red Cross, we build a safe digital aid-distribution system. We first systematize the requirements such a system should satisfy. We then propose a decentralized solution based on the use of tokens that fulfills the needs of humanitarian organizations. It provides scalability and strong accountability, and, by design, guarantees the recipients' privacy. We provide two instantiations of our design, on a smart card and on a smartphone. We formally prove the security and privacy properties of these solutions, and empirically show that they can operate at scale.
BPCE: A Prototype for Co-Evolution between Business Process Variants through Configurable Process Model
Venue: arXiv cs.SE 2023
Year: 2023

With the continuous development of business process management technology, the increasing business process models are usually owned by large enterprises. In large enterprises, different stakeholders may modify the same business process model. In order to better manage the changeability of processes, they adopt configurable business process models to manage process variants. However, the process variants will vary with the change in enterprise business demands. Therefore, it is necessary to explore the co-evolution of the process variants so as to effectively manage the business process family. To this end, a novel framework for co-evolution between business process variants through a configurable process model is proposed in this work. First, the mapping relationship between process variants and configurable models is standardized in this study. A series of change operations and change propagation operations between process variants and configurable models are further defined for achieving propagation. Then, an overall algorithm is proposed for achieving co-evolution of process variants. Next, a prototype is developed for managing change synchronization between process variants and configurable process models. Finally, the effectiveness and efficiency of our proposed process change propagation method are verified based on experiments on two business process datasets. The experimental results show that our approach implements the co-evolution of process variants with high accuracy and efficiency.
Semantic Image Translation for Repairing the Texture Defects of Building Models
Venue: arXiv cs.CV 2023
Year: 2023

The accurate representation of 3D building models in urban environments is significantly hindered by challenges such as texture occlusion, blurring, and missing details, which are difficult to mitigate through standard photogrammetric texture mapping pipelines. Current image completion methods often struggle to produce structured results and effectively handle the intricate nature of highly-structured façade textures with diverse architectural styles. Furthermore, existing image synthesis methods encounter difficulties in preserving high-frequency details and artificial regular structures, which are essential for achieving realistic façade texture synthesis. To address these challenges, we introduce a novel approach for synthesizing façade texture images that authentically reflect the architectural style from a structured label map, guided by a ground-truth façade image. In order to preserve fine details and regular structures, we propose a regularity-aware multi-domain method that capitalizes on frequency information and corner maps. We also incorporate SEAN blocks into our generator to enable versatile style transfer. To generate plausible structured images without undesirable regions, we employ image completion techniques to remove occlusions according to semantics prior to image inference. Our proposed method is also capable of synthesizing texture images with specific styles for façades that lack pre-existing textures, using manually annotated labels. Experimental results on publicly available façade image and 3D model datasets demonstrate that our method yields superior results and effectively addresses issues associated with flawed textures. The code and datasets will be made publicly available for further research and development.
Can I Trust My Simulation Model? Measuring the Quality of Business Process Simulation Models
Venue: arXiv cs.SE 2023
Year: 2023

Business Process Simulation (BPS) is an approach to analyze the performance of business processes under different scenarios. For example, BPS allows us to estimate what would be the cycle time of a process if one or more resources became unavailable. The starting point of BPS is a process model annotated with simulation parameters (a BPS model). BPS models may be manually designed, based on information collected from stakeholders and empirical observations, or automatically discovered from execution data. Regardless of its origin, a key question when using a BPS model is how to assess its quality. In this paper, we propose a collection of measures to evaluate the quality of a BPS model w.r.t. its ability to replicate the observed behavior of the process. We advocate an approach whereby different measures tackle different process perspectives. We evaluate the ability of the proposed measures to discern the impact of modifications to a BPS model, and their ability to uncover the relative strengths and weaknesses of two approaches for automated discovery of BPS models. The evaluation shows that the measures not only capture how close a BPS model is to the observed behavior, but they also help us to identify sources of discrepancies.
Assessing Cross-Cultural Alignment between ChatGPT and Human Societies: An Empirical Study
Venue: arXiv cs.CL 2023
Year: 2023

The recent release of ChatGPT has garnered widespread recognition for its exceptional ability to generate human-like responses in dialogue. Given its usage by users from various nations and its training on a vast multilingual corpus that incorporates diverse cultural and societal norms, it is crucial to evaluate its effectiveness in cultural adaptation. In this paper, we investigate the underlying cultural background of ChatGPT by analyzing its responses to questions designed to quantify human cultural differences. Our findings suggest that, when prompted with American context, ChatGPT exhibits a strong alignment with American culture, but it adapts less effectively to other cultural contexts. Furthermore, by using different prompts to probe the model, we show that English prompts reduce the variance in model responses, flattening out cultural differences and biasing them towards American culture. This study provides valuable insights into the cultural implications of ChatGPT and highlights the necessity of greater diversity and cultural awareness in language technologies.
Fuzzified advanced robust hashes for identification of digital and physical objects
Venue: arXiv cs.CR 2023
Year: 2023

With the rising numbers for IoT objects, it is becoming easier to penetrate counterfeit objects into the mainstream market by adversaries. Such infiltration of bogus products can be addressed with third-party-verifiable identification. Generally, state-of-the-art identification schemes do not guarantee that an identifier e.g. barcodes or RFID itself cannot be forged. This paper introduces identification patterns representing the objects intrinsic identity by robust hashes and not only by generated identification patterns. Inspired by these two notions, a collection of uniquely identifiable attributes called quasi-identifiers (QI) can be used to identify an object. Since all attributes do not contribute equally towards an object's identity, each QI has a different contribution towards the identifier. A robust hash developed utilising the QI has been named fuzzified robust hashes (FaR hashes), which can be used as an object identifier. Although the FaR hash is a single hash string, selected bits change in response to the modification of QI. On the other hand, other QIs in the object are more important for the object's identity. If these QIs change, the complete FaR hash is going to change. The calculation of FaR hash using attributes should allow third parties to generate the identifier and compare it with the current one to verify the genuineness of the object.
Learning in Factored Domains with Information-Constrained Visual Representations
Venue: arXiv cs.AI 2023
Year: 2023

Humans learn quickly even in tasks that contain complex visual information. This is due in part to the efficient formation of compressed representations of visual information, allowing for better generalization and robustness. However, compressed representations alone are insufficient for explaining the high speed of human learning. Reinforcement learning (RL) models that seek to replicate this impressive efficiency may do so through the use of factored representations of tasks. These informationally simplistic representations of tasks are similarly motivated as the use of compressed representations of visual information. Recent studies have connected biological visual perception to disentangled and compressed representations. This raises the question of how humans learn to efficiently represent visual information in a manner useful for learning tasks. In this paper we present a model of human factored representation learning based on an altered form of a $β$-Variational Auto-encoder used in a visual learning task. Modelling results demonstrate a trade-off in the informational complexity of model latent dimension spaces, between the speed of learning and the accuracy of reconstructions.
The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting
Venue: arXiv cs.DS 2023
Year: 2023

We introduce and study the online pause and resume problem. In this problem, a player attempts to find the $k$ lowest (alternatively, highest) prices in a sequence of fixed length $T$, which is revealed sequentially. At each time step, the player is presented with a price and decides whether to accept or reject it. The player incurs a switching cost whenever their decision changes in consecutive time steps, i.e., whenever they pause or resume purchasing. This online problem is motivated by the goal of carbon-aware load shifting, where a workload may be paused during periods of high carbon intensity and resumed during periods of low carbon intensity and incurs a cost when saving or restoring its state. It has strong connections to existing problems studied in the literature on online optimization, though it introduces unique technical challenges that prevent the direct application of existing algorithms. Extending prior work on threshold-based algorithms, we introduce double-threshold algorithms for both the minimization and maximization variants of this problem. We further show that the competitive ratios achieved by these algorithms are the best achievable by any deterministic online algorithm. Finally, we empirically validate our proposed algorithm through case studies on the application of carbon-aware load shifting using real carbon trace data and existing baseline algorithms.
Recognition, recall, and retention of few-shot memories in large language models
Venue: arXiv cs.CL 2023
Year: 2023

The training of modern large language models (LLMs) takes place in a regime where most training examples are seen only a few times by the model during the course of training. What does a model remember about such examples seen only a few times during training and how long does that memory persist in the face of continuous training with new examples? Here, we investigate these questions through simple recognition, recall, and retention experiments with LLMs. In recognition experiments, we ask if the model can distinguish the seen example from a novel example; in recall experiments, we ask if the model can correctly recall the seen example when cued by a part of it; and in retention experiments, we periodically probe the model's memory for the original examples as the model is trained continuously with new examples. We find that a single exposure is generally sufficient for a model to achieve near perfect accuracy even in very challenging recognition experiments. We estimate that the recognition performance of even small language models easily exceeds human recognition performance reported in similar experiments with humans (Shepard, 1967). Achieving near perfect recall takes more exposures, but most models can do it in just 3 exposures. The flip side of this remarkable capacity for fast learning is that precise memories are quickly overwritten: recall performance for the original examples drops steeply over the first 10 training updates with new examples, followed by a more gradual decline. Even after 100K updates, however, some of the original examples are still recalled near perfectly. A qualitatively similar retention pattern has been observed in human long-term memory retention studies before (Bahrick, 1984). Finally, recognition is much more robust to interference than recall and memory for natural language sentences is generally superior to memory for stimuli without structure.
Light induced spiking of proteinoids
Venue: arXiv cs.ET 2023
Year: 2023

Proteinoids, or thermal proteins, are produced by heating amino acids to their melting point and initiation of polymerisation to produce polymeric chains. In aqueous solutions proteinoids swell into hollow microspheres. These microspheres produce endogenous burst of electrical potential spikes and change patterns of their electrical activity in response to illumination. We report results of detailed investigation on the effects of white cold light on the spiking of proteinoids. We study how different types and intensities of light determine proteinoids' spiking amplitude, period, and pattern. The results of this study will be utilised to evaluate proteinoids for their potential as optical sensors and their application in unconventional computing.
Online Learning and Disambiguations of Partial Concept Classes
Venue: arXiv cs.LG 2023
Year: 2023

In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introduced a unifying framework to study the learnability of classes of partial concepts. One of the central questions studied in their work is whether the learnability of a partial concept class is always inherited from the learnability of some ``extension'' of it to a total concept class. They showed this is not the case for PAC learning but left the problem open for the stronger notion of online learnability. We resolve this problem by constructing a class of partial concepts that is online learnable, but no extension of it to a class of total concepts is online learnable (or even PAC learnable).
Ensemble weather forecast post-processing with a flexible probabilistic neural network approach
Venue: arXiv cs.LG 2023
Year: 2023

Ensemble forecast post-processing is a necessary step in producing accurate probabilistic forecasts. Conventional post-processing methods operate by estimating the parameters of a parametric distribution, frequently on a per-location or per-lead-time basis. We propose a novel, neural network-based method, which produces forecasts for all locations and lead times, jointly. To relax the distributional assumption of many post-processing methods, our approach incorporates normalizing flows as flexible parametric distribution estimators. This enables us to model varying forecast distributions in a mathematically exact way. We demonstrate the effectiveness of our method in the context of the EUPPBench benchmark, where we conduct temperature forecast post-processing for stations in a sub-region of western Europe. We show that our novel method exhibits state-of-the-art performance on the benchmark, outclassing our previous, well-performing entry. Additionally, by providing a detailed comparison of three variants of our novel post-processing method, we elucidate the reasons why our method outperforms per-lead-time-based approaches and approaches with distributional assumptions.
Transformer-based Self-supervised Multimodal Representation Learning for Wearable Emotion Recognition
Venue: arXiv cs.HC 2023
Year: 2023

Recently, wearable emotion recognition based on peripheral physiological signals has drawn massive attention due to its less invasive nature and its applicability in real-life scenarios. However, how to effectively fuse multimodal data remains a challenging problem. Moreover, traditional fully-supervised based approaches suffer from overfitting given limited labeled data. To address the above issues, we propose a novel self-supervised learning (SSL) framework for wearable emotion recognition, where efficient multimodal fusion is realized with temporal convolution-based modality-specific encoders and a transformer-based shared encoder, capturing both intra-modal and inter-modal correlations. Extensive unlabeled data is automatically assigned labels by five signal transforms, and the proposed SSL model is pre-trained with signal transformation recognition as a pretext task, allowing the extraction of generalized multimodal representations for emotion-related downstream tasks. For evaluation, the proposed SSL model was first pre-trained on a large-scale self-collected physiological dataset and the resulting encoder was subsequently frozen or fine-tuned on three public supervised emotion recognition datasets. Ultimately, our SSL-based method achieved state-of-the-art results in various emotion classification tasks. Meanwhile, the proposed model proved to be more accurate and robust compared to fully-supervised methods on low data regimes.