OpenRaiser/Intern-Atlas huggingface dataset:
Private Function Retrieval
Venue: arXiv cs.IT 2017
Year: 2017

The widespread use of cloud computing services raises the question of how one can delegate the processing tasks to the untrusted distributed parties without breeching the privacy of its data and algorithms. Motivated by the algorithm privacy concerns in a distributed computing system, in this paper, we introduce the private function retrieval (PFR) problem, where a user wishes to efficiently retrieve a linear function of $K$ messages from $N$ non-communicating replicated servers while keeping the function hidden from each individual server. The goal is to find a scheme with minimum communication cost. To characterize the fundamental limits of the communication cost, we define the capacity of PFR problem as the size of the message that can be privately retrieved (which is the size of one file) normalized to the required downloaded information bits. We first show that for the PFR problem with $K$ messages, $N=2$ servers and a linear function with binary coefficients the capacity is $C=\frac{1}{2}\Big(1-\frac{1}{2^K}\Big)^{-1}$. Interestingly, this is the capacity of retrieving one of $K$ messages from $N=2$ servers while keeping the index of the requested message hidden from each individual server, the problem known as private information retrieval (PIR). Then, we extend the proposed achievable scheme to the case of arbitrary number of servers and coefficients in the field $GF(q)$ with arbitrary $q$ and obtain $R=\Big(1-\frac{1}{N}\Big)\Big(1+\frac{\frac{1}{N-1}}{(\frac{q^K-1}{q-1})^{N-1}}\Big)$.
Social Sensing of Floods in the UK
Venue: arXiv cs.HC 2017
Year: 2017

"Social sensing" is a form of crowd-sourcing that involves systematic analysis of digital communications to detect real-world events. Here we consider the use of social sensing for observing natural hazards. In particular, we present a case study that uses data from a popular social media platform (Twitter) to detect and locate flood events in the UK. In order to improve data quality we apply a number of filters (timezone, simple text filters and a naive Bayes `relevance' filter) to the data. We then use place names in the user profile and message text to infer the location of the tweets. These two steps remove most of the irrelevant tweets and yield orders of magnitude more located tweets than we have by relying on geo-tagged data. We demonstrate that high resolution social sensing of floods is feasible and we can produce high-quality historical and real-time maps of floods using Twitter.
Denoising Imaging Polarimetry by an Adapted BM3D Method
Venue: arXiv cs.CV 2017
Year: 2017

Imaging polarimetry allows more information to be extracted from a scene than conventional intensity or colour imaging. However, a major challenge of imaging polarimetry is image degradation due to noise. This paper investigates the mitigation of noise through denoising algorithms and compares existing denoising algorithms with a new method, based on BM3D. This algorithm, PBM3D, gives visual quality superior to the state of the art across all images and noise standard deviations tested. We show that denoising polarization images using PBM3D allows the degree of polarization to be more accurately calculated by comparing it to spectroscopy methods.
Modeling Human Categorization of Natural Images Using Deep Feature Representations
Venue: arXiv cs.CV 2017
Year: 2017

Over the last few decades, psychologists have developed sophisticated formal models of human categorization using simple artificial stimuli. In this paper, we use modern machine learning methods to extend this work into the realm of naturalistic stimuli, enabling human categorization to be studied over the complex visual domain in which it evolved and developed. We show that representations derived from a convolutional neural network can be used to model behavior over a database of >300,000 human natural image classifications, and find that a group of models based on these representations perform well, near the reliability of human judgments. Interestingly, this group includes both exemplar and prototype models, contrasting with the dominance of exemplar models in previous work. We are able to improve the performance of the remaining models by preprocessing neural network representations to more closely capture human similarity judgments.
Estimating Graph Parameters from Random Order Streams
Venue: arXiv cs.DS 2017
Year: 2017

We develop a new algorithmic technique that allows to transfer some constant time approximation algorithms for general graphs into random order streaming algorithms. We illustrate our technique by proving that in random order streams with probability at least $2/3$, $\bullet$ the number of connected components of $G$ can be approximated up to an additive error of $\varepsilon n$ using $(\frac{1}{\varepsilon})^{O(1/\varepsilon^3)}$ space, $\bullet$ the weight of a minimum spanning tree of a connected input graph with integer edges weights from $\{1,\dots,W\}$ can be approximated within a multiplicative factor of $1+\varepsilon$ using $\big(\frac{1}{\varepsilon}\big)^{\tilde O(W^3/\varepsilon^3)}$ space, $\bullet$ the size of a maximum independent set in planar graphs can be approximated within a multiplicative factor of $1+\varepsilon$ using space $2^{(1/\varepsilon)^{(1/\varepsilon)^{\log^{O(1)} (1/\varepsilon)}}}$.
On Partial Covering For Geometric Set Systems
Venue: arXiv cs.CG 2017
Year: 2017

We study a generalization of the Set Cover problem called the \emph{Partial Set Cover} in the context of geometric set systems. The input to this problem is a set system $(X, \mathcal{S})$, where $X$ is a set of elements and $\mathcal{S}$ is a collection of subsets of $X$, and an integer $k \le |X|$. The goal is to cover at least $k$ elements of $X$ by using a minimum-weight collection of sets from $\mathcal{S}$. The main result of this article is an LP rounding scheme which shows that the integrality gap of the Partial Set Cover LP is at most a constant times that of the Set Cover LP for a certain projection of the set system $(X, \mathcal{S})$. As a corollary of this result, we get improved approximation guarantees for the Partial Set Cover problem for a large class of geometric set systems.
Effect of enhanced dissipation by shear flows on transient relaxation and probability density function in two dimensions
Venue: arXiv cs.IT 2017
Year: 2017

We report a non-perturbative study of the effects of shear flows on turbulence reduction in a decaying turbulence in two dimensions. By considering different initial power spectra and shear flows (zonal flows, combined zonal flows and streamers), we demonstrate how shear flows rapidly generate small scales, leading to a fast damping of turbulence amplitude. In particular, a double exponential decrease in turbulence amplitude is shown to occur due to an exponential increase in wavenumber. The scaling of the effective dissipation time scale $τ_{e}$, previously taken to be a hybrid time scale $τ_{e} \propto τ_Ω^{2/3} τ_η$, is shown to depend on types of depend on the type of shear flow as well as the initial power spectrum. Here, $τ_Ω$ and $τ_η$ are shearing and molecular diffusion times, respectively. Furthermore, we present time-dependent Probability Density Functions (PDFs) and discuss the effect of enhanced dissipation on PDFs and a dynamical time scale $τ(t)$, which represents the time scale over which a system passes through statistically different states.
DataVizard: Recommending Visual Presentations for Structured Data
Venue: arXiv cs.AI 2017
Year: 2017

Selecting the appropriate visual presentation of the data such that it preserves the semantics of the underlying data and at the same time provides an intuitive summary of the data is an important, often the final step of data analytics. Unfortunately, this is also a step involving significant human effort starting from selection of groups of columns in the structured results from analytics stages, to the selection of right visualization by experimenting with various alternatives. In this paper, we describe our \emph{DataVizard} system aimed at reducing this overhead by automatically recommending the most appropriate visual presentation for the structured result. Specifically, we consider the following two scenarios: first, when one needs to visualize the results of a structured query such as SQL; and the second, when one has acquired a data table with an associated short description (e.g., tables from the Web). Using a corpus of real-world database queries (and their results) and a number of statistical tables crawled from the Web, we show that DataVizard is capable of recommending visual presentations with high accuracy. We also present the results of a user survey that we conducted in order to assess user views of the suitability of the presented charts vis-a-vis the plain text captions of the data.
Modeling and Performance Comparison of Privacy Approaches for Location Based Services
Venue: arXiv cs.CR 2017
Year: 2017

In pervasive computing environment, Location Based Services (LBSs) are getting popularity among users because of their usefulness in day-to-day life. LBSs are information services that use geospatial data of mobile device and smart phone users to provide information, entertainment and security in real time. A key concern in such pervasive computing environment is the need to reveal the user's exact location which may allow an adversary to infer private information about the user. To address the privacy concerns of LBS users, a large number of security approaches have been proposed based on the concept of k-anonymity. The central idea in location k-anonymity is to find a set of k-1 users confined in a given geographical area of the actual user, such that the location of these k users are indistinguishable from one another, thus protecting the identity of the user. Although a number of performance parameters like success rate, amount of privacy achieved are used to measure the performance of the k-anonymity approaches, they make the implicit, unrealistic assumption that the k-1 users are readily available. As such these approaches ignore the turnaround time to process a user request, which is crucial for a real-time application like LBS. In this work, we model the k-anonymity approaches using queuing theory to compute the average sojourn time of users and queue length of the system. To demonstrate that queuing theory can be used to model all k-anonymity approaches, we consider graph-based k-anonymity approaches. The proposed analytical model is further validated with experimental results.
SkipFlow: Incorporating Neural Coherence Features for End-to-End Automatic Text Scoring
Venue: arXiv cs.AI 2017
Year: 2017

Deep learning has demonstrated tremendous potential for Automatic Text Scoring (ATS) tasks. In this paper, we describe a new neural architecture that enhances vanilla neural network models with auxiliary neural coherence features. Our new method proposes a new \textsc{SkipFlow} mechanism that models relationships between snapshots of the hidden representations of a long short-term memory (LSTM) network as it reads. Subsequently, the semantic relationships between multiple snapshots are used as auxiliary features for prediction. This has two main benefits. Firstly, essays are typically long sequences and therefore the memorization capability of the LSTM network may be insufficient. Implicit access to multiple snapshots can alleviate this problem by acting as a protection against vanishing gradients. The parameters of the \textsc{SkipFlow} mechanism also acts as an auxiliary memory. Secondly, modeling relationships between multiple positions allows our model to learn features that represent and approximate textual coherence. In our model, we call this \textit{neural coherence} features. Overall, we present a unified deep learning architecture that generates neural coherence features as it reads in an end-to-end fashion. Our approach demonstrates state-of-the-art performance on the benchmark ASAP dataset, outperforming not only feature engineering baselines but also other deep learning models.
Efficiency Analysis of ASP Encodings for Sequential Pattern Mining Tasks
Venue: arXiv cs.AI 2017
Year: 2017

This article presents the use of Answer Set Programming (ASP) to mine sequential patterns. ASP is a high-level declarative logic programming paradigm for high level encoding combinatorial and optimization problem solving as well as knowledge representation and reasoning. Thus, ASP is a good candidate for implementing pattern mining with background knowledge, which has been a data mining issue for a long time. We propose encodings of the classical sequential pattern mining tasks within two representations of embeddings (fill-gaps vs skip-gaps) and for various kinds of patterns: frequent, constrained and condensed. We compare the computational performance of these encodings with each other to get a good insight into the efficiency of ASP encodings. The results show that the fill-gaps strategy is better on real problems due to lower memory consumption. Finally, compared to a constraint programming approach (CPSM), another declarative programming paradigm, our proposal showed comparable performance.
Sequences of radius $k$ for complete bipartite graphs
Venue: arXiv cs.DM 2017
Year: 2017

A \emph{$k$-radius sequence} for a graph $G$ is a sequence of vertices of $G$ (typically with repetitions) such that for every edge $uv$ of $G$ vertices $u$ and $v$ appear at least once within distance $k$ in the sequence. The length of a shortest $k$-radius sequence for $G$ is denoted by $f_k(G)$. We give an asymptotically tight estimation on $f_k(G)$ for complete bipartite graphs {which matches a lower bound, valid for all bipartite graphs}. We also show that determining $f_k(G)$ for an arbitrary graph $G$ is NP-hard for every constant $k>1$.
An optimized shape descriptor based on structural properties of networks
Venue: arXiv cs.CV 2017
Year: 2017

The structural analysis of shape boundaries leads to the characterization of objects as well as to the understanding of shape properties. The literature on graphs and networks have contributed to the structural characterization of shapes with different theoretical approaches. We performed a study on the relationship between the shape architecture and the network topology constructed over the shape boundary. For that, we used a method for network modeling proposed in 2009. Firstly, together with curvature analysis, we evaluated the proposed approach for regular polygons. This way, it was possible to investigate how the network measurements vary according to some specific shape properties. Secondly, we evaluated the performance of the proposed shape descriptor in classification tasks for three datasets, accounting for both real-world and synthetic shapes. We demonstrated that not only degree related measurements are capable of distinguishing classes of objects. Yet, when using measurements that account for distinct properties of the network structure, the construction of the shape descriptor becomes more computationally efficient. Given the fact the network is dynamically constructed, the number of iterations can be reduced. The proposed approach accounts for a more robust set of structural measurements, that improved the discriminant power of the shape descriptors.
CryptoDL: Deep Neural Networks over Encrypted Data
Venue: arXiv cs.CR 2017
Year: 2017

Machine learning algorithms based on deep neural networks have achieved remarkable results and are being extensively used in different domains. However, the machine learning algorithms requires access to raw data which is often privacy sensitive. To address this issue, we develop new techniques to provide solutions for running deep neural networks over encrypted data. In this paper, we develop new techniques to adopt deep neural networks within the practical limitation of current homomorphic encryption schemes. More specifically, we focus on classification of the well-known convolutional neural networks (CNN). First, we design methods for approximation of the activation functions commonly used in CNNs (i.e. ReLU, Sigmoid, and Tanh) with low degree polynomials which is essential for efficient homomorphic encryption schemes. Then, we train convolutional neural networks with the approximation polynomials instead of original activation functions and analyze the performance of the models. Finally, we implement convolutional neural networks over encrypted data and measure performance of the models. Our experimental results validate the soundness of our approach with several convolutional neural networks with varying number of layers and structures. When applied to the MNIST optical character recognition tasks, our approach achieves 99.52\% accuracy which significantly outperforms the state-of-the-art solutions and is very close to the accuracy of the best non-private version, 99.77\%. Also, it can make close to 164000 predictions per hour. We also applied our approach to CIFAR-10, which is much more complex compared to MNIST, and were able to achieve 91.5\% accuracy with approximation polynomials used as activation functions. These results show that CryptoDL provides efficient, accurate and scalable privacy-preserving predictions.
Towards Dual-functional Radar-Communication Systems: Optimal Waveform Design
Venue: arXiv cs.IT 2017
Year: 2017

We focus on a dual-functional multi-input-multi-output (MIMO) radar-communication (RadCom) system, where a single transmitter communicates with downlink cellular users and detects radar targets simultaneously. Several design criteria are considered for minimizing the downlink multi-user interference. First, we consider both the omnidirectional and directional beampattern design problems, where the closed-form globally optimal solutions are obtained. Based on these waveforms, we further consider a weighted optimization to enable a flexible trade-off between radar and communications performance and introduce a low-complexity algorithm. The computational costs of the above three designs are shown to be similar to the conventional zero-forcing (ZF) precoding. Moreover, to address the more practical constant modulus waveform design problem, we propose a branch-and-bound algorithm that obtains a globally optimal solution and derive its worst-case complexity as a function of the maximum iteration number. Finally, we assess the effectiveness of the proposed waveform design approaches by numerical results.
A visual search engine for Bangladeshi laws
Venue: arXiv cs.HC 2017
Year: 2017

Browsing and finding relevant information for Bangladeshi laws is a challenge faced by all law students and researchers in Bangladesh, and by citizens who want to learn about any legal procedure. Some law archives in Bangladesh are digitized, but lack proper tools to organize the data meaningfully. We present a text visualization tool that utilizes machine learning techniques to make the searching of laws quicker and easier. Using Doc2Vec to layout law article nodes, link mining techniques to visualize relevant citation networks, and named entity recognition to quickly find relevant sections in long law articles, our tool provides a faster and better search experience to the users. Qualitative feedback from law researchers, students, and government officials show promise for visually intuitive search tools in the context of governmental, legal, and constitutional data in developing countries, where digitized data does not necessarily pave the way towards an easy access to information.
Optimal Tuning of Two-Dimensional Keyboards
Venue: arXiv cs.SD 2017
Year: 2017

We give a new analysis of a tuning problem in music theory, pertaining specifically to the approximation of harmonics on a two-dimensional keyboard. We formulate the question as a linear programming problem on families of constraints and provide exact solutions for many new keyboard dimensions. We also show that an optimal tuning for harmonic approximation can be obtained for any keyboard of given width, provided sufficiently many rows of octaves.
Robust and High Fidelity Mesh Denoising
Venue: arXiv cs.GR 2017
Year: 2017

This paper presents a simple and effective two-stage mesh denoising algorithm, where in the first stage, the face normal filtering is done by using the bilateral normal filtering in the robust statistics framework. Tukey's bi-weight function is used as similarity function in the bilateral weighting, which is a robust estimator and stops the diffusion at sharp edges to retain features and removes noise from flat regions effectively. In the second stage, an edge weighted Laplace operator is introduced to compute a differential coordinate. This differential coordinate helps the algorithm to produce a high-quality mesh without any face normal flips and makes the method robust against high-intensity noise.
Sliced Wasserstein Distance for Learning Gaussian Mixture Models
Venue: arXiv cs.CV 2017
Year: 2017

Gaussian mixture models (GMM) are powerful parametric tools with many applications in machine learning and computer vision. Expectation maximization (EM) is the most popular algorithm for estimating the GMM parameters. However, EM guarantees only convergence to a stationary point of the log-likelihood function, which could be arbitrarily worse than the optimal solution. Inspired by the relationship between the negative log-likelihood function and the Kullback-Leibler (KL) divergence, we propose an alternative formulation for estimating the GMM parameters using the sliced Wasserstein distance, which gives rise to a new algorithm. Specifically, we propose minimizing the sliced-Wasserstein distance between the mixture model and the data distribution with respect to the GMM parameters. In contrast to the KL-divergence, the energy landscape for the sliced-Wasserstein distance is more well-behaved and therefore more suitable for a stochastic gradient descent scheme to obtain the optimal GMM parameters. We show that our formulation results in parameter estimates that are more robust to random initializations and demonstrate that it can estimate high-dimensional data distributions more faithfully than the EM algorithm.
Deep Inception-Residual Laplacian Pyramid Networks for Accurate Single Image Super-Resolution
Venue: arXiv cs.CV 2017
Year: 2017

With exploiting contextual information over large image regions in an efficient way, the deep convolutional neural network has shown an impressive performance for single image super-resolution (SR). In this paper, we propose a deep convolutional network by cascading the well-designed inception-residual blocks within the deep Laplacian pyramid framework to progressively restore the missing high-frequency details of high-resolution (HR) images. By optimizing our network structure, the trainable depth of the proposed network gains a significant improvement, which in turn improves super-resolving accuracy. With our network depth increasing, however, the saturation and degradation of training accuracy continues to be a critical problem. As regard to this, we propose an effective two-stage training strategy, in which we firstly use images downsampled from the ground-truth HR images as the optimal objective to train the inception-residual blocks in each pyramid level with an extremely high learning rate enabled by gradient clipping, and then the ground-truth HR images are used to fine-tune all the pre-trained inception-residual blocks for obtaining the final SR model. Furthermore, we present a new loss function operating in both image space and local rank space to optimize our network for exploiting the contextual information among different output components. Extensive experiments on benchmark datasets validate that the proposed method outperforms existing state-of-the-art SR methods in terms of the objective evaluation as well as the visual quality.