OpenRaiser/Intern-Atlas huggingface dataset:
Differentially Private Neighborhood-based Recommender Systems
Venue: arXiv cs.CR 2017
Year: 2017

Privacy issues of recommender systems have become a hot topic for the society as such systems are appearing in every corner of our life. In contrast to the fact that many secure multi-party computation protocols have been proposed to prevent information leakage in the process of recommendation computation, very little has been done to restrict the information leakage from the recommendation results. In this paper, we apply the differential privacy concept to neighborhood-based recommendation methods (NBMs) under a probabilistic framework. We first present a solution, by directly calibrating Laplace noise into the training process, to differential-privately find the maximum a posteriori parameters similarity. Then we connect differential privacy to NBMs by exploiting a recent observation that sampling from the scaled posterior distribution of a Bayesian model results in provably differentially private systems. Our experiments show that both solutions allow promising accuracy with a modest privacy budget, and the second solution yields better accuracy if the sampling asymptotically converges. We also compare our solutions to the recent differentially private matrix factorization (MF) recommender systems, and show that our solutions achieve better accuracy when the privacy budget is reasonably small. This is an interesting result because MF systems often offer better accuracy when differential privacy is not applied.
Surjective H-Colouring: New Hardness Results
Venue: arXiv cs.CC 2017
Year: 2017

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring problem is to decide whether or not a graph G allows a homomorphism to a fixed graph H. We continue a study on a variant of this problem, namely the Surjective H-Colouring problem, which imposes the homomorphism to be vertex-surjective. We build upon previous results and show that this problem is NP-complete for every connected graph H that has exactly two vertices with a self-loop as long as these two vertices are not adjacent. As a result, we can classify the computational complexity of Surjective H-Colouring for every graph H on at most four vertices.
Fragmenting very large XML data warehouses via K-means clustering algorithm
Venue: arXiv cs.DB 2017
Year: 2017

XML data sources are more and more gaining popularity in the context of a wide family of Business Intelligence (BI) and On-Line Analytical Processing (OLAP) applications, due to the amenities of XML in representing and managing semi-structured and complex multidimensional data. As a consequence, many XML data warehouse models have been proposed during past years in order to handle hetero-geneity and complexity of multidimensional data in a way traditional relational data warehouse approaches fail to achieve. However, XML-native database systems currently suffer from limited performance, both in terms of volumes of manageable data and query response time. Therefore , recent research efforts are focusing the attention on fragmentation techniques, which are able to overcome the limitations above. Derived horizontal fragmentation is already used in relational data warehouses, and can definitely be adapted to the XML context. However, classical fragmentation algorithms are not suitable to control the number of originated fragments, which instead plays a critical role in data warehouses, and, with more emphasis, distributed data warehouse architectures. Inspired by this research challenge, in this paper we propose the use of K-means clustering algorithm for effectively and efficiently supporting the fragmentation of very large XML data warehouses, and, at the same time, completely controlling and determining the number of originated fragments via adequately setting the parameter K. We complete our analytical contribution by means of a comprehensive experimental assessment where we compare the efficiency of our proposed XML data warehouse fragmentation technique against those of classical derived horizontal fragmentation algorithms adapted to XML data warehouses.
An $N \log N$ Parallel Fast Direct Solver for Kernel Matrices
Venue: arXiv cs.DC 2017
Year: 2017

Kernel matrices appear in machine learning and non-parametric statistics. Given $N$ points in $d$ dimensions and a kernel function that requires $\mathcal{O}(d)$ work to evaluate, we present an $\mathcal{O}(dN\log N)$-work algorithm for the approximate factorization of a regularized kernel matrix, a common computational bottleneck in the training phase of a learning task. With this factorization, solving a linear system with a kernel matrix can be done with $\mathcal{O}(N\log N)$ work. Our algorithm only requires kernel evaluations and does not require that the kernel matrix admits an efficient global low rank approximation. Instead our factorization only assumes low-rank properties for the off-diagonal blocks under an appropriate row and column ordering. We also present a hybrid method that, when the factorization is prohibitively expensive, combines a partial factorization with iterative methods. As a highlight, we are able to approximately factorize a dense $11M\times11M$ kernel matrix in 2 minutes on 3,072 x86 "Haswell" cores and a $4.5M\times4.5M$ matrix in 1 minute using 4,352 "Knights Landing" cores.
IEEE 802.15.6-based Prototype System for WBAN: Design and Implementation
Venue: arXiv cs.NI 2017
Year: 2017

Various current trends such as ever growing population and accelerated aging effects have effectively promoted the growth of Wireless Body Area Network (WBAN). Being the specialized standard of WBAN, the burgeoning IEEE 802.15.6 is on its way to refinement and perfection. Since experiments are the foundation of research in WBAN that reproduce system operating patterns, yet existing platforms in WBAN are mainly simulations that could not highly conform to reality with strict requirements to some degree. Thus, a reliable and efficient system based on the IEEE 802.15.6, named WBAN prototype system, is proposed and implemented in this paper. The prototype system is ascertained to be valid, authentic and efficient via analyses of scenario tests. Running in circumstances much closer to reality, the system obtains experimental results that meet rigid requirements preferably. Furthermore, based on the valid platform we created, optimizations of two parameters in the IEEE 802.15.6 by actual measurements are derived. We obtain an optimum number of transmission retries and relationship of payload length within 30 with FER, making a trade-off between waste of resource and high packet loss rate.
Machine Learning of Linear Differential Equations using Gaussian Processes
Venue: arXiv cs.LG 2017
Year: 2017

This work leverages recent advances in probabilistic machine learning to discover conservation laws expressed by parametric linear equations. Such equations involve, but are not limited to, ordinary and partial differential, integro-differential, and fractional order operators. Here, Gaussian process priors are modified according to the particular form of such operators and are employed to infer parameters of the linear equations from scarce and possibly noisy observations. Such observations may come from experiments or "black-box" computer simulations.
Methods for Mapping Forest Disturbance and Degradation from Optical Earth Observation Data: a Review
Venue: arXiv cs.CV 2017
Year: 2017

Purpose of review: This paper presents a review of the current state of the art in remote sensing based monitoring of forest disturbances and forest degradation from optical Earth Observation data. Part one comprises an overview of currently available optical remote sensing sensors, which can be used for forest disturbance and degradation mapping. Part two reviews the two main categories of existing approaches: classical image-to-image change detection and time series analysis. Recent findings: With the launch of the Sentinel-2a satellite and available Landsat imagery, time series analysis has become the most promising but also most demanding category of degradation mapping approaches. Four time series classification methods are distinguished. The methods are explained and their benefits and drawbacks are discussed. A separate chapter presents a number of recent forest degradation mapping studies for two different ecosystems: temperate forests with a geographical focus on Europe and tropical forests with a geographical focus on Africa. Summary: The review revealed that a wide variety of methods for the detection of forest degradation is already available. Today, the main challenge is to transfer these approaches to high resolution time series data from multiple sensors. Future research should also focus on the classification of disturbance types and the development of robust up-scalable methods to enable near real time disturbance mapping in support of operational reactive measures.
Multi-task Learning Of Deep Neural Networks For Audio Visual Automatic Speech Recognition
Venue: arXiv cs.CL 2017
Year: 2017

Multi-task learning (MTL) involves the simultaneous training of two or more related tasks over shared representations. In this work, we apply MTL to audio-visual automatic speech recognition(AV-ASR). Our primary task is to learn a mapping between audio-visual fused features and frame labels obtained from acoustic GMM/HMM model. This is combined with an auxiliary task which maps visual features to frame labels obtained from a separate visual GMM/HMM model. The MTL model is tested at various levels of babble noise and the results are compared with a base-line hybrid DNN-HMM AV-ASR model. Our results indicate that MTL is especially useful at higher level of noise. Compared to base-line, upto 7\% relative improvement in WER is reported at -3 SNR dB
Top-k Querying of Unknown Values under Order Constraints (Extended Version)
Venue: arXiv cs.DB 2017
Year: 2017

Many practical scenarios make it necessary to evaluate top-k queries over data items with partially unknown values. This paper considers a setting where the values are taken from a numerical domain, and where some partial order constraints are given over known and unknown values: under these constraints, we assume that all possible worlds are equally likely. Our work is the first to propose a principled scheme to derive the value distributions and expected values of unknown items in this setting, with the goal of computing estimated top-k results by interpolating the unknown values from the known ones. We study the complexity of this general task, and show tight complexity bounds, proving that the problem is intractable, but can be tractably approximated. We then consider the case of tree-shaped partial orders, where we show a constructive PTIME solution. We also compare our problem setting to other top-k definitions on uncertain data.
Unsupervised Image-to-Image Translation with Generative Adversarial Networks
Venue: arXiv cs.CV 2017
Year: 2017

It's useful to automatically transform an image from its original form to some synthetic form (style, partial contents, etc.), while keeping the original structure or semantics. We define this requirement as the "image-to-image translation" problem, and propose a general approach to achieve it, based on deep convolutional and conditional generative adversarial networks (GANs), which has gained a phenomenal success to learn mapping images from noise input since 2014. In this work, we develop a two step (unsupervised) learning method to translate images between different domains by using unlabeled images without specifying any correspondence between them, so that to avoid the cost of acquiring labeled data. Compared with prior works, we demonstrated the capacity of generality in our model, by which variance of translations can be conduct by a single type of model. Such capability is desirable in applications like bidirectional translation
H-infinity Filtering for Cloud-Aided Semi-active Suspension with Delayed Information
Venue: arXiv cs.SY 2017
Year: 2017

This chapter presents an H-infinity filtering framework for cloud-aided semiactive suspension system with time-varying delays. In this system, road profile information is downloaded from a cloud database to facilitate onboard estimation of suspension states. Time-varying data transmission delays are considered and assumed to be bounded. A quarter-car linear suspension model is used and an H-infinity filter is designed with both onboard sensor measurements and delayed road profile information from the cloud. The filter design procedure is designed based on linear matrix inequalities (LMIs). Numerical simulation results are reported that illustrates the fusion of cloud-based and on-board information that can be achieved in Vehicleto- Cloud-to-Vehicle (V2C2V) implementation.
On finding highly connected spanning subgraphs
Venue: arXiv cs.DS 2017
Year: 2017

In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph $G$ and an integer $r_{uv}$ for every pair of vertices $u,v\in V(G)$. The objective is to construct a subgraph $H$ of minimum weight which contains $r_{uv}$ edge-disjoint (or node-disjoint) $u$-$v$ paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. In this paper, we consider the version of the problem where we are given a $λ$-edge connected (di)graph $G$ with a non-negative weight function $w$ on the edges and an integer $k$, and the objective is to find a minimum weight spanning subgraph $H$ that is also $λ$-edge connected, and has at least $k$ fewer edges than $G$. In other words, we are asked to compute a maximum weight subset of edges, of cardinality up to $k$, which may be safely deleted from $G$. Motivated by this question, we investigate the connectivity properties of $λ$-edge connected (di)graphs and obtain algorithmically significant structural results. We demonstrate the importance of our structural results by presenting an algorithm running in time $2^{O(k \log k)} |V(G)|^{O(1)}$ for $λ$-ECS, thus proving its fixed-parameter tractability. We follow up on this result and obtain the {\em first polynomial compression} for $λ$-ECS on unweighted graphs. As a consequence, we also obtain the first fixed parameter tractable algorithm, and a polynomial kernel for a parameterized version of the classic Mininum Equivalent Graph problem. We believe that our structural results are of independent interest and will play a crucial role in the design of algorithms for connectivity-constrained problems in general and the SNDP problem in particular.
Generalisation in Named Entity Recognition: A Quantitative Analysis
Venue: arXiv cs.CL 2017
Year: 2017

Named Entity Recognition (NER) is a key NLP task, which is all the more challenging on Web and user-generated content with their diverse and continuously changing language. This paper aims to quantify how this diversity impacts state-of-the-art NER methods, by measuring named entity (NE) and context variability, feature sparsity, and their effects on precision and recall. In particular, our findings indicate that NER approaches struggle to generalise in diverse genres with limited training data. Unseen NEs, in particular, play an important role, which have a higher incidence in diverse genres such as social media than in more regular genres such as newswire. Coupled with a higher incidence of unseen features more generally and the lack of large training corpora, this leads to significantly lower F1 scores for diverse genres as compared to more regular ones. We also find that leading systems rely heavily on surface forms found in training data, having problems generalising beyond these, and offer explanations for this observation.
The Secrecy Capacity of Gaussian MIMO Channels with Finite Memory - Full Version
Venue: arXiv cs.IT 2017
Year: 2017

In this work we study the secrecy capacity of Gaussian multiple-input multiple-output (MIMO) wiretap channels (WTCs) with a finite memory, subject to a per-symbol average power constraint on the MIMO channel input. MIMO channels with finite memory are very common in wireless communications as well as in wireline communications (e.g., in communications over power lines). To derive the secrecy capacity of the Gaussian MIMO WTC with finite memory we first construct an asymptotically-equivalent block-memoryless MIMO WTC, which is then transformed into a set of parallel, independent, memoryless MIMO WTCs in the frequency domain. The secrecy capacity of the Gaussian MIMO WTC with finite memory is obtained as the secrecy capacity of the set of parallel independent memoryless MIMO WTCs, and is expressed as a maximization over the input covariance matrices in the frequency domain. Lastly, we detail two applications of our result: First, we show that the secrecy capacity of the Gaussian scalar WTC with finite memory can be achieved by waterfilling, and obtain a closed-form expression for this secrecy capacity. Then, we use our result to characterize the secrecy capacity of narrowband powerline channels, thereby resolving one of the major open issues for this channel model.
A note on dual demodulator continuous transmission frequency modulation technique
Venue: arXiv cs.IT 2017
Year: 2017

The range resolution in conventional continuous time frequency modulation (CTFM) is inversely proportional to the signal bandwidth. The dual-demodulator continuous time frequency modulation (DD-CTFM) processing technique was proposed by Gough et al [1] as a method to increase the range resolution by making the output of DD-CTFM truly continuous. However, it has been found that in practice the range resolution is still limited by the signal bandwidth. The limitation of DD-CTFM has been explained using simulations and mathematically in this paper.
Unhappy Developers: Bad for Themselves, Bad for Process, and Bad for Software Product
Venue: arXiv cs.SE 2017
Year: 2017

Recent research in software engineering supports the "happy-productive" thesis, and the desire of flourishing happiness among programmers is often expressed by industry practitioners. Recent literature has suggested that a cost-effective way to foster happiness and productivity among workers could be to limit unhappiness of developers due to its negative impact. However, possible negative effects of unhappiness are still largely unknown in the software development context. In this paper, we present the first results from a study exploring the consequences of the unhappy developers. Using qualitative data analysis of the survey responses given by 181 participants, we identified 49 potential consequences of unhappiness while developing software. These results have several implications. While raising the awareness of the role of moods, emotions and feelings in software development, we foresee that our classification scheme will spawn new happiness studies linking causes and effects, and it can act as a guideline for developers and managers to foster happiness at work.
Reachability in Augmented Interval Markov Chains
Venue: arXiv cs.CC 2017
Year: 2017

In this paper we propose augmented interval Markov chains (AIMCs): a generalisation of the familiar interval Markov chains (IMCs) where uncertain transition probabilities are in addition allowed to depend on one another. This new model preserves the flexibility afforded by IMCs for describing stochastic systems where the parameters are unclear, for example due to measurement error, but also allows us to specify transitions with probabilities known to be identical, thereby lending further expressivity. The focus of this paper is reachability in AIMCs. We study the qualitative, exact quantitative and approximate reachability problem, as well as natural subproblems thereof, and establish several upper and lower bounds for their complexity. We prove the exact reachability problem is at least as hard as the famous square-root sum problem, but, encouragingly, the approximate version lies in $\mathbf{NP}$ if the underlying graph is known, whilst the restriction of the exact problem to a constant number of uncertain edges is in $\mathbf{P}$. Finally, we show that uncertainty in the graph structure affects complexity by proving $\mathbf{NP}$-completeness for the qualitative subproblem, in contrast with an easily-obtained upper bound of $\mathbf{P}$ for the same subproblem with known graph structure.
Parallel mining of time-faded heavy hitters
Venue: arXiv cs.DS 2017
Year: 2017

We present PFDCMSS, a novel message-passing based parallel algorithm for mining time-faded heavy hitters. The algorithm is a parallel version of the recently published FDCMSS sequential algorithm. We formally prove its correctness by showing that the underlying data structure, a sketch augmented with a Space Saving stream summary holding exactly two counters, is mergeable. Whilst mergeability of traditional sketches derives immediately from theory, we show that merging our augmented sketch is non trivial. Nonetheless, the resulting parallel algorithm is fast and simple to implement. To the best of our knowledge, PFDCMSS is the first parallel algorithm solving the problem of mining time-faded heavy hitters on message-passing parallel architectures. Extensive experimental results confirm that PFDCMSS retains the extreme accuracy and error bound provided by FDCMSS whilst providing excellent parallel scalability.
How to Quantize $n$ Outputs of a Binary Symmetric Channel to $n-1$ Bits?
Venue: arXiv cs.IT 2017
Year: 2017

Suppose that $Y^n$ is obtained by observing a uniform Bernoulli random vector $X^n$ through a binary symmetric channel with crossover probability $α$. The "most informative Boolean function" conjecture postulates that the maximal mutual information between $Y^n$ and any Boolean function $\mathrm{b}(X^n)$ is attained by a dictator function. In this paper, we consider the "complementary" case in which the Boolean function is replaced by $f:\left\{0,1\right\}^n\to\left\{0,1\right\}^{n-1}$, namely, an $n-1$ bit quantizer, and show that $I(f(X^n);Y^n)\leq (n-1)\cdot\left(1-h(α)\right)$ for any such $f$. Thus, in this case, the optimal function is of the form $f(x^n)=(x_1,\ldots,x_{n-1})$.
An Accurate Interconnect Test Structure for Parasitic Validation in On-Chip Machine Learning Accelerators
Venue: arXiv cs.ET 2017
Year: 2017

For nanotechnology nodes, the feature size is shrunk rapidly, the wire becomes narrow and thin, it leads to high RC parasitic, especially for resistance. The overall system performance are dominated by interconnect rather than device. As such, it is imperative to accurately measure and model interconnect parasitic in order to predict interconnect performance on silicon. Despite many test structures developed in the past to characterize device models and layout effects, only few of them are available for interconnects. Nevertheless, they are either not suitable for real chip implementation or too complicated to be embedded. A compact yet comprehensive test structure to capture all interconnect parasitic in a real chip is needed. To address this problem, this paper describes a set of test structures that can be used to study the timing performance (i.e. propagation delay and crosstalk) of various interconnect configurations. Moreover, an empirical model is developed to estimate the actual RC parasitic. Compared with the state-of-the-art interconnect test structures, the new structure is compact in size and can be easily embedded on die as a parasitic variation monitor. We have validated the proposed structure on a test chip in TSMC 28nm HPM process. Recently, the test structure is further modified to identify the serious interconnect process issues for critical path design using TSMC 7nm FF process.