OpenRaiser/Intern-Atlas huggingface dataset:
Influence of segmentation on deep iris recognition performance
Venue: arXiv cs.CV 2020
Year: 2020

Despite the rise of deep learning in numerous areas of computer vision and image processing, iris recognition has not benefited considerably from these trends so far. Most of the existing research on deep iris recognition is focused on new models for generating discriminative and robust iris representations and relies on methodologies akin to traditional iris recognition pipelines. Hence, the proposed models do not approach iris recognition in an end-to-end manner, but rather use standard heuristic iris segmentation (and unwrapping) techniques to produce normalized inputs for the deep learning models. However, because deep learning is able to model very complex data distributions and nonlinear data changes, an obvious question arises. How important is the use of traditional segmentation methods in a deep learning setting? To answer this question, we present in this paper an empirical analysis of the impact of iris segmentation on the performance of deep learning models using a simple two stage pipeline consisting of a segmentation and a recognition step. We evaluate how the accuracy of segmentation influences recognition performance but also examine if segmentation is needed at all. We use the CASIA Thousand and SBVPI datasets for the experiments and report several interesting findings.
Support Recovery in the Phase Retrieval Model: Information-Theoretic Fundamental Limits
Venue: arXiv cs.IT 2020
Year: 2020

The support recovery problem consists of determining a sparse subset of variables that is relevant in generating a set of observations. In this paper, we study the support recovery problem in the phase retrieval model consisting of noisy phaseless measurements, which arises in a diverse range of settings such as optical detection, X-ray crystallography, electron microscopy, and coherent diffractive imaging. Our focus is on information-theoretic fundamental limits under an approximate recovery criterion, considering both discrete and Gaussian models for the sparse non-zero entries, along with Gaussian measurement matrices. In both cases, our bounds provide sharp thresholds with near-matching constant factors in several scaling regimes on the sparsity and signal-to-noise ratio. As a key step towards obtaining these results, we develop new concentration bounds for the conditional information content of log-concave random variables, which may be of independent interest.
initKmix -- A Novel Initial Partition Generation Algorithm for Clustering Mixed Data using k-means-based Clustering
Venue: arXiv cs.LG 2020
Year: 2020

Mixed datasets consist of both numeric and categorical attributes. Various k-means-based clustering algorithms have been developed for these datasets. Generally, these algorithms use random partition as a starting point, which tends to produce different clustering results for different runs. In this paper, we propose, initKmix, a novel algorithm for finding an initial partition for k-means-based clustering algorithms for mixed datasets. In the initKmix algorithm, a k-means-based clustering algorithm is run many times, and in each run, one of the attributes is used to create initial clusters for that run. The clustering results of various runs are combined to produce the initial partition. This initial partition is then used as a seed to a k-means-based clustering algorithm to cluster mixed data. Experiments with various categorical and mixed datasets showed that initKmix produced accurate and consistent results, and outperformed the random initial partition method and other state-of-the-art initialization methods. Experiments also showed that k-means-based clustering for mixed datasets with initKmix performed similar to or better than many state-of-the-art clustering algorithms for categorical and mixed datasets.
Cache-aided Interference Management Using Hypercube Combinatorial Cache Designs
Venue: arXiv cs.IT 2020
Year: 2020

We consider a cache-aided interference network which consists of a library of $N$ files, $K_T$ transmitters and $K_R$ receivers (users), each equipped with a local cache of size $M_T$ and $M_R$ files respectively, and connected via a discrete-time additive white Gaussian noise channel. Each receiver requests an arbitrary file from the library. The objective is to design a cache placement without knowing the receivers' requests and a communication scheme such that the sum Degrees of Freedom (sum-DoF) of the delivery is maximized. This network model has been investigated by Naderializadeh {\em et al.}, who proposed a prefetching and a delivery schemes that achieves a sum-DoF of $\min\{\frac{M_TK_T+K_RM_R}{N}, K_R\}$. One of biggest limitations of this scheme is the requirement of high subpacketization level. This paper is the first attempt in the literature (according to our knowledge) to reduce the file subpacketization in such a network. In particular, we propose a new approach for both prefetching and linear delivery schemes based on a combinatorial design called {\em hypercube}. We show that required number of packets per file can be exponentially reduced compared to the state of the art scheme proposed by Naderializadeh {\em et al.}, or the NMA scheme. When $M_TK_T+K_RM_R \geq K_R$, the achievable one-shot sum-DoF using this approach is $\frac{M_TK_T+K_RM_R}{N}$ , which shows that 1) the one-shot sum-DoF scales linearly with the aggregate cache size in the network and 2) it is within a factor of $2$ to the information-theoretic optimum. Surprisingly, the identical and near optimal sum-DoF performance can be achieved using the hypercube approach with a much less file subpacketization.
Signatures and Induction Principles for Higher Inductive-Inductive Types
Venue: arXiv cs.LO 2020
Year: 2020

Higher inductive-inductive types (HIITs) generalize inductive types of dependent type theories in two ways. On the one hand they allow the simultaneous definition of multiple sorts that can be indexed over each other. On the other hand they support equality constructors, thus generalizing higher inductive types of homotopy type theory. Examples that make use of both features are the Cauchy real numbers and the well-typed syntax of type theory where conversion rules are given as equality constructors. In this paper we propose a general definition of HIITs using a small type theory, named the theory of signatures. A context in this theory encodes a HIIT by listing the constructors. We also compute notions of induction and recursion for HIITs, by using variants of syntactic logical relation translations. Building full categorical semantics and constructing initial algebras is left for future work. The theory of HIIT signatures was formalised in Agda together with the syntactic translations. We also provide a Haskell implementation, which takes signatures as input and outputs translation results as valid Agda code.
A New Codebook Design for Analog Beamforming in Millimeter-wave Communication
Venue: arXiv cs.IT 2020
Year: 2020

In this study, we analyze the codebook design used for analog beamforming. Analog beamforming and combining suffer from a subspace sampling limitation, that is, the receiver cannot directly observe the channel coefficients; instead, the receiver observes a noisy version of their weighted combination. To resolve this, the transmitter and the receiver usually collaborate to determine the best beamformer combiner pair during the beam-sweeping process. This is done by evaluating a limited number of codewords chosen from a pre-defined codebook. In this study, we propose a new framework inspired by the generalized Lloyd algorithm to design analog beamforming codebooks that optimize various performance metrics including the average beamforming gain, the outage, and the average data rate. The flexibility of our framework enables us to design beamforming codebooks for any array shapes including uniform linear and planar arrays. The other practical complexity in analog beamforming is the low resolution of the phase shifters. Therefore, we have extended our algorithm to create quantized codebooks that outperform the existing codebooks in literature. We have also provided extensive simulations to verify the superiority of our proposed codebook as compared with the existing codebooks.
A Faster FPTAS for Knapsack Problem With Cardinality Constraint
Venue: arXiv cs.DS 2020
Year: 2020

We study the $K$-item knapsack problem (i.e., $1.5$-dimensional KP), which is a generalization of the famous 0-1 knapsack problem (i.e., $1$-dimensional KP) in which an upper bound $K$ is imposed on the number of items selected. This problem is of fundamental importance and is known to have a broad range of applications in various fields. It is well known that, there is no FPTAS for the $d$-dimensional knapsack problem when $d\geq 2$, unless P $=$ NP. While the $K$-item knapsack problem is known to admit an FPTAS, the complexity of all existing FPTASs have a high dependency on the cardinality bound $K$ and approximation error $\varepsilon$, which could result in inefficiencies especially when $K$ and $\varepsilon^{-1}$ increase. The current best results are due to Mastrolilli and Hutter (2006), in which two schemes are presented exhibiting a space-time tradeoff--one scheme with time complexity $O(n+Kz^{2}/\varepsilon^{2})$ and space complexity $O(n+z^{3}/\varepsilon)$, while another scheme requires $O(n+(Kz^{2}+z^{4})/\varepsilon^{2})$ run-time but only needs $O(n+z^{2}/\varepsilon)$ space, where $z=\min\{K,1/\varepsilon\}$. In this paper we close the space-time tradeoff exhibited in the state-of-the-art by designing a new FPTAS with a run-time of $\widetilde{O}(n+z^{2}/\varepsilon^{2})$, while simultaneously reaching the $O(n+z^{2}/\varepsilon)$ space bound. Our scheme provides $\widetilde{O}(K)$ and $O(z)$ improvements on the state-of-the-art algorithms in time and space complexity respectively, and is the first scheme that achieves a run-time that is independent of cardinality bound $K$ (up to logarithmic factors) under fixed $\varepsilon$. Another salient feature of our scheme is that it is the first FPTAS that achieves better time and space complexity bounds than the very first standard FPTAS over all parameter regimes.
Automating Software Citation using GitCite
Venue: arXiv cs.DB 2020
Year: 2020

The ability to cite software and give credit to its authors and contributors is increasingly important. While the number of online open-source software repositories has grown rapidly over the past few years, few are being properly cited when used due to the difficulty of creating appropriate citations and the lack of automated techniques. This paper presents GitCite, a model for software citation with version control which enables citations to be inferred for any project component based on a small number of explicit citations attached to subdirectories/files, and an implementation that integrates with Git and GitHub. The implementation includes a browser extension and a local executable tool, which enable citations to be added/modified/deleted to software project repositories and managed through functions such as fork/merge/copy.
A Sequential Importance Sampling Algorithm for Estimating Linear Extensions
Venue: arXiv cs.DS 2020
Year: 2020

In recent decades, a number of profound theorems concerning approximation of hard counting problems have appeared. These include estimation of the permanent, estimating the volume of a convex polyhedron, and counting (approximately) the number of linear extensions of a partially ordered set. All of these results have been achieved using probabilistic sampling methods, specifically Monte Carlo Markov Chain (MCMC) techniques. In each case, a rapidly mixing Markov chain is defined that is guaranteed to produce, with high probability, an accurate result after only a polynomial number of operations. Although of polynomial complexity, none of these results lead to a practical computational technique, nor do they claim to. The polynomials are of high degree and a non-trivial amount of computing is required to get even a single sample. Our aim in this paper is to present practical Monte Carlo methods for one of these problems, counting linear extensions. Like related work on estimating the coefficients of the reliability polynomial, our technique is based on improving the so-called Knuth counting algorithm by incorporating an importance function into the node selection technique giving a sequential importance sampling (SIS) method. We define and report performance on two importance functions.
Homogeneous Linear Inequality Constraints for Neural Network Activations
Venue: arXiv cs.LG 2020
Year: 2020

We propose a method to impose homogeneous linear inequality constraints of the form $Ax\leq 0$ on neural network activations. The proposed method allows a data-driven training approach to be combined with modeling prior knowledge about the task. One way to achieve this task is by means of a projection step at test time after unconstrained training. However, this is an expensive operation. By directly incorporating the constraints into the architecture, we can significantly speed-up inference at test time; for instance, our experiments show a speed-up of up to two orders of magnitude over a projection method. Our algorithm computes a suitable parameterization of the feasible set at initialization and uses standard variants of stochastic gradient descent to find solutions to the constrained network. Thus, the modeling constraints are always satisfied during training. Crucially, our approach avoids to solve an optimization problem at each training step or to manually trade-off data and constraint fidelity with additional hyperparameters. We consider constrained generative modeling as an important application domain and experimentally demonstrate the proposed method by constraining a variational autoencoder.
CLEAR: A Consistent Lifting, Embedding, and Alignment Rectification Algorithm for Multi-View Data Association
Venue: arXiv cs.RO 2020
Year: 2020

Many robotics applications require alignment and fusion of observations obtained at multiple views to form a global model of the environment. Multi-way data association methods provide a mechanism to improve alignment accuracy of pairwise associations and ensure their consistency. However, existing methods that solve this computationally challenging problem are often too slow for real-time applications. Furthermore, some of the existing techniques can violate the cycle consistency principle, thus drastically reducing the fusion accuracy. This work presents the CLEAR (Consistent Lifting, Embedding, and Alignment Rectification) algorithm to address these issues. By leveraging insights from the multi-way matching and spectral graph clustering literature, CLEAR provides cycle consistent and accurate solutions in a computationally efficient manner. Numerical experiments on both synthetic and real datasets are carried out to demonstrate the scalability and superior performance of our algorithm in real-world problems. This algorithmic framework can provide significant improvement in the accuracy and efficiency of existing discrete assignment problems, which traditionally use pairwise (but potentially inconsistent) correspondences. An implementation of CLEAR is made publicly available online.
Dynamic-Weighted Simplex Strategy for Learning Enabled Cyber Physical Systems
Venue: arXiv cs.AI 2020
Year: 2020

Cyber Physical Systems (CPS) have increasingly started using Learning Enabled Components (LECs) for performing perception-based control tasks. The simple design approach, and their capability to continuously learn has led to their widespread use in different autonomous applications. Despite their simplicity and impressive capabilities, these models are difficult to assure, which makes their use challenging. The problem of assuring CPS with untrusted controllers has been achieved using the Simplex Architecture. This architecture integrates the system to be assured with a safe controller and provides a decision logic to switch between the decisions of these controllers. However, the key challenges in using the Simplex Architecture are: (1) designing an effective decision logic, and (2) sudden transitions between controller decisions lead to inconsistent system performance. To address these research challenges, we make three key contributions: (1) \textit{dynamic-weighted simplex strategy} -- we introduce ``weighted simplex strategy" as the weighted ensemble extension of the classical Simplex Architecture. We then provide a reinforcement learning based mechanism to find dynamic ensemble weights, (2) \textit{middleware framework} -- we design a framework that allows the use of the dynamic-weighted simplex strategy, and provides a resource manager to monitor the computational resources, and (3) \textit{hardware testbed} -- we design a remote-controlled car testbed called DeepNNCar to test and demonstrate the aforementioned key concepts. Using the hardware, we show that the dynamic-weighted simplex strategy has 60\% fewer out-of-track occurrences (soft constraint violations), while demonstrating higher optimized speed (performance) of 0.4 m/s during indoor driving than the original LEC driven system.
On the security relevance of weights in deep learning
Venue: arXiv cs.CR 2020
Year: 2020

Recently, a weight-based attack on stochastic gradient descent inducing overfitting has been proposed. We show that the threat is broader: A task-independent permutation on the initial weights suffices to limit the achieved accuracy to for example 50% on the Fashion MNIST dataset from initially more than $90$%. These findings are confirmed on MNIST and CIFAR. We formally confirm that the attack succeeds with high likelihood and does not depend on the data. Empirically, weight statistics and loss appear unsuspicious, making it hard to detect the attack if the user is not aware. Our paper is thus a call for action to acknowledge the importance of the initial weights in deep learning.
A 3D Probabilistic Deep Learning System for Detection and Diagnosis of Lung Cancer Using Low-Dose CT Scans
Venue: arXiv cs.CV 2020
Year: 2020

We introduce a new computer aided detection and diagnosis system for lung cancer screening with low-dose CT scans that produces meaningful probability assessments. Our system is based entirely on 3D convolutional neural networks and achieves state-of-the-art performance for both lung nodule detection and malignancy classification tasks on the publicly available LUNA16 and Kaggle Data Science Bowl challenges. While nodule detection systems are typically designed and optimized on their own, we find that it is important to consider the coupling between detection and diagnosis components. Exploiting this coupling allows us to develop an end-to-end system that has higher and more robust performance and eliminates the need for a nodule detection false positive reduction stage. Furthermore, we characterize model uncertainty in our deep learning systems, a first for lung CT analysis, and show that we can use this to provide well-calibrated classification probabilities for both nodule detection and patient malignancy diagnosis. These calibrated probabilities informed by model uncertainty can be used for subsequent risk-based decision making towards diagnostic interventions or disease treatments, as we demonstrate using a probability-based patient referral strategy to further improve our results.
On the Convergence of Network Systems
Venue: arXiv cs.DS 2020
Year: 2020

The apparent disconnection between the microscopic and the macroscopic is a major issue in the understanding of complex systems. To this extend, we study the convergence of repeatedly applying local rules on a network, and touch on the expressive power of this model. We look at network systems and study their behavior when different types of local rules are applied on them. For a very general class of local rules, we prove convergence and provide a certain member of this class that, when applied on a graph, efficiently computes its k-core and its (k-1)-crust giving hints on the expressive power of such a model. Furthermore, we provide guarantees on the speed of convergence for an important subclass of the aforementioned class. We also study more general rules, and show that they do not converge. Our counterexamples resolve an open question of (Zhang, Wang, Wang, Zhou, KDD- 2009) as well, concerning whether a certain process converges. Finally, we show the universality of our network system, by providing a local rule under which it is Turing-Complete.
Asymptotic resolution bounds of generalized modularity and multi-scale community detection
Venue: arXiv cs.SI 2020
Year: 2020

The maximization of generalized modularity performs well on networks in which the members of all communities are statistically indistinguishable from each other. However, there is no theory bounding the maximization performance in more realistic networks where edges are heterogeneously distributed within and between communities. Using the random graph properties, we establish asymptotic theoretical bounds on the resolution parameter for which the generalized modularity maximization performs well. From this new perspective on random graph model, we find the resolution limit of modularity maximization can be explained in a surprisingly simple and straightforward way. Given a network produced by the stochastic block models, the communities for which the resolution parameter is larger than their densities are likely to be spread among multiple clusters, while communities for which the resolution parameter is smaller than their background inter-community edge density will be merged into one large component. Therefore, no suitable resolution parameter exits when the intra-community edge density in a subgraph is lower than the inter-community edge density in some other subgraph. For such networks, we propose a progressive agglomerative heuristic algorithm to detect practically significant communities at multiple scales.
Orchestrating Product Provenance Story: When IOTA ECOSYSTEM Meets The Electronics Supply Chain Space
Venue: arXiv cs.CR 2020
Year: 2020

"Trustworthy data" is the fuel for ensuring transparent traceability, precise decision-making, and cogent coordination in the supply chain (SC) space. However, the disparate data silos act as a trade barrier in orchestrating the provenance of product story starting from the transformation of raw materials into the circuit board to the assembling of electronic components into end products available on the store shelf for customers. Therefore, to bridge the fragmented siloed information across global supply chain partners, the diffusion of blockchain (BC) as one of the advanced distributed ledger technology (DLT) takeover the on-premise legacy systems. Nevertheless, the challenging constraints of blockchain including scalability, accessing off-line data, fee-less microtransactions and many more lead to the third wave of blockchain called IOTA. In this paper, we propose a framework for supporting provenance in the electronic supply chain (ECS) by using permissioned IOTA ledger. Realizing the crucial requirement of trustworthy data, we use Masked Authenticated Messaging (MAM) channel provided by IOTA that allows the SC players to procure distributed information while keeping confidential trade flows, tamper-proof data, and fine-grained accessibility rights. To identify operational disruption, we devise a transparent product ledger through transaction data and consignment information to keep track of the complete product journey at each intermediary step during SC processes. Furthermore, we evaluate the secure provenance data construction time for varying payload size.