OpenRaiser/Intern-Atlas huggingface dataset:
Subspace Packings
Venue: arXiv cs.IT 2019
Year: 2019

The Grassmannian ${\mathcal G}_q(n,k)$ is the set of all $k$-dimensional subspaces of the vector space $\mathbb{F}_q^n$. It is well known that codes in the Grassmannian space can be used for error-correction in random network coding. On the other hand, these codes are $q$-analogs of codes in the Johnson scheme, i.e. constant dimension codes. These codes of the Grassmannian ${\mathcal G}_q(n,k)$ also form a family of $q$-analogs of block designs and they are called \emph{subspace designs}. The application of subspace codes has motivated extensive work on the $q$-analogs of block designs. In this paper, we examine one of the last families of $q$-analogs of block designs which was not considered before. This family called \emph{subspace packings} is the $q$-analog of packings. This family of designs was considered recently for network coding solution for a family of multicast networks called the generalized combination networks. A \emph{subspace packing} $t$-$(n,k,λ)^m_q$ is a set $\mathcal{S}$ of $k$-subspaces from ${\mathcal G}_q(n,k)$ such that each $t$-subspace of ${\mathcal G}_q(n,t)$ is contained in at most $λ$ elements of $\mathcal{S}$. The goal of this work is to consider the largest size of such subspace packings.
The Generic SysML/KAOS Domain Metamodel
Venue: arXiv cs.SE 2019
Year: 2019

This paper is related to the generalised/generic version of the SysML/KAOS domain metamodel and on translation and back propagation rules between the new domain models and B System specifications.
Observability Properties of Colored Graphs
Venue: arXiv cs.LG 2019
Year: 2019

A colored graph is a directed graph in which nodes or edges have been assigned colors that are not necessarily unique. Observability problems in such graphs consider whether an agent observing the colors of edges or nodes traversed on a path in the graph can determine which node they are at currently or which nodes were visited earlier in the traversal. Previous research efforts have identified several different notions of observability as well as the associated properties of graphs for which those observability properties hold. This paper unifies the prior work into a common framework with several new results about relationships between those notions and associated graph properties. The new framework provides an intuitive way to reason about the attainable accuracy as a function of lag and time spent observing, and identifies simple modifications to improve the observability of a given graph. We show that one form of the graph modification problem is in NP-Complete. The intuition of the new framework is borne out with numerical experiments. This work has implications for problems that can be described in terms of an agent traversing a colored graph, including the reconstruction of hidden states in a hidden Markov model (HMM).
Transkernel: Bridging Monolithic Kernels to Peripheral Cores
Venue: arXiv cs.OS 2019
Year: 2019

Smart devices see a large number of ephemeral tasks driven by background activities. In order to execute such a task, the OS kernel wakes up the platform beforehand and puts it back to sleep afterwards. In doing so, the kernel operates various IO devices and orchestrates their power state transitions. Such kernel executions are inefficient as they mismatch typical CPU hardware. They are better off running on a low-power, microcontroller-like core, i.e., peripheral core, relieving CPU from the inefficiency. We therefore present a new OS structure, in which a lightweight virtual executor called transkernel offloads specific phases from a monolithic kernel. The transkernel translates stateful kernel execution through cross-ISA, dynamic binary translation (DBT); it emulates a small set of stateless kernel services behind a narrow, stable binary interface; it specializes for hot paths; it exploits ISA similarities for lowering DBT cost. Through an ARM-based prototype, we demonstrate transkernel's feasibility and benefit. We show that while cross-ISA DBT is typically used under the assumption of efficiency loss, it can enable efficiency gain, even on off-the-shelf hardware.
Deep Neural Network Augmentation: Generating Faces for Affect Analysis
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents a novel approach for synthesizing facial affect; either in terms of the six basic expressions (i.e., anger, disgust, fear, joy, sadness and surprise), or in terms of valence (i.e., how positive or negative is an emotion) and arousal (i.e., power of the emotion activation). The proposed approach accepts the following inputs: i) a neutral 2D image of a person; ii) a basic facial expression or a pair of valence-arousal (VA) emotional state descriptors to be generated, or a path of affect in the 2D VA Space to be generated as an image sequence. In order to synthesize affect in terms of VA, for this person, $600,000$ frames from the 4DFAB database were annotated. The affect synthesis is implemented by fitting a 3D Morphable Model on the neutral image, then deforming the reconstructed face and adding the inputted affect, and blending the new face with the given affect into the original image. Qualitative experiments illustrate the generation of realistic images, when the neutral image is sampled from thirteen well known lab-controlled or in-the-wild databases, including Aff-Wild, AffectNet, RAF-DB; comparisons with Generative Adversarial Networks (GANs) show the higher quality achieved by the proposed approach. Then, quantitative experiments are conducted, in which the synthesized images are used for data augmentation in training Deep Neural Networks to perform affect recognition over all databases; greatly improved performances are achieved when compared with state-of-the-art methods, as well as with GAN-based data augmentation, in all cases.
Shall I Compare Thee to a Machine-Written Sonnet? An Approach to Algorithmic Sonnet Generation
Venue: arXiv cs.AI 2019
Year: 2019

We provide an approach for generating beautiful poetry. Our sonnet-generation algorithm includes several novel elements that improve over the state of the art, leading to metrical, rhyming poetry with many human-like qualities. These novel elements include in-line punctuation, part of speech restrictions, and more appropriate training corpora. Our work is the winner of the 2018 PoetiX Literary Turing Test Award for computer-generated poetry.
Exploiting temporal and depth information for multi-frame face anti-spoofing
Venue: arXiv cs.CV 2019
Year: 2019

Face anti-spoofing is significant to the security of face recognition systems. Previous works on depth supervised learning have proved the effectiveness for face anti-spoofing. Nevertheless, they only considered the depth as an auxiliary supervision in the single frame. Different from these methods, we develop a new method to estimate depth information from multiple RGB frames and propose a depth-supervised architecture which can efficiently encodes spatiotemporal information for presentation attack detection. It includes two novel modules: optical flow guided feature block (OFFB) and convolution gated recurrent units (ConvGRU) module, which are designed to extract short-term and long-term motion to discriminate living and spoofing faces. Extensive experiments demonstrate that the proposed approach achieves state-of-the-art results on four benchmark datasets, namely OULU-NPU, SiW, CASIA-MFSD, and Replay-Attack.
Improved Fourier Mellin Invariant for Robust Rotation Estimation with Omni-cameras
Venue: arXiv cs.RO 2019
Year: 2019

Spectral methods such as the improved Fourier Mellin Invariant (iFMI) transform have proved faster, more robust and accurate than feature based methods on image registration. However, iFMI is restricted to work only when the camera moves in 2D space and has not been applied on omni-cameras images so far. In this work, we extend the iFMI method and apply a motion model to estimate an omni-camera's pose when it moves in 3D space. This is particularly useful in field robotics applications to get a rapid and comprehensive view of unstructured environments, and to estimate robustly the robot pose. In the experiment section, we compared the extended iFMI method against ORB and AKAZE feature based approaches on three datasets showing different type of environments: office, lawn and urban scenery (MPI-omni dataset). The results show that our method boosts the accuracy of the robot pose estimation two to four times with respect to the feature registration techniques, while offering lower processing times. Furthermore, the iFMI approach presents the best performance against motion blur typically present in mobile robotics.
Vectorized Character Counting for Faster Pattern Matching
Venue: arXiv cs.DS 2019
Year: 2019

Many modern sequence alignment tools implement fast string matching using the space efficient data structure called FM-index. The succinct nature of this data structure presents unique challenges for the algorithm designers. In this paper, we explore the opportunities for parallelization of the exact and inexact matches and present an efficient SIMD solution for the Occ portion of the algorithm. Our implementation computes all eight Occ values required for the inexact match algorithm step in a single pass. We showcase the algorithm performance in a multi-core genome aligner and discuss effects of the memory prefetch.
State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis
Venue: arXiv cs.CC 2019
Year: 2019

The linear space hypothesis is a practical working hypothesis, which originally states the insolvability of a restricted 2CNF Boolean formula satisfiability problem parameterized by the number of Boolean variables. From this hypothesis, it naturally follows that the degree-3 directed graph connectivity problem (3DSTCON) parameterized by the number of vertices in a given graph cannot belong to PsubLIN, composed of all parameterized decision problems computable by polynomial-time, sub-linear-space deterministic Turing machines. This hypothesis immediately implies L$\neq$NL and it was used as a solid foundation to obtain new lower bounds on the computational complexity of various NL search and NL optimization problems. The state complexity of transformation refers to the cost of converting one type of finite automata to another type, where the cost is measured in terms of the increase of the number of inner states of the converted automata from that of the original automata. We relate the linear space hypothesis to the state complexity of transforming restricted 2-way nondeterministic finite automata to computationally equivalent 2-way alternating finite automata having narrow computation graphs. For this purpose, we present state complexity characterizations of 3DSTCON and PsubLIN. We further characterize a nonuniform version of the linear space hypothesis in terms of the state complexity of transformation.
Investigating Bell Inequalities for Multidimensional Relevance Judgments in Information Retrieval
Venue: arXiv cs.IR 2019
Year: 2019

Relevance judgment in Information Retrieval is influenced by multiple factors. These include not only the topicality of the documents but also other user oriented factors like trust, user interest, etc. Recent works have identified these various factors into seven dimensions of relevance. In a previous work, these relevance dimensions were quantified and user's cognitive state with respect to a document was represented as a state vector in a Hilbert Space, with each relevance dimension representing a basis. It was observed that relevance dimensions are incompatible in some documents, when making a judgment. Incompatibility being a fundamental feature of Quantum Theory, this motivated us to test the Quantum nature of relevance judgments using Bell type inequalities. However, none of the Bell-type inequalities tested have shown any violation. We discuss our methodology to construct incompatible basis for documents from real world query log data, the experiments to test Bell inequalities on this dataset and possible reasons for the lack of violation.
The 5G-AKA Authentication Protocol Privacy
Venue: arXiv cs.CR 2019
Year: 2019

We study the 5G-AKA authentication protocol described in the 5G mobile communication standards. This version of AKA tries to achieve a better privacy than the 3G and 4G versions through the use of asymmetric randomized encryption. Nonetheless, we show that except for the IMSI-catcher attack, all known attacks against 5G-AKA privacy still apply. Next, we modify the 5G-AKA protocol to prevent these attacks, while satisfying the cost and efficiency constraints of the 5G-AKA protocol. We then formally prove that our protocol is sigma-unlinkable. This is a new security notion, which allows for a fine-grained quantification of a protocol privacy. Our security proof is carried out in the Bana-Comon indistinguishability logic. We also prove mutual authentication as a secondary result.
Deciding Indistinguishability
Venue: arXiv cs.CR 2019
Year: 2019

Computational indistinguishability is a key property in cryptography and verification of security protocols. Current tools for proving it rely on cryptographic game transformations. We follow Bana and Comon's approach, axiomatizing what an adversary cannot distinguish. We prove the decidability of a set of first-order axioms that are both computationally sound and expressive enough. This can be viewed as the decidability of a family of cryptographic game transformations. Our proof relies on term rewriting and automated deduction techniques.
Augmented LiDAR Simulator for Autonomous Driving
Venue: arXiv cs.CV 2019
Year: 2019

In Autonomous Driving (AD), detection and tracking of obstacles on the roads is a critical task. Deep-learning based methods using annotated LiDAR data have been the most widely adopted approach for this. Unfortunately, annotating 3D point cloud is a very challenging, time- and money-consuming task. In this paper, we propose a novel LiDAR simulator that augments real point cloud with synthetic obstacles (e.g., cars, pedestrians, and other movable objects). Unlike previous simulators that entirely rely on CG models and game engines, our augmented simulator bypasses the requirement to create high-fidelity background CAD models. Instead, we can simply deploy a vehicle with a LiDAR scanner to sweep the street of interests to obtain the background point cloud, based on which annotated point cloud can be automatically generated. This unique "scan-and-simulate" capability makes our approach scalable and practical, ready for large-scale industrial applications. In this paper, we describe our simulator in detail, in particular the placement of obstacles that is critical for performance enhancement. We show that detectors with our simulated LiDAR point cloud alone can perform comparably (within two percentage points) with these trained with real data. Mixing real and simulated data can achieve over 95% accuracy.
GroundNet: Monocular Ground Plane Normal Estimation with Geometric Consistency
Venue: arXiv cs.CV 2019
Year: 2019

We focus on estimating the 3D orientation of the ground plane from a single image. We formulate the problem as an inter-mingled multi-task prediction problem by jointly optimizing for pixel-wise surface normal direction, ground plane segmentation, and depth estimates. Specifically, our proposed model, GroundNet, first estimates the depth and surface normal in two separate streams, from which two ground plane normals are then computed deterministically. To leverage the geometric correlation between depth and normal, we propose to add a consistency loss on top of the computed ground plane normals. In addition, a ground segmentation stream is used to isolate the ground regions so that we can selectively back-propagate parameter updates through only the ground regions in the image. Our method achieves the top-ranked performance on ground plane normal estimation and horizon line detection on the real-world outdoor datasets of ApolloScape and KITTI, improving the performance of previous art by up to 17.7% relatively.
NSEEN: Neural Semantic Embedding for Entity Normalization
Venue: arXiv cs.IR 2019
Year: 2019

Much of human knowledge is encoded in text, available in scientific publications, books, and the web. Given the rapid growth of these resources, we need automated methods to extract such knowledge into machine-processable structures, such as knowledge graphs. An important task in this process is entity normalization, which consists of mapping noisy entity mentions in text to canonical entities in well-known reference sets. However, entity normalization is a challenging problem; there often are many textual forms for a canonical entity that may not be captured in the reference set, and entities mentioned in text may include many syntactic variations, or errors. The problem is particularly acute in scientific domains, such as biology. To address this problem, we have developed a general, scalable solution based on a deep Siamese neural network model to embed the semantic information about the entities, as well as their syntactic variations. We use these embeddings for fast mapping of new entities to large reference sets, and empirically show the effectiveness of our framework in challenging bio-entity normalization datasets.
Architectural-Space Exploration of Heterogeneous Reliability and Checkpointing Modes for Out-of-Order Superscalar Processors
Venue: arXiv cs.AR 2019
Year: 2019

Reliability has emerged as a key topic of interest for researchers around the world to detect and/or mitigate the side effects of decreasing transistor sizes, such as soft errors. Traditional solutions, like DMR and TMR, incur significant area and power overheads, which might not always be applicable due to power restrictions. Therefore, we investigate alternative heterogeneous reliability modes that can be activated at run-time based on the system requirements, while reducing the power and area overheads of the processor. Our heterogeneous reliability modes are successful in reducing the processor vulnerability by 87% on average, with area and power overheads of 10% and 43%, respectively. To further enhance the design space of heterogeneous reliability, we investigate combinations of efficient compression techniques like Distributed Multi-threaded Checkpointing, Hash-based Incremental Checkpointing, and GNU zip, to reduce the storage requirements of data that are backed-up at an application checkpoint. We have successfully reduced checkpoint sizes by a factor ~6x by combining various state compression techniques. We use gem5 to implement and simulate the state compression techniques and the heterogeneous reliability modes discussed in this paper.
Approximate Eigenvalue Decompositions of Linear Transformations with a Few Householder Reflectors
Venue: arXiv cs.NA 2019
Year: 2019

The ability to decompose a signal in an orthonormal basis (a set of orthogonal components, each normalized to have unit length) using a fast numerical procedure rests at the heart of many signal processing methods and applications. The classic examples are the Fourier and wavelet transforms that enjoy numerically efficient implementations (FFT and FWT, respectively). Unfortunately, orthonormal transformations are in general unstructured, and therefore they do not enjoy low computational complexity properties. In this paper, based on Householder reflectors, we introduce a class of orthonormal matrices that are numerically efficient to manipulate: we control the complexity of matrix-vector multiplications with these matrices using a given parameter. We provide numerical algorithms that approximate any orthonormal or symmetric transform with a new orthonormal or symmetric structure made up of products of a given number of Householder reflectors. We show analyses and numerical evidence to highlight the accuracy of the proposed approximations and provide an application to the case of learning fast Mahanalobis distance metric transformations.
M2U-Net: Effective and Efficient Retinal Vessel Segmentation for Resource-Constrained Environments
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we present a novel neural network architecture for retinal vessel segmentation that improves over the state of the art on two benchmark datasets, is the first to run in real time on high resolution images, and its small memory and processing requirements make it deployable in mobile and embedded systems. The M2U-Net has a new encoder-decoder architecture that is inspired by the U-Net. It adds pretrained components of MobileNetV2 in the encoder part and novel contractive bottleneck blocks in the decoder part that, combined with bilinear upsampling, drastically reduce the parameter count to 0.55M compared to 31.03M in the original U-Net. We have evaluated its performance against a wide body of previously published results on three public datasets. On two of them, the M2U-Net achieves new state-of-the-art performance by a considerable margin. When implemented on a GPU, our method is the first to achieve real-time inference speeds on high-resolution fundus images. We also implemented our proposed network on an ARM-based embedded system where it segments images in between 0.6 and 15 sec, depending on the resolution. Thus, the M2U-Net enables a number of applications of retinal vessel structure extraction, such as early diagnosis of eye diseases, retinal biometric authentication systems, and robot assisted microsurgery.
Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
Venue: arXiv cs.SI 2019
Year: 2019

The standard greedy algorithm has been recently shown to enjoy approximation guarantees for constrained non-submodular nondecreasing set function maximization. While these recent results allow to better characterize the empirical success of the greedy algorithm, they are only applicable to simple cardinality constraints. In this paper, we study the problem of maximizing a non-submodular nondecreasing set function subject to a general matroid constraint. We first show that the standard greedy algorithm offers an approximation factor of $\frac{0.4 γ^{2}}{\sqrt{γr} + 1}$, where $γ$ is the submodularity ratio of the function and $r$ is the rank of the matroid. Then, we show that the same greedy algorithm offers a constant approximation factor of $(1 + 1/(1-α))^{-1}$, where $α$ is the generalized curvature of the function. In addition, we demonstrate that these approximation guarantees are applicable to several real-world applications in which the submodularity ratio and the generalized curvature can be bounded. Finally, we show that our greedy algorithm does achieve a competitive performance in practice using a variety of experiments on synthetic and real-world data.
Fenchel Lifted Networks: A Lagrange Relaxation of Neural Network Training
Venue: arXiv cs.LG 2019
Year: 2019

Despite the recent successes of deep neural networks, the corresponding training problem remains highly non-convex and difficult to optimize. Classes of models have been proposed that introduce greater structure to the objective function at the cost of lifting the dimension of the problem. However, these lifted methods sometimes perform poorly compared to traditional neural networks. In this paper, we introduce a new class of lifted models, Fenchel lifted networks, that enjoy the same benefits as previous lifted models, without suffering a degradation in performance over classical networks. Our model represents activation functions as equivalent biconvex constraints and uses Lagrange Multipliers to arrive at a rigorous lower bound of the traditional neural network training problem. This model is efficiently trained using block-coordinate descent and is parallelizable across data points and/or layers. We compare our model against standard fully connected and convolutional networks and show that we are able to match or beat their performance.