OpenRaiser/Intern-Atlas huggingface dataset:
Sharper Bounds for Regularized Data Fitting
Venue: arXiv cs.DS 2017
Year: 2017

We study matrix sketching methods for regularized variants of linear regression, low rank approximation, and canonical correlation analysis. Our main focus is on sketching techniques which preserve the objective function value for regularized problems, which is an area that has remained largely unexplored. We study regularization both in a fairly broad setting, and in the specific context of the popular and widely used technique of ridge regularization; for the latter, as applied to each of these problems, we show algorithmic resource bounds in which the {\em statistical dimension} appears in places where in previous bounds the rank would appear. The statistical dimension is always smaller than the rank, and decreases as the amount of regularization increases. In particular, for the ridge low-rank approximation problem $\min_{Y,X} \lVert YX - A \rVert_F^2 + λ\lVert Y\rVert_F^2 + λ\lVert X \rVert_F^2$, where $Y\in\mathbb{R}^{n\times k}$ and $X\in\mathbb{R}^{k\times d}$, we give an approximation algorithm needing \[ O(\mathtt{nnz}(A)) + \tilde{O}((n+d)\varepsilon^{-1}k \min\{k, \varepsilon^{-1}\mathtt{sd}_λ(Y^*)\})+ \mathtt{poly}(\mathtt{sd}_λ(Y^*) \varepsilon^{-1}) \] time, where $s_λ(Y^*)\le k$ is the statistical dimension of $Y^*$, $Y^*$ is an optimal $Y$, $\varepsilon$ is an error parameter, and $\mathtt{nnz}(A)$ is the number of nonzero entries of $A$.This is faster than prior work, even when $λ=0$. We also study regularization in a much more general setting. For example, we obtain sketching-based algorithms for the low-rank approximation problem $\min_{X,Y} \lVert YX - A \rVert_F^2 + f(Y,X)$ where $f(\cdot,\cdot)$ is a regularizing function satisfying some very general conditions (chiefly, invariance under orthogonal transformations).
Large-scale JPEG steganalysis using hybrid deep-learning framework
Venue: arXiv cs.MM 2017
Year: 2017

Adoption of deep learning in image steganalysis is still in its initial stage. In this paper we propose a generic hybrid deep-learning framework for JPEG steganalysis incorporating the domain knowledge behind rich steganalytic models. Our proposed framework involves two main stages. The first stage is hand-crafted, corresponding to the convolution phase and the quantization & truncation phase of the rich models. The second stage is a compound deep neural network containing multiple deep subnets in which the model parameters are learned in the training procedure. We provided experimental evidences and theoretical reflections to argue that the introduction of threshold quantizers, though disable the gradient-descent-based learning of the bottom convolution phase, is indeed cost-effective. We have conducted extensive experiments on a large-scale dataset extracted from ImageNet. The primary dataset used in our experiments contains 500,000 cover images, while our largest dataset contains five million cover images. Our experiments show that the integration of quantization and truncation into deep-learning steganalyzers do boost the detection performance by a clear margin. Furthermore, we demonstrate that our framework is insensitive to JPEG blocking artifact alterations, and the learned model can be easily transferred to a different attacking target and even a different dataset. These properties are of critical importance in practical applications.
Construction Inspection through Spatial Database
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents a novel pipeline for development of an efficient set of tools for extracting information from the video of a structure, captured by an Unmanned Aircraft System (UAS) to produce as-built documentation to aid inspection of large multi-storied building during construction. Our system uses the output from a Simultaneous Localization and Mapping system and a 3D CAD model of the structure in order to construct a spatial database to store images into the 3D CAD model space. This allows the user to perform a spatial query for images through spatial indexing into the 3D CAD model space. The image returned by the spatial query is used to extract metric information. The spatial database is also used to generate a 3D textured model which provides a visual as-built documentation.
Diminishable Parameterized Problems and Strict Polynomial Kernelization
Venue: arXiv cs.CC 2017
Year: 2017

Kernelization---a mathematical key concept for provably effective polynomial-time preprocessing of NP-hard problems---plays a central role in parameterized complexity and has triggered an extensive line of research. This is in part due to a lower bounds framework that allows to exclude polynomial-size kernels under the assumption of NP $\nsubseteq$ coNP$/$poly. In this paper we consider a restricted yet natural variant of kernelization, namely strict kernelization, where one is not allowed to increase the parameter of the reduced instance (the kernel) by more than an additive constant. Building on earlier work of Chen, Flum, and Müller [Theory Comput. Syst. 2011] and developing a general and remarkably simple framework, we show that a variety of FPT problems does not admit strict polynomial kernels under the weaker assumption of P $\neq$ NP. In particular, we show that various (multicolored) graph problems and Turing machine computation problems do not admit strict polynomial kernels unless P $=$ NP. To this end, a key concept we use are diminishable problems; these are parameterized problems that allow to decrease the parameter of the input instance by at least one in polynomial time, thereby outputting an equivalent problem instance. Finally, we study a relaxation of the notion of strict kernels and reveal its limitations.
Help, It Looks Confusing: GUI Task Automation Through Demonstration and Follow-up Questions
Venue: arXiv cs.HC 2017
Year: 2017

Non-programming users should be able to create their own customized scripts to perform computer-based tasks for them, just by demonstrating to the machine how it's done. To that end, we develop a system prototype which learns-by-demonstration called HILC (Help, It Looks Confusing). Users train HILC to synthesize a task script by demonstrating the task, which produces the needed screenshots and their corresponding mouse-keyboard signals. After the demonstration, the user answers follow-up questions. We propose a user-in-the-loop framework that learns to generate scripts of actions performed on visible elements of graphical applications. While pure programming-by-demonstration is still unrealistic, we use quantitative and qualitative experiments to show that non-programming users are willing and effective at answering follow-up queries posed by our system. Our models of events and appearance are surprisingly simple, but are combined effectively to cope with varying amounts of supervision. The best available baseline, Sikuli Slides, struggled with the majority of the tests in our user study experiments. The prototype with our proposed approach successfully helped users accomplish simple linear tasks, complicated tasks (monitoring, looping, and mixed), and tasks that span across multiple executables. Even when both systems could ultimately perform a task, ours was trained and refined by the user in less time.
Anomaly Detection in the Bitcoin System - A Network Perspective
Venue: arXiv cs.SI 2017
Year: 2017

The problem of anomaly detection has been studied for a long time, and many Network Analysis techniques have been proposed as solutions. Although some results appear to be quite promising, no method is clearly to be superior to the rest. In this paper, we particularly consider anomaly detection in the Bitcoin transaction network. Our goal is to detect which users and transactions are the most suspicious; in this case, anomalous behavior is a proxy for suspicious behavior. To this end, we use the laws of power degree and densification and local outlier factor (LOF) method (which is proceeded by k-means clustering method) on two graphs generated by the Bitcoin transaction network: one graph has users as nodes, and the other has transactions as nodes. We remark that the methods used here can be applied to any type of setting with an inherent graph structure, including, but not limited to, computer networks, telecommunications networks, auction networks, security networks, social networks, Web networks, or any financial networks. We use the Bitcoin transaction network in this paper due to the availability, size, and attractiveness of the data set.
Responses to Critiques on Machine Learning of Criminality Perceptions (Addendum of arXiv:1611.04135)
Venue: arXiv cs.CV 2017
Year: 2017

In November 2016 we submitted to arXiv our paper "Automated Inference on Criminality Using Face Images". It generated a great deal of discussions in the Internet and some media outlets. Our work is only intended for pure academic discussions; how it has become a media consumption is a total surprise to us. Although in agreement with our critics on the need and importance of policing AI research for the general good of the society, we are deeply baffled by the ways some of them mispresented our work, in particular the motive and objective of our research.
Self-Calibration and Bilinear Inverse Problems via Linear Least Squares
Venue: arXiv cs.IT 2017
Year: 2017

Whenever we use devices to take measurements, calibration is indispensable. While the purpose of calibration is to reduce bias and uncertainty in the measurements, it can be quite difficult, expensive, and sometimes even impossible to implement. We study a challenging problem called \emph{self-calibration}, i.e., the task of designing an algorithm for devices so that the algorithm is able to perform calibration automatically. More precisely, we consider the setup $\boldsymbol{y} = \mathcal{A}(\boldsymbol{d}) \boldsymbol{x} + \boldsymbolε$ where only partial information about the sensing matrix $\mathcal{A}(\boldsymbol{d})$ is known and where $\mathcal{A}(\boldsymbol{d})$ linearly depends on $\boldsymbol{d}$. The goal is to estimate the calibration parameter $\boldsymbol{d}$ (resolve the uncertainty in the sensing process) and the signal/object of interests $\boldsymbol{x}$ simultaneously. For three different models of practical relevance, we show how such a \emph{bilinear} inverse problem, including blind deconvolution as an important example, can be solved via a simple \emph{linear least squares} approach. As a consequence, the proposed algorithms are numerically extremely efficient, thus potentially allowing for real-time deployment. We also present a variation of the least squares approach, which leads to a~\emph{spectral method}, where the solution to the bilinear inverse problem can be found by computing the singular vector associated with the smallest singular value of a certain matrix derived from the bilinear system. Explicit theoretical guarantees and stability theory are derived for both techniques; and the number of sampling complexity is nearly optimal (up to a poly-log factor). Applications in imaging sciences and signal processing are discussed and numerical simulations are presented to demonstrate the effectiveness and efficiency of our approach.
Uncertain Graph Sparsification
Venue: arXiv cs.DS 2017
Year: 2017

Uncertain graphs are prevalent in several applications including communications systems, biological databases and social networks. The ever increasing size of the underlying data renders both graph storage and query processing extremely expensive. Sparsification has often been used to reduce the size of deterministic graphs by maintaining only the important edges. However, adaptation of deterministic sparsification methods fails in the uncertain setting. To overcome this problem, we introduce the first sparsification techniques aimed explicitly at uncertain graphs. The proposed methods reduce the number of edges and redistribute their probabilities in order to decrease the graph size, while preserving its underlying structure. The resulting graph can be used to efficiently and accurately approximate any query and mining tasks on the original graph. An extensive experimental evaluation with real and synthetic datasets illustrates the effectiveness of our techniques on several common graph tasks, including clustering coefficient, page rank, reliability and shortest path distance.
Similarity Search Combining Query Relaxation and Diversification
Venue: arXiv cs.DB 2017
Year: 2017

We study the similarity search problem which aims to find the similar query results according to a set of given data and a query string. To balance the result number and result quality, we combine query result diversity with query relaxation. Relaxation guarantees the number of the query results, returning more relevant elements to the query if the results are too few, while the diversity tries to reduce the similarity among the returned results. By making a trade-off of similarity and diversity, we improve the user experience. To achieve this goal, we define a novel goal function combining similarity and diversity. Aiming at this goal, we propose three algorithms. Among them, algorithms genGreedy and genCluster perform relaxation first and select part of the candidates to diversify. The third algorithm CB2S splits the dataset into smaller pieces using the clustering algorithm of k-means and processes queries in several small sets to retrieve more diverse results. The balance of similarity and diversity is determined through setting a threshold, which has a default value and can be adjusted according to users' preference. The performance and efficiency of our system are demonstrated through extensive experiments based on various datasets.
A Neural Architecture Mimicking Humans End-to-End for Natural Language Inference
Venue: arXiv cs.CL 2017
Year: 2017

In this work we use the recent advances in representation learning to propose a neural architecture for the problem of natural language inference. Our approach is aligned to mimic how a human does the natural language inference process given two statements. The model uses variants of Long Short Term Memory (LSTM), attention mechanism and composable neural networks, to carry out the task. Each part of our model can be mapped to a clear functionality humans do for carrying out the overall task of natural language inference. The model is end-to-end differentiable enabling training by stochastic gradient descent. On Stanford Natural Language Inference(SNLI) dataset, the proposed model achieves better accuracy numbers than all published models in literature.
Quantitative Entropy Study of Language Complexity
Venue: arXiv cs.CL 2017
Year: 2017

We study the entropy of Chinese and English texts, based on characters in case of Chinese texts and based on words for both languages. Significant differences are found between the languages and between different personal styles of debating partners. The entropy analysis points in the direction of lower entropy, that is of higher complexity. Such a text analysis would be applied for individuals of different styles, a single individual at different age, as well as different groups of the population.
HPAT: High Performance Analytics with Scripting Ease-of-Use
Venue: arXiv cs.DC 2017
Year: 2017

Big data analytics requires high programmer productivity and high performance simultaneously on large-scale clusters. However, current big data analytics frameworks (e.g. Apache Spark) have prohibitive runtime overheads since they are library-based. We introduce a novel auto-parallelizing compiler approach that exploits the characteristics of the data analytics domain such as the map/reduce parallel pattern and is robust, unlike previous auto-parallelization methods. Using this approach, we build High Performance Analytics Toolkit (HPAT), which parallelizes high-level scripting (Julia) programs automatically, generates efficient MPI/C++ code, and provides resiliency. Furthermore, it provides automatic optimizations for scripting programs, such as fusion of array operations. Thus, HPAT is 369x to 2033x faster than Spark on the Cori supercomputer and 20x to 256x times on Amazon AWS.
Locomotion of the generalized Purcell's swimmer : Modelling, controllability and motion primitives
Venue: arXiv cs.RO 2017
Year: 2017

Micro-robotics at low Reynolds number has been a growing area of research over the past decade. We propose and study a generalized 3-link robotic swimmer inspired by the planar Purcell's swimmer. By incorporating out-of-plane motion of the outer limbs, this mechanism generalizes the planar Purcell's swimmer, which has been widely studied in the literature. Such an evolution of the limbs' motion results in the swimmer's base link evolving in a 3-dimensional space. The swimmer's configuration space admits a trivial principal fiber bundle structure, which along with the slender body theory at the low Reynolds number regime, facilitates in obtaining a principal kinematic form of the equations. We derive a coordinate-free expression for the local form of the kinematic connection. A novel approach for local controllability analysis of this 3-dimensional swimmer in the low Reynolds number regime is presented by employing the controllability results of the planar Purcell's swimmer. This is followed by control synthesis using the motion primitives approach. We prove the existence of motion primitives based control sequence for maneuvering the swimmer's base link whose motion evolves on a Lie group. Using the principal fiber bundle structure, an algorithm for point to point reconfiguration of the swimmer is presented. A set of control sequences for translational and rotational maneuvers is then provided along with numerical simulations.
Graph Learning from Data under Structural and Laplacian Constraints
Venue: arXiv cs.LG 2017
Year: 2017

Graphs are fundamental mathematical structures used in various fields to represent data, signals and processes. In this paper, we propose a novel framework for learning/estimating graphs from data. The proposed framework includes (i) formulation of various graph learning problems, (ii) their probabilistic interpretations and (iii) associated algorithms. Specifically, graph learning problems are posed as estimation of graph Laplacian matrices from some observed data under given structural constraints (e.g., graph connectivity and sparsity level). From a probabilistic perspective, the problems of interest correspond to maximum a posteriori (MAP) parameter estimation of Gaussian-Markov random field (GMRF) models, whose precision (inverse covariance) is a graph Laplacian matrix. For the proposed graph learning problems, specialized algorithms are developed by incorporating the graph Laplacian and structural constraints. The experimental results demonstrate that the proposed algorithms outperform the current state-of-the-art methods in terms of accuracy and computational efficiency.
Bayesian optimization of hyper-parameters in reservoir computing
Venue: arXiv cs.LG 2017
Year: 2017

We describe a method for searching the optimal hyper-parameters in reservoir computing, which consists of a Gaussian process with Bayesian optimization. It provides an alternative to other frequently used optimization methods such as grid, random, or manual search. In addition to a set of optimal hyper-parameters, the method also provides a probability distribution of the cost function as a function of the hyper-parameters. We apply this method to two types of reservoirs: nonlinear delay nodes and echo state networks. It shows excellent performance on all considered benchmarks, either matching or significantly surpassing results found in the literature. In general, the algorithm achieves optimal results in fewer iterations when compared to other optimization methods. We have optimized up to six hyper-parameters simultaneously, which would have been infeasible using, e.g., grid search. Due to its automated nature, this method significantly reduces the need for expert knowledge when optimizing the hyper-parameters in reservoir computing. Existing software libraries for Bayesian optimization, such as Spearmint, make the implementation of the algorithm straightforward. A fork of the Spearmint framework along with a tutorial on how to use it in practice is available at https://bitbucket.org/uhasseltmachinelearning/spearmint/
Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space
Venue: arXiv cs.IT 2017
Year: 2017

We consider faithfully combining phase retrieval with classical compressed sensing. Inspired by the recent novel formulation for phase retrieval called PhaseMax, we present and analyze SparsePhaseMax, a linear program for phaseless compressed sensing in the natural parameter space. We establish that when provided with an initialization that correlates with an arbitrary $k$-sparse $n$-vector, SparsePhaseMax recovers this vector up to global sign with high probability from $O(k \log \frac{n}{k})$ magnitude measurements against i.i.d. Gaussian random vectors. Our proof of this fact exploits a curious newfound connection between phaseless and 1-bit compressed sensing. This is the first result to establish bootstrapped compressed sensing from phaseless Gaussian measurements under optimal sample complexity.
Multi-Scale Saliency Detection using Dictionary Learning
Venue: arXiv cs.CV 2017
Year: 2017

Saliency detection has drawn a lot of attention of researchers in various fields over the past several years. Saliency is the perceptual quality that makes an object, person to draw the attention of humans at the very sight. Salient object detection in an image has been used centrally in many computational photography and computer vision applications like video compression, object recognition and classification, object segmentation, adaptive content delivery, motion detection, content aware resizing, camouflage images and change blindness images to name a few. We propose a method to detect saliency in the objects using multimodal dictionary learning which has been recently used in classification and image fusion. The multimodal dictionary that we are learning is task driven which gives improved performance over its counterpart (the one which is not task specific).
Beyond Deep Residual Learning for Image Restoration: Persistent Homology-Guided Manifold Simplification
Venue: arXiv cs.CV 2017
Year: 2017

The latest deep learning approaches perform better than the state-of-the-art signal processing approaches in various image restoration tasks. However, if an image contains many patterns and structures, the performance of these CNNs is still inferior. To address this issue, here we propose a novel feature space deep residual learning algorithm that outperforms the existing residual learning. The main idea is originated from the observation that the performance of a learning algorithm can be improved if the input and/or label manifolds can be made topologically simpler by an analytic mapping to a feature space. Our extensive numerical studies using denoising experiments and NTIRE single-image super-resolution (SISR) competition demonstrate that the proposed feature space residual learning outperforms the existing state-of-the-art approaches. Moreover, our algorithm was ranked third in NTIRE competition with 5-10 times faster computational time compared to the top ranked teams. The source code is available on page : https://github.com/iorism/CNN.git