OpenRaiser/Intern-Atlas huggingface dataset:
Scalable Causal Structure Learning: Scoping Review of Traditional and Deep Learning Algorithms and New Opportunities in Biomedicine
Venue: arXiv cs.LG 2023
Year: 2023

Causal structure learning refers to a process of identifying causal structures from observational data, and it can have multiple applications in biomedicine and health care. This paper provides a practical review and tutorial on scalable causal structure learning models with examples of real-world data to help health care audiences understand and apply them. We reviewed traditional (combinatorial and score-based methods) for causal structure discovery and machine learning-based schemes. We also highlighted recent developments in biomedicine where causal structure learning can be applied to discover structures such as gene networks, brain connectivity networks, and those in cancer epidemiology. We also compared the performance of traditional and machine learning-based algorithms for causal discovery over some benchmark data sets. Machine learning-based approaches, including deep learning, have many advantages over traditional approaches, such as scalability, including a greater number of variables, and potentially being applied in a wide range of biomedical applications, such as genetics, if sufficient data are available. Furthermore, these models are more flexible than traditional models and are poised to positively affect many applications in the future.
Content Preserving Image Translation with Texture Co-occurrence and Spatial Self-Similarity for Texture Debiasing and Domain Adaptation
Venue: arXiv cs.CV 2023
Year: 2023

Models trained on datasets with texture bias usually perform poorly on out-of-distribution samples since biased representations are embedded into the model. Recently, various image translation and debiasing methods have attempted to disentangle texture biased representations for downstream tasks, but accurately discarding biased features without altering other relevant information is still challenging. In this paper, we propose a novel framework that leverages image translation to generate additional training images using the content of a source image and the texture of a target image with a different bias property to explicitly mitigate texture bias when training a model on a target task. Our model ensures texture similarity between the target and generated images via a texture co-occurrence loss while preserving content details from source images with a spatial self-similarity loss. Both the generated and original training images are combined to train improved classification or segmentation models robust to inconsistent texture bias. Evaluation on five classification- and two segmentation-datasets with known texture biases demonstrates the utility of our method, and reports significant improvements over recent state-of-the-art methods in all cases.
Knowledge-driven Active Learning
Venue: arXiv cs.LG 2023
Year: 2023

The deployment of Deep Learning (DL) models is still precluded in those contexts where the amount of supervised data is limited. To answer this issue, active learning strategies aim at minimizing the amount of labelled data required to train a DL model. Most active strategies are based on uncertain sample selection, and even often restricted to samples lying close to the decision boundary. These techniques are theoretically sound, but an understanding of the selected samples based on their content is not straightforward, further driving non-experts to consider DL as a black-box. For the first time, here we propose to take into consideration common domain-knowledge and enable non-expert users to train a model with fewer samples. In our Knowledge-driven Active Learning (KAL) framework, rule-based knowledge is converted into logic constraints and their violation is checked as a natural guide for sample selection. We show that even simple relationships among data and output classes offer a way to spot predictions for which the model need supervision. We empirically show that KAL (i) outperforms many active learning strategies, particularly in those contexts where domain knowledge is rich, (ii) it discovers data distribution lying far from the initial training data, (iii) it ensures domain experts that the provided knowledge is acquired by the model, (iv) it is suitable for regression and object recognition tasks unlike uncertainty-based strategies, and (v) its computational demand is low.
Faster Modular Composition
Venue: arXiv cs.SC 2023
Year: 2023

A new Las Vegas algorithm is presented for the composition of two polynomials modulo a third one, over an arbitrary field. When the degrees of these polynomials are bounded by $n$, the algorithm uses $O(n^{1.43})$ field operations, breaking through the $3/2$ barrier in the exponent for the first time. The previous fastest algebraic algorithms, due to Brent and Kung in 1978, require $O(n^{1.63})$ field operations in general, and ${n^{3/2+o(1)}}$ field operations in the special case of power series over a field of large enough characteristic. If cubic-time matrix multiplication is used, the new algorithm runs in ${n^{5/3+o(1)}}$ operations, while previous ones run in $O(n^2)$ operations. Our approach relies on the computation of a matrix of algebraic relations that is typically of small size. Randomization is used to reduce arbitrary input to this favorable situation.
Think Before You Speak: Explicitly Generating Implicit Commonsense Knowledge for Response Generation
Venue: arXiv cs.CL 2023
Year: 2023

Implicit knowledge, such as common sense, is key to fluid human conversations. Current neural response generation (RG) models are trained to generate responses directly, omitting unstated implicit knowledge. In this paper, we present Think-Before-Speaking (TBS), a generative approach to first externalize implicit commonsense knowledge (think) and use this knowledge to generate responses (speak). We expect that externalizing implicit knowledge allows more efficient learning, produces more informative responses, and enables more explainable models. We analyze different choices to collect knowledge-aligned dialogues, represent implicit knowledge, and transition between knowledge and dialogues. Empirical results show TBS models outperform end-to-end and knowledge-augmented RG baselines on most automatic metrics and generate more informative, specific, and commonsense-following responses, as evaluated by human annotators. TBS also generates knowledge that makes sense and is relevant to the dialogue around 85\% of the time.
Detecting directional forces in the evolution of grammar: A case study of the English perfect with intransitives across EEBO, COHA, and Google Books
Venue: arXiv cs.CY 2023
Year: 2023

Languages have diverse characteristics that have emerged through evolution. In modern English grammar, the perfect is formed with \textit{have}+PP (past participle), but in earlier English the \textit{be}+PP form also existed. It is widely recognised that the auxiliary verb BE was replaced by HAVE throughout evolution, except for some special cases. However, whether this evolution was caused by natural selection or random drift is still unclear. Here we examined directional forces in the evolution of the English perfect with intransitives by combining three large-scale data sources: EEBO (Early English Books Online), COHA (Corpus of Historical American English), and Google Books. We found that most intransitive verbs exhibited an apparent transition from \textit{be}+PP to \textit{have}+PP, most of which were classified as `selection' by a deep neural network-based model. These results suggest that the English perfect could have evolved through natural selection rather than random drift, and provide insights into the cultural evolution of grammar.
Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals
Venue: arXiv cs.DM 2023
Year: 2023

The approximate uniform sampling of graphs with a given degree sequence is a well-known, extensively studied problem in theoretical computer science and has significant applications, e.g., in the analysis of social networks. In this work we study an extension of the problem, where degree intervals are specified rather than a single degree sequence. We are interested in sampling and counting graphs whose degree sequences satisfy the degree interval constraints. A natural scenario where this problem arises is in hypothesis testing on social networks that are only partially observed. In this work, we provide the first fully polynomial almost uniform sampler (FPAUS) as well as the first fully polynomial randomized approximation scheme (FPRAS) for sampling and counting, respectively, graphs with near-regular degree intervals, in which every node $i$ has a degree from an interval not too far away from a given $d \in \N$. In order to design our FPAUS, we rely on various state-of-the-art tools from Markov chain theory and combinatorics. In particular, we provide the first non-trivial algorithmic application of a breakthrough result of Liebenau and Wormald (2017) regarding an asymptotic formula for the number of graphs with a given near-regular degree sequence. Furthermore, we also make use of the recent breakthrough of Anari et al. (2019) on sampling a base of a matroid under a strongly log-concave probability distribution. As a more direct approach, we also study a natural Markov chain recently introduced by Rechner, Strowick and Müller-Hannemann (2018), based on three simple local operations: Switches, hinge flips, and additions/deletions of a single edge. We obtain the first theoretical results for this Markov chain by showing it is rapidly mixing for the case of near-regular degree intervals of size at most one.
Data structure for node connectivity and cut queries
Venue: arXiv cs.DS 2023
Year: 2023

Let $κ(s,t)$ denote the maximum number of internally disjoint $st$-paths in an undirected graph $G$. We consider designing a compact data structure that answers $k$-bounded node connectivity queries: given $s,t \in V$ return $\min\{κ(s,t),k+1\}$. A trivial data structure has space $O(n^2)$ and query time $O(1)$. A data structure of Hsu and Lu has space $O(k^2n)$ and query time $O(\log k)$,and a randomized data structure of Iszak and Nutov has space $O(kn\log n)$ and query time $O(k \log n)$. We extend the Hsu-Lu data structure to answer queries in time $O(1)$. In parallel to our work, Pettie, Saranurak and Yin extended the Iszak-Nutov data structure to answer queries in time $O(\log n)$. Our data structure is more compact for $k<\log n$, and our query time is always better. We then augment our data structure by a list of cuts that enables to return a pointer to a minimum $st$-cut in the list (or to a cut of size $\leq k$) whenever $κ(s,t) \leq k$. A trivial data structure has cut list size $n(n-1)/2$, and cut query time $O(1)$, while the Pettie, Saranurak and Yin data structure has list size $O(kn \log n)$ and cut query time $O(\log n)$. We show that $O(kn)$ cuts suffice to return an $st$-cut of size $\leq k$, and a list of $O(k^2 n)$ cuts contains a minimum $st$-cut for every $s,t \in V$. In the case when $S$ is a node subset with $κ(s,t) \geq k$ for all $s,t \in V$, we show that $3|S|$ cuts suffice, and that these cuts can be partitioned into $O(k)$ laminar families. Thus using space $O(kn)$ we can answers each connectivity and cut queries for $s,t \in S$ in $O(1)$ time, generalizing and substantially simplifying the proof of a result of Pettie and Yin for the case $|S|=V$.
From river flow to spatial flow: flow map via river flow directions assignment algorithm
Venue: arXiv cs.GR 2023
Year: 2023

Flow maps are thematic maps that visualize object movements across space with a tree layout, in which the underlying tree structure is similar to a natural river system. In this paper, we present a novel and automated approach named RFDA-FM for flow maps from one origin to multiple destinations using a river extraction algorithm in digital elevation models (DEM). The RFDA-FM first models the mapping space as a flat surface by a DEM. A maze-solving algorithm (MSA) for river extraction is then adapted to calculate the flow path from one destination to the origin by constraining its searching directions, direction weights, and searching ranges according to the quality criteria of flow maps. All flow paths from the destinations to the origin are obtained iteratively based on the MSA according to their importance, which is defined by considering their length. Finally, these paths are smoothly rendered with varying widths according to their volume using Bézier curves. A comparison with existing approaches indicates that the flow maps generated by RFDA-FM can be better at keeping nodes away from edges without node overlaps and edge crosses. Two extension experiments demonstrate that RFDA-FM is applicable to heterogeneous mapping space or mapping space with obstacle areas. The parameter analysis shows that RFDA-FM can intuitively control the layouts of flow maps. Project website: https://github.com/TrentonWei/FlowMap
Learning Partial Equivariances from Data
Venue: arXiv cs.CV 2023
Year: 2023

Group Convolutional Neural Networks (G-CNNs) constrain learned features to respect the symmetries in the selected group, and lead to better generalization when these symmetries appear in the data. If this is not the case, however, equivariance leads to overly constrained models and worse performance. Frequently, transformations occurring in data can be better represented by a subset of a group than by a group as a whole, e.g., rotations in $[-90^{\circ}, 90^{\circ}]$. In such cases, a model that respects equivariance $\textit{partially}$ is better suited to represent the data. In addition, relevant transformations may differ for low and high-level features. For instance, full rotation equivariance is useful to describe edge orientations in a face, but partial rotation equivariance is better suited to describe face poses relative to the camera. In other words, the optimal level of equivariance may differ per layer. In this work, we introduce $\textit{Partial G-CNNs}$: G-CNNs able to learn layer-wise levels of partial and full equivariance to discrete, continuous groups and combinations thereof as part of training. Partial G-CNNs retain full equivariance when beneficial, e.g., for rotated MNIST, but adjust it whenever it becomes harmful, e.g., for classification of 6 / 9 digits or natural images. We empirically show that partial G-CNNs pair G-CNNs when full equivariance is advantageous, and outperform them otherwise.
HARPS: An Online POMDP Framework for Human-Assisted Robotic Planning and Sensing
Venue: arXiv cs.RO 2023
Year: 2023

Autonomous robots can benefit greatly from human-provided semantic characterizations of uncertain task environments and states. However, the development of integrated strategies which let robots model, communicate, and act on such 'soft data' remains challenging. Here, the Human Assisted Robotic Planning and Sensing (HARPS) framework is presented for active semantic sensing and planning in human-robot teams to address these gaps by formally combining the benefits of online sampling-based POMDP policies, multimodal semantic interaction, and Bayesian data fusion. This approach lets humans opportunistically impose model structure and extend the range of semantic soft data in uncertain environments by sketching and labeling arbitrary landmarks across the environment. Dynamic updating of the environment model while during search allows robotic agents to actively query humans for novel and relevant semantic data, thereby improving beliefs of unknown environments and states for improved online planning. Simulations of a UAV-enabled target search application in a large-scale partially structured environment show significant improvements in time and belief state estimates required for interception versus conventional planning based solely on robotic sensing. Human subject studies in the same environment (n = 36) demonstrate an average doubling in dynamic target capture rate compared to the lone robot case, and highlight the robustness of active probabilistic reasoning and semantic sensing over a range of user characteristics and interaction modalities.
Balanced Allocations: Caching and Packing, Twinning and Thinning
Venue: arXiv cs.DM 2023
Year: 2023

We consider the sequential allocation of $m$ balls (jobs) into $n$ bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small gap between the maximum load and the average load. In this paper, we present a general framework that allows us to analyze various allocation processes that slightly prefer allocating into underloaded, as opposed to overloaded bins. Our analysis covers several natural instances of processes, including: The Caching process (a.k.a. memory protocol) as studied by Mitzenmacher, Prabhakar and Shah (2002): At each round we only take one bin sample, but we also have access to a cache in which the most recently used bin is stored. We place the ball into the least loaded of the two. The Packing process: At each round we only take one bin sample. If the load is below some threshold (e.g., the average load), then we place as many balls until the threshold is reached; otherwise, we place only one ball. The Twinning process: At each round, we only take one bin sample. If the load is below some threshold, then we place two balls; otherwise, we place only one ball. The Thinning process as recently studied by Feldheim and Gurel-Gurevich (2021): At each round, we first take one bin sample. If its load is below some threshold, we place one ball; otherwise, we place one ball into a $\textit{second}$ bin sample. As we demonstrate, our general framework implies for all these processes a gap of $\mathcal{O}(\log n)$ between the maximum load and average load, even when an arbitrary number of balls $m \geq n$ are allocated (heavily loaded case). Our analysis is inspired by a previous work of Peres, Talwar and Wieder (2010) for the $(1+β)$-process, however here we rely on the interplay between different potential functions to prove stabilization.
E-DPNCT: An Enhanced Attack Resilient Differential Privacy Model For Smart Grids Using Split Noise Cancellation
Venue: arXiv cs.CR 2023
Year: 2023

High frequency reporting of energy consumption data in smart grids can be used to infer sensitive information regarding the consumer's life style and poses serious security and privacy threats. Differential privacy (DP) based privacy models for smart grids ensure privacy when analysing energy consumption data for billing and load monitoring. However, DP models for smart grids are vulnerable to collusion attack where an adversary colludes with malicious smart meters and un-trusted aggregator in order to get private information from other smart meters. We first show the vulnerability of DP based privacy model for smart grids against collusion attacks to establish the need of a collusion resistant model privacy model. Then, we propose an Enhanced Differential Private Noise Cancellation Model for Load Monitoring and Billing for Smart Meters (E-DPNCT) which not only provides resistance against collusion attacks but also protects the privacy of the smart grid data while providing accurate billing and load monitoring. We use differential privacy with a split noise cancellation protocol with multiple master smart meters (MSMs) to achieve colluison resistance. We did extensive comparison of our E-DPNCT model with state of the art attack resistant privacy preserving models such as EPIC for collusion attack. We simulate our E-DPNCT model with real time data which shows significant improvement in privacy attack scenarios. Further, we analyze the impact of selecting different sensitivity parameters for calibrating DP noise over the privacy of customer electricity profile and accuracy of electricity data aggregation such as load monitoring and billing.
Efficient CI-Based One-Bit Precoding for Multiuser Downlink Massive MIMO Systems with PSK Modulation
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we consider the one-bit precoding problem for the multiuser downlink massive multiple-input multiple-output (MIMO) system with phase shift keying (PSK) modulation. We focus on the celebrated constructive interference (CI)-based problem formulation. We first establish the NP-hardness of the problem (even in the single-user case), which reveals the intrinsic difficulty of globally solving the problem. Then, we propose a novel negative $\ell_1$ penalty model for the considered problem, which penalizes the one-bit constraint into the objective by a negative $\ell_1$-norm term, and show the equivalence between (global and local) solutions of the original problem and the penalty problem when the penalty parameter is sufficiently large. We further transform the penalty model into an equivalent min-max problem and propose an efficient alternating proximal/projection gradient descent ascent (APGDA) algorithm for solving it, which performs a proximal gradient decent over one block of variables and a projection gradient ascent over the other block of variables alternately. The APGDA algorithm enjoys a low per-iteration complexity and is guaranteed to converge to a stationary point of the min-max problem and a local minimizer of the penalty problem. To further reduce the computational cost, we also propose a low-complexity implementation of the APGDA algorithm, where the values of the variables will be fixed in later iterations once they satisfy the one-bit constraint. Numerical results show that, compared to the state-of-the-art CI-based algorithms, both of the proposed algorithms generally achieve better bit-error-rate (BER) performance with lower computational cost.
An Efficient Branch-and-Bound Solver for Hitting Set
Venue: arXiv cs.DS 2023
Year: 2023

The hitting set problem asks for a collection of sets over a universe $U$ to find a minimum subset of $U$ that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instances from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.
Improving Spectral Clustering Using Spectrum-Preserving Node Aggregation
Venue: arXiv cs.LG 2023
Year: 2023

Spectral clustering is one of the most popular clustering methods. However, the high computational cost due to the involved eigen-decomposition procedure can immediately hinder its applications in large-scale tasks. In this paper we use spectrum-preserving node reduction to accelerate eigen-decomposition and generate concise representations of data sets. Specifically, we create a small number of pseudonodes based on spectral similarity. Then, standard spectral clustering algorithm is performed on the smaller node set. Finally, each data point in the original data set is assigned to the cluster as its representative pseudo-node. The proposed framework run in nearly-linear time. Meanwhile, the clustering accuracy can be significantly improved by mining concise representations. The experimental results show dramatically improved clustering performance when compared with state-of-the-art methods.