OpenRaiser/Intern-Atlas huggingface dataset:
Image De-Noising For Salt and Pepper Noise by Introducing New Enhanced Filter
Venue: arXiv cs.CV 2019
Year: 2019

When an image is formed, factors such as lighting (spectra, source, and intensity) and camera characteristics (sensor response, lenses) affect the appearance of the image. Therefore, the prime factor that reduces the quality of the image is noise. It hides the important details and information of images. In order to enhance the qualities of the image, the removal of noises become imperative and that should not at the cost of any loss of image information. Noise removal is one of the pre-processing stages of image processing. In this paper a new method for the enhancement of grayscale images is introduced, when images are corrupted by fixed valued impulse noise (salt and pepper noise). The proposed methodology ensures a better output for the low and medium density of fixed value impulse noise as compared to the other famous filters like Standard Median Filter (SMF), Decision Based Median Filter (DBMF) and Modified Decision Based Median Filter (MDBMF) etc. The main objective of the proposed method was to improve peak signal to noise ratio (PSNR), visual perception and reduction in the blurring of the image. The proposed algorithm replaced the noisy pixel by trimmed mean value. When previous pixel values, 0s, and 255s are present in the particular window and all the pixel values are 0s and 255s then the remaining noisy pixels are replaced by mean value. The gray-scale image of mandrill and Lena were tested via the proposed method. The experimental result shows better peak signal to noise ratio (PSNR), mean square error values with better visual and human perception.
Comparative Performance Analysis of Image De-noising Techniques
Venue: arXiv cs.CV 2019
Year: 2019

Noise is an important factor which when get added to an image reduces its quality and appearance. So in order to enhance the image qualities, it has to be removed with preserving the textural information and structural features of image. There are different types of noises exist who corrupt the images. Selection of the denoising algorithm is application dependent. Hence, it is necessary to have knowledge about the noise present in the image so as to select the appropriate denoising algorithm. Objective of this paper is to present brief account on types of noises, its types and different noise removal algorithms. In the first section types of noises on the basis of their additive and multiplicative nature are being discussed. In second section a precise classification and analysis of the different potential image denoising algorithm is presented. At the end of paper, a comparative study of all these algorithms in context of performance evaluation is done and concluded with several promising directions for future research work.
RDCSim: a GPU-Accelerated, Interactive Simulator for Reaction--Diffusion Chemistry
Venue: arXiv cs.ET 2019
Year: 2019

This paper presents RDCSim, an interactive simulator for reaction--diffusion chemistry (RDC) research, being developed as part of an ongoing project studying how humans interact with unconventional computing systems. While much research into the computational properties of RDC makes use of simulations, the development of multiple RDC simulations across different research groups can lead to results that are harder to reproduce. By automating the storage of parameter values alongside simulation results, RDCSim aims to make reproducing RDC results painless. This paper presents the functionality of RDCSim, and verifies the behaviour of the underlying chemical simulation using two seminal examples from the RDC literature: logical AND gates and chemical diodes.
Overfitting Mechanism and Avoidance in Deep Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

Assisted by the availability of data and high performance computing, deep learning techniques have achieved breakthroughs and surpassed human performance empirically in difficult tasks, including object recognition, speech recognition, and natural language processing. As they are being used in critical applications, understanding underlying mechanisms for their successes and limitations is imperative. In this paper, we show that overfitting, one of the fundamental issues in deep neural networks, is due to continuous gradient updating and scale sensitiveness of cross entropy loss. By separating samples into correctly and incorrectly classified ones, we show that they behave very differently, where the loss decreases in the correct ones and increases in the incorrect ones. Furthermore, by analyzing dynamics during training, we propose a consensus-based classification algorithm that enables us to avoid overfitting and significantly improve the classification accuracy especially when the number of training samples is limited. As each trained neural network depends on extrinsic factors such as initial values as well as training data, requiring consensus among multiple models reduces extrinsic factors substantially; for statistically independent models, the reduction is exponential. Compared to ensemble algorithms, the proposed algorithm avoids overgeneralization by not classifying ambiguous inputs. Systematic experimental results demonstrate the effectiveness of the proposed algorithm. For example, using only 1000 training samples from MNIST dataset, the proposed algorithm achieves 95% accuracy, significantly higher than any of the individual models, with 90% of the test samples classified.
Design of Real-time Semantic Segmentation Decoder for Automated Driving
Venue: arXiv cs.CV 2019
Year: 2019

Semantic segmentation remains a computationally intensive algorithm for embedded deployment even with the rapid growth of computation power. Thus efficient network design is a critical aspect especially for applications like automated driving which requires real-time performance. Recently, there has been a lot of research on designing efficient encoders that are mostly task agnostic. Unlike image classification and bounding box object detection tasks, decoders are computationally expensive as well for semantic segmentation task. In this work, we focus on efficient design of the segmentation decoder and assume that an efficient encoder is already designed to provide shared features for a multi-task learning system. We design a novel efficient non-bottleneck layer and a family of decoders which fit into a small run-time budget using VGG10 as efficient encoder. We demonstrate in our dataset that experimentation with various design choices led to an improvement of 10\% from a baseline performance.
Mixed Formal Learning: A Path to Transparent Machine Learning
Venue: arXiv cs.AI 2019
Year: 2019

This paper presents Mixed Formal Learning, a new architecture that learns models based on formal mathematical representations of the domain of interest and exposes latent variables. The second element in the architecture learns a particular skill, typically by using traditional prediction or classification mechanisms. Our key findings include that this architecture: (1) Facilitates transparency by exposing key latent variables based on a learned mathematical model; (2) Enables Low Shot and Zero Shot training of machine learning without sacrificing accuracy or recall.
Efficiently factoring polynomials modulo $p^4$
Venue: arXiv cs.CC 2019
Year: 2019

Polynomial factoring has famous practical algorithms over fields-- finite, rational \& $p$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, $x^2+p \bmod p^2$ is irreducible, but $x^2+px \bmod p^2$ has exponentially many factors! We present the first randomized poly(deg $f, \log p$) time algorithm to factor a given univariate integral $f(x)$ modulo $p^k$, for a prime $p$ and $k \leq 4$. Thus, we solve the open question of factoring modulo $p^3$ posed in (Sircana, ISSAC'17). Our method reduces the general problem of factoring $f(x) \bmod p^k$ to that of {\em root finding} in a related polynomial $E(y) \bmod\langle p^k, φ(x)^\ell \rangle$ for some irreducible $φ\bmod p$. We could efficiently solve the latter for $k\le4$, by incrementally transforming $E(y)$. Moreover, we discover an efficient and strong generalization of Hensel lifting to lift factors of $f(x) \bmod p$ to those $\bmod\ p^4$ (if possible). This was previously unknown, as the case of repeated factors of $f(x) \bmod p$ forbids classical Hensel lifting.
CASCLIK: CasADi-Based Closed-Loop Inverse Kinematics
Venue: arXiv cs.RO 2019
Year: 2019

A Python module for rapid prototyping of constraint-based closed-loop inverse kinematics controllers is presented. The module allows for combining multiple tasks that are resolved with a quadratic, nonlinear, or model predictive optimization-based approach, or a set-based task-priority inverse kinematics approach. The optimization-based approaches are described in relation to the set-based task approach, and a novel multidimensional "in tangent cone" function is presented for set-based tasks. A ROS component is provided, and the controllers are tested with matching a pose using either transformation matrices or dual quaternions, trajectory tracking while remaining in a bounded workspace, maximizing manipulability during a tracking task, tracking an input marker's position, and force compliance.
Comparing Direct and Indirect Representations for Environment-Specific Robot Component Design
Venue: arXiv cs.RO 2019
Year: 2019

We compare two representations used to define the morphology of legs for a hexapod robot, which are subsequently 3D printed. A leg morphology occupies a set of voxels in a voxel grid. One method, a direct representation, uses a collection of Bezier splines. The second, an indirect method, utilises CPPN-NEAT. In our first experiment, we investigate two strategies to post-process the CPPN output and ensure leg length constraints are met. The first uses an adaptive threshold on the output neuron, the second, previously reported in the literature, scales the largest generated artefact to our desired length. In our second experiment, we build on our past work that evolves the tibia of a hexapod to provide environment-specific performance benefits. We compare the performance of our direct and indirect legs across three distinct environments, represented in a high-fidelity simulator. Results are significant and support our hypothesis that the indirect representation allows for further exploration of the design space leading to improved fitness.
Exact Recovery for a Family of Community-Detection Generative Models
Venue: arXiv cs.IT 2019
Year: 2019

Generative models for networks with communities have been studied extensively for being a fertile ground to establish information-theoretic and computational thresholds. In this paper we propose a new toy model for planted generative models called planted Random Energy Model (REM), inspired by Derrida's REM. For this model we provide the asymptotic behaviour of the probability of error for the maximum likelihood estimator and hence the exact recovery threshold. As an application, we further consider the 2 non-equally sized community Weighted Stochastic Block Model (2-WSBM) on $h$-uniform hypergraphs, that is equivalent to the P-REM on both sides of the spectrum, for high and low edge cardinality $h$. We provide upper and lower bounds for the exact recoverability for any $h$, mapping these problems to the aforementioned P-REM. To the best of our knowledge these are the first consistency results for the 2-WSBM on graphs and on hypergraphs with non-equally sized community.
Straggler Resilient Serverless Computing Based on Polar Codes
Venue: arXiv cs.IT 2019
Year: 2019

We propose a serverless computing mechanism for distributed computation based on polar codes. Serverless computing is an emerging cloud based computation model that lets users run their functions on the cloud without provisioning or managing servers. Our proposed approach is a hybrid computing framework that carries out computationally expensive tasks such as linear algebraic operations involving large-scale data using serverless computing and does the rest of the processing locally. We address the limitations and reliability issues of serverless platforms such as straggling workers using coding theory, drawing ideas from recent literature on coded computation. The proposed mechanism uses polar codes to ensure straggler-resilience in a computationally effective manner. We provide extensive evidence showing polar codes outperform other coding methods. We have designed a sequential decoder specifically for polar codes in erasure channels with full-precision input and outputs. In addition, we have extended the proposed method to the matrix multiplication case where both matrices being multiplied are coded. The proposed coded computation scheme is implemented for AWS Lambda. Experiment results are presented where the performance of the proposed coded computation technique is tested in optimization via gradient descent. Finally, we introduce the idea of partial polarization which reduces the computational burden of encoding and decoding at the expense of straggler-resilience.
Towards a Functional Fee Market for Cryptocurrencies
Venue: arXiv cs.CR 2019
Year: 2019

Blockchain-based cryptocurrencies prioritize transactions based on their fees, creating a unique kind of fee market. Empirically, this market has failed to yield stable equilibria with predictable prices for desired levels of service. We argue that this is due to the absence of a dominant strategy equilibrium in the current fee mechanism. We propose an alternative fee setting mechanism that is inspired by generalized second price auctions. The design of such a mechanism is challenging because miners can use any criteria for including transactions and can manipulate the results of the auction after seeing the proposed fees. Nonetheless, we show that our proposed protocol is free from manipulation as the number of users increases. We further show that, for a large number of users and miners, the gain from manipulation is small for all parties. This results in users proposing fees that represent their true utility and lower variance of revenue for miners. Historical analysis shows that Bitcoin users could have saved $272,528,000 USD in transaction fees while miners could have reduced the variance of fee income by an average factor of 7.4 times.
Perception-in-the-Loop Adversarial Examples
Venue: arXiv cs.LG 2019
Year: 2019

We present a scalable, black box, perception-in-the-loop technique to find adversarial examples for deep neural network classifiers. Black box means that our procedure only has input-output access to the classifier, and not to the internal structure, parameters, or intermediate confidence values. Perception-in-the-loop means that the notion of proximity between inputs can be directly queried from human participants rather than an arbitrarily chosen metric. Our technique is based on covariance matrix adaptation evolution strategy (CMA-ES), a black box optimization approach. CMA-ES explores the search space iteratively in a black box manner, by generating populations of candidates according to a distribution, choosing the best candidates according to a cost function, and updating the posterior distribution to favor the best candidates. We run CMA-ES using human participants to provide the fitness function, using the insight that the choice of best candidates in CMA-ES can be naturally modeled as a perception task: pick the top $k$ inputs perceptually closest to a fixed input. We empirically demonstrate that finding adversarial examples is feasible using small populations and few iterations. We compare the performance of CMA-ES on the MNIST benchmark with other black-box approaches using $L_p$ norms as a cost function, and show that it performs favorably both in terms of success in finding adversarial examples and in minimizing the distance between the original and the adversarial input. In experiments on the MNIST, CIFAR10, and GTSRB benchmarks, we demonstrate that CMA-ES can find perceptually similar adversarial inputs with a small number of iterations and small population sizes when using perception-in-the-loop. Finally, we show that networks trained specifically to be robust against $L_\infty$ norm can still be susceptible to perceptually similar adversarial examples.
Signed Network Structural Analysis and Applications with a Focus on Balance Theory
Venue: arXiv cs.SI 2019
Year: 2019

We analyse signed networks from the perspective of balance theory which predicts structural balance as a global structure for signed social networks that represent groups of friends and enemies. The scarcity of balanced networks encouraged us to define the notion of partial balance in order to quantify the extent to which a network is balanced. We evaluate several numerical measures of partial balance and recommend using the frustration index, a measure that satisfies key axiomatic properties and allows us to analyse graphs based on their levels of partial balance. The exact algorithms used in the literature to compute the frustration index, also called the line index of balance, are not scalable and cannot process graphs with a few hundred edges. We formulate computing the frustration index as a graph optimisation problem to find the minimum number of edges whose removal results in a balanced network given binary decision variables associated with graph nodes and edges. We use our first optimisation model to analyse graphs with up to 3000 edges. Reformulating the optimisation problem, we develop three more efficient binary linear programming models. Equipping the models with valid inequalities and prioritised branching as speed-up techniques allows us to process graphs with 15000 edges on inexpensive hardware. Besides making exact computations possible for large graphs, we show that our models outperform heuristics and approximation algorithms suggested in the literature by orders of magnitude. We extend the concepts of balance and frustration in signed networks to applications beyond the classic friend-enemy interpretation of balance theory in social context. Using a high-performance computer, we analyse graphs with up to 100000 edges to investigate a range of applications from biology and chemistry to finance, international relations, and physics.
Network Transplanting (extended abstract)
Venue: arXiv cs.LG 2019
Year: 2019

This paper focuses on a new task, i.e., transplanting a category-and-task-specific neural network to a generic, modular network without strong supervision. We design a functionally interpretable structure for the generic network. Like building LEGO blocks, we teach the generic network a new category by directly transplanting the module corresponding to the category from a pre-trained network with a few or even without sample annotations. Our method incrementally adds new categories to the generic network but does not affect representations of existing categories. In this way, our method breaks the typical bottleneck of learning a net for massive tasks and categories, i.e., the requirement of collecting samples for all tasks and categories at the same time before the learning begins. Thus, we use a new distillation algorithm, namely back-distillation, to overcome specific challenges of network transplanting. Our method without training samples even outperformed the baseline with 100 training samples.
Error-Correcting Neural Sequence Prediction
Venue: arXiv cs.LG 2019
Year: 2019

We propose a novel neural sequence prediction method based on \textit{error-correcting output codes} that avoids exact softmax normalization and allows for a tradeoff between speed and performance. Instead of minimizing measures between the predicted probability distribution and true distribution, we use error-correcting codes to represent both predictions and outputs. Secondly, we propose multiple ways to improve accuracy and convergence rates by maximizing the separability between codes that correspond to classes proportional to word embedding similarities. Lastly, we introduce our main contribution called \textit{Latent Variable Mixture Sampling}, a technique that is used to mitigate exposure bias, which can be integrated into training latent variable-based neural sequence predictors such as ECOC. This involves mixing the latent codes of past predictions and past targets in one of two ways: (1) according to a predefined sampling schedule or (2) a differentiable sampling procedure whereby the mixing probability is learned throughout training by replacing the greedy argmax operation with a smooth approximation. ECOC-NSP leads to consistent improvements on language modelling datasets and the proposed Latent Variable mixture sampling methods are found to perform well for text generation tasks such as image captioning.
Understanding the Impact of Label Granularity on CNN-based Image Classification
Venue: arXiv cs.CV 2019
Year: 2019

In recent years, supervised learning using Convolutional Neural Networks (CNNs) has achieved great success in image classification tasks, and large scale labeled datasets have contributed significantly to this achievement. However, the definition of a label is often application dependent. For example, an image of a cat can be labeled as "cat" or perhaps more specifically "Persian cat." We refer to this as label granularity. In this paper, we conduct extensive experiments using various datasets to demonstrate and analyze how and why training based on fine-grain labeling, such as "Persian cat" can improve CNN accuracy on classifying coarse-grain classes, in this case "cat." The experimental results show that training CNNs with fine-grain labels improves both network's optimization and generalization capabilities, as intuitively it encourages the network to learn more features, and hence increases classification accuracy on coarse-grain classes under all datasets considered. Moreover, fine-grain labels enhance data efficiency in CNN training. For example, a CNN trained with fine-grain labels and only 40% of the total training data can achieve higher accuracy than a CNN trained with the full training dataset and coarse-grain labels. These results point to two possible applications of this work: (i) with sufficient human resources, one can improve CNN performance by re-labeling the dataset with fine-grain labels, and (ii) with limited human resources, to improve CNN performance, rather than collecting more training data, one may instead use fine-grain labels for the dataset. We further propose a metric called Average Confusion Ratio to characterize the effectiveness of fine-grain labeling, and show its use through extensive experimentation. Code is available at https://github.com/cmu-enyac/Label-Granularity.
A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs
Venue: arXiv cs.DS 2019
Year: 2019

The Capacitated Vehicle Routing problem is to find a minimum-cost set of tours that collectively cover clients in a graph, such that each tour starts and ends at a specified depot and is subject to a capacity bound on the number of clients it can serve. In this paper, we present a polynomial-time approximation scheme (PTAS) for instances in which the input graph is planar and the capacity is bounded. Previously, only a quasipolynomial-time approximation scheme was known for these instances. To obtain this result, we show how to embed planar graphs into bounded-treewidth graphs while preserving, in expectation, the client-to-client distances up to a small additive error proportional to client distances to the depot.