OpenRaiser/Intern-Atlas huggingface dataset:
FBAdtTracker: An Interactive Data Collection and Analysis Tool for Facebook Advertisements
Venue: arXiv cs.IR 2024
Year: 2024

The growing use of social media has led to drastic changes in our decision-making. Especially, Facebook offers marketing API which promotes business to target potential groups who are likely to consume their items. However, this service can be abused by malicious advertisers who attempt to deceive people by disinformation such as propaganda and divisive opinion. To counter this problem, we introduce a new application named FBAdTracker. The purpose of this application is to provide an integrated data collection and analysis system for current research on fact-checking related to Facebook advertisements. Our system is capable of monitoring up-to-date Facebook ads and analyzing ads retrieved from Facebook Ads Library.
Neural Distributed Source Coding
Venue: arXiv cs.IT 2024
Year: 2024

Distributed source coding (DSC) is the task of encoding an input in the absence of correlated side information that is only available to the decoder. Remarkably, Slepian and Wolf showed in 1973 that an encoder without access to the side information can asymptotically achieve the same compression rate as when the side information is available to it. While there is vast prior work on this topic, practical DSC has been limited to synthetic datasets and specific correlation structures. Here we present a framework for lossy DSC that is agnostic to the correlation structure and can scale to high dimensions. Rather than relying on hand-crafted source modeling, our method utilizes a conditional Vector-Quantized Variational Autoencoder (VQ-VAE) to learn the distributed encoder and decoder. We evaluate our method on multiple datasets and show that our method can handle complex correlations and achieves state-of-the-art PSNR. Our code is made available at https://github.com/acnagle/neural-dsc.
AI without networks
Venue: arXiv cs.LG 2024
Year: 2024

Contemporary Artificial Intelligence (AI) stands on two legs: large training data corpora and many-parameter artificial neural networks (ANNs). The data corpora are needed to represent the complexity and heterogeneity of the world. The role of the networks is less transparent due to the obscure dependence of the network parameters and outputs on the training data and inputs. This raises problems, ranging from technical-scientific to legal-ethical. We hypothesize that a transparent approach to machine learning is possible without using networks at all. By generalizing a parameter-free, statistically consistent data interpolation method, which we analyze theoretically in detail, we develop a network-free framework for AI incorporating generative modeling. We demonstrate this framework with examples from three different disciplines - ethology, control theory, and mathematics. Our generative Hilbert framework applied to the trajectories of small groups of swimming fish outperformed state-of-the-art traditional mathematical behavioral models and current ANN-based models. We demonstrate pure data interpolation based control by stabilizing an inverted pendulum and a driven logistic map around unstable fixed points. Finally, we present a mathematical application by predicting zeros of the Riemann Zeta function, achieving comparable performance as a transformer network. We do not suggest that the proposed framework will always outperform networks as over-parameterized networks can interpolate. However, our framework is theoretically sound, transparent, deterministic, and parameter free: remarkably, it does not require any compute-expensive training, does not involve optimization, has no model selection, and is easily reproduced and ported. We also propose an easily computed method of credit assignment based on this framework, to help address ethical-legal challenges raised by generative AI.
Deep Proxy Causal Learning and its Application to Confounded Bandit Policy Evaluation
Venue: arXiv cs.LG 2024
Year: 2024

Proxy causal learning (PCL) is a method for estimating the causal effect of treatments on outcomes in the presence of unobserved confounding, using proxies (structured side information) for the confounder. This is achieved via two-stage regression: in the first stage, we model relations among the treatment and proxies; in the second stage, we use this model to learn the effect of treatment on the outcome, given the context provided by the proxies. PCL guarantees recovery of the true causal effect, subject to identifiability conditions. We propose a novel method for PCL, the deep feature proxy variable method (DFPV), to address the case where the proxies, treatments, and outcomes are high-dimensional and have nonlinear complex relationships, as represented by deep neural network features. We show that DFPV outperforms recent state-of-the-art PCL methods on challenging synthetic benchmarks, including settings involving high dimensional image data. Furthermore, we show that PCL can be applied to off-policy evaluation for the confounded bandit problem, in which DFPV also exhibits competitive performance.
Globular weak $ω$-categories as models of a type theory
Venue: arXiv cs.LO 2024
Year: 2024

We study the dependent type theory CaTT, introduced by Finster and Mimram, which presents the theory of weak $ω$-categories, following the idea that type theories can be considered as presentations of generalized algebraic theories. Our main contribution is a formal proof that the models of this type theory correspond precisely to weak $ω$-categories, as defined by Maltsiniotis, by generalizing a definition proposed by Grothendieck for weak $ω$-groupoids: Those are defined as suitable presheaves over a cat-coherator, which is a category encoding structure expected to be found in an $ω$-category. This comparison is established by proving the initiality conjecture for the type theory CaTT, in a way which suggests the possible generalization to a nerve theorem for a certain class of dependent type theories
Instrumental Variable Estimation for Compositional Treatments
Venue: arXiv cs.LG 2024
Year: 2024

Many scientific datasets are compositional in nature. Important biological examples include species abundances in ecology, cell-type compositions derived from single-cell sequencing data, and amplicon abundance data in microbiome research. Here, we provide a causal view on compositional data in an instrumental variable setting where the composition acts as the cause. First, we crisply articulate potential pitfalls for practitioners regarding the interpretation of compositional causes from the viewpoint of interventions and warn against attributing causal meaning to common summary statistics such as diversity indices in microbiome data analysis. We then advocate for and develop multivariate methods using statistical data transformations and regression techniques that take the special structure of the compositional sample space into account while still yielding scientifically interpretable results. In a comparative analysis on synthetic and real microbiome data we show the advantages and limitations of our proposal. We posit that our analysis provides a useful framework and guidance for valid and informative cause-effect estimation in the context of compositional data.
Real-Time XFEL Data Analysis at SLAC and NERSC: a Trial Run of Nascent Exascale Experimental Data Analysis
Venue: arXiv cs.DC 2024
Year: 2024

X-ray scattering experiments using Free Electron Lasers (XFELs) are a powerful tool to determine the molecular structure and function of unknown samples (such as COVID-19 viral proteins). XFEL experiments are a challenge to computing in two ways: i) due to the high cost of running XFELs, a fast turnaround time from data acquisition to data analysis is essential to make informed decisions on experimental protocols; ii) data collection rates are growing exponentially, requiring new scalable algorithms. Here we report our experiences analyzing data from two experiments at the Linac Coherent Light Source (LCLS) during September 2020. Raw data were analyzed on NERSC's Cori XC40 system, using the Superfacility paradigm: our workflow automatically moves raw data between LCLS and NERSC, where it is analyzed using the software package CCTBX. We achieved real time data analysis with a turnaround time from data acquisition to full molecular reconstruction in as little as 10 min -- sufficient time for the experiment's operators to make informed decisions. By hosting the data analysis on Cori, and by automating LCLS-NERSC interoperability, we achieved a data analysis rate which matches the data acquisition rate. Completing data analysis with 10 mins is a first for XFEL experiments and an important milestone if we are to keep up with data collection trends.
The failure of cut-elimination in cyclic proof for first-order logic with inductive definitions
Venue: arXiv cs.LO 2024
Year: 2024

A cyclic proof system is a proof system whose proof figure is a tree with cycles. The cut-elimination in a proof system is fundamental. It is conjectured that the cut-elimination in the cyclic proof system for first-order logic with inductive definitions does not hold. This paper shows that the conjecture is correct by giving a sequent not provable without the cut rule but provable in the cyclic proof system.
Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL
Venue: arXiv cs.LG 2024
Year: 2024

The success of deep reinforcement learning (DRL) lies in its ability to learn a representation that is well-suited for the exploration and exploitation task. To understand how the choice of representation can improve the efficiency of reinforcement learning (RL), we study representation selection for a class of low-rank Markov Decision Processes (MDPs) where the transition kernel can be represented in a bilinear form. We propose an efficient algorithm, called ReLEX, for representation learning in both online and offline RL. Specifically, we show that the online version of ReLEX, called ReLEX-UCB, always performs no worse than the state-of-the-art algorithm without representation selection, and achieves a strictly better constant regret if the representation function class has a "coverage" property over the entire state-action space. For the offline counterpart, ReLEX-LCB, we show that the algorithm can find the optimal policy if the representation class can cover the state-action space and achieves gap-dependent sample complexity. This is the first result with constant sample complexity for representation learning in offline RL.
Semiring Provenance for Büchi Games: Strategy Analysis with Absorptive Polynomials
Venue: arXiv cs.LO 2024
Year: 2024

This paper presents a case study for the application of semiring semantics for fixed-point formulae to the analysis of strategies in Büchi games. Semiring semantics generalizes the classical Boolean semantics by permitting multiple truth values from certain semirings. Evaluating the fixed-point formula that defines the winning region in a given game in an appropriate semiring of polynomials provides not only the Boolean information on who wins, but also tells us how they win and which strategies they might use. This is well-understood for reachability games, where the winning region is definable as a least fixed point. The case of Büchi games is of special interest, not only due to their practical importance, but also because it is the simplest case where the fixed-point definition involves a genuine alternation of a greatest and a least fixed point. We show that, in a precise sense, semiring semantics provide information about all absorption-dominant strategies -- strategies that win with minimal effort, and we discuss how these relate to positional and the more general persistent strategies. This information enables applications such as game synthesis or determining minimal modifications to the game needed to change its outcome. Lastly, we discuss limitations of our approach and present questions that cannot be immediately answered by semiring semantics.
Exploring individual differences through network topology
Venue: arXiv cs.SI 2024
Year: 2024

Social animals, including humans, have a broad range of personality traits, which can be used to predict individual behavioral responses and decisions. Current methods to quantify individual personality traits in humans rely on self-report questionnaires, which require time and effort to collect, and rely on active cooperation. However, personality differences naturally manifest in social interactions such as online social networks. Here, we explored this option and found that the topology of an online social network can be used to characterize the personality traits of its members. We analyzed the directed social graph formed by the users of the LiveJournal (LJ) blogging platform. Individual user personality traits, inferred from their self-reported domains of interest (DOIs), were associated with their network measures. Empirical clustering of DOIs by topological similarity exposed two main self-emergent DOI groups that were in alignment with the personality meta-traits plasticity and stability. Closeness, a global topological measure of network centrality, was higher for bloggers associated with plasticity (vs. stability). A local network motif (a triad of 3 connected bloggers) also separated the personality meta-traits. Finally, topology-based classification of DOIs (without analyzing the blog content) attained > 70% accuracy (average AUC of the test-set). These results indicate that personality traits can be detected in social network topology. This has serious implications for user privacy. But, if used responsibly, network identification of personality traits could aid in early identification of health-related risks, at the population level.
A Cascade Dual-Decoder Model for Joint Entity and Relation Extraction
Venue: arXiv cs.CL 2024
Year: 2024

In knowledge graph construction, a challenging issue is how to extract complex (e.g., overlapping) entities and relationships from a small amount of unstructured historical data. The traditional pipeline methods are to divide the extraction into two separate subtasks, which misses the potential interaction between the two subtasks and may lead to error propagation. In this work, we propose an effective cascade dual-decoder method to extract overlapping relational triples, which includes a text-specific relation decoder and a relation-corresponded entity decoder. Our approach is straightforward and it includes a text-specific relation decoder and a relation-corresponded entity decoder. The text-specific relation decoder detects relations from a sentence at the text level. That is, it does this according to the semantic information of the whole sentence. For each extracted relation, which is with trainable embedding, the relation-corresponded entity decoder detects the corresponding head and tail entities using a span-based tagging scheme. In this way, the overlapping triple problem can be tackled naturally. We conducted experiments on a real-world open-pit mine dataset and two public datasets to verify the method's generalizability. The experimental results demonstrate the effectiveness and competitiveness of our proposed method and achieve better F1 scores under strict evaluation metrics. Our implementation is available at https://github.com/prastunlp/DualDec.
EPMF: Efficient Perception-aware Multi-sensor Fusion for 3D Semantic Segmentation
Venue: arXiv cs.CV 2024
Year: 2024

We study multi-sensor fusion for 3D semantic segmentation that is important to scene understanding for many applications, such as autonomous driving and robotics. Existing fusion-based methods, however, may not achieve promising performance due to the vast difference between the two modalities. In this work, we investigate a collaborative fusion scheme called perception-aware multi-sensor fusion (PMF) to effectively exploit perceptual information from two modalities, namely, appearance information from RGB images and spatio-depth information from point clouds. To this end, we project point clouds to the camera coordinate using perspective projection, and process both inputs from LiDAR and cameras in 2D space while preventing the information loss of RGB images. Then, we propose a two-stream network to extract features from the two modalities, separately. The extracted features are fused by effective residual-based fusion modules. Moreover, we introduce additional perception-aware losses to measure the perceptual difference between the two modalities. Last, we propose an improved version of PMF, i.e., EPMF, which is more efficient and effective by optimizing data pre-processing and network architecture under perspective projection. Specifically, we propose cross-modal alignment and cropping to obtain tight inputs and reduce unnecessary computational costs. We then explore more efficient contextual modules under perspective projection and fuse the LiDAR features into the camera stream to boost the performance of the two-stream network. Extensive experiments on benchmark data sets show the superiority of our method. For example, on nuScenes test set, our EPMF outperforms the state-of-the-art method, i.e., RangeFormer, by 0.9% in mIoU. Our source code is available at https://github.com/ICEORY/PMF.
Adaptability and the Pivot Penalty in Science and Technology
Venue: arXiv cs.DL 2024
Year: 2024

Scientists and inventors set the direction of their work amidst an evolving landscape of questions, opportunities, and challenges. This paper introduces a measurement framework to quantify how far researchers move from their existing research when producing new works. We apply this framework to millions of scientific publications and patents and uncover a pervasive "pivot penalty", where the impact of new research steeply declines the further a researcher moves from their prior work. The pivot penalty applies nearly universally across scientific publishing and patenting and has been growing in magnitude over the past five decades. While creativity frameworks suggest a benefit to exploratory search by researchers and often emphasize outsider advantages in driving breakthroughs, we find little evidence for such an advantage. The pivot penalty is consistent with increasingly narrow specializations of researchers, and when researchers undertake large pivots, a signature of their work is weak engagement with established mixtures of prior knowledge. Unexpected shocks to the research landscape, which may push researchers away from existing areas or pull them into new ones, further demonstrate substantial pivot penalties. COVID-19 provides a high-scale case study, where many researchers engaged the pandemic, yet the pivot penalty remains severe. The pivot penalty generalizes across fields, career stage, productivity, collaboration, and funding contexts, highlighting both the breadth and depth of the adaptive challenge. Overall, the findings point to large and increasing challenges in adapting to new opportunities and threats. The results have implications for individual researchers, research organizations, science policy, and the capacity of science and society as a whole to confront emergent demands.
VILENS: Visual, Inertial, Lidar, and Leg Odometry for All-Terrain Legged Robots
Venue: arXiv cs.RO 2024
Year: 2024

We present visual inertial lidar legged navigation system (VILENS), an odometry system for legged robots based on factor graphs. The key novelty is the tight fusion of four different sensor modalities to achieve reliable operation when the individual sensors would otherwise produce degenerate estimation. To minimize leg odometry drift, we extend the robot's state with a linear velocity bias term, which is estimated online. This bias is observable because of the tight fusion of this preintegrated velocity factor with vision, lidar, and inertial measurement unit (IMU) factors. Extensive experimental validation on different ANYmal quadruped robots is presented, for a total duration of 2 h and 1.8 km traveled. The experiments involved dynamic locomotion over loose rocks, slopes, and mud, which caused challenges such as slippage and terrain deformation. Perceptual challenges included dark and dusty underground caverns, and open and feature-deprived areas. We show an average improvement of 62% translational and 51% rotational errors compared to a state-of-the-art loosely coupled approach. To demonstrate its robustness, VILENS was also integrated with a perceptive controller and a local path planner.
MCL-GAN: Generative Adversarial Networks with Multiple Specialized Discriminators
Venue: arXiv cs.LG 2024
Year: 2024

We propose a framework of generative adversarial networks with multiple discriminators, which collaborate to represent a real dataset more effectively. Our approach facilitates learning a generator consistent with the underlying data distribution based on real images and thus mitigates the chronic mode collapse problem. From the inspiration of multiple choice learning, we guide each discriminator to have expertise in a subset of the entire data and allow the generator to find reasonable correspondences between the latent and real data spaces automatically without extra supervision for training examples. Despite the use of multiple discriminators, the backbone networks are shared across the discriminators and the increase in training cost is marginal. We demonstrate the effectiveness of our algorithm using multiple evaluation metrics in the standard datasets for diverse tasks.
Automatic Resource Allocation in Business Processes: A Systematic Literature Survey
Venue: arXiv cs.SE 2024
Year: 2024

For delivering products or services to their clients, organizations execute manifold business processes. During such execution, upcoming process tasks need to be allocated to internal resources. Resource allocation is a complex decision-making problem with high impact on the effectiveness and efficiency of processes. A wide range of approaches was developed to support research allocation automatically. This systematic literature survey provides an overview of approaches and categorizes them regarding their resource allocation goals and capabilities, their use of models and data, their algorithmic solutions, and their maturity. Rule-based approaches were identified as dominant, but heuristics and learning approaches also play a relevant role.
Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$
Venue: arXiv cs.CC 2024
Year: 2024

We show that the problem of determining the feasibility of quadratic systems over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$ requires exponential time. This separates P and NP over these fields/rings in the BCSS model of computation.
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications
Venue: arXiv cs.CC 2024
Year: 2024

We analyze the Fourier growth, i.e. the $L_1$ Fourier weight at level $k$ (denoted $L_{1,k}$), of various well-studied classes of "structured" $\mathbb{F}_2$-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [CHHL19,CHLT19,CGLSS20] which show that upper bounds on Fourier growth (even at level $k=2$) give unconditional pseudorandom generators. Our main structural results on Fourier growth are as follows: - We show that any symmetric degree-$d$ $\mathbb{F}_2$-polynomial $p$ has $L_{1,k}(p) \le \Pr[p=1] \cdot O(d)^k$, and this is tight for any constant $k$. This quadratically strengthens an earlier bound that was implicit in [RSV13]. - We show that any read-$Δ$ degree-$d$ $\mathbb{F}_2$-polynomial $p$ has $L_{1,k}(p) \le \Pr[p=1] \cdot (k Δd)^{O(k)}$. - We establish a composition theorem which gives $L_{1,k}$ bounds on disjoint compositions of functions that are closed under restrictions and admit $L_{1,k}$ bounds. Finally, we apply the above structural results to obtain new unconditional pseudorandom generators and new correlation bounds for various classes of $\mathbb{F}_2$-polynomials.