OpenRaiser/Intern-Atlas huggingface dataset:
Deep Learning Based Single Sample Per Person Face Recognition: A Survey
Venue: arXiv cs.CV 2022
Year: 2022

Face recognition has long been an active research area in the field of artificial intelligence, particularly since the rise of deep learning in recent years. In some practical situations, each identity has only a single sample available for training. Face recognition under this situation is referred to as single sample face recognition and poses significant challenges to the effective training of deep models. Therefore, in recent years, researchers have attempted to unleash more potential of deep learning and improve the model recognition performance in the single sample situation. While several comprehensive surveys have been conducted on traditional single sample face recognition approaches, emerging deep learning based methods are rarely involved in these reviews. Accordingly, we focus on the deep learning-based methods in this paper, classifying them into virtual sample methods and generic learning methods. In the former category, virtual images or virtual features are generated to benefit the training of the deep model. In the latter one, additional multi-sample generic sets are used. There are three types of generic learning methods: combining traditional methods and deep features, improving the loss function, and improving network structure, all of which are covered in our analysis. Moreover, we review face datasets that have been commonly used for evaluating single sample face recognition models and go on to compare the results of different types of models. Additionally, we discuss problems with existing single sample face recognition methods, including identity information preservation in virtual sample methods, domain adaption in generic learning methods. Furthermore, we regard developing unsupervised methods is a promising future direction, and point out that the semantic gap as an important issue that needs to be further considered.
P3GM: Private High-Dimensional Data Release via Privacy Preserving Phased Generative Model
Venue: arXiv cs.LG 2022
Year: 2022

How can we release a massive volume of sensitive data while mitigating privacy risks? Privacy-preserving data synthesis enables the data holder to outsource analytical tasks to an untrusted third party. The state-of-the-art approach for this problem is to build a generative model under differential privacy, which offers a rigorous privacy guarantee. However, the existing method cannot adequately handle high dimensional data. In particular, when the input dataset contains a large number of features, the existing techniques require injecting a prohibitive amount of noise to satisfy differential privacy, which results in the outsourced data analysis meaningless. To address the above issue, this paper proposes privacy-preserving phased generative model (P3GM), which is a differentially private generative model for releasing such sensitive data. P3GM employs the two-phase learning process to make it robust against the noise, and to increase learning efficiency (e.g., easy to converge). We give theoretical analyses about the learning complexity and privacy loss in P3GM. We further experimentally evaluate our proposed method and demonstrate that P3GM significantly outperforms existing solutions. Compared with the state-of-the-art methods, our generated samples look fewer noises and closer to the original data in terms of data diversity. Besides, in several data mining tasks with synthesized data, our model outperforms the competitors in terms of accuracy.
On Session Continuation among Slices for Inter-Slice Mobility Support in 3GPP Service-based Architecture
Venue: arXiv cs.NI 2022
Year: 2022

The 3GPP has provided its first standard specifications for network slicing in the recent Release 15. The fundamental principles are specified which constitute the standard network slicing framework. These specifications, however, lack the session continuation mechanisms among slices, which is a fundamental requirement to achieve inter-slice mobility. In this paper, we propose three solutions which enable session continuation among slices in the current 3GPP network slicing framework. These solutions are based on existing, well-established standard mechanisms. The first solution is based on the Return Routability/Binding Update (RR/BU) procedure of the popular Internet standard, Mobile IPv6 (MIPv6). The second solution is based on the 3GPP standard GPRS Tunnelling Protocol User Plane (GTPv1-U), which establishes a GTP tunnel between previous and new slice for session continuation. The third solution is a hybrid solution of both MIPv6-RR/BU and GTPv1-U protocols. We compare the performance of all these solutions through analytical modelling. Results show that the GTPv1-U based and the hybrid MIPv6/GTPv1-U solutions promise lower service disruption latency, however, incur higher resource utilization overhead compared to MIPv6-RR/BU and 3GPP standard PDU Session Establishment process.
Detectability of labeled weighted automata over monoids
Venue: arXiv cs.FL 2022
Year: 2022

In this paper, we for the first time obtain characterization of four fundamental notions of detectability for general labeled weighted automata over monoids (denoted by $\mathcal{A}^{\mathfrak{M}}$ for short), where the four notions are strong (periodic) detectability (SD and SPD) and weak (periodic) detectability (WD and WPD). Firstly, we formulate the notions of concurrent composition, observer, and detector for $\mathcal{A}^{\mathfrak{M}}$. Secondly, we use the concurrent composition to give an equivalent condition for SD, use the detector to give an equivalent condition for SPD, and use the observer to give equivalent conditions for WD and WPD, all for general $\mathcal{A}^{\mathfrak{M}}$ without any assumption. Thirdly, we prove that for a labeled weighted automaton over monoid $(\mathbb{Q}^k,+)$ (denoted by $\mathcal{A}^{\mathbb{Q}^k}$), its concurrent composition, observer, and detector can be computed in NP, $2$-EXPTIME, and $2$-EXPTIME, respectively, by developing novel connections between $\mathcal{A}^{\mathbb{Q}^k}$ and the NP-complete exact path length problem (proved by [Nykänen and Ukkonen, 2002]) and a subclass of Presburger arithmetic. As a result, we prove that for $\mathcal{A}^{\mathbb{Q}^k}$, SD can be verified in coNP, while SPD, WD, and WPD can be verified in $2$-EXPTIME. Finally, we prove that the problems of verifying SD and SPD of deterministic, deadlock-free, and divergence-free $\mathcal{A}^{\mathbb{N}}$ over monoid $(\mathbb{N},+)$ are both coNP-hard. The developed original methods will provide foundations for characterizing other fundamental properties (e.g., diagnosability, opacity) for $\mathcal{A}^{\mathfrak{M}}$. We also initially explore detectability in labeled timed automata, and prove that the SD verification problem is PSPACE-complete, while WD and WPD are undecidable.
Set Based Stochastic Subsampling
Venue: arXiv cs.LG 2022
Year: 2022

Deep models are designed to operate on huge volumes of high dimensional data such as images. In order to reduce the volume of data these models must process, we propose a set-based two-stage end-to-end neural subsampling model that is jointly optimized with an \textit{arbitrary} downstream task network (e.g. classifier). In the first stage, we efficiently subsample \textit{candidate elements} using conditionally independent Bernoulli random variables by capturing coarse grained global information using set encoding functions, followed by conditionally dependent autoregressive subsampling of the candidate elements using Categorical random variables by modeling pair-wise interactions using set attention networks in the second stage. We apply our method to feature and instance selection and show that it outperforms the relevant baselines under low subsampling rates on a variety of tasks including image classification, image reconstruction, function reconstruction and few-shot classification. Additionally, for nonparametric models such as Neural Processes that require to leverage the whole training data at inference time, we show that our method enhances the scalability of these models.
Density of Binary Disc Packings: Playing with Stoichiometry
Venue: arXiv cs.DM 2022
Year: 2022

We consider hard-disc mixtures with disc sizes within ratio $\sqrt{2}-1$, that is, the small disc exactly fits in the hole between four large discs. For each prescribed stoichiometry of large and small discs, the densest packings are rigorously determined via a computer-assisted proof. The density is maximal for the 1:1 stoichiometry: the large discs then form a square grid in each interstitial site of which a small disc nests. When there is an excess of large discs, the densest packings are made of a single phase which mixes the two types of discs in a chaotic way (it can be described by square-triangle tilings). When there is an excess of small discs, on the contrary, a phenomenon of phase separation appears: the large discs are involved in the densest 1:1 stoichiometry phases while the excess of small discs form compact hexagonal phases.
Replication-Robust Payoff-Allocation for Machine Learning Data Markets
Venue: arXiv cs.LG 2022
Year: 2022

Submodular functions have been a powerful mathematical model for a wide range of real-world applications. Recently, submodular functions are becoming increasingly important in machine learning (ML) for modelling notions such as information and redundancy among entities such as data and features. Among these applications, a key question is payoff allocation, i.e., how to evaluate the importance of each entity towards the collective objective? To this end, classic solution concepts from cooperative game theory offer principled approaches to payoff allocation. However, despite the extensive body of game-theoretic literature, payoff allocation in submodular games are relatively under-researched. In particular, an important notion that arises in the emerging submodular applications is redundancy, which may occur from various sources such as abundant data or malicious manipulations where a player replicates its resource and act under multiple identities. Though many game-theoretic solution concepts can be directly used in submodular games, naively applying them for payoff allocation in these settings may incur robustness issues against replication. In this paper, we systematically study the replication manipulation in submodular games and investigate replication robustness, a metric that quantitatively measures the robustness of solution concepts against replication. Using this metric, we present conditions which theoretically characterise the robustness of semivalues, a wide family of solution concepts including the Shapley and Banzhaf value. Moreover, we empirically validate our theoretical results on an emerging submodular ML application, i.e., the ML data market.
Multi-Partition Embedding Interaction with Block Term Format for Knowledge Graph Completion
Venue: arXiv cs.LG 2022
Year: 2022

Knowledge graph completion is an important task that aims to predict the missing relational link between entities. Knowledge graph embedding methods perform this task by representing entities and relations as embedding vectors and modeling their interactions to compute the matching score of each triple. Previous work has usually treated each embedding as a whole and has modeled the interactions between these whole embeddings, potentially making the model excessively expensive or requiring specially designed interaction mechanisms. In this work, we propose the multi-partition embedding interaction (MEI) model with block term format to systematically address this problem. MEI divides each embedding into a multi-partition vector to efficiently restrict the interactions. Each local interaction is modeled with the Tucker tensor format and the full interaction is modeled with the block term tensor format, enabling MEI to control the trade-off between expressiveness and computational cost, learn the interaction mechanisms from data automatically, and achieve state-of-the-art performance on the link prediction task. In addition, we theoretically study the parameter efficiency problem and derive a simple empirically verified criterion for optimal parameter trade-off. We also apply the framework of MEI to provide a new generalized explanation for several specially designed interaction mechanisms in previous models. The source code is released at https://github.com/tranhungnghiep/MEI-KGE.
Characteristic Logics for Behavioural Hemimetrics via Fuzzy Lax Extensions
Venue: arXiv cs.LO 2022
Year: 2022

In systems involving quantitative data, such as probabilistic, fuzzy, or metric systems, behavioural distances provide a more fine-grained comparison of states than two-valued notions of behavioural equivalence or behaviour inclusion. Like in the two-valued case, the wide variation found in system types creates a need for generic methods that apply to many system types at once. Approaches of this kind are emerging within the paradigm of universal coalgebra, based either on lifting pseudometrics along set functors or on lifting general real-valued (fuzzy) relations along functors by means of fuzzy lax extensions. An immediate benefit of the latter is that they allow bounding behavioural distance by means of fuzzy (bi-)simulations that need not themselves be hemi- or pseudometrics; this is analogous to classical simulations and bisimulations, which need not be preorders or equivalence relations, respectively. The known generic pseudometric liftings, specifically the generic Kantorovich and Wasserstein liftings, both can be extended to yield fuzzy lax extensions, using the fact that both are effectively given by a choice of quantitative modalities. Our central result then shows that in fact all fuzzy lax extensions are Kantorovich extensions for a suitable set of quantitative modalities, the so-called Moss modalities. For nonexpansive fuzzy lax extensions, this allows for the extraction of quantitative modal logics that characterize behavioural distance, i.e. satisfy a quantitative version of the Hennessy-Milner theorem; equivalently, we obtain expressiveness of a quantitative version of Moss' coalgebraic logic. All our results explicitly hold also for asymmetric distances (hemimetrics), i.e. notions of quantitative simulation.
Minimizing Convex Functions with Rational Minimizers
Venue: arXiv cs.DS 2022
Year: 2022

Given a separation oracle $\mathsf{SO}$ for a convex function $f$ defined on $\mathbb{R}^n$ that has an integral minimizer inside a box with radius $R$, we show how to find an exact minimizer of $f$ using at most (a) $O(n (n \log \log (n)/\log (n) + \log(R)))$ calls to $\mathsf{SO}$ and $\mathsf{poly}(n, \log(R))$ arithmetic operations, or (b) $O(n \log(nR))$ calls to $\mathsf{SO}$ and $\exp(O(n)) \cdot \mathsf{poly}(\log(R))$ arithmetic operations. When the set of minimizers of $f$ has integral extreme points, our algorithm outputs an integral minimizer of $f$. This improves upon the previously best oracle complexity of $O(n^2 (n + \log(R)))$ for polynomial time algorithms and $O(n^2\log(nR))$ for exponential time algorithms obtained by [Grötschel, Lovász and Schrijver, Prog. Comb. Opt. 1984, Springer 1988] over thirty years ago. Our improvement on Grötschel, Lovász and Schrijver's result generalizes to the setting where the set of minimizers of $f$ is a rational polyhedron with bounded vertex complexity. For the Submodular Function Minimization problem, our result immediately implies a strongly polynomial algorithm that makes at most $O(n^3 \log \log (n)/\log (n))$ calls to an evaluation oracle, and an exponential time algorithm that makes at most $O(n^2 \log(n))$ calls to an evaluation oracle. These improve upon the previously best $O(n^3 \log^2(n))$ oracle complexity for strongly polynomial algorithms given in [Lee, Sidford and Wong, FOCS 2015] and [Dadush, Végh and Zambelli, SODA 2018], and an exponential time algorithm with oracle complexity $O(n^3 \log(n))$ given in the former work. Our result is achieved via a reduction to the Shortest Vector Problem in lattices. We analyze its oracle complexity using a potential function that simultaneously captures the size of the search set and the density of the lattice.
Social distancing with the Optimal Steps Model
Venue: arXiv cs.MA 2022
Year: 2022

With the Covid-19 pandemic an urgent need to simulate social distancing arises. The Optimal Steps Model (OSM) is a pedestrian locomotion model that operationalizes an individual's need for personal space. We present new parameter values for personal space in the Optimal Steps Model to simulate social distancing in the pedestrian dynamics simulator Vadere. Our approach is pragmatic. We consider two use cases: in the first we demand that a set social distance must never be violated. In the second the social distance must be kept only on average. For each use case we conduct simulation studies in a typical bottleneck scenario and measure contact times, that is, violations of the social distance rule. We derive rules of thumb for suitable parameter choices in dependency of the desired social distance. We test the rules of thumb for the social distances 1.5m and 2.0m and observe that the new parameter values indeed lead to the desired social distancing. Thus, the rules of thumb will quickly enable Vadere users to conduct their own studies without understanding the intricacies of the OSM implementation and without extensive parameter adjustment.
Learning Utilities and Equilibria in Non-Truthful Auctions
Venue: arXiv cs.GT 2022
Year: 2022

In non-truthful auctions, agents' utility for a strategy depends on the strategies of the opponents and also the prior distribution over their private types; the set of Bayes Nash equilibria generally has an intricate dependence on the prior. Using the First Price Auction as our main demonstrating example, we show that $\tilde O(n / ε^2)$ samples from the prior with $n$ agents suffice for an algorithm to learn the interim utilities for all monotone bidding strategies. As a consequence, this number of samples suffice for learning all approximate equilibria. We give almost matching (up to polylog factors) lower bound on the sample complexity for learning utilities. We also consider a setting where agents must pay a search cost to discover their own types. Drawing on a connection between this setting and the first price auction, discovered recently by Kleinberg et al. (2016), we show that $\tilde O(n / ε^2)$ samples suffice for utilities and equilibria to be estimated in a near welfare-optimal descending auction in this setting. En route, we improve the sample complexity bound, recently obtained by Guo et al. (2021), for the Pandora's Box problem, which is a classical model for sequential consumer search.
Meta-Learning through Hebbian Plasticity in Random Networks
Venue: arXiv cs.NE 2022
Year: 2022

Lifelong learning and adaptability are two defining aspects of biological agents. Modern reinforcement learning (RL) approaches have shown significant progress in solving complex tasks, however once training is concluded, the found solutions are typically static and incapable of adapting to new information or perturbations. While it is still not completely understood how biological brains learn and adapt so efficiently from experience, it is believed that synaptic plasticity plays a prominent role in this process. Inspired by this biological mechanism, we propose a search method that, instead of optimizing the weight parameters of neural networks directly, only searches for synapse-specific Hebbian learning rules that allow the network to continuously self-organize its weights during the lifetime of the agent. We demonstrate our approach on several reinforcement learning tasks with different sensory modalities and more than 450K trainable plasticity parameters. We find that starting from completely random weights, the discovered Hebbian rules enable an agent to navigate a dynamical 2D-pixel environment; likewise they allow a simulated 3D quadrupedal robot to learn how to walk while adapting to morphological damage not seen during training and in the absence of any explicit reward or error signal in less than 100 timesteps. Code is available at https://github.com/enajx/HebbianMetaLearning.
Detection as Regression: Certified Object Detection by Median Smoothing
Venue: arXiv cs.CV 2022
Year: 2022

Despite the vulnerability of object detectors to adversarial attacks, very few defenses are known to date. While adversarial training can improve the empirical robustness of image classifiers, a direct extension to object detection is very expensive. This work is motivated by recent progress on certified classification by randomized smoothing. We start by presenting a reduction from object detection to a regression problem. Then, to enable certified regression, where standard mean smoothing fails, we propose median smoothing, which is of independent interest. We obtain the first model-agnostic, training-free, and certified defense for object detection against $\ell_2$-bounded attacks. The code for all experiments in the paper is available at http://github.com/Ping-C/CertifiedObjectDetection .
The Mean-Squared Error of Double Q-Learning
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we establish a theoretical comparison between the asymptotic mean-squared error of Double Q-learning and Q-learning. Our result builds upon an analysis for linear stochastic approximation based on Lyapunov equations and applies to both tabular setting and with linear function approximation, provided that the optimal policy is unique and the algorithms converge. We show that the asymptotic mean-squared error of Double Q-learning is exactly equal to that of Q-learning if Double Q-learning uses twice the learning rate of Q-learning and outputs the average of its two estimators. We also present some practical implications of this theoretical observation using simulations.
MTP: Multi-Task Pruning for Efficient Semantic Segmentation Networks
Venue: arXiv cs.CV 2022
Year: 2022

This paper focuses on channel pruning for semantic segmentation networks. Previous methods to compress and accelerate deep neural networks in the classification task cannot be straightforwardly applied to the semantic segmentation network that involves an implicit multi-task learning problem via pre-training. To identify the redundancy in segmentation networks, we present a multi-task channel pruning approach. The importance of each convolution filter \wrt the channel of an arbitrary layer will be simultaneously determined by the classification and segmentation tasks. In addition, we develop an alternative scheme for optimizing importance scores of filters in the entire network. Experimental results on several benchmarks illustrate the superiority of the proposed algorithm over the state-of-the-art pruning methods. Notably, we can obtain an about $2\times$ FLOPs reduction on DeepLabv3 with only an about $1\%$ mIoU drop on the PASCAL VOC 2012 dataset and an about $1.3\%$ mIoU drop on Cityscapes dataset, respectively.