OpenRaiser/Intern-Atlas huggingface dataset:
Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reduction
Venue: arXiv cs.LG 2016
Year: 2016

Zeroth-order (derivative-free) optimization attracts a lot of attention in machine learning, because explicit gradient calculations may be computationally expensive or infeasible. To handle large scale problems both in volume and dimension, recently asynchronous doubly stochastic zeroth-order algorithms were proposed. The convergence rate of existing asynchronous doubly stochastic zeroth order algorithms is $O(\frac{1}{\sqrt{T}})$ (also for the sequential stochastic zeroth-order optimization algorithms). In this paper, we focus on the finite sums of smooth but not necessarily convex functions, and propose an asynchronous doubly stochastic zeroth-order optimization algorithm using the accelerated technology of variance reduction (AsyDSZOVR). Rigorous theoretical analysis show that the convergence rate can be improved from $O(\frac{1}{\sqrt{T}})$ the best result of existing algorithms to $O(\frac{1}{T})$. Also our theoretical results is an improvement to the ones of the sequential stochastic zeroth-order optimization algorithms.
Inspiration or Preparation? Explaining Creativity in Scientific Enterprise
Venue: arXiv cs.SI 2016
Year: 2016

Human creativity is the ultimate driving force behind scientific progress. While the building blocks of innovations are often embodied in existing knowledge, it is creativity that blends seemingly disparate ideas. Existing studies have made striding advances in quantifying creativity of scientific publications by investigating their citation relationships. Yet, little is known hitherto about the underlying mechanisms governing scientific creative processes, largely due to that a paper's references, at best, only partially reflect its authors' actual information consumption. This work represents an initial step towards fine-grained understanding of creative processes in scientific enterprise. In specific, using two web-scale longitudinal datasets (120.1 million papers and 53.5 billion web requests spanning 4 years), we directly contrast authors' information consumption behaviors against their knowledge products. We find that, of 59.0\% papers across all scientific fields, 25.7\% of their creativity can be readily explained by information consumed by their authors. Further, by leveraging these findings, we develop a predictive framework that accurately identifies the most critical knowledge to fostering target scientific innovations. We believe that our framework is of fundamental importance to the study of scientific creativity. It promotes strategies to stimulate and potentially automate creative processes, and provides insights towards more effective designs of information recommendation platforms.
ImageNet pre-trained models with batch normalization
Venue: arXiv cs.CV 2016
Year: 2016

Convolutional neural networks (CNN) pre-trained on ImageNet are the backbone of most state-of-the-art approaches. In this paper, we present a new set of pre-trained models with popular state-of-the-art architectures for the Caffe framework. The first release includes Residual Networks (ResNets) with generation script as well as the batch-normalization-variants of AlexNet and VGG19. All models outperform previous models with the same architecture. The models and training code are available at http://www.inf-cv.uni-jena.de/Research/CNN+Models.html and https://github.com/cvjena/cnn-models
Improving the Performance of Neural Networks in Regression Tasks Using Drawering
Venue: arXiv cs.LG 2016
Year: 2016

The method presented extends a given regression neural network to make its performance improve. The modification affects the learning procedure only, hence the extension may be easily omitted during evaluation without any change in prediction. It means that the modified model may be evaluated as quickly as the original one but tends to perform better. This improvement is possible because the modification gives better expressive power, provides better behaved gradients and works as a regularization. The knowledge gained by the temporarily extended neural network is contained in the parameters shared with the original neural network. The only cost is an increase in learning time.
Object Classification with Joint Projection and Low-rank Dictionary Learning
Venue: arXiv cs.CV 2016
Year: 2016

For an object classification system, the most critical obstacles towards real-world applications are often caused by large intra-class variability, arising from different lightings, occlusion and corruption, in limited sample sets. Most methods in the literature would fail when the training samples are heavily occluded, corrupted or have significant illumination or viewpoint variations. Besides, most of the existing methods and especially deep learning-based methods, need large training sets to achieve a satisfactory recognition performance. Although using the pre-trained network on a generic large-scale dataset and fine-tune it to the small-sized target dataset is a widely used technique, this would not help when the content of base and target datasets are very different. To address these issues, we propose a joint projection and low-rank dictionary learning method using dual graph constraints (JP-LRDL). The proposed joint learning method would enable us to learn the features on top of which dictionaries can be better learned, from the data with large intra-class variability. Specifically, a structured class-specific dictionary is learned and the discrimination is further improved by imposing a graph constraint on the coding coefficients, that maximizes the intra-class compactness and inter-class separability. We also enforce low-rank and structural incoherence constraints on sub-dictionaries to make them more compact and robust to variations and outliers and reduce the redundancy among them, respectively. To preserve the intrinsic structure of data and penalize unfavourable relationship among training samples simultaneously, we introduce a projection graph into the framework, which significantly enhances the discriminative ability of the projection matrix and makes the method robust to small-sized and high-dimensional datasets.
Study of shoplifting prevention using image analysis and ERP check
Venue: arXiv cs.DC 2016
Year: 2016

In this paper, we propose a SaaS service which prevents shoplifting using image analysis and ERP. In Japan, total damage of shoplifting reaches 450 billion yen and more than 1000 small shops gave up their businesses because of shoplifting. Based on recent cloud technology and data analysis technology, we propose a shoplifting prevention service with image analysis of security camera and ERP data check for small shops. We evaluated stream analysis of security camera movie using online machine learining framework Jubatus.
Throughput-Optimal Load Balancing for Intra Datacenter Networks
Venue: arXiv cs.NI 2016
Year: 2016

Traffic load-balancing in datacenters alleviates hot spots and improves network utilization. In this paper, a stable in-network load-balancing algorithm is developed in the setting of software-defined networking. A control plane configures a data plane over successive intervals of time. While the MaxWeight algorithm can be applied in this setting and offers certain throughput optimality properties, its bang-bang control structure rewards single flows on each interval and prohibits link-capacity sharing. This paper develops a new algorithm that is throughput-optimal and allows link-capacity sharing, leading to low queue occupancy. The algorithm deliberately imitates weighted fair queueing, which provides fairness and graceful interaction with TCP traffic. Inspired by insights from the analysis, a heuristic improvement is also developed to operate with practical switches and TCP flows. Simulations from a network simulator shows that the algorithm outperforms the widely-used equal-cost multipath (ECMP) technique.
Design and Evaluation of Alternate Enumeration Techniques for Subset Sum Problem
Venue: arXiv cs.DS 2016
Year: 2016

The subset sum problem, also referred as SSP, is a NP-Hard computational problem. SSP has its applications in broad domains like cryptography, number theory, operation research and complexity theory. The most famous algorithm for solving SSP is Backtracking Algorithm which has exponential time complexity. Therefore, our goal is to design and develop better alternate enumeration techniques for faster generation of SSP solutions. Given the set of first n natural numbers which is denoted by Xn and a target sum S, we propose various alternate enumeration techniques which find all the subsets of Xn that add up to sum S. In this paper, we present the mathematics behind this exponential problem. We analyze the distribution of power set of Xn and present formulas which show definite patterns and relations among these subsets. We introduce three major distributions for power set of Xn: Sum Distribution, Length-Sum Distribution and Element Distribution. These distributions are prepossessing procedures for various alternate enumeration techniques for solving SSP. We propose novel algorithms: Subset Generation using Sum Distribution, Subset Generation using Length-Sum Distribution, Basic Bucket Algorithm, Maximum and Minimum Frequency Driven Bucket Algorithms and Local Search using Maximal and Minimal Subsets for enumerating SSP. We compare the performance of these approaches against the traditional backtracking algorithm. The efficiency and effectiveness of these algorithms are presented with the help of these experimental results. Furthermore, we studied the over solution set of subsets generated by various algorithms to get the complete solution for subset sum problem. Finally, we present a conjecture about upper bound on the number of subsets that has to be enumerated to get all solutions for Subset Sum Problem.
Coactive Critiquing: Elicitation of Preferences and Features
Venue: arXiv cs.AI 2016
Year: 2016

When faced with complex choices, users refine their own preference criteria as they explore the catalogue of options. In this paper we propose an approach to preference elicitation suited for this scenario. We extend Coactive Learning, which iteratively collects manipulative feedback, to optionally query example critiques. User critiques are integrated into the learning model by dynamically extending the feature space. Our formulation natively supports constructive learning tasks, where the option catalogue is generated on-the-fly. We present an upper bound on the average regret suffered by the learner. Our empirical analysis highlights the promise of our approach.
On the Minimum Chordal Completion Polytope
Venue: arXiv cs.DS 2016
Year: 2016

A graph is chordal if every cycle of length at least four contains a chord, that is, an edge connecting two nonconsecutive vertices of the cycle. Several classical applications in sparse linear systems, database management, computer vision, and semidefinite programming can be reduced to finding the minimum number of edges to add to a graph so that it becomes chordal, known as the minimum chordal completion problem (MCCP). In this article we propose a new formulation for the MCCP which does not rely on finding perfect elimination orderings of the graph, as has been considered in previous work. We introduce several families of facet-defining inequalities for cycle subgraphs and investigate the underlying separation problems, showing that some key inequalities are NP-Hard to separate. We also show general properties of the proposed polyhedra, indicating certain conditions and methods through which facets and inequalities associated with the polytope of a certain graph can be adapted in order to become valid and eventually facet-defining for some of its subgraphs or supergraphs. Numerical studies combining heuristic separation methods based on a threshold rounding and lazy-constraint generation indicate that our approach substantially outperforms existing methods for the MCCP, solving many benchmark graphs to optimality for the first time.
Collaborative Visual Area Coverage using Unmanned Aerial Vehicles
Venue: arXiv cs.SY 2016
Year: 2016

This article addresses the visual area coverage problem using a team of Unmanned Aerial Vehicles (UAVs). The UAVs are assumed to be equipped with a downward facing camera covering all points of interest within a circle on the ground. The diameter of this circular conic-section increases as the UAV flies at a larger height, yet the quality of the observed area is inverse proportional to the UAV's height. The objective is to provide a distributed control algorithm that maximizes a combined coverage-quality criterion by adjusting the UAV's altitude. Simulation studies are offered to highlight the effectiveness of the suggested scheme.
Re-identification of Humans in Crowds using Personal, Social and Environmental Constraints
Venue: arXiv cs.CV 2016
Year: 2016

This paper addresses the problem of human re-identification across non-overlapping cameras in crowds.Re-identification in crowded scenes is a challenging problem due to large number of people and frequent occlusions, coupled with changes in their appearance due to different properties and exposure of cameras. To solve this problem, we model multiple Personal, Social and Environmental (PSE) constraints on human motion across cameras. The personal constraints include appearance and preferred speed of each individual assumed to be similar across the non-overlapping cameras. The social influences (constraints) are quadratic in nature, i.e. occur between pairs of individuals, and modeled through grouping and collision avoidance. Finally, the environmental constraints capture the transition probabilities between gates (entrances / exits) in different cameras, defined as multi-modal distributions of transition time and destination between all pairs of gates. We incorporate these constraints into an energy minimization framework for solving human re-identification. Assigning $1-1$ correspondence while modeling PSE constraints is NP-hard. We present a stochastic local search algorithm to restrict the search space of hypotheses, and obtain $1-1$ solution in the presence of linear and quadratic PSE constraints. Moreover, we present an alternate optimization using Frank-Wolfe algorithm that solves the convex approximation of the objective function with linear relaxation on binary variables, and yields an order of magnitude speed up over stochastic local search with minor drop in performance. We evaluate our approach using Cumulative Matching Curves as well $1-1$ assignment on several thousand frames of Grand Central, PRID and DukeMTMC datasets, and obtain significantly better results compared to existing re-identification methods.
On Counting Subring-Subcodes of Free Linear Codes Over Finite Principal Ideal Rings
Venue: arXiv cs.IT 2016
Year: 2016

Let $R$ be a finite principal ideal ring and $S$ the Galois extension of $R$ of degree $m$. For $k$ and $k_0$, positive integers we determine the number of free $S$-linear codes $B$ of length $l$ with the property $k = rank_S(B)$ and $k_0 = rank_R (B\cap R^l)$. This corrects a wrong result which was given in the case of finite fields.
Embedded Line Scan Image Sensors: The Low Cost Alternative for High Speed Imaging
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we propose a low-cost high-speed imaging line scan system. We replace an expensive industrial line scan camera and illumination with a custom-built set-up of cheap off-the-shelf components, yielding a measurement system with comparative quality while costing about 20 times less. We use a low-cost linear (1D) image sensor, cheap optics including a LED-based or LASER-based lighting and an embedded platform to process the images. A step-by-step method to design such a custom high speed imaging system and select proper components is proposed. Simulations allowing to predict the final image quality to be obtained by the set-up has been developed. Finally, we applied our method in a lab, closely representing the real-life cases. Our results shows that our simulations are very accurate and that our low-cost line scan set-up acquired image quality compared to the high-end commercial vision system, for a fraction of the price.
A Communication-Efficient Parallel Method for Group-Lasso
Venue: arXiv cs.LG 2016
Year: 2016

Group-Lasso (gLasso) identifies important explanatory factors in predicting the response variable by considering the grouping structure over input variables. However, most existing algorithms for gLasso are not scalable to deal with large-scale datasets, which are becoming a norm in many applications. In this paper, we present a divide-and-conquer based parallel algorithm (DC-gLasso) to scale up gLasso in the tasks of regression with grouping structures. DC-gLasso only needs two iterations to collect and aggregate the local estimates on subsets of the data, and is provably correct to recover the true model under certain conditions. We further extend it to deal with overlappings between groups. Empirical results on a wide range of synthetic and real-world datasets show that DC-gLasso can significantly improve the time efficiency without sacrificing regression accuracy.
Robust Low-Complexity Randomized Methods for Locating Outliers in Large Matrices
Venue: arXiv cs.IT 2016
Year: 2016

This paper examines the problem of locating outlier columns in a large, otherwise low-rank matrix, in settings where {}{the data} are noisy, or where the overall matrix has missing elements. We propose a randomized two-step inference framework, and establish sufficient conditions on the required sample complexities under which these methods succeed (with high probability) in accurately locating the outliers for each task. Comprehensive numerical experimental results are provided to verify the theoretical bounds and demonstrate the computational efficiency of the proposed algorithm.
Neural Turing Machines: Convergence of Copy Tasks
Venue: arXiv cs.NE 2016
Year: 2016

The architecture of neural Turing machines is differentiable end to end and is trainable with gradient descent methods. Due to their large unfolded depth Neural Turing Machines are hard to train and because of their linear access of complete memory they do not scale. Other architectures have been studied to overcome these difficulties. In this report we focus on improving the quality of prediction of the original linear memory architecture on copy and repeat copy tasks. Copy task predictions on sequences of length six times larger than those the neural Turing machine was trained on prove to be highly accurate and so do predictions of repeat copy tasks for sequences with twice the repetition number and twice the sequence length neural Turing machine was trained on.
Subquadratic Algorithms for Algebraic Generalizations of 3SUM
Venue: arXiv cs.DS 2016
Year: 2016

The 3SUM problem asks if an input $n$-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave a $O(n^{11/6})$ upper bound on the number of solutions of trivariate polynomial equations when the solutions are taken from the cartesian product of three $n$-sets of real numbers. We give algorithms for the corresponding problem of counting such solutions. Grønlund and Pettie recently designed subquadratic algorithms for 3SUM. We generalize their results to 3POL. Finally, we shed light on the General Position Testing (GPT) problem: "Given $n$ points in the plane, do three of them lie on a line?", a key problem in computational geometry. We prove that there exist bounded-degree algebraic decision trees of depth $O(n^{\frac{12}{7}+\varepsilon})$ that solve 3POL, and that 3POL can be solved in $O(n^2 {(\log \log n)}^\frac{3}{2} / {(\log n)}^\frac{1}{2})$ time in the real-RAM model. Among the possible applications of those results, we show how to solve GPT in subquadratic time when the input points lie on $o({(\log n)}^\frac{1}{6}/{(\log \log n)}^\frac{1}{2})$ constant-degree polynomial curves. This constitutes a first step towards closing the major open question of whether GPT can be solved in subquadratic time. To obtain these results, we generalize important tools --- such as batch range searching and dominance reporting --- to a polynomial setting. We expect these new tools to be useful in other applications.
Geodesics using Waves: Computing Distances using Wave Propagation
Venue: arXiv cs.CG 2016
Year: 2016

In this paper, we present a new method for computing approximate geodesic distances. We introduce the wave method for approximating geodesic distances from a point on a manifold mesh. Our method involves the solution of two linear systems of equations. One system of equations is solved repeatedly to propagate the wave on the entire mesh, and one system is solved once after wave propagation is complete in order to compute the approximate geodesic distances up to an additive constant. However, these systems need to be pre-factored only once, and can be solved efficiently at each iteration. All of our tests required approximately between 300 and 400 iterations, which were completed in a few seconds. Therefore, this method can approximate geodesic distances quickly, and the approximation is highly accurate.
Contextual Visual Similarity
Venue: arXiv cs.CV 2016
Year: 2016

Measuring visual similarity is critical for image understanding. But what makes two images similar? Most existing work on visual similarity assumes that images are similar because they contain the same object instance or category. However, the reason why images are similar is much more complex. For example, from the perspective of category, a black dog image is similar to a white dog image. However, in terms of color, a black dog image is more similar to a black horse image than the white dog image. This example serves to illustrate that visual similarity is ambiguous but can be made precise when given an explicit contextual perspective. Based on this observation, we propose the concept of contextual visual similarity. To be concrete, we examine the concept of contextual visual similarity in the application domain of image search. Instead of providing only a single image for image similarity search (\eg, Google image search), we require three images. Given a query image, a second positive image and a third negative image, dissimilar to the first two images, we define a contextualized similarity search criteria. In particular, we learn feature weights over all the feature dimensions of each image such that the distance between the query image and the positive image is small and their distances to the negative image are large after reweighting their features. The learned feature weights encode the contextualized visual similarity specified by the user and can be used for attribute specific image search. We also show the usefulness of our contextualized similarity weighting scheme for different tasks, such as answering visual analogy questions and unsupervised attribute discovery.