OpenRaiser/Intern-Atlas huggingface dataset:
Empirical Study of Straggler Problem in Parameter Server on Iterative Convergent Distributed Machine Learning
Venue: arXiv cs.DC 2023
Year: 2023

The purpose of this study is to test the effectiveness of current straggler mitigation techniques over different important iterative convergent machine learning(ML) algorithm including Matrix Factorization (MF), Multinomial Logistic Regression (MLR), and Latent Dirichlet Allocation (LDA) . The experiment was conducted to implemented using the FlexPS system, which is the latest system implementation that employ parameter server architecture. The experiment employed the Bulk Synchronous Parallel (BSP) computational model to examine the straggler problem in Parameter Server on Iterative Convergent Distributed Machine Learning. Moreover, the current research analyzes the experimental arrangement of the parameter server strategy concerning the parallel learning problems by injecting universal straggler patterns and executing latest mitigation techniques. The findings of the study are significant in that as they will provide the necessary platform for conducting further research into the problem and allow the researcher to compare different methods for various applications. The outcome is therefore expected to facilitate the development of new techniques coupled with new perspectives in addressing this problem.
Detecting Inactive Cyberwarriors from Online Forums
Venue: arXiv cs.SI 2023
Year: 2023

The proliferation of misinformation has emerged as a new form of warfare in the information age. This type of warfare involves cyberwarriors, who deliberately propagate messages aimed at defaming opponents or fostering unity among allies. In this study, we investigate the level of activity exhibited by cyberwarriors within a large online forum, and remarkably, we discover that only a minute fraction of cyberwarriors are active users. Surprisingly, despite their expected role of actively disseminating misinformation, cyberwarriors remain predominantly silent during peacetime and only spring into action when necessary. Moreover, we analyze the challenges associated with identifying cyberwarriors and provide evidence that detecting inactive cyberwarriors is considerably more challenging than identifying their active counterparts. Finally, we discuss potential methodologies to more effectively identify cyberwarriors during their inactive phases, offering insights into better capturing their presence and actions. The experimental code is released for reproducibility: \url{https://github.com/Ryaninthegame/Detect-Inactive-Spammers-on-PTT}.
Certifying C program correctness with respect to CH2O with VeriFast
Venue: arXiv cs.LO 2023
Year: 2023

VeriFast is a powerful tool for verification of various correctness properties of C programs using symbolic execution. However, VeriFast itself has not been verified. We present a proof-of-concept extension which generates a correctness certificate for each successful verification run individually. This certificate takes the form of a Coq script which, when successfully checked by Coq, removes the need for trusting in the correctness of VeriFast itself. The Coq script achieves this by applying a chain of soundness results, allowing us to prove correctness of the program with regards to the third-party CH2O small step semantics for C11 by proving correctness in terms of symbolic execution in Coq. This proof chain includes two intermediate auxiliary big step semantics, the most important of which describes VeriFast's interpretation of C. Finally, symbolic execution in Coq is implemented by transforming the exported AST of the program into a Coq proposition representing the symbolic execution performed by VeriFast itself.
A Task-Parallel Approach for Localized Topological Data Structures
Venue: arXiv cs.DS 2023
Year: 2023

Unstructured meshes are characterized by data points irregularly distributed in the Euclidian space. Due to the irregular nature of these data, computing connectivity information between the mesh elements requires much more time and memory than on uniformly distributed data. To lower storage costs, dynamic data structures have been proposed. These data structures compute connectivity information on the fly and discard them when no longer needed. However, on-the-fly computation slows down algorithms and results in a negative impact on the time performance. To address this issue, we propose a new task-parallel approach to proactively compute mesh connectivity. Unlike previous approaches implementing data-parallel models, where all threads run the same type of instructions, our task-parallel approach allows threads to run different functions. Specifically, some threads run the algorithm of choice while other threads compute connectivity information before they are actually needed. The approach was implemented in the new Accelerated Clustered TOPOlogical (ACTOPO) data structure, which can support any processing algorithm requiring mesh connectivity information. Our experiments show that ACTOPO combines the benefits of state-of-the-art memory-efficient (TTK CompactTriangulation) and time-efficient (TTK ExplicitTriangulation) topological data structures. It occupies a similar amount of memory as TTK CompactTriangulation while providing up to 5x speedup. Moreover, it achieves comparable time performance as TTK ExplicitTriangulation while using only half of the memory space.
AskIt: Unified Programming Interface for Programming with Large Language Models
Venue: arXiv cs.PL 2023
Year: 2023

Large Language Models (LLMs) exhibit a unique phenomenon known as emergent abilities, demonstrating adeptness across numerous tasks, from text summarization to code generation. While these abilities open up novel avenues in software design and crafting, their incorporation presents substantial challenges. Developers face decisions regarding the use of LLMs for directly performing tasks within applications as well as for generating and executing code to accomplish these tasks. Moreover, effective prompt design becomes a critical concern, given the necessity of extracting data from natural language outputs. To address these complexities, this paper introduces AskIt, a domain-specific language (DSL) specifically designed for LLMs. AskIt simplifies LLM integration by providing a unified interface that not only allows for direct task execution using LLMs but also supports the entire cycle of code generation and execution. This dual capability is achieved through (1) type-guided output control, (2) template-based function definitions, and (3) prompt generation for both usage modes. Our evaluations underscore AskIt's effectiveness. Across 50 tasks, AskIt generated concise prompts, achieving a 16.14 % reduction in prompt length compared to benchmarks. Additionally, by enabling a seamless transition between using LLMs directly in applications and for generating code, AskIt achieved significant efficiency improvements, as observed in our GSM8K benchmark experiments. The implementations of AskIt in TypeScript and Python are available at https://github.com/katsumiok/ts-askit and https://github.com/katsumiok/pyaskit, respectively.
A General Recipe for Automated Machine Learning in Practice
Venue: arXiv cs.LG 2023
Year: 2023

Automated Machine Learning (AutoML) is an area of research that focuses on developing methods to generate machine learning models automatically. The idea of being able to build machine learning models with very little human intervention represents a great opportunity for the practice of applied machine learning. However, there is very little information on how to design an AutoML system in practice. Most of the research focuses on the problems facing optimization algorithms and leaves out the details of how that would be done in practice. In this paper, we propose a frame of reference for building general AutoML systems. Through a narrative review of the main approaches in the area, our main idea is to distill the fundamental concepts in order to support them in a single design. Finally, we discuss some open problems related to the application of AutoML for future research.
Deep Reinforcement Learning Based Framework for Mobile Energy Disseminator Dispatching to Charge On-the-Road Electric Vehicles
Venue: arXiv cs.RO 2023
Year: 2023

The exponential growth of electric vehicles (EVs) presents novel challenges in preserving battery health and in addressing the persistent problem of vehicle range anxiety. To address these concerns, wireless charging, particularly, Mobile Energy Disseminators (MEDs) have emerged as a promising solution. The MED is mounted behind a large vehicle and charges all participating EVs within a radius upstream of it. Unfortuantely, during such V2V charging, the MED and EVs inadvertently form platoons, thereby occupying multiple lanes and impairing overall corridor travel efficiency. In addition, constrained budgets for MED deployment necessitate the development of an effective dispatching strategy to determine optimal timing and locations for introducing the MEDs into traffic. This paper proposes a deep reinforcement learning (DRL) based methodology to develop a vehicle dispatching framework. In the first component of the framework, we develop a realistic reinforcement learning environment termed "ChargingEnv" which incorporates a reliable charging simulation system that accounts for common practical issues in wireless charging deployment, specifically, the charging panel misalignment. The second component, the Proximal-Policy Optimization (PPO) agent, is trained to control MED dispatching through continuous interactions with ChargingEnv. Numerical experiments were carried out to demonstrate the demonstrate the efficacy of the proposed MED deployment decision processor. The experiment results suggest that the proposed model can significantly enhance EV travel range while efficiently deploying a optimal number of MEDs. The proposed model is found to be not only practical in its applicability but also has promises of real-world effectiveness. The proposed model can help travelers to maximize EV range and help road agencies or private-sector vendors to manage the deployment of MEDs efficiently.
Bridging Distribution Learning and Image Clustering in High-dimensional Space
Venue: arXiv cs.LG 2023
Year: 2023

Distribution learning focuses on learning the probability density function from a set of data samples. In contrast, clustering aims to group similar objects together in an unsupervised manner. Usually, these two tasks are considered unrelated. However, the relationship between the two may be indirectly correlated, with Gaussian Mixture Models (GMM) acting as a bridge. In this paper, we focus on exploring the correlation between distribution learning and clustering, with the motivation to fill the gap between these two fields, utilizing an autoencoder (AE) to encode images into a high-dimensional latent space. Then, Monte-Carlo Marginalization (MCMarg) and Kullback-Leibler (KL) divergence loss are used to fit the Gaussian components of the GMM and learn the data distribution. Finally, image clustering is achieved through each Gaussian component of GMM. Yet, the "curse of dimensionality" poses severe challenges for most clustering algorithms. Compared with the classic Expectation-Maximization (EM) Algorithm, experimental results show that MCMarg and KL divergence can greatly alleviate the difficulty. Based on the experimental results, we believe distribution learning can exploit the potential of GMM in image clustering within high-dimensional space.
ACER: An AST-based Call Graph Generator Framework
Venue: arXiv cs.SE 2023
Year: 2023

We introduce ACER, an AST-based call graph generator framework. ACER leverages tree-sitter to interface with any language. We opted to focus on generators that operate on abstract syntax trees (ASTs) due to their speed and simplicitly in certain scenarios; however, a fully quantified intermediate representation usually provides far better information at the cost of requiring compilation. To evaluate our framework, we created two context-insensitive Java generators and compared them to existing open-source Java generators.
Lower Bound for Independence Covering in $C_4$-Free Graphs
Venue: arXiv cs.DM 2023
Year: 2023

An independent set in a graph $G$ is a set $S$ of pairwise non-adjacent vertices in $G$. A family $\mathcal{F}$ of independent sets in $G$ is called a $k$-independence covering family if for every independent set $I$ in $G$ of size at most $k$, there exists an $S \in \mathcal{F}$ such that $I \subseteq S$. Lokshtanov et al. [ACM Transactions on Algorithms, 2018] showed that graphs of degeneracy $d$ admit $k$-independence covering families of size $\binom{k(d+1)}{k} \cdot 2^{o(kd)} \cdot \log n$, and used this result to design efficient parameterized algorithms for a number of problems, including STABLE ODD CYCLE TRANSVERSAL and STABLE MULTICUT. In light of the results of Lokshtanov et al. it is quite natural to ask whether even more general families of graphs admit $k$-independence covering families of size $f(k)n^{O(1)}$. Graphs that exclude a complete bipartite graph $K_{d+1,d+1}$ with $d+1$ vertices on both sides as a subgraph, called $K_{d+1,d+1}$-free graphs, are a frequently considered generalization of $d$-degenerate graphs. This motivates the question whether $K_{d,d}$-free graphs admit $k$-independence covering families of size $f(k,d)n^{O(1)}$. Our main result is a resounding "no" to this question -- specifically we prove that even $K_{2,2}$-free graphs (or equivalently $C_4$-free graphs) do not admit $k$-independence covering families of size $f(k)n^{\frac{k}{4}-ε}$.
Predict And Prevent DDOS Attacks Using Machine Learning and Statistical Algorithms
Venue: arXiv cs.CR 2023
Year: 2023

A malicious attempt to exhaust a victim's resources to cause it to crash or halt its services is known as a distributed denial-of-service (DDoS) attack. DDOS attacks stop authorized users from accessing specific services available on the Internet. It targets varying components of a network layer and it is better to stop into layer 4 (transport layer) of the network before approaching a higher layer. This study uses several machine learning and statistical models to detect DDoS attacks from traces of traffic flow and suggests a method to prevent DDOS attacks. For this purpose, we used logistic regression, CNN, XGBoost, naive Bayes, AdaBoostClassifier, KNN, and random forest ML algorithms. In addition, data preprocessing was performed using three methods to identify the most relevant features. This paper explores the issue of improving the DDOS attack detection accuracy using the latest dataset named CICDDoS2019, which has over 50 million records. Because we employed an extensive dataset for this investigation, our findings are trustworthy and practical. Our target class (attack class) was imbalanced. Therefore, we used two techniques to deal with imbalanced data in machine learning. The XGboost machine learning model provided the best detection accuracy of (99.9999%) after applying the SMOTE approach to the target class, outperforming recently developed DDoS detection systems. To the best of our knowledge, no other research has worked on the most recent dataset with over 50 million records, addresses the statistical technique to select the most significant feature, has this high accuracy, and suggests ways to avoid DDOS attackI.
Investigating Quantitative-Qualitative Topical Preference: A Comparative Study of Early and Late Engagers in Japanese ChatGPT Conversations
Venue: arXiv cs.SI 2023
Year: 2023

This study investigates engagement patterns related to OpenAI's ChatGPT on Japanese Twitter, focusing on two distinct user groups - early and late engagers, inspired by the Innovation Theory. Early engagers are defined as individuals who initiated conversations about ChatGPT during its early stages, whereas late engagers are those who began participating at a later date. To examine the nature of the conversations, we employ a dual methodology, encompassing both quantitative and qualitative analyses. The quantitative analysis reveals that early engagers often engage with more forward-looking and speculative topics, emphasizing the technological advancements and potential transformative impact of ChatGPT. Conversely, the late engagers intereact more with contemporary topics, focusing on the optimization of existing AI capabilities and considering their inherent limitations. Through our qualitative analysis, we propose a method to measure the proportion of shared or unique viewpoints within topics across both groups. We found that early engagers generally concentrate on a more limited range of perspectives, whereas late engagers exhibit a wider range of viewpoints. Interestingly, a weak correlation was found between the volume of tweets and the diversity of discussed topics in both groups. These findings underscore the importance of identifying semantic bias, rather than relying solely on the volume of tweets, for understanding differences in communication styles between groups within a given topic. Moreover, our versatile dual methodology holds potential for broader applications, such as studying engagement patterns within different user groups, or in contexts beyond ChatGPT.
Towards a Rigorous Analysis of Mutual Information in Contrastive Learning
Venue: arXiv cs.AI 2023
Year: 2023

Contrastive learning has emerged as a cornerstone in recent achievements of unsupervised representation learning. Its primary paradigm involves an instance discrimination task with a mutual information loss. The loss is known as InfoNCE and it has yielded vital insights into contrastive learning through the lens of mutual information analysis. However, the estimation of mutual information can prove challenging, creating a gap between the elegance of its mathematical foundation and the complexity of its estimation. As a result, drawing rigorous insights or conclusions from mutual information analysis becomes intricate. In this study, we introduce three novel methods and a few related theorems, aimed at enhancing the rigor of mutual information analysis. Despite their simplicity, these methods can carry substantial utility. Leveraging these approaches, we reassess three instances of contrastive learning analysis, illustrating their capacity to facilitate deeper comprehension or to rectify pre-existing misconceptions. Specifically, we investigate small batch size, mutual information as a measure, and the InfoMin principle.
Towards Earlier Detection of Oral Diseases On Smartphones Using Oral and Dental RGB Images
Venue: arXiv cs.CV 2023
Year: 2023

Oral diseases such as periodontal (gum) diseases and dental caries (cavities) affect billions of people across the world today. However, previous state-of-the-art models have relied on X-ray images to detect oral diseases, making them inaccessible to remote monitoring, developing countries, and telemedicine. To combat this overuse of X-ray imagery, we propose a lightweight machine learning model capable of detecting calculus (also known as hardened plaque or tartar) in RGB images while running efficiently on low-end devices. The model, a modified MobileNetV3-Small neural network transfer learned from ImageNet, achieved an accuracy of 72.73% (which is comparable to state-of-the-art solutions) while still being able to run on mobile devices due to its reduced memory requirements and processing times. A ResNet34-based model was also constructed and achieved an accuracy of 81.82%. Both of these models were tested on a mobile app, demonstrating their potential to limit the number of serious oral disease cases as their predictions can help patients schedule appointments earlier without the need to go to the clinic.
Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuation
Venue: arXiv cs.LG 2023
Year: 2023

Data valuation aims to quantify the usefulness of individual data sources in training machine learning (ML) models, and is a critical aspect of data-centric ML research. However, data valuation faces significant yet frequently overlooked privacy challenges despite its importance. This paper studies these challenges with a focus on KNN-Shapley, one of the most practical data valuation methods nowadays. We first emphasize the inherent privacy risks of KNN-Shapley, and demonstrate the significant technical difficulties in adapting KNN-Shapley to accommodate differential privacy (DP). To overcome these challenges, we introduce TKNN-Shapley, a refined variant of KNN-Shapley that is privacy-friendly, allowing for straightforward modifications to incorporate DP guarantee (DP-TKNN-Shapley). We show that DP-TKNN-Shapley has several advantages and offers a superior privacy-utility tradeoff compared to naively privatized KNN-Shapley in discerning data quality. Moreover, even non-private TKNN-Shapley achieves comparable performance as KNN-Shapley. Overall, our findings suggest that TKNN-Shapley is a promising alternative to KNN-Shapley, particularly for real-world applications involving sensitive data.
Speech Wikimedia: A 77 Language Multilingual Speech Dataset
Venue: arXiv cs.AI 2023
Year: 2023

The Speech Wikimedia Dataset is a publicly available compilation of audio with transcriptions extracted from Wikimedia Commons. It includes 1780 hours (195 GB) of CC-BY-SA licensed transcribed speech from a diverse set of scenarios and speakers, in 77 different languages. Each audio file has one or more transcriptions in different languages, making this dataset suitable for training speech recognition, speech translation, and machine translation models.
Optimizing Factual Accuracy in Text Generation through Dynamic Knowledge Selection
Venue: arXiv cs.CL 2023
Year: 2023

Language models (LMs) have revolutionized the way we interact with information, but they often generate nonfactual text, raising concerns about their reliability. Previous methods use external knowledge as references for text generation to enhance factuality but often struggle with the knowledge mix-up(e.g., entity mismatch) of irrelevant references. Besides,as the length of the output text grows, the randomness of sampling can escalate, detrimentally impacting the factual accuracy of the generated text. In this paper, we present DKGen, which divide the text generation process into an iterative process. In each iteration, DKGen takes the input query, the previously generated text and a subset of the reference passages as input to generate short text. During the process, the subset is dynamically selected from the full passage set based on their relevance to the previously generated text and the query, largely eliminating the irrelevant references from input. To further enhance DKGen's ability to correctly use these external knowledge, DKGen distills the relevance order of reference passages to the cross-attention distribution of decoder. We train and evaluate DKGen on a large-scale benchmark dataset. Experiment results show that DKGen outperforms all baseline models.