OpenRaiser/Intern-Atlas huggingface dataset:
On Equivalence of Likelihood Maximization of Stochastic Block Model and Constrained Nonnegative Matrix Factorization
Venue: arXiv cs.SI 2017
Year: 2017

Community structures detection in complex network is important for understanding not only the topological structures of the network, but also the functions of it. Stochastic block model and nonnegative matrix factorization are two widely used methods for community detection, which are proposed from different perspectives. In this paper, the relations between them are studied. The logarithm of likelihood function for stochastic block model can be reformulated under the framework of nonnegative matrix factorization. Besides the model equivalence, the algorithms employed by the two methods are different. Preliminary numerical experiments are carried out to compare the behaviors of the algorithms.
Cohomology of Cryo-Electron Microscopy
Venue: arXiv cs.CV 2017
Year: 2017

The goal of cryo-electron microscopy (EM) is to reconstruct the 3-dimensional structure of a molecule from a collection of its 2-dimensional projected images. In this article, we show that the basic premise of cryo-EM --- patching together 2-dimensional projections to reconstruct a 3-dimensional object --- is naturally one of Cech cohomology with SO(2)-coefficients. We deduce that every cryo-EM reconstruction problem corresponds to an oriented circle bundle on a simplicial complex, allowing us to classify cryo-EM problems via principal bundles. In practice, the 2-dimensional images are noisy and a main task in cryo-EM is to denoise them. We will see how the aforementioned insights can be used towards this end.
Practical Subtyping for System F with Sized (Co-)Induction
Venue: arXiv cs.LO 2017
Year: 2017

We present a rich type system with subtyping for an extension of System F. Our type constructors include sum and product types, universal and existential quantifiers, inductive and coinductive types. The latter two size annotations allowing the preservation of size invariants. For example it is possible to derive the termination of the quicksort by showing that partitioning a list does not increase its size. The system deals with complex programs involving mixed induction and coinduction, or even mixed (co-)induction and polymorphism (as for Scott-encoded datatypes). One of the key ideas is to completely separate the induction on sizes from the notion of recursive programs. We use the size change principle to check that the proof is well-founded, not that the program terminates. Termination is obtained by a strong normalization proof. Another key idea is the use symbolic witnesses to handle quantifiers of all sorts. To demonstrate the practicality of our system, we provide an implementation that accepts all the examples discussed in the paper and much more.
Inhabitation in Simply-Typed Lambda-Calculus through a Lambda-Calculus for Proof Search
Venue: arXiv cs.LO 2017
Year: 2017

A new, comprehensive approach to inhabitation problems in simply-typed lambda-calculus is shown, dealing with both decision and counting problems. This approach works by exploiting a representation of the search space generated by a given inhabitation problem, which is in terms of a lambda-calculus for proof search that the authors developed recently. The representation may be seen as extending the Curry-Howard representation of proofs by lambda-terms, staying within the methods of lambda-calculus and type systems. Our methodology reveals inductive descriptions of the decision problems, driven by the syntax of the proof-search expressions, and the end products are simple, recursive decision procedures and counting functions.
Norm-preserving Orthogonal Permutation Linear Unit Activation Functions (OPLU)
Venue: arXiv cs.NE 2017
Year: 2017

We propose a novel activation function that implements piece-wise orthogonal non-linear mappings based on permutations. It is straightforward to implement, and very computationally efficient, also it has little memory requirements. We tested it on two toy problems for feedforward and recurrent networks, it shows similar performance to tanh and ReLU. OPLU activation function ensures norm preservance of the backpropagated gradients, therefore it is potentially good for the training of deep, extra deep, and recurrent neural networks.
Graph-based Collaborative Ranking
Venue: arXiv cs.SI 2017
Year: 2017

Data sparsity, that is a common problem in neighbor-based collaborative filtering domain, usually complicates the process of item recommendation. This problem is more serious in collaborative ranking domain, in which calculating the users similarities and recommending items are based on ranking data. Some graph-based approaches have been proposed to address the data sparsity problem, but they suffer from two flaws. First, they fail to correctly model the users priorities, and second, they cannot be used when the only available data is a set of ranking instead of rating values. In this paper, we propose a novel graph-based approach, called GRank, that is designed for collaborative ranking domain. GRank can correctly model users priorities in a new tripartite graph structure, and analyze it to directly infer a recommendation list. The experimental results show a significant improvement in recommendation quality compared to the state of the art graph-based recommendation algorithms and other collaborative ranking techniques.
Subcategory-aware Convolutional Neural Networks for Object Proposals and Detection
Venue: arXiv cs.CV 2017
Year: 2017

In CNN-based object detection methods, region proposal becomes a bottleneck when objects exhibit significant scale variation, occlusion or truncation. In addition, these methods mainly focus on 2D object detection and cannot estimate detailed properties of objects. In this paper, we propose subcategory-aware CNNs for object detection. We introduce a novel region proposal network that uses subcategory information to guide the proposal generating process, and a new detection network for joint detection and subcategory classification. By using subcategories related to object pose, we achieve state-of-the-art performance on both detection and pose estimation on commonly used benchmarks.
Structured Sparse Convolutional Autoencoder
Venue: arXiv cs.LG 2017
Year: 2017

This paper aims to improve the feature learning in Convolutional Networks (Convnet) by capturing the structure of objects. A new sparsity function is imposed on the extracted featuremap to capture the structure and shape of the learned object, extracting interpretable features to improve the prediction performance. The proposed algorithm is based on organizing the activation within and across featuremap by constraining the node activities through $\ell_{2}$ and $\ell_{1}$ normalization in a structured form.
Design and Analysis of Dynamic Auto Scaling Algorithm (DASA) for 5G Mobile Networks
Venue: arXiv cs.NI 2017
Year: 2017

Network Function Virtualization (NFV) enables mobile operators to virtualize their network entities as Virtualized Network Functions (VNFs), offering fine-grained on-demand network capabilities. VNFs can be dynamically scale-in/out to meet the performance requirements for future 5G networks. However, designing an auto-scaling algorithm with low operation cost and low latency while considering the capacity of legacy network equipment is a challenge. In this paper, we propose a VNF Dynamic Auto Scaling Algorithm (DASA) considering the tradeoff between performance and operation cost. We also develop an analytical model to quantify the tradeoff and validate the analysis through extensive simulations. The system is modeled as a queueing model while legacy network equipment is considered as a reserved block of servers. The VNF instances are powered on and off according to the number of job requests. The results show that the proposed DASA can significantly reduce operation cost given the latency upper-bound. Moreover, the models provide a quick way to evaluate the cost-performance tradeoff without wide deployment, which can save cost and time.
Network of Experts for Large-Scale Image Categorization
Venue: arXiv cs.CV 2017
Year: 2017

We present a tree-structured network architecture for large scale image classification. The trunk of the network contains convolutional layers optimized over all classes. At a given depth, the trunk splits into separate branches, each dedicated to discriminate a different subset of classes. Each branch acts as an expert classifying a set of categories that are difficult to tell apart, while the trunk provides common knowledge to all experts in the form of shared features. The training of our "network of experts" is completely end-to-end: the partition of categories into disjoint subsets is learned simultaneously with the parameters of the network trunk and the experts are trained jointly by minimizing a single learning objective over all classes. The proposed structure can be built from any existing convolutional neural network (CNN). We demonstrate its generality by adapting 4 popular CNNs for image categorization into the form of networks of experts. Our experiments on CIFAR100 and ImageNet show that in every case our method yields a substantial improvement in accuracy over the base CNN, and gives the best result achieved so far on CIFAR100. Finally, the improvement in accuracy comes at little additional cost: compared to the base network, the training time is only moderately increased and the number of parameters is comparable or in some cases even lower.
Approximation Algorithm for Fault-Tolerant Virtual Backbone in Wireless Sensor Networks
Venue: arXiv cs.DM 2017
Year: 2017

To save energy and alleviate interferences in a wireless sensor network, the usage of virtual backbone was proposed. Because of accidental damages or energy depletion, it is desirable to construct a fault tolerant virtual backbone, which can be modeled as a $k$-connected $m$-fold dominating set (abbreviated as $(k,m)$-CDS) in a graph. A node set $C\subseteq V(G)$ is a $(k,m)$-CDS of graph $G$ if every node in $V(G)\backslash C$ is adjacent with at least $m$ nodes in $C$ and the subgraph of $G$ induced by $C$ is $k$-connected. In this paper, we present an approximation algorithm for the minimum $(3,m)$-CDS problem with $m\geq3$. The performance ratio is at most $γ$, where $γ=α+8+2\ln(2α-6)$ for $α\geq4$ and $γ=3α+2\ln2$ for $α<4$, and $α$ is the performance ratio for the minimum $(2,m)$-CDS problem. Using currently best known value of $α$, the performance ratio is $\lnδ+o(\lnδ)$, where $δ$ is the maximum degree of the graph, which is asymptotically best possible in view of the non-approximability of the problem. This is the first performance-guaranteed algorithm for the minimum $(3,m)$-CDS problem on a general graph. Furthermore, applying our algorithm on a unit disk graph which models a homogeneous wireless sensor network, the performance ratio is less than 27, improving previous ratio 62.3 by a large amount for the $(3,m)$-CDS problem on a unit disk graph.
FlashR: R-Programmed Parallel and Scalable Machine Learning using SSDs
Venue: arXiv cs.DC 2017
Year: 2017

R is one of the most popular programming languages for statistics and machine learning, but the R framework is relatively slow and unable to scale to large datasets. The general approach for speeding up an implementation in R is to implement the algorithms in C or FORTRAN and provide an R wrapper. FlashR takes a different approach: it executes R code in parallel and scales the code beyond memory capacity by utilizing solid-state drives (SSDs) automatically. It provides a small number of generalized operations (GenOps) upon which we reimplement a large number of matrix functions in the R base package. As such, FlashR parallelizes and scales existing R code with little/no modification. To reduce data movement between CPU and SSDs, FlashR evaluates matrix operations lazily, fuses operations at runtime, and uses cache-aware, two-level matrix partitioning. We evaluate FlashR on a variety of machine learning and statistics algorithms on inputs of up to four billion data points. FlashR out-of-core tracks closely the performance of FlashR in-memory. The R code for machine learning algorithms executed in FlashR outperforms the in-memory execution of H2O and Spark MLlib by a factor of 2-10 and outperforms Revolution R Open by more than an order of magnitude.
Joint Source-Channel Coding with One-Bit ADC Front End
Venue: arXiv cs.IT 2017
Year: 2017

Motivated by the practical constraints arising in emerging sensor network and Internet-of-Things (IoT) applications, the zero-delay transmission of a Gaussian measurement over a real single-input multiple-output (SIMO) additive white Gaussian noise (AWGN) channel is studied with a low-resolution analog-to-digital converter (ADC) front end. Joint optimization of the encoder and the decoder mapping is tackled under both the mean squared error (MSE) distortion and the distortion outage probability (DOP) criteria, with an average power constraint on the channel input. Optimal encoder and decoder mappings are identified for a one-bit ADC front end under both criteria. For the MSE distortion, the optimal encoder mapping is shown to be non-linear in general, while it tends to a linear encoder in the low signal-to-noise ratio (SNR) regime, and to an antipodal digital encoder in the high SNR regime. This is in contrast to the optimality of linear encoding at all SNR values in the presence of a full-precision front end. For the DOP criterion, it is shown that the optimal encoder mapping is piecewise constant and can take only two opposite values when it is non-zero. For both the MSE distortion and the DOP criteria, necessary optimality conditions are then derived for $K$-level ADC front ends as well as front ends with multiple one-bit ADCs. These conditions are used to obtain numerically optimized solutions. Extensive numerical results are also provided in order to gain insights into the structure of the optimal encoding and decoding mappings.
Indexing Variation Graphs
Venue: arXiv cs.DS 2017
Year: 2017

Variation graphs, which represent genetic variation within a population, are replacing sequences as reference genomes. Path indexes are one of the most important tools for working with variation graphs. They generalize text indexes to graphs, allowing one to find the paths matching the query string. We propose using de Bruijn graphs as path indexes, compressing them by merging redundant subgraphs, and encoding them with the Burrows-Wheeler transform. The resulting fast, space-efficient, and versatile index is used in the variation graph toolkit vg.
Achievable Moderate Deviations Asymptotics for Streaming Compression of Correlated Sources
Venue: arXiv cs.IT 2017
Year: 2017

Motivated by streaming multi-view video coding and wireless sensor networks, we consider the problem of blockwise streaming compression of a pair of correlated sources, which we term streaming Slepian-Wolf coding. We study the moderate deviations regime in which the rate pairs of a sequence of codes converge, along a straight line, to various points on the boundary of the Slepian-Wolf region at a speed slower than the inverse square root of the blocklength $n$, while the error probability decays subexponentially fast in $n$. Our main result focuses on directions of approaches to corner points of the Slepian-Wolf region. It states that for each correlated source and all corner points, there exists a non-empty subset of directions of approaches such that the moderate deviations constant (the constant of proportionality for the subexponential decay of the error probability) is enhanced (over the non-streaming case) by at least a factor of $T$, the block delay of decoding source block pairs. We specialize our main result to the setting of streaming lossless source coding and generalize this result to the setting where we have different delay requirements for each of the two source blocks. The proof of our main result involves the use of various analytical tools and amalgamates several ideas from the recent information-theoretic streaming literature. We adapt the so-called truncated memory encoding idea from Draper and Khisti (2011) and Lee, Tan, and Khisti (2016) to ensure that the effect of error accumulation is nullified in the limit of large blocklengths. We also adapt the use of the so-called minimum weighted empirical suffix entropy decoder which was used by Draper, Chang, and Sahai (2014) to derive achievable error exponents for symbolwise streaming Slepian-Wolf coding.
Long-Term Identity-Aware Multi-Person Tracking for Surveillance Video Summarization
Venue: arXiv cs.CV 2017
Year: 2017

Multi-person tracking plays a critical role in the analysis of surveillance video. However, most existing work focus on shorter-term (e.g. minute-long or hour-long) video sequences. Therefore, we propose a multi-person tracking algorithm for very long-term (e.g. month-long) multi-camera surveillance scenarios. Long-term tracking is challenging because 1) the apparel/appearance of the same person will vary greatly over multiple days and 2) a person will leave and re-enter the scene numerous times. To tackle these challenges, we leverage face recognition information, which is robust to apparel change, to automatically reinitialize our tracker over multiple days of recordings. Unfortunately, recognized faces are unavailable oftentimes. Therefore, our tracker propagates identity information to frames without recognized faces by uncovering the appearance and spatial manifold formed by person detections. We tested our algorithm on a 23-day 15-camera data set (4,935 hours total), and we were able to localize a person 53.2% of the time with 69.8% precision. We further performed video summarization experiments based on our tracking output. Results on 116.25 hours of video showed that we were able to generate a reasonable visual diary (i.e. a summary of what a person did) for different people, thus potentially opening the door to automatic summarization of the vast amount of surveillance video generated every day.
Simultaneous Food Localization and Recognition
Venue: arXiv cs.CV 2017
Year: 2017

The development of automatic nutrition diaries, which would allow to keep track objectively of everything we eat, could enable a whole new world of possibilities for people concerned about their nutrition patterns. With this purpose, in this paper we propose the first method for simultaneous food localization and recognition. Our method is based on two main steps, which consist in, first, produce a food activation map on the input image (i.e. heat map of probabilities) for generating bounding boxes proposals and, second, recognize each of the food types or food-related objects present in each bounding box. We demonstrate that our proposal, compared to the most similar problem nowadays - object localization, is able to obtain high precision and reasonable recall levels with only a few bounding boxes. Furthermore, we show that it is applicable to both conventional and egocentric images.
Concurrent Data Structures Linked in Time
Venue: arXiv cs.LO 2017
Year: 2017

Arguments about correctness of a concurrent data structure are typically carried out by using the notion of linearizability and specifying the linearization points of the data structure's procedures. Such arguments are often cumbersome as the linearization points' position in time can be dynamic (depend on the interference, run-time values and events from the past, or even future), non-local (appear in procedures other than the one considered), and whose position in the execution trace may only be determined after the considered procedure has already terminated. In this paper we propose a new method, based on a separation-style logic, for reasoning about concurrent objects with such linearization points. We embrace the dynamic nature of linearization points, and encode it as part of the data structure's auxiliary state, so that it can be dynamically modified in place by auxiliary code, as needed when some appropriate run-time event occurs. We name the idea linking-in-time, because it reduces temporal reasoning to spatial reasoning. For example, modifying a temporal position of a linearization point can be modeled similarly to a pointer update in separation logic. Furthermore, the auxiliary state provides a convenient way to concisely express the properties essential for reasoning about clients of such concurrent objects. We illustrate the method by verifying (mechanically in Coq) an intricate optimal snapshot algorithm due to Jayanti, as well as some clients.
Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs
Venue: arXiv cs.DS 2017
Year: 2017

We present a data mining approach for reducing the search space of local search algorithms in a class of binary integer programs including the set covering and partitioning problems. The quality of locally optimal solutions typically improves if a larger neighborhood is used, while the computation time of searching the neighborhood increases exponentially. To overcome this, we extract variable associations from the instance to be solved in order to identify promising pairs of flipping variables in the neighborhood search. Based on this, we develop a 4-flip neighborhood local search algorithm that incorporates an efficient incremental evaluation of solutions and an adaptive control of penalty weights. Computational results show that the proposed method improves the performance of the local search algorithm for large-scale set covering and partitioning problems.
Optimal data recovery and forecasting with dummy long-horizon forecasts
Venue: arXiv cs.IT 2017
Year: 2017

The paper suggests a method of recovering missing values for sequences, including sequences with a multidimensional index, based on optimal approximation by processes featuring spectrum degeneracy. The problem is considered in the pathwise setting, without using probabilistic assumptions on the ensemble. The method requires to solve a closed linear equation connecting the available observations of the underlying process with the values of the approximating process with degenerate spectrum outside the observation range.Some robustness with respect to noise contamination is established for the suggested recovering algorithm. It is suggested to apply this data recovery algorithm to forecasting with a preselected dummy long-horizon forecast that helps to regularize the solution.
Ortho-polygon Visibility Representations of Embedded Graphs
Venue: arXiv cs.CG 2017
Year: 2017

An ortho-polygon visibility representation of an $n$-vertex embedded graph $G$ (OPVR of $G$) is an embedding-preserving drawing of $G$ that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of $G$ is the minimum $k$ such that every polygon has at most $k$ reflex corners. We present polynomial time algorithms that test whether $G$ has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of $G$ are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if $G$ has at most one crossing per edge (i.e., $G$ is a 1-plane graph), an OPVR of $G$ always exists while this may not be the case if two crossings per edge are allowed. Also, if $G$ is a 3-connected 1-plane graph, we can compute an OPVR of $G$ whose vertex complexity is bounded by a constant in $O(n)$ time. However, if $G$ is a 2-connected 1-plane graph, the vertex complexity of any OPVR of $G$ may be $Ω(n)$. In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in $O(n)$ time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs.