OpenRaiser/Intern-Atlas huggingface dataset:
Nonmyopic Multiclass Active Search with Diminishing Returns for Diverse Discovery
Venue: arXiv cs.LG 2023
Year: 2023

Active search is a setting in adaptive experimental design where we aim to uncover members of rare, valuable class(es) subject to a budget constraint. An important consideration in this problem is diversity among the discovered targets -- in many applications, diverse discoveries offer more insight and may be preferable in downstream tasks. However, most existing active search policies either assume that all targets belong to a common positive class or encourage diversity via simple heuristics. We present a novel formulation of active search with multiple target classes, characterized by a utility function chosen from a flexible family whose members encourage diversity via a diminishing returns mechanism. We then study this problem under the Bayesian lens and prove a hardness result for approximating the optimal policy for arbitrary positive, increasing, and concave utility functions. Finally, we design an efficient, nonmyopic approximation to the optimal policy for this class of utilities and demonstrate its superior empirical performance in a variety of settings, including drug discovery.
Machine Explanations and Human Understanding
Venue: arXiv cs.AI 2023
Year: 2023

Explanations are hypothesized to improve human understanding of machine learning models and achieve a variety of desirable outcomes, ranging from model debugging to enhancing human decision making. However, empirical studies have found mixed and even negative results. An open question, therefore, is under what conditions explanations can improve human understanding and in what way. Using adapted causal diagrams, we provide a formal characterization of the interplay between machine explanations and human understanding, and show how human intuitions play a central role in enabling human understanding. Specifically, we identify three core concepts of interest that cover all existing quantitative measures of understanding in the context of human-AI decision making: task decision boundary, model decision boundary, and model error. Our key result is that without assumptions about task-specific intuitions, explanations may potentially improve human understanding of model decision boundary, but they cannot improve human understanding of task decision boundary or model error. To achieve complementary human-AI performance, we articulate possible ways on how explanations need to work with human intuitions. For instance, human intuitions about the relevance of features (e.g., education is more important than age in predicting a person's income) can be critical in detecting model error. We validate the importance of human intuitions in shaping the outcome of machine explanations with empirical human-subject studies. Overall, our work provides a general framework along with actionable implications for future algorithmic development and empirical experiments of machine explanations.
HW/SW Co-design for Reliable TCAM-based In-memory Brain-inspired Hyperdimensional Computing
Venue: arXiv cs.ET 2023
Year: 2023

Brain-inspired hyperdimensional computing (HDC) is continuously gaining remarkable attention. It is a promising alternative to traditional machine-learning approaches due to its ability to learn from little data, lightweight implementation, and resiliency against errors. However, HDC is overwhelmingly data-centric similar to traditional machine-learning algorithms. In-memory computing is rapidly emerging to overcome the von Neumann bottleneck by eliminating data movements between compute and storage units. In this work, we investigate and model the impact of imprecise in-memory computing hardware on the inference accuracy of HDC. Our modeling is based on 14nm FinFET technology fully calibrated with Intel measurement data. We accurately model, for the first time, the voltage-dependent error probability in SRAM-based and FeFET-based in-memory computing. Thanks to HDC's resiliency against errors, the complexity of the underlying hardware can be reduced, providing large energy savings of up to 6x. Experimental results for SRAM reveal that variability-induced errors have a probability of up to 39 percent. Despite such a high error probability, the inference accuracy is only marginally impacted. This opens doors to explore new tradeoffs. We also demonstrate that the resiliency against errors is application-dependent. In addition, we investigate the robustness of HDC against errors when the underlying in-memory hardware is realized using emerging non-volatile FeFET devices instead of mature CMOS-based SRAMs. We demonstrate that inference accuracy does remain high despite the larger error probability, while large area and power savings can be obtained. All in all, HW/SW co-design is the key for efficient yet reliable in-memory hyperdimensional computing for both conventional CMOS technology and upcoming emerging technologies.
Understanding Hyperdimensional Computing for Parallel Single-Pass Learning
Venue: arXiv cs.LG 2023
Year: 2023

Hyperdimensional computing (HDC) is an emerging learning paradigm that computes with high dimensional binary vectors. It is attractive because of its energy efficiency and low latency, especially on emerging hardware -- but HDC suffers from low model accuracy, with little theoretical understanding of what limits its performance. We propose a new theoretical analysis of the limits of HDC via a consideration of what similarity matrices can be "expressed" by binary vectors, and we show how the limits of HDC can be approached using random Fourier features (RFF). We extend our analysis to the more general class of vector symbolic architectures (VSA), which compute with high-dimensional vectors (hypervectors) that are not necessarily binary. We propose a new class of VSAs, finite group VSAs, which surpass the limits of HDC. Using representation theory, we characterize which similarity matrices can be "expressed" by finite group VSA hypervectors, and we show how these VSAs can be constructed. Experimental results show that our RFF method and group VSA can both outperform the state-of-the-art HDC model by up to 7.6\% while maintaining hardware efficiency.
Who Funds Misinformation? A Systematic Analysis of the Ad-related Profit Routines of Fake News sites
Venue: arXiv cs.CY 2023
Year: 2023

Fake news is an age-old phenomenon, widely assumed to be associated with political propaganda published to sway public opinion. Yet, with the growth of social media, it has become a lucrative business for Web publishers. Despite many studies performed and countermeasures proposed, unreliable news sites have increased in the last years their share of engagement among the top performing news sources. Stifling fake news impact depends on our efforts in limiting the (economic) incentives of fake news producers. In this paper, we aim at enhancing the transparency around these exact incentives, and explore: Who supports the existence of fake news websites via paid ads, either as an advertiser or an ad seller? Who owns these websites and what other Web business are they into? We are the first to systematize the auditing process of fake news revenue flows. We identify the companies that advertise in fake news websites and the intermediary companies responsible for facilitating those ad revenues. We study more than 2,400 popular news websites and show that well-known ad networks, such as Google and IndexExchange, have a direct advertising relation with more than 40% of fake news websites. Using a graph clustering approach on 114.5K sites, we show that entities who own fake news sites, also operate other types of websites pointing to the fact that owning a fake news website is part of a broader business operation.
Locating and Editing Factual Associations in GPT
Venue: arXiv cs.CL 2023
Year: 2023

We analyze the storage and recall of factual associations in autoregressive transformer language models, finding evidence that these associations correspond to localized, directly-editable computations. We first develop a causal intervention for identifying neuron activations that are decisive in a model's factual predictions. This reveals a distinct set of steps in middle-layer feed-forward modules that mediate factual predictions while processing subject tokens. To test our hypothesis that these computations correspond to factual association recall, we modify feed-forward weights to update specific factual associations using Rank-One Model Editing (ROME). We find that ROME is effective on a standard zero-shot relation extraction (zsRE) model-editing task, comparable to existing methods. To perform a more sensitive evaluation, we also evaluate ROME on a new dataset of counterfactual assertions, on which it simultaneously maintains both specificity and generalization, whereas other methods sacrifice one or another. Our results confirm an important role for mid-layer feed-forward modules in storing factual associations and suggest that direct manipulation of computational mechanisms may be a feasible approach for model editing. The code, dataset, visualizations, and an interactive demo notebook are available at https://rome.baulab.info/
Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming
Venue: arXiv cs.DM 2023
Year: 2023

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix $A$ and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of $A$, and when parameterized by the dual tree-depth and the entry complexity of $A$; both these parameterization imply that $A$ is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the $\ell_1$-norm of the Graver basis is bounded by a function of the maximum $\ell_1$-norm of a circuit of $A$. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix $A$ that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the $\ell_1$-norm of the Graver basis of the constraint matrix, when parameterized by the $\ell_1$-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.
Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization
Venue: arXiv cs.LG 2023
Year: 2023

Over the recent years, reinforcement learning (RL) starts to show promising results in tackling combinatorial optimization (CO) problems, in particular when coupled with curriculum learning to facilitate training. Despite emerging empirical evidence, theoretical study on why RL helps is still at its early stage. This paper presents the first systematic study on policy optimization methods for online CO problems. We show that online CO problems can be naturally formulated as latent Markov Decision Processes (LMDPs), and prove convergence bounds on natural policy gradient (NPG) for solving LMDPs. Furthermore, our theory explains the benefit of curriculum learning: it can find a strong sampling policy and reduce the distribution shift, a critical quantity that governs the convergence rate in our theorem. For a canonical online CO problem, the Best Choice Problem (BCP), we formally prove that distribution shift is reduced exponentially with curriculum learning even if the curriculum is a randomly generated BCP on a smaller scale. Our theory also shows we can simplify the curriculum learning scheme used in prior work from multi-step to single-step. Lastly, we provide extensive experiments on the Best Choice Problem, Online Knapsack, and AdWords to verify our findings.
The Schrödinger Bridge between Gaussian Measures has a Closed Form
Venue: arXiv cs.LG 2023
Year: 2023

The static optimal transport $(\mathrm{OT})$ problem between Gaussians seeks to recover an optimal map, or more generally a coupling, to morph a Gaussian into another. It has been well studied and applied to a wide variety of tasks. Here we focus on the dynamic formulation of OT, also known as the Schrödinger bridge (SB) problem, which has recently seen a surge of interest in machine learning due to its connections with diffusion-based generative models. In contrast to the static setting, much less is known about the dynamic setting, even for Gaussian distributions. In this paper, we provide closed-form expressions for SBs between Gaussian measures. In contrast to the static Gaussian OT problem, which can be simply reduced to studying convex programs, our framework for solving SBs requires significantly more involved tools such as Riemannian geometry and generator theory. Notably, we establish that the solutions of SBs between Gaussian measures are themselves Gaussian processes with explicit mean and covariance kernels, and thus are readily amenable for many downstream applications such as generative modeling or interpolation. To demonstrate the utility, we devise a new method for modeling the evolution of single-cell genomics data and report significantly improved numerical stability compared to existing SB-based approaches.
Distributionally Robust Data Join
Venue: arXiv cs.LG 2023
Year: 2023

Suppose we are given two datasets: a labeled dataset and unlabeled dataset which also has additional auxiliary features not present in the first dataset. What is the most principled way to use these datasets together to construct a predictor? The answer should depend upon whether these datasets are generated by the same or different distributions over their mutual feature sets, and how similar the test distribution will be to either of those distributions. In many applications, the two datasets will likely follow different distributions, but both may be close to the test distribution. We introduce the problem of building a predictor which minimizes the maximum loss over all probability distributions over the original features, auxiliary features, and binary labels, whose Wasserstein distance is $r_1$ away from the empirical distribution over the labeled dataset and $r_2$ away from that of the unlabeled dataset. This can be thought of as a generalization of distributionally robust optimization (DRO), which allows for two data sources, one of which is unlabeled and may contain auxiliary features.
Achievable Rate Maximization Pattern Design for Reconfigurable MIMO Antenna Array
Venue: arXiv cs.IT 2023
Year: 2023

Reconfigurable multiple-input multiple-output can provide performance gains over traditional MIMO by reshaping the channels, i.e., introducing more channel realizations. In this paper, we focus on the achievable rate maximization pattern design for reconfigurable MIMO systems. Firstly, we introduce the matrix representation of pattern reconfigurable MIMO (PR-MIMO), based on which a pattern design problem is formulated. To further reveal the effect of the radiation pattern on the wireless channel, we consider pattern design for both the single-pattern case where the optimized radiation pattern is the same for all the antenna elements, and the multi-pattern case where different antenna elements can adopt different radiation patterns. For the single-pattern case, we show that the pattern design is equivalent to a redistribution of gains among all scattering paths, and an eigenvalue optimization based solution is obtained. For the multi-pattern case, we propose a sequential optimization framework with manifold optimization and eigenvalue decomposition to obtain near-optimal solutions. Numerical results validate the superiority of PR-MIMO systems over traditional MIMO in terms of achievable rate, and also show the effectiveness of the proposed solutions.
Efficient Spatial Representation and Routing of Deformable One-Dimensional Objects for Manipulation
Venue: arXiv cs.RO 2023
Year: 2023

With the field of rigid-body robotics having matured in the last fifty years, routing, planning, and manipulation of deformable objects have recently emerged as a more untouched research area in many fields ranging from surgical robotics to industrial assembly and construction. Routing approaches for deformable objects which rely on learned implicit spatial representations (e.g., Learning-from-Demonstration methods) make them vulnerable to changes in the environment and the specific setup. On the other hand, algorithms that entirely separate the spatial representation of the deformable object from the routing and manipulation, often using a representation approach independent of planning, result in slow planning in high dimensional space. This paper proposes a novel approach to routing deformable one-dimensional objects (e.g., wires, cables, ropes, sutures, threads). This approach utilizes a compact representation for the object, allowing efficient and fast online routing. The spatial representation is based on the geometrical decomposition of the space into convex subspaces, resulting in a discrete coding of the deformable object configuration as a sequence. With such a configuration, the routing problem can be solved using a fast dynamic programming sequence matching method that calculates the next routing move. The proposed method couples the routing and efficient configuration for improved planning time. Our simulation and real experiments show the method correctly computing the next manipulation action in sub-millisecond time and accomplishing various routing and manipulation tasks.
NeuroMixGDP: A Neural Collapse-Inspired Random Mixup for Private Data Release
Venue: arXiv cs.LG 2023
Year: 2023

Privacy-preserving data release algorithms have gained increasing attention for their ability to protect user privacy while enabling downstream machine learning tasks. However, the utility of current popular algorithms is not always satisfactory. Mixup of raw data provides a new way of data augmentation, which can help improve utility. However, its performance drastically deteriorates when differential privacy (DP) noise is added. To address this issue, this paper draws inspiration from the recently observed Neural Collapse (NC) phenomenon, which states that the last layer features of a neural network concentrate on the vertices of a simplex as Equiangular Tight Frame (ETF). We propose a scheme to mixup the Neural Collapse features to exploit the ETF simplex structure and release noisy mixed features to enhance the utility of the released data. By using Gaussian Differential Privacy (GDP), we obtain an asymptotic rate for the optimal mixup degree. To further enhance the utility and address the label collapse issue when the mixup degree is large, we propose a Hierarchical sampling method to stratify the mixup samples on a small number of classes. This method remarkably improves utility when the number of classes is large. Extensive experiments demonstrate the effectiveness of our proposed method in protecting against attacks and improving utility. In particular, our approach shows significantly improved utility compared to directly training classification networks with DPSGD on CIFAR100 and MiniImagenet datasets, highlighting the benefits of using privacy-preserving data release. We release reproducible code in https://github.com/Lidonghao1996/NeuroMixGDP.
An Introduction to Neural Data Compression
Venue: arXiv cs.LG 2023
Year: 2023

Neural compression is the application of neural networks and other machine learning methods to data compression. Recent advances in statistical machine learning have opened up new possibilities for data compression, allowing compression algorithms to be learned end-to-end from data using powerful generative models such as normalizing flows, variational autoencoders, diffusion probabilistic models, and generative adversarial networks. The present article aims to introduce this field of research to a broader machine learning audience by reviewing the necessary background in information theory (e.g., entropy coding, rate-distortion theory) and computer vision (e.g., image quality assessment, perceptual metrics), and providing a curated guide through the essential ideas and methods in the literature thus far.
Non-Obvious Manipulability for Single-Parameter Agents and Bilateral Trade
Venue: arXiv cs.GT 2023
Year: 2023

A recent line of work in mechanism design has focused on guaranteeing incentive compatibility for agents without contingent reasoning skills: obviously strategyproof mechanisms guarantee that it is "obvious" for these imperfectly rational agents to behave honestly, whereas non-obviously manipulable (NOM) mechanisms take a more optimistic view and ensure that these agents will only misbehave when it is "obvious" for them to do so. Technically, obviousness requires comparing certain extrema (defined over the actions of the other agents) of an agent's utilities for honest behaviour against dishonest behaviour. We present a technique for designing NOM mechanisms in settings where monetary transfers are allowed based on cycle monotonicity, which allows us to disentangle the specification of the mechanism's allocation from the payments. By leveraging this framework, we completely characterise both allocation and payment functions of NOM mechanisms for single-parameter agents. We then look at the classical setting of bilateral trade and study whether and how much subsidy is needed to guarantee NOM, efficiency, and individual rationality. We prove a stark dichotomy; no finite subsidy suffices if agents look only at best-case extremes, whereas no subsidy at all is required when agents focus on worst-case extremes. We conclude the paper by characterising the NOM mechanisms that require no subsidies whilst satisfying individual rationality.
Enumeration of Dyck paths with air pockets
Venue: arXiv cs.DM 2023
Year: 2023

We introduce and study the new combinatorial class of Dyck paths with air pockets. We exhibit a bijection with the peakless Motzkin paths which transports several pattern statistics and give bivariate generating functions for the distribution of patterns as peaks, returns and pyramids. Then, we deduce the popularities and asymptotic expectations of these patterns and point out a link between the popularity of pyramids and a special kind of closed smooth self-overlapping curves, a subset of Fibonacci meanders. A similar study is conducted for non-decreasing Dyck paths with air pockets.