OpenRaiser/Intern-Atlas huggingface dataset:
Biometric Systems Private by Design: Reasoning about privacy properties of biometric system architectures
Venue: arXiv cs.CR 2017
Year: 2017

This work aims to show the applicability, and how, of privacy by design approach to biometric systems and the benefit of using formal methods to this end. Starting from a general framework that has been introduced at STM in 2014, that enables to define privacy architectures and to formally reason about their properties, we explain how it can be adapted to biometrics. The choice of particular techniques and the role of the components (central server, secure module, biometric terminal, smart card, etc.) in the architecture have a strong impact on the privacy guarantees provided by a biometric system. In the literature, some architectures have already been analysed in some way. However, the existing proposals were made on a case by case basis, which makes it difficult to compare them and to provide a rationale for the choice of specific options. In this paper, we describe, on different architectures with various levels of protection, how a general framework for the definition of privacy architectures can be used to specify the design options of a biometric systems and to reason about them in a formal way.
Stochastic Stability Analysis of Perturbed Learning Automata with Constant Step-Size in Strategic-Form Games
Venue: arXiv cs.GT 2017
Year: 2017

This paper considers a class of reinforcement-learning that belongs to the family of Learning Automata and provides a stochastic-stability analysis in strategic-form games. For this class of dynamics, convergence to pure Nash equilibria has been demonstrated only for the fine class of potential games. Prior work primarily provides convergence properties of the dynamics through stochastic approximations, where the asymptotic behavior can be associated with the limit points of an ordinary-differential equation (ODE). However, analyzing global convergence through the ODE-approximation requires the existence of a Lyapunov or a potential function, which naturally restricts the applicabity of these algorithms to a fine class of games. To overcome these limitations, this paper introduces an alternative framework for analyzing stochastic-stability that is based upon an explicit characterization of the (unique) invariant probability measure of the induced Markov chain.
Big Data for Social Sciences: Measuring patterns of human behavior through large-scale mobile phone data
Venue: arXiv cs.CY 2017
Year: 2017

Through seven publications this dissertation shows how anonymized mobile phone data can contribute to the social good and provide insights into human behaviour on a large scale. The size of the datasets analysed ranges from 500 million to 300 billion phone records, covering millions of people. The key contributions are two-fold: 1. Big Data for Social Good: Through prediction algorithms the results show how mobile phone data can be useful to predict important socio-economic indicators, such as income, illiteracy and poverty in developing countries. Such knowledge can be used to identify where vulnerable groups in society are, reduce economic shocks and is a critical component for monitoring poverty rates over time. Further, the dissertation demonstrates how mobile phone data can be used to better understand human behaviour during large shocks in society, exemplified by an analysis of data from the terror attack in Norway and a natural disaster on the south-coast in Bangladesh. This work leads to an increased understanding of how information spreads, and how millions of people move around. The intention is to identify displaced people faster, cheaper and more accurately than existing survey-based methods. 2. Big Data for efficient marketing: Finally, the dissertation offers an insight into how anonymised mobile phone data can be used to map out large social networks, covering millions of people, to understand how products spread inside these networks. Results show that by including social patterns and machine learning techniques in a large-scale marketing experiment in Asia, the adoption rate is increased by 13 times compared to the approach used by experienced marketers. A data-driven and scientific approach to marketing, through more tailored campaigns, contributes to less irrelevant offers for the customers, and better cost efficiency for the companies.
Statistical Anomaly Detection via Composite Hypothesis Testing for Markov Models
Venue: arXiv cs.SY 2017
Year: 2017

Under Markovian assumptions, we leverage a Central Limit Theorem (CLT) for the empirical measure in the test statistic of the composite hypothesis Hoeffding test so as to establish weak convergence results for the test statistic, and, thereby, derive a new estimator for the threshold needed by the test. We first show the advantages of our estimator over an existing estimator by conducting extensive numerical experiments. We find that our estimator controls better for false alarms while maintaining satisfactory detection probabilities. We then apply the Hoeffding test with our threshold estimator to detecting anomalies in two distinct applications domains: one in communication networks and the other in transportation networks. The former application seeks to enhance cyber security and the latter aims at building smarter transportation systems in cities.
The Infinite Server Problem
Venue: arXiv cs.DS 2017
Year: 2017

We study a variant of the $k$-server problem, the infinite server problem, in which infinitely many servers reside initially at a particular point of the metric space and serve a sequence of requests. In the framework of competitive analysis, we show a surprisingly tight connection between this problem and the $(h,k)$-server problem, in which an online algorithm with $k$ servers competes against an offline algorithm with $h$ servers. Specifically, we show that the infinite server problem has bounded competitive ratio if and only if the $(h,k)$-server problem has bounded competitive ratio for some $k=O(h)$. We give a lower bound of $3.146$ for the competitive ratio of the infinite server problem, which implies the same lower bound for the $(h,k)$-server problem even when $k/h \to \infty$ and holds also for the line metric; the previous known bounds were 2.4 for general metric spaces and 2 for the line. For weighted trees and layered graphs we obtain upper bounds, although they depend on the depth. Of particular interest is the infinite server problem on the line, which we show to be equivalent to the seemingly easier case in which all requests are in a fixed bounded interval away from the original position of the servers. This is a special case of a more general reduction from arbitrary metric spaces to bounded subspaces. Unfortunately, classical approaches (double coverage and generalizations, work function algorithm, balancing algorithms) fail even for this special case.
Competing Bandits: Learning under Competition
Venue: arXiv cs.GT 2017
Year: 2017

Most modern systems strive to learn from interactions with users, and many engage in exploration: making potentially suboptimal choices for the sake of acquiring new information. We initiate a study of the interplay between exploration and competition--how such systems balance the exploration for learning and the competition for users. Here the users play three distinct roles: they are customers that generate revenue, they are sources of data for learning, and they are self-interested agents which choose among the competing systems. In our model, we consider competition between two multi-armed bandit algorithms faced with the same bandit instance. Users arrive one by one and choose among the two algorithms, so that each algorithm makes progress if and only if it is chosen. We ask whether and to what extent competition incentivizes the adoption of better bandit algorithms. We investigate this issue for several models of user response, as we vary the degree of rationality and competitiveness in the model. Our findings are closely related to the "competition vs. innovation" relationship, a well-studied theme in economics.
Analysis of Agent Expertise in Ms. Pac-Man using Value-of-Information-based Policies
Venue: arXiv cs.LG 2017
Year: 2017

Conventional reinforcement learning methods for Markov decision processes rely on weakly-guided, stochastic searches to drive the learning process. It can therefore be difficult to predict what agent behaviors might emerge. In this paper, we consider an information-theoretic cost function for performing constrained stochastic searches that promote the formation of risk-averse to risk-favoring behaviors. This cost function is the value of information, which provides the optimal trade-off between the expected return of a policy and the policy's complexity; policy complexity is measured by number of bits and controlled by a single hyperparameter on the cost function. As the policy complexity is reduced, the agents will increasingly eschew risky actions. This reduces the potential for high accrued rewards. As the policy complexity increases, the agents will take actions, regardless of the risk, that can raise the long-term rewards. The obtainable reward depends on a single, tunable hyperparameter that regulates the degree of policy complexity. We evaluate the performance of value-of-information-based policies on a stochastic version of Ms. Pac-Man. A major component of this paper is the demonstration that ranges of policy complexity values yield different game-play styles and explaining why this occurs. We also show that our reinforcement-learning search mechanism is more efficient than the others we utilize. This result implies that the value of information theory is appropriate for framing the exploitation-exploration trade-off in reinforcement learning.
Decomposition of polynomial sets into characteristic pairs
Venue: arXiv cs.SC 2017
Year: 2017

A characteristic pair is a pair (G,C) of polynomial sets in which G is a reduced lexicographic Groebner basis, C is the minimal triangular set contained in G, and C is normal. In this paper, we show that any finite polynomial set P can be decomposed algorithmically into finitely many characteristic pairs with associated zero relations, which provide representations for the zero set of P in terms of those of Groebner bases and those of triangular sets. The algorithm we propose for the decomposition makes use of the inherent connection between Ritt characteristic sets and lexicographic Groebner bases and is based essentially on the structural properties and the computation of lexicographic Groebner bases. Several nice properties about the decomposition and the resulting characteristic pairs, in particular relationships between the Groebner basis and the triangular set in each pair, are established. Examples are given to illustrate the algorithm and some of the properties.
Widely-Linear Precoding for Large-Scale MIMO with IQI: Algorithms and Performance Analysis
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we study widely-linear precoding techniques to mitigate in-phase/quadrature-phase (IQ) imbalance (IQI) in the downlink of large-scale multiple-input multiple-output (MIMO) systems. We adopt a real-valued signal model which takes into account the IQI at the transmitter and then develop widely-linear zero-forcing (WL-ZF), widely-linear matched filter (WL-MF), widely-linear minimum mean-squared error (WL-MMSE) and widely-linear block-diagonalization (WL-BD) type precoding algorithms for both {\color{red} single- and multiple-antenna users.} We also present a performance analysis of WL-ZF and WL-BD. It is proved that without IQI, WL-ZF has exactly the same multiplexing gain and power offset as ZF, while when IQI exists, WL-ZF achieves the same multiplexing gain as ZF with ideal IQ branches, but with a minor power loss which is related to the system scale and the IQ parameters. We also compare the performance of WL-BD with BD. The analysis shows that with ideal IQ branches, WL-BD has the same data rate as BD, while when IQI exists, WL-BD achieves the same multiplexing gain as BD without IQ imbalance. Numerical results verify the analysis and show that the proposed widely-linear type precoding methods significantly outperform their conventional counterparts with IQI and approach those with ideal IQ branches.
Billion-scale similarity search with GPUs
Venue: arXiv cs.CV 2017
Year: 2017

Similarity search finds application in specialized database systems handling complex data such as images or videos, which are typically represented by high-dimensional features and require specific indexing structures. This paper tackles the problem of better utilizing GPUs for this task. While GPUs excel at data-parallel tasks, prior approaches are bottlenecked by algorithms that expose less parallelism, such as k-min selection, or make poor use of the memory hierarchy. We propose a design for k-selection that operates at up to 55% of theoretical peak performance, enabling a nearest neighbor implementation that is 8.5x faster than prior GPU state of the art. We apply it in different similarity search scenarios, by proposing optimized design for brute-force, approximate and compressed-domain search based on product quantization. In all these setups, we outperform the state of the art by large margins. Our implementation enables the construction of a high accuracy k-NN graph on 95 million images from the Yfcc100M dataset in 35 minutes, and of a graph connecting 1 billion vectors in less than 12 hours on 4 Maxwell Titan X GPUs. We have open-sourced our approach for the sake of comparison and reproducibility.
Weakly- and Semi-Supervised Object Detection with Expectation-Maximization Algorithm
Venue: arXiv cs.CV 2017
Year: 2017

Object detection when provided image-level labels instead of instance-level labels (i.e., bounding boxes) during training is an important problem in computer vision, since large scale image datasets with instance-level labels are extremely costly to obtain. In this paper, we address this challenging problem by developing an Expectation-Maximization (EM) based object detection method using deep convolutional neural networks (CNNs). Our method is applicable to both the weakly-supervised and semi-supervised settings. Extensive experiments on PASCAL VOC 2007 benchmark show that (1) in the weakly supervised setting, our method provides significant detection performance improvement over current state-of-the-art methods, (2) having access to a small number of strongly (instance-level) annotated images, our method can almost match the performace of the fully supervised Fast RCNN. We share our source code at https://github.com/ZiangYan/EM-WSD.
ShaResNet: reducing residual network parameter number by sharing weights
Venue: arXiv cs.CV 2017
Year: 2017

Deep Residual Networks have reached the state of the art in many image processing tasks such image classification. However, the cost for a gain in accuracy in terms of depth and memory is prohibitive as it requires a higher number of residual blocks, up to double the initial value. To tackle this problem, we propose in this paper a way to reduce the redundant information of the networks. We share the weights of convolutional layers between residual blocks operating at the same spatial scale. The signal flows multiple times in the same convolutional layer. The resulting architecture, called ShaResNet, contains block specific layers and shared layers. These ShaResNet are trained exactly in the same fashion as the commonly used residual networks. We show, on the one hand, that they are almost as efficient as their sequential counterparts while involving less parameters, and on the other hand that they are more efficient than a residual network with the same number of parameters. For example, a 152-layer-deep residual network can be reduced to 106 convolutional layers, i.e. a parameter gain of 39\%, while loosing less than 0.2\% accuracy on ImageNet.
NOMA Meets Finite Resolution Analog Beamforming in Massive MIMO and Millimeter-Wave Networks
Venue: arXiv cs.IT 2017
Year: 2017

Finite resolution analog beamforming (FRAB) has been recognized as an effective approach to reduce hardware costs in massive multiple-input multiple-output (MIMO) and millimeter-wave networks. However, the use of FRAB means that the beamformers are not perfectly aligned with the users' channels and multiple users may be assigned similar or even identifical beamformers. This letter shows how non-orthogonal multiple access (NOMA) can be used to exploit this feature of FRAB, where a single FRAB based beamformer is shared by multiple users. Both analytical and simulation results are provided to demonstrate the excellent performance achieved by this new NOMA transmission scheme.
Studying Positive Speech on Twitter
Venue: arXiv cs.CL 2017
Year: 2017

We present results of empirical studies on positive speech on Twitter. By positive speech we understand speech that works for the betterment of a given situation, in this case relations between different communities in a conflict-prone country. We worked with four Twitter data sets. Through semi-manual opinion mining, we found that positive speech accounted for < 1% of the data . In fully automated studies, we tested two approaches: unsupervised statistical analysis, and supervised text classification based on distributed word representation. We discuss benefits and challenges of those approaches and report empirical evidence obtained in the study.
Low-rank Label Propagation for Semi-supervised Learning with 100 Millions Samples
Venue: arXiv cs.LG 2017
Year: 2017

The success of semi-supervised learning crucially relies on the scalability to a huge amount of unlabelled data that are needed to capture the underlying manifold structure for better classification. Since computing the pairwise similarity between the training data is prohibitively expensive in most kinds of input data, currently, there is no general ready-to-use semi-supervised learning method/tool available for learning with tens of millions or more data points. In this paper, we adopted the idea of two low-rank label propagation algorithms, GLNP (Global Linear Neighborhood Propagation) and Kernel Nyström Approximation, and implemented the parallelized version of the two algorithms accelerated with Nesterov's accelerated projected gradient descent for Big-data Label Propagation (BigLP). The parallel algorithms are tested on five real datasets ranging from 7000 to 10,000,000 in size and a simulation dataset of 100,000,000 samples. In the experiments, the implementation can scale up to datasets with 100,000,000 samples and hundreds of features and the algorithms also significantly improved the prediction accuracy when only a very small percentage of the data is labeled. The results demonstrate that the BigLP implementation is highly scalable to big data and effective in utilizing the unlabeled data for semi-supervised learning.
Context-Sensitive Super-Resolution for Fast Fetal Magnetic Resonance Imaging
Venue: arXiv cs.CV 2017
Year: 2017

3D Magnetic Resonance Imaging (MRI) is often a trade-off between fast but low-resolution image acquisition and highly detailed but slow image acquisition. Fast imaging is required for targets that move to avoid motion artefacts. This is in particular difficult for fetal MRI. Spatially independent upsampling techniques, which are the state-of-the-art to address this problem, are error prone and disregard contextual information. In this paper we propose a context-sensitive upsampling method based on a residual convolutional neural network model that learns organ specific appearance and adopts semantically to input data allowing for the generation of high resolution images with sharp edges and fine scale detail. By making contextual decisions about appearance and shape, present in different parts of an image, we gain a maximum of structural detail at a similar contrast as provided by high-resolution data. We experiment on $145$ fetal scans and show that our approach yields an increased PSNR of $1.25$ $dB$ when applied to under-sampled fetal data \emph{cf.} baseline upsampling. Furthermore, our method yields an increased PSNR of $1.73$ $dB$ when utilizing under-sampled fetal data to perform brain volume reconstruction on motion corrupted captured data.
SceneSuggest: Context-driven 3D Scene Design
Venue: arXiv cs.GR 2017
Year: 2017

We present SceneSuggest: an interactive 3D scene design system providing context-driven suggestions for 3D model retrieval and placement. Using a point-and-click metaphor we specify regions in a scene in which to automatically place and orient relevant 3D models. Candidate models are ranked using a set of static support, position, and orientation priors learned from 3D scenes. We show that our suggestions enable rapid assembly of indoor scenes. We perform a user study comparing suggestions to manual search and selection, as well as to suggestions with no automatic orientation. We find that suggestions reduce total modeling time by 32%, that orientation priors reduce time spent re-orienting objects by 27%, and that context-driven suggestions reduce the number of text queries by 50%.
Ending the Anomaly: Achieving Low Latency and Airtime Fairness in WiFi
Venue: arXiv cs.NI 2017
Year: 2017

With more devices connected, delays and jitter at the WiFi hop become more prevalent, and correct functioning during network congestion becomes more important. However, two important performance issues prevent modern WiFi from reaching its potential: Increased latency under load caused by excessive queueing (i.e. bufferbloat) and the 802.11 performance anomaly. To remedy these issues, we present a novel two-part solution: We design a new queueing scheme that eliminates bufferbloat in the wireless setting. Leveraging this queueing scheme, we then design an airtime fairness scheduler that operates at the access point and doesn't require any changes to clients. We evaluate our solution using both a theoretical model and experiments in a testbed environment, formulating a suitable analytical model in the process. We show that our solution achieves an order of magnitude reduction in latency under load, large improvements in multi-station throughput, and nearly perfect airtime fairness for both TCP and downstream UDP traffic. Further experiments with application traffic confirm that the solution provides significant performance gains for real-world traffic.We develop a production quality implementation of our solution in the Linux kernel, the platform powering most access points outside of the managed enterprise setting. The implementation has been accepted into the mainline kernel distribution, making it available for deployment on billions of devices running Linux today.
Multi-Sensor Data Pattern Recognition for Multi-Target Localization: A Machine Learning Approach
Venue: arXiv cs.SY 2017
Year: 2017

Data-target pairing is an important step towards multi-target localization for the intelligent operation of unmanned systems. Target localization plays a crucial role in numerous applications, such as search, and rescue missions, traffic management and surveillance. The objective of this paper is to present an innovative target location learning approach, where numerous machine learning approaches, including K-means clustering and supported vector machines (SVM), are used to learn the data pattern across a list of spatially distributed sensors. To enable the accurate data association from different sensors for accurate target localization, appropriate data pre-processing is essential, which is then followed by the application of different machine learning algorithms to appropriately group data from different sensors for the accurate localization of multiple targets. Through simulation examples, the performance of these machine learning algorithms is quantified and compared.