OpenRaiser/Intern-Atlas huggingface dataset:
Full Characterization of Minimal Linear Codes as Cutting Blocking Sets
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we first study in detail the relationship between minimal linear codes and cutting blocking sets, which were recently introduced by Bonini and Borello, and then completely characterize minimal linear codes as cutting blocking sets. As a direct result, minimal projective codes of dimension $3$ and $t$-fold blocking sets with $t\ge 2$ in projective planes are identical objects. Some bounds on the parameters of minimal codes are derived from this characterization. This confirms a recent conjecture by Alfarano, Borello and Neri in [a geometric characterization of minimal codes and their asymptotic performance, arXiv:1911.11738, 2019] about a lower bound of the minimum distance of a minimal code. Using this new link between minimal codes and blocking sets, we also present new general primary and secondary constructions of minimal linear codes. As a result, infinite families of minimal linear codes not satisfying the Aschikhmin-Barg's condition are obtained. In addition to this, the weight distributions of two subfamilies of the proposed minimal linear codes are established. Open problems are also presented.
Probability Analysis of Age of Information in Multi-hop Networks
Venue: arXiv cs.IT 2020
Year: 2020

Age-of-information (AoI) is a metric quantifying information freshness at the receiver. It captures the delay together with packet loss and packet generation rate. However, the existing literature focuses on average or peak AoI and neglects the complete distribution. In this work, we consider a N-hop network with time-invariant packet loss probabilities on each link. We derive closed form equations for the probability mass function of AoI. We verify our findings with simulations. Our results show that the performance indicators considered in the literature such as average or peak AoI may give misleading insights into the real AoI performance.
SelfVIO: Self-Supervised Deep Monocular Visual-Inertial Odometry and Depth Estimation
Venue: arXiv cs.CV 2020
Year: 2020

In the last decade, numerous supervised deep learning approaches requiring large amounts of labeled data have been proposed for visual-inertial odometry (VIO) and depth map estimation. To overcome the data limitation, self-supervised learning has emerged as a promising alternative, exploiting constraints such as geometric and photometric consistency in the scene. In this study, we introduce a novel self-supervised deep learning-based VIO and depth map recovery approach (SelfVIO) using adversarial training and self-adaptive visual-inertial sensor fusion. SelfVIO learns to jointly estimate 6 degrees-of-freedom (6-DoF) ego-motion and a depth map of the scene from unlabeled monocular RGB image sequences and inertial measurement unit (IMU) readings. The proposed approach is able to perform VIO without the need for IMU intrinsic parameters and/or the extrinsic calibration between the IMU and the camera. estimation and single-view depth recovery network. We provide comprehensive quantitative and qualitative evaluations of the proposed framework comparing its performance with state-of-the-art VIO, VO, and visual simultaneous localization and mapping (VSLAM) approaches on the KITTI, EuRoC and Cityscapes datasets. Detailed comparisons prove that SelfVIO outperforms state-of-the-art VIO approaches in terms of pose estimation and depth recovery, making it a promising approach among existing methods in the literature.
High Quality ELMo Embeddings for Seven Less-Resourced Languages
Venue: arXiv cs.CL 2020
Year: 2020

Recent results show that deep neural networks using contextual embeddings significantly outperform non-contextual embeddings on a majority of text classification task. We offer precomputed embeddings from popular contextual ELMo model for seven languages: Croatian, Estonian, Finnish, Latvian, Lithuanian, Slovenian, and Swedish. We demonstrate that the quality of embeddings strongly depends on the size of training set and show that existing publicly available ELMo embeddings for listed languages shall be improved. We train new ELMo embeddings on much larger training sets and show their advantage over baseline non-contextual FastText embeddings. In evaluation, we use two benchmarks, the analogy task and the NER task.
Optimal Non-Coherent Detector for Ambient Backscatter Communication System
Venue: arXiv cs.IT 2020
Year: 2020

The probability density function (pdf) of the received signal of an ambient backscatter communication system is derived, assuming that on-off keying (OOK) is performed at the tag, and that the ambient radio frequency (RF) signal is white Gaussian. The pdf of the received signal is then utilized to design two different types of non-coherent detectors. The first detector directly uses the received signal to perform a hypothesis test. The second detector first estimates the channel based on the observed signal and then performs the hypothesis test. Test statistics and optimal decision threshold of the detectors are derived. The energy detector is shown to be an approximation of the second detector. For cases where the reader is able to avoid or cancel the direct interference from the RF source (e.g., through successive interference cancellation), a third detector is given as a special case of the first detector. Numerical results show that both the first and the second detectors have the same bit error rate (BER) performance, making the second detector preferable over the first detector due to its computational simplicity.
Subexponential LPs Approximate Max-Cut
Venue: arXiv cs.DS 2020
Year: 2020

We show that for every $\varepsilon > 0$, the degree-$n^\varepsilon$ Sherali-Adams linear program (with $\exp(\tilde{O}(n^\varepsilon))$ variables and constraints) approximates the maximum cut problem within a factor of $(\frac{1}{2}+\varepsilon')$, for some $\varepsilon'(\varepsilon) > 0$. Our result provides a surprising converse to known lower bounds against all linear programming relaxations of Max-Cut, and hence resolves the extension complexity of approximate Max-Cut for approximation factors close to $\frac{1}{2}$ (up to the function $\varepsilon'(\varepsilon)$). Previously, only semidefinite programs and spectral methods were known to yield approximation factors better than $\frac 12$ for Max-Cut in time $2^{o(n)}$. We also show that constant-degree Sherali-Adams linear programs (with $\text{poly}(n)$ variables and constraints) can solve Max-Cut with approximation factor close to $1$ on graphs of small threshold rank: this is the first connection of which we are aware between threshold rank and linear programming-based algorithms. Our results separate the power of Sherali-Adams versus Lovász-Schrijver hierarchies for approximating Max-Cut, since it is known that $(\frac{1}{2}+\varepsilon)$ approximation of Max Cut requires $Ω_\varepsilon (n)$ rounds in the Lovász-Schrijver hierarchy. We also provide a subexponential time approximation for Khot's Unique Games problem: we show that for every $\varepsilon > 0$ the degree-$(n^\varepsilon \log q)$ Sherali-Adams linear program distinguishes instances of Unique Games of value $\geq 1-\varepsilon'$ from instances of value $\leq \varepsilon'$, for some $\varepsilon'( \varepsilon) >0$, where $q$ is the alphabet size. Such guarantees are qualitatively similar to those of previous subexponential-time algorithms for Unique Games but our algorithm does not rely on semidefinite programming or subspace enumeration techniques.
Unsupervised Keyword Extraction for Full-sentence VQA
Venue: arXiv cs.CV 2020
Year: 2020

In the majority of the existing Visual Question Answering (VQA) research, the answers consist of short, often single words, as per instructions given to the annotators during dataset construction. This study envisions a VQA task for natural situations, where the answers are more likely to be sentences rather than single words. To bridge the gap between this natural VQA and existing VQA approaches, a novel unsupervised keyword extraction method is proposed. The method is based on the principle that the full-sentence answers can be decomposed into two parts: one that contains new information answering the question (i.e., keywords), and one that contains information already included in the question. Discriminative decoders were designed to achieve such decomposition, and the method was experimentally implemented on VQA datasets containing full-sentence answers. The results show that the proposed model can accurately extract the keywords without being given explicit annotations describing them.
List colouring of two matroids through reduction to partition matroids
Venue: arXiv cs.DM 2020
Year: 2020

In the list coloring problem for two matroids, we are given matroids $M_1=(S,{\cal I}_1)$ and $M_2=(S,{\cal I}_2)$ on the same ground set $S$, and the goal is to determine the smallest number $k$ such that given arbitrary lists $L_s$ of $k$ colors for $s\in S$, it is possible to choose a color from each list so that every monochromatic set is independent in both $M_1$ and $M_2$. When both $M_1$ and $M_2$ are partition matroids, Galvin's list coloring theorem for bipartite graphs gives the answer. One of the main open questions is to decide if there exists a constant $c$ such that if the coloring number is $k$ (i.e., the ground set can be partitioned into $k$ common independent sets), then the list coloring number is at most $c\cdot k$. We consider matroid classes that appear naturally in combinatorial optimization problems, namely graphic matroids, paving matroids and gammoids. We show that if both matroids are from these fundamental classes, then the list coloring number is at most twice the coloring number. The proof is based on a new approach that reduces a matroid to a partition matroid without increasing its coloring number too much, and might be of independent combinatorial interest. In particular, we show that if $M=(S,{\cal I})$ is a matroid in which $S$ can be partitioned into $k$ independent sets, then there exists a partition matroid $N=(S,{\cal J})$ with ${\cal J}\subseteq{\cal I}$ in which $S$ can be partitioned into (A) $k$ independent sets if $M$ is a transversal matroid, (B) $2k-1$ independent sets if $M$ is a graphic matroid, (C) $\lceil kr/(r-1)\rceil$ independent sets if $M$ is a paving matroid of rank $r$, and (D) $2k-2$ independent sets if $M$ is a gammoid. We extend our results by showing that the existence of a matroid $N$ with $χ(N)\leq 2χ(M)$ implies the existence of a matroid $N'$ with $χ(N')\leq 2χ(M')$ for every truncation $M'$ of $M$.
Delay-Complexity Trade-off of Random Linear Network Coding in Wireless Broadcast
Venue: arXiv cs.IT 2020
Year: 2020

In wireless broadcast, random linear network coding (RLNC) over GF(2^L) is known to asymptotically achieve the optimal completion delay with increasing L. However, the high decoding complexity hinders the potential applicability of RLNC schemes over large GF(2^L). In this paper, a comprehensive analysis of completion delay and decoding complexity is conducted for field-based systematic RLNC schemes in wireless broadcast. In particular, we prove that the RLNC scheme over GF(2) can also asymptotically approach the optimal completion delay per packet when the packet number goes to infinity. Moreover, we introduce a new method, based on circular-shift operations, to design RLNC schemes which avoid multiplications over large GF(2^L). Based on both theoretical and numerical analyses, the new RLNC schemes turn out to have a much better trade-off between completion delay and decoding complexity. In particular, numerical results demonstrate that the proposed schemes can attain average completion delay just within 5% higher than the optimal one, while the decoding complexity is only about 3 times the one of the RLNC scheme over GF(2).
Time-aware Gradient Attack on Dynamic Network Link Prediction
Venue: arXiv cs.SI 2020
Year: 2020

In network link prediction, it is possible to hide a target link from being predicted with a small perturbation on network structure. This observation may be exploited in many real world scenarios, for example, to preserve privacy, or to exploit financial security. There have been many recent studies to generate adversarial examples to mislead deep learning models on graph data. However, none of the previous work has considered the dynamic nature of real-world systems. In this work, we present the first study of adversarial attack on dynamic network link prediction (DNLP). The proposed attack method, namely time-aware gradient attack (TGA), utilizes the gradient information generated by deep dynamic network embedding (DDNE) across different snapshots to rewire a few links, so as to make DDNE fail to predict target links. We implement TGA in two ways: one is based on traversal search, namely TGA-Tra; and the other is simplified with greedy search for efficiency, namely TGA-Gre. We conduct comprehensive experiments which show the outstanding performance of TGA in attacking DNLP algorithms.
Towards a Hypothesis on Visual Transformation based Self-Supervision
Venue: arXiv cs.LG 2020
Year: 2020

We propose the first qualitative hypothesis characterizing the behavior of visual transformation based self-supervision, called the VTSS hypothesis. Given a dataset upon which a self-supervised task is performed while predicting instantiations of a transformation, the hypothesis states that if the predicted instantiations of the transformations are already present in the dataset, then the representation learned will be less useful. The hypothesis was derived by observing a key constraint in the application of self-supervision using a particular transformation. This constraint, which we term the transformation conflict for this paper, forces a network learn degenerative features thereby reducing the usefulness of the representation. The VTSS hypothesis helps us identify transformations that have the potential to be effective as a self-supervision task. Further, it helps to generally predict whether a particular transformation based self-supervision technique would be effective or not for a particular dataset. We provide extensive evaluations on CIFAR 10, CIFAR 100, SVHN and FMNIST confirming the hypothesis and the trends it predicts. We also propose novel cost-effective self-supervision techniques based on translation and scale, which when combined with rotation outperforms all transformations applied individually. Overall, this paper aims to shed light on the phenomenon of visual transformation based self-supervision.
Attribute Restoration Framework for Anomaly Detection
Venue: arXiv cs.CV 2020
Year: 2020

With the recent advances in deep neural networks, anomaly detection in multimedia has received much attention in the computer vision community. While reconstruction-based methods have recently shown great promise for anomaly detection, the information equivalence among input and supervision for reconstruction tasks can not effectively force the network to learn semantic feature embeddings. We here propose to break this equivalence by erasing selected attributes from the original data and reformulate it as a restoration task, where the normal and the anomalous data are expected to be distinguishable based on restoration errors. Through forcing the network to restore the original image, the semantic feature embeddings related to the erased attributes are learned by the network. During testing phases, because anomalous data are restored with the attribute learned from the normal data, the restoration error is expected to be large. Extensive experiments have demonstrated that the proposed method significantly outperforms several state-of-the-arts on multiple benchmark datasets, especially on ImageNet, increasing the AUROC of the top-performing baseline by 10.1%. We also evaluate our method on a real-world anomaly detection dataset MVTec AD and a video anomaly detection dataset ShanghaiTech.
Non-parametric Uni-modality Constraints for Deep Ordinal Classification
Venue: arXiv cs.LG 2020
Year: 2020

We propose a new constrained-optimization formulation for deep ordinal classification, in which uni-modality of the label distribution is enforced implicitly via a set of inequality constraints over all the pairs of adjacent labels. Based on (c-1) constraints for c labels, our model is non-parametric and, therefore, more flexible than the existing deep ordinal classification techniques. Unlike these, it does not restrict the learned representation to a single and specific parametric model (or penalty) imposed on all the labels. Therefore, it enables the training to explore larger spaces of solutions, while removing the need for ad hoc choices and scaling up to large numbers of labels. It can be used in conjunction with any standard classification loss and any deep architecture. To tackle the ensuing challenging optimization problem, we solve a sequence of unconstrained losses based on a powerful extension of the log-barrier method. This handles effectively competing constraints and accommodates standard SGD for deep networks, while avoiding computationally expensive Lagrangian dual steps and outperforming substantially penalty methods. Furthermore, we propose a new performance metric for ordinal classification, as a proxy to measure distribution uni-modality, referred to as the Sides Order Index (SOI). We report comprehensive evaluations and comparisons to state-of-the-art methods on benchmark public datasets for several ordinal classification tasks, showing the merits of our approach in terms of label consistency, classification accuracy and scalability. Importantly, enforcing label consistency with our model does not incur higher classification errors, unlike many existing ordinal classification methods. A public reproducible PyTorch implementation is provided. (https://github.com/sbelharbi/unimodal-prob-deep-oc-free-distribution)
Minimum-cost integer circulations in given homology classes
Venue: arXiv cs.DM 2020
Year: 2020

Let $D$ be a directed graph cellularly embedded in a surface together with non-negative cost on its arcs. Given any integer circulation in $D$, we study the problem of finding a minimum-cost non-negative integer circulation in $D$ that is homologous over the integers to the given circulation. A special case of this problem arises in recent work on the stable set problem for graphs with bounded odd cycle packing number, in which the surface is non-orientable (Conforti et al., SODA'20). For orientable surfaces, polynomial-time algorithms have been obtained for different variants of this problem. We complement these results by showing that the convex hull of feasible solutions has a very simple polyhedral description. In contrast, only little seems to be known about the case of non-orientable surfaces. We show that the problem is strongly NP-hard for general non-orientable surfaces, and give the first polynomial-time algorithm for surfaces of fixed genus. For the latter, we provide a characterization of homology (over the integers) that allows us to recast the problem as a special integer program, which can be efficiently solved using proximity results and dynamic programming.
Energy-efficient stochastic computing with superparamagnetic tunnel junctions
Venue: arXiv cs.ET 2020
Year: 2020

Superparamagnetic tunnel junctions (SMTJs) have emerged as a competitive, realistic nanotechnology to support novel forms of stochastic computation in CMOS-compatible platforms. One of their applications is to generate random bitstreams suitable for use in stochastic computing implementations. We describe a method for digitally programmable bitstream generation based on pre-charge sense amplifiers. This generator is significantly more energy efficient than SMTJ-based bitstream generators that tune probabilities with spin currents and a factor of two more efficient than related CMOS-based implementations. The true randomness of this bitstream generator allows us to use them as the fundamental units of a novel neural network architecture. To take advantage of the potential savings, we codesign the algorithm with the circuit, rather than directly transcribing a classical neural network into hardware. The flexibility of the neural network mathematics allows us to adapt the network to the explicitly energy efficient choices we make at the device level. The result is a convolutional neural network design operating at $\approx$ 150 nJ per inference with 97 % performance on MNIST -- a factor of 1.4 to 7.7 improvement in energy efficiency over comparable proposals in the recent literature.
Summarizing CPU and GPU Design Trends with Product Data
Venue: arXiv cs.DC 2020
Year: 2020

Moore's Law and Dennard Scaling have guided the semiconductor industry for the past few decades. Recently, both laws have faced validity challenges as transistor sizes approach the practical limits of physics. We are interested in testing the validity of these laws and reflect on the reasons responsible. In this work, we collect data of more than 4000 publicly-available CPU and GPU products. We find that transistor scaling remains critical in keeping the laws valid. However, architectural solutions have become increasingly important and will play a larger role in the future. We observe that GPUs consistently deliver higher performance than CPUs. GPU performance continues to rise because of increases in GPU frequency, improvements in the thermal design power (TDP), and growth in die size. But we also see the ratio of GPU to CPU performance moving closer to parity, thanks to new SIMD extensions on CPUs and increased CPU core counts.
"You might also like this model": Data Driven Approach for Recommending Deep Learning Models for Unknown Image Datasets
Venue: arXiv cs.LG 2020
Year: 2020

For an unknown (new) classification dataset, choosing an appropriate deep learning architecture is often a recursive, time-taking, and laborious process. In this research, we propose a novel technique to recommend a suitable architecture from a repository of known models. Further, we predict the performance accuracy of the recommended architecture on the given unknown dataset, without the need for training the model. We propose a model encoder approach to learn a fixed length representation of deep learning architectures along with its hyperparameters, in an unsupervised fashion. We manually curate a repository of image datasets with corresponding known deep learning models and show that the predicted accuracy is a good estimator of the actual accuracy. We discuss the implications of the proposed approach for three benchmark images datasets and also the challenges in using the approach for text modality. To further increase the reproducibility of the proposed approach, the entire implementation is made publicly available along with the trained models.
Using Depth for Pixel-Wise Detection of Adversarial Attacks in Crowd Counting
Venue: arXiv cs.CV 2020
Year: 2020

State-of-the-art methods for counting people in crowded scenes rely on deep networks to estimate crowd density. While effective, deep learning approaches are vulnerable to adversarial attacks, which, in a crowd-counting context, can lead to serious security issues. However, attack and defense mechanisms have been virtually unexplored in regression tasks, let alone for crowd density estimation. In this paper, we investigate the effectiveness of existing attack strategies on crowd-counting networks, and introduce a simple yet effective pixel-wise detection mechanism. It builds on the intuition that, when attacking a multitask network, in our case estimating crowd density and scene depth, both outputs will be perturbed, and thus the second one can be used for detection purposes. We will demonstrate that this significantly outperforms heuristic and uncertainty-based strategies.