OpenRaiser/Intern-Atlas huggingface dataset:
DNN-Buddies: A Deep Neural Network-Based Estimation Metric for the Jigsaw Puzzle Problem
Venue: arXiv cs.CV 2017
Year: 2017

This paper introduces the first deep neural network-based estimation metric for the jigsaw puzzle problem. Given two puzzle piece edges, the neural network predicts whether or not they should be adjacent in the correct assembly of the puzzle, using nothing but the pixels of each piece. The proposed metric exhibits an extremely high precision even though no manual feature extraction is performed. When incorporated into an existing puzzle solver, the solution's accuracy increases significantly, achieving thereby a new state-of-the-art standard.
Microsoft Academic: A multidisciplinary comparison of citation counts with Scopus and Mendeley for 29 journals
Venue: arXiv cs.DL 2017
Year: 2017

Microsoft Academic is a free citation index that allows large scale data collection. This combination makes it useful for scientometric research. Previous studies have found that its citation counts tend to be slightly larger than those of Scopus but smaller than Google Scholar, with disciplinary variations. This study reports the largest and most systematic analysis so far, of 172,752 articles in 29 large journals chosen from different specialisms. From Scopus citation counts, Microsoft Academic citation counts and Mendeley reader counts for articles published 2007-2017, Microsoft Academic found a slightly more (6%) citations than Scopus overall and especially for the current year (51%). It found fewer citations than Mendeley readers overall (59%), and only 7% as many for the current year. Differences between journals were probably due to field preprint sharing cultures or journal policies rather than broad disciplinary differences.
Is Non-Neutrality Profitable for the Stakeholders of the Internet Market? - Part II
Venue: arXiv cs.GT 2017
Year: 2017

In this part of the paper, we obtain analytical results for the case that transport costs are not small (complement of Part I), and combine them with the results in Part I of the paper to provide general results for all values of transport costs. We show that, in general, if an SPNE exists, it would be one of the five possible strategies each of which we explicitly characterize. We also prove that when EUs have sufficiently high inertia for at least one of the ISPs, there exists a unique SPNE with a non-neutral outcome in which both of the ISPs are active, and the CP offers her content with free quality on the neutral ISP and with premium quality on the non-neutral ISP. Moreover, we show that an SPNE does not always exist. We also analyze a benchmark case in which both ISPs are neutral, and prove that there exists a unique SPNE in which the CP offers her content with free quality on both ISPs, and both ISPs are active. We also provide extensive numerical results and discussions for all ranges of transport costs. Simulation results suggest that if the SPNE exists, it would be unique. In addition, results reveal that the neutral ISP receives a lower payoff and the non-neutral ISP receives a higher payoff (most of the time) in a non-neutral scenario. However, we also identify scenarios in which the non-neutral ISP loses payoff by adopting non-neutrality. In addition, we show that a non-neutral regime yields a higher welfare for EUs than a neutral one if the market power of the non-neutral ISP is small, the sensitivity of EUs (respectively, the CP) to the quality is low (respectively, high), or a combinations of these factors.
A Survey and Taxonomy of Resource Optimisation for Executing Bag-of-Task Applications on Public Clouds
Venue: arXiv cs.DC 2017
Year: 2017

Cloud computing has been widely adopted due to the flexibility in resource provisioning and on-demand pricing models. Entire clusters of Virtual Machines (VMs) can be dynamically provisioned to meet the computational demands of users. However, from a user's perspective, it is still challenging to utilise cloud resources efficiently. This is because an overwhelmingly wide variety of resource types with different prices and significant performance variations are available. This paper presents a survey and taxonomy of existing research in optimising the execution of Bag-of-Task applications on cloud resources. A BoT application consists of multiple independent tasks, each of which can be executed by a VM in any order; these applications are widely used by both the scientific communities and commercial organisations. The objectives of this survey are as follows: (i) to provide the reader with a concise understanding of existing research on optimising the execution of BoT applications on the cloud, (ii) to define a taxonomy that categorises current frameworks to compare and contrast them, and (iii) to present current trends and future research directions in the area.
Image Authentication using Visual Cryptography
Venue: arXiv cs.CR 2017
Year: 2017

This report gives a novel technique of image encryption and authentication by combining elements of Visual Cryptography and Public Key Cryptography. A prominent attack involving generation of fake shares to cheat honest users has been described and a demonstration of the proposed system employing a centralised server to generate shares and authenticate them on the basis of requests is made as a counter to the described attack.
Distance to Center of Mass Encoding for Instance Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

The instance segmentation can be considered an extension of the object detection problem where bounding boxes are replaced by object contours. Strictly speaking the problem requires to identify each pixel instance and class independently of the artifice used for this mean. The advantage of instance segmentation over the usual object detection lies in the precise delineation of objects improving object localization. Additionally, object contours allow the evaluation of partial occlusion with basic image processing algorithms. This work approaches the instance segmentation problem as an annotation problem and presents a novel technique to encode and decode ground truth annotations. We propose a mathematical representation of instances that any deep semantic segmentation model can learn and generalize. Each individual instance is represented by a center of mass and a field of vectors pointing to it. This encoding technique has been denominated Distance to Center of Mass Encoding (DCME).
Conditions on Shifted Passivity of Port-Hamiltonian Systems
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we examine the shifted passivity property of port-Hamiltonian systems. Shifted passivity accounts for the fact that in many applications the desired steady-state values of the input and output variables are nonzero, and thus one is interested in passivity with respect to the shifted signals. We consider port-Hamiltonian systems with strictly convex Hamiltonian, and derive conditions under which shifted passivity is guaranteed. In case the Hamiltonian is quadratic and state dependency appears in an affine manner in the dissipation and interconnection matrices, our conditions reduce to negative semidefiniteness of an appropriately constructed constant matrix. Moreover, we elaborate on how these conditions can be extended to the case when the shifted passivity property can be enforced via output feedback, thus paving the path for controller design. Stability of forced equilibria of the system is analyzed invoking the proposed passivity conditions. The utility and relevance of the results are illustrated with their application to a 6th order synchronous generator model as well as a controlled rigid body system.
SMT Queries Decomposition and Caching in Semi-Symbolic Model Checking
Venue: arXiv cs.PL 2017
Year: 2017

In semi-symbolic (control-explicit data-symbolic) model checking the state-space explosion problem is fought by representing sets of states by first-order formulas over the bit-vector theory. In this model checking approach, most of the verification time is spent in an SMT solver on deciding satisfiability of quantified queries, which represent equality of symbolic states. In this paper, we introduce a new scheme for decomposition of symbolic states, which can be used to significantly improve the performance of any semi-symbolic model checker. Using the decomposition, a model checker can issue much simpler and smaller queries to the solver when compared to the original case. Some SMT calls may be even avoided completely, as the satisfaction of some of the simplified formulas can be decided syntactically. Moreover, the decomposition allows for an efficient caching scheme for quantified formulas. To support our theoretical contribution, we show the performance gain of our model checker SymDIVINE on a set of examples from the Software Verification Competition.
SHIP: A Scalable High-performance IPv6 Lookup Algorithm that Exploits Prefix Characteristics
Venue: arXiv cs.DS 2017
Year: 2017

Due to the emergence of new network applications, current IP lookup engines must support high-bandwidth, low lookup latency and the ongoing growth of IPv6 networks. However, existing solutions are not designed to address jointly those three requirements. This paper introduces SHIP, an IPv6 lookup algorithm that exploits prefix characteristics to build a two-level data structure designed to meet future application requirements. Using both prefix length distribution and prefix density, SHIP first clusters prefixes into groups sharing similar characteristics, then it builds a hybrid trie-tree for each prefix group. The compact and scalable data structure built can be stored in on-chip low-latency memories, and allows the traversal process to be parallelized and pipelined at each level in order to support high packet bandwidth. Evaluated on real and synthetic prefix tables holding up to 580 k IPv6 prefixes, SHIP has a logarithmic scaling factor in terms of the number of memory accesses, and a linear memory consumption scaling. Using the largest synthetic prefix table, simulations show that compared to other well-known approaches, SHIP uses at least 44% less memory per prefix, while reducing the memory latency by 61%.
JADE: Joint Autoencoders for Dis-Entanglement
Venue: arXiv cs.LG 2017
Year: 2017

The problem of feature disentanglement has been explored in the literature, for the purpose of image and video processing and text analysis. State-of-the-art methods for disentangling feature representations rely on the presence of many labeled samples. In this work, we present a novel method for disentangling factors of variation in data-scarce regimes. Specifically, we explore the application of feature disentangling for the problem of supervised classification in a setting where few labeled samples exist, and there are no unlabeled samples for use in unsupervised training. Instead, a similar datasets exists which shares at least one direction of variation with the sample-constrained datasets. We train our model end-to-end using the framework of variational autoencoders and are able to experimentally demonstrate that using an auxiliary dataset with similar variation factors contribute positively to classification performance, yielding competitive results with the state-of-the-art in unsupervised learning.
Neural Ranking Models with Multiple Document Fields
Venue: arXiv cs.IR 2017
Year: 2017

Deep neural networks have recently shown promise in the ad-hoc retrieval task. However, such models have often been based on one field of the document, for example considering document title only or document body only. Since in practice documents typically have multiple fields, and given that non-neural ranking models such as BM25F have been developed to take advantage of document structure, this paper investigates how neural models can deal with multiple document fields. We introduce a model that can consume short text fields such as document title and long text fields such as document body. It can also handle multi-instance fields with variable number of instances, for example where each document has zero or more instances of incoming anchor text. Since fields vary in coverage and quality, we introduce a masking method to handle missing field instances, as well as a field-level dropout method to avoid relying too much on any one field. As in the studies of non-neural field weighting, we find it is better for the ranker to score the whole document jointly, rather than generate a per-field score and aggregate. We find that different document fields may match different aspects of the query and therefore benefit from comparing with separate representations of the query text. The combination of techniques introduced here leads to a neural ranker that can take advantage of full document structure, including multiple instance and missing instance data, of variable length. The techniques significantly enhance the performance of the ranker, and also outperform a learning to rank baseline with hand-crafted features.
D numbers theory based game-theoretic framework in adversarial decision making under fuzzy environment
Venue: arXiv cs.AI 2017
Year: 2017

Adversarial decision making is a particular type of decision making problem where the gain a decision maker obtains as a result of his decisions is affected by the actions taken by others. Representation of alternatives' evaluations and methods to find the optimal alternative are two important aspects in the adversarial decision making. The aim of this study is to develop a general framework for solving the adversarial decision making issue under uncertain environment. By combining fuzzy set theory, game theory and D numbers theory (DNT), a DNT based game-theoretic framework for adversarial decision making under fuzzy environment is presented. Within the proposed framework or model, fuzzy set theory is used to model the uncertain evaluations of decision makers to alternatives, the non-exclusiveness among fuzzy evaluations are taken into consideration by using DNT, and the conflict of interests among decision makers is considered in a two-person non-constant sum game theory perspective. An illustrative application is given to demonstrate the effectiveness of the proposed model. This work, on one hand, has developed an effective framework for adversarial decision making under fuzzy environment; One the other hand, it has further improved the basis of DNT as a generalization of Dempster-Shafer theory for uncertainty reasoning.
A Near-optimal Algorithm for Edge Connectivity-based Hierarchical Graph Decomposition
Venue: arXiv cs.DS 2017
Year: 2017

Driven by many applications in graph analytics, the problem of computing $k$-edge connected components ($k$-ECCs) of a graph $G$ for a user-given $k$ has been extensively studied recently. In this paper, we investigate the problem of constructing the hierarchy of edge connectivity-based graph decomposition, which compactly represents the $k$-ECCs of a graph for all possible $k$ values. This is based on the fact that each $k$-ECC is entirely contained in a $(k-1)$-ECC. In contrast to the existing approaches that conduct the computation either in a bottom-up or a top-down manner, we propose a binary search-based framework which invokes a $k$-ECC computation algorithm as a black box. Let $T_{kecc}(G)$ be the time complexity of computing all $k$-ECCs of $G$ for a specific $k$ value. We prove that the time complexity of our framework is ${\cal O}\big( (\log δ(G))\times T_{kecc}(G)\big)$, where $δ(G)$ is the degeneracy of $G$ and equals the maximum value among the minimum vertex degrees of all subgraphs of $G$. As $δ(G)$ is typically small for real-world graphs, this time complexity is optimal up to a logarithmic factor.
Malaria Likelihood Prediction By Effectively Surveying Households Using Deep Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

We build a deep reinforcement learning (RL) agent that can predict the likelihood of an individual testing positive for malaria by asking questions about their household. The RL agent learns to determine which survey question to ask next and when to stop to make a prediction about their likelihood of malaria based on their responses hitherto. The agent incurs a small penalty for each question asked, and a large reward/penalty for making the correct/wrong prediction; it thus has to learn to balance the length of the survey with the accuracy of its final predictions. Our RL agent is a Deep Q-network that learns a policy directly from the responses to the questions, with an action defined for each possible survey question and for each possible prediction class. We focus on Kenya, where malaria is a massive health burden, and train the RL agent on a dataset of 6481 households from the Kenya Malaria Indicator Survey 2015. To investigate the importance of having survey questions be adaptive to responses, we compare our RL agent to a supervised learning (SL) baseline that fixes its set of survey questions a priori. We evaluate on prediction accuracy and on the number of survey questions asked on a holdout set and find that the RL agent is able to predict with 80% accuracy, using only 2.5 questions on average. In addition, the RL agent learns to survey adaptively to responses and is able to match the SL baseline in prediction accuracy while significantly reducing survey length.
DeepRadiologyNet: Radiologist Level Pathology Detection in CT Head Images
Venue: arXiv cs.CV 2017
Year: 2017

We describe a system to automatically filter clinically significant findings from computerized tomography (CT) head scans, operating at performance levels exceeding that of practicing radiologists. Our system, named DeepRadiologyNet, builds on top of deep convolutional neural networks (CNNs) trained using approximately 3.5 million CT head images gathered from over 24,000 studies taken from January 1, 2015 to August 31, 2015 and January 1, 2016 to April 30 2016 in over 80 clinical sites. For our initial system, we identified 30 phenomenological traits to be recognized in the CT scans. To test the system, we designed a clinical trial using over 4.8 million CT head images (29,925 studies), completely disjoint from the training and validation set, interpreted by 35 US Board Certified radiologists with specialized CT head experience. We measured clinically significant error rates to ascertain whether the performance of DeepRadiologyNet was comparable to or better than that of US Board Certified radiologists. DeepRadiologyNet achieved a clinically significant miss rate of 0.0367% on automatically selected high-confidence studies. Thus, DeepRadiologyNet enables significant reduction in the workload of human radiologists by automatically filtering studies and reporting on the high-confidence ones at an operating point well below the literal error rate for US Board Certified radiologists, estimated at 0.82%.
Semantically Consistent Image Completion with Fine-grained Details
Venue: arXiv cs.CV 2017
Year: 2017

Image completion has achieved significant progress due to advances in generative adversarial networks (GANs). Albeit natural-looking, the synthesized contents still lack details, especially for scenes with complex structures or images with large holes. This is because there exists a gap between low-level reconstruction loss and high-level adversarial loss. To address this issue, we introduce a perceptual network to provide mid-level guidance, which measures the semantical similarity between the synthesized and original contents in a similarity-enhanced space. We conduct a detailed analysis on the effects of different losses and different levels of perceptual features in image completion, showing that there exist complementarity between adversarial training and perceptual features. By combining them together, our model can achieve nearly seamless fusion results in an end-to-end manner. Moreover, we design an effective lightweight generator architecture, which can achieve effective image inpainting with far less parameters. Evaluated on CelebA Face and Paris StreetView dataset, our proposed method significantly outperforms existing methods.
Online Facility Location on Semi-Random Streams
Venue: arXiv cs.DS 2017
Year: 2017

In the streaming model, the order of the stream can significantly affect the difficulty of a problem. A $t$-semirandom stream was introduced as an interpolation between random-order ($t=1$) and adversarial-order ($t=n$) streams where an adversary intercepts a random-order stream and can delay up to $t$ elements at a time. IITK Sublinear Open Problem \#15 asks to find algorithms whose performance degrades smoothly as $t$ increases. We show that the celebrated online facility location algorithm achieves an expected competitive ratio of $O(\frac{\log t}{\log \log t})$. We present a matching lower bound that any randomized algorithm has an expected competitive ratio of $Ω(\frac{\log t}{\log \log t})$. We use this result to construct an $O(1)$-approximate streaming algorithm for $k$-median clustering that stores $O(k \log t)$ points and has $O(k \log t)$ worst-case update time. Our technique generalizes to any dissimilarity measure that satisfies a weak triangle inequality, including $k$-means, $M$-estimators, and $\ell_p$ norms. The special case $t=1$ yields an optimal $O(k)$ space algorithm for random-order streams as well as an optimal $O(nk)$ time algorithm in the RAM model, closing a long line of research on this problem.
BL-MNE: Emerging Heterogeneous Social Network Embedding through Broad Learning with Aligned Autoencoder
Venue: arXiv cs.SI 2017
Year: 2017

Network embedding aims at projecting the network data into a low-dimensional feature space, where the nodes are represented as a unique feature vector and network structure can be effectively preserved. In recent years, more and more online application service sites can be represented as massive and complex networks, which are extremely challenging for traditional machine learning algorithms to deal with. Effective embedding of the complex network data into low-dimension feature representation can both save data storage space and enable traditional machine learning algorithms applicable to handle the network data. Network embedding performance will degrade greatly if the networks are of a sparse structure, like the emerging networks with few connections. In this paper, we propose to learn the embedding representation for a target emerging network based on the broad learning setting, where the emerging network is aligned with other external mature networks at the same time. To solve the problem, a new embedding framework, namely "Deep alIgned autoencoder based eMbEdding" (DIME), is introduced in this paper. DIME handles the diverse link and attribute in a unified analytic based on broad learning, and introduces the multiple aligned attributed heterogeneous social network concept to model the network structure. A set of meta paths are introduced in the paper, which define various kinds of connections among users via the heterogeneous link and attribute information. The closeness among users in the networks are defined as the meta proximity scores, which will be fed into DIME to learn the embedding vectors of users in the emerging network. Extensive experiments have been done on real-world aligned social networks, which have demonstrated the effectiveness of DIME in learning the emerging network embedding vectors.