by jsendak | Dec 30, 2023 | Computer Science
Introduction: Exploring the Complexity of Combinatorial Problems with Wires and Swaps
In this article, we delve into the intricacies of a combinatorial problem involving y-monotone wires. The problem revolves around the concept of a tangle, which determines the order of wires on different horizontal layers. The orders can only differ through swaps of neighboring wires. Our main focus is on two related problems: List-Feasibility and Tangle-Height Minimization.
List-Feasibility seeks to find a tangle that realizes a given list of swaps, while Tangle-Height Minimization looks to minimize the number of layers used by the tangle. These problems have been proven to be NP-hard, making them highly challenging to solve.
However, our research takes a step further by showing that List-Feasibility remains NP-hard even when each pair of wires swaps only a constant number of times. On a positive note, we present an algorithm for Tangle-Height Minimization that calculates an optimal tangle for $n$ wires and a given list of swaps in efficient time.
By leveraging this algorithm, we are able to derive a simplified and faster version to solve List-Feasibility. In addition, we demonstrate that List-Feasibility is in NP and fixed-parameter tractable with respect to the number of wires.
We also tackle a specific type of list called “simple” lists, where each swap occurs at most once. For such lists, we showcase an algorithm that solves Tangle-Height Minimization in faster time.
Abstract:We study the following combinatorial problem. Given a set of $n$ y-monotone emph{wires}, a emph{tangle} determines the order of the wires on a number of horizontal emph{layers} such that the orders of the wires on any two consecutive layers differ only in swaps of neighboring wires. Given a multiset~$L$ of emph{swaps} (that is, unordered pairs of wires) and an initial order of the wires, a tangle emph{realizes}~$L$ if each pair of wires changes its order exactly as many times as specified by~$L$. textsc{List-Feasibility} is the problem of finding a tangle that realizes a given list~$L$ if such a tangle exists. textsc{Tangle-Height Minimization} is the problem of finding a tangle that realizes a given list and additionally uses the minimum number of layers. textsc{List-Feasibility} (and therefore textsc{Tangle-Height Minimization}) is NP-hard [Yamanaka, Horiyama, Uno, Wasa; CCCG 2018].
We prove that textsc{List-Feasibility} remains NP-hard if every pair of wires swaps only a constant number of times. On the positive side, we present an algorithm for textsc{Tangle-Height Minimization} that computes an optimal tangle for $n$ wires and a given list~$L$ of swaps in $O((2|L|/n^2+1)^{n^2/2} cdot varphi^n cdot n)$ time, where $varphi approx 1.618$ is the golden ratio and $|L|$ is the total number of swaps in~$L$. From this algorithm, we derive a simpler and faster version to solve textsc{List-Feasibility}. We also use the algorithm to show that textsc{List-Feasibility} is in NP and fixed-parameter tractable with respect to the number of wires. For emph{simple} lists, where every swap occurs at most once, we show how to solve textsc{Tangle-Height Minimization} in $O(n!varphi^n)$ time.
Read the original article
by jsendak | Dec 30, 2023 | Computer Science
In this article, we explore the use of large language models like ChatGPT as auditors for causal networks. Causal networks are commonly used to model complex relationships between variables in various fields, but they often contain erroneous edges. Correcting these networks typically requires domain expertise that may not be readily available. Our proposed method involves presenting ChatGPT with a causal network, one edge at a time, to gain insights about edge directionality, potential confounders, and mediating variables. We analyze ChatGPT’s perspectives on each causal link and generate visualizations summarizing these viewpoints for human analysts to make informed decisions. By integrating large language models, automated causal inference, and human expertise, we aim to develop comprehensive causal models for any scenario. This paper introduces early results with a prototype of our approach.
Abstract:Causal networks are widely used in many fields, including epidemiology, social science, medicine, and engineering, to model the complex relationships between variables. While it can be convenient to algorithmically infer these models directly from observational data, the resulting networks are often plagued with erroneous edges. Auditing and correcting these networks may require domain expertise frequently unavailable to the analyst. We propose the use of large language models such as ChatGPT as an auditor for causal networks. Our method presents ChatGPT with a causal network, one edge at a time, to produce insights about edge directionality, possible confounders, and mediating variables. We ask ChatGPT to reflect on various aspects of each causal link and we then produce visualizations that summarize these viewpoints for the human analyst to direct the edge, gather more data, or test further hypotheses. We envision a system where large language models, automated causal inference, and the human analyst and domain expert work hand in hand as a team to derive holistic and comprehensive causal models for any given case scenario. This paper presents first results obtained with an emerging prototype.
Read the original article
by jsendak | Dec 30, 2023 | Computer Science
This article explores the algorithmic tool called Cylindrical Algebraic Decomposition (CAD) and its application in Real Quantifier Elimination (QE). These topics are important in symbolic computation and have recently gained renewed interest in the development of SMT solvers for non-linear real arithmetic. The article begins by discussing the limitations of iterated univariate resultants in traditional CAD, especially when dealing with multiple equational constraints. It proposes the use of multivariate resultants in the projection phase of CAD as a more efficient alternative. The article also delves into an alternative approach to this problem documented in a previous paper, which redefines the object under construction but only applies to two equational constraints. Important clarifications, corrections, and proofs are provided in relation to this approach. Lastly, the article addresses SMT or Real QE problems expressed using rational functions and their prevalence in industrial applications. It revisits a proposal for handling satisfiability in these cases and offers an alternative approach for more complicated quantification structures.
Abstract:This paper builds and extends on the authors previous work related to the algorithmic tool, Cylindrical Algebraic Decomposition (CAD), and one of its core applications, Real Quantifier Elimination (QE). These topics are at the heart of symbolic computation and were first implemented in computer algebra systems decades ago, but have recently received renewed interest as part of the ongoing development of SMT solvers for non-linear real arithmetic.
First, we consider the use of iterated univariate resultants in traditional CAD, and how this leads to inefficiencies, especially in the case of an input with multiple equational constraints. We reproduce the workshop paper [Davenport & England, 2023], adding important clarifications to our suggestions first made there to make use of multivariate resultants in the projection phase of CAD. We then consider an alternative approach to this problem first documented in [McCallum & Brown, 2009] which redefines the actual object under construction, albeit only in the case of two equational constraints. We correct an important typo and provide a missing proof in that paper.
We finish by revising the topic of how to deal with SMT or Real QE problems expressed using rational functions (as opposed to the usual polynomial ones) noting that these are often found in industrial applications. We revisit a proposal made in [Uncu, Davenport and England, 2023] for doing this in the case of satisfiability, explaining why such an approach does not trivially extend to more complicated quantification structure and giving a suitable alternative.
Read the original article
by jsendak | Dec 30, 2023 | Computer Science
Diffusion models have shown impressive performance in various domains, but their ability to follow natural language instructions and generate complex scenes is still lacking. Prior works have used reinforcement learning to enhance this capability, but it requires careful reward design and often fails to incorporate rich natural language feedback. In this article, we introduce a novel algorithm called iterative prompt relabeling (IP-RLDF) that aligns images to text through iterative image sampling and prompt relabeling. By sampling a batch of images conditioned on the text and relabeling the text prompts of unmatched pairs with classifier feedback, IP-RLDF significantly improves the models’ image generation following instructions. We conducted thorough experiments on three different models and achieved up to 15.22% improvement on the spatial relation VISOR benchmark, outperforming previous RL methods. Explore this article to learn more about the advancements in diffusion models and the effectiveness of IP-RLDF in generating images based on natural language instructions.
Abstract:Diffusion models have shown impressive performance in many domains, including image generation, time series prediction, and reinforcement learning. The algorithm demonstrates superior performance over the traditional GAN and transformer based methods. However, the model’s capability to follow natural language instructions (e.g., spatial relationships between objects, generating complex scenes) is still unsatisfactory. This has been an important research area to enhance such capability. Prior works adopt reinforcement learning to adjust the behavior of the diffusion models. However, RL methods not only require careful reward design and complex hyperparameter tuning, but also fails to incorporate rich natural language feedback. In this work, we propose iterative prompt relabeling (IP-RLDF), a novel algorithm that aligns images to text through iterative image sampling and prompt relabeling. IP-RLDF first samples a batch of images conditioned on the text, then relabels the text prompts of unmatched text-image pairs with classifier feedback. We conduct thorough experiments on three different models, including SDv2, GLIGEN, and SDXL, testing their capability to generate images following instructions. With IP-RLDF, we improved up to 15.22% (absolute improvement) on the challenging spatial relation VISOR benchmark, demonstrating superior performance compared to previous RL methods.
Read the original article
by jsendak | Dec 30, 2023 | Computer Science
Protecting Privacy in Federated Recommender Systems: Introducing UC-FedRec
Federated recommender (FedRec) systems have been developed to address privacy concerns in recommender systems by allowing users to train a shared recommendation model on their local devices, thereby preventing raw data transmissions and collections. However, a common FedRec approach may still leave users vulnerable to attribute inference attacks, where personal attributes can be easily inferred from the learned model.
Moreover, traditional FedRecs often fail to consider the diverse privacy preferences of users, resulting in difficulties in balancing recommendation utility and privacy preservation. This can lead to unnecessary recommendation performance loss or private information leakage.
In order to address these issues, we propose a novel user-consented federated recommendation system (UC-FedRec) that allows users to define their own privacy preferences while still enjoying personalized recommendations. By paying a minimum recommendation accuracy price, UC-FedRec offers flexibility in meeting various privacy demands. Users can have control over their data and make informed decisions about the level of privacy they are comfortable with.
Our experiments on real-world datasets demonstrate that UC-FedRec outperforms baseline approaches in terms of efficiency and flexibility. With UC-FedRec, users can have peace of mind knowing that their privacy is protected without sacrificing the quality of personalized recommendations.
Abstract:Recommender systems can be privacy-sensitive. To protect users’ private historical interactions, federated learning has been proposed in distributed learning for user representations. Using federated recommender (FedRec) systems, users can train a shared recommendation model on local devices and prevent raw data transmissions and collections. However, the recommendation model learned by a common FedRec may still be vulnerable to private information leakage risks, particularly attribute inference attacks, which means that the attacker can easily infer users’ personal attributes from the learned model. Additionally, traditional FedRecs seldom consider the diverse privacy preference of users, leading to difficulties in balancing the recommendation utility and privacy preservation. Consequently, FedRecs may suffer from unnecessary recommendation performance loss due to over-protection and private information leakage simultaneously. In this work, we propose a novel user-consented federated recommendation system (UC-FedRec) to flexibly satisfy the different privacy needs of users by paying a minimum recommendation accuracy price. UC-FedRec allows users to self-define their privacy preferences to meet various demands and makes recommendations with user consent. Experiments conducted on different real-world datasets demonstrate that our framework is more efficient and flexible compared to baselines.
Read the original article
by jsendak | Dec 30, 2023 | Computer Science
Introducing Time Travelling Pixels (TTP): A Novel Approach to High-Precision Change Detection in Remote Sensing
Change detection plays a crucial role in observing and analyzing surface transformations in remote sensing. While deep learning-based methods have advanced the field significantly, accurately detecting changes in complex spatio-temporal scenarios remains a challenge. To address this, researchers have turned to foundation models with their exceptional versatility and generalization capabilities. However, there is still a gap to be bridged in terms of data and tasks. In this paper, we propose Time Travelling Pixels (TTP), a groundbreaking approach that incorporates the latent knowledge of the SAM foundation model into change detection. This method effectively tackles the domain shift in knowledge transfer and overcomes the challenge of expressing both homogeneous and heterogeneous characteristics of multi-temporal images. The exceptional results achieved on the LEVIR-CD dataset testify to the effectiveness of TTP. You can access the code for TTP at this URL.
Abstract:Change detection, a prominent research area in remote sensing, is pivotal in observing and analyzing surface transformations. Despite significant advancements achieved through deep learning-based methods, executing high-precision change detection in spatio-temporally complex remote sensing scenarios still presents a substantial challenge. The recent emergence of foundation models, with their powerful universality and generalization capabilities, offers potential solutions. However, bridging the gap of data and tasks remains a significant obstacle. In this paper, we introduce Time Travelling Pixels (TTP), a novel approach that integrates the latent knowledge of the SAM foundation model into change detection. This method effectively addresses the domain shift in general knowledge transfer and the challenge of expressing homogeneous and heterogeneous characteristics of multi-temporal images. The state-of-the-art results obtained on the LEVIR-CD underscore the efficacy of the TTP. The Code is available at url{this https URL}.
Read the original article
