OpenRaiser/Intern-Atlas huggingface dataset:
Quantitative Global Carbon Inequality Network
Venue: arXiv cs.SI 2024
Year: 2024

International trading networks significantly influence global economic conditions and environmental outcomes. A notable imbalance between economic gains and emissions transfers persists, manifesting as carbon inequality. This study introduces a novel metric, the Ecological Economic Equality Index, integrated with complex network dynamics analysis, to quantitatively evaluate the evolving roles within the global trading network and to pinpoint inequities in trade relationships from 1995 to 2022. Utilising high spatiotemporal resolution data from the Environmentally Extended Multi-regional Input-output model, our findings reveal a widening disparity in carbon inequality and dynamic patterns. This analysis emphasises the gap in regional carbon inequality and identifies unequal trade. The study underscores that carbon inequality is a critical challenge affecting both developing and developed regions, demanding widespread attention and action.
Multi-Scale Temporal Difference Transformer for Video-Text Retrieval
Venue: arXiv cs.CV 2024
Year: 2024

Currently, in the field of video-text retrieval, there are many transformer-based methods. Most of them usually stack frame features and regrade frames as tokens, then use transformers for video temporal modeling. However, they commonly neglect the inferior ability of the transformer modeling local temporal information. To tackle this problem, we propose a transformer variant named Multi-Scale Temporal Difference Transformer (MSTDT). MSTDT mainly addresses the defects of the traditional transformer which has limited ability to capture local temporal information. Besides, in order to better model the detailed dynamic information, we make use of the difference feature between frames, which practically reflects the dynamic movement of a video. We extract the inter-frame difference feature and integrate the difference and frame feature by the multi-scale temporal transformer. In general, our proposed MSTDT consists of a short-term multi-scale temporal difference transformer and a long-term temporal transformer. The former focuses on modeling local temporal information, the latter aims at modeling global temporal information. At last, we propose a new loss to narrow the distance of similar samples. Extensive experiments show that backbone, such as CLIP, with MSTDT has attained a new state-of-the-art result.
Multimodal Multilabel Classification by CLIP
Venue: arXiv cs.CV 2024
Year: 2024

Multimodal multilabel classification (MMC) is a challenging task that aims to design a learning algorithm to handle two data sources, the image and text, and learn a comprehensive semantic feature presentation across the modalities. In this task, we review the extensive number of state-of-the-art approaches in MMC and leverage a novel technique that utilises the Contrastive Language-Image Pre-training (CLIP) as the feature extractor and fine-tune the model by exploring different classification heads, fusion methods and loss functions. Finally, our best result achieved more than 90% F_1 score in the public Kaggle competition leaderboard. This paper provides detailed descriptions of novel training methods and quantitative analysis through the experimental results.
LeanBin: Harnessing Lifting and Recompilation to Debloat Binaries
Venue: arXiv cs.SE 2024
Year: 2024

To reduce the source of potential exploits, binary debloating or specialization tools are used to remove unnecessary code from binaries. This paper presents a new binary debloating and specialization tool, LeanBin, that harnesses lifting and recompilation, based on observed execution traces. The dynamically recorded execution traces capture the required subset of instructions and control flow of the application binary for a given set of inputs. This initial control flow is subsequently augmented using heuristic-free static analysis to avoid excessively restricting the input space. The further structuring of the control flow and translation of binary instructions into a subset of C enables a lightweight generation of the code that can be recompiled, obtaining LLVM IR and a new debloated binary. Unlike most debloating approaches, LeanBin enables both binary debloating of the application and shared libraries, while reusing the existing compiler infrastructure. Additionally, unlike existing binary lifters, it does not rely on potentially unsound heuristics used by static lifters, nor suffers from long execution times, a limitation of existing dynamic lifters. Instead, LeanBin combines both heuristic-free static and dynamic analysis. The run time of lifting and debloating SPEC CPU2006 INT benchmarks has a geomean of 1.78$\times$, normalized to the native execution, and the debloated binary runs with a geomean overhead of 1.21$\times$. The percentage of gadgets, compared to the original binary, has a geomean between 24.10% and 30.22%, depending on the debloating strategy; and the code size can be as low as 53.59%. For the SQLite use-case, LeanBin debloats a binary including its shared library and generates a debloated binary that runs up to 1.24$\times$ faster with 3.65% gadgets.
Provable Statistical Rates for Consistency Diffusion Models
Venue: arXiv cs.LG 2024
Year: 2024

Diffusion models have revolutionized various application domains, including computer vision and audio generation. Despite the state-of-the-art performance, diffusion models are known for their slow sample generation due to the extensive number of steps involved. In response, consistency models have been developed to merge multiple steps in the sampling process, thereby significantly boosting the speed of sample generation without compromising quality. This paper contributes towards the first statistical theory for consistency models, formulating their training as a distribution discrepancy minimization problem. Our analysis yields statistical estimation rates based on the Wasserstein distance for consistency models, matching those of vanilla diffusion models. Additionally, our results encompass the training of consistency models through both distillation and isolation methods, demystifying their underlying advantage.
On The Effectiveness of Dynamic Reduction Techniques in Automated Program Repair
Venue: arXiv cs.SE 2024
Year: 2024

Repairing a large-scale buggy program using current automated program repair (APR) approaches can be a time-consuming operation that requires significant computational resources. We describe a program repair framework that effectively handles large-scale buggy programs of industrial complexity. The framework exploits program reduction in the form of program slicing to eliminate parts of the code irrelevant to the bug being repaired without adversely affecting the capability of the repair system in producing correct patches. Observation-based slicing is a recently introduced, language-independent slicing technique that shows a good effectiveness in a wide range of applications. In this work, we show how ORBS can be effectively integrated with APR to improve all aspects of the repair process including the fault localization step, patch generation step, and patch validation step. The presented repair framework indeed enhances the capability of APR by reducing the execution cost of a test suite and the search cost for the appropriate faulty statement corresponding to the bug being repair. Our empirical results on the widely used Defects4J dataset reveal that a substantial improvement in performance can be obtained without any degradation in repair quality.
Evaluating Serverless Machine Learning Performance on Google Cloud Run
Venue: arXiv cs.DC 2024
Year: 2024

End-users can get functions-as-a-service from serverless platforms, which promise lower hosting costs, high availability, fault tolerance, and dynamic flexibility for hosting individual functions known as microservices. Machine learning tools are seen to be reliably useful, and the services created using these tools are in increasing demand on a large scale. The serverless platforms are uniquely suited for hosting these machine learning services to be used for large-scale applications. These platforms are well known for their cost efficiency, fault tolerance, resource scaling, robust APIs for communication, and global reach. However, machine learning services are different from the web-services in that these serverless platforms were originally designed to host web services. We aimed to understand how these serverless platforms handle machine learning workloads with our study. We examine machine learning performance on one of the serverless platforms - Google Cloud Run, which is a GPU-less infrastructure that is not designed for machine learning application deployment.
Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams
Venue: arXiv cs.DS 2024
Year: 2024

Identifying heavy hitters and estimating the frequencies of flows are fundamental tasks in various network domains. Existing approaches to this challenge can broadly be categorized into two groups, hashing-based and competing-counter-based. The Count-Min sketch is a standard example of a hashing-based algorithm, and the Space Saving algorithm is an example of a competing-counter algorithm. Recent works have explored the use of machine learning to enhance algorithms for frequency estimation problems, under the algorithms with prediction framework. However, these works have focused solely on the hashing-based approach, which may not be best for identifying heavy hitters. In this paper, we present the first learned competing-counter-based algorithm, called LSS, for identifying heavy hitters, top k, and flow frequency estimation that utilizes the well-known Space Saving algorithm. We provide theoretical insights into how and to what extent our approach can improve upon Space Saving, backed by experimental results on both synthetic and real-world datasets. Our evaluation demonstrates that LSS can enhance the accuracy and efficiency of Space Saving in identifying heavy hitters, top k, and estimating flow frequencies.
Thinking Inside The Box: Privacy Against Stronger Adversaries
Venue: arXiv cs.CR 2024
Year: 2024

In this thesis, we study extensions of statistical cryptographic primitives. In particular we study leakage-resilient secret sharing, non-malleable extractors, and immunized ideal one-way functions. The thesis is divided into three main chapters. In the first chapter, we show that 2-out-of-2 leakage resilient (and also non-malleable) secret sharing requires randomness sources that are also extractable. This rules out the possibility of using min-entropic sources. In the second, we introduce collision-resistant seeded extractors and show that any seeded extractor can be made collision resistant at a small overhead in seed length. We then use it to give a two-source non-malleable extractor with entropy rate 0.81 in one source and polylogarithmic in the other. The non-malleable extractor lead to the first statistical privacy amplification protocol against memory tampering adversaries. In the final chapter, we study the hardness of the data structure variant of the 3SUM problem which is motivated by a recent construction to immunise random oracles against pre-processing adversaries. We give worst-case data structure hardness for the 3SUM problem matching known barriers in data structures for adaptive adversaries. We also give a slightly stronger lower bound in the case of non-adaptivity. Lastly, we give a novel result in the bit-probe setting.
DemoRank: Selecting Effective Demonstrations for Large Language Models in Ranking Task
Venue: arXiv cs.IR 2024
Year: 2024

Recently, there has been increasing interest in applying large language models (LLMs) as zero-shot passage rankers. However, few studies have explored how to select appropriate in-context demonstrations for the passage ranking task, which is the focus of this paper. Previous studies mainly use LLM's feedback to train a retriever for demonstration selection. These studies apply the LLM to score each demonstration independently, which ignores the dependencies between demonstrations (especially important in ranking task), leading to inferior performance of top-$k$ retrieved demonstrations. To mitigate this issue, we introduce a demonstration reranker to rerank the retrieved demonstrations so that top-$k$ ranked ones are more suitable for ICL. However, generating training data for such reranker is quite challenging. On the one hand, different from demonstration retriever, the training samples of reranker need to incorporate demonstration dependencies. On the other hand, obtaining the gold ranking from the retrieved demonstrations is an NP-hard problem, which is hard to implement. To overcome these challenges, we propose a method to approximate the optimal demonstration list iteratively and utilize LLM to score demonstration lists of varying lengths. By doing so, the search space is greatly reduced and demonstration dependencies are considered. Based on these scored demonstration lists, we further design a list-pairwise training approach which compares a pair of lists that only differ in the last demonstration, to teach the reranker how to select the next demonstration given a previous sequence. In this paper, we propose a demonstration selection framework DemoRank for ranking task and conduct extensive experiments to prove its strong ability.
Simple Delegated Choice
Venue: arXiv cs.GT 2024
Year: 2024

This paper studies delegation in a model of discrete choice. In the delegation problem, an uninformed principal must consult an informed agent to make a decision. Both the agent and principal have preferences over the decided-upon action which vary based on the state of the world, and which may not be aligned. The principal may commit to a mechanism, which maps reports of the agent to actions. When this mechanism is deterministic, it can take the form of a menu of actions, from which the agent simply chooses upon observing the state. In this case, the principal is said to have delegated the choice of action to the agent. We consider a setting where the decision being delegated is a choice of a utility-maximizing action from a set of several options. We assume the shared portion of the agent's and principal's utilities is drawn from a distribution known to the principal, and that utility misalignment takes the form of a known bias for or against each action. We provide tight approximation analyses for simple threshold policies under three increasingly general sets of assumptions. With independently-distributed utilities, we prove a $3$-approximation. When the agent has an outside option the principal cannot rule out, the constant approximation fails, but we prove a $\log ρ/\log\log ρ$-approximation, where $ρ$ is the ratio of the maximum value to the optimal utility. We also give a weaker but tight bound that holds for correlated values, and complement our upper bounds with hardness results. One special case of our model is utility-based assortment optimization, for which our results are new.
A Survey on Intent-aware Recommender Systems
Venue: arXiv cs.IR 2024
Year: 2024

Many modern online services feature personalized recommendations. A central challenge when providing such recommendations is that the reason why an individual user accesses the service may change from visit to visit or even during an ongoing usage session. To be effective, a recommender system should therefore aim to take the users' probable intent of using the service at a certain point in time into account. In recent years, researchers have thus started to address this challenge by incorporating intent-awareness into recommender systems. Correspondingly, a number of technical approaches were put forward, including diversification techniques, intent prediction models or latent intent modeling approaches. In this paper, we survey and categorize existing approaches to building the next generation of Intent-Aware Recommender Systems (IARS). Based on an analysis of current evaluation practices, we outline open gaps and possible future directions in this area, which in particular include the consideration of additional interaction signals and contextual information to further improve the effectiveness of such systems.
UNO Arena for Evaluating Sequential Decision-Making Capability of Large Language Models
Venue: arXiv cs.CL 2024
Year: 2024

Sequential decision-making refers to algorithms that take into account the dynamics of the environment, where early decisions affect subsequent decisions. With large language models (LLMs) demonstrating powerful capabilities between tasks, we can't help but ask: Can Current LLMs Effectively Make Sequential Decisions? In order to answer this question, we propose the UNO Arena based on the card game UNO to evaluate the sequential decision-making capability of LLMs and explain in detail why we choose UNO. In UNO Arena, We evaluate the sequential decision-making capability of LLMs dynamically with novel metrics based Monte Carlo methods. We set up random players, DQN-based reinforcement learning players, and LLM players (e.g. GPT-4, Gemini-pro) for comparison testing. Furthermore, in order to improve the sequential decision-making capability of LLMs, we propose the TUTRI player, which can involves having LLMs reflect their own actions wtih the summary of game history and the game strategy. Numerous experiments demonstrate that the TUTRI player achieves a notable breakthrough in the performance of sequential decision-making compared to the vanilla LLM player.
Restricted Permutations Enumerated by Inversions
Venue: arXiv cs.DM 2024
Year: 2024

Permutations are usually enumerated by size, but new results can be found by enumerating them by inversions instead, in which case one must restrict one's attention to indecomposable permutations. In the style of the seminal paper by Simion and Schmidt, we investigate all combinations of permutation patterns of length at most 3.
Detecting Isohedral Polyforms with a SAT Solver
Venue: arXiv cs.DM 2024
Year: 2024

I show how to express the question of whether a polyform tiles the plane isohedrally as a Boolean formula that can be tested using a SAT solver. This approach is adaptable to a wide range of polyforms, requires no special-case code for different isohedral tiling types, and integrates seamlessly with existing software for computing Heesch numbers of polyforms.
On the Orthogonality of Generalized Pattern Sequences
Venue: arXiv cs.DM 2024
Year: 2024

The partial sums of integer sequences that count the occurrences of a specific pattern in the binary expansion of positive integers have been investigated by different authors since the 1950s. In this note, we introduce generalized pattern sequences, which count the occurrences of a finite number of different patterns in the expansion of positive integers in any integer base, and analyze their partial sums.
Transient Evaluation of Non-Markovian Models by Stochastic State Classes and Simulation
Venue: arXiv cs.LO 2024
Year: 2024

Non-Markovian models have great expressive power, at the cost of complex analysis of the stochastic process. The method of Stochastic State Classes (SSCs) derives closed-form analytical expressions for the joint Probability Density Functions (PDFs) of the active timers with marginal expolynomial PDF, though being hindered by the number of concurrent non-exponential timers and of discrete events between regenerations. Simulation is an alternative capable of handling the large class of PDFs samplable via inverse transform, which however suffers from rare events. We combine these approaches to analyze time-bounded transient properties of non-Markovian models. We enumerate SSCs near the root of the state-space tree and then rely on simulation to reach the target, affording transient evaluation of models for which the method of SSCs is not viable while reducing computational time and variance of the estimator of transient probabilities with respect to simulation. Promising results are observed in the estimation of rare event probabilities.
Suppressing Uncertainties in Degradation Estimation for Blind Super-Resolution
Venue: arXiv cs.CV 2024
Year: 2024

The problem of blind image super-resolution aims to recover high-resolution (HR) images from low-resolution (LR) images with unknown degradation modes. Most existing methods model the image degradation process using blur kernels. However, this explicit modeling approach struggles to cover the complex and varied degradation processes encountered in the real world, such as high-order combinations of JPEG compression, blur, and noise. Implicit modeling for the degradation process can effectively overcome this issue, but a key challenge of implicit modeling is the lack of accurate ground truth labels for the degradation process to conduct supervised training. To overcome this limitations inherent in implicit modeling, we propose an \textbf{U}ncertainty-based degradation representation for blind \textbf{S}uper-\textbf{R}esolution framework (\textbf{USR}). By suppressing the uncertainty of local degradation representations in images, USR facilitated self-supervised learning of degradation representations. The USR consists of two components: Adaptive Uncertainty-Aware Degradation Extraction (AUDE) and a feature extraction network composed of Variable Depth Dynamic Convolution (VDDC) blocks. To extract Uncertainty-based Degradation Representation from LR images, the AUDE utilizes the Self-supervised Uncertainty Contrast module with Uncertainty Suppression Loss to suppress the inherent model uncertainty of the Degradation Extractor. Furthermore, VDDC block integrates degradation information through dynamic convolution. Rhe VDDC also employs an Adaptive Intensity Scaling operation that adaptively adjusts the degradation representation according to the network hierarchy, thereby facilitating the effective integration of degradation information. Quantitative and qualitative experiments affirm the superiority of our approach.
EMMI -- Empathic Multimodal Motivational Interviews Dataset: Analyses and Annotations
Venue: arXiv cs.CL 2024
Year: 2024

The study of multimodal interaction in therapy can yield a comprehensive understanding of therapist and patient behavior that can be used to develop a multimodal virtual agent supporting therapy. This investigation aims to uncover how therapists skillfully blend therapy's task goal (employing classical steps of Motivational Interviewing) with the social goal (building a trusting relationship and expressing empathy). Furthermore, we seek to categorize patients into various ``types'' requiring tailored therapeutic approaches. To this intent, we present multimodal annotations of a corpus consisting of simulated motivational interviewing conversations, wherein actors portray the roles of patients and therapists. We introduce EMMI, composed of two publicly available MI corpora, AnnoMI and the Motivational Interviewing Dataset, for which we add multimodal annotations. We analyze these annotations to characterize functional behavior for developing a virtual agent performing motivational interviews emphasizing social and empathic behaviors. Our analysis found three clusters of patients expressing significant differences in behavior and adaptation of the therapist's behavior to those types. This shows the importance of a therapist being able to adapt their behavior depending on the current situation within the dialog and the type of user.