OpenRaiser/Intern-Atlas huggingface dataset:
Digit Serial Methods with Applications to Division and Square Root (with mechanically checked correctness proofs)
Venue: arXiv cs.NA 2017
Year: 2017

We present a generic digit serial method (DSM) to compute the digits of a real number $V$ . Bounds on these digits, and on the errors in the associated estimates of $V$ formed from these digits, are derived. To illustrate our results, we derive such bounds for a parameterized family of high-radix algorithms for division and square root. These bounds enable a DSM designer to determine, for example, whether a given choice of parameters allows rapid formation and rounding of its approximation to $V$. All our claims are mechanically verified using the HOL-Light theorem prover, and are included in the appendix with commentary.
Improved Algorithms for Scheduling Unsplittable Flows on Paths
Venue: arXiv cs.DS 2017
Year: 2017

In this paper, we investigate offline and online algorithms for rufpp, the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform sizes on a given path with non-uniform edge capacities. rufpp is NP-hard and constant-factor approximation algorithms are known under the no bottleneck assumption (NBA), which stipulates that maximum size of a flow is at most the minimum edge capacity. We study rufpp without the NBA, and present improved online and offline algorithms. We first study offline rufpp for a restricted class of instances called $α$-small, where the size of each flow is at most $α$ times the capacity of its bottleneck edge, and present an $O(\log(1/(1-α)))$-approximation algorithm. Our main result is an online $O(\log\log c_{\max})$-competitive algorithm for rufpp for general instances, where $c_{\max}$ is the largest edge capacities, improving upon the previous best bound of $O(\log c_{\max})$ due to Epstein et al. Our result leads to an offline $O(\min(\log n, \log m, \log\log c_{\max}))$-approximation algorithm and an online $O(\min(\log m, \log\log c_{\max}))$-competitive algorithm for rufpp, where $n$ is the number of flows and $m$ is the number of edges.
Image Denoising via CNNs: An Adversarial Approach
Venue: arXiv cs.CV 2017
Year: 2017

Is it possible to recover an image from its noisy version using convolutional neural networks? This is an interesting problem as convolutional layers are generally used as feature detectors for tasks like classification, segmentation and object detection. We present a new CNN architecture for blind image denoising which synergically combines three architecture components, a multi-scale feature extraction layer which helps in reducing the effect of noise on feature maps, an l_p regularizer which helps in selecting only the appropriate feature maps for the task of reconstruction, and finally a three step training approach which leverages adversarial training to give the final performance boost to the model. The proposed model shows competitive denoising performance when compared to the state-of-the-art approaches.
Modeling and Analysis of Network Dynamics in Complex Communication Networks Using Social Network Methods
Venue: arXiv cs.SI 2017
Year: 2017

Modern communication networks are inherently complex in nature. First of all, they have a large number of heterogeneous components. Secondly, their connectivity is extremely dynamic. Nodes can come and go, links can be removed and added over time. Traditional modeling and simulation techniques amalgamate or ignore such dynamics and therefore, are unable to represent them. Complex communication networks are therefore better modeled as mathematical structures called graphs. Modeling as graphs allows for the application of complex techniques such as various network based analysis techniques. While this is a very important and much needed skill for communication networks researchers and engineers, to the best of our knowledge, currently there is no resource describing these details. In this paper, we give a concise but comprehensive review of modeling complex communication networks as graphs. We also show how to apply complex social network analysis on these models besides a demonstration of formal modeling network dynamics.
Video Object Segmentation with Re-identification
Venue: arXiv cs.CV 2017
Year: 2017

Conventional video segmentation methods often rely on temporal continuity to propagate masks. Such an assumption suffers from issues like drifting and inability to handle large displacement. To overcome these issues, we formulate an effective mechanism to prevent the target from being lost via adaptive object re-identification. Specifically, our Video Object Segmentation with Re-identification (VS-ReID) model includes a mask propagation module and a ReID module. The former module produces an initial probability map by flow warping while the latter module retrieves missing instances by adaptive matching. With these two modules iteratively applied, our VS-ReID records a global mean (Region Jaccard and Boundary F measure) of 0.699, the best performance in 2017 DAVIS Challenge.
Reframing Societal Discourse as Requirements Negotiation: Vision Statement
Venue: arXiv cs.SE 2017
Year: 2017

Challenges in spatial planning include adjusting settlement patterns to increasing or shrinking populations; it also includes organizing food delivery in rural and peripheral environments. Discourse typically starts with an open problem and the search for a holistic and innovative solution. Software will often be needed to implement the innovation. Spatial planning problems are characterized by large and heterogeneous groups of stakeholders, such as municipalities, companies, interest groups, citizens, women and men, young people and children. Current techniques for participation are slow, laborious and costly, and they tend to miss out on many stakeholders or interest groups. We propose a triple shift in perspective: (1) Discourse is reframed as a requirements process with the explicit goal to state software, hardware, and organizational requirements. (2) Due to the above-mentioned characteristics of spatial planning problems, we suggest using techniques of requirements engineering (RE) and CrowdRE for getting stakeholders (e.g. user groups) involved. (3) We propose video as a medium for communicating problems, solution alternatives, and arguments effectively within a mixed crowd of officials, citizens, children and elderly people. Although few spatial planning problems can be solved by software alone, this new perspective helps to focus discussions anyway. RE techniques can assist in finding common ground despite the heterogeneous group of stakeholders, e.g. citizens. Digital requirements and video are well-suited for facilitating distribution, feedback, and discourse via the internet. In this paper, we propose this new perspective as a timely opportunity for the spatial planning domain - and as an increasingly important application domain of CrowdRE.
Learning the kernel matrix by resampling
Venue: arXiv cs.LG 2017
Year: 2017

In this abstract paper, we introduce a new kernel learning method by a nonparametric density estimator. The estimator consists of a group of k-centroids clusterings. Each clustering randomly selects data points with randomly selected features as its centroids, and learns a one-hot encoder by one-nearest-neighbor optimization. The estimator generates a sparse representation for each data point. Then, we construct a nonlinear kernel matrix from the sparse representation of data. One major advantage of the proposed kernel method is that it is relatively insensitive to its free parameters, and therefore, it can produce reasonable results without parameter tuning. Another advantage is that it is simple. We conjecture that the proposed method can find its applications in many learning tasks or methods where sparse representation or kernel matrix is explored. In this preliminary study, we have applied the kernel matrix to spectral clustering. Our experimental results demonstrate that the kernel generated by the proposed method outperforms the well-tuned Gaussian RBF kernel. This abstract paper is used to protect the idea, full versions will be updated later.
Self-Supervised Learning for Spinal MRIs
Venue: arXiv cs.CV 2017
Year: 2017

A significant proportion of patients scanned in a clinical setting have follow-up scans. We show in this work that such longitudinal scans alone can be used as a form of 'free' self-supervision for training a deep network. We demonstrate this self-supervised learning for the case of T2-weighted sagittal lumbar Magnetic Resonance Images (MRIs). A Siamese convolutional neural network (CNN) is trained using two losses: (i) a contrastive loss on whether the scan is of the same person (i.e. longitudinal) or not, together with (ii) a classification loss on predicting the level of vertebral bodies. The performance of this pre-trained network is then assessed on a grading classification task. We experiment on a dataset of 1016 subjects, 423 possessing follow-up scans, with the end goal of learning the disc degeneration radiological gradings attached to the intervertebral discs. We show that the performance of the pre-trained CNN on the supervised classification task is (i) superior to that of a network trained from scratch; and (ii) requires far fewer annotated training samples to reach an equivalent performance to that of the network trained from scratch.
A Lightweight Front-end Tool for Interactive Entity Population
Venue: arXiv cs.CL 2017
Year: 2017

Entity population, a task of collecting entities that belong to a particular category, has attracted attention from vertical domains. There is still a high demand for creating entity dictionaries in vertical domains, which are not covered by existing knowledge bases. We develop a lightweight front-end tool for facilitating interactive entity population. We implement key components necessary for effective interactive entity population: 1) GUI-based dashboards to quickly modify an entity dictionary, and 2) entity highlighting on documents for quickly viewing the current progress. We aim to reduce user cost from beginning to end, including package installation and maintenance. The implementation enables users to use this tool on their web browsers without any additional packages --- users can focus on their missions to create entity dictionaries. Moreover, an entity expansion module is implemented as external APIs. This design makes it easy to continuously improve interactive entity population pipelines. We are making our demo publicly available (http://bit.ly/luwak-demo).
Car sharing through the data analysis lens
Venue: arXiv cs.CY 2017
Year: 2017

Car sharing is one the pillars of a smart transportation infrastructure, as it is expected to reduce traffic congestion, parking demands and pollution in our cities. From the point of view of demand modelling, car sharing is a weak signal in the city landscape: only a small percentage of the population uses it, and thus it is difficult to study reliably with traditional techniques such as households travel diaries. In this work, we depart from these traditional approaches and we rely on web-based, digital records about vehicle availability in 10 European cities for one of the major active car sharing operators. We discuss how vehicles are used, what are the main characteristics of car sharing trips, whether events happening in certain areas are predictable or not, and how the spatio-temporal information about vehicle availability can be used to infer how different zones in a city are used by customers. We conclude the paper by presenting a direct application of the analysis of the dataset, aimed at identifying where to locate maintenance facilities within the car sharing operational area.
Line Segment Covering of Cells in Arrangements
Venue: arXiv cs.CG 2017
Year: 2017

Given a collection $L$ of line segments, we consider its arrangement and study the problem of covering all cells with line segments of $L$. That is, we want to find a minimum-size set $L'$ of line segments such that every cell in the arrangement has a line from $L'$ defining its boundary. We show that the problem is NP-hard, even when all segments are axis-aligned. In fact, the problem is still NP-hard when we only need to cover rectangular cells of the arrangement. For the latter problem we also show that it is fixed parameter tractable with respect to the size of the optimal solution. Finally we provide a linear time algorithm for the case where cells of the arrangement are created by recursively subdividing a rectangle using horizontal and vertical cutting segments.
Kernalised Multi-resolution Convnet for Visual Tracking
Venue: arXiv cs.CV 2017
Year: 2017

Visual tracking is intrinsically a temporal problem. Discriminative Correlation Filters (DCF) have demonstrated excellent performance for high-speed generic visual object tracking. Built upon their seminal work, there has been a plethora of recent improvements relying on convolutional neural network (CNN) pretrained on ImageNet as a feature extractor for visual tracking. However, most of their works relying on ad hoc analysis to design the weights for different layers either using boosting or hedging techniques as an ensemble tracker. In this paper, we go beyond the conventional DCF framework and propose a Kernalised Multi-resolution Convnet (KMC) formulation that utilises hierarchical response maps to directly output the target movement. When directly deployed the learnt network to predict the unseen challenging UAV tracking dataset without any weight adjustment, the proposed model consistently achieves excellent tracking performance. Moreover, the transfered multi-reslution CNN renders it possible to be integrated into the RNN temporal learning framework, therefore opening the door on the end-to-end temporal deep learning (TDL) for visual tracking.
On Quantifying Knowledge Segregation in Society
Venue: arXiv cs.SI 2017
Year: 2017

With rapid increase in online information consumption, especially via social media sites, there have been concerns on whether people are getting selective exposure to a biased subset of the information space, where a user is receiving more of what she already knows, and thereby potentially getting trapped in echo chambers or filter bubbles. Even though such concerns are being debated for some time, it is not clear how to quantify such echo chamber effect. In this position paper, we introduce Information Segregation (or Informational Segregation) measures, which follow the long lines of work on residential segregation. We believe that information segregation nicely captures the notion of exposure to different information by different population in a society, and would help in quantifying the extent of social media sites offering selective (or diverse) information to their users.
Maximum-Area Quadrilateral in a Convex Polygon, Revisited
Venue: arXiv cs.CG 2017
Year: 2017

In this note we show by example that the algorithm presented in 1979 by Dobkin and Snyder for finding the largest-area k-gon that is inscribed in a convex polygon fails to find the optimal solution for k=4. This question, posed by Keikha et al. where they showed that the Dobkin Snyder algorithm fails for k=3.
VLDL Satisfiability and Model Checking via Tree Automata
Venue: arXiv cs.LO 2017
Year: 2017

We present novel algorithms solving the satisfiability problem and the model checking problem for Visibly Linear Dynamic Logic (VLDL) in asymptotically optimal time via a reduction to the emptiness problem for tree automata with Büchi acceptance. Since VLDL allows for the specification of important properties of recursive systems, this reduction enables the efficient analysis of such systems. Furthermore, as the problem of tree automata emptiness is well-studied, this reduction enables leveraging the mature algorithms and tools for that problem in order to solve the satisfiability problem and the model checking problem for VLDL.
The University of Edinburgh's Neural MT Systems for WMT17
Venue: arXiv cs.CL 2017
Year: 2017

This paper describes the University of Edinburgh's submissions to the WMT17 shared news translation and biomedical translation tasks. We participated in 12 translation directions for news, translating between English and Czech, German, Latvian, Russian, Turkish and Chinese. For the biomedical task we submitted systems for English to Czech, German, Polish and Romanian. Our systems are neural machine translation systems trained with Nematus, an attentional encoder-decoder. We follow our setup from last year and build BPE-based models with parallel and back-translated monolingual training data. Novelties this year include the use of deep architectures, layer normalization, and more compact models due to weight tying and improvements in BPE segmentations. We perform extensive ablative experiments, reporting on the effectivenes of layer normalization, deep architectures, and different ensembling techniques.
Exact values for three domination-like problems in circular and infinite grid graphs of small height
Venue: arXiv cs.DM 2017
Year: 2017

In this paper we study three domination-like problems, namely identifying codes, locating-dominating codes, and locating-total-dominating codes. We are interested in finding the minimum cardinality of such codes in circular and infinite grid graphs of given height. We provide an alternate proof for already known results, as well as new results. These were obtained by a computer search based on a generic framework, that we developed earlier, for the search of a minimum labeling satisfying a pseudo-d-local property in rotagraphs.
Noninvasive Corneal Image-Based Gaze Measurement System
Venue: arXiv cs.HC 2017
Year: 2017

Gaze tracking is an important technology as the system can give information about a person from what and where the person is seeing. There have been many attempts to make robust and accurate gaze trackers using either monitor or wearable devices. However, those contraptions often require fine individual calibration per session and/or require a person wearing a device, which may not be suitable for certain situations. In this paper, we propose a robust and a completely noninvasive gaze tracking system that involves neither complex calibrations nor the use of wearable devices. We achieve this via direct eye reflection analysis by building a real-time system that effectively enables it. We also show several interesting applications for our system including experiments with young children.
Aligned and Non-Aligned Double JPEG Detection Using Convolutional Neural Networks
Venue: arXiv cs.CR 2017
Year: 2017

Due to the wide diffusion of JPEG coding standard, the image forensic community has devoted significant attention to the development of double JPEG (DJPEG) compression detectors through the years. The ability of detecting whether an image has been compressed twice provides paramount information toward image authenticity assessment. Given the trend recently gained by convolutional neural networks (CNN) in many computer vision tasks, in this paper we propose to use CNNs for aligned and non-aligned double JPEG compression detection. In particular, we explore the capability of CNNs to capture DJPEG artifacts directly from images. Results show that the proposed CNN-based detectors achieve good performance even with small size images (i.e., 64x64), outperforming state-of-the-art solutions, especially in the non-aligned case. Besides, good results are also achieved in the commonly-recognized challenging case in which the first quality factor is larger than the second one.
Combining Keystroke Dynamics and Face Recognition for User Verification
Venue: arXiv cs.HC 2017
Year: 2017

The massive explosion and ubiquity of computing devices and the outreach of the web have been the most defining events of the century so far. As more and more people gain access to the internet, traditional know-something and have-something authentication methods such as PINs and passwords are proving to be insufficient for prohibiting unauthorized access to increasingly personal data on the web. Therefore, the need of the hour is a user-verification system that is not only more reliable and secure, but also unobtrusive and minimalistic. Keystroke Dynamics is a novel Biometric Technique; it is not only unobtrusive, but also transparent and inexpensive. The fusion of keystroke dynamics and Face Recognition engenders the most desirable characteristics of a verification system. Our implementation uses Hidden Markov Models (HMM) for modelling the Keystroke Dynamics, with the help of two widely used Feature Vectors: Keypress Latency and Keypress Duration. On the other hand, Face Recognition makes use of the traditional Eigenfaces approach.The results show that the system has a high precision, with a False Acceptance Rate of 5.4% and a False Rejection Rate of 9.2%. Moreover, it is also future-proof, as the hardware requirements, i.e. camera and keyboard (physical or on-screen), have become an indispensable part of modern computing.
Network Community Detection: A Review and Visual Survey
Venue: arXiv cs.SI 2017
Year: 2017

Community structure is an important area of research. It has received a considerable attention from the scientific community. Despite its importance, one of the key problems in locating information about community detection is the diverse spread of related articles across various disciplines. To the best of our knowledge, there is no current comprehensive review of recent literature which uses a scientometric analysis using complex networks analysis covering all relevant articles from the Web of Science (WoS). Here we present a visual survey of key literature using CiteSpace. The idea is to identify emerging trends besides using network techniques to examine the evolution of the domain. Towards that end, we identify the most influential, central, as well as active nodes using scientometric analyses. We examine authors, key articles, cited references, core subject categories, key journals, institutions, as well as countries. The exploration of the scientometric literature of the domain reveals that Yong Wang is a pivot node with the highest centrality. Additionally, we have observed that Mark Newman is the most highly cited author in the network. We have also identified that the journal, "Reviews of Modern Physics" has the strongest citation burst. In terms of cited documents, an article by Andrea Lancichinetti has the highest centrality score. We have also discovered that the origin of the key publications in this domain is from the United States. Whereas Scotland has the strongest and longest citation burst. Additionally, we have found that the categories of "Computer Science" and "Engineering" lead other categories based on frequency and centrality respectively.
Trust Implications of DDoS Protection in Online Elections
Venue: arXiv cs.CR 2017
Year: 2017

Online elections make a natural target for distributed denial of service attacks. Election agencies wary of disruptions to voting may procure DDoS protection services from a cloud provider. However, current DDoS detection and mitigation methods come at the cost of significantly increased trust in the cloud provider. In this paper we examine the security implications of denial-of-service prevention in the context of the 2017 state election in Western Australia, revealing a complex interaction between actors and infrastructure extending far beyond its borders. Based on the publicly observable properties of this deployment, we outline several attack scenarios including one that could allow a nation state to acquire the credentials necessary to man-in-the-middle a foreign election in the context of an unrelated domestic law enforcement or national security operation, and we argue that a fundamental tension currently exists between trust and availability in online elections.