OpenRaiser/Intern-Atlas huggingface dataset:
Regret and Belief Complexity Trade-off in Gaussian Process Bandits via Information Thresholding
Venue: arXiv cs.LG 2022
Year: 2022

Bayesian optimization is a framework for global search via maximum a posteriori updates rather than simulated annealing, and has gained prominence for decision-making under uncertainty. In this work, we cast Bayesian optimization as a multi-armed bandit problem, where the payoff function is sampled from a Gaussian process (GP). Further, we focus on action selections via upper confidence bound (UCB) or expected improvement (EI) due to their prevalent use in practice. Prior works using GPs for bandits cannot allow the iteration horizon $T$ to be large, as the complexity of computing the posterior parameters scales cubically with the number of past observations. To circumvent this computational burden, we propose a simple statistical test: only incorporate an action into the GP posterior when its conditional entropy exceeds an $ε$ threshold. Doing so permits us to precisely characterize the trade-off between regret bounds of GP bandit algorithms and complexity of the posterior distributions depending on the compression parameter $ε$ for both discrete and continuous action sets. To best of our knowledge, this is the first result which allows us to obtain sublinear regret bounds while still maintaining sublinear growth rate of the complexity of the posterior which is linear in the existing literature. Moreover, a provably finite bound on the complexity could be achieved but the algorithm would result in $ε$-regret which means $\textbf{Reg}_T/T \rightarrow \mathcal{O}(ε)$ as $T\rightarrow \infty$. Experimentally, we observe state of the art accuracy and complexity trade-offs for GP bandit algorithms applied to global optimization, suggesting the merits of compressed GPs in bandit settings.
Fair allocation of indivisible items with conflict graphs
Venue: arXiv cs.DM 2022
Year: 2022

We consider the fair allocation of indivisible items to several agents and add a graph theoretical perspective to this classical problem. Namely, we introduce an incompatibility relation between pairs of items described in terms of a conflict graph. Every subset of items assigned to one agent has to form an independent set in this graph. Thus, the allocation of items to the agents corresponds to a partial coloring of the conflict graph. Every agent has its own profit valuation for every item. Aiming at a fair allocation, our goal is the maximization of the lowest total profit of items allocated to any one of the agents. The resulting optimization problem contains, as special cases, both Partition and Independent Set. In our contribution we derive complexity and algorithmic results depending on the properties of the given graph. We show that the problem is strongly NP-hard for bipartite graphs and their line graphs, and solvable in pseudo-polynomial time for the classes of chordal graphs, cocomparability graphs, biconvex bipartite graphs, and graphs of bounded treewidth. Each of the pseudo-polynomial algorithms can also be turned into a fully polynomial approximation scheme (FPTAS).
Inter-Slice Mobility Management in 5G: Motivations, Standard Principles, Challenges and Research Directions
Venue: arXiv cs.NI 2022
Year: 2022

Mobility management in a sliced 5G network introduces new and complex challenges. In a network-sliced environment, user mobility has to be managed among not only different base stations or access technologies but also different slices. Managing user mobility among slices, or inter-slice mobility, motivates the need for new solutions. This article, presented as a tutorial, focuses on the problem of inter-slice mobility from the perspective of 3GPP standards for 5G. It provides a detailed overview of the relevant 3GPP standard principles. Accordingly, key technical gaps, challenges, and corresponding research directions are identified towards achieving seamless inter-slice mobility within the current 3GPP network slicing framework.
Epistemic Phase Transitions in Mathematical Proofs
Venue: arXiv cs.SC 2022
Year: 2022

Mathematical proofs are both paradigms of certainty and some of the most explicitly-justified arguments that we have in the cultural record. Their very explicitness, however, leads to a paradox, because the probability of error grows exponentially as the argument expands. When a mathematician encounters a proof, how does she come to believe it? Here we show that, under a cognitively-plausible belief formation mechanism combining deductive and abductive reasoning, belief in mathematical arguments can undergo what we call an epistemic phase transition: a dramatic and rapidly-propagating jump from uncertainty to near-complete confidence at reasonable levels of claim-to-claim error rates. To show this, we analyze an unusual dataset of forty-eight machine-aided proofs from the formalized reasoning system Coq, including major theorems ranging from ancient to 21st Century mathematics, along with five hand-constructed cases including Euclid, Apollonius, Hernstein's Topics in Algebra, and Andrew Wiles's proof of Fermat's Last Theorem. Our results bear both on recent work in the history and philosophy of mathematics on how we understand proofs, and on a question, basic to cognitive science, of how we justify complex beliefs.
Indexing Highly Repetitive String Collections
Venue: arXiv cs.DS 2022
Year: 2022

Two decades ago, a breakthrough in indexing string collections made it possible to represent them within their compressed space while at the same time offering indexed search functionalities. As this new technology permeated through applications like bioinformatics, the string collections experienced a growth that outperforms Moore's Law and challenges our ability of handling them even in compressed form. It turns out, fortunately, that many of these rapidly growing string collections are highly repetitive, so that their information content is orders of magnitude lower than their plain size. The statistical compression methods used for classical collections, however, are blind to this repetitiveness, and therefore a new set of techniques has been developed in order to properly exploit it. The resulting indexes form a new generation of data structures able to handle the huge repetitive string collections that we are facing. In this survey we cover the algorithmic developments that have led to these data structures. We describe the distinct compression paradigms that have been used to exploit repetitiveness, the fundamental algorithmic ideas that form the base of all the existing indexes, and the various structures that have been proposed, comparing them both in theoretical and practical aspects. We conclude with the current challenges in this fascinating field.
Redesign of web-based exam for knowledge evaluation in Advanced Mathematics for pharmaceutical students based on analysis of the results
Venue: arXiv cs.CY 2022
Year: 2022

The usage of the information technologies everywhere leads to demands for new manners of education. Modern e-learning environments lead the teaching, the learning and the evaluation of acquired knowledge and skills of the students to a new era. The students' motivation for e-learning is considered. The course of Advanced Mathematics is part of the curriculum of pharmaceutical students at the Medical University - Plovdiv. For students' knowledge evaluation it is used a hybrid-type exam in this university discipline, i.e. a problems-solving part and a remote web-based test which is created using the free and open-source e-educational platform Moodle. This paper presents a detailed analysis of the implemented electronic test for knowledge evaluation of the students, using statistical methods and instruments. The questions included in the test and the respective answers given by the students are estimated and analysed. Thus, it is made an improvement of the database of the test questions. The received results are used to enhance the quality of the developed knowledge evaluation and the type of its implementation.
Scenario-Transferable Semantic Graph Reasoning for Interaction-Aware Probabilistic Prediction
Venue: arXiv cs.RO 2022
Year: 2022

Accurately predicting the possible behaviors of traffic participants is an essential capability for autonomous vehicles. Since autonomous vehicles need to navigate in dynamically changing environments, they are expected to make accurate predictions regardless of where they are and what driving circumstances they encountered. Several methodologies have been proposed to solve prediction problems under different traffic situations. These works usually combine agent trajectories with either color-coded or vectorized high definition (HD) map as input representations and encode this information for behavior prediction tasks. However, not all the information is relevant in the scene for the forecasting and such irrelevant information may be even distracting to the forecasting in certain situations. Therefore, in this paper, we propose a novel generic representation for various driving environments by taking the advantage of semantics and domain knowledge. Using semantics enables situations to be modeled in a uniform way and applying domain knowledge filters out unrelated elements to target vehicle's future behaviors. We then propose a general semantic behavior prediction framework to effectively utilize these representations by formulating them into spatial-temporal semantic graphs and reasoning internal relations among these graphs. We theoretically and empirically validate the proposed framework under highly interactive and complex scenarios, demonstrating that our method not only achieves state-of-the-art performance, but also processes desirable zero-shot transferability.
The Economics of Social Data
Venue: arXiv cs.GT 2022
Year: 2022

A data intermediary acquires signals from individual consumers regarding their preferences. The intermediary resells the information in a product market wherein firms and consumers tailor their choices to the demand data. The social dimension of the individual data -- whereby a consumer's data are predictive of others' behavior -- generates a data externality that can reduce the intermediary's cost of acquiring the information. The intermediary optimally preserves the privacy of consumers' identities if and only if doing so increases social surplus. This policy enables the intermediary to capture the total value of the information as the number of consumers becomes large.
Probabilistic Spatial Transformer Networks
Venue: arXiv cs.LG 2022
Year: 2022

Spatial Transformer Networks (STNs) estimate image transformations that can improve downstream tasks by `zooming in' on relevant regions in an image. However, STNs are hard to train and sensitive to mis-predictions of transformations. To circumvent these limitations, we propose a probabilistic extension that estimates a stochastic transformation rather than a deterministic one. Marginalizing transformations allows us to consider each image at multiple poses, which makes the localization task easier and the training more robust. As an additional benefit, the stochastic transformations act as a localized, learned data augmentation that improves the downstream tasks. We show across standard imaging benchmarks and on a challenging real-world dataset that these two properties lead to improved classification performance, robustness and model calibration. We further demonstrate that the approach generalizes to non-visual domains by improving model performance on time-series data.
On the Effect of Dropping Layers of Pre-trained Transformer Models
Venue: arXiv cs.CL 2022
Year: 2022

Transformer-based NLP models are trained using hundreds of millions or even billions of parameters, limiting their applicability in computationally constrained environments. While the number of parameters generally correlates with performance, it is not clear whether the entire network is required for a downstream task. Motivated by the recent work on pruning and distilling pre-trained models, we explore strategies to drop layers in pre-trained models, and observe the effect of pruning on downstream GLUE tasks. We were able to prune BERT, RoBERTa and XLNet models up to 40%, while maintaining up to 98% of their original performance. Additionally we show that our pruned models are on par with those built using knowledge distillation, both in terms of size and performance. Our experiments yield interesting observations such as, (i) the lower layers are most critical to maintain downstream task performance, (ii) some tasks such as paraphrase detection and sentence similarity are more robust to the dropping of layers, and (iii) models trained using a different objective function exhibit different learning patterns and w.r.t the layer dropping.
LIAAD: Lightweight Attentive Angular Distillation for Large-scale Age-Invariant Face Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Disentangled representations have been commonly adopted to Age-invariant Face Recognition (AiFR) tasks. However, these methods have reached some limitations with (1) the requirement of large-scale face recognition (FR) training data with age labels, which is limited in practice; (2) heavy deep network architectures for high performance; and (3) their evaluations are usually taken place on age-related face databases while neglecting the standard large-scale FR databases to guarantee robustness. This work presents a novel Lightweight Attentive Angular Distillation (LIAAD) approach to Large-scale Lightweight AiFR that overcomes these limitations. Given two high-performance heavy networks as teachers with different specialized knowledge, LIAAD introduces a learning paradigm to efficiently distill the age-invariant attentive and angular knowledge from those teachers to a lightweight student network making it more powerful with higher FR accuracy and robust against age factor. Consequently, LIAAD approach is able to take the advantages of both FR datasets with and without age labels to train an AiFR model. Far apart from prior distillation methods mainly focusing on accuracy and compression ratios in closed-set problems, our LIAAD aims to solve the open-set problem, i.e. large-scale face recognition. Evaluations on LFW, IJB-B and IJB-C Janus, AgeDB and MegaFace-FGNet with one million distractors have demonstrated the efficiency of the proposed approach on light-weight structure. This work also presents a new longitudinal face aging (LogiFace) database \footnote{This database will be made available} for further studies in age-related facial problems in future.
Robust Large-Margin Learning in Hyperbolic Space
Venue: arXiv cs.LG 2022
Year: 2022

Recently, there has been a surge of interest in representation learning in hyperbolic spaces, driven by their ability to represent hierarchical data with significantly fewer dimensions than standard Euclidean spaces. However, the viability and benefits of hyperbolic spaces for downstream machine learning tasks have received less attention. In this paper, we present, to our knowledge, the first theoretical guarantees for learning a classifier in hyperbolic rather than Euclidean space. Specifically, we consider the problem of learning a large-margin classifier for data possessing a hierarchical structure. We provide an algorithm to efficiently learn a large-margin hyperplane, relying on the careful injection of adversarial examples. Finally, we prove that for hierarchical data that embeds well into hyperbolic space, the low embedding dimension ensures superior guarantees when learning the classifier directly in hyperbolic space.
An Entropy Clustering Approach for Assessing Visual Question Difficulty
Venue: arXiv cs.CV 2022
Year: 2022

We propose a novel approach to identify the difficulty of visual questions for Visual Question Answering (VQA) without direct supervision or annotations to the difficulty. Prior works have considered the diversity of ground-truth answers of human annotators. In contrast, we analyze the difficulty of visual questions based on the behavior of multiple different VQA models. We propose to cluster the entropy values of the predicted answer distributions obtained by three different models: a baseline method that takes as input images and questions, and two variants that take as input images only and questions only. We use a simple k-means to cluster the visual questions of the VQA v2 validation set. Then we use state-of-the-art methods to determine the accuracy and the entropy of the answer distributions for each cluster. A benefit of the proposed method is that no annotation of the difficulty is required, because the accuracy of each cluster reflects the difficulty of visual questions that belong to it. Our approach can identify clusters of difficult visual questions that are not answered correctly by state-of-the-art methods. Detailed analysis on the VQA v2 dataset reveals that 1) all methods show poor performances on the most difficult cluster (about 10\% accuracy), 2) as the cluster difficulty increases, the answers predicted by the different methods begin to differ, and 3) the values of cluster entropy are highly correlated with the cluster accuracy. We show that our approach has the advantage of being able to assess the difficulty of visual questions without ground-truth (\ie, the test set of VQA v2) by assigning them to one of the clusters. We expect that this can stimulate the development of novel directions of research and new algorithms.
A stochastic reduced-order model for statistical microstructure descriptors evolution
Venue: arXiv cs.CE 2022
Year: 2022

Integrated Computational Materials Engineering (ICME) models have been a crucial building block for modern materials development, relieving heavy reliance on experiments and significantly accelerating the materials design process. However, ICME models are also computationally expensive, particularly with respect to time integration for dynamics, which hinders the ability to study statistical ensembles and thermodynamic properties of large systems for long time scales. To alleviate the computational bottleneck, we propose to model the evolution of statistical microstructure descriptors as a continuous-time stochastic process using a non-linear Langevin equation, where the probability density function (PDF) of the statistical microstructure descriptors, which are also the quantities of interests (QoIs), are modeled by the Fokker-Planck equation. We discuss how to calibrate the drift and diffusion terms of the Fokker-Planck equation from the theoretical and computational perspectives. The calibrated Fokker-Planck equation can be used as a stochastic reduced-order model (ROM) to simulate the microstructure evolution of statistical microstructure descriptors PDF. Considering statistical microstructure descriptors in the microstructure evolution as QoIs, we demonstrate our proposed methodology in three integrated computational materials engineering (ICME) models: kinetic Monte Carlo, phase field, and molecular dynamics simulations.
Efficient, Near Complete and Often Sound Hybrid Dynamic Data Race Prediction (extended version)
Venue: arXiv cs.PL 2022
Year: 2022

Dynamic data race prediction aims to identify races based on a single program run represented by a trace. The challenge is to remain efficient while being as sound and as complete as possible. Efficient means a linear run-time as otherwise the method unlikely scales for real-world programs. We introduce an efficient, near complete and often sound dynamic data race prediction method that combines the lockset method with several improvements made in the area of happens-before methods. By near complete we mean that the method is complete in theory but for efficiency reasons the implementation applies some optimizations that may result in incompleteness. The method can be shown to be sound for two threads but is unsound in general. We provide extensive experimental data that shows that our method works well in practice.
SenseCare: A Research Platform for Medical Image Informatics and Interactive 3D Visualization
Venue: arXiv cs.HC 2022
Year: 2022

Clinical research on smart health has an increasing demand for intelligent and clinic-oriented medical image computing algorithms and platforms that support various applications. To this end, we have developed SenseCare research platform, which is designed to facilitate translational research on intelligent diagnosis and treatment planning in various clinical scenarios. To enable clinical research with Artificial Intelligence (AI), SenseCare provides a range of AI toolkits for different tasks, including image segmentation, registration, lesion and landmark detection from various image modalities ranging from radiology to pathology. In addition, SenseCare is clinic-oriented and supports a wide range of clinical applications such as diagnosis and surgical planning for lung cancer, pelvic tumor, coronary artery disease, etc. SenseCare provides several appealing functions and features such as advanced 3D visualization, concurrent and efficient web-based access, fast data synchronization and high data security, multi-center deployment, support for collaborative research, etc. In this report, we present an overview of SenseCare as an efficient platform providing comprehensive toolkits and high extensibility for intelligent image analysis and clinical research in different application scenarios. We also summarize the research outcome through the collaboration with multiple hospitals.
Hcore-Init: Neural Network Initialization based on Graph Degeneracy
Venue: arXiv cs.LG 2022
Year: 2022

Neural networks are the pinnacle of Artificial Intelligence, as in recent years we witnessed many novel architectures, learning and optimization techniques for deep learning. Capitalizing on the fact that neural networks inherently constitute multipartite graphs among neuron layers, we aim to analyze directly their structure to extract meaningful information that can improve the learning process. To our knowledge graph mining techniques for enhancing learning in neural networks have not been thoroughly investigated. In this paper we propose an adapted version of the k-core structure for the complete weighted multipartite graph extracted from a deep learning architecture. As a multipartite graph is a combination of bipartite graphs, that are in turn the incidence graphs of hypergraphs, we design k-hypercore decomposition, the hypergraph analogue of k-core degeneracy. We applied k-hypercore to several neural network architectures, more specifically to convolutional neural networks and multilayer perceptrons for image recognition tasks after a very short pretraining. Then we used the information provided by the hypercore numbers of the neurons to re-initialize the weights of the neural network, thus biasing the gradient optimization scheme. Extensive experiments proved that k-hypercore outperforms the state-of-the-art initialization methods.
Fully Dynamic s-t Edge Connectivity in Subpolynomial Time
Venue: arXiv cs.DS 2022
Year: 2022

We present a deterministic fully dynamic algorithm to answer $c$-edge connectivity queries on pairs of vertices in $n^{o(1)}$ worst case update and query time for any positive integer $c = (\log n)^{o(1)}$ for a graph with $n$ vertices. Previously, only polylogarithmic and $O(\sqrt{n})$ worst case update time fully dynamic algorithms were known for answering $1$, $2$ and $3$-edge connectivity queries respectively [Henzinger and King 1995, Frederikson 1997, Galil and Italiano 1991]. Our result extends the $c$-edge connectivity vertex sparsifier [Chalermsook et al. 2021] to a multi-level sparsification framework. As our main technical contribution, we present a novel update algorithm for the multi-level $c$-edge connectivity vertex sparsifier with subpolynomial update time.