OpenRaiser/Intern-Atlas huggingface dataset:
Modeling Human Sentence Processing with Left-Corner Recurrent Neural Network Grammars
Venue: arXiv cs.CL 2023
Year: 2023

In computational linguistics, it has been shown that hierarchical structures make language models (LMs) more human-like. However, the previous literature has been agnostic about a parsing strategy of the hierarchical models. In this paper, we investigated whether hierarchical structures make LMs more human-like, and if so, which parsing strategy is most cognitively plausible. In order to address this question, we evaluated three LMs against human reading times in Japanese with head-final left-branching structures: Long Short-Term Memory (LSTM) as a sequential model and Recurrent Neural Network Grammars (RNNGs) with top-down and left-corner parsing strategies as hierarchical models. Our computational modeling demonstrated that left-corner RNNGs outperformed top-down RNNGs and LSTM, suggesting that hierarchical and left-corner architectures are more cognitively plausible than top-down or sequential architectures. In addition, the relationships between the cognitive plausibility and (i) perplexity, (ii) parsing, and (iii) beam size will also be discussed.
A Survey on Multi-modal Summarization
Venue: arXiv cs.CL 2023
Year: 2023

The new era of technology has brought us to the point where it is convenient for people to share their opinions over an abundance of platforms. These platforms have a provision for the users to express themselves in multiple forms of representations, including text, images, videos, and audio. This, however, makes it difficult for users to obtain all the key information about a topic, making the task of automatic multi-modal summarization (MMS) essential. In this paper, we present a comprehensive survey of the existing research in the area of MMS, covering various modalities like text, image, audio, and video. Apart from highlighting the different evaluation metrics and datasets used for the MMS task, our work also discusses the current challenges and future directions in this field.
How social networks influence human behavior: An integrated latent space approach for differential social influence
Venue: arXiv cs.SI 2023
Year: 2023

How social networks influence human behavior has been an interesting topic in applied research. Existing methods often utilized scale-level behavioral data to estimate the influence of a social network on human behavior. This study proposes a novel approach to studying social influence that utilizes item-level behavioral measures. Under the latent space modeling framework, we integrate the two interaction maps for respondents' social network data and item-level behavior measures. The interaction map visualizes the association between the latent homophily of the respondents and their behaviors measured at the item level in a low-dimensional latent space, revealing the potential, differential social influence effects across specific behaviors measured at the item level. We also measure overall social influence as the impact of the interaction map configuration contributed by the social network data on the behavior data. The performance and properties of the proposed approach are evaluated via simulation studies. We apply the proposed model to an empirical dataset to demonstrate how the students' friendship network influences their participation in school activities.
Concave Utility Reinforcement Learning with Zero-Constraint Violations
Venue: arXiv cs.LG 2023
Year: 2023

We consider the problem of tabular infinite horizon concave utility reinforcement learning (CURL) with convex constraints. For this, we propose a model-based learning algorithm that also achieves zero constraint violations. Assuming that the concave objective and the convex constraints have a solution interior to the set of feasible occupation measures, we solve a tighter optimization problem to ensure that the constraints are never violated despite the imprecise model knowledge and model stochasticity. We use Bellman error-based analysis for tabular infinite-horizon setups which allows analyzing stochastic policies. Combining the Bellman error-based analysis and tighter optimization equation, for $T$ interactions with the environment, we obtain a high-probability regret guarantee for objective which grows as $\Tilde{O}(1/\sqrt{T})$, excluding other factors. The proposed method can be applied for optimistic algorithms to obtain high-probability regret bounds and also be used for posterior sampling algorithms to obtain a loose Bayesian regret bounds but with significant improvement in computational complexity.
Efficient-FedRec: Efficient Federated Learning Framework for Privacy-Preserving News Recommendation
Venue: arXiv cs.IR 2023
Year: 2023

News recommendation is critical for personalized news access. Most existing news recommendation methods rely on centralized storage of users' historical news click behavior data, which may lead to privacy concerns and hazards. Federated Learning is a privacy-preserving framework for multiple clients to collaboratively train models without sharing their private data. However, the computation and communication cost of directly learning many existing news recommendation models in a federated way are unacceptable for user clients. In this paper, we propose an efficient federated learning framework for privacy-preserving news recommendation. Instead of training and communicating the whole model, we decompose the news recommendation model into a large news model maintained in the server and a light-weight user model shared on both server and clients, where news representations and user model are communicated between server and clients. More specifically, the clients request the user model and news representations from the server, and send their locally computed gradients to the server for aggregation. The server updates its global user model with the aggregated gradients, and further updates its news model to infer updated news representations. Since the local gradients may contain private information, we propose a secure aggregation method to aggregate gradients in a privacy-preserving way. Experiments on two real-world datasets show that our method can reduce the computation and communication cost on clients while keep promising model performance.
Compute and Energy Consumption Trends in Deep Learning Inference
Venue: arXiv cs.LG 2023
Year: 2023

The progress of some AI paradigms such as deep learning is said to be linked to an exponential growth in the number of parameters. There are many studies corroborating these trends, but does this translate into an exponential increase in energy consumption? In order to answer this question we focus on inference costs rather than training costs, as the former account for most of the computing effort, solely because of the multiplicative factors. Also, apart from algorithmic innovations, we account for more specific and powerful hardware (leading to higher FLOPS) that is usually accompanied with important energy efficiency optimisations. We also move the focus from the first implementation of a breakthrough paper towards the consolidated version of the techniques one or two year later. Under this distinctive and comprehensive perspective, we study relevant models in the areas of computer vision and natural language processing: for a sustained increase in performance we see a much softer growth in energy consumption than previously anticipated. The only caveat is, yet again, the multiplicative factor, as future AI increases penetration and becomes more pervasive.
Rethinking Lightweight Convolutional Neural Networks for Efficient and High-quality Pavement Crack Detection
Venue: arXiv cs.CV 2023
Year: 2023

Pixel-level road crack detection has always been a challenging task in intelligent transportation systems. Due to the external environments, such as weather, light, and other factors, pavement cracks often present low contrast, poor continuity, and different sizes in length and width. However, most of the existing studies pay less attention to crack data under different situations. Meanwhile, recent algorithms based on deep convolutional neural networks (DCNNs) have promoted the development of cutting-edge models for crack detection. Nevertheless, they usually focus on complex models for good performance, but ignore detection efficiency in practical applications. In this article, to address the first issue, we collected two new databases (i.e. Rain365 and Sun520) captured in rainy and sunny days respectively, which enrich the data of the open source community. For the second issue, we reconsider how to improve detection efficiency with excellent performance, and then propose our lightweight encoder-decoder architecture termed CarNet. Specifically, we introduce a novel olive-shaped structure for the encoder network, a light-weight multi-scale block and a new up-sampling method in the decoder network. Numerous experiments show that our model can better balance detection performance and efficiency compared with previous models. Especially, on the Sun520 dataset, our CarNet significantly advances the state-of-the-art performance with ODS F-score from 0.488 to 0.514. Meanwhile, it does so with an improved detection speed (104 frame per second) which is orders of magnitude faster than some recent DCNNs-based algorithms specially designed for crack detection.
Computing Balanced Solutions for Large International Kidney Exchange Schemes
Venue: arXiv cs.GT 2023
Year: 2023

To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient-donor pools. We consider a recently introduced credit system. In each round, countries are given an initial ``fair'' allocation of the total number of kidney transplants. This allocation is adjusted by a credit function yielding a target allocation. The goal is to find a solution that approaches the target allocation as closely as possible, to ensure long-term stability of the international pool. As solutions, we use maximum matchings that lexicographically minimize the country deviations from the target allocation. We perform, for the first time, a computational study for a {\it large} number of countries. For the initial allocations we use two easy-to-compute solution concepts, the benefit value and the contribution value, and four classical but hard-to-compute concepts, the Shapley value, nucleolus, Banzhaf value and tau value. By using state-of-the-art software we show that the latter four concepts are now within reach for IKEPs of up to fifteen countries. Our experiments show that using lexicographically minimal maximum matchings instead of ones that only minimize the largest deviation from the target allocation (as previously done) may make an IKEP up to 54% more balanced.
Noise Robust Core-Stable Coalitions of Hedonic Games
Venue: arXiv cs.GT 2023
Year: 2023

We consider the coalition formation games with an additional component, `noisy preferences'. Moreover, such noisy preferences are available only for a sample of coalitions. We propose a multiplicative noise model and obtain the prediction probability, defined as the probability that the estimated PAC core-stable partition of the noisy game is also PAC core-stable for the unknown noise-free game. This prediction probability depends on the probability of a combinatorial construct called an `agreement event'. We explicitly obtain the agreement probability for $n$ agent noisy game with l\geq 2 support noise distribution. For a user-given satisfaction value on this probability, we identify the noise regimes for which an estimated partition is noise robust; that is, it is PAC core-stable in both noisy and noise-free games. We obtain similar robustness results when the estimated partition is not PAC core-stable. These noise regimes correspond to the level sets of the agreement probability function and are non-convex sets. Moreover, an important fact is that the prediction probability can be high even if high noise values occur with a high probability. Further, for a class of top-responsive hedonic games, we obtain the bounds on the extra noisy samples required to get noise robustness with a user-given satisfaction value. We completely solve the noise robustness problem of a $2$ agent hedonic game. In particular, we obtain the prediction probability function for l=2 and l=3 noise support cases. For l=2, the prediction probability is convex in noise probability, but the noise robust regime is non-convex. Its minimum value, called the safety value, is 0.62; so, below 0.62, the noise robust regime is the entire probability simplex. However, for l \geq 3, the prediction probability is non-convex; so, the safety value is the global minima of a non-convex function and is computationally hard.
Comfetch: Federated Learning of Large Networks on Constrained Clients via Sketching
Venue: arXiv cs.LG 2023
Year: 2023

Federated learning (FL) is a popular paradigm for private and collaborative model training on the edge. In centralized FL, the parameters of a global architecture (such as a deep neural network) are maintained and distributed by a central server/controller to clients who transmit model updates (gradients) back to the server based on local optimization. While many efforts have focused on reducing the communication complexity of gradient transmission, the vast majority of compression-based algorithms assume that each participating client is able to download and train the current and full set of parameters, which may not be a practical assumption depending on the resource constraints of smaller clients such as mobile devices. In this work, we propose a simple yet effective novel algorithm, Comfetch, which allows clients to train large networks using reduced representations of the global architecture via the count sketch, which reduces local computational and memory costs along with bi-directional communication complexity. We provide a nonconvex convergence guarantee and experimentally demonstrate that it is possible to learn large models, such as a deep convolutional network, through federated training on their sketched counterparts. The resulting global models exhibit competitive test accuracy over CIFAR10/100 classification when compared against un-compressed model training.
Online Learning of Network Bottlenecks via Minimax Paths
Venue: arXiv cs.LG 2023
Year: 2023

In this paper, we study bottleneck identification in networks via extracting minimax paths. Many real-world networks have stochastic weights for which full knowledge is not available in advance. Therefore, we model this task as a combinatorial semi-bandit problem to which we apply a combinatorial version of Thompson Sampling and establish an upper bound on the corresponding Bayesian regret. Due to the computational intractability of the problem, we then devise an alternative problem formulation which approximates the original objective. Finally, we experimentally evaluate the performance of Thompson Sampling with the approximate formulation on real-world directed and undirected networks.
On the Noise Stability and Robustness of Adversarially Trained Networks on NVM Crossbars
Venue: arXiv cs.LG 2023
Year: 2023

Applications based on Deep Neural Networks (DNNs) have grown exponentially in the past decade. To match their increasing computational needs, several Non-Volatile Memory (NVM) crossbar based accelerators have been proposed. Recently, researchers have shown that apart from improved energy efficiency and performance, such approximate hardware also possess intrinsic robustness for defense against adversarial attacks. Prior works quantified this intrinsic robustness for vanilla DNNs trained on unperturbed inputs. However, adversarial training of DNNs is the benchmark technique for robustness, and sole reliance on intrinsic robustness of the hardware may not be sufficient. In this work, we explore the design of robust DNNs through the amalgamation of adversarial training and intrinsic robustness of NVM crossbar-based analog hardware. First, we study the noise stability of such networks on unperturbed inputs and observe that internal activations of adversarially trained networks have lower Signal-to-Noise Ratio (SNR), and are sensitive to noise compared to vanilla networks. As a result, they suffer on average 2x performance degradation due to the approximate computations on analog hardware. Noise stability analyses show the instability of adversarially trained DNNs. On the other hand, for adversarial images generated using Square Black Box attacks, ResNet-10/20 adversarially trained on CIFAR-10/100 display a robustness gain of 20-30%. For adversarial images generated using Projected-Gradient-Descent (PGD) White-Box attacks, adversarially trained DNNs present a 5-10% gain in robust accuracy due to underlying NVM crossbar when $ε_{attack}$ is greater than $ε_{train}$. Our results indicate that implementing adversarially trained networks on analog hardware requires careful calibration between hardware non-idealities and $ε_{train}$ for optimum robustness and performance.
Adding Negation to Lambda Mu
Venue: arXiv cs.LO 2023
Year: 2023

We present $\cal L$, an extension of Parigot's $λμ$-calculus by adding negation as a type constructor, together with syntactic constructs that represent negation introduction and elimination. We will define a notion of reduction that extends $λμ$'s reduction system with two new reduction rules, and show that the system satisfies subject reduction. Using Aczel's generalisation of Tait and Martin-Löf's notion of parallel reduction, we show that this extended reduction is confluent. Although the notion of type assignment has its limitations with respect to representation of proofs in natural deduction with implication and negation, we will show that all propositions that can be shown in there have a witness in $\cal L$. Using Girard's approach of reducibility candidates, we show that all typeable terms are strongly normalisable, and conclude the paper by showing that type assignment for $\cal L$ enjoys the principal typing property.
Unsupervised Movement Detection in Indoor Positioning Systems of Production Halls
Venue: arXiv cs.LG 2023
Year: 2023

Consider indoor positioning systems (IPS) in production halls where objects equipped with sensors send their current position. Beside its large volume, the analyzation of the resulting raw data is challenging due to the susceptibility towards noise. Reasons are accuracy issues and undesired awakenings of sensors that occur due to the dynamics of logistic processes (e.g.~vibrations of passing forklifts). We propose a tailor-made statistical procedure for these challenges and combine visual analytics with movement detection. Contrary to common stay-point algorithms, we do not only distinguish between stops and moves, but also consider undesired awakenings. This leads to a more detailed interpretation scheme offering usages for online (e.g.~monitoring of orders) and offline applications (e.g.~detection of problematic areas). The approach does not require other information than the raw IPS output and enables an ad-hoc analysis. We underline our findings in an extensive case study with real IPS data of our industry partner.
Code modernization strategies for short-range non-bonded molecular dynamics simulations
Venue: arXiv cs.DC 2023
Year: 2023

Modern HPC systems are increasingly relying on greater core counts and wider vector registers. Thus, applications need to be adapted to fully utilize these hardware capabilities. One class of applications that can benefit from this increase in parallelism are molecular dynamics simulations. In this paper, we describe our efforts at modernizing the ESPResSo++ molecular dynamics simulation package by restructuring its particle data layout for efficient memory accesses and applying vectorization techniques to benefit the calculation of short-range non-bonded forces, which results in an overall three times speedup and serves as a baseline for further optimizations. We also implement fine-grained parallelism for multi-core CPUs through HPX, a C++ runtime system which uses lightweight threads and an asynchronous many-task approach to maximize concurrency. Our goal is to evaluate the performance of an HPX-based approach compared to the bulk-synchronous MPI-based implementation. This requires the introduction of an additional layer to the domain decomposition scheme that defines the task granularity. On spatially inhomogeneous systems, which impose a corresponding load-imbalance in traditional MPI-based approaches, we demonstrate that by choosing an optimal task size, the efficient work-stealing mechanisms of HPX can overcome the overhead of communication resulting in an overall 1.4 times speedup compared to the baseline MPI version.
The Point-to-Set Principle and the Dimensions of Hamel Bases
Venue: arXiv cs.LO 2023
Year: 2023

We prove that every real number in [0,1] is the Hausdorff dimension of a Hamel basis of the vector space of reals over the field of rationals. The logic of our proof is of particular interest. The statement of our theorem is classical; it does not involve the theory of computing. However, our proof makes essential use of algorithmic fractal dimension--a computability-theoretic construct--and the point-to-set principle of J. Lutz and N. Lutz (2018).
A Dynamic Programming Algorithm for Finding an Optimal Sequence of Informative Measurements
Venue: arXiv cs.LG 2023
Year: 2023

An informative measurement is the most efficient way to gain information about an unknown state. We present a first-principles derivation of a general-purpose dynamic programming algorithm that returns an optimal sequence of informative measurements by sequentially maximizing the entropy of possible measurement outcomes. This algorithm can be used by an autonomous agent or robot to decide where best to measure next, planning a path corresponding to an optimal sequence of informative measurements. The algorithm is applicable to states and controls that are either continuous or discrete, and agent dynamics that is either stochastic or deterministic; including Markov decision processes and Gaussian processes. Recent results from the fields of approximate dynamic programming and reinforcement learning, including on-line approximations such as rollout and Monte Carlo tree search, allow the measurement task to be solved in real time. The resulting solutions include non-myopic paths and measurement sequences that can generally outperform, sometimes substantially, commonly used greedy approaches. This is demonstrated for a global search task, where on-line planning for a sequence of local searches is found to reduce the number of measurements in the search by approximately half. A variant of the algorithm is derived for Gaussian processes for active sensing.
Long-Range Transformers for Dynamic Spatiotemporal Forecasting
Venue: arXiv cs.LG 2023
Year: 2023

Multivariate time series forecasting focuses on predicting future values based on historical context. State-of-the-art sequence-to-sequence models rely on neural attention between timesteps, which allows for temporal learning but fails to consider distinct spatial relationships between variables. In contrast, methods based on graph neural networks explicitly model variable relationships. However, these methods often rely on predefined graphs that cannot change over time and perform separate spatial and temporal updates without establishing direct connections between each variable at every timestep. Our work addresses these problems by translating multivariate forecasting into a "spatiotemporal sequence" formulation where each Transformer input token represents the value of a single variable at a given time. Long-Range Transformers can then learn interactions between space, time, and value information jointly along this extended sequence. Our method, which we call Spacetimeformer, achieves competitive results on benchmarks from traffic forecasting to electricity demand and weather prediction while learning spatiotemporal relationships purely from data.