OpenRaiser/Intern-Atlas huggingface dataset:
Mobility operator service capacity sharing contract design to risk-pool against network disruptions
Venue: arXiv cs.GT 2023
Year: 2023

We propose a new mechanism to design risk-pooling contracts between operators to facilitate horizontal cooperation to mitigate those costs and improve service resilience during disruptions. We formulate a novel two-stage stochastic multicommodity flow model to determine the cost savings of a coalition under different disruption scenarios and solve it using L-shaped method along with sample average approximation. Computational tests of the L-shaped method against deterministic equivalent method with sample average approximation are conducted for network instances with up to 64 nodes, 10 OD pairs, and 1024 scenarios. The results demonstrate that the solution algorithm only becomes computationally effective for larger size instances (above 128 nodes) and that SAA maintains a close approximation. The proposed model is applied to a regional multi-operator network in the Randstad area of the Netherlands, for four operators, 40 origin-destination pairs, and over 1400 links where disruption data is available. Using the proposed method, we identify stable cost allocations among four operating agencies that could yield a 66% improvement in overall network performance over not having any risk-pooling contract in place. Furthermore, the model allows policymakers to evaluate the sensitivity of any one operator's bargaining power to different network structures and disruption scenario distributions, as we illustrate for the HTM operator in Randstad.
Composed Fine-Tuning: Freezing Pre-Trained Denoising Autoencoders for Improved Generalization
Venue: arXiv cs.LG 2023
Year: 2023

We focus on prediction problems with structured outputs that are subject to output validity constraints, e.g. pseudocode-to-code translation where the code must compile. While labeled input-output pairs are expensive to obtain, "unlabeled" outputs, i.e. outputs without corresponding inputs, are freely available (e.g. code on GitHub) and provide information about output validity. We can capture the output structure by pre-training a denoiser to denoise corrupted versions of unlabeled outputs. We first show that standard fine-tuning after pre-training destroys some of this structure. We then propose composed fine-tuning, which fine-tunes a predictor composed with the pre-trained denoiser, which is frozen to preserve output structure. For two-layer ReLU networks, we prove that composed fine-tuning significantly reduces the complexity of the predictor, thus improving generalization. Empirically, we show that composed fine-tuning improves over standard fine-tuning on two pseudocode-to-code translation datasets (3% and 6% relative). The improvement from composed fine-tuning is magnified on out-of-distribution (OOD) examples (4% and 25% relative).
Robustness to Transformations Across Categories: Is Robustness To Transformations Driven by Invariant Neural Representations?
Venue: arXiv cs.CV 2023
Year: 2023

Deep Convolutional Neural Networks (DCNNs) have demonstrated impressive robustness to recognize objects under transformations (eg. blur or noise) when these transformations are included in the training set. A hypothesis to explain such robustness is that DCNNs develop invariant neural representations that remain unaltered when the image is transformed. However, to what extent this hypothesis holds true is an outstanding question, as robustness to transformations could be achieved with properties different from invariance, eg. parts of the network could be specialized to recognize either transformed or non-transformed images. This paper investigates the conditions under which invariant neural representations emerge by leveraging that they facilitate robustness to transformations beyond the training distribution. Concretely, we analyze a training paradigm in which only some object categories are seen transformed during training and evaluate whether the DCNN is robust to transformations across categories not seen transformed. Our results with state-of-the-art DCNNs indicate that invariant neural representations do not always drive robustness to transformations, as networks show robustness for categories seen transformed during training even in the absence of invariant neural representations. Invariance only emerges as the number of transformed categories in the training set is increased. This phenomenon is much more prominent with local transformations such as blurring and high-pass filtering than geometric transformations such as rotation and thinning, which entail changes in the spatial arrangement of the object. Our results contribute to a better understanding of invariant neural representations in deep learning and the conditions under which it spontaneously emerges.
FLUID: A Unified Evaluation Framework for Flexible Sequential Data
Venue: arXiv cs.CV 2023
Year: 2023

Modern ML methods excel when training data is IID, large-scale, and well labeled. Learning in less ideal conditions remains an open challenge. The sub-fields of few-shot, continual, transfer, and representation learning have made substantial strides in learning under adverse conditions; each affording distinct advantages through methods and insights. These methods address different challenges such as data arriving sequentially or scarce training examples, however often the difficult conditions an ML system will face over its lifetime cannot be anticipated prior to deployment. Therefore, general ML systems which can handle the many challenges of learning in practical settings are needed. To foster research towards the goal of general ML methods, we introduce a new unified evaluation framework - FLUID (Flexible Sequential Data). FLUID integrates the objectives of few-shot, continual, transfer, and representation learning while enabling comparison and integration of techniques across these subfields. In FLUID, a learner faces a stream of data and must make sequential predictions while choosing how to update itself, adapt quickly to novel classes, and deal with changing data distributions; while accounting for the total amount of compute. We conduct experiments on a broad set of methods which shed new insight on the advantages and limitations of current solutions and indicate new research problems to solve. As a starting point towards more general methods, we present two new baselines which outperform other evaluated methods on FLUID. Project page: https://raivn.cs.washington.edu/projects/FLUID/.
Contrastive Multiple Correspondence Analysis (cMCA): Using Contrastive Learning to Identify Latent Subgroups in Political Parties
Venue: arXiv cs.SI 2023
Year: 2023

Scaling methods have long been utilized to simplify and cluster high-dimensional data. However, the general latent spaces across all predefined groups derived from these methods sometimes do not fall into researchers' interest regarding specific patterns within groups. To tackle this issue, we adopt an emerging analysis approach called contrastive learning. We contribute to this growing field by extending its ideas to multiple correspondence analysis (MCA) in order to enable an analysis of data often encountered by social scientists -- containing binary, ordinal, and nominal variables. We demonstrate the utility of contrastive MCA (cMCA) by analyzing two different surveys of voters in the U.S. and U.K. Our results suggest that, first, cMCA can identify substantively important dimensions and divisions among subgroups that are overlooked by traditional methods; second, for other cases, cMCA can derive latent traits that emphasize subgroups seen moderately in those derived by traditional methods.
CompRes: A Dataset for Narrative Structure in News
Venue: arXiv cs.CL 2023
Year: 2023

This paper addresses the task of automatically detecting narrative structures in raw texts. Previous works have utilized the oral narrative theory by Labov and Waletzky to identify various narrative elements in personal stories texts. Instead, we direct our focus to news articles, motivated by their growing social impact as well as their role in creating and shaping public opinion. We introduce CompRes -- the first dataset for narrative structure in news media. We describe the process in which the dataset was constructed: first, we designed a new narrative annotation scheme, better suited for news media, by adapting elements from the narrative theory of Labov and Waletzky (Complication and Resolution) and adding a new narrative element of our own (Success); then, we used that scheme to annotate a set of 29 English news articles (containing 1,099 sentences) collected from news and partisan websites. We use the annotated dataset to train several supervised models to identify the different narrative elements, achieving an $F_1$ score of up to 0.7. We conclude by suggesting several promising directions for future work.
Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
Venue: arXiv cs.DS 2023
Year: 2023

Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue maximization via viral marketing. The massive instances occurring in modern day applications can render existing algorithms prohibitively slow, while frequently, those instances are also inherently stochastic. Focusing on these challenges, we revisit the classic problem of maximizing a (possibly non-monotone) submodular function subject to a knapsack constraint. We present a simple randomized greedy algorithm that achieves a $5.83$ approximation and runs in $O(n \log n)$ time, i.e., at least a factor $n$ faster than other state-of-the-art algorithms. The robustness of our approach allows us to further transfer it to a stochastic version of the problem. There, we obtain a 9-approximation to the best adaptive policy, which is the first constant approximation for non-monotone objectives. Experimental evaluation of our algorithms showcases their improved performance on real and synthetic data.
Substring Complexity in Sublinear Space
Venue: arXiv cs.DS 2023
Year: 2023

Shannon's entropy is a definitive lower bound for statistical compression. Unfortunately, no such clear measure exists for the compressibility of repetitive strings. Thus, ad hoc measures are employed to estimate the repetitiveness of strings, e.g., the size $z$ of the Lempel-Ziv parse or the number $r$ of equal-letter runs of the Burrows-Wheeler transform. A more recent one is the size $γ$ of a smallest string attractor. Let $T$ be a string of length $n$. A string attractor of $T$ is a set of positions of $T$ capturing the occurrences of all the substrings of $T$. Unfortunately, Kempa and Prezza [STOC 2018] showed that computing $γ$ is NP-hard. Kociumaka et al. [LATIN 2020] considered a new measure of compressibility that is based on the function $S_T(k)$ counting the number of distinct substrings of length $k$ of $T$, also known as the substring complexity of $T$. This new measure is defined as $δ= \sup\{S_T(k)/k, k\geq 1\}$ and lower bounds all the relevant ad hoc measures previously considered. In particular, $δ\leq γ$ always holds and $δ$ can be computed in $\mathcal{O}(n)$ time using $Θ(n)$ working space. Kociumaka et al. showed that one can construct an $\mathcal{O}(δ\log \frac{n}δ)$-sized representation of $T$ supporting efficient direct access and efficient pattern matching queries on $T$. Given that for highly compressible strings, $δ$ is significantly smaller than $n$, it is natural to pose the following question: Can we compute $δ$ efficiently using sublinear working space? We address this algorithmic challenge by showing the following bounds to compute $δ$: $\mathcal{O}(\frac{n^3\log b}{b^2})$ time using $\mathcal{O}(b)$ space, for any $b\in[1,n]$, in the comparison model; or $\tilde{\mathcal{O}}(n^2/b)$ time using $\tilde{\mathcal{O}}(b)$ space, for any $b\in[\sqrt{n},n]$, in the word RAM model.
Model Checkers Are Cool: How to Model Check Voting Protocols in Uppaal
Venue: arXiv cs.CR 2023
Year: 2023

The design and implementation of an e-voting system is a challenging task. Formal analysis can be of great help here. In particular, it can lead to a better understanding of how the voting system works, and what requirements on the system are relevant. In this paper, we propose that the state-of-art model checker Uppaal provides a good environment for modelling and preliminary verification of voting protocols. To illustrate this, we present an Uppaal model of Prêt à Voter, together with some natural extensions. We also show how to verify a variant of receipt-freeness, despite the severe limitations of the property specification language in the model checker.
A Comparative Analysis of Deep Reinforcement Learning-enabled Freeway Decision-making for Automated Vehicles
Venue: arXiv cs.AI 2023
Year: 2023

Deep reinforcement learning (DRL) has emerged as a pervasive and potent methodology for addressing artificial intelligence challenges. Due to its substantial potential for autonomous self-learning and self-improvement, DRL finds broad applications across various research domains. This article undertakes a comprehensive comparison of several DRL approaches con-cerning the decision-making challenges encountered by autono-mous vehicles on freeways. These techniques encompass common deep Q-learning (DQL), double deep Q-learning (DDQL), dueling deep Q-learning, and prioritized replay deep Q-learning. Initially, the reinforcement learning (RL) framework is introduced, fol-lowed by a mathematical establishment of the implementations of the aforementioned DRL methods. Subsequently, a freeway driving scenario for automated vehicles is constructed, wherein the decision-making problem is reformulated as a control opti-mization challenge. Finally, a series of simulation experiments are conducted to assess the control performance of these DRL-enabled decision-making strategies. This culminates in a comparative analysis, which seeks to elucidate the connection between autonomous driving outcomes and the learning char-acteristics inherent to these DRL techniques.
Asymptotic Performance of Box-RLS Decoders under Imperfect CSI with Optimized Resource Allocation
Venue: arXiv cs.IT 2023
Year: 2023

This paper considers the problem of symbol detection in massive multiple-input multiple-output (MIMO) wireless communication systems. We consider hard-thresholding preceeded by two variants of the regularized least squares (RLS) decoder; namely the unconstrained RLS and the RLS with box constraint. For all schemes, we focus on the evaluation of the mean squared error (MSE) and the symbol error probability (SEP) for M-ary pulse amplitude modulation (M-PAM) symbols transmitted over a massive MIMO system when the channel is estimated using linear minimum mean squared error (LMMSE) estimator. Under such circumstances, the channel estimation error is Gaussian which allows for the use of the convex Gaussian min-max theorem (CGMT) to derive asymptotic approximations for the MSE and SER when the system dimensions and the coherence duration grow large with the same pace. The obtained expressions are then leveraged to derive the optimal power distribution between pilot and data under a total transmit energy constraint. In addition, we derive an asymptotic approximation of the goodput for all schemes which is then used to jointly optimize the number of training symbols and their associated power. Numerical results are presented to support the accuracy of the theoretical results.
Using Machine Teaching to Investigate Human Assumptions when Teaching Reinforcement Learners
Venue: arXiv cs.LG 2023
Year: 2023

Successful teaching requires an assumption of how the learner learns - how the learner uses experiences from the world to update their internal states. We investigate what expectations people have about a learner when they teach them in an online manner using rewards and punishment. We focus on a common reinforcement learning method, Q-learning, and examine what assumptions people have using a behavioral experiment. To do so, we first establish a normative standard, by formulating the problem as a machine teaching optimization problem. To solve the machine teaching optimization problem, we use a deep learning approximation method which simulates learners in the environment and learns to predict how feedback affects the learner's internal states. What do people assume about a learner's learning and discount rates when they teach them an idealized exploration-exploitation task? In a behavioral experiment, we find that people can teach the task to Q-learners in a relatively efficient and effective manner when the learner uses a small value for its discounting rate and a large value for its learning rate. However, they still are suboptimal. We also find that providing people with real-time updates of how possible feedback would affect the Q-learner's internal states weakly helps them teach. Our results reveal how people teach using evaluative feedback and provide guidance for how engineers should design machine agents in a manner that is intuitive for people.
Optimal training of integer-valued neural networks with mixed integer programming
Venue: arXiv cs.LG 2023
Year: 2023

Recent work has shown potential in using Mixed Integer Programming (MIP) solvers to optimize certain aspects of neural networks (NNs). However the intriguing approach of training NNs with MIP solvers is under-explored. State-of-the-art-methods to train NNs are typically gradient-based and require significant data, computation on GPUs, and extensive hyper-parameter tuning. In contrast, training with MIP solvers does not require GPUs or heavy hyper-parameter tuning, but currently cannot handle anything but small amounts of data. This article builds on recent advances that train binarized NNs using MIP solvers. We go beyond current work by formulating new MIP models which improve training efficiency and which can train the important class of integer-valued neural networks (INNs). We provide two novel methods to further the potential significance of using MIP to train NNs. The first method optimizes the number of neurons in the NN while training. This reduces the need for deciding on network architecture before training. The second method addresses the amount of training data which MIP can feasibly handle: we provide a batch training method that dramatically increases the amount of data that MIP solvers can use to train. We thus provide a promising step towards using much more data than before when training NNs using MIP models. Experimental results on two real-world data-limited datasets demonstrate that our approach strongly outperforms the previous state of the art in training NN with MIP, in terms of accuracy, training time and amount of data. Our methodology is proficient at training NNs when minimal training data is available, and at training with minimal memory requirements -- which is potentially valuable for deploying to low-memory devices.
Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching
Venue: arXiv cs.DS 2023
Year: 2023

We study the problem of solving linear program in the streaming model. Given a constraint matrix $A\in \mathbb{R}^{m\times n}$ and vectors $b\in \mathbb{R}^m, c\in \mathbb{R}^n$, we develop a space-efficient interior point method that optimizes solely on the dual program. To this end, we obtain efficient algorithms for various different problems: * For general linear programs, we can solve them in $\widetilde O(\sqrt n\log(1/ε))$ passes and $\widetilde O(n^2)$ space for an $ε$-approximate solution. To the best of our knowledge, this is the most efficient LP solver in streaming with no polynomial dependence on $m$ for both space and passes. * For bipartite graphs, we can solve the minimum vertex cover and maximum weight matching problem in $\widetilde O(\sqrt{m})$ passes and $\widetilde O(n)$ space. In addition to our space-efficient IPM, we also give algorithms for solving SDD systems and isolation lemma in $\widetilde O(n)$ spaces, which are the cornerstones for our graph results.
Hierarchical community structure in networks
Venue: arXiv cs.SI 2023
Year: 2023

Modular and hierarchical community structures are pervasive in real-world complex systems. A great deal of effort has gone into trying to detect and study these structures. Important theoretical advances in the detection of modular have included identifying fundamental limits of detectability by formally defining community structure using probabilistic generative models. Detecting hierarchical community structure introduces additional challenges alongside those inherited from community detection. Here we present a theoretical study on hierarchical community structure in networks, which has thus far not received the same rigorous attention. We address the following questions: 1) How should we define a hierarchy of communities? 2) How do we determine if there is sufficient evidence of a hierarchical structure in a network? and 3) How can we detect hierarchical structure efficiently? We approach these questions by introducing a definition of hierarchy based on the concept of stochastic externally equitable partitions and their relation to probabilistic models, such as the popular stochastic block model. We enumerate the challenges involved in detecting hierarchies and, by studying the spectral properties of hierarchical structure, present an efficient and principled method for detecting them.
Approximate Majority With Catalytic Inputs
Venue: arXiv cs.DC 2023
Year: 2023

Population protocols are a class of algorithms for modeling distributed computation in networks of finite-state agents communicating through pairwise interactions. Their suitability for analyzing numerous chemical processes has motivated the adaptation of the original population protocol framework to better model these chemical systems. In this paper, we further the study of two such adaptations in the context of solving approximate majority: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents, we assume a population with $n$ catalytic input agents and $m$ worker agents, and the goal of the worker agents is to compute some predicate over the states of the catalytic inputs. We call this model the Catalytic Input (CI) model. For $m = Θ(n)$, we show that computing the exact majority of the input population with high probability requires at least $Ω(n^2)$ total interactions, demonstrating a strong separation between the CI model and the standard population protocol model. On the other hand, we show that the simple third-state dynamics of Angluin et al. for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in $O(n \log n)$ total steps w.h.p. when the input margin is $Ω(\sqrt{n \log n})$. We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by Alistarh et al. In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each step with probability $β\leq O\left(\sqrt{n \log n}/n\right)$, exhibiting a resilience to leaks similar to that of Byzantine agents in previous works.