OpenRaiser/Intern-Atlas huggingface dataset:
Open-Ended Multi-Modal Relational Reasoning for Video Question Answering
Venue: arXiv cs.AI 2024
Year: 2024

In this paper, we introduce a robotic agent specifically designed to analyze external environments and address participants' questions. The primary focus of this agent is to assist individuals using language-based interactions within video-based scenes. Our proposed method integrates video recognition technology and natural language processing models within the robotic agent. We investigate the crucial factors affecting human-robot interactions by examining pertinent issues arising between participants and robot agents. Methodologically, our experimental findings reveal a positive relationship between trust and interaction efficiency. Furthermore, our model demonstrates a 2\% to 3\% performance enhancement in comparison to other benchmark methods.
Enhancing Human Pose Estimation in Ancient Vase Paintings via Perceptually-grounded Style Transfer Learning
Venue: arXiv cs.CV 2024
Year: 2024

Human pose estimation (HPE) is a central part of understanding the visual narration and body movements of characters depicted in artwork collections, such as Greek vase paintings. Unfortunately, existing HPE methods do not generalise well across domains resulting in poorly recognized poses. Therefore, we propose a two step approach: (1) adapting a dataset of natural images of known person and pose annotations to the style of Greek vase paintings by means of image style-transfer. We introduce a perceptually-grounded style transfer training to enforce perceptual consistency. Then, we fine-tune the base model with this newly created dataset. We show that using style-transfer learning significantly improves the SOTA performance on unlabelled data by more than 6% mean average precision (mAP) as well as mean average recall (mAR). (2) To improve the already strong results further, we created a small dataset (ClassArch) consisting of ancient Greek vase paintings from the 6-5th century BCE with person and pose annotations. We show that fine-tuning on this data with a style-transferred model improves the performance further. In a thorough ablation study, we give a targeted analysis of the influence of style intensities, revealing that the model learns generic domain styles. Additionally, we provide a pose-based image retrieval to demonstrate the effectiveness of our method.
Hard QBFs for Merge Resolution
Venue: arXiv cs.CC 2024
Year: 2024

We prove the first genuine QBF proof size lower bounds for the proof system Merge Resolution (MRes [Olaf Beyersdorff et al., 2020]), a refutational proof system for prenex quantified Boolean formulas (QBF) with a CNF matrix. Unlike most QBF resolution systems in the literature, proofs in MRes consist of resolution steps together with information on countermodels, which are syntactically stored in the proofs as merge maps. As demonstrated in [Olaf Beyersdorff et al., 2020], this makes MRes quite powerful: it has strategy extraction by design and allows short proofs for formulas which are hard for classical QBF resolution systems. Here we show the first genuine QBF exponential lower bounds for MRes, thereby uncovering limitations of MRes. Technically, the results are either transferred from bounds from circuit complexity (for restricted versions of MRes) or directly obtained by combinatorial arguments (for full MRes). Our results imply that the MRes approach is largely orthogonal to other QBF resolution models such as the QCDCL resolution systems QRes and QURes and the expansion systems $\forall$Exp+Res and IR.
A New Perspective to Node Influence Evaluation in Complex Network Using Subgraph Tr-Centrality
Venue: arXiv cs.SI 2024
Year: 2024

There is great significance in evaluating a node's Influence ranking in complex networks. Over the years, many researchers have presented different measures for quantifying node interconnectedness within networks. Therefore, this paper introduces a centrality measure called Tr-centrality which focuses on using the node triangle structure and the node neighborhood information to define the strength of a node, which is defined as the summation of Gruebler's Equation of the node's one-hop triangle neighborhood to the number of all the edges in the subgraph. Furthermore, we socially consider it as the local trust of a node. To verify the validity of Tr-centrality [1], we apply it to four real-world networks with different densities and shapes, and Tr-centrality has proven to yield better results.
Privacy-Constrained Policies via Mutual Information Regularized Policy Gradients
Venue: arXiv cs.LG 2024
Year: 2024

As reinforcement learning techniques are increasingly applied to real-world decision problems, attention has turned to how these algorithms use potentially sensitive information. We consider the task of training a policy that maximizes reward while minimizing disclosure of certain sensitive state variables through the actions. We give examples of how this setting covers real-world problems in privacy for sequential decision-making. We solve this problem in the policy gradients framework by introducing a regularizer based on the mutual information (MI) between the sensitive state and the actions. We develop a model-based stochastic gradient estimator for optimization of privacy-constrained policies. We also discuss an alternative MI regularizer that serves as an upper bound to our main MI regularizer and can be optimized in a model-free setting, and a powerful direct estimator that can be used in an environment with differentiable dynamics. We contrast previous work in differentially-private RL to our mutual-information formulation of information disclosure. Experimental results show that our training method results in policies that hide the sensitive state, even in challenging high-dimensional tasks.
Enhancing Sindhi Word Segmentation using Subword Representation Learning and Position-aware Self-attention
Venue: arXiv cs.CL 2024
Year: 2024

Sindhi word segmentation is a challenging task due to space omission and insertion issues. The Sindhi language itself adds to this complexity. It's cursive and consists of characters with inherent joining and non-joining properties, independent of word boundaries. Existing Sindhi word segmentation methods rely on designing and combining hand-crafted features. However, these methods have limitations, such as difficulty handling out-of-vocabulary words, limited robustness for other languages, and inefficiency with large amounts of noisy or raw text. Neural network-based models, in contrast, can automatically capture word boundary information without requiring prior knowledge. In this paper, we propose a Subword-Guided Neural Word Segmenter (SGNWS) that addresses word segmentation as a sequence labeling task. The SGNWS model incorporates subword representation learning through a bidirectional long short-term memory encoder, position-aware self-attention, and a conditional random field. Our empirical results demonstrate that the SGNWS model achieves state-of-the-art performance in Sindhi word segmentation on six datasets.
Gated Ensemble of Spatio-temporal Mixture of Experts for Multi-task Learning in Ride-hailing System
Venue: arXiv cs.LG 2024
Year: 2024

Ride-hailing system requires efficient management of dynamic demand and supply to ensure optimal service delivery, pricing strategies, and operational efficiency. Designing spatio-temporal forecasting models separately in a task-wise and city-wise manner to forecast demand and supply-demand gap in a ride-hailing system poses a burden for the expanding transportation network companies. Therefore, a multi-task learning architecture is proposed in this study by developing gated ensemble of spatio-temporal mixture of experts network (GESME-Net) with convolutional recurrent neural network (CRNN), convolutional neural network (CNN), and recurrent neural network (RNN) for simultaneously forecasting these spatio-temporal tasks in a city as well as across different cities. Furthermore, a task adaptation layer is integrated with the architecture for learning joint representation in multi-task learning and revealing the contribution of the input features utilized in prediction. The proposed architecture is tested with data from Didi Chuxing for: (i) simultaneously forecasting demand and supply-demand gap in Beijing, and (ii) simultaneously forecasting demand across Chengdu and Xian. In both scenarios, models from our proposed architecture outperformed the single-task and multi-task deep learning benchmarks and ensemble-based machine learning algorithms.
Het-node2vec: second order random walk sampling for heterogeneous multigraphs embedding
Venue: arXiv cs.LG 2024
Year: 2024

Many real-world problems are naturally modeled as heterogeneous graphs, where nodes and edges represent multiple types of entities and relations. Existing learning models for heterogeneous graph representation usually depend on the computation of specific and user-defined heterogeneous paths, or in the application of large and often not scalable deep neural network architectures. We propose Het-node2vec, an extension of the node2vec algorithm, designed for embedding heterogeneous graphs. Het-node2vec addresses the challenge of capturing the topological and structural characteristics of graphs and the semantic information underlying the different types of nodes and edges of heterogeneous graphs, by introducing a simple stochastic node and edge type switching strategy in second order random walk processes. The proposed approach also introduces an ''attention mechanism'' to focus the random walks on specific node and edge types, thus allowing more accurate embeddings and more focused predictions on specific node and edge types of interest. Empirical results on benchmark datasets show that Hetnode2vec achieves comparable or superior performance with respect to state-of-the-art methods for heterogeneous graphs in node label and edge prediction tasks.
BE-RAN: Blockchain-enabled Open RAN for 6G with DID and Privacy-Preserving Communication
Venue: arXiv cs.CR 2024
Year: 2024

As 6G networks evolve towards a synergistic system of Communication, Sensing, and Computing, Radio Access Networks become more distributed, necessitating robust end-to-end authentication. We propose Blockchain-enabled Radio Access Networks, a novel decentralized RAN architecture enhancing security, privacy, and efficiency in authentication processes. BE-RAN leverages distributed ledger technology to establish trust, offering user-centric identity management, enabling mutual authentication, and facilitating on-demand point-to-point inter-network elements and UE-UE communication with accountable logging and billing service add-on for public network users, all without relying on centralized authorities. We envision a thoroughly decentralized RAN model and propose a privacy-preserving P2P communication approach that complements existing security measures while supporting the CSC paradigm. Results demonstrate BE-RAN significantly reduces communication and computation overheads, enhances privacy through decentralized identity management, and facilitates CSC integration, advancing towards more efficient and secure 6G networks.
FDApy: a Python package for functional data
Venue: arXiv cs.MS 2024
Year: 2024

We introduce FDApy, an open-source Python package for the analysis of functional data. The package provides tools for the representation of (multivariate) functional data defined on different dimensional domains and for functional data that is irregularly sampled. Additionally, dimension reduction techniques are implemented for multivariate and/or multidimensional functional data that are regularly or irregularly sampled. A toolbox for generating functional datasets is also provided. The documentation includes installation and usage instructions, examples on simulated and real datasets and a complete description of the API. FDApy is released under the MIT license. The code and documentation are available at https://github.com/StevenGolovkine/FDApy.
Private DNA Sequencing: Hiding Information in Discrete Noise
Venue: arXiv cs.IT 2024
Year: 2024

When an individual's DNA is sequenced, sensitive medical information becomes available to the sequencing laboratory. A recently proposed way to hide an individual's genetic information is to mix in DNA samples of other individuals. We assume that the genetic content of these samples is known to the individual but unknown to the sequencing laboratory. Thus, these DNA samples act as "noise" to the sequencing laboratory, but still allow the individual to recover their own DNA samples afterward. Motivated by this idea, we study the problem of hiding a binary random variable $X$ (a genetic marker) with the additive noise provided by mixing DNA samples, using mutual information as a privacy metric. This is equivalent to the problem of finding a worst-case noise distribution for recovering $X$ from the noisy observation among a set of feasible discrete distributions. We characterize upper and lower bounds to the solution of this problem, which are empirically shown to be very close. The lower bound is obtained through a convex relaxation of the original discrete optimization problem, and yields a closed-form expression. The upper bound is computed via a greedy algorithm for selecting the mixing proportions.
Graphs of Joint Types, Noninteractive Simulation, and Stronger Hypercontractivity
Venue: arXiv cs.IT 2024
Year: 2024

In this paper, we study the type graph, namely, a bipartite graph induced by a joint type. We investigate the maximum edge density of induced bipartite subgraphs of this graph having a number of vertices on each side on an exponential scale in the length $n$ of the type. This can be seen as an isoperimetric problem. We provide asymptotically sharp bounds for the exponent of the maximum edge density as the length of the type goes to infinity. We also study the biclique rate region of the type graph, which is defined as the set of $(R_{1},R_{2})$ such that there exists a biclique of the type graph which has respectively $2^{nR_{1}}$ and $2^{nR_{2}}$ vertices on the two sides. We provide asymptotically sharp bounds for the biclique rate region as well. We then discuss the connections of these results to noninteractive simulation and hypercontractivity inequalities. Furthermore, as an application of our results, a new outer bound for the zero-error capacity region of the binary adder channel is provided, which improves the previously best known bound, due to Austrin, Kaski, Koivisto, and Nederlof. Our proofs in this paper are based on the method of types and linear algebra.
Probabilistic Trust Intervals for Out of Distribution Detection
Venue: arXiv cs.LG 2024
Year: 2024

The ability of a deep learning network to distinguish between in-distribution (ID) and out-of-distribution (OOD) inputs is crucial for ensuring the reliability and trustworthiness of AI systems. Existing OOD detection methods often involve complex architectural innovations, such as ensemble models, which, while enhancing detection accuracy, significantly increase model complexity and training time. Other methods utilize surrogate samples to simulate OOD inputs, but these may not generalize well across different types of OOD data. In this paper, we propose a straightforward yet novel technique to enhance OOD detection in pre-trained networks without altering its original parameters. Our approach defines probabilistic trust intervals for each network weight, determined using in-distribution data. During inference, additional weight values are sampled, and the resulting disagreements among outputs are utilized for OOD detection. We propose a metric to quantify this disagreement and validate its effectiveness with empirical evidence. Our method significantly outperforms various baseline methods across multiple OOD datasets without requiring actual or surrogate OOD samples. We evaluate our approach on MNIST, Fashion-MNIST, CIFAR-10, CIFAR-100 and CIFAR-10-C (a corruption-augmented version of CIFAR-10), across various neural network architectures (e.g., VGG-16, ResNet-20, DenseNet-100). On the MNIST-FashionMNIST setup, our method achieves a False Positive Rate (FPR) of 12.46\% at 95\% True Positive Rate (TPR), compared to 27.09\% achieved by the best baseline. On adversarial and corrupted datasets such as CIFAR-10-C, our proposed method easily differentiate between clean and noisy inputs. These results demonstrate the robustness of our approach in identifying corrupted and adversarial inputs, all without requiring OOD samples during training.
Minimum projective linearizations of trees in linear time
Venue: arXiv cs.DS 2024
Year: 2024

The Minimum Linear Arrangement problem (MLA) consists of finding a mapping $π$ from vertices of a graph to distinct integers that minimizes $\sum_{\{u,v\}\in E}|π(u) - π(v)|$. In that setting, vertices are often assumed to lie on a horizontal line and edges are drawn as semicircles above said line. For trees, various algorithms are available to solve the problem in polynomial time in $n=|V|$. There exist variants of the MLA in which the arrangements are constrained. Iordanskii, and later Hochberg and Stallmann (HS), put forward $O(n)$-time algorithms that solve the problem when arrangements are constrained to be planar (also known as one-page book embeddings). We also consider linear arrangements of rooted trees that are constrained to be projective (planar embeddings where the root is not covered by any edge). Gildea and Temperley (GT) sketched an algorithm for projective arrangements which they claimed runs in $O(n)$ but did not provide any justification of its cost. In contrast, Park and Levy claimed that GT's algorithm runs in $O(n \log d_{max})$ where $d_{max}$ is the maximum degree but did not provide sufficient detail. Here we correct an error in HS's algorithm for the planar case, show its relationship with the projective case, and derive simple algorithms for the projective and planar cases that run without a doubt in $O(n)$ time.
Output Perturbation for Differentially Private Convex Optimization: Faster and More General
Venue: arXiv cs.LG 2024
Year: 2024

Finding efficient, easily implementable differentially private (DP) algorithms that offer strong excess risk bounds is an important problem in modern machine learning. To date, most work has focused on private empirical risk minimization (ERM) or private stochastic convex optimization (SCO), which corresponds to population loss minimization. However, there are often other objectives-such as fairness, adversarial robustness, or sensitivity to outliers-besides average performance that are not captured in the classical ERM/SCO setups. Further, most recent work in private SCO has focused on $(\varepsilon, δ)$-DP ($δ> 0$), whereas proving tight excess risk and runtime bounds for $(\varepsilon, 0)$-differential privacy remains a challenging open problem. Our first contribution is to provide the tightest known $(\varepsilon, 0)$-differentially private expected population loss bounds and fastest runtimes for smooth and strongly convex loss functions. In particular, for SCO with well-conditioned smooth and strongly convex loss functions, we provide a linear-time algorithm with optimal excess risk. For our second contribution, we study DP optimization for a broad class of tilted loss functions-which can be used to promote fairness or robustness, and are not necessarily of ERM form. We establish the first known DP excess risk and runtime bounds for optimizing this class; under smoothness and strong convexity assumptions, our bounds are near optimal. For our third contribution, we specialize our theory to DP adversarial training. Our results are achieved using perhaps the simplest yet practical differentially private algorithm: output perturbation. Although this method is not novel conceptually, our novel implementation scheme and analysis show that the power of this method to achieve strong privacy, utility, and runtime guarantees has not been fully appreciated in prior works.
Private Prediction Sets
Venue: arXiv cs.LG 2024
Year: 2024

In real-world settings involving consequential decision-making, the deployment of machine learning systems generally requires both reliable uncertainty quantification and protection of individuals' privacy. We present a framework that treats these two desiderata jointly. Our framework is based on conformal prediction, a methodology that augments predictive models to return prediction sets that provide uncertainty quantification -- they provably cover the true response with a user-specified probability, such as 90%. One might hope that when used with privately-trained models, conformal prediction would yield privacy guarantees for the resulting prediction sets; unfortunately, this is not the case. To remedy this key problem, we develop a method that takes any pre-trained predictive model and outputs differentially private prediction sets. Our method follows the general approach of split conformal prediction; we use holdout data to calibrate the size of the prediction sets but preserve privacy by using a privatized quantile subroutine. This subroutine compensates for the noise introduced to preserve privacy in order to guarantee correct coverage. We evaluate the method on large-scale computer vision datasets.
Explaining Neural Scaling Laws
Venue: arXiv cs.LG 2024
Year: 2024

The population loss of trained deep neural networks often follows precise power-law scaling relations with either the size of the training dataset or the number of parameters in the network. We propose a theory that explains the origins of and connects these scaling laws. We identify variance-limited and resolution-limited scaling behavior for both dataset and model size, for a total of four scaling regimes. The variance-limited scaling follows simply from the existence of a well-behaved infinite data or infinite width limit, while the resolution-limited regime can be explained by positing that models are effectively resolving a smooth data manifold. In the large width limit, this can be equivalently obtained from the spectrum of certain kernels, and we present evidence that large width and large dataset resolution-limited scaling exponents are related by a duality. We exhibit all four scaling regimes in the controlled setting of large random feature and pretrained models and test the predictions empirically on a range of standard architectures and datasets. We also observe several empirical relationships between datasets and scaling exponents under modifications of task and architecture aspect ratio. Our work provides a taxonomy for classifying different scaling regimes, underscores that there can be different mechanisms driving improvements in loss, and lends insight into the microscopic origins of and relationships between scaling exponents.
Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes
Venue: arXiv cs.LG 2024
Year: 2024

In this article, we consider convergence of stochastic gradient descent schemes (SGD), including momentum stochastic gradient descent (MSGD), under weak assumptions on the underlying landscape. More explicitly, we show that on the event that the SGD stays bounded we have convergence of the SGD if there is only a countable number of critical points or if the objective function satisfies Lojasiewicz-inequalities around all critical levels as all analytic functions do. In particular, we show that for neural networks with analytic activation function such as softplus, sigmoid and the hyperbolic tangent, SGD converges on the event of staying bounded, if the random variables modelling the signal and response in the training are compactly supported.