In recent years, large language models (LLMs) have become increasingly prevalent, offering remarkable text generation capabilities.However, a pressing challenge is their tendency to make confidently wrong predictions, highlighting the critical need for uncertainty quantification (UQ) in LLMs.While previous works have mainly focused on addressing aleatoric uncertainty, the full spectrum of uncertainties, including epistemic, remains inadequately explored.Motivated by this gap, we introduce a novel UQ method, sampling with perturbation for UQ (SPUQ), designed to tackle both aleatoric and epistemic uncertainties.The method entails generating a set of perturbations for LLM inputs, sampling outputs for each perturbation, and incorporating an aggregation module that generalizes the sampling uncertainty approach for text generation tasks.Through extensive experiments on various datasets, we investigated different perturbation and aggregation techniques.Our findings show a substantial improvement in model uncertainty calibration, with a reduction in Expected Calibration Error (ECE) by 50% on average.Our findings suggest that our proposed UQ method offers promising steps toward enhancing the reliability and trustworthiness of LLMs 1 .

Pritika Ramu, Sijia Wang, Lalla Mouatadid, Joy Rimchala, Lifu Huang. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

The performance of optical character recognition (OCR) heavily relies on document image quality, which is crucial for automatic document processing and document intelligence. However, most existing document enhancement methods require supervised data pairs, which raises concerns about data separation and privacy protection, and makes it challenging to adapt these methods to new domain pairs. To address these issues, we propose DECDM, an end-to-end document-level image translation method inspired by recent advances in diffusion models. Our method overcomes the limitations of paired training by independently training the source (noisy input) and target (clean output) models, making it possible to apply domain-specific diffusion models to other pairs. DECDM trains on one dataset at a time, eliminating the need to scan both datasets concurrently, and effectively preserving data privacy from the source or target domain. We also introduce simple data augmentation strategies to improve character-glyph conservation during translation. We compare DECDM with state-of-the-art methods on multiple synthetic data and benchmark datasets, such as document denoising and shadow removal, and demonstrate the superiority of performance quantitatively and qualitatively.

Abstract. Modular decomposition focuses on repeatedly identifying a module [Formula: see text] (a collection of vertices that shares exactly the same neighborhood outside of [Formula: see text]) and collapsing it into a single vertex. This notion of exactitude of neighborhood is very strict, especially when dealing with real-world graphs. We study new ways to relax this exactitude condition. However, generalizing modular decomposition is far from obvious. Most of the previous proposals lose algebraic properties of modules and thus most of the nice algorithmic consequences. We introduce the notion of an [Formula: see text]- module, a relaxation that maintains some of the algebraic structure. It leads to a new combinatorial decomposition with interesting properties. Among the main results in this work, we show that minimal [Formula: see text]-modules can be computed in polynomial time, and we generalize series and parallel operation between graphs. This leads to [Formula: see text]-cographs which have interesting properties. We study how to generalize Gallai’s theorem corresponding to the case for [Formula: see text], but unfortunately we give evidence that computing such a decomposition tree can be difficult.

The adoption of knowledge graphs is growing across various domains. And their construction, when automated, can result in verbose sparse graphs. In this talk, we discuss how to mine frequent patterns and subgraphs in a calculation knowledge graph in order to factor out verbose representations and allow for each of maintenance, reduction of storage, and an increase in runtime speed.

We study the maximum induced matching problem on a graph G. Induced matchings correspond to independent sets in L^2(G), the square of the line graph of G. The problem is NP-complete on bipartite graphs. In this work, we show that for a number of graph families with forbidden vertex orderings, almost all forbidden patterns on three vertices are preserved when taking the square of the line graph. These orderings can be computed in linear time in the size of the input graph. In particular, given a graph class \mathcal{G} characterized by a vertex ordering, and a graph G=(V,E) \in \mathcal{G} with a corresponding vertex ordering \sigma of V, one can produce (in linear time in the size of G) an ordering on the vertices of L^2(G), that shows that L^2(G) \in \mathcal{G} - for a number of graph classes \mathcal{G} - without computing the line graph or the square of the line graph of G. These results generalize and unify previous ones on showing closure under L^2(\cdot) for various graph families. Furthermore, these orderings on L^2(G) can be exploited algorithmically to compute a maximum induced matching on G faster. We illustrate this latter fact in the second half of the paper where we focus on cocomparability graphs, a large graph class that includes interval, permutation, trapezoid graphs, and co-graphs, and we present the first \mathcal{O}(mn) time algorithm to compute a maximum weighted induced matching on cocomparability graphs; an improvement from the best known \mathcal{O}(n^4) time algorithm for the unweighted case.