OpenRaiser/Intern-Atlas huggingface dataset:
Simple Yet Efficient Content Based Video Copy Detection
Venue: arXiv cs.MM 2018
Year: 2018

Given a collection of videos, how to detect content-based copies efficiently with high accuracy? Detecting copies in large video collections still remains one of the major challenges of multimedia retrieval. While many video copy detection approaches show high computation times and insufficient quality, we propose a new efficient content-based video copy detection algorithm improving both aspects. The idea of our approach consists in utilizing self-similarity matrices as video descriptors in order to capture different visual properties. We benchmark our algorithm on the MuscleVCD ST1 benchmark dataset and show that our approach is able to achieve a score of 100\% and a score of at least 93\% in a wide range of parameters.
A System's Perspective Towards an Architecture Framework for Safe Automated Vehicles
Venue: arXiv cs.SY 2018
Year: 2018

With an increasing degree of automation, automated vehicle systems become more complex in terms of functional components as well as interconnected hardware and software components. Thus, holistic systems engineering becomes a severe challenge. Emergent properties like system safety are not solely arguable in singular viewpoints such as structural representations of software or electrical wiring (e.g. fault tolerant). This states the need to get several viewpoints on a system and describe correspondences between these views in order to enable traceability of emergent system properties. Today, the most abstract view found in architecture frameworks is a logical description of system functions which structures the system in terms of information flow and functional components. In this article we extend established system viewpoints towards a capability-based assessment of an automated vehicle and conduct an exemplary safety analysis to derive behavioral safety requirements. These requirements can afterwards be attributed to different viewpoints in an architecture frameworks and thus be integrated into a development process for automated vehicles.
Inherent Brain Segmentation Quality Control from Fully ConvNet Monte Carlo Sampling
Venue: arXiv cs.CV 2018
Year: 2018

We introduce inherent measures for effective quality control of brain segmentation based on a Bayesian fully convolutional neural network, using model uncertainty. Monte Carlo samples from the posterior distribution are efficiently generated using dropout at test time. Based on these samples, we introduce next to a voxel-wise uncertainty map also three metrics for structure-wise uncertainty. We then incorporate these structure-wise uncertainty in group analyses as a measure of confidence in the observation. Our results show that the metrics are highly correlated to segmentation accuracy and therefore present an inherent measure of segmentation quality. Furthermore, group analysis with uncertainty results in effect sizes closer to that of manual annotations. The introduced uncertainty metrics can not only be very useful in translation to clinical practice but also provide automated quality control and group analyses in processing large data repositories.
Cell Selection with Deep Reinforcement Learning in Sparse Mobile Crowdsensing
Venue: arXiv cs.AI 2018
Year: 2018

Sparse Mobile CrowdSensing (MCS) is a novel MCS paradigm where data inference is incorporated into the MCS process for reducing sensing costs while its quality is guaranteed. Since the sensed data from different cells (sub-areas) of the target sensing area will probably lead to diverse levels of inference data quality, cell selection (i.e., choose which cells of the target area to collect sensed data from participants) is a critical issue that will impact the total amount of data that requires to be collected (i.e., data collection costs) for ensuring a certain level of quality. To address this issue, this paper proposes a Deep Reinforcement learning based Cell selection mechanism for Sparse MCS, called DR-Cell. First, we properly model the key concepts in reinforcement learning including state, action, and reward, and then propose to use a deep recurrent Q-network for learning the Q-function that can help decide which cell is a better choice under a certain state during cell selection. Furthermore, we leverage the transfer learning techniques to reduce the amount of data required for training the Q-function if there are multiple correlated MCS tasks that need to be conducted in the same target area. Experiments on various real-life sensing datasets verify the effectiveness of DR-Cell over the state-of-the-art cell selection mechanisms in Sparse MCS by reducing up to 15% of sensed cells with the same data inference quality guarantee.
Unsupervised Prostate Cancer Detection on H&E using Convolutional Adversarial Autoencoders
Venue: arXiv cs.CV 2018
Year: 2018

We propose an unsupervised method using self-clustering convolutional adversarial autoencoders to classify prostate tissue as tumor or non-tumor without any labeled training data. The clustering method is integrated into the training of the autoencoder and requires only little post-processing. Our network trains on hematoxylin and eosin (H&E) input patches and we tested two different reconstruction targets, H&E and immunohistochemistry (IHC). We show that antibody-driven feature learning using IHC helps the network to learn relevant features for the clustering task. Our network achieves a F1 score of 0.62 using only a small set of validation labels to assign classes to clusters.
A Simple Capacity Lower Bound for Communication with Superimposed Pilots
Venue: arXiv cs.IT 2018
Year: 2018

We present a novel closed-form lower bound on the Gaussian-input mutual information for noncoherent communication (i.e., in which neither transmitter nor receiver are cognizant of the fading state) over a frequency-flat fading channel with additive noise. Our bound yields positive (non-trivial) values even in the most challenging case of zero-mean fast fading, a regime in which the conventional approach of orthogonal time-multiplexed pilots is unavailing and for which, to the best of the author's knowledge, no simple analytical bound is known. Its derivation relies on endowing the transmit signal with a non-zero mean, which can be interpreted as a pilot symbol that is additively superimposed onto the information-bearing Gaussian signal. The optimal fraction of transmit power that one should dedicate to this pilot is computed in closed form and shown to tend to one half at low SNR and to a limit above $2-\sqrt{2} \approx 0.586$ at high SNR. We further show how one can refine the bound for the general case of non-zero mean fading. Finally, we state an extension of our bound to the MIMO setting and apply it to compare superimposed vs. orthogonal pilots on the SISO Rayleigh block fading channel.
Topology-induced Enhancement of Mappings
Venue: arXiv cs.DC 2018
Year: 2018

In this paper we propose a new method to enhance a mapping $μ(\cdot)$ of a parallel application's computational tasks to the processing elements (PEs) of a parallel computer. The idea behind our method \mswap is to enhance such a mapping by drawing on the observation that many topologies take the form of a partial cube. This class of graphs includes all rectangular and cubic meshes, any such torus with even extensions in each dimension, all hypercubes, and all trees. Following previous work, we represent the parallel application and the parallel computer by graphs $G_a = (V_a, E_a)$ and $G_p = (V_p, E_p)$. $G_p$ being a partial cube allows us to label its vertices, the PEs, by bitvectors such that the cost of exchanging one unit of information between two vertices $u_p$ and $v_p$ of $G_p$ amounts to the Hamming distance between the labels of $u_p$ and $v_p$. By transferring these bitvectors from $V_p$ to $V_a$ via $μ^{-1}(\cdot)$ and extending them to be unique on $V_a$, we can enhance $μ(\cdot)$ by swapping labels of $V_a$ in a new way. Pairs of swapped labels are local \wrt the PEs, but not \wrt $G_a$. Moreover, permutations of the bitvectors' entries give rise to a plethora of hierarchies on the PEs. Through these hierarchies we turn \mswap into a hierarchical method for improving $μ(\cdot)$ that is complementary to state-of-the-art methods for computing $μ(\cdot)$ in the first place. In our experiments we use \mswap to enhance mappings of complex networks onto rectangular meshes and tori with 256 and 512 nodes, as well as hypercubes with 256 nodes. It turns out that common quality measures of mappings derived from state-of-the-art algorithms can be improved considerably.
Heuristic and Cost-based Optimization for Diverse Provenance Tasks
Venue: arXiv cs.DB 2018
Year: 2018

A well-established technique for capturing database provenance as annotations on data is to instrument queries to propagate such annotations. However, even sophisticated query optimizers often fail to produce efficient execution plans for instrumented queries. We develop provenance-aware optimization techniques to address this problem. Specifically, we study algebraic equivalences targeted at instrumented queries and alternative ways of instrumenting queries for provenance capture. Furthermore, we present an extensible heuristic and cost-based optimization framework utilizing these optimizations. Our experiments confirm that these optimizations are highly effective, improving performance by several orders of magnitude for diverse provenance tasks.
Unsupervised Probabilistic Deformation Modeling for Robust Diffeomorphic Registration
Venue: arXiv cs.CV 2018
Year: 2018

We propose a deformable registration algorithm based on unsupervised learning of a low-dimensional probabilistic parameterization of deformations. We model registration in a probabilistic and generative fashion, by applying a conditional variational autoencoder (CVAE) network. This model enables to also generate normal or pathological deformations of any new image based on the probabilistic latent space. Most recent learning-based registration algorithms use supervised labels or deformation models, that miss important properties such as diffeomorphism and sufficiently regular deformation fields. In this work, we constrain transformations to be diffeomorphic by using a differentiable exponentiation layer with a symmetric loss function. We evaluated our method on 330 cardiac MR sequences and demonstrate robust intra-subject registration results comparable to two state-of-the-art methods but with more regular deformation fields compared to a recent learning-based algorithm. Our method reached a mean DICE score of 78.3% and a mean Hausdorff distance of 7.9mm. In two preliminary experiments, we illustrate the model's abilities to transport pathological deformations to healthy subjects and to cluster five diseases in the unsupervised deformation encoding space with a classification performance of 70%.
Anonymous Single-Sign-On for n designated services with traceability
Venue: arXiv cs.CR 2018
Year: 2018

Anonymous Single-Sign-On authentication schemes have been proposed to allow users to access a service protected by a verifier without revealing their identity which has become more important due to the introduction of strong privacy regulations. In this paper we describe a new approach whereby anonymous authentication to different verifiers is achieved via authorisation tags and pseudonyms. The particular innovation of our scheme is authentication can only occur between a user and its designated verifier for a service, and the verification cannot be performed by any other verifier. The benefit of this authentication approach is that it prevents information leakage of a user's service access information, even if the verifiers for these services collude which each other. Our scheme also supports a trusted third party who is authorised to de-anonymise the user and reveal her whole services access information if required. Furthermore, our scheme is lightweight because it does not rely on attribute or policy-based signature schemes to enable access to multiple services. The scheme's security model is given together with a security proof, an implementation and a performance evaluation.
Minimizing Area and Energy of Deep Learning Hardware Design Using Collective Low Precision and Structured Compression
Venue: arXiv cs.NE 2018
Year: 2018

Deep learning algorithms have shown tremendous success in many recognition tasks; however, these algorithms typically include a deep neural network (DNN) structure and a large number of parameters, which makes it challenging to implement them on power/area-constrained embedded platforms. To reduce the network size, several studies investigated compression by introducing element-wise or row-/column-/block-wise sparsity via pruning and regularization. In addition, many recent works have focused on reducing precision of activations and weights with some reducing down to a single bit. However, combining various sparsity structures with binarized or very-low-precision (2-3 bit) neural networks have not been comprehensively explored. In this work, we present design techniques for minimum-area/-energy DNN hardware with minimal degradation in accuracy. During training, both binarization/low-precision and structured sparsity are applied as constraints to find the smallest memory footprint for a given deep learning algorithm. The DNN model for CIFAR-10 dataset with weight memory reduction of 50X exhibits accuracy comparable to that of the floating-point counterpart. Area, performance and energy results of DNN hardware in 40nm CMOS are reported for the MNIST dataset. The optimized DNN that combines 8X structured compression and 3-bit weight precision showed 98.4% accuracy at 20nJ per classification.
A Predictive Model for Notional Anaphora in English
Venue: arXiv cs.CL 2018
Year: 2018

Notional anaphors are pronouns which disagree with their antecedents' grammatical categories for notional reasons, such as plural to singular agreement in: 'the government ... they'. Since such cases are rare and conflict with evidence from strictly agreeing cases ('the government ... it'), they present a substantial challenge to both coreference resolution and referring expression generation. Using the OntoNotes corpus, this paper takes an ensemble approach to predicting English notional anaphora in context on the basis of the largest empirical data to date. In addition to state of the art prediction accuracy, the results suggest that theoretical approaches positing a plural construal at the antecedent's utterance are insufficient, and that circumstances at the anaphor's utterance location, as well as global factors such as genre, have a strong effect on the choice of referring expression.
On Reducing IoT Service Delay via Fog Offloading
Venue: arXiv cs.NI 2018
Year: 2018

With the Internet of Things (IoT) becoming a major component of our daily life, understanding how to improve the quality of service (QoS) for IoT applications through fog computing is becoming an important problem. In this paper, we introduce a general framework for IoT-fog-cloud applications, and propose a delay-minimizing collaboration and offloading policy for fog-capable devices that aims to reduce the service delay for IoT applications. We then develop an analytical model to evaluate our policy and show how the proposed framework helps to reduce IoT service delay.
GritNet: Student Performance Prediction with Deep Learning
Venue: arXiv cs.LG 2018
Year: 2018

Student performance prediction - where a machine forecasts the future performance of students as they interact with online coursework - is a challenging problem. Reliable early-stage predictions of a student's future performance could be critical to facilitate timely educational interventions during a course. However, very few prior studies have explored this problem from a deep learning perspective. In this paper, we recast the student performance prediction problem as a sequential event prediction problem and propose a new deep learning based algorithm, termed GritNet, which builds upon the bidirectional long short term memory (BLSTM). Our results, from real Udacity students' graduation predictions, show that the GritNet not only consistently outperforms the standard logistic-regression based method, but that improvements are substantially pronounced in the first few weeks when accurate predictions are most challenging.
Personal vs. Know-How Contacts: Which Matter More in Wiki Elections?
Venue: arXiv cs.SI 2018
Year: 2018

The use of social media affects the real world as well. This study relies on specific social network measures to investigate the interactions between election participants and the importance of their contacts. It investigates whether personal contacts matter more than know-how contacts in wiki election nominations and voting participation by using standard tools such as Pajek and Gephi. It further evaluates the significance of a personal contacts in online wiki elections through a number of different graph-based influence identification methods. Additionally, the basic characteristics and cohesive groups in the wiki vote network are explored. This work contributes by discovering the significance of personal contacts over know-how contacts of a person in online elections. It is found that personal contacts, i.e. immediate neighbors (degree centrality) and neighborhood (k-neighbors) of a person have a positive effect on a person's nomination as an administrator and also contribute to the active participation of voters in voting. Moreover, know-how contacts, analyzed by means of measures such as betweenness and closeness centralities, have a relatively insignificant effect on the selection of a person. However, know-how contacts in terms of betweenness centrality for passing information in the network can positively contribute only to the voting process. These contacts also measured in terms of influence domain and PageRank can play a vital role in the selection of an admin. Additionally, such contacts in terms of reachability and brokerage roles have a positive association with the voting process.
Accurate Deep Direct Geo-Localization from Ground Imagery and Phone-Grade GPS
Venue: arXiv cs.CV 2018
Year: 2018

One of the most critical topics in autonomous driving or ride-sharing technology is to accurately localize vehicles in the world frame. In addition to common multi-view camera systems, it usually also relies on industrial grade sensors, such as LiDAR, differential GPS, high precision IMU, and etc. In this paper, we develop an approach to provide an effective solution to this problem. We propose a method to train a geo-spatial deep neural network (CNN+LSTM) to predict accurate geo-locations (latitude and longitude) using only ordinary ground imagery and low accuracy phone-grade GPS. We evaluate our approach on the open dataset released during ACM Multimedia 2017 Grand Challenge. Having ground truth locations for training, we are able to reach nearly lane-level accuracy. We also evaluate the proposed method on our own collected images in San Francisco downtown area often described as "downtown canyon" where consumer GPS signals are extremely inaccurate. The results show the model can predict quality locations that suffice in real business applications, such as ride-sharing, only using phone-grade GPS. Unlike classic visual localization or recent PoseNet-like methods that may work well in indoor environments or small-scale outdoor environments, we avoid using a map or an SFM (structure-from-motion) model at all. More importantly, the proposed method can be scaled up without concerns over the potential failure of 3D reconstruction.
Parallel Quicksort without Pairwise Element Exchange
Venue: arXiv cs.DC 2018
Year: 2018

Quicksort is an instructive classroom approach to parallel sorting on distributed memory parallel computers with many opportunities for illustrating specific implementation alternatives and tradeoffs with common communication interfaces like MPI. The (two) standard distributed memory Quicksort implementations exchange partitioned data elements at each level of the Quicksort recursion. In this note, we show that this is not necessary: It suffices to distribute only the chosen pivots, and postpone element redistribution to the bottom of the recursion. This reduces the total volume of data exchanged from $O(n\log p)$ to $O(n)$, $n$ being the total number of elements to be sorted and $p$ a power-of-two number of processors, by trading off against a total of $O(p)$ additional pivot element distributions. Based on this observation, we describe new, \emph{exchange-free} implementation variants of parallel Quicksort and of Wagar's HyperQuicksort. We have implemented the discussed four different Quicksort variations in MPI, and show that with good pivot selection, Quicksort without pairwise element exchange can be significantly faster than standard implementations on moderately large problems.
Planar Steiner Orientation is NP-complete
Venue: arXiv cs.DM 2018
Year: 2018

Many applications in graph theory are motivated by routing or flow problems. Among these problems is Steiner Orientation: given a mixed graph G (having directed and undirected edges) and a set T of k terminal pairs in G, is there an orientation of the undirected edges in G such that there is a directed path for every terminal pair in T ? This problem was shown to be NP -complete by Arkin and Hassin [1] and later W [1]-hard by Pilipczuk and Wahlström [7], parametrized by k. On the other hand, there is an XP algorithm by Cygan et al. [3] and a polynomial time algorithm for graphs without directed edges by Hassin and Megiddo [5]. Chitnis and Feldmann [2] showed W [1]-hardness of the problem for graphs of genus 1. We consider a further restriction to planar graphs and show NP -completeness.
Benchmarking Top-K Keyword and Top-K Document Processing with T${}^2$K${}^2$ and T${}^2$K${}^2$D${}^2$
Venue: arXiv cs.DB 2018
Year: 2018

Top-k keyword and top-k document extraction are very popular text analysis techniques. Top-k keywords and documents are often computed on-the-fly, but they exploit weighted vocabularies that are costly to build. To compare competing weighting schemes and database implementations, benchmarking is customary. To the best of our knowledge, no benchmark currently addresses these problems. Hence, in this paper, we present T${}^2$K${}^2$, a top-k keywords and documents benchmark, and its decision support-oriented evolution T${}^2$K${}^2$D${}^2$. Both benchmarks feature a real tweet dataset and queries with various complexities and selectivities. They help evaluate weighting schemes and database implementations in terms of computing performance. To illustrate our bench-marks' relevance and genericity, we successfully ran performance tests on the TF-IDF and Okapi BM25 weighting schemes, on one hand, and on different relational (Oracle, PostgreSQL) and document-oriented (MongoDB) database implementations, on the other hand.
Specialty-Aware Task Assignment in Spatial Crowdsourcing
Venue: arXiv cs.DB 2018
Year: 2018

With the rapid development of Mobile Internet, spatial crowdsourcing is gaining more and more attention from both academia and industry. In spatial crowdsourcing, spatial tasks are sent to workers based on their locations. A wide kind of tasks in spatial crowdsourcing are specialty-aware, which are complex and need to be completed by workers with different skills collaboratively. Existing studies on specialty-aware spatial crowdsourcing assume that each worker has a united charge when performing different tasks, no matter how many skills of her/him are used to complete the task, which is not fair and practical. In this paper, we study the problem of specialty-aware task assignment in spatial crowdsourcing, where each worker has fine-grained charge for each of their skills, and the goal is to maximize the total number of completed tasks based on tasks' budget and requirements on particular skills. The problem is proven to be NP-hard. Thus, we propose two efficient heuristics to solve the problem. Experiments on both synthetic and real datasets demonstrate the effectiveness and efficiency of our solutions.