OpenRaiser/Intern-Atlas huggingface dataset:
You Can Have Your Cake and Redistrict It Too
Venue: arXiv cs.GT 2023
Year: 2023

The design of algorithms for political redistricting generally takes one of two approaches: optimize an objective such as compactness or, drawing on fair division, construct a protocol whose outcomes guarantee partisan fairness. We aim to have the best of both worlds by optimizing an objective subject to a binary fairness constraint. As the fairness constraint we adopt the geometric target, which requires the number of seats won by each party to be at least the average (rounded down) of its outcomes under the worst and best partitions of the state. To study the feasibility of this approach, we introduce a new model of redistricting that closely mirrors the classic model of cake-cutting. This model has two innovative features. First, in any part of the state there is an underlying 'density' of voters with political leanings toward any given party, making it impossible to finely separate voters for different parties into different districts. This captures a realistic constraint that previously existing theoretical models of redistricting tend to ignore. Second, parties may disagree on the distribution of voters - whether by genuine disagreement or attempted strategic behavior. In the absence of a 'ground truth' distribution, a redistricting algorithm must therefore aim to simultaneously be fair to each party with respect to its own reported data. Our main theoretical result is that, surprisingly, the geometric target is always feasible with respect to arbitrarily diverging data sets on how voters are distributed. Any standard for fairness is only useful if it can be readily satisfied in practice. Our empirical results, which use real election data and maps of six US states, demonstrate that the geometric target is always feasible, and that imposing it as a fairness constraint comes at almost no cost to three well-studied optimization objectives.
GFDC: A Granule Fusion Density-Based Clustering with Evidential Reasoning
Venue: arXiv cs.LG 2023
Year: 2023

Currently, density-based clustering algorithms are widely applied because they can detect clusters with arbitrary shapes. However, they perform poorly in measuring global density, determining reasonable cluster centers or structures, assigning samples accurately and handling data with large density differences among clusters. To overcome their drawbacks, this paper proposes a granule fusion density-based clustering with evidential reasoning (GFDC). Both local and global densities of samples are measured by a sparse degree metric first. Then information granules are generated in high-density and low-density regions, assisting in processing clusters with significant density differences. Further, three novel granule fusion strategies are utilized to combine granules into stable cluster structures, helping to detect clusters with arbitrary shapes. Finally, by an assignment method developed from Dempster-Shafer theory, unstable samples are assigned. After using GFDC, a reasonable clustering result and some identified outliers can be obtained. The experimental results on extensive datasets demonstrate the effectiveness of GFDC.
Modeling the Q-Diversity in a Min-max Play Game for Robust Optimization
Venue: arXiv cs.CL 2023
Year: 2023

Models trained with empirical risk minimization (ERM) are revealed to easily rely on spurious correlations, resulting in poor generalization. Group distributionally robust optimization (group DRO) can alleviate this problem by minimizing the worst-case loss over pre-defined groups. While promising, in practice factors like expensive annotations and privacy preclude the availability of group labels. More crucially, when taking a closer look at the failure modes of out-of-distribution generalization, the typical procedure of reweighting in group DRO loses efficiency. Hinged on the limitations, in this work, we reformulate the group DRO framework by proposing Q-Diversity. Characterized by an interactive training mode, Q-Diversity relaxes the group identification from annotation into direct parameterization. Furthermore, a novel mixing strategy across groups is presented to diversify the under-represented groups. In a series of experiments on both synthetic and real-world text classification tasks, results demonstrate that Q-Diversity can consistently improve worst-case accuracy under different distributional shifts, outperforming state-of-the-art alternatives.
Learning Horn Envelopes via Queries from Large Language Models
Venue: arXiv cs.LG 2023
Year: 2023

We investigate an approach for extracting knowledge from trained neural networks based on Angluin's exact learning model with membership and equivalence queries to an oracle. In this approach, the oracle is a trained neural network. We consider Angluin's classical algorithm for learning Horn theories and study the necessary changes to make it applicable to learn from neural networks. In particular, we have to consider that trained neural networks may not behave as Horn oracles, meaning that their underlying target theory may not be Horn. We propose a new algorithm that aims at extracting the "tightest Horn approximation" of the target theory and that is guaranteed to terminate in exponential time (in the worst case) and in polynomial time if the target has polynomially many non-Horn examples. To showcase the applicability of the approach, we perform experiments on pre-trained language models and extract rules that expose occupation-based gender biases.
DiffCap: Exploring Continuous Diffusion on Image Captioning
Venue: arXiv cs.CV 2023
Year: 2023

Current image captioning works usually focus on generating descriptions in an autoregressive manner. However, there are limited works that focus on generating descriptions non-autoregressively, which brings more decoding diversity. Inspired by the success of diffusion models on generating natural-looking images, we propose a novel method DiffCap to apply continuous diffusions on image captioning. Unlike image generation where the output is fixed-size and continuous, image description length varies with discrete tokens. Our method transforms discrete tokens in a natural way and applies continuous diffusion on them to successfully fuse extracted image features for diffusion caption generation. Our experiments on COCO dataset demonstrate that our method uses a much simpler structure to achieve comparable results to the previous non-autoregressive works. Apart from quality, an intriguing property of DiffCap is its high diversity during generation, which is missing from many autoregressive models. We believe our method on fusing multimodal features in diffusion language generation will inspire more researches on multimodal language generation tasks for its simplicity and decoding flexibility.
Probabilistic Modeling: Proving the Lottery Ticket Hypothesis in Spiking Neural Network
Venue: arXiv cs.LG 2023
Year: 2023

The Lottery Ticket Hypothesis (LTH) states that a randomly-initialized large neural network contains a small sub-network (i.e., winning tickets) which, when trained in isolation, can achieve comparable performance to the large network. LTH opens up a new path for network pruning. Existing proofs of LTH in Artificial Neural Networks (ANNs) are based on continuous activation functions, such as ReLU, which satisfying the Lipschitz condition. However, these theoretical methods are not applicable in Spiking Neural Networks (SNNs) due to the discontinuous of spiking function. We argue that it is possible to extend the scope of LTH by eliminating Lipschitz condition. Specifically, we propose a novel probabilistic modeling approach for spiking neurons with complicated spatio-temporal dynamics. Then we theoretically and experimentally prove that LTH holds in SNNs. According to our theorem, we conclude that pruning directly in accordance with the weight size in existing SNNs is clearly not optimal. We further design a new criterion for pruning based on our theory, which achieves better pruning results than baseline.
On the approximability and energy-flow modeling of the electric vehicle sharing problem
Venue: arXiv cs.CC 2023
Year: 2023

The electric vehicle sharing problem (EVSP) arises from the planning and operation of one-way electric car-sharing systems. It aims to maximize the total rental time of a fleet of electric vehicles while ensuring that all the demands of the customer are fulfilled. In this paper, we expand the knowledge on the complexity of the EVSP by showing that it is NP-hard to approximate it to within a factor of $n^{1-ε}$ in polynomial time, for any $ε> 0$, where $n$ denotes the number of customers, unless P = NP. In addition, we also show that the problem does not have a monotone structure, which can be detrimental to the development of heuristics employing constructive strategies. Moreover, we propose a novel approach for the modeling of the EVSP based on energy flows in the network. Based on the new model, we propose a relax-and-fix strategy and an exact algorithm that uses a warm-start solution obtained from our heuristic approach. We report computational results comparing our formulation with the best-performing formulation in the literature. The results show that our formulation outperforms the previous one concerning the number of optimal solutions obtained, optimality gaps, and computational times. Previously, $32.7\%$ of the instances remained unsolved (within a time limit of one hour) by the best-performing formulation in the literature, while our formulation obtained optimal solutions for all instances. To stress our approaches, two more challenging new sets of instances were generated, for which we were able to solve $49.5\%$ of the instances, with an average optimality gap of $2.91\%$ for those not solved optimally.
Proceedings of the International Workshop on Methodologies for Translating Legal Norms into Formal Representations (LN2FR 2022) in association with 35th International Conference on Legal Knowledge and Information Systems (JURIX 2022)
Venue: arXiv cs.LO 2023
Year: 2023

This volume contains the papers presented at LN2FR 2022: The International Workshop on Methodologies for Translating Legal Norms into Formal Representations, held on December 14, 2022 in association with 35th International Conference on Legal Knowledge and Information Systems (JURIX 2022). Using symbolic logic or similar methods of knowledge representation to formalise legal norms is one of the most traditional goals of legal informatics as a scientific discipline. More than mere theoretical value, this approach is also connected to promising real-world applications involving, e.g., the observance of legal norms by highly automated machines or even the (partial) automatisation of legal reasoning, leading to new automated legal services. Albeit the long research tradition on the use of logic to formalise legal norms, many challenges involved in the development of an adequate methodology for the formalisation of concrete legal regulations remain unsolved. This includes not only the choice of a sufficiently expressive formal language or model, but also the concrete way through which a legal text formulated in natural language is to be translated into the formal representation. The workshop LN2FR seeked to explore the various challenges connected with the task of using formal languages and models to represent legal norms in a machine-readable manner.
A Measure of Explanatory Effectiveness
Venue: arXiv cs.CL 2023
Year: 2023

In most conversations about explanation and AI, the recipient of the explanation (the explainee) is suspiciously absent, despite the problem being ultimately communicative in nature. We pose the problem `explaining AI systems' in terms of a two-player cooperative game in which each agent seeks to maximise our proposed measure of explanatory effectiveness. This measure serves as a foundation for the automated assessment of explanations, in terms of the effects that any given action in the game has on the internal state of the explainee.
MIMO Asynchronous MAC with Faster-than-Nyquist (FTN) Signaling
Venue: arXiv cs.IT 2023
Year: 2023

Faster-than-Nyquist (FTN) signaling is a nonorthogonal transmission technique, which brings in intentional inter-symbol interference. This way it can significantly enhance spectral efficiency for practical pulse shapes such as the root raised cosine pulses. This paper proposes an achievable rate region for the multiple antenna (MIMO) asynchronous multiple access channel (aMAC) with FTN signaling. The scheme applies waterfilling in the spatial domain and precoding in time. Waterfilling in space provides better power allocation and precoding helps mitigate inter-symbol interference due to asynchronous transmission and FTN. The results show that the gains due to asynchronous transmission and FTN are more emphasized in MIMO aMAC than in single antenna aMAC. Moreover, FTN improves single-user rates, and asynchronous transmission improves the sum-rate, due to better inter-user interference management.
Tweetorial Hooks: Generative AI Tools to Motivate Science on Social Media
Venue: arXiv cs.HC 2023
Year: 2023

Communicating science and technology is essential for the public to understand and engage in a rapidly changing world. Tweetorials are an emerging phenomenon where experts explain STEM topics on social media in creative and engaging ways. However, STEM experts struggle to write an engaging "hook" in the first tweet that captures the reader's attention. We propose methods to use large language models (LLMs) to help users scaffold their process of writing a relatable hook for complex scientific topics. We demonstrate that LLMs can help writers find everyday experiences that are relatable and interesting to the public, avoid jargon, and spark curiosity. Our evaluation shows that the system reduces cognitive load and helps people write better hooks. Lastly, we discuss the importance of interactivity with LLMs to preserve the correctness, effectiveness, and authenticity of the writing.
Revisiting the Architectures like Pointer Networks to Efficiently Improve the Next Word Distribution, Summarization Factuality, and Beyond
Venue: arXiv cs.CL 2023
Year: 2023

Is the output softmax layer, which is adopted by most language models (LMs), always the best way to compute the next word probability? Given so many attention layers in a modern transformer-based LM, are the pointer networks redundant nowadays? In this study, we discover that the answers to both questions are no. This is because the softmax bottleneck sometimes prevents the LMs from predicting the desired distribution and the pointer networks can be used to break the bottleneck efficiently. Based on the finding, we propose several softmax alternatives by simplifying the pointer networks and accelerating the word-by-word rerankers. In GPT-2, our proposals are significantly better and more efficient than mixture of softmax, a state-of-the-art softmax alternative. In summarization experiments, without significantly decreasing its training/testing speed, our best method based on T5-Small improves factCC score by 2 points in CNN/DM and XSUM dataset, and improves MAUVE scores by 30% in BookSum paragraph-level dataset.
Task-agnostic Distillation of Encoder-Decoder Language Models
Venue: arXiv cs.CL 2023
Year: 2023

Finetuning pretrained language models (LMs) have enabled appealing performance on a diverse array of tasks. The intriguing task-agnostic property has driven a shifted focus from task-specific to task-agnostic distillation of LMs. While task-agnostic, compute-efficient, performance-preserved LMs can be yielded by task-agnostic distillation, previous studies mainly sit in distillation of either encoder-only LMs (e.g., BERT) or decoder-only ones (e.g., GPT) yet largely neglect that distillation of encoder-decoder LMs (e.g., T5) can posit very distinguished behaviors. Frustratingly, we discover that existing task-agnostic distillation methods can fail to handle the distillation of encoder-decoder LMs. To the demand, we explore a few paths and uncover a path named as MiniEnD that successfully tackles the distillation of encoder-decoder LMs in a task-agnostic fashion. We examine MiniEnD on language understanding and abstractive summarization. The results showcase that MiniEnD is generally effective and is competitive compared to other alternatives. We further scale MiniEnD up to distillation of 3B encoder-decoder language models with interpolated distillation. The results imply the opportunities and challenges in distilling large language models (e.g., LLaMA).
Are Your Explanations Reliable? Investigating the Stability of LIME in Explaining Text Classifiers by Marrying XAI and Adversarial Attack
Venue: arXiv cs.LG 2023
Year: 2023

LIME has emerged as one of the most commonly referenced tools in explainable AI (XAI) frameworks that is integrated into critical machine learning applications--e.g., healthcare and finance. However, its stability remains little explored, especially in the context of text data, due to the unique text-space constraints. To address these challenges, in this paper, we first evaluate the inherent instability of LIME on text data to establish a baseline, and then propose a novel algorithm XAIFooler to perturb text inputs and manipulate explanations that casts investigation on the stability of LIME as a text perturbation optimization problem. XAIFooler conforms to the constraints to preserve text semantics and original prediction with small perturbations, and introduces Rank-biased Overlap (RBO) as a key part to guide the optimization of XAIFooler that satisfies all the requirements for explanation similarity measure. Extensive experiments on real-world text datasets demonstrate that XAIFooler significantly outperforms all baselines by large margins in its ability to manipulate LIME's explanations with high semantic preservability.
Integer or Floating Point? New Outlooks for Low-Bit Quantization on Large Language Models
Venue: arXiv cs.LG 2023
Year: 2023

Efficient deployment of large language models (LLMs) necessitates low-bit quantization to minimize model size and inference cost. While low-bit integer formats (e.g., INT8/INT4) have been the conventional choice, emerging low-bit floating-point formats (e.g., FP8/FP4) offer a compelling alternative and are gaining support from cutting-edge hardware, such as NVIDIA's H100 GPU. However, the superiority of low-bit INT versus FP formats for quantization on LLMs remains unclear. In this study, we conduct a comparative analysis of INT and FP quantization with the same bit-width, revealing that the optimal quantization format varies across different layers due to the complexity and diversity of tensor distribution. Consequently, we advocate the Mixture of Formats Quantization (MoFQ), which selects the optimal format on a layer-wise basis. This simple yet effective approach achieves state-of-the-art results in both weight-only (W-only) and weight-activation (WA) post-training quantization scenarios when tested on LLaMA across various tasks. In 4-bit W-only quantization, MoFQ surpasses GPTQ without complex hyperparameter tuning and with an order of magnitude faster quantization speed. While in 8-bit WA quantization, MoFQ significantly outperforms INT/FP-only methods, achieving performance close to the full precision model. Notably, MoFQ incurs no hardware overhead compared to INT/FP-only quantization, as the bit-width remains unchanged.
CoSINT: Designing a Collaborative Capture the Flag Competition to Investigate Misinformation
Venue: arXiv cs.HC 2023
Year: 2023

Crowdsourced investigations shore up democratic institutions by debunking misinformation and uncovering human rights abuses. However, current crowdsourcing approaches rely on simplistic collaborative or competitive models and lack technological support, limiting their collective impact. Prior research has shown that blending elements of competition and collaboration can lead to greater performance and creativity, but crowdsourced investigations pose unique analytical and ethical challenges. In this paper, we employed a four-month-long Research through Design process to design and evaluate a novel interaction style called collaborative capture the flag competitions (CoCTFs). We instantiated this interaction style through CoSINT, a platform that enables a trained crowd to work with professional investigators to identify and investigate social media misinformation. Our mixed-methods evaluation showed that CoSINT leverages the complementary strengths of competition and collaboration, allowing a crowd to quickly identify and debunk misinformation. We also highlight tensions between competition versus collaboration and discuss implications for the design of crowdsourced investigations.
AutoPaint: A Self-Inpainting Method for Unsupervised Anomaly Detection
Venue: arXiv cs.CV 2023
Year: 2023

Robust and accurate detection and segmentation of heterogenous tumors appearing in different anatomical organs with supervised methods require large-scale labeled datasets covering all possible types of diseases. Due to the unavailability of such rich datasets and the high cost of annotations, unsupervised anomaly detection (UAD) methods have been developed aiming to detect the pathologies as deviation from the normality by utilizing the unlabeled healthy image data. However, developed UAD models are often trained with an incomplete distribution of healthy anatomies and have difficulties in preserving anatomical constraints. This work intends to, first, propose a robust inpainting model to learn the details of healthy anatomies and reconstruct high-resolution images by preserving anatomical constraints. Second, we propose an autoinpainting pipeline to automatically detect tumors, replace their appearance with the learned healthy anatomies, and based on that segment the tumoral volumes in a purely unsupervised fashion. Three imaging datasets, including PET, CT, and PET-CT scans of lung tumors and head and neck tumors, are studied as benchmarks for evaluation. Experimental results demonstrate the significant superiority of the proposed method over a wide range of state-of-the-art UAD methods. Moreover, the unsupervised method we propose produces comparable results to a robust supervised segmentation method when applied to multimodal images.
A Dual-level Detection Method for Video Copy Detection
Venue: arXiv cs.CV 2023
Year: 2023

With the development of multimedia technology, Video Copy Detection has been a crucial problem for social media platforms. Meta AI hold Video Similarity Challenge on CVPR 2023 to push the technology forward. In this paper, we share our winner solutions on both tracks to help progress in this area. For Descriptor Track, we propose a dual-level detection method with Video Editing Detection (VED) and Frame Scenes Detection (FSD) to tackle the core challenges on Video Copy Detection. Experimental results demonstrate the effectiveness and efficiency of our proposed method. Code is available at https://github.com/FeipengMa6/VSC22-Submission.