OpenRaiser/Intern-Atlas huggingface dataset:
Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
Venue: arXiv cs.DS 2018
Year: 2018

We construct an efficient classical analogue of the quantum matrix inversion algorithm (HHL) for low-rank matrices. Inspired by recent work of Tang, assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix and sample from the solution to the problem $Ax=b$ using fast sampling techniques. We implement the pseudo-inverse by finding an approximate singular value decomposition of $A$ via subsampling, then inverting the singular values. In principle, the approach can also be used to apply any desired "smooth" function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem, our result suggests that more low-rank quantum algorithms can be effectively "dequantised" into classical length-square sampling algorithms.
The Impact of Timestamp Granularity in Optimistic Concurrency Control
Venue: arXiv cs.DB 2018
Year: 2018

Optimistic concurrency control (OCC) can exploit the strengths of parallel hardware to provide excellent performance for uncontended transactions, and is popular in high-performance in-memory databases and transactional systems. But at high contention levels, OCC is susceptible to frequent aborts, leading to wasted work and degraded performance. Contention managers, mixed optimistic/pessimistic concurrency control algorithms, and novel optimistic-inspired concurrency control algorithms, such as TicToc, aim to address this problem, but these mechanisms introduce sometimes-high overheads of their own. We show that in real-world benchmarks, traditional OCC can outperform these alternative mechanisms by simply adding fine-grained version timestamps (using different timestamps for disjoint components of each record). With fine-grained timestamps, OCC gets 1.14x TicToc's throughput in TPC-C at 128 cores (previous work reported TicToc having 1.8x higher throughput than OCC at 80 hyperthreads). Our study shows that timestamp granularity has a greater impact than previously thought on the performance of transaction processing systems, and should not be overlooked in the push for faster concurrency control schemes.
Approximation Algorithms for Minimum Norm and Ordered Optimization Problems
Venue: arXiv cs.DS 2018
Year: 2018

$ $In many optimization problems, a feasible solution induces a multi-dimensional cost vector. For example, in load-balancing a schedule induces a load vector across the machines. In $k$-clustering, opening $k$ facilities induces an assignment cost vector across the clients. In this paper we consider the following minimum norm optimization problem : Given an arbitrary monotone, symmetric norm, find a solution which minimizes the norm of the induced cost-vector. This generalizes many fundamental NP-hard problems. We give a general framework to tackle the minimum norm problem, and illustrate its efficacy in the unrelated machine load balancing and $k$-clustering setting. Our concrete results are the following. $\bullet$ We give constant factor approximation algorithms for the minimum norm load balancing problem in unrelated machines, and the minimum norm $k$-clustering problem. To our knowledge, our results constitute the first constant-factor approximations for such a general suite of objectives. $\bullet$ In load balancing with unrelated machines, we give a $2$-approximation for the problem of finding an assignment minimizing the sum of the largest $\ell$ loads, for any $\ell$. We give a $(2+\varepsilon)$-approximation for the so-called ordered load-balancing problem. $\bullet$ For $k$-clustering, we give a $(5+\varepsilon)$-approximation for the ordered $k$-median problem significantly improving the constant factor approximations from Byrka, Sornat, and Spoerhase (STOC 2018) and Chakrabarty and Swamy (ICALP 2018). $\bullet$ Our techniques also imply $O(1)$ approximations to the best simultaneous optimization factor for any instance of the unrelated machine load-balancing and the $k$-clustering setting. To our knowledge, these are the first positive simultaneous optimization results in these settings.
Exploring the Scope of Unconstrained Via Minimization by Recursive Floorplan Bipartitioning
Venue: arXiv cs.OH 2018
Year: 2018

Random via failure is a major concern for post-fabrication reliability and poor manufacturing yield. A demanding solution to this problem is redundant via insertion during post-routing optimization. It becomes very critical when a multi-layer routing solution already incurs a large number of vias. Very few global routers addressed unconstrained via minimization (UVM) problem, while using minimal pattern routing and layer assignment of nets. It also includes a recent floorplan based early global routability assessment tool STAIRoute \cite{karb2}. This work addresses an early version of unconstrained via minimization problem during early global routing by identifying a set of minimal bend routing regions in any floorplan, by a new recursive bipartitioning framework. These regions facilitate monotone pattern routing of a set of nets in the floorplan by STAIRoute. The area/number balanced floorplan bipartitionining is a multi-objective optimization problem and known to be NP-hard \cite{majum2}. No existing approaches considered bend minimization as an objective and some of them incurred higher runtime overhead. In this paper, we present a Greedy as well as randomized neighbor search based staircase wave-front propagation methods for obtaining optimal bipartitioning results for minimal bend routing through multiple routing layers, for a balanced trade-off between routability, wirelength and congestion. Experiments were conducted on MCNC/GSRC floorplanning benchmarks for studying the variation of early via count obtained by STAIRoute for different values of the trade-off parameters ($γ, β$) in this multi-objective optimization problem, using $8$ metal layers. We studied the impact of ($γ, β$) values on each of the objectives as well as their linear combination function $Gain$ of these objectives.
Child Gender Determination with Convolutional Neural Networks on Hand Radio-Graphs
Venue: arXiv cs.CV 2018
Year: 2018

Motivation: In forensic or medico-legal investigation as well as in anthropology the gender determination of the subject (hit by a disastrous or any kind of traumatic situation) is mostly the first step. In state-of-the-art techniques the gender is determined by examining dimensions of the bones of skull and the pelvis area. In worse situations when there is only a small portion of the human remains to be investigated and the subject is a child, we need alternative techniques to determine the gender of the subject. In this work we propose a technique called GDCNN (Gender Determination with Convolutional Neural Networks), where the left hand radio-graphs of the children between a wide range of ages in 1 month to 18 years are examined to determine the gender. To our knowledge this technique is first of its kind. Further to identify the area of the attention we used Class Activation Mapping (CAM). Results: The results suggest the accuracy of the model is as high as 98%, which is very convincing by taking into account the incompletely grown skeleton of the children. The attention observed with CAM discovers that the lower part of the hand around carpals (wrist) is more important for child gender determination.
Gradient Harmonized Single-stage Detector
Venue: arXiv cs.CV 2018
Year: 2018

Despite the great success of two-stage detectors, single-stage detector is still a more elegant and efficient way, yet suffers from the two well-known disharmonies during training, i.e. the huge difference in quantity between positive and negative examples as well as between easy and hard examples. In this work, we first point out that the essential effect of the two disharmonies can be summarized in term of the gradient. Further, we propose a novel gradient harmonizing mechanism (GHM) to be a hedging for the disharmonies. The philosophy behind GHM can be easily embedded into both classification loss function like cross-entropy (CE) and regression loss function like smooth-$L_1$ ($SL_1$) loss. To this end, two novel loss functions called GHM-C and GHM-R are designed to balancing the gradient flow for anchor classification and bounding box refinement, respectively. Ablation study on MS COCO demonstrates that without laborious hyper-parameter tuning, both GHM-C and GHM-R can bring substantial improvement for single-stage detector. Without any whistles and bells, our model achieves 41.6 mAP on COCO test-dev set which surpasses the state-of-the-art method, Focal Loss (FL) + $SL_1$, by 0.8.
SVM-Based Sea-Surface Small Target Detection: A False-Alarm-Rate-Controllable Approach
Venue: arXiv cs.IT 2018
Year: 2018

In this letter, we consider the varying detection environments to address the problem of detecting small targets within sea clutter. We first extract three simple yet practically discriminative features from the returned signals in the time and frequency domains and then fuse them into a 3-D feature space. Based on the constructed space, we then adopt and elegantly modify the support vector machine (SVM) to design a learning-based detector that enfolds the false alarm rate (FAR). Most importantly, our proposed detector can flexibly control the FAR by simply adjusting two introduced parameters, which facilitates to regulate detector's sensitivity to the outliers incurred by the sea spikes and to fairly evaluate the performance of different detection algorithms. Experimental results demonstrate that our proposed detector significantly improves the detection probability over several existing classical detectors in both low signal to clutter ratio (SCR) (up to 58%) and low FAR (up to 40%) cases.
A conjugate prior for the Dirichlet distribution
Venue: arXiv cs.LG 2018
Year: 2018

This note investigates a conjugate class for the Dirichlet distribution class in the exponential family.
Self-Supervised Learning of Depth and Camera Motion from 360° Videos
Venue: arXiv cs.CV 2018
Year: 2018

As 360° cameras become prevalent in many autonomous systems (e.g., self-driving cars and drones), efficient 360° perception becomes more and more important. We propose a novel self-supervised learning approach for predicting the omnidirectional depth and camera motion from a 360° video. In particular, starting from the SfMLearner, which is designed for cameras with normal field-of-view, we introduce three key features to process 360° images efficiently. Firstly, we convert each image from equirectangular projection to cubic projection in order to avoid image distortion. In each network layer, we use Cube Padding (CP), which pads intermediate features from adjacent faces, to avoid image boundaries. Secondly, we propose a novel "spherical" photometric consistency constraint on the whole viewing sphere. In this way, no pixel will be projected outside the image boundary which typically happens in images with normal field-of-view. Finally, rather than naively estimating six independent camera motions (i.e., naively applying SfM-Learner to each face on a cube), we propose a novel camera pose consistency loss to ensure the estimated camera motions reaching consensus. To train and evaluate our approach, we collect a new PanoSUNCG dataset containing a large amount of 360° videos with groundtruth depth and camera motion. Our approach achieves state-of-the-art depth prediction and camera motion estimation on PanoSUNCG with faster inference speed comparing to equirectangular. In real-world indoor videos, our approach can also achieve qualitatively reasonable depth prediction by acquiring model pre-trained on PanoSUNCG.
Robustness of the Closest Unstable Equilibrium Point Along a P-V Curve
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we study numerically the behavior of the closest unstable equilibrium point (UEP) on the stability boundary of a stable equilibrium point (SEP) of a post-switching power system along a P-V curve. Using the structure-preserving model of the WSCC 9-bus 3-machine system, we show that along the load curve, the closest UEP can switch to a new UEP. We also show that the stability region of the post-switching SEP can expand and contract as the load moves towards the nose point of the P-V curve. Our numerical results also show the impact of the direction of movement of the closest UEP on the size and shape of the stability region of a SEP.
Personal Names Popularity Estimation and its Application to Record Linkage
Venue: arXiv cs.DB 2018
Year: 2018

This study deals with a fairly simply formulated problem -- how to estimate the number of people bearing the same full name in a large population. Estimation of name popularity can leverage personal name matching in databases and be of interest for many other domains. A distinctive feature of large collections of names is that they contain a large number of unique items, which is challenging for statistical modeling. We investigate a number of statistical techniques and also propose a simple yet effective method aimed at obtaining more accurate count estimates. In our experiments we use a dataset containing about 20 million name occurrences that correspond to about 13 million real-world persons. We perform a thorough evaluation of the name count estimation methods and a record linkage experiment guided by name popularity estimates. Obtained results suggest that theoretically informed approaches outperform simple heuristics and can be useful in a variety of applications.
Autonomic Intrusion Response in Distributed Computing using Big Data
Venue: arXiv cs.DC 2018
Year: 2018

We introduce a method for Intrusion Detection based on the classification, understanding and prediction of behavioural deviance and potential threats, issuing recommendations, and acting to address eminent issues. Our work seeks a practical solutions to automate the process of identification and response to Cybersecurity threats in hybrid Distributed Computing environments through the analysis of large datasets generated during operations. We are motivated by the growth in utilisation of Cloud Computing and Edge Computing as the technology for business and social solutions. The technology mix and complex operation render these environments target to attacks like hijacking, man-in-the-middle, denial of service, phishing, and others. The Autonomous Intrusion Response System implements innovative models of data analysis and context-aware recommendation systems to respond to attacks and self-healing. We introduce a proof-of-concept implementation and evaluate against datasets from experimentation scenarios based on public and private clouds. The results present significant improvement in response effectiveness and potential to scale to large environments.
ATENSOR - REDUCE program for tensor simplification
Venue: arXiv cs.SC 2018
Year: 2018

The paper presents a REDUCE program for the simplification of tensor expressions that are considered as formal indexed objects. The proposed algorithm is based on the consideration of tensor expressions as vectors in some linear space. This linear space is formed by all the elements of the group algebra of the corresponding tensor expression. Such approach permits us to simplify the tensor expressions possessing symmetry properties, summation (dummy) indices and multiterm identities by unify manner. The canonical element for the tensor expression is defined in terms of the basic vectors of this linear space. The main restriction of the algorithm is the dimension of the linear space that is equal to N!, where N is a number of indices of the tensor expression. The program uses REDUCE as user interface.
Very Hard Electoral Control Problems
Venue: arXiv cs.GT 2018
Year: 2018

It is important to understand how the outcome of an election can be modified by an agent with control over the structure of the election. Electoral control has been studied for many election systems, but for all studied systems the winner problem is in P, and so control is in NP. There are election systems, such as Kemeny, that have many desirable properties, but whose winner problems are not in NP. Thus for such systems control is not in NP, and in fact we show that it is typically complete for $Σ_2^p$ (i.e., ${\rm NP}^{\rm NP}$, the second level of the polynomial hierarchy). This is a very high level of complexity. Approaches that perform quite well for solving NP problems do not necessarily work for $Σ_2^p$-complete problems. However, answer set programming is suited to express problems in $Σ_2^p$, and we present an encoding for Kemeny control.
QDB: From Quantum Algorithms Towards Correct Quantum Programs
Venue: arXiv cs.PL 2018
Year: 2018

With the advent of small-scale prototype quantum computers, researchers can now code and run quantum algorithms that were previously proposed but not fully implemented. In support of this growing interest in quantum computing experimentation, programmers need new tools and techniques to write and debug QC code. In this work, we implement a range of QC algorithms and programs in order to discover what types of bugs occur and what defenses against those bugs are possible in QC programs. We conduct our study by running small-sized QC programs in QC simulators in order to replicate published results in QC implementations. Where possible, we cross-validate results from programs written in different QC languages for the same problems and inputs. Drawing on this experience, we provide a taxonomy for QC bugs, and we propose QC language features that would aid in writing correct code.
Deep Q learning for fooling neural networks
Venue: arXiv cs.LG 2018
Year: 2018

Deep learning models are vulnerable to external attacks. In this paper, we propose a Reinforcement Learning (RL) based approach to generate adversarial examples for the pre-trained (target) models. We assume a semi black-box setting where the only access an adversary has to the target model is the class probabilities obtained for the input queries. We train a Deep Q Network (DQN) agent which, with experience, learns to attack only a small portion of image pixels to generate non-targeted adversarial images. Initially, an agent explores an environment by sequentially modifying random sets of image pixels and observes its effect on the class probabilities. At the end of an episode, it receives a positive (negative) reward if it succeeds (fails) to alter the label of the image. Experimental results with MNIST, CIFAR-10 and Imagenet datasets demonstrate that our RL framework is able to learn an effective attack policy.
Staging Human-computer Dialogs: An Application of the Futamura Projections
Venue: arXiv cs.PL 2018
Year: 2018

We demonstrate an application of the Futamura Projections to human-computer interaction, and particularly to staging human-computer dialogs. Specifically, by providing staging analogs to the classical Futamura Projections, we demonstrate that the Futamura Projections can be applied to the staging of human-computer dialogs in addition to the execution of programs.
Neural Wavetable: a playable wavetable synthesizer using neural networks
Venue: arXiv cs.SD 2018
Year: 2018

We present Neural Wavetable, a proof-of-concept wavetable synthesizer that uses neural networks to generate playable wavetables. The system can produce new, distinct waveforms through the interpolation of traditional wavetables in an autoencoder's latent space. It is available as a VST/AU plugin for use in a Digital Audio Workstation.
Emergence of Addictive Behaviors in Reinforcement Learning Agents
Venue: arXiv cs.LG 2018
Year: 2018

This paper presents a novel approach to the technical analysis of wireheading in intelligent agents. Inspired by the natural analogues of wireheading and their prevalent manifestations, we propose the modeling of such phenomenon in Reinforcement Learning (RL) agents as psychological disorders. In a preliminary step towards evaluating this proposal, we study the feasibility and dynamics of emergent addictive policies in Q-learning agents in the tractable environment of the game of Snake. We consider a slightly modified settings for this game, in which the environment provides a "drug" seed alongside the original "healthy" seed for the consumption of the snake. We adopt and extend an RL-based model of natural addiction to Q-learning agents in this settings, and derive sufficient parametric conditions for the emergence of addictive behaviors in such agents. Furthermore, we evaluate our theoretical analysis with three sets of simulation-based experiments. The results demonstrate the feasibility of addictive wireheading in RL agents, and provide promising venues of further research on the psychopathological modeling of complex AI safety problems.
Submodular Optimization Over Streams with Inhomogeneous Decays
Venue: arXiv cs.DS 2018
Year: 2018

Cardinality constrained submodular function maximization, which aims to select a subset of size at most $k$ to maximize a monotone submodular utility function, is the key in many data mining and machine learning applications such as data summarization and maximum coverage problems. When data is given as a stream, streaming submodular optimization (SSO) techniques are desired. Existing SSO techniques can only apply to insertion-only streams where each element has an infinite lifespan, and sliding-window streams where each element has a same lifespan (i.e., window size). However, elements in some data streams may have arbitrary different lifespans, and this requires addressing SSO over streams with inhomogeneous-decays (SSO-ID). This work formulates the SSO-ID problem and presents three algorithms: BasicStreaming is a basic streaming algorithm that achieves an $(1/2-ε)$ approximation factor; HistApprox improves the efficiency significantly and achieves an $(1/3-ε)$ approximation factor; HistStreaming is a streaming version of HistApprox and uses heuristics to further improve the efficiency. Experiments conducted on real data demonstrate that HistStreaming can find high quality solutions and is up to two orders of magnitude faster than the naive Greedy algorithm.
Efficient and Scalable Multi-task Regression on Massive Number of Tasks
Venue: arXiv cs.LG 2018
Year: 2018

Many real-world large-scale regression problems can be formulated as Multi-task Learning (MTL) problems with a massive number of tasks, as in retail and transportation domains. However, existing MTL methods still fail to offer both the generalization performance and the scalability for such problems. Scaling up MTL methods to problems with a tremendous number of tasks is a big challenge. Here, we propose a novel algorithm, named Convex Clustering Multi-Task regression Learning (CCMTL), which integrates with convex clustering on the k-nearest neighbor graph of the prediction models. Further, CCMTL efficiently solves the underlying convex problem with a newly proposed optimization method. CCMTL is accurate, efficient to train, and empirically scales linearly in the number of tasks. On both synthetic and real-world datasets, the proposed CCMTL outperforms seven state-of-the-art (SoA) multi-task learning methods in terms of prediction accuracy as well as computational efficiency. On a real-world retail dataset with 23,812 tasks, CCMTL requires only around 30 seconds to train on a single thread, while the SoA methods need up to hours or even days.