OpenRaiser/Intern-Atlas huggingface dataset:
Constructing $k$-ary Orientable Sequences with Asymptotically Optimal Length
Venue: arXiv cs.DM 2024
Year: 2024

An orientable sequence of order $n$ over an alphabet $\{0,1,\ldots, k{-}1\}$ is a cyclic sequence such that each length-$n$ substring appears at most once \emph{in either direction}. When $k= 2$, efficient algorithms are known to construct binary orientable sequences, with asymptotically optimal length, by applying the classic cycle-joining technique. The key to the construction is the definition of a parent rule to construct a cycle-joining tree of asymmetric bracelets. Unfortunately, the parent rule does not generalize to larger alphabets. Furthermore, unlike the binary case, a cycle-joining tree does not immediately lead to a simple successor-rule when $k \geq 3$ unless the tree has certain properties. In this paper, we derive a parent rule to derive a cycle-joining tree of $k$-ary asymmetric bracelets. This leads to a successor rule that constructs asymptotically optimal $k$-ary orientable sequences in $O(n)$ time per symbol using $O(n)$ space. In the special case when $n=2$, we provide a simple construction of $k$-ary orientable sequences of maximal length.
Decoding Climate Disagreement: A Graph Neural Network-Based Approach to Understanding Social Media Dynamics
Venue: arXiv cs.CL 2024
Year: 2024

This work introduces the ClimateSent-GAT Model, an innovative method that integrates Graph Attention Networks (GATs) with techniques from natural language processing to accurately identify and predict disagreements within Reddit comment-reply pairs. Our model classifies disagreements into three categories: agree, disagree, and neutral. Leveraging the inherent graph structure of Reddit comment-reply pairs, the model significantly outperforms existing benchmarks by capturing complex interaction patterns and sentiment dynamics. This research advances graph-based NLP methodologies and provides actionable insights for policymakers and educators in climate science communication.
Simple and Interpretable Probabilistic Classifiers for Knowledge Graphs
Venue: arXiv cs.AI 2024
Year: 2024

Tackling the problem of learning probabilistic classifiers from incomplete data in the context of Knowledge Graphs expressed in Description Logics, we describe an inductive approach based on learning simple belief networks. Specifically, we consider a basic probabilistic model, a Naive Bayes classifier, based on multivariate Bernoullis and its extension to a two-tier network in which this classification model is connected to a lower layer consisting of a mixture of Bernoullis. We show how such models can be converted into (probabilistic) axioms (or rules) thus ensuring more interpretability. Moreover they may be also initialized exploiting expert knowledge. We present and discuss the outcomes of an empirical evaluation which aimed at testing the effectiveness of the models on a number of random classification problems with different ontologies.
A Differentially Private Blockchain-Based Approach for Vertical Federated Learning
Venue: arXiv cs.CR 2024
Year: 2024

We present the Differentially Private Blockchain-Based Vertical Federal Learning (DP-BBVFL) algorithm that provides verifiability and privacy guarantees for decentralized applications. DP-BBVFL uses a smart contract to aggregate the feature representations, i.e., the embeddings, from clients transparently. We apply local differential privacy to provide privacy for embeddings stored on a blockchain, hence protecting the original data. We provide the first prototype application of differential privacy with blockchain for vertical federated learning. Our experiments with medical data show that DP-BBVFL achieves high accuracy with a tradeoff in training time due to on-chain aggregation. This innovative fusion of differential privacy and blockchain technology in DP-BBVFL could herald a new era of collaborative and trustworthy machine learning applications across several decentralized application domains.
Spectral Toolkit of Algorithms for Graphs: Technical Report (2)
Venue: arXiv cs.DS 2024
Year: 2024

Spectral Toolkit of Algorithms for Graphs (STAG) is an open-source library for efficient graph algorithms. This technical report presents the newly implemented component on locality sensitive hashing, kernel density estimation, and fast spectral clustering. The report includes a user's guide to the newly implemented algorithms, experiments and demonstrations of the new functionality, and several technical considerations behind our development.
Diffusion Model-Based Video Editing: A Survey
Venue: arXiv cs.CV 2024
Year: 2024

The rapid development of diffusion models (DMs) has significantly advanced image and video applications, making "what you want is what you see" a reality. Among these, video editing has gained substantial attention and seen a swift rise in research activity, necessitating a comprehensive and systematic review of the existing literature. This paper reviews diffusion model-based video editing techniques, including theoretical foundations and practical applications. We begin by overviewing the mathematical formulation and image domain's key methods. Subsequently, we categorize video editing approaches by the inherent connections of their core technologies, depicting evolutionary trajectory. This paper also dives into novel applications, including point-based editing and pose-guided human video editing. Additionally, we present a comprehensive comparison using our newly introduced V2VBench. Building on the progress achieved to date, the paper concludes with ongoing challenges and potential directions for future research.
Support and Scandals in GameFi dApps: A Network Analysis of The Sandbox Transactions
Venue: arXiv cs.SI 2024
Year: 2024

We explore the burgeoning field of GameFi through a detailed network analysis of The Sandbox, a prominent decentralized application (dApp) in this domain. Utilizing the bow-tie model, we map out transaction data within The Sandbox, providing a novel perspective on its operational dynamics. Our study investigates the varying impacts of external support, uncovering a surprising absence of enduring effects on network activity. We also investigate the network's response to several notable incidents, including the Ronin Hack and the United States Securities and Exchange Commission's hearing on cryptocurrencies, revealing a generally resilient structure with limited long-term disturbances. A critical aspect of our analysis focuses on the "whales," or major stakeholders in The Sandbox, where we uncover their pivotal role in influencing network trends, noting a significant shift in their engagement over time. This research sheds light on the intricate workings of GameFi ecosystems and contributes to the broader discourse on the intersection of the Web, AI, and society, particularly in understanding the resilience and dynamics of emerging digital economies. We particularly note the parallels of the long-tail behavior we see in web-based ecosystems appearing in this niche domain of GameFi. Our findings hold significant implications for the future development of equitable and sustainable GameFi dApps, offering insights into stakeholder behavior and network resilience in the face of external challenges and opportunities.
Large Language Models for Wearable Sensor-Based Human Activity Recognition, Health Monitoring, and Behavioral Modeling: A Survey of Early Trends, Datasets, and Challenges
Venue: arXiv cs.HC 2024
Year: 2024

The proliferation of wearable technology enables the generation of vast amounts of sensor data, offering significant opportunities for advancements in health monitoring, activity recognition, and personalized medicine. However, the complexity and volume of this data present substantial challenges in data modeling and analysis, which have been tamed with approaches spanning time series modeling to deep learning techniques. The latest frontier in this domain is the adoption of Large Language Models (LLMs), such as GPT-4 and Llama, for data analysis, modeling, understanding, and generation of human behavior through the lens of wearable sensor data. This survey explores current trends and challenges in applying LLMs for sensor-based human activity recognition and behavior modeling. We discuss the nature of wearable sensors data, the capabilities and limitations of LLMs to model them and their integration with traditional machine learning techniques. We also identify key challenges, including data quality, computational requirements, interpretability, and privacy concerns. By examining case studies and successful applications, we highlight the potential of LLMs in enhancing the analysis and interpretation of wearable sensors data. Finally, we propose future directions for research, emphasizing the need for improved preprocessing techniques, more efficient and scalable models, and interdisciplinary collaboration. This survey aims to provide a comprehensive overview of the intersection between wearable sensors data and LLMs, offering insights into the current state and future prospects of this emerging field.
Uncovering the Interaction Equation: Quantifying the Effect of User Interactions on Social Media Homepage Recommendations
Venue: arXiv cs.SI 2024
Year: 2024

Social media platforms depend on algorithms to select, curate, and deliver content personalized for their users. These algorithms leverage users' past interactions and extensive content libraries to retrieve and rank content that personalizes experiences and boosts engagement. Among various modalities through which this algorithmically curated content may be delivered, the homepage feed is the most prominent. This paper presents a comprehensive study of how prior user interactions influence the content presented on users' homepage feeds across three major platforms: YouTube, Reddit, and X (formerly Twitter). We use a series of carefully designed experiments to gather data capable of uncovering the influence of specific user interactions on homepage content. This study provides insights into the behaviors of the content curation algorithms used by each platform, how they respond to user interactions, and also uncovers evidence of deprioritization of specific topics.
Service Colonies: A Novel Architectural Style for Developing Software Systems with Autonomous and Cooperative Services
Venue: arXiv cs.SE 2024
Year: 2024

This paper presents the concept of a service colony and its characteristics. A service colony is a novel architectural style for developing a software system as a group of autonomous software services co-operating to fulfill the objectives of the system. Each inhabitant service in the colony implements a specific system functionality, collaborates with the other services, and makes proactive decisions that impact its performance and interaction patterns with other inhabitants. By increasing the level of self-awareness and autonomy available to individual system components, the resulting system is increasingly more decentralized, distributed, flexible, adaptable, distributed, modular, robust, and fault-tolerant.
Structural Design Through Reinforcement Learning
Venue: arXiv cs.AI 2024
Year: 2024

This paper introduces the Structural Optimization gym (SOgym), a novel open-source Reinforcement Learning (RL) environment designed to advance machine learning in Topology Optimization (TO). SOgym enables RL agents to generate physically viable and structurally robust designs by integrating the physics of TO into the reward function. To enhance scalability, SOgym leverages feature-mapping methods as a mesh-independent interface between the environment and the agent, allowing efficient interaction with the design variables regardless of mesh resolution. Baseline results use a model-free Proximal Policy Optimization agent and a model-based DreamerV3 agent. Three observation space configurations were tested. The TopOpt game-inspired configuration, an interactive educational tool that improves students' intuition in designing structures to minimize compliance under volume constraints, performed best in terms of performance and sample efficiency. The 100M parameter version of DreamerV3 produced structures within 54% of the baseline compliance achieved by traditional optimization methods and a 0% disconnection rate, an improvement over supervised learning approaches that often struggle with disconnected load paths. When comparing the learning rates of the agents to those of engineering students from the TopOpt game experiment, the DreamerV3-100M model shows a learning rate approximately four orders of magnitude lower, an impressive feat for a policy trained from scratch through trial and error. These results suggest RL's potential to solve continuous TO problems and its capacity to explore and learn from diverse design solutions. SOgym provides a platform for developing RL agents for complex structural design challenges and is publicly available to support further research in the field.
Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
Venue: arXiv cs.IT 2024
Year: 2024

In this paper, we prove that with high probability, random Reed-Solomon codes approach the half-Singleton bound - the optimal rate versus error tradeoff for linear insdel codes - with linear-sized alphabets. More precisely, we prove that, for any $ε>0$ and positive integers $n$ and $k$, with high probability, random Reed--Solomon codes of length $n$ and dimension $k$ can correct $(1-\varepsilon)n-2k+1$ adversarial insdel errors over alphabets of size $n+2^{\mathsf{poly}(1/\varepsilon)}k$. This significantly improves upon the alphabet size demonstrated in the work of Con, Shpilka, and Tamo (IEEE TIT, 2023), who showed the existence of Reed--Solomon codes with exponential alphabet size $\widetilde O\left(\binom{n}{2k-1}^2\right)$ precisely achieving the half-Singleton bound. Our methods are inspired by recent works on list-decoding Reed-Solomon codes. Brakensiek-Gopi-Makam (STOC 2023) showed that random Reed-Solomon codes are list-decodable up to capacity with exponential-sized alphabets, and Guo-Zhang (FOCS 2023) and Alrabiah-Guruswami-Li (STOC 2024) improved the alphabet-size to linear. We achieve a similar alphabet-size reduction by similarly establishing strong bounds on the probability that certain random rectangular matrices are full rank. To accomplish this in our insdel context, our proof combines the random matrix techniques from list-decoding with structural properties of Longest Common Subsequences.
BoostCom: Towards Efficient Universal Fully Homomorphic Encryption by Boosting the Word-wise Comparisons
Venue: arXiv cs.CR 2024
Year: 2024

Fully Homomorphic Encryption (FHE) allows for the execution of computations on encrypted data without the need to decrypt it first, offering significant potential for privacy-preserving computational operations. Emerging arithmetic-based FHE schemes (ar-FHE), like BGV, demonstrate even better performance in word-wise comparison operations over non-arithmetic FHE (na-FHE) schemes, such as TFHE, especially for basic tasks like comparing values, finding maximums, and minimums. This shows the universality of ar-FHE in effectively handling both arithmetic and non-arithmetic operations without the expensive conversion between arithmetic and non-arithmetic FHEs. We refer to universal arithmetic Fully Homomorphic Encryption as uFHE. The arithmetic operations in uFHE remain consistent with those in the original arithmetic FHE, which have seen significant acceleration. However, its non-arithmetic comparison operations differ, are slow, and have not been as thoroughly studied or accelerated. In this paper, we introduce BoostCom, a scheme designed to speed up word-wise comparison operations, enhancing the efficiency of uFHE systems. BoostCom involves a multi-prong optimizations including infrastructure acceleration (Multi-level heterogeneous parallelization and GPU-related improvements), and algorithm-aware optimizations (slot compaction, non-blocking comparison semantic). Together, BoostCom achieves an end-to-end performance improvement of more than an order of magnitude (11.1x faster) compared to the state-of-the-art CPU-based uFHE systems, across various FHE parameters and tasks.
Fast Revenue Maximization
Venue: arXiv cs.GT 2024
Year: 2024

Problem definition: We study a data-driven pricing problem in which a seller offers a price for a single item based on demand observed at a small number of historical prices. Our goal is to derive precise evaluation procedures of the value of the historical information gathered by the seller, along with prescriptions for more efficient price experimentation. Methodology/results: Our main methodological result is an exact characterization of the maximin ratio (defined as the worst-case revenue garnered by a seller who only relies on past data divided by the optimal revenue achievable with full knowledge of the distribution of values). This result allows to measure the value of any historical data consisting of prices and corresponding conversion rates. We leverage this central reduction to provide new insights about price experimentation. Managerial implications: Motivated by practical constraints that impede the seller from changing prices abruptly, we first illustrate our framework by evaluating the value of local information and show that the mere sign of the gradient of the revenue curve at a single point can provide significant information to the seller. We then showcase how our framework can be used to run efficient price experiments. On the one hand, we develop a method to select the next price experiment that the seller should use to maximize the future robust performance. On the other hand, we demonstrate that our result allows to considerably reduce the number of price experiments needed to reach preset revenue guarantees through dynamic pricing algorithms.
HiLight: Technical Report on the Motern AI Video Language Model
Venue: arXiv cs.CV 2024
Year: 2024

This technical report presents the implementation of a state-of-the-art video encoder for video-text modal alignment and a video conversation framework called HiLight, which features dual visual towers. The work is divided into two main parts: 1.alignment of video and text modalities; 2.convenient and efficient way to interact with users. Our goal is to address the task of video comprehension in the context of billiards. The report includes a discussion of the concepts and the final solution developed during the task's implementation.
Probability of Differentiation Reveals Brittleness of Homogeneity Bias in GPT-4
Venue: arXiv cs.CL 2024
Year: 2024

Homogeneity bias in Large Language Models (LLMs) refers to their tendency to homogenize the representations of some groups compared to others. Previous studies documenting this bias have predominantly used encoder models, which may have inadvertently introduced biases. To address this limitation, we prompted GPT-4 to generate single word/expression completions associated with 18 situation cues-specific, measurable elements of environments that influence how individuals perceive situations and compared the variability of these completions using probability of differentiation. This approach directly assessed homogeneity bias from the model's outputs, bypassing encoder models. Across five studies, we find that homogeneity bias is highly volatile across situation cues and writing prompts, suggesting that the bias observed in past work may reflect those within encoder models rather than LLMs. Furthermore, we find that homogeneity bias in LLMs is brittle, as even minor and arbitrary changes in prompts can significantly alter the expression of biases. Future work should further explore how variations in syntactic features and topic choices in longer text generations influence homogeneity bias in LLMs.
INSIGHT: Universal Neural Simulator for Analog Circuits Harnessing Autoregressive Transformers
Venue: arXiv cs.LG 2024
Year: 2024

Analog front-end design heavily relies on specialized human expertise and costly trial-and-error simulations, which motivated many prior works on analog design automation. However, efficient and effective exploration of the vast and complex design space remains constrained by the time-consuming nature of SPICE simulations, making effective design automation a challenging endeavor. In this paper, we introduce INSIGHT, a GPU-powered, technology-agnostic, effective universal neural simulator in the analog front-end design automation loop. INSIGHT accurately predicts the performance metrics of analog circuits across various technologies with just a few microseconds of inference time. Notably, its autoregressive capabilities enable INSIGHT to accurately predict simulation-costly critical transient specifications leveraging less expensive performance metric information. The low cost and high fidelity feature make INSIGHT a good substitute for standard simulators in analog front-end optimization frameworks. INSIGHT is compatible with any optimization framework, facilitating enhanced design space exploration for sample efficiency through sophisticated offline learning and adaptation techniques. Our experiments demonstrate that INSIGHT-M, a model-based batch reinforcement learning sizing framework with INSIGHT as the accurate surrogate, only requires < 20 real-time simulations with 100-1000x lower simulation costs and significant speedup over existing sizing methods.
Towards a text-based quantitative and explainable histopathology image analysis
Venue: arXiv cs.CV 2024
Year: 2024

Recently, vision-language pre-trained models have emerged in computational pathology. Previous works generally focused on the alignment of image-text pairs via the contrastive pre-training paradigm. Such pre-trained models have been applied to pathology image classification in zero-shot learning or transfer learning fashion. Herein, we hypothesize that the pre-trained vision-language models can be utilized for quantitative histopathology image analysis through a simple image-to-text retrieval. To this end, we propose a Text-based Quantitative and Explainable histopathology image analysis, which we call TQx. Given a set of histopathology images, we adopt a pre-trained vision-language model to retrieve a word-of-interest pool. The retrieved words are then used to quantify the histopathology images and generate understandable feature embeddings due to the direct mapping to the text description. To evaluate the proposed method, the text-based embeddings of four histopathology image datasets are utilized to perform clustering and classification tasks. The results demonstrate that TQx is able to quantify and analyze histopathology images that are comparable to the prevalent visual models in computational pathology.
LokiLM: Technical Report
Venue: arXiv cs.CL 2024
Year: 2024

In this work, we introduce LokiLM, a 1.4B parameter large language model trained on 500B tokens. Our model performs strongly in natural language reasoning tasks and achieves state-of-the-art performance among models with 1.5B parameters or less. LokiLM is trained using multi-teacher knowledge distillation and high-quality training data to achieve benchmark results competitive with larger models trained on significantly more tokens. We support these findings by introducing steps to avoid benchmark contamination and overfitting throughout our development process. Despite its promising performance, LokiLM exhibits a concerning amount of hallucinations and scores poorly on the TruthfulQA benchmark, so we do not release the model publicly.