OpenRaiser/Intern-Atlas huggingface dataset:
Learning bounded-degree polytrees with known skeleton
Venue: arXiv cs.LG 2024
Year: 2024

We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees, a rich class of high-dimensional probability distributions and a subclass of Bayesian networks, a widely-studied type of graphical model. Recently, Bhattacharyya et al. (2021) obtained finite-sample guarantees for recovering tree-structured Bayesian networks, i.e., 1-polytrees. We extend their results by providing an efficient algorithm which learns $d$-polytrees in polynomial time and sample complexity for any bounded $d$ when the underlying undirected graph (skeleton) is known. We complement our algorithm with an information-theoretic sample complexity lower bound, showing that the dependence on the dimension and target accuracy parameters are nearly tight.
Top of the Heap: Efficient Memory Error Protection of Safe Heap Objects
Venue: arXiv cs.CR 2024
Year: 2024

Heap memory errors remain a major source of software vulnerabilities. Existing memory safety defenses aim at protecting all objects, resulting in high performance cost and incomplete protection. Instead, we propose an approach that accurately identifies objects that are inexpensive to protect, and design a method to protect such objects comprehensively from all classes of memory errors. Towards this goal, we introduce the Uriah system that (1) statically identifies the heap objects whose accesses satisfy spatial and type safety, and (2) dynamically allocates such "safe" heap objects on an isolated safe heap to enforce a form of temporal safety while preserving spatial and type safety, called temporal allocated-type safety. Uriah finds 72.0% of heap allocation sites produce objects whose accesses always satisfy spatial and type safety in the SPEC CPU2006/2017 benchmarks, 5 server programs, and Firefox, which are then isolated on a safe heap using Uriah allocator to enforce temporal allocated-type safety. Uriah incurs only 2.9% and 2.6% runtime overhead, along with 9.3% and 5.4% memory overhead, on the SPEC CPU 2006 and 2017 benchmarks, while preventing exploits on all the heap memory errors in DARPA CGC binaries and 28 recent CVEs. Additionally, using existing defenses to enforce their memory safety guarantees on the unsafe heap objects significantly reduces overhead, enabling the protection of heap objects from all classes of memory errors at more practical costs.
Cultural Compass: Predicting Transfer Learning Success in Offensive Language Detection with Cultural Features
Venue: arXiv cs.CL 2024
Year: 2024

The increasing ubiquity of language technology necessitates a shift towards considering cultural diversity in the machine learning realm, particularly for subjective tasks that rely heavily on cultural nuances, such as Offensive Language Detection (OLD). Current understanding underscores that these tasks are substantially influenced by cultural values, however, a notable gap exists in determining if cultural features can accurately predict the success of cross-cultural transfer learning for such subjective tasks. Addressing this, our study delves into the intersection of cultural features and transfer learning effectiveness. The findings reveal that cultural value surveys indeed possess a predictive power for cross-cultural transfer learning success in OLD tasks and that it can be further improved using offensive word distance. Based on these results, we advocate for the integration of cultural information into datasets. Additionally, we recommend leveraging data sources rich in cultural information, such as surveys, to enhance cultural adaptability. Our research signifies a step forward in the quest for more inclusive, culturally sensitive language technologies.
How Knowledge Workers Think Generative AI Will (Not) Transform Their Industries
Venue: arXiv cs.CY 2024
Year: 2024

Generative AI is expected to have transformative effects in multiple knowledge industries. To better understand how knowledge workers expect generative AI may affect their industries in the future, we conducted participatory research workshops for seven different industries, with a total of 54 participants across three US cities. We describe participants' expectations of generative AI's impact, including a dominant narrative that cut across the groups' discourse: participants largely envision generative AI as a tool to perform menial work, under human review. Participants do not generally anticipate the disruptive changes to knowledge industries currently projected in common media and academic narratives. Participants do however envision generative AI may amplify four social forces currently shaping their industries: deskilling, dehumanization, disconnection, and disinformation. We describe these forces, and then we provide additional detail regarding attitudes in specific knowledge industries. We conclude with a discussion of implications and research challenges for the HCI community.
Extremal Mechanisms for Pointwise Maximal Leakage
Venue: arXiv cs.IT 2024
Year: 2024

Data publishing under privacy constraints can be achieved with mechanisms that add randomness to data points when released to an untrusted party, thereby decreasing the data's utility. In this paper, we analyze this privacy-utility tradeoff for the pointwise maximal leakage privacy measure and a general class of convex utility functions. Pointwise maximal leakage (PML) was recently proposed as an operationally meaningful privacy measure based on two equivalent threat models: An adversary guessing a randomized function and an adversary aiming to maximize a general gain function. We study the behavior of the randomized response mechanism designed for local differential privacy under different prior distributions of the private data. Motivated by the findings of this analysis, we derive several closed-form solutions for the optimal privacy-utility tradeoff in the presented PML context using tools from convex analysis. Finally, we present a linear program that can compute optimal mechanisms for PML in a general setting.
Learning of Sea Surface Height Interpolation from Multi-variate Simulated Satellite Observations
Venue: arXiv cs.LG 2024
Year: 2024

Satellite-based remote sensing missions have revolutionized our understanding of the Ocean state and dynamics. Among them, space-borne altimetry provides valuable Sea Surface Height (SSH) measurements, used to estimate surface geostrophic currents. Due to the sensor technology employed, important gaps occur in SSH observations. Complete SSH maps are produced using linear Optimal Interpolations (OI) such as the widely-used Data Unification and Altimeter Combination System (DUACS). On the other hand, Sea Surface Temperature (SST) products have much higher data coverage and SST is physically linked to geostrophic currents through advection. We propose a new multi-variate Observing System Simulation Experiment (OSSE) emulating 20 years of SSH and SST satellite observations. We train an Attention-Based Encoder-Decoder deep learning network (\textsc{abed}) on this data, comparing two settings: one with access to ground truth during training and one without. On our OSSE, we compare ABED reconstructions when trained using either supervised or unsupervised loss functions, with or without SST information. We evaluate the SSH interpolations in terms of eddy detection. We also introduce a new way to transfer the learning from simulation to observations: supervised pre-training on our OSSE followed by unsupervised fine-tuning on satellite data. Based on real SSH observations from the Ocean Data Challenge 2021, we find that this learning strategy, combined with the use of SST, decreases the root mean squared error by 24% compared to OI.
ConditionVideo: Training-Free Condition-Guided Text-to-Video Generation
Venue: arXiv cs.CV 2024
Year: 2024

Recent works have successfully extended large-scale text-to-image models to the video domain, producing promising results but at a high computational cost and requiring a large amount of video data. In this work, we introduce ConditionVideo, a training-free approach to text-to-video generation based on the provided condition, video, and input text, by leveraging the power of off-the-shelf text-to-image generation methods (e.g., Stable Diffusion). ConditionVideo generates realistic dynamic videos from random noise or given scene videos. Our method explicitly disentangles the motion representation into condition-guided and scenery motion components. To this end, the ConditionVideo model is designed with a UNet branch and a control branch. To improve temporal coherence, we introduce sparse bi-directional spatial-temporal attention (sBiST-Attn). The 3D control network extends the conventional 2D controlnet model, aiming to strengthen conditional generation accuracy by additionally leveraging the bi-directional frames in the temporal domain. Our method exhibits superior performance in terms of frame consistency, clip score, and conditional accuracy, outperforming other compared methods.
Deep Reinforcement Learning for Autonomous Cyber Defence: A Survey
Venue: arXiv cs.LG 2024
Year: 2024

The rapid increase in the number of cyber-attacks in recent years raises the need for principled methods for defending networks against malicious actors. Deep reinforcement learning (DRL) has emerged as a promising approach for mitigating these attacks. However, while DRL has shown much potential for cyber defence, numerous challenges must be overcome before DRL can be applied to the autonomous cyber defence (ACD) problem at scale. Principled methods are required for environments that confront learners with very high-dimensional state spaces, large multi-discrete action spaces, and adversarial learning. Recent works have reported success in solving these problems individually. There have also been impressive engineering efforts towards solving all three for real-time strategy games. However, applying DRL to the full ACD problem remains an open challenge. Here, we survey the relevant DRL literature and conceptualize an idealised ACD-DRL agent. We provide: i.) A summary of the domain properties that define the ACD problem; ii.) A comprehensive comparison of current ACD environments used for benchmarking DRL approaches; iii.) An overview of state-of-the-art approaches for scaling DRL to domains that confront learners with the curse of dimensionality, and; iv.) A survey and critique of current methods for limiting the exploitability of agents within adversarial settings from the perspective of ACD. We conclude with open research questions that we hope will motivate future directions for researchers and practitioners working on ACD.
Deepfakes, Phrenology, Surveillance, and More! A Taxonomy of AI Privacy Risks
Venue: arXiv cs.HC 2024
Year: 2024

Privacy is a key principle for developing ethical AI technologies, but how does including AI technologies in products and services change privacy risks? We constructed a taxonomy of AI privacy risks by analyzing 321 documented AI privacy incidents. We codified how the unique capabilities and requirements of AI technologies described in those incidents generated new privacy risks, exacerbated known ones, or otherwise did not meaningfully alter the risk. We present 12 high-level privacy risks that AI technologies either newly created (e.g., exposure risks from deepfake pornography) or exacerbated (e.g., surveillance risks from collecting training data). One upshot of our work is that incorporating AI technologies into a product can alter the privacy risks it entails. Yet, current approaches to privacy-preserving AI/ML (e.g., federated learning, differential privacy, checklists) only address a subset of the privacy risks arising from the capabilities and data requirements of AI.
Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization
Venue: arXiv cs.LG 2024
Year: 2024

Neural combinatorial optimization (NCO) is a promising learning-based approach for solving challenging combinatorial optimization problems without specialized algorithm design by experts. However, most constructive NCO methods cannot solve problems with large-scale instance sizes, which significantly diminishes their usefulness for real-world applications. In this work, we propose a novel Light Encoder and Heavy Decoder (LEHD) model with a strong generalization ability to address this critical issue. The LEHD model can learn to dynamically capture the relationships between all available nodes of varying sizes, which is beneficial for model generalization to problems of various scales. Moreover, we develop a data-efficient training scheme and a flexible solution construction mechanism for the proposed LEHD model. By training on small-scale problem instances, the LEHD model can generate nearly optimal solutions for the Travelling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP) with up to 1000 nodes, and also generalizes well to solve real-world TSPLib and CVRPLib problems. These results confirm our proposed LEHD model can significantly improve the state-of-the-art performance for constructive NCO. The code is available at https://github.com/CIAM-Group/NCO_code/tree/main/single_objective/LEHD.
Reset It and Forget It: Relearning Last-Layer Weights Improves Continual and Transfer Learning
Venue: arXiv cs.LG 2024
Year: 2024

This work identifies a simple pre-training mechanism that leads to representations exhibiting better continual and transfer learning. This mechanism -- the repeated resetting of weights in the last layer, which we nickname "zapping" -- was originally designed for a meta-continual-learning procedure, yet we show it is surprisingly applicable in many settings beyond both meta-learning and continual learning. In our experiments, we wish to transfer a pre-trained image classifier to a new set of classes, in a few shots. We show that our zapping procedure results in improved transfer accuracy and/or more rapid adaptation in both standard fine-tuning and continual learning settings, while being simple to implement and computationally efficient. In many cases, we achieve performance on par with state of the art meta-learning without needing the expensive higher-order gradients, by using a combination of zapping and sequential learning. An intuitive explanation for the effectiveness of this zapping procedure is that representations trained with repeated zapping learn features that are capable of rapidly adapting to newly initialized classifiers. Such an approach may be considered a computationally cheaper type of, or alternative to, meta-learning rapidly adaptable features with higher-order gradients. This adds to recent work on the usefulness of resetting neural network parameters during training, and invites further investigation of this mechanism.
Understanding the Humans Behind Online Misinformation: An Observational Study Through the Lens of the COVID-19 Pandemic
Venue: arXiv cs.CL 2024
Year: 2024

The proliferation of online misinformation has emerged as one of the biggest threats to society. Considerable efforts have focused on building misinformation detection models, still the perils of misinformation remain abound. Mitigating online misinformation and its ramifications requires a holistic approach that encompasses not only an understanding of its intricate landscape in relation to the complex issue and topic-rich information ecosystem online, but also the psychological drivers of individuals behind it. Adopting a time series analytic technique and robust causal inference-based design, we conduct a large-scale observational study analyzing over 32 million COVID-19 tweets and 16 million historical timeline tweets. We focus on understanding the behavior and psychology of users disseminating misinformation during COVID-19 and its relationship with the historical inclinations towards sharing misinformation on Non-COVID domains before the pandemic. Our analysis underscores the intricacies inherent to cross-domain misinformation, and highlights that users' historical inclination toward sharing misinformation is positively associated with their present behavior pertaining to misinformation sharing on emergent topics and beyond. This work may serve as a valuable foundation for designing user-centric inoculation strategies and ecologically-grounded agile interventions for effectively tackling online misinformation.
Do pretrained Transformers Learn In-Context by Gradient Descent?
Venue: arXiv cs.CL 2024
Year: 2024

The emergence of In-Context Learning (ICL) in LLMs remains a remarkable phenomenon that is partially understood. To explain ICL, recent studies have created theoretical connections to Gradient Descent (GD). We ask, do such connections hold up in actual pre-trained language models? We highlight the limiting assumptions in prior works that make their setup considerably different from the practical setup in which language models are trained. For example, their experimental verification uses \emph{ICL objective} (training models explicitly for ICL), which differs from the emergent ICL in the wild. Furthermore, the theoretical hand-constructed weights used in these studies have properties that don't match those of real LLMs. We also look for evidence in real models. We observe that ICL and GD have different sensitivity to the order in which they observe demonstrations. Finally, we probe and compare the ICL vs. GD hypothesis in a natural setting. We conduct comprehensive empirical analyses on language models pre-trained on natural data (LLaMa-7B). Our comparisons of three performance metrics highlight the inconsistent behavior of ICL and GD as a function of various factors such as datasets, models, and the number of demonstrations. We observe that ICL and GD modify the output distribution of language models differently. These results indicate that \emph{the equivalence between ICL and GD remains an open hypothesis} and calls for further studies.
Idea2Img: Iterative Self-Refinement with GPT-4V(ision) for Automatic Image Design and Generation
Venue: arXiv cs.CV 2024
Year: 2024

We introduce ``Idea to Image,'' a system that enables multimodal iterative self-refinement with GPT-4V(ision) for automatic image design and generation. Humans can quickly identify the characteristics of different text-to-image (T2I) models via iterative explorations. This enables them to efficiently convert their high-level generation ideas into effective T2I prompts that can produce good images. We investigate if systems based on large multimodal models (LMMs) can develop analogous multimodal self-refinement abilities that enable exploring unknown models or environments via self-refining tries. Idea2Img cyclically generates revised T2I prompts to synthesize draft images, and provides directional feedback for prompt revision, both conditioned on its memory of the probed T2I model's characteristics. The iterative self-refinement brings Idea2Img various advantages over vanilla T2I models. Notably, Idea2Img can process input ideas with interleaved image-text sequences, follow ideas with design instructions, and generate images of better semantic and visual qualities. The user preference study validates the efficacy of multimodal iterative self-refinement on automatic image design and generation.
Jigsaw: Supporting Designers to Prototype Multimodal Applications by Chaining AI Foundation Models
Venue: arXiv cs.HC 2024
Year: 2024

Recent advancements in AI foundation models have made it possible for them to be utilized off-the-shelf for creative tasks, including ideating design concepts or generating visual prototypes. However, integrating these models into the creative process can be challenging as they often exist as standalone applications tailored to specific tasks. To address this challenge, we introduce Jigsaw, a prototype system that employs puzzle pieces as metaphors to represent foundation models. Jigsaw allows designers to combine different foundation model capabilities across various modalities by assembling compatible puzzle pieces. To inform the design of Jigsaw, we interviewed ten designers and distilled design goals. In a user study, we showed that Jigsaw enhanced designers' understanding of available foundation model capabilities, provided guidance on combining capabilities across different modalities and tasks, and served as a canvas to support design exploration, prototyping, and documentation.
DexCatch: Learning to Catch Arbitrary Objects with Dexterous Hands
Venue: arXiv cs.RO 2024
Year: 2024

Achieving human-like dexterous manipulation remains a crucial area of research in robotics. Current research focuses on improving the success rate of pick-and-place tasks. Compared with pick-and-place, throwing-catching behavior has the potential to increase the speed of transporting objects to their destination. However, dynamic dexterous manipulation poses a major challenge for stable control due to a large number of dynamic contacts. In this paper, we propose a Learning-based framework for Throwing-Catching tasks using dexterous hands (LTC). Our method, LTC, achieves a 73\% success rate across 45 scenarios (diverse hand poses and objects), and the learned policies demonstrate strong zero-shot transfer performance on unseen objects. Additionally, in tasks where the object in hand faces sideways, an extremely unstable scenario due to the lack of support from the palm, all baselines fail, while our method still achieves a success rate of over 60\%.
Migrant Resettlement by Evolutionary Multi-objective Optimization
Venue: arXiv cs.NE 2024
Year: 2024

Migration has been a universal phenomenon, which brings opportunities as well as challenges for global development. As the number of migrants (e.g., refugees) increases rapidly in recent years, a key challenge faced by each country is the problem of migrant resettlement. This problem has attracted scientific research attention, from the perspective of maximizing the employment rate. Previous works mainly formulated migrant resettlement as an approximately submodular optimization problem subject to multiple matroid constraints and employed the greedy algorithm, whose performance, however, may be limited due to its greedy nature. In this paper, we propose a new framework MR-EMO based on Evolutionary Multi-objective Optimization, which reformulates Migrant Resettlement as a bi-objective optimization problem that maximizes the expected number of employed migrants and minimizes the number of dispatched migrants simultaneously, and employs a Multi-Objective Evolutionary Algorithm (MOEA) to solve the bi-objective problem. We implement MR-EMO using three MOEAs, the popular NSGA-II, MOEA/D as well as the theoretically grounded GSEMO. To further improve the performance of MR-EMO, we propose a specific MOEA, called GSEMO-SR, using matrix-swap mutation and repair mechanism, which has a better ability to search for feasible solutions. We prove that MR-EMO using either GSEMO or GSEMO-SR can achieve better theoretical guarantees than the previous greedy algorithm. Experimental results under the interview and coordination migration models clearly show the superiority of MR-EMO (with either NSGA-II, MOEA/D, GSEMO or GSEMO-SR) over previous algorithms, and that using GSEMO-SR leads to the best performance of MR-EMO.