OpenRaiser/Intern-Atlas huggingface dataset:
Endogenous Coalition Formation in Policy Debates
Venue: arXiv cs.SI 2024
Year: 2024

Political actors form coalitions around their joint normative beliefs in order to influence the policy process on contentious issues such as climate change or population ageing. Policy process theory maintains that learning within and across coalitions is a central predictor of coalition formation and policy change but has yet to explain how policy learning works. The present article explains the formation and maintenance of coalitions by focusing on the ways actors adopt policy beliefs from other actors in policy debates. A policy debate is a complex social system in which temporal network dependence guides how actors contribute ideological statements to the debate. Belief adoption matters in three complementary ways: bonding, which exploits cues within coalitions; bridging, which explores new beliefs outside one's perimeter in the debate; and repulsion, which reinforces polarization between coalitions and cements their belief systems. We formalize this theory of endogenous coalition formation in policy debates and test it on a micro-level empirical dataset using statistical network analysis and event history analysis.
Sample Amplification: Increasing Dataset Size even when Learning is Impossible
Venue: arXiv cs.LG 2024
Year: 2024

Given data drawn from an unknown distribution, $D$, to what extent is it possible to ``amplify'' this dataset and output an even larger set of samples that appear to have been drawn from $D$? We formalize this question as follows: an $(n,m)$ $\text{amplification procedure}$ takes as input $n$ independent draws from an unknown distribution $D$, and outputs a set of $m > n$ ``samples''. An amplification procedure is valid if no algorithm can distinguish the set of $m$ samples produced by the amplifier from a set of $m$ independent draws from $D$, with probability greater than $2/3$. Perhaps surprisingly, in many settings, a valid amplification procedure exists, even when the size of the input dataset, $n$, is significantly less than what would be necessary to learn $D$ to non-trivial accuracy. Specifically we consider two fundamental settings: the case where $D$ is an arbitrary discrete distribution supported on $\le k$ elements, and the case where $D$ is a $d$-dimensional Gaussian with unknown mean, and fixed covariance. In the first case, we show that an $\left(n, n + Θ(\frac{n}{\sqrt{k}})\right)$ amplifier exists. In particular, given $n=O(\sqrt{k})$ samples from $D$, one can output a set of $m=n+1$ datapoints, whose total variation distance from the distribution of $m$ i.i.d. draws from $D$ is a small constant, despite the fact that one would need quadratically more data, $n=Θ(k)$, to learn $D$ up to small constant total variation distance. In the Gaussian case, we show that an $\left(n,n+Θ(\frac{n}{\sqrt{d}} )\right)$ amplifier exists, even though learning the distribution to small constant total variation distance requires $Θ(d)$ samples. In both the discrete and Gaussian settings, we show that these results are tight, to constant factors. Beyond these results, we formalize a number of curious directions for future research along this vein.
Hypothetical answers to continuous queries over data streams
Venue: arXiv cs.PL 2024
Year: 2024

Continuous queries over data streams may suffer from blocking operations and/or unbound wait, which may delay answers until some relevant input arrives through the data stream. These delays may turn answers, when they arrive, obsolete to users who sometimes have to make decisions with no help whatsoever. Therefore, it can be useful to provide hypothetical answers - "given the current information, it is possible that X will become true at time t" - instead of no information at all. In this paper we present a semantics for queries and corresponding answers that covers such hypothetical answers, together with an online algorithm for updating the set of facts that are consistent with the currently available information.
Detecting Clues for Skill Levels and Machine Operation Difficulty from Egocentric Vision
Venue: arXiv cs.HC 2024
Year: 2024

With respect to machine operation tasks, the experiences from different skill level operators, especially novices, can provide worthy understanding about the manner in which they perceive the operational environment and formulate knowledge to deal with various operation situations. In this study, we describe the operator's behaviors by utilizing the relations among their head, hand, and operation location (hotspot) during the operation. A total of 40 experiences associated with a sewing machine operation task performed by amateur operators was recorded via a head-mounted RGB-D camera. We examined important features of operational behaviors in different skill level operators and confirmed their correlation to the difficulties of the operation steps. The result shows that the pure-gazing behavior is significantly reduced when the operator's skill improved. Moreover, the hand-approaching duration and the frequency of attention movement before operation are strongly correlated to the operational difficulty in such machine operating environments.
On Strong Diameter Padded Decompositions
Venue: arXiv cs.DS 2024
Year: 2024

Given a weighted graph $G=(V,E,w)$, a partition of $V$ is $Δ$-bounded if the diameter of each cluster is bounded by $Δ$. A distribution over $Δ$-bounded partitions is a $β$-padded decomposition if every ball of radius $γΔ$ is contained in a single cluster with probability at least $e^{-β\cdotγ}$. The weak diameter of a cluster $C$ is measured w.r.t. distances in $G$, while the strong diameter is measured w.r.t. distances in the induced graph $G[C]$. The decomposition is weak/strong according to the diameter guarantee. Formerly, it was proven that $K_r$ minor free graphs admit weak decompositions with padding parameter $O(r)$, while for strong decompositions only $O(r^2)$ padding parameter was known. Furthermore, for the case of a graph $G$, for which the induced shortest path metric $d_G$ has doubling dimension $d$, a weak $O(d)$-padded decomposition was constructed, which is also known to be tight. For the case of strong diameter, nothing was known. We construct strong $O(r)$-padded decompositions for $K_r$ minor free graphs, matching the state of the art for weak decompositions. Similarly, for graphs with doubling dimension $d$ we construct a strong $O(d)$-padded decomposition, which is also tight. We use this decomposition to construct strong $\left(O(d),\tilde{O}(d)\right)$ sparse cover scheme for such graphs. Our new decompositions and cover have implications to approximating unique games, the construction of light and sparse spanners, and for path reporting distance oracles.
Large Scale Geometries of Infinite Strings
Venue: arXiv cs.LO 2024
Year: 2024

We introduce geometric consideration into the theory of formal languages. We aim to shed light on our understanding of global patterns that occur on infinite strings. We utilise methods of geometric group theory. Our emphasis is on large scale geometries. Two infinite strings have the same large scale geometry if there are colour preserving bi-Lipschitz maps with distortions between the strings. Call these maps quasi-isometries. Introduction of large scale geometries poses several questions. The first question asks to study the partial order induced by quasi-isometries. This partial order compares large scale geometries; as such it presents an algebraic tool for classification of global patterns. We prove there is a greatest large scale geometry and infinitely many minimal large scale geometries. The second question is related to understanding the quasi-isometric maps on various classes of strings. The third question investigates the sets of large scale geometries of strings accepted by computational models, e.g. Büchi automata. We provide an algorithm that describes large scale geometries of strings accepted by Büchi automata. This links large scale geometries with automata theory. The fourth question studies the complexity of the quasi-isometry problem. We show the problem is $Σ_3^0$-complete thus providing a bridge with computability theory. Finally, the fifth question asks to build algebraic structures that are invariants of large scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. Partly, we study asymptotic cones of algorithmically random strings thus connecting the topic with algorithmic randomness.
A New Analysis of Differential Privacy's Generalization Guarantees
Venue: arXiv cs.LG 2024
Year: 2024

We give a new proof of the "transfer theorem" underlying adaptive data analysis: that any mechanism for answering adaptively chosen statistical queries that is differentially private and sample-accurate is also accurate out-of-sample. Our new proof is elementary and gives structural insights that we expect will be useful elsewhere. We show: 1) that differential privacy ensures that the expectation of any query on the posterior distribution on datasets induced by the transcript of the interaction is close to its true value on the data distribution, and 2) sample accuracy on its own ensures that any query answer produced by the mechanism is close to its posterior expectation with high probability. This second claim follows from a thought experiment in which we imagine that the dataset is resampled from the posterior distribution after the mechanism has committed to its answers. The transfer theorem then follows by summing these two bounds, and in particular, avoids the "monitor argument" used to derive high probability bounds in prior work. An upshot of our new proof technique is that the concrete bounds we obtain are substantially better than the best previously known bounds, even though the improvements are in the constants, rather than the asymptotics (which are known to be tight). As we show, our new bounds outperform the naive "sample-splitting" baseline at dramatically smaller dataset sizes compared to the previous state of the art, bringing techniques from this literature closer to practicality.
String Indexing with Compressed Patterns
Venue: arXiv cs.DS 2024
Year: 2024

Given a string $S$ of length $n$, the classic string indexing problem is to preprocess $S$ into a compact data structure that supports efficient subsequent pattern queries. In this paper we consider the basic variant where the pattern is given in compressed form and the goal is to achieve query time that is fast in terms of the compressed size of the pattern. This captures the common client-server scenario, where a client submits a query and communicates it in compressed form to a server. Instead of the server decompressing the query before processing it, we consider how to efficiently process the compressed query directly. Our main result is a novel linear space data structure that achieves near-optimal query time for patterns compressed with the classic Lempel-Ziv compression scheme. Along the way we develop several data structural techniques of independent interest, including a novel data structure that compactly encodes all LZ77 compressed suffixes of a string in linear space and a general decomposition of tries that reduces the search time from logarithmic in the size of the trie to logarithmic in the length of the pattern.
Symplectic ODE-Net: Learning Hamiltonian Dynamics with Control
Venue: arXiv cs.LG 2024
Year: 2024

In this paper, we introduce Symplectic ODE-Net (SymODEN), a deep learning framework which can infer the dynamics of a physical system, given by an ordinary differential equation (ODE), from observed state trajectories. To achieve better generalization with fewer training samples, SymODEN incorporates appropriate inductive bias by designing the associated computation graph in a physics-informed manner. In particular, we enforce Hamiltonian dynamics with control to learn the underlying dynamics in a transparent way, which can then be leveraged to draw insight about relevant physical aspects of the system, such as mass and potential energy. In addition, we propose a parametrization which can enforce this Hamiltonian formalism even when the generalized coordinate data is embedded in a high-dimensional space or we can only access velocity data instead of generalized momentum. This framework, by offering interpretable, physically-consistent models for physical systems, opens up new possibilities for synthesizing model-based control strategies.
On the Approximation Ratio of the $k$-Opt and Lin-Kernighan Algorithm
Venue: arXiv cs.DM 2024
Year: 2024

The $k$-Opt and Lin-Kernighan algorithm are two of the most important local search approaches for the Metric TSP. Both start with an arbitrary tour and make local improvements in each step to get a shorter tour. We show that for any fixed $k\geq 3$ the approximation ratio of the $k$-Opt algorithm for Metric TSP is $O(\sqrt[k]{n})$. Assuming the Erdős girth conjecture, we prove a matching lower bound of $Ω(\sqrt[k]{n})$. Unconditionally, we obtain matching bounds for $k=3,4,6$ and a lower bound of $Ω(n^{\frac{2}{3k-3}})$. Our most general bounds depend on the values of a function from extremal graph theory and are tight up to a factor logarithmic in the number of vertices unconditionally. Moreover, all the upper bounds also apply to a parameterized generalization of the Lin-Kernighan algorithm with appropriate parameters. We also show that the approximation ratio of $k$-Opt for Graph TSP is $Ω\left(\frac{\log(n)}{\log\log(n)}\right)$ and $O\left(\left(\frac{\log(n)}{\log\log(n)}\right)^{\log_2(9)+ε}\right)$ for all $ε>0$. For the (1,2)-TSP we give a lower bound of $\frac{11}{10}$ on the approximation ratio of the $k$-improv and $k$-Opt algorithm for arbitrary fixed $k$.
Decidability of membership problems for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ and singular matrices
Venue: arXiv cs.FL 2024
Year: 2024

We consider membership problems for rational subsets of the semigroup of $2\times 2$ matrices over $\mathbb{Q}$. For a semigroup $M$, the rational subsets $\mathrm{Rat}(M)$ are defined as the sets accepted by NFAs whose transitions are labeled by elements of $M$. In general, it is undecidable on inputs $m\in M$ and $R\in \mathrm{Rat}(M)$ whether $m$ belongs to $R$. Therefore, we restrict our attention to the family $\mathrm{FRat}(M,S)$ of flat rational subsets of $M$ over $S$, where $S$ is a subsemigroup of $M$. It consists of finite unions of the form $g_0L_1g_1 \cdots L_tg_t$, where $L_i\in \mathrm{Rat}(S)$ and $g_i\in M$. Assuming that the membership for $\mathrm{Rat}(S)$ is decidable, we prove various results when the membership for $\mathrm{FRat}(M,S)$ is decidable. If $H$ is a subgroup of a group $G$, then we provide a rather general condition when $\mathrm{FRat}(G,H)$ is an (effective) relative Boolean algebra. This leads to one of our main results that the emptiness problem for Boolean combinations of sets in $\mathrm{FRat}(\mathrm{GL}(2,\mathbb{Q}),\mathrm{GL}(2,\mathbb{Z}))$ is decidable. It is possible that this result cannot be pushed any further as indicated by the following dichotomy: if $G$ is a finitely generated group such that $\mathrm{GL}(2,\mathbb{Z}) < G < \mathrm{GL}(2,\mathbb{Q})$, then either $G\cong \mathrm{GL}(2,\mathbb{Z})\times \mathbb{Z}^k$ or $G$ contains an extension of the Baumslag-Solitar group $\mathrm{BS}(1,q)$ of infinite index. It is open whether the membership for rational subsets is decidable in the latter case. For singular matrices, we will show that the membership problem for $\mathrm{FRat}(\mathbb{Q}^{2\times 2},S)$ is decidable in doubly exponential time, where $S$ is the monoid generated by $\mathrm{GL}(2,\mathbb{Z})\cup \{r\in \mathbb{Q}\,\mid\,r>1\} \cup \{0,\left(\begin{smallmatrix}1 & 0\\ 0 & 0\end{smallmatrix}\right)\}$.
FetusMap: Fetal Pose Estimation in 3D Ultrasound
Venue: arXiv cs.CV 2024
Year: 2024

The 3D ultrasound (US) entrance inspires a multitude of automated prenatal examinations. However, studies about the structuralized description of the whole fetus in 3D US are still rare. In this paper, we propose to estimate the 3D pose of fetus in US volumes to facilitate its quantitative analyses in global and local scales. Given the great challenges in 3D US, including the high volume dimension, poor image quality, symmetric ambiguity in anatomical structures and large variations of fetal pose, our contribution is three-fold. (i) This is the first work about 3D pose estimation of fetus in the literature. We aim to extract the skeleton of whole fetus and assign different segments/joints with correct torso/limb labels. (ii) We propose a self-supervised learning (SSL) framework to finetune the deep network to form visually plausible pose predictions. Specifically, we leverage the landmark-based registration to effectively encode case-adaptive anatomical priors and generate evolving label proxy for supervision. (iii) To enable our 3D network perceive better contextual cues with higher resolution input under limited computing resource, we further adopt the gradient check-pointing (GCP) strategy to save GPU memory and improve the prediction. Extensively validated on a large 3D US dataset, our method tackles varying fetal poses and achieves promising results. 3D pose estimation of fetus has potentials in serving as a map to provide navigation for many advanced studies.
Statistical Linear Models in Virus Genomic Alignment-free Classification: Application to Hepatitis C Viruses
Venue: arXiv cs.LG 2024
Year: 2024

Viral sequence classification is an important task in pathogen detection, epidemiological surveys and evolutionary studies. Statistical learning methods are widely used to classify and identify viral sequences in samples from environments. These methods face several challenges associated with the nature and properties of viral genomes such as recombination, mutation rate and diversity. Also, new generations of sequencing technologies rise other difficulties by generating massive amounts of fragmented sequences. While linear classifiers are often used to classify viruses, there is a lack of exploration of the accuracy space of existing models in the context of alignment free approaches. In this study, we present an exhaustive assessment procedure exploring the power of linear classifiers in genotyping and subtyping partial and complete genomes. It is applied to the Hepatitis C viruses (HCV). Several variables are considered in this investigation such as classifier types (generative and discriminative) and their hyper-parameters (smoothing value and regularization penalty function), the classification task (genotyping and subtyping), the length of the tested sequences (partial and complete) and the length of k-mer words. Overall, several classifiers perform well given a set of precise combination of the experimental variables mentioned above. Finally, we provide the procedure and benchmark data to allow for more robust assessment of classification from virus genomes.
On the Reduction of Variance and Overestimation of Deep Q-Learning
Venue: arXiv cs.LG 2024
Year: 2024

The breakthrough of deep Q-Learning on different types of environments revolutionized the algorithmic design of Reinforcement Learning to introduce more stable and robust algorithms, to that end many extensions to deep Q-Learning algorithm have been proposed to reduce the variance of the target values and the overestimation phenomena. In this paper, we examine new methodology to solve these issues, we propose using Dropout techniques on deep Q-Learning algorithm as a way to reduce variance and overestimation. We also present experiments conducted on benchmark environments, demonstrating the effectiveness of our methodology in enhancing stability and reducing both variance and overestimation in model performance.
Deep Weakly-Supervised Domain Adaptation for Pain Localization in Videos
Venue: arXiv cs.CV 2024
Year: 2024

Automatic pain assessment has an important potential diagnostic value for populations that are incapable of articulating their pain experiences. As one of the dominating nonverbal channels for eliciting pain expression events, facial expressions has been widely investigated for estimating the pain intensity of individual. However, using state-of-the-art deep learning (DL) models in real-world pain estimation applications poses several challenges related to the subjective variations of facial expressions, operational capture conditions, and lack of representative training videos with labels. Given the cost of annotating intensity levels for every video frame, we propose a weakly-supervised domain adaptation (WSDA) technique that allows for training 3D CNNs for spatio-temporal pain intensity estimation using weakly labeled videos, where labels are provided on a periodic basis. In particular, WSDA integrates multiple instance learning into an adversarial deep domain adaptation framework to train an Inflated 3D-CNN (I3D) model such that it can accurately estimate pain intensities in the target operational domain. The training process relies on weak target loss, along with domain loss and source loss for domain adaptation of the I3D model. Experimental results obtained using labeled source domain RECOLA videos and weakly-labeled target domain UNBC-McMaster videos indicate that the proposed deep WSDA approach can achieve significantly higher level of sequence (bag)-level and frame (instance)-level pain localization accuracy than related state-of-the-art approaches.
Image Restoration Using Deep Regulated Convolutional Networks
Venue: arXiv cs.CV 2024
Year: 2024

While the depth of convolutional neural networks has attracted substantial attention in the deep learning research, the width of these networks has recently received greater interest. The width of networks, defined as the size of the receptive fields and the density of the channels, has demonstrated crucial importance in low-level vision tasks such as image denoising and restoration. However, the limited generalization ability, due to the increased width of networks, creates a bottleneck in designing wider networks. In this paper, we propose the Deep Regulated Convolutional Network (RC-Net), a deep network composed of regulated sub-network blocks cascaded by skip-connections, to overcome this bottleneck. Specifically, the Regulated Convolution block (RC-block), featured by a combination of large and small convolution filters, balances the effectiveness of prominent feature extraction and the generalization ability of the network. RC-Nets have several compelling advantages: they embrace diversified features through large-small filter combinations, alleviate the hazy boundary and blurred details in image denoising and super-resolution problems, and stabilize the learning process. Our proposed RC-Nets outperform state-of-the-art approaches with significant performance gains in various image restoration tasks while demonstrating promising generalization ability. The code is available at https://github.com/cswin/RC-Nets.