OpenRaiser/Intern-Atlas huggingface dataset:
Deep Hashing: A Joint Approach for Image Signature Learning
Venue: arXiv cs.CV 2016
Year: 2016

Similarity-based image hashing represents crucial technique for visual data storage reduction and expedited image search. Conventional hashing schemes typically feed hand-crafted features into hash functions, which separates the procedures of feature extraction and hash function learning. In this paper, we propose a novel algorithm that concurrently performs feature engineering and non-linear supervised hashing function learning. Our technical contributions in this paper are two-folds: 1) deep network optimization is often achieved by gradient propagation, which critically requires a smooth objective function. The discrete nature of hash codes makes them not amenable for gradient-based optimization. To address this issue, we propose an exponentiated hashing loss function and its bilinear smooth approximation. Effective gradient calculation and propagation are thereby enabled; 2) pre-training is an important trick in supervised deep learning. The impact of pre-training on the hash code quality has never been discussed in current deep hashing literature. We propose a pre-training scheme inspired by recent advance in deep network based image classification, and experimentally demonstrate its effectiveness. Comprehensive quantitative evaluations are conducted on several widely-used image benchmarks. On all benchmarks, our proposed deep hashing algorithm outperforms all state-of-the-art competitors by significant margins. In particular, our algorithm achieves a near-perfect 0.99 in terms of Hamming ranking accuracy with only 12 bits on MNIST, and a new record of 0.74 on the CIFAR10 dataset. In comparison, the best accuracies obtained on CIFAR10 by existing hashing algorithms without or with deep networks are known to be 0.36 and 0.58 respectively.
Reasoning and Algorithm Selection Augmented Symbolic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we present an alternative method to symbolic segmentation: we approach symbolic segmentation as an algorithm selection problem. That is, let there be a set A of available algorithms for symbolic segmentation, a set of input features $F$, a set of image attribute $\mathbb{A}$ and a selection mechanism $S(F,\mathbb{A},A)$ that selects on a case by case basis the best algorithm. The semantic segmentation is then an optimization process that combines best component segments from multiple results into a single optimal result. The experiments compare three different algorithm selection mechanisms using three selected semantic segmentation algorithms. The results show that using the current state of art algorithms and relatively low accuracy of algorithm selection the accuracy of the semantic segmentation can be improved by 2\%.
Differential Privacy as a Mutual Information Constraint
Venue: arXiv cs.IT 2016
Year: 2016

Differential privacy is a precise mathematical constraint meant to ensure privacy of individual pieces of information in a database even while queries are being answered about the aggregate. Intuitively, one must come to terms with what differential privacy does and does not guarantee. For example, the definition prevents a strong adversary who knows all but one entry in the database from further inferring about the last one. This strong adversary assumption can be overlooked, resulting in misinterpretation of the privacy guarantee of differential privacy. Herein we give an equivalent definition of privacy using mutual information that makes plain some of the subtleties of differential privacy. The mutual-information differential privacy is in fact sandwiched between $ε$-differential privacy and $(ε,δ)$-differential privacy in terms of its strength. In contrast to previous works using unconditional mutual information, differential privacy is fundamentally related to conditional mutual information, accompanied by a maximization over the database distribution. The conceptual advantage of using mutual information, aside from yielding a simpler and more intuitive definition of differential privacy, is that its properties are well understood. Several properties of differential privacy are easily verified for the mutual information alternative, such as composition theorems.
Joint 3D Positioning and Network Synchronization in 5G Ultra-Dense Networks Using UKF and EKF
Venue: arXiv cs.IT 2016
Year: 2016

It is commonly expected that future fifth generation (5G) networks will be deployed with a high spatial density of access nodes (ANs) in order to meet the envisioned capacity requirements of the upcoming wireless networks. Densification is beneficial not only for communications but it also creates a convenient infrastructure for highly accurate user node (UN) positioning. Despite the fact that positioning will play an important role in future networks, thus enabling a huge amount of location-based applications and services, this great opportunity has not been widely explored in the existing literature. Therefore, this paper proposes an unscented Kalman filter (UKF)-based method for estimating directions of arrival (DoAs) and times of arrival (ToA) at ANs as well as performing joint 3D positioning and network synchronization in a network-centric manner. In addition to the proposed UKF-based solution, the existing 2D extended Kalman filter (EKF)-based solution is extended to cover also realistic 3D positioning scenarios. Building on the premises of 5G ultra-dense networks (UDNs), the performance of both methods is evaluated and analysed in terms of DoA and ToA estimation as well as positioning and clock offset estimation accuracy, using the METIS map-based ray-tracing channel model and 3D trajectories for vehicles and unmanned aerial vehicles (UAVs) through the Madrid grid. Based on the comprehensive numerical evaluations, both proposed methods can provide the envisioned one meter 3D positioning accuracy even in the case of unsynchronized 5G network while simultaneously tracking the clock offsets of network elements with a nanosecond-scale accuracy.
Student's t Distribution based Estimation of Distribution Algorithms for Derivative-free Global Optimization
Venue: arXiv cs.NE 2016
Year: 2016

In this paper, we are concerned with a branch of evolutionary algorithms termed estimation of distribution (EDA), which has been successfully used to tackle derivative-free global optimization problems. For existent EDA algorithms, it is a common practice to use a Gaussian distribution or a mixture of Gaussian components to represent the statistical property of available promising solutions found so far. Observing that the Student's t distribution has heavier and longer tails than the Gaussian, which may be beneficial for exploring the solution space, we propose a novel EDA algorithm termed ESTDA, in which the Student's t distribution, rather than Gaussian, is employed. To address hard multimodal and deceptive problems, we extend ESTDA further by substituting a single Student's t distribution with a mixture of Student's t distributions. The resulting algorithm is named as estimation of mixture of Student's t distribution algorithm (EMSTDA). Both ESTDA and EMSTDA are evaluated through extensive and in-depth numerical experiments using over a dozen of benchmark objective functions. Empirical results demonstrate that the proposed algorithms provide remarkably better performance than their Gaussian counterparts.
Measuring the State of the Art of Automated Pathway Curation Using Graph Algorithms - A Case Study of the mTOR Pathway
Venue: arXiv cs.CL 2016
Year: 2016

This paper evaluates the difference between human pathway curation and current NLP systems. We propose graph analysis methods for quantifying the gap between human curated pathway maps and the output of state-of-the-art automatic NLP systems. Evaluation is performed on the popular mTOR pathway. Based on analyzing where current systems perform well and where they fail, we identify possible avenues for progress.
High-throughput Ingest of Provenance Records into Accumulo
Venue: arXiv cs.DB 2016
Year: 2016

Whole-system data provenance provides deep insight into the processing of data on a system, including detecting data integrity attacks. The downside to systems that collect whole-system data provenance is the sheer volume of data that is generated under many heavy workloads. In order to make provenance metadata useful, it must be stored somewhere where it can be queried. This problem becomes even more challenging when considering a network of provenance-aware machines all collecting this metadata. In this paper, we investigate the use of D4M and Accumulo to support high-throughput data ingest of whole-system provenance data. We find that we are able to ingest 3,970 graph components per second. Centrally storing the provenance metadata allows us to build systems that can detect and respond to data integrity attacks that are captured by the provenance system.
Prutor: A System for Tutoring CS1 and Collecting Student Programs for Analysis
Venue: arXiv cs.CY 2016
Year: 2016

An introductory programming course (CS1) is an integral part of any undergraduate curriculum. Due to large number and diverse programming background of students, providing timely and personalised feedback to individual students is a challenging task for any CS1 instructor. The help provided by teaching assistants (typically senior students) is not sufficient as it suffers from unintentional bias and, most of the time, not quick enough. In this paper, we present Prutor, a tutoring system platform to conduct introductory programming courses. Prutor is a cloud-based web application that provides instant and useful feedback to students while solving programming problems. Prutor stores, at regular intervals, the snapshots of students' attempts to solve programming problems. These intermediate versions of the student programs provide the instructors (and data analysts) a view of the students' approach to solving programming problems. Since Prutor is accessible through any standard web browser, students do not need to worry about dependencies external to the programming course, viz. Operating Systems, Editors, Compilers, Compiler Options, etc.. This enables the students to focus on solving only the programming problems. Apart from the code snapshots at regular intervals, Prutor also collects other valuable data such as the time taken by the students to solve the problems, the number of compile and execution events, and the errors made. We have used this data in developing intelligent tools for giving feedback to students, some of which are described briefly in this paper. This system thus serves as a platform for tutoring as well as data collection for researchers.
Distributed Optimization for Client-Server Architecture with Negative Gradient Weights
Venue: arXiv cs.DC 2016
Year: 2016

Availability of both massive datasets and computing resources have made machine learning and predictive analytics extremely pervasive. In this work we present a synchronous algorithm and architecture for distributed optimization motivated by privacy requirements posed by applications in machine learning. We present an algorithm for the recently proposed multi-parameter-server architecture. We consider a group of parameter servers that learn a model based on randomized gradients received from clients. Clients are computational entities with private datasets (inducing a private objective function), that evaluate and upload randomized gradients to the parameter servers. The parameter servers perform model updates based on received gradients and share the model parameters with other servers. We prove that the proposed algorithm can optimize the overall objective function for a very general architecture involving $C$ clients connected to $S$ parameter servers in an arbitrary time varying topology and the parameter servers forming a connected network.
Rapid Classification of Crisis-Related Data on Social Networks using Convolutional Neural Networks
Venue: arXiv cs.CL 2016
Year: 2016

The role of social media, in particular microblogging platforms such as Twitter, as a conduit for actionable and tactical information during disasters is increasingly acknowledged. However, time-critical analysis of big crisis data on social media streams brings challenges to machine learning techniques, especially the ones that use supervised learning. The Scarcity of labeled data, particularly in the early hours of a crisis, delays the machine learning process. The current state-of-the-art classification methods require a significant amount of labeled data specific to a particular event for training plus a lot of feature engineering to achieve best results. In this work, we introduce neural network based classification methods for binary and multi-class tweet classification task. We show that neural network based models do not require any feature engineering and perform better than state-of-the-art methods. In the early hours of a disaster when no labeled data is available, our proposed method makes the best use of the out-of-event data and achieves good results.
Energy Management for Demand Responsive Users with Shared Energy Storage System
Venue: arXiv cs.SY 2016
Year: 2016

This paper investigates the energy management problem for multiple self-interested users, each with renewable energy generation as well as both the fixed and controllable loads, that all share a common energy storage system (ESS). The self-interested users are willing to sell/buy energy to/from the shared ESS if they can achieve lower energy costs compared to the case of no energy trading while preserving their privacy e.g. sharing only limited information with a central controller. Under this setup, we propose an iterative algorithm by which the central controller coordinates the charging/discharging values to/from the shared ESS by all users such that their individual energy costs reduce at the same time. For performance benchmark, the case of cooperative users that all belong to the same entity is considered, where they share all the required information with the central controller so as to minimize their total energy cost. Finally, the effectiveness of our proposed algorithm in simultaneously reducing users' energy costs is shown via simulations based on realistic system data of California, US.
Centralized coded caching schemes: A hypergraph theoretical approach
Venue: arXiv cs.IT 2016
Year: 2016

The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a solution to reduce the network burden in peak times in a wireless system. Later Yan et al. reformulated the problem as designing a corresponding placement delivery array, and proposed two new schemes from this perspective. These schemes above significantly reduce the transmission rate $R$, compared with the uncoded caching scheme. However, to implement the new schemes, each file should be cut into $F$ pieces, where $F$ increases exponentially with the number of users $K$. Such constraint is obviously infeasible in the practical setting, especially when $K$ is large. Thus it is desirable to design caching schemes with constant rate $R$ (independent of $K$) as well as small $F$. In this paper we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6, 3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6, 3)-theorem in extremal combinatorics, we show that constant rate caching schemes with $F$ growing linearly with $K$ do not exist. Second, we present two infinite classes of centralized coded caching schemes, which include the schemes of Ali-Niesen and Yan et al. as special cases, respectively. Moreover, our constructions show that constant rate caching schemes with $F$ growing sub-exponentially with $K$ do exist.
Survivable Cloud Network Design Against Multiple Failures Through Protecting Spanning Trees
Venue: arXiv cs.NI 2016
Year: 2016

Survivable design of cross-layer networks, such as the cloud computing infrastructure, lies in its resource deployment and allocation and mapping of the logical (virtual datacenter/IP) network into the physical infrastructure (cloud backbone/WDM) such that link or node failure(s) in the physical infrastructure would not result in cascading failures in the logical network. Most of the prior approaches for survivable cross-layer network design aim at single-link failure scenario, which are not applicable to the more challenging multi-failure scenarios. Also, as many of these approaches use the cross-layer cut concept, enumeration of all cuts in the network is required and thus introducing exponential number of constraints. To overcome these difficulties, we investigate in this paper survivable mapping approaches against multiple physical link failures and its special case, Shared Risk Link Group (SRLG) failure. We present the necessary and sufficient conditions based on both cross-layer spanning trees and cutsets to guarantee a survivable mapping when multiple physical link failures occur. Based on the necessary and sufficient conditions, we propose to solve the problem through (1) mixed-integer linear programs which avoid enumerating all combinations of link failures, and (2) an algorithm which generates/adds logical spanning trees sequentially. Our simulation results show that the proposed approaches can produce survivable mappings effectively against both $k$- and SRLG-failures.
Greedy Maximization Framework for Graph-based Influence Functions
Venue: arXiv cs.DS 2016
Year: 2016

The study of graph-based submodular maximization problems was initiated in a seminal work of Kempe, Kleinberg, and Tardos (2003): An {\em influence} function of subsets of nodes is defined by the graph structure and the aim is to find subsets of seed nodes with (approximately) optimal tradeoff of size and influence. Applications include viral marketing, monitoring, and active learning of node labels. This powerful formulation was studied for (generalized) {\em coverage} functions, where the influence of a seed set on a node is the maximum utility of a seed item to the node, and for pairwise {\em utility} based on reachability, distances, or reverse ranks. We define a rich class of influence functions which unifies and extends previous work beyond coverage functions and specific utility functions. We present a meta-algorithm for approximate greedy maximization with strong approximation quality guarantees and worst-case near-linear computation for all functions in our class. Our meta-algorithm generalizes a recent design by Cohen et al (2014) that was specific for distance-based coverage functions.
What Information Really Matters in Supervisor Reduction?
Venue: arXiv cs.SY 2016
Year: 2016

To make a supervisor comprehensible to a layman has been a long-lasting goal in the supervisory control community. One strategy is to reduce the size of a supervisor to generate a control equivalent version, whose size is hopefully much smaller than the original one so that a user or control designer can easily check whether a designed controller fulfils its objectives and requirements. After the first journal paper on this topic appeared in 1986 by Vaz and Wonham, which relied on the concept of control covers, in 2004 Su and Wonham proposed to use control congruences to ensure computational viability. This work is later adopted in the supervisor localization theory, which aims for a control equivalent distributed implementation of a given centralized supervisor. But after so many publications, some fundamental questions, which should have been addressed in the first place, have not been answered yet, namely what information is critical to ensure control equivalence, what information is responsible for size reduction, and whether the partial observation really makes things different. In this paper we will address these fundamental questions by showing that there does exist a unified supervisor reduction theory, which is applicable to all feasible supervisors regardless of whether they are under full observation or partial observation. Our theory provides a partial order over all control equivalent feasible supervisors based on their enabling, disabling and marking information, which can be used to categorize the corresponding reduction rates. Based on this result we can see that, given two control equivalent feasible supervisors, the one under full observation can always result in a reduced supervisor no bigger than that induced by a supervisor under partial observation.
The Importance of Skip Connections in Biomedical Image Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we study the influence of both long and short skip connections on Fully Convolutional Networks (FCN) for biomedical image segmentation. In standard FCNs, only long skip connections are used to skip features from the contracting path to the expanding path in order to recover spatial information lost during downsampling. We extend FCNs by adding short skip connections, that are similar to the ones introduced in residual networks, in order to build very deep FCNs (of hundreds of layers). A review of the gradient flow confirms that for a very deep FCN it is beneficial to have both long and short skip connections. Finally, we show that a very deep FCN can achieve near-to-state-of-the-art results on the EM dataset without any further post-processing.
Learning to Rank Questions for Community Question Answering with Ranking SVM
Venue: arXiv cs.IR 2016
Year: 2016

This paper presents our method to retrieve relevant queries given a new question in the context of Discovery Challenge: Learning to Re-Ranking Questions for Community Question Answering competition. In order to do that, a set of learning to rank methods was investigated to select an appropriate method. The selected method was optimized on training data by using a search strategy. After optimizing, the method was applied to development and test set. Results from the competition indicate that the performance of our method outperforms almost participants and show that Ranking SVM is efficient for retrieving relevant queries in community question answering.
Robust benchmarking in noisy environments
Venue: arXiv cs.PF 2016
Year: 2016

We propose a benchmarking strategy that is robust in the presence of timer error, OS jitter and other environmental fluctuations, and is insensitive to the highly nonideal statistics produced by timing measurements. We construct a model that explains how these strongly nonideal statistics can arise from environmental fluctuations, and also justifies our proposed strategy. We implement this strategy in the BenchmarkTools Julia package, where it is used in production continuous integration (CI) pipelines for developing the Julia language and its ecosystem.
Narumi-Katayama Index of Total Transformation Graphs
Venue: arXiv cs.DM 2016
Year: 2016

The Narumi-Katayama index of a graph was introduced in 1984 for representing the carbon skeleton of a saturated hydrocarbons and is defined as the product of degrees of all the vertices of the graph. In this paper, we examine the Narumi-Katayama index of different total transformation graphs.
Consistency constraints for overlapping data clustering
Venue: arXiv cs.LG 2016
Year: 2016

We examine overlapping clustering schemes with functorial constraints, in the spirit of Carlsson--Memoli. This avoids issues arising from the chaining required by partition-based methods. Our principal result shows that any clustering functor is naturally constrained to refine single-linkage clusters and be refined by maximal-linkage clusters. We work in the context of metric spaces with non-expansive maps, which is appropriate for modeling data processing which does not increase information content.