OpenRaiser/Intern-Atlas huggingface dataset:
Multi-view Deep Subspace Clustering Networks
Venue: arXiv cs.CV 2024
Year: 2024

Multi-view subspace clustering aims to discover the inherent structure of data by fusing multiple views of complementary information. Most existing methods first extract multiple types of handcrafted features and then learn a joint affinity matrix for clustering. The disadvantage of this approach lies in two aspects: 1) multi-view relations are not embedded into feature learning, and 2) the end-to-end learning manner of deep learning is not suitable for multi-view clustering. Even when deep features have been extracted, it is a nontrivial problem to choose a proper backbone for clustering on different datasets. To address these issues, we propose the Multi-view Deep Subspace Clustering Networks (MvDSCN), which learns a multi-view self-representation matrix in an end-to-end manner. The MvDSCN consists of two sub-networks, \ie, a diversity network (Dnet) and a universality network (Unet). A latent space is built using deep convolutional autoencoders, and a self-representation matrix is learned in the latent space using a fully connected layer. Dnet learns view-specific self-representation matrices, whereas Unet learns a common self-representation matrix for all views. To exploit the complementarity of multi-view representations, the Hilbert--Schmidt independence criterion (HSIC) is introduced as a diversity regularizer that captures the nonlinear, high-order inter-view relations. Because different views share the same label space, the self-representation matrices of each view are aligned to the common one by universality regularization. The MvDSCN also unifies multiple backbones to boost clustering performance and avoid the need for model selection. Experiments demonstrate the superiority of the MvDSCN.
Deep Generalized Max Pooling
Venue: arXiv cs.CV 2024
Year: 2024

Global pooling layers are an essential part of Convolutional Neural Networks (CNN). They are used to aggregate activations of spatial locations to produce a fixed-size vector in several state-of-the-art CNNs. Global average pooling or global max pooling are commonly used for converting convolutional features of variable size images to a fix-sized embedding. However, both pooling layer types are computed spatially independent: each individual activation map is pooled and thus activations of different locations are pooled together. In contrast, we propose Deep Generalized Max Pooling that balances the contribution of all activations of a spatially coherent region by re-weighting all descriptors so that the impact of frequent and rare ones is equalized. We show that this layer is superior to both average and max pooling on the classification of Latin medieval manuscripts (CLAMM'16, CLAMM'17), as well as writer identification (Historical-WI'17).
Contextual Text Denoising with Masked Language Models
Venue: arXiv cs.CL 2024
Year: 2024

Recently, with the help of deep learning models, significant advances have been made in different Natural Language Processing (NLP) tasks. Unfortunately, state-of-the-art models are vulnerable to noisy texts. We propose a new contextual text denoising algorithm based on the ready-to-use masked language model. The proposed algorithm does not require retraining of the model and can be integrated into any NLP system without additional training on paired cleaning training data. We evaluate our method under synthetic noise and natural noise and show that the proposed algorithm can use context information to correct noise text and improve the performance of noisy inputs in several downstream tasks.
Two Ridge Solutions for the Incremental Broad Learning System on Added Nodes
Venue: arXiv cs.LG 2024
Year: 2024

The original Broad Learning System (BLS) on new added nodes and its existing efficient implementation both assume the ridge parameter lambda -> 0 in the ridge inverse to approximate the generalized inverse, and compute the generalized inverse solution for the output weights. In this paper, we propose two ridge solutions for the output weights in the BLS on added nodes, where lambda -> 0 is no longer assumed, and lambda can be any positive real number. One of the proposed ridge solutions computes the output weights from the inverse Cholesky factor, which is updated efficiently by extending the existing inverse Cholesky factorization. The other proposed ridge solution computes the output weights from the ridge inverse, and updates the ridge inverse by extending the Greville's method that is a classical tool to compute the generalized inverse of partitioned matrices. For the proposed efficient ridge solution based on the inverse Cholesky factor, we also develop another implementation that is numerically more stable when the ridge parameter lambda is very small. The proposed ridge solution based on the ridge inverse and the numerically more stable implementation of the proposed efficient ridge solution require the same complexity as the original BLS and the existing efficient BLS, respectively. Moreover, the speedups of the proposed efficient ridge solution to the original BLS and the existing efficient BLS are 3 and more than 1.67 respectively, when the computational complexities for each update are compared, and the speedups are 1.99 - 2.52 and 1.31 - 1.58, respectively, when the total training time is compared by numerical experiments. On the other hand, our numerical experiments show that both the proposed ridge solutions for BLS achieve better testing accuracies than the original BLS and the existing efficient BLS.
Gamifying the Vehicle Routing Problem with Stochastic Requests
Venue: arXiv cs.LG 2024
Year: 2024

Do you remember your first video game console? We remember ours. Decades ago, they provided hours of entertainment. Now, we have repurposed them to solve dynamic and stochastic optimization problems. With deep reinforcement learning methods posting superhuman performance on a wide range of Atari games, we consider the task of representing a classic logistics problem as a game. Then, we train agents to play it. We consider several game designs for the vehicle routing problem with stochastic requests. We show how various design features impact agents' performance, including perspective, field of view, and minimaps. With the right game design, general purpose Atari agents outperform optimization-based benchmarks, especially as problem size grows. Our work points to the representation of dynamic and stochastic optimization problems via games as a promising research direction.
Neural Random Forest Imitation
Venue: arXiv cs.LG 2024
Year: 2024

We present Neural Random Forest Imitation - a novel approach for transforming random forests into neural networks. Existing methods propose a direct mapping and produce very inefficient architectures. In this work, we introduce an imitation learning approach by generating training data from a random forest and learning a neural network that imitates its behavior. This implicit transformation creates very efficient neural networks that learn the decision boundaries of a random forest. The generated model is differentiable, can be used as a warm start for fine-tuning, and enables end-to-end optimization. Experiments on several real-world benchmark datasets demonstrate superior performance, especially when training with very few training examples. Compared to state-of-the-art methods, we significantly reduce the number of network parameters while achieving the same or even improved accuracy due to better generalization.
An Urban Water Extraction Method Combining Deep Learning and Google Earth Engine
Venue: arXiv cs.CV 2024
Year: 2024

Urban water is important for the urban ecosystem. Accurate and efficient detection of urban water with remote sensing data is of great significance for urban management and planning. In this paper, we proposed a new method to combine Google Earth Engine (GEE) with multiscale convolutional neural network (MSCNN) to extract urban water from Landsat images, which is summarized as offline training and online prediction (OTOP). That is, the training of MSCNN was completed offline, and the process of urban water extraction was implemented on GEE with the trained parameters of MSCNN. The OTOP can give full play to the respective advantages of GEE and CNN, and make the use of deep learning method on GEE more flexible. It can process available satellite images with high performance without data download and storage, and the overall performance of urban water extraction is also higher than that of the modified normalized difference water index (MNDWI) and random forest. The mean kappa, F1-score and intersection over union (IoU) of urban water extraction with the OTOP in Changchun, Wuhan, Kunming and Guangzhou reached 0.924, 0.930 and 0.869, respectively. The results of the extended validation in the other major cities of China also show that the OTOP is robust and can be used to extract different types of urban water, which benefits from the structural design and training of the MSCNN. Therefore, the OTOP is especially suitable for the study of large-scale and long-term urban water change detection in the background of urbanization.
Faster Transformer Decoding: N-gram Masked Self-Attention
Venue: arXiv cs.LG 2024
Year: 2024

Motivated by the fact that most of the information relevant to the prediction of target tokens is drawn from the source sentence $S=s_1, \ldots, s_S$, we propose truncating the target-side window used for computing self-attention by making an $N$-gram assumption. Experiments on WMT EnDe and EnFr data sets show that the $N$-gram masked self-attention model loses very little in BLEU score for $N$ values in the range $4, \ldots, 8$, depending on the task.
Profunctor Optics, a Categorical Update
Venue: arXiv cs.PL 2024
Year: 2024

Optics are bidirectional data accessors that capture data transformation patterns such as accessing subfields or iterating over containers. Profunctor optics are a particular choice of representation supporting modularity, meaning that we can construct accessors for complex structures by combining simpler ones. Profunctor optics have previously been studied only in an unenriched and non-mixed setting, in which both directions of access are modelled in the same category. However, functional programming languages are arguably better described by enriched categories; and we have found that some structures in the literature are actually mixed optics, with access directions modelled in different categories. Our work generalizes a classic result by Pastro and Street on Tambara theory and uses it to describe mixed V-enriched profunctor optics and to endow them with V-category structure. We provide some original families of optics and derivations, including an elementary one for traversals. Finally, we discuss a Haskell implementation.
Function approximation by neural nets in the mean-field regime: Entropic regularization and controlled McKean-Vlasov dynamics
Venue: arXiv cs.LG 2024
Year: 2024

We consider the problem of function approximation by two-layer neural nets with random weights that are "nearly Gaussian" in the sense of Kullback-Leibler divergence. Our setting is the mean-field limit, where the finite population of neurons in the hidden layer is replaced by a continuous ensemble. We show that the problem can be phrased as global minimization of a free energy functional on the space of (finite-length) paths over probability measures on the weights. This functional trades off the $L^2$ approximation risk of the terminal measure against the KL divergence of the path with respect to an isotropic Brownian motion prior. We characterize the unique global minimizer and examine the dynamics in the space of probability measures over weights that can achieve it. In particular, we show that the optimal path-space measure corresponds to the Föllmer drift, the solution to a McKean-Vlasov optimal control problem closely related to the classic Schrödinger bridge problem. While the Föllmer drift cannot in general be obtained in closed form, thus limiting its potential algorithmic utility, we illustrate the viability of the mean-field Langevin diffusion as a finite-time approximation under various conditions on entropic regularization. Specifically, we show that it closely tracks the Föllmer drift when the regularization is such that the minimizing density is log-concave.
Session: End-To-End Encrypted Conversations With Minimal Metadata Leakage
Venue: arXiv cs.CR 2024
Year: 2024

Session is an open-source, public-key-based secure messaging application which uses a set of decentralised storage servers and an onion routing protocol to send end-to-end encrypted messages with minimal exposure of user metadata. It does this while providing the common features expected of mainstream messaging applications, such as multi-device syncing, offline inboxes, and voice/video calling.
Periodicity Pitch Detection in Complex Harmonies on EEG Timeline Data
Venue: arXiv cs.SD 2024
Year: 2024

An acoustic stimulus, e.g., a musical harmony, is transformed in a highly non-linear way during the hearing process in ear and brain. We study this by comparing the frequency spectrum of an input stimulus and its response spectrum in the auditory processing stream using the frequency following response (FFR). Using electroencephalography (EEG), we investigate whether the periodicity pitches of complex harmonies (which are related to their missing fundamentals) are added in the auditory brainstem by analyzing the FFR. While other experiments focus on common musical harmonies like the major and the minor triad and dyads, we also consider the suspended chord. The suspended chord causes tension foreign to the common triads and therefore holds a special role among the triads. While watching a muted nature documentary, the participants hear synthesized classic piano triads and single tones with a duration of 300ms for the stimulus and 100ms interstimulus interval. We acquired EEG data of 64 electrodes with a sampling rate of 5kHz to get a detailed enough resolution of the perception process in the human brain. Applying a fast Fourier transformation (FFT) on the EEG response, starting 50ms after stimulus onset, the evaluation of the frequency spectra shows that the periodicity pitch frequencies calculated beforehand +/-3Hz occur with some accuracy. However, jitter turned out as a problem here. Note that the sought-for periodicity pitch frequencies do not physically exist in the frequency spectra of the stimuli.
Adaptive Graph Auto-Encoder for General Data Clustering
Venue: arXiv cs.LG 2024
Year: 2024

Graph-based clustering plays an important role in the clustering area. Recent studies about graph convolution neural networks have achieved impressive success on graph type data. However, in general clustering tasks, the graph structure of data does not exist such that the strategy to construct a graph is crucial for performance. Therefore, how to extend graph convolution networks into general clustering tasks is an attractive problem. In this paper, we propose a graph auto-encoder for general data clustering, which constructs the graph adaptively according to the generative perspective of graphs. The adaptive process is designed to induce the model to exploit the high-level information behind data and utilize the non-Euclidean structure sufficiently. We further design a novel mechanism with rigorous analysis to avoid the collapse caused by the adaptive construction. Via combining the generative model for network embedding and graph-based clustering, a graph auto-encoder with a novel decoder is developed such that it performs well in weighted graph used scenarios. Extensive experiments prove the superiority of our model.
Quantized Decentralized Stochastic Learning over Directed Graphs
Venue: arXiv cs.DC 2024
Year: 2024

We consider a decentralized stochastic learning problem where data points are distributed among computing nodes communicating over a directed graph. As the model size gets large, decentralized learning faces a major bottleneck that is the heavy communication load due to each node transmitting large messages (model updates) to its neighbors. To tackle this bottleneck, we propose the quantized decentralized stochastic learning algorithm over directed graphs that is based on the push-sum algorithm in decentralized consensus optimization. More importantly, we prove that our algorithm achieves the same convergence rates of the decentralized stochastic learning algorithm with exact-communication for both convex and non-convex losses. Numerical evaluations corroborate our main theoretical results and illustrate significant speed-up compared to the exact-communication methods.
Deep Learning-based CSI Feedback for RIS-assisted Multi-user Systems
Venue: arXiv cs.IT 2024
Year: 2024

In the realm of reconfigurable intelligent surface (RIS)-assisted wireless communications, efficient channel state information (CSI) feedback is paramount. This paper introduces RIS-CoCsiNet, a novel deep learning-based framework designed to greatly enhance feedback efficiency. By leveraging the inherent correlation among proximate user equipments (UEs), our approach strategically categorizes RIS-UE CSI into shared and unique data sets. This nuanced understanding allows for significant reductions in feedback overhead, as the shared data is no longer redundantly relayed. Setting RIS-CoCsiNet apart from traditional autoencoder systems, we incorporate an additional decoder and a combination neural network at the base station. These enhancements are tasked with the precise retrieval and fusion of shared and individual data. And notably, all these innovations are achieved without modifying the UEs. For those UEs boasting multiple antennas, our design seamlessly integrates long short-term memory modules, capturing the intricate correlations between antennas. With a recognition of the non-sparse nature of the RIS-UE CSI phase, we pioneer two magnitude-dependent phase feedback strategies. These strategies adeptly weave in both statistical and real-time CSI magnitude data. The potency of RIS-CoCsiNet is further solidified through compelling simulation results drawn from two diverse channel datasets.
SMap: Internet-wide Scanning for Spoofing
Venue: arXiv cs.CR 2024
Year: 2024

To protect themselves from attacks, networks need to enforce ingress filtering, i.e., block inbound packets sent from spoofed IP addresses. Although this is a widely known best practice, it is still not clear how many networks do not block spoofed packets. Inferring the extent of spoofability at Internet scale is challenging and despite multiple efforts the existing studies currently cover only a limited set of the Internet networks: they can either measure networks that operate servers with faulty network-stack implementations, or require installation of the measurement software on volunteer networks, or assume specific properties, like traceroute loops. Improving coverage of the spoofing measurements is critical. In this work we present the Spoofing Mapper (SMap): the first scanner for performing Internet-wide studies of ingress filtering. SMap evaluates spoofability of networks utilising standard protocols that are present in almost any Internet network. We applied SMap for Internet-wide measurements of ingress filtering: we found that 69.8% of all the Autonomous Systems (ASes) in the Internet do not filter spoofed packets and found 46880 new spoofable ASes which were not identified in prior studies. Our measurements with SMap provide the first comprehensive view of ingress filtering deployment in the Internet as well as remediation in filtering spoofed packets over a period of two years until May 2021. We set up a web service at https://smap.cad.sit.fraunhofer.de to perform continual Internet-wide data collection with SMap and display statistics from spoofing evaluation. We make our datasets as well as the SMap (implementation and the source code) publicly available to enable researchers to reproduce and validate our results, as well as to continually keep track of changes in filtering spoofed packets in the Internet.
The Local Information Cost of Distributed Graph Spanners
Venue: arXiv cs.DC 2024
Year: 2024

We introduce the \emph{local information cost} (LIC), which quantifies the amount of information that nodes in a network need to learn when solving a graph problem. We show that the local information cost presents a natural lower bound on the communication complexity of distributed algorithms. For the synchronous CONGEST KT1 model, where each node has initial knowledge of its neighbors' IDs, we prove that $Ω(\frac{\text{LIC}_γ(P)}{\logτ\log n})$ bits are required for solving a graph problem $P$ with a $τ$-round algorithm that errs with probability at most $γ$. Our result is the first lower bound that yields a general trade-off between communication and time for graph problems in the CONGEST KT1 model. We demonstrate how to apply the local information cost by deriving a lower bound on the communication complexity of computing a spanner with multiplicative stretch $2t-1$ that consists of at most $O(n^{1+\frac{1}{t} + ε})$ edges, where $ε= O( {1}/{t^2} )$. More concretely, we show that any $O(\text{poly}(n))$-time spanner algorithm must send at least $\tildeΩ(\tfrac{1}{t^2} n^{1+{1}/{2t}})$ bits. Previously, only a trivial lower bound of $\tilde Ω(n)$ bits was known for this problem. (See PDF for the full abstract.)
A Theory of the Risk for Optimization with Relaxation and its Application to Support Vector Machines
Venue: arXiv cs.LG 2024
Year: 2024

In this paper we consider optimization with relaxation, an ample paradigm to make data-driven designs. This approach was previously considered by the same authors of this work in Garatti and Campi (2019), a study that revealed a deep-seated connection between two concepts: risk (probability of not satisfying a new, out-of-sample, constraint) and complexity (according to a definition introduced in paper Garatti and Campi (2019)). This connection was shown to have profound implications in applications because it implied that the risk can be estimated from the complexity, a quantity that can be measured from the data without any knowledge of the data-generation mechanism. In the present work we establish new results. First, we expand the scope of Garatti and Campi (2019) so as to embrace a more general setup that covers various algorithms in machine learning. Then, we study classical support vector methods - including SVM (Support Vector Machine), SVR (Support Vector Regression) and SVDD (Support Vector Data Description) - and derive new results for the ability of these methods to generalize. All results are valid for any finite size of the data set. When the sample size tends to infinity, we establish the unprecedented result that the risk approaches the ratio between the complexity and the cardinality of the data sample, regardless of the value of the complexity.
When Votes Change and Committees Should (Not)
Venue: arXiv cs.CC 2024
Year: 2024

Electing a single committee of a small size is a classical and well-understood voting situation. Being interested in a sequence of committees, we introduce and study two time-dependent multistage models based on simple Plurality voting. Therein, we are given a sequence of voting profiles (stages) over the same set of agents and candidates, and our task is to find a small committee for each stage of high score. In the conservative model we additionally require that any two consecutive committees have a small symmetric difference. Analogously, in the revolutionary model we require large symmetric differences. We prove both models to be NP-hard even for a constant number of agents, and, based on this, initiate a parameterized complexity analysis for the most natural parameters and combinations thereof. Among other results, we prove both models to be in XP yet W[1]-hard regarding the number of stages, and that being revolutionary seems to be "easier" than being conservative: If the (upper- resp. lower-) bound on the size of symmetric differences is constant, the conservative model remains NP-hard while the revolutionary model becomes polynomial-time solvable.